indexed_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_INDEXED_SET_H
#define MCRL2_UTILITIES_INDEXED_SET_H
 
#include <deque>
#include <mutex>
 
#include "mcrl2/utilities/unordered_map.h"
#include "mcrl2/utilities/unused.h"
#include "mcrl2/utilities/detail/atomic_wrapper.h"
#include "mcrl2/utilities/shared_mutex.h"
 
namespace mcrl2
{
namespace utilities
{
 
template<typename Key,
         bool ThreadSafe = false,
         typename Hash = std::hash<Key>,
         typename Equals = std::equal_to<Key>,
         typename Allocator = std::allocator<Key>,
         typename KeyTable = std::deque< Key, Allocator > > 
class indexed_set
{
private:
  std::vector<detail::atomic_wrapper<std::size_t>> m_hashtable;
  KeyTable m_keys;
 
  mutable std::shared_ptr<std::mutex> m_mutex;
  mutable std::vector<shared_mutex> m_shared_mutexes;
 
  //  has not yet been used. This allows to increase m_keys in 
  //  large steps, avoiding exclusive access too often.  
  detail::atomic_wrapper<size_t> m_next_index;
 
  Hash m_hasher;
  Equals m_equals;
 
  void reserve_indices(std::size_t thread_index);
 
  std::size_t put_in_hashtable(const Key& key, std::size_t value, std::size_t& new_position);
 
  inline void resize_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 KeyTable::iterator iterator;
  typedef typename KeyTable::const_iterator const_iterator;
 
  typedef typename KeyTable::reverse_iterator reverse_iterator;
  typedef typename KeyTable::const_reverse_iterator const_reverse_iterator;
 
  typedef std::ptrdiff_t difference_type;
  
  static constexpr size_type npos = std::numeric_limits<std::size_t>::max();
 
  indexed_set();
 
  indexed_set(std::size_t number_of_threads);
 
  indexed_set(
    std::size_t number_of_threads, 
    std::size_t initial_hashtable_size, 
    const hasher& hash = hasher(),
    const key_equal& equals = key_equal());
 
  size_type index(const key_type& key, std::size_t thread_index = 0) const;
 
  const key_type& at(const size_type index) const;
 
  const key_type& operator[](const size_type index) const;
 
  iterator begin(std::size_t thread_index = 0) 
  { 
    shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
    iterator i = m_keys.begin();
    return i;
  }
 
  iterator end(std::size_t thread_index = 0)
  { 
    shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
    iterator i = m_keys.begin()+m_next_index;
    return i;
  }
 
  const_iterator begin(std::size_t thread_index = 0) const
  {
    shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
    const_iterator i = m_keys.begin();
    return i;
  }
 
  const_iterator end(std::size_t thread_index = 0) const
  {
    shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
    const_iterator i = m_keys.begin()+m_next_index;
    return i;
  }
 
  const_iterator cbegin(std::size_t thread_index = 0) const
  { 
    shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
    const_iterator i = m_keys.begin();
    return i;
  }
 
  const_iterator cend(std::size_t thread_index = 0) const 
  { 
    shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
    const_iterator i = m_keys.cbegin() + m_next_index;
    return i;
  }
 
  reverse_iterator rbegin(std::size_t thread_index = 0) 
  { 
    shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
    reverse_iterator i = m_keys.rend() - m_next_index;
    return i;
  }
 
  reverse_iterator rend(std::size_t thread_index = 0)
  { 
    shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
    reverse_iterator i = m_keys.rend();
    return i;
  }
 
  const_reverse_iterator crbegin(std::size_t thread_index = 0) const
  { 
    shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
    const_reverse_iterator i=m_keys.crend() - m_next_index;
    return i;
  }
 
  const_reverse_iterator crend(std::size_t thread_index = 0) const 
  { 
    shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
    reverse_iterator i = m_keys.crend();
    return i;
  }
 
  void clear(std::size_t thread_index=0);
 
  std::pair<size_type, bool> insert(const key_type& key, std::size_t thread_index = 0);
 
  const_iterator find(const key_type& key, std::size_t thread_index = 0) const;
 
  size_type size(std::size_t thread_index = 0) const
  { 
    shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
    size_type result=m_next_index;
    return result;
  }
};
 
} // end namespace utilities
} // end namespace mcrl2
 
#include "mcrl2/utilities/detail/indexed_set.h"
 
 
#endif // MCRL2_UTILITIES_INDEXED_SET_H