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