+/* Red-black tree operations taken from Introduction to Algorithms,
+ Cormen, Leiserson & Rivest, chapter 14.
+*/
+
+void rbl_left_rotate(rbl_t *x)
+{
+ rbl_t *y;
+
+ y = x->right;
+ x->right = y->left;
+
+ if(y->left)
+ y->left->parent = x;
+
+ y->parent = x->parent;
+
+ if(!x->parent)
+ x->tree->head = y;
+ else
+ if(x == x->parent->left)
+ x->parent->left = y;
+ else
+ x->parent->right = y;
+
+ y->left = x;
+ x->parent = y;
+}
+
+void rbl_right_rotate(rbl_t *y)
+{
+ rbl_t *x;
+
+ x = y->left;
+ y->left = x->right;
+
+ if(x->right)
+ x->right->parent = y;
+
+ x->parent = y->parent;
+
+ if(!y->parent)
+ y->tree->head = x;
+ else
+ if(y == y->parent->right)
+ y->parent->right = x;
+ else
+ y->parent->left = x;
+
+ x->right = y;
+ y->parent = x;
+}
+
+/* Insert a node into the rbl tree */
+rbl_t rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
+{
+ rbl_t *closest, y;
+ int result;
+
+ /* Binary tree and linked list insert */
+
+ if(tree->head)
+ {
+ closest = rbl_search_closest(tree, rbl->data);
+ result = tree->compare(rbl->data, data);
+ if(result < 0)
+ {
+ closest->left = rbl;
+ rbl->prev = closest->prev;
+ rbl->next = closest;
+ closest->prev = rbl;
+ rbl->prev->next = rbl;
+ }
+ else if(result > 0)
+ {
+ closest->right = rbl;
+ rbl->next = closest->right;
+ rbl->prev = closest;
+ closest->next = rbl;
+ rbl->next->prev = rbl;
+ }
+ else
+ return closest; /* Ofcourse, we cannot add two identical things */
+ }
+ else
+ tree->head = rbl;
+
+ /* Red-black part of insert */
+
+ rbl->color = RBL_RED;
+
+ while(rbl->parent && rbl->parent->color == RBL_RED)
+ {
+ if(rbl->parent == rbl->parent->parent->left)
+ {
+ y = rbl->parent->parent->right;
+ if(y->color == RBL_RED)
+ {
+ rbl->parent->color = RBL_BLACK;
+ y->color = RBL_BLACK;
+ rbl->parent->parent->color = RBL_RED;
+ rbl = rbl->parent->parent;
+ }
+ else
+ {
+ if(rbl == rbl->parent->right)
+ {
+ rbl = rbl->parent;
+ rbl_left_rotate(rbl);
+ }
+ rbl->parent->color = RBL_BLACK;
+ rbl->parent->parent->color = RBL_RED;
+ rbl_right_rotate(rbl->parent->parent);
+ }
+ }
+ else
+ {
+ y = rbl->parent->parent->left;
+ if(y->color == RBL_RED)
+ {
+ rbl->parent->color = RBL_BLACK;
+ y->color = RBL_BLACK;
+ rbl->parent->parent->color = RBL_RED;
+ rbl = rbl->parent->parent;
+ }
+ else
+ {
+ if(rbl == rbl->parent->left)
+ {
+ rbl = rbl->parent;
+ rbl_right_rotate(rbl);
+ }
+ rbl->parent->color = RBL_BLACK;
+ rbl->parent->parent->color = RBL_RED;
+ rbl_left_rotate(rbl->parent->parent);
+ }
+ }
+ }
+
+ tree->head->color = RBL_BLACK;
+
+ return rbl;
+}
+
+/* Create a new node and insert it into the tree */