hash.c File Reference

Hash table data structure. More...

#include "config.h"
#include <ctype.h>
#include <stdbool.h>
#include "hash.h"
#include "memory.h"
#include "string2.h"

Include dependency graph for hash.c:

Go to the source code of this file.

Macros
#define	SOME_PRIME   149711

Functions
static size_t	gen_string_hash (union HashKey key, size_t n)
	Generate a hash from a string - Implements Hash::gen_hash() More...
static int	cmp_string_key (union HashKey a, union HashKey b)
	Compare two string keys - Implements Hash::cmp_key() More...
static size_t	gen_case_string_hash (union HashKey key, size_t n)
	Generate a hash from a string (ignore the case) - Implements Hash::gen_hash() More...
static int	cmp_case_string_key (union HashKey a, union HashKey b)
	Compare two string keys (ignore case) - Implements Hash::cmp_key() More...
static size_t	gen_int_hash (union HashKey key, size_t n)
	Generate a hash from an integer - Implements Hash::gen_hash() More...
static int	cmp_int_key (union HashKey a, union HashKey b)
	Compare two integer keys - Implements Hash::cmp_key() More...
static struct Hash *	hash_new (size_t nelem)
	Create a new Hash table. More...
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. More...
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. More...
static void *	union_hash_find (const struct Hash *table, union HashKey key)
	Find the HashElem data in a Hash table element using a key. More...
static void	union_hash_delete (struct Hash *table, union HashKey key, const void *data)
	Remove an element from a Hash table. More...
struct Hash *	mutt_hash_new (size_t nelem, HashFlags flags)
	Create a new Hash table (with string keys) More...
struct Hash *	mutt_hash_int_new (size_t nelem, HashFlags flags)
	Create a new Hash table (with integer 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 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. More...
struct HashElem *	mutt_hash_insert (struct Hash *table, const char *strkey, void *data)
	Add a new element to the Hash table (with string keys) More...
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) 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 HashElem *	mutt_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_int_find (const struct Hash *table, unsigned int intkey)
	Find the HashElem data in a Hash table element using a key. More...
struct HashElem *	mutt_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_delete (struct Hash *table, const char *strkey, const void *data)
	Remove an element from a Hash table. 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_free (struct Hash **ptr)
	Free a hash table. More...
struct HashElem *	mutt_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

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.c.

Macro Definition Documentation

SOME_PRIME

#define SOME_PRIME   149711

Definition at line 37 of file hash.c.

Function Documentation

gen_string_hash()

static size_t gen_string_hash ( union HashKey  key, size_t  n  )

static

Generate a hash from a string - Implements Hash::gen_hash()

Parameters

key	String key
n	Number of elements in the Hash table

Return values

num	Cryptographic hash of the string

Definition at line 45 of file hash.c.

{
  size_t h = 0;
  const unsigned char *s = (const unsigned char *) key.strkey;

  while (*s)
    h += ((h << 7) + *s++);
  h = (h * SOME_PRIME) % n;

  return h;
}

Here is the call graph for this function:

Here is the caller graph for this function:

cmp_string_key()

static int cmp_string_key ( union HashKey  a, union HashKey  b  )

static

Compare two string keys - Implements Hash::cmp_key()

Parameters

a	First key to compare
b	Second key to compare

Return values

-1	a precedes b
0	a and b are identical
1	b precedes a

Definition at line 65 of file hash.c.

{
  return mutt_str_strcmp(a.strkey, b.strkey);
}

Here is the call graph for this function:

Here is the caller graph for this function:

gen_case_string_hash()

static size_t gen_case_string_hash ( union HashKey  key, size_t  n  )

static

Generate a hash from a string (ignore the case) - Implements Hash::gen_hash()

Parameters

key	String key
n	Number of elements in the Hash table

Return values

num	Cryptographic hash of the string

Definition at line 76 of file hash.c.

{
  size_t h = 0;
  const unsigned char *s = (const unsigned char *) key.strkey;

  while (*s)
    h += ((h << 7) + tolower(*s++));
  h = (h * SOME_PRIME) % n;

  return h;
}

Here is the call graph for this function:

Here is the caller graph for this function:

cmp_case_string_key()

static int cmp_case_string_key ( union HashKey  a, union HashKey  b  )

static

Compare two string keys (ignore case) - Implements Hash::cmp_key()

Parameters

a	First key to compare
b	Second key to compare

Return values

-1	a precedes b
0	a and b are identical
1	b precedes a

Definition at line 96 of file hash.c.

{
  return mutt_str_strcasecmp(a.strkey, b.strkey);
}

Here is the call graph for this function:

Here is the caller graph for this function:

gen_int_hash()

static size_t gen_int_hash ( union HashKey  key, size_t  n  )

static

Generate a hash from an integer - Implements Hash::gen_hash()

Parameters

key	Integer key
n	Number of elements in the Hash table

Return values

num	Cryptographic hash of the integer

Definition at line 107 of file hash.c.

{
  return key.intkey % n;
}

Here is the caller graph for this function:

cmp_int_key()

static int cmp_int_key ( union HashKey  a, union HashKey  b  )

static

Compare two integer keys - Implements Hash::cmp_key()

Parameters

a	First key to compare
b	Second key to compare

Return values

-1	a precedes b
0	a and b are identical
1	b precedes a

Definition at line 120 of file hash.c.

{
  if (a.intkey == b.intkey)
    return 0;
  if (a.intkey < b.intkey)
    return -1;
  return 1;
}

Here is the caller graph for this function:

hash_new()

static struct Hash* hash_new ( size_t  nelem )

static

Create a new Hash table.

Parameters

nelem

Number of elements it should contain

Return values

ptr	New Hash table

The Hash table can contain more elements than nelem, but they will be chained together.

Definition at line 137 of file hash.c.

{
  struct Hash *table = mutt_mem_calloc(1, sizeof(struct Hash));
  if (nelem == 0)
    nelem = 2;
  table->nelem = nelem;
  table->table = mutt_mem_calloc(nelem, sizeof(struct HashElem *));
  return table;
}

Here is the call graph for this function:

Here is the caller graph for this function:

union_hash_insert()

static struct HashElem* union_hash_insert ( struct Hash *  table, union HashKey  key, int  type, void *  data  )

static

Insert into a hash table using a union as a key.

Parameters

table	Hash table to update
key	Key to hash on
type	Data type
data	Data to associate with key

Return values

ptr	Newly inserted HashElem

Definition at line 155 of file hash.c.

{
  if (!table)
    return NULL;

  struct HashElem *he = mutt_mem_malloc(sizeof(struct HashElem));
  unsigned int h = table->gen_hash(key, table->nelem);
  he->key = key;
  he->data = data;
  he->type = type;

  if (table->allow_dups)
  {
    he->next = table->table[h];
    table->table[h] = he;
  }
  else
  {
    struct HashElem *tmp = NULL, *last = NULL;

    for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next)
    {
      const int r = table->cmp_key(tmp->key, key);
      if (r == 0)
      {
        FREE(&he);
        return NULL;
      }
      if (r > 0)
        break;
    }
    if (last)
      last->next = he;
    else
      table->table[h] = he;
    he->next = tmp;
  }
  return he;
}

Here is the call graph for this function:

Here is the caller graph for this function:

union_hash_find_elem()

static struct HashElem* union_hash_find_elem ( const struct Hash *  table, union HashKey  key  )

static

Find a HashElem in a Hash table element using a key.

Parameters

table	Hash table to search
key	Key (either string or integer)

Return values

ptr	HashElem matching the key

Definition at line 202 of file hash.c.

{
  if (!table)
    return NULL;

  int hash = table->gen_hash(key, table->nelem);
  struct HashElem *he = table->table[hash];
  for (; he; he = he->next)
  {
    if (table->cmp_key(key, he->key) == 0)
      return he;
  }
  return NULL;
}

Here is the caller graph for this function:

union_hash_find()

static void* union_hash_find ( const struct Hash *  table, union HashKey  key  )

static

Find the HashElem data in a Hash table element using a key.

Parameters

table	Hash table to search
key	Key (either string or integer)

Return values

ptr	Data attached to the HashElem matching the key

Definition at line 223 of file hash.c.

{
  if (!table)
    return NULL;
  struct HashElem *he = union_hash_find_elem(table, key);
  if (he)
    return he->data;
  return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

union_hash_delete()

static void union_hash_delete ( struct Hash *  table, union HashKey  key, const void *  data  )

static

Remove an element from a Hash table.

Parameters

table	Hash table to use
key	Key (either string or integer)
data	Private data to match (or NULL for any match)

Definition at line 239 of file hash.c.

{
  if (!table)
    return;

  int hash = table->gen_hash(key, table->nelem);
  struct HashElem *he = table->table[hash];
  struct HashElem **last = &table->table[hash];

  while (he)
  {
    if (((data == he->data) || !data) && (table->cmp_key(he->key, key) == 0))
    {
      *last = he->next;
      if (table->free_hdata)
        table->free_hdata(he->type, he->data, table->hdata);
      if (table->strdup_keys)
        FREE(&he->key.strkey);
      FREE(&he);

      he = *last;
    }
    else
    {
      last = &he->next;
      he = he->next;
    }
  }
}

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

nelem	Number of elements it should contain
flags	Flags, see HashFlags

Return values

ptr	New Hash table

Definition at line 275 of file hash.c.

{
  struct Hash *table = hash_new(nelem);
  if (flags & MUTT_HASH_STRCASECMP)
  {
    table->gen_hash = gen_case_string_hash;
    table->cmp_key = cmp_case_string_key;
  }
  else
  {
    table->gen_hash = gen_string_hash;
    table->cmp_key = cmp_string_key;
  }
  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_int_new()

struct Hash* mutt_hash_int_new	(	size_t	nelem,
		HashFlags	flags
	)

Create a new Hash table (with integer keys)

Parameters

nelem	Number of elements it should contain
flags	Flags, see HashFlags

Return values

ptr	New Hash table

Definition at line 301 of file hash.c.

{
  struct Hash *table = hash_new(nelem);
  table->gen_hash = gen_int_hash;
  table->cmp_key = cmp_int_key;
  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 Hash *	table,
		hashelem_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 317 of file hash.c.

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

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

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 333 of file hash.c.

{
  if (!table || !strkey)
    return NULL;

  union HashKey key;
  key.strkey = table->strdup_keys ? mutt_str_strdup(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_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

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 351 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_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

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 363 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_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

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 378 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 Hash *	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 393 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_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

table	Hash table to search
intkey	Integer key

Return values

ptr	Data attached to the HashElem matching the key

Definition at line 408 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_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

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 425 of file hash.c.

{
  if (!table || !strkey)
    return NULL;

  union HashKey key;

  key.strkey = strkey;
  int hash = table->gen_hash(key, table->nelem);
  return table->table[hash];
}

Here is the caller graph for this function:

mutt_hash_delete()

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

{
  if (!table || !strkey)
    return;
  union HashKey key;
  key.strkey = strkey;
  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_delete()

void mutt_hash_int_delete	(	struct Hash *	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 458 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_free()

void mutt_hash_free

(

struct Hash **

ptr

)

Free a hash table.

Parameters

[out]

ptr

Hash Table to be freed

Definition at line 471 of file hash.c.

{
  if (!ptr || !*ptr)
    return;

  struct Hash *hash = *ptr;
  struct HashElem *elem = NULL, *tmp = NULL;

  for (size_t i = 0; i < hash->nelem; i++)
  {
    for (elem = hash->table[i]; elem;)
    {
      tmp = elem;
      elem = elem->next;
      if (hash->free_hdata)
        hash->free_hdata(tmp->type, tmp->data, hash->hdata);
      if (hash->strdup_keys)
        FREE(&tmp->key.strkey);
      FREE(&tmp);
    }
  }
  FREE(&hash->table);
  FREE(ptr);
}

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

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 503 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->nelem)
  {
    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: