Logo Search packages:      
Sourcecode: jpegpixi version File versions

rbtree.c

/* This file is part of a red-black tree implementation.
   Copyright (C) 2003, 2004 Martin Dickopp

   This file is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This file 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 General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this file; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307,
   USA.



   The function `rbtree_delete' has in part been derived from the
   GNU ISO C++ Library, to which the following copyright and license
   notices apply:


   Copyright (C) 2001, 2002 Free Software Foundation, Inc.

   This file is part of the GNU ISO C++ Library.  This library is free
   software; you can redistribute it and/or modify it under the
   terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2, 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
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License along
   with this library; see the file COPYING.  If not, write to the Free
   Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
   USA.

   As a special exception, you may use this file as part of a free software
   library without restriction.  Specifically, if other files instantiate
   templates or use macros or inline functions from this file, or you compile
   this file and link it with other files to produce an executable, this
   file does not by itself cause the resulting executable to be covered by
   the GNU General Public License.  This exception does not however
   invalidate any other reasons why the executable file might be covered by
   the GNU General Public License.


   Copyright (c) 1996,1997
   Silicon Graphics Computer Systems, Inc.

   Permission to use, copy, modify, distribute and sell this software
   and its documentation for any purpose is hereby granted without fee,
   provided that the above copyright notice appear in all copies and
   that both that copyright notice and this permission notice appear
   in supporting documentation.  Silicon Graphics makes no
   representations about the suitability of this software for any
   purpose.  It is provided "as is" without express or implied warranty.


   Copyright (c) 1994
   Hewlett-Packard Company

   Permission to use, copy, modify, distribute and sell this software
   and its documentation for any purpose is hereby granted without fee,
   provided that the above copyright notice appear in all copies and
   that both that copyright notice and this permission notice appear
   in supporting documentation.  Hewlett-Packard Company makes no
   representations about the suitability of this software for any
   purpose.  It is provided "as is" without express or implied warranty.  */

#ifdef HAVE_CONFIG_H
# include <config.h>
#endif
#include "util.h"

#if !STDC_HEADERS && HAVE_MALLOC_H
# include <malloc.h>
#endif
#if !HAVE_DECL_MALLOC
extern void *malloc ();
#endif

#include "rbtree.h"


/* Alignment of the data associated with a tree node.  */
#define ALIGNMENT 16

/* Size of `struct rbtree_node' rounded up to an integer multiple of `ALIGNMENT'.  */
#define SIZEOF_RBTREE_NODE (sizeof (struct rbtree_node) + (ALIGNMENT - 1) \
                            - (sizeof (struct rbtree_node) - 1) % ALIGNMENT)

/* Get data pointer from `struct rbtree_node' pointer.  */
#define NODE2DATA(node) ((void *)((char *)(node) + SIZEOF_RBTREE_NODE))

/* Get `struct rbtree_node' pointer from data pointer.  */
#define DATA2NODE(data) ((struct rbtree_node *)((char *)(data) - SIZEOF_RBTREE_NODE))



/* Color.  */
enum rbtree_color {BLACK = 0, RED = 1};

/* Tree node.  */
struct rbtree_node {
    struct rbtree_node *l;      /* Left child node.  */
    struct rbtree_node *r;      /* Right child node.  */
    struct rbtree_node *p;      /* Parent node.  */
    enum rbtree_color color;    /* Color.  */
};



static void rbtree_rot_l (struct rbtree *tree, struct rbtree_node *node) gcc_attr_nonnull (());
static void rbtree_rot_r (struct rbtree *tree, struct rbtree_node *node) gcc_attr_nonnull (());



/* Helper function: recursively destroy `node' and all nodes below it.  */
void
rbtree_destroy1 (struct rbtree_node *node)
{
    while (1)
    {
        struct rbtree_node *const tmp = node->r;

        if (node->l != 0)
            rbtree_destroy1 (node->l);

        free (node);

        if (tmp != 0)
            node = tmp;
        else
            break;
    }
}



/* Insert a new node into a tree.  The data is copied; the location of the copied data is returned,
   and if `exists_ptr' is not a null pointer, the integer at the location pointed to is set to zero.
   If the node already exists, the location of the existing node data is returned, and if `exists_ptr'
   is not a null pointer, the integer at the location pointed to is set to one.  If memory allocation
   fails, a null pointer is returned.  */
void *
rbtree_insert (struct rbtree *const tree, const void *const data, size_t data_len,
               int (*const compare) (const void *a, const void *b), int *const exists_ptr)
{
    struct rbtree_node *node;
    void *data_copy;


    {
        struct rbtree_node *node_p = 0, *tmp = tree->root;

        while (tmp != 0)
        {
            const int cmp = compare (data, NODE2DATA (tmp));

            node_p = tmp;

            if (cmp == 0)
            {
                if (exists_ptr != 0)
                    *exists_ptr = 1;
                return NODE2DATA (tmp);
            }
            else if (cmp < 0)
                tmp = tmp->l;
            else
                tmp = tmp->r;
        }

        node = malloc (SIZEOF_RBTREE_NODE + data_len);
        if (node == 0)
            return 0;

        data_copy = NODE2DATA (node);
        node->l = 0;
        node->r = 0;
        node->p = node_p;
        node->color = RED;
        memcpy (data_copy, data, data_len);
    }

    if (node->p == 0)
        tree->root = node;
    else if (compare (data, NODE2DATA (node->p)) < 0)
        node->p->l = node;
    else
        node->p->r = node;

    while (node != tree->root && node->p->color != BLACK)
        if (node->p == node->p->p->l)
        {
            if (node->p->p->r != 0 && node->p->p->r->color != BLACK)
            {
                node->p->p->r->color = BLACK;
                node->p->p->color = RED;
                node->p->color = BLACK;
                node = node->p->p;
            }
            else
            {
                if (node == node->p->r)
                {
                    node = node->p;
                    rbtree_rot_l (tree, node);
                }

                node->p->p->color = RED;
                node->p->color = BLACK;
                rbtree_rot_r (tree, node->p->p);
            }
        }
        else
        {
            if (node->p->p->l != 0 && node->p->p->l->color != BLACK)
            {
                node->p->p->l->color = BLACK;
                node->p->p->color = RED;
                node->p->color = BLACK;
                node = node->p->p;
            }
            else
            {
                if (node == node->p->l)
                {
                    node = node->p;
                    rbtree_rot_r (tree, node);
                }

                node->p->p->color = RED;
                node->p->color = BLACK;
                rbtree_rot_l (tree, node->p->p);
            }
        }

    tree->root->color = BLACK;
    if (exists_ptr != 0)
        *exists_ptr = 0;
    return data_copy;
}



/* Delete a node.  The `data' parameter must point to the data associated with an existing node.  */
void
rbtree_delete (struct rbtree *const tree, void *const data)
{
    struct rbtree_node *const node = DATA2NODE (data);
    struct rbtree_node *del_node, *tmp, *tmp_p;


    del_node = node;

    if (del_node->r == 0)
        tmp = del_node->l;
    else
    {
        if (del_node->l != 0)
        {
            del_node = del_node->r;
            while (del_node->l != 0)
                del_node = del_node->l;
        }

        tmp = del_node->r;
    }

    if (del_node != node)
    {
        node->l->p = del_node;
        del_node->l = node->l;

        if (del_node != node->r)
        {
            tmp_p = del_node->p;
            if (tmp != 0)
                tmp->p = del_node->p;
            del_node->p->l = tmp;
            del_node->r = node->r;
            node->r->p = del_node;
        }
        else
            tmp_p = del_node;

        if (tree->root == node)
            tree->root = del_node;
        else if (node->p->l == node)
            node->p->l = del_node;
        else
            node->p->r = del_node;

        del_node->p = node->p;

        {
            const enum rbtree_color tmp_color = del_node->color;
            del_node->color = node->color;
            node->color = tmp_color;
        }

        del_node = node;
    }
    else
    {
        tmp_p = node->p;

        if (tmp != 0)
            tmp->p = node->p;

        if (tree->root == node)
            tree->root = tmp;
        else if (node->p->l == node)
            node->p->l = tmp;
        else
            node->p->r = tmp;
    }

    if (del_node->color == BLACK)
    {
        while (tmp != tree->root && (tmp == 0 || tmp->color == BLACK))
            if (tmp == tmp_p->l)
            {
                struct rbtree_node *tmp_p_r = tmp_p->r;

                if (tmp_p_r->color != BLACK)
                {
                    tmp_p_r->color = BLACK;
                    tmp_p->color = RED;
                    rbtree_rot_l (tree, tmp_p);
                    tmp_p_r = tmp_p->r;
                }

                if ((tmp_p_r->l == 0 || tmp_p_r->l->color == BLACK)
                    && (tmp_p_r->r == 0 || tmp_p_r->r->color == BLACK))
                {
                    tmp_p_r->color = RED;
                    tmp = tmp_p;
                    tmp_p = tmp->p;
                }
                else
                {
                    if (tmp_p_r->r == 0 || tmp_p_r->r->color == BLACK)
                    {
                        tmp_p_r->l->color = BLACK;
                        tmp_p_r->color = RED;
                        rbtree_rot_r (tree, tmp_p_r);
                        tmp_p_r = tmp_p->r;
                    }

                    tmp_p_r->color = tmp_p->color;
                    tmp_p->color = BLACK;
                    if (tmp_p_r->r != 0)
                        tmp_p_r->r->color = BLACK;
                    rbtree_rot_l (tree, tmp_p);
                    break;
                }
            }
            else
            {
                struct rbtree_node *tmp_p_l = tmp_p->l;

                if (tmp_p_l->color != BLACK)
                {
                    tmp_p_l->color = BLACK;
                    tmp_p->color = RED;
                    rbtree_rot_r (tree, tmp_p);
                    tmp_p_l = tmp_p->l;
                }

                if ((tmp_p_l->l == 0 || tmp_p_l->l->color == BLACK)
                    && (tmp_p_l->r == 0 || tmp_p_l->r->color == BLACK))
                {
                    tmp_p_l->color = RED;
                    tmp = tmp_p;
                    tmp_p = tmp->p;
                }
                else
                {
                    if (tmp_p_l->l == 0 || tmp_p_l->l->color == BLACK)
                    {
                        tmp_p_l->r->color = BLACK;
                        tmp_p_l->color = RED;
                        rbtree_rot_l (tree, tmp_p_l);
                        tmp_p_l = tmp_p->l;
                    }

                    tmp_p_l->color = tmp_p->color;
                    tmp_p->color = BLACK;
                    if (tmp_p_l->l != 0)
                        tmp_p_l->l->color = BLACK;
                    rbtree_rot_r (tree, tmp_p);
                    break;
                }
            }

        if (tmp != 0)
            tmp->color = BLACK;
    }

    free (del_node);
}



/* Find a node.  Return the data associated with the node, or a null pointer if the node does not exist.  */
void *
rbtree_find (const struct rbtree *const tree, const void *const data,
             int (*const compare) (const void *a, const void *b))
{
    const struct rbtree_node *node = tree->root;

    while (node != 0)
    {
        const int cmp = compare (data, NODE2DATA (node));

        if (cmp == 0)
            return NODE2DATA (node);
        else if (cmp < 0)
            node = node->l;
        else
            node = node->r;
    }

    return 0;
}



/* Return the data associated with the first node, or a null pointer if the tree is empty.  */
void *
rbtree_first (const struct rbtree *const tree)
{
    const struct rbtree_node *node = tree->root;

    if (node == 0)
        return 0;

    while (node->l != 0)
        node = node->l;

    return NODE2DATA (node);
}



/* Return the data associated with the next node, or a null pointer if no more nodes exist.  */
void *
rbtree_next (const void *const data)
{
    const struct rbtree_node *node = DATA2NODE (data), *tmp;

    if (node->r != 0)
    {
        node = node->r;
        while (node->l != 0)
            node = node->l;

        return NODE2DATA (node);
    }

    tmp = node->p;
    while (tmp != 0 && tmp->r == node)
    {
        node = tmp;
        tmp = tmp->p;
    }

    return tmp != 0 ? NODE2DATA (tmp) : 0;
}



/* Rotate a node to the left.  */
static void
rbtree_rot_l (struct rbtree *const tree, struct rbtree_node *const node)
{
    struct rbtree_node *const tmp = node->r;

    node->r = tmp->l;
    if (tmp->l != 0)
        tmp->l->p = node;
    tmp->p = node->p;
    if (tmp->p == 0)
        tree->root = tmp;
    else if (node == node->p->l)
        node->p->l = tmp;
    else
        node->p->r = tmp;
    tmp->l = node;
    node->p = tmp;
}



/* Rotate a node to the right.  */
static void
rbtree_rot_r (struct rbtree *const tree, struct rbtree_node *const node)
{
    struct rbtree_node *const tmp = node->l;

    node->l = tmp->r;
    if (tmp->r != 0)
        tmp->r->p = node;
    tmp->p = node->p;
    if (tmp->p == 0)
        tree->root = tmp;
    else if (node == node->p->r)
        node->p->r = tmp;
    else
        node->p->l = tmp;
    tmp->r = node;
    node->p = tmp;
}

Generated by  Doxygen 1.6.0   Back to index