src/vppinfra/vec.h

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /*
  16   Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
  17
  18   Permission is hereby granted, free of charge, to any person obtaining
  19   a copy of this software and associated documentation files (the
  20   "Software"), to deal in the Software without restriction, including
  21   without limitation the rights to use, copy, modify, merge, publish,
  22   distribute, sublicense, and/or sell copies of the Software, and to
  23   permit persons to whom the Software is furnished to do so, subject to
  24   the following conditions:
  25
  26   The above copyright notice and this permission notice shall be
  27   included in all copies or substantial portions of the Software.
  28
  29   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  30   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  31   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  32   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  33   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  34   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  35   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  36 */
  37
  38 #ifndef included_vec_h
  39 #define included_vec_h
  40
  41 #include <vppinfra/clib.h>      /* word, etc */
  42 #include <vppinfra/mem.h>       /* clib_mem_free */
  43 #include <vppinfra/string.h>    /* memcpy, memmove */
  44 #include <vppinfra/vec_bootstrap.h>
  45
  46 /** \file
  47
  48    CLIB vectors are ubiquitous dynamically resized arrays with by user
  49    defined "headers".  Many CLIB data structures (e.g. hash, heap,
  50    pool) are vectors with various different headers.
  51
  52    The memory layout looks like this:
  53
  54 ~~~~~~~~
  55                     user header (aligned to uword boundary)
  56                     vector length: number of elements
  57    user's pointer-> vector element #0
  58                     vector element #1
  59                     ...
  60 ~~~~~~~~
  61
  62    The user pointer contains the address of vector element # 0.  Null
  63    pointer vectors are valid and mean a zero length vector.
  64
  65    You can reset the length of an allocated vector to zero via the
  66    vec_reset_length(v) macro, or by setting the vector length field to
  67    zero (e.g. _vec_len (v) = 0). Vec_reset_length(v) preferred: it
  68    understands Null pointers.
  69
  70    Typically, the header is not present.  Headers allow for other
  71    data structures to be built atop CLIB vectors.
  72
  73    Users may specify the alignment for data elements via the
  74    vec_*_aligned macros.
  75
  76    Vectors elements can be any C type e.g. (int, double, struct bar).
  77    This is also true for data types built atop vectors (e.g. heap,
  78    pool, etc.).
  79
  80    Many macros have _a variants supporting alignment of vector data
  81    and _h variants supporting non zero length vector headers.
  82    The _ha variants support both.
  83
  84    Standard programming error: memorize a pointer to the ith element
  85    of a vector then expand it. Vectors expand by 3/2, so such code
  86    may appear to work for a period of time. Memorize vector indices
  87    which are invariant.
  88  */
  89
  90 /** \brief Low-level resize allocation function, usually not called directly
  91
  92     @param v pointer to a vector
  93     @param length_increment length increment in elements
  94     @param data_bytes requested size in bytes
  95     @param header_bytes header size in bytes (may be zero)
  96     @param data_align alignment (may be zero)
  97     @return v_prime pointer to resized vector, may or may not equal v
  98 */
  99 void *vec_resize_allocate_memory (void *v,
 100                                   word length_increment,
 101                                   uword data_bytes,
 102                                   uword header_bytes, uword data_align);
 103
 104 /** \brief Low-level vector resize function, usually not called directly
 105
 106     @param v pointer to a vector
 107     @param length_increment length increment in elements
 108     @param data_bytes requested size in bytes
 109     @param header_bytes header size in bytes (may be zero)
 110     @param data_align alignment (may be zero)
 111     @return v_prime pointer to resized vector, may or may not equal v
 112 */
 113
 114 always_inline void *
 115 _vec_resize (void *v,
 116              word length_increment,
 117              uword data_bytes, uword header_bytes, uword data_align)
 118 {
 119   vec_header_t *vh = _vec_find (v);
 120   uword new_data_bytes, aligned_header_bytes;
 121
 122   aligned_header_bytes = vec_header_bytes (header_bytes);
 123
 124   new_data_bytes = data_bytes + aligned_header_bytes;
 125
 126   if (PREDICT_TRUE (v != 0))
 127     {
 128       void *p = v - aligned_header_bytes;
 129
 130       /* Vector header must start heap object. */
 131       ASSERT (clib_mem_is_heap_object (p));
 132
 133       /* Typically we'll not need to resize. */
 134       if (new_data_bytes <= clib_mem_size (p))
 135         {
 136           vh->len += length_increment;
 137           return v;
 138         }
 139     }
 140
 141   /* Slow path: call helper function. */
 142   return vec_resize_allocate_memory (v, length_increment, data_bytes,
 143                                      header_bytes,
 144                                      clib_max (sizeof (vec_header_t),
 145                                                data_align));
 146 }
 147
 148 /** \brief Low-level vector resize predicate
 149
 150     @param v pointer to a vector
 151     @param length_increment length increment in elements
 152     @param data_bytes requested size in bytes
 153     @param header_bytes header size in bytes (may be zero)
 154     @param data_align alignment (may be zero)
 155     @return v_prime pointer to resized vector, may or may not equal v
 156 */
 157
 158 always_inline int
 159 _vec_resize_will_expand (void *v,
 160                          word length_increment,
 161                          uword data_bytes, uword header_bytes,
 162                          uword data_align)
 163 {
 164   vec_header_t *vh = _vec_find (v);
 165   uword new_data_bytes, aligned_header_bytes;
 166
 167   aligned_header_bytes = vec_header_bytes (header_bytes);
 168
 169   new_data_bytes = data_bytes + aligned_header_bytes;
 170
 171   if (PREDICT_TRUE (v != 0))
 172     {
 173       void *p = v - aligned_header_bytes;
 174
 175       /* Vector header must start heap object. */
 176       ASSERT (clib_mem_is_heap_object (p));
 177
 178       /* Typically we'll not need to resize. */
 179       if (new_data_bytes <= clib_mem_size (p))
 180         {
 181           vh->len += length_increment;
 182           return 0;
 183         }
 184     }
 185   return 1;
 186 }
 187
 188 /** \brief Predicate function, says whether the supplied vector is a clib heap
 189     object (general version).
 190
 191     @param v pointer to a vector
 192     @param header_bytes vector header size in bytes (may be zero)
 193     @return 0 or 1
 194 */
 195 uword clib_mem_is_vec_h (void *v, uword header_bytes);
 196
 197
 198 /** \brief Predicate function, says whether the supplied vector is a clib heap
 199     object
 200
 201     @param v pointer to a vector
 202     @return 0 or 1
 203 */
 204 always_inline uword
 205 clib_mem_is_vec (void *v)
 206 {
 207   return clib_mem_is_vec_h (v, 0);
 208 }
 209
 210 /* Local variable naming macro (prevents collisions with other macro naming). */
 211 #define _v(var) _vec_##var
 212
 213 /** \brief Resize a vector (general version).
 214    Add N elements to end of given vector V, return pointer to start of vector.
 215    Vector will have room for H header bytes and will have user's data aligned
 216    at alignment A (rounded to next power of 2).
 217
 218     @param V pointer to a vector
 219     @param N number of elements to add
 220     @param H header size in bytes (may be zero)
 221     @param A alignment (may be zero)
 222     @return V (value-result macro parameter)
 223 */
 224
 225 #define vec_resize_ha(V,N,H,A)                                                  \
 226 do {                                                                            \
 227   word _v(n) = (N);                                                             \
 228   word _v(l) = vec_len (V);                                                     \
 229   V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A));    \
 230 } while (0)
 231
 232 /** \brief Resize a vector (no header, unspecified alignment)
 233    Add N elements to end of given vector V, return pointer to start of vector.
 234    Vector will have room for H header bytes and will have user's data aligned
 235    at alignment A (rounded to next power of 2).
 236
 237     @param V pointer to a vector
 238     @param N number of elements to add
 239     @return V (value-result macro parameter)
 240 */
 241 #define vec_resize(V,N)     vec_resize_ha(V,N,0,0)
 242
 243 /** \brief Resize a vector (no header, alignment specified).
 244    Add N elements to end of given vector V, return pointer to start of vector.
 245    Vector will have room for H header bytes and will have user's data aligned
 246    at alignment A (rounded to next power of 2).
 247
 248     @param V pointer to a vector
 249     @param N number of elements to add
 250     @param A alignment (may be zero)
 251     @return V (value-result macro parameter)
 252 */
 253
 254 #define vec_resize_aligned(V,N,A) vec_resize_ha(V,N,0,A)
 255
 256 /** \brief Allocate space for N more elements
 257
 258     @param V pointer to a vector
 259     @param N number of elements to add
 260     @param H header size in bytes (may be zero)
 261     @param A alignment (may be zero)
 262     @return V (value-result macro parameter)
 263 */
 264
 265 #define vec_alloc_ha(V,N,H,A)                   \
 266 do {                                            \
 267     uword _v(l) = vec_len (V);                  \
 268     vec_resize_ha (V, N, H, A);                 \
 269     _vec_len (V) = _v(l);                       \
 270 } while (0)
 271
 272 /** \brief Allocate space for N more elements
 273     (no header, unspecified alignment)
 274
 275     @param V pointer to a vector
 276     @param N number of elements to add
 277     @return V (value-result macro parameter)
 278 */
 279 #define vec_alloc(V,N) vec_alloc_ha(V,N,0,0)
 280
 281 /** \brief Allocate space for N more elements (no header, given alignment)
 282     @param V pointer to a vector
 283     @param N number of elements to add
 284     @param A alignment (may be zero)
 285     @return V (value-result macro parameter)
 286 */
 287
 288 #define vec_alloc_aligned(V,N,A) vec_alloc_ha(V,N,0,A)
 289
 290 /** \brief Create new vector of given type and length (general version).
 291     @param T type of elements in new vector
 292     @param N number of elements to add
 293     @param H header size in bytes (may be zero)
 294     @param A alignment (may be zero)
 295     @return V new vector
 296 */
 297 #define vec_new_ha(T,N,H,A)                                     \
 298 ({                                                              \
 299   word _v(n) = (N);                                             \
 300   _vec_resize ((T *) 0, _v(n), _v(n) * sizeof (T), (H), (A));   \
 301 })
 302
 303 /** \brief Create new vector of given type and length
 304     (unspecified alignment, no header).
 305
 306     @param T type of elements in new vector
 307     @param N number of elements to add
 308     @return V new vector
 309 */
 310 #define vec_new(T,N)           vec_new_ha(T,N,0,0)
 311 /** \brief Create new vector of given type and length
 312     (alignment specified, no header).
 313
 314     @param T type of elements in new vector
 315     @param N number of elements to add
 316     @param A alignment (may be zero)
 317     @return V new vector
 318 */
 319 #define vec_new_aligned(T,N,A) vec_new_ha(T,N,0,A)
 320
 321 /** \brief Free vector's memory (general version)
 322
 323     @param V pointer to a vector
 324     @param H size of header in bytes
 325     @return V (value-result parameter, V=0)
 326 */
 327 #define vec_free_h(V,H)                         \
 328 do {                                            \
 329   if (V)                                        \
 330     {                                           \
 331       clib_mem_free (vec_header ((V), (H)));    \
 332       V = 0;                                    \
 333     }                                           \
 334 } while (0)
 335
 336 /** \brief Free vector's memory (no header).
 337     @param V pointer to a vector
 338     @return V (value-result parameter, V=0)
 339 */
 340 #define vec_free(V) vec_free_h(V,0)
 341
 342 /**\brief Free vector user header (syntactic sugar)
 343    @param h vector header
 344    @void
 345 */
 346 #define vec_free_header(h) clib_mem_free (h)
 347
 348 /** \brief Return copy of vector (general version).
 349
 350     @param V pointer to a vector
 351     @param H size of header in bytes
 352     @param A alignment (may be zero)
 353
 354     @return Vdup copy of vector
 355 */
 356
 357 #define vec_dup_ha(V,H,A)                               \
 358 ({                                                      \
 359   __typeof__ ((V)[0]) * _v(v) = 0;                      \
 360   uword _v(l) = vec_len (V);                            \
 361   if (_v(l) > 0)                                        \
 362     {                                                   \
 363       vec_resize_ha (_v(v), _v(l), (H), (A));           \
 364       clib_memcpy (_v(v), (V), _v(l) * sizeof ((V)[0]));\
 365     }                                                   \
 366   _v(v);                                                \
 367 })
 368
 369 /** \brief Return copy of vector (no header, no alignment)
 370
 371     @param V pointer to a vector
 372     @return Vdup copy of vector
 373 */
 374 #define vec_dup(V) vec_dup_ha(V,0,0)
 375
 376 /** \brief Return copy of vector (no header, alignment specified).
 377
 378     @param V pointer to a vector
 379     @param A alignment (may be zero)
 380
 381     @return Vdup copy of vector
 382 */
 383 #define vec_dup_aligned(V,A) vec_dup_ha(V,0,A)
 384
 385 /** \brief Copy a vector, memcpy wrapper. Assumes sizeof(SRC[0]) ==
 386     sizeof(DST[0])
 387
 388     @param DST destination
 389     @param SRC source
 390 */
 391 #define vec_copy(DST,SRC) clib_memcpy (DST, SRC, vec_len (DST) * \
 392                                        sizeof ((DST)[0]))
 393
 394 /** \brief Clone a vector. Make a new vector with the
 395     same size as a given vector but possibly with a different type.
 396
 397     @param NEW_V pointer to new vector
 398     @param OLD_V pointer to old vector
 399 */
 400 #define vec_clone(NEW_V,OLD_V)                                                  \
 401 do {                                                                            \
 402   (NEW_V) = 0;                                                                  \
 403   (NEW_V) = _vec_resize ((NEW_V), vec_len (OLD_V),                              \
 404                          vec_len (OLD_V) * sizeof ((NEW_V)[0]), (0), (0));      \
 405 } while (0)
 406
 407 /** \brief Make sure vector is long enough for given index (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 H header size in bytes (may be zero)
 412     @param A alignment (may be zero)
 413     @return V (value-result macro parameter)
 414 */
 415
 416 #define vec_validate_ha(V,I,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       /* Must zero new space since user may have previously             \
 424          used e.g. _vec_len (v) -= 10 */                                \
 425       memset ((V) + _v(l), 0, (1 + (_v(i) - _v(l))) * sizeof ((V)[0])); \
 426     }                                                                   \
 427 } while (0)
 428
 429 /** \brief Make sure vector is long enough for given index
 430     (no header, unspecified alignment)
 431
 432     @param V (possibly NULL) pointer to a vector.
 433     @param I vector index which will be valid upon return
 434     @return V (value-result macro parameter)
 435 */
 436 #define vec_validate(V,I)           vec_validate_ha(V,I,0,0)
 437
 438 /** \brief Make sure vector is long enough for given index
 439     (no header, specified alignment)
 440
 441     @param V (possibly NULL) pointer to a vector.
 442     @param I vector index which will be valid upon return
 443     @param A alignment (may be zero)
 444     @return V (value-result macro parameter)
 445 */
 446
 447 #define vec_validate_aligned(V,I,A) vec_validate_ha(V,I,0,A)
 448
 449 /** \brief Make sure vector is long enough for given index
 450     and initialize empty space (general version)
 451
 452     @param V (possibly NULL) pointer to a vector.
 453     @param I vector index which will be valid upon return
 454     @param INIT initial value (can be a complex expression!)
 455     @param H header size in bytes (may be zero)
 456     @param A alignment (may be zero)
 457     @return V (value-result macro parameter)
 458 */
 459 #define vec_validate_init_empty_ha(V,I,INIT,H,A)                \
 460 do {                                                            \
 461   word _v(i) = (I);                                             \
 462   word _v(l) = vec_len (V);                                     \
 463   if (_v(i) >= _v(l))                                           \
 464     {                                                           \
 465       vec_resize_ha ((V), 1 + (_v(i) - _v(l)), (H), (A));       \
 466       while (_v(l) <= _v(i))                                    \
 467         {                                                       \
 468           (V)[_v(l)] = (INIT);                                  \
 469           _v(l)++;                                              \
 470         }                                                       \
 471     }                                                           \
 472 } while (0)
 473
 474 /** \brief Make sure vector is long enough for given index
 475     and initialize empty space (no header, unspecified alignment)
 476
 477     @param V (possibly NULL) pointer to a vector.
 478     @param I vector index which will be valid upon return
 479     @param INIT initial value (can be a complex expression!)
 480     @param H header size in bytes (may be zero)
 481     @param A alignment (may be zero)
 482     @return V (value-result macro parameter)
 483 */
 484
 485 #define vec_validate_init_empty(V,I,INIT) \
 486   vec_validate_init_empty_ha(V,I,INIT,0,0)
 487
 488 /** \brief Make sure vector is long enough for given index
 489     and initialize empty space (no header, alignment alignment)
 490
 491     @param V (possibly NULL) pointer to a vector.
 492     @param I vector index which will be valid upon return
 493     @param INIT initial value (can be a complex expression!)
 494     @param H header size in bytes (may be zero)
 495     @param A alignment (may be zero)
 496     @return V (value-result macro parameter)
 497 */
 498 #define vec_validate_init_empty_aligned(V,I,INIT,A) \
 499   vec_validate_init_empty_ha(V,I,INIT,0,A)
 500
 501 /** \brief Add 1 element to end of vector (general version).
 502
 503     @param V pointer to a vector
 504     @param E element to add
 505     @param H header size in bytes (may be zero)
 506     @param A alignment (may be zero)
 507     @return V (value-result macro parameter)
 508 */
 509 #define vec_add1_ha(V,E,H,A)                                            \
 510 do {                                                                    \
 511   word _v(l) = vec_len (V);                                             \
 512   V = _vec_resize ((V), 1, (_v(l) + 1) * sizeof ((V)[0]), (H), (A));    \
 513   (V)[_v(l)] = (E);                                                     \
 514 } while (0)
 515
 516 /** \brief Add 1 element to end of vector (unspecified alignment).
 517
 518     @param V pointer to a vector
 519     @param E element to add
 520     @return V (value-result macro parameter)
 521 */
 522 #define vec_add1(V,E)           vec_add1_ha(V,E,0,0)
 523
 524 /** \brief Add 1 element to end of vector (alignment specified).
 525
 526     @param V pointer to a vector
 527     @param E element to add
 528     @param H header size in bytes (may be zero)
 529     @param A alignment (may be zero)
 530     @return V (value-result macro parameter)
 531 */
 532 #define vec_add1_aligned(V,E,A) vec_add1_ha(V,E,0,A)
 533
 534 /** \brief Add N elements to end of vector V,
 535     return pointer to new elements in P. (general version)
 536
 537     @param V pointer to a vector
 538     @param P pointer to new vector element(s)
 539     @param N number of elements to add
 540     @param H header size in bytes (may be zero)
 541     @param A alignment (may be zero)
 542     @return V and P (value-result macro parameters)
 543 */
 544 #define vec_add2_ha(V,P,N,H,A)                                                  \
 545 do {                                                                            \
 546   word _v(n) = (N);                                                             \
 547   word _v(l) = vec_len (V);                                                     \
 548   V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A));    \
 549   P = (V) + _v(l);                                                              \
 550 } while (0)
 551
 552 /** \brief Add N elements to end of vector V,
 553     return pointer to new elements in P. (no header, unspecified alignment)
 554
 555     @param V pointer to a vector
 556     @param P pointer to new vector element(s)
 557     @param N number of elements to add
 558     @return V and P (value-result macro parameters)
 559 */
 560
 561 #define vec_add2(V,P,N)           vec_add2_ha(V,P,N,0,0)
 562
 563 /** \brief Add N elements to end of vector V,
 564     return pointer to new elements in P. (no header, alignment specified)
 565
 566     @param V pointer to a vector
 567     @param P pointer to new vector element(s)
 568     @param N number of elements to add
 569     @param A alignment (may be zero)
 570     @return V and P (value-result macro parameters)
 571 */
 572
 573 #define vec_add2_aligned(V,P,N,A) vec_add2_ha(V,P,N,0,A)
 574
 575 /** \brief Add N elements to end of vector V (general version)
 576
 577     @param V pointer to a vector
 578     @param E pointer to element(s) to add
 579     @param N number of elements to add
 580     @param H header size in bytes (may be zero)
 581     @param A alignment (may be zero)
 582     @return V (value-result macro parameter)
 583 */
 584 #define vec_add_ha(V,E,N,H,A)                                                   \
 585 do {                                                                            \
 586   word _v(n) = (N);                                                             \
 587   word _v(l) = vec_len (V);                                                     \
 588   V = _vec_resize ((V), _v(n), (_v(l) + _v(n)) * sizeof ((V)[0]), (H), (A));    \
 589   clib_memcpy ((V) + _v(l), (E), _v(n) * sizeof ((V)[0]));                      \
 590 } while (0)
 591
 592 /** \brief Add N elements to end of vector V (no header, unspecified alignment)
 593
 594     @param V pointer to a vector
 595     @param E pointer to element(s) to add
 596     @param N number of elements to add
 597     @return V (value-result macro parameter)
 598 */
 599 #define vec_add(V,E,N)           vec_add_ha(V,E,N,0,0)
 600
 601 /** \brief Add N elements to end of vector V (no header, specified alignment)
 602
 603     @param V pointer to a vector
 604     @param E pointer to element(s) to add
 605     @param N number of elements to add
 606     @param A alignment (may be zero)
 607     @return V (value-result macro parameter)
 608 */
 609 #define vec_add_aligned(V,E,N,A) vec_add_ha(V,E,N,0,A)
 610
 611 /** \brief Returns last element of a vector and decrements its length
 612
 613     @param V pointer to a vector
 614     @return E element removed from the end of the vector
 615 */
 616 #define vec_pop(V)                              \
 617 ({                                              \
 618   uword _v(l) = vec_len (V);                    \
 619   ASSERT (_v(l) > 0);                           \
 620   _v(l) -= 1;                                   \
 621   _vec_len (V) = _v (l);                        \
 622   (V)[_v(l)];                                   \
 623 })
 624
 625 /** \brief Set E to the last element of a vector, decrement vector length
 626     @param V pointer to a vector
 627     @param E pointer to the last vector element
 628     @return E element removed from the end of the vector
 629     (value-result macro parameter
 630 */
 631
 632 #define vec_pop2(V,E)                           \
 633 ({                                              \
 634   uword _v(l) = vec_len (V);                    \
 635   if (_v(l) > 0) (E) = vec_pop (V);             \
 636   _v(l) > 0;                                    \
 637 })
 638
 639 /** \brief Insert N vector elements starting at element M,
 640     initialize new elements (general version).
 641
 642     @param V (possibly NULL) pointer to a vector.
 643     @param N number of elements to insert
 644     @param M insertion point
 645     @param INIT initial value (can be a complex expression!)
 646     @param H header size in bytes (may be zero)
 647     @param A alignment (may be zero)
 648     @return V (value-result macro parameter)
 649 */
 650 #define vec_insert_init_empty_ha(V,N,M,INIT,H,A)        \
 651 do {                                                    \
 652   word _v(l) = vec_len (V);                             \
 653   word _v(n) = (N);                                     \
 654   word _v(m) = (M);                                     \
 655   V = _vec_resize ((V),                                 \
 656                    _v(n),                               \
 657                    (_v(l) + _v(n))*sizeof((V)[0]),      \
 658                    (H), (A));                           \
 659   ASSERT (_v(m) <= _v(l));                              \
 660   memmove ((V) + _v(m) + _v(n),                         \
 661            (V) + _v(m),                                 \
 662            (_v(l) - _v(m)) * sizeof ((V)[0]));          \
 663   memset  ((V) + _v(m), INIT, _v(n) * sizeof ((V)[0])); \
 664 } while (0)
 665
 666 /** \brief Insert N vector elements starting at element M,
 667     initialize new elements to zero (general version)
 668
 669     @param V (possibly NULL) pointer to a vector.
 670     @param N number of elements to insert
 671     @param M insertion point
 672     @param H header size in bytes (may be zero)
 673     @param A alignment (may be zero)
 674     @return V (value-result macro parameter)
 675 */
 676 #define vec_insert_ha(V,N,M,H,A)    vec_insert_init_empty_ha(V,N,M,0,H,A)
 677
 678 /** \brief Insert N vector elements starting at element M,
 679     initialize new elements to zero (no header, unspecified alignment)
 680
 681     @param V (possibly NULL) pointer to a vector.
 682     @param N number of elements to insert
 683     @param M insertion point
 684     @return V (value-result macro parameter)
 685 */
 686 #define vec_insert(V,N,M)           vec_insert_ha(V,N,M,0,0)
 687
 688 /** \brief Insert N vector elements starting at element M,
 689     initialize new elements to zero (no header, alignment specified)
 690
 691     @param V (possibly NULL) pointer to a vector.
 692     @param N number of elements to insert
 693     @param M insertion point
 694     @param A alignment (may be zero)
 695     @return V (value-result macro parameter)
 696 */
 697 #define vec_insert_aligned(V,N,M,A) vec_insert_ha(V,N,M,0,A)
 698
 699 /** \brief Insert N vector elements starting at element M,
 700     initialize new elements (no header, unspecified alignment)
 701
 702     @param V (possibly NULL) pointer to a vector.
 703     @param N number of elements to insert
 704     @param M insertion point
 705     @param INIT initial value (can be a complex expression!)
 706     @return V (value-result macro parameter)
 707 */
 708
 709 #define vec_insert_init_empty(V,N,M,INIT) \
 710   vec_insert_init_empty_ha(V,N,M,INIT,0,0)
 711 /* Resize vector by N elements starting from element M, initialize new elements to INIT (alignment specified, no header). */
 712
 713 /** \brief Insert N vector elements starting at element M,
 714     initialize new elements (no header, specified alignment)
 715
 716     @param V (possibly NULL) pointer to a vector.
 717     @param N number of elements to insert
 718     @param M insertion point
 719     @param INIT initial value (can be a complex expression!)
 720     @param A alignment (may be zero)
 721     @return V (value-result macro parameter)
 722 */
 723 #define vec_insert_init_empty_aligned(V,N,M,INIT,A) \
 724   vec_insert_init_empty_ha(V,N,M,INIT,0,A)
 725
 726 /** \brief Insert N vector elements starting at element M,
 727     insert given elements (general version)
 728
 729     @param V (possibly NULL) pointer to a vector.
 730     @param E element(s) to insert
 731     @param N number of elements to insert
 732     @param M insertion point
 733     @param H header size in bytes (may be zero)
 734     @param A alignment (may be zero)
 735     @return V (value-result macro parameter)
 736 */
 737
 738 #define vec_insert_elts_ha(V,E,N,M,H,A)                 \
 739 do {                                                    \
 740   word _v(l) = vec_len (V);                             \
 741   word _v(n) = (N);                                     \
 742   word _v(m) = (M);                                     \
 743   V = _vec_resize ((V),                                 \
 744                    _v(n),                               \
 745                    (_v(l) + _v(n))*sizeof((V)[0]),      \
 746                    (H), (A));                           \
 747   ASSERT (_v(m) <= _v(l));                              \
 748   memmove ((V) + _v(m) + _v(n),                         \
 749            (V) + _v(m),                                 \
 750            (_v(l) - _v(m)) * sizeof ((V)[0]));          \
 751   clib_memcpy ((V) + _v(m), (E),                        \
 752                _v(n) * sizeof ((V)[0]));                \
 753 } while (0)
 754
 755 /** \brief Insert N vector elements starting at element M,
 756     insert given elements (no header, unspecified alignment)
 757
 758     @param V (possibly NULL) pointer to a vector.
 759     @param E element(s) to insert
 760     @param N number of elements to insert
 761     @param M insertion point
 762     @return V (value-result macro parameter)
 763 */
 764 #define vec_insert_elts(V,E,N,M)           vec_insert_elts_ha(V,E,N,M,0,0)
 765
 766 /** \brief Insert N vector elements starting at element M,
 767     insert given elements (no header, specified alignment)
 768
 769     @param V (possibly NULL) pointer to a vector.
 770     @param E element(s) to insert
 771     @param N number of elements to insert
 772     @param M insertion point
 773     @param A alignment (may be zero)
 774     @return V (value-result macro parameter)
 775 */
 776 #define vec_insert_elts_aligned(V,E,N,M,A) vec_insert_elts_ha(V,E,N,M,0,A)
 777
 778 /** \brief Delete N elements starting at element M
 779
 780     @param V pointer to a vector
 781     @param N number of elements to delete
 782     @param M first element to delete
 783     @return V (value-result macro parameter)
 784 */
 785 #define vec_delete(V,N,M)                                       \
 786 do {                                                            \
 787   word _v(l) = vec_len (V);                                     \
 788   word _v(n) = (N);                                             \
 789   word _v(m) = (M);                                             \
 790   /* Copy over deleted elements. */                             \
 791   if (_v(l) - _v(n) - _v(m) > 0)                                \
 792     memmove ((V) + _v(m), (V) + _v(m) + _v(n),                  \
 793              (_v(l) - _v(n) - _v(m)) * sizeof ((V)[0]));        \
 794   /* Zero empty space at end (for future re-allocation). */     \
 795   if (_v(n) > 0)                                                \
 796     memset ((V) + _v(l) - _v(n), 0, _v(n) * sizeof ((V)[0]));   \
 797   _vec_len (V) -= _v(n);                                        \
 798 } while (0)
 799
 800 /** \brief Delete the element at index I
 801
 802     @param V pointer to a vector
 803     @param I index to delete
 804 */
 805 #define vec_del1(v,i)                           \
 806 do {                                            \
 807   uword _vec_del_l = _vec_len (v) - 1;          \
 808   uword _vec_del_i = (i);                       \
 809   if (_vec_del_i < _vec_del_l)                  \
 810     (v)[_vec_del_i] = (v)[_vec_del_l];          \
 811   _vec_len (v) = _vec_del_l;                    \
 812 } while (0)
 813
 814 /** \brief Append v2 after v1. Result in v1.
 815     @param V1 target vector
 816     @param V2 vector to append
 817 */
 818
 819 #define vec_append(v1,v2)                                               \
 820 do {                                                                    \
 821   uword _v(l1) = vec_len (v1);                                          \
 822   uword _v(l2) = vec_len (v2);                                          \
 823                                                                         \
 824   v1 = _vec_resize ((v1), _v(l2),                                       \
 825                     (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0);        \
 826   clib_memcpy ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0]));         \
 827 } while (0)
 828
 829 /** \brief Append v2 after v1. Result in v1. Specified alignment.
 830     @param V1 target vector
 831     @param V2 vector to append
 832     @param align required alignment
 833 */
 834
 835 #define vec_append_aligned(v1,v2,align)                                 \
 836 do {                                                                    \
 837   uword _v(l1) = vec_len (v1);                                          \
 838   uword _v(l2) = vec_len (v2);                                          \
 839                                                                         \
 840   v1 = _vec_resize ((v1), _v(l2),                                       \
 841                     (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align);    \
 842   clib_memcpy ((v1) + _v(l1), (v2), _v(l2) * sizeof ((v2)[0]));         \
 843 } while (0)
 844
 845 /** \brief Prepend v2 before v1. Result in v1.
 846     @param V1 target vector
 847     @param V2 vector to prepend
 848 */
 849
 850 #define vec_prepend(v1,v2)                                              \
 851 do {                                                                    \
 852   uword _v(l1) = vec_len (v1);                                          \
 853   uword _v(l2) = vec_len (v2);                                          \
 854                                                                         \
 855   v1 = _vec_resize ((v1), _v(l2),                                       \
 856                     (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, 0);        \
 857   memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0]));             \
 858   clib_memcpy ((v1), (v2), _v(l2) * sizeof ((v2)[0]));                  \
 859 } while (0)
 860
 861 /** \brief Prepend v2 before v1. Result in v1. Specified alignment
 862     @param V1 target vector
 863     @param V2 vector to prepend
 864     @param align required alignment
 865 */
 866
 867 #define vec_prepend_aligned(v1,v2,align)                                \
 868 do {                                                                    \
 869   uword _v(l1) = vec_len (v1);                                          \
 870   uword _v(l2) = vec_len (v2);                                          \
 871                                                                         \
 872   v1 = _vec_resize ((v1), _v(l2),                                       \
 873                     (_v(l1) + _v(l2)) * sizeof ((v1)[0]), 0, align);    \
 874   memmove ((v1) + _v(l2), (v1), _v(l1) * sizeof ((v1)[0]));             \
 875   clib_memcpy ((v1), (v2), _v(l2) * sizeof ((v2)[0]));                  \
 876 } while (0)
 877
 878
 879 /** \brief Zero all vector elements. Null-pointer tolerant.
 880     @param var Vector to zero
 881 */
 882 #define vec_zero(var)                                           \
 883 do {                                                            \
 884   if (var)                                                      \
 885     memset ((var), 0, vec_len (var) * sizeof ((var)[0]));       \
 886 } while (0)
 887
 888 /** \brief Set all vector elements to given value. Null-pointer tolerant.
 889     @param v vector to set
 890     @param val value for each vector element
 891 */
 892 #define vec_set(v,val)                          \
 893 do {                                            \
 894   word _v(i);                                   \
 895   __typeof__ ((v)[0]) _val = (val);             \
 896   for (_v(i) = 0; _v(i) < vec_len (v); _v(i)++) \
 897     (v)[_v(i)] = _val;                          \
 898 } while (0)
 899
 900 #ifdef CLIB_UNIX
 901 #include <stdlib.h>             /* for qsort */
 902 #endif
 903
 904 /** \brief Compare two vectors, not NULL-pointer tolerant
 905
 906     @param v1 Pointer to a vector
 907     @param v2 Pointer to a vector
 908     @return 1 if equal, 0 if unequal
 909 */
 910 #define vec_is_equal(v1,v2) \
 911   (vec_len (v1) == vec_len (v2) && ! memcmp ((v1), (v2), vec_len (v1) * sizeof ((v1)[0])))
 912
 913 /** \brief Compare two vectors (only applicable to vectors of signed numbers).
 914    Used in qsort compare functions.
 915
 916     @param v1 Pointer to a vector
 917     @param v2 Pointer to a vector
 918     @return -1, 0, +1
 919 */
 920 #define vec_cmp(v1,v2)                                  \
 921 ({                                                      \
 922   word _v(i), _v(cmp), _v(l);                           \
 923   _v(l) = clib_min (vec_len (v1), vec_len (v2));        \
 924   _v(cmp) = 0;                                          \
 925   for (_v(i) = 0; _v(i) < _v(l); _v(i)++) {             \
 926     _v(cmp) = (v1)[_v(i)] - (v2)[_v(i)];                \
 927     if (_v(cmp))                                        \
 928       break;                                            \
 929   }                                                     \
 930   if (_v(cmp) == 0 && _v(l) > 0)                        \
 931     _v(cmp) = vec_len(v1) - vec_len(v2);                \
 932   (_v(cmp) < 0 ? -1 : (_v(cmp) > 0 ? +1 : 0));          \
 933 })
 934
 935 /** \brief Search a vector for the index of the entry that matches.
 936
 937     @param v1 Pointer to a vector
 938     @param v2 Entry to match
 939     @return index of match or ~0
 940 */
 941 #define vec_search(v,E)                                 \
 942 ({                                                      \
 943   word _v(i) = 0;                                       \
 944   while (_v(i) < vec_len(v))                            \
 945   {                                                     \
 946     if ((v)[_v(i)] == E)                                        \
 947       break;                                            \
 948     _v(i)++;                                            \
 949   }                                                     \
 950   if (_v(i) == vec_len(v))                              \
 951     _v(i) = ~0;                                         \
 952   _v(i);                                                \
 953 })
 954
 955 /** \brief Sort a vector using the supplied element comparison function
 956
 957     @param vec vector to sort
 958     @param f comparison function
 959 */
 960 #define vec_sort_with_function(vec,f)                           \
 961 do {                                                            \
 962   qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f));    \
 963 } while (0)
 964
 965 /** \brief Make a vector containing a NULL terminated c-string.
 966
 967     @param V (possibly NULL) pointer to a vector.
 968     @param S pointer to string buffer.
 969     @param L string length (NOT including the terminating NULL; a la strlen())
 970 */
 971 #define vec_validate_init_c_string(V, S, L)     \
 972   do {                                          \
 973     vec_reset_length (V);                       \
 974     vec_validate ((V), (L));                    \
 975     if ((S) && (L))                             \
 976         clib_memcpy ((V), (S), (L));            \
 977     (V)[(L)] = 0;                               \
 978   } while (0)
 979
 980
 981 /** \brief Test whether a vector is a NULL terminated c-string.
 982
 983     @param V (possibly NULL) pointer to a vector.
 984     @return BOOLEAN indicating if the vector c-string is null terminated.
 985 */
 986 #define vec_c_string_is_terminated(V)                   \
 987   (((V) != 0) && (vec_len (V) != 0) && ((V)[vec_len ((V)) - 1] == 0))
 988
 989 /** \brief (If necessary) NULL terminate a vector containing a c-string.
 990
 991     @param V (possibly NULL) pointer to a vector.
 992     @return V (value-result macro parameter)
 993 */
 994 #define vec_terminate_c_string(V)               \
 995   do {                                          \
 996     u32 vl = vec_len ((V));                     \
 997     if (!vec_c_string_is_terminated(V))         \
 998       {                                         \
 999         vec_validate ((V), vl);                 \
1000         (V)[vl] = 0;                            \
1001       }                                         \
1002   } while (0)
1003
1004 #endif /* included_vec_h */
1005
1006
1007 /*
1008  * fd.io coding-style-patch-verification: ON
1009  *
1010  * Local Variables:
1011  * eval: (c-set-style "gnu")
1012  * End:
1013  */