summaryrefslogtreecommitdiffstats
path: root/src/vppinfra/vec.h
diff options
context:
space:
mode:
authorDamjan Marion <damarion@cisco.com>2022-03-19 00:07:52 +0100
committerFlorin Coras <florin.coras@gmail.com>2022-03-30 18:27:13 +0000
commit299571aca34d36e637e43cfbba6275662d0d7795 (patch)
treea48be21950d082afb7dd93562f76f0ba554e8919 /src/vppinfra/vec.h
parent9539647b895c456ca53892a9259e3127c6b92d35 (diff)
vppinfra: vector allocator rework
- support of in-place growth of vectors (if there is available space next to existing alloc) - drops the need for alloc_aligned_at_offset from memory allocator, which allows easier swap to different memory allocator and reduces malloc overhead - rework of pool and vec macros to inline functions to improve debuggability - fix alignment - in many cases macros were not using native alignment of the particular datatype. Explicitly setting alignment with XXX_aligned() versions of the macro is not needed anymore in > 99% of cases - fix ASAN usage - avoid use of vector of voids, this was root cause of several bugs found in vec_* and pool_* function where sizeof() was used on voids instead of real vector data type - introduce minimal alignment which is currently 8 bytes, vectors will be always aligned at least to that value (underlay allocator actually always provide 16-byte aligned allocs) Type: improvement Change-Id: I20f4b081bb13bbf7bc0ace85cc4e301787f12fdf Signed-off-by: Damjan Marion <damarion@cisco.com>
Diffstat (limited to 'src/vppinfra/vec.h')
-rw-r--r--src/vppinfra/vec.h701
1 files changed, 373 insertions, 328 deletions
diff --git a/src/vppinfra/vec.h b/src/vppinfra/vec.h
index 8f42149021a..e90c27c1bc1 100644
--- a/src/vppinfra/vec.h
+++ b/src/vppinfra/vec.h
@@ -52,11 +52,12 @@
The memory layout looks like this:
~~~~~~~~
- user header (aligned to uword boundary)
- vector length: number of elements
+ user header (start of memory allocation)
+ padding
+ vector header: number of elements, header size
user's pointer-> vector element #0
- vector element #1
- ...
+ vector element #1
+ ...
~~~~~~~~
The user pointer contains the address of vector element # 0. Null
@@ -70,8 +71,9 @@
Typically, the header is not present. Headers allow for other
data structures to be built atop CLIB vectors.
- Users may specify the alignment for first data element of a vector
- via the vec_*_aligned macros.
+ While users may specify the alignment for first data element of a vector
+ via the vec_*_aligned macros that is typically not needed as alignment
+ is set based on native alignment of the data structure used.
Vector elements can be any C type e.g. (int, double, struct bar).
This is also true for data types built atop vectors (e.g. heap,
@@ -89,91 +91,79 @@
which are invariant.
*/
-/** \brief Low-level resize allocation function, usually not called directly
+/** \brief Low-level (re)allocation function, usually not called directly
@param v pointer to a vector
- @param length_increment length increment in elements
- @param data_bytes requested size in bytes
- @param header_bytes header size in bytes (may be zero)
- @param data_align alignment (may be zero)
+ @param n_elts requested number of elements
+ @param elt_sz requested size of one element
+ @param hdr_sz header size in bytes (may be zero)
+ @param align alignment (may be zero)
@return v_prime pointer to resized vector, may or may not equal v
*/
-void *vec_resize_allocate_memory (void *v, word length_increment,
- uword data_bytes, uword header_bytes,
- uword data_align);
+void *_vec_realloc (void *v, uword n_elts, uword elt_sz, uword hdr_sz,
+ uword align, void *heap);
-/** \brief Low-level vector resize function, usually not called directly
+/* calculate minimum alignment out of data natural alignment and provided
+ * value, should not be < VEC_MIN_ALIGN */
+static_always_inline uword
+__vec_align (uword data_align, uword configuered_align)
+{
+ data_align = clib_max (data_align, configuered_align);
+ ASSERT (count_set_bits (data_align) == 1);
+ return clib_max (VEC_MIN_ALIGN, data_align);
+}
- @param v pointer to a vector
- @param length_increment length increment in elements
- @param data_bytes requested size in bytes
- @param header_bytes header size in bytes (may be zero)
- @param data_align alignment (may be zero)
- @return v_prime pointer to resized vector, may or may not equal v
-*/
+/* function used t o catch cases where vec_* macros on used on void * */
+static_always_inline uword
+__vec_elt_sz (uword elt_sz, int is_void)
+{
+ /* vector macro operations on void * are not allowed */
+ ASSERT (is_void == 0);
+ return elt_sz;
+}
-#define _vec_resize(V, L, DB, HB, A) \
- ({ \
- __typeof__ ((V)) _V; \
- _V = _vec_resize_inline ((void *) V, L, DB, HB, \
- clib_max ((__alignof__((V)[0])), (A))); \
- _V; \
- })
+static_always_inline void
+_vec_update_pointer (void **vp, void *v)
+{
+ /* avoid store if not needed */
+ if (v != vp[0])
+ vp[0] = v;
+}
always_inline void *
-_vec_resize_inline (void *v, word length_increment, uword data_bytes,
- uword header_bytes, uword data_align)
+_vec_realloc_inline (void *v, uword n_elts, uword elt_sz, uword hdr_sz,
+ uword align, void *heap)
{
- vec_header_t *vh = _vec_find (v);
- uword new_data_bytes, aligned_header_bytes;
-
- aligned_header_bytes = vec_header_bytes (header_bytes);
-
- new_data_bytes = data_bytes + aligned_header_bytes;
-
if (PREDICT_TRUE (v != 0))
{
- void *p = v - aligned_header_bytes;
-
/* Vector header must start heap object. */
- ASSERT (clib_mem_is_heap_object (p));
+ ASSERT (clib_mem_is_heap_object (vec_header (v)));
/* Typically we'll not need to resize. */
- if (new_data_bytes <= clib_mem_size (p))
+ if ((n_elts * elt_sz) <= vec_max_bytes (v))
{
- CLIB_MEM_UNPOISON (v, data_bytes);
- vh->len += length_increment;
+ _vec_set_len (v, n_elts, elt_sz);
return v;
}
}
/* Slow path: call helper function. */
- return vec_resize_allocate_memory (
- v, length_increment, data_bytes, header_bytes,
- clib_max (sizeof (vec_header_t), data_align));
+ return _vec_realloc (v, n_elts, elt_sz, hdr_sz, align, heap);
}
-/** \brief Determine if vector will resize with next allocation
-
- @param v pointer to a vector
- @param length_increment length increment in elements
- @param data_bytes requested size in bytes
- @param header_bytes header size in bytes (may be zero)
- @param data_align alignment (may be zero)
- @return 1 if vector will resize 0 otherwise
-*/
-
always_inline int
-_vec_resize_will_expand (void *v, uword n_elts, uword elt_size)
+_vec_resize_will_expand (void *v, uword n_elts, uword elt_sz)
{
- if (PREDICT_TRUE (v != 0))
- {
- /* Vector header must start heap object. */
- ASSERT (clib_mem_is_heap_object (vec_header (v)));
+ if (v == 0)
+ return 1;
+
+ /* Vector header must start heap object. */
+ ASSERT (clib_mem_is_heap_object (vec_header (v)));
+
+ n_elts += _vec_len (v);
+ if ((n_elts * elt_sz) <= vec_max_bytes (v))
+ return 0;
- if (vec_mem_size (v) >= ((_vec_len (v) + n_elts)) * elt_size)
- return 0;
- }
return 1;
}
@@ -185,7 +175,7 @@ _vec_resize_will_expand (void *v, uword n_elts, uword elt_size)
*/
#define vec_resize_will_expand(V, N) \
- _vec_resize_will_expand (V, N, sizeof ((V)[0]))
+ _vec_resize_will_expand (V, N, _vec_elt_sz (V))
/* Local variable naming macro (prevents collisions with other macro naming). */
#define _v(var) _vec_##var
@@ -202,15 +192,16 @@ _vec_resize_will_expand (void *v, uword n_elts, uword elt_size)
@return V (value-result macro parameter)
*/
+static_always_inline void
+_vec_resize (void **vp, uword n_add, uword hdr_sz, uword align, uword elt_sz)
+{
+ void *v = vp[0];
+ v = _vec_realloc_inline (v, vec_len (v) + n_add, elt_sz, hdr_sz, align, 0);
+ _vec_update_pointer (vp, v);
+}
+
#define vec_resize_ha(V, N, H, A) \
- do \
- { \
- word _v (n) = (N); \
- word _v (l) = vec_len (V); \
- V = _vec_resize ((V), _v (n), (_v (l) + _v (n)) * sizeof ((V)[0]), (H), \
- (A)); \
- } \
- while (0)
+ _vec_resize ((void **) &(V), N, H, _vec_align (V, A), _vec_elt_sz (V))
/** \brief Resize a vector (no header, unspecified alignment)
Add N elements to end of given vector V, return pointer to start of vector.
@@ -245,12 +236,14 @@ _vec_resize_will_expand (void *v, uword n_elts, uword elt_size)
@return V (value-result macro parameter)
*/
-#define vec_alloc_ha(V,N,H,A) \
-do { \
- uword _v(l) = vec_len (V); \
- vec_resize_ha (V, N, H, A); \
- _vec_len (V) = _v(l); \
-} while (0)
+#define vec_alloc_ha(V, N, H, A) \
+ do \
+ { \
+ uword _v (l) = vec_len (V); \
+ vec_resize_ha (V, N, H, A); \
+ vec_set_len (V, _v (l)); \
+ } \
+ while (0)
/** \brief Allocate space for N more elements
(no header, unspecified alignment)
@@ -277,11 +270,8 @@ do { \
@param A alignment (may be zero)
@return V new vector
*/
-#define vec_new_ha(T,N,H,A) \
-({ \
- word _v(n) = (N); \
- (T *)_vec_resize ((T *) 0, _v(n), _v(n) * sizeof (T), (H), (A)); \
-})
+#define vec_new_ha(T, N, H, A) \
+ _vec_realloc (0, N, sizeof (T), H, _vec_align ((T *) 0, A), 0)
/** \brief Create new vector of given type and length
(unspecified alignment, no header).
@@ -305,16 +295,17 @@ do { \
@param V pointer to a vector
@return V (value-result parameter, V=0)
*/
-#define vec_free(V) \
- do \
- { \
- if (V) \
- { \
- clib_mem_free (vec_header ((V))); \
- V = 0; \
- } \
- } \
- while (0)
+
+static_always_inline void
+_vec_free (void **vp)
+{
+ if (vp[0] == 0)
+ return;
+ clib_mem_free (vec_header (vp[0]));
+ vp[0] = 0;
+}
+
+#define vec_free(V) _vec_free ((void **) &(V))
void vec_free_not_inline (void *v);
@@ -333,17 +324,22 @@ void vec_free_not_inline (void *v);
@return Vdup copy of vector
*/
+static_always_inline void *
+_vec_dup (void *v, uword hdr_size, uword align, uword elt_sz)
+{
+ uword len = vec_len (v);
+ void *n = 0;
+
+ if (len)
+ {
+ n = _vec_realloc (0, len, elt_sz, hdr_size, align, 0);
+ clib_memcpy_fast (n, v, len * elt_sz);
+ }
+ return n;
+}
+
#define vec_dup_ha(V, H, A) \
- ({ \
- __typeof__ ((V)[0]) *_v (v) = 0; \
- uword _v (l) = vec_len (V); \
- if (_v (l) > 0) \
- { \
- vec_resize_ha (_v (v), _v (l), (H), (A)); \
- clib_memcpy_fast (_v (v), (V), _v (l) * sizeof ((V)[0])); \
- } \
- _v (v); \
- })
+ _vec_dup ((void *) (V), H, _vec_align (V, A), _vec_elt_sz (V))
/** \brief Return copy of vector (no header, no alignment)
@@ -376,12 +372,15 @@ void vec_free_not_inline (void *v);
@param NEW_V pointer to new vector
@param OLD_V pointer to old vector
*/
-#define vec_clone(NEW_V,OLD_V) \
-do { \
- (NEW_V) = 0; \
- (NEW_V) = _vec_resize ((NEW_V), vec_len (OLD_V), \
- vec_len (OLD_V) * sizeof ((NEW_V)[0]), (0), (0)); \
-} while (0)
+
+static_always_inline void
+_vec_clone (void **v1p, void *v2, uword align, uword elt_sz)
+{
+ v1p[0] = _vec_realloc (0, vec_len (v2), elt_sz, 0, align, 0);
+}
+#define vec_clone(NEW_V, OLD_V) \
+ _vec_clone ((void **) &(NEW_V), OLD_V, _vec_align (NEW_V, 0), \
+ _vec_elt_sz (NEW_V))
/** \brief Make sure vector is long enough for given index (general version).
@@ -392,24 +391,29 @@ do { \
@return V (value-result macro parameter)
*/
+always_inline void
+_vec_zero_elts (void *v, uword first, uword count, uword elt_sz)
+{
+ clib_memset_u8 (v + (first * elt_sz), 0, count * elt_sz);
+}
+#define vec_zero_elts(V, F, C) _vec_zero_elts (V, F, C, sizeof ((V)[0]))
+
+static_always_inline void *
+_vec_validate_ha (void *v, uword index, uword header_size, uword align,
+ uword elt_sz)
+{
+ uword vl = vec_len (v);
+ if (index >= vl)
+ {
+ v = _vec_realloc_inline (v, index + 1, elt_sz, header_size, align, 0);
+ _vec_zero_elts (v, vl, index - vl + 1, elt_sz);
+ }
+ return v;
+}
+
#define vec_validate_ha(V, I, H, A) \
- do \
- { \
- STATIC_ASSERT (A == 0 || ((A % sizeof (V[0])) == 0) || \
- ((sizeof (V[0]) % A) == 0), \
- "vector validate aligned on incorrectly sized object"); \
- word _v (i) = (I); \
- word _v (l) = vec_len (V); \
- if (_v (i) >= _v (l)) \
- { \
- vec_resize_ha ((V), 1 + (_v (i) - _v (l)), (H), (A)); \
- /* Must zero new space since user may have previously \
- used e.g. _vec_len (v) -= 10 */ \
- clib_memset ((V) + _v (l), 0, \
- (1 + (_v (i) - _v (l))) * sizeof ((V)[0])); \
- } \
- } \
- while (0)
+ (V) = \
+ _vec_validate_ha ((void *) (V), I, H, _vec_align (V, A), sizeof ((V)[0]))
/** \brief Make sure vector is long enough for given index
(no header, unspecified alignment)
@@ -441,20 +445,22 @@ do { \
@param A alignment (may be zero)
@return V (value-result macro parameter)
*/
-#define vec_validate_init_empty_ha(V,I,INIT,H,A) \
-do { \
- word _v(i) = (I); \
- word _v(l) = vec_len (V); \
- if (_v(i) >= _v(l)) \
- { \
- vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A)); \
- while (_v(l) <= _v(i)) \
- { \
- (V)[_v(l)] = (INIT); \
- _v(l)++; \
- } \
- } \
-} while (0)
+#define vec_validate_init_empty_ha(V, I, INIT, H, A) \
+ do \
+ { \
+ word _v (i) = (I); \
+ word _v (l) = vec_len (V); \
+ if (_v (i) >= _v (l)) \
+ { \
+ vec_resize_ha (V, 1 + (_v (i) - _v (l)), H, A); \
+ while (_v (l) <= _v (i)) \
+ { \
+ (V)[_v (l)] = (INIT); \
+ _v (l)++; \
+ } \
+ } \
+ } \
+ while (0)
/** \brief Make sure vector is long enough for given index
and initialize empty space (no header, unspecified alignment)
@@ -488,12 +494,22 @@ do { \
@param A alignment (may be zero)
@return V (value-result macro parameter)
*/
-#define vec_add1_ha(V,E,H,A) \
-do { \
- word _v(l) = vec_len (V); \
- V = _vec_resize ((V), 1, (_v(l) + 1) * sizeof ((V)[0]), (H), (A)); \
- (V)[_v(l)] = (E); \
-} while (0)
+
+static_always_inline void *
+_vec_add1 (void **vp, uword hdr_sz, uword align, uword elt_sz)
+{
+ void *v = vp[0];
+ uword len = vec_len (v);
+ v = _vec_realloc_inline (v, len + 1, elt_sz, hdr_sz, align, 0);
+
+ _vec_update_pointer (vp, v);
+
+ return v + len * elt_sz;
+}
+
+#define vec_add1_ha(V, E, H, A) \
+ ((__typeof__ ((V)[0]) *) _vec_add1 ((void **) &(V), H, _vec_align (V, A), \
+ _vec_elt_sz (V)))[0] = (E)
/** \brief Add 1 element to end of vector (unspecified alignment).
@@ -522,13 +538,21 @@ do { \
@param A alignment (may be zero)
@return V and P (value-result macro parameters)
*/
-#define vec_add2_ha(V,P,N,H,A) \
-do { \
- word _v(n) = (N); \
- word _v(l) = vec_len (V); \
- V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A)); \
- P = (V) + _v(l); \
-} while (0)
+
+static_always_inline void
+_vec_add2 (void **vp, void **pp, uword n_add, uword hdr_sz, uword align,
+ uword elt_sz)
+{
+ void *v = vp[0];
+ uword len = vec_len (vp[0]);
+ v = _vec_realloc_inline (v, len + n_add, elt_sz, hdr_sz, align, 0);
+ _vec_update_pointer (vp, v);
+ pp[0] = v + len * elt_sz;
+}
+
+#define vec_add2_ha(V, P, N, H, A) \
+ _vec_add2 ((void **) &(V), (void **) &(P), N, H, _vec_align (V, A), \
+ _vec_elt_sz (V))
/** \brief Add N elements to end of vector V,
return pointer to new elements in P. (no header, unspecified alignment)
@@ -562,19 +586,26 @@ do { \
@param A alignment (may be zero)
@return V (value-result macro parameter)
*/
+static_always_inline void
+_vec_add (void **vp, void *e, word n_add, uword hdr_sz, uword align,
+ uword elt_sz)
+{
+ void *v = vp[0];
+ uword len = vec_len (v);
+
+ ASSERT (n_add >= 0);
+
+ if (n_add < 1)
+ return;
+
+ v = _vec_realloc_inline (v, len + n_add, elt_sz, hdr_sz, align, 0);
+ clib_memcpy_fast (v + len * elt_sz, e, n_add * elt_sz);
+ _vec_update_pointer (vp, v);
+}
+
#define vec_add_ha(V, E, N, H, A) \
- do \
- { \
- word _v (n) = (N); \
- if (PREDICT_TRUE (_v (n) > 0)) \
- { \
- word _v (l) = vec_len (V); \
- V = _vec_resize ((V), _v (n), (_v (l) + _v (n)) * sizeof ((V)[0]), \
- (H), (A)); \
- clib_memcpy_fast ((V) + _v (l), (E), _v (n) * sizeof ((V)[0])); \
- } \
- } \
- while (0)
+ _vec_add ((void **) &(V), (void *) (E), N, H, _vec_align (V, A), \
+ _vec_elt_sz (V))
/** \brief Add N elements to end of vector V (no header, unspecified alignment)
@@ -600,14 +631,16 @@ do { \
@param V pointer to a vector
@return E element removed from the end of the vector
*/
-#define vec_pop(V) \
-({ \
- uword _v(l) = vec_len (V); \
- ASSERT (_v(l) > 0); \
- _v(l) -= 1; \
- _vec_len (V) = _v (l); \
- (V)[_v(l)]; \
-})
+#define vec_pop(V) \
+ ({ \
+ uword _v (l) = vec_len (V); \
+ __typeof__ ((V)[0]) _v (rv); \
+ ASSERT (_v (l) > 0); \
+ _v (l) -= 1; \
+ _v (rv) = (V)[_v (l)]; \
+ vec_set_len (V, _v (l)); \
+ (_v (rv)); \
+ })
/** \brief Set E to the last element of a vector, decrement vector length
@param V pointer to a vector
@@ -634,21 +667,26 @@ do { \
@param A alignment (may be zero)
@return V (value-result macro parameter)
*/
-#define vec_insert_init_empty_ha(V,N,M,INIT,H,A) \
-do { \
- word _v(l) = vec_len (V); \
- word _v(n) = (N); \
- word _v(m) = (M); \
- V = _vec_resize ((V), \
- _v(n), \
- (_v(l) + _v(n))*sizeof((V)[0]), \
- (H), (A)); \
- ASSERT (_v(m) <= _v(l)); \
- memmove ((V) + _v(m) + _v(n), \
- (V) + _v(m), \
- (_v(l) - _v(m)) * sizeof ((V)[0])); \
- clib_memset ((V) + _v(m), INIT, _v(n) * sizeof ((V)[0])); \
-} while (0)
+
+static_always_inline void
+_vec_insert (void **vp, uword n_insert, uword ins_pt, u8 init, uword hdr_sz,
+ uword align, uword elt_sz)
+{
+ void *v = vp[0];
+ uword len = vec_len (v);
+
+ ASSERT (ins_pt <= len);
+
+ v = _vec_realloc_inline (v, len + n_insert, elt_sz, hdr_sz, align, 0);
+ clib_memmove (v + elt_sz * (ins_pt + n_insert), v + ins_pt * elt_sz,
+ (len - ins_pt) * elt_sz);
+ _vec_zero_elts (v, ins_pt, n_insert, elt_sz);
+ _vec_update_pointer (vp, v);
+}
+
+#define vec_insert_init_empty_ha(V, N, M, INIT, H, A) \
+ _vec_insert ((void **) &(V), N, M, INIT, H, _vec_align (V, A), \
+ _vec_elt_sz (V))
/** \brief Insert N vector elements starting at element M,
initialize new elements to zero (general version)
@@ -722,23 +760,26 @@ do { \
@return V (value-result macro parameter)
*/
+static_always_inline void
+_vec_insert_elts (void **vp, void *e, uword n_insert, uword ins_pt,
+ uword hdr_sz, uword align, uword elt_sz)
+{
+ void *v = vp[0];
+ uword len = vec_len (v);
+
+ ASSERT (ins_pt <= len);
+
+ v = _vec_realloc_inline (v, len + n_insert, elt_sz, hdr_sz, align, 0);
+ clib_memmove (v + elt_sz * (ins_pt + n_insert), v + ins_pt * elt_sz,
+ (len - ins_pt) * elt_sz);
+ _vec_zero_elts (v, ins_pt, n_insert, elt_sz);
+ clib_memcpy_fast (v + ins_pt * elt_sz, e, n_insert * elt_sz);
+ _vec_update_pointer (vp, v);
+}
+
#define vec_insert_elts_ha(V, E, N, M, H, A) \
- do \
- { \
- word _v (n) = (N); \
- if (PREDICT_TRUE (_v (n) > 0)) \
- { \
- word _v (l) = vec_len (V); \
- word _v (m) = (M); \
- V = _vec_resize ((V), _v (n), (_v (l) + _v (n)) * sizeof ((V)[0]), \
- (H), (A)); \
- ASSERT (_v (m) <= _v (l)); \
- memmove ((V) + _v (m) + _v (n), (V) + _v (m), \
- (_v (l) - _v (m)) * sizeof ((V)[0])); \
- clib_memcpy_fast ((V) + _v (m), (E), _v (n) * sizeof ((V)[0])); \
- } \
- } \
- while (0)
+ _vec_insert_elts ((void **) &(V), E, N, M, H, _vec_align (V, A), \
+ _vec_elt_sz (V))
/** \brief Insert N vector elements starting at element M,
insert given elements (no header, unspecified alignment)
@@ -770,57 +811,65 @@ do { \
@param M first element to delete
@return V (value-result macro parameter)
*/
-#define vec_delete(V,N,M) \
-do { \
- word _v(l) = vec_len (V); \
- word _v(n) = (N); \
- word _v(m) = (M); \
- /* Copy over deleted elements. */ \
- if (_v(l) - _v(n) - _v(m) > 0) \
- memmove ((V) + _v(m), (V) + _v(m) + _v(n), \
- (_v(l) - _v(n) - _v(m)) * sizeof ((V)[0])); \
- /* Zero empty space at end (for future re-allocation). */ \
- if (_v(n) > 0) \
- clib_memset ((V) + _v(l) - _v(n), 0, _v(n) * sizeof ((V)[0])); \
- _vec_len (V) -= _v(n); \
- CLIB_MEM_POISON(vec_end(V), _v(n) * sizeof ((V)[0])); \
-} while (0)
+
+static_always_inline void
+_vec_delete (void *v, uword n_del, uword first, uword elt_sz)
+{
+ word n_bytes_del, n_bytes_to_move, len = vec_len (v);
+ u8 *dst;
+
+ if (n_del == 0)
+ return;
+
+ ASSERT (first + n_del <= len);
+
+ n_bytes_del = n_del * elt_sz;
+ n_bytes_to_move = (len - first - n_del) * elt_sz;
+ dst = v + first * elt_sz;
+
+ if (n_bytes_to_move > 0)
+ clib_memmove (dst, dst + n_bytes_del, n_bytes_to_move);
+ clib_memset (dst + n_bytes_to_move, 0, n_bytes_del);
+
+ _vec_set_len (v, _vec_len (v) - n_del, elt_sz);
+}
+
+#define vec_delete(V, N, M) _vec_delete ((void *) (V), N, M, _vec_elt_sz (V))
/** \brief Delete the element at index I
@param V pointer to a vector
@param I index to delete
*/
-#define vec_del1(v,i) \
-do { \
- uword _vec_del_l = _vec_len (v) - 1; \
- uword _vec_del_i = (i); \
- if (_vec_del_i < _vec_del_l) \
- (v)[_vec_del_i] = (v)[_vec_del_l]; \
- _vec_len (v) = _vec_del_l; \
- CLIB_MEM_POISON(vec_end(v), sizeof ((v)[0])); \
-} while (0)
-/** \brief Append v2 after v1. Result in v1.
- @param V1 target vector
- @param V2 vector to append
-*/
+static_always_inline void
+_vec_del1 (void *v, uword index, uword elt_sz)
+{
+ uword len = _vec_len (v) - 1;
-#define vec_append(v1, v2) \
- do \
- { \
- uword _v (l1) = vec_len (v1); \
- uword _v (l2) = vec_len (v2); \
- \
- if (PREDICT_TRUE (_v (l2) > 0)) \
- { \
- v1 = _vec_resize ((v1), _v (l2), \
- (_v (l1) + _v (l2)) * sizeof ((v1)[0]), 0, 0); \
- clib_memcpy_fast ((v1) + _v (l1), (v2), \
- _v (l2) * sizeof ((v2)[0])); \
- } \
- } \
- while (0)
+ if (index < len)
+ clib_memcpy_fast (v + index * elt_sz, v + len * elt_sz, elt_sz);
+
+ _vec_set_len (v, len, elt_sz);
+}
+
+#define vec_del1(v, i) _vec_del1 ((void *) (v), i, _vec_elt_sz (v))
+
+static_always_inline void
+_vec_append (void **v1p, void *v2, uword v1_elt_sz, uword v2_elt_sz,
+ uword align)
+{
+ void *v1 = v1p[0];
+ uword len1 = vec_len (v1);
+ uword len2 = vec_len (v2);
+
+ if (PREDICT_TRUE (len2 > 0))
+ {
+ v1 = _vec_realloc_inline (v1, len1 + len2, v2_elt_sz, 0, align, 0);
+ clib_memcpy_fast (v1 + len1 * v1_elt_sz, v2, len2 * v2_elt_sz);
+ _vec_update_pointer (v1p, v1);
+ }
+}
/** \brief Append v2 after v1. Result in v1. Specified alignment.
@param V1 target vector
@@ -829,41 +878,32 @@ do { \
*/
#define vec_append_aligned(v1, v2, align) \
- do \
- { \
- uword _v (l1) = vec_len (v1); \
- uword _v (l2) = vec_len (v2); \
- \
- if (PREDICT_TRUE (_v (l2) > 0)) \
- { \
- v1 = _vec_resize ( \
- (v1), _v (l2), (_v (l1) + _v (l2)) * sizeof ((v1)[0]), 0, align); \
- clib_memcpy_fast ((v1) + _v (l1), (v2), \
- _v (l2) * sizeof ((v2)[0])); \
- } \
- } \
- while (0)
+ _vec_append ((void **) &(v1), (void *) (v2), _vec_elt_sz (v1), \
+ _vec_elt_sz (v2), _vec_align (v1, align))
-/** \brief Prepend v2 before v1. Result in v1.
+/** \brief Append v2 after v1. Result in v1.
@param V1 target vector
- @param V2 vector to prepend
+ @param V2 vector to append
*/
-#define vec_prepend(v1, v2) \
- do \
- { \
- uword _v (l1) = vec_len (v1); \
- uword _v (l2) = vec_len (v2); \
- \
- if (PREDICT_TRUE (_v (l2) > 0)) \
- { \
- v1 = _vec_resize ((v1), _v (l2), \
- (_v (l1) + _v (l2)) * sizeof ((v1)[0]), 0, 0); \
- memmove ((v1) + _v (l2), (v1), _v (l1) * sizeof ((v1)[0])); \
- clib_memcpy_fast ((v1), (v2), _v (l2) * sizeof ((v2)[0])); \
- } \
- } \
- while (0)
+#define vec_append(v1, v2) vec_append_aligned (v1, v2, 0)
+
+static_always_inline void
+_vec_prepend (void **v1p, void *v2, uword v1_elt_sz, uword v2_elt_sz,
+ uword align)
+{
+ void *v1 = v1p[0];
+ uword len1 = vec_len (v1);
+ uword len2 = vec_len (v2);
+
+ if (PREDICT_TRUE (len2 > 0))
+ {
+ v1 = _vec_realloc_inline (v1, len1 + len2, v2_elt_sz, 0, align, 0);
+ clib_memmove (v1 + len2 * v2_elt_sz, v1p[0], len1 * v1_elt_sz);
+ clib_memcpy_fast (v1, v2, len2 * v2_elt_sz);
+ _vec_update_pointer (v1p, v1);
+ }
+}
/** \brief Prepend v2 before v1. Result in v1. Specified alignment
@param V1 target vector
@@ -872,29 +912,29 @@ do { \
*/
#define vec_prepend_aligned(v1, v2, align) \
- do \
- { \
- uword _v (l1) = vec_len (v1); \
- uword _v (l2) = vec_len (v2); \
- \
- if (PREDICT_TRUE (_v (l2) > 0)) \
- { \
- v1 = _vec_resize ( \
- (v1), _v (l2), (_v (l1) + _v (l2)) * sizeof ((v1)[0]), 0, align); \
- memmove ((v1) + _v (l2), (v1), _v (l1) * sizeof ((v1)[0])); \
- clib_memcpy_fast ((v1), (v2), _v (l2) * sizeof ((v2)[0])); \
- } \
- } \
- while (0)
+ _vec_prepend ((void **) &(v1), (void *) (v2), _vec_elt_sz (v1), \
+ _vec_elt_sz (v2), _vec_align (v1, align))
+
+/** \brief Prepend v2 before v1. Result in v1.
+ @param V1 target vector
+ @param V2 vector to prepend
+*/
+
+#define vec_prepend(v1, v2) vec_prepend_aligned (v1, v2, 0)
/** \brief Zero all vector elements. Null-pointer tolerant.
@param var Vector to zero
*/
-#define vec_zero(var) \
-do { \
- if (var) \
- clib_memset ((var), 0, vec_len (var) * sizeof ((var)[0])); \
-} while (0)
+static_always_inline void
+_vec_zero (void *v, uword elt_sz)
+{
+ uword len = vec_len (v);
+
+ if (len)
+ clib_memset_u8 (v, 0, len * elt_sz);
+}
+
+#define vec_zero(var) _vec_zero ((void *) (var), _vec_elt_sz (var))
/** \brief Set all vector elements to given value. Null-pointer tolerant.
@param v vector to set
@@ -918,8 +958,23 @@ do { \
@param v2 Pointer to a vector
@return 1 if equal, 0 if unequal
*/
-#define vec_is_equal(v1,v2) \
- (vec_len (v1) == vec_len (v2) && ! memcmp ((v1), (v2), vec_len (v1) * sizeof ((v1)[0])))
+static_always_inline int
+_vec_is_equal (void *v1, void *v2, uword v1_elt_sz, uword v2_elt_sz)
+{
+ uword vec_len_v1 = vec_len (v1);
+
+ if ((vec_len_v1 != vec_len (v2)) || (v1_elt_sz != v2_elt_sz))
+ return 0;
+
+ if ((vec_len_v1 == 0) || (memcmp (v1, v2, vec_len_v1 * v1_elt_sz) == 0))
+ return 1;
+
+ return 0;
+}
+
+#define vec_is_equal(v1, v2) \
+ _vec_is_equal ((void *) (v1), (void *) (v2), _vec_elt_sz (v1), \
+ _vec_elt_sz (v2))
/** \brief Compare two vectors (only applicable to vectors of signed numbers).
Used in qsort compare functions.
@@ -1004,15 +1059,16 @@ do { \
@param S pointer to string buffer.
@param L string length (NOT including the terminating NULL; a la strlen())
*/
-#define vec_validate_init_c_string(V, S, L) \
- do { \
- vec_reset_length (V); \
- vec_validate ((V), (L)); \
- if ((S) && (L)) \
- clib_memcpy_fast ((V), (S), (L)); \
- (V)[(L)] = 0; \
- } while (0)
-
+#define vec_validate_init_c_string(V, S, L) \
+ do \
+ { \
+ vec_reset_length (V); \
+ vec_validate (V, (L)); \
+ if ((S) && (L)) \
+ clib_memcpy_fast (V, (S), (L)); \
+ (V)[(L)] = 0; \
+ } \
+ while (0)
/** \brief Test whether a vector is a NULL terminated c-string.
@@ -1027,23 +1083,12 @@ do { \
@param V (possibly NULL) pointer to a vector.
@return V (value-result macro parameter)
*/
-#define vec_terminate_c_string(V) \
- do { \
- u32 vl = vec_len ((V)); \
- if (!vec_c_string_is_terminated(V)) \
- { \
- vec_validate ((V), vl); \
- (V)[vl] = 0; \
- } \
- } while (0)
+#define vec_terminate_c_string(V) \
+ do \
+ { \
+ if (!vec_c_string_is_terminated (V)) \
+ vec_add1 (V, 0); \
+ } \
+ while (0)
#endif /* included_vec_h */
-
-
-/*
- * fd.io coding-style-patch-verification: ON
- *
- * Local Variables:
- * eval: (c-set-style "gnu")
- * End:
- */