mstl_hash_table.hpp

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

            data_swap( m_node_count, rhs.m_node_count );
            data_swap( m_hash_factor, rhs.m_hash_factor );
            data_swap( m_alloc, rhs.m_alloc );
            m_buckets.swap( rhs.m_buckets );
        }
    }

    iterator find( const key_type& k )
        {  return iterator( find_node(k), this );  }
    const_iterator find( const key_type& k ) const
        {  return const_iterator( find_node(k), const_cast<self*>(this) );  }

    pair_iterator equal_range( const key_type& k )
    {
        pair_node_ptr pptr = equal_range_node( k );
        return pair_iterator( iterator(pptr.first, this),
                              iterator(pptr.second, this) );
    }
    pair_const_iterator equal_range( const key_type& k ) const
    {
        pair_node_ptr pptr = equal_range_node( k );
        return pair_const_iterator( const_iterator(pptr.first,
                                                   const_cast<self*>(this)),
                                    const_iterator(pptr.second,
                                                   const_cast<self*>(this)) );
    }

    void erase( iterator first, iterator last );
    size_type erase( const key_type& k );
    void erase( iterator position )
    {
        erase_adjust( position.current );
        destroy_node( position.current );
        --m_node_count;
    }

    pair_iterator_bool insert_unique( const value_type& v )
    {
        resize( m_node_count + 1 );
        return insert_unique_noresize( v );
    }
    template< typename InputIterator >
    void insert_unique( InputIterator first, InputIterator last,
                        size_type extra_size = 0 )
    {
        if( first != last )
            range_insert_unique( first, last,
                                 range_length(first, last, extra_size) );
    }

    iterator insert_equal( const value_type& v )
    {
        resize( m_node_count + 1 );
        return insert_equal_noresize( v );
    }
    template< typename InputIterator >
    void insert_equal( InputIterator first, InputIterator last,
                       size_type extra_size = 0 )
    {
        if( first != last )
            range_insert_equal( first, last,
                                range_length(first, last, extra_size) );
    }

protected:
    //初始化辅助函数
    void copy( const self& rhs );

    node* create_node( const_reference x )
    {
       node* ptr = m_alloc.allocate( 1 );
       try
       {
       	   construct( &(ptr->data), x );
       }
       catch(...)
       {
       	   m_alloc.deallocate( ptr, 1 );
       	   throw;
       }
       ptr->next = NULL_POINTER;
       return ptr;
    }

    void destroy_node( node* ptr )
    {
        destroy( &(ptr->data) );
        m_alloc.deallocate( ptr, 1 );
    }

    void init_buckets( size_type n )
    {
        const size_type bkt_size = hash_table_next_prime( n );
        m_buckets.assign( bkt_size, (node*)NULL_POINTER );
        m_node_count = 0;
    }


    //获得节点在散列表中位置的辅助函数
    size_type bucket_pos_key( const key_type& k, size_type n ) const
        {  return ( m_hash(k) % n );  }
    size_type bucket_pos_key( const key_type& k ) const
        {  return bucket_pos_key( k, m_buckets.size() );  }

    size_type bucket_pos_value( const value_type& v, size_type n ) const
        {  return bucket_pos_key( m_get_key(v), n );  }
    size_type bucket_pos_value( const value_type& v ) const
        {  return bucket_pos_key( m_get_key(v) );  }


    //insert、erase辅助函数
    pair_iterator_bool insert_unique_noresize( const value_type& v );
    iterator insert_equal_noresize( const value_type& v );

    template< typename InputIterator >
    void range_insert_unique( InputIterator first, InputIterator last,
                              size_type extra_size )
    {
        resize( m_node_count + extra_size );
        for( ; first != last; ++first )
            insert_unique_noresize( *first );
    }

    template< typename InputIterator >
    void range_insert_equal( InputIterator first, InputIterator last,
                             size_type extra_size )
    {
        resize( m_node_count + extra_size );
        for( ; first != last; ++first )
            insert_equal_noresize( *first );
    }

    void erase_bucket( const size_type bkt_num, node* first, node* last );
    void erase_bucket( const size_type bkt_num, node* last );


    //负责查找的辅助函数
    node* find_node( const key_type& k ) const;
    pair_node_ptr equal_range_node( const key_type& k ) const;


    node* begin_node() const;
    void erase_adjust( node* position );
    void modify_key_aux( iterator position, const key_type& new_key );

};  //end class

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

template< typename Key, typename Value, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Allocator >
void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::
copy( const self& rhs )
{
    m_buckets.assign( rhs.m_buckets.size(), (node*)NULL_POINTER );

    try
    {
        size_type bkt_size = rhs.m_buckets.size();
        for( size_type i = 0; i < bkt_size; ++i )
        {
            node* source = rhs.m_buckets[i];
            if( source )
            {
                m_buckets[i] = create_node( source->data );
                node* current = m_buckets[i];
                source = source->next;
                while( source )
                {
                    current->next = create_node( source->data );
                    source = source->next;
                    current = current->next;
                }  //end while
            }  //end if
        }  //end for
    }  //end try
    catch(...)
    {
        clear();
        throw;
    }
    m_node_count = rhs.m_node_count;
}
//-----------------------------------------------------------------------------

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>::
begin_node() const
{
    size_type bkt_size = m_buckets.size();
    for( size_type i = 0; i < bkt_size; ++i )
    {
        if( m_buckets[i] )
            return m_buckets[i];
    }
    return ( (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>::clear()
{
    size_type bkt_size = m_buckets.size();
    for( size_type i = 0; i < bkt_size; ++i )
    {
        node* current = m_buckets[i];
        node* temp;
        while( current )
        {
            temp = current;
            current = current->next;
            destroy_node( temp );
        }
        m_buckets[i] = NULL_POINTER;
    }
    m_node_count = 0;
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Allocator >
void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::
resize( size_type new_elements )
{
    const size_type old_bkt_size = m_buckets.size();

    //当新节点个数与buckets个数的比值大于散列系数时，就重构表
    if( (new_elements / old_bkt_size) > m_hash_factor )
    {
        const size_type new_bkt_size = hash_table_next_prime( new_elements );

        if( new_bkt_size > old_bkt_size )  //当质数为最大值时会相等
        {
            vector<node*> new_buckets( new_bkt_size, (node*)NULL_POINTER );

            try
            {
                for( size_type i = 0; i < old_bkt_size; ++i )
                {
                    node* current = m_buckets[i];
                    while( current )
                    {
                    	//寻找在新表中的新位置
                        const size_type new_pos =
                              bucket_pos_value( current->data, new_bkt_size );
                        m_buckets[i] = current->next;
                        current->next = new_buckets[new_pos];
                        new_buckets[new_pos] = current;
                        current = m_buckets[i];
                    }  //end while
                }  //end for
                m_buckets.swap( new_buckets );
            }  //end try
            catch(...)
            {
                for( size_type j = 0; j < new_buckets.size(); ++j )
                {
                    node* next;
                    while( new_buckets[j] )
                    {
                        next = new_buckets[j]->next;
                        destroy_node( new_buckets[j] );
                        new_buckets[j] = next;
                    }
                    throw;
                }  //end for
            }  //end catch
        }  //end if
    }  //end if
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Allocator >
typename hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::
pair_iterator_bool
hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::
insert_unique_noresize( const value_type& v )
{
    const size_type n = bucket_pos_value( v );  //找到新节点应插入的位置
    node* first = m_buckets[n];

    node* current = first;
    while( current )
    {
        if( m_eq_key( m_get_key(current->data), m_get_key(v) ) )  //有等价值则不插入
            return pair_iterator_bool( iterator(current, this), false );
        current = current->next;
    }

    node* new_node = create_node( v );
    new_node->next = first;
    m_buckets[n] = new_node;
    ++m_node_count;
    return pair_iterator_bool( iterator(new_node, this), true );
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Allocator >
typename
hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::iterator
hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::
insert_equal_noresize( const value_type& v )
{
    const size_type n = bucket_pos_value( v );
    node* first = m_buckets[n];

    node* current = first;
    while( current )
    {
        if( m_eq_key( m_get_key(current->data), m_get_key(v) ) )
        {
            node* new_node = create_node( v );
            new_node->next = current->next;
            current->next = new_node;
            ++m_node_count;
            return iterator( new_node, this );
        }
        current = current->next;
    }

    node* new_node = create_node( v );
    new_node->next = first;
    m_buckets[n] = new_node;
    ++m_node_count;
    return iterator( new_node, this );
}
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Allocator >
void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::
erase_adjust( node* erase_node )
{
    if( erase_node )
    {
        const size_type n = bucket_pos_value( erase_node->data );
        node* current = m_buckets[n];  //节点所在的bucket

        if( erase_node == current )  //删除节点是该bucket的第一个节点
            m_buckets[n] = current->next;
        else