Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 1 | /* The implementation of the hash table (_Py_hashtable_t) is based on the |
| 2 | cfuhash project: |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 3 | http://sourceforge.net/projects/libcfu/ |
| 4 | |
| 5 | Copyright of cfuhash: |
| 6 | ---------------------------------- |
| 7 | Creation date: 2005-06-24 21:22:40 |
| 8 | Authors: Don |
| 9 | Change log: |
| 10 | |
| 11 | Copyright (c) 2005 Don Owens |
| 12 | All rights reserved. |
| 13 | |
| 14 | This code is released under the BSD license: |
| 15 | |
| 16 | Redistribution and use in source and binary forms, with or without |
| 17 | modification, are permitted provided that the following conditions |
| 18 | are met: |
| 19 | |
| 20 | * Redistributions of source code must retain the above copyright |
| 21 | notice, this list of conditions and the following disclaimer. |
| 22 | |
| 23 | * Redistributions in binary form must reproduce the above |
| 24 | copyright notice, this list of conditions and the following |
| 25 | disclaimer in the documentation and/or other materials provided |
| 26 | with the distribution. |
| 27 | |
| 28 | * Neither the name of the author nor the names of its |
| 29 | contributors may be used to endorse or promote products derived |
| 30 | from this software without specific prior written permission. |
| 31 | |
| 32 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 33 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 34 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS |
| 35 | FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE |
| 36 | COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, |
| 37 | INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
| 38 | (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR |
| 39 | SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| 40 | HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
| 41 | STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| 42 | ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
| 43 | OF THE POSSIBILITY OF SUCH DAMAGE. |
| 44 | ---------------------------------- |
| 45 | */ |
| 46 | |
| 47 | #include "Python.h" |
| 48 | #include "hashtable.h" |
| 49 | |
| 50 | #define HASHTABLE_MIN_SIZE 16 |
| 51 | #define HASHTABLE_HIGH 0.50 |
| 52 | #define HASHTABLE_LOW 0.10 |
| 53 | #define HASHTABLE_REHASH_FACTOR 2.0 / (HASHTABLE_LOW + HASHTABLE_HIGH) |
| 54 | |
| 55 | #define BUCKETS_HEAD(SLIST) \ |
| 56 | ((_Py_hashtable_entry_t *)_Py_SLIST_HEAD(&(SLIST))) |
| 57 | #define TABLE_HEAD(HT, BUCKET) \ |
| 58 | ((_Py_hashtable_entry_t *)_Py_SLIST_HEAD(&(HT)->buckets[BUCKET])) |
| 59 | #define ENTRY_NEXT(ENTRY) \ |
| 60 | ((_Py_hashtable_entry_t *)_Py_SLIST_ITEM_NEXT(ENTRY)) |
| 61 | #define HASHTABLE_ITEM_SIZE(HT) \ |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 62 | (sizeof(_Py_hashtable_entry_t) + (HT)->key_size + (HT)->data_size) |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 63 | |
Victor Stinner | 5dacbd4 | 2016-03-23 09:52:13 +0100 | [diff] [blame] | 64 | #define ENTRY_READ_PDATA(TABLE, ENTRY, DATA_SIZE, PDATA) \ |
| 65 | do { \ |
| 66 | assert((DATA_SIZE) == (TABLE)->data_size); \ |
Christian Heimes | f051e43 | 2016-09-13 20:22:02 +0200 | [diff] [blame] | 67 | memcpy((PDATA), _Py_HASHTABLE_ENTRY_PDATA(TABLE, (ENTRY)), \ |
Victor Stinner | 5dacbd4 | 2016-03-23 09:52:13 +0100 | [diff] [blame] | 68 | (DATA_SIZE)); \ |
| 69 | } while (0) |
| 70 | |
| 71 | #define ENTRY_WRITE_PDATA(TABLE, ENTRY, DATA_SIZE, PDATA) \ |
| 72 | do { \ |
| 73 | assert((DATA_SIZE) == (TABLE)->data_size); \ |
Christian Heimes | f051e43 | 2016-09-13 20:22:02 +0200 | [diff] [blame] | 74 | memcpy((void *)_Py_HASHTABLE_ENTRY_PDATA((TABLE), (ENTRY)), \ |
Victor Stinner | 5dacbd4 | 2016-03-23 09:52:13 +0100 | [diff] [blame] | 75 | (PDATA), (DATA_SIZE)); \ |
| 76 | } while (0) |
| 77 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 78 | /* Forward declaration */ |
| 79 | static void hashtable_rehash(_Py_hashtable_t *ht); |
| 80 | |
| 81 | static void |
| 82 | _Py_slist_init(_Py_slist_t *list) |
| 83 | { |
| 84 | list->head = NULL; |
| 85 | } |
| 86 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 87 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 88 | static void |
| 89 | _Py_slist_prepend(_Py_slist_t *list, _Py_slist_item_t *item) |
| 90 | { |
| 91 | item->next = list->head; |
| 92 | list->head = item; |
| 93 | } |
| 94 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 95 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 96 | static void |
| 97 | _Py_slist_remove(_Py_slist_t *list, _Py_slist_item_t *previous, |
| 98 | _Py_slist_item_t *item) |
| 99 | { |
| 100 | if (previous != NULL) |
| 101 | previous->next = item->next; |
| 102 | else |
| 103 | list->head = item->next; |
| 104 | } |
| 105 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 106 | |
Victor Stinner | 322bc12 | 2016-03-21 14:36:39 +0100 | [diff] [blame] | 107 | Py_uhash_t |
Victor Stinner | 5dacbd4 | 2016-03-23 09:52:13 +0100 | [diff] [blame] | 108 | _Py_hashtable_hash_ptr(struct _Py_hashtable_t *ht, const void *pkey) |
Victor Stinner | 322bc12 | 2016-03-21 14:36:39 +0100 | [diff] [blame] | 109 | { |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 110 | void *key; |
| 111 | |
Victor Stinner | 5dacbd4 | 2016-03-23 09:52:13 +0100 | [diff] [blame] | 112 | _Py_HASHTABLE_READ_KEY(ht, pkey, key); |
| 113 | return (Py_uhash_t)_Py_HashPointer(key); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 114 | } |
| 115 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 116 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 117 | int |
Victor Stinner | 5dacbd4 | 2016-03-23 09:52:13 +0100 | [diff] [blame] | 118 | _Py_hashtable_compare_direct(_Py_hashtable_t *ht, const void *pkey, |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 119 | const _Py_hashtable_entry_t *entry) |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 120 | { |
Victor Stinner | 5dacbd4 | 2016-03-23 09:52:13 +0100 | [diff] [blame] | 121 | const void *pkey2 = _Py_HASHTABLE_ENTRY_PKEY(entry); |
| 122 | return (memcmp(pkey, pkey2, ht->key_size) == 0); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 123 | } |
| 124 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 125 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 126 | /* makes sure the real size of the buckets array is a power of 2 */ |
| 127 | static size_t |
| 128 | round_size(size_t s) |
| 129 | { |
| 130 | size_t i; |
| 131 | if (s < HASHTABLE_MIN_SIZE) |
| 132 | return HASHTABLE_MIN_SIZE; |
| 133 | i = 1; |
| 134 | while (i < s) |
| 135 | i <<= 1; |
| 136 | return i; |
| 137 | } |
| 138 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 139 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 140 | _Py_hashtable_t * |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 141 | _Py_hashtable_new_full(size_t key_size, size_t data_size, |
| 142 | size_t init_size, |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 143 | _Py_hashtable_hash_func hash_func, |
| 144 | _Py_hashtable_compare_func compare_func, |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 145 | _Py_hashtable_allocator_t *allocator) |
| 146 | { |
| 147 | _Py_hashtable_t *ht; |
| 148 | size_t buckets_size; |
| 149 | _Py_hashtable_allocator_t alloc; |
| 150 | |
| 151 | if (allocator == NULL) { |
| 152 | alloc.malloc = PyMem_RawMalloc; |
| 153 | alloc.free = PyMem_RawFree; |
| 154 | } |
| 155 | else |
| 156 | alloc = *allocator; |
| 157 | |
| 158 | ht = (_Py_hashtable_t *)alloc.malloc(sizeof(_Py_hashtable_t)); |
| 159 | if (ht == NULL) |
| 160 | return ht; |
| 161 | |
| 162 | ht->num_buckets = round_size(init_size); |
| 163 | ht->entries = 0; |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 164 | ht->key_size = key_size; |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 165 | ht->data_size = data_size; |
| 166 | |
| 167 | buckets_size = ht->num_buckets * sizeof(ht->buckets[0]); |
| 168 | ht->buckets = alloc.malloc(buckets_size); |
| 169 | if (ht->buckets == NULL) { |
| 170 | alloc.free(ht); |
| 171 | return NULL; |
| 172 | } |
| 173 | memset(ht->buckets, 0, buckets_size); |
| 174 | |
| 175 | ht->hash_func = hash_func; |
| 176 | ht->compare_func = compare_func; |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 177 | ht->alloc = alloc; |
| 178 | return ht; |
| 179 | } |
| 180 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 181 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 182 | _Py_hashtable_t * |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 183 | _Py_hashtable_new(size_t key_size, size_t data_size, |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 184 | _Py_hashtable_hash_func hash_func, |
| 185 | _Py_hashtable_compare_func compare_func) |
| 186 | { |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 187 | return _Py_hashtable_new_full(key_size, data_size, |
| 188 | HASHTABLE_MIN_SIZE, |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 189 | hash_func, compare_func, |
Victor Stinner | c955387 | 2016-03-22 12:13:01 +0100 | [diff] [blame] | 190 | NULL); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 191 | } |
| 192 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 193 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 194 | size_t |
| 195 | _Py_hashtable_size(_Py_hashtable_t *ht) |
| 196 | { |
| 197 | size_t size; |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 198 | |
| 199 | size = sizeof(_Py_hashtable_t); |
| 200 | |
| 201 | /* buckets */ |
| 202 | size += ht->num_buckets * sizeof(_Py_hashtable_entry_t *); |
| 203 | |
| 204 | /* entries */ |
| 205 | size += ht->entries * HASHTABLE_ITEM_SIZE(ht); |
| 206 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 207 | return size; |
| 208 | } |
| 209 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 210 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 211 | #ifdef Py_DEBUG |
| 212 | void |
| 213 | _Py_hashtable_print_stats(_Py_hashtable_t *ht) |
| 214 | { |
| 215 | size_t size; |
| 216 | size_t chain_len, max_chain_len, total_chain_len, nchains; |
| 217 | _Py_hashtable_entry_t *entry; |
| 218 | size_t hv; |
| 219 | double load; |
| 220 | |
| 221 | size = _Py_hashtable_size(ht); |
| 222 | |
| 223 | load = (double)ht->entries / ht->num_buckets; |
| 224 | |
| 225 | max_chain_len = 0; |
| 226 | total_chain_len = 0; |
| 227 | nchains = 0; |
| 228 | for (hv = 0; hv < ht->num_buckets; hv++) { |
| 229 | entry = TABLE_HEAD(ht, hv); |
| 230 | if (entry != NULL) { |
| 231 | chain_len = 0; |
| 232 | for (; entry; entry = ENTRY_NEXT(entry)) { |
| 233 | chain_len++; |
| 234 | } |
| 235 | if (chain_len > max_chain_len) |
| 236 | max_chain_len = chain_len; |
| 237 | total_chain_len += chain_len; |
| 238 | nchains++; |
| 239 | } |
| 240 | } |
Victor Stinner | 293f3f5 | 2014-07-01 08:57:10 +0200 | [diff] [blame] | 241 | printf("hash table %p: entries=%" |
| 242 | PY_FORMAT_SIZE_T "u/%" PY_FORMAT_SIZE_T "u (%.0f%%), ", |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 243 | ht, ht->entries, ht->num_buckets, load * 100.0); |
| 244 | if (nchains) |
| 245 | printf("avg_chain_len=%.1f, ", (double)total_chain_len / nchains); |
Victor Stinner | 8c663fd | 2017-11-08 14:44:44 -0800 | [diff] [blame] | 246 | printf("max_chain_len=%" PY_FORMAT_SIZE_T "u, %" PY_FORMAT_SIZE_T "u KiB\n", |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 247 | max_chain_len, size / 1024); |
| 248 | } |
| 249 | #endif |
| 250 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 251 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 252 | _Py_hashtable_entry_t * |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 253 | _Py_hashtable_get_entry(_Py_hashtable_t *ht, |
| 254 | size_t key_size, const void *pkey) |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 255 | { |
| 256 | Py_uhash_t key_hash; |
| 257 | size_t index; |
| 258 | _Py_hashtable_entry_t *entry; |
| 259 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 260 | assert(key_size == ht->key_size); |
| 261 | |
Victor Stinner | 5dacbd4 | 2016-03-23 09:52:13 +0100 | [diff] [blame] | 262 | key_hash = ht->hash_func(ht, pkey); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 263 | index = key_hash & (ht->num_buckets - 1); |
| 264 | |
| 265 | for (entry = TABLE_HEAD(ht, index); entry != NULL; entry = ENTRY_NEXT(entry)) { |
Victor Stinner | 5dacbd4 | 2016-03-23 09:52:13 +0100 | [diff] [blame] | 266 | if (entry->key_hash == key_hash && ht->compare_func(ht, pkey, entry)) |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 267 | break; |
| 268 | } |
| 269 | |
| 270 | return entry; |
| 271 | } |
| 272 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 273 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 274 | static int |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 275 | _Py_hashtable_pop_entry(_Py_hashtable_t *ht, size_t key_size, const void *pkey, |
| 276 | void *data, size_t data_size) |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 277 | { |
| 278 | Py_uhash_t key_hash; |
| 279 | size_t index; |
| 280 | _Py_hashtable_entry_t *entry, *previous; |
| 281 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 282 | assert(key_size == ht->key_size); |
| 283 | |
Victor Stinner | 5dacbd4 | 2016-03-23 09:52:13 +0100 | [diff] [blame] | 284 | key_hash = ht->hash_func(ht, pkey); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 285 | index = key_hash & (ht->num_buckets - 1); |
| 286 | |
| 287 | previous = NULL; |
| 288 | for (entry = TABLE_HEAD(ht, index); entry != NULL; entry = ENTRY_NEXT(entry)) { |
Victor Stinner | 5dacbd4 | 2016-03-23 09:52:13 +0100 | [diff] [blame] | 289 | if (entry->key_hash == key_hash && ht->compare_func(ht, pkey, entry)) |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 290 | break; |
| 291 | previous = entry; |
| 292 | } |
| 293 | |
| 294 | if (entry == NULL) |
| 295 | return 0; |
| 296 | |
| 297 | _Py_slist_remove(&ht->buckets[index], (_Py_slist_item_t *)previous, |
| 298 | (_Py_slist_item_t *)entry); |
| 299 | ht->entries--; |
| 300 | |
| 301 | if (data != NULL) |
Victor Stinner | 5dacbd4 | 2016-03-23 09:52:13 +0100 | [diff] [blame] | 302 | ENTRY_READ_PDATA(ht, entry, data_size, data); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 303 | ht->alloc.free(entry); |
| 304 | |
| 305 | if ((float)ht->entries / (float)ht->num_buckets < HASHTABLE_LOW) |
| 306 | hashtable_rehash(ht); |
| 307 | return 1; |
| 308 | } |
| 309 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 310 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 311 | int |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 312 | _Py_hashtable_set(_Py_hashtable_t *ht, size_t key_size, const void *pkey, |
Victor Stinner | c955387 | 2016-03-22 12:13:01 +0100 | [diff] [blame] | 313 | size_t data_size, const void *data) |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 314 | { |
| 315 | Py_uhash_t key_hash; |
| 316 | size_t index; |
| 317 | _Py_hashtable_entry_t *entry; |
| 318 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 319 | assert(key_size == ht->key_size); |
| 320 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 321 | assert(data != NULL || data_size == 0); |
| 322 | #ifndef NDEBUG |
| 323 | /* Don't write the assertion on a single line because it is interesting |
| 324 | to know the duplicated entry if the assertion failed. The entry can |
| 325 | be read using a debugger. */ |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 326 | entry = _Py_hashtable_get_entry(ht, key_size, pkey); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 327 | assert(entry == NULL); |
| 328 | #endif |
| 329 | |
Victor Stinner | 5dacbd4 | 2016-03-23 09:52:13 +0100 | [diff] [blame] | 330 | key_hash = ht->hash_func(ht, pkey); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 331 | index = key_hash & (ht->num_buckets - 1); |
| 332 | |
| 333 | entry = ht->alloc.malloc(HASHTABLE_ITEM_SIZE(ht)); |
| 334 | if (entry == NULL) { |
| 335 | /* memory allocation failed */ |
| 336 | return -1; |
| 337 | } |
| 338 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 339 | entry->key_hash = key_hash; |
Christian Heimes | f051e43 | 2016-09-13 20:22:02 +0200 | [diff] [blame] | 340 | memcpy((void *)_Py_HASHTABLE_ENTRY_PKEY(entry), pkey, ht->key_size); |
Benjamin Peterson | 4a75760 | 2016-09-06 19:03:40 -0700 | [diff] [blame] | 341 | if (data) |
Benjamin Peterson | 35b40c6 | 2016-09-06 19:04:37 -0700 | [diff] [blame] | 342 | ENTRY_WRITE_PDATA(ht, entry, data_size, data); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 343 | |
| 344 | _Py_slist_prepend(&ht->buckets[index], (_Py_slist_item_t*)entry); |
| 345 | ht->entries++; |
| 346 | |
| 347 | if ((float)ht->entries / (float)ht->num_buckets > HASHTABLE_HIGH) |
| 348 | hashtable_rehash(ht); |
| 349 | return 0; |
| 350 | } |
| 351 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 352 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 353 | int |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 354 | _Py_hashtable_get(_Py_hashtable_t *ht, size_t key_size,const void *pkey, |
| 355 | size_t data_size, void *data) |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 356 | { |
| 357 | _Py_hashtable_entry_t *entry; |
| 358 | |
| 359 | assert(data != NULL); |
| 360 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 361 | entry = _Py_hashtable_get_entry(ht, key_size, pkey); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 362 | if (entry == NULL) |
| 363 | return 0; |
Victor Stinner | 5dacbd4 | 2016-03-23 09:52:13 +0100 | [diff] [blame] | 364 | ENTRY_READ_PDATA(ht, entry, data_size, data); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 365 | return 1; |
| 366 | } |
| 367 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 368 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 369 | int |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 370 | _Py_hashtable_pop(_Py_hashtable_t *ht, size_t key_size, const void *pkey, |
| 371 | size_t data_size, void *data) |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 372 | { |
| 373 | assert(data != NULL); |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 374 | return _Py_hashtable_pop_entry(ht, key_size, pkey, data, data_size); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 375 | } |
| 376 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 377 | |
Victor Stinner | 5810005 | 2016-03-22 12:25:04 +0100 | [diff] [blame] | 378 | /* Code commented since the function is not needed in Python */ |
| 379 | #if 0 |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 380 | void |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 381 | _Py_hashtable_delete(_Py_hashtable_t *ht, size_t key_size, const void *pkey) |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 382 | { |
| 383 | #ifndef NDEBUG |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 384 | int found = _Py_hashtable_pop_entry(ht, key_size, pkey, NULL, 0); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 385 | assert(found); |
| 386 | #else |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 387 | (void)_Py_hashtable_pop_entry(ht, key_size, pkey, NULL, 0); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 388 | #endif |
| 389 | } |
Victor Stinner | 5810005 | 2016-03-22 12:25:04 +0100 | [diff] [blame] | 390 | #endif |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 391 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 392 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 393 | int |
| 394 | _Py_hashtable_foreach(_Py_hashtable_t *ht, |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 395 | _Py_hashtable_foreach_func func, |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 396 | void *arg) |
| 397 | { |
| 398 | _Py_hashtable_entry_t *entry; |
| 399 | size_t hv; |
| 400 | |
| 401 | for (hv = 0; hv < ht->num_buckets; hv++) { |
| 402 | for (entry = TABLE_HEAD(ht, hv); entry; entry = ENTRY_NEXT(entry)) { |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 403 | int res = func(ht, entry, arg); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 404 | if (res) |
| 405 | return res; |
| 406 | } |
| 407 | } |
| 408 | return 0; |
| 409 | } |
| 410 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 411 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 412 | static void |
| 413 | hashtable_rehash(_Py_hashtable_t *ht) |
| 414 | { |
| 415 | size_t buckets_size, new_size, bucket; |
| 416 | _Py_slist_t *old_buckets = NULL; |
| 417 | size_t old_num_buckets; |
| 418 | |
| 419 | new_size = round_size((size_t)(ht->entries * HASHTABLE_REHASH_FACTOR)); |
| 420 | if (new_size == ht->num_buckets) |
| 421 | return; |
| 422 | |
| 423 | old_num_buckets = ht->num_buckets; |
| 424 | |
| 425 | buckets_size = new_size * sizeof(ht->buckets[0]); |
| 426 | old_buckets = ht->buckets; |
| 427 | ht->buckets = ht->alloc.malloc(buckets_size); |
| 428 | if (ht->buckets == NULL) { |
| 429 | /* cancel rehash on memory allocation failure */ |
| 430 | ht->buckets = old_buckets ; |
| 431 | /* memory allocation failed */ |
| 432 | return; |
| 433 | } |
| 434 | memset(ht->buckets, 0, buckets_size); |
| 435 | |
| 436 | ht->num_buckets = new_size; |
| 437 | |
| 438 | for (bucket = 0; bucket < old_num_buckets; bucket++) { |
| 439 | _Py_hashtable_entry_t *entry, *next; |
| 440 | for (entry = BUCKETS_HEAD(old_buckets[bucket]); entry != NULL; entry = next) { |
| 441 | size_t entry_index; |
| 442 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 443 | |
Victor Stinner | 5dacbd4 | 2016-03-23 09:52:13 +0100 | [diff] [blame] | 444 | assert(ht->hash_func(ht, _Py_HASHTABLE_ENTRY_PKEY(entry)) == entry->key_hash); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 445 | next = ENTRY_NEXT(entry); |
| 446 | entry_index = entry->key_hash & (new_size - 1); |
| 447 | |
| 448 | _Py_slist_prepend(&ht->buckets[entry_index], (_Py_slist_item_t*)entry); |
| 449 | } |
| 450 | } |
| 451 | |
| 452 | ht->alloc.free(old_buckets); |
| 453 | } |
| 454 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 455 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 456 | void |
| 457 | _Py_hashtable_clear(_Py_hashtable_t *ht) |
| 458 | { |
| 459 | _Py_hashtable_entry_t *entry, *next; |
| 460 | size_t i; |
| 461 | |
| 462 | for (i=0; i < ht->num_buckets; i++) { |
| 463 | for (entry = TABLE_HEAD(ht, i); entry != NULL; entry = next) { |
| 464 | next = ENTRY_NEXT(entry); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 465 | ht->alloc.free(entry); |
| 466 | } |
| 467 | _Py_slist_init(&ht->buckets[i]); |
| 468 | } |
| 469 | ht->entries = 0; |
| 470 | hashtable_rehash(ht); |
| 471 | } |
| 472 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 473 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 474 | void |
| 475 | _Py_hashtable_destroy(_Py_hashtable_t *ht) |
| 476 | { |
| 477 | size_t i; |
| 478 | |
| 479 | for (i = 0; i < ht->num_buckets; i++) { |
| 480 | _Py_slist_item_t *entry = ht->buckets[i].head; |
| 481 | while (entry) { |
| 482 | _Py_slist_item_t *entry_next = entry->next; |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 483 | ht->alloc.free(entry); |
| 484 | entry = entry_next; |
| 485 | } |
| 486 | } |
| 487 | |
| 488 | ht->alloc.free(ht->buckets); |
| 489 | ht->alloc.free(ht); |
| 490 | } |
| 491 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 492 | |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 493 | _Py_hashtable_t * |
| 494 | _Py_hashtable_copy(_Py_hashtable_t *src) |
| 495 | { |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 496 | const size_t key_size = src->key_size; |
| 497 | const size_t data_size = src->data_size; |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 498 | _Py_hashtable_t *dst; |
| 499 | _Py_hashtable_entry_t *entry; |
| 500 | size_t bucket; |
| 501 | int err; |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 502 | |
Victor Stinner | 285cf0a | 2016-03-21 22:00:58 +0100 | [diff] [blame] | 503 | dst = _Py_hashtable_new_full(key_size, data_size, |
| 504 | src->num_buckets, |
Victor Stinner | c955387 | 2016-03-22 12:13:01 +0100 | [diff] [blame] | 505 | src->hash_func, |
| 506 | src->compare_func, |
| 507 | &src->alloc); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 508 | if (dst == NULL) |
| 509 | return NULL; |
| 510 | |
| 511 | for (bucket=0; bucket < src->num_buckets; bucket++) { |
| 512 | entry = TABLE_HEAD(src, bucket); |
| 513 | for (; entry; entry = ENTRY_NEXT(entry)) { |
Victor Stinner | 5dacbd4 | 2016-03-23 09:52:13 +0100 | [diff] [blame] | 514 | const void *pkey = _Py_HASHTABLE_ENTRY_PKEY(entry); |
| 515 | const void *pdata = _Py_HASHTABLE_ENTRY_PDATA(src, entry); |
| 516 | err = _Py_hashtable_set(dst, key_size, pkey, data_size, pdata); |
Victor Stinner | ed3b0bc | 2013-11-23 12:27:24 +0100 | [diff] [blame] | 517 | if (err) { |
| 518 | _Py_hashtable_destroy(dst); |
| 519 | return NULL; |
| 520 | } |
| 521 | } |
| 522 | } |
| 523 | return dst; |
| 524 | } |