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
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) |
| Free a collection by checking if it is NULL first. | |
| #define | FIFTYONE_DEGREES_COLLECTION_RELEASE(c, i) |
| Collection release macro used to release a collection item. | |
| #define | fiftyoneDegreesCollectionGetCount(collection) |
| Gets the actual number of items in the collection by iterating through to the base collection. | |
Typedefs | |
| typedef void *(* | fiftyoneDegreesCollectionGetMethod) (const fiftyoneDegreesCollection *collection, const fiftyoneDegreesCollectionKey *key, fiftyoneDegreesCollectionItem *item, fiftyoneDegreesException *exception) |
| Gets an item from the collection. | |
| typedef void *(* | fiftyoneDegreesCollectionFileRead) (const fiftyoneDegreesCollectionFile *collection, const fiftyoneDegreesCollectionKey *key, fiftyoneDegreesData *data, fiftyoneDegreesException *exception) |
| Reads the item from the underlying data file. | |
| typedef int(* | fiftyoneDegreesCollectionItemComparer) (void *state, fiftyoneDegreesCollectionItem *item, fiftyoneDegreesCollectionKey key, fiftyoneDegreesException *exception) |
| Compares two items and returns the difference between them for the purposes of a binary search of ordering operation. | |
| 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. | |
| typedef void(* | fiftyoneDegreesCollectionFreeMethod) (fiftyoneDegreesCollection *collection) |
| Frees all the memory and handles associated with the collection. | |
| typedef bool(* | fiftyoneDegreesCollectionIterateMethod) (void *state, uint32_t key, void *data) |
| Method used to iterate over data held in a collection. | |
Functions | |
| bool | fiftyoneDegreesCollectionGetIsMemoryOnly () |
| Determines if in memory collection methods have been compiled so they are fully optimized. | |
| int32_t | fiftyoneDegreesCollectionGetInteger32 (const fiftyoneDegreesCollection *collection, uint32_t indexOrOffset, fiftyoneDegreesException *exception) |
| Returns a 32 bit integer from collections that provide such values. | |
| 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. | |
| fiftyoneDegreesCollection * | fiftyoneDegreesCollectionCreateFromMemory (fiftyoneDegreesMemoryReader *reader, fiftyoneDegreesCollectionHeader header) |
| Creates the collection from a memory reader where the collection maps to the memory allocated to the reader. | |
| 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. | |
| void * | fiftyoneDegreesCollectionReadFileFixed (const fiftyoneDegreesCollectionFile *file, const fiftyoneDegreesCollectionKey *key, fiftyoneDegreesData *data, fiftyoneDegreesException *exception) |
| Used with collections where each item is a fixed number of bytes recorded in elementSize. | |
| fiftyoneDegreesCollectionHeader | fiftyoneDegreesCollectionHeaderFromFile (FILE *file, uint32_t elementSize, bool isCount) |
| Reads the 4 bytes at the current reader position and configures the collection header. | |
| void * | fiftyoneDegreesCollectionReadFileVariable (const fiftyoneDegreesCollectionFile *file, fiftyoneDegreesData *data, const fiftyoneDegreesCollectionKey *key, void *initial, 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. | |
| fiftyoneDegreesCollectionHeader | fiftyoneDegreesCollectionHeaderFromMemory (fiftyoneDegreesMemoryReader *reader, uint32_t elementSize, bool isCount) |
| Reads the 4 bytes at the current reader position and configures the collection header. | |
| long | fiftyoneDegreesCollectionBinarySearch (const fiftyoneDegreesCollection *collection, fiftyoneDegreesCollectionItem *item, fiftyoneDegreesCollectionIndexOrOffset lowerKey, fiftyoneDegreesCollectionIndexOrOffset upperKey, const fiftyoneDegreesCollectionKeyType *keyType, 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. | |
Macro Definition Documentation
◆ FIFTYONE_DEGREES_COLLECTION_FREE
| #define FIFTYONE_DEGREES_COLLECTION_FREE | ( | 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 ) |
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
◆ fiftyoneDegreesCollectionGetCount
| #define fiftyoneDegreesCollectionGetCount | ( | 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
Typedef Documentation
◆ fiftyoneDegreesCollectionFileRead
| typedef void *(* fiftyoneDegreesCollectionFileRead) (const fiftyoneDegreesCollectionFile *collection, const fiftyoneDegreesCollectionKey *key, 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 key key of 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
◆ fiftyoneDegreesCollectionGetMethod
| typedef void *(* fiftyoneDegreesCollectionGetMethod) (const fiftyoneDegreesCollection *collection, const fiftyoneDegreesCollectionKey *key, 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 key key of 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, fiftyoneDegreesCollectionKey key, 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 key key of the item in the data structure 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 | ( | const fiftyoneDegreesCollection * | collection, |
| fiftyoneDegreesCollectionItem * | item, | ||
| fiftyoneDegreesCollectionIndexOrOffset | lowerKey, | ||
| fiftyoneDegreesCollectionIndexOrOffset | upperKey, | ||
| const fiftyoneDegreesCollectionKeyType * | keyType, | ||
| 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. lowerKey to start the search at upperKey to end the search at keyType type of lower/upper keys 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
◆ fiftyoneDegreesCollectionGetInteger32()
| int32_t fiftyoneDegreesCollectionGetInteger32 | ( | const 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.
◆ 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, |
| const fiftyoneDegreesCollectionKey * | key, | ||
| 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 key 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, | ||
| const fiftyoneDegreesCollectionKey * | key, | ||
| void * | initial, | ||
| 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 key key of the item in the data structure initial pointer to enough memory to store the initial data 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