NeoMutt  2021-10-29-225-gb9986f
Teaching an old dog new tricks
DOXYGEN
hash.h File Reference

Hash Table data structure. More...

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
+ Include dependency graph for hash.h:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

union  HashKey
 The data item stored in a HashElem. More...
 
struct  HashElem
 The item stored in a Hash Table. More...
 
struct  HashTable
 A Hash Table. More...
 
struct  HashWalkState
 Cursor to iterate through a Hash Table. More...
 

Macros

#define MUTT_HASH_NO_FLAGS   0
 No flags are set. More...
 
#define MUTT_HASH_STRCASECMP   (1 << 0)
 use strcasecmp() to compare keys More...
 
#define MUTT_HASH_STRDUP_KEYS   (1 << 1)
 make a copy of the keys More...
 
#define MUTT_HASH_ALLOW_DUPS   (1 << 2)
 allow duplicate keys to be inserted More...
 

Typedefs

typedef void(* hash_hdata_free_t) (int type, void *obj, intptr_t data)
 
typedef size_t(* hash_gen_hash_t) (union HashKey key, size_t num_elems)
 
typedef int(* hash_cmp_key_t) (union HashKey a, union HashKey b)
 
typedef uint8_t HashFlags
 Flags for mutt_hash_new(), e.g. MUTT_HASH_STRCASECMP. More...
 

Functions

void mutt_hash_delete (struct HashTable *table, const char *strkey, const void *data)
 Remove an element from a Hash Table. 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_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_free (struct HashTable **ptr)
 Free 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...
 
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_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_int_insert (struct HashTable *table, unsigned int intkey, void *data)
 Add a new element to the Hash Table (with integer keys) More...
 
struct HashTablemutt_hash_int_new (size_t num_elems, HashFlags flags)
 Create a new Hash Table (with integer keys) More...
 
struct HashTablemutt_hash_new (size_t num_elems, HashFlags flags)
 Create a new Hash Table (with string 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_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.h.

Macro Definition Documentation

◆ MUTT_HASH_NO_FLAGS

#define MUTT_HASH_NO_FLAGS   0

No flags are set.

Definition at line 109 of file hash.h.

◆ MUTT_HASH_STRCASECMP

#define MUTT_HASH_STRCASECMP   (1 << 0)

use strcasecmp() to compare keys

Definition at line 110 of file hash.h.

◆ MUTT_HASH_STRDUP_KEYS

#define MUTT_HASH_STRDUP_KEYS   (1 << 1)

make a copy of the keys

Definition at line 111 of file hash.h.

◆ MUTT_HASH_ALLOW_DUPS

#define MUTT_HASH_ALLOW_DUPS   (1 << 2)

allow duplicate keys to be inserted

Definition at line 112 of file hash.h.

Typedef Documentation

◆ hash_hdata_free_t

typedef void(* hash_hdata_free_t) (int type, void *obj, intptr_t data)

Definition at line 63 of file hash.h.

◆ hash_gen_hash_t

typedef size_t(* hash_gen_hash_t) (union HashKey key, size_t num_elems)

Definition at line 76 of file hash.h.

◆ hash_cmp_key_t

typedef int(* hash_cmp_key_t) (union HashKey a, union HashKey b)

Definition at line 91 of file hash.h.

◆ HashFlags

typedef uint8_t HashFlags

Flags for mutt_hash_new(), e.g. MUTT_HASH_STRCASECMP.

Definition at line 108 of file hash.h.

Function Documentation

◆ 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
#define FREE(x)
Definition: memory.h:40
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
const char * strkey
String key.
Definition: hash.h:36
+ 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 }
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
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:98
+ 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 }
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:

◆ 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 }
The item stored in a Hash Table.
Definition: hash.h:44
struct HashElem * next
Linked List.
Definition: hash.h:48
A Hash Table.
Definition: hash.h:97
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
+ 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_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 }
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_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_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 }
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
+ 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
static struct HashTable * hash_new(size_t num_elems)
Create a new Hash Table.
Definition: hash.c:121
#define MUTT_HASH_ALLOW_DUPS
allow duplicate keys to be inserted
Definition: hash.h:112
+ Here is the call graph for this function:
+ 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
#define MUTT_HASH_STRDUP_KEYS
make a copy of the keys
Definition: hash.h:111
#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_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 }
+ Here is the call graph for this function:
+ 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: