Debian Codegraph @

src/treemap.c

raw
1 /*
2 * treemap.c - tree map implementation
3 *
4 * Copyright (c) 2007-2024 Shiro Kawai <[email protected]>
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * 3. Neither the name of the authors nor the names of its contributors
18 * may be used to endorse or promote products derived from this
19 * software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 #define LIBGAUCHE_BODY
35 #include "gauche.h"
36 #include "gauche/priv/configP.h"
37
38 /*================================================================
39 * ScmTreeCore
40 */
41
42 /* The actual node structure. The first two elements must match
43 ScmDictEntry. */
44 typedef struct NodeRec {
45 intptr_t key;
46 intptr_t value;
47 int color;
48 struct NodeRec *parent;
49 struct NodeRec *left;
50 struct NodeRec *right;
51 } Node;
52
53 /* Tree core has an extra operation than dictionary */
54 enum TreeOp {
55 TREE_GET = SCM_DICT_GET,
56 TREE_CREATE = SCM_DICT_CREATE,
57 TREE_DELETE = SCM_DICT_DELETE,
58 TREE_NEAR
59 };
60
61 #define BLACK 0
62 #define RED 1
63
64 #define BLACKP(n) (!(n) || (n->color == BLACK))
65 #define REDP(n) ((n) && (n->color == RED))
66
67 #define PAINT(n, c) (n->color = c)
68
69 /* The following three macros assume N has a parent. */
70 #define LEFTP(n) (n == n->parent->left)
71 #define RIGHTP(n) (n == n->parent->right)
72 #define SIBLING(n) (LEFTP(n)? n->parent->right:n->parent->left)
73
74 /* Like the above, but can be used if the child is NULL. */
75 #define LEFTP2(p, n) (p->left == n)
76 #define RIGHTP2(p, n) (p->right == n)
77 #define SIBLING2(p, n) (LEFTP2(p, n)? p->right : p->left)
78
79 #define ROOT(tc) ((Node*)tc->root)
80 #define SET_ROOT(tc, n) (tc->root = (ScmDictEntry*)n)
81
82 static Node *core_ref(ScmTreeCore *tc, intptr_t key, enum TreeOp op,
83 Node **lo, Node **hi);
84 static Node *rightmost(Node *n);
85 static Node *leftmost(Node *n);
86 static Node *next_node(Node *n);
87 static Node *prev_node(Node *n);
88 static Node *delete_node(ScmTreeCore *tc, Node *n);
89 static Node *copy_tree(Node *parent, Node *self);
90 static int node_cleared_p(Node *n);
91
92 /*
93 * Public API
94 */
95
96 void Scm_TreeCoreInit(ScmTreeCore *tc,
97 ScmTreeCoreCompareProc *cmp,
98 void *data)
99 {
100 tc->root = NULL;
101 tc->cmp = cmp;
102 tc->num_entries = 0;
103 tc->data = data;
104 }
105
106 void Scm_TreeCoreCopy(ScmTreeCore *dst, const ScmTreeCore *src)
107 {
108 if (ROOT(src)) {
109 SET_ROOT(dst, copy_tree(NULL, ROOT(src)));
110 } else {
111 SET_ROOT(dst, NULL);
112 }
113 dst->cmp = src->cmp;
114 dst->num_entries = src->num_entries;
115 dst->data = src->data;
116 }
117
118 void Scm_TreeCoreClear(ScmTreeCore *tc)
119 {
120 tc->root = NULL;
121 tc->num_entries = 0;
122 }
123
124 ScmDictEntry *Scm_TreeCoreSearch(ScmTreeCore *tc,
125 intptr_t key,
126 ScmDictOp op)
127 {
128 return (ScmDictEntry*)core_ref(tc, key, (enum TreeOp)op, NULL, NULL);
129 }
130
131 ScmDictEntry *Scm_TreeCoreClosestEntries(ScmTreeCore *tc,
132 intptr_t key,
133 ScmDictEntry **lo,
134 ScmDictEntry **hi)
135 {
136 Node *l, *h;
137 Node *r = core_ref(tc, key, TREE_NEAR, &l, &h);
138 *lo = (ScmDictEntry*)l;
139 *hi = (ScmDictEntry*)h;
140 return (ScmDictEntry*)r;
141 }
142
143 ScmDictEntry *Scm_TreeCoreNextEntry(ScmTreeCore *tc, intptr_t key)
144 {
145 Node *l, *h;
146 core_ref(tc, key, TREE_NEAR, &l, &h);
147 return (ScmDictEntry*)h;
148 }
149
150 ScmDictEntry *Scm_TreeCorePrevEntry(ScmTreeCore *tc, intptr_t key)
151 {
152 Node *l, *h;
153 core_ref(tc, key, TREE_NEAR, &l, &h);
154 return (ScmDictEntry*)l;
155 }
156
157 static Node *core_bound(ScmTreeCore *tc, ScmTreeCoreBoundOp op, int pop)
158 {
159 Node *root = ROOT(tc);
160 if (root) {
161 Node *n = (op == SCM_TREE_CORE_MIN)? leftmost(root) : rightmost(root);
162 if (pop) {
163 n = delete_node(tc, n);
164 tc->num_entries--;
165 }
166 return n;
167 } else {
168 return NULL;
169 }
170 }
171
172 ScmDictEntry *Scm_TreeCoreGetBound(ScmTreeCore *tc, ScmTreeCoreBoundOp op)
173 {
174 return (ScmDictEntry*)core_bound(tc, op, FALSE);
175 }
176
177 ScmDictEntry *Scm_TreeCorePopBound(ScmTreeCore *tc, ScmTreeCoreBoundOp op)
178 {
179 return (ScmDictEntry*)core_bound(tc, op, TRUE);
180 }
181
182 int Scm_TreeCoreNumEntries(ScmTreeCore *tc)
183 {
184 return tc->num_entries;
185 }
186
187 int Scm_TreeCoreEq(ScmTreeCore *a, ScmTreeCore *b)
188 {
189 ScmTreeIter ai, bi;
190 if (a->num_entries != b->num_entries) return FALSE;
191 Scm_TreeIterInit(&ai, a, NULL);
192 Scm_TreeIterInit(&bi, b, NULL);
193 for (;;) {
194 ScmDictEntry *ae = Scm_TreeIterNext(&ai);
195 ScmDictEntry *be = Scm_TreeIterNext(&bi);
196 if (ae == NULL) {
197 if (be == NULL) return TRUE;
198 else return FALSE;
199 }
200 if (be == NULL) return FALSE;
201 if (ae->key != be->key || ae->value != be->value) return FALSE;
202 }
203 }
204
205 static ScmDictEntry *advance_iter(ScmDictEntry *e)
206 {
207 if (e) return (ScmDictEntry*)next_node((Node*)e);
208 else return NULL;
209 }
210
211 static ScmDictEntry *retrogress_iter(ScmDictEntry *e)
212 {
213 if (e) return (ScmDictEntry*)prev_node((Node*)e);
214 else return NULL;
215 }
216
217 /* START can be NULL; in which case, if next call is TreeIterNext,
218 it iterates from the minimum node; if next call is TreeIterPrev,
219 it iterates from the maximum node. */
220 void Scm_TreeIterInit(ScmTreeIter *iter,
221 ScmTreeCore *tc,
222 ScmDictEntry *start)
223 {
224 if (start && Scm_TreeCoreSearch(tc, start->key, SCM_DICT_GET) != start) {
225 Scm_Error("Scm_TreeIterInit: iteration start point is not a part of the tree.");
226 }
227 iter->t = tc;
228 iter->c = start;
229 iter->n = (start
230 ? advance_iter(start)
231 : Scm_TreeCoreGetBound(iter->t, SCM_TREE_CORE_MIN));
232 iter->p = (start
233 ? retrogress_iter(start)
234 : Scm_TreeCoreGetBound(iter->t, SCM_TREE_CORE_MAX));
235 }
236
237 /* Mind that the 'current' node might be deleted. */
238 ScmDictEntry *Scm_TreeIterNext(ScmTreeIter *iter)
239 {
240 if (node_cleared_p((Node*)iter->c)) {
241 iter->c = iter->n;
242 iter->p = retrogress_iter(iter->c);
243 iter->n = advance_iter(iter->c);
244 } else {
245 iter->p = iter->c;
246 iter->c = iter->n;
247 iter->n = advance_iter(iter->c);
248 }
249 return iter->c;
250 }
251
252 ScmDictEntry *Scm_TreeIterPrev(ScmTreeIter *iter)
253 {
254 if (node_cleared_p((Node*)iter->c)) {
255 iter->c = iter->p;
256 iter->n = advance_iter(iter->c);
257 iter->p = retrogress_iter(iter->c);
258 } else {
259 iter->n = iter->c;
260 iter->c = iter->p;
261 iter->p = retrogress_iter(iter->c);
262 }
263 return iter->c;
264 }
265
266 ScmDictEntry *Scm_TreeIterCurrent(ScmTreeIter *iter)
267 {
268 return iter->c;
269 }
270
271 int Scm_TreeIterAtEnd(ScmTreeIter *iter)
272 {
273 return iter->c == NULL && (iter->p == NULL || iter->n == NULL);
274 }
275
276 /* consistency check */
277
278
279 /* depth is # of black nodes. */
280 static int check_traverse(Node *node, int depth, int *count)
281 {
282 int ld, rd;
283
284 (*count)++; /* entry count */
285 if (BLACKP(node)) depth++;
286
287 if (node->left) {
288 if (REDP(node) && REDP(node->left)) {
289 Scm_Error("[internal] tree map has adjacent red nodes");
290 }
291 ld = check_traverse(node->left, depth, count);
292 } else {
293 ld = depth;
294 }
295 if (node->right) {
296 if (REDP(node) && REDP(node->right)) {
297 Scm_Error("[internal] tree map has adjacent red nodes");
298 }
299 rd = check_traverse(node->right, depth, count);
300 } else {
301 rd = depth;
302 }
303 if (ld != rd) {
304 Scm_Error("[internal] tree map has different black-node depth (L:%d vs R:%d)", ld, rd);
305 }
306 return ld;
307 }
308
309 void Scm_TreeCoreCheckConsistency(ScmTreeCore *tc)
310 {
311 Node *r = ROOT(tc);
312 int cnt = 0;
313
314 if (!BLACKP(r)) Scm_Error("[internal] tree map root node is not black.");
315 if (r) check_traverse(r, 1, &cnt);
316 if (cnt != tc->num_entries) {
317 Scm_Error("[internal] tree map node count mismatch: record %d vs actual %d", tc->num_entries, cnt);
318 }
319 }
320
321 /*================================================================
322 * ScmTreeMap
323 */
324
325 static void treemap_print(ScmObj obj, ScmPort *port,
326 ScmWriteContext *ctx SCM_UNUSED)
327 {
328 ScmTreeMap *tm = SCM_TREE_MAP(obj);
329 Scm_Printf(port, "#<tree-map %p (%d entries)>", tm,
330 Scm_TreeCoreNumEntries(SCM_TREE_MAP_CORE(tm)));
331 }
332
333 SCM_DEFINE_BUILTIN_CLASS(Scm_TreeMapClass, treemap_print, Scm_ObjectCompare,
334 NULL, NULL,
335 SCM_CLASS_ORDERED_DICTIONARY_CPL);
336
337 /*
338 * Constructor
339 */
340
341 ScmObj Scm_MakeTreeMap(ScmTreeCoreCompareProc *cmp, void *data)
342 {
343 ScmTreeMap *tm = SCM_NEW(ScmTreeMap);
344 SCM_SET_CLASS(tm, SCM_CLASS_TREE_MAP);
345 /* TODO: default cmp should be different from TreeCore */
346 Scm_TreeCoreInit(SCM_TREE_MAP_CORE(tm), cmp, data);
347 return SCM_OBJ(tm);
348 }
349
350 ScmObj Scm_TreeMapCopy(const ScmTreeMap *src)
351 {
352 ScmTreeMap *tm = SCM_NEW(ScmTreeMap);
353 SCM_SET_CLASS(tm, SCM_CLASS_TREE_MAP);
354 Scm_TreeCoreCopy(SCM_TREE_MAP_CORE(tm), SCM_TREE_MAP_CORE(src));
355 return SCM_OBJ(tm);
356 }
357
358 /*
359 * Query
360 */
361 ScmObj Scm_TreeMapRef(ScmTreeMap *tm, ScmObj key, ScmObj fallback)
362 {
363 ScmDictEntry *e = Scm_TreeCoreSearch(SCM_TREE_MAP_CORE(tm),
364 (intptr_t)key, SCM_DICT_GET);
365 if (!e) {
366 return fallback;
367 } else {
368 return SCM_DICT_VALUE(e);
369 }
370 }
371
372 /* Returns previous value; can return SCM_UNBOUND when the association hasn't
373 been there. Be careful not to let SCM_UNBOUND leak out to Scheme! */
374 ScmObj Scm_TreeMapSet(ScmTreeMap *tm, ScmObj key, ScmObj value, int flags)
375 {
376 ScmDictEntry *e = Scm_TreeCoreSearch(SCM_TREE_MAP_CORE(tm),
377 (intptr_t)key,
378 (flags&SCM_DICT_NO_CREATE)? SCM_DICT_GET : SCM_DICT_CREATE);
379 if (!e) return SCM_UNBOUND;
380 ScmObj oldval = e->value? SCM_DICT_VALUE(e) : SCM_UNBOUND;
381 if (!(flags&SCM_DICT_NO_OVERWRITE) || SCM_UNBOUNDP(oldval)) {
382 (void)SCM_DICT_SET_VALUE(e, value);
383 }
384 return oldval;
385 }
386
387 ScmObj Scm_TreeMapDelete(ScmTreeMap *tm, ScmObj key)
388 {
389 ScmDictEntry *e = Scm_TreeCoreSearch(SCM_TREE_MAP_CORE(tm),
390 (intptr_t)key, SCM_DICT_DELETE);
391 if (e && e->value) return SCM_DICT_VALUE(e);
392 else return SCM_UNBOUND;
393 }
394
395 /* for debug */
396 static void dump_traverse(Node *node, int depth, ScmPort *out, int scmobj)
397 {
398 if (node->left) dump_traverse(node->left, depth+1, out, scmobj);
399 for (int i=0; i<depth; i++) Scm_Printf(out, " ");
400 if (scmobj) {
401 Scm_Printf(out, "%c:%S => %S\n", BLACKP(node)?'B':'R',
402 SCM_OBJ(node->key), SCM_OBJ(node->value));
403 } else {
404 Scm_Printf(out, "%c:%08x => %08x\n", BLACKP(node)?'B':'R',
405 node->key, node->value);
406 }
407 if (node->right) dump_traverse(node->right, depth+1, out, scmobj);
408 }
409
410 void Scm_TreeMapDump(ScmTreeMap *tm, ScmPort *out)
411 {
412 ScmTreeCore *tc = SCM_TREE_MAP_CORE(tm);
413 Node *r = ROOT(tc);
414 Scm_Printf(out, "Entries=%d\n", tc->num_entries);
415 if (r) {
416 dump_traverse(r, 0, out, TRUE);
417 }
418 }
419
420 void Scm_TreeCoreDump(ScmTreeCore *tc, ScmPort *out)
421 {
422 Node *r = ROOT(tc);
423 Scm_Printf(out, "Entries=%d\n", tc->num_entries);
424 if (r) {
425 dump_traverse(r, 0, out, FALSE);
426 }
427 }
428
429 /*=============================================================
430 * Internal stuff (Red-Black Tree implementation)
431 */
432
433 /* Returns the right/leftmost node under N. */
434 static Node *rightmost(Node *n)
435 {
436 while (n->right) n = n->right;
437 return n;
438 }
439
440 static Node *leftmost(Node *n)
441 {
442 while (n->left) n = n->left;
443 return n;
444 }
445
446 /* Returns the previous node of N. NULL iff n is the minimum. */
447 static Node *prev_node(Node *n)
448 {
449 if (n->left) return rightmost(n->left);
450 while (n->parent) {
451 if (RIGHTP(n)) return n->parent;
452 n = n->parent;
453 }
454 return NULL;
455 }
456
457 /* Returns the next node of N. NULL iff n is the maximum. */
458 static Node *next_node(Node *n)
459 {
460 if (n->right) return leftmost(n->right);
461 while (n->parent) {
462 if (LEFTP(n)) return n->parent;
463 n = n->parent;
464 }
465 return NULL;
466 }
467
468 /* fresh node */
469 static Node *new_node(Node *parent, intptr_t key)
470 {
471 Node *n = SCM_NEW(Node);
472 n->key = key;
473 n->value = 0;
474 n->color = RED; /* default is red */
475 n->parent = parent;
476 n->left = n->right = NULL;
477 return n;
478 }
479
480 /* clear node (for Weak-GC safeness) */
481 static void clear_node(Node *node)
482 {
483 node->parent = node->left = node->right = NULL;
484 }
485
486 static int node_cleared_p(Node *node)
487 {
488 return (node && node->parent == NULL
489 && node->left == NULL && node->right == NULL);
490 }
491
492 /* replace N's position by M. M could be NULL. */
493 static void replace_node(ScmTreeCore *tc, Node *n, Node *m)
494 {
495 if (n->parent) {
496 if (LEFTP(n)) n->parent->left = m;
497 else n->parent->right = m;
498 } else {
499 SET_ROOT(tc, m);
500 }
501 if (m) m->parent = n->parent;
502 }
503
504
505 /* rotate_right:
506
507 N L
508 +-----+ +-----+
509 L R ==> GL N
510 +---+ +---+
511 GL GR GR R
512 */
513 static void rotate_right(ScmTreeCore *tc, Node *n)
514 {
515 Node *l = n->left;
516 SCM_ASSERT(l != NULL);
517 Node *gr = l->right;
518
519 replace_node(tc, n, l);
520 l->right = n; n->parent = l;
521 n->left = gr; if (gr) gr->parent = n;
522 }
523
524 /* rotate_left:
525
526 N R
527 +-----+ +-----+
528 L R ==> N GR
529 +---+ +---+
530 GL GR L GL
531 */
532 static void rotate_left(ScmTreeCore *tc, Node *n)
533 {
534 Node *r = n->right;
535 SCM_ASSERT(r != NULL);
536 Node *gl = r->left;
537
538 replace_node(tc, n, r);
539 r->left = n; n->parent = r;
540 n->right = gl; if (gl) gl->parent = n;
541 }
542
543 #if 0 /* for debug */
544 #define BALANCE_CASE(n) printf("balance case %s\n", n)
545 #else
546 #define BALANCE_CASE(n) /*nothing*/
547 #endif
548
549 /* balance tree after insertion of N */
550 static void balance_tree(ScmTreeCore *tc, Node *n)
551 {
552 Node *p = n->parent;
553
554 if (!p) { BALANCE_CASE("1"); n->color = BLACK; return; } /* root */
555 if (BLACKP(p)) { BALANCE_CASE("2"); return; } /* nothing to do */
556
557 /* Here we're sure we have grandparent. */
558 Node *g = p->parent;
559 SCM_ASSERT(g != NULL);
560 Node *u = (g->left == p)? g->right : g->left;
561
562 if (REDP(u)) {
563 p->color = u->color = BLACK;
564 g->color = RED;
565 BALANCE_CASE("3");
566 balance_tree(tc, g);
567 return;
568 }
569 if (n == p->right && p == g->left) {
570 rotate_left(tc, p);
571 n = n->left;
572 BALANCE_CASE("4a");
573 } else if (n == p->left && p == g->right) {
574 rotate_right(tc, p);
575 n = n->right;
576 BALANCE_CASE("4b");
577 }
578 p = n->parent;
579 g = p->parent;
580 p->color = BLACK;
581 g->color = RED;
582 if (n == p->left && p == g->left) {
583 rotate_right(tc, g);
584 BALANCE_CASE("5a");
585 } else {
586 rotate_left(tc, g);
587 BALANCE_CASE("5b");
588 }
589 }
590
591 #if 0 /* for debug */
592 #define DELETE_CASE(n) printf("delete case %s\n", n)
593 #else
594 #define DELETE_CASE(n) /*nothing*/
595 #endif
596
597 /* deletes a node TODIE who has at most one child, CHILD.
598 Note that CHILD can be NULL (empty BLACK node) */
599 static void delete_node1(ScmTreeCore *tc, Node *todie, Node *child)
600 {
601 Node *parent = todie->parent;
602
603 replace_node(tc, todie, child);
604 if (REDP(todie)) { DELETE_CASE("1"); return; }
605 if (REDP(child)) { DELETE_CASE("2"); child->color = BLACK; return; }
606
607 recur:
608 /* At this point, child is BLACK. */
609 if (parent == NULL) { DELETE_CASE("3"); return; }
610 Node *sibling = SIBLING2(parent, child);
611 /* sibling can't be NULL, since it would break the invariance of
612 consistent # of black nodes for every path. */
613 SCM_ASSERT(sibling != NULL);
614
615 if (REDP(sibling)) {
616 parent->color = RED;
617 sibling->color = BLACK;
618 if (LEFTP2(parent, child)) {
619 rotate_left(tc, parent);
620 sibling = SIBLING2(parent, child);
621 DELETE_CASE("4a");
622 } else {
623 rotate_right(tc, parent);
624 sibling = SIBLING2(parent, child);
625 DELETE_CASE("4b");
626 }
627 }
628
629 /* At this point, sibling is BLACK */
630 if (BLACKP(parent) && BLACKP(sibling->left) && BLACKP(sibling->right)) {
631 sibling->color = RED;
632
633 child = parent;
634 parent = parent->parent;
635 DELETE_CASE("5");
636 goto recur;
637 }
638 if (REDP(parent) && BLACKP(sibling->left) && BLACKP(sibling->right)) {
639 parent->color = BLACK;
640 sibling->color = RED;
641 DELETE_CASE("6");
642 return;
643 }
644 if (LEFTP2(parent, child)) {
645 if (REDP(sibling->left) && BLACKP(sibling->right)) {
646 sibling->color = RED;
647 sibling->left->color = BLACK;
648 rotate_right(tc, sibling);
649 sibling = SIBLING2(parent, child);
650 DELETE_CASE("7a");
651 }
652 } else { /* RIGHTP(child) */
653 if (BLACKP(sibling->left) && REDP(sibling->right)) {
654 sibling->color = RED;
655 sibling->right->color = BLACK;
656 rotate_left(tc, sibling);
657 sibling = SIBLING2(parent, child);
658 DELETE_CASE("7b");
659 }
660 }
661 sibling->color = parent->color;
662 parent->color = BLACK;
663 if (LEFTP2(parent, child)) {
664 sibling->right->color = BLACK;
665 rotate_left(tc, parent);
666 DELETE_CASE("8a");
667 } else {
668 sibling->left->color = BLACK;
669 rotate_right(tc, parent);
670 DELETE_CASE("8b");
671 }
672 }
673
674 static void swap_node(ScmTreeCore *tc, Node *x, Node *y)
675 {
676 #define SWAP(x, y, tmp) do { tmp = x; x = y; y = tmp; } while (0)
677 if (x->parent) {
678 if (LEFTP(x)) x->parent->left = y;
679 else x->parent->right = y;
680 }
681 if (y->parent) {
682 if (LEFTP(y)) y->parent->left = x;
683 else y->parent->right = x;
684 }
685 Node *t;
686 SWAP(x->parent, y->parent, t);
687
688 if (x->left) x->left->parent = y;
689 if (y->left) y->left->parent = x;
690 SWAP(x->left, y->left, t);
691
692 if (x->right) x->right->parent = y;
693 if (y->right) y->right->parent = x;
694 SWAP(x->right, y->right, t);
695
696 int c;
697 SWAP(x->color, y->color, c);
698 if (x == ROOT(tc)) SET_ROOT(tc, y);
699 else if (y == ROOT(tc)) SET_ROOT(tc, x);
700 #undef SWAP
701 }
702
703 static Node *delete_node(ScmTreeCore *tc, Node *n)
704 {
705 while (n->left && n->right) {
706 /* N has both children. We swap N and its previous node.
707 It would be easier just to swap key and value, but it could
708 lead to a hard-to-track bug if a pointer to N is retained
709 in somewhere (e.g. iterator). So we actually swap the node. */
710 swap_node(tc, n, prev_node(n));
711 }
712
713 /* we have at most one child */
714 if (n->left) {
715 delete_node1(tc, n, n->left);
716 } else {
717 delete_node1(tc, n, n->right); /* this covers no child case */
718 }
719 clear_node(n);
720 return n;
721 }
722
723 /* accessor */
724 Node *core_ref(ScmTreeCore *tc, intptr_t key, enum TreeOp op,
725 Node **lo, Node **hi)
726 {
727 Node *e = ROOT(tc), *n = NULL;
728
729 if (e == NULL) {
730 /* Tree is empty */
731 if (op == TREE_CREATE) {
732 n = new_node(NULL, key);
733 PAINT(n, BLACK);
734 SET_ROOT(tc, n);
735 tc->num_entries++;
736 }
737 if (op == TREE_NEAR) {
738 *lo = *hi = NULL;
739 }
740 return n;
741 }
742
743 for (;;) {
744 int r = 0;
745 if (tc->cmp) r = tc->cmp(tc, e->key, key);
746
747 if (tc->cmp? (r == 0) : (e->key == key)) {
748 /* Exact match */
749 if (op == TREE_DELETE) {
750 n = delete_node(tc, e);
751 tc->num_entries--;
752 return n;
753 }
754 if (op == TREE_NEAR) {
755 *lo = prev_node(e);
756 *hi = next_node(e);
757 }
758 return e;
759 }
760
761 if (tc->cmp? (r < 0) : (e->key < key)) {
762 /* Key is larger than E */
763 if (e->right) {
764 e = e->right;
765 } else {
766 if (op == TREE_CREATE) {
767 n = new_node(e, key);
768 e->right = n;
769 balance_tree(tc, n);
770 tc->num_entries++;
771 return n;
772 }
773 if (op == TREE_NEAR) {
774 *lo = e;
775 *hi = next_node(e);
776 }
777 return NULL;
778 }
779 } else {
780 /* Key is smaller than E */
781 if (e->left) {
782 e = e->left;
783 } else {
784 if (op == TREE_CREATE) {
785 n = new_node(e, key);
786 e->left = n;
787 balance_tree(tc, n);
788 tc->num_entries++;
789 return n;
790 }
791 if (op == TREE_NEAR) {
792 *hi = e;
793 *lo = prev_node(e);
794 }
795 return NULL;
796 }
797 }
798 }
799 }
800
801 /* copy */
802 static Node *copy_tree(Node *parent, Node *self)
803 {
804 Node *n = new_node(parent, self->key);
805 n->value = self->value;
806 n->color = self->color;
807 if (self->left) n->left = copy_tree(n, self->left);
808 if (self->right) n->right = copy_tree(n, self->right);
809 return n;
810 }