tools/testing/selftests/kvm/lib/sparsebit.c

   1 /*
   2  * Sparse bit array
   3  *
   4  * Copyright (C) 2018, Google LLC.
   5  * Copyright (C) 2018, Red Hat, Inc. (code style cleanup and fuzzing driver)
   6  *
   7  * This work is licensed under the terms of the GNU GPL, version 2.
   8  *
   9  * This library provides functions to support a memory efficient bit array,
  10  * with an index size of 2^64.  A sparsebit array is allocated through
  11  * the use sparsebit_alloc() and free'd via sparsebit_free(),
  12  * such as in the following:
  13  *
  14  *   struct sparsebit *s;
  15  *   s = sparsebit_alloc();
  16  *   sparsebit_free(&s);
  17  *
  18  * The struct sparsebit type resolves down to a struct sparsebit.
  19  * Note that, sparsebit_free() takes a pointer to the sparsebit
  20  * structure.  This is so that sparsebit_free() is able to poison
  21  * the pointer (e.g. set it to NULL) to the struct sparsebit before
  22  * returning to the caller.
  23  *
  24  * Between the return of sparsebit_alloc() and the call of
  25  * sparsebit_free(), there are multiple query and modifying operations
  26  * that can be performed on the allocated sparsebit array.  All of
  27  * these operations take as a parameter the value returned from
  28  * sparsebit_alloc() and most also take a bit index.  Frequently
  29  * used routines include:
  30  *
  31  *  ---- Query Operations
  32  *  sparsebit_is_set(s, idx)
  33  *  sparsebit_is_clear(s, idx)
  34  *  sparsebit_any_set(s)
  35  *  sparsebit_first_set(s)
  36  *  sparsebit_next_set(s, prev_idx)
  37  *
  38  *  ---- Modifying Operations
  39  *  sparsebit_set(s, idx)
  40  *  sparsebit_clear(s, idx)
  41  *  sparsebit_set_num(s, idx, num);
  42  *  sparsebit_clear_num(s, idx, num);
  43  *
  44  * A common operation, is to itterate over all the bits set in a test
  45  * sparsebit array.  This can be done via code with the following structure:
  46  *
  47  *   sparsebit_idx_t idx;
  48  *   if (sparsebit_any_set(s)) {
  49  *     idx = sparsebit_first_set(s);
  50  *     do {
  51  *       ...
  52  *       idx = sparsebit_next_set(s, idx);
  53  *     } while (idx != 0);
  54  *   }
  55  *
  56  * The index of the first bit set needs to be obtained via
  57  * sparsebit_first_set(), because sparsebit_next_set(), needs
  58  * the index of the previously set.  The sparsebit_idx_t type is
  59  * unsigned, so there is no previous index before 0 that is available.
  60  * Also, the call to sparsebit_first_set() is not made unless there
  61  * is at least 1 bit in the array set.  This is because sparsebit_first_set()
  62  * aborts if sparsebit_first_set() is called with no bits set.
  63  * It is the callers responsibility to assure that the
  64  * sparsebit array has at least a single bit set before calling
  65  * sparsebit_first_set().
  66  *
  67  * ==== Implementation Overview ====
  68  * For the most part the internal implementation of sparsebit is
  69  * opaque to the caller.  One important implementation detail that the
  70  * caller may need to be aware of is the spatial complexity of the
  71  * implementation.  This implementation of a sparsebit array is not
  72  * only sparse, in that it uses memory proportional to the number of bits
  73  * set.  It is also efficient in memory usage when most of the bits are
  74  * set.
  75  *
  76  * At a high-level the state of the bit settings are maintained through
  77  * the use of a binary-search tree, where each node contains at least
  78  * the following members:
  79  *
  80  *   typedef uint64_t sparsebit_idx_t;
  81  *   typedef uint64_t sparsebit_num_t;
  82  *
  83  *   sparsebit_idx_t idx;
  84  *   uint32_t mask;
  85  *   sparsebit_num_t num_after;
  86  *
  87  * The idx member contains the bit index of the first bit described by this
  88  * node, while the mask member stores the setting of the first 32-bits.
  89  * The setting of the bit at idx + n, where 0 <= n < 32, is located in the
  90  * mask member at 1 << n.
  91  *
  92  * Nodes are sorted by idx and the bits described by two nodes will never
  93  * overlap. The idx member is always aligned to the mask size, i.e. a
  94  * multiple of 32.
  95  *
  96  * Beyond a typical implementation, the nodes in this implementation also
  97  * contains a member named num_after.  The num_after member holds the
  98  * number of bits immediately after the mask bits that are contiguously set.
  99  * The use of the num_after member allows this implementation to efficiently
 100  * represent cases where most bits are set.  For example, the case of all
 101  * but the last two bits set, is represented by the following two nodes:
 102  *
 103  *   node 0 - idx: 0x0 mask: 0xffffffff num_after: 0xffffffffffffffc0
 104  *   node 1 - idx: 0xffffffffffffffe0 mask: 0x3fffffff num_after: 0
 105  *
 106  * ==== Invariants ====
 107  * This implementation usses the following invariants:
 108  *
 109  *   + Node are only used to represent bits that are set.
 110  *     Nodes with a mask of 0 and num_after of 0 are not allowed.
 111  *
 112  *   + Sum of bits set in all the nodes is equal to the value of
 113  *     the struct sparsebit_pvt num_set member.
 114  *
 115  *   + The setting of at least one bit is always described in a nodes
 116  *     mask (mask >= 1).
 117  *
 118  *   + A node with all mask bits set only occurs when the last bit
 119  *     described by the previous node is not equal to this nodes
 120  *     starting index - 1.  All such occurences of this condition are
 121  *     avoided by moving the setting of the nodes mask bits into
 122  *     the previous nodes num_after setting.
 123  *
 124  *   + Node starting index is evenly divisable by the number of bits
 125  *     within a nodes mask member.
 126  *
 127  *   + Nodes never represent a range of bits that wrap around the
 128  *     highest supported index.
 129  *
 130  *      (idx + MASK_BITS + num_after - 1) <= ((sparsebit_idx_t) 0) - 1)
 131  *
 132  *     As a consequence of the above, the num_after member of a node
 133  *     will always be <=:
 134  *
 135  *       maximum_index - nodes_starting_index - number_of_mask_bits
 136  *
 137  *   + Nodes within the binary search tree are sorted based on each
 138  *     nodes starting index.
 139  *
 140  *   + The range of bits described by any two nodes do not overlap.  The
 141  *     range of bits described by a single node is:
 142  *
 143  *       start: node->idx
 144  *       end (inclusive): node->idx + MASK_BITS + node->num_after - 1;
 145  *
 146  * Note, at times these invariants are temporarily violated for a
 147  * specific portion of the code.  For example, when setting a mask
 148  * bit, there is a small delay between when the mask bit is set and the
 149  * value in the struct sparsebit_pvt num_set member is updated.  Other
 150  * temporary violations occur when node_split() is called with a specified
 151  * index and assures that a node where its mask represents the bit
 152  * at the specified index exists.  At times to do this node_split()
 153  * must split an existing node into two nodes or create a node that
 154  * has no bits set.  Such temporary violations must be corrected before
 155  * returning to the caller.  These corrections are typically performed
 156  * by the local function node_reduce().
 157  */
 158
 159 #include "test_util.h"
 160 #include "sparsebit.h"
 161 #include <limits.h>
 162 #include <assert.h>
 163
 164 #define DUMP_LINE_MAX 100 /* Does not include indent amount */
 165
 166 typedef uint32_t mask_t;
 167 #define MASK_BITS (sizeof(mask_t) * CHAR_BIT)
 168
 169 struct node {
 170         struct node *parent;
 171         struct node *left;
 172         struct node *right;
 173         sparsebit_idx_t idx; /* index of least-significant bit in mask */
 174         sparsebit_num_t num_after; /* num contiguously set after mask */
 175         mask_t mask;
 176 };
 177
 178 struct sparsebit {
 179         /*
 180          * Points to root node of the binary search
 181          * tree.  Equal to NULL when no bits are set in
 182          * the entire sparsebit array.
 183          */
 184         struct node *root;
 185
 186         /*
 187          * A redundant count of the total number of bits set.  Used for
 188          * diagnostic purposes and to change the time complexity of
 189          * sparsebit_num_set() from O(n) to O(1).
 190          * Note: Due to overflow, a value of 0 means none or all set.
 191          */
 192         sparsebit_num_t num_set;
 193 };
 194
 195 /* Returns the number of set bits described by the settings
 196  * of the node pointed to by nodep.
 197  */
 198 static sparsebit_num_t node_num_set(struct node *nodep)
 199 {
 200         return nodep->num_after + __builtin_popcount(nodep->mask);
 201 }
 202
 203 /* Returns a pointer to the node that describes the
 204  * lowest bit index.
 205  */
 206 static struct node *node_first(struct sparsebit *s)
 207 {
 208         struct node *nodep;
 209
 210         for (nodep = s->root; nodep && nodep->left; nodep = nodep->left)
 211                 ;
 212
 213         return nodep;
 214 }
 215
 216 /* Returns a pointer to the node that describes the
 217  * lowest bit index > the index of the node pointed to by np.
 218  * Returns NULL if no node with a higher index exists.
 219  */
 220 static struct node *node_next(struct sparsebit *s, struct node *np)
 221 {
 222         struct node *nodep = np;
 223
 224         /*
 225          * If current node has a right child, next node is the left-most
 226          * of the right child.
 227          */
 228         if (nodep->right) {
 229                 for (nodep = nodep->right; nodep->left; nodep = nodep->left)
 230                         ;
 231                 return nodep;
 232         }
 233
 234         /*
 235          * No right child.  Go up until node is left child of a parent.
 236          * That parent is then the next node.
 237          */
 238         while (nodep->parent && nodep == nodep->parent->right)
 239                 nodep = nodep->parent;
 240
 241         return nodep->parent;
 242 }
 243
 244 /* Searches for and returns a pointer to the node that describes the
 245  * highest index < the index of the node pointed to by np.
 246  * Returns NULL if no node with a lower index exists.
 247  */
 248 static struct node *node_prev(struct sparsebit *s, struct node *np)
 249 {
 250         struct node *nodep = np;
 251
 252         /*
 253          * If current node has a left child, next node is the right-most
 254          * of the left child.
 255          */
 256         if (nodep->left) {
 257                 for (nodep = nodep->left; nodep->right; nodep = nodep->right)
 258                         ;
 259                 return (struct node *) nodep;
 260         }
 261
 262         /*
 263          * No left child.  Go up until node is right child of a parent.
 264          * That parent is then the next node.
 265          */
 266         while (nodep->parent && nodep == nodep->parent->left)
 267                 nodep = nodep->parent;
 268
 269         return (struct node *) nodep->parent;
 270 }
 271
 272
 273 /* Allocates space to hold a copy of the node sub-tree pointed to by
 274  * subtree and duplicates the bit settings to the newly allocated nodes.
 275  * Returns the newly allocated copy of subtree.
 276  */
 277 static struct node *node_copy_subtree(struct node *subtree)
 278 {
 279         struct node *root;
 280
 281         /* Duplicate the node at the root of the subtree */
 282         root = calloc(1, sizeof(*root));
 283         if (!root) {
 284                 perror("calloc");
 285                 abort();
 286         }
 287
 288         root->idx = subtree->idx;
 289         root->mask = subtree->mask;
 290         root->num_after = subtree->num_after;
 291
 292         /* As needed, recursively duplicate the left and right subtrees */
 293         if (subtree->left) {
 294                 root->left = node_copy_subtree(subtree->left);
 295                 root->left->parent = root;
 296         }
 297
 298         if (subtree->right) {
 299                 root->right = node_copy_subtree(subtree->right);
 300                 root->right->parent = root;
 301         }
 302
 303         return root;
 304 }
 305
 306 /* Searches for and returns a pointer to the node that describes the setting
 307  * of the bit given by idx.  A node describes the setting of a bit if its
 308  * index is within the bits described by the mask bits or the number of
 309  * contiguous bits set after the mask.  Returns NULL if there is no such node.
 310  */
 311 static struct node *node_find(struct sparsebit *s, sparsebit_idx_t idx)
 312 {
 313         struct node *nodep;
 314
 315         /* Find the node that describes the setting of the bit at idx */
 316         for (nodep = s->root; nodep;
 317              nodep = nodep->idx > idx ? nodep->left : nodep->right) {
 318                 if (idx >= nodep->idx &&
 319                     idx <= nodep->idx + MASK_BITS + nodep->num_after - 1)
 320                         break;
 321         }
 322
 323         return nodep;
 324 }
 325
 326 /* Entry Requirements:
 327  *   + A node that describes the setting of idx is not already present.
 328  *
 329  * Adds a new node to describe the setting of the bit at the index given
 330  * by idx.  Returns a pointer to the newly added node.
 331  *
 332  * TODO(lhuemill): Degenerate cases causes the tree to get unbalanced.
 333  */
 334 static struct node *node_add(struct sparsebit *s, sparsebit_idx_t idx)
 335 {
 336         struct node *nodep, *parentp, *prev;
 337
 338         /* Allocate and initialize the new node. */
 339         nodep = calloc(1, sizeof(*nodep));
 340         if (!nodep) {
 341                 perror("calloc");
 342                 abort();
 343         }
 344
 345         nodep->idx = idx & -MASK_BITS;
 346
 347         /* If no nodes, set it up as the root node. */
 348         if (!s->root) {
 349                 s->root = nodep;
 350                 return nodep;
 351         }
 352
 353         /*
 354          * Find the parent where the new node should be attached
 355          * and add the node there.
 356          */
 357         parentp = s->root;
 358         while (true) {
 359                 if (idx < parentp->idx) {
 360                         if (!parentp->left) {
 361                                 parentp->left = nodep;
 362                                 nodep->parent = parentp;
 363                                 break;
 364                         }
 365                         parentp = parentp->left;
 366                 } else {
 367                         assert(idx > parentp->idx + MASK_BITS + parentp->num_after - 1);
 368                         if (!parentp->right) {
 369                                 parentp->right = nodep;
 370                                 nodep->parent = parentp;
 371                                 break;
 372                         }
 373                         parentp = parentp->right;
 374                 }
 375         }
 376
 377         /*
 378          * Does num_after bits of previous node overlap with the mask
 379          * of the new node?  If so set the bits in the new nodes mask
 380          * and reduce the previous nodes num_after.
 381          */
 382         prev = node_prev(s, nodep);
 383         while (prev && prev->idx + MASK_BITS + prev->num_after - 1 >= nodep->idx) {
 384                 unsigned int n1 = (prev->idx + MASK_BITS + prev->num_after - 1)
 385                         - nodep->idx;
 386                 assert(prev->num_after > 0);
 387                 assert(n1 < MASK_BITS);
 388                 assert(!(nodep->mask & (1 << n1)));
 389                 nodep->mask |= (1 << n1);
 390                 prev->num_after--;
 391         }
 392
 393         return nodep;
 394 }
 395
 396 /* Returns whether all the bits in the sparsebit array are set.  */
 397 bool sparsebit_all_set(struct sparsebit *s)
 398 {
 399         /*
 400          * If any nodes there must be at least one bit set.  Only case
 401          * where a bit is set and total num set is 0, is when all bits
 402          * are set.
 403          */
 404         return s->root && s->num_set == 0;
 405 }
 406
 407 /* Clears all bits described by the node pointed to by nodep, then
 408  * removes the node.
 409  */
 410 static void node_rm(struct sparsebit *s, struct node *nodep)
 411 {
 412         struct node *tmp;
 413         sparsebit_num_t num_set;
 414
 415         num_set = node_num_set(nodep);
 416         assert(s->num_set >= num_set || sparsebit_all_set(s));
 417         s->num_set -= node_num_set(nodep);
 418
 419         /* Have both left and right child */
 420         if (nodep->left && nodep->right) {
 421                 /*
 422                  * Move left children to the leftmost leaf node
 423                  * of the right child.
 424                  */
 425                 for (tmp = nodep->right; tmp->left; tmp = tmp->left)
 426                         ;
 427                 tmp->left = nodep->left;
 428                 nodep->left = NULL;
 429                 tmp->left->parent = tmp;
 430         }
 431
 432         /* Left only child */
 433         if (nodep->left) {
 434                 if (!nodep->parent) {
 435                         s->root = nodep->left;
 436                         nodep->left->parent = NULL;
 437                 } else {
 438                         nodep->left->parent = nodep->parent;
 439                         if (nodep == nodep->parent->left)
 440                                 nodep->parent->left = nodep->left;
 441                         else {
 442                                 assert(nodep == nodep->parent->right);
 443                                 nodep->parent->right = nodep->left;
 444                         }
 445                 }
 446
 447                 nodep->parent = nodep->left = nodep->right = NULL;
 448                 free(nodep);
 449
 450                 return;
 451         }
 452
 453
 454         /* Right only child */
 455         if (nodep->right) {
 456                 if (!nodep->parent) {
 457                         s->root = nodep->right;
 458                         nodep->right->parent = NULL;
 459                 } else {
 460                         nodep->right->parent = nodep->parent;
 461                         if (nodep == nodep->parent->left)
 462                                 nodep->parent->left = nodep->right;
 463                         else {
 464                                 assert(nodep == nodep->parent->right);
 465                                 nodep->parent->right = nodep->right;
 466                         }
 467                 }
 468
 469                 nodep->parent = nodep->left = nodep->right = NULL;
 470                 free(nodep);
 471
 472                 return;
 473         }
 474
 475         /* Leaf Node */
 476         if (!nodep->parent) {
 477                 s->root = NULL;
 478         } else {
 479                 if (nodep->parent->left == nodep)
 480                         nodep->parent->left = NULL;
 481                 else {
 482                         assert(nodep == nodep->parent->right);
 483                         nodep->parent->right = NULL;
 484                 }
 485         }
 486
 487         nodep->parent = nodep->left = nodep->right = NULL;
 488         free(nodep);
 489
 490         return;
 491 }
 492
 493 /* Splits the node containing the bit at idx so that there is a node
 494  * that starts at the specified index.  If no such node exists, a new
 495  * node at the specified index is created.  Returns the new node.
 496  *
 497  * idx must start of a mask boundary.
 498  */
 499 static struct node *node_split(struct sparsebit *s, sparsebit_idx_t idx)
 500 {
 501         struct node *nodep1, *nodep2;
 502         sparsebit_idx_t offset;
 503         sparsebit_num_t orig_num_after;
 504
 505         assert(!(idx % MASK_BITS));
 506
 507         /*
 508          * Is there a node that describes the setting of idx?
 509          * If not, add it.
 510          */
 511         nodep1 = node_find(s, idx);
 512         if (!nodep1)
 513                 return node_add(s, idx);
 514
 515         /*
 516          * All done if the starting index of the node is where the
 517          * split should occur.
 518          */
 519         if (nodep1->idx == idx)
 520                 return nodep1;
 521
 522         /*
 523          * Split point not at start of mask, so it must be part of
 524          * bits described by num_after.
 525          */
 526
 527         /*
 528          * Calculate offset within num_after for where the split is
 529          * to occur.
 530          */
 531         offset = idx - (nodep1->idx + MASK_BITS);
 532         orig_num_after = nodep1->num_after;
 533
 534         /*
 535          * Add a new node to describe the bits starting at
 536          * the split point.
 537          */
 538         nodep1->num_after = offset;
 539         nodep2 = node_add(s, idx);
 540
 541         /* Move bits after the split point into the new node */
 542         nodep2->num_after = orig_num_after - offset;
 543         if (nodep2->num_after >= MASK_BITS) {
 544                 nodep2->mask = ~(mask_t) 0;
 545                 nodep2->num_after -= MASK_BITS;
 546         } else {
 547                 nodep2->mask = (1 << nodep2->num_after) - 1;
 548                 nodep2->num_after = 0;
 549         }
 550
 551         return nodep2;
 552 }
 553
 554 /* Iteratively reduces the node pointed to by nodep and its adjacent
 555  * nodes into a more compact form.  For example, a node with a mask with
 556  * all bits set adjacent to a previous node, will get combined into a
 557  * single node with an increased num_after setting.
 558  *
 559  * After each reduction, a further check is made to see if additional
 560  * reductions are possible with the new previous and next nodes.  Note,
 561  * a search for a reduction is only done across the nodes nearest nodep
 562  * and those that became part of a reduction.  Reductions beyond nodep
 563  * and the adjacent nodes that are reduced are not discovered.  It is the
 564  * responsibility of the caller to pass a nodep that is within one node
 565  * of each possible reduction.
 566  *
 567  * This function does not fix the temporary violation of all invariants.
 568  * For example it does not fix the case where the bit settings described
 569  * by two or more nodes overlap.  Such a violation introduces the potential
 570  * complication of a bit setting for a specific index having different settings
 571  * in different nodes.  This would then introduce the further complication
 572  * of which node has the correct setting of the bit and thus such conditions
 573  * are not allowed.
 574  *
 575  * This function is designed to fix invariant violations that are introduced
 576  * by node_split() and by changes to the nodes mask or num_after members.
 577  * For example, when setting a bit within a nodes mask, the function that
 578  * sets the bit doesn't have to worry about whether the setting of that
 579  * bit caused the mask to have leading only or trailing only bits set.
 580  * Instead, the function can call node_reduce(), with nodep equal to the
 581  * node address that it set a mask bit in, and node_reduce() will notice
 582  * the cases of leading or trailing only bits and that there is an
 583  * adjacent node that the bit settings could be merged into.
 584  *
 585  * This implementation specifically detects and corrects violation of the
 586  * following invariants:
 587  *
 588  *   + Node are only used to represent bits that are set.
 589  *     Nodes with a mask of 0 and num_after of 0 are not allowed.
 590  *
 591  *   + The setting of at least one bit is always described in a nodes
 592  *     mask (mask >= 1).
 593  *
 594  *   + A node with all mask bits set only occurs when the last bit
 595  *     described by the previous node is not equal to this nodes
 596  *     starting index - 1.  All such occurences of this condition are
 597  *     avoided by moving the setting of the nodes mask bits into
 598  *     the previous nodes num_after setting.
 599  */
 600 static void node_reduce(struct sparsebit *s, struct node *nodep)
 601 {
 602         bool reduction_performed;
 603
 604         do {
 605                 reduction_performed = false;
 606                 struct node *prev, *next, *tmp;
 607
 608                 /* 1) Potential reductions within the current node. */
 609
 610                 /* Nodes with all bits cleared may be removed. */
 611                 if (nodep->mask == 0 && nodep->num_after == 0) {
 612                         /*
 613                          * About to remove the node pointed to by
 614                          * nodep, which normally would cause a problem
 615                          * for the next pass through the reduction loop,
 616                          * because the node at the starting point no longer
 617                          * exists.  This potential problem is handled
 618                          * by first remembering the location of the next
 619                          * or previous nodes.  Doesn't matter which, because
 620                          * once the node at nodep is removed, there will be
 621                          * no other nodes between prev and next.
 622                          *
 623                          * Note, the checks performed on nodep against both
 624                          * both prev and next both check for an adjacent
 625                          * node that can be reduced into a single node.  As
 626                          * such, after removing the node at nodep, doesn't
 627                          * matter whether the nodep for the next pass
 628                          * through the loop is equal to the previous pass
 629                          * prev or next node.  Either way, on the next pass
 630                          * the one not selected will become either the
 631                          * prev or next node.
 632                          */
 633                         tmp = node_next(s, nodep);
 634                         if (!tmp)
 635                                 tmp = node_prev(s, nodep);
 636
 637                         node_rm(s, nodep);
 638                         nodep = NULL;
 639
 640                         nodep = tmp;
 641                         reduction_performed = true;
 642                         continue;
 643                 }
 644
 645                 /*
 646                  * When the mask is 0, can reduce the amount of num_after
 647                  * bits by moving the initial num_after bits into the mask.
 648                  */
 649                 if (nodep->mask == 0) {
 650                         assert(nodep->num_after != 0);
 651                         assert(nodep->idx + MASK_BITS > nodep->idx);
 652
 653                         nodep->idx += MASK_BITS;
 654
 655                         if (nodep->num_after >= MASK_BITS) {
 656                                 nodep->mask = ~0;
 657                                 nodep->num_after -= MASK_BITS;
 658                         } else {
 659                                 nodep->mask = (1u << nodep->num_after) - 1;
 660                                 nodep->num_after = 0;
 661                         }
 662
 663                         reduction_performed = true;
 664                         continue;
 665                 }
 666
 667                 /*
 668                  * 2) Potential reductions between the current and
 669                  * previous nodes.
 670                  */
 671                 prev = node_prev(s, nodep);
 672                 if (prev) {
 673                         sparsebit_idx_t prev_highest_bit;
 674
 675                         /* Nodes with no bits set can be removed. */
 676                         if (prev->mask == 0 && prev->num_after == 0) {
 677                                 node_rm(s, prev);
 678
 679                                 reduction_performed = true;
 680                                 continue;
 681                         }
 682
 683                         /*
 684                          * All mask bits set and previous node has
 685                          * adjacent index.
 686                          */
 687                         if (nodep->mask + 1 == 0 &&
 688                             prev->idx + MASK_BITS == nodep->idx) {
 689                                 prev->num_after += MASK_BITS + nodep->num_after;
 690                                 nodep->mask = 0;
 691                                 nodep->num_after = 0;
 692
 693                                 reduction_performed = true;
 694                                 continue;
 695                         }
 696
 697                         /*
 698                          * Is node adjacent to previous node and the node
 699                          * contains a single contiguous range of bits
 700                          * starting from the beginning of the mask?
 701                          */
 702                         prev_highest_bit = prev->idx + MASK_BITS - 1 + prev->num_after;
 703                         if (prev_highest_bit + 1 == nodep->idx &&
 704                             (nodep->mask | (nodep->mask >> 1)) == nodep->mask) {
 705                                 /*
 706                                  * How many contiguous bits are there?
 707                                  * Is equal to the total number of set
 708                                  * bits, due to an earlier check that
 709                                  * there is a single contiguous range of
 710                                  * set bits.
 711                                  */
 712                                 unsigned int num_contiguous
 713                                         = __builtin_popcount(nodep->mask);
 714                                 assert((num_contiguous > 0) &&
 715                                        ((1ULL << num_contiguous) - 1) == nodep->mask);
 716
 717                                 prev->num_after += num_contiguous;
 718                                 nodep->mask = 0;
 719
 720                                 /*
 721                                  * For predictable performance, handle special
 722                                  * case where all mask bits are set and there
 723                                  * is a non-zero num_after setting.  This code
 724                                  * is functionally correct without the following
 725                                  * conditionalized statements, but without them
 726                                  * the value of num_after is only reduced by
 727                                  * the number of mask bits per pass.  There are
 728                                  * cases where num_after can be close to 2^64.
 729                                  * Without this code it could take nearly
 730                                  * (2^64) / 32 passes to perform the full
 731                                  * reduction.
 732                                  */
 733                                 if (num_contiguous == MASK_BITS) {
 734                                         prev->num_after += nodep->num_after;
 735                                         nodep->num_after = 0;
 736                                 }
 737
 738                                 reduction_performed = true;
 739                                 continue;
 740                         }
 741                 }
 742
 743                 /*
 744                  * 3) Potential reductions between the current and
 745                  * next nodes.
 746                  */
 747                 next = node_next(s, nodep);
 748                 if (next) {
 749                         /* Nodes with no bits set can be removed. */
 750                         if (next->mask == 0 && next->num_after == 0) {
 751                                 node_rm(s, next);
 752                                 reduction_performed = true;
 753                                 continue;
 754                         }
 755
 756                         /*
 757                          * Is next node index adjacent to current node
 758                          * and has a mask with all bits set?
 759                          */
 760                         if (next->idx == nodep->idx + MASK_BITS + nodep->num_after &&
 761                             next->mask == ~(mask_t) 0) {
 762                                 nodep->num_after += MASK_BITS;
 763                                 next->mask = 0;
 764                                 nodep->num_after += next->num_after;
 765                                 next->num_after = 0;
 766
 767                                 node_rm(s, next);
 768                                 next = NULL;
 769
 770                                 reduction_performed = true;
 771                                 continue;
 772                         }
 773                 }
 774         } while (nodep && reduction_performed);
 775 }
 776
 777 /* Returns whether the bit at the index given by idx, within the
 778  * sparsebit array is set or not.
 779  */
 780 bool sparsebit_is_set(struct sparsebit *s, sparsebit_idx_t idx)
 781 {
 782         struct node *nodep;
 783
 784         /* Find the node that describes the setting of the bit at idx */
 785         for (nodep = s->root; nodep;
 786              nodep = nodep->idx > idx ? nodep->left : nodep->right)
 787                 if (idx >= nodep->idx &&
 788                     idx <= nodep->idx + MASK_BITS + nodep->num_after - 1)
 789                         goto have_node;
 790
 791         return false;
 792
 793 have_node:
 794         /* Bit is set if it is any of the bits described by num_after */
 795         if (nodep->num_after && idx >= nodep->idx + MASK_BITS)
 796                 return true;
 797
 798         /* Is the corresponding mask bit set */
 799         assert(idx >= nodep->idx && idx - nodep->idx < MASK_BITS);
 800         return !!(nodep->mask & (1 << (idx - nodep->idx)));
 801 }
 802
 803 /* Within the sparsebit array pointed to by s, sets the bit
 804  * at the index given by idx.
 805  */
 806 static void bit_set(struct sparsebit *s, sparsebit_idx_t idx)
 807 {
 808         struct node *nodep;
 809
 810         /* Skip bits that are already set */
 811         if (sparsebit_is_set(s, idx))
 812                 return;
 813
 814         /*
 815          * Get a node where the bit at idx is described by the mask.
 816          * The node_split will also create a node, if there isn't
 817          * already a node that describes the setting of bit.
 818          */
 819         nodep = node_split(s, idx & -MASK_BITS);
 820
 821         /* Set the bit within the nodes mask */
 822         assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1);
 823         assert(!(nodep->mask & (1 << (idx - nodep->idx))));
 824         nodep->mask |= 1 << (idx - nodep->idx);
 825         s->num_set++;
 826
 827         node_reduce(s, nodep);
 828 }
 829
 830 /* Within the sparsebit array pointed to by s, clears the bit
 831  * at the index given by idx.
 832  */
 833 static void bit_clear(struct sparsebit *s, sparsebit_idx_t idx)
 834 {
 835         struct node *nodep;
 836
 837         /* Skip bits that are already cleared */
 838         if (!sparsebit_is_set(s, idx))
 839                 return;
 840
 841         /* Is there a node that describes the setting of this bit? */
 842         nodep = node_find(s, idx);
 843         if (!nodep)
 844                 return;
 845
 846         /*
 847          * If a num_after bit, split the node, so that the bit is
 848          * part of a node mask.
 849          */
 850         if (idx >= nodep->idx + MASK_BITS)
 851                 nodep = node_split(s, idx & -MASK_BITS);
 852
 853         /*
 854          * After node_split above, bit at idx should be within the mask.
 855          * Clear that bit.
 856          */
 857         assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1);
 858         assert(nodep->mask & (1 << (idx - nodep->idx)));
 859         nodep->mask &= ~(1 << (idx - nodep->idx));
 860         assert(s->num_set > 0 || sparsebit_all_set(s));
 861         s->num_set--;
 862
 863         node_reduce(s, nodep);
 864 }
 865
 866 /* Recursively dumps to the FILE stream given by stream the contents
 867  * of the sub-tree of nodes pointed to by nodep.  Each line of output
 868  * is prefixed by the number of spaces given by indent.  On each
 869  * recursion, the indent amount is increased by 2.  This causes nodes
 870  * at each level deeper into the binary search tree to be displayed
 871  * with a greater indent.
 872  */
 873 static void dump_nodes(FILE *stream, struct node *nodep,
 874         unsigned int indent)
 875 {
 876         char *node_type;
 877
 878         /* Dump contents of node */
 879         if (!nodep->parent)
 880                 node_type = "root";
 881         else if (nodep == nodep->parent->left)
 882                 node_type = "left";
 883         else {
 884                 assert(nodep == nodep->parent->right);
 885                 node_type = "right";
 886         }
 887         fprintf(stream, "%*s---- %s nodep: %p\n", indent, "", node_type, nodep);
 888         fprintf(stream, "%*s  parent: %p left: %p right: %p\n", indent, "",
 889                 nodep->parent, nodep->left, nodep->right);
 890         fprintf(stream, "%*s  idx: 0x%lx mask: 0x%x num_after: 0x%lx\n",
 891                 indent, "", nodep->idx, nodep->mask, nodep->num_after);
 892
 893         /* If present, dump contents of left child nodes */
 894         if (nodep->left)
 895                 dump_nodes(stream, nodep->left, indent + 2);
 896
 897         /* If present, dump contents of right child nodes */
 898         if (nodep->right)
 899                 dump_nodes(stream, nodep->right, indent + 2);
 900 }
 901
 902 static inline sparsebit_idx_t node_first_set(struct node *nodep, int start)
 903 {
 904         mask_t leading = (mask_t)1 << start;
 905         int n1 = __builtin_ctz(nodep->mask & -leading);
 906
 907         return nodep->idx + n1;
 908 }
 909
 910 static inline sparsebit_idx_t node_first_clear(struct node *nodep, int start)
 911 {
 912         mask_t leading = (mask_t)1 << start;
 913         int n1 = __builtin_ctz(~nodep->mask & -leading);
 914
 915         return nodep->idx + n1;
 916 }
 917
 918 /* Dumps to the FILE stream specified by stream, the implementation dependent
 919  * internal state of s.  Each line of output is prefixed with the number
 920  * of spaces given by indent.  The output is completely implementation
 921  * dependent and subject to change.  Output from this function should only
 922  * be used for diagnostic purposes.  For example, this function can be
 923  * used by test cases after they detect an unexpected condition, as a means
 924  * to capture diagnostic information.
 925  */
 926 static void sparsebit_dump_internal(FILE *stream, struct sparsebit *s,
 927         unsigned int indent)
 928 {
 929         /* Dump the contents of s */
 930         fprintf(stream, "%*sroot: %p\n", indent, "", s->root);
 931         fprintf(stream, "%*snum_set: 0x%lx\n", indent, "", s->num_set);
 932
 933         if (s->root)
 934                 dump_nodes(stream, s->root, indent);
 935 }
 936
 937 /* Allocates and returns a new sparsebit array. The initial state
 938  * of the newly allocated sparsebit array has all bits cleared.
 939  */
 940 struct sparsebit *sparsebit_alloc(void)
 941 {
 942         struct sparsebit *s;
 943
 944         /* Allocate top level structure. */
 945         s = calloc(1, sizeof(*s));
 946         if (!s) {
 947                 perror("calloc");
 948                 abort();
 949         }
 950
 951         return s;
 952 }
 953
 954 /* Frees the implementation dependent data for the sparsebit array
 955  * pointed to by s and poisons the pointer to that data.
 956  */
 957 void sparsebit_free(struct sparsebit **sbitp)
 958 {
 959         struct sparsebit *s = *sbitp;
 960
 961         if (!s)
 962                 return;
 963
 964         sparsebit_clear_all(s);
 965         free(s);
 966         *sbitp = NULL;
 967 }
 968
 969 /* Makes a copy of the sparsebit array given by s, to the sparsebit
 970  * array given by d.  Note, d must have already been allocated via
 971  * sparsebit_alloc().  It can though already have bits set, which
 972  * if different from src will be cleared.
 973  */
 974 void sparsebit_copy(struct sparsebit *d, struct sparsebit *s)
 975 {
 976         /* First clear any bits already set in the destination */
 977         sparsebit_clear_all(d);
 978
 979         if (s->root) {
 980                 d->root = node_copy_subtree(s->root);
 981                 d->num_set = s->num_set;
 982         }
 983 }
 984
 985 /* Returns whether num consecutive bits starting at idx are all set.  */
 986 bool sparsebit_is_set_num(struct sparsebit *s,
 987         sparsebit_idx_t idx, sparsebit_num_t num)
 988 {
 989         sparsebit_idx_t next_cleared;
 990
 991         assert(num > 0);
 992         assert(idx + num - 1 >= idx);
 993
 994         /* With num > 0, the first bit must be set. */
 995         if (!sparsebit_is_set(s, idx))
 996                 return false;
 997
 998         /* Find the next cleared bit */
 999         next_cleared = sparsebit_next_clear(s, idx);
1000
1001         /*
1002          * If no cleared bits beyond idx, then there are at least num
1003          * set bits. idx + num doesn't wrap.  Otherwise check if
1004          * there are enough set bits between idx and the next cleared bit.
1005          */
1006         return next_cleared == 0 || next_cleared - idx >= num;
1007 }
1008
1009 /* Returns whether the bit at the index given by idx.  */
1010 bool sparsebit_is_clear(struct sparsebit *s,
1011         sparsebit_idx_t idx)
1012 {
1013         return !sparsebit_is_set(s, idx);
1014 }
1015
1016 /* Returns whether num consecutive bits starting at idx are all cleared.  */
1017 bool sparsebit_is_clear_num(struct sparsebit *s,
1018         sparsebit_idx_t idx, sparsebit_num_t num)
1019 {
1020         sparsebit_idx_t next_set;
1021
1022         assert(num > 0);
1023         assert(idx + num - 1 >= idx);
1024
1025         /* With num > 0, the first bit must be cleared. */
1026         if (!sparsebit_is_clear(s, idx))
1027                 return false;
1028
1029         /* Find the next set bit */
1030         next_set = sparsebit_next_set(s, idx);
1031
1032         /*
1033          * If no set bits beyond idx, then there are at least num
1034          * cleared bits. idx + num doesn't wrap.  Otherwise check if
1035          * there are enough cleared bits between idx and the next set bit.
1036          */
1037         return next_set == 0 || next_set - idx >= num;
1038 }
1039
1040 /* Returns the total number of bits set.  Note: 0 is also returned for
1041  * the case of all bits set.  This is because with all bits set, there
1042  * is 1 additional bit set beyond what can be represented in the return
1043  * value.  Use sparsebit_any_set(), instead of sparsebit_num_set() > 0,
1044  * to determine if the sparsebit array has any bits set.
1045  */
1046 sparsebit_num_t sparsebit_num_set(struct sparsebit *s)
1047 {
1048         return s->num_set;
1049 }
1050
1051 /* Returns whether any bit is set in the sparsebit array.  */
1052 bool sparsebit_any_set(struct sparsebit *s)
1053 {
1054         /*
1055          * Nodes only describe set bits.  If any nodes then there
1056          * is at least 1 bit set.
1057          */
1058         if (!s->root)
1059                 return false;
1060
1061         /*
1062          * Every node should have a non-zero mask.  For now will
1063          * just assure that the root node has a non-zero mask,
1064          * which is a quick check that at least 1 bit is set.
1065          */
1066         assert(s->root->mask != 0);
1067         assert(s->num_set > 0 ||
1068                (s->root->num_after == ((sparsebit_num_t) 0) - MASK_BITS &&
1069                 s->root->mask == ~(mask_t) 0));
1070
1071         return true;
1072 }
1073
1074 /* Returns whether all the bits in the sparsebit array are cleared.  */
1075 bool sparsebit_all_clear(struct sparsebit *s)
1076 {
1077         return !sparsebit_any_set(s);
1078 }
1079
1080 /* Returns whether all the bits in the sparsebit array are set.  */
1081 bool sparsebit_any_clear(struct sparsebit *s)
1082 {
1083         return !sparsebit_all_set(s);
1084 }
1085
1086 /* Returns the index of the first set bit.  Abort if no bits are set.
1087  */
1088 sparsebit_idx_t sparsebit_first_set(struct sparsebit *s)
1089 {
1090         struct node *nodep;
1091
1092         /* Validate at least 1 bit is set */
1093         assert(sparsebit_any_set(s));
1094
1095         nodep = node_first(s);
1096         return node_first_set(nodep, 0);
1097 }
1098
1099 /* Returns the index of the first cleared bit.  Abort if
1100  * no bits are cleared.
1101  */
1102 sparsebit_idx_t sparsebit_first_clear(struct sparsebit *s)
1103 {
1104         struct node *nodep1, *nodep2;
1105
1106         /* Validate at least 1 bit is cleared. */
1107         assert(sparsebit_any_clear(s));
1108
1109         /* If no nodes or first node index > 0 then lowest cleared is 0 */
1110         nodep1 = node_first(s);
1111         if (!nodep1 || nodep1->idx > 0)
1112                 return 0;
1113
1114         /* Does the mask in the first node contain any cleared bits. */
1115         if (nodep1->mask != ~(mask_t) 0)
1116                 return node_first_clear(nodep1, 0);
1117
1118         /*
1119          * All mask bits set in first node.  If there isn't a second node
1120          * then the first cleared bit is the first bit after the bits
1121          * described by the first node.
1122          */
1123         nodep2 = node_next(s, nodep1);
1124         if (!nodep2) {
1125                 /*
1126                  * No second node.  First cleared bit is first bit beyond
1127                  * bits described by first node.
1128                  */
1129                 assert(nodep1->mask == ~(mask_t) 0);
1130                 assert(nodep1->idx + MASK_BITS + nodep1->num_after != (sparsebit_idx_t) 0);
1131                 return nodep1->idx + MASK_BITS + nodep1->num_after;
1132         }
1133
1134         /*
1135          * There is a second node.
1136          * If it is not adjacent to the first node, then there is a gap
1137          * of cleared bits between the nodes, and the first cleared bit
1138          * is the first bit within the gap.
1139          */
1140         if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx)
1141                 return nodep1->idx + MASK_BITS + nodep1->num_after;
1142
1143         /*
1144          * Second node is adjacent to the first node.
1145          * Because it is adjacent, its mask should be non-zero.  If all
1146          * its mask bits are set, then with it being adjacent, it should
1147          * have had the mask bits moved into the num_after setting of the
1148          * previous node.
1149          */
1150         return node_first_clear(nodep2, 0);
1151 }
1152
1153 /* Returns index of next bit set within s after the index given by prev.
1154  * Returns 0 if there are no bits after prev that are set.
1155  */
1156 sparsebit_idx_t sparsebit_next_set(struct sparsebit *s,
1157         sparsebit_idx_t prev)
1158 {
1159         sparsebit_idx_t lowest_possible = prev + 1;
1160         sparsebit_idx_t start;
1161         struct node *nodep;
1162
1163         /* A bit after the highest index can't be set. */
1164         if (lowest_possible == 0)
1165                 return 0;
1166
1167         /*
1168          * Find the leftmost 'candidate' overlapping or to the right
1169          * of lowest_possible.
1170          */
1171         struct node *candidate = NULL;
1172
1173         /* True iff lowest_possible is within candidate */
1174         bool contains = false;
1175
1176         /*
1177          * Find node that describes setting of bit at lowest_possible.
1178          * If such a node doesn't exist, find the node with the lowest
1179          * starting index that is > lowest_possible.
1180          */
1181         for (nodep = s->root; nodep;) {
1182                 if ((nodep->idx + MASK_BITS + nodep->num_after - 1)
1183                         >= lowest_possible) {
1184                         candidate = nodep;
1185                         if (candidate->idx <= lowest_possible) {
1186                                 contains = true;
1187                                 break;
1188                         }
1189                         nodep = nodep->left;
1190                 } else {
1191                         nodep = nodep->right;
1192                 }
1193         }
1194         if (!candidate)
1195                 return 0;
1196
1197         assert(candidate->mask != 0);
1198
1199         /* Does the candidate node describe the setting of lowest_possible? */
1200         if (!contains) {
1201                 /*
1202                  * Candidate doesn't describe setting of bit at lowest_possible.
1203                  * Candidate points to the first node with a starting index
1204                  * > lowest_possible.
1205                  */
1206                 assert(candidate->idx > lowest_possible);
1207
1208                 return node_first_set(candidate, 0);
1209         }
1210
1211         /*
1212          * Candidate describes setting of bit at lowest_possible.
1213          * Note: although the node describes the setting of the bit
1214          * at lowest_possible, its possible that its setting and the
1215          * setting of all latter bits described by this node are 0.
1216          * For now, just handle the cases where this node describes
1217          * a bit at or after an index of lowest_possible that is set.
1218          */
1219         start = lowest_possible - candidate->idx;
1220
1221         if (start < MASK_BITS && candidate->mask >= (1 << start))
1222                 return node_first_set(candidate, start);
1223
1224         if (candidate->num_after) {
1225                 sparsebit_idx_t first_num_after_idx = candidate->idx + MASK_BITS;
1226
1227                 return lowest_possible < first_num_after_idx
1228                         ? first_num_after_idx : lowest_possible;
1229         }
1230
1231         /*
1232          * Although candidate node describes setting of bit at
1233          * the index of lowest_possible, all bits at that index and
1234          * latter that are described by candidate are cleared.  With
1235          * this, the next bit is the first bit in the next node, if
1236          * such a node exists.  If a next node doesn't exist, then
1237          * there is no next set bit.
1238          */
1239         candidate = node_next(s, candidate);
1240         if (!candidate)
1241                 return 0;
1242
1243         return node_first_set(candidate, 0);
1244 }
1245
1246 /* Returns index of next bit cleared within s after the index given by prev.
1247  * Returns 0 if there are no bits after prev that are cleared.
1248  */
1249 sparsebit_idx_t sparsebit_next_clear(struct sparsebit *s,
1250         sparsebit_idx_t prev)
1251 {
1252         sparsebit_idx_t lowest_possible = prev + 1;
1253         sparsebit_idx_t idx;
1254         struct node *nodep1, *nodep2;
1255
1256         /* A bit after the highest index can't be set. */
1257         if (lowest_possible == 0)
1258                 return 0;
1259
1260         /*
1261          * Does a node describing the setting of lowest_possible exist?
1262          * If not, the bit at lowest_possible is cleared.
1263          */
1264         nodep1 = node_find(s, lowest_possible);
1265         if (!nodep1)
1266                 return lowest_possible;
1267
1268         /* Does a mask bit in node 1 describe the next cleared bit. */
1269         for (idx = lowest_possible - nodep1->idx; idx < MASK_BITS; idx++)
1270                 if (!(nodep1->mask & (1 << idx)))
1271                         return nodep1->idx + idx;
1272
1273         /*
1274          * Next cleared bit is not described by node 1.  If there
1275          * isn't a next node, then next cleared bit is described
1276          * by bit after the bits described by the first node.
1277          */
1278         nodep2 = node_next(s, nodep1);
1279         if (!nodep2)
1280                 return nodep1->idx + MASK_BITS + nodep1->num_after;
1281
1282         /*
1283          * There is a second node.
1284          * If it is not adjacent to the first node, then there is a gap
1285          * of cleared bits between the nodes, and the next cleared bit
1286          * is the first bit within the gap.
1287          */
1288         if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx)
1289                 return nodep1->idx + MASK_BITS + nodep1->num_after;
1290
1291         /*
1292          * Second node is adjacent to the first node.
1293          * Because it is adjacent, its mask should be non-zero.  If all
1294          * its mask bits are set, then with it being adjacent, it should
1295          * have had the mask bits moved into the num_after setting of the
1296          * previous node.
1297          */
1298         return node_first_clear(nodep2, 0);
1299 }
1300
1301 /* Starting with the index 1 greater than the index given by start, finds
1302  * and returns the index of the first sequence of num consecutively set
1303  * bits.  Returns a value of 0 of no such sequence exists.
1304  */
1305 sparsebit_idx_t sparsebit_next_set_num(struct sparsebit *s,
1306         sparsebit_idx_t start, sparsebit_num_t num)
1307 {
1308         sparsebit_idx_t idx;
1309
1310         assert(num >= 1);
1311
1312         for (idx = sparsebit_next_set(s, start);
1313                 idx != 0 && idx + num - 1 >= idx;
1314                 idx = sparsebit_next_set(s, idx)) {
1315                 assert(sparsebit_is_set(s, idx));
1316
1317                 /*
1318                  * Does the sequence of bits starting at idx consist of
1319                  * num set bits?
1320                  */
1321                 if (sparsebit_is_set_num(s, idx, num))
1322                         return idx;
1323
1324                 /*
1325                  * Sequence of set bits at idx isn't large enough.
1326                  * Skip this entire sequence of set bits.
1327                  */
1328                 idx = sparsebit_next_clear(s, idx);
1329                 if (idx == 0)
1330                         return 0;
1331         }
1332
1333         return 0;
1334 }
1335
1336 /* Starting with the index 1 greater than the index given by start, finds
1337  * and returns the index of the first sequence of num consecutively cleared
1338  * bits.  Returns a value of 0 of no such sequence exists.
1339  */
1340 sparsebit_idx_t sparsebit_next_clear_num(struct sparsebit *s,
1341         sparsebit_idx_t start, sparsebit_num_t num)
1342 {
1343         sparsebit_idx_t idx;
1344
1345         assert(num >= 1);
1346
1347         for (idx = sparsebit_next_clear(s, start);
1348                 idx != 0 && idx + num - 1 >= idx;
1349                 idx = sparsebit_next_clear(s, idx)) {
1350                 assert(sparsebit_is_clear(s, idx));
1351
1352                 /*
1353                  * Does the sequence of bits starting at idx consist of
1354                  * num cleared bits?
1355                  */
1356                 if (sparsebit_is_clear_num(s, idx, num))
1357                         return idx;
1358
1359                 /*
1360                  * Sequence of cleared bits at idx isn't large enough.
1361                  * Skip this entire sequence of cleared bits.
1362                  */
1363                 idx = sparsebit_next_set(s, idx);
1364                 if (idx == 0)
1365                         return 0;
1366         }
1367
1368         return 0;
1369 }
1370
1371 /* Sets the bits * in the inclusive range idx through idx + num - 1.  */
1372 void sparsebit_set_num(struct sparsebit *s,
1373         sparsebit_idx_t start, sparsebit_num_t num)
1374 {
1375         struct node *nodep, *next;
1376         unsigned int n1;
1377         sparsebit_idx_t idx;
1378         sparsebit_num_t n;
1379         sparsebit_idx_t middle_start, middle_end;
1380
1381         assert(num > 0);
1382         assert(start + num - 1 >= start);
1383
1384         /*
1385          * Leading - bits before first mask boundary.
1386          *
1387          * TODO(lhuemill): With some effort it may be possible to
1388          *   replace the following loop with a sequential sequence
1389          *   of statements.  High level sequence would be:
1390          *
1391          *     1. Use node_split() to force node that describes setting
1392          *        of idx to be within the mask portion of a node.
1393          *     2. Form mask of bits to be set.
1394          *     3. Determine number of mask bits already set in the node
1395          *        and store in a local variable named num_already_set.
1396          *     4. Set the appropriate mask bits within the node.
1397          *     5. Increment struct sparsebit_pvt num_set member
1398          *        by the number of bits that were actually set.
1399          *        Exclude from the counts bits that were already set.
1400          *     6. Before returning to the caller, use node_reduce() to
1401          *        handle the multiple corner cases that this method
1402          *        introduces.
1403          */
1404         for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--)
1405                 bit_set(s, idx);
1406
1407         /* Middle - bits spanning one or more entire mask */
1408         middle_start = idx;
1409         middle_end = middle_start + (n & -MASK_BITS) - 1;
1410         if (n >= MASK_BITS) {
1411                 nodep = node_split(s, middle_start);
1412
1413                 /*
1414                  * As needed, split just after end of middle bits.
1415                  * No split needed if end of middle bits is at highest
1416                  * supported bit index.
1417                  */
1418                 if (middle_end + 1 > middle_end)
1419                         (void) node_split(s, middle_end + 1);
1420
1421                 /* Delete nodes that only describe bits within the middle. */
1422                 for (next = node_next(s, nodep);
1423                         next && (next->idx < middle_end);
1424                         next = node_next(s, nodep)) {
1425                         assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end);
1426                         node_rm(s, next);
1427                         next = NULL;
1428                 }
1429
1430                 /* As needed set each of the mask bits */
1431                 for (n1 = 0; n1 < MASK_BITS; n1++) {
1432                         if (!(nodep->mask & (1 << n1))) {
1433                                 nodep->mask |= 1 << n1;
1434                                 s->num_set++;
1435                         }
1436                 }
1437
1438                 s->num_set -= nodep->num_after;
1439                 nodep->num_after = middle_end - middle_start + 1 - MASK_BITS;
1440                 s->num_set += nodep->num_after;
1441
1442                 node_reduce(s, nodep);
1443         }
1444         idx = middle_end + 1;
1445         n -= middle_end - middle_start + 1;
1446
1447         /* Trailing - bits at and beyond last mask boundary */
1448         assert(n < MASK_BITS);
1449         for (; n > 0; idx++, n--)
1450                 bit_set(s, idx);
1451 }
1452
1453 /* Clears the bits * in the inclusive range idx through idx + num - 1.  */
1454 void sparsebit_clear_num(struct sparsebit *s,
1455         sparsebit_idx_t start, sparsebit_num_t num)
1456 {
1457         struct node *nodep, *next;
1458         unsigned int n1;
1459         sparsebit_idx_t idx;
1460         sparsebit_num_t n;
1461         sparsebit_idx_t middle_start, middle_end;
1462
1463         assert(num > 0);
1464         assert(start + num - 1 >= start);
1465
1466         /* Leading - bits before first mask boundary */
1467         for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--)
1468                 bit_clear(s, idx);
1469
1470         /* Middle - bits spanning one or more entire mask */
1471         middle_start = idx;
1472         middle_end = middle_start + (n & -MASK_BITS) - 1;
1473         if (n >= MASK_BITS) {
1474                 nodep = node_split(s, middle_start);
1475
1476                 /*
1477                  * As needed, split just after end of middle bits.
1478                  * No split needed if end of middle bits is at highest
1479                  * supported bit index.
1480                  */
1481                 if (middle_end + 1 > middle_end)
1482                         (void) node_split(s, middle_end + 1);
1483
1484                 /* Delete nodes that only describe bits within the middle. */
1485                 for (next = node_next(s, nodep);
1486                         next && (next->idx < middle_end);
1487                         next = node_next(s, nodep)) {
1488                         assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end);
1489                         node_rm(s, next);
1490                         next = NULL;
1491                 }
1492
1493                 /* As needed clear each of the mask bits */
1494                 for (n1 = 0; n1 < MASK_BITS; n1++) {
1495                         if (nodep->mask & (1 << n1)) {
1496                                 nodep->mask &= ~(1 << n1);
1497                                 s->num_set--;
1498                         }
1499                 }
1500
1501                 /* Clear any bits described by num_after */
1502                 s->num_set -= nodep->num_after;
1503                 nodep->num_after = 0;
1504
1505                 /*
1506                  * Delete the node that describes the beginning of
1507                  * the middle bits and perform any allowed reductions
1508                  * with the nodes prev or next of nodep.
1509                  */
1510                 node_reduce(s, nodep);
1511                 nodep = NULL;
1512         }
1513         idx = middle_end + 1;
1514         n -= middle_end - middle_start + 1;
1515
1516         /* Trailing - bits at and beyond last mask boundary */
1517         assert(n < MASK_BITS);
1518         for (; n > 0; idx++, n--)
1519                 bit_clear(s, idx);
1520 }
1521
1522 /* Sets the bit at the index given by idx.  */
1523 void sparsebit_set(struct sparsebit *s, sparsebit_idx_t idx)
1524 {
1525         sparsebit_set_num(s, idx, 1);
1526 }
1527
1528 /* Clears the bit at the index given by idx.  */
1529 void sparsebit_clear(struct sparsebit *s, sparsebit_idx_t idx)
1530 {
1531         sparsebit_clear_num(s, idx, 1);
1532 }
1533
1534 /* Sets the bits in the entire addressable range of the sparsebit array.  */
1535 void sparsebit_set_all(struct sparsebit *s)
1536 {
1537         sparsebit_set(s, 0);
1538         sparsebit_set_num(s, 1, ~(sparsebit_idx_t) 0);
1539         assert(sparsebit_all_set(s));
1540 }
1541
1542 /* Clears the bits in the entire addressable range of the sparsebit array.  */
1543 void sparsebit_clear_all(struct sparsebit *s)
1544 {
1545         sparsebit_clear(s, 0);
1546         sparsebit_clear_num(s, 1, ~(sparsebit_idx_t) 0);
1547         assert(!sparsebit_any_set(s));
1548 }
1549
1550 static size_t display_range(FILE *stream, sparsebit_idx_t low,
1551         sparsebit_idx_t high, bool prepend_comma_space)
1552 {
1553         char *fmt_str;
1554         size_t sz;
1555
1556         /* Determine the printf format string */
1557         if (low == high)
1558                 fmt_str = prepend_comma_space ? ", 0x%lx" : "0x%lx";
1559         else
1560                 fmt_str = prepend_comma_space ? ", 0x%lx:0x%lx" : "0x%lx:0x%lx";
1561
1562         /*
1563          * When stream is NULL, just determine the size of what would
1564          * have been printed, else print the range.
1565          */
1566         if (!stream)
1567                 sz = snprintf(NULL, 0, fmt_str, low, high);
1568         else
1569                 sz = fprintf(stream, fmt_str, low, high);
1570
1571         return sz;
1572 }
1573
1574
1575 /* Dumps to the FILE stream given by stream, the bit settings
1576  * of s.  Each line of output is prefixed with the number of
1577  * spaces given by indent.  The length of each line is implementation
1578  * dependent and does not depend on the indent amount.  The following
1579  * is an example output of a sparsebit array that has bits:
1580  *
1581  *   0x5, 0x8, 0xa:0xe, 0x12
1582  *
1583  * This corresponds to a sparsebit whose bits 5, 8, 10, 11, 12, 13, 14, 18
1584  * are set.  Note that a ':', instead of a '-' is used to specify a range of
1585  * contiguous bits.  This is done because '-' is used to specify command-line
1586  * options, and sometimes ranges are specified as command-line arguments.
1587  */
1588 void sparsebit_dump(FILE *stream, struct sparsebit *s,
1589         unsigned int indent)
1590 {
1591         size_t current_line_len = 0;
1592         size_t sz;
1593         struct node *nodep;
1594
1595         if (!sparsebit_any_set(s))
1596                 return;
1597
1598         /* Display initial indent */
1599         fprintf(stream, "%*s", indent, "");
1600
1601         /* For each node */
1602         for (nodep = node_first(s); nodep; nodep = node_next(s, nodep)) {
1603                 unsigned int n1;
1604                 sparsebit_idx_t low, high;
1605
1606                 /* For each group of bits in the mask */
1607                 for (n1 = 0; n1 < MASK_BITS; n1++) {
1608                         if (nodep->mask & (1 << n1)) {
1609                                 low = high = nodep->idx + n1;
1610
1611                                 for (; n1 < MASK_BITS; n1++) {
1612                                         if (nodep->mask & (1 << n1))
1613                                                 high = nodep->idx + n1;
1614                                         else
1615                                                 break;
1616                                 }
1617
1618                                 if ((n1 == MASK_BITS) && nodep->num_after)
1619                                         high += nodep->num_after;
1620
1621                                 /*
1622                                  * How much room will it take to display
1623                                  * this range.
1624                                  */
1625                                 sz = display_range(NULL, low, high,
1626                                         current_line_len != 0);
1627
1628                                 /*
1629                                  * If there is not enough room, display
1630                                  * a newline plus the indent of the next
1631                                  * line.
1632                                  */
1633                                 if (current_line_len + sz > DUMP_LINE_MAX) {
1634                                         fputs("\n", stream);
1635                                         fprintf(stream, "%*s", indent, "");
1636                                         current_line_len = 0;
1637                                 }
1638
1639                                 /* Display the range */
1640                                 sz = display_range(stream, low, high,
1641                                         current_line_len != 0);
1642                                 current_line_len += sz;
1643                         }
1644                 }
1645
1646                 /*
1647                  * If num_after and most significant-bit of mask is not
1648                  * set, then still need to display a range for the bits
1649                  * described by num_after.
1650                  */
1651                 if (!(nodep->mask & (1 << (MASK_BITS - 1))) && nodep->num_after) {
1652                         low = nodep->idx + MASK_BITS;
1653                         high = nodep->idx + MASK_BITS + nodep->num_after - 1;
1654
1655                         /*
1656                          * How much room will it take to display
1657                          * this range.
1658                          */
1659                         sz = display_range(NULL, low, high,
1660                                 current_line_len != 0);
1661
1662                         /*
1663                          * If there is not enough room, display
1664                          * a newline plus the indent of the next
1665                          * line.
1666                          */
1667                         if (current_line_len + sz > DUMP_LINE_MAX) {
1668                                 fputs("\n", stream);
1669                                 fprintf(stream, "%*s", indent, "");
1670                                 current_line_len = 0;
1671                         }
1672
1673                         /* Display the range */
1674                         sz = display_range(stream, low, high,
1675                                 current_line_len != 0);
1676                         current_line_len += sz;
1677                 }
1678         }
1679         fputs("\n", stream);
1680 }
1681
1682 /* Validates the internal state of the sparsebit array given by
1683  * s.  On error, diagnostic information is printed to stderr and
1684  * abort is called.
1685  */
1686 void sparsebit_validate_internal(struct sparsebit *s)
1687 {
1688         bool error_detected = false;
1689         struct node *nodep, *prev = NULL;
1690         sparsebit_num_t total_bits_set = 0;
1691         unsigned int n1;
1692
1693         /* For each node */
1694         for (nodep = node_first(s); nodep;
1695                 prev = nodep, nodep = node_next(s, nodep)) {
1696
1697                 /*
1698                  * Increase total bits set by the number of bits set
1699                  * in this node.
1700                  */
1701                 for (n1 = 0; n1 < MASK_BITS; n1++)
1702                         if (nodep->mask & (1 << n1))
1703                                 total_bits_set++;
1704
1705                 total_bits_set += nodep->num_after;
1706
1707                 /*
1708                  * Arbitrary choice as to whether a mask of 0 is allowed
1709                  * or not.  For diagnostic purposes it is beneficial to
1710                  * have only one valid means to represent a set of bits.
1711                  * To support this an arbitrary choice has been made
1712                  * to not allow a mask of zero.
1713                  */
1714                 if (nodep->mask == 0) {
1715                         fprintf(stderr, "Node mask of zero, "
1716                                 "nodep: %p nodep->mask: 0x%x",
1717                                 nodep, nodep->mask);
1718                         error_detected = true;
1719                         break;
1720                 }
1721
1722                 /*
1723                  * Validate num_after is not greater than the max index
1724                  * - the number of mask bits.  The num_after member
1725                  * uses 0-based indexing and thus has no value that
1726                  * represents all bits set.  This limitation is handled
1727                  * by requiring a non-zero mask.  With a non-zero mask,
1728                  * MASK_BITS worth of bits are described by the mask,
1729                  * which makes the largest needed num_after equal to:
1730                  *
1731                  *    (~(sparsebit_num_t) 0) - MASK_BITS + 1
1732                  */
1733                 if (nodep->num_after
1734                         > (~(sparsebit_num_t) 0) - MASK_BITS + 1) {
1735                         fprintf(stderr, "num_after too large, "
1736                                 "nodep: %p nodep->num_after: 0x%lx",
1737                                 nodep, nodep->num_after);
1738                         error_detected = true;
1739                         break;
1740                 }
1741
1742                 /* Validate node index is divisible by the mask size */
1743                 if (nodep->idx % MASK_BITS) {
1744                         fprintf(stderr, "Node index not divisable by "
1745                                 "mask size,\n"
1746                                 "  nodep: %p nodep->idx: 0x%lx "
1747                                 "MASK_BITS: %lu\n",
1748                                 nodep, nodep->idx, MASK_BITS);
1749                         error_detected = true;
1750                         break;
1751                 }
1752
1753                 /*
1754                  * Validate bits described by node don't wrap beyond the
1755                  * highest supported index.
1756                  */
1757                 if ((nodep->idx + MASK_BITS + nodep->num_after - 1) < nodep->idx) {
1758                         fprintf(stderr, "Bits described by node wrap "
1759                                 "beyond highest supported index,\n"
1760                                 "  nodep: %p nodep->idx: 0x%lx\n"
1761                                 "  MASK_BITS: %lu nodep->num_after: 0x%lx",
1762                                 nodep, nodep->idx, MASK_BITS, nodep->num_after);
1763                         error_detected = true;
1764                         break;
1765                 }
1766
1767                 /* Check parent pointers. */
1768                 if (nodep->left) {
1769                         if (nodep->left->parent != nodep) {
1770                                 fprintf(stderr, "Left child parent pointer "
1771                                         "doesn't point to this node,\n"
1772                                         "  nodep: %p nodep->left: %p "
1773                                         "nodep->left->parent: %p",
1774                                         nodep, nodep->left,
1775                                         nodep->left->parent);
1776                                 error_detected = true;
1777                                 break;
1778                         }
1779                 }
1780
1781                 if (nodep->right) {
1782                         if (nodep->right->parent != nodep) {
1783                                 fprintf(stderr, "Right child parent pointer "
1784                                         "doesn't point to this node,\n"
1785                                         "  nodep: %p nodep->right: %p "
1786                                         "nodep->right->parent: %p",
1787                                         nodep, nodep->right,
1788                                         nodep->right->parent);
1789                                 error_detected = true;
1790                                 break;
1791                         }
1792                 }
1793
1794                 if (!nodep->parent) {
1795                         if (s->root != nodep) {
1796                                 fprintf(stderr, "Unexpected root node, "
1797                                         "s->root: %p nodep: %p",
1798                                         s->root, nodep);
1799                                 error_detected = true;
1800                                 break;
1801                         }
1802                 }
1803
1804                 if (prev) {
1805                         /*
1806                          * Is index of previous node before index of
1807                          * current node?
1808                          */
1809                         if (prev->idx >= nodep->idx) {
1810                                 fprintf(stderr, "Previous node index "
1811                                         ">= current node index,\n"
1812                                         "  prev: %p prev->idx: 0x%lx\n"
1813                                         "  nodep: %p nodep->idx: 0x%lx",
1814                                         prev, prev->idx, nodep, nodep->idx);
1815                                 error_detected = true;
1816                                 break;
1817                         }
1818
1819                         /*
1820                          * Nodes occur in asscending order, based on each
1821                          * nodes starting index.
1822                          */
1823                         if ((prev->idx + MASK_BITS + prev->num_after - 1)
1824                                 >= nodep->idx) {
1825                                 fprintf(stderr, "Previous node bit range "
1826                                         "overlap with current node bit range,\n"
1827                                         "  prev: %p prev->idx: 0x%lx "
1828                                         "prev->num_after: 0x%lx\n"
1829                                         "  nodep: %p nodep->idx: 0x%lx "
1830                                         "nodep->num_after: 0x%lx\n"
1831                                         "  MASK_BITS: %lu",
1832                                         prev, prev->idx, prev->num_after,
1833                                         nodep, nodep->idx, nodep->num_after,
1834                                         MASK_BITS);
1835                                 error_detected = true;
1836                                 break;
1837                         }
1838
1839                         /*
1840                          * When the node has all mask bits set, it shouldn't
1841                          * be adjacent to the last bit described by the
1842                          * previous node.
1843                          */
1844                         if (nodep->mask == ~(mask_t) 0 &&
1845                             prev->idx + MASK_BITS + prev->num_after == nodep->idx) {
1846                                 fprintf(stderr, "Current node has mask with "
1847                                         "all bits set and is adjacent to the "
1848                                         "previous node,\n"
1849                                         "  prev: %p prev->idx: 0x%lx "
1850                                         "prev->num_after: 0x%lx\n"
1851                                         "  nodep: %p nodep->idx: 0x%lx "
1852                                         "nodep->num_after: 0x%lx\n"
1853                                         "  MASK_BITS: %lu",
1854                                         prev, prev->idx, prev->num_after,
1855                                         nodep, nodep->idx, nodep->num_after,
1856                                         MASK_BITS);
1857
1858                                 error_detected = true;
1859                                 break;
1860                         }
1861                 }
1862         }
1863
1864         if (!error_detected) {
1865                 /*
1866                  * Is sum of bits set in each node equal to the count
1867                  * of total bits set.
1868                  */
1869                 if (s->num_set != total_bits_set) {
1870                         fprintf(stderr, "Number of bits set missmatch,\n"
1871                                 "  s->num_set: 0x%lx total_bits_set: 0x%lx",
1872                                 s->num_set, total_bits_set);
1873
1874                         error_detected = true;
1875                 }
1876         }
1877
1878         if (error_detected) {
1879                 fputs("  dump_internal:\n", stderr);
1880                 sparsebit_dump_internal(stderr, s, 4);
1881                 abort();
1882         }
1883 }
1884
1885
1886 #ifdef FUZZ
1887 /* A simple but effective fuzzing driver.  Look for bugs with the help
1888  * of some invariants and of a trivial representation of sparsebit.
1889  * Just use 512 bytes of /dev/zero and /dev/urandom as inputs, and let
1890  * afl-fuzz do the magic. :)
1891  */
1892
1893 #include <stdlib.h>
1894 #include <assert.h>
1895
1896 struct range {
1897         sparsebit_idx_t first, last;
1898         bool set;
1899 };
1900
1901 struct sparsebit *s;
1902 struct range ranges[1000];
1903 int num_ranges;
1904
1905 static bool get_value(sparsebit_idx_t idx)
1906 {
1907         int i;
1908
1909         for (i = num_ranges; --i >= 0; )
1910                 if (ranges[i].first <= idx && idx <= ranges[i].last)
1911                         return ranges[i].set;
1912
1913         return false;
1914 }
1915
1916 static void operate(int code, sparsebit_idx_t first, sparsebit_idx_t last)
1917 {
1918         sparsebit_num_t num;
1919         sparsebit_idx_t next;
1920
1921         if (first < last) {
1922                 num = last - first + 1;
1923         } else {
1924                 num = first - last + 1;
1925                 first = last;
1926                 last = first + num - 1;
1927         }
1928
1929         switch (code) {
1930         case 0:
1931                 sparsebit_set(s, first);
1932                 assert(sparsebit_is_set(s, first));
1933                 assert(!sparsebit_is_clear(s, first));
1934                 assert(sparsebit_any_set(s));
1935                 assert(!sparsebit_all_clear(s));
1936                 if (get_value(first))
1937                         return;
1938                 if (num_ranges == 1000)
1939                         exit(0);
1940                 ranges[num_ranges++] = (struct range)
1941                         { .first = first, .last = first, .set = true };
1942                 break;
1943         case 1:
1944                 sparsebit_clear(s, first);
1945                 assert(!sparsebit_is_set(s, first));
1946                 assert(sparsebit_is_clear(s, first));
1947                 assert(sparsebit_any_clear(s));
1948                 assert(!sparsebit_all_set(s));
1949                 if (!get_value(first))
1950                         return;
1951                 if (num_ranges == 1000)
1952                         exit(0);
1953                 ranges[num_ranges++] = (struct range)
1954                         { .first = first, .last = first, .set = false };
1955                 break;
1956         case 2:
1957                 assert(sparsebit_is_set(s, first) == get_value(first));
1958                 assert(sparsebit_is_clear(s, first) == !get_value(first));
1959                 break;
1960         case 3:
1961                 if (sparsebit_any_set(s))
1962                         assert(get_value(sparsebit_first_set(s)));
1963                 if (sparsebit_any_clear(s))
1964                         assert(!get_value(sparsebit_first_clear(s)));
1965                 sparsebit_set_all(s);
1966                 assert(!sparsebit_any_clear(s));
1967                 assert(sparsebit_all_set(s));
1968                 num_ranges = 0;
1969                 ranges[num_ranges++] = (struct range)
1970                         { .first = 0, .last = ~(sparsebit_idx_t)0, .set = true };
1971                 break;
1972         case 4:
1973                 if (sparsebit_any_set(s))
1974                         assert(get_value(sparsebit_first_set(s)));
1975                 if (sparsebit_any_clear(s))
1976                         assert(!get_value(sparsebit_first_clear(s)));
1977                 sparsebit_clear_all(s);
1978                 assert(!sparsebit_any_set(s));
1979                 assert(sparsebit_all_clear(s));
1980                 num_ranges = 0;
1981                 break;
1982         case 5:
1983                 next = sparsebit_next_set(s, first);
1984                 assert(next == 0 || next > first);
1985                 assert(next == 0 || get_value(next));
1986                 break;
1987         case 6:
1988                 next = sparsebit_next_clear(s, first);
1989                 assert(next == 0 || next > first);
1990                 assert(next == 0 || !get_value(next));
1991                 break;
1992         case 7:
1993                 next = sparsebit_next_clear(s, first);
1994                 if (sparsebit_is_set_num(s, first, num)) {
1995                         assert(next == 0 || next > last);
1996                         if (first)
1997                                 next = sparsebit_next_set(s, first - 1);
1998                         else if (sparsebit_any_set(s))
1999                                 next = sparsebit_first_set(s);
2000                         else
2001                                 return;
2002                         assert(next == first);
2003                 } else {
2004                         assert(sparsebit_is_clear(s, first) || next <= last);
2005                 }
2006                 break;
2007         case 8:
2008                 next = sparsebit_next_set(s, first);
2009                 if (sparsebit_is_clear_num(s, first, num)) {
2010                         assert(next == 0 || next > last);
2011                         if (first)
2012                                 next = sparsebit_next_clear(s, first - 1);
2013                         else if (sparsebit_any_clear(s))
2014                                 next = sparsebit_first_clear(s);
2015                         else
2016                                 return;
2017                         assert(next == first);
2018                 } else {
2019                         assert(sparsebit_is_set(s, first) || next <= last);
2020                 }
2021                 break;
2022         case 9:
2023                 sparsebit_set_num(s, first, num);
2024                 assert(sparsebit_is_set_num(s, first, num));
2025                 assert(!sparsebit_is_clear_num(s, first, num));
2026                 assert(sparsebit_any_set(s));
2027                 assert(!sparsebit_all_clear(s));
2028                 if (num_ranges == 1000)
2029                         exit(0);
2030                 ranges[num_ranges++] = (struct range)
2031                         { .first = first, .last = last, .set = true };
2032                 break;
2033         case 10:
2034                 sparsebit_clear_num(s, first, num);
2035                 assert(!sparsebit_is_set_num(s, first, num));
2036                 assert(sparsebit_is_clear_num(s, first, num));
2037                 assert(sparsebit_any_clear(s));
2038                 assert(!sparsebit_all_set(s));
2039                 if (num_ranges == 1000)
2040                         exit(0);
2041                 ranges[num_ranges++] = (struct range)
2042                         { .first = first, .last = last, .set = false };
2043                 break;
2044         case 11:
2045                 sparsebit_validate_internal(s);
2046                 break;
2047         default:
2048                 break;
2049         }
2050 }
2051
2052 unsigned char get8(void)
2053 {
2054         int ch;
2055
2056         ch = getchar();
2057         if (ch == EOF)
2058                 exit(0);
2059         return ch;
2060 }
2061
2062 uint64_t get64(void)
2063 {
2064         uint64_t x;
2065
2066         x = get8();
2067         x = (x << 8) | get8();
2068         x = (x << 8) | get8();
2069         x = (x << 8) | get8();
2070         x = (x << 8) | get8();
2071         x = (x << 8) | get8();
2072         x = (x << 8) | get8();
2073         return (x << 8) | get8();
2074 }
2075
2076 int main(void)
2077 {
2078         s = sparsebit_alloc();
2079         for (;;) {
2080                 uint8_t op = get8() & 0xf;
2081                 uint64_t first = get64();
2082                 uint64_t last = get64();
2083
2084                 operate(op, first, last);
2085         }
2086 }
2087 #endif