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_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 old value of the bit
 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   uword i0 = i / BITS (ai[0]);
 212   return _vec_resize_will_expand (ai, 1, i0 * sizeof (ai[0]), 0,
 213                                   sizeof (uword));
 214 }
 215
 216 /** Gets the ith bit value from a bitmap
 217     @param ai - pointer to the bitmap
 218     @param i - the bit position to interrogate
 219     @returns the indicated bit value
 220 */
 221 always_inline uword
 222 clib_bitmap_get (uword * ai, uword i)
 223 {
 224   uword i0 = i / BITS (ai[0]);
 225   uword i1 = i % BITS (ai[0]);
 226   return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1);
 227 }
 228
 229 /** Gets the ith bit value from a bitmap
 230     Does not sanity-check the bit position. Be careful.
 231     @param ai - pointer to the bitmap
 232     @param i - the bit position to interrogate
 233     @returns the indicated bit value, or garbage if the bit position is
 234     out of range.
 235 */
 236 always_inline uword
 237 clib_bitmap_get_no_check (uword * ai, uword i)
 238 {
 239   uword i0 = i / BITS (ai[0]);
 240   uword i1 = i % BITS (ai[0]);
 241   return 0 != ((ai[i0] >> i1) & 1);
 242 }
 243
 244 always_inline uword
 245 clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits)
 246 {
 247   uword i0 = i / BITS (ai[0]);
 248   uword i1 = i % BITS (ai[0]);
 249   ASSERT (i1 + n_bits <= BITS (uword));
 250   return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits));
 251 }
 252
 253 /** Gets the ith through ith + n_bits bit values from a bitmap
 254     @param bitmap - pointer to the bitmap
 255     @param i - the first bit position to retrieve
 256     @param n_bits - the number of bit positions to retrieve
 257     @returns the indicated range of bits
 258 */
 259 always_inline uword
 260 clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
 261 {
 262   uword i0, i1, result;
 263   uword l = vec_len (bitmap);
 264
 265   ASSERT (n_bits <= BITS (result));
 266
 267   i0 = i / BITS (bitmap[0]);
 268   i1 = i % BITS (bitmap[0]);
 269
 270   /* Check first word. */
 271   result = 0;
 272   if (i0 < l)
 273     {
 274       result |= (bitmap[i0] >> i1);
 275       if (n_bits < BITS (bitmap[0]))
 276         result &= (((uword) 1 << n_bits) - 1);
 277     }
 278
 279   /* Check for overlap into next word. */
 280   i0++;
 281   if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
 282     {
 283       n_bits -= BITS (bitmap[0]) - i1;
 284       result |=
 285         (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
 286     }
 287
 288   return result;
 289 }
 290
 291 /** sets the ith through ith + n_bits bits in a bitmap
 292     @param bitmap - pointer to the bitmap
 293     @param i - the first bit position to retrieve
 294     @param value - the values to set
 295     @param n_bits - the number of bit positions to set
 296     @returns a pointer to the updated bitmap, which may expand and move
 297 */
 298
 299 always_inline uword *
 300 clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
 301 {
 302   uword i0, i1, l, t, m;
 303
 304   ASSERT (n_bits <= BITS (value));
 305
 306   i0 = i / BITS (bitmap[0]);
 307   i1 = i % BITS (bitmap[0]);
 308
 309   /* Allocate bitmap. */
 310   clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0]));
 311   l = vec_len (bitmap);
 312
 313   m = ~0;
 314   if (n_bits < BITS (value))
 315     m = (((uword) 1 << n_bits) - 1);
 316   value &= m;
 317
 318   /* Insert into first word. */
 319   t = bitmap[i0];
 320   t &= ~(m << i1);
 321   t |= value << i1;
 322   bitmap[i0] = t;
 323
 324   /* Insert into second word. */
 325   i0++;
 326   if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
 327     {
 328       t = BITS (bitmap[0]) - i1;
 329       value >>= t;
 330       n_bits -= t;
 331       t = bitmap[i0];
 332       m = ((uword) 1 << n_bits) - 1;
 333       t &= ~m;
 334       t |= value;
 335       bitmap[i0] = t;
 336     }
 337
 338   return bitmap;
 339 }
 340
 341 always_inline uword *
 342 clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
 343 {
 344   uword a0, a1, b0;
 345   uword i_end, mask;
 346
 347   a0 = i / BITS (bitmap[0]);
 348   a1 = i % BITS (bitmap[0]);
 349
 350   i_end = i + n_bits;
 351   b0 = i_end / BITS (bitmap[0]);
 352
 353   clib_bitmap_vec_validate (bitmap, b0);
 354
 355   /* First word. */
 356   mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0;
 357   mask <<= a1;
 358
 359   if (value)
 360     bitmap[a0] |= mask;
 361   else
 362     bitmap[a0] &= ~mask;
 363
 364   for (a0++; a0 < b0; a0++)
 365     bitmap[a0] = value ? ~0 : 0;
 366
 367   if (a0 == b0)
 368     {
 369       word n_bits_left = n_bits - (BITS (bitmap[0]) - a1);
 370       mask = pow2_mask (n_bits_left);
 371       if (value)
 372         bitmap[a0] |= mask;
 373       else
 374         bitmap[a0] &= ~mask;
 375     }
 376
 377   return bitmap;
 378 }
 379
 380 /** Macro to iterate across set bits in a bitmap
 381
 382     @param i - the current set bit
 383     @param ai - the bitmap
 384     @param body - the expression to evaluate for each set bit
 385 */
 386 #define clib_bitmap_foreach(i,ai)                                       \
 387   if (ai)                                                               \
 388     for (i = clib_bitmap_first_set (ai);                                \
 389          i != ~0;                                                       \
 390          i = clib_bitmap_next_set (ai, i + 1))
 391
 392 /** Return the lowest numbered set bit in a bitmap
 393     @param ai - pointer to the bitmap
 394     @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
 395 */
 396 always_inline uword
 397 clib_bitmap_first_set (uword * ai)
 398 {
 399   uword i = 0;
 400 #if uword_bits == 64
 401 #if defined(CLIB_HAVE_VEC256)
 402   while (i + 7 < vec_len (ai))
 403     {
 404       u64x4 v;
 405       v = u64x4_load_unaligned (ai + i) | u64x4_load_unaligned (ai + i + 4);
 406       if (!u64x4_is_all_zero (v))
 407         break;
 408       i += 8;
 409     }
 410 #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
 411   while (i + 3 < vec_len (ai))
 412     {
 413       u64x2 v;
 414       v = u64x2_load_unaligned (ai + i) | u64x2_load_unaligned (ai + i + 2);
 415       if (!u64x2_is_all_zero (v))
 416         break;
 417       i += 4;
 418     }
 419 #endif
 420 #endif
 421   for (; i < vec_len (ai); i++)
 422     {
 423       uword x = ai[i];
 424       if (x != 0)
 425         return i * BITS (ai[0]) + log2_first_set (x);
 426     }
 427   return ~0;
 428 }
 429
 430 /** Return the higest numbered set bit in a bitmap
 431     @param ai - pointer to the bitmap
 432     @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
 433 */
 434 always_inline uword
 435 clib_bitmap_last_set (uword * ai)
 436 {
 437   uword i;
 438
 439   for (i = vec_len (ai); i > 0; i--)
 440     {
 441       uword x = ai[i - 1];
 442       if (x != 0)
 443         {
 444           uword first_bit;
 445           first_bit = count_leading_zeros (x);
 446           return (i) * BITS (ai[0]) - first_bit - 1;
 447         }
 448     }
 449   return ~0;
 450 }
 451
 452 /** Return the lowest numbered clear bit in a bitmap
 453     @param ai - pointer to the bitmap
 454     @returns lowest numbered clear bit
 455 */
 456 always_inline uword
 457 clib_bitmap_first_clear (uword * ai)
 458 {
 459   uword i;
 460   for (i = 0; i < vec_len (ai); i++)
 461     {
 462       uword x = ~ai[i];
 463       if (x != 0)
 464         return i * BITS (ai[0]) + log2_first_set (x);
 465     }
 466   return i * BITS (ai[0]);
 467 }
 468
 469 /** Return the number of set bits in a bitmap
 470     @param ai - pointer to the bitmap
 471     @returns the number of set bits in the bitmap
 472 */
 473 always_inline uword
 474 clib_bitmap_count_set_bits (uword * ai)
 475 {
 476   uword i;
 477   uword n_set = 0;
 478   for (i = 0; i < vec_len (ai); i++)
 479     n_set += count_set_bits (ai[i]);
 480   return n_set;
 481 }
 482
 483 /** Logical operator across two bitmaps
 484
 485     @param ai - pointer to the destination bitmap
 486     @param bi - pointer to the source bitmap
 487     @returns ai = ai and bi. ai is modified, bi is not modified
 488 */
 489 always_inline uword *clib_bitmap_and (uword * ai, uword * bi);
 490
 491 /** Logical operator across two bitmaps
 492
 493     @param ai - pointer to the destination bitmap
 494     @param bi - pointer to the source bitmap
 495     @returns ai = ai & ~bi. ai is modified, bi is not modified
 496 */
 497 always_inline uword *clib_bitmap_andnot (uword * ai, uword * bi);
 498
 499 /** Logical operator across two bitmaps
 500
 501     @param ai - pointer to the destination bitmap
 502     @param bi - pointer to the source bitmap
 503     @returns ai = ai & ~bi. ai is modified, bi is not modified
 504 */
 505 always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
 506 /** Logical operator across two bitmaps
 507
 508     @param ai - pointer to the destination bitmap
 509     @param bi - pointer to the source bitmap
 510     @returns ai = ai or bi. ai is modified, bi is not modified
 511 */
 512 always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
 513
 514 /** Logical operator across two bitmaps
 515
 516     @param ai - pointer to the destination bitmap
 517     @param bi - pointer to the source bitmap
 518     @returns ai = ai xor bi. ai is modified, bi is not modified
 519 */
 520 always_inline uword *clib_bitmap_xor (uword * ai, uword * bi);
 521
 522 /* ALU function definition macro for functions taking two bitmaps. */
 523 #define _(name, body, check_zero)                               \
 524 always_inline uword *                                           \
 525 clib_bitmap_##name (uword * ai, uword * bi)                     \
 526 {                                                               \
 527   uword i, a, b, bi_len, n_trailing_zeros;                      \
 528                                                                 \
 529   n_trailing_zeros = 0;                                         \
 530   bi_len = vec_len (bi);                                        \
 531   if (bi_len > 0)                                               \
 532     clib_bitmap_vec_validate (ai, bi_len - 1);                  \
 533   for (i = 0; i < vec_len (ai); i++)                            \
 534     {                                                           \
 535       a = ai[i];                                                \
 536       b = i < bi_len ? bi[i] : 0;                               \
 537       do { body; } while (0);                                   \
 538       ai[i] = a;                                                \
 539       if (check_zero)                                           \
 540         n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1);      \
 541     }                                                           \
 542   if (check_zero)                                               \
 543     _vec_len (ai) -= n_trailing_zeros;                          \
 544   return ai;                                                    \
 545 }
 546
 547 /* ALU functions: */
 548 /* *INDENT-OFF* */
 549 _(and, a = a & b, 1)
 550 _(andnot, a = a & ~b, 1)
 551 _(or, a = a | b, 0)
 552 _(xor, a = a ^ b, 1)
 553 /* *INDENT-ON* */
 554 #undef _
 555 /** Logical operator across two bitmaps which duplicates the first bitmap
 556
 557     @param ai - pointer to the destination bitmap
 558     @param bi - pointer to the source bitmap
 559     @returns aiDup = ai and bi. Neither ai nor bi are modified
 560 */
 561 always_inline uword *clib_bitmap_dup_and (uword * ai, uword * bi);
 562
 563 /** Logical operator across two bitmaps which duplicates the first bitmap
 564
 565     @param ai - pointer to the destination bitmap
 566     @param bi - pointer to the source bitmap
 567     @returns aiDup = ai & ~bi. Neither ai nor bi are modified
 568 */
 569 always_inline uword *clib_bitmap_dup_andnot (uword * ai, uword * bi);
 570
 571 /** Logical operator across two bitmaps which duplicates the first bitmap
 572
 573     @param ai - pointer to the destination bitmap
 574     @param bi - pointer to the source bitmap
 575     @returns aiDup = ai or bi. Neither ai nor bi are modified
 576 */
 577 always_inline uword *clib_bitmap_dup_or (uword * ai, uword * bi);
 578
 579 /** Logical operator across two bitmaps which duplicates the first bitmap
 580
 581     @param ai - pointer to the destination bitmap
 582     @param bi - pointer to the source bitmap
 583     @returns aiDup = ai xor bi. Neither ai nor bi are modified
 584 */
 585 always_inline uword *clib_bitmap_dup_xor (uword * ai, uword * bi);
 586
 587 #define _(name)                                         \
 588   always_inline uword *                                 \
 589   clib_bitmap_dup_##name (uword * ai, uword * bi)       \
 590 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
 591
 592 /* *INDENT-OFF* */
 593 _(and);
 594 _(andnot);
 595 _(or);
 596 _(xor);
 597 /* *INDENT-ON* */
 598 #undef _
 599
 600 /* ALU function definition macro for functions taking one bitmap and an
 601  * immediate. */
 602 #define _(name, body, check_zero)                       \
 603 always_inline uword *                                   \
 604 clib_bitmap_##name (uword * ai, uword i)                \
 605 {                                                       \
 606   uword i0 = i / BITS (ai[0]);                          \
 607   uword i1 = i % BITS (ai[0]);                          \
 608   uword a, b;                                           \
 609   clib_bitmap_vec_validate (ai, i0);                    \
 610   a = ai[i0];                                           \
 611   b = (uword) 1 << i1;                                  \
 612   do { body; } while (0);                               \
 613   ai[i0] = a;                                           \
 614   if (check_zero && a == 0)                             \
 615     ai = _clib_bitmap_remove_trailing_zeros (ai);       \
 616   return ai;                                            \
 617 }
 618
 619 /* ALU functions immediate: */
 620 /* *INDENT-OFF* */
 621 _(andi, a = a & b, 1)
 622 _(andnoti, a = a & ~b, 1)
 623 _(ori, a = a | b, 0)
 624 _(xori, a = a ^ b, 1)
 625 /* *INDENT-ON* */
 626 #undef _
 627
 628 /* ALU function definition macro for functions taking one bitmap and an
 629  * immediate. No tail trimming */
 630 #define _(name, body)                                   \
 631 always_inline uword *                                   \
 632 clib_bitmap_##name##_notrim (uword * ai, uword i)       \
 633 {                                                       \
 634   uword i0 = i / BITS (ai[0]);                          \
 635   uword i1 = i % BITS (ai[0]);                          \
 636   uword a, b;                                           \
 637   clib_bitmap_vec_validate (ai, i0);                    \
 638   a = ai[i0];                                           \
 639   b = (uword) 1 << i1;                                  \
 640   do { body; } while (0);                               \
 641   ai[i0] = a;                                           \
 642   return ai;                                            \
 643 }
 644
 645 /* ALU functions immediate: */
 646 /* *INDENT-OFF* */
 647 _(andi, a = a & b)
 648 _(andnoti, a = a & ~b)
 649 _(ori, a = a | b)
 650 _(xori, a = a ^ b)
 651 #undef _
 652 /* *INDENT-ON* */
 653
 654 /** Return a random bitmap of the requested length
 655     @param ai - pointer to the destination bitmap
 656     @param n_bits - number of bits to allocate
 657     @param [in,out] seed - pointer to the random number seed
 658     @returns a reasonably random bitmap based. See random.h.
 659 */
 660 always_inline uword *
 661 clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
 662 {
 663   vec_reset_length (ai);
 664
 665   if (n_bits > 0)
 666     {
 667       uword i = n_bits - 1;
 668       uword i0, i1;
 669       uword log2_rand_max;
 670
 671       log2_rand_max = min_log2 (random_u32_max ());
 672
 673       i0 = i / BITS (ai[0]);
 674       i1 = i % BITS (ai[0]);
 675
 676       clib_bitmap_vec_validate (ai, i0);
 677       for (i = 0; i <= i0; i++)
 678         {
 679           uword n;
 680           for (n = 0; n < BITS (ai[i]); n += log2_rand_max)
 681             ai[i] |= random_u32 (seed) << n;
 682         }
 683       if (i1 + 1 < BITS (ai[0]))
 684         ai[i0] &= (((uword) 1 << (i1 + 1)) - 1);
 685     }
 686   return ai;
 687 }
 688
 689 /** Return the next set bit in a bitmap starting at bit i
 690     @param ai - pointer to the bitmap
 691     @param i - first bit position to test
 692     @returns first set bit position at or after i,
 693     ~0 if no further set bits are found
 694 */
 695 always_inline uword
 696 clib_bitmap_next_set (uword * ai, uword i)
 697 {
 698   uword i0 = i / BITS (ai[0]);
 699   uword i1 = i % BITS (ai[0]);
 700   uword t;
 701
 702   if (i0 < vec_len (ai))
 703     {
 704       t = (ai[i0] >> i1) << i1;
 705       if (t)
 706         return log2_first_set (t) + i0 * BITS (ai[0]);
 707
 708       for (i0++; i0 < vec_len (ai); i0++)
 709         {
 710           t = ai[i0];
 711           if (t)
 712             return log2_first_set (t) + i0 * BITS (ai[0]);
 713         }
 714     }
 715
 716   return ~0;
 717 }
 718
 719 /** Return the next clear bit in a bitmap starting at bit i
 720     @param ai - pointer to the bitmap
 721     @param i - first bit position to test
 722     @returns first clear bit position at or after i
 723 */
 724 always_inline uword
 725 clib_bitmap_next_clear (uword * ai, uword i)
 726 {
 727   uword i0 = i / BITS (ai[0]);
 728   uword i1 = i % BITS (ai[0]);
 729   uword t;
 730
 731   if (i0 < vec_len (ai))
 732     {
 733       t = (~ai[i0] >> i1) << i1;
 734       if (t)
 735         return log2_first_set (t) + i0 * BITS (ai[0]);
 736
 737       for (i0++; i0 < vec_len (ai); i0++)
 738         {
 739           t = ~ai[i0];
 740           if (t)
 741             return log2_first_set (t) + i0 * BITS (ai[0]);
 742         }
 743
 744       return i0 * BITS (ai[0]);
 745     }
 746   return i;
 747 }
 748
 749 uword unformat_bitmap_mask (unformat_input_t *input, va_list *va);
 750 uword unformat_bitmap_list (unformat_input_t *input, va_list *va);
 751 u8 *format_bitmap_hex (u8 *s, va_list *args);
 752 u8 *format_bitmap_list (u8 *s, va_list *args);
 753
 754 #endif /* included_clib_bitmap_h */
 755
 756 /*
 757  * fd.io coding-style-patch-verification: ON
 758  *
 759  * Local Variables:
 760  * eval: (c-set-style "gnu")
 761  * End:
 762  */