Type traits for EllenBinTreeSet and EllenBinTreeMap. More...

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

Public Types
typedef opt::none	key_extractor
	Key extracting functor (only for `EllenBinTreeSet`) More...

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

typedef opt::none	less
	Specifies binary predicate used for key compare. 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 CDS_DEFAULT_ALLOCATOR	allocator
	Allocator for leaf 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 EllenBinTreeXXX classes) More...

typedef opt::none	copy_policy
	Key copy policy (for `EllenBinTreeMap`) More...

Detailed Description

Type traits for EllenBinTreeSet and EllenBinTreeMap.

Member Typedef Documentation

◆ allocator

typedef CDS_DEFAULT_ALLOCATOR cds::container::ellen_bintree::traits::allocator

Allocator for leaf nodes.

Each leaf node contains data stored in the container.

◆ compare

typedef opt::none cds::container::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.

◆ copy_policy

typedef opt::none cds::container::ellen_bintree::traits::copy_policy

Key copy policy (for EllenBinTreeMap)

The key copy policy defines a functor to copy leaf node's key to internal node. This policy is used only in EllenBinTreeMap. By default, assignment operator is used.

The copy functor interface is:

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

◆ item_counter

typedef atomicity::empty_item_counter cds::container::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::container::ellen_bintree::traits::key_extractor

Key extracting functor (only for EllenBinTreeSet)

This is mandatory functor for EllenBinTreeSet. It 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 of EllenBinTreeSet

◆ less

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

Specifies binary predicate used for key compare.

See cds::opt::less option description.

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

◆ memory_model

typedef opt::v::relaxed_ordering cds::container::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::container::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::container::ellen_bintree::traits::rcu_check_deadlock

RCU deadlock checking policy (only for RCU-based EllenBinTreeXXX classes)

List of available options see opt::rcu_check_deadlock

◆ stat

typedef empty_stat cds::container::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::container::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 a small number limited the number of threads working with the tree. Therefore, a bounded lock-free container like cds::container::VyukovMPMCCycleQueue is 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 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/container/details/ellen_bintree_base.h

Public Types