51Degrees Device Detection C/C++  4.1

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

tree.h

1 /* *********************************************************************
2  * This Original Work 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 Original Work is licensed under the European Union Public Licence (EUPL)
7  * 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 
65 #include <stdlib.h>
66 #include <stdint.h>
67 #include <assert.h>
68 
69 #include "data.h"
70 
72 typedef struct fiftyone_degrees_tree_node_t fiftyoneDegreesTreeNode;
73 typedef struct fiftyone_degrees_tree_root_t fiftyoneDegreesTreeRoot;
77 typedef struct fiftyone_degrees_tree_node_t {
78  int64_t key;
83  unsigned char colour;
85 
87 typedef struct fiftyone_degrees_tree_root_t {
91 
98  void* state,
100 
105 
114 
122 
128 
137  int64_t key);
138 
147 
153 
159 
169  void *state,
171 
176 #endif
uint32_t fiftyoneDegreesTreeCount(fiftyoneDegreesTreeRoot *root)
Used by assert statements to validate the number of entries in the cache for debugging should any cha...
fiftyoneDegreesTreeNode * fiftyoneDegreesTreeEmpty
Empty tree node.
fiftyoneDegreesTreeNode * fiftyoneDegreesTreeFind(fiftyoneDegreesTreeRoot *root, int64_t key)
Returns the node that matches the key code provided.
void fiftyoneDegreesTreeRootInit(fiftyoneDegreesTreeRoot *root)
Initialises a newly allocated tree root to a clean state.
fiftyoneDegreesTreeRoot * root
The current root node of the tree.
Definition: tree.h:79
Tree root structure defining the beginning of the tree.
Definition: tree.h:87
fiftyoneDegreesTreeNode * right
Right node or NULL if none.
Definition: tree.h:82
void fiftyoneDegreesTreeNodeRemove(fiftyoneDegreesTreeNode *node)
Removes a node from the tree it belongs to.
Node structure defining a single node in the tree.
Definition: tree.h:77
void fiftyoneDegreesTreeNodeInit(fiftyoneDegreesTreeNode *node, fiftyoneDegreesTreeRoot *root)
Initialises a newly allocated node.
fiftyoneDegreesTreeNode root
The current root node of the tree.
Definition: tree.h:88
void(* fiftyoneDegreesTreeIterateMethod)(void *state, fiftyoneDegreesTreeNode *node)
Callback method called while iterating over a tree.
Definition: tree.h:97
fiftyoneDegreesTreeNode * parent
Parent node or NULL if root.
Definition: tree.h:80
fiftyoneDegreesTreeNode empty
Empty tree node.
Definition: tree.h:89
int64_t key
Numeric key associated with the data value.
Definition: tree.h:78
void fiftyoneDegreesTreeInsert(fiftyoneDegreesTreeNode *node)
Inserts the node into the red black tree.
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...
unsigned char colour
The colour of the node in the red black tree.
Definition: tree.h:83
fiftyoneDegreesTreeNode * left
Left node or NULL if none.
Definition: tree.h:81
void fiftyoneDegreesTreeDelete(fiftyoneDegreesTreeNode *node)
Removes the node from the tree so that it can be used again to store another result.