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;
32 splay_node_t *node = tree->root;
35 while((c = tree->compare(data, node->data))) {
40 c = tree->compare(data, child->data);
43 rightbottom->left = child;
44 child->parent = rightbottom;
47 node->left = child->right;
56 leftbottom->right = child;
57 child->parent = leftbottom;
60 rightbottom->left = node;
61 node->parent = rightbottom;
68 rightbottom->left = node;
69 node->parent = rightbottom;
84 c = tree->compare(data, child->data);
87 leftbottom->right = child;
88 child->parent = leftbottom;
91 node->right = child->left;
100 rightbottom->left = child;
101 child->parent = rightbottom;
104 leftbottom->right = node;
105 node->parent = leftbottom;
112 leftbottom->right = node;
113 node->parent = leftbottom;
117 child->parent = NULL;
133 leftbottom->right = node->left;
134 node->left->parent = leftbottom;
136 node->left = left.right;
137 left.right->parent = node;
142 rightbottom->left = node->right;
143 node->right->parent = rightbottom;
145 node->right = right.left;
146 right.left->parent = node;
156 static void splay_bottom_up(splay_tree_t *tree, splay_node_t *node) {
157 splay_node_t *parent, *grandparent;
159 while(node->parent) {
160 parent = node->parent;
161 grandparent = node->parent->parent;
163 if(!grandparent) { /* zig */
164 if(node == parent->left) {
165 parent->left = node->right;
166 node->right = parent;
168 parent->right = node->left;
172 parent->parent = node;
175 if(node == grandparent->left->left) { /* left zig-zig */
176 grandparent->left = parent->right;
177 parent->right = grandparent;
178 grandparent->parent = parent;
180 parent->left = node->right;
181 node->right = parent;
182 parent->parent = node;
184 } else if(node == grandparent->right->right) { /* right zig-zig */
185 grandparent->right = parent->left;
186 parent->left = grandparent;
187 grandparent->parent = parent;
189 parent->right = node->left;
191 parent->parent = node;
193 } else if(node == grandparent->left->right) { /* left-right zig-zag */
194 parent->right = node->left;
196 parent->parent = node;
198 grandparent->left = node->right;
199 node->right = grandparent;
200 grandparent->parent = node;
202 } else { /* right-left zig-zag */
203 parent->left = node->right;
204 node->right = parent;
205 parent->parent = node;
207 grandparent->right = node->left;
208 node->left = grandparent;
209 grandparent->parent = node;
212 node->parent = grandparent->parent;
215 if(grandparent == node->parent->left)
216 node->parent->left = node;
218 node->parent->right = node;
226 /* (De)constructors */
228 splay_tree_t *splay_alloc_tree(splay_compare_t compare, splay_action_t delete) {
231 tree = xmalloc_and_zero(sizeof(splay_tree_t));
232 tree->compare = compare;
233 tree->delete = delete;
238 void splay_free_tree(splay_tree_t *tree) {
242 splay_node_t *splay_alloc_node(void) {
243 return xmalloc_and_zero(sizeof(splay_node_t));
246 void splay_free_node(splay_tree_t *tree, splay_node_t *node) {
247 if(node->data && tree->delete)
248 tree->delete(node->data);
255 void *splay_search(splay_tree_t *tree, const void *data) {
258 node = splay_search_node(tree, data);
260 return node ? node->data : NULL;
263 void *splay_search_closest(splay_tree_t *tree, const void *data, int *result) {
266 node = splay_search_closest_node(tree, data, result);
268 return node ? node->data : NULL;
271 void *splay_search_closest_smaller(splay_tree_t *tree, const void *data) {
274 node = splay_search_closest_smaller_node(tree, data);
276 return node ? node->data : NULL;
279 void *splay_search_closest_greater(splay_tree_t *tree, const void *data) {
282 node = splay_search_closest_greater_node(tree, data);
284 return node ? node->data : NULL;
287 splay_node_t *splay_search_node(splay_tree_t *tree, const void *data) {
291 node = splay_search_closest_node(tree, data, &result);
293 return result ? NULL : node;
296 splay_node_t *splay_search_closest_node_nosplay(const splay_tree_t *tree, const void *data, int *result) {
309 c = tree->compare(data, node->data);
337 splay_node_t *splay_search_closest_node(splay_tree_t *tree, const void *data, int *result) {
338 return splay_top_down(tree, data, result);
341 splay_node_t *splay_search_closest_smaller_node(splay_tree_t *tree, const void *data) {
345 node = splay_search_closest_node(tree, data, &result);
353 splay_node_t *splay_search_closest_greater_node(splay_tree_t *tree, const void *data) {
357 node = splay_search_closest_node(tree, data, &result);
365 /* Insertion and deletion */
367 splay_node_t *splay_insert(splay_tree_t *tree, void *data) {
368 splay_node_t *closest, *new;
372 new = splay_alloc_node();
374 splay_insert_top(tree, new);
376 closest = splay_search_closest_node_nosplay(tree, data, &result);
381 new = splay_alloc_node();
385 splay_insert_before(tree, closest, new);
387 splay_insert_after(tree, closest, new);
393 splay_node_t *splay_insert_node(splay_tree_t *tree, splay_node_t *node) {
394 splay_node_t *closest;
398 splay_insert_top(tree, node);
400 closest = splay_search_closest_node_nosplay(tree, node->data, &result);
406 splay_insert_before(tree, closest, node);
408 splay_insert_after(tree, closest, node);
414 void splay_insert_top(splay_tree_t *tree, splay_node_t *node) {
415 node->prev = node->next = node->parent = NULL;
416 tree->head = tree->tail = tree->root = node;
419 void splay_insert_before(splay_tree_t *tree, splay_node_t *before, splay_node_t *node) {
422 splay_insert_after(tree, tree->tail, node);
424 splay_insert_top(tree, node);
429 node->parent = before;
430 node->prev = before->prev;
433 splay_insert_after(tree, before->prev, node);
438 before->prev->next = node;
445 splay_bottom_up(tree, node);
448 void splay_insert_after(splay_tree_t *tree, splay_node_t *after, splay_node_t *node) {
451 splay_insert_before(tree, tree->head, node);
453 splay_insert_top(tree, node);
458 splay_insert_before(tree, after->next, node);
463 node->parent = after;
464 node->next = after->next;
467 after->next->prev = node;
474 splay_bottom_up(tree, node);
477 splay_node_t *splay_unlink(splay_tree_t *tree, void *data) {
481 node = splay_search_closest_node_nosplay(tree, data, &result);
484 splay_unlink_node(tree, node);
489 void splay_unlink_node(splay_tree_t *tree, splay_node_t *node) {
491 node->prev->next = node->next;
493 tree->head = node->next;
496 node->next->prev = node->prev;
498 tree->tail = node->prev;
501 node->left->parent = NULL;
502 tree->root = node->left;
505 splay_bottom_up(tree, node->prev);
506 node->prev->right = node->right;
507 node->right->parent = node->prev;
510 node->right->parent = NULL;
511 tree->root = node->right;
515 void splay_delete_node(splay_tree_t *tree, splay_node_t *node) {
516 splay_unlink_node(tree, node);
517 splay_free_node(tree, node);
520 void splay_delete(splay_tree_t *tree, void *data) {
523 node = splay_search_node(tree, data);
526 splay_delete_node(tree, node);
529 /* Fast tree cleanup */
531 void splay_delete_tree(splay_tree_t *tree) {
532 splay_node_t *node, *next;
534 for(node = tree->root; node; node = next) {
536 splay_free_node(tree, node);
539 splay_free_tree(tree);
544 void splay_foreach(const splay_tree_t *tree, splay_action_t action) {
545 splay_node_t *node, *next;
547 for(node = tree->head; node; node = next) {
553 void splay_foreach_node(const splay_tree_t *tree, splay_action_t action) {
554 splay_node_t *node, *next;
556 for(node = tree->head; node; node = next) {