Collaboration diagram for AA-Tree:
Files | |
file | aatree.c |
Cop-out implementation of an AA-tree. | |
file | aatree.h |
Interface to an AA-tree. | |
Data Structures | |
struct | AANode_t |
The node data used to track the structure of an AA-Tree. More... | |
struct | AATreeRemovalData_t |
Used by AATreeRemove() to store data used to remove items from the tree. More... | |
Defines | |
#define | AA_ROOT_NODE (&aaTerminatorNode) |
A pointer to the initial root node; if it is the root node of a tree, then the tree is empty. | |
#define | AATreeIsEmpty(tree) ((tree) == &aaTerminatorNode) |
Evaluates to true if the given tree is empty. | |
#define | AATreeRemove(tree, key) |
Removes an item from the given tree. | |
Typedefs | |
typedef AANode_t | AANode |
typedef Uint16 | AATreeKeyLevelType |
The data type used to identify the items in the AA-Tree. | |
typedef AATreeRemovalData_t | AATreeRemovalData |
Functions | |
AANode * | _AATreeRemove (AANode *tree, AATreeRemovalData *rd) |
Implements the recursive removal algorithim; removes and deallocates the node with the given key. | |
AANode * | AATreeAdd (AANode **tree, AATreeKeyLevelType key) |
Adds a node to the indicated tree. | |
void | AATreeDestroy (AANode *tree) |
Deallocates all AANodes that comprise a tree. | |
AANode * | AATreeFind (AANode *tree, AATreeKeyLevelType key) |
Finds a node in the tree. | |
Variables | |
AANode | aaTerminatorNode |
The node used to indicate that a particular branch is empty. |
AA-Trees are simplified Red-Black trees with an easier implementation.
The implementation does not manage memory for any data being tracked by a tree. However, it does dynamically allocate and deallocate the AANode structures that make up the trees.
#define AA_ROOT_NODE (&aaTerminatorNode) |
A pointer to the initial root node; if it is the root node of a tree, then the tree is empty.
Definition at line 130 of file aatree.h.
Referenced by CancelAllMessages(), and MessageUninit().
#define AATreeIsEmpty | ( | tree | ) | ((tree) == &aaTerminatorNode) |
#define AATreeRemove | ( | tree, | |||
key | ) |
Value:
if ((tree) != &aaTerminatorNode) { \ AANode *newRoot; \ AATreeRemovalData rd = { NULL, &aaTerminatorNode, key }; \ if ((newRoot = _AATreeRemove(tree, &rd)) != NULL) tree = newRoot; \ }
This is a macro implementation that has a little code to start the removal operationn to avoid putting that code in a really small function. I just didn't feel like making that function.
tree | A pointer to the root node of a tree. This pointer will be altered to point to the new root node. | |
key | The key that identifies the item to remove from the tree. The corresponding node will be deallocated. |
Definition at line 211 of file aatree.h.
Referenced by Send().
typedef Uint16 AATreeKeyLevelType |
typedef struct AATreeRemovalData_t AATreeRemovalData |
AANode* _AATreeRemove | ( | AANode * | tree, | |
AATreeRemovalData * | rd | |||
) |
Implements the recursive removal algorithim; removes and deallocates the node with the given key.
For internal use only.
Use the AATreeRemove() macro instead of calling this function directly.
tree | A pointer to the next branch of the tree to work with. | |
rd | Removal scope data. |
Definition at line 67 of file aatree.c.
References aaTerminatorNode, Vector_t::array, copout, Vector_t::items, AATreeRemovalData_t::key, AANode_t::key, and Vector_t::VectorRemove.
AANode* AATreeAdd | ( | AANode ** | tree, | |
AATreeKeyLevelType | key | |||
) |
Adds a node to the indicated tree.
tree | A pointer to the root node of the tree that will be given the new item. This pointer will be changed to the new root node. In case of error, it will remain unchanged. | |
key | The key of the node to add. |
Definition at line 49 of file aatree.c.
References Vector_t::array, copout, AANode_t::key, Vector_t::VectorAdd(), and Vector_t::VectorInit().
Referenced by AddMessage().
Here is the call graph for this function:
void AATreeDestroy | ( | AANode * | tree | ) |
Deallocates all AANodes that comprise a tree.
tree | The root node of the tree to deallocate. The tree must not already be empty. The root node will not be valid after this function returns. |
Definition at line 89 of file aatree.c.
References copout, treeExit(), TRUE, and Vector_t::VectorClear().
Referenced by CancelAllMessages(), and MessageUninit().
Here is the call graph for this function:
AANode* AATreeFind | ( | AANode * | tree, | |
AATreeKeyLevelType | key | |||
) |
Finds a node in the tree.
tree | A pointer to the root node of the tree to search. | |
key | The key identifying the node to find. |
Definition at line 37 of file aatree.c.
References Vector_t::array, copout, Vector_t::items, and AANode_t::key.
Referenced by HandleAck(), and ServiceMessages().
The node used to indicate that a particular branch is empty.
This is used in place of NULL to simplify the code, and defined only once to avoid having multiple copies.
Definition at line 34 of file aatree.c.
Referenced by _AATreeRemove().