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()
638 nodep = tmp; in node_reduce()
647 if (nodep->mask == 0) { in node_reduce()
648 assert(nodep->num_after != 0); in node_reduce()
649 assert(nodep->idx + MASK_BITS > nodep->idx); in node_reduce()
651 nodep->idx += MASK_BITS; in node_reduce()
653 if (nodep->num_after >= MASK_BITS) { in node_reduce()
654 nodep->mask = ~0; in node_reduce()
655 nodep->num_after -= MASK_BITS; in node_reduce()
657 nodep->mask = (1u << nodep->num_after) - 1; in node_reduce()
658 nodep->num_after = 0; in node_reduce()
669 prev = node_prev(s, nodep); in node_reduce()
685 if (nodep->mask + 1 == 0 && in node_reduce()
686 prev->idx + MASK_BITS == nodep->idx) { in node_reduce()
687 prev->num_after += MASK_BITS + nodep->num_after; in node_reduce()
688 nodep->mask = 0; in node_reduce()
689 nodep->num_after = 0; in node_reduce()
701 if (prev_highest_bit + 1 == nodep->idx && in node_reduce()
702 (nodep->mask | (nodep->mask >> 1)) == nodep->mask) { in node_reduce()
711 = __builtin_popcount(nodep->mask); in node_reduce()
713 ((1ULL << num_contiguous) - 1) == nodep->mask); in node_reduce()
716 nodep->mask = 0; in node_reduce()
732 prev->num_after += nodep->num_after; in node_reduce()
733 nodep->num_after = 0; in node_reduce()
745 next = node_next(s, nodep); in node_reduce()
758 if (next->idx == nodep->idx + MASK_BITS + nodep->num_after && in node_reduce()
760 nodep->num_after += MASK_BITS; in node_reduce()
762 nodep->num_after += next->num_after; in node_reduce()
772 } while (nodep && reduction_performed); in node_reduce()
780 struct node *nodep; in sparsebit_is_set() local
783 for (nodep = s->root; nodep; in sparsebit_is_set()
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()
806 struct node *nodep; in bit_set() local
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()
825 node_reduce(s, nodep); in bit_set()
833 struct node *nodep; in bit_clear() local
840 nodep = node_find(s, idx); in bit_clear()
841 if (!nodep) 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()
861 node_reduce(s, nodep); in bit_clear()
871 static void dump_nodes(FILE *stream, struct node *nodep, in dump_nodes() argument
877 if (!nodep->parent) in dump_nodes()
879 else if (nodep == nodep->parent->left) in dump_nodes()
882 assert(nodep == nodep->parent->right); in dump_nodes()
885 fprintf(stream, "%*s---- %s nodep: %p\n", indent, "", node_type, nodep); in dump_nodes()
887 nodep->parent, nodep->left, nodep->right); in dump_nodes()
889 indent, "", nodep->idx, nodep->mask, nodep->num_after); in dump_nodes()
892 if (nodep->left) in dump_nodes()
893 dump_nodes(stream, nodep->left, indent + 2); in dump_nodes()
896 if (nodep->right) in dump_nodes()
897 dump_nodes(stream, nodep->right, indent + 2); in dump_nodes()
900 static inline sparsebit_idx_t node_first_set(struct node *nodep, int start) in node_first_set() argument
903 int n1 = __builtin_ctz(nodep->mask & -leading); in node_first_set()
905 return nodep->idx + n1; in node_first_set()
908 static inline sparsebit_idx_t node_first_clear(struct node *nodep, int start) in node_first_clear() argument
911 int n1 = __builtin_ctz(~nodep->mask & -leading); in node_first_clear()
913 return nodep->idx + n1; in node_first_clear()
1088 struct node *nodep; in sparsebit_first_set() local
1093 nodep = node_first(s); in sparsebit_first_set()
1094 return node_first_set(nodep, 0); in sparsebit_first_set()
1159 struct node *nodep; in sparsebit_next_set() local
1179 for (nodep = s->root; nodep;) { in sparsebit_next_set()
1180 if ((nodep->idx + MASK_BITS + nodep->num_after - 1) in sparsebit_next_set()
1182 candidate = nodep; in sparsebit_next_set()
1187 nodep = nodep->left; in sparsebit_next_set()
1189 nodep = nodep->right; in sparsebit_next_set()
1373 struct node *nodep, *next; in sparsebit_set_num() local
1409 nodep = node_split(s, middle_start); in sparsebit_set_num()
1420 for (next = node_next(s, nodep); in sparsebit_set_num()
1422 next = node_next(s, nodep)) { in sparsebit_set_num()
1430 if (!(nodep->mask & (1 << n1))) { in sparsebit_set_num()
1431 nodep->mask |= 1 << n1; in sparsebit_set_num()
1436 s->num_set -= nodep->num_after; in sparsebit_set_num()
1437 nodep->num_after = middle_end - middle_start + 1 - MASK_BITS; in sparsebit_set_num()
1438 s->num_set += nodep->num_after; in sparsebit_set_num()
1440 node_reduce(s, nodep); in sparsebit_set_num()
1455 struct node *nodep, *next; in sparsebit_clear_num() local
1472 nodep = node_split(s, middle_start); in sparsebit_clear_num()
1483 for (next = node_next(s, nodep); in sparsebit_clear_num()
1485 next = node_next(s, nodep)) { in sparsebit_clear_num()
1493 if (nodep->mask & (1 << n1)) { in sparsebit_clear_num()
1494 nodep->mask &= ~(1 << n1); in sparsebit_clear_num()
1500 s->num_set -= nodep->num_after; in sparsebit_clear_num()
1501 nodep->num_after = 0; in sparsebit_clear_num()
1508 node_reduce(s, nodep); in sparsebit_clear_num()
1509 nodep = NULL; in sparsebit_clear_num()
1591 struct node *nodep; in sparsebit_dump() local
1600 for (nodep = node_first(s); nodep; nodep = node_next(s, nodep)) { in sparsebit_dump()
1606 if (nodep->mask & (1 << n1)) { in sparsebit_dump()
1607 low = high = nodep->idx + n1; in sparsebit_dump()
1610 if (nodep->mask & (1 << n1)) in sparsebit_dump()
1611 high = nodep->idx + n1; in sparsebit_dump()
1616 if ((n1 == MASK_BITS) && nodep->num_after) in sparsebit_dump()
1617 high += nodep->num_after; in sparsebit_dump()
1649 if (!(nodep->mask & (1 << (MASK_BITS - 1))) && nodep->num_after) { 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()
1687 struct node *nodep, *prev = NULL; in sparsebit_validate_internal() local
1692 for (nodep = node_first(s); nodep; in sparsebit_validate_internal()
1693 prev = nodep, nodep = node_next(s, nodep)) { in sparsebit_validate_internal()
1700 if (nodep->mask & (1 << n1)) in sparsebit_validate_internal()
1703 total_bits_set += nodep->num_after; in sparsebit_validate_internal()
1712 if (nodep->mask == 0) { in sparsebit_validate_internal()
1715 nodep, nodep->mask); in sparsebit_validate_internal()
1731 if (nodep->num_after in sparsebit_validate_internal()
1735 nodep, nodep->num_after); in sparsebit_validate_internal()
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()
1766 if (nodep->left) { in sparsebit_validate_internal()
1767 if (nodep->left->parent != nodep) { in sparsebit_validate_internal()
1772 nodep, nodep->left, in sparsebit_validate_internal()
1773 nodep->left->parent); in sparsebit_validate_internal()
1779 if (nodep->right) { in sparsebit_validate_internal()
1780 if (nodep->right->parent != nodep) { in sparsebit_validate_internal()
1785 nodep, nodep->right, in sparsebit_validate_internal()
1786 nodep->right->parent); in sparsebit_validate_internal()
1792 if (!nodep->parent) { in sparsebit_validate_internal()
1793 if (s->root != nodep) { in sparsebit_validate_internal()
1796 s->root, nodep); 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()
1822 >= nodep->idx) { in sparsebit_validate_internal()
1831 nodep, nodep->idx, nodep->num_after, in sparsebit_validate_internal()
1842 if (nodep->mask == ~(mask_t) 0 && in sparsebit_validate_internal()
1843 prev->idx + MASK_BITS + prev->num_after == nodep->idx) { in sparsebit_validate_internal()
1853 nodep, nodep->idx, nodep->num_after, in sparsebit_validate_internal()