Root/qpkg/jrb.c

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 <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
72static 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
86static 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
93static 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
137static 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
184static 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
198static 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
229static 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
242static 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
255struct 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
269struct 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
306struct 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
320static 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
357void 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
489int 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
507int 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
525void 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
540void *jrb_val(struct jrb *n)
541{
542    return n->val;
543}
544
545
546struct 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
555struct 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

Archive Download this file

Branches:
master



interactive