/[dynamips]/trunk/rbtree.c
This is repository of my old source code which isn't updated any more. Go to git.rot13.org for current projects!
ViewVC logotype

Annotation of /trunk/rbtree.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3 - (hide annotations)
Sat Oct 6 16:05:34 2007 UTC (16 years, 5 months ago) by dpavlin
Original Path: upstream/dynamips-0.2.6-RC2/rbtree.c
File MIME type: text/plain
File size: 11687 byte(s)
dynamips-0.2.6-RC2

1 dpavlin 1 /*
2     * Dynamips
3     * Copyright (c) 2005 Christophe Fillot.
4     * E-mail: cf@utc.fr
5     *
6     * rbtree.c: Red/Black Trees.
7     */
8    
9     static const char rcsid[] = "$Id$";
10    
11     #include <stdio.h>
12     #include <stdlib.h>
13     #include <string.h>
14     #include <stdarg.h>
15     #include <unistd.h>
16     #include <errno.h>
17     #include <signal.h>
18     #include <fcntl.h>
19     #include <ctype.h>
20    
21     #include "utils.h"
22     #include "rbtree.h"
23    
24     #define rbtree_nil(tree) (&(tree)->nil)
25     #define NIL(tree,x) (((x) == rbtree_nil(tree)) || !x)
26    
27     /* Allocate memory for a new node */
28     static rbtree_node *rbtree_node_alloc(rbtree_tree *tree,void *key,void *value)
29     {
30     rbtree_node *node;
31    
32     if (!(node = mp_alloc_n0(&tree->mp,sizeof(*node))))
33     return NULL;
34    
35     node->key = key;
36     node->value = value;
37     node->left = rbtree_nil(tree);
38     node->right = rbtree_nil(tree);
39     node->parent = rbtree_nil(tree);
40     node->color = -1;
41     return node;
42     }
43    
44     /* Free memory used by a node */
45     static inline void rbtree_node_free(rbtree_tree *tree,rbtree_node *node)
46     {
47     mp_free(node);
48     }
49    
50     /* Returns the node which represents the minimum value */
51     static inline rbtree_node *rbtree_min(rbtree_tree *tree,rbtree_node *x)
52     {
53     while(!NIL(tree,x->left))
54     x = x->left;
55    
56     return(x);
57     }
58    
59     /* Returns the node which represents the maximum value */
60     static inline rbtree_node *rbtree_max(rbtree_tree *tree,rbtree_node *x)
61     {
62     while(!NIL(tree,x->right))
63     x = x->right;
64    
65     return(x);
66     }
67    
68     /* Returns the successor of a node */
69     static inline rbtree_node *rbtree_successor(rbtree_tree *tree,rbtree_node *x)
70     {
71     rbtree_node *y;
72    
73     if (!NIL(tree,x->right))
74     return(rbtree_min(tree,x->right));
75    
76     y = x->parent;
77     while(!NIL(tree,y) && (x == y->right)) {
78     x = y;
79     y = y->parent;
80     }
81    
82     return(y);
83     }
84    
85     /* Left rotation */
86     static inline void rbtree_left_rotate(rbtree_tree *tree,rbtree_node *x)
87     {
88     rbtree_node *y;
89    
90     y = x->right;
91     x->right = y->left;
92    
93     if (!NIL(tree,x->right))
94     x->right->parent = x;
95    
96     y->parent = x->parent;
97    
98     if (NIL(tree,x->parent))
99     tree->root = y;
100     else {
101     if (x == x->parent->left)
102     x->parent->left = y;
103     else
104     x->parent->right = y;
105     }
106    
107     y->left = x;
108     x->parent = y;
109     }
110    
111     /* Right rotation */
112     static inline void rbtree_right_rotate(rbtree_tree *tree,rbtree_node *y)
113     {
114     rbtree_node *x;
115    
116     x = y->left;
117     y->left = x->right;
118    
119     if (!NIL(tree,y->left))
120     y->left->parent = y;
121    
122     x->parent = y->parent;
123    
124     if (NIL(tree,y->parent))
125     tree->root = x;
126     else {
127     if (y->parent->left == y)
128     y->parent->left = x;
129     else
130     y->parent->right = x;
131     }
132    
133     x->right = y;
134     y->parent = x;
135     }
136    
137     /* insert a new node */
138     static rbtree_node *rbtree_insert_new(rbtree_tree *tree,void *key,void *value,
139     int *exists)
140     {
141     rbtree_node *parent,*node,*new_node,**nodeplace;
142     int comp;
143    
144     nodeplace = &tree->root;
145     parent = NULL;
146     *exists = FALSE;
147    
148     for(;;)
149     {
150     node = *nodeplace;
151    
152     if (NIL(tree,node))
153     break;
154    
155     comp = tree->key_cmp(key,node->key,tree->opt_data);
156    
157     if (!comp) {
158     *exists = TRUE;
159     node->value = value;
160     return node;
161     }
162    
163     parent = node;
164     nodeplace = (comp > 0) ? &node->right : &node->left;
165     }
166    
167     /* create a new node */
168     if (!(new_node = rbtree_node_alloc(tree,key,value)))
169     return NULL;
170    
171     *nodeplace = new_node;
172     new_node->parent = parent;
173    
174     tree->node_count++;
175     return new_node;
176     }
177    
178     /* Insert a node in a Red/Black Tree */
179     int rbtree_insert(rbtree_tree *tree,void *key,void *value)
180     {
181     rbtree_node *x,*y;
182     int exists;
183    
184     /* insert a new node (if necessary) */
185     x = rbtree_insert_new(tree,key,value,&exists);
186    
187     if (exists) return(0);
188     if (!x) return(-1);
189    
190     tree->node_count++;
191    
192     /* maintains red-black properties */
193     x->color = RBTREE_RED;
194    
195     while((x != tree->root) && (x->parent->color == RBTREE_RED))
196     {
197     if (x->parent == x->parent->parent->left)
198     {
199     y = x->parent->parent->right;
200    
201     if (y->color == RBTREE_RED)
202     {
203     x->parent->color = RBTREE_BLACK;
204     y->color = RBTREE_BLACK;
205     x->parent->parent->color = RBTREE_RED;
206     x = x->parent->parent;
207     }
208     else
209     {
210     if (x == x->parent->right) {
211     x = x->parent;
212     rbtree_left_rotate(tree,x);
213     }
214    
215     x->parent->color = RBTREE_BLACK;
216     x->parent->parent->color = RBTREE_RED;
217     rbtree_right_rotate(tree,x->parent->parent);
218     }
219     }
220     else
221     {
222     y = x->parent->parent->left;
223    
224     if (y->color == RBTREE_RED)
225     {
226     x->parent->color = RBTREE_BLACK;
227     y->color = RBTREE_BLACK;
228     x->parent->parent->color = RBTREE_RED;
229     x = x->parent->parent;
230     }
231     else
232     {
233     if (x == x->parent->left) {
234     x = x->parent;
235     rbtree_right_rotate(tree,x);
236     }
237    
238     x->parent->color = RBTREE_BLACK;
239     x->parent->parent->color = RBTREE_RED;
240     rbtree_left_rotate(tree,x->parent->parent);
241     }
242     }
243     }
244    
245     tree->root->color = RBTREE_BLACK;
246     return(0);
247     }
248    
249     /* Lookup for a node corresponding to "key" */
250     static inline rbtree_node *rbtree_lookup_node(rbtree_tree *tree,void *key)
251     {
252     rbtree_node *node;
253     int comp;
254    
255     node = tree->root;
256    
257     for (;;) {
258     if (NIL(tree,node)) /* key not found */
259     break;
260    
261     if (!(comp = tree->key_cmp(key,node->key,tree->opt_data)))
262     break; /* exact match */
263    
264     node = (comp > 0) ? node->right : node->left;
265     }
266    
267     return(node);
268     }
269    
270     /*
271     * Lookup for a node corresponding to "key". If node does not exist,
272     * function returns null pointer.
273     */
274     void *rbtree_lookup(rbtree_tree *tree,void *key)
275     {
276     return(rbtree_lookup_node(tree,key)->value);
277     }
278    
279     /* Restore Red/black tree properties after a removal */
280     static void rbtree_removal_fixup(rbtree_tree *tree,rbtree_node *x)
281     {
282     rbtree_node *w;
283    
284     while((x != tree->root) && (x->color == RBTREE_BLACK))
285     {
286     if (x == x->parent->left)
287     {
288     w = x->parent->right;
289    
290     if (w->color == RBTREE_RED) {
291     w->color = RBTREE_BLACK;
292     x->parent->color = RBTREE_RED;
293     rbtree_left_rotate(tree,x->parent);
294     w = x->parent->right;
295     }
296    
297     if ((w->left->color == RBTREE_BLACK) &&
298     (w->right->color == RBTREE_BLACK))
299     {
300     w->color = RBTREE_RED;
301     x = x->parent;
302     }
303     else
304     {
305     if (w->right->color == RBTREE_BLACK) {
306     w->left->color = RBTREE_BLACK;
307     w->color = RBTREE_RED;
308     rbtree_right_rotate(tree,w);
309     w = x->parent->right;
310     }
311    
312     w->color = x->parent->color;
313     x->parent->color = RBTREE_BLACK;
314     w->right->color = RBTREE_BLACK;
315     rbtree_left_rotate(tree,x->parent);
316     x = tree->root;
317     }
318     }
319     else
320     {
321     w = x->parent->left;
322    
323     if (w->color == RBTREE_RED) {
324     w->color = RBTREE_BLACK;
325     x->parent->color = RBTREE_RED;
326     rbtree_right_rotate(tree,x->parent);
327     w = x->parent->left;
328     }
329    
330     if ((w->right->color == RBTREE_BLACK) &&
331     (w->left->color == RBTREE_BLACK))
332     {
333     w->color = RBTREE_RED;
334     x = x->parent;
335     }
336     else
337     {
338     if (w->left->color == RBTREE_BLACK) {
339     w->right->color = RBTREE_BLACK;
340     w->color = RBTREE_RED;
341     rbtree_left_rotate(tree,w);
342     w = x->parent->left;
343     }
344    
345     w->color = x->parent->color;
346     x->parent->color = RBTREE_BLACK;
347     w->left->color = RBTREE_BLACK;
348     rbtree_right_rotate(tree,x->parent);
349     x = tree->root;
350     }
351     }
352     }
353    
354     x->color = RBTREE_BLACK;
355     }
356    
357     /* Removes a node out of a tree */
358     void *rbtree_remove(rbtree_tree *tree,void *key)
359     {
360     rbtree_node *z = rbtree_lookup_node(tree,key);
361     rbtree_node *x,*y;
362     void *value;
363    
364     if (NIL(tree,z))
365     return NULL;
366    
367     value = z->value;
368    
369     if (NIL(tree,z->left) || NIL(tree,z->right))
370     y = z;
371     else
372     y = rbtree_successor(tree,z);
373    
374     if (!NIL(tree,y->left))
375     x = y->left;
376     else
377     x = y->right;
378    
379     x->parent = y->parent;
380    
381     if (NIL(tree,y->parent))
382     tree->root = x;
383     else {
384     if (y == y->parent->left)
385     y->parent->left = x;
386     else
387     y->parent->right = x;
388     }
389    
390     if (y != z) {
391     z->key = y->key;
392     z->value = y->value;
393     }
394    
395     if (y->color == RBTREE_BLACK)
396     rbtree_removal_fixup(tree,x);
397    
398     rbtree_node_free(tree,y);
399     tree->node_count++;
400     return(value);
401     }
402    
403     static void rbtree_foreach_node(rbtree_tree *tree,rbtree_node *node,
404     tree_fforeach user_fn,void *opt)
405     {
406     if (!NIL(tree,node)) {
407     rbtree_foreach_node(tree,node->left,user_fn,opt);
408     user_fn(node->key,node->value,opt);
409     rbtree_foreach_node(tree,node->right,user_fn,opt);
410     }
411     }
412    
413     /* Call the specified function for each node */
414     int rbtree_foreach(rbtree_tree *tree,tree_fforeach user_fn,void *opt)
415     {
416     if (!tree) return(-1);
417    
418     rbtree_foreach_node(tree,tree->root,user_fn,opt);
419     return(0);
420     }
421    
422     /* Returns the maximum height of the right and left sub-trees */
423     static int rbtree_height_node(rbtree_tree *tree,rbtree_node *node)
424     {
425     int lh,rh;
426    
427     lh = (!NIL(tree,node->left)) ? rbtree_height_node(tree,node->left) : 0;
428     rh = (!NIL(tree,node->right)) ? rbtree_height_node(tree,node->right) : 0;
429     return(1 + m_max(lh,rh));
430     }
431    
432     /* Compute the height of a Red/Black tree */
433     int rbtree_height(rbtree_tree *tree)
434     {
435     return(!NIL(tree,tree->root) ? rbtree_height_node(tree,tree->root) : 0);
436     }
437    
438     /* Returns the number of nodes */
439     int rbtree_node_count(rbtree_tree *tree)
440     {
441     return(tree->node_count);
442     }
443    
444     /* Purge all nodes */
445     void rbtree_purge(rbtree_tree *tree)
446     {
447     mp_free_all_blocks(&tree->mp);
448     tree->node_count = 0;
449    
450     /* just in case */
451     memset(rbtree_nil(tree),0,sizeof(rbtree_node));
452     rbtree_nil(tree)->color = RBTREE_BLACK;
453    
454     /* reset root */
455     tree->root = rbtree_nil(tree);
456     }
457    
458     /* Check a node */
459     static int rbtree_check_node(rbtree_tree *tree,rbtree_node *node)
460     {
461     if (!NIL(tree,node)) return(0);
462    
463     if (!NIL(tree,node->left)) {
464     if (tree->key_cmp(node->key,node->left->key,tree->opt_data) <= 0)
465     return(-1);
466    
467     if (rbtree_check_node(tree,node->left) == -1)
468     return(-1);
469     }
470    
471     if (!NIL(tree,node->right)) {
472     if (tree->key_cmp(node->key,node->right->key,tree->opt_data) >= 0)
473     return(-1);
474    
475     if (rbtree_check_node(tree,node->right) == -1)
476     return(-1);
477     }
478    
479     return(0);
480     }
481    
482     /* Check tree consistency */
483     int rbtree_check(rbtree_tree *tree)
484     {
485     return(rbtree_check_node(tree,tree->root));
486     }
487    
488     /* Create a new Red/Black tree */
489     rbtree_tree *rbtree_create(tree_fcompare key_cmp,void *opt_data)
490     {
491     rbtree_tree *tree;
492    
493     if (!(tree = malloc(sizeof(*tree))))
494     return NULL;
495    
496     memset(tree,0,sizeof(*tree));
497    
498     /* initialize the memory pool */
499     if (!mp_create_fixed_pool(&tree->mp,"Red-Black Tree")) {
500     free(tree);
501     return NULL;
502     }
503    
504     /* initialize the "nil" pointer */
505     memset(rbtree_nil(tree),0,sizeof(rbtree_node));
506     rbtree_nil(tree)->color = RBTREE_BLACK;
507    
508     tree->key_cmp = key_cmp;
509     tree->opt_data = opt_data;
510     tree->root = rbtree_nil(tree);
511     return tree;
512     }
513    
514     /* Delete a Red/Black tree */
515     void rbtree_delete(rbtree_tree *tree)
516     {
517     if (tree) {
518     mp_free_pool(&tree->mp);
519     free(tree);
520     }
521     }

  ViewVC Help
Powered by ViewVC 1.1.26