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