btreealgorithms.h

b tree code for index in the database design

//////////////////////////////////////////////////////////////////
///
/// (C) 2007: ScalingWeb.com
///
/// Author: Anton Fedoruk <[e-mail]>
///
//////////////////////////////////////////////////////////////////

#ifndef __BTreeAlgorithms_h__
#define __BTreeAlgorithms_h__

#include "BTreeNode.h"

///
/// BTree algorithms implementation
///

template
<
	int NodeSize,
	typename KeyT,
	typename DataT,
	template < int, typename, typename > class TController
>
class BTreeAlgorithms : public TController< NodeSize, KeyT, DataT >
{
public:

	typedef BTreeNode< NodeSize, KeyT, DataT > NodeType;
	enum { nodeSize = NodeSize };

	BTreeAlgorithms();
	~BTreeAlgorithms();

	///
	/// Add new key:data pair
	bool add( const KeyT &key, const DataT &data );

	///
	/// Remove pair by key
	bool remove( const KeyT &key );

	///
	/// Remove pair by key and return associated data
	bool remove( const KeyT &key, DataT &data );

	///
	/// Find data by key, or return false if key was not found
	bool find( const KeyT &key, DataT &data );

	///
	/// Find all specified data
	template< class TChecker, class TContainer >
	bool search( TContainer &retList, const KeyT &startKey, 
		bool preciseSearch, TChecker &condition );

	///
	/// Get all specified in container data
	template< class TContainer >
	bool getAll( TContainer &retList );

	///
	/// Change data which belongs to the key is specified
	void changeData( const KeyT &key, const DataT &newData );

	///
	/// Close BTree and release all occupied resources
	void close();

protected:

	int getMedian( NodeType *node, BTreeElement< KeyT, DataT > &elem );

	void splitNodeByKey( NodeType **fullNode, KeyT &key );
	bool splitNode( NodeType *node, 
		BTreeElement< KeyT, DataT > &median, NodeType **nodeRight );

	NodeType* findNode( NodeType *node, const KeyT &key, int &retIndex, 
		int &parentIndex, bool &found );

	bool rebalance( NodeType *node, int parentIndex );
	bool combine( NodeType *leftNode, NodeType *rightNode );
	bool pullOut( NodeType *node, int itemIndex );

	NodeType* rightMost( NodeType *subtree, KeyT &largestKey, DataT &largestData );
	NodeType* leftMost( NodeType *subtree, KeyT &smallestKey, DataT &smallestData );

	// Internal search methods
	template < class TChecker, class TContainer >
	bool allKeys( NodeType *node, TContainer &retList, int elemIndex, 
		const KeyT &startKey, TChecker &condition );
	template < class TChecker, class TContainer >
	bool allKeys( NodeType *node, TContainer &retList, TChecker &condition );
	template< class TContainer >
	bool allKeys( NodeType *node, TContainer &retList );

};

//	===================================================================
//	BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::BTreeAlgorithms

template< int NodeSize, typename KeyT, typename DataT, 
template < int, typename, typename > class TController >
BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::BTreeAlgorithms()
{}

//	===================================================================
//	BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::~BTreeAlgorithms

template< int NodeSize, typename KeyT, typename DataT, 
template < int, typename, typename > class TController >
BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::~BTreeAlgorithms()
{
	close();
}

//	===================================================================
//	BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::add

template< int NodeSize, typename KeyT, typename DataT, 
template < int, typename, typename > class TController >
bool BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::add( const KeyT &key, 
												const DataT &data )
{
	if ( !isOpen() ) return false;

	if ( !root_ )
	{
		int addr = rootAddr();
		if ( !addr )
		{
			root_ = newNode();
			root_->flags_ = NodeType::NodeChanged;
			rootAddr( root_->addr_ );
		}
		else
		{
			if ( !loadNode( &root_, addr ) )
			{
				return false;
			}
		}
	}

	if ( !root_ ) return false;

	// Find targeted node
	bool found = false;
	KeyT copyKey( key );
	DataT copyData( data );
	int retIndex = -1, parentIndex = 0;

	NodeType *node = findNode( root_, copyKey, retIndex, parentIndex, found );

	if ( found || !node )
	{
		// Duplicate keys are not accepted
		releaseCache();
		return false;
	}

	if ( !node->isFull() )
	{
		// Just add to not full node
		node->add( copyKey, copyData );
		releaseCache();
		return true;
	}
	else
	{
		BTreeElement< KeyT, DataT > median;
		median.key_ = key;
		median.data_ = data;
		NodeType *nodeRight = 0;
		NodeType *parent = 0;
		if ( !loadNode( &parent, node->parent_ ) )
		{
			releaseCache();
			return false;
		}

		// Split node and get median
		if ( !splitNode( node, median, &nodeRight ) )
		{
			releaseCache();
			return false;
		}

		while ( 0 != parent )
		{
			// Add median to the parent
			if ( parent->isFull() )
			{
				if ( !splitNode( parent, median, &nodeRight ) )
				{
					releaseCache();
					return false;
				}

				node = parent;

				// Move up
				if ( !loadNode( &parent, parent->parent_ ) )
				{
					releaseCache();
					return false;
				}
			}
			else
			{
				parent->add( median );
				parent->flags_ = NodeType::NodeChanged;
				nodeRight->parent_ = parent->addr_;
				nodeRight->flags_ = NodeType::NodeChanged;
				break;
			}
		}

		if ( !parent )
		{
			// The root node!
			root_ = newNode();
			rootAddr( root_->addr_ );
			node->parent_ = root_->addr_;
			node->flags_ = NodeType::NodeChanged;
			nodeRight->parent_ = root_->addr_;
			nodeRight->flags_ = NodeType::NodeChanged;

			root_->add( median.key_, median.data_ );
			root_->elems_[ 0 ].link_ = nodeRight->addr_;
			root_->less_ = node->addr_;
		}
	}

	releaseCache();
	return true;
}

//	===================================================================
//	BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::remove

template< int NodeSize, typename KeyT, typename DataT, 
template < int, typename, typename > class TController >
bool BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::remove( const KeyT &key )
{
	if ( !root_ )
	{
		return false;
	}

	// Find targeted node
	bool found = false;
	int retIndex = -1, parentIndex = 0;

	NodeType *node = findNode( root_, key, retIndex, parentIndex, found );

	if ( !found || !node )
	{
		// Key not found
		releaseCache();
		return false;
	}

	if ( !node->hasChilds() )
	{
		node->removeAt( retIndex );
		if ( !rebalance( node, parentIndex ) )
		{
			releaseCache();
			return false;
		}
	}
	else
	{
		if ( !pullOut( node, retIndex ) )
		{
			releaseCache();
			return false;
		}
	}

	releaseCache();
	return true;
}

//	===================================================================
//	BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::remove

template< int NodeSize, typename KeyT, typename DataT, 
template < int, typename, typename > class TController >
bool BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::remove( const KeyT &key, 
														DataT &data )
{
	if ( !root_ )
	{
		return false;
	}

	// Find targeted node
	bool found = false;
	int retIndex = -1, parentIndex = 0;

	NodeType *node = findNode( root_, key, retIndex, parentIndex, found );

	if ( !found || !node )
	{
		// Key not found
		releaseCache();
		return false;
	}
	else
	{
		data = node->elems_[ retIndex ].data_;
	}

	if ( !node->hasChilds() )
	{
		node->removeAt( retIndex );
		if ( !rebalance( node, parentIndex ) )
		{
			releaseCache();
			return false;
		}
	}
	else
	{
		if ( !pullOut( node, retIndex ) )
		{
			releaseCache();
			return false;
		}
	}

	releaseCache();
	return true;
}

//	===================================================================
//	BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::find

template< int NodeSize, typename KeyT, typename DataT, 
template < int, typename, typename > class TController >
bool BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::find( const KeyT &key, 
								DataT &data )
{
	if ( !root_ )
	{
		return false;
	}

	int index = 0, parentIndex = 0;
	bool found = false;
	NodeType *node = findNode( root_, key, index, parentIndex, found );

	if ( !node || index < 0 )
	{
		releaseCache();
		return false;
	}

	if ( found )
	{
		// Key found
		data = node->elems_[ index ].data_;
		releaseCache();
		return true;
	}

	releaseCache();

	// Key not found
	return false;
}

//	===================================================================
//	BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::search

template < int NodeSize, typename KeyT, typename DataT, 
template < int, typename, typename > class TController >
template < class TChecker, class TContainer >
bool BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::search( 
		TContainer &retList, const KeyT &startKey, bool preciseSearch,
		TChecker &condition )
{
	retList.clear();

	// Find targeted node
	bool found = false;
	int retIndex = -1, parentIndex = 0;
	NodeType *node = findNode( root_, startKey, retIndex, parentIndex, found );

	if ( ( preciseSearch && !found ) || !node )
	{
		releaseCache();
		return false;
	}

	if ( !allKeys( node, retList, retIndex, startKey, condition ) )
	{
		releaseCache();
		return false;
	}

	releaseCache();
	return true;
}

//	===================================================================
//	BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::getAll

template < int NodeSize, typename KeyT, typename DataT, 
template < int, typename, typename > class TController >
template < class TContainer >
bool BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::getAll( TContainer &retList )
{
	if ( !allKeys( root_, retList ) )
	{
		releaseCache();
		return false;
	}

	releaseCache();
	return true;
}

//	===================================================================
//	BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::changeData

template< int NodeSize, typename KeyT, typename DataT, 
template < int, typename, typename > class TController >
void BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::changeData( const KeyT &key, 
											const DataT &newData )
{
	if ( !root_ )
	{
		return;
	}

	int index = 0, parentIndex = 0;
	bool found = false;
	NodeType *node = findNode( root_, key, index, parentIndex, found );

	if ( !node || index < 0 )
	{
		releaseCache();
		return;
	}

	if ( found )
	{
		// Key found
		node->elems_[ index ].data_ = newData;
		node->flags_ = NodeType::NodeChanged;
		releaseCache();
		return;
	}

	releaseCache();
}

//	===================================================================
//	BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::allKeys

template < int NodeSize, typename KeyT, typename DataT, 
template < int, typename, typename > class TController >
template < class TChecker, class TContainer >
bool BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::allKeys( 
		NodeType *node, TContainer &retList, int elemIndex,
		const KeyT &startKey, TChecker &condition )
{
	if ( !node ) return true;

	if ( -1 == elemIndex )
	{
		node->find( startKey, elemIndex );
		if ( -1 == elemIndex )
		{
			return false;
		}
	}

	int i = elemIndex;
	//if ( i > 0 ) i--;

	while ( i < node->size_ )
	{
		if ( condition.satisfy( node->elems_[ i ].key_ ) )
		{
			retList.push_back( TContainer::ElemType( node->elems_[ i ] ) );

			if ( node->elems_[ i ].link_ )
			{
				// Examine each child item
				NodeType *child = 0;
				bool wasInCache = nodeInCache( node->elems_[ i ].link_ );
				if ( !loadNode( &child, node->elems_[ i ].link_ ) ) return false;
				allKeys( child, retList, condition );
				if ( child && !wasInCache ) releaseNode( child->addr_ );
			}
		}
		else
		{
			break;
		}

		// Move to node end
		i++;
	}

	if ( !node->parent_ )
	{
		// End of search has reached
		return true;
	}

	// Move to up
	NodeType *parent = 0;
	bool wasInCache = nodeInCache( node->parent_ );
	if ( !loadNode( &parent, node->parent_ ) )
	{
		return false;
	}

	bool ret = allKeys( parent, retList, -1, startKey, condition );
	if ( parent && !wasInCache ) releaseNode( parent->addr_ );
	return ret;
}

//	===================================================================
//	BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::allKeys

template < int NodeSize, typename KeyT, typename DataT, 
template < int, typename, typename > class TController >
template < class TChecker, class TContainer >
bool BTreeAlgorithms< NodeSize, KeyT, DataT, TController >::allKeys( 
	NodeType *node, TContainer &retList, TChecker &condition )
{
	if ( !node ) return true;

	if ( node->less_ )
	{
		NodeType *less = 0;

		bool wasInCache = nodeInCache( node->less_ );
		if ( !loadNode( &less, node->less_ ) ) return false;
		if ( !allKeys( less, retList ) )
		{
			// End of the condition had reached
			return false;
		}