\r\n

51Degrees Device Detection C/C++  4.4

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

Search

Documentation

Graph

• Device Detection
• Hash API

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. When the buffer is not big enough, buffer will be written up the limit and return the number of characters which would have been written.

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. Negative value if something has gone wrong.

On This Page

• Structs
• Functions

Generated by doxygen 1.8.15