The kernel of flat combining. More...

#include <cds/algo/flat_combining/kernel.h>

Data Structures
class	iterator
	Publication list iterator. More...

Public Types
typedef Traits	traits
	Type traits.

typedef traits::lock_type	global_lock_type
	Global lock type.

typedef traits::wait_strategy	wait_strategy
	Wait strategy type.

typedef traits::allocator	allocator
	Allocator type (used for allocating publication_record_type data)

typedef traits::stat	stat
	Internal statistics.

typedef traits::memory_model	memory_model
	C++ memory model.

typedef wait_strategy::template make_publication_record< PublicationRecord >::type	publication_record_type
	Publication record type.

Public Member Functions
	kernel ()
	Initializes the object. More...

	kernel (unsigned int nCompactFactor, unsigned int nCombinePassCount)
	Initializes the object. More...

	~kernel ()
	Destroys the object and all publication records.

publication_record_type *	acquire_record ()
	Gets publication list record for the current thread. More...

void	release_record (publication_record_type *pRec)
	Marks publication record for the current thread as empty.

template<class Container >
void	combine (unsigned int nOpId, publication_record_type *pRec, Container &owner)
	Trying to execute operation `nOpId`. More...

template<class Container >
void	batch_combine (unsigned int nOpId, publication_record_type *pRec, Container &owner)
	Trying to execute operation `nOpId` in batch-combine mode. More...

template<typename Func >
void	invoke_exclusive (Func f)
	Invokes `Func` in exclusive mode. More...

void	operation_done (publication_record &rec)
	Marks `rec` as executed. More...

stat const &	statistics () const
	Internal statistics.

unsigned int	compact_factor () const
	Returns the compact factor.

unsigned int	combine_pass_count () const
	Returns number of combining passes for combiner thread.

iterator	begin ()
	Returns an iterator to the first active publication record.

iterator	end ()
	Returns an iterator to the end of publication list. Should not be dereferenced.

int	get_operation (publication_record &rec)
	Gets current value of `rec.nRequest`. More...

void	wakeup_any ()
	Wakes up any waiting thread. More...

Protected Attributes
atomics::atomic< unsigned int >	m_nCount
	Total count of combining passes. Used as an age.

publication_record_type *	m_pHead
	Head of active publication list.

publication_record_type *	m_pAllocatedHead
	Head of allocated publication list.

boost::thread_specific_ptr< publication_record_type >	m_pThreadRec
	Thread-local publication record.

global_lock_type	m_Mutex
	Global mutex.

stat	m_Stat
	Internal statistics.

unsigned int const	m_nCompactFactor
	Publication list compacting factor (the list will be compacted through `m_nCompactFactor` combining passes)

unsigned int const	m_nCombinePassCount
	Number of combining passes.

wait_strategy	m_waitStrategy
	Wait strategy.

Detailed Description

template<typename PublicationRecord, typename Traits = traits>
class cds::algo::flat_combining::kernel< PublicationRecord, Traits >

The kernel of flat combining.

Template parameters:

PublicationRecord - a type derived from publication_record
Traits - a type traits of flat combining, default is flat_combining::traits. make_traits metafunction can be used to create type traits

The kernel object should be a member of a container class. The container cooperates with flat combining kernel object. There are two ways to interact with the kernel:

One-by-one processing the active records of the publication list. This mode provides by combine() function: the container acquires its publication record by acquire_record(), fills its fields and calls combine() function of its kernel object. If the current thread becomes a combiner, the kernel calls fc_apply() function of the container for each active non-empty record. Then, the container should release its publication record by release_record(). Only one pass through the publication list is possible.
Batch processing - batch_combine() function. It this mode the container obtains access to entire publication list. This mode allows the container to perform an elimination, for example, the stack can collide push() and pop() requests. The sequence of invocations is the following: the container acquires its publication record by acquire_record(), fills its field and call batch_combine() function of its kernel object. If the current thread becomes a combiner, the kernel calls fc_process() function of the container passing two iterators pointing to the begin and the end of publication list (see iterator class). The iterators allow multiple pass through active records of publication list. For each processed record the container should call operation_done() function. On the end, the container should release its record by release_record().

Constructor & Destructor Documentation

◆ kernel() [1/2]

template<typename PublicationRecord , typename Traits = traits>

cds::algo::flat_combining::kernel< PublicationRecord, Traits >::kernel ( )

inline

Initializes the object.

Compact factor = 1024

Combiner pass count = 8

◆ kernel() [2/2]

template<typename PublicationRecord , typename Traits = traits>

cds::algo::flat_combining::kernel< PublicationRecord, Traits >::kernel	(	unsigned int	nCompactFactor,
		unsigned int	nCombinePassCount
	)

inline

Initializes the object.

Parameters

nCompactFactor	Publication list compacting factor (the list will be compacted through `nCompactFactor` combining passes)
nCombinePassCount	Number of combining passes for combiner thread

Member Function Documentation

◆ acquire_record()

template<typename PublicationRecord , typename Traits = traits>

publication_record_type* cds::algo::flat_combining::kernel< PublicationRecord, Traits >::acquire_record ( )

inline

Gets publication list record for the current thread.

If there is no publication record for the current thread the function allocates it.

◆ batch_combine()

template<typename PublicationRecord , typename Traits = traits>

template<class Container >

void cds::algo::flat_combining::kernel< PublicationRecord, Traits >::batch_combine	(	unsigned int	nOpId,
		publication_record_type *	pRec,
		Container &	owner
	)

inline

Trying to execute operation nOpId in batch-combine mode.

pRec is the publication record acquiring by acquire_record() earlier. owner is a container that owns flat combining kernel object. As a result the current thread can become a combiner or can wait for another combiner performs pRec operation.

If the thread becomes a combiner, the kernel calls owner.fc_process() giving the container the full access over publication list. This function is useful for an elimination technique if the container supports any kind of that. The container can perform multiple pass through publication list.

owner.fc_process() has two arguments - forward iterators on begin and end of publication list, see iterator class. For each processed record the container should call operation_done() function to mark the record as processed.

On the end of batch_combine the combine() function is called to process rest of publication records.

◆ combine()

template<typename PublicationRecord , typename Traits = traits>

template<class Container >

void cds::algo::flat_combining::kernel< PublicationRecord, Traits >::combine	(	unsigned int	nOpId,
		publication_record_type *	pRec,
		Container &	owner
	)

inline

Trying to execute operation nOpId.

pRec is the publication record acquiring by acquire_record earlier. owner is a container that is owner of flat combining kernel object. As a result the current thread can become a combiner or can wait for another combiner performs pRec operation.

If the thread becomes a combiner, the kernel calls owner.fc_apply for each active non-empty publication record.

◆ get_operation()

template<typename PublicationRecord , typename Traits = traits>

int cds::algo::flat_combining::kernel< PublicationRecord, Traits >::get_operation ( publication_record & rec )

inline

Gets current value of rec.nRequest.

This function is intended for invoking from a wait strategy

◆ invoke_exclusive()

template<typename PublicationRecord , typename Traits = traits>

template<typename Func >

void cds::algo::flat_combining::kernel< PublicationRecord, Traits >::invoke_exclusive ( Func f )

inline

Invokes Func in exclusive mode.

Some operation in flat combining containers should be called in exclusive mode i.e the current thread should become the combiner to process the operation. The typical example is empty() function.

invoke_exclusive() allows do that: the current thread becomes the combiner, invokes f exclusively but unlike a typical usage the thread does not process any pending request. Instead, after end of f call the current thread wakes up a pending thread if any.

◆ operation_done()

template<typename PublicationRecord , typename Traits = traits>

void cds::algo::flat_combining::kernel< PublicationRecord, Traits >::operation_done ( publication_record & rec )

inline

Marks rec as executed.

This function should be called by container if batch_combine() mode is used. For usual combining (see combine()) this function is excess.

◆ wakeup_any()

template<typename PublicationRecord , typename Traits = traits>

void cds::algo::flat_combining::kernel< PublicationRecord, Traits >::wakeup_any ( )

inline

Wakes up any waiting thread.

This function is intended for invoking from a wait strategy

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

cds/algo/flat_combining/kernel.h

Data Structures

Public Types

Public Member Functions

Protected Attributes

Detailed Description

template<typename PublicationRecord, typename Traits = traits> class cds::algo::flat_combining::kernel< PublicationRecord, Traits >

Constructor & Destructor Documentation

◆ kernel() [1/2]

◆ kernel() [2/2]

Member Function Documentation

◆ acquire_record()

◆ batch_combine()

◆ combine()

◆ get_operation()

◆ invoke_exclusive()

◆ operation_done()

◆ wakeup_any()

template<typename PublicationRecord, typename Traits = traits>
class cds::algo::flat_combining::kernel< PublicationRecord, Traits >