FD.io VPP  v20.05.1-6-gf53edbc3b
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(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 /**\brief Free vector user header (syntactic sugar)
383  @param h vector header
384  @void
385 */
386 #define vec_free_header(h) clib_mem_free (h)
387 
388 /** \brief Return copy of vector (general version).
389 
390  @param V pointer to a vector
391  @param H size of header in bytes
392  @param A alignment (may be zero)
393  @param S numa (may be VEC_NUMA_UNSPECIFIED)
394 
395  @return Vdup copy of vector
396 */
397 
398 #define vec_dup_ha_numa(V,H,A,S) \
399 ({ \
400  __typeof__ ((V)[0]) * _v(v) = 0; \
401  uword _v(l) = vec_len (V); \
402  if (_v(l) > 0) \
403  { \
404  vec_resize_has (_v(v), _v(l), (H), (A), (S)); \
405  clib_memcpy_fast (_v(v), (V), _v(l) * sizeof ((V)[0]));\
406  } \
407  _v(v); \
408 })
409 
410 /** \brief Return copy of vector (VEC_NUMA_UNSPECIFIED).
411 
412  @param V pointer to a vector
413  @param H size of header in bytes
414  @param A alignment (may be zero)
415 
416  @return Vdup copy of vector
417 */
418 #define vec_dup_ha(V,H,A) \
419  vec_dup_ha_numa(V,H,A,VEC_NUMA_UNSPECIFIED)
420 
421 
422 /** \brief Return copy of vector (no header, no alignment)
423 
424  @param V pointer to a vector
425  @return Vdup copy of vector
426 */
427 #define vec_dup(V) vec_dup_ha(V,0,0)
428 
429 /** \brief Return copy of vector (no header, alignment specified).
430 
431  @param V pointer to a vector
432  @param A alignment (may be zero)
433 
434  @return Vdup copy of vector
435 */
436 #define vec_dup_aligned(V,A) vec_dup_ha(V,0,A)
437 
438 /** \brief Copy a vector, memcpy wrapper. Assumes sizeof(SRC[0]) ==
439  sizeof(DST[0])
440 
441  @param DST destination
442  @param SRC source
443 */
444 #define vec_copy(DST,SRC) clib_memcpy_fast (DST, SRC, vec_len (DST) * \
445  sizeof ((DST)[0]))
446 
447 /** \brief Clone a vector. Make a new vector with the
448  same size as a given vector but possibly with a different type.
449 
450  @param NEW_V pointer to new vector
451  @param OLD_V pointer to old vector
452 */
453 #define vec_clone(NEW_V,OLD_V) \
454 do { \
455  (NEW_V) = 0; \
456  (NEW_V) = _vec_resize ((NEW_V), vec_len (OLD_V), \
457  vec_len (OLD_V) * sizeof ((NEW_V)[0]), (0), (0)); \
458 } while (0)
459 
460 /** \brief Make sure vector is long enough for given index (general version).
461 
462  @param V (possibly NULL) pointer to a vector.
463  @param I vector index which will be valid upon return
464  @param H header size in bytes (may be zero)
465  @param A alignment (may be zero)
466  @param N numa_id (may be zero)
467  @return V (value-result macro parameter)
468 */
469 
470 #define vec_validate_han(V,I,H,A,N) \
471 do { \
472  void *oldheap; \
473  STATIC_ASSERT(A==0 || ((A % sizeof(V[0]))==0) \
474  || ((sizeof(V[0]) % A) == 0), \
475  "vector validate aligned on incorrectly sized object"); \
476  word _v(i) = (I); \
477  word _v(l) = vec_len (V); \
478  if (_v(i) >= _v(l)) \
479  { \
480  /* switch to the per-numa heap if directed */ \
481  if (PREDICT_FALSE(N != VEC_NUMA_UNSPECIFIED)) \
482  { \
483  oldheap = clib_mem_get_per_cpu_heap(); \
484  clib_mem_set_per_cpu_heap (clib_mem_get_per_numa_heap(N)); \
485  } \
486  \
487  vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A)); \
488  /* Must zero new space since user may have previously \
489  used e.g. _vec_len (v) -= 10 */ \
490  clib_memset ((V) + _v(l), 0, \
491  (1 + (_v(i) - _v(l))) * sizeof ((V)[0])); \
492  /* Switch back to the global heap */ \
493  if (PREDICT_FALSE (N != VEC_NUMA_UNSPECIFIED)) \
494  clib_mem_set_per_cpu_heap (oldheap); \
495  } \
496 } while (0)
497 
498 #define vec_validate_ha(V,I,H,A) vec_validate_han(V,I,H,A,VEC_NUMA_UNSPECIFIED)
499 
500 /** \brief Make sure vector is long enough for given index
501  (no header, unspecified alignment)
502 
503  @param V (possibly NULL) pointer to a vector.
504  @param I vector index which will be valid upon return
505  @return V (value-result macro parameter)
506 */
507 #define vec_validate(V,I) vec_validate_ha(V,I,0,0)
508 
509 /** \brief Make sure vector is long enough for given index
510  (no header, specified alignment)
511 
512  @param V (possibly NULL) pointer to a vector.
513  @param I vector index which will be valid upon return
514  @param A alignment (may be zero)
515  @return V (value-result macro parameter)
516 */
517 
518 #define vec_validate_aligned(V,I,A) vec_validate_ha(V,I,0,A)
519 
520 /** \brief Make sure vector is long enough for given index
521  and initialize empty space (general version)
522 
523  @param V (possibly NULL) pointer to a vector.
524  @param I vector index which will be valid upon return
525  @param INIT initial value (can be a complex expression!)
526  @param H header size in bytes (may be zero)
527  @param A alignment (may be zero)
528  @return V (value-result macro parameter)
529 */
530 #define vec_validate_init_empty_ha(V,I,INIT,H,A) \
531 do { \
532  word _v(i) = (I); \
533  word _v(l) = vec_len (V); \
534  if (_v(i) >= _v(l)) \
535  { \
536  vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A)); \
537  while (_v(l) <= _v(i)) \
538  { \
539  (V)[_v(l)] = (INIT); \
540  _v(l)++; \
541  } \
542  } \
543 } while (0)
544 
545 /** \brief Make sure vector is long enough for given index
546  and initialize empty space (no header, unspecified alignment)
547 
548  @param V (possibly NULL) pointer to a vector.
549  @param I vector index which will be valid upon return
550  @param INIT initial value (can be a complex expression!)
551  @return V (value-result macro parameter)
552 */
553 
554 #define vec_validate_init_empty(V,I,INIT) \
555  vec_validate_init_empty_ha(V,I,INIT,0,0)
556 
557 /** \brief Make sure vector is long enough for given index
558  and initialize empty space (no header, alignment alignment)
559 
560  @param V (possibly NULL) pointer to a vector.
561  @param I vector index which will be valid upon return
562  @param INIT initial value (can be a complex expression!)
563  @param A alignment (may be zero)
564  @return V (value-result macro parameter)
565 */
566 #define vec_validate_init_empty_aligned(V,I,INIT,A) \
567  vec_validate_init_empty_ha(V,I,INIT,0,A)
568 
569 /** \brief Add 1 element to end of vector (general version).
570 
571  @param V pointer to a vector
572  @param E element to add
573  @param H header size in bytes (may be zero)
574  @param A alignment (may be zero)
575  @return V (value-result macro parameter)
576 */
577 #define vec_add1_ha(V,E,H,A) \
578 do { \
579  word _v(l) = vec_len (V); \
580  V = _vec_resize ((V), 1, (_v(l) + 1) * sizeof ((V)[0]), (H), (A)); \
581  (V)[_v(l)] = (E); \
582 } while (0)
583 
584 /** \brief Add 1 element to end of vector (unspecified alignment).
585 
586  @param V pointer to a vector
587  @param E element to add
588  @return V (value-result macro parameter)
589 */
590 #define vec_add1(V,E) vec_add1_ha(V,E,0,0)
591 
592 /** \brief Add 1 element to end of vector (alignment specified).
593 
594  @param V pointer to a vector
595  @param E element to add
596  @param A alignment (may be zero)
597  @return V (value-result macro parameter)
598 */
599 #define vec_add1_aligned(V,E,A) vec_add1_ha(V,E,0,A)
600 
601 /** \brief Add N elements to end of vector V,
602  return pointer to new elements in P. (general version)
603 
604  @param V pointer to a vector
605  @param P pointer to new vector element(s)
606  @param N number of elements to add
607  @param H header size in bytes (may be zero)
608  @param A alignment (may be zero)
609  @return V and P (value-result macro parameters)
610 */
611 #define vec_add2_ha(V,P,N,H,A) \
612 do { \
613  word _v(n) = (N); \
614  word _v(l) = vec_len (V); \
615  V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A)); \
616  P = (V) + _v(l); \
617 } while (0)
618 
619 /** \brief Add N elements to end of vector V,
620  return pointer to new elements in P. (no header, unspecified alignment)
621 
622  @param V pointer to a vector
623  @param P pointer to new vector element(s)
624  @param N number of elements to add
625  @return V and P (value-result macro parameters)
626 */
627 
628 #define vec_add2(V,P,N) vec_add2_ha(V,P,N,0,0)
629 
630 /** \brief Add N elements to end of vector V,
631  return pointer to new elements in P. (no header, alignment specified)
632 
633  @param V pointer to a vector
634  @param P pointer to new vector element(s)
635  @param N number of elements to add
636  @param A alignment (may be zero)
637  @return V and P (value-result macro parameters)
638 */
639 
640 #define vec_add2_aligned(V,P,N,A) vec_add2_ha(V,P,N,0,A)
641 
642 /** \brief Add N elements to end of vector V (general version)
643 
644  @param V pointer to a vector
645  @param E pointer to element(s) to add
646  @param N number of elements to add
647  @param H header size in bytes (may be zero)
648  @param A alignment (may be zero)
649  @return V (value-result macro parameter)
650 */
651 #define vec_add_ha(V,E,N,H,A) \
652 do { \
653  word _v(n) = (N); \
654  word _v(l) = vec_len (V); \
655  V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A)); \
656  clib_memcpy_fast ((V) + _v(l), (E), _v(n) * sizeof ((V)[0])); \
657 } while (0)
658 
659 /** \brief Add N elements to end of vector V (no header, unspecified alignment)
660 
661  @param V pointer to a vector
662  @param E pointer to element(s) to add
663  @param N number of elements to add
664  @return V (value-result macro parameter)
665 */
666 #define vec_add(V,E,N) vec_add_ha(V,E,N,0,0)
667 
668 /** \brief Add N elements to end of vector V (no header, specified alignment)
669 
670  @param V pointer to a vector
671  @param E pointer to element(s) to add
672  @param N number of elements to add
673  @param A alignment (may be zero)
674  @return V (value-result macro parameter)
675 */
676 #define vec_add_aligned(V,E,N,A) vec_add_ha(V,E,N,0,A)
677 
678 /** \brief Returns last element of a vector and decrements its length
679 
680  @param V pointer to a vector
681  @return E element removed from the end of the vector
682 */
683 #define vec_pop(V) \
684 ({ \
685  uword _v(l) = vec_len (V); \
686  ASSERT (_v(l) > 0); \
687  _v(l) -= 1; \
688  _vec_len (V) = _v (l); \
689  (V)[_v(l)]; \
690 })
691 
692 /** \brief Set E to the last element of a vector, decrement vector length
693  @param V pointer to a vector
694  @param E pointer to the last vector element
695  @return E element removed from the end of the vector
696  (value-result macro parameter
697 */
698 
699 #define vec_pop2(V,E) \
700 ({ \
701  uword _v(l) = vec_len (V); \
702  if (_v(l) > 0) (E) = vec_pop (V); \
703  _v(l) > 0; \
704 })
705 
706 /** \brief Insert N vector elements starting at element M,
707  initialize new elements (general version).
708 
709  @param V (possibly NULL) pointer to a vector.
710  @param N number of elements to insert
711  @param M insertion point
712  @param INIT initial value (can be a complex expression!)
713  @param H header size in bytes (may be zero)
714  @param A alignment (may be zero)
715  @return V (value-result macro parameter)
716 */
717 #define vec_insert_init_empty_ha(V,N,M,INIT,H,A) \
718 do { \
719  word _v(l) = vec_len (V); \
720  word _v(n) = (N); \
721  word _v(m) = (M); \
722  V = _vec_resize ((V), \
723  _v(n), \
724  (_v(l) + _v(n))*sizeof((V)[0]), \
725  (H), (A)); \
726  ASSERT (_v(m) <= _v(l)); \
727  memmove ((V) + _v(m) + _v(n), \
728  (V) + _v(m), \
729  (_v(l) - _v(m)) * sizeof ((V)[0])); \
730  clib_memset ((V) + _v(m), INIT, _v(n) * sizeof ((V)[0])); \
731 } while (0)
732 
733 /** \brief Insert N vector elements starting at element M,
734  initialize new elements to zero (general version)
735 
736  @param V (possibly NULL) pointer to a vector.
737  @param N number of elements to insert
738  @param M insertion point
739  @param H header size in bytes (may be zero)
740  @param A alignment (may be zero)
741  @return V (value-result macro parameter)
742 */
743 #define vec_insert_ha(V,N,M,H,A) vec_insert_init_empty_ha(V,N,M,0,H,A)
744 
745 /** \brief Insert N vector elements starting at element M,
746  initialize new elements to zero (no header, unspecified alignment)
747 
748  @param V (possibly NULL) pointer to a vector.
749  @param N number of elements to insert
750  @param M insertion point
751  @return V (value-result macro parameter)
752 */
753 #define vec_insert(V,N,M) vec_insert_ha(V,N,M,0,0)
754 
755 /** \brief Insert N vector elements starting at element M,
756  initialize new elements to zero (no header, alignment specified)
757 
758  @param V (possibly NULL) pointer to a vector.
759  @param N number of elements to insert
760  @param M insertion point
761  @param A alignment (may be zero)
762  @return V (value-result macro parameter)
763 */
764 #define vec_insert_aligned(V,N,M,A) vec_insert_ha(V,N,M,0,A)
765 
766 /** \brief Insert N vector elements starting at element M,
767  initialize new elements (no header, unspecified alignment)
768 
769  @param V (possibly NULL) pointer to a vector.
770  @param N number of elements to insert
771  @param M insertion point
772  @param INIT initial value (can be a complex expression!)
773  @return V (value-result macro parameter)
774 */
775 
776 #define vec_insert_init_empty(V,N,M,INIT) \
777  vec_insert_init_empty_ha(V,N,M,INIT,0,0)
778 /* Resize vector by N elements starting from element M, initialize new elements to INIT (alignment specified, no header). */
779 
780 /** \brief Insert N vector elements starting at element M,
781  initialize new elements (no header, specified alignment)
782 
783  @param V (possibly NULL) pointer to a vector.
784  @param N number of elements to insert
785  @param M insertion point
786  @param INIT initial value (can be a complex expression!)
787  @param A alignment (may be zero)
788  @return V (value-result macro parameter)
789 */
790 #define vec_insert_init_empty_aligned(V,N,M,INIT,A) \
791  vec_insert_init_empty_ha(V,N,M,INIT,0,A)
792 
793 /** \brief Insert N vector elements starting at element M,
794  insert given elements (general version)
795 
796  @param V (possibly NULL) pointer to a vector.
797  @param E element(s) to insert
798  @param N number of elements to insert
799  @param M insertion point
800  @param H header size in bytes (may be zero)
801  @param A alignment (may be zero)
802  @return V (value-result macro parameter)
803 */
804 
805 #define vec_insert_elts_ha(V,E,N,M,H,A) \
806 do { \
807  word _v(l) = vec_len (V); \
808  word _v(n) = (N); \
809  word _v(m) = (M); \
810  V = _vec_resize ((V), \
811  _v(n), \
812  (_v(l) + _v(n))*sizeof((V)[0]), \
813  (H), (A)); \
814  ASSERT (_v(m) <= _v(l)); \
815  memmove ((V) + _v(m) + _v(n), \
816  (V) + _v(m), \
817  (_v(l) - _v(m)) * sizeof ((V)[0])); \
818  clib_memcpy_fast ((V) + _v(m), (E), \
819  _v(n) * sizeof ((V)[0])); \
820 } while (0)
821 
822 /** \brief Insert N vector elements starting at element M,
823  insert given elements (no header, unspecified alignment)
824 
825  @param V (possibly NULL) pointer to a vector.
826  @param E element(s) to insert
827  @param N number of elements to insert
828  @param M insertion point
829  @return V (value-result macro parameter)
830 */
831 #define vec_insert_elts(V,E,N,M) vec_insert_elts_ha(V,E,N,M,0,0)
832 
833 /** \brief Insert N vector elements starting at element M,
834  insert given elements (no header, specified alignment)
835 
836  @param V (possibly NULL) pointer to a vector.
837  @param E element(s) to insert
838  @param N number of elements to insert
839  @param M insertion point
840  @param A alignment (may be zero)
841  @return V (value-result macro parameter)
842 */
843 #define vec_insert_elts_aligned(V,E,N,M,A) vec_insert_elts_ha(V,E,N,M,0,A)
844 
845 /** \brief Delete N elements starting at element M
846 
847  @param V pointer to a vector
848  @param N number of elements to delete
849  @param M first element to delete
850  @return V (value-result macro parameter)
851 */
852 #define vec_delete(V,N,M) \
853 do { \
854  word _v(l) = vec_len (V); \
855  word _v(n) = (N); \
856  word _v(m) = (M); \
857  /* Copy over deleted elements. */ \
858  if (_v(l) - _v(n) - _v(m) > 0) \
859  memmove ((V) + _v(m), (V) + _v(m) + _v(n), \
860  (_v(l) - _v(n) - _v(m)) * sizeof ((V)[0])); \
861  /* Zero empty space at end (for future re-allocation). */ \
862  if (_v(n) > 0) \
863  clib_memset ((V) + _v(l) - _v(n), 0, _v(n) * sizeof ((V)[0])); \
864  _vec_len (V) -= _v(n); \
865  CLIB_MEM_POISON(vec_end(V), _v(n) * sizeof ((V)[0])); \
866 } while (0)
867 
868 /** \brief Delete the element at index I
869 
870  @param V pointer to a vector
871  @param I index to delete
872 */
873 #define vec_del1(v,i) \
874 do { \
875  uword _vec_del_l = _vec_len (v) - 1; \
876  uword _vec_del_i = (i); \
877  if (_vec_del_i < _vec_del_l) \
878  (v)[_vec_del_i] = (v)[_vec_del_l]; \
879  _vec_len (v) = _vec_del_l; \
880  CLIB_MEM_POISON(vec_end(v), sizeof ((v)[0])); \
881 } while (0)
882 
883 /** \brief Append v2 after v1. Result in v1.
884  @param V1 target vector
885  @param V2 vector to append
886 */
887 
888 #define vec_append(v1,v2) \
889 do { \
890  uword _v(l1) = vec_len (v1); \
891  uword _v(l2) = vec_len (v2); \
892  \
893  v1 = _vec_resize ((v1), _v(l2), \
894  (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0); \
895  clib_memcpy_fast ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0])); \
896 } while (0)
897 
898 /** \brief Append v2 after v1. Result in v1. Specified alignment.
899  @param V1 target vector
900  @param V2 vector to append
901  @param align required alignment
902 */
903 
904 #define vec_append_aligned(v1,v2,align) \
905 do { \
906  uword _v(l1) = vec_len (v1); \
907  uword _v(l2) = vec_len (v2); \
908  \
909  v1 = _vec_resize ((v1), _v(l2), \
910  (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align); \
911  clib_memcpy_fast ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0])); \
912 } while (0)
913 
914 /** \brief Prepend v2 before v1. Result in v1.
915  @param V1 target vector
916  @param V2 vector to prepend
917 */
918 
919 #define vec_prepend(v1,v2) \
920 do { \
921  uword _v(l1) = vec_len (v1); \
922  uword _v(l2) = vec_len (v2); \
923  \
924  v1 = _vec_resize ((v1), _v(l2), \
925  (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0); \
926  memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0])); \
927  clib_memcpy_fast ((v1), (v2), _v(l2) * sizeof ((v2)[0])); \
928 } while (0)
929 
930 /** \brief Prepend v2 before v1. Result in v1. Specified alignment
931  @param V1 target vector
932  @param V2 vector to prepend
933  @param align required alignment
934 */
935 
936 #define vec_prepend_aligned(v1,v2,align) \
937 do { \
938  uword _v(l1) = vec_len (v1); \
939  uword _v(l2) = vec_len (v2); \
940  \
941  v1 = _vec_resize ((v1), _v(l2), \
942  (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align); \
943  memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0])); \
944  clib_memcpy_fast ((v1), (v2), _v(l2) * sizeof ((v2)[0])); \
945 } while (0)
946 
947 
948 /** \brief Zero all vector elements. Null-pointer tolerant.
949  @param var Vector to zero
950 */
951 #define vec_zero(var) \
952 do { \
953  if (var) \
954  clib_memset ((var), 0, vec_len (var) * sizeof ((var)[0])); \
955 } while (0)
956 
957 /** \brief Set all vector elements to given value. Null-pointer tolerant.
958  @param v vector to set
959  @param val value for each vector element
960 */
961 #define vec_set(v,val) \
962 do { \
963  word _v(i); \
964  __typeof__ ((v)[0]) _val = (val); \
965  for (_v(i) = 0; _v(i) < vec_len (v); _v(i)++) \
966  (v)[_v(i)] = _val; \
967 } while (0)
968 
969 #ifdef CLIB_UNIX
970 #include <stdlib.h> /* for qsort */
971 #endif
972 
973 /** \brief Compare two vectors, not NULL-pointer tolerant
974 
975  @param v1 Pointer to a vector
976  @param v2 Pointer to a vector
977  @return 1 if equal, 0 if unequal
978 */
979 #define vec_is_equal(v1,v2) \
980  (vec_len (v1) == vec_len (v2) && ! memcmp ((v1), (v2), vec_len (v1) * sizeof ((v1)[0])))
981 
982 /** \brief Compare two vectors (only applicable to vectors of signed numbers).
983  Used in qsort compare functions.
984 
985  @param v1 Pointer to a vector
986  @param v2 Pointer to a vector
987  @return -1, 0, +1
988 */
989 #define vec_cmp(v1,v2) \
990 ({ \
991  word _v(i), _v(cmp), _v(l); \
992  _v(l) = clib_min (vec_len (v1), vec_len (v2)); \
993  _v(cmp) = 0; \
994  for (_v(i) = 0; _v(i) < _v(l); _v(i)++) { \
995  _v(cmp) = (v1)[_v(i)] - (v2)[_v(i)]; \
996  if (_v(cmp)) \
997  break; \
998  } \
999  if (_v(cmp) == 0 && _v(l) > 0) \
1000  _v(cmp) = vec_len(v1) - vec_len(v2); \
1001  (_v(cmp) < 0 ? -1 : (_v(cmp) > 0 ? +1 : 0)); \
1002 })
1003 
1004 /** \brief Search a vector for the index of the entry that matches.
1005 
1006  @param v Pointer to a vector
1007  @param E Entry to match
1008  @return index of match or ~0
1009 */
1010 #define vec_search(v,E) \
1011 ({ \
1012  word _v(i) = 0; \
1013  while (_v(i) < vec_len(v)) \
1014  { \
1015  if ((v)[_v(i)] == E) \
1016  break; \
1017  _v(i)++; \
1018  } \
1019  if (_v(i) == vec_len(v)) \
1020  _v(i) = ~0; \
1021  _v(i); \
1022 })
1023 
1024 /** \brief Search a vector for the index of the entry that matches.
1025 
1026  @param v Pointer to a vector
1027  @param E Pointer to entry to match
1028  @param fn Comparison function !0 => match
1029  @return index of match or ~0
1030 */
1031 #define vec_search_with_function(v,E,fn) \
1032 ({ \
1033  word _v(i) = 0; \
1034  while (_v(i) < vec_len(v)) \
1035  { \
1036  if (0 != fn(&(v)[_v(i)], (E))) \
1037  break; \
1038  _v(i)++; \
1039  } \
1040  if (_v(i) == vec_len(v)) \
1041  _v(i) = ~0; \
1042  _v(i); \
1043 })
1044 
1045 /** \brief Sort a vector using the supplied element comparison function
1046 
1047  Does not depend on the underlying implementation to deal correctly
1048  with null, zero-long, or 1-long vectors
1049 
1050  @param vec vector to sort
1051  @param f comparison function
1052 */
1053 #define vec_sort_with_function(vec,f) \
1054 do { \
1055  if (vec_len (vec) > 1) \
1056  qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f)); \
1057 } while (0)
1058 
1059 /** \brief Make a vector containing a NULL terminated c-string.
1060 
1061  @param V (possibly NULL) pointer to a vector.
1062  @param S pointer to string buffer.
1063  @param L string length (NOT including the terminating NULL; a la strlen())
1064 */
1065 #define vec_validate_init_c_string(V, S, L) \
1066  do { \
1067  vec_reset_length (V); \
1068  vec_validate ((V), (L)); \
1069  if ((S) && (L)) \
1070  clib_memcpy_fast ((V), (S), (L)); \
1071  (V)[(L)] = 0; \
1072  } while (0)
1073 
1074 
1075 /** \brief Test whether a vector is a NULL terminated c-string.
1076 
1077  @param V (possibly NULL) pointer to a vector.
1078  @return BOOLEAN indicating if the vector c-string is null terminated.
1079 */
1080 #define vec_c_string_is_terminated(V) \
1081  (((V) != 0) && (vec_len (V) != 0) && ((V)[vec_len ((V)) - 1] == 0))
1082 
1083 /** \brief (If necessary) NULL terminate a vector containing a c-string.
1084 
1085  @param V (possibly NULL) pointer to a vector.
1086  @return V (value-result macro parameter)
1087 */
1088 #define vec_terminate_c_string(V) \
1089  do { \
1090  u32 vl = vec_len ((V)); \
1091  if (!vec_c_string_is_terminated(V)) \
1092  { \
1093  vec_validate ((V), vl); \
1094  (V)[vl] = 0; \
1095  } \
1096  } while (0)
1097 
1098 #endif /* included_vec_h */
1099 
1100 
1101 /*
1102  * fd.io coding-style-patch-verification: ON
1103  *
1104  * Local Variables:
1105  * eval: (c-set-style "gnu")
1106  * End:
1107  */
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:119
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
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:118
#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:312
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.