RWBTreeOnDisk(3C++) RWBTreeOnDisk(3C++)
NameRWBTreeOnDisk - Rogue Wave library class
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");
RWBTreeOnDiskbt(fm);
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 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 (see
below);
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 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) then
the location will be retrieved from the RWFileManager using function
start() (see class RWFileManager). 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
Page 1
RWBTreeOnDisk(3C++) RWBTreeOnDisk(3C++)
order of the B-tree can be set in the constructor. Larger values will
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.
Persistence
None
Enumerations
enum styleMode {V6Style, V5Style};
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.
V6Style Initialize a new tree using V6.X style trees. This is the
default.
V5Style Initialize a new tree using V5.X style trees. In this case, the
key length is fixed at 16 bytes.
enum createMode {autoCreate, create};
This enumeration is used by the constructor to determine whether to force
the creation of a new tree.
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.
Public Constructor
RWBTreeOnDisk(RWFileManager& f,
unsigned nbuf = 10,
createMode omode = autoCreate,
unsigned keylen = 16,
RWBoolean ignoreNull = FALSE,
RWoffset start = RWNIL,
styleMode smode = V6Style,
unsigned halfOrder = 10,
unsigned minFill = 10);
Construct a B-tree on disk. The parameters are as follows:
f The file in which the B-tree is to be managed. This is the only
required parameter.
Page 2
RWBTreeOnDisk(3C++) RWBTreeOnDisk(3C++)
nbuf The maximum number of nodes that can be cached in memory.
omode Determines whether to force the creation of a new tree or whether
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), then
uses the value returned by the RWFileManager's start() member function.
Ignored when creating a new tree.
smode Sets the type of B-tree to create, allowing backwards compatibility
(see above). 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.
Public Member Functions
void
applyToKeyAndValue((*ap)(const char*,RWstoredValue), void* x);
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 may not change the key. The value x can
be anything and is passed through from the call to applyToKeyAndValue().
This member function may throw an RWFileErr exception.
RWoffset
baseLocation() const;
Returns the offset of this tree's starting location within the
RWFileManager. This is the value you will pass to a constructor as the
Page 3
RWBTreeOnDisk(3C++) RWBTreeOnDisk(3C++)
start argument when you want to open one of several trees stored in one
managed file.
unsigned
cacheCount() const;
Returns the maximum number of nodes that may currently be cached.
unsigned
cacheCount(unsigned newcount);
Sets the number of nodes that should be cached to newcount. Returns the
old number.
void
clear();
Removes all items from the collection.This member function may throw an
RWFileErr exception.
RWBoolean
contains(const char* ky) const;
Returns TRUE if the tree contains a key that is equal to the string
pointed to by ky, and FALSE otherwise. This member function may throw an
RWFileErr exception.
size_t
entries();
Returns the number of items in the RWBTreeOnDisk. This member function
may throw an RWFileErr exception.
RWoffset
extraLocation(RWoffset newlocation);
Sets the location where this RWBTreeOnDisk keeps your own application-
specific information to newlocation. Returns the previous value.
RWBoolean
findKey( const char* ky, RWCString& foundKy)const ;
Returns TRUE if ky is found, otherwise FALSE. If successful, the found
key is returned as a reference in foundKy. This member function may throw
Page 4
RWBTreeOnDisk(3C++) RWBTreeOnDisk(3C++)
an RWFileErr exception.
RWBoolean
findKeyAndValue( const char* ky,
RWCString& foundKy,
RWStoredValue& foundVal)const ;
Returns TRUE if ky is found, otherwise FALSE. If successful, the found
key is returned as a reference in foundKy, and the value is returned as a
reference in foundVal. This member function may throw an RWFileErr
exception.
RWstoredValue
findValue(const char* ky)const;
Returns the value for the key that compares equal to the string pointed
to by ky. Returns RWNIL if no key is found. This member function may
throw an RWFileErr exception.
int
height();
Returns the height of the RWBTreeOnDisk. A possible exception is
RWFileErr.
int
insertKeyAndValue(const char* ky,RWstoredValue v);
Adds a key-value pair to the B-tree. Returns TRUE for successful
insertion, FALSE otherwise. A possible exception is RWFileErr.
unsigned
keyLength() const;
Return the length of the keys for this RWBTreeOnDisk. This number is set
when the tree is first constructed and cannot be changed.
unsigned
minOrder()const;
Return 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.
Page 5
RWBTreeOnDisk(3C++) RWBTreeOnDisk(3C++)
unsigned
nodeSize() const;
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 to you for your
calculations about how many nodes to cache.
unsigned
order()const;
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.
RWBoolean
isEmpty() const;
Returns TRUE if the RWBTreeOnDisk is empty, otherwise FALSE.
void
remove(const char* ky);
Removes the key and value pair that has a key which matches ky. This
member function may throw an RWFileErr exception.
RWBoolean
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 methed returns TRUE. Otherwise, returns FALSE.
RWdiskTreeCompare
setComparison(RWdiskTreeCompare fun);
Changes the comparison function to fun and returns the old function.
This function must have prototype:
int yourFun(const char* key1, const char* key2, size_t N);
Page 6
RWBTreeOnDisk(3C++) RWBTreeOnDisk(3C++)
It should return a number less than zero, equal to zero, 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 strncmp() (the
default), or strnicmp() (for case-independent comparisons).
Page 7
