bitwise trie implementation More...
#include "cgul_common.h"#include "cgul_exception.h"#include "cgul_cache.h"#include "cgul_bitwise_trie_node.h"
Typedefs | |
| typedef typedefCGUL_BEGIN_C struct cgul_bitwise_trie * | cgul_bitwise_trie_t |
Detailed Description
Bitwise trie implementation.
Typedef Documentation
§ cgul_bitwise_trie_t
| typedef typedefCGUL_BEGIN_C struct cgul_bitwise_trie* cgul_bitwise_trie_t |
Opaque pointer to a cgul_bitwise_trie instance.
Function Documentation
§ cgul_bitwise_trie__new()
| CGUL_EXPORT cgul_bitwise_trie_t cgul_bitwise_trie__new | ( | cgul_exception_t * | cex | ) |
Create a new cgul_bitwise_trie object. If memory cannot be allocated, NULL is returned, and an exception is thrown. The client is responsible for freeing the object by calling cgul_bitwise_trie__delete().
- Parameters
-
[in,out] cex c-style exception
- Returns
- new
cgul_bitwise_trieinstance
§ cgul_bitwise_trie__delete()
| CGUL_EXPORT void cgul_bitwise_trie__delete | ( | cgul_bitwise_trie_t | t | ) |
This method frees all internally allocated memory. This does not include the values stored in the trie. The client is responsible for freeing the values when the client thinks it is convenient and safe to do so.
As a convenience, you may want to call cgul_bitwise_trie__clear() before calling this method in order to properly put the values back on its cgul_cache object (if a cgul_cache object is being used) before you delete the trie. If a cgul_cache object is not being used, the client needs to arrange some other mechanism to free the values.
Do not try to access t after calling this method.
- Parameters
-
[in] t cgul_bitwise_trieinstance
- See also
- cgul_bitwise_trie__free_values()
§ cgul_bitwise_trie__free_values()
| CGUL_EXPORT void cgul_bitwise_trie__free_values | ( | cgul_bitwise_trie_t | t | ) |
This method calls free() on all the values in the trie t. Because this is such a common operation, it is an exception to the rule that cgul containers never free values. This method should only ever be called immediately before calling cgul_bitwise_trie__delete() because it otherwise invalidates the trie. Because this function is basically an extension of cgul_bitwise_trie__delete(), it does not accept a cgul_exception object as an input parameter.
- Parameters
-
[in] t cgul_bitwise_trieinstance
§ cgul_bitwise_trie__get_cache_size()
| CGUL_EXPORT unsigned long int cgul_bitwise_trie__get_cache_size | ( | cgul_exception_t * | cex, |
| cgul_bitwise_trie_t | t | ||
| ) |
Get the size of the cache of nodes.
- Parameters
-
[in] cex c-style exception [in] t cgul_bitwise_trieinstance
- Returns
- size of the cache of nodes
§ cgul_bitwise_trie__set_cache_size()
| CGUL_EXPORT void cgul_bitwise_trie__set_cache_size | ( | cgul_exception_t * | cex, |
| cgul_bitwise_trie_t | t, | ||
| unsigned long int | size | ||
| ) |
Set the size of the cache of nodes.
For efficiency, the cgul_bitwise_trie can keep a cache of nodes that can be reused. In many situations, this can greatly reduce the number of calls to malloc() which can greatly improve performance and reduce memory fragmentation.
You can release all the cached nodes and disable caching of nodes by setting the cache reserve to 0 and the cache size to 0 (in that order). This is the default.
If an error occurs (while enlarging the cache), an exception is thrown.
- Parameters
-
[in,out] cex c-style exception [in] t cgul_bitwise_trieinstance[in] size of the cache of nodes
§ cgul_bitwise_trie__get_cache_reserve()
| CGUL_EXPORT unsigned long int cgul_bitwise_trie__get_cache_reserve | ( | cgul_exception_t * | cex, |
| cgul_bitwise_trie_t | t | ||
| ) |
Get the reserve limit of the cache of nodes.
- Parameters
-
[in] cex c-style exception [in] t cgul_bitwise_trieinstance
- Returns
- reserve limit of the cache of nodes
§ cgul_bitwise_trie__set_cache_reserve()
| CGUL_EXPORT void cgul_bitwise_trie__set_cache_reserve | ( | cgul_exception_t * | cex, |
| cgul_bitwise_trie_t | t, | ||
| unsigned long int | reserve | ||
| ) |
Set the reserve limit of the cache of nodes and guarantee that at least that many nodes are allocated and waiting in reserve.
When you use this method to increase the reserve, you are guaranteed that at least reserve count of nodes will be allocated and reserved for future use.
This is useful because cgul_bitwise_trie__insert() can throw an exception if it cannot allocate a node to hold the index/value pair. Thus, by allocating and reserving a node now, we know that cgul_bitwise_trie__insert() will be able to run without error later when the node is "unreserved". Normally, this is not an issue because you can almost always just insert at the moment when it is requested, but if the cgul_bitwise_trie is busy at that moment (perhaps it is iterating over its nodes), you'll have to queue insert (and remove) requests for later execution.
To "unreserve" a node so that it can be used, you simply call this method again with a value for reserve that is less than the current reserve limit.
If an error occurs while allocating the reserved nodes, an exception is thrown.
WARNING: If you reserve nodes without "unreserving" them, you will introduce a memory leak that is difficult to track down because this class is careful to free all of the cached nodes (including the reserved nodes) when it is deleted, but the reserved nodes will just sit around in memory until that time. Thus, after reserving nodes by calling this method, you must remember to timely set the reserve level back to zero in order to make those nodes available.
- Parameters
-
[in,out] cex c-style exception [in] t cgul_bitwise_trieinstance[in] reserve of the cache of nodes
- See also
- cgul_cache__set_reserve
§ cgul_bitwise_trie__is_empty()
| CGUL_EXPORT int cgul_bitwise_trie__is_empty | ( | cgul_exception_t * | cex, |
| cgul_bitwise_trie_t | t | ||
| ) |
Return 1 if the trie is empty; otherwise, return 0.
- Parameters
-
[in] cex c-style exception [in] t cgul_bitwise_trieinstance
- Returns
- whether the trie is empty
§ cgul_bitwise_trie__assign()
| CGUL_EXPORT void cgul_bitwise_trie__assign | ( | cgul_exception_t * | cex, |
| cgul_bitwise_trie_t | t, | ||
| unsigned long int | index, | ||
| void * | ptr | ||
| ) |
Assign ptr to t[index].
- Parameters
-
[in,out] cex c-style exception [in] t cgul_bitwise_trieinstance[in] index index into t[in] ptr pointer to assign to t[index]
§ cgul_bitwise_trie__at()
| CGUL_EXPORT void* cgul_bitwise_trie__at | ( | cgul_exception_t * | cex, |
| cgul_bitwise_trie_t | t, | ||
| unsigned long int | index, | ||
| int * | exists | ||
| ) |
This method returns the element at t[index]. If index cannot be found in the trie, NULL is returned.
If and only if exists is not NULL, this method will set it to 1 if a node exists for index and to 0 otherwise. This lets the client distinguished between a NULL value that is returned because index could not be found and a NULL value that is returned because a it is being stored in the trie.
- Parameters
-
[in,out] cex c-style exception [in] t cgul_bitwise_trieinstance[in] index index into t[out] exists whether a node exists for index
- Returns
- element at
t[index]
§ cgul_bitwise_trie__remove()
| CGUL_EXPORT int cgul_bitwise_trie__remove | ( | cgul_exception_t * | cex, |
| cgul_bitwise_trie_t | t, | ||
| unsigned long int | index, | ||
| void ** | value_out | ||
| ) |
Remove the node in t associated with index. The value pointer stored in the node that is to be removed will be returned in value_out if you pass in a pointer that is not NULL. This method returns 1 if the node was removed; it returns 0 otherwise.
- Parameters
-
[in] cex c-style exception [in] t cgul_bitwise_trieinstance[in] index index into t[out] value_out pointer for the value stored in the node
- Returns
- whether the node was removed
§ cgul_bitwise_trie__get_oldest()
| CGUL_EXPORT cgul_bitwise_trie_node_t cgul_bitwise_trie__get_oldest | ( | cgul_exception_t * | cex, |
| cgul_bitwise_trie_t | t | ||
| ) |
Return the oldest node according to chronological order (i.e., the order in which the nodes are inserted). This operation is O(1). If the trie is empty, NULL is returned. This class does not have to search the trie in order to find the oldest node because it efficiently keeps a direct pointer to the oldest node up to date.
The following example shows how to iterate over the entire trie in chronological order:
cgul_bitwise_trie_node_t n = cgul_bitwise_trie__get_oldest(cex, t);
for ( ; n ; n = cgul_bitwise_trie_node__get_younger(cex, n)) {
...
}
- Parameters
-
[in] cex c-style exception [in] t cgul_bitwise_trieinstance
- Returns
- oldest node
§ cgul_bitwise_trie__set_oldest()
| CGUL_EXPORT void cgul_bitwise_trie__set_oldest | ( | cgul_exception_t * | cex, |
| cgul_bitwise_trie_t | t, | ||
| cgul_bitwise_trie_node_t | n | ||
| ) |
Set the oldest node in the trie to be n. This method could be used, for example, if your code expires the oldest node in the trie, and you want to force n to be the next node to expire.
- Parameters
-
[in] cex c-style exception [in] t cgul_bitwise_trieinstance[in] n node
§ cgul_bitwise_trie__get_youngest()
| CGUL_EXPORT cgul_bitwise_trie_node_t cgul_bitwise_trie__get_youngest | ( | cgul_exception_t * | cex, |
| cgul_bitwise_trie_t | t | ||
| ) |
Return the youngest node according to chronological order (i.e., the order in which the nodes are inserted). This operation is O(1). If the trie is empty, NULL is returned. This class does not have to search the trie in order to find the youngest node because it efficiently keeps a direct pointer to the youngest node up to date.
The following example shows how to iterate over the entire trie in reverse chronological order:
cgul_bitwise_trie_node_t n = cgul_bitwise_trie__get_youngest(cex, t);
for ( ; n ; n = cgul_bitwise_trie_node__get_older(cex, n)) {
...
}
- Parameters
-
[in] cex c-style exception [in] t cgul_bitwise_trieinstance
- Returns
- youngest node
§ cgul_bitwise_trie__set_youngest()
| CGUL_EXPORT void cgul_bitwise_trie__set_youngest | ( | cgul_exception_t * | cex, |
| cgul_bitwise_trie_t | t, | ||
| cgul_bitwise_trie_node_t | n | ||
| ) |
Set the youngest node in the trie to be n. This method could be used, for example, if your code expires the least-recently used (LRU) node. By calling cgul_bitwise_trie__set_youngest() each time a node is used, the least-recently used node will be the oldest node in the trie.
- Parameters
-
[in] cex c-style exception [in] t cgul_bitwise_trieinstance[in] n node
- See also
- cgul_bitwise_trie__set_oldest()
§ cgul_bitwise_trie__get_size()
| CGUL_EXPORT unsigned long int cgul_bitwise_trie__get_size | ( | cgul_exception_t * | cex, |
| cgul_bitwise_trie_t | t | ||
| ) |
Return the total number of elements stored in t. This value can be less than than the maximum index stored in t because in general cgul_bitwise_trie instances are sparse.
- Parameters
-
[in] cex c-style exception [in] t cgul_bitwise_trieinstance
- Returns
- size of the trie
§ cgul_bitwise_trie__swap()
| CGUL_EXPORT void cgul_bitwise_trie__swap | ( | cgul_exception_t * | cex, |
| cgul_bitwise_trie_t | t1, | ||
| cgul_bitwise_trie_t | t2 | ||
| ) |
Swap the underlying data for t1 and t2. For large bitwise tries, this should be much faster than trying to do the same thing using removes and inserts.
- Parameters
-
[in] cex c-style exception [in] t1 first cgul_bitwise_trieinstance[in] t2 second cgul_bitwise_trieinstance
