Lines Matching refs:nodep
197 static sparsebit_num_t node_num_set(struct node *nodep) in node_num_set() argument
199 return nodep->num_after + __builtin_popcount(nodep->mask); in node_num_set()
207 struct node *nodep; in node_first() local
209 for (nodep = s->root; nodep && nodep->left; nodep = nodep->left) in node_first()
212 return nodep; in node_first()
221 struct node *nodep = np; in node_next() local
227 if (nodep->right) { in node_next()
228 for (nodep = nodep->right; nodep->left; nodep = nodep->left) in node_next()
230 return nodep; in node_next()
237 while (nodep->parent && nodep == nodep->parent->right) in node_next()
238 nodep = nodep->parent; in node_next()
240 return nodep->parent; in node_next()
249 struct node *nodep = np; in node_prev() local
255 if (nodep->left) { in node_prev()
256 for (nodep = nodep->left; nodep->right; nodep = nodep->right) in node_prev()
258 return (struct node *) nodep; in node_prev()
265 while (nodep->parent && nodep == nodep->parent->left) in node_prev()
266 nodep = nodep->parent; in node_prev()
268 return (struct node *) nodep->parent; in node_prev()
312 struct node *nodep; in node_find() local
315 for (nodep = s->root; nodep; in node_find()
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()
322 return nodep; in node_find()
335 struct node *nodep, *parentp, *prev; in node_add() local
338 nodep = calloc(1, sizeof(*nodep)); in node_add()
339 if (!nodep) { in node_add()
344 nodep->idx = idx & -MASK_BITS; in node_add()
348 s->root = nodep; in node_add()
349 return nodep; in node_add()
360 parentp->left = nodep; in node_add()
361 nodep->parent = parentp; in node_add()
368 parentp->right = nodep; in node_add()
369 nodep->parent = parentp; in node_add()
381 prev = node_prev(s, nodep); in node_add()
382 while (prev && prev->idx + MASK_BITS + prev->num_after - 1 >= nodep->idx) { in node_add()
384 - nodep->idx; in node_add()
387 assert(!(nodep->mask & (1 << n1))); in node_add()
388 nodep->mask |= (1 << n1); in node_add()
392 return nodep; in node_add()
409 static void node_rm(struct sparsebit *s, struct node *nodep) in node_rm() argument
414 num_set = node_num_set(nodep); in node_rm()
416 s->num_set -= node_num_set(nodep); in node_rm()
419 if (nodep->left && nodep->right) { in node_rm()
424 for (tmp = nodep->right; tmp->left; tmp = tmp->left) in node_rm()
426 tmp->left = nodep->left; in node_rm()
427 nodep->left = NULL; in node_rm()
432 if (nodep->left) { in node_rm()
433 if (!nodep->parent) { in node_rm()
434 s->root = nodep->left; in node_rm()
435 nodep->left->parent = NULL; in node_rm()
437 nodep->left->parent = nodep->parent; in node_rm()
438 if (nodep == nodep->parent->left) in node_rm()
439 nodep->parent->left = nodep->left; in node_rm()
441 assert(nodep == nodep->parent->right); in node_rm()
442 nodep->parent->right = nodep->left; in node_rm()
446 nodep->parent = nodep->left = nodep->right = NULL; in node_rm()
447 free(nodep); in node_rm()
454 if (nodep->right) { in node_rm()
455 if (!nodep->parent) { in node_rm()
456 s->root = nodep->right; in node_rm()
457 nodep->right->parent = NULL; in node_rm()
459 nodep->right->parent = nodep->parent; in node_rm()
460 if (nodep == nodep->parent->left) in node_rm()
461 nodep->parent->left = nodep->right; in node_rm()
463 assert(nodep == nodep->parent->right); in node_rm()
464 nodep->parent->right = nodep->right; in node_rm()
468 nodep->parent = nodep->left = nodep->right = NULL; in node_rm()
469 free(nodep); in node_rm()
475 if (!nodep->parent) { in node_rm()
478 if (nodep->parent->left == nodep) in node_rm()
479 nodep->parent->left = NULL; in node_rm()
481 assert(nodep == nodep->parent->right); in node_rm()
482 nodep->parent->right = NULL; in node_rm()
486 nodep->parent = nodep->left = nodep->right = NULL; in node_rm()
487 free(nodep); in node_rm()
599 static void node_reduce(struct sparsebit *s, struct node *nodep) in node_reduce() argument
610 if (nodep->mask == 0 && nodep->num_after == 0) { in node_reduce()
632 tmp = node_next(s, nodep); in node_reduce()
634 tmp = node_prev(s, nodep); in node_reduce()
636 node_rm(s, nodep); in node_reduce()
637 nodep = NULL; in node_reduce()
639 nodep = tmp; in node_reduce()
648 if (nodep->mask == 0) { in node_reduce()
649 assert(nodep->num_after != 0); in node_reduce()
650 assert(nodep->idx + MASK_BITS > nodep->idx); in node_reduce()
652 nodep->idx += MASK_BITS; in node_reduce()
654 if (nodep->num_after >= MASK_BITS) { in node_reduce()
655 nodep->mask = ~0; in node_reduce()
656 nodep->num_after -= MASK_BITS; in node_reduce()
658 nodep->mask = (1u << nodep->num_after) - 1; in node_reduce()
659 nodep->num_after = 0; in node_reduce()
670 prev = node_prev(s, nodep); in node_reduce()
686 if (nodep->mask + 1 == 0 && in node_reduce()
687 prev->idx + MASK_BITS == nodep->idx) { in node_reduce()
688 prev->num_after += MASK_BITS + nodep->num_after; in node_reduce()
689 nodep->mask = 0; in node_reduce()
690 nodep->num_after = 0; in node_reduce()
702 if (prev_highest_bit + 1 == nodep->idx && in node_reduce()
703 (nodep->mask | (nodep->mask >> 1)) == nodep->mask) { in node_reduce()
712 = __builtin_popcount(nodep->mask); in node_reduce()
714 ((1ULL << num_contiguous) - 1) == nodep->mask); in node_reduce()
717 nodep->mask = 0; in node_reduce()
733 prev->num_after += nodep->num_after; in node_reduce()
734 nodep->num_after = 0; in node_reduce()
746 next = node_next(s, nodep); in node_reduce()
759 if (next->idx == nodep->idx + MASK_BITS + nodep->num_after && in node_reduce()
761 nodep->num_after += MASK_BITS; in node_reduce()
763 nodep->num_after += next->num_after; in node_reduce()
773 } while (nodep && reduction_performed); in node_reduce()
781 struct node *nodep; in sparsebit_is_set() local
784 for (nodep = s->root; nodep; in sparsebit_is_set()
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()
807 struct node *nodep; in bit_set() local
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()
826 node_reduce(s, nodep); in bit_set()
834 struct node *nodep; in bit_clear() local
841 nodep = node_find(s, idx); in bit_clear()
842 if (!nodep) 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()
862 node_reduce(s, nodep); in bit_clear()
872 static void dump_nodes(FILE *stream, struct node *nodep, in dump_nodes() argument
878 if (!nodep->parent) in dump_nodes()
880 else if (nodep == nodep->parent->left) in dump_nodes()
883 assert(nodep == nodep->parent->right); in dump_nodes()
886 fprintf(stream, "%*s---- %s nodep: %p\n", indent, "", node_type, nodep); in dump_nodes()
888 nodep->parent, nodep->left, nodep->right); in dump_nodes()
890 indent, "", nodep->idx, nodep->mask, nodep->num_after); in dump_nodes()
893 if (nodep->left) in dump_nodes()
894 dump_nodes(stream, nodep->left, indent + 2); in dump_nodes()
897 if (nodep->right) in dump_nodes()
898 dump_nodes(stream, nodep->right, indent + 2); in dump_nodes()
901 static inline sparsebit_idx_t node_first_set(struct node *nodep, int start) in node_first_set() argument
904 int n1 = __builtin_ctz(nodep->mask & -leading); in node_first_set()
906 return nodep->idx + n1; in node_first_set()
909 static inline sparsebit_idx_t node_first_clear(struct node *nodep, int start) in node_first_clear() argument
912 int n1 = __builtin_ctz(~nodep->mask & -leading); in node_first_clear()
914 return nodep->idx + n1; in node_first_clear()
1089 struct node *nodep; in sparsebit_first_set() local
1094 nodep = node_first(s); in sparsebit_first_set()
1095 return node_first_set(nodep, 0); in sparsebit_first_set()
1160 struct node *nodep; in sparsebit_next_set() local
1180 for (nodep = s->root; nodep;) { in sparsebit_next_set()
1181 if ((nodep->idx + MASK_BITS + nodep->num_after - 1) in sparsebit_next_set()
1183 candidate = nodep; in sparsebit_next_set()
1188 nodep = nodep->left; in sparsebit_next_set()
1190 nodep = nodep->right; in sparsebit_next_set()
1374 struct node *nodep, *next; in sparsebit_set_num() local
1410 nodep = node_split(s, middle_start); in sparsebit_set_num()
1421 for (next = node_next(s, nodep); in sparsebit_set_num()
1423 next = node_next(s, nodep)) { in sparsebit_set_num()
1431 if (!(nodep->mask & (1 << n1))) { in sparsebit_set_num()
1432 nodep->mask |= 1 << n1; in sparsebit_set_num()
1437 s->num_set -= nodep->num_after; in sparsebit_set_num()
1438 nodep->num_after = middle_end - middle_start + 1 - MASK_BITS; in sparsebit_set_num()
1439 s->num_set += nodep->num_after; in sparsebit_set_num()
1441 node_reduce(s, nodep); in sparsebit_set_num()
1456 struct node *nodep, *next; in sparsebit_clear_num() local
1473 nodep = node_split(s, middle_start); in sparsebit_clear_num()
1484 for (next = node_next(s, nodep); in sparsebit_clear_num()
1486 next = node_next(s, nodep)) { in sparsebit_clear_num()
1494 if (nodep->mask & (1 << n1)) { in sparsebit_clear_num()
1495 nodep->mask &= ~(1 << n1); in sparsebit_clear_num()
1501 s->num_set -= nodep->num_after; in sparsebit_clear_num()
1502 nodep->num_after = 0; in sparsebit_clear_num()
1509 node_reduce(s, nodep); in sparsebit_clear_num()
1510 nodep = NULL; in sparsebit_clear_num()
1592 struct node *nodep; in sparsebit_dump() local
1601 for (nodep = node_first(s); nodep; nodep = node_next(s, nodep)) { in sparsebit_dump()
1607 if (nodep->mask & (1 << n1)) { in sparsebit_dump()
1608 low = high = nodep->idx + n1; in sparsebit_dump()
1611 if (nodep->mask & (1 << n1)) in sparsebit_dump()
1612 high = nodep->idx + n1; in sparsebit_dump()
1617 if ((n1 == MASK_BITS) && nodep->num_after) in sparsebit_dump()
1618 high += nodep->num_after; in sparsebit_dump()
1650 if (!(nodep->mask & (1 << (MASK_BITS - 1))) && nodep->num_after) { 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()
1688 struct node *nodep, *prev = NULL; in sparsebit_validate_internal() local
1693 for (nodep = node_first(s); nodep; in sparsebit_validate_internal()
1694 prev = nodep, nodep = node_next(s, nodep)) { in sparsebit_validate_internal()
1701 if (nodep->mask & (1 << n1)) in sparsebit_validate_internal()
1704 total_bits_set += nodep->num_after; in sparsebit_validate_internal()
1713 if (nodep->mask == 0) { in sparsebit_validate_internal()
1716 nodep, nodep->mask); in sparsebit_validate_internal()
1732 if (nodep->num_after in sparsebit_validate_internal()
1736 nodep, nodep->num_after); in sparsebit_validate_internal()
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()
1767 if (nodep->left) { in sparsebit_validate_internal()
1768 if (nodep->left->parent != nodep) { in sparsebit_validate_internal()
1773 nodep, nodep->left, in sparsebit_validate_internal()
1774 nodep->left->parent); in sparsebit_validate_internal()
1780 if (nodep->right) { in sparsebit_validate_internal()
1781 if (nodep->right->parent != nodep) { in sparsebit_validate_internal()
1786 nodep, nodep->right, in sparsebit_validate_internal()
1787 nodep->right->parent); in sparsebit_validate_internal()
1793 if (!nodep->parent) { in sparsebit_validate_internal()
1794 if (s->root != nodep) { in sparsebit_validate_internal()
1797 s->root, nodep); 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()
1823 >= nodep->idx) { in sparsebit_validate_internal()
1832 nodep, nodep->idx, nodep->num_after, in sparsebit_validate_internal()
1843 if (nodep->mask == ~(mask_t) 0 && in sparsebit_validate_internal()
1844 prev->idx + MASK_BITS + prev->num_after == nodep->idx) { in sparsebit_validate_internal()
1854 nodep, nodep->idx, nodep->num_after, in sparsebit_validate_internal()