NeoMutt  2019-12-07
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  Hash
 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(* hashelem_free_t) (int type, void *obj, intptr_t data)
 typedef hashelem_free_t - Prototype for Hash Destructor callback function More...
 
typedef uint8_t HashFlags
 Flags for mutt_hash_new(), e.g. MUTT_HASH_STRCASECMP. More...
 

Functions

void mutt_hash_delete (struct Hash *table, const char *strkey, const void *data)
 Remove an element from a Hash table. More...
 
struct HashElemmutt_hash_find_bucket (const struct Hash *table, const char *strkey)
 Find the HashElem in a Hash table element using a key. More...
 
void * mutt_hash_find (const struct Hash *table, const char *strkey)
 Find the HashElem data in a Hash table element using a key. More...
 
struct HashElemmutt_hash_find_elem (const struct Hash *table, const char *strkey)
 Find the HashElem in a Hash table element using a key. More...
 
void mutt_hash_free (struct Hash **ptr)
 Free a hash table. More...
 
struct HashElemmutt_hash_insert (struct Hash *table, const char *strkey, void *data)
 Add a new element to the Hash table (with string keys) More...
 
void mutt_hash_int_delete (struct Hash *table, unsigned int intkey, const void *data)
 Remove an element from a Hash table. More...
 
void * mutt_hash_int_find (const struct Hash *table, unsigned int intkey)
 Find the HashElem data in a Hash table element using a key. More...
 
struct HashElemmutt_hash_int_insert (struct Hash *table, unsigned int intkey, void *data)
 Add a new element to the Hash table (with integer keys) More...
 
struct Hashmutt_hash_int_new (size_t nelem, HashFlags flags)
 Create a new Hash table (with integer keys) More...
 
struct Hashmutt_hash_new (size_t nelem, HashFlags flags)
 Create a new Hash table (with string keys) More...
 
void mutt_hash_set_destructor (struct Hash *table, hashelem_free_t fn, intptr_t fn_data)
 Set the destructor for a Hash Table. More...
 
struct HashElemmutt_hash_typed_insert (struct Hash *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 Hash *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 74 of file hash.h.

◆ MUTT_HASH_STRCASECMP

#define MUTT_HASH_STRCASECMP   (1 << 0)

use strcasecmp() to compare keys

Definition at line 75 of file hash.h.

◆ MUTT_HASH_STRDUP_KEYS

#define MUTT_HASH_STRDUP_KEYS   (1 << 1)

make a copy of the keys

Definition at line 76 of file hash.h.

◆ MUTT_HASH_ALLOW_DUPS

#define MUTT_HASH_ALLOW_DUPS   (1 << 2)

allow duplicate keys to be inserted

Definition at line 77 of file hash.h.

Typedef Documentation

◆ hashelem_free_t

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

typedef hashelem_free_t - Prototype for Hash Destructor callback function

Parameters
typeHash Type
objObject to free
dataData associated with the Hash

Definition at line 56 of file hash.h.

◆ HashFlags

typedef uint8_t HashFlags

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

Definition at line 73 of file hash.h.

Function Documentation

◆ mutt_hash_delete()

void mutt_hash_delete ( struct Hash 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 443 of file hash.c.

444 {
445  if (!table || !strkey)
446  return;
447  union HashKey key;
448  key.strkey = strkey;
449  union_hash_delete(table, key, data);
450 }
const char * strkey
Definition: hash.h:35
The data item stored in a HashElem.
Definition: hash.h:34
static void union_hash_delete(struct Hash *table, union HashKey key, const void *data)
Remove an element from a Hash table.
Definition: hash.c:239
+ 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 Hash 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 425 of file hash.c.

426 {
427  if (!table || !strkey)
428  return NULL;
429 
430  union HashKey key;
431 
432  key.strkey = strkey;
433  int hash = table->gen_hash(key, table->nelem);
434  return table->table[hash];
435 }
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:66
size_t nelem
Number of elements in the Hash table.
Definition: hash.h:63
const char * strkey
Definition: hash.h:35
size_t(* gen_hash)(union HashKey, size_t)
Function to generate hash id from the key.
Definition: hash.h:67
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 Hash 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 378 of file hash.c.

379 {
380  if (!table || !strkey)
381  return NULL;
382  union HashKey key;
383  key.strkey = strkey;
384  return union_hash_find(table, key);
385 }
const char * strkey
Definition: hash.h:35
static void * union_hash_find(const struct Hash *table, union HashKey key)
Find the HashElem data in a Hash table element using a key.
Definition: hash.c:223
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 Hash 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 393 of file hash.c.

394 {
395  if (!table || !strkey)
396  return NULL;
397  union HashKey key;
398  key.strkey = strkey;
399  return union_hash_find_elem(table, key);
400 }
static struct HashElem * union_hash_find_elem(const struct Hash *table, union HashKey key)
Find a HashElem in a Hash table element using a key.
Definition: hash.c:202
const char * strkey
Definition: hash.h:35
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 Hash **  ptr)

Free a hash table.

Parameters
[out]ptrHash Table to be freed

Definition at line 471 of file hash.c.

472 {
473  if (!ptr || !*ptr)
474  return;
475 
476  struct Hash *hash = *ptr;
477  struct HashElem *elem = NULL, *tmp = NULL;
478 
479  for (size_t i = 0; i < hash->nelem; i++)
480  {
481  for (elem = hash->table[i]; elem;)
482  {
483  tmp = elem;
484  elem = elem->next;
485  if (hash->free_hdata)
486  hash->free_hdata(tmp->type, tmp->data, hash->hdata);
487  if (hash->strdup_keys)
488  FREE(&tmp->key.strkey);
489  FREE(&tmp);
490  }
491  }
492  FREE(&hash->table);
493  FREE(ptr);
494 }
A Hash Table.
Definition: hash.h:61
hashelem_free_t free_hdata
Function to free a Hash element.
Definition: hash.h:70
intptr_t hdata
Data to pass to the free_hdata() function.
Definition: hash.h:69
struct HashElem * next
Definition: hash.h:47
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:66
size_t nelem
Number of elements in the Hash table.
Definition: hash.h:63
#define FREE(x)
Definition: memory.h:40
bool strdup_keys
if set, the key->strkey is strdup&#39;ed
Definition: hash.h:64
The item stored in a Hash Table.
Definition: hash.h:42
+ Here is the caller graph for this function:

◆ mutt_hash_insert()

struct HashElem* mutt_hash_insert ( struct Hash 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 351 of file hash.c.

352 {
353  return mutt_hash_typed_insert(table, strkey, -1, data);
354 }
void * data
Definition: hash.h:46
struct HashElem * mutt_hash_typed_insert(struct Hash *table, const char *strkey, int type, void *data)
Insert a string with type info into a Hash Table.
Definition: hash.c:333
+ 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 Hash 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 458 of file hash.c.

459 {
460  if (!table)
461  return;
462  union HashKey key;
463  key.intkey = intkey;
464  union_hash_delete(table, key, data);
465 }
unsigned int intkey
Definition: hash.h:36
The data item stored in a HashElem.
Definition: hash.h:34
static void union_hash_delete(struct Hash *table, union HashKey key, const void *data)
Remove an element from a Hash table.
Definition: hash.c:239
+ 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 Hash 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 408 of file hash.c.

409 {
410  if (!table)
411  return NULL;
412  union HashKey key;
413  key.intkey = intkey;
414  return union_hash_find(table, key);
415 }
unsigned int intkey
Definition: hash.h:36
static void * union_hash_find(const struct Hash *table, union HashKey key)
Find the HashElem data in a Hash table element using a key.
Definition: hash.c:223
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 Hash 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 363 of file hash.c.

364 {
365  if (!table)
366  return NULL;
367  union HashKey key;
368  key.intkey = intkey;
369  return union_hash_insert(table, key, -1, data);
370 }
unsigned int intkey
Definition: hash.h:36
static struct HashElem * union_hash_insert(struct Hash *table, union HashKey key, int type, void *data)
Insert into a hash table using a union as a key.
Definition: hash.c:155
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 Hash* mutt_hash_int_new ( size_t  nelem,
HashFlags  flags 
)

Create a new Hash table (with integer keys)

Parameters
nelemNumber of elements it should contain
flagsFlags, see HashFlags
Return values
ptrNew Hash table

Definition at line 301 of file hash.c.

302 {
303  struct Hash *table = hash_new(nelem);
304  table->gen_hash = gen_int_hash;
305  table->cmp_key = cmp_int_key;
306  if (flags & MUTT_HASH_ALLOW_DUPS)
307  table->allow_dups = true;
308  return table;
309 }
A Hash Table.
Definition: hash.h:61
static struct Hash * hash_new(size_t nelem)
Create a new Hash table.
Definition: hash.c:137
int(* cmp_key)(union HashKey, union HashKey)
Function to compare two Hash keys.
Definition: hash.h:68
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:66
#define MUTT_HASH_ALLOW_DUPS
allow duplicate keys to be inserted
Definition: hash.h:77
static size_t gen_int_hash(union HashKey key, size_t n)
Generate a hash from an integer.
Definition: hash.c:107
size_t nelem
Number of elements in the Hash table.
Definition: hash.h:63
bool allow_dups
if set, duplicate keys are allowed
Definition: hash.h:65
size_t(* gen_hash)(union HashKey, size_t)
Function to generate hash id from the key.
Definition: hash.h:67
static int cmp_int_key(union HashKey a, union HashKey b)
Compare two integer keys.
Definition: hash.c:120
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ mutt_hash_new()

struct Hash* mutt_hash_new ( size_t  nelem,
HashFlags  flags 
)

Create a new Hash table (with string keys)

Parameters
nelemNumber of elements it should contain
flagsFlags, see HashFlags
Return values
ptrNew Hash table

Definition at line 275 of file hash.c.

276 {
277  struct Hash *table = hash_new(nelem);
278  if (flags & MUTT_HASH_STRCASECMP)
279  {
281  table->cmp_key = cmp_case_string_key;
282  }
283  else
284  {
285  table->gen_hash = gen_string_hash;
286  table->cmp_key = cmp_string_key;
287  }
288  if (flags & MUTT_HASH_STRDUP_KEYS)
289  table->strdup_keys = true;
290  if (flags & MUTT_HASH_ALLOW_DUPS)
291  table->allow_dups = true;
292  return table;
293 }
A Hash Table.
Definition: hash.h:61
static struct Hash * hash_new(size_t nelem)
Create a new Hash table.
Definition: hash.c:137
static int cmp_case_string_key(union HashKey a, union HashKey b)
Compare two string keys (ignore case)
Definition: hash.c:96
static int cmp_string_key(union HashKey a, union HashKey b)
Compare two string keys.
Definition: hash.c:65
#define MUTT_HASH_STRCASECMP
use strcasecmp() to compare keys
Definition: hash.h:75
int(* cmp_key)(union HashKey, union HashKey)
Function to compare two Hash keys.
Definition: hash.h:68
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:66
#define MUTT_HASH_ALLOW_DUPS
allow duplicate keys to be inserted
Definition: hash.h:77
size_t nelem
Number of elements in the Hash table.
Definition: hash.h:63
bool allow_dups
if set, duplicate keys are allowed
Definition: hash.h:65
bool strdup_keys
if set, the key->strkey is strdup&#39;ed
Definition: hash.h:64
static size_t gen_string_hash(union HashKey key, size_t n)
Generate a hash from a string.
Definition: hash.c:45
static size_t gen_case_string_hash(union HashKey key, size_t n)
Generate a hash from a string (ignore the case)
Definition: hash.c:76
#define MUTT_HASH_STRDUP_KEYS
make a copy of the keys
Definition: hash.h:76
size_t(* gen_hash)(union HashKey, size_t)
Function to generate hash id from the key.
Definition: hash.h:67
+ 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 Hash table,
hashelem_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 317 of file hash.c.

318 {
319  if (!table)
320  return;
321  table->free_hdata = fn;
322  table->hdata = fn_data;
323 }
hashelem_free_t free_hdata
Function to free a Hash element.
Definition: hash.h:70
intptr_t hdata
Data to pass to the free_hdata() function.
Definition: hash.h:69
+ Here is the caller graph for this function:

◆ mutt_hash_typed_insert()

struct HashElem* mutt_hash_typed_insert ( struct Hash 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 333 of file hash.c.

335 {
336  if (!table || !strkey)
337  return NULL;
338 
339  union HashKey key;
340  key.strkey = table->strdup_keys ? mutt_str_strdup(strkey) : strkey;
341  return union_hash_insert(table, key, type, data);
342 }
static struct HashElem * union_hash_insert(struct Hash *table, union HashKey key, int type, void *data)
Insert into a hash table using a union as a key.
Definition: hash.c:155
char * mutt_str_strdup(const char *str)
Copy a string, safely.
Definition: string.c:380
const char * strkey
Definition: hash.h:35
bool strdup_keys
if set, the key->strkey is strdup&#39;ed
Definition: hash.h:64
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 Hash 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 503 of file hash.c.

504 {
505  if (!table || !state)
506  return NULL;
507 
508  if (state->last && state->last->next)
509  {
510  state->last = state->last->next;
511  return state->last;
512  }
513 
514  if (state->last)
515  state->index++;
516 
517  while (state->index < table->nelem)
518  {
519  if (table->table[state->index])
520  {
521  state->last = table->table[state->index];
522  return state->last;
523  }
524  state->index++;
525  }
526 
527  state->index = 0;
528  state->last = NULL;
529  return NULL;
530 }
struct HashElem * next
Definition: hash.h:47
struct HashElem * last
Definition: hash.h:99
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:66
size_t nelem
Number of elements in the Hash table.
Definition: hash.h:63
size_t index
Definition: hash.h:98
+ Here is the caller graph for this function: