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

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