libsc  1.6.0
src/sc_avl.h
00001 /* *INDENT-OFF* */
00002 
00003 /*****************************************************************************
00004 
00005     avl.h - Source code for the AVL-tree library.
00006 
00007     Copyright (C) 1998  Michael H. Buselli <cosine@cosine.org>
00008     Copyright (C) 2000-2002  Wessel Dankers <wsl@nl.linux.org>
00009 
00010     This library is free software; you can redistribute it and/or
00011     modify it under the terms of the GNU Lesser General Public
00012     License as published by the Free Software Foundation; either
00013     version 2.1 of the License, or (at your option) any later version.
00014 
00015     This library is distributed in the hope that it will be useful,
00016     but WITHOUT ANY WARRANTY; without even the implied warranty of
00017     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00018     Lesser General Public License for more details.
00019 
00020     You should have received a copy of the GNU Lesser General Public
00021     License along with this library; if not, write to the Free Software
00022     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
00023 
00024     Augmented AVL-tree. Original by Michael H. Buselli <cosine@cosine.org>.
00025 
00026     Modified by Wessel Dankers <wsl@nl.linux.org> to add a bunch of bloat to
00027     the sourcecode, change the interface and squash a few bugs.
00028     Mail him if you find new bugs.
00029 
00030 *****************************************************************************/
00031 
00032 /* renamed from avl.h to sc_avl.h for the SC Library and modified */
00033 
00034 #ifndef _AVL_H
00035 #define _AVL_H
00036 
00037 #include <sc_containers.h>
00038 
00039 SC_EXTERN_C_BEGIN;
00040 
00041 /* modification to use count only */
00042 #define AVL_COUNT
00043 
00044 /* We need either depths, counts or both (the latter being the default) */
00045 #if !defined(AVL_DEPTH) && !defined(AVL_COUNT)
00046 #define AVL_DEPTH
00047 #define AVL_COUNT
00048 #endif
00049 
00050 /* User supplied function to compare two items like strcmp() does.
00051  * For example: cmp(a,b) will return:
00052  *   -1  if a < b
00053  *    0  if a = b
00054  *    1  if a > b
00055  */
00056 typedef int (*avl_compare_t)(const void *, const void *);
00057 
00058 /* User supplied function to delete an item when a node is free()d.
00059  * If NULL, the item is not free()d.
00060  */
00061 typedef void (*avl_freeitem_t)(void *);
00062 
00063 /* User supplied function to call on an item in foreach().
00064  */
00065 typedef void (*avl_foreach_t)(void *, void *);
00066 
00067 typedef struct avl_node_t {
00068         struct avl_node_t *next;
00069         struct avl_node_t *prev;
00070         struct avl_node_t *parent;
00071         struct avl_node_t *left;
00072         struct avl_node_t *right;
00073         void *item;
00074 #ifdef AVL_COUNT
00075         unsigned int count;
00076 #endif
00077 #ifdef AVL_DEPTH
00078         unsigned char depth;
00079 #endif
00080 } avl_node_t;
00081 
00082 typedef struct avl_tree_t {
00083         avl_node_t *head;
00084         avl_node_t *tail;
00085         avl_node_t *top;
00086         avl_compare_t cmp;
00087         avl_freeitem_t freeitem;
00088 } avl_tree_t;
00089 
00090 /* Initializes a new tree for elements that will be ordered using
00091  * the supplied strcmp()-like function.
00092  * Returns the value of avltree (even if it's NULL).
00093  * O(1) */
00094 extern avl_tree_t *avl_init_tree(avl_tree_t *avltree, avl_compare_t, avl_freeitem_t);
00095 
00096 /* Allocates and initializes a new tree for elements that will be
00097  * ordered using the supplied strcmp()-like function.
00098  * Aborts if memory could not be allocated.
00099  * O(1) */
00100 extern avl_tree_t *avl_alloc_tree(avl_compare_t, avl_freeitem_t);
00101 
00102 /* Frees the entire tree efficiently. Nodes will be free()d.
00103  * If the tree's freeitem is not NULL it will be invoked on every item.
00104  * O(n) */
00105 extern void avl_free_tree(avl_tree_t *);
00106 
00107 /* Reinitializes the tree structure for reuse. Nothing is free()d.
00108  * Compare and freeitem functions are left alone.
00109  * O(1) */
00110 extern void avl_clear_tree(avl_tree_t *);
00111 
00112 /* Free()s all nodes in the tree but leaves the tree itself.
00113  * If the tree's freeitem is not NULL it will be invoked on every item.
00114  * O(n) */
00115 extern void avl_free_nodes(avl_tree_t *);
00116 
00117 /* Initializes memory for use as a node. Returns NULL if avlnode is NULL.
00118  * O(1) */
00119 extern avl_node_t *avl_init_node(avl_node_t *avlnode, void *item);
00120 
00121 /* Insert an item into the tree and return the new node.
00122  * Aborts if memory for the new node could not be allocated.
00123  * Returns NULL if the node is already in the tree, or the new node.
00124  * O(lg n) */
00125 extern avl_node_t *avl_insert(avl_tree_t *, void *item);
00126 
00127 /* Insert a node into the tree and return it.
00128  * Returns NULL if the node is already in the tree.
00129  * O(lg n) */
00130 extern avl_node_t *avl_insert_node(avl_tree_t *, avl_node_t *);
00131 
00132 /* Insert a node in an empty tree. If avlnode is NULL, the tree will be
00133  * cleared and ready for re-use.
00134  * If the tree is not empty, the old nodes are left dangling.
00135  * O(1) */
00136 extern avl_node_t *avl_insert_top(avl_tree_t *, avl_node_t *avlnode);
00137 
00138 /* Insert a node before another node. Returns the new node.
00139  * If old is NULL, the item is appended to the tree.
00140  * O(lg n) */
00141 extern avl_node_t *avl_insert_before(avl_tree_t *, avl_node_t *old, avl_node_t *nw);
00142 
00143 /* Insert a node after another node. Returns the new node.
00144  * If old is NULL, the item is prepended to the tree.
00145  * O(lg n) */
00146 extern avl_node_t *avl_insert_after(avl_tree_t *, avl_node_t *old, avl_node_t *nw);
00147 
00148 /* Deletes a node from the tree. Returns immediately if the node is NULL.
00149  * The item will not be free()d regardless of the tree's freeitem handler.
00150  * This function comes in handy if you need to update the search key.
00151  * O(lg n) */
00152 extern void avl_unlink_node(avl_tree_t *, avl_node_t *);
00153 
00154 /* Deletes a node from the tree. Returns immediately if the node is NULL.
00155  * If the tree's freeitem is not NULL, it is invoked on the item.
00156  * If it is, returns the item.
00157  * O(lg n) */
00158 extern void *avl_delete_node(avl_tree_t *, avl_node_t *);
00159 
00160 /* Searches for an item in the tree and deletes it if found.
00161  * If the tree's freeitem is not NULL, it is invoked on the item.
00162  * If it is, returns the item.
00163  * O(lg n) */
00164 extern void *avl_delete(avl_tree_t *, const void *item);
00165 
00166 /* If exactly one node is moved in memory, this will fix the pointers
00167  * in the tree that refer to it. It must be an exact shallow copy.
00168  * Returns the pointer to the old position.
00169  * O(1) */
00170 extern avl_node_t *avl_fixup_node(avl_tree_t *, avl_node_t *nw);
00171 
00172 /* Searches for a node with the key closest (or equal) to the given item.
00173  * If avlnode is not NULL, *avlnode will be set to the node found or NULL
00174  * if the tree is empty. Return values:
00175  *   -1  if the returned node is smaller
00176  *    0  if the returned node is equal or if the tree is empty
00177  *    1  if the returned node is greater
00178  * O(lg n) */
00179 extern int avl_search_closest(const avl_tree_t *, const void *item, avl_node_t **avlnode);
00180 
00181 /* Searches for the item in the tree and returns a matching node if found
00182  * or NULL if not.
00183  * O(lg n) */
00184 extern avl_node_t *avl_search(const avl_tree_t *, const void *item);
00185 
00186 /* Calls the callback function for every item in the tree in order.
00187  * O(n) */
00188 extern void avl_foreach(avl_tree_t *, avl_foreach_t, void *);
00189 
00190 #ifdef AVL_COUNT
00191 /* Returns the number of nodes in the tree.
00192  * O(1) */
00193 extern unsigned int avl_count(const avl_tree_t *);
00194 
00195 /* Searches a node by its rank in the list. Counting starts at 0.
00196  * Returns NULL if the index exceeds the number of nodes in the tree.
00197  * O(lg n) */
00198 extern avl_node_t *avl_at(const avl_tree_t *, unsigned int);
00199 
00200 /* Returns the rank of a node in the list. Counting starts at 0.
00201  * O(lg n) */
00202 extern unsigned int avl_index(const avl_node_t *);
00203 
00204 /* Copies all items into an array of void *.
00205 * O(n) */
00206 extern void avl_to_array (avl_tree_t *, sc_array_t *);
00207 
00208 #endif /* AVL_COUNT */
00209 
00210 SC_EXTERN_C_END;
00211 
00212 #endif /* !_AVL_H */
 All Data Structures Files Functions Variables Typedefs Defines