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 data elements via the
76 Vectors 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 data
81 and _h variants supporting non zero length vector headers.
82 The _ha variants support both.
84 Standard programming error: memorize a pointer to the ith element
85 of a vector then expand it. Vectors expand by 3/2, so such code
86 may appear to work for a period of time. Memorize vector indices
90 /** \brief Low-level resize allocation function, usually not called directly
92 @param v pointer to a vector
93 @param length_increment length increment in elements
94 @param data_bytes requested size in bytes
95 @param header_bytes header size in bytes (may be zero)
96 @param data_align alignment (may be zero)
97 @return v_prime pointer to resized vector, may or may not equal v
99 void *vec_resize_allocate_memory (void *v,
100 word length_increment,
102 uword header_bytes, uword data_align);
104 /** \brief Low-level vector resize function, usually not called directly
106 @param v pointer to a vector
107 @param length_increment length increment in elements
108 @param data_bytes requested size in bytes
109 @param header_bytes header size in bytes (may be zero)
110 @param data_align alignment (may be zero)
111 @return v_prime pointer to resized vector, may or may not equal v
114 #define _vec_resize(V,L,DB,HB,A) \
115 _vec_resize_inline(V,L,DB,HB,clib_max((__alignof__((V)[0])),(A)))
118 _vec_resize_inline (void *v,
119 word length_increment,
120 uword data_bytes, uword header_bytes, uword data_align)
122 vec_header_t *vh = _vec_find (v);
123 uword new_data_bytes, aligned_header_bytes;
125 aligned_header_bytes = vec_header_bytes (header_bytes);
127 new_data_bytes = data_bytes + aligned_header_bytes;
129 if (PREDICT_TRUE (v != 0))
131 void *p = v - aligned_header_bytes;
133 /* Vector header must start heap object. */
134 ASSERT (clib_mem_is_heap_object (p));
136 /* Typically we'll not need to resize. */
137 if (new_data_bytes <= clib_mem_size (p))
139 vh->len += length_increment;
144 /* Slow path: call helper function. */
145 return vec_resize_allocate_memory (v, length_increment, data_bytes,
147 clib_max (sizeof (vec_header_t),
151 /** \brief Determine if vector will resize with next allocation
153 @param v pointer to a vector
154 @param length_increment length increment in elements
155 @param data_bytes requested size in bytes
156 @param header_bytes header size in bytes (may be zero)
157 @param data_align alignment (may be zero)
158 @return 1 if vector will resize 0 otherwise
162 _vec_resize_will_expand (void *v,
163 word length_increment,
164 uword data_bytes, uword header_bytes,
167 uword new_data_bytes, aligned_header_bytes;
169 aligned_header_bytes = vec_header_bytes (header_bytes);
171 new_data_bytes = data_bytes + aligned_header_bytes;
173 if (PREDICT_TRUE (v != 0))
175 void *p = v - aligned_header_bytes;
177 /* Vector header must start heap object. */
178 ASSERT (clib_mem_is_heap_object (p));
180 /* Typically we'll not need to resize. */
181 if (new_data_bytes <= clib_mem_size (p))
187 /** \brief Predicate function, says whether the supplied vector is a clib heap
188 object (general version).
190 @param v pointer to a vector
191 @param header_bytes vector header size in bytes (may be zero)
194 uword clib_mem_is_vec_h (void *v, uword header_bytes);
197 /** \brief Predicate function, says whether the supplied vector is a clib heap
200 @param v pointer to a vector
204 clib_mem_is_vec (void *v)
206 return clib_mem_is_vec_h (v, 0);
209 /* Local variable naming macro (prevents collisions with other macro naming). */
210 #define _v(var) _vec_##var
212 /** \brief Resize a vector (general version).
213 Add N elements to end of given vector V, return pointer to start of vector.
214 Vector will have room for H header bytes and will have user's data aligned
215 at alignment A (rounded to next power of 2).
217 @param V pointer to a vector
218 @param N number of elements to add
219 @param H header size in bytes (may be zero)
220 @param A alignment (may be zero)
221 @return V (value-result macro parameter)
224 #define vec_resize_ha(V,N,H,A) \
227 word _v(l) = vec_len (V); \
228 V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A)); \
231 /** \brief Resize a vector (no header, unspecified alignment)
232 Add N elements to end of given vector V, return pointer to start of vector.
233 Vector will have room for H header bytes and will have user's data aligned
234 at alignment A (rounded to next power of 2).
236 @param V pointer to a vector
237 @param N number of elements to add
238 @return V (value-result macro parameter)
240 #define vec_resize(V,N) vec_resize_ha(V,N,0,0)
242 /** \brief Resize a vector (no header, alignment specified).
243 Add N elements to end of given vector V, return pointer to start of vector.
244 Vector will have room for H header bytes and will have user's data aligned
245 at alignment A (rounded to next power of 2).
247 @param V pointer to a vector
248 @param N number of elements to add
249 @param A alignment (may be zero)
250 @return V (value-result macro parameter)
253 #define vec_resize_aligned(V,N,A) vec_resize_ha(V,N,0,A)
255 /** \brief Allocate space for N more elements
257 @param V pointer to a vector
258 @param N number of elements to add
259 @param H header size in bytes (may be zero)
260 @param A alignment (may be zero)
261 @return V (value-result macro parameter)
264 #define vec_alloc_ha(V,N,H,A) \
266 uword _v(l) = vec_len (V); \
267 vec_resize_ha (V, N, H, A); \
268 _vec_len (V) = _v(l); \
271 /** \brief Allocate space for N more elements
272 (no header, unspecified alignment)
274 @param V pointer to a vector
275 @param N number of elements to add
276 @return V (value-result macro parameter)
278 #define vec_alloc(V,N) vec_alloc_ha(V,N,0,0)
280 /** \brief Allocate space for N more elements (no header, given alignment)
281 @param V pointer to a vector
282 @param N number of elements to add
283 @param A alignment (may be zero)
284 @return V (value-result macro parameter)
287 #define vec_alloc_aligned(V,N,A) vec_alloc_ha(V,N,0,A)
289 /** \brief Create new vector of given type and length (general version).
290 @param T type of elements in new vector
291 @param N number of elements to add
292 @param H header size in bytes (may be zero)
293 @param A alignment (may be zero)
296 #define vec_new_ha(T,N,H,A) \
299 _vec_resize ((T *) 0, _v(n), _v(n) * sizeof (T), (H), (A)); \
302 /** \brief Create new vector of given type and length
303 (unspecified alignment, no header).
305 @param T type of elements in new vector
306 @param N number of elements to add
309 #define vec_new(T,N) vec_new_ha(T,N,0,0)
310 /** \brief Create new vector of given type and length
311 (alignment specified, no header).
313 @param T type of elements in new vector
314 @param N number of elements to add
315 @param A alignment (may be zero)
318 #define vec_new_aligned(T,N,A) vec_new_ha(T,N,0,A)
320 /** \brief Free vector's memory (general version)
322 @param V pointer to a vector
323 @param H size of header in bytes
324 @return V (value-result parameter, V=0)
326 #define vec_free_h(V,H) \
330 clib_mem_free (vec_header ((V), (H))); \
335 /** \brief Free vector's memory (no header).
336 @param V pointer to a vector
337 @return V (value-result parameter, V=0)
339 #define vec_free(V) vec_free_h(V,0)
341 /**\brief Free vector user header (syntactic sugar)
342 @param h vector header
345 #define vec_free_header(h) clib_mem_free (h)
347 /** \brief Return copy of vector (general version).
349 @param V pointer to a vector
350 @param H size of header in bytes
351 @param A alignment (may be zero)
353 @return Vdup copy of vector
356 #define vec_dup_ha(V,H,A) \
358 __typeof__ ((V)[0]) * _v(v) = 0; \
359 uword _v(l) = vec_len (V); \
362 vec_resize_ha (_v(v), _v(l), (H), (A)); \
363 clib_memcpy (_v(v), (V), _v(l) * sizeof ((V)[0]));\
368 /** \brief Return copy of vector (no header, no alignment)
370 @param V pointer to a vector
371 @return Vdup copy of vector
373 #define vec_dup(V) vec_dup_ha(V,0,0)
375 /** \brief Return copy of vector (no header, alignment specified).
377 @param V pointer to a vector
378 @param A alignment (may be zero)
380 @return Vdup copy of vector
382 #define vec_dup_aligned(V,A) vec_dup_ha(V,0,A)
384 /** \brief Copy a vector, memcpy wrapper. Assumes sizeof(SRC[0]) ==
387 @param DST destination
390 #define vec_copy(DST,SRC) clib_memcpy (DST, SRC, vec_len (DST) * \
393 /** \brief Clone a vector. Make a new vector with the
394 same size as a given vector but possibly with a different type.
396 @param NEW_V pointer to new vector
397 @param OLD_V pointer to old vector
399 #define vec_clone(NEW_V,OLD_V) \
402 (NEW_V) = _vec_resize ((NEW_V), vec_len (OLD_V), \
403 vec_len (OLD_V) * sizeof ((NEW_V)[0]), (0), (0)); \
406 /** \brief Make sure vector is long enough for given index (general version).
408 @param V (possibly NULL) pointer to a vector.
409 @param I vector index which will be valid upon return
410 @param H header size in bytes (may be zero)
411 @param A alignment (may be zero)
412 @return V (value-result macro parameter)
415 #define vec_validate_ha(V,I,H,A) \
417 STATIC_ASSERT(A==0 || ((A % sizeof(V[0]))==0) || ((sizeof(V[0]) % A) == 0),\
418 "vector validate aligned on incorrectly sized object"); \
420 word _v(l) = vec_len (V); \
421 if (_v(i) >= _v(l)) \
423 vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A)); \
424 /* Must zero new space since user may have previously \
425 used e.g. _vec_len (v) -= 10 */ \
426 memset ((V) + _v(l), 0, (1 + (_v(i) - _v(l))) * sizeof ((V)[0])); \
430 /** \brief Make sure vector is long enough for given index
431 (no header, unspecified alignment)
433 @param V (possibly NULL) pointer to a vector.
434 @param I vector index which will be valid upon return
435 @return V (value-result macro parameter)
437 #define vec_validate(V,I) vec_validate_ha(V,I,0,0)
439 /** \brief Make sure vector is long enough for given index
440 (no header, specified alignment)
442 @param V (possibly NULL) pointer to a vector.
443 @param I vector index which will be valid upon return
444 @param A alignment (may be zero)
445 @return V (value-result macro parameter)
448 #define vec_validate_aligned(V,I,A) vec_validate_ha(V,I,0,A)
450 /** \brief Make sure vector is long enough for given index
451 and initialize empty space (general version)
453 @param V (possibly NULL) pointer to a vector.
454 @param I vector index which will be valid upon return
455 @param INIT initial value (can be a complex expression!)
456 @param H header size in bytes (may be zero)
457 @param A alignment (may be zero)
458 @return V (value-result macro parameter)
460 #define vec_validate_init_empty_ha(V,I,INIT,H,A) \
463 word _v(l) = vec_len (V); \
464 if (_v(i) >= _v(l)) \
466 vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A)); \
467 while (_v(l) <= _v(i)) \
469 (V)[_v(l)] = (INIT); \
475 /** \brief Make sure vector is long enough for given index
476 and initialize empty space (no header, unspecified alignment)
478 @param V (possibly NULL) pointer to a vector.
479 @param I vector index which will be valid upon return
480 @param INIT initial value (can be a complex expression!)
481 @param H header size in bytes (may be zero)
482 @param A alignment (may be zero)
483 @return V (value-result macro parameter)
486 #define vec_validate_init_empty(V,I,INIT) \
487 vec_validate_init_empty_ha(V,I,INIT,0,0)
489 /** \brief Make sure vector is long enough for given index
490 and initialize empty space (no header, alignment alignment)
492 @param V (possibly NULL) pointer to a vector.
493 @param I vector index which will be valid upon return
494 @param INIT initial value (can be a complex expression!)
495 @param H header size in bytes (may be zero)
496 @param A alignment (may be zero)
497 @return V (value-result macro parameter)
499 #define vec_validate_init_empty_aligned(V,I,INIT,A) \
500 vec_validate_init_empty_ha(V,I,INIT,0,A)
502 /** \brief Add 1 element to end of vector (general version).
504 @param V pointer to a vector
505 @param E element to add
506 @param H header size in bytes (may be zero)
507 @param A alignment (may be zero)
508 @return V (value-result macro parameter)
510 #define vec_add1_ha(V,E,H,A) \
512 word _v(l) = vec_len (V); \
513 V = _vec_resize ((V), 1, (_v(l) + 1) * sizeof ((V)[0]), (H), (A)); \
517 /** \brief Add 1 element to end of vector (unspecified alignment).
519 @param V pointer to a vector
520 @param E element to add
521 @return V (value-result macro parameter)
523 #define vec_add1(V,E) vec_add1_ha(V,E,0,0)
525 /** \brief Add 1 element to end of vector (alignment specified).
527 @param V pointer to a vector
528 @param E element to add
529 @param H header size in bytes (may be zero)
530 @param A alignment (may be zero)
531 @return V (value-result macro parameter)
533 #define vec_add1_aligned(V,E,A) vec_add1_ha(V,E,0,A)
535 /** \brief Add N elements to end of vector V,
536 return pointer to new elements in P. (general version)
538 @param V pointer to a vector
539 @param P pointer to new vector element(s)
540 @param N number of elements to add
541 @param H header size in bytes (may be zero)
542 @param A alignment (may be zero)
543 @return V and P (value-result macro parameters)
545 #define vec_add2_ha(V,P,N,H,A) \
548 word _v(l) = vec_len (V); \
549 V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A)); \
553 /** \brief Add N elements to end of vector V,
554 return pointer to new elements in P. (no header, unspecified alignment)
556 @param V pointer to a vector
557 @param P pointer to new vector element(s)
558 @param N number of elements to add
559 @return V and P (value-result macro parameters)
562 #define vec_add2(V,P,N) vec_add2_ha(V,P,N,0,0)
564 /** \brief Add N elements to end of vector V,
565 return pointer to new elements in P. (no header, alignment specified)
567 @param V pointer to a vector
568 @param P pointer to new vector element(s)
569 @param N number of elements to add
570 @param A alignment (may be zero)
571 @return V and P (value-result macro parameters)
574 #define vec_add2_aligned(V,P,N,A) vec_add2_ha(V,P,N,0,A)
576 /** \brief Add N elements to end of vector V (general version)
578 @param V pointer to a vector
579 @param E pointer to element(s) to add
580 @param N number of elements to add
581 @param H header size in bytes (may be zero)
582 @param A alignment (may be zero)
583 @return V (value-result macro parameter)
585 #define vec_add_ha(V,E,N,H,A) \
588 word _v(l) = vec_len (V); \
589 V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A)); \
590 clib_memcpy ((V) + _v(l), (E), _v(n) * sizeof ((V)[0])); \
593 /** \brief Add N elements to end of vector V (no header, unspecified alignment)
595 @param V pointer to a vector
596 @param E pointer to element(s) to add
597 @param N number of elements to add
598 @return V (value-result macro parameter)
600 #define vec_add(V,E,N) vec_add_ha(V,E,N,0,0)
602 /** \brief Add N elements to end of vector V (no header, specified alignment)
604 @param V pointer to a vector
605 @param E pointer to element(s) to add
606 @param N number of elements to add
607 @param A alignment (may be zero)
608 @return V (value-result macro parameter)
610 #define vec_add_aligned(V,E,N,A) vec_add_ha(V,E,N,0,A)
612 /** \brief Returns last element of a vector and decrements its length
614 @param V pointer to a vector
615 @return E element removed from the end of the vector
619 uword _v(l) = vec_len (V); \
620 ASSERT (_v(l) > 0); \
622 _vec_len (V) = _v (l); \
626 /** \brief Set E to the last element of a vector, decrement vector length
627 @param V pointer to a vector
628 @param E pointer to the last vector element
629 @return E element removed from the end of the vector
630 (value-result macro parameter
633 #define vec_pop2(V,E) \
635 uword _v(l) = vec_len (V); \
636 if (_v(l) > 0) (E) = vec_pop (V); \
640 /** \brief Insert N vector elements starting at element M,
641 initialize new elements (general version).
643 @param V (possibly NULL) pointer to a vector.
644 @param N number of elements to insert
645 @param M insertion point
646 @param INIT initial value (can be a complex expression!)
647 @param H header size in bytes (may be zero)
648 @param A alignment (may be zero)
649 @return V (value-result macro parameter)
651 #define vec_insert_init_empty_ha(V,N,M,INIT,H,A) \
653 word _v(l) = vec_len (V); \
656 V = _vec_resize ((V), \
658 (_v(l) + _v(n))*sizeof((V)[0]), \
660 ASSERT (_v(m) <= _v(l)); \
661 memmove ((V) + _v(m) + _v(n), \
663 (_v(l) - _v(m)) * sizeof ((V)[0])); \
664 memset ((V) + _v(m), INIT, _v(n) * sizeof ((V)[0])); \
667 /** \brief Insert N vector elements starting at element M,
668 initialize new elements to zero (general version)
670 @param V (possibly NULL) pointer to a vector.
671 @param N number of elements to insert
672 @param M insertion point
673 @param H header size in bytes (may be zero)
674 @param A alignment (may be zero)
675 @return V (value-result macro parameter)
677 #define vec_insert_ha(V,N,M,H,A) vec_insert_init_empty_ha(V,N,M,0,H,A)
679 /** \brief Insert N vector elements starting at element M,
680 initialize new elements to zero (no header, unspecified alignment)
682 @param V (possibly NULL) pointer to a vector.
683 @param N number of elements to insert
684 @param M insertion point
685 @return V (value-result macro parameter)
687 #define vec_insert(V,N,M) vec_insert_ha(V,N,M,0,0)
689 /** \brief Insert N vector elements starting at element M,
690 initialize new elements to zero (no header, alignment specified)
692 @param V (possibly NULL) pointer to a vector.
693 @param N number of elements to insert
694 @param M insertion point
695 @param A alignment (may be zero)
696 @return V (value-result macro parameter)
698 #define vec_insert_aligned(V,N,M,A) vec_insert_ha(V,N,M,0,A)
700 /** \brief Insert N vector elements starting at element M,
701 initialize new elements (no header, unspecified alignment)
703 @param V (possibly NULL) pointer to a vector.
704 @param N number of elements to insert
705 @param M insertion point
706 @param INIT initial value (can be a complex expression!)
707 @return V (value-result macro parameter)
710 #define vec_insert_init_empty(V,N,M,INIT) \
711 vec_insert_init_empty_ha(V,N,M,INIT,0,0)
712 /* Resize vector by N elements starting from element M, initialize new elements to INIT (alignment specified, no header). */
714 /** \brief Insert N vector elements starting at element M,
715 initialize new elements (no header, specified alignment)
717 @param V (possibly NULL) pointer to a vector.
718 @param N number of elements to insert
719 @param M insertion point
720 @param INIT initial value (can be a complex expression!)
721 @param A alignment (may be zero)
722 @return V (value-result macro parameter)
724 #define vec_insert_init_empty_aligned(V,N,M,INIT,A) \
725 vec_insert_init_empty_ha(V,N,M,INIT,0,A)
727 /** \brief Insert N vector elements starting at element M,
728 insert given elements (general version)
730 @param V (possibly NULL) pointer to a vector.
731 @param E element(s) to insert
732 @param N number of elements to insert
733 @param M insertion point
734 @param H header size in bytes (may be zero)
735 @param A alignment (may be zero)
736 @return V (value-result macro parameter)
739 #define vec_insert_elts_ha(V,E,N,M,H,A) \
741 word _v(l) = vec_len (V); \
744 V = _vec_resize ((V), \
746 (_v(l) + _v(n))*sizeof((V)[0]), \
748 ASSERT (_v(m) <= _v(l)); \
749 memmove ((V) + _v(m) + _v(n), \
751 (_v(l) - _v(m)) * sizeof ((V)[0])); \
752 clib_memcpy ((V) + _v(m), (E), \
753 _v(n) * sizeof ((V)[0])); \
756 /** \brief Insert N vector elements starting at element M,
757 insert given elements (no header, unspecified alignment)
759 @param V (possibly NULL) pointer to a vector.
760 @param E element(s) to insert
761 @param N number of elements to insert
762 @param M insertion point
763 @return V (value-result macro parameter)
765 #define vec_insert_elts(V,E,N,M) vec_insert_elts_ha(V,E,N,M,0,0)
767 /** \brief Insert N vector elements starting at element M,
768 insert given elements (no header, specified alignment)
770 @param V (possibly NULL) pointer to a vector.
771 @param E element(s) to insert
772 @param N number of elements to insert
773 @param M insertion point
774 @param A alignment (may be zero)
775 @return V (value-result macro parameter)
777 #define vec_insert_elts_aligned(V,E,N,M,A) vec_insert_elts_ha(V,E,N,M,0,A)
779 /** \brief Delete N elements starting at element M
781 @param V pointer to a vector
782 @param N number of elements to delete
783 @param M first element to delete
784 @return V (value-result macro parameter)
786 #define vec_delete(V,N,M) \
788 word _v(l) = vec_len (V); \
791 /* Copy over deleted elements. */ \
792 if (_v(l) - _v(n) - _v(m) > 0) \
793 memmove ((V) + _v(m), (V) + _v(m) + _v(n), \
794 (_v(l) - _v(n) - _v(m)) * sizeof ((V)[0])); \
795 /* Zero empty space at end (for future re-allocation). */ \
797 memset ((V) + _v(l) - _v(n), 0, _v(n) * sizeof ((V)[0])); \
798 _vec_len (V) -= _v(n); \
801 /** \brief Delete the element at index I
803 @param V pointer to a vector
804 @param I index to delete
806 #define vec_del1(v,i) \
808 uword _vec_del_l = _vec_len (v) - 1; \
809 uword _vec_del_i = (i); \
810 if (_vec_del_i < _vec_del_l) \
811 (v)[_vec_del_i] = (v)[_vec_del_l]; \
812 _vec_len (v) = _vec_del_l; \
815 /** \brief Append v2 after v1. Result in v1.
816 @param V1 target vector
817 @param V2 vector to append
820 #define vec_append(v1,v2) \
822 uword _v(l1) = vec_len (v1); \
823 uword _v(l2) = vec_len (v2); \
825 v1 = _vec_resize ((v1), _v(l2), \
826 (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0); \
827 clib_memcpy ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0])); \
830 /** \brief Append v2 after v1. Result in v1. Specified alignment.
831 @param V1 target vector
832 @param V2 vector to append
833 @param align required alignment
836 #define vec_append_aligned(v1,v2,align) \
838 uword _v(l1) = vec_len (v1); \
839 uword _v(l2) = vec_len (v2); \
841 v1 = _vec_resize ((v1), _v(l2), \
842 (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align); \
843 clib_memcpy ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0])); \
846 /** \brief Prepend v2 before v1. Result in v1.
847 @param V1 target vector
848 @param V2 vector to prepend
851 #define vec_prepend(v1,v2) \
853 uword _v(l1) = vec_len (v1); \
854 uword _v(l2) = vec_len (v2); \
856 v1 = _vec_resize ((v1), _v(l2), \
857 (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0); \
858 memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0])); \
859 clib_memcpy ((v1), (v2), _v(l2) * sizeof ((v2)[0])); \
862 /** \brief Prepend v2 before v1. Result in v1. Specified alignment
863 @param V1 target vector
864 @param V2 vector to prepend
865 @param align required alignment
868 #define vec_prepend_aligned(v1,v2,align) \
870 uword _v(l1) = vec_len (v1); \
871 uword _v(l2) = vec_len (v2); \
873 v1 = _vec_resize ((v1), _v(l2), \
874 (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align); \
875 memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0])); \
876 clib_memcpy ((v1), (v2), _v(l2) * sizeof ((v2)[0])); \
880 /** \brief Zero all vector elements. Null-pointer tolerant.
881 @param var Vector to zero
883 #define vec_zero(var) \
886 memset ((var), 0, vec_len (var) * sizeof ((var)[0])); \
889 /** \brief Set all vector elements to given value. Null-pointer tolerant.
890 @param v vector to set
891 @param val value for each vector element
893 #define vec_set(v,val) \
896 __typeof__ ((v)[0]) _val = (val); \
897 for (_v(i) = 0; _v(i) < vec_len (v); _v(i)++) \
902 #include <stdlib.h> /* for qsort */
905 /** \brief Compare two vectors, not NULL-pointer tolerant
907 @param v1 Pointer to a vector
908 @param v2 Pointer to a vector
909 @return 1 if equal, 0 if unequal
911 #define vec_is_equal(v1,v2) \
912 (vec_len (v1) == vec_len (v2) && ! memcmp ((v1), (v2), vec_len (v1) * sizeof ((v1)[0])))
914 /** \brief Compare two vectors (only applicable to vectors of signed numbers).
915 Used in qsort compare functions.
917 @param v1 Pointer to a vector
918 @param v2 Pointer to a vector
921 #define vec_cmp(v1,v2) \
923 word _v(i), _v(cmp), _v(l); \
924 _v(l) = clib_min (vec_len (v1), vec_len (v2)); \
926 for (_v(i) = 0; _v(i) < _v(l); _v(i)++) { \
927 _v(cmp) = (v1)[_v(i)] - (v2)[_v(i)]; \
931 if (_v(cmp) == 0 && _v(l) > 0) \
932 _v(cmp) = vec_len(v1) - vec_len(v2); \
933 (_v(cmp) < 0 ? -1 : (_v(cmp) > 0 ? +1 : 0)); \
936 /** \brief Search a vector for the index of the entry that matches.
938 @param v1 Pointer to a vector
939 @param v2 Entry to match
940 @return index of match or ~0
942 #define vec_search(v,E) \
945 while (_v(i) < vec_len(v)) \
947 if ((v)[_v(i)] == E) \
951 if (_v(i) == vec_len(v)) \
956 /** \brief Search a vector for the index of the entry that matches.
958 @param v1 Pointer to a vector
959 @param v2 Pointer to entry to match
960 @param fn Comparison function !0 => match
961 @return index of match or ~0
963 #define vec_search_with_function(v,E,fn) \
966 while (_v(i) < vec_len(v)) \
968 if (0 != fn(&(v)[_v(i)], (E))) \
972 if (_v(i) == vec_len(v)) \
977 /** \brief Sort a vector using the supplied element comparison function
979 @param vec vector to sort
980 @param f comparison function
982 #define vec_sort_with_function(vec,f) \
984 qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f)); \
987 /** \brief Make a vector containing a NULL terminated c-string.
989 @param V (possibly NULL) pointer to a vector.
990 @param S pointer to string buffer.
991 @param L string length (NOT including the terminating NULL; a la strlen())
993 #define vec_validate_init_c_string(V, S, L) \
995 vec_reset_length (V); \
996 vec_validate ((V), (L)); \
998 clib_memcpy ((V), (S), (L)); \
1003 /** \brief Test whether a vector is a NULL terminated c-string.
1005 @param V (possibly NULL) pointer to a vector.
1006 @return BOOLEAN indicating if the vector c-string is null terminated.
1008 #define vec_c_string_is_terminated(V) \
1009 (((V) != 0) && (vec_len (V) != 0) && ((V)[vec_len ((V)) - 1] == 0))
1011 /** \brief (If necessary) NULL terminate a vector containing a c-string.
1013 @param V (possibly NULL) pointer to a vector.
1014 @return V (value-result macro parameter)
1016 #define vec_terminate_c_string(V) \
1018 u32 vl = vec_len ((V)); \
1019 if (!vec_c_string_is_terminated(V)) \
1021 vec_validate ((V), vl); \
1026 #endif /* included_vec_h */
1030 * fd.io coding-style-patch-verification: ON
1033 * eval: (c-set-style "gnu")