vppinfra/vppinfra/bitmap.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, 2005 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_clib_bitmap_h
  39 #define included_clib_bitmap_h
  40
  41 /** \file
  42     Bitmaps built as vectors of machine words
  43 */
  44
  45 #include <vppinfra/vec.h>
  46 #include <vppinfra/random.h>
  47 #include <vppinfra/error.h>
  48 #include <vppinfra/bitops.h>    /* for count_set_bits */
  49
  50 typedef uword clib_bitmap_t;
  51
  52 /** predicate function; is an entire bitmap empty?
  53     @param ai - pointer to a bitmap
  54     @returns 1 if the entire bitmap is zero, 0 otherwise
  55 */
  56 always_inline uword
  57 clib_bitmap_is_zero (uword * ai)
  58 {
  59   uword i;
  60   for (i = 0; i < vec_len (ai); i++)
  61     if (ai[i] != 0)
  62       return 0;
  63   return 1;
  64 }
  65
  66 /** predicate function; are two bitmaps equal?
  67     @param a - pointer to a bitmap
  68     @param b - pointer to a bitmap
  69     @returns 1 if the bitmaps are equal, 0 otherwise
  70 */
  71 always_inline uword
  72 clib_bitmap_is_equal (uword * a, uword * b)
  73 {
  74   uword i;
  75   if (vec_len (a) != vec_len (b))
  76     return 0;
  77   for (i = 0; i < vec_len (a); i++)
  78     if (a[i] != b[i])
  79       return 0;
  80   return 1;
  81 }
  82
  83 /** Duplicate a bitmap
  84     @param ai - pointer to a bitmap
  85     @returns a duplicate of the bitmap
  86 */
  87 #define clib_bitmap_dup(v) vec_dup(v)
  88
  89 /** Free a bitmap
  90     @param v - pointer to the bitmap to free
  91 */
  92 #define clib_bitmap_free(v) vec_free(v)
  93
  94 /** Number of bytes in a bitmap
  95     @param v - pointer to the bitmap
  96 */
  97 #define clib_bitmap_bytes(v) vec_bytes(v)
  98
  99 /** Clear a bitmap
 100     @param v - pointer to the bitmap to clear
 101 */
 102 #define clib_bitmap_zero(v) vec_zero(v)
 103
 104 /** Allocate a bitmap with the supplied number of bits
 105     @param [out] v - the resulting bitmap
 106     @param n_bits - the required number of bits
 107 */
 108
 109 #define clib_bitmap_alloc(v,n_bits) \
 110   v = vec_new (uword, ((n_bits) + BITS (uword) - 1) / BITS (uword))
 111
 112 #define clib_bitmap_vec_validate(v,i) vec_validate_aligned((v),(i),sizeof(uword))
 113
 114 /* Make sure that a bitmap is at least n_bits in size */
 115 #define clib_bitmap_validate(v,n_bits) \
 116   clib_bitmap_vec_validate ((v), ((n_bits) - 1) / BITS (uword))
 117
 118 /* low-level routine to remove trailing zeros from a bitmap */
 119 always_inline uword *
 120 _clib_bitmap_remove_trailing_zeros (uword * a)
 121 {
 122   word i;
 123   if (a)
 124     {
 125       for (i = _vec_len (a) - 1; i >= 0; i--)
 126         if (a[i] != 0)
 127           break;
 128       _vec_len (a) = i + 1;
 129     }
 130   return a;
 131 }
 132
 133 /** Sets the ith bit of a bitmap to new_value.
 134     No sanity checking. Be careful.
 135     @param a - pointer to the bitmap
 136     @param i - the bit position to interrogate
 137     @param new_value - new value for the bit
 138     @returns the old value of the bit
 139 */
 140 always_inline uword
 141 clib_bitmap_set_no_check (uword * a, uword i, uword new_value)
 142 {
 143   uword i0 = i / BITS (a[0]);
 144   uword i1 = i % BITS (a[0]);
 145   uword bit = (uword) 1 << i1;
 146   uword ai, old_value;
 147
 148   /* Removed ASSERT since uword * a may not be a vector. */
 149   /* ASSERT (i0 < vec_len (a)); */
 150
 151   ai = a[i0];
 152   old_value = (ai & bit) != 0;
 153   ai &= ~ bit;
 154   ai |= ((uword) (new_value != 0)) << i1;
 155   a[i0] = ai;
 156   return old_value;
 157 }
 158
 159 /** Sets the ith bit of a bitmap to new_value
 160     Removes trailing zeros from the bitmap
 161     @param a - pointer to the bitmap
 162     @param i - the bit position to interrogate
 163     @param new_value - new value for the bit
 164     @returns the old value of the bit
 165 */
 166 always_inline uword *
 167 clib_bitmap_set (uword * ai, uword i, uword value)
 168 {
 169   uword i0 = i / BITS (ai[0]);
 170   uword i1 = i % BITS (ai[0]);
 171   uword a;
 172
 173   /* Check for writing a zero to beyond end of bitmap. */
 174   if (value == 0 && i0 >= vec_len (ai))
 175     return ai;                  /* Implied trailing zeros. */
 176
 177   clib_bitmap_vec_validate (ai, i0);
 178
 179   a = ai[i0];
 180   a &= ~((uword) 1 << i1);
 181   a |= ((uword) (value != 0)) << i1;
 182   ai[i0] = a;
 183
 184   /* If bits have been cleared, test for zero. */
 185   if (a == 0)
 186     ai = _clib_bitmap_remove_trailing_zeros (ai);
 187
 188   return ai;
 189 }
 190
 191 /** Gets the ith bit value from a bitmap
 192     @param ai - pointer to the bitmap
 193     @param i - the bit position to interrogate
 194     @returns the indicated bit value
 195 */
 196 always_inline uword
 197 clib_bitmap_get (uword * ai, uword i)
 198 {
 199   uword i0 = i / BITS (ai[0]);
 200   uword i1 = i % BITS (ai[0]);
 201   return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1);
 202 }
 203
 204 /** Gets the ith bit value from a bitmap
 205     Does not sanity-check the bit position. Be careful.
 206     @param ai - pointer to the bitmap
 207     @param i - the bit position to interrogate
 208     @returns the indicated bit value, or garbage if the bit position is
 209     out of range.
 210 */
 211 always_inline uword
 212 clib_bitmap_get_no_check (uword * ai, uword i)
 213 {
 214   uword i0 = i / BITS (ai[0]);
 215   uword i1 = i % BITS (ai[0]);
 216   return 0 != ((ai[i0] >> i1) & 1);
 217 }
 218
 219 always_inline uword
 220 clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits)
 221 {
 222   uword i0 = i / BITS (ai[0]);
 223   uword i1 = i % BITS (ai[0]);
 224   ASSERT (i1 + n_bits <= BITS (uword));
 225   return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits));
 226 }
 227
 228 /** Gets the ith through ith + n_bits bit values from a bitmap
 229     @param bitmap - pointer to the bitmap
 230     @param i - the first bit position to retrieve
 231     @param n_bits - the number of bit positions to retrieve
 232     @returns the indicated range of bits
 233 */
 234 always_inline uword
 235 clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
 236 {
 237   uword i0, i1, result;
 238   uword l = vec_len (bitmap);
 239
 240   ASSERT (n_bits <= BITS (result));
 241
 242   i0 = i / BITS (bitmap[0]);
 243   i1 = i % BITS (bitmap[0]);
 244
 245   /* Check first word. */
 246   result = 0;
 247   if (i0 < l)
 248     {
 249       result |= (bitmap[i0] >> i1);
 250       if (n_bits < BITS (bitmap[0]))
 251         result &= (((uword) 1 << n_bits) - 1);
 252     }
 253
 254   /* Check for overlap into next word. */
 255   i0++;
 256   if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
 257     {
 258       n_bits -= BITS (bitmap[0]) - i1;
 259       result |= (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
 260     }
 261
 262   return result;
 263 }
 264
 265 /** sets the ith through ith + n_bits bits in a bitmap
 266     @param bitmap - pointer to the bitmap
 267     @param i - the first bit position to retrieve
 268     @param value - the values to set
 269     @param n_bits - the number of bit positions to set
 270     @returns a pointer to the updated bitmap, which may expand and move
 271 */
 272
 273 always_inline uword *
 274 clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
 275 {
 276   uword i0, i1, l, t, m;
 277
 278   ASSERT (n_bits <= BITS (value));
 279
 280   i0 = i / BITS (bitmap[0]);
 281   i1 = i % BITS (bitmap[0]);
 282
 283   /* Allocate bitmap. */
 284   clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0]));
 285   l = vec_len (bitmap);
 286
 287   m = ~0;
 288   if (n_bits < BITS (value))
 289     m = (((uword) 1 << n_bits) - 1);
 290   value &= m;
 291
 292   /* Insert into first word. */
 293   t = bitmap[i0];
 294   t &= ~(m << i1);
 295   t |= value << i1;
 296   bitmap[i0] = t;
 297
 298   /* Insert into second word. */
 299   i0++;
 300   if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
 301     {
 302       t = BITS (bitmap[0]) - i1;
 303       value >>= t;
 304       n_bits -= t;
 305       t = bitmap[i0];
 306       m = ((uword) 1 << n_bits) - 1;
 307       t &= ~m;
 308       t |= value;
 309       bitmap[i0] = t;
 310     }
 311
 312   return bitmap;
 313 }
 314
 315 always_inline uword *
 316 clfib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
 317 {
 318   uword a0, a1, b0;
 319   uword i_end, mask;
 320
 321   a0 = i / BITS (bitmap[0]);
 322   a1 = i % BITS (bitmap[0]);
 323
 324   i_end = i + n_bits;
 325   b0 = i_end / BITS (bitmap[0]);
 326
 327   clib_bitmap_vec_validate (bitmap, b0);
 328
 329   /* First word. */
 330   mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0;
 331   mask <<= a1;
 332
 333   if (value)
 334     bitmap[a0] |= mask;
 335   else
 336     bitmap[a0] &= ~mask;
 337
 338   for (a0++; a0 < b0; a0++)
 339     bitmap[a0] = value ? ~0 : 0;
 340
 341   if (a0 == b0)
 342     {
 343       word n_bits_left = n_bits - (BITS (bitmap[0]) - a1);
 344       mask = pow2_mask (n_bits_left);
 345       if (value)
 346         bitmap[a0] |= mask;
 347       else
 348         bitmap[a0] &= ~mask;
 349     }
 350
 351   return bitmap;
 352 }
 353
 354 /** Macro to iterate across set bits in a bitmap
 355
 356     @param i - the current set bit
 357     @param ai - the bitmap
 358     @param body - the expression to evaluate for each set bit
 359 */
 360 #define clib_bitmap_foreach(i,ai,body)                                  \
 361 do {                                                                    \
 362   uword __bitmap_i, __bitmap_ai, __bitmap_len, __bitmap_first_set;      \
 363   __bitmap_len = vec_len ((ai));                                        \
 364   for (__bitmap_i = 0; __bitmap_i < __bitmap_len; __bitmap_i++)         \
 365     {                                                                   \
 366       __bitmap_ai = (ai)[__bitmap_i];                                   \
 367       while (__bitmap_ai != 0)                                          \
 368         {                                                               \
 369           __bitmap_first_set = first_set (__bitmap_ai);                 \
 370           (i) = (__bitmap_i * BITS ((ai)[0])                            \
 371                  + min_log2 (__bitmap_first_set));                      \
 372           do { body; } while (0);                                       \
 373           __bitmap_ai ^= __bitmap_first_set;                            \
 374         }                                                               \
 375     }                                                                   \
 376 } while (0)
 377
 378
 379 /** Return the lowest numbered set bit in a bitmap
 380     @param ai - pointer to the bitmap
 381     @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
 382 */
 383 always_inline uword clib_bitmap_first_set (uword * ai)
 384 {
 385   uword i;
 386   for (i = 0; i < vec_len (ai); i++)
 387     {
 388       uword x = ai[i];
 389       if (x != 0)
 390         return i * BITS (ai[0]) + log2_first_set (x);
 391     }
 392   return ~0;
 393 }
 394
 395 /** Return the higest numbered set bit in a bitmap
 396     @param ai - pointer to the bitmap
 397     @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
 398 */
 399 always_inline uword clib_bitmap_last_set (uword * ai)
 400 {
 401   uword i;
 402
 403   for (i = vec_len (ai); i > 0 ; i--)
 404     {
 405       uword x = ai[i - 1];
 406       if (x != 0)
 407         {
 408           uword first_bit;
 409           count_leading_zeros (first_bit, x);
 410           return (i) * BITS (ai[0]) - first_bit - 1;
 411         }
 412     }
 413   return ~0;
 414 }
 415
 416 /** Return the lowest numbered clear bit in a bitmap
 417     @param ai - pointer to the bitmap
 418     @returns lowest numbered clear bit
 419 */
 420 always_inline uword
 421 clib_bitmap_first_clear (uword * ai)
 422 {
 423   uword i;
 424   for (i = 0; i < vec_len (ai); i++)
 425     {
 426       uword x = ~ai[i];
 427       if (x != 0)
 428         return i * BITS (ai[0]) + log2_first_set (x);
 429     }
 430   return i * BITS (ai[0]);
 431 }
 432
 433 /** Return the number of set bits in a bitmap
 434     @param ai - pointer to the bitmap
 435     @returns the number of set bits in the bitmap
 436 */
 437 always_inline uword
 438 clib_bitmap_count_set_bits (uword * ai)
 439 {
 440   uword i;
 441   uword n_set = 0;
 442   for (i = 0; i < vec_len (ai); i++)
 443     n_set += count_set_bits (ai[i]);
 444   return n_set;
 445 }
 446
 447 /** Logical operator across two bitmaps
 448
 449     @param ai - pointer to the destination bitmap
 450     @param bi - pointer to the source bitmap
 451     @returns ai = ai and bi. ai is modified, bi is not modified
 452 */
 453 always_inline uword *
 454 clib_bitmap_and (uword * ai, uword * bi);
 455
 456 /** Logical operator across two bitmaps
 457
 458     @param ai - pointer to the destination bitmap
 459     @param bi - pointer to the source bitmap
 460     @returns ai = ai & ~bi. ai is modified, bi is not modified
 461 */
 462 always_inline uword *
 463 clib_bitmap_andnot (uword * ai, uword * bi);
 464
 465 /** Logical operator across two bitmaps
 466
 467     @param ai - pointer to the destination bitmap
 468     @param bi - pointer to the source bitmap
 469     @returns ai = ai & ~bi. ai is modified, bi is not modified
 470 */
 471 always_inline uword *
 472 clib_bitmap_or (uword * ai, uword * bi);
 473 /** Logical operator across two bitmaps
 474
 475     @param ai - pointer to the destination bitmap
 476     @param bi - pointer to the source bitmap
 477     @returns ai = ai or bi. ai is modified, bi is not modified
 478 */
 479 always_inline uword *
 480 clib_bitmap_or (uword * ai, uword * bi);
 481
 482 /** Logical operator across two bitmaps
 483
 484     @param ai - pointer to the destination bitmap
 485     @param bi - pointer to the source bitmap
 486     @returns ai = ai xor bi. ai is modified, bi is not modified
 487 */
 488 always_inline uword *
 489 clib_bitmap_xor (uword * ai, uword * bi);
 490
 491 /* ALU function definition macro for functions taking two bitmaps. */
 492 #define _(name, body, check_zero)                               \
 493 always_inline uword *                                           \
 494 clib_bitmap_##name (uword * ai, uword * bi)                     \
 495 {                                                               \
 496   uword i, a, b, bi_len, n_trailing_zeros;                      \
 497                                                                 \
 498   n_trailing_zeros = 0;                                         \
 499   bi_len = vec_len (bi);                                        \
 500   if (bi_len > 0)                                               \
 501     clib_bitmap_vec_validate (ai, bi_len - 1);                  \
 502   for (i = 0; i < vec_len (ai); i++)                            \
 503     {                                                           \
 504       a = ai[i];                                                \
 505       b = i < bi_len ? bi[i] : 0;                               \
 506       do { body; } while (0);                                   \
 507       ai[i] = a;                                                \
 508       if (check_zero)                                           \
 509         n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1);      \
 510     }                                                           \
 511   if (check_zero)                                               \
 512     _vec_len (ai) -= n_trailing_zeros;                          \
 513   return ai;                                                    \
 514 }
 515
 516 /* ALU functions: */
 517 _ (and, a = a & b, 1)
 518 _ (andnot, a = a &~ b, 1)
 519 _ (or,  a = a | b, 0)
 520 _ (xor, a = a ^ b, 1)
 521 #undef _
 522
 523 /** Logical operator across two bitmaps which duplicates the first bitmap
 524
 525     @param ai - pointer to the destination bitmap
 526     @param bi - pointer to the source bitmap
 527     @returns aiDup = ai and bi. Neither ai nor bi are modified
 528 */
 529 always_inline uword *
 530 clib_bitmap_dup_and (uword * ai, uword * bi);
 531
 532 /** Logical operator across two bitmaps which duplicates the first bitmap
 533
 534     @param ai - pointer to the destination bitmap
 535     @param bi - pointer to the source bitmap
 536     @returns aiDup = ai & ~bi. Neither ai nor bi are modified
 537 */
 538 always_inline uword *
 539 clib_bitmap_dup_andnot (uword * ai, uword * bi);
 540
 541 /** Logical operator across two bitmaps which duplicates the first bitmap
 542
 543     @param ai - pointer to the destination bitmap
 544     @param bi - pointer to the source bitmap
 545     @returns aiDup = ai or bi. Neither ai nor bi are modified
 546 */
 547 always_inline uword *
 548 clib_bitmap_dup_or (uword * ai, uword * bi);
 549
 550 /** Logical operator across two bitmaps which duplicates the first bitmap
 551
 552     @param ai - pointer to the destination bitmap
 553     @param bi - pointer to the source bitmap
 554     @returns aiDup = ai xor bi. Neither ai nor bi are modified
 555 */
 556 always_inline uword *
 557 clib_bitmap_dup_xor (uword * ai, uword * bi);
 558
 559 #define _(name)                                         \
 560   always_inline uword *                                 \
 561   clib_bitmap_dup_##name (uword * ai, uword * bi)       \
 562 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
 563
 564 _ (and);
 565 _ (andnot);
 566 _ (or);
 567 _ (xor);
 568
 569 #undef _
 570
 571 /* ALU function definition macro for functions taking one bitmap and an immediate. */
 572 #define _(name, body, check_zero)                       \
 573 always_inline uword *                                   \
 574 clib_bitmap_##name (uword * ai, uword i)                \
 575 {                                                       \
 576   uword i0 = i / BITS (ai[0]);                          \
 577   uword i1 = i % BITS (ai[0]);                          \
 578   uword a, b;                                           \
 579   clib_bitmap_vec_validate (ai, i0);                    \
 580   a = ai[i0];                                           \
 581   b = (uword) 1 << i1;                                  \
 582   do { body; } while (0);                               \
 583   ai[i0] = a;                                           \
 584   if (check_zero && a == 0)                             \
 585     ai = _clib_bitmap_remove_trailing_zeros (ai);       \
 586   return ai;                                            \
 587 }
 588
 589 /* ALU functions immediate: */
 590 _ (andi, a = a & b, 1)
 591 _ (andnoti, a = a &~ b, 1)
 592 _ (ori, a = a | b, 0)
 593 _ (xori, a = a ^ b, 1)
 594
 595 #undef _
 596
 597 /** Return a random bitmap of the requested length
 598     @param ai - pointer to the destination bitmap
 599     @param n_bits - number of bits to allocate
 600     @param [in/out] seed - pointer to the random number seed
 601     @returns a reasonably random bitmap based. See random.h.
 602 */
 603 always_inline uword *
 604 clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
 605 {
 606   vec_reset_length (ai);
 607
 608   if (n_bits > 0)
 609     {
 610       uword i = n_bits - 1;
 611       uword i0, i1;
 612       uword log2_rand_max;
 613
 614       log2_rand_max = min_log2 (random_u32_max ());
 615
 616       i0 = i / BITS (ai[0]);
 617       i1 = i % BITS (ai[0]);
 618
 619       clib_bitmap_vec_validate (ai, i0);
 620       for (i = 0; i <= i0; i++)
 621         {
 622           uword n;
 623           for (n = 0; n < BITS (ai[i]); n += log2_rand_max)
 624             ai[i] |= random_u32 (seed) << n;
 625         }
 626       if (i1 + 1 < BITS (ai[0]))
 627         ai[i0] &= (((uword) 1 << (i1 + 1)) - 1);
 628     }
 629   return ai;
 630 }
 631
 632 /** Return the next set bit in a bitmap starting at bit i
 633     @param ai - pointer to the bitmap
 634     @param i - first bit position to test
 635     @returns first set bit position at or after i,
 636     ~0 if no further set bits are found
 637 */
 638 always_inline uword
 639 clib_bitmap_next_set (uword * ai, uword i)
 640 {
 641   uword i0 = i / BITS (ai[0]);
 642   uword i1 = i % BITS (ai[0]);
 643   uword t;
 644
 645   if (i0 < vec_len (ai))
 646     {
 647       t = (ai[i0] >> i1) << i1;
 648       if (t)
 649         return log2_first_set (t) + i0 * BITS (ai[0]);
 650
 651       for (i0++; i0 < vec_len (ai); i0++)
 652         {
 653           t = ai[i0];
 654           if (t)
 655             return log2_first_set (t) + i0 * BITS (ai[0]);
 656         }
 657     }
 658
 659   return ~0;
 660 }
 661
 662 /** Return the next clear bit in a bitmap starting at bit i
 663     @param ai - pointer to the bitmap
 664     @param i - first bit position to test
 665     @returns first clear bit position at or after i
 666 */
 667 always_inline uword
 668 clib_bitmap_next_clear (uword * ai, uword i)
 669 {
 670   uword i0 = i / BITS (ai[0]);
 671   uword i1 = i % BITS (ai[0]);
 672   uword t;
 673
 674   if (i0 < vec_len (ai))
 675     {
 676       t = (~ai[i0] >> i1) << i1;
 677       if (t)
 678         return log2_first_set (t) + i0 * BITS (ai[0]);
 679
 680       for (i0++; i0 < vec_len (ai); i0++)
 681         {
 682           t = ~ai[i0];
 683           if (t)
 684             return log2_first_set (t) + i0 * BITS (ai[0]);
 685         }
 686     }
 687   return i;
 688 }
 689
 690 /** unformat a list of bit ranges into a bitmap (eg "0-3,5-7,11" )
 691
 692     uword * bitmap;
 693     rv = unformat ("%U", unformat_bitmap_list, &bitmap);
 694
 695     Standard unformat_function_t arguments
 696
 697     @param input - pointer an unformat_input_t
 698     @param va - varargs list comprising a single uword **
 699     @returns 1 on success, 0 on failure
 700 */
 701 static inline uword
 702 unformat_bitmap_list(unformat_input_t * input, va_list * va)
 703 {
 704   uword ** bitmap_return = va_arg (* va, uword **);
 705   uword * bitmap = 0;
 706
 707   u32 a,b;
 708
 709   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 710     {
 711       int i;
 712       if (unformat (input, "%u-%u,", &a, &b))
 713         ;
 714       else if (unformat (input, "%u,", &a))
 715         b = a;
 716       else if (unformat (input, "%u-%u", &a, &b))
 717         ;
 718       else if (unformat (input, "%u", &a))
 719         b = a;
 720       else if (bitmap)
 721         {
 722           unformat_put_input(input);
 723           break;
 724         }
 725       else
 726         goto error;
 727
 728       if (b < a)
 729         goto error;
 730
 731       for (i = a; i <= b; i++)
 732         bitmap = clib_bitmap_set(bitmap, i, 1);
 733     }
 734   *bitmap_return = bitmap;
 735   return 1;
 736 error:
 737   clib_bitmap_free(bitmap);
 738   return 0;
 739 }
 740
 741 /** Format a bitmap as a string of hex bytes
 742
 743     uword * bitmap;
 744     s = format ("%U", format_bitmap_hex, bitmap);
 745
 746     Standard format_function_t arguments
 747
 748     @param s - string under construction
 749     @param args - varargs list comprising a single uword *
 750     @returns string under construction
 751 */
 752 static inline u8 *
 753 format_bitmap_hex(u8 * s, va_list * args)
 754 {
 755   uword * bitmap = va_arg (*args, uword *);
 756   int i, is_trailing_zero = 1;
 757
 758   if (!bitmap)
 759     return format(s, "0");
 760
 761   i = vec_bytes (bitmap) * 2;
 762
 763   while (i > 0)
 764     {
 765       u8 x = clib_bitmap_get_multiple(bitmap, --i * 4, 4);
 766
 767       if (x && is_trailing_zero)
 768         is_trailing_zero = 0;
 769
 770       if (x || !is_trailing_zero)
 771           s = format(s, "%x", x);
 772     }
 773   return s;
 774 }
 775 #endif /* included_clib_bitmap_h */