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