bst.c

Go to the documentation of this file.

/*
 * bstree - Implements a threaded binary search tree.
 *
 * Copyright (C) 2010 Franck Bui-Huu <fbuihuu@gmail.com>
 *
 * This library 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; version 2 of the
 * License.
 *
 * 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 GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 * USA
 */
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#include "avltree.h"

/*
 * This is where the black magic is defined. If you're lucky enough to
 * work on a system that doesn't support these kind of tricks then we
 * assume UINTPTR_MAX and uintptr_t type are not defined.
 *
 * Note that the getters returns a pointer when appropriate otherwise
 * NULL;
 */
#ifdef UINTPTR_MAX

#define NODE_INIT       { 0, }

static inline void INIT_NODE(struct bstree_node *node)
{
        node->left = 0;
        node->right = 0;
}

static inline void set_thread(struct bstree_node *t, uintptr_t *p)
{
        *p = (uintptr_t)t | 1;
}

static inline struct bstree_node *get_thread(uintptr_t u)
{
        return (struct bstree_node *)((u & -(int)(u & 1)) & ~1UL);
}

static inline void set_link(struct bstree_node *n, uintptr_t *p)
{
        *p = (uintptr_t)n;
}

static inline struct bstree_node *get_link(uintptr_t u)
{
        return (struct bstree_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

#define NODE_INIT       { NULL, }

static inline void INIT_NODE(struct bstree_node *node)
{
        node->left = NULL;
        node->right = NULL;
        node->left_is_thread = 0;
        node->right_is_thread = 0;
}

static inline void set_left(struct bstree_node *l, struct bstree_node *n)
{
        n->left = l;
        n->left_is_thread = 0;
}

static inline void set_right(struct bstree_node *r, struct bstree_node *n)
{
        n->right = r;
        n->right_is_thread = 0;
}

static inline void set_prev(struct bstree_node *t, struct bstree_node *n)
{
        n->left = t;
        n->left_is_thread = 1;
}

static inline void set_next(struct bstree_node *t, struct bstree_node *n)
{
        n->right = t;
        n->right_is_thread = 1;
}

static inline struct bstree_node *get_left(const struct bstree_node *n)
{
        if (n->left_is_thread)
                return NULL;
        return n->left;
}

static inline struct bstree_node *get_right(const struct bstree_node *n)
{
        if (n->right_is_thread)
                return NULL;
        return n->right;
}

static inline struct bstree_node *get_prev(const struct bstree_node *n)
{
        if (!n->left_is_thread)
                return NULL;
        return n->left;
}

static inline struct bstree_node *get_next(const struct bstree_node *n)
{
        if (!n->right_is_thread)
                return NULL;
        return n->right;
}

#endif  /* UINTPTR_MAX */

/*
 * Iterators
 */
static inline struct bstree_node *get_first(struct bstree_node *node)
{
        struct bstree_node *left;
        while ((left = get_left(node)))
                node = left;
        return node;
}

static inline struct bstree_node *get_last(struct bstree_node *node)
{
        struct bstree_node *right;
        while ((right = get_right(node)))
                node = right;
        return node;
}

struct bstree_node *bstree_first(const struct bstree *tree)
{
        if (tree->root)
                return tree->first;
        return NULL;
}

struct bstree_node *bstree_last(const struct bstree *tree)
{
        if (tree->root)
                return tree->last;
        return NULL;
}

struct bstree_node *bstree_next(const struct bstree_node *node)
{
        struct bstree_node *right = get_right(node);
        if (right)
                return get_first(right);
        return get_next(node);
}

struct bstree_node *bstree_prev(const struct bstree_node *node)
{
        struct bstree_node *left = get_left(node);
        if (left)
                return get_last(left);
        return get_prev(node);
}

/*
 * Main ops: lookup, insert, remove.
 */
static struct bstree_node *do_lookup(const struct bstree_node *key,
                                     const struct bstree *tree,
                                     struct bstree_node **pparent,
                                     int *is_left)
{
        struct bstree_node *node = tree->root;

        *pparent = NULL;
        *is_left = 0;

        while (node) {
                int res = tree->cmp_fn(node, key);
                if (res == 0)
                        return node;
                *pparent = node;
                if ((*is_left = res > 0))
                        node = get_left(node);
                else
                        node = get_right(node);
        }
        return NULL;
}

struct bstree_node *bstree_lookup(const struct bstree_node *key,
                                  const struct bstree *tree)
{
        struct bstree_node *parent;
        int is_left;

        return do_lookup(key, tree, &parent, &is_left);
}

struct bstree_node *bstree_insert(struct bstree_node *node, struct bstree *tree)
{
        struct bstree_node *key, *parent;
        int is_left;

        key = do_lookup(node, tree, &parent, &is_left);
        if (key)
                return key;

        if (!parent) {
                INIT_NODE(node);
                tree->root = tree->first = tree->last = node;
                return NULL;
        }
        if (is_left) {
                if (parent == tree->first)
                        tree->first = node;
                set_prev(get_prev(parent), node);
                set_next(parent, node);
                set_left(node, parent);
        } else {
                if (parent == tree->last)
                        tree->last = node;
                set_prev(parent, node);
                set_next(get_next(parent), node);
                set_right(node, parent);
        }
        return NULL;
}

static void set_child(struct bstree_node *child, struct bstree_node *node, int left)
{
        if (left)
                set_left(child, node);
        else
                set_right(child, node);
}

void bstree_remove(struct bstree_node *node, struct bstree *tree)
{
        struct bstree_node *left, *right, *next;
        struct bstree_node fake_parent, *parent;
        int is_left;

        do_lookup(node, tree, &parent, &is_left);

        if (!parent) {
                INIT_NODE(&fake_parent);
                parent = &fake_parent;
                is_left = 0;
        }
        left  = get_left(node);
        right = get_right(node);

        if (!left && !right) {
                if (is_left)
                        set_prev(get_prev(node), parent);
                else
                        set_next(get_next(node), parent);
                next = parent;
                goto update_first_last;
        }
        if (!left) {
                next = get_first(right);
                set_prev(get_prev(node), next);
                set_child(right, parent, is_left);
                goto update_first_last;
        }
        if (!right) {
                next = get_last(left);
                set_next(get_next(node), next);
                set_child(left, parent, is_left);
                goto update_first_last;
        }

        next = get_first(right);
        if (next != right) {
                /* 'm' is the parent of 'next' */
                struct bstree_node *m = get_next(get_last(next));

                if (get_right(next))
                        set_left(get_right(next), m);
                else
                        set_prev(next, m);

                set_right(right, next);
        }
        set_child(next, parent, is_left);
        set_left(left, next);
        set_next(next, get_last(left));
out:
        if (parent == &fake_parent)
                tree->root = get_right(parent);
        return;

update_first_last:
        if (node == tree->first)
                tree->first = next;
        if (node == tree->last)
                tree->last = next;
        goto out;
}

void bstree_replace(struct bstree_node *old, struct bstree_node *new,
                    struct bstree *tree)
{
        struct bstree_node *parent;
        int is_left;

        do_lookup(old, tree, &parent, &is_left);
        if (parent)
                set_child(new, parent, is_left);
        else
                tree->root = new;

        if (tree->first == old)
                tree->first = new;
        if (tree->last == old)
                tree->last = new;

        *new = *old;
}

int bstree_init(struct bstree *tree, bstree_cmp_fn_t cmp, unsigned long flags)
{
        if (flags)
                return -1;
        tree->root = NULL;
        tree->cmp_fn = cmp;
        return 0;
}