mstl_hash_table.hpp

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

/*
The young Library
Copyright (c) 2005 by 杨桓

Permission to use, copy, modify, distribute and sell this software for any
purpose is hereby granted without fee, provided that the above copyright
notice appear in all copies and that both that copyright notice and this
permission notice appear in supporting documentation.
The author make no representations about the suitability of this software
for any purpose. It is provided "as is" without express or implied warranty.
*/

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_MINI_STL_HASH_TABLE_HEADER_FILE__
#define __MACRO_CPLUSPLUS_MINI_STL_HASH_TABLE_HEADER_FILE__
//-----------------------------------------------------------------------------
#include "mstl_hash_table_base.hpp"
#include "../mstl_pair.hpp"
#include "../mstl_vector.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename Value >
struct hash_table_node
{
    hash_table_node*  next;  //当节点为链表的尾节点时，该值为空
    Value  data;
};

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

template< typename T, typename Ref, typename Ptr, typename Key,
          typename HashFun, typename ExtractKey, typename EqualKey,
          typename Alloc >
class hash_table_iterator;

template< typename Key, typename Value, typename HashFun,
          typename ExtractKey, typename EqualKey, typename Allocator >
class hash_table;

template< typename T, typename Key, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Alloc >
inline
hash_table_iterator<T, T&, T*, Key, HashFun, ExtractKey, EqualKey, Alloc>
const_iter_cast( const hash_table_iterator<T, const T&, const T*, Key,
                           HashFun, ExtractKey, EqualKey, Alloc>& citer );



template< typename T, typename Ref, typename Ptr, typename Key,
          typename HashFun, typename ExtractKey, typename EqualKey,
          typename Alloc >
class hash_table_iterator
{
public:
    typedef  forward_iterator_tag  iterator_category;
    typedef  def_size_t            size_type;
    typedef  def_ptrdiff_t         difference_type;
    typedef  T                     value_type;
    typedef  Ref                   reference;
    typedef  Ptr                   pointer;

    typedef  hash_table_iterator<T, Ref, Ptr, Key, HashFun, ExtractKey,
                                 EqualKey, Alloc>  self;

    typedef  hash_table_iterator<T, T&, T*, Key, HashFun, ExtractKey,
                                 EqualKey, Alloc>  iterator;

    typedef  hash_table_iterator<T, const T&, const T*, Key, HashFun,
                                 ExtractKey, EqualKey, Alloc>  const_iterator;

private:
    typedef  hash_table<Key, T, HashFun, ExtractKey, EqualKey, Alloc>
             hashtable;

    typedef  hash_table_node<value_type>  node;

    typedef  typename primal_type<Ref>::contrary_const_ref  Ref_t;
    typedef  typename primal_type<Ptr>::contrary_const_ptr  Ptr_t;

    friend class hash_table<Key, T, HashFun, ExtractKey, EqualKey, Alloc>;
    friend class hash_table_iterator<T, Ref_t, Ptr_t, Key, HashFun,
                                     ExtractKey, EqualKey, Alloc>;
    friend iterator const_iter_cast <> ( const const_iterator& );


    node*       current;
    hashtable*  table;

public:
    hash_table_iterator() : current(NULL_POINTER), table(NULL_POINTER)  {}

    hash_table_iterator( node* n_ptr, hashtable* ht_ptr )
    : current(n_ptr), table(ht_ptr)  {}

    hash_table_iterator( const iterator& x )
    : current(x.current), table(x.table)  {}

    self& operator=( def_nullptr_t n )
    {
        if( n == NULL_POINTER )
        {
            current = NULL_POINTER;
            table = NULL_POINTER;
        }
        return *this;
    }

    bool operator!() const  {  return ( !current && !table );  }

    bool operator==( const self& rhs ) const  {  return current == rhs.current;  }
    bool operator!=( const self& rhs ) const  {  return current != rhs.current;  }

    reference operator*() const  {  return current->data;  }
    pointer operator->() const   {  return &( operator*() );  }

    self& operator++();
    self operator++(int)
    {
        self old = *this;
        ++(*this);
        return old;
    }

};  //end iterator

template< typename T, typename Ref, typename Ptr, typename Key,
          typename HashFun, typename ExtractKey, typename EqualKey,
          typename Alloc >
hash_table_iterator<T, Ref, Ptr, Key, HashFun, ExtractKey, EqualKey, Alloc>&
hash_table_iterator<T, Ref, Ptr, Key, HashFun, ExtractKey, EqualKey, Alloc>::
operator++()
{
    const node* old = current;
    current = current->next;

    if( !current )
    {
        size_type bucket = table->bucket_pos_value( old->data );
        size_type bkt_size = table->m_buckets.size();
        while( !current && ++bucket < bkt_size )
            current = table->m_buckets[bucket];
    }

    return *this;
}



template< typename T, typename Key, typename HashFun, typename ExtractKey,
          typename EqualKey, typename Alloc >
inline
hash_table_iterator<T, T&, T*, Key, HashFun, ExtractKey, EqualKey, Alloc>
const_iter_cast( const hash_table_iterator<T, const T&, const T*, Key,
                           HashFun, ExtractKey, EqualKey, Alloc>& citer )
{
    return hash_table_iterator<T, T&, T*, Key, HashFun, ExtractKey,
                               EqualKey, Alloc>( citer.current, citer.table );
}

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

template< typename Key, typename Value,
          typename HashFun, typename ExtractKey, typename EqualKey,
          typename Allocator = allocator< hash_table_node<Value> > >
class hash_table
{
public:
    typedef  hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>
             self;

    typedef  Key         key_type;
    typedef  HashFun     hasher;
    typedef  ExtractKey  extract_key;
    typedef  EqualKey    key_equal;
    typedef  Allocator   allocator_type;

    typedef  Value              value_type;
    typedef  value_type&        reference;
    typedef  const value_type&  const_reference;
    typedef  value_type*        pointer;
    typedef  const value_type*  const_pointer;
    typedef  def_size_t         size_type;
    typedef  def_ptrdiff_t      difference_type;

    typedef  hash_table_iterator
             <Value, Value&, Value*, Key, HashFun, ExtractKey, EqualKey,
              Allocator>  iterator;

    typedef  hash_table_iterator
             <Value, const Value&, const Value*, Key, HashFun, ExtractKey,
              EqualKey, Allocator>  const_iterator;

    typedef  pair<iterator, iterator>              pair_iterator;
    typedef  pair<const_iterator, const_iterator>  pair_const_iterator;
    typedef  pair<iterator, bool>                  pair_iterator_bool;

    friend  class hash_table_iterator<Value, Value&, Value*, Key, HashFun,
                                      ExtractKey, EqualKey, Allocator>;

    friend  class hash_table_iterator<Value, const Value&, const Value*, Key,
                                      HashFun, ExtractKey, EqualKey, Allocator>;

protected:
    typedef  hash_table_node<value_type>  node;
    typedef  typename Allocator::template rebind<node*>::other  ptr_allocator;
//    typedef  allocator<node*>  ptr_allocator;
    typedef  pair<node*, node*>  pair_node_ptr;


    hasher          m_hash;
    key_equal       m_eq_key;
    extract_key     m_get_key;
    size_type       m_node_count;
    double          m_hash_factor;
    allocator_type  m_alloc;
    vector<node*, ptr_allocator>  m_buckets;

public:
    explicit hash_table( size_type size,
                         const hasher& hf = hasher(),
                         const key_equal& eq = key_equal(),
                         const extract_key& et = extract_key() )
    : m_hash(hf), m_eq_key(eq), m_get_key(et), m_node_count(0),
      m_hash_factor(0.75)
    {
        init_buckets( size );
    }

    hash_table( const self& rhs )
    : m_hash(rhs.m_hash), m_eq_key(rhs.m_eq_key), m_get_key(rhs.m_get_key),
      m_node_count(0), m_hash_factor(0.75)
    {
        copy( rhs );
    }

    self& operator=( const self& rhs )
    {
        if( this != &rhs )
        {
            clear();
            m_hash = rhs.m_hash;
            m_eq_key = rhs.m_eq_key;
            m_get_key = rhs.m_get_key;
            copy( rhs );
        }
        return *this;
    }

    ~hash_table()  {  clear();  }

    hasher hash_fun() const   {  return m_hash;  }
    key_equal key_eq() const  {  return m_eq_key;  }

    double get_hash_factor() const  {  return m_hash_factor;  }
    void set_hash_factor( double factor )
    {
        if( factor > 0 )
            m_hash_factor = factor;
    }

    void clear();
    void resize( size_type new_elements );
    size_type count( const key_type& k ) const;

    size_type size() const          {  return m_node_count;  }
    size_type max_size() const      {  return size_t_max;  }
    bool empty() const              {  return ( m_node_count == 0 );  }
    size_type bucket_count() const  {  return m_buckets.size();  }

    size_type max_bucket_count() const
    {
        return hash_table_prime_list[ hash_table_num_primes - 1 ];
    }

    size_type elements_in_bucket( size_type bucket ) const
    {
        size_type result = 0;
        node* current = m_buckets[bucket];
        while( current )
        {
            result += 1;
            current = current->next;
        }
        return result;
    }

    iterator begin()
        {  return iterator( begin_node(), this );  }
    iterator end()
        {  return iterator( (node*)NULL_POINTER, this );  }
    const_iterator begin() const
        {  return const_iterator( begin_node(), const_cast<self*>(this) );  }
    const_iterator end() const
        {  return const_iterator( (node*)NULL_POINTER, const_cast<self*>(this) );  }

    void modify_key_equal( const key_type& k, const key_type& new_key );
    void modify_key_equal( iterator position, const key_type& new_key )
    {
        if( position != end() )
            modify_key_aux( position, new_key );
    }
    iterator modify_key_unique( const key_type& k, const key_type& new_key )
    {
        iterator result = find( k );
        if( result != end() && find(new_key) == end() )
            modify_key_aux( result, new_key );
        return result;
    }
    bool modify_key_unique( iterator position, const key_type& new_key )
    {
        if( position == end() || find(new_key) != end() )
            return false;
        modify_key_aux( position, new_key );
        return true;
    }

    void swap( self& rhs )
    {
        if( this != &rhs )
        {
            data_swap( m_hash, rhs.m_hash );
            data_swap( m_eq_key, rhs.m_eq_key );
            data_swap( m_get_key, rhs.m_get_key );