2 * Copyright (c) 2015 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
16 Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
18 Permission is hereby granted, free of charge, to any person obtaining
19 a copy of this software and associated documentation files (the
20 "Software"), to deal in the Software without restriction, including
21 without limitation the rights to use, copy, modify, merge, publish,
22 distribute, sublicense, and/or sell copies of the Software, and to
23 permit persons to whom the Software is furnished to do so, subject to
24 the following conditions:
26 The above copyright notice and this permission notice shall be
27 included in all copies or substantial portions of the Software.
29 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33 LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34 OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
38 #ifndef included_vec_h
39 #define included_vec_h
41 #include <vppinfra/clib.h> /* word, etc */
42 #include <vppinfra/mem.h> /* clib_mem_free */
43 #include <vppinfra/string.h> /* memcpy, memmove */
44 #include <vppinfra/vec_bootstrap.h>
48 CLIB vectors are ubiquitous dynamically resized arrays with by user
49 defined "headers". Many CLIB data structures (e.g. hash, heap,
50 pool) are vectors with various different headers.
52 The memory layout looks like this:
55 user header (start of memory allocation)
57 heap pointer (optional, only if default_heap == 0)
58 vector header: number of elements, header size
59 user's pointer-> vector element #0
64 The user pointer contains the address of vector element # 0. Null
65 pointer vectors are valid and mean a zero length vector.
67 You can reset the length of an allocated vector to zero via the
68 vec_reset_length(v) macro, or by setting the vector length field to
69 zero (e.g. _vec_len (v) = 0). Vec_reset_length(v) preferred: it
70 understands Null pointers.
72 Typically, the header is not present. Headers allow for other
73 data structures to be built atop CLIB vectors.
75 While users may specify the alignment for first data element of a vector
76 via the vec_*_aligned macros that is typically not needed as alignment
77 is set based on native alignment of the data structure used.
79 Vector elements can be any C type e.g. (int, double, struct bar).
80 This is also true for data types built atop vectors (e.g. heap,
83 Many macros have \_a variants supporting alignment of vector elements
84 and \_h variants supporting non-zero-length vector headers. The \_ha
85 variants support both. Additionally cacheline alignment within a
86 vector element structure can be specified using the
87 CLIB_CACHE_LINE_ALIGN_MARK() macro.
89 Standard programming error: memorize a pointer to the ith element
90 of a vector then expand it. Vectors expand by 3/2, so such code
91 may appear to work for a period of time. Memorize vector indices
95 /** \brief Low-level (re)allocation function, usually not called directly
97 @param v pointer to a vector
98 @param n_elts requested number of elements
99 @param elt_sz requested size of one element
100 @param hdr_sz header size in bytes (may be zero)
101 @param align alignment (may be zero)
102 @return v_prime pointer to resized vector, may or may not equal v
113 void *_vec_alloc_internal (uword n_elts, const vec_attr_t *const attr);
114 void *_vec_realloc_internal (void *v, uword n_elts,
115 const vec_attr_t *const attr);
116 void *_vec_resize_internal (void *v, uword n_elts,
117 const vec_attr_t *const attr);
119 /* calculate minimum alignment out of data natural alignment and provided
120 * value, should not be < VEC_MIN_ALIGN */
121 static_always_inline uword
122 __vec_align (uword data_align, uword configuered_align)
124 data_align = clib_max (data_align, configuered_align);
125 ASSERT (count_set_bits (data_align) == 1);
126 return clib_max (VEC_MIN_ALIGN, data_align);
129 /* function used t o catch cases where vec_* macros on used on void * */
130 static_always_inline uword
131 __vec_elt_sz (uword elt_sz, int is_void)
133 /* vector macro operations on void * are not allowed */
134 ASSERT (is_void == 0);
138 static_always_inline void
139 _vec_update_pointer (void **vp, void *v)
141 /* avoid store if not needed */
146 static_always_inline void *
147 vec_get_heap (void *v)
149 if (v == 0 || _vec_find (v)->default_heap == 1)
151 return _vec_heap (v);
154 static_always_inline uword
155 vec_get_align (void *v)
157 return 1ULL << _vec_find (v)->log2_align;
160 static_always_inline void
161 _vec_prealloc (void **vp, uword n_elts, uword hdr_sz, uword align, void *heap,
164 const vec_attr_t va = {
165 .elt_sz = elt_sz, .hdr_sz = hdr_sz, .align = align, .heap = heap
171 v = _vec_alloc_internal (n_elts, &va);
172 _vec_set_len (v, 0, elt_sz);
173 _vec_update_pointer (vp, v);
176 /** \brief Pre-allocate a vector (generic version)
178 @param V pointer to a vector
179 @param N number of elements to pre-allocate
180 @param H header size in bytes (may be zero)
181 @param A alignment (zero means default alignment of the data structure)
182 @param P heap (zero means default heap)
183 @return V (value-result macro parameter)
186 #define vec_prealloc_hap(V, N, H, A, P) \
187 _vec_prealloc ((void **) &(V), N, H, _vec_align (V, A), P, _vec_elt_sz (V))
189 /** \brief Pre-allocate a vector (simple version)
191 @param V pointer to a vector
192 @param N number of elements to pre-allocate
193 @return V (value-result macro parameter)
195 #define vec_prealloc(V, N) vec_prealloc_hap (V, N, 0, 0, 0)
197 /** \brief Pre-allocate a vector (heap version)
199 @param V pointer to a vector
200 @param N number of elements to pre-allocate
201 @param P heap (zero means default heap)
202 @return V (value-result macro parameter)
204 #define vec_prealloc_heap(V, N, P) vec_prealloc_hap (V, N, 0, 0, P)
207 _vec_resize_will_expand (void *v, uword n_elts, uword elt_sz)
212 /* Vector header must start heap object. */
213 ASSERT (clib_mem_heap_is_heap_object (vec_get_heap (v), vec_header (v)));
215 n_elts += _vec_len (v);
216 if ((n_elts * elt_sz) <= vec_max_bytes (v))
222 /** \brief Determine if vector will resize with next allocation
224 @param V pointer to a vector
225 @param N number of elements to add
226 @return 1 if vector will resize 0 otherwise
229 #define vec_resize_will_expand(V, N) \
230 _vec_resize_will_expand (V, N, _vec_elt_sz (V))
232 /* Local variable naming macro (prevents collisions with other macro naming). */
233 #define _v(var) _vec_##var
235 /** \brief Resize a vector (general version).
236 Add N elements to end of given vector V, return pointer to start of vector.
237 Vector will have room for H header bytes and will have user's data aligned
238 at alignment A (rounded to next power of 2).
240 @param V pointer to a vector
241 @param N number of elements to add
242 @param H header size in bytes (may be zero)
243 @param A alignment (may be zero)
244 @return V (value-result macro parameter)
247 static_always_inline void
248 _vec_resize (void **vp, uword n_add, uword hdr_sz, uword align, uword elt_sz)
251 if (PREDICT_FALSE (v == 0))
253 const vec_attr_t va = { .elt_sz = elt_sz,
256 *vp = _vec_alloc_internal (n_add, &va);
260 if (PREDICT_FALSE (_vec_find (v)->grow_elts < n_add))
262 const vec_attr_t va = { .elt_sz = elt_sz,
265 v = _vec_resize_internal (v, _vec_len (v) + n_add, &va);
266 _vec_update_pointer (vp, v);
269 _vec_set_len (v, _vec_len (v) + n_add, elt_sz);
272 #define vec_resize_ha(V, N, H, A) \
273 _vec_resize ((void **) &(V), N, H, _vec_align (V, A), _vec_elt_sz (V))
275 /** \brief Resize a vector (no header, unspecified alignment)
276 Add N elements to end of given vector V, return pointer to start of vector.
277 Vector will have room for H header bytes and will have user's data aligned
278 at alignment A (rounded to next power of 2).
280 @param V pointer to a vector
281 @param N number of elements to add
282 @return V (value-result macro parameter)
284 #define vec_resize(V,N) vec_resize_ha(V,N,0,0)
286 /** \brief Resize a vector (no header, alignment specified).
287 Add N elements to end of given vector V, return pointer to start of vector.
288 Vector will have room for H header bytes and will have user's data aligned
289 at alignment A (rounded to next power of 2).
291 @param V pointer to a vector
292 @param N number of elements to add
293 @param A alignment (may be zero)
294 @return V (value-result macro parameter)
297 #define vec_resize_aligned(V,N,A) vec_resize_ha(V,N,0,A)
299 /** \brief Allocate space for N more elements
301 @param V pointer to a vector
302 @param N number of elements to add
303 @param H header size in bytes (may be zero)
304 @param A alignment (may be zero)
305 @return V (value-result macro parameter)
308 #define vec_alloc_ha(V, N, H, A) \
311 uword _v (l) = vec_len (V); \
312 vec_resize_ha (V, N, H, A); \
313 vec_set_len (V, _v (l)); \
317 /** \brief Allocate space for N more elements
318 (no header, unspecified alignment)
320 @param V pointer to a vector
321 @param N number of elements to add
322 @return V (value-result macro parameter)
324 #define vec_alloc(V,N) vec_alloc_ha(V,N,0,0)
326 /** \brief Allocate space for N more elements (no header, given alignment)
327 @param V pointer to a vector
328 @param N number of elements to add
329 @param A alignment (may be zero)
330 @return V (value-result macro parameter)
333 #define vec_alloc_aligned(V,N,A) vec_alloc_ha(V,N,0,A)
335 /** \brief Create new vector of given type and length (general version).
336 @param T type of elements in new vector
337 @param N number of elements to add
338 @param H header size in bytes (may be zero)
339 @param A alignment (may be zero)
340 @param P heap (may be zero)
343 #define vec_new_generic(T, N, H, A, P) \
344 _vec_alloc_internal (N, &((vec_attr_t){ .align = _vec_align ((T *) 0, A), \
347 .elt_sz = sizeof (T) }))
349 /** \brief Create new vector of given type and length
350 (unspecified alignment, no header).
352 @param T type of elements in new vector
353 @param N number of elements to add
356 #define vec_new(T, N) vec_new_generic (T, N, 0, 0, 0)
357 /** \brief Create new vector of given type and length
358 (alignment specified, no header).
360 @param T type of elements in new vector
361 @param N number of elements to add
362 @param A alignment (may be zero)
365 #define vec_new_aligned(T, N, A) vec_new_generic (T, N, 0, A, 0)
366 /** \brief Create new vector of given type and length
367 (heap specified, no header).
369 @param T type of elements in new vector
370 @param N number of elements to add
371 @param P heap (may be zero)
374 #define vec_new_heap(T, N, P) vec_new_generic (T, N, 0, 0, P)
376 /** \brief Free vector's memory (no header).
377 @param V pointer to a vector
378 @return V (value-result parameter, V=0)
381 static_always_inline void
382 _vec_free (void **vp)
386 clib_mem_heap_free (vec_get_heap (vp[0]), vec_header (vp[0]));
390 #define vec_free(V) _vec_free ((void **) &(V))
392 void vec_free_not_inline (void *v);
394 /**\brief Free vector user header (syntactic sugar)
395 @param h vector header
398 #define vec_free_header(h) clib_mem_free (h)
400 /** \brief Return copy of vector (general version).
402 @param V pointer to a vector
403 @param H size of header in bytes
404 @param A alignment (may be zero)
406 @return Vdup copy of vector
409 static_always_inline void *
410 _vec_dup (void *v, uword hdr_size, uword align, uword elt_sz)
412 uword len = vec_len (v);
413 const vec_attr_t va = { .elt_sz = elt_sz, .align = align };
418 n = _vec_alloc_internal (len, &va);
419 clib_memcpy_fast (n, v, len * elt_sz);
424 #define vec_dup_ha(V, H, A) \
425 _vec_dup ((void *) (V), H, _vec_align (V, A), _vec_elt_sz (V))
427 /** \brief Return copy of vector (no header, no alignment)
429 @param V pointer to a vector
430 @return Vdup copy of vector
432 #define vec_dup(V) vec_dup_ha(V,0,0)
434 /** \brief Return copy of vector (no header, alignment specified).
436 @param V pointer to a vector
437 @param A alignment (may be zero)
439 @return Vdup copy of vector
441 #define vec_dup_aligned(V,A) vec_dup_ha(V,0,A)
443 /** \brief Copy a vector, memcpy wrapper. Assumes sizeof(SRC[0]) ==
446 @param DST destination
449 #define vec_copy(DST,SRC) clib_memcpy_fast (DST, SRC, vec_len (DST) * \
452 /** \brief Clone a vector. Make a new vector with the
453 same size as a given vector but possibly with a different type.
455 @param NEW_V pointer to new vector
456 @param OLD_V pointer to old vector
459 static_always_inline void
460 _vec_clone (void **v1p, void *v2, uword align, uword elt_sz)
462 const vec_attr_t va = { .elt_sz = elt_sz, .align = align };
463 v1p[0] = _vec_alloc_internal (vec_len (v2), &va);
465 #define vec_clone(NEW_V, OLD_V) \
466 _vec_clone ((void **) &(NEW_V), OLD_V, _vec_align (NEW_V, 0), \
469 /** \brief Make sure vector is long enough for given index (general version).
471 @param V (possibly NULL) pointer to a vector.
472 @param I vector index which will be valid upon return
473 @param H header size in bytes (may be zero)
474 @param A alignment (may be zero)
475 @return V (value-result macro parameter)
479 _vec_zero_elts (void *v, uword first, uword count, uword elt_sz)
481 clib_memset_u8 (v + (first * elt_sz), 0, count * elt_sz);
483 #define vec_zero_elts(V, F, C) _vec_zero_elts (V, F, C, sizeof ((V)[0]))
485 static_always_inline void
486 _vec_validate (void **vp, uword index, uword header_size, uword align,
487 void *heap, uword elt_sz)
490 uword vl, n_elts = index + 1;
492 if (PREDICT_FALSE (v == 0))
494 const vec_attr_t va = { .elt_sz = elt_sz,
496 .hdr_sz = header_size };
497 *vp = _vec_alloc_internal (n_elts, &va);
503 if (PREDICT_FALSE (index < vl))
506 if (PREDICT_FALSE (index >= _vec_find (v)->grow_elts + vl))
508 const vec_attr_t va = { .elt_sz = elt_sz,
510 .hdr_sz = header_size };
511 v = _vec_resize_internal (v, n_elts, &va);
512 _vec_update_pointer (vp, v);
515 _vec_set_len (v, n_elts, elt_sz);
517 _vec_zero_elts (v, vl, n_elts - vl, elt_sz);
520 #define vec_validate_hap(V, I, H, A, P) \
521 _vec_validate ((void **) &(V), I, H, _vec_align (V, A), 0, sizeof ((V)[0]))
523 /** \brief Make sure vector is long enough for given index
524 (no header, unspecified alignment)
526 @param V (possibly NULL) pointer to a vector.
527 @param I vector index which will be valid upon return
528 @return V (value-result macro parameter)
530 #define vec_validate(V, I) vec_validate_hap (V, I, 0, 0, 0)
532 /** \brief Make sure vector is long enough for given index
533 (no header, specified alignment)
535 @param V (possibly NULL) pointer to a vector.
536 @param I vector index which will be valid upon return
537 @param A alignment (may be zero)
538 @return V (value-result macro parameter)
541 #define vec_validate_aligned(V, I, A) vec_validate_hap (V, I, 0, A, 0)
543 /** \brief Make sure vector is long enough for given index
544 (no header, specified heap)
546 @param V (possibly NULL) pointer to a vector.
547 @param I vector index which will be valid upon return
548 @param H heap (may be zero)
549 @return V (value-result macro parameter)
552 #define vec_validate_heap(V, I, P) vec_validate_hap (V, I, 0, 0, P)
554 /** \brief Make sure vector is long enough for given index
555 and initialize empty space (general version)
557 @param V (possibly NULL) pointer to a vector.
558 @param I vector index which will be valid upon return
559 @param INIT initial value (can be a complex expression!)
560 @param H header size in bytes (may be zero)
561 @param A alignment (may be zero)
562 @return V (value-result macro parameter)
564 #define vec_validate_init_empty_ha(V, I, INIT, H, A) \
568 word _v (l) = vec_len (V); \
569 if (_v (i) >= _v (l)) \
571 vec_resize_ha (V, 1 + (_v (i) - _v (l)), H, A); \
572 while (_v (l) <= _v (i)) \
574 (V)[_v (l)] = (INIT); \
581 /** \brief Make sure vector is long enough for given index
582 and initialize empty space (no header, unspecified alignment)
584 @param V (possibly NULL) pointer to a vector.
585 @param I vector index which will be valid upon return
586 @param INIT initial value (can be a complex expression!)
587 @return V (value-result macro parameter)
590 #define vec_validate_init_empty(V,I,INIT) \
591 vec_validate_init_empty_ha(V,I,INIT,0,0)
593 /** \brief Make sure vector is long enough for given index
594 and initialize empty space (no header, alignment alignment)
596 @param V (possibly NULL) pointer to a vector.
597 @param I vector index which will be valid upon return
598 @param INIT initial value (can be a complex expression!)
599 @param A alignment (may be zero)
600 @return V (value-result macro parameter)
602 #define vec_validate_init_empty_aligned(V,I,INIT,A) \
603 vec_validate_init_empty_ha(V,I,INIT,0,A)
605 /** \brief Add 1 element to end of vector (general version).
607 @param V pointer to a vector
608 @param E element to add
609 @param H header size in bytes (may be zero)
610 @param A alignment (may be zero)
611 @return V (value-result macro parameter)
614 static_always_inline void *
615 _vec_add1 (void **vp, uword hdr_sz, uword align, uword elt_sz)
620 if (PREDICT_FALSE (v == 0))
622 const vec_attr_t va = { .elt_sz = elt_sz,
625 return *vp = _vec_alloc_internal (1, &va);
630 if (PREDICT_FALSE (_vec_find (v)->grow_elts == 0))
632 const vec_attr_t va = { .elt_sz = elt_sz,
635 v = _vec_resize_internal (v, len + 1, &va);
636 _vec_update_pointer (vp, v);
639 _vec_set_len (v, len + 1, elt_sz);
641 return v + len * elt_sz;
644 #define vec_add1_ha(V, E, H, A) \
645 ((__typeof__ ((V)[0]) *) _vec_add1 ((void **) &(V), H, _vec_align (V, A), \
646 _vec_elt_sz (V)))[0] = (E)
648 /** \brief Add 1 element to end of vector (unspecified alignment).
650 @param V pointer to a vector
651 @param E element to add
652 @return V (value-result macro parameter)
654 #define vec_add1(V,E) vec_add1_ha(V,E,0,0)
656 /** \brief Add 1 element to end of vector (alignment specified).
658 @param V pointer to a vector
659 @param E element to add
660 @param A alignment (may be zero)
661 @return V (value-result macro parameter)
663 #define vec_add1_aligned(V,E,A) vec_add1_ha(V,E,0,A)
665 /** \brief Add N elements to end of vector V,
666 return pointer to new elements in P. (general version)
668 @param V pointer to a vector
669 @param P pointer to new vector element(s)
670 @param N number of elements to add
671 @param H header size in bytes (may be zero)
672 @param A alignment (may be zero)
673 @return V and P (value-result macro parameters)
676 static_always_inline void
677 _vec_add2 (void **vp, void **pp, uword n_add, uword hdr_sz, uword align,
683 if (PREDICT_FALSE (v == 0))
685 const vec_attr_t va = { .elt_sz = elt_sz,
688 *vp = *pp = _vec_alloc_internal (n_add, &va);
693 if (PREDICT_FALSE (_vec_find (v)->grow_elts < n_add))
695 const vec_attr_t va = { .elt_sz = elt_sz,
698 v = _vec_resize_internal (v, len + n_add, &va);
699 _vec_update_pointer (vp, v);
702 _vec_set_len (v, len + n_add, elt_sz);
704 *pp = v + len * elt_sz;
707 #define vec_add2_ha(V, P, N, H, A) \
708 _vec_add2 ((void **) &(V), (void **) &(P), N, H, _vec_align (V, A), \
711 /** \brief Add N elements to end of vector V,
712 return pointer to new elements in P. (no header, unspecified alignment)
714 @param V pointer to a vector
715 @param P pointer to new vector element(s)
716 @param N number of elements to add
717 @return V and P (value-result macro parameters)
720 #define vec_add2(V,P,N) vec_add2_ha(V,P,N,0,0)
722 /** \brief Add N elements to end of vector V,
723 return pointer to new elements in P. (no header, alignment specified)
725 @param V pointer to a vector
726 @param P pointer to new vector element(s)
727 @param N number of elements to add
728 @param A alignment (may be zero)
729 @return V and P (value-result macro parameters)
732 #define vec_add2_aligned(V,P,N,A) vec_add2_ha(V,P,N,0,A)
734 /** \brief Add N elements to end of vector V (general version)
736 @param V pointer to a vector
737 @param E pointer to element(s) to add
738 @param N number of elements to add
739 @param H header size in bytes (may be zero)
740 @param A alignment (may be zero)
741 @return V (value-result macro parameter)
743 static_always_inline void
744 _vec_add (void **vp, void *e, word n_add, uword hdr_sz, uword align,
755 if (PREDICT_FALSE (v == 0))
757 const vec_attr_t va = { .elt_sz = elt_sz,
760 *vp = v = _vec_alloc_internal (n_add, &va);
761 clib_memcpy_fast (v, e, n_add * elt_sz);
767 if (PREDICT_FALSE (_vec_find (v)->grow_elts < n_add))
769 const vec_attr_t va = { .elt_sz = elt_sz,
772 v = _vec_resize_internal (v, len + n_add, &va);
773 _vec_update_pointer (vp, v);
776 _vec_set_len (v, len + n_add, elt_sz);
778 clib_memcpy_fast (v + len * elt_sz, e, n_add * elt_sz);
781 #define vec_add_ha(V, E, N, H, A) \
782 _vec_add ((void **) &(V), (void *) (E), N, H, _vec_align (V, A), \
785 /** \brief Add N elements to end of vector V (no header, unspecified alignment)
787 @param V pointer to a vector
788 @param E pointer to element(s) to add
789 @param N number of elements to add
790 @return V (value-result macro parameter)
792 #define vec_add(V,E,N) vec_add_ha(V,E,N,0,0)
794 /** \brief Add N elements to end of vector V (no header, specified alignment)
796 @param V pointer to a vector
797 @param E pointer to element(s) to add
798 @param N number of elements to add
799 @param A alignment (may be zero)
800 @return V (value-result macro parameter)
802 #define vec_add_aligned(V,E,N,A) vec_add_ha(V,E,N,0,A)
804 /** \brief Returns last element of a vector and decrements its length
806 @param V pointer to a vector
807 @return E element removed from the end of the vector
811 uword _v (l) = vec_len (V); \
812 __typeof__ ((V)[0]) _v (rv); \
813 ASSERT (_v (l) > 0); \
815 _v (rv) = (V)[_v (l)]; \
816 vec_set_len (V, _v (l)); \
820 /** \brief Set E to the last element of a vector, decrement vector length
821 @param V pointer to a vector
822 @param E pointer to the last vector element
823 @return E element removed from the end of the vector
824 (value-result macro parameter
827 #define vec_pop2(V,E) \
829 uword _v(l) = vec_len (V); \
830 if (_v(l) > 0) (E) = vec_pop (V); \
834 /** \brief Insert N vector elements starting at element M,
835 initialize new elements (general version).
837 @param V (possibly NULL) pointer to a vector.
838 @param N number of elements to insert
839 @param M insertion point
840 @param INIT initial value (can be a complex expression!)
841 @param H header size in bytes (may be zero)
842 @param A alignment (may be zero)
843 @return V (value-result macro parameter)
846 static_always_inline void
847 _vec_insert (void **vp, uword n_insert, uword ins_pt, u8 init, uword hdr_sz,
848 uword align, uword elt_sz)
851 uword len = vec_len (v);
852 const vec_attr_t va = { .elt_sz = elt_sz, .align = align, .hdr_sz = hdr_sz };
854 ASSERT (ins_pt <= len);
856 v = _vec_resize_internal (v, len + n_insert, &va);
857 clib_memmove (v + va.elt_sz * (ins_pt + n_insert), v + ins_pt * elt_sz,
858 (len - ins_pt) * elt_sz);
859 _vec_zero_elts (v, ins_pt, n_insert, elt_sz);
860 _vec_update_pointer (vp, v);
863 #define vec_insert_init_empty_ha(V, N, M, INIT, H, A) \
864 _vec_insert ((void **) &(V), N, M, INIT, H, _vec_align (V, A), \
867 /** \brief Insert N vector elements starting at element M,
868 initialize new elements to zero (general version)
870 @param V (possibly NULL) pointer to a vector.
871 @param N number of elements to insert
872 @param M insertion point
873 @param H header size in bytes (may be zero)
874 @param A alignment (may be zero)
875 @return V (value-result macro parameter)
877 #define vec_insert_ha(V,N,M,H,A) vec_insert_init_empty_ha(V,N,M,0,H,A)
879 /** \brief Insert N vector elements starting at element M,
880 initialize new elements to zero (no header, unspecified alignment)
882 @param V (possibly NULL) pointer to a vector.
883 @param N number of elements to insert
884 @param M insertion point
885 @return V (value-result macro parameter)
887 #define vec_insert(V,N,M) vec_insert_ha(V,N,M,0,0)
889 /** \brief Insert N vector elements starting at element M,
890 initialize new elements to zero (no header, alignment specified)
892 @param V (possibly NULL) pointer to a vector.
893 @param N number of elements to insert
894 @param M insertion point
895 @param A alignment (may be zero)
896 @return V (value-result macro parameter)
898 #define vec_insert_aligned(V,N,M,A) vec_insert_ha(V,N,M,0,A)
900 /** \brief Insert N vector elements starting at element M,
901 initialize new elements (no header, unspecified alignment)
903 @param V (possibly NULL) pointer to a vector.
904 @param N number of elements to insert
905 @param M insertion point
906 @param INIT initial value (can be a complex expression!)
907 @return V (value-result macro parameter)
910 #define vec_insert_init_empty(V,N,M,INIT) \
911 vec_insert_init_empty_ha(V,N,M,INIT,0,0)
912 /* Resize vector by N elements starting from element M, initialize new elements to INIT (alignment specified, no header). */
914 /** \brief Insert N vector elements starting at element M,
915 initialize new elements (no header, specified alignment)
917 @param V (possibly NULL) pointer to a vector.
918 @param N number of elements to insert
919 @param M insertion point
920 @param INIT initial value (can be a complex expression!)
921 @param A alignment (may be zero)
922 @return V (value-result macro parameter)
924 #define vec_insert_init_empty_aligned(V,N,M,INIT,A) \
925 vec_insert_init_empty_ha(V,N,M,INIT,0,A)
927 /** \brief Insert N vector elements starting at element M,
928 insert given elements (general version)
930 @param V (possibly NULL) pointer to a vector.
931 @param E element(s) to insert
932 @param N number of elements to insert
933 @param M insertion point
934 @param H header size in bytes (may be zero)
935 @param A alignment (may be zero)
936 @return V (value-result macro parameter)
939 static_always_inline void
940 _vec_insert_elts (void **vp, void *e, uword n_insert, uword ins_pt,
941 uword hdr_sz, uword align, uword elt_sz)
944 uword len = vec_len (v);
945 const vec_attr_t va = { .elt_sz = elt_sz, .align = align, .hdr_sz = hdr_sz };
947 ASSERT (ins_pt <= len);
949 v = _vec_resize_internal (v, len + n_insert, &va);
950 clib_memmove (v + elt_sz * (ins_pt + n_insert), v + ins_pt * elt_sz,
951 (len - ins_pt) * elt_sz);
952 _vec_zero_elts (v, ins_pt, n_insert, elt_sz);
953 clib_memcpy_fast (v + ins_pt * elt_sz, e, n_insert * elt_sz);
954 _vec_update_pointer (vp, v);
957 #define vec_insert_elts_ha(V, E, N, M, H, A) \
958 _vec_insert_elts ((void **) &(V), E, N, M, H, _vec_align (V, A), \
961 /** \brief Insert N vector elements starting at element M,
962 insert given elements (no header, unspecified alignment)
964 @param V (possibly NULL) pointer to a vector.
965 @param E element(s) to insert
966 @param N number of elements to insert
967 @param M insertion point
968 @return V (value-result macro parameter)
970 #define vec_insert_elts(V,E,N,M) vec_insert_elts_ha(V,E,N,M,0,0)
972 /** \brief Insert N vector elements starting at element M,
973 insert given elements (no header, specified alignment)
975 @param V (possibly NULL) pointer to a vector.
976 @param E element(s) to insert
977 @param N number of elements to insert
978 @param M insertion point
979 @param A alignment (may be zero)
980 @return V (value-result macro parameter)
982 #define vec_insert_elts_aligned(V,E,N,M,A) vec_insert_elts_ha(V,E,N,M,0,A)
984 /** \brief Delete N elements starting at element M
986 @param V pointer to a vector
987 @param N number of elements to delete
988 @param M first element to delete
989 @return V (value-result macro parameter)
992 static_always_inline void
993 _vec_delete (void *v, uword n_del, uword first, uword elt_sz)
995 word n_bytes_del, n_bytes_to_move, len = vec_len (v);
1001 ASSERT (first + n_del <= len);
1003 n_bytes_del = n_del * elt_sz;
1004 n_bytes_to_move = (len - first - n_del) * elt_sz;
1005 dst = v + first * elt_sz;
1007 if (n_bytes_to_move > 0)
1008 clib_memmove (dst, dst + n_bytes_del, n_bytes_to_move);
1009 clib_memset (dst + n_bytes_to_move, 0, n_bytes_del);
1011 _vec_set_len (v, _vec_len (v) - n_del, elt_sz);
1014 #define vec_delete(V, N, M) _vec_delete ((void *) (V), N, M, _vec_elt_sz (V))
1016 /** \brief Delete the element at index I
1018 @param V pointer to a vector
1019 @param I index to delete
1022 static_always_inline void
1023 _vec_del1 (void *v, uword index, uword elt_sz)
1025 uword len = _vec_len (v) - 1;
1028 clib_memcpy_fast (v + index * elt_sz, v + len * elt_sz, elt_sz);
1030 _vec_set_len (v, len, elt_sz);
1033 #define vec_del1(v, i) _vec_del1 ((void *) (v), i, _vec_elt_sz (v))
1035 static_always_inline void
1036 _vec_append (void **v1p, void *v2, uword v1_elt_sz, uword v2_elt_sz,
1040 uword len1 = vec_len (v1);
1041 uword len2 = vec_len (v2);
1043 if (PREDICT_TRUE (len2 > 0))
1045 const vec_attr_t va = { .elt_sz = v2_elt_sz, .align = align };
1046 v1 = _vec_resize_internal (v1, len1 + len2, &va);
1047 clib_memcpy_fast (v1 + len1 * v1_elt_sz, v2, len2 * v2_elt_sz);
1048 _vec_update_pointer (v1p, v1);
1052 /** \brief Append v2 after v1. Result in v1. Specified alignment.
1053 @param V1 target vector
1054 @param V2 vector to append
1055 @param align required alignment
1058 #define vec_append_aligned(v1, v2, align) \
1059 _vec_append ((void **) &(v1), (void *) (v2), _vec_elt_sz (v1), \
1060 _vec_elt_sz (v2), _vec_align (v1, align))
1062 /** \brief Append v2 after v1. Result in v1.
1063 @param V1 target vector
1064 @param V2 vector to append
1067 #define vec_append(v1, v2) vec_append_aligned (v1, v2, 0)
1069 static_always_inline void
1070 _vec_prepend (void **v1p, void *v2, uword v1_elt_sz, uword v2_elt_sz,
1074 uword len1 = vec_len (v1);
1075 uword len2 = vec_len (v2);
1077 if (PREDICT_TRUE (len2 > 0))
1079 const vec_attr_t va = { .elt_sz = v2_elt_sz, .align = align };
1080 v1 = _vec_resize_internal (v1, len1 + len2, &va);
1081 clib_memmove (v1 + len2 * v2_elt_sz, v1p[0], len1 * v1_elt_sz);
1082 clib_memcpy_fast (v1, v2, len2 * v2_elt_sz);
1083 _vec_update_pointer (v1p, v1);
1087 /** \brief Prepend v2 before v1. Result in v1. Specified alignment
1088 @param V1 target vector
1089 @param V2 vector to prepend
1090 @param align required alignment
1093 #define vec_prepend_aligned(v1, v2, align) \
1094 _vec_prepend ((void **) &(v1), (void *) (v2), _vec_elt_sz (v1), \
1095 _vec_elt_sz (v2), _vec_align (v1, align))
1097 /** \brief Prepend v2 before v1. Result in v1.
1098 @param V1 target vector
1099 @param V2 vector to prepend
1102 #define vec_prepend(v1, v2) vec_prepend_aligned (v1, v2, 0)
1104 /** \brief Zero all vector elements. Null-pointer tolerant.
1105 @param var Vector to zero
1107 static_always_inline void
1108 _vec_zero (void *v, uword elt_sz)
1110 uword len = vec_len (v);
1113 clib_memset_u8 (v, 0, len * elt_sz);
1116 #define vec_zero(var) _vec_zero ((void *) (var), _vec_elt_sz (var))
1118 /** \brief Set all vector elements to given value. Null-pointer tolerant.
1119 @param v vector to set
1120 @param val value for each vector element
1122 #define vec_set(v,val) \
1125 __typeof__ ((v)[0]) _val = (val); \
1126 for (_v(i) = 0; _v(i) < vec_len (v); _v(i)++) \
1127 (v)[_v(i)] = _val; \
1131 #include <stdlib.h> /* for qsort */
1134 /** \brief Compare two vectors, not NULL-pointer tolerant
1136 @param v1 Pointer to a vector
1137 @param v2 Pointer to a vector
1138 @return 1 if equal, 0 if unequal
1140 static_always_inline int
1141 _vec_is_equal (void *v1, void *v2, uword v1_elt_sz, uword v2_elt_sz)
1143 uword vec_len_v1 = vec_len (v1);
1145 if ((vec_len_v1 != vec_len (v2)) || (v1_elt_sz != v2_elt_sz))
1148 if ((vec_len_v1 == 0) || (memcmp (v1, v2, vec_len_v1 * v1_elt_sz) == 0))
1154 #define vec_is_equal(v1, v2) \
1155 _vec_is_equal ((void *) (v1), (void *) (v2), _vec_elt_sz (v1), \
1158 /** \brief Compare two vectors (only applicable to vectors of signed numbers).
1159 Used in qsort compare functions.
1161 @param v1 Pointer to a vector
1162 @param v2 Pointer to a vector
1165 #define vec_cmp(v1,v2) \
1167 word _v(i), _v(cmp), _v(l); \
1168 _v(l) = clib_min (vec_len (v1), vec_len (v2)); \
1170 for (_v(i) = 0; _v(i) < _v(l); _v(i)++) { \
1171 _v(cmp) = (v1)[_v(i)] - (v2)[_v(i)]; \
1175 if (_v(cmp) == 0 && _v(l) > 0) \
1176 _v(cmp) = vec_len(v1) - vec_len(v2); \
1177 (_v(cmp) < 0 ? -1 : (_v(cmp) > 0 ? +1 : 0)); \
1180 /** \brief Search a vector for the index of the entry that matches.
1182 @param v Pointer to a vector
1183 @param E Entry to match
1184 @return index of match or ~0
1186 #define vec_search(v,E) \
1189 while (_v(i) < vec_len(v)) \
1191 if ((v)[_v(i)] == E) \
1195 if (_v(i) == vec_len(v)) \
1200 /** \brief Search a vector for the index of the entry that matches.
1202 @param v Pointer to a vector
1203 @param E Pointer to entry to match
1204 @param fn Comparison function !0 => match
1205 @return index of match or ~0
1207 #define vec_search_with_function(v,E,fn) \
1210 while (_v(i) < vec_len(v)) \
1212 if (0 != fn(&(v)[_v(i)], (E))) \
1216 if (_v(i) == vec_len(v)) \
1221 /** \brief Sort a vector using the supplied element comparison function
1223 Does not depend on the underlying implementation to deal correctly
1224 with null, zero-long, or 1-long vectors
1226 @param vec vector to sort
1227 @param f comparison function
1229 #define vec_sort_with_function(vec,f) \
1231 if (vec_len (vec) > 1) \
1232 qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f)); \
1235 /** \brief Make a vector containing a NULL terminated c-string.
1237 @param V (possibly NULL) pointer to a vector.
1238 @param S pointer to string buffer.
1239 @param L string length (NOT including the terminating NULL; a la strlen())
1241 #define vec_validate_init_c_string(V, S, L) \
1244 vec_reset_length (V); \
1245 vec_validate (V, (L)); \
1247 clib_memcpy_fast (V, (S), (L)); \
1252 /** \brief Test whether a vector is a NULL terminated c-string.
1254 @param V (possibly NULL) pointer to a vector.
1255 @return BOOLEAN indicating if the vector c-string is null terminated.
1257 #define vec_c_string_is_terminated(V) \
1258 (((V) != 0) && (vec_len (V) != 0) && ((V)[vec_len ((V)) - 1] == 0))
1260 /** \brief (If necessary) NULL terminate a vector containing a c-string.
1262 @param V (possibly NULL) pointer to a vector.
1263 @return V (value-result macro parameter)
1265 #define vec_terminate_c_string(V) \
1268 if (!vec_c_string_is_terminated (V)) \
1273 #endif /* included_vec_h */