/* Inserts |item| into |tree| and returns a pointer to |item|'s address. If a duplicate item is found in the tree, returns a pointer to the duplicate without inserting |item|. Returns |NULL| in case of memory allocation failure. */ void ** rtavl_probe (struct rtavl_table *tree, void *item) { struct rtavl_node *y, *z; /* Top node to update balance factor, and parent. */ struct rtavl_node *p, *q; /* Iterator, and parent. */ struct rtavl_node *n; /* Newly inserted node. */ struct rtavl_node *w; /* New root of rebalanced subtree. */ int dir; /* Direction to descend. */ unsigned char da[RTAVL_MAX_HEIGHT]; /* Cached comparison results. */ int k = 0; /* Number of cached results. */ assert (tree != NULL && item != NULL); z = (struct rtavl_node *) &tree->rtavl_root; y = tree->rtavl_root; if (tree->rtavl_root != NULL) for (q = z, p = y; ; q = p, p = p->rtavl_link[dir]) { int cmp = tree->rtavl_compare (item, p->rtavl_data, tree->rtavl_param); if (cmp == 0) return &p->rtavl_data; if (p->rtavl_balance != 0) z = q, y = p, k = 0; da[k++] = dir = cmp > 0; if (dir == 0) { if (p->rtavl_link[0] == NULL) break; } else /* |dir == 1| */ { if (p->rtavl_rtag == RTAVL_THREAD) break; } } else { p = (struct rtavl_node *) &tree->rtavl_root; dir = 0; } n = tree->rtavl_alloc->libavl_malloc (tree->rtavl_alloc, sizeof *n); if (n == NULL) return NULL; tree->rtavl_count++; n->rtavl_data = item; n->rtavl_link[0] = NULL; if (dir == 0) n->rtavl_link[1] = p; else /* |dir == 1| */ { p->rtavl_rtag = RTAVL_CHILD; n->rtavl_link[1] = p->rtavl_link[1]; } n->rtavl_rtag = RTAVL_THREAD; n->rtavl_balance = 0; p->rtavl_link[dir] = n; if (y == NULL) { n->rtavl_link[1] = NULL; return &n->rtavl_data; } for (p = y, k = 0; p != n; p = p->rtavl_link[da[k]], k++) if (da[k] == 0) p->rtavl_balance--; else p->rtavl_balance++; if (y->rtavl_balance == -2) { struct rtavl_node *x = y->rtavl_link[0]; if (x->rtavl_balance == -1) { w = x; if (x->rtavl_rtag == RTAVL_THREAD) { x->rtavl_rtag = RTAVL_CHILD; y->rtavl_link[0] = NULL; } else y->rtavl_link[0] = x->rtavl_link[1]; x->rtavl_link[1] = y; x->rtavl_balance = y->rtavl_balance = 0; } else { assert (x->rtavl_balance == +1); w = x->rtavl_link[1]; x->rtavl_link[1] = w->rtavl_link[0]; w->rtavl_link[0] = x; y->rtavl_link[0] = w->rtavl_link[1]; w->rtavl_link[1] = y; if (w->rtavl_balance == -1) x->rtavl_balance = 0, y->rtavl_balance = +1; else if (w->rtavl_balance == 0) x->rtavl_balance = y->rtavl_balance = 0; else /* |w->rtavl_balance == +1| */ x->rtavl_balance = -1, y->rtavl_balance = 0; w->rtavl_balance = 0; if (x->rtavl_link[1] == NULL) { x->rtavl_rtag = RTAVL_THREAD; x->rtavl_link[1] = w; } if (w->rtavl_rtag == RTAVL_THREAD) { y->rtavl_link[0] = NULL; w->rtavl_rtag = RTAVL_CHILD; } } } else if (y->rtavl_balance == +2) { struct rtavl_node *x = y->rtavl_link[1]; if (x->rtavl_balance == +1) { w = x; if (x->rtavl_link[0] == NULL) { y->rtavl_rtag = RTAVL_THREAD; y->rtavl_link[1] = x; } else y->rtavl_link[1] = x->rtavl_link[0]; x->rtavl_link[0] = y; x->rtavl_balance = y->rtavl_balance = 0; } else { assert (x->rtavl_balance == -1); w = x->rtavl_link[0]; x->rtavl_link[0] = w->rtavl_link[1]; w->rtavl_link[1] = x; y->rtavl_link[1] = w->rtavl_link[0]; w->rtavl_link[0] = y; if (w->rtavl_balance == +1) x->rtavl_balance = 0, y->rtavl_balance = -1; else if (w->rtavl_balance == 0) x->rtavl_balance = y->rtavl_balance = 0; else /* |w->rtavl_balance == -1| */ x->rtavl_balance = +1, y->rtavl_balance = 0; w->rtavl_balance = 0; if (y->rtavl_link[1] == NULL) { y->rtavl_rtag = RTAVL_THREAD; y->rtavl_link[1] = w; } if (w->rtavl_rtag == RTAVL_THREAD) { x->rtavl_link[0] = NULL; w->rtavl_rtag = RTAVL_CHILD; } } } else return &n->rtavl_data; z->rtavl_link[y != z->rtavl_link[0]] = w; return &n->rtavl_data; }