src/vppinfra/vec.h

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /*
  16   Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
  17
  18   Permission is hereby granted, free of charge, to any person obtaining
  19   a copy of this software and associated documentation files (the
  20   "Software"), to deal in the Software without restriction, including
  21   without limitation the rights to use, copy, modify, merge, publish,
  22   distribute, sublicense, and/or sell copies of the Software, and to
  23   permit persons to whom the Software is furnished to do so, subject to
  24   the following conditions:
  25
  26   The above copyright notice and this permission notice shall be
  27   included in all copies or substantial portions of the Software.
  28
  29   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  30   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  31   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  32   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  33   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  34   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  35   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  36 */
  37
  38 #ifndef included_vec_h
  39 #define included_vec_h
  40
  41 #include <vppinfra/clib.h>      /* word, etc */
  42 #include <vppinfra/mem.h>       /* clib_mem_free */
  43 #include <vppinfra/string.h>    /* memcpy, memmove */
  44 #include <vppinfra/vec_bootstrap.h>
  45
  46 /** \file
  47
  48    CLIB vectors are ubiquitous dynamically resized arrays with by user
  49    defined "headers".  Many CLIB data structures (e.g. hash, heap,
  50    pool) are vectors with various different headers.
  51
  52    The memory layout looks like this:
  53
  54 ~~~~~~~~
  55                     user header (aligned to uword boundary)
  56                     vector length: number of elements
  57    user's pointer-> vector element #0
  58                     vector element #1
  59                     ...
  60 ~~~~~~~~
  61
  62    The user pointer contains the address of vector element # 0.  Null
  63    pointer vectors are valid and mean a zero length vector.
  64
  65    You can reset the length of an allocated vector to zero via the
  66    vec_reset_length(v) macro, or by setting the vector length field to
  67    zero (e.g. _vec_len (v) = 0). Vec_reset_length(v) preferred: it
  68    understands Null pointers.
  69
  70    Typically, the header is not present.  Headers allow for other
  71    data structures to be built atop CLIB vectors.
  72
  73    Users may specify the alignment for first data element of a vector
  74    via the vec_*_aligned macros.
  75
  76    Vector elements can be any C type e.g. (int, double, struct bar).
  77    This is also true for data types built atop vectors (e.g. heap,
  78    pool, etc.).
  79
  80    Many macros have \_a variants supporting alignment of vector elements
  81    and \_h variants supporting non-zero-length vector headers. The \_ha
  82    variants support both.  Additionally cacheline alignment within a
  83    vector element structure can be specified using the
  84    CLIB_CACHE_LINE_ALIGN_MARK() macro.
  85
  86    Standard programming error: memorize a pointer to the ith element
  87    of a vector then expand it. Vectors expand by 3/2, so such code
  88    may appear to work for a period of time. Memorize vector indices
  89    which are invariant.
  90  */
  91
  92 /** \brief Low-level resize allocation function, usually not called directly
  93
  94     @param v pointer to a vector
  95     @param length_increment length increment in elements
  96     @param data_bytes requested size in bytes
  97     @param header_bytes header size in bytes (may be zero)
  98     @param data_align alignment (may be zero)
  99     @return v_prime pointer to resized vector, may or may not equal v
 100 */
 101 void *vec_resize_allocate_memory (void *v,
 102                                   word length_increment,
 103                                   uword data_bytes,
 104                                   uword header_bytes, uword data_align);
 105
 106 /** \brief Low-level vector resize function, usually not called directly
 107
 108     @param v pointer to a vector
 109     @param length_increment length increment in elements
 110     @param data_bytes requested size in bytes
 111     @param header_bytes header size in bytes (may be zero)
 112     @param data_align alignment (may be zero)
 113     @return v_prime pointer to resized vector, may or may not equal v
 114 */
 115
 116 #define _vec_resize(V,L,DB,HB,A) \
 117   _vec_resize_inline(V,L,DB,HB,clib_max((__alignof__((V)[0])),(A)))
 118
 119 always_inline void *
 120 _vec_resize_inline (void *v,
 121                     word length_increment,
 122                     uword data_bytes, uword header_bytes, uword data_align)
 123 {
 124   vec_header_t *vh = _vec_find (v);
 125   uword new_data_bytes, aligned_header_bytes;
 126
 127   aligned_header_bytes = vec_header_bytes (header_bytes);
 128
 129   new_data_bytes = data_bytes + aligned_header_bytes;
 130
 131   if (PREDICT_TRUE (v != 0))
 132     {
 133       void *p = v - aligned_header_bytes;
 134
 135       /* Vector header must start heap object. */
 136       ASSERT (clib_mem_is_heap_object (p));
 137
 138       /* Typically we'll not need to resize. */
 139       if (new_data_bytes <= clib_mem_size (p))
 140         {
 141           CLIB_MEM_UNPOISON (v, data_bytes);
 142           vh->len += length_increment;
 143           return v;
 144         }
 145     }
 146
 147   /* Slow path: call helper function. */
 148   return vec_resize_allocate_memory (v, length_increment, data_bytes,
 149                                      header_bytes,
 150                                      clib_max (sizeof (vec_header_t),
 151                                                data_align));
 152 }
 153
 154 /** \brief Determine if vector will resize with next allocation
 155
 156     @param v pointer to a vector
 157     @param length_increment length increment in elements
 158     @param data_bytes requested size in bytes
 159     @param header_bytes header size in bytes (may be zero)
 160     @param data_align alignment (may be zero)
 161     @return 1 if vector will resize 0 otherwise
 162 */
 163
 164 always_inline int
 165 _vec_resize_will_expand (void *v,
 166                          word length_increment,
 167                          uword data_bytes, uword header_bytes,
 168                          uword data_align)
 169 {
 170   uword new_data_bytes, aligned_header_bytes;
 171
 172   aligned_header_bytes = vec_header_bytes (header_bytes);
 173
 174   new_data_bytes = data_bytes + aligned_header_bytes;
 175
 176   if (PREDICT_TRUE (v != 0))
 177     {
 178       void *p = v - aligned_header_bytes;
 179
 180       /* Vector header must start heap object. */
 181       ASSERT (clib_mem_is_heap_object (p));
 182
 183       /* Typically we'll not need to resize. */
 184       if (new_data_bytes <= clib_mem_size (p))
 185         return 0;
 186     }
 187   return 1;
 188 }
 189
 190 /** \brief Predicate function, says whether the supplied vector is a clib heap
 191     object (general version).
 192
 193     @param v pointer to a vector
 194     @param header_bytes vector header size in bytes (may be zero)
 195     @return 0 or 1
 196 */
 197 uword clib_mem_is_vec_h (void *v, uword header_bytes);
 198
 199
 200 /** \brief Predicate function, says whether the supplied vector is a clib heap
 201     object
 202
 203     @param v pointer to a vector
 204     @return 0 or 1
 205 */
 206 always_inline uword
 207 clib_mem_is_vec (void *v)
 208 {
 209   return clib_mem_is_vec_h (v, 0);
 210 }
 211
 212 /* Local variable naming macro (prevents collisions with other macro naming). */
 213 #define _v(var) _vec_##var
 214
 215 /** \brief Resize a vector (general version).
 216    Add N elements to end of given vector V, return pointer to start of vector.
 217    Vector will have room for H header bytes and will have user's data aligned
 218    at alignment A (rounded to next power of 2).
 219
 220     @param V pointer to a vector
 221     @param N number of elements to add
 222     @param H header size in bytes (may be zero)
 223     @param A alignment (may be zero)
 224     @return V (value-result macro parameter)
 225 */
 226
 227 #define vec_resize_ha(V,N,H,A)                                                  \
 228 do {                                                                            \
 229   word _v(n) = (N);                                                             \
 230   word _v(l) = vec_len (V);                                                     \
 231   V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A));    \
 232 } while (0)
 233
 234 /** \brief Resize a vector (no header, unspecified alignment)
 235    Add N elements to end of given vector V, return pointer to start of vector.
 236    Vector will have room for H header bytes and will have user's data aligned
 237    at alignment A (rounded to next power of 2).
 238
 239     @param V pointer to a vector
 240     @param N number of elements to add
 241     @return V (value-result macro parameter)
 242 */
 243 #define vec_resize(V,N)     vec_resize_ha(V,N,0,0)
 244
 245 /** \brief Resize a vector (no header, alignment specified).
 246    Add N elements to end of given vector V, return pointer to start of vector.
 247    Vector will have room for H header bytes and will have user's data aligned
 248    at alignment A (rounded to next power of 2).
 249
 250     @param V pointer to a vector
 251     @param N number of elements to add
 252     @param A alignment (may be zero)
 253     @return V (value-result macro parameter)
 254 */
 255
 256 #define vec_resize_aligned(V,N,A) vec_resize_ha(V,N,0,A)
 257
 258 /** \brief Allocate space for N more elements
 259
 260     @param V pointer to a vector
 261     @param N number of elements to add
 262     @param H header size in bytes (may be zero)
 263     @param A alignment (may be zero)
 264     @return V (value-result macro parameter)
 265 */
 266
 267 #define vec_alloc_ha(V,N,H,A)                   \
 268 do {                                            \
 269     uword _v(l) = vec_len (V);                  \
 270     vec_resize_ha (V, N, H, A);                 \
 271     _vec_len (V) = _v(l);                       \
 272 } while (0)
 273
 274 /** \brief Allocate space for N more elements
 275     (no header, unspecified alignment)
 276
 277     @param V pointer to a vector
 278     @param N number of elements to add
 279     @return V (value-result macro parameter)
 280 */
 281 #define vec_alloc(V,N) vec_alloc_ha(V,N,0,0)
 282
 283 /** \brief Allocate space for N more elements (no header, given alignment)
 284     @param V pointer to a vector
 285     @param N number of elements to add
 286     @param A alignment (may be zero)
 287     @return V (value-result macro parameter)
 288 */
 289
 290 #define vec_alloc_aligned(V,N,A) vec_alloc_ha(V,N,0,A)
 291
 292 /** \brief Create new vector of given type and length (general version).
 293     @param T type of elements in new vector
 294     @param N number of elements to add
 295     @param H header size in bytes (may be zero)
 296     @param A alignment (may be zero)
 297     @return V new vector
 298 */
 299 #define vec_new_ha(T,N,H,A)                                     \
 300 ({                                                              \
 301   word _v(n) = (N);                                             \
 302   _vec_resize ((T *) 0, _v(n), _v(n) * sizeof (T), (H), (A));   \
 303 })
 304
 305 /** \brief Create new vector of given type and length
 306     (unspecified alignment, no header).
 307
 308     @param T type of elements in new vector
 309     @param N number of elements to add
 310     @return V new vector
 311 */
 312 #define vec_new(T,N)           vec_new_ha(T,N,0,0)
 313 /** \brief Create new vector of given type and length
 314     (alignment specified, no header).
 315
 316     @param T type of elements in new vector
 317     @param N number of elements to add
 318     @param A alignment (may be zero)
 319     @return V new vector
 320 */
 321 #define vec_new_aligned(T,N,A) vec_new_ha(T,N,0,A)
 322
 323 /** \brief Free vector's memory (general version)
 324
 325     @param V pointer to a vector
 326     @param H size of header in bytes
 327     @return V (value-result parameter, V=0)
 328 */
 329 #define vec_free_h(V,H)                         \
 330 do {                                            \
 331   if (V)                                        \
 332     {                                           \
 333       clib_mem_free (vec_header ((V), (H)));    \
 334       V = 0;                                    \
 335     }                                           \
 336 } while (0)
 337
 338 /** \brief Free vector's memory (no header).
 339     @param V pointer to a vector
 340     @return V (value-result parameter, V=0)
 341 */
 342 #define vec_free(V) vec_free_h(V,0)
 343
 344 /**\brief Free vector user header (syntactic sugar)
 345    @param h vector header
 346    @void
 347 */
 348 #define vec_free_header(h) clib_mem_free (h)
 349
 350 /** \brief Return copy of vector (general version).
 351
 352     @param V pointer to a vector
 353     @param H size of header in bytes
 354     @param A alignment (may be zero)
 355
 356     @return Vdup copy of vector
 357 */
 358
 359 #define vec_dup_ha(V,H,A)                               \
 360 ({                                                      \
 361   __typeof__ ((V)[0]) * _v(v) = 0;                      \
 362   uword _v(l) = vec_len (V);                            \
 363   if (_v(l) > 0)                                        \
 364     {                                                   \
 365       vec_resize_ha (_v(v), _v(l), (H), (A));           \
 366       clib_memcpy_fast (_v(v), (V), _v(l) * sizeof ((V)[0]));\
 367     }                                                   \
 368   _v(v);                                                \
 369 })
 370
 371 /** \brief Return copy of vector (no header, no alignment)
 372
 373     @param V pointer to a vector
 374     @return Vdup copy of vector
 375 */
 376 #define vec_dup(V) vec_dup_ha(V,0,0)
 377
 378 /** \brief Return copy of vector (no header, alignment specified).
 379
 380     @param V pointer to a vector
 381     @param A alignment (may be zero)
 382
 383     @return Vdup copy of vector
 384 */
 385 #define vec_dup_aligned(V,A) vec_dup_ha(V,0,A)
 386
 387 /** \brief Copy a vector, memcpy wrapper. Assumes sizeof(SRC[0]) ==
 388     sizeof(DST[0])
 389
 390     @param DST destination
 391     @param SRC source
 392 */
 393 #define vec_copy(DST,SRC) clib_memcpy_fast (DST, SRC, vec_len (DST) * \
 394                                        sizeof ((DST)[0]))
 395
 396 /** \brief Clone a vector. Make a new vector with the
 397     same size as a given vector but possibly with a different type.
 398
 399     @param NEW_V pointer to new vector
 400     @param OLD_V pointer to old vector
 401 */
 402 #define vec_clone(NEW_V,OLD_V)                                                  \
 403 do {                                                                            \
 404   (NEW_V) = 0;                                                                  \
 405   (NEW_V) = _vec_resize ((NEW_V), vec_len (OLD_V),                              \
 406                          vec_len (OLD_V) * sizeof ((NEW_V)[0]), (0), (0));      \
 407 } while (0)
 408
 409 /** \brief Make sure vector is long enough for given index (general version).
 410
 411     @param V (possibly NULL) pointer to a vector.
 412     @param I vector index which will be valid upon return
 413     @param H header size in bytes (may be zero)
 414     @param A alignment (may be zero)
 415     @return V (value-result macro parameter)
 416 */
 417
 418 #define vec_validate_ha(V,I,H,A)                                        \
 419 do {                                                                    \
 420   STATIC_ASSERT(A==0 || ((A % sizeof(V[0]))==0) || ((sizeof(V[0]) % A) == 0),\
 421                 "vector validate aligned on incorrectly sized object"); \
 422   word _v(i) = (I);                                                     \
 423   word _v(l) = vec_len (V);                                             \
 424   if (_v(i) >= _v(l))                                                   \
 425     {                                                                   \
 426       vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A));               \
 427       /* Must zero new space since user may have previously             \
 428          used e.g. _vec_len (v) -= 10 */                                \
 429       clib_memset ((V) + _v(l), 0, (1 + (_v(i) - _v(l))) * sizeof ((V)[0]));    \
 430     }                                                                   \
 431 } while (0)
 432
 433 /** \brief Make sure vector is long enough for given index
 434     (no header, unspecified alignment)
 435
 436     @param V (possibly NULL) pointer to a vector.
 437     @param I vector index which will be valid upon return
 438     @return V (value-result macro parameter)
 439 */
 440 #define vec_validate(V,I)           vec_validate_ha(V,I,0,0)
 441
 442 /** \brief Make sure vector is long enough for given index
 443     (no header, specified alignment)
 444
 445     @param V (possibly NULL) pointer to a vector.
 446     @param I vector index which will be valid upon return
 447     @param A alignment (may be zero)
 448     @return V (value-result macro parameter)
 449 */
 450
 451 #define vec_validate_aligned(V,I,A) vec_validate_ha(V,I,0,A)
 452
 453 /** \brief Make sure vector is long enough for given index
 454     and initialize empty space (general version)
 455
 456     @param V (possibly NULL) pointer to a vector.
 457     @param I vector index which will be valid upon return
 458     @param INIT initial value (can be a complex expression!)
 459     @param H header size in bytes (may be zero)
 460     @param A alignment (may be zero)
 461     @return V (value-result macro parameter)
 462 */
 463 #define vec_validate_init_empty_ha(V,I,INIT,H,A)                \
 464 do {                                                            \
 465   word _v(i) = (I);                                             \
 466   word _v(l) = vec_len (V);                                     \
 467   if (_v(i) >= _v(l))                                           \
 468     {                                                           \
 469       vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A));       \
 470       while (_v(l) <= _v(i))                                    \
 471         {                                                       \
 472           (V)[_v(l)] = (INIT);                                  \
 473           _v(l)++;                                              \
 474         }                                                       \
 475     }                                                           \
 476 } while (0)
 477
 478 /** \brief Make sure vector is long enough for given index
 479     and initialize empty space (no header, unspecified alignment)
 480
 481     @param V (possibly NULL) pointer to a vector.
 482     @param I vector index which will be valid upon return
 483     @param INIT initial value (can be a complex expression!)
 484     @return V (value-result macro parameter)
 485 */
 486
 487 #define vec_validate_init_empty(V,I,INIT) \
 488   vec_validate_init_empty_ha(V,I,INIT,0,0)
 489
 490 /** \brief Make sure vector is long enough for given index
 491     and initialize empty space (no header, alignment alignment)
 492
 493     @param V (possibly NULL) pointer to a vector.
 494     @param I vector index which will be valid upon return
 495     @param INIT initial value (can be a complex expression!)
 496     @param A alignment (may be zero)
 497     @return V (value-result macro parameter)
 498 */
 499 #define vec_validate_init_empty_aligned(V,I,INIT,A) \
 500   vec_validate_init_empty_ha(V,I,INIT,0,A)
 501
 502 /** \brief Add 1 element to end of vector (general version).
 503
 504     @param V pointer to a vector
 505     @param E element to add
 506     @param H header size in bytes (may be zero)
 507     @param A alignment (may be zero)
 508     @return V (value-result macro parameter)
 509 */
 510 #define vec_add1_ha(V,E,H,A)                                            \
 511 do {                                                                    \
 512   word _v(l) = vec_len (V);                                             \
 513   V = _vec_resize ((V), 1, (_v(l) + 1) * sizeof ((V)[0]), (H), (A));    \
 514   (V)[_v(l)] = (E);                                                     \
 515 } while (0)
 516
 517 /** \brief Add 1 element to end of vector (unspecified alignment).
 518
 519     @param V pointer to a vector
 520     @param E element to add
 521     @return V (value-result macro parameter)
 522 */
 523 #define vec_add1(V,E)           vec_add1_ha(V,E,0,0)
 524
 525 /** \brief Add 1 element to end of vector (alignment specified).
 526
 527     @param V pointer to a vector
 528     @param E element to add
 529     @param A alignment (may be zero)
 530     @return V (value-result macro parameter)
 531 */
 532 #define vec_add1_aligned(V,E,A) vec_add1_ha(V,E,0,A)
 533
 534 /** \brief Add N elements to end of vector V,
 535     return pointer to new elements in P. (general version)
 536
 537     @param V pointer to a vector
 538     @param P pointer to new vector element(s)
 539     @param N number of elements to add
 540     @param H header size in bytes (may be zero)
 541     @param A alignment (may be zero)
 542     @return V and P (value-result macro parameters)
 543 */
 544 #define vec_add2_ha(V,P,N,H,A)                                                  \
 545 do {                                                                            \
 546   word _v(n) = (N);                                                             \
 547   word _v(l) = vec_len (V);                                                     \
 548   V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A));    \
 549   P = (V) + _v(l);                                                              \
 550 } while (0)
 551
 552 /** \brief Add N elements to end of vector V,
 553     return pointer to new elements in P. (no header, unspecified alignment)
 554
 555     @param V pointer to a vector
 556     @param P pointer to new vector element(s)
 557     @param N number of elements to add
 558     @return V and P (value-result macro parameters)
 559 */
 560
 561 #define vec_add2(V,P,N)           vec_add2_ha(V,P,N,0,0)
 562
 563 /** \brief Add N elements to end of vector V,
 564     return pointer to new elements in P. (no header, alignment specified)
 565
 566     @param V pointer to a vector
 567     @param P pointer to new vector element(s)
 568     @param N number of elements to add
 569     @param A alignment (may be zero)
 570     @return V and P (value-result macro parameters)
 571 */
 572
 573 #define vec_add2_aligned(V,P,N,A) vec_add2_ha(V,P,N,0,A)
 574
 575 /** \brief Add N elements to end of vector V (general version)
 576
 577     @param V pointer to a vector
 578     @param E pointer to element(s) to add
 579     @param N number of elements to add
 580     @param H header size in bytes (may be zero)
 581     @param A alignment (may be zero)
 582     @return V (value-result macro parameter)
 583 */
 584 #define vec_add_ha(V,E,N,H,A)                                                   \
 585 do {                                                                            \
 586   word _v(n) = (N);                                                             \
 587   word _v(l) = vec_len (V);                                                     \
 588   V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A));    \
 589   clib_memcpy_fast ((V) + _v(l), (E), _v(n) * sizeof ((V)[0]));                 \
 590 } while (0)
 591
 592 /** \brief Add N elements to end of vector V (no header, unspecified alignment)
 593
 594     @param V pointer to a vector
 595     @param E pointer to element(s) to add
 596     @param N number of elements to add
 597     @return V (value-result macro parameter)
 598 */
 599 #define vec_add(V,E,N)           vec_add_ha(V,E,N,0,0)
 600
 601 /** \brief Add N elements to end of vector V (no header, specified alignment)
 602
 603     @param V pointer to a vector
 604     @param E pointer to element(s) to add
 605     @param N number of elements to add
 606     @param A alignment (may be zero)
 607     @return V (value-result macro parameter)
 608 */
 609 #define vec_add_aligned(V,E,N,A) vec_add_ha(V,E,N,0,A)
 610
 611 /** \brief Returns last element of a vector and decrements its length
 612
 613     @param V pointer to a vector
 614     @return E element removed from the end of the vector
 615 */
 616 #define vec_pop(V)                              \
 617 ({                                              \
 618   uword _v(l) = vec_len (V);                    \
 619   ASSERT (_v(l) > 0);                           \
 620   _v(l) -= 1;                                   \
 621   _vec_len (V) = _v (l);                        \
 622   (V)[_v(l)];                                   \
 623 })
 624
 625 /** \brief Set E to the last element of a vector, decrement vector length
 626     @param V pointer to a vector
 627     @param E pointer to the last vector element
 628     @return E element removed from the end of the vector
 629     (value-result macro parameter
 630 */
 631
 632 #define vec_pop2(V,E)                           \
 633 ({                                              \
 634   uword _v(l) = vec_len (V);                    \
 635   if (_v(l) > 0) (E) = vec_pop (V);             \
 636   _v(l) > 0;                                    \
 637 })
 638
 639 /** \brief Insert N vector elements starting at element M,
 640     initialize new elements (general version).
 641
 642     @param V (possibly NULL) pointer to a vector.
 643     @param N number of elements to insert
 644     @param M insertion point
 645     @param INIT initial value (can be a complex expression!)
 646     @param H header size in bytes (may be zero)
 647     @param A alignment (may be zero)
 648     @return V (value-result macro parameter)
 649 */
 650 #define vec_insert_init_empty_ha(V,N,M,INIT,H,A)        \
 651 do {                                                    \
 652   word _v(l) = vec_len (V);                             \
 653   word _v(n) = (N);                                     \
 654   word _v(m) = (M);                                     \
 655   V = _vec_resize ((V),                                 \
 656                    _v(n),                               \
 657                    (_v(l) + _v(n))*sizeof((V)[0]),      \
 658                    (H), (A));                           \
 659   ASSERT (_v(m) <= _v(l));                              \
 660   memmove ((V) + _v(m) + _v(n),                         \
 661            (V) + _v(m),                                 \
 662            (_v(l) - _v(m)) * sizeof ((V)[0]));          \
 663   clib_memset  ((V) + _v(m), INIT, _v(n) * sizeof ((V)[0]));    \
 664 } while (0)
 665
 666 /** \brief Insert N vector elements starting at element M,
 667     initialize new elements to zero (general version)
 668
 669     @param V (possibly NULL) pointer to a vector.
 670     @param N number of elements to insert
 671     @param M insertion point
 672     @param H header size in bytes (may be zero)
 673     @param A alignment (may be zero)
 674     @return V (value-result macro parameter)
 675 */
 676 #define vec_insert_ha(V,N,M,H,A)    vec_insert_init_empty_ha(V,N,M,0,H,A)
 677
 678 /** \brief Insert N vector elements starting at element M,
 679     initialize new elements to zero (no header, unspecified alignment)
 680
 681     @param V (possibly NULL) pointer to a vector.
 682     @param N number of elements to insert
 683     @param M insertion point
 684     @return V (value-result macro parameter)
 685 */
 686 #define vec_insert(V,N,M)           vec_insert_ha(V,N,M,0,0)
 687
 688 /** \brief Insert N vector elements starting at element M,
 689     initialize new elements to zero (no header, alignment specified)
 690
 691     @param V (possibly NULL) pointer to a vector.
 692     @param N number of elements to insert
 693     @param M insertion point
 694     @param A alignment (may be zero)
 695     @return V (value-result macro parameter)
 696 */
 697 #define vec_insert_aligned(V,N,M,A) vec_insert_ha(V,N,M,0,A)
 698
 699 /** \brief Insert N vector elements starting at element M,
 700     initialize new elements (no header, unspecified alignment)
 701
 702     @param V (possibly NULL) pointer to a vector.
 703     @param N number of elements to insert
 704     @param M insertion point
 705     @param INIT initial value (can be a complex expression!)
 706     @return V (value-result macro parameter)
 707 */
 708
 709 #define vec_insert_init_empty(V,N,M,INIT) \
 710   vec_insert_init_empty_ha(V,N,M,INIT,0,0)
 711 /* Resize vector by N elements starting from element M, initialize new elements to INIT (alignment specified, no header). */
 712
 713 /** \brief Insert N vector elements starting at element M,
 714     initialize new elements (no header, specified alignment)
 715
 716     @param V (possibly NULL) pointer to a vector.
 717     @param N number of elements to insert
 718     @param M insertion point
 719     @param INIT initial value (can be a complex expression!)
 720     @param A alignment (may be zero)
 721     @return V (value-result macro parameter)
 722 */
 723 #define vec_insert_init_empty_aligned(V,N,M,INIT,A) \
 724   vec_insert_init_empty_ha(V,N,M,INIT,0,A)
 725
 726 /** \brief Insert N vector elements starting at element M,
 727     insert given elements (general version)
 728
 729     @param V (possibly NULL) pointer to a vector.
 730     @param E element(s) to insert
 731     @param N number of elements to insert
 732     @param M insertion point
 733     @param H header size in bytes (may be zero)
 734     @param A alignment (may be zero)
 735     @return V (value-result macro parameter)
 736 */
 737
 738 #define vec_insert_elts_ha(V,E,N,M,H,A)                 \
 739 do {                                                    \
 740   word _v(l) = vec_len (V);                             \
 741   word _v(n) = (N);                                     \
 742   word _v(m) = (M);                                     \
 743   V = _vec_resize ((V),                                 \
 744                    _v(n),                               \
 745                    (_v(l) + _v(n))*sizeof((V)[0]),      \
 746                    (H), (A));                           \
 747   ASSERT (_v(m) <= _v(l));                              \
 748   memmove ((V) + _v(m) + _v(n),                         \
 749            (V) + _v(m),                                 \
 750            (_v(l) - _v(m)) * sizeof ((V)[0]));          \
 751   clib_memcpy_fast ((V) + _v(m), (E),                   \
 752                _v(n) * sizeof ((V)[0]));                \
 753 } while (0)
 754
 755 /** \brief Insert N vector elements starting at element M,
 756     insert given elements (no header, unspecified alignment)
 757
 758     @param V (possibly NULL) pointer to a vector.
 759     @param E element(s) to insert
 760     @param N number of elements to insert
 761     @param M insertion point
 762     @return V (value-result macro parameter)
 763 */
 764 #define vec_insert_elts(V,E,N,M)           vec_insert_elts_ha(V,E,N,M,0,0)
 765
 766 /** \brief Insert N vector elements starting at element M,
 767     insert given elements (no header, specified alignment)
 768
 769     @param V (possibly NULL) pointer to a vector.
 770     @param E element(s) to insert
 771     @param N number of elements to insert
 772     @param M insertion point
 773     @param A alignment (may be zero)
 774     @return V (value-result macro parameter)
 775 */
 776 #define vec_insert_elts_aligned(V,E,N,M,A) vec_insert_elts_ha(V,E,N,M,0,A)
 777
 778 /** \brief Delete N elements starting at element M
 779
 780     @param V pointer to a vector
 781     @param N number of elements to delete
 782     @param M first element to delete
 783     @return V (value-result macro parameter)
 784 */
 785 #define vec_delete(V,N,M)                                       \
 786 do {                                                            \
 787   word _v(l) = vec_len (V);                                     \
 788   word _v(n) = (N);                                             \
 789   word _v(m) = (M);                                             \
 790   /* Copy over deleted elements. */                             \
 791   if (_v(l) - _v(n) - _v(m) > 0)                                \
 792     memmove ((V) + _v(m), (V) + _v(m) + _v(n),                  \
 793              (_v(l) - _v(n) - _v(m)) * sizeof ((V)[0]));        \
 794   /* Zero empty space at end (for future re-allocation). */     \
 795   if (_v(n) > 0)                                                \
 796     clib_memset ((V) + _v(l) - _v(n), 0, _v(n) * sizeof ((V)[0]));      \
 797   _vec_len (V) -= _v(n);                                        \
 798   CLIB_MEM_POISON(vec_end(V), _v(n) * sizeof ((V)[0]));         \
 799 } while (0)
 800
 801 /** \brief Delete the element at index I
 802
 803     @param V pointer to a vector
 804     @param I index to delete
 805 */
 806 #define vec_del1(v,i)                           \
 807 do {                                            \
 808   uword _vec_del_l = _vec_len (v) - 1;          \
 809   uword _vec_del_i = (i);                       \
 810   if (_vec_del_i < _vec_del_l)                  \
 811     (v)[_vec_del_i] = (v)[_vec_del_l];          \
 812   _vec_len (v) = _vec_del_l;                    \
 813   CLIB_MEM_POISON(vec_end(v), sizeof ((v)[0])); \
 814 } while (0)
 815
 816 /** \brief Append v2 after v1. Result in v1.
 817     @param V1 target vector
 818     @param V2 vector to append
 819 */
 820
 821 #define vec_append(v1,v2)                                               \
 822 do {                                                                    \
 823   uword _v(l1) = vec_len (v1);                                          \
 824   uword _v(l2) = vec_len (v2);                                          \
 825                                                                         \
 826   v1 = _vec_resize ((v1), _v(l2),                                       \
 827                     (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0);        \
 828   clib_memcpy_fast ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0]));            \
 829 } while (0)
 830
 831 /** \brief Append v2 after v1. Result in v1. Specified alignment.
 832     @param V1 target vector
 833     @param V2 vector to append
 834     @param align required alignment
 835 */
 836
 837 #define vec_append_aligned(v1,v2,align)                                 \
 838 do {                                                                    \
 839   uword _v(l1) = vec_len (v1);                                          \
 840   uword _v(l2) = vec_len (v2);                                          \
 841                                                                         \
 842   v1 = _vec_resize ((v1), _v(l2),                                       \
 843                     (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align);    \
 844   clib_memcpy_fast ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0]));            \
 845 } while (0)
 846
 847 /** \brief Prepend v2 before v1. Result in v1.
 848     @param V1 target vector
 849     @param V2 vector to prepend
 850 */
 851
 852 #define vec_prepend(v1,v2)                                              \
 853 do {                                                                    \
 854   uword _v(l1) = vec_len (v1);                                          \
 855   uword _v(l2) = vec_len (v2);                                          \
 856                                                                         \
 857   v1 = _vec_resize ((v1), _v(l2),                                       \
 858                     (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0);        \
 859   memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0]));             \
 860   clib_memcpy_fast ((v1), (v2), _v(l2) * sizeof ((v2)[0]));                  \
 861 } while (0)
 862
 863 /** \brief Prepend v2 before v1. Result in v1. Specified alignment
 864     @param V1 target vector
 865     @param V2 vector to prepend
 866     @param align required alignment
 867 */
 868
 869 #define vec_prepend_aligned(v1,v2,align)                                \
 870 do {                                                                    \
 871   uword _v(l1) = vec_len (v1);                                          \
 872   uword _v(l2) = vec_len (v2);                                          \
 873                                                                         \
 874   v1 = _vec_resize ((v1), _v(l2),                                       \
 875                     (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align);    \
 876   memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0]));             \
 877   clib_memcpy_fast ((v1), (v2), _v(l2) * sizeof ((v2)[0]));                  \
 878 } while (0)
 879
 880
 881 /** \brief Zero all vector elements. Null-pointer tolerant.
 882     @param var Vector to zero
 883 */
 884 #define vec_zero(var)                                           \
 885 do {                                                            \
 886   if (var)                                                      \
 887     clib_memset ((var), 0, vec_len (var) * sizeof ((var)[0]));  \
 888 } while (0)
 889
 890 /** \brief Set all vector elements to given value. Null-pointer tolerant.
 891     @param v vector to set
 892     @param val value for each vector element
 893 */
 894 #define vec_set(v,val)                          \
 895 do {                                            \
 896   word _v(i);                                   \
 897   __typeof__ ((v)[0]) _val = (val);             \
 898   for (_v(i) = 0; _v(i) < vec_len (v); _v(i)++) \
 899     (v)[_v(i)] = _val;                          \
 900 } while (0)
 901
 902 #ifdef CLIB_UNIX
 903 #include <stdlib.h>             /* for qsort */
 904 #endif
 905
 906 /** \brief Compare two vectors, not NULL-pointer tolerant
 907
 908     @param v1 Pointer to a vector
 909     @param v2 Pointer to a vector
 910     @return 1 if equal, 0 if unequal
 911 */
 912 #define vec_is_equal(v1,v2) \
 913   (vec_len (v1) == vec_len (v2) && ! memcmp ((v1), (v2), vec_len (v1) * sizeof ((v1)[0])))
 914
 915 /** \brief Compare two vectors (only applicable to vectors of signed numbers).
 916    Used in qsort compare functions.
 917
 918     @param v1 Pointer to a vector
 919     @param v2 Pointer to a vector
 920     @return -1, 0, +1
 921 */
 922 #define vec_cmp(v1,v2)                                  \
 923 ({                                                      \
 924   word _v(i), _v(cmp), _v(l);                           \
 925   _v(l) = clib_min (vec_len (v1), vec_len (v2));        \
 926   _v(cmp) = 0;                                          \
 927   for (_v(i) = 0; _v(i) < _v(l); _v(i)++) {             \
 928     _v(cmp) = (v1)[_v(i)] - (v2)[_v(i)];                \
 929     if (_v(cmp))                                        \
 930       break;                                            \
 931   }                                                     \
 932   if (_v(cmp) == 0 && _v(l) > 0)                        \
 933     _v(cmp) = vec_len(v1) - vec_len(v2);                \
 934   (_v(cmp) < 0 ? -1 : (_v(cmp) > 0 ? +1 : 0));          \
 935 })
 936
 937 /** \brief Search a vector for the index of the entry that matches.
 938
 939     @param v Pointer to a vector
 940     @param E Entry to match
 941     @return index of match or ~0
 942 */
 943 #define vec_search(v,E)                                 \
 944 ({                                                      \
 945   word _v(i) = 0;                                       \
 946   while (_v(i) < vec_len(v))                            \
 947   {                                                     \
 948     if ((v)[_v(i)] == E)                                        \
 949       break;                                            \
 950     _v(i)++;                                            \
 951   }                                                     \
 952   if (_v(i) == vec_len(v))                              \
 953     _v(i) = ~0;                                         \
 954   _v(i);                                                \
 955 })
 956
 957 /** \brief Search a vector for the index of the entry that matches.
 958
 959     @param v Pointer to a vector
 960     @param E Pointer to entry to match
 961     @param fn Comparison function !0 => match
 962     @return index of match or ~0
 963 */
 964 #define vec_search_with_function(v,E,fn)                \
 965 ({                                                      \
 966   word _v(i) = 0;                                       \
 967   while (_v(i) < vec_len(v))                            \
 968   {                                                     \
 969     if (0 != fn(&(v)[_v(i)], (E)))                      \
 970       break;                                            \
 971     _v(i)++;                                            \
 972   }                                                     \
 973   if (_v(i) == vec_len(v))                              \
 974     _v(i) = ~0;                                         \
 975   _v(i);                                                \
 976 })
 977
 978 /** \brief Sort a vector using the supplied element comparison function
 979
 980     @param vec vector to sort
 981     @param f comparison function
 982 */
 983 #define vec_sort_with_function(vec,f)                           \
 984 do {                                                            \
 985   qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f));    \
 986 } while (0)
 987
 988 /** \brief Make a vector containing a NULL terminated c-string.
 989
 990     @param V (possibly NULL) pointer to a vector.
 991     @param S pointer to string buffer.
 992     @param L string length (NOT including the terminating NULL; a la strlen())
 993 */
 994 #define vec_validate_init_c_string(V, S, L)     \
 995   do {                                          \
 996     vec_reset_length (V);                       \
 997     vec_validate ((V), (L));                    \
 998     if ((S) && (L))                             \
 999         clib_memcpy_fast ((V), (S), (L));            \
1000     (V)[(L)] = 0;                               \
1001   } while (0)
1002
1003
1004 /** \brief Test whether a vector is a NULL terminated c-string.
1005
1006     @param V (possibly NULL) pointer to a vector.
1007     @return BOOLEAN indicating if the vector c-string is null terminated.
1008 */
1009 #define vec_c_string_is_terminated(V)                   \
1010   (((V) != 0) && (vec_len (V) != 0) && ((V)[vec_len ((V)) - 1] == 0))
1011
1012 /** \brief (If necessary) NULL terminate a vector containing a c-string.
1013
1014     @param V (possibly NULL) pointer to a vector.
1015     @return V (value-result macro parameter)
1016 */
1017 #define vec_terminate_c_string(V)               \
1018   do {                                          \
1019     u32 vl = vec_len ((V));                     \
1020     if (!vec_c_string_is_terminated(V))         \
1021       {                                         \
1022         vec_validate ((V), vl);                 \
1023         (V)[vl] = 0;                            \
1024       }                                         \
1025   } while (0)
1026
1027 #endif /* included_vec_h */
1028
1029
1030 /*
1031  * fd.io coding-style-patch-verification: ON
1032  *
1033  * Local Variables:
1034  * eval: (c-set-style "gnu")
1035  * End:
1036  */