Issue #16991: Add a C implementation of collections.OrderedDict.

3 files changed, 55 insertions, 3 deletions

diff --git a/Include/Python.h b/Include/Python.h
index 46d2ece..858dbd1 100644
--- a/Include/Python.h
+++ b/Include/Python.h
@@ -85,6 +85,7 @@
 #include "tupleobject.h"
 #include "listobject.h"
 #include "dictobject.h"
+#include "odictobject.h"
 #include "enumobject.h"
 #include "setobject.h"
 #include "methodobject.h"
diff --git a/Include/dictobject.h b/Include/dictobject.h
index 1f4dedb..17262fe 100644
--- a/Include/dictobject.h
+++ b/Include/dictobject.h
@@ -27,6 +27,11 @@ typedef struct {
     PyObject **ma_values;
 } PyDictObject;
 
+typedef struct {
+    PyObject_HEAD
+    PyDictObject *dv_dict;
+} _PyDictViewObject;
+
 #endif /* Py_LIMITED_API */
 
 PyAPI_DATA(PyTypeObject) PyDict_Type;
@@ -40,9 +45,9 @@ PyAPI_DATA(PyTypeObject) PyDictValues_Type;
 #define PyDict_Check(op) \
                  PyType_FastSubclass(Py_TYPE(op), Py_TPFLAGS_DICT_SUBCLASS)
 #define PyDict_CheckExact(op) (Py_TYPE(op) == &PyDict_Type)
-#define PyDictKeys_Check(op) (Py_TYPE(op) == &PyDictKeys_Type)
-#define PyDictItems_Check(op) (Py_TYPE(op) == &PyDictItems_Type)
-#define PyDictValues_Check(op) (Py_TYPE(op) == &PyDictValues_Type)
+#define PyDictKeys_Check(op) (PyObject_IsInstance(op, (PyObject *)&PyDictKeys_Type))
+#define PyDictItems_Check(op) (PyObject_IsInstance(op, (PyObject *)&PyDictItems_Type))
+#define PyDictValues_Check(op) (PyObject_IsInstance(op, (PyObject *)&PyDictValues_Type))
 /* This excludes Values, since they are not sets. */
 # define PyDictViewSet_Check(op) \
     (PyDictKeys_Check(op) || PyDictItems_Check(op))
@@ -75,6 +80,7 @@ PyDictKeysObject *_PyDict_NewKeysForClass(void);
 PyAPI_FUNC(PyObject *) PyObject_GenericGetDict(PyObject *, void *);
 PyAPI_FUNC(int) _PyDict_Next(
     PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value, Py_hash_t *hash);
+PyObject *_PyDictView_New(PyObject *, PyTypeObject *);
 #endif
 PyAPI_FUNC(PyObject *) PyDict_Keys(PyObject *mp);
 PyAPI_FUNC(PyObject *) PyDict_Values(PyObject *mp);
@@ -88,6 +94,9 @@ PyAPI_FUNC(PyObject *) _PyDict_NewPresized(Py_ssize_t minused);
 PyAPI_FUNC(void) _PyDict_MaybeUntrack(PyObject *mp);
 PyAPI_FUNC(int) _PyDict_HasOnlyStringKeys(PyObject *mp);
 Py_ssize_t _PyDict_KeysSize(PyDictKeysObject *keys);
+PyObject *_PyDict_SizeOf(PyDictObject *);
+PyObject *_PyDict_Pop(PyDictObject *, PyObject *, PyObject *);
+PyObject *_PyDict_FromKeys(PyObject *, PyObject *, PyObject *);
 #define _PyDict_HasSplitTable(d) ((d)->ma_values != NULL)
 
 PyAPI_FUNC(int) PyDict_ClearFreeList(void);
diff --git a/Include/odictobject.h b/Include/odictobject.h
new file mode 100644
index 0000000..a32fbc5
--- /dev/null
+++ b/Include/odictobject.h
@@ -0,0 +1,42 @@
+#ifndef Py_ODICTOBJECT_H
+#define Py_ODICTOBJECT_H
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+
+/* OrderedDict */
+
+#ifndef Py_LIMITED_API
+
+typedef struct _odictobject PyODictObject;
+
+PyAPI_DATA(PyTypeObject) PyODict_Type;
+PyAPI_DATA(PyTypeObject) PyODictIter_Type;
+PyAPI_DATA(PyTypeObject) PyODictKeys_Type;
+PyAPI_DATA(PyTypeObject) PyODictItems_Type;
+PyAPI_DATA(PyTypeObject) PyODictValues_Type;
+
+#endif /* Py_LIMITED_API */
+
+#define PyODict_Check(op) PyObject_IsInstance(op, (PyObject *)&PyODict_Type)
+#define PyODict_CheckExact(op) (Py_TYPE(op) == &PyODict_Type)
+#define PyODict_SIZE(op) ((PyDictObject *)op)->ma_used
+#define PyODict_HasKey(od, key) (PyMapping_HasKey(PyObject *)od, key)
+
+PyAPI_FUNC(PyObject *) PyODict_New(void);
+PyAPI_FUNC(int) PyODict_SetItem(PyObject *od, PyObject *key, PyObject *item);
+PyAPI_FUNC(int) PyODict_DelItem(PyObject *od, PyObject *key);
+
+/* wrappers around PyDict* functions */
+#define PyODict_GetItem(od, key) PyDict_GetItem((PyObject *)od, key)
+#define PyODict_Contains(od, key) PyDict_Contains((PyObject *)od, key)
+#define PyODict_Size(od) PyDict_Size((PyObject *)od)
+#define PyODict_GetItemString(od, key) \
+    PyDict_GetItemString((PyObject *)od, key)
+#define Py_ODict_GetItemId(od, key)  _PyDict_GetItemId((PyObject *)od, key)
+
+#ifdef __cplusplus
+}
+#endif
+#endif /* !Py_ODICTOBJECT_H */