0000: 23 69 6e 63 6c 75 64 65 20 22 74 72 65 65 2e 68 #include "tree.h
0010: 22 0a 0a 23 69 66 20 49 4e 54 45 52 46 41 43 45 "..#if INTERFACE
0020: 0a 65 6e 75 6d 20 74 72 65 65 6d 6f 64 65 20 7b .enum treemode {
0030: 20 54 52 45 45 5f 53 50 4c 41 59 3d 31 2c 20 54 TREE_SPLAY=1, T
0040: 52 45 45 5f 54 52 45 41 50 2c 20 54 52 45 45 5f REE_TREAP, TREE_
0050: 43 4f 55 4e 54 20 7d 3b 0a 0a 23 65 6e 64 69 66 COUNT };..#endif
0060: 0a 0a 65 78 63 65 70 74 69 6f 6e 5f 64 65 66 20 ..exception_def
0070: 4f 75 74 4f 66 42 6f 75 6e 64 73 45 78 63 65 70 OutOfBoundsExcep
0080: 74 69 6f 6e 20 3d 20 7b 20 22 4f 75 74 4f 66 42 tion = { "OutOfB
0090: 6f 75 6e 64 73 45 78 63 65 70 74 69 6f 6e 22 2c oundsException",
00a0: 20 26 52 75 6e 74 69 6d 65 45 78 63 65 70 74 69 &RuntimeExcepti
00b0: 6f 6e 20 7d 3b 0a 0a 74 79 70 65 64 65 66 20 73 on };..typedef s
00c0: 74 72 75 63 74 20 74 72 65 65 5f 74 20 74 72 65 truct tree_t tre
00d0: 65 5f 74 3b 0a 74 79 70 65 64 65 66 20 73 74 72 e_t;.typedef str
00e0: 75 63 74 20 6e 6f 64 65 5f 74 20 6e 6f 64 65 5f uct node_t node_
00f0: 74 3b 0a 0a 73 74 72 75 63 74 20 6e 6f 64 65 5f t;..struct node_
0100: 74 20 7b 0a 09 6d 61 70 5f 6b 65 79 20 6b 65 79 t {..map_key key
0110: 3b 0a 09 6d 61 70 5f 64 61 74 61 20 64 61 74 61 ;..map_data data
0120: 3b 0a 0a 09 2f 2a 20 43 6f 75 6e 74 20 6f 66 20 ;.../* Count of
0130: 6e 6f 64 65 73 2c 20 69 6e 63 6c 75 64 69 6e 67 nodes, including
0140: 20 74 68 69 73 20 6f 6e 65 20 2a 2f 0a 09 69 6e this one */..in
0150: 74 20 63 6f 75 6e 74 3b 0a 0a 09 2f 2a 20 74 72 t count;.../* tr
0160: 65 61 70 20 6e 6f 64 65 20 70 72 69 6f 72 69 74 eap node priorit
0170: 79 20 2a 2f 0a 09 69 6e 74 20 70 72 69 6f 72 69 y */..int priori
0180: 74 79 3b 0a 0a 09 2f 2a 20 4e 6f 64 65 73 20 63 ty;.../* Nodes c
0190: 6f 6e 6e 65 63 74 69 76 69 74 79 20 2a 2f 0a 09 onnectivity */..
01a0: 6e 6f 64 65 5f 74 20 2a 20 70 61 72 65 6e 74 3b node_t * parent;
01b0: 0a 09 6e 6f 64 65 5f 74 20 2a 20 6c 65 66 74 3b ..node_t * left;
01c0: 0a 09 6e 6f 64 65 5f 74 20 2a 20 72 69 67 68 74 ..node_t * right
01d0: 3b 0a 7d 3b 0a 0a 73 74 72 75 63 74 20 74 72 65 ;.};..struct tre
01e0: 65 5f 74 20 7b 0a 09 6d 61 70 5f 74 20 6d 61 70 e_t {..map_t map
01f0: 3b 0a 0a 09 6e 6f 64 65 5f 74 20 2a 20 72 6f 6f ;...node_t * roo
0200: 74 3b 0a 0a 09 69 6e 74 20 6d 6f 64 65 3b 0a 0a t;...int mode;..
0210: 09 69 6e 74 20 28 2a 63 6f 6d 70 29 28 6d 61 70 .int (*comp)(map
0220: 5f 6b 65 79 20 6b 31 2c 20 6d 61 70 5f 6b 65 79 _key k1, map_key
0230: 20 6b 32 29 3b 0a 7d 3b 0a 0a 73 74 61 74 69 63 k2);.};..static
0240: 20 6e 6f 64 65 5f 74 20 2a 20 74 72 65 65 5f 6e node_t * tree_n
0250: 6f 64 65 5f 66 69 72 73 74 28 74 72 65 65 5f 74 ode_first(tree_t
0260: 20 2a 20 74 72 65 65 29 3b 0a 73 74 61 74 69 63 * tree);.static
0270: 20 63 6f 6e 73 74 20 6e 6f 64 65 5f 74 20 2a 20 const node_t *
0280: 6e 6f 64 65 5f 6e 65 78 74 28 20 63 6f 6e 73 74 node_next( const
0290: 20 6e 6f 64 65 5f 74 20 2a 20 63 6f 6e 73 74 20 node_t * const
02a0: 63 75 72 72 65 6e 74 20 29 3b 0a 23 69 66 20 30 current );.#if 0
02b0: 0a 73 74 61 74 69 63 20 76 6f 69 64 20 74 72 65 .static void tre
02c0: 65 5f 6d 61 72 6b 28 76 6f 69 64 20 2a 20 70 29 e_mark(void * p)
02d0: 0a 7b 0a 09 74 72 65 65 5f 74 20 2a 20 74 72 65 .{..tree_t * tre
02e0: 65 20 3d 20 28 74 72 65 65 5f 74 2a 29 70 3b 0a e = (tree_t*)p;.
02f0: 09 73 6c 61 62 5f 67 63 5f 6d 61 72 6b 28 74 72 .slab_gc_mark(tr
0300: 65 65 2d 3e 72 6f 6f 74 29 3b 0a 7d 0a 0a 73 74 ee->root);.}..st
0310: 61 74 69 63 20 76 6f 69 64 20 6e 6f 64 65 5f 6d atic void node_m
0320: 61 72 6b 28 76 6f 69 64 20 2a 20 70 29 0a 7b 0a ark(void * p).{.
0330: 09 6e 6f 64 65 5f 74 20 2a 20 6e 6f 64 65 20 3d .node_t * node =
0340: 20 28 6e 6f 64 65 5f 74 2a 29 70 3b 0a 09 73 6c (node_t*)p;..sl
0350: 61 62 5f 67 63 5f 6d 61 72 6b 28 28 76 6f 69 64 ab_gc_mark((void
0360: 2a 29 6e 6f 64 65 2d 3e 6b 65 79 29 3b 0a 09 73 *)node->key);..s
0370: 6c 61 62 5f 67 63 5f 6d 61 72 6b 28 28 76 6f 69 lab_gc_mark((voi
0380: 64 2a 29 6e 6f 64 65 2d 3e 64 61 74 61 29 3b 0a d*)node->data);.
0390: 09 73 6c 61 62 5f 67 63 5f 6d 61 72 6b 28 6e 6f .slab_gc_mark(no
03a0: 64 65 2d 3e 6c 65 66 74 29 3b 0a 09 73 6c 61 62 de->left);..slab
03b0: 5f 67 63 5f 6d 61 72 6b 28 6e 6f 64 65 2d 3e 72 _gc_mark(node->r
03c0: 69 67 68 74 29 3b 0a 7d 0a 0a 76 6f 69 64 20 64 ight);.}..void d
03d0: 65 62 75 67 5f 66 69 6e 61 6c 69 7a 65 28 76 6f ebug_finalize(vo
03e0: 69 64 20 2a 20 70 29 0a 7b 0a 7d 0a 0a 73 74 61 id * p).{.}..sta
03f0: 74 69 63 20 73 6c 61 62 5f 74 79 70 65 5f 74 20 tic slab_type_t
0400: 6e 6f 64 65 73 5b 31 5d 20 3d 20 7b 20 53 4c 41 nodes[1] = { SLA
0410: 42 5f 54 59 50 45 28 73 69 7a 65 6f 66 28 6e 6f B_TYPE(sizeof(no
0420: 64 65 5f 74 29 2c 20 6e 6f 64 65 5f 6d 61 72 6b de_t), node_mark
0430: 2c 20 64 65 62 75 67 5f 66 69 6e 61 6c 69 7a 65 , debug_finalize
0440: 29 7d 3b 0a 73 74 61 74 69 63 20 73 6c 61 62 5f )};.static slab_
0450: 74 79 70 65 5f 74 20 74 72 65 65 73 5b 31 5d 20 type_t trees[1]
0460: 3d 20 7b 20 53 4c 41 42 5f 54 59 50 45 28 73 69 = { SLAB_TYPE(si
0470: 7a 65 6f 66 28 74 72 65 65 5f 74 29 2c 20 74 72 zeof(tree_t), tr
0480: 65 65 5f 6d 61 72 6b 2c 20 64 65 62 75 67 5f 66 ee_mark, debug_f
0490: 69 6e 61 6c 69 7a 65 29 7d 3b 0a 23 65 6e 64 69 inalize)};.#endi
04a0: 66 0a 73 74 61 74 69 63 20 73 6c 61 62 5f 74 79 f.static slab_ty
04b0: 70 65 5f 74 20 6e 6f 64 65 73 5b 31 5d 20 3d 20 pe_t nodes[1] =
04c0: 7b 20 53 4c 41 42 5f 54 59 50 45 28 73 69 7a 65 { SLAB_TYPE(size
04d0: 6f 66 28 6e 6f 64 65 5f 74 29 2c 20 30 2c 20 30 of(node_t), 0, 0
04e0: 29 7d 3b 0a 73 74 61 74 69 63 20 73 6c 61 62 5f )};.static slab_
04f0: 74 79 70 65 5f 74 20 74 72 65 65 73 5b 31 5d 20 type_t trees[1]
0500: 3d 20 7b 20 53 4c 41 42 5f 54 59 50 45 28 73 69 = { SLAB_TYPE(si
0510: 7a 65 6f 66 28 74 72 65 65 5f 74 29 2c 20 30 2c zeof(tree_t), 0,
0520: 20 30 29 7d 3b 0a 0a 2f 2a 0a 20 2a 20 52 6f 74 0)};../*. * Rot
0530: 61 74 65 20 6c 65 66 74 3a 0a 20 2a 20 20 20 20 ate left:. *
0540: 42 20 20 20 20 20 20 20 20 20 20 20 20 44 0a 20 B D.
0550: 2a 20 20 20 2f 20 5c 20 20 20 20 20 20 20 20 20 * / \
0560: 20 2f 20 5c 0a 20 2a 20 20 41 20 20 20 44 20 20 / \. * A D
0570: 20 3d 3e 20 20 20 42 20 20 20 45 0a 20 2a 20 20 => B E. *
0580: 20 20 20 2f 20 5c 20 20 20 20 20 20 2f 20 5c 0a / \ / \.
0590: 20 2a 20 20 20 20 43 20 20 20 45 20 20 20 20 41 * C E A
05a0: 20 20 20 43 0a 20 2a 2f 0a 73 74 61 74 69 63 20 C. */.static
05b0: 76 6f 69 64 20 6e 6f 64 65 5f 72 6f 74 61 74 65 void node_rotate
05c0: 5f 6c 65 66 74 28 20 6e 6f 64 65 5f 74 20 2a 20 _left( node_t *
05d0: 62 20 29 0a 7b 0a 20 20 20 20 20 20 20 20 6e 6f b ).{. no
05e0: 64 65 5f 74 20 2a 20 61 20 3d 20 62 2d 3e 6c 65 de_t * a = b->le
05f0: 66 74 3b 0a 20 20 20 20 20 20 20 20 6e 6f 64 65 ft;. node
0600: 5f 74 20 2a 20 64 20 3d 20 62 2d 3e 72 69 67 68 _t * d = b->righ
0610: 74 3b 0a 20 20 20 20 20 20 20 20 6e 6f 64 65 5f t;. node_
0620: 74 20 2a 20 63 20 3d 20 64 2d 3e 6c 65 66 74 3b t * c = d->left;
0630: 0a 20 20 20 20 20 20 20 20 6e 6f 64 65 5f 74 20 . node_t
0640: 2a 20 65 20 3d 20 64 2d 3e 72 69 67 68 74 3b 0a * e = d->right;.
0650: 0a 20 20 20 20 20 20 20 20 61 73 73 65 72 74 28 . assert(
0660: 64 29 3b 0a 20 20 20 20 20 20 20 20 61 73 73 65 d);. asse
0670: 72 74 28 64 2d 3e 70 61 72 65 6e 74 20 3d 3d 20 rt(d->parent ==
0680: 62 29 3b 0a 20 20 20 20 20 20 20 20 61 73 73 65 b);. asse
0690: 72 74 28 4e 55 4c 4c 20 3d 3d 20 63 20 7c 7c 20 rt(NULL == c ||
06a0: 63 2d 3e 70 61 72 65 6e 74 20 3d 3d 20 64 29 3b c->parent == d);
06b0: 0a 20 20 20 20 20 20 20 20 61 73 73 65 72 74 28 . assert(
06c0: 4e 55 4c 4c 20 3d 3d 20 62 2d 3e 70 61 72 65 6e NULL == b->paren
06d0: 74 20 7c 7c 20 62 2d 3e 70 61 72 65 6e 74 2d 3e t || b->parent->
06e0: 6c 65 66 74 20 3d 3d 20 62 20 7c 7c 20 62 2d 3e left == b || b->
06f0: 70 61 72 65 6e 74 2d 3e 72 69 67 68 74 20 3d 3d parent->right ==
0700: 20 62 29 3b 0a 0a 20 20 20 20 20 20 20 20 2f 2a b);.. /*
0710: 20 4c 69 6e 6b 20 64 20 69 6e 74 6f 20 62 27 73 Link d into b's
0720: 20 70 61 72 65 6e 74 20 2a 2f 0a 20 20 20 20 20 parent */.
0730: 20 20 20 64 2d 3e 70 61 72 65 6e 74 20 3d 20 62 d->parent = b
0740: 2d 3e 70 61 72 65 6e 74 3b 0a 0a 20 20 20 20 20 ->parent;..
0750: 20 20 20 2f 2a 20 52 65 70 61 72 65 6e 74 20 62 /* Reparent b
0760: 20 2a 2f 0a 20 20 20 20 20 20 20 20 62 2d 3e 70 */. b->p
0770: 61 72 65 6e 74 20 3d 20 64 3b 0a 20 20 20 20 20 arent = d;.
0780: 20 20 20 64 2d 3e 6c 65 66 74 20 3d 20 62 3b 0a d->left = b;.
0790: 0a 20 20 20 20 20 20 20 20 2f 2a 20 52 65 70 61 . /* Repa
07a0: 72 65 6e 74 20 63 20 69 66 20 72 65 71 75 69 72 rent c if requir
07b0: 65 64 20 2a 2f 0a 20 20 20 20 20 20 20 20 62 2d ed */. b-
07c0: 3e 72 69 67 68 74 20 3d 20 63 3b 0a 20 20 20 20 >right = c;.
07d0: 20 20 20 20 69 66 20 28 62 2d 3e 72 69 67 68 74 if (b->right
07e0: 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 ) {.
07f0: 20 20 20 20 62 2d 3e 72 69 67 68 74 2d 3e 70 61 b->right->pa
0800: 72 65 6e 74 20 3d 20 62 3b 0a 20 20 20 20 20 20 rent = b;.
0810: 20 20 7d 0a 0a 20 20 20 20 20 20 20 20 2f 2a 20 }.. /*
0820: 4c 69 6e 6b 20 69 6e 74 6f 20 64 20 70 61 72 65 Link into d pare
0830: 6e 74 20 2a 2f 0a 20 20 20 20 20 20 20 20 69 66 nt */. if
0840: 20 28 64 2d 3e 70 61 72 65 6e 74 29 20 7b 0a 20 (d->parent) {.
0850: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 i
0860: 66 20 28 62 20 3d 3d 20 64 2d 3e 70 61 72 65 6e f (b == d->paren
0870: 74 2d 3e 6c 65 66 74 29 20 7b 0a 20 20 20 20 20 t->left) {.
0880: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0890: 20 20 20 64 2d 3e 70 61 72 65 6e 74 2d 3e 6c 65 d->parent->le
08a0: 66 74 20 3d 20 64 3b 0a 20 20 20 20 20 20 20 20 ft = d;.
08b0: 20 20 20 20 20 20 20 20 7d 20 65 6c 73 65 20 7b } else {
08c0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 .
08d0: 20 20 20 20 20 20 20 20 20 64 2d 3e 70 61 72 65 d->pare
08e0: 6e 74 2d 3e 72 69 67 68 74 20 3d 20 64 3b 0a 20 nt->right = d;.
08f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 7d }
0900: 0a 20 20 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 . }..
0910: 20 20 20 20 2f 2a 20 46 69 78 20 6e 6f 64 65 20 /* Fix node
0920: 63 6f 75 6e 74 73 20 2a 2f 0a 20 20 20 20 20 20 counts */.
0930: 20 20 62 2d 3e 63 6f 75 6e 74 20 3d 20 31 20 2b b->count = 1 +
0940: 20 28 28 61 29 20 3f 20 61 2d 3e 63 6f 75 6e 74 ((a) ? a->count
0950: 20 3a 20 30 29 20 2b 20 28 28 63 29 20 3f 20 63 : 0) + ((c) ? c
0960: 2d 3e 63 6f 75 6e 74 20 3a 20 30 29 3b 0a 20 20 ->count : 0);.
0970: 20 20 20 20 20 20 64 2d 3e 63 6f 75 6e 74 20 3d d->count =
0980: 20 31 20 2b 20 62 2d 3e 63 6f 75 6e 74 20 2b 20 1 + b->count +
0990: 28 28 65 29 20 3f 20 65 2d 3e 63 6f 75 6e 74 20 ((e) ? e->count
09a0: 3a 20 30 29 3b 0a 0a 20 20 20 20 20 20 20 20 61 : 0);.. a
09b0: 73 73 65 72 74 28 4e 55 4c 4c 20 3d 3d 20 64 2d ssert(NULL == d-
09c0: 3e 70 61 72 65 6e 74 20 7c 7c 20 64 2d 3e 70 61 >parent || d->pa
09d0: 72 65 6e 74 2d 3e 6c 65 66 74 20 3d 3d 20 64 20 rent->left == d
09e0: 7c 7c 20 64 2d 3e 70 61 72 65 6e 74 2d 3e 72 69 || d->parent->ri
09f0: 67 68 74 20 3d 3d 20 64 29 3b 0a 7d 0a 0a 2f 2a ght == d);.}../*
0a00: 0a 20 2a 20 52 6f 74 61 74 65 20 72 69 67 68 74 . * Rotate right
0a10: 3a 0a 20 2a 20 20 20 20 20 20 44 20 20 20 20 20 :. * D
0a20: 20 20 20 42 0a 20 2a 20 20 20 20 20 2f 20 5c 20 B. * / \
0a30: 20 20 20 20 20 2f 20 5c 0a 20 2a 20 20 20 20 42 / \. * B
0a40: 20 20 20 45 20 3d 3e 20 41 20 20 20 44 0a 20 2a E => A D. *
0a50: 20 20 20 2f 20 5c 20 20 20 20 20 20 20 20 20 20 / \
0a60: 2f 20 5c 0a 20 2a 20 20 41 20 20 20 43 20 20 20 / \. * A C
0a70: 20 20 20 20 20 43 20 20 20 45 0a 20 2a 2f 0a 73 C E. */.s
0a80: 74 61 74 69 63 20 76 6f 69 64 20 6e 6f 64 65 5f tatic void node_
0a90: 72 6f 74 61 74 65 5f 72 69 67 68 74 28 20 6e 6f rotate_right( no
0aa0: 64 65 5f 74 20 2a 20 64 20 29 0a 7b 0a 20 20 20 de_t * d ).{.
0ab0: 20 20 20 20 20 6e 6f 64 65 5f 74 20 2a 20 62 20 node_t * b
0ac0: 3d 20 64 2d 3e 6c 65 66 74 3b 0a 20 20 20 20 20 = d->left;.
0ad0: 20 20 20 6e 6f 64 65 5f 74 20 2a 20 61 20 3d 20 node_t * a =
0ae0: 62 2d 3e 6c 65 66 74 3b 0a 20 20 20 20 20 20 20 b->left;.
0af0: 20 6e 6f 64 65 5f 74 20 2a 20 63 20 3d 20 62 2d node_t * c = b-
0b00: 3e 72 69 67 68 74 3b 0a 20 20 20 20 20 20 20 20 >right;.
0b10: 6e 6f 64 65 5f 74 20 2a 20 65 20 3d 20 64 2d 3e node_t * e = d->
0b20: 72 69 67 68 74 3b 0a 0a 20 20 20 20 20 20 20 20 right;..
0b30: 61 73 73 65 72 74 28 62 29 3b 0a 20 20 20 20 20 assert(b);.
0b40: 20 20 20 61 73 73 65 72 74 28 62 2d 3e 70 61 72 assert(b->par
0b50: 65 6e 74 20 3d 3d 20 64 29 3b 0a 20 20 20 20 20 ent == d);.
0b60: 20 20 20 61 73 73 65 72 74 28 4e 55 4c 4c 20 3d assert(NULL =
0b70: 3d 20 63 20 7c 7c 20 63 2d 3e 70 61 72 65 6e 74 = c || c->parent
0b80: 20 3d 3d 20 62 29 3b 0a 20 20 20 20 20 20 20 20 == b);.
0b90: 61 73 73 65 72 74 28 4e 55 4c 4c 20 3d 3d 20 64 assert(NULL == d
0ba0: 2d 3e 70 61 72 65 6e 74 20 7c 7c 20 64 2d 3e 70 ->parent || d->p
0bb0: 61 72 65 6e 74 2d 3e 6c 65 66 74 20 3d 3d 20 64 arent->left == d
0bc0: 20 7c 7c 20 64 2d 3e 70 61 72 65 6e 74 2d 3e 72 || d->parent->r
0bd0: 69 67 68 74 20 3d 3d 20 64 29 3b 0a 0a 20 20 20 ight == d);..
0be0: 20 20 20 20 20 2f 2a 20 4c 69 6e 6b 20 62 20 69 /* Link b i
0bf0: 6e 74 6f 20 64 27 73 20 70 61 72 65 6e 74 20 2a nto d's parent *
0c00: 2f 0a 20 20 20 20 20 20 20 20 62 2d 3e 70 61 72 /. b->par
0c10: 65 6e 74 20 3d 20 64 2d 3e 70 61 72 65 6e 74 3b ent = d->parent;
0c20: 0a 0a 20 20 20 20 20 20 20 20 2f 2a 20 52 65 70 .. /* Rep
0c30: 61 72 65 6e 74 20 64 20 2a 2f 0a 20 20 20 20 20 arent d */.
0c40: 20 20 20 64 2d 3e 70 61 72 65 6e 74 20 3d 20 62 d->parent = b
0c50: 3b 0a 20 20 20 20 20 20 20 20 62 2d 3e 72 69 67 ;. b->rig
0c60: 68 74 20 3d 20 64 3b 0a 0a 20 20 20 20 20 20 20 ht = d;..
0c70: 20 2f 2a 20 52 65 70 61 72 65 6e 74 20 63 20 69 /* Reparent c i
0c80: 66 20 72 65 71 75 69 72 65 64 20 2a 2f 0a 20 20 f required */.
0c90: 20 20 20 20 20 20 64 2d 3e 6c 65 66 74 20 3d 20 d->left =
0ca0: 63 3b 0a 20 20 20 20 20 20 20 20 69 66 20 28 64 c;. if (d
0cb0: 2d 3e 6c 65 66 74 29 20 7b 0a 20 20 20 20 20 20 ->left) {.
0cc0: 20 20 20 20 20 20 20 20 20 20 64 2d 3e 6c 65 66 d->lef
0cd0: 74 2d 3e 70 61 72 65 6e 74 20 3d 20 64 3b 0a 20 t->parent = d;.
0ce0: 20 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 20 }..
0cf0: 20 20 2f 2a 20 4c 69 6e 6b 20 69 6e 74 6f 20 62 /* Link into b
0d00: 20 70 61 72 65 6e 74 20 2a 2f 0a 20 20 20 20 20 parent */.
0d10: 20 20 20 69 66 20 28 62 2d 3e 70 61 72 65 6e 74 if (b->parent
0d20: 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 ) {.
0d30: 20 20 20 20 69 66 20 28 64 20 3d 3d 20 62 2d 3e if (d == b->
0d40: 70 61 72 65 6e 74 2d 3e 6c 65 66 74 29 20 7b 0a parent->left) {.
0d50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0d60: 20 20 20 20 20 20 20 20 62 2d 3e 70 61 72 65 6e b->paren
0d70: 74 2d 3e 6c 65 66 74 20 3d 20 62 3b 0a 20 20 20 t->left = b;.
0d80: 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 20 65 } e
0d90: 6c 73 65 20 7b 0a 20 20 20 20 20 20 20 20 20 20 lse {.
0da0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 62 2d b-
0db0: 3e 70 61 72 65 6e 74 2d 3e 72 69 67 68 74 20 3d >parent->right =
0dc0: 20 62 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 b;.
0dd0: 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 7d 0a }. }.
0de0: 0a 20 20 20 20 20 20 20 20 2f 2a 20 46 69 78 20 . /* Fix
0df0: 6e 6f 64 65 20 63 6f 75 6e 74 73 20 2a 2f 0a 20 node counts */.
0e00: 20 20 20 20 20 20 20 64 2d 3e 63 6f 75 6e 74 20 d->count
0e10: 3d 20 31 20 2b 20 28 28 63 29 20 3f 20 63 2d 3e = 1 + ((c) ? c->
0e20: 63 6f 75 6e 74 20 3a 20 30 29 20 2b 20 28 28 65 count : 0) + ((e
0e30: 29 20 3f 20 65 2d 3e 63 6f 75 6e 74 20 3a 20 30 ) ? e->count : 0
0e40: 29 3b 0a 20 20 20 20 20 20 20 20 62 2d 3e 63 6f );. b->co
0e50: 75 6e 74 20 3d 20 31 20 2b 20 64 2d 3e 63 6f 75 unt = 1 + d->cou
0e60: 6e 74 20 2b 20 28 28 61 29 20 3f 20 61 2d 3e 63 nt + ((a) ? a->c
0e70: 6f 75 6e 74 20 3a 20 30 29 3b 0a 0a 20 20 20 20 ount : 0);..
0e80: 20 20 20 20 61 73 73 65 72 74 28 4e 55 4c 4c 20 assert(NULL
0e90: 3d 3d 20 62 2d 3e 70 61 72 65 6e 74 20 7c 7c 20 == b->parent ||
0ea0: 62 2d 3e 70 61 72 65 6e 74 2d 3e 6c 65 66 74 20 b->parent->left
0eb0: 3d 3d 20 62 20 7c 7c 20 62 2d 3e 70 61 72 65 6e == b || b->paren
0ec0: 74 2d 3e 72 69 67 68 74 20 3d 3d 20 62 29 3b 0a t->right == b);.
0ed0: 7d 0a 0a 73 74 61 74 69 63 20 69 6e 74 20 6e 6f }..static int no
0ee0: 64 65 5f 69 73 5f 6c 65 66 74 28 20 63 6f 6e 73 de_is_left( cons
0ef0: 74 20 6e 6f 64 65 5f 74 20 2a 20 63 6f 6e 73 74 t node_t * const
0f00: 20 6e 6f 64 65 20 29 0a 7b 0a 20 20 20 20 20 20 node ).{.
0f10: 20 20 72 65 74 75 72 6e 20 28 6e 6f 64 65 2d 3e return (node->
0f20: 70 61 72 65 6e 74 20 26 26 20 6e 6f 64 65 20 3d parent && node =
0f30: 3d 20 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 2d 3e = node->parent->
0f40: 6c 65 66 74 29 3b 0a 7d 0a 0a 73 74 61 74 69 63 left);.}..static
0f50: 20 69 6e 74 20 6e 6f 64 65 5f 69 73 5f 72 69 67 int node_is_rig
0f60: 68 74 28 20 63 6f 6e 73 74 20 6e 6f 64 65 5f 74 ht( const node_t
0f70: 20 2a 20 63 6f 6e 73 74 20 6e 6f 64 65 20 29 0a * const node ).
0f80: 7b 0a 20 20 20 20 20 20 20 20 72 65 74 75 72 6e {. return
0f90: 20 28 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 20 26 (node->parent &
0fa0: 26 20 6e 6f 64 65 20 3d 3d 20 6e 6f 64 65 2d 3e & node == node->
0fb0: 70 61 72 65 6e 74 2d 3e 72 69 67 68 74 29 3b 0a parent->right);.
0fc0: 7d 0a 0a 73 74 61 74 69 63 20 76 6f 69 64 20 6e }..static void n
0fd0: 6f 64 65 5f 73 70 6c 61 79 28 20 6e 6f 64 65 5f ode_splay( node_
0fe0: 74 20 2a 20 6e 6f 64 65 20 29 0a 7b 0a 20 20 20 t * node ).{.
0ff0: 20 20 20 20 20 77 68 69 6c 65 28 6e 6f 64 65 2d while(node-
1000: 3e 70 61 72 65 6e 74 29 20 7b 0a 20 20 20 20 20 >parent) {.
1010: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 28 6e if (n
1020: 6f 64 65 5f 69 73 5f 6c 65 66 74 28 6e 6f 64 65 ode_is_left(node
1030: 29 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 )) {.
1040: 20 20 20 20 20 20 20 20 20 20 20 20 20 69 66 20 if
1050: 28 6e 6f 64 65 5f 69 73 5f 6c 65 66 74 28 6e 6f (node_is_left(no
1060: 64 65 2d 3e 70 61 72 65 6e 74 29 29 20 7b 0a 20 de->parent)) {.
1070: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1080: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6e n
1090: 6f 64 65 5f 72 6f 74 61 74 65 5f 72 69 67 68 74 ode_rotate_right
10a0: 28 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 2d 3e 70 (node->parent->p
10b0: 61 72 65 6e 74 29 3b 0a 20 20 20 20 20 20 20 20 arent);.
10c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
10d0: 20 20 20 20 20 20 20 20 6e 6f 64 65 5f 72 6f 74 node_rot
10e0: 61 74 65 5f 72 69 67 68 74 28 6e 6f 64 65 2d 3e ate_right(node->
10f0: 70 61 72 65 6e 74 29 3b 0a 20 20 20 20 20 20 20 parent);.
1100: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1110: 20 7d 20 65 6c 73 65 20 69 66 20 28 6e 6f 64 65 } else if (node
1120: 5f 69 73 5f 72 69 67 68 74 28 6e 6f 64 65 2d 3e _is_right(node->
1130: 70 61 72 65 6e 74 29 29 20 7b 0a 20 20 20 20 20 parent)) {.
1140: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1150: 20 20 20 20 20 20 20 20 20 20 20 6e 6f 64 65 5f node_
1160: 72 6f 74 61 74 65 5f 72 69 67 68 74 28 6e 6f 64 rotate_right(nod
1170: 65 2d 3e 70 61 72 65 6e 74 29 3b 0a 20 20 20 20 e->parent);.
1180: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1190: 20 20 20 20 20 20 20 20 20 20 20 20 6e 6f 64 65 node
11a0: 5f 72 6f 74 61 74 65 5f 6c 65 66 74 28 6e 6f 64 _rotate_left(nod
11b0: 65 2d 3e 70 61 72 65 6e 74 29 3b 0a 20 20 20 20 e->parent);.
11c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
11d0: 20 20 20 20 7d 20 65 6c 73 65 20 7b 0a 20 20 20 } else {.
11e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
11f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 6e 6f 64 nod
1200: 65 5f 72 6f 74 61 74 65 5f 72 69 67 68 74 28 6e e_rotate_right(n
1210: 6f 64 65 2d 3e 70 61 72 65 6e 74 29 3b 0a 20 20 ode->parent);.
1220: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1230: 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 }.
1240: 20 20 20 20 20 20 20 20 7d 20 65 6c 73 65 20 69 } else i
1250: 66 20 28 6e 6f 64 65 5f 69 73 5f 72 69 67 68 74 f (node_is_right
1260: 28 6e 6f 64 65 29 29 20 7b 0a 20 20 20 20 20 20 (node)) {.
1270: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1280: 20 20 69 66 20 28 6e 6f 64 65 5f 69 73 5f 72 69 if (node_is_ri
1290: 67 68 74 28 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 ght(node->parent
12a0: 29 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 )) {.
12b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
12c0: 20 20 20 20 20 6e 6f 64 65 5f 72 6f 74 61 74 65 node_rotate
12d0: 5f 6c 65 66 74 28 6e 6f 64 65 2d 3e 70 61 72 65 _left(node->pare
12e0: 6e 74 2d 3e 70 61 72 65 6e 74 29 3b 0a 20 20 20 nt->parent);.
12f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1300: 20 20 20 20 20 20 20 20 20 20 20 20 20 6e 6f 64 nod
1310: 65 5f 72 6f 74 61 74 65 5f 6c 65 66 74 28 6e 6f e_rotate_left(no
1320: 64 65 2d 3e 70 61 72 65 6e 74 29 3b 0a 20 20 20 de->parent);.
1330: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1340: 20 20 20 20 20 7d 20 65 6c 73 65 20 69 66 20 28 } else if (
1350: 6e 6f 64 65 5f 69 73 5f 72 69 67 68 74 28 6e 6f node_is_right(no
1360: 64 65 2d 3e 70 61 72 65 6e 74 29 29 20 7b 0a 20 de->parent)) {.
1370: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1380: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6e n
1390: 6f 64 65 5f 72 6f 74 61 74 65 5f 6c 65 66 74 28 ode_rotate_left(
13a0: 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 29 3b 0a 20 node->parent);.
13b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
13c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6e n
13d0: 6f 64 65 5f 72 6f 74 61 74 65 5f 72 69 67 68 74 ode_rotate_right
13e0: 28 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 29 3b 0a (node->parent);.
13f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1400: 20 20 20 20 20 20 20 20 7d 20 65 6c 73 65 20 7b } else {
1410: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 .
1420: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1430: 20 6e 6f 64 65 5f 72 6f 74 61 74 65 5f 6c 65 66 node_rotate_lef
1440: 74 28 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 29 3b t(node->parent);
1450: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 .
1460: 20 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 }.
1470: 20 20 20 20 20 20 20 20 20 20 20 7d 0a 20 20 20 }.
1480: 20 20 20 20 20 7d 0a 7d 0a 0a 73 74 61 74 69 63 }.}..static
1490: 20 76 6f 69 64 20 6e 6f 64 65 5f 70 72 69 6f 72 void node_prior
14a0: 69 74 69 7a 65 28 20 6e 6f 64 65 5f 74 20 2a 20 itize( node_t *
14b0: 6e 6f 64 65 20 29 0a 7b 0a 20 20 20 20 20 20 20 node ).{.
14c0: 20 6e 6f 64 65 2d 3e 70 72 69 6f 72 69 74 79 20 node->priority
14d0: 3d 20 28 28 75 69 6e 74 70 74 72 5f 74 29 6e 6f = ((uintptr_t)no
14e0: 64 65 20 2a 20 39 39 37 29 20 26 20 30 78 66 66 de * 997) & 0xff
14f0: 3b 0a 20 20 20 20 20 20 20 20 77 68 69 6c 65 28 ;. while(
1500: 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 20 26 26 20 node->parent &&
1510: 6e 6f 64 65 2d 3e 70 72 69 6f 72 69 74 79 20 3c node->priority <
1520: 20 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 2d 3e 70 node->parent->p
1530: 72 69 6f 72 69 74 79 29 20 7b 0a 20 20 20 20 20 riority) {.
1540: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 28 6e if (n
1550: 6f 64 65 5f 69 73 5f 6c 65 66 74 28 6e 6f 64 65 ode_is_left(node
1560: 29 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 )) {.
1570: 20 20 20 20 20 20 20 20 20 20 20 20 20 6e 6f 64 nod
1580: 65 5f 72 6f 74 61 74 65 5f 72 69 67 68 74 28 6e e_rotate_right(n
1590: 6f 64 65 2d 3e 70 61 72 65 6e 74 29 3b 0a 20 20 ode->parent);.
15a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 20 }
15b0: 65 6c 73 65 20 69 66 20 28 6e 6f 64 65 5f 69 73 else if (node_is
15c0: 5f 72 69 67 68 74 28 6e 6f 64 65 29 29 20 7b 0a _right(node)) {.
15d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
15e0: 20 20 20 20 20 20 20 20 6e 6f 64 65 5f 72 6f 74 node_rot
15f0: 61 74 65 5f 6c 65 66 74 28 6e 6f 64 65 2d 3e 70 ate_left(node->p
1600: 61 72 65 6e 74 29 3b 0a 20 20 20 20 20 20 20 20 arent);.
1610: 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 }.
1620: 20 20 7d 0a 7d 0a 0a 73 74 61 74 69 63 20 69 6e }.}..static in
1630: 74 20 6e 6f 64 65 5f 63 6f 75 6e 74 28 20 6e 6f t node_count( no
1640: 64 65 5f 74 20 2a 20 6e 6f 64 65 20 29 0a 7b 0a de_t * node ).{.
1650: 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 28 return (
1660: 6e 6f 64 65 29 20 3f 20 6e 6f 64 65 2d 3e 63 6f node) ? node->co
1670: 75 6e 74 20 3a 20 30 3b 0a 7d 0a 0a 73 74 61 74 unt : 0;.}..stat
1680: 69 63 20 76 6f 69 64 20 6e 6f 64 65 5f 63 6f 75 ic void node_cou
1690: 6e 74 5f 62 61 6c 61 6e 63 65 28 20 6e 6f 64 65 nt_balance( node
16a0: 5f 74 20 2a 20 6e 6f 64 65 20 29 0a 7b 0a 20 20 _t * node ).{.
16b0: 20 20 20 20 20 20 6e 6f 64 65 5f 74 20 2a 20 62 node_t * b
16c0: 61 6c 61 6e 63 65 20 3d 20 6e 6f 64 65 3b 0a 20 alance = node;.
16d0: 20 20 20 20 20 20 20 77 68 69 6c 65 28 62 61 6c while(bal
16e0: 61 6e 63 65 20 26 26 20 62 61 6c 61 6e 63 65 2d ance && balance-
16f0: 3e 70 61 72 65 6e 74 29 20 7b 0a 20 20 20 20 20 >parent) {.
1700: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 28 6e if (n
1710: 6f 64 65 5f 69 73 5f 72 69 67 68 74 28 62 61 6c ode_is_right(bal
1720: 61 6e 63 65 29 20 26 26 20 28 6e 6f 64 65 5f 63 ance) && (node_c
1730: 6f 75 6e 74 28 62 61 6c 61 6e 63 65 2d 3e 70 61 ount(balance->pa
1740: 72 65 6e 74 2d 3e 6c 65 66 74 29 20 3c 20 6e 6f rent->left) < no
1750: 64 65 5f 63 6f 75 6e 74 28 62 61 6c 61 6e 63 65 de_count(balance
1760: 2d 3e 72 69 67 68 74 29 29 20 29 20 7b 0a 20 20 ->right)) ) {.
1770: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1780: 20 20 20 20 20 20 6e 6f 64 65 5f 72 6f 74 61 74 node_rotat
1790: 65 5f 6c 65 66 74 28 62 61 6c 61 6e 63 65 2d 3e e_left(balance->
17a0: 70 61 72 65 6e 74 29 3b 0a 20 20 20 20 20 20 20 parent);.
17b0: 20 20 20 20 20 20 20 20 20 7d 20 65 6c 73 65 20 } else
17c0: 69 66 20 28 6e 6f 64 65 5f 69 73 5f 6c 65 66 74 if (node_is_left
17d0: 28 62 61 6c 61 6e 63 65 29 20 26 26 20 28 6e 6f (balance) && (no
17e0: 64 65 5f 63 6f 75 6e 74 28 62 61 6c 61 6e 63 65 de_count(balance
17f0: 2d 3e 70 61 72 65 6e 74 2d 3e 72 69 67 68 74 29 ->parent->right)
1800: 20 3c 20 6e 6f 64 65 5f 63 6f 75 6e 74 28 62 61 < node_count(ba
1810: 6c 61 6e 63 65 2d 3e 6c 65 66 74 29 29 20 29 20 lance->left)) )
1820: 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 {.
1830: 20 20 20 20 20 20 20 20 20 20 6e 6f 64 65 5f 72 node_r
1840: 6f 74 61 74 65 5f 72 69 67 68 74 28 62 61 6c 61 otate_right(bala
1850: 6e 63 65 2d 3e 70 61 72 65 6e 74 29 3b 0a 20 20 nce->parent);.
1860: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a }.
1870: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1880: 62 61 6c 61 6e 63 65 20 3d 20 62 61 6c 61 6e 63 balance = balanc
1890: 65 2d 3e 70 61 72 65 6e 74 3b 0a 20 20 20 20 20 e->parent;.
18a0: 20 20 20 7d 0a 7d 0a 0a 73 74 61 74 69 63 20 76 }.}..static v
18b0: 6f 69 64 20 6e 6f 64 65 5f 73 69 6d 70 6c 65 5f oid node_simple_
18c0: 62 61 6c 61 6e 63 65 28 20 6e 6f 64 65 5f 74 20 balance( node_t
18d0: 2a 20 6e 6f 64 65 20 29 0a 7b 0a 09 6e 6f 64 65 * node ).{..node
18e0: 5f 74 20 2a 20 70 61 72 65 6e 74 20 3d 20 6e 6f _t * parent = no
18f0: 64 65 2d 3e 70 61 72 65 6e 74 3b 0a 0a 09 77 68 de->parent;...wh
1900: 69 6c 65 28 70 61 72 65 6e 74 29 20 7b 0a 09 09 ile(parent) {...
1910: 69 6e 74 20 69 20 3d 20 30 3b 0a 0a 09 09 69 20 int i = 0;....i
1920: 7c 3d 20 28 70 61 72 65 6e 74 2d 3e 6c 65 66 74 |= (parent->left
1930: 20 21 3d 20 30 29 3b 0a 09 09 69 20 3c 3c 3d 20 != 0);...i <<=
1940: 31 3b 0a 09 09 69 20 7c 3d 20 28 70 61 72 65 6e 1;...i |= (paren
1950: 74 2d 3e 72 69 67 68 74 20 21 3d 20 30 29 3b 0a t->right != 0);.
1960: 09 09 69 20 3c 3c 3d 20 31 3b 0a 09 09 69 20 7c ..i <<= 1;...i |
1970: 3d 20 28 6e 6f 64 65 2d 3e 6c 65 66 74 20 21 3d = (node->left !=
1980: 20 30 29 3b 0a 09 09 69 20 3c 3c 3d 20 31 3b 0a 0);...i <<= 1;.
1990: 09 09 69 20 7c 3d 20 28 6e 6f 64 65 2d 3e 72 69 ..i |= (node->ri
19a0: 67 68 74 20 21 3d 20 30 29 3b 0a 0a 09 09 73 77 ght != 0);....sw
19b0: 69 74 63 68 28 69 29 20 7b 0a 09 09 2f 2a 20 31 itch(i) {.../* 1
19c0: 30 30 31 20 2a 2f 0a 09 09 63 61 73 65 20 39 3a 001 */...case 9:
19d0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 .
19e0: 20 20 20 20 20 20 20 20 20 6e 6f 64 65 5f 72 6f node_ro
19f0: 74 61 74 65 5f 6c 65 66 74 28 6e 6f 64 65 29 3b tate_left(node);
1a00: 0a 09 09 2f 2a 20 31 30 31 30 20 2a 2f 0a 09 09 .../* 1010 */...
1a10: 63 61 73 65 20 31 30 3a 0a 20 20 20 20 20 20 20 case 10:.
1a20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1a30: 20 6e 6f 64 65 5f 72 6f 74 61 74 65 5f 72 69 67 node_rotate_rig
1a40: 68 74 28 70 61 72 65 6e 74 29 3b 0a 09 09 09 62 ht(parent);....b
1a50: 72 65 61 6b 3b 0a 09 09 2f 2a 20 30 31 31 30 20 reak;.../* 0110
1a60: 2a 2f 0a 09 09 63 61 73 65 20 36 3a 0a 20 20 20 */...case 6:.
1a70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1a80: 20 20 20 20 20 6e 6f 64 65 5f 72 6f 74 61 74 65 node_rotate
1a90: 5f 72 69 67 68 74 28 6e 6f 64 65 29 3b 0a 09 09 _right(node);...
1aa0: 2f 2a 20 30 31 30 31 20 2a 2f 0a 09 09 63 61 73 /* 0101 */...cas
1ab0: 65 20 35 3a 0a 20 20 20 20 20 20 20 20 20 20 20 e 5:.
1ac0: 20 20 20 20 20 20 20 20 20 20 20 20 20 6e 6f 64 nod
1ad0: 65 5f 72 6f 74 61 74 65 5f 6c 65 66 74 28 70 61 e_rotate_left(pa
1ae0: 72 65 6e 74 29 3b 0a 09 09 09 62 72 65 61 6b 3b rent);....break;
1af0: 0a 09 09 7d 0a 09 09 6e 6f 64 65 20 3d 20 70 61 ...}...node = pa
1b00: 72 65 6e 74 3b 0a 09 09 70 61 72 65 6e 74 20 3d rent;...parent =
1b10: 20 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 3b 0a 09 node->parent;..
1b20: 7d 0a 7d 0a 0a 73 74 61 74 69 63 20 6e 6f 64 65 }.}..static node
1b30: 5f 74 20 2a 20 74 72 65 65 5f 6e 6f 64 65 5f 6e _t * tree_node_n
1b40: 65 77 28 20 6e 6f 64 65 5f 74 20 2a 20 70 61 72 ew( node_t * par
1b50: 65 6e 74 2c 20 6d 61 70 5f 6b 65 79 20 6b 65 79 ent, map_key key
1b60: 2c 20 6d 61 70 5f 64 61 74 61 20 64 61 74 61 20 , map_data data
1b70: 29 0a 7b 0a 20 20 20 20 20 20 20 20 6e 6f 64 65 ).{. node
1b80: 5f 74 20 2a 20 6e 6f 64 65 20 3d 20 73 6c 61 62 _t * node = slab
1b90: 5f 61 6c 6c 6f 63 28 6e 6f 64 65 73 29 3b 0a 20 _alloc(nodes);.
1ba0: 20 20 20 20 20 20 20 6e 6f 64 65 2d 3e 6b 65 79 node->key
1bb0: 20 3d 20 6b 65 79 3b 0a 20 20 20 20 20 20 20 20 = key;.
1bc0: 6e 6f 64 65 2d 3e 64 61 74 61 20 3d 20 64 61 74 node->data = dat
1bd0: 61 3b 0a 20 20 20 20 20 20 20 20 6e 6f 64 65 2d a;. node-
1be0: 3e 70 61 72 65 6e 74 20 3d 20 70 61 72 65 6e 74 >parent = parent
1bf0: 3b 0a 20 20 20 20 20 20 20 20 6e 6f 64 65 2d 3e ;. node->
1c00: 63 6f 75 6e 74 20 3d 20 31 3b 0a 20 20 20 20 20 count = 1;.
1c10: 20 20 20 77 68 69 6c 65 28 70 61 72 65 6e 74 29 while(parent)
1c20: 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 {.
1c30: 20 20 20 70 61 72 65 6e 74 2d 3e 63 6f 75 6e 74 parent->count
1c40: 2b 2b 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 ++;.
1c50: 20 20 20 20 70 61 72 65 6e 74 20 3d 20 70 61 72 parent = par
1c60: 65 6e 74 2d 3e 70 61 72 65 6e 74 3b 0a 20 20 20 ent->parent;.
1c70: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 6e }. n
1c80: 6f 64 65 2d 3e 6c 65 66 74 20 3d 20 6e 6f 64 65 ode->left = node
1c90: 2d 3e 72 69 67 68 74 20 3d 20 4e 55 4c 4c 3b 0a ->right = NULL;.
1ca0: 0a 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 . return
1cb0: 6e 6f 64 65 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 node;.}..static
1cc0: 76 6f 69 64 20 74 72 65 65 5f 64 65 73 74 72 6f void tree_destro
1cd0: 79 28 20 63 6f 6e 73 74 20 6d 61 70 5f 74 20 2a y( const map_t *
1ce0: 20 6d 61 70 20 29 0a 7b 0a 7d 0a 0a 73 74 61 74 map ).{.}..stat
1cf0: 69 63 20 6e 6f 64 65 5f 74 20 2a 20 6e 6f 64 65 ic node_t * node
1d00: 5f 70 72 65 76 28 20 6e 6f 64 65 5f 74 20 2a 20 _prev( node_t *
1d10: 63 75 72 72 65 6e 74 20 29 0a 7b 0a 09 6e 6f 64 current ).{..nod
1d20: 65 5f 74 20 2a 20 6e 6f 64 65 20 3d 20 63 75 72 e_t * node = cur
1d30: 72 65 6e 74 3b 0a 0a 09 2f 2a 20 43 61 73 65 20 rent;.../* Case
1d40: 31 20 2d 20 57 65 20 68 61 76 65 20 61 20 6c 65 1 - We have a le
1d50: 66 74 20 6e 6f 64 65 2c 20 6e 6f 64 65 73 20 77 ft node, nodes w
1d60: 68 69 63 68 20 61 72 65 20 61 66 74 65 72 20 6f hich are after o
1d70: 75 72 20 70 61 72 65 6e 74 20 2a 2f 0a 09 69 66 ur parent */..if
1d80: 20 28 6e 6f 64 65 2d 3e 6c 65 66 74 29 20 7b 0a (node->left) {.
1d90: 09 09 6e 6f 64 65 20 3d 20 6e 6f 64 65 2d 3e 6c ..node = node->l
1da0: 65 66 74 3b 0a 09 09 77 68 69 6c 65 28 6e 6f 64 eft;...while(nod
1db0: 65 2d 3e 72 69 67 68 74 29 20 7b 0a 09 09 09 6e e->right) {....n
1dc0: 6f 64 65 20 3d 20 6e 6f 64 65 2d 3e 72 69 67 68 ode = node->righ
1dd0: 74 3b 0a 09 09 7d 0a 0a 09 09 72 65 74 75 72 6e t;...}....return
1de0: 20 6e 6f 64 65 3b 0a 09 7d 0a 0a 09 77 68 69 6c node;..}...whil
1df0: 65 28 6e 6f 64 65 5f 69 73 5f 6c 65 66 74 28 6e e(node_is_left(n
1e00: 6f 64 65 29 29 20 7b 0a 09 09 6e 6f 64 65 20 3d ode)) {...node =
1e10: 20 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 3b 0a 09 node->parent;..
1e20: 7d 0a 0a 09 2f 2a 20 43 61 73 65 20 32 20 2d 20 }.../* Case 2 -
1e30: 57 65 27 72 65 20 61 20 72 69 67 68 74 20 6e 6f We're a right no
1e40: 64 65 2c 20 6f 75 72 20 70 61 72 65 6e 74 20 69 de, our parent i
1e50: 73 20 70 72 65 76 69 6f 75 73 20 2a 2f 0a 09 69 s previous */..i
1e60: 66 20 28 6e 6f 64 65 5f 69 73 5f 72 69 67 68 74 f (node_is_right
1e70: 28 6e 6f 64 65 29 29 20 7b 0a 09 09 72 65 74 75 (node)) {...retu
1e80: 72 6e 20 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 3b rn node->parent;
1e90: 0a 09 7d 0a 0a 09 72 65 74 75 72 6e 20 30 3b 0a ..}...return 0;.
1ea0: 7d 0a 0a 73 74 61 74 69 63 20 63 6f 6e 73 74 20 }..static const
1eb0: 6e 6f 64 65 5f 74 20 2a 20 6e 6f 64 65 5f 6e 65 node_t * node_ne
1ec0: 78 74 28 20 63 6f 6e 73 74 20 6e 6f 64 65 5f 74 xt( const node_t
1ed0: 20 2a 20 63 6f 6e 73 74 20 63 75 72 72 65 6e 74 * const current
1ee0: 20 29 0a 7b 0a 09 63 6f 6e 73 74 20 6e 6f 64 65 ).{..const node
1ef0: 5f 74 20 2a 20 6e 6f 64 65 20 3d 20 63 75 72 72 _t * node = curr
1f00: 65 6e 74 3b 0a 0a 09 2f 2a 20 43 61 73 65 20 31 ent;.../* Case 1
1f10: 20 2d 20 57 65 20 68 61 76 65 20 61 20 72 69 67 - We have a rig
1f20: 68 74 20 6e 6f 64 65 2c 20 6e 6f 64 65 73 20 77 ht node, nodes w
1f30: 68 69 63 68 20 61 72 65 20 62 65 66 6f 72 65 20 hich are before
1f40: 6f 75 72 20 70 61 72 65 6e 74 20 2a 2f 0a 09 69 our parent */..i
1f50: 66 20 28 6e 6f 64 65 2d 3e 72 69 67 68 74 29 20 f (node->right)
1f60: 7b 0a 09 09 6e 6f 64 65 20 3d 20 6e 6f 64 65 2d {...node = node-
1f70: 3e 72 69 67 68 74 3b 0a 09 09 77 68 69 6c 65 28 >right;...while(
1f80: 6e 6f 64 65 2d 3e 6c 65 66 74 29 20 7b 0a 09 09 node->left) {...
1f90: 09 6e 6f 64 65 20 3d 20 6e 6f 64 65 2d 3e 6c 65 .node = node->le
1fa0: 66 74 3b 0a 09 09 7d 0a 0a 09 09 72 65 74 75 72 ft;...}....retur
1fb0: 6e 20 6e 6f 64 65 3b 0a 09 7d 0a 0a 09 77 68 69 n node;..}...whi
1fc0: 6c 65 28 6e 6f 64 65 5f 69 73 5f 72 69 67 68 74 le(node_is_right
1fd0: 28 6e 6f 64 65 29 29 20 7b 0a 09 09 6e 6f 64 65 (node)) {...node
1fe0: 20 3d 20 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 3b = node->parent;
1ff0: 0a 09 7d 0a 0a 09 2f 2a 20 43 61 73 65 20 32 20 ..}.../* Case 2
2000: 2d 20 57 65 27 72 65 20 61 20 6c 65 66 74 20 6e - We're a left n
2010: 6f 64 65 2c 20 6f 75 72 20 70 61 72 65 6e 74 20 ode, our parent
2020: 69 73 20 6e 65 78 74 20 2a 2f 0a 09 69 66 20 28 is next */..if (
2030: 6e 6f 64 65 5f 69 73 5f 6c 65 66 74 28 6e 6f 64 node_is_left(nod
2040: 65 29 29 20 7b 0a 09 09 72 65 74 75 72 6e 20 6e e)) {...return n
2050: 6f 64 65 2d 3e 70 61 72 65 6e 74 3b 0a 09 7d 0a ode->parent;..}.
2060: 0a 09 72 65 74 75 72 6e 20 30 3b 0a 7d 0a 0a 23 ..return 0;.}..#
2070: 69 66 20 30 0a 73 74 61 74 69 63 20 76 6f 69 64 if 0.static void
2080: 20 74 72 65 65 5f 77 61 6c 6b 5f 6e 6f 64 65 28 tree_walk_node(
2090: 20 6e 6f 64 65 5f 74 20 2a 20 6e 6f 64 65 2c 20 node_t * node,
20a0: 77 61 6c 6b 5f 66 75 6e 63 20 66 75 6e 63 2c 20 walk_func func,
20b0: 76 6f 69 64 20 2a 20 70 20 29 0a 7b 0a 20 20 20 void * p ).{.
20c0: 20 20 20 20 20 69 66 20 28 4e 55 4c 4c 20 3d 3d if (NULL ==
20d0: 20 6e 6f 64 65 29 20 7b 0a 20 20 20 20 20 20 20 node) {.
20e0: 20 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 3b return;
20f0: 0a 20 20 20 20 20 20 20 20 7d 0a 0a 09 2f 2a 20 . }.../*
2100: 46 69 6e 64 20 6c 65 66 74 20 6d 6f 73 74 20 6e Find left most n
2110: 6f 64 65 20 2a 2f 0a 09 77 68 69 6c 65 28 6e 6f ode */..while(no
2120: 64 65 2d 3e 6c 65 66 74 29 20 7b 0a 09 09 6e 6f de->left) {...no
2130: 64 65 20 3d 20 6e 6f 64 65 2d 3e 6c 65 66 74 3b de = node->left;
2140: 0a 09 7d 0a 0a 09 2f 2a 20 53 74 65 70 20 74 68 ..}.../* Step th
2150: 72 6f 75 67 68 20 61 6c 6c 20 6e 6f 64 65 73 20 rough all nodes
2160: 2a 2f 0a 09 77 68 69 6c 65 28 6e 6f 64 65 29 20 */..while(node)
2170: 7b 0a 09 09 66 75 6e 63 28 70 2c 20 6e 6f 64 65 {...func(p, node
2180: 2d 3e 6b 65 79 2c 20 6e 6f 64 65 2d 3e 64 61 74 ->key, node->dat
2190: 61 29 3b 0a 09 09 6e 6f 64 65 20 3d 20 6e 6f 64 a);...node = nod
21a0: 65 5f 6e 65 78 74 28 6e 6f 64 65 29 3b 0a 09 7d e_next(node);..}
21b0: 0a 7d 0a 23 65 6e 64 69 66 0a 0a 73 74 61 74 69 .}.#endif..stati
21c0: 63 20 6e 6f 64 65 5f 74 20 2a 20 74 72 65 65 5f c node_t * tree_
21d0: 6e 6f 64 65 5f 66 69 72 73 74 28 74 72 65 65 5f node_first(tree_
21e0: 74 20 2a 20 74 72 65 65 29 0a 7b 0a 09 6e 6f 64 t * tree).{..nod
21f0: 65 5f 74 20 2a 20 6e 6f 64 65 20 3d 20 74 72 65 e_t * node = tre
2200: 65 2d 3e 72 6f 6f 74 3b 0a 0a 09 69 66 20 28 6e e->root;...if (n
2210: 6f 64 65 29 20 7b 0a 09 09 77 68 69 6c 65 28 6e ode) {...while(n
2220: 6f 64 65 2d 3e 6c 65 66 74 29 20 7b 0a 09 09 09 ode->left) {....
2230: 6e 6f 64 65 20 3d 20 6e 6f 64 65 2d 3e 6c 65 66 node = node->lef
2240: 74 3b 0a 09 09 7d 0a 09 7d 0a 0a 09 72 65 74 75 t;...}..}...retu
2250: 72 6e 20 6e 6f 64 65 3b 0a 7d 0a 0a 73 74 61 74 rn node;.}..stat
2260: 69 63 20 6e 6f 64 65 5f 74 20 2a 20 74 72 65 65 ic node_t * tree
2270: 5f 6e 6f 64 65 5f 6c 61 73 74 28 74 72 65 65 5f _node_last(tree_
2280: 74 20 2a 20 74 72 65 65 29 0a 7b 0a 09 6e 6f 64 t * tree).{..nod
2290: 65 5f 74 20 2a 20 6e 6f 64 65 20 3d 20 74 72 65 e_t * node = tre
22a0: 65 2d 3e 72 6f 6f 74 3b 0a 0a 09 69 66 20 28 6e e->root;...if (n
22b0: 6f 64 65 29 20 7b 0a 09 09 77 68 69 6c 65 28 6e ode) {...while(n
22c0: 6f 64 65 2d 3e 72 69 67 68 74 29 20 7b 0a 09 09 ode->right) {...
22d0: 09 6e 6f 64 65 20 3d 20 6e 6f 64 65 2d 3e 72 69 .node = node->ri
22e0: 67 68 74 3b 0a 09 09 7d 0a 09 7d 0a 0a 09 72 65 ght;...}..}...re
22f0: 74 75 72 6e 20 6e 6f 64 65 3b 0a 7d 0a 0a 73 74 turn node;.}..st
2300: 61 74 69 63 20 76 6f 69 64 20 74 72 65 65 5f 77 atic void tree_w
2310: 61 6c 6b 5f 6e 6f 64 65 73 28 20 63 6f 6e 73 74 alk_nodes( const
2320: 20 6e 6f 64 65 5f 74 20 2a 20 73 74 61 72 74 2c node_t * start,
2330: 20 63 6f 6e 73 74 20 6e 6f 64 65 5f 74 20 2a 20 const node_t *
2340: 65 6e 64 2c 20 63 6f 6e 73 74 20 77 61 6c 6b 5f end, const walk_
2350: 66 75 6e 63 20 66 75 6e 63 2c 20 63 6f 6e 73 74 func func, const
2360: 20 76 6f 69 64 20 2a 20 70 29 0a 7b 0a 09 63 6f void * p).{..co
2370: 6e 73 74 20 6e 6f 64 65 5f 74 20 2a 20 6e 6f 64 nst node_t * nod
2380: 65 20 3d 20 73 74 61 72 74 3b 0a 09 77 68 69 6c e = start;..whil
2390: 65 20 28 6e 6f 64 65 29 20 7b 0a 09 09 66 75 6e e (node) {...fun
23a0: 63 28 70 2c 20 6e 6f 64 65 2d 3e 6b 65 79 2c 20 c(p, node->key,
23b0: 6e 6f 64 65 2d 3e 64 61 74 61 29 3b 0a 09 09 6e node->data);...n
23c0: 6f 64 65 20 3d 20 28 6e 6f 64 65 20 3d 3d 20 65 ode = (node == e
23d0: 6e 64 29 20 3f 20 30 20 3a 20 6e 6f 64 65 5f 6e nd) ? 0 : node_n
23e0: 65 78 74 28 6e 6f 64 65 29 3b 0a 09 7d 0a 7d 0a ext(node);..}.}.
23f0: 0a 76 6f 69 64 20 74 72 65 65 5f 77 61 6c 6b 28 .void tree_walk(
2400: 20 63 6f 6e 73 74 20 6d 61 70 5f 74 20 2a 20 6d const map_t * m
2410: 61 70 2c 20 63 6f 6e 73 74 20 77 61 6c 6b 5f 66 ap, const walk_f
2420: 75 6e 63 20 66 75 6e 63 2c 20 63 6f 6e 73 74 20 unc func, const
2430: 76 6f 69 64 20 2a 20 70 20 29 0a 7b 0a 20 20 20 void * p ).{.
2440: 20 20 20 20 20 74 72 65 65 5f 74 20 2a 20 74 72 tree_t * tr
2450: 65 65 20 3d 20 63 6f 6e 74 61 69 6e 65 72 5f 6f ee = container_o
2460: 66 28 6d 61 70 2c 20 74 72 65 65 5f 74 2c 20 6d f(map, tree_t, m
2470: 61 70 29 3b 0a 09 6e 6f 64 65 5f 74 20 2a 20 73 ap);..node_t * s
2480: 74 61 72 74 20 3d 20 74 72 65 65 5f 6e 6f 64 65 tart = tree_node
2490: 5f 66 69 72 73 74 28 74 72 65 65 29 3b 0a 09 6e _first(tree);..n
24a0: 6f 64 65 5f 74 20 2a 20 65 6e 64 20 3d 20 74 72 ode_t * end = tr
24b0: 65 65 5f 6e 6f 64 65 5f 6c 61 73 74 28 74 72 65 ee_node_last(tre
24c0: 65 29 3b 0a 0a 20 20 20 20 20 20 20 20 74 72 65 e);.. tre
24d0: 65 5f 77 61 6c 6b 5f 6e 6f 64 65 73 28 73 74 61 e_walk_nodes(sta
24e0: 72 74 2c 20 65 6e 64 2c 20 66 75 6e 63 2c 20 70 rt, end, func, p
24f0: 29 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 63 6f 6e );.}..static con
2500: 73 74 20 6e 6f 64 65 5f 74 20 2a 20 74 72 65 65 st node_t * tree
2510: 5f 67 65 74 5f 6e 6f 64 65 28 20 74 72 65 65 5f _get_node( tree_
2520: 74 20 2a 20 74 72 65 65 2c 20 6d 61 70 5f 6b 65 t * tree, map_ke
2530: 79 20 6b 65 79 2c 20 6d 61 70 5f 65 71 5f 74 65 y key, map_eq_te
2540: 73 74 20 63 6f 6e 64 20 29 3b 0a 76 6f 69 64 20 st cond );.void
2550: 74 72 65 65 5f 77 61 6c 6b 5f 72 61 6e 67 65 28 tree_walk_range(
2560: 20 63 6f 6e 73 74 20 6d 61 70 5f 74 20 2a 20 6d const map_t * m
2570: 61 70 2c 20 77 61 6c 6b 5f 66 75 6e 63 20 66 75 ap, walk_func fu
2580: 6e 63 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a nc, const void *
2590: 20 70 2c 20 6d 61 70 5f 6b 65 79 20 66 72 6f 6d p, map_key from
25a0: 2c 20 6d 61 70 5f 6b 65 79 20 74 6f 20 29 0a 7b , map_key to ).{
25b0: 0a 20 20 20 20 20 20 20 20 74 72 65 65 5f 74 20 . tree_t
25c0: 2a 20 74 72 65 65 20 3d 20 63 6f 6e 74 61 69 6e * tree = contain
25d0: 65 72 5f 6f 66 28 6d 61 70 2c 20 74 72 65 65 5f er_of(map, tree_
25e0: 74 2c 20 6d 61 70 29 3b 0a 09 63 6f 6e 73 74 20 t, map);..const
25f0: 6e 6f 64 65 5f 74 20 2a 20 73 74 61 72 74 20 3d node_t * start =
2600: 20 28 66 72 6f 6d 29 20 3f 20 74 72 65 65 5f 67 (from) ? tree_g
2610: 65 74 5f 6e 6f 64 65 28 74 72 65 65 2c 20 66 72 et_node(tree, fr
2620: 6f 6d 2c 20 4d 41 50 5f 47 45 29 20 3a 20 74 72 om, MAP_GE) : tr
2630: 65 65 5f 6e 6f 64 65 5f 66 69 72 73 74 28 74 72 ee_node_first(tr
2640: 65 65 29 3b 0a 09 63 6f 6e 73 74 20 6e 6f 64 65 ee);..const node
2650: 5f 74 20 2a 20 65 6e 64 20 3d 20 28 74 6f 29 20 _t * end = (to)
2660: 3f 20 74 72 65 65 5f 67 65 74 5f 6e 6f 64 65 28 ? tree_get_node(
2670: 74 72 65 65 2c 20 74 6f 2c 20 4d 41 50 5f 4c 54 tree, to, MAP_LT
2680: 29 20 3a 20 74 72 65 65 5f 6e 6f 64 65 5f 6c 61 ) : tree_node_la
2690: 73 74 28 74 72 65 65 29 3b 0a 0a 20 20 20 20 20 st(tree);..
26a0: 20 20 20 74 72 65 65 5f 77 61 6c 6b 5f 6e 6f 64 tree_walk_nod
26b0: 65 73 28 73 74 61 72 74 2c 20 65 6e 64 2c 20 66 es(start, end, f
26c0: 75 6e 63 2c 20 70 29 3b 0a 7d 0a 0a 73 74 61 74 unc, p);.}..stat
26d0: 69 63 20 76 6f 69 64 20 6e 6f 64 65 5f 76 65 72 ic void node_ver
26e0: 69 66 79 28 20 74 72 65 65 5f 74 20 2a 20 74 72 ify( tree_t * tr
26f0: 65 65 2c 20 6e 6f 64 65 5f 74 20 2a 20 6e 6f 64 ee, node_t * nod
2700: 65 20 29 0a 7b 0a 09 69 66 20 28 31 29 20 7b 0a e ).{..if (1) {.
2710: 09 09 69 66 20 28 4e 55 4c 4c 20 3d 3d 20 6e 6f ..if (NULL == no
2720: 64 65 29 20 7b 0a 09 09 09 72 65 74 75 72 6e 3b de) {....return;
2730: 0a 09 09 7d 0a 0a 09 09 69 66 20 28 6e 6f 64 65 ...}....if (node
2740: 2d 3e 63 6f 75 6e 74 20 3d 3d 20 31 29 20 7b 0a ->count == 1) {.
2750: 09 09 09 61 73 73 65 72 74 28 30 20 3d 3d 20 6e ...assert(0 == n
2760: 6f 64 65 2d 3e 6c 65 66 74 29 3b 0a 09 09 09 61 ode->left);....a
2770: 73 73 65 72 74 28 30 20 3d 3d 20 6e 6f 64 65 2d ssert(0 == node-
2780: 3e 72 69 67 68 74 29 3b 0a 09 09 7d 0a 0a 09 09 >right);...}....
2790: 69 6e 74 20 63 6f 75 6e 74 20 3d 20 31 3b 0a 0a int count = 1;..
27a0: 09 09 2f 2a 20 43 68 65 63 6b 20 63 68 69 6c 64 ../* Check child
27b0: 20 6c 69 6e 6b 61 67 65 20 2a 2f 0a 09 09 69 66 linkage */...if
27c0: 20 28 6e 6f 64 65 2d 3e 6c 65 66 74 29 20 7b 0a (node->left) {.
27d0: 09 09 09 63 6f 75 6e 74 20 2b 3d 20 6e 6f 64 65 ...count += node
27e0: 2d 3e 6c 65 66 74 2d 3e 63 6f 75 6e 74 3b 0a 09 ->left->count;..
27f0: 09 09 61 73 73 65 72 74 28 6e 6f 64 65 20 3d 3d ..assert(node ==
2800: 20 6e 6f 64 65 2d 3e 6c 65 66 74 2d 3e 70 61 72 node->left->par
2810: 65 6e 74 29 3b 0a 09 09 09 6e 6f 64 65 5f 76 65 ent);....node_ve
2820: 72 69 66 79 28 74 72 65 65 2c 20 6e 6f 64 65 2d rify(tree, node-
2830: 3e 6c 65 66 74 29 3b 0a 09 09 7d 0a 09 09 69 66 >left);...}...if
2840: 20 28 6e 6f 64 65 2d 3e 72 69 67 68 74 29 20 7b (node->right) {
2850: 0a 09 09 09 63 6f 75 6e 74 20 2b 3d 20 6e 6f 64 ....count += nod
2860: 65 2d 3e 72 69 67 68 74 2d 3e 63 6f 75 6e 74 3b e->right->count;
2870: 0a 09 09 09 61 73 73 65 72 74 28 6e 6f 64 65 20 ....assert(node
2880: 3d 3d 20 6e 6f 64 65 2d 3e 72 69 67 68 74 2d 3e == node->right->
2890: 70 61 72 65 6e 74 29 3b 0a 09 09 09 6e 6f 64 65 parent);....node
28a0: 5f 76 65 72 69 66 79 28 74 72 65 65 2c 20 6e 6f _verify(tree, no
28b0: 64 65 2d 3e 72 69 67 68 74 29 3b 0a 09 09 7d 0a de->right);...}.
28c0: 0a 09 09 61 73 73 65 72 74 28 63 6f 75 6e 74 20 ...assert(count
28d0: 3d 3d 20 6e 6f 64 65 2d 3e 63 6f 75 6e 74 29 3b == node->count);
28e0: 0a 09 7d 0a 7d 0a 0a 73 74 61 74 69 63 20 76 6f ..}.}..static vo
28f0: 69 64 20 74 72 65 65 5f 76 65 72 69 66 79 28 20 id tree_verify(
2900: 74 72 65 65 5f 74 20 2a 20 74 72 65 65 2c 20 6e tree_t * tree, n
2910: 6f 64 65 5f 74 20 2a 20 6e 6f 64 65 20 29 0a 7b ode_t * node ).{
2920: 0a 09 69 66 20 28 31 29 20 7b 0a 09 09 2f 2a 0a ..if (1) {.../*.
2930: 09 09 20 2a 20 49 66 20 77 65 27 72 65 20 70 61 .. * If we're pa
2940: 73 73 65 64 20 61 20 6e 6f 64 65 2c 20 63 68 65 ssed a node, che
2950: 63 6b 20 74 68 61 74 20 74 68 65 20 6e 6f 64 65 ck that the node
2960: 0a 09 09 20 2a 20 69 73 20 6c 69 6e 6b 65 64 20 ... * is linked
2970: 74 6f 20 74 68 65 20 72 6f 6f 74 2e 0a 09 09 20 to the root....
2980: 2a 2f 0a 09 09 69 66 20 28 6e 6f 64 65 29 20 7b */...if (node) {
2990: 0a 09 09 09 6e 6f 64 65 5f 74 20 2a 20 72 6f 6f ....node_t * roo
29a0: 74 20 3d 20 6e 6f 64 65 3b 0a 0a 09 09 09 77 68 t = node;.....wh
29b0: 69 6c 65 28 72 6f 6f 74 2d 3e 70 61 72 65 6e 74 ile(root->parent
29c0: 29 20 7b 0a 09 09 09 09 72 6f 6f 74 20 3d 20 72 ) {.....root = r
29d0: 6f 6f 74 2d 3e 70 61 72 65 6e 74 3b 0a 09 09 09 oot->parent;....
29e0: 7d 0a 0a 09 09 09 61 73 73 65 72 74 28 74 72 65 }.....assert(tre
29f0: 65 2d 3e 72 6f 6f 74 20 3d 3d 20 72 6f 6f 74 29 e->root == root)
2a00: 3b 0a 09 09 7d 0a 0a 09 09 2f 2a 0a 09 09 20 2a ;...}..../*... *
2a10: 20 43 68 65 63 6b 20 6e 6f 64 65 20 63 6f 75 6e Check node coun
2a20: 74 73 0a 09 09 20 2a 2f 0a 09 09 69 66 20 28 74 ts... */...if (t
2a30: 72 65 65 2d 3e 72 6f 6f 74 29 20 7b 0a 09 09 09 ree->root) {....
2a40: 61 73 73 65 72 74 28 74 72 65 65 2d 3e 72 6f 6f assert(tree->roo
2a50: 74 2d 3e 63 6f 75 6e 74 20 3d 3d 20 6e 6f 64 65 t->count == node
2a60: 5f 63 6f 75 6e 74 28 74 72 65 65 2d 3e 72 6f 6f _count(tree->roo
2a70: 74 29 29 3b 0a 09 09 09 61 73 73 65 72 74 28 74 t));....assert(t
2a80: 72 65 65 2d 3e 72 6f 6f 74 2d 3e 70 61 72 65 6e ree->root->paren
2a90: 74 20 3d 3d 20 30 29 3b 0a 09 09 7d 0a 0a 09 09 t == 0);...}....
2aa0: 2f 2a 0a 09 09 20 2a 20 56 65 72 69 66 79 20 74 /*... * Verify t
2ab0: 68 65 20 72 6f 6f 74 20 6e 6f 64 65 2c 20 61 6e he root node, an
2ac0: 64 20 76 65 72 69 66 79 20 74 68 65 20 72 65 73 d verify the res
2ad0: 74 20 6f 66 20 74 68 65 0a 09 09 20 2a 20 74 72 t of the... * tr
2ae0: 65 65 2e 0a 09 09 20 2a 2f 0a 09 09 6e 6f 64 65 ee.... */...node
2af0: 5f 76 65 72 69 66 79 28 74 72 65 65 2c 20 74 72 _verify(tree, tr
2b00: 65 65 2d 3e 72 6f 6f 74 29 3b 0a 09 7d 0a 7d 0a ee->root);..}.}.
2b10: 0a 73 74 61 74 69 63 20 6d 61 70 5f 64 61 74 61 .static map_data
2b20: 20 74 72 65 65 5f 70 75 74 28 20 63 6f 6e 73 74 tree_put( const
2b30: 20 6d 61 70 5f 74 20 2a 20 6d 61 70 2c 20 6d 61 map_t * map, ma
2b40: 70 5f 6b 65 79 20 6b 65 79 2c 20 6d 61 70 5f 64 p_key key, map_d
2b50: 61 74 61 20 64 61 74 61 20 29 0a 7b 0a 20 20 20 ata data ).{.
2b60: 20 20 20 20 20 74 72 65 65 5f 74 20 2a 20 74 72 tree_t * tr
2b70: 65 65 20 3d 20 63 6f 6e 74 61 69 6e 65 72 5f 6f ee = container_o
2b80: 66 28 6d 61 70 2c 20 74 72 65 65 5f 74 2c 20 6d f(map, tree_t, m
2b90: 61 70 29 3b 0a 20 20 20 20 20 20 20 20 6e 6f 64 ap);. nod
2ba0: 65 5f 74 20 2a 20 6e 6f 64 65 20 3d 20 74 72 65 e_t * node = tre
2bb0: 65 2d 3e 72 6f 6f 74 3b 0a 20 20 20 20 20 20 20 e->root;.
2bc0: 20 6e 6f 64 65 5f 74 20 2a 20 70 61 72 65 6e 74 node_t * parent
2bd0: 20 3d 20 4e 55 4c 4c 3b 0a 20 20 20 20 20 20 20 = NULL;.
2be0: 20 6e 6f 64 65 5f 74 20 2a 20 2a 20 70 6c 61 73 node_t * * plas
2bf0: 74 20 3d 20 26 74 72 65 65 2d 3e 72 6f 6f 74 3b t = &tree->root;
2c00: 0a 0a 20 20 20 20 20 20 20 20 74 72 65 65 5f 76 .. tree_v
2c10: 65 72 69 66 79 28 74 72 65 65 2c 20 4e 55 4c 4c erify(tree, NULL
2c20: 29 3b 0a 20 20 20 20 20 20 20 20 77 68 69 6c 65 );. while
2c30: 28 6e 6f 64 65 29 20 7b 0a 09 09 69 6e 74 20 64 (node) {...int d
2c40: 69 66 66 20 3d 20 74 72 65 65 2d 3e 63 6f 6d 70 iff = tree->comp
2c50: 28 6b 65 79 2c 20 6e 6f 64 65 2d 3e 6b 65 79 29 (key, node->key)
2c60: 3b 0a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 ;..
2c70: 20 20 20 69 66 20 28 64 69 66 66 3c 30 29 20 7b if (diff<0) {
2c80: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 .
2c90: 20 20 20 20 20 20 20 20 20 70 61 72 65 6e 74 20 parent
2ca0: 3d 20 6e 6f 64 65 3b 0a 20 20 20 20 20 20 20 20 = node;.
2cb0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2cc0: 70 6c 61 73 74 20 3d 20 26 6e 6f 64 65 2d 3e 6c plast = &node->l
2cd0: 65 66 74 3b 0a 20 20 20 20 20 20 20 20 20 20 20 eft;.
2ce0: 20 20 20 20 20 20 20 20 20 20 20 20 20 6e 6f 64 nod
2cf0: 65 20 3d 20 6e 6f 64 65 2d 3e 6c 65 66 74 3b 0a e = node->left;.
2d00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2d10: 7d 20 65 6c 73 65 20 69 66 20 28 64 69 66 66 3e } else if (diff>
2d20: 30 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 0) {.
2d30: 20 20 20 20 20 20 20 20 20 20 20 20 20 70 61 72 par
2d40: 65 6e 74 20 3d 20 6e 6f 64 65 3b 0a 20 20 20 20 ent = node;.
2d50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2d60: 20 20 20 20 70 6c 61 73 74 20 3d 20 26 6e 6f 64 plast = &nod
2d70: 65 2d 3e 72 69 67 68 74 3b 0a 20 20 20 20 20 20 e->right;.
2d80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2d90: 20 20 6e 6f 64 65 20 3d 20 6e 6f 64 65 2d 3e 72 node = node->r
2da0: 69 67 68 74 3b 0a 20 20 20 20 20 20 20 20 20 20 ight;.
2db0: 20 20 20 20 20 20 7d 20 65 6c 73 65 20 7b 0a 20 } else {.
2dc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2dd0: 20 20 20 20 20 20 20 2f 2a 20 52 65 70 6c 61 63 /* Replac
2de0: 65 20 65 78 69 73 74 69 6e 67 20 64 61 74 61 20 e existing data
2df0: 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 */.
2e00: 20 20 20 20 20 20 20 20 20 20 20 6d 61 70 5f 64 map_d
2e10: 61 74 61 20 6f 6c 64 64 61 74 61 20 3d 20 6e 6f ata olddata = no
2e20: 64 65 2d 3e 64 61 74 61 3b 0a 20 20 20 20 20 20 de->data;.
2e30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2e40: 20 20 6e 6f 64 65 2d 3e 6b 65 79 20 3d 20 6b 65 node->key = ke
2e50: 79 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 y;.
2e60: 20 20 20 20 20 20 20 20 20 20 20 6e 6f 64 65 2d node-
2e70: 3e 64 61 74 61 20 3d 20 64 61 74 61 3b 0a 20 20 >data = data;.
2e80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2e90: 20 20 20 20 20 20 74 72 65 65 5f 76 65 72 69 66 tree_verif
2ea0: 79 28 74 72 65 65 2c 20 6e 6f 64 65 29 3b 0a 20 y(tree, node);.
2eb0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2ec0: 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 6f 6c return ol
2ed0: 64 64 61 74 61 3b 0a 20 20 20 20 20 20 20 20 20 ddata;.
2ee0: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 }.
2ef0: 20 7d 0a 0a 20 20 20 20 20 20 20 20 2f 2a 0a 20 }.. /*.
2f00: 20 20 20 20 20 20 20 20 2a 20 42 79 20 68 65 72 * By her
2f10: 65 2c 20 77 65 20 68 61 76 65 20 6e 65 77 20 64 e, we have new d
2f20: 61 74 61 0a 20 20 20 20 20 20 20 20 20 2a 2f 0a ata. */.
2f30: 20 20 20 20 20 20 20 20 2a 70 6c 61 73 74 20 3d *plast =
2f40: 20 6e 6f 64 65 20 3d 20 74 72 65 65 5f 6e 6f 64 node = tree_nod
2f50: 65 5f 6e 65 77 28 70 61 72 65 6e 74 2c 20 6b 65 e_new(parent, ke
2f60: 79 2c 20 64 61 74 61 29 3b 0a 0a 20 20 20 20 20 y, data);..
2f70: 20 20 20 2f 2a 0a 20 20 20 20 20 20 20 20 20 2a /*. *
2f80: 20 44 6f 20 61 6e 79 20 22 62 61 6c 61 6e 63 69 Do any "balanci
2f90: 6e 67 22 0a 20 20 20 20 20 20 20 20 20 2a 2f 0a ng". */.
2fa0: 20 20 20 20 20 20 20 20 73 77 69 74 63 68 28 74 switch(t
2fb0: 72 65 65 2d 3e 6d 6f 64 65 29 20 7b 0a 20 20 20 ree->mode) {.
2fc0: 20 20 20 20 20 63 61 73 65 20 54 52 45 45 5f 53 case TREE_S
2fd0: 50 4c 41 59 3a 0a 20 20 20 20 20 20 20 20 20 20 PLAY:.
2fe0: 20 20 20 20 20 20 6e 6f 64 65 5f 73 70 6c 61 79 node_splay
2ff0: 28 6e 6f 64 65 29 3b 0a 20 20 20 20 20 20 20 20 (node);.
3000: 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 break;.
3010: 20 20 20 20 20 20 20 63 61 73 65 20 54 52 45 45 case TREE
3020: 5f 54 52 45 41 50 3a 0a 20 20 20 20 20 20 20 20 _TREAP:.
3030: 20 20 20 20 20 20 20 20 6e 6f 64 65 5f 70 72 69 node_pri
3040: 6f 72 69 74 69 7a 65 28 6e 6f 64 65 29 3b 0a 20 oritize(node);.
3050: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 62 b
3060: 72 65 61 6b 3b 0a 20 20 20 20 20 20 20 20 63 61 reak;. ca
3070: 73 65 20 54 52 45 45 5f 43 4f 55 4e 54 3a 0a 20 se TREE_COUNT:.
3080: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6e n
3090: 6f 64 65 5f 63 6f 75 6e 74 5f 62 61 6c 61 6e 63 ode_count_balanc
30a0: 65 28 6e 6f 64 65 29 3b 0a 20 20 20 20 20 20 20 e(node);.
30b0: 20 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a break;.
30c0: 09 64 65 66 61 75 6c 74 3a 0a 09 09 6e 6f 64 65 .default:...node
30d0: 5f 73 69 6d 70 6c 65 5f 62 61 6c 61 6e 63 65 28 _simple_balance(
30e0: 6e 6f 64 65 29 3b 0a 09 09 62 72 65 61 6b 3b 0a node);...break;.
30f0: 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 }.
3100: 20 20 69 66 20 28 4e 55 4c 4c 20 3d 3d 20 6e 6f if (NULL == no
3110: 64 65 2d 3e 70 61 72 65 6e 74 29 20 7b 0a 20 20 de->parent) {.
3120: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 74 72 tr
3130: 65 65 2d 3e 72 6f 6f 74 20 3d 20 6e 6f 64 65 3b ee->root = node;
3140: 0a 20 20 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 . }..
3150: 20 20 20 20 69 66 20 28 74 72 65 65 2d 3e 72 6f if (tree->ro
3160: 6f 74 2d 3e 70 61 72 65 6e 74 29 20 7b 0a 20 20 ot->parent) {.
3170: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a /*
3180: 20 54 72 65 65 20 68 61 73 20 6e 65 77 20 72 6f Tree has new ro
3190: 6f 74 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 ot */.
31a0: 20 20 20 20 20 20 77 68 69 6c 65 28 74 72 65 65 while(tree
31b0: 2d 3e 72 6f 6f 74 2d 3e 70 61 72 65 6e 74 29 20 ->root->parent)
31c0: 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 {.
31d0: 20 20 20 20 20 20 20 20 20 20 74 72 65 65 2d 3e tree->
31e0: 72 6f 6f 74 20 3d 20 74 72 65 65 2d 3e 72 6f 6f root = tree->roo
31f0: 74 2d 3e 70 61 72 65 6e 74 3b 0a 20 20 20 20 20 t->parent;.
3200: 20 20 20 20 20 20 20 20 20 20 20 7d 0a 20 20 20 }.
3210: 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 20 20 20 }..
3220: 74 72 65 65 5f 76 65 72 69 66 79 28 74 72 65 65 tree_verify(tree
3230: 2c 20 6e 6f 64 65 29 3b 0a 0a 09 72 65 74 75 72 , node);...retur
3240: 6e 20 30 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 63 n 0;.}..static c
3250: 6f 6e 73 74 20 6e 6f 64 65 5f 74 20 2a 20 74 72 onst node_t * tr
3260: 65 65 5f 67 65 74 5f 6e 6f 64 65 28 20 74 72 65 ee_get_node( tre
3270: 65 5f 74 20 2a 20 74 72 65 65 2c 20 6d 61 70 5f e_t * tree, map_
3280: 6b 65 79 20 6b 65 79 2c 20 6d 61 70 5f 65 71 5f key key, map_eq_
3290: 74 65 73 74 20 63 6f 6e 64 20 29 0a 7b 0a 09 6e test cond ).{..n
32a0: 6f 64 65 5f 74 20 2a 20 6e 6f 64 65 20 3d 20 74 ode_t * node = t
32b0: 72 65 65 2d 3e 72 6f 6f 74 3b 0a 0a 09 2f 2a 20 ree->root;.../*
32c0: 46 49 58 4d 45 3a 20 41 6c 6c 20 74 68 69 73 20 FIXME: All this
32d0: 6c 6f 67 69 63 20 6e 65 65 64 73 20 63 68 65 63 logic needs chec
32e0: 6b 69 6e 67 21 20 2a 2f 0a 09 77 68 69 6c 65 28 king! */..while(
32f0: 6e 6f 64 65 29 20 7b 0a 09 09 69 6e 74 20 64 69 node) {...int di
3300: 66 66 20 3d 20 74 72 65 65 2d 3e 63 6f 6d 70 28 ff = tree->comp(
3310: 6b 65 79 2c 20 6e 6f 64 65 2d 3e 6b 65 79 29 3b key, node->key);
3320: 0a 0a 09 09 69 66 20 28 64 69 66 66 3c 30 29 20 ....if (diff<0)
3330: 7b 0a 09 09 09 69 66 20 28 6e 6f 64 65 2d 3e 6c {....if (node->l
3340: 65 66 74 29 20 7b 0a 09 09 09 09 6e 6f 64 65 20 eft) {.....node
3350: 3d 20 6e 6f 64 65 2d 3e 6c 65 66 74 3b 0a 09 09 = node->left;...
3360: 09 7d 20 65 6c 73 65 20 7b 0a 09 09 09 09 73 77 .} else {.....sw
3370: 69 74 63 68 28 63 6f 6e 64 29 20 7b 0a 09 09 09 itch(cond) {....
3380: 09 63 61 73 65 20 4d 41 50 5f 47 54 3a 20 63 61 .case MAP_GT: ca
3390: 73 65 20 4d 41 50 5f 47 45 3a 0a 09 09 09 09 09 se MAP_GE:......
33a0: 72 65 74 75 72 6e 20 6e 6f 64 65 3b 0a 09 09 09 return node;....
33b0: 09 63 61 73 65 20 4d 41 50 5f 4c 54 3a 20 63 61 .case MAP_LT: ca
33c0: 73 65 20 4d 41 50 5f 4c 45 3a 0a 09 09 09 09 09 se MAP_LE:......
33d0: 72 65 74 75 72 6e 20 6e 6f 64 65 5f 70 72 65 76 return node_prev
33e0: 28 6e 6f 64 65 29 3b 0a 09 09 09 09 64 65 66 61 (node);.....defa
33f0: 75 6c 74 3a 0a 09 09 09 09 09 72 65 74 75 72 6e ult:......return
3400: 20 30 3b 0a 09 09 09 09 7d 0a 09 09 09 7d 0a 09 0;.....}....}..
3410: 09 7d 20 65 6c 73 65 20 69 66 20 28 64 69 66 66 .} else if (diff
3420: 3e 30 29 20 7b 0a 09 09 09 69 66 20 28 6e 6f 64 >0) {....if (nod
3430: 65 2d 3e 72 69 67 68 74 29 20 7b 0a 09 09 09 09 e->right) {.....
3440: 6e 6f 64 65 20 3d 20 6e 6f 64 65 2d 3e 72 69 67 node = node->rig
3450: 68 74 3b 0a 09 09 09 7d 20 65 6c 73 65 20 7b 0a ht;....} else {.
3460: 09 09 09 09 73 77 69 74 63 68 28 63 6f 6e 64 29 ....switch(cond)
3470: 20 7b 0a 09 09 09 09 63 61 73 65 20 4d 41 50 5f {.....case MAP_
3480: 47 54 3a 20 63 61 73 65 20 4d 41 50 5f 47 45 3a GT: case MAP_GE:
3490: 0a 09 09 09 09 09 72 65 74 75 72 6e 20 6e 6f 64 ......return nod
34a0: 65 5f 6e 65 78 74 28 6e 6f 64 65 29 3b 0a 09 09 e_next(node);...
34b0: 09 09 63 61 73 65 20 4d 41 50 5f 4c 54 3a 20 63 ..case MAP_LT: c
34c0: 61 73 65 20 4d 41 50 5f 4c 45 3a 0a 09 09 09 09 ase MAP_LE:.....
34d0: 09 72 65 74 75 72 6e 20 6e 6f 64 65 3b 0a 09 09 .return node;...
34e0: 09 09 64 65 66 61 75 6c 74 3a 0a 09 09 09 09 09 ..default:......
34f0: 72 65 74 75 72 6e 20 30 3b 0a 09 09 09 09 7d 0a return 0;.....}.
3500: 09 09 09 7d 0a 09 09 7d 20 65 6c 73 65 20 7b 0a ...}...} else {.
3510: 09 09 09 73 77 69 74 63 68 28 63 6f 6e 64 29 20 ...switch(cond)
3520: 7b 0a 09 09 09 63 61 73 65 20 4d 41 50 5f 4c 54 {....case MAP_LT
3530: 3a 0a 09 09 09 09 72 65 74 75 72 6e 20 6e 6f 64 :.....return nod
3540: 65 5f 70 72 65 76 28 6e 6f 64 65 29 3b 0a 09 09 e_prev(node);...
3550: 09 63 61 73 65 20 4d 41 50 5f 47 54 3a 0a 09 09 .case MAP_GT:...
3560: 09 09 72 65 74 75 72 6e 20 6e 6f 64 65 5f 6e 65 ..return node_ne
3570: 78 74 28 6e 6f 64 65 29 3b 0a 09 09 09 64 65 66 xt(node);....def
3580: 61 75 6c 74 3a 0a 09 09 09 09 69 66 20 28 54 52 ault:.....if (TR
3590: 45 45 5f 53 50 4c 41 59 20 3d 3d 20 74 72 65 65 EE_SPLAY == tree
35a0: 2d 3e 6d 6f 64 65 29 20 7b 0a 09 09 09 09 09 6e ->mode) {......n
35b0: 6f 64 65 5f 73 70 6c 61 79 28 6e 6f 64 65 29 3b ode_splay(node);
35c0: 0a 09 09 09 09 09 69 66 20 28 74 72 65 65 2d 3e ......if (tree->
35d0: 72 6f 6f 74 2d 3e 70 61 72 65 6e 74 29 20 7b 0a root->parent) {.
35e0: 09 09 09 09 09 09 2f 2a 20 54 72 65 65 20 68 61 ....../* Tree ha
35f0: 73 20 6e 65 77 20 72 6f 6f 74 20 2a 2f 0a 09 09 s new root */...
3600: 09 09 09 09 77 68 69 6c 65 28 74 72 65 65 2d 3e ....while(tree->
3610: 72 6f 6f 74 2d 3e 70 61 72 65 6e 74 29 20 7b 0a root->parent) {.
3620: 09 09 09 09 09 09 09 74 72 65 65 2d 3e 72 6f 6f .......tree->roo
3630: 74 20 3d 20 74 72 65 65 2d 3e 72 6f 6f 74 2d 3e t = tree->root->
3640: 70 61 72 65 6e 74 3b 0a 09 09 09 09 09 09 7d 0a parent;.......}.
3650: 09 09 09 09 09 7d 0a 09 09 09 09 7d 0a 09 09 09 .....}.....}....
3660: 09 72 65 74 75 72 6e 20 6e 6f 64 65 3b 0a 09 09 .return node;...
3670: 09 7d 0a 09 09 7d 0a 09 7d 0a 0a 09 72 65 74 75 .}...}..}...retu
3680: 72 6e 20 30 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 rn 0;.}..static
3690: 6d 61 70 5f 64 61 74 61 20 74 72 65 65 5f 67 65 map_data tree_ge
36a0: 74 5f 64 61 74 61 28 20 74 72 65 65 5f 74 20 2a t_data( tree_t *
36b0: 20 74 72 65 65 2c 20 6d 61 70 5f 6b 65 79 20 6b tree, map_key k
36c0: 65 79 2c 20 6d 61 70 5f 65 71 5f 74 65 73 74 20 ey, map_eq_test
36d0: 63 6f 6e 64 20 29 0a 7b 0a 09 63 6f 6e 73 74 20 cond ).{..const
36e0: 6e 6f 64 65 5f 74 20 2a 20 6e 6f 64 65 20 3d 20 node_t * node =
36f0: 74 72 65 65 5f 67 65 74 5f 6e 6f 64 65 28 74 72 tree_get_node(tr
3700: 65 65 2c 20 6b 65 79 2c 20 63 6f 6e 64 29 3b 0a ee, key, cond);.
3710: 0a 09 72 65 74 75 72 6e 20 28 6e 6f 64 65 29 20 ..return (node)
3720: 3f 20 6e 6f 64 65 2d 3e 64 61 74 61 20 3a 20 30 ? node->data : 0
3730: 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 6d 61 70 5f ;.}..static map_
3740: 64 61 74 61 20 74 72 65 65 5f 67 65 74 28 63 6f data tree_get(co
3750: 6e 73 74 20 6d 61 70 5f 74 20 2a 20 6d 61 70 2c nst map_t * map,
3760: 20 6d 61 70 5f 6b 65 79 20 6b 65 79 2c 20 6d 61 map_key key, ma
3770: 70 5f 65 71 5f 74 65 73 74 20 63 6f 6e 64 20 29 p_eq_test cond )
3780: 0a 7b 0a 20 20 20 20 20 20 20 20 74 72 65 65 5f .{. tree_
3790: 74 20 2a 20 74 72 65 65 20 3d 20 63 6f 6e 74 61 t * tree = conta
37a0: 69 6e 65 72 5f 6f 66 28 6d 61 70 2c 20 74 72 65 iner_of(map, tre
37b0: 65 5f 74 2c 20 6d 61 70 29 3b 0a 09 72 65 74 75 e_t, map);..retu
37c0: 72 6e 20 74 72 65 65 5f 67 65 74 5f 64 61 74 61 rn tree_get_data
37d0: 28 74 72 65 65 2c 20 6b 65 79 2c 20 63 6f 6e 64 (tree, key, cond
37e0: 29 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 6d 61 70 );.}..static map
37f0: 5f 64 61 74 61 20 74 72 65 65 5f 72 65 6d 6f 76 _data tree_remov
3800: 65 28 20 63 6f 6e 73 74 20 6d 61 70 5f 74 20 2a e( const map_t *
3810: 20 6d 61 70 2c 20 6d 61 70 5f 6b 65 79 20 6b 65 map, map_key ke
3820: 79 20 29 0a 7b 0a 20 20 20 20 20 20 20 20 74 72 y ).{. tr
3830: 65 65 5f 74 20 2a 20 74 72 65 65 20 3d 20 63 6f ee_t * tree = co
3840: 6e 74 61 69 6e 65 72 5f 6f 66 28 6d 61 70 2c 20 ntainer_of(map,
3850: 74 72 65 65 5f 74 2c 20 6d 61 70 29 3b 0a 20 20 tree_t, map);.
3860: 20 20 20 20 20 20 6e 6f 64 65 5f 74 20 2a 20 6e node_t * n
3870: 6f 64 65 20 3d 20 74 72 65 65 2d 3e 72 6f 6f 74 ode = tree->root
3880: 3b 0a 0a 20 20 20 20 20 20 20 20 74 72 65 65 5f ;.. tree_
3890: 76 65 72 69 66 79 28 74 72 65 65 2c 20 4e 55 4c verify(tree, NUL
38a0: 4c 29 3b 0a 20 20 20 20 20 20 20 20 77 68 69 6c L);. whil
38b0: 65 28 6e 6f 64 65 29 20 7b 0a 09 09 69 6e 74 20 e(node) {...int
38c0: 64 69 66 66 20 3d 20 74 72 65 65 2d 3e 63 6f 6d diff = tree->com
38d0: 70 28 6b 65 79 2c 20 6e 6f 64 65 2d 3e 6b 65 79 p(key, node->key
38e0: 29 3b 0a 0a 20 20 20 20 20 20 20 20 20 20 20 20 );..
38f0: 20 20 20 20 69 66 20 28 64 69 66 66 3c 30 29 20 if (diff<0)
3900: 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 {.
3910: 20 20 20 20 20 20 20 20 20 20 6e 6f 64 65 20 3d node =
3920: 20 6e 6f 64 65 2d 3e 6c 65 66 74 3b 0a 20 20 20 node->left;.
3930: 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 20 65 } e
3940: 6c 73 65 20 69 66 20 28 64 69 66 66 3e 30 29 20 lse if (diff>0)
3950: 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 {.
3960: 20 20 20 20 20 20 20 20 20 20 6e 6f 64 65 20 3d node =
3970: 20 6e 6f 64 65 2d 3e 72 69 67 68 74 3b 0a 20 20 node->right;.
3980: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 20 }
3990: 65 6c 73 65 20 7b 0a 20 20 20 20 20 20 20 20 20 else {.
39a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6d m
39b0: 61 70 5f 64 61 74 61 20 64 61 74 61 20 3d 20 6e ap_data data = n
39c0: 6f 64 65 2d 3e 64 61 74 61 3b 0a 20 20 20 20 20 ode->data;.
39d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
39e0: 20 20 20 6e 6f 64 65 5f 74 20 2a 20 70 61 72 65 node_t * pare
39f0: 6e 74 20 3d 20 4e 55 4c 4c 3b 0a 0a 20 20 20 20 nt = NULL;..
3a00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3a10: 20 20 20 20 2f 2a 20 42 75 62 62 6c 65 20 74 68 /* Bubble th
3a20: 65 20 6e 6f 64 65 20 64 6f 77 6e 20 74 6f 20 61 e node down to a
3a30: 20 6c 65 61 66 20 2a 2f 0a 20 20 20 20 20 20 20 leaf */.
3a40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3a50: 20 77 68 69 6c 65 28 6e 6f 64 65 2d 3e 6c 65 66 while(node->lef
3a60: 74 20 7c 7c 20 6e 6f 64 65 2d 3e 72 69 67 68 74 t || node->right
3a70: 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 ) {.
3a80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3a90: 20 20 20 20 69 66 20 28 6e 6f 64 65 2d 3e 6c 65 if (node->le
3aa0: 66 74 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 ft) {.
3ab0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3ac0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6e 6f no
3ad0: 64 65 5f 72 6f 74 61 74 65 5f 72 69 67 68 74 28 de_rotate_right(
3ae0: 6e 6f 64 65 29 3b 0a 20 20 20 20 20 20 20 20 20 node);.
3af0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3b00: 20 20 20 20 20 20 20 7d 20 65 6c 73 65 20 7b 0a } else {.
3b10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3b20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3b30: 20 20 20 20 20 20 20 20 6e 6f 64 65 5f 72 6f 74 node_rot
3b40: 61 74 65 5f 6c 65 66 74 28 6e 6f 64 65 29 3b 0a ate_left(node);.
3b50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3b60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3b70: 7d 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 }.
3b80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3b90: 20 20 69 66 20 28 4e 55 4c 4c 20 3d 3d 20 6e 6f if (NULL == no
3ba0: 64 65 2d 3e 70 61 72 65 6e 74 2d 3e 70 61 72 65 de->parent->pare
3bb0: 6e 74 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 nt) {.
3bc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3bd0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 74 72 tr
3be0: 65 65 2d 3e 72 6f 6f 74 20 3d 20 6e 6f 64 65 2d ee->root = node-
3bf0: 3e 70 61 72 65 6e 74 3b 0a 20 20 20 20 20 20 20 >parent;.
3c00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3c10: 20 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 }.
3c20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3c30: 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20 20 }.
3c40: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 /*
3c50: 4e 6f 64 65 20 68 61 73 20 6e 6f 20 63 68 69 6c Node has no chil
3c60: 64 72 65 6e 2c 20 6a 75 73 74 20 64 65 6c 65 74 dren, just delet
3c70: 65 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 20 e */.
3c80: 20 20 20 20 20 20 20 20 20 20 20 20 20 61 73 73 ass
3c90: 65 72 74 28 31 20 3d 3d 20 6e 6f 64 65 2d 3e 63 ert(1 == node->c
3ca0: 6f 75 6e 74 29 3b 0a 20 20 20 20 20 20 20 20 20 ount);.
3cb0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 i
3cc0: 66 20 28 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 20 f (node->parent
3cd0: 26 26 20 6e 6f 64 65 20 3d 3d 20 6e 6f 64 65 2d && node == node-
3ce0: 3e 70 61 72 65 6e 74 2d 3e 6c 65 66 74 29 20 7b >parent->left) {
3cf0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 .
3d00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3d10: 20 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 2d 3e 6c node->parent->l
3d20: 65 66 74 20 3d 20 4e 55 4c 4c 3b 0a 20 20 20 20 eft = NULL;.
3d30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3d40: 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20 }.
3d50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 66 if
3d60: 20 28 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 20 26 (node->parent &
3d70: 26 20 6e 6f 64 65 20 3d 3d 20 6e 6f 64 65 2d 3e & node == node->
3d80: 70 61 72 65 6e 74 2d 3e 72 69 67 68 74 29 20 7b parent->right) {
3d90: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 .
3da0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3db0: 20 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 2d 3e 72 node->parent->r
3dc0: 69 67 68 74 20 3d 20 4e 55 4c 4c 3b 0a 20 20 20 ight = NULL;.
3dd0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3de0: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 }.
3df0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 i
3e00: 66 20 28 4e 55 4c 4c 20 3d 3d 20 6e 6f 64 65 2d f (NULL == node-
3e10: 3e 70 61 72 65 6e 74 29 20 7b 0a 20 20 20 20 20 >parent) {.
3e20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3e30: 20 20 20 20 20 20 20 20 20 20 20 74 72 65 65 2d tree-
3e40: 3e 72 6f 6f 74 20 3d 20 4e 55 4c 4c 3b 0a 20 20 >root = NULL;.
3e50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3e60: 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 20 20 }..
3e70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3e80: 20 2f 2a 20 44 65 63 72 65 6d 65 6e 74 20 74 68 /* Decrement th
3e90: 65 20 63 6f 75 6e 74 73 20 6f 6e 20 70 61 72 65 e counts on pare
3ea0: 6e 74 20 6e 6f 64 65 73 20 2a 2f 0a 20 20 20 20 nt nodes */.
3eb0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3ec0: 20 20 20 20 70 61 72 65 6e 74 20 3d 20 6e 6f 64 parent = nod
3ed0: 65 2d 3e 70 61 72 65 6e 74 3b 0a 20 20 20 20 20 e->parent;.
3ee0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3ef0: 20 20 20 77 68 69 6c 65 28 70 61 72 65 6e 74 29 while(parent)
3f00: 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 {.
3f10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3f20: 20 20 20 70 61 72 65 6e 74 2d 3e 63 6f 75 6e 74 parent->count
3f30: 2d 2d 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 --;.
3f40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3f50: 20 20 20 20 70 61 72 65 6e 74 20 3d 20 70 61 72 parent = par
3f60: 65 6e 74 2d 3e 70 61 72 65 6e 74 3b 0a 20 20 20 ent->parent;.
3f70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3f80: 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 20 20 20 }..
3f90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3fa0: 74 72 65 65 5f 76 65 72 69 66 79 28 74 72 65 65 tree_verify(tree
3fb0: 2c 20 4e 55 4c 4c 29 3b 0a 0a 20 20 20 20 20 20 , NULL);..
3fc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3fd0: 20 20 72 65 74 75 72 6e 20 64 61 74 61 3b 0a 20 return data;.
3fe0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 7d }
3ff0: 0a 20 20 20 20 20 20 20 20 7d 0a 0a 09 72 65 74 . }...ret
4000: 75 72 6e 20 30 3b 0a 7d 0a 0a 0a 73 74 61 74 69 urn 0;.}...stati
4010: 63 20 69 74 65 72 61 74 6f 72 5f 74 20 2a 20 74 c iterator_t * t
4020: 72 65 65 5f 69 74 65 72 61 74 6f 72 28 20 63 6f ree_iterator( co
4030: 6e 73 74 20 6d 61 70 5f 74 20 2a 20 6d 61 70 29 nst map_t * map)
4040: 0a 7b 0a 09 72 65 74 75 72 6e 20 30 3b 0a 7d 0a .{..return 0;.}.
4050: 0a 73 74 61 74 69 63 20 6e 6f 64 65 5f 74 20 2a .static node_t *
4060: 20 6e 6f 64 65 5f 6f 72 64 69 6e 61 6c 28 6e 6f node_ordinal(no
4070: 64 65 5f 74 20 2a 20 72 6f 6f 74 2c 20 69 6e 74 de_t * root, int
4080: 20 69 29 0a 7b 0a 09 6e 6f 64 65 5f 74 20 2a 20 i).{..node_t *
4090: 6e 6f 64 65 20 3d 20 72 6f 6f 74 3b 0a 0a 09 69 node = root;...i
40a0: 66 20 28 69 20 3e 3d 20 6e 6f 64 65 2d 3e 63 6f f (i >= node->co
40b0: 75 6e 74 29 20 7b 0a 09 09 4b 54 48 52 4f 57 46 unt) {...KTHROWF
40c0: 28 4f 75 74 4f 66 42 6f 75 6e 64 73 45 78 63 65 (OutOfBoundsExce
40d0: 70 74 69 6f 6e 2c 20 22 4f 75 74 20 6f 66 20 62 ption, "Out of b
40e0: 6f 75 6e 64 73 3a 20 25 64 20 3e 3d 20 25 64 5c ounds: %d >= %d\
40f0: 6e 22 2c 20 69 2c 20 6e 6f 64 65 2d 3e 63 6f 75 n", i, node->cou
4100: 6e 74 29 3b 0a 09 09 72 65 74 75 72 6e 20 30 3b nt);...return 0;
4110: 0a 09 7d 0a 0a 09 77 68 69 6c 65 28 6e 6f 64 65 ..}...while(node
4120: 29 20 7b 0a 09 09 69 6e 74 20 63 6f 75 6e 74 5f ) {...int count_
4130: 6c 65 66 74 20 3d 20 6e 6f 64 65 5f 63 6f 75 6e left = node_coun
4140: 74 28 6e 6f 64 65 2d 3e 6c 65 66 74 29 3b 0a 09 t(node->left);..
4150: 09 69 66 20 28 69 3c 63 6f 75 6e 74 5f 6c 65 66 .if (i<count_lef
4160: 74 29 20 7b 0a 09 09 09 6e 6f 64 65 20 3d 20 6e t) {....node = n
4170: 6f 64 65 2d 3e 6c 65 66 74 3b 20 0a 09 09 7d 20 ode->left; ...}
4180: 65 6c 73 65 20 69 66 20 28 69 20 3d 3d 20 63 6f else if (i == co
4190: 75 6e 74 5f 6c 65 66 74 29 20 7b 0a 09 09 09 72 unt_left) {....r
41a0: 65 74 75 72 6e 20 6e 6f 64 65 3b 0a 09 09 7d 20 eturn node;...}
41b0: 65 6c 73 65 20 7b 0a 09 09 09 6e 6f 64 65 20 3d else {....node =
41c0: 20 6e 6f 64 65 2d 3e 72 69 67 68 74 3b 0a 09 09 node->right;...
41d0: 09 69 20 2d 3d 20 28 63 6f 75 6e 74 5f 6c 65 66 .i -= (count_lef
41e0: 74 2b 31 29 3b 0a 09 09 7d 0a 09 7d 0a 0a 09 2f t+1);...}..}.../
41f0: 2a 20 46 49 58 4d 45 3a 20 43 61 6e 27 74 20 68 * FIXME: Can't h
4200: 61 70 70 65 6e 21 20 2a 2f 0a 09 72 65 74 75 72 appen! */..retur
4210: 6e 20 30 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 6e n 0;.}..static n
4220: 6f 64 65 5f 74 20 2a 20 6e 6f 64 65 5f 6f 70 74 ode_t * node_opt
4230: 69 6d 69 7a 65 28 6e 6f 64 65 5f 74 20 2a 20 72 imize(node_t * r
4240: 6f 6f 74 29 0a 7b 0a 09 69 66 20 28 30 20 3d 3d oot).{..if (0 ==
4250: 20 72 6f 6f 74 29 20 7b 0a 09 09 72 65 74 75 72 root) {...retur
4260: 6e 20 30 3b 0a 09 7d 0a 0a 09 6e 6f 64 65 5f 74 n 0;..}...node_t
4270: 20 2a 20 70 61 72 65 6e 74 20 3d 20 72 6f 6f 74 * parent = root
4280: 2d 3e 70 61 72 65 6e 74 3b 0a 09 6e 6f 64 65 5f ->parent;..node_
4290: 74 20 2a 20 6e 6f 64 65 20 3d 20 6e 6f 64 65 5f t * node = node_
42a0: 6f 72 64 69 6e 61 6c 28 72 6f 6f 74 2c 20 72 6f ordinal(root, ro
42b0: 6f 74 2d 3e 63 6f 75 6e 74 2f 32 29 3b 0a 0a 09 ot->count/2);...
42c0: 6e 6f 64 65 2d 3e 70 72 69 6f 72 69 74 79 20 3d node->priority =
42d0: 20 28 70 61 72 65 6e 74 29 20 3f 20 70 61 72 65 (parent) ? pare
42e0: 6e 74 2d 3e 70 72 69 6f 72 69 74 79 20 2b 20 31 nt->priority + 1
42f0: 30 20 3a 20 31 30 3b 0a 0a 09 77 68 69 6c 65 28 0 : 10;...while(
4300: 6e 6f 64 65 2d 3e 70 61 72 65 6e 74 20 21 3d 20 node->parent !=
4310: 70 61 72 65 6e 74 29 20 7b 0a 09 09 69 66 20 28 parent) {...if (
4320: 6e 6f 64 65 5f 69 73 5f 6c 65 66 74 28 6e 6f 64 node_is_left(nod
4330: 65 29 29 20 7b 0a 09 09 09 6e 6f 64 65 5f 72 6f e)) {....node_ro
4340: 74 61 74 65 5f 72 69 67 68 74 28 6e 6f 64 65 2d tate_right(node-
4350: 3e 70 61 72 65 6e 74 29 3b 0a 09 09 7d 20 65 6c >parent);...} el
4360: 73 65 20 7b 0a 09 09 09 6e 6f 64 65 5f 72 6f 74 se {....node_rot
4370: 61 74 65 5f 6c 65 66 74 28 6e 6f 64 65 2d 3e 70 ate_left(node->p
4380: 61 72 65 6e 74 29 3b 0a 09 09 7d 0a 09 7d 0a 0a arent);...}..}..
4390: 09 6e 6f 64 65 2d 3e 6c 65 66 74 20 3d 20 6e 6f .node->left = no
43a0: 64 65 5f 6f 70 74 69 6d 69 7a 65 28 6e 6f 64 65 de_optimize(node
43b0: 2d 3e 6c 65 66 74 29 3b 0a 09 6e 6f 64 65 2d 3e ->left);..node->
43c0: 72 69 67 68 74 20 3d 20 6e 6f 64 65 5f 6f 70 74 right = node_opt
43d0: 69 6d 69 7a 65 28 6e 6f 64 65 2d 3e 72 69 67 68 imize(node->righ
43e0: 74 29 3b 0a 0a 09 72 65 74 75 72 6e 20 6e 6f 64 t);...return nod
43f0: 65 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 76 6f 69 e;.}..static voi
4400: 64 20 74 72 65 65 5f 6f 70 74 69 6d 69 7a 65 28 d tree_optimize(
4410: 63 6f 6e 73 74 20 6d 61 70 5f 74 20 2a 20 6d 61 const map_t * ma
4420: 70 29 0a 7b 0a 20 20 20 20 20 20 20 20 74 72 65 p).{. tre
4430: 65 5f 74 20 2a 20 74 72 65 65 20 3d 20 63 6f 6e e_t * tree = con
4440: 74 61 69 6e 65 72 5f 6f 66 28 6d 61 70 2c 20 74 tainer_of(map, t
4450: 72 65 65 5f 74 2c 20 6d 61 70 29 3b 0a 09 74 72 ree_t, map);..tr
4460: 65 65 2d 3e 72 6f 6f 74 20 3d 20 6e 6f 64 65 5f ee->root = node_
4470: 6f 70 74 69 6d 69 7a 65 28 74 72 65 65 2d 3e 72 optimize(tree->r
4480: 6f 6f 74 29 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 oot);.}..static
4490: 73 69 7a 65 5f 74 20 74 72 65 65 5f 73 69 7a 65 size_t tree_size
44a0: 28 63 6f 6e 73 74 20 6d 61 70 5f 74 20 2a 20 6d (const map_t * m
44b0: 61 70 29 0a 7b 0a 20 20 20 20 20 20 20 20 74 72 ap).{. tr
44c0: 65 65 5f 74 20 2a 20 74 72 65 65 20 3d 20 63 6f ee_t * tree = co
44d0: 6e 74 61 69 6e 65 72 5f 6f 66 28 6d 61 70 2c 20 ntainer_of(map,
44e0: 74 72 65 65 5f 74 2c 20 6d 61 70 29 3b 0a 0a 09 tree_t, map);...
44f0: 69 66 20 28 74 72 65 65 2d 3e 72 6f 6f 74 29 20 if (tree->root)
4500: 7b 0a 09 09 72 65 74 75 72 6e 20 74 72 65 65 2d {...return tree-
4510: 3e 72 6f 6f 74 2d 3e 63 6f 75 6e 74 3b 0a 09 7d >root->count;..}
4520: 20 65 6c 73 65 20 7b 0a 09 09 72 65 74 75 72 6e else {...return
4530: 20 30 3b 0a 09 7d 0a 7d 0a 0a 76 6f 69 64 20 74 0;..}.}..void t
4540: 72 65 65 5f 69 6e 69 74 28 29 0a 7b 0a 09 49 4e ree_init().{..IN
4550: 49 54 5f 4f 4e 43 45 28 29 3b 0a 0a 7d 0a 0a 73 IT_ONCE();..}..s
4560: 74 61 74 69 63 20 69 6e 74 65 72 66 61 63 65 5f tatic interface_
4570: 6d 61 70 5f 74 20 74 72 65 65 5f 74 5f 6d 61 70 map_t tree_t_map
4580: 20 5b 5d 20 3d 0a 7b 0a 09 49 4e 54 45 52 46 41 [] =.{..INTERFA
4590: 43 45 5f 4d 41 50 5f 45 4e 54 52 59 28 74 72 65 CE_MAP_ENTRY(tre
45a0: 65 5f 74 2c 20 69 69 64 5f 6d 61 70 5f 74 2c 20 e_t, iid_map_t,
45b0: 6d 61 70 29 2c 0a 7d 3b 0a 73 74 61 74 69 63 20 map),.};.static
45c0: 49 4e 54 45 52 46 41 43 45 5f 49 4d 50 4c 5f 51 INTERFACE_IMPL_Q
45d0: 55 45 52 59 28 6d 61 70 5f 74 2c 20 74 72 65 65 UERY(map_t, tree
45e0: 5f 74 2c 20 6d 61 70 29 0a 73 74 61 74 69 63 20 _t, map).static
45f0: 49 4e 54 45 52 46 41 43 45 5f 4f 50 53 5f 54 59 INTERFACE_OPS_TY
4600: 50 45 28 6d 61 70 5f 74 29 20 49 4e 54 45 52 46 PE(map_t) INTERF
4610: 41 43 45 5f 49 4d 50 4c 5f 4e 41 4d 45 28 6d 61 ACE_IMPL_NAME(ma
4620: 70 5f 74 2c 20 74 72 65 65 5f 74 29 20 3d 20 7b p_t, tree_t) = {
4630: 0a 09 49 4e 54 45 52 46 41 43 45 5f 49 4d 50 4c ..INTERFACE_IMPL
4640: 5f 51 55 45 52 59 5f 4d 45 54 48 4f 44 28 6d 61 _QUERY_METHOD(ma
4650: 70 5f 74 2c 20 74 72 65 65 5f 74 29 0a 09 49 4e p_t, tree_t)..IN
4660: 54 45 52 46 41 43 45 5f 49 4d 50 4c 5f 4d 45 54 TERFACE_IMPL_MET
4670: 48 4f 44 28 64 65 73 74 72 6f 79 2c 20 74 72 65 HOD(destroy, tre
4680: 65 5f 64 65 73 74 72 6f 79 29 0a 09 49 4e 54 45 e_destroy)..INTE
4690: 52 46 41 43 45 5f 49 4d 50 4c 5f 4d 45 54 48 4f RFACE_IMPL_METHO
46a0: 44 28 77 61 6c 6b 2c 20 74 72 65 65 5f 77 61 6c D(walk, tree_wal
46b0: 6b 29 0a 09 49 4e 54 45 52 46 41 43 45 5f 49 4d k)..INTERFACE_IM
46c0: 50 4c 5f 4d 45 54 48 4f 44 28 77 61 6c 6b 5f 72 PL_METHOD(walk_r
46d0: 61 6e 67 65 2c 20 74 72 65 65 5f 77 61 6c 6b 5f ange, tree_walk_
46e0: 72 61 6e 67 65 29 0a 09 49 4e 54 45 52 46 41 43 range)..INTERFAC
46f0: 45 5f 49 4d 50 4c 5f 4d 45 54 48 4f 44 28 70 75 E_IMPL_METHOD(pu
4700: 74 2c 20 74 72 65 65 5f 70 75 74 29 0a 09 49 4e t, tree_put)..IN
4710: 54 45 52 46 41 43 45 5f 49 4d 50 4c 5f 4d 45 54 TERFACE_IMPL_MET
4720: 48 4f 44 28 67 65 74 2c 20 74 72 65 65 5f 67 65 HOD(get, tree_ge
4730: 74 29 0a 09 49 4e 54 45 52 46 41 43 45 5f 49 4d t)..INTERFACE_IM
4740: 50 4c 5f 4d 45 54 48 4f 44 28 6f 70 74 69 6d 69 PL_METHOD(optimi
4750: 7a 65 2c 20 74 72 65 65 5f 6f 70 74 69 6d 69 7a ze, tree_optimiz
4760: 65 29 0a 09 49 4e 54 45 52 46 41 43 45 5f 49 4d e)..INTERFACE_IM
4770: 50 4c 5f 4d 45 54 48 4f 44 28 72 65 6d 6f 76 65 PL_METHOD(remove
4780: 2c 20 74 72 65 65 5f 72 65 6d 6f 76 65 29 0a 09 , tree_remove)..
4790: 49 4e 54 45 52 46 41 43 45 5f 49 4d 50 4c 5f 4d INTERFACE_IMPL_M
47a0: 45 54 48 4f 44 28 69 74 65 72 61 74 6f 72 2c 20 ETHOD(iterator,
47b0: 74 72 65 65 5f 69 74 65 72 61 74 6f 72 29 0a 09 tree_iterator)..
47c0: 49 4e 54 45 52 46 41 43 45 5f 49 4d 50 4c 5f 4d INTERFACE_IMPL_M
47d0: 45 54 48 4f 44 28 73 69 7a 65 2c 20 74 72 65 65 ETHOD(size, tree
47e0: 5f 73 69 7a 65 29 0a 7d 3b 0a 0a 6d 61 70 5f 74 _size).};..map_t
47f0: 20 2a 20 74 72 65 65 5f 6e 65 77 28 69 6e 74 20 * tree_new(int
4800: 28 2a 63 6f 6d 70 29 28 6d 61 70 5f 6b 65 79 20 (*comp)(map_key
4810: 6b 31 2c 20 6d 61 70 5f 6b 65 79 20 6b 32 29 2c k1, map_key k2),
4820: 20 74 72 65 65 6d 6f 64 65 20 6d 6f 64 65 29 0a treemode mode).
4830: 7b 0a 09 74 72 65 65 5f 69 6e 69 74 28 29 3b 0a {..tree_init();.
4840: 09 74 72 65 65 5f 74 20 2a 20 74 72 65 65 20 3d .tree_t * tree =
4850: 20 73 6c 61 62 5f 61 6c 6c 6f 63 28 74 72 65 65 slab_alloc(tree
4860: 73 29 3b 0a 09 74 72 65 65 2d 3e 6d 61 70 2e 6f s);..tree->map.o
4870: 70 73 20 3d 20 26 74 72 65 65 5f 74 5f 6d 61 70 ps = &tree_t_map
4880: 5f 74 3b 0a 09 74 72 65 65 2d 3e 72 6f 6f 74 20 _t;..tree->root
4890: 3d 20 30 3b 0a 09 74 72 65 65 2d 3e 6d 6f 64 65 = 0;..tree->mode
48a0: 20 3d 20 6d 6f 64 65 3b 0a 09 74 72 65 65 2d 3e = mode;..tree->
48b0: 63 6f 6d 70 20 3d 20 28 63 6f 6d 70 29 20 3f 20 comp = (comp) ?
48c0: 63 6f 6d 70 20 3a 20 6d 61 70 5f 6b 65 79 63 6d comp : map_keycm
48d0: 70 3b 0a 0a 09 72 65 74 75 72 6e 20 63 6f 6d 5f p;...return com_
48e0: 71 75 65 72 79 28 74 72 65 65 5f 74 5f 6d 61 70 query(tree_t_map
48f0: 2c 20 63 6f 75 6e 74 6f 66 28 74 72 65 65 5f 74 , countof(tree_t
4900: 5f 6d 61 70 29 2c 20 69 69 64 5f 6d 61 70 5f 74 _map), iid_map_t
4910: 2c 20 74 72 65 65 29 3b 0a 7d 0a 0a 6d 61 70 5f , tree);.}..map_
4920: 74 20 2a 20 73 70 6c 61 79 5f 6e 65 77 28 69 6e t * splay_new(in
4930: 74 20 28 2a 63 6f 6d 70 29 28 6d 61 70 5f 6b 65 t (*comp)(map_ke
4940: 79 20 6b 31 2c 20 6d 61 70 5f 6b 65 79 20 6b 32 y k1, map_key k2
4950: 29 29 0a 7b 0a 09 72 65 74 75 72 6e 20 74 72 65 )).{..return tre
4960: 65 5f 6e 65 77 28 63 6f 6d 70 2c 20 54 52 45 45 e_new(comp, TREE
4970: 5f 53 50 4c 41 59 29 3b 0a 7d 0a 0a 6d 61 70 5f _SPLAY);.}..map_
4980: 74 20 2a 20 74 72 65 61 70 5f 6e 65 77 28 69 6e t * treap_new(in
4990: 74 20 28 2a 63 6f 6d 70 29 28 6d 61 70 5f 6b 65 t (*comp)(map_ke
49a0: 79 20 6b 31 2c 20 6d 61 70 5f 6b 65 79 20 6b 32 y k1, map_key k2
49b0: 29 29 0a 7b 0a 09 72 65 74 75 72 6e 20 74 72 65 )).{..return tre
49c0: 65 5f 6e 65 77 28 63 6f 6d 70 2c 20 54 52 45 45 e_new(comp, TREE
49d0: 5f 54 52 45 41 50 29 3b 0a 7d 0a 0a 73 74 61 74 _TREAP);.}..stat
49e0: 69 63 20 76 6f 69 64 20 74 72 65 65 5f 67 72 61 ic void tree_gra
49f0: 70 68 5f 6e 6f 64 65 28 6e 6f 64 65 5f 74 20 2a ph_node(node_t *
4a00: 20 6e 6f 64 65 2c 20 69 6e 74 20 6c 65 76 65 6c node, int level
4a10: 29 0a 7b 0a 09 69 66 20 28 30 3d 3d 6e 6f 64 65 ).{..if (0==node
4a20: 29 20 7b 0a 09 09 72 65 74 75 72 6e 3b 0a 09 7d ) {...return;..}
4a30: 0a 0a 09 69 66 20 28 6e 6f 64 65 2d 3e 6c 65 66 ...if (node->lef
4a40: 74 29 20 7b 0a 09 09 74 72 65 65 5f 67 72 61 70 t) {...tree_grap
4a50: 68 5f 6e 6f 64 65 28 6e 6f 64 65 2d 3e 6c 65 66 h_node(node->lef
4a60: 74 2c 20 6c 65 76 65 6c 2b 31 29 3b 0a 09 7d 0a t, level+1);..}.
4a70: 09 6b 65 72 6e 65 6c 5f 70 72 69 6e 74 6b 28 22 .kernel_printk("
4a80: 25 64 5c 74 22 2c 20 6c 65 76 65 6c 29 3b 0a 09 %d\t", level);..
4a90: 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 6c for(int i=0; i<l
4aa0: 65 76 65 6c 3b 20 69 2b 2b 29 20 7b 0a 09 09 6b evel; i++) {...k
4ab0: 65 72 6e 65 6c 5f 70 72 69 6e 74 6b 28 22 20 20 ernel_printk("
4ac0: 22 29 3b 0a 09 7d 0a 09 6b 65 72 6e 65 6c 5f 70 ");..}..kernel_p
4ad0: 72 69 6e 74 6b 28 22 25 73 5c 6e 22 2c 20 6e 6f rintk("%s\n", no
4ae0: 64 65 2d 3e 64 61 74 61 29 3b 0a 09 69 66 20 28 de->data);..if (
4af0: 6e 6f 64 65 2d 3e 72 69 67 68 74 29 20 7b 0a 09 node->right) {..
4b00: 09 74 72 65 65 5f 67 72 61 70 68 5f 6e 6f 64 65 .tree_graph_node
4b10: 28 6e 6f 64 65 2d 3e 72 69 67 68 74 2c 20 6c 65 (node->right, le
4b20: 76 65 6c 2b 31 29 3b 0a 09 7d 0a 7d 0a 0a 23 69 vel+1);..}.}..#i
4b30: 66 20 30 0a 73 74 61 74 69 63 20 76 6f 69 64 20 f 0.static void
4b40: 74 72 65 65 5f 77 61 6c 6b 5f 64 75 6d 70 28 76 tree_walk_dump(v
4b50: 6f 69 64 20 2a 20 70 2c 20 76 6f 69 64 20 2a 20 oid * p, void *
4b60: 6b 65 79 2c 20 76 6f 69 64 20 2a 20 64 61 74 61 key, void * data
4b70: 29 0a 7b 0a 09 6b 65 72 6e 65 6c 5f 70 72 69 6e ).{..kernel_prin
4b80: 74 6b 28 22 25 73 5c 6e 22 2c 20 64 61 74 61 29 tk("%s\n", data)
4b90: 3b 0a 0a 09 69 66 20 28 70 29 20 7b 0a 09 09 6d ;...if (p) {...m
4ba0: 61 70 5f 74 20 2a 20 61 6b 6d 61 70 20 3d 20 28 ap_t * akmap = (
4bb0: 6d 61 70 5f 74 2a 29 70 3b 0a 09 09 2f 2a 20 41 map_t*)p;.../* A
4bc0: 64 64 20 74 68 65 20 64 61 74 61 20 74 6f 20 74 dd the data to t
4bd0: 68 65 20 61 6b 20 6d 61 70 20 2a 2f 0a 09 09 6d he ak map */...m
4be0: 61 70 5f 6b 65 79 20 2a 20 61 6b 20 3d 20 28 6d ap_key * ak = (m
4bf0: 61 70 5f 6b 65 79 2a 29 6d 61 70 5f 61 72 72 61 ap_key*)map_arra
4c00: 79 6b 65 79 32 28 28 69 6e 74 70 74 72 5f 74 29 ykey2((intptr_t)
4c10: 61 6b 6d 61 70 2c 20 2a 28 28 63 68 61 72 2a 29 akmap, *((char*)
4c20: 64 61 74 61 29 29 3b 0a 09 09 6d 61 70 5f 70 75 data));...map_pu
4c30: 74 70 70 28 61 6b 6d 61 70 2c 20 61 6b 2c 20 64 tpp(akmap, ak, d
4c40: 61 74 61 29 3b 0a 09 7d 0a 7d 0a 23 65 6e 64 69 ata);..}.}.#endi
4c50: 66 0a 0a 76 6f 69 64 20 74 72 65 65 5f 74 65 73 f..void tree_tes
4c60: 74 28 29 0a 7b 0a 09 74 72 65 65 5f 69 6e 69 74 t().{..tree_init
4c70: 28 29 3b 0a 09 6d 61 70 5f 74 20 2a 20 6d 61 70 ();..map_t * map
4c80: 20 3d 20 74 72 65 61 70 5f 6e 65 77 28 6d 61 70 = treap_new(map
4c90: 5f 73 74 72 63 6d 70 29 3b 0a 09 6d 61 70 5f 74 _strcmp);..map_t
4ca0: 20 2a 20 61 6b 6d 61 70 20 3d 20 74 72 65 65 5f * akmap = tree_
4cb0: 6e 65 77 28 6d 61 70 5f 61 72 72 61 79 63 6d 70 new(map_arraycmp
4cc0: 2c 20 30 29 3b 0a 09 6d 61 70 5f 74 65 73 74 28 , 0);..map_test(
4cd0: 6d 61 70 2c 20 61 6b 6d 61 70 29 3b 0a 0a 09 74 map, akmap);...t
4ce0: 72 65 65 5f 67 72 61 70 68 5f 6e 6f 64 65 28 63 ree_graph_node(c
4cf0: 6f 6e 74 61 69 6e 65 72 5f 6f 66 28 61 6b 6d 61 ontainer_of(akma
4d00: 70 2c 20 74 72 65 65 5f 74 2c 20 6d 61 70 29 2d p, tree_t, map)-
4d10: 3e 72 6f 6f 74 2c 20 30 29 3b 0a 09 6d 61 70 5f >root, 0);..map_
4d20: 6f 70 74 69 6d 69 7a 65 28 61 6b 6d 61 70 29 3b optimize(akmap);
4d30: 0a 09 74 72 65 65 5f 67 72 61 70 68 5f 6e 6f 64 ..tree_graph_nod
4d40: 65 28 63 6f 6e 74 61 69 6e 65 72 5f 6f 66 28 61 e(container_of(a
4d50: 6b 6d 61 70 2c 20 74 72 65 65 5f 74 2c 20 6d 61 kmap, tree_t, ma
4d60: 70 29 2d 3e 72 6f 6f 74 2c 20 30 29 3b 0a 7d 0a p)->root, 0);.}.