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