EllenBinTree traits. More...

#include <cds/intrusive/details/ellen_bintree_base.h>

Public Types
typedef base_hook	hook
	Hook used (mandatory) More...

typedef opt::none	key_extractor
	Key extracting functor (mandatory) More...

typedef opt::none	compare
	Key comparison functor. More...

typedef opt::none	less
	Specifies binary predicate used for key compare. More...

typedef opt::v::empty_disposer	disposer
	Disposer. More...

typedef atomicity::empty_item_counter	item_counter
	Item counter. More...

typedef opt::v::relaxed_ordering	memory_model
	C++ memory ordering model. More...

typedef CDS_DEFAULT_ALLOCATOR	update_desc_allocator
	Allocator for update descriptors. More...

typedef CDS_DEFAULT_ALLOCATOR	node_allocator
	Allocator for internal nodes. More...

typedef empty_stat	stat
	Internal statistics. More...

typedef cds::backoff::empty	back_off
	Back-off strategy.

typedef cds::opt::v::rcu_throw_deadlock	rcu_check_deadlock
	RCU deadlock checking policy (only for RCU-based EllenBinTree) More...

Detailed Description

EllenBinTree traits.

Member Typedef Documentation

◆ compare

typedef opt::none cds::intrusive::ellen_bintree::traits::compare

Key comparison functor.

No default functor is provided. If the option is not specified, the less is used.

See cds::opt::compare option description for functor interface.

You should provide compare or less functor. See predicate requirements.

◆ disposer

typedef opt::v::empty_disposer cds::intrusive::ellen_bintree::traits::disposer

Disposer.

The functor used for dispose removed items. Default is opt::v::empty_disposer.

◆ hook

typedef base_hook cds::intrusive::ellen_bintree::traits::hook

Hook used (mandatory)

Possible values are: ellen_bintree::base_hook, ellen_bintree::member_hook, ellen_bintree::traits_hook.

◆ item_counter

typedef atomicity::empty_item_counter cds::intrusive::ellen_bintree::traits::item_counter

Item counter.

The type for item counter, by default it is disabled (atomicity::empty_item_counter). To enable it use atomicity::item_counter or atomicity::cache_friendly_item_counter

◆ key_extractor

typedef opt::none cds::intrusive::ellen_bintree::traits::key_extractor

Key extracting functor (mandatory)

You should explicit define a valid functor. The functor has the following prototype:

struct key_extractor {
    void operator ()( Key& dest, T const& src );
};

It should initialize dest key from src data. The functor is used to initialize internal nodes.

◆ less

typedef opt::none cds::intrusive::ellen_bintree::traits::less

Specifies binary predicate used for key compare.

See cds::opt::less option description for predicate interface.

You should provide compare or less functor. See predicate requirements.

◆ memory_model

typedef opt::v::relaxed_ordering cds::intrusive::ellen_bintree::traits::memory_model

C++ memory ordering model.

List of available memory ordering see opt::memory_model

◆ node_allocator

typedef CDS_DEFAULT_ALLOCATOR cds::intrusive::ellen_bintree::traits::node_allocator

Allocator for internal nodes.

The allocator type is used for ellen_bintree::internal_node.

◆ rcu_check_deadlock

typedef cds::opt::v::rcu_throw_deadlock cds::intrusive::ellen_bintree::traits::rcu_check_deadlock

RCU deadlock checking policy (only for RCU-based EllenBinTree)

List of available options see opt::rcu_check_deadlock

◆ stat

typedef empty_stat cds::intrusive::ellen_bintree::traits::stat

Internal statistics.

By default, internal statistics is disabled (ellen_bintree::empty_stat). To enable it use ellen_bintree::stat.

◆ update_desc_allocator

typedef CDS_DEFAULT_ALLOCATOR cds::intrusive::ellen_bintree::traits::update_desc_allocator

Allocator for update descriptors.

The allocator type is used for ellen_bintree::update_desc.

Update descriptor is helping data structure with short lifetime and it is good candidate for pooling. The number of simultaneously existing descriptors is bounded and it is limited by number of threads working with the tree. Therefore, a bounded lock-free container like cds::container::VyukovMPMCCycleQueue is a good choice for the free-list of update descriptors, see cds::memory::vyukov_queue_pool free-list implementation.

Also notice that size of update descriptor is constant and not dependent on the type of data stored in the tree so single free-list object can be used for several EllenBinTree object.

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

cds/intrusive/details/ellen_bintree_base.h

Public Types