NeoMutt  2021-10-29-220-g2b1eec
Teaching an old dog new tricks
DOXYGEN
hash.c File Reference

Hash Table data structure. More...

#include "config.h"
#include <ctype.h>
#include <stdbool.h>
#include "hash.h"
#include "memory.h"
#include "string2.h"
+ Include dependency graph for hash.c:

Go to the source code of this file.

Macros

#define SOME_PRIME   149711
 

Functions

static size_t gen_string_hash (union HashKey key, size_t num_elems)
 Generate a hash from a string - Implements hash_gen_hash_t -. More...
 
static int cmp_string_key (union HashKey a, union HashKey b)
 Compare two string keys - Implements hash_cmp_key_t -. More...
 
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 -. More...
 
static int cmp_case_string_key (union HashKey a, union HashKey b)
 Compare two string keys (ignore case) - Implements hash_cmp_key_t -. More...
 
static size_t gen_int_hash (union HashKey key, size_t num_elems)
 Generate a hash from an integer - Implements hash_gen_hash_t -. More...
 
static int cmp_int_key (union HashKey a, union HashKey b)
 Compare two integer keys - Implements hash_cmp_key_t -. More...
 
static struct HashTablehash_new (size_t num_elems)
 Create a new Hash Table. More...
 
static struct HashElemunion_hash_insert (struct HashTable *table, union HashKey key, int type, void *data)
 Insert into a hash table using a union as a key. More...
 
static struct HashElemunion_hash_find_elem (const struct HashTable *table, union HashKey key)
 Find a HashElem in a Hash Table element using a key. More...
 
static void * union_hash_find (const struct HashTable *table, union HashKey key)
 Find the HashElem data in a Hash Table element using a key. More...
 
static void union_hash_delete (struct HashTable *table, union HashKey key, const void *data)
 Remove an element from a Hash Table. More...
 
struct HashTablemutt_hash_new (size_t num_elems, HashFlags flags)
 Create a new Hash Table (with string keys) More...
 
struct HashTablemutt_hash_int_new (size_t num_elems, HashFlags flags)
 Create a new Hash Table (with integer keys) More...
 
void mutt_hash_set_destructor (struct HashTable *table, hash_hdata_free_t fn, intptr_t fn_data)
 Set the destructor for a Hash Table. More...
 
struct HashElemmutt_hash_typed_insert (struct HashTable *table, const char *strkey, int type, void *data)
 Insert a string with type info into a Hash Table. More...
 
struct HashElemmutt_hash_insert (struct HashTable *table, const char *strkey, void *data)
 Add a new element to the Hash Table (with string keys) More...
 
struct HashElemmutt_hash_int_insert (struct HashTable *table, unsigned int intkey, void *data)
 Add a new element to the Hash Table (with integer keys) More...
 
void * mutt_hash_find (const struct HashTable *table, const char *strkey)
 Find the HashElem data in a Hash Table element using a key. More...
 
struct HashElemmutt_hash_find_elem (const struct HashTable *table, const char *strkey)
 Find the HashElem in a Hash Table element using a key. More...
 
void * mutt_hash_int_find (const struct HashTable *table, unsigned int intkey)
 Find the HashElem data in a Hash Table element using a key. More...
 
struct HashElemmutt_hash_find_bucket (const struct HashTable *table, const char *strkey)
 Find the HashElem in a Hash Table element using a key. More...
 
void mutt_hash_delete (struct HashTable *table, const char *strkey, const void *data)
 Remove an element from a Hash Table. More...
 
void mutt_hash_int_delete (struct HashTable *table, unsigned int intkey, const void *data)
 Remove an element from a Hash Table. More...
 
void mutt_hash_free (struct HashTable **ptr)
 Free a hash table. More...
 
struct HashElemmutt_hash_walk (const struct HashTable *table, struct HashWalkState *state)
 Iterate through all the HashElem's in a Hash Table. More...
 

Detailed Description

Hash Table data structure.

Authors
  • Michael R. Elkins
  • Richard Russon

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Definition in file hash.c.

Macro Definition Documentation

◆ SOME_PRIME

#define SOME_PRIME   149711

Definition at line 37 of file hash.c.

Function Documentation

◆ hash_new()

static struct HashTable* hash_new ( size_t  num_elems)
static

Create a new Hash Table.

Parameters
num_elemsNumber of elements it should contain
Return values
ptrNew Hash Table

The Hash Table can contain more elements than num_elems, but they will be chained together.

Definition at line 121 of file hash.c.

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 }
void * mutt_mem_calloc(size_t nmemb, size_t size)
Allocate zeroed memory on the heap.
Definition: memory.c:50
The item stored in a Hash Table.
Definition: hash.h:44
A Hash Table.
Definition: hash.h:97
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:101
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:98
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ union_hash_insert()

static struct HashElem* union_hash_insert ( struct HashTable table,
union HashKey  key,
int  type,
void *  data 
)
static

Insert into a hash table using a union as a key.

Parameters
tableHash Table to update
keyKey to hash on
typeData type
dataData to associate with key
Return values
ptrNewly inserted HashElem

Definition at line 139 of file hash.c.

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 }
#define FREE(x)
Definition: memory.h:40
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
hash_gen_hash_t gen_hash
Function to generate hash id from the key.
Definition: hash.h:102
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
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ union_hash_find_elem()

static struct HashElem* union_hash_find_elem ( const struct HashTable table,
union HashKey  key 
)
static

Find a HashElem in a Hash Table element using a key.

Parameters
tableHash Table to search
keyKey (either string or integer)
Return values
ptrHashElem matching the key

Definition at line 186 of file hash.c.

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 }
+ Here is the caller graph for this function:

◆ union_hash_find()

static void* union_hash_find ( const struct HashTable table,
union HashKey  key 
)
static

Find the HashElem data in a Hash Table element using a key.

Parameters
tableHash Table to search
keyKey (either string or integer)
Return values
ptrData attached to the HashElem matching the key

Definition at line 207 of file hash.c.

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 }
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
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ union_hash_delete()

static void union_hash_delete ( struct HashTable table,
union HashKey  key,
const void *  data 
)
static

Remove an element from a Hash Table.

Parameters
tableHash Table to use
keyKey (either string or integer)
dataPrivate data to match (or NULL for any match)

Definition at line 223 of file hash.c.

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 }
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
const char * strkey
String key.
Definition: hash.h:36
+ Here is the caller graph for this function:

◆ mutt_hash_new()

struct HashTable* mutt_hash_new ( size_t  num_elems,
HashFlags  flags 
)

Create a new Hash Table (with string keys)

Parameters
num_elemsNumber of elements it should contain
flagsFlags, see HashFlags
Return values
ptrNew Hash Table

Definition at line 259 of file hash.c.

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 }
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 struct HashTable * hash_new(size_t num_elems)
Create a new Hash Table.
Definition: hash.c:121
#define MUTT_HASH_STRDUP_KEYS
make a copy of the keys
Definition: hash.h:111
#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
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ mutt_hash_int_new()

struct HashTable* mutt_hash_int_new ( size_t  num_elems,
HashFlags  flags 
)

Create a new Hash Table (with integer keys)

Parameters
num_elemsNumber of elements it should contain
flagsFlags, see HashFlags
Return values
ptrNew Hash Table

Definition at line 285 of file hash.c.

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 }
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 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
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ mutt_hash_set_destructor()

void mutt_hash_set_destructor ( struct HashTable table,
hash_hdata_free_t  fn,
intptr_t  fn_data 
)

Set the destructor for a Hash Table.

Parameters
tableHash Table to use
fnCallback function to free Hash Table's resources
fn_dataData to pass to the callback function

Definition at line 301 of file hash.c.

302 {
303  if (!table)
304  return;
305  table->hdata_free = fn;
306  table->hdata = fn_data;
307 }
+ Here is the caller graph for this function:

◆ mutt_hash_typed_insert()

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.

Parameters
tableHash Table to use
strkeyString key
typeType to associate with the key
dataPrivate data associated with the key
Return values
ptrNewly inserted HashElem

Definition at line 317 of file hash.c.

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 }
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
char * mutt_str_dup(const char *str)
Copy a string, safely.
Definition: string.c:181
The data item stored in a HashElem.
Definition: hash.h:35
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ mutt_hash_insert()

struct HashElem* mutt_hash_insert ( struct HashTable table,
const char *  strkey,
void *  data 
)

Add a new element to the Hash Table (with string keys)

Parameters
tableHash Table (with string keys)
strkeyString key
dataPrivate data associated with the key
Return values
ptrNewly inserted HashElem

Definition at line 335 of file hash.c.

336 {
337  return mutt_hash_typed_insert(table, strkey, -1, data);
338 }
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
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ mutt_hash_int_insert()

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)

Parameters
tableHash Table (with integer keys)
intkeyInteger key
dataPrivate data associated with the key
Return values
ptrNewly inserted HashElem

Definition at line 347 of file hash.c.

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 }
unsigned int intkey
Integer key.
Definition: hash.h:37
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ mutt_hash_find()

void* mutt_hash_find ( const struct HashTable table,
const char *  strkey 
)

Find the HashElem data in a Hash Table element using a key.

Parameters
tableHash Table to search
strkeyString key to search for
Return values
ptrData attached to the HashElem matching the key

Definition at line 362 of file hash.c.

363 {
364  if (!table || !strkey)
365  return NULL;
366  union HashKey key;
367  key.strkey = strkey;
368  return union_hash_find(table, key);
369 }
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
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ mutt_hash_find_elem()

struct HashElem* mutt_hash_find_elem ( const struct HashTable table,
const char *  strkey 
)

Find the HashElem in a Hash Table element using a key.

Parameters
tableHash Table to search
strkeyString key to search for
Return values
ptrHashElem matching the key

Definition at line 377 of file hash.c.

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 }
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ mutt_hash_int_find()

void* mutt_hash_int_find ( const struct HashTable table,
unsigned int  intkey 
)

Find the HashElem data in a Hash Table element using a key.

Parameters
tableHash Table to search
intkeyInteger key
Return values
ptrData attached to the HashElem matching the key

Definition at line 392 of file hash.c.

393 {
394  if (!table)
395  return NULL;
396  union HashKey key;
397  key.intkey = intkey;
398  return union_hash_find(table, key);
399 }
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ mutt_hash_find_bucket()

struct HashElem* mutt_hash_find_bucket ( const struct HashTable table,
const char *  strkey 
)

Find the HashElem in a Hash Table element using a key.

Parameters
tableHash Table to search
strkeyString key to search for
Return values
ptrHashElem matching the key

Unlike mutt_hash_find_elem(), this will return the first matching entry.

Definition at line 409 of file hash.c.

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 }
+ Here is the caller graph for this function:

◆ mutt_hash_delete()

void mutt_hash_delete ( struct HashTable table,
const char *  strkey,
const void *  data 
)

Remove an element from a Hash Table.

Parameters
tableHash Table to use
strkeyString key to match
dataPrivate data to match (or NULL for any match)

Definition at line 427 of file hash.c.

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 }
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
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ mutt_hash_int_delete()

void mutt_hash_int_delete ( struct HashTable table,
unsigned int  intkey,
const void *  data 
)

Remove an element from a Hash Table.

Parameters
tableHash Table to use
intkeyInteger key to match
dataPrivate data to match (or NULL for any match)

Definition at line 444 of file hash.c.

445 {
446  if (!table)
447  return;
448  union HashKey key;
449  key.intkey = intkey;
450  union_hash_delete(table, key, data);
451 }
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ mutt_hash_free()

void mutt_hash_free ( struct HashTable **  ptr)

Free a hash table.

Parameters
[out]ptrHash Table to be freed

Definition at line 457 of file hash.c.

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 }
+ Here is the caller graph for this function:

◆ mutt_hash_walk()

struct HashElem* mutt_hash_walk ( const struct HashTable table,
struct HashWalkState state 
)

Iterate through all the HashElem's in a Hash Table.

Parameters
tableHash Table to search
stateCursor to keep track
Return values
ptrNext HashElem in the Hash Table
NULLWhen the last HashElem has been seen

Definition at line 489 of file hash.c.

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 }
size_t index
Current position in table.
Definition: hash.h:133
struct HashElem * last
Current element in linked list.
Definition: hash.h:134
+ Here is the caller graph for this function: