Implements a file-based RTree. More...

#include <RTree.h>

Classes
class	Datablock
	Each RTree leaf points to Datablocks; they describe where the actual data that the index references resides via a filename and an offset into that file. More...

Public Member Functions

RTree (FileAllocator &fa, FileOffset anchor)

Attach RTree to FileAllocator. More...

void init (int M)

Initialize empty tree. More...

void reattach ()

Re-attach to an existing tree. More...

int getM () const

The 'M' value, i.e. More...

Interval getInterval ()

Return range covered by this RTree

Exceptions

GenericException on read error.

Datablock * search (const epicsTime &start) const

Locate data after start time. More...

Datablock * getFirstDatablock () const

Datablock * getLastDatablock () const

class Node chooseLeaf (const Interval &range)

bool insertDatablock (const Interval &range, FileOffset data_offset, const stdString &data_filename)

Create and insert a new Datablock. More...

size_t removeDatablock (const Interval &range, FileOffset data_offset, const stdString &data_filename)

Remove reference to given data block. More...

bool updateLastDatablock (const Interval &range, FileOffset data_offset, stdString data_filename)

Tries to update existing datablock. More...

void makeDot (const char *filename)

Create a graphviz 'dot' file. More...

bool selfTest (unsigned long &nodes, unsigned long &records)

Returns true if tree passes self test, otherwise prints errors. More...

Static Public Attributes
static const size_t	anchor_size = 8

Detailed Description

Implements a file-based RTree.

See the Antonin Guttman paper "R-Trees: A Dynamic Index Structure for Spatial Searching" (Proc. 1984 ACM-SIGMOD Conference on Management of Data, pp. 47-57).

The records are time intervals start...end. In addition to what's described in the Guttman paper,

all records are non-overlapping (they might touch but they don't overlap);
all records are sorted by time;
node removal only for empty nodes, no reordering of records.

Constructor & Destructor Documentation

RTree::RTree	(	FileAllocator &	fa,
		FileOffset	anchor
	)

Attach RTree to FileAllocator.

Parameters

fa,:	The file allocator
anchor,:	The RTree will deposit its root pointer there. Caller needs to assert that there are RTree::anchor_size bytes available at that location in the file.

Member Function Documentation

class Node RTree::chooseLeaf ( const Interval & range )

Returns: Leaf node suitable for range.

Datablock* RTree::getFirstDatablock ( ) const

Returns: Locate first datablock in tree, or 0 if there is nothing. Client must delete.

Exceptions

GenericException on read error.

Datablock* RTree::getLastDatablock ( ) const

See Also: getFirstDatablock

int RTree::getM ( ) const

inline

The 'M' value, i.e.

Node size, of this RTree.

void RTree::init ( int M )

Initialize empty tree.

Compare to reattach().

Exceptions

GenericException on write error.

bool RTree::insertDatablock	(	const Interval &	range,
		FileOffset	data_offset,
		const stdString &	data_filename
	)

Create and insert a new Datablock.

Note: Once a data block (offset and filename) is inserted for a given start and end time, the RTree code assumes that it stays that way. I.e. if we try to insert the same start/end/offset/file again, this will result in a NOP and return false. It is an error to insert the same offset/file again with a different start and/or end time!

See Also: updateLastDatablock for the special case up updating the end time.

Returns: true if a new entry was created, false if offset and filename were already found.

Exceptions

GenericException on write error.

void RTree::makeDot ( const char * filename )

Create a graphviz 'dot' file.

void RTree::reattach ( )

Re-attach to an existing tree.

Compare to init().

Exceptions

GenericException on write error.

size_t RTree::removeDatablock	(	const Interval &	range,
		FileOffset	data_offset,
		const stdString &	data_filename
	)

Remove reference to given data block.

Returns: Number of data block references found and removed, or 0.

Exceptions

GenericException on internal error.

Datablock* RTree::search ( const epicsTime & start ) const

Locate data after start time.

Specifically, the last record with data at or just before the start time is returned, so that the user can then decide if and how that value might extrapolate onto the start time. There's one exception: When requesting a start time that preceeds the first available data point, so that there is no previous data point, the very first record is returned.

Returns: Data block info or 0 if nothing found. Caller must delete.

Exceptions

GenericException on read error.

bool RTree::selfTest	(	unsigned long &	nodes,
		unsigned long &	records
	)

Returns true if tree passes self test, otherwise prints errors.

On success, nodes will contain the number of nodes in the tree and record contains the number of used records. One can compare that to the total number of available records, nodes*getM().

bool RTree::updateLastDatablock	(	const Interval &	range,
		FileOffset	data_offset,
		stdString	data_filename
	)

Tries to update existing datablock.

Tries to update the end time of the last datablock, in case start, data_offset and data_filename all match. Will otherwise fall back to insertDatablock.

Returns: true if a new entry was created, false if offset and filename were already found.

Exceptions

GenericException on write error.

Member Data Documentation

const size_t RTree::anchor_size = 8

static

See Also: constructor Rtree()

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

/home/malitsky/projects/epics-archiver/sourceforge/trunk/ea4-cpp/include/common/storage/RTree.h

Classes

Public Member Functions

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation