Lines Matching refs:nodep
195 * of the node pointed to by nodep.
197 static sparsebit_num_t node_num_set(struct node *nodep)
199 return nodep->num_after + __builtin_popcount(nodep->mask);
207 struct node *nodep;
209 for (nodep = s->root; nodep && nodep->left; nodep = nodep->left)
212 return nodep;
221 struct node *nodep = np;
227 if (nodep->right) {
228 for (nodep = nodep->right; nodep->left; nodep = nodep->left)
230 return nodep;
237 while (nodep->parent && nodep == nodep->parent->right)
238 nodep = nodep->parent;
240 return nodep->parent;
249 struct node *nodep = np;
255 if (nodep->left) {
256 for (nodep = nodep->left; nodep->right; nodep = nodep->right)
258 return (struct node *) nodep;
265 while (nodep->parent && nodep == nodep->parent->left)
266 nodep = nodep->parent;
268 return (struct node *) nodep->parent;
312 struct node *nodep;
315 for (nodep = s->root; nodep;
316 nodep = nodep->idx > idx ? nodep->left : nodep->right) {
317 if (idx >= nodep->idx &&
318 idx <= nodep->idx + MASK_BITS + nodep->num_after - 1)
322 return nodep;
335 struct node *nodep, *parentp, *prev;
338 nodep = calloc(1, sizeof(*nodep));
339 if (!nodep) {
344 nodep->idx = idx & -MASK_BITS;
348 s->root = nodep;
349 return nodep;
360 parentp->left = nodep;
361 nodep->parent = parentp;
368 parentp->right = nodep;
369 nodep->parent = parentp;
381 prev = node_prev(s, nodep);
382 while (prev && prev->idx + MASK_BITS + prev->num_after - 1 >= nodep->idx) {
384 - nodep->idx;
387 assert(!(nodep->mask & (1 << n1)));
388 nodep->mask |= (1 << n1);
392 return nodep;
406 /* Clears all bits described by the node pointed to by nodep, then
409 static void node_rm(struct sparsebit *s, struct node *nodep)
414 num_set = node_num_set(nodep);
416 s->num_set -= node_num_set(nodep);
419 if (nodep->left && nodep->right) {
424 for (tmp = nodep->right; tmp->left; tmp = tmp->left)
426 tmp->left = nodep->left;
427 nodep->left = NULL;
432 if (nodep->left) {
433 if (!nodep->parent) {
434 s->root = nodep->left;
435 nodep->left->parent = NULL;
437 nodep->left->parent = nodep->parent;
438 if (nodep == nodep->parent->left)
439 nodep->parent->left = nodep->left;
441 assert(nodep == nodep->parent->right);
442 nodep->parent->right = nodep->left;
446 nodep->parent = nodep->left = nodep->right = NULL;
447 free(nodep);
454 if (nodep->right) {
455 if (!nodep->parent) {
456 s->root = nodep->right;
457 nodep->right->parent = NULL;
459 nodep->right->parent = nodep->parent;
460 if (nodep == nodep->parent->left)
461 nodep->parent->left = nodep->right;
463 assert(nodep == nodep->parent->right);
464 nodep->parent->right = nodep->right;
468 nodep->parent = nodep->left = nodep->right = NULL;
469 free(nodep);
475 if (!nodep->parent) {
478 if (nodep->parent->left == nodep)
479 nodep->parent->left = NULL;
481 assert(nodep == nodep->parent->right);
482 nodep->parent->right = NULL;
486 nodep->parent = nodep->left = nodep->right = NULL;
487 free(nodep);
553 /* Iteratively reduces the node pointed to by nodep and its adjacent
560 * a search for a reduction is only done across the nodes nearest nodep
561 * and those that became part of a reduction. Reductions beyond nodep
563 * responsibility of the caller to pass a nodep that is within one node
579 * Instead, the function can call node_reduce(), with nodep equal to the
599 static void node_reduce(struct sparsebit *s, struct node *nodep)
610 if (nodep->mask == 0 && nodep->num_after == 0) {
613 * nodep, which normally would cause a problem
619 * once the node at nodep is removed, there will be
622 * Note, the checks performed on nodep against both
625 * such, after removing the node at nodep, doesn't
626 * matter whether the nodep for the next pass
632 tmp = node_next(s, nodep);
634 tmp = node_prev(s, nodep);
636 node_rm(s, nodep);
638 nodep = tmp;
647 if (nodep->mask == 0) {
648 assert(nodep->num_after != 0);
649 assert(nodep->idx + MASK_BITS > nodep->idx);
651 nodep->idx += MASK_BITS;
653 if (nodep->num_after >= MASK_BITS) {
654 nodep->mask = ~0;
655 nodep->num_after -= MASK_BITS;
657 nodep->mask = (1u << nodep->num_after) - 1;
658 nodep->num_after = 0;
669 prev = node_prev(s, nodep);
685 if (nodep->mask + 1 == 0 &&
686 prev->idx + MASK_BITS == nodep->idx) {
687 prev->num_after += MASK_BITS + nodep->num_after;
688 nodep->mask = 0;
689 nodep->num_after = 0;
701 if (prev_highest_bit + 1 == nodep->idx &&
702 (nodep->mask | (nodep->mask >> 1)) == nodep->mask) {
711 = __builtin_popcount(nodep->mask);
713 ((1ULL << num_contiguous) - 1) == nodep->mask);
716 nodep->mask = 0;
732 prev->num_after += nodep->num_after;
733 nodep->num_after = 0;
745 next = node_next(s, nodep);
758 if (next->idx == nodep->idx + MASK_BITS + nodep->num_after &&
760 nodep->num_after += MASK_BITS;
762 nodep->num_after += next->num_after;
772 } while (nodep && reduction_performed);
780 struct node *nodep;
783 for (nodep = s->root; nodep;
784 nodep = nodep->idx > idx ? nodep->left : nodep->right)
785 if (idx >= nodep->idx &&
786 idx <= nodep->idx + MASK_BITS + nodep->num_after - 1)
793 if (nodep->num_after && idx >= nodep->idx + MASK_BITS)
797 assert(idx >= nodep->idx && idx - nodep->idx < MASK_BITS);
798 return !!(nodep->mask & (1 << (idx - nodep->idx)));
806 struct node *nodep;
817 nodep = node_split(s, idx & -MASK_BITS);
820 assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1);
821 assert(!(nodep->mask & (1 << (idx - nodep->idx))));
822 nodep->mask |= 1 << (idx - nodep->idx);
825 node_reduce(s, nodep);
833 struct node *nodep;
840 nodep = node_find(s, idx);
841 if (!nodep)
848 if (idx >= nodep->idx + MASK_BITS)
849 nodep = node_split(s, idx & -MASK_BITS);
855 assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1);
856 assert(nodep->mask & (1 << (idx - nodep->idx)));
857 nodep->mask &= ~(1 << (idx - nodep->idx));
861 node_reduce(s, nodep);
865 * of the sub-tree of nodes pointed to by nodep. Each line of output
871 static void dump_nodes(FILE *stream, struct node *nodep,
877 if (!nodep->parent)
879 else if (nodep == nodep->parent->left)
882 assert(nodep == nodep->parent->right);
885 fprintf(stream, "%*s---- %s nodep: %p\n", indent, "", node_type, nodep);
887 nodep->parent, nodep->left, nodep->right);
889 indent, "", nodep->idx, nodep->mask, nodep->num_after);
892 if (nodep->left)
893 dump_nodes(stream, nodep->left, indent + 2);
896 if (nodep->right)
897 dump_nodes(stream, nodep->right, indent + 2);
900 static inline sparsebit_idx_t node_first_set(struct node *nodep, int start)
903 int n1 = __builtin_ctz(nodep->mask & -leading);
905 return nodep->idx + n1;
908 static inline sparsebit_idx_t node_first_clear(struct node *nodep, int start)
911 int n1 = __builtin_ctz(~nodep->mask & -leading);
913 return nodep->idx + n1;
1088 struct node *nodep;
1093 nodep = node_first(s);
1094 return node_first_set(nodep, 0);
1159 struct node *nodep;
1179 for (nodep = s->root; nodep;) {
1180 if ((nodep->idx + MASK_BITS + nodep->num_after - 1)
1182 candidate = nodep;
1187 nodep = nodep->left;
1189 nodep = nodep->right;
1373 struct node *nodep, *next;
1409 nodep = node_split(s, middle_start);
1420 for (next = node_next(s, nodep);
1422 next = node_next(s, nodep)) {
1430 if (!(nodep->mask & (1 << n1))) {
1431 nodep->mask |= 1 << n1;
1436 s->num_set -= nodep->num_after;
1437 nodep->num_after = middle_end - middle_start + 1 - MASK_BITS;
1438 s->num_set += nodep->num_after;
1440 node_reduce(s, nodep);
1455 struct node *nodep, *next;
1472 nodep = node_split(s, middle_start);
1483 for (next = node_next(s, nodep);
1485 next = node_next(s, nodep)) {
1493 if (nodep->mask & (1 << n1)) {
1494 nodep->mask &= ~(1 << n1);
1500 s->num_set -= nodep->num_after;
1501 nodep->num_after = 0;
1506 * with the nodes prev or next of nodep.
1508 node_reduce(s, nodep);
1509 nodep = NULL;
1591 struct node *nodep;
1600 for (nodep = node_first(s); nodep; nodep = node_next(s, nodep)) {
1606 if (nodep->mask & (1 << n1)) {
1607 low = high = nodep->idx + n1;
1610 if (nodep->mask & (1 << n1))
1611 high = nodep->idx + n1;
1616 if ((n1 == MASK_BITS) && nodep->num_after)
1617 high += nodep->num_after;
1649 if (!(nodep->mask & (1 << (MASK_BITS - 1))) && nodep->num_after) {
1650 low = nodep->idx + MASK_BITS;
1651 high = nodep->idx + MASK_BITS + nodep->num_after - 1;
1687 struct node *nodep, *prev = NULL;
1692 for (nodep = node_first(s); nodep;
1693 prev = nodep, nodep = node_next(s, nodep)) {
1700 if (nodep->mask & (1 << n1))
1703 total_bits_set += nodep->num_after;
1712 if (nodep->mask == 0) {
1714 "nodep: %p nodep->mask: 0x%x",
1715 nodep, nodep->mask);
1731 if (nodep->num_after
1734 "nodep: %p nodep->num_after: 0x%lx",
1735 nodep, nodep->num_after);
1741 if (nodep->idx % MASK_BITS) {
1744 " nodep: %p nodep->idx: 0x%lx "
1746 nodep, nodep->idx, MASK_BITS);
1755 if ((nodep->idx + MASK_BITS + nodep->num_after - 1) < nodep->idx) {
1758 " nodep: %p nodep->idx: 0x%lx\n"
1759 " MASK_BITS: %lu nodep->num_after: 0x%lx",
1760 nodep, nodep->idx, MASK_BITS, nodep->num_after);
1766 if (nodep->left) {
1767 if (nodep->left->parent != nodep) {
1770 " nodep: %p nodep->left: %p "
1771 "nodep->left->parent: %p",
1772 nodep, nodep->left,
1773 nodep->left->parent);
1779 if (nodep->right) {
1780 if (nodep->right->parent != nodep) {
1783 " nodep: %p nodep->right: %p "
1784 "nodep->right->parent: %p",
1785 nodep, nodep->right,
1786 nodep->right->parent);
1792 if (!nodep->parent) {
1793 if (s->root != nodep) {
1795 "s->root: %p nodep: %p",
1796 s->root, nodep);
1807 if (prev->idx >= nodep->idx) {
1811 " nodep: %p nodep->idx: 0x%lx",
1812 prev, prev->idx, nodep, nodep->idx);
1822 >= nodep->idx) {
1827 " nodep: %p nodep->idx: 0x%lx "
1828 "nodep->num_after: 0x%lx\n"
1831 nodep, nodep->idx, nodep->num_after,
1842 if (nodep->mask == ~(mask_t) 0 &&
1843 prev->idx + MASK_BITS + prev->num_after == nodep->idx) {
1849 " nodep: %p nodep->idx: 0x%lx "
1850 "nodep->num_after: 0x%lx\n"
1853 nodep, nodep->idx, nodep->num_after,