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.
diff --git a/Objects/dict-common.h b/Objects/dict-common.h
index 2912eb9..5f9afdb 100644
--- a/Objects/dict-common.h
+++ b/Objects/dict-common.h
@@ -8,15 +8,25 @@
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