From 9eab306d85e2f8e6ba93f33ce3c04f238e969b67 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 7 Nov 2015 16:08:12 +0100 Subject: Adding upstream version 0.1. Signed-off-by: Daniel Baumann --- lacos_rbtree.h | 249 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 249 insertions(+) create mode 100644 lacos_rbtree.h (limited to 'lacos_rbtree.h') 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 . +*/ + +#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 -- cgit v1.2.3