NeoMutt  2022-04-29-145-g9b6a0e
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 
44 static 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 
61 static int cmp_string_key(union HashKey a, union HashKey b)
62 {
63  return mutt_str_cmp(a.strkey, b.strkey);
64 }
65 
71 static 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 
88 static int cmp_case_string_key(union HashKey a, union HashKey b)
89 {
90  return mutt_istr_cmp(a.strkey, b.strkey);
91 }
92 
96 static size_t gen_int_hash(union HashKey key, size_t num_elems)
97 {
98  return (key.intkey % num_elems);
99 }
100 
104 static 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 
121 static 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 
139 static 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 
186 static 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 
207 static 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 
223 static 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 {
261  struct HashTable *table = hash_new(num_elems);
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 {
287  struct HashTable *table = hash_new(num_elems);
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 
301 void mutt_hash_set_destructor(struct HashTable *table, hash_hdata_free_t fn, intptr_t fn_data)
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 
335 struct 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 
347 struct 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 
362 void *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 
377 struct 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 
392 void *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 
409 struct 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 
427 void 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.
433  key.strkey = mutt_str_dup(strkey);
434  union_hash_delete(table, key, data);
435  FREE(&key.strkey);
436 }
437 
444 void 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 
457 void 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 
489 struct 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
void mutt_hash_delete(struct HashTable *table, const char *strkey, const void *data)
Remove an element from a Hash Table.
Definition: hash.c:427
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
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
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
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
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
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
#define SOME_PRIME
Definition: hash.c:37
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
struct HashTable * mutt_hash_int_new(size_t num_elems, HashFlags flags)
Create a new Hash Table (with integer keys)
Definition: hash.c:285
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_walk(const struct HashTable *table, struct HashWalkState *state)
Iterate through all the HashElem's in a Hash Table.
Definition: hash.c:489
struct HashTable * mutt_hash_new(size_t num_elems, HashFlags flags)
Create a new Hash Table (with string keys)
Definition: hash.c:259
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
static struct HashTable * hash_new(size_t num_elems)
Create a new Hash Table.
Definition: hash.c:121
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
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_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:447
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:460
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