TLBTree< T, _OP > Class Template Reference

Standard in-memory B-Tree (Bayer & McCreight) template. More...

#include <tlbtree.h>

Collaboration diagram for TLBTree< T, _OP >:

[legend]List of all members.


Public Member Functions
	TLBTree (int _m=16, const _OP &op=_OP())
	Create a B-Tree.
	~TLBTree ()
	Destructor: Deletes tree.
void	clear ()
	Clear the whole tree.
bool	IsEmpty () const
	Is the tree empty? Runtime O(1).
size_t	CountElements () const
	Count number of stored elements:.
size_t	CountNodes () const
	Count number of tree nodes:.
size_t	GetNodeSize () const
template<typename K> T *	search (const K &key)
	Find element in the tree.
template<typename K> T *	SearchNeighbours (const K &key, T prev, T next)
	Find the neighbours of passed key.
T *	GetSmallest ()
	Get smallest/largest element in the tree (or NULL):.
T *	GetLargest ()
int	store (const T &e, bool allow_update, T *oldval=NULL)
	Store passed elemet in the tree.
template<typename K> int	remove (const K &key, T *e=NULL)
	Remove passed element from tree.
int	RemoveSmallest (T *e=NULL)
	Special version of Remove():.
int	RemoveLargest (T *e=NULL)
Public Attributes
_OP	OP
Private Member Functions
Node *	_AllocLeaf ()
	Allocate a new leaf node; parent=NULL for root:.
Node *	_AllocNonLeaf ()
Node *	_FreeNode (Node *n)
	Deallocate a node:.
void	_DeleteTree (Node *tn)
	Recursively delete tree.
template<typename K> T *	_Find (const K &key, Node *tn)
	Find element in subtree.
Node *	_FindSmallestLeaf (Node *n)
	Find leaf node with smallest element in subtree.
Node *	_FindLargestLeaf (Node *n)
	Find leaf node with largest element in subtree.
T *	_FindSmallest (Node *n)
	Find smallest/largest element in subtree.
T *	_FindLargest (Node *n)
template<typename K> T *	_FindNeighbours (const K &key, Node tn, T p, T *n)
	Find element in subtree.
int	_Store (Node tn, const T &e, Node split, bool allow_update, T oldval)
	Store a node in the tree.
bool	_HandleUnderflow (Node *tn, int idx)
	Handle underflow in tn->down[idx].
void	_HandleRootUnderflow ()
	Used by remove routines:.
bool	_MoveSmallest (Node tn, T ent)
	Move smallest entry in passed subtree to passed entry.
template<typename K> int	_Remove (Node tn, const K &key, T e)
	Remove element from tree.
int	_RemoveSL (Node tn, int sl, T e)
	Used by RemoveSmallest() / RemoveLargest():.
int	_DoRemoveSL (int sl, T *e)
	USed by RemoveSmallest() / RemoveLargest():.
size_t	_CountElements (Node *tn) const
	Recursively count number of elements in subtree.
size_t	_CountNodes (Node *tn) const
	Recursvely count number of nodes.
	TLBTree (const TLBTree &)
	Do not use these:.
void	operator= (const TLBTree &)
Private Attributes
int	m
	Min number of elements per tree node; max number is 2*m.
Node *	root
	Tree root.
T	tmp
	Temporary element for split/join operations.

Detailed Description

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
class TLBTree< T, _OP >

Standard in-memory B-Tree (Bayer & McCreight) template.

Author:: Wolfgang Wieser ] wwieser (a) gmx <*> de [

Implements standard B-Tree:

Each tree node stores between m and 2*m elements (exception: the root node may store less.)
A node with k keys has k+1 children.
All leaves are on the same level.

B-Trees allow operations store(), remove(), search() (and FindNeighbours()/Smallest/Largest) in O(log(n)) runtime. Memory consumption overhead is never worse than 50% (unless the tree is nearly empty, i.e. O(m) elements).

NOTE: TLBTree will move data when re-balancing the tree. This means that you must NOT rely on pointers to elements (which are stored in the tree) to be valid after an operation which can cause re-ordering. (Such operations include all operations which add or remove element(s).)

Thread safety: The complete tree must be protected by a mutex for all "write" operations.

WHAT TO USE FOR <T>: This class is probably most useful for T being a simple type (integer, unique pointers to a class or small data-only structures). You may use any POD type or any struct/class which is a "plain data type" (PDT; see defop.h) and even for "complex data types" as long as you can provide the required operator plugin OP and it has a working default constructor and a working copy constructor (both for temporaries).

This class is NOT "C++-safe", i.e. do not use the assignment operator or the copy constructor (these are private).

Definition at line 78 of file tlbtree.h.

Constructor & Destructor Documentation

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

TLBTree< T, _OP >::TLBTree ( const TLBTree< T, _OP > & ) [private]

Do not use these:.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

TLBTree< T, _OP >::TLBTree ( int _m = 16,

const _OP & op = _OP()

) [inline]

Create a B-Tree.

Parameters:

_m: Min number of number of elements per tree node; max number is 2*m. Must be at least 2; powers of 2 preferred.

op: Operator template to use for the elements. See TLDefaultOperators_CDT<T>.

Definition at line 561 of file tlbtree.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

TLBTree< T, _OP >::~TLBTree ( ) [inline]

Destructor: Deletes tree.

Definition at line 564 of file tlbtree.h.

Member Function Documentation

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

Node* TLBTree< T, _OP >::_AllocLeaf ( ) [inline, private]

Allocate a new leaf node; parent=NULL for root:.

For internal use only.

Returns NULL on alloc failure.

Definition at line 230 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_AllocNonLeaf(), TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_Store(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::store().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

Node* TLBTree< T, _OP >::_AllocNonLeaf ( ) [inline, private]

For internal use only.

Allocate non-leaf node:

Definition at line 236 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_Store(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::store().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

size_t TLBTree< T, _OP >::_CountElements ( Node * tn ) const [inline, private]

Recursively count number of elements in subtree.

For internal use only.

Definition at line 532 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_CountElements(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::CountElements().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

size_t TLBTree< T, _OP >::_CountNodes ( Node * tn ) const [inline, private]

Recursvely count number of nodes.

For internal use only.

Definition at line 541 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_CountNodes(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::CountNodes().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

void TLBTree< T, _OP >::_DeleteTree ( Node * tn ) [inline, private]

Recursively delete tree.

For internal use only.

Definition at line 253 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_DeleteTree(), TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::clear(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::~TLBTree().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

int TLBTree< T, _OP >::_DoRemoveSL ( int sl,

T * e

) [inline, private]

USed by RemoveSmallest() / RemoveLargest():.

For internal use only.

Definition at line 496 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::RemoveLargest(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::RemoveSmallest().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

template<typename K>

T* TLBTree< T, _OP >::_Find ( const K & key,

Node * tn

) [inline, private]

Find element in subtree.

For internal use only.

Definition at line 263 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::search().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

T* TLBTree< T, _OP >::_FindLargest ( Node * n ) [inline, private]

Definition at line 282 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_FindNeighbours(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::GetLargest().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

Node* TLBTree< T, _OP >::_FindLargestLeaf ( Node * n ) [inline, private]

Find leaf node with largest element in subtree.

For internal use only.

Definition at line 277 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_FindLargest().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

template<typename K>

T* TLBTree< T, _OP >::_FindNeighbours ( const K & key,

Node * tn,

T ** p,

T ** n

) [inline, private]

Find element in subtree.

For internal use only.

Definition at line 286 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_FindNeighbours(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::SearchNeighbours().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

T* TLBTree< T, _OP >::_FindSmallest ( Node * n ) [inline, private]

Find smallest/largest element in subtree.

For internal use only.

Definition at line 280 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_FindNeighbours(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::GetSmallest().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

Node* TLBTree< T, _OP >::_FindSmallestLeaf ( Node * n ) [inline, private]

Find leaf node with smallest element in subtree.

For internal use only.

Definition at line 274 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_FindSmallest().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

Node* TLBTree< T, _OP >::_FreeNode ( Node * n ) [inline, private]

Deallocate a node:.

For internal use only.

Must already have been removed from the tree and all elements cleaned up (i.e. n->nelem==0).

Definition at line 249 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_DeleteTree(), TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_HandleRootUnderflow(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_HandleUnderflow().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

void TLBTree< T, _OP >::_HandleRootUnderflow ( ) [inline, private]

Used by remove routines:.

For internal use only.

Definition at line 432 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_DoRemoveSL(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::remove().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

bool TLBTree< T, _OP >::_HandleUnderflow ( Node * tn,

int idx

) [inline, private]

Handle underflow in tn->down[idx].

For internal use only.

Returns:
0 -> OK 1 -> underflow in tn.

Definition at line 386 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_MoveSmallest(), TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_Remove(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_RemoveSL().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

bool TLBTree< T, _OP >::_MoveSmallest ( Node * tn,

T * ent

) [inline, private]

Move smallest entry in passed subtree to passed entry.

For internal use only.

Returns:
1 -> underflow 0 -> OK

Definition at line 447 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_MoveSmallest(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_Remove().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

template<typename K>

int TLBTree< T, _OP >::_Remove ( Node * tn,

const K & key,

T * e

) [inline, private]

Remove element from tree.

For internal use only.

Returns:
2 -> underflow
1 -> not deleted /not found)
0 -> OK, deleted

Definition at line 464 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_Remove(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::remove().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

int TLBTree< T, _OP >::_RemoveSL ( Node * tn,

int sl,

T * e

) [inline, private]

Used by RemoveSmallest() / RemoveLargest():.

For internal use only.

Definition at line 482 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_DoRemoveSL(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_RemoveSL().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

int TLBTree< T, _OP >::_Store ( Node * tn,

const T & e,

Node ** split,

bool allow_update,

T * oldval

) [inline, private]

Store a node in the tree.

For internal use only.

Returns:
0,1 -> see store().
3 -> split node

Definition at line 311 of file tlbtree.h.
Referenced by TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_Store(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::store().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

void TLBTree< T, _OP >::clear ( ) [inline]

Clear the whole tree.

Definition at line 567 of file tlbtree.h.
Referenced by VM::VMLinker::LinkAll().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

size_t TLBTree< T, _OP >::CountElements ( ) const [inline]

Count number of stored elements:.
Runtime is O(k) (k = numaber of nodes <= number of elements/m)
Definition at line 579 of file tlbtree.h.
Referenced by main().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

size_t TLBTree< T, _OP >::CountNodes ( ) const [inline]

Count number of tree nodes:.

Definition at line 583 of file tlbtree.h.
Referenced by main().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

T* TLBTree< T, _OP >::GetLargest ( ) [inline]

Definition at line 627 of file tlbtree.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

size_t TLBTree< T, _OP >::GetNodeSize ( ) const [inline]

Get size of a tree node as used internally to store the data: Total tree memory consumption is: sizeof(TLBTree) + CountNodes()*GetNodeSize()
Definition at line 589 of file tlbtree.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

T* TLBTree< T, _OP >::GetSmallest ( ) [inline]

Get smallest/largest element in the tree (or NULL):.
Runtime is O(depth) ( depth = O(log(n/m)) ).
Definition at line 625 of file tlbtree.h.
Referenced by VM::VMLinker::_SQPeek().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

bool TLBTree< T, _OP >::IsEmpty ( ) const [inline]

Is the tree empty? Runtime O(1).

Definition at line 571 of file tlbtree.h.
Referenced by main().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

void TLBTree< T, _OP >::operator= ( const TLBTree< T, _OP > & ) [private]

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

template<typename K>

int TLBTree< T, _OP >::remove ( const K & key,

T * e = NULL

) [inline]

Remove passed element from tree.
Runtime O(log(n)) (n = number of elements in the tree) If e is non-null, store a copy of the found element in *e (using OP.ass()) before removing it. It is valid to write T key_elem=<initialize key>; btree.remove(key_elem,&key_elem);
Returns:
0 -> OK, element removed
1 -> element not removed (not in tree)

Definition at line 677 of file tlbtree.h.
Referenced by main().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

int TLBTree< T, _OP >::RemoveLargest ( T * e = NULL ) [inline]

Definition at line 696 of file tlbtree.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

int TLBTree< T, _OP >::RemoveSmallest ( T * e = NULL ) [inline]

Special version of Remove():.
Remove smallest/largest entry from the tree. If e is non-null, store a copy of the element in *e (using OP.ass()) before removing it.
Returns:
0 -> OK, element removed
1 -> tree empty

Definition at line 694 of file tlbtree.h.
Referenced by VM::VMLinker::_SQPop().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

template<typename K>

T* TLBTree< T, _OP >::search ( const K & key ) [inline]

Find element in the tree.
Runtime O(log(n)) (n = number of elements in the tree) Returns pointer to the element or NULL.
Note:
You may change the element as long as you do not change its ordering value (which is used by OP.lt()) so that the tree stays consistent (=sorted).

Definition at line 601 of file tlbtree.h.
Referenced by VM::VMLinker::_SQQuery(), and main().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

template<typename K>

T* TLBTree< T, _OP >::SearchNeighbours ( const K & key,

T ** prev,

T ** next

) [inline]

Find the neighbours of passed key.
Runtime O(log(n)) (n = number of elements in the tree) prev,next return the next smaller and larger entries. If exact match is found, it is returned as return value. You may use prev/next=NULL if not interested. In case no prev/next value exists, NULL is returned in prev/next, respectively.
Definition at line 614 of file tlbtree.h.
Referenced by main().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

int TLBTree< T, _OP >::store ( const T & e,

bool allow_update,

T * oldval = NULL

) [inline]

Store passed elemet in the tree.
If allow_update is 0, then an existing matching entry will not be replaced but the store operation will instead fail.
In case oldval is non-NULL, the original value of the entry will be stored under *oldval (using OP.ass()) if the return value is 1. (This holds independent of allow_update.)
Runtime O(log(n)) (n = number of elements in the tree)

Returns:
1 -> not stored as it was already in the tree; in case allow_update is set, the element was updated; otherwise it stayed unchanged.
0 -> OK, stored

Definition at line 648 of file tlbtree.h.
Referenced by VM::VMLinker::_SQPush(), and main().

Member Data Documentation

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

int TLBTree< T, _OP >::m [private]

Min number of elements per tree node; max number is 2*m.

Definition at line 211 of file tlbtree.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

_OP TLBTree< T, _OP >::OP

Definition at line 218 of file tlbtree.h.
Referenced by TLBTree< T, _OP >::Node::_DEL_L(), TLBTree< T, _OP >::Node::_DEL_R(), TLBTree< T, _OP >::Node::_DELLeaf(), TLBTree< T, _OP >::Node::_INS_NS(), TLBTree< T, _OP >::Node::_INSLeafNS(), TLBTree< T, _OP >::Node::_LBI(), TLBTree< T, _OP >::Node::elem(), TLBTree< T, _OP >::Node::elemP(), and main().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

Node* TLBTree< T, _OP >::root [private]

Tree root.

Definition at line 212 of file tlbtree.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>

T TLBTree< T, _OP >::tmp [private]

Temporary element for split/join operations.

Definition at line 213 of file tlbtree.h.

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

/ray/src/lib/tl/tlbtree.h

Generated on Sat Feb 19 22:35:46 2005 for Ray by

1.3.5

TLBTree< T, _OP > Class Template Reference

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Detailed Description

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> class TLBTree< T, _OP >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
class TLBTree< T, _OP >