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);
637 nodep = NULL;
639 nodep = tmp;
648 if (nodep->mask == 0) {
649 assert(nodep->num_after != 0);
650 assert(nodep->idx + MASK_BITS > nodep->idx);
652 nodep->idx += MASK_BITS;
654 if (nodep->num_after >= MASK_BITS) {
655 nodep->mask = ~0;
656 nodep->num_after -= MASK_BITS;
658 nodep->mask = (1u << nodep->num_after) - 1;
659 nodep->num_after = 0;
670 prev = node_prev(s, nodep);
686 if (nodep->mask + 1 == 0 &&
687 prev->idx + MASK_BITS == nodep->idx) {
688 prev->num_after += MASK_BITS + nodep->num_after;
689 nodep->mask = 0;
690 nodep->num_after = 0;
702 if (prev_highest_bit + 1 == nodep->idx &&
703 (nodep->mask | (nodep->mask >> 1)) == nodep->mask) {
712 = __builtin_popcount(nodep->mask);
714 ((1ULL << num_contiguous) - 1) == nodep->mask);
717 nodep->mask = 0;
733 prev->num_after += nodep->num_after;
734 nodep->num_after = 0;
746 next = node_next(s, nodep);
759 if (next->idx == nodep->idx + MASK_BITS + nodep->num_after &&
761 nodep->num_after += MASK_BITS;
763 nodep->num_after += next->num_after;
773 } while (nodep && reduction_performed);
781 struct node *nodep;
784 for (nodep = s->root; nodep;
785 nodep = nodep->idx > idx ? nodep->left : nodep->right)
786 if (idx >= nodep->idx &&
787 idx <= nodep->idx + MASK_BITS + nodep->num_after - 1)
794 if (nodep->num_after && idx >= nodep->idx + MASK_BITS)
798 assert(idx >= nodep->idx && idx - nodep->idx < MASK_BITS);
799 return !!(nodep->mask & (1 << (idx - nodep->idx)));
807 struct node *nodep;
818 nodep = node_split(s, idx & -MASK_BITS);
821 assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1);
822 assert(!(nodep->mask & (1 << (idx - nodep->idx))));
823 nodep->mask |= 1 << (idx - nodep->idx);
826 node_reduce(s, nodep);
834 struct node *nodep;
841 nodep = node_find(s, idx);
842 if (!nodep)
849 if (idx >= nodep->idx + MASK_BITS)
850 nodep = node_split(s, idx & -MASK_BITS);
856 assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1);
857 assert(nodep->mask & (1 << (idx - nodep->idx)));
858 nodep->mask &= ~(1 << (idx - nodep->idx));
862 node_reduce(s, nodep);
866 * of the sub-tree of nodes pointed to by nodep. Each line of output
872 static void dump_nodes(FILE *stream, struct node *nodep,
878 if (!nodep->parent)
880 else if (nodep == nodep->parent->left)
883 assert(nodep == nodep->parent->right);
886 fprintf(stream, "%*s---- %s nodep: %p\n", indent, "", node_type, nodep);
888 nodep->parent, nodep->left, nodep->right);
890 indent, "", nodep->idx, nodep->mask, nodep->num_after);
893 if (nodep->left)
894 dump_nodes(stream, nodep->left, indent + 2);
897 if (nodep->right)
898 dump_nodes(stream, nodep->right, indent + 2);
901 static inline sparsebit_idx_t node_first_set(struct node *nodep, int start)
904 int n1 = __builtin_ctz(nodep->mask & -leading);
906 return nodep->idx + n1;
909 static inline sparsebit_idx_t node_first_clear(struct node *nodep, int start)
912 int n1 = __builtin_ctz(~nodep->mask & -leading);
914 return nodep->idx + n1;
1089 struct node *nodep;
1094 nodep = node_first(s);
1095 return node_first_set(nodep, 0);
1160 struct node *nodep;
1180 for (nodep = s->root; nodep;) {
1181 if ((nodep->idx + MASK_BITS + nodep->num_after - 1)
1183 candidate = nodep;
1188 nodep = nodep->left;
1190 nodep = nodep->right;
1374 struct node *nodep, *next;
1410 nodep = node_split(s, middle_start);
1421 for (next = node_next(s, nodep);
1423 next = node_next(s, nodep)) {
1431 if (!(nodep->mask & (1 << n1))) {
1432 nodep->mask |= 1 << n1;
1437 s->num_set -= nodep->num_after;
1438 nodep->num_after = middle_end - middle_start + 1 - MASK_BITS;
1439 s->num_set += nodep->num_after;
1441 node_reduce(s, nodep);
1456 struct node *nodep, *next;
1473 nodep = node_split(s, middle_start);
1484 for (next = node_next(s, nodep);
1486 next = node_next(s, nodep)) {
1494 if (nodep->mask & (1 << n1)) {
1495 nodep->mask &= ~(1 << n1);
1501 s->num_set -= nodep->num_after;
1502 nodep->num_after = 0;
1507 * with the nodes prev or next of nodep.
1509 node_reduce(s, nodep);
1510 nodep = NULL;
1592 struct node *nodep;
1601 for (nodep = node_first(s); nodep; nodep = node_next(s, nodep)) {
1607 if (nodep->mask & (1 << n1)) {
1608 low = high = nodep->idx + n1;
1611 if (nodep->mask & (1 << n1))
1612 high = nodep->idx + n1;
1617 if ((n1 == MASK_BITS) && nodep->num_after)
1618 high += nodep->num_after;
1650 if (!(nodep->mask & (1 << (MASK_BITS - 1))) && nodep->num_after) {
1651 low = nodep->idx + MASK_BITS;
1652 high = nodep->idx + MASK_BITS + nodep->num_after - 1;
1688 struct node *nodep, *prev = NULL;
1693 for (nodep = node_first(s); nodep;
1694 prev = nodep, nodep = node_next(s, nodep)) {
1701 if (nodep->mask & (1 << n1))
1704 total_bits_set += nodep->num_after;
1713 if (nodep->mask == 0) {
1715 "nodep: %p nodep->mask: 0x%x",
1716 nodep, nodep->mask);
1732 if (nodep->num_after
1735 "nodep: %p nodep->num_after: 0x%lx",
1736 nodep, nodep->num_after);
1742 if (nodep->idx % MASK_BITS) {
1745 " nodep: %p nodep->idx: 0x%lx "
1747 nodep, nodep->idx, MASK_BITS);
1756 if ((nodep->idx + MASK_BITS + nodep->num_after - 1) < nodep->idx) {
1759 " nodep: %p nodep->idx: 0x%lx\n"
1760 " MASK_BITS: %lu nodep->num_after: 0x%lx",
1761 nodep, nodep->idx, MASK_BITS, nodep->num_after);
1767 if (nodep->left) {
1768 if (nodep->left->parent != nodep) {
1771 " nodep: %p nodep->left: %p "
1772 "nodep->left->parent: %p",
1773 nodep, nodep->left,
1774 nodep->left->parent);
1780 if (nodep->right) {
1781 if (nodep->right->parent != nodep) {
1784 " nodep: %p nodep->right: %p "
1785 "nodep->right->parent: %p",
1786 nodep, nodep->right,
1787 nodep->right->parent);
1793 if (!nodep->parent) {
1794 if (s->root != nodep) {
1796 "s->root: %p nodep: %p",
1797 s->root, nodep);
1808 if (prev->idx >= nodep->idx) {
1812 " nodep: %p nodep->idx: 0x%lx",
1813 prev, prev->idx, nodep, nodep->idx);
1823 >= nodep->idx) {
1828 " nodep: %p nodep->idx: 0x%lx "
1829 "nodep->num_after: 0x%lx\n"
1832 nodep, nodep->idx, nodep->num_after,
1843 if (nodep->mask == ~(mask_t) 0 &&
1844 prev->idx + MASK_BITS + prev->num_after == nodep->idx) {
1850 " nodep: %p nodep->idx: 0x%lx "
1851 "nodep->num_after: 0x%lx\n"
1854 nodep, nodep->idx, nodep->num_after,