#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif
#include "libiberty.h"
#include "splay-tree.h"
static void splay_tree_delete_helper PARAMS((splay_tree,
splay_tree_node));
static void splay_tree_splay PARAMS((splay_tree,
splay_tree_key));
static splay_tree_node splay_tree_splay_helper
PARAMS((splay_tree,
splay_tree_key,
splay_tree_node*,
splay_tree_node*,
splay_tree_node*));
static int splay_tree_foreach_helper PARAMS((splay_tree,
splay_tree_node,
splay_tree_foreach_fn,
void*));
static void
splay_tree_delete_helper (sp, node)
splay_tree sp;
splay_tree_node node;
{
if (!node)
return;
splay_tree_delete_helper (sp, node->left);
splay_tree_delete_helper (sp, node->right);
if (sp->delete_key)
(*sp->delete_key)(node->key);
if (sp->delete_value)
(*sp->delete_value)(node->value);
free ((char*) node);
}
static splay_tree_node
splay_tree_splay_helper (sp, key, node, parent, grandparent)
splay_tree sp;
splay_tree_key key;
splay_tree_node *node;
splay_tree_node *parent;
splay_tree_node *grandparent;
{
splay_tree_node *next;
splay_tree_node n;
int comparison;
n = *node;
if (!n)
return *parent;
comparison = (*sp->comp) (key, n->key);
if (comparison == 0)
next = 0;
else if (comparison < 0)
next = &n->left;
else
next = &n->right;
if (next)
{
n = splay_tree_splay_helper (sp, key, next, node, parent);
if (*node != n)
return n;
}
if (!parent)
return n;
if (!grandparent)
{
if (n == (*parent)->left)
{
*node = n->right;
n->right = *parent;
}
else
{
*node = n->left;
n->left = *parent;
}
*parent = n;
return n;
}
if (n == (*parent)->left && *parent == (*grandparent)->left)
{
splay_tree_node p = *parent;
(*grandparent)->left = p->right;
p->right = *grandparent;
p->left = n->right;
n->right = p;
*grandparent = n;
return n;
}
else if (n == (*parent)->right && *parent == (*grandparent)->right)
{
splay_tree_node p = *parent;
(*grandparent)->right = p->left;
p->left = *grandparent;
p->right = n->left;
n->left = p;
*grandparent = n;
return n;
}
if (n == (*parent)->left)
{
(*parent)->left = n->right;
n->right = *parent;
(*grandparent)->right = n->left;
n->left = *grandparent;
*grandparent = n;
return n;
}
else
{
(*parent)->right = n->left;
n->left = *parent;
(*grandparent)->left = n->right;
n->right = *grandparent;
*grandparent = n;
return n;
}
}
static void
splay_tree_splay (sp, key)
splay_tree sp;
splay_tree_key key;
{
if (sp->root == 0)
return;
splay_tree_splay_helper (sp, key, &sp->root,
0, 0);
}
static int
splay_tree_foreach_helper (sp, node, fn, data)
splay_tree sp;
splay_tree_node node;
splay_tree_foreach_fn fn;
void* data;
{
int val;
if (!node)
return 0;
val = splay_tree_foreach_helper (sp, node->left, fn, data);
if (val)
return val;
val = (*fn)(node, data);
if (val)
return val;
return splay_tree_foreach_helper (sp, node->right, fn, data);
}
splay_tree
splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
splay_tree_compare_fn compare_fn;
splay_tree_delete_key_fn delete_key_fn;
splay_tree_delete_value_fn delete_value_fn;
{
splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree));
sp->root = 0;
sp->comp = compare_fn;
sp->delete_key = delete_key_fn;
sp->delete_value = delete_value_fn;
return sp;
}
void
splay_tree_delete (sp)
splay_tree sp;
{
splay_tree_delete_helper (sp, sp->root);
free ((char*) sp);
}
void
splay_tree_insert (sp, key, value)
splay_tree sp;
splay_tree_key key;
splay_tree_value value;
{
int comparison;
splay_tree_splay (sp, key);
if (sp->root)
comparison = (*sp->comp)(sp->root->key, key);
if (sp->root && comparison == 0)
{
if (sp->delete_value)
(*sp->delete_value)(sp->root->value);
sp->root->value = value;
}
else
{
splay_tree_node node;
node = (splay_tree_node) xmalloc (sizeof (struct splay_tree_node));
node->key = key;
node->value = value;
if (!sp->root)
node->left = node->right = 0;
else if (comparison < 0)
{
node->left = sp->root;
node->right = node->left->right;
node->left->right = 0;
}
else
{
node->right = sp->root;
node->left = node->right->left;
node->right->left = 0;
}
sp->root = node;
}
}
splay_tree_node
splay_tree_lookup (sp, key)
splay_tree sp;
splay_tree_key key;
{
splay_tree_splay (sp, key);
if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
return sp->root;
else
return 0;
}
int
splay_tree_foreach (sp, fn, data)
splay_tree sp;
splay_tree_foreach_fn fn;
void *data;
{
return splay_tree_foreach_helper (sp, sp->root, fn, data);
}
int
splay_tree_compare_ints (k1, k2)
splay_tree_key k1;
splay_tree_key k2;
{
if ((int) k1 < (int) k2)
return -1;
else if ((int) k1 > (int) k2)
return 1;
else
return 0;
}
int
splay_tree_compare_pointers (k1, k2)
splay_tree_key k1;
splay_tree_key k2;
{
if ((char*) k1 < (char*) k2)
return -1;
else if ((char*) k1 > (char*) k2)
return 1;
else
return 0;
}