+ rbl = new_rbl();
+ rbl->data = data;
+
+ return rbl_insert_rbl(tree, rbl);
+}
+
+/* Restore red-black property after violation due to a deletion */
+void rbl_delete_fixup(rbl_t *x)
+{
+ rbl_t *w;
+
+ while(x != x->tree->top && x->color == RBL_BLACK)
+ {
+ if(x == x->parent->left)
+ {
+ w = x->parent->right;
+ if(w->color == RBL_RED)
+ {
+ w->color = RBL_BLACK;
+ x->partent->color = RBL_RED;
+ rbl_left_rotate(x->parent);
+ w = x->parent->right;
+ }
+ if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
+ {
+ w->color = RBL_RED;
+ x = x->parent;
+ }
+ else
+ {
+ if(w->right->color == RBL_BLACK)
+ {
+ w->left->color = RBL_BLACK;
+ w->color = RBL_RED;
+ rbl_right_rotate(w);
+ w = x->parent->right;
+ }
+ w->color = x->parent->color;
+ x->parent->color = RBL_BLACK;
+ w->right->color = RBL_BLACK;
+ rbl_left_rotate(x->parent);
+ x = x->tree->top;
+ }
+ }
+ else
+ {
+ w = x->parent->left;
+ if(w->color == RBL_RED)
+ {
+ w->color = RBL_BLACK;
+ x->partent->color = RBL_RED;
+ rbl_right_rotate(x->parent);
+ w = x->parent->left;
+ }
+ if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
+ {
+ w->color = RBL_RED;
+ x = x->parent;
+ }
+ else
+ {
+ if(w->left->color == RBL_BLACK)
+ {
+ w->right->color = RBL_BLACK;
+ w->color = RBL_RED;
+ rbl_left_rotate(w);
+ w = x->parent->left;
+ }
+ w->color = x->parent->color;
+ x->parent->color = RBL_BLACK;
+ w->left->color = RBL_BLACK;
+ rbl_right_rotate(x->parent);
+ x = x->tree->top;
+ }
+ }
+ }
+
+ x->color = RBL_BLACK;
+}
+
+/* Unlink node from the tree, but keep the node intact. */
+rbl_t rbl_unlink_rbl(rbl_t *rbl)
+{
+ rbl_t *x, *y;
+
+ /* Binary tree delete */
+
+ if(rbl->left && rbl->right)
+ y = rbl->next;
+ else
+ y = rbl;
+
+ if(y->left)
+ x = y->left;
+ else
+ x = y->right;
+
+ if(x)
+ x->parent = y->parent;
+
+ if(!y->parent)
+ rbl->tree->top = x;
+ else
+ if(y == y->parent->left)
+ y->parent->left = x;
+ else
+ y->parent->right = x;
+
+ if(y != rbl)
+ {
+ y->left = rbl->left;
+ y->right = rbl->right;
+ y->parent = rbl->parent;
+ if(rbl == rbl->parent->left)
+ rbl->parent->left = y;
+ else
+ rbl->parent->right = y;
+ }
+
+ /* Linked list delete */
+
+ if(rbl->prev)
+ rbl->prev->next = rbl->next;
+ else
+ rbl->tree->head = rbl->next;
+
+ if(rbl->next)
+ rbl->next->prev = rbl->prev;
+ else
+ rbl->tree->tail = rbl->prev;
+
+ /* Red-black part of delete */
+
+ if(y->color == RBL_BLACK)
+ rbl_delete_fixup(x);
+
+ return rbl;
+}
+
+/* Search node in tree and unlink it */
+rbl_t rbl_unlink(rbltree_t *tree, void *data)
+{
+ rbl_t *rbl;
+
+ rbl = rbl_search(tree, data);
+
+ if(rbl)
+ return rbl_unlink_rbl(rbl);
+ else
+ return NULL;
+}
+
+/* Unlink node and free it */
+void rbl_delete_rbl(rbl_t *rbl)
+{
+ free_rbl(rbl_unlink_rbl(rbl));
+}
+
+/* Search node in tree, unlink and free it */
+void rbl_delete(rbltree_t *tree, void *data)
+{
+ free_rbl(rbl_unlink(tree, data));
+}
+
+/* Do action for each list entry (in order)
+ Deletion of entry for which action is called is allowed.
+ */
+void rbl_foreach(rbltree_t *tree, rbl_action_t *action)
+{
+ rbl_t *rbl, *next;
+
+ for(rbl = tree->head; rbl; rbl = next);
+ {
+ next = rbl->next;
+ action(rbl);
+ }