FD.io VPP  v19.01.1-17-ge106252
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  @param H header size in bytes (may be zero)
484  @param A alignment (may be zero)
485  @return V (value-result macro parameter)
486 */
487 
488 #define vec_validate_init_empty(V,I,INIT) \
489  vec_validate_init_empty_ha(V,I,INIT,0,0)
490 
491 /** \brief Make sure vector is long enough for given index
492  and initialize empty space (no header, alignment alignment)
493 
494  @param V (possibly NULL) pointer to a vector.
495  @param I vector index which will be valid upon return
496  @param INIT initial value (can be a complex expression!)
497  @param H header size in bytes (may be zero)
498  @param A alignment (may be zero)
499  @return V (value-result macro parameter)
500 */
501 #define vec_validate_init_empty_aligned(V,I,INIT,A) \
502  vec_validate_init_empty_ha(V,I,INIT,0,A)
503 
504 /** \brief Add 1 element to end of vector (general version).
505 
506  @param V pointer to a vector
507  @param E element to add
508  @param H header size in bytes (may be zero)
509  @param A alignment (may be zero)
510  @return V (value-result macro parameter)
511 */
512 #define vec_add1_ha(V,E,H,A) \
513 do { \
514  word _v(l) = vec_len (V); \
515  V = _vec_resize ((V), 1, (_v(l) + 1) * sizeof ((V)[0]), (H), (A)); \
516  (V)[_v(l)] = (E); \
517 } while (0)
518 
519 /** \brief Add 1 element to end of vector (unspecified alignment).
520 
521  @param V pointer to a vector
522  @param E element to add
523  @return V (value-result macro parameter)
524 */
525 #define vec_add1(V,E) vec_add1_ha(V,E,0,0)
526 
527 /** \brief Add 1 element to end of vector (alignment specified).
528 
529  @param V pointer to a vector
530  @param E element to add
531  @param H header size in bytes (may be zero)
532  @param A alignment (may be zero)
533  @return V (value-result macro parameter)
534 */
535 #define vec_add1_aligned(V,E,A) vec_add1_ha(V,E,0,A)
536 
537 /** \brief Add N elements to end of vector V,
538  return pointer to new elements in P. (general version)
539 
540  @param V pointer to a vector
541  @param P pointer to new vector element(s)
542  @param N number of elements to add
543  @param H header size in bytes (may be zero)
544  @param A alignment (may be zero)
545  @return V and P (value-result macro parameters)
546 */
547 #define vec_add2_ha(V,P,N,H,A) \
548 do { \
549  word _v(n) = (N); \
550  word _v(l) = vec_len (V); \
551  V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A)); \
552  P = (V) + _v(l); \
553 } while (0)
554 
555 /** \brief Add N elements to end of vector V,
556  return pointer to new elements in P. (no header, unspecified alignment)
557 
558  @param V pointer to a vector
559  @param P pointer to new vector element(s)
560  @param N number of elements to add
561  @return V and P (value-result macro parameters)
562 */
563 
564 #define vec_add2(V,P,N) vec_add2_ha(V,P,N,0,0)
565 
566 /** \brief Add N elements to end of vector V,
567  return pointer to new elements in P. (no header, alignment specified)
568 
569  @param V pointer to a vector
570  @param P pointer to new vector element(s)
571  @param N number of elements to add
572  @param A alignment (may be zero)
573  @return V and P (value-result macro parameters)
574 */
575 
576 #define vec_add2_aligned(V,P,N,A) vec_add2_ha(V,P,N,0,A)
577 
578 /** \brief Add N elements to end of vector V (general version)
579 
580  @param V pointer to a vector
581  @param E pointer to element(s) to add
582  @param N number of elements to add
583  @param H header size in bytes (may be zero)
584  @param A alignment (may be zero)
585  @return V (value-result macro parameter)
586 */
587 #define vec_add_ha(V,E,N,H,A) \
588 do { \
589  word _v(n) = (N); \
590  word _v(l) = vec_len (V); \
591  V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A)); \
592  clib_memcpy_fast ((V) + _v(l), (E), _v(n) * sizeof ((V)[0])); \
593 } while (0)
594 
595 /** \brief Add N elements to end of vector V (no header, unspecified alignment)
596 
597  @param V pointer to a vector
598  @param E pointer to element(s) to add
599  @param N number of elements to add
600  @return V (value-result macro parameter)
601 */
602 #define vec_add(V,E,N) vec_add_ha(V,E,N,0,0)
603 
604 /** \brief Add N elements to end of vector V (no header, specified alignment)
605 
606  @param V pointer to a vector
607  @param E pointer to element(s) to add
608  @param N number of elements to add
609  @param A alignment (may be zero)
610  @return V (value-result macro parameter)
611 */
612 #define vec_add_aligned(V,E,N,A) vec_add_ha(V,E,N,0,A)
613 
614 /** \brief Returns last element of a vector and decrements its length
615 
616  @param V pointer to a vector
617  @return E element removed from the end of the vector
618 */
619 #define vec_pop(V) \
620 ({ \
621  uword _v(l) = vec_len (V); \
622  ASSERT (_v(l) > 0); \
623  _v(l) -= 1; \
624  _vec_len (V) = _v (l); \
625  (V)[_v(l)]; \
626 })
627 
628 /** \brief Set E to the last element of a vector, decrement vector length
629  @param V pointer to a vector
630  @param E pointer to the last vector element
631  @return E element removed from the end of the vector
632  (value-result macro parameter
633 */
634 
635 #define vec_pop2(V,E) \
636 ({ \
637  uword _v(l) = vec_len (V); \
638  if (_v(l) > 0) (E) = vec_pop (V); \
639  _v(l) > 0; \
640 })
641 
642 /** \brief Insert N vector elements starting at element M,
643  initialize new elements (general version).
644 
645  @param V (possibly NULL) pointer to a vector.
646  @param N number of elements to insert
647  @param M insertion point
648  @param INIT initial value (can be a complex expression!)
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_insert_init_empty_ha(V,N,M,INIT,H,A) \
654 do { \
655  word _v(l) = vec_len (V); \
656  word _v(n) = (N); \
657  word _v(m) = (M); \
658  V = _vec_resize ((V), \
659  _v(n), \
660  (_v(l) + _v(n))*sizeof((V)[0]), \
661  (H), (A)); \
662  ASSERT (_v(m) <= _v(l)); \
663  memmove ((V) + _v(m) + _v(n), \
664  (V) + _v(m), \
665  (_v(l) - _v(m)) * sizeof ((V)[0])); \
666  clib_memset ((V) + _v(m), INIT, _v(n) * sizeof ((V)[0])); \
667 } while (0)
668 
669 /** \brief Insert N vector elements starting at element M,
670  initialize new elements to zero (general version)
671 
672  @param V (possibly NULL) pointer to a vector.
673  @param N number of elements to insert
674  @param M insertion point
675  @param H header size in bytes (may be zero)
676  @param A alignment (may be zero)
677  @return V (value-result macro parameter)
678 */
679 #define vec_insert_ha(V,N,M,H,A) vec_insert_init_empty_ha(V,N,M,0,H,A)
680 
681 /** \brief Insert N vector elements starting at element M,
682  initialize new elements to zero (no header, unspecified alignment)
683 
684  @param V (possibly NULL) pointer to a vector.
685  @param N number of elements to insert
686  @param M insertion point
687  @return V (value-result macro parameter)
688 */
689 #define vec_insert(V,N,M) vec_insert_ha(V,N,M,0,0)
690 
691 /** \brief Insert N vector elements starting at element M,
692  initialize new elements to zero (no header, alignment specified)
693 
694  @param V (possibly NULL) pointer to a vector.
695  @param N number of elements to insert
696  @param M insertion point
697  @param A alignment (may be zero)
698  @return V (value-result macro parameter)
699 */
700 #define vec_insert_aligned(V,N,M,A) vec_insert_ha(V,N,M,0,A)
701 
702 /** \brief Insert N vector elements starting at element M,
703  initialize new elements (no header, unspecified alignment)
704 
705  @param V (possibly NULL) pointer to a vector.
706  @param N number of elements to insert
707  @param M insertion point
708  @param INIT initial value (can be a complex expression!)
709  @return V (value-result macro parameter)
710 */
711 
712 #define vec_insert_init_empty(V,N,M,INIT) \
713  vec_insert_init_empty_ha(V,N,M,INIT,0,0)
714 /* Resize vector by N elements starting from element M, initialize new elements to INIT (alignment specified, no header). */
715 
716 /** \brief Insert N vector elements starting at element M,
717  initialize new elements (no header, specified alignment)
718 
719  @param V (possibly NULL) pointer to a vector.
720  @param N number of elements to insert
721  @param M insertion point
722  @param INIT initial value (can be a complex expression!)
723  @param A alignment (may be zero)
724  @return V (value-result macro parameter)
725 */
726 #define vec_insert_init_empty_aligned(V,N,M,INIT,A) \
727  vec_insert_init_empty_ha(V,N,M,INIT,0,A)
728 
729 /** \brief Insert N vector elements starting at element M,
730  insert given elements (general version)
731 
732  @param V (possibly NULL) pointer to a vector.
733  @param E element(s) to insert
734  @param N number of elements to insert
735  @param M insertion point
736  @param H header size in bytes (may be zero)
737  @param A alignment (may be zero)
738  @return V (value-result macro parameter)
739 */
740 
741 #define vec_insert_elts_ha(V,E,N,M,H,A) \
742 do { \
743  word _v(l) = vec_len (V); \
744  word _v(n) = (N); \
745  word _v(m) = (M); \
746  V = _vec_resize ((V), \
747  _v(n), \
748  (_v(l) + _v(n))*sizeof((V)[0]), \
749  (H), (A)); \
750  ASSERT (_v(m) <= _v(l)); \
751  memmove ((V) + _v(m) + _v(n), \
752  (V) + _v(m), \
753  (_v(l) - _v(m)) * sizeof ((V)[0])); \
754  clib_memcpy_fast ((V) + _v(m), (E), \
755  _v(n) * sizeof ((V)[0])); \
756 } while (0)
757 
758 /** \brief Insert N vector elements starting at element M,
759  insert given elements (no header, unspecified alignment)
760 
761  @param V (possibly NULL) pointer to a vector.
762  @param E element(s) to insert
763  @param N number of elements to insert
764  @param M insertion point
765  @return V (value-result macro parameter)
766 */
767 #define vec_insert_elts(V,E,N,M) vec_insert_elts_ha(V,E,N,M,0,0)
768 
769 /** \brief Insert N vector elements starting at element M,
770  insert given elements (no header, specified alignment)
771 
772  @param V (possibly NULL) pointer to a vector.
773  @param E element(s) to insert
774  @param N number of elements to insert
775  @param M insertion point
776  @param A alignment (may be zero)
777  @return V (value-result macro parameter)
778 */
779 #define vec_insert_elts_aligned(V,E,N,M,A) vec_insert_elts_ha(V,E,N,M,0,A)
780 
781 /** \brief Delete N elements starting at element M
782 
783  @param V pointer to a vector
784  @param N number of elements to delete
785  @param M first element to delete
786  @return V (value-result macro parameter)
787 */
788 #define vec_delete(V,N,M) \
789 do { \
790  word _v(l) = vec_len (V); \
791  word _v(n) = (N); \
792  word _v(m) = (M); \
793  /* Copy over deleted elements. */ \
794  if (_v(l) - _v(n) - _v(m) > 0) \
795  memmove ((V) + _v(m), (V) + _v(m) + _v(n), \
796  (_v(l) - _v(n) - _v(m)) * sizeof ((V)[0])); \
797  /* Zero empty space at end (for future re-allocation). */ \
798  if (_v(n) > 0) \
799  clib_memset ((V) + _v(l) - _v(n), 0, _v(n) * sizeof ((V)[0])); \
800  _vec_len (V) -= _v(n); \
801 } while (0)
802 
803 /** \brief Delete the element at index I
804 
805  @param V pointer to a vector
806  @param I index to delete
807 */
808 #define vec_del1(v,i) \
809 do { \
810  uword _vec_del_l = _vec_len (v) - 1; \
811  uword _vec_del_i = (i); \
812  if (_vec_del_i < _vec_del_l) \
813  (v)[_vec_del_i] = (v)[_vec_del_l]; \
814  _vec_len (v) = _vec_del_l; \
815 } while (0)
816 
817 /** \brief Append v2 after v1. Result in v1.
818  @param V1 target vector
819  @param V2 vector to append
820 */
821 
822 #define vec_append(v1,v2) \
823 do { \
824  uword _v(l1) = vec_len (v1); \
825  uword _v(l2) = vec_len (v2); \
826  \
827  v1 = _vec_resize ((v1), _v(l2), \
828  (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0); \
829  clib_memcpy_fast ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0])); \
830 } while (0)
831 
832 /** \brief Append v2 after v1. Result in v1. Specified alignment.
833  @param V1 target vector
834  @param V2 vector to append
835  @param align required alignment
836 */
837 
838 #define vec_append_aligned(v1,v2,align) \
839 do { \
840  uword _v(l1) = vec_len (v1); \
841  uword _v(l2) = vec_len (v2); \
842  \
843  v1 = _vec_resize ((v1), _v(l2), \
844  (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align); \
845  clib_memcpy_fast ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0])); \
846 } while (0)
847 
848 /** \brief Prepend v2 before v1. Result in v1.
849  @param V1 target vector
850  @param V2 vector to prepend
851 */
852 
853 #define vec_prepend(v1,v2) \
854 do { \
855  uword _v(l1) = vec_len (v1); \
856  uword _v(l2) = vec_len (v2); \
857  \
858  v1 = _vec_resize ((v1), _v(l2), \
859  (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0); \
860  memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0])); \
861  clib_memcpy_fast ((v1), (v2), _v(l2) * sizeof ((v2)[0])); \
862 } while (0)
863 
864 /** \brief Prepend v2 before v1. Result in v1. Specified alignment
865  @param V1 target vector
866  @param V2 vector to prepend
867  @param align required alignment
868 */
869 
870 #define vec_prepend_aligned(v1,v2,align) \
871 do { \
872  uword _v(l1) = vec_len (v1); \
873  uword _v(l2) = vec_len (v2); \
874  \
875  v1 = _vec_resize ((v1), _v(l2), \
876  (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align); \
877  memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0])); \
878  clib_memcpy_fast ((v1), (v2), _v(l2) * sizeof ((v2)[0])); \
879 } while (0)
880 
881 
882 /** \brief Zero all vector elements. Null-pointer tolerant.
883  @param var Vector to zero
884 */
885 #define vec_zero(var) \
886 do { \
887  if (var) \
888  clib_memset ((var), 0, vec_len (var) * sizeof ((var)[0])); \
889 } while (0)
890 
891 /** \brief Set all vector elements to given value. Null-pointer tolerant.
892  @param v vector to set
893  @param val value for each vector element
894 */
895 #define vec_set(v,val) \
896 do { \
897  word _v(i); \
898  __typeof__ ((v)[0]) _val = (val); \
899  for (_v(i) = 0; _v(i) < vec_len (v); _v(i)++) \
900  (v)[_v(i)] = _val; \
901 } while (0)
902 
903 #ifdef CLIB_UNIX
904 #include <stdlib.h> /* for qsort */
905 #endif
906 
907 /** \brief Compare two vectors, not NULL-pointer tolerant
908 
909  @param v1 Pointer to a vector
910  @param v2 Pointer to a vector
911  @return 1 if equal, 0 if unequal
912 */
913 #define vec_is_equal(v1,v2) \
914  (vec_len (v1) == vec_len (v2) && ! memcmp ((v1), (v2), vec_len (v1) * sizeof ((v1)[0])))
915 
916 /** \brief Compare two vectors (only applicable to vectors of signed numbers).
917  Used in qsort compare functions.
918 
919  @param v1 Pointer to a vector
920  @param v2 Pointer to a vector
921  @return -1, 0, +1
922 */
923 #define vec_cmp(v1,v2) \
924 ({ \
925  word _v(i), _v(cmp), _v(l); \
926  _v(l) = clib_min (vec_len (v1), vec_len (v2)); \
927  _v(cmp) = 0; \
928  for (_v(i) = 0; _v(i) < _v(l); _v(i)++) { \
929  _v(cmp) = (v1)[_v(i)] - (v2)[_v(i)]; \
930  if (_v(cmp)) \
931  break; \
932  } \
933  if (_v(cmp) == 0 && _v(l) > 0) \
934  _v(cmp) = vec_len(v1) - vec_len(v2); \
935  (_v(cmp) < 0 ? -1 : (_v(cmp) > 0 ? +1 : 0)); \
936 })
937 
938 /** \brief Search a vector for the index of the entry that matches.
939 
940  @param v1 Pointer to a vector
941  @param v2 Entry to match
942  @return index of match or ~0
943 */
944 #define vec_search(v,E) \
945 ({ \
946  word _v(i) = 0; \
947  while (_v(i) < vec_len(v)) \
948  { \
949  if ((v)[_v(i)] == E) \
950  break; \
951  _v(i)++; \
952  } \
953  if (_v(i) == vec_len(v)) \
954  _v(i) = ~0; \
955  _v(i); \
956 })
957 
958 /** \brief Search a vector for the index of the entry that matches.
959 
960  @param v1 Pointer to a vector
961  @param v2 Pointer to entry to match
962  @param fn Comparison function !0 => match
963  @return index of match or ~0
964 */
965 #define vec_search_with_function(v,E,fn) \
966 ({ \
967  word _v(i) = 0; \
968  while (_v(i) < vec_len(v)) \
969  { \
970  if (0 != fn(&(v)[_v(i)], (E))) \
971  break; \
972  _v(i)++; \
973  } \
974  if (_v(i) == vec_len(v)) \
975  _v(i) = ~0; \
976  _v(i); \
977 })
978 
979 /** \brief Sort a vector using the supplied element comparison function
980 
981  @param vec vector to sort
982  @param f comparison function
983 */
984 #define vec_sort_with_function(vec,f) \
985 do { \
986  qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f)); \
987 } while (0)
988 
989 /** \brief Make a vector containing a NULL terminated c-string.
990 
991  @param V (possibly NULL) pointer to a vector.
992  @param S pointer to string buffer.
993  @param L string length (NOT including the terminating NULL; a la strlen())
994 */
995 #define vec_validate_init_c_string(V, S, L) \
996  do { \
997  vec_reset_length (V); \
998  vec_validate ((V), (L)); \
999  if ((S) && (L)) \
1000  clib_memcpy_fast ((V), (S), (L)); \
1001  (V)[(L)] = 0; \
1002  } while (0)
1003 
1004 
1005 /** \brief Test whether a vector is a NULL terminated c-string.
1006 
1007  @param V (possibly NULL) pointer to a vector.
1008  @return BOOLEAN indicating if the vector c-string is null terminated.
1009 */
1010 #define vec_c_string_is_terminated(V) \
1011  (((V) != 0) && (vec_len (V) != 0) && ((V)[vec_len ((V)) - 1] == 0))
1012 
1013 /** \brief (If necessary) NULL terminate a vector containing a c-string.
1014 
1015  @param V (possibly NULL) pointer to a vector.
1016  @return V (value-result macro parameter)
1017 */
1018 #define vec_terminate_c_string(V) \
1019  do { \
1020  u32 vl = vec_len ((V)); \
1021  if (!vec_c_string_is_terminated(V)) \
1022  { \
1023  vec_validate ((V), vl); \
1024  (V)[vl] = 0; \
1025  } \
1026  } while (0)
1027 
1028 #endif /* included_vec_h */
1029 
1030 
1031 /*
1032  * fd.io coding-style-patch-verification: ON
1033  *
1034  * Local Variables:
1035  * eval: (c-set-style "gnu")
1036  * End:
1037  */
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.