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