Root/qpkg/jrb.c

Source at commit a9f12d56661a8e6def5a2b32519c3efd55e38d31 created 8 years 11 months ago.
By Werner Almesberger, qpkg: converted ID comparison from "struct id *" to "void *"
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/* 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
74static 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
88static 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
95static 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
139static 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
186static 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
200static 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
231static 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
244static 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
257struct 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
271struct 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
308struct 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
322static 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
359void 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
491int 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
509int 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
527void 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
542void *jrb_val(struct jrb *n)
543{
544    return n->val;
545}
546
547
548struct 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

Archive Download this file

Branches:
master



interactive