Root/qpkg/jrb.c

Source at commit 2787a45c436c35fc6fd0ed452903ad045fe9571d created 9 years 24 days ago.
By Werner Almesberger, qpkg: added James S. Plank's red-black trees
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);
53static void jrb_print_tree(JRB t, int level);
54static void jrb_iprint_tree(JRB t, int level);
55 
56#define isred(n) (n->red)
57#define isblack(n) (!isred(n))
58#define isleft(n) (n->left)
59#define isright(n) (!isleft(n))
60#define isint(n) (n->internal)
61#define isext(n) (!isint(n))
62#define ishead(n) (n->roothead & 2)
63#define isroot(n) (n->roothead & 1)
64#define getlext(n) ((struct jrb_node *)(n->key.v))
65#define setlext(node, val) node->key.v = (void *) (val)
66#define getrext(n) ((struct jrb_node *)(n->val.v))
67#define setrext(node, value) node->val.v = (void *) (value)
68#define setred(n) n->red = 1
69#define setblack(n) n->red = 0
70#define setleft(n) n->left = 1
71#define setright(n) n->left = 0
72#define sethead(n) (n->roothead |= 2)
73#define setroot(n) (n->roothead |= 1)
74#define setint(n) n->internal = 1
75#define setext(n) n->internal = 0
76#define setnormal(n) n->roothead = 0
77#define sibling(n) ((isleft(n)) ? n->parent->blink : n->parent->flink)
78 
79static 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 
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#define mk_new_ext(new, kkkey, vvval) {\
98  new = (JRB) malloc(sizeof(struct jrb_node));\
99  new->val = vvval;\
100  new->key = kkkey;\
101  setext(new);\
102  setblack(new);\
103  setnormal(new);\
104}
105 
106static void mk_new_int(JRB l, JRB r, JRB p, int il)
107{
108  JRB newnode;
109 
110  newnode = (JRB) malloc(sizeof(struct jrb_node));
111  setint(newnode);
112  setred(newnode);
113  setnormal(newnode);
114  newnode->flink = l;
115  newnode->blink = r;
116  newnode->parent = p;
117  setlext(newnode, l);
118  setrext(newnode, r);
119  l->parent = newnode;
120  r->parent = newnode;
121  setleft(l);
122  setright(r);
123  if (ishead(p)) {
124    p->parent = newnode;
125    setroot(newnode);
126  } else if (il) {
127    setleft(newnode);
128    p->flink = newnode;
129  } else {
130    setright(newnode);
131    p->blink = newnode;
132  }
133  recolor(newnode);
134}
135  
136   
137JRB lprev(JRB n)
138{
139  if (ishead(n)) return n;
140  while (!isroot(n)) {
141    if (isright(n)) return n->parent;
142    n = n->parent;
143  }
144  return n->parent;
145}
146 
147JRB rprev(JRB n)
148{
149  if (ishead(n)) return n;
150  while (!isroot(n)) {
151    if (isleft(n)) return n->parent;
152    n = n->parent;
153  }
154  return n->parent;
155}
156 
157JRB make_jrb(void)
158{
159  JRB head;
160 
161  head = (JRB) malloc (sizeof(struct jrb_node));
162  head->flink = head;
163  head->blink = head;
164  head->parent = head;
165  head->key.s = "";
166  sethead(head);
167  return head;
168}
169 
170JRB jrb_find_gte_str(JRB n, char *key, int *fnd)
171{
172  int cmp;
173 
174  *fnd = 0;
175  if (!ishead(n)) {
176    fprintf(stderr, "jrb_find_gte_str called on non-head %p\n", n);
177    exit(1);
178  }
179  if (n->parent == n) return n;
180  cmp = strcmp(key, n->blink->key.s);
181  if (cmp == 0) {
182    *fnd = 1;
183    return n->blink;
184  }
185  if (cmp > 0) return n;
186  else n = n->parent;
187  while (1) {
188    if (isext(n)) return n;
189    cmp = strcmp(key, getlext(n)->key.s);
190    if (cmp == 0) {
191      *fnd = 1;
192      return getlext(n);
193    }
194    if (cmp < 0) n = n->flink ; else n = n->blink;
195  }
196}
197 
198JRB jrb_find_str(JRB n, char *key)
199{
200  int fnd;
201  JRB j;
202  j = jrb_find_gte_str(n, key, &fnd);
203  if (fnd) return j; else return NULL;
204}
205 
206JRB jrb_find_gte_int(JRB n, int ikey, int *fnd)
207{
208  *fnd = 0;
209  if (!ishead(n)) {
210    fprintf(stderr, "jrb_find_gte_int called on non-head %p\n", n);
211    exit(1);
212  }
213  if (n->parent == n) return n;
214  if (ikey == n->blink->key.i) {
215    *fnd = 1;
216    return n->blink;
217  }
218  if (ikey > n->blink->key.i) return n;
219  else n = n->parent;
220  while (1) {
221    if (isext(n)) return n;
222    if (ikey == getlext(n)->key.i) {
223      *fnd = 1;
224      return getlext(n);
225    }
226    n = (ikey < getlext(n)->key.i) ? n->flink : n->blink;
227  }
228}
229 
230JRB jrb_find_int(JRB n, int ikey)
231{
232  int fnd;
233  JRB j;
234
235  j = jrb_find_gte_int(n, ikey, &fnd);
236  if (fnd) return j; else return NULL;
237}
238 
239JRB jrb_find_gte_dbl(JRB n, double dkey, int *fnd)
240{
241  *fnd = 0;
242  if (!ishead(n)) {
243    fprintf(stderr, "jrb_find_gte_dbl called on non-head %p\n", n);
244    exit(1);
245  }
246  if (n->parent == n) return n;
247  if (dkey == n->blink->key.d) {
248    *fnd = 1;
249    return n->blink;
250  }
251  if (dkey > n->blink->key.d) return n;
252  else n = n->parent;
253  while (1) {
254    if (isext(n)) return n;
255    if (dkey == getlext(n)->key.d) {
256      *fnd = 1;
257      return getlext(n);
258    }
259    n = (dkey < getlext(n)->key.d) ? n->flink : n->blink;
260  }
261}
262 
263JRB jrb_find_dbl(JRB n, double dkey)
264{
265  int fnd;
266  JRB j;
267
268  j = jrb_find_gte_dbl(n, dkey, &fnd);
269  if (fnd) return j; else return NULL;
270}
271 
272JRB jrb_find_gte_gen(JRB n, Jval key,int (*fxn)(Jval, Jval), 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) return n;
282  cmp = (*fxn)(key, n->blink->key);
283  if (cmp == 0) {
284    *fnd = 1;
285    return n->blink;
286  }
287  if (cmp > 0) return n;
288  else n = n->parent;
289  while (1) {
290    if (isext(n)) return n;
291    cmp = (*fxn)(key, getlext(n)->key);
292    if (cmp == 0) {
293      *fnd = 1;
294      return getlext(n);
295    }
296    if (cmp < 0) n = n->flink ; else n = n->blink;
297  }
298}
299 
300JRB jrb_find_gen(JRB n, Jval key, int (*fxn)(Jval, Jval))
301{
302  int fnd;
303  JRB j;
304
305  j = jrb_find_gte_gen(n, key, fxn, &fnd);
306  if (fnd) return j; else return NULL;
307}
308 
309static JRB jrb_insert_b(JRB n, Jval key, Jval val)
310{
311  JRB newleft, newright, newnode, p;
312 
313  if (ishead(n)) {
314    if (n->parent == n) { /* Tree is empty */
315      mk_new_ext(newnode, key, val);
316      insert(newnode, n);
317      n->parent = newnode;
318      newnode->parent = n;
319      setroot(newnode);
320      return newnode;
321    } else {
322      mk_new_ext(newright, key, val);
323      insert(newright, n);
324      newleft = newright->blink;
325      setnormal(newleft);
326      mk_new_int(newleft, newright, newleft->parent, isleft(newleft));
327      p = rprev(newright);
328      if (!ishead(p)) setlext(p, newright);
329      return newright;
330    }
331  } else {
332    mk_new_ext(newleft, key, val);
333    insert(newleft, n);
334    setnormal(n);
335    mk_new_int(newleft, n, n->parent, isleft(n));
336    p = lprev(newleft);
337    if (!ishead(p)) setrext(p, newleft);
338    return newleft;
339  }
340}
341 
342static void recolor(JRB n)
343{
344  JRB p, gp, s;
345  int done = 0;
346 
347  while(!done) {
348    if (isroot(n)) {
349      setblack(n);
350      return;
351    }
352 
353    p = n->parent;
354 
355    if (isblack(p)) return;
356    
357    if (isroot(p)) {
358      setblack(p);
359      return;
360    }
361 
362    gp = p->parent;
363    s = sibling(p);
364    if (isred(s)) {
365      setblack(p);
366      setred(gp);
367      setblack(s);
368      n = gp;
369    } else {
370      done = 1;
371    }
372  }
373  /* p's sibling is black, p is red, gp is black */
374  
375  if ((isleft(n) == 0) == (isleft(p) == 0)) {
376    single_rotate(gp, isleft(n));
377    setblack(p);
378    setred(gp);
379  } else {
380    single_rotate(p, isleft(n));
381    single_rotate(gp, isleft(n));
382    setblack(n);
383    setred(gp);
384  }
385}
386 
387static void single_rotate(JRB y, int l)
388{
389  int rl = 0 /* for gcc */, ir;
390  JRB x, yp;
391 
392  ir = isroot(y);
393  yp = y->parent;
394  if (!ir) {
395    rl = isleft(y);
396  }
397  
398  if (l) {
399    x = y->flink;
400    y->flink = x->blink;
401    setleft(y->flink);
402    y->flink->parent = y;
403    x->blink = y;
404    setright(y);
405  } else {
406    x = y->blink;
407    y->blink = x->flink;
408    setright(y->blink);
409    y->blink->parent = y;
410    x->flink = y;
411    setleft(y);
412  }
413 
414  x->parent = yp;
415  y->parent = x;
416  if (ir) {
417    yp->parent = x;
418    setnormal(y);
419    setroot(x);
420  } else {
421    if (rl) {
422      yp->flink = x;
423      setleft(x);
424    } else {
425      yp->blink = x;
426      setright(x);
427    }
428  }
429}
430    
431void jrb_delete_node(JRB n)
432{
433  JRB s, p, gp;
434  char ir;
435 
436  if (isint(n)) {
437    fprintf(stderr, "Cannot delete an internal node: %p\n", n);
438    exit(1);
439  }
440  if (ishead(n)) {
441    fprintf(stderr, "Cannot delete the head of an jrb_tree: %p\n", n);
442    exit(1);
443  }
444  delete_item(n); /* Delete it from the list */
445  p = n->parent; /* The only node */
446  if (isroot(n)) {
447    p->parent = p;
448    free(n);
449    return;
450  }
451  s = sibling(n); /* The only node after deletion */
452  if (isroot(p)) {
453    s->parent = p->parent;
454    s->parent->parent = s;
455    setroot(s);
456    free(p);
457    free(n);
458    return;
459  }
460  gp = p->parent; /* Set parent to sibling */
461  s->parent = gp;
462  if (isleft(p)) {
463    gp->flink = s;
464    setleft(s);
465  } else {
466    gp->blink = s;
467    setright(s);
468  }
469  ir = isred(p);
470  free(p);
471  free(n);
472  
473  if (isext(s)) { /* Update proper rext and lext values */
474    p = lprev(s);
475    if (!ishead(p)) setrext(p, s);
476    p = rprev(s);
477    if (!ishead(p)) setlext(p, s);
478  } else if (isblack(s)) {
479    fprintf(stderr, "DELETION PROB -- sib is black, internal\n");
480    exit(1);
481  } else {
482    p = lprev(s);
483    if (!ishead(p)) setrext(p, s->flink);
484    p = rprev(s);
485    if (!ishead(p)) setlext(p, s->blink);
486    setblack(s);
487    return;
488  }
489 
490  if (ir) return;
491 
492  /* Recolor */
493  
494  n = s;
495  p = n->parent;
496  s = sibling(n);
497  while(isblack(p) && isblack(s) && isint(s) &&
498        isblack(s->flink) && isblack(s->blink)) {
499    setred(s);
500    n = p;
501    if (isroot(n)) return;
502    p = n->parent;
503    s = sibling(n);
504  }
505  
506  if (isblack(p) && isred(s)) { /* Rotation 2.3b */
507    single_rotate(p, isright(n));
508    setred(p);
509    setblack(s);
510    s = sibling(n);
511  }
512    
513  { JRB x, z; char il;
514    
515    if (isext(s)) {
516      fprintf(stderr, "DELETION ERROR: sibling not internal\n");
517      exit(1);
518    }
519 
520    il = isleft(n);
521    x = il ? s->flink : s->blink ;
522    z = sibling(x);
523 
524    if (isred(z)) { /* Rotation 2.3f */
525      single_rotate(p, !il);
526      setblack(z);
527      if (isred(p)) setred(s); else setblack(s);
528      setblack(p);
529    } else if (isblack(x)) { /* Recoloring only (2.3c) */
530      if (isred(s) || isblack(p)) {
531        fprintf(stderr, "DELETION ERROR: 2.3c not quite right\n");
532        exit(1);
533      }
534      setblack(p);
535      setred(s);
536      return;
537    } else if (isred(p)) { /* 2.3d */
538      single_rotate(s, il);
539      single_rotate(p, !il);
540      setblack(x);
541      setred(s);
542      return;
543    } else { /* 2.3e */
544      single_rotate(s, il);
545      single_rotate(p, !il);
546      setblack(x);
547      return;
548    }
549  }
550}
551 
552 
553void jrb_print_tree(JRB t, int level)
554{
555  int i;
556  if (ishead(t) && t->parent == t) {
557    printf("tree %p is empty\n", t);
558  } else if (ishead(t)) {
559    printf("Head: %p. Root = %p\n", t, t->parent);
560    jrb_print_tree(t->parent, 0);
561  } else {
562    if (isext(t)) {
563      for (i = 0; i < level; i++) putchar(' ');
564      printf("Ext node %p: %c,%c: p=%p, k=%s\n",
565              t, isred(t)?'R':'B', isleft(t)?'l':'r', t->parent, t->key.s);
566    } else {
567      jrb_print_tree(t->flink, level+2);
568      jrb_print_tree(t->blink, level+2);
569      for (i = 0; i < level; i++) putchar(' ');
570      printf("Int node %p: %c,%c: l=%p, r=%p, p=%p, lr=(%s,%s)\n",
571              t, isred(t)?'R':'B', isleft(t)?'l':'r', t->flink,
572              t->blink,
573              t->parent, getlext(t)->key.s, getrext(t)->key.s);
574    }
575  }
576}
577 
578void jrb_iprint_tree(JRB t, int level)
579{
580  int i;
581  if (ishead(t) && t->parent == t) {
582    printf("tree %p is empty\n", t);
583  } else if (ishead(t)) {
584    printf("Head: %p. Root = %p, < = %p, > = %p\n",
585            t, t->parent, t->blink, t->flink);
586    jrb_iprint_tree(t->parent, 0);
587  } else {
588    if (isext(t)) {
589      for (i = 0; i < level; i++) putchar(' ');
590      printf("Ext node %p: %c,%c: p=%p, <=%p, >=%p k=%d\n",
591              t, isred(t)?'R':'B', isleft(t)?'l':'r', t->parent,
592              t->blink, t->flink, t->key.i);
593    } else {
594      jrb_iprint_tree(t->flink, level+2);
595      jrb_iprint_tree(t->blink, level+2);
596      for (i = 0; i < level; i++) putchar(' ');
597      printf("Int node %p: %c,%c: l=%p, r=%p, p=%p, lr=(%d,%d)\n",
598              t, isred(t)?'R':'B', isleft(t)?'l':'r', t->flink,
599              t->blink,
600              t->parent, getlext(t)->key.i, getrext(t)->key.i);
601    }
602  }
603}
604      
605int jrb_nblack(JRB n)
606{
607  int nb;
608  if (ishead(n) || isint(n)) {
609    fprintf(stderr, "ERROR: jrb_nblack called on a non-external node %p\n", n);
610    exit(1);
611  }
612  nb = 0;
613  while(!ishead(n)) {
614    if (isblack(n)) nb++;
615    n = n->parent;
616  }
617  return nb;
618}
619 
620int jrb_plength(JRB n)
621{
622  int pl;
623  if (ishead(n) || isint(n)) {
624    fprintf(stderr, "ERROR: jrb_plength called on a non-external node %p\n", n);
625    exit(1);
626  }
627  pl = 0;
628  while(!ishead(n)) {
629    pl++;
630    n = n->parent;
631  }
632  return pl;
633}
634 
635void jrb_free_tree(JRB n)
636{
637  if (!ishead(n)) {
638    fprintf(stderr, "ERROR: Rb_free_tree called on a non-head node\n");
639    exit(1);
640  }
641 
642  while(jrb_first(n) != jrb_nil(n)) {
643    jrb_delete_node(jrb_first(n));
644  }
645  free(n);
646}
647 
648Jval jrb_val(JRB n)
649{
650  return n->val;
651}
652 
653#if 0
654static JRB jrb_insert_a(JRB nd, Jval key, Jval val)
655{
656  return jrb_insert_b(nd->flink, key, val);
657}
658#endif
659
660JRB jrb_insert_str(JRB tree, char *key, Jval val)
661{
662  Jval k;
663  int fnd;
664
665  k.s = key;
666  return jrb_insert_b(jrb_find_gte_str(tree, key, &fnd), k, val);
667}
668
669JRB jrb_insert_int(JRB tree, int ikey, Jval val)
670{
671  Jval k;
672  int fnd;
673
674  k.i = ikey;
675  return jrb_insert_b(jrb_find_gte_int(tree, ikey, &fnd), k, val);
676}
677
678JRB jrb_insert_dbl(JRB tree, double dkey, Jval val)
679{
680  Jval k;
681  int fnd;
682
683  k.d = dkey;
684  return jrb_insert_b(jrb_find_gte_dbl(tree, dkey, &fnd), k, val);
685}
686
687JRB jrb_insert_gen(JRB tree, Jval key, Jval val,
688                          int (*func)(Jval, Jval))
689{
690  int fnd;
691
692  return jrb_insert_b(jrb_find_gte_gen(tree, key, func, &fnd), key, val);
693}
694
695
696

Archive Download this file

Branches:
master



interactive