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

graph.h

1/* *********************************************************************
2 * This Original Work is copyright of 51 Degrees Mobile Experts Limited.
3 * Copyright 2026 51 Degrees Mobile Experts Limited, Davidson House,
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
111
112
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/common.h"
122#include "../../common/data.h"
123#include "../../common/collection.h"
124#include "../../common/exceptions.h"
125
142#pragma pack(push, 4)
143typedef struct fiftyoneDegrees_graph_node_hash_t {
144 uint32_t hashCode;
145 int32_t nodeOffset;
147} fiftyoneDegreesGraphNodeHash;
148#pragma pack(pop)
149
151typedef struct fiftyoneDegrees_graph_trace_node_t fiftyoneDegreesGraphTraceNode;
153
159typedef struct fiftyoneDegrees_graph_trace_node_t {
160 uint32_t index;
163 uint32_t length;
164 uint32_t firstIndex;
165 uint32_t lastIndex;
166 uint32_t hashCode;
168 bool matched;
169 char *rootName;
172 fiftyoneDegreesGraphTraceNode* next;
174} fiftyoneDegreesGraphTraceNode;
175
179#pragma pack(push, 1)
180typedef struct fiftyoneDegrees_graph_node_t {
181 int32_t unmatchedNodeOffset;
183 byte flags;
184 int16_t firstIndex;
186 int16_t lastIndex;
188 byte length;
189 int32_t hashesCount;
190 int32_t modulo;
196} fiftyoneDegreesGraphNode;
197#pragma pack(pop)
198
208#define FIFTYONE_DEGREES_GRAPH_NODE_IS_HASH_TABLE(n) \
209 ((n)->modulo > 0 && (n)->modulo <= (n)->hashesCount)
210
211#ifndef FIFTYONE_DEGREES_MEMORY_ONLY
212
223EXTERNAL void* fiftyoneDegreesGraphNodeReadFromFile(
224 const fiftyoneDegreesCollectionFile *file,
225 const fiftyoneDegreesCollectionKey *key,
226 fiftyoneDegreesData *data,
227 fiftyoneDegreesException *exception);
228
229#endif
230
241EXTERNAL fiftyoneDegreesGraphNode* fiftyoneDegreesGraphGetNode(
242 fiftyoneDegreesCollection *collection,
243 uint32_t offset,
244 fiftyoneDegreesCollectionItem *item,
245 fiftyoneDegreesException *exception);
246
262EXTERNAL fiftyoneDegreesGraphNodeHash*
263fiftyoneDegreesGraphGetMatchingHashFromListNodeTable(
264 fiftyoneDegreesGraphNode *node,
265 uint32_t hash);
266
275EXTERNAL fiftyoneDegreesGraphNodeHash*
276fiftyoneDegreesGraphGetMatchingHashFromListNodeSearch(
277 fiftyoneDegreesGraphNode *node,
278 uint32_t hash);
279
290EXTERNAL fiftyoneDegreesGraphNodeHash*
291fiftyoneDegreesGraphGetMatchingHashFromListNode(
292 fiftyoneDegreesGraphNode *node,
293 uint32_t hash);
294
303EXTERNAL fiftyoneDegreesGraphNodeHash*
304fiftyoneDegreesGraphGetMatchingHashFromBinaryNode(
305 fiftyoneDegreesGraphNode *node,
306 uint32_t hash);
307
316EXTERNAL fiftyoneDegreesGraphNodeHash*
317fiftyoneDegreesGraphGetMatchingHashFromNode(
318 fiftyoneDegreesGraphNode *node,
319 uint32_t hash);
320
329EXTERNAL fiftyoneDegreesGraphTraceNode* fiftyoneDegreesGraphTraceCreate(
330 const char *fmt,
331 ...);
332
338EXTERNAL void fiftyoneDegreesGraphTraceFree(
339 fiftyoneDegreesGraphTraceNode *route);
340
347EXTERNAL void fiftyoneDegreesGraphTraceAppend(
348 fiftyoneDegreesGraphTraceNode *route,
349 fiftyoneDegreesGraphTraceNode *node);
350
370EXTERNAL int fiftyoneDegreesGraphTraceGet(
371 char *destination,
372 size_t length,
373 fiftyoneDegreesGraphTraceNode* route,
374 const char *source);
375
379
380#endif
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,...
fiftyoneDegreesGraphTraceFree
void fiftyoneDegreesGraphTraceFree(fiftyoneDegreesGraphTraceNode *route)
Frees a graph trace structure.
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.
fiftyoneDegreesGraphGetMatchingHashFromNode
fiftyoneDegreesGraphNodeHash * fiftyoneDegreesGraphGetMatchingHashFromNode(fiftyoneDegreesGraphNode *node, uint32_t hash)
Gets a matching hash record from a match where the node a single hash record.
fiftyoneDegreesGraphGetMatchingHashFromBinaryNode
fiftyoneDegreesGraphNodeHash * fiftyoneDegreesGraphGetMatchingHashFromBinaryNode(fiftyoneDegreesGraphNode *node, uint32_t hash)
Gets a matching hash record from a node where the node a single hash record.
fiftyoneDegreesGraphTraceAppend
void fiftyoneDegreesGraphTraceAppend(fiftyoneDegreesGraphTraceNode *route, fiftyoneDegreesGraphTraceNode *node)
Appends a node to an existing trace route.
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...
fiftyoneDegreesGraphGetMatchingHashFromListNode
fiftyoneDegreesGraphNodeHash * fiftyoneDegreesGraphGetMatchingHashFromListNode(fiftyoneDegreesGraphNode *node, uint32_t hash)
Gets a matching hash record from a node where the node has multiple hash records, using the layout in...
fiftyoneDegreesGraphNodeReadFromFile
void * fiftyoneDegreesGraphNodeReadFromFile(const fiftyoneDegreesCollectionFile *file, const fiftyoneDegreesCollectionKey *key, fiftyoneDegreesData *data, fiftyoneDegreesException *exception)
Read a graph node from the file collection provided and store in the data pointer.
fiftyoneDegreesGraphTraceCreate
fiftyoneDegreesGraphTraceNode * fiftyoneDegreesGraphTraceCreate(const char *fmt,...)
Creates a new graph trace node.
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.
fiftyoneDegreesCollectionFile
Type of collection where the collection is streamed from file.
Definition collection.h:456
fiftyoneDegreesCollection
All the shared methods and fields required by file, memory and cached collections.
Definition collection.h:408
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:315
fiftyoneDegreesCollectionKey
Explains to a collection (or cache) what the consumer is looking for.
Definition collectionKey.h:76
fiftyoneDegreesData
Data structure used for reusing memory which may have been allocated in a previous operation.
Definition data.h:105
fiftyoneDegreesException
Structure used to represent a 51Degrees exception and passed into methods that might generate excepti...
Definition exceptions.h:115
fiftyoneDegreesGraphNodeHash
Hash record structure to compare to a substring hash.
Definition graph.h:143
fiftyoneDegreesGraphNodeHash::nodeOffset
int32_t nodeOffset
Offset of the node to use if this hash code is a match.
Definition graph.h:145
fiftyoneDegreesGraphNodeHash::hashCode
uint32_t hashCode
Hash code to compare.
Definition graph.h:144
fiftyoneDegreesGraphNode
Graph node structure used to construct the directed acyclic graph to search.
Definition graph.h:180
fiftyoneDegreesGraphNode::hashesCount
int32_t hashesCount
Number of hash records in the node.
Definition graph.h:189
fiftyoneDegreesGraphNode::unmatchedNodeOffset
int32_t unmatchedNodeOffset
Offset of the node to use if there is no matching hash record.
Definition graph.h:181
fiftyoneDegreesGraphNode::modulo
int32_t modulo
Modulo to use when the hashes are a hash table.
Definition graph.h:190
fiftyoneDegreesGraphNode::lastIndex
int16_t lastIndex
Last character index to search for a matching hash code.
Definition graph.h:186
fiftyoneDegreesGraphNode::firstIndex
int16_t firstIndex
First character index to search for a matching hash code.
Definition graph.h:184
fiftyoneDegreesGraphNode::flags
byte flags
Flags available for future implementation.
Definition graph.h:183
fiftyoneDegreesGraphNode::length
byte length
Length of the substring to hash.
Definition graph.h:188
fiftyoneDegreesGraphTraceNode
Trace node structure used to trace the route taken when evaluating a graph.
Definition graph.h:159
fiftyoneDegreesGraphTraceNode::matched
bool matched
True if a matching hash was found.
Definition graph.h:168
fiftyoneDegreesGraphTraceNode::lastIndex
uint32_t lastIndex
The last index in the hash node.
Definition graph.h:165
fiftyoneDegreesGraphTraceNode::hashCode
uint32_t hashCode
The matched hash code, or zero if no matching hash was found.
Definition graph.h:166
fiftyoneDegreesGraphTraceNode::next
fiftyoneDegreesGraphTraceNode * next
Pointer to the next node in the linked list.
Definition graph.h:172
fiftyoneDegreesGraphTraceNode::rootName
char * rootName
The name title of the node.
Definition graph.h:169
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:160
fiftyoneDegreesGraphTraceNode::firstIndex
uint32_t firstIndex
The first index in the hash node.
Definition graph.h:164
fiftyoneDegreesGraphTraceNode::length
uint32_t length
The length of the hashed value being evaluated.
Definition graph.h:163

Have a data or code question? Get in touch and explore subscription options.