hashtable.h

Go to the documentation of this file.

// Author(s): Maurice Laveaux
// Copyright: see the accompanying file COPYING or copy at
// https://github.com/mCRL2org/mCRL2/blob/master/COPYING
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
 
#ifndef MCRL2_UTILITIES_HASHTABLE_H
#define MCRL2_UTILITIES_HASHTABLE_H
 
#include <vector>
 
#include "mcrl2/utilities/unordered_map.h"
 
namespace mcrl2
{
namespace utilities
{
 
template<typename Key,
         typename Hash = std::hash<Key>,
         typename Equals = std::equal_to<Key>,
         typename Allocator = std::allocator<Key>>
class hashtable
{
public:
  typedef Key key_type;
  typedef std::size_t size_type;
  typedef std::pair<const key_type, size_type> value_type;
  typedef Equals key_equal;
  typedef Hash hasher;
 
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
 
  typedef typename std::vector < Key >::iterator iterator;
  typedef typename std::vector < Key >::const_iterator const_iterator;
 
  typedef typename std::vector < Key >::reverse_iterator reverse_iterator;
  typedef typename std::vector < Key >::const_reverse_iterator const_reverse_iterator;
 
  typedef std::ptrdiff_t difference_type;
 
  hashtable();
 
  hashtable(std::size_t initial_hashtable_size,
    const hasher& hash = hasher(),
    const key_equal& equals = key_equal());
 
  iterator begin() 
  { 
    return m_hashtable.begin();
  }
 
  iterator end()
  { 
    return m_hashtable.end();
  }
 
  iterator begin() const
  {
    return m_hashtable.begin();
  }
 
  iterator end() const
  {
    return m_hashtable.end();
  }
 
  const_iterator cbegin() const
  { 
    return m_hashtable.cbegin();
  }
 
  const_iterator cend() const 
  { 
    return m_hashtable.cend();
  }
 
  iterator rbegin() 
  { 
    return m_hashtable.rbegin();
  }
 
  iterator rend()
  { 
    return m_hashtable.rend();
  }
 
  const_iterator crbegin() const
  { 
    return m_hashtable.crbegin();
  }
 
  const_iterator crend() const 
  { 
    return m_hashtable.crend();
  }
 
  void clear();
 
  std::pair<iterator, bool> insert(const key_type& key);
 
  iterator erase(const key_type& key);
 
  iterator find(const key_type& key);
 
  size_type size() const
  { 
    return m_number_of_elements;
  }
 
  bool must_resize();
 
  void resize();
 
 
private:
  std::size_t get_index(const key_type& key);
 
  std::vector<Key> m_hashtable;
 
  Hash m_hasher;
  Equals m_equals;
 
  std::size_t m_number_of_elements = 0;
 
  size_type m_buckets_mask;
 
  inline void rehash(std::size_t size);
};
 
} // end namespace utilities
} // end namespace mcrl2
 
#include "mcrl2/utilities/detail/hashtable.h"
 
 
#endif // MCRL2_UTILITIES_HASHTABLE_H