hash_map_rdestl.h

#ifndef RDESTL_HASH_MAP_H
#define RDESTL_HASH_MAP_H

#include <stk_util/util/algorithm_rdestl.h>
#include <stk_util/util/allocator_rdestl.h>
#include <stk_util/util/functional_rdestl.h>
#include <stk_util/util/hash_rdestl.h>
#include <stk_util/util/pair_rdestl.h>

namespace rde
{

// TLoadFactor4 - controls hash map load. 4 means 100% load, ie. hashmap will grow
// when number of items == capacity. Default value of 6 means it grows when
// number of items == capacity * 3/2 (6/4). Higher load == tighter maps, but bigger
// risk of collisions.
template<typename TKey, typename TValue,
    class THashFunc = rde::hash<TKey>,
    int TLoadFactor4 = 6,
    class TKeyEqualFunc = rde::equal_to<TKey>,
    class TAllocator = rde::allocator>
class hash_map
{
public:
  typedef rde::pair<TKey, TValue>         value_type;

private:
  struct node
    {
    static const hash_value_t kUnusedHash       = 0xFFFFFFFF;
        static const hash_value_t kDeletedHash      = 0xFFFFFFFE;

        node(): hash(kUnusedHash) {}

        RDE_FORCEINLINE bool is_unused() const    { return hash == kUnusedHash; }
        RDE_FORCEINLINE bool is_deleted() const     { return hash == kDeletedHash; }
        RDE_FORCEINLINE bool is_occupied() const  { return hash < kDeletedHash; }

    hash_value_t    hash;
        value_type      data;
  };
  template<typename TNodePtr, typename TPtr, typename TRef>
    class node_iterator
    {
    friend class hash_map;
    public:
    typedef forward_iterator_tag    iterator_category;

        explicit node_iterator(TNodePtr node, const hash_map* map)
        : m_node(node),
            m_map(map)
    {}
        template<typename UNodePtr, typename UPtr, typename URef>
        node_iterator(const node_iterator<UNodePtr, UPtr, URef>& rhs)
        : m_node(rhs.node()),
      m_map(rhs.get_map())
    {}

    TRef operator*() const
        {
      RDE_ASSERT(m_node != 0);
            return m_node->data;
    }
        TPtr operator->() const
        {
      return &m_node->data;
    }
        RDE_FORCEINLINE TNodePtr node() const
        {
      return m_node;
    }

    node_iterator& operator++()
        {
      RDE_ASSERT(m_node != 0);
      ++m_node;
            move_to_next_occupied_node();
      return *this;
        }
    node_iterator operator++(int)
        {
      node_iterator copy(*this);
            ++(*this);
            return copy;
    }

        RDE_FORCEINLINE bool operator==(const node_iterator& rhs) const
        {
      return rhs.m_node == m_node;
    }
        bool operator!=(const node_iterator& rhs) const
        {
      return !(rhs == *this);
    }

        const hash_map* get_map() const { return m_map; }
  private:
    void move_to_next_occupied_node()
        {
      // @todo: save nodeEnd in constructor?
      TNodePtr nodeEnd = m_map->m_nodes + m_map->bucket_count();
            for (; m_node < nodeEnd; ++m_node)
            {
        if (m_node->is_occupied())
          break;
      }
    }
        TNodePtr    m_node;
        const hash_map* m_map;
  };

public:
  typedef TKey   key_type;
        typedef TValue                                mapped_type;
        typedef TAllocator                              allocator_type;
  typedef node_iterator<node*, value_type*, value_type&>            iterator;
  typedef node_iterator<const node*, const value_type*, const value_type&>  const_iterator;
        typedef int                                 size_type;
  static const size_type                            kNodeSize = sizeof(node);
  static const size_type                            kInitialCapacity = 64;

  hash_map()
  : m_nodes(&ms_emptyNode),
    m_size(0),
    m_capacity(0),
    m_capacityMask(0),
    m_numUsed(0)
  {
    RDE_ASSERT((kInitialCapacity & (kInitialCapacity - 1)) == 0); // Must be power-of-two
  }
  explicit hash_map(const allocator_type& allocator)
    : m_nodes(&ms_emptyNode),
        m_size(0),
        m_capacity(0),
    m_capacityMask(0),
        m_numUsed(0),
        m_allocator(allocator)
  {
    
  }
  explicit hash_map(size_type initial_bucket_count,
    const allocator_type& allocator = allocator_type())
    : m_nodes(&ms_emptyNode),
        m_size(0),
        m_capacity(0),
    m_capacityMask(0),
        m_numUsed(0),
        m_allocator(allocator)
  {
    reserve(initial_bucket_count);
  }
  hash_map(size_type initial_bucket_count,
    const THashFunc& hashFunc,
    const allocator_type& allocator = allocator_type())
    : m_nodes(&ms_emptyNode),
        m_size(0),
        m_capacity(0),
    m_capacityMask(0),
        m_numUsed(0),
    m_hashFunc(hashFunc),
        m_allocator(allocator)
  {
    reserve(initial_bucket_count);
  }
  hash_map(const hash_map& rhs, const allocator_type& allocator = allocator_type())
    : m_nodes(&ms_emptyNode),
        m_size(0),
        m_capacity(0),
    m_capacityMask(0),
        m_numUsed(0),
        m_allocator(allocator)
  {
    *this = rhs;
  }
  explicit hash_map(e_noinitialize)
  {
    
  }
  ~hash_map()
  {
    delete_nodes();
  }

  iterator begin()
    {
    iterator it(m_nodes, this);
    it.move_to_next_occupied_node();
    return it;
  }
  const_iterator begin() const
    {
    const_iterator it(m_nodes, this);
    it.move_to_next_occupied_node();
    return it;
  }
  iterator end()              { return iterator(m_nodes + m_capacity, this); }
  const_iterator end() const  { return const_iterator(m_nodes + m_capacity, this); }

  // @note: Added for compatiblity sake.
  //      Personally, I consider it "risky". Use find/insert for more
  //      explicit operations.
  mapped_type& operator[](const key_type& key)
  {
    hash_value_t hash;
    node* n = find_for_insert(key, &hash);
    if (n == 0 || !n->is_occupied())
    {
      return insert_at(value_type(key, TValue()), n, hash).first->second;
    }
    return n->data.second;
  }
  // @note: Doesn't copy allocator.
  hash_map& operator=(const hash_map& rhs)
  {
    RDE_ASSERT(invariant());
    if (&rhs != this)
    {
      clear();
      if (m_capacity < rhs.bucket_count())
      {
        delete_nodes();
        m_nodes = allocate_nodes(rhs.bucket_count());
        m_capacity = rhs.bucket_count();
        m_capacityMask = m_capacity - 1;
      }
      rehash(m_capacity, m_nodes, rhs.m_capacity, rhs.m_nodes, false);
      m_size = rhs.size();
      m_numUsed = rhs.m_numUsed;
    }
    RDE_ASSERT(invariant());
    return *this;
  }
  void swap(hash_map& rhs)
  {
    if (&rhs != this)
    {
      RDE_ASSERT(invariant());
      RDE_ASSERT(m_allocator == rhs.m_allocator);
      rde::swap(m_nodes, rhs.m_nodes);
      rde::swap(m_size, rhs.m_size);
      rde::swap(m_capacity, rhs.m_capacity);
      rde::swap(m_capacityMask, rhs.m_capacityMask);
      rde::swap(m_numUsed, rhs.m_numUsed);
      rde::swap(m_hashFunc, rhs.m_hashFunc);
      rde::swap(m_keyEqualFunc, rhs.m_keyEqualFunc);
      RDE_ASSERT(invariant());
    }
  }

  rde::pair<iterator, bool> insert(const value_type& v)
  {
    typedef rde::pair<iterator, bool> ret_type_t;
    RDE_ASSERT(invariant());
    if (m_numUsed * TLoadFactor4 >= m_capacity * 4)
      grow();

    hash_value_t hash = 0XFFFFFFFF;

    node* n = find_for_insert(v.first, &hash);
    if (n->is_occupied())
    {
      RDE_ASSERT(hash == n->hash && m_keyEqualFunc(v.first, n->data.first));
      return ret_type_t(iterator(n, this), false);
    }
    if (n->is_unused())
      ++m_numUsed;
    rde::copy_construct(&n->data, v);
        n->hash = hash;
        ++m_size;
    RDE_ASSERT(invariant());
        return ret_type_t(iterator(n, this), true);
  }

  size_type erase(const key_type& key)
    {
    node* n = lookup(key);
        if (n != (m_nodes + m_capacity) && n->is_occupied())
        {
      erase_node(n);
            return 1;
    }
    return 0;
  }
    void erase(iterator it)
    {
    RDE_ASSERT(it.get_map() == this);
        if (it != end())
        {
      RDE_ASSERT(!empty());
            erase_node(it.node());
    }
  }
  void erase(iterator from, iterator to)
  {
    for (; from != to; ++from)
        {
      node* n = from.node();
            if (n->is_occupied())
        erase_node(n);
    }
  }

  iterator find(const key_type& key)
    {
    node* n = lookup(key);
        return iterator(n, this);
  }
  const_iterator find(const key_type& key) const
  {
    const node* n = lookup(key);
    return const_iterator(n, this);
  }

  void clear()
    {
    node* endNode = m_nodes + m_capacity;
        for (node* iter = m_nodes; iter != endNode; ++iter)
        {
            if( iter )
            {
                if (iter->is_occupied())
                {
                    rde::destruct(&iter->data);
                }
                // We can make them unused, because we clear whole hash_map,
                // so we can guarantee there'll be no holes.
                iter->hash = node::kUnusedHash;
            }
    }
        m_size = 0;
        m_numUsed = 0;
  }

  // More like reserve.
  // resize() name chosen for compatibility sake.
  void reserve(size_type min_size)
  {
    size_type newCapacity = (m_capacity == 0 ? kInitialCapacity : m_capacity);
    while (newCapacity < min_size)
      newCapacity *= 2;
    if (newCapacity > m_capacity)
      grow(newCapacity);
  }

  size_type bucket_count() const      { return m_capacity; }
  size_type size() const          { return m_size; }
  size_type empty() const         { return size() == 0; }
  size_type nonempty_bucket_count() const { return m_numUsed; }
  size_type used_memory() const
  {
    return bucket_count() * kNodeSize;
  }

  const allocator_type& get_allocator() const { return m_allocator; }
  void set_allocator(const allocator_type& allocator)
  {
    m_allocator = allocator;
  }

private:
  void grow()
  {
    const int newCapacity = (m_capacity == 0 ? kInitialCapacity : m_capacity * 2);
    grow(newCapacity);
  }
  void grow(int new_capacity)
  {
    RDE_ASSERT((new_capacity & (new_capacity - 1)) == 0); // Must be power-of-two
    node* newNodes = allocate_nodes(new_capacity);
    rehash(new_capacity, newNodes, m_capacity, m_nodes, true);
    if (m_nodes != &ms_emptyNode)
      m_allocator.deallocate(m_nodes, sizeof(node) * m_capacity);
    m_capacity = new_capacity;
    m_capacityMask = new_capacity - 1;
    m_nodes = newNodes;
    m_numUsed = m_size;
    RDE_ASSERT(m_numUsed < m_capacity);
   }
  rde::pair<iterator, bool> insert_at(const value_type& v, node* n,
    hash_value_t hash)
  {
    RDE_ASSERT(invariant());
    if (n == 0 || m_numUsed * TLoadFactor4 >= m_capacity * 4)
      return insert(v);

    RDE_ASSERT(!n->is_occupied());
    if (n->is_unused())
      ++m_numUsed;
    rde::copy_construct(&n->data, v);
    n->hash = hash;
    ++m_size;
    RDE_ASSERT(invariant());
    return rde::pair<iterator, bool>(iterator(n, this), true);
  }
  node* find_for_insert(const key_type& key, hash_value_t* out_hash)
  {
    if (m_capacity == 0)
      return 0;

    const hash_value_t hash = hash_func(key);
        *out_hash = hash;
        uint32 i = hash & m_capacityMask;

        node* n = m_nodes + i;
    if (n->hash == hash && m_keyEqualFunc(key, n->data.first))
      return n;

        node* freeNode(0);
        if (n->is_deleted())
      freeNode = n;
    uint32 numProbes(0);
        // Guarantees loop termination.
        RDE_ASSERT(m_numUsed < m_capacity);
        while (!n->is_unused())
        {
      ++numProbes;
            i = (i + numProbes) & m_capacityMask;
            n = m_nodes + i;
      if (compare_key(n, key, hash))
        return n;
            if (n->is_deleted() && freeNode == 0)
        freeNode = n;
    }
        return freeNode ? freeNode : n;
  }
  node* lookup(const key_type& key) const
  {
    const hash_value_t hash = hash_func(key);
        uint32 i = hash & m_capacityMask;
        node* n = m_nodes + i;
    // In theory, we could try to use compare_key here, it would
    // be a little bit faster for keys with cheap_compare. However, if keys are
    // not totally destroyed on removal (erase_node), this could result in returning
    // unused nodes. By testing hashes - we make sure it does not happen.
    // This could also be solved by doing what Google does -- set_empty_key/set_deleted_key,
    // but for the time being it doesn't look to me like it's worth it.
    if (n->hash == hash && m_keyEqualFunc(key, n->data.first))
      return n;

    uint32 numProbes(0);
        // Guarantees loop termination.
        RDE_ASSERT(m_capacity == 0 || m_numUsed < m_capacity);
        while (!n->is_unused())
        {
      ++numProbes;
            i = (i + numProbes) & m_capacityMask;
            n = m_nodes + i;

      if (compare_key(n, key, hash))
        return n;
    }
    return m_nodes + m_capacity;
  }

  static void rehash(int new_capacity, node* new_nodes,
    int capacity, const node* nodes, bool destruct_original)
  {
        //if (nodes == &ms_emptyNode || new_nodes == &ms_emptyNode)
          //  return;

    const node* it = nodes;
    const node* itEnd = nodes + capacity;
    const uint32 mask = new_capacity - 1;
    while (it != itEnd)
    {
      if (it->is_occupied())
      {
        const hash_value_t hash = it->hash;
        uint32 i = hash & mask;

        node* n = new_nodes + i;
        uint32 numProbes(0);
        while (!n->is_unused())
        {
          ++numProbes;
          i = (i + numProbes) & mask;
          n = new_nodes + i;
        }
        rde::copy_construct(&n->data, it->data);
        n->hash = hash;
        if (destruct_original)
          rde::destruct(&it->data);
      }
      ++it;
    }
  }

  node* allocate_nodes(int n)
  {
    node* buckets = static_cast<node*>(m_allocator.allocate(n * sizeof(node)));
        node* iterBuckets(buckets);
        node* end = iterBuckets + n;
        for (; iterBuckets != end; ++iterBuckets)
      iterBuckets->hash = node::kUnusedHash;

    return buckets;
  }
  void delete_nodes()
  {
    node* it = m_nodes;
        node* itEnd = it + m_capacity;
        while (it != itEnd)
        {
      if (it && it->is_occupied())
        rde::destruct(&it->data);
      ++it;
    }
    if (m_nodes != &ms_emptyNode)
      m_allocator.deallocate(m_nodes, sizeof(node) * m_capacity);

        m_capacity = 0;
    m_capacityMask = 0;
        m_size = 0;
  }
  void erase_node(node* n)
  {
    RDE_ASSERT(!empty());
        RDE_ASSERT(n->is_occupied());
        rde::destruct(&n->data);
        n->hash = node::kDeletedHash;
    --m_size;
  }

  RDE_FORCEINLINE hash_value_t hash_func(const key_type& key) const
  {
    const hash_value_t h = m_hashFunc(key) & 0xFFFFFFFD;
    //RDE_ASSERT(h < node::kDeletedHash);
        return h;
  }
  bool invariant() const
  {
    RDE_ASSERT((m_capacity & (m_capacity - 1)) == 0);
    RDE_ASSERT(m_numUsed >= m_size);
    return true;
  }

  RDE_FORCEINLINE bool compare_key(const node* n, const key_type& key, hash_value_t hash,
    int_to_type<false>) const
  {
    return (n->hash == hash && m_keyEqualFunc(key, n->data.first));
  }
  RDE_FORCEINLINE bool compare_key(const node* n, const key_type& key, hash_value_t,
    int_to_type<true>) const
  {
    return m_keyEqualFunc(key, n->data.first);
  }
  RDE_FORCEINLINE bool compare_key(const node* n, const key_type& key, hash_value_t hash) const
  {
    return compare_key(n, key, hash, int_to_type<has_cheap_compare<TKey>::value>());
  }

  node*     m_nodes;
  int       m_size;
  int       m_capacity;
  uint32      m_capacityMask;
  int       m_numUsed;
  THashFunc       m_hashFunc;
  TKeyEqualFunc m_keyEqualFunc;
  TAllocator      m_allocator;

  static node   ms_emptyNode;
};


// Holy ...
template<typename TKey, typename TValue,
    class THashFunc,
    int TLoadFactor4,
    class TKeyEqualFunc,
    class TAllocator>
typename hash_map<TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator>::node hash_map<TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator>::ms_emptyNode;

}

#endif