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);
650 assert(nodep->idx + MASK_BITS > nodep->idx);
652 nodep->idx += MASK_BITS;
687 prev->idx + MASK_BITS == nodep->idx) {
701 prev_highest_bit = prev->idx + MASK_BITS - 1 + prev->num_after;
702 if (prev_highest_bit + 1 == nodep->idx &&
759 if (next->idx == nodep->idx + MASK_BITS + nodep->num_after &&
776 /* Returns whether the bit at the index given by idx, within the
779 bool sparsebit_is_set(struct sparsebit *s, sparsebit_idx_t idx)
783 /* Find the node that describes the setting of the bit at idx */
785 nodep = nodep->idx > idx ? nodep->left : nodep->right)
786 if (idx >= nodep->idx &&
787 idx <= nodep->idx + MASK_BITS + nodep->num_after - 1)
794 if (nodep->num_after && idx >= nodep->idx + MASK_BITS)
798 assert(idx >= nodep->idx && idx - nodep->idx < MASK_BITS);
799 return !!(nodep->mask & (1 << (idx - nodep->idx)));
803 * at the index given by idx.
805 static void bit_set(struct sparsebit *s, sparsebit_idx_t idx)
810 if (sparsebit_is_set(s, idx))
814 * Get a node where the bit at idx is described by the mask.
818 nodep = node_split(s, idx & -MASK_BITS);
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);
830 * at the index given by idx.
832 static void bit_clear(struct sparsebit *s, sparsebit_idx_t idx)
837 if (!sparsebit_is_set(s, idx))
841 nodep = node_find(s, idx);
849 if (idx >= nodep->idx + MASK_BITS)
850 nodep = node_split(s, idx & -MASK_BITS);
853 * After node_split above, bit at idx should be within the mask.
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));
889 fprintf(stream, "%*s idx: 0x%lx mask: 0x%x num_after: 0x%lx\n",
890 indent, "", nodep->idx, nodep->mask, nodep->num_after);
906 return nodep->idx + n1;
914 return nodep->idx + n1;
984 /* Returns whether num consecutive bits starting at idx are all set. */
986 sparsebit_idx_t idx, sparsebit_num_t num)
991 assert(idx + num - 1 >= idx);
994 if (!sparsebit_is_set(s, idx))
998 next_cleared = sparsebit_next_clear(s, idx);
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.
1005 return next_cleared == 0 || next_cleared - idx >= num;
1008 /* Returns whether the bit at the index given by idx. */
1010 sparsebit_idx_t idx)
1012 return !sparsebit_is_set(s, idx);
1015 /* Returns whether num consecutive bits starting at idx are all cleared. */
1017 sparsebit_idx_t idx, sparsebit_num_t num)
1022 assert(idx + num - 1 >= idx);
1025 if (!sparsebit_is_clear(s, idx))
1029 next_set = sparsebit_next_set(s, idx);
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.
1036 return next_set == 0 || next_set - idx >= num;
1110 if (!nodep1 || nodep1->idx > 0)
1129 assert(nodep1->idx + MASK_BITS + nodep1->num_after != (sparsebit_idx_t) 0);
1130 return nodep1->idx + MASK_BITS + nodep1->num_after;
1139 if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx)
1140 return nodep1->idx + MASK_BITS + nodep1->num_after;
1181 if ((nodep->idx + MASK_BITS + nodep->num_after - 1)
1184 if (candidate->idx <= lowest_possible) {
1205 assert(candidate->idx > lowest_possible);
1218 start = lowest_possible - candidate->idx;
1224 sparsebit_idx_t first_num_after_idx = candidate->idx + MASK_BITS;
1252 sparsebit_idx_t idx;
1268 for (idx = lowest_possible - nodep1->idx; idx < MASK_BITS; idx++)
1269 if (!(nodep1->mask & (1 << idx)))
1270 return nodep1->idx + idx;
1279 return nodep1->idx + MASK_BITS + nodep1->num_after;
1287 if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx)
1288 return nodep1->idx + MASK_BITS + nodep1->num_after;
1307 sparsebit_idx_t idx;
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));
1317 * Does the sequence of bits starting at idx consist of
1320 if (sparsebit_is_set_num(s, idx, num))
1321 return idx;
1324 * Sequence of set bits at idx isn't large enough.
1327 idx = sparsebit_next_clear(s, idx);
1328 if (idx == 0)
1342 sparsebit_idx_t idx;
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));
1352 * Does the sequence of bits starting at idx consist of
1355 if (sparsebit_is_clear_num(s, idx, num))
1356 return idx;
1359 * Sequence of cleared bits at idx isn't large enough.
1362 idx = sparsebit_next_set(s, idx);
1363 if (idx == 0)
1370 /* Sets the bits * in the inclusive range idx through idx + num - 1. */
1376 sparsebit_idx_t idx;
1391 * of idx to be within the mask portion of a node.
1403 for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--)
1404 bit_set(s, idx);
1407 middle_start = idx;
1422 next && (next->idx < middle_end);
1424 assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end);
1443 idx = middle_end + 1;
1448 for (; n > 0; idx++, n--)
1449 bit_set(s, idx);
1452 /* Clears the bits * in the inclusive range idx through idx + num - 1. */
1458 sparsebit_idx_t idx;
1466 for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--)
1467 bit_clear(s, idx);
1470 middle_start = idx;
1485 next && (next->idx < middle_end);
1487 assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end);
1512 idx = middle_end + 1;
1517 for (; n > 0; idx++, n--)
1518 bit_clear(s, idx);
1521 /* Sets the bit at the index given by idx. */
1522 void sparsebit_set(struct sparsebit *s, sparsebit_idx_t idx)
1524 sparsebit_set_num(s, idx, 1);
1527 /* Clears the bit at the index given by idx. */
1528 void sparsebit_clear(struct sparsebit *s, sparsebit_idx_t idx)
1530 sparsebit_clear_num(s, idx, 1);
1608 low = high = nodep->idx + n1;
1612 high = nodep->idx + n1;
1651 low = nodep->idx + MASK_BITS;
1652 high = nodep->idx + MASK_BITS + nodep->num_after - 1;
1742 if (nodep->idx % MASK_BITS) {
1745 " nodep: %p nodep->idx: 0x%lx "
1747 nodep, nodep->idx, MASK_BITS);
1756 if ((nodep->idx + MASK_BITS + nodep->num_after - 1) < nodep->idx) {
1759 " nodep: %p nodep->idx: 0x%lx\n"
1761 nodep, nodep->idx, MASK_BITS, nodep->num_after);
1808 if (prev->idx >= nodep->idx) {
1811 " prev: %p prev->idx: 0x%lx\n"
1812 " nodep: %p nodep->idx: 0x%lx",
1813 prev, prev->idx, nodep, nodep->idx);
1822 if ((prev->idx + MASK_BITS + prev->num_after - 1)
1823 >= nodep->idx) {
1826 " prev: %p prev->idx: 0x%lx "
1828 " nodep: %p nodep->idx: 0x%lx "
1831 prev, prev->idx, prev->num_after,
1832 nodep, nodep->idx, nodep->num_after,
1844 prev->idx + MASK_BITS + prev->num_after == nodep->idx) {
1848 " prev: %p prev->idx: 0x%lx "
1850 " nodep: %p nodep->idx: 0x%lx "
1853 prev, prev->idx, prev->num_after,
1854 nodep, nodep->idx, nodep->num_after,
1904 static bool get_value(sparsebit_idx_t idx)
1909 if (ranges[i].first <= idx && idx <= ranges[i].last)