yc_bbstree.c

来自「一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面」· C语言 代码 · 共 1,490 行 · 第 1/4 页

    }
    else if( pos == &(self->m_header) )  /* pos == end */
    {
        bbstree_node* back = RIGHTMOST( self );

        if( self->m_node_count > 0
            && self->m_cmp_key( GET_NODE_KEY(self, back),
                                DATA_KEY(self, value) ) < 0 )
            result = bbstree_insert_node( self, NULL, back, value );
        else
            result = bbstree_insert_unique_value( self, value );
    }
    else
    {
        bbstree_node* before = pos;
        bbstree_itr_dec( &before );

        /* before < value < pos */
        if( self->m_cmp_key( GET_NODE_KEY(self, before),
                             DATA_KEY(self, value) ) < 0
            && self->m_cmp_key( DATA_KEY(self, value),
                                GET_NODE_KEY(self, pos) ) < 0 )
        {
            if( pos->right )
                result = bbstree_insert_node( self, pos, pos, value );
            else
                result = bbstree_insert_node( self, NULL, before, value );
        }
        else
            result = bbstree_insert_unique_value( self, value );
    }

    return result;
}

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

bbstree_node* bbstree_insert_equal_value( bbstree* self, const void* value )
{
    bbstree_node* parent = &(self->m_header);
    bbstree_node* child = ROOT( self );

    if( self->m_get_key )
    {
        const void* key = self->m_get_key( value );
        while( child )
        {
            parent = child;
            if( self->m_cmp_key( key, NODE_KEY(self, child) ) < 0 )
                child = child->left;
            else
                child = child->right;
        }
    }
    else
    {
        while( child )
        {
            parent = child;
            if( self->m_cmp_key( value, NODE_DATA(child) ) < 0 )
                child = child->left;
            else
                child = child->right;
        }
    }

    return bbstree_insert_node( self, child, parent, value );
}

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

bbstree_node* bbstree_insert_equal_pos( bbstree* self,
                                        bbstree_node* pos,
                                        const void* value )
{
    bbstree_node* result = NULL;

    if( pos == LEFTMOST(self) )  /* pos == begin */
    {
        /* count > 0  and  value < pos */
        if( self->m_node_count > 0
            && self->m_cmp_key( DATA_KEY(self, value),
                                GET_NODE_KEY(self, pos) ) < 0 )
            result = bbstree_insert_node( self, pos, pos, value );
        else
            result = bbstree_insert_equal_value( self, value );
    }
    else if( pos == &(self->m_header) )  /* pos == end */
    {
        bbstree_node* back = RIGHTMOST( self );

        /* count > 0  and  value >= back */
        if( self->m_node_count > 0
            && self->m_cmp_key( DATA_KEY(self, value),
                                GET_NODE_KEY(self, back) ) >= 0 )
            result = bbstree_insert_node( self, NULL, back, value );
        else
            result = bbstree_insert_equal_value( self, value );
    }
    else
    {
        bbstree_node* before = pos;
        bbstree_itr_dec( &before );

        /* pos >= value >= before */
        if( self->m_cmp_key( DATA_KEY(self, value),
                             GET_NODE_KEY(self, before) ) >= 0
            && self->m_cmp_key( GET_NODE_KEY(self, pos),
                                DATA_KEY(self, value) ) >= 0 )
        {
            if( pos->right )
                result = bbstree_insert_node( self, pos, pos, value );
            else
                result = bbstree_insert_node( self, NULL, before, value );
        }
        else
            result = bbstree_insert_equal_value( self, value );
    }

    return result;
}

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

bool bbstree_replace_key_unique_pos( bbstree* self,
                                     bbstree_node* pos,
                                     const void* new_key,
                                     ylib_fp_copy_t copy_key )
{
    if( (pos && pos == &(self->m_header))
        || bbstree_find(self, new_key) != &(self->m_header) )
        return false;

    bbstree_replace_key_node( self, pos, new_key, copy_key );
    return true;
}

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

bbstree_node* bbstree_replace_key_unique( bbstree* self,
                                          const void* old_key,
                                          const void* new_key,
                                          ylib_fp_copy_t copy_key )
{
    bbstree_node* result = bbstree_find( self, old_key );

    if( result == &(self->m_header)
        || bbstree_find(self, new_key) != &(self->m_header) )
        return &(self->m_header);

    bbstree_replace_key_node( self, result, new_key, copy_key );
    return result;
}

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

void bbstree_replace_key_equal_pos( bbstree* self,
                                    bbstree_node* pos,
                                    const void* new_key,
                                    ylib_fp_copy_t copy_key )
{
    if( pos && pos != &(self->m_header) )
        bbstree_replace_key_node( self, pos, new_key, copy_key );
}

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

void bbstree_replace_key_equal( bbstree* self,
                                const void* old_key,
                                const void* new_key,
                                ylib_fp_copy_t copy_key )
{
    bbstree_node* first = bbstree_lower_bound( self, old_key );
    bbstree_node* last = bbstree_upper_bound( self, old_key );

    if( first != &(self->m_header) )
    {
        bbstree_node* replace_pos;

        while( first != last
               && self->m_cmp_key( new_key, GET_NODE_KEY(self, first) ) != 0 )
        {
            replace_pos = first;
            bbstree_itr_inc( &first );
            bbstree_replace_key_node( self, replace_pos, new_key, copy_key );
        }
    }
}

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

bool bbstree_foreach( bbstree* self,
                      void (*oper_node)(bbstree*, const bbstree_node*) )
{
    if( self->m_node_count > 0 )
    {
        bbstree_node** front;
        bbstree_node** back;

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_VARIABLE_LENGTH_ARRAY__
        size_t alloc_size = sizeof(bbstree_node*) * self->m_node_count;
        bbstree_node** queue = (bbstree_node**)( self->m_alloc(alloc_size) );
        if( !queue )
            return false;
#else
        bbstree_node* queue[ self->m_node_count ];
#endif

        front = queue;
        back = queue + 1;

        *front = ROOT( self );
        while( front < back )
        {
            if( (*front)->left )
            {
                *back = (*front)->left;
                ++back;
            }
            if( (*front)->right )
            {
                *back = (*front)->right;
                ++back;
            }
            oper_node( self, *front );
            ++front;
        }

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_VARIABLE_LENGTH_ARRAY__
        self->m_dealloc( queue, alloc_size );
#endif
    }

    return true;
}

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

size_t bbstree_node_height( const bbstree_node* pos,
                            const bbstree_node* root )
{
    size_t height = 0;

    while( pos->parent && pos != root )
    {
        ++height;
        pos = pos->parent;
    }

    return height;
}

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

static size_t rbtree_black_count( const bbstree_node* node,
                                  const bbstree_node* root )
{
    size_t count;

    if( !node )
        return 0;

    count = ( BLACK == node->color ? 1 : 0 );

    if( node == root )
        return count;
    else
        return rbtree_black_count(node->parent, root) + count;
}

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

/*
 * 1. Every node is either red or black.
 * 2. The root is black.
 * 3. Every leaf (NIL) is black.
 * 4. If a node is red, then both its children are black.
 * 5. For each node, all paths from the node to descendant leaves contain
 *    the same number of black nodes.
 */
bool verify_red_black_tree( bbstree* self )
{
    size_t black_count = 0;
    bbstree_node* current;
    bbstree_node* last;
    bbstree_node* lchild;
    bbstree_node* rchild;

    if( self->m_node_count == 0 || self->m_header.left == &(self->m_header) )
        return ( self->m_node_count == 0
                 && self->m_header.left == &(self->m_header)
                 && self->m_header.right == &(self->m_header) )
               ? true : false;

    black_count = rbtree_black_count( LEFTMOST(self), ROOT(self) );
    current = self->m_header.left;
    last = &( self->m_header );

    while( current != last )
    {
        lchild = current->left;
        rchild = current->right;

        if( RED == current->color )
        {
            if( (lchild && RED == lchild->color)
                || (rchild && RED == rchild->color) )
                return false;
        }

        if( lchild && self->m_cmp_key( GET_NODE_KEY(self, current),
                                       GET_NODE_KEY(self, lchild) ) < 0 )
            return false;

        if( rchild && self->m_cmp_key( GET_NODE_KEY(self, rchild),
                                       GET_NODE_KEY(self, current) ) < 0 )
            return false;

        if( !lchild && !rchild
            && rbtree_black_count(current, ROOT(self)) != black_count )
            return false;

        bbstree_itr_inc( &current );
    }  /* end while */

    if( LEFTMOST(self) != bbstree_min_element(ROOT(self))
        || RIGHTMOST(self) != bbstree_max_element(ROOT(self)) )
        return false;

    return true;
}

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

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_INLINE_FUNCTION__
    size_t bbstree_max_size( void )
    {
        return SIZE_MAX;
    }

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

    size_t bbstree_size( bbstree* self )
    {
        return self->m_node_count;
    }

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

    bbstree_node* bbstree_begin( bbstree* self )
    {
        return self->m_header.left;
    }

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

    bbstree_node* bbstree_end( bbstree* self )
    {
        return &(self->m_header);
    }
#endif

/******************************************************************************/
/******************************************************************************/
#ifdef __cplusplus
    }  }
#endif
/******************************************************************************/
/******************************************************************************/