unordered_set.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_UNORDERED_SET_H
#define MCRL2_UTILITIES_UNORDERED_SET_H
 
#include "mcrl2/utilities/block_allocator.h"
#include "mcrl2/utilities/logger.h"
#include "mcrl2/utilities/detail/bucket_list.h"
 
#include <cmath>
#include <mutex>
#include <vector>
 
namespace mcrl2::utilities
{
 
constexpr static bool EnableLockfreeInsertion = true;
 
constexpr static long BucketsPerMutex = 256;
 
template<typename T>
void print_performance_statistics(const T& unordered_set);
 
// Forward declaration of an unordered_map.
template<typename Key,
         typename T,
         typename Hash = std::hash<Key>,
         typename KeyEqual = std::equal_to<Key>,
         typename Allocator = std::allocator<Key>,
         bool ThreadSafe = false,
         bool Resize = true>
class unordered_map;
 
namespace detail
{
  // Check for the existence of the is_transparent type.
  template <typename...> using void_t = void;
 
  template <typename X, typename = void> struct is_transparent : std::false_type
  {};
 
  template <typename X>
  struct is_transparent<X, void_t<typename X::is_transparent>> : std::true_type
  {};
} // namespace detail
 
 
template<typename Key,
         typename Hash = std::hash<Key>,
         typename Equals = std::equal_to<Key>,
         typename Allocator = std::allocator<Key>,
         bool ThreadSafe = false,
         bool Resize = true>
class unordered_set
{
  static_assert (!(ThreadSafe && Resize), "ThreadSafe cannot be enabled together with automatic resizing.");
 
private:
  using bucket_type = detail::bucket_list<Key, Allocator>;
  using bucket_iterator = typename std::vector<bucket_type>::iterator;
  using const_bucket_iterator = typename std::vector<bucket_type>::const_iterator;
  using mutex_type = std::mutex;
 
  template<typename Key_, typename T, typename Hash_, typename KeyEqual, typename Allocator_, bool ThreadSafe_, bool Resize_>
  friend class unordered_map;
 
public:
  template<typename Bucket, bool Constant>
  class unordered_set_iterator : std::iterator_traits<Key>
  {
  private:
    friend class unordered_set;
 
    template<typename Key_, typename T, typename Hash_, typename KeyEqual, typename Allocator_, bool ThreadSafe_, bool Resize_>
    friend class unordered_map;
 
    using bucket_it = typename std::vector<Bucket>::const_iterator;
    using key_it_type = typename Bucket::const_iterator;
 
  public:
    using value_type = Key;
    using reference = typename std::conditional<Constant, const Key&, Key&>::type;
    using pointer = typename std::conditional<Constant, const Key*, Key*>::type;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::forward_iterator_tag;
 
    unordered_set_iterator() = default;
 
    operator unordered_set_iterator<Bucket, true>() const
    {
      return unordered_set_iterator<Bucket, true>(m_bucket_it, m_bucket_end, m_key_before_it, m_key_it);
    }
 
    unordered_set_iterator& operator++()
    {
      ++m_key_before_it;
      ++m_key_it;
      goto_next_bucket();
      return *this;
    }
 
    unordered_set_iterator operator++(int)
    {
      unordered_set_iterator copy(*this);
      ++(*this);
      return *copy;
    }
 
    reference operator*() const
    {
      return const_cast<reference>(*m_key_it);
    }
 
    pointer operator->() const
    {
      return const_cast<pointer>(&(*m_key_it));
    }
 
    bool operator!=(const unordered_set_iterator& other) const
    {
      return m_key_it != other.m_key_it || m_bucket_it != other.m_bucket_it;
    }
 
    bool operator==(const unordered_set_iterator& other) const
    {
      return !(*this != other);
    }
 
  private:
    unordered_set_iterator(bucket_it it, bucket_it end, key_it_type before_it, key_it_type key) :
      m_bucket_it(it), m_bucket_end(end), m_key_before_it(before_it), m_key_it(key)
    {}
 
    unordered_set_iterator(bucket_it it, bucket_it end) :
      m_bucket_it(it), m_bucket_end(end), m_key_before_it((*it).before_begin()), m_key_it((*it).begin())
    {
      goto_next_bucket();
    }
 
    explicit unordered_set_iterator(bucket_it it) :
      m_bucket_it(it)
    {}
 
    operator unordered_set_iterator<Bucket, false>() const
    {
      return unordered_set_iterator<Bucket, false>(m_bucket_it, m_bucket_end, m_key_before_it, m_key_it);
    }
 
    key_it_type& key_before_it() { return m_key_before_it; }
 
    key_it_type& key_it() { return m_key_it; }
 
    bucket_it& get_bucket_it() { return m_bucket_it; }
 
    void goto_next_bucket()
    {
      // Find the first bucket that is not empty.
      while(!(m_key_it != detail::EndIterator))
      {
        // Take the next bucket and reset the key iterator.
        ++m_bucket_it;
 
        if (m_bucket_it != m_bucket_end)
        {
          m_key_it = (*m_bucket_it).begin();
          m_key_before_it = (*m_bucket_it).before_begin();
        }
        else
        {
          // Reached the end of the buckets.
          break;
        }
      }
 
      // The current bucket contains elements or we are at the end.
      assert(m_bucket_it == m_bucket_end || m_key_it != detail::EndIterator);
    }
 
    bucket_it m_bucket_it;
    bucket_it m_bucket_end;
    key_it_type m_key_before_it;
    key_it_type m_key_it; // Invariant: m_key_it != EndIterator.
  };
 
  using key_type = Key;
  using value_type = Key;
  using hasher = Hash;
  using key_equal = Equals;
  using allocator_type = typename bucket_type::NodeAllocator;
 
  using reference = value_type&;
  using const_reference = const value_type&;
  using pointer = typename std::allocator_traits<Allocator>::pointer;
  using const_pointer = typename std::allocator_traits<Allocator>::const_pointer;
 
  using const_local_iterator = typename bucket_type::const_iterator;
  using local_iterator = typename bucket_type::const_iterator;
  using const_iterator = unordered_set_iterator<bucket_type, true>;
  using iterator = const_iterator;
 
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;
 
  unordered_set() { rehash(0); }
 
  explicit unordered_set(size_type bucket_count,
    const hasher& hash = hasher(),
    const key_equal& equals = key_equal())
    : m_hash(hash),
      m_equals(equals)
  {
    rehash(bucket_count);
  }
 
  // Copy operators.
  unordered_set(const unordered_set& set);
  unordered_set& operator=(const unordered_set& set);
 
  // Default move operators.
  unordered_set(unordered_set&& other) = default;
  unordered_set& operator=(unordered_set&& other) = default;
 
  ~unordered_set();
 
  const allocator_type& get_allocator() const noexcept { return m_allocator; }
  allocator_type& get_allocator() noexcept { return m_allocator; }
 
  iterator begin() { return iterator(m_buckets.begin(), m_buckets.end()); }
  iterator end() { return iterator(m_buckets.end()); }
 
  const_iterator begin() const { return const_iterator(m_buckets.begin(), m_buckets.end()); }
  const_iterator end() const { return const_iterator(m_buckets.end()); }
 
  const_iterator cbegin() const { return const_iterator(m_buckets.begin(), m_buckets.end()); }
  const_iterator cend() const { return const_iterator(m_buckets.end()); }
 
  bool empty() const noexcept { return size() == 0; }
 
  size_type size() const noexcept { return m_number_of_elements; }
  size_type max_size() const noexcept { return m_buckets.max_size(); }
 
  void clear();
 
  template<typename ...Args>
  std::pair<iterator, bool> emplace(Args&&... args);
 
  template<typename...Args>
  void erase(const Args&... args);
 
  iterator erase(const_iterator it);
 
  template<typename ...Args>
  size_type count(const Args&... args) const;
 
  template<typename...Args>
  const_iterator find(const Args&... args) const;
 
  template<typename...Args>
  iterator find(const Args&... args);
 
  local_iterator begin(size_type n) { return m_buckets[n].begin(); }
  local_iterator end(size_type n) { return m_buckets[n].end(); }
 
  const_local_iterator begin(size_type n) const { return m_buckets[n].begin(); }
  const_local_iterator end(size_type n) const { return m_buckets[n].end(); }
 
  const_local_iterator cbegin(size_type n) const { return m_buckets[n].begin(); }
  const_local_iterator cend(size_type n) const { return m_buckets[n].end(); }
 
  size_type bucket_count() const noexcept { return m_buckets_mask + 1; }
  size_type max_bucket_count() const noexcept { return m_buckets.max_size(); }
 
  size_type bucket_size(size_type n) const noexcept { return std::distance(m_buckets[n].begin(), m_buckets[n].end()); }
  size_type bucket(const key_type& key) const noexcept { return std::distance(m_buckets.begin(), find_bucket_index(key)); }
 
  float load_factor() const { return static_cast<float>(size()) / bucket_count(); }
  float max_load_factor() const { return m_max_load_factor; }
  void max_load_factor(float factor) { m_max_load_factor = factor; }
 
  void rehash(size_type number_of_buckets);
 
  void reserve(size_type count) { rehash(static_cast<std::size_t>(std::ceil(static_cast<float>(count) / max_load_factor()))); }
 
  hasher hash_function() const { return m_hash; }
  key_equal key_eq() const { return m_equals; }
 
  size_type capacity() const noexcept { return m_buckets.size(); }
 
  void rehash_if_needed();
 
private:
  template<typename Key_, typename T, typename Hash_, typename KeyEqual, typename Allocator_, bool ThreadSafe_, bool Resize_>
  friend class unordered_map;
 
  template<typename ...Args>
  std::pair<iterator, bool> emplace_impl(size_type bucket_index, Args&&... args);
 
  template<typename ...Args>
  void erase_impl(const Args&... args);
 
  template<typename ...Args>
  size_type find_bucket_index(const Args&... args) const;
 
  template<typename ...Args>
  const_iterator find_impl(size_type bucket_index, const Args&... args) const;
 
  static constexpr bool allow_transparent = detail::is_transparent<Hash>() && detail::is_transparent<Equals>();
 
  std::conditional_t<ThreadSafe, std::atomic<size_type>, size_type> m_number_of_elements = 0;
 
  std::conditional_t<ThreadSafe, std::atomic<size_type>, size_type> m_buckets_mask = 0;
 
  std::vector<bucket_type> m_buckets;
  std::vector<std::mutex> m_bucket_mutexes;
 
  float m_max_load_factor = 1.0f;
 
  hasher m_hash = hasher();
  key_equal m_equals = key_equal();
  allocator_type m_allocator;
};
 
template<typename Key,
         typename Hash = std::hash<Key>,
         typename Equals = std::equal_to<Key>,
         typename Allocator = mcrl2::utilities::block_allocator<Key>,
         bool ThreadSafe = false>
using unordered_set_large = unordered_set<Key, Hash, Equals, Allocator, ThreadSafe>;
 
} // namespace mcrl2::utilities
 
#include "mcrl2/utilities/detail/unordered_set_implementation.h"
 
#endif // MCRL2_UTILITIES_UNORDERED_SET_H