1 files changed, 249 insertions, 0 deletions
diff --git a/lacos_rbtree.h b/lacos_rbtree.h
new file mode 100644
index 0000000..1945233
--- /dev/null
+++ b/lacos_rbtree.h
@@ -0,0 +1,249 @@
+/*  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/>.
+*/
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+
+struct lacos_rbtree_node;
+/*
+  Opaque data type for red-black binary tree nodes. To get its data pointer,
+  cast a (struct lacos_rbtree_node *) object to (void **) and derefer it once.
+  Empty trees equal to (struct lacos_rbtree_node *)0.
+
+  This group of functions is generally not thread-safe (although it doesn't use
+  any static data), because the non-read-only operations must exclude all
+  operations on the same tree via external locking in a multi-threaded
+  environment.
+
+  If you want to alter the (your own) "key" field in an element, you mustn't do
+  that in one step. It must involve one delete and one insert operation, in the
+  order of your choice. Delete-insert is probably faster than insert-delete.
+*/
+
+
+/*
+  The functions below all return and mainly take pointers to nodes, not
+  elements (pointers to void). However, for simplicity of language, they are
+  described as if they operated on pointers to void (elements).
+*/
+
+
+lacos_rbtree_node *
+lacos_rbtree_find( lacos_rbtree_node *root, const void *key,
+    int (*cmp)(const void *cmp_key, const void *cmp_data));
+/*
+  USAGE:
+    Find an element in the tree.
+
+  ARGUMENTS:
+    root:
+      Root of the tree.
+
+    key:
+      This specifies which element should be found. This doesn't need to be an
+      element, it can be a standalone key too, if you write the "cmp" function
+      accordingly.
+
+    cmp:
+      A function which should return an integer less than, equal to, or greater
+      than zero if the "key" argument compares less than, equal to, or greater
+      than the currently inspected element in the tree.
+
+  RETURN VALUE:
+    If the key is found, this function returns the element (actually the
+    address of the containing node). If it is not found, 0 is returned.
+
+  READ-ONLY OPERATION:
+    Yes.
+*/
+
+
+lacos_rbtree_node *
+lacos_rbtree_min( lacos_rbtree_node *root);
+/*
+  USAGE:
+    Get the smallest element in the tree.
+
+  ARGUMENTS:
+    root:
+      Root of the tree.
+
+  RETURN VALUE:
+    If the tree is empty ("root" is null), 0 is returned. Otherwise, the
+    smallest element is returned.
+
+  READ-ONLY OPERATION:
+    Yes.
+*/
+
+
+lacos_rbtree_node *
+lacos_rbtree_max( lacos_rbtree_node *root);
+/*
+  USAGE:
+    Get the greatest element in the tree.
+
+  ARGUMENTS:
+    root:
+      Root of the tree.
+
+  RETURN VALUE:
+    If the tree is empty ("root" is null), 0 is returned. Otherwise, the
+    greatest element is returned.
+
+  READ-ONLY OPERATION:
+    Yes.
+*/
+
+
+lacos_rbtree_node *
+lacos_rbtree_next( lacos_rbtree_node *current);
+/*
+  USAGE:
+    Get the smallest element greater than "current".
+
+  ARGUMENTS:
+    current:
+      An element.
+
+  RETURN VALUE:
+    If "current" is null or the last element in the tree, 0 is returned.
+    Otherwise, the smallest element greater than "current" is returned.
+
+  READ-ONLY OPERATION:
+    Yes.
+*/
+
+
+lacos_rbtree_node *
+lacos_rbtree_prev( lacos_rbtree_node *current);
+/*
+  USAGE:
+    Get the greatest element smaller than "current".
+
+  ARGUMENTS:
+    current:
+      An element.
+
+  RETURN VALUE:
+    If "current" is null or the first element in the tree, 0 is returned.
+    Otherwise, the greatest element smaller than "current" is returned.
+
+  READ-ONLY OPERATION:
+    Yes.
+*/
+
+
+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);
+/*
+  USAGE:
+    Insert an element into the tree.
+
+  ARGUMENTS:
+    new_root:
+      Address of the tree's root; "*new_root" is the root of the tree. Both
+      input and output.
+
+    new_node:
+      Output only.
+
+    new_data:
+      The data to insert. This must not be a standalone key, this must be a
+      full element. It will only be linked in, not copied.
+
+    cmp:
+      A function which should return an integer less than, equal to, or greater
+      than zero if the "new_data" argument compares less than, equal to, or
+      greater than the currently inspected element in the tree.
+
+    alloc:
+      A memory allocator function whose externally observable behavior is
+      consistent with that of "malloc". It must work together with the
+      "dealloc" function passed to "lacos_rbtree_delete".
+
+    alloc_ctl:
+      A pointer to a custom data type to supply the "alloc" function with
+      optional auxiliary control information (arena etc).
+
+  RETURN VALUE:
+    If the insertion succeeds, 0 is returned, the new element is stored into
+    "*new_node", and "*new_root" is updated to the new root of the tree.
+
+    Otherwise, "*new_root" is not modified, and -1 is returned because of one
+    of the following errors:
+
+    - An element with a colliding key was found in the tree. In this case, the
+      colliding element is stored into "*new_node".
+    - There was not enough memory to allocate a new node object. In this case,
+      0 is stored into "*new_node".
+
+    Existing node pointers remain valid in any case.
+
+  READ-ONLY OPERATION:
+    No.
+*/
+
+
+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);
+/*
+  USAGE:
+    Remove an element from the tree.
+
+  ARGUMENTS:
+    new_root:
+      Address of the tree's root; "*new_root" is the root of the tree. Both
+      input and output.
+
+    old_node:
+      The element to remove. This must be a valid node pointer into the tree.
+
+    old_data:
+      The deleted element (the data of the deleted node, which was specified by
+      the "new_data" argument of the corresponding "lacos_rbtree_insert" call).
+      You could get the data also through "*(void **)old_node" before calling
+      this function. The data pointer of the node to delete is only accessed
+      and stored into "*old_data" if "old_data" is not 0.
+
+    dealloc:
+      A memory deallocator function whose externally observable behavior is
+      consistent with that of "free". It must work together with the "alloc"
+      function passed to "lacos_rbtree_insert".
+
+    alloc_ctl:
+      A pointer to a custom data type to supply the "dealloc" function with
+      optional auxiliary control information (arena etc).
+
+    Existing node pointers different from "old_node" remain valid.
+
+  READ-ONLY OPERATION:
+    No.
+*/
+
+
+#ifdef __cplusplus
+}
+#endif