yc_bbstree.c

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

                    succ_parent->color = BLACK;
                    if( succ_rbrother->right )
                        succ_rbrother->right->color = BLACK;
                    *root = bbstree_rotate_left( succ_parent, *root );
                    break;
                }
            }  /* end if : successor is left child */
            else  /* successor is right child */
            {
                bbstree_node* succ_lbrother = succ_parent->left;

                if( RED == succ_lbrother->color )
                {
                    succ_lbrother->color = BLACK;
                    succ_parent->color = RED;
                    *root = bbstree_rotate_right( succ_parent, *root );
                    succ_lbrother = succ_parent->left;
            	}

                if( ( !(succ_lbrother->right)
                      || BLACK == succ_lbrother->right->color )
                    && ( !(succ_lbrother->left)
                         || BLACK == succ_lbrother->left->color ) )
                {
                    succ_lbrother->color = RED;
                    successor = succ_parent;
                    succ_parent = succ_parent->parent;
                }
                else
                {
                    if( !(succ_lbrother->left)
                        || BLACK == succ_lbrother->left->color )
                    {
                        if( succ_lbrother->right )
                            succ_lbrother->right->color = BLACK;
                        succ_lbrother->color = RED;
                        *root = bbstree_rotate_left( succ_lbrother, *root );
                        succ_lbrother = succ_parent->left;
                    }

                    succ_lbrother->color = succ_parent->color;
                    succ_parent->color = BLACK;
                    if( succ_lbrother->left )
                        succ_lbrother->left->color = BLACK;
                    *root = bbstree_rotate_right( succ_parent, *root );
                    break;
                }
            }  /* end else : successor is right child */
        }  /* end while */

        if( successor )
            successor->color = BLACK;
    } /* end if */
}

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

static void bbstree_insert_fixup( bbstree_node* pos, bbstree_node** root )
{
    pos->color = RED;  /* 新节点先设置为红色 */

    while( pos != *root && RED == pos->parent->color )
    {
        /* pos->parent is left child */
        if( pos->parent == pos->parent->parent->left )
        {
            /* runcle 是 pos 的右叔父 */
            bbstree_node* runcle = pos->parent->parent->right;

            /* 1: 右叔父的颜色是红色，这时只需改变颜色 */
            if( runcle && RED == runcle->color )
            {
                runcle->color = BLACK;
                pos->parent->color = BLACK;
                pos->parent->parent->color = RED;
                pos = pos->parent->parent;
            }
            else  /* 右叔父是空节点或者右叔父的颜色是黑色 */
            {
                if( pos == pos->parent->right )  /* 2: pos 是右子节点*/
                {
                    pos = pos->parent;
                    *root = bbstree_rotate_left( pos, *root );
                }
                pos->parent->color = BLACK;  /* 3: exit while */
                pos->parent->parent->color = RED;
                *root = bbstree_rotate_right( pos->parent->parent, *root );
            }
        }
        else  /* pos->parent is right child */
        {
            bbstree_node* luncle = pos->parent->parent->left;

            if( luncle && RED == luncle->color )
            {
                luncle->color = BLACK;
                pos->parent->color = BLACK;
                pos->parent->parent->color = RED;
                pos = pos->parent->parent;
            }
            else
            {
                if( pos == pos->parent->left )
                {
                    pos = pos->parent;
                    *root = bbstree_rotate_right( pos, *root );
                }
                pos->parent->color = BLACK;
                pos->parent->parent->color = RED;
                *root = bbstree_rotate_left( pos->parent->parent, *root );
            }
        }
    } /* end while */

    (*root)->color = BLACK;
}

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

static bbstree_node* bbstree_insert_node( bbstree* self,
                                          bbstree_node* child,
                                          bbstree_node* parent,
                                          const void* value )
{
    const void* new_key;
    const void* parent_key;
    bbstree_node* new_node = (bbstree_node*)( self->m_alloc(
                                sizeof(bbstree_node) + self->m_element_size) );

    if( new_node )
    {
        COPY_VALUE( NODE_DATA(new_node), value, self->m_element_size,
                    self->m_elmt_init_copy );

        new_key = ( self->m_get_key ? self->m_get_key(value) : value );
        parent_key = GET_NODE_KEY( self, parent );

        /* value < parent */
        if( parent == &(self->m_header) || child
            || self->m_cmp_key(new_key, parent_key) < 0 )
        {
            parent->left = new_node;
            if( parent == &(self->m_header) )
            {
                self->m_header.parent = new_node;
                self->m_header.right = new_node;
            }
            else if( LEFTMOST(self) == parent )
                LEFTMOST(self) = new_node;
        }
        else  /* value >= parent */
        {
            parent->right = new_node;
            if( RIGHTMOST(self) == parent )
                RIGHTMOST(self) = new_node;
        }
        new_node->parent = parent;
        new_node->left = NULL;
        new_node->right = NULL;

        bbstree_insert_fixup( new_node, &(self->m_header.parent) );
        ++( self->m_node_count );
    }

    return new_node;
}

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

static void bbstree_replace_key_node( bbstree* self,
                                      bbstree_node* replace_node,
                                      const void* new_key,
                                      ylib_fp_copy_t copy_key )
{
    bbstree_node* result = NULL;
    bbstree_node* curr = NULL;
    void* oldkey = (void*)GET_NODE_KEY( self, replace_node );

    /* 如果只有一个节点，则直接替换 */
    if( self->m_node_count == 1 )
    {
        COPY_VALUE( oldkey, new_key, self->m_element_size, copy_key );
        return;
    }

    /* 先将要替换键的节点退出树，再将新的键赋值 */
    bbstree_erase_fixup( replace_node, &(self->m_header) );
    COPY_VALUE( oldkey, new_key, self->m_element_size, copy_key );

    /* 将节点重新插入树 */
    result = &(self->m_header);
    curr = ROOT( self );
    if( self->m_get_key )
    {
        while( curr )
        {
            result = curr;
            curr = ( self->m_cmp_key( new_key, NODE_KEY(self, curr) ) < 0
                     ? curr->left : curr->right );
        }
    }
    else
    {
        while( curr )
        {
            result = curr;
            curr = ( self->m_cmp_key( new_key, NODE_DATA(curr) ) < 0
                     ? curr->left : curr->right );
        }
    }

    if( self->m_cmp_key( new_key, GET_NODE_KEY(self, result) ) < 0 )
    {
        result->left = replace_node;
        if( LEFTMOST(self) == result )
            LEFTMOST(self) = replace_node;
    }
    else
    {
        result->right = replace_node;
        if( RIGHTMOST(self) == result )
            RIGHTMOST(self) = replace_node;
    }

    replace_node->parent = result;
    replace_node->left = NULL;
    replace_node->right = NULL;

    bbstree_insert_fixup( replace_node, &(self->m_header.parent) );
}

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

static void bbstree_destroy_tree( bbstree* self,
                                  bbstree_node* root )
{
    size_t node_size = sizeof(bbstree_node) + self->m_element_size;
    bool destroy = ( self->m_elmt_destroy ? true : false );
    bbstree_node* left;

    while( root )
    {
        bbstree_destroy_tree( self, root->right );
        left = root->left;
        if( true == destroy )
            self->m_elmt_destroy( NODE_DATA(root) );
        self->m_dealloc( root, node_size );
        root = left;
    }
}

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

static bbstree_node* bbstree_copy_node( bbstree* self,
                                        const bbstree_node* src )
{
    bbstree_node* dst = (bbstree_node*)( self->m_alloc( sizeof(bbstree_node)
                                         + self->m_element_size ) );

    if( dst )
    {
        dst->color = src->color;
        dst->parent = NULL;
        dst->left = NULL;
        dst->right = NULL;

        COPY_VALUE( NODE_DATA(dst), NODE_DATA(src),
                    self->m_element_size, self->m_elmt_init_copy );
    }

    return dst;
}

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

static bbstree_node* bbstree_copy_tree( bbstree* self,
                                        bbstree_node* dst,
                                        const bbstree_node* src )
{
    bbstree_node* root = bbstree_copy_node( self, src );

    if( root )
    {
        root->parent = dst;

        if( src->right )
            root->right = bbstree_copy_tree( self, root, src->right );
        dst = root;
        src = src->left;

        while( src )
        {
            bbstree_node* temp = bbstree_copy_node( self, src );
            if( !temp )
            {
                bbstree_destroy( self );
                return NULL;
            }
            dst->left = temp;
            temp->parent = dst;
            if( src->right )
                temp->right = bbstree_copy_tree( self, temp, src->right );
            dst = temp;
            src = src->left;
        }
    }

    return root;
}

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

static void bbstree_init_header( bbstree* self )
{
    self->m_header.parent = NULL;
    self->m_header.left = &( self->m_header );
    self->m_header.right = &( self->m_header );
    self->m_header.color = RED;
}

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

void bbstree_init( bbstree* uninit_self,
                   size_t element_size,
                   ylib_fp_copy_t elmt_init_copy,
                   ylib_fp_oper_t elmt_destroy,
                   ylib_fp_get_t get_key,
                   ylib_fp_cmp_t cmp_key,
                   ylib_fp_alloc_t alloc,
                   ylib_fp_dealloc_t dealloc )
{
    bbstree_init_header( uninit_self );

    uninit_self->m_node_count = 0;
    uninit_self->m_element_size = element_size;
    uninit_self->m_elmt_init_copy = elmt_init_copy;
    uninit_self->m_elmt_destroy = elmt_destroy;
    uninit_self->m_get_key = get_key;
    uninit_self->m_cmp_key = cmp_key;
    uninit_self->m_alloc = alloc;
    uninit_self->m_dealloc = dealloc;
}

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

void bbstree_destroy( bbstree* self )
{
    if( self->m_node_count > 0 )
        bbstree_destroy_tree( self, ROOT(self) );

    self->m_header.parent = NULL;
    self->m_header.left = &( self->m_header );
    self->m_header.right = &( self->m_header );
    self->m_node_count = 0;
}

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

int bbstree_init_copy( bbstree* uninit_self, const bbstree* src )
{
    if( uninit_self == src )
        return -1;
    else
    {
        *uninit_self = *src;
        bbstree_init_header( uninit_self );
        uninit_self->m_node_count = 0;

        if( src->m_node_count > 0 )
        {
            uninit_self->m_header.parent = bbstree_copy_tree( uninit_self,
                                &(uninit_self->m_header), ROOT(src) );