mcrl2::utilities::indexed_set =============================================================================== Include file: .. code-block:: c++ #include "mcrl2/utilities/indexed_set.h .. cpp:class:: mcrl2::utilities::indexed_set A set that assigns each element an unique index. Public types ------------------------------------------------------------------------------- .. cpp:type:: mcrl2::utilities::indexed_set::const_iterator typedef for :cpp:type:`KeyTable::const_iterator` .. cpp:type:: mcrl2::utilities::indexed_set::const_pointer typedef for :cpp:type:`const value_type *` .. cpp:type:: mcrl2::utilities::indexed_set::const_reference typedef for :cpp:type:`const value_type &` .. cpp:type:: mcrl2::utilities::indexed_set::const_reverse_iterator typedef for :cpp:type:`KeyTable::const_reverse_iterator` .. cpp:type:: mcrl2::utilities::indexed_set::difference_type typedef for :cpp:type:`std::ptrdiff_t` .. cpp:type:: mcrl2::utilities::indexed_set::hasher typedef for :cpp:type:`Hash` .. cpp:type:: mcrl2::utilities::indexed_set::iterator typedef for :cpp:type:`KeyTable::iterator` .. cpp:type:: mcrl2::utilities::indexed_set::key_equal typedef for :cpp:type:`Equals` .. cpp:type:: mcrl2::utilities::indexed_set::key_type typedef for :cpp:type:`Key` .. cpp:type:: mcrl2::utilities::indexed_set::pointer typedef for :cpp:type:`value_type *` .. cpp:type:: mcrl2::utilities::indexed_set::reference typedef for :cpp:type:`value_type &` .. cpp:type:: mcrl2::utilities::indexed_set::reverse_iterator typedef for :cpp:type:`KeyTable::reverse_iterator` .. cpp:type:: mcrl2::utilities::indexed_set::size_type typedef for :cpp:type:`std::size_t` .. cpp:type:: mcrl2::utilities::indexed_set::value_type typedef for :cpp:type:`std::pair\< const key_type, size_type >` Private attributes ------------------------------------------------------------------------------- .. cpp:member:: Equals mcrl2::utilities::indexed_set::m_equals .. cpp:member:: Hash mcrl2::utilities::indexed_set::m_hasher .. cpp:member:: std::vector< std::size_t > mcrl2::utilities::indexed_set::m_hashtable .. cpp:member:: KeyTable mcrl2::utilities::indexed_set::m_keys .. cpp:member:: std::shared_ptr< std::mutex > mcrl2::utilities::indexed_set::m_mutex Mutex for the m_hashtable and m_keys data structures. .. cpp:member:: detail::atomic_size_t_wrapper mcrl2::utilities::indexed_set::m_next_index m_next_index indicates the next index that .. cpp:member:: std::vector< detail::thread_control > mcrl2::utilities::indexed_set::m_thread_control public-static-attrib ------------------------------------------------------------------------------- .. cpp:member:: constexpr size_type mcrl2::utilities::indexed_set::npos Value returned when an element does not exist in the set. **Returns:** Value indicating non existing element, equal to std::numeric_limits::max(). Private member functions ------------------------------------------------------------------------------- .. cpp:function:: void indexed_set_assertion(std::size_t thread_index) const .. cpp:function:: void lock_exclusive(const std::size_t thread_index) const .. cpp:function:: void lock_shared(const std::size_t thread_index) const .. cpp:function:: std::size_t put_in_hashtable(const Key &key, std::size_t value, std::size_t &new_position) Inserts the given (key, n) pair into the indexed set. .. cpp:function:: void reserve_indices(std::size_t thread_index) Reserve indices that can be used. Doing this infrequently prevents obtaining an exclusive lock for the indexed set too often. This operation requires a resize of m_keys. .. cpp:function:: void resize_hashtable() Resizes the hash table to twice its current size. .. cpp:function:: void unlock_exclusive(const std::size_t thread_index) const .. cpp:function:: void unlock_shared(const std::size_t thread_index) const Public member functions ------------------------------------------------------------------------------- .. cpp:function:: const key_type& at(const size_type index) const Returns a reference to the mapped value. Returns an out_of_range exception if there is no element with the given key. **Parameters:** * **index** The position in the indexed set. **Returns:** The value at position index. .. cpp:function:: iterator begin(std::size_t thread_index=0) Forward iterator which runs through the elements from the lowest to the largest number. Complexity is constant per operation. .. cpp:function:: const_iterator begin(std::size_t thread_index=0) const Forward iterator which runs through the elements from the lowest to the largest number. Complexity is constant per operation. .. cpp:function:: const_iterator cbegin(std::size_t thread_index=0) const const_iterator going through the elements in the set numbered from zero upwards. .. cpp:function:: const_iterator cend(std::size_t thread_index=0) const End of the forward const_iterator. .. cpp:function:: void clear(std::size_t thread_index=0) Clears the indexed set by removing all its elements. It is not guaranteed that the memory is released too. .. cpp:function:: const_reverse_iterator crbegin(std::size_t thread_index=0) const Reverse const_iterator going through the elements from the highest to the lowest numbered element. .. cpp:function:: const_reverse_iterator crend(std::size_t thread_index=0) const End of the reverse const_iterator. .. cpp:function:: iterator end(std::size_t thread_index=0) End of the forward iterator. .. cpp:function:: const_iterator end(std::size_t thread_index=0) const End of the forward iterator. .. cpp:function:: const_iterator find(const key_type &key, std::size_t thread_index=0) const Provides an iterator to the stored key in the indexed set. **Parameters:** * **key** The key that is sought. **Returns:** An iterator to the key, otherwise end(). .. cpp:function:: size_type index(const key_type &key, std::size_t thread_index=0) const Returns a reference to the mapped value. Returns an invalid value, larger or equal than the size of the indexed set, if there is no element with the given key. .. cpp:function:: indexed_set() Constructor of an empty indexed set. Starts with a hashtable of size 128 and assumes one single thread. .. cpp:function:: indexed_set(std::size_t number_of_threads) Constructor of an empty indexed set. With a single thread it delivers contiguous values for states. With multiple threads some indices may be skipped. Each thread reserves numbers, which it hands out. If a thread does not have the opportunity to hand out all numbers, holes in the contiguous numbering can occur. The holes are always of limited size. **Parameters:** * **number_of_threads** The number of threads that use this index set. If the number is 1, it is treated as a sequential set. If this number is larger than 1, the threads must be numbered from 1 up and including number_of_threads. The number 0 cannot be used in that case. .. cpp:function:: indexed_set(std::size_t number_of_threads, std::size_t initial_hashtable_size, const hasher &hash=hasher(), const key_equal &equals=key_equal()) Constructor of an empty index set. Starts with a hashtable of the indicated size. With one thread the numbering is contiguous. With multiple threads limited size holes can occur in the numbering. **Parameters:** * **number_of_threads** The number of threads that use this index set. This number is either 1, and then the implementation assumes that the thread has number 0, or it is larger than 1, and it is assumed that threads are numbered from 1 upwards. * **initial_hashtable_size** The initial size of the hashtable. * **hash** The hash function. * **equals** The comparison function for its elements. .. cpp:function:: std::pair insert(const key_type &key, std::size_t thread_index=0) Insert a key in the indexed set and return its index. If the element was already in the set, the resulting bool is true, and the existing index is returned. Otherwise, the key is inserted in the set, and the next available index is assigned to it. **Parameters:** * **key** The key to be inserted in the set. **Returns:** The index of the key and a boolean indicating whether the element was actually inserted. .. cpp:function:: const key_type& operator[](const size_type index) const Operator that provides a const reference at the position indicated by index. **Parameters:** * **index** The position in the indexed set. **Returns:** The value at position index. .. cpp:function:: reverse_iterator rbegin(std::size_t thread_index=0) Reverse iterator going through the elements in the set from the largest to the smallest index. .. cpp:function:: reverse_iterator rend(std::size_t thread_index=0) End of the reverse iterator. .. cpp:function:: size_type size(std::size_t thread_index=0) const The number of elements in the indexed set. **Returns:** The number of elements in the indexed set.