51Degrees Device Detection C/C++  4.1

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

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).
uint32_t hashCode;
// 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.
nodes,
matchingHash->nodeOffset,
&item,
exception);
}
else {
// There was no matching hash, so go to the unmatched node.
nodes,
&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
On This Page