afsmonitor: avoid double free on exit
[openafs.git] / src / mcas / rb_lock_mutex.c
1 /******************************************************************************
2  * rb_lock_mutex.c
3  *
4  * Lock-based red-black trees, based on Hanke's relaxed balancing operations.
5  *
6  * For more details on the local tree restructuring operations used here:
7  *  S. Hanke, T. Ottmann, and E. Soisalon-Soininen.
8  *  "Relaxed balanced red-black trees".
9  *  3rd Italian Conference on Algorithms and Complexity, pages 193-204.
10  *
11  * Rather than issuing up-in and up-out requests to a balancing process,
12  * each operation is directly responsible for local rebalancing. However,
13  * this process can be split into a number of individual restructuring
14  * operations, and locks can be released between each operation. Between
15  * operations, we mark the node concerned as UNBALANCED -- contending
16  * updates will then wait for this mark to be removed before continuing.
17  *
18  * Copyright (c) 2002-2003, K A Fraser
19
20 Redistribution and use in source and binary forms, with or without
21 modification, are permitted provided that the following conditions are
22 met:
23
24     * Redistributions of source code must retain the above copyright
25     * notice, this list of conditions and the following disclaimer.
26     * Redistributions in binary form must reproduce the above
27     * copyright notice, this list of conditions and the following
28     * disclaimer in the documentation and/or other materials provided
29     * with the distribution.  Neither the name of the Keir Fraser
30     * nor the names of its contributors may be used to endorse or
31     * promote products derived from this software without specific
32     * prior written permission.
33
34 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
35 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
36 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
37 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
38 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
39 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
40 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
41 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
42 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
43 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
44 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
45  */
46
47 #define __SET_IMPLEMENTATION__
48
49 #include <stdio.h>
50 #include <assert.h>
51 #include <stdlib.h>
52 #include <unistd.h>
53 #include "portable_defns.h"
54 #include "gc.h"
55 #include "set.h"
56
57 #define BLACK_MARK      0
58 #define RED_MARK        1
59 #define UNBALANCED_MARK 2
60
61 #define SET_VALUE(_v,_n)  \
62     ((_v) = ((setval_t)(((unsigned long)(_v)&3)|((unsigned long)(_n)))))
63 #define GET_VALUE(_v)     ((setval_t)((int_addr_t)(_v) & ~3UL))
64 #define GET_COLOUR(_v)    ((int_addr_t)(_v) & 1)
65 #define SET_COLOUR(_v,_c) \
66     ((setval_t)(((unsigned long)(_v)&~1UL)|(unsigned long)(_c)))
67
68 #define IS_BLACK(_v)      (GET_COLOUR(_v) == 0)
69 #define IS_RED(_v)        (GET_COLOUR(_v) == 1)
70 #define IS_UNBALANCED(_v) (((int_addr_t)(_v) & 2) == 2)
71
72 #define MK_BLACK(_v)      ((setval_t)(((int_addr_t)(_v)&~1UL) | 0))
73 #define MK_RED(_v)        ((setval_t)(((int_addr_t)(_v)&~1UL) | 1))
74 #define MK_BALANCED(_v)   ((setval_t)(((int_addr_t)(_v)&~2UL) | 0))
75 #define MK_UNBALANCED(_v) ((setval_t)(((int_addr_t)(_v)&~2UL) | 2))
76
77 #define GARBAGE_VALUE     ((setval_t)4)
78 #define IS_GARBAGE(_n)    (GET_VALUE((_n)->v) == GARBAGE_VALUE)
79 #define MK_GARBAGE(_n)    (SET_VALUE((_n)->v, GARBAGE_VALUE))
80
81 #define INTERNAL_VALUE ((void *)0xdeadbee0)
82
83 #define IS_ROOT(_n) ((_n)->p->k == 0)
84 #define IS_LEAF(_n) ((_n)->l == NULL)
85
86 /* TRUE if node X is a child of P. */
87 #define ADJACENT(_p,_x) (((_p)->l==(_x))||((_p)->r==(_x)))
88
89 typedef struct node_st node_t;
90 typedef struct set_st set_t;
91
92 struct node_st
93 {
94     setkey_t k;
95     setval_t v;
96     node_t *l, *r, *p;
97     mcs_lock_t lock;
98 };
99
100 struct set_st
101 {
102     node_t root;
103     node_t null;
104     node_t dummy_g, dummy_gg;
105 };
106
107 static int gc_id;
108
109 /* Nodes p, x, y must be locked. */
110 static void left_rotate(ptst_t *ptst, node_t *x)
111 {
112     node_t *y = x->r, *p = x->p, *nx;
113
114     nx    = gc_alloc(ptst, gc_id);
115     nx->p = y;
116     nx->l = x->l;
117     nx->r = y->l;
118     nx->k = x->k;
119     nx->v = x->v;
120     mcs_init(&nx->lock);
121
122     WMB();
123
124     y->p    = p;
125     x->l->p = nx;
126     y->l->p = nx;
127     y->l    = nx;
128     if ( x == p->l ) p->l = y; else p->r = y;
129
130     MK_GARBAGE(x);
131     gc_free(ptst, x, gc_id);
132 }
133
134
135 /* Nodes p, x, y must be locked. */
136 static void right_rotate(ptst_t *ptst, node_t *x)
137 {
138     node_t *y = x->l, *p = x->p, *nx;
139
140     nx    = gc_alloc(ptst, gc_id);
141     nx->p = y;
142     nx->l = y->r;
143     nx->r = x->r;
144     nx->k = x->k;
145     nx->v = x->v;
146     mcs_init(&nx->lock);
147
148     WMB();
149
150     y->p    = p;
151     x->r->p = nx;
152     y->r->p = nx;
153     y->r    = nx;
154     if ( x == p->l ) p->l = y; else p->r = y;
155
156     MK_GARBAGE(x);
157     gc_free(ptst, x, gc_id);
158 }
159
160
161 static void fix_unbalance_up(ptst_t *ptst, node_t *x)
162 {
163     qnode_t x_qn, g_qn, p_qn, w_qn, gg_qn;
164     node_t *g, *p, *w, *gg;
165     int done = 0;
166
167     do {
168         assert(IS_UNBALANCED(x->v));
169         if ( IS_GARBAGE(x) ) return;
170
171         p  = x->p;
172         g  = p->p;
173         gg = g->p;
174
175         mcs_lock(&gg->lock, &gg_qn);
176         if ( !ADJACENT(gg, g) || IS_UNBALANCED(gg->v) || IS_GARBAGE(gg) )
177             goto unlock_gg;
178
179         mcs_lock(&g->lock, &g_qn);
180         if ( !ADJACENT(g, p) || IS_UNBALANCED(g->v) ) goto unlock_ggg;
181
182         mcs_lock(&p->lock, &p_qn);
183         if ( !ADJACENT(p, x) || IS_UNBALANCED(p->v) ) goto unlock_pggg;
184
185         mcs_lock(&x->lock, &x_qn);
186
187         assert(IS_RED(x->v));
188         assert(IS_UNBALANCED(x->v));
189
190         if ( IS_BLACK(p->v) )
191         {
192             /* Case 1. Nothing to do. */
193             x->v = MK_BALANCED(x->v);
194             done = 1;
195             goto unlock_xpggg;
196         }
197
198         if ( IS_ROOT(x) )
199         {
200             /* Case 2. */
201             x->v = MK_BLACK(MK_BALANCED(x->v));
202             done = 1;
203             goto unlock_xpggg;
204         }
205
206         if ( IS_ROOT(p) )
207         {
208             /* Case 2. */
209             p->v = MK_BLACK(p->v);
210             x->v = MK_BALANCED(x->v);
211             done = 1;
212             goto unlock_xpggg;
213         }
214
215         if ( g->l == p ) w = g->r; else w = g->l;
216         mcs_lock(&w->lock, &w_qn);
217
218         if ( IS_RED(w->v) )
219         {
220             /* Case 5. */
221             /* In all other cases, doesn't change colour or subtrees. */
222             if ( IS_UNBALANCED(w->v) ) goto unlock_wxpggg;
223             g->v = MK_UNBALANCED(MK_RED(g->v));
224             p->v = MK_BLACK(p->v);
225             w->v = MK_BLACK(w->v);
226             x->v = MK_BALANCED(x->v);
227             done = 2;
228             goto unlock_wxpggg;
229         }
230
231         /* Cases 3 & 4. Both of these need the great-grandfather locked. */
232         if ( p == g->l )
233         {
234             if ( x == p->l )
235             {
236                 /* Case 3. Single rotation. */
237                 x->v = MK_BALANCED(x->v);
238                 p->v = MK_BLACK(p->v);
239                 g->v = MK_RED(g->v);
240                 right_rotate(ptst, g);
241             }
242             else
243             {
244                 /* Case 4. Double rotation. */
245                 x->v = MK_BALANCED(MK_BLACK(x->v));
246                 g->v = MK_RED(g->v);
247                 left_rotate(ptst, p);
248                 right_rotate(ptst, g);
249             }
250         }
251         else /* SYMMETRIC CASE */
252         {
253             if ( x == p->r )
254             {
255                 /* Case 3. Single rotation. */
256                 x->v = MK_BALANCED(x->v);
257                 p->v = MK_BLACK(p->v);
258                 g->v = MK_RED(g->v);
259                 left_rotate(ptst, g);
260             }
261             else
262             {
263                 /* Case 4. Double rotation. */
264                 x->v = MK_BALANCED(MK_BLACK(x->v));
265                 g->v = MK_RED(g->v);
266                 right_rotate(ptst, p);
267                 left_rotate(ptst, g);
268             }
269         }
270
271         done = 1;
272
273     unlock_wxpggg:
274         mcs_unlock(&w->lock, &w_qn);
275     unlock_xpggg:
276         mcs_unlock(&x->lock, &x_qn);
277     unlock_pggg:
278         mcs_unlock(&p->lock, &p_qn);
279     unlock_ggg:
280         mcs_unlock(&g->lock, &g_qn);
281     unlock_gg:
282         mcs_unlock(&gg->lock, &gg_qn);
283
284         if ( done == 2 )
285         {
286             x = g;
287             done = 0;
288         }
289     }
290     while ( !done );
291 }
292
293
294 static void fix_unbalance_down(ptst_t *ptst, node_t *x)
295 {
296     /* WN == W_NEAR, WF == W_FAR (W_FAR is further, in key space, from X). */
297     qnode_t x_qn, w_qn, p_qn, g_qn, wn_qn, wf_qn;
298     node_t *w, *p, *g, *wn, *wf;
299     int done = 0;
300
301     do {
302         if ( !IS_UNBALANCED(x->v) || IS_GARBAGE(x) ) return;
303
304         p = x->p;
305         g = p->p;
306
307         mcs_lock(&g->lock, &g_qn);
308         if ( !ADJACENT(g, p) || IS_UNBALANCED(g->v) || IS_GARBAGE(g) )
309             goto unlock_g;
310
311         mcs_lock(&p->lock, &p_qn);
312         if ( !ADJACENT(p, x) || IS_UNBALANCED(p->v) ) goto unlock_pg;
313
314         mcs_lock(&x->lock, &x_qn);
315
316         if ( !IS_BLACK(x->v) || !IS_UNBALANCED(x->v) )
317         {
318             done = 1;
319             goto unlock_xpg;
320         }
321
322         if ( IS_ROOT(x) )
323         {
324             x->v = MK_BALANCED(x->v);
325             done = 1;
326             goto unlock_xpg;
327         }
328
329         w = (x == p->l) ? p->r : p->l;
330         mcs_lock(&w->lock, &w_qn);
331         if ( IS_UNBALANCED(w->v) )
332         {
333             if ( IS_BLACK(w->v) )
334             {
335                 /* Funky relaxed rules to the rescue. */
336                 x->v = MK_BALANCED(x->v);
337                 w->v = MK_BALANCED(w->v);
338                 if ( IS_BLACK(p->v) )
339                 {
340                     p->v = MK_UNBALANCED(p->v);
341                     done = 2;
342                 }
343                 else
344                 {
345                     p->v = MK_BLACK(p->v);
346                     done = 1;
347                 }
348             }
349             goto unlock_wxpg;
350         }
351
352         assert(!IS_LEAF(w));
353
354         if ( x == p->l )
355         {
356             wn = w->l;
357             wf = w->r;
358         }
359         else
360         {
361             wn = w->r;
362             wf = w->l;
363         }
364
365         mcs_lock(&wn->lock, &wn_qn);
366         /* Hanke has an extra relaxed transform here. It's not needed. */
367         if ( IS_UNBALANCED(wn->v) ) goto unlock_wnwxpg;
368
369         mcs_lock(&wf->lock, &wf_qn);
370         if ( IS_UNBALANCED(wf->v) ) goto unlock_wfwnwxpg;
371
372         if ( IS_RED(w->v) )
373         {
374             /* Case 1. Rotate at parent. */
375             assert(IS_BLACK(p->v) && IS_BLACK(wn->v) && IS_BLACK(wf->v));
376             w->v = MK_BLACK(w->v);
377             p->v = MK_RED(p->v);
378             if ( x == p->l ) left_rotate(ptst, p); else right_rotate(ptst, p);
379             goto unlock_wfwnwxpg;
380         }
381
382         if ( IS_BLACK(wn->v) && IS_BLACK(wf->v) )
383         {
384             if ( IS_RED(p->v) )
385             {
386                 /* Case 2. Simple recolouring. */
387                 p->v = MK_BLACK(p->v);
388                 done = 1;
389             }
390             else
391             {
392                 /* Case 5. Simple recolouring. */
393                 p->v = MK_UNBALANCED(p->v);
394                 done = 2;
395             }
396             w->v = MK_RED(w->v);
397             x->v = MK_BALANCED(x->v);
398             goto unlock_wfwnwxpg;
399         }
400
401         if ( x == p->l )
402         {
403             if ( IS_RED(wf->v) )
404             {
405                 /* Case 3. Single rotation. */
406                 wf->v = MK_BLACK(wf->v);
407                 w->v = SET_COLOUR(w->v, GET_COLOUR(p->v));
408                 p->v = MK_BLACK(p->v);
409                 x->v = MK_BALANCED(x->v);
410                 left_rotate(ptst, p);
411             }
412             else
413             {
414                 /* Case 4. Double rotation. */
415                 assert(IS_RED(wn->v));
416                 wn->v = SET_COLOUR(wn->v, GET_COLOUR(p->v));
417                 p->v = MK_BLACK(p->v);
418                 x->v = MK_BALANCED(x->v);
419                 right_rotate(ptst, w);
420                 left_rotate(ptst, p);
421             }
422         }
423         else /* SYMMETRIC CASE: X == P->R  */
424         {
425             if ( IS_RED(wf->v) )
426             {
427                 /* Case 3. Single rotation. */
428                 wf->v = MK_BLACK(wf->v);
429                 w->v = SET_COLOUR(w->v, GET_COLOUR(p->v));
430                 p->v = MK_BLACK(p->v);
431                 x->v = MK_BALANCED(x->v);
432                 right_rotate(ptst, p);
433             }
434             else
435             {
436                 /* Case 4. Double rotation. */
437                 assert(IS_RED(wn->v));
438                 wn->v = SET_COLOUR(wn->v, GET_COLOUR(p->v));
439                 p->v = MK_BLACK(p->v);
440                 x->v = MK_BALANCED(x->v);
441                 left_rotate(ptst, w);
442                 right_rotate(ptst, p);
443             }
444         }
445
446         done = 1;
447
448     unlock_wfwnwxpg:
449         mcs_unlock(&wf->lock, &wf_qn);
450     unlock_wnwxpg:
451         mcs_unlock(&wn->lock, &wn_qn);
452     unlock_wxpg:
453         mcs_unlock(&w->lock, &w_qn);
454     unlock_xpg:
455         mcs_unlock(&x->lock, &x_qn);
456     unlock_pg:
457         mcs_unlock(&p->lock, &p_qn);
458     unlock_g:
459         mcs_unlock(&g->lock, &g_qn);
460
461         if ( done == 2 )
462         {
463             x = p;
464             done = 0;
465         }
466     }
467     while ( !done );
468 }
469
470
471 static void delete_finish(ptst_t *ptst, node_t *x)
472 {
473     qnode_t g_qn, p_qn, w_qn, x_qn;
474     node_t *g, *p, *w;
475     int done = 0;
476
477     do {
478         if ( IS_GARBAGE(x) ) return;
479
480         p = x->p;
481         g = p->p;
482
483         mcs_lock(&g->lock, &g_qn);
484         if ( !ADJACENT(g, p) || IS_UNBALANCED(g->v) || IS_GARBAGE(g) )
485             goto unlock_g;
486
487         mcs_lock(&p->lock, &p_qn);
488         /* Removing unbalanced red nodes is okay. */
489         if ( !ADJACENT(p, x) || (IS_UNBALANCED(p->v) && IS_BLACK(p->v)) )
490             goto unlock_pg;
491
492         mcs_lock(&x->lock, &x_qn);
493         if ( IS_UNBALANCED(x->v) ) goto unlock_xpg;
494         if ( GET_VALUE(x->v) != NULL )
495         {
496             done = 1;
497             goto unlock_xpg;
498         }
499
500         if ( p->l == x ) w = p->r; else w = p->l;
501         assert(w != x);
502         mcs_lock(&w->lock, &w_qn);
503         if ( IS_UNBALANCED(w->v) ) goto unlock_wxpg;
504
505         if ( g->l == p ) g->l = w; else g->r = w;
506         MK_GARBAGE(p); gc_free(ptst, p, gc_id);
507         MK_GARBAGE(x); gc_free(ptst, x, gc_id);
508         w->p = g;
509         if ( IS_BLACK(p->v) && IS_BLACK(w->v) )
510         {
511             w->v = MK_UNBALANCED(w->v);
512             done = 2;
513         }
514         else
515         {
516             w->v = MK_BLACK(w->v);
517             done = 1;
518         }
519
520     unlock_wxpg:
521         mcs_unlock(&w->lock, &w_qn);
522     unlock_xpg:
523         mcs_unlock(&x->lock, &x_qn);
524     unlock_pg:
525         mcs_unlock(&p->lock, &p_qn);
526     unlock_g:
527         mcs_unlock(&g->lock, &g_qn);
528     }
529     while ( !done );
530
531     if ( done == 2 ) fix_unbalance_down(ptst, w);
532 }
533
534
535 set_t *set_alloc(void)
536 {
537     ptst_t *ptst;
538     set_t  *set;
539     node_t *root, *null;
540
541     ptst = critical_enter();
542
543     set = (set_t *)malloc(sizeof(*set));
544     memset(set, 0, sizeof(*set));
545
546     root = &set->root;
547     null = &set->null;
548
549     root->k = 0;
550     root->v = MK_RED(INTERNAL_VALUE);
551     root->l = NULL;
552     root->r = null;
553     root->p = NULL;
554     mcs_init(&root->lock);
555
556     null->k = SENTINEL_KEYMIN;
557     null->v = MK_BLACK(INTERNAL_VALUE);
558     null->l = NULL;
559     null->r = NULL;
560     null->p = root;
561     mcs_init(&null->lock);
562
563     set->dummy_gg.l = &set->dummy_g;
564     set->dummy_g.p  = &set->dummy_gg;
565     set->dummy_g.l  = &set->root;
566     set->root.p     = &set->dummy_g;
567
568     critical_exit(ptst);
569
570     return set;
571 }
572
573
574 setval_t set_update(set_t *s, setkey_t k, setval_t v, int overwrite)
575 {
576     ptst_t  *ptst;
577     qnode_t  y_qn, z_qn;
578     node_t  *y, *z, *new_internal, *new_leaf;
579     int      fix_up = 0;
580     setval_t ov = NULL;
581
582     k = CALLER_TO_INTERNAL_KEY(k);
583
584     ptst = critical_enter();
585
586  retry:
587     z = &s->root;
588     while ( (y = (k <= z->k) ? z->l : z->r) != NULL )
589         z = y;
590
591     y = z->p;
592     mcs_lock(&y->lock, &y_qn);
593     if ( (((k <= y->k) ? y->l : y->r) != z) || IS_GARBAGE(y) )
594     {
595         mcs_unlock(&y->lock, &y_qn);
596         goto retry;
597     }
598
599     mcs_lock(&z->lock, &z_qn);
600     assert(!IS_GARBAGE(z) && IS_LEAF(z));
601
602     if ( z->k == k )
603     {
604         ov = GET_VALUE(z->v);
605         if ( overwrite || (ov == NULL) )
606             SET_VALUE(z->v, v);
607     }
608     else
609     {
610         new_leaf     = gc_alloc(ptst, gc_id);
611         new_internal = gc_alloc(ptst, gc_id);
612         new_leaf->k = k;
613         new_leaf->v = MK_BLACK(v);
614         new_leaf->l = NULL;
615         new_leaf->r = NULL;
616
617         new_leaf->p = new_internal;
618         mcs_init(&new_leaf->lock);
619         if ( z->k < k )
620         {
621             new_internal->k = z->k;
622             new_internal->l = z;
623             new_internal->r = new_leaf;
624         }
625         else
626         {
627             new_internal->k = k;
628             new_internal->l = new_leaf;
629             new_internal->r = z;
630         }
631         new_internal->p = y;
632         mcs_init(&new_internal->lock);
633
634         if ( IS_UNBALANCED(z->v) )
635         {
636             z->v = MK_BALANCED(z->v);
637             new_internal->v = MK_BLACK(INTERNAL_VALUE);
638         }
639         else if ( IS_RED(y->v) )
640         {
641             new_internal->v = MK_UNBALANCED(MK_RED(INTERNAL_VALUE));
642             fix_up = 1;
643         }
644         else
645         {
646             new_internal->v = MK_RED(INTERNAL_VALUE);
647         }
648
649         WMB();
650
651         z->p = new_internal;
652         if ( y->l == z ) y->l = new_internal; else y->r = new_internal;
653     }
654
655     mcs_unlock(&y->lock, &y_qn);
656     mcs_unlock(&z->lock, &z_qn);
657
658     if ( fix_up )
659         fix_unbalance_up(ptst, new_internal);
660
661  out:
662     critical_exit(ptst);
663
664     return ov;
665 }
666
667
668 setval_t set_remove(set_t *s, setkey_t k)
669 {
670     ptst_t  *ptst;
671     node_t  *y, *z;
672     qnode_t  z_qn;
673     setval_t ov = NULL;
674
675     k = CALLER_TO_INTERNAL_KEY(k);
676
677     ptst = critical_enter();
678
679     z = &s->root;
680     while ( (y = (k <= z->k) ? z->l : z->r) != NULL )
681         z = y;
682
683     if ( z->k == k )
684     {
685         mcs_lock(&z->lock, &z_qn);
686         if ( !IS_GARBAGE(z) )
687         {
688             ov = GET_VALUE(z->v);
689
690             SET_VALUE(z->v, NULL);
691         }
692         mcs_unlock(&z->lock, &z_qn);
693     }
694
695     if ( ov != NULL )
696         delete_finish(ptst, z);
697
698     critical_exit(ptst);
699
700     return ov;
701 }
702
703
704 setval_t set_lookup(set_t *s, setkey_t k)
705 {
706     ptst_t  *ptst;
707     node_t  *m, *n;
708     setval_t v;
709
710     k = CALLER_TO_INTERNAL_KEY(k);
711
712     ptst = critical_enter();
713
714     n = &s->root;
715     while ( (m = (k <= n->k) ? n->l : n->r) != NULL )
716         n = m;
717
718     v = (k == n->k) ? GET_VALUE(n->v) : NULL;
719     if ( v == GARBAGE_VALUE ) v = NULL;
720
721     critical_exit(ptst);
722
723     return v;
724 }
725
726
727 void _init_set_subsystem(void)
728 {
729     gc_id = gc_add_allocator(sizeof(node_t));
730 }
731
732 #if 0
733 static int valll=0, bug=0, nrb=-1;
734 static void __traverse(node_t *n, int d, int _nrb)
735 {
736     int i;
737     if ( n == NULL )
738     {
739         if ( nrb == -1 ) nrb = _nrb;
740         if ( nrb != _nrb )
741             printf("Imbalance at depth %d (%d,%d)\n", d, nrb, _nrb);
742         return;
743     }
744     if ( IS_LEAF(n) && (n->k != 0) )
745     {
746         assert(n->l == NULL);
747         assert(n->r == NULL);
748         assert(IS_BLACK(n->v));
749     }
750     if ( !IS_LEAF(n) && IS_RED(n->v) )
751     {
752         assert(IS_BLACK(n->l->v));
753         assert(IS_BLACK(n->r->v));
754     }
755     if ( IS_BLACK(n->v) ) _nrb++;
756     __traverse(n->l, d+1, _nrb);
757     if ( valll > n->k ) bug=1;
758 #if 0
759     for ( i = 0; i < d; i++ ) printf("  ");
760     printf("%c%p K: %5d  V: %p  P: %p  L: %p  R: %p  depth: %d\n",
761            IS_BLACK(n->v) ? 'B' : 'R', n, n->k, n->v, n->p, n->l, n->r, d);
762 #endif
763     valll = n->k;
764     __traverse(n->r, d+1, _nrb);
765 }
766 void check_tree(set_t *s)
767 {
768     __traverse(s->root.r, 0, 0);
769     if ( bug )
770         printf("***********************************************************************************************\n");
771 }
772 #endif