summaryrefslogtreecommitdiffstats
path: root/lacos_rbtree.cc
diff options
context:
space:
mode:
authorDaniel Baumann <mail@daniel-baumann.ch>2015-11-07 15:08:12 +0000
committerDaniel Baumann <mail@daniel-baumann.ch>2015-11-07 15:08:12 +0000
commit9eab306d85e2f8e6ba93f33ce3c04f238e969b67 (patch)
treef832251ea988b9ee317ba7a6f0defea0c77fbea4 /lacos_rbtree.cc
parentInitial commit. (diff)
downloadplzip-9eab306d85e2f8e6ba93f33ce3c04f238e969b67.tar.xz
plzip-9eab306d85e2f8e6ba93f33ce3c04f238e969b67.zip
Adding upstream version 0.1.upstream/0.1
Signed-off-by: Daniel Baumann <mail@daniel-baumann.ch>
Diffstat (limited to 'lacos_rbtree.cc')
-rw-r--r--lacos_rbtree.cc418
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;
+}