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 void *_vec_realloc (void *v, uword n_elts, uword elt_sz, uword hdr_sz,
 105                     uword align, void *heap);
 106
 107 /* calculate minimum alignment out of data natural alignment and provided
 108  * value, should not be < VEC_MIN_ALIGN */
 109 static_always_inline uword
 110 __vec_align (uword data_align, uword configuered_align)
 111 {
 112   data_align = clib_max (data_align, configuered_align);
 113   ASSERT (count_set_bits (data_align) == 1);
 114   return clib_max (VEC_MIN_ALIGN, data_align);
 115 }
 116
 117 /* function used t o catch cases where vec_* macros on used on void * */
 118 static_always_inline uword
 119 __vec_elt_sz (uword elt_sz, int is_void)
 120 {
 121   /* vector macro operations on void * are not allowed */
 122   ASSERT (is_void == 0);
 123   return elt_sz;
 124 }
 125
 126 static_always_inline void
 127 _vec_update_pointer (void **vp, void *v)
 128 {
 129   /* avoid store if not needed */
 130   if (v != vp[0])
 131     vp[0] = v;
 132 }
 133
 134 static_always_inline void *
 135 vec_get_heap (void *v)
 136 {
 137   if (v == 0 || _vec_find (v)->default_heap == 1)
 138     return 0;
 139   return _vec_heap (v);
 140 }
 141
 142 static_always_inline void *
 143 _vec_realloc_inline (void *v, uword n_elts, uword elt_sz, uword hdr_sz,
 144                      uword align, void *heap)
 145 {
 146   if (PREDICT_TRUE (v != 0))
 147     {
 148       /* Vector header must start heap object. */
 149       ASSERT (clib_mem_heap_is_heap_object (vec_get_heap (v), vec_header (v)));
 150
 151       /* Typically we'll not need to resize. */
 152       if ((n_elts * elt_sz) <= vec_max_bytes (v))
 153         {
 154           _vec_set_len (v, n_elts, elt_sz);
 155           return v;
 156         }
 157     }
 158
 159   /* Slow path: call helper function. */
 160   return _vec_realloc (v, n_elts, elt_sz, hdr_sz, align, heap);
 161 }
 162
 163 static_always_inline void
 164 _vec_prealloc (void **vp, uword n_elts, uword hdr_sz, uword align, void *heap,
 165                uword elt_sz)
 166 {
 167   void *v;
 168
 169   ASSERT (vp[0] == 0);
 170
 171   v = _vec_realloc (0, n_elts, elt_sz, hdr_sz, align, heap);
 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[0];
 251   v = _vec_realloc_inline (v, vec_len (v) + n_add, elt_sz, hdr_sz, align, 0);
 252   _vec_update_pointer (vp, v);
 253 }
 254
 255 #define vec_resize_ha(V, N, H, A)                                             \
 256   _vec_resize ((void **) &(V), N, H, _vec_align (V, A), _vec_elt_sz (V))
 257
 258 /** \brief Resize a vector (no header, unspecified alignment)
 259    Add N elements to end of given vector V, return pointer to start of vector.
 260    Vector will have room for H header bytes and will have user's data aligned
 261    at alignment A (rounded to next power of 2).
 262
 263     @param V pointer to a vector
 264     @param N number of elements to add
 265     @return V (value-result macro parameter)
 266 */
 267 #define vec_resize(V,N)     vec_resize_ha(V,N,0,0)
 268
 269 /** \brief Resize a vector (no header, alignment specified).
 270    Add N elements to end of given vector V, return pointer to start of vector.
 271    Vector will have room for H header bytes and will have user's data aligned
 272    at alignment A (rounded to next power of 2).
 273
 274     @param V pointer to a vector
 275     @param N number of elements to add
 276     @param A alignment (may be zero)
 277     @return V (value-result macro parameter)
 278 */
 279
 280 #define vec_resize_aligned(V,N,A) vec_resize_ha(V,N,0,A)
 281
 282 /** \brief Allocate space for N more elements
 283
 284     @param V pointer to a vector
 285     @param N number of elements to add
 286     @param H header size in bytes (may be zero)
 287     @param A alignment (may be zero)
 288     @return V (value-result macro parameter)
 289 */
 290
 291 #define vec_alloc_ha(V, N, H, A)                                              \
 292   do                                                                          \
 293     {                                                                         \
 294       uword _v (l) = vec_len (V);                                             \
 295       vec_resize_ha (V, N, H, A);                                             \
 296       vec_set_len (V, _v (l));                                                \
 297     }                                                                         \
 298   while (0)
 299
 300 /** \brief Allocate space for N more elements
 301     (no header, unspecified alignment)
 302
 303     @param V pointer to a vector
 304     @param N number of elements to add
 305     @return V (value-result macro parameter)
 306 */
 307 #define vec_alloc(V,N) vec_alloc_ha(V,N,0,0)
 308
 309 /** \brief Allocate space for N more elements (no header, given alignment)
 310     @param V pointer to a vector
 311     @param N number of elements to add
 312     @param A alignment (may be zero)
 313     @return V (value-result macro parameter)
 314 */
 315
 316 #define vec_alloc_aligned(V,N,A) vec_alloc_ha(V,N,0,A)
 317
 318 /** \brief Create new vector of given type and length (general version).
 319     @param T type of elements in new vector
 320     @param N number of elements to add
 321     @param H header size in bytes (may be zero)
 322     @param A alignment (may be zero)
 323     @param P heap (may be zero)
 324     @return V new vector
 325 */
 326 #define vec_new_generic(T, N, H, A, P)                                        \
 327   _vec_realloc (0, N, sizeof (T), H, _vec_align ((T *) 0, A), P)
 328
 329 /** \brief Create new vector of given type and length
 330     (unspecified alignment, no header).
 331
 332     @param T type of elements in new vector
 333     @param N number of elements to add
 334     @return V new vector
 335 */
 336 #define vec_new(T, N) vec_new_generic (T, N, 0, 0, 0)
 337 /** \brief Create new vector of given type and length
 338     (alignment specified, no header).
 339
 340     @param T type of elements in new vector
 341     @param N number of elements to add
 342     @param A alignment (may be zero)
 343     @return V new vector
 344 */
 345 #define vec_new_aligned(T, N, A) vec_new_generic (T, N, 0, A, 0)
 346 /** \brief Create new vector of given type and length
 347     (heap specified, no header).
 348
 349     @param T type of elements in new vector
 350     @param N number of elements to add
 351     @param P heap (may be zero)
 352     @return V new vector
 353 */
 354 #define vec_new_heap(T, N, P) vec_new_generic (T, N, 0, 0, P)
 355
 356 /** \brief Free vector's memory (no header).
 357     @param V pointer to a vector
 358     @return V (value-result parameter, V=0)
 359 */
 360
 361 static_always_inline void
 362 _vec_free (void **vp)
 363 {
 364   if (vp[0] == 0)
 365     return;
 366   clib_mem_free (vec_header (vp[0]));
 367   vp[0] = 0;
 368 }
 369
 370 #define vec_free(V) _vec_free ((void **) &(V))
 371
 372 void vec_free_not_inline (void *v);
 373
 374 /**\brief Free vector user header (syntactic sugar)
 375    @param h vector header
 376    @void
 377 */
 378 #define vec_free_header(h) clib_mem_free (h)
 379
 380 /** \brief Return copy of vector (general version).
 381
 382     @param V pointer to a vector
 383     @param H size of header in bytes
 384     @param A alignment (may be zero)
 385
 386     @return Vdup copy of vector
 387 */
 388
 389 static_always_inline void *
 390 _vec_dup (void *v, uword hdr_size, uword align, uword elt_sz)
 391 {
 392   uword len = vec_len (v);
 393   void *n = 0;
 394
 395   if (len)
 396     {
 397       n = _vec_realloc (0, len, elt_sz, hdr_size, align, 0);
 398       clib_memcpy_fast (n, v, len * elt_sz);
 399     }
 400   return n;
 401 }
 402
 403 #define vec_dup_ha(V, H, A)                                                   \
 404   _vec_dup ((void *) (V), H, _vec_align (V, A), _vec_elt_sz (V))
 405
 406 /** \brief Return copy of vector (no header, no alignment)
 407
 408     @param V pointer to a vector
 409     @return Vdup copy of vector
 410 */
 411 #define vec_dup(V) vec_dup_ha(V,0,0)
 412
 413 /** \brief Return copy of vector (no header, alignment specified).
 414
 415     @param V pointer to a vector
 416     @param A alignment (may be zero)
 417
 418     @return Vdup copy of vector
 419 */
 420 #define vec_dup_aligned(V,A) vec_dup_ha(V,0,A)
 421
 422 /** \brief Copy a vector, memcpy wrapper. Assumes sizeof(SRC[0]) ==
 423     sizeof(DST[0])
 424
 425     @param DST destination
 426     @param SRC source
 427 */
 428 #define vec_copy(DST,SRC) clib_memcpy_fast (DST, SRC, vec_len (DST) * \
 429                                        sizeof ((DST)[0]))
 430
 431 /** \brief Clone a vector. Make a new vector with the
 432     same size as a given vector but possibly with a different type.
 433
 434     @param NEW_V pointer to new vector
 435     @param OLD_V pointer to old vector
 436 */
 437
 438 static_always_inline void
 439 _vec_clone (void **v1p, void *v2, uword align, uword elt_sz)
 440 {
 441   v1p[0] = _vec_realloc (0, vec_len (v2), elt_sz, 0, align, 0);
 442 }
 443 #define vec_clone(NEW_V, OLD_V)                                               \
 444   _vec_clone ((void **) &(NEW_V), OLD_V, _vec_align (NEW_V, 0),               \
 445               _vec_elt_sz (NEW_V))
 446
 447 /** \brief Make sure vector is long enough for given index (general version).
 448
 449     @param V (possibly NULL) pointer to a vector.
 450     @param I vector index which will be valid upon return
 451     @param H header size in bytes (may be zero)
 452     @param A alignment (may be zero)
 453     @return V (value-result macro parameter)
 454 */
 455
 456 always_inline void
 457 _vec_zero_elts (void *v, uword first, uword count, uword elt_sz)
 458 {
 459   clib_memset_u8 (v + (first * elt_sz), 0, count * elt_sz);
 460 }
 461 #define vec_zero_elts(V, F, C) _vec_zero_elts (V, F, C, sizeof ((V)[0]))
 462
 463 static_always_inline void
 464 _vec_validate (void **vp, uword index, uword header_size, uword align,
 465                void *heap, uword elt_sz)
 466 {
 467   void *v = vp[0];
 468   uword vl = vec_len (v);
 469   if (index >= vl)
 470     {
 471       v = _vec_realloc_inline (v, index + 1, elt_sz, header_size, align, heap);
 472       _vec_zero_elts (v, vl, index - vl + 1, elt_sz);
 473       _vec_update_pointer (vp, v);
 474     }
 475 }
 476
 477 #define vec_validate_hap(V, I, H, A, P)                                       \
 478   _vec_validate ((void **) &(V), I, H, _vec_align (V, A), 0, sizeof ((V)[0]))
 479
 480 /** \brief Make sure vector is long enough for given index
 481     (no header, unspecified alignment)
 482
 483     @param V (possibly NULL) pointer to a vector.
 484     @param I vector index which will be valid upon return
 485     @return V (value-result macro parameter)
 486 */
 487 #define vec_validate(V, I) vec_validate_hap (V, I, 0, 0, 0)
 488
 489 /** \brief Make sure vector is long enough for given index
 490     (no header, specified alignment)
 491
 492     @param V (possibly NULL) pointer to a vector.
 493     @param I vector index which will be valid upon return
 494     @param A alignment (may be zero)
 495     @return V (value-result macro parameter)
 496 */
 497
 498 #define vec_validate_aligned(V, I, A) vec_validate_hap (V, I, 0, A, 0)
 499
 500 /** \brief Make sure vector is long enough for given index
 501     (no header, specified heap)
 502
 503     @param V (possibly NULL) pointer to a vector.
 504     @param I vector index which will be valid upon return
 505     @param H heap (may be zero)
 506     @return V (value-result macro parameter)
 507 */
 508
 509 #define vec_validate_heap(V, I, P) vec_validate_hap (V, I, 0, 0, P)
 510
 511 /** \brief Make sure vector is long enough for given index
 512     and initialize empty space (general version)
 513
 514     @param V (possibly NULL) pointer to a vector.
 515     @param I vector index which will be valid upon return
 516     @param INIT initial value (can be a complex expression!)
 517     @param H header size in bytes (may be zero)
 518     @param A alignment (may be zero)
 519     @return V (value-result macro parameter)
 520 */
 521 #define vec_validate_init_empty_ha(V, I, INIT, H, A)                          \
 522   do                                                                          \
 523     {                                                                         \
 524       word _v (i) = (I);                                                      \
 525       word _v (l) = vec_len (V);                                              \
 526       if (_v (i) >= _v (l))                                                   \
 527         {                                                                     \
 528           vec_resize_ha (V, 1 + (_v (i) - _v (l)), H, A);                     \
 529           while (_v (l) <= _v (i))                                            \
 530             {                                                                 \
 531               (V)[_v (l)] = (INIT);                                           \
 532               _v (l)++;                                                       \
 533             }                                                                 \
 534         }                                                                     \
 535     }                                                                         \
 536   while (0)
 537
 538 /** \brief Make sure vector is long enough for given index
 539     and initialize empty space (no header, unspecified alignment)
 540
 541     @param V (possibly NULL) pointer to a vector.
 542     @param I vector index which will be valid upon return
 543     @param INIT initial value (can be a complex expression!)
 544     @return V (value-result macro parameter)
 545 */
 546
 547 #define vec_validate_init_empty(V,I,INIT) \
 548   vec_validate_init_empty_ha(V,I,INIT,0,0)
 549
 550 /** \brief Make sure vector is long enough for given index
 551     and initialize empty space (no header, alignment alignment)
 552
 553     @param V (possibly NULL) pointer to a vector.
 554     @param I vector index which will be valid upon return
 555     @param INIT initial value (can be a complex expression!)
 556     @param A alignment (may be zero)
 557     @return V (value-result macro parameter)
 558 */
 559 #define vec_validate_init_empty_aligned(V,I,INIT,A) \
 560   vec_validate_init_empty_ha(V,I,INIT,0,A)
 561
 562 /** \brief Add 1 element to end of vector (general version).
 563
 564     @param V pointer to a vector
 565     @param E element to add
 566     @param H header size in bytes (may be zero)
 567     @param A alignment (may be zero)
 568     @return V (value-result macro parameter)
 569 */
 570
 571 static_always_inline void *
 572 _vec_add1 (void **vp, uword hdr_sz, uword align, uword elt_sz)
 573 {
 574   void *v = vp[0];
 575   uword len = vec_len (v);
 576   v = _vec_realloc_inline (v, len + 1, elt_sz, hdr_sz, align, 0);
 577
 578   _vec_update_pointer (vp, v);
 579
 580   return v + len * elt_sz;
 581 }
 582
 583 #define vec_add1_ha(V, E, H, A)                                               \
 584   ((__typeof__ ((V)[0]) *) _vec_add1 ((void **) &(V), H, _vec_align (V, A),   \
 585                                       _vec_elt_sz (V)))[0] = (E)
 586
 587 /** \brief Add 1 element to end of vector (unspecified alignment).
 588
 589     @param V pointer to a vector
 590     @param E element to add
 591     @return V (value-result macro parameter)
 592 */
 593 #define vec_add1(V,E)           vec_add1_ha(V,E,0,0)
 594
 595 /** \brief Add 1 element to end of vector (alignment specified).
 596
 597     @param V pointer to a vector
 598     @param E element to add
 599     @param A alignment (may be zero)
 600     @return V (value-result macro parameter)
 601 */
 602 #define vec_add1_aligned(V,E,A) vec_add1_ha(V,E,0,A)
 603
 604 /** \brief Add N elements to end of vector V,
 605     return pointer to new elements in P. (general version)
 606
 607     @param V pointer to a vector
 608     @param P pointer to new vector element(s)
 609     @param N number of elements to add
 610     @param H header size in bytes (may be zero)
 611     @param A alignment (may be zero)
 612     @return V and P (value-result macro parameters)
 613 */
 614
 615 static_always_inline void
 616 _vec_add2 (void **vp, void **pp, uword n_add, uword hdr_sz, uword align,
 617            uword elt_sz)
 618 {
 619   void *v = vp[0];
 620   uword len = vec_len (vp[0]);
 621   v = _vec_realloc_inline (v, len + n_add, elt_sz, hdr_sz, align, 0);
 622   _vec_update_pointer (vp, v);
 623   pp[0] = v + len * elt_sz;
 624 }
 625
 626 #define vec_add2_ha(V, P, N, H, A)                                            \
 627   _vec_add2 ((void **) &(V), (void **) &(P), N, H, _vec_align (V, A),         \
 628              _vec_elt_sz (V))
 629
 630 /** \brief Add N elements to end of vector V,
 631     return pointer to new elements in P. (no header, unspecified alignment)
 632
 633     @param V pointer to a vector
 634     @param P pointer to new vector element(s)
 635     @param N number of elements to add
 636     @return V and P (value-result macro parameters)
 637 */
 638
 639 #define vec_add2(V,P,N)           vec_add2_ha(V,P,N,0,0)
 640
 641 /** \brief Add N elements to end of vector V,
 642     return pointer to new elements in P. (no header, alignment specified)
 643
 644     @param V pointer to a vector
 645     @param P pointer to new vector element(s)
 646     @param N number of elements to add
 647     @param A alignment (may be zero)
 648     @return V and P (value-result macro parameters)
 649 */
 650
 651 #define vec_add2_aligned(V,P,N,A) vec_add2_ha(V,P,N,0,A)
 652
 653 /** \brief Add N elements to end of vector V (general version)
 654
 655     @param V pointer to a vector
 656     @param E pointer to element(s) to add
 657     @param N number of elements to add
 658     @param H header size in bytes (may be zero)
 659     @param A alignment (may be zero)
 660     @return V (value-result macro parameter)
 661 */
 662 static_always_inline void
 663 _vec_add (void **vp, void *e, word n_add, uword hdr_sz, uword align,
 664           uword elt_sz)
 665 {
 666   void *v = vp[0];
 667   uword len = vec_len (v);
 668
 669   ASSERT (n_add >= 0);
 670
 671   if (n_add < 1)
 672     return;
 673
 674   v = _vec_realloc_inline (v, len + n_add, elt_sz, hdr_sz, align, 0);
 675   clib_memcpy_fast (v + len * elt_sz, e, n_add * elt_sz);
 676   _vec_update_pointer (vp, v);
 677 }
 678
 679 #define vec_add_ha(V, E, N, H, A)                                             \
 680   _vec_add ((void **) &(V), (void *) (E), N, H, _vec_align (V, A),            \
 681             _vec_elt_sz (V))
 682
 683 /** \brief Add N elements to end of vector V (no header, unspecified alignment)
 684
 685     @param V pointer to a vector
 686     @param E pointer to element(s) to add
 687     @param N number of elements to add
 688     @return V (value-result macro parameter)
 689 */
 690 #define vec_add(V,E,N)           vec_add_ha(V,E,N,0,0)
 691
 692 /** \brief Add N elements to end of vector V (no header, specified alignment)
 693
 694     @param V pointer to a vector
 695     @param E pointer to element(s) to add
 696     @param N number of elements to add
 697     @param A alignment (may be zero)
 698     @return V (value-result macro parameter)
 699 */
 700 #define vec_add_aligned(V,E,N,A) vec_add_ha(V,E,N,0,A)
 701
 702 /** \brief Returns last element of a vector and decrements its length
 703
 704     @param V pointer to a vector
 705     @return E element removed from the end of the vector
 706 */
 707 #define vec_pop(V)                                                            \
 708   ({                                                                          \
 709     uword _v (l) = vec_len (V);                                               \
 710     __typeof__ ((V)[0]) _v (rv);                                              \
 711     ASSERT (_v (l) > 0);                                                      \
 712     _v (l) -= 1;                                                              \
 713     _v (rv) = (V)[_v (l)];                                                    \
 714     vec_set_len (V, _v (l));                                                  \
 715     (_v (rv));                                                                \
 716   })
 717
 718 /** \brief Set E to the last element of a vector, decrement vector length
 719     @param V pointer to a vector
 720     @param E pointer to the last vector element
 721     @return E element removed from the end of the vector
 722     (value-result macro parameter
 723 */
 724
 725 #define vec_pop2(V,E)                           \
 726 ({                                              \
 727   uword _v(l) = vec_len (V);                    \
 728   if (_v(l) > 0) (E) = vec_pop (V);             \
 729   _v(l) > 0;                                    \
 730 })
 731
 732 /** \brief Insert N vector elements starting at element M,
 733     initialize new elements (general version).
 734
 735     @param V (possibly NULL) pointer to a vector.
 736     @param N number of elements to insert
 737     @param M insertion point
 738     @param INIT initial value (can be a complex expression!)
 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
 744 static_always_inline void
 745 _vec_insert (void **vp, uword n_insert, uword ins_pt, u8 init, uword hdr_sz,
 746              uword align, uword elt_sz)
 747 {
 748   void *v = vp[0];
 749   uword len = vec_len (v);
 750
 751   ASSERT (ins_pt <= len);
 752
 753   v = _vec_realloc_inline (v, len + n_insert, elt_sz, hdr_sz, align, 0);
 754   clib_memmove (v + elt_sz * (ins_pt + n_insert), v + ins_pt * elt_sz,
 755                 (len - ins_pt) * elt_sz);
 756   _vec_zero_elts (v, ins_pt, n_insert, elt_sz);
 757   _vec_update_pointer (vp, v);
 758 }
 759
 760 #define vec_insert_init_empty_ha(V, N, M, INIT, H, A)                         \
 761   _vec_insert ((void **) &(V), N, M, INIT, H, _vec_align (V, A),              \
 762                _vec_elt_sz (V))
 763
 764 /** \brief Insert N vector elements starting at element M,
 765     initialize new elements to zero (general version)
 766
 767     @param V (possibly NULL) pointer to a vector.
 768     @param N number of elements to insert
 769     @param M insertion point
 770     @param H header size in bytes (may be zero)
 771     @param A alignment (may be zero)
 772     @return V (value-result macro parameter)
 773 */
 774 #define vec_insert_ha(V,N,M,H,A)    vec_insert_init_empty_ha(V,N,M,0,H,A)
 775
 776 /** \brief Insert N vector elements starting at element M,
 777     initialize new elements to zero (no header, unspecified alignment)
 778
 779     @param V (possibly NULL) pointer to a vector.
 780     @param N number of elements to insert
 781     @param M insertion point
 782     @return V (value-result macro parameter)
 783 */
 784 #define vec_insert(V,N,M)           vec_insert_ha(V,N,M,0,0)
 785
 786 /** \brief Insert N vector elements starting at element M,
 787     initialize new elements to zero (no header, alignment specified)
 788
 789     @param V (possibly NULL) pointer to a vector.
 790     @param N number of elements to insert
 791     @param M insertion point
 792     @param A alignment (may be zero)
 793     @return V (value-result macro parameter)
 794 */
 795 #define vec_insert_aligned(V,N,M,A) vec_insert_ha(V,N,M,0,A)
 796
 797 /** \brief Insert N vector elements starting at element M,
 798     initialize new elements (no header, unspecified alignment)
 799
 800     @param V (possibly NULL) pointer to a vector.
 801     @param N number of elements to insert
 802     @param M insertion point
 803     @param INIT initial value (can be a complex expression!)
 804     @return V (value-result macro parameter)
 805 */
 806
 807 #define vec_insert_init_empty(V,N,M,INIT) \
 808   vec_insert_init_empty_ha(V,N,M,INIT,0,0)
 809 /* Resize vector by N elements starting from element M, initialize new elements to INIT (alignment specified, no header). */
 810
 811 /** \brief Insert N vector elements starting at element M,
 812     initialize new elements (no header, specified alignment)
 813
 814     @param V (possibly NULL) pointer to a vector.
 815     @param N number of elements to insert
 816     @param M insertion point
 817     @param INIT initial value (can be a complex expression!)
 818     @param A alignment (may be zero)
 819     @return V (value-result macro parameter)
 820 */
 821 #define vec_insert_init_empty_aligned(V,N,M,INIT,A) \
 822   vec_insert_init_empty_ha(V,N,M,INIT,0,A)
 823
 824 /** \brief Insert N vector elements starting at element M,
 825     insert given elements (general version)
 826
 827     @param V (possibly NULL) pointer to a vector.
 828     @param E element(s) to insert
 829     @param N number of elements to insert
 830     @param M insertion point
 831     @param H header size in bytes (may be zero)
 832     @param A alignment (may be zero)
 833     @return V (value-result macro parameter)
 834 */
 835
 836 static_always_inline void
 837 _vec_insert_elts (void **vp, void *e, uword n_insert, uword ins_pt,
 838                   uword hdr_sz, uword align, uword elt_sz)
 839 {
 840   void *v = vp[0];
 841   uword len = vec_len (v);
 842
 843   ASSERT (ins_pt <= len);
 844
 845   v = _vec_realloc_inline (v, len + n_insert, elt_sz, hdr_sz, align, 0);
 846   clib_memmove (v + elt_sz * (ins_pt + n_insert), v + ins_pt * elt_sz,
 847                 (len - ins_pt) * elt_sz);
 848   _vec_zero_elts (v, ins_pt, n_insert, elt_sz);
 849   clib_memcpy_fast (v + ins_pt * elt_sz, e, n_insert * elt_sz);
 850   _vec_update_pointer (vp, v);
 851 }
 852
 853 #define vec_insert_elts_ha(V, E, N, M, H, A)                                  \
 854   _vec_insert_elts ((void **) &(V), E, N, M, H, _vec_align (V, A),            \
 855                     _vec_elt_sz (V))
 856
 857 /** \brief Insert N vector elements starting at element M,
 858     insert given elements (no header, unspecified alignment)
 859
 860     @param V (possibly NULL) pointer to a vector.
 861     @param E element(s) to insert
 862     @param N number of elements to insert
 863     @param M insertion point
 864     @return V (value-result macro parameter)
 865 */
 866 #define vec_insert_elts(V,E,N,M)           vec_insert_elts_ha(V,E,N,M,0,0)
 867
 868 /** \brief Insert N vector elements starting at element M,
 869     insert given elements (no header, specified alignment)
 870
 871     @param V (possibly NULL) pointer to a vector.
 872     @param E element(s) to insert
 873     @param N number of elements to insert
 874     @param M insertion point
 875     @param A alignment (may be zero)
 876     @return V (value-result macro parameter)
 877 */
 878 #define vec_insert_elts_aligned(V,E,N,M,A) vec_insert_elts_ha(V,E,N,M,0,A)
 879
 880 /** \brief Delete N elements starting at element M
 881
 882     @param V pointer to a vector
 883     @param N number of elements to delete
 884     @param M first element to delete
 885     @return V (value-result macro parameter)
 886 */
 887
 888 static_always_inline void
 889 _vec_delete (void *v, uword n_del, uword first, uword elt_sz)
 890 {
 891   word n_bytes_del, n_bytes_to_move, len = vec_len (v);
 892   u8 *dst;
 893
 894   if (n_del == 0)
 895     return;
 896
 897   ASSERT (first + n_del <= len);
 898
 899   n_bytes_del = n_del * elt_sz;
 900   n_bytes_to_move = (len - first - n_del) * elt_sz;
 901   dst = v + first * elt_sz;
 902
 903   if (n_bytes_to_move > 0)
 904     clib_memmove (dst, dst + n_bytes_del, n_bytes_to_move);
 905   clib_memset (dst + n_bytes_to_move, 0, n_bytes_del);
 906
 907   _vec_set_len (v, _vec_len (v) - n_del, elt_sz);
 908 }
 909
 910 #define vec_delete(V, N, M) _vec_delete ((void *) (V), N, M, _vec_elt_sz (V))
 911
 912 /** \brief Delete the element at index I
 913
 914     @param V pointer to a vector
 915     @param I index to delete
 916 */
 917
 918 static_always_inline void
 919 _vec_del1 (void *v, uword index, uword elt_sz)
 920 {
 921   uword len = _vec_len (v) - 1;
 922
 923   if (index < len)
 924     clib_memcpy_fast (v + index * elt_sz, v + len * elt_sz, elt_sz);
 925
 926   _vec_set_len (v, len, elt_sz);
 927 }
 928
 929 #define vec_del1(v, i) _vec_del1 ((void *) (v), i, _vec_elt_sz (v))
 930
 931 static_always_inline void
 932 _vec_append (void **v1p, void *v2, uword v1_elt_sz, uword v2_elt_sz,
 933              uword align)
 934 {
 935   void *v1 = v1p[0];
 936   uword len1 = vec_len (v1);
 937   uword len2 = vec_len (v2);
 938
 939   if (PREDICT_TRUE (len2 > 0))
 940     {
 941       v1 = _vec_realloc_inline (v1, len1 + len2, v2_elt_sz, 0, align, 0);
 942       clib_memcpy_fast (v1 + len1 * v1_elt_sz, v2, len2 * v2_elt_sz);
 943       _vec_update_pointer (v1p, v1);
 944     }
 945 }
 946
 947 /** \brief Append v2 after v1. Result in v1. Specified alignment.
 948     @param V1 target vector
 949     @param V2 vector to append
 950     @param align required alignment
 951 */
 952
 953 #define vec_append_aligned(v1, v2, align)                                     \
 954   _vec_append ((void **) &(v1), (void *) (v2), _vec_elt_sz (v1),              \
 955                _vec_elt_sz (v2), _vec_align (v1, align))
 956
 957 /** \brief Append v2 after v1. Result in v1.
 958     @param V1 target vector
 959     @param V2 vector to append
 960 */
 961
 962 #define vec_append(v1, v2) vec_append_aligned (v1, v2, 0)
 963
 964 static_always_inline void
 965 _vec_prepend (void **v1p, void *v2, uword v1_elt_sz, uword v2_elt_sz,
 966               uword align)
 967 {
 968   void *v1 = v1p[0];
 969   uword len1 = vec_len (v1);
 970   uword len2 = vec_len (v2);
 971
 972   if (PREDICT_TRUE (len2 > 0))
 973     {
 974       v1 = _vec_realloc_inline (v1, len1 + len2, v2_elt_sz, 0, align, 0);
 975       clib_memmove (v1 + len2 * v2_elt_sz, v1p[0], len1 * v1_elt_sz);
 976       clib_memcpy_fast (v1, v2, len2 * v2_elt_sz);
 977       _vec_update_pointer (v1p, v1);
 978     }
 979 }
 980
 981 /** \brief Prepend v2 before v1. Result in v1. Specified alignment
 982     @param V1 target vector
 983     @param V2 vector to prepend
 984     @param align required alignment
 985 */
 986
 987 #define vec_prepend_aligned(v1, v2, align)                                    \
 988   _vec_prepend ((void **) &(v1), (void *) (v2), _vec_elt_sz (v1),             \
 989                 _vec_elt_sz (v2), _vec_align (v1, align))
 990
 991 /** \brief Prepend v2 before v1. Result in v1.
 992     @param V1 target vector
 993     @param V2 vector to prepend
 994 */
 995
 996 #define vec_prepend(v1, v2) vec_prepend_aligned (v1, v2, 0)
 997
 998 /** \brief Zero all vector elements. Null-pointer tolerant.
 999     @param var Vector to zero
1000 */
1001 static_always_inline void
1002 _vec_zero (void *v, uword elt_sz)
1003 {
1004   uword len = vec_len (v);
1005
1006   if (len)
1007     clib_memset_u8 (v, 0, len * elt_sz);
1008 }
1009
1010 #define vec_zero(var) _vec_zero ((void *) (var), _vec_elt_sz (var))
1011
1012 /** \brief Set all vector elements to given value. Null-pointer tolerant.
1013     @param v vector to set
1014     @param val value for each vector element
1015 */
1016 #define vec_set(v,val)                          \
1017 do {                                            \
1018   word _v(i);                                   \
1019   __typeof__ ((v)[0]) _val = (val);             \
1020   for (_v(i) = 0; _v(i) < vec_len (v); _v(i)++) \
1021     (v)[_v(i)] = _val;                          \
1022 } while (0)
1023
1024 #ifdef CLIB_UNIX
1025 #include <stdlib.h>             /* for qsort */
1026 #endif
1027
1028 /** \brief Compare two vectors, not NULL-pointer tolerant
1029
1030     @param v1 Pointer to a vector
1031     @param v2 Pointer to a vector
1032     @return 1 if equal, 0 if unequal
1033 */
1034 static_always_inline int
1035 _vec_is_equal (void *v1, void *v2, uword v1_elt_sz, uword v2_elt_sz)
1036 {
1037   uword vec_len_v1 = vec_len (v1);
1038
1039   if ((vec_len_v1 != vec_len (v2)) || (v1_elt_sz != v2_elt_sz))
1040     return 0;
1041
1042   if ((vec_len_v1 == 0) || (memcmp (v1, v2, vec_len_v1 * v1_elt_sz) == 0))
1043     return 1;
1044
1045   return 0;
1046 }
1047
1048 #define vec_is_equal(v1, v2)                                                  \
1049   _vec_is_equal ((void *) (v1), (void *) (v2), _vec_elt_sz (v1),              \
1050                  _vec_elt_sz (v2))
1051
1052 /** \brief Compare two vectors (only applicable to vectors of signed numbers).
1053    Used in qsort compare functions.
1054
1055     @param v1 Pointer to a vector
1056     @param v2 Pointer to a vector
1057     @return -1, 0, +1
1058 */
1059 #define vec_cmp(v1,v2)                                  \
1060 ({                                                      \
1061   word _v(i), _v(cmp), _v(l);                           \
1062   _v(l) = clib_min (vec_len (v1), vec_len (v2));        \
1063   _v(cmp) = 0;                                          \
1064   for (_v(i) = 0; _v(i) < _v(l); _v(i)++) {             \
1065     _v(cmp) = (v1)[_v(i)] - (v2)[_v(i)];                \
1066     if (_v(cmp))                                        \
1067       break;                                            \
1068   }                                                     \
1069   if (_v(cmp) == 0 && _v(l) > 0)                        \
1070     _v(cmp) = vec_len(v1) - vec_len(v2);                \
1071   (_v(cmp) < 0 ? -1 : (_v(cmp) > 0 ? +1 : 0));          \
1072 })
1073
1074 /** \brief Search a vector for the index of the entry that matches.
1075
1076     @param v Pointer to a vector
1077     @param E Entry to match
1078     @return index of match or ~0
1079 */
1080 #define vec_search(v,E)                                 \
1081 ({                                                      \
1082   word _v(i) = 0;                                       \
1083   while (_v(i) < vec_len(v))                            \
1084   {                                                     \
1085     if ((v)[_v(i)] == E)                                        \
1086       break;                                            \
1087     _v(i)++;                                            \
1088   }                                                     \
1089   if (_v(i) == vec_len(v))                              \
1090     _v(i) = ~0;                                         \
1091   _v(i);                                                \
1092 })
1093
1094 /** \brief Search a vector for the index of the entry that matches.
1095
1096     @param v Pointer to a vector
1097     @param E Pointer to entry to match
1098     @param fn Comparison function !0 => match
1099     @return index of match or ~0
1100 */
1101 #define vec_search_with_function(v,E,fn)                \
1102 ({                                                      \
1103   word _v(i) = 0;                                       \
1104   while (_v(i) < vec_len(v))                            \
1105   {                                                     \
1106     if (0 != fn(&(v)[_v(i)], (E)))                      \
1107       break;                                            \
1108     _v(i)++;                                            \
1109   }                                                     \
1110   if (_v(i) == vec_len(v))                              \
1111     _v(i) = ~0;                                         \
1112   _v(i);                                                \
1113 })
1114
1115 /** \brief Sort a vector using the supplied element comparison function
1116
1117     Does not depend on the underlying implementation to deal correctly
1118     with null, zero-long, or 1-long vectors
1119
1120     @param vec vector to sort
1121     @param f comparison function
1122 */
1123 #define vec_sort_with_function(vec,f)                           \
1124 do {                                                            \
1125   if (vec_len (vec) > 1)                                        \
1126     qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f));  \
1127 } while (0)
1128
1129 /** \brief Make a vector containing a NULL terminated c-string.
1130
1131     @param V (possibly NULL) pointer to a vector.
1132     @param S pointer to string buffer.
1133     @param L string length (NOT including the terminating NULL; a la strlen())
1134 */
1135 #define vec_validate_init_c_string(V, S, L)                                   \
1136   do                                                                          \
1137     {                                                                         \
1138       vec_reset_length (V);                                                   \
1139       vec_validate (V, (L));                                                  \
1140       if ((S) && (L))                                                         \
1141         clib_memcpy_fast (V, (S), (L));                                       \
1142       (V)[(L)] = 0;                                                           \
1143     }                                                                         \
1144   while (0)
1145
1146 /** \brief Test whether a vector is a NULL terminated c-string.
1147
1148     @param V (possibly NULL) pointer to a vector.
1149     @return BOOLEAN indicating if the vector c-string is null terminated.
1150 */
1151 #define vec_c_string_is_terminated(V)                   \
1152   (((V) != 0) && (vec_len (V) != 0) && ((V)[vec_len ((V)) - 1] == 0))
1153
1154 /** \brief (If necessary) NULL terminate a vector containing a c-string.
1155
1156     @param V (possibly NULL) pointer to a vector.
1157     @return V (value-result macro parameter)
1158 */
1159 #define vec_terminate_c_string(V)                                             \
1160   do                                                                          \
1161     {                                                                         \
1162       if (!vec_c_string_is_terminated (V))                                    \
1163         vec_add1 (V, 0);                                                      \
1164     }                                                                         \
1165   while (0)
1166
1167 #endif /* included_vec_h */