1 /*
2 * ivykis, an event handling library
3 * Copyright (C) 2010 Lennert Buytenhek
4 * Dedicated to Marija Kulikova.
5 *
6 * This library is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU Lesser General Public License version
8 * 2.1 as published by the Free Software Foundation.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU Lesser General Public License version 2.1 for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public
16 * License version 2.1 along with this library; if not, write to the
17 * Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
18 * Boston, MA 02110-1301, USA.
19 */
20
21 #include <stdio.h>
22 #include <iv.h>
23 #include "iv_avl.h"
24
height(const struct iv_avl_node * an)25 static int height(const struct iv_avl_node *an)
26 {
27 return an != NULL ? an->height : 0;
28 }
29
recalc_height(struct iv_avl_node * an)30 static void recalc_height(struct iv_avl_node *an)
31 {
32 int hl;
33 int hr;
34
35 hl = height(an->left);
36 hr = height(an->right);
37 an->height = 1 + ((hl > hr) ? hl : hr);
38 }
39
40 /*
41 * There are four different rotations that may need to be performed
42 * to rebalance subtrees after an insertion or deletion operation.
43 *
44 * In the diagrams below, the letters a - g symbolise tree nodes or
45 * subtrees, where capital letters denote nodes that are guaranteed
46 * to be present, and lower case letters denote nodes that may be NULL.
47 *
48 * The tables document the balance factors for each of the capital
49 * letter nodes, where the balance factor is defined as the height of
50 * the right subtree minus the height of the left subtree.
51 *
52 *
53 * left rotation:
54 *
55 * B D before | after
56 * / \ / \ B D | D B
57 * a D => B E --------+--------
58 * / \ / \ +2 0 | -1 +1
59 * c E a c +2 +1 | 0 0
60 *
61 *
62 * right rotation:
63 *
64 * D B before | after
65 * / \ / \ D B | B D
66 * B e => A D --------+--------
67 * / \ / \ -2 -1 | 0 0
68 * A c c e -2 0 | +1 -1
69 *
70 *
71 * left-right rotation:
72 *
73 * F D before | after
74 * / \ / \ F B D | D B F
75 * B g => / \ ------------+------------
76 * / \ B F -2 +1 -1 | 0 0 +1
77 * a D / \ / \ -2 +1 0 | 0 0 0
78 * / \ a c e g -2 +1 +1 | 0 -1 0
79 * c e
80 *
81 *
82 * right-left rotation:
83 *
84 * B D before | after
85 * / \ / \ B F D | D B F
86 * a F => / \ ------------+------------
87 * / \ B F +2 -1 -1 | 0 0 +1
88 * D g / \ / \ +2 -1 0 | 0 0 0
89 * / \ a c e g +2 -1 +1 | 0 -1 0
90 * c e
91 */
rotate_left(struct iv_avl_node ** root)92 static void rotate_left(struct iv_avl_node **root)
93 {
94 struct iv_avl_node *b = *root;
95 struct iv_avl_node *d = b->right;
96 struct iv_avl_node *c;
97
98 c = d->left;
99 b->right = c;
100 if (c != NULL)
101 c->parent = b;
102 recalc_height(b);
103
104 d->left = b;
105 d->parent = b->parent;
106 b->parent = d;
107 recalc_height(d);
108
109 *root = d;
110 }
111
rotate_right(struct iv_avl_node ** root)112 static void rotate_right(struct iv_avl_node **root)
113 {
114 struct iv_avl_node *d = *root;
115 struct iv_avl_node *b = d->left;
116 struct iv_avl_node *c;
117
118 c = b->right;
119 d->left = c;
120 if (c != NULL)
121 c->parent = d;
122 recalc_height(d);
123
124 b->right = d;
125 b->parent = d->parent;
126 d->parent = b;
127 recalc_height(b);
128
129 *root = b;
130 }
131
rotate_left_right(struct iv_avl_node ** root)132 static void rotate_left_right(struct iv_avl_node **root)
133 {
134 struct iv_avl_node *f = *root;
135 struct iv_avl_node *b = f->left;
136 struct iv_avl_node *d = b->right;
137 struct iv_avl_node *c;
138 struct iv_avl_node *e;
139
140 c = d->left;
141 b->right = c;
142 if (c != NULL)
143 c->parent = b;
144 recalc_height(b);
145
146 e = d->right;
147 f->left = e;
148 if (e != NULL)
149 e->parent = f;
150 recalc_height(f);
151
152 d->left = b;
153 d->right = f;
154 d->parent = f->parent;
155 b->parent = d;
156 f->parent = d;
157 recalc_height(d);
158
159 *root = d;
160 }
161
rotate_right_left(struct iv_avl_node ** root)162 static void rotate_right_left(struct iv_avl_node **root)
163 {
164 struct iv_avl_node *b = *root;
165 struct iv_avl_node *f = b->right;
166 struct iv_avl_node *d = f->left;
167 struct iv_avl_node *c;
168 struct iv_avl_node *e;
169
170 c = d->left;
171 b->right = c;
172 if (c != NULL)
173 c->parent = b;
174 recalc_height(b);
175
176 e = d->right;
177 f->left = e;
178 if (e != NULL)
179 e->parent = f;
180 recalc_height(f);
181
182 d->left = b;
183 d->right = f;
184 d->parent = b->parent;
185 b->parent = d;
186 f->parent = d;
187 recalc_height(d);
188
189 *root = d;
190 }
191
balance(const struct iv_avl_node * an)192 static int balance(const struct iv_avl_node *an)
193 {
194 return height(an->right) - height(an->left);
195 }
196
rebalance_node(struct iv_avl_node ** _root)197 static void rebalance_node(struct iv_avl_node **_root)
198 {
199 struct iv_avl_node *root = *_root;
200 int bal;
201
202 bal = balance(root);
203 if (bal == -2) {
204 if (balance(root->left) <= 0)
205 rotate_right(_root);
206 else
207 rotate_left_right(_root);
208 } else if (bal == 2) {
209 if (balance(root->right) < 0)
210 rotate_right_left(_root);
211 else
212 rotate_left(_root);
213 }
214 }
215
216 /*
217 * Find the address of the (child) pointer that points to an.
218 */
219 static struct iv_avl_node **
find_reference(struct iv_avl_tree * tree,const struct iv_avl_node * an)220 find_reference(struct iv_avl_tree *tree, const struct iv_avl_node *an)
221 {
222 if (an->parent != NULL) {
223 if (an->parent->left == an)
224 return &an->parent->left;
225 else
226 return &an->parent->right;
227 } else {
228 return &tree->root;
229 }
230 }
231
replace_reference(struct iv_avl_tree * tree,const struct iv_avl_node * an,struct iv_avl_node * new_child)232 static void replace_reference(struct iv_avl_tree *tree,
233 const struct iv_avl_node *an,
234 struct iv_avl_node *new_child)
235 {
236 *find_reference(tree, an) = new_child;
237 }
238
239 /*
240 * Rebalance the tree from an back to the root. Rebalancing can stop
241 * at the first node where no re-balancing was needed, or where
242 * re-balancing restored the height of the subtree to what it was
243 * before the insertion or deletion.
244 */
rebalance_path(struct iv_avl_tree * tree,struct iv_avl_node * an)245 static void rebalance_path(struct iv_avl_tree *tree, struct iv_avl_node *an)
246 {
247 while (an != NULL) {
248 int old_height;
249 struct iv_avl_node **ref;
250
251 old_height = an->height;
252 recalc_height(an);
253
254 ref = find_reference(tree, an);
255 rebalance_node(ref);
256 an = *ref;
257
258 if (old_height == an->height)
259 break;
260
261 an = an->parent;
262 }
263 }
264
iv_avl_tree_insert(struct iv_avl_tree * tree,struct iv_avl_node * an)265 int iv_avl_tree_insert(struct iv_avl_tree *tree, struct iv_avl_node *an)
266 {
267 struct iv_avl_node *p;
268 struct iv_avl_node **pp;
269
270 /*
271 * Find the node to which an is to be attached as a leaf.
272 */
273 p = NULL;
274 pp = &tree->root;
275 while (*pp != NULL) {
276 int ret;
277
278 p = *pp;
279
280 ret = tree->compare(an, p);
281 if (ret < 0)
282 pp = &p->left;
283 else if (ret > 0)
284 pp = &p->right;
285 else
286 return -1;
287 }
288
289 /*
290 * Insert an.
291 */
292 an->left = NULL;
293 an->right = NULL;
294 an->parent = p;
295 an->height = 1;
296 *pp = an;
297
298 /*
299 * Start rebalancing from an's parent.
300 */
301 rebalance_path(tree, p);
302
303 return 0;
304 }
305
306 static struct iv_avl_node *
iv_avl_tree_delete_leaf(struct iv_avl_tree * tree,struct iv_avl_node * an)307 iv_avl_tree_delete_leaf(struct iv_avl_tree *tree, struct iv_avl_node *an)
308 {
309 /*
310 * Simply replace the reference from an's parent to an by NULL,
311 * and start rebalancing from an's parent.
312 */
313 replace_reference(tree, an, NULL);
314
315 return an->parent;
316 }
317
318 static struct iv_avl_node *
iv_avl_tree_delete_nonleaf(struct iv_avl_tree * tree,struct iv_avl_node * an)319 iv_avl_tree_delete_nonleaf(struct iv_avl_tree *tree, struct iv_avl_node *an)
320 {
321 struct iv_avl_node *victim;
322 struct iv_avl_node *p;
323
324 /*
325 * an is not a leaf node, so removing it is slightly more
326 * complicated than NULLing its parent's reference to it.
327 *
328 * an will be replaced by either the maximum node in the
329 * left subtree or the minimum node in the right subtree,
330 * depending on the relative heights of those subtrees. We
331 * call the replacing node the victim node.
332 *
333 * The victim node, i.e. the maximum (minimum) node in the
334 * left (right) subtree could still have a left (right) child
335 * node. Here, we replace the victim node by its child, and
336 * unlink the victim node from the tree.
337 */
338 if (height(an->left) > height(an->right)) {
339 victim = an->left;
340 while (victim->right != NULL)
341 victim = victim->right;
342
343 replace_reference(tree, victim, victim->left);
344 if (victim->left != NULL)
345 victim->left->parent = victim->parent;
346 } else {
347 victim = an->right;
348 while (victim->left != NULL)
349 victim = victim->left;
350
351 replace_reference(tree, victim, victim->right);
352 if (victim->right != NULL)
353 victim->right->parent = victim->parent;
354 }
355
356 /*
357 * We will start rebalancing the tree from the victim node's
358 * original parent, unless that original parent is an, in which
359 * case we will start rebalancing from the victim node itself
360 * (after it has replaced an).
361 */
362 p = victim->parent;
363 if (p == an)
364 p = victim;
365
366 /*
367 * Point an's parent's pointer to it to victim, move an's
368 * children to victim, and make an's children point back to
369 * victim as their parent.
370 */
371 replace_reference(tree, an, victim);
372 victim->left = an->left;
373 victim->right = an->right;
374 victim->parent = an->parent;
375 victim->height = an->height;
376 if (victim->left != NULL)
377 victim->left->parent = victim;
378 if (victim->right != NULL)
379 victim->right->parent = victim;
380
381 return p;
382 }
383
iv_avl_tree_delete(struct iv_avl_tree * tree,struct iv_avl_node * an)384 void iv_avl_tree_delete(struct iv_avl_tree *tree, struct iv_avl_node *an)
385 {
386 struct iv_avl_node *p;
387
388 if (an->left == NULL && an->right == NULL)
389 p = iv_avl_tree_delete_leaf(tree, an);
390 else
391 p = iv_avl_tree_delete_nonleaf(tree, an);
392
393 rebalance_path(tree, p);
394 }
395
iv_avl_tree_next(struct iv_avl_node * an)396 struct iv_avl_node *iv_avl_tree_next(struct iv_avl_node *an)
397 {
398 struct iv_avl_node *p;
399
400 if (an->right != NULL) {
401 an = an->right;
402 while (an->left != NULL)
403 an = an->left;
404
405 return an;
406 }
407
408 p = an->parent;
409 while (p != NULL && an == p->right) {
410 an = p;
411 p = an->parent;
412 }
413
414 return p;
415 }
416
iv_avl_tree_prev(struct iv_avl_node * an)417 struct iv_avl_node *iv_avl_tree_prev(struct iv_avl_node *an)
418 {
419 struct iv_avl_node *p;
420
421 if (an->left != NULL) {
422 an = an->left;
423 while (an->right != NULL)
424 an = an->right;
425
426 return an;
427 }
428
429 p = an->parent;
430 while (p != NULL && an == p->left) {
431 an = p;
432 p = an->parent;
433 }
434
435 return p;
436 }
437