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.

1 files changed, 218 insertions, 0 deletions

diff --git a/Include/internal/pycore_hashtable.h b/Include/internal/pycore_hashtable.h
new file mode 100644
index 0000000..585f76b
--- /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 */