source: vis_dev/glu-2.3/src/avl/avl.c @ 86

Last change on this file since 86 was 13, checked in by cecile, 13 years ago

library glu 2.3

File size: 11.9 KB
Line 
1/*
2 * $Id: avl.c,v 1.11 2005/04/30 03:03:05 fabio Exp $
3 *
4 */
5/* LINTLIBRARY */
6
7
8#include <stdio.h>
9
10#ifndef PACKAGE
11#include "util.h"
12#endif
13
14#include "avl.h"
15
16#ifdef PACKAGE
17extern char *malloc();
18#ifdef ultrix
19extern void free();
20#endif
21
22#define MAX(a,b)        ((a) > (b) ? (a) : (b))
23
24#define NIL(type)               \
25    ((type *) 0)
26#define ALLOC(type, num)        \
27    ((type *) malloc(sizeof(type) * (num)))
28#define REALLOC(type, obj, num) \
29    ((type *) realloc((char *) obj, sizeof(type) * (num)))
30#define FREE(obj)               \
31    free((char *) (obj))
32#endif
33
34
35#define HEIGHT(node) (node == NIL(avl_node) ? -1 : (node)->height)
36#define BALANCE(node) (HEIGHT((node)->right) - HEIGHT((node)->left))
37
38#define compute_height(node) {                          \
39    int x=HEIGHT(node->left), y=HEIGHT(node->right);    \
40    (node)->height = MAX(x,y) + 1;                      \
41}
42
43#define COMPARE(key, nodekey, compare)                  \
44    ((compare == avl_numcmp) ?                          \
45        (long) key - (long) nodekey :                   \
46        (*compare)(key, nodekey))
47
48
49#define STACK_SIZE      50
50
51static avl_node *new_node(char *key, char *value);
52static avl_node *find_rightmost(avl_node **node_p);
53static void do_rebalance(avl_node ***stack_nodep, int stack_n); 
54static int rotate_left(avl_node **node_p);
55static int rotate_right(avl_node **node_p);
56static int do_check_tree(avl_node *node, int (*compar)(const void *, const void *), int *error);
57
58avl_tree *
59avl_init_table(int (*compar)(const void *, const void *))
60{
61    avl_tree *tree;
62
63    tree = ALLOC(avl_tree, 1);
64    tree->root = NIL(avl_node);
65    tree->compar = compar;
66    tree->num_entries = 0;
67    return tree;
68}
69
70
71int
72avl_lookup(avl_tree *tree, const void *key, void *value_p)
73{
74    avl_node *node;
75    int (*compare)(const void *, const void *) = tree->compar, diff;
76
77    node = tree->root;
78    while (node != NIL(avl_node)) {
79        diff = COMPARE(key, node->key, compare);
80        if (diff == 0) {
81            /* got a match */
82            if (value_p != NULL) *(char **)value_p = node->value;
83            return 1;
84        }
85        node = (diff < 0) ? node->left : node->right;
86    }
87    return 0;
88}
89
90int
91avl_first(avl_tree *tree, char **key_p, char **value_p)
92{
93    register avl_node *node;
94
95    if (tree->root == 0) {
96        return 0;               /* no entries */
97    } else {
98        /* walk down the tree; stop at leftmost leaf */
99        for(node = tree->root; node->left != 0; node = node->left) {
100        }
101        if (key_p != NIL(char *)) *key_p = node->key;
102        if (value_p != NIL(char *)) *value_p = node->value;
103        return 1;
104    }
105}
106
107int
108avl_last(avl_tree *tree, char **key_p, char **value_p)
109{
110    register avl_node *node;
111
112    if (tree->root == 0) {
113        return 0;               /* no entries */
114    } else {
115        /* walk down the tree; stop at rightmost leaf */
116        for(node = tree->root; node->right != 0; node = node->right) {
117        }
118        if (key_p != NIL(char *)) *key_p = node->key;
119        if (value_p != NIL(char *)) *value_p = node->value;
120        return 1;
121    }
122}
123
124int
125avl_insert(avl_tree *tree, void *key, void *value)
126{
127    avl_node **node_p, *node;
128    int stack_n = 0;
129    int (*compare)(const void *, const void *) = tree->compar;
130    avl_node **stack_nodep[STACK_SIZE];
131    int diff, status;
132
133    node_p = &tree->root;
134
135    /* walk down the tree (saving the path); stop at insertion point */
136    status = 0;
137    while ((node = *node_p) != NIL(avl_node)) {
138        stack_nodep[stack_n++] = node_p;
139        diff = COMPARE(key, node->key, compare);
140        if (diff == 0) status = 1;
141        node_p = (diff < 0) ? &node->left : &node->right;
142    }
143
144    /* insert the item and re-balance the tree */
145    *node_p = new_node((char *)key, (char *)value);
146    do_rebalance(stack_nodep, stack_n);
147    tree->num_entries++;
148    tree->modified = 1;
149    return status;
150}
151
152
153int
154avl_find_or_add(avl_tree *tree, char *key, char ***slot_p)
155{
156    register avl_node **node_p, *node;
157    register int stack_n = 0;
158    register int (*compare)(const void *, const void *) = tree->compar;
159    avl_node **stack_nodep[STACK_SIZE];
160    int diff;
161
162    node_p = &tree->root;
163
164    /* walk down the tree (saving the path); stop at insertion point */
165    while ((node = *node_p) != NIL(avl_node)) {
166        stack_nodep[stack_n++] = node_p;
167        diff = COMPARE(key, node->key, compare);
168        if (diff == 0) {
169            if (slot_p != 0) *slot_p = &node->value;
170            return 1;           /* found */
171        }
172        node_p = (diff < 0) ? &node->left : &node->right;
173    }
174
175    /* insert the item and re-balance the tree */
176    *node_p = new_node(key, NIL(char));
177    if (slot_p != 0) *slot_p = &(*node_p)->value;
178    do_rebalance(stack_nodep, stack_n);
179    tree->num_entries++;
180    tree->modified = 1;
181    return 0;                   /* not already in tree */
182}
183
184int
185avl_delete(avl_tree *tree, void *key_p, void *value_p)
186{
187    avl_node **node_p, *node, *rightmost;
188    int stack_n = 0;
189    char *key = *(char **) key_p;
190    int (*compare)(const void *, const void *) = tree->compar, diff;
191    avl_node **stack_nodep[STACK_SIZE];
192
193    node_p = &tree->root;
194
195    /* Walk down the tree saving the path; return if not found */
196    while ((node = *node_p) != NIL(avl_node)) {
197        diff = COMPARE(key, node->key, compare);
198        if (diff == 0) goto delete_item;
199        stack_nodep[stack_n++] = node_p;
200        node_p = (diff < 0) ? &node->left : &node->right;
201    }
202    return 0;           /* not found */
203
204    /* prepare to delete node and replace it with rightmost of left tree */
205delete_item:
206    *(char **) key_p = node->key;
207    if (value_p != NULL) *(char **)value_p = node->value;
208    if (node->left == NIL(avl_node)) {
209        *node_p = node->right;
210    } else {
211        rightmost = find_rightmost(&node->left);
212        rightmost->left = node->left;
213        rightmost->right = node->right;
214        rightmost->height = -2;         /* mark bogus height for do_rebal */
215        *node_p = rightmost;
216        stack_nodep[stack_n++] = node_p;
217    }
218    FREE(node);
219
220    /* work our way back up, re-balancing the tree */
221    do_rebalance(stack_nodep, stack_n);
222    tree->num_entries--;
223    tree->modified = 1;
224    return 1;
225}
226
227static void 
228avl_record_gen_forward(avl_node *node, avl_generator *gen)
229{
230    if (node != NIL(avl_node)) {
231        avl_record_gen_forward(node->left, gen);
232        gen->nodelist[gen->count++] = node;
233        avl_record_gen_forward(node->right, gen);
234    }
235}
236
237
238static void 
239avl_record_gen_backward(avl_node *node, avl_generator *gen)
240{
241    if (node != NIL(avl_node)) {
242        avl_record_gen_backward(node->right, gen);
243        gen->nodelist[gen->count++] = node;
244        avl_record_gen_backward(node->left, gen);
245    }
246}
247
248
249avl_generator *
250avl_init_gen(avl_tree *tree, int dir)
251{
252    avl_generator *gen;
253
254    /* what a hack */
255    gen = ALLOC(avl_generator, 1);
256    gen->tree = tree;
257    gen->nodelist = ALLOC(avl_node *, avl_count(tree));
258    gen->count = 0;
259    if (dir == AVL_FORWARD) {
260        avl_record_gen_forward(tree->root, gen);
261    } else {
262        avl_record_gen_backward(tree->root, gen);
263    }
264    gen->count = 0;
265
266    /* catch any attempt to modify the tree while we generate */
267    tree->modified = 0;
268    return gen;
269}
270
271
272int
273avl_gen(avl_generator *gen, char **key_p, char **value_p)
274{
275    avl_node *node;
276
277    if (gen->count == gen->tree->num_entries) {
278        return 0;
279    } else {
280        node = gen->nodelist[gen->count++];
281        if (key_p != NIL(char *)) *key_p = node->key;
282        if (value_p != NIL(char *)) *value_p = node->value;
283        return 1;
284    }
285}
286
287
288void
289avl_free_gen(avl_generator *gen)
290{
291    FREE(gen->nodelist);
292    FREE(gen);
293}
294
295
296static avl_node *
297find_rightmost(avl_node **node_p)
298{
299    register avl_node *node;
300    register int stack_n = 0;
301    avl_node **stack_nodep[STACK_SIZE];
302
303    node = *node_p;
304    while (node->right != NIL(avl_node)) {
305        stack_nodep[stack_n++] = node_p;
306        node_p = &node->right;
307        node = *node_p;
308    }
309    *node_p = node->left;
310
311    do_rebalance(stack_nodep, stack_n);
312    return node;
313}
314
315
316static void
317do_rebalance(avl_node ***stack_nodep, int stack_n)
318{
319    register avl_node **node_p, *node;
320    register int hl, hr;
321    int height;
322
323    /* work our way back up, re-balancing the tree */
324    while (--stack_n >= 0) {
325        node_p = stack_nodep[stack_n];
326        node = *node_p;
327        hl = HEIGHT(node->left);                /* watch for NIL */
328        hr = HEIGHT(node->right);               /* watch for NIL */
329        if ((hr - hl) < -1) {
330            rotate_right(node_p);
331        } else if ((hr - hl) > 1) {
332            rotate_left(node_p);
333        } else {
334            height = MAX(hl, hr) + 1;
335            if (height == node->height) break;
336            node->height = height;
337        }
338    }
339}
340
341static int
342rotate_left(avl_node **node_p)
343{
344    register avl_node *old_root = *node_p, *new_root, *new_right;
345
346    if (BALANCE(old_root->right) >= 0) {
347        *node_p = new_root = old_root->right;
348        old_root->right = new_root->left;
349        new_root->left = old_root;
350    } else {
351        new_right = old_root->right;
352        *node_p = new_root = new_right->left;
353        old_root->right = new_root->left;
354        new_right->left = new_root->right;
355        new_root->right = new_right;
356        new_root->left = old_root;
357        compute_height(new_right);
358    }
359    compute_height(old_root);
360    compute_height(new_root);
361
362    return 0;
363}
364
365
366static int
367rotate_right(avl_node **node_p)
368{
369    register avl_node *old_root = *node_p, *new_root, *new_left;
370
371    if (BALANCE(old_root->left) <= 0) {
372        *node_p = new_root = old_root->left;
373        old_root->left = new_root->right;
374        new_root->right = old_root;
375    } else {
376        new_left = old_root->left;
377        *node_p = new_root = new_left->right;
378        old_root->left = new_root->right;
379        new_left->right = new_root->left;
380        new_root->left = new_left;
381        new_root->right = old_root;
382        compute_height(new_left);
383    }
384    compute_height(old_root);
385    compute_height(new_root);
386
387    return 0;
388}
389
390static void 
391avl_walk_forward(avl_node *node, void (*func)(const void *, const void *))
392{
393    if (node != NIL(avl_node)) {
394        avl_walk_forward(node->left, func);
395        (*func)(node->key, node->value);
396        avl_walk_forward(node->right, func);
397    }
398}
399
400
401static void 
402avl_walk_backward(avl_node *node, void (*func)(const void *, const void *))
403{
404    if (node != NIL(avl_node)) {
405        avl_walk_backward(node->right, func);
406        (*func)(node->key, node->value);
407        avl_walk_backward(node->left, func);
408    }
409}
410
411
412void
413avl_foreach(
414  avl_tree *tree,
415  void (*func)(const void *, const void *),
416  int direction)
417{
418    if (direction == AVL_FORWARD) {
419        avl_walk_forward(tree->root, func);
420    } else {
421        avl_walk_backward(tree->root, func);
422    }
423}
424
425
426static void
427free_entry(
428  avl_node *node,
429  void (*key_free)(char *),
430  void (*value_free)(char *))
431{
432    if (node != NIL(avl_node)) {
433        free_entry(node->left, key_free, value_free);
434        free_entry(node->right, key_free, value_free);
435        if (key_free != 0) (*key_free)(node->key);
436        if (value_free != 0) (*value_free)(node->value);
437        FREE(node);
438    }
439}
440   
441
442void 
443avl_free_table(
444  avl_tree *tree,
445  void (*key_free)(char *),
446  void (*value_free)(char *))
447{
448    free_entry(tree->root, key_free, value_free);
449    FREE(tree);
450}
451
452
453int 
454avl_count(avl_tree *tree)
455{
456    return tree->num_entries;
457}
458
459
460static avl_node *
461new_node(char *key, char *value)
462{
463    register avl_node *newn;
464
465    newn = ALLOC(avl_node, 1);
466    newn->key = key;
467    newn->value = value;
468    newn->height = 0;
469    newn->left = newn->right = NIL(avl_node);
470    return newn;
471}
472
473
474int 
475avl_numcmp(const void *x, const void *y)
476{
477    return (long) x - (long) y;
478}
479
480int
481avl_check_tree(avl_tree *tree)
482{
483    int error = 0;
484    (void) do_check_tree(tree->root, tree->compar, &error);
485    return error;
486}
487
488
489static int
490do_check_tree(
491  avl_node *node,
492  int (*compar)(const void *, const void *),
493  int *error)
494{
495    int l_height, r_height, comp_height, bal;
496   
497    if (node == NIL(avl_node)) {
498        return -1;
499    }
500
501    r_height = do_check_tree(node->right, compar, error);
502    l_height = do_check_tree(node->left, compar, error);
503
504    comp_height = MAX(l_height, r_height) + 1;
505    bal = r_height - l_height;
506   
507    if (comp_height != node->height) {
508        (void) printf("Bad height for 0x%p: computed=%d stored=%d\n",
509            (void *) node, comp_height, node->height);
510        ++*error;
511    }
512
513    if (bal > 1 || bal < -1) {
514        (void) printf("Out of balance at node 0x%p, balance = %d\n", 
515            (void *) node, bal);
516        ++*error;
517    }
518
519    if (node->left != NIL(avl_node) && 
520                    (*compar)(node->left->key, node->key) > 0) {
521        (void) printf("Bad ordering between 0x%p and 0x%p", 
522            (void *) node, (void *) node->left);
523        ++*error;
524    }
525   
526    if (node->right != NIL(avl_node) && 
527                    (*compar)(node->key, node->right->key) > 0) {
528        (void) printf("Bad ordering between 0x%p and 0x%p", 
529            (void *) node, (void *) node->right);
530        ++*error;
531    }
532
533    return comp_height;
534}
Note: See TracBrowser for help on using the repository browser.