Merging upstream version 0.2.

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

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