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