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

A BTree Node. More...

#include <btree.h>

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

List of all members.

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 fairport::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

template<typename K, typename V>

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

Definition at line 54 of file btree.h.

---

Constructor & Destructor Documentation

template<typename K, typename V>

virtual fairport::btree_node< K, V >::~btree_node

(

)

[inline, virtual]

Definition at line 56 of file btree.h.

---

Member Function Documentation

template<typename K, typename V>

const_iterator fairport::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.

template<typename K, typename V >

int fairport::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.

template<typename K, typename V>

const_iterator fairport::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.

template<typename K, typename V>

virtual void fairport::btree_node< K, V >::first

(

btree_iter_impl< K, V > &

iter

)

const [protected, pure virtual]

Positions the iterator at the first element on this tree.

Parameters:

[in,out]

iter

Iterator state class

Implemented in fairport::btree_node_nonleaf< K, V >, and fairport::btree_node_leaf< K, V >.

template<typename K, typename V>

virtual const K& fairport::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 fairport::subnode_leaf_block, fairport::subnode_nonleaf_block, fairport::bth_leaf_node< K, V >, fairport::bth_nonleaf_node< K, V >, fairport::bt_leaf_page< K, V >, and fairport::bt_nonleaf_page< K, V >.

template<typename K, typename V>

virtual void fairport::btree_node< K, V >::last

(

btree_iter_impl< K, V > &

iter

)

const [protected, pure virtual]

Positions the iterator at the "end" element.

Parameters:

[in,out]

iter

Iterator state class

Implemented in fairport::btree_node_nonleaf< K, V >, and fairport::btree_node_leaf< K, V >.

template<typename K, typename V>

virtual const V& fairport::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 fairport::btree_node_nonleaf< K, V >, and fairport::btree_node_leaf< K, V >.

template<typename K, typename V>

virtual void fairport::btree_node< K, V >::next

(

btree_iter_impl< K, V > &

iter

)

const [protected, pure virtual]

Moves the iterator to the next element.

Parameters:

[in,out]

iter

Iterator state class

Implemented in fairport::btree_node_nonleaf< K, V >, and fairport::btree_node_leaf< K, V >.

template<typename K, typename V>

virtual uint fairport::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 fairport::subnode_leaf_block, fairport::subnode_nonleaf_block, fairport::bth_leaf_node< K, V >, fairport::bth_nonleaf_node< K, V >, fairport::bt_leaf_page< K, V >, and fairport::bt_nonleaf_page< K, V >.

template<typename K, typename V>

virtual void fairport::btree_node< K, V >::prev

(

btree_iter_impl< K, V > &

iter

)

const [protected, pure virtual]

Moves the iterator to the previous element.

Parameters:

[in,out]

iter

Iterator state class

Implemented in fairport::btree_node_nonleaf< K, V >, and fairport::btree_node_leaf< K, V >.

---

Friends And Related Function Documentation

template<typename K, typename V>

friend class btree_node_nonleaf< K, V > [friend]

Definition at line 105 of file btree.h.

template<typename K, typename V>

friend class const_btree_node_iter< K, V > [friend]

Reimplemented in fairport::btree_node_nonleaf< K, V >, fairport::btree_node_nonleaf< node_id, subnode_info >, fairport::btree_node_leaf< K, V >, and fairport::btree_node_leaf< node_id, subnode_info >.

Definition at line 104 of file btree.h.

---

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

• fairport/util/btree.h