173 	sparsebit_idx_t idx; /* index of least-significant bit in mask */  member
288 	root->idx = subtree->idx;  in node_copy_subtree()
311 static struct node *node_find(struct sparsebit *s, sparsebit_idx_t idx)  in node_find()  argument
317 	     nodep = nodep->idx > idx ? nodep->left : nodep->right) {  in node_find()
318 		if (idx >= nodep->idx &&  in node_find()
319 		    idx <= nodep->idx + MASK_BITS + nodep->num_after - 1)  in node_find()
334 static struct node *node_add(struct sparsebit *s, sparsebit_idx_t idx)  in node_add()  argument
345 	nodep->idx = idx & -MASK_BITS;  in node_add()
359 		if (idx < parentp->idx) {  in node_add()
367 			assert(idx > parentp->idx + MASK_BITS + parentp->num_after - 1);  in node_add()
383 	while (prev && prev->idx + MASK_BITS + prev->num_after - 1 >= nodep->idx) {  in node_add()
384 		unsigned int n1 = (prev->idx + MASK_BITS + prev->num_after - 1)  in node_add()
385 			- nodep->idx;  in node_add()
499 static struct node *node_split(struct sparsebit *s, sparsebit_idx_t idx)  in node_split()  argument
505 	assert(!(idx % MASK_BITS));  in node_split()
511 	nodep1 = node_find(s, idx);  in node_split()
513 		return node_add(s, idx);  in node_split()
519 	if (nodep1->idx == idx)  in node_split()
531 	offset = idx - (nodep1->idx + MASK_BITS);  in node_split()
539 	nodep2 = node_add(s, idx);  in node_split()
651 			assert(nodep->idx + MASK_BITS > nodep->idx);  in node_reduce()
653 			nodep->idx += MASK_BITS;  in node_reduce()
688 			    prev->idx + MASK_BITS == nodep->idx) {  in node_reduce()
702 			prev_highest_bit = prev->idx + MASK_BITS - 1 + prev->num_after;  in node_reduce()
703 			if (prev_highest_bit + 1 == nodep->idx &&  in node_reduce()
760 			if (next->idx == nodep->idx + MASK_BITS + nodep->num_after &&  in node_reduce()
780 bool sparsebit_is_set(struct sparsebit *s, sparsebit_idx_t idx)  in sparsebit_is_set()  argument
786 	     nodep = nodep->idx > idx ? nodep->left : nodep->right)  in sparsebit_is_set()
787 		if (idx >= nodep->idx &&  in sparsebit_is_set()
788 		    idx <= nodep->idx + MASK_BITS + nodep->num_after - 1)  in sparsebit_is_set()
795 	if (nodep->num_after && idx >= nodep->idx + MASK_BITS)  in sparsebit_is_set()
799 	assert(idx >= nodep->idx && idx - nodep->idx < MASK_BITS);  in sparsebit_is_set()
800 	return !!(nodep->mask & (1 << (idx - nodep->idx)));  in sparsebit_is_set()
806 static void bit_set(struct sparsebit *s, sparsebit_idx_t idx)  in bit_set()  argument
811 	if (sparsebit_is_set(s, idx))  in bit_set()
819 	nodep = node_split(s, idx & -MASK_BITS);  in bit_set()
822 	assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1);  in bit_set()
823 	assert(!(nodep->mask & (1 << (idx - nodep->idx))));  in bit_set()
824 	nodep->mask |= 1 << (idx - nodep->idx);  in bit_set()
833 static void bit_clear(struct sparsebit *s, sparsebit_idx_t idx)  in bit_clear()  argument
838 	if (!sparsebit_is_set(s, idx))  in bit_clear()
842 	nodep = node_find(s, idx);  in bit_clear()
850 	if (idx >= nodep->idx + MASK_BITS)  in bit_clear()
851 		nodep = node_split(s, idx & -MASK_BITS);  in bit_clear()
857 	assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1);  in bit_clear()
858 	assert(nodep->mask & (1 << (idx - nodep->idx)));  in bit_clear()
859 	nodep->mask &= ~(1 << (idx - nodep->idx));  in bit_clear()
891 		indent, "", nodep->idx, nodep->mask, nodep->num_after);  in dump_nodes()
907 	return nodep->idx + n1;  in node_first_set()
915 	return nodep->idx + n1;  in node_first_clear()
987 	sparsebit_idx_t idx, sparsebit_num_t num)  in sparsebit_is_set_num()  argument
992 	assert(idx + num - 1 >= idx);  in sparsebit_is_set_num()
995 	if (!sparsebit_is_set(s, idx))  in sparsebit_is_set_num()
999 	next_cleared = sparsebit_next_clear(s, idx);  in sparsebit_is_set_num()
1006 	return next_cleared == 0 || next_cleared - idx >= num;  in sparsebit_is_set_num()
1011 	sparsebit_idx_t idx)  in sparsebit_is_clear()  argument
1013 	return !sparsebit_is_set(s, idx);  in sparsebit_is_clear()
1018 	sparsebit_idx_t idx, sparsebit_num_t num)  in sparsebit_is_clear_num()  argument
1023 	assert(idx + num - 1 >= idx);  in sparsebit_is_clear_num()
1026 	if (!sparsebit_is_clear(s, idx))  in sparsebit_is_clear_num()
1030 	next_set = sparsebit_next_set(s, idx);  in sparsebit_is_clear_num()
1037 	return next_set == 0 || next_set - idx >= num;  in sparsebit_is_clear_num()
1111 	if (!nodep1 || nodep1->idx > 0)  in sparsebit_first_clear()
1130 		assert(nodep1->idx + MASK_BITS + nodep1->num_after != (sparsebit_idx_t) 0);  in sparsebit_first_clear()
1131 		return nodep1->idx + MASK_BITS + nodep1->num_after;  in sparsebit_first_clear()
1140 	if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx)  in sparsebit_first_clear()
1141 		return nodep1->idx + MASK_BITS + nodep1->num_after;  in sparsebit_first_clear()
1182 		if ((nodep->idx + MASK_BITS + nodep->num_after - 1)  in sparsebit_next_set()
1185 			if (candidate->idx <= lowest_possible) {  in sparsebit_next_set()
1206 		assert(candidate->idx > lowest_possible);  in sparsebit_next_set()
1219 	start = lowest_possible - candidate->idx;  in sparsebit_next_set()
1225 		sparsebit_idx_t first_num_after_idx = candidate->idx + MASK_BITS;  in sparsebit_next_set()
1253 	sparsebit_idx_t idx;  in sparsebit_next_clear()  local
1269 	for (idx = lowest_possible - nodep1->idx; idx < MASK_BITS; idx++)  in sparsebit_next_clear()
1270 		if (!(nodep1->mask & (1 << idx)))  in sparsebit_next_clear()
1271 			return nodep1->idx + idx;  in sparsebit_next_clear()
1280 		return nodep1->idx + MASK_BITS + nodep1->num_after;  in sparsebit_next_clear()
1288 	if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx)  in sparsebit_next_clear()
1289 		return nodep1->idx + MASK_BITS + nodep1->num_after;  in sparsebit_next_clear()
1308 	sparsebit_idx_t idx;  in sparsebit_next_set_num()  local
1312 	for (idx = sparsebit_next_set(s, start);  in sparsebit_next_set_num()
1313 		idx != 0 && idx + num - 1 >= idx;  in sparsebit_next_set_num()
1314 		idx = sparsebit_next_set(s, idx)) {  in sparsebit_next_set_num()
1315 		assert(sparsebit_is_set(s, idx));  in sparsebit_next_set_num()
1321 		if (sparsebit_is_set_num(s, idx, num))  in sparsebit_next_set_num()
1322 			return idx;  in sparsebit_next_set_num()
1328 		idx = sparsebit_next_clear(s, idx);  in sparsebit_next_set_num()
1329 		if (idx == 0)  in sparsebit_next_set_num()
1343 	sparsebit_idx_t idx;  in sparsebit_next_clear_num()  local
1347 	for (idx = sparsebit_next_clear(s, start);  in sparsebit_next_clear_num()
1348 		idx != 0 && idx + num - 1 >= idx;  in sparsebit_next_clear_num()
1349 		idx = sparsebit_next_clear(s, idx)) {  in sparsebit_next_clear_num()
1350 		assert(sparsebit_is_clear(s, idx));  in sparsebit_next_clear_num()
1356 		if (sparsebit_is_clear_num(s, idx, num))  in sparsebit_next_clear_num()
1357 			return idx;  in sparsebit_next_clear_num()
1363 		idx = sparsebit_next_set(s, idx);  in sparsebit_next_clear_num()
1364 		if (idx == 0)  in sparsebit_next_clear_num()
1377 	sparsebit_idx_t idx;  in sparsebit_set_num()  local
1404 	for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--)  in sparsebit_set_num()
1405 		bit_set(s, idx);  in sparsebit_set_num()
1408 	middle_start = idx;  in sparsebit_set_num()
1423 			next && (next->idx < middle_end);  in sparsebit_set_num()
1425 			assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end);  in sparsebit_set_num()
1444 	idx = middle_end + 1;  in sparsebit_set_num()
1449 	for (; n > 0; idx++, n--)  in sparsebit_set_num()
1450 		bit_set(s, idx);  in sparsebit_set_num()
1459 	sparsebit_idx_t idx;  in sparsebit_clear_num()  local
1467 	for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--)  in sparsebit_clear_num()
1468 		bit_clear(s, idx);  in sparsebit_clear_num()
1471 	middle_start = idx;  in sparsebit_clear_num()
1486 			next && (next->idx < middle_end);  in sparsebit_clear_num()
1488 			assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end);  in sparsebit_clear_num()
1513 	idx = middle_end + 1;  in sparsebit_clear_num()
1518 	for (; n > 0; idx++, n--)  in sparsebit_clear_num()
1519 		bit_clear(s, idx);  in sparsebit_clear_num()
1523 void sparsebit_set(struct sparsebit *s, sparsebit_idx_t idx)  in sparsebit_set()  argument
1525 	sparsebit_set_num(s, idx, 1);  in sparsebit_set()
1529 void sparsebit_clear(struct sparsebit *s, sparsebit_idx_t idx)  in sparsebit_clear()  argument
1531 	sparsebit_clear_num(s, idx, 1);  in sparsebit_clear()
1609 				low = high = nodep->idx + n1;  in sparsebit_dump()
1613 						high = nodep->idx + n1;  in sparsebit_dump()
1652 			low = nodep->idx + MASK_BITS;  in sparsebit_dump()
1653 			high = nodep->idx + MASK_BITS + nodep->num_after - 1;  in sparsebit_dump()
1743 		if (nodep->idx % MASK_BITS) {  in sparsebit_validate_internal()
1748 				nodep, nodep->idx, MASK_BITS);  in sparsebit_validate_internal()
1757 		if ((nodep->idx + MASK_BITS + nodep->num_after - 1) < nodep->idx) {  in sparsebit_validate_internal()
1762 				nodep, nodep->idx, MASK_BITS, nodep->num_after);  in sparsebit_validate_internal()
1809 			if (prev->idx >= nodep->idx) {  in sparsebit_validate_internal()
1814 					prev, prev->idx, nodep, nodep->idx);  in sparsebit_validate_internal()
1823 			if ((prev->idx + MASK_BITS + prev->num_after - 1)  in sparsebit_validate_internal()
1824 				>= nodep->idx) {  in sparsebit_validate_internal()
1832 					prev, prev->idx, prev->num_after,  in sparsebit_validate_internal()
1833 					nodep, nodep->idx, nodep->num_after,  in sparsebit_validate_internal()
1845 			    prev->idx + MASK_BITS + prev->num_after == nodep->idx) {  in sparsebit_validate_internal()
1854 					prev, prev->idx, prev->num_after,  in sparsebit_validate_internal()
1855 					nodep, nodep->idx, nodep->num_after,  in sparsebit_validate_internal()
1905 static bool get_value(sparsebit_idx_t idx)  in get_value()  argument
1910 		if (ranges[i].first <= idx && idx <= ranges[i].last)  in get_value()