Lines Matching refs:idx
31 * sparsebit_is_set(s, idx)
32 * sparsebit_is_clear(s, idx)
38 * sparsebit_set(s, idx)
39 * sparsebit_clear(s, idx)
40 * sparsebit_set_num(s, idx, num);
41 * sparsebit_clear_num(s, idx, num);
46 * sparsebit_idx_t idx;
48 * idx = sparsebit_first_set(s);
51 * idx = sparsebit_next_set(s, idx);
52 * } while (idx != 0);
82 * sparsebit_idx_t idx;
86 * The idx member contains the bit index of the first bit described by this
88 * The setting of the bit at idx + n, where 0 <= n < 32, is located in the
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
102 * node 0 - idx: 0x0 mask: 0xffffffff num_after: 0xffffffffffffffc0
103 * node 1 - idx: 0xffffffffffffffe0 mask: 0x3fffffff num_after: 0
129 * (idx + MASK_BITS + num_after - 1) <= ((sparsebit_idx_t) 0) - 1)
142 * start: node->idx
143 * end (inclusive): node->idx + MASK_BITS + node->num_after - 1;
172 sparsebit_idx_t idx; /* index of least-significant bit in mask */
287 root->idx = subtree->idx;
306 * of the bit given by idx. A node describes the setting of a bit if its
310 static struct node *node_find(struct sparsebit *s, sparsebit_idx_t idx)
314 /* Find the node that describes the setting of the bit at idx */
316 nodep = nodep->idx > idx ? nodep->left : nodep->right) {
317 if (idx >= nodep->idx &&
318 idx <= nodep->idx + MASK_BITS + nodep->num_after - 1)
326 * + A node that describes the setting of idx is not already present.
329 * by idx. Returns a pointer to the newly added node.
333 static struct node *node_add(struct sparsebit *s, sparsebit_idx_t idx)
344 nodep->idx = idx & -MASK_BITS;
358 if (idx < parentp->idx) {
366 assert(idx > parentp->idx + MASK_BITS + parentp->num_after - 1);
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;
492 /* Splits the node containing the bit at idx so that there is a node
496 * idx must start of a mask boundary.
498 static struct node *node_split(struct sparsebit *s, sparsebit_idx_t idx)
504 assert(!(idx % MASK_BITS));
507 * Is there a node that describes the setting of idx?
510 nodep1 = node_find(s, idx);
512 return node_add(s, idx);
518 if (nodep1->idx == idx)
530 offset = idx - (nodep1->idx + MASK_BITS);
538 nodep2 = node_add(s, idx);
649 assert(nodep->idx + MASK_BITS > nodep->idx);
651 nodep->idx += MASK_BITS;
686 prev->idx + MASK_BITS == nodep->idx) {
700 prev_highest_bit = prev->idx + MASK_BITS - 1 + prev->num_after;
701 if (prev_highest_bit + 1 == nodep->idx &&
758 if (next->idx == nodep->idx + MASK_BITS + nodep->num_after &&
775 /* Returns whether the bit at the index given by idx, within the
778 bool sparsebit_is_set(struct sparsebit *s, sparsebit_idx_t idx)
782 /* Find the node that describes the setting of the bit at idx */
784 nodep = nodep->idx > idx ? nodep->left : nodep->right)
785 if (idx >= nodep->idx &&
786 idx <= nodep->idx + MASK_BITS + nodep->num_after - 1)
793 if (nodep->num_after && idx >= nodep->idx + MASK_BITS)
797 assert(idx >= nodep->idx && idx - nodep->idx < MASK_BITS);
798 return !!(nodep->mask & (1 << (idx - nodep->idx)));
802 * at the index given by idx.
804 static void bit_set(struct sparsebit *s, sparsebit_idx_t idx)
809 if (sparsebit_is_set(s, idx))
813 * Get a node where the bit at idx is described by the mask.
817 nodep = node_split(s, idx & -MASK_BITS);
820 assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1);
821 assert(!(nodep->mask & (1 << (idx - nodep->idx))));
822 nodep->mask |= 1 << (idx - nodep->idx);
829 * at the index given by idx.
831 static void bit_clear(struct sparsebit *s, sparsebit_idx_t idx)
836 if (!sparsebit_is_set(s, idx))
840 nodep = node_find(s, idx);
848 if (idx >= nodep->idx + MASK_BITS)
849 nodep = node_split(s, idx & -MASK_BITS);
852 * After node_split above, bit at idx should be within the mask.
855 assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1);
856 assert(nodep->mask & (1 << (idx - nodep->idx)));
857 nodep->mask &= ~(1 << (idx - nodep->idx));
888 fprintf(stream, "%*s idx: 0x%lx mask: 0x%x num_after: 0x%lx\n",
889 indent, "", nodep->idx, nodep->mask, nodep->num_after);
905 return nodep->idx + n1;
913 return nodep->idx + n1;
983 /* Returns whether num consecutive bits starting at idx are all set. */
985 sparsebit_idx_t idx, sparsebit_num_t num)
990 assert(idx + num - 1 >= idx);
993 if (!sparsebit_is_set(s, idx))
997 next_cleared = sparsebit_next_clear(s, idx);
1000 * If no cleared bits beyond idx, then there are at least num
1001 * set bits. idx + num doesn't wrap. Otherwise check if
1002 * there are enough set bits between idx and the next cleared bit.
1004 return next_cleared == 0 || next_cleared - idx >= num;
1007 /* Returns whether the bit at the index given by idx. */
1009 sparsebit_idx_t idx)
1011 return !sparsebit_is_set(s, idx);
1014 /* Returns whether num consecutive bits starting at idx are all cleared. */
1016 sparsebit_idx_t idx, sparsebit_num_t num)
1021 assert(idx + num - 1 >= idx);
1024 if (!sparsebit_is_clear(s, idx))
1028 next_set = sparsebit_next_set(s, idx);
1031 * If no set bits beyond idx, then there are at least num
1032 * cleared bits. idx + num doesn't wrap. Otherwise check if
1033 * there are enough cleared bits between idx and the next set bit.
1035 return next_set == 0 || next_set - idx >= num;
1109 if (!nodep1 || nodep1->idx > 0)
1128 assert(nodep1->idx + MASK_BITS + nodep1->num_after != (sparsebit_idx_t) 0);
1129 return nodep1->idx + MASK_BITS + nodep1->num_after;
1138 if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx)
1139 return nodep1->idx + MASK_BITS + nodep1->num_after;
1180 if ((nodep->idx + MASK_BITS + nodep->num_after - 1)
1183 if (candidate->idx <= lowest_possible) {
1204 assert(candidate->idx > lowest_possible);
1217 start = lowest_possible - candidate->idx;
1223 sparsebit_idx_t first_num_after_idx = candidate->idx + MASK_BITS;
1251 sparsebit_idx_t idx;
1267 for (idx = lowest_possible - nodep1->idx; idx < MASK_BITS; idx++)
1268 if (!(nodep1->mask & (1 << idx)))
1269 return nodep1->idx + idx;
1278 return nodep1->idx + MASK_BITS + nodep1->num_after;
1286 if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx)
1287 return nodep1->idx + MASK_BITS + nodep1->num_after;
1306 sparsebit_idx_t idx;
1310 for (idx = sparsebit_next_set(s, start);
1311 idx != 0 && idx + num - 1 >= idx;
1312 idx = sparsebit_next_set(s, idx)) {
1313 assert(sparsebit_is_set(s, idx));
1316 * Does the sequence of bits starting at idx consist of
1319 if (sparsebit_is_set_num(s, idx, num))
1320 return idx;
1323 * Sequence of set bits at idx isn't large enough.
1326 idx = sparsebit_next_clear(s, idx);
1327 if (idx == 0)
1341 sparsebit_idx_t idx;
1345 for (idx = sparsebit_next_clear(s, start);
1346 idx != 0 && idx + num - 1 >= idx;
1347 idx = sparsebit_next_clear(s, idx)) {
1348 assert(sparsebit_is_clear(s, idx));
1351 * Does the sequence of bits starting at idx consist of
1354 if (sparsebit_is_clear_num(s, idx, num))
1355 return idx;
1358 * Sequence of cleared bits at idx isn't large enough.
1361 idx = sparsebit_next_set(s, idx);
1362 if (idx == 0)
1369 /* Sets the bits * in the inclusive range idx through idx + num - 1. */
1375 sparsebit_idx_t idx;
1390 * of idx to be within the mask portion of a node.
1402 for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--)
1403 bit_set(s, idx);
1406 middle_start = idx;
1421 next && (next->idx < middle_end);
1423 assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end);
1442 idx = middle_end + 1;
1447 for (; n > 0; idx++, n--)
1448 bit_set(s, idx);
1451 /* Clears the bits * in the inclusive range idx through idx + num - 1. */
1457 sparsebit_idx_t idx;
1465 for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--)
1466 bit_clear(s, idx);
1469 middle_start = idx;
1484 next && (next->idx < middle_end);
1486 assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end);
1511 idx = middle_end + 1;
1516 for (; n > 0; idx++, n--)
1517 bit_clear(s, idx);
1520 /* Sets the bit at the index given by idx. */
1521 void sparsebit_set(struct sparsebit *s, sparsebit_idx_t idx)
1523 sparsebit_set_num(s, idx, 1);
1526 /* Clears the bit at the index given by idx. */
1527 void sparsebit_clear(struct sparsebit *s, sparsebit_idx_t idx)
1529 sparsebit_clear_num(s, idx, 1);
1607 low = high = nodep->idx + n1;
1611 high = nodep->idx + n1;
1650 low = nodep->idx + MASK_BITS;
1651 high = nodep->idx + MASK_BITS + nodep->num_after - 1;
1741 if (nodep->idx % MASK_BITS) {
1744 " nodep: %p nodep->idx: 0x%lx "
1746 nodep, nodep->idx, MASK_BITS);
1755 if ((nodep->idx + MASK_BITS + nodep->num_after - 1) < nodep->idx) {
1758 " nodep: %p nodep->idx: 0x%lx\n"
1760 nodep, nodep->idx, MASK_BITS, nodep->num_after);
1807 if (prev->idx >= nodep->idx) {
1810 " prev: %p prev->idx: 0x%lx\n"
1811 " nodep: %p nodep->idx: 0x%lx",
1812 prev, prev->idx, nodep, nodep->idx);
1821 if ((prev->idx + MASK_BITS + prev->num_after - 1)
1822 >= nodep->idx) {
1825 " prev: %p prev->idx: 0x%lx "
1827 " nodep: %p nodep->idx: 0x%lx "
1830 prev, prev->idx, prev->num_after,
1831 nodep, nodep->idx, nodep->num_after,
1843 prev->idx + MASK_BITS + prev->num_after == nodep->idx) {
1847 " prev: %p prev->idx: 0x%lx "
1849 " nodep: %p nodep->idx: 0x%lx "
1852 prev, prev->idx, prev->num_after,
1853 nodep, nodep->idx, nodep->num_after,
1902 static bool get_value(sparsebit_idx_t idx)
1907 if (ranges[i].first <= idx && idx <= ranges[i].last)