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