hash.c File Reference

Hash Table data structure. More...

#include "config.h"
#include <stdbool.h>
#include "hash.h"
#include "ctype2.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
	A prime number used for hashing.

Functions
static size_t	gen_hash_string (union HashKey key, size_t num_elems)
	Generate a hash from a string - Implements hash_gen_hash_t -.
static int	cmp_key_string (union HashKey a, union HashKey b)
	Compare two string keys - Implements hash_cmp_key_t -.
static size_t	gen_hash_case_string (union HashKey key, size_t num_elems)
	Generate a hash from a string (ignore the case) - Implements hash_gen_hash_t -.
static int	cmp_key_case_string (union HashKey a, union HashKey b)
	Compare two string keys (ignore case) - Implements hash_cmp_key_t -.
static size_t	gen_hash_int (union HashKey key, size_t num_elems)
	Generate a hash from an integer - Implements hash_gen_hash_t -.
static int	cmp_key_int (union HashKey a, union HashKey b)
	Compare two integer keys - Implements hash_cmp_key_t -.
static struct HashTable *	hash_new (size_t num_elems)
	Create a new Hash Table.
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.
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.
static void *	union_hash_find (const struct HashTable *table, union HashKey key)
	Find the HashElem data in a Hash Table element using a key.
static void	union_hash_delete (struct HashTable *table, union HashKey key, const void *data)
	Remove an element from a Hash Table.
struct HashTable *	mutt_hash_new (size_t num_elems, HashFlags flags)
	Create a new Hash Table (with string keys)
struct HashTable *	mutt_hash_int_new (size_t num_elems, HashFlags flags)
	Create a new Hash Table (with integer 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_insert (struct HashTable *table, const char *strkey, void *data)
	Add a new element to the Hash Table (with string keys)
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)
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_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_find_bucket (const struct HashTable *table, const char *strkey)
	Find the HashElem in a Hash Table element using a key.
void	mutt_hash_delete (struct HashTable *table, const char *strkey, const void *data)
	Remove an element from a Hash Table.
void	mutt_hash_int_delete (struct HashTable *table, unsigned int intkey, const void *data)
	Remove an element from a Hash Table.
void	mutt_hash_free (struct HashTable **ptr)
	Free 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
• Pietro Cerutti
• Thomas Klausner

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

A prime number used for hashing.

Definition at line 39 of file hash.c.

Function Documentation

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

{
  struct HashTable *table = MUTT_MEM_CALLOC(1, struct HashTable);
  if (num_elems == 0)
    num_elems = 2;
  table->num_elems = num_elems;
  table->table = MUTT_MEM_CALLOC(num_elems, struct HashElem *);
  return table;
}

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

{
  if (!table)
    return NULL; // LCOV_EXCL_LINE
 
  struct HashElem *he = MUTT_MEM_CALLOC(1, 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;
    struct HashElem *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 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 189 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 210 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 226 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 **he_last = &table->table[hash];
 
  while (he)
  {
    if (((data == he->data) || !data) && (table->cmp_key(he->key, key) == 0))
    {
      *he_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 = *he_last;
    }
    else
    {
      he_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 262 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_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 288 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_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 304 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 320 of file hash.c.

{
  if (!table || !strkey)
    return NULL;
 
  union HashKey key = { 0 };
  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 338 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 350 of file hash.c.

{
  if (!table)
    return NULL;
  union HashKey key = { 0 };
  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 365 of file hash.c.

{
  if (!table || !strkey)
    return NULL;
  union HashKey key = { 0 };
  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 380 of file hash.c.

{
  if (!table || !strkey)
    return NULL;
  union HashKey key = { 0 };
  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 395 of file hash.c.

{
  if (!table)
    return NULL;
  union HashKey key = { 0 };
  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 412 of file hash.c.

{
  if (!table || !strkey)
    return NULL;
 
  union HashKey key = { 0 };
 
  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 430 of file hash.c.

{
  if (!table || !strkey || (strkey[0] == '\0'))
    return;
  union HashKey key = { 0 };
  // 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 447 of file hash.c.

{
  if (!table)
    return;
  union HashKey key = { 0 };
  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 460 of file hash.c.

{
  if (!ptr || !*ptr)
    return;
 
  struct HashTable *table = *ptr;
  struct HashElem *he = NULL;
  struct HashElem *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_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 493 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: