Extended structure of a leaf node in memory. More...

Public Types
typedef _Alloc::template rebind< leaf_node >::other	alloc_type
	Define an related allocator for the leaf_node structs.
Public Member Functions
void	initialize ()
	Set variables to initial values.
bool	isfull () const
	True if the node's slots are full.
bool	isfew () const
	True if few used entries, less than half full.
bool	isunderflow () const
	True if node has too few entries.
void	set_slot (unsigned short slot, const pair_type &value)
	Set the (key,data) pair in slot.
void	set_slot (unsigned short slot, const key_type &key)
	Set the key pair in slot.
Public Attributes
leaf_node *	prevleaf
	Double linked list pointers to traverse the leaves.
leaf_node *	nextleaf
	Double linked list pointers to traverse the leaves.
key_type	slotkey [leafslotmax]
	Keys of children or data pointers.
data_type	slotdata [used_as_set?1:leafslotmax]
	Array of data.

Detailed Description

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>
struct stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node

Extended structure of a leaf node in memory.

Contains pairs of keys and data items. Key and data slots are kept in separate arrays, because the key array is traversed very often compared to accessing the data items.

Definition at line 319 of file btree.h.

Member Typedef Documentation

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

typedef _Alloc::template rebind<leaf_node>::other stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::alloc_type

Define an related allocator for the leaf_node structs.

Definition at line 322 of file btree.h.

Member Function Documentation

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::initialize ( ) [inline]

Set variables to initial values.

Definition at line 337 of file btree.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::nextleaf, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::prevleaf.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::allocate_leaf().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::isfew ( ) const [inline]

True if few used entries, less than half full.

Definition at line 350 of file btree.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::minleafslots, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::node::slotuse.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::isfull ( ) const [inline]

True if the node's slots are full.

Definition at line 344 of file btree.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leafslotmax, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::node::slotuse.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::isunderflow ( ) const [inline]

True if node has too few entries.

Definition at line 356 of file btree.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::minleafslots, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::node::slotuse.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::set_slot	(	unsigned short	slot,
		const pair_type &	value
	)		`[inline]`

Set the (key,data) pair in slot.

Overloaded function used by bulk_load().

Definition at line 363 of file btree.h.

References BTREE_ASSERT, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::slotdata, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::slotkey, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::node::slotuse, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::used_as_set.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::set_slot	(	unsigned short	slot,
		const key_type &	key
	)		`[inline]`

Set the key pair in slot.

Overloaded function used by bulk_load().

Definition at line 373 of file btree.h.

References BTREE_ASSERT, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::slotkey, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::node::slotuse, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::used_as_set.

Member Data Documentation

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

leaf_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::nextleaf

Double linked list pointers to traverse the leaves.

Definition at line 328 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::copy_recursive(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::initialize(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::iterator::operator++(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_iterator::operator++(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::reverse_iterator::operator--(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_reverse_iterator::operator--(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::print_leaves(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore_node(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::split_leaf_node().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

leaf_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::prevleaf

Double linked list pointers to traverse the leaves.

Definition at line 325 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::copy_recursive(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::initialize(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::reverse_iterator::operator++(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_reverse_iterator::operator++(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::iterator::operator--(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_iterator::operator--(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore_node(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::split_leaf_node().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

data_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::slotdata[used_as_set?1:leafslotmax]

Array of data.

Definition at line 334 of file btree.h.

Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::iterator::data(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_iterator::data(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::reverse_iterator::data(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_reverse_iterator::data(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::set_slot().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

key_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::slotkey[leafslotmax]

Keys of children or data pointers.

Definition at line 331 of file btree.h.

Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::iterator::key(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_iterator::key(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::reverse_iterator::key(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_reverse_iterator::key(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::set_slot().

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

stx/btree.h

Public Types

Public Member Functions

Public Attributes

Detailed Description

Member Typedef Documentation

Member Function Documentation

Member Data Documentation