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 (start of memory allocation)
  56                     padding
  57                     heap pointer (optional, only if default_heap == 0)
  58                     vector header: number of elements, header size
  59    user's pointer-> vector element #0
  60                     vector element #1
  61                     ...
  62 ~~~~~~~~
  63
  64    The user pointer contains the address of vector element # 0.  Null
  65    pointer vectors are valid and mean a zero length vector.
  66
  67    You can reset the length of an allocated vector to zero via the
  68    vec_reset_length(v) macro, or by setting the vector length field to
  69    zero (e.g. _vec_len (v) = 0). Vec_reset_length(v) preferred: it
  70    understands Null pointers.
  71
  72    Typically, the header is not present.  Headers allow for other
  73    data structures to be built atop CLIB vectors.
  74
  75    While users may specify the alignment for first data element of a vector
  76    via the vec_*_aligned macros that is typically not needed as alignment
  77    is set based on native alignment of the data structure used.
  78
  79    Vector elements can be any C type e.g. (int, double, struct bar).
  80    This is also true for data types built atop vectors (e.g. heap,
  81    pool, etc.).
  82
  83    Many macros have \_a variants supporting alignment of vector elements
  84    and \_h variants supporting non-zero-length vector headers. The \_ha
  85    variants support both.  Additionally cacheline alignment within a
  86    vector element structure can be specified using the
  87    CLIB_CACHE_LINE_ALIGN_MARK() macro.
  88
  89    Standard programming error: memorize a pointer to the ith element
  90    of a vector then expand it. Vectors expand by 3/2, so such code
  91    may appear to work for a period of time. Memorize vector indices
  92    which are invariant.
  93  */
  94
  95 /** \brief Low-level (re)allocation function, usually not called directly
  96
  97     @param v pointer to a vector
  98     @param n_elts requested number of elements
  99     @param elt_sz requested size of one element
 100     @param hdr_sz header size in bytes (may be zero)
 101     @param align alignment (may be zero)
 102     @return v_prime pointer to resized vector, may or may not equal v
 103 */
 104
 105 typedef struct
 106 {
 107   void *heap;
 108   u32 elt_sz;
 109   u16 hdr_sz;
 110   u16 align;
 111 } vec_attr_t;
 112
 113 void *_vec_alloc_internal (uword n_elts, const vec_attr_t *const attr);
 114 void *_vec_realloc_internal (void *v, uword n_elts,
 115                              const vec_attr_t *const attr);
 116 void *_vec_resize_internal (void *v, uword n_elts,
 117                             const vec_attr_t *const attr);
 118
 119 /* calculate minimum alignment out of data natural alignment and provided
 120  * value, should not be < VEC_MIN_ALIGN */
 121 static_always_inline uword
 122 __vec_align (uword data_align, uword configuered_align)
 123 {
 124   data_align = clib_max (data_align, configuered_align);
 125   ASSERT (count_set_bits (data_align) == 1);
 126   return clib_max (VEC_MIN_ALIGN, data_align);
 127 }
 128
 129 /* function used t o catch cases where vec_* macros on used on void * */
 130 static_always_inline uword
 131 __vec_elt_sz (uword elt_sz, int is_void)
 132 {
 133   /* vector macro operations on void * are not allowed */
 134   ASSERT (is_void == 0);
 135   return elt_sz;
 136 }
 137
 138 static_always_inline void
 139 _vec_update_pointer (void **vp, void *v)
 140 {
 141   /* avoid store if not needed */
 142   if (v != vp[0])
 143     vp[0] = v;
 144 }
 145
 146 static_always_inline void *
 147 vec_get_heap (void *v)
 148 {
 149   if (v == 0 || _vec_find (v)->default_heap == 1)
 150     return 0;
 151   return _vec_heap (v);
 152 }
 153
 154 static_always_inline uword
 155 vec_get_align (void *v)
 156 {
 157   return 1ULL << _vec_find (v)->log2_align;
 158 }
 159
 160 static_always_inline void
 161 _vec_prealloc (void **vp, uword n_elts, uword hdr_sz, uword align, void *heap,
 162                uword elt_sz)
 163 {
 164   const vec_attr_t va = {
 165     .elt_sz = elt_sz, .hdr_sz = hdr_sz, .align = align, .heap = heap
 166   };
 167   void *v;
 168
 169   ASSERT (vp[0] == 0);
 170
 171   v = _vec_alloc_internal (n_elts, &va);
 172   _vec_set_len (v, 0, elt_sz);
 173   _vec_update_pointer (vp, v);
 174 }
 175
 176 /** \brief Pre-allocate a vector (generic version)
 177
 178     @param V pointer to a vector
 179     @param N number of elements to pre-allocate
 180     @param H header size in bytes (may be zero)
 181     @param A alignment (zero means default alignment of the data structure)
 182     @param P heap (zero means default heap)
 183     @return V (value-result macro parameter)
 184 */
 185
 186 #define vec_prealloc_hap(V, N, H, A, P)                                       \
 187   _vec_prealloc ((void **) &(V), N, H, _vec_align (V, A), P, _vec_elt_sz (V))
 188
 189 /** \brief Pre-allocate a vector (simple version)
 190
 191     @param V pointer to a vector
 192     @param N number of elements to pre-allocate
 193     @return V (value-result macro parameter)
 194 */
 195 #define vec_prealloc(V, N) vec_prealloc_hap (V, N, 0, 0, 0)
 196
 197 /** \brief Pre-allocate a vector (heap version)
 198
 199     @param V pointer to a vector
 200     @param N number of elements to pre-allocate
 201     @param P heap (zero means default heap)
 202     @return V (value-result macro parameter)
 203 */
 204 #define vec_prealloc_heap(V, N, P) vec_prealloc_hap (V, N, 0, 0, P)
 205
 206 always_inline int
 207 _vec_resize_will_expand (void *v, uword n_elts, uword elt_sz)
 208 {
 209   if (v == 0)
 210     return 1;
 211
 212   /* Vector header must start heap object. */
 213   ASSERT (clib_mem_heap_is_heap_object (vec_get_heap (v), vec_header (v)));
 214
 215   n_elts += _vec_len (v);
 216   if ((n_elts * elt_sz) <= vec_max_bytes (v))
 217     return 0;
 218
 219   return 1;
 220 }
 221
 222 /** \brief Determine if vector will resize with next allocation
 223
 224     @param V pointer to a vector
 225     @param N number of elements to add
 226     @return 1 if vector will resize 0 otherwise
 227 */
 228
 229 #define vec_resize_will_expand(V, N)                                          \
 230   _vec_resize_will_expand (V, N, _vec_elt_sz (V))
 231
 232 /* Local variable naming macro (prevents collisions with other macro naming). */
 233 #define _v(var) _vec_##var
 234
 235 /** \brief Resize a vector (general version).
 236    Add N elements to end of given vector V, return pointer to start of vector.
 237    Vector will have room for H header bytes and will have user's data aligned
 238    at alignment A (rounded to next power of 2).
 239
 240     @param V pointer to a vector
 241     @param N number of elements to add
 242     @param H header size in bytes (may be zero)
 243     @param A alignment (may be zero)
 244     @return V (value-result macro parameter)
 245 */
 246
 247 static_always_inline void
 248 _vec_resize (void **vp, uword n_add, uword hdr_sz, uword align, uword elt_sz)
 249 {
 250   void *v = *vp;
 251   if (PREDICT_FALSE (v == 0))
 252     {
 253       const vec_attr_t va = { .elt_sz = elt_sz,
 254                               .align = align,
 255                               .hdr_sz = hdr_sz };
 256       *vp = _vec_alloc_internal (n_add, &va);
 257       return;
 258     }
 259
 260   if (PREDICT_FALSE (_vec_find (v)->grow_elts < n_add))
 261     {
 262       const vec_attr_t va = { .elt_sz = elt_sz,
 263                               .align = align,
 264                               .hdr_sz = hdr_sz };
 265       v = _vec_resize_internal (v, _vec_len (v) + n_add, &va);
 266       _vec_update_pointer (vp, v);
 267     }
 268   else
 269     _vec_set_len (v, _vec_len (v) + n_add, elt_sz);
 270 }
 271
 272 #define vec_resize_ha(V, N, H, A)                                             \
 273   _vec_resize ((void **) &(V), N, H, _vec_align (V, A), _vec_elt_sz (V))
 274
 275 /** \brief Resize a vector (no header, unspecified alignment)
 276    Add N elements to end of given vector V, return pointer to start of vector.
 277    Vector will have room for H header bytes and will have user's data aligned
 278    at alignment A (rounded to next power of 2).
 279
 280     @param V pointer to a vector
 281     @param N number of elements to add
 282     @return V (value-result macro parameter)
 283 */
 284 #define vec_resize(V,N)     vec_resize_ha(V,N,0,0)
 285
 286 /** \brief Resize a vector (no header, alignment specified).
 287    Add N elements to end of given vector V, return pointer to start of vector.
 288    Vector will have room for H header bytes and will have user's data aligned
 289    at alignment A (rounded to next power of 2).
 290
 291     @param V pointer to a vector
 292     @param N number of elements to add
 293     @param A alignment (may be zero)
 294     @return V (value-result macro parameter)
 295 */
 296
 297 #define vec_resize_aligned(V,N,A) vec_resize_ha(V,N,0,A)
 298
 299 /** \brief Allocate space for N more elements
 300
 301     @param V pointer to a vector
 302     @param N number of elements to add
 303     @param H header size in bytes (may be zero)
 304     @param A alignment (may be zero)
 305     @return V (value-result macro parameter)
 306 */
 307
 308 #define vec_alloc_ha(V, N, H, A)                                              \
 309   do                                                                          \
 310     {                                                                         \
 311       uword _v (l) = vec_len (V);                                             \
 312       vec_resize_ha (V, N, H, A);                                             \
 313       vec_set_len (V, _v (l));                                                \
 314     }                                                                         \
 315   while (0)
 316
 317 /** \brief Allocate space for N more elements
 318     (no header, unspecified alignment)
 319
 320     @param V pointer to a vector
 321     @param N number of elements to add
 322     @return V (value-result macro parameter)
 323 */
 324 #define vec_alloc(V,N) vec_alloc_ha(V,N,0,0)
 325
 326 /** \brief Allocate space for N more elements (no header, given alignment)
 327     @param V pointer to a vector
 328     @param N number of elements to add
 329     @param A alignment (may be zero)
 330     @return V (value-result macro parameter)
 331 */
 332
 333 #define vec_alloc_aligned(V,N,A) vec_alloc_ha(V,N,0,A)
 334
 335 /** \brief Create new vector of given type and length (general version).
 336     @param T type of elements in new vector
 337     @param N number of elements to add
 338     @param H header size in bytes (may be zero)
 339     @param A alignment (may be zero)
 340     @param P heap (may be zero)
 341     @return V new vector
 342 */
 343 #define vec_new_generic(T, N, H, A, P)                                        \
 344   _vec_alloc_internal (N, &((vec_attr_t){ .align = _vec_align ((T *) 0, A),   \
 345                                           .hdr_sz = (H),                      \
 346                                           .heap = (P),                        \
 347                                           .elt_sz = sizeof (T) }))
 348
 349 /** \brief Create new vector of given type and length
 350     (unspecified alignment, no header).
 351
 352     @param T type of elements in new vector
 353     @param N number of elements to add
 354     @return V new vector
 355 */
 356 #define vec_new(T, N) vec_new_generic (T, N, 0, 0, 0)
 357 /** \brief Create new vector of given type and length
 358     (alignment specified, no header).
 359
 360     @param T type of elements in new vector
 361     @param N number of elements to add
 362     @param A alignment (may be zero)
 363     @return V new vector
 364 */
 365 #define vec_new_aligned(T, N, A) vec_new_generic (T, N, 0, A, 0)
 366 /** \brief Create new vector of given type and length
 367     (heap specified, no header).
 368
 369     @param T type of elements in new vector
 370     @param N number of elements to add
 371     @param P heap (may be zero)
 372     @return V new vector
 373 */
 374 #define vec_new_heap(T, N, P) vec_new_generic (T, N, 0, 0, P)
 375
 376 /** \brief Free vector's memory (no header).
 377     @param V pointer to a vector
 378     @return V (value-result parameter, V=0)
 379 */
 380
 381 static_always_inline void
 382 _vec_free (void **vp)
 383 {
 384   if (vp[0] == 0)
 385     return;
 386   clib_mem_heap_free (vec_get_heap (vp[0]), vec_header (vp[0]));
 387   vp[0] = 0;
 388 }
 389
 390 #define vec_free(V) _vec_free ((void **) &(V))
 391
 392 void vec_free_not_inline (void *v);
 393
 394 /**\brief Free vector user header (syntactic sugar)
 395    @param h vector header
 396    @void
 397 */
 398 #define vec_free_header(h) clib_mem_free (h)
 399
 400 /** \brief Return copy of vector (general version).
 401
 402     @param V pointer to a vector
 403     @param H size of header in bytes
 404     @param A alignment (may be zero)
 405
 406     @return Vdup copy of vector
 407 */
 408
 409 static_always_inline void *
 410 _vec_dup (void *v, uword hdr_size, uword align, uword elt_sz)
 411 {
 412   uword len = vec_len (v);
 413   const vec_attr_t va = { .elt_sz = elt_sz, .align = align };
 414   void *n = 0;
 415
 416   if (len)
 417     {
 418       n = _vec_alloc_internal (len, &va);
 419       clib_memcpy_fast (n, v, len * elt_sz);
 420     }
 421   return n;
 422 }
 423
 424 #define vec_dup_ha(V, H, A)                                                   \
 425   _vec_dup ((void *) (V), H, _vec_align (V, A), _vec_elt_sz (V))
 426
 427 /** \brief Return copy of vector (no header, no alignment)
 428
 429     @param V pointer to a vector
 430     @return Vdup copy of vector
 431 */
 432 #define vec_dup(V) vec_dup_ha(V,0,0)
 433
 434 /** \brief Return copy of vector (no header, alignment specified).
 435
 436     @param V pointer to a vector
 437     @param A alignment (may be zero)
 438
 439     @return Vdup copy of vector
 440 */
 441 #define vec_dup_aligned(V,A) vec_dup_ha(V,0,A)
 442
 443 /** \brief Copy a vector, memcpy wrapper. Assumes sizeof(SRC[0]) ==
 444     sizeof(DST[0])
 445
 446     @param DST destination
 447     @param SRC source
 448 */
 449 #define vec_copy(DST,SRC) clib_memcpy_fast (DST, SRC, vec_len (DST) * \
 450                                        sizeof ((DST)[0]))
 451
 452 /** \brief Clone a vector. Make a new vector with the
 453     same size as a given vector but possibly with a different type.
 454
 455     @param NEW_V pointer to new vector
 456     @param OLD_V pointer to old vector
 457 */
 458
 459 static_always_inline void
 460 _vec_clone (void **v1p, void *v2, uword align, uword elt_sz)
 461 {
 462   const vec_attr_t va = { .elt_sz = elt_sz, .align = align };
 463   v1p[0] = _vec_alloc_internal (vec_len (v2), &va);
 464 }
 465 #define vec_clone(NEW_V, OLD_V)                                               \
 466   _vec_clone ((void **) &(NEW_V), OLD_V, _vec_align (NEW_V, 0),               \
 467               _vec_elt_sz (NEW_V))
 468
 469 /** \brief Make sure vector is long enough for given index (general version).
 470
 471     @param V (possibly NULL) pointer to a vector.
 472     @param I vector index which will be valid upon return
 473     @param H header size in bytes (may be zero)
 474     @param A alignment (may be zero)
 475     @return V (value-result macro parameter)
 476 */
 477
 478 always_inline void
 479 _vec_zero_elts (void *v, uword first, uword count, uword elt_sz)
 480 {
 481   clib_memset_u8 (v + (first * elt_sz), 0, count * elt_sz);
 482 }
 483 #define vec_zero_elts(V, F, C) _vec_zero_elts (V, F, C, sizeof ((V)[0]))
 484
 485 static_always_inline void
 486 _vec_validate (void **vp, uword index, uword header_size, uword align,
 487                void *heap, uword elt_sz)
 488 {
 489   void *v = *vp;
 490   uword vl, n_elts = index + 1;
 491
 492   if (PREDICT_FALSE (v == 0))
 493     {
 494       const vec_attr_t va = { .elt_sz = elt_sz,
 495                               .align = align,
 496                               .hdr_sz = header_size };
 497       *vp = _vec_alloc_internal (n_elts, &va);
 498       return;
 499     }
 500
 501   vl = _vec_len (v);
 502
 503   if (PREDICT_FALSE (index < vl))
 504     return;
 505
 506   if (PREDICT_FALSE (index >= _vec_find (v)->grow_elts + vl))
 507     {
 508       const vec_attr_t va = { .elt_sz = elt_sz,
 509                               .align = align,
 510                               .hdr_sz = header_size };
 511       v = _vec_resize_internal (v, n_elts, &va);
 512       _vec_update_pointer (vp, v);
 513     }
 514   else
 515     _vec_set_len (v, n_elts, elt_sz);
 516
 517   _vec_zero_elts (v, vl, n_elts - vl, elt_sz);
 518 }
 519
 520 #define vec_validate_hap(V, I, H, A, P)                                       \
 521   _vec_validate ((void **) &(V), I, H, _vec_align (V, A), 0, sizeof ((V)[0]))
 522
 523 /** \brief Make sure vector is long enough for given index
 524     (no header, unspecified alignment)
 525
 526     @param V (possibly NULL) pointer to a vector.
 527     @param I vector index which will be valid upon return
 528     @return V (value-result macro parameter)
 529 */
 530 #define vec_validate(V, I) vec_validate_hap (V, I, 0, 0, 0)
 531
 532 /** \brief Make sure vector is long enough for given index
 533     (no header, specified alignment)
 534
 535     @param V (possibly NULL) pointer to a vector.
 536     @param I vector index which will be valid upon return
 537     @param A alignment (may be zero)
 538     @return V (value-result macro parameter)
 539 */
 540
 541 #define vec_validate_aligned(V, I, A) vec_validate_hap (V, I, 0, A, 0)
 542
 543 /** \brief Make sure vector is long enough for given index
 544     (no header, specified heap)
 545
 546     @param V (possibly NULL) pointer to a vector.
 547     @param I vector index which will be valid upon return
 548     @param H heap (may be zero)
 549     @return V (value-result macro parameter)
 550 */
 551
 552 #define vec_validate_heap(V, I, P) vec_validate_hap (V, I, 0, 0, P)
 553
 554 /** \brief Make sure vector is long enough for given index
 555     and initialize empty space (general version)
 556
 557     @param V (possibly NULL) pointer to a vector.
 558     @param I vector index which will be valid upon return
 559     @param INIT initial value (can be a complex expression!)
 560     @param H header size in bytes (may be zero)
 561     @param A alignment (may be zero)
 562     @return V (value-result macro parameter)
 563 */
 564 #define vec_validate_init_empty_ha(V, I, INIT, H, A)                          \
 565   do                                                                          \
 566     {                                                                         \
 567       word _v (i) = (I);                                                      \
 568       word _v (l) = vec_len (V);                                              \
 569       if (_v (i) >= _v (l))                                                   \
 570         {                                                                     \
 571           vec_resize_ha (V, 1 + (_v (i) - _v (l)), H, A);                     \
 572           while (_v (l) <= _v (i))                                            \
 573             {                                                                 \
 574               (V)[_v (l)] = (INIT);                                           \
 575               _v (l)++;                                                       \
 576             }                                                                 \
 577         }                                                                     \
 578     }                                                                         \
 579   while (0)
 580
 581 /** \brief Make sure vector is long enough for given index
 582     and initialize empty space (no header, unspecified alignment)
 583
 584     @param V (possibly NULL) pointer to a vector.
 585     @param I vector index which will be valid upon return
 586     @param INIT initial value (can be a complex expression!)
 587     @return V (value-result macro parameter)
 588 */
 589
 590 #define vec_validate_init_empty(V,I,INIT) \
 591   vec_validate_init_empty_ha(V,I,INIT,0,0)
 592
 593 /** \brief Make sure vector is long enough for given index
 594     and initialize empty space (no header, alignment alignment)
 595
 596     @param V (possibly NULL) pointer to a vector.
 597     @param I vector index which will be valid upon return
 598     @param INIT initial value (can be a complex expression!)
 599     @param A alignment (may be zero)
 600     @return V (value-result macro parameter)
 601 */
 602 #define vec_validate_init_empty_aligned(V,I,INIT,A) \
 603   vec_validate_init_empty_ha(V,I,INIT,0,A)
 604
 605 /** \brief Add 1 element to end of vector (general version).
 606
 607     @param V pointer to a vector
 608     @param E element to add
 609     @param H header size in bytes (may be zero)
 610     @param A alignment (may be zero)
 611     @return V (value-result macro parameter)
 612 */
 613
 614 static_always_inline void *
 615 _vec_add1 (void **vp, uword hdr_sz, uword align, uword elt_sz)
 616 {
 617   void *v = vp[0];
 618   uword len;
 619
 620   if (PREDICT_FALSE (v == 0))
 621     {
 622       const vec_attr_t va = { .elt_sz = elt_sz,
 623                               .align = align,
 624                               .hdr_sz = hdr_sz };
 625       return *vp = _vec_alloc_internal (1, &va);
 626     }
 627
 628   len = _vec_len (v);
 629
 630   if (PREDICT_FALSE (_vec_find (v)->grow_elts == 0))
 631     {
 632       const vec_attr_t va = { .elt_sz = elt_sz,
 633                               .align = align,
 634                               .hdr_sz = hdr_sz };
 635       v = _vec_resize_internal (v, len + 1, &va);
 636       _vec_update_pointer (vp, v);
 637     }
 638   else
 639     _vec_set_len (v, len + 1, elt_sz);
 640
 641   return v + len * elt_sz;
 642 }
 643
 644 #define vec_add1_ha(V, E, H, A)                                               \
 645   ((__typeof__ ((V)[0]) *) _vec_add1 ((void **) &(V), H, _vec_align (V, A),   \
 646                                       _vec_elt_sz (V)))[0] = (E)
 647
 648 /** \brief Add 1 element to end of vector (unspecified alignment).
 649
 650     @param V pointer to a vector
 651     @param E element to add
 652     @return V (value-result macro parameter)
 653 */
 654 #define vec_add1(V,E)           vec_add1_ha(V,E,0,0)
 655
 656 /** \brief Add 1 element to end of vector (alignment specified).
 657
 658     @param V pointer to a vector
 659     @param E element to add
 660     @param A alignment (may be zero)
 661     @return V (value-result macro parameter)
 662 */
 663 #define vec_add1_aligned(V,E,A) vec_add1_ha(V,E,0,A)
 664
 665 /** \brief Add N elements to end of vector V,
 666     return pointer to new elements in P. (general version)
 667
 668     @param V pointer to a vector
 669     @param P pointer to new vector element(s)
 670     @param N number of elements to add
 671     @param H header size in bytes (may be zero)
 672     @param A alignment (may be zero)
 673     @return V and P (value-result macro parameters)
 674 */
 675
 676 static_always_inline void
 677 _vec_add2 (void **vp, void **pp, uword n_add, uword hdr_sz, uword align,
 678            uword elt_sz)
 679 {
 680   void *v = *vp;
 681   uword len;
 682
 683   if (PREDICT_FALSE (v == 0))
 684     {
 685       const vec_attr_t va = { .elt_sz = elt_sz,
 686                               .align = align,
 687                               .hdr_sz = hdr_sz };
 688       *vp = *pp = _vec_alloc_internal (n_add, &va);
 689       return;
 690     }
 691
 692   len = _vec_len (v);
 693   if (PREDICT_FALSE (_vec_find (v)->grow_elts < n_add))
 694     {
 695       const vec_attr_t va = { .elt_sz = elt_sz,
 696                               .align = align,
 697                               .hdr_sz = hdr_sz };
 698       v = _vec_resize_internal (v, len + n_add, &va);
 699       _vec_update_pointer (vp, v);
 700     }
 701   else
 702     _vec_set_len (v, len + n_add, elt_sz);
 703
 704   *pp = v + len * elt_sz;
 705 }
 706
 707 #define vec_add2_ha(V, P, N, H, A)                                            \
 708   _vec_add2 ((void **) &(V), (void **) &(P), N, H, _vec_align (V, A),         \
 709              _vec_elt_sz (V))
 710
 711 /** \brief Add N elements to end of vector V,
 712     return pointer to new elements in P. (no header, unspecified alignment)
 713
 714     @param V pointer to a vector
 715     @param P pointer to new vector element(s)
 716     @param N number of elements to add
 717     @return V and P (value-result macro parameters)
 718 */
 719
 720 #define vec_add2(V,P,N)           vec_add2_ha(V,P,N,0,0)
 721
 722 /** \brief Add N elements to end of vector V,
 723     return pointer to new elements in P. (no header, alignment specified)
 724
 725     @param V pointer to a vector
 726     @param P pointer to new vector element(s)
 727     @param N number of elements to add
 728     @param A alignment (may be zero)
 729     @return V and P (value-result macro parameters)
 730 */
 731
 732 #define vec_add2_aligned(V,P,N,A) vec_add2_ha(V,P,N,0,A)
 733
 734 /** \brief Add N elements to end of vector V (general version)
 735
 736     @param V pointer to a vector
 737     @param E pointer to element(s) to add
 738     @param N number of elements to add
 739     @param H header size in bytes (may be zero)
 740     @param A alignment (may be zero)
 741     @return V (value-result macro parameter)
 742 */
 743 static_always_inline void
 744 _vec_add (void **vp, void *e, word n_add, uword hdr_sz, uword align,
 745           uword elt_sz)
 746 {
 747   void *v = *vp;
 748   uword len;
 749
 750   ASSERT (n_add >= 0);
 751
 752   if (n_add < 1)
 753     return;
 754
 755   if (PREDICT_FALSE (v == 0))
 756     {
 757       const vec_attr_t va = { .elt_sz = elt_sz,
 758                               .align = align,
 759                               .hdr_sz = hdr_sz };
 760       *vp = v = _vec_alloc_internal (n_add, &va);
 761       clib_memcpy_fast (v, e, n_add * elt_sz);
 762       return;
 763     }
 764
 765   len = _vec_len (v);
 766
 767   if (PREDICT_FALSE (_vec_find (v)->grow_elts < n_add))
 768     {
 769       const vec_attr_t va = { .elt_sz = elt_sz,
 770                               .align = align,
 771                               .hdr_sz = hdr_sz };
 772       v = _vec_resize_internal (v, len + n_add, &va);
 773       _vec_update_pointer (vp, v);
 774     }
 775   else
 776     _vec_set_len (v, len + n_add, elt_sz);
 777
 778   clib_memcpy_fast (v + len * elt_sz, e, n_add * elt_sz);
 779 }
 780
 781 #define vec_add_ha(V, E, N, H, A)                                             \
 782   _vec_add ((void **) &(V), (void *) (E), N, H, _vec_align (V, A),            \
 783             _vec_elt_sz (V))
 784
 785 /** \brief Add N elements to end of vector V (no header, unspecified alignment)
 786
 787     @param V pointer to a vector
 788     @param E pointer to element(s) to add
 789     @param N number of elements to add
 790     @return V (value-result macro parameter)
 791 */
 792 #define vec_add(V,E,N)           vec_add_ha(V,E,N,0,0)
 793
 794 /** \brief Add N elements to end of vector V (no header, specified alignment)
 795
 796     @param V pointer to a vector
 797     @param E pointer to element(s) to add
 798     @param N number of elements to add
 799     @param A alignment (may be zero)
 800     @return V (value-result macro parameter)
 801 */
 802 #define vec_add_aligned(V,E,N,A) vec_add_ha(V,E,N,0,A)
 803
 804 /** \brief Returns last element of a vector and decrements its length
 805
 806     @param V pointer to a vector
 807     @return E element removed from the end of the vector
 808 */
 809 #define vec_pop(V)                                                            \
 810   ({                                                                          \
 811     uword _v (l) = vec_len (V);                                               \
 812     __typeof__ ((V)[0]) _v (rv);                                              \
 813     ASSERT (_v (l) > 0);                                                      \
 814     _v (l) -= 1;                                                              \
 815     _v (rv) = (V)[_v (l)];                                                    \
 816     vec_set_len (V, _v (l));                                                  \
 817     (_v (rv));                                                                \
 818   })
 819
 820 /** \brief Set E to the last element of a vector, decrement vector length
 821     @param V pointer to a vector
 822     @param E pointer to the last vector element
 823     @return E element removed from the end of the vector
 824     (value-result macro parameter
 825 */
 826
 827 #define vec_pop2(V,E)                           \
 828 ({                                              \
 829   uword _v(l) = vec_len (V);                    \
 830   if (_v(l) > 0) (E) = vec_pop (V);             \
 831   _v(l) > 0;                                    \
 832 })
 833
 834 /** \brief Insert N vector elements starting at element M,
 835     initialize new elements (general version).
 836
 837     @param V (possibly NULL) pointer to a vector.
 838     @param N number of elements to insert
 839     @param M insertion point
 840     @param INIT initial value (can be a complex expression!)
 841     @param H header size in bytes (may be zero)
 842     @param A alignment (may be zero)
 843     @return V (value-result macro parameter)
 844 */
 845
 846 static_always_inline void
 847 _vec_insert (void **vp, uword n_insert, uword ins_pt, u8 init, uword hdr_sz,
 848              uword align, uword elt_sz)
 849 {
 850   void *v = vp[0];
 851   uword len = vec_len (v);
 852   const vec_attr_t va = { .elt_sz = elt_sz, .align = align, .hdr_sz = hdr_sz };
 853
 854   ASSERT (ins_pt <= len);
 855
 856   v = _vec_resize_internal (v, len + n_insert, &va);
 857   clib_memmove (v + va.elt_sz * (ins_pt + n_insert), v + ins_pt * elt_sz,
 858                 (len - ins_pt) * elt_sz);
 859   _vec_zero_elts (v, ins_pt, n_insert, elt_sz);
 860   _vec_update_pointer (vp, v);
 861 }
 862
 863 #define vec_insert_init_empty_ha(V, N, M, INIT, H, A)                         \
 864   _vec_insert ((void **) &(V), N, M, INIT, H, _vec_align (V, A),              \
 865                _vec_elt_sz (V))
 866
 867 /** \brief Insert N vector elements starting at element M,
 868     initialize new elements to zero (general version)
 869
 870     @param V (possibly NULL) pointer to a vector.
 871     @param N number of elements to insert
 872     @param M insertion point
 873     @param H header size in bytes (may be zero)
 874     @param A alignment (may be zero)
 875     @return V (value-result macro parameter)
 876 */
 877 #define vec_insert_ha(V,N,M,H,A)    vec_insert_init_empty_ha(V,N,M,0,H,A)
 878
 879 /** \brief Insert N vector elements starting at element M,
 880     initialize new elements to zero (no header, unspecified alignment)
 881
 882     @param V (possibly NULL) pointer to a vector.
 883     @param N number of elements to insert
 884     @param M insertion point
 885     @return V (value-result macro parameter)
 886 */
 887 #define vec_insert(V,N,M)           vec_insert_ha(V,N,M,0,0)
 888
 889 /** \brief Insert N vector elements starting at element M,
 890     initialize new elements to zero (no header, alignment specified)
 891
 892     @param V (possibly NULL) pointer to a vector.
 893     @param N number of elements to insert
 894     @param M insertion point
 895     @param A alignment (may be zero)
 896     @return V (value-result macro parameter)
 897 */
 898 #define vec_insert_aligned(V,N,M,A) vec_insert_ha(V,N,M,0,A)
 899
 900 /** \brief Insert N vector elements starting at element M,
 901     initialize new elements (no header, unspecified alignment)
 902
 903     @param V (possibly NULL) pointer to a vector.
 904     @param N number of elements to insert
 905     @param M insertion point
 906     @param INIT initial value (can be a complex expression!)
 907     @return V (value-result macro parameter)
 908 */
 909
 910 #define vec_insert_init_empty(V,N,M,INIT) \
 911   vec_insert_init_empty_ha(V,N,M,INIT,0,0)
 912 /* Resize vector by N elements starting from element M, initialize new elements to INIT (alignment specified, no header). */
 913
 914 /** \brief Insert N vector elements starting at element M,
 915     initialize new elements (no header, specified alignment)
 916
 917     @param V (possibly NULL) pointer to a vector.
 918     @param N number of elements to insert
 919     @param M insertion point
 920     @param INIT initial value (can be a complex expression!)
 921     @param A alignment (may be zero)
 922     @return V (value-result macro parameter)
 923 */
 924 #define vec_insert_init_empty_aligned(V,N,M,INIT,A) \
 925   vec_insert_init_empty_ha(V,N,M,INIT,0,A)
 926
 927 /** \brief Insert N vector elements starting at element M,
 928     insert given elements (general version)
 929
 930     @param V (possibly NULL) pointer to a vector.
 931     @param E element(s) to insert
 932     @param N number of elements to insert
 933     @param M insertion point
 934     @param H header size in bytes (may be zero)
 935     @param A alignment (may be zero)
 936     @return V (value-result macro parameter)
 937 */
 938
 939 static_always_inline void
 940 _vec_insert_elts (void **vp, void *e, uword n_insert, uword ins_pt,
 941                   uword hdr_sz, uword align, uword elt_sz)
 942 {
 943   void *v = vp[0];
 944   uword len = vec_len (v);
 945   const vec_attr_t va = { .elt_sz = elt_sz, .align = align, .hdr_sz = hdr_sz };
 946
 947   ASSERT (ins_pt <= len);
 948
 949   v = _vec_resize_internal (v, len + n_insert, &va);
 950   clib_memmove (v + elt_sz * (ins_pt + n_insert), v + ins_pt * elt_sz,
 951                 (len - ins_pt) * elt_sz);
 952   _vec_zero_elts (v, ins_pt, n_insert, elt_sz);
 953   clib_memcpy_fast (v + ins_pt * elt_sz, e, n_insert * elt_sz);
 954   _vec_update_pointer (vp, v);
 955 }
 956
 957 #define vec_insert_elts_ha(V, E, N, M, H, A)                                  \
 958   _vec_insert_elts ((void **) &(V), E, N, M, H, _vec_align (V, A),            \
 959                     _vec_elt_sz (V))
 960
 961 /** \brief Insert N vector elements starting at element M,
 962     insert given elements (no header, unspecified alignment)
 963
 964     @param V (possibly NULL) pointer to a vector.
 965     @param E element(s) to insert
 966     @param N number of elements to insert
 967     @param M insertion point
 968     @return V (value-result macro parameter)
 969 */
 970 #define vec_insert_elts(V,E,N,M)           vec_insert_elts_ha(V,E,N,M,0,0)
 971
 972 /** \brief Insert N vector elements starting at element M,
 973     insert given elements (no header, specified alignment)
 974
 975     @param V (possibly NULL) pointer to a vector.
 976     @param E element(s) to insert
 977     @param N number of elements to insert
 978     @param M insertion point
 979     @param A alignment (may be zero)
 980     @return V (value-result macro parameter)
 981 */
 982 #define vec_insert_elts_aligned(V,E,N,M,A) vec_insert_elts_ha(V,E,N,M,0,A)
 983
 984 /** \brief Delete N elements starting at element M
 985
 986     @param V pointer to a vector
 987     @param N number of elements to delete
 988     @param M first element to delete
 989     @return V (value-result macro parameter)
 990 */
 991
 992 static_always_inline void
 993 _vec_delete (void *v, uword n_del, uword first, uword elt_sz)
 994 {
 995   word n_bytes_del, n_bytes_to_move, len = vec_len (v);
 996   u8 *dst;
 997
 998   if (n_del == 0)
 999     return;
1000
1001   ASSERT (first + n_del <= len);
1002
1003   n_bytes_del = n_del * elt_sz;
1004   n_bytes_to_move = (len - first - n_del) * elt_sz;
1005   dst = v + first * elt_sz;
1006
1007   if (n_bytes_to_move > 0)
1008     clib_memmove (dst, dst + n_bytes_del, n_bytes_to_move);
1009   clib_memset (dst + n_bytes_to_move, 0, n_bytes_del);
1010
1011   _vec_set_len (v, _vec_len (v) - n_del, elt_sz);
1012 }
1013
1014 #define vec_delete(V, N, M) _vec_delete ((void *) (V), N, M, _vec_elt_sz (V))
1015
1016 /** \brief Delete the element at index I
1017
1018     @param V pointer to a vector
1019     @param I index to delete
1020 */
1021
1022 static_always_inline void
1023 _vec_del1 (void *v, uword index, uword elt_sz)
1024 {
1025   uword len = _vec_len (v) - 1;
1026
1027   if (index < len)
1028     clib_memcpy_fast (v + index * elt_sz, v + len * elt_sz, elt_sz);
1029
1030   _vec_set_len (v, len, elt_sz);
1031 }
1032
1033 #define vec_del1(v, i) _vec_del1 ((void *) (v), i, _vec_elt_sz (v))
1034
1035 static_always_inline void
1036 _vec_append (void **v1p, void *v2, uword v1_elt_sz, uword v2_elt_sz,
1037              uword align)
1038 {
1039   void *v1 = v1p[0];
1040   uword len1 = vec_len (v1);
1041   uword len2 = vec_len (v2);
1042
1043   if (PREDICT_TRUE (len2 > 0))
1044     {
1045       const vec_attr_t va = { .elt_sz = v2_elt_sz, .align = align };
1046       v1 = _vec_resize_internal (v1, len1 + len2, &va);
1047       clib_memcpy_fast (v1 + len1 * v1_elt_sz, v2, len2 * v2_elt_sz);
1048       _vec_update_pointer (v1p, v1);
1049     }
1050 }
1051
1052 /** \brief Append v2 after v1. Result in v1. Specified alignment.
1053     @param V1 target vector
1054     @param V2 vector to append
1055     @param align required alignment
1056 */
1057
1058 #define vec_append_aligned(v1, v2, align)                                     \
1059   _vec_append ((void **) &(v1), (void *) (v2), _vec_elt_sz (v1),              \
1060                _vec_elt_sz (v2), _vec_align (v1, align))
1061
1062 /** \brief Append v2 after v1. Result in v1.
1063     @param V1 target vector
1064     @param V2 vector to append
1065 */
1066
1067 #define vec_append(v1, v2) vec_append_aligned (v1, v2, 0)
1068
1069 static_always_inline void
1070 _vec_prepend (void *restrict *v1p, void *restrict v2, uword v1_elt_sz,
1071               uword v2_elt_sz, uword align)
1072 {
1073   void *restrict v1 = v1p[0];
1074   uword len1 = vec_len (v1);
1075   uword len2 = vec_len (v2);
1076
1077   if (PREDICT_TRUE (len2 > 0))
1078     {
1079       /* prepending vector to itself would result in use-after-free */
1080       ASSERT (v1 != v2);
1081       const vec_attr_t va = { .elt_sz = v2_elt_sz, .align = align };
1082       v1 = _vec_resize_internal (v1, len1 + len2, &va);
1083       clib_memmove (v1 + len2 * v2_elt_sz, v1, len1 * v1_elt_sz);
1084       clib_memcpy_fast (v1, v2, len2 * v2_elt_sz);
1085       _vec_update_pointer ((void **) v1p, v1);
1086     }
1087 }
1088
1089 /** \brief Prepend v2 before v1. Result in v1. Specified alignment
1090     @param V1 target vector
1091     @param V2 vector to prepend, V1 != V2
1092     @param align required alignment
1093 */
1094
1095 #define vec_prepend_aligned(v1, v2, align)                                    \
1096   _vec_prepend ((void **) &(v1), (void *) (v2), _vec_elt_sz (v1),             \
1097                 _vec_elt_sz (v2), _vec_align (v1, align))
1098
1099 /** \brief Prepend v2 before v1. Result in v1.
1100     @param V1 target vector
1101     @param V2 vector to prepend, V1 != V2
1102 */
1103
1104 #define vec_prepend(v1, v2) vec_prepend_aligned (v1, v2, 0)
1105
1106 /** \brief Zero all vector elements. Null-pointer tolerant.
1107     @param var Vector to zero
1108 */
1109 static_always_inline void
1110 _vec_zero (void *v, uword elt_sz)
1111 {
1112   uword len = vec_len (v);
1113
1114   if (len)
1115     clib_memset_u8 (v, 0, len * elt_sz);
1116 }
1117
1118 #define vec_zero(var) _vec_zero ((void *) (var), _vec_elt_sz (var))
1119
1120 /** \brief Set all vector elements to given value. Null-pointer tolerant.
1121     @param v vector to set
1122     @param val value for each vector element
1123 */
1124 #define vec_set(v,val)                          \
1125 do {                                            \
1126   word _v(i);                                   \
1127   __typeof__ ((v)[0]) _val = (val);             \
1128   for (_v(i) = 0; _v(i) < vec_len (v); _v(i)++) \
1129     (v)[_v(i)] = _val;                          \
1130 } while (0)
1131
1132 #ifdef CLIB_UNIX
1133 #include <stdlib.h>             /* for qsort */
1134 #endif
1135
1136 /** \brief Compare two vectors, not NULL-pointer tolerant
1137
1138     @param v1 Pointer to a vector
1139     @param v2 Pointer to a vector
1140     @return 1 if equal, 0 if unequal
1141 */
1142 static_always_inline int
1143 _vec_is_equal (void *v1, void *v2, uword v1_elt_sz, uword v2_elt_sz)
1144 {
1145   uword vec_len_v1 = vec_len (v1);
1146
1147   if ((vec_len_v1 != vec_len (v2)) || (v1_elt_sz != v2_elt_sz))
1148     return 0;
1149
1150   if ((vec_len_v1 == 0) || (memcmp (v1, v2, vec_len_v1 * v1_elt_sz) == 0))
1151     return 1;
1152
1153   return 0;
1154 }
1155
1156 #define vec_is_equal(v1, v2)                                                  \
1157   _vec_is_equal ((void *) (v1), (void *) (v2), _vec_elt_sz (v1),              \
1158                  _vec_elt_sz (v2))
1159
1160 /** \brief Compare two vectors (only applicable to vectors of signed numbers).
1161    Used in qsort compare functions.
1162
1163     @param v1 Pointer to a vector
1164     @param v2 Pointer to a vector
1165     @return -1, 0, +1
1166 */
1167 #define vec_cmp(v1,v2)                                  \
1168 ({                                                      \
1169   word _v(i), _v(cmp), _v(l);                           \
1170   _v(l) = clib_min (vec_len (v1), vec_len (v2));        \
1171   _v(cmp) = 0;                                          \
1172   for (_v(i) = 0; _v(i) < _v(l); _v(i)++) {             \
1173     _v(cmp) = (v1)[_v(i)] - (v2)[_v(i)];                \
1174     if (_v(cmp))                                        \
1175       break;                                            \
1176   }                                                     \
1177   if (_v(cmp) == 0 && _v(l) > 0)                        \
1178     _v(cmp) = vec_len(v1) - vec_len(v2);                \
1179   (_v(cmp) < 0 ? -1 : (_v(cmp) > 0 ? +1 : 0));          \
1180 })
1181
1182 /** \brief Search a vector for the index of the entry that matches.
1183
1184     @param v Pointer to a vector
1185     @param E Entry to match
1186     @return index of match or ~0
1187 */
1188 #define vec_search(v,E)                                 \
1189 ({                                                      \
1190   word _v(i) = 0;                                       \
1191   while (_v(i) < vec_len(v))                            \
1192   {                                                     \
1193     if ((v)[_v(i)] == E)                                        \
1194       break;                                            \
1195     _v(i)++;                                            \
1196   }                                                     \
1197   if (_v(i) == vec_len(v))                              \
1198     _v(i) = ~0;                                         \
1199   _v(i);                                                \
1200 })
1201
1202 /** \brief Search a vector for the index of the entry that matches.
1203
1204     @param v Pointer to a vector
1205     @param E Pointer to entry to match
1206     @param fn Comparison function !0 => match
1207     @return index of match or ~0
1208 */
1209 #define vec_search_with_function(v,E,fn)                \
1210 ({                                                      \
1211   word _v(i) = 0;                                       \
1212   while (_v(i) < vec_len(v))                            \
1213   {                                                     \
1214     if (0 != fn(&(v)[_v(i)], (E)))                      \
1215       break;                                            \
1216     _v(i)++;                                            \
1217   }                                                     \
1218   if (_v(i) == vec_len(v))                              \
1219     _v(i) = ~0;                                         \
1220   _v(i);                                                \
1221 })
1222
1223 /** \brief Sort a vector using the supplied element comparison function
1224
1225     Does not depend on the underlying implementation to deal correctly
1226     with null, zero-long, or 1-long vectors
1227
1228     @param vec vector to sort
1229     @param f comparison function
1230 */
1231 #define vec_sort_with_function(vec,f)                           \
1232 do {                                                            \
1233   if (vec_len (vec) > 1)                                        \
1234     qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f));  \
1235 } while (0)
1236
1237 /** \brief Make a vector containing a NULL terminated c-string.
1238
1239     @param V (possibly NULL) pointer to a vector.
1240     @param S pointer to string buffer.
1241     @param L string length (NOT including the terminating NULL; a la strlen())
1242 */
1243 #define vec_validate_init_c_string(V, S, L)                                   \
1244   do                                                                          \
1245     {                                                                         \
1246       vec_reset_length (V);                                                   \
1247       vec_validate (V, (L));                                                  \
1248       if ((S) && (L))                                                         \
1249         clib_memcpy_fast (V, (S), (L));                                       \
1250       (V)[(L)] = 0;                                                           \
1251     }                                                                         \
1252   while (0)
1253
1254 /** \brief Test whether a vector is a NULL terminated c-string.
1255
1256     @param V (possibly NULL) pointer to a vector.
1257     @return BOOLEAN indicating if the vector c-string is null terminated.
1258 */
1259 #define vec_c_string_is_terminated(V)                   \
1260   (((V) != 0) && (vec_len (V) != 0) && ((V)[vec_len ((V)) - 1] == 0))
1261
1262 /** \brief (If necessary) NULL terminate a vector containing a c-string.
1263
1264     @param V (possibly NULL) pointer to a vector.
1265     @return V (value-result macro parameter)
1266 */
1267 #define vec_terminate_c_string(V)                                             \
1268   do                                                                          \
1269     {                                                                         \
1270       if (!vec_c_string_is_terminated (V))                                    \
1271         vec_add1 (V, 0);                                                      \
1272     }                                                                         \
1273   while (0)
1274
1275 #endif /* included_vec_h */