Lines Matching refs:nodep
198 static sparsebit_num_t node_num_set(struct node *nodep) in node_num_set() argument
200 return nodep->num_after + __builtin_popcount(nodep->mask); in node_num_set()
208 struct node *nodep; in node_first() local
210 for (nodep = s->root; nodep && nodep->left; nodep = nodep->left) in node_first()
213 return nodep; in node_first()
222 struct node *nodep = np; in node_next() local
228 if (nodep->right) { in node_next()
229 for (nodep = nodep->right; nodep->left; nodep = nodep->left) in node_next()
231 return nodep; in node_next()
238 while (nodep->parent && nodep == nodep->parent->right) in node_next()
239 nodep = nodep->parent; in node_next()
241 return nodep->parent; in node_next()
250 struct node *nodep = np; in node_prev() local
256 if (nodep->left) { in node_prev()
257 for (nodep = nodep->left; nodep->right; nodep = nodep->right) in node_prev()
259 return (struct node *) nodep; in node_prev()
266 while (nodep->parent && nodep == nodep->parent->left) in node_prev()
267 nodep = nodep->parent; in node_prev()
269 return (struct node *) nodep->parent; in node_prev()
313 struct node *nodep; in node_find() local
316 for (nodep = s->root; nodep; in node_find()
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()
323 return nodep; in node_find()
336 struct node *nodep, *parentp, *prev; in node_add() local
339 nodep = calloc(1, sizeof(*nodep)); in node_add()
340 if (!nodep) { in node_add()
345 nodep->idx = idx & -MASK_BITS; in node_add()
349 s->root = nodep; in node_add()
350 return nodep; in node_add()
361 parentp->left = nodep; in node_add()
362 nodep->parent = parentp; in node_add()
369 parentp->right = nodep; in node_add()
370 nodep->parent = parentp; in node_add()
382 prev = node_prev(s, nodep); in node_add()
383 while (prev && prev->idx + MASK_BITS + prev->num_after - 1 >= nodep->idx) { in node_add()
385 - nodep->idx; in node_add()
388 assert(!(nodep->mask & (1 << n1))); in node_add()
389 nodep->mask |= (1 << n1); in node_add()
393 return nodep; in node_add()
410 static void node_rm(struct sparsebit *s, struct node *nodep) in node_rm() argument
415 num_set = node_num_set(nodep); in node_rm()
417 s->num_set -= node_num_set(nodep); in node_rm()
420 if (nodep->left && nodep->right) { in node_rm()
425 for (tmp = nodep->right; tmp->left; tmp = tmp->left) in node_rm()
427 tmp->left = nodep->left; in node_rm()
428 nodep->left = NULL; in node_rm()
433 if (nodep->left) { in node_rm()
434 if (!nodep->parent) { in node_rm()
435 s->root = nodep->left; in node_rm()
436 nodep->left->parent = NULL; in node_rm()
438 nodep->left->parent = nodep->parent; in node_rm()
439 if (nodep == nodep->parent->left) in node_rm()
440 nodep->parent->left = nodep->left; in node_rm()
442 assert(nodep == nodep->parent->right); in node_rm()
443 nodep->parent->right = nodep->left; in node_rm()
447 nodep->parent = nodep->left = nodep->right = NULL; in node_rm()
448 free(nodep); in node_rm()
455 if (nodep->right) { in node_rm()
456 if (!nodep->parent) { in node_rm()
457 s->root = nodep->right; in node_rm()
458 nodep->right->parent = NULL; in node_rm()
460 nodep->right->parent = nodep->parent; in node_rm()
461 if (nodep == nodep->parent->left) in node_rm()
462 nodep->parent->left = nodep->right; in node_rm()
464 assert(nodep == nodep->parent->right); in node_rm()
465 nodep->parent->right = nodep->right; in node_rm()
469 nodep->parent = nodep->left = nodep->right = NULL; in node_rm()
470 free(nodep); in node_rm()
476 if (!nodep->parent) { in node_rm()
479 if (nodep->parent->left == nodep) in node_rm()
480 nodep->parent->left = NULL; in node_rm()
482 assert(nodep == nodep->parent->right); in node_rm()
483 nodep->parent->right = NULL; in node_rm()
487 nodep->parent = nodep->left = nodep->right = NULL; in node_rm()
488 free(nodep); in node_rm()
600 static void node_reduce(struct sparsebit *s, struct node *nodep) in node_reduce() argument
611 if (nodep->mask == 0 && nodep->num_after == 0) { in node_reduce()
633 tmp = node_next(s, nodep); in node_reduce()
635 tmp = node_prev(s, nodep); in node_reduce()
637 node_rm(s, nodep); in node_reduce()
638 nodep = NULL; in node_reduce()
640 nodep = tmp; in node_reduce()
649 if (nodep->mask == 0) { in node_reduce()
650 assert(nodep->num_after != 0); in node_reduce()
651 assert(nodep->idx + MASK_BITS > nodep->idx); in node_reduce()
653 nodep->idx += MASK_BITS; in node_reduce()
655 if (nodep->num_after >= MASK_BITS) { in node_reduce()
656 nodep->mask = ~0; in node_reduce()
657 nodep->num_after -= MASK_BITS; in node_reduce()
659 nodep->mask = (1u << nodep->num_after) - 1; in node_reduce()
660 nodep->num_after = 0; in node_reduce()
671 prev = node_prev(s, nodep); in node_reduce()
687 if (nodep->mask + 1 == 0 && in node_reduce()
688 prev->idx + MASK_BITS == nodep->idx) { in node_reduce()
689 prev->num_after += MASK_BITS + nodep->num_after; in node_reduce()
690 nodep->mask = 0; in node_reduce()
691 nodep->num_after = 0; in node_reduce()
703 if (prev_highest_bit + 1 == nodep->idx && in node_reduce()
704 (nodep->mask | (nodep->mask >> 1)) == nodep->mask) { in node_reduce()
713 = __builtin_popcount(nodep->mask); in node_reduce()
715 ((1ULL << num_contiguous) - 1) == nodep->mask); in node_reduce()
718 nodep->mask = 0; in node_reduce()
734 prev->num_after += nodep->num_after; in node_reduce()
735 nodep->num_after = 0; in node_reduce()
747 next = node_next(s, nodep); in node_reduce()
760 if (next->idx == nodep->idx + MASK_BITS + nodep->num_after && in node_reduce()
762 nodep->num_after += MASK_BITS; in node_reduce()
764 nodep->num_after += next->num_after; in node_reduce()
774 } while (nodep && reduction_performed); in node_reduce()
782 struct node *nodep; in sparsebit_is_set() local
785 for (nodep = s->root; nodep; in sparsebit_is_set()
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()
808 struct node *nodep; in bit_set() local
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()
827 node_reduce(s, nodep); in bit_set()
835 struct node *nodep; in bit_clear() local
842 nodep = node_find(s, idx); in bit_clear()
843 if (!nodep) 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()
863 node_reduce(s, nodep); in bit_clear()
873 static void dump_nodes(FILE *stream, struct node *nodep, in dump_nodes() argument
879 if (!nodep->parent) in dump_nodes()
881 else if (nodep == nodep->parent->left) in dump_nodes()
884 assert(nodep == nodep->parent->right); in dump_nodes()
887 fprintf(stream, "%*s---- %s nodep: %p\n", indent, "", node_type, nodep); in dump_nodes()
889 nodep->parent, nodep->left, nodep->right); in dump_nodes()
891 indent, "", nodep->idx, nodep->mask, nodep->num_after); in dump_nodes()
894 if (nodep->left) in dump_nodes()
895 dump_nodes(stream, nodep->left, indent + 2); in dump_nodes()
898 if (nodep->right) in dump_nodes()
899 dump_nodes(stream, nodep->right, indent + 2); in dump_nodes()
902 static inline sparsebit_idx_t node_first_set(struct node *nodep, int start) in node_first_set() argument
905 int n1 = __builtin_ctz(nodep->mask & -leading); in node_first_set()
907 return nodep->idx + n1; in node_first_set()
910 static inline sparsebit_idx_t node_first_clear(struct node *nodep, int start) in node_first_clear() argument
913 int n1 = __builtin_ctz(~nodep->mask & -leading); in node_first_clear()
915 return nodep->idx + n1; in node_first_clear()
1090 struct node *nodep; in sparsebit_first_set() local
1095 nodep = node_first(s); in sparsebit_first_set()
1096 return node_first_set(nodep, 0); in sparsebit_first_set()
1161 struct node *nodep; in sparsebit_next_set() local
1181 for (nodep = s->root; nodep;) { in sparsebit_next_set()
1182 if ((nodep->idx + MASK_BITS + nodep->num_after - 1) in sparsebit_next_set()
1184 candidate = nodep; in sparsebit_next_set()
1189 nodep = nodep->left; in sparsebit_next_set()
1191 nodep = nodep->right; in sparsebit_next_set()
1375 struct node *nodep, *next; in sparsebit_set_num() local
1411 nodep = node_split(s, middle_start); in sparsebit_set_num()
1422 for (next = node_next(s, nodep); in sparsebit_set_num()
1424 next = node_next(s, nodep)) { in sparsebit_set_num()
1432 if (!(nodep->mask & (1 << n1))) { in sparsebit_set_num()
1433 nodep->mask |= 1 << n1; in sparsebit_set_num()
1438 s->num_set -= nodep->num_after; in sparsebit_set_num()
1439 nodep->num_after = middle_end - middle_start + 1 - MASK_BITS; in sparsebit_set_num()
1440 s->num_set += nodep->num_after; in sparsebit_set_num()
1442 node_reduce(s, nodep); in sparsebit_set_num()
1457 struct node *nodep, *next; in sparsebit_clear_num() local
1474 nodep = node_split(s, middle_start); in sparsebit_clear_num()
1485 for (next = node_next(s, nodep); in sparsebit_clear_num()
1487 next = node_next(s, nodep)) { in sparsebit_clear_num()
1495 if (nodep->mask & (1 << n1)) { in sparsebit_clear_num()
1496 nodep->mask &= ~(1 << n1); in sparsebit_clear_num()
1502 s->num_set -= nodep->num_after; in sparsebit_clear_num()
1503 nodep->num_after = 0; in sparsebit_clear_num()
1510 node_reduce(s, nodep); in sparsebit_clear_num()
1511 nodep = NULL; in sparsebit_clear_num()
1593 struct node *nodep; in sparsebit_dump() local
1602 for (nodep = node_first(s); nodep; nodep = node_next(s, nodep)) { in sparsebit_dump()
1608 if (nodep->mask & (1 << n1)) { in sparsebit_dump()
1609 low = high = nodep->idx + n1; in sparsebit_dump()
1612 if (nodep->mask & (1 << n1)) in sparsebit_dump()
1613 high = nodep->idx + n1; in sparsebit_dump()
1618 if ((n1 == MASK_BITS) && nodep->num_after) in sparsebit_dump()
1619 high += nodep->num_after; in sparsebit_dump()
1651 if (!(nodep->mask & (1 << (MASK_BITS - 1))) && nodep->num_after) { 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()
1689 struct node *nodep, *prev = NULL; in sparsebit_validate_internal() local
1694 for (nodep = node_first(s); nodep; in sparsebit_validate_internal()
1695 prev = nodep, nodep = node_next(s, nodep)) { in sparsebit_validate_internal()
1702 if (nodep->mask & (1 << n1)) in sparsebit_validate_internal()
1705 total_bits_set += nodep->num_after; in sparsebit_validate_internal()
1714 if (nodep->mask == 0) { in sparsebit_validate_internal()
1717 nodep, nodep->mask); in sparsebit_validate_internal()
1733 if (nodep->num_after in sparsebit_validate_internal()
1737 nodep, nodep->num_after); in sparsebit_validate_internal()
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()
1768 if (nodep->left) { in sparsebit_validate_internal()
1769 if (nodep->left->parent != nodep) { in sparsebit_validate_internal()
1774 nodep, nodep->left, in sparsebit_validate_internal()
1775 nodep->left->parent); in sparsebit_validate_internal()
1781 if (nodep->right) { in sparsebit_validate_internal()
1782 if (nodep->right->parent != nodep) { in sparsebit_validate_internal()
1787 nodep, nodep->right, in sparsebit_validate_internal()
1788 nodep->right->parent); in sparsebit_validate_internal()
1794 if (!nodep->parent) { in sparsebit_validate_internal()
1795 if (s->root != nodep) { in sparsebit_validate_internal()
1798 s->root, nodep); 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()
1824 >= nodep->idx) { in sparsebit_validate_internal()
1833 nodep, nodep->idx, nodep->num_after, in sparsebit_validate_internal()
1844 if (nodep->mask == ~(mask_t) 0 && in sparsebit_validate_internal()
1845 prev->idx + MASK_BITS + prev->num_after == nodep->idx) { in sparsebit_validate_internal()
1855 nodep, nodep->idx, nodep->num_after, in sparsebit_validate_internal()