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