Mercurial > dovecot > core-2.2

annotate src/lib/hash.h @ 22955:812e5c961328

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fts: Indexing virtual mailbox didn't always index the last mails
author Timo Sirainen <timo.sirainen@dovecot.fi>
date Thu, 03 May 2018 18:33:00 +0300
parents 77638cc62ca8
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
6410
e4eb71ae8e96 Changed .h ifdef/defines to use <NAME>_H format.
Timo Sirainen <tss@iki.fi>
parents: 3906
diff changeset
1 #ifndef HASH_H
e4eb71ae8e96 Changed .h ifdef/defines to use <NAME>_H format.
Timo Sirainen <tss@iki.fi>
parents: 3906
diff changeset
2 #define HASH_H
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
3
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
4 struct hash_table;
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
5
18090
77638cc62ca8 lib: array/hash - enable typof checks for more compilers
Phil Carmody <phil@dovecot.fi>
parents: 18089
diff changeset
6 #ifdef HAVE_TYPEOF
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
7 # define HASH_VALUE_CAST(table) (typeof((table)._value))
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
8 #else
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
9 # define HASH_VALUE_CAST(table)
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
10 #endif
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
11
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
12 /* Returns hash code. */
1038
60646878858e Function typedefs now define them as functions, not function pointers.
Timo Sirainen <tss@iki.fi>
parents: 953
diff changeset
13 typedef unsigned int hash_callback_t(const void *p);
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
14 /* Returns 0 if the pointers are equal. */
1038
60646878858e Function typedefs now define them as functions, not function pointers.
Timo Sirainen <tss@iki.fi>
parents: 953
diff changeset
15 typedef int hash_cmp_callback_t(const void *p1, const void *p2);
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
16
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
17 /* Create a new hash table. If initial_size is 0, the default value is used.
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
18 table_pool is used to allocate/free large hash tables, node_pool is used
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
19 for smaller allocations and can also be alloconly pool. The pools must not
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
20 be free'd before hash_table_destroy() is called. */
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
21 void hash_table_create(struct hash_table **table_r, pool_t node_pool,
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
22 unsigned int initial_size,
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
23 hash_callback_t *hash_cb,
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
24 hash_cmp_callback_t *key_compare_cb);
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
25 #if defined (__GNUC__) && !defined(__cplusplus)
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
26 # define hash_table_create(table, pool, size, hash_cb, key_cmp_cb) \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
27 ({(void)COMPILE_ERROR_IF_TRUE( \
14923
96fd2c3bf932 Reverted "support for non-pointers" part of the hash table API changes.
Timo Sirainen <tss@iki.fi>
parents: 14918
diff changeset
28 sizeof((*table)._key) != sizeof(void *) || \
96fd2c3bf932 Reverted "support for non-pointers" part of the hash table API changes.
Timo Sirainen <tss@iki.fi>
parents: 14918
diff changeset
29 sizeof((*table)._value) != sizeof(void *)); \
15902
ecd923186510 Previous "duplicate const" fix accidentally deleted some checking code instead of fixing it.
Timo Sirainen <tss@iki.fi>
parents: 15901
diff changeset
30 (void)COMPILE_ERROR_IF_TRUE( \
ecd923186510 Previous "duplicate const" fix accidentally deleted some checking code instead of fixing it.
Timo Sirainen <tss@iki.fi>
parents: 15901
diff changeset
31 !__builtin_types_compatible_p(typeof(&key_cmp_cb), \
ecd923186510 Previous "duplicate const" fix accidentally deleted some checking code instead of fixing it.
Timo Sirainen <tss@iki.fi>
parents: 15901
diff changeset
32 int (*)(typeof((*table)._key), typeof((*table)._key))) && \
ecd923186510 Previous "duplicate const" fix accidentally deleted some checking code instead of fixing it.
Timo Sirainen <tss@iki.fi>
parents: 15901
diff changeset
33 !__builtin_types_compatible_p(typeof(&key_cmp_cb), \
15935
4baf0183f13d Reverted the recent hash.h changes. Instead use -Wno-duplicate-decl-specifier with clang.
Timo Sirainen <tss@iki.fi>
parents: 15902
diff changeset
34 int (*)(typeof((*table)._const_key), typeof((*table)._const_key)))); \
15902
ecd923186510 Previous "duplicate const" fix accidentally deleted some checking code instead of fixing it.
Timo Sirainen <tss@iki.fi>
parents: 15901
diff changeset
35 (void)COMPILE_ERROR_IF_TRUE( \
ecd923186510 Previous "duplicate const" fix accidentally deleted some checking code instead of fixing it.
Timo Sirainen <tss@iki.fi>
parents: 15901
diff changeset
36 !__builtin_types_compatible_p(typeof(&hash_cb), \
ecd923186510 Previous "duplicate const" fix accidentally deleted some checking code instead of fixing it.
Timo Sirainen <tss@iki.fi>
parents: 15901
diff changeset
37 unsigned int (*)(typeof((*table)._key))) && \
ecd923186510 Previous "duplicate const" fix accidentally deleted some checking code instead of fixing it.
Timo Sirainen <tss@iki.fi>
parents: 15901
diff changeset
38 !__builtin_types_compatible_p(typeof(&hash_cb), \
15935
4baf0183f13d Reverted the recent hash.h changes. Instead use -Wno-duplicate-decl-specifier with clang.
Timo Sirainen <tss@iki.fi>
parents: 15902
diff changeset
39 unsigned int (*)(typeof((*table)._const_key)))); \
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
40 hash_table_create(&(*table)._table, pool, size, \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
41 (hash_callback_t *)hash_cb, \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
42 (hash_cmp_callback_t *)key_cmp_cb);})
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
43 #else
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
44 # define hash_table_create(table, pool, size, hash_cb, key_cmp_cb) \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
45 hash_table_create(&(*table)._table, pool, size, \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
46 (hash_callback_t *)hash_cb, \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
47 (hash_cmp_callback_t *)key_cmp_cb)
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
48 #endif
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
49
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
50 /* Create hash table where comparisons are done directly with the pointers. */
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
51 void hash_table_create_direct(struct hash_table **table_r, pool_t node_pool,
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
52 unsigned int initial_size);
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
53 #if defined (__GNUC__) && !defined(__cplusplus)
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
54 # define hash_table_create_direct(table, pool, size) \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
55 ({(void)COMPILE_ERROR_IF_TRUE( \
14923
96fd2c3bf932 Reverted "support for non-pointers" part of the hash table API changes.
Timo Sirainen <tss@iki.fi>
parents: 14918
diff changeset
56 sizeof((*table)._key) != sizeof(void *) || \
96fd2c3bf932 Reverted "support for non-pointers" part of the hash table API changes.
Timo Sirainen <tss@iki.fi>
parents: 14918
diff changeset
57 sizeof((*table)._value) != sizeof(void *)); \
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
58 hash_table_create_direct(&(*table)._table, pool, size);})
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
59 #else
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
60 # define hash_table_create_direct(table, pool, size) \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
61 hash_table_create_direct(&(*table)._table, pool, size)
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
62 #endif
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
63
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
64 #define hash_table_is_created(table) \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
65 ((table)._table != NULL)
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
66
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
67 void hash_table_destroy(struct hash_table **table);
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
68 #define hash_table_destroy(table) \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
69 hash_table_destroy(&(*table)._table)
949
e601f13d95b1 hash_clear() can now be used to drop the memory allocated using node_pool.
Timo Sirainen <tss@iki.fi>
parents: 945
diff changeset
70 /* Remove all nodes from hash table. If free_collisions is TRUE, the
16318
25679980d267 hash_table_clear(): Added a comment about API usage.
Timo Sirainen <tss@iki.fi>
parents: 15935
diff changeset
71 memory allocated from node_pool is freed, or discarded with alloconly pools.
25679980d267 hash_table_clear(): Added a comment about API usage.
Timo Sirainen <tss@iki.fi>
parents: 15935
diff changeset
72 WARNING: If you p_clear() the node_pool, the free_collisions must be TRUE. */
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
73 void hash_table_clear(struct hash_table *table, bool free_collisions);
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
74 #define hash_table_clear(table, free_collisions) \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
75 hash_table_clear((table)._table, free_collisions)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
76
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
77 void *hash_table_lookup(const struct hash_table *table, const void *key) ATTR_PURE;
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
78 #define hash_table_lookup(table, key) \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
79 HASH_VALUE_CAST(table)hash_table_lookup((table)._table, \
15935
4baf0183f13d Reverted the recent hash.h changes. Instead use -Wno-duplicate-decl-specifier with clang.
Timo Sirainen <tss@iki.fi>
parents: 15902
diff changeset
80 (const void *)((const char *)(key) + COMPILE_ERROR_IF_TYPES2_NOT_COMPATIBLE((table)._key, (table)._const_key, key)))
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
81
14923
96fd2c3bf932 Reverted "support for non-pointers" part of the hash table API changes.
Timo Sirainen <tss@iki.fi>
parents: 14918
diff changeset
82 bool hash_table_lookup_full(const struct hash_table *table,
96fd2c3bf932 Reverted "support for non-pointers" part of the hash table API changes.
Timo Sirainen <tss@iki.fi>
parents: 14918
diff changeset
83 const void *lookup_key,
96fd2c3bf932 Reverted "support for non-pointers" part of the hash table API changes.
Timo Sirainen <tss@iki.fi>
parents: 14918
diff changeset
84 void **orig_key_r, void **value_r);
16349
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
85 #ifndef __cplusplus
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
86 # define hash_table_lookup_full(table, lookup_key, orig_key_r, value_r) \
14923
96fd2c3bf932 Reverted "support for non-pointers" part of the hash table API changes.
Timo Sirainen <tss@iki.fi>
parents: 14918
diff changeset
87 hash_table_lookup_full((table)._table, \
18089
922ac3245e17 lib: array/hash - protect macro parameters
Phil Carmody <phil@dovecot.fi>
parents: 17454
diff changeset
88 (void *)((const char *)(lookup_key) + \
922ac3245e17 lib: array/hash - protect macro parameters
Phil Carmody <phil@dovecot.fi>
parents: 17454
diff changeset
89 COMPILE_ERROR_IF_TYPES2_NOT_COMPATIBLE((table)._const_key, (table)._key, lookup_key)), \
922ac3245e17 lib: array/hash - protect macro parameters
Phil Carmody <phil@dovecot.fi>
parents: 17454
diff changeset
90 (void *)((orig_key_r) + \
922ac3245e17 lib: array/hash - protect macro parameters
Phil Carmody <phil@dovecot.fi>
parents: 17454
diff changeset
91 COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE((table)._keyp, orig_key_r) + \
922ac3245e17 lib: array/hash - protect macro parameters
Phil Carmody <phil@dovecot.fi>
parents: 17454
diff changeset
92 COMPILE_ERROR_IF_TRUE(sizeof(*(orig_key_r)) != sizeof(void *))), \
922ac3245e17 lib: array/hash - protect macro parameters
Phil Carmody <phil@dovecot.fi>
parents: 17454
diff changeset
93 (void *)((value_r) + \
922ac3245e17 lib: array/hash - protect macro parameters
Phil Carmody <phil@dovecot.fi>
parents: 17454
diff changeset
94 COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE((table)._valuep, value_r) + \
922ac3245e17 lib: array/hash - protect macro parameters
Phil Carmody <phil@dovecot.fi>
parents: 17454
diff changeset
95 COMPILE_ERROR_IF_TRUE(sizeof(*(value_r)) != sizeof(void *))))
16349
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
96 #else
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
97 /* C++ requires (void **) casting, but that's not possible with strict
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
98 aliasing, so .. we'll just disable the type checks */
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
99 # define hash_table_lookup_full(table, lookup_key, orig_key_r, value_r) \
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
100 hash_table_lookup_full((table)._table, lookup_key, orig_key_r, value_r)
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
101 #endif
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
102
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
103 /* Insert/update node in hash table. The difference is that hash_table_insert()
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
104 replaces the key in table to given one, while hash_table_update() doesnt. */
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
105 void hash_table_insert(struct hash_table *table, void *key, void *value);
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
106 void hash_table_update(struct hash_table *table, void *key, void *value);
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
107 #define hash_table_insert(table, key, value) \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
108 hash_table_insert((table)._table, \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
109 (void *)((char*)(key) + COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE((table)._key, key)), \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
110 (void *)((char*)(value) + COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE((table)._value, value)))
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
111 #define hash_table_update(table, key, value) \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
112 hash_table_update((table)._table, \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
113 (void *)((char *)(key) + COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE((table)._key, key)), \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
114 (void *)((char *)(value) + COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE((table)._value, value)))
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
115
17454
5c617a5036f3 lib: Changed hash_table_remove() "key not found" panic to be in a macro itself.
Timo Sirainen <tss@iki.fi>
parents: 16349
diff changeset
116 bool hash_table_try_remove(struct hash_table *table, const void *key);
5c617a5036f3 lib: Changed hash_table_remove() "key not found" panic to be in a macro itself.
Timo Sirainen <tss@iki.fi>
parents: 16349
diff changeset
117 #define hash_table_try_remove(table, key) \
5c617a5036f3 lib: Changed hash_table_remove() "key not found" panic to be in a macro itself.
Timo Sirainen <tss@iki.fi>
parents: 16349
diff changeset
118 hash_table_try_remove((table)._table, \
5c617a5036f3 lib: Changed hash_table_remove() "key not found" panic to be in a macro itself.
Timo Sirainen <tss@iki.fi>
parents: 16349
diff changeset
119 (const void *)((const char *)(key) + COMPILE_ERROR_IF_TYPES2_NOT_COMPATIBLE((table)._const_key, (table)._key, key)))
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
120 #define hash_table_remove(table, key) \
17454
5c617a5036f3 lib: Changed hash_table_remove() "key not found" panic to be in a macro itself.
Timo Sirainen <tss@iki.fi>
parents: 16349
diff changeset
121 STMT_START { \
5c617a5036f3 lib: Changed hash_table_remove() "key not found" panic to be in a macro itself.
Timo Sirainen <tss@iki.fi>
parents: 16349
diff changeset
122 if (unlikely(!hash_table_try_remove(table, key))) \
5c617a5036f3 lib: Changed hash_table_remove() "key not found" panic to be in a macro itself.
Timo Sirainen <tss@iki.fi>
parents: 16349
diff changeset
123 i_panic("key not found from hash"); \
5c617a5036f3 lib: Changed hash_table_remove() "key not found" panic to be in a macro itself.
Timo Sirainen <tss@iki.fi>
parents: 16349
diff changeset
124 } STMT_END
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
125 unsigned int hash_table_count(const struct hash_table *table) ATTR_PURE;
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
126 #define hash_table_count(table) \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
127 hash_table_count((table)._table)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
128
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
129 /* Iterates through all nodes in hash table. You may safely call hash_table_*()
1897
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1038
diff changeset
130 functions while iterating, but if you add any new nodes, they may or may
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1038
diff changeset
131 not be called for in this iteration. */
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
132 struct hash_iterate_context *hash_table_iterate_init(struct hash_table *table);
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
133 #define hash_table_iterate_init(table) \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
134 hash_table_iterate_init((table)._table)
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
135 bool hash_table_iterate(struct hash_iterate_context *ctx,
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
136 void **key_r, void **value_r);
16349
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
137 #ifndef __cplusplus
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
138 # define hash_table_iterate(ctx, table, key_r, value_r) \
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
139 hash_table_iterate(ctx, \
18089
922ac3245e17 lib: array/hash - protect macro parameters
Phil Carmody <phil@dovecot.fi>
parents: 17454
diff changeset
140 (void *)((key_r) + \
922ac3245e17 lib: array/hash - protect macro parameters
Phil Carmody <phil@dovecot.fi>
parents: 17454
diff changeset
141 COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE((table)._keyp, key_r) + \
922ac3245e17 lib: array/hash - protect macro parameters
Phil Carmody <phil@dovecot.fi>
parents: 17454
diff changeset
142 COMPILE_ERROR_IF_TRUE(sizeof(*(key_r)) != sizeof(void *)) + \
922ac3245e17 lib: array/hash - protect macro parameters
Phil Carmody <phil@dovecot.fi>
parents: 17454
diff changeset
143 COMPILE_ERROR_IF_TRUE(sizeof(*(value_r)) != sizeof(void *))), \
16349
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
144 (void *)((value_r) + COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE((table)._valuep, value_r)))
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
145 #else
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
146 /* C++ requires (void **) casting, but that's not possible with strict
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
147 aliasing, so .. we'll just disable the type checks */
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
148 # define hash_table_iterate(ctx, table, key_r, value_r) \
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
149 hash_table_iterate(ctx, key_r, value_r)
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
150 #endif
bf98dc25e3e4 Avoid strict aliasing warnings.
Timo Sirainen <tss@iki.fi>
parents: 16318
diff changeset
151
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
152 void hash_table_iterate_deinit(struct hash_iterate_context **ctx);
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
153
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
154 /* Hash table isn't resized, and removed nodes aren't removed from
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
155 the list while hash table is freezed. Supports nesting. */
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
156 void hash_table_freeze(struct hash_table *table);
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
157 void hash_table_thaw(struct hash_table *table);
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
158 #define hash_table_freeze(table) \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
159 hash_table_freeze((table)._table)
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
160 #define hash_table_thaw(table) \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
161 hash_table_thaw((table)._table)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
162
3616
906b87e236bf Added hash_copy() and added some consts
Timo Sirainen <tss@iki.fi>
parents: 1897
diff changeset
163 /* Copy all nodes from one hash table to another */
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
164 void hash_table_copy(struct hash_table *dest, struct hash_table *src);
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
165 #define hash_table_copy(table1, table2) \
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
166 hash_table_copy((table1)._table, (table2)._table)
3616
906b87e236bf Added hash_copy() and added some consts
Timo Sirainen <tss@iki.fi>
parents: 1897
diff changeset
167
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
168 /* hash function for strings */
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
169 unsigned int str_hash(const char *p) ATTR_PURE;
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
170 unsigned int strcase_hash(const char *p) ATTR_PURE;
13222
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 8594
diff changeset
171 /* a generic hash for a given memory block */
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 8594
diff changeset
172 unsigned int mem_hash(const void *p, unsigned int size) ATTR_PURE;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
173
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
174 #endif