src/vppinfra/vec.h

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /*
  16   Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
  17
  18   Permission is hereby granted, free of charge, to any person obtaining
  19   a copy of this software and associated documentation files (the
  20   "Software"), to deal in the Software without restriction, including
  21   without limitation the rights to use, copy, modify, merge, publish,
  22   distribute, sublicense, and/or sell copies of the Software, and to
  23   permit persons to whom the Software is furnished to do so, subject to
  24   the following conditions:
  25
  26   The above copyright notice and this permission notice shall be
  27   included in all copies or substantial portions of the Software.
  28
  29   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  30   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  31   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  32   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  33   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  34   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  35   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  36 */
  37
  38 #ifndef included_vec_h
  39 #define included_vec_h
  40
  41 #include <vppinfra/clib.h>      /* word, etc */
  42 #include <vppinfra/mem.h>       /* clib_mem_free */
  43 #include <vppinfra/string.h>    /* memcpy, memmove */
  44 #include <vppinfra/vec_bootstrap.h>
  45
  46 /** \file
  47
  48    CLIB vectors are ubiquitous dynamically resized arrays with by user
  49    defined "headers".  Many CLIB data structures (e.g. hash, heap,
  50    pool) are vectors with various different headers.
  51
  52    The memory layout looks like this:
  53
  54 ~~~~~~~~
  55                     user header (aligned to uword boundary)
  56                     vector length: number of elements
  57    user's pointer-> vector element #0
  58                     vector element #1
  59                     ...
  60 ~~~~~~~~
  61
  62    The user pointer contains the address of vector element # 0.  Null
  63    pointer vectors are valid and mean a zero length vector.
  64
  65    You can reset the length of an allocated vector to zero via the
  66    vec_reset_length(v) macro, or by setting the vector length field to
  67    zero (e.g. _vec_len (v) = 0). Vec_reset_length(v) preferred: it
  68    understands Null pointers.
  69
  70    Typically, the header is not present.  Headers allow for other
  71    data structures to be built atop CLIB vectors.
  72
  73    Users may specify the alignment for first data element of a vector
  74    via the vec_*_aligned macros.
  75
  76    Vector elements can be any C type e.g. (int, double, struct bar).
  77    This is also true for data types built atop vectors (e.g. heap,
  78    pool, etc.).
  79
  80    Many macros have \_a variants supporting alignment of vector elements
  81    and \_h variants supporting non-zero-length vector headers. The \_ha
  82    variants support both.  Additionally cacheline alignment within a
  83    vector element structure can be specified using the
  84    CLIB_CACHE_LINE_ALIGN_MARK() macro.
  85
  86    Standard programming error: memorize a pointer to the ith element
  87    of a vector then expand it. Vectors expand by 3/2, so such code
  88    may appear to work for a period of time. Memorize vector indices
  89    which are invariant.
  90  */
  91
  92 /** \brief Low-level resize allocation function, usually not called directly
  93
  94     @param v pointer to a vector
  95     @param length_increment length increment in elements
  96     @param data_bytes requested size in bytes
  97     @param header_bytes header size in bytes (may be zero)
  98     @param data_align alignment (may be zero)
  99     @param numa_id numa id (may be zero)
 100     @return v_prime pointer to resized vector, may or may not equal v
 101 */
 102 void *vec_resize_allocate_memory (void *v,
 103                                   word length_increment,
 104                                   uword data_bytes,
 105                                   uword header_bytes, uword data_align,
 106                                   uword numa_id);
 107
 108 /** \brief Low-level vector resize function, usually not called directly
 109
 110     @param v pointer to a vector
 111     @param length_increment length increment in elements
 112     @param data_bytes requested size in bytes
 113     @param header_bytes header size in bytes (may be zero)
 114     @param data_align alignment (may be zero)
 115     @param numa_id (may be ~0)
 116     @return v_prime pointer to resized vector, may or may not equal v
 117 */
 118
 119 #define _vec_resize_numa(V,L,DB,HB,A,S)                                 \
 120 ({                                                                      \
 121   __typeof__ ((V)) _V;                                                  \
 122   _V = _vec_resize_inline((void *)V,L,DB,HB,clib_max((__alignof__((V)[0])),(A)),(S)); \
 123   _V;                                                                   \
 124 })
 125
 126 #define _vec_resize(V,L,DB,HB,A)  \
 127   _vec_resize_numa(V,L,DB,HB,A,VEC_NUMA_UNSPECIFIED)
 128
 129 always_inline void *
 130 _vec_resize_inline (void *v,
 131                     word length_increment,
 132                     uword data_bytes, uword header_bytes, uword data_align,
 133                     uword numa_id)
 134 {
 135   vec_header_t *vh = _vec_find (v);
 136   uword new_data_bytes, aligned_header_bytes;
 137   void *oldheap;
 138
 139   aligned_header_bytes = vec_header_bytes (header_bytes);
 140
 141   new_data_bytes = data_bytes + aligned_header_bytes;
 142
 143   if (PREDICT_TRUE (v != 0))
 144     {
 145       void *p = v - aligned_header_bytes;
 146
 147       if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
 148         {
 149           oldheap = clib_mem_get_per_cpu_heap ();
 150           clib_mem_set_per_cpu_heap (clib_mem_get_per_numa_heap (numa_id));
 151         }
 152
 153       /* Vector header must start heap object. */
 154       ASSERT (clib_mem_is_heap_object (p));
 155
 156       /* Typically we'll not need to resize. */
 157       if (new_data_bytes <= clib_mem_size (p))
 158         {
 159           CLIB_MEM_UNPOISON (v, data_bytes);
 160           vh->len += length_increment;
 161           if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
 162             clib_mem_set_per_cpu_heap (oldheap);
 163           return v;
 164         }
 165       if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
 166         clib_mem_set_per_cpu_heap (oldheap);
 167     }
 168
 169   /* Slow path: call helper function. */
 170   return vec_resize_allocate_memory (v, length_increment, data_bytes,
 171                                      header_bytes,
 172                                      clib_max (sizeof (vec_header_t),
 173                                                data_align), numa_id);
 174 }
 175
 176 /** \brief Determine if vector will resize with next allocation
 177
 178     @param v pointer to a vector
 179     @param length_increment length increment in elements
 180     @param data_bytes requested size in bytes
 181     @param header_bytes header size in bytes (may be zero)
 182     @param data_align alignment (may be zero)
 183     @return 1 if vector will resize 0 otherwise
 184 */
 185
 186 always_inline int
 187 _vec_resize_will_expand (void *v,
 188                          word length_increment,
 189                          uword data_bytes, uword header_bytes,
 190                          uword data_align)
 191 {
 192   uword new_data_bytes, aligned_header_bytes;
 193
 194   aligned_header_bytes = vec_header_bytes (header_bytes);
 195
 196   new_data_bytes = data_bytes + aligned_header_bytes;
 197
 198   if (PREDICT_TRUE (v != 0))
 199     {
 200       void *p = v - aligned_header_bytes;
 201
 202       /* Vector header must start heap object. */
 203       ASSERT (clib_mem_is_heap_object (p));
 204
 205       /* Typically we'll not need to resize. */
 206       if (new_data_bytes <= clib_mem_size (p))
 207         return 0;
 208     }
 209   return 1;
 210 }
 211
 212 /** \brief Determine if vector will resize with next allocation
 213
 214     @param V pointer to a vector
 215     @param N number of elements to add
 216     @return 1 if vector will resize 0 otherwise
 217 */
 218
 219 #define vec_resize_will_expand(V, N)                                          \
 220   ({                                                                          \
 221     word _v (n) = (N);                                                        \
 222     word _v (l) = vec_len (V);                                                \
 223     _vec_resize_will_expand ((V), _v (n),                                     \
 224                              (_v (l) + _v (n)) * sizeof ((V)[0]), 0, 0);      \
 225   })
 226
 227 /** \brief Predicate function, says whether the supplied vector is a clib heap
 228     object (general version).
 229
 230     @param v pointer to a vector
 231     @param header_bytes vector header size in bytes (may be zero)
 232     @return 0 or 1
 233 */
 234 uword clib_mem_is_vec_h (void *v, uword header_bytes);
 235
 236
 237 /** \brief Predicate function, says whether the supplied vector is a clib heap
 238     object
 239
 240     @param v pointer to a vector
 241     @return 0 or 1
 242 */
 243 always_inline uword
 244 clib_mem_is_vec (void *v)
 245 {
 246   return clib_mem_is_vec_h (v, 0);
 247 }
 248
 249 /* Local variable naming macro (prevents collisions with other macro naming). */
 250 #define _v(var) _vec_##var
 251
 252 /** \brief Resize a vector (general version).
 253    Add N elements to end of given vector V, return pointer to start of vector.
 254    Vector will have room for H header bytes and will have user's data aligned
 255    at alignment A (rounded to next power of 2).
 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     @param S numa_id (may be zero)
 262     @return V (value-result macro parameter)
 263 */
 264
 265 #define vec_resize_has(V,N,H,A,S)                               \
 266 do {                                                            \
 267   word _v(n) = (N);                                             \
 268   word _v(l) = vec_len (V);                                     \
 269   V = _vec_resize_numa ((V), _v(n),                           \
 270                           (_v(l) + _v(n)) * sizeof ((V)[0]),    \
 271                           (H), (A),(S));                        \
 272 } while (0)
 273
 274 /** \brief Resize a vector (less general version).
 275    Add N elements to end of given vector V, return pointer to start of vector.
 276    Vector will have room for H header bytes and will have user's data aligned
 277    at alignment A (rounded to next power of 2).
 278
 279     @param V pointer to a vector
 280     @param N number of elements to add
 281     @param H header size in bytes (may be zero)
 282     @param A alignment (may be zero)
 283     @return V (value-result macro parameter)
 284 */
 285 #define vec_resize_ha(V,N,H,A) vec_resize_has(V,N,H,A,VEC_NUMA_UNSPECIFIED)
 286
 287 /** \brief Resize a vector (no header, unspecified alignment)
 288    Add N elements to end of given vector V, return pointer to start of vector.
 289    Vector will have room for H header bytes and will have user's data aligned
 290    at alignment A (rounded to next power of 2).
 291
 292     @param V pointer to a vector
 293     @param N number of elements to add
 294     @return V (value-result macro parameter)
 295 */
 296 #define vec_resize(V,N)     vec_resize_ha(V,N,0,0)
 297
 298 /** \brief Resize a vector (no header, alignment specified).
 299    Add N elements to end of given vector V, return pointer to start of vector.
 300    Vector will have room for H header bytes and will have user's data aligned
 301    at alignment A (rounded to next power of 2).
 302
 303     @param V pointer to a vector
 304     @param N number of elements to add
 305     @param A alignment (may be zero)
 306     @return V (value-result macro parameter)
 307 */
 308
 309 #define vec_resize_aligned(V,N,A) vec_resize_ha(V,N,0,A)
 310
 311 /** \brief Allocate space for N more elements
 312
 313     @param V pointer to a vector
 314     @param N number of elements to add
 315     @param H header size in bytes (may be zero)
 316     @param A alignment (may be zero)
 317     @return V (value-result macro parameter)
 318 */
 319
 320 #define vec_alloc_ha(V,N,H,A)                   \
 321 do {                                            \
 322     uword _v(l) = vec_len (V);                  \
 323     vec_resize_ha (V, N, H, A);                 \
 324     _vec_len (V) = _v(l);                       \
 325 } while (0)
 326
 327 /** \brief Allocate space for N more elements
 328     (no header, unspecified alignment)
 329
 330     @param V pointer to a vector
 331     @param N number of elements to add
 332     @return V (value-result macro parameter)
 333 */
 334 #define vec_alloc(V,N) vec_alloc_ha(V,N,0,0)
 335
 336 /** \brief Allocate space for N more elements (no header, given alignment)
 337     @param V pointer to a vector
 338     @param N number of elements to add
 339     @param A alignment (may be zero)
 340     @return V (value-result macro parameter)
 341 */
 342
 343 #define vec_alloc_aligned(V,N,A) vec_alloc_ha(V,N,0,A)
 344
 345 /** \brief Create new vector of given type and length (general version).
 346     @param T type of elements in new vector
 347     @param N number of elements to add
 348     @param H header size in bytes (may be zero)
 349     @param A alignment (may be zero)
 350     @return V new vector
 351 */
 352 #define vec_new_ha(T,N,H,A)                                             \
 353 ({                                                                      \
 354   word _v(n) = (N);                                                     \
 355   (T *)_vec_resize ((T *) 0, _v(n), _v(n) * sizeof (T), (H), (A));      \
 356 })
 357
 358 /** \brief Create new vector of given type and length
 359     (unspecified alignment, no header).
 360
 361     @param T type of elements in new vector
 362     @param N number of elements to add
 363     @return V new vector
 364 */
 365 #define vec_new(T,N)           vec_new_ha(T,N,0,0)
 366 /** \brief Create new vector of given type and length
 367     (alignment specified, no header).
 368
 369     @param T type of elements in new vector
 370     @param N number of elements to add
 371     @param A alignment (may be zero)
 372     @return V new vector
 373 */
 374 #define vec_new_aligned(T,N,A) vec_new_ha(T,N,0,A)
 375
 376 /** \brief Free vector's memory (general version)
 377
 378     @param V pointer to a vector
 379     @param H size of header in bytes
 380     @return V (value-result parameter, V=0)
 381 */
 382 #define vec_free_h(V, H)                                                      \
 383   do                                                                          \
 384     {                                                                         \
 385       if (V)                                                                  \
 386         {                                                                     \
 387           clib_mem_free (vec_header ((V)));                                   \
 388           V = 0;                                                              \
 389         }                                                                     \
 390     }                                                                         \
 391   while (0)
 392
 393 /** \brief Free vector's memory (no header).
 394     @param V pointer to a vector
 395     @return V (value-result parameter, V=0)
 396 */
 397 #define vec_free(V) vec_free_h(V,0)
 398
 399 void vec_free_not_inline (void *v);
 400
 401 /**\brief Free vector user header (syntactic sugar)
 402    @param h vector header
 403    @void
 404 */
 405 #define vec_free_header(h) clib_mem_free (h)
 406
 407 /** \brief Return copy of vector (general version).
 408
 409     @param V pointer to a vector
 410     @param H size of header in bytes
 411     @param A alignment (may be zero)
 412     @param S numa (may be VEC_NUMA_UNSPECIFIED)
 413
 414     @return Vdup copy of vector
 415 */
 416
 417 #define vec_dup_ha_numa(V,H,A,S)                      \
 418 ({                                                      \
 419   __typeof__ ((V)[0]) * _v(v) = 0;                      \
 420   uword _v(l) = vec_len (V);                            \
 421   if (_v(l) > 0)                                        \
 422     {                                                   \
 423       vec_resize_has (_v(v), _v(l), (H), (A), (S));     \
 424       clib_memcpy_fast (_v(v), (V), _v(l) * sizeof ((V)[0]));\
 425     }                                                   \
 426   _v(v);                                                \
 427 })
 428
 429 /** \brief Return copy of vector (VEC_NUMA_UNSPECIFIED).
 430
 431     @param V pointer to a vector
 432     @param H size of header in bytes
 433     @param A alignment (may be zero)
 434
 435     @return Vdup copy of vector
 436 */
 437 #define vec_dup_ha(V,H,A) \
 438   vec_dup_ha_numa(V,H,A,VEC_NUMA_UNSPECIFIED)
 439
 440
 441 /** \brief Return copy of vector (no header, no alignment)
 442
 443     @param V pointer to a vector
 444     @return Vdup copy of vector
 445 */
 446 #define vec_dup(V) vec_dup_ha(V,0,0)
 447
 448 /** \brief Return copy of vector (no header, alignment specified).
 449
 450     @param V pointer to a vector
 451     @param A alignment (may be zero)
 452
 453     @return Vdup copy of vector
 454 */
 455 #define vec_dup_aligned(V,A) vec_dup_ha(V,0,A)
 456
 457 /** \brief Copy a vector, memcpy wrapper. Assumes sizeof(SRC[0]) ==
 458     sizeof(DST[0])
 459
 460     @param DST destination
 461     @param SRC source
 462 */
 463 #define vec_copy(DST,SRC) clib_memcpy_fast (DST, SRC, vec_len (DST) * \
 464                                        sizeof ((DST)[0]))
 465
 466 /** \brief Clone a vector. Make a new vector with the
 467     same size as a given vector but possibly with a different type.
 468
 469     @param NEW_V pointer to new vector
 470     @param OLD_V pointer to old vector
 471 */
 472 #define vec_clone(NEW_V,OLD_V)                                                  \
 473 do {                                                                            \
 474   (NEW_V) = 0;                                                                  \
 475   (NEW_V) = _vec_resize ((NEW_V), vec_len (OLD_V),                              \
 476                          vec_len (OLD_V) * sizeof ((NEW_V)[0]), (0), (0));      \
 477 } while (0)
 478
 479 /** \brief Make sure vector is long enough for given index (general version).
 480
 481     @param V (possibly NULL) pointer to a vector.
 482     @param I vector index which will be valid upon return
 483     @param H header size in bytes (may be zero)
 484     @param A alignment (may be zero)
 485     @param N numa_id (may be zero)
 486     @return V (value-result macro parameter)
 487 */
 488
 489 #define vec_validate_han(V,I,H,A,N)                                     \
 490 do {                                                                    \
 491   void *oldheap;                                                        \
 492   STATIC_ASSERT(A==0 || ((A % sizeof(V[0]))==0)                         \
 493         || ((sizeof(V[0]) % A) == 0),                                   \
 494     "vector validate aligned on incorrectly sized object");             \
 495   word _v(i) = (I);                                                     \
 496   word _v(l) = vec_len (V);                                             \
 497   if (_v(i) >= _v(l))                                                   \
 498     {                                                                   \
 499       /* switch to the per-numa heap if directed */                   \
 500       if (PREDICT_FALSE(N != VEC_NUMA_UNSPECIFIED))                   \
 501         {                                                               \
 502            oldheap = clib_mem_get_per_cpu_heap();                       \
 503            clib_mem_set_per_cpu_heap (clib_mem_get_per_numa_heap(N)); \
 504         }                                                               \
 505                                                                         \
 506       vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A));               \
 507       /* Must zero new space since user may have previously             \
 508          used e.g. _vec_len (v) -= 10 */                                \
 509       clib_memset ((V) + _v(l), 0,                                      \
 510                    (1 + (_v(i) - _v(l))) * sizeof ((V)[0]));            \
 511       /* Switch back to the global heap */                              \
 512       if (PREDICT_FALSE (N != VEC_NUMA_UNSPECIFIED))                  \
 513         clib_mem_set_per_cpu_heap (oldheap);                            \
 514     }                                                                   \
 515 } while (0)
 516
 517 #define vec_validate_ha(V,I,H,A) vec_validate_han(V,I,H,A,VEC_NUMA_UNSPECIFIED)
 518
 519 /** \brief Make sure vector is long enough for given index
 520     (no header, unspecified alignment)
 521
 522     @param V (possibly NULL) pointer to a vector.
 523     @param I vector index which will be valid upon return
 524     @return V (value-result macro parameter)
 525 */
 526 #define vec_validate(V,I)           vec_validate_ha(V,I,0,0)
 527
 528 /** \brief Make sure vector is long enough for given index
 529     (no header, specified alignment)
 530
 531     @param V (possibly NULL) pointer to a vector.
 532     @param I vector index which will be valid upon return
 533     @param A alignment (may be zero)
 534     @return V (value-result macro parameter)
 535 */
 536
 537 #define vec_validate_aligned(V,I,A) vec_validate_ha(V,I,0,A)
 538
 539 /** \brief Make sure vector is long enough for given index
 540     and initialize empty space (general version)
 541
 542     @param V (possibly NULL) pointer to a vector.
 543     @param I vector index which will be valid upon return
 544     @param INIT initial value (can be a complex expression!)
 545     @param H header size in bytes (may be zero)
 546     @param A alignment (may be zero)
 547     @return V (value-result macro parameter)
 548 */
 549 #define vec_validate_init_empty_ha(V,I,INIT,H,A)                \
 550 do {                                                            \
 551   word _v(i) = (I);                                             \
 552   word _v(l) = vec_len (V);                                     \
 553   if (_v(i) >= _v(l))                                           \
 554     {                                                           \
 555       vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A));       \
 556       while (_v(l) <= _v(i))                                    \
 557         {                                                       \
 558           (V)[_v(l)] = (INIT);                                  \
 559           _v(l)++;                                              \
 560         }                                                       \
 561     }                                                           \
 562 } while (0)
 563
 564 /** \brief Make sure vector is long enough for given index
 565     and initialize empty space (no header, unspecified alignment)
 566
 567     @param V (possibly NULL) pointer to a vector.
 568     @param I vector index which will be valid upon return
 569     @param INIT initial value (can be a complex expression!)
 570     @return V (value-result macro parameter)
 571 */
 572
 573 #define vec_validate_init_empty(V,I,INIT) \
 574   vec_validate_init_empty_ha(V,I,INIT,0,0)
 575
 576 /** \brief Make sure vector is long enough for given index
 577     and initialize empty space (no header, alignment alignment)
 578
 579     @param V (possibly NULL) pointer to a vector.
 580     @param I vector index which will be valid upon return
 581     @param INIT initial value (can be a complex expression!)
 582     @param A alignment (may be zero)
 583     @return V (value-result macro parameter)
 584 */
 585 #define vec_validate_init_empty_aligned(V,I,INIT,A) \
 586   vec_validate_init_empty_ha(V,I,INIT,0,A)
 587
 588 /** \brief Add 1 element to end of vector (general version).
 589
 590     @param V pointer to a vector
 591     @param E element to add
 592     @param H header size in bytes (may be zero)
 593     @param A alignment (may be zero)
 594     @return V (value-result macro parameter)
 595 */
 596 #define vec_add1_ha(V,E,H,A)                                            \
 597 do {                                                                    \
 598   word _v(l) = vec_len (V);                                             \
 599   V = _vec_resize ((V), 1, (_v(l) + 1) * sizeof ((V)[0]), (H), (A));    \
 600   (V)[_v(l)] = (E);                                                     \
 601 } while (0)
 602
 603 /** \brief Add 1 element to end of vector (unspecified alignment).
 604
 605     @param V pointer to a vector
 606     @param E element to add
 607     @return V (value-result macro parameter)
 608 */
 609 #define vec_add1(V,E)           vec_add1_ha(V,E,0,0)
 610
 611 /** \brief Add 1 element to end of vector (alignment specified).
 612
 613     @param V pointer to a vector
 614     @param E element to add
 615     @param A alignment (may be zero)
 616     @return V (value-result macro parameter)
 617 */
 618 #define vec_add1_aligned(V,E,A) vec_add1_ha(V,E,0,A)
 619
 620 /** \brief Add N elements to end of vector V,
 621     return pointer to new elements in P. (general version)
 622
 623     @param V pointer to a vector
 624     @param P pointer to new vector element(s)
 625     @param N number of elements to add
 626     @param H header size in bytes (may be zero)
 627     @param A alignment (may be zero)
 628     @return V and P (value-result macro parameters)
 629 */
 630 #define vec_add2_ha(V,P,N,H,A)                                                  \
 631 do {                                                                            \
 632   word _v(n) = (N);                                                             \
 633   word _v(l) = vec_len (V);                                                     \
 634   V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A));    \
 635   P = (V) + _v(l);                                                              \
 636 } while (0)
 637
 638 /** \brief Add N elements to end of vector V,
 639     return pointer to new elements in P. (no header, unspecified alignment)
 640
 641     @param V pointer to a vector
 642     @param P pointer to new vector element(s)
 643     @param N number of elements to add
 644     @return V and P (value-result macro parameters)
 645 */
 646
 647 #define vec_add2(V,P,N)           vec_add2_ha(V,P,N,0,0)
 648
 649 /** \brief Add N elements to end of vector V,
 650     return pointer to new elements in P. (no header, alignment specified)
 651
 652     @param V pointer to a vector
 653     @param P pointer to new vector element(s)
 654     @param N number of elements to add
 655     @param A alignment (may be zero)
 656     @return V and P (value-result macro parameters)
 657 */
 658
 659 #define vec_add2_aligned(V,P,N,A) vec_add2_ha(V,P,N,0,A)
 660
 661 /** \brief Add N elements to end of vector V (general version)
 662
 663     @param V pointer to a vector
 664     @param E pointer to element(s) to add
 665     @param N number of elements to add
 666     @param H header size in bytes (may be zero)
 667     @param A alignment (may be zero)
 668     @return V (value-result macro parameter)
 669 */
 670 #define vec_add_ha(V, E, N, H, A)                                             \
 671   do                                                                          \
 672     {                                                                         \
 673       word _v (n) = (N);                                                      \
 674       if (PREDICT_TRUE (_v (n) > 0))                                          \
 675         {                                                                     \
 676           word _v (l) = vec_len (V);                                          \
 677           V = _vec_resize ((V), _v (n), (_v (l) + _v (n)) * sizeof ((V)[0]),  \
 678                            (H), (A));                                         \
 679           clib_memcpy_fast ((V) + _v (l), (E), _v (n) * sizeof ((V)[0]));     \
 680         }                                                                     \
 681     }                                                                         \
 682   while (0)
 683
 684 /** \brief Add N elements to end of vector V (no header, unspecified alignment)
 685
 686     @param V pointer to a vector
 687     @param E pointer to element(s) to add
 688     @param N number of elements to add
 689     @return V (value-result macro parameter)
 690 */
 691 #define vec_add(V,E,N)           vec_add_ha(V,E,N,0,0)
 692
 693 /** \brief Add N elements to end of vector V (no header, specified alignment)
 694
 695     @param V pointer to a vector
 696     @param E pointer to element(s) to add
 697     @param N number of elements to add
 698     @param A alignment (may be zero)
 699     @return V (value-result macro parameter)
 700 */
 701 #define vec_add_aligned(V,E,N,A) vec_add_ha(V,E,N,0,A)
 702
 703 /** \brief Returns last element of a vector and decrements its length
 704
 705     @param V pointer to a vector
 706     @return E element removed from the end of the vector
 707 */
 708 #define vec_pop(V)                              \
 709 ({                                              \
 710   uword _v(l) = vec_len (V);                    \
 711   ASSERT (_v(l) > 0);                           \
 712   _v(l) -= 1;                                   \
 713   _vec_len (V) = _v (l);                        \
 714   (V)[_v(l)];                                   \
 715 })
 716
 717 /** \brief Set E to the last element of a vector, decrement vector length
 718     @param V pointer to a vector
 719     @param E pointer to the last vector element
 720     @return E element removed from the end of the vector
 721     (value-result macro parameter
 722 */
 723
 724 #define vec_pop2(V,E)                           \
 725 ({                                              \
 726   uword _v(l) = vec_len (V);                    \
 727   if (_v(l) > 0) (E) = vec_pop (V);             \
 728   _v(l) > 0;                                    \
 729 })
 730
 731 /** \brief Insert N vector elements starting at element M,
 732     initialize new elements (general version).
 733
 734     @param V (possibly NULL) pointer to a vector.
 735     @param N number of elements to insert
 736     @param M insertion point
 737     @param INIT initial value (can be a complex expression!)
 738     @param H header size in bytes (may be zero)
 739     @param A alignment (may be zero)
 740     @return V (value-result macro parameter)
 741 */
 742 #define vec_insert_init_empty_ha(V,N,M,INIT,H,A)        \
 743 do {                                                    \
 744   word _v(l) = vec_len (V);                             \
 745   word _v(n) = (N);                                     \
 746   word _v(m) = (M);                                     \
 747   V = _vec_resize ((V),                                 \
 748                    _v(n),                               \
 749                    (_v(l) + _v(n))*sizeof((V)[0]),      \
 750                    (H), (A));                           \
 751   ASSERT (_v(m) <= _v(l));                              \
 752   memmove ((V) + _v(m) + _v(n),                         \
 753            (V) + _v(m),                                 \
 754            (_v(l) - _v(m)) * sizeof ((V)[0]));          \
 755   clib_memset  ((V) + _v(m), INIT, _v(n) * sizeof ((V)[0]));    \
 756 } while (0)
 757
 758 /** \brief Insert N vector elements starting at element M,
 759     initialize new elements to zero (general version)
 760
 761     @param V (possibly NULL) pointer to a vector.
 762     @param N number of elements to insert
 763     @param M insertion point
 764     @param H header size in bytes (may be zero)
 765     @param A alignment (may be zero)
 766     @return V (value-result macro parameter)
 767 */
 768 #define vec_insert_ha(V,N,M,H,A)    vec_insert_init_empty_ha(V,N,M,0,H,A)
 769
 770 /** \brief Insert N vector elements starting at element M,
 771     initialize new elements to zero (no header, unspecified alignment)
 772
 773     @param V (possibly NULL) pointer to a vector.
 774     @param N number of elements to insert
 775     @param M insertion point
 776     @return V (value-result macro parameter)
 777 */
 778 #define vec_insert(V,N,M)           vec_insert_ha(V,N,M,0,0)
 779
 780 /** \brief Insert N vector elements starting at element M,
 781     initialize new elements to zero (no header, alignment specified)
 782
 783     @param V (possibly NULL) pointer to a vector.
 784     @param N number of elements to insert
 785     @param M insertion point
 786     @param A alignment (may be zero)
 787     @return V (value-result macro parameter)
 788 */
 789 #define vec_insert_aligned(V,N,M,A) vec_insert_ha(V,N,M,0,A)
 790
 791 /** \brief Insert N vector elements starting at element M,
 792     initialize new elements (no header, unspecified alignment)
 793
 794     @param V (possibly NULL) pointer to a vector.
 795     @param N number of elements to insert
 796     @param M insertion point
 797     @param INIT initial value (can be a complex expression!)
 798     @return V (value-result macro parameter)
 799 */
 800
 801 #define vec_insert_init_empty(V,N,M,INIT) \
 802   vec_insert_init_empty_ha(V,N,M,INIT,0,0)
 803 /* Resize vector by N elements starting from element M, initialize new elements to INIT (alignment specified, no header). */
 804
 805 /** \brief Insert N vector elements starting at element M,
 806     initialize new elements (no header, specified alignment)
 807
 808     @param V (possibly NULL) pointer to a vector.
 809     @param N number of elements to insert
 810     @param M insertion point
 811     @param INIT initial value (can be a complex expression!)
 812     @param A alignment (may be zero)
 813     @return V (value-result macro parameter)
 814 */
 815 #define vec_insert_init_empty_aligned(V,N,M,INIT,A) \
 816   vec_insert_init_empty_ha(V,N,M,INIT,0,A)
 817
 818 /** \brief Insert N vector elements starting at element M,
 819     insert given elements (general version)
 820
 821     @param V (possibly NULL) pointer to a vector.
 822     @param E element(s) to insert
 823     @param N number of elements to insert
 824     @param M insertion point
 825     @param H header size in bytes (may be zero)
 826     @param A alignment (may be zero)
 827     @return V (value-result macro parameter)
 828 */
 829
 830 #define vec_insert_elts_ha(V, E, N, M, H, A)                                  \
 831   do                                                                          \
 832     {                                                                         \
 833       word _v (n) = (N);                                                      \
 834       if (PREDICT_TRUE (_v (n) > 0))                                          \
 835         {                                                                     \
 836           word _v (l) = vec_len (V);                                          \
 837           word _v (m) = (M);                                                  \
 838           V = _vec_resize ((V), _v (n), (_v (l) + _v (n)) * sizeof ((V)[0]),  \
 839                            (H), (A));                                         \
 840           ASSERT (_v (m) <= _v (l));                                          \
 841           memmove ((V) + _v (m) + _v (n), (V) + _v (m),                       \
 842                    (_v (l) - _v (m)) * sizeof ((V)[0]));                      \
 843           clib_memcpy_fast ((V) + _v (m), (E), _v (n) * sizeof ((V)[0]));     \
 844         }                                                                     \
 845     }                                                                         \
 846   while (0)
 847
 848 /** \brief Insert N vector elements starting at element M,
 849     insert given elements (no header, unspecified alignment)
 850
 851     @param V (possibly NULL) pointer to a vector.
 852     @param E element(s) to insert
 853     @param N number of elements to insert
 854     @param M insertion point
 855     @return V (value-result macro parameter)
 856 */
 857 #define vec_insert_elts(V,E,N,M)           vec_insert_elts_ha(V,E,N,M,0,0)
 858
 859 /** \brief Insert N vector elements starting at element M,
 860     insert given elements (no header, specified alignment)
 861
 862     @param V (possibly NULL) pointer to a vector.
 863     @param E element(s) to insert
 864     @param N number of elements to insert
 865     @param M insertion point
 866     @param A alignment (may be zero)
 867     @return V (value-result macro parameter)
 868 */
 869 #define vec_insert_elts_aligned(V,E,N,M,A) vec_insert_elts_ha(V,E,N,M,0,A)
 870
 871 /** \brief Delete N elements starting at element M
 872
 873     @param V pointer to a vector
 874     @param N number of elements to delete
 875     @param M first element to delete
 876     @return V (value-result macro parameter)
 877 */
 878 #define vec_delete(V,N,M)                                       \
 879 do {                                                            \
 880   word _v(l) = vec_len (V);                                     \
 881   word _v(n) = (N);                                             \
 882   word _v(m) = (M);                                             \
 883   /* Copy over deleted elements. */                             \
 884   if (_v(l) - _v(n) - _v(m) > 0)                                \
 885     memmove ((V) + _v(m), (V) + _v(m) + _v(n),                  \
 886              (_v(l) - _v(n) - _v(m)) * sizeof ((V)[0]));        \
 887   /* Zero empty space at end (for future re-allocation). */     \
 888   if (_v(n) > 0)                                                \
 889     clib_memset ((V) + _v(l) - _v(n), 0, _v(n) * sizeof ((V)[0]));      \
 890   _vec_len (V) -= _v(n);                                        \
 891   CLIB_MEM_POISON(vec_end(V), _v(n) * sizeof ((V)[0]));         \
 892 } while (0)
 893
 894 /** \brief Delete the element at index I
 895
 896     @param V pointer to a vector
 897     @param I index to delete
 898 */
 899 #define vec_del1(v,i)                           \
 900 do {                                            \
 901   uword _vec_del_l = _vec_len (v) - 1;          \
 902   uword _vec_del_i = (i);                       \
 903   if (_vec_del_i < _vec_del_l)                  \
 904     (v)[_vec_del_i] = (v)[_vec_del_l];          \
 905   _vec_len (v) = _vec_del_l;                    \
 906   CLIB_MEM_POISON(vec_end(v), sizeof ((v)[0])); \
 907 } while (0)
 908
 909 /** \brief Append v2 after v1. Result in v1.
 910     @param V1 target vector
 911     @param V2 vector to append
 912 */
 913
 914 #define vec_append(v1, v2)                                                    \
 915   do                                                                          \
 916     {                                                                         \
 917       uword _v (l1) = vec_len (v1);                                           \
 918       uword _v (l2) = vec_len (v2);                                           \
 919                                                                               \
 920       if (PREDICT_TRUE (_v (l2) > 0))                                         \
 921         {                                                                     \
 922           v1 = _vec_resize ((v1), _v (l2),                                    \
 923                             (_v (l1) + _v (l2)) * sizeof ((v1)[0]), 0, 0);    \
 924           clib_memcpy_fast ((v1) + _v (l1), (v2),                             \
 925                             _v (l2) * sizeof ((v2)[0]));                      \
 926         }                                                                     \
 927     }                                                                         \
 928   while (0)
 929
 930 /** \brief Append v2 after v1. Result in v1. Specified alignment.
 931     @param V1 target vector
 932     @param V2 vector to append
 933     @param align required alignment
 934 */
 935
 936 #define vec_append_aligned(v1, v2, align)                                     \
 937   do                                                                          \
 938     {                                                                         \
 939       uword _v (l1) = vec_len (v1);                                           \
 940       uword _v (l2) = vec_len (v2);                                           \
 941                                                                               \
 942       if (PREDICT_TRUE (_v (l2) > 0))                                         \
 943         {                                                                     \
 944           v1 = _vec_resize (                                                  \
 945             (v1), _v (l2), (_v (l1) + _v (l2)) * sizeof ((v1)[0]), 0, align); \
 946           clib_memcpy_fast ((v1) + _v (l1), (v2),                             \
 947                             _v (l2) * sizeof ((v2)[0]));                      \
 948         }                                                                     \
 949     }                                                                         \
 950   while (0)
 951
 952 /** \brief Prepend v2 before v1. Result in v1.
 953     @param V1 target vector
 954     @param V2 vector to prepend
 955 */
 956
 957 #define vec_prepend(v1, v2)                                                   \
 958   do                                                                          \
 959     {                                                                         \
 960       uword _v (l1) = vec_len (v1);                                           \
 961       uword _v (l2) = vec_len (v2);                                           \
 962                                                                               \
 963       if (PREDICT_TRUE (_v (l2) > 0))                                         \
 964         {                                                                     \
 965           v1 = _vec_resize ((v1), _v (l2),                                    \
 966                             (_v (l1) + _v (l2)) * sizeof ((v1)[0]), 0, 0);    \
 967           memmove ((v1) + _v (l2), (v1), _v (l1) * sizeof ((v1)[0]));         \
 968           clib_memcpy_fast ((v1), (v2), _v (l2) * sizeof ((v2)[0]));          \
 969         }                                                                     \
 970     }                                                                         \
 971   while (0)
 972
 973 /** \brief Prepend v2 before v1. Result in v1. Specified alignment
 974     @param V1 target vector
 975     @param V2 vector to prepend
 976     @param align required alignment
 977 */
 978
 979 #define vec_prepend_aligned(v1, v2, align)                                    \
 980   do                                                                          \
 981     {                                                                         \
 982       uword _v (l1) = vec_len (v1);                                           \
 983       uword _v (l2) = vec_len (v2);                                           \
 984                                                                               \
 985       if (PREDICT_TRUE (_v (l2) > 0))                                         \
 986         {                                                                     \
 987           v1 = _vec_resize (                                                  \
 988             (v1), _v (l2), (_v (l1) + _v (l2)) * sizeof ((v1)[0]), 0, align); \
 989           memmove ((v1) + _v (l2), (v1), _v (l1) * sizeof ((v1)[0]));         \
 990           clib_memcpy_fast ((v1), (v2), _v (l2) * sizeof ((v2)[0]));          \
 991         }                                                                     \
 992     }                                                                         \
 993   while (0)
 994
 995 /** \brief Zero all vector elements. Null-pointer tolerant.
 996     @param var Vector to zero
 997 */
 998 #define vec_zero(var)                                           \
 999 do {                                                            \
1000   if (var)                                                      \
1001     clib_memset ((var), 0, vec_len (var) * sizeof ((var)[0]));  \
1002 } while (0)
1003
1004 /** \brief Set all vector elements to given value. Null-pointer tolerant.
1005     @param v vector to set
1006     @param val value for each vector element
1007 */
1008 #define vec_set(v,val)                          \
1009 do {                                            \
1010   word _v(i);                                   \
1011   __typeof__ ((v)[0]) _val = (val);             \
1012   for (_v(i) = 0; _v(i) < vec_len (v); _v(i)++) \
1013     (v)[_v(i)] = _val;                          \
1014 } while (0)
1015
1016 #ifdef CLIB_UNIX
1017 #include <stdlib.h>             /* for qsort */
1018 #endif
1019
1020 /** \brief Compare two vectors, not NULL-pointer tolerant
1021
1022     @param v1 Pointer to a vector
1023     @param v2 Pointer to a vector
1024     @return 1 if equal, 0 if unequal
1025 */
1026 #define vec_is_equal(v1,v2) \
1027   (vec_len (v1) == vec_len (v2) && ! memcmp ((v1), (v2), vec_len (v1) * sizeof ((v1)[0])))
1028
1029 /** \brief Compare two vectors (only applicable to vectors of signed numbers).
1030    Used in qsort compare functions.
1031
1032     @param v1 Pointer to a vector
1033     @param v2 Pointer to a vector
1034     @return -1, 0, +1
1035 */
1036 #define vec_cmp(v1,v2)                                  \
1037 ({                                                      \
1038   word _v(i), _v(cmp), _v(l);                           \
1039   _v(l) = clib_min (vec_len (v1), vec_len (v2));        \
1040   _v(cmp) = 0;                                          \
1041   for (_v(i) = 0; _v(i) < _v(l); _v(i)++) {             \
1042     _v(cmp) = (v1)[_v(i)] - (v2)[_v(i)];                \
1043     if (_v(cmp))                                        \
1044       break;                                            \
1045   }                                                     \
1046   if (_v(cmp) == 0 && _v(l) > 0)                        \
1047     _v(cmp) = vec_len(v1) - vec_len(v2);                \
1048   (_v(cmp) < 0 ? -1 : (_v(cmp) > 0 ? +1 : 0));          \
1049 })
1050
1051 /** \brief Search a vector for the index of the entry that matches.
1052
1053     @param v Pointer to a vector
1054     @param E Entry to match
1055     @return index of match or ~0
1056 */
1057 #define vec_search(v,E)                                 \
1058 ({                                                      \
1059   word _v(i) = 0;                                       \
1060   while (_v(i) < vec_len(v))                            \
1061   {                                                     \
1062     if ((v)[_v(i)] == E)                                        \
1063       break;                                            \
1064     _v(i)++;                                            \
1065   }                                                     \
1066   if (_v(i) == vec_len(v))                              \
1067     _v(i) = ~0;                                         \
1068   _v(i);                                                \
1069 })
1070
1071 /** \brief Search a vector for the index of the entry that matches.
1072
1073     @param v Pointer to a vector
1074     @param E Pointer to entry to match
1075     @param fn Comparison function !0 => match
1076     @return index of match or ~0
1077 */
1078 #define vec_search_with_function(v,E,fn)                \
1079 ({                                                      \
1080   word _v(i) = 0;                                       \
1081   while (_v(i) < vec_len(v))                            \
1082   {                                                     \
1083     if (0 != fn(&(v)[_v(i)], (E)))                      \
1084       break;                                            \
1085     _v(i)++;                                            \
1086   }                                                     \
1087   if (_v(i) == vec_len(v))                              \
1088     _v(i) = ~0;                                         \
1089   _v(i);                                                \
1090 })
1091
1092 /** \brief Sort a vector using the supplied element comparison function
1093
1094     Does not depend on the underlying implementation to deal correctly
1095     with null, zero-long, or 1-long vectors
1096
1097     @param vec vector to sort
1098     @param f comparison function
1099 */
1100 #define vec_sort_with_function(vec,f)                           \
1101 do {                                                            \
1102   if (vec_len (vec) > 1)                                        \
1103     qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f));  \
1104 } while (0)
1105
1106 /** \brief Make a vector containing a NULL terminated c-string.
1107
1108     @param V (possibly NULL) pointer to a vector.
1109     @param S pointer to string buffer.
1110     @param L string length (NOT including the terminating NULL; a la strlen())
1111 */
1112 #define vec_validate_init_c_string(V, S, L)     \
1113   do {                                          \
1114     vec_reset_length (V);                       \
1115     vec_validate ((V), (L));                    \
1116     if ((S) && (L))                             \
1117         clib_memcpy_fast ((V), (S), (L));            \
1118     (V)[(L)] = 0;                               \
1119   } while (0)
1120
1121
1122 /** \brief Test whether a vector is a NULL terminated c-string.
1123
1124     @param V (possibly NULL) pointer to a vector.
1125     @return BOOLEAN indicating if the vector c-string is null terminated.
1126 */
1127 #define vec_c_string_is_terminated(V)                   \
1128   (((V) != 0) && (vec_len (V) != 0) && ((V)[vec_len ((V)) - 1] == 0))
1129
1130 /** \brief (If necessary) NULL terminate a vector containing a c-string.
1131
1132     @param V (possibly NULL) pointer to a vector.
1133     @return V (value-result macro parameter)
1134 */
1135 #define vec_terminate_c_string(V)               \
1136   do {                                          \
1137     u32 vl = vec_len ((V));                     \
1138     if (!vec_c_string_is_terminated(V))         \
1139       {                                         \
1140         vec_validate ((V), vl);                 \
1141         (V)[vl] = 0;                            \
1142       }                                         \
1143   } while (0)
1144
1145 #endif /* included_vec_h */
1146
1147
1148 /*
1149  * fd.io coding-style-patch-verification: ON
1150  *
1151  * Local Variables:
1152  * eval: (c-set-style "gnu")
1153  * End:
1154  */