In any real-world application where you use elements to represent information, you'll often need to search for those elements using different keys or criteria.
This is where the concept of multi-indexing becomes essential.
Consider a common example: files in a file system. A single file element might need to be found in several distinct ways:
- By its name (e.g., 'document.pdf').
- By its residing directory (e.g., '/home/user/documents/').
- By its full path (e.g., '/home/user/documents/document.pdf').
- By its unique inode number.
With multi-indexing, each search key requires the file element to be inserted into a separate, dedicated data structure (like a hash table or a tree) to allow for a fast search based on that specific key. This is exactly what TommyDS is designed to facilitate.
You can compare this concept to a SQL database. In a database, a single table can have multiple indexes. Each index allows for a fast lookup of rows based on the value in a specific column (the search key), without having to scan the entire table. TommyDS helps you achieve this same performance benefit in your C application for in-memory data structures.
TommyDS simplifies the management of these multiple indexes, allowing you to have a single element, but link it into several different data structures simultaneously, each using a different field of the element as the search key.
For example, if your application needs to preserve the global insertion order across multiple indexes or across the entire collection, you can include an auxiliary tommy_list alongside the indexed structures. This gives you the best of both worlds: fast lookup via the indexed containers, and sequential traversal in original insertion order via the list.
The next code example demonstrates using multiple data structures (a list to preserve global insertion order and several hash tables for indexing) to store a 'file' element, allowing access and searching based on different fields.
First, we declare the file element structure, including the required intrusive nodes for the various data structures that will store it.
struct file {
char dir[MAXDIR];
char name[MAXNAME];
inode_t inode;
};
Data structure node.
Definition: tommytypes.h:242
Next, we define helper functions to compute the hash for each field used as a key and comparison functions to search for an element based on a specified key.
int search_by_inode(const void* arg, const void* elem)
{
const inode_t* inode = arg;
const struct file* f = elem;
return *inode != f->inode;
}
{
}
{
}
{
}
struct path {
char* dir;
char* name;
};
int search_by_path(const void* arg, const void* elem)
{
const struct path* p = arg;
const struct file* f = elem;
return strcmp(p->dir, f->dir) != 0 || strcmp(p->name, f->name) != 0;
}
tommy_hash_t hash_by_path(
const char* dir,
const char* name)
{
}
tommy_uint32_t tommy_strhash_u32(tommy_uint32_t init_val, const void *void_key)
String hash function with a 32-bit result.
Definition: tommyhash.h:107
tommy_uint64_t tommy_inthash_u64(tommy_uint64_t key)
Reversible 64-bit integer hash function.
Definition: tommyhash.h:161
tommy_size_t tommy_hash_t
Type used in hashtables to store the hash of an element.
Definition: tommytypes.h:224
Now we declare and initialize the data structures.
Hashtable container type.
Definition: tommyhashdyn.h:182
TOMMY_API void tommy_hashdyn_init(tommy_hashdyn *hashdyn)
Initializes the hashtable.
void tommy_list_init(tommy_list *list)
Initializes the list.
Definition: tommylist.h:190
We create a file element and insert it into all the data structures.
struct file* f = malloc(sizeof(struct file));
strcpy(f->dir, ...);
strcpy(f->name, ...);
f->inode = ...;
TOMMY_API void tommy_hashdyn_insert(tommy_hashdyn *hashdyn, tommy_hashdyn_node *node, void *data, tommy_hash_t hash)
Inserts an element in the hashtable.
void tommy_list_insert_tail(tommy_list *list, tommy_node *node, void *data)
Inserts an element at the tail of a list.
Definition: tommylist.h:331
After all files are inserted, we can now search them by inode, remove a file with a specific path, and list all the files with a specific name, regardless of the directory they reside in.
inode_t inode_to_find = ...;
struct file* found =
tommy_hashdyn_search(&hashtable_by_inode, search_by_inode, &inode_to_find, hash_by_inode(inode_to_find));
if (found) {
printf("%s/%s\n", found->dir, found->name);
}
struct path path_to_find;
path_to_find.dir = ...;
path_to_find.name = ...;
found =
tommy_hashdyn_search(&hashtable_by_path, search_by_path, &path_to_find, hash_by_path(path_to_find.dir, path_to_find.name));
if (found) {
printf("%s/%s\n", found->dir, found->name);
}
const char* name_to_find = ...;
while (i) {
struct file* f = i->
data;
if (strcmp(f->name, name_to_find) == 0) {
printf("%s/%s\n", f->dir, f->name);
}
}
while (i) {
struct file* found = i->
data;
printf("%s/%s %lu\n", found->dir, found->name, found->inode);
}
struct tommy_node_struct * next
Next node.
Definition: tommytypes.h:247
void * data
Pointer to the element containing the node.
Definition: tommytypes.h:260
void * tommy_hashdyn_search(tommy_hashdyn *hashdyn, tommy_search_func *cmp, const void *cmp_arg, tommy_hash_t hash)
Searches an element in the hashtable.
Definition: tommyhashdyn.h:349
tommy_hashdyn_node * tommy_hashdyn_bucket(tommy_hashdyn *hashdyn, tommy_hash_t hash)
Gets the bucket of the specified hash.
Definition: tommyhashdyn.h:309
TOMMY_API void * tommy_hashdyn_remove_existing(tommy_hashdyn *hashdyn, tommy_hashdyn_node *node)
Removes an element from the hashtable.
void * tommy_list_remove_existing(tommy_list *list, tommy_node *node)
Removes an element from the list.
Definition: tommylist.h:406
tommy_node * tommy_list_head(tommy_list *list)
Gets the head of the list.
Definition: tommylist.h:215
Finally, we deallocate all the file elements and deinitialize the data structures.
TOMMY_API void tommy_hashdyn_done(tommy_hashdyn *hashdyn)
Deinitializes the hashtable.
void tommy_list_foreach(tommy_list *list, tommy_foreach_func *func)
Calls the specified function for each element in the list.
Definition: tommylist.h:770