ConcurrentRangeMap.h File Reference

Map from range to payload object, allowing concurrent, lockless reads. More...

#include "CxxUtils/stall.h"
#include "CxxUtils/IsUpdater.h"
#include <atomic>
#include <mutex>
#include <utility>
#include <vector>
#include <memory>
#include <algorithm>
#include <functional>
#include <ranges>
#include "CxxUtils/ConcurrentRangeMap.icc"

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	CxxUtils::IRangeMapPayloadDeleter< T, CONTEXT >
	Helper to delete payload objects for ConcurrentRangeMap. More...
struct	CxxUtils::DeletePayload
	Map from range to payload object, allowing concurrent, lockless reads. More...
class	CxxUtils::Impl
	Implementation object. More...

Namespaces
namespace	CxxUtils
namespace	CxxUtils::detail

Concepts
concept	CxxUtils::detail::IsConcurrentRangeCompare
	Concept for comparison template argument.

Typedefs
using	CxxUtils::payload_unique_ptr = std::unique_ptr<T, DeletePayload>
	unique_ptr holding a payload object.
using	CxxUtils::const_iterator = const value_type*
using	CxxUtils::Updater_t = UPDATER<Impl>
using	CxxUtils::IPayloadDeleter = CxxUtils::IRangeMapPayloadDeleter<T, typename Updater_t::Context_t>

Enumerations
enum class	CxxUtils::EmplaceResult { CxxUtils::SUCCESS , CxxUtils::OVERLAP , CxxUtils::DUPLICATE , CxxUtils::EXTENDED }
	Results returned from emplace(). More...

Functions
	CxxUtils::ConcurrentRangeMap (Updater_t &&updater, std::shared_ptr< IPayloadDeleter > payloadDeleter, size_t capacity=16, const COMPARE &compare=COMPARE())
	Constructor.
	CxxUtils::~ConcurrentRangeMap ()
	Destructor.
IPayloadDeleter &	CxxUtils::deleter ()
	Return a reference to the payload deleter object.
const_iterator	CxxUtils::find (const key_query_type &key) const
	Search for the first item less than or equal to KEY.
EmplaceResult	CxxUtils::emplace (const RANGE &range, payload_unique_ptr ptr, bool tryExtend=false, const typename Updater_t::Context_t &ctx=Updater_t::defaultContext())
	Add a new element to the map.
void	CxxUtils::erase (const key_query_type &key, const typename Updater_t::Context_t &ctx=Updater_t::defaultContext())
	Erase the first item less than or equal to KEY.
int	CxxUtils::extendLastRange (const RANGE &newRange, const typename Updater_t::Context_t &ctx=Updater_t::defaultContext())
	Extend the range of the last entry of the map.
void	CxxUtils::updateRanges (std::function< void(RANGE &)> rangeUpdater, const typename Updater_t::Context_t &ctx=Updater_t::defaultContext())
	Update all range objects.
size_t	CxxUtils::trim (const std::vector< key_query_type > &keys, bool trimall=false)
	Remove unused entries from the front of the list.
size_t	CxxUtils::nInserts () const
	Return the number times an item was inserted into the map.
size_t	CxxUtils::maxSize () const
	Return the maximum size of the map.
const_iterator_range	CxxUtils::range () const
	Return an iterator range covering the entire map.
void	CxxUtils::quiescent (const typename Updater_t::Context_t &ctx=Updater_t::defaultContext())
	Called when this thread is no longer referencing anything from this container.
const_iterator	CxxUtils::getBegin (const_iterator &last) const
	Return the begin/last pointers.
void	CxxUtils::updatePointers (value_type *new_begin, value_type *new_end)
	Consistently update both the begin and last pointers.
bool	CxxUtils::anyInRange (const key_type &r, const std::vector< key_query_type > &keys) const
	Test to see if any keys within keys match r.
void	CxxUtils::installImpl (std::unique_ptr< Impl > new_impl, value_type *new_begin, value_type *new_end, const typename Updater_t::Context_t &ctx)
	Install a new implementation instance and make it visible.
int	CxxUtils::extendImpl (lock_t &lock, const RANGE &extendedRange, const typename Updater_t::Context_t &ctx)
	Extend the range of the last entry of the map.
Set operations.
ConcurrentBitset &	CxxUtils::clear ()
	Clear all bits in the set.
Size, bit testing
bit_t	CxxUtils::size () const
	Count the number of 1 bits in the set.
bool	CxxUtils::empty () const
	Return true if there are no 1 bits in the set.
bit_t	CxxUtils::capacity () const
	The number of bits that this container can hold.

Variables
Updater_t	CxxUtils::m_updater
	Updater object. This maintains ownership of the current implementation class and the older versions.
COMPARE	CxxUtils::m_compare
	Comparison object.
std::shared_ptr< IPayloadDeleter >	CxxUtils::m_payloadDeleter
	Payload deleter object. Important: do not discard an object while it's still reachable from the m_begin / m_last range — update the pointers first. Otherwise, the object may be deleted while another thread is still referencing it: thread 1: Discard object. Sets grace mask for both slots. thread 2: Call quiescent(). Clears grace mask for 2. Retrieve the discarded object. thread 1: Adjust pointers. Call quiescent. The discarded object may be deleted at this point while thread 2 is still reading it.
std::atomic< value_type * >	CxxUtils::m_begin
	Pointers to the first and last elements of the container. m_last is not the usual end pointer; it points at the last element in the container. If the container is empty, then m_last will be null. If these are to both be updated together, it should be done in this order. First, m_begin should be set to null. This marks that there's an update in progress. Then m_last should be set, followed by m_begin. To read both pointers, we first fetch m_last. Then fetch m_begin. Then check that both m_begin is non-null and the previous value we fetched for last matches what's now in m_last. If either condition fails, then re-fetch both pointers.
std::atomic< value_type * >	CxxUtils::m_last
size_t	CxxUtils::m_nInserts
	Some basic statistics.
size_t	CxxUtils::m_maxSize

Detailed Description

Map from range to payload object, allowing concurrent, lockless reads.

Author

scott snyder snyde.nosp@m.r@bn.nosp@m.l.gov

Date

Nov, 2017

Definition in file ConcurrentRangeMap.h.