/[dynamips]/upstream/dynamips-0.2.5/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

Contents of /upstream/dynamips-0.2.5/rbtree.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1 - (show annotations)
Sat Oct 6 16:01:44 2007 UTC (12 years, 2 months ago) by dpavlin
File MIME type: text/plain
File size: 11687 byte(s)
import 0.2.5 from upstream

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