X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=src%2Fvppinfra%2Fvec.h;h=6f0e7e9148be54cc3ed964ba74ed7e5e91499615;hb=f34597f;hp=eed96d6b9c2608aac25f97e77293e8a866148769;hpb=7cd468a3d7dee7d6c92f69a0bb7061ae208ec727;p=vpp.git diff --git a/src/vppinfra/vec.h b/src/vppinfra/vec.h index eed96d6b9c2..6f0e7e9148b 100644 --- a/src/vppinfra/vec.h +++ b/src/vppinfra/vec.h @@ -70,16 +70,18 @@ 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 @@ -111,10 +113,13 @@ void *vec_resize_allocate_memory (void *v, @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))) + always_inline void * -_vec_resize (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; @@ -145,6 +150,42 @@ _vec_resize (void *v, data_align)); } +/** \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, + word length_increment, + uword data_bytes, uword header_bytes, + uword data_align) +{ + 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)); + + /* Typically we'll not need to resize. */ + if (new_data_bytes <= clib_mem_size (p)) + return 0; + } + return 1; +} + /** \brief Predicate function, says whether the supplied vector is a clib heap object (general version). @@ -321,7 +362,7 @@ do { \ if (_v(l) > 0) \ { \ vec_resize_ha (_v(v), _v(l), (H), (A)); \ - clib_memcpy (_v(v), (V), _v(l) * sizeof ((V)[0]));\ + clib_memcpy_fast (_v(v), (V), _v(l) * sizeof ((V)[0]));\ } \ _v(v); \ }) @@ -348,7 +389,7 @@ do { \ @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 @@ -375,6 +416,8 @@ do { \ #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)) \ @@ -382,7 +425,7 @@ do { \ 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])); \ + clib_memset ((V) + _v(l), 0, (1 + (_v(i) - _v(l))) * sizeof ((V)[0])); \ } \ } while (0) @@ -455,7 +498,7 @@ do { \ @param A alignment (may be zero) @return V (value-result macro parameter) */ -#define vec_validate_init_empty_aligned(V,I,A) \ +#define vec_validate_init_empty_aligned(V,I,INIT,A) \ vec_validate_init_empty_ha(V,I,INIT,0,A) /** \brief Add 1 element to end of vector (general version). @@ -546,7 +589,7 @@ 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])); \ + 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) @@ -620,7 +663,7 @@ do { \ 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, @@ -708,7 +751,7 @@ do { \ memmove ((V) + _v(m) + _v(n), \ (V) + _v(m), \ (_v(l) - _v(m)) * sizeof ((V)[0])); \ - clib_memcpy ((V) + _v(m), (E), \ + clib_memcpy_fast ((V) + _v(m), (E), \ _v(n) * sizeof ((V)[0])); \ } while (0) @@ -753,7 +796,7 @@ do { \ (_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); \ } while (0) @@ -783,7 +826,7 @@ do { \ \ 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])); \ + clib_memcpy_fast ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0])); \ } while (0) /** \brief Append v2 after v1. Result in v1. Specified alignment. @@ -799,7 +842,7 @@ do { \ \ 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])); \ + clib_memcpy_fast ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0])); \ } while (0) /** \brief Prepend v2 before v1. Result in v1. @@ -815,7 +858,7 @@ do { \ 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])); \ + clib_memcpy_fast ((v1), (v2), _v(l2) * sizeof ((v2)[0])); \ } while (0) /** \brief Prepend v2 before v1. Result in v1. Specified alignment @@ -832,7 +875,7 @@ do { \ 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])); \ + clib_memcpy_fast ((v1), (v2), _v(l2) * sizeof ((v2)[0])); \ } while (0) @@ -842,7 +885,7 @@ do { \ #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. @@ -903,7 +946,28 @@ do { \ word _v(i) = 0; \ while (_v(i) < vec_len(v)) \ { \ - if (v[_v(i)] == E) \ + if ((v)[_v(i)] == E) \ + break; \ + _v(i)++; \ + } \ + if (_v(i) == vec_len(v)) \ + _v(i) = ~0; \ + _v(i); \ +}) + +/** \brief Search a vector for the index of the entry that matches. + + @param v1 Pointer to a vector + @param v2 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)++; \ } \ @@ -933,7 +997,7 @@ do { \ 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)