Lines Matching refs:ht
79 static void hashtable_rehash(_Py_hashtable_t *ht);
108 _Py_hashtable_hash_ptr(struct _Py_hashtable_t *ht, const void *pkey) in _Py_hashtable_hash_ptr() argument
112 _Py_HASHTABLE_READ_KEY(ht, pkey, key); in _Py_hashtable_hash_ptr()
118 _Py_hashtable_compare_direct(_Py_hashtable_t *ht, const void *pkey, in _Py_hashtable_compare_direct() argument
122 return (memcmp(pkey, pkey2, ht->key_size) == 0); in _Py_hashtable_compare_direct()
147 _Py_hashtable_t *ht; in _Py_hashtable_new_full() local
158 ht = (_Py_hashtable_t *)alloc.malloc(sizeof(_Py_hashtable_t)); in _Py_hashtable_new_full()
159 if (ht == NULL) in _Py_hashtable_new_full()
160 return ht; in _Py_hashtable_new_full()
162 ht->num_buckets = round_size(init_size); in _Py_hashtable_new_full()
163 ht->entries = 0; in _Py_hashtable_new_full()
164 ht->key_size = key_size; in _Py_hashtable_new_full()
165 ht->data_size = data_size; in _Py_hashtable_new_full()
167 buckets_size = ht->num_buckets * sizeof(ht->buckets[0]); in _Py_hashtable_new_full()
168 ht->buckets = alloc.malloc(buckets_size); in _Py_hashtable_new_full()
169 if (ht->buckets == NULL) { in _Py_hashtable_new_full()
170 alloc.free(ht); in _Py_hashtable_new_full()
173 memset(ht->buckets, 0, buckets_size); in _Py_hashtable_new_full()
175 ht->hash_func = hash_func; in _Py_hashtable_new_full()
176 ht->compare_func = compare_func; in _Py_hashtable_new_full()
177 ht->alloc = alloc; in _Py_hashtable_new_full()
178 return ht; in _Py_hashtable_new_full()
195 _Py_hashtable_size(_Py_hashtable_t *ht) in _Py_hashtable_size() argument
202 size += ht->num_buckets * sizeof(_Py_hashtable_entry_t *); in _Py_hashtable_size()
205 size += ht->entries * HASHTABLE_ITEM_SIZE(ht); in _Py_hashtable_size()
213 _Py_hashtable_print_stats(_Py_hashtable_t *ht) in _Py_hashtable_print_stats() argument
221 size = _Py_hashtable_size(ht); in _Py_hashtable_print_stats()
223 load = (double)ht->entries / ht->num_buckets; in _Py_hashtable_print_stats()
228 for (hv = 0; hv < ht->num_buckets; hv++) { in _Py_hashtable_print_stats()
229 entry = TABLE_HEAD(ht, hv); in _Py_hashtable_print_stats()
243 ht, ht->entries, ht->num_buckets, load * 100.0); in _Py_hashtable_print_stats()
253 _Py_hashtable_get_entry(_Py_hashtable_t *ht, in _Py_hashtable_get_entry() argument
260 assert(key_size == ht->key_size); in _Py_hashtable_get_entry()
262 key_hash = ht->hash_func(ht, pkey); in _Py_hashtable_get_entry()
263 index = key_hash & (ht->num_buckets - 1); in _Py_hashtable_get_entry()
265 for (entry = TABLE_HEAD(ht, index); entry != NULL; entry = ENTRY_NEXT(entry)) { in _Py_hashtable_get_entry()
266 if (entry->key_hash == key_hash && ht->compare_func(ht, pkey, entry)) in _Py_hashtable_get_entry()
275 _Py_hashtable_pop_entry(_Py_hashtable_t *ht, size_t key_size, const void *pkey, in _Py_hashtable_pop_entry() argument
282 assert(key_size == ht->key_size); in _Py_hashtable_pop_entry()
284 key_hash = ht->hash_func(ht, pkey); in _Py_hashtable_pop_entry()
285 index = key_hash & (ht->num_buckets - 1); in _Py_hashtable_pop_entry()
288 for (entry = TABLE_HEAD(ht, index); entry != NULL; entry = ENTRY_NEXT(entry)) { in _Py_hashtable_pop_entry()
289 if (entry->key_hash == key_hash && ht->compare_func(ht, pkey, entry)) in _Py_hashtable_pop_entry()
297 _Py_slist_remove(&ht->buckets[index], (_Py_slist_item_t *)previous, in _Py_hashtable_pop_entry()
299 ht->entries--; in _Py_hashtable_pop_entry()
302 ENTRY_READ_PDATA(ht, entry, data_size, data); in _Py_hashtable_pop_entry()
303 ht->alloc.free(entry); in _Py_hashtable_pop_entry()
305 if ((float)ht->entries / (float)ht->num_buckets < HASHTABLE_LOW) in _Py_hashtable_pop_entry()
306 hashtable_rehash(ht); in _Py_hashtable_pop_entry()
312 _Py_hashtable_set(_Py_hashtable_t *ht, size_t key_size, const void *pkey, in _Py_hashtable_set() argument
319 assert(key_size == ht->key_size); in _Py_hashtable_set()
326 entry = _Py_hashtable_get_entry(ht, key_size, pkey); in _Py_hashtable_set()
330 key_hash = ht->hash_func(ht, pkey); in _Py_hashtable_set()
331 index = key_hash & (ht->num_buckets - 1); in _Py_hashtable_set()
333 entry = ht->alloc.malloc(HASHTABLE_ITEM_SIZE(ht)); in _Py_hashtable_set()
340 memcpy((void *)_Py_HASHTABLE_ENTRY_PKEY(entry), pkey, ht->key_size); in _Py_hashtable_set()
342 ENTRY_WRITE_PDATA(ht, entry, data_size, data); in _Py_hashtable_set()
344 _Py_slist_prepend(&ht->buckets[index], (_Py_slist_item_t*)entry); in _Py_hashtable_set()
345 ht->entries++; in _Py_hashtable_set()
347 if ((float)ht->entries / (float)ht->num_buckets > HASHTABLE_HIGH) in _Py_hashtable_set()
348 hashtable_rehash(ht); in _Py_hashtable_set()
354 _Py_hashtable_get(_Py_hashtable_t *ht, size_t key_size,const void *pkey, in _Py_hashtable_get() argument
361 entry = _Py_hashtable_get_entry(ht, key_size, pkey); in _Py_hashtable_get()
364 ENTRY_READ_PDATA(ht, entry, data_size, data); in _Py_hashtable_get()
370 _Py_hashtable_pop(_Py_hashtable_t *ht, size_t key_size, const void *pkey, in _Py_hashtable_pop() argument
374 return _Py_hashtable_pop_entry(ht, key_size, pkey, data, data_size); in _Py_hashtable_pop()
381 _Py_hashtable_delete(_Py_hashtable_t *ht, size_t key_size, const void *pkey)
384 int found = _Py_hashtable_pop_entry(ht, key_size, pkey, NULL, 0);
387 (void)_Py_hashtable_pop_entry(ht, key_size, pkey, NULL, 0);
394 _Py_hashtable_foreach(_Py_hashtable_t *ht, in _Py_hashtable_foreach() argument
401 for (hv = 0; hv < ht->num_buckets; hv++) { in _Py_hashtable_foreach()
402 for (entry = TABLE_HEAD(ht, hv); entry; entry = ENTRY_NEXT(entry)) { in _Py_hashtable_foreach()
403 int res = func(ht, entry, arg); in _Py_hashtable_foreach()
413 hashtable_rehash(_Py_hashtable_t *ht) in hashtable_rehash() argument
419 new_size = round_size((size_t)(ht->entries * HASHTABLE_REHASH_FACTOR)); in hashtable_rehash()
420 if (new_size == ht->num_buckets) in hashtable_rehash()
423 old_num_buckets = ht->num_buckets; in hashtable_rehash()
425 buckets_size = new_size * sizeof(ht->buckets[0]); in hashtable_rehash()
426 old_buckets = ht->buckets; in hashtable_rehash()
427 ht->buckets = ht->alloc.malloc(buckets_size); in hashtable_rehash()
428 if (ht->buckets == NULL) { in hashtable_rehash()
430 ht->buckets = old_buckets ; in hashtable_rehash()
434 memset(ht->buckets, 0, buckets_size); in hashtable_rehash()
436 ht->num_buckets = new_size; in hashtable_rehash()
444 assert(ht->hash_func(ht, _Py_HASHTABLE_ENTRY_PKEY(entry)) == entry->key_hash); in hashtable_rehash()
448 _Py_slist_prepend(&ht->buckets[entry_index], (_Py_slist_item_t*)entry); in hashtable_rehash()
452 ht->alloc.free(old_buckets); in hashtable_rehash()
457 _Py_hashtable_clear(_Py_hashtable_t *ht) in _Py_hashtable_clear() argument
462 for (i=0; i < ht->num_buckets; i++) { in _Py_hashtable_clear()
463 for (entry = TABLE_HEAD(ht, i); entry != NULL; entry = next) { in _Py_hashtable_clear()
465 ht->alloc.free(entry); in _Py_hashtable_clear()
467 _Py_slist_init(&ht->buckets[i]); in _Py_hashtable_clear()
469 ht->entries = 0; in _Py_hashtable_clear()
470 hashtable_rehash(ht); in _Py_hashtable_clear()
475 _Py_hashtable_destroy(_Py_hashtable_t *ht) in _Py_hashtable_destroy() argument
479 for (i = 0; i < ht->num_buckets; i++) { in _Py_hashtable_destroy()
480 _Py_slist_item_t *entry = ht->buckets[i].head; in _Py_hashtable_destroy()
483 ht->alloc.free(entry); in _Py_hashtable_destroy()
488 ht->alloc.free(ht->buckets); in _Py_hashtable_destroy()
489 ht->alloc.free(ht); in _Py_hashtable_destroy()