NeoMutt  2020-04-24
Teaching an old dog new tricks
DOXYGEN
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 Hashhash_new (size_t nelem)
 Create a new Hash table. More...
 
static struct HashElemunion_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 HashElemunion_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 Hashmutt_hash_new (size_t nelem, HashFlags flags)
 Create a new Hash table (with string keys) More...
 
struct Hashmutt_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 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_insert (struct Hash *table, const char *strkey, void *data)
 Add a new element to the Hash table (with string keys) 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...
 
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_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_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 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.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
keyString key
nNumber of elements in the Hash table
Return values
numCryptographic hash of the string

Definition at line 45 of file hash.c.

46 {
47  size_t h = 0;
48  const unsigned char *s = (const unsigned char *) key.strkey;
49 
50  while (*s)
51  h += ((h << 7) + *s++);
52  h = (h * SOME_PRIME) % n;
53 
54  return h;
55 }
while(1)
Definition: acutest.h:731
int n
Definition: acutest.h:492
const char * strkey
Definition: hash.h:35
#define SOME_PRIME
Definition: hash.c:37
+ 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
aFirst key to compare
bSecond key to compare
Return values
-1a precedes b
0a and b are identical
1b precedes a

Definition at line 65 of file hash.c.

66 {
67  return mutt_str_strcmp(a.strkey, b.strkey);
68 }
const char * strkey
Definition: hash.h:35
int mutt_str_strcmp(const char *a, const char *b)
Compare two strings, safely.
Definition: string.c:641
+ 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
keyString key
nNumber of elements in the Hash table
Return values
numCryptographic hash of the string

Definition at line 76 of file hash.c.

77 {
78  size_t h = 0;
79  const unsigned char *s = (const unsigned char *) key.strkey;
80 
81  while (*s)
82  h += ((h << 7) + tolower(*s++));
83  h = (h * SOME_PRIME) % n;
84 
85  return h;
86 }
while(1)
Definition: acutest.h:731
int n
Definition: acutest.h:492
const char * strkey
Definition: hash.h:35
#define SOME_PRIME
Definition: hash.c:37
+ 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
aFirst key to compare
bSecond key to compare
Return values
-1a precedes b
0a and b are identical
1b precedes a

Definition at line 96 of file hash.c.

97 {
98  return mutt_str_strcasecmp(a.strkey, b.strkey);
99 }
const char * strkey
Definition: hash.h:35
int mutt_str_strcasecmp(const char *a, const char *b)
Compare two strings ignoring case, safely.
Definition: string.c:654
+ 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
keyInteger key
nNumber of elements in the Hash table
Return values
numCryptographic hash of the integer

Definition at line 107 of file hash.c.

108 {
109  return key.intkey % n;
110 }
unsigned int intkey
Definition: hash.h:36
int n
Definition: acutest.h:492
+ 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
aFirst key to compare
bSecond key to compare
Return values
-1a precedes b
0a and b are identical
1b precedes a

Definition at line 120 of file hash.c.

121 {
122  if (a.intkey == b.intkey)
123  return 0;
124  if (a.intkey < b.intkey)
125  return -1;
126  return 1;
127 }
unsigned int intkey
Definition: hash.h:36
+ 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
nelemNumber of elements it should contain
Return values
ptrNew 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.

138 {
139  struct Hash *table = mutt_mem_calloc(1, sizeof(struct Hash));
140  if (nelem == 0)
141  nelem = 2;
142  table->nelem = nelem;
143  table->table = mutt_mem_calloc(nelem, sizeof(struct HashElem *));
144  return table;
145 }
void * mutt_mem_calloc(size_t nmemb, size_t size)
Allocate zeroed memory on the heap.
Definition: memory.c:50
A Hash Table.
Definition: hash.h:61
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
The item stored in a Hash Table.
Definition: hash.h:42
+ 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
tableHash table to update
keyKey to hash on
typeData type
dataData to associate with key
Return values
ptrNewly inserted HashElem

Definition at line 155 of file hash.c.

157 {
158  if (!table)
159  return NULL;
160 
161  struct HashElem *he = mutt_mem_malloc(sizeof(struct HashElem));
162  unsigned int h = table->gen_hash(key, table->nelem);
163  he->key = key;
164  he->data = data;
165  he->type = type;
166 
167  if (table->allow_dups)
168  {
169  he->next = table->table[h];
170  table->table[h] = he;
171  }
172  else
173  {
174  struct HashElem *tmp = NULL, *last = NULL;
175 
176  for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next)
177  {
178  const int r = table->cmp_key(tmp->key, key);
179  if (r == 0)
180  {
181  FREE(&he);
182  return NULL;
183  }
184  if (r > 0)
185  break;
186  }
187  if (last)
188  last->next = he;
189  else
190  table->table[h] = he;
191  he->next = tmp;
192  }
193  return he;
194 }
union HashKey key
Definition: hash.h:45
struct HashElem * next
Definition: hash.h:47
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
size_t nelem
Number of elements in the Hash table.
Definition: hash.h:63
void * mutt_mem_malloc(size_t size)
Allocate memory on the heap.
Definition: memory.c:90
bool allow_dups
if set, duplicate keys are allowed
Definition: hash.h:65
void * data
Definition: hash.h:46
int type
Definition: hash.h:44
#define FREE(x)
Definition: memory.h:40
The item stored in a Hash Table.
Definition: hash.h:42
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:

◆ 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
tableHash table to search
keyKey (either string or integer)
Return values
ptrHashElem matching the key

Definition at line 202 of file hash.c.

203 {
204  if (!table)
205  return NULL;
206 
207  int hash = table->gen_hash(key, table->nelem);
208  struct HashElem *he = table->table[hash];
209  for (; he; he = he->next)
210  {
211  if (table->cmp_key(key, he->key) == 0)
212  return he;
213  }
214  return NULL;
215 }
union HashKey key
Definition: hash.h:45
struct HashElem * next
Definition: hash.h:47
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
size_t nelem
Number of elements in the Hash table.
Definition: hash.h:63
The item stored in a Hash Table.
Definition: hash.h:42
size_t(* gen_hash)(union HashKey, size_t)
Function to generate hash id from the key.
Definition: hash.h:67
+ 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
tableHash table to search
keyKey (either string or integer)
Return values
ptrData attached to the HashElem matching the key

Definition at line 223 of file hash.c.

224 {
225  if (!table)
226  return NULL;
227  struct HashElem *he = union_hash_find_elem(table, key);
228  if (he)
229  return he->data;
230  return NULL;
231 }
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
void * data
Definition: hash.h:46
The item stored in a Hash Table.
Definition: hash.h:42
+ 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
tableHash table to use
keyKey (either string or integer)
dataPrivate data to match (or NULL for any match)

Definition at line 239 of file hash.c.

240 {
241  if (!table)
242  return;
243 
244  int hash = table->gen_hash(key, table->nelem);
245  struct HashElem *he = table->table[hash];
246  struct HashElem **last = &table->table[hash];
247 
248  while (he)
249  {
250  if (((data == he->data) || !data) && (table->cmp_key(he->key, key) == 0))
251  {
252  *last = he->next;
253  if (table->free_hdata)
254  table->free_hdata(he->type, he->data, table->hdata);
255  if (table->strdup_keys)
256  FREE(&he->key.strkey);
257  FREE(&he);
258 
259  he = *last;
260  }
261  else
262  {
263  last = &he->next;
264  he = he->next;
265  }
266  }
267 }
union HashKey key
Definition: hash.h:45
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
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
size_t nelem
Number of elements in the Hash table.
Definition: hash.h:63
void * data
Definition: hash.h:46
const char * strkey
Definition: hash.h:35
int type
Definition: hash.h:44
#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
size_t(* gen_hash)(union HashKey, size_t)
Function to generate hash id from the key.
Definition: hash.h:67
+ 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) - Implements Hash::cmp_key()
Definition: hash.c:96
static int cmp_string_key(union HashKey a, union HashKey b)
Compare two string keys - Implements Hash::cmp_key()
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 - Implements Hash::gen_hash()
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) - Implements Hash::gen_hash()
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_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 - Implements Hash::gen_hash()
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 - Implements Hash::cmp_key()
Definition: hash.c:120
+ 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_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 }
const char * strkey
Definition: hash.h:35
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_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_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_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_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_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_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_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_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: