NeoMutt  2022-04-29-249-gaae397
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 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 HashTablehash_new (size_t num_elems)
 Create a new Hash Table. More...
 
static struct HashElemunion_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 HashElemunion_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 HashTablemutt_hash_new (size_t num_elems, HashFlags flags)
 Create a new Hash Table (with string keys) More...
 
struct HashTablemutt_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 HashElemmutt_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 HashElemmutt_hash_insert (struct HashTable *table, const char *strkey, void *data)
 Add a new element to the Hash Table (with string keys) More...
 
struct HashElemmutt_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 HashElemmutt_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 HashElemmutt_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 HashElemmutt_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

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

◆ hash_new()

static struct HashTable * hash_new ( size_t  num_elems)
static

Create a new Hash Table.

Parameters
num_elemsNumber of elements it should contain
Return values
ptrNew Hash Table

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

Definition at line 121 of file hash.c.

122{
123 struct HashTable *table = mutt_mem_calloc(1, sizeof(struct HashTable));
124 if (num_elems == 0)
125 num_elems = 2;
126 table->num_elems = num_elems;
127 table->table = mutt_mem_calloc(num_elems, sizeof(struct HashElem *));
128 return table;
129}
void * mutt_mem_calloc(size_t nmemb, size_t size)
Allocate zeroed memory on the heap.
Definition: memory.c:50
The item stored in a Hash Table.
Definition: hash.h:44
A Hash Table.
Definition: hash.h:97
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:101
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:98
+ 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
tableHash Table to update
keyKey to hash on
typeData type
dataData to associate with key
Return values
ptrNewly inserted HashElem

Definition at line 139 of file hash.c.

141{
142 if (!table)
143 return NULL; // LCOV_EXCL_LINE
144
145 struct HashElem *he = mutt_mem_calloc(1, sizeof(struct HashElem));
146 size_t hash = table->gen_hash(key, table->num_elems);
147 he->key = key;
148 he->data = data;
149 he->type = type;
150
151 if (table->allow_dups)
152 {
153 he->next = table->table[hash];
154 table->table[hash] = he;
155 }
156 else
157 {
158 struct HashElem *tmp = NULL, *last = NULL;
159
160 for (tmp = table->table[hash], last = NULL; tmp; last = tmp, tmp = tmp->next)
161 {
162 const int rc = table->cmp_key(tmp->key, key);
163 if (rc == 0)
164 {
165 FREE(&he);
166 return NULL;
167 }
168 if (rc > 0)
169 break;
170 }
171 if (last)
172 last->next = he;
173 else
174 table->table[hash] = he;
175 he->next = tmp;
176 }
177 return he;
178}
#define FREE(x)
Definition: memory.h:43
struct HashElem * next
Linked List.
Definition: hash.h:48
union HashKey key
Key representing the data.
Definition: hash.h:46
int type
Type of data stored in Hash Table, e.g. DT_STRING.
Definition: hash.h:45
void * data
User-supplied data.
Definition: hash.h:47
hash_gen_hash_t gen_hash
Function to generate hash id from the key.
Definition: hash.h:102
hash_cmp_key_t cmp_key
Function to compare two Hash keys.
Definition: hash.h:103
bool allow_dups
if set, duplicate keys are allowed
Definition: hash.h:100
+ 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
tableHash Table to search
keyKey (either string or integer)
Return values
ptrHashElem matching the key

Definition at line 186 of file hash.c.

187{
188 if (!table)
189 return NULL; // LCOV_EXCL_LINE
190
191 size_t hash = table->gen_hash(key, table->num_elems);
192 struct HashElem *he = table->table[hash];
193 for (; he; he = he->next)
194 {
195 if (table->cmp_key(key, he->key) == 0)
196 return he;
197 }
198 return NULL;
199}
+ 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
tableHash Table to search
keyKey (either string or integer)
Return values
ptrData attached to the HashElem matching the key

Definition at line 207 of file hash.c.

208{
209 if (!table)
210 return NULL; // LCOV_EXCL_LINE
211 struct HashElem *he = union_hash_find_elem(table, key);
212 if (he)
213 return he->data;
214 return NULL;
215}
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.
Definition: hash.c:186
+ 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
tableHash Table to use
keyKey (either string or integer)
dataPrivate data to match (or NULL for any match)

Definition at line 223 of file hash.c.

224{
225 if (!table)
226 return; // LCOV_EXCL_LINE
227
228 size_t hash = table->gen_hash(key, table->num_elems);
229 struct HashElem *he = table->table[hash];
230 struct HashElem **last = &table->table[hash];
231
232 while (he)
233 {
234 if (((data == he->data) || !data) && (table->cmp_key(he->key, key) == 0))
235 {
236 *last = he->next;
237 if (table->hdata_free)
238 table->hdata_free(he->type, he->data, table->hdata);
239 if (table->strdup_keys)
240 FREE(&he->key.strkey);
241 FREE(&he);
242
243 he = *last;
244 }
245 else
246 {
247 last = &he->next;
248 he = he->next;
249 }
250 }
251}
bool strdup_keys
if set, the key->strkey is strdup()'d
Definition: hash.h:99
intptr_t hdata
Data to pass to the hdata_free() function.
Definition: hash.h:104
hash_hdata_free_t hdata_free
Function to free a Hash element.
Definition: hash.h:105
const char * strkey
String key.
Definition: hash.h:36
+ 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_elemsNumber of elements it should contain
flagsFlags, see HashFlags
Return values
ptrNew Hash Table

Definition at line 259 of file hash.c.

260{
262 if (flags & MUTT_HASH_STRCASECMP)
263 {
264 table->gen_hash = gen_case_string_hash;
265 table->cmp_key = cmp_case_string_key;
266 }
267 else
268 {
269 table->gen_hash = gen_string_hash;
270 table->cmp_key = cmp_string_key;
271 }
272 if (flags & MUTT_HASH_STRDUP_KEYS)
273 table->strdup_keys = true;
274 if (flags & MUTT_HASH_ALLOW_DUPS)
275 table->allow_dups = true;
276 return table;
277}
static int cmp_case_string_key(union HashKey a, union HashKey b)
Compare two string keys (ignore case) - Implements hash_cmp_key_t -.
Definition: hash.c:88
static int cmp_string_key(union HashKey a, union HashKey b)
Compare two string keys - Implements hash_cmp_key_t -.
Definition: hash.c:61
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 -.
Definition: hash.c:71
static size_t gen_string_hash(union HashKey key, size_t num_elems)
Generate a hash from a string - Implements hash_gen_hash_t -.
Definition: hash.c:44
static struct HashTable * hash_new(size_t num_elems)
Create a new Hash Table.
Definition: hash.c:121
#define MUTT_HASH_STRDUP_KEYS
make a copy of the keys
Definition: hash.h:111
#define MUTT_HASH_ALLOW_DUPS
allow duplicate keys to be inserted
Definition: hash.h:112
#define MUTT_HASH_STRCASECMP
use strcasecmp() to compare keys
Definition: hash.h:110
+ 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_elemsNumber of elements it should contain
flagsFlags, see HashFlags
Return values
ptrNew Hash Table

Definition at line 285 of file hash.c.

286{
288 table->gen_hash = gen_int_hash;
289 table->cmp_key = cmp_int_key;
290 if (flags & MUTT_HASH_ALLOW_DUPS)
291 table->allow_dups = true;
292 return table;
293}
static int cmp_int_key(union HashKey a, union HashKey b)
Compare two integer keys - Implements hash_cmp_key_t -.
Definition: hash.c:104
static size_t gen_int_hash(union HashKey key, size_t num_elems)
Generate a hash from an integer - Implements hash_gen_hash_t -.
Definition: hash.c:96
+ 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
tableHash Table to use
fnCallback function to free Hash Table's resources
fn_dataData to pass to the callback function

Definition at line 301 of file hash.c.

302{
303 if (!table)
304 return;
305 table->hdata_free = fn;
306 table->hdata = fn_data;
307}
+ 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
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 317 of file hash.c.

319{
320 if (!table || !strkey)
321 return NULL;
322
323 union HashKey key;
324 key.strkey = table->strdup_keys ? mutt_str_dup(strkey) : strkey;
325 return union_hash_insert(table, key, type, data);
326}
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.
Definition: hash.c:139
char * mutt_str_dup(const char *str)
Copy a string, safely.
Definition: string.c:250
The data item stored in a HashElem.
Definition: hash.h:35
+ 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
tableHash Table (with string keys)
strkeyString key
dataPrivate data associated with the key
Return values
ptrNewly inserted HashElem

Definition at line 335 of file hash.c.

336{
337 return mutt_hash_typed_insert(table, strkey, -1, data);
338}
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.
Definition: hash.c:317
+ 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
tableHash Table (with integer keys)
intkeyInteger key
dataPrivate data associated with the key
Return values
ptrNewly inserted HashElem

Definition at line 347 of file hash.c.

348{
349 if (!table)
350 return NULL;
351 union HashKey key;
352 key.intkey = intkey;
353 return union_hash_insert(table, key, -1, data);
354}
unsigned int intkey
Integer key.
Definition: hash.h:37
+ 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
tableHash Table to search
strkeyString key to search for
Return values
ptrData attached to the HashElem matching the key

Definition at line 362 of file hash.c.

363{
364 if (!table || !strkey)
365 return NULL;
366 union HashKey key;
367 key.strkey = strkey;
368 return union_hash_find(table, key);
369}
static void * union_hash_find(const struct HashTable *table, union HashKey key)
Find the HashElem data in a Hash Table element using a key.
Definition: hash.c:207
+ 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
tableHash Table to search
strkeyString key to search for
Return values
ptrHashElem matching the key

Definition at line 377 of file hash.c.

378{
379 if (!table || !strkey)
380 return NULL;
381 union HashKey key;
382 key.strkey = strkey;
383 return union_hash_find_elem(table, key);
384}
+ 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
tableHash Table to search
intkeyInteger key
Return values
ptrData attached to the HashElem matching the key

Definition at line 392 of file hash.c.

393{
394 if (!table)
395 return NULL;
396 union HashKey key;
397 key.intkey = intkey;
398 return union_hash_find(table, key);
399}
+ 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
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 409 of file hash.c.

410{
411 if (!table || !strkey)
412 return NULL;
413
414 union HashKey key;
415
416 key.strkey = strkey;
417 size_t hash = table->gen_hash(key, table->num_elems);
418 return table->table[hash];
419}
+ 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
tableHash Table to use
strkeyString key to match
dataPrivate data to match (or NULL for any match)

Definition at line 427 of file hash.c.

428{
429 if (!table || !strkey || (strkey[0] == '\0'))
430 return;
431 union HashKey key;
432 // Copy the key because union_hash_delete() may use it after the HashElem is freed.
434 union_hash_delete(table, key, data);
435 FREE(&key.strkey);
436}
static void union_hash_delete(struct HashTable *table, union HashKey key, const void *data)
Remove an element from a Hash Table.
Definition: hash.c:223
+ 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
tableHash Table to use
intkeyInteger key to match
dataPrivate data to match (or NULL for any match)

Definition at line 444 of file hash.c.

445{
446 if (!table)
447 return;
448 union HashKey key;
449 key.intkey = intkey;
450 union_hash_delete(table, key, data);
451}
+ 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]ptrHash Table to be freed

Definition at line 457 of file hash.c.

458{
459 if (!ptr || !*ptr)
460 return;
461
462 struct HashTable *table = *ptr;
463 struct HashElem *elem = NULL, *tmp = NULL;
464
465 for (size_t i = 0; i < table->num_elems; i++)
466 {
467 for (elem = table->table[i]; elem;)
468 {
469 tmp = elem;
470 elem = elem->next;
471 if (table->hdata_free && tmp->data)
472 table->hdata_free(tmp->type, tmp->data, table->hdata);
473 if (table->strdup_keys)
474 FREE(&tmp->key.strkey);
475 FREE(&tmp);
476 }
477 }
478 FREE(&table->table);
479 FREE(ptr);
480}
+ 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
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 489 of file hash.c.

490{
491 if (!table || !state)
492 return NULL;
493
494 if (state->last && state->last->next)
495 {
496 state->last = state->last->next;
497 return state->last;
498 }
499
500 if (state->last)
501 state->index++;
502
503 while (state->index < table->num_elems)
504 {
505 if (table->table[state->index])
506 {
507 state->last = table->table[state->index];
508 return state->last;
509 }
510 state->index++;
511 }
512
513 state->index = 0;
514 state->last = NULL;
515 return NULL;
516}
size_t index
Current position in table.
Definition: hash.h:133
struct HashElem * last
Current element in linked list.
Definition: hash.h:134
+ Here is the caller graph for this function: