1 files changed, 59 insertions, 3 deletions

diff --git a/Objects/dict-common.h b/Objects/dict-common.h
index 2912eb94ea..c3baf59ef2 100644
--- a/Objects/dict-common.h
+++ b/Objects/dict-common.h
@@ -8,15 +8,71 @@ typedef struct {
     PyObject *me_value; /* This field is only meaningful for combined tables */
 } PyDictKeyEntry;
 
-typedef PyDictKeyEntry *(*dict_lookup_func)
-(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr);
+/* dict_lookup_func() returns index of entry which can be used like DK_ENTRIES(dk)[index].
+ * -1 when no entry found, -3 when compare raises error.
+ */
+typedef Py_ssize_t (*dict_lookup_func)
+(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr,
+ Py_ssize_t *hashpos);
 
+#define DKIX_EMPTY (-1)
+#define DKIX_DUMMY (-2)  /* Used internally */
+#define DKIX_ERROR (-3)
+
+/* See dictobject.c for actual layout of DictKeysObject */
 struct _dictkeysobject {
     Py_ssize_t dk_refcnt;
+
+    /* Size of the hash table (dk_indices). It must be a power of 2. */
     Py_ssize_t dk_size;
+
+    /* Function to lookup in the hash table (dk_indices):
+
+       - lookdict(): general-purpose, and may return DKIX_ERROR if (and
+         only if) a comparison raises an exception.
+
+       - lookdict_unicode(): specialized to Unicode string keys, comparison of
+         which can never raise an exception; that function can never return
+         DKIX_ERROR.
+
+       - lookdict_unicode_nodummy(): similar to lookdict_unicode() but further
+         specialized for Unicode string keys that cannot be the <dummy> value.
+
+       - lookdict_split(): Version of lookdict() for split tables. */
     dict_lookup_func dk_lookup;
+
+    /* Number of usable entries in dk_entries.
+       0 <= dk_usable <= USABLE_FRACTION(dk_size) */
     Py_ssize_t dk_usable;
-    PyDictKeyEntry dk_entries[1];
+
+    /* Number of used entries in dk_entries.
+       0 <= dk_nentries < dk_size */
+    Py_ssize_t dk_nentries;
+
+    /* Actual hash table of dk_size entries. It holds indices in dk_entries,
+       or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
+
+       Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
+
+       The size in bytes of an indice depends on dk_size:
+
+       - 1 byte if dk_size <= 0xff (char*)
+       - 2 bytes if dk_size <= 0xffff (int16_t*)
+       - 4 bytes if dk_size <= 0xffffffff (int32_t*)
+       - 8 bytes otherwise (int64_t*)
+
+       Dynamically sized, 8 is minimum. */
+    union {
+        int8_t as_1[8];
+        int16_t as_2[4];
+        int32_t as_4[2];
+#if SIZEOF_VOID_P > 4
+        int64_t as_8[1];
+#endif
+    } dk_indices;
+
+    /* "PyDictKeyEntry dk_entries[dk_usable];" array follows:
+       see the DK_ENTRIES() macro */
 };
 
 #endif