yc_bbstree.c

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

            if( !(uninit_self->m_header.parent) )
                return 0;
            else
            {
                uninit_self->m_header.left
                    = bbstree_min_element( uninit_self->m_header.parent );
                uninit_self->m_header.right
                    = bbstree_max_element( uninit_self->m_header.parent );
            }
        }

        uninit_self->m_node_count = src->m_node_count;
    }

    return 1;
}

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

int bbstree_assign_copy( bbstree* self, const bbstree* src )
{
    if( self == src || self->m_element_size != src->m_element_size
        || self->m_elmt_init_copy != src->m_elmt_init_copy )
        return -1;
    else
    {
        bbstree_destroy( self );

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

            if( !(self->m_header.parent) )
                return 0;
            else
            {
                self->m_header.left
                    = bbstree_min_element( self->m_header.parent );
                self->m_header.right
                    = bbstree_max_element( self->m_header.parent );
            }
        }

        self->m_node_count = src->m_node_count;
    }

    return 1;
}

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

void bbstree_init_move( bbstree* uninit_self, bbstree* src )
{
    if( uninit_self != src )
    {
        *uninit_self = *src;
        bbstree_init_header( uninit_self );
        uninit_self->m_node_count = 0;
        bbstree_swap( uninit_self, src );
    }
}

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

void bbstree_assign_move( bbstree* self, bbstree* src )
{
    if( self != src )
        bbstree_swap( self, src );
}

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

void bbstree_swap( bbstree* self, bbstree* other )
{
    if( self != other )
    {
        bbstree temp;
        bool xempty = ( self->m_node_count == 0 ? true : false );
        bool yempty = ( other->m_node_count == 0 ? true : false );

        if( true == xempty )
        {
       	    if( true == yempty )
       	        return;

            temp = *self;
            *self = *other;
            *other = temp;
            bbstree_init_header( other );  /* empty other */

            /* other->root pointer to self->m_header */
            self->m_header.parent->parent = &(self->m_header);
        }
    	else
    	{
            temp = *self;
            *self = *other;
            *other = temp;

            /* self->root pointer to other->m_header */
            other->m_header.parent->parent = &(other->m_header);

            if( true == yempty )
                bbstree_init_header( self );  /* empty self */
            else
                self->m_header.parent->parent = &(self->m_header);
        }
    }
}

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

bbstree_node* bbstree_find( bbstree* self, const void* key )
{
    bbstree_node* result = &(self->m_header);
    bbstree_node* current = ROOT( self );

    if( self->m_get_key )
    {
        while( current )
        {
            /* current < key */
            if( self->m_cmp_key( NODE_KEY(self, current), key ) < 0 )
                current = current->right;
            else
            {
                result = current;
                current = current->left;
            }
        }
    }
    else
    {
        while( current )
        {
            if( self->m_cmp_key( NODE_DATA(current), key ) < 0 )
                current = current->right;
            else
            {
                result = current;
                current = current->left;
            }
        }
    }

    return ( result == &(self->m_header) )
           || ( self->m_cmp_key(key, GET_NODE_KEY(self, result)) < 0 )
           ? &(self->m_header) : result;
}

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

bbstree_node* bbstree_lower_bound( bbstree* self, const void* key )
{
    bbstree_node* result = &(self->m_header);
    bbstree_node* current = ROOT( self );

    if( self->m_get_key )
    {
        while( current )
        {
            /* current < key */
            if( self->m_cmp_key( NODE_KEY(self, current), key ) < 0 )
                current = current->right;
            else
            {
                result = current;
                current = current->left;
            }
        }
    }
    else
    {
        while( current )
        {
            if( self->m_cmp_key( NODE_DATA(current), key ) < 0 )
                current = current->right;
            else
            {
                result = current;
                current = current->left;
            }
        }
    }

    return result;
}

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

bbstree_node* bbstree_upper_bound( bbstree* self, const void* key )
{
    bbstree_node* result = &(self->m_header);
    bbstree_node* current = ROOT( self );

    if( self->m_get_key )
    {
        while( current )
        {
            /* key < current */
            if( self->m_cmp_key( key, NODE_KEY(self, current) ) < 0 )
            {
                result = current;
                current = current->left;
            }
            else
                current = current->right;
        }
    }
    else
    {
        while( current )
        {
            if( self->m_cmp_key( key, NODE_DATA(current) ) < 0 )
            {
                result = current;
                current = current->left;
            }
            else
                current = current->right;
        }
    }

    return result;
}

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

bbstree_pair_iterator bbstree_equal_range( bbstree* self, const void* key )
{
    bbstree_pair_iterator result;
    result.first = bbstree_lower_bound( self, key );
    result.second = bbstree_upper_bound( self, key );
    return result;
}

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

size_t bbstree_count( bbstree* self, const void* key )
{
    size_t count = 0;
    bbstree_node* first = bbstree_lower_bound( self, key );
    bbstree_node* last = bbstree_upper_bound( self, key );

    while( first != last )
    {
        ++count;
        bbstree_itr_inc( &first );
    }

    return count;
}

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

void bbstree_erase_pos( bbstree* self, bbstree_node* pos )
{
    if( pos && pos != &(self->m_header) )
    {
        bbstree_erase_fixup( pos, &(self->m_header) );
        if( self->m_elmt_destroy )
            self->m_elmt_destroy( NODE_DATA(pos) );
        self->m_dealloc( pos, sizeof(bbstree_node) + self->m_element_size );
        --( self->m_node_count );
    }
}

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

void bbstree_erase_range( bbstree* self,
                          bbstree_node* first,
                          bbstree_node* last )
{
    if( first && last && first != &(self->m_header) )
    {
        if( first == self->m_header.left && last == &(self->m_header) )
            bbstree_destroy( self );
        else
        {
            bbstree_node* erase_node;

            while( first != last )
            {
                erase_node = first;
                bbstree_itr_inc( &first );
                bbstree_erase_pos( self, erase_node );
            }
        }
    }
}

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

size_t bbstree_erase_key( bbstree* self, const void* key )
{
    size_t count = 0;
    bbstree_node* erase_node = NULL;
    bbstree_node* first = bbstree_lower_bound( self, key );
    bbstree_node* last = bbstree_upper_bound( self, key );

    while( first != last )
    {
        ++count;
        erase_node = first;
        bbstree_itr_inc( &first );
        bbstree_erase_pos( self, erase_node );
    }

    return count;
}

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

bbstree_node* bbstree_insert_unique_value( bbstree* self, const void* value )
{
    int less_val = -1;
    bbstree_node* result;
    bbstree_node* parent = &(self->m_header);
    bbstree_node* current = ROOT( self );

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

    result = parent;
    if( less_val < 0 )  /* last result is value < current */
    {
        if( result == LEFTMOST(self) )
            return bbstree_insert_node( self, current, parent, value );
        else
            bbstree_itr_dec( &result );
    }

    /* result < value */
    if( self->m_cmp_key(GET_NODE_KEY(self, result), DATA_KEY(self, value)) < 0 )
        return bbstree_insert_node( self, current, parent, value );

    return result;
}

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

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

    if( pos == LEFTMOST(self) )  /* pos == begin */
    {
        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_unique_value( self, value );