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