NeoMutt  2020-09-25
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

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

43 {
44  size_t hash = 0;
45  const unsigned char *s = (const unsigned char *) key.strkey;
46 
47  while (*s != '\0')
48  hash += ((hash << 7) + *s++);
49  hash = (hash * SOME_PRIME) % num_elems;
50 
51  return hash;
52 }
const char * strkey
String key.
Definition: hash.h:36
#define SOME_PRIME
Definition: hash.c:37
+ 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.

58 {
59  return mutt_str_cmp(a.strkey, b.strkey);
60 }
int mutt_str_cmp(const char *a, const char *b)
Compare two strings, safely.
Definition: string.c:567
const char * strkey
String key.
Definition: hash.h:36
+ 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.

66 {
67  size_t hash = 0;
68  const unsigned char *s = (const unsigned char *) key.strkey;
69 
70  while (*s != '\0')
71  hash += ((hash << 7) + tolower(*s++));
72  hash = (hash * SOME_PRIME) % num_elems;
73 
74  return hash;
75 }
const char * strkey
String key.
Definition: hash.h:36
#define SOME_PRIME
Definition: hash.c:37
+ 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.

81 {
82  return mutt_istr_cmp(a.strkey, b.strkey);
83 }
int mutt_istr_cmp(const char *a, const char *b)
Compare two strings ignoring case, safely.
Definition: string.c:580
const char * strkey
String key.
Definition: hash.h:36
+ 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.

89 {
90  return (key.intkey % num_elems);
91 }
unsigned int intkey
Integer key.
Definition: hash.h:37
+ 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.

97 {
98  if (a.intkey == b.intkey)
99  return 0;
100  if (a.intkey < b.intkey)
101  return -1;
102  return 1;
103 }
unsigned int intkey
Integer key.
Definition: hash.h:37
+ 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_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 113 of file hash.c.

114 {
115  struct HashTable *table = mutt_mem_calloc(1, sizeof(struct HashTable));
116  if (num_elems == 0)
117  num_elems = 2;
118  table->num_elems = num_elems;
119  table->table = mutt_mem_calloc(num_elems, sizeof(struct HashElem *));
120  return table;
121 }
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:84
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:86
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:89
The item stored in a Hash Table.
Definition: hash.h:43
+ 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 131 of file hash.c.

133 {
134  if (!table)
135  return NULL; // LCOV_EXCL_LINE
136 
137  struct HashElem *he = mutt_mem_calloc(1, sizeof(struct HashElem));
138  size_t hash = table->gen_hash(key, table->num_elems);
139  he->key = key;
140  he->data = data;
141  he->type = type;
142 
143  if (table->allow_dups)
144  {
145  he->next = table->table[hash];
146  table->table[hash] = he;
147  }
148  else
149  {
150  struct HashElem *tmp = NULL, *last = NULL;
151 
152  for (tmp = table->table[hash], last = NULL; tmp; last = tmp, tmp = tmp->next)
153  {
154  const int rc = table->cmp_key(tmp->key, key);
155  if (rc == 0)
156  {
157  FREE(&he);
158  return NULL;
159  }
160  if (rc > 0)
161  break;
162  }
163  if (last)
164  last->next = he;
165  else
166  table->table[hash] = he;
167  he->next = tmp;
168  }
169  return he;
170 }
union HashKey key
Key representing the data.
Definition: hash.h:46
void * mutt_mem_calloc(size_t nmemb, size_t size)
Allocate zeroed memory on the heap.
Definition: memory.c:50
bool allow_dups
if set, duplicate keys are allowed
Definition: hash.h:88
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:86
struct HashElem * next
Linked List.
Definition: hash.h:48
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:89
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:90
int type
Type of data stored in Hash Table, e.g. DT_STRING.
Definition: hash.h:45
#define FREE(x)
Definition: memory.h:40
The item stored in a Hash Table.
Definition: hash.h:43
hash_cmp_key_t cmp_key
Function to compare two Hash keys.
Definition: hash.h:91
+ 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 178 of file hash.c.

179 {
180  if (!table)
181  return NULL; // LCOV_EXCL_LINE
182 
183  size_t hash = table->gen_hash(key, table->num_elems);
184  struct HashElem *he = table->table[hash];
185  for (; he; he = he->next)
186  {
187  if (table->cmp_key(key, he->key) == 0)
188  return he;
189  }
190  return NULL;
191 }
union HashKey key
Key representing the data.
Definition: hash.h:46
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:86
struct HashElem * next
Linked List.
Definition: hash.h:48
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:89
hash_gen_hash_t gen_hash
Function to generate hash id from the key.
Definition: hash.h:90
The item stored in a Hash Table.
Definition: hash.h:43
hash_cmp_key_t cmp_key
Function to compare two Hash keys.
Definition: hash.h:91
+ 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 199 of file hash.c.

200 {
201  if (!table)
202  return NULL; // LCOV_EXCL_LINE
203  struct HashElem *he = union_hash_find_elem(table, key);
204  if (he)
205  return he->data;
206  return NULL;
207 }
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:178
void * data
User-supplied data.
Definition: hash.h:47
The item stored in a Hash Table.
Definition: hash.h:43
+ 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 215 of file hash.c.

216 {
217  if (!table)
218  return; // LCOV_EXCL_LINE
219 
220  size_t hash = table->gen_hash(key, table->num_elems);
221  struct HashElem *he = table->table[hash];
222  struct HashElem **last = &table->table[hash];
223 
224  while (he)
225  {
226  if (((data == he->data) || !data) && (table->cmp_key(he->key, key) == 0))
227  {
228  *last = he->next;
229  if (table->hdata_free)
230  table->hdata_free(he->type, he->data, table->hdata);
231  if (table->strdup_keys)
232  FREE(&he->key.strkey);
233  FREE(&he);
234 
235  he = *last;
236  }
237  else
238  {
239  last = &he->next;
240  he = he->next;
241  }
242  }
243 }
union HashKey key
Key representing the data.
Definition: hash.h:46
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:86
struct HashElem * next
Linked List.
Definition: hash.h:48
hash_hdata_free_t hdata_free
Function to free a Hash element.
Definition: hash.h:93
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:89
intptr_t hdata
Data to pass to the hdata_free() function.
Definition: hash.h:92
void * data
User-supplied data.
Definition: hash.h:47
const char * strkey
String key.
Definition: hash.h:36
hash_gen_hash_t gen_hash
Function to generate hash id from the key.
Definition: hash.h:90
bool strdup_keys
if set, the key->strkey is strdup()&#39;d
Definition: hash.h:87
int type
Type of data stored in Hash Table, e.g. DT_STRING.
Definition: hash.h:45
#define FREE(x)
Definition: memory.h:40
The item stored in a Hash Table.
Definition: hash.h:43
hash_cmp_key_t cmp_key
Function to compare two Hash keys.
Definition: hash.h:91
+ 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 251 of file hash.c.

252 {
253  struct HashTable *table = hash_new(num_elems);
254  if (flags & MUTT_HASH_STRCASECMP)
255  {
257  table->cmp_key = cmp_case_string_key;
258  }
259  else
260  {
261  table->gen_hash = gen_string_hash;
262  table->cmp_key = cmp_string_key;
263  }
264  if (flags & MUTT_HASH_STRDUP_KEYS)
265  table->strdup_keys = true;
266  if (flags & MUTT_HASH_ALLOW_DUPS)
267  table->allow_dups = true;
268  return table;
269 }
A Hash Table.
Definition: hash.h:84
bool allow_dups
if set, duplicate keys are allowed
Definition: hash.h:88
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:86
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:80
static int cmp_string_key(union HashKey a, union HashKey b)
Compare two string keys - Implements hash_cmp_key_t.
Definition: hash.c:57
#define MUTT_HASH_STRCASECMP
use strcasecmp() to compare keys
Definition: hash.h:98
#define MUTT_HASH_ALLOW_DUPS
allow duplicate keys to be inserted
Definition: hash.h:100
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:89
hash_gen_hash_t gen_hash
Function to generate hash id from the key.
Definition: hash.h:90
bool strdup_keys
if set, the key->strkey is strdup()&#39;d
Definition: hash.h:87
static struct HashTable * hash_new(size_t num_elems)
Create a new Hash Table.
Definition: hash.c:113
#define MUTT_HASH_STRDUP_KEYS
make a copy of the keys
Definition: hash.h:99
hash_cmp_key_t cmp_key
Function to compare two Hash keys.
Definition: hash.h:91
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:42
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:65
+ 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 277 of file hash.c.

278 {
279  struct HashTable *table = hash_new(num_elems);
280  table->gen_hash = gen_int_hash;
281  table->cmp_key = cmp_int_key;
282  if (flags & MUTT_HASH_ALLOW_DUPS)
283  table->allow_dups = true;
284  return table;
285 }
A Hash Table.
Definition: hash.h:84
bool allow_dups
if set, duplicate keys are allowed
Definition: hash.h:88
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:86
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:88
#define MUTT_HASH_ALLOW_DUPS
allow duplicate keys to be inserted
Definition: hash.h:100
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:89
hash_gen_hash_t gen_hash
Function to generate hash id from the key.
Definition: hash.h:90
static struct HashTable * hash_new(size_t num_elems)
Create a new Hash Table.
Definition: hash.c:113
hash_cmp_key_t cmp_key
Function to compare two Hash keys.
Definition: hash.h:91
static int cmp_int_key(union HashKey a, union HashKey b)
Compare two integer keys - Implements hash_cmp_key_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 293 of file hash.c.

294 {
295  if (!table)
296  return;
297  table->hdata_free = fn;
298  table->hdata = fn_data;
299 }
hash_hdata_free_t hdata_free
Function to free a Hash element.
Definition: hash.h:93
intptr_t hdata
Data to pass to the hdata_free() function.
Definition: hash.h:92
+ 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 309 of file hash.c.

311 {
312  if (!table || !strkey)
313  return NULL;
314 
315  union HashKey key;
316  key.strkey = table->strdup_keys ? mutt_str_dup(strkey) : strkey;
317  return union_hash_insert(table, key, type, data);
318 }
char * mutt_str_dup(const char *str)
Copy a string, safely.
Definition: string.c:370
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:131
const char * strkey
String key.
Definition: hash.h:36
bool strdup_keys
if set, the key->strkey is strdup()&#39;d
Definition: hash.h:87
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 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 327 of file hash.c.

328 {
329  return mutt_hash_typed_insert(table, strkey, -1, data);
330 }
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:309
const char * strkey
String key.
Definition: hash.h:36
+ 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 339 of file hash.c.

340 {
341  if (!table)
342  return NULL;
343  union HashKey key;
344  key.intkey = intkey;
345  return union_hash_insert(table, key, -1, data);
346 }
unsigned int intkey
Integer key.
Definition: hash.h:37
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:131
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 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 354 of file hash.c.

355 {
356  if (!table || !strkey)
357  return NULL;
358  union HashKey key;
359  key.strkey = strkey;
360  return union_hash_find(table, key);
361 }
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:199
const char * strkey
String key.
Definition: hash.h:36
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 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 369 of file hash.c.

370 {
371  if (!table || !strkey)
372  return NULL;
373  union HashKey key;
374  key.strkey = strkey;
375  return union_hash_find_elem(table, key);
376 }
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:178
const char * strkey
String key.
Definition: hash.h:36
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 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 384 of file hash.c.

385 {
386  if (!table)
387  return NULL;
388  union HashKey key;
389  key.intkey = intkey;
390  return union_hash_find(table, key);
391 }
unsigned int intkey
Integer key.
Definition: hash.h:37
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:199
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 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 401 of file hash.c.

402 {
403  if (!table || !strkey)
404  return NULL;
405 
406  union HashKey key;
407 
408  key.strkey = strkey;
409  size_t hash = table->gen_hash(key, table->num_elems);
410  return table->table[hash];
411 }
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:86
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:89
const char * strkey
String key.
Definition: hash.h:36
hash_gen_hash_t gen_hash
Function to generate hash id from the key.
Definition: hash.h:90
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 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 419 of file hash.c.

420 {
421  if (!table || !strkey)
422  return;
423  union HashKey key;
424  key.strkey = strkey;
425  union_hash_delete(table, key, data);
426 }
static void union_hash_delete(struct HashTable *table, union HashKey key, const void *data)
Remove an element from a Hash Table.
Definition: hash.c:215
const char * strkey
String key.
Definition: hash.h:36
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_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 434 of file hash.c.

435 {
436  if (!table)
437  return;
438  union HashKey key;
439  key.intkey = intkey;
440  union_hash_delete(table, key, data);
441 }
unsigned int intkey
Integer key.
Definition: hash.h:37
static void union_hash_delete(struct HashTable *table, union HashKey key, const void *data)
Remove an element from a Hash Table.
Definition: hash.c:215
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_free()

void mutt_hash_free ( struct HashTable **  ptr)

Free a hash table.

Parameters
[out]ptrHash Table to be freed

Definition at line 447 of file hash.c.

448 {
449  if (!ptr || !*ptr)
450  return;
451 
452  struct HashTable *table = *ptr;
453  struct HashElem *elem = NULL, *tmp = NULL;
454 
455  for (size_t i = 0; i < table->num_elems; i++)
456  {
457  for (elem = table->table[i]; elem;)
458  {
459  tmp = elem;
460  elem = elem->next;
461  if (table->hdata_free)
462  table->hdata_free(tmp->type, tmp->data, table->hdata);
463  if (table->strdup_keys)
464  FREE(&tmp->key.strkey);
465  FREE(&tmp);
466  }
467  }
468  FREE(&table->table);
469  FREE(ptr);
470 }
A Hash Table.
Definition: hash.h:84
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:86
struct HashElem * next
Linked List.
Definition: hash.h:48
hash_hdata_free_t hdata_free
Function to free a Hash element.
Definition: hash.h:93
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:89
intptr_t hdata
Data to pass to the hdata_free() function.
Definition: hash.h:92
bool strdup_keys
if set, the key->strkey is strdup()&#39;d
Definition: hash.h:87
#define FREE(x)
Definition: memory.h:40
The item stored in a Hash Table.
Definition: hash.h:43
+ 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 479 of file hash.c.

480 {
481  if (!table || !state)
482  return NULL;
483 
484  if (state->last && state->last->next)
485  {
486  state->last = state->last->next;
487  return state->last;
488  }
489 
490  if (state->last)
491  state->index++;
492 
493  while (state->index < table->num_elems)
494  {
495  if (table->table[state->index])
496  {
497  state->last = table->table[state->index];
498  return state->last;
499  }
500  state->index++;
501  }
502 
503  state->index = 0;
504  state->last = NULL;
505  return NULL;
506 }
size_t num_elems
Number of elements in the Hash Table.
Definition: hash.h:86
struct HashElem * next
Linked List.
Definition: hash.h:48
struct HashElem * last
Current element in linked list.
Definition: hash.h:122
struct HashElem ** table
Array of Hash keys.
Definition: hash.h:89
size_t index
Current position in table.
Definition: hash.h:121
+ Here is the caller graph for this function: