The memory layout looks like this:
~~~~~~~~
- user header (aligned to uword boundary)
- vector length: number of elements
+ user header (start of memory allocation)
+ padding
+ heap pointer (optional, only if default_heap == 0)
+ 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
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,
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 numa_id numa id (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,
- uword numa_id);
-/** \brief Low-level vector resize function, usually not called directly
+typedef struct
+{
+ void *heap;
+ u32 elt_sz;
+ u16 hdr_sz;
+ u16 align;
+} vec_attr_t;
+
+void *_vec_alloc_internal (uword n_elts, const vec_attr_t *const attr);
+void *_vec_realloc_internal (void *v, uword n_elts,
+ const vec_attr_t *const attr);
+void *_vec_resize_internal (void *v, uword n_elts,
+ const vec_attr_t *const attr);
+
+/* 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)
- @param numa_id (may be ~0)
- @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_numa(V,L,DB,HB,A,S) \
- _vec_resize_inline(V,L,DB,HB,clib_max((__alignof__((V)[0])),(A)),(S))
+static_always_inline void
+_vec_update_pointer (void **vp, void *v)
+{
+ /* avoid store if not needed */
+ if (v != vp[0])
+ vp[0] = v;
+}
-#define _vec_resize(V,L,DB,HB,A) \
- _vec_resize_numa(V,L,DB,HB,A,VEC_NUMA_UNSPECIFIED)
+static_always_inline void *
+vec_get_heap (void *v)
+{
+ if (v == 0 || _vec_find (v)->default_heap == 1)
+ return 0;
+ return _vec_heap (v);
+}
-always_inline void *
-_vec_resize_inline (void *v,
- word length_increment,
- uword data_bytes, uword header_bytes, uword data_align,
- uword numa_id)
+static_always_inline uword
+vec_get_align (void *v)
{
- vec_header_t *vh = _vec_find (v);
- uword new_data_bytes, aligned_header_bytes;
- void *oldheap;
+ return 1ULL << _vec_find (v)->log2_align;
+}
- aligned_header_bytes = vec_header_bytes (header_bytes);
+static_always_inline void
+_vec_prealloc (void **vp, uword n_elts, uword hdr_sz, uword align, void *heap,
+ uword elt_sz)
+{
+ const vec_attr_t va = {
+ .elt_sz = elt_sz, .hdr_sz = hdr_sz, .align = align, .heap = heap
+ };
+ void *v;
- new_data_bytes = data_bytes + aligned_header_bytes;
+ ASSERT (vp[0] == 0);
- if (PREDICT_TRUE (v != 0))
- {
- void *p = v - aligned_header_bytes;
-
- if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
- {
- oldheap = clib_mem_get_per_cpu_heap ();
- clib_mem_set_per_cpu_heap (clib_mem_get_per_numa_heap (numa_id));
- }
-
- /* Vector header must start heap object. */
- ASSERT (clib_mem_is_heap_object (p));
-
- /* Typically we'll not need to resize. */
- if (new_data_bytes <= clib_mem_size (p))
- {
- CLIB_MEM_UNPOISON (v, data_bytes);
- vh->len += length_increment;
- if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
- clib_mem_set_per_cpu_heap (oldheap);
- return v;
- }
- if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
- clib_mem_set_per_cpu_heap (oldheap);
- }
-
- /* 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), numa_id);
+ v = _vec_alloc_internal (n_elts, &va);
+ _vec_set_len (v, 0, elt_sz);
+ _vec_update_pointer (vp, v);
}
-/** \brief Determine if vector will resize with next allocation
+/** \brief Pre-allocate a vector (generic version)
- @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
+ @param V pointer to a vector
+ @param N number of elements to pre-allocate
+ @param H header size in bytes (may be zero)
+ @param A alignment (zero means default alignment of the data structure)
+ @param P heap (zero means default heap)
+ @return V (value-result macro parameter)
*/
-always_inline int
-_vec_resize_will_expand (void *v,
- word length_increment,
- uword data_bytes, uword header_bytes,
- uword data_align)
-{
- uword new_data_bytes, aligned_header_bytes;
+#define vec_prealloc_hap(V, N, H, A, P) \
+ _vec_prealloc ((void **) &(V), N, H, _vec_align (V, A), P, _vec_elt_sz (V))
- aligned_header_bytes = vec_header_bytes (header_bytes);
+/** \brief Pre-allocate a vector (simple version)
- new_data_bytes = data_bytes + aligned_header_bytes;
+ @param V pointer to a vector
+ @param N number of elements to pre-allocate
+ @return V (value-result macro parameter)
+*/
+#define vec_prealloc(V, N) vec_prealloc_hap (V, N, 0, 0, 0)
- if (PREDICT_TRUE (v != 0))
- {
- void *p = v - aligned_header_bytes;
+/** \brief Pre-allocate a vector (heap version)
- /* Vector header must start heap object. */
- ASSERT (clib_mem_is_heap_object (p));
+ @param V pointer to a vector
+ @param N number of elements to pre-allocate
+ @param P heap (zero means default heap)
+ @return V (value-result macro parameter)
+*/
+#define vec_prealloc_heap(V, N, P) vec_prealloc_hap (V, N, 0, 0, P)
- /* Typically we'll not need to resize. */
- if (new_data_bytes <= clib_mem_size (p))
- return 0;
- }
- return 1;
-}
+always_inline int
+_vec_resize_will_expand (void *v, uword n_elts, uword elt_sz)
+{
+ if (v == 0)
+ return 1;
-/** \brief Predicate function, says whether the supplied vector is a clib heap
- object (general version).
+ /* Vector header must start heap object. */
+ ASSERT (clib_mem_heap_is_heap_object (vec_get_heap (v), vec_header (v)));
- @param v pointer to a vector
- @param header_bytes vector header size in bytes (may be zero)
- @return 0 or 1
-*/
-uword clib_mem_is_vec_h (void *v, uword header_bytes);
+ n_elts += _vec_len (v);
+ if ((n_elts * elt_sz) <= vec_max_bytes (v))
+ return 0;
+ return 1;
+}
-/** \brief Predicate function, says whether the supplied vector is a clib heap
- object
+/** \brief Determine if vector will resize with next allocation
- @param v pointer to a vector
- @return 0 or 1
+ @param V pointer to a vector
+ @param N number of elements to add
+ @return 1 if vector will resize 0 otherwise
*/
-always_inline uword
-clib_mem_is_vec (void *v)
-{
- return clib_mem_is_vec_h (v, 0);
-}
+
+#define vec_resize_will_expand(V, N) \
+ _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
@param N number of elements to add
@param H header size in bytes (may be zero)
@param A alignment (may be zero)
- @param S numa_id (may be zero)
@return V (value-result macro parameter)
*/
-#define vec_resize_has(V,N,H,A,S) \
-do { \
- word _v(n) = (N); \
- word _v(l) = vec_len (V); \
- V = _vec_resize_numa ((V), _v(n), \
- (_v(l) + _v(n)) * sizeof ((V)[0]), \
- (H), (A),(S)); \
-} while (0)
+static_always_inline void
+_vec_resize (void **vp, uword n_add, uword hdr_sz, uword align, uword elt_sz)
+{
+ void *v = *vp;
+ if (PREDICT_FALSE (v == 0))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = hdr_sz };
+ *vp = _vec_alloc_internal (n_add, &va);
+ return;
+ }
-/** \brief Resize a vector (less general version).
- Add N elements to end of given vector V, return pointer to start of vector.
- Vector will have room for H header bytes and will have user's data aligned
- at alignment A (rounded to next power of 2).
+ if (PREDICT_FALSE (_vec_find (v)->grow_elts < n_add))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = hdr_sz };
+ v = _vec_resize_internal (v, _vec_len (v) + n_add, &va);
+ _vec_update_pointer (vp, v);
+ }
+ else
+ _vec_set_len (v, _vec_len (v) + n_add, elt_sz);
+}
- @param V pointer to a vector
- @param N number of elements to add
- @param H header size in bytes (may be zero)
- @param A alignment (may be zero)
- @return V (value-result macro parameter)
-*/
-#define vec_resize_ha(V,N,H,A) vec_resize_has(V,N,H,A,VEC_NUMA_UNSPECIFIED)
+#define vec_resize_ha(V, N, H, A) \
+ _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.
@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)
@param N number of elements to add
@param H header size in bytes (may be zero)
@param A alignment (may be zero)
+ @param P heap (may be zero)
@return V new vector
*/
-#define vec_new_ha(T,N,H,A) \
-({ \
- word _v(n) = (N); \
- _vec_resize ((T *) 0, _v(n), _v(n) * sizeof (T), (H), (A)); \
-})
+#define vec_new_generic(T, N, H, A, P) \
+ _vec_alloc_internal (N, &((vec_attr_t){ .align = _vec_align ((T *) 0, A), \
+ .hdr_sz = (H), \
+ .heap = (P), \
+ .elt_sz = sizeof (T) }))
/** \brief Create new vector of given type and length
(unspecified alignment, no header).
@param N number of elements to add
@return V new vector
*/
-#define vec_new(T,N) vec_new_ha(T,N,0,0)
+#define vec_new(T, N) vec_new_generic (T, N, 0, 0, 0)
/** \brief Create new vector of given type and length
(alignment specified, no header).
@param A alignment (may be zero)
@return V new vector
*/
-#define vec_new_aligned(T,N,A) vec_new_ha(T,N,0,A)
-
-/** \brief Free vector's memory (general version)
+#define vec_new_aligned(T, N, A) vec_new_generic (T, N, 0, A, 0)
+/** \brief Create new vector of given type and length
+ (heap specified, no header).
- @param V pointer to a vector
- @param H size of header in bytes
- @return V (value-result parameter, V=0)
+ @param T type of elements in new vector
+ @param N number of elements to add
+ @param P heap (may be zero)
+ @return V new vector
*/
-#define vec_free_h(V,H) \
-do { \
- if (V) \
- { \
- clib_mem_free (vec_header ((V), (H))); \
- V = 0; \
- } \
-} while (0)
+#define vec_new_heap(T, N, P) vec_new_generic (T, N, 0, 0, P)
/** \brief Free vector's memory (no header).
@param V pointer to a vector
@return V (value-result parameter, V=0)
*/
-#define vec_free(V) vec_free_h(V,0)
+
+static_always_inline void
+_vec_free (void **vp)
+{
+ if (vp[0] == 0)
+ return;
+ clib_mem_heap_free (vec_get_heap (vp[0]), vec_header (vp[0]));
+ vp[0] = 0;
+}
+
+#define vec_free(V) _vec_free ((void **) &(V))
+
+void vec_free_not_inline (void *v);
/**\brief Free vector user header (syntactic sugar)
@param h vector header
@param V pointer to a vector
@param H size of header in bytes
@param A alignment (may be zero)
- @param S numa (may be VEC_NUMA_UNSPECIFIED)
@return Vdup copy of vector
*/
-#define vec_dup_ha_numa(V,H,A,S) \
-({ \
- __typeof__ ((V)[0]) * _v(v) = 0; \
- uword _v(l) = vec_len (V); \
- if (_v(l) > 0) \
- { \
- vec_resize_has (_v(v), _v(l), (H), (A), (S)); \
- clib_memcpy_fast (_v(v), (V), _v(l) * sizeof ((V)[0]));\
- } \
- _v(v); \
-})
-
-/** \brief Return copy of vector (VEC_NUMA_UNSPECIFIED).
-
- @param V pointer to a vector
- @param H size of header in bytes
- @param A alignment (may be zero)
+static_always_inline void *
+_vec_dup (void *v, uword hdr_size, uword align, uword elt_sz)
+{
+ uword len = vec_len (v);
+ const vec_attr_t va = { .elt_sz = elt_sz, .align = align };
+ void *n = 0;
- @return Vdup copy of vector
-*/
-#define vec_dup_ha(V,H,A) \
- vec_dup_ha_numa(V,H,A,VEC_NUMA_UNSPECIFIED)
+ if (len)
+ {
+ n = _vec_alloc_internal (len, &va);
+ clib_memcpy_fast (n, v, len * elt_sz);
+ }
+ return n;
+}
+#define vec_dup_ha(V, H, A) \
+ _vec_dup ((void *) (V), H, _vec_align (V, A), _vec_elt_sz (V))
/** \brief Return copy of vector (no header, no alignment)
@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)
+{
+ const vec_attr_t va = { .elt_sz = elt_sz, .align = align };
+ v1p[0] = _vec_alloc_internal (vec_len (v2), &va);
+}
+#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).
@param I vector index which will be valid upon return
@param H header size in bytes (may be zero)
@param A alignment (may be zero)
- @param N numa_id (may be zero)
@return V (value-result macro parameter)
*/
-#define vec_validate_han(V,I,H,A,N) \
-do { \
- void *oldheap; \
- 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)) \
- { \
- /* switch to the per-numa heap if directed */ \
- if (PREDICT_FALSE(N != VEC_NUMA_UNSPECIFIED)) \
- { \
- oldheap = clib_mem_get_per_cpu_heap(); \
- clib_mem_set_per_cpu_heap (clib_mem_get_per_numa_heap(N)); \
- } \
- \
- 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])); \
- /* Switch back to the global heap */ \
- if (PREDICT_FALSE (N != VEC_NUMA_UNSPECIFIED)) \
- clib_mem_set_per_cpu_heap (oldheap); \
- } \
-} while (0)
+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 (void **vp, uword index, uword header_size, uword align,
+ void *heap, uword elt_sz)
+{
+ void *v = *vp;
+ uword vl, n_elts = index + 1;
-#define vec_validate_ha(V,I,H,A) vec_validate_han(V,I,H,A,VEC_NUMA_UNSPECIFIED)
+ if (PREDICT_FALSE (v == 0))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = header_size };
+ *vp = _vec_alloc_internal (n_elts, &va);
+ return;
+ }
+
+ vl = _vec_len (v);
+
+ if (PREDICT_FALSE (index < vl))
+ return;
+
+ if (PREDICT_FALSE (index >= _vec_find (v)->grow_elts + vl))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = header_size };
+ v = _vec_resize_internal (v, n_elts, &va);
+ _vec_update_pointer (vp, v);
+ }
+ else
+ _vec_set_len (v, n_elts, elt_sz);
+
+ _vec_zero_elts (v, vl, n_elts - vl, elt_sz);
+}
+
+#define vec_validate_hap(V, I, H, A, P) \
+ _vec_validate ((void **) &(V), I, H, _vec_align (V, A), 0, sizeof ((V)[0]))
/** \brief Make sure vector is long enough for given index
(no header, unspecified alignment)
@param I vector index which will be valid upon return
@return V (value-result macro parameter)
*/
-#define vec_validate(V,I) vec_validate_ha(V,I,0,0)
+#define vec_validate(V, I) vec_validate_hap (V, I, 0, 0, 0)
/** \brief Make sure vector is long enough for given index
(no header, specified alignment)
@return V (value-result macro parameter)
*/
-#define vec_validate_aligned(V,I,A) vec_validate_ha(V,I,0,A)
+#define vec_validate_aligned(V, I, A) vec_validate_hap (V, I, 0, A, 0)
+
+/** \brief Make sure vector is long enough for given index
+ (no header, specified heap)
+
+ @param V (possibly NULL) pointer to a vector.
+ @param I vector index which will be valid upon return
+ @param H heap (may be zero)
+ @return V (value-result macro parameter)
+*/
+
+#define vec_validate_heap(V, I, P) vec_validate_hap (V, I, 0, 0, P)
/** \brief Make sure vector is long enough for given index
and initialize empty space (general version)
@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)
@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;
+
+ if (PREDICT_FALSE (v == 0))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = hdr_sz };
+ return *vp = _vec_alloc_internal (1, &va);
+ }
+
+ len = _vec_len (v);
+
+ if (PREDICT_FALSE (_vec_find (v)->grow_elts == 0))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = hdr_sz };
+ v = _vec_resize_internal (v, len + 1, &va);
+ _vec_update_pointer (vp, v);
+ }
+ else
+ _vec_set_len (v, len + 1, elt_sz);
+
+ 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).
@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;
+ uword len;
+
+ if (PREDICT_FALSE (v == 0))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = hdr_sz };
+ *vp = *pp = _vec_alloc_internal (n_add, &va);
+ return;
+ }
+
+ len = _vec_len (v);
+ if (PREDICT_FALSE (_vec_find (v)->grow_elts < n_add))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = hdr_sz };
+ v = _vec_resize_internal (v, len + n_add, &va);
+ _vec_update_pointer (vp, v);
+ }
+ else
+ _vec_set_len (v, len + n_add, elt_sz);
+
+ *pp = 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)
@param A alignment (may be zero)
@return V (value-result macro parameter)
*/
-#define vec_add_ha(V,E,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)); \
- clib_memcpy_fast ((V) + _v(l), (E), _v(n) * sizeof ((V)[0])); \
-} while (0)
+static_always_inline void
+_vec_add (void **vp, void *e, word n_add, uword hdr_sz, uword align,
+ uword elt_sz)
+{
+ void *v = *vp;
+ uword len;
+
+ ASSERT (n_add >= 0);
+
+ if (n_add < 1)
+ return;
+
+ if (PREDICT_FALSE (v == 0))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = hdr_sz };
+ *vp = v = _vec_alloc_internal (n_add, &va);
+ clib_memcpy_fast (v, e, n_add * elt_sz);
+ return;
+ }
+
+ len = _vec_len (v);
+
+ if (PREDICT_FALSE (_vec_find (v)->grow_elts < n_add))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = hdr_sz };
+ v = _vec_resize_internal (v, len + n_add, &va);
+ _vec_update_pointer (vp, v);
+ }
+ else
+ _vec_set_len (v, len + n_add, elt_sz);
+
+ clib_memcpy_fast (v + len * elt_sz, e, n_add * elt_sz);
+}
+
+#define vec_add_ha(V, E, N, H, A) \
+ _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)
@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
@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);
+ const vec_attr_t va = { .elt_sz = elt_sz, .align = align, .hdr_sz = hdr_sz };
+
+ ASSERT (ins_pt <= len);
+
+ v = _vec_resize_internal (v, len + n_insert, &va);
+ clib_memmove (v + va.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)
@return V (value-result macro parameter)
*/
-#define vec_insert_elts_ha(V,E,N,M,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_memcpy_fast ((V) + _v(m), (E), \
- _v(n) * sizeof ((V)[0])); \
-} while (0)
+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);
+ const vec_attr_t va = { .elt_sz = elt_sz, .align = align, .hdr_sz = hdr_sz };
+
+ ASSERT (ins_pt <= len);
+
+ v = _vec_resize_internal (v, len + n_insert, &va);
+ 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) \
+ _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)
@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); \
- \
- 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))
+ {
+ const vec_attr_t va = { .elt_sz = v2_elt_sz, .align = align };
+ v1 = _vec_resize_internal (v1, len1 + len2, &va);
+ 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
@param align required alignment
*/
-#define vec_append_aligned(v1,v2,align) \
-do { \
- uword _v(l1) = vec_len (v1); \
- uword _v(l2) = vec_len (v2); \
- \
- 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)
+#define vec_append_aligned(v1, v2, align) \
+ _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
-*/
-
-#define vec_prepend(v1,v2) \
-do { \
- uword _v(l1) = vec_len (v1); \
- uword _v(l2) = vec_len (v2); \
- \
- 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)
+ @param V2 vector to append
+*/
+
+#define vec_append(v1, v2) vec_append_aligned (v1, v2, 0)
+
+static_always_inline void
+_vec_prepend (void *restrict *v1p, void *restrict v2, uword v1_elt_sz,
+ uword v2_elt_sz, uword align)
+{
+ void *restrict v1 = v1p[0];
+ uword len1 = vec_len (v1);
+ uword len2 = vec_len (v2);
+
+ if (PREDICT_TRUE (len2 > 0))
+ {
+ /* prepending vector to itself would result in use-after-free */
+ ASSERT (v1 != v2);
+ const vec_attr_t va = { .elt_sz = v2_elt_sz, .align = align };
+ v1 = _vec_resize_internal (v1, len1 + len2, &va);
+ clib_memmove (v1 + len2 * v2_elt_sz, v1, len1 * v1_elt_sz);
+ clib_memcpy_fast (v1, v2, len2 * v2_elt_sz);
+ _vec_update_pointer ((void **) v1p, v1);
+ }
+}
/** \brief Prepend v2 before v1. Result in v1. Specified alignment
@param V1 target vector
- @param V2 vector to prepend
+ @param V2 vector to prepend, V1 != V2
@param align required alignment
*/
-#define vec_prepend_aligned(v1,v2,align) \
-do { \
- uword _v(l1) = vec_len (v1); \
- uword _v(l2) = vec_len (v2); \
- \
- 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)
+#define vec_prepend_aligned(v1, v2, align) \
+ _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, V1 != V2
+*/
+
+#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
@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.
/** \brief Sort a vector using the supplied element comparison function
+ Does not depend on the underlying implementation to deal correctly
+ with null, zero-long, or 1-long vectors
+
@param vec vector to sort
@param f comparison function
*/
-#define vec_sort_with_function(vec,f) \
-do { \
- qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f)); \
+#define vec_sort_with_function(vec,f) \
+do { \
+ if (vec_len (vec) > 1) \
+ qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f)); \
} while (0)
/** \brief Make a vector containing a NULL terminated c-string.
@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.
@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:
- */
Code Review / vpp.git / blobdiff