Detailed Description
Implementation of the classic red black binary tree.
Introduction
Implementation of a classic red black binary tree adapted to support the result set structure used in the LRU cache. Several important considerations should be noted with this implementation.
- The maximum number of entries in the tree is known when the tree is created. All memory allocation is performed at initialisation.
- Once the tree is full it will remain full and never shrinks. The memory used is freed when the cache is freed.
- A node in the tree also contains other data such as the linked list pointers used to identify the first and last entry in the cache, and the cache data itself. See structure Node.
- The cache structure Cache contains special fields "empty" and "root". "Empty" is used in place of NULL to indicate that the left, right or parent pointer of the node has no data. The use of "empty" makes the algorithm more efficient as the data structure used to indicate no data is the same as a valid data structure and therefore does not require custom logic. The "root" fields left pointer is used as the start of the tree. Similarly the parent element being a valid data structure simplifies the algorithm.
Developers modifying this section of code should be familiar with the red black tree design template. Code comments assume an understanding of the principles involved.
For further information see: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
Collaboration diagram for Tree:
Structs | |
| struct | fiftyoneDegreesTreeNode |
| Node structure defining a single node in the tree. More... | |
| struct | fiftyoneDegreesTreeRoot |
| Tree root structure defining the beginning of the tree. More... | |
Typedefs | |
| typedef void(* | fiftyoneDegreesTreeIterateMethod) (void *state, fiftyoneDegreesTreeNode *node) |
| Callback method called while iterating over a tree. | |
Functions | |
| uint32_t | fiftyoneDegreesTreeCount (fiftyoneDegreesTreeRoot *root) |
| Used by assert statements to validate the number of entries in the cache for debugging should any changes be made to the logic. | |
| void | fiftyoneDegreesTreeDelete (fiftyoneDegreesTreeNode *node) |
| Removes the node from the tree so that it can be used again to store another result. | |
| void | fiftyoneDegreesTreeInsert (fiftyoneDegreesTreeNode *node) |
| Inserts the node into the red black tree. | |
| fiftyoneDegreesTreeNode * | fiftyoneDegreesTreeFind (fiftyoneDegreesTreeRoot *root, int64_t key) |
| Returns the node that matches the key code provided. | |
| void | fiftyoneDegreesTreeNodeInit (fiftyoneDegreesTreeNode *node, fiftyoneDegreesTreeRoot *root) |
| Initialises a newly allocated node. | |
| void | fiftyoneDegreesTreeNodeRemove (fiftyoneDegreesTreeNode *node) |
| Removes a node from the tree it belongs to. | |
| void | fiftyoneDegreesTreeRootInit (fiftyoneDegreesTreeRoot *root) |
| Initialises a newly allocated tree root to a clean state. | |
| void | fiftyoneDegreesTreeIterateNodes (fiftyoneDegreesTreeRoot *root, void *state, fiftyoneDegreesTreeIterateMethod callback) |
| Iterates over all the nodes in the tree starting at the root provided, calling the callback method with each node in the tree. | |
Variables | |
| fiftyoneDegreesTreeNode * | fiftyoneDegreesTreeEmpty |
| Empty tree node. | |
Typedef Documentation
◆ fiftyoneDegreesTreeIterateMethod
| typedef void(* fiftyoneDegreesTreeIterateMethod) (void *state, fiftyoneDegreesTreeNode *node) |
Callback method called while iterating over a tree.
- Parameters
-
state pointer to any data needed by the method node at the current point in the tree
Function Documentation
◆ fiftyoneDegreesTreeCount()
| uint32_t fiftyoneDegreesTreeCount | ( | fiftyoneDegreesTreeRoot * | root | ) |
Used by assert statements to validate the number of entries in the cache for debugging should any changes be made to the logic.
Should not be compiled in release builds.
- Parameters
-
root pointer to the node being counted.
- Returns
- the number of children plus 1 for this current node.
◆ fiftyoneDegreesTreeDelete()
| void fiftyoneDegreesTreeDelete | ( | fiftyoneDegreesTreeNode * | node | ) |
Removes the node from the tree so that it can be used again to store another result.
The node will come from the last item in the cache's linked list.
- Parameters
-
node pointer to be deleted.
◆ fiftyoneDegreesTreeFind()
| fiftyoneDegreesTreeNode * fiftyoneDegreesTreeFind | ( | fiftyoneDegreesTreeRoot * | root, |
| int64_t | key ) |
Returns the node that matches the key code provided.
- Parameters
-
root of the tree to search in key to get the item for
- Returns
- the corresponding node if it exists in the tree, otherwise NULL.
◆ fiftyoneDegreesTreeInsert()
| void fiftyoneDegreesTreeInsert | ( | fiftyoneDegreesTreeNode * | node | ) |
Inserts the node into the red black tree.
- Parameters
-
node pointer to the node being inserted.
◆ fiftyoneDegreesTreeIterateNodes()
| void fiftyoneDegreesTreeIterateNodes | ( | fiftyoneDegreesTreeRoot * | root, |
| void * | state, | ||
| fiftyoneDegreesTreeIterateMethod | callback ) |
Iterates over all the nodes in the tree starting at the root provided, calling the callback method with each node in the tree.
- Parameters
-
root of the tree to iterate state pointer to pass to the callback method callback method to call with each node
◆ fiftyoneDegreesTreeNodeInit()
| void fiftyoneDegreesTreeNodeInit | ( | fiftyoneDegreesTreeNode * | node, |
| fiftyoneDegreesTreeRoot * | root ) |
Initialises a newly allocated node.
- Parameters
-
node to initialise root of the tree to which the node belongs
◆ fiftyoneDegreesTreeNodeRemove()
| void fiftyoneDegreesTreeNodeRemove | ( | fiftyoneDegreesTreeNode * | node | ) |
Removes a node from the tree it belongs to.
- Parameters
-
node to remove
◆ fiftyoneDegreesTreeRootInit()
| void fiftyoneDegreesTreeRootInit | ( | fiftyoneDegreesTreeRoot * | root | ) |
Initialises a newly allocated tree root to a clean state.
- Parameters
-
root to initialise