summaryrefslogtreecommitdiffstats
path: root/lacos_rbtree.h
diff options
context:
space:
mode:
authorDaniel Baumann <mail@daniel-baumann.ch>2015-11-07 15:10:42 +0000
committerDaniel Baumann <mail@daniel-baumann.ch>2015-11-07 15:10:42 +0000
commite2f36dd00ba51cd2e5c1793bfd5327c5d4aba142 (patch)
treecf7e6fe72f0d01c3f0a275ab3e0aafd266c9dc7e /lacos_rbtree.h
parentAdding debian version 0.1-1. (diff)
downloadplzip-e2f36dd00ba51cd2e5c1793bfd5327c5d4aba142.tar.xz
plzip-e2f36dd00ba51cd2e5c1793bfd5327c5d4aba142.zip
Merging upstream version 0.2.
Signed-off-by: Daniel Baumann <mail@daniel-baumann.ch>
Diffstat (limited to 'lacos_rbtree.h')
-rw-r--r--lacos_rbtree.h249
1 files changed, 0 insertions, 249 deletions
diff --git a/lacos_rbtree.h b/lacos_rbtree.h
deleted file mode 100644
index 1945233..0000000
--- a/lacos_rbtree.h
+++ /dev/null
@@ -1,249 +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/>.
-*/
-
-#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