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 (aligned to uword boundary)
56 vector length: number of elements
57 user's pointer-> vector element #0
62 The user pointer contains the address of vector element # 0. Null
63 pointer vectors are valid and mean a zero length vector.
65 You can reset the length of an allocated vector to zero via the
66 vec_reset_length(v) macro, or by setting the vector length field to
67 zero (e.g. _vec_len (v) = 0). Vec_reset_length(v) preferred: it
68 understands Null pointers.
70 Typically, the header is not present. Headers allow for other
71 data structures to be built atop CLIB vectors.
73 Users may specify the alignment for first data element of a vector
74 via the vec_*_aligned macros.
76 Vector elements can be any C type e.g. (int, double, struct bar).
77 This is also true for data types built atop vectors (e.g. heap,
80 Many macros have \_a variants supporting alignment of vector elements
81 and \_h variants supporting non-zero-length vector headers. The \_ha
82 variants support both. Additionally cacheline alignment within a
83 vector element structure can be specified using the
84 CLIB_CACHE_LINE_ALIGN_MARK() macro.
86 Standard programming error: memorize a pointer to the ith element
87 of a vector then expand it. Vectors expand by 3/2, so such code
88 may appear to work for a period of time. Memorize vector indices
92 /** \brief Low-level resize allocation function, usually not called directly
94 @param v pointer to a vector
95 @param length_increment length increment in elements
96 @param data_bytes requested size in bytes
97 @param header_bytes header size in bytes (may be zero)
98 @param data_align alignment (may be zero)
99 @param numa_id numa id (may be zero)
100 @return v_prime pointer to resized vector, may or may not equal v
102 void *vec_resize_allocate_memory (void *v,
103 word length_increment,
105 uword header_bytes, uword data_align,
108 /** \brief Low-level vector resize function, usually not called directly
110 @param v pointer to a vector
111 @param length_increment length increment in elements
112 @param data_bytes requested size in bytes
113 @param header_bytes header size in bytes (may be zero)
114 @param data_align alignment (may be zero)
115 @param numa_id (may be ~0)
116 @return v_prime pointer to resized vector, may or may not equal v
119 #define _vec_resize_numa(V,L,DB,HB,A,S) \
120 _vec_resize_inline(V,L,DB,HB,clib_max((__alignof__((V)[0])),(A)),(S))
122 #define _vec_resize(V,L,DB,HB,A) \
123 _vec_resize_numa(V,L,DB,HB,A,VEC_NUMA_UNSPECIFIED)
126 _vec_resize_inline (void *v,
127 word length_increment,
128 uword data_bytes, uword header_bytes, uword data_align,
131 vec_header_t *vh = _vec_find (v);
132 uword new_data_bytes, aligned_header_bytes;
135 aligned_header_bytes = vec_header_bytes (header_bytes);
137 new_data_bytes = data_bytes + aligned_header_bytes;
139 if (PREDICT_TRUE (v != 0))
141 void *p = v - aligned_header_bytes;
143 if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
145 oldheap = clib_mem_get_per_cpu_heap ();
146 clib_mem_set_per_cpu_heap (clib_mem_get_per_numa_heap (numa_id));
149 /* Vector header must start heap object. */
150 ASSERT (clib_mem_is_heap_object (p));
152 /* Typically we'll not need to resize. */
153 if (new_data_bytes <= clib_mem_size (p))
155 CLIB_MEM_UNPOISON (v, data_bytes);
156 vh->len += length_increment;
157 if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
158 clib_mem_set_per_cpu_heap (oldheap);
161 if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
162 clib_mem_set_per_cpu_heap (oldheap);
165 /* Slow path: call helper function. */
166 return vec_resize_allocate_memory (v, length_increment, data_bytes,
168 clib_max (sizeof (vec_header_t),
169 data_align), numa_id);
172 /** \brief Determine if vector will resize with next allocation
174 @param v pointer to a vector
175 @param length_increment length increment in elements
176 @param data_bytes requested size in bytes
177 @param header_bytes header size in bytes (may be zero)
178 @param data_align alignment (may be zero)
179 @return 1 if vector will resize 0 otherwise
183 _vec_resize_will_expand (void *v,
184 word length_increment,
185 uword data_bytes, uword header_bytes,
188 uword new_data_bytes, aligned_header_bytes;
190 aligned_header_bytes = vec_header_bytes (header_bytes);
192 new_data_bytes = data_bytes + aligned_header_bytes;
194 if (PREDICT_TRUE (v != 0))
196 void *p = v - aligned_header_bytes;
198 /* Vector header must start heap object. */
199 ASSERT (clib_mem_is_heap_object (p));
201 /* Typically we'll not need to resize. */
202 if (new_data_bytes <= clib_mem_size (p))
208 /** \brief Predicate function, says whether the supplied vector is a clib heap
209 object (general version).
211 @param v pointer to a vector
212 @param header_bytes vector header size in bytes (may be zero)
215 uword clib_mem_is_vec_h (void *v, uword header_bytes);
218 /** \brief Predicate function, says whether the supplied vector is a clib heap
221 @param v pointer to a vector
225 clib_mem_is_vec (void *v)
227 return clib_mem_is_vec_h (v, 0);
230 /* Local variable naming macro (prevents collisions with other macro naming). */
231 #define _v(var) _vec_##var
233 /** \brief Resize a vector (general version).
234 Add N elements to end of given vector V, return pointer to start of vector.
235 Vector will have room for H header bytes and will have user's data aligned
236 at alignment A (rounded to next power of 2).
238 @param V pointer to a vector
239 @param N number of elements to add
240 @param H header size in bytes (may be zero)
241 @param A alignment (may be zero)
242 @param S numa_id (may be zero)
243 @return V (value-result macro parameter)
246 #define vec_resize_has(V,N,H,A,S) \
249 word _v(l) = vec_len (V); \
250 V = _vec_resize_numa ((V), _v(n), \
251 (_v(l) + _v(n)) * sizeof ((V)[0]), \
255 /** \brief Resize a vector (less general version).
256 Add N elements to end of given vector V, return pointer to start of vector.
257 Vector will have room for H header bytes and will have user's data aligned
258 at alignment A (rounded to next power of 2).
260 @param V pointer to a vector
261 @param N number of elements to add
262 @param H header size in bytes (may be zero)
263 @param A alignment (may be zero)
264 @return V (value-result macro parameter)
266 #define vec_resize_ha(V,N,H,A) vec_resize_has(V,N,H,A,VEC_NUMA_UNSPECIFIED)
268 /** \brief Resize a vector (no header, unspecified alignment)
269 Add N elements to end of given vector V, return pointer to start of vector.
270 Vector will have room for H header bytes and will have user's data aligned
271 at alignment A (rounded to next power of 2).
273 @param V pointer to a vector
274 @param N number of elements to add
275 @return V (value-result macro parameter)
277 #define vec_resize(V,N) vec_resize_ha(V,N,0,0)
279 /** \brief Resize a vector (no header, alignment specified).
280 Add N elements to end of given vector V, return pointer to start of vector.
281 Vector will have room for H header bytes and will have user's data aligned
282 at alignment A (rounded to next power of 2).
284 @param V pointer to a vector
285 @param N number of elements to add
286 @param A alignment (may be zero)
287 @return V (value-result macro parameter)
290 #define vec_resize_aligned(V,N,A) vec_resize_ha(V,N,0,A)
292 /** \brief Allocate space for N more elements
294 @param V pointer to a vector
295 @param N number of elements to add
296 @param H header size in bytes (may be zero)
297 @param A alignment (may be zero)
298 @return V (value-result macro parameter)
301 #define vec_alloc_ha(V,N,H,A) \
303 uword _v(l) = vec_len (V); \
304 vec_resize_ha (V, N, H, A); \
305 _vec_len (V) = _v(l); \
308 /** \brief Allocate space for N more elements
309 (no header, unspecified alignment)
311 @param V pointer to a vector
312 @param N number of elements to add
313 @return V (value-result macro parameter)
315 #define vec_alloc(V,N) vec_alloc_ha(V,N,0,0)
317 /** \brief Allocate space for N more elements (no header, given alignment)
318 @param V pointer to a vector
319 @param N number of elements to add
320 @param A alignment (may be zero)
321 @return V (value-result macro parameter)
324 #define vec_alloc_aligned(V,N,A) vec_alloc_ha(V,N,0,A)
326 /** \brief Create new vector of given type and length (general version).
327 @param T type of elements in new vector
328 @param N number of elements to add
329 @param H header size in bytes (may be zero)
330 @param A alignment (may be zero)
333 #define vec_new_ha(T,N,H,A) \
336 _vec_resize ((T *) 0, _v(n), _v(n) * sizeof (T), (H), (A)); \
339 /** \brief Create new vector of given type and length
340 (unspecified alignment, no header).
342 @param T type of elements in new vector
343 @param N number of elements to add
346 #define vec_new(T,N) vec_new_ha(T,N,0,0)
347 /** \brief Create new vector of given type and length
348 (alignment specified, no header).
350 @param T type of elements in new vector
351 @param N number of elements to add
352 @param A alignment (may be zero)
355 #define vec_new_aligned(T,N,A) vec_new_ha(T,N,0,A)
357 /** \brief Free vector's memory (general version)
359 @param V pointer to a vector
360 @param H size of header in bytes
361 @return V (value-result parameter, V=0)
363 #define vec_free_h(V,H) \
367 clib_mem_free (vec_header ((V), (H))); \
372 /** \brief Free vector's memory (no header).
373 @param V pointer to a vector
374 @return V (value-result parameter, V=0)
376 #define vec_free(V) vec_free_h(V,0)
378 /**\brief Free vector user header (syntactic sugar)
379 @param h vector header
382 #define vec_free_header(h) clib_mem_free (h)
384 /** \brief Return copy of vector (general version).
386 @param V pointer to a vector
387 @param H size of header in bytes
388 @param A alignment (may be zero)
389 @param S numa (may be VEC_NUMA_UNSPECIFIED)
391 @return Vdup copy of vector
394 #define vec_dup_ha_numa(V,H,A,S) \
396 __typeof__ ((V)[0]) * _v(v) = 0; \
397 uword _v(l) = vec_len (V); \
400 vec_resize_has (_v(v), _v(l), (H), (A), (S)); \
401 clib_memcpy_fast (_v(v), (V), _v(l) * sizeof ((V)[0]));\
406 /** \brief Return copy of vector (VEC_NUMA_UNSPECIFIED).
408 @param V pointer to a vector
409 @param H size of header in bytes
410 @param A alignment (may be zero)
412 @return Vdup copy of vector
414 #define vec_dup_ha(V,H,A) \
415 vec_dup_ha_numa(V,H,A,VEC_NUMA_UNSPECIFIED)
418 /** \brief Return copy of vector (no header, no alignment)
420 @param V pointer to a vector
421 @return Vdup copy of vector
423 #define vec_dup(V) vec_dup_ha(V,0,0)
425 /** \brief Return copy of vector (no header, alignment specified).
427 @param V pointer to a vector
428 @param A alignment (may be zero)
430 @return Vdup copy of vector
432 #define vec_dup_aligned(V,A) vec_dup_ha(V,0,A)
434 /** \brief Copy a vector, memcpy wrapper. Assumes sizeof(SRC[0]) ==
437 @param DST destination
440 #define vec_copy(DST,SRC) clib_memcpy_fast (DST, SRC, vec_len (DST) * \
443 /** \brief Clone a vector. Make a new vector with the
444 same size as a given vector but possibly with a different type.
446 @param NEW_V pointer to new vector
447 @param OLD_V pointer to old vector
449 #define vec_clone(NEW_V,OLD_V) \
452 (NEW_V) = _vec_resize ((NEW_V), vec_len (OLD_V), \
453 vec_len (OLD_V) * sizeof ((NEW_V)[0]), (0), (0)); \
456 /** \brief Make sure vector is long enough for given index (general version).
458 @param V (possibly NULL) pointer to a vector.
459 @param I vector index which will be valid upon return
460 @param H header size in bytes (may be zero)
461 @param A alignment (may be zero)
462 @param N numa_id (may be zero)
463 @return V (value-result macro parameter)
466 #define vec_validate_han(V,I,H,A,N) \
469 STATIC_ASSERT(A==0 || ((A % sizeof(V[0]))==0) \
470 || ((sizeof(V[0]) % A) == 0), \
471 "vector validate aligned on incorrectly sized object"); \
473 word _v(l) = vec_len (V); \
474 if (_v(i) >= _v(l)) \
476 /* switch to the per-numa heap if directed */ \
477 if (PREDICT_FALSE(N != VEC_NUMA_UNSPECIFIED)) \
479 oldheap = clib_mem_get_per_cpu_heap(); \
480 clib_mem_set_per_cpu_heap (clib_mem_get_per_numa_heap(N)); \
483 vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A)); \
484 /* Must zero new space since user may have previously \
485 used e.g. _vec_len (v) -= 10 */ \
486 clib_memset ((V) + _v(l), 0, \
487 (1 + (_v(i) - _v(l))) * sizeof ((V)[0])); \
488 /* Switch back to the global heap */ \
489 if (PREDICT_FALSE (N != VEC_NUMA_UNSPECIFIED)) \
490 clib_mem_set_per_cpu_heap (oldheap); \
494 #define vec_validate_ha(V,I,H,A) vec_validate_han(V,I,H,A,VEC_NUMA_UNSPECIFIED)
496 /** \brief Make sure vector is long enough for given index
497 (no header, unspecified alignment)
499 @param V (possibly NULL) pointer to a vector.
500 @param I vector index which will be valid upon return
501 @return V (value-result macro parameter)
503 #define vec_validate(V,I) vec_validate_ha(V,I,0,0)
505 /** \brief Make sure vector is long enough for given index
506 (no header, specified alignment)
508 @param V (possibly NULL) pointer to a vector.
509 @param I vector index which will be valid upon return
510 @param A alignment (may be zero)
511 @return V (value-result macro parameter)
514 #define vec_validate_aligned(V,I,A) vec_validate_ha(V,I,0,A)
516 /** \brief Make sure vector is long enough for given index
517 and initialize empty space (general version)
519 @param V (possibly NULL) pointer to a vector.
520 @param I vector index which will be valid upon return
521 @param INIT initial value (can be a complex expression!)
522 @param H header size in bytes (may be zero)
523 @param A alignment (may be zero)
524 @return V (value-result macro parameter)
526 #define vec_validate_init_empty_ha(V,I,INIT,H,A) \
529 word _v(l) = vec_len (V); \
530 if (_v(i) >= _v(l)) \
532 vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A)); \
533 while (_v(l) <= _v(i)) \
535 (V)[_v(l)] = (INIT); \
541 /** \brief Make sure vector is long enough for given index
542 and initialize empty space (no header, unspecified alignment)
544 @param V (possibly NULL) pointer to a vector.
545 @param I vector index which will be valid upon return
546 @param INIT initial value (can be a complex expression!)
547 @return V (value-result macro parameter)
550 #define vec_validate_init_empty(V,I,INIT) \
551 vec_validate_init_empty_ha(V,I,INIT,0,0)
553 /** \brief Make sure vector is long enough for given index
554 and initialize empty space (no header, alignment alignment)
556 @param V (possibly NULL) pointer to a vector.
557 @param I vector index which will be valid upon return
558 @param INIT initial value (can be a complex expression!)
559 @param A alignment (may be zero)
560 @return V (value-result macro parameter)
562 #define vec_validate_init_empty_aligned(V,I,INIT,A) \
563 vec_validate_init_empty_ha(V,I,INIT,0,A)
565 /** \brief Add 1 element to end of vector (general version).
567 @param V pointer to a vector
568 @param E element to add
569 @param H header size in bytes (may be zero)
570 @param A alignment (may be zero)
571 @return V (value-result macro parameter)
573 #define vec_add1_ha(V,E,H,A) \
575 word _v(l) = vec_len (V); \
576 V = _vec_resize ((V), 1, (_v(l) + 1) * sizeof ((V)[0]), (H), (A)); \
580 /** \brief Add 1 element to end of vector (unspecified alignment).
582 @param V pointer to a vector
583 @param E element to add
584 @return V (value-result macro parameter)
586 #define vec_add1(V,E) vec_add1_ha(V,E,0,0)
588 /** \brief Add 1 element to end of vector (alignment specified).
590 @param V pointer to a vector
591 @param E element to add
592 @param A alignment (may be zero)
593 @return V (value-result macro parameter)
595 #define vec_add1_aligned(V,E,A) vec_add1_ha(V,E,0,A)
597 /** \brief Add N elements to end of vector V,
598 return pointer to new elements in P. (general version)
600 @param V pointer to a vector
601 @param P pointer to new vector element(s)
602 @param N number of elements to add
603 @param H header size in bytes (may be zero)
604 @param A alignment (may be zero)
605 @return V and P (value-result macro parameters)
607 #define vec_add2_ha(V,P,N,H,A) \
610 word _v(l) = vec_len (V); \
611 V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A)); \
615 /** \brief Add N elements to end of vector V,
616 return pointer to new elements in P. (no header, unspecified alignment)
618 @param V pointer to a vector
619 @param P pointer to new vector element(s)
620 @param N number of elements to add
621 @return V and P (value-result macro parameters)
624 #define vec_add2(V,P,N) vec_add2_ha(V,P,N,0,0)
626 /** \brief Add N elements to end of vector V,
627 return pointer to new elements in P. (no header, alignment specified)
629 @param V pointer to a vector
630 @param P pointer to new vector element(s)
631 @param N number of elements to add
632 @param A alignment (may be zero)
633 @return V and P (value-result macro parameters)
636 #define vec_add2_aligned(V,P,N,A) vec_add2_ha(V,P,N,0,A)
638 /** \brief Add N elements to end of vector V (general version)
640 @param V pointer to a vector
641 @param E pointer to element(s) to add
642 @param N number of elements to add
643 @param H header size in bytes (may be zero)
644 @param A alignment (may be zero)
645 @return V (value-result macro parameter)
647 #define vec_add_ha(V,E,N,H,A) \
650 word _v(l) = vec_len (V); \
651 V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A)); \
652 clib_memcpy_fast ((V) + _v(l), (E), _v(n) * sizeof ((V)[0])); \
655 /** \brief Add N elements to end of vector V (no header, unspecified alignment)
657 @param V pointer to a vector
658 @param E pointer to element(s) to add
659 @param N number of elements to add
660 @return V (value-result macro parameter)
662 #define vec_add(V,E,N) vec_add_ha(V,E,N,0,0)
664 /** \brief Add N elements to end of vector V (no header, specified alignment)
666 @param V pointer to a vector
667 @param E pointer to element(s) to add
668 @param N number of elements to add
669 @param A alignment (may be zero)
670 @return V (value-result macro parameter)
672 #define vec_add_aligned(V,E,N,A) vec_add_ha(V,E,N,0,A)
674 /** \brief Returns last element of a vector and decrements its length
676 @param V pointer to a vector
677 @return E element removed from the end of the vector
681 uword _v(l) = vec_len (V); \
682 ASSERT (_v(l) > 0); \
684 _vec_len (V) = _v (l); \
688 /** \brief Set E to the last element of a vector, decrement vector length
689 @param V pointer to a vector
690 @param E pointer to the last vector element
691 @return E element removed from the end of the vector
692 (value-result macro parameter
695 #define vec_pop2(V,E) \
697 uword _v(l) = vec_len (V); \
698 if (_v(l) > 0) (E) = vec_pop (V); \
702 /** \brief Insert N vector elements starting at element M,
703 initialize new elements (general version).
705 @param V (possibly NULL) pointer to a vector.
706 @param N number of elements to insert
707 @param M insertion point
708 @param INIT initial value (can be a complex expression!)
709 @param H header size in bytes (may be zero)
710 @param A alignment (may be zero)
711 @return V (value-result macro parameter)
713 #define vec_insert_init_empty_ha(V,N,M,INIT,H,A) \
715 word _v(l) = vec_len (V); \
718 V = _vec_resize ((V), \
720 (_v(l) + _v(n))*sizeof((V)[0]), \
722 ASSERT (_v(m) <= _v(l)); \
723 memmove ((V) + _v(m) + _v(n), \
725 (_v(l) - _v(m)) * sizeof ((V)[0])); \
726 clib_memset ((V) + _v(m), INIT, _v(n) * sizeof ((V)[0])); \
729 /** \brief Insert N vector elements starting at element M,
730 initialize new elements to zero (general version)
732 @param V (possibly NULL) pointer to a vector.
733 @param N number of elements to insert
734 @param M insertion point
735 @param H header size in bytes (may be zero)
736 @param A alignment (may be zero)
737 @return V (value-result macro parameter)
739 #define vec_insert_ha(V,N,M,H,A) vec_insert_init_empty_ha(V,N,M,0,H,A)
741 /** \brief Insert N vector elements starting at element M,
742 initialize new elements to zero (no header, unspecified alignment)
744 @param V (possibly NULL) pointer to a vector.
745 @param N number of elements to insert
746 @param M insertion point
747 @return V (value-result macro parameter)
749 #define vec_insert(V,N,M) vec_insert_ha(V,N,M,0,0)
751 /** \brief Insert N vector elements starting at element M,
752 initialize new elements to zero (no header, alignment specified)
754 @param V (possibly NULL) pointer to a vector.
755 @param N number of elements to insert
756 @param M insertion point
757 @param A alignment (may be zero)
758 @return V (value-result macro parameter)
760 #define vec_insert_aligned(V,N,M,A) vec_insert_ha(V,N,M,0,A)
762 /** \brief Insert N vector elements starting at element M,
763 initialize new elements (no header, unspecified alignment)
765 @param V (possibly NULL) pointer to a vector.
766 @param N number of elements to insert
767 @param M insertion point
768 @param INIT initial value (can be a complex expression!)
769 @return V (value-result macro parameter)
772 #define vec_insert_init_empty(V,N,M,INIT) \
773 vec_insert_init_empty_ha(V,N,M,INIT,0,0)
774 /* Resize vector by N elements starting from element M, initialize new elements to INIT (alignment specified, no header). */
776 /** \brief Insert N vector elements starting at element M,
777 initialize new elements (no header, specified alignment)
779 @param V (possibly NULL) pointer to a vector.
780 @param N number of elements to insert
781 @param M insertion point
782 @param INIT initial value (can be a complex expression!)
783 @param A alignment (may be zero)
784 @return V (value-result macro parameter)
786 #define vec_insert_init_empty_aligned(V,N,M,INIT,A) \
787 vec_insert_init_empty_ha(V,N,M,INIT,0,A)
789 /** \brief Insert N vector elements starting at element M,
790 insert given elements (general version)
792 @param V (possibly NULL) pointer to a vector.
793 @param E element(s) to insert
794 @param N number of elements to insert
795 @param M insertion point
796 @param H header size in bytes (may be zero)
797 @param A alignment (may be zero)
798 @return V (value-result macro parameter)
801 #define vec_insert_elts_ha(V,E,N,M,H,A) \
803 word _v(l) = vec_len (V); \
806 V = _vec_resize ((V), \
808 (_v(l) + _v(n))*sizeof((V)[0]), \
810 ASSERT (_v(m) <= _v(l)); \
811 memmove ((V) + _v(m) + _v(n), \
813 (_v(l) - _v(m)) * sizeof ((V)[0])); \
814 clib_memcpy_fast ((V) + _v(m), (E), \
815 _v(n) * sizeof ((V)[0])); \
818 /** \brief Insert N vector elements starting at element M,
819 insert given elements (no header, unspecified alignment)
821 @param V (possibly NULL) pointer to a vector.
822 @param E element(s) to insert
823 @param N number of elements to insert
824 @param M insertion point
825 @return V (value-result macro parameter)
827 #define vec_insert_elts(V,E,N,M) vec_insert_elts_ha(V,E,N,M,0,0)
829 /** \brief Insert N vector elements starting at element M,
830 insert given elements (no header, specified alignment)
832 @param V (possibly NULL) pointer to a vector.
833 @param E element(s) to insert
834 @param N number of elements to insert
835 @param M insertion point
836 @param A alignment (may be zero)
837 @return V (value-result macro parameter)
839 #define vec_insert_elts_aligned(V,E,N,M,A) vec_insert_elts_ha(V,E,N,M,0,A)
841 /** \brief Delete N elements starting at element M
843 @param V pointer to a vector
844 @param N number of elements to delete
845 @param M first element to delete
846 @return V (value-result macro parameter)
848 #define vec_delete(V,N,M) \
850 word _v(l) = vec_len (V); \
853 /* Copy over deleted elements. */ \
854 if (_v(l) - _v(n) - _v(m) > 0) \
855 memmove ((V) + _v(m), (V) + _v(m) + _v(n), \
856 (_v(l) - _v(n) - _v(m)) * sizeof ((V)[0])); \
857 /* Zero empty space at end (for future re-allocation). */ \
859 clib_memset ((V) + _v(l) - _v(n), 0, _v(n) * sizeof ((V)[0])); \
860 _vec_len (V) -= _v(n); \
861 CLIB_MEM_POISON(vec_end(V), _v(n) * sizeof ((V)[0])); \
864 /** \brief Delete the element at index I
866 @param V pointer to a vector
867 @param I index to delete
869 #define vec_del1(v,i) \
871 uword _vec_del_l = _vec_len (v) - 1; \
872 uword _vec_del_i = (i); \
873 if (_vec_del_i < _vec_del_l) \
874 (v)[_vec_del_i] = (v)[_vec_del_l]; \
875 _vec_len (v) = _vec_del_l; \
876 CLIB_MEM_POISON(vec_end(v), sizeof ((v)[0])); \
879 /** \brief Append v2 after v1. Result in v1.
880 @param V1 target vector
881 @param V2 vector to append
884 #define vec_append(v1,v2) \
886 uword _v(l1) = vec_len (v1); \
887 uword _v(l2) = vec_len (v2); \
889 v1 = _vec_resize ((v1), _v(l2), \
890 (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0); \
891 clib_memcpy_fast ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0])); \
894 /** \brief Append v2 after v1. Result in v1. Specified alignment.
895 @param V1 target vector
896 @param V2 vector to append
897 @param align required alignment
900 #define vec_append_aligned(v1,v2,align) \
902 uword _v(l1) = vec_len (v1); \
903 uword _v(l2) = vec_len (v2); \
905 v1 = _vec_resize ((v1), _v(l2), \
906 (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align); \
907 clib_memcpy_fast ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0])); \
910 /** \brief Prepend v2 before v1. Result in v1.
911 @param V1 target vector
912 @param V2 vector to prepend
915 #define vec_prepend(v1,v2) \
917 uword _v(l1) = vec_len (v1); \
918 uword _v(l2) = vec_len (v2); \
920 v1 = _vec_resize ((v1), _v(l2), \
921 (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0); \
922 memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0])); \
923 clib_memcpy_fast ((v1), (v2), _v(l2) * sizeof ((v2)[0])); \
926 /** \brief Prepend v2 before v1. Result in v1. Specified alignment
927 @param V1 target vector
928 @param V2 vector to prepend
929 @param align required alignment
932 #define vec_prepend_aligned(v1,v2,align) \
934 uword _v(l1) = vec_len (v1); \
935 uword _v(l2) = vec_len (v2); \
937 v1 = _vec_resize ((v1), _v(l2), \
938 (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align); \
939 memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0])); \
940 clib_memcpy_fast ((v1), (v2), _v(l2) * sizeof ((v2)[0])); \
944 /** \brief Zero all vector elements. Null-pointer tolerant.
945 @param var Vector to zero
947 #define vec_zero(var) \
950 clib_memset ((var), 0, vec_len (var) * sizeof ((var)[0])); \
953 /** \brief Set all vector elements to given value. Null-pointer tolerant.
954 @param v vector to set
955 @param val value for each vector element
957 #define vec_set(v,val) \
960 __typeof__ ((v)[0]) _val = (val); \
961 for (_v(i) = 0; _v(i) < vec_len (v); _v(i)++) \
966 #include <stdlib.h> /* for qsort */
969 /** \brief Compare two vectors, not NULL-pointer tolerant
971 @param v1 Pointer to a vector
972 @param v2 Pointer to a vector
973 @return 1 if equal, 0 if unequal
975 #define vec_is_equal(v1,v2) \
976 (vec_len (v1) == vec_len (v2) && ! memcmp ((v1), (v2), vec_len (v1) * sizeof ((v1)[0])))
978 /** \brief Compare two vectors (only applicable to vectors of signed numbers).
979 Used in qsort compare functions.
981 @param v1 Pointer to a vector
982 @param v2 Pointer to a vector
985 #define vec_cmp(v1,v2) \
987 word _v(i), _v(cmp), _v(l); \
988 _v(l) = clib_min (vec_len (v1), vec_len (v2)); \
990 for (_v(i) = 0; _v(i) < _v(l); _v(i)++) { \
991 _v(cmp) = (v1)[_v(i)] - (v2)[_v(i)]; \
995 if (_v(cmp) == 0 && _v(l) > 0) \
996 _v(cmp) = vec_len(v1) - vec_len(v2); \
997 (_v(cmp) < 0 ? -1 : (_v(cmp) > 0 ? +1 : 0)); \
1000 /** \brief Search a vector for the index of the entry that matches.
1002 @param v Pointer to a vector
1003 @param E Entry to match
1004 @return index of match or ~0
1006 #define vec_search(v,E) \
1009 while (_v(i) < vec_len(v)) \
1011 if ((v)[_v(i)] == E) \
1015 if (_v(i) == vec_len(v)) \
1020 /** \brief Search a vector for the index of the entry that matches.
1022 @param v Pointer to a vector
1023 @param E Pointer to entry to match
1024 @param fn Comparison function !0 => match
1025 @return index of match or ~0
1027 #define vec_search_with_function(v,E,fn) \
1030 while (_v(i) < vec_len(v)) \
1032 if (0 != fn(&(v)[_v(i)], (E))) \
1036 if (_v(i) == vec_len(v)) \
1041 /** \brief Sort a vector using the supplied element comparison function
1043 @param vec vector to sort
1044 @param f comparison function
1046 #define vec_sort_with_function(vec,f) \
1048 qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f)); \
1051 /** \brief Make a vector containing a NULL terminated c-string.
1053 @param V (possibly NULL) pointer to a vector.
1054 @param S pointer to string buffer.
1055 @param L string length (NOT including the terminating NULL; a la strlen())
1057 #define vec_validate_init_c_string(V, S, L) \
1059 vec_reset_length (V); \
1060 vec_validate ((V), (L)); \
1062 clib_memcpy_fast ((V), (S), (L)); \
1067 /** \brief Test whether a vector is a NULL terminated c-string.
1069 @param V (possibly NULL) pointer to a vector.
1070 @return BOOLEAN indicating if the vector c-string is null terminated.
1072 #define vec_c_string_is_terminated(V) \
1073 (((V) != 0) && (vec_len (V) != 0) && ((V)[vec_len ((V)) - 1] == 0))
1075 /** \brief (If necessary) NULL terminate a vector containing a c-string.
1077 @param V (possibly NULL) pointer to a vector.
1078 @return V (value-result macro parameter)
1080 #define vec_terminate_c_string(V) \
1082 u32 vl = vec_len ((V)); \
1083 if (!vec_c_string_is_terminated(V)) \
1085 vec_validate ((V), vl); \
1090 #endif /* included_vec_h */
1094 * fd.io coding-style-patch-verification: ON
1097 * eval: (c-set-style "gnu")