diff options
Diffstat (limited to 'lacos_rbtree.cc')
| -rw-r--r-- | lacos_rbtree.cc | 418 |
1 files changed, 0 insertions, 418 deletions
diff --git a/lacos_rbtree.cc b/lacos_rbtree.cc deleted file mode 100644 index 14404c0..0000000 --- a/lacos_rbtree.cc +++ /dev/null @@ -1,418 +0,0 @@ -/* 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; -} |