streambtreecontroller.h

b tree code for index in the database design

	if ( node->less_ )
	{
		NodeType *less;
		if ( !loadNode( &less, node->less_ ) ) return false;
		freeChunks_.erase( node->less_ );
		readAllOffsets( less );
		if ( less ) releaseNode( less->addr_ );

		// Iterate other children if we have a less one
		for ( int i = 0; i < node->count(); i++ )
		{
			NodeType *kid = 0;

			if ( node->elems_[ i ].link_ )
			{
				if ( !loadNode( &kid, node->elems_[ i ].link_ ) ) return false;
			}
			freeChunks_.erase( node->elems_[ i ].link_ );

			if ( kid )
			{
				readAllOffsets( kid );
				releaseNode( kid->addr_ );
			}
		}
	}

	return true;
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::deleteNode

template< int NodeSize, typename KeyT, typename DataT >
void StreamBTreeController< NodeSize, KeyT, DataT >::deleteNode( NodeType* node )
{
	typename ChunkCacheMap::iterator iter = cache_.find( node->addr_ );

	if ( iter != cache_.end() )
	{
		cache_.erase( iter );
	}

	freeChunks_.insert( node->addr_ );
	delete node;
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::loadNode

template< int NodeSize, typename KeyT, typename DataT >
bool StreamBTreeController< NodeSize, KeyT, DataT >::loadNode( 
			NodeType **node, int addr )
{
	if ( !addr )
	{
		*node = 0;
		return true;
	}

	typename ChunkCacheMap::iterator iter = cache_.find( addr );

	if ( iter == cache_.end() )
	{
		*node = new NodeType();
		storage_->seek( addr );
		storage_->read( ( char* ) *node, sizeof( NodeType ) );

		if ( addr == ( *node )->addr_ )
		{
			CacheData cacheData( *node );
			cache_[ addr ] = cacheData;
		}
	}
	else
	{
		*node = iter->node;
	}

	if ( ( *node )->addr_ != addr )
	{
		// Storage is corrupted!
		return false;
	}

	return true;
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::saveNode

template< int NodeSize, typename KeyT, typename DataT >
void StreamBTreeController< NodeSize, KeyT, DataT >::saveNode( NodeType *node )
{
	node->flags_ = 0;
	storage_->seek( node->addr_ );
	storage_->write( ( const char* ) node, sizeof( NodeType ) );
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::flushChanges

template< int NodeSize, typename KeyT, typename DataT >
void StreamBTreeController< NodeSize, KeyT, DataT >::flushChanges()
{
	if ( !storage_ ) return;

	// Journaling
	if ( journal_ )
	{
		JBufferedOutputStream< JStream > journal( journal_ );
		if ( journal.size() > 0 )
		{
			journal.resize( 0 );
		}

		bool firstTime = true;
		guint complete = 0;

		typename ChunkCacheMap::iterator iter = cache_.begin();
		for ( ; iter != cache_.end(); iter++ )
		{
			NodeType *node = iter->node;

			if ( NodeType::NodeChanged == node->flags_ )
			{
				if ( firstTime )
				{
					// Write completion label
					journal.seek( 0 );
					journal.write( ( char* ) &complete, sizeof( complete ) );
					journal.write( ( char* ) &rootAddr_, sizeof( rootAddr_ ) );
					firstTime = false;
				}

				node->flags_ = 0;
				journal.write( ( const char* ) node, sizeof( NodeType ) );
				node->flags_ = NodeType::NodeChanged;
			}
		}

		if ( !firstTime )
		{
			// Complete it
			journal.seekRaw( 0 );
			complete = ~0;
			journal.write( ( char* ) &complete, sizeof( complete ) );
			journal.flush();
		}
		journal.setSource( 0 );
	}

	// Actual saving
	typename ChunkCacheMap::iterator iter = cache_.begin();
	for ( ; iter != cache_.end(); iter++ )
	{
		if ( NodeType::NodeChanged == iter->node->flags_ )
		{
			// Save node
			saveNode( iter->node );
		}
	}

	// Write root
	if ( rootAddr_ )
	{
		storage_->seek( sizeof( int ) );
		storage_->write( ( char* ) &rootAddr_, sizeof( rootAddr_ ) );
		rootAddr_ = 0;
	}

	// Clear journal
	if ( journal_ ) journal_->resize( 0 );
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::releaseCache

template< int NodeSize, typename KeyT, typename DataT >
void StreamBTreeController< NodeSize, KeyT, DataT >::releaseCache()
{
	if ( cacheSize() > maxCacheSize_ )
	{
		clearCache();
		return;
	}
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::clearCache

template< int NodeSize, typename KeyT, typename DataT >
void StreamBTreeController< NodeSize, KeyT, DataT >::clearCache()
{
	flushChanges();

	typename ChunkCacheMap::iterator iter = cache_.begin();
	for ( ; iter != cache_.end(); iter++ )
	{
		if ( iter->node != root_ )
		{
			delete iter->node;
		}
	}

	cache_.clear();
	if ( root_ )
	{
		cache_[ root_->addr_ ] = CacheData( root_ );
	}
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::releaseNode

template< int NodeSize, typename KeyT, typename DataT >
void StreamBTreeController< NodeSize, KeyT, DataT >::releaseNode( int addr )
{
	typename ChunkCacheMap::iterator iter = cache_.find( addr );

	if ( cache_.end() != iter )
	{
		if ( NodeType::NodeChanged == iter->node->flags_ )
		{
			flushChanges();
			releaseNode( addr );
			return;
		}

		if ( iter->node != root_ )
		{
			delete iter->node;
			cache_.erase( iter );
		}
	}
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::rootAddr

template< int NodeSize, typename KeyT, typename DataT >
int StreamBTreeController< NodeSize, KeyT, DataT >::rootAddr()
{
	int addr = 0;
	storage_->seek( sizeof( int ) );
	storage_->read( ( char* ) &addr, sizeof( addr ) );
	return addr;
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::closeController

template< int NodeSize, typename KeyT, typename DataT >
void StreamBTreeController< NodeSize, KeyT, DataT >::closeController()
{
	cache_.clear();

	if ( storage_ )
	{
		if ( !freeChunks_.empty() )
		{
			// Save removed nodes list
			guint rlistAddr = storage_->size();
			QByteArray rblock;
			FreeChunksSet::const_iterator iter = freeChunks_.begin();
			guint aaddr = 0;
			for ( ; iter != freeChunks_.end(); iter++ )
			{
				aaddr = *iter;
				rblock.resize( rblock.size() + sizeof( aaddr ) );
				::memcpy( rblock.data() + rblock.size() - sizeof( aaddr ), 
					( char* ) &aaddr, sizeof( aaddr ) );
			}
			freeChunks_.clear();

			storage_->seek( rlistAddr );
			storage_->write( rblock.data(), rblock.size() );

			storage_->seek( constRemovedAddr );
			storage_->write( ( char* ) &rlistAddr, sizeof( rlistAddr ) );
		}

		storage_->close();
		storage_ = 0;

		if ( journal_ )
		{
			journal_->close();
			journal_ = 0;
		}
	}
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::rootAddr

template< int NodeSize, typename KeyT, typename DataT >
void StreamBTreeController< NodeSize, KeyT, DataT >::rootAddr( int addr )
{
	rootAddr_ = addr;
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::rootAddr

template< int NodeSize, typename KeyT, typename DataT >
guint StreamBTreeController< NodeSize, KeyT, DataT >::cacheSize() const
{
	return sizeof( NodeType )*cache_.size();
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::setMaxCacheSize

template< int NodeSize, typename KeyT, typename DataT >
void StreamBTreeController< NodeSize, KeyT, DataT >::setMaxCacheSize( guint maxSize )
{
	maxCacheSize_ = maxSize;
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::getMaxCacheSize

template< int NodeSize, typename KeyT, typename DataT >
guint StreamBTreeController< NodeSize, KeyT, DataT >::getMaxCacheSize()
{
	return maxCacheSize_;
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::getMaxCacheSize

template< int NodeSize, typename KeyT, typename DataT >
bool StreamBTreeController< NodeSize, KeyT, DataT >::nodeInCache( int addr )
{
	return cache_.end() != cache_.find( addr );
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::getMaxCacheSize

template< int NodeSize, typename KeyT, typename DataT >
JStream* StreamBTreeController< NodeSize, KeyT, DataT >::storage()
{
	return storage_;
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::clear

template< int NodeSize, typename KeyT, typename DataT >
bool StreamBTreeController< NodeSize, KeyT, DataT >::clear()
{
	// Clear cache
	typename ChunkCacheMap::iterator iter = cache_.begin();
	for ( ; iter != cache_.end(); iter++ )
	{
		delete iter->node;
	}

	cache_.clear();
	freeChunks_.clear();
	root_  = 0;

	JStream *treeStorage = storage_;
	storage_->resize( 0 );
	storage_ = 0;

	return open( treeStorage, maxCacheSize_ );
}

//	===================================================================
//	StreamBTreeController< NodeSize, KeyT, DataT >::root

template< int NodeSize, typename KeyT, typename DataT >
typename StreamBTreeController< NodeSize, KeyT, DataT >::NodeType* 
		StreamBTreeController< NodeSize, KeyT, DataT >::root()
{
	return root_;
}

#endif // __StreamBTreeController_h__