linux/tools/testing/selftests/kvm/lib/sparsebit.c
<<
>>
Prefs
   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
 165typedef uint32_t mask_t;
 166#define MASK_BITS (sizeof(mask_t) * CHAR_BIT)
 167
 168struct 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
 177struct 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 */
 197static 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 */
 205static 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 */
 219static 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 */
 247static 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 */
 276static 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 */
 310static 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 */
 333static 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.  */
 396bool 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 */
 409static 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 */
 498static 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 */
 599static 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 */
 779bool 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
 792have_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 */
 805static 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 */
 832static 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 */
 872static 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
 901static 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
 909static 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 */
 925static 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 */
 939struct 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 */
 956void 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 */
 973void 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.  */
 985bool 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.  */
1009bool 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.  */
1016bool 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 */
1045sparsebit_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.  */
1051bool 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.  */
1074bool 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.  */
1080bool 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 */
1087sparsebit_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 */
1101sparsebit_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 */
1155sparsebit_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 */
1248sparsebit_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 */
1304sparsebit_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 */
1339sparsebit_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.  */
1371void 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.  */
1453void 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.  */
1522void 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.  */
1528void 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.  */
1534void 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.  */
1542void 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
1549static 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 */
1587void 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 */
1685void 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#include <assert.h>
1894
1895struct range {
1896        sparsebit_idx_t first, last;
1897        bool set;
1898};
1899
1900struct sparsebit *s;
1901struct range ranges[1000];
1902int num_ranges;
1903
1904static bool get_value(sparsebit_idx_t idx)
1905{
1906        int i;
1907
1908        for (i = num_ranges; --i >= 0; )
1909                if (ranges[i].first <= idx && idx <= ranges[i].last)
1910                        return ranges[i].set;
1911
1912        return false;
1913}
1914
1915static void operate(int code, sparsebit_idx_t first, sparsebit_idx_t last)
1916{
1917        sparsebit_num_t num;
1918        sparsebit_idx_t next;
1919
1920        if (first < last) {
1921                num = last - first + 1;
1922        } else {
1923                num = first - last + 1;
1924                first = last;
1925                last = first + num - 1;
1926        }
1927
1928        switch (code) {
1929        case 0:
1930                sparsebit_set(s, first);
1931                assert(sparsebit_is_set(s, first));
1932                assert(!sparsebit_is_clear(s, first));
1933                assert(sparsebit_any_set(s));
1934                assert(!sparsebit_all_clear(s));
1935                if (get_value(first))
1936                        return;
1937                if (num_ranges == 1000)
1938                        exit(0);
1939                ranges[num_ranges++] = (struct range)
1940                        { .first = first, .last = first, .set = true };
1941                break;
1942        case 1:
1943                sparsebit_clear(s, first);
1944                assert(!sparsebit_is_set(s, first));
1945                assert(sparsebit_is_clear(s, first));
1946                assert(sparsebit_any_clear(s));
1947                assert(!sparsebit_all_set(s));
1948                if (!get_value(first))
1949                        return;
1950                if (num_ranges == 1000)
1951                        exit(0);
1952                ranges[num_ranges++] = (struct range)
1953                        { .first = first, .last = first, .set = false };
1954                break;
1955        case 2:
1956                assert(sparsebit_is_set(s, first) == get_value(first));
1957                assert(sparsebit_is_clear(s, first) == !get_value(first));
1958                break;
1959        case 3:
1960                if (sparsebit_any_set(s))
1961                        assert(get_value(sparsebit_first_set(s)));
1962                if (sparsebit_any_clear(s))
1963                        assert(!get_value(sparsebit_first_clear(s)));
1964                sparsebit_set_all(s);
1965                assert(!sparsebit_any_clear(s));
1966                assert(sparsebit_all_set(s));
1967                num_ranges = 0;
1968                ranges[num_ranges++] = (struct range)
1969                        { .first = 0, .last = ~(sparsebit_idx_t)0, .set = true };
1970                break;
1971        case 4:
1972                if (sparsebit_any_set(s))
1973                        assert(get_value(sparsebit_first_set(s)));
1974                if (sparsebit_any_clear(s))
1975                        assert(!get_value(sparsebit_first_clear(s)));
1976                sparsebit_clear_all(s);
1977                assert(!sparsebit_any_set(s));
1978                assert(sparsebit_all_clear(s));
1979                num_ranges = 0;
1980                break;
1981        case 5:
1982                next = sparsebit_next_set(s, first);
1983                assert(next == 0 || next > first);
1984                assert(next == 0 || get_value(next));
1985                break;
1986        case 6:
1987                next = sparsebit_next_clear(s, first);
1988                assert(next == 0 || next > first);
1989                assert(next == 0 || !get_value(next));
1990                break;
1991        case 7:
1992                next = sparsebit_next_clear(s, first);
1993                if (sparsebit_is_set_num(s, first, num)) {
1994                        assert(next == 0 || next > last);
1995                        if (first)
1996                                next = sparsebit_next_set(s, first - 1);
1997                        else if (sparsebit_any_set(s))
1998                                next = sparsebit_first_set(s);
1999                        else
2000                                return;
2001                        assert(next == first);
2002                } else {
2003                        assert(sparsebit_is_clear(s, first) || next <= last);
2004                }
2005                break;
2006        case 8:
2007                next = sparsebit_next_set(s, first);
2008                if (sparsebit_is_clear_num(s, first, num)) {
2009                        assert(next == 0 || next > last);
2010                        if (first)
2011                                next = sparsebit_next_clear(s, first - 1);
2012                        else if (sparsebit_any_clear(s))
2013                                next = sparsebit_first_clear(s);
2014                        else
2015                                return;
2016                        assert(next == first);
2017                } else {
2018                        assert(sparsebit_is_set(s, first) || next <= last);
2019                }
2020                break;
2021        case 9:
2022                sparsebit_set_num(s, first, num);
2023                assert(sparsebit_is_set_num(s, first, num));
2024                assert(!sparsebit_is_clear_num(s, first, num));
2025                assert(sparsebit_any_set(s));
2026                assert(!sparsebit_all_clear(s));
2027                if (num_ranges == 1000)
2028                        exit(0);
2029                ranges[num_ranges++] = (struct range)
2030                        { .first = first, .last = last, .set = true };
2031                break;
2032        case 10:
2033                sparsebit_clear_num(s, first, num);
2034                assert(!sparsebit_is_set_num(s, first, num));
2035                assert(sparsebit_is_clear_num(s, first, num));
2036                assert(sparsebit_any_clear(s));
2037                assert(!sparsebit_all_set(s));
2038                if (num_ranges == 1000)
2039                        exit(0);
2040                ranges[num_ranges++] = (struct range)
2041                        { .first = first, .last = last, .set = false };
2042                break;
2043        case 11:
2044                sparsebit_validate_internal(s);
2045                break;
2046        default:
2047                break;
2048        }
2049}
2050
2051unsigned char get8(void)
2052{
2053        int ch;
2054
2055        ch = getchar();
2056        if (ch == EOF)
2057                exit(0);
2058        return ch;
2059}
2060
2061uint64_t get64(void)
2062{
2063        uint64_t x;
2064
2065        x = 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        x = (x << 8) | get8();
2072        return (x << 8) | get8();
2073}
2074
2075int main(void)
2076{
2077        s = sparsebit_alloc();
2078        for (;;) {
2079                uint8_t op = get8() & 0xf;
2080                uint64_t first = get64();
2081                uint64_t last = get64();
2082
2083                operate(op, first, last);
2084        }
2085}
2086#endif
2087