Adding upstream version 0.1.upstream/0.1

Signed-off-by: Daniel Baumann <mail@daniel-baumann.ch>

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;
+}