| Data Types |
| createMode styleMode |
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);
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 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.
None
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. |
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);
Constructs 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. |
| nbuf | The maximum number of nodes that can be cached in memory. |
| omode | 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), 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. |
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 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 find(const char* ky)const ;
This is a synonym for contains(ky).
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 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. This member function may throw an RWFileErr exception.
int insertKeyAndValue(const char* ky,RWstoredValue v);
Adds a key-value pair to the B-tree. Returns TRUE for successful insertion, FALSE otherwise. This member function may throw an RWFileErr exception.
RWBoolean isEmpty() const;
Returns TRUE if this RWBtreeOnDisk contains no data, FALSE otherwise.
unsigned keyLength() const;
Returns 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;
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 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 for your calculations about how many nodes to cache.
unsigned occurrencesOf(const char* ky) const;
Returns 1 if ky is found, 0 otherwise.
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.
void remove(const char* ky);
Removes the key and value pair that has a key that matches ky. This member function may throw an RWFileErr exception.
void
removeKeyAndValue(const char* ky,
RWCString& retKey,
RWstoredValue& retVal);
Removes the key and value pair that has a key that matches ky. The removed data is returned in the reference arguments retKey and retVal. This member function may throw an RWFileErr exception.
void
removeKeyAndValue(const char* ky
RWstoredValue& retVal);
Removes the key and value pair that has a key that matches ky. The removed value is returned in the reference argument retKey. 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 method 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);
It 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 strncmp() (the default), or strnicmp() (for case-independent comparisons). If you set the comparison function to behave differently after data has already been stored, RWBtreeOnDisk will exhibit unspecified (wrong!) behavior.