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     @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 A alignment (may be zero)
 496     @return V (value-result macro parameter)
 497 */
 498 #define vec_validate_init_empty_aligned(V,I,INIT,A) \
 499   vec_validate_init_empty_ha(V,I,INIT,0,A)
 500
 501 /** \brief Add 1 element to end of vector (general version).
 502
 503     @param V pointer to a vector
 504     @param E element to add
 505     @param H header size in bytes (may be zero)
 506     @param A alignment (may be zero)
 507     @return V (value-result macro parameter)
 508 */
 509 #define vec_add1_ha(V,E,H,A)                                            \
 510 do {                                                                    \
 511   word _v(l) = vec_len (V);                                             \
 512   V = _vec_resize ((V), 1, (_v(l) + 1) * sizeof ((V)[0]), (H), (A));    \
 513   (V)[_v(l)] = (E);                                                     \
 514 } while (0)
 515
 516 /** \brief Add 1 element to end of vector (unspecified alignment).
 517
 518     @param V pointer to a vector
 519     @param E element to add
 520     @return V (value-result macro parameter)
 521 */
 522 #define vec_add1(V,E)           vec_add1_ha(V,E,0,0)
 523
 524 /** \brief Add 1 element to end of vector (alignment specified).
 525
 526     @param V pointer to a vector
 527     @param E element to add
 528     @param A alignment (may be zero)
 529     @return V (value-result macro parameter)
 530 */
 531 #define vec_add1_aligned(V,E,A) vec_add1_ha(V,E,0,A)
 532
 533 /** \brief Add N elements to end of vector V,
 534     return pointer to new elements in P. (general version)
 535
 536     @param V pointer to a vector
 537     @param P pointer to new vector element(s)
 538     @param N number of elements to add
 539     @param H header size in bytes (may be zero)
 540     @param A alignment (may be zero)
 541     @return V and P (value-result macro parameters)
 542 */
 543 #define vec_add2_ha(V,P,N,H,A)                                                  \
 544 do {                                                                            \
 545   word _v(n) = (N);                                                             \
 546   word _v(l) = vec_len (V);                                                     \
 547   V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A));    \
 548   P = (V) + _v(l);                                                              \
 549 } while (0)
 550
 551 /** \brief Add N elements to end of vector V,
 552     return pointer to new elements in P. (no header, unspecified alignment)
 553
 554     @param V pointer to a vector
 555     @param P pointer to new vector element(s)
 556     @param N number of elements to add
 557     @return V and P (value-result macro parameters)
 558 */
 559
 560 #define vec_add2(V,P,N)           vec_add2_ha(V,P,N,0,0)
 561
 562 /** \brief Add N elements to end of vector V,
 563     return pointer to new elements in P. (no header, alignment specified)
 564
 565     @param V pointer to a vector
 566     @param P pointer to new vector element(s)
 567     @param N number of elements to add
 568     @param A alignment (may be zero)
 569     @return V and P (value-result macro parameters)
 570 */
 571
 572 #define vec_add2_aligned(V,P,N,A) vec_add2_ha(V,P,N,0,A)
 573
 574 /** \brief Add N elements to end of vector V (general version)
 575
 576     @param V pointer to a vector
 577     @param E pointer to element(s) to add
 578     @param N number of elements to add
 579     @param H header size in bytes (may be zero)
 580     @param A alignment (may be zero)
 581     @return V (value-result macro parameter)
 582 */
 583 #define vec_add_ha(V,E,N,H,A)                                                   \
 584 do {                                                                            \
 585   word _v(n) = (N);                                                             \
 586   word _v(l) = vec_len (V);                                                     \
 587   V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A));    \
 588   clib_memcpy_fast ((V) + _v(l), (E), _v(n) * sizeof ((V)[0]));                 \
 589 } while (0)
 590
 591 /** \brief Add N elements to end of vector V (no header, unspecified alignment)
 592
 593     @param V pointer to a vector
 594     @param E pointer to element(s) to add
 595     @param N number of elements to add
 596     @return V (value-result macro parameter)
 597 */
 598 #define vec_add(V,E,N)           vec_add_ha(V,E,N,0,0)
 599
 600 /** \brief Add N elements to end of vector V (no header, specified alignment)
 601
 602     @param V pointer to a vector
 603     @param E pointer to element(s) to add
 604     @param N number of elements to add
 605     @param A alignment (may be zero)
 606     @return V (value-result macro parameter)
 607 */
 608 #define vec_add_aligned(V,E,N,A) vec_add_ha(V,E,N,0,A)
 609
 610 /** \brief Returns last element of a vector and decrements its length
 611
 612     @param V pointer to a vector
 613     @return E element removed from the end of the vector
 614 */
 615 #define vec_pop(V)                              \
 616 ({                                              \
 617   uword _v(l) = vec_len (V);                    \
 618   ASSERT (_v(l) > 0);                           \
 619   _v(l) -= 1;                                   \
 620   _vec_len (V) = _v (l);                        \
 621   (V)[_v(l)];                                   \
 622 })
 623
 624 /** \brief Set E to the last element of a vector, decrement vector length
 625     @param V pointer to a vector
 626     @param E pointer to the last vector element
 627     @return E element removed from the end of the vector
 628     (value-result macro parameter
 629 */
 630
 631 #define vec_pop2(V,E)                           \
 632 ({                                              \
 633   uword _v(l) = vec_len (V);                    \
 634   if (_v(l) > 0) (E) = vec_pop (V);             \
 635   _v(l) > 0;                                    \
 636 })
 637
 638 /** \brief Insert N vector elements starting at element M,
 639     initialize new elements (general version).
 640
 641     @param V (possibly NULL) pointer to a vector.
 642     @param N number of elements to insert
 643     @param M insertion point
 644     @param INIT initial value (can be a complex expression!)
 645     @param H header size in bytes (may be zero)
 646     @param A alignment (may be zero)
 647     @return V (value-result macro parameter)
 648 */
 649 #define vec_insert_init_empty_ha(V,N,M,INIT,H,A)        \
 650 do {                                                    \
 651   word _v(l) = vec_len (V);                             \
 652   word _v(n) = (N);                                     \
 653   word _v(m) = (M);                                     \
 654   V = _vec_resize ((V),                                 \
 655                    _v(n),                               \
 656                    (_v(l) + _v(n))*sizeof((V)[0]),      \
 657                    (H), (A));                           \
 658   ASSERT (_v(m) <= _v(l));                              \
 659   memmove ((V) + _v(m) + _v(n),                         \
 660            (V) + _v(m),                                 \
 661            (_v(l) - _v(m)) * sizeof ((V)[0]));          \
 662   clib_memset  ((V) + _v(m), INIT, _v(n) * sizeof ((V)[0]));    \
 663 } while (0)
 664
 665 /** \brief Insert N vector elements starting at element M,
 666     initialize new elements to zero (general version)
 667
 668     @param V (possibly NULL) pointer to a vector.
 669     @param N number of elements to insert
 670     @param M insertion point
 671     @param H header size in bytes (may be zero)
 672     @param A alignment (may be zero)
 673     @return V (value-result macro parameter)
 674 */
 675 #define vec_insert_ha(V,N,M,H,A)    vec_insert_init_empty_ha(V,N,M,0,H,A)
 676
 677 /** \brief Insert N vector elements starting at element M,
 678     initialize new elements to zero (no header, unspecified alignment)
 679
 680     @param V (possibly NULL) pointer to a vector.
 681     @param N number of elements to insert
 682     @param M insertion point
 683     @return V (value-result macro parameter)
 684 */
 685 #define vec_insert(V,N,M)           vec_insert_ha(V,N,M,0,0)
 686
 687 /** \brief Insert N vector elements starting at element M,
 688     initialize new elements to zero (no header, alignment specified)
 689
 690     @param V (possibly NULL) pointer to a vector.
 691     @param N number of elements to insert
 692     @param M insertion point
 693     @param A alignment (may be zero)
 694     @return V (value-result macro parameter)
 695 */
 696 #define vec_insert_aligned(V,N,M,A) vec_insert_ha(V,N,M,0,A)
 697
 698 /** \brief Insert N vector elements starting at element M,
 699     initialize new elements (no header, unspecified alignment)
 700
 701     @param V (possibly NULL) pointer to a vector.
 702     @param N number of elements to insert
 703     @param M insertion point
 704     @param INIT initial value (can be a complex expression!)
 705     @return V (value-result macro parameter)
 706 */
 707
 708 #define vec_insert_init_empty(V,N,M,INIT) \
 709   vec_insert_init_empty_ha(V,N,M,INIT,0,0)
 710 /* Resize vector by N elements starting from element M, initialize new elements to INIT (alignment specified, no header). */
 711
 712 /** \brief Insert N vector elements starting at element M,
 713     initialize new elements (no header, specified alignment)
 714
 715     @param V (possibly NULL) pointer to a vector.
 716     @param N number of elements to insert
 717     @param M insertion point
 718     @param INIT initial value (can be a complex expression!)
 719     @param A alignment (may be zero)
 720     @return V (value-result macro parameter)
 721 */
 722 #define vec_insert_init_empty_aligned(V,N,M,INIT,A) \
 723   vec_insert_init_empty_ha(V,N,M,INIT,0,A)
 724
 725 /** \brief Insert N vector elements starting at element M,
 726     insert given elements (general version)
 727
 728     @param V (possibly NULL) pointer to a vector.
 729     @param E element(s) to insert
 730     @param N number of elements to insert
 731     @param M insertion point
 732     @param H header size in bytes (may be zero)
 733     @param A alignment (may be zero)
 734     @return V (value-result macro parameter)
 735 */
 736
 737 #define vec_insert_elts_ha(V,E,N,M,H,A)                 \
 738 do {                                                    \
 739   word _v(l) = vec_len (V);                             \
 740   word _v(n) = (N);                                     \
 741   word _v(m) = (M);                                     \
 742   V = _vec_resize ((V),                                 \
 743                    _v(n),                               \
 744                    (_v(l) + _v(n))*sizeof((V)[0]),      \
 745                    (H), (A));                           \
 746   ASSERT (_v(m) <= _v(l));                              \
 747   memmove ((V) + _v(m) + _v(n),                         \
 748            (V) + _v(m),                                 \
 749            (_v(l) - _v(m)) * sizeof ((V)[0]));          \
 750   clib_memcpy_fast ((V) + _v(m), (E),                   \
 751                _v(n) * sizeof ((V)[0]));                \
 752 } while (0)
 753
 754 /** \brief Insert N vector elements starting at element M,
 755     insert given elements (no header, unspecified alignment)
 756
 757     @param V (possibly NULL) pointer to a vector.
 758     @param E element(s) to insert
 759     @param N number of elements to insert
 760     @param M insertion point
 761     @return V (value-result macro parameter)
 762 */
 763 #define vec_insert_elts(V,E,N,M)           vec_insert_elts_ha(V,E,N,M,0,0)
 764
 765 /** \brief Insert N vector elements starting at element M,
 766     insert given elements (no header, specified alignment)
 767
 768     @param V (possibly NULL) pointer to a vector.
 769     @param E element(s) to insert
 770     @param N number of elements to insert
 771     @param M insertion point
 772     @param A alignment (may be zero)
 773     @return V (value-result macro parameter)
 774 */
 775 #define vec_insert_elts_aligned(V,E,N,M,A) vec_insert_elts_ha(V,E,N,M,0,A)
 776
 777 /** \brief Delete N elements starting at element M
 778
 779     @param V pointer to a vector
 780     @param N number of elements to delete
 781     @param M first element to delete
 782     @return V (value-result macro parameter)
 783 */
 784 #define vec_delete(V,N,M)                                       \
 785 do {                                                            \
 786   word _v(l) = vec_len (V);                                     \
 787   word _v(n) = (N);                                             \
 788   word _v(m) = (M);                                             \
 789   /* Copy over deleted elements. */                             \
 790   if (_v(l) - _v(n) - _v(m) > 0)                                \
 791     memmove ((V) + _v(m), (V) + _v(m) + _v(n),                  \
 792              (_v(l) - _v(n) - _v(m)) * sizeof ((V)[0]));        \
 793   /* Zero empty space at end (for future re-allocation). */     \
 794   if (_v(n) > 0)                                                \
 795     clib_memset ((V) + _v(l) - _v(n), 0, _v(n) * sizeof ((V)[0]));      \
 796   _vec_len (V) -= _v(n);                                        \
 797 } while (0)
 798
 799 /** \brief Delete the element at index I
 800
 801     @param V pointer to a vector
 802     @param I index to delete
 803 */
 804 #define vec_del1(v,i)                           \
 805 do {                                            \
 806   uword _vec_del_l = _vec_len (v) - 1;          \
 807   uword _vec_del_i = (i);                       \
 808   if (_vec_del_i < _vec_del_l)                  \
 809     (v)[_vec_del_i] = (v)[_vec_del_l];          \
 810   _vec_len (v) = _vec_del_l;                    \
 811 } while (0)
 812
 813 /** \brief Append v2 after v1. Result in v1.
 814     @param V1 target vector
 815     @param V2 vector to append
 816 */
 817
 818 #define vec_append(v1,v2)                                               \
 819 do {                                                                    \
 820   uword _v(l1) = vec_len (v1);                                          \
 821   uword _v(l2) = vec_len (v2);                                          \
 822                                                                         \
 823   v1 = _vec_resize ((v1), _v(l2),                                       \
 824                     (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0);        \
 825   clib_memcpy_fast ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0]));            \
 826 } while (0)
 827
 828 /** \brief Append v2 after v1. Result in v1. Specified alignment.
 829     @param V1 target vector
 830     @param V2 vector to append
 831     @param align required alignment
 832 */
 833
 834 #define vec_append_aligned(v1,v2,align)                                 \
 835 do {                                                                    \
 836   uword _v(l1) = vec_len (v1);                                          \
 837   uword _v(l2) = vec_len (v2);                                          \
 838                                                                         \
 839   v1 = _vec_resize ((v1), _v(l2),                                       \
 840                     (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align);    \
 841   clib_memcpy_fast ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0]));            \
 842 } while (0)
 843
 844 /** \brief Prepend v2 before v1. Result in v1.
 845     @param V1 target vector
 846     @param V2 vector to prepend
 847 */
 848
 849 #define vec_prepend(v1,v2)                                              \
 850 do {                                                                    \
 851   uword _v(l1) = vec_len (v1);                                          \
 852   uword _v(l2) = vec_len (v2);                                          \
 853                                                                         \
 854   v1 = _vec_resize ((v1), _v(l2),                                       \
 855                     (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0);        \
 856   memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0]));             \
 857   clib_memcpy_fast ((v1), (v2), _v(l2) * sizeof ((v2)[0]));                  \
 858 } while (0)
 859
 860 /** \brief Prepend v2 before v1. Result in v1. Specified alignment
 861     @param V1 target vector
 862     @param V2 vector to prepend
 863     @param align required alignment
 864 */
 865
 866 #define vec_prepend_aligned(v1,v2,align)                                \
 867 do {                                                                    \
 868   uword _v(l1) = vec_len (v1);                                          \
 869   uword _v(l2) = vec_len (v2);                                          \
 870                                                                         \
 871   v1 = _vec_resize ((v1), _v(l2),                                       \
 872                     (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align);    \
 873   memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0]));             \
 874   clib_memcpy_fast ((v1), (v2), _v(l2) * sizeof ((v2)[0]));                  \
 875 } while (0)
 876
 877
 878 /** \brief Zero all vector elements. Null-pointer tolerant.
 879     @param var Vector to zero
 880 */
 881 #define vec_zero(var)                                           \
 882 do {                                                            \
 883   if (var)                                                      \
 884     clib_memset ((var), 0, vec_len (var) * sizeof ((var)[0]));  \
 885 } while (0)
 886
 887 /** \brief Set all vector elements to given value. Null-pointer tolerant.
 888     @param v vector to set
 889     @param val value for each vector element
 890 */
 891 #define vec_set(v,val)                          \
 892 do {                                            \
 893   word _v(i);                                   \
 894   __typeof__ ((v)[0]) _val = (val);             \
 895   for (_v(i) = 0; _v(i) < vec_len (v); _v(i)++) \
 896     (v)[_v(i)] = _val;                          \
 897 } while (0)
 898
 899 #ifdef CLIB_UNIX
 900 #include <stdlib.h>             /* for qsort */
 901 #endif
 902
 903 /** \brief Compare two vectors, not NULL-pointer tolerant
 904
 905     @param v1 Pointer to a vector
 906     @param v2 Pointer to a vector
 907     @return 1 if equal, 0 if unequal
 908 */
 909 #define vec_is_equal(v1,v2) \
 910   (vec_len (v1) == vec_len (v2) && ! memcmp ((v1), (v2), vec_len (v1) * sizeof ((v1)[0])))
 911
 912 /** \brief Compare two vectors (only applicable to vectors of signed numbers).
 913    Used in qsort compare functions.
 914
 915     @param v1 Pointer to a vector
 916     @param v2 Pointer to a vector
 917     @return -1, 0, +1
 918 */
 919 #define vec_cmp(v1,v2)                                  \
 920 ({                                                      \
 921   word _v(i), _v(cmp), _v(l);                           \
 922   _v(l) = clib_min (vec_len (v1), vec_len (v2));        \
 923   _v(cmp) = 0;                                          \
 924   for (_v(i) = 0; _v(i) < _v(l); _v(i)++) {             \
 925     _v(cmp) = (v1)[_v(i)] - (v2)[_v(i)];                \
 926     if (_v(cmp))                                        \
 927       break;                                            \
 928   }                                                     \
 929   if (_v(cmp) == 0 && _v(l) > 0)                        \
 930     _v(cmp) = vec_len(v1) - vec_len(v2);                \
 931   (_v(cmp) < 0 ? -1 : (_v(cmp) > 0 ? +1 : 0));          \
 932 })
 933
 934 /** \brief Search a vector for the index of the entry that matches.
 935
 936     @param v Pointer to a vector
 937     @param E Entry to match
 938     @return index of match or ~0
 939 */
 940 #define vec_search(v,E)                                 \
 941 ({                                                      \
 942   word _v(i) = 0;                                       \
 943   while (_v(i) < vec_len(v))                            \
 944   {                                                     \
 945     if ((v)[_v(i)] == E)                                        \
 946       break;                                            \
 947     _v(i)++;                                            \
 948   }                                                     \
 949   if (_v(i) == vec_len(v))                              \
 950     _v(i) = ~0;                                         \
 951   _v(i);                                                \
 952 })
 953
 954 /** \brief Search a vector for the index of the entry that matches.
 955
 956     @param v Pointer to a vector
 957     @param E Pointer to entry to match
 958     @param fn Comparison function !0 => match
 959     @return index of match or ~0
 960 */
 961 #define vec_search_with_function(v,E,fn)                \
 962 ({                                                      \
 963   word _v(i) = 0;                                       \
 964   while (_v(i) < vec_len(v))                            \
 965   {                                                     \
 966     if (0 != fn(&(v)[_v(i)], (E)))                      \
 967       break;                                            \
 968     _v(i)++;                                            \
 969   }                                                     \
 970   if (_v(i) == vec_len(v))                              \
 971     _v(i) = ~0;                                         \
 972   _v(i);                                                \
 973 })
 974
 975 /** \brief Sort a vector using the supplied element comparison function
 976
 977     @param vec vector to sort
 978     @param f comparison function
 979 */
 980 #define vec_sort_with_function(vec,f)                           \
 981 do {                                                            \
 982   qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f));    \
 983 } while (0)
 984
 985 /** \brief Make a vector containing a NULL terminated c-string.
 986
 987     @param V (possibly NULL) pointer to a vector.
 988     @param S pointer to string buffer.
 989     @param L string length (NOT including the terminating NULL; a la strlen())
 990 */
 991 #define vec_validate_init_c_string(V, S, L)     \
 992   do {                                          \
 993     vec_reset_length (V);                       \
 994     vec_validate ((V), (L));                    \
 995     if ((S) && (L))                             \
 996         clib_memcpy_fast ((V), (S), (L));            \
 997     (V)[(L)] = 0;                               \
 998   } while (0)
 999
1000
1001 /** \brief Test whether a vector is a NULL terminated c-string.
1002
1003     @param V (possibly NULL) pointer to a vector.
1004     @return BOOLEAN indicating if the vector c-string is null terminated.
1005 */
1006 #define vec_c_string_is_terminated(V)                   \
1007   (((V) != 0) && (vec_len (V) != 0) && ((V)[vec_len ((V)) - 1] == 0))
1008
1009 /** \brief (If necessary) NULL terminate a vector containing a c-string.
1010
1011     @param V (possibly NULL) pointer to a vector.
1012     @return V (value-result macro parameter)
1013 */
1014 #define vec_terminate_c_string(V)               \
1015   do {                                          \
1016     u32 vl = vec_len ((V));                     \
1017     if (!vec_c_string_is_terminated(V))         \
1018       {                                         \
1019         vec_validate ((V), vl);                 \
1020         (V)[vl] = 0;                            \
1021       }                                         \
1022   } while (0)
1023
1024 #endif /* included_vec_h */
1025
1026
1027 /*
1028  * fd.io coding-style-patch-verification: ON
1029  *
1030  * Local Variables:
1031  * eval: (c-set-style "gnu")
1032  * End:
1033  */