1 /*  pdnmesh - a 2D finite element solver
2     Copyright (C) 2001-2005 Sarod Yatawatta <sarod@users.sf.net>
3   This program is free software; you can redistribute it and/or modify
4   it under the terms of the GNU General Public License as published by
5   the Free Software Foundation; either version 2 of the License, or
6   (at your option) any later version.
7 
8   This program is distributed in the hope that it will be useful,
9   but WITHOUT ANY WARRANTY; without even the implied warranty of
10   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11   GNU General Public License for more details.
12 
13   You should have received a copy of the GNU General Public License
14   along with this program; if not, write to the Free Software
15   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16   $Id: rbt.c,v 1.11 2005/04/18 08:30:00 sarod Exp $
17 */
18 
19 #ifdef HAVE_CONFIG_H
20 #include <config.h>
21 #endif
22 
23 /* generic RBT */
24 
25 #include <stdio.h>
26 #include <stdlib.h> /* for malloc */
27 #include "types.h"
28 
29 /* sentinel */
30 #ifndef NIL
31 #define NIL &sentinel
32 RBT_node_type sentinel={NIL,NIL,0,rbtBLACK,0};
33 #endif /* NIL */
34 
35 /* intialize tree */
36 int
RBT_init(RBT_tree * t,int (* comp_EQ)(const void * rec1,const void * rec2),int (* comp_LT)(const void * rec1,const void * rec2),void (* print_record)(const void * rec),void (* free_record)(void * rec))37 RBT_init(RBT_tree *t, int (*comp_EQ) (const void *rec1, const void *rec2),
38 		int (*comp_LT) (const void *rec1, const void *rec2),
39 	        void (*print_record) (const void *rec),
40 					void (*free_record)(void *rec))
41 {
42  t->root=NIL;
43  t->comp_EQ=comp_EQ;
44  t->comp_LT=comp_LT;
45  t->print_record=print_record;
46  t->free_record=free_record;
47 
48  return(RBT_STATUS_OK);
49 }
50 
51 /* local rotation routines */
52 /* rotate node x to left */
53 static void
rotate_left(RBT_node_type * x,RBT_tree * t)54 rotate_left(RBT_node_type *x,RBT_tree *t)
55 {
56 
57   RBT_node_type *y=x->right;
58   /*establish x->right link */
59   x->right=y->left;
60   if (y->left != NIL) y->left->parent=x;
61 
62   /* establish y->parent link */
63   if (y!=NIL) y->parent =x->parent;
64   if (x->parent) {
65    if (x == x->parent->left)
66      x->parent->left =y;
67    else
68      x->parent->right=y;
69   } else {
70    t->root=y;
71   }
72 
73   /* link x and y */
74   y->left =x;
75   if ( x != NIL ) x->parent =y;
76 }
77 
78 /* rotate node x to right */
79 static void
rotate_right(RBT_node_type * x,RBT_tree * t)80 rotate_right(RBT_node_type *x,RBT_tree *t) {
81 
82     RBT_node_type *y = x->left;
83 
84     /* establish x->left link */
85     x->left = y->right;
86     if (y->right != NIL) y->right->parent = x;
87 
88     /* establish y->parent link */
89     if (y != NIL) y->parent = x->parent;
90     if (x->parent) {
91         if (x == x->parent->right)
92             x->parent->right = y;
93         else
94             x->parent->left = y;
95     } else {
96         t->root = y;
97     }
98 
99     /* link x and y */
100     y->right = x;
101     if (x != NIL) x->parent = y;
102 }
103 
104 /* rebalance after insertion of x */
105 static void
insert_fixup(RBT_node_type * x,RBT_tree * t)106 insert_fixup(RBT_node_type *x,RBT_tree *t) {
107 
108 
109     /* check Red-Black properties */
110     while (x != t->root && x->parent->color == rbtRED) {
111         /* we have a violation */
112         if (x->parent == x->parent->parent->left) {
113             RBT_node_type *y = x->parent->parent->right;
114             if (y->color == rbtRED) {
115 
116                 /* uncle is rbtRED */
117                 x->parent->color = rbtBLACK;
118                 y->color = rbtBLACK;
119                 x->parent->parent->color = rbtRED;
120                 x = x->parent->parent;
121             } else {
122 
123                 /* uncle is rbtBLACK */
124                 if (x == x->parent->right) {
125                     /* make x a left child */
126                     x = x->parent;
127                     rotate_left(x,t);
128                 }
129 
130                 /* recolor and rotate */
131                 x->parent->color = rbtBLACK;
132                 x->parent->parent->color = rbtRED;
133                 rotate_right(x->parent->parent,t);
134             }
135         } else {
136 
137             /* mirror image of above code */
138             RBT_node_type *y = x->parent->parent->left;
139             if (y->color == rbtRED) {
140 
141                 /* uncle is rbtRED */
142                 x->parent->color = rbtBLACK;
143                 y->color = rbtBLACK;
144                 x->parent->parent->color = rbtRED;
145                 x = x->parent->parent;
146             } else {
147 
148                 /* uncle is rbtBLACK */
149                 if (x == x->parent->left) {
150                     x = x->parent;
151                     rotate_right(x,t);
152                 }
153                 x->parent->color = rbtBLACK;
154                 x->parent->parent->color = rbtRED;
155                 rotate_left(x->parent->parent,t);
156             }
157         }
158     }
159     t->root->color = rbtBLACK;
160 }
161 
162 /* insert data record */
163 int
RBT_insert(void * rec,RBT_tree * t)164 RBT_insert(void *rec, RBT_tree *t) {
165     RBT_node_type *current, *parent, *x;
166 
167     /* find future parent */
168     current = t->root;
169     parent = 0;
170     while (current != NIL) {
171         if (t->comp_EQ(rec, current->rec))
172             return(RBT_STATUS_KEY_FOUND);
173         parent = current;
174         current = t->comp_LT(rec, current->rec) ?
175             current->left : current->right;
176     }
177 
178     /* setup new node */
179     if ((x =(RBT_node_type *)malloc(sizeof(*x))) == 0)
180     {
181        fprintf(stderr,"%s: %d: no free memory",__FILE__,__LINE__);
182        exit(1);
183     }
184     x->parent = parent;
185     x->left = NIL;
186     x->right = NIL;
187     x->color = rbtRED;
188     x->rec=rec; /* fixme - use memcpy */
189 
190     /* insert node in tree */
191     if(parent) {
192         if(t->comp_LT(rec, parent->rec))
193             parent->left = x;
194         else
195             parent->right = x;
196     } else {
197         t->root = x;
198     }
199 
200     insert_fixup(x,t);
201 
202     return(RBT_STATUS_OK);
203 }
204 
205 /* delete fixing -local */
206 static void
delete_fixup(RBT_node_type * x,RBT_tree * t)207 delete_fixup(RBT_node_type *x,RBT_tree *t) {
208 
209     while (x != t->root && x->color == rbtBLACK) {
210         if (x == x->parent->left) {
211             RBT_node_type *w = x->parent->right;
212             if (w->color == rbtRED) {
213                 w->color = rbtBLACK;
214                 x->parent->color = rbtRED;
215                 rotate_left(x->parent,t);
216                 w = x->parent->right;
217             }
218             if (w->left->color == rbtBLACK && w->right->color == rbtBLACK) {
219                 w->color = rbtRED;
220                 x = x->parent;
221             } else {
222                 if (w->right->color == rbtBLACK) {
223                     w->left->color = rbtBLACK;
224                     w->color = rbtRED;
225                     rotate_right(w,t);
226                     w = x->parent->right;
227                 }
228                 w->color = x->parent->color;
229                 x->parent->color = rbtBLACK;
230                 w->right->color = rbtBLACK;
231                 rotate_left(x->parent,t);
232                 x = t->root;
233             }
234         } else {
235             RBT_node_type *w = x->parent->left;
236             if (w->color == rbtRED) {
237                 w->color = rbtBLACK;
238                 x->parent->color = rbtRED;
239                 rotate_right(x->parent,t);
240                 w = x->parent->left;
241             }
242             if (w->right->color == rbtBLACK && w->left->color == rbtBLACK) {
243                 w->color = rbtRED;
244                 x = x->parent;
245             } else {
246                 if (w->left->color == rbtBLACK) {
247                     w->right->color = rbtBLACK;
248                     w->color = rbtRED;
249                     rotate_left(w,t);
250                     w = x->parent->left;
251                 }
252                 w->color = x->parent->color;
253                 x->parent->color = rbtBLACK;
254                 w->left->color = rbtBLACK;
255                 rotate_right(x->parent,t);
256                 x = t->root;
257             }
258         }
259     }
260     x->color = rbtBLACK;
261 }
262 
263 /* deletion routine */
264 int
RBT_delete(void * rec,RBT_tree * t)265 RBT_delete(void * rec,RBT_tree *t) {
266     RBT_node_type *x, *y, *z;
267 
268     /* find node in tree */
269     z = t->root;
270     while(z != NIL) {
271         if(t->comp_EQ(rec, z->rec))
272             break;
273         else
274             z = t->comp_LT(rec, z->rec) ? z->left : z->right;
275     }
276     if (z == NIL) return(RBT_STATUS_KEY_NOT_FOUND); /* not found */
277 
278     if (z->left == NIL || z->right == NIL) {
279         /* y has a NIL node as a child */
280         y = z;
281     } else {
282         /* find tree successor with a NIL node as a child */
283         y = z->right;
284         while (y->left != NIL) y = y->left;
285     }
286 
287     /* x is y's only child */
288     if (y->left != NIL)
289         x = y->left;
290     else
291         x = y->right;
292 
293     /* remove y from the parent chain */
294     x->parent = y->parent;
295     if (y->parent)
296         if (y == y->parent->left)
297             y->parent->left = x;
298         else
299             y->parent->right = x;
300     else
301         t->root = x;
302 
303     if (y != z) {
304         z->rec = y->rec;
305     }
306 
307 
308     if (y->color == rbtBLACK)
309         delete_fixup(x,t);
310 
311     free(y);
312     return(RBT_STATUS_OK);
313 }
314 
315 /* search RBT for the record */
316 /* rec will point to the actual record if found */
317 void *
RBT_find(void * rec,RBT_tree * t)318 RBT_find(void *rec, RBT_tree *t)
319 {
320 
321     RBT_node_type *current = t->root;
322     while(current != NIL) {
323         if(t->comp_EQ(rec, current->rec)) {
324             /*rec = current->rec;
325             return(RBT_STATUS_KEY_FOUND); */
326 						return((void*)current->rec);
327         } else {
328             current = t->comp_LT(rec, current->rec) ?
329                 current->left : current->right;
330         }
331     }
332     /*return(RBT_STATUS_KEY_NOT_FOUND); */
333 		return(0);
334 }
335 
336 /* local visit */
337 static void
visit_node(RBT_node_type * n,RBT_tree * t)338 visit_node(RBT_node_type *n,RBT_tree *t)
339 {
340   if ( n != NIL ){
341     visit_node(n->left,t);
342     t->print_record(n->rec);
343     visit_node(n->right,t);
344   }
345 }
346 
347 /* traverse tree */
348 void
RBT_traverse(RBT_tree * t)349 RBT_traverse(RBT_tree *t)
350 {
351  visit_node(t->root,t);
352 }
353 
354 
355 /* local free */
356 static void
free_local(RBT_node_type * n,RBT_tree * t)357 free_local(RBT_node_type *n,RBT_tree *t)
358 {
359  if ( n!=NIL ) {
360 		free_local(n->left,t);
361 		free_local(n->right,t);
362 		t->free_record(n->rec);
363 	  free(n);
364     n=NIL;
365  }
366 }
367 /* free memory used by a  tree */
368 /* makes t=NIL */
369 void
RBT_free(RBT_tree * t)370 RBT_free(RBT_tree *t)
371 {
372  free_local(t->root,t);
373  t->root=NIL;
374 }
375