1#include <structures/splay.h>
2
3static void rotate_left(struct splay_tree *tree, struct splay_node *x) {
4 struct splay_node *y = x->right;
5 x->right = y->left;
6 if (y->left) {
7 y->left->parent = x;
8 }
9 y->parent = x->parent;
10 if (!x->parent) {
11 tree->root = y;
12 } else if (x == x->parent->left) {
13 x->parent->left = y;
14 } else {
15 x->parent->right = y;
16 }
17 y->left = x;
18 x->parent = y;
19}
20
21static void rotate_right(struct splay_tree *tree, struct splay_node *y) {
22 struct splay_node *x = y->left;
23 y->left = x->right;
24 if (x->right) {
25 x->right->parent = y;
26 }
27 x->parent = y->parent;
28 if (!y->parent) {
29 tree->root = x;
30 } else if (y == y->parent->left) {
31 y->parent->left = x;
32 } else {
33 y->parent->right = x;
34 }
35 x->right = y;
36 y->parent = x;
37}
38
39void splay(struct splay_tree *tree, struct splay_node *x) {
40 if (!tree || !x) {
41 return;
42 }
43
44 while (x->parent) {
45 if (!x->parent->parent) {
46 /* Zig */
47 if (x->parent->left == x) {
48 rotate_right(tree, y: x->parent);
49 } else {
50 rotate_left(tree, x: x->parent);
51 }
52 } else if (x->parent->left == x &&
53 x->parent->parent->left == x->parent) {
54 /* Zig-Zig (left-left) */
55 rotate_right(tree, y: x->parent->parent);
56 rotate_right(tree, y: x->parent);
57 } else if (x->parent->right == x &&
58 x->parent->parent->right == x->parent) {
59 /* Zig-Zig (right-right) */
60 rotate_left(tree, x: x->parent->parent);
61 rotate_left(tree, x: x->parent);
62 } else if (x->parent->left == x &&
63 x->parent->parent->right == x->parent) {
64 /* Zig-Zag (right-left) */
65 rotate_right(tree, y: x->parent);
66 rotate_left(tree, x: x->parent);
67 } else {
68 /* Zig-Zag (left-right) */
69 rotate_left(tree, x: x->parent);
70 rotate_right(tree, y: x->parent);
71 }
72 }
73}
74
75void splay_tree_init(struct splay_tree *tree,
76 const struct splay_node_ops *ops) {
77 tree->root = NULL;
78 tree->ops = ops;
79}
80
81void splay_insert(struct splay_tree *tree, struct splay_node *node) {
82 splay_init_node(n: node);
83
84 if (!tree->root) {
85 tree->root = node;
86 return;
87 }
88
89 struct splay_node *cur = tree->root;
90 struct splay_node *p = NULL;
91 int cmp = 0;
92
93 while (cur) {
94 p = cur;
95 cmp = tree->ops->cmp(node, cur);
96 if (cmp < 0) {
97 cur = cur->left;
98 } else {
99 cur = cur->right;
100 }
101 }
102
103 node->parent = p;
104 if (cmp < 0) {
105 p->left = node;
106 } else {
107 p->right = node;
108 }
109
110 splay(tree, x: node);
111}
112
113void splay_remove(struct splay_tree *tree, struct splay_node *node) {
114 if (!tree || !tree->root || !node) {
115 return;
116 }
117
118 splay(tree, x: node);
119
120 if (!node->left) {
121 tree->root = node->right;
122 if (tree->root) {
123 tree->root->parent = NULL;
124 }
125 } else {
126 struct splay_node *left_sub = node->left;
127 left_sub->parent = NULL;
128
129 struct splay_node *max = left_sub;
130 while (max->right) {
131 max = max->right;
132 }
133
134 tree->root = left_sub;
135 splay(tree, x: max);
136
137 max->right = node->right;
138 if (max->right) {
139 max->right->parent = max;
140 }
141 tree->root = max;
142 }
143
144 splay_init_node(n: node);
145}
146
147struct splay_node *splay_find(struct splay_tree *tree, const void *key) {
148 if (!tree || !tree->root) {
149 return NULL;
150 }
151
152 struct splay_node *x = tree->root;
153 struct splay_node *last = NULL;
154
155 while (x) {
156 last = x;
157 int cmp = tree->ops->cmp_key(x, key);
158 if (cmp == 0) {
159 break;
160 } else if (cmp > 0) {
161 x = x->left;
162 } else {
163 x = x->right;
164 }
165 }
166
167 if (last) {
168 splay(tree, x: last);
169 }
170
171 if (x && tree->ops->cmp_key(x, key) == 0) {
172 return x;
173 }
174
175 return NULL;
176}
177
178struct splay_node *splay_first(const struct splay_tree *tree) {
179 if (!tree || !tree->root) {
180 return NULL;
181 }
182 struct splay_node *node = tree->root;
183 while (node->left) {
184 node = node->left;
185 }
186 return node;
187}
188
189struct splay_node *splay_last(const struct splay_tree *tree) {
190 if (!tree || !tree->root) {
191 return NULL;
192 }
193 struct splay_node *node = tree->root;
194 while (node->right) {
195 node = node->right;
196 }
197 return node;
198}
199
200struct splay_node *splay_next(const struct splay_node *node) {
201 if (!node) {
202 return NULL;
203 }
204
205 if (node->right) {
206 node = node->right;
207 while (node->left) {
208 node = node->left;
209 }
210 return (struct splay_node *) node;
211 }
212
213 struct splay_node *parent = node->parent;
214 while (parent && node == parent->right) {
215 node = parent;
216 parent = parent->parent;
217 }
218 return parent;
219}
220
221struct splay_node *splay_prev(const struct splay_node *node) {
222 if (!node) {
223 return NULL;
224 }
225
226 if (node->left) {
227 node = node->left;
228 while (node->right) {
229 node = node->right;
230 }
231 return (struct splay_node *) node;
232 }
233
234 struct splay_node *parent = node->parent;
235 while (parent && node == parent->left) {
236 node = parent;
237 parent = parent->parent;
238 }
239 return parent;
240}
241