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 mismatch,\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
1894struct range {
1895	sparsebit_idx_t first, last;
1896	bool set;
1897};
1898
1899struct sparsebit *s;
1900struct range ranges[1000];
1901int num_ranges;
1902
1903static 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
1914static 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
2050unsigned char get8(void)
2051{
2052	int ch;
2053
2054	ch = getchar();
2055	if (ch == EOF)
2056		exit(0);
2057	return ch;
2058}
2059
2060uint64_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
2074int 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