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       clib_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) clib_memcpy (DST, SRC, vec_len (DST) * \
 350                                        sizeof ((DST)[0]))
 351
 352 /** \brief Clone a vector. Make a new vector with the
 353     same size as a given vector but possibly with a different type.
 354
 355     @param NEW_V pointer to new vector
 356     @param OLD_V pointer to old vector
 357 */
 358 #define vec_clone(NEW_V,OLD_V)                                                  \
 359 do {                                                                            \
 360   (NEW_V) = 0;                                                                  \
 361   (NEW_V) = _vec_resize ((NEW_V), vec_len (OLD_V),                              \
 362                          vec_len (OLD_V) * sizeof ((NEW_V)[0]), (0), (0));      \
 363 } while (0)
 364
 365 /** \brief Make sure vector is long enough for given index (general version).
 366
 367     @param V (possibly NULL) pointer to a vector.
 368     @param I vector index which will be valid upon return
 369     @param H header size in bytes (may be zero)
 370     @param A alignment (may be zero)
 371     @return V (value-result macro parameter)
 372 */
 373
 374 #define vec_validate_ha(V,I,H,A)                                        \
 375 do {                                                                    \
 376   word _v(i) = (I);                                                     \
 377   word _v(l) = vec_len (V);                                             \
 378   if (_v(i) >= _v(l))                                                   \
 379     {                                                                   \
 380       vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A));               \
 381       /* Must zero new space since user may have previously             \
 382          used e.g. _vec_len (v) -= 10 */                                \
 383       memset ((V) + _v(l), 0, (1 + (_v(i) - _v(l))) * sizeof ((V)[0])); \
 384     }                                                                   \
 385 } while (0)
 386
 387 /** \brief Make sure vector is long enough for given index
 388     (no header, unspecified alignment)
 389
 390     @param V (possibly NULL) pointer to a vector.
 391     @param I vector index which will be valid upon return
 392     @return V (value-result macro parameter)
 393 */
 394 #define vec_validate(V,I)           vec_validate_ha(V,I,0,0)
 395
 396 /** \brief Make sure vector is long enough for given index
 397     (no header, specified alignment)
 398
 399     @param V (possibly NULL) pointer to a vector.
 400     @param I vector index which will be valid upon return
 401     @param A alignment (may be zero)
 402     @return V (value-result macro parameter)
 403 */
 404
 405 #define vec_validate_aligned(V,I,A) vec_validate_ha(V,I,0,A)
 406
 407 /** \brief Make sure vector is long enough for given index
 408     and initialize empty space (general version)
 409
 410     @param V (possibly NULL) pointer to a vector.
 411     @param I vector index which will be valid upon return
 412     @param INIT initial value (can be a complex expression!)
 413     @param H header size in bytes (may be zero)
 414     @param A alignment (may be zero)
 415     @return V (value-result macro parameter)
 416 */
 417 #define vec_validate_init_empty_ha(V,I,INIT,H,A)                \
 418 do {                                                            \
 419   word _v(i) = (I);                                             \
 420   word _v(l) = vec_len (V);                                     \
 421   if (_v(i) >= _v(l))                                           \
 422     {                                                           \
 423       vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A));       \
 424       while (_v(l) <= _v(i))                                    \
 425         {                                                       \
 426           (V)[_v(l)] = (INIT);                                  \
 427           _v(l)++;                                              \
 428         }                                                       \
 429     }                                                           \
 430 } while (0)
 431
 432 /** \brief Make sure vector is long enough for given index
 433     and initialize empty space (no header, unspecified alignment)
 434
 435     @param V (possibly NULL) pointer to a vector.
 436     @param I vector index which will be valid upon return
 437     @param INIT initial value (can be a complex expression!)
 438     @param H header size in bytes (may be zero)
 439     @param A alignment (may be zero)
 440     @return V (value-result macro parameter)
 441 */
 442
 443 #define vec_validate_init_empty(V,I,INIT) \
 444   vec_validate_init_empty_ha(V,I,INIT,0,0)
 445
 446 /** \brief Make sure vector is long enough for given index
 447     and initialize empty space (no header, alignment alignment)
 448
 449     @param V (possibly NULL) pointer to a vector.
 450     @param I vector index which will be valid upon return
 451     @param INIT initial value (can be a complex expression!)
 452     @param H header size in bytes (may be zero)
 453     @param A alignment (may be zero)
 454     @return V (value-result macro parameter)
 455 */
 456 #define vec_validate_init_empty_aligned(V,I,A) \
 457   vec_validate_init_empty_ha(V,I,INIT,0,A)
 458
 459 /** \brief Add 1 element to end of vector (general version).
 460
 461     @param V pointer to a vector
 462     @param E element to add
 463     @param H header size in bytes (may be zero)
 464     @param A alignment (may be zero)
 465     @return V (value-result macro parameter)
 466 */
 467 #define vec_add1_ha(V,E,H,A)                                            \
 468 do {                                                                    \
 469   word _v(l) = vec_len (V);                                             \
 470   V = _vec_resize ((V), 1, (_v(l) + 1) * sizeof ((V)[0]), (H), (A));    \
 471   (V)[_v(l)] = (E);                                                     \
 472 } while (0)
 473
 474 /** \brief Add 1 element to end of vector (unspecified alignment).
 475
 476     @param V pointer to a vector
 477     @param E element to add
 478     @return V (value-result macro parameter)
 479 */
 480 #define vec_add1(V,E)           vec_add1_ha(V,E,0,0)
 481
 482 /** \brief Add 1 element to end of vector (alignment specified).
 483
 484     @param V pointer to a vector
 485     @param E element to add
 486     @param H header size in bytes (may be zero)
 487     @param A alignment (may be zero)
 488     @return V (value-result macro parameter)
 489 */
 490 #define vec_add1_aligned(V,E,A) vec_add1_ha(V,E,0,A)
 491
 492 /** \brief Add N elements to end of vector V,
 493     return pointer to new elements in P. (general version)
 494
 495     @param V pointer to a vector
 496     @param P pointer to new vector element(s)
 497     @param N number of elements to add
 498     @param H header size in bytes (may be zero)
 499     @param A alignment (may be zero)
 500     @return V and P (value-result macro parameters)
 501 */
 502 #define vec_add2_ha(V,P,N,H,A)                                                  \
 503 do {                                                                            \
 504   word _v(n) = (N);                                                             \
 505   word _v(l) = vec_len (V);                                                     \
 506   V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A));    \
 507   P = (V) + _v(l);                                                              \
 508 } while (0)
 509
 510 /** \brief Add N elements to end of vector V,
 511     return pointer to new elements in P. (no header, unspecified alignment)
 512
 513     @param V pointer to a vector
 514     @param P pointer to new vector element(s)
 515     @param N number of elements to add
 516     @return V and P (value-result macro parameters)
 517 */
 518
 519 #define vec_add2(V,P,N)           vec_add2_ha(V,P,N,0,0)
 520
 521 /** \brief Add N elements to end of vector V,
 522     return pointer to new elements in P. (no header, alignment specified)
 523
 524     @param V pointer to a vector
 525     @param P pointer to new vector element(s)
 526     @param N number of elements to add
 527     @param A alignment (may be zero)
 528     @return V and P (value-result macro parameters)
 529 */
 530
 531 #define vec_add2_aligned(V,P,N,A) vec_add2_ha(V,P,N,0,A)
 532
 533 /** \brief Add N elements to end of vector V (general version)
 534
 535     @param V pointer to a vector
 536     @param E pointer to element(s) to add
 537     @param N number of elements to add
 538     @param H header size in bytes (may be zero)
 539     @param A alignment (may be zero)
 540     @return V (value-result macro parameter)
 541 */
 542 #define vec_add_ha(V,E,N,H,A)                                                   \
 543 do {                                                                            \
 544   word _v(n) = (N);                                                             \
 545   word _v(l) = vec_len (V);                                                     \
 546   V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A));    \
 547   clib_memcpy ((V) + _v(l), (E), _v(n) * sizeof ((V)[0]));                      \
 548 } while (0)
 549
 550 /** \brief Add N elements to end of vector V (no header, unspecified alignment)
 551
 552     @param V pointer to a vector
 553     @param E pointer to element(s) to add
 554     @param N number of elements to add
 555     @return V (value-result macro parameter)
 556 */
 557 #define vec_add(V,E,N)           vec_add_ha(V,E,N,0,0)
 558
 559 /** \brief Add N elements to end of vector V (no header, specified alignment)
 560
 561     @param V pointer to a vector
 562     @param E pointer to element(s) to add
 563     @param N number of elements to add
 564     @param A alignment (may be zero)
 565     @return V (value-result macro parameter)
 566 */
 567 #define vec_add_aligned(V,E,N,A) vec_add_ha(V,E,N,0,A)
 568
 569 /** \brief Returns last element of a vector and decrements its length
 570
 571     @param V pointer to a vector
 572     @return E element removed from the end of the vector
 573 */
 574 #define vec_pop(V)                              \
 575 ({                                              \
 576   uword _v(l) = vec_len (V);                    \
 577   ASSERT (_v(l) > 0);                           \
 578   _v(l) -= 1;                                   \
 579   _vec_len (V) = _v (l);                        \
 580   (V)[_v(l)];                                   \
 581 })
 582
 583 /** \brief Set E to the last element of a vector, decrement vector length
 584     @param V pointer to a vector
 585     @param E pointer to the last vector element
 586     @return E element removed from the end of the vector
 587     (value-result macro parameter
 588 */
 589
 590 #define vec_pop2(V,E)                           \
 591 ({                                              \
 592   uword _v(l) = vec_len (V);                    \
 593   if (_v(l) > 0) (E) = vec_pop (V);             \
 594   _v(l) > 0;                                    \
 595 })
 596
 597 /** \brief Insert N vector elements starting at element M,
 598     initialize new elements (general version).
 599
 600     @param V (possibly NULL) pointer to a vector.
 601     @param N number of elements to insert
 602     @param M insertion point
 603     @param INIT initial value (can be a complex expression!)
 604     @param H header size in bytes (may be zero)
 605     @param A alignment (may be zero)
 606     @return V (value-result macro parameter)
 607 */
 608 #define vec_insert_init_empty_ha(V,N,M,INIT,H,A)        \
 609 do {                                                    \
 610   word _v(l) = vec_len (V);                             \
 611   word _v(n) = (N);                                     \
 612   word _v(m) = (M);                                     \
 613   V = _vec_resize ((V),                                 \
 614                    _v(n),                               \
 615                    (_v(l) + _v(n))*sizeof((V)[0]),      \
 616                    (H), (A));                           \
 617   ASSERT (_v(m) <= _v(l));                              \
 618   memmove ((V) + _v(m) + _v(n),                         \
 619            (V) + _v(m),                                 \
 620            (_v(l) - _v(m)) * sizeof ((V)[0]));          \
 621   memset  ((V) + _v(m), INIT, _v(n) * sizeof ((V)[0])); \
 622 } while (0)
 623
 624 /** \brief Insert N vector elements starting at element M,
 625     initialize new elements to zero (general version)
 626
 627     @param V (possibly NULL) pointer to a vector.
 628     @param N number of elements to insert
 629     @param M insertion point
 630     @param H header size in bytes (may be zero)
 631     @param A alignment (may be zero)
 632     @return V (value-result macro parameter)
 633 */
 634 #define vec_insert_ha(V,N,M,H,A)    vec_insert_init_empty_ha(V,N,M,0,H,A)
 635
 636 /** \brief Insert N vector elements starting at element M,
 637     initialize new elements to zero (no header, unspecified alignment)
 638
 639     @param V (possibly NULL) pointer to a vector.
 640     @param N number of elements to insert
 641     @param M insertion point
 642     @return V (value-result macro parameter)
 643 */
 644 #define vec_insert(V,N,M)           vec_insert_ha(V,N,M,0,0)
 645
 646 /** \brief Insert N vector elements starting at element M,
 647     initialize new elements to zero (no header, alignment specified)
 648
 649     @param V (possibly NULL) pointer to a vector.
 650     @param N number of elements to insert
 651     @param M insertion point
 652     @param A alignment (may be zero)
 653     @return V (value-result macro parameter)
 654 */
 655 #define vec_insert_aligned(V,N,M,A) vec_insert_ha(V,N,M,0,A)
 656
 657 /** \brief Insert N vector elements starting at element M,
 658     initialize new elements (no header, unspecified alignment)
 659
 660     @param V (possibly NULL) pointer to a vector.
 661     @param N number of elements to insert
 662     @param M insertion point
 663     @param INIT initial value (can be a complex expression!)
 664     @return V (value-result macro parameter)
 665 */
 666
 667 #define vec_insert_init_empty(V,N,M,INIT) \
 668   vec_insert_init_empty_ha(V,N,M,INIT,0,0)
 669 /* Resize vector by N elements starting from element M, initialize new elements to INIT (alignment specified, no header). */
 670
 671 /** \brief Insert N vector elements starting at element M,
 672     initialize new elements (no header, specified alignment)
 673
 674     @param V (possibly NULL) pointer to a vector.
 675     @param N number of elements to insert
 676     @param M insertion point
 677     @param INIT initial value (can be a complex expression!)
 678     @param A alignment (may be zero)
 679     @return V (value-result macro parameter)
 680 */
 681 #define vec_insert_init_empty_aligned(V,N,M,INIT,A) \
 682   vec_insert_init_empty_ha(V,N,M,INIT,0,A)
 683
 684 /** \brief Insert N vector elements starting at element M,
 685     insert given elements (general version)
 686
 687     @param V (possibly NULL) pointer to a vector.
 688     @param E element(s) to insert
 689     @param N number of elements to insert
 690     @param M insertion point
 691     @param H header size in bytes (may be zero)
 692     @param A alignment (may be zero)
 693     @return V (value-result macro parameter)
 694 */
 695
 696 #define vec_insert_elts_ha(V,E,N,M,H,A)                 \
 697 do {                                                    \
 698   word _v(l) = vec_len (V);                             \
 699   word _v(n) = (N);                                     \
 700   word _v(m) = (M);                                     \
 701   V = _vec_resize ((V),                                 \
 702                    _v(n),                               \
 703                    (_v(l) + _v(n))*sizeof((V)[0]),      \
 704                    (H), (A));                           \
 705   ASSERT (_v(m) <= _v(l));                              \
 706   memmove ((V) + _v(m) + _v(n),                         \
 707            (V) + _v(m),                                 \
 708            (_v(l) - _v(m)) * sizeof ((V)[0]));          \
 709   clib_memcpy ((V) + _v(m), (E),                        \
 710                _v(n) * sizeof ((V)[0]));                \
 711 } while (0)
 712
 713 /** \brief Insert N vector elements starting at element M,
 714     insert given elements (no header, unspecified alignment)
 715
 716     @param V (possibly NULL) pointer to a vector.
 717     @param E element(s) to insert
 718     @param N number of elements to insert
 719     @param M insertion point
 720     @return V (value-result macro parameter)
 721 */
 722 #define vec_insert_elts(V,E,N,M)           vec_insert_elts_ha(V,E,N,M,0,0)
 723
 724 /** \brief Insert N vector elements starting at element M,
 725     insert given elements (no header, specified alignment)
 726
 727     @param V (possibly NULL) pointer to a vector.
 728     @param E element(s) to insert
 729     @param N number of elements to insert
 730     @param M insertion point
 731     @param A alignment (may be zero)
 732     @return V (value-result macro parameter)
 733 */
 734 #define vec_insert_elts_aligned(V,E,N,M,A) vec_insert_elts_ha(V,E,N,M,0,A)
 735
 736 /** \brief Delete N elements starting at element M
 737
 738     @param V pointer to a vector
 739     @param N number of elements to delete
 740     @param M first element to delete
 741     @return V (value-result macro parameter)
 742 */
 743 #define vec_delete(V,N,M)                                       \
 744 do {                                                            \
 745   word _v(l) = vec_len (V);                                     \
 746   word _v(n) = (N);                                             \
 747   word _v(m) = (M);                                             \
 748   /* Copy over deleted elements. */                             \
 749   if (_v(l) - _v(n) - _v(m) > 0)                                \
 750     memmove ((V) + _v(m), (V) + _v(m) + _v(n),                  \
 751              (_v(l) - _v(n) - _v(m)) * sizeof ((V)[0]));        \
 752   /* Zero empty space at end (for future re-allocation). */     \
 753   if (_v(n) > 0)                                                \
 754     memset ((V) + _v(l) - _v(n), 0, _v(n) * sizeof ((V)[0]));   \
 755   _vec_len (V) -= _v(n);                                        \
 756 } while (0)
 757
 758 /** \brief Delete the element at index I
 759
 760     @param V pointer to a vector
 761     @param I index to delete
 762 */
 763 #define vec_del1(v,i)                           \
 764 do {                                            \
 765   uword _vec_del_l = _vec_len (v) - 1;          \
 766   uword _vec_del_i = (i);                       \
 767   if (_vec_del_i < _vec_del_l)                  \
 768     (v)[_vec_del_i] = (v)[_vec_del_l];          \
 769   _vec_len (v) = _vec_del_l;                    \
 770 } while (0)
 771
 772 /** \brief Append v2 after v1. Result in v1.
 773     @param V1 target vector
 774     @param V2 vector to append
 775 */
 776
 777 #define vec_append(v1,v2)                                               \
 778 do {                                                                    \
 779   uword _v(l1) = vec_len (v1);                                          \
 780   uword _v(l2) = vec_len (v2);                                          \
 781                                                                         \
 782   v1 = _vec_resize ((v1), _v(l2),                                       \
 783                     (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0);        \
 784   clib_memcpy ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0]));         \
 785 } while (0)
 786
 787 /** \brief Append v2 after v1. Result in v1. Specified alignment.
 788     @param V1 target vector
 789     @param V2 vector to append
 790     @param align required alignment
 791 */
 792
 793 #define vec_append_aligned(v1,v2,align)                                 \
 794 do {                                                                    \
 795   uword _v(l1) = vec_len (v1);                                          \
 796   uword _v(l2) = vec_len (v2);                                          \
 797                                                                         \
 798   v1 = _vec_resize ((v1), _v(l2),                                       \
 799                     (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align);    \
 800   clib_memcpy ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0]));         \
 801 } while (0)
 802
 803 /** \brief Prepend v2 before v1. Result in v1.
 804     @param V1 target vector
 805     @param V2 vector to prepend
 806 */
 807
 808 #define vec_prepend(v1,v2)                                              \
 809 do {                                                                    \
 810   uword _v(l1) = vec_len (v1);                                          \
 811   uword _v(l2) = vec_len (v2);                                          \
 812                                                                         \
 813   v1 = _vec_resize ((v1), _v(l2),                                       \
 814                     (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0);        \
 815   memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0]));             \
 816   clib_memcpy ((v1), (v2), _v(l2) * sizeof ((v2)[0]));                  \
 817 } while (0)
 818
 819 /** \brief Prepend v2 before v1. Result in v1. Specified alignment
 820     @param V1 target vector
 821     @param V2 vector to prepend
 822     @param align required alignment
 823 */
 824
 825 #define vec_prepend_aligned(v1,v2,align)                                \
 826 do {                                                                    \
 827   uword _v(l1) = vec_len (v1);                                          \
 828   uword _v(l2) = vec_len (v2);                                          \
 829                                                                         \
 830   v1 = _vec_resize ((v1), _v(l2),                                       \
 831                     (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align);    \
 832   memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0]));             \
 833   clib_memcpy ((v1), (v2), _v(l2) * sizeof ((v2)[0]));                  \
 834 } while (0)
 835
 836
 837 /** \brief Zero all vector elements. Null-pointer tolerant.
 838     @param var Vector to zero
 839 */
 840 #define vec_zero(var)                                           \
 841 do {                                                            \
 842   if (var)                                                      \
 843     memset ((var), 0, vec_len (var) * sizeof ((var)[0]));       \
 844 } while (0)
 845
 846 /** \brief Set all vector elements to given value. Null-pointer tolerant.
 847     @param v vector to set
 848     @param val value for each vector element
 849 */
 850 #define vec_set(v,val)                          \
 851 do {                                            \
 852   word _v(i);                                   \
 853   __typeof__ ((v)[0]) _val = (val);             \
 854   for (_v(i) = 0; _v(i) < vec_len (v); _v(i)++) \
 855     (v)[_v(i)] = _val;                          \
 856 } while (0)
 857
 858 #ifdef CLIB_UNIX
 859 #include <stdlib.h>             /* for qsort */
 860 #endif
 861
 862 /** \brief Compare two vectors, not NULL-pointer tolerant
 863
 864     @param v1 Pointer to a vector
 865     @param v2 Pointer to a vector
 866     @return 1 if equal, 0 if unequal
 867 */
 868 #define vec_is_equal(v1,v2) \
 869   (vec_len (v1) == vec_len (v2) && ! memcmp ((v1), (v2), vec_len (v1) * sizeof ((v1)[0])))
 870
 871 /** \brief Compare two vectors (only applicable to vectors of signed numbers).
 872    Used in qsort compare functions.
 873
 874     @param v1 Pointer to a vector
 875     @param v2 Pointer to a vector
 876     @return -1, 0, +1
 877 */
 878 #define vec_cmp(v1,v2)                                  \
 879 ({                                                      \
 880   word _v(i), _v(cmp), _v(l);                           \
 881   _v(l) = clib_min (vec_len (v1), vec_len (v2));        \
 882   _v(cmp) = 0;                                          \
 883   for (_v(i) = 0; _v(i) < _v(l); _v(i)++) {             \
 884     _v(cmp) = (v1)[_v(i)] - (v2)[_v(i)];                \
 885     if (_v(cmp))                                        \
 886       break;                                            \
 887   }                                                     \
 888   if (_v(cmp) == 0 && _v(l) > 0)                        \
 889     _v(cmp) = vec_len(v1) - vec_len(v2);                \
 890   (_v(cmp) < 0 ? -1 : (_v(cmp) > 0 ? +1 : 0));          \
 891 })
 892
 893 /** \brief Sort a vector using the supplied element comparison function
 894
 895     @param vec vector to sort
 896     @param f comparison function
 897 */
 898 #define vec_sort_with_function(vec,f)                           \
 899 do {                                                            \
 900   qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f));    \
 901 } while (0)
 902
 903 /** \brief Make a vector containing a NULL terminated c-string.
 904
 905     @param V (possibly NULL) pointer to a vector.
 906     @param S pointer to string buffer.
 907     @param L string length (NOT including the terminating NULL; a la strlen())
 908 */
 909 #define vec_validate_init_c_string(V, S, L)     \
 910   do {                                          \
 911     vec_reset_length (V);                       \
 912     vec_validate ((V), (L));                    \
 913     if ((S) && (L))                             \
 914         clib_memcpy ((V), (S), (L));            \
 915     (V)[(L)] = 0;                               \
 916   } while (0)
 917
 918
 919 /** \brief Test whether a vector is a NULL terminated c-string.
 920
 921     @param V (possibly NULL) pointer to a vector.
 922     @return BOOLEAN indicating if the vector c-string is null terminated.
 923 */
 924 #define vec_c_string_is_terminated(V)                   \
 925   (((V) != 0) && (vec_len (V) != 0) && ((V)[vec_len ((V)) - 1] == 0))
 926
 927 /** \brief (If necessary) NULL terminate a vector containing a c-string.
 928
 929     @param V (possibly NULL) pointer to a vector.
 930     @return V (value-result macro parameter)
 931 */
 932 #define vec_terminate_c_string(V)               \
 933   do {                                          \
 934     u32 vl = vec_len ((V));                     \
 935     if (!vec_c_string_is_terminated(V))         \
 936       {                                         \
 937         vec_validate ((V), vl);                 \
 938         (V)[vl] = 0;                            \
 939       }                                         \
 940   } while (0)
 941
 942 #endif /* included_vec_h */
 943