\r\n

51Degrees Device Detection C/C++  4.4

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 2023 51 Degrees Mobile Experts Limited, Davidson House,
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 
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;
79  fiftyoneDegreesTreeRoot *root;
80  fiftyoneDegreesTreeNode *parent;
81  fiftyoneDegreesTreeNode *left;
82  fiftyoneDegreesTreeNode *right;
83  unsigned char colour;
84 } fiftyoneDegreesTreeNode;
85 
87 typedef struct fiftyone_degrees_tree_root_t {
88  fiftyoneDegreesTreeNode root;
89  fiftyoneDegreesTreeNode empty;
90 } fiftyoneDegreesTreeRoot;
91 
97 typedef void(*fiftyoneDegreesTreeIterateMethod)(
98  void* state,
99  fiftyoneDegreesTreeNode* node);
100 
104 extern fiftyoneDegreesTreeNode *fiftyoneDegreesTreeEmpty;
105 
113 uint32_t fiftyoneDegreesTreeCount(fiftyoneDegreesTreeRoot *root);
114 
121 void fiftyoneDegreesTreeDelete(fiftyoneDegreesTreeNode *node);
122 
127 void fiftyoneDegreesTreeInsert(fiftyoneDegreesTreeNode *node);
128 
135 fiftyoneDegreesTreeNode* fiftyoneDegreesTreeFind(
136  fiftyoneDegreesTreeRoot *root,
137  int64_t key);
138 
144 void fiftyoneDegreesTreeNodeInit(
145  fiftyoneDegreesTreeNode *node,
146  fiftyoneDegreesTreeRoot *root);
147 
152 void fiftyoneDegreesTreeNodeRemove(fiftyoneDegreesTreeNode *node);
153 
158 void fiftyoneDegreesTreeRootInit(fiftyoneDegreesTreeRoot *root);
159 
167 void fiftyoneDegreesTreeIterateNodes(
168  fiftyoneDegreesTreeRoot *root,
169  void *state,
170  fiftyoneDegreesTreeIterateMethod callback);
171 
176 #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...
fiftyoneDegreesTreeEmpty
fiftyoneDegreesTreeNode * fiftyoneDegreesTreeEmpty
Empty tree node.
fiftyoneDegreesTreeFind
fiftyoneDegreesTreeNode * fiftyoneDegreesTreeFind(fiftyoneDegreesTreeRoot *root, int64_t key)
Returns the node that matches the key code provided.
fiftyoneDegreesTreeRootInit
void fiftyoneDegreesTreeRootInit(fiftyoneDegreesTreeRoot *root)
Initialises a newly allocated tree root to a clean state.
fiftyoneDegreesTreeNode::root
fiftyoneDegreesTreeRoot * root
The current root node of the tree.
Definition: tree.h:79
fiftyoneDegreesTreeRoot
Tree root structure defining the beginning of the tree.
Definition: tree.h:87
fiftyoneDegreesTreeNode::right
fiftyoneDegreesTreeNode * right
Right node or NULL if none.
Definition: tree.h:82
fiftyoneDegreesTreeNodeRemove
void fiftyoneDegreesTreeNodeRemove(fiftyoneDegreesTreeNode *node)
Removes a node from the tree it belongs to.
fiftyoneDegreesTreeNode
Node structure defining a single node in the tree.
Definition: tree.h:77
fiftyoneDegreesTreeNodeInit
void fiftyoneDegreesTreeNodeInit(fiftyoneDegreesTreeNode *node, fiftyoneDegreesTreeRoot *root)
Initialises a newly allocated node.
fiftyoneDegreesTreeRoot::root
fiftyoneDegreesTreeNode root
The current root node of the tree.
Definition: tree.h:88
fiftyoneDegreesTreeIterateMethod
void(* fiftyoneDegreesTreeIterateMethod)(void *state, fiftyoneDegreesTreeNode *node)
Callback method called while iterating over a tree.
Definition: tree.h:97
fiftyoneDegreesTreeNode::parent
fiftyoneDegreesTreeNode * parent
Parent node or NULL if root.
Definition: tree.h:80
fiftyoneDegreesTreeRoot::empty
fiftyoneDegreesTreeNode empty
Empty tree node.
Definition: tree.h:89
fiftyoneDegreesTreeNode::key
int64_t key
Numeric key associated with the data value.
Definition: tree.h:78
fiftyoneDegreesTreeInsert
void fiftyoneDegreesTreeInsert(fiftyoneDegreesTreeNode *node)
Inserts the node into the red black tree.
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...
fiftyoneDegreesTreeNode::colour
unsigned char colour
The colour of the node in the red black tree.
Definition: tree.h:83
fiftyoneDegreesTreeNode::left
fiftyoneDegreesTreeNode * left
Left node or NULL if none.
Definition: tree.h:81
fiftyoneDegreesTreeDelete
void fiftyoneDegreesTreeDelete(fiftyoneDegreesTreeNode *node)
Removes the node from the tree so that it can be used again to store another result.

Generated by doxygen 1.8.15