Date:2010-11-20 00:18:59 (13 years 4 months ago)
Author:Werner Almesberger
Commit:009f56c927dba844c30a628a670ac92a2ff04f19
Message:qpkg/jrb.c: major whitespace readjustment (converted from GNU to K&R style)

Files: qpkg/jrb.c (1 diff)

Change Details

qpkg/jrb.c
5151static void recolor(JRB n);
5252static void single_rotate(JRB y, int l);
5353
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))
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))
6363#define setlext(node, val) node->key = (void *) (val)
64#define getrext(n) ((struct jrb_node *)(n->val))
64#define getrext(n) ((struct jrb_node *) (n->val))
6565#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)
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)
7676
77
7778static void insert(JRB item, JRB list) /* Inserts to the end of a list */
7879{
79  JRB last_node;
80    JRB last_node;
8081
81  last_node = list->blink;
82    last_node = list->blink;
8283
83  list->blink = item;
84  last_node->flink = item;
85  item->blink = last_node;
86  item->flink = list;
84    list->blink = item;
85    last_node->flink = item;
86    item->blink = last_node;
87    item->flink = list;
8788}
89
8890
8991static void delete_item(JRB item) /* Deletes an arbitrary iterm */
9092{
91  item->flink->blink = item->blink;
92  item->blink->flink = item->flink;
93    item->flink->blink = item->blink;
94    item->blink->flink = item->flink;
9395}
9496
95#define mk_new_ext(new, kkkey, vvval) {\
96  new = (JRB) malloc(sizeof(struct jrb_node));\
97  new->val = vvval;\
98  new->key = kkkey;\
99  setext(new);\
100  setblack(new);\
101  setnormal(new);\
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); \
102104}
103105
104106static void mk_new_int(JRB l, JRB r, JRB p, int il)
105107{
106  JRB newnode;
107
108  newnode = (JRB) malloc(sizeof(struct jrb_node));
109  setint(newnode);
110  setred(newnode);
111  setnormal(newnode);
112  newnode->flink = l;
113  newnode->blink = r;
114  newnode->parent = p;
115  setlext(newnode, l);
116  setrext(newnode, r);
117  l->parent = newnode;
118  r->parent = newnode;
119  setleft(l);
120  setright(r);
121  if (ishead(p)) {
122    p->parent = newnode;
123    setroot(newnode);
124  } else if (il) {
125    setleft(newnode);
126    p->flink = newnode;
127  } else {
128    setright(newnode);
129    p->blink = newnode;
130  }
131  recolor(newnode);
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);
132134}
133135
134136
135137JRB lprev(JRB n)
136138{
137  if (ishead(n)) return n;
138  while (!isroot(n)) {
139    if (isright(n)) return n->parent;
140    n = n->parent;
141  }
142  return n->parent;
139    if (ishead(n))
140        return n;
141    while (!isroot(n)) {
142        if (isright(n))
143            return n->parent;
144        n = n->parent;
145    }
146    return n->parent;
143147}
148
144149
145150JRB rprev(JRB n)
146151{
147  if (ishead(n)) return n;
148  while (!isroot(n)) {
149    if (isleft(n)) return n->parent;
150    n = n->parent;
151  }
152  return n->parent;
152    if (ishead(n))
153        return n;
154    while (!isroot(n)) {
155        if (isleft(n))
156            return n->parent;
157        n = n->parent;
158    }
159    return n->parent;
153160}
154161
162
155163JRB make_jrb(void)
156164{
157  JRB head;
158
159  head = (JRB) malloc (sizeof(struct jrb_node));
160  head->flink = head;
161  head->blink = head;
162  head->parent = head;
163  head->key = NULL;
164  sethead(head);
165  return head;
165    JRB head;
166
167    head = (JRB) malloc(sizeof(struct jrb_node));
168    head->flink = head;
169    head->blink = head;
170    head->parent = head;
171    head->key = NULL;
172    sethead(head);
173    return head;
166174}
167175
176
168177JRB jrb_find_gte(JRB n, const void *key,
169178    int (*fxn)(const void *, const void *), int *fnd)
170179{
171  int cmp;
172
173  *fnd = 0;
174  if (!ishead(n)) {
175    fprintf(stderr, "jrb_find_gte_str called on non-head %p\n", n);
176    exit(1);
177  }
178  if (n->parent == n) return n;
179  cmp = (*fxn)(key, n->blink->key);
180  if (cmp == 0) {
181    *fnd = 1;
182    return n->blink;
183  }
184  if (cmp > 0) return n;
185  else n = n->parent;
186  while (1) {
187    if (isext(n)) return n;
188    cmp = (*fxn)(key, getlext(n)->key);
189    if (cmp == 0) {
190      *fnd = 1;
191      return getlext(n);
192    }
193    if (cmp < 0) n = n->flink ; else n = n->blink;
194  }
180    int cmp;
181
182    *fnd = 0;
183    if (!ishead(n)) {
184        fprintf(stderr, "jrb_find_gte_str called on non-head %p\n", n);
185        exit(1);
186    }
187    if (n->parent == n)
188        return n;
189    cmp = (*fxn)(key, n->blink->key);
190    if (cmp == 0) {
191        *fnd = 1;
192        return n->blink;
193    }
194    if (cmp > 0)
195        return n;
196    else
197        n = n->parent;
198    while (1) {
199        if (isext(n))
200            return n;
201        cmp = (*fxn)(key, getlext(n)->key);
202        if (cmp == 0) {
203            *fnd = 1;
204            return getlext(n);
205        }
206        if (cmp < 0)
207            n = n->flink;
208        else
209            n = n->blink;
210    }
195211}
212
196213
197214JRB jrb_find(JRB n, const void *key, int (*fxn)(const void *, const void *))
198215{
199  int fnd;
200  JRB j;
216    int fnd;
217    JRB j;
201218
202  j = jrb_find_gte(n, key, fxn, &fnd);
203  if (fnd) return j; else return NULL;
219    j = jrb_find_gte(n, key, fxn, &fnd);
220    if (fnd)
221        return j;
222    else
223        return NULL;
204224}
225
205226
206227static JRB jrb_insert_b(JRB n, void *key, void *val)
207228{
208  JRB newleft, newright, newnode, p;
209
210  if (ishead(n)) {
211    if (n->parent == n) { /* Tree is empty */
212      mk_new_ext(newnode, key, val);
213      insert(newnode, n);
214      n->parent = newnode;
215      newnode->parent = n;
216      setroot(newnode);
217      return newnode;
218    } else {
219      mk_new_ext(newright, key, val);
220      insert(newright, n);
221      newleft = newright->blink;
222      setnormal(newleft);
223      mk_new_int(newleft, newright, newleft->parent, isleft(newleft));
224      p = rprev(newright);
225      if (!ishead(p)) setlext(p, newright);
226      return newright;
227    }
228  } else {
229    mk_new_ext(newleft, key, val);
230    insert(newleft, n);
231    setnormal(n);
232    mk_new_int(newleft, n, n->parent, isleft(n));
233    p = lprev(newleft);
234    if (!ishead(p)) setrext(p, newleft);
235    return newleft;
236  }
229    JRB newleft, newright, newnode, p;
230
231    if (ishead(n)) {
232        if (n->parent == n) { /* Tree is empty */
233            mk_new_ext(newnode, key, val);
234            insert(newnode, n);
235            n->parent = newnode;
236            newnode->parent = n;
237            setroot(newnode);
238            return newnode;
239        } else {
240            mk_new_ext(newright, key, val);
241            insert(newright, n);
242            newleft = newright->blink;
243            setnormal(newleft);
244            mk_new_int(newleft, newright, newleft->parent,
245                isleft(newleft));
246            p = rprev(newright);
247            if (!ishead(p))
248                setlext(p, newright);
249            return newright;
250        }
251    } else {
252        mk_new_ext(newleft, key, val);
253        insert(newleft, n);
254        setnormal(n);
255        mk_new_int(newleft, n, n->parent, isleft(n));
256        p = lprev(newleft);
257        if (!ishead(p))
258            setrext(p, newleft);
259        return newleft;
260    }
237261}
262
238263
239264static void recolor(JRB n)
240265{
241  JRB p, gp, s;
242  int done = 0;
266    JRB p, gp, s;
267    int done = 0;
243268
244  while(!done) {
245    if (isroot(n)) {
246      setblack(n);
247      return;
248    }
269    while(!done) {
270        if (isroot(n)) {
271            setblack(n);
272            return;
273        }
249274
250    p = n->parent;
275        p = n->parent;
251276
252    if (isblack(p)) return;
277        if (isblack(p))
278            return;
253279
254    if (isroot(p)) {
255      setblack(p);
256      return;
257    }
258
259    gp = p->parent;
260    s = sibling(p);
261    if (isred(s)) {
262      setblack(p);
263      setred(gp);
264      setblack(s);
265      n = gp;
266    } else {
267      done = 1;
268    }
269  }
270  /* p's sibling is black, p is red, gp is black */
280        if (isroot(p)) {
281            setblack(p);
282            return;
283        }
284
285        gp = p->parent;
286        s = sibling(p);
287        if (isred(s)) {
288            setblack(p);
289            setred(gp);
290            setblack(s);
291            n = gp;
292        } else {
293            done = 1;
294        }
295    }
296    /* p's sibling is black, p is red, gp is black */
271297
272  if ((isleft(n) == 0) == (isleft(p) == 0)) {
273    single_rotate(gp, isleft(n));
274    setblack(p);
275    setred(gp);
276  } else {
277    single_rotate(p, isleft(n));
278    single_rotate(gp, isleft(n));
279    setblack(n);
280    setred(gp);
281  }
298    if ((isleft(n) == 0) == (isleft(p) == 0)) {
299        single_rotate(gp, isleft(n));
300        setblack(p);
301        setred(gp);
302    } else {
303        single_rotate(p, isleft(n));
304        single_rotate(gp, isleft(n));
305        setblack(n);
306        setred(gp);
307    }
282308}
309
283310
284311static void single_rotate(JRB y, int l)
285312{
286  int rl = 0 /* for gcc */, ir;
287  JRB x, yp;
288
289  ir = isroot(y);
290  yp = y->parent;
291  if (!ir) {
292    rl = isleft(y);
293  }
313    int rl = 0 /* for gcc */, ir;
314    JRB x, yp;
315
316    ir = isroot(y);
317    yp = y->parent;
318    if (!ir)
319        rl = isleft(y);
294320
295  if (l) {
296    x = y->flink;
297    y->flink = x->blink;
298    setleft(y->flink);
299    y->flink->parent = y;
300    x->blink = y;
301    setright(y);
302  } else {
303    x = y->blink;
304    y->blink = x->flink;
305    setright(y->blink);
306    y->blink->parent = y;
307    x->flink = y;
308    setleft(y);
309  }
310
311  x->parent = yp;
312  y->parent = x;
313  if (ir) {
314    yp->parent = x;
315    setnormal(y);
316    setroot(x);
317  } else {
318    if (rl) {
319      yp->flink = x;
320      setleft(x);
321    } else {
322      yp->blink = x;
323      setright(x);
324    }
325  }
321     if (l) {
322        x = y->flink;
323        y->flink = x->blink;
324        setleft(y->flink);
325        y->flink->parent = y;
326        x->blink = y;
327        setright(y);
328    } else {
329        x = y->blink;
330        y->blink = x->flink;
331        setright(y->blink);
332        y->blink->parent = y;
333        x->flink = y;
334        setleft(y);
335    }
336
337    x->parent = yp;
338    y->parent = x;
339    if (ir) {
340        yp->parent = x;
341        setnormal(y);
342        setroot(x);
343    } else {
344        if (rl) {
345            yp->flink = x;
346            setleft(x);
347        } else {
348            yp->blink = x;
349            setright(x);
350        }
351    }
326352}
327
353
354
328355void jrb_delete_node(JRB n)
329356{
330  JRB s, p, gp;
331  char ir;
332
333  if (isint(n)) {
334    fprintf(stderr, "Cannot delete an internal node: %p\n", n);
335    exit(1);
336  }
337  if (ishead(n)) {
338    fprintf(stderr, "Cannot delete the head of an jrb_tree: %p\n", n);
339    exit(1);
340  }
341  delete_item(n); /* Delete it from the list */
342  p = n->parent; /* The only node */
343  if (isroot(n)) {
344    p->parent = p;
345    free(n);
346    return;
347  }
348  s = sibling(n); /* The only node after deletion */
349  if (isroot(p)) {
350    s->parent = p->parent;
351    s->parent->parent = s;
352    setroot(s);
353    free(p);
354    free(n);
355    return;
356  }
357  gp = p->parent; /* Set parent to sibling */
358  s->parent = gp;
359  if (isleft(p)) {
360    gp->flink = s;
361    setleft(s);
362  } else {
363    gp->blink = s;
364    setright(s);
365  }
366  ir = isred(p);
367  free(p);
368  free(n);
357    JRB s, p, gp;
358    char ir;
359
360    if (isint(n)) {
361        fprintf(stderr, "Cannot delete an internal node: %p\n", n);
362        exit(1);
363    }
364    if (ishead(n)) {
365        fprintf(stderr,
366            "Cannot delete the head of an jrb_tree: %p\n", n);
367        exit(1);
368    }
369    delete_item(n); /* Delete it from the list */
370    p = n->parent; /* The only node */
371    if (isroot(n)) {
372        p->parent = p;
373        free(n);
374        return;
375    }
376    s = sibling(n); /* The only node after deletion */
377    if (isroot(p)) {
378        s->parent = p->parent;
379        s->parent->parent = s;
380        setroot(s);
381        free(p);
382        free(n);
383        return;
384    }
385    gp = p->parent; /* Set parent to sibling */
386    s->parent = gp;
387    if (isleft(p)) {
388        gp->flink = s;
389        setleft(s);
390    } else {
391        gp->blink = s;
392        setright(s);
393    }
394    ir = isred(p);
395    free(p);
396    free(n);
369397
370  if (isext(s)) { /* Update proper rext and lext values */
371    p = lprev(s);
372    if (!ishead(p)) setrext(p, s);
373    p = rprev(s);
374    if (!ishead(p)) setlext(p, s);
375  } else if (isblack(s)) {
376    fprintf(stderr, "DELETION PROB -- sib is black, internal\n");
377    exit(1);
378  } else {
379    p = lprev(s);
380    if (!ishead(p)) setrext(p, s->flink);
381    p = rprev(s);
382    if (!ishead(p)) setlext(p, s->blink);
383    setblack(s);
384    return;
385  }
386
387  if (ir) return;
388
389  /* Recolor */
398    if (isext(s)) { /* Update proper rext and lext values */
399        p = lprev(s);
400        if (!ishead(p))
401            setrext(p, s);
402        p = rprev(s);
403        if (!ishead(p))
404            setlext(p, s);
405    } else if (isblack(s)) {
406        fprintf(stderr, "DELETION PROB -- sib is black, internal\n");
407        exit(1);
408    } else {
409        p = lprev(s);
410        if (!ishead(p))
411            setrext(p, s->flink);
412        p = rprev(s);
413        if (!ishead(p))
414            setlext(p, s->blink);
415        setblack(s);
416        return;
417    }
418
419    if (ir)
420        return;
421
422    /* Recolor */
390423
391  n = s;
392  p = n->parent;
393  s = sibling(n);
394  while(isblack(p) && isblack(s) && isint(s) &&
395        isblack(s->flink) && isblack(s->blink)) {
396    setred(s);
397    n = p;
398    if (isroot(n)) return;
399    p = n->parent;
400    s = sibling(n);
401  }
424    n = s;
425    p = n->parent;
426    s = sibling(n);
427    while(isblack(p) && isblack(s) && isint(s) &&
428        isblack(s->flink) && isblack(s->blink)) {
429        setred(s);
430        n = p;
431        if (isroot(n))
432            return;
433        p = n->parent;
434        s = sibling(n);
435    }
402436
403  if (isblack(p) && isred(s)) { /* Rotation 2.3b */
404    single_rotate(p, isright(n));
405    setred(p);
406    setblack(s);
407    s = sibling(n);
408  }
437    if (isblack(p) && isred(s)) { /* Rotation 2.3b */
438        single_rotate(p, isright(n));
439        setred(p);
440        setblack(s);
441        s = sibling(n);
442    }
409443
410  { JRB x, z; char il;
444    {
445        JRB x, z; char il;
411446
412    if (isext(s)) {
413      fprintf(stderr, "DELETION ERROR: sibling not internal\n");
414      exit(1);
415    }
416
417    il = isleft(n);
418    x = il ? s->flink : s->blink ;
419    z = sibling(x);
420
421    if (isred(z)) { /* Rotation 2.3f */
422      single_rotate(p, !il);
423      setblack(z);
424      if (isred(p)) setred(s); else setblack(s);
425      setblack(p);
426    } else if (isblack(x)) { /* Recoloring only (2.3c) */
427      if (isred(s) || isblack(p)) {
428        fprintf(stderr, "DELETION ERROR: 2.3c not quite right\n");
429        exit(1);
430      }
431      setblack(p);
432      setred(s);
433      return;
434    } else if (isred(p)) { /* 2.3d */
435      single_rotate(s, il);
436      single_rotate(p, !il);
437      setblack(x);
438      setred(s);
439      return;
440    } else { /* 2.3e */
441      single_rotate(s, il);
442      single_rotate(p, !il);
443      setblack(x);
444      return;
445    }
446  }
447        if (isext(s)) {
448            fprintf(stderr,
449                "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        } else 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        } else if (isred(p)) { /* 2.3d */
475            single_rotate(s, il);
476            single_rotate(p, !il);
477            setblack(x);
478            setred(s);
479            return;
480        } else { /* 2.3e */
481            single_rotate(s, il);
482            single_rotate(p, !il);
483            setblack(x);
484            return;
485        }
486    }
447487}
488
448489
449490int jrb_nblack(JRB n)
450491{
451  int nb;
452  if (ishead(n) || isint(n)) {
453    fprintf(stderr, "ERROR: jrb_nblack called on a non-external node %p\n", n);
454    exit(1);
455  }
456  nb = 0;
457  while(!ishead(n)) {
458    if (isblack(n)) nb++;
459    n = n->parent;
460  }
461  return nb;
492    int nb;
493
494    if (ishead(n) || isint(n)) {
495        fprintf(stderr,
496            "ERROR: jrb_nblack called on a non-external node %p\n", n);
497        exit(1);
498    }
499    nb = 0;
500    while(!ishead(n)) {
501        if (isblack(n)) nb++;
502        n = n->parent;
503    }
504    return nb;
462505}
506
463507
464508int jrb_plength(JRB n)
465509{
466  int pl;
467  if (ishead(n) || isint(n)) {
468    fprintf(stderr, "ERROR: jrb_plength called on a non-external node %p\n", n);
469    exit(1);
470  }
471  pl = 0;
472  while(!ishead(n)) {
473    pl++;
474    n = n->parent;
475  }
476  return pl;
510    int pl;
511
512    if (ishead(n) || isint(n)) {
513        fprintf(stderr,
514            "ERROR: jrb_plength called on a non-external node %p\n", n);
515        exit(1);
516    }
517    pl = 0;
518    while (!ishead(n)) {
519        pl++;
520        n = n->parent;
521    }
522    return pl;
477523}
524
478525
479526void jrb_free_tree(JRB n)
480527{
481  if (!ishead(n)) {
482    fprintf(stderr, "ERROR: Rb_free_tree called on a non-head node\n");
483    exit(1);
484  }
485
486  while(jrb_first(n) != jrb_nil(n)) {
487    jrb_delete_node(jrb_first(n));
488  }
489  free(n);
528    if (!ishead(n)) {
529        fprintf(stderr,
530            "ERROR: Rb_free_tree called on a non-head node\n");
531        exit(1);
532    }
533
534    while(jrb_first(n) != jrb_nil(n))
535        jrb_delete_node(jrb_first(n));
536
537    free(n);
490538}
539
491540
492541void *jrb_val(JRB n)
493542{
494  return n->val;
543    return n->val;
495544}
545
496546
497547JRB jrb_insert(JRB tree, void *key, void *val,
498                          int (*func)(const void *, const void *))
548                          int (*func)(const void *a, const void *b))
499549{
500  int fnd;
550    int fnd;
501551
502  return jrb_insert_b(jrb_find_gte(tree, key, func, &fnd), key, val);
552    return jrb_insert_b(jrb_find_gte(tree, key, func, &fnd), key, val);
503553}

Archive Download the corresponding diff file

Branches:
master



interactive