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