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 the subject of the following patents and patent

7 * applications, owned by 51 Degrees Mobile Experts Limited of 5 Charlotte

8 * Close, Caversham, Reading, Berkshire, United Kingdom RG4 7BY:

9 * European Patent No. 3438848; and

10 * United States Patent No. 10,482,175.

11 *

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

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

14 *

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

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

17 *

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

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

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

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

22 *

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

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

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

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

27 * ********************************************************************* */

28

29 #ifndef FIFTYONE_DEGREES_GRAPH_INCLUDED

30 #define FIFTYONE_DEGREES_GRAPH_INCLUDED

31

113 #include <stdint.h>

114 #include <stdbool.h>

115 #ifdef _MSC_VER

116 #pragma warning(push)

117 #pragma warning(disable : 5105)

118 #include <windows.h>

119 #pragma warning(pop)

120 #endif

121 #include "../common-cxx/common.h"

122 #include "../common-cxx/data.h"

123 #include "../common-cxx/collection.h"

124 #include "../common-cxx/exceptions.h"

125

127 #pragma pack(push, 4)

128 typedef struct fiftyoneDegrees_graph_node_hash_t {

129 uint32_t hashCode;

130 int32_t nodeOffset;

132 } fiftyoneDegreesGraphNodeHash;

133 #pragma pack(pop)

134

136 typedef struct fiftyoneDegrees_graph_trace_node_t fiftyoneDegreesGraphTraceNode;

144 typedef struct fiftyoneDegrees_graph_trace_node_t {

145 uint32_t index;

148 uint32_t length;

149 uint32_t firstIndex;

150 uint32_t lastIndex;

151 uint32_t hashCode;

153 bool matched;

154 char *rootName;

157 fiftyoneDegreesGraphTraceNode* next;

159 } fiftyoneDegreesGraphTraceNode;

160

164 #pragma pack(push, 1)

165 typedef struct fiftyoneDegrees_graph_node_t {

166 int32_t unmatchedNodeOffset;

168 byte flags;

169 int16_t firstIndex;

171 int16_t lastIndex;

173 byte length;

174 int32_t hashesCount;

175 int32_t modulo;

176 } fiftyoneDegreesGraphNode;

177 #pragma pack(pop)

178

179 #ifndef FIFTYONE_DEGREES_MEMORY_ONLY

180

191 EXTERNAL void* fiftyoneDegreesGraphNodeReadFromFile(

192 const fiftyoneDegreesCollectionFile *file,

193 uint32_t offset,

194 fiftyoneDegreesData *data,

195 fiftyoneDegreesException *exception);

196

197 #endif

198

209 EXTERNAL fiftyoneDegreesGraphNode* fiftyoneDegreesGraphGetNode(

210 fiftyoneDegreesCollection *collection,

211 uint32_t offset,

212 fiftyoneDegreesCollectionItem *item,

213 fiftyoneDegreesException *exception);

214

226 EXTERNAL fiftyoneDegreesGraphNodeHash*

227 fiftyoneDegreesGraphGetMatchingHashFromListNodeTable(

228 fiftyoneDegreesGraphNode *node,

229 uint32_t hash);

230

239 EXTERNAL fiftyoneDegreesGraphNodeHash*

240 fiftyoneDegreesGraphGetMatchingHashFromListNodeSearch(

241 fiftyoneDegreesGraphNode *node,

242 uint32_t hash);

243

252 EXTERNAL fiftyoneDegreesGraphNodeHash*

253 fiftyoneDegreesGraphGetMatchingHashFromListNode(

254 fiftyoneDegreesGraphNode *node,

255 uint32_t hash);

256

265 EXTERNAL fiftyoneDegreesGraphNodeHash*

266 fiftyoneDegreesGraphGetMatchingHashFromBinaryNode(

267 fiftyoneDegreesGraphNode *node,

268 uint32_t hash);

269

278 EXTERNAL fiftyoneDegreesGraphNodeHash*

279 fiftyoneDegreesGraphGetMatchingHashFromNode(

280 fiftyoneDegreesGraphNode *node,

281 uint32_t hash);

282

291 EXTERNAL fiftyoneDegreesGraphTraceNode* fiftyoneDegreesGraphTraceCreate(

292 const char *fmt,

293 ...);

294

300 EXTERNAL void fiftyoneDegreesGraphTraceFree(

301 fiftyoneDegreesGraphTraceNode *route);

302

309 EXTERNAL void fiftyoneDegreesGraphTraceAppend(

310 fiftyoneDegreesGraphTraceNode *route,

311 fiftyoneDegreesGraphTraceNode *node);

312

332 EXTERNAL int fiftyoneDegreesGraphTraceGet(

333 char *destination,

334 size_t length,

335 fiftyoneDegreesGraphTraceNode* route,

336 const char *source);

337

342 #endif

fiftyoneDegreesGraphGetMatchingHashFromListNodeSearch

fiftyoneDegreesGraphNodeHash * fiftyoneDegreesGraphGetMatchingHashFromListNodeSearch(fiftyoneDegreesGraphNode *node, uint32_t hash)

Gets a matching hash record from a node where the hash records are stored as an ordered list by perfo...

fiftyoneDegreesGraphTraceNode::matched

bool matched

True if a matching hash was found.

Definition: graph.h:153

fiftyoneDegreesGraphTraceNode::rootName

char * rootName

The name title of the node.

Definition: graph.h:154

fiftyoneDegreesGraphTraceNode::next

fiftyoneDegreesGraphTraceNode * next

Pointer to the next node in the linked list.

Definition: graph.h:157

fiftyoneDegreesGraphTraceNode::lastIndex

uint32_t lastIndex

The last index in the hash node.

Definition: graph.h:150

fiftyoneDegreesCollectionItem

Used to store a handle to the underlying item that could be used to release the item when it's finish...

Definition: collection.h:308

fiftyoneDegreesGraphGetNode

fiftyoneDegreesGraphNode * fiftyoneDegreesGraphGetNode(fiftyoneDegreesCollection *collection, uint32_t offset, fiftyoneDegreesCollectionItem *item, fiftyoneDegreesException *exception)

Gets the graph node at the requested offset from the graph node collection provided.

fiftyoneDegreesGraphGetMatchingHashFromListNode

fiftyoneDegreesGraphNodeHash * fiftyoneDegreesGraphGetMatchingHashFromListNode(fiftyoneDegreesGraphNode *node, uint32_t hash)

Gets a matching hash record from a node where the node has multiple hash records.

fiftyoneDegreesGraphNodeHash

Hash record structure to compare to a substring hash.

Definition: graph.h:128

fiftyoneDegreesGraphNode::lastIndex

int16_t lastIndex

Last character index to search for a matching hash code.

Definition: graph.h:171

fiftyoneDegreesCollectionFile

Type of collection where the collection is streamed from file.

Definition: collection.h:445

fiftyoneDegreesGraphTraceNode::length

uint32_t length

The length of the hashed value being evaluated.

Definition: graph.h:148

fiftyoneDegreesGraphNodeReadFromFile

void * fiftyoneDegreesGraphNodeReadFromFile(const fiftyoneDegreesCollectionFile *file, uint32_t offset, fiftyoneDegreesData *data, fiftyoneDegreesException *exception)

Read a graph node from the file collection provided and store in the data pointer.

fiftyoneDegreesGraphNode::flags

byte flags

Flags available for future implementation.

Definition: graph.h:168

fiftyoneDegreesData

Data structure used for reusing memory which may have been allocated in a previous operation.

Definition: data.h:101

fiftyoneDegreesGraphNode::hashesCount

int32_t hashesCount

Number of hash records in the node.

Definition: graph.h:174

fiftyoneDegreesGraphTraceFree

void fiftyoneDegreesGraphTraceFree(fiftyoneDegreesGraphTraceNode *route)

Frees a graph trace structure.

fiftyoneDegreesGraphNode::length

byte length

Length of the substring to hash.

Definition: graph.h:173

fiftyoneDegreesGraphGetMatchingHashFromNode

fiftyoneDegreesGraphNodeHash * fiftyoneDegreesGraphGetMatchingHashFromNode(fiftyoneDegreesGraphNode *node, uint32_t hash)

Gets a matching hash record from a match where the node a single hash record.

fiftyoneDegreesGraphNodeHash::hashCode

uint32_t hashCode

Hash code to compare.

Definition: graph.h:129

fiftyoneDegreesGraphTraceNode::hashCode

uint32_t hashCode

The matched hash code, or zero if no matching hash was found.

Definition: graph.h:151

fiftyoneDegreesGraphNodeHash::nodeOffset

int32_t nodeOffset

Offset of the node to use if this hash code is a match.

Definition: graph.h:130

fiftyoneDegreesGraphTraceCreate

fiftyoneDegreesGraphTraceNode * fiftyoneDegreesGraphTraceCreate(const char *fmt,...)

Creates a new graph trace node.

fiftyoneDegreesGraphTraceNode::index

uint32_t index

The index in the evidence where the hash was found, or the last index which was evaluated if no match...

Definition: graph.h:145

fiftyoneDegreesGraphTraceGet

int fiftyoneDegreesGraphTraceGet(char *destination, size_t length, fiftyoneDegreesGraphTraceNode *route, const char *source)

Writes a trace route in a readable format to a destination will the memory allocated,...

fiftyoneDegreesGraphNode::firstIndex

int16_t firstIndex

First character index to search for a matching hash code.

Definition: graph.h:169

fiftyoneDegreesException

Structure used to represent a 51Degrees exception and passed into methods that might generate excepti...

Definition: exceptions.h:111

fiftyoneDegreesGraphNode::modulo

int32_t modulo

Modulo to use when the hashes are a hash table.

Definition: graph.h:175

fiftyoneDegreesGraphTraceNode

Trace node structure used to trace the route taken when evaluating a graph.

Definition: graph.h:144

fiftyoneDegreesGraphTraceAppend

void fiftyoneDegreesGraphTraceAppend(fiftyoneDegreesGraphTraceNode *route, fiftyoneDegreesGraphTraceNode *node)

Appends a node to an existing trace route.

fiftyoneDegreesGraphNode

Graph node structure used to construct the directed acyclic graph to search.

Definition: graph.h:165

fiftyoneDegreesGraphGetMatchingHashFromListNodeTable

fiftyoneDegreesGraphNodeHash * fiftyoneDegreesGraphGetMatchingHashFromListNodeTable(fiftyoneDegreesGraphNode *node, uint32_t hash)

Gets a matching hash record from a node where the hash records are structured as a hash table.

fiftyoneDegreesCollection

All the shared methods and fields required by file, memory and cached collections.

Definition: collection.h:408

fiftyoneDegreesGraphGetMatchingHashFromBinaryNode

fiftyoneDegreesGraphNodeHash * fiftyoneDegreesGraphGetMatchingHashFromBinaryNode(fiftyoneDegreesGraphNode *node, uint32_t hash)

Gets a matching hash record from a node where the node a single hash record.

fiftyoneDegreesGraphNode::unmatchedNodeOffset

int32_t unmatchedNodeOffset

Offset of the node to use if there is no matching hash record.

Definition: graph.h:166

fiftyoneDegreesGraphTraceNode::firstIndex

uint32_t firstIndex

The first index in the hash node.

Definition: graph.h:149

51Degrees Device Detection C/C++ 4.4

graph.h