NeoMutt  2021-02-05-666-ge300cd
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)
 Prototype for Hash Destructor callback function. More...
 
typedef size_t(* hash_gen_hash_t) (union HashKey key, size_t num_elems)
 Prototype for a Key hashing function. More...
 
typedef int(* hash_cmp_key_t) (union HashKey a, union HashKey b)
 Prototype for a function to compare two Hash keys. More...
 
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 100 of file hash.h.

◆ MUTT_HASH_STRCASECMP

#define MUTT_HASH_STRCASECMP   (1 << 0)

use strcasecmp() to compare keys

Definition at line 101 of file hash.h.

◆ MUTT_HASH_STRDUP_KEYS

#define MUTT_HASH_STRDUP_KEYS   (1 << 1)

make a copy of the keys

Definition at line 102 of file hash.h.

◆ MUTT_HASH_ALLOW_DUPS

#define MUTT_HASH_ALLOW_DUPS   (1 << 2)

allow duplicate keys to be inserted

Definition at line 103 of file hash.h.

Typedef Documentation

◆ hash_hdata_free_t

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

Prototype for Hash Destructor callback function.

Parameters
typeHash Type
objObject to free
dataData associated with the Hash

Contract

  • obj is not NULL

Definition at line 60 of file hash.h.

◆ hash_gen_hash_t

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

Prototype for a Key hashing function.

Parameters
keyKey to hash
num_elemsNumber of elements in the Hash Table

Turn a Key (a string or an integer) into a hash id. The hash id will be a number between 0 and (num_elems-1).

Definition at line 70 of file hash.h.

◆ hash_cmp_key_t

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

Prototype for a function to compare two Hash keys.

Parameters
aFirst key to compare
bSecond key to compare
Return values
-1a precedes b
0a and b are identical
1b precedes a

This works like strcmp().

Definition at line 82 of file hash.h.

◆ HashFlags

typedef uint8_t HashFlags

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

Definition at line 99 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 419 of file hash.c.

420 {
421  if (!table || !strkey)
422  return;
423  union HashKey key;
424  // Copy the key because union_hash_delete() may use it after the HashElem is freed.
425  key.strkey = mutt_str_dup(strkey);
426  union_hash_delete(table, key, data);
427  FREE(&key.strkey);
428 }
char * mutt_str_dup(const char *str)
Copy a string, safely.
Definition: string.c:370
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
const char * strkey
String key.
Definition: hash.h:36
#define FREE(x)
Definition: memory.h:40
The data item stored in a HashElem.
Definition: hash.h:34
+ 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 401 of file hash.c.

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 }
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:89
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:92
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:93
The data item stored in a HashElem.
Definition: hash.h:34
+ 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 354 of file hash.c.

355 {
356  if (!table || !strkey)
357  return NULL;
358  union HashKey key;
359  key.strkey = strkey;
360  return union_hash_find(table, key);
361 }
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
const char * strkey
String key.
Definition: hash.h:36
The data item stored in a HashElem.
Definition: hash.h:34
+ 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 369 of file hash.c.

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 }
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
const char * strkey
String key.
Definition: hash.h:36
The data item stored in a HashElem.
Definition: hash.h:34
+ 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 449 of file hash.c.

450 {
451  if (!ptr || !*ptr)
452  return;
453 
454  struct HashTable *table = *ptr;
455  struct HashElem *elem = NULL, *tmp = NULL;
456 
457  for (size_t i = 0; i < table->num_elems; i++)
458  {
459  for (elem = table->table[i]; elem;)
460  {
461  tmp = elem;
462  elem = elem->next;
463  if (table->hdata_free && tmp->data)
464  table->hdata_free(tmp->type, tmp->data, table->hdata);
465  if (table->strdup_keys)
466  FREE(&tmp->key.strkey);
467  FREE(&tmp);
468  }
469  }
470  FREE(&table->table);
471  FREE(ptr);
472 }
A Hash Table.
Definition: hash.h:87
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:89
struct HashElem * next
Linked List.
Definition: hash.h:48
hash_hdata_free_t hdata_free
Function to free a Hash element.
Definition: hash.h:96
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:92
intptr_t hdata
Data to pass to the hdata_free() function.
Definition: hash.h:95
bool strdup_keys
if set, the key->strkey is strdup()&#39;d
Definition: hash.h:90
#define FREE(x)
Definition: memory.h:40
The item stored in a Hash Table.
Definition: hash.h:43
+ 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 327 of file hash.c.

328 {
329  return mutt_hash_typed_insert(table, strkey, -1, data);
330 }
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
+ 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 436 of file hash.c.

437 {
438  if (!table)
439  return;
440  union HashKey key;
441  key.intkey = intkey;
442  union_hash_delete(table, key, data);
443 }
unsigned int intkey
Integer key.
Definition: hash.h:37
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
The data item stored in a HashElem.
Definition: hash.h:34
+ 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 384 of file hash.c.

385 {
386  if (!table)
387  return NULL;
388  union HashKey key;
389  key.intkey = intkey;
390  return union_hash_find(table, key);
391 }
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
The data item stored in a HashElem.
Definition: hash.h:34
+ 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 339 of file hash.c.

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 }
unsigned int intkey
Integer key.
Definition: hash.h:37
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
The data item stored in a HashElem.
Definition: hash.h:34
+ 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 277 of file hash.c.

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 }
A Hash Table.
Definition: hash.h:87
bool allow_dups
if set, duplicate keys are allowed
Definition: hash.h:91
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:89
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
#define MUTT_HASH_ALLOW_DUPS
allow duplicate keys to be inserted
Definition: hash.h:103
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:92
hash_gen_hash_t gen_hash
Function to generate hash id from the key.
Definition: hash.h:93
static struct HashTable * hash_new(size_t num_elems)
Create a new Hash Table.
Definition: hash.c:113
hash_cmp_key_t cmp_key
Function to compare two Hash keys.
Definition: hash.h:94
static int cmp_int_key(union HashKey a, union HashKey b)
Compare two integer keys - Implements hash_cmp_key_t.
Definition: hash.c:96
+ 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 251 of file hash.c.

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 }
A Hash Table.
Definition: hash.h:87
bool allow_dups
if set, duplicate keys are allowed
Definition: hash.h:91
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:89
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
static int cmp_string_key(union HashKey a, union HashKey b)
Compare two string keys - Implements hash_cmp_key_t.
Definition: hash.c:57
#define MUTT_HASH_STRCASECMP
use strcasecmp() to compare keys
Definition: hash.h:101
#define MUTT_HASH_ALLOW_DUPS
allow duplicate keys to be inserted
Definition: hash.h:103
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:92
hash_gen_hash_t gen_hash
Function to generate hash id from the key.
Definition: hash.h:93
bool strdup_keys
if set, the key->strkey is strdup()&#39;d
Definition: hash.h:90
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:102
hash_cmp_key_t cmp_key
Function to compare two Hash keys.
Definition: hash.h:94
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
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
+ 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 293 of file hash.c.

294 {
295  if (!table)
296  return;
297  table->hdata_free = fn;
298  table->hdata = fn_data;
299 }
hash_hdata_free_t hdata_free
Function to free a Hash element.
Definition: hash.h:96
intptr_t hdata
Data to pass to the hdata_free() function.
Definition: hash.h:95
+ 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 309 of file hash.c.

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 }
char * mutt_str_dup(const char *str)
Copy a string, safely.
Definition: string.c:370
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
const char * strkey
String key.
Definition: hash.h:36
bool strdup_keys
if set, the key->strkey is strdup()&#39;d
Definition: hash.h:90
The data item stored in a HashElem.
Definition: hash.h:34
+ 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 481 of file hash.c.

482 {
483  if (!table || !state)
484  return NULL;
485 
486  if (state->last && state->last->next)
487  {
488  state->last = state->last->next;
489  return state->last;
490  }
491 
492  if (state->last)
493  state->index++;
494 
495  while (state->index < table->num_elems)
496  {
497  if (table->table[state->index])
498  {
499  state->last = table->table[state->index];
500  return state->last;
501  }
502  state->index++;
503  }
504 
505  state->index = 0;
506  state->last = NULL;
507  return NULL;
508 }
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:89
struct HashElem * next
Linked List.
Definition: hash.h:48
struct HashElem * last
Current element in linked list.
Definition: hash.h:125
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:92
size_t index
Current position in table.
Definition: hash.h:124
+ Here is the caller graph for this function: