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