Skip to content

Commit 96c6af9

Browse files
ericsnowcurrentlyericsnowcurrently
committed
Issue python#16991: Add a C implementation of collections.OrderedDict.
1 parent 0a3297d commit 96c6af9

12 files changed

Lines changed: 2860 additions & 195 deletions

File tree

‎Include/Python.h‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -85,6 +85,7 @@
8585
#include "tupleobject.h"
8686
#include "listobject.h"
8787
#include "dictobject.h"
88+
#include "odictobject.h"
8889
#include "enumobject.h"
8990
#include "setobject.h"
9091
#include "methodobject.h"

‎Include/dictobject.h‎

Lines changed: 12 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,11 @@ typedef struct {
2727
PyObject **ma_values;
2828
} PyDictObject;
2929

30+
typedef struct {
31+
PyObject_HEAD
32+
PyDictObject *dv_dict;
33+
} _PyDictViewObject;
34+
3035
#endif /* Py_LIMITED_API */
3136

3237
PyAPI_DATA(PyTypeObject) PyDict_Type;
@@ -40,9 +45,9 @@ PyAPI_DATA(PyTypeObject) PyDictValues_Type;
4045
#define PyDict_Check(op) \
4146
PyType_FastSubclass(Py_TYPE(op), Py_TPFLAGS_DICT_SUBCLASS)
4247
#define PyDict_CheckExact(op) (Py_TYPE(op) == &PyDict_Type)
43-
#define PyDictKeys_Check(op) (Py_TYPE(op) == &PyDictKeys_Type)
44-
#define PyDictItems_Check(op) (Py_TYPE(op) == &PyDictItems_Type)
45-
#define PyDictValues_Check(op) (Py_TYPE(op) == &PyDictValues_Type)
48+
#define PyDictKeys_Check(op) (PyObject_IsInstance(op, (PyObject *)&PyDictKeys_Type))
49+
#define PyDictItems_Check(op) (PyObject_IsInstance(op, (PyObject *)&PyDictItems_Type))
50+
#define PyDictValues_Check(op) (PyObject_IsInstance(op, (PyObject *)&PyDictValues_Type))
4651
/* This excludes Values, since they are not sets. */
4752
# define PyDictViewSet_Check(op) \
4853
(PyDictKeys_Check(op) || PyDictItems_Check(op))
@@ -75,6 +80,7 @@ PyDictKeysObject *_PyDict_NewKeysForClass(void);
7580
PyAPI_FUNC(PyObject *) PyObject_GenericGetDict(PyObject *, void *);
7681
PyAPI_FUNC(int) _PyDict_Next(
7782
PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value, Py_hash_t *hash);
83+
PyObject *_PyDictView_New(PyObject *, PyTypeObject *);
7884
#endif
7985
PyAPI_FUNC(PyObject *) PyDict_Keys(PyObject *mp);
8086
PyAPI_FUNC(PyObject *) PyDict_Values(PyObject *mp);
@@ -88,6 +94,9 @@ PyAPI_FUNC(PyObject *) _PyDict_NewPresized(Py_ssize_t minused);
8894
PyAPI_FUNC(void) _PyDict_MaybeUntrack(PyObject *mp);
8995
PyAPI_FUNC(int) _PyDict_HasOnlyStringKeys(PyObject *mp);
9096
Py_ssize_t _PyDict_KeysSize(PyDictKeysObject *keys);
97+
PyObject *_PyDict_SizeOf(PyDictObject *);
98+
PyObject *_PyDict_Pop(PyDictObject *, PyObject *, PyObject *);
99+
PyObject *_PyDict_FromKeys(PyObject *, PyObject *, PyObject *);
91100
#define _PyDict_HasSplitTable(d) ((d)->ma_values != NULL)
92101

93102
PyAPI_FUNC(int) PyDict_ClearFreeList(void);

‎Include/odictobject.h‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
#ifndef Py_ODICTOBJECT_H
2+
#define Py_ODICTOBJECT_H
3+
#ifdef __cplusplus
4+
extern "C" {
5+
#endif
6+
7+
8+
/* OrderedDict */
9+
10+
#ifndef Py_LIMITED_API
11+
12+
typedef struct _odictobject PyODictObject;
13+
14+
PyAPI_DATA(PyTypeObject) PyODict_Type;
15+
PyAPI_DATA(PyTypeObject) PyODictIter_Type;
16+
PyAPI_DATA(PyTypeObject) PyODictKeys_Type;
17+
PyAPI_DATA(PyTypeObject) PyODictItems_Type;
18+
PyAPI_DATA(PyTypeObject) PyODictValues_Type;
19+
20+
#endif /* Py_LIMITED_API */
21+
22+
#define PyODict_Check(op) PyObject_IsInstance(op, (PyObject *)&PyODict_Type)
23+
#define PyODict_CheckExact(op) (Py_TYPE(op) == &PyODict_Type)
24+
#define PyODict_SIZE(op) ((PyDictObject *)op)->ma_used
25+
#define PyODict_HasKey(od, key) (PyMapping_HasKey(PyObject *)od, key)
26+
27+
PyAPI_FUNC(PyObject *) PyODict_New(void);
28+
PyAPI_FUNC(int) PyODict_SetItem(PyObject *od, PyObject *key, PyObject *item);
29+
PyAPI_FUNC(int) PyODict_DelItem(PyObject *od, PyObject *key);
30+
31+
/* wrappers around PyDict* functions */
32+
#define PyODict_GetItem(od, key) PyDict_GetItem((PyObject *)od, key)
33+
#define PyODict_Contains(od, key) PyDict_Contains((PyObject *)od, key)
34+
#define PyODict_Size(od) PyDict_Size((PyObject *)od)
35+
#define PyODict_GetItemString(od, key) \
36+
PyDict_GetItemString((PyObject *)od, key)
37+
#define Py_ODict_GetItemId(od, key) _PyDict_GetItemId((PyObject *)od, key)
38+
39+
#ifdef __cplusplus
40+
}
41+
#endif
42+
#endif /* !Py_ODICTOBJECT_H */

‎Lib/collections/__init__.py‎

Lines changed: 19 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,6 @@
77
import _collections_abc
88
__all__ += _collections_abc.__all__
99

10-
from _collections import deque, defaultdict
1110
from operator import itemgetter as _itemgetter, eq as _eq
1211
from keyword import iskeyword as _iskeyword
1312
import sys as _sys
@@ -16,7 +15,18 @@
1615
from itertools import repeat as _repeat, chain as _chain, starmap as _starmap
1716
from reprlib import recursive_repr as _recursive_repr
1817

19-
MutableSequence.register(deque)
18+
try:
19+
from _collections import deque
20+
except ImportError:
21+
pass
22+
else:
23+
MutableSequence.register(deque)
24+
25+
try:
26+
from _collections import defaultdict
27+
except ImportError:
28+
pass
29+
2030

2131
################################################################################
2232
### OrderedDict
@@ -264,6 +274,13 @@ def __eq__(self, other):
264274
return dict.__eq__(self, other)
265275

266276

277+
try:
278+
from _collections import OrderedDict
279+
except ImportError:
280+
# Leave the pure Python version in place.
281+
pass
282+
283+
267284
################################################################################
268285
### namedtuple
269286
################################################################################

0 commit comments

Comments
 (0)