Overview |
Topics |
|
A B-tree is a data structure that maintains an ordered set of data and allows efficient operations to find, delete, insert, and browse the data stored in the tree. For a detailed overview of tree data structures see the Balanced Binary Tree page. In this implementation, a balanced multi-way file based tree class is used to create index files. Index files are used to rapidly locate objects in a VBD data file. Each piece of data stored in the B-tree is called a key. Because each key is unique it can only occur in one location.
A B-tree consists of node records containing multiple keys, and branches that link the nodes of the B-tree together. In this design one tree node corresponds to a chuck of data, called a page. B-trees offer fast disk based searching by loading pages, rather then individual items. Keys are kept in sorted order within each node. This implementation uses multi-way nodes. Multi-way nodes allow the height of a B-tree to be smaller then that of binary trees and make it easier to balance.
Every B-tree is classified by their order n, meaning the nodes contain from n-1 to n/2 keys (so nodes are always at least half full of keys), and n to n/2 + 1 branches (n can be any number.) For example, in a B-tree with an order of seven, each node can have up to seven branches. Corresponding to these branches are three keys that help in determining which branch to take during a search.
In this implementation, the B-tree class has order n nodes with up to n branches and n-1 keys. The order specifies the maximum number of branches. A node may have fewer branches than the maximum. The B-tree class maintains balance by implementing the following properties: except for the root node, all nodes must have at least (n-1)/2 keys and (n-1)/2 + 1 branches. This means that all nodes except the root node are always at least half full of keys. The B-tree order is defined by the NBR global integer constant. An NBR of seven means that all non-root nodes must have at least three keys. NOTE: The leaves of the B-tree class are always on the same level.
The EntryKey and Mnode classes are used to make up the balanced multi-way tree. The Mnode class is responsible for inserting, deleting, and searching for keys in a node. It ensures that each node in the tree will have a left branch that leads to all nodes with keys smaller than the smallest key. The right branches will be paired with a key, each branch leading to all nodes with keys greater than the given key, but less than the key to the right. Branches are indexed from -1 to NBR-2. The -1th branch represents the left branch and the 0th branch is the right branch of the first entry. NOTE: If the NBR constant (B-tree order) is changed, all the VBD index files will have to be rebuilt if they used a different NBR value when they were created.
Key names are fixed in length by the global MAXKEYSIZE integer constant. Each entry consists of a 64-byte string or 512-bit value representing an object's name, a 32-bit integer representing an object's file address in the data file, and a 32-bit integer representing the class ID of an object. The object's file address, in the data file, represents the object's identification number. Using the data file address to ID the object ensures that the identity of each object will be unique. This feature allows duplicate objects to be stored in the database. NOTE: If the MAXKEYSIZE constant is changed, all the VBD index files will have to be rebuilt if they used a different MAXKEYSIZE value when they were created.
Searching a B-tree for a key always begins at the root node and follows the branches from node to node until either the key is located or the search fails. A search fails when a leaf node is reached and there are no more branches to follow. Searching a balanced tree means that all leaves are at the same depth. There is no runaway pointer overhead. Even very large B-trees can guarantee only a small number of nodes must be retrieved to find a given key.
B-trees grow when new keys are inserted. The B-tree class walks down the tree until a duplicate entry key is found (which is not allowed) or it finds a leaf node. At this point the B-tree class will attempt to insert the new entry into the leaf. If the leaf is not full the key is simply inserted. Otherwise, the node is split in half by sending one of its entries up the tree to be inserted into the parent node. The B-tree class will always use the median entry, as defined in sort order, to split the node. If the parent is full and cannot handle the median entry, the parent must be split. If the parent is split, the parent's median entry sent further up the tree. Eventually, the root node might have to split in half, and a new root created to contain the median entry. B-trees always grow at the root due to bottom-up node splitting. This keeps the leaves all at the same level and results in a well-balanced tree.
Deleting B-tree entries is much more complicated then insertions, due to the balance that must be maintained. After deleting an entry from a leaf, the B-tree class checks to see whether the node still has the minimum required number of entries. If not, another entry is borrowed from other node's left and right siblings. A sibling entry is moved into the parent node, then the original parent entry is moved into the node needing the entry. When both the left and right siblings have entries to spare the B-tree class will always choose the left sibling. If neither sibling has any extra entries the B-tree class will merge a given node with one of the siblings, as well as an entry from the parent node. In the case of a left merge, the original parent entry has its right link set to the left link of the right node so the B-tree class can keep track of any nodes below the ones involved in the merge. If the parent node ends up with too few entries, it must borrow entries or merge with one of its siblings. If the root becomes empty due to a merge, the tree shrinks one level with the new root being the node to the left of the old root.
The Btree class is file based and incorporates its own caching system. The VBD file manager and the Cache classes are used to handle all file operations. When a B-tree file is created a static storage area is reserved for the B-tree header in its VBD file. The B-tree header contains the address of the root node, the order, the number of entries, the number of nodes, and the tree height. All B-tree operations start at the root node each time the file is opened. If a file contains more then one B-tree, the appropriate static storage area must be reserved for the tree headers. Each B-tree will have its own cache of buckets that store multi-way nodes. NOTE: By default the B-tree cache class and its supporting classes are implemented as template classes. In order to avoid portability problems, a non-template version of these classes can by enabled by defining the __NOT_USING_TEMPLATE_CLASS__ at compile time.
Btree::Btree(int CacheSize = 8) - Class constructor responsible for initializing the B-tree cache, cache pointer, and the file pointer. The file pointer is initially set to zero when a B-tree object is constructed.
Btree::~Btree() - Class destructor responsible for disconnecting the B-tree from the file and the memory cache.
Exceptions:
CDanglingPtr
CEOFError
CFileWriteError
CFileNotWriteable
CFileSeekError
CChecksumError
CAccessViolation
CFileReadError
CFileNotReady
int Btree::Connect(VBDFilePtr &fptr, int create, FAU bha=sizeof(FileHeader)) - Public member function used to connect the B-tree to an already open file. If create is true, a new B-tree is created but not a new file. Returns true if successful.
Exceptions:
CDanglingPtr
CEOFError
CFileWriteError
CFileNotWriteable
CFileSeekError
CCacheFull
CAccessViolation
CFileReadError
CFileNotReady
CChecksumError
void Btree::Disconnect() - Public member function used to disconnect the B-tree from the file and the memory cache.
Exceptions:
CDanglingPtr
CEOFError
CFileWriteError
CFileNotWriteable
CFileSeekError
CChecksumError
CAccessViolation
CFileReadError
CFileNotReady
int Btree::Create(char *FName, FAU bha=sizeof(FileHeader)) - Public member function used to create a new file to hold the B-tree. Disconnects the B-tree from any open files before creating the new file. Returns true if successful.
Exceptions:
CFileCreationError
CEOFError
CFileWriteError
CFileNotWriteable
CDanglingPtr
CFileCloseError
CFileSeekError
CCacheFull
CAccessViolation
CFileReadError
CFileNotReady
CChecksumError
int Btree::Open(char *FName, VBDFile::AccessMode mode, FAU bha=sizeof(FileHeader)) - Public member function used to open an existing file to hold the btree. Disconnects the B-tree from any open files before opening the file. Returns true if successful.
Exceptions:
CFileOpenError
CWrongFileType
CAccessViolation
CFileReadError
CFileNotReady
CDanglingPtr
CFileCloseError
CFileSeekError
CEOFError
CFileWriteError
CFileNotWriteable
CCacheFull
CChecksumError
void Btree::Flush(int clear=0) - Public member function used to flush all buffers to disk. When flushing the cache in read-only mode, no data is actually written. However, Btree::Flush() is called anyway to check for dangling cache pointers.
Exceptions:
CDanglingPtr
CEOFError
CFileWriteError
CFileNotWriteable
CFileSeekError
CChecksumError
CAccessViolation
CFileReadError
CFileNotReady
void Btree::Close() - Public member function used to disconnect the B-tree from the file and the memory cache.
Exceptions:
CDanglingPtr
CEOFError
CFileWriteError
CFileNotWriteable
CFileSeekError
CChecksumError
CAccessViolation
CFileReadError
CFileNotReady
int Btree::Search(EntryKey &e) - Public member function used to recursively search the tree for the first node having only a matching EntryKey::key. This function does not attempt to match the EntryKey::class_id or the EntryKey::object_address members. If a matching entry is found, the EntryKey::key field of e is filled in. Returns true if successful.
int Btree::Search(char *key) - Public member function used to recursively search the tree for the first node having a matching EntryKey::key only. This function does not attempt to match the EntryKey::class_id or the EntryKey::object_address members. Returns true if successful.
int Btree::FullSearch(const EntryKey &e) - Public member function used to recursively search the tree for the first node having a matching EntryKey::key, EntryKey::class_id, and EntryKey::object_address. If a matching entry is found, the EntryKey::key, EntryKey::class_id, and EntryKey::object_address fields of e is filled in. Returns true if successful.
int Btree::FullSearch(char *key, FAU object_address, FAU class_id) - Public member function used to recursively search the tree for the first node having a matching EntryKey::key, EntryKey::class_id, and EntryKey::object_address. Returns true if successful.
int Btree::Add(char *key, FAU object_address = 0, FAU class_id = 0, int flush = 1) - Public member function used to add a new entry key into the B-tree. The Btree::Add() function calls the recursive Btree::Insert() function after constructing the entry to be inserted. If Btree::Add() sees a node overflow generated by the Btree::Insert() function it will grow a new root with the median entry passed back, by reference, as the root's sole entry. If the entry could not be inserted a __DUPLKEY__ key or __ALLOCERR__ error will be returned. Returns true if successful. If the flush variable is true the cache will be flushed with each add operation to ensure that the B-tree file header stays in sync during multiple file access.
Exceptions:
CCacheFull
CNullPtr
CDanglingPtr
CEOFError
CFileWriteError
CFileNotWriteable
CFileSeekError
CAccessViolation
CFileReadError
CFileNotReady
CChecksumError
int Btree::Add(EntryKey &e, int flush = 1) - Public member function used to add a new entry key into the B-tree. The Btree::Add() function calls the recursive Btree::Insert() function to perform the actual insertion. If Btree::Add() sees a node overflow generated by the Btree::Insert() function it will grow a new root with the median entry passed back, by reference, as the root's sole entry. If the entry could not be inserted a __DUPLKEY__ key or __ALLOCERR__ error will be returned. Returns true if successful. If the flush variable is true the cache will be flushed with each add operation to ensure that the B-tree file header stays in sync during multiple file access.
Exceptions:
CCacheFull
CNullPtr
CDanglingPtr
CEOFError
CFileWriteError
CFileNotWriteable
CFileSeekError
CAccessViolation
CFileReadError
CFileNotReady
CChecksumError
int Btree::Remove(char *k, FAU object_address = 0, FAU class_id = 0, int flush = 1) - Public member function used to delete an entry key from the B-tree. The Btree::Remove() function calls the recursive Btree::Delete() function after constructing the key to be removed. After the call to the Btree::Delete() function, the Btree::Remove() function checks to see if the root node has become empty due to a merge that took place below it . If so, the root is removed from the tree and the node to the root's left becomes the new root. If the old, empty, root is the only node in the tree, it is left empty so there is at least one node in the tree. Returns true if successful or false if the entry was not found in the tree. If the flush variable is true the cache will be flushed with each remove operation to ensure that the B-tree file header stays in sync during multiple file access.
Exceptions:
CAssertError
CDanglingPtr
CSyncError
CAccessViolation
CFileReadError
CFileNotReady
CEOFError
CFileWriteError
CFileNotWriteable
CFileSeekError
CChecksumError
int Btree::Remove(EntryKey &e, int flush = 1) - Public member function used to delete an entry key from the B-tree. The Btree::Remove function calls the recursive Btree::Delete() function to due the actual deletion. After the call to the Btree::Delete() function, the Btree::Remove() function checks to see if the root node has become empty due to a merge that took place below it . If so, the root is removed from the tree and the node to the root's left becomes the new root. If the old, empty, root is the only node in the tree, it is left empty so there is at least one node in the tree. Returns true if successful or false if the entry was not found in the tree. If the flush variable is true the cache will be flushed with each remove operation to ensure that the B-tree file header stays in sync during multiple file access.
Exceptions:
CAssertError
CDanglingPtr
CSyncError
CAccessViolation
CFileReadError
CFileNotReady
CEOFError
CFileWriteError
CFileNotWriteable
CFileSeekError
CChecksumError
int Btree::IsEmpty() const - Public member function that returns true if the B-tree is empty, base on the node count stored in the tree header.
int Btree::IsOpen() const - Public member function that returns true if the file is open.
int Btree::IsOK() const - Public member function that returns true if the file status is ok.
void Btree::ClearErr() - Public member function use to clear file errors.
FAU Btree::GetRootAddr() - Public member function that returns the tree's root file address as stored in the tree header.
INT32 Btree::GetOrder() - Public member function that returns the tree's order as stored in the tree header.
INT32 Btree::GetNumEntries() - Public member function that returns the number of entries as stored in the tree header.
INT32 Btree::GetNumNodes() - Public member function that returns the number of node as stored in the Btree header.
INT32 Btree::GetHeight() - Public member function that returns the tree's height as stored in the Btree header.
VBDFilePtr Btree::GetFilePtr() - Public member function that returns the reference counted VBD file pointer that the tree is currently using.
FAU Btree::GetHeaderAddr() - Public member function the returns the file address of the tree header stored on disk.
CachePointer Btree::GetRoot() - Public member function that returns the cache pointer that represents the tree's root node.
Cache <Mnode>
Cache *Btree::GetCache() - Public member that returns a pointer to the cache that the B-tree is currently connect to. NOTE: this version is selected at compile time by defining the __NOT_USING_TEMPLATE_CLASS__ macro. This macro compiles the non-template versions the Bucket, CachePtr, and Cache class. The __BTREE_MNODE__ must be defined at compile time to code the Bucket, CachePtr, and Cache classes for the Mnode class type. If the __NOT_USING_TEMPLATE_CLASS__ macro is not defined the __USING_TEMPLATE_CLASS__ macro is defined by default.
void Btree::ReadHdr() - Protected member function used to read the tree header from disk. The tree header is used to store the file address of the root node, the order of the tree, the height of the tree, the number of entries and the number of nodes from one program invocation to the next. Tree headers are always stored in the file's pre-allocated static storage area.
Exceptions:
CAccessViolation
CFileReadError
CFileNotReady
CFileSeekError
void Btree::WriteHdr() - Protected member function used to write the tree header to disk. The tree header is used to store the file address of the root node, the order of the tree, the height of the tree, the number of entries and the number of nodes from one program invocation to the next. Tree headers are always stored in the file's pre-allocated static storage area.
Exceptions:
CEOFError
CFileWriteError
CFileNotWriteable
CFileSeekError
CChecksumError
CAccessViolation
CFileReadError
CFileNotReady
int Btree::Insert(EntryKey &e, CachePointer t) - Protected member function used by the Btree::Add() function to insert entry e into sub-tree t. The Btree::Insert() function is a recursive function that walks down the tree to a leaf node, inserts the entry there, and then propagates any splits up the tree as the recursion unwinds. The __DUPLKEY__, __ALLOCERR__, or __NODE_OVERFLOW__ function status codes are used to control the recursion. Returns true if entry was inserted without any errors or node overflows. A node overflow indicates that the node below was split. The median entry will be sent back to the Btree::Insert() function until it is inserted or the top of the tree is reached and the last call to Btree::Insert() is unwound. If Btree::Add() sees a node overflow it will grow a new root with the median entry passed back, by reference, as the root's sole entry. If the entry could not be inserted a duplicate key or allocation error will be returned.
Exceptions:
CCacheFull
CNullPtr
CDanglingPtr
CEOFError
CFileWriteError
CFileNotWriteable
CFileSeekError
CAccessViolation
CFileReadError
CFileNotReady
CChecksumError
int Btree::Delete(EntryKey &e, CachePointer t) - Protected member function used by the Btree::Remove() function to delete entry e from sub-tree with root t. The Btree::Delete() function searches the tree for the entry to delete, using recursive calls to itself. When the entry is found, the tree is further traversed in search of the successor entry to use as the replacement. When the entry has been replaced, the Btree::Delete() function is recursively called again to delete the successor entry in its original leaf node. The recursion bottoms out when an entry is deleted from a leaf node. At this point, the entry is removed from the node and the Btree::RestoreBalance() function is called to do any rotation or merging necessary to ensure that the node with the deleted entry has the minimum number of entries. As the recursion unwinds the merging process is propagated up the tree as needed. The Btree::Remove() function checks to see if the root node has become empty due to a merge that took place below it after the Btree::Delete() function returns. If so, the root is removed from the tree by the Btree::Remove() function and the node to the root's left becomes the new root. If the old, empty, root is the only node in the tree, it is left empty so there is at least one node in the tree. Returns true if successful or false if the entry was not found in the tree.
Exceptions:
CAssertError
CDanglingPtr
CSyncError
CAccessViolation
CFileReadError
CFileNotReady
CEOFError
CFileWriteError
CFileNotWriteable
CFileSeekError
CChecksumError
void Btree:: RestoreBalance(CachePointer p, int posn) - Protected member function used to do any rotation or merging necessary to ensure that the node with a deleted entry has the minimum number of entries. The function is called when the node below the branch at position posn in parent node p does not have enough entries. The node will be given an entry from either its left or right sibling, or merged with a sibling.
void Btree::RotateRight(CachePointer p, int posn) - Protected member function used by the Btree::RestoreBalance() function to do a right rotation using the entry at parent node p and position posn as the pivot point. This function assumes that parent node p is not a leaf and that it has a left and right child. Also assumes that the right child is not full, and that parent node p and its left child are not empty.
void Btree::RotateLeft(CachePointer p, int posn) - Protected member function used by the Btree::RestoreBalance() function to do a left rotation using the entry at parent node p and position posn as the pivot point. This function assumes that parent node p is not a leaf and that it has a left and right child. Also assumes that the left child is not full, and that parent node p and its right child are not empty.
void Btree::Merge(CachePointer p, int posn) - Protected member function used by the Btree::RestoreBalance() function to merge a node. This function merges the node on the branch to the left of the entry at position posn of parent node p, with an entry of parent node p and the node on the branch to the right of an entry of parent node p. This function assumes that position posn is in range.
Exceptions:
CDanglingPtr
CSyncError
CAccessViolation
CFileReadError
CFileNotReady
CEOFError
CFileWriteError
CFileNotWriteable
CFileSeekError
CChecksumError
void Btree::ReInit(int flush = 0) - Reconnect the cache and the B-tree header to ensure that the memory buffers and the file data stay in sync during multiple file access and multiple instances of the same application. If the flush variable is true, the cache and the file buffers will be flushed to disk before reconnecting the cache.
Exceptions:
CAccessViolation
CFileReadError
CFileNotReady
CFileSeekError
CDanglingPtr
CEOFError
CFileWriteError
CFileNotWriteable
CChecksumError
int Btree:TestTree() - This function is used to ensure that the memory buffers and the file data stay in sync during multiple file access.
Exceptions:
CAccessViolation
CFileReadError
CFileNotReady
CFileSeekError
CDanglingPtr
CEOFError
CFileWriteError
CFileNotWriteable
CChecksumError
Mnode::Mnode() - Default class constructor.
int Mnode::Search(const EntryKey &e, int &posn) - Public member function used to search the node for the first key having a matching EntryKey::key only. This function does not attempt to match the EntryKey::class_id or the EntryKey::object_address members. It passes back the position of a matching entry by reference, or the position of the entry containing the appropriate branch to keep searching down if no matching entry is found. If a matching entry is found, the EntryKey::key field of e is filled in. Returns -1 if e's key is less than all keys in the node, returns 0 if there was a match, or returns 1 if e's key is greater than all keys in the node.
int Mnode::FullSearch(const EntryKey &e, int &posn) - Public member function used to search the node for the first key having a matching EntryKey::key, EntryKey::class_id, and EntryKey::object_address. It passes back the position of a matching entry by reference, or the position of the entry containing the appropriate branch to keep searching down if no matching entry is found. If a matching entry is found, the EntryKey::key, EntryKey::class_id, and EntryKey::object_address field of e is filled in. Returns -1 if e's key is less than all keys in the node, returns 0 if there was a match, or returns 1 if e's key is greater than all keys in the node.
void Mnode::Split(Mnode &b, int split_posn) - Public member function used to move the right half of this node at split_posn into empty node b. This function assumes split_posn is in range.
void Mnode::InsEntryKeyEntryKey &e, int posn) - Public member function used to insert entry e into the node at position posn. This function assumes there is enough room in the node and that position posn is less then or equal to the number of entries that are actually in use.
void Mnode::Cat(EntryKey &e) - Public member function used to insert entry e into this node.
void Mnode::Cat(Mnode &n) - Public member function used to add all the entries of node n to the end of this node. This function assumes there is enough room in this node.
void Mnode::DelEntryKey(int posn) - public member function used to delete the entry at position posn. This function assumes that position posn is in range.
INT32 &Mnode::Branch(int posn) - Public member function that returns the branch for the given position posn. The left branch is returned if position posn equals -1. NOTE: In order for this version of the Mnode::Branch() function to work there cannot be any gaps between the left field and the entry field in the Mnode class. To bypass this rule explicitly test for -1 and return the left branch.
INT32 &Mnode::GetBranchs(int posn) - Public member function that returns the branch for the given position posn. The left branch is returned if position posn equals -1.
INT32 Mnode::LastPosn() - Public member function that returns the last position in the node.
int Mnode::IsEmpty() - Public member function the returns true if this node is empty.
int Mnode::IsFull() - Public member function the returns true if this node is full.
int Mnode::IsPoor() - Public member function the returns true if this node has fewer than the minimum number of entries required.
int Mnode::IsPlentiful() - Public member function the returns true if this node has more than the minimum number of entries required.
EntryKey::EntryKey() - Default class constructor.
EntryKey::EntryKey(const char *s) - General class constructor used to construct an entry key object, filling in only EntryKey::key field. The object address and class ID fields will be set to zero.
EntryKey::EntryKey(const char *s, INT32 oa, INT32 ci) - General class constructor used to construct an entry key object filling in the EntryKey::key, EntryKey::object_address, and the EntryKey::class_id fields.
EntryKey::EntryKey(const EntryKey &s) - Class copy constructor responsible for copy constructing an object. The EntryKey::key, EntryKey::object_address, and the EntryKey::class_id fields will be copied and the object's right child pointer will be set to zero.
void EntryKey::operator=(const EntryKey &s) - Class assignment operator used to assign the entire contents of one EntryKey object to another.
void EntryKey::operator=(const char *s) - Class assignment operator used to assign the object's EntryKey::key field to the given null-terminated character string.
void EntryKey::SetStrKey(char *s) - Public member function used to set the EntryKey::key field to the given null-terminated character string.
void EntryKey::SetStrKey(const char *s) - Public member function used to set the EntryKey::key field to the given null-terminated character string.
void EntryKey::SetOA(INT32 oa) - Public member function used to set the EntryKey::object_address field to the given object address.
void EntryKey::SetCID(INT32 cid) - Public member function used to set the EntryKey::class_id field to the given class ID.
char *EntryKey::GetStrKey() - Public member function that returns a string representing this object's EntryKey::key field.
const char *EntryKey::GetStrKey() const - Public member function that returns a string representing this object's EntryKey::key field.
INT32 EntryKey::GetOA() - Public member function that returns a 32 bit integer value representing this object's EntryKey::object_address field.
INT32 EntryKey::GetOA() const - Public member function that returns a 32 bit integer value representing this object's EntryKey::object_address field.
INT32 EntryKey::GetCID() - Public member function that returns a 32 bit integer value representing this object's EntryKey::class_id field.
INT32 EntryKey::GetCID() const - Public member function that returns a 32 bit integer value representing this object's EntryKey::class_id field.
friend int Compare(const EntryKey &a, const EntryKey &b) - Friend function used to do a partial compare of EntryKey objects a and b. Compares only the EntryKey::key field. Returns -1 if EntryKey object a is less then b, 0 if a equals b, or 1 if a is greater then b.
friend int FullCompare(const EntryKey &a, const EntryKey &b) - Friend function used to do a full compare of EntryKey objects a and b. Compares the EntryKey::key, EntryKey::object_address and EntryKey::class_id fields. Returns -1 if EntryKey object a is less then b, 0 if a equals b, or 1 if a is greater then b.
void EntryKey::SetClassID(INT32 id) - Public member function used to set the EntryKey::class_id field to the given class ID.
void EntryKey::SetObjectAddress(INT32 addr) - Public member function used to set the EntryKey::object_address field to the given object address.
INT32 EntryKey::ClassID() - Public member function that returns a 32 bit integer value representing this object's EntryKey::class_id field.
INT32 EntryKey::ObjectAddress() - Public member function that returns a 32 bit integer value representing this object's EntryKey::object_address field.
BtreeWalkerb Class
BtreeWalker Class
BtreeWalk Function
InMemCopy Class
The BtreeWalkerb class defines a generic iterator used to visit every node in a B-tree using a specified walk order: btPREORDER, btPOSTORDER, btINORDER, or btLVLORDER. The BtreeWalkerb class turns the recursive BtreeWalk() function into an iteration by using an explicit stack. It is designed to be used as base class or in conjunction with another class to traverse the B-tree and process the entry keys.
BtreeWalkerb::BtreeWalkerb(Btree *t, BtreeWalkOrder w) - Class constructor responsible for setting a pointer to the root node and setting the walk order. BtreeWalkOrder is an enumeration used to specify btPREORDER, btPOSTORDER, btINORDER, or btLVLORDER traversal.
virtual BtreeWalkerb::~BtreeWalkerb() - Class destructor provided for virtuality.
void BtreeWalkerb::Reset() - Public member function used to reset this object's root node pointer and walk order.
void BtreeWalkerb::Reset(Btree *t, BtreeWalkOrder w) - Public member function used to set this object's root node pointer and walk order. BtreeWalkOrder is an enumeration used to specify btPREORDER, btPOSTORDER, btINORDER, or btLVLORDER traversal. This function is responsible for initializing the NextFptr member function pointer by giving it the address of a traversal function: BtreeWalkerb::NextPreOrder(), BtreeWalkerb::NextInOrder(), BtreeWalkerb::NextPostOrder(), or BtreeWalkerb::NextLvlOrder(). These member functions do not have access to the stack stored in the iterator object. They use an explicit stack to store node pointers when walking up and down the tree and do not process the node data when visiting. Instead of making a call to a pre-defined visit function, these functions return a pointer to the node visited.
CachePointer BtreeWalkerb::Next() - Public member function that returns a pointer to the next node in sequence. This function makes a call to the one of the traversal functions pointed to by the NextFptr member function pointer.
CachePointer (BtreeWalkerb::*NextFptr)() - Pointer to one of the tree transversal functions: BtreeWalkerb::NextPreOrder(), BtreeWalkerb::NextInOrder(), BtreeWalkerb::NextPostOrder(), or BtreeWalkerb::NextLvlOrder(). NOTE: A pointer to non-static member functions must be handled differently than ordinary function pointers. C++ introduces a new type of pointer, called a pointer-to-member, which can be invoked only by providing an object. A pointer-to-member-function is not required to contain the machine address of the appropriate function. It cannot be cast into a pointer-to-function. Non-static member functions have a hidden parameter that corresponds to the this pointer. The this pointer, points to the instance data for the object. In order to invoke the call an object must be specified to make the member function call. The BtreeWalkerb::Next() function calls the member function pointer NextFptr using the object in question: return (this->*NextFptr)();
CachePointer BtreeWalkerb::NextPreOrder() - Protected member function used to visit each node in the tree using pre-order traversal (parent, left sub-tree, then the right sub-tree) using an explicit stack. Returns a pointer to the node to be visited.
CachePointer BtreeWalkerb::NextInOrder() - Protected member function used to visit each node in the tree using in-order traversal (left sub-tree, parent, then the right sub-tree), using an explicit stack. Returns a pointer to the node to be visited.
CachePointer BtreeWalkerb::NextPostOrder() - Protected member function used to visit each node in the tree using post order traversal (left sub-tree, right sub-tree, then the parent), using an explicit stack. Returns a pointer to the node to be visited.
CachePointer BtreeWalkerb::NextLvlOrder() - Protected member function used to visit each node in the tree from top to bottom, left to right, level by level. Returns a pointer to the node to be visited.
The BtreeWalker class is a general-purpose class used in conjunction with the BtreeWalkerb class to sort the entry keys and perform basic search operations.
BtreeWalker::BtreeWalker(Btree *t) - Class constructor responsible for setting a pointer to the B-tree.
unsigned BtreeWalker::Sort(EntryKeyVisitFunc Visit) - Public member function used to sort the entry keys in alphabetical order. EntryKeyVisitFunc is a function pointer that points to a visit action defined in the application. The visit action defines a procedure used to process entry keys as they are sorted.
int BtreeWalker:: Find(const EntryKey &key, EntryKey &e) - Public member function used to find a specified entry key. Will return true if the key is found or false if the key is not found. The key name, object address, and class ID of the matching entry key will be passed back in entry key "e".
unsigned BtreeWalker:: Partiallookup(const char *p, EntryKeyVisitFunc Visit) - Public member function that searches for sub-string pattern "p" in each entry key. EntryKeyVisitFunc is a function pointer that points to a visit action defined in the application. The visit action defines a procedure used to process the entry key if a matching sub-string is found. Returns the number of matches found or zero if no matching sub-strings are found.
The BtreeWalk() function is a standalone function that performs a recursive level order traversal used for walking the B-tree and processing node data.
void BtreeWalk(CachePointer t, BtreeVisitFunc Visit, Btree *tree = 0) - This is a recursive function used to walk through the B-tree node by node. BtreeVisitFunc is a function pointer that points to a visit action defined in the application. The visit action defines a procedure used to process node data. If a pointer to the B-tree is passed to this function, the tree header is tested to ensure that the memory buffers and the file data stay in sync during multiple file access.
The InMemCopy class is used as a container to store the entry keys in memory with as little overhead as possible. It can be used with the BtreeWalk() function or any other iterations that need to load the contents of a B-tree in memory for display, data file searching, or printing applications. Unlike the EntryKey class the InMemCopy class does not used fixed length strings. Variable length strings, created by the User Defined String Class, allow the InMemCopy class to allocate the minimum amount of memory needed to store an entry key.
class InMemCopy
{
public:
InMemCopy() { }
~InMemCopy() { }
InMemCopy(char *k, INT32 oa, INT32 cid) {
int len = strlen(k);
UString buf(k, len); // Allocate the minimum amount needed
key = buf;
object_address = oa;
class_id = cid;
}
InMemCopy(const InMemCopy &ob) {
key = ob.key;
object_address = ob.object_address;
class_id = ob.class_id;
}
void operator=(const InMemCopy &ob) {
key = ob.key;
object_address = ob.object_address;
class_id = ob.class_id;
}
public:
UString key; // Unique data key
INT32 object_address; // Object's address in the database file
INT32 class_id; // Class ID number of the object
};
The B-tree class can generate any of the following exceptions if the CPP_EXCEPTIONS macro is defined in the EHandler class at compile time. NOTE: The appropriate try and catch statements within the application must handle these exceptions or the program will terminate. If the CPP_EXCEPTIONS macro is not defined, the global error hander will signal that an exception has occurred and will terminate the program as defined in the EHandler::Terminate() function.
CAssertError - this exception is thrown if any assumptions made during program execution are evaluated and do not meet the conditions specified within the application, causing the entry not to be processed.
CCacheFull - this exception is thrown if all the cache buckets are locked, indicating that no more buckets can be acquired until another bucket is released.
CNullPtr - this exception is thrown if an attempt is made to access a null file address or null memory location.
CAccessViolation - this exception is thrown if an "end of file" error occurs during multiple file access. This exception was added to tell the application that the file has grown in size but the EOF marker has not.
CDanglingPtr - this exception is thrown if there are any dangling references to a reference counted pointer, indicating that a copy of this object is still being used by another object.
CEOFError - this exception is thrown if an "end of file" error is encountered.
CFileCloseError - this exception is thrown if the file cannot be closed.
CFileCreationError - this exception is thrown if the file cannot be created.
CFileNotReady - this exception is thrown if the file is not ready for reading.
CFileNotWriteable - this exception is thrown if the file cannot be written to.
CFileOpenError - this exception is thrown if the file cannot be opened because it does not exist or cannot be accessed in the specified file access mode.
CFileReadError - this exception is thrown if an error occurs while reading from the file.
CFileSeekError - this exception is thrown if an error is encountered during a seek operation.
CFileWriteError - this exception is thrown if the number of bytes written do not match the number of bytes requested to write.
CSyncError - this exception is thrown if the block header's check word cannot be read. This indicates a file synchronization error, meaning the VBD file manager is not reading a valid variable data block or the block is corrupt.
CWrongFileType - this exception is thrown if the file is not a VBD file type or the header is damaged and cannot be identified by the signature string in the file header.
CChecksumError - this exception is thrown if a bit error occurs when writing to disk. A 32-bit CRC checksum based on the Ethernet polynomial of 0x4C11DB7 is calculated when any data is written to the VBD file. The calculated checksum is then compared to data actually stored on disk. If the calculated checksum does not match the actual checksum, a bit error has occurred during data storage.