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