1 /** 2 * @file hash_table.h 3 * @author Radek Krejci <rkrejci@cesnet.cz> 4 * @author Michal Vasko <mvasko@cesnet.cz> 5 * @brief libyang hash table 6 * 7 * Copyright (c) 2015 - 2018 CESNET, z.s.p.o. 8 * 9 * This source code is licensed under BSD 3-Clause License (the "License"). 10 * You may not use this file except in compliance with the License. 11 * You may obtain a copy of the License at 12 * 13 * https://opensource.org/licenses/BSD-3-Clause 14 */ 15 16 #ifndef LY_HASH_TABLE_H_ 17 #define LY_HASH_TABLE_H_ 18 19 #include <stdint.h> 20 #include <pthread.h> 21 22 #include "common.h" 23 #include "dict.h" 24 25 /** 26 * @brief Compute hash from (several) string(s). 27 * 28 * Usage: 29 * - init hash to 0 30 * - repeatedly call dict_hash_multi(), provide hash from the last call 31 * - call dict_hash_multi() with key_part = NULL to finish the hash 32 */ 33 uint32_t dict_hash_multi(uint32_t hash, const char *key_part, size_t len); 34 35 /** 36 * @brief Callback for checking hash table values equivalence. 37 * 38 * @param[in] val1_p Pointer to the first value. 39 * @param[in] val2_p Pointer to the second value. 40 * @param[in] mod Whether the operation modifies the hash table (insert or remove) or not (find). 41 * @param[in] cb_data User callback data. 42 * @return 0 on non-equal, non-zero on equal. 43 */ 44 typedef int (*values_equal_cb)(void *val1_p, void *val2_p, int mod, void *cb_data); 45 46 /** when the table is at least this much percent full, it is enlarged (double the size) */ 47 #define LYHT_ENLARGE_PERCENTAGE 75 48 49 /** only once the table is this much percent full, enable shrinking */ 50 #define LYHT_FIRST_SHRINK_PERCENTAGE 50 51 52 /** when the table is less than this much percent full, it is shrunk (half the size) */ 53 #define LYHT_SHRINK_PERCENTAGE 25 54 55 /** when the table has less than this much percent empty records, it is rehashed to get rid of all the invalid records */ 56 #define LYHT_REHASH_PERCENTAGE 2 57 58 /** never shrink beyond this size */ 59 #define LYHT_MIN_SIZE 8 60 61 /** 62 * @brief Generic hash table record. 63 */ 64 struct ht_rec { 65 uint32_t hash; /* hash of the value */ 66 int32_t hits; /* (collision/overflow value count - 1) (a filled entry has 1 hit), 67 * special value (-1) means a deleted record) */ 68 unsigned char val[1]; /* arbitrary-size value */ 69 } _PACKED; 70 71 /** 72 * @brief (Very) generic hash table. 73 * 74 * Hash table with open addressing collision resolution and 75 * linear probing of interval 1 (next free record is used). 76 * Removal is lazy (removed records are only marked). 77 */ 78 struct hash_table { 79 uint32_t used; /* number of values stored in the hash table (filled records) */ 80 uint32_t size; /* always holds 2^x == size (is power of 2), actually number of records allocated */ 81 uint32_t invalid; /* number of invalid records in the hash table (deleted records) */ 82 values_equal_cb val_equal; /* callback for testing value equivalence */ 83 void *cb_data; /* user data callback arbitrary value */ 84 uint16_t resize; /* 0 - resizing is disabled, * 85 * 1 - enlarging is enabled, * 86 * 2 - both shrinking and enlarging is enabled */ 87 uint16_t rec_size; /* real size (in bytes) of one record for accessing recs array */ 88 unsigned char *recs; /* pointer to the hash table itself (array of struct ht_rec) */ 89 }; 90 91 struct dict_rec { 92 char *value; 93 uint32_t refcount; 94 } _PACKED; 95 96 /** 97 * dictionary to store repeating strings 98 */ 99 struct dict_table { 100 struct hash_table *hash_tab; 101 pthread_mutex_t lock; 102 }; 103 104 /** 105 * @brief Initiate content (non-zero values) of the dictionary 106 * 107 * @param[in] dict Dictionary table to initiate 108 */ 109 void lydict_init(struct dict_table *dict); 110 111 /** 112 * @brief Cleanup the dictionary content 113 * 114 * @param[in] dict Dictionary table to cleanup 115 */ 116 void lydict_clean(struct dict_table *dict); 117 118 /** 119 * @brief Get a specific record from a hash table. 120 * 121 * @param[in] recs Hash table records. 122 * @param[in] rec_size Size of one hash table record. 123 * @param[in] idx Index of the record. 124 * @return Record from \p recs on index \p idx. 125 */ 126 struct ht_rec *lyht_get_rec(unsigned char *recs, uint16_t rec_size, uint32_t idx); 127 128 /** 129 * @brief Create new hash table. 130 * 131 * @param[in] size Starting size of the hash table (capacity of values), must be power of 2. 132 * @param[in] val_size Size in bytes of value (the stored hashed item). 133 * @param[in] val_equal Callback for checking value equivalence. 134 * @param[in] cb_data User data always passed to \p val_equal. 135 * @param[in] resize Whether to resize the table on too few/too many records taken. 136 * @return Empty hash table, NULL on error. 137 */ 138 struct hash_table *lyht_new(uint32_t size, uint16_t val_size, values_equal_cb val_equal, void *cb_data, int resize); 139 140 /** 141 * @brief Set hash table value equal callback. 142 * 143 * @param[in] ht Hash table to modify. 144 * @param[in] new_val_equal New callback for checking value equivalence. 145 * @return Previous callback for checking value equivalence. 146 */ 147 values_equal_cb lyht_set_cb(struct hash_table *ht, values_equal_cb new_val_equal); 148 149 /** 150 * @brief Set hash table value equal callback user data. 151 * 152 * @param[in] ht Hash table to modify. 153 * @param[in] new_cb_data New data for values callback. 154 * @return Previous data for values callback. 155 */ 156 void *lyht_set_cb_data(struct hash_table *ht, void *new_cb_data); 157 158 /** 159 * @brief Make a duplicate of an existing hash table. 160 * 161 * @param[in] orig Original hash table to duplicate. 162 * @return Duplicated hash table \p orig, NULL on error. 163 */ 164 struct hash_table *lyht_dup(const struct hash_table *orig); 165 166 /** 167 * @brief Free a hash table. 168 * 169 * @param[in] ht Hash table to be freed. 170 */ 171 void lyht_free(struct hash_table *ht); 172 173 /** 174 * @brief Find a value in a hash table. 175 * 176 * @param[in] ht Hash table to search in. 177 * @param[in] val_p Pointer to the value to find. 178 * @param[in] hash Hash of the stored value. 179 * @param[out] match_p Pointer to the matching value, optional. 180 * @return 0 on success, 1 on not found. 181 */ 182 int lyht_find(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p); 183 184 /** 185 * @brief Find another equal value in the hash table. 186 * 187 * @param[in] ht Hash table to search in. 188 * @param[in] val_p Pointer to the previously found value in \p ht. 189 * @param[in] hash Hash of the previously found value. 190 * @param[out] match_p Pointer to the matching value, optional. 191 * @return 0 on success, 1 on not found. 192 */ 193 int lyht_find_next(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p); 194 195 /** 196 * @brief Insert a value into a hash table. 197 * 198 * @param[in] ht Hash table to insert into. 199 * @param[in] val_p Pointer to the value to insert. Be careful, if the values stored in the hash table 200 * are pointers, \p val_p must be a pointer to a pointer. 201 * @param[in] hash Hash of the stored value. 202 * @param[out] match_p Pointer to the stored value, optional 203 * @return 0 on success, 1 if already inserted, -1 on error. 204 */ 205 int lyht_insert(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p); 206 207 /** 208 * @brief Insert a value into hash table. Same functionality as lyht_insert() 209 * but allows to specify a temporary val equal callback to be used in case the hash table 210 * will be resized after successful insertion. 211 * 212 * @param[in] ht Hash table to insert into. 213 * @param[in] val_p Pointer to the value to insert. Be careful, if the values stored in the hash table 214 * are pointers, \p val_p must be a pointer to a pointer. 215 * @param[in] hash Hash of the stored value. 216 * @param[in] resize_val_equal Val equal callback to use for resizing. 217 * @param[out] match_p Pointer to the stored value, optional 218 * @return 0 on success, 1 if already inserted, -1 on error. 219 */ 220 int lyht_insert_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash, values_equal_cb resize_val_equal, 221 void **match_p); 222 223 /** 224 * @brief Remove a value from a hash table. 225 * 226 * @param[in] ht Hash table to remove from. 227 * @param[in] value_p Pointer to value to be removed. Be careful, if the values stored in the hash table 228 * are pointers, \p value_p must be a pointer to a pointer. 229 * @param[in] hash Hash of the stored value. 230 * @return 0 on success, 1 if value was not found, -1 on error. 231 */ 232 int lyht_remove(struct hash_table *ht, void *val_p, uint32_t hash); 233 234 /** 235 * @brief Remove a value from a hash table. Same functionality as lyht_remove() 236 * but allows to specify a temporary val equal callback to be used in case the hash table 237 * will be resized after successful removal. 238 * 239 * @param[in] ht Hash table to remove from. 240 * @param[in] value_p Pointer to value to be removed. Be careful, if the values stored in the hash table 241 * are pointers, \p value_p must be a pointer to a pointer. 242 * @param[in] hash Hash of the stored value. 243 * @param[in] resize_val_equal Val equal callback to use for resizing. 244 * @return 0 on success, 1 if value was not found, -1 on error. 245 */ 246 int lyht_remove_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash, values_equal_cb resize_val_equal); 247 248 #endif /* LY_HASH_TABLE_H_ */ 249