FD.io VPP  v20.01-48-g3e0dafb74
Vector Packet Processing
vec.h
Go to the documentation of this file.
1 /*
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:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
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.
14  */
15 /*
16  Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
17 
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:
25 
26  The above copyright notice and this permission notice shall be
27  included in all copies or substantial portions of the Software.
28 
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.
36 */
37 
38 #ifndef included_vec_h
39 #define included_vec_h
40 
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>
45 
46 /** \file
47 
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.
51 
52  The memory layout looks like this:
53 
54 ~~~~~~~~
55  user header (aligned to uword boundary)
56  vector length: number of elements
57  user's pointer-> vector element #0
58  vector element #1
59  ...
60 ~~~~~~~~
61 
62  The user pointer contains the address of vector element # 0. Null
63  pointer vectors are valid and mean a zero length vector.
64 
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.
69 
70  Typically, the header is not present. Headers allow for other
71  data structures to be built atop CLIB vectors.
72 
73  Users may specify the alignment for first data element of a vector
74  via the vec_*_aligned macros.
75 
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,
78  pool, etc.).
79 
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.
85 
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
89  which are invariant.
90  */
91 
92 /** \brief Low-level resize allocation function, usually not called directly
93 
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  @return v_prime pointer to resized vector, may or may not equal v
100 */
101 void *vec_resize_allocate_memory (void *v,
102  word length_increment,
103  uword data_bytes,
104  uword header_bytes, uword data_align);
105 
106 /** \brief Low-level vector resize function, usually not called directly
107 
108  @param v pointer to a vector
109  @param length_increment length increment in elements
110  @param data_bytes requested size in bytes
111  @param header_bytes header size in bytes (may be zero)
112  @param data_align alignment (may be zero)
113  @return v_prime pointer to resized vector, may or may not equal v
114 */
115 
116 #define _vec_resize(V,L,DB,HB,A) \
117  _vec_resize_inline(V,L,DB,HB,clib_max((__alignof__((V)[0])),(A)))
118 
119 always_inline void *
120 _vec_resize_inline (void *v,
121  word length_increment,
122  uword data_bytes, uword header_bytes, uword data_align)
123 {
124  vec_header_t *vh = _vec_find (v);
125  uword new_data_bytes, aligned_header_bytes;
126 
127  aligned_header_bytes = vec_header_bytes (header_bytes);
128 
129  new_data_bytes = data_bytes + aligned_header_bytes;
130 
131  if (PREDICT_TRUE (v != 0))
132  {
133  void *p = v - aligned_header_bytes;
134 
135  /* Vector header must start heap object. */
137 
138  /* Typically we'll not need to resize. */
139  if (new_data_bytes <= clib_mem_size (p))
140  {
141  CLIB_MEM_UNPOISON (v, data_bytes);
142  vh->len += length_increment;
143  return v;
144  }
145  }
146 
147  /* Slow path: call helper function. */
148  return vec_resize_allocate_memory (v, length_increment, data_bytes,
149  header_bytes,
150  clib_max (sizeof (vec_header_t),
151  data_align));
152 }
153 
154 /** \brief Determine if vector will resize with next allocation
155 
156  @param v pointer to a vector
157  @param length_increment length increment in elements
158  @param data_bytes requested size in bytes
159  @param header_bytes header size in bytes (may be zero)
160  @param data_align alignment (may be zero)
161  @return 1 if vector will resize 0 otherwise
162 */
163 
164 always_inline int
165 _vec_resize_will_expand (void *v,
166  word length_increment,
167  uword data_bytes, uword header_bytes,
168  uword data_align)
169 {
170  uword new_data_bytes, aligned_header_bytes;
171 
172  aligned_header_bytes = vec_header_bytes (header_bytes);
173 
174  new_data_bytes = data_bytes + aligned_header_bytes;
175 
176  if (PREDICT_TRUE (v != 0))
177  {
178  void *p = v - aligned_header_bytes;
179 
180  /* Vector header must start heap object. */
182 
183  /* Typically we'll not need to resize. */
184  if (new_data_bytes <= clib_mem_size (p))
185  return 0;
186  }
187  return 1;
188 }
189 
190 /** \brief Predicate function, says whether the supplied vector is a clib heap
191  object (general version).
192 
193  @param v pointer to a vector
194  @param header_bytes vector header size in bytes (may be zero)
195  @return 0 or 1
196 */
197 uword clib_mem_is_vec_h (void *v, uword header_bytes);
198 
199 
200 /** \brief Predicate function, says whether the supplied vector is a clib heap
201  object
202 
203  @param v pointer to a vector
204  @return 0 or 1
205 */
208 {
209  return clib_mem_is_vec_h (v, 0);
210 }
211 
212 /* Local variable naming macro (prevents collisions with other macro naming). */
213 #define _v(var) _vec_##var
214 
215 /** \brief Resize a vector (general version).
216  Add N elements to end of given vector V, return pointer to start of vector.
217  Vector will have room for H header bytes and will have user's data aligned
218  at alignment A (rounded to next power of 2).
219 
220  @param V pointer to a vector
221  @param N number of elements to add
222  @param H header size in bytes (may be zero)
223  @param A alignment (may be zero)
224  @return V (value-result macro parameter)
225 */
226 
227 #define vec_resize_ha(V,N,H,A) \
228 do { \
229  word _v(n) = (N); \
230  word _v(l) = vec_len (V); \
231  V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A)); \
232 } while (0)
233 
234 /** \brief Resize a vector (no header, unspecified alignment)
235  Add N elements to end of given vector V, return pointer to start of vector.
236  Vector will have room for H header bytes and will have user's data aligned
237  at alignment A (rounded to next power of 2).
238 
239  @param V pointer to a vector
240  @param N number of elements to add
241  @return V (value-result macro parameter)
242 */
243 #define vec_resize(V,N) vec_resize_ha(V,N,0,0)
244 
245 /** \brief Resize a vector (no header, alignment specified).
246  Add N elements to end of given vector V, return pointer to start of vector.
247  Vector will have room for H header bytes and will have user's data aligned
248  at alignment A (rounded to next power of 2).
249 
250  @param V pointer to a vector
251  @param N number of elements to add
252  @param A alignment (may be zero)
253  @return V (value-result macro parameter)
254 */
255 
256 #define vec_resize_aligned(V,N,A) vec_resize_ha(V,N,0,A)
257 
258 /** \brief Allocate space for N more elements
259 
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)
265 */
266 
267 #define vec_alloc_ha(V,N,H,A) \
268 do { \
269  uword _v(l) = vec_len (V); \
270  vec_resize_ha (V, N, H, A); \
271  _vec_len (V) = _v(l); \
272 } while (0)
273 
274 /** \brief Allocate space for N more elements
275  (no header, unspecified alignment)
276 
277  @param V pointer to a vector
278  @param N number of elements to add
279  @return V (value-result macro parameter)
280 */
281 #define vec_alloc(V,N) vec_alloc_ha(V,N,0,0)
282 
283 /** \brief Allocate space for N more elements (no header, given alignment)
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)
288 */
289 
290 #define vec_alloc_aligned(V,N,A) vec_alloc_ha(V,N,0,A)
291 
292 /** \brief Create new vector of given type and length (general version).
293  @param T type of elements in new vector
294  @param N number of elements to add
295  @param H header size in bytes (may be zero)
296  @param A alignment (may be zero)
297  @return V new vector
298 */
299 #define vec_new_ha(T,N,H,A) \
300 ({ \
301  word _v(n) = (N); \
302  _vec_resize ((T *) 0, _v(n), _v(n) * sizeof (T), (H), (A)); \
303 })
304 
305 /** \brief Create new vector of given type and length
306  (unspecified alignment, no header).
307 
308  @param T type of elements in new vector
309  @param N number of elements to add
310  @return V new vector
311 */
312 #define vec_new(T,N) vec_new_ha(T,N,0,0)
313 /** \brief Create new vector of given type and length
314  (alignment specified, no header).
315 
316  @param T type of elements in new vector
317  @param N number of elements to add
318  @param A alignment (may be zero)
319  @return V new vector
320 */
321 #define vec_new_aligned(T,N,A) vec_new_ha(T,N,0,A)
322 
323 /** \brief Free vector's memory (general version)
324 
325  @param V pointer to a vector
326  @param H size of header in bytes
327  @return V (value-result parameter, V=0)
328 */
329 #define vec_free_h(V,H) \
330 do { \
331  if (V) \
332  { \
333  clib_mem_free (vec_header ((V), (H))); \
334  V = 0; \
335  } \
336 } while (0)
337 
338 /** \brief Free vector's memory (no header).
339  @param V pointer to a vector
340  @return V (value-result parameter, V=0)
341 */
342 #define vec_free(V) vec_free_h(V,0)
343 
344 /**\brief Free vector user header (syntactic sugar)
345  @param h vector header
346  @void
347 */
348 #define vec_free_header(h) clib_mem_free (h)
349 
350 /** \brief Return copy of vector (general version).
351 
352  @param V pointer to a vector
353  @param H size of header in bytes
354  @param A alignment (may be zero)
355 
356  @return Vdup copy of vector
357 */
358 
359 #define vec_dup_ha(V,H,A) \
360 ({ \
361  __typeof__ ((V)[0]) * _v(v) = 0; \
362  uword _v(l) = vec_len (V); \
363  if (_v(l) > 0) \
364  { \
365  vec_resize_ha (_v(v), _v(l), (H), (A)); \
366  clib_memcpy_fast (_v(v), (V), _v(l) * sizeof ((V)[0]));\
367  } \
368  _v(v); \
369 })
370 
371 /** \brief Return copy of vector (no header, no alignment)
372 
373  @param V pointer to a vector
374  @return Vdup copy of vector
375 */
376 #define vec_dup(V) vec_dup_ha(V,0,0)
377 
378 /** \brief Return copy of vector (no header, alignment specified).
379 
380  @param V pointer to a vector
381  @param A alignment (may be zero)
382 
383  @return Vdup copy of vector
384 */
385 #define vec_dup_aligned(V,A) vec_dup_ha(V,0,A)
386 
387 /** \brief Copy a vector, memcpy wrapper. Assumes sizeof(SRC[0]) ==
388  sizeof(DST[0])
389 
390  @param DST destination
391  @param SRC source
392 */
393 #define vec_copy(DST,SRC) clib_memcpy_fast (DST, SRC, vec_len (DST) * \
394  sizeof ((DST)[0]))
395 
396 /** \brief Clone a vector. Make a new vector with the
397  same size as a given vector but possibly with a different type.
398 
399  @param NEW_V pointer to new vector
400  @param OLD_V pointer to old vector
401 */
402 #define vec_clone(NEW_V,OLD_V) \
403 do { \
404  (NEW_V) = 0; \
405  (NEW_V) = _vec_resize ((NEW_V), vec_len (OLD_V), \
406  vec_len (OLD_V) * sizeof ((NEW_V)[0]), (0), (0)); \
407 } while (0)
408 
409 /** \brief Make sure vector is long enough for given index (general version).
410 
411  @param V (possibly NULL) pointer to a vector.
412  @param I vector index which will be valid upon return
413  @param H header size in bytes (may be zero)
414  @param A alignment (may be zero)
415  @return V (value-result macro parameter)
416 */
417 
418 #define vec_validate_ha(V,I,H,A) \
419 do { \
420  STATIC_ASSERT(A==0 || ((A % sizeof(V[0]))==0) || ((sizeof(V[0]) % A) == 0),\
421  "vector validate aligned on incorrectly sized object"); \
422  word _v(i) = (I); \
423  word _v(l) = vec_len (V); \
424  if (_v(i) >= _v(l)) \
425  { \
426  vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A)); \
427  /* Must zero new space since user may have previously \
428  used e.g. _vec_len (v) -= 10 */ \
429  clib_memset ((V) + _v(l), 0, (1 + (_v(i) - _v(l))) * sizeof ((V)[0])); \
430  } \
431 } while (0)
432 
433 /** \brief Make sure vector is long enough for given index
434  (no header, unspecified alignment)
435 
436  @param V (possibly NULL) pointer to a vector.
437  @param I vector index which will be valid upon return
438  @return V (value-result macro parameter)
439 */
440 #define vec_validate(V,I) vec_validate_ha(V,I,0,0)
441 
442 /** \brief Make sure vector is long enough for given index
443  (no header, specified alignment)
444 
445  @param V (possibly NULL) pointer to a vector.
446  @param I vector index which will be valid upon return
447  @param A alignment (may be zero)
448  @return V (value-result macro parameter)
449 */
450 
451 #define vec_validate_aligned(V,I,A) vec_validate_ha(V,I,0,A)
452 
453 /** \brief Make sure vector is long enough for given index
454  and initialize empty space (general version)
455 
456  @param V (possibly NULL) pointer to a vector.
457  @param I vector index which will be valid upon return
458  @param INIT initial value (can be a complex expression!)
459  @param H header size in bytes (may be zero)
460  @param A alignment (may be zero)
461  @return V (value-result macro parameter)
462 */
463 #define vec_validate_init_empty_ha(V,I,INIT,H,A) \
464 do { \
465  word _v(i) = (I); \
466  word _v(l) = vec_len (V); \
467  if (_v(i) >= _v(l)) \
468  { \
469  vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A)); \
470  while (_v(l) <= _v(i)) \
471  { \
472  (V)[_v(l)] = (INIT); \
473  _v(l)++; \
474  } \
475  } \
476 } while (0)
477 
478 /** \brief Make sure vector is long enough for given index
479  and initialize empty space (no header, unspecified alignment)
480 
481  @param V (possibly NULL) pointer to a vector.
482  @param I vector index which will be valid upon return
483  @param INIT initial value (can be a complex expression!)
484  @return V (value-result macro parameter)
485 */
486 
487 #define vec_validate_init_empty(V,I,INIT) \
488  vec_validate_init_empty_ha(V,I,INIT,0,0)
489 
490 /** \brief Make sure vector is long enough for given index
491  and initialize empty space (no header, alignment alignment)
492 
493  @param V (possibly NULL) pointer to a vector.
494  @param I vector index which will be valid upon return
495  @param INIT initial value (can be a complex expression!)
496  @param A alignment (may be zero)
497  @return V (value-result macro parameter)
498 */
499 #define vec_validate_init_empty_aligned(V,I,INIT,A) \
500  vec_validate_init_empty_ha(V,I,INIT,0,A)
501 
502 /** \brief Add 1 element to end of vector (general version).
503 
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)
509 */
510 #define vec_add1_ha(V,E,H,A) \
511 do { \
512  word _v(l) = vec_len (V); \
513  V = _vec_resize ((V), 1, (_v(l) + 1) * sizeof ((V)[0]), (H), (A)); \
514  (V)[_v(l)] = (E); \
515 } while (0)
516 
517 /** \brief Add 1 element to end of vector (unspecified alignment).
518 
519  @param V pointer to a vector
520  @param E element to add
521  @return V (value-result macro parameter)
522 */
523 #define vec_add1(V,E) vec_add1_ha(V,E,0,0)
524 
525 /** \brief Add 1 element to end of vector (alignment specified).
526 
527  @param V pointer to a vector
528  @param E element to add
529  @param A alignment (may be zero)
530  @return V (value-result macro parameter)
531 */
532 #define vec_add1_aligned(V,E,A) vec_add1_ha(V,E,0,A)
533 
534 /** \brief Add N elements to end of vector V,
535  return pointer to new elements in P. (general version)
536 
537  @param V pointer to a vector
538  @param P pointer to new vector element(s)
539  @param N number of elements to add
540  @param H header size in bytes (may be zero)
541  @param A alignment (may be zero)
542  @return V and P (value-result macro parameters)
543 */
544 #define vec_add2_ha(V,P,N,H,A) \
545 do { \
546  word _v(n) = (N); \
547  word _v(l) = vec_len (V); \
548  V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A)); \
549  P = (V) + _v(l); \
550 } while (0)
551 
552 /** \brief Add N elements to end of vector V,
553  return pointer to new elements in P. (no header, unspecified alignment)
554 
555  @param V pointer to a vector
556  @param P pointer to new vector element(s)
557  @param N number of elements to add
558  @return V and P (value-result macro parameters)
559 */
560 
561 #define vec_add2(V,P,N) vec_add2_ha(V,P,N,0,0)
562 
563 /** \brief Add N elements to end of vector V,
564  return pointer to new elements in P. (no header, alignment specified)
565 
566  @param V pointer to a vector
567  @param P pointer to new vector element(s)
568  @param N number of elements to add
569  @param A alignment (may be zero)
570  @return V and P (value-result macro parameters)
571 */
572 
573 #define vec_add2_aligned(V,P,N,A) vec_add2_ha(V,P,N,0,A)
574 
575 /** \brief Add N elements to end of vector V (general version)
576 
577  @param V pointer to a vector
578  @param E pointer to element(s) to add
579  @param N number of elements to add
580  @param H header size in bytes (may be zero)
581  @param A alignment (may be zero)
582  @return V (value-result macro parameter)
583 */
584 #define vec_add_ha(V,E,N,H,A) \
585 do { \
586  word _v(n) = (N); \
587  word _v(l) = vec_len (V); \
588  V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A)); \
589  clib_memcpy_fast ((V) + _v(l), (E), _v(n) * sizeof ((V)[0])); \
590 } while (0)
591 
592 /** \brief Add N elements to end of vector V (no header, unspecified alignment)
593 
594  @param V pointer to a vector
595  @param E pointer to element(s) to add
596  @param N number of elements to add
597  @return V (value-result macro parameter)
598 */
599 #define vec_add(V,E,N) vec_add_ha(V,E,N,0,0)
600 
601 /** \brief Add N elements to end of vector V (no header, specified alignment)
602 
603  @param V pointer to a vector
604  @param E pointer to element(s) to add
605  @param N number of elements to add
606  @param A alignment (may be zero)
607  @return V (value-result macro parameter)
608 */
609 #define vec_add_aligned(V,E,N,A) vec_add_ha(V,E,N,0,A)
610 
611 /** \brief Returns last element of a vector and decrements its length
612 
613  @param V pointer to a vector
614  @return E element removed from the end of the vector
615 */
616 #define vec_pop(V) \
617 ({ \
618  uword _v(l) = vec_len (V); \
619  ASSERT (_v(l) > 0); \
620  _v(l) -= 1; \
621  _vec_len (V) = _v (l); \
622  (V)[_v(l)]; \
623 })
624 
625 /** \brief Set E to the last element of a vector, decrement vector length
626  @param V pointer to a vector
627  @param E pointer to the last vector element
628  @return E element removed from the end of the vector
629  (value-result macro parameter
630 */
631 
632 #define vec_pop2(V,E) \
633 ({ \
634  uword _v(l) = vec_len (V); \
635  if (_v(l) > 0) (E) = vec_pop (V); \
636  _v(l) > 0; \
637 })
638 
639 /** \brief Insert N vector elements starting at element M,
640  initialize new elements (general version).
641 
642  @param V (possibly NULL) pointer to a vector.
643  @param N number of elements to insert
644  @param M insertion point
645  @param INIT initial value (can be a complex expression!)
646  @param H header size in bytes (may be zero)
647  @param A alignment (may be zero)
648  @return V (value-result macro parameter)
649 */
650 #define vec_insert_init_empty_ha(V,N,M,INIT,H,A) \
651 do { \
652  word _v(l) = vec_len (V); \
653  word _v(n) = (N); \
654  word _v(m) = (M); \
655  V = _vec_resize ((V), \
656  _v(n), \
657  (_v(l) + _v(n))*sizeof((V)[0]), \
658  (H), (A)); \
659  ASSERT (_v(m) <= _v(l)); \
660  memmove ((V) + _v(m) + _v(n), \
661  (V) + _v(m), \
662  (_v(l) - _v(m)) * sizeof ((V)[0])); \
663  clib_memset ((V) + _v(m), INIT, _v(n) * sizeof ((V)[0])); \
664 } while (0)
665 
666 /** \brief Insert N vector elements starting at element M,
667  initialize new elements to zero (general version)
668 
669  @param V (possibly NULL) pointer to a vector.
670  @param N number of elements to insert
671  @param M insertion point
672  @param H header size in bytes (may be zero)
673  @param A alignment (may be zero)
674  @return V (value-result macro parameter)
675 */
676 #define vec_insert_ha(V,N,M,H,A) vec_insert_init_empty_ha(V,N,M,0,H,A)
677 
678 /** \brief Insert N vector elements starting at element M,
679  initialize new elements to zero (no header, unspecified alignment)
680 
681  @param V (possibly NULL) pointer to a vector.
682  @param N number of elements to insert
683  @param M insertion point
684  @return V (value-result macro parameter)
685 */
686 #define vec_insert(V,N,M) vec_insert_ha(V,N,M,0,0)
687 
688 /** \brief Insert N vector elements starting at element M,
689  initialize new elements to zero (no header, alignment specified)
690 
691  @param V (possibly NULL) pointer to a vector.
692  @param N number of elements to insert
693  @param M insertion point
694  @param A alignment (may be zero)
695  @return V (value-result macro parameter)
696 */
697 #define vec_insert_aligned(V,N,M,A) vec_insert_ha(V,N,M,0,A)
698 
699 /** \brief Insert N vector elements starting at element M,
700  initialize new elements (no header, unspecified alignment)
701 
702  @param V (possibly NULL) pointer to a vector.
703  @param N number of elements to insert
704  @param M insertion point
705  @param INIT initial value (can be a complex expression!)
706  @return V (value-result macro parameter)
707 */
708 
709 #define vec_insert_init_empty(V,N,M,INIT) \
710  vec_insert_init_empty_ha(V,N,M,INIT,0,0)
711 /* Resize vector by N elements starting from element M, initialize new elements to INIT (alignment specified, no header). */
712 
713 /** \brief Insert N vector elements starting at element M,
714  initialize new elements (no header, specified alignment)
715 
716  @param V (possibly NULL) pointer to a vector.
717  @param N number of elements to insert
718  @param M insertion point
719  @param INIT initial value (can be a complex expression!)
720  @param A alignment (may be zero)
721  @return V (value-result macro parameter)
722 */
723 #define vec_insert_init_empty_aligned(V,N,M,INIT,A) \
724  vec_insert_init_empty_ha(V,N,M,INIT,0,A)
725 
726 /** \brief Insert N vector elements starting at element M,
727  insert given elements (general version)
728 
729  @param V (possibly NULL) pointer to a vector.
730  @param E element(s) to insert
731  @param N number of elements to insert
732  @param M insertion point
733  @param H header size in bytes (may be zero)
734  @param A alignment (may be zero)
735  @return V (value-result macro parameter)
736 */
737 
738 #define vec_insert_elts_ha(V,E,N,M,H,A) \
739 do { \
740  word _v(l) = vec_len (V); \
741  word _v(n) = (N); \
742  word _v(m) = (M); \
743  V = _vec_resize ((V), \
744  _v(n), \
745  (_v(l) + _v(n))*sizeof((V)[0]), \
746  (H), (A)); \
747  ASSERT (_v(m) <= _v(l)); \
748  memmove ((V) + _v(m) + _v(n), \
749  (V) + _v(m), \
750  (_v(l) - _v(m)) * sizeof ((V)[0])); \
751  clib_memcpy_fast ((V) + _v(m), (E), \
752  _v(n) * sizeof ((V)[0])); \
753 } while (0)
754 
755 /** \brief Insert N vector elements starting at element M,
756  insert given elements (no header, unspecified alignment)
757 
758  @param V (possibly NULL) pointer to a vector.
759  @param E element(s) to insert
760  @param N number of elements to insert
761  @param M insertion point
762  @return V (value-result macro parameter)
763 */
764 #define vec_insert_elts(V,E,N,M) vec_insert_elts_ha(V,E,N,M,0,0)
765 
766 /** \brief Insert N vector elements starting at element M,
767  insert given elements (no header, specified alignment)
768 
769  @param V (possibly NULL) pointer to a vector.
770  @param E element(s) to insert
771  @param N number of elements to insert
772  @param M insertion point
773  @param A alignment (may be zero)
774  @return V (value-result macro parameter)
775 */
776 #define vec_insert_elts_aligned(V,E,N,M,A) vec_insert_elts_ha(V,E,N,M,0,A)
777 
778 /** \brief Delete N elements starting at element M
779 
780  @param V pointer to a vector
781  @param N number of elements to delete
782  @param M first element to delete
783  @return V (value-result macro parameter)
784 */
785 #define vec_delete(V,N,M) \
786 do { \
787  word _v(l) = vec_len (V); \
788  word _v(n) = (N); \
789  word _v(m) = (M); \
790  /* Copy over deleted elements. */ \
791  if (_v(l) - _v(n) - _v(m) > 0) \
792  memmove ((V) + _v(m), (V) + _v(m) + _v(n), \
793  (_v(l) - _v(n) - _v(m)) * sizeof ((V)[0])); \
794  /* Zero empty space at end (for future re-allocation). */ \
795  if (_v(n) > 0) \
796  clib_memset ((V) + _v(l) - _v(n), 0, _v(n) * sizeof ((V)[0])); \
797  _vec_len (V) -= _v(n); \
798  CLIB_MEM_POISON(vec_end(V), _v(n) * sizeof ((V)[0])); \
799 } while (0)
800 
801 /** \brief Delete the element at index I
802 
803  @param V pointer to a vector
804  @param I index to delete
805 */
806 #define vec_del1(v,i) \
807 do { \
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; \
813  CLIB_MEM_POISON(vec_end(v), sizeof ((v)[0])); \
814 } while (0)
815 
816 /** \brief Append v2 after v1. Result in v1.
817  @param V1 target vector
818  @param V2 vector to append
819 */
820 
821 #define vec_append(v1,v2) \
822 do { \
823  uword _v(l1) = vec_len (v1); \
824  uword _v(l2) = vec_len (v2); \
825  \
826  v1 = _vec_resize ((v1), _v(l2), \
827  (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0); \
828  clib_memcpy_fast ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0])); \
829 } while (0)
830 
831 /** \brief Append v2 after v1. Result in v1. Specified alignment.
832  @param V1 target vector
833  @param V2 vector to append
834  @param align required alignment
835 */
836 
837 #define vec_append_aligned(v1,v2,align) \
838 do { \
839  uword _v(l1) = vec_len (v1); \
840  uword _v(l2) = vec_len (v2); \
841  \
842  v1 = _vec_resize ((v1), _v(l2), \
843  (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align); \
844  clib_memcpy_fast ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0])); \
845 } while (0)
846 
847 /** \brief Prepend v2 before v1. Result in v1.
848  @param V1 target vector
849  @param V2 vector to prepend
850 */
851 
852 #define vec_prepend(v1,v2) \
853 do { \
854  uword _v(l1) = vec_len (v1); \
855  uword _v(l2) = vec_len (v2); \
856  \
857  v1 = _vec_resize ((v1), _v(l2), \
858  (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0); \
859  memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0])); \
860  clib_memcpy_fast ((v1), (v2), _v(l2) * sizeof ((v2)[0])); \
861 } while (0)
862 
863 /** \brief Prepend v2 before v1. Result in v1. Specified alignment
864  @param V1 target vector
865  @param V2 vector to prepend
866  @param align required alignment
867 */
868 
869 #define vec_prepend_aligned(v1,v2,align) \
870 do { \
871  uword _v(l1) = vec_len (v1); \
872  uword _v(l2) = vec_len (v2); \
873  \
874  v1 = _vec_resize ((v1), _v(l2), \
875  (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align); \
876  memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0])); \
877  clib_memcpy_fast ((v1), (v2), _v(l2) * sizeof ((v2)[0])); \
878 } while (0)
879 
880 
881 /** \brief Zero all vector elements. Null-pointer tolerant.
882  @param var Vector to zero
883 */
884 #define vec_zero(var) \
885 do { \
886  if (var) \
887  clib_memset ((var), 0, vec_len (var) * sizeof ((var)[0])); \
888 } while (0)
889 
890 /** \brief Set all vector elements to given value. Null-pointer tolerant.
891  @param v vector to set
892  @param val value for each vector element
893 */
894 #define vec_set(v,val) \
895 do { \
896  word _v(i); \
897  __typeof__ ((v)[0]) _val = (val); \
898  for (_v(i) = 0; _v(i) < vec_len (v); _v(i)++) \
899  (v)[_v(i)] = _val; \
900 } while (0)
901 
902 #ifdef CLIB_UNIX
903 #include <stdlib.h> /* for qsort */
904 #endif
905 
906 /** \brief Compare two vectors, not NULL-pointer tolerant
907 
908  @param v1 Pointer to a vector
909  @param v2 Pointer to a vector
910  @return 1 if equal, 0 if unequal
911 */
912 #define vec_is_equal(v1,v2) \
913  (vec_len (v1) == vec_len (v2) && ! memcmp ((v1), (v2), vec_len (v1) * sizeof ((v1)[0])))
914 
915 /** \brief Compare two vectors (only applicable to vectors of signed numbers).
916  Used in qsort compare functions.
917 
918  @param v1 Pointer to a vector
919  @param v2 Pointer to a vector
920  @return -1, 0, +1
921 */
922 #define vec_cmp(v1,v2) \
923 ({ \
924  word _v(i), _v(cmp), _v(l); \
925  _v(l) = clib_min (vec_len (v1), vec_len (v2)); \
926  _v(cmp) = 0; \
927  for (_v(i) = 0; _v(i) < _v(l); _v(i)++) { \
928  _v(cmp) = (v1)[_v(i)] - (v2)[_v(i)]; \
929  if (_v(cmp)) \
930  break; \
931  } \
932  if (_v(cmp) == 0 && _v(l) > 0) \
933  _v(cmp) = vec_len(v1) - vec_len(v2); \
934  (_v(cmp) < 0 ? -1 : (_v(cmp) > 0 ? +1 : 0)); \
935 })
936 
937 /** \brief Search a vector for the index of the entry that matches.
938 
939  @param v Pointer to a vector
940  @param E Entry to match
941  @return index of match or ~0
942 */
943 #define vec_search(v,E) \
944 ({ \
945  word _v(i) = 0; \
946  while (_v(i) < vec_len(v)) \
947  { \
948  if ((v)[_v(i)] == E) \
949  break; \
950  _v(i)++; \
951  } \
952  if (_v(i) == vec_len(v)) \
953  _v(i) = ~0; \
954  _v(i); \
955 })
956 
957 /** \brief Search a vector for the index of the entry that matches.
958 
959  @param v Pointer to a vector
960  @param E Pointer to entry to match
961  @param fn Comparison function !0 => match
962  @return index of match or ~0
963 */
964 #define vec_search_with_function(v,E,fn) \
965 ({ \
966  word _v(i) = 0; \
967  while (_v(i) < vec_len(v)) \
968  { \
969  if (0 != fn(&(v)[_v(i)], (E))) \
970  break; \
971  _v(i)++; \
972  } \
973  if (_v(i) == vec_len(v)) \
974  _v(i) = ~0; \
975  _v(i); \
976 })
977 
978 /** \brief Sort a vector using the supplied element comparison function
979 
980  @param vec vector to sort
981  @param f comparison function
982 */
983 #define vec_sort_with_function(vec,f) \
984 do { \
985  qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f)); \
986 } while (0)
987 
988 /** \brief Make a vector containing a NULL terminated c-string.
989 
990  @param V (possibly NULL) pointer to a vector.
991  @param S pointer to string buffer.
992  @param L string length (NOT including the terminating NULL; a la strlen())
993 */
994 #define vec_validate_init_c_string(V, S, L) \
995  do { \
996  vec_reset_length (V); \
997  vec_validate ((V), (L)); \
998  if ((S) && (L)) \
999  clib_memcpy_fast ((V), (S), (L)); \
1000  (V)[(L)] = 0; \
1001  } while (0)
1002 
1003 
1004 /** \brief Test whether a vector is a NULL terminated c-string.
1005 
1006  @param V (possibly NULL) pointer to a vector.
1007  @return BOOLEAN indicating if the vector c-string is null terminated.
1008 */
1009 #define vec_c_string_is_terminated(V) \
1010  (((V) != 0) && (vec_len (V) != 0) && ((V)[vec_len ((V)) - 1] == 0))
1011 
1012 /** \brief (If necessary) NULL terminate a vector containing a c-string.
1013 
1014  @param V (possibly NULL) pointer to a vector.
1015  @return V (value-result macro parameter)
1016 */
1017 #define vec_terminate_c_string(V) \
1018  do { \
1019  u32 vl = vec_len ((V)); \
1020  if (!vec_c_string_is_terminated(V)) \
1021  { \
1022  vec_validate ((V), vl); \
1023  (V)[vl] = 0; \
1024  } \
1025  } while (0)
1026 
1027 #endif /* included_vec_h */
1028 
1029 
1030 /*
1031  * fd.io coding-style-patch-verification: ON
1032  *
1033  * Local Variables:
1034  * eval: (c-set-style "gnu")
1035  * End:
1036  */
uword clib_mem_is_vec_h(void *v, uword header_bytes)
Predicate function, says whether the supplied vector is a clib heap object (general version)...
Definition: vec.c:117
#define CLIB_MEM_UNPOISON(a, s)
Definition: sanitizer.h:47
Optimized string handling code, including c11-compliant "safe C library" variants.
#define PREDICT_TRUE(x)
Definition: clib.h:112
i64 word
Definition: types.h:111
static uword vec_header_bytes(uword header_bytes)
Definition: vec_bootstrap.h:80
#define always_inline
Definition: ipsec.h:28
void * vec_resize_allocate_memory(void *v, word length_increment, uword data_bytes, uword header_bytes, uword data_align)
Low-level resize allocation function, usually not called directly.
Definition: vec.c:44
static uword clib_mem_size(void *p)
Definition: mem.h:261
u32 len
Number of elements in vector (NOT its allocated length).
Definition: vec_bootstrap.h:60
#define ASSERT(truth)
vector header structure
Definition: vec_bootstrap.h:55
static uword clib_mem_is_heap_object(void *p)
Definition: mem.h:203
#define clib_max(x, y)
Definition: clib.h:288
u64 uword
Definition: types.h:112
static uword clib_mem_is_vec(void *v)
Predicate function, says whether the supplied vector is a clib heap object.
Definition: vec.h:207
Vector bootstrap header file.