pstsdk::btree_node< K, V > Class Template Reference

A BTree Node. More...

#include <btree.h>

Inheritance diagram for pstsdk::btree_node< K, V >:

Collaboration diagram for pstsdk::btree_node< K, V >:

Public Types
typedef const_btree_node_iter< K, V >	const_iterator

Public Member Functions
virtual	~btree_node ()
virtual const V &	lookup (const K &key) const =0
	Looks up the associated value for a given key.
virtual const K &	get_key (uint pos) const =0
	Returns the key at the specified position.
virtual uint	num_values () const =0
	Returns the number of entries in this btree_node.
const_iterator	begin () const
	Returns a STL style iterator positioned at the first entry.
const_iterator	end () const
	Returns a STL style iterator positioned at the "end" entry.
int	binary_search (const K &key) const
	Performs a binary search over the keys of this btree_node.

Protected Member Functions
virtual void	first (btree_iter_impl< K, V > &iter) const =0
	Positions the iterator at the first element on this tree.
virtual void	last (btree_iter_impl< K, V > &iter) const =0
	Positions the iterator at the "end" element.
virtual void	next (btree_iter_impl< K, V > &iter) const =0
	Moves the iterator to the next element.
virtual void	prev (btree_iter_impl< K, V > &iter) const =0
	Moves the iterator to the previous element.

Friends
class	const_btree_node_iter< K, V >
class	btree_node_nonleaf< K, V >

Detailed Description

template<typename K, typename V>
class pstsdk::btree_node< K, V >

A BTree Node.

The fundamental type in the BTree system is the btree_node. It provides the generic interface which is refined by the other classes.

Parameters

K	The key type. Must be LessThan comparable.
V	The value type

Definition at line 51 of file btree.h.

Member Typedef Documentation

const_iterator

template<typename K , typename V >

typedef const_btree_node_iter<K,V> pstsdk::btree_node< K, V >::const_iterator

Definition at line 54 of file btree.h.

Constructor & Destructor Documentation

~btree_node()

template<typename K , typename V >

virtual pstsdk::btree_node< K, V >::~btree_node ( )

inlinevirtual

Definition at line 56 of file btree.h.

Member Function Documentation

begin()

template<typename K , typename V >

const_iterator pstsdk::btree_node< K, V >::begin ( ) const

inline

Returns a STL style iterator positioned at the first entry.

Supports iteration over the value members of this btree. This method returns an iterator positioned on the first element of the tree. One can then

Returns

An iterator over the values in this btree

Definition at line 85 of file btree.h.

binary_search()

template<typename K , typename V >

int pstsdk::btree_node< K, V >::binary_search

(

const K &

key

)

const

Performs a binary search over the keys of this btree_node.

Parameters

[in]

key

The key to lookup

Returns

The position of the key, or of the entry which would contain it

Definition at line 264 of file btree.h.

end()

template<typename K , typename V >

const_iterator pstsdk::btree_node< K, V >::end ( ) const

inline

Returns a STL style iterator positioned at the "end" entry.

Supports iteration over the value members of this btree. This method returns an iterator positioned past the last element of this btree.

Returns

An iterator over the values in this btree

Definition at line 93 of file btree.h.

first()

template<typename K , typename V >

virtual void pstsdk::btree_node< K, V >::first ( btree_iter_impl< K, V > &  iter ) const

protectedpure virtual

Positions the iterator at the first element on this tree.

Parameters

[in,out]

iter

Iterator state class

Implemented in pstsdk::btree_node_leaf< K, V >, pstsdk::btree_node_nonleaf< K, V >, and pstsdk::btree_node_nonleaf< node_id, subnode_info >.

get_key()

template<typename K , typename V >

virtual const K & pstsdk::btree_node< K, V >::get_key ( uint  pos ) const

pure virtual

Returns the key at the specified position.

This is specific to this btree_node, not the entire tree

Parameters

[in]

pos

The position to retrieve the key for

Returns

The key at the requested position

Implemented in pstsdk::bth_nonleaf_node< K, V >, pstsdk::bth_leaf_node< K, V >, pstsdk::subnode_nonleaf_block, pstsdk::subnode_leaf_block, pstsdk::bt_nonleaf_page< K, V >, and pstsdk::bt_leaf_page< K, V >.

last()

template<typename K , typename V >

virtual void pstsdk::btree_node< K, V >::last ( btree_iter_impl< K, V > &  iter ) const

protectedpure virtual

Positions the iterator at the "end" element.

Parameters

[in,out]

iter

Iterator state class

Implemented in pstsdk::btree_node_leaf< K, V >, pstsdk::btree_node_nonleaf< K, V >, and pstsdk::btree_node_nonleaf< node_id, subnode_info >.

lookup()

template<typename K , typename V >

virtual const V & pstsdk::btree_node< K, V >::lookup ( const K &  key ) const

pure virtual

Looks up the associated value for a given key.

This will defer to child btree_nodes as appropriate

Exceptions

key_not_found<K>

if the requested key is not in this btree

Parameters

[in]

key

The key to lookup

Returns

The associated value

Implemented in pstsdk::btree_node_leaf< K, V >, pstsdk::btree_node_nonleaf< K, V >, pstsdk::btree_node_leaf< node_id, subnode_info >, and pstsdk::btree_node_nonleaf< node_id, subnode_info >.

next()

template<typename K , typename V >

virtual void pstsdk::btree_node< K, V >::next ( btree_iter_impl< K, V > &  iter ) const

protectedpure virtual

Moves the iterator to the next element.

Parameters

[in,out]

iter

Iterator state class

Implemented in pstsdk::btree_node_leaf< K, V >, pstsdk::btree_node_nonleaf< K, V >, pstsdk::btree_node_leaf< node_id, subnode_info >, and pstsdk::btree_node_nonleaf< node_id, subnode_info >.

num_values()

template<typename K , typename V >

virtual uint pstsdk::btree_node< K, V >::num_values ( ) const

pure virtual

Returns the number of entries in this btree_node.

This is specific to this btree_node, not the entire tree

Returns

The number of keys in this btree_node

Implemented in pstsdk::bth_nonleaf_node< K, V >, pstsdk::bth_leaf_node< K, V >, pstsdk::subnode_nonleaf_block, pstsdk::subnode_leaf_block, pstsdk::bt_nonleaf_page< K, V >, and pstsdk::bt_leaf_page< K, V >.

prev()

template<typename K , typename V >

virtual void pstsdk::btree_node< K, V >::prev ( btree_iter_impl< K, V > &  iter ) const

protectedpure virtual

Moves the iterator to the previous element.

Parameters

[in,out]

iter

Iterator state class

Implemented in pstsdk::btree_node_leaf< K, V >, pstsdk::btree_node_nonleaf< K, V >, pstsdk::btree_node_leaf< node_id, subnode_info >, and pstsdk::btree_node_nonleaf< node_id, subnode_info >.

Friends And Related Symbol Documentation

btree_node_nonleaf< K, V >

template<typename K , typename V >

friend class btree_node_nonleaf< K, V >

friend

Definition at line 99 of file btree.h.

const_btree_node_iter< K, V >

template<typename K , typename V >

friend class const_btree_node_iter< K, V >

friend

Definition at line 99 of file btree.h.

---

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

• pstsdk/util/btree.h