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. | |
| 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.
A node in use cannot be expelled and any operation can need any shard, so every shard holds at least one node for each operation that can use the cache at the same time. The cache has as many shards as the concurrency, or fewer where that is needed, and a capacity below the concurrency is raised to it.
- Parameters
-
capacity number of items that the cache should store concurrency the expected number of parallel operations, where 0 is taken as 1 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 the memory could not be allocated.
◆ 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. A load that fails also returns null, and its node is free to be used again.
- 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.