17a338472SThomas Gleixner // SPDX-License-Identifier: GPL-2.0-only
2783e9e51SPaolo Bonzini /*
3783e9e51SPaolo Bonzini * Sparse bit array
4783e9e51SPaolo Bonzini *
5783e9e51SPaolo Bonzini * Copyright (C) 2018, Google LLC.
6783e9e51SPaolo Bonzini * Copyright (C) 2018, Red Hat, Inc. (code style cleanup and fuzzing driver)
7783e9e51SPaolo Bonzini *
8783e9e51SPaolo Bonzini * This library provides functions to support a memory efficient bit array,
9783e9e51SPaolo Bonzini * with an index size of 2^64. A sparsebit array is allocated through
10783e9e51SPaolo Bonzini * the use sparsebit_alloc() and free'd via sparsebit_free(),
11783e9e51SPaolo Bonzini * such as in the following:
12783e9e51SPaolo Bonzini *
13783e9e51SPaolo Bonzini * struct sparsebit *s;
14783e9e51SPaolo Bonzini * s = sparsebit_alloc();
15783e9e51SPaolo Bonzini * sparsebit_free(&s);
16783e9e51SPaolo Bonzini *
17783e9e51SPaolo Bonzini * The struct sparsebit type resolves down to a struct sparsebit.
18783e9e51SPaolo Bonzini * Note that, sparsebit_free() takes a pointer to the sparsebit
19783e9e51SPaolo Bonzini * structure. This is so that sparsebit_free() is able to poison
20783e9e51SPaolo Bonzini * the pointer (e.g. set it to NULL) to the struct sparsebit before
21783e9e51SPaolo Bonzini * returning to the caller.
22783e9e51SPaolo Bonzini *
23783e9e51SPaolo Bonzini * Between the return of sparsebit_alloc() and the call of
24783e9e51SPaolo Bonzini * sparsebit_free(), there are multiple query and modifying operations
25783e9e51SPaolo Bonzini * that can be performed on the allocated sparsebit array. All of
26783e9e51SPaolo Bonzini * these operations take as a parameter the value returned from
27783e9e51SPaolo Bonzini * sparsebit_alloc() and most also take a bit index. Frequently
28783e9e51SPaolo Bonzini * used routines include:
29783e9e51SPaolo Bonzini *
30783e9e51SPaolo Bonzini * ---- Query Operations
31783e9e51SPaolo Bonzini * sparsebit_is_set(s, idx)
32783e9e51SPaolo Bonzini * sparsebit_is_clear(s, idx)
33783e9e51SPaolo Bonzini * sparsebit_any_set(s)
34783e9e51SPaolo Bonzini * sparsebit_first_set(s)
35783e9e51SPaolo Bonzini * sparsebit_next_set(s, prev_idx)
36783e9e51SPaolo Bonzini *
37783e9e51SPaolo Bonzini * ---- Modifying Operations
38783e9e51SPaolo Bonzini * sparsebit_set(s, idx)
39783e9e51SPaolo Bonzini * sparsebit_clear(s, idx)
40783e9e51SPaolo Bonzini * sparsebit_set_num(s, idx, num);
41783e9e51SPaolo Bonzini * sparsebit_clear_num(s, idx, num);
42783e9e51SPaolo Bonzini *
43783e9e51SPaolo Bonzini * A common operation, is to itterate over all the bits set in a test
44783e9e51SPaolo Bonzini * sparsebit array. This can be done via code with the following structure:
45783e9e51SPaolo Bonzini *
46783e9e51SPaolo Bonzini * sparsebit_idx_t idx;
47783e9e51SPaolo Bonzini * if (sparsebit_any_set(s)) {
48783e9e51SPaolo Bonzini * idx = sparsebit_first_set(s);
49783e9e51SPaolo Bonzini * do {
50783e9e51SPaolo Bonzini * ...
51783e9e51SPaolo Bonzini * idx = sparsebit_next_set(s, idx);
52783e9e51SPaolo Bonzini * } while (idx != 0);
53783e9e51SPaolo Bonzini * }
54783e9e51SPaolo Bonzini *
55783e9e51SPaolo Bonzini * The index of the first bit set needs to be obtained via
56783e9e51SPaolo Bonzini * sparsebit_first_set(), because sparsebit_next_set(), needs
57783e9e51SPaolo Bonzini * the index of the previously set. The sparsebit_idx_t type is
58783e9e51SPaolo Bonzini * unsigned, so there is no previous index before 0 that is available.
59783e9e51SPaolo Bonzini * Also, the call to sparsebit_first_set() is not made unless there
60783e9e51SPaolo Bonzini * is at least 1 bit in the array set. This is because sparsebit_first_set()
61783e9e51SPaolo Bonzini * aborts if sparsebit_first_set() is called with no bits set.
62783e9e51SPaolo Bonzini * It is the callers responsibility to assure that the
63783e9e51SPaolo Bonzini * sparsebit array has at least a single bit set before calling
64783e9e51SPaolo Bonzini * sparsebit_first_set().
65783e9e51SPaolo Bonzini *
66783e9e51SPaolo Bonzini * ==== Implementation Overview ====
67783e9e51SPaolo Bonzini * For the most part the internal implementation of sparsebit is
68783e9e51SPaolo Bonzini * opaque to the caller. One important implementation detail that the
69783e9e51SPaolo Bonzini * caller may need to be aware of is the spatial complexity of the
70783e9e51SPaolo Bonzini * implementation. This implementation of a sparsebit array is not
71783e9e51SPaolo Bonzini * only sparse, in that it uses memory proportional to the number of bits
72783e9e51SPaolo Bonzini * set. It is also efficient in memory usage when most of the bits are
73783e9e51SPaolo Bonzini * set.
74783e9e51SPaolo Bonzini *
75783e9e51SPaolo Bonzini * At a high-level the state of the bit settings are maintained through
76783e9e51SPaolo Bonzini * the use of a binary-search tree, where each node contains at least
77783e9e51SPaolo Bonzini * the following members:
78783e9e51SPaolo Bonzini *
79783e9e51SPaolo Bonzini * typedef uint64_t sparsebit_idx_t;
80783e9e51SPaolo Bonzini * typedef uint64_t sparsebit_num_t;
81783e9e51SPaolo Bonzini *
82783e9e51SPaolo Bonzini * sparsebit_idx_t idx;
83783e9e51SPaolo Bonzini * uint32_t mask;
84783e9e51SPaolo Bonzini * sparsebit_num_t num_after;
85783e9e51SPaolo Bonzini *
86783e9e51SPaolo Bonzini * The idx member contains the bit index of the first bit described by this
87783e9e51SPaolo Bonzini * node, while the mask member stores the setting of the first 32-bits.
88783e9e51SPaolo Bonzini * The setting of the bit at idx + n, where 0 <= n < 32, is located in the
89783e9e51SPaolo Bonzini * mask member at 1 << n.
90783e9e51SPaolo Bonzini *
91783e9e51SPaolo Bonzini * Nodes are sorted by idx and the bits described by two nodes will never
92783e9e51SPaolo Bonzini * overlap. The idx member is always aligned to the mask size, i.e. a
93783e9e51SPaolo Bonzini * multiple of 32.
94783e9e51SPaolo Bonzini *
95783e9e51SPaolo Bonzini * Beyond a typical implementation, the nodes in this implementation also
96783e9e51SPaolo Bonzini * contains a member named num_after. The num_after member holds the
97783e9e51SPaolo Bonzini * number of bits immediately after the mask bits that are contiguously set.
98783e9e51SPaolo Bonzini * The use of the num_after member allows this implementation to efficiently
99783e9e51SPaolo Bonzini * represent cases where most bits are set. For example, the case of all
100783e9e51SPaolo Bonzini * but the last two bits set, is represented by the following two nodes:
101783e9e51SPaolo Bonzini *
102783e9e51SPaolo Bonzini * node 0 - idx: 0x0 mask: 0xffffffff num_after: 0xffffffffffffffc0
103783e9e51SPaolo Bonzini * node 1 - idx: 0xffffffffffffffe0 mask: 0x3fffffff num_after: 0
104783e9e51SPaolo Bonzini *
105783e9e51SPaolo Bonzini * ==== Invariants ====
106783e9e51SPaolo Bonzini * This implementation usses the following invariants:
107783e9e51SPaolo Bonzini *
108783e9e51SPaolo Bonzini * + Node are only used to represent bits that are set.
109783e9e51SPaolo Bonzini * Nodes with a mask of 0 and num_after of 0 are not allowed.
110783e9e51SPaolo Bonzini *
111783e9e51SPaolo Bonzini * + Sum of bits set in all the nodes is equal to the value of
112783e9e51SPaolo Bonzini * the struct sparsebit_pvt num_set member.
113783e9e51SPaolo Bonzini *
114783e9e51SPaolo Bonzini * + The setting of at least one bit is always described in a nodes
115783e9e51SPaolo Bonzini * mask (mask >= 1).
116783e9e51SPaolo Bonzini *
117783e9e51SPaolo Bonzini * + A node with all mask bits set only occurs when the last bit
118783e9e51SPaolo Bonzini * described by the previous node is not equal to this nodes
119783e9e51SPaolo Bonzini * starting index - 1. All such occurences of this condition are
120783e9e51SPaolo Bonzini * avoided by moving the setting of the nodes mask bits into
121783e9e51SPaolo Bonzini * the previous nodes num_after setting.
122783e9e51SPaolo Bonzini *
1234d5f26eeSColin Ian King * + Node starting index is evenly divisible by the number of bits
124783e9e51SPaolo Bonzini * within a nodes mask member.
125783e9e51SPaolo Bonzini *
126783e9e51SPaolo Bonzini * + Nodes never represent a range of bits that wrap around the
127783e9e51SPaolo Bonzini * highest supported index.
128783e9e51SPaolo Bonzini *
129783e9e51SPaolo Bonzini * (idx + MASK_BITS + num_after - 1) <= ((sparsebit_idx_t) 0) - 1)
130783e9e51SPaolo Bonzini *
131783e9e51SPaolo Bonzini * As a consequence of the above, the num_after member of a node
132783e9e51SPaolo Bonzini * will always be <=:
133783e9e51SPaolo Bonzini *
134783e9e51SPaolo Bonzini * maximum_index - nodes_starting_index - number_of_mask_bits
135783e9e51SPaolo Bonzini *
136783e9e51SPaolo Bonzini * + Nodes within the binary search tree are sorted based on each
137783e9e51SPaolo Bonzini * nodes starting index.
138783e9e51SPaolo Bonzini *
139783e9e51SPaolo Bonzini * + The range of bits described by any two nodes do not overlap. The
140783e9e51SPaolo Bonzini * range of bits described by a single node is:
141783e9e51SPaolo Bonzini *
142783e9e51SPaolo Bonzini * start: node->idx
143783e9e51SPaolo Bonzini * end (inclusive): node->idx + MASK_BITS + node->num_after - 1;
144783e9e51SPaolo Bonzini *
145783e9e51SPaolo Bonzini * Note, at times these invariants are temporarily violated for a
146783e9e51SPaolo Bonzini * specific portion of the code. For example, when setting a mask
147783e9e51SPaolo Bonzini * bit, there is a small delay between when the mask bit is set and the
148783e9e51SPaolo Bonzini * value in the struct sparsebit_pvt num_set member is updated. Other
149783e9e51SPaolo Bonzini * temporary violations occur when node_split() is called with a specified
150783e9e51SPaolo Bonzini * index and assures that a node where its mask represents the bit
151783e9e51SPaolo Bonzini * at the specified index exists. At times to do this node_split()
152783e9e51SPaolo Bonzini * must split an existing node into two nodes or create a node that
153783e9e51SPaolo Bonzini * has no bits set. Such temporary violations must be corrected before
154783e9e51SPaolo Bonzini * returning to the caller. These corrections are typically performed
155783e9e51SPaolo Bonzini * by the local function node_reduce().
156783e9e51SPaolo Bonzini */
157783e9e51SPaolo Bonzini
158783e9e51SPaolo Bonzini #include "test_util.h"
159783e9e51SPaolo Bonzini #include "sparsebit.h"
160783e9e51SPaolo Bonzini #include <limits.h>
161783e9e51SPaolo Bonzini #include <assert.h>
162783e9e51SPaolo Bonzini
163783e9e51SPaolo Bonzini #define DUMP_LINE_MAX 100 /* Does not include indent amount */
164783e9e51SPaolo Bonzini
165783e9e51SPaolo Bonzini typedef uint32_t mask_t;
166783e9e51SPaolo Bonzini #define MASK_BITS (sizeof(mask_t) * CHAR_BIT)
167783e9e51SPaolo Bonzini
168783e9e51SPaolo Bonzini struct node {
169783e9e51SPaolo Bonzini struct node *parent;
170783e9e51SPaolo Bonzini struct node *left;
171783e9e51SPaolo Bonzini struct node *right;
172783e9e51SPaolo Bonzini sparsebit_idx_t idx; /* index of least-significant bit in mask */
173783e9e51SPaolo Bonzini sparsebit_num_t num_after; /* num contiguously set after mask */
174783e9e51SPaolo Bonzini mask_t mask;
175783e9e51SPaolo Bonzini };
176783e9e51SPaolo Bonzini
177783e9e51SPaolo Bonzini struct sparsebit {
178783e9e51SPaolo Bonzini /*
179783e9e51SPaolo Bonzini * Points to root node of the binary search
180783e9e51SPaolo Bonzini * tree. Equal to NULL when no bits are set in
181783e9e51SPaolo Bonzini * the entire sparsebit array.
182783e9e51SPaolo Bonzini */
183783e9e51SPaolo Bonzini struct node *root;
184783e9e51SPaolo Bonzini
185783e9e51SPaolo Bonzini /*
186783e9e51SPaolo Bonzini * A redundant count of the total number of bits set. Used for
187783e9e51SPaolo Bonzini * diagnostic purposes and to change the time complexity of
188783e9e51SPaolo Bonzini * sparsebit_num_set() from O(n) to O(1).
189783e9e51SPaolo Bonzini * Note: Due to overflow, a value of 0 means none or all set.
190783e9e51SPaolo Bonzini */
191783e9e51SPaolo Bonzini sparsebit_num_t num_set;
192783e9e51SPaolo Bonzini };
193783e9e51SPaolo Bonzini
194783e9e51SPaolo Bonzini /* Returns the number of set bits described by the settings
195783e9e51SPaolo Bonzini * of the node pointed to by nodep.
196783e9e51SPaolo Bonzini */
node_num_set(struct node * nodep)197783e9e51SPaolo Bonzini static sparsebit_num_t node_num_set(struct node *nodep)
198783e9e51SPaolo Bonzini {
199783e9e51SPaolo Bonzini return nodep->num_after + __builtin_popcount(nodep->mask);
200783e9e51SPaolo Bonzini }
201783e9e51SPaolo Bonzini
202783e9e51SPaolo Bonzini /* Returns a pointer to the node that describes the
203783e9e51SPaolo Bonzini * lowest bit index.
204783e9e51SPaolo Bonzini */
node_first(const struct sparsebit * s)205*35f50c91SMichael Roth static struct node *node_first(const struct sparsebit *s)
206783e9e51SPaolo Bonzini {
207783e9e51SPaolo Bonzini struct node *nodep;
208783e9e51SPaolo Bonzini
209783e9e51SPaolo Bonzini for (nodep = s->root; nodep && nodep->left; nodep = nodep->left)
210783e9e51SPaolo Bonzini ;
211783e9e51SPaolo Bonzini
212783e9e51SPaolo Bonzini return nodep;
213783e9e51SPaolo Bonzini }
214783e9e51SPaolo Bonzini
215783e9e51SPaolo Bonzini /* Returns a pointer to the node that describes the
216783e9e51SPaolo Bonzini * lowest bit index > the index of the node pointed to by np.
217783e9e51SPaolo Bonzini * Returns NULL if no node with a higher index exists.
218783e9e51SPaolo Bonzini */
node_next(const struct sparsebit * s,struct node * np)219*35f50c91SMichael Roth static struct node *node_next(const struct sparsebit *s, struct node *np)
220783e9e51SPaolo Bonzini {
221783e9e51SPaolo Bonzini struct node *nodep = np;
222783e9e51SPaolo Bonzini
223783e9e51SPaolo Bonzini /*
224783e9e51SPaolo Bonzini * If current node has a right child, next node is the left-most
225783e9e51SPaolo Bonzini * of the right child.
226783e9e51SPaolo Bonzini */
227783e9e51SPaolo Bonzini if (nodep->right) {
228783e9e51SPaolo Bonzini for (nodep = nodep->right; nodep->left; nodep = nodep->left)
229783e9e51SPaolo Bonzini ;
230783e9e51SPaolo Bonzini return nodep;
231783e9e51SPaolo Bonzini }
232783e9e51SPaolo Bonzini
233783e9e51SPaolo Bonzini /*
234783e9e51SPaolo Bonzini * No right child. Go up until node is left child of a parent.
235783e9e51SPaolo Bonzini * That parent is then the next node.
236783e9e51SPaolo Bonzini */
237783e9e51SPaolo Bonzini while (nodep->parent && nodep == nodep->parent->right)
238783e9e51SPaolo Bonzini nodep = nodep->parent;
239783e9e51SPaolo Bonzini
240783e9e51SPaolo Bonzini return nodep->parent;
241783e9e51SPaolo Bonzini }
242783e9e51SPaolo Bonzini
243783e9e51SPaolo Bonzini /* Searches for and returns a pointer to the node that describes the
244783e9e51SPaolo Bonzini * highest index < the index of the node pointed to by np.
245783e9e51SPaolo Bonzini * Returns NULL if no node with a lower index exists.
246783e9e51SPaolo Bonzini */
node_prev(const struct sparsebit * s,struct node * np)247*35f50c91SMichael Roth static struct node *node_prev(const struct sparsebit *s, struct node *np)
248783e9e51SPaolo Bonzini {
249783e9e51SPaolo Bonzini struct node *nodep = np;
250783e9e51SPaolo Bonzini
251783e9e51SPaolo Bonzini /*
252783e9e51SPaolo Bonzini * If current node has a left child, next node is the right-most
253783e9e51SPaolo Bonzini * of the left child.
254783e9e51SPaolo Bonzini */
255783e9e51SPaolo Bonzini if (nodep->left) {
256783e9e51SPaolo Bonzini for (nodep = nodep->left; nodep->right; nodep = nodep->right)
257783e9e51SPaolo Bonzini ;
258783e9e51SPaolo Bonzini return (struct node *) nodep;
259783e9e51SPaolo Bonzini }
260783e9e51SPaolo Bonzini
261783e9e51SPaolo Bonzini /*
262783e9e51SPaolo Bonzini * No left child. Go up until node is right child of a parent.
263783e9e51SPaolo Bonzini * That parent is then the next node.
264783e9e51SPaolo Bonzini */
265783e9e51SPaolo Bonzini while (nodep->parent && nodep == nodep->parent->left)
266783e9e51SPaolo Bonzini nodep = nodep->parent;
267783e9e51SPaolo Bonzini
268783e9e51SPaolo Bonzini return (struct node *) nodep->parent;
269783e9e51SPaolo Bonzini }
270783e9e51SPaolo Bonzini
271783e9e51SPaolo Bonzini
272783e9e51SPaolo Bonzini /* Allocates space to hold a copy of the node sub-tree pointed to by
273783e9e51SPaolo Bonzini * subtree and duplicates the bit settings to the newly allocated nodes.
274783e9e51SPaolo Bonzini * Returns the newly allocated copy of subtree.
275783e9e51SPaolo Bonzini */
node_copy_subtree(const struct node * subtree)276*35f50c91SMichael Roth static struct node *node_copy_subtree(const struct node *subtree)
277783e9e51SPaolo Bonzini {
278783e9e51SPaolo Bonzini struct node *root;
279783e9e51SPaolo Bonzini
280783e9e51SPaolo Bonzini /* Duplicate the node at the root of the subtree */
281783e9e51SPaolo Bonzini root = calloc(1, sizeof(*root));
282783e9e51SPaolo Bonzini if (!root) {
283783e9e51SPaolo Bonzini perror("calloc");
284783e9e51SPaolo Bonzini abort();
285783e9e51SPaolo Bonzini }
286783e9e51SPaolo Bonzini
287783e9e51SPaolo Bonzini root->idx = subtree->idx;
288783e9e51SPaolo Bonzini root->mask = subtree->mask;
289783e9e51SPaolo Bonzini root->num_after = subtree->num_after;
290783e9e51SPaolo Bonzini
291783e9e51SPaolo Bonzini /* As needed, recursively duplicate the left and right subtrees */
292783e9e51SPaolo Bonzini if (subtree->left) {
293783e9e51SPaolo Bonzini root->left = node_copy_subtree(subtree->left);
294783e9e51SPaolo Bonzini root->left->parent = root;
295783e9e51SPaolo Bonzini }
296783e9e51SPaolo Bonzini
297783e9e51SPaolo Bonzini if (subtree->right) {
298783e9e51SPaolo Bonzini root->right = node_copy_subtree(subtree->right);
299783e9e51SPaolo Bonzini root->right->parent = root;
300783e9e51SPaolo Bonzini }
301783e9e51SPaolo Bonzini
302783e9e51SPaolo Bonzini return root;
303783e9e51SPaolo Bonzini }
304783e9e51SPaolo Bonzini
305783e9e51SPaolo Bonzini /* Searches for and returns a pointer to the node that describes the setting
306783e9e51SPaolo Bonzini * of the bit given by idx. A node describes the setting of a bit if its
307783e9e51SPaolo Bonzini * index is within the bits described by the mask bits or the number of
308783e9e51SPaolo Bonzini * contiguous bits set after the mask. Returns NULL if there is no such node.
309783e9e51SPaolo Bonzini */
node_find(const struct sparsebit * s,sparsebit_idx_t idx)310*35f50c91SMichael Roth static struct node *node_find(const struct sparsebit *s, sparsebit_idx_t idx)
311783e9e51SPaolo Bonzini {
312783e9e51SPaolo Bonzini struct node *nodep;
313783e9e51SPaolo Bonzini
314783e9e51SPaolo Bonzini /* Find the node that describes the setting of the bit at idx */
315783e9e51SPaolo Bonzini for (nodep = s->root; nodep;
316783e9e51SPaolo Bonzini nodep = nodep->idx > idx ? nodep->left : nodep->right) {
317783e9e51SPaolo Bonzini if (idx >= nodep->idx &&
318783e9e51SPaolo Bonzini idx <= nodep->idx + MASK_BITS + nodep->num_after - 1)
319783e9e51SPaolo Bonzini break;
320783e9e51SPaolo Bonzini }
321783e9e51SPaolo Bonzini
322783e9e51SPaolo Bonzini return nodep;
323783e9e51SPaolo Bonzini }
324783e9e51SPaolo Bonzini
325783e9e51SPaolo Bonzini /* Entry Requirements:
326783e9e51SPaolo Bonzini * + A node that describes the setting of idx is not already present.
327783e9e51SPaolo Bonzini *
328783e9e51SPaolo Bonzini * Adds a new node to describe the setting of the bit at the index given
329783e9e51SPaolo Bonzini * by idx. Returns a pointer to the newly added node.
330783e9e51SPaolo Bonzini *
331783e9e51SPaolo Bonzini * TODO(lhuemill): Degenerate cases causes the tree to get unbalanced.
332783e9e51SPaolo Bonzini */
node_add(struct sparsebit * s,sparsebit_idx_t idx)333783e9e51SPaolo Bonzini static struct node *node_add(struct sparsebit *s, sparsebit_idx_t idx)
334783e9e51SPaolo Bonzini {
335783e9e51SPaolo Bonzini struct node *nodep, *parentp, *prev;
336783e9e51SPaolo Bonzini
337783e9e51SPaolo Bonzini /* Allocate and initialize the new node. */
338783e9e51SPaolo Bonzini nodep = calloc(1, sizeof(*nodep));
339783e9e51SPaolo Bonzini if (!nodep) {
340783e9e51SPaolo Bonzini perror("calloc");
341783e9e51SPaolo Bonzini abort();
342783e9e51SPaolo Bonzini }
343783e9e51SPaolo Bonzini
344783e9e51SPaolo Bonzini nodep->idx = idx & -MASK_BITS;
345783e9e51SPaolo Bonzini
346783e9e51SPaolo Bonzini /* If no nodes, set it up as the root node. */
347783e9e51SPaolo Bonzini if (!s->root) {
348783e9e51SPaolo Bonzini s->root = nodep;
349783e9e51SPaolo Bonzini return nodep;
350783e9e51SPaolo Bonzini }
351783e9e51SPaolo Bonzini
352783e9e51SPaolo Bonzini /*
353783e9e51SPaolo Bonzini * Find the parent where the new node should be attached
354783e9e51SPaolo Bonzini * and add the node there.
355783e9e51SPaolo Bonzini */
356783e9e51SPaolo Bonzini parentp = s->root;
357783e9e51SPaolo Bonzini while (true) {
358783e9e51SPaolo Bonzini if (idx < parentp->idx) {
359783e9e51SPaolo Bonzini if (!parentp->left) {
360783e9e51SPaolo Bonzini parentp->left = nodep;
361783e9e51SPaolo Bonzini nodep->parent = parentp;
362783e9e51SPaolo Bonzini break;
363783e9e51SPaolo Bonzini }
364783e9e51SPaolo Bonzini parentp = parentp->left;
365783e9e51SPaolo Bonzini } else {
366783e9e51SPaolo Bonzini assert(idx > parentp->idx + MASK_BITS + parentp->num_after - 1);
367783e9e51SPaolo Bonzini if (!parentp->right) {
368783e9e51SPaolo Bonzini parentp->right = nodep;
369783e9e51SPaolo Bonzini nodep->parent = parentp;
370783e9e51SPaolo Bonzini break;
371783e9e51SPaolo Bonzini }
372783e9e51SPaolo Bonzini parentp = parentp->right;
373783e9e51SPaolo Bonzini }
374783e9e51SPaolo Bonzini }
375783e9e51SPaolo Bonzini
376783e9e51SPaolo Bonzini /*
377783e9e51SPaolo Bonzini * Does num_after bits of previous node overlap with the mask
378783e9e51SPaolo Bonzini * of the new node? If so set the bits in the new nodes mask
379783e9e51SPaolo Bonzini * and reduce the previous nodes num_after.
380783e9e51SPaolo Bonzini */
381783e9e51SPaolo Bonzini prev = node_prev(s, nodep);
382783e9e51SPaolo Bonzini while (prev && prev->idx + MASK_BITS + prev->num_after - 1 >= nodep->idx) {
383783e9e51SPaolo Bonzini unsigned int n1 = (prev->idx + MASK_BITS + prev->num_after - 1)
384783e9e51SPaolo Bonzini - nodep->idx;
385783e9e51SPaolo Bonzini assert(prev->num_after > 0);
386783e9e51SPaolo Bonzini assert(n1 < MASK_BITS);
387783e9e51SPaolo Bonzini assert(!(nodep->mask & (1 << n1)));
388783e9e51SPaolo Bonzini nodep->mask |= (1 << n1);
389783e9e51SPaolo Bonzini prev->num_after--;
390783e9e51SPaolo Bonzini }
391783e9e51SPaolo Bonzini
392783e9e51SPaolo Bonzini return nodep;
393783e9e51SPaolo Bonzini }
394783e9e51SPaolo Bonzini
395783e9e51SPaolo Bonzini /* Returns whether all the bits in the sparsebit array are set. */
sparsebit_all_set(const struct sparsebit * s)396*35f50c91SMichael Roth bool sparsebit_all_set(const struct sparsebit *s)
397783e9e51SPaolo Bonzini {
398783e9e51SPaolo Bonzini /*
399783e9e51SPaolo Bonzini * If any nodes there must be at least one bit set. Only case
400783e9e51SPaolo Bonzini * where a bit is set and total num set is 0, is when all bits
401783e9e51SPaolo Bonzini * are set.
402783e9e51SPaolo Bonzini */
403783e9e51SPaolo Bonzini return s->root && s->num_set == 0;
404783e9e51SPaolo Bonzini }
405783e9e51SPaolo Bonzini
406783e9e51SPaolo Bonzini /* Clears all bits described by the node pointed to by nodep, then
407783e9e51SPaolo Bonzini * removes the node.
408783e9e51SPaolo Bonzini */
node_rm(struct sparsebit * s,struct node * nodep)409783e9e51SPaolo Bonzini static void node_rm(struct sparsebit *s, struct node *nodep)
410783e9e51SPaolo Bonzini {
411783e9e51SPaolo Bonzini struct node *tmp;
412783e9e51SPaolo Bonzini sparsebit_num_t num_set;
413783e9e51SPaolo Bonzini
414783e9e51SPaolo Bonzini num_set = node_num_set(nodep);
415783e9e51SPaolo Bonzini assert(s->num_set >= num_set || sparsebit_all_set(s));
416783e9e51SPaolo Bonzini s->num_set -= node_num_set(nodep);
417783e9e51SPaolo Bonzini
418783e9e51SPaolo Bonzini /* Have both left and right child */
419783e9e51SPaolo Bonzini if (nodep->left && nodep->right) {
420783e9e51SPaolo Bonzini /*
421783e9e51SPaolo Bonzini * Move left children to the leftmost leaf node
422783e9e51SPaolo Bonzini * of the right child.
423783e9e51SPaolo Bonzini */
424783e9e51SPaolo Bonzini for (tmp = nodep->right; tmp->left; tmp = tmp->left)
425783e9e51SPaolo Bonzini ;
426783e9e51SPaolo Bonzini tmp->left = nodep->left;
427783e9e51SPaolo Bonzini nodep->left = NULL;
428783e9e51SPaolo Bonzini tmp->left->parent = tmp;
429783e9e51SPaolo Bonzini }
430783e9e51SPaolo Bonzini
431783e9e51SPaolo Bonzini /* Left only child */
432783e9e51SPaolo Bonzini if (nodep->left) {
433783e9e51SPaolo Bonzini if (!nodep->parent) {
434783e9e51SPaolo Bonzini s->root = nodep->left;
435783e9e51SPaolo Bonzini nodep->left->parent = NULL;
436783e9e51SPaolo Bonzini } else {
437783e9e51SPaolo Bonzini nodep->left->parent = nodep->parent;
438783e9e51SPaolo Bonzini if (nodep == nodep->parent->left)
439783e9e51SPaolo Bonzini nodep->parent->left = nodep->left;
440783e9e51SPaolo Bonzini else {
441783e9e51SPaolo Bonzini assert(nodep == nodep->parent->right);
442783e9e51SPaolo Bonzini nodep->parent->right = nodep->left;
443783e9e51SPaolo Bonzini }
444783e9e51SPaolo Bonzini }
445783e9e51SPaolo Bonzini
446783e9e51SPaolo Bonzini nodep->parent = nodep->left = nodep->right = NULL;
447783e9e51SPaolo Bonzini free(nodep);
448783e9e51SPaolo Bonzini
449783e9e51SPaolo Bonzini return;
450783e9e51SPaolo Bonzini }
451783e9e51SPaolo Bonzini
452783e9e51SPaolo Bonzini
453783e9e51SPaolo Bonzini /* Right only child */
454783e9e51SPaolo Bonzini if (nodep->right) {
455783e9e51SPaolo Bonzini if (!nodep->parent) {
456783e9e51SPaolo Bonzini s->root = nodep->right;
457783e9e51SPaolo Bonzini nodep->right->parent = NULL;
458783e9e51SPaolo Bonzini } else {
459783e9e51SPaolo Bonzini nodep->right->parent = nodep->parent;
460783e9e51SPaolo Bonzini if (nodep == nodep->parent->left)
461783e9e51SPaolo Bonzini nodep->parent->left = nodep->right;
462783e9e51SPaolo Bonzini else {
463783e9e51SPaolo Bonzini assert(nodep == nodep->parent->right);
464783e9e51SPaolo Bonzini nodep->parent->right = nodep->right;
465783e9e51SPaolo Bonzini }
466783e9e51SPaolo Bonzini }
467783e9e51SPaolo Bonzini
468783e9e51SPaolo Bonzini nodep->parent = nodep->left = nodep->right = NULL;
469783e9e51SPaolo Bonzini free(nodep);
470783e9e51SPaolo Bonzini
471783e9e51SPaolo Bonzini return;
472783e9e51SPaolo Bonzini }
473783e9e51SPaolo Bonzini
474783e9e51SPaolo Bonzini /* Leaf Node */
475783e9e51SPaolo Bonzini if (!nodep->parent) {
476783e9e51SPaolo Bonzini s->root = NULL;
477783e9e51SPaolo Bonzini } else {
478783e9e51SPaolo Bonzini if (nodep->parent->left == nodep)
479783e9e51SPaolo Bonzini nodep->parent->left = NULL;
480783e9e51SPaolo Bonzini else {
481783e9e51SPaolo Bonzini assert(nodep == nodep->parent->right);
482783e9e51SPaolo Bonzini nodep->parent->right = NULL;
483783e9e51SPaolo Bonzini }
484783e9e51SPaolo Bonzini }
485783e9e51SPaolo Bonzini
486783e9e51SPaolo Bonzini nodep->parent = nodep->left = nodep->right = NULL;
487783e9e51SPaolo Bonzini free(nodep);
488783e9e51SPaolo Bonzini
489783e9e51SPaolo Bonzini return;
490783e9e51SPaolo Bonzini }
491783e9e51SPaolo Bonzini
492783e9e51SPaolo Bonzini /* Splits the node containing the bit at idx so that there is a node
493783e9e51SPaolo Bonzini * that starts at the specified index. If no such node exists, a new
494783e9e51SPaolo Bonzini * node at the specified index is created. Returns the new node.
495783e9e51SPaolo Bonzini *
496783e9e51SPaolo Bonzini * idx must start of a mask boundary.
497783e9e51SPaolo Bonzini */
node_split(struct sparsebit * s,sparsebit_idx_t idx)498783e9e51SPaolo Bonzini static struct node *node_split(struct sparsebit *s, sparsebit_idx_t idx)
499783e9e51SPaolo Bonzini {
500783e9e51SPaolo Bonzini struct node *nodep1, *nodep2;
501783e9e51SPaolo Bonzini sparsebit_idx_t offset;
502783e9e51SPaolo Bonzini sparsebit_num_t orig_num_after;
503783e9e51SPaolo Bonzini
504783e9e51SPaolo Bonzini assert(!(idx % MASK_BITS));
505783e9e51SPaolo Bonzini
506783e9e51SPaolo Bonzini /*
507783e9e51SPaolo Bonzini * Is there a node that describes the setting of idx?
508783e9e51SPaolo Bonzini * If not, add it.
509783e9e51SPaolo Bonzini */
510783e9e51SPaolo Bonzini nodep1 = node_find(s, idx);
511783e9e51SPaolo Bonzini if (!nodep1)
512783e9e51SPaolo Bonzini return node_add(s, idx);
513783e9e51SPaolo Bonzini
514783e9e51SPaolo Bonzini /*
515783e9e51SPaolo Bonzini * All done if the starting index of the node is where the
516783e9e51SPaolo Bonzini * split should occur.
517783e9e51SPaolo Bonzini */
518783e9e51SPaolo Bonzini if (nodep1->idx == idx)
519783e9e51SPaolo Bonzini return nodep1;
520783e9e51SPaolo Bonzini
521783e9e51SPaolo Bonzini /*
522783e9e51SPaolo Bonzini * Split point not at start of mask, so it must be part of
523783e9e51SPaolo Bonzini * bits described by num_after.
524783e9e51SPaolo Bonzini */
525783e9e51SPaolo Bonzini
526783e9e51SPaolo Bonzini /*
527783e9e51SPaolo Bonzini * Calculate offset within num_after for where the split is
528783e9e51SPaolo Bonzini * to occur.
529783e9e51SPaolo Bonzini */
530783e9e51SPaolo Bonzini offset = idx - (nodep1->idx + MASK_BITS);
531783e9e51SPaolo Bonzini orig_num_after = nodep1->num_after;
532783e9e51SPaolo Bonzini
533783e9e51SPaolo Bonzini /*
534783e9e51SPaolo Bonzini * Add a new node to describe the bits starting at
535783e9e51SPaolo Bonzini * the split point.
536783e9e51SPaolo Bonzini */
537783e9e51SPaolo Bonzini nodep1->num_after = offset;
538783e9e51SPaolo Bonzini nodep2 = node_add(s, idx);
539783e9e51SPaolo Bonzini
540783e9e51SPaolo Bonzini /* Move bits after the split point into the new node */
541783e9e51SPaolo Bonzini nodep2->num_after = orig_num_after - offset;
542783e9e51SPaolo Bonzini if (nodep2->num_after >= MASK_BITS) {
543783e9e51SPaolo Bonzini nodep2->mask = ~(mask_t) 0;
544783e9e51SPaolo Bonzini nodep2->num_after -= MASK_BITS;
545783e9e51SPaolo Bonzini } else {
546783e9e51SPaolo Bonzini nodep2->mask = (1 << nodep2->num_after) - 1;
547783e9e51SPaolo Bonzini nodep2->num_after = 0;
548783e9e51SPaolo Bonzini }
549783e9e51SPaolo Bonzini
550783e9e51SPaolo Bonzini return nodep2;
551783e9e51SPaolo Bonzini }
552783e9e51SPaolo Bonzini
553783e9e51SPaolo Bonzini /* Iteratively reduces the node pointed to by nodep and its adjacent
554783e9e51SPaolo Bonzini * nodes into a more compact form. For example, a node with a mask with
555783e9e51SPaolo Bonzini * all bits set adjacent to a previous node, will get combined into a
556783e9e51SPaolo Bonzini * single node with an increased num_after setting.
557783e9e51SPaolo Bonzini *
558783e9e51SPaolo Bonzini * After each reduction, a further check is made to see if additional
559783e9e51SPaolo Bonzini * reductions are possible with the new previous and next nodes. Note,
560783e9e51SPaolo Bonzini * a search for a reduction is only done across the nodes nearest nodep
561783e9e51SPaolo Bonzini * and those that became part of a reduction. Reductions beyond nodep
562783e9e51SPaolo Bonzini * and the adjacent nodes that are reduced are not discovered. It is the
563783e9e51SPaolo Bonzini * responsibility of the caller to pass a nodep that is within one node
564783e9e51SPaolo Bonzini * of each possible reduction.
565783e9e51SPaolo Bonzini *
566783e9e51SPaolo Bonzini * This function does not fix the temporary violation of all invariants.
567783e9e51SPaolo Bonzini * For example it does not fix the case where the bit settings described
568783e9e51SPaolo Bonzini * by two or more nodes overlap. Such a violation introduces the potential
569783e9e51SPaolo Bonzini * complication of a bit setting for a specific index having different settings
570783e9e51SPaolo Bonzini * in different nodes. This would then introduce the further complication
571783e9e51SPaolo Bonzini * of which node has the correct setting of the bit and thus such conditions
572783e9e51SPaolo Bonzini * are not allowed.
573783e9e51SPaolo Bonzini *
574783e9e51SPaolo Bonzini * This function is designed to fix invariant violations that are introduced
575783e9e51SPaolo Bonzini * by node_split() and by changes to the nodes mask or num_after members.
576783e9e51SPaolo Bonzini * For example, when setting a bit within a nodes mask, the function that
577783e9e51SPaolo Bonzini * sets the bit doesn't have to worry about whether the setting of that
578783e9e51SPaolo Bonzini * bit caused the mask to have leading only or trailing only bits set.
579783e9e51SPaolo Bonzini * Instead, the function can call node_reduce(), with nodep equal to the
580783e9e51SPaolo Bonzini * node address that it set a mask bit in, and node_reduce() will notice
581783e9e51SPaolo Bonzini * the cases of leading or trailing only bits and that there is an
582783e9e51SPaolo Bonzini * adjacent node that the bit settings could be merged into.
583783e9e51SPaolo Bonzini *
584783e9e51SPaolo Bonzini * This implementation specifically detects and corrects violation of the
585783e9e51SPaolo Bonzini * following invariants:
586783e9e51SPaolo Bonzini *
587783e9e51SPaolo Bonzini * + Node are only used to represent bits that are set.
588783e9e51SPaolo Bonzini * Nodes with a mask of 0 and num_after of 0 are not allowed.
589783e9e51SPaolo Bonzini *
590783e9e51SPaolo Bonzini * + The setting of at least one bit is always described in a nodes
591783e9e51SPaolo Bonzini * mask (mask >= 1).
592783e9e51SPaolo Bonzini *
593783e9e51SPaolo Bonzini * + A node with all mask bits set only occurs when the last bit
594783e9e51SPaolo Bonzini * described by the previous node is not equal to this nodes
595783e9e51SPaolo Bonzini * starting index - 1. All such occurences of this condition are
596783e9e51SPaolo Bonzini * avoided by moving the setting of the nodes mask bits into
597783e9e51SPaolo Bonzini * the previous nodes num_after setting.
598783e9e51SPaolo Bonzini */
node_reduce(struct sparsebit * s,struct node * nodep)599783e9e51SPaolo Bonzini static void node_reduce(struct sparsebit *s, struct node *nodep)
600783e9e51SPaolo Bonzini {
601783e9e51SPaolo Bonzini bool reduction_performed;
602783e9e51SPaolo Bonzini
603783e9e51SPaolo Bonzini do {
604783e9e51SPaolo Bonzini reduction_performed = false;
605783e9e51SPaolo Bonzini struct node *prev, *next, *tmp;
606783e9e51SPaolo Bonzini
607783e9e51SPaolo Bonzini /* 1) Potential reductions within the current node. */
608783e9e51SPaolo Bonzini
609783e9e51SPaolo Bonzini /* Nodes with all bits cleared may be removed. */
610783e9e51SPaolo Bonzini if (nodep->mask == 0 && nodep->num_after == 0) {
611783e9e51SPaolo Bonzini /*
612783e9e51SPaolo Bonzini * About to remove the node pointed to by
613783e9e51SPaolo Bonzini * nodep, which normally would cause a problem
614783e9e51SPaolo Bonzini * for the next pass through the reduction loop,
615783e9e51SPaolo Bonzini * because the node at the starting point no longer
616783e9e51SPaolo Bonzini * exists. This potential problem is handled
617783e9e51SPaolo Bonzini * by first remembering the location of the next
618783e9e51SPaolo Bonzini * or previous nodes. Doesn't matter which, because
619783e9e51SPaolo Bonzini * once the node at nodep is removed, there will be
620783e9e51SPaolo Bonzini * no other nodes between prev and next.
621783e9e51SPaolo Bonzini *
622783e9e51SPaolo Bonzini * Note, the checks performed on nodep against both
623783e9e51SPaolo Bonzini * both prev and next both check for an adjacent
624783e9e51SPaolo Bonzini * node that can be reduced into a single node. As
625783e9e51SPaolo Bonzini * such, after removing the node at nodep, doesn't
626783e9e51SPaolo Bonzini * matter whether the nodep for the next pass
627783e9e51SPaolo Bonzini * through the loop is equal to the previous pass
628783e9e51SPaolo Bonzini * prev or next node. Either way, on the next pass
629783e9e51SPaolo Bonzini * the one not selected will become either the
630783e9e51SPaolo Bonzini * prev or next node.
631783e9e51SPaolo Bonzini */
632783e9e51SPaolo Bonzini tmp = node_next(s, nodep);
633783e9e51SPaolo Bonzini if (!tmp)
634783e9e51SPaolo Bonzini tmp = node_prev(s, nodep);
635783e9e51SPaolo Bonzini
636783e9e51SPaolo Bonzini node_rm(s, nodep);
637783e9e51SPaolo Bonzini
638783e9e51SPaolo Bonzini nodep = tmp;
639783e9e51SPaolo Bonzini reduction_performed = true;
640783e9e51SPaolo Bonzini continue;
641783e9e51SPaolo Bonzini }
642783e9e51SPaolo Bonzini
643783e9e51SPaolo Bonzini /*
644783e9e51SPaolo Bonzini * When the mask is 0, can reduce the amount of num_after
645783e9e51SPaolo Bonzini * bits by moving the initial num_after bits into the mask.
646783e9e51SPaolo Bonzini */
647783e9e51SPaolo Bonzini if (nodep->mask == 0) {
648783e9e51SPaolo Bonzini assert(nodep->num_after != 0);
649783e9e51SPaolo Bonzini assert(nodep->idx + MASK_BITS > nodep->idx);
650783e9e51SPaolo Bonzini
651783e9e51SPaolo Bonzini nodep->idx += MASK_BITS;
652783e9e51SPaolo Bonzini
653783e9e51SPaolo Bonzini if (nodep->num_after >= MASK_BITS) {
654783e9e51SPaolo Bonzini nodep->mask = ~0;
655783e9e51SPaolo Bonzini nodep->num_after -= MASK_BITS;
656783e9e51SPaolo Bonzini } else {
657783e9e51SPaolo Bonzini nodep->mask = (1u << nodep->num_after) - 1;
658783e9e51SPaolo Bonzini nodep->num_after = 0;
659783e9e51SPaolo Bonzini }
660783e9e51SPaolo Bonzini
661783e9e51SPaolo Bonzini reduction_performed = true;
662783e9e51SPaolo Bonzini continue;
663783e9e51SPaolo Bonzini }
664783e9e51SPaolo Bonzini
665783e9e51SPaolo Bonzini /*
666783e9e51SPaolo Bonzini * 2) Potential reductions between the current and
667783e9e51SPaolo Bonzini * previous nodes.
668783e9e51SPaolo Bonzini */
669783e9e51SPaolo Bonzini prev = node_prev(s, nodep);
670783e9e51SPaolo Bonzini if (prev) {
671783e9e51SPaolo Bonzini sparsebit_idx_t prev_highest_bit;
672783e9e51SPaolo Bonzini
673783e9e51SPaolo Bonzini /* Nodes with no bits set can be removed. */
674783e9e51SPaolo Bonzini if (prev->mask == 0 && prev->num_after == 0) {
675783e9e51SPaolo Bonzini node_rm(s, prev);
676783e9e51SPaolo Bonzini
677783e9e51SPaolo Bonzini reduction_performed = true;
678783e9e51SPaolo Bonzini continue;
679783e9e51SPaolo Bonzini }
680783e9e51SPaolo Bonzini
681783e9e51SPaolo Bonzini /*
682783e9e51SPaolo Bonzini * All mask bits set and previous node has
683783e9e51SPaolo Bonzini * adjacent index.
684783e9e51SPaolo Bonzini */
685783e9e51SPaolo Bonzini if (nodep->mask + 1 == 0 &&
686783e9e51SPaolo Bonzini prev->idx + MASK_BITS == nodep->idx) {
687783e9e51SPaolo Bonzini prev->num_after += MASK_BITS + nodep->num_after;
688783e9e51SPaolo Bonzini nodep->mask = 0;
689783e9e51SPaolo Bonzini nodep->num_after = 0;
690783e9e51SPaolo Bonzini
691783e9e51SPaolo Bonzini reduction_performed = true;
692783e9e51SPaolo Bonzini continue;
693783e9e51SPaolo Bonzini }
694783e9e51SPaolo Bonzini
695783e9e51SPaolo Bonzini /*
696783e9e51SPaolo Bonzini * Is node adjacent to previous node and the node
697783e9e51SPaolo Bonzini * contains a single contiguous range of bits
698783e9e51SPaolo Bonzini * starting from the beginning of the mask?
699783e9e51SPaolo Bonzini */
700783e9e51SPaolo Bonzini prev_highest_bit = prev->idx + MASK_BITS - 1 + prev->num_after;
701783e9e51SPaolo Bonzini if (prev_highest_bit + 1 == nodep->idx &&
702783e9e51SPaolo Bonzini (nodep->mask | (nodep->mask >> 1)) == nodep->mask) {
703783e9e51SPaolo Bonzini /*
704783e9e51SPaolo Bonzini * How many contiguous bits are there?
705783e9e51SPaolo Bonzini * Is equal to the total number of set
706783e9e51SPaolo Bonzini * bits, due to an earlier check that
707783e9e51SPaolo Bonzini * there is a single contiguous range of
708783e9e51SPaolo Bonzini * set bits.
709783e9e51SPaolo Bonzini */
710783e9e51SPaolo Bonzini unsigned int num_contiguous
711783e9e51SPaolo Bonzini = __builtin_popcount(nodep->mask);
712783e9e51SPaolo Bonzini assert((num_contiguous > 0) &&
713783e9e51SPaolo Bonzini ((1ULL << num_contiguous) - 1) == nodep->mask);
714783e9e51SPaolo Bonzini
715783e9e51SPaolo Bonzini prev->num_after += num_contiguous;
716783e9e51SPaolo Bonzini nodep->mask = 0;
717783e9e51SPaolo Bonzini
718783e9e51SPaolo Bonzini /*
719783e9e51SPaolo Bonzini * For predictable performance, handle special
720783e9e51SPaolo Bonzini * case where all mask bits are set and there
721783e9e51SPaolo Bonzini * is a non-zero num_after setting. This code
722783e9e51SPaolo Bonzini * is functionally correct without the following
723783e9e51SPaolo Bonzini * conditionalized statements, but without them
724783e9e51SPaolo Bonzini * the value of num_after is only reduced by
725783e9e51SPaolo Bonzini * the number of mask bits per pass. There are
726783e9e51SPaolo Bonzini * cases where num_after can be close to 2^64.
727783e9e51SPaolo Bonzini * Without this code it could take nearly
728783e9e51SPaolo Bonzini * (2^64) / 32 passes to perform the full
729783e9e51SPaolo Bonzini * reduction.
730783e9e51SPaolo Bonzini */
731783e9e51SPaolo Bonzini if (num_contiguous == MASK_BITS) {
732783e9e51SPaolo Bonzini prev->num_after += nodep->num_after;
733783e9e51SPaolo Bonzini nodep->num_after = 0;
734783e9e51SPaolo Bonzini }
735783e9e51SPaolo Bonzini
736783e9e51SPaolo Bonzini reduction_performed = true;
737783e9e51SPaolo Bonzini continue;
738783e9e51SPaolo Bonzini }
739783e9e51SPaolo Bonzini }
740783e9e51SPaolo Bonzini
741783e9e51SPaolo Bonzini /*
742783e9e51SPaolo Bonzini * 3) Potential reductions between the current and
743783e9e51SPaolo Bonzini * next nodes.
744783e9e51SPaolo Bonzini */
745783e9e51SPaolo Bonzini next = node_next(s, nodep);
746783e9e51SPaolo Bonzini if (next) {
747783e9e51SPaolo Bonzini /* Nodes with no bits set can be removed. */
748783e9e51SPaolo Bonzini if (next->mask == 0 && next->num_after == 0) {
749783e9e51SPaolo Bonzini node_rm(s, next);
750783e9e51SPaolo Bonzini reduction_performed = true;
751783e9e51SPaolo Bonzini continue;
752783e9e51SPaolo Bonzini }
753783e9e51SPaolo Bonzini
754783e9e51SPaolo Bonzini /*
755783e9e51SPaolo Bonzini * Is next node index adjacent to current node
756783e9e51SPaolo Bonzini * and has a mask with all bits set?
757783e9e51SPaolo Bonzini */
758783e9e51SPaolo Bonzini if (next->idx == nodep->idx + MASK_BITS + nodep->num_after &&
759783e9e51SPaolo Bonzini next->mask == ~(mask_t) 0) {
760783e9e51SPaolo Bonzini nodep->num_after += MASK_BITS;
761783e9e51SPaolo Bonzini next->mask = 0;
762783e9e51SPaolo Bonzini nodep->num_after += next->num_after;
763783e9e51SPaolo Bonzini next->num_after = 0;
764783e9e51SPaolo Bonzini
765783e9e51SPaolo Bonzini node_rm(s, next);
766783e9e51SPaolo Bonzini next = NULL;
767783e9e51SPaolo Bonzini
768783e9e51SPaolo Bonzini reduction_performed = true;
769783e9e51SPaolo Bonzini continue;
770783e9e51SPaolo Bonzini }
771783e9e51SPaolo Bonzini }
772783e9e51SPaolo Bonzini } while (nodep && reduction_performed);
773783e9e51SPaolo Bonzini }
774783e9e51SPaolo Bonzini
775783e9e51SPaolo Bonzini /* Returns whether the bit at the index given by idx, within the
776783e9e51SPaolo Bonzini * sparsebit array is set or not.
777783e9e51SPaolo Bonzini */
sparsebit_is_set(const struct sparsebit * s,sparsebit_idx_t idx)778*35f50c91SMichael Roth bool sparsebit_is_set(const struct sparsebit *s, sparsebit_idx_t idx)
779783e9e51SPaolo Bonzini {
780783e9e51SPaolo Bonzini struct node *nodep;
781783e9e51SPaolo Bonzini
782783e9e51SPaolo Bonzini /* Find the node that describes the setting of the bit at idx */
783783e9e51SPaolo Bonzini for (nodep = s->root; nodep;
784783e9e51SPaolo Bonzini nodep = nodep->idx > idx ? nodep->left : nodep->right)
785783e9e51SPaolo Bonzini if (idx >= nodep->idx &&
786783e9e51SPaolo Bonzini idx <= nodep->idx + MASK_BITS + nodep->num_after - 1)
787783e9e51SPaolo Bonzini goto have_node;
788783e9e51SPaolo Bonzini
789783e9e51SPaolo Bonzini return false;
790783e9e51SPaolo Bonzini
791783e9e51SPaolo Bonzini have_node:
792783e9e51SPaolo Bonzini /* Bit is set if it is any of the bits described by num_after */
793783e9e51SPaolo Bonzini if (nodep->num_after && idx >= nodep->idx + MASK_BITS)
794783e9e51SPaolo Bonzini return true;
795783e9e51SPaolo Bonzini
796783e9e51SPaolo Bonzini /* Is the corresponding mask bit set */
797783e9e51SPaolo Bonzini assert(idx >= nodep->idx && idx - nodep->idx < MASK_BITS);
798783e9e51SPaolo Bonzini return !!(nodep->mask & (1 << (idx - nodep->idx)));
799783e9e51SPaolo Bonzini }
800783e9e51SPaolo Bonzini
801783e9e51SPaolo Bonzini /* Within the sparsebit array pointed to by s, sets the bit
802783e9e51SPaolo Bonzini * at the index given by idx.
803783e9e51SPaolo Bonzini */
bit_set(struct sparsebit * s,sparsebit_idx_t idx)804783e9e51SPaolo Bonzini static void bit_set(struct sparsebit *s, sparsebit_idx_t idx)
805783e9e51SPaolo Bonzini {
806783e9e51SPaolo Bonzini struct node *nodep;
807783e9e51SPaolo Bonzini
808783e9e51SPaolo Bonzini /* Skip bits that are already set */
809783e9e51SPaolo Bonzini if (sparsebit_is_set(s, idx))
810783e9e51SPaolo Bonzini return;
811783e9e51SPaolo Bonzini
812783e9e51SPaolo Bonzini /*
813783e9e51SPaolo Bonzini * Get a node where the bit at idx is described by the mask.
814783e9e51SPaolo Bonzini * The node_split will also create a node, if there isn't
815783e9e51SPaolo Bonzini * already a node that describes the setting of bit.
816783e9e51SPaolo Bonzini */
817783e9e51SPaolo Bonzini nodep = node_split(s, idx & -MASK_BITS);
818783e9e51SPaolo Bonzini
819783e9e51SPaolo Bonzini /* Set the bit within the nodes mask */
820783e9e51SPaolo Bonzini assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1);
821783e9e51SPaolo Bonzini assert(!(nodep->mask & (1 << (idx - nodep->idx))));
822783e9e51SPaolo Bonzini nodep->mask |= 1 << (idx - nodep->idx);
823783e9e51SPaolo Bonzini s->num_set++;
824783e9e51SPaolo Bonzini
825783e9e51SPaolo Bonzini node_reduce(s, nodep);
826783e9e51SPaolo Bonzini }
827783e9e51SPaolo Bonzini
828783e9e51SPaolo Bonzini /* Within the sparsebit array pointed to by s, clears the bit
829783e9e51SPaolo Bonzini * at the index given by idx.
830783e9e51SPaolo Bonzini */
bit_clear(struct sparsebit * s,sparsebit_idx_t idx)831783e9e51SPaolo Bonzini static void bit_clear(struct sparsebit *s, sparsebit_idx_t idx)
832783e9e51SPaolo Bonzini {
833783e9e51SPaolo Bonzini struct node *nodep;
834783e9e51SPaolo Bonzini
835783e9e51SPaolo Bonzini /* Skip bits that are already cleared */
836783e9e51SPaolo Bonzini if (!sparsebit_is_set(s, idx))
837783e9e51SPaolo Bonzini return;
838783e9e51SPaolo Bonzini
839783e9e51SPaolo Bonzini /* Is there a node that describes the setting of this bit? */
840783e9e51SPaolo Bonzini nodep = node_find(s, idx);
841783e9e51SPaolo Bonzini if (!nodep)
842783e9e51SPaolo Bonzini return;
843783e9e51SPaolo Bonzini
844783e9e51SPaolo Bonzini /*
845783e9e51SPaolo Bonzini * If a num_after bit, split the node, so that the bit is
846783e9e51SPaolo Bonzini * part of a node mask.
847783e9e51SPaolo Bonzini */
848783e9e51SPaolo Bonzini if (idx >= nodep->idx + MASK_BITS)
849783e9e51SPaolo Bonzini nodep = node_split(s, idx & -MASK_BITS);
850783e9e51SPaolo Bonzini
851783e9e51SPaolo Bonzini /*
852783e9e51SPaolo Bonzini * After node_split above, bit at idx should be within the mask.
853783e9e51SPaolo Bonzini * Clear that bit.
854783e9e51SPaolo Bonzini */
855783e9e51SPaolo Bonzini assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1);
856783e9e51SPaolo Bonzini assert(nodep->mask & (1 << (idx - nodep->idx)));
857783e9e51SPaolo Bonzini nodep->mask &= ~(1 << (idx - nodep->idx));
858783e9e51SPaolo Bonzini assert(s->num_set > 0 || sparsebit_all_set(s));
859783e9e51SPaolo Bonzini s->num_set--;
860783e9e51SPaolo Bonzini
861783e9e51SPaolo Bonzini node_reduce(s, nodep);
862783e9e51SPaolo Bonzini }
863783e9e51SPaolo Bonzini
864783e9e51SPaolo Bonzini /* Recursively dumps to the FILE stream given by stream the contents
865783e9e51SPaolo Bonzini * of the sub-tree of nodes pointed to by nodep. Each line of output
866783e9e51SPaolo Bonzini * is prefixed by the number of spaces given by indent. On each
867783e9e51SPaolo Bonzini * recursion, the indent amount is increased by 2. This causes nodes
868783e9e51SPaolo Bonzini * at each level deeper into the binary search tree to be displayed
869783e9e51SPaolo Bonzini * with a greater indent.
870783e9e51SPaolo Bonzini */
dump_nodes(FILE * stream,struct node * nodep,unsigned int indent)871783e9e51SPaolo Bonzini static void dump_nodes(FILE *stream, struct node *nodep,
872783e9e51SPaolo Bonzini unsigned int indent)
873783e9e51SPaolo Bonzini {
874783e9e51SPaolo Bonzini char *node_type;
875783e9e51SPaolo Bonzini
876783e9e51SPaolo Bonzini /* Dump contents of node */
877783e9e51SPaolo Bonzini if (!nodep->parent)
878783e9e51SPaolo Bonzini node_type = "root";
879783e9e51SPaolo Bonzini else if (nodep == nodep->parent->left)
880783e9e51SPaolo Bonzini node_type = "left";
881783e9e51SPaolo Bonzini else {
882783e9e51SPaolo Bonzini assert(nodep == nodep->parent->right);
883783e9e51SPaolo Bonzini node_type = "right";
884783e9e51SPaolo Bonzini }
885783e9e51SPaolo Bonzini fprintf(stream, "%*s---- %s nodep: %p\n", indent, "", node_type, nodep);
886783e9e51SPaolo Bonzini fprintf(stream, "%*s parent: %p left: %p right: %p\n", indent, "",
887783e9e51SPaolo Bonzini nodep->parent, nodep->left, nodep->right);
888783e9e51SPaolo Bonzini fprintf(stream, "%*s idx: 0x%lx mask: 0x%x num_after: 0x%lx\n",
889783e9e51SPaolo Bonzini indent, "", nodep->idx, nodep->mask, nodep->num_after);
890783e9e51SPaolo Bonzini
891783e9e51SPaolo Bonzini /* If present, dump contents of left child nodes */
892783e9e51SPaolo Bonzini if (nodep->left)
893783e9e51SPaolo Bonzini dump_nodes(stream, nodep->left, indent + 2);
894783e9e51SPaolo Bonzini
895783e9e51SPaolo Bonzini /* If present, dump contents of right child nodes */
896783e9e51SPaolo Bonzini if (nodep->right)
897783e9e51SPaolo Bonzini dump_nodes(stream, nodep->right, indent + 2);
898783e9e51SPaolo Bonzini }
899783e9e51SPaolo Bonzini
node_first_set(struct node * nodep,int start)900783e9e51SPaolo Bonzini static inline sparsebit_idx_t node_first_set(struct node *nodep, int start)
901783e9e51SPaolo Bonzini {
902783e9e51SPaolo Bonzini mask_t leading = (mask_t)1 << start;
903783e9e51SPaolo Bonzini int n1 = __builtin_ctz(nodep->mask & -leading);
904783e9e51SPaolo Bonzini
905783e9e51SPaolo Bonzini return nodep->idx + n1;
906783e9e51SPaolo Bonzini }
907783e9e51SPaolo Bonzini
node_first_clear(struct node * nodep,int start)908783e9e51SPaolo Bonzini static inline sparsebit_idx_t node_first_clear(struct node *nodep, int start)
909783e9e51SPaolo Bonzini {
910783e9e51SPaolo Bonzini mask_t leading = (mask_t)1 << start;
911783e9e51SPaolo Bonzini int n1 = __builtin_ctz(~nodep->mask & -leading);
912783e9e51SPaolo Bonzini
913783e9e51SPaolo Bonzini return nodep->idx + n1;
914783e9e51SPaolo Bonzini }
915783e9e51SPaolo Bonzini
916783e9e51SPaolo Bonzini /* Dumps to the FILE stream specified by stream, the implementation dependent
917783e9e51SPaolo Bonzini * internal state of s. Each line of output is prefixed with the number
918783e9e51SPaolo Bonzini * of spaces given by indent. The output is completely implementation
919783e9e51SPaolo Bonzini * dependent and subject to change. Output from this function should only
920783e9e51SPaolo Bonzini * be used for diagnostic purposes. For example, this function can be
921783e9e51SPaolo Bonzini * used by test cases after they detect an unexpected condition, as a means
922783e9e51SPaolo Bonzini * to capture diagnostic information.
923783e9e51SPaolo Bonzini */
sparsebit_dump_internal(FILE * stream,const struct sparsebit * s,unsigned int indent)924*35f50c91SMichael Roth static void sparsebit_dump_internal(FILE *stream, const struct sparsebit *s,
925783e9e51SPaolo Bonzini unsigned int indent)
926783e9e51SPaolo Bonzini {
927783e9e51SPaolo Bonzini /* Dump the contents of s */
928783e9e51SPaolo Bonzini fprintf(stream, "%*sroot: %p\n", indent, "", s->root);
929783e9e51SPaolo Bonzini fprintf(stream, "%*snum_set: 0x%lx\n", indent, "", s->num_set);
930783e9e51SPaolo Bonzini
931783e9e51SPaolo Bonzini if (s->root)
932783e9e51SPaolo Bonzini dump_nodes(stream, s->root, indent);
933783e9e51SPaolo Bonzini }
934783e9e51SPaolo Bonzini
935783e9e51SPaolo Bonzini /* Allocates and returns a new sparsebit array. The initial state
936783e9e51SPaolo Bonzini * of the newly allocated sparsebit array has all bits cleared.
937783e9e51SPaolo Bonzini */
sparsebit_alloc(void)938783e9e51SPaolo Bonzini struct sparsebit *sparsebit_alloc(void)
939783e9e51SPaolo Bonzini {
940783e9e51SPaolo Bonzini struct sparsebit *s;
941783e9e51SPaolo Bonzini
942783e9e51SPaolo Bonzini /* Allocate top level structure. */
943783e9e51SPaolo Bonzini s = calloc(1, sizeof(*s));
944783e9e51SPaolo Bonzini if (!s) {
945783e9e51SPaolo Bonzini perror("calloc");
946783e9e51SPaolo Bonzini abort();
947783e9e51SPaolo Bonzini }
948783e9e51SPaolo Bonzini
949783e9e51SPaolo Bonzini return s;
950783e9e51SPaolo Bonzini }
951783e9e51SPaolo Bonzini
952783e9e51SPaolo Bonzini /* Frees the implementation dependent data for the sparsebit array
953783e9e51SPaolo Bonzini * pointed to by s and poisons the pointer to that data.
954783e9e51SPaolo Bonzini */
sparsebit_free(struct sparsebit ** sbitp)955783e9e51SPaolo Bonzini void sparsebit_free(struct sparsebit **sbitp)
956783e9e51SPaolo Bonzini {
957783e9e51SPaolo Bonzini struct sparsebit *s = *sbitp;
958783e9e51SPaolo Bonzini
959783e9e51SPaolo Bonzini if (!s)
960783e9e51SPaolo Bonzini return;
961783e9e51SPaolo Bonzini
962783e9e51SPaolo Bonzini sparsebit_clear_all(s);
963783e9e51SPaolo Bonzini free(s);
964783e9e51SPaolo Bonzini *sbitp = NULL;
965783e9e51SPaolo Bonzini }
966783e9e51SPaolo Bonzini
967783e9e51SPaolo Bonzini /* Makes a copy of the sparsebit array given by s, to the sparsebit
968783e9e51SPaolo Bonzini * array given by d. Note, d must have already been allocated via
969783e9e51SPaolo Bonzini * sparsebit_alloc(). It can though already have bits set, which
970783e9e51SPaolo Bonzini * if different from src will be cleared.
971783e9e51SPaolo Bonzini */
sparsebit_copy(struct sparsebit * d,const struct sparsebit * s)972*35f50c91SMichael Roth void sparsebit_copy(struct sparsebit *d, const struct sparsebit *s)
973783e9e51SPaolo Bonzini {
974783e9e51SPaolo Bonzini /* First clear any bits already set in the destination */
975783e9e51SPaolo Bonzini sparsebit_clear_all(d);
976783e9e51SPaolo Bonzini
977783e9e51SPaolo Bonzini if (s->root) {
978783e9e51SPaolo Bonzini d->root = node_copy_subtree(s->root);
979783e9e51SPaolo Bonzini d->num_set = s->num_set;
980783e9e51SPaolo Bonzini }
981783e9e51SPaolo Bonzini }
982783e9e51SPaolo Bonzini
983783e9e51SPaolo Bonzini /* 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*35f50c91SMichael Roth bool sparsebit_is_set_num(const struct sparsebit *s,
985783e9e51SPaolo Bonzini sparsebit_idx_t idx, sparsebit_num_t num)
986783e9e51SPaolo Bonzini {
987783e9e51SPaolo Bonzini sparsebit_idx_t next_cleared;
988783e9e51SPaolo Bonzini
989783e9e51SPaolo Bonzini assert(num > 0);
990783e9e51SPaolo Bonzini assert(idx + num - 1 >= idx);
991783e9e51SPaolo Bonzini
992783e9e51SPaolo Bonzini /* With num > 0, the first bit must be set. */
993783e9e51SPaolo Bonzini if (!sparsebit_is_set(s, idx))
994783e9e51SPaolo Bonzini return false;
995783e9e51SPaolo Bonzini
996783e9e51SPaolo Bonzini /* Find the next cleared bit */
997783e9e51SPaolo Bonzini next_cleared = sparsebit_next_clear(s, idx);
998783e9e51SPaolo Bonzini
999783e9e51SPaolo Bonzini /*
1000783e9e51SPaolo Bonzini * If no cleared bits beyond idx, then there are at least num
1001783e9e51SPaolo Bonzini * set bits. idx + num doesn't wrap. Otherwise check if
1002783e9e51SPaolo Bonzini * there are enough set bits between idx and the next cleared bit.
1003783e9e51SPaolo Bonzini */
1004783e9e51SPaolo Bonzini return next_cleared == 0 || next_cleared - idx >= num;
1005783e9e51SPaolo Bonzini }
1006783e9e51SPaolo Bonzini
1007783e9e51SPaolo Bonzini /* Returns whether the bit at the index given by idx. */
sparsebit_is_clear(const struct sparsebit * s,sparsebit_idx_t idx)1008*35f50c91SMichael Roth bool sparsebit_is_clear(const struct sparsebit *s,
1009783e9e51SPaolo Bonzini sparsebit_idx_t idx)
1010783e9e51SPaolo Bonzini {
1011783e9e51SPaolo Bonzini return !sparsebit_is_set(s, idx);
1012783e9e51SPaolo Bonzini }
1013783e9e51SPaolo Bonzini
1014783e9e51SPaolo Bonzini /* 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*35f50c91SMichael Roth bool sparsebit_is_clear_num(const struct sparsebit *s,
1016783e9e51SPaolo Bonzini sparsebit_idx_t idx, sparsebit_num_t num)
1017783e9e51SPaolo Bonzini {
1018783e9e51SPaolo Bonzini sparsebit_idx_t next_set;
1019783e9e51SPaolo Bonzini
1020783e9e51SPaolo Bonzini assert(num > 0);
1021783e9e51SPaolo Bonzini assert(idx + num - 1 >= idx);
1022783e9e51SPaolo Bonzini
1023783e9e51SPaolo Bonzini /* With num > 0, the first bit must be cleared. */
1024783e9e51SPaolo Bonzini if (!sparsebit_is_clear(s, idx))
1025783e9e51SPaolo Bonzini return false;
1026783e9e51SPaolo Bonzini
1027783e9e51SPaolo Bonzini /* Find the next set bit */
1028783e9e51SPaolo Bonzini next_set = sparsebit_next_set(s, idx);
1029783e9e51SPaolo Bonzini
1030783e9e51SPaolo Bonzini /*
1031783e9e51SPaolo Bonzini * If no set bits beyond idx, then there are at least num
1032783e9e51SPaolo Bonzini * cleared bits. idx + num doesn't wrap. Otherwise check if
1033783e9e51SPaolo Bonzini * there are enough cleared bits between idx and the next set bit.
1034783e9e51SPaolo Bonzini */
1035783e9e51SPaolo Bonzini return next_set == 0 || next_set - idx >= num;
1036783e9e51SPaolo Bonzini }
1037783e9e51SPaolo Bonzini
1038783e9e51SPaolo Bonzini /* Returns the total number of bits set. Note: 0 is also returned for
1039783e9e51SPaolo Bonzini * the case of all bits set. This is because with all bits set, there
1040783e9e51SPaolo Bonzini * is 1 additional bit set beyond what can be represented in the return
1041783e9e51SPaolo Bonzini * value. Use sparsebit_any_set(), instead of sparsebit_num_set() > 0,
1042783e9e51SPaolo Bonzini * to determine if the sparsebit array has any bits set.
1043783e9e51SPaolo Bonzini */
sparsebit_num_set(const struct sparsebit * s)1044*35f50c91SMichael Roth sparsebit_num_t sparsebit_num_set(const struct sparsebit *s)
1045783e9e51SPaolo Bonzini {
1046783e9e51SPaolo Bonzini return s->num_set;
1047783e9e51SPaolo Bonzini }
1048783e9e51SPaolo Bonzini
1049783e9e51SPaolo Bonzini /* Returns whether any bit is set in the sparsebit array. */
sparsebit_any_set(const struct sparsebit * s)1050*35f50c91SMichael Roth bool sparsebit_any_set(const struct sparsebit *s)
1051783e9e51SPaolo Bonzini {
1052783e9e51SPaolo Bonzini /*
1053783e9e51SPaolo Bonzini * Nodes only describe set bits. If any nodes then there
1054783e9e51SPaolo Bonzini * is at least 1 bit set.
1055783e9e51SPaolo Bonzini */
1056783e9e51SPaolo Bonzini if (!s->root)
1057783e9e51SPaolo Bonzini return false;
1058783e9e51SPaolo Bonzini
1059783e9e51SPaolo Bonzini /*
1060783e9e51SPaolo Bonzini * Every node should have a non-zero mask. For now will
1061783e9e51SPaolo Bonzini * just assure that the root node has a non-zero mask,
1062783e9e51SPaolo Bonzini * which is a quick check that at least 1 bit is set.
1063783e9e51SPaolo Bonzini */
1064783e9e51SPaolo Bonzini assert(s->root->mask != 0);
1065783e9e51SPaolo Bonzini assert(s->num_set > 0 ||
1066783e9e51SPaolo Bonzini (s->root->num_after == ((sparsebit_num_t) 0) - MASK_BITS &&
1067783e9e51SPaolo Bonzini s->root->mask == ~(mask_t) 0));
1068783e9e51SPaolo Bonzini
1069783e9e51SPaolo Bonzini return true;
1070783e9e51SPaolo Bonzini }
1071783e9e51SPaolo Bonzini
1072783e9e51SPaolo Bonzini /* Returns whether all the bits in the sparsebit array are cleared. */
sparsebit_all_clear(const struct sparsebit * s)1073*35f50c91SMichael Roth bool sparsebit_all_clear(const struct sparsebit *s)
1074783e9e51SPaolo Bonzini {
1075783e9e51SPaolo Bonzini return !sparsebit_any_set(s);
1076783e9e51SPaolo Bonzini }
1077783e9e51SPaolo Bonzini
1078783e9e51SPaolo Bonzini /* Returns whether all the bits in the sparsebit array are set. */
sparsebit_any_clear(const struct sparsebit * s)1079*35f50c91SMichael Roth bool sparsebit_any_clear(const struct sparsebit *s)
1080783e9e51SPaolo Bonzini {
1081783e9e51SPaolo Bonzini return !sparsebit_all_set(s);
1082783e9e51SPaolo Bonzini }
1083783e9e51SPaolo Bonzini
1084783e9e51SPaolo Bonzini /* Returns the index of the first set bit. Abort if no bits are set.
1085783e9e51SPaolo Bonzini */
sparsebit_first_set(const struct sparsebit * s)1086*35f50c91SMichael Roth sparsebit_idx_t sparsebit_first_set(const struct sparsebit *s)
1087783e9e51SPaolo Bonzini {
1088783e9e51SPaolo Bonzini struct node *nodep;
1089783e9e51SPaolo Bonzini
1090783e9e51SPaolo Bonzini /* Validate at least 1 bit is set */
1091783e9e51SPaolo Bonzini assert(sparsebit_any_set(s));
1092783e9e51SPaolo Bonzini
1093783e9e51SPaolo Bonzini nodep = node_first(s);
1094783e9e51SPaolo Bonzini return node_first_set(nodep, 0);
1095783e9e51SPaolo Bonzini }
1096783e9e51SPaolo Bonzini
1097783e9e51SPaolo Bonzini /* Returns the index of the first cleared bit. Abort if
1098783e9e51SPaolo Bonzini * no bits are cleared.
1099783e9e51SPaolo Bonzini */
sparsebit_first_clear(const struct sparsebit * s)1100*35f50c91SMichael Roth sparsebit_idx_t sparsebit_first_clear(const struct sparsebit *s)
1101783e9e51SPaolo Bonzini {
1102783e9e51SPaolo Bonzini struct node *nodep1, *nodep2;
1103783e9e51SPaolo Bonzini
1104783e9e51SPaolo Bonzini /* Validate at least 1 bit is cleared. */
1105783e9e51SPaolo Bonzini assert(sparsebit_any_clear(s));
1106783e9e51SPaolo Bonzini
1107783e9e51SPaolo Bonzini /* If no nodes or first node index > 0 then lowest cleared is 0 */
1108783e9e51SPaolo Bonzini nodep1 = node_first(s);
1109783e9e51SPaolo Bonzini if (!nodep1 || nodep1->idx > 0)
1110783e9e51SPaolo Bonzini return 0;
1111783e9e51SPaolo Bonzini
1112783e9e51SPaolo Bonzini /* Does the mask in the first node contain any cleared bits. */
1113783e9e51SPaolo Bonzini if (nodep1->mask != ~(mask_t) 0)
1114783e9e51SPaolo Bonzini return node_first_clear(nodep1, 0);
1115783e9e51SPaolo Bonzini
1116783e9e51SPaolo Bonzini /*
1117783e9e51SPaolo Bonzini * All mask bits set in first node. If there isn't a second node
1118783e9e51SPaolo Bonzini * then the first cleared bit is the first bit after the bits
1119783e9e51SPaolo Bonzini * described by the first node.
1120783e9e51SPaolo Bonzini */
1121783e9e51SPaolo Bonzini nodep2 = node_next(s, nodep1);
1122783e9e51SPaolo Bonzini if (!nodep2) {
1123783e9e51SPaolo Bonzini /*
1124783e9e51SPaolo Bonzini * No second node. First cleared bit is first bit beyond
1125783e9e51SPaolo Bonzini * bits described by first node.
1126783e9e51SPaolo Bonzini */
1127783e9e51SPaolo Bonzini assert(nodep1->mask == ~(mask_t) 0);
1128783e9e51SPaolo Bonzini assert(nodep1->idx + MASK_BITS + nodep1->num_after != (sparsebit_idx_t) 0);
1129783e9e51SPaolo Bonzini return nodep1->idx + MASK_BITS + nodep1->num_after;
1130783e9e51SPaolo Bonzini }
1131783e9e51SPaolo Bonzini
1132783e9e51SPaolo Bonzini /*
1133783e9e51SPaolo Bonzini * There is a second node.
1134783e9e51SPaolo Bonzini * If it is not adjacent to the first node, then there is a gap
1135783e9e51SPaolo Bonzini * of cleared bits between the nodes, and the first cleared bit
1136783e9e51SPaolo Bonzini * is the first bit within the gap.
1137783e9e51SPaolo Bonzini */
1138783e9e51SPaolo Bonzini if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx)
1139783e9e51SPaolo Bonzini return nodep1->idx + MASK_BITS + nodep1->num_after;
1140783e9e51SPaolo Bonzini
1141783e9e51SPaolo Bonzini /*
1142783e9e51SPaolo Bonzini * Second node is adjacent to the first node.
1143783e9e51SPaolo Bonzini * Because it is adjacent, its mask should be non-zero. If all
1144783e9e51SPaolo Bonzini * its mask bits are set, then with it being adjacent, it should
1145783e9e51SPaolo Bonzini * have had the mask bits moved into the num_after setting of the
1146783e9e51SPaolo Bonzini * previous node.
1147783e9e51SPaolo Bonzini */
1148783e9e51SPaolo Bonzini return node_first_clear(nodep2, 0);
1149783e9e51SPaolo Bonzini }
1150783e9e51SPaolo Bonzini
1151783e9e51SPaolo Bonzini /* Returns index of next bit set within s after the index given by prev.
1152783e9e51SPaolo Bonzini * Returns 0 if there are no bits after prev that are set.
1153783e9e51SPaolo Bonzini */
sparsebit_next_set(const struct sparsebit * s,sparsebit_idx_t prev)1154*35f50c91SMichael Roth sparsebit_idx_t sparsebit_next_set(const struct sparsebit *s,
1155783e9e51SPaolo Bonzini sparsebit_idx_t prev)
1156783e9e51SPaolo Bonzini {
1157783e9e51SPaolo Bonzini sparsebit_idx_t lowest_possible = prev + 1;
1158783e9e51SPaolo Bonzini sparsebit_idx_t start;
1159783e9e51SPaolo Bonzini struct node *nodep;
1160783e9e51SPaolo Bonzini
1161783e9e51SPaolo Bonzini /* A bit after the highest index can't be set. */
1162783e9e51SPaolo Bonzini if (lowest_possible == 0)
1163783e9e51SPaolo Bonzini return 0;
1164783e9e51SPaolo Bonzini
1165783e9e51SPaolo Bonzini /*
1166783e9e51SPaolo Bonzini * Find the leftmost 'candidate' overlapping or to the right
1167783e9e51SPaolo Bonzini * of lowest_possible.
1168783e9e51SPaolo Bonzini */
1169783e9e51SPaolo Bonzini struct node *candidate = NULL;
1170783e9e51SPaolo Bonzini
1171783e9e51SPaolo Bonzini /* True iff lowest_possible is within candidate */
1172783e9e51SPaolo Bonzini bool contains = false;
1173783e9e51SPaolo Bonzini
1174783e9e51SPaolo Bonzini /*
1175783e9e51SPaolo Bonzini * Find node that describes setting of bit at lowest_possible.
1176783e9e51SPaolo Bonzini * If such a node doesn't exist, find the node with the lowest
1177783e9e51SPaolo Bonzini * starting index that is > lowest_possible.
1178783e9e51SPaolo Bonzini */
1179783e9e51SPaolo Bonzini for (nodep = s->root; nodep;) {
1180783e9e51SPaolo Bonzini if ((nodep->idx + MASK_BITS + nodep->num_after - 1)
1181783e9e51SPaolo Bonzini >= lowest_possible) {
1182783e9e51SPaolo Bonzini candidate = nodep;
1183783e9e51SPaolo Bonzini if (candidate->idx <= lowest_possible) {
1184783e9e51SPaolo Bonzini contains = true;
1185783e9e51SPaolo Bonzini break;
1186783e9e51SPaolo Bonzini }
1187783e9e51SPaolo Bonzini nodep = nodep->left;
1188783e9e51SPaolo Bonzini } else {
1189783e9e51SPaolo Bonzini nodep = nodep->right;
1190783e9e51SPaolo Bonzini }
1191783e9e51SPaolo Bonzini }
1192783e9e51SPaolo Bonzini if (!candidate)
1193783e9e51SPaolo Bonzini return 0;
1194783e9e51SPaolo Bonzini
1195783e9e51SPaolo Bonzini assert(candidate->mask != 0);
1196783e9e51SPaolo Bonzini
1197783e9e51SPaolo Bonzini /* Does the candidate node describe the setting of lowest_possible? */
1198783e9e51SPaolo Bonzini if (!contains) {
1199783e9e51SPaolo Bonzini /*
1200783e9e51SPaolo Bonzini * Candidate doesn't describe setting of bit at lowest_possible.
1201783e9e51SPaolo Bonzini * Candidate points to the first node with a starting index
1202783e9e51SPaolo Bonzini * > lowest_possible.
1203783e9e51SPaolo Bonzini */
1204783e9e51SPaolo Bonzini assert(candidate->idx > lowest_possible);
1205783e9e51SPaolo Bonzini
1206783e9e51SPaolo Bonzini return node_first_set(candidate, 0);
1207783e9e51SPaolo Bonzini }
1208783e9e51SPaolo Bonzini
1209783e9e51SPaolo Bonzini /*
1210783e9e51SPaolo Bonzini * Candidate describes setting of bit at lowest_possible.
1211783e9e51SPaolo Bonzini * Note: although the node describes the setting of the bit
1212783e9e51SPaolo Bonzini * at lowest_possible, its possible that its setting and the
1213783e9e51SPaolo Bonzini * setting of all latter bits described by this node are 0.
1214783e9e51SPaolo Bonzini * For now, just handle the cases where this node describes
1215783e9e51SPaolo Bonzini * a bit at or after an index of lowest_possible that is set.
1216783e9e51SPaolo Bonzini */
1217783e9e51SPaolo Bonzini start = lowest_possible - candidate->idx;
1218783e9e51SPaolo Bonzini
1219783e9e51SPaolo Bonzini if (start < MASK_BITS && candidate->mask >= (1 << start))
1220783e9e51SPaolo Bonzini return node_first_set(candidate, start);
1221783e9e51SPaolo Bonzini
1222783e9e51SPaolo Bonzini if (candidate->num_after) {
1223783e9e51SPaolo Bonzini sparsebit_idx_t first_num_after_idx = candidate->idx + MASK_BITS;
1224783e9e51SPaolo Bonzini
1225783e9e51SPaolo Bonzini return lowest_possible < first_num_after_idx
1226783e9e51SPaolo Bonzini ? first_num_after_idx : lowest_possible;
1227783e9e51SPaolo Bonzini }
1228783e9e51SPaolo Bonzini
1229783e9e51SPaolo Bonzini /*
1230783e9e51SPaolo Bonzini * Although candidate node describes setting of bit at
1231783e9e51SPaolo Bonzini * the index of lowest_possible, all bits at that index and
1232783e9e51SPaolo Bonzini * latter that are described by candidate are cleared. With
1233783e9e51SPaolo Bonzini * this, the next bit is the first bit in the next node, if
1234783e9e51SPaolo Bonzini * such a node exists. If a next node doesn't exist, then
1235783e9e51SPaolo Bonzini * there is no next set bit.
1236783e9e51SPaolo Bonzini */
1237783e9e51SPaolo Bonzini candidate = node_next(s, candidate);
1238783e9e51SPaolo Bonzini if (!candidate)
1239783e9e51SPaolo Bonzini return 0;
1240783e9e51SPaolo Bonzini
1241783e9e51SPaolo Bonzini return node_first_set(candidate, 0);
1242783e9e51SPaolo Bonzini }
1243783e9e51SPaolo Bonzini
1244783e9e51SPaolo Bonzini /* Returns index of next bit cleared within s after the index given by prev.
1245783e9e51SPaolo Bonzini * Returns 0 if there are no bits after prev that are cleared.
1246783e9e51SPaolo Bonzini */
sparsebit_next_clear(const struct sparsebit * s,sparsebit_idx_t prev)1247*35f50c91SMichael Roth sparsebit_idx_t sparsebit_next_clear(const struct sparsebit *s,
1248783e9e51SPaolo Bonzini sparsebit_idx_t prev)
1249783e9e51SPaolo Bonzini {
1250783e9e51SPaolo Bonzini sparsebit_idx_t lowest_possible = prev + 1;
1251783e9e51SPaolo Bonzini sparsebit_idx_t idx;
1252783e9e51SPaolo Bonzini struct node *nodep1, *nodep2;
1253783e9e51SPaolo Bonzini
1254783e9e51SPaolo Bonzini /* A bit after the highest index can't be set. */
1255783e9e51SPaolo Bonzini if (lowest_possible == 0)
1256783e9e51SPaolo Bonzini return 0;
1257783e9e51SPaolo Bonzini
1258783e9e51SPaolo Bonzini /*
1259783e9e51SPaolo Bonzini * Does a node describing the setting of lowest_possible exist?
1260783e9e51SPaolo Bonzini * If not, the bit at lowest_possible is cleared.
1261783e9e51SPaolo Bonzini */
1262783e9e51SPaolo Bonzini nodep1 = node_find(s, lowest_possible);
1263783e9e51SPaolo Bonzini if (!nodep1)
1264783e9e51SPaolo Bonzini return lowest_possible;
1265783e9e51SPaolo Bonzini
1266783e9e51SPaolo Bonzini /* Does a mask bit in node 1 describe the next cleared bit. */
1267783e9e51SPaolo Bonzini for (idx = lowest_possible - nodep1->idx; idx < MASK_BITS; idx++)
1268783e9e51SPaolo Bonzini if (!(nodep1->mask & (1 << idx)))
1269783e9e51SPaolo Bonzini return nodep1->idx + idx;
1270783e9e51SPaolo Bonzini
1271783e9e51SPaolo Bonzini /*
1272783e9e51SPaolo Bonzini * Next cleared bit is not described by node 1. If there
1273783e9e51SPaolo Bonzini * isn't a next node, then next cleared bit is described
1274783e9e51SPaolo Bonzini * by bit after the bits described by the first node.
1275783e9e51SPaolo Bonzini */
1276783e9e51SPaolo Bonzini nodep2 = node_next(s, nodep1);
1277783e9e51SPaolo Bonzini if (!nodep2)
1278783e9e51SPaolo Bonzini return nodep1->idx + MASK_BITS + nodep1->num_after;
1279783e9e51SPaolo Bonzini
1280783e9e51SPaolo Bonzini /*
1281783e9e51SPaolo Bonzini * There is a second node.
1282783e9e51SPaolo Bonzini * If it is not adjacent to the first node, then there is a gap
1283783e9e51SPaolo Bonzini * of cleared bits between the nodes, and the next cleared bit
1284783e9e51SPaolo Bonzini * is the first bit within the gap.
1285783e9e51SPaolo Bonzini */
1286783e9e51SPaolo Bonzini if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx)
1287783e9e51SPaolo Bonzini return nodep1->idx + MASK_BITS + nodep1->num_after;
1288783e9e51SPaolo Bonzini
1289783e9e51SPaolo Bonzini /*
1290783e9e51SPaolo Bonzini * Second node is adjacent to the first node.
1291783e9e51SPaolo Bonzini * Because it is adjacent, its mask should be non-zero. If all
1292783e9e51SPaolo Bonzini * its mask bits are set, then with it being adjacent, it should
1293783e9e51SPaolo Bonzini * have had the mask bits moved into the num_after setting of the
1294783e9e51SPaolo Bonzini * previous node.
1295783e9e51SPaolo Bonzini */
1296783e9e51SPaolo Bonzini return node_first_clear(nodep2, 0);
1297783e9e51SPaolo Bonzini }
1298783e9e51SPaolo Bonzini
1299783e9e51SPaolo Bonzini /* Starting with the index 1 greater than the index given by start, finds
1300783e9e51SPaolo Bonzini * and returns the index of the first sequence of num consecutively set
1301783e9e51SPaolo Bonzini * bits. Returns a value of 0 of no such sequence exists.
1302783e9e51SPaolo Bonzini */
sparsebit_next_set_num(const struct sparsebit * s,sparsebit_idx_t start,sparsebit_num_t num)1303*35f50c91SMichael Roth sparsebit_idx_t sparsebit_next_set_num(const struct sparsebit *s,
1304783e9e51SPaolo Bonzini sparsebit_idx_t start, sparsebit_num_t num)
1305783e9e51SPaolo Bonzini {
1306783e9e51SPaolo Bonzini sparsebit_idx_t idx;
1307783e9e51SPaolo Bonzini
1308783e9e51SPaolo Bonzini assert(num >= 1);
1309783e9e51SPaolo Bonzini
1310783e9e51SPaolo Bonzini for (idx = sparsebit_next_set(s, start);
1311783e9e51SPaolo Bonzini idx != 0 && idx + num - 1 >= idx;
1312783e9e51SPaolo Bonzini idx = sparsebit_next_set(s, idx)) {
1313783e9e51SPaolo Bonzini assert(sparsebit_is_set(s, idx));
1314783e9e51SPaolo Bonzini
1315783e9e51SPaolo Bonzini /*
1316783e9e51SPaolo Bonzini * Does the sequence of bits starting at idx consist of
1317783e9e51SPaolo Bonzini * num set bits?
1318783e9e51SPaolo Bonzini */
1319783e9e51SPaolo Bonzini if (sparsebit_is_set_num(s, idx, num))
1320783e9e51SPaolo Bonzini return idx;
1321783e9e51SPaolo Bonzini
1322783e9e51SPaolo Bonzini /*
1323783e9e51SPaolo Bonzini * Sequence of set bits at idx isn't large enough.
1324783e9e51SPaolo Bonzini * Skip this entire sequence of set bits.
1325783e9e51SPaolo Bonzini */
1326783e9e51SPaolo Bonzini idx = sparsebit_next_clear(s, idx);
1327783e9e51SPaolo Bonzini if (idx == 0)
1328783e9e51SPaolo Bonzini return 0;
1329783e9e51SPaolo Bonzini }
1330783e9e51SPaolo Bonzini
1331783e9e51SPaolo Bonzini return 0;
1332783e9e51SPaolo Bonzini }
1333783e9e51SPaolo Bonzini
1334783e9e51SPaolo Bonzini /* Starting with the index 1 greater than the index given by start, finds
1335783e9e51SPaolo Bonzini * and returns the index of the first sequence of num consecutively cleared
1336783e9e51SPaolo Bonzini * bits. Returns a value of 0 of no such sequence exists.
1337783e9e51SPaolo Bonzini */
sparsebit_next_clear_num(const struct sparsebit * s,sparsebit_idx_t start,sparsebit_num_t num)1338*35f50c91SMichael Roth sparsebit_idx_t sparsebit_next_clear_num(const struct sparsebit *s,
1339783e9e51SPaolo Bonzini sparsebit_idx_t start, sparsebit_num_t num)
1340783e9e51SPaolo Bonzini {
1341783e9e51SPaolo Bonzini sparsebit_idx_t idx;
1342783e9e51SPaolo Bonzini
1343783e9e51SPaolo Bonzini assert(num >= 1);
1344783e9e51SPaolo Bonzini
1345783e9e51SPaolo Bonzini for (idx = sparsebit_next_clear(s, start);
1346783e9e51SPaolo Bonzini idx != 0 && idx + num - 1 >= idx;
1347783e9e51SPaolo Bonzini idx = sparsebit_next_clear(s, idx)) {
1348783e9e51SPaolo Bonzini assert(sparsebit_is_clear(s, idx));
1349783e9e51SPaolo Bonzini
1350783e9e51SPaolo Bonzini /*
1351783e9e51SPaolo Bonzini * Does the sequence of bits starting at idx consist of
1352783e9e51SPaolo Bonzini * num cleared bits?
1353783e9e51SPaolo Bonzini */
1354783e9e51SPaolo Bonzini if (sparsebit_is_clear_num(s, idx, num))
1355783e9e51SPaolo Bonzini return idx;
1356783e9e51SPaolo Bonzini
1357783e9e51SPaolo Bonzini /*
1358783e9e51SPaolo Bonzini * Sequence of cleared bits at idx isn't large enough.
1359783e9e51SPaolo Bonzini * Skip this entire sequence of cleared bits.
1360783e9e51SPaolo Bonzini */
1361783e9e51SPaolo Bonzini idx = sparsebit_next_set(s, idx);
1362783e9e51SPaolo Bonzini if (idx == 0)
1363783e9e51SPaolo Bonzini return 0;
1364783e9e51SPaolo Bonzini }
1365783e9e51SPaolo Bonzini
1366783e9e51SPaolo Bonzini return 0;
1367783e9e51SPaolo Bonzini }
1368783e9e51SPaolo Bonzini
1369783e9e51SPaolo Bonzini /* 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)1370783e9e51SPaolo Bonzini void sparsebit_set_num(struct sparsebit *s,
1371783e9e51SPaolo Bonzini sparsebit_idx_t start, sparsebit_num_t num)
1372783e9e51SPaolo Bonzini {
1373783e9e51SPaolo Bonzini struct node *nodep, *next;
1374783e9e51SPaolo Bonzini unsigned int n1;
1375783e9e51SPaolo Bonzini sparsebit_idx_t idx;
1376783e9e51SPaolo Bonzini sparsebit_num_t n;
1377783e9e51SPaolo Bonzini sparsebit_idx_t middle_start, middle_end;
1378783e9e51SPaolo Bonzini
1379783e9e51SPaolo Bonzini assert(num > 0);
1380783e9e51SPaolo Bonzini assert(start + num - 1 >= start);
1381783e9e51SPaolo Bonzini
1382783e9e51SPaolo Bonzini /*
1383783e9e51SPaolo Bonzini * Leading - bits before first mask boundary.
1384783e9e51SPaolo Bonzini *
1385783e9e51SPaolo Bonzini * TODO(lhuemill): With some effort it may be possible to
1386783e9e51SPaolo Bonzini * replace the following loop with a sequential sequence
1387783e9e51SPaolo Bonzini * of statements. High level sequence would be:
1388783e9e51SPaolo Bonzini *
1389783e9e51SPaolo Bonzini * 1. Use node_split() to force node that describes setting
1390783e9e51SPaolo Bonzini * of idx to be within the mask portion of a node.
1391783e9e51SPaolo Bonzini * 2. Form mask of bits to be set.
1392783e9e51SPaolo Bonzini * 3. Determine number of mask bits already set in the node
1393783e9e51SPaolo Bonzini * and store in a local variable named num_already_set.
1394783e9e51SPaolo Bonzini * 4. Set the appropriate mask bits within the node.
1395783e9e51SPaolo Bonzini * 5. Increment struct sparsebit_pvt num_set member
1396783e9e51SPaolo Bonzini * by the number of bits that were actually set.
1397783e9e51SPaolo Bonzini * Exclude from the counts bits that were already set.
1398783e9e51SPaolo Bonzini * 6. Before returning to the caller, use node_reduce() to
1399783e9e51SPaolo Bonzini * handle the multiple corner cases that this method
1400783e9e51SPaolo Bonzini * introduces.
1401783e9e51SPaolo Bonzini */
1402783e9e51SPaolo Bonzini for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--)
1403783e9e51SPaolo Bonzini bit_set(s, idx);
1404783e9e51SPaolo Bonzini
1405783e9e51SPaolo Bonzini /* Middle - bits spanning one or more entire mask */
1406783e9e51SPaolo Bonzini middle_start = idx;
1407783e9e51SPaolo Bonzini middle_end = middle_start + (n & -MASK_BITS) - 1;
1408783e9e51SPaolo Bonzini if (n >= MASK_BITS) {
1409783e9e51SPaolo Bonzini nodep = node_split(s, middle_start);
1410783e9e51SPaolo Bonzini
1411783e9e51SPaolo Bonzini /*
1412783e9e51SPaolo Bonzini * As needed, split just after end of middle bits.
1413783e9e51SPaolo Bonzini * No split needed if end of middle bits is at highest
1414783e9e51SPaolo Bonzini * supported bit index.
1415783e9e51SPaolo Bonzini */
1416783e9e51SPaolo Bonzini if (middle_end + 1 > middle_end)
1417783e9e51SPaolo Bonzini (void) node_split(s, middle_end + 1);
1418783e9e51SPaolo Bonzini
1419783e9e51SPaolo Bonzini /* Delete nodes that only describe bits within the middle. */
1420783e9e51SPaolo Bonzini for (next = node_next(s, nodep);
1421783e9e51SPaolo Bonzini next && (next->idx < middle_end);
1422783e9e51SPaolo Bonzini next = node_next(s, nodep)) {
1423783e9e51SPaolo Bonzini assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end);
1424783e9e51SPaolo Bonzini node_rm(s, next);
1425783e9e51SPaolo Bonzini next = NULL;
1426783e9e51SPaolo Bonzini }
1427783e9e51SPaolo Bonzini
1428783e9e51SPaolo Bonzini /* As needed set each of the mask bits */
1429783e9e51SPaolo Bonzini for (n1 = 0; n1 < MASK_BITS; n1++) {
1430783e9e51SPaolo Bonzini if (!(nodep->mask & (1 << n1))) {
1431783e9e51SPaolo Bonzini nodep->mask |= 1 << n1;
1432783e9e51SPaolo Bonzini s->num_set++;
1433783e9e51SPaolo Bonzini }
1434783e9e51SPaolo Bonzini }
1435783e9e51SPaolo Bonzini
1436783e9e51SPaolo Bonzini s->num_set -= nodep->num_after;
1437783e9e51SPaolo Bonzini nodep->num_after = middle_end - middle_start + 1 - MASK_BITS;
1438783e9e51SPaolo Bonzini s->num_set += nodep->num_after;
1439783e9e51SPaolo Bonzini
1440783e9e51SPaolo Bonzini node_reduce(s, nodep);
1441783e9e51SPaolo Bonzini }
1442783e9e51SPaolo Bonzini idx = middle_end + 1;
1443783e9e51SPaolo Bonzini n -= middle_end - middle_start + 1;
1444783e9e51SPaolo Bonzini
1445783e9e51SPaolo Bonzini /* Trailing - bits at and beyond last mask boundary */
1446783e9e51SPaolo Bonzini assert(n < MASK_BITS);
1447783e9e51SPaolo Bonzini for (; n > 0; idx++, n--)
1448783e9e51SPaolo Bonzini bit_set(s, idx);
1449783e9e51SPaolo Bonzini }
1450783e9e51SPaolo Bonzini
1451783e9e51SPaolo Bonzini /* 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)1452783e9e51SPaolo Bonzini void sparsebit_clear_num(struct sparsebit *s,
1453783e9e51SPaolo Bonzini sparsebit_idx_t start, sparsebit_num_t num)
1454783e9e51SPaolo Bonzini {
1455783e9e51SPaolo Bonzini struct node *nodep, *next;
1456783e9e51SPaolo Bonzini unsigned int n1;
1457783e9e51SPaolo Bonzini sparsebit_idx_t idx;
1458783e9e51SPaolo Bonzini sparsebit_num_t n;
1459783e9e51SPaolo Bonzini sparsebit_idx_t middle_start, middle_end;
1460783e9e51SPaolo Bonzini
1461783e9e51SPaolo Bonzini assert(num > 0);
1462783e9e51SPaolo Bonzini assert(start + num - 1 >= start);
1463783e9e51SPaolo Bonzini
1464783e9e51SPaolo Bonzini /* Leading - bits before first mask boundary */
1465783e9e51SPaolo Bonzini for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--)
1466783e9e51SPaolo Bonzini bit_clear(s, idx);
1467783e9e51SPaolo Bonzini
1468783e9e51SPaolo Bonzini /* Middle - bits spanning one or more entire mask */
1469783e9e51SPaolo Bonzini middle_start = idx;
1470783e9e51SPaolo Bonzini middle_end = middle_start + (n & -MASK_BITS) - 1;
1471783e9e51SPaolo Bonzini if (n >= MASK_BITS) {
1472783e9e51SPaolo Bonzini nodep = node_split(s, middle_start);
1473783e9e51SPaolo Bonzini
1474783e9e51SPaolo Bonzini /*
1475783e9e51SPaolo Bonzini * As needed, split just after end of middle bits.
1476783e9e51SPaolo Bonzini * No split needed if end of middle bits is at highest
1477783e9e51SPaolo Bonzini * supported bit index.
1478783e9e51SPaolo Bonzini */
1479783e9e51SPaolo Bonzini if (middle_end + 1 > middle_end)
1480783e9e51SPaolo Bonzini (void) node_split(s, middle_end + 1);
1481783e9e51SPaolo Bonzini
1482783e9e51SPaolo Bonzini /* Delete nodes that only describe bits within the middle. */
1483783e9e51SPaolo Bonzini for (next = node_next(s, nodep);
1484783e9e51SPaolo Bonzini next && (next->idx < middle_end);
1485783e9e51SPaolo Bonzini next = node_next(s, nodep)) {
1486783e9e51SPaolo Bonzini assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end);
1487783e9e51SPaolo Bonzini node_rm(s, next);
1488783e9e51SPaolo Bonzini next = NULL;
1489783e9e51SPaolo Bonzini }
1490783e9e51SPaolo Bonzini
1491783e9e51SPaolo Bonzini /* As needed clear each of the mask bits */
1492783e9e51SPaolo Bonzini for (n1 = 0; n1 < MASK_BITS; n1++) {
1493783e9e51SPaolo Bonzini if (nodep->mask & (1 << n1)) {
1494783e9e51SPaolo Bonzini nodep->mask &= ~(1 << n1);
1495783e9e51SPaolo Bonzini s->num_set--;
1496783e9e51SPaolo Bonzini }
1497783e9e51SPaolo Bonzini }
1498783e9e51SPaolo Bonzini
1499783e9e51SPaolo Bonzini /* Clear any bits described by num_after */
1500783e9e51SPaolo Bonzini s->num_set -= nodep->num_after;
1501783e9e51SPaolo Bonzini nodep->num_after = 0;
1502783e9e51SPaolo Bonzini
1503783e9e51SPaolo Bonzini /*
1504783e9e51SPaolo Bonzini * Delete the node that describes the beginning of
1505783e9e51SPaolo Bonzini * the middle bits and perform any allowed reductions
1506783e9e51SPaolo Bonzini * with the nodes prev or next of nodep.
1507783e9e51SPaolo Bonzini */
1508783e9e51SPaolo Bonzini node_reduce(s, nodep);
1509783e9e51SPaolo Bonzini nodep = NULL;
1510783e9e51SPaolo Bonzini }
1511783e9e51SPaolo Bonzini idx = middle_end + 1;
1512783e9e51SPaolo Bonzini n -= middle_end - middle_start + 1;
1513783e9e51SPaolo Bonzini
1514783e9e51SPaolo Bonzini /* Trailing - bits at and beyond last mask boundary */
1515783e9e51SPaolo Bonzini assert(n < MASK_BITS);
1516783e9e51SPaolo Bonzini for (; n > 0; idx++, n--)
1517783e9e51SPaolo Bonzini bit_clear(s, idx);
1518783e9e51SPaolo Bonzini }
1519783e9e51SPaolo Bonzini
1520783e9e51SPaolo Bonzini /* Sets the bit at the index given by idx. */
sparsebit_set(struct sparsebit * s,sparsebit_idx_t idx)1521783e9e51SPaolo Bonzini void sparsebit_set(struct sparsebit *s, sparsebit_idx_t idx)
1522783e9e51SPaolo Bonzini {
1523783e9e51SPaolo Bonzini sparsebit_set_num(s, idx, 1);
1524783e9e51SPaolo Bonzini }
1525783e9e51SPaolo Bonzini
1526783e9e51SPaolo Bonzini /* Clears the bit at the index given by idx. */
sparsebit_clear(struct sparsebit * s,sparsebit_idx_t idx)1527783e9e51SPaolo Bonzini void sparsebit_clear(struct sparsebit *s, sparsebit_idx_t idx)
1528783e9e51SPaolo Bonzini {
1529783e9e51SPaolo Bonzini sparsebit_clear_num(s, idx, 1);
1530783e9e51SPaolo Bonzini }
1531783e9e51SPaolo Bonzini
1532783e9e51SPaolo Bonzini /* Sets the bits in the entire addressable range of the sparsebit array. */
sparsebit_set_all(struct sparsebit * s)1533783e9e51SPaolo Bonzini void sparsebit_set_all(struct sparsebit *s)
1534783e9e51SPaolo Bonzini {
1535783e9e51SPaolo Bonzini sparsebit_set(s, 0);
1536783e9e51SPaolo Bonzini sparsebit_set_num(s, 1, ~(sparsebit_idx_t) 0);
1537783e9e51SPaolo Bonzini assert(sparsebit_all_set(s));
1538783e9e51SPaolo Bonzini }
1539783e9e51SPaolo Bonzini
1540783e9e51SPaolo Bonzini /* Clears the bits in the entire addressable range of the sparsebit array. */
sparsebit_clear_all(struct sparsebit * s)1541783e9e51SPaolo Bonzini void sparsebit_clear_all(struct sparsebit *s)
1542783e9e51SPaolo Bonzini {
1543783e9e51SPaolo Bonzini sparsebit_clear(s, 0);
1544783e9e51SPaolo Bonzini sparsebit_clear_num(s, 1, ~(sparsebit_idx_t) 0);
1545783e9e51SPaolo Bonzini assert(!sparsebit_any_set(s));
1546783e9e51SPaolo Bonzini }
1547783e9e51SPaolo Bonzini
display_range(FILE * stream,sparsebit_idx_t low,sparsebit_idx_t high,bool prepend_comma_space)1548783e9e51SPaolo Bonzini static size_t display_range(FILE *stream, sparsebit_idx_t low,
1549783e9e51SPaolo Bonzini sparsebit_idx_t high, bool prepend_comma_space)
1550783e9e51SPaolo Bonzini {
1551783e9e51SPaolo Bonzini char *fmt_str;
1552783e9e51SPaolo Bonzini size_t sz;
1553783e9e51SPaolo Bonzini
1554783e9e51SPaolo Bonzini /* Determine the printf format string */
1555783e9e51SPaolo Bonzini if (low == high)
1556783e9e51SPaolo Bonzini fmt_str = prepend_comma_space ? ", 0x%lx" : "0x%lx";
1557783e9e51SPaolo Bonzini else
1558783e9e51SPaolo Bonzini fmt_str = prepend_comma_space ? ", 0x%lx:0x%lx" : "0x%lx:0x%lx";
1559783e9e51SPaolo Bonzini
1560783e9e51SPaolo Bonzini /*
1561783e9e51SPaolo Bonzini * When stream is NULL, just determine the size of what would
1562783e9e51SPaolo Bonzini * have been printed, else print the range.
1563783e9e51SPaolo Bonzini */
1564783e9e51SPaolo Bonzini if (!stream)
1565783e9e51SPaolo Bonzini sz = snprintf(NULL, 0, fmt_str, low, high);
1566783e9e51SPaolo Bonzini else
1567783e9e51SPaolo Bonzini sz = fprintf(stream, fmt_str, low, high);
1568783e9e51SPaolo Bonzini
1569783e9e51SPaolo Bonzini return sz;
1570783e9e51SPaolo Bonzini }
1571783e9e51SPaolo Bonzini
1572783e9e51SPaolo Bonzini
1573783e9e51SPaolo Bonzini /* Dumps to the FILE stream given by stream, the bit settings
1574783e9e51SPaolo Bonzini * of s. Each line of output is prefixed with the number of
1575783e9e51SPaolo Bonzini * spaces given by indent. The length of each line is implementation
1576783e9e51SPaolo Bonzini * dependent and does not depend on the indent amount. The following
1577783e9e51SPaolo Bonzini * is an example output of a sparsebit array that has bits:
1578783e9e51SPaolo Bonzini *
1579783e9e51SPaolo Bonzini * 0x5, 0x8, 0xa:0xe, 0x12
1580783e9e51SPaolo Bonzini *
1581783e9e51SPaolo Bonzini * This corresponds to a sparsebit whose bits 5, 8, 10, 11, 12, 13, 14, 18
1582783e9e51SPaolo Bonzini * are set. Note that a ':', instead of a '-' is used to specify a range of
1583783e9e51SPaolo Bonzini * contiguous bits. This is done because '-' is used to specify command-line
1584783e9e51SPaolo Bonzini * options, and sometimes ranges are specified as command-line arguments.
1585783e9e51SPaolo Bonzini */
sparsebit_dump(FILE * stream,const struct sparsebit * s,unsigned int indent)1586*35f50c91SMichael Roth void sparsebit_dump(FILE *stream, const struct sparsebit *s,
1587783e9e51SPaolo Bonzini unsigned int indent)
1588783e9e51SPaolo Bonzini {
1589783e9e51SPaolo Bonzini size_t current_line_len = 0;
1590783e9e51SPaolo Bonzini size_t sz;
1591783e9e51SPaolo Bonzini struct node *nodep;
1592783e9e51SPaolo Bonzini
1593783e9e51SPaolo Bonzini if (!sparsebit_any_set(s))
1594783e9e51SPaolo Bonzini return;
1595783e9e51SPaolo Bonzini
1596783e9e51SPaolo Bonzini /* Display initial indent */
1597783e9e51SPaolo Bonzini fprintf(stream, "%*s", indent, "");
1598783e9e51SPaolo Bonzini
1599783e9e51SPaolo Bonzini /* For each node */
1600783e9e51SPaolo Bonzini for (nodep = node_first(s); nodep; nodep = node_next(s, nodep)) {
1601783e9e51SPaolo Bonzini unsigned int n1;
1602783e9e51SPaolo Bonzini sparsebit_idx_t low, high;
1603783e9e51SPaolo Bonzini
1604783e9e51SPaolo Bonzini /* For each group of bits in the mask */
1605783e9e51SPaolo Bonzini for (n1 = 0; n1 < MASK_BITS; n1++) {
1606783e9e51SPaolo Bonzini if (nodep->mask & (1 << n1)) {
1607783e9e51SPaolo Bonzini low = high = nodep->idx + n1;
1608783e9e51SPaolo Bonzini
1609783e9e51SPaolo Bonzini for (; n1 < MASK_BITS; n1++) {
1610783e9e51SPaolo Bonzini if (nodep->mask & (1 << n1))
1611783e9e51SPaolo Bonzini high = nodep->idx + n1;
1612783e9e51SPaolo Bonzini else
1613783e9e51SPaolo Bonzini break;
1614783e9e51SPaolo Bonzini }
1615783e9e51SPaolo Bonzini
1616783e9e51SPaolo Bonzini if ((n1 == MASK_BITS) && nodep->num_after)
1617783e9e51SPaolo Bonzini high += nodep->num_after;
1618783e9e51SPaolo Bonzini
1619783e9e51SPaolo Bonzini /*
1620783e9e51SPaolo Bonzini * How much room will it take to display
1621783e9e51SPaolo Bonzini * this range.
1622783e9e51SPaolo Bonzini */
1623783e9e51SPaolo Bonzini sz = display_range(NULL, low, high,
1624783e9e51SPaolo Bonzini current_line_len != 0);
1625783e9e51SPaolo Bonzini
1626783e9e51SPaolo Bonzini /*
1627783e9e51SPaolo Bonzini * If there is not enough room, display
1628783e9e51SPaolo Bonzini * a newline plus the indent of the next
1629783e9e51SPaolo Bonzini * line.
1630783e9e51SPaolo Bonzini */
1631783e9e51SPaolo Bonzini if (current_line_len + sz > DUMP_LINE_MAX) {
1632783e9e51SPaolo Bonzini fputs("\n", stream);
1633783e9e51SPaolo Bonzini fprintf(stream, "%*s", indent, "");
1634783e9e51SPaolo Bonzini current_line_len = 0;
1635783e9e51SPaolo Bonzini }
1636783e9e51SPaolo Bonzini
1637783e9e51SPaolo Bonzini /* Display the range */
1638783e9e51SPaolo Bonzini sz = display_range(stream, low, high,
1639783e9e51SPaolo Bonzini current_line_len != 0);
1640783e9e51SPaolo Bonzini current_line_len += sz;
1641783e9e51SPaolo Bonzini }
1642783e9e51SPaolo Bonzini }
1643783e9e51SPaolo Bonzini
1644783e9e51SPaolo Bonzini /*
1645783e9e51SPaolo Bonzini * If num_after and most significant-bit of mask is not
1646783e9e51SPaolo Bonzini * set, then still need to display a range for the bits
1647783e9e51SPaolo Bonzini * described by num_after.
1648783e9e51SPaolo Bonzini */
1649783e9e51SPaolo Bonzini if (!(nodep->mask & (1 << (MASK_BITS - 1))) && nodep->num_after) {
1650783e9e51SPaolo Bonzini low = nodep->idx + MASK_BITS;
1651783e9e51SPaolo Bonzini high = nodep->idx + MASK_BITS + nodep->num_after - 1;
1652783e9e51SPaolo Bonzini
1653783e9e51SPaolo Bonzini /*
1654783e9e51SPaolo Bonzini * How much room will it take to display
1655783e9e51SPaolo Bonzini * this range.
1656783e9e51SPaolo Bonzini */
1657783e9e51SPaolo Bonzini sz = display_range(NULL, low, high,
1658783e9e51SPaolo Bonzini current_line_len != 0);
1659783e9e51SPaolo Bonzini
1660783e9e51SPaolo Bonzini /*
1661783e9e51SPaolo Bonzini * If there is not enough room, display
1662783e9e51SPaolo Bonzini * a newline plus the indent of the next
1663783e9e51SPaolo Bonzini * line.
1664783e9e51SPaolo Bonzini */
1665783e9e51SPaolo Bonzini if (current_line_len + sz > DUMP_LINE_MAX) {
1666783e9e51SPaolo Bonzini fputs("\n", stream);
1667783e9e51SPaolo Bonzini fprintf(stream, "%*s", indent, "");
1668783e9e51SPaolo Bonzini current_line_len = 0;
1669783e9e51SPaolo Bonzini }
1670783e9e51SPaolo Bonzini
1671783e9e51SPaolo Bonzini /* Display the range */
1672783e9e51SPaolo Bonzini sz = display_range(stream, low, high,
1673783e9e51SPaolo Bonzini current_line_len != 0);
1674783e9e51SPaolo Bonzini current_line_len += sz;
1675783e9e51SPaolo Bonzini }
1676783e9e51SPaolo Bonzini }
1677783e9e51SPaolo Bonzini fputs("\n", stream);
1678783e9e51SPaolo Bonzini }
1679783e9e51SPaolo Bonzini
1680783e9e51SPaolo Bonzini /* Validates the internal state of the sparsebit array given by
1681783e9e51SPaolo Bonzini * s. On error, diagnostic information is printed to stderr and
1682783e9e51SPaolo Bonzini * abort is called.
1683783e9e51SPaolo Bonzini */
sparsebit_validate_internal(const struct sparsebit * s)1684*35f50c91SMichael Roth void sparsebit_validate_internal(const struct sparsebit *s)
1685783e9e51SPaolo Bonzini {
1686783e9e51SPaolo Bonzini bool error_detected = false;
1687783e9e51SPaolo Bonzini struct node *nodep, *prev = NULL;
1688783e9e51SPaolo Bonzini sparsebit_num_t total_bits_set = 0;
1689783e9e51SPaolo Bonzini unsigned int n1;
1690783e9e51SPaolo Bonzini
1691783e9e51SPaolo Bonzini /* For each node */
1692783e9e51SPaolo Bonzini for (nodep = node_first(s); nodep;
1693783e9e51SPaolo Bonzini prev = nodep, nodep = node_next(s, nodep)) {
1694783e9e51SPaolo Bonzini
1695783e9e51SPaolo Bonzini /*
1696783e9e51SPaolo Bonzini * Increase total bits set by the number of bits set
1697783e9e51SPaolo Bonzini * in this node.
1698783e9e51SPaolo Bonzini */
1699783e9e51SPaolo Bonzini for (n1 = 0; n1 < MASK_BITS; n1++)
1700783e9e51SPaolo Bonzini if (nodep->mask & (1 << n1))
1701783e9e51SPaolo Bonzini total_bits_set++;
1702783e9e51SPaolo Bonzini
1703783e9e51SPaolo Bonzini total_bits_set += nodep->num_after;
1704783e9e51SPaolo Bonzini
1705783e9e51SPaolo Bonzini /*
1706783e9e51SPaolo Bonzini * Arbitrary choice as to whether a mask of 0 is allowed
1707783e9e51SPaolo Bonzini * or not. For diagnostic purposes it is beneficial to
1708783e9e51SPaolo Bonzini * have only one valid means to represent a set of bits.
1709783e9e51SPaolo Bonzini * To support this an arbitrary choice has been made
1710783e9e51SPaolo Bonzini * to not allow a mask of zero.
1711783e9e51SPaolo Bonzini */
1712783e9e51SPaolo Bonzini if (nodep->mask == 0) {
1713783e9e51SPaolo Bonzini fprintf(stderr, "Node mask of zero, "
1714783e9e51SPaolo Bonzini "nodep: %p nodep->mask: 0x%x",
1715783e9e51SPaolo Bonzini nodep, nodep->mask);
1716783e9e51SPaolo Bonzini error_detected = true;
1717783e9e51SPaolo Bonzini break;
1718783e9e51SPaolo Bonzini }
1719783e9e51SPaolo Bonzini
1720783e9e51SPaolo Bonzini /*
1721783e9e51SPaolo Bonzini * Validate num_after is not greater than the max index
1722783e9e51SPaolo Bonzini * - the number of mask bits. The num_after member
1723783e9e51SPaolo Bonzini * uses 0-based indexing and thus has no value that
1724783e9e51SPaolo Bonzini * represents all bits set. This limitation is handled
1725783e9e51SPaolo Bonzini * by requiring a non-zero mask. With a non-zero mask,
1726783e9e51SPaolo Bonzini * MASK_BITS worth of bits are described by the mask,
1727783e9e51SPaolo Bonzini * which makes the largest needed num_after equal to:
1728783e9e51SPaolo Bonzini *
1729783e9e51SPaolo Bonzini * (~(sparsebit_num_t) 0) - MASK_BITS + 1
1730783e9e51SPaolo Bonzini */
1731783e9e51SPaolo Bonzini if (nodep->num_after
1732783e9e51SPaolo Bonzini > (~(sparsebit_num_t) 0) - MASK_BITS + 1) {
1733783e9e51SPaolo Bonzini fprintf(stderr, "num_after too large, "
1734783e9e51SPaolo Bonzini "nodep: %p nodep->num_after: 0x%lx",
1735783e9e51SPaolo Bonzini nodep, nodep->num_after);
1736783e9e51SPaolo Bonzini error_detected = true;
1737783e9e51SPaolo Bonzini break;
1738783e9e51SPaolo Bonzini }
1739783e9e51SPaolo Bonzini
1740783e9e51SPaolo Bonzini /* Validate node index is divisible by the mask size */
1741783e9e51SPaolo Bonzini if (nodep->idx % MASK_BITS) {
17424d5f26eeSColin Ian King fprintf(stderr, "Node index not divisible by "
1743783e9e51SPaolo Bonzini "mask size,\n"
1744783e9e51SPaolo Bonzini " nodep: %p nodep->idx: 0x%lx "
1745783e9e51SPaolo Bonzini "MASK_BITS: %lu\n",
1746783e9e51SPaolo Bonzini nodep, nodep->idx, MASK_BITS);
1747783e9e51SPaolo Bonzini error_detected = true;
1748783e9e51SPaolo Bonzini break;
1749783e9e51SPaolo Bonzini }
1750783e9e51SPaolo Bonzini
1751783e9e51SPaolo Bonzini /*
1752783e9e51SPaolo Bonzini * Validate bits described by node don't wrap beyond the
1753783e9e51SPaolo Bonzini * highest supported index.
1754783e9e51SPaolo Bonzini */
1755783e9e51SPaolo Bonzini if ((nodep->idx + MASK_BITS + nodep->num_after - 1) < nodep->idx) {
1756783e9e51SPaolo Bonzini fprintf(stderr, "Bits described by node wrap "
1757783e9e51SPaolo Bonzini "beyond highest supported index,\n"
1758783e9e51SPaolo Bonzini " nodep: %p nodep->idx: 0x%lx\n"
1759783e9e51SPaolo Bonzini " MASK_BITS: %lu nodep->num_after: 0x%lx",
1760783e9e51SPaolo Bonzini nodep, nodep->idx, MASK_BITS, nodep->num_after);
1761783e9e51SPaolo Bonzini error_detected = true;
1762783e9e51SPaolo Bonzini break;
1763783e9e51SPaolo Bonzini }
1764783e9e51SPaolo Bonzini
1765783e9e51SPaolo Bonzini /* Check parent pointers. */
1766783e9e51SPaolo Bonzini if (nodep->left) {
1767783e9e51SPaolo Bonzini if (nodep->left->parent != nodep) {
1768783e9e51SPaolo Bonzini fprintf(stderr, "Left child parent pointer "
1769783e9e51SPaolo Bonzini "doesn't point to this node,\n"
1770783e9e51SPaolo Bonzini " nodep: %p nodep->left: %p "
1771783e9e51SPaolo Bonzini "nodep->left->parent: %p",
1772783e9e51SPaolo Bonzini nodep, nodep->left,
1773783e9e51SPaolo Bonzini nodep->left->parent);
1774783e9e51SPaolo Bonzini error_detected = true;
1775783e9e51SPaolo Bonzini break;
1776783e9e51SPaolo Bonzini }
1777783e9e51SPaolo Bonzini }
1778783e9e51SPaolo Bonzini
1779783e9e51SPaolo Bonzini if (nodep->right) {
1780783e9e51SPaolo Bonzini if (nodep->right->parent != nodep) {
1781783e9e51SPaolo Bonzini fprintf(stderr, "Right child parent pointer "
1782783e9e51SPaolo Bonzini "doesn't point to this node,\n"
1783783e9e51SPaolo Bonzini " nodep: %p nodep->right: %p "
1784783e9e51SPaolo Bonzini "nodep->right->parent: %p",
1785783e9e51SPaolo Bonzini nodep, nodep->right,
1786783e9e51SPaolo Bonzini nodep->right->parent);
1787783e9e51SPaolo Bonzini error_detected = true;
1788783e9e51SPaolo Bonzini break;
1789783e9e51SPaolo Bonzini }
1790783e9e51SPaolo Bonzini }
1791783e9e51SPaolo Bonzini
1792783e9e51SPaolo Bonzini if (!nodep->parent) {
1793783e9e51SPaolo Bonzini if (s->root != nodep) {
1794783e9e51SPaolo Bonzini fprintf(stderr, "Unexpected root node, "
1795783e9e51SPaolo Bonzini "s->root: %p nodep: %p",
1796783e9e51SPaolo Bonzini s->root, nodep);
1797783e9e51SPaolo Bonzini error_detected = true;
1798783e9e51SPaolo Bonzini break;
1799783e9e51SPaolo Bonzini }
1800783e9e51SPaolo Bonzini }
1801783e9e51SPaolo Bonzini
1802783e9e51SPaolo Bonzini if (prev) {
1803783e9e51SPaolo Bonzini /*
1804783e9e51SPaolo Bonzini * Is index of previous node before index of
1805783e9e51SPaolo Bonzini * current node?
1806783e9e51SPaolo Bonzini */
1807783e9e51SPaolo Bonzini if (prev->idx >= nodep->idx) {
1808783e9e51SPaolo Bonzini fprintf(stderr, "Previous node index "
1809783e9e51SPaolo Bonzini ">= current node index,\n"
1810783e9e51SPaolo Bonzini " prev: %p prev->idx: 0x%lx\n"
1811783e9e51SPaolo Bonzini " nodep: %p nodep->idx: 0x%lx",
1812783e9e51SPaolo Bonzini prev, prev->idx, nodep, nodep->idx);
1813783e9e51SPaolo Bonzini error_detected = true;
1814783e9e51SPaolo Bonzini break;
1815783e9e51SPaolo Bonzini }
1816783e9e51SPaolo Bonzini
1817783e9e51SPaolo Bonzini /*
1818783e9e51SPaolo Bonzini * Nodes occur in asscending order, based on each
1819783e9e51SPaolo Bonzini * nodes starting index.
1820783e9e51SPaolo Bonzini */
1821783e9e51SPaolo Bonzini if ((prev->idx + MASK_BITS + prev->num_after - 1)
1822783e9e51SPaolo Bonzini >= nodep->idx) {
1823783e9e51SPaolo Bonzini fprintf(stderr, "Previous node bit range "
1824783e9e51SPaolo Bonzini "overlap with current node bit range,\n"
1825783e9e51SPaolo Bonzini " prev: %p prev->idx: 0x%lx "
1826783e9e51SPaolo Bonzini "prev->num_after: 0x%lx\n"
1827783e9e51SPaolo Bonzini " nodep: %p nodep->idx: 0x%lx "
1828783e9e51SPaolo Bonzini "nodep->num_after: 0x%lx\n"
1829783e9e51SPaolo Bonzini " MASK_BITS: %lu",
1830783e9e51SPaolo Bonzini prev, prev->idx, prev->num_after,
1831783e9e51SPaolo Bonzini nodep, nodep->idx, nodep->num_after,
1832783e9e51SPaolo Bonzini MASK_BITS);
1833783e9e51SPaolo Bonzini error_detected = true;
1834783e9e51SPaolo Bonzini break;
1835783e9e51SPaolo Bonzini }
1836783e9e51SPaolo Bonzini
1837783e9e51SPaolo Bonzini /*
1838783e9e51SPaolo Bonzini * When the node has all mask bits set, it shouldn't
1839783e9e51SPaolo Bonzini * be adjacent to the last bit described by the
1840783e9e51SPaolo Bonzini * previous node.
1841783e9e51SPaolo Bonzini */
1842783e9e51SPaolo Bonzini if (nodep->mask == ~(mask_t) 0 &&
1843783e9e51SPaolo Bonzini prev->idx + MASK_BITS + prev->num_after == nodep->idx) {
1844783e9e51SPaolo Bonzini fprintf(stderr, "Current node has mask with "
1845783e9e51SPaolo Bonzini "all bits set and is adjacent to the "
1846783e9e51SPaolo Bonzini "previous node,\n"
1847783e9e51SPaolo Bonzini " prev: %p prev->idx: 0x%lx "
1848783e9e51SPaolo Bonzini "prev->num_after: 0x%lx\n"
1849783e9e51SPaolo Bonzini " nodep: %p nodep->idx: 0x%lx "
1850783e9e51SPaolo Bonzini "nodep->num_after: 0x%lx\n"
1851783e9e51SPaolo Bonzini " MASK_BITS: %lu",
1852783e9e51SPaolo Bonzini prev, prev->idx, prev->num_after,
1853783e9e51SPaolo Bonzini nodep, nodep->idx, nodep->num_after,
1854783e9e51SPaolo Bonzini MASK_BITS);
1855783e9e51SPaolo Bonzini
1856783e9e51SPaolo Bonzini error_detected = true;
1857783e9e51SPaolo Bonzini break;
1858783e9e51SPaolo Bonzini }
1859783e9e51SPaolo Bonzini }
1860783e9e51SPaolo Bonzini }
1861783e9e51SPaolo Bonzini
1862783e9e51SPaolo Bonzini if (!error_detected) {
1863783e9e51SPaolo Bonzini /*
1864783e9e51SPaolo Bonzini * Is sum of bits set in each node equal to the count
1865783e9e51SPaolo Bonzini * of total bits set.
1866783e9e51SPaolo Bonzini */
1867783e9e51SPaolo Bonzini if (s->num_set != total_bits_set) {
1868d22869afSColin Ian King fprintf(stderr, "Number of bits set mismatch,\n"
1869783e9e51SPaolo Bonzini " s->num_set: 0x%lx total_bits_set: 0x%lx",
1870783e9e51SPaolo Bonzini s->num_set, total_bits_set);
1871783e9e51SPaolo Bonzini
1872783e9e51SPaolo Bonzini error_detected = true;
1873783e9e51SPaolo Bonzini }
1874783e9e51SPaolo Bonzini }
1875783e9e51SPaolo Bonzini
1876783e9e51SPaolo Bonzini if (error_detected) {
1877783e9e51SPaolo Bonzini fputs(" dump_internal:\n", stderr);
1878783e9e51SPaolo Bonzini sparsebit_dump_internal(stderr, s, 4);
1879783e9e51SPaolo Bonzini abort();
1880783e9e51SPaolo Bonzini }
1881783e9e51SPaolo Bonzini }
1882783e9e51SPaolo Bonzini
1883783e9e51SPaolo Bonzini
1884783e9e51SPaolo Bonzini #ifdef FUZZ
1885783e9e51SPaolo Bonzini /* A simple but effective fuzzing driver. Look for bugs with the help
1886783e9e51SPaolo Bonzini * of some invariants and of a trivial representation of sparsebit.
1887783e9e51SPaolo Bonzini * Just use 512 bytes of /dev/zero and /dev/urandom as inputs, and let
1888783e9e51SPaolo Bonzini * afl-fuzz do the magic. :)
1889783e9e51SPaolo Bonzini */
1890783e9e51SPaolo Bonzini
1891783e9e51SPaolo Bonzini #include <stdlib.h>
1892783e9e51SPaolo Bonzini
1893783e9e51SPaolo Bonzini struct range {
1894783e9e51SPaolo Bonzini sparsebit_idx_t first, last;
1895783e9e51SPaolo Bonzini bool set;
1896783e9e51SPaolo Bonzini };
1897783e9e51SPaolo Bonzini
1898783e9e51SPaolo Bonzini struct sparsebit *s;
1899783e9e51SPaolo Bonzini struct range ranges[1000];
1900783e9e51SPaolo Bonzini int num_ranges;
1901783e9e51SPaolo Bonzini
get_value(sparsebit_idx_t idx)1902783e9e51SPaolo Bonzini static bool get_value(sparsebit_idx_t idx)
1903783e9e51SPaolo Bonzini {
1904783e9e51SPaolo Bonzini int i;
1905783e9e51SPaolo Bonzini
1906783e9e51SPaolo Bonzini for (i = num_ranges; --i >= 0; )
1907783e9e51SPaolo Bonzini if (ranges[i].first <= idx && idx <= ranges[i].last)
1908783e9e51SPaolo Bonzini return ranges[i].set;
1909783e9e51SPaolo Bonzini
1910783e9e51SPaolo Bonzini return false;
1911783e9e51SPaolo Bonzini }
1912783e9e51SPaolo Bonzini
operate(int code,sparsebit_idx_t first,sparsebit_idx_t last)1913783e9e51SPaolo Bonzini static void operate(int code, sparsebit_idx_t first, sparsebit_idx_t last)
1914783e9e51SPaolo Bonzini {
1915783e9e51SPaolo Bonzini sparsebit_num_t num;
1916783e9e51SPaolo Bonzini sparsebit_idx_t next;
1917783e9e51SPaolo Bonzini
1918783e9e51SPaolo Bonzini if (first < last) {
1919783e9e51SPaolo Bonzini num = last - first + 1;
1920783e9e51SPaolo Bonzini } else {
1921783e9e51SPaolo Bonzini num = first - last + 1;
1922783e9e51SPaolo Bonzini first = last;
1923783e9e51SPaolo Bonzini last = first + num - 1;
1924783e9e51SPaolo Bonzini }
1925783e9e51SPaolo Bonzini
1926783e9e51SPaolo Bonzini switch (code) {
1927783e9e51SPaolo Bonzini case 0:
1928783e9e51SPaolo Bonzini sparsebit_set(s, first);
1929783e9e51SPaolo Bonzini assert(sparsebit_is_set(s, first));
1930783e9e51SPaolo Bonzini assert(!sparsebit_is_clear(s, first));
1931783e9e51SPaolo Bonzini assert(sparsebit_any_set(s));
1932783e9e51SPaolo Bonzini assert(!sparsebit_all_clear(s));
1933783e9e51SPaolo Bonzini if (get_value(first))
1934783e9e51SPaolo Bonzini return;
1935783e9e51SPaolo Bonzini if (num_ranges == 1000)
1936783e9e51SPaolo Bonzini exit(0);
1937783e9e51SPaolo Bonzini ranges[num_ranges++] = (struct range)
1938783e9e51SPaolo Bonzini { .first = first, .last = first, .set = true };
1939783e9e51SPaolo Bonzini break;
1940783e9e51SPaolo Bonzini case 1:
1941783e9e51SPaolo Bonzini sparsebit_clear(s, first);
1942783e9e51SPaolo Bonzini assert(!sparsebit_is_set(s, first));
1943783e9e51SPaolo Bonzini assert(sparsebit_is_clear(s, first));
1944783e9e51SPaolo Bonzini assert(sparsebit_any_clear(s));
1945783e9e51SPaolo Bonzini assert(!sparsebit_all_set(s));
1946783e9e51SPaolo Bonzini if (!get_value(first))
1947783e9e51SPaolo Bonzini return;
1948783e9e51SPaolo Bonzini if (num_ranges == 1000)
1949783e9e51SPaolo Bonzini exit(0);
1950783e9e51SPaolo Bonzini ranges[num_ranges++] = (struct range)
1951783e9e51SPaolo Bonzini { .first = first, .last = first, .set = false };
1952783e9e51SPaolo Bonzini break;
1953783e9e51SPaolo Bonzini case 2:
1954783e9e51SPaolo Bonzini assert(sparsebit_is_set(s, first) == get_value(first));
1955783e9e51SPaolo Bonzini assert(sparsebit_is_clear(s, first) == !get_value(first));
1956783e9e51SPaolo Bonzini break;
1957783e9e51SPaolo Bonzini case 3:
1958783e9e51SPaolo Bonzini if (sparsebit_any_set(s))
1959783e9e51SPaolo Bonzini assert(get_value(sparsebit_first_set(s)));
1960783e9e51SPaolo Bonzini if (sparsebit_any_clear(s))
1961783e9e51SPaolo Bonzini assert(!get_value(sparsebit_first_clear(s)));
1962783e9e51SPaolo Bonzini sparsebit_set_all(s);
1963783e9e51SPaolo Bonzini assert(!sparsebit_any_clear(s));
1964783e9e51SPaolo Bonzini assert(sparsebit_all_set(s));
1965783e9e51SPaolo Bonzini num_ranges = 0;
1966783e9e51SPaolo Bonzini ranges[num_ranges++] = (struct range)
1967783e9e51SPaolo Bonzini { .first = 0, .last = ~(sparsebit_idx_t)0, .set = true };
1968783e9e51SPaolo Bonzini break;
1969783e9e51SPaolo Bonzini case 4:
1970783e9e51SPaolo Bonzini if (sparsebit_any_set(s))
1971783e9e51SPaolo Bonzini assert(get_value(sparsebit_first_set(s)));
1972783e9e51SPaolo Bonzini if (sparsebit_any_clear(s))
1973783e9e51SPaolo Bonzini assert(!get_value(sparsebit_first_clear(s)));
1974783e9e51SPaolo Bonzini sparsebit_clear_all(s);
1975783e9e51SPaolo Bonzini assert(!sparsebit_any_set(s));
1976783e9e51SPaolo Bonzini assert(sparsebit_all_clear(s));
1977783e9e51SPaolo Bonzini num_ranges = 0;
1978783e9e51SPaolo Bonzini break;
1979783e9e51SPaolo Bonzini case 5:
1980783e9e51SPaolo Bonzini next = sparsebit_next_set(s, first);
1981783e9e51SPaolo Bonzini assert(next == 0 || next > first);
1982783e9e51SPaolo Bonzini assert(next == 0 || get_value(next));
1983783e9e51SPaolo Bonzini break;
1984783e9e51SPaolo Bonzini case 6:
1985783e9e51SPaolo Bonzini next = sparsebit_next_clear(s, first);
1986783e9e51SPaolo Bonzini assert(next == 0 || next > first);
1987783e9e51SPaolo Bonzini assert(next == 0 || !get_value(next));
1988783e9e51SPaolo Bonzini break;
1989783e9e51SPaolo Bonzini case 7:
1990783e9e51SPaolo Bonzini next = sparsebit_next_clear(s, first);
1991783e9e51SPaolo Bonzini if (sparsebit_is_set_num(s, first, num)) {
1992783e9e51SPaolo Bonzini assert(next == 0 || next > last);
1993783e9e51SPaolo Bonzini if (first)
1994783e9e51SPaolo Bonzini next = sparsebit_next_set(s, first - 1);
1995783e9e51SPaolo Bonzini else if (sparsebit_any_set(s))
1996783e9e51SPaolo Bonzini next = sparsebit_first_set(s);
1997783e9e51SPaolo Bonzini else
1998783e9e51SPaolo Bonzini return;
1999783e9e51SPaolo Bonzini assert(next == first);
2000783e9e51SPaolo Bonzini } else {
2001783e9e51SPaolo Bonzini assert(sparsebit_is_clear(s, first) || next <= last);
2002783e9e51SPaolo Bonzini }
2003783e9e51SPaolo Bonzini break;
2004783e9e51SPaolo Bonzini case 8:
2005783e9e51SPaolo Bonzini next = sparsebit_next_set(s, first);
2006783e9e51SPaolo Bonzini if (sparsebit_is_clear_num(s, first, num)) {
2007783e9e51SPaolo Bonzini assert(next == 0 || next > last);
2008783e9e51SPaolo Bonzini if (first)
2009783e9e51SPaolo Bonzini next = sparsebit_next_clear(s, first - 1);
2010783e9e51SPaolo Bonzini else if (sparsebit_any_clear(s))
2011783e9e51SPaolo Bonzini next = sparsebit_first_clear(s);
2012783e9e51SPaolo Bonzini else
2013783e9e51SPaolo Bonzini return;
2014783e9e51SPaolo Bonzini assert(next == first);
2015783e9e51SPaolo Bonzini } else {
2016783e9e51SPaolo Bonzini assert(sparsebit_is_set(s, first) || next <= last);
2017783e9e51SPaolo Bonzini }
2018783e9e51SPaolo Bonzini break;
2019783e9e51SPaolo Bonzini case 9:
2020783e9e51SPaolo Bonzini sparsebit_set_num(s, first, num);
2021783e9e51SPaolo Bonzini assert(sparsebit_is_set_num(s, first, num));
2022783e9e51SPaolo Bonzini assert(!sparsebit_is_clear_num(s, first, num));
2023783e9e51SPaolo Bonzini assert(sparsebit_any_set(s));
2024783e9e51SPaolo Bonzini assert(!sparsebit_all_clear(s));
2025783e9e51SPaolo Bonzini if (num_ranges == 1000)
2026783e9e51SPaolo Bonzini exit(0);
2027783e9e51SPaolo Bonzini ranges[num_ranges++] = (struct range)
2028783e9e51SPaolo Bonzini { .first = first, .last = last, .set = true };
2029783e9e51SPaolo Bonzini break;
2030783e9e51SPaolo Bonzini case 10:
2031783e9e51SPaolo Bonzini sparsebit_clear_num(s, first, num);
2032783e9e51SPaolo Bonzini assert(!sparsebit_is_set_num(s, first, num));
2033783e9e51SPaolo Bonzini assert(sparsebit_is_clear_num(s, first, num));
2034783e9e51SPaolo Bonzini assert(sparsebit_any_clear(s));
2035783e9e51SPaolo Bonzini assert(!sparsebit_all_set(s));
2036783e9e51SPaolo Bonzini if (num_ranges == 1000)
2037783e9e51SPaolo Bonzini exit(0);
2038783e9e51SPaolo Bonzini ranges[num_ranges++] = (struct range)
2039783e9e51SPaolo Bonzini { .first = first, .last = last, .set = false };
2040783e9e51SPaolo Bonzini break;
2041783e9e51SPaolo Bonzini case 11:
2042783e9e51SPaolo Bonzini sparsebit_validate_internal(s);
2043783e9e51SPaolo Bonzini break;
2044783e9e51SPaolo Bonzini default:
2045783e9e51SPaolo Bonzini break;
2046783e9e51SPaolo Bonzini }
2047783e9e51SPaolo Bonzini }
2048783e9e51SPaolo Bonzini
get8(void)2049783e9e51SPaolo Bonzini unsigned char get8(void)
2050783e9e51SPaolo Bonzini {
2051783e9e51SPaolo Bonzini int ch;
2052783e9e51SPaolo Bonzini
2053783e9e51SPaolo Bonzini ch = getchar();
2054783e9e51SPaolo Bonzini if (ch == EOF)
2055783e9e51SPaolo Bonzini exit(0);
2056783e9e51SPaolo Bonzini return ch;
2057783e9e51SPaolo Bonzini }
2058783e9e51SPaolo Bonzini
get64(void)2059783e9e51SPaolo Bonzini uint64_t get64(void)
2060783e9e51SPaolo Bonzini {
2061783e9e51SPaolo Bonzini uint64_t x;
2062783e9e51SPaolo Bonzini
2063783e9e51SPaolo Bonzini x = get8();
2064783e9e51SPaolo Bonzini x = (x << 8) | get8();
2065783e9e51SPaolo Bonzini x = (x << 8) | get8();
2066783e9e51SPaolo Bonzini x = (x << 8) | get8();
2067783e9e51SPaolo Bonzini x = (x << 8) | get8();
2068783e9e51SPaolo Bonzini x = (x << 8) | get8();
2069783e9e51SPaolo Bonzini x = (x << 8) | get8();
2070783e9e51SPaolo Bonzini return (x << 8) | get8();
2071783e9e51SPaolo Bonzini }
2072783e9e51SPaolo Bonzini
main(void)2073783e9e51SPaolo Bonzini int main(void)
2074783e9e51SPaolo Bonzini {
2075783e9e51SPaolo Bonzini s = sparsebit_alloc();
2076783e9e51SPaolo Bonzini for (;;) {
2077783e9e51SPaolo Bonzini uint8_t op = get8() & 0xf;
2078783e9e51SPaolo Bonzini uint64_t first = get64();
2079783e9e51SPaolo Bonzini uint64_t last = get64();
2080783e9e51SPaolo Bonzini
2081783e9e51SPaolo Bonzini operate(op, first, last);
2082783e9e51SPaolo Bonzini }
2083783e9e51SPaolo Bonzini }
2084783e9e51SPaolo Bonzini #endif
2085