B-tree Stack Class

Topics:

Overview
Conditional Directives
Constants
Type Definitions
Enumerations
Data Structures
Functions

Overview

The B-tree stack class is used by the non-recursive B-tree functions in place of the processor stack to store node addresses during non-recursive insertions and deletions. The B-tree stack class is essentially a doubly linked-list with stack and queue functions. The stack size is not fixed and grows according the height of the B-tree.

Data Structures

The B-tree stack node type is used to store a signal B-tree node address and pointers to the previous and next nodes in the stack.

struct BtreeStack_t
{
  FAU node_address;   // 32-bit or 64-bit B-tree node address
  BtreeStack_t *next; // Pointer to the next node in the stack
  BtreeStack_t *prev; // Pointer to the previous node in the stack
};

Functions

BtreeStack::BtreeStack()
BtreeStack::~BtreeStack()
BtreeStack::AllocNode()
BtreeStack::Clear()
BtreeStack::DetachNode()
BtreeStack::Extract()
BtreeStack::FreeNode()
BtreeStack::GetHead()
BtreeStack::GetTail()
BtreeStack::Insert()
BtreeStack::InsertAfter()
BtreeStack::InsertBefore()
BtreeStack::IsEmpty()
BtreeStack::MakeEmpty()
BtreeStack::Pop()
BtreeStack::Push()
BtreeStack::RemoveHead()
BtreeStack::RemoveTail()

BtreeStack::BtreeStack() - Default class constructor.

BtreeStack::~BtreeStack() - Class destructor responsible for clearing the list when an object is deleted.

BtreeStack_t *BtreeStack::AllocNode(FAU node_address) - Private member function used to allocate a new stack node for the specified B-tree node address. Returns null if memory could not be allocated or a pointer to the stack node if no errors occur.

void BtreeStack::Clear() - Public member function uses to clear the stack.

void BtreeStack::DetachNode(BtreeStack_t *) - Private member function used to detach the specified stack node from its current location

FAU BtreeStack::Extract() - Public queue operation used to extract a B-tree node address from the list. Returns a file pointer to the B-tree node address.

FAU BtreeStack::FreeNode(BtreeStack_t *n) - Private member function used to free the memory location of the stack node. Returns a file pointer to the B-tree node address.

BtreeStack_t *BtreeStack::GetHead() - Public member function that returns the head of the list.

BtreeStack_t *BtreeStack::GetTail() - Public member function that returns the tail of the list.

BtreeStack_t *BtreeStack::Insert(FAU node_address) - Public queue operation used to insert a B-tree node address into the list. Returns a pointer to the stack node or a null value if memory for the node could not be allocated.

void BtreeStack::InsertAfter(BtreeStack_t *pos, BtreeStack_t *n) - Private member function used to insert a new or detached stack node after the node residing at the specified location.

void BtreeStack::InsertBefore(BtreeStack_t *pos, BtreeStack_t *n) - Private member function used to insert a new or detached stack node before the node residing at the specified location.

int BtreeStack::IsEmpty() - Public member function that returns true if the stack is empty.

void BtreeStack::MakeEmpty() - Private member function used to reset the "head" and "tail" pointers.

FAU BtreeStack::Pop() - Public stack operation used to pop a B-tree node address from the list. Returns a file pointer to the B-tree node address.

BtreeStack_t *BtreeStack::Push(FAU node_address) - Public stack operation used to push a B-tree node address into the list. Returns a pointer to the stack node or a null value if memory for the node could not be allocated.

FAU BtreeStack::RemoveHead() - Private member function used to remove the first stack node in the list. Returns a file pointer to the B-tree node address.

FAU BtreeStack::RemoveTail() - Private member function used to remove the last stack node in the list. Returns a file pointer to the B-tree node address.