NeoMutt  2020-04-24
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 
45 static size_t gen_string_hash(union HashKey key, size_t n)
46 {
47  size_t h = 0;
48  const unsigned char *s = (const unsigned char *) key.strkey;
49 
50  while (*s)
51  h += ((h << 7) + *s++);
52  h = (h * SOME_PRIME) % n;
53 
54  return h;
55 }
56 
65 static int cmp_string_key(union HashKey a, union HashKey b)
66 {
67  return mutt_str_strcmp(a.strkey, b.strkey);
68 }
69 
76 static size_t gen_case_string_hash(union HashKey key, size_t n)
77 {
78  size_t h = 0;
79  const unsigned char *s = (const unsigned char *) key.strkey;
80 
81  while (*s)
82  h += ((h << 7) + tolower(*s++));
83  h = (h * SOME_PRIME) % n;
84 
85  return h;
86 }
87 
96 static int cmp_case_string_key(union HashKey a, union HashKey b)
97 {
98  return mutt_str_strcasecmp(a.strkey, b.strkey);
99 }
100 
107 static size_t gen_int_hash(union HashKey key, size_t n)
108 {
109  return key.intkey % n;
110 }
111 
120 static int cmp_int_key(union HashKey a, union HashKey b)
121 {
122  if (a.intkey == b.intkey)
123  return 0;
124  if (a.intkey < b.intkey)
125  return -1;
126  return 1;
127 }
128 
137 static struct Hash *hash_new(size_t nelem)
138 {
139  struct Hash *table = mutt_mem_calloc(1, sizeof(struct Hash));
140  if (nelem == 0)
141  nelem = 2;
142  table->nelem = nelem;
143  table->table = mutt_mem_calloc(nelem, sizeof(struct HashElem *));
144  return table;
145 }
146 
155 static struct HashElem *union_hash_insert(struct Hash *table, union HashKey key,
156  int type, void *data)
157 {
158  if (!table)
159  return NULL;
160 
161  struct HashElem *he = mutt_mem_malloc(sizeof(struct HashElem));
162  unsigned int h = table->gen_hash(key, table->nelem);
163  he->key = key;
164  he->data = data;
165  he->type = type;
166 
167  if (table->allow_dups)
168  {
169  he->next = table->table[h];
170  table->table[h] = he;
171  }
172  else
173  {
174  struct HashElem *tmp = NULL, *last = NULL;
175 
176  for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next)
177  {
178  const int r = table->cmp_key(tmp->key, key);
179  if (r == 0)
180  {
181  FREE(&he);
182  return NULL;
183  }
184  if (r > 0)
185  break;
186  }
187  if (last)
188  last->next = he;
189  else
190  table->table[h] = he;
191  he->next = tmp;
192  }
193  return he;
194 }
195 
202 static struct HashElem *union_hash_find_elem(const struct Hash *table, union HashKey key)
203 {
204  if (!table)
205  return NULL;
206 
207  int hash = table->gen_hash(key, table->nelem);
208  struct HashElem *he = table->table[hash];
209  for (; he; he = he->next)
210  {
211  if (table->cmp_key(key, he->key) == 0)
212  return he;
213  }
214  return NULL;
215 }
216 
223 static void *union_hash_find(const struct Hash *table, union HashKey key)
224 {
225  if (!table)
226  return NULL;
227  struct HashElem *he = union_hash_find_elem(table, key);
228  if (he)
229  return he->data;
230  return NULL;
231 }
232 
239 static void union_hash_delete(struct Hash *table, union HashKey key, const void *data)
240 {
241  if (!table)
242  return;
243 
244  int hash = table->gen_hash(key, table->nelem);
245  struct HashElem *he = table->table[hash];
246  struct HashElem **last = &table->table[hash];
247 
248  while (he)
249  {
250  if (((data == he->data) || !data) && (table->cmp_key(he->key, key) == 0))
251  {
252  *last = he->next;
253  if (table->free_hdata)
254  table->free_hdata(he->type, he->data, table->hdata);
255  if (table->strdup_keys)
256  FREE(&he->key.strkey);
257  FREE(&he);
258 
259  he = *last;
260  }
261  else
262  {
263  last = &he->next;
264  he = he->next;
265  }
266  }
267 }
268 
275 struct Hash *mutt_hash_new(size_t nelem, HashFlags flags)
276 {
277  struct Hash *table = hash_new(nelem);
278  if (flags & MUTT_HASH_STRCASECMP)
279  {
281  table->cmp_key = cmp_case_string_key;
282  }
283  else
284  {
285  table->gen_hash = gen_string_hash;
286  table->cmp_key = cmp_string_key;
287  }
288  if (flags & MUTT_HASH_STRDUP_KEYS)
289  table->strdup_keys = true;
290  if (flags & MUTT_HASH_ALLOW_DUPS)
291  table->allow_dups = true;
292  return table;
293 }
294 
301 struct Hash *mutt_hash_int_new(size_t nelem, HashFlags flags)
302 {
303  struct Hash *table = hash_new(nelem);
304  table->gen_hash = gen_int_hash;
305  table->cmp_key = cmp_int_key;
306  if (flags & MUTT_HASH_ALLOW_DUPS)
307  table->allow_dups = true;
308  return table;
309 }
310 
317 void mutt_hash_set_destructor(struct Hash *table, hashelem_free_t fn, intptr_t fn_data)
318 {
319  if (!table)
320  return;
321  table->free_hdata = fn;
322  table->hdata = fn_data;
323 }
324 
333 struct HashElem *mutt_hash_typed_insert(struct Hash *table, const char *strkey,
334  int type, void *data)
335 {
336  if (!table || !strkey)
337  return NULL;
338 
339  union HashKey key;
340  key.strkey = table->strdup_keys ? mutt_str_strdup(strkey) : strkey;
341  return union_hash_insert(table, key, type, data);
342 }
343 
351 struct HashElem *mutt_hash_insert(struct Hash *table, const char *strkey, void *data)
352 {
353  return mutt_hash_typed_insert(table, strkey, -1, data);
354 }
355 
363 struct HashElem *mutt_hash_int_insert(struct Hash *table, unsigned int intkey, void *data)
364 {
365  if (!table)
366  return NULL;
367  union HashKey key;
368  key.intkey = intkey;
369  return union_hash_insert(table, key, -1, data);
370 }
371 
378 void *mutt_hash_find(const struct Hash *table, const char *strkey)
379 {
380  if (!table || !strkey)
381  return NULL;
382  union HashKey key;
383  key.strkey = strkey;
384  return union_hash_find(table, key);
385 }
386 
393 struct HashElem *mutt_hash_find_elem(const struct Hash *table, const char *strkey)
394 {
395  if (!table || !strkey)
396  return NULL;
397  union HashKey key;
398  key.strkey = strkey;
399  return union_hash_find_elem(table, key);
400 }
401 
408 void *mutt_hash_int_find(const struct Hash *table, unsigned int intkey)
409 {
410  if (!table)
411  return NULL;
412  union HashKey key;
413  key.intkey = intkey;
414  return union_hash_find(table, key);
415 }
416 
425 struct HashElem *mutt_hash_find_bucket(const struct Hash *table, const char *strkey)
426 {
427  if (!table || !strkey)
428  return NULL;
429 
430  union HashKey key;
431 
432  key.strkey = strkey;
433  int hash = table->gen_hash(key, table->nelem);
434  return table->table[hash];
435 }
436 
443 void mutt_hash_delete(struct Hash *table, const char *strkey, const void *data)
444 {
445  if (!table || !strkey)
446  return;
447  union HashKey key;
448  key.strkey = strkey;
449  union_hash_delete(table, key, data);
450 }
451 
458 void mutt_hash_int_delete(struct Hash *table, unsigned int intkey, const void *data)
459 {
460  if (!table)
461  return;
462  union HashKey key;
463  key.intkey = intkey;
464  union_hash_delete(table, key, data);
465 }
466 
471 void mutt_hash_free(struct Hash **ptr)
472 {
473  if (!ptr || !*ptr)
474  return;
475 
476  struct Hash *hash = *ptr;
477  struct HashElem *elem = NULL, *tmp = NULL;
478 
479  for (size_t i = 0; i < hash->nelem; i++)
480  {
481  for (elem = hash->table[i]; elem;)
482  {
483  tmp = elem;
484  elem = elem->next;
485  if (hash->free_hdata)
486  hash->free_hdata(tmp->type, tmp->data, hash->hdata);
487  if (hash->strdup_keys)
488  FREE(&tmp->key.strkey);
489  FREE(&tmp);
490  }
491  }
492  FREE(&hash->table);
493  FREE(ptr);
494 }
495 
503 struct HashElem *mutt_hash_walk(const struct Hash *table, struct HashWalkState *state)
504 {
505  if (!table || !state)
506  return NULL;
507 
508  if (state->last && state->last->next)
509  {
510  state->last = state->last->next;
511  return state->last;
512  }
513 
514  if (state->last)
515  state->index++;
516 
517  while (state->index < table->nelem)
518  {
519  if (table->table[state->index])
520  {
521  state->last = table->table[state->index];
522  return state->last;
523  }
524  state->index++;
525  }
526 
527  state->index = 0;
528  state->last = NULL;
529  return NULL;
530 }
struct Hash * mutt_hash_int_new(size_t nelem, HashFlags flags)
Create a new Hash table (with integer keys)
Definition: hash.c:301
union HashKey key
Definition: hash.h:45
struct HashElem * mutt_hash_find_bucket(const struct Hash *table, const char *strkey)
Find the HashElem in a Hash table element using a key.
Definition: hash.c:425
void mutt_hash_delete(struct Hash *table, const char *strkey, const void *data)
Remove an element from a Hash table.
Definition: hash.c:443
void * mutt_mem_calloc(size_t nmemb, size_t size)
Allocate zeroed memory on the heap.
Definition: memory.c:50
Memory management wrappers.
A Hash Table.
Definition: hash.h:61
hashelem_free_t free_hdata
Function to free a Hash element.
Definition: hash.h:70
void(* hashelem_free_t)(int type, void *obj, intptr_t data)
Prototype for Hash Destructor callback function.
Definition: hash.h:56
Cursor to iterate through a Hash Table.
Definition: hash.h:96
void * mutt_hash_find(const struct Hash *table, const char *strkey)
Find the HashElem data in a Hash table element using a key.
Definition: hash.c:378
static struct Hash * hash_new(size_t nelem)
Create a new Hash table.
Definition: hash.c:137
static int cmp_case_string_key(union HashKey a, union HashKey b)
Compare two string keys (ignore case) - Implements Hash::cmp_key()
Definition: hash.c:96
Hash table data structure.
intptr_t hdata
Data to pass to the free_hdata() function.
Definition: hash.h:69
void * mutt_hash_int_find(const struct Hash *table, unsigned int intkey)
Find the HashElem data in a Hash table element using a key.
Definition: hash.c:408
struct HashElem * next
Definition: hash.h:47
String manipulation functions.
static int cmp_string_key(union HashKey a, union HashKey b)
Compare two string keys - Implements Hash::cmp_key()
Definition: hash.c:65
static struct HashElem * union_hash_find_elem(const struct Hash *table, union HashKey key)
Find a HashElem in a Hash table element using a key.
Definition: hash.c:202
struct HashElem * last
Definition: hash.h:99
#define MUTT_HASH_STRCASECMP
use strcasecmp() to compare keys
Definition: hash.h:75
while(1)
Definition: acutest.h:731
unsigned int intkey
Definition: hash.h:36
struct HashElem * mutt_hash_find_elem(const struct Hash *table, const char *strkey)
Find the HashElem in a Hash table element using a key.
Definition: hash.c:393
int(* cmp_key)(union HashKey, union HashKey)
Function to compare two Hash keys.
Definition: hash.h:68
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:66
#define MUTT_HASH_ALLOW_DUPS
allow duplicate keys to be inserted
Definition: hash.h:77
static size_t gen_int_hash(union HashKey key, size_t n)
Generate a hash from an integer - Implements Hash::gen_hash()
Definition: hash.c:107
size_t nelem
Number of elements in the Hash table.
Definition: hash.h:63
void * mutt_mem_malloc(size_t size)
Allocate memory on the heap.
Definition: memory.c:90
struct Hash * mutt_hash_new(size_t nelem, HashFlags flags)
Create a new Hash table (with string keys)
Definition: hash.c:275
bool allow_dups
if set, duplicate keys are allowed
Definition: hash.h:65
static struct HashElem * union_hash_insert(struct Hash *table, union HashKey key, int type, void *data)
Insert into a hash table using a union as a key.
Definition: hash.c:155
size_t index
Definition: hash.h:98
void * data
Definition: hash.h:46
struct HashElem * mutt_hash_walk(const struct Hash *table, struct HashWalkState *state)
Iterate through all the HashElem&#39;s in a Hash table.
Definition: hash.c:503
int n
Definition: acutest.h:492
char * mutt_str_strdup(const char *str)
Copy a string, safely.
Definition: string.c:380
const char * strkey
Definition: hash.h:35
int mutt_str_strcasecmp(const char *a, const char *b)
Compare two strings ignoring case, safely.
Definition: string.c:654
int type
Definition: hash.h:44
#define FREE(x)
Definition: memory.h:40
bool strdup_keys
if set, the key->strkey is strdup&#39;ed
Definition: hash.h:64
static size_t gen_string_hash(union HashKey key, size_t n)
Generate a hash from a string - Implements Hash::gen_hash()
Definition: hash.c:45
void mutt_hash_int_delete(struct Hash *table, unsigned int intkey, const void *data)
Remove an element from a Hash table.
Definition: hash.c:458
uint8_t HashFlags
Flags for mutt_hash_new(), e.g. MUTT_HASH_STRCASECMP.
Definition: hash.h:73
The item stored in a Hash Table.
Definition: hash.h:42
static size_t gen_case_string_hash(union HashKey key, size_t n)
Generate a hash from a string (ignore the case) - Implements Hash::gen_hash()
Definition: hash.c:76
void mutt_hash_set_destructor(struct Hash *table, hashelem_free_t fn, intptr_t fn_data)
Set the destructor for a Hash Table.
Definition: hash.c:317
static void * union_hash_find(const struct Hash *table, union HashKey key)
Find the HashElem data in a Hash table element using a key.
Definition: hash.c:223
#define MUTT_HASH_STRDUP_KEYS
make a copy of the keys
Definition: hash.h:76
void mutt_hash_free(struct Hash **ptr)
Free a hash table.
Definition: hash.c:471
struct HashElem * mutt_hash_insert(struct Hash *table, const char *strkey, void *data)
Add a new element to the Hash table (with string keys)
Definition: hash.c:351
size_t(* gen_hash)(union HashKey, size_t)
Function to generate hash id from the key.
Definition: hash.h:67
#define SOME_PRIME
Definition: hash.c:37
int mutt_str_strcmp(const char *a, const char *b)
Compare two strings, safely.
Definition: string.c:641
The data item stored in a HashElem.
Definition: hash.h:34
static void union_hash_delete(struct Hash *table, union HashKey key, const void *data)
Remove an element from a Hash table.
Definition: hash.c:239
struct HashElem * mutt_hash_int_insert(struct Hash *table, unsigned int intkey, void *data)
Add a new element to the Hash table (with integer keys)
Definition: hash.c:363
static int cmp_int_key(union HashKey a, union HashKey b)
Compare two integer keys - Implements Hash::cmp_key()
Definition: hash.c:120
struct HashElem * mutt_hash_typed_insert(struct Hash *table, const char *strkey, int type, void *data)
Insert a string with type info into a Hash Table.
Definition: hash.c:333