/*
splay_tree.c -- splay tree and linked list convenience
- Copyright (C) 2004-2006 Guus Sliepen <guus@tinc-vpn.org>
+ Copyright (C) 2004-2012 Guus Sliepen <guus@tinc-vpn.org>
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
rightbottom->left = child;
child->parent = rightbottom;
rightbottom = child;
-
+
if((root->left = child->right))
child->right->parent = root;
-
+
child->right = root;
root->parent = child;
rightbottom->left = root;
root->parent = rightbottom;
rightbottom = root;
-
+
root->left = NULL;
child->parent = NULL;
leftbottom->right = child;
child->parent = leftbottom;
leftbottom = child;
-
+
if((root->right = child->left))
child->left->parent = root;
-
+
child->left = root;
root->parent = child;
return tree->root;
}
-
+
static void splay_bottom_up(splay_tree_t *tree, splay_node_t *node) {
splay_node_t *parent, *grandparent, *greatgrandparent;
while((parent = node->parent)) {
if(!(grandparent = parent->parent)) { /* zig */
if(node == parent->left) {
- if((parent->left = node->right))
+ if((parent->left = node->right))
parent->left->parent = parent;
node->right = parent;
} else {
splay_tree_t *splay_alloc_tree(splay_compare_t compare, splay_action_t delete) {
splay_tree_t *tree;
- tree = xmalloc_and_zero(sizeof(splay_tree_t));
+ tree = xzalloc(sizeof(splay_tree_t));
tree->compare = compare;
tree->delete = delete;
}
splay_node_t *splay_alloc_node(void) {
- return xmalloc_and_zero(sizeof(splay_node_t));
+ return xzalloc(sizeof(splay_node_t));
}
void splay_free_node(splay_tree_t *tree, splay_node_t *node) {
} else if(c > 0) {
if(node->right)
node = node->right;
- else
+ else
break;
} else {
break;
new = splay_alloc_node();
new->data = data;
-
+
if(result < 0)
splay_insert_before(tree, closest, new);
else
splay_insert_after(tree, closest, new);
- }
+ }
return new;
}
splay_node_t *closest;
int result;
+ node->left = node->right = node->parent = node->next = node->prev = NULL;
+
if(!tree->root)
splay_insert_top(tree, node);
else {
closest = splay_search_closest_node(tree, node->data, &result);
-
+
if(!result)
return NULL;
void splay_insert_top(splay_tree_t *tree, splay_node_t *node) {
node->prev = node->next = node->left = node->right = node->parent = NULL;
tree->head = tree->tail = tree->root = node;
+ tree->count++;
}
void splay_insert_before(splay_tree_t *tree, splay_node_t *before, splay_node_t *node) {
node->parent = NULL;
tree->root = node;
+ tree->count++;
}
void splay_insert_after(splay_tree_t *tree, splay_node_t *after, splay_node_t *node) {
node->parent = NULL;
tree->root = node;
+ tree->count++;
}
splay_node_t *splay_unlink(splay_tree_t *tree, void *data) {
} else {
tree->root = NULL;
}
+
+ tree->count--;
}
void splay_delete_node(splay_tree_t *tree, splay_node_t *node) {
/* Fast tree cleanup */
void splay_delete_tree(splay_tree_t *tree) {
- splay_node_t *node, *next;
-
- for(node = tree->head; node; node = next) {
+ for(splay_node_t *node = tree->head, *next; node; node = next) {
next = node->next;
splay_free_node(tree, node);
}
/* Tree walking */
void splay_foreach(const splay_tree_t *tree, splay_action_t action) {
- splay_node_t *node, *next;
-
- for(node = tree->head; node; node = next) {
+ for(splay_node_t *node = tree->head, *next; node; node = next) {
next = node->next;
action(node->data);
}
}
void splay_foreach_node(const splay_tree_t *tree, splay_action_t action) {
- splay_node_t *node, *next;
-
- for(node = tree->head; node; node = next) {
+ for(splay_node_t *node = tree->head, *next; node; node = next) {
next = node->next;
action(node);
}