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);

}

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.

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

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

fiftyoneDegreesGraphNode

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

Definition graph.h:180

fiftyoneDegreesGraphNode::unmatchedNodeOffset

int32_t unmatchedNodeOffset

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

Definition graph.h:181

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

Macros
#define	FIFTYONE_DEGREES_GRAPH_NODE_IS_HASH_TABLE(n)
	Determines whether the hash records of a node are laid out as a usable hash table, i.e.

Functions
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.
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.
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.
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.
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 indicated by the modulo of the node.
fiftyoneDegreesGraphNodeHash *	fiftyoneDegreesGraphGetMatchingHashFromBinaryNode (fiftyoneDegreesGraphNode *node, uint32_t hash)
	Gets a matching hash record from a node where the node a single hash record.
fiftyoneDegreesGraphNodeHash *	fiftyoneDegreesGraphGetMatchingHashFromNode (fiftyoneDegreesGraphNode *node, uint32_t hash)
	Gets a matching hash record from a match where the node a single hash record.
fiftyoneDegreesGraphTraceNode *	fiftyoneDegreesGraphTraceCreate (const char *fmt,...)
	Creates a new graph trace node.
void	fiftyoneDegreesGraphTraceFree (fiftyoneDegreesGraphTraceNode *route)
	Frees a graph trace structure.
void	fiftyoneDegreesGraphTraceAppend (fiftyoneDegreesGraphTraceNode route, fiftyoneDegreesGraphTraceNode node)
	Appends a node to an existing trace route.
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.

Macro Definition Documentation

◆ FIFTYONE_DEGREES_GRAPH_NODE_IS_HASH_TABLE

#define FIFTYONE_DEGREES_GRAPH_NODE_IS_HASH_TABLE

(

n

)

Value:

((n)->modulo > 0 && (n)->modulo <= (n)->hashesCount)

Determines whether the hash records of a node are laid out as a usable hash table, i.e.

the modulo is positive and cannot produce an index beyond the end of the records. Nodes which are neither a hash table nor an ordered list (modulo of zero) hold values which cannot be evaluated safely, and are treated as containing no matching hash.

Parameters

n	pointer to the fiftyoneDegreesGraphNode to test

Returns: true if (hash % modulo) indexes a record of the node

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, using the layout indicated by the modulo of the node.

Nodes which are neither a hash table nor an ordered list hold values which cannot be evaluated safely, and are treated as containing no matching hash.

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 node must be a usable hash table, i.e. FIFTYONE_DEGREES_GRAPH_NODE_IS_HASH_TABLE must be true for it. This guarantees that the index the hash is reduced to can never be greater than the number of hashes, so there is no need to perform a bounds check on the index before using it with the array of hashes. A hash of zero never matches, as a hash code of zero is reserved as a marker in this layout. See fiftyoneDegreesGraphNodeHash.

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,
		const fiftyoneDegreesCollectionKey *	key,
		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
key	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.

Graph Device DetectionHash API

Detailed Description

Collaboration diagram for Graph:

Structs

Macros

Functions

Macro Definition Documentation

◆ FIFTYONE_DEGREES_GRAPH_NODE_IS_HASH_TABLE

Function Documentation

◆ fiftyoneDegreesGraphGetMatchingHashFromBinaryNode()

◆ fiftyoneDegreesGraphGetMatchingHashFromListNode()

◆ fiftyoneDegreesGraphGetMatchingHashFromListNodeSearch()

◆ fiftyoneDegreesGraphGetMatchingHashFromListNodeTable()

◆ fiftyoneDegreesGraphGetMatchingHashFromNode()

◆ fiftyoneDegreesGraphGetNode()

◆ fiftyoneDegreesGraphNodeReadFromFile()

◆ fiftyoneDegreesGraphTraceAppend()

◆ fiftyoneDegreesGraphTraceCreate()

◆ fiftyoneDegreesGraphTraceFree()

◆ fiftyoneDegreesGraphTraceGet()

Graph
Device Detection
Hash API