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