Werner's Miscellanea
Sign in or create your account | Project List | Help
Werner's Miscellanea Git Source Tree
Root/
Source at commit 5a422a470d264cbba8ab2d3b8270f1b8424b569c created 13 years 4 months ago. By Werner Almesberger, qpkg/jrb.c (mk_new_ext): converted from macro to function | |
---|---|
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 | |
78 | static void insert(JRB item, JRB list) /* Inserts to the end of a list */ |
79 | { |
80 | JRB last_node; |
81 | |
82 | last_node = list->blink; |
83 | |
84 | list->blink = item; |
85 | last_node->flink = item; |
86 | item->blink = last_node; |
87 | item->flink = list; |
88 | } |
89 | |
90 | |
91 | static void delete_item(JRB item) /* Deletes an arbitrary iterm */ |
92 | { |
93 | item->flink->blink = item->blink; |
94 | item->blink->flink = item->flink; |
95 | } |
96 | |
97 | |
98 | static JRB mk_new_ext(void *key, void *val) |
99 | { |
100 | JRB new; |
101 | |
102 | new = (JRB) malloc(sizeof(struct jrb_node)); |
103 | new->val = val; |
104 | new->key = key; |
105 | setext(new); |
106 | setblack(new); |
107 | setnormal(new); |
108 | |
109 | return new; |
110 | } |
111 | |
112 | static void mk_new_int(JRB l, JRB r, JRB p, int il) |
113 | { |
114 | JRB newnode; |
115 | |
116 | newnode = (JRB) malloc(sizeof(struct jrb_node)); |
117 | setint(newnode); |
118 | setred(newnode); |
119 | setnormal(newnode); |
120 | newnode->flink = l; |
121 | newnode->blink = r; |
122 | newnode->parent = p; |
123 | setlext(newnode, l); |
124 | setrext(newnode, r); |
125 | l->parent = newnode; |
126 | r->parent = newnode; |
127 | setleft(l); |
128 | setright(r); |
129 | if (ishead(p)) { |
130 | p->parent = newnode; |
131 | setroot(newnode); |
132 | } else if (il) { |
133 | setleft(newnode); |
134 | p->flink = newnode; |
135 | } else { |
136 | setright(newnode); |
137 | p->blink = newnode; |
138 | } |
139 | recolor(newnode); |
140 | } |
141 | |
142 | |
143 | JRB lprev(JRB n) |
144 | { |
145 | if (ishead(n)) |
146 | return n; |
147 | while (!isroot(n)) { |
148 | if (isright(n)) |
149 | return n->parent; |
150 | n = n->parent; |
151 | } |
152 | return n->parent; |
153 | } |
154 | |
155 | |
156 | JRB rprev(JRB n) |
157 | { |
158 | if (ishead(n)) |
159 | return n; |
160 | while (!isroot(n)) { |
161 | if (isleft(n)) |
162 | return n->parent; |
163 | n = n->parent; |
164 | } |
165 | return n->parent; |
166 | } |
167 | |
168 | |
169 | JRB make_jrb(void) |
170 | { |
171 | JRB head; |
172 | |
173 | head = (JRB) malloc(sizeof(struct jrb_node)); |
174 | head->flink = head; |
175 | head->blink = head; |
176 | head->parent = head; |
177 | head->key = NULL; |
178 | sethead(head); |
179 | return head; |
180 | } |
181 | |
182 | |
183 | JRB jrb_find_gte(JRB n, const void *key, |
184 | int (*fxn)(const void *, const void *), int *fnd) |
185 | { |
186 | int cmp; |
187 | |
188 | *fnd = 0; |
189 | if (!ishead(n)) { |
190 | fprintf(stderr, "jrb_find_gte_str called on non-head %p\n", n); |
191 | exit(1); |
192 | } |
193 | if (n->parent == n) |
194 | return n; |
195 | cmp = (*fxn)(key, n->blink->key); |
196 | if (cmp == 0) { |
197 | *fnd = 1; |
198 | return n->blink; |
199 | } |
200 | if (cmp > 0) |
201 | return n; |
202 | else |
203 | n = n->parent; |
204 | while (1) { |
205 | if (isext(n)) |
206 | return n; |
207 | cmp = (*fxn)(key, getlext(n)->key); |
208 | if (cmp == 0) { |
209 | *fnd = 1; |
210 | return getlext(n); |
211 | } |
212 | if (cmp < 0) |
213 | n = n->flink; |
214 | else |
215 | n = n->blink; |
216 | } |
217 | } |
218 | |
219 | |
220 | JRB jrb_find(JRB n, const void *key, int (*fxn)(const void *, const void *)) |
221 | { |
222 | int fnd; |
223 | JRB j; |
224 | |
225 | j = jrb_find_gte(n, key, fxn, &fnd); |
226 | if (fnd) |
227 | return j; |
228 | else |
229 | return NULL; |
230 | } |
231 | |
232 | |
233 | static JRB jrb_insert_b(JRB n, void *key, void *val) |
234 | { |
235 | JRB newleft, newright, newnode, p; |
236 | |
237 | if (ishead(n)) { |
238 | if (n->parent == n) { /* Tree is empty */ |
239 | newnode = mk_new_ext(key, val); |
240 | insert(newnode, n); |
241 | n->parent = newnode; |
242 | newnode->parent = n; |
243 | setroot(newnode); |
244 | return newnode; |
245 | } else { |
246 | newright = mk_new_ext(key, val); |
247 | insert(newright, n); |
248 | newleft = newright->blink; |
249 | setnormal(newleft); |
250 | mk_new_int(newleft, newright, newleft->parent, |
251 | isleft(newleft)); |
252 | p = rprev(newright); |
253 | if (!ishead(p)) |
254 | setlext(p, newright); |
255 | return newright; |
256 | } |
257 | } else { |
258 | newleft = mk_new_ext(key, val); |
259 | insert(newleft, n); |
260 | setnormal(n); |
261 | mk_new_int(newleft, n, n->parent, isleft(n)); |
262 | p = lprev(newleft); |
263 | if (!ishead(p)) |
264 | setrext(p, newleft); |
265 | return newleft; |
266 | } |
267 | } |
268 | |
269 | |
270 | static void recolor(JRB n) |
271 | { |
272 | JRB p, gp, s; |
273 | int done = 0; |
274 | |
275 | while(!done) { |
276 | if (isroot(n)) { |
277 | setblack(n); |
278 | return; |
279 | } |
280 | |
281 | p = n->parent; |
282 | |
283 | if (isblack(p)) |
284 | return; |
285 | |
286 | if (isroot(p)) { |
287 | setblack(p); |
288 | return; |
289 | } |
290 | |
291 | gp = p->parent; |
292 | s = sibling(p); |
293 | if (isred(s)) { |
294 | setblack(p); |
295 | setred(gp); |
296 | setblack(s); |
297 | n = gp; |
298 | } else { |
299 | done = 1; |
300 | } |
301 | } |
302 | /* p's sibling is black, p is red, gp is black */ |
303 | |
304 | if ((isleft(n) == 0) == (isleft(p) == 0)) { |
305 | single_rotate(gp, isleft(n)); |
306 | setblack(p); |
307 | setred(gp); |
308 | } else { |
309 | single_rotate(p, isleft(n)); |
310 | single_rotate(gp, isleft(n)); |
311 | setblack(n); |
312 | setred(gp); |
313 | } |
314 | } |
315 | |
316 | |
317 | static void single_rotate(JRB y, int l) |
318 | { |
319 | int rl = 0 /* for gcc */, ir; |
320 | JRB x, yp; |
321 | |
322 | ir = isroot(y); |
323 | yp = y->parent; |
324 | if (!ir) |
325 | rl = isleft(y); |
326 | |
327 | if (l) { |
328 | x = y->flink; |
329 | y->flink = x->blink; |
330 | setleft(y->flink); |
331 | y->flink->parent = y; |
332 | x->blink = y; |
333 | setright(y); |
334 | } else { |
335 | x = y->blink; |
336 | y->blink = x->flink; |
337 | setright(y->blink); |
338 | y->blink->parent = y; |
339 | x->flink = y; |
340 | setleft(y); |
341 | } |
342 | |
343 | x->parent = yp; |
344 | y->parent = x; |
345 | if (ir) { |
346 | yp->parent = x; |
347 | setnormal(y); |
348 | setroot(x); |
349 | } else { |
350 | if (rl) { |
351 | yp->flink = x; |
352 | setleft(x); |
353 | } else { |
354 | yp->blink = x; |
355 | setright(x); |
356 | } |
357 | } |
358 | } |
359 | |
360 | |
361 | void jrb_delete_node(JRB n) |
362 | { |
363 | JRB s, p, gp; |
364 | char ir; |
365 | |
366 | if (isint(n)) { |
367 | fprintf(stderr, "Cannot delete an internal node: %p\n", n); |
368 | exit(1); |
369 | } |
370 | if (ishead(n)) { |
371 | fprintf(stderr, |
372 | "Cannot delete the head of an jrb_tree: %p\n", n); |
373 | exit(1); |
374 | } |
375 | delete_item(n); /* Delete it from the list */ |
376 | p = n->parent; /* The only node */ |
377 | if (isroot(n)) { |
378 | p->parent = p; |
379 | free(n); |
380 | return; |
381 | } |
382 | s = sibling(n); /* The only node after deletion */ |
383 | if (isroot(p)) { |
384 | s->parent = p->parent; |
385 | s->parent->parent = s; |
386 | setroot(s); |
387 | free(p); |
388 | free(n); |
389 | return; |
390 | } |
391 | gp = p->parent; /* Set parent to sibling */ |
392 | s->parent = gp; |
393 | if (isleft(p)) { |
394 | gp->flink = s; |
395 | setleft(s); |
396 | } else { |
397 | gp->blink = s; |
398 | setright(s); |
399 | } |
400 | ir = isred(p); |
401 | free(p); |
402 | free(n); |
403 | |
404 | if (isext(s)) { /* Update proper rext and lext values */ |
405 | p = lprev(s); |
406 | if (!ishead(p)) |
407 | setrext(p, s); |
408 | p = rprev(s); |
409 | if (!ishead(p)) |
410 | setlext(p, s); |
411 | } else if (isblack(s)) { |
412 | fprintf(stderr, "DELETION PROB -- sib is black, internal\n"); |
413 | exit(1); |
414 | } else { |
415 | p = lprev(s); |
416 | if (!ishead(p)) |
417 | setrext(p, s->flink); |
418 | p = rprev(s); |
419 | if (!ishead(p)) |
420 | setlext(p, s->blink); |
421 | setblack(s); |
422 | return; |
423 | } |
424 | |
425 | if (ir) |
426 | return; |
427 | |
428 | /* Recolor */ |
429 | |
430 | n = s; |
431 | p = n->parent; |
432 | s = sibling(n); |
433 | while(isblack(p) && isblack(s) && isint(s) && |
434 | isblack(s->flink) && isblack(s->blink)) { |
435 | setred(s); |
436 | n = p; |
437 | if (isroot(n)) |
438 | return; |
439 | p = n->parent; |
440 | s = sibling(n); |
441 | } |
442 | |
443 | if (isblack(p) && isred(s)) { /* Rotation 2.3b */ |
444 | single_rotate(p, isright(n)); |
445 | setred(p); |
446 | setblack(s); |
447 | s = sibling(n); |
448 | } |
449 | |
450 | { |
451 | JRB x, z; char il; |
452 | |
453 | if (isext(s)) { |
454 | fprintf(stderr, |
455 | "DELETION ERROR: sibling not internal\n"); |
456 | exit(1); |
457 | } |
458 | |
459 | il = isleft(n); |
460 | x = il ? s->flink : s->blink; |
461 | z = sibling(x); |
462 | |
463 | if (isred(z)) { /* Rotation 2.3f */ |
464 | single_rotate(p, !il); |
465 | setblack(z); |
466 | if (isred(p)) |
467 | setred(s); |
468 | else |
469 | setblack(s); |
470 | setblack(p); |
471 | } else if (isblack(x)) { /* Recoloring only (2.3c) */ |
472 | if (isred(s) || isblack(p)) { |
473 | fprintf(stderr, |
474 | "DELETION ERROR: 2.3c not quite right\n"); |
475 | exit(1); |
476 | } |
477 | setblack(p); |
478 | setred(s); |
479 | return; |
480 | } else if (isred(p)) { /* 2.3d */ |
481 | single_rotate(s, il); |
482 | single_rotate(p, !il); |
483 | setblack(x); |
484 | setred(s); |
485 | return; |
486 | } else { /* 2.3e */ |
487 | single_rotate(s, il); |
488 | single_rotate(p, !il); |
489 | setblack(x); |
490 | return; |
491 | } |
492 | } |
493 | } |
494 | |
495 | |
496 | int jrb_nblack(JRB n) |
497 | { |
498 | int nb; |
499 | |
500 | if (ishead(n) || isint(n)) { |
501 | fprintf(stderr, |
502 | "ERROR: jrb_nblack called on a non-external node %p\n", n); |
503 | exit(1); |
504 | } |
505 | nb = 0; |
506 | while(!ishead(n)) { |
507 | if (isblack(n)) nb++; |
508 | n = n->parent; |
509 | } |
510 | return nb; |
511 | } |
512 | |
513 | |
514 | int jrb_plength(JRB n) |
515 | { |
516 | int pl; |
517 | |
518 | if (ishead(n) || isint(n)) { |
519 | fprintf(stderr, |
520 | "ERROR: jrb_plength called on a non-external node %p\n", n); |
521 | exit(1); |
522 | } |
523 | pl = 0; |
524 | while (!ishead(n)) { |
525 | pl++; |
526 | n = n->parent; |
527 | } |
528 | return pl; |
529 | } |
530 | |
531 | |
532 | void jrb_free_tree(JRB n) |
533 | { |
534 | if (!ishead(n)) { |
535 | fprintf(stderr, |
536 | "ERROR: Rb_free_tree called on a non-head node\n"); |
537 | exit(1); |
538 | } |
539 | |
540 | while(jrb_first(n) != jrb_nil(n)) |
541 | jrb_delete_node(jrb_first(n)); |
542 | |
543 | free(n); |
544 | } |
545 | |
546 | |
547 | void *jrb_val(JRB n) |
548 | { |
549 | return n->val; |
550 | } |
551 | |
552 | |
553 | JRB jrb_insert(JRB tree, void *key, void *val, |
554 | int (*func)(const void *a, const void *b)) |
555 | { |
556 | int fnd; |
557 | |
558 | return jrb_insert_b(jrb_find_gte(tree, key, func, &fnd), key, val); |
559 | } |
560 |
Branches:
master