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()
649 assert(nodep->idx + MASK_BITS > nodep->idx); in node_reduce()
651 nodep->idx += MASK_BITS; in node_reduce()
686 prev->idx + MASK_BITS == nodep->idx) { 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()
758 if (next->idx == nodep->idx + MASK_BITS + nodep->num_after && in node_reduce()
778 bool sparsebit_is_set(struct sparsebit *s, sparsebit_idx_t idx) in sparsebit_is_set() argument
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()
793 if (nodep->num_after && idx >= nodep->idx + MASK_BITS) 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()
804 static void bit_set(struct sparsebit *s, sparsebit_idx_t idx) in bit_set() argument
809 if (sparsebit_is_set(s, idx)) in bit_set()
817 nodep = node_split(s, idx & -MASK_BITS); 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()
831 static void bit_clear(struct sparsebit *s, sparsebit_idx_t idx) in bit_clear() argument
836 if (!sparsebit_is_set(s, idx)) in bit_clear()
840 nodep = node_find(s, idx); in bit_clear()
848 if (idx >= nodep->idx + MASK_BITS) in bit_clear()
849 nodep = node_split(s, idx & -MASK_BITS); 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()
889 indent, "", nodep->idx, nodep->mask, nodep->num_after); in dump_nodes()
905 return nodep->idx + n1; in node_first_set()
913 return nodep->idx + n1; in node_first_clear()
985 sparsebit_idx_t idx, sparsebit_num_t num) in sparsebit_is_set_num() argument
990 assert(idx + num - 1 >= idx); in sparsebit_is_set_num()
993 if (!sparsebit_is_set(s, idx)) in sparsebit_is_set_num()
997 next_cleared = sparsebit_next_clear(s, idx); in sparsebit_is_set_num()
1004 return next_cleared == 0 || next_cleared - idx >= num; in sparsebit_is_set_num()
1009 sparsebit_idx_t idx) in sparsebit_is_clear() argument
1011 return !sparsebit_is_set(s, idx); in sparsebit_is_clear()
1016 sparsebit_idx_t idx, sparsebit_num_t num) in sparsebit_is_clear_num() argument
1021 assert(idx + num - 1 >= idx); in sparsebit_is_clear_num()
1024 if (!sparsebit_is_clear(s, idx)) in sparsebit_is_clear_num()
1028 next_set = sparsebit_next_set(s, idx); in sparsebit_is_clear_num()
1035 return next_set == 0 || next_set - idx >= num; in sparsebit_is_clear_num()
1109 if (!nodep1 || nodep1->idx > 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()
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()
1180 if ((nodep->idx + MASK_BITS + nodep->num_after - 1) in sparsebit_next_set()
1183 if (candidate->idx <= lowest_possible) { in sparsebit_next_set()
1204 assert(candidate->idx > lowest_possible); in sparsebit_next_set()
1217 start = lowest_possible - candidate->idx; in sparsebit_next_set()
1223 sparsebit_idx_t first_num_after_idx = candidate->idx + MASK_BITS; in sparsebit_next_set()
1251 sparsebit_idx_t idx; in sparsebit_next_clear() local
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()
1278 return nodep1->idx + MASK_BITS + nodep1->num_after; 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()
1306 sparsebit_idx_t idx; in sparsebit_next_set_num() local
1310 for (idx = sparsebit_next_set(s, start); in sparsebit_next_set_num()
1311 idx != 0 && idx + num - 1 >= idx; in sparsebit_next_set_num()
1312 idx = sparsebit_next_set(s, idx)) { in sparsebit_next_set_num()
1313 assert(sparsebit_is_set(s, idx)); in sparsebit_next_set_num()
1319 if (sparsebit_is_set_num(s, idx, num)) in sparsebit_next_set_num()
1320 return idx; in sparsebit_next_set_num()
1326 idx = sparsebit_next_clear(s, idx); in sparsebit_next_set_num()
1327 if (idx == 0) in sparsebit_next_set_num()
1341 sparsebit_idx_t idx; in sparsebit_next_clear_num() local
1345 for (idx = sparsebit_next_clear(s, start); in sparsebit_next_clear_num()
1346 idx != 0 && idx + num - 1 >= idx; in sparsebit_next_clear_num()
1347 idx = sparsebit_next_clear(s, idx)) { in sparsebit_next_clear_num()
1348 assert(sparsebit_is_clear(s, idx)); in sparsebit_next_clear_num()
1354 if (sparsebit_is_clear_num(s, idx, num)) in sparsebit_next_clear_num()
1355 return idx; in sparsebit_next_clear_num()
1361 idx = sparsebit_next_set(s, idx); in sparsebit_next_clear_num()
1362 if (idx == 0) in sparsebit_next_clear_num()
1375 sparsebit_idx_t idx; in sparsebit_set_num() local
1402 for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--) in sparsebit_set_num()
1403 bit_set(s, idx); in sparsebit_set_num()
1406 middle_start = idx; 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()
1442 idx = middle_end + 1; in sparsebit_set_num()
1447 for (; n > 0; idx++, n--) in sparsebit_set_num()
1448 bit_set(s, idx); in sparsebit_set_num()
1457 sparsebit_idx_t idx; in sparsebit_clear_num() local
1465 for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--) in sparsebit_clear_num()
1466 bit_clear(s, idx); in sparsebit_clear_num()
1469 middle_start = idx; 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()
1511 idx = middle_end + 1; in sparsebit_clear_num()
1516 for (; n > 0; idx++, n--) in sparsebit_clear_num()
1517 bit_clear(s, idx); in sparsebit_clear_num()
1521 void sparsebit_set(struct sparsebit *s, sparsebit_idx_t idx) in sparsebit_set() argument
1523 sparsebit_set_num(s, idx, 1); in sparsebit_set()
1527 void sparsebit_clear(struct sparsebit *s, sparsebit_idx_t idx) in sparsebit_clear() argument
1529 sparsebit_clear_num(s, idx, 1); in sparsebit_clear()
1607 low = high = nodep->idx + n1; in sparsebit_dump()
1611 high = nodep->idx + n1; 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()
1741 if (nodep->idx % MASK_BITS) { 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()
1760 nodep, nodep->idx, MASK_BITS, nodep->num_after); in sparsebit_validate_internal()
1807 if (prev->idx >= nodep->idx) { 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()
1830 prev, prev->idx, prev->num_after, in sparsebit_validate_internal()
1831 nodep, nodep->idx, nodep->num_after, in sparsebit_validate_internal()
1843 prev->idx + MASK_BITS + prev->num_after == nodep->idx) { 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()
1902 static bool get_value(sparsebit_idx_t idx) in get_value() argument
1907 if (ranges[i].first <= idx && idx <= ranges[i].last) in get_value()