bpo-40116: Add insertion order bit-vector to dict values to allow dicts to share keys more freely. (GH-28520)

2 files changed, 10 insertions, 1 deletions

diff --git a/Include/cpython/dictobject.h b/Include/cpython/dictobject.h
index 7c63374c56..ba118788f7 100644
--- a/Include/cpython/dictobject.h
+++ b/Include/cpython/dictobject.h
@@ -3,6 +3,7 @@
 #endif
 
 typedef struct _dictkeysobject PyDictKeysObject;
+typedef struct _dictvalues PyDictValues;
 
 /* The ma_values pointer is NULL for a combined table
  * or points to an array of PyObject* for a split table
@@ -24,7 +25,7 @@ typedef struct {
 
        If ma_values is not NULL, the table is splitted:
        keys are stored in ma_keys and values are stored in ma_values */
-    PyObject **ma_values;
+    PyDictValues *ma_values;
 } PyDictObject;
 
 PyAPI_FUNC(PyObject *) _PyDict_GetItem_KnownHash(PyObject *mp, PyObject *key,
diff --git a/Include/internal/pycore_dict.h b/Include/internal/pycore_dict.h
index 2becc30beb..d37ef71bbc 100644
--- a/Include/internal/pycore_dict.h
+++ b/Include/internal/pycore_dict.h
@@ -71,6 +71,14 @@ struct _dictkeysobject {
        see the DK_ENTRIES() macro */
 };
 
+/* This must be no more than 16, for the order vector to fit in 64 bits */
+#define SHARED_KEYS_MAX_SIZE 16
+
+struct _dictvalues {
+    uint64_t mv_order;
+    PyObject *values[1];
+};
+
 #define DK_LOG_SIZE(dk)  ((dk)->dk_log2_size)
 #if SIZEOF_VOID_P > 4
 #define DK_SIZE(dk)      (((int64_t)1)<<DK_LOG_SIZE(dk))