NeoMutt  2020-08-07-1-gab41a1
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 
42 static size_t gen_string_hash(union HashKey key, size_t num_elems)
43 {
44  size_t hash = 0;
45  const unsigned char *s = (const unsigned char *) key.strkey;
46 
47  while (*s != '\0')
48  hash += ((hash << 7) + *s++);
49  hash = (hash * SOME_PRIME) % num_elems;
50 
51  return hash;
52 }
53 
57 static int cmp_string_key(union HashKey a, union HashKey b)
58 {
59  return mutt_str_cmp(a.strkey, b.strkey);
60 }
61 
65 static size_t gen_case_string_hash(union HashKey key, size_t num_elems)
66 {
67  size_t hash = 0;
68  const unsigned char *s = (const unsigned char *) key.strkey;
69 
70  while (*s != '\0')
71  hash += ((hash << 7) + tolower(*s++));
72  hash = (hash * SOME_PRIME) % num_elems;
73 
74  return hash;
75 }
76 
80 static int cmp_case_string_key(union HashKey a, union HashKey b)
81 {
82  return mutt_istr_cmp(a.strkey, b.strkey);
83 }
84 
88 static size_t gen_int_hash(union HashKey key, size_t num_elems)
89 {
90  return (key.intkey % num_elems);
91 }
92 
96 static int cmp_int_key(union HashKey a, union HashKey b)
97 {
98  if (a.intkey == b.intkey)
99  return 0;
100  if (a.intkey < b.intkey)
101  return -1;
102  return 1;
103 }
104 
113 static struct HashTable *hash_new(size_t num_elems)
114 {
115  struct HashTable *table = mutt_mem_calloc(1, sizeof(struct HashTable));
116  if (num_elems == 0)
117  num_elems = 2;
118  table->num_elems = num_elems;
119  table->table = mutt_mem_calloc(num_elems, sizeof(struct HashElem *));
120  return table;
121 }
122 
131 static struct HashElem *union_hash_insert(struct HashTable *table,
132  union HashKey key, int type, void *data)
133 {
134  if (!table)
135  return NULL; // LCOV_EXCL_LINE
136 
137  struct HashElem *he = mutt_mem_calloc(1, sizeof(struct HashElem));
138  size_t hash = table->gen_hash(key, table->num_elems);
139  he->key = key;
140  he->data = data;
141  he->type = type;
142 
143  if (table->allow_dups)
144  {
145  he->next = table->table[hash];
146  table->table[hash] = he;
147  }
148  else
149  {
150  struct HashElem *tmp = NULL, *last = NULL;
151 
152  for (tmp = table->table[hash], last = NULL; tmp; last = tmp, tmp = tmp->next)
153  {
154  const int rc = table->cmp_key(tmp->key, key);
155  if (rc == 0)
156  {
157  FREE(&he);
158  return NULL;
159  }
160  if (rc > 0)
161  break;
162  }
163  if (last)
164  last->next = he;
165  else
166  table->table[hash] = he;
167  he->next = tmp;
168  }
169  return he;
170 }
171 
178 static struct HashElem *union_hash_find_elem(const struct HashTable *table, union HashKey key)
179 {
180  if (!table)
181  return NULL; // LCOV_EXCL_LINE
182 
183  size_t hash = table->gen_hash(key, table->num_elems);
184  struct HashElem *he = table->table[hash];
185  for (; he; he = he->next)
186  {
187  if (table->cmp_key(key, he->key) == 0)
188  return he;
189  }
190  return NULL;
191 }
192 
199 static void *union_hash_find(const struct HashTable *table, union HashKey key)
200 {
201  if (!table)
202  return NULL; // LCOV_EXCL_LINE
203  struct HashElem *he = union_hash_find_elem(table, key);
204  if (he)
205  return he->data;
206  return NULL;
207 }
208 
215 static void union_hash_delete(struct HashTable *table, union HashKey key, const void *data)
216 {
217  if (!table)
218  return; // LCOV_EXCL_LINE
219 
220  size_t hash = table->gen_hash(key, table->num_elems);
221  struct HashElem *he = table->table[hash];
222  struct HashElem **last = &table->table[hash];
223 
224  while (he)
225  {
226  if (((data == he->data) || !data) && (table->cmp_key(he->key, key) == 0))
227  {
228  *last = he->next;
229  if (table->hdata_free)
230  table->hdata_free(he->type, he->data, table->hdata);
231  if (table->strdup_keys)
232  FREE(&he->key.strkey);
233  FREE(&he);
234 
235  he = *last;
236  }
237  else
238  {
239  last = &he->next;
240  he = he->next;
241  }
242  }
243 }
244 
252 {
253  struct HashTable *table = hash_new(num_elems);
254  if (flags & MUTT_HASH_STRCASECMP)
255  {
257  table->cmp_key = cmp_case_string_key;
258  }
259  else
260  {
261  table->gen_hash = gen_string_hash;
262  table->cmp_key = cmp_string_key;
263  }
264  if (flags & MUTT_HASH_STRDUP_KEYS)
265  table->strdup_keys = true;
266  if (flags & MUTT_HASH_ALLOW_DUPS)
267  table->allow_dups = true;
268  return table;
269 }
270 
278 {
279  struct HashTable *table = hash_new(num_elems);
280  table->gen_hash = gen_int_hash;
281  table->cmp_key = cmp_int_key;
282  if (flags & MUTT_HASH_ALLOW_DUPS)
283  table->allow_dups = true;
284  return table;
285 }
286 
293 void mutt_hash_set_destructor(struct HashTable *table, hash_hdata_free_t fn, intptr_t fn_data)
294 {
295  if (!table)
296  return;
297  table->hdata_free = fn;
298  table->hdata = fn_data;
299 }
300 
310  const char *strkey, int type, void *data)
311 {
312  if (!table || !strkey)
313  return NULL;
314 
315  union HashKey key;
316  key.strkey = table->strdup_keys ? mutt_str_dup(strkey) : strkey;
317  return union_hash_insert(table, key, type, data);
318 }
319 
327 struct HashElem *mutt_hash_insert(struct HashTable *table, const char *strkey, void *data)
328 {
329  return mutt_hash_typed_insert(table, strkey, -1, data);
330 }
331 
339 struct HashElem *mutt_hash_int_insert(struct HashTable *table, unsigned int intkey, void *data)
340 {
341  if (!table)
342  return NULL;
343  union HashKey key;
344  key.intkey = intkey;
345  return union_hash_insert(table, key, -1, data);
346 }
347 
354 void *mutt_hash_find(const struct HashTable *table, const char *strkey)
355 {
356  if (!table || !strkey)
357  return NULL;
358  union HashKey key;
359  key.strkey = strkey;
360  return union_hash_find(table, key);
361 }
362 
369 struct HashElem *mutt_hash_find_elem(const struct HashTable *table, const char *strkey)
370 {
371  if (!table || !strkey)
372  return NULL;
373  union HashKey key;
374  key.strkey = strkey;
375  return union_hash_find_elem(table, key);
376 }
377 
384 void *mutt_hash_int_find(const struct HashTable *table, unsigned int intkey)
385 {
386  if (!table)
387  return NULL;
388  union HashKey key;
389  key.intkey = intkey;
390  return union_hash_find(table, key);
391 }
392 
401 struct HashElem *mutt_hash_find_bucket(const struct HashTable *table, const char *strkey)
402 {
403  if (!table || !strkey)
404  return NULL;
405 
406  union HashKey key;
407 
408  key.strkey = strkey;
409  size_t hash = table->gen_hash(key, table->num_elems);
410  return table->table[hash];
411 }
412 
419 void mutt_hash_delete(struct HashTable *table, const char *strkey, const void *data)
420 {
421  if (!table || !strkey)
422  return;
423  union HashKey key;
424  key.strkey = strkey;
425  union_hash_delete(table, key, data);
426 }
427 
434 void mutt_hash_int_delete(struct HashTable *table, unsigned int intkey, const void *data)
435 {
436  if (!table)
437  return;
438  union HashKey key;
439  key.intkey = intkey;
440  union_hash_delete(table, key, data);
441 }
442 
447 void mutt_hash_free(struct HashTable **ptr)
448 {
449  if (!ptr || !*ptr)
450  return;
451 
452  struct HashTable *table = *ptr;
453  struct HashElem *elem = NULL, *tmp = NULL;
454 
455  for (size_t i = 0; i < table->num_elems; i++)
456  {
457  for (elem = table->table[i]; elem;)
458  {
459  tmp = elem;
460  elem = elem->next;
461  if (table->hdata_free)
462  table->hdata_free(tmp->type, tmp->data, table->hdata);
463  if (table->strdup_keys)
464  FREE(&tmp->key.strkey);
465  FREE(&tmp);
466  }
467  }
468  FREE(&table->table);
469  FREE(ptr);
470 }
471 
479 struct HashElem *mutt_hash_walk(const struct HashTable *table, struct HashWalkState *state)
480 {
481  if (!table || !state)
482  return NULL;
483 
484  if (state->last && state->last->next)
485  {
486  state->last = state->last->next;
487  return state->last;
488  }
489 
490  if (state->last)
491  state->index++;
492 
493  while (state->index < table->num_elems)
494  {
495  if (table->table[state->index])
496  {
497  state->last = table->table[state->index];
498  return state->last;
499  }
500  state->index++;
501  }
502 
503  state->index = 0;
504  state->last = NULL;
505  return NULL;
506 }
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:178
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:354
int mutt_istr_cmp(const char *a, const char *b)
Compare two strings ignoring case, safely.
Definition: string.c:585
union HashKey key
Key representing the data.
Definition: hash.h:46
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:327
int mutt_str_cmp(const char *a, const char *b)
Compare two strings, safely.
Definition: string.c:572
void * mutt_mem_calloc(size_t nmemb, size_t size)
Allocate zeroed memory on the heap.
Definition: memory.c:50
A Hash Table.
Definition: hash.h:84
Memory management wrappers.
bool allow_dups
if set, duplicate keys are allowed
Definition: hash.h:88
void mutt_hash_free(struct HashTable **ptr)
Free a hash table.
Definition: hash.c:447
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:86
Cursor to iterate through a Hash Table.
Definition: hash.h:119
void(* hash_hdata_free_t)(int type, void *obj, intptr_t data)
Prototype for Hash Destructor callback function.
Definition: hash.h:57
char * mutt_str_dup(const char *str)
Copy a string, safely.
Definition: string.c:375
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:80
Hash Table data structure.
struct HashTable * mutt_hash_int_new(size_t num_elems, HashFlags flags)
Create a new Hash Table (with integer keys)
Definition: hash.c:277
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:384
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:339
struct HashElem * next
Linked List.
Definition: hash.h:48
String manipulation functions.
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:369
static int cmp_string_key(union HashKey a, union HashKey b)
Compare two string keys - Implements hash_cmp_key_t.
Definition: hash.c:57
struct HashElem * last
Current element in linked list.
Definition: hash.h:122
#define MUTT_HASH_STRCASECMP
use strcasecmp() to compare keys
Definition: hash.h:98
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:88
while(1)
Definition: acutest.h:731
unsigned int intkey
Integer key.
Definition: hash.h:37
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:199
hash_hdata_free_t hdata_free
Function to free a Hash element.
Definition: hash.h:93
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:131
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:293
#define MUTT_HASH_ALLOW_DUPS
allow duplicate keys to be inserted
Definition: hash.h:100
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:89
void mutt_hash_int_delete(struct HashTable *table, unsigned int intkey, const void *data)
Remove an element from a Hash Table.
Definition: hash.c:434
intptr_t hdata
Data to pass to the hdata_free() function.
Definition: hash.h:92
static void union_hash_delete(struct HashTable *table, union HashKey key, const void *data)
Remove an element from a Hash Table.
Definition: hash.c:215
size_t index
Current position in table.
Definition: hash.h:121
void * data
User-supplied data.
Definition: hash.h:47
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:309
const char * strkey
String key.
Definition: hash.h:36
hash_gen_hash_t gen_hash
Function to generate hash id from the key.
Definition: hash.h:90
bool strdup_keys
if set, the key->strkey is strdup()&#39;d
Definition: hash.h:87
int type
Type of data stored in Hash Table, e.g. DT_STRING.
Definition: hash.h:45
#define FREE(x)
Definition: memory.h:40
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:401
struct HashElem * mutt_hash_walk(const struct HashTable *table, struct HashWalkState *state)
Iterate through all the HashElem&#39;s in a Hash Table.
Definition: hash.c:479
void mutt_hash_delete(struct HashTable *table, const char *strkey, const void *data)
Remove an element from a Hash Table.
Definition: hash.c:419
uint8_t HashFlags
Flags for mutt_hash_new(), e.g. MUTT_HASH_STRCASECMP.
Definition: hash.h:96
The item stored in a Hash Table.
Definition: hash.h:43
static struct HashTable * hash_new(size_t num_elems)
Create a new Hash Table.
Definition: hash.c:113
#define MUTT_HASH_STRDUP_KEYS
make a copy of the keys
Definition: hash.h:99
hash_cmp_key_t cmp_key
Function to compare two Hash keys.
Definition: hash.h:91
struct HashTable * mutt_hash_new(size_t num_elems, HashFlags flags)
Create a new Hash Table (with string keys)
Definition: hash.c:251
#define SOME_PRIME
Definition: hash.c:37
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:42
The data item stored in a HashElem.
Definition: hash.h:34
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:65
static int cmp_int_key(union HashKey a, union HashKey b)
Compare two integer keys - Implements hash_cmp_key_t.
Definition: hash.c:96