NeoMutt  2022-04-29-249-gaae397
Teaching an old dog new tricks
DOXYGEN
hash.c
Go to the documentation of this file.
1
30#include "config.h"
31#include <ctype.h>
32#include <stdbool.h>
33#include "hash.h"
34#include "memory.h"
35#include "string2.h"
36
37#define SOME_PRIME 149711
38
44static size_t gen_string_hash(union HashKey key, size_t num_elems)
45{
46 size_t hash = 0;
47 const unsigned char *s = (const unsigned char *) key.strkey;
48 if (!s)
49 return 0;
50
51 while (*s != '\0')
52 hash += ((hash << 7) + *s++);
53 hash = (hash * SOME_PRIME) % num_elems;
54
55 return hash;
56}
57
61static int cmp_string_key(union HashKey a, union HashKey b)
62{
63 return mutt_str_cmp(a.strkey, b.strkey);
64}
65
71static size_t gen_case_string_hash(union HashKey key, size_t num_elems)
72{
73 size_t hash = 0;
74 const unsigned char *s = (const unsigned char *) key.strkey;
75 if (!s)
76 return 0;
77
78 while (*s != '\0')
79 hash += ((hash << 7) + tolower(*s++));
80 hash = (hash * SOME_PRIME) % num_elems;
81
82 return hash;
83}
84
88static int cmp_case_string_key(union HashKey a, union HashKey b)
89{
90 return mutt_istr_cmp(a.strkey, b.strkey);
91}
92
96static size_t gen_int_hash(union HashKey key, size_t num_elems)
97{
98 return (key.intkey % num_elems);
99}
100
104static int cmp_int_key(union HashKey a, union HashKey b)
105{
106 if (a.intkey == b.intkey)
107 return 0;
108 if (a.intkey < b.intkey)
109 return -1;
110 return 1;
111}
112
121static struct HashTable *hash_new(size_t num_elems)
122{
123 struct HashTable *table = mutt_mem_calloc(1, sizeof(struct HashTable));
124 if (num_elems == 0)
125 num_elems = 2;
126 table->num_elems = num_elems;
127 table->table = mutt_mem_calloc(num_elems, sizeof(struct HashElem *));
128 return table;
129}
130
139static struct HashElem *union_hash_insert(struct HashTable *table,
140 union HashKey key, int type, void *data)
141{
142 if (!table)
143 return NULL; // LCOV_EXCL_LINE
144
145 struct HashElem *he = mutt_mem_calloc(1, sizeof(struct HashElem));
146 size_t hash = table->gen_hash(key, table->num_elems);
147 he->key = key;
148 he->data = data;
149 he->type = type;
150
151 if (table->allow_dups)
152 {
153 he->next = table->table[hash];
154 table->table[hash] = he;
155 }
156 else
157 {
158 struct HashElem *tmp = NULL, *last = NULL;
159
160 for (tmp = table->table[hash], last = NULL; tmp; last = tmp, tmp = tmp->next)
161 {
162 const int rc = table->cmp_key(tmp->key, key);
163 if (rc == 0)
164 {
165 FREE(&he);
166 return NULL;
167 }
168 if (rc > 0)
169 break;
170 }
171 if (last)
172 last->next = he;
173 else
174 table->table[hash] = he;
175 he->next = tmp;
176 }
177 return he;
178}
179
186static struct HashElem *union_hash_find_elem(const struct HashTable *table, union HashKey key)
187{
188 if (!table)
189 return NULL; // LCOV_EXCL_LINE
190
191 size_t hash = table->gen_hash(key, table->num_elems);
192 struct HashElem *he = table->table[hash];
193 for (; he; he = he->next)
194 {
195 if (table->cmp_key(key, he->key) == 0)
196 return he;
197 }
198 return NULL;
199}
200
207static void *union_hash_find(const struct HashTable *table, union HashKey key)
208{
209 if (!table)
210 return NULL; // LCOV_EXCL_LINE
211 struct HashElem *he = union_hash_find_elem(table, key);
212 if (he)
213 return he->data;
214 return NULL;
215}
216
223static void union_hash_delete(struct HashTable *table, union HashKey key, const void *data)
224{
225 if (!table)
226 return; // LCOV_EXCL_LINE
227
228 size_t hash = table->gen_hash(key, table->num_elems);
229 struct HashElem *he = table->table[hash];
230 struct HashElem **last = &table->table[hash];
231
232 while (he)
233 {
234 if (((data == he->data) || !data) && (table->cmp_key(he->key, key) == 0))
235 {
236 *last = he->next;
237 if (table->hdata_free)
238 table->hdata_free(he->type, he->data, table->hdata);
239 if (table->strdup_keys)
240 FREE(&he->key.strkey);
241 FREE(&he);
242
243 he = *last;
244 }
245 else
246 {
247 last = &he->next;
248 he = he->next;
249 }
250 }
251}
252
260{
262 if (flags & MUTT_HASH_STRCASECMP)
263 {
264 table->gen_hash = gen_case_string_hash;
265 table->cmp_key = cmp_case_string_key;
266 }
267 else
268 {
269 table->gen_hash = gen_string_hash;
270 table->cmp_key = cmp_string_key;
271 }
272 if (flags & MUTT_HASH_STRDUP_KEYS)
273 table->strdup_keys = true;
274 if (flags & MUTT_HASH_ALLOW_DUPS)
275 table->allow_dups = true;
276 return table;
277}
278
286{
288 table->gen_hash = gen_int_hash;
289 table->cmp_key = cmp_int_key;
290 if (flags & MUTT_HASH_ALLOW_DUPS)
291 table->allow_dups = true;
292 return table;
293}
294
302{
303 if (!table)
304 return;
305 table->hdata_free = fn;
306 table->hdata = fn_data;
307}
308
318 const char *strkey, int type, void *data)
319{
320 if (!table || !strkey)
321 return NULL;
322
323 union HashKey key;
324 key.strkey = table->strdup_keys ? mutt_str_dup(strkey) : strkey;
325 return union_hash_insert(table, key, type, data);
326}
327
335struct HashElem *mutt_hash_insert(struct HashTable *table, const char *strkey, void *data)
336{
337 return mutt_hash_typed_insert(table, strkey, -1, data);
338}
339
347struct HashElem *mutt_hash_int_insert(struct HashTable *table, unsigned int intkey, void *data)
348{
349 if (!table)
350 return NULL;
351 union HashKey key;
352 key.intkey = intkey;
353 return union_hash_insert(table, key, -1, data);
354}
355
362void *mutt_hash_find(const struct HashTable *table, const char *strkey)
363{
364 if (!table || !strkey)
365 return NULL;
366 union HashKey key;
367 key.strkey = strkey;
368 return union_hash_find(table, key);
369}
370
377struct HashElem *mutt_hash_find_elem(const struct HashTable *table, const char *strkey)
378{
379 if (!table || !strkey)
380 return NULL;
381 union HashKey key;
382 key.strkey = strkey;
383 return union_hash_find_elem(table, key);
384}
385
392void *mutt_hash_int_find(const struct HashTable *table, unsigned int intkey)
393{
394 if (!table)
395 return NULL;
396 union HashKey key;
397 key.intkey = intkey;
398 return union_hash_find(table, key);
399}
400
409struct HashElem *mutt_hash_find_bucket(const struct HashTable *table, const char *strkey)
410{
411 if (!table || !strkey)
412 return NULL;
413
414 union HashKey key;
415
416 key.strkey = strkey;
417 size_t hash = table->gen_hash(key, table->num_elems);
418 return table->table[hash];
419}
420
427void mutt_hash_delete(struct HashTable *table, const char *strkey, const void *data)
428{
429 if (!table || !strkey || (strkey[0] == '\0'))
430 return;
431 union HashKey key;
432 // Copy the key because union_hash_delete() may use it after the HashElem is freed.
434 union_hash_delete(table, key, data);
435 FREE(&key.strkey);
436}
437
444void mutt_hash_int_delete(struct HashTable *table, unsigned int intkey, const void *data)
445{
446 if (!table)
447 return;
448 union HashKey key;
449 key.intkey = intkey;
450 union_hash_delete(table, key, data);
451}
452
457void mutt_hash_free(struct HashTable **ptr)
458{
459 if (!ptr || !*ptr)
460 return;
461
462 struct HashTable *table = *ptr;
463 struct HashElem *elem = NULL, *tmp = NULL;
464
465 for (size_t i = 0; i < table->num_elems; i++)
466 {
467 for (elem = table->table[i]; elem;)
468 {
469 tmp = elem;
470 elem = elem->next;
471 if (table->hdata_free && tmp->data)
472 table->hdata_free(tmp->type, tmp->data, table->hdata);
473 if (table->strdup_keys)
474 FREE(&tmp->key.strkey);
475 FREE(&tmp);
476 }
477 }
478 FREE(&table->table);
479 FREE(ptr);
480}
481
489struct HashElem *mutt_hash_walk(const struct HashTable *table, struct HashWalkState *state)
490{
491 if (!table || !state)
492 return NULL;
493
494 if (state->last && state->last->next)
495 {
496 state->last = state->last->next;
497 return state->last;
498 }
499
500 if (state->last)
501 state->index++;
502
503 while (state->index < table->num_elems)
504 {
505 if (table->table[state->index])
506 {
507 state->last = table->table[state->index];
508 return state->last;
509 }
510 state->index++;
511 }
512
513 state->index = 0;
514 state->last = NULL;
515 return NULL;
516}
static int cmp_int_key(union HashKey a, union HashKey b)
Compare two integer keys - Implements hash_cmp_key_t -.
Definition: hash.c:104
static int cmp_case_string_key(union HashKey a, union HashKey b)
Compare two string keys (ignore case) - Implements hash_cmp_key_t -.
Definition: hash.c:88
static int cmp_string_key(union HashKey a, union HashKey b)
Compare two string keys - Implements hash_cmp_key_t -.
Definition: hash.c:61
static size_t gen_case_string_hash(union HashKey key, size_t num_elems)
Generate a hash from a string (ignore the case) - Implements hash_gen_hash_t -.
Definition: hash.c:71
static size_t gen_string_hash(union HashKey key, size_t num_elems)
Generate a hash from a string - Implements hash_gen_hash_t -.
Definition: hash.c:44
static size_t gen_int_hash(union HashKey key, size_t num_elems)
Generate a hash from an integer - Implements hash_gen_hash_t -.
Definition: hash.c:96
struct HashElem * mutt_hash_insert(struct HashTable *table, const char *strkey, void *data)
Add a new element to the Hash Table (with string keys)
Definition: hash.c:335
void mutt_hash_delete(struct HashTable *table, const char *strkey, const void *data)
Remove an element from a Hash Table.
Definition: hash.c:427
static struct HashElem * union_hash_find_elem(const struct HashTable *table, union HashKey key)
Find a HashElem in a Hash Table element using a key.
Definition: hash.c:186
void * mutt_hash_find(const struct HashTable *table, const char *strkey)
Find the HashElem data in a Hash Table element using a key.
Definition: hash.c:362
static void * union_hash_find(const struct HashTable *table, union HashKey key)
Find the HashElem data in a Hash Table element using a key.
Definition: hash.c:207
void mutt_hash_int_delete(struct HashTable *table, unsigned int intkey, const void *data)
Remove an element from a Hash Table.
Definition: hash.c:444
static struct HashElem * union_hash_insert(struct HashTable *table, union HashKey key, int type, void *data)
Insert into a hash table using a union as a key.
Definition: hash.c:139
struct HashElem * mutt_hash_find_bucket(const struct HashTable *table, const char *strkey)
Find the HashElem in a Hash Table element using a key.
Definition: hash.c:409
#define SOME_PRIME
Definition: hash.c:37
struct HashTable * mutt_hash_int_new(size_t num_elems, HashFlags flags)
Create a new Hash Table (with integer keys)
Definition: hash.c:285
struct HashElem * mutt_hash_typed_insert(struct HashTable *table, const char *strkey, int type, void *data)
Insert a string with type info into a Hash Table.
Definition: hash.c:317
struct HashElem * mutt_hash_walk(const struct HashTable *table, struct HashWalkState *state)
Iterate through all the HashElem's in a Hash Table.
Definition: hash.c:489
static struct HashTable * hash_new(size_t num_elems)
Create a new Hash Table.
Definition: hash.c:121
struct HashTable * mutt_hash_new(size_t num_elems, HashFlags flags)
Create a new Hash Table (with string keys)
Definition: hash.c:259
struct HashElem * mutt_hash_find_elem(const struct HashTable *table, const char *strkey)
Find the HashElem in a Hash Table element using a key.
Definition: hash.c:377
void mutt_hash_set_destructor(struct HashTable *table, hash_hdata_free_t fn, intptr_t fn_data)
Set the destructor for a Hash Table.
Definition: hash.c:301
void * mutt_hash_int_find(const struct HashTable *table, unsigned int intkey)
Find the HashElem data in a Hash Table element using a key.
Definition: hash.c:392
struct HashElem * mutt_hash_int_insert(struct HashTable *table, unsigned int intkey, void *data)
Add a new element to the Hash Table (with integer keys)
Definition: hash.c:347
void mutt_hash_free(struct HashTable **ptr)
Free a hash table.
Definition: hash.c:457
static void union_hash_delete(struct HashTable *table, union HashKey key, const void *data)
Remove an element from a Hash Table.
Definition: hash.c:223
Hash Table data structure.
uint8_t HashFlags
Flags for mutt_hash_new(), e.g. MUTT_HASH_STRCASECMP.
Definition: hash.h:108
#define MUTT_HASH_STRDUP_KEYS
make a copy of the keys
Definition: hash.h:111
void(* hash_hdata_free_t)(int type, void *obj, intptr_t data)
Definition: hash.h:63
#define MUTT_HASH_ALLOW_DUPS
allow duplicate keys to be inserted
Definition: hash.h:112
#define MUTT_HASH_STRCASECMP
use strcasecmp() to compare keys
Definition: hash.h:110
void * mutt_mem_calloc(size_t nmemb, size_t size)
Allocate zeroed memory on the heap.
Definition: memory.c:50
Memory management wrappers.
#define FREE(x)
Definition: memory.h:43
int mutt_str_cmp(const char *a, const char *b)
Compare two strings, safely.
Definition: string.c:470
char * mutt_str_dup(const char *str)
Copy a string, safely.
Definition: string.c:250
int mutt_istr_cmp(const char *a, const char *b)
Compare two strings ignoring case, safely.
Definition: string.c:483
String manipulation functions.
The item stored in a Hash Table.
Definition: hash.h:44
struct HashElem * next
Linked List.
Definition: hash.h:48
union HashKey key
Key representing the data.
Definition: hash.h:46
int type
Type of data stored in Hash Table, e.g. DT_STRING.
Definition: hash.h:45
void * data
User-supplied data.
Definition: hash.h:47
A Hash Table.
Definition: hash.h:97
hash_gen_hash_t gen_hash
Function to generate hash id from the key.
Definition: hash.h:102
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:101
hash_cmp_key_t cmp_key
Function to compare two Hash keys.
Definition: hash.h:103
bool allow_dups
if set, duplicate keys are allowed
Definition: hash.h:100
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:98
bool strdup_keys
if set, the key->strkey is strdup()'d
Definition: hash.h:99
intptr_t hdata
Data to pass to the hdata_free() function.
Definition: hash.h:104
hash_hdata_free_t hdata_free
Function to free a Hash element.
Definition: hash.h:105
Cursor to iterate through a Hash Table.
Definition: hash.h:132
size_t index
Current position in table.
Definition: hash.h:133
struct HashElem * last
Current element in linked list.
Definition: hash.h:134
The data item stored in a HashElem.
Definition: hash.h:35
const char * strkey
String key.
Definition: hash.h:36
unsigned int intkey
Integer key.
Definition: hash.h:37