hashtable.h now supports keys of any size

Issue #26588: hashtable.h now supports keys of any size, not only
sizeof(void*). It allows to support key larger than sizeof(void*), but also to
use less memory for key smaller than sizeof(void*).

1 files changed, 127 insertions, 38 deletions

diff --git a/Modules/hashtable.h b/Modules/hashtable.h
index a9f9993..6eb5737 100644
--- a/Modules/hashtable.h
+++ b/Modules/hashtable.h
@@ -1,9 +1,10 @@
 #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;
@@ -16,30 +17,55 @@ typedef struct {
 
 #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;
 
-    const void *key;
     Py_uhash_t key_hash;
 
-    /* data follows */
+    /* key (key_size bytes) and then data (data_size bytes) follows */
 } _Py_hashtable_entry_t;
 
-#define _Py_HASHTABLE_ENTRY_DATA(ENTRY) \
-        ((char *)(ENTRY) + sizeof(_Py_hashtable_entry_t))
+#define _Py_HASHTABLE_ENTRY_KEY(ENTRY) \
+        ((const void *)((char *)(ENTRY) + sizeof(_Py_hashtable_entry_t)))
+
+#define _Py_HASHTABLE_ENTRY_DATA(TABLE, ENTRY) \
+        ((char *)(ENTRY) + sizeof(_Py_hashtable_entry_t) + (TABLE)->key_size)
+
+#define _Py_HASHTABLE_ENTRY_DATA_AS_VOID_P(TABLE, ENTRY) \
+        (*(void **)_Py_HASHTABLE_ENTRY_DATA(TABLE, ENTRY))
+
+/* Get a key value from pkey: use memcpy() rather than a pointer dereference
+   to avoid memory alignment issues. */
+#define _Py_HASHTABLE_READ_KEY(KEY_SIZE, PKEY, DST_KEY) \
+    do { \
+        assert(sizeof(DST_KEY) == (KEY_SIZE)); \
+        memcpy(&(DST_KEY), (PKEY), sizeof(DST_KEY)); \
+    } while (0)
 
-#define _Py_HASHTABLE_ENTRY_DATA_AS_VOID_P(ENTRY) \
-        (*(void **)_Py_HASHTABLE_ENTRY_DATA(ENTRY))
+#define _Py_HASHTABLE_ENTRY_READ_KEY(KEY_SIZE, ENTRY, KEY) \
+    do { \
+        assert(sizeof(KEY) == (KEY_SIZE)); \
+        memcpy(&(KEY), _Py_HASHTABLE_ENTRY_KEY(ENTRY), sizeof(KEY)); \
+    } while (0)
 
-#define _Py_HASHTABLE_ENTRY_READ_DATA(TABLE, DATA, DATA_SIZE, ENTRY) \
+#define _Py_HASHTABLE_ENTRY_READ_DATA(TABLE, ENTRY, DATA_SIZE, DATA) \
     do { \
         assert((DATA_SIZE) == (TABLE)->data_size); \
-        memcpy(DATA, _Py_HASHTABLE_ENTRY_DATA(ENTRY), DATA_SIZE); \
+        memcpy(DATA, _Py_HASHTABLE_ENTRY_DATA(TABLE, ENTRY), DATA_SIZE); \
     } while (0)
 
-typedef Py_uhash_t (*_Py_hashtable_hash_func) (const void *key);
-typedef int (*_Py_hashtable_compare_func) (const void *key, const _Py_hashtable_entry_t *he);
+
+/* _Py_hashtable: prototypes */
+
+typedef Py_uhash_t (*_Py_hashtable_hash_func) (size_t key_size,
+                                               const void *pkey);
+typedef int (*_Py_hashtable_compare_func) (size_t key_size,
+                                           const void *pkey,
+                                           const _Py_hashtable_entry_t *he);
 typedef void* (*_Py_hashtable_copy_data_func)(void *data);
 typedef void (*_Py_hashtable_free_data_func)(void *data);
 typedef size_t (*_Py_hashtable_get_data_size_func)(void *data);
@@ -52,10 +78,14 @@ typedef struct {
     void (*free) (void *ptr);
 } _Py_hashtable_allocator_t;
 
+
+/* _Py_hashtable: table */
+
 typedef struct {
     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;
@@ -66,16 +96,25 @@ typedef struct {
     _Py_hashtable_allocator_t alloc;
 } _Py_hashtable_t;
 
-/* hash and compare functions for integers and pointers */
-PyAPI_FUNC(Py_uhash_t) _Py_hashtable_hash_ptr(const void *key);
-PyAPI_FUNC(Py_uhash_t) _Py_hashtable_hash_int(const void *key);
-PyAPI_FUNC(int) _Py_hashtable_compare_direct(const void *key, const _Py_hashtable_entry_t *entry);
+/* hash a pointer (void*) */
+PyAPI_FUNC(Py_uhash_t) _Py_hashtable_hash_ptr(
+    size_t key_size,
+    const void *pkey);
+
+/* comparison using memcmp() */
+PyAPI_FUNC(int) _Py_hashtable_compare_direct(
+    size_t key_size,
+    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,
@@ -84,45 +123,95 @@ PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_new_full(
     _Py_hashtable_free_data_func free_data_func,
     _Py_hashtable_get_data_size_func get_data_size_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);
-PyAPI_FUNC(void) _Py_hashtable_destroy(_Py_hashtable_t *ht);
 
-typedef int (*_Py_hashtable_foreach_func) (_Py_hashtable_entry_t *entry, void *arg);
+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);
+    _Py_hashtable_foreach_func func,
+    void *arg);
+
 PyAPI_FUNC(size_t) _Py_hashtable_size(_Py_hashtable_t *ht);
 
-PyAPI_FUNC(_Py_hashtable_entry_t*) _Py_hashtable_get_entry(
-    _Py_hashtable_t *ht,
-    const void *key);
+/* 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,
-    const void *key,
-    void *data,
-    size_t data_size);
+    size_t key_size,
+    const void *pkey,
+    size_t data_size,
+    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,
-    const void *key,
-    void *data,
-    size_t data_size);
+    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,
-    const void *key,
-    void *data,
-    size_t data_size);
-PyAPI_FUNC(void) _Py_hashtable_delete(
-    _Py_hashtable_t *ht,
-    const void *key);
+    size_t key_size,
+    const void *pkey,
+    size_t data_size,
+    void *data);
 
-#define _Py_HASHTABLE_SET(TABLE, KEY, DATA) \
-    _Py_hashtable_set(TABLE, KEY, &(DATA), sizeof(DATA))
+#define _Py_HASHTABLE_POP(TABLE, KEY, DATA) \
+    _Py_hashtable_pop(TABLE, sizeof(KEY), &(KEY), sizeof(DATA), &(DATA))
 
-#define _Py_HASHTABLE_GET(TABLE, KEY, DATA) \
-    _Py_hashtable_get(TABLE, KEY, &(DATA), sizeof(DATA))
 
-#endif   /* Py_LIMITED_API */
+/* Delete an entry.
+
+   WARNING: The entry must exist. */
+PyAPI_FUNC(void) _Py_hashtable_delete(
+    _Py_hashtable_t *ht,
+    size_t key_size,
+    const void *pkey);
 
+#endif   /* Py_LIMITED_API */
 #endif