Werner's Miscellanea
Sign in or create your account | Project List | Help
Werner's Miscellanea Git Source Tree
Root/
Source at commit cc92c670802bb7f7a0789777f86f0c3f00706216 created 13 years 4 months ago. By Werner Almesberger, qpkg: (jrb) remove _gen suffix, since we removed the non-generic variants | |
---|---|
1 | /* |
2 | Libraries for fields, doubly-linked lists and red-black trees. |
3 | Copyright (C) 2001 James S. Plank |
4 | |
5 | This library is free software; you can redistribute it and/or |
6 | modify it under the terms of the GNU Lesser General Public |
7 | License as published by the Free Software Foundation; either |
8 | version 2.1 of the License, or (at your option) any later version. |
9 | |
10 | This library is distributed in the hope that it will be useful, |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | Lesser General Public License for more details. |
14 | |
15 | You should have received a copy of the GNU Lesser General Public |
16 | License along with this library; if not, write to the Free Software |
17 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
18 | |
19 | --------------------------------------------------------------------------- |
20 | Please see http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Libfdr/ |
21 | for instruction on how to use this library. |
22 | |
23 | Jim Plank |
24 | plank@cs.utk.edu |
25 | http://www.cs.utk.edu/~plank |
26 | |
27 | Associate Professor |
28 | Department of Computer Science |
29 | University of Tennessee |
30 | 203 Claxton Complex |
31 | 1122 Volunteer Blvd. |
32 | Knoxville, TN 37996-3450 |
33 | |
34 | 865-974-4397 |
35 | Fax: 865-974-4404 |
36 | */ |
37 | /* Revision 1.2. Jim Plank */ |
38 | |
39 | /* Original code by Jim Plank (plank@cs.utk.edu) */ |
40 | /* modified for THINK C 6.0 for Macintosh by Chris Bartley */ |
41 | |
42 | #include <string.h> |
43 | #include <stdio.h> |
44 | #include <stdlib.h> |
45 | #include <ctype.h> |
46 | #include "jrb.h" |
47 | |
48 | static void mk_new_int(JRB l, JRB r, JRB p, int il); |
49 | static JRB lprev(JRB n); |
50 | static JRB rprev(JRB n); |
51 | static void recolor(JRB n); |
52 | static void single_rotate(JRB y, int l); |
53 | |
54 | #define isred(n) (n->red) |
55 | #define isblack(n) (!isred(n)) |
56 | #define isleft(n) (n->left) |
57 | #define isright(n) (!isleft(n)) |
58 | #define isint(n) (n->internal) |
59 | #define isext(n) (!isint(n)) |
60 | #define ishead(n) (n->roothead & 2) |
61 | #define isroot(n) (n->roothead & 1) |
62 | #define getlext(n) ((struct jrb_node *)(n->key)) |
63 | #define setlext(node, val) node->key = (void *) (val) |
64 | #define getrext(n) ((struct jrb_node *)(n->val)) |
65 | #define setrext(node, value) node->val = (void *) (value) |
66 | #define setred(n) n->red = 1 |
67 | #define setblack(n) n->red = 0 |
68 | #define setleft(n) n->left = 1 |
69 | #define setright(n) n->left = 0 |
70 | #define sethead(n) (n->roothead |= 2) |
71 | #define setroot(n) (n->roothead |= 1) |
72 | #define setint(n) n->internal = 1 |
73 | #define setext(n) n->internal = 0 |
74 | #define setnormal(n) n->roothead = 0 |
75 | #define sibling(n) ((isleft(n)) ? n->parent->blink : n->parent->flink) |
76 | |
77 | static void insert(JRB item, JRB list) /* Inserts to the end of a list */ |
78 | { |
79 | JRB last_node; |
80 | |
81 | last_node = list->blink; |
82 | |
83 | list->blink = item; |
84 | last_node->flink = item; |
85 | item->blink = last_node; |
86 | item->flink = list; |
87 | } |
88 | |
89 | static void delete_item(JRB item) /* Deletes an arbitrary iterm */ |
90 | { |
91 | item->flink->blink = item->blink; |
92 | item->blink->flink = item->flink; |
93 | } |
94 | |
95 | #define mk_new_ext(new, kkkey, vvval) {\ |
96 | new = (JRB) malloc(sizeof(struct jrb_node));\ |
97 | new->val = vvval;\ |
98 | new->key = kkkey;\ |
99 | setext(new);\ |
100 | setblack(new);\ |
101 | setnormal(new);\ |
102 | } |
103 | |
104 | static void mk_new_int(JRB l, JRB r, JRB p, int il) |
105 | { |
106 | JRB newnode; |
107 | |
108 | newnode = (JRB) malloc(sizeof(struct jrb_node)); |
109 | setint(newnode); |
110 | setred(newnode); |
111 | setnormal(newnode); |
112 | newnode->flink = l; |
113 | newnode->blink = r; |
114 | newnode->parent = p; |
115 | setlext(newnode, l); |
116 | setrext(newnode, r); |
117 | l->parent = newnode; |
118 | r->parent = newnode; |
119 | setleft(l); |
120 | setright(r); |
121 | if (ishead(p)) { |
122 | p->parent = newnode; |
123 | setroot(newnode); |
124 | } else if (il) { |
125 | setleft(newnode); |
126 | p->flink = newnode; |
127 | } else { |
128 | setright(newnode); |
129 | p->blink = newnode; |
130 | } |
131 | recolor(newnode); |
132 | } |
133 | |
134 | |
135 | JRB lprev(JRB n) |
136 | { |
137 | if (ishead(n)) return n; |
138 | while (!isroot(n)) { |
139 | if (isright(n)) return n->parent; |
140 | n = n->parent; |
141 | } |
142 | return n->parent; |
143 | } |
144 | |
145 | JRB rprev(JRB n) |
146 | { |
147 | if (ishead(n)) return n; |
148 | while (!isroot(n)) { |
149 | if (isleft(n)) return n->parent; |
150 | n = n->parent; |
151 | } |
152 | return n->parent; |
153 | } |
154 | |
155 | JRB make_jrb(void) |
156 | { |
157 | JRB head; |
158 | |
159 | head = (JRB) malloc (sizeof(struct jrb_node)); |
160 | head->flink = head; |
161 | head->blink = head; |
162 | head->parent = head; |
163 | head->key = NULL; |
164 | sethead(head); |
165 | return head; |
166 | } |
167 | |
168 | JRB jrb_find_gte(JRB n, const void *key, |
169 | int (*fxn)(const void *, const void *), int *fnd) |
170 | { |
171 | int cmp; |
172 | |
173 | *fnd = 0; |
174 | if (!ishead(n)) { |
175 | fprintf(stderr, "jrb_find_gte_str called on non-head %p\n", n); |
176 | exit(1); |
177 | } |
178 | if (n->parent == n) return n; |
179 | cmp = (*fxn)(key, n->blink->key); |
180 | if (cmp == 0) { |
181 | *fnd = 1; |
182 | return n->blink; |
183 | } |
184 | if (cmp > 0) return n; |
185 | else n = n->parent; |
186 | while (1) { |
187 | if (isext(n)) return n; |
188 | cmp = (*fxn)(key, getlext(n)->key); |
189 | if (cmp == 0) { |
190 | *fnd = 1; |
191 | return getlext(n); |
192 | } |
193 | if (cmp < 0) n = n->flink ; else n = n->blink; |
194 | } |
195 | } |
196 | |
197 | JRB jrb_find(JRB n, const void *key, int (*fxn)(const void *, const void *)) |
198 | { |
199 | int fnd; |
200 | JRB j; |
201 | |
202 | j = jrb_find_gte(n, key, fxn, &fnd); |
203 | if (fnd) return j; else return NULL; |
204 | } |
205 | |
206 | static JRB jrb_insert_b(JRB n, void *key, void *val) |
207 | { |
208 | JRB newleft, newright, newnode, p; |
209 | |
210 | if (ishead(n)) { |
211 | if (n->parent == n) { /* Tree is empty */ |
212 | mk_new_ext(newnode, key, val); |
213 | insert(newnode, n); |
214 | n->parent = newnode; |
215 | newnode->parent = n; |
216 | setroot(newnode); |
217 | return newnode; |
218 | } else { |
219 | mk_new_ext(newright, key, val); |
220 | insert(newright, n); |
221 | newleft = newright->blink; |
222 | setnormal(newleft); |
223 | mk_new_int(newleft, newright, newleft->parent, isleft(newleft)); |
224 | p = rprev(newright); |
225 | if (!ishead(p)) setlext(p, newright); |
226 | return newright; |
227 | } |
228 | } else { |
229 | mk_new_ext(newleft, key, val); |
230 | insert(newleft, n); |
231 | setnormal(n); |
232 | mk_new_int(newleft, n, n->parent, isleft(n)); |
233 | p = lprev(newleft); |
234 | if (!ishead(p)) setrext(p, newleft); |
235 | return newleft; |
236 | } |
237 | } |
238 | |
239 | static void recolor(JRB n) |
240 | { |
241 | JRB p, gp, s; |
242 | int done = 0; |
243 | |
244 | while(!done) { |
245 | if (isroot(n)) { |
246 | setblack(n); |
247 | return; |
248 | } |
249 | |
250 | p = n->parent; |
251 | |
252 | if (isblack(p)) return; |
253 | |
254 | if (isroot(p)) { |
255 | setblack(p); |
256 | return; |
257 | } |
258 | |
259 | gp = p->parent; |
260 | s = sibling(p); |
261 | if (isred(s)) { |
262 | setblack(p); |
263 | setred(gp); |
264 | setblack(s); |
265 | n = gp; |
266 | } else { |
267 | done = 1; |
268 | } |
269 | } |
270 | /* p's sibling is black, p is red, gp is black */ |
271 | |
272 | if ((isleft(n) == 0) == (isleft(p) == 0)) { |
273 | single_rotate(gp, isleft(n)); |
274 | setblack(p); |
275 | setred(gp); |
276 | } else { |
277 | single_rotate(p, isleft(n)); |
278 | single_rotate(gp, isleft(n)); |
279 | setblack(n); |
280 | setred(gp); |
281 | } |
282 | } |
283 | |
284 | static void single_rotate(JRB y, int l) |
285 | { |
286 | int rl = 0 /* for gcc */, ir; |
287 | JRB x, yp; |
288 | |
289 | ir = isroot(y); |
290 | yp = y->parent; |
291 | if (!ir) { |
292 | rl = isleft(y); |
293 | } |
294 | |
295 | if (l) { |
296 | x = y->flink; |
297 | y->flink = x->blink; |
298 | setleft(y->flink); |
299 | y->flink->parent = y; |
300 | x->blink = y; |
301 | setright(y); |
302 | } else { |
303 | x = y->blink; |
304 | y->blink = x->flink; |
305 | setright(y->blink); |
306 | y->blink->parent = y; |
307 | x->flink = y; |
308 | setleft(y); |
309 | } |
310 | |
311 | x->parent = yp; |
312 | y->parent = x; |
313 | if (ir) { |
314 | yp->parent = x; |
315 | setnormal(y); |
316 | setroot(x); |
317 | } else { |
318 | if (rl) { |
319 | yp->flink = x; |
320 | setleft(x); |
321 | } else { |
322 | yp->blink = x; |
323 | setright(x); |
324 | } |
325 | } |
326 | } |
327 | |
328 | void jrb_delete_node(JRB n) |
329 | { |
330 | JRB s, p, gp; |
331 | char ir; |
332 | |
333 | if (isint(n)) { |
334 | fprintf(stderr, "Cannot delete an internal node: %p\n", n); |
335 | exit(1); |
336 | } |
337 | if (ishead(n)) { |
338 | fprintf(stderr, "Cannot delete the head of an jrb_tree: %p\n", n); |
339 | exit(1); |
340 | } |
341 | delete_item(n); /* Delete it from the list */ |
342 | p = n->parent; /* The only node */ |
343 | if (isroot(n)) { |
344 | p->parent = p; |
345 | free(n); |
346 | return; |
347 | } |
348 | s = sibling(n); /* The only node after deletion */ |
349 | if (isroot(p)) { |
350 | s->parent = p->parent; |
351 | s->parent->parent = s; |
352 | setroot(s); |
353 | free(p); |
354 | free(n); |
355 | return; |
356 | } |
357 | gp = p->parent; /* Set parent to sibling */ |
358 | s->parent = gp; |
359 | if (isleft(p)) { |
360 | gp->flink = s; |
361 | setleft(s); |
362 | } else { |
363 | gp->blink = s; |
364 | setright(s); |
365 | } |
366 | ir = isred(p); |
367 | free(p); |
368 | free(n); |
369 | |
370 | if (isext(s)) { /* Update proper rext and lext values */ |
371 | p = lprev(s); |
372 | if (!ishead(p)) setrext(p, s); |
373 | p = rprev(s); |
374 | if (!ishead(p)) setlext(p, s); |
375 | } else if (isblack(s)) { |
376 | fprintf(stderr, "DELETION PROB -- sib is black, internal\n"); |
377 | exit(1); |
378 | } else { |
379 | p = lprev(s); |
380 | if (!ishead(p)) setrext(p, s->flink); |
381 | p = rprev(s); |
382 | if (!ishead(p)) setlext(p, s->blink); |
383 | setblack(s); |
384 | return; |
385 | } |
386 | |
387 | if (ir) return; |
388 | |
389 | /* Recolor */ |
390 | |
391 | n = s; |
392 | p = n->parent; |
393 | s = sibling(n); |
394 | while(isblack(p) && isblack(s) && isint(s) && |
395 | isblack(s->flink) && isblack(s->blink)) { |
396 | setred(s); |
397 | n = p; |
398 | if (isroot(n)) return; |
399 | p = n->parent; |
400 | s = sibling(n); |
401 | } |
402 | |
403 | if (isblack(p) && isred(s)) { /* Rotation 2.3b */ |
404 | single_rotate(p, isright(n)); |
405 | setred(p); |
406 | setblack(s); |
407 | s = sibling(n); |
408 | } |
409 | |
410 | { JRB x, z; char il; |
411 | |
412 | if (isext(s)) { |
413 | fprintf(stderr, "DELETION ERROR: sibling not internal\n"); |
414 | exit(1); |
415 | } |
416 | |
417 | il = isleft(n); |
418 | x = il ? s->flink : s->blink ; |
419 | z = sibling(x); |
420 | |
421 | if (isred(z)) { /* Rotation 2.3f */ |
422 | single_rotate(p, !il); |
423 | setblack(z); |
424 | if (isred(p)) setred(s); else setblack(s); |
425 | setblack(p); |
426 | } else if (isblack(x)) { /* Recoloring only (2.3c) */ |
427 | if (isred(s) || isblack(p)) { |
428 | fprintf(stderr, "DELETION ERROR: 2.3c not quite right\n"); |
429 | exit(1); |
430 | } |
431 | setblack(p); |
432 | setred(s); |
433 | return; |
434 | } else if (isred(p)) { /* 2.3d */ |
435 | single_rotate(s, il); |
436 | single_rotate(p, !il); |
437 | setblack(x); |
438 | setred(s); |
439 | return; |
440 | } else { /* 2.3e */ |
441 | single_rotate(s, il); |
442 | single_rotate(p, !il); |
443 | setblack(x); |
444 | return; |
445 | } |
446 | } |
447 | } |
448 | |
449 | int jrb_nblack(JRB n) |
450 | { |
451 | int nb; |
452 | if (ishead(n) || isint(n)) { |
453 | fprintf(stderr, "ERROR: jrb_nblack called on a non-external node %p\n", n); |
454 | exit(1); |
455 | } |
456 | nb = 0; |
457 | while(!ishead(n)) { |
458 | if (isblack(n)) nb++; |
459 | n = n->parent; |
460 | } |
461 | return nb; |
462 | } |
463 | |
464 | int jrb_plength(JRB n) |
465 | { |
466 | int pl; |
467 | if (ishead(n) || isint(n)) { |
468 | fprintf(stderr, "ERROR: jrb_plength called on a non-external node %p\n", n); |
469 | exit(1); |
470 | } |
471 | pl = 0; |
472 | while(!ishead(n)) { |
473 | pl++; |
474 | n = n->parent; |
475 | } |
476 | return pl; |
477 | } |
478 | |
479 | void jrb_free_tree(JRB n) |
480 | { |
481 | if (!ishead(n)) { |
482 | fprintf(stderr, "ERROR: Rb_free_tree called on a non-head node\n"); |
483 | exit(1); |
484 | } |
485 | |
486 | while(jrb_first(n) != jrb_nil(n)) { |
487 | jrb_delete_node(jrb_first(n)); |
488 | } |
489 | free(n); |
490 | } |
491 | |
492 | void *jrb_val(JRB n) |
493 | { |
494 | return n->val; |
495 | } |
496 | |
497 | JRB jrb_insert(JRB tree, void *key, void *val, |
498 | int (*func)(const void *, const void *)) |
499 | { |
500 | int fnd; |
501 | |
502 | return jrb_insert_b(jrb_find_gte(tree, key, func, &fnd), key, val); |
503 | } |
504 |
Branches:
master