hash.h File Reference

Hash Table data structure. More...

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include "array.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.
#define	MUTT_HASH_STRCASECMP   (1 << 0)
	use strcasecmp() to compare keys
#define	MUTT_HASH_STRDUP_KEYS   (1 << 1)
	make a copy of the keys
#define	MUTT_HASH_ALLOW_DUPS   (1 << 2)
	allow duplicate keys to be inserted

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.

Functions
	ARRAY_HEAD (HashElemArray, struct HashElem *)
void	mutt_hash_delete (struct HashTable *table, const char *strkey, const void *data)
	Remove an element from a Hash Table.
struct HashElem *	mutt_hash_find_bucket (const struct HashTable *table, const char *strkey)
	Find the HashElem in a Hash Table element using a key.
void *	mutt_hash_find (const struct HashTable *table, const char *strkey)
	Find the HashElem data in a Hash Table element using a key.
struct HashElem *	mutt_hash_find_elem (const struct HashTable *table, const char *strkey)
	Find the HashElem in a Hash Table element using a key.
void	mutt_hash_free (struct HashTable **ptr)
	Free a hash table.
struct HashElem *	mutt_hash_insert (struct HashTable *table, const char *strkey, void *data)
	Add a new element to the Hash Table (with string keys)
void	mutt_hash_int_delete (struct HashTable *table, unsigned int intkey, const void *data)
	Remove an element from a Hash Table.
void *	mutt_hash_int_find (const struct HashTable *table, unsigned int intkey)
	Find the HashElem data in a Hash Table element using a key.
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)
struct HashTable *	mutt_hash_int_new (size_t num_elems, HashFlags flags)
	Create a new Hash Table (with integer keys)
struct HashTable *	mutt_hash_new (size_t num_elems, HashFlags flags)
	Create a new Hash Table (with string keys)
void	mutt_hash_set_destructor (struct HashTable *table, hash_hdata_free_t fn, intptr_t fn_data)
	Set the destructor for a Hash Table.
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.
struct HashElem *	mutt_hash_walk (const struct HashTable *table, struct HashWalkState *state)
	Iterate through all the HashElem's in a Hash Table.

Detailed Description

Hash Table data structure.

Authors

• Richard Russon

Copyright

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 2 of the License, or (at your option) any later version.

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 111 of file hash.h.

MUTT_HASH_STRCASECMP

#define MUTT_HASH_STRCASECMP   (1 << 0)

use strcasecmp() to compare keys

Definition at line 112 of file hash.h.

MUTT_HASH_STRDUP_KEYS

#define MUTT_HASH_STRDUP_KEYS   (1 << 1)

make a copy of the keys

Definition at line 113 of file hash.h.

MUTT_HASH_ALLOW_DUPS

#define MUTT_HASH_ALLOW_DUPS   (1 << 2)

allow duplicate keys to be inserted

Definition at line 114 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 110 of file hash.h.

Function Documentation

ARRAY_HEAD()

ARRAY_HEAD	(	HashElemArray	,
		struct HashElem *	)

mutt_hash_delete()

void mutt_hash_delete	(	struct HashTable *	table,
		const char *	strkey,
		const void *	data )

Remove an element from a Hash Table.

Parameters

table	Hash Table to use
strkey	String key to match
data	Private data to match (or NULL for any match)

Definition at line 427 of file hash.c.

{
  if (!table || !strkey || (strkey[0] == '\0'))
    return;
  union HashKey key;
  // Copy the key because union_hash_delete() may use it after the HashElem is freed.
  key.strkey = mutt_str_dup(strkey);
  union_hash_delete(table, key, data);
  FREE(&key.strkey);
}

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

table	Hash Table to search
strkey	String key to search for

Return values

ptr	HashElem matching the key

Unlike mutt_hash_find_elem(), this will return the first matching entry.

Definition at line 409 of file hash.c.

{
  if (!table || !strkey)
    return NULL;
 
  union HashKey key;
 
  key.strkey = strkey;
  size_t hash = table->gen_hash(key, table->num_elems);
  return table->table[hash];
}

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

table	Hash Table to search
strkey	String key to search for

Return values

ptr	Data attached to the HashElem matching the key

Definition at line 362 of file hash.c.

{
  if (!table || !strkey)
    return NULL;
  union HashKey key;
  key.strkey = strkey;
  return union_hash_find(table, key);
}

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

table	Hash Table to search
strkey	String key to search for

Return values

ptr	HashElem matching the key

Definition at line 377 of file hash.c.

{
  if (!table || !strkey)
    return NULL;
  union HashKey key;
  key.strkey = strkey;
  return union_hash_find_elem(table, key);
}

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]

ptr

Hash Table to be freed

Definition at line 457 of file hash.c.

{
  if (!ptr || !*ptr)
    return;
 
  struct HashTable *table = *ptr;
  struct HashElem *he = NULL, *tmp = NULL;
 
  for (size_t i = 0; i < table->num_elems; i++)
  {
    for (he = table->table[i]; he;)
    {
      tmp = he;
      he = he->next;
      if (table->hdata_free && tmp->data)
        table->hdata_free(tmp->type, tmp->data, table->hdata);
      if (table->strdup_keys)
        FREE(&tmp->key.strkey);
      FREE(&tmp);
    }
  }
  FREE(&table->table);
  FREE(ptr);
}

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

table	Hash Table (with string keys)
strkey	String key
data	Private data associated with the key

Return values

ptr	Newly inserted HashElem

Definition at line 335 of file hash.c.

{
  return mutt_hash_typed_insert(table, strkey, -1, data);
}

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

table	Hash Table to use
intkey	Integer key to match
data	Private data to match (or NULL for any match)

Definition at line 444 of file hash.c.

{
  if (!table)
    return;
  union HashKey key;
  key.intkey = intkey;
  union_hash_delete(table, key, data);
}

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

table	Hash Table to search
intkey	Integer key

Return values

ptr	Data attached to the HashElem matching the key

Definition at line 392 of file hash.c.

{
  if (!table)
    return NULL;
  union HashKey key;
  key.intkey = intkey;
  return union_hash_find(table, key);
}

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

table	Hash Table (with integer keys)
intkey	Integer key
data	Private data associated with the key

Return values

ptr	Newly inserted HashElem

Definition at line 347 of file hash.c.

{
  if (!table)
    return NULL;
  union HashKey key;
  key.intkey = intkey;
  return union_hash_insert(table, key, -1, data);
}

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_elems	Number of elements it should contain
flags	Flags, see HashFlags

Return values

ptr	New Hash Table

Definition at line 285 of file hash.c.

{
  struct HashTable *table = hash_new(num_elems);
  table->gen_hash = gen_hash_int;
  table->cmp_key = cmp_key_int;
  if (flags & MUTT_HASH_ALLOW_DUPS)
    table->allow_dups = true;
  return table;
}

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_elems	Number of elements it should contain
flags	Flags, see HashFlags

Return values

ptr	New Hash Table

Definition at line 259 of file hash.c.

{
  struct HashTable *table = hash_new(num_elems);
  if (flags & MUTT_HASH_STRCASECMP)
  {
    table->gen_hash = gen_hash_case_string;
    table->cmp_key = cmp_key_case_string;
  }
  else
  {
    table->gen_hash = gen_hash_string;
    table->cmp_key = cmp_key_string;
  }
  if (flags & MUTT_HASH_STRDUP_KEYS)
    table->strdup_keys = true;
  if (flags & MUTT_HASH_ALLOW_DUPS)
    table->allow_dups = true;
  return table;
}

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

table	Hash Table to use
fn	Callback function to free Hash Table's resources
fn_data	Data to pass to the callback function

Definition at line 301 of file hash.c.

{
  if (!table)
    return;
  table->hdata_free = fn;
  table->hdata = fn_data;
}

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

table	Hash Table to use
strkey	String key
type	Type to associate with the key
data	Private data associated with the key

Return values

ptr	Newly inserted HashElem

Definition at line 317 of file hash.c.

{
  if (!table || !strkey)
    return NULL;
 
  union HashKey key;
  key.strkey = table->strdup_keys ? mutt_str_dup(strkey) : strkey;
  return union_hash_insert(table, key, type, data);
}

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

table	Hash Table to search
state	Cursor to keep track

Return values

ptr	Next HashElem in the Hash Table
NULL	When the last HashElem has been seen

Definition at line 489 of file hash.c.

{
  if (!table || !state)
    return NULL;
 
  if (state->last && state->last->next)
  {
    state->last = state->last->next;
    return state->last;
  }
 
  if (state->last)
    state->index++;
 
  while (state->index < table->num_elems)
  {
    if (table->table[state->index])
    {
      state->last = table->table[state->index];
      return state->last;
    }
    state->index++;
  }
 
  state->index = 0;
  state->last = NULL;
  return NULL;
}

Here is the caller graph for this function: