141 rpst_update_parents(struct rpst_node *n)  in rpst_update_parents()  argument
146                     if (n->n_children[i] != NULL) {  in rpst_update_parents()
147                               n->n_children[i]->n_parent = n;  in rpst_update_parents()
161                     struct rpst_node *n = t->t_root;  in rpst_enlarge_tree()  local
163                     if (n != NULL) {  in rpst_enlarge_tree()
164                               rpst_remove_node(t, n);  in rpst_enlarge_tree()
165                               memset(&n->n_children, 0, sizeof(n->n_children));  in rpst_enlarge_tree()
166                               n->n_children[0] = t->t_root;  in rpst_enlarge_tree()
167                               t->t_root->n_parent = n;  in rpst_enlarge_tree()
168                               t->t_root = n;  in rpst_enlarge_tree()
169                               n->n_parent = NULL;  in rpst_enlarge_tree()
180 rpst_insert_node1(struct rpst_node **where, struct rpst_node *n, uint64_t mask)  in rpst_insert_node1()  argument
186           KASSERT((n->n_x & ((-mask) << 1)) == 0);  in rpst_insert_node1()
191                     n->n_parent = parent;  in rpst_insert_node1()
192                     memset(&n->n_children, 0, sizeof(n->n_children));  in rpst_insert_node1()
193                     *where = n;  in rpst_insert_node1()
197           if (n->n_y == cur->n_y && n->n_x == cur->n_x) {  in rpst_insert_node1()
200           if (n->n_y < cur->n_y) {  in rpst_insert_node1()
205                     memcpy(n->n_children, cur->n_children, sizeof(n->n_children));  in rpst_insert_node1()
206                     n->n_parent = cur->n_parent;  in rpst_insert_node1()
207                     rpst_update_parents(n);  in rpst_insert_node1()
208                     *where = n;  in rpst_insert_node1()
209                     n = cur;  in rpst_insert_node1()
213           idx = (n->n_x & mask) != 0;  in rpst_insert_node1()
231 rpst_insert_node(struct rpst_tree *t, struct rpst_node *n)  in rpst_insert_node()  argument
234           rpst_enlarge_tree(t, n->n_x);  in rpst_insert_node()
235           return rpst_insert_node1(&t->t_root, n, rpst_startmask(t));  in rpst_insert_node()
245 rpst_find_pptr(struct rpst_tree *t, struct rpst_node *n,  in rpst_find_pptr()  argument
248           struct rpst_node * const parent = n->n_parent;  in rpst_find_pptr()
256                     if (parent->n_children[i] == n) {  in rpst_find_pptr()
260           KASSERT(parent->n_children[i] == n);  in rpst_find_pptr()
350 rpst_remove_node(struct rpst_tree *t, struct rpst_node *n)  in rpst_remove_node()  argument
355           where = rpst_find_pptr(t, n, &parent);  in rpst_remove_node()
356           rpst_remove_node_at(parent, where, n);  in rpst_remove_node()
360 rpst_iterator_match_p(const struct rpst_node *n, const struct rpst_iterator *it)  in rpst_iterator_match_p()  argument
363           if (n->n_y > it->it_max_y) {  in rpst_iterator_match_p()
366           if (n->n_x < it->it_min_x) {  in rpst_iterator_match_p()
369           if (n->n_x > it->it_max_x) {  in rpst_iterator_match_p()
379           struct rpst_node *n;  in rpst_iterate_first()  local
382           n = t->t_root;  in rpst_iterate_first()
383           if (n == NULL || n->n_y > max_y) {  in rpst_iterate_first()
390           it->it_cur = n;  in rpst_iterate_first()
400 rpst_node_on_edge_p(const struct rpst_node *n, uint64_t val, uint64_t mask)  in rpst_node_on_edge_p()  argument
403           return ((n->n_x ^ val) & ((-mask) << 1)) == 0;  in rpst_node_on_edge_p()
407 rpst_maxidx(const struct rpst_node *n, uint64_t max_x, uint64_t mask)  in rpst_maxidx()  argument
410           if (rpst_node_on_edge_p(n, max_x, mask)) {  in rpst_maxidx()
418 rpst_minidx(const struct rpst_node *n, uint64_t min_x, uint64_t mask)  in rpst_minidx()  argument
421           if (rpst_node_on_edge_p(n, min_x, mask)) {  in rpst_minidx()
432           struct rpst_node *n;  in rpst_iterate_next()  local
443           n = it->it_cur;  in rpst_iterate_next()
447           maxidx = rpst_maxidx(n, max_x, mask);  in rpst_iterate_next()
448           KASSERT(n == t->t_root || rpst_iterator_match_p(n, it));  in rpst_iterate_next()
451           KASSERT(idx >= rpst_minidx(n, min_x, mask));  in rpst_iterate_next()
452           KASSERT(maxidx == rpst_maxidx(n, max_x, mask));  in rpst_iterate_next()
454           KASSERT(n != NULL);  in rpst_iterate_next()
457               __func__, (void *)n, idx, maxidx, level, mask);  in rpst_iterate_next()
461                     if (min_x <= n->n_x && n->n_x <= max_x) {  in rpst_iterate_next()
462                               it->it_cur = n;  in rpst_iterate_next()
465                               KASSERT(rpst_iterator_match_p(n, it));  in rpst_iterate_next()
466                               return n; /* report */  in rpst_iterate_next()
472                     where = rpst_find_pptr(t, n, &next);  in rpst_iterate_next()
475                               KASSERT(t->t_root == n);  in rpst_iterate_next()
481                     n = next;  in rpst_iterate_next()
483                     maxidx = rpst_maxidx(n, max_x, mask);  in rpst_iterate_next()
484                     idx = where - n->n_children + 1;  in rpst_iterate_next()
490           next = n->n_children[idx];  in rpst_iterate_next()
495           KASSERT(next->n_parent == n);  in rpst_iterate_next()
496           KASSERT(next->n_y >= n->n_y);  in rpst_iterate_next()
499           n = next;  in rpst_iterate_next()
500           idx = rpst_minidx(n, min_x, mask);  in rpst_iterate_next()
501           maxidx = rpst_maxidx(n, max_x, mask);  in rpst_iterate_next()
504               __func__, n, idx, level, mask);  in rpst_iterate_next()
517 rpst_dump_node(const struct rpst_node *n, unsigned int depth)  in rpst_dump_node()  argument
525           if (n == NULL) {  in rpst_dump_node()
530               (const void *)n, n->n_x, n->n_x, n->n_y, n->n_y);  in rpst_dump_node()
532                     rpst_dump_node(n->n_children[i], depth + 1);  in rpst_dump_node()
545           struct rpst_node n;  member
565           struct testnode *n;  in query()  local
585                     n = (void *)rn;  in query()
586                     assert(!n->found);  in query()
587                     n->found = true;  in query()
594           for (n = h; n != NULL; n = n->next) {  in query()
595                     assert(n->failed ||  in query()
596                         n->found == rpst_iterator_match_p(&n->n, &it));  in query()
597                     n->found = false;  in query()
607           struct testnode *n;  in main()  local
626                     n = malloc(sizeof(*n));  in main()
628                               n->n.n_x = 10;  in main()
629                               n->n.n_y = random();  in main()
631                               n->n.n_x = i;  in main()
632                               n->n.n_y = random();  in main()
634                               n->n.n_x = random();  in main()
635                               n->n.n_y = random();  in main()
637                     if (n->n.n_y < min_y) {  in main()
638                               min_y = n->n.n_y;  in main()
640                     if (n->n.n_y > max_y) {  in main()
641                               max_y = n->n.n_y;  in main()
643                     if (n->n.n_x < min_x) {  in main()
644                               min_x = n->n.n_x;  in main()
646                     if (n->n.n_x > max_x) {  in main()
647                               max_x = n->n.n_x;  in main()
649                     n->found = false;  in main()
650                     n->failed = false;  in main()
651                     n->next = h;  in main()
652                     h = n;  in main()
658           for (n = h; n != NULL; n = n->next) {  in main()
662                         n, n->n.n_x, n->n.n_y);  in main()
664                     o = rpst_insert_node(&t, &n->n);  in main()
668                               n->failed = true;  in main()
699           for (n = h; n != NULL; n = n->next) {  in main()
700                     if (n->failed) {  in main()
705                         n, n->n.n_x, n->n.n_y);  in main()
707                     rpst_remove_node(&t, &n->n);  in main()