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