src/avl/avl.c File Reference

#include <stdio.h>
#include "util.h"
#include "avl.h"
Include dependency graph for avl.c:

Go to the source code of this file.

Defines

#define HEIGHT(node)   (node == NIL(avl_node) ? -1 : (node)->height)
#define BALANCE(node)   (HEIGHT((node)->right) - HEIGHT((node)->left))
#define compute_height(node)
#define COMPARE(key, nodekey, compare)
#define STACK_SIZE   50

Functions

static avl_node * new_node (char *key, char *value)
static avl_node * find_rightmost (avl_node **node_p)
static void do_rebalance (avl_node ***stack_nodep, int stack_n)
static int rotate_left (avl_node **node_p)
static int rotate_right (avl_node **node_p)
static int do_check_tree (avl_node *node, int(*compar)(const void *, const void *), int *error)
avl_tree * avl_init_table (int(*compar)(const void *, const void *))
int avl_lookup (avl_tree *tree, const void *key, void *value_p)
int avl_first (avl_tree *tree, char **key_p, char **value_p)
int avl_last (avl_tree *tree, char **key_p, char **value_p)
int avl_insert (avl_tree *tree, void *key, void *value)
int avl_find_or_add (avl_tree *tree, char *key, char ***slot_p)
int avl_delete (avl_tree *tree, void *key_p, void *value_p)
static void avl_record_gen_forward (avl_node *node, avl_generator *gen)
static void avl_record_gen_backward (avl_node *node, avl_generator *gen)
avl_generator * avl_init_gen (avl_tree *tree, int dir)
int avl_gen (avl_generator *gen, char **key_p, char **value_p)
void avl_free_gen (avl_generator *gen)
static void avl_walk_forward (avl_node *node, void(*func)(const void *, const void *))
static void avl_walk_backward (avl_node *node, void(*func)(const void *, const void *))
void avl_foreach (avl_tree *tree, void(*func)(const void *, const void *), int direction)
static void free_entry (avl_node *node, void(*key_free)(char *), void(*value_free)(char *))
void avl_free_table (avl_tree *tree, void(*key_free)(char *), void(*value_free)(char *))
int avl_count (avl_tree *tree)
int avl_numcmp (const void *x, const void *y)
int avl_check_tree (avl_tree *tree)

Define Documentation

#define BALANCE ( node   )     (HEIGHT((node)->right) - HEIGHT((node)->left))

Definition at line 36 of file avl.c.

#define COMPARE ( key,
nodekey,
compare   ) 
Value:
((compare == avl_numcmp) ?                              \
        (long) key - (long) nodekey :                   \
        (*compare)(key, nodekey))

Definition at line 43 of file avl.c.

#define compute_height ( node   ) 
Value:
{                               \
    int x=HEIGHT(node->left), y=HEIGHT(node->right);    \
    (node)->height = MAX(x,y) + 1;                      \
}

Definition at line 38 of file avl.c.

#define HEIGHT ( node   )     (node == NIL(avl_node) ? -1 : (node)->height)

Definition at line 35 of file avl.c.

#define STACK_SIZE   50

Definition at line 49 of file avl.c.

Function Documentation

int avl_check_tree ( avl_tree *  tree  ) 

Definition at line 481 of file avl.c.

00482 {
00483     int error = 0;
00484     (void) do_check_tree(tree->root, tree->compar, &error);
00485     return error;
00486 }

int avl_count ( avl_tree *  tree  ) 

Definition at line 454 of file avl.c.

00455 {
00456     return tree->num_entries;
00457 }

int avl_delete ( avl_tree *  tree,
void *  key_p,
void *  value_p 
)

Definition at line 185 of file avl.c.

00186 {
00187     avl_node **node_p, *node, *rightmost;
00188     int stack_n = 0;
00189     char *key = *(char **) key_p;
00190     int (*compare)(const void *, const void *) = tree->compar, diff;
00191     avl_node **stack_nodep[STACK_SIZE];
00192 
00193     node_p = &tree->root;
00194 
00195     /* Walk down the tree saving the path; return if not found */
00196     while ((node = *node_p) != NIL(avl_node)) {
00197         diff = COMPARE(key, node->key, compare);
00198         if (diff == 0) goto delete_item;
00199         stack_nodep[stack_n++] = node_p;
00200         node_p = (diff < 0) ? &node->left : &node->right;
00201     }
00202     return 0;           /* not found */
00203 
00204     /* prepare to delete node and replace it with rightmost of left tree */
00205 delete_item:
00206     *(char **) key_p = node->key;
00207     if (value_p != NULL) *(char **)value_p = node->value;
00208     if (node->left == NIL(avl_node)) {
00209         *node_p = node->right;
00210     } else {
00211         rightmost = find_rightmost(&node->left);
00212         rightmost->left = node->left;
00213         rightmost->right = node->right;
00214         rightmost->height = -2;         /* mark bogus height for do_rebal */
00215         *node_p = rightmost;
00216         stack_nodep[stack_n++] = node_p;
00217     }
00218     FREE(node);
00219 
00220     /* work our way back up, re-balancing the tree */
00221     do_rebalance(stack_nodep, stack_n);
00222     tree->num_entries--;
00223     tree->modified = 1;
00224     return 1;
00225 }

int avl_find_or_add ( avl_tree *  tree,
char *  key,
char ***  slot_p 
)

Definition at line 154 of file avl.c.

00155 {
00156     register avl_node **node_p, *node;
00157     register int stack_n = 0;
00158     register int (*compare)(const void *, const void *) = tree->compar;
00159     avl_node **stack_nodep[STACK_SIZE];
00160     int diff;
00161 
00162     node_p = &tree->root;
00163 
00164     /* walk down the tree (saving the path); stop at insertion point */
00165     while ((node = *node_p) != NIL(avl_node)) {
00166         stack_nodep[stack_n++] = node_p;
00167         diff = COMPARE(key, node->key, compare);
00168         if (diff == 0) {
00169             if (slot_p != 0) *slot_p = &node->value;
00170             return 1;           /* found */
00171         }
00172         node_p = (diff < 0) ? &node->left : &node->right;
00173     }
00174 
00175     /* insert the item and re-balance the tree */
00176     *node_p = new_node(key, NIL(char));
00177     if (slot_p != 0) *slot_p = &(*node_p)->value;
00178     do_rebalance(stack_nodep, stack_n);
00179     tree->num_entries++;
00180     tree->modified = 1;
00181     return 0;                   /* not already in tree */
00182 }

int avl_first ( avl_tree *  tree,
char **  key_p,
char **  value_p 
)

Definition at line 91 of file avl.c.

00092 {
00093     register avl_node *node;
00094 
00095     if (tree->root == 0) {
00096         return 0;               /* no entries */
00097     } else {
00098         /* walk down the tree; stop at leftmost leaf */
00099         for(node = tree->root; node->left != 0; node = node->left) {
00100         }
00101         if (key_p != NIL(char *)) *key_p = node->key;
00102         if (value_p != NIL(char *)) *value_p = node->value;
00103         return 1;
00104     }
00105 }

void avl_foreach ( avl_tree *  tree,
void(*)(const void *, const void *)  func,
int  direction 
)

Definition at line 413 of file avl.c.

00417 {
00418     if (direction == AVL_FORWARD) {
00419         avl_walk_forward(tree->root, func);
00420     } else {
00421         avl_walk_backward(tree->root, func);
00422     }
00423 }

void avl_free_gen ( avl_generator *  gen  ) 

Definition at line 289 of file avl.c.

00290 {
00291     FREE(gen->nodelist);
00292     FREE(gen);
00293 }

void avl_free_table ( avl_tree *  tree,
void(*)(char *)  key_free,
void(*)(char *)  value_free 
)

Definition at line 443 of file avl.c.

00447 {
00448     free_entry(tree->root, key_free, value_free);
00449     FREE(tree);
00450 }

int avl_gen ( avl_generator *  gen,
char **  key_p,
char **  value_p 
)

Definition at line 273 of file avl.c.

00274 {
00275     avl_node *node;
00276 
00277     if (gen->count == gen->tree->num_entries) {
00278         return 0;
00279     } else {
00280         node = gen->nodelist[gen->count++];
00281         if (key_p != NIL(char *)) *key_p = node->key;
00282         if (value_p != NIL(char *)) *value_p = node->value;
00283         return 1;
00284     }
00285 }

avl_generator* avl_init_gen ( avl_tree *  tree,
int  dir 
)

Definition at line 250 of file avl.c.

00251 {
00252     avl_generator *gen;
00253 
00254     /* what a hack */
00255     gen = ALLOC(avl_generator, 1);
00256     gen->tree = tree;
00257     gen->nodelist = ALLOC(avl_node *, avl_count(tree));
00258     gen->count = 0;
00259     if (dir == AVL_FORWARD) {
00260         avl_record_gen_forward(tree->root, gen);
00261     } else {
00262         avl_record_gen_backward(tree->root, gen);
00263     }
00264     gen->count = 0;
00265 
00266     /* catch any attempt to modify the tree while we generate */
00267     tree->modified = 0;
00268     return gen;
00269 }

avl_tree* avl_init_table ( int(*)(const void *, const void *)  compar  ) 

Definition at line 59 of file avl.c.

00060 {
00061     avl_tree *tree;
00062 
00063     tree = ALLOC(avl_tree, 1);
00064     tree->root = NIL(avl_node);
00065     tree->compar = compar;
00066     tree->num_entries = 0;
00067     return tree;
00068 }

int avl_insert ( avl_tree *  tree,
void *  key,
void *  value 
)

Definition at line 125 of file avl.c.

00126 {
00127     avl_node **node_p, *node;
00128     int stack_n = 0;
00129     int (*compare)(const void *, const void *) = tree->compar;
00130     avl_node **stack_nodep[STACK_SIZE];
00131     int diff, status;
00132 
00133     node_p = &tree->root;
00134 
00135     /* walk down the tree (saving the path); stop at insertion point */
00136     status = 0;
00137     while ((node = *node_p) != NIL(avl_node)) {
00138         stack_nodep[stack_n++] = node_p;
00139         diff = COMPARE(key, node->key, compare);
00140         if (diff == 0) status = 1;
00141         node_p = (diff < 0) ? &node->left : &node->right;
00142     }
00143 
00144     /* insert the item and re-balance the tree */
00145     *node_p = new_node((char *)key, (char *)value);
00146     do_rebalance(stack_nodep, stack_n);
00147     tree->num_entries++;
00148     tree->modified = 1;
00149     return status;
00150 }

int avl_last ( avl_tree *  tree,
char **  key_p,
char **  value_p 
)

Definition at line 108 of file avl.c.

00109 {
00110     register avl_node *node;
00111 
00112     if (tree->root == 0) {
00113         return 0;               /* no entries */
00114     } else {
00115         /* walk down the tree; stop at rightmost leaf */
00116         for(node = tree->root; node->right != 0; node = node->right) {
00117         }
00118         if (key_p != NIL(char *)) *key_p = node->key;
00119         if (value_p != NIL(char *)) *value_p = node->value;
00120         return 1;
00121     }
00122 }

int avl_lookup ( avl_tree *  tree,
const void *  key,
void *  value_p 
)

Definition at line 72 of file avl.c.

00073 {
00074     avl_node *node;
00075     int (*compare)(const void *, const void *) = tree->compar, diff;
00076 
00077     node = tree->root;
00078     while (node != NIL(avl_node)) {
00079         diff = COMPARE(key, node->key, compare);
00080         if (diff == 0) {
00081             /* got a match */
00082             if (value_p != NULL) *(char **)value_p = node->value;
00083             return 1;
00084         }
00085         node = (diff < 0) ? node->left : node->right;
00086     }
00087     return 0;
00088 }

int avl_numcmp ( const void *  x,
const void *  y 
)

Definition at line 475 of file avl.c.

00476 {
00477     return (long) x - (long) y;
00478 }

static void avl_record_gen_backward ( avl_node *  node,
avl_generator *  gen 
) [static]

Definition at line 239 of file avl.c.

00240 {
00241     if (node != NIL(avl_node)) {
00242         avl_record_gen_backward(node->right, gen);
00243         gen->nodelist[gen->count++] = node;
00244         avl_record_gen_backward(node->left, gen);
00245     }
00246 }

static void avl_record_gen_forward ( avl_node *  node,
avl_generator *  gen 
) [static]

Definition at line 228 of file avl.c.

00229 {
00230     if (node != NIL(avl_node)) {
00231         avl_record_gen_forward(node->left, gen);
00232         gen->nodelist[gen->count++] = node;
00233         avl_record_gen_forward(node->right, gen);
00234     }
00235 }

static void avl_walk_backward ( avl_node *  node,
void(*)(const void *, const void *)  func 
) [static]

Definition at line 402 of file avl.c.

00403 {
00404     if (node != NIL(avl_node)) {
00405         avl_walk_backward(node->right, func);
00406         (*func)(node->key, node->value);
00407         avl_walk_backward(node->left, func);
00408     }
00409 }

static void avl_walk_forward ( avl_node *  node,
void(*)(const void *, const void *)  func 
) [static]

Definition at line 391 of file avl.c.

00392 {
00393     if (node != NIL(avl_node)) {
00394         avl_walk_forward(node->left, func);
00395         (*func)(node->key, node->value);
00396         avl_walk_forward(node->right, func);
00397     }
00398 }

static int do_check_tree ( avl_node *  node,
int(*)(const void *, const void *)  compar,
int *  error 
) [static]

Definition at line 490 of file avl.c.

00494 {
00495     int l_height, r_height, comp_height, bal;
00496     
00497     if (node == NIL(avl_node)) {
00498         return -1;
00499     }
00500 
00501     r_height = do_check_tree(node->right, compar, error);
00502     l_height = do_check_tree(node->left, compar, error);
00503 
00504     comp_height = MAX(l_height, r_height) + 1;
00505     bal = r_height - l_height;
00506     
00507     if (comp_height != node->height) {
00508         (void) printf("Bad height for 0x%p: computed=%d stored=%d\n",
00509             (void *) node, comp_height, node->height);
00510         ++*error;
00511     }
00512 
00513     if (bal > 1 || bal < -1) {
00514         (void) printf("Out of balance at node 0x%p, balance = %d\n", 
00515             (void *) node, bal);
00516         ++*error;
00517     }
00518 
00519     if (node->left != NIL(avl_node) && 
00520                     (*compar)(node->left->key, node->key) > 0) {
00521         (void) printf("Bad ordering between 0x%p and 0x%p", 
00522             (void *) node, (void *) node->left);
00523         ++*error;
00524     }
00525     
00526     if (node->right != NIL(avl_node) && 
00527                     (*compar)(node->key, node->right->key) > 0) {
00528         (void) printf("Bad ordering between 0x%p and 0x%p", 
00529             (void *) node, (void *) node->right);
00530         ++*error;
00531     }
00532 
00533     return comp_height;
00534 }

static void do_rebalance ( avl_node ***  stack_nodep,
int  stack_n 
) [static]

Definition at line 317 of file avl.c.

00318 {
00319     register avl_node **node_p, *node;
00320     register int hl, hr;
00321     int height;
00322 
00323     /* work our way back up, re-balancing the tree */
00324     while (--stack_n >= 0) {
00325         node_p = stack_nodep[stack_n];
00326         node = *node_p;
00327         hl = HEIGHT(node->left);                /* watch for NIL */
00328         hr = HEIGHT(node->right);               /* watch for NIL */
00329         if ((hr - hl) < -1) {
00330             rotate_right(node_p);
00331         } else if ((hr - hl) > 1) {
00332             rotate_left(node_p);
00333         } else {
00334             height = MAX(hl, hr) + 1;
00335             if (height == node->height) break;
00336             node->height = height;
00337         }
00338     }
00339 }

static avl_node * find_rightmost ( avl_node **  node_p  )  [static]

Definition at line 297 of file avl.c.

00298 {
00299     register avl_node *node;
00300     register int stack_n = 0;
00301     avl_node **stack_nodep[STACK_SIZE];
00302 
00303     node = *node_p;
00304     while (node->right != NIL(avl_node)) {
00305         stack_nodep[stack_n++] = node_p;
00306         node_p = &node->right;
00307         node = *node_p;
00308     }
00309     *node_p = node->left;
00310 
00311     do_rebalance(stack_nodep, stack_n);
00312     return node;
00313 }

static void free_entry ( avl_node *  node,
void(*)(char *)  key_free,
void(*)(char *)  value_free 
) [static]

Definition at line 427 of file avl.c.

00431 {
00432     if (node != NIL(avl_node)) {
00433         free_entry(node->left, key_free, value_free);
00434         free_entry(node->right, key_free, value_free);
00435         if (key_free != 0) (*key_free)(node->key);
00436         if (value_free != 0) (*value_free)(node->value);
00437         FREE(node);
00438     }
00439 }

static avl_node * new_node ( char *  key,
char *  value 
) [static]

Definition at line 461 of file avl.c.

00462 {
00463     register avl_node *newn;
00464 
00465     newn = ALLOC(avl_node, 1);
00466     newn->key = key;
00467     newn->value = value;
00468     newn->height = 0;
00469     newn->left = newn->right = NIL(avl_node);
00470     return newn;
00471 }

static int rotate_left ( avl_node **  node_p  )  [static]

Definition at line 342 of file avl.c.

00343 {
00344     register avl_node *old_root = *node_p, *new_root, *new_right;
00345 
00346     if (BALANCE(old_root->right) >= 0) {
00347         *node_p = new_root = old_root->right;
00348         old_root->right = new_root->left;
00349         new_root->left = old_root;
00350     } else {
00351         new_right = old_root->right;
00352         *node_p = new_root = new_right->left;
00353         old_root->right = new_root->left;
00354         new_right->left = new_root->right;
00355         new_root->right = new_right;
00356         new_root->left = old_root;
00357         compute_height(new_right);
00358     }
00359     compute_height(old_root);
00360     compute_height(new_root);
00361 
00362     return 0;
00363 }

static int rotate_right ( avl_node **  node_p  )  [static]

Definition at line 367 of file avl.c.

00368 {
00369     register avl_node *old_root = *node_p, *new_root, *new_left;
00370 
00371     if (BALANCE(old_root->left) <= 0) {
00372         *node_p = new_root = old_root->left;
00373         old_root->left = new_root->right;
00374         new_root->right = old_root;
00375     } else {
00376         new_left = old_root->left;
00377         *node_p = new_root = new_left->right;
00378         old_root->left = new_root->right;
00379         new_left->right = new_root->left;
00380         new_root->left = new_left;
00381         new_root->right = old_root;
00382         compute_height(new_left);
00383     }
00384     compute_height(old_root);
00385     compute_height(new_root);
00386 
00387     return 0;
00388 }

Generated on Tue Jan 12 13:57:08 2010 for glu-2.2 by  doxygen 1.6.1