yc_bbstree.c

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

/*
 * The young Library
 * Copyright (c) 2005 by Yang Huan(杨桓)

 * Permission to use, copy, modify, distribute and sell this software 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.
 * The author make no representations about the suitability of this software
 * for any purpose. It is provided "as is" without express or implied warranty.
 */

/******************************************************************************/
/******************************************************************************/
#include "yc_memalgo.h"
#include "yc_bbstree.h"

#ifdef __cplusplus
    namespace youngc {  extern "C" {
#endif
/******************************************************************************/
/******************************************************************************/

#define ROOT( TREE )        ( (TREE)->m_header.parent )
#define LEFTMOST( TREE )    ( (TREE)->m_header.left )
#define RIGHTMOST( TREE )   ( (TREE)->m_header.right )

#define NODE_DATA( NODE )  ( ((ylib_byte_t*)(NODE)) + sizeof(bbstree_node) )

#define DATA_KEY( TREE, DATA ) \
         ( (TREE)->m_get_key ? (TREE)->m_get_key(DATA) : (DATA) )

#define NODE_KEY( TREE, NODE )  ( (TREE)->m_get_key( NODE_DATA(NODE) ) )

#define GET_NODE_KEY( TREE, NODE )                               \
        ( (TREE)->m_get_key ? (TREE)->m_get_key(NODE_DATA(NODE)) \
                            : NODE_DATA(NODE) )

#define COPY_VALUE( PDST, PSRC, ELMTSIZE, COPYFUN )      \
        if( COPYFUN )                                    \
            (COPYFUN)( (PDST), (PSRC) );                 \
        else if( sizeof(int) == (ELMTSIZE) )             \
            *( (int*)(PDST) ) = *( (int*)(PSRC) );       \
        else if( sizeof(double) == (ELMTSIZE) )          \
            *( (double*)(PDST) ) = *( (double*)(PSRC) ); \
        else if( sizeof(char) == (ELMTSIZE) )            \
            *( (char*)(PDST) ) = *( (char*)(PSRC) );     \
        else if( sizeof(short) == (ELMTSIZE) )           \
            *( (short*)(PDST) ) = *( (short*)(PSRC) );   \
        else                                             \
            ylib_memcopy( (PDST), (PSRC), ELMTSIZE )

/******************************************************************************/
/* iterator */
/******************************************************************************/

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_INLINE_FUNCTION__
    void* bbstree_itr_deref( bbstree_node* itr )
    {
        return NODE_DATA( itr );
    }
#endif

/******************************************************************************/

void bbstree_itr_inc( bbstree_node** pitr )
{
    /* is header */
    if( RED == (*pitr)->color && (*pitr)->parent->parent == *pitr )
        *pitr = (*pitr)->left;
    else
    {
        bbstree_node* pos = *pitr;

        if( pos->right )
        {
            /* pos 有右子树，则返回右子树的最左节点 */
            pos = pos->right;
            while( pos->left )
                pos = pos->left;
        }
        else
        {
            /* pos 没有右子树，则上溯至父节点，此时有两种情况：
             * (1) 如果 pos 为父节点的左子节点，则后继节点就是父节点；
             * (2) 如果 pos 为父节点的右子节点，则递归上溯，直至满足(1)为止 */
            bbstree_node* parent = pos->parent;
            while( pos == parent->right )
            {
                pos = parent;
                parent = parent->parent;
            }
            if( pos->right != parent )
                pos = parent;
        }

        *pitr = pos;
    }
}

/******************************************************************************/

void bbstree_itr_dec( bbstree_node** pitr )
{
    /* is header */
    if( RED == (*pitr)->color && (*pitr)->parent->parent == *pitr )
        *pitr = (*pitr)->right;
    else
    {
        bbstree_node* pos = *pitr;

        if( pos->left )
        {
            /* pos 有左子树，则返回左子树的最右节点 */
            pos = pos->left;
            while( pos->right )
                pos = pos->right;
        }
        else
        {
            /* pos 没有左子树，则上溯至父节点，此时有两种情况：
             * (1) 如果 pos 为父节点的右子节点，则前驱节点就是父节点；
             * (2) 如果 pos 为父节点的左子节点，则递归上溯，直至满足(1)为止 */
            bbstree_node* parent = pos->parent;
            while( pos == parent->left )
    	    {
                pos = parent;
                parent = parent->parent;
            }
            pos = parent;
        }

        *pitr = pos;
    }
}

/******************************************************************************/
/* balanced binary search tree */
/******************************************************************************/

static bbstree_node* bbstree_min_element( bbstree_node* node )
{
    if( node )
    {
        while( node->left )
            node = node->left;
    }
    return node;
}

/******************************************************************************/

static bbstree_node* bbstree_max_element( bbstree_node* node )
{
    if( node )
    {
        while( node->right )
            node = node->right;
    }
    return node;
}

/******************************************************************************/

/* 将 pos 移动到它的左子节点位置上，将 pos 的右子节点移动到 pos 的位置上 */
static bbstree_node* bbstree_rotate_left( bbstree_node* pos,
                                          bbstree_node* root )
{
    bbstree_node* rchild = pos->right;

    /* 由于右子节点成为根节点，所以必须将原右子节点的左子树变换成 pos 的右子树 */
    pos->right = rchild->left;
    if( rchild->left )
        rchild->left->parent = pos;
    rchild->parent = pos->parent;

    /* 当 pos 为整棵树的根节点时 */
    if( pos == root )
        root = rchild;
    else if( pos == pos->parent->left )
        pos->parent->left = rchild;   /* leftmost */
    else
        pos->parent->right = rchild;  /* rightmost */

    rchild->left = pos;
    pos->parent = rchild;

    return root;
}

/******************************************************************************/

/* 将 pos 移动到它的右子节点位置上，将 pos 的左子节点移动到 pos 的位置上 */
static bbstree_node* bbstree_rotate_right( bbstree_node* pos,
                                           bbstree_node* root )
{
    bbstree_node* lchild = pos->left;

    /* 由于左子节点成为根节点，所以必须将原左子节点的右子树变换成 pos 的左子树 */
    pos->left = lchild->right;

    if( lchild->right )
        lchild->right->parent = pos;
    lchild->parent = pos->parent;

    /* 当 pos 为整棵树的根节点时 */
    if( pos == root )
        root = lchild;
    else if( pos == pos->parent->right )
        pos->parent->right = lchild;  /* leftmost */
    else
        pos->parent->left = lchild;   /* rightmost */

    lchild->right = pos;
    pos->parent = lchild;

    return root;
}

/******************************************************************************/

static bbstree_node* bbstree_weed_node( bbstree_node*  erase_node,
                                        bbstree_node** successor,
                                        bbstree_node** succ_parent,
                                        bbstree_node** root,
                                        bbstree_node** leftmost,
                                        bbstree_node** rightmost )
{
    bbstree_node* pos = erase_node;  /* pos 是返回值 */
    *successor = NULL;
    *succ_parent = NULL;

    /* 查找 erase_node 的后继节点 */
    if( !(erase_node->left) )  /* erase_node 可能有右子节点或没有子节点 */
        *successor = erase_node->right;  /* successor 可能为空 */
    else  /* erase_node 有左子节点 */
    {
        if( !(erase_node->right) )  /* 只有左子节点 */
            *successor = erase_node->left;
        else  /* 左、右子节点都有，相当于调用 bbstree_itr_next(pos) */
        {
            pos = erase_node->right;
            while( pos->left )
                pos = pos->left;
            *successor = pos->right;
        }
    }

    /* 替换 erase_node */
    if( pos != erase_node )  /* erase_node 左、右子节点都有时会不相等 */
    {
        rbtree_color_t color_temp;

        /* pos 是 erase_node 的后继节点 */
        erase_node->left->parent = pos;
        pos->left = erase_node->left;
        if( pos != erase_node->right )
        {
            *succ_parent = pos->parent;
            if( *successor )
                (*successor)->parent = pos->parent;
            pos->parent->left = *successor;
            pos->right = erase_node->right;
            erase_node->right->parent = pos;
        }
        else
            *succ_parent = pos;

        if( *root == erase_node )
            *root = pos;
        else if( erase_node->parent->left == erase_node )
            erase_node->parent->left = pos;
        else
            erase_node->parent->right = pos;

        pos->parent = erase_node->parent;
        color_temp = pos->color;
        pos->color = erase_node->color;
        erase_node->color = color_temp;
        pos = erase_node;
    }
    else  /* pos == erase_node */
    {
        *succ_parent = pos->parent;
        if( *successor )
            (*successor)->parent = *succ_parent;

        if( *root == erase_node )
            *root = *successor;
        else if( erase_node->parent->left == erase_node )
            erase_node->parent->left = *successor;
        else
            erase_node->parent->right = *successor;

        if( *leftmost == erase_node )
        {
            if( !(erase_node->right) )  /* leftmost->left must be null */
                *leftmost = erase_node->parent;
            else
                *leftmost = bbstree_min_element( *successor );
        }

        if( *rightmost == erase_node )
        {
            if( !(erase_node->left) )   /* rightmost->right must be null */
                *rightmost = erase_node->parent;
            else
                *rightmost = bbstree_max_element( *successor );
        }
    }  /* end else */

    return pos;
}

/******************************************************************************/

static void bbstree_erase_fixup( bbstree_node* erase_node,
                                 bbstree_node* header )
{
    bbstree_node* successor = NULL;
    bbstree_node* succ_parent= NULL;
    bbstree_node* pos = NULL;
    bbstree_node** root = &( header->parent );

    pos = bbstree_weed_node( erase_node, &successor, &succ_parent,
                             root, &(header->left), &(header->right) );

    if( RED != pos->color )
    {
        while( (successor != *root)
               && (!successor || BLACK == successor->color) )
        {
            /* successor is left child */
            if( successor == succ_parent->left )
            {
                /* succ_rbrother 是 successor 的右兄弟 */
                bbstree_node* succ_rbrother = succ_parent->right;

                /* 1: successor 的右兄弟是红色 */
                if( RED == succ_rbrother->color )
                {
                    succ_rbrother->color = BLACK;
                    succ_parent->color = RED;
                    *root = bbstree_rotate_left( succ_parent, *root );
                    succ_rbrother = succ_parent->right;
                }

                /* 2: successor 的右兄弟是黑色，并且右兄弟的两个孩子也是黑色 */
                if( ( !(succ_rbrother->left)
                      || BLACK == succ_rbrother->left->color )
                    && ( !(succ_rbrother->right)
                         || BLACK == succ_rbrother->right->color ) )
                {
                    succ_rbrother->color = RED;
                    successor = succ_parent;
                    succ_parent = succ_parent->parent;
                }
                else
                {
                    /* 2: successor 的右兄弟是黑色，右兄弟的左孩子是红色，
                          右兄弟的右孩子是黑色 */
                    if( !(succ_rbrother->right)
                        || BLACK == succ_rbrother->right->color )
                    {
                        if( succ_rbrother->left )
                            succ_rbrother->left->color = BLACK;
                        succ_rbrother->color = RED;
                        *root = bbstree_rotate_right( succ_rbrother, *root );
                        succ_rbrother = succ_parent->right;
                    }

                    /* 4: successor 的右兄弟是黑色，右兄弟的右孩子是红色 */
                    succ_rbrother->color = succ_parent->color;