CxxUtils::DeletePayload Struct Reference

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

#include <ConcurrentRangeMap.h>

Collaboration diagram for CxxUtils::DeletePayload:

Public Member Functions
	DeletePayload (delete_function *delfcn)
	Initialize with an explicit deletion function.
template<class U>
	DeletePayload (const std::default_delete< U > &)
void	operator() (const T *p) const
	Delete a pointer.

Static Public Member Functions
template<class U>
static void	delfcn (const T *p)
	Allow initializing a payload_unique_ptr from a std::unique_ptr.

Public Attributes
delete_function *	m_delete
	The deletion function.

Detailed Description

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. */ 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 ConcurrentRangeMap { public: 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;

/ Function to delete a T* typedef void delete_function (const T*);

/**

unique_ptr deletion class for a payload object.

We can't use the unique_ptr default because we want to allow instantiating with a void.

Definition at line 236 of file ConcurrentRangeMap.h.

Constructor & Destructor Documentation

DeletePayload() [1/2]

CxxUtils::DeletePayload::DeletePayload ( delete_function * delfcn )

inline

Initialize with an explicit deletion function.

Definition at line 239 of file ConcurrentRangeMap.h.

      : m_delete (delfcn)
    {
    }

DeletePayload() [2/2]

template<class U>

CxxUtils::DeletePayload::DeletePayload ( const std::default_delete< U > & )

inline

Definition at line 251 of file ConcurrentRangeMap.h.

    {
      m_delete = delfcn<U>;
    }

Member Function Documentation

delfcn()

template<class U>

void CxxUtils::DeletePayload::delfcn ( const T * p )

inlinestatic

Allow initializing a payload_unique_ptr from a std::unique_ptr.

Definition at line 246 of file ConcurrentRangeMap.h.

    {
      delete reinterpret_cast<const U*>(p);
    }

operator()()

void CxxUtils::DeletePayload::operator() ( const T * p ) const

inline

Delete a pointer.

Definition at line 257 of file ConcurrentRangeMap.h.

    {
      m_delete (p);
    }

Member Data Documentation

m_delete

delete_function* CxxUtils::DeletePayload::m_delete

The deletion function.

Definition at line 263 of file ConcurrentRangeMap.h.

---

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

• ConcurrentRangeMap.h