2 splay_tree.c -- splay tree and linked list convenience
3 Copyright (C) 2004 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
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 $Id: splay_tree.c 1374 2004-03-21 14:21:22Z guus $
24 #include "splay_tree.h"
29 static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *result) {
30 splay_node_t left = {0}, right = {0};
31 splay_node_t *leftbottom = &left, *rightbottom = &right, *child, *grandchild;
32 splay_node_t *root = tree->root;
41 while((c = tree->compare(data, root->data))) {
42 if(c < 0 && (child = root->left)) {
43 c = tree->compare(data, child->data);
45 if(c < 0 && (grandchild = child->left)) {
46 rightbottom->left = child;
47 child->parent = rightbottom;
50 if((root->left = child->right))
51 child->right->parent = root;
57 grandchild->parent = NULL;
60 } else if (c > 0 && (grandchild = child->right)) {
61 leftbottom->right = child;
62 child->parent = leftbottom;
66 grandchild->parent = NULL;
68 rightbottom->left = root;
69 root->parent = rightbottom;
76 rightbottom->left = root;
77 root->parent = rightbottom;
86 } else if(c > 0 && (child = root->right)) {
87 c = tree->compare(data, child->data);
89 if(c > 0 && (grandchild = child->right)) {
90 leftbottom->right = child;
91 child->parent = leftbottom;
94 if((root->right = child->left))
95 child->left->parent = root;
101 grandchild->parent = NULL;
104 } else if (c < 0 && (grandchild = child->left)) {
105 rightbottom->left = child;
106 child->parent = rightbottom;
110 grandchild->parent = NULL;
112 leftbottom->right = root;
113 root->parent = leftbottom;
120 leftbottom->right = root;
121 root->parent = leftbottom;
125 child->parent = NULL;
139 leftbottom->right = root->left;
140 root->left->parent = leftbottom;
142 root->left = left.right;
143 left.right->parent = root;
148 rightbottom->left = root->right;
149 root->right->parent = rightbottom;
151 root->right = right.left;
152 right.left->parent = root;
164 static void splay_bottom_up(splay_tree_t *tree, splay_node_t *node) {
165 splay_node_t *parent, *grandparent, *greatgrandparent;
167 while((parent = node->parent)) {
168 if(!(grandparent = parent->parent)) { /* zig */
169 if(node == parent->left) {
170 if((parent->left = node->right))
171 parent->left->parent = parent;
172 node->right = parent;
174 if((parent->right = node->left))
175 parent->right->parent = parent;
179 parent->parent = node;
182 greatgrandparent = grandparent->parent;
184 if(node == parent->left && parent == grandparent->left) { /* left zig-zig */
185 if((grandparent->left = parent->right))
186 grandparent->left->parent = grandparent;
187 parent->right = grandparent;
188 grandparent->parent = parent;
190 if((parent->left = node->right))
191 parent->left->parent = parent;
192 node->right = parent;
193 parent->parent = node;
194 } else if(node == parent->right && parent == grandparent->right) { /* right zig-zig */
195 if((grandparent->right = parent->left))
196 grandparent->right->parent = grandparent;
197 parent->left = grandparent;
198 grandparent->parent = parent;
200 if((parent->right = node->left))
201 parent->right->parent = parent;
203 parent->parent = node;
204 } else if(node == parent->right && parent == grandparent->left) { /* left-right zig-zag */
205 if((parent->right = node->left))
206 parent->right->parent = parent;
208 parent->parent = node;
210 if((grandparent->left = node->right))
211 grandparent->left->parent = grandparent;
212 node->right = grandparent;
213 grandparent->parent = node;
214 } else { /* right-left zig-zag */
215 if((parent->left = node->right))
216 parent->left->parent = parent;
217 node->right = parent;
218 parent->parent = node;
220 if((grandparent->right = node->left))
221 grandparent->right->parent = grandparent;
222 node->left = grandparent;
223 grandparent->parent = node;
226 if((node->parent = greatgrandparent)) {
227 if(grandparent == greatgrandparent->left)
228 greatgrandparent->left = node;
230 greatgrandparent->right = node;
238 /* (De)constructors */
240 splay_tree_t *splay_alloc_tree(splay_compare_t compare, splay_action_t delete) {
243 tree = xmalloc_and_zero(sizeof(splay_tree_t));
244 tree->compare = compare;
245 tree->delete = delete;
250 void splay_free_tree(splay_tree_t *tree) {
254 splay_node_t *splay_alloc_node(void) {
255 return xmalloc_and_zero(sizeof(splay_node_t));
258 void splay_free_node(splay_tree_t *tree, splay_node_t *node) {
259 if(node->data && tree->delete)
260 tree->delete(node->data);
267 void *splay_search(splay_tree_t *tree, const void *data) {
270 node = splay_search_node(tree, data);
272 return node ? node->data : NULL;
275 void *splay_search_closest(splay_tree_t *tree, const void *data, int *result) {
278 node = splay_search_closest_node(tree, data, result);
280 return node ? node->data : NULL;
283 void *splay_search_closest_smaller(splay_tree_t *tree, const void *data) {
286 node = splay_search_closest_smaller_node(tree, data);
288 return node ? node->data : NULL;
291 void *splay_search_closest_greater(splay_tree_t *tree, const void *data) {
294 node = splay_search_closest_greater_node(tree, data);
296 return node ? node->data : NULL;
299 splay_node_t *splay_search_node(splay_tree_t *tree, const void *data) {
303 node = splay_search_closest_node(tree, data, &result);
305 return result ? NULL : node;
308 splay_node_t *splay_search_closest_node_nosplay(const splay_tree_t *tree, const void *data, int *result) {
321 c = tree->compare(data, node->data);
343 splay_node_t *splay_search_closest_node(splay_tree_t *tree, const void *data, int *result) {
344 return splay_top_down(tree, data, result);
347 splay_node_t *splay_search_closest_smaller_node(splay_tree_t *tree, const void *data) {
351 node = splay_search_closest_node(tree, data, &result);
359 splay_node_t *splay_search_closest_greater_node(splay_tree_t *tree, const void *data) {
363 node = splay_search_closest_node(tree, data, &result);
371 /* Insertion and deletion */
373 splay_node_t *splay_insert(splay_tree_t *tree, void *data) {
374 splay_node_t *closest, *new;
378 new = splay_alloc_node();
380 splay_insert_top(tree, new);
382 closest = splay_search_closest_node_nosplay(tree, data, &result);
387 new = splay_alloc_node();
391 splay_insert_before(tree, closest, new);
393 splay_insert_after(tree, closest, new);
399 splay_node_t *splay_insert_node(splay_tree_t *tree, splay_node_t *node) {
400 splay_node_t *closest;
404 splay_insert_top(tree, node);
406 closest = splay_search_closest_node_nosplay(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->parent = NULL;
422 tree->head = tree->tail = tree->root = node;
425 void splay_insert_before(splay_tree_t *tree, splay_node_t *before, splay_node_t *node) {
428 splay_insert_after(tree, tree->tail, node);
430 splay_insert_top(tree, node);
435 node->parent = before;
436 node->prev = before->prev;
439 splay_insert_after(tree, before->prev, node);
444 before->prev->next = node;
451 splay_bottom_up(tree, node);
454 void splay_insert_after(splay_tree_t *tree, splay_node_t *after, splay_node_t *node) {
457 splay_insert_before(tree, tree->head, node);
459 splay_insert_top(tree, node);
464 splay_insert_before(tree, after->next, node);
469 node->parent = after;
470 node->next = after->next;
473 after->next->prev = node;
480 splay_bottom_up(tree, node);
483 splay_node_t *splay_unlink(splay_tree_t *tree, void *data) {
487 node = splay_search_closest_node_nosplay(tree, data, &result);
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;
507 node->left->parent = NULL;
508 tree->root = node->left;
511 splay_bottom_up(tree, node->prev);
512 node->prev->right = node->right;
513 node->right->parent = node->prev;
515 } else if(node->right) {
516 node->right->parent = NULL;
517 tree->root = node->right;
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 splay_node_t *node, *next;
542 for(node = tree->root; node; node = next) {
544 splay_free_node(tree, node);
547 splay_free_tree(tree);
552 void splay_foreach(const splay_tree_t *tree, splay_action_t action) {
553 splay_node_t *node, *next;
555 for(node = tree->head; node; node = next) {
561 void splay_foreach_node(const splay_tree_t *tree, splay_action_t action) {
562 splay_node_t *node, *next;
564 for(node = tree->head; node; node = next) {