SourcePro® 2024.1 |
SourcePro® API Reference Guide |
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 Symbols | |
(Note that these are not member symbols.) | |
typedef void(* | RWdiskTreeApply) (const char *, RWstoredValue, void *) |
typedef int(* | RWdiskTreeCompare) (const char *, const char *, size_t) |
typedef unspecified_type | RWstoredValue |
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:
true
for parameter ignoreNull
in the constructor.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.
This enumeration is used by the constructor to determine whether to force the creation of a new tree.
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. |
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.
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.
|
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:
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.
|
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.
|
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.
|
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.
Sets the location where this RWBTreeOnDisk keeps your own application-specific information to newlocation. Returns the previous value.
|
inline |
This is a synonym for contains(key).
|
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.
|
inline |
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.
|
inline |
Returns true
if this RWBTreeOnDisk contains no data, false
otherwise.
|
inline |
Returns the length of the keys for this RWBTreeOnDisk. This number is set when the tree is first constructed, and cannot be changed.
|
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.
|
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.
|
inline |
Returns 1
if key is found, 0
otherwise.
|
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.
|
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.
|
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.
|
related |
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*).
|
related |
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.
|
related |
An unspecified signed integer type representing a file offset.
Copyright © 2024 Rogue Wave Software, Inc., a Perforce company. All Rights Reserved. |