Represents an ordered collection of associations of keys and values, with keys ordered based on an external function and with duplicate keys not allowed. More...

#include <rw/disktree.h>

Public Types
enum	createMode { autoCreate, create }

enum	styleMode { V6Style, V5Style }

Public Member Functions
	RWBTreeOnDisk (RWFileManager &f, unsigned cacheBlocks=10, createMode cmode=autoCreate, unsigned keylen=16, bool ignoreNull=false, RWoffset start=RWNIL, styleMode smode=V6Style, unsigned halfOrder=10, unsigned minFill=10)

	~RWBTreeOnDisk ()

void	applyToKeyAndValue (RWdiskTreeApply ap, void *x)

RWoffset	baseLocation () const

unsigned	cacheCount () const

unsigned	cacheCount (unsigned newcount)

void	clear ()

bool	contains (const char *key) const

unsigned long	entries () const

RWoffset	extraLocation (RWoffset newlocation)

bool	find (const char *key) const

bool	findKey (const char *key, RWCString &retKey) const

bool	findKeyAndValue (const char *key, RWCString &retKey, RWstoredValue &foundVal) const

RWstoredValue	findValue (const char *key) const

unsigned	height () const

bool	insertKeyAndValue (const char *key, RWstoredValue val)

bool	isEmpty () const

unsigned	keyLength () const

unsigned	minOrder () const

unsigned	nodeSize () const

unsigned	occurrencesOf (const char *key) const

unsigned	order () const

void	remove (const char *key)

bool	removeKeyAndValue (const char *key, RWCString &retKey, RWstoredValue &retVal)

bool	removeKeyAndValue (const char *key, RWstoredValue &retVal)

bool	replaceValue (const RWCString &key, const RWstoredValue newVal, RWstoredValue &oldVal)

RWdiskTreeCompare	setComparison (RWdiskTreeCompare fun)

Related Functions
(Note that these are not member functions.)
typedef void(*	RWdiskTreeApply) (const char , RWstoredValue, void )

typedef int(*	RWdiskTreeCompare) (const char , const char , size_t)

typedef unspecified_type	RWstoredValue

Detailed Description

Class RWBTreeOnDisk represents an ordered collection of associations of keys and values, where the ordering is determined by comparing keys using an external function. The user can set this function. Duplicate keys are not allowed. Given a key, the corresponding value can be found.

This class is specifically designed for managing a B-tree in a disk file. Keys, defined to be arrays of chars, and values, defined by the typedef RWstoredValue, are stored and retrieved from a B-tree. The values can represent offsets to locations in a file where the objects are stored.

The key length is set by the constructor. By default, this value is 16 characters. By default, keys are null-terminated. However, the tree can be used with embedded nulls, allowing multibyte and binary data to be used as keys. To do so you must:

Specify true for parameter ignoreNull in the constructor.
Make sure all buffers used for keys are at least as long as the key length. (Remember, storage and comparison will not stop with a null value.)
Use a comparison function (such as std::memcmp()) that ignores nulls.

This class is meant to be used with class RWFileManager, which manages the allocation and deallocation of space in a disk file.

When you construct an RWBTreeOnDisk, you give the location of the root node in the constructor as argument start. If this value is RWNIL (the default), the location is retrieved using RWFileManager::start(). You can also use the enumeration createMode to set whether to use an existing tree (creating one if one doesn't exist) or to force the creation of a new tree. The location of the resultant root node can be retrieved using member function baseLocation().

More than one B-tree can exist in a disk file. Each must have its own separate root node. This can be done by constructing more than one RWBTreeOnDisk, each with createMode set to create.

The order of the B-tree can be set in the constructor. Larger values result in shallower trees, but less efficient use of disk space. The minimum number of entries in a node can also be set. Smaller values may result in less time spent balancing the tree, but less efficient use of disk space.

Synopsis: typedef long RWstoredValue ;

typedef int (*RWdiskTreeCompare)(const char*, const char*, size_t);

#include <rw/disktree.h>

#include <rw/filemgr.h>

RWFileManager fm("filename.dat");

RWBTreeOnDisk bt(fm);

Persistence: None

Member Enumeration Documentation

enum RWBTreeOnDisk::createMode

This enumeration is used by the constructor to determine whether to force the creation of a new tree.

Enumerator
autoCreate	Look in the location given by the constructor argument `start` for the root node. If valid, use it. Otherwise, allocate a new tree. This is the default.
create	Forces the creation of a new tree. The argument `start` is ignored.

enum RWBTreeOnDisk::styleMode

This enumeration is used by the constructor to allow backwards compatibility with older V5.X style trees, which supported only 16-byte key lengths. It is used only when creating a new tree. If opening a tree for update, its type is determined automatically at runtime.

Enumerator
V6Style	Initialize a new tree using V6.X style trees. This is the default.
V5Style	Initialize a new tree using V5.X style trees. The key length is fixed at 16 bytes.

Constructor & Destructor Documentation

RWBTreeOnDisk::RWBTreeOnDisk	(	RWFileManager &	f,
		unsigned	cacheBlocks = `10`,
		createMode	cmode = `autoCreate`,
		unsigned	keylen = `16`,
		bool	ignoreNull = `false`,
		RWoffset	start = `RWNIL`,
		styleMode	smode = `V6Style`,
		unsigned	halfOrder = `10`,
		unsigned	minFill = `10`
	)

Constructs a B-tree on disk.

Parameters

f	The file in which the B-tree is to be managed. This is the only required parameter.
cacheBlocks	The maximum number of nodes that can be cached in memory.
cmode	Determines whether to force the creation of a new tree or to attempt to open an existing tree for update (the default).
keylen	The length of a key in bytes. Ignored when opening an existing tree.
ignoreNull	Controls whether to allow embedded nulls in keys. If `false` (the default), then keys end with a terminating null. If `true`, then all keylen bytes are significant. Ignored when opening an existing tree.
start	Where to find the root node. If set to RWNIL (the default), uses the value returned by the RWFileManager::start() member function. Ignored when creating a new tree.
smode	Sets the type of B-tree to create, allowing backwards compatibility, as described in the general class description. The default specifies new V6.X style B-trees. Ignored when opening an existing tree.
halfOrder	One half the order of the B-tree (that is, one half the number of entries in a node). Ignored when opening an existing tree.
minFill	The minimum number of entries allowed in a node (must be less than or equal to halfOrder). Ignored when opening an existing tree.

RWBTreeOnDisk::~RWBTreeOnDisk ( )

Releases memory resources, and completes any pending I/O.

Member Function Documentation

void RWBTreeOnDisk::applyToKeyAndValue	(	RWdiskTreeApply	ap,
		void *	x
	)

inline

Visits all items in the collection in order, from smallest to largest, calling the user-provided function pointed to by ap with the key and value as arguments. This function should have the prototype:

void yourApplyFunction(const char* ky,

RWstoredValue val, void* x);

The function yourApplyFunction cannot change the key. The value x can be anything and is passed through from the call to this member function. This member function may throw an RWFileErr exception.

RWoffset RWBTreeOnDisk::baseLocation ( ) const

inline

Returns the offset of this tree's starting location within the RWFileManager. This is the value you will pass to a constructor as the start argument when you want to open one of several trees stored in one managed file.

unsigned RWBTreeOnDisk::cacheCount ( ) const

inline

Returns the maximum number of nodes that may currently be cached.

unsigned RWBTreeOnDisk::cacheCount ( unsigned newcount )

Sets the number of nodes that should be cached to newcount. Returns the old number.

void RWBTreeOnDisk::clear ( )

Removes all items from the collection. This member function may throw an RWFileErr exception.

bool RWBTreeOnDisk::contains ( const char * key ) const

inline

Returns true if the tree contains a key that is equal to the string pointed to by key, or false otherwise. This member function may throw an RWFileErr exception.

unsigned long RWBTreeOnDisk::entries ( ) const

Returns the number of items in the RWBTreeOnDisk. This member function may throw an RWFileErr exception.

RWoffset RWBTreeOnDisk::extraLocation ( RWoffset newlocation )

inline

Sets the location where this RWBTreeOnDisk keeps your own application-specific information to newlocation. Returns the previous value.

bool RWBTreeOnDisk::find ( const char * key ) const

inline

This is a synonym for contains(key).

bool RWBTreeOnDisk::findKey	(	const char *	key,
		RWCString &	retKey
	)		const

inline

Returns true if key is found, otherwise false. If successful, the found key is returned as a reference in retKey. This member function may throw an RWFileErr exception.

bool RWBTreeOnDisk::findKeyAndValue	(	const char *	key,
		RWCString &	retKey,
		RWstoredValue &	foundVal
	)		const

Returns true if key is found, otherwise false. If successful, the found key is returned as a reference in retKey, and the value is returned as a reference in foundVal. This member function may throw an RWFileErr exception.

RWstoredValue RWBTreeOnDisk::findValue ( const char * key ) const

inline

Returns the value for the key that compares equal to the string pointed to by key. Returns RWNIL if no key is found. This member function may throw an RWFileErr exception.

unsigned RWBTreeOnDisk::height ( ) const

Returns the height of the RWBTreeOnDisk. This member function may throw an RWFileErr exception.

bool RWBTreeOnDisk::insertKeyAndValue	(	const char *	key,
		RWstoredValue	val
	)

Adds a key-value pair to the B-tree. Returns true for successful insertion, false otherwise. This member function may throw an RWFileErr exception.

bool RWBTreeOnDisk::isEmpty ( ) const

inline

Returns true if this RWBTreeOnDisk contains no data, false otherwise.

unsigned RWBTreeOnDisk::keyLength ( ) const

inline

Returns the length of the keys for this RWBTreeOnDisk. This number is set when the tree is first constructed, and cannot be changed.

unsigned RWBTreeOnDisk::minOrder ( ) const

inline

Returns the minimum number of items that may be found in any non-root node in this RWBTreeOnDisk. This number is set when the tree is first constructed, and cannot be changed.

unsigned RWBTreeOnDisk::nodeSize ( ) const

inline

Returns the number of bytes used by each node of this RWBTreeOnDisk. This number is calculated from the length of the keys and the order of the tree, and cannot be changed. We make it available for your calculations about how many nodes to cache.

unsigned RWBTreeOnDisk::occurrencesOf ( const char * key ) const

inline

Returns 1 if key is found, 0 otherwise.

unsigned RWBTreeOnDisk::order ( ) const

inline

Return half the maximum number of items that may be stored in any node in this RWBTreeOnDisk. This number is set when the tree is first constructed and cannot be changed. This method should have been renamed halfOrder but is still called order() for backward compatibility.

void RWBTreeOnDisk::remove ( const char * key )

inline

Removes the key and value pair with the key that matches key. This member function may throw an RWFileErr exception.

bool RWBTreeOnDisk::removeKeyAndValue	(	const char *	key,
		RWCString &	retKey,
		RWstoredValue &	retVal
	)

Removes the key and value pair with the key that matches key. The removed data is returned in the reference arguments retKey and retVal. The function returns true if the remove operation succeeds, or otherwise false. This function may throw an RWFileErr exception.

bool RWBTreeOnDisk::removeKeyAndValue	(	const char *	key,
		RWstoredValue &	retVal
	)

inline

Removes the key and value pair with key that matches key. The removed value is returned in the reference argument retVal. The function returns true if the remove operation succeeds; or otherwise false. This function may throw an RWFileErr exception.

bool RWBTreeOnDisk::replaceValue	(	const RWCString &	key,
		const RWstoredValue	newVal,
		RWstoredValue &	oldVal
	)

Attempts to replace the RWstoredValue now associated with key by the value newVal. If successful, the previous value is returned by reference in oldVal, and the method returns true, or otherwise false.

RWdiskTreeCompare RWBTreeOnDisk::setComparison ( RWdiskTreeCompare fun )

Changes the comparison function to fun and returns the old function. The function should return a number less than, equal to, or greater than zero, depending on whether the first argument is less than, equal to or greater than the second argument, respectively. The third argument is the key length. Possible choices (among others) are std::strncmp() (the default), or std::strnicmp() (for case-independent comparisons). If you set the comparison function to behave differently after data has already been stored, RWBTreeOnDisk will exhibit undefined behavior that is probably incorrect.

Friends And Related Function Documentation

typedef void(* RWdiskTreeApply) (const char *, RWstoredValue, void *)

A typedef for the function used in the method applyToKeyAndValue(RWdiskTreeApply, void*). This function may not change the first argument, i.e. the key. The last argument can be anything and is passed through from the call to applyToKeyAndValue(RWdiskTreeApply, void*).

typedef int(* RWdiskTreeCompare) (const char *, const char *, size_t)

A typedef for the comparison function to be used with RWBTreeOnDisk. It should return a number less than, equal to, or greater than zero, depending on whether the first argument argument is less than, equal to, or greater than the second argument, respectively. The third argument is the key length.

See also: setComparison(RWdiskTreeCompare)

typedef unspecified_type RWstoredValue

SourcePro® API Reference Guide

Public Types

Public Member Functions

Related Functions

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation