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