Lines Matching refs:idx
172 sparsebit_idx_t idx; /* index of least-significant bit in mask */ member
287 root->idx = subtree->idx; in node_copy_subtree()
310 static struct node *node_find(struct sparsebit *s, sparsebit_idx_t idx) in node_find() argument
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()
333 static struct node *node_add(struct sparsebit *s, sparsebit_idx_t idx) in node_add() argument
344 nodep->idx = idx & -MASK_BITS; in node_add()
358 if (idx < parentp->idx) { in node_add()
366 assert(idx > parentp->idx + MASK_BITS + parentp->num_after - 1); 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()
498 static struct node *node_split(struct sparsebit *s, sparsebit_idx_t idx) in node_split() argument
504 assert(!(idx % MASK_BITS)); in node_split()
510 nodep1 = node_find(s, idx); in node_split()
512 return node_add(s, idx); in node_split()
518 if (nodep1->idx == idx) in node_split()
530 offset = idx - (nodep1->idx + MASK_BITS); in node_split()
538 nodep2 = node_add(s, idx); in node_split()
650 assert(nodep->idx + MASK_BITS > nodep->idx); in node_reduce()
652 nodep->idx += MASK_BITS; in node_reduce()
687 prev->idx + MASK_BITS == nodep->idx) { in node_reduce()
701 prev_highest_bit = prev->idx + MASK_BITS - 1 + prev->num_after; in node_reduce()
702 if (prev_highest_bit + 1 == nodep->idx && in node_reduce()
759 if (next->idx == nodep->idx + MASK_BITS + nodep->num_after && in node_reduce()
779 bool sparsebit_is_set(struct sparsebit *s, sparsebit_idx_t idx) in sparsebit_is_set() argument
785 nodep = nodep->idx > idx ? nodep->left : nodep->right) in sparsebit_is_set()
786 if (idx >= nodep->idx && in sparsebit_is_set()
787 idx <= nodep->idx + MASK_BITS + nodep->num_after - 1) in sparsebit_is_set()
794 if (nodep->num_after && idx >= nodep->idx + MASK_BITS) in sparsebit_is_set()
798 assert(idx >= nodep->idx && idx - nodep->idx < MASK_BITS); in sparsebit_is_set()
799 return !!(nodep->mask & (1 << (idx - nodep->idx))); in sparsebit_is_set()
805 static void bit_set(struct sparsebit *s, sparsebit_idx_t idx) in bit_set() argument
810 if (sparsebit_is_set(s, idx)) in bit_set()
818 nodep = node_split(s, idx & -MASK_BITS); in bit_set()
821 assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1); in bit_set()
822 assert(!(nodep->mask & (1 << (idx - nodep->idx)))); in bit_set()
823 nodep->mask |= 1 << (idx - nodep->idx); in bit_set()
832 static void bit_clear(struct sparsebit *s, sparsebit_idx_t idx) in bit_clear() argument
837 if (!sparsebit_is_set(s, idx)) in bit_clear()
841 nodep = node_find(s, idx); in bit_clear()
849 if (idx >= nodep->idx + MASK_BITS) in bit_clear()
850 nodep = node_split(s, idx & -MASK_BITS); in bit_clear()
856 assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1); in bit_clear()
857 assert(nodep->mask & (1 << (idx - nodep->idx))); in bit_clear()
858 nodep->mask &= ~(1 << (idx - nodep->idx)); in bit_clear()
890 indent, "", nodep->idx, nodep->mask, nodep->num_after); in dump_nodes()
906 return nodep->idx + n1; in node_first_set()
914 return nodep->idx + n1; in node_first_clear()
986 sparsebit_idx_t idx, sparsebit_num_t num) in sparsebit_is_set_num() argument
991 assert(idx + num - 1 >= idx); in sparsebit_is_set_num()
994 if (!sparsebit_is_set(s, idx)) in sparsebit_is_set_num()
998 next_cleared = sparsebit_next_clear(s, idx); in sparsebit_is_set_num()
1005 return next_cleared == 0 || next_cleared - idx >= num; in sparsebit_is_set_num()
1010 sparsebit_idx_t idx) in sparsebit_is_clear() argument
1012 return !sparsebit_is_set(s, idx); in sparsebit_is_clear()
1017 sparsebit_idx_t idx, sparsebit_num_t num) in sparsebit_is_clear_num() argument
1022 assert(idx + num - 1 >= idx); in sparsebit_is_clear_num()
1025 if (!sparsebit_is_clear(s, idx)) in sparsebit_is_clear_num()
1029 next_set = sparsebit_next_set(s, idx); in sparsebit_is_clear_num()
1036 return next_set == 0 || next_set - idx >= num; in sparsebit_is_clear_num()
1110 if (!nodep1 || nodep1->idx > 0) in sparsebit_first_clear()
1129 assert(nodep1->idx + MASK_BITS + nodep1->num_after != (sparsebit_idx_t) 0); in sparsebit_first_clear()
1130 return nodep1->idx + MASK_BITS + nodep1->num_after; in sparsebit_first_clear()
1139 if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx) in sparsebit_first_clear()
1140 return nodep1->idx + MASK_BITS + nodep1->num_after; in sparsebit_first_clear()
1181 if ((nodep->idx + MASK_BITS + nodep->num_after - 1) in sparsebit_next_set()
1184 if (candidate->idx <= lowest_possible) { in sparsebit_next_set()
1205 assert(candidate->idx > lowest_possible); in sparsebit_next_set()
1218 start = lowest_possible - candidate->idx; in sparsebit_next_set()
1224 sparsebit_idx_t first_num_after_idx = candidate->idx + MASK_BITS; in sparsebit_next_set()
1252 sparsebit_idx_t idx; in sparsebit_next_clear() local
1268 for (idx = lowest_possible - nodep1->idx; idx < MASK_BITS; idx++) in sparsebit_next_clear()
1269 if (!(nodep1->mask & (1 << idx))) in sparsebit_next_clear()
1270 return nodep1->idx + idx; in sparsebit_next_clear()
1279 return nodep1->idx + MASK_BITS + nodep1->num_after; in sparsebit_next_clear()
1287 if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx) in sparsebit_next_clear()
1288 return nodep1->idx + MASK_BITS + nodep1->num_after; in sparsebit_next_clear()
1307 sparsebit_idx_t idx; in sparsebit_next_set_num() local
1311 for (idx = sparsebit_next_set(s, start); in sparsebit_next_set_num()
1312 idx != 0 && idx + num - 1 >= idx; in sparsebit_next_set_num()
1313 idx = sparsebit_next_set(s, idx)) { in sparsebit_next_set_num()
1314 assert(sparsebit_is_set(s, idx)); in sparsebit_next_set_num()
1320 if (sparsebit_is_set_num(s, idx, num)) in sparsebit_next_set_num()
1321 return idx; in sparsebit_next_set_num()
1327 idx = sparsebit_next_clear(s, idx); in sparsebit_next_set_num()
1328 if (idx == 0) in sparsebit_next_set_num()
1342 sparsebit_idx_t idx; in sparsebit_next_clear_num() local
1346 for (idx = sparsebit_next_clear(s, start); in sparsebit_next_clear_num()
1347 idx != 0 && idx + num - 1 >= idx; in sparsebit_next_clear_num()
1348 idx = sparsebit_next_clear(s, idx)) { in sparsebit_next_clear_num()
1349 assert(sparsebit_is_clear(s, idx)); in sparsebit_next_clear_num()
1355 if (sparsebit_is_clear_num(s, idx, num)) in sparsebit_next_clear_num()
1356 return idx; in sparsebit_next_clear_num()
1362 idx = sparsebit_next_set(s, idx); in sparsebit_next_clear_num()
1363 if (idx == 0) in sparsebit_next_clear_num()
1376 sparsebit_idx_t idx; in sparsebit_set_num() local
1403 for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--) in sparsebit_set_num()
1404 bit_set(s, idx); in sparsebit_set_num()
1407 middle_start = idx; in sparsebit_set_num()
1422 next && (next->idx < middle_end); in sparsebit_set_num()
1424 assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end); in sparsebit_set_num()
1443 idx = middle_end + 1; in sparsebit_set_num()
1448 for (; n > 0; idx++, n--) in sparsebit_set_num()
1449 bit_set(s, idx); in sparsebit_set_num()
1458 sparsebit_idx_t idx; in sparsebit_clear_num() local
1466 for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--) in sparsebit_clear_num()
1467 bit_clear(s, idx); in sparsebit_clear_num()
1470 middle_start = idx; in sparsebit_clear_num()
1485 next && (next->idx < middle_end); in sparsebit_clear_num()
1487 assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end); in sparsebit_clear_num()
1512 idx = middle_end + 1; in sparsebit_clear_num()
1517 for (; n > 0; idx++, n--) in sparsebit_clear_num()
1518 bit_clear(s, idx); in sparsebit_clear_num()
1522 void sparsebit_set(struct sparsebit *s, sparsebit_idx_t idx) in sparsebit_set() argument
1524 sparsebit_set_num(s, idx, 1); in sparsebit_set()
1528 void sparsebit_clear(struct sparsebit *s, sparsebit_idx_t idx) in sparsebit_clear() argument
1530 sparsebit_clear_num(s, idx, 1); in sparsebit_clear()
1608 low = high = nodep->idx + n1; in sparsebit_dump()
1612 high = nodep->idx + n1; in sparsebit_dump()
1651 low = nodep->idx + MASK_BITS; in sparsebit_dump()
1652 high = nodep->idx + MASK_BITS + nodep->num_after - 1; in sparsebit_dump()
1742 if (nodep->idx % MASK_BITS) { in sparsebit_validate_internal()
1747 nodep, nodep->idx, MASK_BITS); in sparsebit_validate_internal()
1756 if ((nodep->idx + MASK_BITS + nodep->num_after - 1) < nodep->idx) { in sparsebit_validate_internal()
1761 nodep, nodep->idx, MASK_BITS, nodep->num_after); in sparsebit_validate_internal()
1808 if (prev->idx >= nodep->idx) { in sparsebit_validate_internal()
1813 prev, prev->idx, nodep, nodep->idx); in sparsebit_validate_internal()
1822 if ((prev->idx + MASK_BITS + prev->num_after - 1) in sparsebit_validate_internal()
1823 >= nodep->idx) { in sparsebit_validate_internal()
1831 prev, prev->idx, prev->num_after, in sparsebit_validate_internal()
1832 nodep, nodep->idx, nodep->num_after, in sparsebit_validate_internal()
1844 prev->idx + MASK_BITS + prev->num_after == nodep->idx) { in sparsebit_validate_internal()
1853 prev, prev->idx, prev->num_after, in sparsebit_validate_internal()
1854 nodep, nodep->idx, nodep->num_after, in sparsebit_validate_internal()
1903 static bool get_value(sparsebit_idx_t idx) in get_value() argument
1908 if (ranges[i].first <= idx && idx <= ranges[i].last) in get_value()