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
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. | |
| typedef int64_t(* | fiftyoneDegreesCacheHashCodeMethod) (const void *key) |
| Method used to calculate a hash code from the key. | |
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. | |
| void | fiftyoneDegreesCacheFree (fiftyoneDegreesCache *cache) |
| Frees the cache structure, all allocated nodes and their data. | |
| fiftyoneDegreesCacheNode * | fiftyoneDegreesCacheGet (fiftyoneDegreesCache *cache, const void *key, fiftyoneDegreesException *exception) |
| Gets an item from the cache. | |
| void | fiftyoneDegreesCacheRelease (fiftyoneDegreesCacheNode *node) |
| Releases the cache node previous obtained via fiftyoneDegreesCacheGet so that it can be evicted from the cache if needed. | |
| 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. | |
| 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. | |
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.