Typically, the header is not present. Headers allow for other
data structures to be built atop CLIB vectors.
- Users may specify the alignment for data elements via the
- vec_*_aligned macros.
+ Users may specify the alignment for first data element of a vector
+ via the vec_*_aligned macros.
- Vectors elements can be any C type e.g. (int, double, struct bar).
+ 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,
pool, etc.).
- Many macros have _a variants supporting alignment of vector data
- and _h variants supporting non zero length vector headers.
- The _ha variants support both.
+ Many macros have \_a variants supporting alignment of vector elements
+ and \_h variants supporting non-zero-length vector headers. The \_ha
+ variants support both. Additionally cacheline alignment within a
+ vector element structure can be specified using the
+ CLIB_CACHE_LINE_ALIGN_MARK() macro.
Standard programming error: memorize a pointer to the ith element
of a vector then expand it. Vectors expand by 3/2, so such code
@param data_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_resize_allocate_memory (void *v, word length_increment,
+ uword data_bytes, uword header_bytes,
+ uword data_align);
/** \brief Low-level vector resize function, usually not called directly
@return v_prime pointer to resized vector, may or may not equal v
*/
-#define _vec_resize(V,L,DB,HB,A) \
- _vec_resize_inline(V,L,DB,HB,clib_max((__alignof__((V)[0])),(A)))
+#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; \
+ })
always_inline void *
-_vec_resize_inline (void *v,
- word length_increment,
- uword data_bytes, uword header_bytes, uword data_align)
+_vec_resize_inline (void *v, word length_increment, uword data_bytes,
+ uword header_bytes, uword data_align)
{
vec_header_t *vh = _vec_find (v);
uword new_data_bytes, aligned_header_bytes;
/* 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;
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_resize_allocate_memory (
+ v, length_increment, data_bytes, header_bytes,
+ clib_max (sizeof (vec_header_t), data_align));
}
/** \brief Determine if vector will resize with next allocation
*/
always_inline int
-_vec_resize_will_expand (void *v,
- word length_increment,
- uword data_bytes, uword header_bytes,
- uword data_align)
+_vec_resize_will_expand (void *v, uword n_elts, uword elt_size)
{
- 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 (vec_mem_size (v) >= ((_vec_len (v) + n_elts)) * elt_size)
return 0;
}
return 1;
}
-/** \brief Predicate function, says whether the supplied vector is a clib heap
- object (general version).
+/** \brief Determine if vector will resize with next allocation
- @param v pointer to a vector
- @param header_bytes vector header size in bytes (may be zero)
- @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
*/
-uword clib_mem_is_vec_h (void *v, uword header_bytes);
-
-/** \brief Predicate function, says whether the supplied vector is a clib heap
- object
-
- @param v pointer to a vector
- @return 0 or 1
-*/
-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, sizeof ((V)[0]))
/* Local variable naming macro (prevents collisions with other macro naming). */
#define _v(var) _vec_##var
@return V (value-result macro parameter)
*/
-#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)
+#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)
/** \brief Resize a vector (no header, unspecified alignment)
Add N elements to end of given vector V, return pointer to start of vector.
@param A alignment (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_ha(T,N,H,A) \
+({ \
+ word _v(n) = (N); \
+ (T *)_vec_resize ((T *) 0, _v(n), _v(n) * sizeof (T), (H), (A)); \
})
/** \brief Create new vector of given type and length
*/
#define vec_new_aligned(T,N,A) vec_new_ha(T,N,0,A)
-/** \brief Free vector's memory (general version)
-
- @param V pointer to a vector
- @param H size of header in bytes
- @return V (value-result parameter, V=0)
-*/
-#define vec_free_h(V,H) \
-do { \
- if (V) \
- { \
- clib_mem_free (vec_header ((V), (H))); \
- V = 0; \
- } \
-} while (0)
-
/** \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)
+#define vec_free(V) \
+ do \
+ { \
+ if (V) \
+ { \
+ clib_mem_free (vec_header ((V))); \
+ V = 0; \
+ } \
+ } \
+ while (0)
+
+void vec_free_not_inline (void *v);
/**\brief Free vector user header (syntactic sugar)
@param h vector header
@return Vdup copy of vector
*/
-#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 (_v(v), (V), _v(l) * sizeof ((V)[0]));\
- } \
- _v(v); \
-})
+#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); \
+ })
/** \brief Return copy of vector (no header, no alignment)
@param DST destination
@param SRC source
*/
-#define vec_copy(DST,SRC) clib_memcpy (DST, SRC, vec_len (DST) * \
+#define vec_copy(DST,SRC) clib_memcpy_fast (DST, SRC, vec_len (DST) * \
sizeof ((DST)[0]))
/** \brief Clone a vector. Make a new vector with the
@return V (value-result macro parameter)
*/
-#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 */ \
- memset ((V) + _v(l), 0, (1 + (_v(i) - _v(l))) * sizeof ((V)[0])); \
- } \
-} while (0)
+#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)
/** \brief Make sure vector is long enough for given index
(no header, unspecified alignment)
@param V (possibly NULL) pointer to a vector.
@param I vector index which will be valid upon return
@param INIT initial value (can be a complex expression!)
- @param H header size in bytes (may be zero)
- @param A alignment (may be zero)
@return V (value-result macro parameter)
*/
@param V (possibly NULL) pointer to a vector.
@param I vector index which will be valid upon return
@param INIT initial value (can be a complex expression!)
- @param H header size in bytes (may be zero)
@param A alignment (may be zero)
@return V (value-result macro parameter)
*/
@param V pointer to a vector
@param E element to add
- @param H header size in bytes (may be zero)
@param A alignment (may be zero)
@return V (value-result macro parameter)
*/
@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 ((V) + _v(l), (E), _v(n) * sizeof ((V)[0])); \
-} while (0)
+#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)
/** \brief Add N elements to end of vector V (no header, unspecified alignment)
memmove ((V) + _v(m) + _v(n), \
(V) + _v(m), \
(_v(l) - _v(m)) * sizeof ((V)[0])); \
- memset ((V) + _v(m), INIT, _v(n) * sizeof ((V)[0])); \
+ clib_memset ((V) + _v(m), INIT, _v(n) * sizeof ((V)[0])); \
} while (0)
/** \brief Insert N vector elements starting at element M,
@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 ((V) + _v(m), (E), \
- _v(n) * sizeof ((V)[0])); \
-} while (0)
+#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)
/** \brief Insert N vector elements starting at element M,
insert given elements (no header, unspecified alignment)
(_v(l) - _v(n) - _v(m)) * sizeof ((V)[0])); \
/* Zero empty space at end (for future re-allocation). */ \
if (_v(n) > 0) \
- memset ((V) + _v(l) - _v(n), 0, _v(n) * sizeof ((V)[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)
/** \brief Delete the element at index 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 V2 vector to append
*/
-#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 ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0])); \
-} while (0)
+#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)
/** \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 ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0])); \
-} while (0)
+#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)
/** \brief Prepend v2 before 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 ((v1), (v2), _v(l2) * sizeof ((v2)[0])); \
-} while (0)
+#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)
/** \brief Prepend v2 before v1. Result in v1. Specified alignment
@param V1 target vector
@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 ((v1), (v2), _v(l2) * sizeof ((v2)[0])); \
-} while (0)
-
+#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)
/** \brief Zero all vector elements. Null-pointer tolerant.
@param var Vector to zero
#define vec_zero(var) \
do { \
if (var) \
- memset ((var), 0, vec_len (var) * sizeof ((var)[0])); \
+ clib_memset ((var), 0, vec_len (var) * sizeof ((var)[0])); \
} while (0)
/** \brief Set all vector elements to given value. Null-pointer tolerant.
/** \brief Search a vector for the index of the entry that matches.
- @param v1 Pointer to a vector
- @param v2 Entry to match
+ @param v Pointer to a vector
+ @param E Entry to match
@return index of match or ~0
*/
#define vec_search(v,E) \
_v(i); \
})
+/** \brief Search a vector for the index of the entry that matches.
+
+ @param v Pointer to a vector
+ @param E Pointer to entry to match
+ @param fn Comparison function !0 => match
+ @return index of match or ~0
+*/
+#define vec_search_with_function(v,E,fn) \
+({ \
+ word _v(i) = 0; \
+ while (_v(i) < vec_len(v)) \
+ { \
+ if (0 != fn(&(v)[_v(i)], (E))) \
+ break; \
+ _v(i)++; \
+ } \
+ if (_v(i) == vec_len(v)) \
+ _v(i) = ~0; \
+ _v(i); \
+})
+
/** \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.
vec_reset_length (V); \
vec_validate ((V), (L)); \
if ((S) && (L)) \
- clib_memcpy ((V), (S), (L)); \
+ clib_memcpy_fast ((V), (S), (L)); \
(V)[(L)] = 0; \
} while (0)