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

Represents a non-leaf node in a BTree structure. More...

#include <btree.h>

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

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

Public Member Functions
virtual	~btree_node_nonleaf ()
const V &	lookup (const K &key) const
	Looks up the associated value for a given key.
Public Member Functions inherited from pstsdk::btree_node< K, V >
virtual	~btree_node ()
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 btree_node< K, V > *	get_child (uint i)=0
	Returns the child btree_node at the requested location.
virtual const btree_node< K, V > *	get_child (uint i) const =0
	Returns the child btree_node at the requested location.
void	first (btree_iter_impl< K, V > &iter) const
	Positions the iterator at the first element on this tree.
void	last (btree_iter_impl< K, V > &iter) const
	Positions the iterator at the "end" element.
void	next (btree_iter_impl< K, V > &iter) const
	Moves the iterator to the next element.
void	prev (btree_iter_impl< K, V > &iter) const
	Moves the iterator to the previous element.

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

Additional Inherited Members
Public Types inherited from pstsdk::btree_node< K, V >
typedef const_btree_node_iter< K, V >	const_iterator

Detailed Description

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

Represents a non-leaf node in a BTree structure.

Classes which model a non-leaf of a BTree structure inherit from this. They have a total of four simple virtual functions to implement:

• num_values, from btree_node
• get_key(uint pos), from btree_node
• get_child(uint pos)
• get_child(uint pos) const, const version of above

  Parameters

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

Definition at line 171 of file btree.h.

Constructor & Destructor Documentation

~btree_node_nonleaf()

template<typename K , typename V >

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

inlinevirtual

Definition at line 174 of file btree.h.

Member Function Documentation

first()

template<typename K , typename V >

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

protectedvirtual

Positions the iterator at the first element on this tree.

Parameters

[in,out]

iter

Iterator state class

Implements pstsdk::btree_node< K, V >.

Definition at line 369 of file btree.h.

get_child() [1/2]

template<typename K , typename V >

virtual const btree_node< K, V > * pstsdk::btree_node_nonleaf< K, V >::get_child ( uint  i ) const

protectedpure virtual

Returns the child btree_node at the requested location.

Parameters

[in]

i

The position at which to get the child

Returns

a non-owning pointer of the child btree_node

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

get_child() [2/2]

template<typename K , typename V >

virtual btree_node< K, V > * pstsdk::btree_node_nonleaf< K, V >::get_child ( uint  i )

protectedpure virtual

Returns the child btree_node at the requested location.

Parameters

[in]

i

The position at which to get the child

Returns

a non-owning pointer of the child btree_node

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

last()

template<typename K , typename V >

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

protectedvirtual

Positions the iterator at the "end" element.

Parameters

[in,out]

iter

Iterator state class

Implements pstsdk::btree_node< K, V >.

Definition at line 376 of file btree.h.

lookup()

template<typename K , typename V >

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

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

Implements pstsdk::btree_node< K, V >.

Definition at line 358 of file btree.h.

next()

template<typename K , typename V >

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

protectedvirtual

Moves the iterator to the next element.

Parameters

[in,out]

iter

Iterator state class

Implements pstsdk::btree_node< K, V >.

Definition at line 383 of file btree.h.

prev()

template<typename K , typename V >

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

protectedvirtual

Moves the iterator to the previous element.

Parameters

[in,out]

iter

Iterator state class

Implements pstsdk::btree_node< K, V >.

Definition at line 404 of file btree.h.

Friends And Related Symbol Documentation

btree_node_leaf< K, V >

template<typename K , typename V >

friend class btree_node_leaf< K, V >

friend

Definition at line 187 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 187 of file btree.h.

---

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

• pstsdk/util/btree.h