Main Page Namespace List Class Hierarchy Compound List File List Namespace Members Compound Members File Members

CdbBdbSAbsBtree< K, FCP, ORDER > Class Template Reference

An abstract class for B-tree (balanced tree). More...

#include <CdbBdbSAbsBtree.hh>

Inheritance diagram for CdbBdbSAbsBtree< K, FCP, ORDER >:


Public Member Functions
	CdbBdbSAbsBtree ()
	Default constructor.
virtual	~CdbBdbSAbsBtree ()
	Destructor.
void	dump (std::ostream &o) const
	Dump the tree.
void	insert (const K &key)
	Insert a key into the tree.
void	remove (const K &key)
	Remove a key from the tree.
bool	search (const K &key) const
	Search a key in the tree.
bool	search (const K &key, K &result) const
	Extended search for a key in the tree.
bool	fuzzySearch (const K &key, K &result) const
	Search a key in the tree using "fuzzy" search logic.
void	reset ()
	Reset the tree.
CdbItr< K >	iterator () const
	Get an instance of an iterator.
Protected Types
enum	{ N = ORDER::N }
Protected Member Functions
virtual d_ULong	root () const=0
	Get a root node of the B-tree.
virtual void	set_root (d_ULong node)=0
	Set new root node of the B-tree.
virtual CdbBdbSBtreeNode< K, ORDER >	readNode (d_ULong node) const=0
	Get a copy of specified node.
virtual void	updateNode (d_ULong node, const CdbBdbSBtreeNode< K, ORDER > &value)=0
	Save back the value of specified node.
virtual d_ULong	allocate (d_ULong parent=0)=0
	Allocator.
virtual void	release (d_ULong node)=0
	Disposer.
Friends
class	CdbBdbSAbsBtreeItr< K, FCP, ORDER >

Detailed Description

template<class K, class FCP = CdbBdbSBtreeDefaultFCP<K>, class ORDER = CdbBdbSBtreeDefaultOrder>
class CdbBdbSAbsBtree< K, FCP, ORDER >

An abstract class for B-tree (balanced tree).

This template class implements the corresponding B-tree algorithms for Objectivity embedded classes. The concrete storage for the B-tree data structures is provided by derived classes.

The template is parametrized by mean of the following parameters:

K - is a type of keys. This type has to provide the following methods:

default constructor copy constructor destructor

and operators:

= == <= > << (into std::ostream)

FCP - this is a policy class that is expected to provide the only method:

class ... { public: static bool match( const K& source, const K& target ); };

This meathod is used for one-directional comparision of two keys. This operation is meant to answer a question if specified "source" key matches the "target" one.

It's not nessesary true that if "source" matches the "target" then the "targed" would match the "source" one.

The meaning of the "match" is up to the implementation of a concrete policy and type of keys (K).

ORDER - is a utility class with the only usable enumeration specifying an order of the tree. Here is expected interface of this class:

class <name > ... { public: enum { N = }; };

The reason why we're usingthis tricky way to specify the order instead of the non-class template parameter, like "unsigned ORDER", is that teh current version of the DDL compiler does not seem to support this kind of syntax.

Definition at line 89 of file CdbBdbSAbsBtree.hh.

Member Enumeration Documentation

template<class K, class FCP = CdbBdbSBtreeDefaultFCP<K>, class ORDER = CdbBdbSBtreeDefaultOrder>

anonymous enum [protected]

Enumeration values:

N

Definition at line 98 of file CdbBdbSAbsBtree.hh.

Constructor & Destructor Documentation

template<class K, class FCP, class ORDER>

CdbBdbSAbsBtree< K, FCP, ORDER >::CdbBdbSAbsBtree ( )

Default constructor.
Creates an empty tree.
Definition at line 22 of file CdbBdbSAbsBtree.cc.

template<class K, class FCP, class ORDER>

CdbBdbSAbsBtree< K, FCP, ORDER >::~CdbBdbSAbsBtree ( ) [virtual]

Destructor.
Destroys the tree.
Definition at line 28 of file CdbBdbSAbsBtree.cc.

Member Function Documentation

template<class K, class FCP = CdbBdbSBtreeDefaultFCP<K>, class ORDER = CdbBdbSBtreeDefaultOrder>

virtual d_ULong CdbBdbSAbsBtree< K, FCP, ORDER >::allocate ( d_ULong parent = 0 ) [protected, pure virtual]

Allocator.
To be implemented by a storage provider of a derived class.
Implemented in CdbBdbSBtreeP< K, FCP, ORDER >.
Referenced by CdbBdbSAbsBtree< K, FCP, ORDER >::insert().

template<class K, class FCP, class ORDER>

void CdbBdbSAbsBtree< K, FCP, ORDER >::dump ( std::ostream & o ) const

Dump the tree.
The dump is done onto a stream specified through the only parameter of the method.
Definition at line 35 of file CdbBdbSAbsBtree.cc.
References CdbBdbSAbsBtree< K, FCP, ORDER >::root().

template<class K, class FCP, class ORDER>

bool CdbBdbSAbsBtree< K, FCP, ORDER >::fuzzySearch ( const K & key,

K & result

) const

Search a key in the tree using "fuzzy" search logic.
This method will use "fuzzy" logic to search for a key, which is very similar to the one specified on the input. The "similarity" is defined throught this (Btree) class template parameter.
If there is such an entry then the method will return "true" and a value of the found ("similar") key.
Definition at line 269 of file CdbBdbSAbsBtree.cc.
References CdbBdbSAbsBtree< K, FCP, ORDER >::root().

template<class K, class FCP, class ORDER>

void CdbBdbSAbsBtree< K, FCP, ORDER >::insert ( const K & key )

Insert a key into the tree.
Insert specified key into the tree. If the tree alredy has such an element then just ignore it.
Definition at line 44 of file CdbBdbSAbsBtree.cc.
References CdbBdbSAbsBtree< K, FCP, ORDER >::allocate(), CdbBdbSBtreeNode< K, ORDER >::child, CdbBdbSBtreeNode< K, ORDER >::isLeaf, CdbBdbSBtreeNode< K, ORDER >::key, CdbBdbSBtreeNode< K, ORDER >::n, CdbBdbSAbsBtree< K, FCP, ORDER >::N, CdbBdbSBtreeNode< K, ORDER >::parent, CdbBdbSAbsBtree< K, FCP, ORDER >::readNode(), CdbBdbSAbsBtree< K, FCP, ORDER >::release(), CdbBdbSAbsBtree< K, FCP, ORDER >::root(), CdbBdbSAbsBtree< K, FCP, ORDER >::search(), and CdbBdbSAbsBtree< K, FCP, ORDER >::updateNode().

template<class K, class FCP, class ORDER>

CdbItr< K > CdbBdbSAbsBtree< K, FCP, ORDER >::iterator ( ) const

Get an instance of an iterator.
This kind of iterator provides "non-sorted" access to the keys.
Definition at line 290 of file CdbBdbSAbsBtree.cc.

template<class K, class FCP = CdbBdbSBtreeDefaultFCP<K>, class ORDER = CdbBdbSBtreeDefaultOrder>

virtual CdbBdbSBtreeNode<K,ORDER> CdbBdbSAbsBtree< K, FCP, ORDER >::readNode ( d_ULong node ) const [protected, pure virtual]

Get a copy of specified node.
To be implemented by a storage provider of a derived class.
Implemented in CdbBdbSBtreeP< K, FCP, ORDER >.
Referenced by CdbBdbSAbsBtree< K, FCP, ORDER >::insert(), CdbBdbSAbsBtree< K, FCP, ORDER >::remove(), and CdbBdbSAbsBtree< K, FCP, ORDER >::search().

template<class K, class FCP = CdbBdbSBtreeDefaultFCP<K>, class ORDER = CdbBdbSBtreeDefaultOrder>

virtual void CdbBdbSAbsBtree< K, FCP, ORDER >::release ( d_ULong node ) [protected, pure virtual]

Disposer.
To be implemented by a storage provider of a derived class.
Implemented in CdbBdbSBtreeP< K, FCP, ORDER >.
Referenced by CdbBdbSAbsBtree< K, FCP, ORDER >::insert().

template<class K, class FCP, class ORDER>

void CdbBdbSAbsBtree< K, FCP, ORDER >::remove ( const K & key )

Remove a key from the tree.
Remove specified key from the tree. If the tree does not have such an element then just ignore it.
Definition at line 169 of file CdbBdbSAbsBtree.cc.
References CdbBdbSBtreeNode< K, ORDER >::child, CdbBdbSBtreeNode< K, ORDER >::isLeaf, CdbBdbSBtreeNode< K, ORDER >::key, CdbBdbSBtreeNode< K, ORDER >::n, CdbBdbSAbsBtree< K, FCP, ORDER >::readNode(), CdbBdbSAbsBtree< K, FCP, ORDER >::root(), and CdbBdbSAbsBtree< K, FCP, ORDER >::updateNode().

template<class K, class FCP, class ORDER>

void CdbBdbSAbsBtree< K, FCP, ORDER >::reset ( )

Reset the tree.
This operation will remove all elements from the tree except it's root node. The root node will get 0 keys.
Definition at line 281 of file CdbBdbSAbsBtree.cc.
References CdbBdbSAbsBtree< K, FCP, ORDER >::root().

template<class K, class FCP = CdbBdbSBtreeDefaultFCP<K>, class ORDER = CdbBdbSBtreeDefaultOrder>

virtual d_ULong CdbBdbSAbsBtree< K, FCP, ORDER >::root ( ) const [protected, pure virtual]

Get a root node of the B-tree.
To be implemented by a storage provider of a derived class.
Implemented in CdbBdbSBtreeP< K, FCP, ORDER >.
Referenced by CdbBdbSAbsBtree< K, FCP, ORDER >::dump(), CdbBdbSAbsBtree< K, FCP, ORDER >::fuzzySearch(), CdbBdbSAbsBtree< K, FCP, ORDER >::insert(), CdbBdbSAbsBtree< K, FCP, ORDER >::remove(), CdbBdbSAbsBtree< K, FCP, ORDER >::reset(), and CdbBdbSAbsBtree< K, FCP, ORDER >::search().

template<class K, class FCP, class ORDER>

bool CdbBdbSAbsBtree< K, FCP, ORDER >::search ( const K & key,

K & result

) const

Extended search for a key in the tree.
This method will look for the presence of specified key in the tree.
If there is such an entry then the method will return "true" and a value of the found ("similar") key.
Definition at line 239 of file CdbBdbSAbsBtree.cc.
References CdbBdbSBtreeNode< K, ORDER >::key, CdbBdbSBtreeNode< K, ORDER >::n, CdbBdbSAbsBtree< K, FCP, ORDER >::readNode(), and CdbBdbSAbsBtree< K, FCP, ORDER >::root().

template<class K, class FCP, class ORDER>

bool CdbBdbSAbsBtree< K, FCP, ORDER >::search ( const K & key ) const

Search a key in the tree.
This method will only look for the presence of specified key in the tree. If there is such an entry it will just return "true".
Definition at line 229 of file CdbBdbSAbsBtree.cc.
References CdbBdbSAbsBtree< K, FCP, ORDER >::root().
Referenced by CdbBdbSAbsBtree< K, FCP, ORDER >::insert().

template<class K, class FCP = CdbBdbSBtreeDefaultFCP<K>, class ORDER = CdbBdbSBtreeDefaultOrder>

virtual void CdbBdbSAbsBtree< K, FCP, ORDER >::set_root ( d_ULong node ) [protected, pure virtual]

Set new root node of the B-tree.
To be implemented by a storage provider of a derived class.
Implemented in CdbBdbSBtreeP< K, FCP, ORDER >.

template<class K, class FCP = CdbBdbSBtreeDefaultFCP<K>, class ORDER = CdbBdbSBtreeDefaultOrder>

virtual void CdbBdbSAbsBtree< K, FCP, ORDER >::updateNode ( d_ULong node,

const CdbBdbSBtreeNode< K, ORDER > & value

) [protected, pure virtual]

Save back the value of specified node.
To be implemented by a storage provider of a derived class.
Implemented in CdbBdbSBtreeP< K, FCP, ORDER >.
Referenced by CdbBdbSAbsBtree< K, FCP, ORDER >::insert(), and CdbBdbSAbsBtree< K, FCP, ORDER >::remove().

Friends And Related Function Documentation

template<class K, class FCP = CdbBdbSBtreeDefaultFCP<K>, class ORDER = CdbBdbSBtreeDefaultOrder>

friend class CdbBdbSAbsBtreeItr< K, FCP, ORDER > [friend]

Definition at line 94 of file CdbBdbSAbsBtree.hh.

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

Generated on Mon Dec 5 18:22:18 2005 for CDB by

1.3-rc3

CdbBdbSAbsBtree< K, FCP, ORDER > Class Template Reference

Public Member Functions

Protected Types

Protected Member Functions