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