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

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  num_elems  )

static

Generate a hash from a string - Implements hash_gen_hash_t.

Definition at line 42 of file hash.c.

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

  while (*s != '\0')
    hash += ((hash << 7) + *s++);
  hash = (hash * SOME_PRIME) % num_elems;

  return hash;
}

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

Definition at line 57 of file hash.c.

{
  return mutt_str_cmp(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  num_elems  )

static

Generate a hash from a string (ignore the case) - Implements hash_gen_hash_t.

Definition at line 65 of file hash.c.

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

  while (*s != '\0')
    hash += ((hash << 7) + tolower(*s++));
  hash = (hash * SOME_PRIME) % num_elems;

  return hash;
}

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

Definition at line 80 of file hash.c.

{
  return mutt_istr_cmp(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  num_elems  )

static

Generate a hash from an integer - Implements hash_gen_hash_t.

Definition at line 88 of file hash.c.

{
  return (key.intkey % num_elems);
}

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

Definition at line 96 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 HashTable* hash_new ( size_t  num_elems )

static

Create a new Hash Table.

Parameters

num_elems

Number of elements it should contain

Return values

ptr	New Hash Table

The Hash Table can contain more elements than num_elems, but they will be chained together.

Definition at line 113 of file hash.c.

{
  struct HashTable *table = mutt_mem_calloc(1, sizeof(struct HashTable));
  if (num_elems == 0)
    num_elems = 2;
  table->num_elems = num_elems;
  table->table = mutt_mem_calloc(num_elems, 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 HashTable *  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 131 of file hash.c.

{
  if (!table)
    return NULL; // LCOV_EXCL_LINE

  struct HashElem *he = mutt_mem_calloc(1, sizeof(struct HashElem));
  size_t hash = table->gen_hash(key, table->num_elems);
  he->key = key;
  he->data = data;
  he->type = type;

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

    for (tmp = table->table[hash], last = NULL; tmp; last = tmp, tmp = tmp->next)
    {
      const int rc = table->cmp_key(tmp->key, key);
      if (rc == 0)
      {
        FREE(&he);
        return NULL;
      }
      if (rc > 0)
        break;
    }
    if (last)
      last->next = he;
    else
      table->table[hash] = 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 HashTable *  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 178 of file hash.c.

{
  if (!table)
    return NULL; // LCOV_EXCL_LINE

  size_t hash = table->gen_hash(key, table->num_elems);
  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 HashTable *  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 199 of file hash.c.

{
  if (!table)
    return NULL; // LCOV_EXCL_LINE
  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 HashTable *  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 215 of file hash.c.

{
  if (!table)
    return; // LCOV_EXCL_LINE

  size_t hash = table->gen_hash(key, table->num_elems);
  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->hdata_free)
        table->hdata_free(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 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 251 of file hash.c.

{
  struct HashTable *table = hash_new(num_elems);
  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 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 277 of file hash.c.

{
  struct HashTable *table = hash_new(num_elems);
  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 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 293 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 309 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_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 327 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 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 339 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 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 354 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 369 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 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 384 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 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 401 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_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 419 of file hash.c.

{
  if (!table || !strkey)
    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_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 436 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 HashTable **

ptr

)

Free a hash table.

Parameters

[out]

ptr

Hash Table to be freed

Definition at line 449 of file hash.c.

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

  struct HashTable *table = *ptr;
  struct HashElem *elem = NULL, *tmp = NULL;

  for (size_t i = 0; i < table->num_elems; i++)
  {
    for (elem = table->table[i]; elem;)
    {
      tmp = elem;
      elem = elem->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_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 481 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: