1 /*
2 An implementation of top-down splaying with sizes
3 D. Sleator <[email protected]>, January 1994.
4
5 This extends top-down-splay.c to maintain a size field in each node.
6 This is the number of nodes in the subtree rooted there. This makes
7 it possible to efficiently compute the rank of a key. (The rank is
8 the number of nodes to the left of the given key.) It it also
9 possible to quickly find the node of a given rank. Both of these
10 operations are illustrated in the code below. The remainder of this
11 introduction is taken from top-down-splay.c.
12
13 [[ XXX: size maintenance has been removed; not used in lighttpd ]]
14
15 "Splay trees", or "self-adjusting search trees" are a simple and
16 efficient data structure for storing an ordered set. The data
17 structure consists of a binary tree, with no additional fields. It
18 allows searching, insertion, deletion, deletemin, deletemax,
19 splitting, joining, and many other operations, all with amortized
20 logarithmic performance. Since the trees adapt to the sequence of
21 requests, their performance on real access patterns is typically even
22 better. Splay trees are described in a number of texts and papers
23 [1,2,3,4].
24
25 The code here is adapted from simple top-down splay, at the bottom of
26 page 669 of [2]. It can be obtained via anonymous ftp from
27 spade.pc.cs.cmu.edu in directory /usr/sleator/public.
28
29 The chief modification here is that the splay operation works even if the
30 item being splayed is not in the tree, and even if the tree root of the
31 tree is NULL. So the line:
32
33 t = splay(i, t);
34
35 causes it to search for item with key i in the tree rooted at t. If it's
36 there, it is splayed to the root. If it isn't there, then the node put
37 at the root is the last one before NULL that would have been reached in a
38 normal binary search for i. (It's a neighbor of i in the tree.) This
39 allows many other operations to be easily implemented, as shown below.
40
41 [1] "Data Structures and Their Algorithms", Lewis and Denenberg,
42 Harper Collins, 1991, pp 243-251.
43 [2] "Self-adjusting Binary Search Trees" Sleator and Tarjan,
44 JACM Volume 32, No 3, July 1985, pp 652-686.
45 [3] "Data Structure and Algorithm Analysis", Mark Weiss,
46 Benjamin Cummins, 1992, pp 119-130.
47 [4] "Data Structures, Algorithms, and Performance", Derick Wood,
48 Addison-Wesley, 1993, pp 367-375
49 */
50
51 #include "algo_splaytree.h"
52 #include <stdlib.h>
53 #include <assert.h>
54
55 #define compare(i,j) ((i)-(j))
56 /* This is the comparison. */
57 /* Returns <0 if i<j, =0 if i=j, and >0 if i>j */
58
59 /* Splay using the key i (which may or may not be in the tree.)
60 * The starting root is t, and the tree used is defined by rat
61 */
splaytree_splay(splay_tree * t,int i)62 splay_tree * splaytree_splay (splay_tree *t, int i) {
63 splay_tree N, *l, *r, *y;
64 int comp;
65
66 if (t == NULL) return t;
67 N.left = N.right = NULL;
68 l = r = &N;
69
70 for (;;) {
71 comp = compare(i, t->key);
72 if (comp < 0) {
73 if (t->left == NULL) break;
74 if (compare(i, t->left->key) < 0) {
75 y = t->left; /* rotate right */
76 t->left = y->right;
77 y->right = t;
78 t = y;
79 if (t->left == NULL) break;
80 }
81 r->left = t; /* link right */
82 r = t;
83 t = t->left;
84 } else if (comp > 0) {
85 if (t->right == NULL) break;
86 if (compare(i, t->right->key) > 0) {
87 y = t->right; /* rotate left */
88 t->right = y->left;
89 y->left = t;
90 t = y;
91 if (t->right == NULL) break;
92 }
93 l->right = t; /* link left */
94 l = t;
95 t = t->right;
96 } else {
97 break;
98 }
99 }
100
101 l->right = t->left; /* assemble */
102 r->left = t->right;
103 t->left = N.right;
104 t->right = N.left;
105
106 return t;
107 }
108
splaytree_insert(splay_tree * t,int i,void * data)109 splay_tree * splaytree_insert(splay_tree * t, int i, void *data) {
110 /* Insert key i into the tree t, if it is not already there. */
111 /* Return a pointer to the resulting tree. */
112 splay_tree * new;
113
114 if (t != NULL) {
115 t = splaytree_splay(t, i);
116 if (compare(i, t->key)==0) {
117 return t; /* it's already there */
118 }
119 }
120 new = (splay_tree *) malloc (sizeof (splay_tree));
121 assert(new);
122 if (t == NULL) {
123 new->left = new->right = NULL;
124 } else if (compare(i, t->key) < 0) {
125 new->left = t->left;
126 new->right = t;
127 t->left = NULL;
128 } else {
129 new->right = t->right;
130 new->left = t;
131 t->right = NULL;
132 }
133 new->key = i;
134 new->data = data;
135 return new;
136 }
137
splaytree_delete(splay_tree * t,int i)138 splay_tree * splaytree_delete(splay_tree *t, int i) {
139 /* Deletes i from the tree if it's there. */
140 /* Return a pointer to the resulting tree. */
141 splay_tree * x;
142 if (t==NULL) return NULL;
143 t = splaytree_splay(t, i);
144 if (compare(i, t->key) == 0) { /* found it */
145 if (t->left == NULL) {
146 x = t->right;
147 } else {
148 x = splaytree_splay(t->left, i);
149 x->right = t->right;
150 }
151 free(t);
152 return x;
153 } else {
154 return t; /* It wasn't there */
155 }
156 }
157