blob: 367a23a3b99911664dab22a2c1d6d82c0af9f665 [file] [log] [blame]
/*
* splaytree - Implements a top-down threaded splay tree.
*
* Copyright (C) 2010-2014 Franck Bui-Huu <fbuihuu@gmail.com>
*
* This file is part of libtree which is free software; you can
* redistribute it and/or modify it under the terms of the GNU Lesser
* General Public License as published by the Free Software
* Foundation; either version 2.1 of the License, or (at your option)
* any later version.
*
* This library is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*
* See the LICENSE file for license rights and limitations.
*/
#include <assert.h>
#include "avltree.h"
#ifdef UINTPTR_MAX
#define NODE_INIT { 0, }
static inline void INIT_NODE(struct splaytree_node *node)
{
node->left = 0;
node->right = 0;
}
static inline void set_thread(struct splaytree_node *t, uintptr_t * p)
{
*p = (uintptr_t) t | 1;
}
static inline struct splaytree_node *get_thread(uintptr_t u)
{
return (struct splaytree_node *)((u & -(int)(u & 1)) & ~1UL);
}
static inline void set_link(struct splaytree_node *n, uintptr_t * p)
{
*p = (uintptr_t) n;
}
static inline struct splaytree_node *get_link(uintptr_t u)
{
return (struct splaytree_node *)(u & ((int)(u & 1) - 1));
}
#define set_left(l,n) set_link(l, &(n)->left)
#define set_right(r,n) set_link(r, &(n)->right)
#define set_prev(p,n) set_thread(p, &(n)->left)
#define set_next(s,n) set_thread(s, &(n)->right)
#define get_left(n) get_link((n)->left)
#define get_right(n) get_link((n)->right)
#define get_prev(n) get_thread((n)->left)
#define get_next(n) get_thread((n)->right)
#else /* !UINTPTR_MAX */
#define NODE_INIT { NULL, }
static inline void INIT_NODE(struct splaytree_node *node)
{
node->left = NULL;
node->right = NULL;
node->left_is_thread = 0;
node->right_is_thread = 0;
}
static inline void set_left(struct splaytree_node *l, struct splaytree_node *n)
{
n->left = l;
n->left_is_thread = 0;
}
static inline void set_right(struct splaytree_node *r, struct splaytree_node *n)
{
n->right = r;
n->right_is_thread = 0;
}
static inline void set_prev(struct splaytree_node *t, struct splaytree_node *n)
{
n->left = t;
n->left_is_thread = 1;
}
static inline void set_next(struct splaytree_node *t, struct splaytree_node *n)
{
n->right = t;
n->right_is_thread = 1;
}
static inline struct splaytree_node *get_left(const struct splaytree_node *n)
{
if (!n->left_is_thread)
return n->left;
return NULL;
}
static inline struct splaytree_node *get_right(const struct splaytree_node *n)
{
if (!n->right_is_thread)
return n->right;
return NULL;
}
static inline struct splaytree_node *get_prev(const struct splaytree_node *n)
{
if (n->left_is_thread)
return n->left;
return NULL;
}
static inline struct splaytree_node *get_next(const struct splaytree_node *n)
{
if (n->right_is_thread)
return n->right;
return NULL;
}
#endif /* UINTPTR_MAX */
/*
* Iterators
*/
static inline struct splaytree_node *get_first(struct splaytree_node *node)
{
struct splaytree_node *left;
while ((left = get_left(node)))
node = left;
return node;
}
static inline struct splaytree_node *get_last(struct splaytree_node *node)
{
struct splaytree_node *right;
while ((right = get_right(node)))
node = right;
return node;
}
struct splaytree_node *splaytree_first(const struct splaytree *tree)
{
return tree->first;
}
struct splaytree_node *splaytree_last(const struct splaytree *tree)
{
return tree->last;
}
struct splaytree_node *splaytree_next(const struct splaytree_node *node)
{
struct splaytree_node *right = get_right(node);
if (right)
return get_first(right);
return get_next(node);
}
struct splaytree_node *splaytree_prev(const struct splaytree_node *node)
{
struct splaytree_node *left = get_left(node);
if (left)
return get_last(left);
return get_prev(node);
}
static inline void rotate_right(struct splaytree_node *node)
{
struct splaytree_node *left = get_left(node); /* can't be NULL */
struct splaytree_node *r = get_right(left);
if (r)
set_left(r, node);
else
set_prev(left, node);
set_right(node, left);
}
static inline void rotate_left(struct splaytree_node *node)
{
struct splaytree_node *right = get_right(node); /* can't be NULL */
struct splaytree_node *l = get_left(right);
if (l)
set_right(l, node);
else
set_next(right, node);
set_left(node, right);
}
static int do_splay(const struct splaytree_node *key, struct splaytree *tree)
{
struct splaytree_node subroots = NODE_INIT;
struct splaytree_node *subleft = &subroots, *subright = &subroots;
struct splaytree_node *root = tree->root;
splaytree_cmp_fn_t cmp = tree->cmp_fn;
int rv;
for (;;) {
rv = cmp(key, root);
if (rv == 0)
break;
if (rv < 0) {
struct splaytree_node *left;
left = get_left(root);
if (!left)
break;
if ((rv = cmp(key, left)) < 0) {
rotate_right(root);
root = left;
left = get_left(root);
if (!left)
break;
}
/* link left */
set_left(root, subright);
subright = root;
root = left;
} else {
struct splaytree_node *right;
right = get_right(root);
if (!right)
break;
if ((rv = cmp(key, right)) > 0) {
rotate_left(root);
root = right;
right = get_right(root);
if (!right)
break;
}
/* link right */
set_right(root, subleft);
subleft = root;
root = right;
}
}
/* assemble */
if (get_left(root))
set_right(get_left(root), subleft);
else
set_next(root, subleft);
if (get_right(root))
set_left(get_right(root), subright);
else
set_prev(root, subright);
set_left(get_right(&subroots), root);
set_right(get_left(&subroots), root);
tree->root = root;
return rv;
}
struct splaytree_node *splaytree_lookup(const struct splaytree_node *key,
struct splaytree *tree)
{
if (!tree->root)
return NULL;
if (do_splay(key, tree) != 0)
return NULL;
return tree->root;
}
struct splaytree_node *splaytree_insert(struct splaytree_node *node,
struct splaytree *tree)
{
struct splaytree_node *root = tree->root;
int res;
if (!root) {
INIT_NODE(node);
tree->root = node;
tree->first = node;
tree->last = node;
return NULL;
}
res = do_splay(node, tree);
if (res == 0)
return tree->root;
root = tree->root;
if (res < 0) {
struct splaytree_node *left = get_left(root);
set_left(left, node);
set_right(root, node);
if (left)
set_next(node, get_last(left));
else
tree->first = node;
set_prev(node, root);
} else {
struct splaytree_node *right = get_right(root);
set_right(right, node);
set_left(root, node);
if (right)
set_prev(node, get_first(right));
else
tree->last = node;
set_next(node, root);
}
tree->root = node;
return NULL;
}
void splaytree_remove(struct splaytree_node *node, struct splaytree *tree)
{
struct splaytree_node *right, *left, *prev;
do_splay(node, tree);
assert(tree->root == node); /* 'node' must be present */
right = get_right(node);
left = get_left(node);
if (!left) {
tree->root = right;
tree->first = splaytree_next(node);
prev = NULL;
} else {
tree->root = left;
do_splay(node, tree);
set_right(right, tree->root);
prev = tree->root;
}
if (right)
set_prev(prev, get_first(right));
else
tree->last = prev;
}
void splaytree_replace(struct splaytree_node *old, struct splaytree_node *new,
struct splaytree *tree)
{
do_splay(old, tree);
assert(tree->root == old);
tree->root = new;
if (tree->first == old)
tree->first = new;
if (tree->last == old)
tree->last = new;
*new = *old;
}
int splaytree_init(struct splaytree *tree, splaytree_cmp_fn_t cmp,
unsigned long flags)
{
if (flags)
return -1;
tree->root = NULL;
tree->first = NULL;
tree->last = NULL;
tree->cmp_fn = cmp;
return 0;
}