51Degrees Device Detection C/C++  4.1

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

Cache

Detailed Description

Fixed size, thread safe, loading, tree based cache.

Introduction

Implements a fixed size, thread safe, loading, tree based cache. Items requested which are not in the cache already are loaded using the specified load method, before returning as with items which are already in the cache.

Items are fetched from the cache using the fiftyoneDegreesCacheGet method and the item is prevented from being expelled from the cache until the fiftyoneDegreesCacheRelease method is called. Failure to release cache items once they are finished with will result in the available nodes in the cache being exhausted (i.e. no new items can be loaded into the cache).

As the cache is fixed size, the size must be set correctly in order to prevent failures in the get method. The size of a cache MUST be equal to or greater than the maximum number of items which will be in use simultaneously across all threads. Fetching more items than the cache was created to expect will result in the same failure as not releasing items.

The cache is sharded based on the modulo of the key to improve performance in multi threaded operation where an even distribution of key modulos are present.

Details of the red black tree implementation can be found in tree.c.

Example Usage

byte *data;
fiftyoneDegreesCacheLoadMethod *methodToLoadEntryFromData;
// Create a cache
100,
1,
methodToLoadEntryFromData,
data);
// Get an item from the cache
cache,
&0,
exception);
// Check that the value was found
if (entry != NULL) {
// Get the value from the entry
int *value = (int*)entry->data.ptr;
// Do something with the value
// ...
// Release the entry back to the cache
}
// Free the cache

Collaboration diagram for Cache:

Structs

struct  fiftyoneDegreesCacheNode
Cache node structure used for storing data in the cache along with its key. More...
struct  fiftyoneDegreesCacheShard
Cache shard structure used to enable concurrent access to the cache. More...
struct  fiftyoneDegreesCache
Cache structure to store the root of the red black tree and a list of allocated cache nodes. More...

Typedefs

typedef void(*  fiftyoneDegreesCacheLoadMethod) (const void *state, fiftyoneDegreesData *data, const void *key, fiftyoneDegreesException *exception)
Method used to load data into the cache. More...
typedef int64_t(*  fiftyoneDegreesCacheHashCodeMethod) (const void *key)
Method used to calculate a hash code from the key. More...

Functions

fiftyoneDegreesCache *  fiftyoneDegreesCacheCreate (uint32_t capacity, uint16_t concurrency, fiftyoneDegreesCacheLoadMethod load, fiftyoneDegreesCacheHashCodeMethod hash, const void *state)
Creates a new cache.The cache must be destroyed with the fiftyoneDegreesCacheFree method. More...
void  fiftyoneDegreesCacheFree (fiftyoneDegreesCache *cache)
Frees the cache structure, all allocated nodes and their data. More...
fiftyoneDegreesCacheNode *  fiftyoneDegreesCacheGet (fiftyoneDegreesCache *cache, const void *key, fiftyoneDegreesException *exception)
Gets an item from the cache. More...
void  fiftyoneDegreesCacheRelease (fiftyoneDegreesCacheNode *node)
Releases the cache node previous obtained via fiftyoneDegreesCacheGet so that it can be evicted from the cache if needed. More...
int64_t  fiftyoneDegreesCacheHash32 (const void *key)
Passed a pointer to a 32 bit / 4 byte data structure and returns the data as a 64 bit / 8 byte value for use in the cache. More...
int64_t  fiftyoneDegreesCacheHash64 (const void *key)
Passed a pointer to a 64 bit / 8 byte data structure and returns the data as a 64 bit / 8 byte value for use in the cache. More...

Typedef Documentation

◆ fiftyoneDegreesCacheHashCodeMethod

typedef int64_t(* fiftyoneDegreesCacheHashCodeMethod) (const void *key)

Method used to calculate a hash code from the key.

Parameters
key - the data to be calculate the integer key.
Returns
64 bit representation of the key data.

◆ fiftyoneDegreesCacheLoadMethod

typedef void(* fiftyoneDegreesCacheLoadMethod) (const void *state, fiftyoneDegreesData *data, const void *key, fiftyoneDegreesException *exception)

Method used to load data into the cache.

Parameters
state - information used for the load operation.
data - structure to be used to store the data loaded.
key - for the item in the collection to be loaded.
exception - pointer to an exception data structure to be used if an exception occurs. See exceptions.h.

Function Documentation

◆ fiftyoneDegreesCacheCreate()

fiftyoneDegreesCache* fiftyoneDegreesCacheCreate ( uint32_t   capacity,
uint16_t   concurrency,
fiftyoneDegreesCacheLoadMethod   load,
fiftyoneDegreesCacheHashCodeMethod   hash,
const void *   state  
)

Creates a new cache.The cache must be destroyed with the fiftyoneDegreesCacheFree method.

Parameters
capacity - maximum number of items that the cache should store
concurrency - the expected number of parallel operations
load - pointer to method used to load an entry into the cache
hash - pointer to a method used to hash the key into a int64_t
state - pointer to state information to pass to the load method
Returns
a pointer to the cache created, or NULL if one was not created.

◆ fiftyoneDegreesCacheFree()

void fiftyoneDegreesCacheFree ( fiftyoneDegreesCache *   cache )

Frees the cache structure, all allocated nodes and their data.

Parameters
cache - to be freed

◆ fiftyoneDegreesCacheGet()

fiftyoneDegreesCacheNode* fiftyoneDegreesCacheGet ( fiftyoneDegreesCache *   cache,
const void *   key,
fiftyoneDegreesException *   exception  
)

Gets an item from the cache.

If an item is not in the cache, it is loaded using the loader the cache was initialized with.

The cache being used as a loading cache must have a load method defined which returns a pointer to the data relating to the key used. This method may, or may not, allocate memory or free memory previously allocated to data in the cache node.

Nodes fetched from the cache are protected from modification until all references to them are released. This means that the size of the cache must be carefully chosen to be no smaller than the maximum number of nodes which may be in use at any one time. Attempting to fetch a node when there are no free nodes to load the data into will result in a null being returned.

Parameters
cache - to get the entry from
key - for the item to be returned
exception - pointer to an exception data structure to be used if an exception occurs. See exceptions.h.
Returns
pointer to the requested item or null if too many items have been fetched and not released or the key is not valid

◆ fiftyoneDegreesCacheHash32()

int64_t fiftyoneDegreesCacheHash32 ( const void *   key )

Passed a pointer to a 32 bit / 4 byte data structure and returns the data as a 64 bit / 8 byte value for use in the cache.

Used when cache keys are 32 bit integers.

Parameters
key - to be used in the cache
Returns
key represented as a 64 bit integer

◆ fiftyoneDegreesCacheHash64()

int64_t fiftyoneDegreesCacheHash64 ( const void *   key )

Passed a pointer to a 64 bit / 8 byte data structure and returns the data as a 64 bit / 8 byte value for use in the cache.

Used when cache keys are 64 bit integers.

Parameters
key - to be used in the cache
Returns
key represented as a 64 bit integer

◆ fiftyoneDegreesCacheRelease()

void fiftyoneDegreesCacheRelease ( fiftyoneDegreesCacheNode *   node )

Releases the cache node previous obtained via fiftyoneDegreesCacheGet so that it can be evicted from the cache if needed.

Parameters
node - to be released.
On This Page