Lines Matching refs:ht
63 static int hashtable_rehash(_Py_hashtable_t *ht);
120 _Py_hashtable_size(const _Py_hashtable_t *ht) in _Py_hashtable_size() argument
124 size += ht->nbuckets * sizeof(_Py_hashtable_entry_t *); in _Py_hashtable_size()
126 size += ht->nentries * sizeof(_Py_hashtable_entry_t); in _Py_hashtable_size()
132 _Py_hashtable_get_entry_generic(_Py_hashtable_t *ht, const void *key) in _Py_hashtable_get_entry_generic() argument
134 Py_uhash_t key_hash = ht->hash_func(key); in _Py_hashtable_get_entry_generic()
135 size_t index = key_hash & (ht->nbuckets - 1); in _Py_hashtable_get_entry_generic()
136 _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, index); in _Py_hashtable_get_entry_generic()
141 if (entry->key_hash == key_hash && ht->compare_func(key, entry->key)) { in _Py_hashtable_get_entry_generic()
154 _Py_hashtable_get_entry_ptr(_Py_hashtable_t *ht, const void *key) in _Py_hashtable_get_entry_ptr() argument
157 size_t index = key_hash & (ht->nbuckets - 1); in _Py_hashtable_get_entry_ptr()
158 _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, index); in _Py_hashtable_get_entry_ptr()
174 _Py_hashtable_steal(_Py_hashtable_t *ht, const void *key) in _Py_hashtable_steal() argument
176 Py_uhash_t key_hash = ht->hash_func(key); in _Py_hashtable_steal()
177 size_t index = key_hash & (ht->nbuckets - 1); in _Py_hashtable_steal()
179 _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, index); in _Py_hashtable_steal()
186 if (entry->key_hash == key_hash && ht->compare_func(key, entry->key)) { in _Py_hashtable_steal()
193 _Py_slist_remove(&ht->buckets[index], (_Py_slist_item_t *)previous, in _Py_hashtable_steal()
195 ht->nentries--; in _Py_hashtable_steal()
198 ht->alloc.free(entry); in _Py_hashtable_steal()
200 if ((float)ht->nentries / (float)ht->nbuckets < HASHTABLE_LOW) { in _Py_hashtable_steal()
202 hashtable_rehash(ht); in _Py_hashtable_steal()
209 _Py_hashtable_set(_Py_hashtable_t *ht, const void *key, void *value) in _Py_hashtable_set() argument
217 entry = ht->get_entry_func(ht, key); in _Py_hashtable_set()
222 entry = ht->alloc.malloc(sizeof(_Py_hashtable_entry_t)); in _Py_hashtable_set()
228 entry->key_hash = ht->hash_func(key); in _Py_hashtable_set()
232 ht->nentries++; in _Py_hashtable_set()
233 if ((float)ht->nentries / (float)ht->nbuckets > HASHTABLE_HIGH) { in _Py_hashtable_set()
234 if (hashtable_rehash(ht) < 0) { in _Py_hashtable_set()
235 ht->nentries--; in _Py_hashtable_set()
236 ht->alloc.free(entry); in _Py_hashtable_set()
241 size_t index = entry->key_hash & (ht->nbuckets - 1); in _Py_hashtable_set()
242 _Py_slist_prepend(&ht->buckets[index], (_Py_slist_item_t*)entry); in _Py_hashtable_set()
248 _Py_hashtable_get(_Py_hashtable_t *ht, const void *key) in _Py_hashtable_get() argument
250 _Py_hashtable_entry_t *entry = ht->get_entry_func(ht, key); in _Py_hashtable_get()
261 _Py_hashtable_foreach(_Py_hashtable_t *ht, in _Py_hashtable_foreach() argument
265 for (size_t hv = 0; hv < ht->nbuckets; hv++) { in _Py_hashtable_foreach()
266 _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, hv); in _Py_hashtable_foreach()
268 int res = func(ht, entry->key, entry->value, user_data); in _Py_hashtable_foreach()
280 hashtable_rehash(_Py_hashtable_t *ht) in hashtable_rehash() argument
282 size_t new_size = round_size((size_t)(ht->nentries * HASHTABLE_REHASH_FACTOR)); in hashtable_rehash()
283 if (new_size == ht->nbuckets) { in hashtable_rehash()
287 size_t buckets_size = new_size * sizeof(ht->buckets[0]); in hashtable_rehash()
288 _Py_slist_t *new_buckets = ht->alloc.malloc(buckets_size); in hashtable_rehash()
295 for (size_t bucket = 0; bucket < ht->nbuckets; bucket++) { in hashtable_rehash()
296 _Py_hashtable_entry_t *entry = BUCKETS_HEAD(ht->buckets[bucket]); in hashtable_rehash()
298 assert(ht->hash_func(entry->key) == entry->key_hash); in hashtable_rehash()
308 ht->alloc.free(ht->buckets); in hashtable_rehash()
309 ht->nbuckets = new_size; in hashtable_rehash()
310 ht->buckets = new_buckets; in hashtable_rehash()
331 _Py_hashtable_t *ht = (_Py_hashtable_t *)alloc.malloc(sizeof(_Py_hashtable_t)); in _Py_hashtable_new_full() local
332 if (ht == NULL) { in _Py_hashtable_new_full()
333 return ht; in _Py_hashtable_new_full()
336 ht->nbuckets = HASHTABLE_MIN_SIZE; in _Py_hashtable_new_full()
337 ht->nentries = 0; in _Py_hashtable_new_full()
339 size_t buckets_size = ht->nbuckets * sizeof(ht->buckets[0]); in _Py_hashtable_new_full()
340 ht->buckets = alloc.malloc(buckets_size); in _Py_hashtable_new_full()
341 if (ht->buckets == NULL) { in _Py_hashtable_new_full()
342 alloc.free(ht); in _Py_hashtable_new_full()
345 memset(ht->buckets, 0, buckets_size); in _Py_hashtable_new_full()
347 ht->get_entry_func = _Py_hashtable_get_entry_generic; in _Py_hashtable_new_full()
348 ht->hash_func = hash_func; in _Py_hashtable_new_full()
349 ht->compare_func = compare_func; in _Py_hashtable_new_full()
350 ht->key_destroy_func = key_destroy_func; in _Py_hashtable_new_full()
351 ht->value_destroy_func = value_destroy_func; in _Py_hashtable_new_full()
352 ht->alloc = alloc; in _Py_hashtable_new_full()
353 if (ht->hash_func == _Py_hashtable_hash_ptr in _Py_hashtable_new_full()
354 && ht->compare_func == _Py_hashtable_compare_direct) in _Py_hashtable_new_full()
356 ht->get_entry_func = _Py_hashtable_get_entry_ptr; in _Py_hashtable_new_full()
358 return ht; in _Py_hashtable_new_full()
372 _Py_hashtable_destroy_entry(_Py_hashtable_t *ht, _Py_hashtable_entry_t *entry) in _Py_hashtable_destroy_entry() argument
374 if (ht->key_destroy_func) { in _Py_hashtable_destroy_entry()
375 ht->key_destroy_func(entry->key); in _Py_hashtable_destroy_entry()
377 if (ht->value_destroy_func) { in _Py_hashtable_destroy_entry()
378 ht->value_destroy_func(entry->value); in _Py_hashtable_destroy_entry()
380 ht->alloc.free(entry); in _Py_hashtable_destroy_entry()
385 _Py_hashtable_clear(_Py_hashtable_t *ht) in _Py_hashtable_clear() argument
387 for (size_t i=0; i < ht->nbuckets; i++) { in _Py_hashtable_clear()
388 _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, i); in _Py_hashtable_clear()
391 _Py_hashtable_destroy_entry(ht, entry); in _Py_hashtable_clear()
394 _Py_slist_init(&ht->buckets[i]); in _Py_hashtable_clear()
396 ht->nentries = 0; in _Py_hashtable_clear()
399 (void)hashtable_rehash(ht); in _Py_hashtable_clear()
404 _Py_hashtable_destroy(_Py_hashtable_t *ht) in _Py_hashtable_destroy() argument
406 for (size_t i = 0; i < ht->nbuckets; i++) { in _Py_hashtable_destroy()
407 _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, i); in _Py_hashtable_destroy()
410 _Py_hashtable_destroy_entry(ht, entry); in _Py_hashtable_destroy()
415 ht->alloc.free(ht->buckets); in _Py_hashtable_destroy()
416 ht->alloc.free(ht); in _Py_hashtable_destroy()