SourcePro® API Reference Guide

 
Loading...
Searching...
No Matches
RWBTreeOnDisk Class Reference

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
 

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");
Represents an ordered collection of associations of keys and values, with keys ordered based on an ex...
Definition disktree.h:125
int(* RWdiskTreeCompare)(const char *, const char *, size_t)
Definition disktree.h:49
unspecified_type RWstoredValue
Definition compat.h:499
Allocates and deallocates storage in a disk file, much like a "freestore" manager.
Definition filemgr.h:66
Persistence
None

Member Enumeration Documentation

◆ 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.

◆ 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::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
fThe file in which the B-tree is to be managed. This is the only required parameter.
cacheBlocksThe maximum number of nodes that can be cached in memory.
cmodeDetermines whether to force the creation of a new tree or to attempt to open an existing tree for update (the default).
keylenThe length of a key in bytes. Ignored when opening an existing tree.
ignoreNullControls 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.
startWhere 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.
smodeSets 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.
halfOrderOne half the order of the B-tree (that is, one half the number of entries in a node). Ignored when opening an existing tree.
minFillThe minimum number of entries allowed in a node (must be less than or equal to halfOrder). Ignored when opening an existing tree.

◆ ~RWBTreeOnDisk()

RWBTreeOnDisk::~RWBTreeOnDisk ( )

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

Member Function Documentation

◆ applyToKeyAndValue()

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.

◆ baseLocation()

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.

◆ cacheCount() [1/2]

unsigned RWBTreeOnDisk::cacheCount ( ) const
inline

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

◆ cacheCount() [2/2]

unsigned RWBTreeOnDisk::cacheCount ( unsigned newcount)

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

◆ clear()

void RWBTreeOnDisk::clear ( )

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

◆ contains()

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.

◆ entries()

unsigned long RWBTreeOnDisk::entries ( ) const

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

◆ extraLocation()

RWoffset RWBTreeOnDisk::extraLocation ( RWoffset newlocation)
inline

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

◆ find()

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

This is a synonym for contains(key).

◆ findKey()

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.

◆ findKeyAndValue()

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.

◆ findValue()

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.

◆ height()

unsigned RWBTreeOnDisk::height ( ) const

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

◆ insertKeyAndValue()

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.

◆ isEmpty()

bool RWBTreeOnDisk::isEmpty ( ) const
inline

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

◆ keyLength()

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.

◆ minOrder()

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.

◆ nodeSize()

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.

◆ occurrencesOf()

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

Returns 1 if key is found, 0 otherwise.

◆ order()

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.

◆ remove()

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.

◆ removeKeyAndValue() [1/2]

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.

◆ removeKeyAndValue() [2/2]

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.

◆ replaceValue()

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.

◆ setComparison()

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 Symbol Documentation

◆ RWdiskTreeApply

typedef void(* RWdiskTreeApply) (const char *, RWstoredValue, void *)
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*).

◆ RWdiskTreeCompare

typedef int(* RWdiskTreeCompare) (const char *, const char *, size_t)
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.

See also
setComparison(RWdiskTreeCompare)

◆ RWstoredValue

typedef unspecified_type RWstoredValue
related

An unspecified signed integer type representing a file offset.

Copyright © 2024 Rogue Wave Software, Inc., a Perforce company. All Rights Reserved.