Lines Matching +full:bit +full:- +full:mask

1 // SPDX-License-Identifier: GPL-2.0-only
3 * Sparse bit array
8 * This library provides functions to support a memory efficient bit array,
27 * sparsebit_alloc() and most also take a bit index. Frequently
30 * ---- Query Operations
37 * ---- Modifying Operations
55 * The index of the first bit set needs to be obtained via
60 * is at least 1 bit in the array set. This is because sparsebit_first_set()
63 * sparsebit array has at least a single bit set before calling
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
83 * uint32_t mask;
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.
92 * overlap. The idx member is always aligned to the mask size, i.e. a
97 * number of bits immediately after the mask bits that are contiguously set.
102 * node 0 - idx: 0x0 mask: 0xffffffff num_after: 0xffffffffffffffc0
103 * node 1 - idx: 0xffffffffffffffe0 mask: 0x3fffffff num_after: 0
109 * Nodes with a mask of 0 and num_after of 0 are not allowed.
114 * + The setting of at least one bit is always described in a nodes
115 * mask (mask >= 1).
117 * + A node with all mask bits set only occurs when the last bit
119 * starting index - 1. All such occurences of this condition are
120 * avoided by moving the setting of the nodes mask bits into
124 * within a nodes mask member.
129 * (idx + MASK_BITS + num_after - 1) <= ((sparsebit_idx_t) 0) - 1)
134 * maximum_index - nodes_starting_index - number_of_mask_bits
142 * start: node->idx
143 * end (inclusive): node->idx + MASK_BITS + node->num_after - 1;
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
150 * index and assures that a node where its mask represents the bit
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; member
199 return nodep->num_after + __builtin_popcount(nodep->mask); in node_num_set()
203 * lowest bit index.
209 for (nodep = s->root; nodep && nodep->left; nodep = nodep->left) in node_first()
216 * lowest bit index > the index of the node pointed to by np.
224 * If current node has a right child, next node is the left-most in node_next()
227 if (nodep->right) { in node_next()
228 for (nodep = nodep->right; nodep->left; nodep = nodep->left) in node_next()
237 while (nodep->parent && nodep == nodep->parent->right) in node_next()
238 nodep = nodep->parent; in node_next()
240 return nodep->parent; in node_next()
252 * If current node has a left child, next node is the right-most in node_prev()
255 if (nodep->left) { in node_prev()
256 for (nodep = nodep->left; nodep->right; nodep = nodep->right) in node_prev()
265 while (nodep->parent && nodep == nodep->parent->left) in node_prev()
266 nodep = nodep->parent; in node_prev()
268 return (struct node *) nodep->parent; in node_prev()
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.
287 root->idx = subtree->idx; in node_copy_subtree()
288 root->mask = subtree->mask; in node_copy_subtree()
289 root->num_after = subtree->num_after; in node_copy_subtree()
292 if (subtree->left) { in node_copy_subtree()
293 root->left = node_copy_subtree(subtree->left); in node_copy_subtree()
294 root->left->parent = root; in node_copy_subtree()
297 if (subtree->right) { in node_copy_subtree()
298 root->right = node_copy_subtree(subtree->right); in node_copy_subtree()
299 root->right->parent = root; in node_copy_subtree()
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.
314 /* Find the node that describes the setting of the bit at idx */ in node_find()
315 for (nodep = s->root; nodep; in node_find()
316 nodep = nodep->idx > idx ? nodep->left : nodep->right) { in node_find()
317 if (idx >= nodep->idx && in node_find()
318 idx <= nodep->idx + MASK_BITS + nodep->num_after - 1) in node_find()
328 * Adds a new node to describe the setting of the bit at the index given
344 nodep->idx = idx & -MASK_BITS; in node_add()
347 if (!s->root) { in node_add()
348 s->root = nodep; in node_add()
356 parentp = s->root; in node_add()
358 if (idx < parentp->idx) { in node_add()
359 if (!parentp->left) { in node_add()
360 parentp->left = nodep; in node_add()
361 nodep->parent = parentp; in node_add()
364 parentp = parentp->left; in node_add()
366 assert(idx > parentp->idx + MASK_BITS + parentp->num_after - 1); in node_add()
367 if (!parentp->right) { in node_add()
368 parentp->right = nodep; in node_add()
369 nodep->parent = parentp; in node_add()
372 parentp = parentp->right; in node_add()
377 * Does num_after bits of previous node overlap with the mask in node_add()
378 * of the new node? If so set the bits in the new nodes mask in node_add()
382 while (prev && prev->idx + MASK_BITS + prev->num_after - 1 >= nodep->idx) { in node_add()
383 unsigned int n1 = (prev->idx + MASK_BITS + prev->num_after - 1) in node_add()
384 - nodep->idx; in node_add()
385 assert(prev->num_after > 0); in node_add()
387 assert(!(nodep->mask & (1 << n1))); in node_add()
388 nodep->mask |= (1 << n1); in node_add()
389 prev->num_after--; in node_add()
399 * If any nodes there must be at least one bit set. Only case in sparsebit_all_set()
400 * where a bit is set and total num set is 0, is when all bits in sparsebit_all_set()
403 return s->root && s->num_set == 0; in sparsebit_all_set()
415 assert(s->num_set >= num_set || sparsebit_all_set(s)); in node_rm()
416 s->num_set -= node_num_set(nodep); in node_rm()
419 if (nodep->left && nodep->right) { in node_rm()
424 for (tmp = nodep->right; tmp->left; tmp = tmp->left) in node_rm()
426 tmp->left = nodep->left; in node_rm()
427 nodep->left = NULL; in node_rm()
428 tmp->left->parent = tmp; in node_rm()
432 if (nodep->left) { in node_rm()
433 if (!nodep->parent) { in node_rm()
434 s->root = nodep->left; in node_rm()
435 nodep->left->parent = NULL; in node_rm()
437 nodep->left->parent = nodep->parent; in node_rm()
438 if (nodep == nodep->parent->left) in node_rm()
439 nodep->parent->left = nodep->left; in node_rm()
441 assert(nodep == nodep->parent->right); in node_rm()
442 nodep->parent->right = nodep->left; in node_rm()
446 nodep->parent = nodep->left = nodep->right = NULL; in node_rm()
454 if (nodep->right) { in node_rm()
455 if (!nodep->parent) { in node_rm()
456 s->root = nodep->right; in node_rm()
457 nodep->right->parent = NULL; in node_rm()
459 nodep->right->parent = nodep->parent; in node_rm()
460 if (nodep == nodep->parent->left) in node_rm()
461 nodep->parent->left = nodep->right; in node_rm()
463 assert(nodep == nodep->parent->right); in node_rm()
464 nodep->parent->right = nodep->right; in node_rm()
468 nodep->parent = nodep->left = nodep->right = NULL; in node_rm()
475 if (!nodep->parent) { in node_rm()
476 s->root = NULL; in node_rm()
478 if (nodep->parent->left == nodep) in node_rm()
479 nodep->parent->left = NULL; in node_rm()
481 assert(nodep == nodep->parent->right); in node_rm()
482 nodep->parent->right = NULL; in node_rm()
486 nodep->parent = nodep->left = nodep->right = NULL; in node_rm()
492 /* Splits the node containing the bit at idx so that there is a node
496 * idx must start of a mask boundary.
518 if (nodep1->idx == idx) in node_split()
522 * Split point not at start of mask, so it must be part of in node_split()
530 offset = idx - (nodep1->idx + MASK_BITS); in node_split()
531 orig_num_after = nodep1->num_after; in node_split()
537 nodep1->num_after = offset; in node_split()
541 nodep2->num_after = orig_num_after - offset; in node_split()
542 if (nodep2->num_after >= MASK_BITS) { in node_split()
543 nodep2->mask = ~(mask_t) 0; in node_split()
544 nodep2->num_after -= MASK_BITS; in node_split()
546 nodep2->mask = (1 << nodep2->num_after) - 1; in node_split()
547 nodep2->num_after = 0; in node_split()
554 * nodes into a more compact form. For example, a node with a mask with
567 * For example it does not fix the case where the bit settings described
569 * complication of a bit setting for a specific index having different settings
571 * of which node has the correct setting of the bit and thus such conditions
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.
580 * node address that it set a mask bit in, and node_reduce() will notice
582 * adjacent node that the bit settings could be merged into.
588 * Nodes with a mask of 0 and num_after of 0 are not allowed.
590 * + The setting of at least one bit is always described in a nodes
591 * mask (mask >= 1).
593 * + A node with all mask bits set only occurs when the last bit
595 * starting index - 1. All such occurences of this condition are
596 * avoided by moving the setting of the nodes mask bits into
610 if (nodep->mask == 0 && nodep->num_after == 0) { in node_reduce()
644 * When the mask is 0, can reduce the amount of num_after in node_reduce()
645 * bits by moving the initial num_after bits into the mask. in node_reduce()
647 if (nodep->mask == 0) { in node_reduce()
648 assert(nodep->num_after != 0); in node_reduce()
649 assert(nodep->idx + MASK_BITS > nodep->idx); in node_reduce()
651 nodep->idx += MASK_BITS; in node_reduce()
653 if (nodep->num_after >= MASK_BITS) { in node_reduce()
654 nodep->mask = ~0; in node_reduce()
655 nodep->num_after -= MASK_BITS; in node_reduce()
657 nodep->mask = (1u << nodep->num_after) - 1; in node_reduce()
658 nodep->num_after = 0; in node_reduce()
674 if (prev->mask == 0 && prev->num_after == 0) { in node_reduce()
682 * All mask bits set and previous node has in node_reduce()
685 if (nodep->mask + 1 == 0 && in node_reduce()
686 prev->idx + MASK_BITS == nodep->idx) { in node_reduce()
687 prev->num_after += MASK_BITS + nodep->num_after; in node_reduce()
688 nodep->mask = 0; in node_reduce()
689 nodep->num_after = 0; in node_reduce()
698 * starting from the beginning of the mask? in node_reduce()
700 prev_highest_bit = prev->idx + MASK_BITS - 1 + prev->num_after; in node_reduce()
701 if (prev_highest_bit + 1 == nodep->idx && in node_reduce()
702 (nodep->mask | (nodep->mask >> 1)) == nodep->mask) { in node_reduce()
711 = __builtin_popcount(nodep->mask); in node_reduce()
713 ((1ULL << num_contiguous) - 1) == nodep->mask); in node_reduce()
715 prev->num_after += num_contiguous; in node_reduce()
716 nodep->mask = 0; in node_reduce()
720 * case where all mask bits are set and there in node_reduce()
721 * is a non-zero num_after setting. This code in node_reduce()
725 * the number of mask bits per pass. There are in node_reduce()
732 prev->num_after += nodep->num_after; in node_reduce()
733 nodep->num_after = 0; in node_reduce()
748 if (next->mask == 0 && next->num_after == 0) { in node_reduce()
756 * and has a mask with all bits set? in node_reduce()
758 if (next->idx == nodep->idx + MASK_BITS + nodep->num_after && in node_reduce()
759 next->mask == ~(mask_t) 0) { in node_reduce()
760 nodep->num_after += MASK_BITS; in node_reduce()
761 next->mask = 0; in node_reduce()
762 nodep->num_after += next->num_after; in node_reduce()
763 next->num_after = 0; in node_reduce()
775 /* Returns whether the bit at the index given by idx, within the
782 /* Find the node that describes the setting of the bit at idx */ in sparsebit_is_set()
783 for (nodep = s->root; nodep; in sparsebit_is_set()
784 nodep = nodep->idx > idx ? nodep->left : nodep->right) in sparsebit_is_set()
785 if (idx >= nodep->idx && in sparsebit_is_set()
786 idx <= nodep->idx + MASK_BITS + nodep->num_after - 1) in sparsebit_is_set()
792 /* Bit is set if it is any of the bits described by num_after */ in sparsebit_is_set()
793 if (nodep->num_after && idx >= nodep->idx + MASK_BITS) in sparsebit_is_set()
796 /* Is the corresponding mask bit set */ in sparsebit_is_set()
797 assert(idx >= nodep->idx && idx - nodep->idx < MASK_BITS); in sparsebit_is_set()
798 return !!(nodep->mask & (1 << (idx - nodep->idx))); in sparsebit_is_set()
801 /* Within the sparsebit array pointed to by s, sets the bit
813 * Get a node where the bit at idx is described by the mask. in bit_set()
815 * already a node that describes the setting of bit. in bit_set()
817 nodep = node_split(s, idx & -MASK_BITS); in bit_set()
819 /* Set the bit within the nodes mask */ in bit_set()
820 assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1); in bit_set()
821 assert(!(nodep->mask & (1 << (idx - nodep->idx)))); in bit_set()
822 nodep->mask |= 1 << (idx - nodep->idx); in bit_set()
823 s->num_set++; in bit_set()
828 /* Within the sparsebit array pointed to by s, clears the bit
839 /* Is there a node that describes the setting of this bit? */ in bit_clear()
845 * If a num_after bit, split the node, so that the bit is in bit_clear()
846 * part of a node mask. in bit_clear()
848 if (idx >= nodep->idx + MASK_BITS) in bit_clear()
849 nodep = node_split(s, idx & -MASK_BITS); in bit_clear()
852 * After node_split above, bit at idx should be within the mask. in bit_clear()
853 * Clear that bit. in bit_clear()
855 assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1); in bit_clear()
856 assert(nodep->mask & (1 << (idx - nodep->idx))); in bit_clear()
857 nodep->mask &= ~(1 << (idx - nodep->idx)); in bit_clear()
858 assert(s->num_set > 0 || sparsebit_all_set(s)); in bit_clear()
859 s->num_set--; in bit_clear()
865 * of the sub-tree of nodes pointed to by nodep. Each line of output
877 if (!nodep->parent) in dump_nodes()
879 else if (nodep == nodep->parent->left) in dump_nodes()
882 assert(nodep == nodep->parent->right); in dump_nodes()
885 fprintf(stream, "%*s---- %s nodep: %p\n", indent, "", node_type, nodep); in dump_nodes()
887 nodep->parent, nodep->left, nodep->right); in dump_nodes()
888 fprintf(stream, "%*s idx: 0x%lx mask: 0x%x num_after: 0x%lx\n", in dump_nodes()
889 indent, "", nodep->idx, nodep->mask, nodep->num_after); in dump_nodes()
892 if (nodep->left) in dump_nodes()
893 dump_nodes(stream, nodep->left, indent + 2); in dump_nodes()
896 if (nodep->right) in dump_nodes()
897 dump_nodes(stream, nodep->right, indent + 2); in dump_nodes()
903 int n1 = __builtin_ctz(nodep->mask & -leading); in node_first_set()
905 return nodep->idx + n1; in node_first_set()
911 int n1 = __builtin_ctz(~nodep->mask & -leading); in node_first_clear()
913 return nodep->idx + n1; in node_first_clear()
928 fprintf(stream, "%*sroot: %p\n", indent, "", s->root); in sparsebit_dump_internal()
929 fprintf(stream, "%*snum_set: 0x%lx\n", indent, "", s->num_set); in sparsebit_dump_internal()
931 if (s->root) in sparsebit_dump_internal()
932 dump_nodes(stream, s->root, indent); in sparsebit_dump_internal()
977 if (s->root) { in sparsebit_copy()
978 d->root = node_copy_subtree(s->root); in sparsebit_copy()
979 d->num_set = s->num_set; in sparsebit_copy()
990 assert(idx + num - 1 >= idx); in sparsebit_is_set_num()
992 /* With num > 0, the first bit must be set. */ in sparsebit_is_set_num()
996 /* Find the next cleared bit */ in sparsebit_is_set_num()
1002 * there are enough set bits between idx and the next cleared bit. in sparsebit_is_set_num()
1004 return next_cleared == 0 || next_cleared - idx >= num; in sparsebit_is_set_num()
1007 /* Returns whether the bit at the index given by idx. */
1021 assert(idx + num - 1 >= idx); in sparsebit_is_clear_num()
1023 /* With num > 0, the first bit must be cleared. */ in sparsebit_is_clear_num()
1027 /* Find the next set bit */ in sparsebit_is_clear_num()
1033 * there are enough cleared bits between idx and the next set bit. in sparsebit_is_clear_num()
1035 return next_set == 0 || next_set - idx >= num; in sparsebit_is_clear_num()
1040 * is 1 additional bit set beyond what can be represented in the return
1046 return s->num_set; in sparsebit_num_set()
1049 /* Returns whether any bit is set in the sparsebit array. */
1054 * is at least 1 bit set. in sparsebit_any_set()
1056 if (!s->root) in sparsebit_any_set()
1060 * Every node should have a non-zero mask. For now will in sparsebit_any_set()
1061 * just assure that the root node has a non-zero mask, in sparsebit_any_set()
1062 * which is a quick check that at least 1 bit is set. in sparsebit_any_set()
1064 assert(s->root->mask != 0); in sparsebit_any_set()
1065 assert(s->num_set > 0 || in sparsebit_any_set()
1066 (s->root->num_after == ((sparsebit_num_t) 0) - MASK_BITS && in sparsebit_any_set()
1067 s->root->mask == ~(mask_t) 0)); in sparsebit_any_set()
1084 /* Returns the index of the first set bit. Abort if no bits are set.
1090 /* Validate at least 1 bit is set */ in sparsebit_first_set()
1097 /* Returns the index of the first cleared bit. Abort if
1104 /* Validate at least 1 bit is cleared. */ in sparsebit_first_clear()
1109 if (!nodep1 || nodep1->idx > 0) in sparsebit_first_clear()
1112 /* Does the mask in the first node contain any cleared bits. */ in sparsebit_first_clear()
1113 if (nodep1->mask != ~(mask_t) 0) in sparsebit_first_clear()
1117 * All mask bits set in first node. If there isn't a second node in sparsebit_first_clear()
1118 * then the first cleared bit is the first bit after the bits in sparsebit_first_clear()
1124 * No second node. First cleared bit is first bit beyond in sparsebit_first_clear()
1127 assert(nodep1->mask == ~(mask_t) 0); in sparsebit_first_clear()
1128 assert(nodep1->idx + MASK_BITS + nodep1->num_after != (sparsebit_idx_t) 0); in sparsebit_first_clear()
1129 return nodep1->idx + MASK_BITS + nodep1->num_after; in sparsebit_first_clear()
1135 * of cleared bits between the nodes, and the first cleared bit in sparsebit_first_clear()
1136 * is the first bit within the gap. in sparsebit_first_clear()
1138 if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx) in sparsebit_first_clear()
1139 return nodep1->idx + MASK_BITS + nodep1->num_after; in sparsebit_first_clear()
1143 * Because it is adjacent, its mask should be non-zero. If all in sparsebit_first_clear()
1144 * its mask bits are set, then with it being adjacent, it should in sparsebit_first_clear()
1145 * have had the mask bits moved into the num_after setting of the in sparsebit_first_clear()
1151 /* Returns index of next bit set within s after the index given by prev.
1161 /* A bit after the highest index can't be set. */ in sparsebit_next_set()
1175 * Find node that describes setting of bit at lowest_possible. in sparsebit_next_set()
1179 for (nodep = s->root; nodep;) { in sparsebit_next_set()
1180 if ((nodep->idx + MASK_BITS + nodep->num_after - 1) in sparsebit_next_set()
1183 if (candidate->idx <= lowest_possible) { in sparsebit_next_set()
1187 nodep = nodep->left; in sparsebit_next_set()
1189 nodep = nodep->right; in sparsebit_next_set()
1195 assert(candidate->mask != 0); in sparsebit_next_set()
1200 * Candidate doesn't describe setting of bit at lowest_possible. in sparsebit_next_set()
1204 assert(candidate->idx > lowest_possible); in sparsebit_next_set()
1210 * Candidate describes setting of bit at lowest_possible. in sparsebit_next_set()
1211 * Note: although the node describes the setting of the bit in sparsebit_next_set()
1215 * a bit at or after an index of lowest_possible that is set. in sparsebit_next_set()
1217 start = lowest_possible - candidate->idx; in sparsebit_next_set()
1219 if (start < MASK_BITS && candidate->mask >= (1 << start)) in sparsebit_next_set()
1222 if (candidate->num_after) { in sparsebit_next_set()
1223 sparsebit_idx_t first_num_after_idx = candidate->idx + MASK_BITS; in sparsebit_next_set()
1230 * Although candidate node describes setting of bit at in sparsebit_next_set()
1233 * this, the next bit is the first bit in the next node, if in sparsebit_next_set()
1235 * there is no next set bit. in sparsebit_next_set()
1244 /* Returns index of next bit cleared within s after the index given by prev.
1254 /* A bit after the highest index can't be set. */ in sparsebit_next_clear()
1260 * If not, the bit at lowest_possible is cleared. in sparsebit_next_clear()
1266 /* Does a mask bit in node 1 describe the next cleared bit. */ in sparsebit_next_clear()
1267 for (idx = lowest_possible - nodep1->idx; idx < MASK_BITS; idx++) in sparsebit_next_clear()
1268 if (!(nodep1->mask & (1 << idx))) in sparsebit_next_clear()
1269 return nodep1->idx + idx; in sparsebit_next_clear()
1272 * Next cleared bit is not described by node 1. If there in sparsebit_next_clear()
1273 * isn't a next node, then next cleared bit is described in sparsebit_next_clear()
1274 * by bit after the bits described by the first node. in sparsebit_next_clear()
1278 return nodep1->idx + MASK_BITS + nodep1->num_after; in sparsebit_next_clear()
1283 * of cleared bits between the nodes, and the next cleared bit in sparsebit_next_clear()
1284 * is the first bit within the gap. in sparsebit_next_clear()
1286 if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx) in sparsebit_next_clear()
1287 return nodep1->idx + MASK_BITS + nodep1->num_after; in sparsebit_next_clear()
1291 * Because it is adjacent, its mask should be non-zero. If all in sparsebit_next_clear()
1292 * its mask bits are set, then with it being adjacent, it should in sparsebit_next_clear()
1293 * have had the mask bits moved into the num_after setting of the in sparsebit_next_clear()
1311 idx != 0 && idx + num - 1 >= idx; in sparsebit_next_set_num()
1346 idx != 0 && idx + num - 1 >= idx; in sparsebit_next_clear_num()
1369 /* Sets the bits * in the inclusive range idx through idx + num - 1. */
1380 assert(start + num - 1 >= start); in sparsebit_set_num()
1383 * Leading - bits before first mask boundary. in sparsebit_set_num()
1390 * of idx to be within the mask portion of a node. in sparsebit_set_num()
1391 * 2. Form mask of bits to be set. in sparsebit_set_num()
1392 * 3. Determine number of mask bits already set in the node in sparsebit_set_num()
1394 * 4. Set the appropriate mask bits within the node. in sparsebit_set_num()
1402 for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--) in sparsebit_set_num()
1405 /* Middle - bits spanning one or more entire mask */ in sparsebit_set_num()
1407 middle_end = middle_start + (n & -MASK_BITS) - 1; in sparsebit_set_num()
1414 * supported bit index. in sparsebit_set_num()
1421 next && (next->idx < middle_end); in sparsebit_set_num()
1423 assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end); in sparsebit_set_num()
1428 /* As needed set each of the mask bits */ in sparsebit_set_num()
1430 if (!(nodep->mask & (1 << n1))) { in sparsebit_set_num()
1431 nodep->mask |= 1 << n1; in sparsebit_set_num()
1432 s->num_set++; in sparsebit_set_num()
1436 s->num_set -= nodep->num_after; in sparsebit_set_num()
1437 nodep->num_after = middle_end - middle_start + 1 - MASK_BITS; in sparsebit_set_num()
1438 s->num_set += nodep->num_after; in sparsebit_set_num()
1443 n -= middle_end - middle_start + 1; in sparsebit_set_num()
1445 /* Trailing - bits at and beyond last mask boundary */ in sparsebit_set_num()
1447 for (; n > 0; idx++, n--) in sparsebit_set_num()
1451 /* Clears the bits * in the inclusive range idx through idx + num - 1. */
1462 assert(start + num - 1 >= start); in sparsebit_clear_num()
1464 /* Leading - bits before first mask boundary */ in sparsebit_clear_num()
1465 for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--) in sparsebit_clear_num()
1468 /* Middle - bits spanning one or more entire mask */ in sparsebit_clear_num()
1470 middle_end = middle_start + (n & -MASK_BITS) - 1; in sparsebit_clear_num()
1477 * supported bit index. in sparsebit_clear_num()
1484 next && (next->idx < middle_end); in sparsebit_clear_num()
1486 assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end); in sparsebit_clear_num()
1491 /* As needed clear each of the mask bits */ in sparsebit_clear_num()
1493 if (nodep->mask & (1 << n1)) { in sparsebit_clear_num()
1494 nodep->mask &= ~(1 << n1); in sparsebit_clear_num()
1495 s->num_set--; in sparsebit_clear_num()
1500 s->num_set -= nodep->num_after; in sparsebit_clear_num()
1501 nodep->num_after = 0; in sparsebit_clear_num()
1512 n -= middle_end - middle_start + 1; in sparsebit_clear_num()
1514 /* Trailing - bits at and beyond last mask boundary */ in sparsebit_clear_num()
1516 for (; n > 0; idx++, n--) in sparsebit_clear_num()
1520 /* Sets the bit at the index given by idx. */
1526 /* Clears the bit at the index given by idx. */
1573 /* Dumps to the FILE stream given by stream, the bit settings
1582 * are set. Note that a ':', instead of a '-' is used to specify a range of
1583 * contiguous bits. This is done because '-' is used to specify command-line
1584 * options, and sometimes ranges are specified as command-line arguments.
1604 /* For each group of bits in the mask */ in sparsebit_dump()
1606 if (nodep->mask & (1 << n1)) { in sparsebit_dump()
1607 low = high = nodep->idx + n1; in sparsebit_dump()
1610 if (nodep->mask & (1 << n1)) in sparsebit_dump()
1611 high = nodep->idx + n1; in sparsebit_dump()
1616 if ((n1 == MASK_BITS) && nodep->num_after) in sparsebit_dump()
1617 high += nodep->num_after; in sparsebit_dump()
1645 * If num_after and most significant-bit of mask is not in sparsebit_dump()
1649 if (!(nodep->mask & (1 << (MASK_BITS - 1))) && nodep->num_after) { in sparsebit_dump()
1650 low = nodep->idx + MASK_BITS; in sparsebit_dump()
1651 high = nodep->idx + MASK_BITS + nodep->num_after - 1; in sparsebit_dump()
1700 if (nodep->mask & (1 << n1)) in sparsebit_validate_internal()
1703 total_bits_set += nodep->num_after; in sparsebit_validate_internal()
1706 * Arbitrary choice as to whether a mask of 0 is allowed in sparsebit_validate_internal()
1710 * to not allow a mask of zero. in sparsebit_validate_internal()
1712 if (nodep->mask == 0) { in sparsebit_validate_internal()
1713 fprintf(stderr, "Node mask of zero, " in sparsebit_validate_internal()
1714 "nodep: %p nodep->mask: 0x%x", in sparsebit_validate_internal()
1715 nodep, nodep->mask); in sparsebit_validate_internal()
1722 * - the number of mask bits. The num_after member in sparsebit_validate_internal()
1723 * uses 0-based indexing and thus has no value that in sparsebit_validate_internal()
1725 * by requiring a non-zero mask. With a non-zero mask, in sparsebit_validate_internal()
1726 * MASK_BITS worth of bits are described by the mask, in sparsebit_validate_internal()
1729 * (~(sparsebit_num_t) 0) - MASK_BITS + 1 in sparsebit_validate_internal()
1731 if (nodep->num_after in sparsebit_validate_internal()
1732 > (~(sparsebit_num_t) 0) - MASK_BITS + 1) { in sparsebit_validate_internal()
1734 "nodep: %p nodep->num_after: 0x%lx", in sparsebit_validate_internal()
1735 nodep, nodep->num_after); in sparsebit_validate_internal()
1740 /* Validate node index is divisible by the mask size */ in sparsebit_validate_internal()
1741 if (nodep->idx % MASK_BITS) { in sparsebit_validate_internal()
1743 "mask size,\n" in sparsebit_validate_internal()
1744 " nodep: %p nodep->idx: 0x%lx " in sparsebit_validate_internal()
1746 nodep, nodep->idx, MASK_BITS); in sparsebit_validate_internal()
1755 if ((nodep->idx + MASK_BITS + nodep->num_after - 1) < nodep->idx) { in sparsebit_validate_internal()
1758 " nodep: %p nodep->idx: 0x%lx\n" in sparsebit_validate_internal()
1759 " MASK_BITS: %lu nodep->num_after: 0x%lx", in sparsebit_validate_internal()
1760 nodep, nodep->idx, MASK_BITS, nodep->num_after); in sparsebit_validate_internal()
1766 if (nodep->left) { in sparsebit_validate_internal()
1767 if (nodep->left->parent != nodep) { in sparsebit_validate_internal()
1770 " nodep: %p nodep->left: %p " in sparsebit_validate_internal()
1771 "nodep->left->parent: %p", in sparsebit_validate_internal()
1772 nodep, nodep->left, in sparsebit_validate_internal()
1773 nodep->left->parent); in sparsebit_validate_internal()
1779 if (nodep->right) { in sparsebit_validate_internal()
1780 if (nodep->right->parent != nodep) { in sparsebit_validate_internal()
1783 " nodep: %p nodep->right: %p " in sparsebit_validate_internal()
1784 "nodep->right->parent: %p", in sparsebit_validate_internal()
1785 nodep, nodep->right, in sparsebit_validate_internal()
1786 nodep->right->parent); in sparsebit_validate_internal()
1792 if (!nodep->parent) { in sparsebit_validate_internal()
1793 if (s->root != nodep) { in sparsebit_validate_internal()
1795 "s->root: %p nodep: %p", in sparsebit_validate_internal()
1796 s->root, nodep); in sparsebit_validate_internal()
1807 if (prev->idx >= nodep->idx) { in sparsebit_validate_internal()
1810 " prev: %p prev->idx: 0x%lx\n" in sparsebit_validate_internal()
1811 " nodep: %p nodep->idx: 0x%lx", in sparsebit_validate_internal()
1812 prev, prev->idx, nodep, nodep->idx); in sparsebit_validate_internal()
1821 if ((prev->idx + MASK_BITS + prev->num_after - 1) in sparsebit_validate_internal()
1822 >= nodep->idx) { in sparsebit_validate_internal()
1823 fprintf(stderr, "Previous node bit range " in sparsebit_validate_internal()
1824 "overlap with current node bit range,\n" in sparsebit_validate_internal()
1825 " prev: %p prev->idx: 0x%lx " in sparsebit_validate_internal()
1826 "prev->num_after: 0x%lx\n" in sparsebit_validate_internal()
1827 " nodep: %p nodep->idx: 0x%lx " in sparsebit_validate_internal()
1828 "nodep->num_after: 0x%lx\n" in sparsebit_validate_internal()
1830 prev, prev->idx, prev->num_after, in sparsebit_validate_internal()
1831 nodep, nodep->idx, nodep->num_after, in sparsebit_validate_internal()
1838 * When the node has all mask bits set, it shouldn't in sparsebit_validate_internal()
1839 * be adjacent to the last bit described by the in sparsebit_validate_internal()
1842 if (nodep->mask == ~(mask_t) 0 && in sparsebit_validate_internal()
1843 prev->idx + MASK_BITS + prev->num_after == nodep->idx) { in sparsebit_validate_internal()
1844 fprintf(stderr, "Current node has mask with " in sparsebit_validate_internal()
1847 " prev: %p prev->idx: 0x%lx " in sparsebit_validate_internal()
1848 "prev->num_after: 0x%lx\n" in sparsebit_validate_internal()
1849 " nodep: %p nodep->idx: 0x%lx " in sparsebit_validate_internal()
1850 "nodep->num_after: 0x%lx\n" in sparsebit_validate_internal()
1852 prev, prev->idx, prev->num_after, in sparsebit_validate_internal()
1853 nodep, nodep->idx, nodep->num_after, in sparsebit_validate_internal()
1867 if (s->num_set != total_bits_set) { in sparsebit_validate_internal()
1869 " s->num_set: 0x%lx total_bits_set: 0x%lx", in sparsebit_validate_internal()
1870 s->num_set, total_bits_set); in sparsebit_validate_internal()
1888 * afl-fuzz do the magic. :)
1906 for (i = num_ranges; --i >= 0; ) in get_value()
1919 num = last - first + 1; in operate()
1921 num = first - last + 1; in operate()
1923 last = first + num - 1; in operate()
1994 next = sparsebit_next_set(s, first - 1); in operate()
2009 next = sparsebit_next_clear(s, first - 1); in operate()