1/* *********************************************************************

2 * This Original Work is copyright of 51 Degrees Mobile Experts Limited.

4 * Forbury Square, Reading, Berkshire, United Kingdom RG1 3EU.

5 *

6 * This Original Work is licensed under the European Union Public Licence

7 * (EUPL) v.1.2 and is subject to its terms as set out below.

8 *

9 * If a copy of the EUPL was not distributed with this file, You can obtain

10 * one at https://opensource.org/licenses/EUPL-1.2.

11 *

12 * The 'Compatible Licences' set out in the Appendix to the EUPL (as may be

13 * amended by the European Commission) shall be deemed incompatible for

14 * the purposes of the Work and the provisions of the compatibility

15 * clause in Article 5 of the EUPL shall not apply.

16 *

17 * If using the Work as, or as part of, a network application, by

18 * including the attribution notice(s) required under Article 5 of the EUPL

19 * in the end user terms of the application under an appropriate heading,

20 * such notice(s) shall fulfill the requirements of that article.

21 * ********************************************************************* */

22

23#ifndef FIFTYONE_DEGREES_TREE_INCLUDED

24#define FIFTYONE_DEGREES_TREE_INCLUDED

25

26#ifdef FIFTYONE_DEGREES_IPI_SYMBOLS

27#include "ipiSymbols.h"

28#endif

29

30

68

69#include <stdlib.h>

70#include <stdint.h>

71#include <assert.h>

72

73#include "data.h"

74

76typedef struct fiftyone_degrees_tree_node_t fiftyoneDegreesTreeNode;

77typedef struct fiftyone_degrees_tree_root_t fiftyoneDegreesTreeRoot;

79

81typedef struct fiftyone_degrees_tree_node_t {

82 int64_t key;

83 fiftyoneDegreesTreeRoot *root;

84 fiftyoneDegreesTreeNode *parent;

85 fiftyoneDegreesTreeNode *left;

86 fiftyoneDegreesTreeNode *right;

87 unsigned char colour;

88} fiftyoneDegreesTreeNode;

89

91typedef struct fiftyone_degrees_tree_root_t {

92 fiftyoneDegreesTreeNode root;

93 fiftyoneDegreesTreeNode empty;

94} fiftyoneDegreesTreeRoot;

95

101typedef void(*fiftyoneDegreesTreeIterateMethod)(

102 void* state,

103 fiftyoneDegreesTreeNode* node);

104

108extern fiftyoneDegreesTreeNode *fiftyoneDegreesTreeEmpty;

109

117uint32_t fiftyoneDegreesTreeCount(fiftyoneDegreesTreeRoot *root);

118

125void fiftyoneDegreesTreeDelete(fiftyoneDegreesTreeNode *node);

126

131void fiftyoneDegreesTreeInsert(fiftyoneDegreesTreeNode *node);

132

139fiftyoneDegreesTreeNode* fiftyoneDegreesTreeFind(

140 fiftyoneDegreesTreeRoot *root,

141 int64_t key);

142

148void fiftyoneDegreesTreeNodeInit(

149 fiftyoneDegreesTreeNode *node,

150 fiftyoneDegreesTreeRoot *root);

151

156void fiftyoneDegreesTreeNodeRemove(fiftyoneDegreesTreeNode *node);

157

162void fiftyoneDegreesTreeRootInit(fiftyoneDegreesTreeRoot *root);

163

171void fiftyoneDegreesTreeIterateNodes(

172 fiftyoneDegreesTreeRoot *root,

173 void *state,

174 fiftyoneDegreesTreeIterateMethod callback);

175

179

180#endif

fiftyoneDegreesTreeRootInit

void fiftyoneDegreesTreeRootInit(fiftyoneDegreesTreeRoot *root)

Initialises a newly allocated tree root to a clean state.

fiftyoneDegreesTreeIterateMethod

void(* fiftyoneDegreesTreeIterateMethod)(void *state, fiftyoneDegreesTreeNode *node)

Callback method called while iterating over a tree.

Definition tree.h:101

fiftyoneDegreesTreeNodeRemove

void fiftyoneDegreesTreeNodeRemove(fiftyoneDegreesTreeNode *node)

Removes a node from the tree it belongs to.

fiftyoneDegreesTreeInsert

void fiftyoneDegreesTreeInsert(fiftyoneDegreesTreeNode *node)

Inserts the node into the red black tree.

fiftyoneDegreesTreeCount

uint32_t fiftyoneDegreesTreeCount(fiftyoneDegreesTreeRoot *root)

Used by assert statements to validate the number of entries in the cache for debugging should any cha...

fiftyoneDegreesTreeFind

fiftyoneDegreesTreeNode * fiftyoneDegreesTreeFind(fiftyoneDegreesTreeRoot *root, int64_t key)

Returns the node that matches the key code provided.

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 wi...

fiftyoneDegreesTreeDelete

void fiftyoneDegreesTreeDelete(fiftyoneDegreesTreeNode *node)

Removes the node from the tree so that it can be used again to store another result.

fiftyoneDegreesTreeNodeInit

void fiftyoneDegreesTreeNodeInit(fiftyoneDegreesTreeNode *node, fiftyoneDegreesTreeRoot *root)

Initialises a newly allocated node.

fiftyoneDegreesTreeNode

Node structure defining a single node in the tree.

Definition tree.h:81

fiftyoneDegreesTreeNode::colour

unsigned char colour

The colour of the node in the red black tree.

Definition tree.h:87

fiftyoneDegreesTreeNode::left

fiftyoneDegreesTreeNode * left

Left node or NULL if none.

Definition tree.h:85

fiftyoneDegreesTreeNode::parent

fiftyoneDegreesTreeNode * parent

Parent node or NULL if root.

Definition tree.h:84

fiftyoneDegreesTreeNode::right

fiftyoneDegreesTreeNode * right

Right node or NULL if none.

Definition tree.h:86

fiftyoneDegreesTreeNode::key

int64_t key

Numeric key associated with the data value.

Definition tree.h:82

fiftyoneDegreesTreeNode::root

fiftyoneDegreesTreeRoot * root

The current root node of the tree.

Definition tree.h:83

fiftyoneDegreesTreeRoot

Tree root structure defining the beginning of the tree.

Definition tree.h:91

fiftyoneDegreesTreeRoot::empty

fiftyoneDegreesTreeNode empty

Empty tree node.

Definition tree.h:93

fiftyoneDegreesTreeRoot::root

fiftyoneDegreesTreeNode root

The current root node of the tree.

Definition tree.h:92