X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;f=src%2Ftoolbox%2Favl.c;h=24981f51c0ed556687a368d3f21b2cac21c0731c;hb=6dba844bedc2e640fc5766eb013df0a115ab68bd;hp=66cce968fbb0c4bc393f967a47e318df1d786692;hpb=e398feab8946e1fcddce32da2682f3b71303d361;p=cacao.git diff --git a/src/toolbox/avl.c b/src/toolbox/avl.c index 66cce968f..24981f51c 100644 --- a/src/toolbox/avl.c +++ b/src/toolbox/avl.c @@ -1,890 +1,440 @@ -/* Produced by texiweb from libavl.w on 2004/01/08 at 23:19. */ +/* src/toolbox/avl.c - AVL tree implementation -/* libavl - library for manipulation of binary trees. - Copyright (C) 1998-2002 Free Software Foundation, Inc. + Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel, + C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring, + E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, + J. Wenninger, Institut f. Computersprachen - TU Wien + + This file is part of CACAO. 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 2 of the - License, or (at your option) any later version. + published by the Free Software Foundation; either version 2, 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. + 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, write to the Free Software - Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA - 02111-1307, USA. + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + 02110-1301, USA. + + Contact: cacao@cacaojvm.org + + Authors: Christian Thalinger + + Changes: + + $Id: avl.c 5123 2006-07-12 21:45:34Z twisti $ - The author may be contacted at on the Internet, or - write to Ben Pfaff, Stanford University, Computer Science Dept., 353 - Serra Mall, Stanford CA 94305, USA. */ + +#include "config.h" + #include -#include -#include -#include + +#include "vm/types.h" + +#include "mm/memory.h" #include "toolbox/avl.h" -/* Creates and returns a new table - with comparison function |compare| using parameter |param| - and memory allocator |allocator|. - Returns |NULL| if memory allocation failed. */ -struct avl_table * -avl_create (avl_comparison_func *compare, void *param, - struct libavl_allocator *allocator) +#if defined(ENABLE_THREADS) +# include "threads/native/lock.h" +# include "threads/native/threads.h" +#else +# include "threads/none/lock.h" +#endif + + +/* avl_create ****************************************************************** + + Creates a AVL tree structure. + +*******************************************************************************/ + +avl_tree *avl_create(avl_comparator *compar) { - struct avl_table *tree; + avl_tree *t; - assert (compare != NULL); + t = NEW(avl_tree); - if (allocator == NULL) - allocator = &avl_allocator_default; + t->root = NULL; + t->comparator = compar; + t->entries = 0; - tree = allocator->libavl_malloc (allocator, sizeof *tree); - if (tree == NULL) - return NULL; +#if defined(ENABLE_THREADS) + /* create lock object for this tree */ - tree->avl_root = NULL; - tree->avl_compare = compare; - tree->avl_param = param; - tree->avl_alloc = allocator; - tree->avl_count = 0; - tree->avl_generation = 0; + t->lock = NEW(java_objectheader); - return tree; -} + lock_init_object_lock(t->lock); +#endif -/* Search |tree| for an item matching |item|, and return it if found. - Otherwise return |NULL|. */ -void * -avl_find (const struct avl_table *tree, const void *item) -{ - const struct avl_node *p; - - assert (tree != NULL && item != NULL); - for (p = tree->avl_root; p != NULL; ) - { - int cmp = tree->avl_compare (item, p->avl_data, tree->avl_param); - - if (cmp < 0) - p = p->avl_link[0]; - else if (cmp > 0) - p = p->avl_link[1]; - else /* |cmp == 0| */ - return p->avl_data; - } - - return NULL; + return t; } -/* Inserts |item| into |tree| and returns a pointer to |item|'s address. - If a duplicate item is found in the tree, - returns a pointer to the duplicate without inserting |item|. - Returns |NULL| in case of memory allocation failure. */ -void ** -avl_probe (struct avl_table *tree, void *item) -{ - struct avl_node *y, *z; /* Top node to update balance factor, and parent. */ - struct avl_node *p, *q; /* Iterator, and parent. */ - struct avl_node *n; /* Newly inserted node. */ - struct avl_node *w; /* New root of rebalanced subtree. */ - int dir; /* Direction to descend. */ - - unsigned char da[AVL_MAX_HEIGHT]; /* Cached comparison results. */ - int k = 0; /* Number of cached results. */ - - assert (tree != NULL && item != NULL); - - z = (struct avl_node *) &tree->avl_root; - y = tree->avl_root; - dir = 0; - for (q = z, p = y; p != NULL; q = p, p = p->avl_link[dir]) - { - int cmp = tree->avl_compare (item, p->avl_data, tree->avl_param); - if (cmp == 0) - return &p->avl_data; - - if (p->avl_balance != 0) - z = q, y = p, k = 0; - da[k++] = dir = cmp > 0; - } - - n = q->avl_link[dir] = - tree->avl_alloc->libavl_malloc (tree->avl_alloc, sizeof *n); - if (n == NULL) - return NULL; - - tree->avl_count++; - n->avl_data = item; - n->avl_link[0] = n->avl_link[1] = NULL; - n->avl_balance = 0; - if (y == NULL) - return &n->avl_data; - - for (p = y, k = 0; p != n; p = p->avl_link[da[k]], k++) - if (da[k] == 0) - p->avl_balance--; - else - p->avl_balance++; - - if (y->avl_balance == -2) - { - struct avl_node *x = y->avl_link[0]; - if (x->avl_balance == -1) - { - w = x; - y->avl_link[0] = x->avl_link[1]; - x->avl_link[1] = y; - x->avl_balance = y->avl_balance = 0; - } - else - { - assert (x->avl_balance == +1); - w = x->avl_link[1]; - x->avl_link[1] = w->avl_link[0]; - w->avl_link[0] = x; - y->avl_link[0] = w->avl_link[1]; - w->avl_link[1] = y; - if (w->avl_balance == -1) - x->avl_balance = 0, y->avl_balance = +1; - else if (w->avl_balance == 0) - x->avl_balance = y->avl_balance = 0; - else /* |w->avl_balance == +1| */ - x->avl_balance = -1, y->avl_balance = 0; - w->avl_balance = 0; - } - } - else if (y->avl_balance == +2) - { - struct avl_node *x = y->avl_link[1]; - if (x->avl_balance == +1) - { - w = x; - y->avl_link[1] = x->avl_link[0]; - x->avl_link[0] = y; - x->avl_balance = y->avl_balance = 0; - } - else - { - assert (x->avl_balance == -1); - w = x->avl_link[0]; - x->avl_link[0] = w->avl_link[1]; - w->avl_link[1] = x; - y->avl_link[1] = w->avl_link[0]; - w->avl_link[0] = y; - if (w->avl_balance == +1) - x->avl_balance = 0, y->avl_balance = -1; - else if (w->avl_balance == 0) - x->avl_balance = y->avl_balance = 0; - else /* |w->avl_balance == -1| */ - x->avl_balance = +1, y->avl_balance = 0; - w->avl_balance = 0; - } - } - else - return &n->avl_data; - z->avl_link[y != z->avl_link[0]] = w; - - tree->avl_generation++; - return &n->avl_data; -} -/* Inserts |item| into |table|. - Returns |NULL| if |item| was successfully inserted - or if a memory allocation error occurred. - Otherwise, returns the duplicate item. */ -void * -avl_insert (struct avl_table *table, void *item) -{ - void **p = avl_probe (table, item); - return p == NULL || *p == item ? NULL : *p; -} +/* avl_newnode ***************************************************************** -/* Inserts |item| into |table|, replacing any duplicate item. - Returns |NULL| if |item| was inserted without replacing a duplicate, - or if a memory allocation error occurred. - Otherwise, returns the item that was replaced. */ -void * -avl_replace (struct avl_table *table, void *item) -{ - void **p = avl_probe (table, item); - if (p == NULL || *p == item) - return NULL; - else - { - void *r = *p; - *p = item; - return r; - } -} + Creates a new AVL node and sets the pointers correctly. -/* Deletes from |tree| and returns an item matching |item|. - Returns a null pointer if no matching item found. */ -void * -avl_delete (struct avl_table *tree, const void *item) -{ - /* Stack of nodes. */ - struct avl_node *pa[AVL_MAX_HEIGHT]; /* Nodes. */ - unsigned char da[AVL_MAX_HEIGHT]; /* |avl_link[]| indexes. */ - int k; /* Stack pointer. */ - - struct avl_node *p; /* Traverses tree to find node to delete. */ - int cmp; /* Result of comparison between |item| and |p|. */ - - assert (tree != NULL && item != NULL); - - k = 0; - p = (struct avl_node *) &tree->avl_root; - for (cmp = -1; cmp != 0; - cmp = tree->avl_compare (item, p->avl_data, tree->avl_param)) - { - int dir = cmp > 0; - - pa[k] = p; - da[k++] = dir; - - p = p->avl_link[dir]; - if (p == NULL) - return NULL; - } - item = p->avl_data; - - if (p->avl_link[1] == NULL) - pa[k - 1]->avl_link[da[k - 1]] = p->avl_link[0]; - else - { - struct avl_node *r = p->avl_link[1]; - if (r->avl_link[0] == NULL) - { - r->avl_link[0] = p->avl_link[0]; - r->avl_balance = p->avl_balance; - pa[k - 1]->avl_link[da[k - 1]] = r; - da[k] = 1; - pa[k++] = r; - } - else - { - struct avl_node *s; - int j = k++; - - for (;;) - { - da[k] = 0; - pa[k++] = r; - s = r->avl_link[0]; - if (s->avl_link[0] == NULL) - break; - - r = s; - } - - s->avl_link[0] = p->avl_link[0]; - r->avl_link[0] = s->avl_link[1]; - s->avl_link[1] = p->avl_link[1]; - s->avl_balance = p->avl_balance; - - pa[j - 1]->avl_link[da[j - 1]] = s; - da[j] = 1; - pa[j] = s; - } - } - - tree->avl_alloc->libavl_free (tree->avl_alloc, p); - - assert (k > 0); - while (--k > 0) - { - struct avl_node *y = pa[k]; - - if (da[k] == 0) - { - y->avl_balance++; - if (y->avl_balance == +1) - break; - else if (y->avl_balance == +2) - { - struct avl_node *x = y->avl_link[1]; - if (x->avl_balance == -1) - { - struct avl_node *w; - assert (x->avl_balance == -1); - w = x->avl_link[0]; - x->avl_link[0] = w->avl_link[1]; - w->avl_link[1] = x; - y->avl_link[1] = w->avl_link[0]; - w->avl_link[0] = y; - if (w->avl_balance == +1) - x->avl_balance = 0, y->avl_balance = -1; - else if (w->avl_balance == 0) - x->avl_balance = y->avl_balance = 0; - else /* |w->avl_balance == -1| */ - x->avl_balance = +1, y->avl_balance = 0; - w->avl_balance = 0; - pa[k - 1]->avl_link[da[k - 1]] = w; - } - else - { - y->avl_link[1] = x->avl_link[0]; - x->avl_link[0] = y; - pa[k - 1]->avl_link[da[k - 1]] = x; - if (x->avl_balance == 0) - { - x->avl_balance = -1; - y->avl_balance = +1; - break; - } - else - x->avl_balance = y->avl_balance = 0; - } - } - } - else - { - y->avl_balance--; - if (y->avl_balance == -1) - break; - else if (y->avl_balance == -2) - { - struct avl_node *x = y->avl_link[0]; - if (x->avl_balance == +1) - { - struct avl_node *w; - assert (x->avl_balance == +1); - w = x->avl_link[1]; - x->avl_link[1] = w->avl_link[0]; - w->avl_link[0] = x; - y->avl_link[0] = w->avl_link[1]; - w->avl_link[1] = y; - if (w->avl_balance == -1) - x->avl_balance = 0, y->avl_balance = +1; - else if (w->avl_balance == 0) - x->avl_balance = y->avl_balance = 0; - else /* |w->avl_balance == +1| */ - x->avl_balance = -1, y->avl_balance = 0; - w->avl_balance = 0; - pa[k - 1]->avl_link[da[k - 1]] = w; - } - else - { - y->avl_link[0] = x->avl_link[1]; - x->avl_link[1] = y; - pa[k - 1]->avl_link[da[k - 1]] = x; - if (x->avl_balance == 0) - { - x->avl_balance = +1; - y->avl_balance = -1; - break; - } - else - x->avl_balance = y->avl_balance = 0; - } - } - } - } - - tree->avl_count--; - tree->avl_generation++; - return (void *) item; -} +*******************************************************************************/ -/* Refreshes the stack of parent pointers in |trav| - and updates its generation number. */ -static void -trav_refresh (struct avl_traverser *trav) +static avl_node *avl_newnode(void *data) { - assert (trav != NULL); - - trav->avl_generation = trav->avl_table->avl_generation; - - if (trav->avl_node != NULL) - { - avl_comparison_func *cmp = trav->avl_table->avl_compare; - void *param = trav->avl_table->avl_param; - struct avl_node *node = trav->avl_node; - struct avl_node *i; - - trav->avl_height = 0; - for (i = trav->avl_table->avl_root; i != node; ) - { - assert (trav->avl_height < AVL_MAX_HEIGHT); - assert (i != NULL); - - trav->avl_stack[trav->avl_height++] = i; - i = i->avl_link[cmp (node->avl_data, i->avl_data, param) > 0]; - } - } -} + avl_node *n; -/* Initializes |trav| for use with |tree| - and selects the null node. */ -void -avl_t_init (struct avl_traverser *trav, struct avl_table *tree) -{ - trav->avl_table = tree; - trav->avl_node = NULL; - trav->avl_height = 0; - trav->avl_generation = tree->avl_generation; + n = NEW(avl_node); + + n->data = data; + + /* ATTENTION: NEW allocates memory zeroed out */ + +/* n->balance = 0; */ +/* n->childs[0] = NULL; */ +/* n->childs[1] = NULL; */ + + return n; } -/* Initializes |trav| for |tree| - and selects and returns a pointer to its least-valued item. - Returns |NULL| if |tree| contains no nodes. */ -void * -avl_t_first (struct avl_traverser *trav, struct avl_table *tree) -{ - struct avl_node *x; - assert (tree != NULL && trav != NULL); +/* avl_rotate_left ************************************************************* - trav->avl_table = tree; - trav->avl_height = 0; - trav->avl_generation = tree->avl_generation; + Does a left rotation on an AVL node. - x = tree->avl_root; - if (x != NULL) - while (x->avl_link[0] != NULL) - { - assert (trav->avl_height < AVL_MAX_HEIGHT); - trav->avl_stack[trav->avl_height++] = x; - x = x->avl_link[0]; - } - trav->avl_node = x; + A (node) B + \ / \ + B --> A C + \ + C - return x != NULL ? x->avl_data : NULL; -} +*******************************************************************************/ -/* Initializes |trav| for |tree| - and selects and returns a pointer to its greatest-valued item. - Returns |NULL| if |tree| contains no nodes. */ -void * -avl_t_last (struct avl_traverser *trav, struct avl_table *tree) +static void avl_rotate_left(avl_node **node) { - struct avl_node *x; + avl_node *tmp; + avl_node *tmpnode; - assert (tree != NULL && trav != NULL); + /* rotate the node */ - trav->avl_table = tree; - trav->avl_height = 0; - trav->avl_generation = tree->avl_generation; + tmp = *node; + tmpnode = tmp->childs[AVL_RIGHT]; + tmp->childs[AVL_RIGHT] = tmpnode->childs[AVL_LEFT]; + tmpnode->childs[AVL_LEFT] = tmp; - x = tree->avl_root; - if (x != NULL) - while (x->avl_link[1] != NULL) - { - assert (trav->avl_height < AVL_MAX_HEIGHT); - trav->avl_stack[trav->avl_height++] = x; - x = x->avl_link[1]; - } - trav->avl_node = x; + /* set new parent node */ - return x != NULL ? x->avl_data : NULL; + *node = tmpnode; } -/* Searches for |item| in |tree|. - If found, initializes |trav| to the item found and returns the item - as well. - If there is no matching item, initializes |trav| to the null item - and returns |NULL|. */ -void * -avl_t_find (struct avl_traverser *trav, struct avl_table *tree, void *item) -{ - struct avl_node *p, *q; - - assert (trav != NULL && tree != NULL && item != NULL); - trav->avl_table = tree; - trav->avl_height = 0; - trav->avl_generation = tree->avl_generation; - for (p = tree->avl_root; p != NULL; p = q) - { - int cmp = tree->avl_compare (item, p->avl_data, tree->avl_param); - - if (cmp < 0) - q = p->avl_link[0]; - else if (cmp > 0) - q = p->avl_link[1]; - else /* |cmp == 0| */ - { - trav->avl_node = p; - return p->avl_data; - } - - assert (trav->avl_height < AVL_MAX_HEIGHT); - trav->avl_stack[trav->avl_height++] = p; - } - - trav->avl_height = 0; - trav->avl_node = NULL; - return NULL; -} -/* Attempts to insert |item| into |tree|. - If |item| is inserted successfully, it is returned and |trav| is - initialized to its location. - If a duplicate is found, it is returned and |trav| is initialized to - its location. No replacement of the item occurs. - If a memory allocation failure occurs, |NULL| is returned and |trav| - is initialized to the null item. */ -void * -avl_t_insert (struct avl_traverser *trav, struct avl_table *tree, void *item) -{ - void **p; - - assert (trav != NULL && tree != NULL && item != NULL); - - p = avl_probe (tree, item); - if (p != NULL) - { - trav->avl_table = tree; - trav->avl_node = - ((struct avl_node *) - ((char *) p - offsetof (struct avl_node, avl_data))); - trav->avl_generation = tree->avl_generation - 1; - return *p; - } - else - { - avl_t_init (trav, tree); - return NULL; - } -} +/* avl_rotate_right ************************************************************ -/* Initializes |trav| to have the same current node as |src|. */ -void * -avl_t_copy (struct avl_traverser *trav, const struct avl_traverser *src) -{ - assert (trav != NULL && src != NULL); - - if (trav != src) - { - trav->avl_table = src->avl_table; - trav->avl_node = src->avl_node; - trav->avl_generation = src->avl_generation; - if (trav->avl_generation == trav->avl_table->avl_generation) - { - trav->avl_height = src->avl_height; - memcpy (trav->avl_stack, (const void *) src->avl_stack, - sizeof *trav->avl_stack * trav->avl_height); - } - } - - return trav->avl_node != NULL ? trav->avl_node->avl_data : NULL; -} + Does a right rotation on an AVL node. -/* Returns the next data item in inorder - within the tree being traversed with |trav|, - or if there are no more data items returns |NULL|. */ -void * -avl_t_next (struct avl_traverser *trav) -{ - struct avl_node *x; - - assert (trav != NULL); - - if (trav->avl_generation != trav->avl_table->avl_generation) - trav_refresh (trav); - - x = trav->avl_node; - if (x == NULL) - { - return avl_t_first (trav, trav->avl_table); - } - else if (x->avl_link[1] != NULL) - { - assert (trav->avl_height < AVL_MAX_HEIGHT); - trav->avl_stack[trav->avl_height++] = x; - x = x->avl_link[1]; - - while (x->avl_link[0] != NULL) - { - assert (trav->avl_height < AVL_MAX_HEIGHT); - trav->avl_stack[trav->avl_height++] = x; - x = x->avl_link[0]; - } - } - else - { - struct avl_node *y; - - do - { - if (trav->avl_height == 0) - { - trav->avl_node = NULL; - return NULL; - } - - y = x; - x = trav->avl_stack[--trav->avl_height]; - } - while (y == x->avl_link[1]); - } - trav->avl_node = x; - - return x->avl_data; -} + C (node) B + / / \ + B --> A C + / + A -/* Returns the previous data item in inorder - within the tree being traversed with |trav|, - or if there are no more data items returns |NULL|. */ -void * -avl_t_prev (struct avl_traverser *trav) -{ - struct avl_node *x; - - assert (trav != NULL); - - if (trav->avl_generation != trav->avl_table->avl_generation) - trav_refresh (trav); - - x = trav->avl_node; - if (x == NULL) - { - return avl_t_last (trav, trav->avl_table); - } - else if (x->avl_link[0] != NULL) - { - assert (trav->avl_height < AVL_MAX_HEIGHT); - trav->avl_stack[trav->avl_height++] = x; - x = x->avl_link[0]; - - while (x->avl_link[1] != NULL) - { - assert (trav->avl_height < AVL_MAX_HEIGHT); - trav->avl_stack[trav->avl_height++] = x; - x = x->avl_link[1]; - } - } - else - { - struct avl_node *y; - - do - { - if (trav->avl_height == 0) - { - trav->avl_node = NULL; - return NULL; - } - - y = x; - x = trav->avl_stack[--trav->avl_height]; - } - while (y == x->avl_link[0]); - } - trav->avl_node = x; - - return x->avl_data; -} +*******************************************************************************/ -/* Returns |trav|'s current item. */ -void * -avl_t_cur (struct avl_traverser *trav) +static void avl_rotate_right(avl_node **node) { - assert (trav != NULL); + avl_node *tmp; + avl_node *tmpnode; - return trav->avl_node != NULL ? trav->avl_node->avl_data : NULL; -} + /* rotate the node */ -/* Replaces the current item in |trav| by |new| and returns the item replaced. - |trav| must not have the null item selected. - The new item must not upset the ordering of the tree. */ -void * -avl_t_replace (struct avl_traverser *trav, void *new) -{ - void *old; + tmp = *node; + tmpnode = tmp->childs[AVL_LEFT]; + tmp->childs[AVL_LEFT] = tmpnode->childs[AVL_RIGHT]; + tmpnode->childs[AVL_RIGHT] = tmp; - assert (trav != NULL && trav->avl_node != NULL && new != NULL); - old = trav->avl_node->avl_data; - trav->avl_node->avl_data = new; - return old; + /* set new parent node */ + + *node = tmpnode; } -static void -copy_error_recovery (struct avl_node **stack, int height, - struct avl_table *new, avl_item_func *destroy) -{ - assert (stack != NULL && height >= 0 && new != NULL); - for (; height > 2; height -= 2) - stack[height - 1]->avl_link[1] = NULL; - avl_destroy (new, destroy); -} +/* avl_adjust_balance ********************************************************** -/* Copies |org| to a newly created tree, which is returned. - If |copy != NULL|, each data item in |org| is first passed to |copy|, - and the return values are inserted into the tree, - with |NULL| return values taken as indications of failure. - On failure, destroys the partially created new tree, - applying |destroy|, if non-null, to each item in the new tree so far, - and returns |NULL|. - If |allocator != NULL|, it is used for allocation in the new tree. - Otherwise, the same allocator used for |org| is used. */ -struct avl_table * -avl_copy (const struct avl_table *org, avl_copy_func *copy, - avl_item_func *destroy, struct libavl_allocator *allocator) -{ - struct avl_node *stack[2 * (AVL_MAX_HEIGHT + 1)]; - int height = 0; - - struct avl_table *new; - const struct avl_node *x; - struct avl_node *y; - - assert (org != NULL); - new = avl_create (org->avl_compare, org->avl_param, - allocator != NULL ? allocator : org->avl_alloc); - if (new == NULL) - return NULL; - new->avl_count = org->avl_count; - if (new->avl_count == 0) - return new; - - x = (const struct avl_node *) &org->avl_root; - y = (struct avl_node *) &new->avl_root; - for (;;) - { - while (x->avl_link[0] != NULL) - { - assert (height < 2 * (AVL_MAX_HEIGHT + 1)); - - y->avl_link[0] = - new->avl_alloc->libavl_malloc (new->avl_alloc, - sizeof *y->avl_link[0]); - if (y->avl_link[0] == NULL) - { - if (y != (struct avl_node *) &new->avl_root) - { - y->avl_data = NULL; - y->avl_link[1] = NULL; - } - - copy_error_recovery (stack, height, new, destroy); - return NULL; - } - - stack[height++] = (struct avl_node *) x; - stack[height++] = y; - x = x->avl_link[0]; - y = y->avl_link[0]; - } - y->avl_link[0] = NULL; - - for (;;) - { - y->avl_balance = x->avl_balance; - if (copy == NULL) - y->avl_data = x->avl_data; - else - { - y->avl_data = copy (x->avl_data, org->avl_param); - if (y->avl_data == NULL) - { - y->avl_link[1] = NULL; - copy_error_recovery (stack, height, new, destroy); - return NULL; - } - } - - if (x->avl_link[1] != NULL) - { - y->avl_link[1] = - new->avl_alloc->libavl_malloc (new->avl_alloc, - sizeof *y->avl_link[1]); - if (y->avl_link[1] == NULL) - { - copy_error_recovery (stack, height, new, destroy); - return NULL; - } - - x = x->avl_link[1]; - y = y->avl_link[1]; - break; - } - else - y->avl_link[1] = NULL; - - if (height <= 2) - return new; - - y = stack[--height]; - x = stack[--height]; - } - } -} + Does a balance adjustment after a double rotation. + +*******************************************************************************/ -/* Frees storage allocated for |tree|. - If |destroy != NULL|, applies it to each data item in inorder. */ -void -avl_destroy (struct avl_table *tree, avl_item_func *destroy) +static void avl_adjust_balance(avl_node *node) { - struct avl_node *p, *q; - - assert (tree != NULL); - - for (p = tree->avl_root; p != NULL; p = q) - if (p->avl_link[0] == NULL) - { - q = p->avl_link[1]; - if (destroy != NULL && p->avl_data != NULL) - destroy (p->avl_data, tree->avl_param); - tree->avl_alloc->libavl_free (tree->avl_alloc, p); - } - else - { - q = p->avl_link[0]; - p->avl_link[0] = q->avl_link[1]; - q->avl_link[1] = p; - } - - tree->avl_alloc->libavl_free (tree->avl_alloc, tree); + avl_node *left; + avl_node *right; + + left = node->childs[AVL_LEFT]; + right = node->childs[AVL_RIGHT]; + + switch (node->balance) { + case -1: + left->balance = 0; + right->balance = 1; + break; + + case 0: + left->balance = 0; + right->balance = 0; + break; + + case 1: + left->balance = -1; + right->balance = 0; + break; + } + + node->balance = 0; } -/* Allocates |size| bytes of space using |malloc()|. - Returns a null pointer if allocation fails. */ -void * -avl_malloc (struct libavl_allocator *allocator, size_t size) + +/* avl_insert_intern *********************************************************** + + Inserts a AVL node into a AVL tree. + +*******************************************************************************/ + +static s4 avl_insert_intern(avl_tree *tree, avl_node **node, void *data) { - assert (allocator != NULL && size > 0); - return malloc (size); + avl_node *tmpnode; + s4 res; + s4 direction; + s4 insert; + s4 balance; + + /* set temporary variable */ + + tmpnode = *node; + + /* per default no node was inserted */ + + insert = 0; + + /* compare the current node */ + + res = tree->comparator(data, tmpnode->data); + + /* is this node already in the tree? */ + + if (res == 0) + assert(0); + + /* goto left or right child */ + + direction = (res < 0) ? AVL_LEFT : AVL_RIGHT; + + /* there is a child, go recursive */ + + if (tmpnode->childs[direction]) { + balance = avl_insert_intern(tree, &tmpnode->childs[direction], data); + + } else { + avl_node *newnode; + + /* no child, create this node */ + + newnode = avl_newnode(data); + + /* insert into parent node */ + + tmpnode->childs[direction] = newnode; + + /* node was inserted, but don't set insert to 1, since this + insertion is handled in this recursion depth */ + + balance = 1; + } + + /* add insertion value to node balance, value depends on the + direction */ + + tmpnode->balance += (direction == AVL_LEFT) ? -balance : balance; + + if ((balance != 0) && (tmpnode->balance != 0)) { + if (tmpnode->balance < -1) { + /* left subtree too tall: right rotation needed */ + + if (tmpnode->childs[AVL_LEFT]->balance < 0) { + avl_rotate_right(&tmpnode); + + /* simple balance adjustments */ + + tmpnode->balance = 0; + tmpnode->childs[AVL_RIGHT]->balance = 0; + + } else { + avl_rotate_left(&tmpnode->childs[AVL_LEFT]); + avl_rotate_right(&tmpnode); + avl_adjust_balance(tmpnode); + } + + } else if (tmpnode->balance > 1) { + /* right subtree too tall: left rotation needed */ + + if (tmpnode->childs[AVL_RIGHT]->balance > 0) { + avl_rotate_left(&tmpnode); + + /* simple balance adjustments */ + + tmpnode->balance = 0; + tmpnode->childs[AVL_LEFT]->balance = 0; + + } else { + avl_rotate_right(&tmpnode->childs[AVL_RIGHT]); + avl_rotate_left(&tmpnode); + avl_adjust_balance(tmpnode); + } + + } else { + insert = 1; + } + } + + /* set back node */ + + *node = tmpnode; + + /* insertion was ok */ + + return insert; } -/* Frees |block|. */ -void -avl_free (struct libavl_allocator *allocator, void *block) + +/* avl_insert ****************************************************************** + + Inserts a AVL node into a AVL tree. + +*******************************************************************************/ + +bool avl_insert(avl_tree *tree, void *data) { - assert (allocator != NULL && block != NULL); - free (block); + assert(tree); + assert(data); + + LOCK_MONITOR_ENTER(tree->lock); + + /* if we don't have a root node, create one */ + + if (tree->root == NULL) { + tree->root = avl_newnode(data); + + } else { + avl_insert_intern(tree, &tree->root, data); + } + + /* increase entries count */ + + tree->entries++; + +#if 0 + printf("tree=%p entries=%d\n", tree, tree->entries); + + printf("-------------------\n"); + avl_dump(tree->root, 0); + printf("-------------------\n"); +#endif + + LOCK_MONITOR_EXIT(tree->lock); + + /* insertion was ok */ + + return true; } -/* Default memory allocator that uses |malloc()| and |free()|. */ -struct libavl_allocator avl_allocator_default = - { - avl_malloc, - avl_free - }; -#undef NDEBUG -#include +/* avl_find ******************************************************************** + + Find a given data structure in the AVL tree, with the comparision + function of the tree. + +*******************************************************************************/ -/* Asserts that |avl_insert()| succeeds at inserting |item| into |table|. */ -void -(avl_assert_insert) (struct avl_table *table, void *item) +void *avl_find(avl_tree *tree, void *data) { - void **p = avl_probe (table, item); - assert (p != NULL && *p == item); + avl_node *node; + s4 res; + + assert(tree); + assert(data); + + LOCK_MONITOR_ENTER(tree->lock); + + /* search the tree for the given node */ + + for (node = tree->root; node != NULL; ) { + /* compare the current node */ + + res = tree->comparator(data, node->data); + + /* was the entry found? return it */ + + if (res == 0) { + LOCK_MONITOR_EXIT(tree->lock); + + return node->data; + } + + /* goto left or right child */ + + node = node->childs[(res < 0) ? AVL_LEFT : AVL_RIGHT]; + } + + LOCK_MONITOR_EXIT(tree->lock); + + /* entry was not found, returning NULL */ + + return NULL; } -/* Asserts that |avl_delete()| really removes |item| from |table|, - and returns the removed item. */ -void * -(avl_assert_delete) (struct avl_table *table, void *item) + +/* avl_dump ******************************************************************** + + Dumps the AVL tree starting with node. + +*******************************************************************************/ + +#if !defined(NDEBUG) +void avl_dump(avl_node* node, s4 indent) { - void *p = avl_delete (table, item); - assert (p != NULL); - return p; -} + s4 tmp; + + tmp = indent; + + if (node == NULL) + return; + if (node->childs[AVL_RIGHT]) + avl_dump(node->childs[AVL_RIGHT], tmp + 1); + + while(indent--) + printf(" "); + + printf("%p (%d)\n", node->data, node->balance); + + if (node->childs[AVL_LEFT]) + avl_dump(node->childs[AVL_LEFT], tmp + 1); +} +#endif + + +/* + * These are local overrides for various environment variables in Emacs. + * Please do not remove this and leave it at the end of the file, where + * Emacs will automagically detect them. + * --------------------------------------------------------------------- + * Local variables: + * mode: c + * indent-tabs-mode: t + * c-basic-offset: 4 + * tab-width: 4 + * End: + */