From b617993b7c0b0f6f679ef7003a62d0318b6d6af9 Mon Sep 17 00:00:00 2001 From: Victor Stinner Date: Tue, 12 May 2020 02:42:19 +0200 Subject: bpo-40602: Rename hashtable.h to pycore_hashtable.h (GH-20044) * Move Modules/hashtable.h to Include/internal/pycore_hashtable.h * Move Modules/hashtable.c to Python/hashtable.c * Python is now linked to hashtable.c. _tracemalloc is no longer linked to hashtable.c. Previously, marshal.c got hashtable.c via _tracemalloc.c which is built as a builtin module. --- Include/internal/pycore_hashtable.h | 218 +++++++++++++++ Makefile.pre.in | 2 + Modules/Setup | 2 +- Modules/_tracemalloc.c | 2 +- Modules/hashtable.c | 524 ------------------------------------ Modules/hashtable.h | 211 --------------- PCbuild/pythoncore.vcxproj | 3 +- PCbuild/pythoncore.vcxproj.filters | 9 +- Python/hashtable.c | 524 ++++++++++++++++++++++++++++++++++++ Python/marshal.c | 2 +- 10 files changed, 755 insertions(+), 742 deletions(-) create mode 100644 Include/internal/pycore_hashtable.h delete mode 100644 Modules/hashtable.c delete mode 100644 Modules/hashtable.h create mode 100644 Python/hashtable.c diff --git a/Include/internal/pycore_hashtable.h b/Include/internal/pycore_hashtable.h new file mode 100644 index 0000000000..585f76b51d --- /dev/null +++ b/Include/internal/pycore_hashtable.h @@ -0,0 +1,218 @@ +#ifndef Py_INTERNAL_HASHTABLE_H +#define Py_INTERNAL_HASHTABLE_H +#ifdef __cplusplus +extern "C" { +#endif + +#ifndef Py_BUILD_CORE +# error "this header requires Py_BUILD_CORE define" +#endif + +/* Single linked list */ + +typedef struct _Py_slist_item_s { + struct _Py_slist_item_s *next; +} _Py_slist_item_t; + +typedef struct { + _Py_slist_item_t *head; +} _Py_slist_t; + +#define _Py_SLIST_ITEM_NEXT(ITEM) (((_Py_slist_item_t *)ITEM)->next) + +#define _Py_SLIST_HEAD(SLIST) (((_Py_slist_t *)SLIST)->head) + + +/* _Py_hashtable: table entry */ + +typedef struct { + /* used by _Py_hashtable_t.buckets to link entries */ + _Py_slist_item_t _Py_slist_item; + + Py_uhash_t key_hash; + + /* key (key_size bytes) and then data (data_size bytes) follows */ +} _Py_hashtable_entry_t; + +#define _Py_HASHTABLE_ENTRY_PKEY(ENTRY) \ + ((const void *)((char *)(ENTRY) \ + + sizeof(_Py_hashtable_entry_t))) + +#define _Py_HASHTABLE_ENTRY_PDATA(TABLE, ENTRY) \ + ((const void *)((char *)(ENTRY) \ + + sizeof(_Py_hashtable_entry_t) \ + + (TABLE)->key_size)) + +/* Get a key value from pkey: use memcpy() rather than a pointer dereference + to avoid memory alignment issues. */ +#define _Py_HASHTABLE_READ_KEY(TABLE, PKEY, DST_KEY) \ + do { \ + assert(sizeof(DST_KEY) == (TABLE)->key_size); \ + memcpy(&(DST_KEY), (PKEY), sizeof(DST_KEY)); \ + } while (0) + +#define _Py_HASHTABLE_ENTRY_READ_KEY(TABLE, ENTRY, KEY) \ + do { \ + assert(sizeof(KEY) == (TABLE)->key_size); \ + memcpy(&(KEY), _Py_HASHTABLE_ENTRY_PKEY(ENTRY), sizeof(KEY)); \ + } while (0) + +#define _Py_HASHTABLE_ENTRY_READ_DATA(TABLE, ENTRY, DATA) \ + do { \ + assert(sizeof(DATA) == (TABLE)->data_size); \ + memcpy(&(DATA), _Py_HASHTABLE_ENTRY_PDATA(TABLE, (ENTRY)), \ + sizeof(DATA)); \ + } while (0) + +#define _Py_HASHTABLE_ENTRY_WRITE_DATA(TABLE, ENTRY, DATA) \ + do { \ + assert(sizeof(DATA) == (TABLE)->data_size); \ + memcpy((void *)_Py_HASHTABLE_ENTRY_PDATA((TABLE), (ENTRY)), \ + &(DATA), sizeof(DATA)); \ + } while (0) + + +/* _Py_hashtable: prototypes */ + +/* Forward declaration */ +struct _Py_hashtable_t; + +typedef Py_uhash_t (*_Py_hashtable_hash_func) (struct _Py_hashtable_t *ht, + const void *pkey); +typedef int (*_Py_hashtable_compare_func) (struct _Py_hashtable_t *ht, + const void *pkey, + const _Py_hashtable_entry_t *he); + +typedef struct { + /* allocate a memory block */ + void* (*malloc) (size_t size); + + /* release a memory block */ + void (*free) (void *ptr); +} _Py_hashtable_allocator_t; + + +/* _Py_hashtable: table */ + +typedef struct _Py_hashtable_t { + size_t num_buckets; + size_t entries; /* Total number of entries in the table. */ + _Py_slist_t *buckets; + size_t key_size; + size_t data_size; + + _Py_hashtable_hash_func hash_func; + _Py_hashtable_compare_func compare_func; + _Py_hashtable_allocator_t alloc; +} _Py_hashtable_t; + +/* hash a pointer (void*) */ +PyAPI_FUNC(Py_uhash_t) _Py_hashtable_hash_ptr( + struct _Py_hashtable_t *ht, + const void *pkey); + +/* comparison using memcmp() */ +PyAPI_FUNC(int) _Py_hashtable_compare_direct( + _Py_hashtable_t *ht, + const void *pkey, + const _Py_hashtable_entry_t *entry); + +PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_new( + size_t key_size, + size_t data_size, + _Py_hashtable_hash_func hash_func, + _Py_hashtable_compare_func compare_func); + +PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_new_full( + size_t key_size, + size_t data_size, + size_t init_size, + _Py_hashtable_hash_func hash_func, + _Py_hashtable_compare_func compare_func, + _Py_hashtable_allocator_t *allocator); + +PyAPI_FUNC(void) _Py_hashtable_destroy(_Py_hashtable_t *ht); + +/* Return a copy of the hash table */ +PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_copy(_Py_hashtable_t *src); + +PyAPI_FUNC(void) _Py_hashtable_clear(_Py_hashtable_t *ht); + +typedef int (*_Py_hashtable_foreach_func) (_Py_hashtable_t *ht, + _Py_hashtable_entry_t *entry, + void *arg); + +/* Call func() on each entry of the hashtable. + Iteration stops if func() result is non-zero, in this case it's the result + of the call. Otherwise, the function returns 0. */ +PyAPI_FUNC(int) _Py_hashtable_foreach( + _Py_hashtable_t *ht, + _Py_hashtable_foreach_func func, + void *arg); + +PyAPI_FUNC(size_t) _Py_hashtable_size(_Py_hashtable_t *ht); + +/* Add a new entry to the hash. The key must not be present in the hash table. + Return 0 on success, -1 on memory error. + + Don't call directly this function, + but use _Py_HASHTABLE_SET() and _Py_HASHTABLE_SET_NODATA() macros */ +PyAPI_FUNC(int) _Py_hashtable_set( + _Py_hashtable_t *ht, + size_t key_size, + const void *pkey, + size_t data_size, + const void *data); + +#define _Py_HASHTABLE_SET(TABLE, KEY, DATA) \ + _Py_hashtable_set(TABLE, sizeof(KEY), &(KEY), sizeof(DATA), &(DATA)) + +#define _Py_HASHTABLE_SET_NODATA(TABLE, KEY) \ + _Py_hashtable_set(TABLE, sizeof(KEY), &(KEY), 0, NULL) + + +/* Get an entry. + Return NULL if the key does not exist. + + Don't call directly this function, but use _Py_HASHTABLE_GET_ENTRY() + macro */ +PyAPI_FUNC(_Py_hashtable_entry_t*) _Py_hashtable_get_entry( + _Py_hashtable_t *ht, + size_t key_size, + const void *pkey); + +#define _Py_HASHTABLE_GET_ENTRY(TABLE, KEY) \ + _Py_hashtable_get_entry(TABLE, sizeof(KEY), &(KEY)) + + +/* Get data from an entry. Copy entry data into data and return 1 if the entry + exists, return 0 if the entry does not exist. + + Don't call directly this function, but use _Py_HASHTABLE_GET() macro */ +PyAPI_FUNC(int) _Py_hashtable_get( + _Py_hashtable_t *ht, + size_t key_size, + const void *pkey, + size_t data_size, + void *data); + +#define _Py_HASHTABLE_GET(TABLE, KEY, DATA) \ + _Py_hashtable_get(TABLE, sizeof(KEY), &(KEY), sizeof(DATA), &(DATA)) + + +/* Don't call directly this function, but use _Py_HASHTABLE_POP() macro */ +PyAPI_FUNC(int) _Py_hashtable_pop( + _Py_hashtable_t *ht, + size_t key_size, + const void *pkey, + size_t data_size, + void *data); + +#define _Py_HASHTABLE_POP(TABLE, KEY, DATA) \ + _Py_hashtable_pop(TABLE, sizeof(KEY), &(KEY), sizeof(DATA), &(DATA)) + + +#ifdef __cplusplus +} +#endif +#endif /* !Py_INTERNAL_HASHTABLE_H */ diff --git a/Makefile.pre.in b/Makefile.pre.in index 0d616d3044..d545a9efb3 100644 --- a/Makefile.pre.in +++ b/Makefile.pre.in @@ -351,6 +351,7 @@ PYTHON_OBJS= \ Python/getversion.o \ Python/graminit.o \ Python/hamt.o \ + Python/hashtable.o \ Python/import.o \ Python/importdl.o \ Python/initconfig.o \ @@ -1131,6 +1132,7 @@ PYTHON_HEADERS= \ $(srcdir)/Include/internal/pycore_getopt.h \ $(srcdir)/Include/internal/pycore_gil.h \ $(srcdir)/Include/internal/pycore_hamt.h \ + $(srcdir)/Include/internal/pycore_hashtable.h \ $(srcdir)/Include/internal/pycore_import.h \ $(srcdir)/Include/internal/pycore_initconfig.h \ $(srcdir)/Include/internal/pycore_interp.h \ diff --git a/Modules/Setup b/Modules/Setup index 6bf142419d..87e73bac78 100644 --- a/Modules/Setup +++ b/Modules/Setup @@ -132,7 +132,7 @@ faulthandler faulthandler.c # # bpo-35053: The module must be builtin since _Py_NewReference() # can call _PyTraceMalloc_NewReference(). -_tracemalloc _tracemalloc.c hashtable.c +_tracemalloc _tracemalloc.c # PEG-based parser module -- slated to be *the* parser _peg_parser _peg_parser.c diff --git a/Modules/_tracemalloc.c b/Modules/_tracemalloc.c index ea7e012736..f22338166d 100644 --- a/Modules/_tracemalloc.c +++ b/Modules/_tracemalloc.c @@ -2,7 +2,7 @@ #include "pycore_gc.h" // PyGC_Head #include "pycore_pymem.h" // _Py_tracemalloc_config #include "pycore_traceback.h" -#include "hashtable.h" +#include "pycore_hashtable.h" #include "frameobject.h" // PyFrame_GetBack() #include "clinic/_tracemalloc.c.h" diff --git a/Modules/hashtable.c b/Modules/hashtable.c deleted file mode 100644 index 4a36a1e71c..0000000000 --- a/Modules/hashtable.c +++ /dev/null @@ -1,524 +0,0 @@ -/* The implementation of the hash table (_Py_hashtable_t) is based on the - cfuhash project: - http://sourceforge.net/projects/libcfu/ - - Copyright of cfuhash: - ---------------------------------- - Creation date: 2005-06-24 21:22:40 - Authors: Don - Change log: - - Copyright (c) 2005 Don Owens - All rights reserved. - - This code is released under the BSD license: - - Redistribution and use in source and binary forms, with or without - modification, are permitted provided that the following conditions - are met: - - * Redistributions of source code must retain the above copyright - notice, this list of conditions and the following disclaimer. - - * Redistributions in binary form must reproduce the above - copyright notice, this list of conditions and the following - disclaimer in the documentation and/or other materials provided - with the distribution. - - * Neither the name of the author nor the names of its - contributors may be used to endorse or promote products derived - from this software without specific prior written permission. - - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS - FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE - COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, - INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES - (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR - SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, - STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED - OF THE POSSIBILITY OF SUCH DAMAGE. - ---------------------------------- -*/ - -#include "Python.h" -#include "hashtable.h" - -#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)) -#define HASHTABLE_ITEM_SIZE(HT) \ - (sizeof(_Py_hashtable_entry_t) + (HT)->key_size + (HT)->data_size) - -#define ENTRY_READ_PDATA(TABLE, ENTRY, DATA_SIZE, PDATA) \ - do { \ - assert((DATA_SIZE) == (TABLE)->data_size); \ - memcpy((PDATA), _Py_HASHTABLE_ENTRY_PDATA(TABLE, (ENTRY)), \ - (DATA_SIZE)); \ - } while (0) - -#define ENTRY_WRITE_PDATA(TABLE, ENTRY, DATA_SIZE, PDATA) \ - do { \ - assert((DATA_SIZE) == (TABLE)->data_size); \ - memcpy((void *)_Py_HASHTABLE_ENTRY_PDATA((TABLE), (ENTRY)), \ - (PDATA), (DATA_SIZE)); \ - } while (0) - -/* Forward declaration */ -static void 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_uhash_t -_Py_hashtable_hash_ptr(struct _Py_hashtable_t *ht, const void *pkey) -{ - void *key; - - _Py_HASHTABLE_READ_KEY(ht, pkey, key); - return (Py_uhash_t)_Py_HashPointer(key); -} - - -int -_Py_hashtable_compare_direct(_Py_hashtable_t *ht, const void *pkey, - const _Py_hashtable_entry_t *entry) -{ - const void *pkey2 = _Py_HASHTABLE_ENTRY_PKEY(entry); - return (memcmp(pkey, pkey2, ht->key_size) == 0); -} - - -/* makes sure the real size of the buckets array is a power of 2 */ -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_t * -_Py_hashtable_new_full(size_t key_size, size_t data_size, - size_t init_size, - _Py_hashtable_hash_func hash_func, - _Py_hashtable_compare_func compare_func, - _Py_hashtable_allocator_t *allocator) -{ - _Py_hashtable_t *ht; - size_t buckets_size; - _Py_hashtable_allocator_t alloc; - - if (allocator == NULL) { - alloc.malloc = PyMem_RawMalloc; - alloc.free = PyMem_RawFree; - } - else - alloc = *allocator; - - ht = (_Py_hashtable_t *)alloc.malloc(sizeof(_Py_hashtable_t)); - if (ht == NULL) - return ht; - - ht->num_buckets = round_size(init_size); - ht->entries = 0; - ht->key_size = key_size; - ht->data_size = data_size; - - buckets_size = ht->num_buckets * 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->hash_func = hash_func; - ht->compare_func = compare_func; - ht->alloc = alloc; - return ht; -} - - -_Py_hashtable_t * -_Py_hashtable_new(size_t key_size, size_t data_size, - _Py_hashtable_hash_func hash_func, - _Py_hashtable_compare_func compare_func) -{ - return _Py_hashtable_new_full(key_size, data_size, - HASHTABLE_MIN_SIZE, - hash_func, compare_func, - NULL); -} - - -size_t -_Py_hashtable_size(_Py_hashtable_t *ht) -{ - size_t size; - - size = sizeof(_Py_hashtable_t); - - /* buckets */ - size += ht->num_buckets * sizeof(_Py_hashtable_entry_t *); - - /* entries */ - size += ht->entries * HASHTABLE_ITEM_SIZE(ht); - - return size; -} - - -#ifdef Py_DEBUG -void -_Py_hashtable_print_stats(_Py_hashtable_t *ht) -{ - size_t size; - size_t chain_len, max_chain_len, total_chain_len, nchains; - _Py_hashtable_entry_t *entry; - size_t hv; - double load; - - size = _Py_hashtable_size(ht); - - load = (double)ht->entries / ht->num_buckets; - - max_chain_len = 0; - total_chain_len = 0; - nchains = 0; - for (hv = 0; hv < ht->num_buckets; hv++) { - entry = TABLE_HEAD(ht, hv); - if (entry != NULL) { - chain_len = 0; - for (; entry; entry = ENTRY_NEXT(entry)) { - chain_len++; - } - if (chain_len > max_chain_len) - max_chain_len = chain_len; - total_chain_len += chain_len; - nchains++; - } - } - printf("hash table %p: entries=%" - PY_FORMAT_SIZE_T "u/%" PY_FORMAT_SIZE_T "u (%.0f%%), ", - (void *)ht, ht->entries, ht->num_buckets, load * 100.0); - if (nchains) - printf("avg_chain_len=%.1f, ", (double)total_chain_len / nchains); - printf("max_chain_len=%" PY_FORMAT_SIZE_T "u, %" PY_FORMAT_SIZE_T "u KiB\n", - max_chain_len, size / 1024); -} -#endif - - -_Py_hashtable_entry_t * -_Py_hashtable_get_entry(_Py_hashtable_t *ht, - size_t key_size, const void *pkey) -{ - Py_uhash_t key_hash; - size_t index; - _Py_hashtable_entry_t *entry; - - assert(key_size == ht->key_size); - - key_hash = ht->hash_func(ht, pkey); - index = key_hash & (ht->num_buckets - 1); - - for (entry = TABLE_HEAD(ht, index); entry != NULL; entry = ENTRY_NEXT(entry)) { - if (entry->key_hash == key_hash && ht->compare_func(ht, pkey, entry)) - break; - } - - return entry; -} - - -static int -_Py_hashtable_pop_entry(_Py_hashtable_t *ht, size_t key_size, const void *pkey, - void *data, size_t data_size) -{ - Py_uhash_t key_hash; - size_t index; - _Py_hashtable_entry_t *entry, *previous; - - assert(key_size == ht->key_size); - - key_hash = ht->hash_func(ht, pkey); - index = key_hash & (ht->num_buckets - 1); - - previous = NULL; - for (entry = TABLE_HEAD(ht, index); entry != NULL; entry = ENTRY_NEXT(entry)) { - if (entry->key_hash == key_hash && ht->compare_func(ht, pkey, entry)) - break; - previous = entry; - } - - if (entry == NULL) - return 0; - - _Py_slist_remove(&ht->buckets[index], (_Py_slist_item_t *)previous, - (_Py_slist_item_t *)entry); - ht->entries--; - - if (data != NULL) - ENTRY_READ_PDATA(ht, entry, data_size, data); - ht->alloc.free(entry); - - if ((float)ht->entries / (float)ht->num_buckets < HASHTABLE_LOW) - hashtable_rehash(ht); - return 1; -} - - -int -_Py_hashtable_set(_Py_hashtable_t *ht, size_t key_size, const void *pkey, - size_t data_size, const void *data) -{ - Py_uhash_t key_hash; - size_t index; - _Py_hashtable_entry_t *entry; - - assert(key_size == ht->key_size); - - assert(data != NULL || data_size == 0); -#ifndef NDEBUG - /* Don't write the assertion on a single line because it is interesting - to know the duplicated entry if the assertion failed. The entry can - be read using a debugger. */ - entry = _Py_hashtable_get_entry(ht, key_size, pkey); - assert(entry == NULL); -#endif - - key_hash = ht->hash_func(ht, pkey); - index = key_hash & (ht->num_buckets - 1); - - entry = ht->alloc.malloc(HASHTABLE_ITEM_SIZE(ht)); - if (entry == NULL) { - /* memory allocation failed */ - return -1; - } - - entry->key_hash = key_hash; - memcpy((void *)_Py_HASHTABLE_ENTRY_PKEY(entry), pkey, ht->key_size); - if (data) - ENTRY_WRITE_PDATA(ht, entry, data_size, data); - - _Py_slist_prepend(&ht->buckets[index], (_Py_slist_item_t*)entry); - ht->entries++; - - if ((float)ht->entries / (float)ht->num_buckets > HASHTABLE_HIGH) - hashtable_rehash(ht); - return 0; -} - - -int -_Py_hashtable_get(_Py_hashtable_t *ht, size_t key_size,const void *pkey, - size_t data_size, void *data) -{ - _Py_hashtable_entry_t *entry; - - assert(data != NULL); - - entry = _Py_hashtable_get_entry(ht, key_size, pkey); - if (entry == NULL) - return 0; - ENTRY_READ_PDATA(ht, entry, data_size, data); - return 1; -} - - -int -_Py_hashtable_pop(_Py_hashtable_t *ht, size_t key_size, const void *pkey, - size_t data_size, void *data) -{ - assert(data != NULL); - return _Py_hashtable_pop_entry(ht, key_size, pkey, data, data_size); -} - - -/* Code commented since the function is not needed in Python */ -#if 0 -void -_Py_hashtable_delete(_Py_hashtable_t *ht, size_t key_size, const void *pkey) -{ -#ifndef NDEBUG - int found = _Py_hashtable_pop_entry(ht, key_size, pkey, NULL, 0); - assert(found); -#else - (void)_Py_hashtable_pop_entry(ht, key_size, pkey, NULL, 0); -#endif -} -#endif - - -int -_Py_hashtable_foreach(_Py_hashtable_t *ht, - _Py_hashtable_foreach_func func, - void *arg) -{ - _Py_hashtable_entry_t *entry; - size_t hv; - - for (hv = 0; hv < ht->num_buckets; hv++) { - for (entry = TABLE_HEAD(ht, hv); entry; entry = ENTRY_NEXT(entry)) { - int res = func(ht, entry, arg); - if (res) - return res; - } - } - return 0; -} - - -static void -hashtable_rehash(_Py_hashtable_t *ht) -{ - size_t buckets_size, new_size, bucket; - _Py_slist_t *old_buckets = NULL; - size_t old_num_buckets; - - new_size = round_size((size_t)(ht->entries * HASHTABLE_REHASH_FACTOR)); - if (new_size == ht->num_buckets) - return; - - old_num_buckets = ht->num_buckets; - - buckets_size = new_size * sizeof(ht->buckets[0]); - old_buckets = ht->buckets; - ht->buckets = ht->alloc.malloc(buckets_size); - if (ht->buckets == NULL) { - /* cancel rehash on memory allocation failure */ - ht->buckets = old_buckets ; - /* memory allocation failed */ - return; - } - memset(ht->buckets, 0, buckets_size); - - ht->num_buckets = new_size; - - for (bucket = 0; bucket < old_num_buckets; bucket++) { - _Py_hashtable_entry_t *entry, *next; - for (entry = BUCKETS_HEAD(old_buckets[bucket]); entry != NULL; entry = next) { - size_t entry_index; - - - assert(ht->hash_func(ht, _Py_HASHTABLE_ENTRY_PKEY(entry)) == entry->key_hash); - next = ENTRY_NEXT(entry); - entry_index = entry->key_hash & (new_size - 1); - - _Py_slist_prepend(&ht->buckets[entry_index], (_Py_slist_item_t*)entry); - } - } - - ht->alloc.free(old_buckets); -} - - -void -_Py_hashtable_clear(_Py_hashtable_t *ht) -{ - _Py_hashtable_entry_t *entry, *next; - size_t i; - - for (i=0; i < ht->num_buckets; i++) { - for (entry = TABLE_HEAD(ht, i); entry != NULL; entry = next) { - next = ENTRY_NEXT(entry); - ht->alloc.free(entry); - } - _Py_slist_init(&ht->buckets[i]); - } - ht->entries = 0; - hashtable_rehash(ht); -} - - -void -_Py_hashtable_destroy(_Py_hashtable_t *ht) -{ - size_t i; - - for (i = 0; i < ht->num_buckets; i++) { - _Py_slist_item_t *entry = ht->buckets[i].head; - while (entry) { - _Py_slist_item_t *entry_next = entry->next; - ht->alloc.free(entry); - entry = entry_next; - } - } - - ht->alloc.free(ht->buckets); - ht->alloc.free(ht); -} - - -_Py_hashtable_t * -_Py_hashtable_copy(_Py_hashtable_t *src) -{ - const size_t key_size = src->key_size; - const size_t data_size = src->data_size; - _Py_hashtable_t *dst; - _Py_hashtable_entry_t *entry; - size_t bucket; - int err; - - dst = _Py_hashtable_new_full(key_size, data_size, - src->num_buckets, - src->hash_func, - src->compare_func, - &src->alloc); - if (dst == NULL) - return NULL; - - for (bucket=0; bucket < src->num_buckets; bucket++) { - entry = TABLE_HEAD(src, bucket); - for (; entry; entry = ENTRY_NEXT(entry)) { - const void *pkey = _Py_HASHTABLE_ENTRY_PKEY(entry); - const void *pdata = _Py_HASHTABLE_ENTRY_PDATA(src, entry); - err = _Py_hashtable_set(dst, key_size, pkey, data_size, pdata); - if (err) { - _Py_hashtable_destroy(dst); - return NULL; - } - } - } - return dst; -} diff --git a/Modules/hashtable.h b/Modules/hashtable.h deleted file mode 100644 index dbec23d285..0000000000 --- a/Modules/hashtable.h +++ /dev/null @@ -1,211 +0,0 @@ -#ifndef Py_HASHTABLE_H -#define Py_HASHTABLE_H -/* The whole API is private */ -#ifndef Py_LIMITED_API - -/* Single linked list */ - -typedef struct _Py_slist_item_s { - struct _Py_slist_item_s *next; -} _Py_slist_item_t; - -typedef struct { - _Py_slist_item_t *head; -} _Py_slist_t; - -#define _Py_SLIST_ITEM_NEXT(ITEM) (((_Py_slist_item_t *)ITEM)->next) - -#define _Py_SLIST_HEAD(SLIST) (((_Py_slist_t *)SLIST)->head) - - -/* _Py_hashtable: table entry */ - -typedef struct { - /* used by _Py_hashtable_t.buckets to link entries */ - _Py_slist_item_t _Py_slist_item; - - Py_uhash_t key_hash; - - /* key (key_size bytes) and then data (data_size bytes) follows */ -} _Py_hashtable_entry_t; - -#define _Py_HASHTABLE_ENTRY_PKEY(ENTRY) \ - ((const void *)((char *)(ENTRY) \ - + sizeof(_Py_hashtable_entry_t))) - -#define _Py_HASHTABLE_ENTRY_PDATA(TABLE, ENTRY) \ - ((const void *)((char *)(ENTRY) \ - + sizeof(_Py_hashtable_entry_t) \ - + (TABLE)->key_size)) - -/* Get a key value from pkey: use memcpy() rather than a pointer dereference - to avoid memory alignment issues. */ -#define _Py_HASHTABLE_READ_KEY(TABLE, PKEY, DST_KEY) \ - do { \ - assert(sizeof(DST_KEY) == (TABLE)->key_size); \ - memcpy(&(DST_KEY), (PKEY), sizeof(DST_KEY)); \ - } while (0) - -#define _Py_HASHTABLE_ENTRY_READ_KEY(TABLE, ENTRY, KEY) \ - do { \ - assert(sizeof(KEY) == (TABLE)->key_size); \ - memcpy(&(KEY), _Py_HASHTABLE_ENTRY_PKEY(ENTRY), sizeof(KEY)); \ - } while (0) - -#define _Py_HASHTABLE_ENTRY_READ_DATA(TABLE, ENTRY, DATA) \ - do { \ - assert(sizeof(DATA) == (TABLE)->data_size); \ - memcpy(&(DATA), _Py_HASHTABLE_ENTRY_PDATA(TABLE, (ENTRY)), \ - sizeof(DATA)); \ - } while (0) - -#define _Py_HASHTABLE_ENTRY_WRITE_DATA(TABLE, ENTRY, DATA) \ - do { \ - assert(sizeof(DATA) == (TABLE)->data_size); \ - memcpy((void *)_Py_HASHTABLE_ENTRY_PDATA((TABLE), (ENTRY)), \ - &(DATA), sizeof(DATA)); \ - } while (0) - - -/* _Py_hashtable: prototypes */ - -/* Forward declaration */ -struct _Py_hashtable_t; - -typedef Py_uhash_t (*_Py_hashtable_hash_func) (struct _Py_hashtable_t *ht, - const void *pkey); -typedef int (*_Py_hashtable_compare_func) (struct _Py_hashtable_t *ht, - const void *pkey, - const _Py_hashtable_entry_t *he); - -typedef struct { - /* allocate a memory block */ - void* (*malloc) (size_t size); - - /* release a memory block */ - void (*free) (void *ptr); -} _Py_hashtable_allocator_t; - - -/* _Py_hashtable: table */ - -typedef struct _Py_hashtable_t { - size_t num_buckets; - size_t entries; /* Total number of entries in the table. */ - _Py_slist_t *buckets; - size_t key_size; - size_t data_size; - - _Py_hashtable_hash_func hash_func; - _Py_hashtable_compare_func compare_func; - _Py_hashtable_allocator_t alloc; -} _Py_hashtable_t; - -/* hash a pointer (void*) */ -PyAPI_FUNC(Py_uhash_t) _Py_hashtable_hash_ptr( - struct _Py_hashtable_t *ht, - const void *pkey); - -/* comparison using memcmp() */ -PyAPI_FUNC(int) _Py_hashtable_compare_direct( - _Py_hashtable_t *ht, - const void *pkey, - const _Py_hashtable_entry_t *entry); - -PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_new( - size_t key_size, - size_t data_size, - _Py_hashtable_hash_func hash_func, - _Py_hashtable_compare_func compare_func); - -PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_new_full( - size_t key_size, - size_t data_size, - size_t init_size, - _Py_hashtable_hash_func hash_func, - _Py_hashtable_compare_func compare_func, - _Py_hashtable_allocator_t *allocator); - -PyAPI_FUNC(void) _Py_hashtable_destroy(_Py_hashtable_t *ht); - -/* Return a copy of the hash table */ -PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_copy(_Py_hashtable_t *src); - -PyAPI_FUNC(void) _Py_hashtable_clear(_Py_hashtable_t *ht); - -typedef int (*_Py_hashtable_foreach_func) (_Py_hashtable_t *ht, - _Py_hashtable_entry_t *entry, - void *arg); - -/* Call func() on each entry of the hashtable. - Iteration stops if func() result is non-zero, in this case it's the result - of the call. Otherwise, the function returns 0. */ -PyAPI_FUNC(int) _Py_hashtable_foreach( - _Py_hashtable_t *ht, - _Py_hashtable_foreach_func func, - void *arg); - -PyAPI_FUNC(size_t) _Py_hashtable_size(_Py_hashtable_t *ht); - -/* Add a new entry to the hash. The key must not be present in the hash table. - Return 0 on success, -1 on memory error. - - Don't call directly this function, - but use _Py_HASHTABLE_SET() and _Py_HASHTABLE_SET_NODATA() macros */ -PyAPI_FUNC(int) _Py_hashtable_set( - _Py_hashtable_t *ht, - size_t key_size, - const void *pkey, - size_t data_size, - const void *data); - -#define _Py_HASHTABLE_SET(TABLE, KEY, DATA) \ - _Py_hashtable_set(TABLE, sizeof(KEY), &(KEY), sizeof(DATA), &(DATA)) - -#define _Py_HASHTABLE_SET_NODATA(TABLE, KEY) \ - _Py_hashtable_set(TABLE, sizeof(KEY), &(KEY), 0, NULL) - - -/* Get an entry. - Return NULL if the key does not exist. - - Don't call directly this function, but use _Py_HASHTABLE_GET_ENTRY() - macro */ -PyAPI_FUNC(_Py_hashtable_entry_t*) _Py_hashtable_get_entry( - _Py_hashtable_t *ht, - size_t key_size, - const void *pkey); - -#define _Py_HASHTABLE_GET_ENTRY(TABLE, KEY) \ - _Py_hashtable_get_entry(TABLE, sizeof(KEY), &(KEY)) - - -/* Get data from an entry. Copy entry data into data and return 1 if the entry - exists, return 0 if the entry does not exist. - - Don't call directly this function, but use _Py_HASHTABLE_GET() macro */ -PyAPI_FUNC(int) _Py_hashtable_get( - _Py_hashtable_t *ht, - size_t key_size, - const void *pkey, - size_t data_size, - void *data); - -#define _Py_HASHTABLE_GET(TABLE, KEY, DATA) \ - _Py_hashtable_get(TABLE, sizeof(KEY), &(KEY), sizeof(DATA), &(DATA)) - - -/* Don't call directly this function, but use _Py_HASHTABLE_POP() macro */ -PyAPI_FUNC(int) _Py_hashtable_pop( - _Py_hashtable_t *ht, - size_t key_size, - const void *pkey, - size_t data_size, - void *data); - -#define _Py_HASHTABLE_POP(TABLE, KEY, DATA) \ - _Py_hashtable_pop(TABLE, sizeof(KEY), &(KEY), sizeof(DATA), &(DATA)) - - -#endif /* Py_LIMITED_API */ -#endif diff --git a/PCbuild/pythoncore.vcxproj b/PCbuild/pythoncore.vcxproj index 73274ac9ac..b6b0cf3e99 100644 --- a/PCbuild/pythoncore.vcxproj +++ b/PCbuild/pythoncore.vcxproj @@ -181,6 +181,7 @@ + @@ -335,7 +336,6 @@ - @@ -462,6 +462,7 @@ + diff --git a/PCbuild/pythoncore.vcxproj.filters b/PCbuild/pythoncore.vcxproj.filters index 254c8fbbea..10dfffba61 100644 --- a/PCbuild/pythoncore.vcxproj.filters +++ b/PCbuild/pythoncore.vcxproj.filters @@ -237,6 +237,9 @@ Include + + Include + Include @@ -1034,6 +1037,9 @@ Python + + Modules + Python @@ -1142,9 +1148,6 @@ Modules - - Modules - PC diff --git a/Python/hashtable.c b/Python/hashtable.c new file mode 100644 index 0000000000..22b8459010 --- /dev/null +++ b/Python/hashtable.c @@ -0,0 +1,524 @@ +/* The implementation of the hash table (_Py_hashtable_t) is based on the + cfuhash project: + http://sourceforge.net/projects/libcfu/ + + Copyright of cfuhash: + ---------------------------------- + Creation date: 2005-06-24 21:22:40 + Authors: Don + Change log: + + Copyright (c) 2005 Don Owens + All rights reserved. + + This code is released under the BSD license: + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above + copyright notice, this list of conditions and the following + disclaimer in the documentation and/or other materials provided + with the distribution. + + * Neither the name of the author nor the names of its + contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + OF THE POSSIBILITY OF SUCH DAMAGE. + ---------------------------------- +*/ + +#include "Python.h" +#include "pycore_hashtable.h" + +#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)) +#define HASHTABLE_ITEM_SIZE(HT) \ + (sizeof(_Py_hashtable_entry_t) + (HT)->key_size + (HT)->data_size) + +#define ENTRY_READ_PDATA(TABLE, ENTRY, DATA_SIZE, PDATA) \ + do { \ + assert((DATA_SIZE) == (TABLE)->data_size); \ + memcpy((PDATA), _Py_HASHTABLE_ENTRY_PDATA(TABLE, (ENTRY)), \ + (DATA_SIZE)); \ + } while (0) + +#define ENTRY_WRITE_PDATA(TABLE, ENTRY, DATA_SIZE, PDATA) \ + do { \ + assert((DATA_SIZE) == (TABLE)->data_size); \ + memcpy((void *)_Py_HASHTABLE_ENTRY_PDATA((TABLE), (ENTRY)), \ + (PDATA), (DATA_SIZE)); \ + } while (0) + +/* Forward declaration */ +static void 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_uhash_t +_Py_hashtable_hash_ptr(struct _Py_hashtable_t *ht, const void *pkey) +{ + void *key; + + _Py_HASHTABLE_READ_KEY(ht, pkey, key); + return (Py_uhash_t)_Py_HashPointer(key); +} + + +int +_Py_hashtable_compare_direct(_Py_hashtable_t *ht, const void *pkey, + const _Py_hashtable_entry_t *entry) +{ + const void *pkey2 = _Py_HASHTABLE_ENTRY_PKEY(entry); + return (memcmp(pkey, pkey2, ht->key_size) == 0); +} + + +/* makes sure the real size of the buckets array is a power of 2 */ +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_t * +_Py_hashtable_new_full(size_t key_size, size_t data_size, + size_t init_size, + _Py_hashtable_hash_func hash_func, + _Py_hashtable_compare_func compare_func, + _Py_hashtable_allocator_t *allocator) +{ + _Py_hashtable_t *ht; + size_t buckets_size; + _Py_hashtable_allocator_t alloc; + + if (allocator == NULL) { + alloc.malloc = PyMem_RawMalloc; + alloc.free = PyMem_RawFree; + } + else + alloc = *allocator; + + ht = (_Py_hashtable_t *)alloc.malloc(sizeof(_Py_hashtable_t)); + if (ht == NULL) + return ht; + + ht->num_buckets = round_size(init_size); + ht->entries = 0; + ht->key_size = key_size; + ht->data_size = data_size; + + buckets_size = ht->num_buckets * 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->hash_func = hash_func; + ht->compare_func = compare_func; + ht->alloc = alloc; + return ht; +} + + +_Py_hashtable_t * +_Py_hashtable_new(size_t key_size, size_t data_size, + _Py_hashtable_hash_func hash_func, + _Py_hashtable_compare_func compare_func) +{ + return _Py_hashtable_new_full(key_size, data_size, + HASHTABLE_MIN_SIZE, + hash_func, compare_func, + NULL); +} + + +size_t +_Py_hashtable_size(_Py_hashtable_t *ht) +{ + size_t size; + + size = sizeof(_Py_hashtable_t); + + /* buckets */ + size += ht->num_buckets * sizeof(_Py_hashtable_entry_t *); + + /* entries */ + size += ht->entries * HASHTABLE_ITEM_SIZE(ht); + + return size; +} + + +#ifdef Py_DEBUG +void +_Py_hashtable_print_stats(_Py_hashtable_t *ht) +{ + size_t size; + size_t chain_len, max_chain_len, total_chain_len, nchains; + _Py_hashtable_entry_t *entry; + size_t hv; + double load; + + size = _Py_hashtable_size(ht); + + load = (double)ht->entries / ht->num_buckets; + + max_chain_len = 0; + total_chain_len = 0; + nchains = 0; + for (hv = 0; hv < ht->num_buckets; hv++) { + entry = TABLE_HEAD(ht, hv); + if (entry != NULL) { + chain_len = 0; + for (; entry; entry = ENTRY_NEXT(entry)) { + chain_len++; + } + if (chain_len > max_chain_len) + max_chain_len = chain_len; + total_chain_len += chain_len; + nchains++; + } + } + printf("hash table %p: entries=%" + PY_FORMAT_SIZE_T "u/%" PY_FORMAT_SIZE_T "u (%.0f%%), ", + (void *)ht, ht->entries, ht->num_buckets, load * 100.0); + if (nchains) + printf("avg_chain_len=%.1f, ", (double)total_chain_len / nchains); + printf("max_chain_len=%" PY_FORMAT_SIZE_T "u, %" PY_FORMAT_SIZE_T "u KiB\n", + max_chain_len, size / 1024); +} +#endif + + +_Py_hashtable_entry_t * +_Py_hashtable_get_entry(_Py_hashtable_t *ht, + size_t key_size, const void *pkey) +{ + Py_uhash_t key_hash; + size_t index; + _Py_hashtable_entry_t *entry; + + assert(key_size == ht->key_size); + + key_hash = ht->hash_func(ht, pkey); + index = key_hash & (ht->num_buckets - 1); + + for (entry = TABLE_HEAD(ht, index); entry != NULL; entry = ENTRY_NEXT(entry)) { + if (entry->key_hash == key_hash && ht->compare_func(ht, pkey, entry)) + break; + } + + return entry; +} + + +static int +_Py_hashtable_pop_entry(_Py_hashtable_t *ht, size_t key_size, const void *pkey, + void *data, size_t data_size) +{ + Py_uhash_t key_hash; + size_t index; + _Py_hashtable_entry_t *entry, *previous; + + assert(key_size == ht->key_size); + + key_hash = ht->hash_func(ht, pkey); + index = key_hash & (ht->num_buckets - 1); + + previous = NULL; + for (entry = TABLE_HEAD(ht, index); entry != NULL; entry = ENTRY_NEXT(entry)) { + if (entry->key_hash == key_hash && ht->compare_func(ht, pkey, entry)) + break; + previous = entry; + } + + if (entry == NULL) + return 0; + + _Py_slist_remove(&ht->buckets[index], (_Py_slist_item_t *)previous, + (_Py_slist_item_t *)entry); + ht->entries--; + + if (data != NULL) + ENTRY_READ_PDATA(ht, entry, data_size, data); + ht->alloc.free(entry); + + if ((float)ht->entries / (float)ht->num_buckets < HASHTABLE_LOW) + hashtable_rehash(ht); + return 1; +} + + +int +_Py_hashtable_set(_Py_hashtable_t *ht, size_t key_size, const void *pkey, + size_t data_size, const void *data) +{ + Py_uhash_t key_hash; + size_t index; + _Py_hashtable_entry_t *entry; + + assert(key_size == ht->key_size); + + assert(data != NULL || data_size == 0); +#ifndef NDEBUG + /* Don't write the assertion on a single line because it is interesting + to know the duplicated entry if the assertion failed. The entry can + be read using a debugger. */ + entry = _Py_hashtable_get_entry(ht, key_size, pkey); + assert(entry == NULL); +#endif + + key_hash = ht->hash_func(ht, pkey); + index = key_hash & (ht->num_buckets - 1); + + entry = ht->alloc.malloc(HASHTABLE_ITEM_SIZE(ht)); + if (entry == NULL) { + /* memory allocation failed */ + return -1; + } + + entry->key_hash = key_hash; + memcpy((void *)_Py_HASHTABLE_ENTRY_PKEY(entry), pkey, ht->key_size); + if (data) + ENTRY_WRITE_PDATA(ht, entry, data_size, data); + + _Py_slist_prepend(&ht->buckets[index], (_Py_slist_item_t*)entry); + ht->entries++; + + if ((float)ht->entries / (float)ht->num_buckets > HASHTABLE_HIGH) + hashtable_rehash(ht); + return 0; +} + + +int +_Py_hashtable_get(_Py_hashtable_t *ht, size_t key_size,const void *pkey, + size_t data_size, void *data) +{ + _Py_hashtable_entry_t *entry; + + assert(data != NULL); + + entry = _Py_hashtable_get_entry(ht, key_size, pkey); + if (entry == NULL) + return 0; + ENTRY_READ_PDATA(ht, entry, data_size, data); + return 1; +} + + +int +_Py_hashtable_pop(_Py_hashtable_t *ht, size_t key_size, const void *pkey, + size_t data_size, void *data) +{ + assert(data != NULL); + return _Py_hashtable_pop_entry(ht, key_size, pkey, data, data_size); +} + + +/* Code commented since the function is not needed in Python */ +#if 0 +void +_Py_hashtable_delete(_Py_hashtable_t *ht, size_t key_size, const void *pkey) +{ +#ifndef NDEBUG + int found = _Py_hashtable_pop_entry(ht, key_size, pkey, NULL, 0); + assert(found); +#else + (void)_Py_hashtable_pop_entry(ht, key_size, pkey, NULL, 0); +#endif +} +#endif + + +int +_Py_hashtable_foreach(_Py_hashtable_t *ht, + _Py_hashtable_foreach_func func, + void *arg) +{ + _Py_hashtable_entry_t *entry; + size_t hv; + + for (hv = 0; hv < ht->num_buckets; hv++) { + for (entry = TABLE_HEAD(ht, hv); entry; entry = ENTRY_NEXT(entry)) { + int res = func(ht, entry, arg); + if (res) + return res; + } + } + return 0; +} + + +static void +hashtable_rehash(_Py_hashtable_t *ht) +{ + size_t buckets_size, new_size, bucket; + _Py_slist_t *old_buckets = NULL; + size_t old_num_buckets; + + new_size = round_size((size_t)(ht->entries * HASHTABLE_REHASH_FACTOR)); + if (new_size == ht->num_buckets) + return; + + old_num_buckets = ht->num_buckets; + + buckets_size = new_size * sizeof(ht->buckets[0]); + old_buckets = ht->buckets; + ht->buckets = ht->alloc.malloc(buckets_size); + if (ht->buckets == NULL) { + /* cancel rehash on memory allocation failure */ + ht->buckets = old_buckets ; + /* memory allocation failed */ + return; + } + memset(ht->buckets, 0, buckets_size); + + ht->num_buckets = new_size; + + for (bucket = 0; bucket < old_num_buckets; bucket++) { + _Py_hashtable_entry_t *entry, *next; + for (entry = BUCKETS_HEAD(old_buckets[bucket]); entry != NULL; entry = next) { + size_t entry_index; + + + assert(ht->hash_func(ht, _Py_HASHTABLE_ENTRY_PKEY(entry)) == entry->key_hash); + next = ENTRY_NEXT(entry); + entry_index = entry->key_hash & (new_size - 1); + + _Py_slist_prepend(&ht->buckets[entry_index], (_Py_slist_item_t*)entry); + } + } + + ht->alloc.free(old_buckets); +} + + +void +_Py_hashtable_clear(_Py_hashtable_t *ht) +{ + _Py_hashtable_entry_t *entry, *next; + size_t i; + + for (i=0; i < ht->num_buckets; i++) { + for (entry = TABLE_HEAD(ht, i); entry != NULL; entry = next) { + next = ENTRY_NEXT(entry); + ht->alloc.free(entry); + } + _Py_slist_init(&ht->buckets[i]); + } + ht->entries = 0; + hashtable_rehash(ht); +} + + +void +_Py_hashtable_destroy(_Py_hashtable_t *ht) +{ + size_t i; + + for (i = 0; i < ht->num_buckets; i++) { + _Py_slist_item_t *entry = ht->buckets[i].head; + while (entry) { + _Py_slist_item_t *entry_next = entry->next; + ht->alloc.free(entry); + entry = entry_next; + } + } + + ht->alloc.free(ht->buckets); + ht->alloc.free(ht); +} + + +_Py_hashtable_t * +_Py_hashtable_copy(_Py_hashtable_t *src) +{ + const size_t key_size = src->key_size; + const size_t data_size = src->data_size; + _Py_hashtable_t *dst; + _Py_hashtable_entry_t *entry; + size_t bucket; + int err; + + dst = _Py_hashtable_new_full(key_size, data_size, + src->num_buckets, + src->hash_func, + src->compare_func, + &src->alloc); + if (dst == NULL) + return NULL; + + for (bucket=0; bucket < src->num_buckets; bucket++) { + entry = TABLE_HEAD(src, bucket); + for (; entry; entry = ENTRY_NEXT(entry)) { + const void *pkey = _Py_HASHTABLE_ENTRY_PKEY(entry); + const void *pdata = _Py_HASHTABLE_ENTRY_PDATA(src, entry); + err = _Py_hashtable_set(dst, key_size, pkey, data_size, pdata); + if (err) { + _Py_hashtable_destroy(dst); + return NULL; + } + } + } + return dst; +} diff --git a/Python/marshal.c b/Python/marshal.c index b4429aea50..d2bff524f3 100644 --- a/Python/marshal.c +++ b/Python/marshal.c @@ -12,7 +12,7 @@ #include "longintrepr.h" #include "code.h" #include "marshal.h" -#include "../Modules/hashtable.h" +#include "pycore_hashtable.h" /*[clinic input] module marshal -- cgit v1.2.1