NeoMutt  2020-06-26-89-g172cd3
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 97 of file hash.h.

◆ MUTT_HASH_STRCASECMP

#define MUTT_HASH_STRCASECMP   (1 << 0)

use strcasecmp() to compare keys

Definition at line 98 of file hash.h.

◆ MUTT_HASH_STRDUP_KEYS

#define MUTT_HASH_STRDUP_KEYS   (1 << 1)

make a copy of the keys

Definition at line 99 of file hash.h.

◆ MUTT_HASH_ALLOW_DUPS

#define MUTT_HASH_ALLOW_DUPS   (1 << 2)

allow duplicate keys to be inserted

Definition at line 100 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

Definition at line 57 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 67 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 79 of file hash.h.

◆ HashFlags

typedef uint8_t HashFlags

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

Definition at line 96 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  key.strkey = strkey;
425  union_hash_delete(table, key, data);
426 }
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
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:86
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:89
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:90
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 447 of file hash.c.

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

435 {
436  if (!table)
437  return;
438  union HashKey key;
439  key.intkey = intkey;
440  union_hash_delete(table, key, data);
441 }
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:84
bool allow_dups
if set, duplicate keys are allowed
Definition: hash.h:88
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:86
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:100
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:89
hash_gen_hash_t gen_hash
Function to generate hash id from the key.
Definition: hash.h:90
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:91
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:84
bool allow_dups
if set, duplicate keys are allowed
Definition: hash.h:88
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:86
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:98
#define MUTT_HASH_ALLOW_DUPS
allow duplicate keys to be inserted
Definition: hash.h:100
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:89
hash_gen_hash_t gen_hash
Function to generate hash id from the key.
Definition: hash.h:90
bool strdup_keys
if set, the key->strkey is strdup()&#39;d
Definition: hash.h:87
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:99
hash_cmp_key_t cmp_key
Function to compare two Hash keys.
Definition: hash.h:91
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:93
intptr_t hdata
Data to pass to the hdata_free() function.
Definition: hash.h:92
+ 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:375
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:87
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 479 of file hash.c.

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