Implement compact dict

Issue #27350: `dict` implementation is changed like PyPy. It is more compact
and preserves insertion order.

_PyDict_Dummy() function has been removed.

Disable test_gdb: python-gdb.py is not updated yet to the new structure of
compact dictionaries (issue #28023).

Patch written by INADA Naoki.

1 files changed, 13 insertions, 3 deletions

diff --git a/Objects/dict-common.h b/Objects/dict-common.h
index 2912eb94ea..5f9afdb1f9 100644
--- a/Objects/dict-common.h
+++ b/Objects/dict-common.h
@@ -8,15 +8,25 @@ 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;
     Py_ssize_t dk_size;
     dict_lookup_func dk_lookup;
     Py_ssize_t dk_usable;
-    PyDictKeyEntry dk_entries[1];
+    Py_ssize_t dk_nentries;  /* How many entries are used. */
+    char dk_indices[8];      /* dynamically sized. 8 is minimum. */
 };
 
 #endif