\r\n

51Degrees Device Detection C/C++  4.4

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

Collection

Detailed Description

Group of related items such as strings.

Terms

Collection : a group of items that share a common data structure.

Item : an immutable entity within the collection. The number of bytes used to store the item may be either fixed or variable.

Get : returns an immutable Item that must be released when the caller is finished with it.

Release : releases a lock on the Item returned from the Get operation.

Index : where the Item data uses a fixed number of bytes the index of the item in the Collection.

Offset : where items do not share the same number of data bytes the 0 based offset to the Item from the start of the collection’s data (after any header).

Introduction

A Collection is a group of related Items such as strings or properties where the consumer wishes to access the items without concern for the underlying storage mechanism and memory management. Immutable items can be retrieved (Get) from the collection which MUST be released once the caller has finished with the data.

In some configurations it may be more efficient to load all related Items into memory in a continuous address space exactly matching the data structure used in the source data. In others it may be desirable to only load in memory the Items from the source data when required. In all configurations the logical methods to retrieve and release these items are identical.

The methods in the Collection abstract the implementation for collection of items to support the following configurations:

Memory : all the Items in the Collection are held in a continuous address space. The fastest access option where all memory can be allocated during initialisation.

File : none of the Items are loaded into memory and they are retrieved from the data source when required. The slowest access option but the most memory efficient. The memory needed to store the item is allocated when the Item is requested and deallocated when released.

Cache : a hybrid mode where the Least Recently Used (LRU) cache is used to store a limited number of Items in memory. Cache is a compromise between in memory and file based configurations. Unlike Memory and File the cache needs to be locked when accessed for both Get and Release and performance may degrade when used in a multi threaded configuration.

Sometimes it may be desirable to use multiple configurations of Collection with the same underlying data. Consider a data structure where the most frequently required Items exist at the start of the structure. These Items would benefit from being held in memory for fast retrieval whilst the remaining Items which may be infrequently required are cached or loaded when needed from the file. For these situations Collections can be chained together such that the first Collection may not contain data for the requested index or offset and can pass the retrieval to the next Collection in the chain. It is important to note that all chained Collections must be a subset of the final Collection in the chain (as opposed to additional Collections), i.e. all elements are 'gettable' from the final Collection.

Once a Collection is created the only methods that should be used to access data are those exposed in the fiftyoneDegreesCollection instance. It is for this reason the collection.h file exposes so few external methods.

Creation

There are two Collection creation methods:

fiftyoneDegreesCollectionCreateFromMemory

Creates a Collection that is created to access memory that is already allocated in continuous memory simply maps to this memory and provides relatively simple methods to retrieve Items. No reference to the underlying data file or source is required but the memory must already be allocated.

fiftyoneDegreesCollectionCreateFromFile

A Collection mapped to a data file is more complex than the memory method and a greater set of creation configuration features are required. For example; caching options or how many Items at the start of the Collection to store in memory.

A fiftyoneDegreesCollectionConfig structure is used to configure the operation of the resulting Collection. This structure has the following fields.

loaded : the number of Items to load into memory from the start of the Collection’s data structure.

capacity : 0 if a cache should not be used, otherwise the capacity of cache.

concurrency : the expected number of concurrent operations, 1 or greater.

The file create method will work out the different types of Collection(s) needed and how to chain them based on the configuration provided.

Additionally, a pointer to a method to read an Item into the Collection from the underlying data file is required. For fixed width Collections the fiftyoneDegreesCollectionReadFileFixed can be used where the Item key is the zero based index in the Collection. For variable byte width Collections the consumer will need to provide a method that implements fiftyoneDegreesCollectionFileRead.

All creation methods return a pointer to an instance of fiftyoneDegreesCollection. Following creation only the methods exposed by this Collection should be used to retrieve and release Items.

Free

The freeCollection method of the Collection must be called when the Collection is finished with. After this method is called the Collection data structure and all owned data will be released.

Get & Release

All operations that retrieve data from the Collection require an instance of fiftyoneDegreesCollectionItem to be passed. Items can be reused across multiple Get and Release operations to reduce the frequency of memory allocations. Items contain a handle to the underlying data which might be used during the Release operation.

Usage Example

FILE *file;
// Read the collection header from file which contains 32 bit integers
file,
sizeof(int32_t),
true);
// Create the collection from a file which contains 32 bit integers
file,
filePool,
config,
header,
// Check the collection was create successfully
if (collection != NULL) {
// Initialise the item ready to store data from the collection
// Get a pointer to the value from the collection
int32_t *valuePtr = collection->get(
collection,
0,
&item,
exception);
// Check the value was returned
if (valuePtr != NULL) {
// Get the value from the pointer
int32_t value = *valuePtr;
// Release the value back to the collection
}
// Free the collection
}

Important Considerations

The Item passed to the Get method MUST have had fiftyoneDegreesDataReset called on the data field before use to set the default field values. Without this reset the Collection will not know if it can reuse any memory already allocated from a previous Get operation that is no longer being referenced. For example, if a large string was loaded into an Item, and the Item is then reused for a shorter string, there is no need to reallocate memory. Therefore, the same memory is reused.

The get and release methods of the collection are the only methods that should be used to retrieve items from a collection. An item retrieved with the get method MUST be released when finished with via a call to the collection’s release method.

A call to Get DOES NOT need to set the Collection field of the Item. Collection is not a mandatory field to avoid the overhead of setting the Collection field where the Collection’s implementation of the Release method does nothing. This is important to avoid a performance penalty when all Collection data is in memory and does not need to be released. For this reason the consumer must always reference the Collection directly and not via the Collection field of the Item. The Collection field is used by some internal 51Degrees method where a specific Get method is used that will always set the Collection.

Collaboration diagram for Collection:

Structs

struct  fiftyoneDegreesCollectionHeader
Collection header structure which defines the size and location of the collection data. More...
struct  fiftyoneDegreesCollectionConfig
Collection configuration structure which defines how the collection should be created by the create methods. More...
struct  fiftyoneDegreesCollectionItem
Used to store a handle to the underlying item that could be used to release the item when it's finished with. More...
struct  fiftyoneDegreesCollection
All the shared methods and fields required by file, memory and cached collections. More...
struct  fiftyoneDegreesCollectionMemory
Type of collection where the collection is held in continuous memory. More...
struct  fiftyoneDegreesCollectionFile
Type of collection where the collection is streamed from file. More...
struct  fiftyoneDegreesCollectionCache
Type of collection where items are cached as they are used. More...

Macros

#define  FIFTYONE_DEGREES_COLLECTION_FREE(c)   if (c != NULL) { c->freeCollection(c); }
Free a collection by checking if it is NULL first. More...
#define  FIFTYONE_DEGREES_COLLECTION_RELEASE(c, i)   c->release(i)
Collection release macro used to release a collection item. More...

Typedefs

typedef void *(*  fiftyoneDegreesCollectionGetMethod) (fiftyoneDegreesCollection *collection, uint32_t indexOrOffset, fiftyoneDegreesCollectionItem *item, fiftyoneDegreesException *exception)
Gets an item from the collection. More...
typedef uint32_t(*  fiftyoneDegreesCollectionGetFileVariableSizeMethod) (void *initial)
Passed a pointer to the first part of a variable size item and returns the size of the entire item. More...
typedef void *(*  fiftyoneDegreesCollectionFileRead) (const fiftyoneDegreesCollectionFile *collection, uint32_t offsetOrIndex, fiftyoneDegreesData *data, fiftyoneDegreesException *exception)
Reads the item from the underlying data file. More...
typedef int(*  fiftyoneDegreesCollectionItemComparer) (void *state, fiftyoneDegreesCollectionItem *item, long curIndex, fiftyoneDegreesException *exception)
Compares two items and returns the difference between them for the purposes of a binary search of ordering operation. More...
typedef void(*  fiftyoneDegreesCollectionReleaseMethod) (fiftyoneDegreesCollectionItem *item)
Releases the item so that the collection can free the memory or take other actions when the caller no longer needs access to the item. More...
typedef void(*  fiftyoneDegreesCollectionFreeMethod) (fiftyoneDegreesCollection *collection)
Frees all the memory and handles associated with the collection. More...
typedef bool(*  fiftyoneDegreesCollectionIterateMethod) (void *state, uint32_t key, void *data)
Method used to iterate over data held in a collection. More...

Functions

bool  fiftyoneDegreesCollectionGetIsMemoryOnly ()
Determines if in memory collection methods have been compiled so they are fully optimized. More...
int32_t  fiftyoneDegreesCollectionGetInteger32 (fiftyoneDegreesCollection *collection, uint32_t indexOrOffset, fiftyoneDegreesException *exception)
Returns a 32 bit integer from collections that provide such values. More...
fiftyoneDegreesCollection *  fiftyoneDegreesCollectionCreateFromFile (FILE *file, fiftyoneDegreesFilePool *reader, const fiftyoneDegreesCollectionConfig *config, fiftyoneDegreesCollectionHeader header, fiftyoneDegreesCollectionFileRead read)
Creates a collection from the file handle at the current position in the file. More...
fiftyoneDegreesCollection *  fiftyoneDegreesCollectionCreateFromMemory (fiftyoneDegreesMemoryReader *reader, fiftyoneDegreesCollectionHeader header)
Creates the collection from a memory reader where the collection maps to the memory allocated to the reader. More...
fiftyoneDegreesFileHandle *  fiftyoneDegreesCollectionReadFilePosition (const fiftyoneDegreesCollectionFile *file, uint32_t offset, fiftyoneDegreesException *exception)
Get a handle from the file pool associated with the collection and position the file handle at the offset provided. More...
void *  fiftyoneDegreesCollectionReadFileFixed (const fiftyoneDegreesCollectionFile *file, uint32_t index, fiftyoneDegreesData *data, fiftyoneDegreesException *exception)
Used with collections where each item is a fixed number of bytes recorded in elementSize. More...
fiftyoneDegreesCollectionHeader  fiftyoneDegreesCollectionHeaderFromFile (FILE *file, uint32_t elementSize, bool isCount)
Reads the 4 bytes at the current reader position and configures the collection header. More...
void *  fiftyoneDegreesCollectionReadFileVariable (const fiftyoneDegreesCollectionFile *file, fiftyoneDegreesData *data, uint32_t offset, void *initial, size_t initialSize, fiftyoneDegreesCollectionGetFileVariableSizeMethod getFinalSize, fiftyoneDegreesException *exception)
Reads a variable size item from the file where the initial bytes can be used to calculate the size of the entire item. More...
fiftyoneDegreesCollectionHeader  fiftyoneDegreesCollectionHeaderFromMemory (fiftyoneDegreesMemoryReader *reader, uint32_t elementSize, bool isCount)
Reads the 4 bytes at the current reader position and configures the collection header. More...
long  fiftyoneDegreesCollectionBinarySearch (fiftyoneDegreesCollection *collection, fiftyoneDegreesCollectionItem *item, uint32_t lowerIndex, uint32_t upperIndex, void *state, fiftyoneDegreesCollectionItemComparer comparer, fiftyoneDegreesException *exception)
Where a collection is fixed width and contains an ordered list of items this method is used to perform a divide and conquer search. More...
uint32_t  fiftyoneDegreesCollectionGetCount (fiftyoneDegreesCollection *collection)
Gets the actual number of items in the collection by iterating through to the base collection. More...

Macro Definition Documentation

◆ FIFTYONE_DEGREES_COLLECTION_FREE

#define FIFTYONE_DEGREES_COLLECTION_FREE (   c )    if (c != NULL) { c->freeCollection(c); }

Free a collection by checking if it is NULL first.

Parameters
c - collection to free

◆ FIFTYONE_DEGREES_COLLECTION_RELEASE

#define FIFTYONE_DEGREES_COLLECTION_RELEASE (   c,
  i  
)    c->release(i)

Collection release macro used to release a collection item.

This should always be used in place of the release method to enable methods to be optimised out at compile time when memory only mode is set.

Parameters
c - collection the item belongs to
i - item to release

Typedef Documentation

◆ fiftyoneDegreesCollectionFileRead

typedef void*(* fiftyoneDegreesCollectionFileRead) (const fiftyoneDegreesCollectionFile *collection, uint32_t offsetOrIndex, fiftyoneDegreesData *data, fiftyoneDegreesException *exception)

Reads the item from the underlying data file.

Used by the file related collection methods.

Parameters
collection - pointer to the file collection
offsetOrIndex - index or offset to the item in the data structure
data - pointer to the data structure to store the item
exception - pointer to an exception data structure to be used if an exception occurs. See exceptions.h.
Returns
the value in the data->ptr field, or NULL if not successful

◆ fiftyoneDegreesCollectionFreeMethod

typedef void(* fiftyoneDegreesCollectionFreeMethod) (fiftyoneDegreesCollection *collection)

Frees all the memory and handles associated with the collection.

Parameters
collection - the collection to be freed

◆ fiftyoneDegreesCollectionGetFileVariableSizeMethod

typedef uint32_t(* fiftyoneDegreesCollectionGetFileVariableSizeMethod) (void *initial)

Passed a pointer to the first part of a variable size item and returns the size of the entire item.

Parameters
initial - pointer to the start of the item
Returns
size of the item in bytes

◆ fiftyoneDegreesCollectionGetMethod

typedef void*(* fiftyoneDegreesCollectionGetMethod) (fiftyoneDegreesCollection *collection, uint32_t indexOrOffset, fiftyoneDegreesCollectionItem *item, fiftyoneDegreesException *exception)

Gets an item from the collection.

Returns a pointer to the item, or NULL if the item could not be loaded. The exception parameter is set to the status code to indicate the failure.

Parameters
collection - pointer to the file collection
offsetOrIndex - index or offset to the item in the data structure
item - pointer to the item structure to place the result in
exception - pointer to an exception data structure to be used if an exception occurs. See exceptions.h.
Returns
the value in the data->ptr field, or NULL if not successful

◆ fiftyoneDegreesCollectionItemComparer

typedef int(* fiftyoneDegreesCollectionItemComparer) (void *state, fiftyoneDegreesCollectionItem *item, long curIndex, fiftyoneDegreesException *exception)

Compares two items and returns the difference between them for the purposes of a binary search of ordering operation.

Parameters
state - to be used for the comparison
item - the value to compare against the state
curIndex - the index of the current item in the collection
exception - pointer to an exception data structure to be used if an exception occurs. See exceptions.h
Returns
negative if a is lower than b, positive if a is higher than b or 0 if equal.

◆ fiftyoneDegreesCollectionIterateMethod

typedef bool(* fiftyoneDegreesCollectionIterateMethod) (void *state, uint32_t key, void *data)

Method used to iterate over data held in a collection.

Parameters
state - state data for all callbacks
key - the key used with get method of the item being returned
data - data for the specific item
Returns
true if the iteration should continue, otherwise false to stop it

◆ fiftyoneDegreesCollectionReleaseMethod

typedef void(* fiftyoneDegreesCollectionReleaseMethod) (fiftyoneDegreesCollectionItem *item)

Releases the item so that the collection can free the memory or take other actions when the caller no longer needs access to the item.

Parameters
item - the item returned from Get to be released

Function Documentation

◆ fiftyoneDegreesCollectionBinarySearch()

long fiftyoneDegreesCollectionBinarySearch ( fiftyoneDegreesCollection *   collection,
fiftyoneDegreesCollectionItem *   item,
uint32_t   lowerIndex,
uint32_t   upperIndex,
void *   state,
fiftyoneDegreesCollectionItemComparer   comparer,
fiftyoneDegreesException *   exception  
)

Where a collection is fixed width and contains an ordered list of items this method is used to perform a divide and conquer search.

The state and the comparer are used to compare the current index with the value being sought. If an item is found in the collection the item parameter will contain that item when the method completes. The caller will therefore need to release the item when it's finished with it.

Parameters
collection - to be searched
item - memory to be used to store the current value being compared. Will have a lock on the item at the index returned if an item is found. The caller should release the item when finished with it.
lowerIndex - to start the search at
upperIndex - to end the search at
state - used with the compare method when comparing items
comparer - method used to perform the comparison
exception - pointer to an exception data structure to be used if an exception occurs. See exceptions.h.
Returns
the index of the item if found, otherwise -1.

◆ fiftyoneDegreesCollectionCreateFromFile()

fiftyoneDegreesCollection* fiftyoneDegreesCollectionCreateFromFile ( FILE *   file,
fiftyoneDegreesFilePool *   reader,
const fiftyoneDegreesCollectionConfig *   config,
fiftyoneDegreesCollectionHeader   header,
fiftyoneDegreesCollectionFileRead   read  
)

Creates a collection from the file handle at the current position in the file.

The first 4 bytes read will be the number if fixed with items in the collection OR the number of bytes until the end of the collection data.

Parameters
file - a file handle positioned at the start of the collection
reader - a pool of file handles to use operationally to retrieve data from the file after the collection has been created. These are often shared across different collections accessing the same data file.
config - settings for the implementation of the collection to be used. If FIFTYONE_DEGREES_MEMORY_ONLY is defined, then this is either NULL or it is ignored
header - containing collection structure
read - a pointer to a function to read an item into the collection
Returns
pointer to the new collection, or NULL if something went wrong

◆ fiftyoneDegreesCollectionCreateFromMemory()

fiftyoneDegreesCollection* fiftyoneDegreesCollectionCreateFromMemory ( fiftyoneDegreesMemoryReader *   reader,
fiftyoneDegreesCollectionHeader   header  
)

Creates the collection from a memory reader where the collection maps to the memory allocated to the reader.

The resulting collection does not free the memory used to store the data. This method is used where the entire data structure is loaded into continuous memory and provides a high performance collection in all threading situations.

Parameters
reader - with access to the allocated memory
header - containing collection structure
Returns
pointer to the memory collection, or NULL if the collection could not be created

◆ fiftyoneDegreesCollectionGetCount()

uint32_t fiftyoneDegreesCollectionGetCount ( fiftyoneDegreesCollection *   collection )

Gets the actual number of items in the collection by iterating through to the base collection.

In cases where there are chained collections which pre-load and/or cache elements, the first collections may not contain the full collection of elements. Therefore the value of collection->count may not be correct. This method follows the collection->next pointers to get to the base collection containing the true count.

It is important to note that this gets the count for a collection of fixed size elements, and does not apply to collections of variable sized elements.

Parameters
collection - to get the count for
Returns
the number of items in the collection

◆ fiftyoneDegreesCollectionGetInteger32()

int32_t fiftyoneDegreesCollectionGetInteger32 ( fiftyoneDegreesCollection *   collection,
uint32_t   indexOrOffset,
fiftyoneDegreesException *   exception  
)

Returns a 32 bit integer from collections that provide such values.

Parameters
collection - the collection of 32 bit integers
indexOrOffset - the index or offset of the integer required
exception - pointer to an exception data structure to be used if an exception occurs. See exceptions.h.
Returns
the 32 bit integer at the index or offset provided

◆ fiftyoneDegreesCollectionGetIsMemoryOnly()

bool fiftyoneDegreesCollectionGetIsMemoryOnly ( )

Determines if in memory collection methods have been compiled so they are fully optimized.

This results in the loss of file stream operation. In memory only operation compiling without stream capabilities using the FIFTYONE_DEGREES_MEMORY_ONLY directive results in performance improvements.

Returns
true if the library is compiled for memory only operation, otherwise false.
Examples
Hash/Performance.c.

◆ fiftyoneDegreesCollectionHeaderFromFile()

fiftyoneDegreesCollectionHeader fiftyoneDegreesCollectionHeaderFromFile ( FILE *   file,
uint32_t   elementSize,
bool   isCount  
)

Reads the 4 bytes at the current reader position and configures the collection header.

The 4 bytes can either represent the number of fixed width items in the collection OR the number of bytes that follow the 4 bytes which form the collection. The caller must know the type of structure expected and set the elementSize and isCount parameters.

Parameters
file - a file handle positioned at the start of the collection
elementSize - if known the size in bytes of each item, or 0 for variable width items
isCount - the number of items in the collection if known
Returns
a header set with the details for the collection

◆ fiftyoneDegreesCollectionHeaderFromMemory()

fiftyoneDegreesCollectionHeader fiftyoneDegreesCollectionHeaderFromMemory ( fiftyoneDegreesMemoryReader *   reader,
uint32_t   elementSize,
bool   isCount  
)

Reads the 4 bytes at the current reader position and configures the collection header.

The 4 bytes can either represent the number of fixed width items in the collection OR the number of bytes that follow the 4 bytes which form the collection. The caller must know the type of structure expected and set the elementSize and isCount parameters.

Parameters
reader - with access to the allocated memory
elementSize - if known the size in bytes of each item, or 0 for variable width items
isCount - the number of items in the collection if known
Returns
a header set with the details for the collection

◆ fiftyoneDegreesCollectionReadFileFixed()

void* fiftyoneDegreesCollectionReadFileFixed ( const fiftyoneDegreesCollectionFile *   file,
uint32_t   index,
fiftyoneDegreesData *   data,
fiftyoneDegreesException *   exception  
)

Used with collections where each item is a fixed number of bytes recorded in elementSize.

The method will read that number of bytes into the data item ensuring sufficient memory is allocated. Contained in the collection to avoid repeating this common method across different collection consumers.

Parameters
file - pointer to the fiftyoneDegreesCollectionFile to use for the read
data - structure to populate with a reference to the item
index - zero based index of the item required in the fixed with data structure
exception - pointer to an exception data structure to be used if an exception occurs. See exceptions.h.
Returns
a pointer to the item in the data structure or NULL if can't be found due to an invalid index

◆ fiftyoneDegreesCollectionReadFilePosition()

fiftyoneDegreesFileHandle* fiftyoneDegreesCollectionReadFilePosition ( const fiftyoneDegreesCollectionFile *   file,
uint32_t   offset,
fiftyoneDegreesException *   exception  
)

Get a handle from the file pool associated with the collection and position the file handle at the offset provided.

Parameters
file - pointer to the fiftyoneDegreesCollectionFile to use for the read
offset - from the start of the data structure, not the entire file, where the item should be read from
exception - pointer to an exception data structure to be used if an exception occurs. See exceptions.h.
Returns
a file handle for further read operations, or NULL if the offset is invalid, or a handle can not be obtained.

◆ fiftyoneDegreesCollectionReadFileVariable()

void* fiftyoneDegreesCollectionReadFileVariable ( const fiftyoneDegreesCollectionFile *   file,
fiftyoneDegreesData *   data,
uint32_t   offset,
void *   initial,
size_t   initialSize,
fiftyoneDegreesCollectionGetFileVariableSizeMethod   getFinalSize,
fiftyoneDegreesException *   exception  
)

Reads a variable size item from the file where the initial bytes can be used to calculate the size of the entire item.

Parameters
file - pointer to the fiftyoneDegreesCollectionFile to use for the read
data - structure to populate with a reference to the item
offset - zero based offset to the item within the data structure
initial - pointer to enough memory to store the initial data
initialSize - amount of initial data to read
getFinalSize - method pass the initial pointer to get the final size
exception - pointer to an exception data structure to be used if an exception occurs. See exceptions.h.
Returns
a pointer to the item in the data structure or NULL if can't be found due to an invalid index