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