#include "config.h"
#include "log.h"
#include "fptr_wlist.h"
#include "util/rbtree.h"
#define BLACK 0
#define RED 1
rbnode_t rbtree_null_node = {
RBTREE_NULL,
RBTREE_NULL,
RBTREE_NULL,
NULL,
BLACK
};
static void rbtree_rotate_left(rbtree_t *rbtree, rbnode_t *node);
static void rbtree_rotate_right(rbtree_t *rbtree, rbnode_t *node);
static void rbtree_insert_fixup(rbtree_t *rbtree, rbnode_t *node);
static void rbtree_delete_fixup(rbtree_t* rbtree, rbnode_t* child, rbnode_t* child_parent);
rbtree_t *
rbtree_create (int (*cmpf)(const void *, const void *))
{
rbtree_t *rbtree;
rbtree = (rbtree_t *) malloc(sizeof(rbtree_t));
if (!rbtree) {
return NULL;
}
rbtree_init(rbtree, cmpf);
return rbtree;
}
void
rbtree_init(rbtree_t *rbtree, int (*cmpf)(const void *, const void *))
{
rbtree->root = RBTREE_NULL;
rbtree->count = 0;
rbtree->cmp = cmpf;
}
static void
rbtree_rotate_left(rbtree_t *rbtree, rbnode_t *node)
{
rbnode_t *right = node->right;
node->right = right->left;
if (right->left != RBTREE_NULL)
right->left->parent = node;
right->parent = node->parent;
if (node->parent != RBTREE_NULL) {
if (node == node->parent->left) {
node->parent->left = right;
} else {
node->parent->right = right;
}
} else {
rbtree->root = right;
}
right->left = node;
node->parent = right;
}
static void
rbtree_rotate_right(rbtree_t *rbtree, rbnode_t *node)
{
rbnode_t *left = node->left;
node->left = left->right;
if (left->right != RBTREE_NULL)
left->right->parent = node;
left->parent = node->parent;
if (node->parent != RBTREE_NULL) {
if (node == node->parent->right) {
node->parent->right = left;
} else {
node->parent->left = left;
}
} else {
rbtree->root = left;
}
left->right = node;
node->parent = left;
}
static void
rbtree_insert_fixup(rbtree_t *rbtree, rbnode_t *node)
{
rbnode_t *uncle;
while (node != rbtree->root && node->parent->color == RED) {
if (node->parent == node->parent->parent->left) {
uncle = node->parent->parent->right;
if (uncle->color == RED) {
node->parent->color = BLACK;
uncle->color = BLACK;
node->parent->parent->color = RED;
node = node->parent->parent;
} else {
if (node == node->parent->right) {
node = node->parent;
rbtree_rotate_left(rbtree, node);
}
node->parent->color = BLACK;
node->parent->parent->color = RED;
rbtree_rotate_right(rbtree, node->parent->parent);
}
} else {
uncle = node->parent->parent->left;
if (uncle->color == RED) {
node->parent->color = BLACK;
uncle->color = BLACK;
node->parent->parent->color = RED;
node = node->parent->parent;
} else {
if (node == node->parent->left) {
node = node->parent;
rbtree_rotate_right(rbtree, node);
}
node->parent->color = BLACK;
node->parent->parent->color = RED;
rbtree_rotate_left(rbtree, node->parent->parent);
}
}
}
rbtree->root->color = BLACK;
}
rbnode_t *
rbtree_insert (rbtree_t *rbtree, rbnode_t *data)
{
int r = 0;
rbnode_t *node = rbtree->root;
rbnode_t *parent = RBTREE_NULL;
fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));
while (node != RBTREE_NULL) {
if ((r = rbtree->cmp(data->key, node->key)) == 0) {
return NULL;
}
parent = node;
if (r < 0) {
node = node->left;
} else {
node = node->right;
}
}
data->parent = parent;
data->left = data->right = RBTREE_NULL;
data->color = RED;
rbtree->count++;
if (parent != RBTREE_NULL) {
if (r < 0) {
parent->left = data;
} else {
parent->right = data;
}
} else {
rbtree->root = data;
}
rbtree_insert_fixup(rbtree, data);
return data;
}
rbnode_t *
rbtree_search (rbtree_t *rbtree, const void *key)
{
rbnode_t *node;
if (rbtree_find_less_equal(rbtree, key, &node)) {
return node;
} else {
return NULL;
}
}
static void swap_int8(uint8_t* x, uint8_t* y)
{
uint8_t t = *x; *x = *y; *y = t;
}
static void swap_np(rbnode_t** x, rbnode_t** y)
{
rbnode_t* t = *x; *x = *y; *y = t;
}
static void change_parent_ptr(rbtree_t* rbtree, rbnode_t* parent, rbnode_t* old, rbnode_t* new)
{
if(parent == RBTREE_NULL)
{
log_assert(rbtree->root == old);
if(rbtree->root == old) rbtree->root = new;
return;
}
log_assert(parent->left == old || parent->right == old
|| parent->left == new || parent->right == new);
if(parent->left == old) parent->left = new;
if(parent->right == old) parent->right = new;
}
static void change_child_ptr(rbnode_t* child, rbnode_t* old, rbnode_t* new)
{
if(child == RBTREE_NULL) return;
log_assert(child->parent == old || child->parent == new);
if(child->parent == old) child->parent = new;
}
rbnode_t*
rbtree_delete(rbtree_t *rbtree, const void *key)
{
rbnode_t *to_delete;
rbnode_t *child;
if((to_delete = rbtree_search(rbtree, key)) == 0) return 0;
rbtree->count--;
if(to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL)
{
rbnode_t *smright = to_delete->right;
while(smright->left != RBTREE_NULL)
smright = smright->left;
swap_int8(&to_delete->color, &smright->color);
change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);
if(to_delete->right != smright)
change_parent_ptr(rbtree, smright->parent, smright, to_delete);
change_child_ptr(smright->left, smright, to_delete);
change_child_ptr(smright->left, smright, to_delete);
change_child_ptr(smright->right, smright, to_delete);
change_child_ptr(smright->right, smright, to_delete);
change_child_ptr(to_delete->left, to_delete, smright);
if(to_delete->right != smright)
change_child_ptr(to_delete->right, to_delete, smright);
if(to_delete->right == smright)
{
to_delete->right = to_delete;
smright->parent = smright;
}
swap_np(&to_delete->parent, &smright->parent);
swap_np(&to_delete->left, &smright->left);
swap_np(&to_delete->right, &smright->right);
}
log_assert(to_delete->left == RBTREE_NULL || to_delete->right == RBTREE_NULL);
if(to_delete->left != RBTREE_NULL) child = to_delete->left;
else child = to_delete->right;
change_parent_ptr(rbtree, to_delete->parent, to_delete, child);
change_child_ptr(child, to_delete, to_delete->parent);
if(to_delete->color == RED)
{
}
else if(child->color == RED)
{
if(child!=RBTREE_NULL) child->color = BLACK;
}
else rbtree_delete_fixup(rbtree, child, to_delete->parent);
to_delete->parent = RBTREE_NULL;
to_delete->left = RBTREE_NULL;
to_delete->right = RBTREE_NULL;
to_delete->color = BLACK;
return to_delete;
}
static void rbtree_delete_fixup(rbtree_t* rbtree, rbnode_t* child, rbnode_t* child_parent)
{
rbnode_t* sibling;
int go_up = 1;
if(child_parent->right == child) sibling = child_parent->left;
else sibling = child_parent->right;
while(go_up)
{
if(child_parent == RBTREE_NULL)
{
return;
}
if(sibling->color == RED)
{
child_parent->color = RED;
sibling->color = BLACK;
if(child_parent->right == child)
rbtree_rotate_right(rbtree, child_parent);
else rbtree_rotate_left(rbtree, child_parent);
if(child_parent->right == child) sibling = child_parent->left;
else sibling = child_parent->right;
}
if(child_parent->color == BLACK
&& sibling->color == BLACK
&& sibling->left->color == BLACK
&& sibling->right->color == BLACK)
{
if(sibling != RBTREE_NULL)
sibling->color = RED;
child = child_parent;
child_parent = child_parent->parent;
if(child_parent->right == child) sibling = child_parent->left;
else sibling = child_parent->right;
}
else go_up = 0;
}
if(child_parent->color == RED
&& sibling->color == BLACK
&& sibling->left->color == BLACK
&& sibling->right->color == BLACK)
{
if(sibling != RBTREE_NULL)
sibling->color = RED;
child_parent->color = BLACK;
return;
}
log_assert(sibling != RBTREE_NULL);
if(child_parent->right == child
&& sibling->color == BLACK
&& sibling->right->color == RED
&& sibling->left->color == BLACK)
{
sibling->color = RED;
sibling->right->color = BLACK;
rbtree_rotate_left(rbtree, sibling);
if(child_parent->right == child) sibling = child_parent->left;
else sibling = child_parent->right;
}
else if(child_parent->left == child
&& sibling->color == BLACK
&& sibling->left->color == RED
&& sibling->right->color == BLACK)
{
sibling->color = RED;
sibling->left->color = BLACK;
rbtree_rotate_right(rbtree, sibling);
if(child_parent->right == child) sibling = child_parent->left;
else sibling = child_parent->right;
}
sibling->color = child_parent->color;
child_parent->color = BLACK;
if(child_parent->right == child)
{
log_assert(sibling->left->color == RED);
sibling->left->color = BLACK;
rbtree_rotate_right(rbtree, child_parent);
}
else
{
log_assert(sibling->right->color == RED);
sibling->right->color = BLACK;
rbtree_rotate_left(rbtree, child_parent);
}
}
int
rbtree_find_less_equal(rbtree_t *rbtree, const void *key, rbnode_t **result)
{
int r;
rbnode_t *node;
log_assert(result);
node = rbtree->root;
*result = NULL;
fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));
while (node != RBTREE_NULL) {
r = rbtree->cmp(key, node->key);
if (r == 0) {
*result = node;
return 1;
}
if (r < 0) {
node = node->left;
} else {
*result = node;
node = node->right;
}
}
return 0;
}
rbnode_t *
rbtree_first (rbtree_t *rbtree)
{
rbnode_t *node;
for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left);
return node;
}
rbnode_t *
rbtree_last (rbtree_t *rbtree)
{
rbnode_t *node;
for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right);
return node;
}
rbnode_t *
rbtree_next (rbnode_t *node)
{
rbnode_t *parent;
if (node->right != RBTREE_NULL) {
for (node = node->right; node->left != RBTREE_NULL; node = node->left);
} else {
parent = node->parent;
while (parent != RBTREE_NULL && node == parent->right) {
node = parent;
parent = parent->parent;
}
node = parent;
}
return node;
}
rbnode_t *
rbtree_previous(rbnode_t *node)
{
rbnode_t *parent;
if (node->left != RBTREE_NULL) {
for (node = node->left; node->right != RBTREE_NULL; node = node->right);
} else {
parent = node->parent;
while (parent != RBTREE_NULL && node == parent->left) {
node = parent;
parent = parent->parent;
}
node = parent;
}
return node;
}
static void
traverse_post(void (*func)(rbnode_t*, void*), void* arg, rbnode_t* node)
{
if(!node || node == RBTREE_NULL)
return;
traverse_post(func, arg, node->left);
traverse_post(func, arg, node->right);
(*func)(node, arg);
}
void
traverse_postorder(rbtree_t* tree, void (*func)(rbnode_t*, void*), void* arg)
{
traverse_post(func, arg, tree->root);
}