/*
splay_tree.c -- splay tree and linked list convenience
- Copyright (C) 2004-2006 Guus Sliepen <guus@tinc-vpn.org>
+ Copyright (C) 2014-2017 Guus Sliepen <guus@meshlink.io>
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
/* Splay operation */
static splay_node_t *splay_top_down(splay_tree_t *tree, const void *data, int *result) {
- splay_node_t left = {NULL}, right = {NULL};
+ splay_node_t left = {}, right = {};
splay_node_t *leftbottom = &left, *rightbottom = &right, *child, *grandchild;
splay_node_t *root = tree->root;
int c;
grandchild->parent = NULL;
root = grandchild;
- } else if (c > 0 && (grandchild = child->right)) {
+ } else if(c > 0 && (grandchild = child->right)) {
leftbottom->right = child;
child->parent = leftbottom;
leftbottom = child;
grandchild->parent = NULL;
root = grandchild;
- } else if (c < 0 && (grandchild = child->left)) {
+ } else if(c < 0 && (grandchild = child->left)) {
rightbottom->left = child;
child->parent = rightbottom;
rightbottom = child;
root = child;
break;
}
- } else {
+ } else
break;
- }
}
/* Merge trees */
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) {
node = node->right;
else
break;
- } else {
+ } else
break;
- }
}
if(result)
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 {
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 if(node->next) {
tree->root = node->right;
node->right->parent = NULL;
- } else {
+ } else
tree->root = NULL;
- }
+
+ tree->count--;
}
void splay_delete_node(splay_tree_t *tree, splay_node_t *node) {