Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::math_opt::ThreadSafeIdMap< V > Class Template Referenceabstract

Detailed Description

template<typename V>
class operations_research::math_opt::ThreadSafeIdMap< V >

A map from int64_t ids to V, where the ids are created by this map and handed out sequentially.

The underlying storage for this map is vector<pair<int64_t, unique_ptr<V>>>. Insertions and deletions from this vector are done lazily whenever any of the functions UpdateXXX() are invoked.

At a high level, the purpose of this class is to allow for the thread-safe removal of elements from the map, while have as little overhead as possible when iterating over the elements of the map (UpdateAndGetAll()). In particular, in the common case where there is nothing to update, UpdateAndGetAll() only incurs the cost of a single atomic read with std::memory_order_relaxed, which is much faster than acquiring a lock on a mutex.

This map has pointer stability for values, users can only insert by providing a unique_ptr<V>.

The functions of this class are mutually thread-safe. However, the functions:

  • UpdateAndGetAll()
  • GetAll()
  • UpdateAndGet()
  • Get() return pointers that:
  • can be invalidated other function calls on this class,
  • are not const and may contain mutable data (if V is mutable). Thus there are some limitations on the use of this class in a concurrent context. Each of these functions above returning pointers documents their invalidation conditions inline. Most importantly, it is safe for a single thread to invoke UpdateAndGetAll(), and then modify the returned V*, with an arbitrary number of concurrent calls to Erase().

Definition at line 63 of file thread_safe_id_map.h.

#include <thread_safe_id_map.h>

Public Member Functions

 ThreadSafeIdMap ()=default
absl::Span< const std::pair< int64_t, std::unique_ptr< V > > > UpdateAndGetAll ()
std::vector< std::pair< int64_t, V * > > GetAll () const
V * UpdateAndGet (int64_t id)
V * Get (int64_t id) const
int64_t Insert (std::unique_ptr< V > value)
 Inserts value into the map and returns the assigned key.
bool Erase (int64_t key)
 Erases key from the map, returning true if the key was found in the map.
int64_t Size () const
 The number of elements in the map.

Constructor & Destructor Documentation

◆ ThreadSafeIdMap()

template<typename V>
operations_research::math_opt::ThreadSafeIdMap< V >::ThreadSafeIdMap ( )
default

Member Function Documentation

◆ Erase()

template<typename V>
bool operations_research::math_opt::ThreadSafeIdMap< V >::Erase ( int64_t key)

Erases key from the map, returning true if the key was found in the map.

Definition at line 233 of file thread_safe_id_map.h.

◆ Get()

template<typename V>
V * operations_research::math_opt::ThreadSafeIdMap< V >::Get ( int64_t id) const

Returns the value for this key, or nullptr if this key is not in the map.

The returned pointer is invalidated by any call to Erase(id) or ~ThreadSafeIdMap().

This function is similar to UpdateAndGet(), but it is const. It can be slightly slower, but it is also safer to use from a concurrent context, as it will not invalidate any pointers returned by other functions on this class.

Warning
this does NOT run O(1) time, the complexity is linear in the number of elements in the map plus the number of pending insertions and deletions.
Note
the V value returned is mutable. Any concurrent mutations must be synchronized externally.

Definition at line 173 of file thread_safe_id_map.h.

◆ GetAll()

template<typename V>
std::vector< std::pair< int64_t, V * > > operations_research::math_opt::ThreadSafeIdMap< V >::GetAll ( ) const

Returns all key-value paris in the map.

In contrast to UpdateAndGetAll(), this function will always acquire a lock and copy the data before returning. Thus, this function is slower, but the values are harder to invalidate. This function is also const, while UpdateAndGetAll() is not. Last, because this function does not update, it will not invalidate any pointers returned by other functions on this class.

For each (id, V*) pair, the V* is invalidated by either:

  • ~ThreadSafeIdMap()
  • Erase(id) followed by any call to UpdateXXX().
Note
the V values returned are mutable. Any concurrent mutations must be synchronized externally.

Definition at line 192 of file thread_safe_id_map.h.

◆ Insert()

template<typename V>
int64_t operations_research::math_opt::ThreadSafeIdMap< V >::Insert ( std::unique_ptr< V > value)

Inserts value into the map and returns the assigned key.

Definition at line 223 of file thread_safe_id_map.h.

◆ Size()

template<typename V>
int64_t operations_research::math_opt::ThreadSafeIdMap< V >::Size ( ) const

The number of elements in the map.

Definition at line 166 of file thread_safe_id_map.h.

◆ UpdateAndGet()

template<typename V>
V * operations_research::math_opt::ThreadSafeIdMap< V >::UpdateAndGet ( int64_t id)

Returns the value for this key, or nullptr if this key is not in the map.

The returned pointer is invalidated by either of:

  • ~ThreadSafeIdMap()
  • Erase(id) followed by any call to UpdateXXX().
Warning
this does NOT run O(1) time, the complexity is linear in the number of elements in the map plus the number of pending insertions and deletions.
Note
the V value returned is mutable. Any concurrent mutations must be synchronized externally.

Definition at line 209 of file thread_safe_id_map.h.

◆ UpdateAndGetAll()

template<typename V>
absl::Span< const std::pair< int64_t, std::unique_ptr< V > > > operations_research::math_opt::ThreadSafeIdMap< V >::UpdateAndGetAll ( )

Returns all key-value pairs in the map.

The returned span is invalidated by an Insert() or Erase() followed by a call to UpdateAndGetAll() or UpdateAndGet().

Note
the V values returned are mutable. Any concurrent mutations must be synchronized externally.

Template function implementations.

Definition at line 157 of file thread_safe_id_map.h.

The documentation for this class was generated from the following file: