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