Line data    Source code

       1             : // Author(s): Maurice Laveaux
       2             : // Copyright: see the accompanying file COPYING or copy at
       3             : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
       4             : //
       5             : // Distributed under the Boost Software License, Version 1.0.
       6             : // (See accompanying file LICENSE_1_0.txt or copy at
       7             : // http://www.boost.org/LICENSE_1_0.txt)
       8             : 
       9             : #ifndef MCRL2_UTILITIES_INDEXED_SET_H
      10             : #define MCRL2_UTILITIES_INDEXED_SET_H
      11             : 
      12             : #include <deque>
      13             : #include <mutex>
      14             : 
      15             : #include "mcrl2/utilities/unordered_map.h"
      16             : #include "mcrl2/utilities/unused.h"
      17             : #include "mcrl2/utilities/detail/atomic_wrapper.h"
      18             : #include "mcrl2/utilities/shared_mutex.h"
      19             : 
      20             : namespace mcrl2
      21             : {
      22             : namespace utilities
      23             : {
      24             : 
      25             : /// \brief A set that assigns each element an unique index.
      26             : template<typename Key,
      27             :          bool ThreadSafe = false,
      28             :          typename Hash = std::hash<Key>,
      29             :          typename Equals = std::equal_to<Key>,
      30             :          typename Allocator = std::allocator<Key>,
      31             :          typename KeyTable = std::deque< Key, Allocator > > 
      32             : class indexed_set
      33             : {
      34             : private:
      35             :   std::vector<detail::atomic_wrapper<std::size_t>> m_hashtable;
      36             :   KeyTable m_keys;
      37             : 
      38             :   /// \brief Mutex for the m_hashtable and m_keys data structures.
      39             :   mutable std::shared_ptr<std::mutex> m_mutex;
      40             :   mutable std::vector<shared_mutex> m_shared_mutexes;
      41             : 
      42             :   /// m_next_index indicates the next index that 
      43             :   //  has not yet been used. This allows to increase m_keys in 
      44             :   //  large steps, avoiding exclusive access too often.  
      45             :   detail::atomic_wrapper<size_t> m_next_index;
      46             : 
      47             :   Hash m_hasher;
      48             :   Equals m_equals;
      49             : 
      50             :   /// \brief Reserve indices that can be used. Doing this 
      51             :   ///        infrequently prevents obtaining an exclusive lock for the
      52             :   ///        indexed set too often. This operation requires a
      53             :   ///        resize of m_keys. 
      54             :   void reserve_indices(std::size_t thread_index);
      55             : 
      56             :   /// \brief Inserts the given (key, n) pair into the indexed set.
      57             :   std::size_t put_in_hashtable(const Key& key, std::size_t value, std::size_t& new_position);
      58             : 
      59             :   /// \brief Resizes the hash table to twice its current size.
      60             :   inline void resize_hashtable();
      61             : 
      62             : public:
      63             :   typedef Key key_type;
      64             :   typedef std::size_t size_type;
      65             :   typedef std::pair<const key_type, size_type> value_type;
      66             :   typedef Equals key_equal;
      67             :   typedef Hash hasher;
      68             : 
      69             :   typedef value_type& reference;
      70             :   typedef const value_type& const_reference;
      71             :   typedef value_type* pointer;
      72             :   typedef const value_type* const_pointer;
      73             : 
      74             :   typedef typename KeyTable::iterator iterator;
      75             :   typedef typename KeyTable::const_iterator const_iterator;
      76             : 
      77             :   typedef typename KeyTable::reverse_iterator reverse_iterator;
      78             :   typedef typename KeyTable::const_reverse_iterator const_reverse_iterator;
      79             : 
      80             :   typedef std::ptrdiff_t difference_type;
      81             :   
      82             :   /// \brief Value returned when an element does not exist in the set.
      83             :   /// \return Value indicating non existing element, equal to std::numeric_limits<std::size_t>::max(). 
      84             :   static constexpr size_type npos = std::numeric_limits<std::size_t>::max();
      85             : 
      86             :   /// \brief Constructor of an empty indexed set. Starts with a hashtable of size 128 and assumes one single thread.
      87             :   indexed_set();
      88             : 
      89             :   /// \brief Constructor of an empty indexed set. 
      90             :   /// \details With a single thread it delivers contiguous values for states.
      91             :   ///          With multiple threads some indices may be skipped. Each thread
      92             :   ///          reserves numbers, which it hands out. If a thread does not have
      93             :   ///          the opportunity to hand out all numbers, holes in the contiguous
      94             :   ///          numbering can occur. The holes are always of limited size. 
      95             :   /// \param number_of_threads The number of threads that use this index set. If the number is 1, it is treated
      96             :   ///        as a sequential set. If this number is larger than 1, the threads must be numbered
      97             :   ///        from 1 up and including number_of_threads. The number 0 cannot be used in that case. 
      98             :   indexed_set(std::size_t number_of_threads);
      99             : 
     100             :   /// \brief Constructor of an empty index set. Starts with a hashtable of the indicated size. 
     101             :   /// \details With one thread the numbering is contiguous. With multiple threads limited size holes
     102             :   ///          can occur in the numbering. 
     103             :   /// \param number_of_threads The number of threads that use this index set. This number is either 1, and then the implementation 
     104             :   ///        assumes that the thread has number 0, or it is larger than 1, and it is assumed that threads are numbered from 1 upwards. 
     105             :   /// \param initial_hashtable_size The initial size of the hashtable.
     106             :   /// \param hash The hash function.
     107             :   /// \param equals The comparison function for its elements.
     108             :   indexed_set(
     109             :     std::size_t number_of_threads, 
     110             :     std::size_t initial_hashtable_size, 
     111             :     const hasher& hash = hasher(),
     112             :     const key_equal& equals = key_equal());
     113             : 
     114             :   /// \brief Returns a reference to the mapped value.
     115             :   /// \details Returns an invalid value, larger or equal than the size of the indexed set, if there is no element with the given key.
     116             :   size_type index(const key_type& key, std::size_t thread_index = 0) const;
     117             : 
     118             :   /// \brief Returns a reference to the mapped value.
     119             :   /// \details Returns an out_of_range exception if there is no element with the given key.
     120             :   /// \param index The position in the indexed set.
     121             :   /// \return The value at position index.
     122             :   const key_type& at(const size_type index) const;
     123             : 
     124             :   /// \brief Operator that provides a const reference at the position indicated by index.
     125             :   /// \param index The position in the indexed set.
     126             :   /// \return The value at position index.
     127             :   /// \threadsafe
     128             :   const key_type& operator[](const size_type index) const;
     129             : 
     130             :   /// \brief Forward iterator which runs through the elements from the lowest to the largest number.
     131             :   /// \details Complexity is constant per operation.
     132             :   iterator begin(std::size_t thread_index = 0) 
     133             :   { 
     134             :     shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
     135             :     iterator i = m_keys.begin();
     136             :     return i;
     137             :   }
     138             : 
     139             :   /// \brief End of the forward iterator.
     140           4 :   iterator end(std::size_t thread_index = 0)
     141             :   { 
     142           4 :     shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
     143           4 :     iterator i = m_keys.begin()+m_next_index;
     144           8 :     return i;
     145           4 :   }
     146             : 
     147             :   /// \brief Forward iterator which runs through the elements from the lowest to the largest number.
     148             :   /// \details Complexity is constant per operation.
     149        2231 :   const_iterator begin(std::size_t thread_index = 0) const
     150             :   {
     151        2231 :     shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
     152        2231 :     const_iterator i = m_keys.begin();
     153        4462 :     return i;
     154        2231 :   }
     155             : 
     156             :   /// \brief End of the forward iterator.
     157        9239 :   const_iterator end(std::size_t thread_index = 0) const
     158             :   {
     159        9239 :     shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
     160        9239 :     const_iterator i = m_keys.begin()+m_next_index;
     161       18478 :     return i;
     162        9239 :   }
     163             : 
     164             :   /// \brief const_iterator going through the elements in the set numbered from zero upwards. 
     165             :   const_iterator cbegin(std::size_t thread_index = 0) const
     166             :   { 
     167             :     shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
     168             :     const_iterator i = m_keys.begin();
     169             :     return i;
     170             :   }
     171             : 
     172             :   /// \brief End of the forward const_iterator. 
     173             :   const_iterator cend(std::size_t thread_index = 0) const 
     174             :   { 
     175             :     shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
     176             :     const_iterator i = m_keys.cbegin() + m_next_index;
     177             :     return i;
     178             :   }
     179             : 
     180             :   /// \brief Reverse iterator going through the elements in the set from the largest to the smallest index. 
     181             :   reverse_iterator rbegin(std::size_t thread_index = 0) 
     182             :   { 
     183             :     shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
     184             :     reverse_iterator i = m_keys.rend() - m_next_index;
     185             :     return i;
     186             :   }
     187             : 
     188             :   /// \brief End of the reverse iterator. 
     189             :   reverse_iterator rend(std::size_t thread_index = 0)
     190             :   { 
     191             :     shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
     192             :     reverse_iterator i = m_keys.rend();
     193             :     return i;
     194             :   }
     195             : 
     196             :   /// \brief Reverse const_iterator going through the elements from the highest to the lowest numbered element. 
     197             :   const_reverse_iterator crbegin(std::size_t thread_index = 0) const
     198             :   { 
     199             :     shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
     200             :     const_reverse_iterator i=m_keys.crend() - m_next_index;
     201             :     return i;
     202             :   }
     203             : 
     204             :   /// \brief End of the reverse const_iterator. 
     205             :   const_reverse_iterator crend(std::size_t thread_index = 0) const 
     206             :   { 
     207             :     shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
     208             :     reverse_iterator i = m_keys.crend();
     209             :     return i;
     210             :   }
     211             : 
     212             :   /// \brief Clears the indexed set by removing all its elements. It is not guaranteed that the memory is released too. 
     213             :   void clear(std::size_t thread_index=0);
     214             : 
     215             :   /// \brief Insert a key in the indexed set and return its index. 
     216             :   /// \details If the element was already in the set, the resulting bool is true, and the existing index is returned.
     217             :   ///         Otherwise, the key is inserted in the set, and the next available index is assigned to it. 
     218             :   /// \param  key The key to be inserted in the set.
     219             :   /// \return The index of the key and a boolean indicating whether the element was actually inserted.
     220             :   /// \details threadsafe
     221             :   std::pair<size_type, bool> insert(const key_type& key, std::size_t thread_index = 0);
     222             : 
     223             :   /// \brief Provides an iterator to the stored key in the indexed set.
     224             :   /// \param key The key that is sought.
     225             :   /// \return An iterator to the key, otherwise end().
     226             :   const_iterator find(const key_type& key, std::size_t thread_index = 0) const;
     227             : 
     228             :   /// \brief The number of elements in the indexed set.
     229             :   /// \return The number of elements in the indexed set. 
     230             :   /// \details threadsafe
     231       93379 :   size_type size(std::size_t thread_index = 0) const
     232             :   { 
     233       93379 :     shared_guard guard = m_shared_mutexes[thread_index].lock_shared();
     234       93379 :     size_type result=m_next_index;
     235       93379 :     return result;
     236       93379 :   }
     237             : };
     238             : 
     239             : } // end namespace utilities
     240             : } // end namespace mcrl2
     241             : 
     242             : #include "mcrl2/utilities/detail/indexed_set.h"
     243             : 
     244             : 
     245             : #endif // MCRL2_UTILITIES_INDEXED_SET_H