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

#include <ConcurrentRangeMap.h>

Collaboration diagram for CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >:

Classes
struct	DeletePayload
	`unique_ptr` deletion class for a payload object. More...
class	Impl
	Holds one version of the map. More...

Public Types
enum class	EmplaceResult { SUCCESS , OVERLAP , DUPLICATE , EXTENDED }
	Results returned from emplace(). More...
typedef RANGE	key_type
typedef const T *	mapped_type
typedef std::pair< RANGE, const T * >	value_type
typedef const value_type &	const_reference
typedef const value_type *	const_pointer
typedef size_t	size_type
typedef int	difference_type
typedef COMPARE	key_compare
typedef KEY	key_query_type
typedef void	delete_function(const T *)
	Function to delete a `T*`.
using	payload_unique_ptr = std::unique_ptr<T, DeletePayload>
	`unique_ptr` holding a payload object.
using	const_iterator = const value_type*
using	const_iterator_range = std::ranges::subrange<const_iterator>
using	Updater_t = UPDATER<Impl>
using	IPayloadDeleter = CxxUtils::IRangeMapPayloadDeleter<T, typename Updater_t::Context_t>

Public Member Functions
	ConcurrentRangeMap (Updater_t &&updater, std::shared_ptr< IPayloadDeleter > payloadDeleter, size_t capacity=16, const COMPARE &compare=COMPARE())
	Constructor.
	~ConcurrentRangeMap ()
	Destructor.
IPayloadDeleter &	deleter ()
	Return a reference to the payload deleter object.
const IPayloadDeleter &	deleter () const
	Return a reference to the payload deleter object.
const_iterator	find (const key_query_type &key) const
	Search for the first item less than or equal to KEY.
EmplaceResult	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	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	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	updateRanges (std::function< void(RANGE &)> rangeUpdater, const typename Updater_t::Context_t &ctx=Updater_t::defaultContext())
	Update all range objects.
size_t	trim (const std::vector< key_query_type > &keys, bool trimall=false)
	Remove unused entries from the front of the list.
void	clear ()
	Remove all entries in the container.
size_t	size () const
	Return the current number of elements in the map.
bool	empty () const
	Test if the map is empty.
size_t	capacity () const
	Return the current capacity of the map.
size_t	nInserts () const
	Return the number times an item was inserted into the map.
size_t	maxSize () const
	Return the maximum size of the map.
const_iterator_range	range () const
	Return a range that can be used to iterate over the container.
void	quiescent (const typename Updater_t::Context_t &ctx=Updater_t::defaultContext())
	Called when this thread is no longer referencing anything from this container.

Private Types
typedef std::mutex	mutex_t
	Type of the mutex for this container.
typedef std::lock_guard< mutex_t >	lock_t

Private Member Functions
const_iterator	getBegin (const_iterator &last) const
	Return the begin/last pointers.
void	updatePointers (value_type new_begin, value_type new_end)
	Consistently update both the begin and last pointers.
bool	anyInRange (const key_type &r, const std::vector< key_query_type > &keys) const
	Test to see if any keys within `keys` match `r`.
void	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	extendImpl (lock_t &lock, const RANGE &extendedRange, const typename Updater_t::Context_t &ctx)
	Extend the range of the last entry of the map.

Private Attributes
Updater_t	m_updater
	Updater object.
COMPARE	m_compare
	Comparison object.
std::shared_ptr< IPayloadDeleter >	m_payloadDeleter
	Payload deleter object.
Impl *	m_impl
	Current version of the implementation class.
std::atomic< value_type * >	m_begin
	Pointers to the first and last elements of the container.
std::atomic< value_type * >	m_last
size_t	m_nInserts
	Some basic statistics.
size_t	m_maxSize
mutex_t	m_mutex
	Mutex protecting the container.

Detailed Description

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>
requires (detail::IsUpdater<UPDATER> && detail::IsConcurrentRangeCompare<COMPARE, RANGE, KEY, typename UPDATER<int>::Context_t>)
class CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >

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

This class implements a map of sorted ‘range’ objects (though only a single value is actually used) to allocated payload objects. Values can be looked up by a key; the value returned will be the first for which the range is not less than the key. We also support insertions, erasures, and iteration.

The only thing we need to do with the contained pointers is to delete them. Rather than doing that directly, we take a deletion object as an argument to the constructor. This allows one to instantiate this template with void as T, to reduce the amount of generated code. The emplace method takes a unique_ptr as an argument. We define payload_unique_ptr which is a unique_ptr to T that does deletion by calling an arbitrary function. payload_unique_ptr may be initialized from a unique_ptr; to construct one directly, the deletion function should be passed as a second argument to the payload_unique_ptr constructor.

There can be only one writer at a time; this is enforced with internal locks. However, there can be any number of concurrent readers at any time. The reads are lockless (but not necessarily waitless, though this should not be significant in practice). So this is appropriate when reads are much more frequent than writes.

This implementation also assumes that a lookup is most likely to be for the last element in the map, that insertions are most likely to be at the end, and that erasures are most likely to be from the beginning. This class will still work if these assumptions are violated, but it may be much slower. (The use case for which this was targeted was that of conditions containers.)

Template arguments: RANGE - The type of the range object stored with each element. KEY - The type used to look up objects in the container. This may be same as RANGE, but not necessarily. (For example, RANGE may contain start and end times, while KEY may be a single time.) COMPARE - Object used for key comparisons; see below. UPDATER - Object used for memory management; see below.

COMPARE should implement a less-than relation, like a typical STL comparison object, with these signatures:

bool operator() (const KEY& k1,   const RANGE& r2) const;
bool operator() (const RANGE& r1, const RANGE& r2) const;
bool inRange (const KEY& k, const RANGE& r) const;
 
// Test if two ranges overlap, and adjust if needed.
// OLDRANGE is an existing range in the container, and NEWRANGE
// is a new one being added.  Return one of:
//   0 -- no overlap between the ranges; NEWRANGE is unmodified.
//   1 -- ranges overlap.  NEWRANGE has been adjusted to avoid the overlap.
//        If the start of NEWRANGE is changed, it must
//        only be moved forward (increased), never backwards.
//  -1 -- duplicate: NEWRANGE is entirely inside OLDRANGE.
//        Delete the new range.         
int overlap (const Context_t& ctx,
             const RANGE& oldRange, RANGE& newRange) const;
 
// Possibly extend an existing range at the end.
// RANGE is the existing range, and NEWRANGE is the range
// being added.  Returns one of:
// Required only for extendLastRange --- which see.
//   0 -- no change was made to RANGE.
//   1 -- RANGE was extended. 
//  -1 -- newRange is a duplicate.
int extendRange (Range& range, const Range& newRange) const;

In order to implement updating concurrently with reading, we need to defer deletion of objects until no thread can be referencing them any more. The policy for this for the internal implementation objects is set by the template UPDATER<T>. For details, see IsUpdater.h.

Deletion of payload objects is managed via the IRangeMapPayloadDeleter object passed to the constructor.

Implementation notes: The values we store are pairs of RANGE, const T*. The data are stored in a vector of such values. We maintain atomic pointers to the first and last valid elements in the map. We can quickly add an element to the end or delete an element from the beginning by adjusting these pointers. Any other changes will require making a new copy of the data vector.

Definition at line 212 of file ConcurrentRangeMap.h.

Member Typedef Documentation

◆ const_iterator

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

using CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::const_iterator = const value_type*

Definition at line 288 of file ConcurrentRangeMap.h.

◆ const_iterator_range

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

using CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::const_iterator_range = std::ranges::subrange<const_iterator>

Definition at line 289 of file ConcurrentRangeMap.h.

◆ const_pointer

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

typedef const value_type* CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::const_pointer

Definition at line 219 of file ConcurrentRangeMap.h.

◆ const_reference

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

typedef const value_type& CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::const_reference

Definition at line 218 of file ConcurrentRangeMap.h.

◆ delete_function

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

typedef void CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::delete_function(const T *)

Function to delete a T*.

Definition at line 227 of file ConcurrentRangeMap.h.

◆ difference_type

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

typedef int CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::difference_type

Definition at line 221 of file ConcurrentRangeMap.h.

◆ IPayloadDeleter

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

using CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::IPayloadDeleter = CxxUtils::IRangeMapPayloadDeleter<T, typename Updater_t::Context_t>

Definition at line 336 of file ConcurrentRangeMap.h.

◆ key_compare

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

typedef COMPARE CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::key_compare

Definition at line 222 of file ConcurrentRangeMap.h.

◆ key_query_type

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

typedef KEY CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::key_query_type

Definition at line 223 of file ConcurrentRangeMap.h.

◆ key_type

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

typedef RANGE CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::key_type

Definition at line 215 of file ConcurrentRangeMap.h.

◆ lock_t

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

typedef std::lock_guard<mutex_t> CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::lock_t

private

Definition at line 552 of file ConcurrentRangeMap.h.

◆ mapped_type

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

typedef const T* CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::mapped_type

Definition at line 216 of file ConcurrentRangeMap.h.

◆ mutex_t

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

typedef std::mutex CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::mutex_t

private

Type of the mutex for this container.

Definition at line 551 of file ConcurrentRangeMap.h.

◆ payload_unique_ptr

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

using CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::payload_unique_ptr = std::unique_ptr<T, DeletePayload>

unique_ptr holding a payload object.

One may initialize an instance of this in one of two ways. First, from another std::unique_ptr:

payload_unique_ptr p = std::unique_ptr<U> (...);

CxxUtils::ConcurrentRangeMap::payload_unique_ptr

std::unique_ptr< T, DeletePayload > payload_unique_ptr

unique_ptr holding a payload object.

Definition ConcurrentRangeMap.h:286

where U* must be convertible to T*. In this case, the pointer will be deleted as a U*. Second, one can supply an explicit deletion function:

T* tp = ...;

payload_unique_ptr p (tp, delfcn);

Definition at line 286 of file ConcurrentRangeMap.h.

◆ size_type

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

typedef size_t CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::size_type

Definition at line 220 of file ConcurrentRangeMap.h.

◆ Updater_t

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

using CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::Updater_t = UPDATER<Impl>

Definition at line 335 of file ConcurrentRangeMap.h.

◆ value_type

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

typedef std::pair<RANGE, const T*> CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::value_type

Definition at line 217 of file ConcurrentRangeMap.h.

Member Enumeration Documentation

◆ EmplaceResult

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

enum class CxxUtils::ConcurrentRangeMap::EmplaceResult

strong

Results returned from emplace().

Enumerator
SUCCESS	All ok.
OVERLAP	New object was added, but overlaps with an existing range.
DUPLICATE	New object duplicates an existing range, and was not added.
EXTENDED

Definition at line 383 of file ConcurrentRangeMap.h.

  {
    SUCCESS,
    OVERLAP,
    DUPLICATE,
 
    // Existing range was extended to match the new range; new object
    // was deleted.
    EXTENDED
  };

Constructor & Destructor Documentation

◆ ConcurrentRangeMap()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::ConcurrentRangeMap	(	Updater_t &&	updater,
		std::shared_ptr< IPayloadDeleter >	payloadDeleter,
		size_t	capacity = 16,
		const COMPARE &	compare = COMPARE() )

Constructor.

Parameters

updater	Object used to manage memory (see comments at the start of the class).
payloadDeleter	Object for deleting payload objects. This is owned via a `shared_ptr`.
capacity	Initial capacity of the map.
compare	Comparison object.

◆ ~ConcurrentRangeMap()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::~ConcurrentRangeMap ( )

Destructor.

Clean up any remaining payload objects.

Member Function Documentation

◆ anyInRange()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

bool CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::anyInRange	(	const key_type &	r,
		const std::vector< key_query_type > &	keys ) const

private

Test to see if any keys within keys match r.

r Range to test. @break keys List of keys to test. MUST be sorted.

◆ capacity()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

size_t CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::capacity ( ) const

Return the current capacity of the map.

◆ clear()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

void CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::clear ( )

Remove all entries in the container.

Mostly for testing — should not normally be used.

◆ deleter() [1/2]

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

IPayloadDeleter & CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::deleter ( )

Return a reference to the payload deleter object.

◆ deleter() [2/2]

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

const IPayloadDeleter & CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::deleter ( ) const

Return a reference to the payload deleter object.

◆ emplace()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

EmplaceResult CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::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.

Parameters

range	Validity range for this element.
ptr	Payload for this element.
tryExtend	If true, then allow an existing range to be extended (see below).
ctx	Execution context.

Returns SUCCESS if the new element was successfully inserted. Returns DUPLICATE if the range compared equal to an existing one. In that case, no new element is inserted (and ptr gets deleted). Returns EXTEND if the range of the last element was extended to range. This happens if tryExtend is true, range is equal to the range of the last element (according to m_compare), and the range can be extended according to extendRange. (This will generally mean that the start time of range matches the last range, and end time of range is after the end time of the last range.) In this case, again no new element is inserted and ptr is deleted. Returns OVERLAP if the range of the new element overlaps an existing element (the new element is still inserted).

◆ empty()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

bool CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::empty ( ) const

Test if the map is empty.

◆ erase()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

void CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::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.

Parameters

key	The key to search erase.
ctx	Execution context.

◆ extendImpl()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

int CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::extendImpl	(	lock_t &	lock,
		const RANGE &	extendedRange,
		const typename Updater_t::Context_t &	ctx )

private

Extend the range of the last entry of the map.

Parameters

Lock	object.
extendedRange	New range to use for the last entry.
ctx	Execution context.

Implementation of extendLastRange; see there for details. Must be called with the lock held.

◆ extendLastRange()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

int CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::extendLastRange	(	const RANGE &	newRange,
		const typename Updater_t::Context_t &	ctx = Updater_t::defaultContext() )

Extend the range of the last entry of the map.

Parameters

newRange	New range to use for the last entry.
ctx	Execution context.

The range of the last entry in the map is updated to newRange. Does nothing if the map is empty. This will make a new version of implementation data.

The semantics of what it means to extend a range are given by the extendRange method of the COMPARE object (see above).

Returns -1 if there was an error; 1 if the last range was extended; and 0 if nothing was changed.

◆ find()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

const_iterator CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::find ( const key_query_type & key ) const

Search for the first item less than or equal to KEY.

Parameters

key	The key to search for.

Returns: The value, or nullptr if not found.

◆ getBegin()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

const_iterator CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::getBegin ( const_iterator & last ) const

private

Return the begin/last pointers.

Parameters

[in,out] last Current value of last.

Retrieve consistent values of the begin and last pointers. The last pointer should have already been fetched, and may be updated. Usage should be like this:

const_iterator last = m_last;
if (!last) return;  // Container empty.
const_iterator begin = getBegin (last);
if (!last) return;  // Container empty.

◆ installImpl()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

void CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::installImpl	(	std::unique_ptr< Impl >	new_impl,
		value_type *	new_begin,
		value_type *	new_end,
		const typename Updater_t::Context_t &	ctx )

private

Install a new implementation instance and make it visible.

Parameters

new_impl	The new instance.
new_begin	Begin pointer for the new instance.
new_end	End pointer for the new instance. (Usual STL meaning of end. If the instance is empty, then new_end should match new_begin.)
ctx	Execution context.

◆ maxSize()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

size_t CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::maxSize ( ) const

Return the maximum size of the map.

◆ nInserts()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

size_t CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::nInserts ( ) const

Return the number times an item was inserted into the map.

◆ quiescent()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

void CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::quiescent ( const typename Updater_t::Context_t & ctx = Updater_t::defaultContext() )

Called when this thread is no longer referencing anything from this container.

Parameters

ctx	Execution context.

◆ range()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

const_iterator_range CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::range ( ) const

Return a range that can be used to iterate over the container.

◆ size()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

size_t CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::size ( ) const

Return the current number of elements in the map.

◆ trim()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

size_t CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::trim	(	const std::vector< key_query_type > &	keys,
		bool	trimall = false )

Remove unused entries from the front of the list.

Parameters

keys	List of keys that may still be in use. (Must be sorted.)
trimall	If true, then allow removing all elements in the container. Otherwise, stop when there's one left.

We examine the objects in the container, starting with the earliest one. If none of the keys in keys match the range for this object, then it is removed from the container. We stop when we either find an object with a range matching a key in keys or (if trimall is false) when there is only one object left.

The list keys MUST be sorted.

Removed objects are queued for deletion once all slots have been marked as quiescent.

Returns the number of objects that were removed.

◆ updatePointers()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

void CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::updatePointers	(	value_type *	new_begin,
		value_type *	new_end )

private

Consistently update both the begin and last pointers.

Parameters

begin	New begin pointer.
end	New end pointer.

◆ updateRanges()

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

void CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::updateRanges	(	std::function< void(RANGE &)>	rangeUpdater,
		const typename Updater_t::Context_t &	ctx = Updater_t::defaultContext() )

Update all range objects.

Parameters

rangeUpdater	Functional to call on each range object.
ctx	Execution context.

This will iterate through the list of entries and call rangeUpdater on the RANGE part of each. Be careful: rangeUpdater must not change any part of the range which might affect the sorting of entries.

Member Data Documentation

◆ m_begin

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

std::atomic<value_type*> CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::m_begin

private

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.

Definition at line 654 of file ConcurrentRangeMap.h.

◆ m_compare

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

COMPARE CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::m_compare

private

Comparison object.

Definition at line 625 of file ConcurrentRangeMap.h.

◆ m_impl

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

Impl* CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::m_impl

private

Current version of the implementation class.

Definition at line 641 of file ConcurrentRangeMap.h.

◆ m_last

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

std::atomic<value_type*> CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::m_last

private

Definition at line 655 of file ConcurrentRangeMap.h.

◆ m_maxSize

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

size_t CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::m_maxSize

private

Definition at line 659 of file ConcurrentRangeMap.h.

◆ m_mutex

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

mutex_t CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::m_mutex

private

Mutex protecting the container.

Definition at line 662 of file ConcurrentRangeMap.h.

◆ m_nInserts

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

size_t CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::m_nInserts

private

Some basic statistics.

Definition at line 658 of file ConcurrentRangeMap.h.

◆ m_payloadDeleter

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

std::shared_ptr<IPayloadDeleter> CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::m_payloadDeleter

private

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.

Definition at line 638 of file ConcurrentRangeMap.h.

◆ m_updater

template<class RANGE, class KEY, class T, class COMPARE, template< class > class UPDATER>

Updater_t CxxUtils::ConcurrentRangeMap< RANGE, KEY, T, COMPARE, UPDATER >::m_updater

private

Updater object.

This maintains ownership of the current implementation class and the older versions.

Definition at line 622 of file ConcurrentRangeMap.h.

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

ConcurrentRangeMap.h

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_iterator_range

◆ const_pointer

◆ const_reference

◆ delete_function

◆ difference_type

◆ IPayloadDeleter

◆ key_compare

◆ key_query_type

◆ key_type

◆ lock_t

◆ mapped_type

◆ mutex_t

◆ payload_unique_ptr

◆ size_type

◆ Updater_t

◆ value_type

Member Enumeration Documentation

◆ EmplaceResult

Constructor & Destructor Documentation

◆ ConcurrentRangeMap()

◆ ~ConcurrentRangeMap()

Member Function Documentation

◆ anyInRange()

◆ capacity()

◆ clear()

◆ deleter() [1/2]

◆ deleter() [2/2]

◆ emplace()

◆ empty()

◆ erase()

◆ extendImpl()

◆ extendLastRange()

◆ find()

◆ getBegin()

◆ installImpl()

◆ maxSize()

◆ nInserts()

◆ quiescent()

◆ range()

◆ size()

◆ trim()

◆ updatePointers()

◆ updateRanges()

Member Data Documentation

◆ m_begin

◆ m_compare

◆ m_impl

◆ m_last

◆ m_maxSize

◆ m_mutex

◆ m_nInserts

◆ m_payloadDeleter

◆ m_updater