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