2 splay_tree.c -- splay tree and linked list convenience
3 Copyright (C) 2004-2013 Guus Sliepen <guus@tinc-vpn.org>
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
10 This program 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 General Public License for more details.
15 You should have received a copy of the GNU General Public License along
16 with this program; if not, write to the Free Software Foundation, Inc.,
17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22 #include "splay_tree.h"
27 static splay_node_t
*splay_top_down(splay_tree_t
*tree
, const void *data
, int *result
) {
28 splay_node_t left
= {NULL
}, right
= {NULL
};
29 splay_node_t
*leftbottom
= &left
, *rightbottom
= &right
, *child
, *grandchild
;
30 splay_node_t
*root
= tree
->root
;
39 while((c
= tree
->compare(data
, root
->data
))) {
40 if(c
< 0 && (child
= root
->left
)) {
41 c
= tree
->compare(data
, child
->data
);
43 if(c
< 0 && (grandchild
= child
->left
)) {
44 rightbottom
->left
= child
;
45 child
->parent
= rightbottom
;
48 if((root
->left
= child
->right
))
49 child
->right
->parent
= root
;
55 grandchild
->parent
= NULL
;
58 } else if (c
> 0 && (grandchild
= child
->right
)) {
59 leftbottom
->right
= child
;
60 child
->parent
= leftbottom
;
64 grandchild
->parent
= NULL
;
66 rightbottom
->left
= root
;
67 root
->parent
= rightbottom
;
74 rightbottom
->left
= root
;
75 root
->parent
= rightbottom
;
84 } else if(c
> 0 && (child
= root
->right
)) {
85 c
= tree
->compare(data
, child
->data
);
87 if(c
> 0 && (grandchild
= child
->right
)) {
88 leftbottom
->right
= child
;
89 child
->parent
= leftbottom
;
92 if((root
->right
= child
->left
))
93 child
->left
->parent
= root
;
99 grandchild
->parent
= NULL
;
102 } else if (c
< 0 && (grandchild
= child
->left
)) {
103 rightbottom
->left
= child
;
104 child
->parent
= rightbottom
;
108 grandchild
->parent
= NULL
;
110 leftbottom
->right
= root
;
111 root
->parent
= leftbottom
;
118 leftbottom
->right
= root
;
119 root
->parent
= leftbottom
;
123 child
->parent
= NULL
;
137 leftbottom
->right
= root
->left
;
138 root
->left
->parent
= leftbottom
;
140 root
->left
= left
.right
;
141 left
.right
->parent
= root
;
146 rightbottom
->left
= root
->right
;
147 root
->right
->parent
= rightbottom
;
149 root
->right
= right
.left
;
150 right
.left
->parent
= root
;
162 static void splay_bottom_up(splay_tree_t
*tree
, splay_node_t
*node
) {
163 splay_node_t
*parent
, *grandparent
, *greatgrandparent
;
165 while((parent
= node
->parent
)) {
166 if(!(grandparent
= parent
->parent
)) { /* zig */
167 if(node
== parent
->left
) {
168 if((parent
->left
= node
->right
))
169 parent
->left
->parent
= parent
;
170 node
->right
= parent
;
172 if((parent
->right
= node
->left
))
173 parent
->right
->parent
= parent
;
177 parent
->parent
= node
;
180 greatgrandparent
= grandparent
->parent
;
182 if(node
== parent
->left
&& parent
== grandparent
->left
) { /* left zig-zig */
183 if((grandparent
->left
= parent
->right
))
184 grandparent
->left
->parent
= grandparent
;
185 parent
->right
= grandparent
;
186 grandparent
->parent
= parent
;
188 if((parent
->left
= node
->right
))
189 parent
->left
->parent
= parent
;
190 node
->right
= parent
;
191 parent
->parent
= node
;
192 } else if(node
== parent
->right
&& parent
== grandparent
->right
) { /* right zig-zig */
193 if((grandparent
->right
= parent
->left
))
194 grandparent
->right
->parent
= grandparent
;
195 parent
->left
= grandparent
;
196 grandparent
->parent
= parent
;
198 if((parent
->right
= node
->left
))
199 parent
->right
->parent
= parent
;
201 parent
->parent
= node
;
202 } else if(node
== parent
->right
&& parent
== grandparent
->left
) { /* left-right zig-zag */
203 if((parent
->right
= node
->left
))
204 parent
->right
->parent
= parent
;
206 parent
->parent
= node
;
208 if((grandparent
->left
= node
->right
))
209 grandparent
->left
->parent
= grandparent
;
210 node
->right
= grandparent
;
211 grandparent
->parent
= node
;
212 } else { /* right-left zig-zag */
213 if((parent
->left
= node
->right
))
214 parent
->left
->parent
= parent
;
215 node
->right
= parent
;
216 parent
->parent
= node
;
218 if((grandparent
->right
= node
->left
))
219 grandparent
->right
->parent
= grandparent
;
220 node
->left
= grandparent
;
221 grandparent
->parent
= node
;
224 if((node
->parent
= greatgrandparent
)) {
225 if(grandparent
== greatgrandparent
->left
)
226 greatgrandparent
->left
= node
;
228 greatgrandparent
->right
= node
;
236 /* (De)constructors */
238 splay_tree_t
*splay_alloc_tree(splay_compare_t compare
, splay_action_t
delete) {
241 tree
= xzalloc(sizeof(splay_tree_t
));
242 tree
->compare
= compare
;
243 tree
->delete = delete;
248 void splay_free_tree(splay_tree_t
*tree
) {
252 splay_node_t
*splay_alloc_node(void) {
253 return xzalloc(sizeof(splay_node_t
));
256 void splay_free_node(splay_tree_t
*tree
, splay_node_t
*node
) {
257 if(node
->data
&& tree
->delete)
258 tree
->delete(node
->data
);
265 void *splay_search(splay_tree_t
*tree
, const void *data
) {
268 node
= splay_search_node(tree
, data
);
270 return node
? node
->data
: NULL
;
273 void *splay_search_closest(splay_tree_t
*tree
, const void *data
, int *result
) {
276 node
= splay_search_closest_node(tree
, data
, result
);
278 return node
? node
->data
: NULL
;
281 void *splay_search_closest_smaller(splay_tree_t
*tree
, const void *data
) {
284 node
= splay_search_closest_smaller_node(tree
, data
);
286 return node
? node
->data
: NULL
;
289 void *splay_search_closest_greater(splay_tree_t
*tree
, const void *data
) {
292 node
= splay_search_closest_greater_node(tree
, data
);
294 return node
? node
->data
: NULL
;
297 splay_node_t
*splay_search_node(splay_tree_t
*tree
, const void *data
) {
301 node
= splay_search_closest_node(tree
, data
, &result
);
303 return result
? NULL
: node
;
306 splay_node_t
*splay_search_closest_node_nosplay(const splay_tree_t
*tree
, const void *data
, int *result
) {
319 c
= tree
->compare(data
, node
->data
);
341 splay_node_t
*splay_search_closest_node(splay_tree_t
*tree
, const void *data
, int *result
) {
342 return splay_top_down(tree
, data
, result
);
345 splay_node_t
*splay_search_closest_smaller_node(splay_tree_t
*tree
, const void *data
) {
349 node
= splay_search_closest_node(tree
, data
, &result
);
357 splay_node_t
*splay_search_closest_greater_node(splay_tree_t
*tree
, const void *data
) {
361 node
= splay_search_closest_node(tree
, data
, &result
);
369 /* Insertion and deletion */
371 splay_node_t
*splay_insert(splay_tree_t
*tree
, void *data
) {
372 splay_node_t
*closest
, *new;
376 new = splay_alloc_node();
378 splay_insert_top(tree
, new);
380 closest
= splay_search_closest_node(tree
, data
, &result
);
385 new = splay_alloc_node();
389 splay_insert_before(tree
, closest
, new);
391 splay_insert_after(tree
, closest
, new);
397 splay_node_t
*splay_insert_node(splay_tree_t
*tree
, splay_node_t
*node
) {
398 splay_node_t
*closest
;
401 node
->left
= node
->right
= node
->parent
= node
->next
= node
->prev
= NULL
;
404 splay_insert_top(tree
, node
);
406 closest
= splay_search_closest_node(tree
, node
->data
, &result
);
412 splay_insert_before(tree
, closest
, node
);
414 splay_insert_after(tree
, closest
, node
);
420 void splay_insert_top(splay_tree_t
*tree
, splay_node_t
*node
) {
421 node
->prev
= node
->next
= node
->left
= node
->right
= node
->parent
= NULL
;
422 tree
->head
= tree
->tail
= tree
->root
= node
;
426 void splay_insert_before(splay_tree_t
*tree
, splay_node_t
*before
, splay_node_t
*node
) {
429 splay_insert_after(tree
, tree
->tail
, node
);
431 splay_insert_top(tree
, node
);
436 if((node
->prev
= before
->prev
))
437 before
->prev
->next
= node
;
442 splay_bottom_up(tree
, before
);
444 node
->right
= before
;
445 before
->parent
= node
;
446 if((node
->left
= before
->left
))
447 before
->left
->parent
= node
;
455 void splay_insert_after(splay_tree_t
*tree
, splay_node_t
*after
, splay_node_t
*node
) {
458 splay_insert_before(tree
, tree
->head
, node
);
460 splay_insert_top(tree
, node
);
465 if((node
->next
= after
->next
))
466 after
->next
->prev
= node
;
471 splay_bottom_up(tree
, after
);
474 after
->parent
= node
;
475 if((node
->right
= after
->right
))
476 after
->right
->parent
= node
;
484 splay_node_t
*splay_unlink(splay_tree_t
*tree
, void *data
) {
487 node
= splay_search_node(tree
, data
);
490 splay_unlink_node(tree
, node
);
495 void splay_unlink_node(splay_tree_t
*tree
, splay_node_t
*node
) {
497 node
->prev
->next
= node
->next
;
499 tree
->head
= node
->next
;
502 node
->next
->prev
= node
->prev
;
504 tree
->tail
= node
->prev
;
506 splay_bottom_up(tree
, node
);
509 node
->left
->parent
= NULL
;
510 tree
->root
= node
->left
;
511 if((node
->prev
->right
= node
->right
))
512 node
->right
->parent
= node
->prev
;
513 } else if(node
->next
) {
514 tree
->root
= node
->right
;
515 node
->right
->parent
= NULL
;
523 void splay_delete_node(splay_tree_t
*tree
, splay_node_t
*node
) {
524 splay_unlink_node(tree
, node
);
525 splay_free_node(tree
, node
);
528 void splay_delete(splay_tree_t
*tree
, void *data
) {
531 node
= splay_search_node(tree
, data
);
534 splay_delete_node(tree
, node
);
537 /* Fast tree cleanup */
539 void splay_delete_tree(splay_tree_t
*tree
) {
540 for(splay_node_t
*node
= tree
->head
, *next
; node
; node
= next
) {
542 splay_free_node(tree
, node
);
545 splay_free_tree(tree
);
550 void splay_foreach(const splay_tree_t
*tree
, splay_action_t action
) {
551 for(splay_node_t
*node
= tree
->head
, *next
; node
; node
= next
) {
557 void splay_foreach_node(const splay_tree_t
*tree
, splay_action_t action
) {
558 for(splay_node_t
*node
= tree
->head
, *next
; node
; node
= next
) {