Root/qpkg/jrb.c

Source at commit 7e641d2655b767e7282a05959a19ac0d54542323 created 8 years 10 months ago.
By Werner Almesberger, qpkg/jrb.[ch]: remove trailing spaces
1/*
2Libraries for fields, doubly-linked lists and red-black trees.
3Copyright (C) 2001 James S. Plank
4
5This library is free software; you can redistribute it and/or
6modify it under the terms of the GNU Lesser General Public
7License as published by the Free Software Foundation; either
8version 2.1 of the License, or (at your option) any later version.
9
10This library is distributed in the hope that it will be useful,
11but WITHOUT ANY WARRANTY; without even the implied warranty of
12MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13Lesser General Public License for more details.
14
15You should have received a copy of the GNU Lesser General Public
16License along with this library; if not, write to the Free Software
17Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18
19---------------------------------------------------------------------------
20Please see http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Libfdr/
21for instruction on how to use this library.
22
23Jim Plank
24plank@cs.utk.edu
25http://www.cs.utk.edu/~plank
26
27Associate Professor
28Department of Computer Science
29University of Tennessee
30203 Claxton Complex
311122 Volunteer Blvd.
32Knoxville, TN 37996-3450
33
34     865-974-4397
35Fax: 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
48static void mk_new_int(JRB l, JRB r, JRB p, int il);
49static JRB lprev(JRB n);
50static JRB rprev(JRB n);
51static void recolor(JRB n);
52static 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
78static 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
91static 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
98static 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
112static 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
143JRB 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
156JRB 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
169JRB 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
183JRB 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
220JRB 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
233static 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
270static 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
317static 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
361void jrb_delete_node(JRB n)
362{
363    JRB s, p, gp, x, z;
364    char ir, il;
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    if (isext(s)) {
451        fprintf(stderr, "DELETION ERROR: sibling not internal\n");
452        exit(1);
453    }
454
455    il = isleft(n);
456    x = il ? s->flink : s->blink;
457    z = sibling(x);
458
459    if (isred(z)) { /* Rotation 2.3f */
460        single_rotate(p, !il);
461        setblack(z);
462        if (isred(p))
463            setred(s);
464        else
465            setblack(s);
466        setblack(p);
467        return;
468    }
469    if (isblack(x)) { /* Recoloring only (2.3c) */
470        if (isred(s) || isblack(p)) {
471            fprintf(stderr,
472                "DELETION ERROR: 2.3c not quite right\n");
473            exit(1);
474        }
475        setblack(p);
476        setred(s);
477        return;
478    }
479    if (isred(p)) { /* 2.3d */
480        single_rotate(s, il);
481        single_rotate(p, !il);
482        setblack(x);
483        setred(s);
484    return;
485    }
486    /* 2.3e */
487    single_rotate(s, il);
488    single_rotate(p, !il);
489    setblack(x);
490}
491
492
493int jrb_nblack(JRB n)
494{
495    int nb;
496
497    if (ishead(n) || isint(n)) {
498        fprintf(stderr,
499            "ERROR: jrb_nblack called on a non-external node %p\n", n);
500        exit(1);
501    }
502    nb = 0;
503    while (!ishead(n)) {
504        if (isblack(n)) nb++;
505        n = n->parent;
506    }
507    return nb;
508}
509
510
511int jrb_plength(JRB n)
512{
513    int pl;
514
515    if (ishead(n) || isint(n)) {
516        fprintf(stderr,
517            "ERROR: jrb_plength called on a non-external node %p\n", n);
518        exit(1);
519    }
520    pl = 0;
521    while (!ishead(n)) {
522        pl++;
523        n = n->parent;
524    }
525    return pl;
526}
527
528
529void jrb_free_tree(JRB n)
530{
531    if (!ishead(n)) {
532        fprintf(stderr,
533            "ERROR: Rb_free_tree called on a non-head node\n");
534        exit(1);
535    }
536
537    while (jrb_first(n) != jrb_nil(n))
538        jrb_delete_node(jrb_first(n));
539
540    free(n);
541}
542
543
544void *jrb_val(JRB n)
545{
546    return n->val;
547}
548
549
550JRB jrb_insert(JRB tree, void *key, void *val,
551                          int (*func)(const void *a, const void *b))
552{
553    int fnd;
554
555    return jrb_insert_b(jrb_find_gte(tree, key, func, &fnd), key, val);
556}
557

Archive Download this file

Branches:
master



interactive