#include "Python.h"

#include "pycore_hashtable.h" // export _Py_hashtable_new()

#include "pycore_pyhash.h" // _Py_HashPointerRaw()

#define HASHTABLE_MIN_SIZE 16

#define HASHTABLE_HIGH 0.50

#define HASHTABLE_LOW 0.10

#define HASHTABLE_REHASH_FACTOR 2.0 / (HASHTABLE_LOW + HASHTABLE_HIGH)

#define BUCKETS_HEAD(SLIST) \

((_Py_hashtable_entry_t *)_Py_SLIST_HEAD(&(SLIST)))

#define TABLE_HEAD(HT, BUCKET) \

((_Py_hashtable_entry_t *)_Py_SLIST_HEAD(&(HT)->buckets[BUCKET]))

#define ENTRY_NEXT(ENTRY) \

((_Py_hashtable_entry_t *)_Py_SLIST_ITEM_NEXT(ENTRY))

static int hashtable_rehash(_Py_hashtable_t *ht);

static void

_Py_slist_init(_Py_slist_t *list)

{

list->head = NULL;

}

static void

_Py_slist_prepend(_Py_slist_t *list, _Py_slist_item_t *item)

{

item->next = list->head;

list->head = item;

}

static void

_Py_slist_remove(_Py_slist_t *list, _Py_slist_item_t *previous,

_Py_slist_item_t *item)

{

if (previous != NULL)

previous->next = item->next;

else

list->head = item->next;

}

_Py_hashtable_hash_ptr(const void *key)

{

return (Py_uhash_t)_Py_HashPointerRaw(key);

}

_Py_hashtable_compare_direct(const void *key1, const void *key2)

{

return (key1 == key2);

}

static size_t

round_size(size_t s)

{

size_t i;

if (s < HASHTABLE_MIN_SIZE)

return HASHTABLE_MIN_SIZE;

i = 1;

while (i < s)

i <<= 1;

return i;

}

_Py_hashtable_size(const _Py_hashtable_t *ht)

{

size_t size = sizeof(_Py_hashtable_t);

/* buckets */

size += ht->nbuckets * sizeof(_Py_hashtable_entry_t *);

/* entries */

size += ht->nentries * sizeof(_Py_hashtable_entry_t);

return size;

}

_Py_hashtable_len(const _Py_hashtable_t *ht)

{

return ht->nentries;

}

_Py_hashtable_entry_t *

_Py_hashtable_get_entry_generic(_Py_hashtable_t *ht, const void *key)

{

Py_uhash_t key_hash = ht->hash_func(key);

size_t index = key_hash & (ht->nbuckets - 1);

_Py_hashtable_entry_t *entry = TABLE_HEAD(ht, index);

while (1) {

if (entry == NULL) {

return NULL;

}

if (entry->key_hash == key_hash && ht->compare_func(key, entry->key)) {

break;

}

entry = ENTRY_NEXT(entry);

}

return entry;

}

static _Py_hashtable_entry_t *

_Py_hashtable_get_entry_ptr(_Py_hashtable_t *ht, const void *key)

{

Py_uhash_t key_hash = _Py_hashtable_hash_ptr(key);

size_t index = key_hash & (ht->nbuckets - 1);

_Py_hashtable_entry_t *entry = TABLE_HEAD(ht, index);

while (1) {

if (entry == NULL) {

return NULL;

}

// Compare directly keys (ignore entry->key_hash)

if (entry->key == key) {

break;

}

entry = ENTRY_NEXT(entry);

}

return entry;

}

_Py_hashtable_steal(_Py_hashtable_t *ht, const void *key)

{

Py_uhash_t key_hash = ht->hash_func(key);

size_t index = key_hash & (ht->nbuckets - 1);

_Py_hashtable_entry_t *entry = TABLE_HEAD(ht, index);

_Py_hashtable_entry_t *previous = NULL;

while (1) {

if (entry == NULL) {

// not found

return NULL;

}

if (entry->key_hash == key_hash && ht->compare_func(key, entry->key)) {

break;

}

previous = entry;

entry = ENTRY_NEXT(entry);

}

_Py_slist_remove(&ht->buckets[index], (_Py_slist_item_t *)previous,

(_Py_slist_item_t *)entry);

ht->nentries--;

void *value = entry->value;

ht->alloc.free(entry);

if ((float)ht->nentries / (float)ht->nbuckets < HASHTABLE_LOW) {

// Ignore failure: error cannot be reported to the caller

hashtable_rehash(ht);

}

return value;

}

_Py_hashtable_set(_Py_hashtable_t *ht, const void *key, void *value)

{

_Py_hashtable_entry_t *entry;

#ifndef NDEBUG

/* Don't write the assertion on a single line because it is interesting

entry = ht->get_entry_func(ht, key);

assert(entry == NULL);

entry = ht->alloc.malloc(sizeof(_Py_hashtable_entry_t));

if (entry == NULL) {

/* memory allocation failed */

return -1;

}

entry->key_hash = ht->hash_func(key);

entry->key = (void *)key;

entry->value = value;

ht->nentries++;

if ((float)ht->nentries / (float)ht->nbuckets > HASHTABLE_HIGH) {

if (hashtable_rehash(ht) < 0) {

ht->nentries--;

ht->alloc.free(entry);

return -1;

}

}

size_t index = entry->key_hash & (ht->nbuckets - 1);

_Py_slist_prepend(&ht->buckets[index], (_Py_slist_item_t*)entry);

return 0;

}

_Py_hashtable_get(_Py_hashtable_t *ht, const void *key)

{

_Py_hashtable_entry_t *entry = ht->get_entry_func(ht, key);

if (entry != NULL) {

return entry->value;

}

else {

return NULL;

}

}

_Py_hashtable_foreach(_Py_hashtable_t *ht,

_Py_hashtable_foreach_func func,

void *user_data)

{

for (size_t hv = 0; hv < ht->nbuckets; hv++) {

_Py_hashtable_entry_t *entry = TABLE_HEAD(ht, hv);

while (entry != NULL) {

int res = func(ht, entry->key, entry->value, user_data);

if (res) {

return res;

}

entry = ENTRY_NEXT(entry);

}

}

return 0;

}

static int

hashtable_rehash(_Py_hashtable_t *ht)

{

size_t new_size = round_size((size_t)(ht->nentries * HASHTABLE_REHASH_FACTOR));

if (new_size == ht->nbuckets) {

return 0;

}

size_t buckets_size = new_size * sizeof(ht->buckets[0]);

_Py_slist_t *new_buckets = ht->alloc.malloc(buckets_size);

if (new_buckets == NULL) {

/* memory allocation failed */

return -1;

}

memset(new_buckets, 0, buckets_size);

for (size_t bucket = 0; bucket < ht->nbuckets; bucket++) {

_Py_hashtable_entry_t *entry = BUCKETS_HEAD(ht->buckets[bucket]);

while (entry != NULL) {

assert(ht->hash_func(entry->key) == entry->key_hash);

_Py_hashtable_entry_t *next = ENTRY_NEXT(entry);

size_t entry_index = entry->key_hash & (new_size - 1);

_Py_slist_prepend(&new_buckets[entry_index], (_Py_slist_item_t*)entry);

entry = next;

}

}

ht->alloc.free(ht->buckets);

ht->nbuckets = new_size;

ht->buckets = new_buckets;

return 0;

}

_Py_hashtable_t *

_Py_hashtable_new_full(_Py_hashtable_hash_func hash_func,

_Py_hashtable_allocator_t *allocator)

{

_Py_hashtable_allocator_t alloc;

if (allocator == NULL) {

alloc.malloc = PyMem_Malloc;

alloc.free = PyMem_Free;

}

else {

alloc = *allocator;

}

_Py_hashtable_t *ht = (_Py_hashtable_t *)alloc.malloc(sizeof(_Py_hashtable_t));

if (ht == NULL) {

return ht;

}

ht->nbuckets = HASHTABLE_MIN_SIZE;

ht->nentries = 0;

size_t buckets_size = ht->nbuckets * sizeof(ht->buckets[0]);

ht->buckets = alloc.malloc(buckets_size);

if (ht->buckets == NULL) {

alloc.free(ht);

return NULL;

}

memset(ht->buckets, 0, buckets_size);

ht->get_entry_func = _Py_hashtable_get_entry_generic;

ht->hash_func = hash_func;

ht->compare_func = compare_func;

ht->key_destroy_func = key_destroy_func;

ht->value_destroy_func = value_destroy_func;

ht->alloc = alloc;

if (ht->hash_func == _Py_hashtable_hash_ptr

&& ht->compare_func == _Py_hashtable_compare_direct)

{

ht->get_entry_func = _Py_hashtable_get_entry_ptr;

}

return ht;

}

_Py_hashtable_t *

_Py_hashtable_new(_Py_hashtable_hash_func hash_func,

_Py_hashtable_compare_func compare_func)

{

return _Py_hashtable_new_full(hash_func, compare_func,

NULL, NULL, NULL);

}

static void

_Py_hashtable_destroy_entry(_Py_hashtable_t *ht, _Py_hashtable_entry_t *entry)

{

if (ht->key_destroy_func) {

ht->key_destroy_func(entry->key);

}

if (ht->value_destroy_func) {

ht->value_destroy_func(entry->value);

}

ht->alloc.free(entry);

}

_Py_hashtable_clear(_Py_hashtable_t *ht)

{

for (size_t i=0; i < ht->nbuckets; i++) {

_Py_hashtable_entry_t *entry = TABLE_HEAD(ht, i);

while (entry != NULL) {

_Py_hashtable_entry_t *next = ENTRY_NEXT(entry);

_Py_hashtable_destroy_entry(ht, entry);

entry = next;

}

_Py_slist_init(&ht->buckets[i]);

}

ht->nentries = 0;

// Ignore failure: clear function is not expected to fail

// because of a memory allocation failure.

(void)hashtable_rehash(ht);

}

_Py_hashtable_destroy(_Py_hashtable_t *ht)

{

for (size_t i = 0; i < ht->nbuckets; i++) {

_Py_hashtable_entry_t *entry = TABLE_HEAD(ht, i);

while (entry) {

_Py_hashtable_entry_t *entry_next = ENTRY_NEXT(entry);

_Py_hashtable_destroy_entry(ht, entry);

entry = entry_next;

}

}

ht->alloc.free(ht->buckets);

ht->alloc.free(ht);

}