TWCOS Kernel

Hex Artifact Content
Login

Artifact c7d49e1daa41a5721b376e4c9e101bfa4d56f9bf:


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);.}.