mstl_hash_table.hpp

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

        {
            node* next = current->next;
            while( next )
            {
                if( next == erase_node )  //找到要删除的节点
                {
                    current->next = next->next;
                    return;
                }
                else
                {
                    current = next;
                    next = current->next;
                }
            }  //end while
        }  //end else
    }
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Allocator >
void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::
erase( iterator first, iterator last )
{
    if( first != last )
    {
        size_type first_bkt = first.current ? bucket_pos_value( first.current->data )
                              : m_buckets.size();
        size_type last_bkt = last.current ? bucket_pos_value( last.current->data )
                             : m_buckets.size();

        if( first_bkt == last_bkt )
            erase_bucket( first_bkt, first.current, last.current );
        else
        {
            for( size_type i = first_bkt; i < last_bkt; ++i )
                erase_bucket( i, 0 );
            if( last_bkt != m_buckets.size() )
                erase_bucket( last_bkt, last.current );
        }
    }
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Allocator >
typename
hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::size_type
hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::
erase( const key_type& k )
{
    size_type erase_count = 0;
    const size_type n = bucket_pos_key( k );
    node* first = m_buckets[n];

    if( first )
    {
        node* current = first;
        node* next = current->next;

        while( next )  //先删除first后面的等价节点
        {
            if( m_eq_key( m_get_key(next->data), k ) )
            {
                current->next = next->next;
                destroy_node( next );
                next = current->next;
                --m_node_count;
                ++erase_count;
            }
            else
            {
                current = next;
                next = current->next;
            }
        }

        if( m_eq_key( m_get_key(first->data), k ) )  //确定是否删除第一个节点
        {
            m_buckets[n] = first->next;
            destroy_node( first );
            --m_node_count;
            ++erase_count;
        }
    }

    return erase_count;
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Allocator >
void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::
erase_bucket( const size_type bkt_num, node* first, node* last )
{
    node* current = m_buckets[bkt_num];

    if( current == first )
        erase_bucket( bkt_num, last );
    else
    {
        node* next = current->next;

        while( next != first )  //找到first在链表中的位置
        {
            current = next;
            next = current->next;
        }  //current将指向first之前的那个节点

        while( next != last )
        {
            current->next = next->next;
            destroy_node( next );
            next = current->next;
            --m_node_count;
        }
    }
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Allocator >
void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::
erase_bucket( const size_type bkt_num, node* last )
{
    node* current = m_buckets[bkt_num];
    node* next;

    while( current != last )
    {
    	next = current->next;
        destroy_node( current );
        current = next;
        --m_node_count;
    }

    m_buckets[bkt_num] = current;
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Allocator >
typename
hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::size_type
hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::
count( const key_type& k ) const
{
    const size_type n = bucket_pos_key( k );
    size_type result = 0;
    for( node* current = m_buckets[n]; current; current = current->next )
    {
        if( m_eq_key( m_get_key(current->data), k ) )
            ++result;
    }
    return result;
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Allocator >
typename hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::node*
hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::
find_node( const key_type& k ) const
{
    const size_type n = bucket_pos_key( k );
    node* current = m_buckets[n];
    while( current )
    {
        if( m_eq_key( m_get_key(current->data), k ) )
            break;
        else
            current = current->next;
    }
    return current;
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Allocator >
typename
hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::pair_node_ptr
hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::
equal_range_node( const key_type& k ) const
{
    const size_type i = bucket_pos_key( k );

    for( node* first = m_buckets[i]; first; first = first->next )
    {
        if( m_eq_key( m_get_key(first->data), k ) )
        {
            for( node* last = first->next; last; last = last->next )
            {
                if( !m_eq_key( m_get_key(first->data), k ) )
                    return pair_node_ptr( first, last );
            }

            for( size_type j = i + 1; j < m_buckets.size(); ++j )
            {
                if( m_buckets[j] )
                    return pair_node_ptr( first, m_buckets[j] );
            }
        }  //end if
    }  //end for

    return pair_node_ptr( (node*)NULL_POINTER, (node*)NULL_POINTER );
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Allocator >
void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::
modify_key_aux( iterator position, const key_type& new_key )
{
    node* modify_node = position.current;
    erase_adjust( position.current );

    try
    {
        const_cast<key_type&>( m_get_key(modify_node->data) ) = new_key;
    }
    catch(...)
    {
        destroy_node( modify_node );
        --m_node_count;
        throw;
    }

    //为节点寻找新插入的位置
    const size_type n = bucket_pos_key( new_key );
    node* first = m_buckets[n];
    node* current = first;

    while( current )
    {
        if( m_eq_key( m_get_key(current->data),
                      m_get_key(position.current->data) ) )
        {
            modify_node->next = current->next;
            current->next = modify_node;
            return;
        }
        current = current->next;
    }

    modify_node->next = first;
    m_buckets[n] = modify_node;
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Allocator >
void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::
modify_key_equal( const key_type& k, const key_type& new_key )
{
    //寻找新的插入位置
    const size_type n = bucket_pos_key( new_key );
    node* new_first = m_buckets[n];
    node* new_prev_first = NULL_POINTER;
    while( new_first )  //寻找新链表中是否有键值相等的点
    {
        if( m_eq_key( m_get_key(new_first->data), new_key ) )
            break;
        new_prev_first = new_first;
        new_first = new_first->next;
    }

    //修改所有键值相等的节点并插入新的位置
    const size_type i = bucket_pos_key( k );
    node* old_first = m_buckets[i];
    node* old_prev_first = old_first;
    node* adjust_node;

    while( old_first )
    {
        if( m_eq_key( m_get_key(old_first->data), k ) )
        {
            //已找到键值相等的节点
            while( old_first )
            {
                //调整原节点所在的链表
                adjust_node = old_first;
                old_first = old_first->next;
                old_prev_first->next = old_first;
                if( m_buckets[i] == adjust_node )
                    m_buckets[i] = old_first;

                //修改新找到节点的键值
                try
                {
                    const_cast<key_type&>( m_get_key(adjust_node->data) ) = new_key;
                }
                catch(...)
                {
                    destroy_node( adjust_node );
                    --m_node_count;
                    throw;
                }

                if( new_prev_first )  //新插入的bucket中有其他节点
                {
                    adjust_node->next = new_first;
                    new_prev_first->next = adjust_node;
                }
                else  //新插入的bucket没有其他节点或者第一个节点即为键值相等的节点
                {
                    m_buckets[n] = adjust_node;
                    adjust_node->next = new_first;
                }
                new_first = adjust_node;

                //判断下一个节点是否为空或者键值是否相等
                if( !old_first || !m_eq_key( m_get_key(old_first->data), k ) )
                    return;

            }  //end while
        }  //end if

        //未找到键值相等的节点则继续往下查找
        old_prev_first = old_first;
        old_first = old_first->next;
    }  //end while
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Allocator >
inline void swap( hash_table
                  <Key, Value, HashFun, ExtractKey, EqualKey, Allocator>& lhs,
                  hash_table
                  <Key, Value, HashFun, ExtractKey, EqualKey, Allocator>& rhs )
{
    lhs.swap( rhs );
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_END_NAMESPACE__
#endif
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------