1 #ifndef HASH_H 2 #define HASH_H 3 4 struct hash_table; 5 6 #ifdef HAVE_TYPEOF 7 # define HASH_VALUE_CAST(table) (typeof((table)._value)) 8 #else 9 # define HASH_VALUE_CAST(table) 10 #endif 11 12 /* Returns hash code. */ 13 typedef unsigned int hash_callback_t(const void *p); 14 /* Returns 0 if the pointers are equal. */ 15 typedef int hash_cmp_callback_t(const void *p1, const void *p2); 16 17 /* Create a new hash table. If initial_size is 0, the default value is used. 18 table_pool is used to allocate/free large hash tables, node_pool is used 19 for smaller allocations and can also be alloconly pool. The pools must not 20 be free'd before hash_table_destroy() is called. */ 21 void hash_table_create(struct hash_table **table_r, pool_t node_pool, 22 unsigned int initial_size, 23 hash_callback_t *hash_cb, 24 hash_cmp_callback_t *key_compare_cb); 25 #define hash_table_create(table, pool, size, hash_cb, key_cmp_cb) \ 26 TYPE_CHECKS(void, \ 27 COMPILE_ERROR_IF_TRUE( \ 28 sizeof((*table)._key) != sizeof(void *) || \ 29 sizeof((*table)._value) != sizeof(void *)) || \ 30 COMPILE_ERROR_IF_TRUE( \ 31 !__builtin_types_compatible_p(typeof(&key_cmp_cb), \ 32 int (*)(typeof((*table)._key), typeof((*table)._key))) && \ 33 !__builtin_types_compatible_p(typeof(&key_cmp_cb), \ 34 int (*)(typeof((*table)._const_key), typeof((*table)._const_key)))) || \ 35 COMPILE_ERROR_IF_TRUE( \ 36 !__builtin_types_compatible_p(typeof(&hash_cb), \ 37 unsigned int (*)(typeof((*table)._key))) && \ 38 !__builtin_types_compatible_p(typeof(&hash_cb), \ 39 unsigned int (*)(typeof((*table)._const_key)))), \ 40 hash_table_create(&(*table)._table, pool, size, \ 41 (hash_callback_t *)hash_cb, \ 42 (hash_cmp_callback_t *)key_cmp_cb)) 43 44 /* Create hash table where comparisons are done directly with the pointers. */ 45 void hash_table_create_direct(struct hash_table **table_r, pool_t node_pool, 46 unsigned int initial_size); 47 #define hash_table_create_direct(table, pool, size) \ 48 TYPE_CHECKS(void, \ 49 COMPILE_ERROR_IF_TRUE( \ 50 sizeof((*table)._key) != sizeof(void *) || \ 51 sizeof((*table)._value) != sizeof(void *)), \ 52 hash_table_create_direct(&(*table)._table, pool, size)) 53 54 #define hash_table_is_created(table) \ 55 ((table)._table != NULL) 56 57 void hash_table_destroy(struct hash_table **table); 58 #define hash_table_destroy(table) \ 59 hash_table_destroy(&(*table)._table) 60 /* Remove all nodes from hash table. If free_collisions is TRUE, the 61 memory allocated from node_pool is freed, or discarded with alloconly pools. 62 WARNING: If you p_clear() the node_pool, the free_collisions must be TRUE. */ 63 void hash_table_clear(struct hash_table *table, bool free_collisions); 64 #define hash_table_clear(table, free_collisions) \ 65 hash_table_clear((table)._table, free_collisions) 66 67 void *hash_table_lookup(const struct hash_table *table, const void *key) ATTR_PURE; 68 #define hash_table_lookup(table, key) \ 69 TYPE_CHECKS(void *, \ 70 COMPILE_ERROR_IF_TYPES2_NOT_COMPATIBLE((table)._key, (table)._const_key, key), \ 71 HASH_VALUE_CAST(table)hash_table_lookup((table)._table, (key))) 72 73 bool hash_table_lookup_full(const struct hash_table *table, 74 const void *lookup_key, 75 void **orig_key_r, void **value_r); 76 #ifndef __cplusplus 77 # define hash_table_lookup_full(table, lookup_key, orig_key_r, value_r) \ 78 TYPE_CHECKS(bool, \ 79 COMPILE_ERROR_IF_TYPES2_NOT_COMPATIBLE((table)._const_key, (table)._key, lookup_key) || \ 80 COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE((table)._keyp, orig_key_r) || \ 81 COMPILE_ERROR_IF_TRUE(sizeof(*(orig_key_r)) != sizeof(void *)) || \ 82 COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE((table)._valuep, value_r) || \ 83 COMPILE_ERROR_IF_TRUE(sizeof(*(value_r)) != sizeof(void *)), \ 84 hash_table_lookup_full((table)._table, \ 85 (lookup_key), (void *)(orig_key_r), (void *)(value_r))) 86 #else 87 /* C++ requires (void **) casting, but that's not possible with strict 88 aliasing, so .. we'll just disable the type checks */ 89 # define hash_table_lookup_full(table, lookup_key, orig_key_r, value_r) \ 90 hash_table_lookup_full((table)._table, lookup_key, orig_key_r, value_r) 91 #endif 92 93 /* Suppose to insert a new key-value node to the hash table. 94 If the key already exists, assert-crash. */ 95 void hash_table_insert(struct hash_table *table, void *key, void *value); 96 /* If the key doesn't exists, do the exact same as hash_table_insert() 97 If the key already exists, preserve the original key and update only the value.*/ 98 void hash_table_update(struct hash_table *table, void *key, void *value); 99 #define hash_table_insert(table, key, value) \ 100 TYPE_CHECKS(void, \ 101 COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE((table)._key, key) || \ 102 COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE((table)._value, value), \ 103 hash_table_insert((table)._table, (void *)(key), (void *)(value))) 104 #define hash_table_update(table, key, value) \ 105 TYPE_CHECKS(void, \ 106 COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE((table)._key, key) || \ 107 COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE((table)._value, value), \ 108 hash_table_update((table)._table, (void *)(key), (void *)(value))) 109 110 bool hash_table_try_remove(struct hash_table *table, const void *key); 111 #define hash_table_try_remove(table, key) \ 112 TYPE_CHECKS(bool, \ 113 COMPILE_ERROR_IF_TYPES2_NOT_COMPATIBLE((table)._const_key, (table)._key, key), \ 114 hash_table_try_remove((table)._table, (const void *)(key))) 115 #define hash_table_remove(table, key) \ 116 STMT_START { \ 117 if (unlikely(!hash_table_try_remove(table, key))) \ 118 i_panic("key not found from hash"); \ 119 } STMT_END 120 unsigned int hash_table_count(const struct hash_table *table) ATTR_PURE; 121 #define hash_table_count(table) \ 122 hash_table_count((table)._table) 123 124 /* Iterates through all nodes in hash table. You may safely call hash_table_*() 125 functions while iterating, but if you add any new nodes, they may or may 126 not be called for in this iteration. */ 127 struct hash_iterate_context *hash_table_iterate_init(struct hash_table *table); 128 #define hash_table_iterate_init(table) \ 129 hash_table_iterate_init((table)._table) 130 bool hash_table_iterate(struct hash_iterate_context *ctx, 131 void **key_r, void **value_r); 132 #ifndef __cplusplus 133 # define hash_table_iterate(ctx, table, key_r, value_r) \ 134 TYPE_CHECKS(bool, \ 135 COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE((table)._keyp, key_r) || \ 136 COMPILE_ERROR_IF_TRUE(sizeof(*(key_r)) != sizeof(void *)) || \ 137 COMPILE_ERROR_IF_TRUE(sizeof(*(value_r)) != sizeof(void *)) || \ 138 COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE((table)._valuep, value_r), \ 139 hash_table_iterate(ctx, (void *)(key_r), (void *)(value_r))) 140 #else 141 /* C++ requires (void **) casting, but that's not possible with strict 142 aliasing, so .. we'll just disable the type checks */ 143 # define hash_table_iterate(ctx, table, key_r, value_r) \ 144 hash_table_iterate(ctx, key_r, value_r) 145 #endif 146 147 void hash_table_iterate_deinit(struct hash_iterate_context **ctx); 148 149 /* Hash table isn't resized, and removed nodes aren't removed from 150 the list while hash table is freezed. Supports nesting. */ 151 void hash_table_freeze(struct hash_table *table); 152 void hash_table_thaw(struct hash_table *table); 153 #define hash_table_freeze(table) \ 154 hash_table_freeze((table)._table) 155 #define hash_table_thaw(table) \ 156 hash_table_thaw((table)._table) 157 158 /* Copy all nodes from one hash table to another */ 159 void hash_table_copy(struct hash_table *dest, struct hash_table *src); 160 #define hash_table_copy(table1, table2) \ 161 hash_table_copy((table1)._table, (table2)._table) 162 163 /* hash function for strings */ 164 unsigned int str_hash(const char *p) ATTR_PURE; 165 unsigned int strcase_hash(const char *p) ATTR_PURE; 166 167 /* fast hash function which uppercases a-z. Does not work well 168 with input that consists from non number/letter input, as 169 it works by dropping 0x20. */ 170 unsigned int strfastcase_hash(const char *p) ATTR_PURE; 171 172 /* a generic hash for a given memory block */ 173 unsigned int mem_hash(const void *p, unsigned int size) ATTR_PURE; 174 175 #endif 176