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