tommyhashtbl.h
Go to the documentation of this file.
1// SPDX-License-Identifier: BSD-2-Clause
2// Copyright (C) 2010 Andrea Mazzoleni
3
143#ifndef TOMMY_HASHTBL_H
144#define TOMMY_HASHTBL_H
145
146#include "tommyhash.h"
147#include "tommylist.h"
148
149/******************************************************************************/
150/* hashtable */
151
157
168
175TOMMY_API void tommy_hashtable_init(tommy_hashtable* hashtable, tommy_size_t bucket_max);
176
184TOMMY_API void tommy_hashtable_done(tommy_hashtable* hashtable);
185
195tommy_inline void tommy_hashtable_swap(tommy_hashtable* first, tommy_hashtable* second)
196{
197 tommy_hashtable tmp = *first;
198 *first = *second;
199 *second = tmp;
200}
201
211TOMMY_API void tommy_hashtable_clear(tommy_hashtable* hashtable);
212
220TOMMY_API void tommy_hashtable_insert(tommy_hashtable* hashtable, tommy_hashtable_node* node, void* data, tommy_hash_t hash);
221
238TOMMY_API void* tommy_hashtable_insert_unique(tommy_hashtable* hashtable, tommy_hashtable_node* node, void* data, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash);
239
252TOMMY_API void* tommy_hashtable_remove(tommy_hashtable* hashtable, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash);
253
264{
265 return hashtable->bucket[hash & hashtable->bucket_mask];
266}
267
279tommy_inline tommy_hashtable_node* tommy_hashtable_find(tommy_hashtable* hashtable, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
280{
281 tommy_hashtable_node* i = tommy_hashtable_bucket(hashtable, hash);
282
283 while (i) {
284 /* we first check if the hash matches, as in the same bucket we may have multiple hash values */
285 if (i->index == hash && cmp(cmp_arg, i->data) == 0)
286 return i;
287 i = i->next;
288 }
289 return 0;
290}
291
303tommy_inline void* tommy_hashtable_search(tommy_hashtable* hashtable, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
304{
305 tommy_hashtable_node* node = tommy_hashtable_find(hashtable, cmp, cmp_arg, hash);
306
307 return node ? node->data : 0;
308}
309
318
329
340
352
364
381
420
430TOMMY_API void tommy_hashtable_foreach_arg(tommy_hashtable* hashtable, tommy_foreach_arg_func* func, void* arg);
431
439{
440 return hashtable->count;
441}
442
450{
451 return hashtable->count == 0;
452}
453
461{
462 return hashtable->bucket_max;
463}
464
472
512TOMMY_API void tommy_hashtable_to_list(tommy_hashtable* hashtable, tommy_list* list);
513
514#endif
515
Hashtable container type.
Definition: tommyhashtbl.h:162
tommy_hashtable_node ** bucket
Hash buckets.
Definition: tommyhashtbl.h:163
tommy_size_t bucket_mask
Bit mask to access the buckets.
Definition: tommyhashtbl.h:165
tommy_size_t bucket_max
Number of buckets.
Definition: tommyhashtbl.h:164
tommy_size_t count
Number of elements.
Definition: tommyhashtbl.h:166
Data structure node.
Definition: tommytypes.h:242
tommy_size_t index
Index of the node.
Definition: tommytypes.h:269
struct tommy_node_struct * next
Next node.
Definition: tommytypes.h:247
void * data
Pointer to the element containing the node.
Definition: tommytypes.h:260
Hash functions for use with tommy_hashtable, tommy_hashdyn and tommy_hashlin.
void * tommy_hashtable_search(tommy_hashtable *hashtable, tommy_search_func *cmp, const void *cmp_arg, tommy_hash_t hash)
Searches an element in the hashtable.
Definition: tommyhashtbl.h:303
tommy_size_t tommy_hashtable_bucket_count(const tommy_hashtable *hashtable)
Gets the number of buckets.
Definition: tommyhashtbl.h:460
TOMMY_API void tommy_hashtable_rehash_existing(tommy_hashtable *hashtable, tommy_hashtable_node *node, tommy_hash_t hash)
Updates the hash of an element already contained in the hashtable.
TOMMY_API tommy_hashtable_node * tommy_hashtable_head(tommy_hashtable *hashtable)
Gets the first node in iteration order, or 0 if empty.
tommy_bool_t tommy_hashtable_empty(const tommy_hashtable *hashtable)
Checks whether the hashtable is empty.
Definition: tommyhashtbl.h:449
tommy_hashtable_node * tommy_hashtable_find(tommy_hashtable *hashtable, tommy_search_func *cmp, const void *cmp_arg, tommy_hash_t hash)
Finds a node in the hashtable.
Definition: tommyhashtbl.h:279
TOMMY_API void tommy_hashtable_done(tommy_hashtable *hashtable)
Deinitializes the hashtable.
TOMMY_API void tommy_hashtable_init(tommy_hashtable *hashtable, tommy_size_t bucket_max)
Initializes the hashtable.
TOMMY_API void tommy_hashtable_insert(tommy_hashtable *hashtable, tommy_hashtable_node *node, void *data, tommy_hash_t hash)
Inserts an element in the hashtable.
tommy_node tommy_hashtable_node
Hashtable node.
Definition: tommyhashtbl.h:156
TOMMY_API tommy_hashtable_node * tommy_hashtable_next(tommy_hashtable *hashtable, tommy_hashtable_node *node)
Gets the following node in iteration order, or 0 for the tail.
TOMMY_API tommy_hashtable_node * tommy_hashtable_prev(tommy_hashtable *hashtable, tommy_hashtable_node *node)
Gets the preceding node in iteration order, or 0 for the head.
TOMMY_API void * tommy_hashtable_remove_existing(tommy_hashtable *hashtable, tommy_hashtable_node *node)
Removes an element from the hashtable.
TOMMY_API void tommy_hashtable_foreach_arg(tommy_hashtable *hashtable, tommy_foreach_arg_func *func, void *arg)
Calls the specified function with an argument for each element in the hashtable.
TOMMY_API void * tommy_hashtable_remove(tommy_hashtable *hashtable, tommy_search_func *cmp, const void *cmp_arg, tommy_hash_t hash)
Searches and removes an element from the hashtable.
void tommy_hashtable_swap(tommy_hashtable *first, tommy_hashtable *second)
Exchanges the complete state of two initialized hashtables, including bucket allocations.
Definition: tommyhashtbl.h:195
TOMMY_API void tommy_hashtable_foreach(tommy_hashtable *hashtable, tommy_foreach_func *func)
Calls the specified function for each element in the hashtable.
TOMMY_API void * tommy_hashtable_insert_unique(tommy_hashtable *hashtable, tommy_hashtable_node *node, void *data, tommy_search_func *cmp, const void *cmp_arg, tommy_hash_t hash)
Inserts an element only if no equal element is already contained.
struct tommy_hashtable_struct tommy_hashtable
Hashtable container type.
tommy_size_t tommy_hashtable_count(const tommy_hashtable *hashtable)
Gets the number of elements.
Definition: tommyhashtbl.h:438
TOMMY_API tommy_hashtable_node * tommy_hashtable_tail(tommy_hashtable *hashtable)
Gets the last node in iteration order, or 0 if empty.
TOMMY_API void tommy_hashtable_clear(tommy_hashtable *hashtable)
Removes all elements, preserving the allocated buckets.
TOMMY_API void tommy_hashtable_to_list(tommy_hashtable *hashtable, tommy_list *list)
Transfers all elements from the hashtable into a tommy_list.
TOMMY_API tommy_size_t tommy_hashtable_memory_usage(const tommy_hashtable *hashtable)
Gets the size of allocated memory.
tommy_hashtable_node * tommy_hashtable_bucket(tommy_hashtable *hashtable, tommy_hash_t hash)
Gets the bucket of the specified hash.
Definition: tommyhashtbl.h:263
Doubly linked list for collisions into hashtables.
void tommy_foreach_func(void *elem)
Foreach function.
Definition: tommytypes.h:346
int tommy_search_func(const void *arg, const void *elem)
Search function for elements.
Definition: tommytypes.h:334
uint64_t tommy_size_t
Generic size_t type.
Definition: tommytypes.h:40
void tommy_foreach_arg_func(void *arg, void *elem)
Foreach function with an argument.
Definition: tommytypes.h:353
tommy_size_t tommy_hash_t
Type used in hashtables to store the hash of an element.
Definition: tommytypes.h:224
int tommy_bool_t
Generic boolean type.
Definition: tommytypes.h:53