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