Detailed Description

Acyclic graph structures used in the Hash API.

Each graph node consists of:

a range of character positions which its hash values are expected to be found,
the number of characters which should be hashed,
the number of hash values contained in the node,
the modulo used to get the index of hashes in the node,
the hash values themselves,
the offset to the next node in the graph if no hashes match.

A matching hash can be found within a node using the fiftyoneDegreesGraphGetMatchingHashFromNode method. If this returns a pointer to a hash, then the node at the offset contained in the hash is used to get the next node to evaluate. If NULL is returned instead, then the node at the 'unmatched' offset should be used to get the next node to evaluate.

For example:

// Declarations (not set in this example block).

fiftyoneDegreesCollection *nodes;

fiftyoneDegreesGraphNode *node;

uint32_t hashCode;

fiftyoneDegreesGraphNodeHash *matchingHash;

fiftyoneDegreesException *exception;

fiftyoneDegreesCollectionItem item;

// Get a matching hash from the node.

matchingHash = fiftyoneDegreesGraphGetMatchingHashFromNode(node, hashCode);

if (matchingHash != NULL) {

// There was a matching hash, so go to the node it points to.

node = fiftyoneDegreesGraphGetNode(

nodes,

matchingHash->nodeOffset,

&item,

exception);

}

else {

// There was no matching hash, so go to the unmatched node.

node = fiftyoneDegreesGraphGetNode(

nodes,

node->unmatchedNodeOffset,

&item,

exception);

}

A leaf node is indicated by a negative value for the node offset (either in the unmatched node offset, or the matched hash). Instead of an explicit leaf node to terminate the graph, this negative value is used in order to save 4 bytes per node, and whole node per leaf of the graph.

Once a leaf node is reached, the offset can be negated an used to retrieve whatever type of value the graph was built to store. Usually, this is an offset or index to an element in a collection.

NOTE: By convention, a node offset of zero also indicates a leaf node. This is permitted by ensuring the first node in a collection (the only node with an offset of 0) is a root node i.e. no other nodes will point to it by its offset.

// Declaration (not set in this example).

fiftyoneDegreesHashNodeHash *hash;

if (hash->nodeOffset <= 0) {

// The offset is negative (or zero) indicating a leaf has been reached,

// so get the value.

uint32_t value = -hash->nodeOffset;

...

}

Collaboration diagram for Graph:

Structs

struct	fiftyoneDegreesGraphNodeHash Hash record structure to compare to a substring hash. More...
struct	fiftyoneDegreesGraphTraceNode Trace node structure used to trace the route taken when evaluating a graph. More...
struct	fiftyoneDegreesGraphNode Graph node structure used to construct the directed acyclic graph to search. More...

Functions

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. More...
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. More...
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. More...
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 performing a binary search. More...
fiftyoneDegreesGraphNodeHash *	fiftyoneDegreesGraphGetMatchingHashFromListNode (fiftyoneDegreesGraphNode *node, uint32_t hash) Gets a matching hash record from a node where the node has multiple hash records. More...
fiftyoneDegreesGraphNodeHash *	fiftyoneDegreesGraphGetMatchingHashFromBinaryNode (fiftyoneDegreesGraphNode *node, uint32_t hash) Gets a matching hash record from a node where the node a single hash record. More...
fiftyoneDegreesGraphNodeHash *	fiftyoneDegreesGraphGetMatchingHashFromNode (fiftyoneDegreesGraphNode *node, uint32_t hash) Gets a matching hash record from a match where the node a single hash record. More...
fiftyoneDegreesGraphTraceNode *	fiftyoneDegreesGraphTraceCreate (const char *fmt,...) Creates a new graph trace node. More...
void	fiftyoneDegreesGraphTraceFree (fiftyoneDegreesGraphTraceNode *route) Frees a graph trace structure. More...
void	fiftyoneDegreesGraphTraceAppend (fiftyoneDegreesGraphTraceNode route, fiftyoneDegreesGraphTraceNode node) Appends a node to an existing trace route. More...
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, and returns the number of characters written to the destination. More...

Function Documentation

◆ fiftyoneDegreesGraphGetMatchingHashFromBinaryNode()

fiftyoneDegreesGraphNodeHash* fiftyoneDegreesGraphGetMatchingHashFromBinaryNode	(	fiftyoneDegreesGraphNode *	node,
		uint32_t	hash
	)

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

Parameters: node - the node to search; hash - the hash code to search for

Returns: fiftyoneDegreesGraphNodeHash* data.ptr to a matching hash record, or null if none match.

◆ fiftyoneDegreesGraphGetMatchingHashFromListNode()

fiftyoneDegreesGraphNodeHash* fiftyoneDegreesGraphGetMatchingHashFromListNode	(	fiftyoneDegreesGraphNode *	node,
		uint32_t	hash
	)

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

Parameters: node - the node to search; hash - the hash code to search for

Returns: fiftyoneDegreesGraphNodeHash* data.ptr to a matching hash record, or null if none match.

◆ 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 performing a binary search.

Parameters: node - the node to search; hash - the hash code to search for

Returns: fiftyoneDegreesGraphNodeHash* data.ptr to a matching hash record, or null if none match.

◆ 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.

The value that index is set to can never be greater than the number of hashes. As such there is no need to perform a bounds check on index before using it with the array of hashes.

Parameters: node - the node to search; hash - the hash code to search for

Returns: fiftyoneDegreesGraphNodeHash* data.ptr to a matching hash record, or null if none match.

◆ fiftyoneDegreesGraphGetMatchingHashFromNode()

fiftyoneDegreesGraphNodeHash* fiftyoneDegreesGraphGetMatchingHashFromNode	(	fiftyoneDegreesGraphNode *	node,
		uint32_t	hash
	)

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

Parameters: node - the node to search; hash - the hash code to search for

Returns: fiftyoneDegreesGraphNodeHash* data.ptr to a matching hash record, or null if none match.

◆ 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.

Parameters: collection - to get the node from; offset - of the node to get; item - to store the node item in; exception - pointer to an exception data structure to be used if an exception occurs. See exceptions.h.

Returns: the node requested or NULL

◆ 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.

This method is used when creating a collection from file.

Parameters: file - collection to read from; offset - of the graph node in the collection; data - to store the resulting graph node in; exception - pointer to an exception data structure to be used if an exception occurs. See exceptions.h

Returns: pointer to the graph node allocated within the data structure

◆ fiftyoneDegreesGraphTraceAppend()

void fiftyoneDegreesGraphTraceAppend	(	fiftyoneDegreesGraphTraceNode *	route,
		fiftyoneDegreesGraphTraceNode *	node
	)

Appends a node to an existing trace route.

The new node is added to the tail of the linked list pointed to by route.

Parameters: route - the root of the trace route linked list; node - the new node to append to the trace route

◆ fiftyoneDegreesGraphTraceCreate()

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

Creates a new graph trace node.

Importantly, this is not a graph node, but a graph trace node, used to trace the route taken through a graph. The node is allocated and initialized.

Parameters: fmt - the format string to use as the name of the node; ... - arguments for the format string

Returns: a newly allocated graph trace node

◆ fiftyoneDegreesGraphTraceFree()

void fiftyoneDegreesGraphTraceFree

(

fiftyoneDegreesGraphTraceNode *

route

)

Frees a graph trace structure.

This method frees all nodes in the linked list, so should be called with the root node.

Parameters: route - root node for the trace route

◆ 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, and returns the number of characters written to the destination.

If called with NULL as the destination, and 0 as length, nothing will be written, but the number of characters which would have been written will still be returned.

Parameters: destination - pointer to the memory to write the trace string to; length - the number of characters that can be written to the destination memory; route - the highest node in the route to write the trace for. This can be the root node, or any other node along the trace; source - the source string. Usually a User-Agent to get the matched characters from

Returns: the number of characters written, or the number of characters which would have been written if length was long enough

51Degrees Device Detection C/C++ 4.2

Graph
Device Detection
Hash API

Detailed Description

Collaboration diagram for Graph:

Structs

Functions

Function Documentation

◆ fiftyoneDegreesGraphGetMatchingHashFromBinaryNode()

◆ fiftyoneDegreesGraphGetMatchingHashFromListNode()

◆ fiftyoneDegreesGraphGetMatchingHashFromListNodeSearch()

◆ fiftyoneDegreesGraphGetMatchingHashFromListNodeTable()

◆ fiftyoneDegreesGraphGetMatchingHashFromNode()

◆ fiftyoneDegreesGraphGetNode()

◆ fiftyoneDegreesGraphNodeReadFromFile()

◆ fiftyoneDegreesGraphTraceAppend()

◆ fiftyoneDegreesGraphTraceCreate()

◆ fiftyoneDegreesGraphTraceFree()

◆ fiftyoneDegreesGraphTraceGet()

On This Page

51Degrees Device Detection C/C++ 4.2

GraphDevice DetectionHash API

Detailed Description

Collaboration diagram for Graph:

Structs

Functions

Function Documentation

◆ fiftyoneDegreesGraphGetMatchingHashFromBinaryNode()

◆ fiftyoneDegreesGraphGetMatchingHashFromListNode()

◆ fiftyoneDegreesGraphGetMatchingHashFromListNodeSearch()

◆ fiftyoneDegreesGraphGetMatchingHashFromListNodeTable()

◆ fiftyoneDegreesGraphGetMatchingHashFromNode()

◆ fiftyoneDegreesGraphGetNode()

◆ fiftyoneDegreesGraphNodeReadFromFile()

◆ fiftyoneDegreesGraphTraceAppend()

◆ fiftyoneDegreesGraphTraceCreate()

◆ fiftyoneDegreesGraphTraceFree()

◆ fiftyoneDegreesGraphTraceGet()

On This Page

Graph
Device Detection
Hash API