51Degrees Common C/C++  4.1

A shared functionality library that is used by 51Degrees products
Search

tree.h

1 /* *********************************************************************
2  * This Source Code Form is copyright of 51 Degrees Mobile Experts Limited.
3  * Copyright 2019 51 Degrees Mobile Experts Limited, 5 Charlotte Close,
4  * Caversham, Reading, Berkshire, United Kingdom RG4 7BY
5  *
6  * This Source Code Form is subject to the terms of the Mozilla Public
7  * License, v. 2.0.
8  *
9  * If a copy of the MPL was not distributed with this file, You can obtain
10  * one at http://mozilla.org/MPL/2.0/.
11  *
12  * This Source Code Form is "Incompatible With Secondary Licenses", as
13  * defined by the Mozilla Public License, v. 2.0.
14  * ********************************************************************* */
15 
16 #ifndef FIFTYONE_DEGREES_TREE_INCLUDED
17 #define FIFTYONE_DEGREES_TREE_INCLUDED
18 
19 
58 #include <stdlib.h>
59 #include <stdint.h>
60 #include <assert.h>
61 
62 #include "data.h"
63 
65 typedef struct fiftyone_degrees_tree_node_t fiftyoneDegreesTreeNode;
66 typedef struct fiftyone_degrees_tree_root_t fiftyoneDegreesTreeRoot;
70 typedef struct fiftyone_degrees_tree_node_t {
71  int64_t key;
72  fiftyoneDegreesTreeRoot *root;
73  fiftyoneDegreesTreeNode *parent;
74  fiftyoneDegreesTreeNode *left;
75  fiftyoneDegreesTreeNode *right;
76  unsigned char colour;
77 } fiftyoneDegreesTreeNode;
78 
80 typedef struct fiftyone_degrees_tree_root_t {
81  fiftyoneDegreesTreeNode root;
82  fiftyoneDegreesTreeNode empty;
83 } fiftyoneDegreesTreeRoot;
84 
90 typedef void(*fiftyoneDegreesTreeIterateMethod)(
91  void* state,
92  fiftyoneDegreesTreeNode* node);
93 
97 extern fiftyoneDegreesTreeNode *fiftyoneDegreesTreeEmpty;
98 
106 uint32_t fiftyoneDegreesTreeCount(fiftyoneDegreesTreeRoot *root);
107 
114 void fiftyoneDegreesTreeDelete(fiftyoneDegreesTreeNode *node);
115 
120 void fiftyoneDegreesTreeInsert(fiftyoneDegreesTreeNode *node);
121 
128 fiftyoneDegreesTreeNode* fiftyoneDegreesTreeFind(
129  fiftyoneDegreesTreeRoot *root,
130  int64_t key);
131 
137 void fiftyoneDegreesTreeNodeInit(
138  fiftyoneDegreesTreeNode *node,
139  fiftyoneDegreesTreeRoot *root);
140 
145 void fiftyoneDegreesTreeNodeRemove(fiftyoneDegreesTreeNode *node);
146 
151 void fiftyoneDegreesTreeRootInit(fiftyoneDegreesTreeRoot *root);
152 
160 void fiftyoneDegreesTreeIterateNodes(
161  fiftyoneDegreesTreeRoot *root,
162  void *state,
163  fiftyoneDegreesTreeIterateMethod callback);
164 
169 #endif
fiftyoneDegreesTreeCount
uint32_t fiftyoneDegreesTreeCount(fiftyoneDegreesTreeRoot *root)
Used by assert statements to validate the number of entries in the cache for debugging should any cha...
Definition: tree.c:381
fiftyoneDegreesTreeEmpty
fiftyoneDegreesTreeNode * fiftyoneDegreesTreeEmpty
Empty tree node.
fiftyoneDegreesTreeFind
fiftyoneDegreesTreeNode * fiftyoneDegreesTreeFind(fiftyoneDegreesTreeRoot *root, int64_t key)
Returns the node that matches the key code provided.
Definition: tree.c:252
fiftyoneDegreesTreeRootInit
void fiftyoneDegreesTreeRootInit(fiftyoneDegreesTreeRoot *root)
Initialises a newly allocated tree root to a clean state.
Definition: tree.c:351
fiftyoneDegreesTreeNode::root
fiftyoneDegreesTreeRoot * root
The current root node of the tree.
Definition: tree.h:72
fiftyoneDegreesTreeRoot
Tree root structure defining the beginning of the tree.
Definition: tree.h:80
fiftyoneDegreesTreeNode::right
fiftyoneDegreesTreeNode * right
Right node or NULL if none.
Definition: tree.h:75
fiftyoneDegreesTreeNodeRemove
void fiftyoneDegreesTreeNodeRemove(fiftyoneDegreesTreeNode *node)
Removes a node from the tree it belongs to.
Definition: tree.c:344
fiftyoneDegreesTreeNode
Node structure defining a single node in the tree.
Definition: tree.h:70
fiftyoneDegreesTreeNodeInit
void fiftyoneDegreesTreeNodeInit(fiftyoneDegreesTreeNode *node, fiftyoneDegreesTreeRoot *root)
Initialises a newly allocated node.
Definition: tree.c:366
fiftyoneDegreesTreeRoot::root
fiftyoneDegreesTreeNode root
The current root node of the tree.
Definition: tree.h:81
fiftyoneDegreesTreeIterateMethod
void(* fiftyoneDegreesTreeIterateMethod)(void *state, fiftyoneDegreesTreeNode *node)
Callback method called while iterating over a tree.
Definition: tree.h:90
fiftyoneDegreesTreeNode::parent
fiftyoneDegreesTreeNode * parent
Parent node or NULL if root.
Definition: tree.h:73
fiftyoneDegreesTreeRoot::empty
fiftyoneDegreesTreeNode empty
Empty tree node.
Definition: tree.h:82
fiftyoneDegreesTreeNode::key
int64_t key
Numeric key associated with the data value.
Definition: tree.h:71
fiftyoneDegreesTreeInsert
void fiftyoneDegreesTreeInsert(fiftyoneDegreesTreeNode *node)
Inserts the node into the red black tree.
Definition: tree.c:269
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...
Definition: tree.c:374
fiftyoneDegreesTreeNode::colour
unsigned char colour
The colour of the node in the red black tree.
Definition: tree.h:76
fiftyoneDegreesTreeNode::left
fiftyoneDegreesTreeNode * left
Left node or NULL if none.
Definition: tree.h:74
fiftyoneDegreesTreeDelete
void fiftyoneDegreesTreeDelete(fiftyoneDegreesTreeNode *node)
Removes the node from the tree so that it can be used again to store another result.
Definition: tree.c:300

Generated by doxygen 1.8.15