/* Deletes from |tree| and returns an item matching |item|. Returns a null pointer if no matching item found. */ void * trb_delete (struct trb_table *tree, const void *item) { struct trb_node *pa[TRB_MAX_HEIGHT]; /* Nodes on stack. */ unsigned char da[TRB_MAX_HEIGHT]; /* Directions moved from stack nodes. */ int k = 0; /* Stack height. */ struct trb_node *p; int cmp, dir; assert (tree != NULL && item != NULL); if (tree->trb_root == NULL) return NULL; p = (struct trb_node *) &tree->trb_root; for (cmp = -1; cmp != 0; cmp = tree->trb_compare (item, p->trb_data, tree->trb_param)) { dir = cmp > 0; pa[k] = p; da[k++] = dir; if (p->trb_tag[dir] == TRB_THREAD) return NULL; p = p->trb_link[dir]; } item = p->trb_data; if (p->trb_tag[1] == TRB_THREAD) { if (p->trb_tag[0] == TRB_CHILD) { struct trb_node *t = p->trb_link[0]; while (t->trb_tag[1] == TRB_CHILD) t = t->trb_link[1]; t->trb_link[1] = p->trb_link[1]; pa[k - 1]->trb_link[da[k - 1]] = p->trb_link[0]; } else { pa[k - 1]->trb_link[da[k - 1]] = p->trb_link[da[k - 1]]; if (pa[k - 1] != (struct trb_node *) &tree->trb_root) pa[k - 1]->trb_tag[da[k - 1]] = TRB_THREAD; } } else { enum trb_color t; struct trb_node *r = p->trb_link[1]; if (r->trb_tag[0] == TRB_THREAD) { r->trb_link[0] = p->trb_link[0]; r->trb_tag[0] = p->trb_tag[0]; if (r->trb_tag[0] == TRB_CHILD) { struct trb_node *t = r->trb_link[0]; while (t->trb_tag[1] == TRB_CHILD) t = t->trb_link[1]; t->trb_link[1] = r; } pa[k - 1]->trb_link[da[k - 1]] = r; t = r->trb_color; r->trb_color = p->trb_color; p->trb_color = t; da[k] = 1; pa[k++] = r; } else { struct trb_node *s; int j = k++; for (;;) { da[k] = 0; pa[k++] = r; s = r->trb_link[0]; if (s->trb_tag[0] == TRB_THREAD) break; r = s; } da[j] = 1; pa[j] = s; if (s->trb_tag[1] == TRB_CHILD) r->trb_link[0] = s->trb_link[1]; else { r->trb_link[0] = s; r->trb_tag[0] = TRB_THREAD; } s->trb_link[0] = p->trb_link[0]; if (p->trb_tag[0] == TRB_CHILD) { struct trb_node *t = p->trb_link[0]; while (t->trb_tag[1] == TRB_CHILD) t = t->trb_link[1]; t->trb_link[1] = s; s->trb_tag[0] = TRB_CHILD; } s->trb_link[1] = p->trb_link[1]; s->trb_tag[1] = TRB_CHILD; t = s->trb_color; s->trb_color = p->trb_color; p->trb_color = t; pa[j - 1]->trb_link[da[j - 1]] = s; } } if (p->trb_color == TRB_BLACK) { for (; k > 1; k--) { if (pa[k - 1]->trb_tag[da[k - 1]] == TRB_CHILD) { struct trb_node *x = pa[k - 1]->trb_link[da[k - 1]]; if (x->trb_color == TRB_RED) { x->trb_color = TRB_BLACK; break; } } if (da[k - 1] == 0) { struct trb_node *w = pa[k - 1]->trb_link[1]; if (w->trb_color == TRB_RED) { w->trb_color = TRB_BLACK; pa[k - 1]->trb_color = TRB_RED; pa[k - 1]->trb_link[1] = w->trb_link[0]; w->trb_link[0] = pa[k - 1]; pa[k - 2]->trb_link[da[k - 2]] = w; pa[k] = pa[k - 1]; da[k] = 0; pa[k - 1] = w; k++; w = pa[k - 1]->trb_link[1]; } if ((w->trb_tag[0] == TRB_THREAD || w->trb_link[0]->trb_color == TRB_BLACK) && (w->trb_tag[1] == TRB_THREAD || w->trb_link[1]->trb_color == TRB_BLACK)) { w->trb_color = TRB_RED; } else { if (w->trb_tag[1] == TRB_THREAD || w->trb_link[1]->trb_color == TRB_BLACK) { struct trb_node *y = w->trb_link[0]; y->trb_color = TRB_BLACK; w->trb_color = TRB_RED; w->trb_link[0] = y->trb_link[1]; y->trb_link[1] = w; w = pa[k - 1]->trb_link[1] = y; if (w->trb_tag[1] == TRB_THREAD) { w->trb_tag[1] = TRB_CHILD; w->trb_link[1]->trb_tag[0] = TRB_THREAD; w->trb_link[1]->trb_link[0] = w; } } w->trb_color = pa[k - 1]->trb_color; pa[k - 1]->trb_color = TRB_BLACK; w->trb_link[1]->trb_color = TRB_BLACK; pa[k - 1]->trb_link[1] = w->trb_link[0]; w->trb_link[0] = pa[k - 1]; pa[k - 2]->trb_link[da[k - 2]] = w; if (w->trb_tag[0] == TRB_THREAD) { w->trb_tag[0] = TRB_CHILD; pa[k - 1]->trb_tag[1] = TRB_THREAD; pa[k - 1]->trb_link[1] = w; } break; } } else { struct trb_node *w = pa[k - 1]->trb_link[0]; if (w->trb_color == TRB_RED) { w->trb_color = TRB_BLACK; pa[k - 1]->trb_color = TRB_RED; pa[k - 1]->trb_link[0] = w->trb_link[1]; w->trb_link[1] = pa[k - 1]; pa[k - 2]->trb_link[da[k - 2]] = w; pa[k] = pa[k - 1]; da[k] = 1; pa[k - 1] = w; k++; w = pa[k - 1]->trb_link[0]; } if ((w->trb_tag[0] == TRB_THREAD || w->trb_link[0]->trb_color == TRB_BLACK) && (w->trb_tag[1] == TRB_THREAD || w->trb_link[1]->trb_color == TRB_BLACK)) { w->trb_color = TRB_RED; } else { if (w->trb_tag[0] == TRB_THREAD || w->trb_link[0]->trb_color == TRB_BLACK) { struct trb_node *y = w->trb_link[1]; y->trb_color = TRB_BLACK; w->trb_color = TRB_RED; w->trb_link[1] = y->trb_link[0]; y->trb_link[0] = w; w = pa[k - 1]->trb_link[0] = y; if (w->trb_tag[0] == TRB_THREAD) { w->trb_tag[0] = TRB_CHILD; w->trb_link[0]->trb_tag[1] = TRB_THREAD; w->trb_link[0]->trb_link[1] = w; } } w->trb_color = pa[k - 1]->trb_color; pa[k - 1]->trb_color = TRB_BLACK; w->trb_link[0]->trb_color = TRB_BLACK; pa[k - 1]->trb_link[0] = w->trb_link[1]; w->trb_link[1] = pa[k - 1]; pa[k - 2]->trb_link[da[k - 2]] = w; if (w->trb_tag[1] == TRB_THREAD) { w->trb_tag[1] = TRB_CHILD; pa[k - 1]->trb_tag[0] = TRB_THREAD; pa[k - 1]->trb_link[0] = w; } break; } } } if (tree->trb_root != NULL) tree->trb_root->trb_color = TRB_BLACK; } tree->trb_alloc->libavl_free (tree->trb_alloc, p); tree->trb_count--; return (void *) item; }