mcrl2::utilities::indexed_set

Include file:

#include "mcrl2/utilities/indexed_set.h

class mcrl2::utilities::indexed_set

A set that assigns each element an unique index.

Public types

type mcrl2::utilities::indexed_set::const_iterator

typedef for KeyTable::const_iterator

type mcrl2::utilities::indexed_set::const_reverse_iterator

typedef for KeyTable::const_reverse_iterator

type mcrl2::utilities::indexed_set::difference_type

typedef for std::ptrdiff_t

type mcrl2::utilities::indexed_set::hasher

typedef for Hash

type mcrl2::utilities::indexed_set::iterator

typedef for KeyTable::iterator

type mcrl2::utilities::indexed_set::key_equal

typedef for Equals

type mcrl2::utilities::indexed_set::key_type

typedef for Key

type mcrl2::utilities::indexed_set::pointer

typedef for value_type *

type mcrl2::utilities::indexed_set::reference

typedef for value_type &

type mcrl2::utilities::indexed_set::reverse_iterator

typedef for KeyTable::reverse_iterator

type mcrl2::utilities::indexed_set::size_type

typedef for std::size_t

type mcrl2::utilities::indexed_set::value_type

typedef for std::pair< const key_type, size_type >

Public attributes

const typedef value_type * mcrl2::utilities::indexed_set::const_pointer

const typedef value_type & mcrl2::utilities::indexed_set::const_reference

Private attributes

Equals mcrl2::utilities::indexed_set::m_equals

Hash mcrl2::utilities::indexed_set::m_hasher

std::vector<std::size_t> mcrl2::utilities::indexed_set::m_hashtable

KeyTable mcrl2::utilities::indexed_set::m_keys

std::shared_ptr<std::mutex> mcrl2::utilities::indexed_set::m_mutex

Mutex for the m_hashtable and m_keys data structures.

detail::atomic_size_t_wrapper mcrl2::utilities::indexed_set::m_next_index

m_next_index indicates the next index that

std::vector<detail::thread_control> mcrl2::utilities::indexed_set::m_thread_control

public-static-attrib

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<std::size_t>::max().

Private member functions

void indexed_set_assertion(std::size_t thread_index) const

void lock_exclusive(const std::size_t thread_index) const

void lock_shared(const std::size_t thread_index) const

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.

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.

void resize_hashtable()

Resizes the hash table to twice its current size.

void unlock_exclusive(const std::size_t thread_index) const

void unlock_shared(const std::size_t thread_index) const

Public member functions

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.

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.

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.

const_iterator cbegin(std::size_t thread_index = 0) const

const_iterator going through the elements in the set numbered from zero upwards.

const_iterator cend(std::size_t thread_index = 0) const

End of the forward const_iterator.

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.

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.

const_reverse_iterator crend(std::size_t thread_index = 0) const

End of the reverse const_iterator.

iterator end(std::size_t thread_index = 0)

End of the forward iterator.

const_iterator end(std::size_t thread_index = 0) const

End of the forward iterator.

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().

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.

indexed_set()

Constructor of an empty indexed set. Starts with a hashtable of size 128 and assumes one single thread.

indexed_set(std::size_t number_of_threads)

Constructor of an empty indexed set. detail 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.

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.

std::pair<size_type, bool> 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. threadsafe

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. threadsafe

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.

reverse_iterator rend(std::size_t thread_index = 0)

End of the reverse iterator.

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. threadsafe