NeoMutt  2022-04-29-249-gaae397
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.
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:43
char * mutt_str_dup(const char *str)
Copy a string, safely.
Definition: string.c:250
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{
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{
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: