51Degrees Device Detection C/C++  4.2

A device detection library that is used natively or by 51Degrees products

Tree

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.

  1. The maximum number of entries in the tree is known when the tree is created. All memory allocation is performed at initialisation.
  2. Once the tree is full it will remain full and never shrinks. The memory used is freed when the cache is freed.
  3. 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.
  4. 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. More...

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. More...
void  fiftyoneDegreesTreeDelete (fiftyoneDegreesTreeNode *node)
Removes the node from the tree so that it can be used again to store another result. More...
void  fiftyoneDegreesTreeInsert (fiftyoneDegreesTreeNode *node)
Inserts the node into the red black tree. More...
fiftyoneDegreesTreeNode *  fiftyoneDegreesTreeFind (fiftyoneDegreesTreeRoot *root, int64_t key)
Returns the node that matches the key code provided. More...
void  fiftyoneDegreesTreeNodeInit (fiftyoneDegreesTreeNode *node, fiftyoneDegreesTreeRoot *root)
Initialises a newly allocated node. More...
void  fiftyoneDegreesTreeNodeRemove (fiftyoneDegreesTreeNode *node)
Removes a node from the tree it belongs to. More...
void  fiftyoneDegreesTreeRootInit (fiftyoneDegreesTreeRoot *root)
Initialises a newly allocated tree root to a clean state. More...
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. More...

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
On This Page

Generated by doxygen 1.8.15