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