diff options
Diffstat (limited to 'lacos_rbtree.cc')
| -rw-r--r-- | lacos_rbtree.cc | 418 |
1 files changed, 418 insertions, 0 deletions
diff --git a/lacos_rbtree.cc b/lacos_rbtree.cc new file mode 100644 index 0000000..14404c0 --- /dev/null +++ b/lacos_rbtree.cc @@ -0,0 +1,418 @@ +/* Plzip - A parallel version of the lzip data compressor + Copyright (C) 2009 Laszlo Ersek. + Copyright (C) 2009 Antonio Diaz Diaz. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ + +#define _FILE_OFFSET_BITS 64 + +#include <cstddef> + +#include "lacos_rbtree.h" + + +enum lacos_rbtree_color { + LACOS_RBTREE_RED, + LACOS_RBTREE_BLACK +}; + +struct lacos_rbtree_node { + void *data; + lacos_rbtree_node *parent, + *left, + *right; + lacos_rbtree_color color; +}; + + +lacos_rbtree_node * +lacos_rbtree_find( lacos_rbtree_node *root, const void *key, + int (*cmp)(const void *cmp_key, const void *cmp_data)) +{ + int cmp_res; + while (root && (cmp_res = (*cmp)(key, root->data))) + root = cmp_res < 0 ? root->left : root->right; + return root; +} + + +lacos_rbtree_node * +lacos_rbtree_min( lacos_rbtree_node *root) +{ + lacos_rbtree_node *tmp; + + if (!root) + return 0; + + while ((tmp = root->left)) + root = tmp; + + return root; +} + + +lacos_rbtree_node * +lacos_rbtree_max( lacos_rbtree_node *root) +{ + lacos_rbtree_node *tmp; + + if (!root) + return 0; + + while ((tmp = root->right)) + root = tmp; + + return root; +} + + +lacos_rbtree_node * +lacos_rbtree_next( lacos_rbtree_node *current) +{ + lacos_rbtree_node *tmp; + + if (!current) + return 0; + + if ((tmp = current->right)) { + while ((current = tmp->left)) + tmp = current; + return tmp; + } + + while ((tmp = current->parent) && current == tmp->right) + current = tmp; + + return tmp; +} + + +lacos_rbtree_node * +lacos_rbtree_prev( lacos_rbtree_node *current) +{ + lacos_rbtree_node *tmp; + + if (!current) + return 0; + + if ((tmp = current->left)) { + while ((current = tmp->right)) + tmp = current; + return tmp; + } + + while ((tmp = current->parent) && current == tmp->left) + current = tmp; + + return tmp; +} + + +static void +lacos_rbtree_rotate_left( lacos_rbtree_node **new_root, + lacos_rbtree_node *rotation_root) +{ + lacos_rbtree_node + *parent = rotation_root->parent, + *rc = rotation_root->right, + *rlc = rc->left; + + rotation_root->right = rlc; + if (rlc) + rlc->parent = rotation_root; + rc->parent = parent; + if (parent) + if (rotation_root == parent->left) + parent->left = rc; + else + parent->right = rc; + else + *new_root = rc; + rc->left = rotation_root; + rotation_root->parent = rc; +} + + +static void +lacos_rbtree_rotate_right( lacos_rbtree_node **new_root, + lacos_rbtree_node *rotation_root) +{ + lacos_rbtree_node + *parent = rotation_root->parent, + *lc = rotation_root->left, + *lrc = lc->right; + + rotation_root->left = lrc; + if (lrc) + lrc->parent = rotation_root; + lc->parent = parent; + if (parent) + if (rotation_root == parent->left) + parent->left = lc; + else + parent->right = lc; + else + *new_root = lc; + lc->right = rotation_root; + rotation_root->parent = lc; +} + + +int +lacos_rbtree_insert( lacos_rbtree_node **new_root, + lacos_rbtree_node **new_node, void *new_data, + int (*cmp)(const void *cmp_new_data, const void *cmp_data), + void *(*alloc)(size_t size, void *alloc_ctl), void *alloc_ctl) +{ + int cmp_res = 0; + lacos_rbtree_node *tmp = *new_root, *parent = 0; + + while (tmp && (cmp_res = (*cmp)(new_data, tmp->data))) { + parent = tmp; + tmp = cmp_res < 0 ? tmp->left : tmp->right; + } + + if (tmp) { + *new_node = tmp; + return -1; + } + + if (!(*new_node = tmp = (lacos_rbtree_node *)(*alloc)(sizeof(lacos_rbtree_node), + alloc_ctl))) + return -1; + + tmp->data = new_data; + tmp->parent = parent; + tmp->left = 0; + tmp->right = 0; + if (parent) + if (cmp_res < 0) + parent->left = tmp; + else + parent->right = tmp; + else { + *new_root = tmp; + tmp->color = LACOS_RBTREE_BLACK; + return 0; + } + + { + lacos_rbtree_node *root = *new_root, *grandparent, *uncle; + + tmp->color = LACOS_RBTREE_RED; + + while (tmp != root && LACOS_RBTREE_RED == parent->color) { + grandparent = parent->parent; + if (parent == grandparent->left) { + uncle = grandparent->right; + if (uncle && LACOS_RBTREE_RED == uncle->color) { + parent->color = LACOS_RBTREE_BLACK; + uncle->color = LACOS_RBTREE_BLACK; + grandparent->color = LACOS_RBTREE_RED; + tmp = grandparent; + parent = tmp->parent; + } + else { + if (tmp == parent->right) { + tmp = parent; + lacos_rbtree_rotate_left(&root, tmp); + parent = tmp->parent; + grandparent = parent->parent; + } + parent->color = LACOS_RBTREE_BLACK; + grandparent->color = LACOS_RBTREE_RED; + lacos_rbtree_rotate_right(&root, grandparent); + } + } + else { + uncle = grandparent->left; + if (uncle && LACOS_RBTREE_RED == uncle->color) { + parent->color = LACOS_RBTREE_BLACK; + uncle->color = LACOS_RBTREE_BLACK; + grandparent->color = LACOS_RBTREE_RED; + tmp = grandparent; + parent = tmp->parent; + } + else { + if (tmp == parent->left) { + tmp = parent; + lacos_rbtree_rotate_right(&root, tmp); + parent = tmp->parent; + grandparent = parent->parent; + } + parent->color = LACOS_RBTREE_BLACK; + grandparent->color = LACOS_RBTREE_RED; + lacos_rbtree_rotate_left(&root, grandparent); + } + } + } + + root->color = LACOS_RBTREE_BLACK; + *new_root = root; + } + return 0; +} + + +void +lacos_rbtree_delete( lacos_rbtree_node **new_root, + lacos_rbtree_node *old_node, void **old_data, + void (*dealloc)(void *ptr, void *alloc_ctl), void *alloc_ctl) +{ + lacos_rbtree_node *child, *parent, *root = *new_root, + *old_node_left = old_node->left, + *old_node_right = old_node->right, + *old_node_parent = old_node->parent; + lacos_rbtree_color color_of_firstly_unlinked; + + if (old_data) + *old_data = old_node->data; + + if (old_node_left && old_node_right) { + lacos_rbtree_node + *to_relink = old_node_right, + *tmp = to_relink->left; + + if (tmp) { + do { + to_relink = tmp; + tmp = tmp->left; + } while (tmp); + parent = to_relink->parent; + child = to_relink->right; + parent->left = child; + if (child) + child->parent = parent; + to_relink->right = old_node_right; + old_node_right->parent = to_relink; + } + else { + parent = old_node_right; + child = old_node_right->right; + } + + to_relink->left = old_node_left; + old_node_left->parent = to_relink; + + color_of_firstly_unlinked = to_relink->color; + to_relink->color = old_node->color; + + to_relink->parent = old_node_parent; + + if (old_node_parent) + if (old_node == old_node_parent->left) + old_node_parent->left = to_relink; + else + old_node_parent->right = to_relink; + else + root = to_relink; + } + else { + parent = old_node_parent; + child = old_node_left ? old_node_left : old_node_right; + color_of_firstly_unlinked = old_node->color; + + if (child) + child->parent = parent; + if (old_node_parent) + if (old_node == old_node_parent->left) + old_node_parent->left = child; + else + old_node_parent->right = child; + else + root = child; + } + + (*dealloc)(old_node, alloc_ctl); + + if (LACOS_RBTREE_BLACK == color_of_firstly_unlinked) { + lacos_rbtree_node *brother, *left_nephew, *right_nephew; + int left_black, right_black; + + while (child != root && (!child || LACOS_RBTREE_BLACK == child->color)) + if (child == parent->left) { + brother = parent->right; + if (LACOS_RBTREE_RED == brother->color) { + brother->color = LACOS_RBTREE_BLACK; + parent->color = LACOS_RBTREE_RED; + lacos_rbtree_rotate_left(&root, parent); + brother = parent->right; + } + left_nephew = brother->left; + right_nephew = brother->right; + right_black = !right_nephew + || LACOS_RBTREE_BLACK == right_nephew->color; + if ((!left_nephew || LACOS_RBTREE_BLACK == left_nephew->color) + && right_black) { + brother->color = LACOS_RBTREE_RED; + child = parent; + parent = parent->parent; + } + else { + if (right_black) { + left_nephew->color = LACOS_RBTREE_BLACK; + brother->color = LACOS_RBTREE_RED; + lacos_rbtree_rotate_right(&root, brother); + brother = parent->right; + right_nephew = brother->right; + } + brother->color = parent->color; + parent->color = LACOS_RBTREE_BLACK; + right_nephew->color = LACOS_RBTREE_BLACK; + lacos_rbtree_rotate_left(&root, parent); + child = root; + break; + } + } + else { + brother = parent->left; + if (LACOS_RBTREE_RED == brother->color) { + brother->color = LACOS_RBTREE_BLACK; + parent->color = LACOS_RBTREE_RED; + lacos_rbtree_rotate_right(&root, parent); + brother = parent->left; + } + right_nephew = brother->right; + left_nephew = brother->left; + left_black = !left_nephew || LACOS_RBTREE_BLACK == left_nephew->color; + if ((!right_nephew || LACOS_RBTREE_BLACK == right_nephew->color) + && left_black) { + brother->color = LACOS_RBTREE_RED; + child = parent; + parent = parent->parent; + } + else { + if (left_black) { + right_nephew->color = LACOS_RBTREE_BLACK; + brother->color = LACOS_RBTREE_RED; + lacos_rbtree_rotate_left(&root, brother); + brother = parent->left; + left_nephew = brother->left; + } + brother->color = parent->color; + parent->color = LACOS_RBTREE_BLACK; + left_nephew->color = LACOS_RBTREE_BLACK; + lacos_rbtree_rotate_right(&root, parent); + child = root; + break; + } + } + + if (child) + child->color = LACOS_RBTREE_BLACK; + } + + *new_root = root; +} |