diff options
| -rw-r--r-- | Include/Python.h | 1 | ||||
| -rw-r--r-- | Include/dictobject.h | 15 | ||||
| -rw-r--r-- | Include/odictobject.h | 42 | ||||
| -rw-r--r-- | Lib/collections/__init__.py | 21 | ||||
| -rw-r--r-- | Lib/test/test_collections.py | 202 | ||||
| -rw-r--r-- | Makefile.pre.in | 1 | ||||
| -rw-r--r-- | Misc/NEWS | 2 | ||||
| -rw-r--r-- | Modules/_collectionsmodule.c | 3 | ||||
| -rw-r--r-- | Objects/dict-common.h | 22 | ||||
| -rw-r--r-- | Objects/dictobject.c | 337 | ||||
| -rw-r--r-- | Objects/object.c | 15 | ||||
| -rw-r--r-- | Objects/odictobject.c | 2394 |
12 files changed, 2860 insertions, 195 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 */ diff --git a/Lib/collections/__init__.py b/Lib/collections/__init__.py index fc60e13..6794de1 100644 --- a/Lib/collections/__init__.py +++ b/Lib/collections/__init__.py @@ -7,7 +7,6 @@ from _collections_abc import * import _collections_abc __all__ += _collections_abc.__all__ -from _collections import deque, defaultdict from operator import itemgetter as _itemgetter, eq as _eq from keyword import iskeyword as _iskeyword import sys as _sys @@ -16,7 +15,18 @@ from _weakref import proxy as _proxy from itertools import repeat as _repeat, chain as _chain, starmap as _starmap from reprlib import recursive_repr as _recursive_repr -MutableSequence.register(deque) +try: + from _collections import deque +except ImportError: + pass +else: + MutableSequence.register(deque) + +try: + from _collections import defaultdict +except ImportError: + pass + ################################################################################ ### OrderedDict @@ -264,6 +274,13 @@ class OrderedDict(dict): return dict.__eq__(self, other) +try: + from _collections import OrderedDict +except ImportError: + # Leave the pure Python version in place. + pass + + ################################################################################ ### namedtuple ################################################################################ diff --git a/Lib/test/test_collections.py b/Lib/test/test_collections.py index dc79b69..3bb326a 100644 --- a/Lib/test/test_collections.py +++ b/Lib/test/test_collections.py @@ -1,7 +1,8 @@ """Unit tests for collections.py.""" import unittest, doctest, operator -from test.support import TESTFN, forget, unlink +from test.support import TESTFN, forget, unlink, import_fresh_module +import contextlib import inspect from test import support from collections import namedtuple, Counter, OrderedDict, _count_elements @@ -1609,9 +1610,24 @@ class TestCounter(unittest.TestCase): ### OrderedDict ################################################################################ -class TestOrderedDict(unittest.TestCase): +py_coll = import_fresh_module('collections', blocked=['_collections']) +c_coll = import_fresh_module('collections', fresh=['_collections']) + + +@contextlib.contextmanager +def replaced_module(name, replacement): + original_module = sys.modules[name] + sys.modules[name] = replacement + try: + yield + finally: + sys.modules[name] = original_module + + +class OrderedDictTests: def test_init(self): + OrderedDict = self.module.OrderedDict with self.assertRaises(TypeError): OrderedDict([('a', 1), ('b', 2)], None) # too many args pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)] @@ -1635,6 +1651,7 @@ class TestOrderedDict(unittest.TestCase): [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)]) def test_update(self): + OrderedDict = self.module.OrderedDict with self.assertRaises(TypeError): OrderedDict().update([('a', 1), ('b', 2)], None) # too many args pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)] @@ -1675,11 +1692,17 @@ class TestOrderedDict(unittest.TestCase): self.assertRaises(TypeError, OrderedDict().update, (), ()) self.assertRaises(TypeError, OrderedDict.update) + self.assertRaises(TypeError, OrderedDict().update, 42) + self.assertRaises(TypeError, OrderedDict().update, (), ()) + self.assertRaises(TypeError, OrderedDict.update) + def test_abc(self): + OrderedDict = self.module.OrderedDict self.assertIsInstance(OrderedDict(), MutableMapping) self.assertTrue(issubclass(OrderedDict, MutableMapping)) def test_clear(self): + OrderedDict = self.module.OrderedDict pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] shuffle(pairs) od = OrderedDict(pairs) @@ -1688,6 +1711,7 @@ class TestOrderedDict(unittest.TestCase): self.assertEqual(len(od), 0) def test_delitem(self): + OrderedDict = self.module.OrderedDict pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] od = OrderedDict(pairs) del od['a'] @@ -1697,6 +1721,7 @@ class TestOrderedDict(unittest.TestCase): self.assertEqual(list(od.items()), pairs[:2] + pairs[3:]) def test_setitem(self): + OrderedDict = self.module.OrderedDict od = OrderedDict([('d', 1), ('b', 2), ('c', 3), ('a', 4), ('e', 5)]) od['c'] = 10 # existing element od['f'] = 20 # new element @@ -1704,6 +1729,7 @@ class TestOrderedDict(unittest.TestCase): [('d', 1), ('b', 2), ('c', 10), ('a', 4), ('e', 5), ('f', 20)]) def test_iterators(self): + OrderedDict = self.module.OrderedDict pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] shuffle(pairs) od = OrderedDict(pairs) @@ -1720,6 +1746,11 @@ class TestOrderedDict(unittest.TestCase): self.assertEqual(list(reversed(od.items())), list(reversed(pairs))) def test_detect_deletion_during_iteration(self): + # XXX This test should also work under cOrderedDict. + if self.module is c_coll: + raise unittest.SkipTest("only valid for pure Python OrderedDict") + + OrderedDict = self.module.OrderedDict od = OrderedDict.fromkeys('abc') it = iter(od) key = next(it) @@ -1729,7 +1760,21 @@ class TestOrderedDict(unittest.TestCase): # The only guarantee that the next() will not succeed next(it) + def test_sorted_iterators(self): + OrderedDict = self.module.OrderedDict + with self.assertRaises(TypeError): + OrderedDict([('a', 1), ('b', 2)], None) + pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)] + od = OrderedDict(pairs) + self.assertEqual(sorted(od), [t[0] for t in pairs]) + self.assertEqual(sorted(od.keys()), [t[0] for t in pairs]) + self.assertEqual(sorted(od.values()), [t[1] for t in pairs]) + self.assertEqual(sorted(od.items()), pairs) + self.assertEqual(sorted(reversed(od)), + sorted([t[0] for t in reversed(pairs)])) + def test_popitem(self): + OrderedDict = self.module.OrderedDict pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] shuffle(pairs) od = OrderedDict(pairs) @@ -1739,7 +1784,18 @@ class TestOrderedDict(unittest.TestCase): od.popitem() self.assertEqual(len(od), 0) + def test_popitem_last(self): + OrderedDict = self.module.OrderedDict + pairs = [(i, i) for i in range(30)] + + obj = OrderedDict(pairs) + for i in range(8): + obj.popitem(True) + obj.popitem(True) + self.assertEqual(len(obj), 21) + def test_pop(self): + OrderedDict = self.module.OrderedDict pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] shuffle(pairs) od = OrderedDict(pairs) @@ -1764,6 +1820,7 @@ class TestOrderedDict(unittest.TestCase): m.pop('a') def test_equality(self): + OrderedDict = self.module.OrderedDict pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] shuffle(pairs) od1 = OrderedDict(pairs) @@ -1779,6 +1836,7 @@ class TestOrderedDict(unittest.TestCase): self.assertNotEqual(od1, OrderedDict(pairs[:-1])) def test_copying(self): + OrderedDict = self.module.OrderedDict # Check that ordered dicts are copyable, deepcopyable, picklable, # and have a repr/eval round-trip pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] @@ -1787,12 +1845,17 @@ class TestOrderedDict(unittest.TestCase): msg = "\ncopy: %s\nod: %s" % (dup, od) self.assertIsNot(dup, od, msg) self.assertEqual(dup, od) + self.assertEqual(list(dup.items()), list(od.items())) + self.assertEqual(len(dup), len(od)) + self.assertEqual(type(dup), type(od)) check(od.copy()) check(copy.copy(od)) check(copy.deepcopy(od)) - for proto in range(pickle.HIGHEST_PROTOCOL + 1): - with self.subTest(proto=proto): - check(pickle.loads(pickle.dumps(od, proto))) + # pickle directly pulls the module, so we have to fake it + with replaced_module('collections', self.module): + for proto in range(pickle.HIGHEST_PROTOCOL + 1): + with self.subTest(proto=proto): + check(pickle.loads(pickle.dumps(od, proto))) check(eval(repr(od))) update_test = OrderedDict() update_test.update(od) @@ -1800,6 +1863,7 @@ class TestOrderedDict(unittest.TestCase): check(OrderedDict(od)) def test_yaml_linkage(self): + OrderedDict = self.module.OrderedDict # Verify that __reduce__ is setup in a way that supports PyYAML's dump() feature. # In yaml, lists are native but tuples are not. pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] @@ -1809,6 +1873,7 @@ class TestOrderedDict(unittest.TestCase): self.assertTrue(all(type(pair)==list for pair in od.__reduce__()[1])) def test_reduce_not_too_fat(self): + OrderedDict = self.module.OrderedDict # do not save instance dictionary if not needed pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] od = OrderedDict(pairs) @@ -1817,15 +1882,20 @@ class TestOrderedDict(unittest.TestCase): self.assertIsNotNone(od.__reduce__()[2]) def test_pickle_recursive(self): + OrderedDict = self.module.OrderedDict od = OrderedDict() od[1] = od - for proto in range(-1, pickle.HIGHEST_PROTOCOL + 1): - dup = pickle.loads(pickle.dumps(od, proto)) - self.assertIsNot(dup, od) - self.assertEqual(list(dup.keys()), [1]) - self.assertIs(dup[1], dup) + + # pickle directly pulls the module, so we have to fake it + with replaced_module('collections', self.module): + for proto in range(-1, pickle.HIGHEST_PROTOCOL + 1): + dup = pickle.loads(pickle.dumps(od, proto)) + self.assertIsNot(dup, od) + self.assertEqual(list(dup.keys()), [1]) + self.assertIs(dup[1], dup) def test_repr(self): + OrderedDict = self.module.OrderedDict od = OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]) self.assertEqual(repr(od), "OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)])") @@ -1833,6 +1903,7 @@ class TestOrderedDict(unittest.TestCase): self.assertEqual(repr(OrderedDict()), "OrderedDict()") def test_repr_recursive(self): + OrderedDict = self.module.OrderedDict # See issue #9826 od = OrderedDict.fromkeys('abc') od['x'] = od @@ -1840,6 +1911,7 @@ class TestOrderedDict(unittest.TestCase): "OrderedDict([('a', None), ('b', None), ('c', None), ('x', ...)])") def test_setdefault(self): + OrderedDict = self.module.OrderedDict pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] shuffle(pairs) od = OrderedDict(pairs) @@ -1858,16 +1930,19 @@ class TestOrderedDict(unittest.TestCase): self.assertEqual(Missing().setdefault(5, 9), 9) def test_reinsert(self): + OrderedDict = self.module.OrderedDict # Given insert a, insert b, delete a, re-insert a, # verify that a is now later than b. od = OrderedDict() od['a'] = 1 od['b'] = 2 del od['a'] + self.assertEqual(list(od.items()), [('b', 2)]) od['a'] = 1 self.assertEqual(list(od.items()), [('b', 2), ('a', 1)]) def test_move_to_end(self): + OrderedDict = self.module.OrderedDict od = OrderedDict.fromkeys('abcde') self.assertEqual(list(od), list('abcde')) od.move_to_end('c') @@ -1880,14 +1955,19 @@ class TestOrderedDict(unittest.TestCase): self.assertEqual(list(od), list('cabde')) with self.assertRaises(KeyError): od.move_to_end('x') + with self.assertRaises(KeyError): + od.move_to_end('x', 0) def test_sizeof(self): + OrderedDict = self.module.OrderedDict # Wimpy test: Just verify the reported size is larger than a regular dict d = dict(a=1) od = OrderedDict(**d) self.assertGreater(sys.getsizeof(od), sys.getsizeof(d)) + OrderedDict = self.module.OrderedDict def test_override_update(self): + OrderedDict = self.module.OrderedDict # Verify that subclasses can override update() without breaking __init__() class MyOD(OrderedDict): def update(self, *args, **kwds): @@ -1895,18 +1975,101 @@ class TestOrderedDict(unittest.TestCase): items = [('a', 1), ('c', 3), ('b', 2)] self.assertEqual(list(MyOD(items).items()), items) -class GeneralMappingTests(mapping_tests.BasicTestMappingProtocol): - type2test = OrderedDict + +class PurePythonOrderedDictTests(OrderedDictTests, unittest.TestCase): + + module = py_coll + + +@unittest.skipUnless(c_coll, 'requires the C version of the collections module') +class CPythonOrderedDictTests(OrderedDictTests, unittest.TestCase): + + module = c_coll + + def test_delitem_hash_collision(self): + OrderedDict = self.module.OrderedDict + + class Key: + def __init__(self, hash): + self._hash = hash + self.value = str(id(self)) + def __hash__(self): + return self._hash + def __eq__(self, other): + try: + return self.value == other.value + except AttributeError: + return False + def __repr__(self): + return self.value + + def blocking_hash(hash): + # See the collision-handling in lookdict (in Objects/dictobject.c). + MINSIZE = 8 + i = (hash & MINSIZE-1) + return (i << 2) + i + hash + 1 + + COLLIDING = 1 + + key = Key(COLLIDING) + colliding = Key(COLLIDING) + blocking = Key(blocking_hash(COLLIDING)) + + od = OrderedDict() + od[key] = ... + od[blocking] = ... + od[colliding] = ... + od['after'] = ... + + del od[blocking] + del od[colliding] + self.assertEqual(list(od.items()), [(key, ...), ('after', ...)]) + + +class PurePythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol): + + @classmethod + def setUpClass(cls): + cls.type2test = py_coll.OrderedDict def test_popitem(self): d = self._empty_mapping() self.assertRaises(KeyError, d.popitem) -class MyOrderedDict(OrderedDict): - pass -class SubclassMappingTests(mapping_tests.BasicTestMappingProtocol): - type2test = MyOrderedDict +@unittest.skipUnless(c_coll, 'requires the C version of the collections module') +class CPythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol): + + @classmethod + def setUpClass(cls): + cls.type2test = c_coll.OrderedDict + + def test_popitem(self): + d = self._empty_mapping() + self.assertRaises(KeyError, d.popitem) + + +class PurePythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol): + + @classmethod + def setUpClass(cls): + class MyOrderedDict(py_coll.OrderedDict): + pass + cls.type2test = MyOrderedDict + + def test_popitem(self): + d = self._empty_mapping() + self.assertRaises(KeyError, d.popitem) + + +@unittest.skipUnless(c_coll, 'requires the C version of the collections module') +class CPythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol): + + @classmethod + def setUpClass(cls): + class MyOrderedDict(c_coll.OrderedDict): + pass + cls.type2test = MyOrderedDict def test_popitem(self): d = self._empty_mapping() @@ -1923,8 +2086,11 @@ def test_main(verbose=None): NamedTupleDocs = doctest.DocTestSuite(module=collections) test_classes = [TestNamedTuple, NamedTupleDocs, TestOneTrickPonyABCs, TestCollectionABCs, TestCounter, TestChainMap, - TestOrderedDict, GeneralMappingTests, SubclassMappingTests, - TestUserObjects] + PurePythonOrderedDictTests, CPythonOrderedDictTests, + PurePythonGeneralMappingTests, CPythonGeneralMappingTests, + PurePythonSubclassMappingTests, CPythonSubclassMappingTests, + TestUserObjects, + ] support.run_unittest(*test_classes) support.run_doctest(collections, verbose) diff --git a/Makefile.pre.in b/Makefile.pre.in index 5db048a..ce2c0aa2 100644 --- a/Makefile.pre.in +++ b/Makefile.pre.in @@ -437,6 +437,7 @@ OBJECT_OBJS= \ Objects/listobject.o \ Objects/longobject.o \ Objects/dictobject.o \ + Objects/odictobject.o \ Objects/memoryobject.o \ Objects/methodobject.o \ Objects/moduleobject.o \ @@ -23,6 +23,8 @@ Library - Issue #24326: Fixed audioop.ratecv() with non-default weightB argument. Original patch by David Moore. +- Issue #16991: Add a C implementation of OrderedDict. + What's New in Python 3.5.0 beta 1? ================================== diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c index 2b70b2b..c1fd8b9 100644 --- a/Modules/_collectionsmodule.c +++ b/Modules/_collectionsmodule.c @@ -2263,6 +2263,9 @@ PyInit__collections(void) Py_INCREF(&defdict_type); PyModule_AddObject(m, "defaultdict", (PyObject *)&defdict_type); + Py_INCREF(&PyODict_Type); + PyModule_AddObject(m, "OrderedDict", (PyObject *)&PyODict_Type); + if (PyType_Ready(&dequeiter_type) < 0) return NULL; Py_INCREF(&dequeiter_type); diff --git a/Objects/dict-common.h b/Objects/dict-common.h new file mode 100644 index 0000000..2912eb9 --- /dev/null +++ b/Objects/dict-common.h @@ -0,0 +1,22 @@ +#ifndef Py_DICT_COMMON_H +#define Py_DICT_COMMON_H + +typedef struct { + /* Cached hash code of me_key. */ + Py_hash_t me_hash; + PyObject *me_key; + 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); + +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]; +}; + +#endif diff --git a/Objects/dictobject.c b/Objects/dictobject.c index 0548224..3791d5b 100644 --- a/Objects/dictobject.c +++ b/Objects/dictobject.c @@ -67,6 +67,7 @@ to the combined-table form. #define PyDict_MINSIZE_COMBINED 8 #include "Python.h" +#include "dict-common.h" #include "stringlib/eq.h" /*[clinic input] @@ -74,24 +75,6 @@ class dict "PyDictObject *" "&PyDict_Type" [clinic start generated code]*/ /*[clinic end generated code: output=da39a3ee5e6b4b0d input=f157a5a0ce9589d6]*/ -typedef struct { - /* Cached hash code of me_key. */ - Py_hash_t me_hash; - PyObject *me_key; - 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); - -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]; -}; - /* To ensure the lookup algorithm terminates, there must be at least one Unused @@ -1425,6 +1408,141 @@ _PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, return 1; } +/* Internal version of dict.pop(). */ +PyObject * +_PyDict_Pop(PyDictObject *mp, PyObject *key, PyObject *deflt) +{ + Py_hash_t hash; + PyObject *old_value, *old_key; + PyDictKeyEntry *ep; + PyObject **value_addr; + + if (mp->ma_used == 0) { + if (deflt) { + Py_INCREF(deflt); + return deflt; + } + _PyErr_SetKeyError(key); + return NULL; + } + if (!PyUnicode_CheckExact(key) || + (hash = ((PyASCIIObject *) key)->hash) == -1) { + hash = PyObject_Hash(key); + if (hash == -1) + return NULL; + } + ep = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr); + if (ep == NULL) + return NULL; + old_value = *value_addr; + if (old_value == NULL) { + if (deflt) { + Py_INCREF(deflt); + return deflt; + } + _PyErr_SetKeyError(key); + return NULL; + } + *value_addr = NULL; + mp->ma_used--; + if (!_PyDict_HasSplitTable(mp)) { + ENSURE_ALLOWS_DELETIONS(mp); + old_key = ep->me_key; + Py_INCREF(dummy); + ep->me_key = dummy; + Py_DECREF(old_key); + } + return old_value; +} + +/* Internal version of dict.from_keys(). It is subclass-friendly. */ +PyObject * +_PyDict_FromKeys(PyObject *cls, PyObject *iterable, PyObject *value) +{ + PyObject *it; /* iter(iterable) */ + PyObject *key; + PyObject *d; + int status; + + d = PyObject_CallObject(cls, NULL); + if (d == NULL) + return NULL; + + if (PyDict_CheckExact(d) && ((PyDictObject *)d)->ma_used == 0) { + if (PyDict_CheckExact(iterable)) { + PyDictObject *mp = (PyDictObject *)d; + PyObject *oldvalue; + Py_ssize_t pos = 0; + PyObject *key; + Py_hash_t hash; + + if (dictresize(mp, Py_SIZE(iterable))) { + Py_DECREF(d); + return NULL; + } + + while (_PyDict_Next(iterable, &pos, &key, &oldvalue, &hash)) { + if (insertdict(mp, key, hash, value)) { + Py_DECREF(d); + return NULL; + } + } + return d; + } + if (PyAnySet_CheckExact(iterable)) { + PyDictObject *mp = (PyDictObject *)d; + Py_ssize_t pos = 0; + PyObject *key; + Py_hash_t hash; + + if (dictresize(mp, PySet_GET_SIZE(iterable))) { + Py_DECREF(d); + return NULL; + } + + while (_PySet_NextEntry(iterable, &pos, &key, &hash)) { + if (insertdict(mp, key, hash, value)) { + Py_DECREF(d); + return NULL; + } + } + return d; + } + } + + it = PyObject_GetIter(iterable); + if (it == NULL){ + Py_DECREF(d); + return NULL; + } + + if (PyDict_CheckExact(d)) { + while ((key = PyIter_Next(it)) != NULL) { + status = PyDict_SetItem(d, key, value); + Py_DECREF(key); + if (status < 0) + goto Fail; + } + } else { + while ((key = PyIter_Next(it)) != NULL) { + status = PyObject_SetItem(d, key, value); + Py_DECREF(key); + if (status < 0) + goto Fail; + } + } + + if (PyErr_Occurred()) + goto Fail; + Py_DECREF(it); + return d; + +Fail: + Py_DECREF(it); + Py_DECREF(d); + return NULL; +} + /* Methods */ static void @@ -1763,88 +1881,7 @@ static PyObject * dict_fromkeys_impl(PyTypeObject *type, PyObject *iterable, PyObject *value) /*[clinic end generated code: output=8fb98e4b10384999 input=b85a667f9bf4669d]*/ { - PyObject *it; /* iter(seq) */ - PyObject *key; - PyObject *d; - int status; - - d = PyObject_CallObject((PyObject *)type, NULL); - if (d == NULL) - return NULL; - - if (PyDict_CheckExact(d) && ((PyDictObject *)d)->ma_used == 0) { - if (PyDict_CheckExact(iterable)) { - PyDictObject *mp = (PyDictObject *)d; - PyObject *oldvalue; - Py_ssize_t pos = 0; - PyObject *key; - Py_hash_t hash; - - if (dictresize(mp, Py_SIZE(iterable))) { - Py_DECREF(d); - return NULL; - } - - while (_PyDict_Next(iterable, &pos, &key, &oldvalue, &hash)) { - if (insertdict(mp, key, hash, value)) { - Py_DECREF(d); - return NULL; - } - } - return d; - } - if (PyAnySet_CheckExact(iterable)) { - PyDictObject *mp = (PyDictObject *)d; - Py_ssize_t pos = 0; - PyObject *key; - Py_hash_t hash; - - if (dictresize(mp, PySet_GET_SIZE(iterable))) { - Py_DECREF(d); - return NULL; - } - - while (_PySet_NextEntry(iterable, &pos, &key, &hash)) { - if (insertdict(mp, key, hash, value)) { - Py_DECREF(d); - return NULL; - } - } - return d; - } - } - - it = PyObject_GetIter(iterable); - if (it == NULL){ - Py_DECREF(d); - return NULL; - } - - if (PyDict_CheckExact(d)) { - while ((key = PyIter_Next(it)) != NULL) { - status = PyDict_SetItem(d, key, value); - Py_DECREF(key); - if (status < 0) - goto Fail; - } - } else { - while ((key = PyIter_Next(it)) != NULL) { - status = PyObject_SetItem(d, key, value); - Py_DECREF(key); - if (status < 0) - goto Fail; - } - } - - if (PyErr_Occurred()) - goto Fail; - Py_DECREF(it); - return d; - -Fail: - Py_DECREF(it); - Py_DECREF(d); - return NULL; + return _PyDict_FromKeys((PyObject *)type, iterable, value); } static int @@ -2356,50 +2393,12 @@ dict_clear(PyDictObject *mp) static PyObject * dict_pop(PyDictObject *mp, PyObject *args) { - Py_hash_t hash; - PyObject *old_value, *old_key; PyObject *key, *deflt = NULL; - PyDictKeyEntry *ep; - PyObject **value_addr; if(!PyArg_UnpackTuple(args, "pop", 1, 2, &key, &deflt)) return NULL; - if (mp->ma_used == 0) { - if (deflt) { - Py_INCREF(deflt); - return deflt; - } - _PyErr_SetKeyError(key); - return NULL; - } - if (!PyUnicode_CheckExact(key) || - (hash = ((PyASCIIObject *) key)->hash) == -1) { - hash = PyObject_Hash(key); - if (hash == -1) - return NULL; - } - ep = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr); - if (ep == NULL) - return NULL; - old_value = *value_addr; - if (old_value == NULL) { - if (deflt) { - Py_INCREF(deflt); - return deflt; - } - _PyErr_SetKeyError(key); - return NULL; - } - *value_addr = NULL; - mp->ma_used--; - if (!_PyDict_HasSplitTable(mp)) { - ENSURE_ALLOWS_DELETIONS(mp); - old_key = ep->me_key; - Py_INCREF(dummy); - ep->me_key = dummy; - Py_DECREF(old_key); - } - return old_value; + + return _PyDict_Pop(mp, key, deflt); } static PyObject * @@ -2506,8 +2505,8 @@ dict_tp_clear(PyObject *op) static PyObject *dictiter_new(PyDictObject *, PyTypeObject *); -static PyObject * -dict_sizeof(PyDictObject *mp) +PyObject * +_PyDict_SizeOf(PyDictObject *mp) { Py_ssize_t size, res; @@ -2575,7 +2574,7 @@ static PyMethodDef mapp_methods[] = { DICT___CONTAINS___METHODDEF {"__getitem__", (PyCFunction)dict_subscript, METH_O | METH_COEXIST, getitem__doc__}, - {"__sizeof__", (PyCFunction)dict_sizeof, METH_NOARGS, + {"__sizeof__", (PyCFunction)_PyDict_SizeOf, METH_NOARGS, sizeof__doc__}, {"get", (PyCFunction)dict_get, METH_VARARGS, get__doc__}, @@ -3104,8 +3103,8 @@ static PyObject *dictiter_iternextitem(dictiterobject *di) value = *value_ptr; Py_INCREF(key); Py_INCREF(value); - PyTuple_SET_ITEM(result, 0, key); - PyTuple_SET_ITEM(result, 1, value); + PyTuple_SET_ITEM(result, 0, key); /* steals reference */ + PyTuple_SET_ITEM(result, 1, value); /* steals reference */ return result; fail: @@ -3200,28 +3199,22 @@ dictiter_reduce(dictiterobject *di) /* The instance lay-out is the same for all three; but the type differs. */ -typedef struct { - PyObject_HEAD - PyDictObject *dv_dict; -} dictviewobject; - - static void -dictview_dealloc(dictviewobject *dv) +dictview_dealloc(_PyDictViewObject *dv) { Py_XDECREF(dv->dv_dict); PyObject_GC_Del(dv); } static int -dictview_traverse(dictviewobject *dv, visitproc visit, void *arg) +dictview_traverse(_PyDictViewObject *dv, visitproc visit, void *arg) { Py_VISIT(dv->dv_dict); return 0; } static Py_ssize_t -dictview_len(dictviewobject *dv) +dictview_len(_PyDictViewObject *dv) { Py_ssize_t len = 0; if (dv->dv_dict != NULL) @@ -3229,10 +3222,10 @@ dictview_len(dictviewobject *dv) return len; } -static PyObject * -dictview_new(PyObject *dict, PyTypeObject *type) +PyObject * +_PyDictView_New(PyObject *dict, PyTypeObject *type) { - dictviewobject *dv; + _PyDictViewObject *dv; if (dict == NULL) { PyErr_BadInternalCall(); return NULL; @@ -3244,7 +3237,7 @@ dictview_new(PyObject *dict, PyTypeObject *type) type->tp_name, dict->ob_type->tp_name); return NULL; } - dv = PyObject_GC_New(dictviewobject, type); + dv = PyObject_GC_New(_PyDictViewObject, type); if (dv == NULL) return NULL; Py_INCREF(dict); @@ -3348,7 +3341,7 @@ dictview_richcompare(PyObject *self, PyObject *other, int op) } static PyObject * -dictview_repr(dictviewobject *dv) +dictview_repr(_PyDictViewObject *dv) { PyObject *seq; PyObject *result; @@ -3365,7 +3358,7 @@ dictview_repr(dictviewobject *dv) /*** dict_keys ***/ static PyObject * -dictkeys_iter(dictviewobject *dv) +dictkeys_iter(_PyDictViewObject *dv) { if (dv->dv_dict == NULL) { Py_RETURN_NONE; @@ -3374,7 +3367,7 @@ dictkeys_iter(dictviewobject *dv) } static int -dictkeys_contains(dictviewobject *dv, PyObject *obj) +dictkeys_contains(_PyDictViewObject *dv, PyObject *obj) { if (dv->dv_dict == NULL) return 0; @@ -3499,7 +3492,7 @@ dictviews_isdisjoint(PyObject *self, PyObject *other) PyObject *item = NULL; if (self == other) { - if (dictview_len((dictviewobject *)self) == 0) + if (dictview_len((_PyDictViewObject *)self) == 0) Py_RETURN_TRUE; else Py_RETURN_FALSE; @@ -3508,7 +3501,7 @@ dictviews_isdisjoint(PyObject *self, PyObject *other) /* Iterate over the shorter object (only if other is a set, * because PySequence_Contains may be expensive otherwise): */ if (PyAnySet_Check(other) || PyDictViewSet_Check(other)) { - Py_ssize_t len_self = dictview_len((dictviewobject *)self); + Py_ssize_t len_self = dictview_len((_PyDictViewObject *)self); Py_ssize_t len_other = PyObject_Size(other); if (len_other == -1) return NULL; @@ -3555,7 +3548,7 @@ static PyMethodDef dictkeys_methods[] = { PyTypeObject PyDictKeys_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) "dict_keys", /* tp_name */ - sizeof(dictviewobject), /* tp_basicsize */ + sizeof(_PyDictViewObject), /* tp_basicsize */ 0, /* tp_itemsize */ /* methods */ (destructor)dictview_dealloc, /* tp_dealloc */ @@ -3588,13 +3581,13 @@ PyTypeObject PyDictKeys_Type = { static PyObject * dictkeys_new(PyObject *dict) { - return dictview_new(dict, &PyDictKeys_Type); + return _PyDictView_New(dict, &PyDictKeys_Type); } /*** dict_items ***/ static PyObject * -dictitems_iter(dictviewobject *dv) +dictitems_iter(_PyDictViewObject *dv) { if (dv->dv_dict == NULL) { Py_RETURN_NONE; @@ -3603,7 +3596,7 @@ dictitems_iter(dictviewobject *dv) } static int -dictitems_contains(dictviewobject *dv, PyObject *obj) +dictitems_contains(_PyDictViewObject *dv, PyObject *obj) { PyObject *key, *value, *found; if (dv->dv_dict == NULL) @@ -3641,7 +3634,7 @@ static PyMethodDef dictitems_methods[] = { PyTypeObject PyDictItems_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) "dict_items", /* tp_name */ - sizeof(dictviewobject), /* tp_basicsize */ + sizeof(_PyDictViewObject), /* tp_basicsize */ 0, /* tp_itemsize */ /* methods */ (destructor)dictview_dealloc, /* tp_dealloc */ @@ -3674,13 +3667,13 @@ PyTypeObject PyDictItems_Type = { static PyObject * dictitems_new(PyObject *dict) { - return dictview_new(dict, &PyDictItems_Type); + return _PyDictView_New(dict, &PyDictItems_Type); } /*** dict_values ***/ static PyObject * -dictvalues_iter(dictviewobject *dv) +dictvalues_iter(_PyDictViewObject *dv) { if (dv->dv_dict == NULL) { Py_RETURN_NONE; @@ -3706,7 +3699,7 @@ static PyMethodDef dictvalues_methods[] = { PyTypeObject PyDictValues_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) "dict_values", /* tp_name */ - sizeof(dictviewobject), /* tp_basicsize */ + sizeof(_PyDictViewObject), /* tp_basicsize */ 0, /* tp_itemsize */ /* methods */ (destructor)dictview_dealloc, /* tp_dealloc */ @@ -3739,7 +3732,7 @@ PyTypeObject PyDictValues_Type = { static PyObject * dictvalues_new(PyObject *dict) { - return dictview_new(dict, &PyDictValues_Type); + return _PyDictView_New(dict, &PyDictValues_Type); } /* Returns NULL if cannot allocate a new PyDictKeysObject, diff --git a/Objects/object.c b/Objects/object.c index c1d7a05..be12be5 100644 --- a/Objects/object.c +++ b/Objects/object.c @@ -1607,6 +1607,21 @@ _Py_ReadyTypes(void) if (PyType_Ready(&PyDict_Type) < 0) Py_FatalError("Can't initialize dict type"); + if (PyType_Ready(&PyODict_Type) < 0) + Py_FatalError("Can't initialize OrderedDict type"); + + if (PyType_Ready(&PyODictKeys_Type) < 0) + Py_FatalError("Can't initialize odict_keys type"); + + if (PyType_Ready(&PyODictItems_Type) < 0) + Py_FatalError("Can't initialize odict_items type"); + + if (PyType_Ready(&PyODictValues_Type) < 0) + Py_FatalError("Can't initialize odict_values type"); + + if (PyType_Ready(&PyODictIter_Type) < 0) + Py_FatalError("Can't initialize odict_keyiterator type"); + if (PyType_Ready(&PySet_Type) < 0) Py_FatalError("Can't initialize set type"); diff --git a/Objects/odictobject.c b/Objects/odictobject.c new file mode 100644 index 0000000..3648913 --- /dev/null +++ b/Objects/odictobject.c @@ -0,0 +1,2394 @@ +/* Ordered Dictionary object implementation. + +This implementation is necessarily explicitly equivalent to the pure Python +OrderedDict class in Lib/collections/__init__.py. The strategy there +involves using a doubly-linked-list to capture the order. We keep to that +strategy, using a lower-level linked-list. + +About the Linked-List +===================== + +For the linked list we use a basic doubly-linked-list. Using a circularly- +linked-list does have some benefits, but they don't apply so much here +since OrderedDict is focused on the ends of the list (for the most part). +Furthermore, there are some features of generic linked-lists that we simply +don't need for OrderedDict. Thus a simple custom implementation meets our +needs. Alternatives to our simple approach include the QCIRCLE_* +macros from BSD's queue.h, and the linux's list.h. + +Getting O(1) Node Lookup +------------------------ + +One invariant of Python's OrderedDict is that it preserves time complexity +of dict's methods, particularly the O(1) operations. Simply adding a +linked-list on top of dict is not sufficient here; operations for nodes in +the middle of the linked-list implicitly require finding the node first. +With a simple linked-list like we're using, that is an O(n) operation. +Consequently, methods like __delitem__() would change from O(1) to O(n), +which is unacceptable. + +In order to preserve O(1) performance for node removal (finding nodes), we +must do better than just looping through the linked-list. Here are options +we've considered: + +1. use a second dict to map keys to nodes (a la the pure Python version). +2. keep a simple hash table mirroring the order of dict's, mapping each key + to the corresponding node in the linked-list. +3. use a version of shared keys (split dict) that allows non-unicode keys. +4. have the value stored for each key be a (value, node) pair, and adjust + __getitem__(), get(), etc. accordingly. + +The approach with the least performance impact (time and space) is #2, +mirroring the key order of dict's dk_enties with an array of node pointers. +While lookdict() and friends (dk_lookup) don't give us the index into the +array, we make use of pointer arithmetic to get that index. An alternative +would be to refactor lookdict() to provide the index, explicitly exposing +the implementation detail. We could even just use a custom lookup function +for OrderedDict that facilitates our need. However, both approaches are +significantly more complicated than just using pointer arithmetic. + +The catch with mirroring the hash table ordering is that we have to keep +the ordering in sync through any dict resizes. However, that order only +matters during node lookup. We can simply defer any potential resizing +until we need to do a lookup. + +Linked-List Nodes +----------------- + +The current implementation stores a pointer to the associated key only. +One alternative would be to store a pointer to the PyDictKeyEntry instead. +This would save one pointer de-reference per item, which is nice during +calls to values() and items(). However, it adds unnecessary overhead +otherwise, so we stick with just the key. + +Linked-List API +--------------- + +As noted, the linked-list implemented here does not have all the bells and +whistles. However, we recognize that the implementation may need to +change to accommodate performance improvements or extra functionality. To +that end, We use a simple API to interact with the linked-list. Here's a +summary of the methods/macros: + +Node info: + +* _odictnode_KEY(node) +* _odictnode_VALUE(od, node) +* _odictnode_PREV(node) +* _odictnode_NEXT(node) + +Linked-List info: + +* _odict_FIRST(od) +* _odict_LAST(od) +* _odict_EMPTY(od) +* _odict_FOREACH(od, node) - used in place of `for (node=...)` + +For adding nodes: + +* _odict_add_head(od, node) +* _odict_add_tail(od, node) +* _odict_add_new_node(od, key) + +For removing nodes: + +* _odict_pop_node(od, node, key) +* _odict_clear_node(od, node) +* _odict_clear_nodes(od, clear_each) + +Others: + +* _odict_initialize(od) +* _odict_find_node(od, key) +* _odict_keys_equal(od1, od2) + +Used, but specific to the linked-list implementation: + +* _odict_free_fast_nodes(od) + +And here's a look at how the linked-list relates to the OrderedDict API: + +============ === === ==== ==== ==== === ==== ===== ==== ==== === ==== === === +method key val prev next mem 1st last empty iter find add rmv clr keq +============ === === ==== ==== ==== === ==== ===== ==== ==== === ==== === === +__del__ ~ X +__delitem__ free ~ node +__eq__ ~ X +__iter__ X X +__new__ X X +__reduce__ X ~ X +__repr__ X X X +__reversed__ X X +__setitem__ key +__sizeof__ size X +clear ~ ~ X +copy X X X +items X X X +keys X X +move_to_end X X X ~ h/t key +pop free key +popitem X X free X X node +setdefault ~ ? ~ +values X X +============ === === ==== ==== ==== === ==== ===== ==== ==== === ==== === === + +__delitem__ is the only method that directly relies on finding an arbitrary +node in the linked-list. Everything else is iteration or relates to the +ends of the linked-list. + +Situation that Endangers Consistency +------------------------------------ +Using a raw linked-list for OrderedDict exposes a key situation that can +cause problems. If a node is stored in a variable, there is a chance that +the node may have been deallocated before the variable gets used, thus +potentially leading to a segmentation fault. A key place where this shows +up is during iteration through the linked list (via _odict_FOREACH or +otherwise). + +A number of solutions are available to resolve this situation: + +* defer looking up the node until as late as possible and certainly after + any code that could possibly result in a deletion; +* if the node is needed both before and after a point where the node might + be removed, do a check before using the node at the "after" location to + see if the node is still valid; +* like the last one, but simply pull the node again to ensure it's right; +* keep the key in the variable instead of the node and then look up the + node using the key at the point where the node is needed (this is what + we do for the iterators). + +Another related problem, preserving consistent ordering during iteration, +is described below. That one is not exclusive to using linked-lists. + + +Challenges from Subclassing dict +================================ + +OrderedDict subclasses dict, which is an unusual relationship between two +builtin types (other than the base object type). Doing so results in +some complication and deserves further explanation. There are two things +to consider here. First, in what circumstances or with what adjustments +can OrderedDict be used as a drop-in replacement for dict (at the C level)? +Second, how can the OrderedDict implementation leverage the dict +implementation effectively without introducing unnecessary coupling or +inefficiencies? + +This second point is reflected here and in the implementation, so the +further focus is on the first point. It is worth noting that for +overridden methods, the dict implementation is deferred to as much as +possible. Furthermore, coupling is limited to as little as is reasonable. + +Concrete API Compatibility +-------------------------- + +Use of the concrete C-API for dict (PyDict_*) with OrderedDict is +problematic. (See http://bugs.python.org/issue10977.) The concrete API +has a number of hard-coded assumptions tied to the dict implementation. +This is, in part, due to performance reasons, which is understandable +given the part dict plays in Python. + +Any attempt to replace dict with OrderedDict for any role in the +interpreter (e.g. **kwds) faces a challenge. Such any effort must +recognize that the instances in affected locations currently interact with +the concrete API. + +Here are some ways to address this challenge: + +1. Change the relevant usage of the concrete API in CPython and add + PyDict_CheckExact() calls to each of the concrete API funcions. +2. Adjust the relevant concrete API functions to explicitly accommodate + OrderedDict. +3. As with #1, add the checks, but improve the abstract API with smart fast + paths for dict and OrderedDict, and refactor CPython to use the abstract + API. Improvements to the abstract API would be valuable regardless. + +Adding the checks to the concrete API would help make any interpreter +switch to OrderedDict less painful for extension modules. However, this +won't work. The equivalent C API call to `dict.__setitem__(obj, k, v)` +is 'PyDict_SetItem(obj, k, v)`. This illustrates how subclasses in C call +the base class's methods, since there is no equivalent of super() in the +C API. Calling into Python for parent class API would work, but some +extension modules already rely on this feature of the concrete API. + +For reference, here is a breakdown of some of the dict concrete API: + +========================== ============= ======================= +concrete API uses abstract API +========================== ============= ======================= +PyDict_Check PyMapping_Check +(PyDict_CheckExact) - +(PyDict_New) - +(PyDictProxy_New) - +PyDict_Clear - +PyDict_Contains PySequence_Contains +PyDict_Copy - +PyDict_SetItem PyObject_SetItem +PyDict_SetItemString PyMapping_SetItemString +PyDict_DelItem PyMapping_DelItem +PyDict_DelItemString PyMapping_DelItemString +PyDict_GetItem - +PyDict_GetItemWithError PyObject_GetItem +_PyDict_GetItemIdWithError - +PyDict_GetItemString PyMapping_GetItemString +PyDict_Items PyMapping_Items +PyDict_Keys PyMapping_Keys +PyDict_Values PyMapping_Values +PyDict_Size PyMapping_Size + PyMapping_Length +PyDict_Next PyIter_Next +_PyDict_Next - +PyDict_Merge - +PyDict_Update - +PyDict_MergeFromSeq2 - +PyDict_ClearFreeList - +- PyMapping_HasKeyString +- PyMapping_HasKey +========================== ============= ======================= + + +The dict Interface Relative to OrderedDict +========================================== + +Since OrderedDict subclasses dict, understanding the various methods and +attributes of dict is important for implementing OrderedDict. + +Relevant Type Slots +------------------- + +================= ================ =================== ================ +slot attribute object dict +================= ================ =================== ================ +tp_dealloc - object_dealloc dict_dealloc +tp_repr __repr__ object_repr dict_repr +sq_contains __contains__ - dict_contains +mp_length __len__ - dict_length +mp_subscript __getitem__ - dict_subscript +mp_ass_subscript __setitem__ - dict_ass_sub + __delitem__ +tp_hash __hash__ _Py_HashPointer ..._HashNotImpl +tp_str __str__ object_str - +tp_getattro __getattribute__ ..._GenericGetAttr (repeated) + __getattr__ +tp_setattro __setattr__ ..._GenericSetAttr (disabled) +tp_doc __doc__ (literal) dictionary_doc +tp_traverse - - dict_traverse +tp_clear - - dict_tp_clear +tp_richcompare __eq__ object_richcompare dict_richcompare + __ne__ +tp_weaklistoffset (__weakref__) - - +tp_iter __iter__ - dict_iter +tp_dictoffset (__dict__) - - +tp_init __init__ object_init dict_init +tp_alloc - PyType_GenericAlloc (repeated) +tp_new __new__ object_new dict_new +tp_free - PyObject_Del PyObject_GC_Del +================= ================ =================== ================ + +Relevant Methods +---------------- + +================ =================== =============== +method object dict +================ =================== =============== +__reduce__ object_reduce - +__sizeof__ object_sizeof dict_sizeof +clear - dict_clear +copy - dict_copy +fromkeys - dict_fromkeys +get - dict_get +items - dictitems_new +keys - dictkeys_new +pop - dict_pop +popitem - dict_popitem +setdefault - dict_setdefault +update - dict_update +values - dictvalues_new +================ =================== =============== + + +Pure Python OrderedDict +======================= + +As already noted, compatibility with the pure Python OrderedDict +implementation is a key goal of this C implementation. To further that +goal, here's a summary of how OrderedDict-specific methods are implemented +in collections/__init__.py. Also provided is an indication of which +methods directly mutate or iterate the object, as well as any relationship +with the underlying linked-list. + +============= ============== == ================ === === ==== +method impl used ll uses inq mut iter +============= ============== == ================ === === ==== +__contains__ dict - - X +__delitem__ OrderedDict Y dict.__delitem__ X +__eq__ OrderedDict N OrderedDict ~ + dict.__eq__ + __iter__ +__getitem__ dict - - X +__iter__ OrderedDict Y - X +__init__ OrderedDict N update +__len__ dict - - X +__ne__ MutableMapping - __eq__ ~ +__reduce__ OrderedDict N OrderedDict ~ + __iter__ + __getitem__ +__repr__ OrderedDict N __class__ ~ + items +__reversed__ OrderedDict Y - X +__setitem__ OrderedDict Y __contains__ X + dict.__setitem__ +__sizeof__ OrderedDict Y __len__ ~ + __dict__ +clear OrderedDict Y dict.clear X +copy OrderedDict N __class__ + __init__ +fromkeys OrderedDict N __setitem__ +get dict - - ~ +items MutableMapping - ItemsView X +keys MutableMapping - KeysView X +move_to_end OrderedDict Y - X +pop OrderedDict N __contains__ X + __getitem__ + __delitem__ +popitem OrderedDict Y dict.pop X +setdefault OrderedDict N __contains__ ~ + __getitem__ + __setitem__ +update MutableMapping - __setitem__ ~ +values MutableMapping - ValuesView X +============= ============== == ================ === === ==== + +__reversed__ and move_to_end are both exclusive to OrderedDict. + + +C OrderedDict Implementation +============================ + +================= ================ +slot impl +================= ================ +tp_dealloc odict_dealloc +tp_repr odict_repr +mp_ass_subscript odict_ass_sub +tp_doc odict_doc +tp_traverse odict_traverse +tp_clear odict_tp_clear +tp_richcompare odict_richcompare +tp_weaklistoffset (offset) +tp_iter odict_iter +tp_dictoffset (offset) +tp_init odict_init +tp_alloc (repeated) +tp_new odict_new +================= ================ + +================= ================ +method impl +================= ================ +__reduce__ odict_reduce +__sizeof__ odict_sizeof +clear odict_clear +copy odict_copy +fromkeys odict_fromkeys +items odictitems_new +keys odictkeys_new +pop odict_pop +popitem odict_popitem +setdefault odict_setdefault +update odict_update +values odictvalues_new +================= ================ + +Inherited unchanged from object/dict: + +================ ========================== +method type field +================ ========================== +- tp_free +__contains__ tp_as_sequence.sq_contains +__getattr__ tp_getattro +__getattribute__ tp_getattro +__getitem__ tp_as_mapping.mp_subscript +__hash__ tp_hash +__len__ tp_as_mapping.mp_length +__setattr__ tp_setattro +__str__ tp_str +get - +================ ========================== + + +Other Challenges +================ + +Preserving Ordering During Iteration +------------------------------------ +During iteration through an OrderedDict, it is possible that items could +get added, removed, or reordered. For a linked-list implementation, as +with some other implementations, that situation may lead to undefined +behavior. The documentation for dict mentions this in the `iter()` section +of http://docs.python.org/3.4/library/stdtypes.html#dictionary-view-objects. +In this implementation we follow dict's lead (as does the pure Python +implementation) for __iter__(), keys(), values(), and items(). + +For internal iteration (using _odict_FOREACH or not), there is still the +risk that not all nodes that we expect to be seen in the loop actually get +seen. Thus, we are careful in each of those places to ensure that they +are. This comes, of course, at a small price at each location. The +solutions are much the same as those detailed in the `Situation that +Endangers Consistency` section above. + + +Potential Optimizations +======================= + +* Allocate the nodes as a block via od_fast_nodes instead of individually. + - Set node->key to NULL to indicate the node is not-in-use. + - Add _odict_EXISTS()? + - How to maintain consistency across resizes? Existing node pointers + would be invalidate after a resize, which is particularly problematic + for the iterators. +* Use a more stream-lined implementation of update() and, likely indirectly, + __init__(). + +*/ + +/* TODO + +sooner: +- reentrancy (make sure everything is at a thread-safe state when calling + into Python). I've already checked this multiple times, but want to + make one more pass. +- add unit tests for reentrancy? + +later: +- make the dict views support the full set API (the pure Python impl does) +- implement a fuller MutableMapping API in C? +- move the MutableMapping implementation to abstract.c? +- optimize mutablemapping_update +- use PyObject_MALLOC (small object allocator) for odict nodes? +- support subclasses better (e.g. in odict_richcompare) + +*/ + +#include "Python.h" +#include "structmember.h" +#include "dict-common.h" +#include <stddef.h> + + +typedef struct _odictnode _ODictNode; + +/* PyODictObject */ +struct _odictobject { + /* od_dict is the underlying dict. */ + PyDictObject od_dict; + /* od_first is the first node in the odict, if any. */ + _ODictNode *od_first; + /* od_last is the last node in the odict, if any. */ + _ODictNode *od_last; + /* od_size is the number of entries in od_fast_nodes. */ + Py_ssize_t od_size; /* managed by _odict_resize() */ + /* od_fast_nodes is a hash table that mirrors the dict table. */ + _ODictNode **od_fast_nodes; /* managed by _odict_resize() */ + /* od_inst_dict is OrderedDict().__dict__. */ + PyObject *od_inst_dict; + /* od_weakreflist holds weakrefs to the odict. */ + PyObject *od_weakreflist; +}; + + +/* ---------------------------------------------- + * odict keys (a simple doubly-linked list) + */ + +struct _odictnode { + PyObject *key; + _ODictNode *next; + _ODictNode *prev; +}; + +#define _odictnode_KEY(node) \ + (node->key) +/* borrowed reference */ +#define _odictnode_VALUE(node, od) \ + PyODict_GetItem((PyObject *)od, _odictnode_KEY(node)) +/* If needed we could also have _odictnode_HASH. */ +#define _odictnode_PREV(node) (node->prev) +#define _odictnode_NEXT(node) (node->next) + +#define _odict_FIRST(od) (((PyODictObject *)od)->od_first) +#define _odict_LAST(od) (((PyODictObject *)od)->od_last) +#define _odict_EMPTY(od) (_odict_FIRST(od) == NULL) +#define _odict_FOREACH(od, node) \ + for (node = _odict_FIRST(od); node != NULL; node = _odictnode_NEXT(node)) + + +static Py_ssize_t _odict_get_index(PyODictObject *, PyObject *); /* forward */ + +static void +_odict_free_fast_nodes(PyODictObject *od) { + if (od->od_fast_nodes) { + PyMem_FREE(od->od_fast_nodes); + } +} + +static int +_odict_resize(PyODictObject *od) { + Py_ssize_t size, prev_size, i; + _ODictNode **fast_nodes, *node; + + /* Initialize a new "fast nodes" table. */ + size = ((PyDictObject *)od)->ma_keys->dk_size; + fast_nodes = PyMem_NEW(_ODictNode *, size); + if (fast_nodes == NULL) { + PyErr_NoMemory(); + return -1; + } + for (i = 0; i < size; i++) + fast_nodes[i] = NULL; + + /* Copy the current nodes into the table. */ + prev_size = od->od_size; + od->od_size = size; + _odict_FOREACH(od, node) { + assert(node != NULL); + i = _odict_get_index(od, _odictnode_KEY(node)); + if (i < 0) { + od->od_size = prev_size; + PyMem_FREE(fast_nodes); + return -1; + } + fast_nodes[i] = node; + } + if (size != ((PyDictObject *)od)->ma_keys->dk_size) { + /* If _odict_get_index triggered a resize then we are already done. */ + PyMem_FREE(fast_nodes); + return 0; + } + + /* Replace the old fast nodes table. */ + _odict_free_fast_nodes(od); + od->od_fast_nodes = fast_nodes; + return 0; +} + +/* Return the index into the hash table, regardless of a valid node. */ +static Py_ssize_t +_odict_get_index(PyODictObject *od, PyObject *key) +{ + Py_hash_t hash; + PyObject **value_addr = NULL; + PyDictKeyEntry *ep; + PyDictKeysObject *keys = ((PyDictObject *)od)->ma_keys; + + assert(key != NULL); + do { + /* Ensure od_fast_nodes and dk_entries are in sync. */ + if (keys->dk_size != od->od_size) { + int resize_res = _odict_resize(od); + if (resize_res < 0) + return -1; + } + + /* now get the index */ + hash = PyObject_Hash(key); + if (hash == -1) + return -1; + /* May have resized during the PyObject_Hash() call. */ + keys = ((PyDictObject *)od)->ma_keys; + } while (keys->dk_size != od->od_size); + + ep = (keys->dk_lookup)((PyDictObject *)od, key, hash, &value_addr); + if (ep == NULL) + return -1; + /* We use pointer arithmetic to get the entry's index into the table. */ + return ep - keys->dk_entries; +} + +static int +_odict_initialize(PyODictObject *od) +{ + _odict_FIRST(od) = NULL; + _odict_LAST(od) = NULL; + return _odict_resize((PyODictObject *)od); +} + +/* Returns NULL if there was some error or the key was not found. */ +static _ODictNode * +_odict_find_node(PyODictObject *od, PyObject *key) +{ + Py_ssize_t index; + + if (_odict_EMPTY(od)) + return NULL; + index = _odict_get_index(od, key); + if (index < 0) + return NULL; + return od->od_fast_nodes[index]; +} + +static void +_odict_add_head(PyODictObject *od, _ODictNode *node) +{ + if (_odict_FIRST(od) == NULL) { + _odictnode_PREV(node) = NULL; + _odictnode_NEXT(node) = NULL; + _odict_FIRST(od) = node; + _odict_LAST(od) = node; + } + else { + _odictnode_PREV(node) = NULL; + _odictnode_NEXT(node) = _odict_FIRST(od); + _odict_FIRST(od) = node; + _odictnode_PREV(_odict_FIRST(od)) = node; + } +} + +static void +_odict_add_tail(PyODictObject *od, _ODictNode *node) +{ + if (_odict_LAST(od) == NULL) { + _odictnode_PREV(node) = NULL; + _odictnode_NEXT(node) = NULL; + _odict_FIRST(od) = node; + _odict_LAST(od) = node; + } + else { + _odictnode_PREV(node) = _odict_LAST(od); + _odictnode_NEXT(node) = NULL; + _odictnode_NEXT(_odict_LAST(od)) = node; + _odict_LAST(od) = node; + } +} + +/* adds the node to the end of the list */ +static int +_odict_add_new_node(PyODictObject *od, PyObject *key) +{ + Py_ssize_t i; + _ODictNode *node; + + Py_INCREF(key); + i = _odict_get_index(od, key); + if (i < 0) { + if (!PyErr_Occurred()) + PyErr_SetObject(PyExc_KeyError, key); + Py_DECREF(key); + return -1; + } + else if (od->od_fast_nodes[i] != NULL) { + /* We already have a node for the key so there's no need to add one. */ + Py_DECREF(key); + return 0; + } + + /* must not be added yet */ + node = (_ODictNode *)PyMem_MALLOC(sizeof(_ODictNode)); + if (node == NULL) { + Py_DECREF(key); + PyErr_NoMemory(); + return -1; + } + + _odictnode_KEY(node) = key; + _odict_add_tail(od, node); + od->od_fast_nodes[i] = node; + return 0; +} + +/* Putting the decref after the free causes problems. */ +#define _odictnode_DEALLOC(node) \ + do { \ + Py_DECREF(_odictnode_KEY(node)); \ + PyMem_FREE((void *)node); \ + } while (0) + +/* Repeated calls on the same node are no-ops. */ +static void +_odict_remove_node(PyODictObject *od, _ODictNode *node) +{ + if (_odict_FIRST(od) == node) + _odict_FIRST(od) = _odictnode_NEXT(node); + else if (_odictnode_PREV(node) != NULL) + _odictnode_NEXT(_odictnode_PREV(node)) = _odictnode_NEXT(node); + + if (_odict_LAST(od) == node) + _odict_LAST(od) = _odictnode_PREV(node); + else if (_odictnode_NEXT(node) != NULL) + _odictnode_PREV(_odictnode_NEXT(node)) = _odictnode_PREV(node); + + _odictnode_PREV(node) = NULL; + _odictnode_NEXT(node) = NULL; +} + +static _ODictNode * +_odict_pop_node(PyODictObject *od, _ODictNode *node, PyObject *key) +{ + if (node == NULL) { + node = _odict_find_node(od, key); + if (node == NULL) + return NULL; + } + _odict_remove_node(od, node); + return node; +} + +/* If someone calls PyDict_DelItem() directly on an OrderedDict, we'll + get all sorts of problems here. In PyODict_DelItem we make sure to + call _odict_clear_node first. + + This matters in the case of colliding keys. Suppose we add 3 keys: + [A, B, C], where the hash of C collides with A and the next possible + index in the hash table is occupied by B. If we remove B then for C + the dict's looknode func will give us the old index of B instead of + the index we got before deleting B. However, the node for C in + od_fast_nodes is still at the old dict index of C. Thus to be sure + things don't get out of sync, we clear the node in od_fast_nodes + *before* calling PyDict_DelItem. + + The same must be done for any other OrderedDict operations where + we modify od_fast_nodes. +*/ +static int +_odict_clear_node(PyODictObject *od, _ODictNode *node, PyObject *key) +{ + Py_ssize_t i; + + assert(key != NULL); + if (_odict_EMPTY(od)) { + /* Let later code decide if this is a KeyError. */ + return 0; + } + + i = _odict_get_index(od, key); + if (i < 0) + return PyErr_Occurred() ? -1 : 0; + + if (node == NULL) + node = od->od_fast_nodes[i]; + assert(node == od->od_fast_nodes[i]); + if (node == NULL) { + /* Let later code decide if this is a KeyError. */ + return 0; + } + + // Now clear the node. + od->od_fast_nodes[i] = NULL; + _odict_remove_node(od, node); + _odictnode_DEALLOC(node); + return 0; +} + +static void +_odict_clear_nodes(PyODictObject *od) +{ + _ODictNode *node, *next; + + if (!_odict_EMPTY(od)) { + node = _odict_FIRST(od); + while (node != NULL) { + next = _odictnode_NEXT(node); + _odictnode_DEALLOC(node); + node = next; + } + _odict_FIRST(od) = NULL; + _odict_LAST(od) = NULL; + } + + _odict_free_fast_nodes(od); + od->od_fast_nodes = NULL; +} + +/* There isn't any memory management of nodes past this point. */ +#undef _odictnode_DEALLOC + +static int +_odict_keys_equal(PyODictObject *a, PyODictObject *b) +{ + _ODictNode *node_a, *node_b; + + node_a = _odict_FIRST(a); + node_b = _odict_FIRST(b); + while (1) { + if (node_a == NULL && node_b == NULL) + /* success: hit the end of each at the same time */ + return 1; + else if (node_a == NULL || node_b == NULL) + /* unequal length */ + return 0; + else { + int res = PyObject_RichCompareBool( + (PyObject *)_odictnode_KEY(node_a), + (PyObject *)_odictnode_KEY(node_b), + Py_EQ); + if (res < 0) + return res; + else if (res == 0) + return 0; + + /* otherwise it must match, so move on to the next one */ + node_a = _odictnode_NEXT(node_a); + node_b = _odictnode_NEXT(node_b); + } + } +} + + +/* ---------------------------------------------- + * OrderedDict mapping methods + */ + +/* mp_ass_subscript: __setitem__() and __delitem__() */ + +static int +odict_mp_ass_sub(PyODictObject *od, PyObject *v, PyObject *w) +{ + if (w == NULL) + return PyODict_DelItem((PyObject *)od, v); + else + return PyODict_SetItem((PyObject *)od, v, w); +} + +/* tp_as_mapping */ + +static PyMappingMethods odict_as_mapping = { + 0, /*mp_length*/ + 0, /*mp_subscript*/ + (objobjargproc)odict_mp_ass_sub, /*mp_ass_subscript*/ +}; + + +/* ---------------------------------------------- + * OrderedDict methods + */ + +/* __delitem__() */ + +PyDoc_STRVAR(odict_delitem__doc__, "od.__delitem__(y) <==> del od[y]"); + +/* __eq__() */ + +PyDoc_STRVAR(odict_eq__doc__, +"od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive \n\ + while comparison to a regular mapping is order-insensitive.\n\ + "); + +/* forward */ +static PyObject * odict_richcompare(PyObject *v, PyObject *w, int op); + +static PyObject * +odict_eq(PyObject *a, PyObject *b) +{ + return odict_richcompare(a, b, Py_EQ); +} + +/* __init__() */ + +PyDoc_STRVAR(odict_init__doc__, +"Initialize an ordered dictionary. The signature is the same as\n\ + regular dictionaries, but keyword arguments are not recommended because\n\ + their insertion order is arbitrary.\n\ +\n\ + "); + +/* forward */ +static int odict_init(PyObject *self, PyObject *args, PyObject *kwds); + +/* __iter__() */ + +PyDoc_STRVAR(odict_iter__doc__, "od.__iter__() <==> iter(od)"); + +static PyObject * odict_iter(PyODictObject *self); /* forward */ + +/* __ne__() */ + +/* Mapping.__ne__() does not have a docstring. */ +PyDoc_STRVAR(odict_ne__doc__, ""); + +static PyObject * +odict_ne(PyObject *a, PyObject *b) +{ + return odict_richcompare(a, b, Py_NE); +} + +/* __repr__() */ + +PyDoc_STRVAR(odict_repr__doc__, "od.__repr__() <==> repr(od)"); + +static PyObject * odict_repr(PyODictObject *self); /* forward */ + +/* __setitem__() */ + +PyDoc_STRVAR(odict_setitem__doc__, "od.__setitem__(i, y) <==> od[i]=y"); + +/* fromkeys() */ + +PyDoc_STRVAR(odict_fromkeys__doc__, +"OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S.\n\ + If not specified, the value defaults to None.\n\ +\n\ + "); + +static PyObject * +odict_fromkeys(PyObject *cls, PyObject *args) +{ + PyObject *seq; + PyObject *value = Py_None; + if (!PyArg_UnpackTuple(args, "fromkeys", 1, 2, &seq, &value)) /* borrowed */ + return NULL; + return _PyDict_FromKeys(cls, seq, value); +} + +/* __sizeof__() */ + +/* OrderedDict.__sizeof__() does not have a docstring. */ +PyDoc_STRVAR(odict_sizeof__doc__, ""); + +static PyObject * +odict_sizeof(PyODictObject *od) +{ + PyObject *pylong; + Py_ssize_t res; + + pylong = _PyDict_SizeOf((PyDictObject *)od); + if (pylong == NULL) + return NULL; + res = PyLong_AsSsize_t(pylong); + Py_DECREF(pylong); + if (res == -1 && PyErr_Occurred()) + return NULL; + + res += sizeof(PyODictObject) - sizeof(PyDictObject); + + /* instance dict */ + pylong = _PyDict_SizeOf((PyDictObject *)od->od_inst_dict); + if (pylong == NULL) + return NULL; + res += PyLong_AsSsize_t(pylong); + Py_DECREF(pylong); + if (res == -1 && PyErr_Occurred()) + return NULL; + + res += sizeof(_ODictNode) * od->od_size; /* od_fast_nodes */ + if (!_odict_EMPTY(od)) { + res += sizeof(_ODictNode) * PyODict_SIZE(od); /* linked-list */ + } + return PyLong_FromSsize_t(res); +} + +/* __reduce__() */ + +PyDoc_STRVAR(odict_reduce__doc__, "Return state information for pickling"); + +static PyObject * +odict_reduce(register PyODictObject *od) +{ + _Py_IDENTIFIER(__dict__); + _Py_IDENTIFIER(__class__); + PyObject *vars = NULL, *ns = NULL, *result = NULL, *cls = NULL; + PyObject *items_iter = NULL, *items = NULL, *args = NULL; + + /* capture any instance state */ + vars = _PyObject_GetAttrId((PyObject *)od, &PyId___dict__); + if (vars != NULL) { + PyObject *empty, *od_vars, *iterator, *key; + + /* od.__dict__ isn't necessarily a dict... */ + ns = PyObject_CallMethod((PyObject *)vars, "copy", NULL); + if (ns == NULL) + goto Done; + empty = PyODict_New(); + if (empty == NULL) + goto Done; + od_vars = _PyObject_GetAttrId((PyObject *)empty, &PyId___dict__); + Py_DECREF(empty); + if (od_vars == NULL) + goto Done; + iterator = PyObject_GetIter(od_vars); + Py_DECREF(od_vars); + if (iterator == NULL) + goto Done; + + while ( (key = PyIter_Next(iterator)) ) { + if (PyMapping_HasKey(ns, key) && PyMapping_DelItem(ns, key) != 0) { + Py_DECREF(iterator); + Py_DECREF(key); + goto Done; + } + Py_DECREF(key); + } + Py_DECREF(iterator); + if (PyErr_Occurred()) + goto Done; + + if (!PyObject_Length(ns)) { + /* nothing novel to pickle in od.__dict__ */ + Py_DECREF(ns); + ns = NULL; + } + } + + /* build the result */ + cls = _PyObject_GetAttrId((PyObject *)od, &PyId___class__); + if (cls == NULL) + goto Done; + + args = PyTuple_New(0); + if (args == NULL) + goto Done; + + items = PyObject_CallMethod((PyObject *)od, "items", NULL); + if (items == NULL) + goto Done; + + items_iter = PyObject_GetIter(items); + if (items_iter == NULL) + goto Done; + + result = PyTuple_Pack(5, cls, args, ns ? ns : Py_None, Py_None, items_iter); + +Done: + Py_XDECREF(vars); + Py_XDECREF(ns); + Py_XDECREF(cls); + Py_XDECREF(args); + Py_XDECREF(items); + Py_XDECREF(items_iter); + + return result; +} + +/* setdefault() */ + +PyDoc_STRVAR(odict_setdefault__doc__, + "od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od"); + +/* Skips __missing__() calls. */ +static PyObject * +odict_setdefault(register PyODictObject *od, PyObject *args) +{ + _ODictNode *node; + PyObject *key, *result = NULL; + PyObject *failobj = Py_None; + + /* both borrowed */ + if (!PyArg_UnpackTuple(args, "setdefault", 1, 2, &key, &failobj)) + return NULL; + Py_INCREF(key); + Py_INCREF(failobj); + + if (PyODict_CheckExact(od)) { + node = _odict_find_node(od, key); + if (node == NULL) { + if (PyErr_Occurred()) { + goto done; + } + else if (PyODict_SetItem((PyObject *)od, key, failobj) >= 0) { + result = failobj; + Py_INCREF(failobj); + } + } + else { + result = PyODict_GetItem(od, key); /* borrowed reference */ + Py_XINCREF(result); + } + } + else { + int exists = PySequence_Contains((PyObject *)od, key); + if (exists < 0) { + goto done; + } + else if (exists) { + result = PyObject_GetItem((PyObject *)od, key); + } + else if (PyObject_SetItem((PyObject *)od, key, failobj) >= 0) { + result = failobj; + Py_INCREF(failobj); + } + } + +done: + Py_DECREF(failobj); + Py_DECREF(key); + return result; +} + +/* pop() */ + +PyDoc_STRVAR(odict_pop__doc__, +"od.pop(k[,d]) -> v, remove specified key and return the corresponding\n\ + value. If key is not found, d is returned if given, otherwise KeyError\n\ + is raised.\n\ +\n\ + "); + +/* forward */ +static PyObject * _odict_popkey(PyObject *, PyObject *, PyObject *); + +/* Skips __missing__() calls. */ +static PyObject * +odict_pop(PyObject *od, PyObject *args) +{ + PyObject *key, *failobj = NULL; + + if (!PyArg_UnpackTuple(args, "pop", 1, 2, &key, &failobj)) { /* borrowed */ + return NULL; + } + + return _odict_popkey(od, key, failobj); +} + +static PyObject * +_odict_popkey(PyObject *od, PyObject *key, PyObject *failobj) +{ + _ODictNode *node; + PyObject *value = NULL; + + Py_INCREF(key); + Py_XINCREF(failobj); + + /* Pop the node first to avoid a possible dict resize (due to + eval loop reentrancy) and complications due to hash collision + resolution. */ + node = _odict_find_node((PyODictObject *)od, key); + if (node == NULL) { + if (PyErr_Occurred()) + goto done; + } + else { + int res = _odict_clear_node((PyODictObject *)od, node, key); + if (res < 0) { + goto done; + } + } + + /* Now delete the value from the dict. */ + if (PyODict_CheckExact(od)) { + if (node != NULL) { + /* We could do PyDict_GetItem() and PyDict_DelItem() directly... */ + value = _PyDict_Pop((PyDictObject *)od, key, failobj); + } + } + else { + int exists = PySequence_Contains(od, key); + if (exists < 0) + goto done; + if (exists) { + value = PyObject_GetItem(od, key); + if (value != NULL) { + if (PyObject_DelItem(od, key) == -1) { + Py_DECREF(value); + value = NULL; + } + } + } + } + + /* Apply the fallback value, if necessary. */ + if (value == NULL && !PyErr_Occurred()) { + if (failobj) { + value = failobj; + Py_INCREF(failobj); + } + else { + PyErr_SetObject(PyExc_KeyError, key); + } + } + +done: + Py_DECREF(key); + Py_XDECREF(failobj); + return value; +} + +/* popitem() */ + +PyDoc_STRVAR(odict_popitem__doc__, +"od.popitem() -> (k, v), return and remove a (key, value) pair.\n\ + Pairs are returned in LIFO order if last is true or FIFO order if false.\n\ +\n\ + "); + +static PyObject * +odict_popitem(PyObject *od, PyObject *args) +{ + PyObject *key, *value, *item = NULL, *last = NULL; + _ODictNode *node; + + if (_odict_EMPTY((PyODictObject *)od)) { + PyErr_SetString(PyExc_KeyError, "dictionary is empty"); + return NULL; + } + + /* pull the item */ + + if (!PyArg_UnpackTuple(args, "popitem", 0, 1, &last)) /* borrowed */ + return NULL; + Py_XINCREF(last); + + if (last == NULL || last == Py_True) + node = _odict_LAST((PyODictObject *)od); + else + node = _odict_FIRST((PyODictObject *)od); + Py_XDECREF(last); + + key = _odictnode_KEY(node); + value = _odict_popkey(od, key, NULL); + if (value == NULL) + return NULL; + item = PyTuple_Pack(2, key, value); + Py_DECREF(value); + return item; +} + +/* keys() */ + +/* MutableMapping.keys() does not have a docstring. */ +PyDoc_STRVAR(odict_keys__doc__, ""); + +static PyObject * odictkeys_new(PyObject *od); /* forward */ + +/* values() */ + +/* MutableMapping.values() does not have a docstring. */ +PyDoc_STRVAR(odict_values__doc__, ""); + +static PyObject * odictvalues_new(PyObject *od); /* forward */ + +/* items() */ + +/* MutableMapping.items() does not have a docstring. */ +PyDoc_STRVAR(odict_items__doc__, ""); + +static PyObject * odictitems_new(PyObject *od); /* forward */ + +/* update() */ + +/* MutableMapping.update() does not have a docstring. */ +PyDoc_STRVAR(odict_update__doc__, ""); + +/* forward */ +static PyObject * mutablemapping_update(PyObject *, PyObject *, PyObject *); + +#define odict_update mutablemapping_update + +/* clear() */ + +PyDoc_STRVAR(odict_clear__doc__, + "od.clear() -> None. Remove all items from od."); + +static PyObject * +odict_clear(register PyODictObject *od) +{ + PyDict_Clear((PyObject *)od); + _odict_clear_nodes(od); + _odict_FIRST(od) = NULL; + _odict_LAST(od) = NULL; + if (_odict_resize(od) < 0) + return NULL; + Py_RETURN_NONE; +} + +/* copy() */ + +PyDoc_STRVAR(odict_copy__doc__, "od.copy() -> a shallow copy of od"); + +static PyObject * +odict_copy(register PyODictObject *od) +{ + _ODictNode *node; + PyObject *od_copy; + + if (PyODict_CheckExact(od)) + od_copy = PyODict_New(); + else + od_copy = PyObject_CallFunctionObjArgs((PyObject *)Py_TYPE(od), NULL); + if (od_copy == NULL) + return NULL; + + if (PyODict_CheckExact(od)) { + _odict_FOREACH(od, node) { + int res = PyODict_SetItem((PyObject *)od_copy, + _odictnode_KEY(node), + _odictnode_VALUE(node, od)); + if (res != 0) + goto fail; + } + } + else { + _odict_FOREACH(od, node) { + int res; + PyObject *value = PyObject_GetItem((PyObject *)od, + _odictnode_KEY(node)); + if (value == NULL) + goto fail; + res = PyObject_SetItem((PyObject *)od_copy, + _odictnode_KEY(node), value); + Py_DECREF(value); + if (res != 0) + goto fail; + } + } + return od_copy; + +fail: + Py_DECREF(od_copy); + return NULL; +} + +/* __reversed__() */ + +PyDoc_STRVAR(odict_reversed__doc__, "od.__reversed__() <==> reversed(od)"); + +#define _odict_ITER_REVERSED 1 +#define _odict_ITER_KEYS 2 +#define _odict_ITER_VALUES 4 + +/* forward */ +static PyObject * odictiter_new(PyODictObject *, int); + +static PyObject * +odict_reversed(PyODictObject *od) +{ + if (_odict_EMPTY(od)) { + Py_RETURN_NONE; + } + return odictiter_new(od, _odict_ITER_KEYS|_odict_ITER_REVERSED); +} + +/* move_to_end() */ + +PyDoc_STRVAR(odict_move_to_end__doc__, +"Move an existing element to the end (or beginning if last==False).\n\ +\n\ + Raises KeyError if the element does not exist.\n\ + When last=True, acts like a fast version of self[key]=self.pop(key).\n\ +\n\ + "); + +static PyObject * +odict_move_to_end(PyODictObject *od, PyObject *args) +{ + PyObject *key, *last = NULL; + Py_ssize_t pos = -1; + + /* both borrowed */ + if (!PyArg_UnpackTuple(args, "move_to_end", 1, 2, &key, &last)) + return NULL; + Py_INCREF(key); + if (_odict_EMPTY(od)) { + PyErr_SetObject(PyExc_KeyError, key); + Py_DECREF(key); + return NULL; + } + if (last != NULL) { + Py_INCREF(last); + pos = PyObject_IsTrue(last) ? -1 : 0; + Py_DECREF(last); + } + if (pos == 0) { + /* Only move if not already the first one. */ + PyObject *first_key = _odictnode_KEY(_odict_FIRST(od)); + if (PyObject_RichCompareBool(key, first_key, Py_NE)) { + _ODictNode *node = _odict_pop_node(od, NULL, key); + if (node != NULL) { + _odict_add_head(od, node); + } + else { + if (!PyErr_Occurred()) + PyErr_SetObject(PyExc_KeyError, key); + Py_DECREF(key); + return NULL; + } + } + } + else if (pos == -1) { + /* Only move if not already the last one. */ + PyObject *last_key = _odictnode_KEY(_odict_LAST(od)); + if (PyObject_RichCompareBool(key, last_key, Py_NE)) { + _ODictNode *node = _odict_pop_node(od, NULL, key); + if (node != NULL) { + _odict_add_tail(od, node); + } + else { + if (!PyErr_Occurred()) + PyErr_SetObject(PyExc_KeyError, key); + Py_DECREF(key); + return NULL; + } + } + } + Py_DECREF(key); + Py_RETURN_NONE; +} + + +/* tp_methods */ + +static PyMethodDef odict_methods[] = { + + /* explicitly defined so we can align docstrings with + * collections.OrderedDict */ + {"__delitem__", (PyCFunction)odict_mp_ass_sub, METH_NOARGS, + odict_delitem__doc__}, + {"__eq__", (PyCFunction)odict_eq, METH_NOARGS, + odict_eq__doc__}, + {"__init__", (PyCFunction)odict_init, METH_NOARGS, + odict_init__doc__}, + {"__iter__", (PyCFunction)odict_iter, METH_NOARGS, + odict_iter__doc__}, + {"__ne__", (PyCFunction)odict_ne, METH_NOARGS, + odict_ne__doc__}, + {"__repr__", (PyCFunction)odict_repr, METH_NOARGS, + odict_repr__doc__}, + {"__setitem__", (PyCFunction)odict_mp_ass_sub, METH_NOARGS, + odict_setitem__doc__}, + {"fromkeys", (PyCFunction)odict_fromkeys, METH_VARARGS | METH_CLASS, + odict_fromkeys__doc__}, + + /* overridden dict methods */ + {"__sizeof__", (PyCFunction)odict_sizeof, METH_NOARGS, + odict_sizeof__doc__}, + {"__reduce__", (PyCFunction)odict_reduce, METH_NOARGS, + odict_reduce__doc__}, + {"setdefault", (PyCFunction)odict_setdefault, METH_VARARGS, + odict_setdefault__doc__}, + {"pop", (PyCFunction)odict_pop, METH_VARARGS, + odict_pop__doc__}, + {"popitem", (PyCFunction)odict_popitem, METH_VARARGS, + odict_popitem__doc__}, + {"keys", (PyCFunction)odictkeys_new, METH_NOARGS, + odict_keys__doc__}, + {"values", (PyCFunction)odictvalues_new, METH_NOARGS, + odict_values__doc__}, + {"items", (PyCFunction)odictitems_new, METH_NOARGS, + odict_items__doc__}, + {"update", (PyCFunction)odict_update, METH_VARARGS | METH_KEYWORDS, + odict_update__doc__}, + {"clear", (PyCFunction)odict_clear, METH_NOARGS, + odict_clear__doc__}, + {"copy", (PyCFunction)odict_copy, METH_NOARGS, + odict_copy__doc__}, + + /* new methods */ + {"__reversed__", (PyCFunction)odict_reversed, METH_NOARGS, + odict_reversed__doc__}, + {"move_to_end", (PyCFunction)odict_move_to_end, METH_VARARGS, + odict_move_to_end__doc__}, + + {NULL, NULL} /* sentinel */ +}; + + +/* ---------------------------------------------- + * OrderedDict members + */ + +/* tp_members */ + +static PyMemberDef odict_members[] = { + {"__dict__", T_OBJECT, offsetof(PyODictObject, od_inst_dict), READONLY}, + {0} +}; + + +/* ---------------------------------------------- + * OrderedDict type slot methods + */ + +/* tp_dealloc */ + +static void +odict_dealloc(PyODictObject *self) +{ + PyObject_GC_UnTrack(self); + Py_TRASHCAN_SAFE_BEGIN(self); + Py_XDECREF(self->od_inst_dict); + if (self->od_weakreflist != NULL) + PyObject_ClearWeakRefs((PyObject *)self); + + _odict_clear_nodes(self); + Py_TRASHCAN_SAFE_END(self); + + /* must be last */ + PyDict_Type.tp_dealloc((PyObject *)self); +}; + +/* tp_repr */ + +static PyObject * +odict_repr(PyODictObject *self) +{ + int i; + const char *formatstr; + _Py_IDENTIFIER(__class__); + _Py_IDENTIFIER(__name__); + Py_ssize_t count = -1; + PyObject *pieces = NULL, *result = NULL, *cls = NULL; + PyObject *classname = NULL, *format = NULL, *args = NULL; + _ODictNode *node; + + i = Py_ReprEnter((PyObject *)self); + if (i != 0) { + return i > 0 ? PyUnicode_FromString("...") : NULL; + } + + if (PyODict_SIZE(self) == 0) { + /* "OrderedDict()" */ + goto Finish; + } + + if (PyODict_CheckExact(self)) { + pieces = PyList_New(PyODict_SIZE(self)); + if (pieces == NULL) + goto Done; + + _odict_FOREACH(self, node) { + PyObject *pair = PyTuple_Pack(2, _odictnode_KEY(node), + _odictnode_VALUE(node, self)); + if (pair == NULL) + goto Done; + + PyList_SET_ITEM(pieces, ++count, pair); /* steals reference */ + } + } + else { + PyObject *items = PyObject_CallMethod((PyObject *)self, "items", NULL); + if (items == NULL) + goto Done; + pieces = PySequence_List(items); + Py_DECREF(items); + if(pieces == NULL) + goto Done; + } + +Finish: + cls = _PyObject_GetAttrId((PyObject *)self, &PyId___class__); + if (cls == NULL) + goto Done; + classname = _PyObject_GetAttrId(cls, &PyId___name__); + if (classname == NULL) + goto Done; + + if (pieces == NULL) { + formatstr = "%s()"; + args = PyTuple_Pack(1, classname); + } + else { + formatstr = "%s(%r)"; + args = PyTuple_Pack(2, classname, pieces); + } + if (args == NULL) + goto Done; + + format = PyUnicode_InternFromString(formatstr); + if (format == NULL) + goto Done; + + result = PyUnicode_Format(format, args); +Done: + Py_XDECREF(pieces); + Py_XDECREF(cls); + Py_XDECREF(classname); + Py_XDECREF(format); + Py_XDECREF(args); + Py_ReprLeave((PyObject *)self); + return result; +}; + +/* tp_doc */ + +PyDoc_STRVAR(odict_doc, + "Dictionary that remembers insertion order"); + +/* tp_traverse */ + +static int +odict_traverse(PyODictObject *od, visitproc visit, void *arg) +{ + Py_VISIT(od->od_inst_dict); + Py_VISIT(od->od_weakreflist); + return PyDict_Type.tp_traverse((PyObject *)od, visit, arg); +} + +/* tp_clear */ + +static int +odict_tp_clear(PyODictObject *od) +{ + PyObject *res; + Py_CLEAR(od->od_inst_dict); + Py_CLEAR(od->od_weakreflist); + res = odict_clear(od); + if (res == NULL) + return -1; + Py_DECREF(res); + return 0; +} + +/* tp_richcompare */ + +static PyObject * +odict_richcompare(PyObject *v, PyObject *w, int op) +{ + if (!PyODict_Check(v) || !PyDict_Check(w)) { + Py_RETURN_NOTIMPLEMENTED; + } + + if (op == Py_EQ || op == Py_NE) { + PyObject *res, *cmp; + int eq; + + cmp = PyDict_Type.tp_richcompare(v, w, op); + if (cmp == NULL) + return NULL; + if (!PyODict_Check(w)) + return cmp; + if (op == Py_EQ && cmp == Py_False) + return cmp; + if (op == Py_NE && cmp == Py_True) + return cmp; + Py_DECREF(cmp); + + /* Try comparing odict keys. */ + eq = _odict_keys_equal((PyODictObject *)v, (PyODictObject *)w); + if (eq < 0) + return NULL; + + res = (eq == (op == Py_EQ)) ? Py_True : Py_False; + Py_INCREF(res); + return res; + } else { + Py_RETURN_NOTIMPLEMENTED; + } +}; + +/* tp_iter */ + +static PyObject * +odict_iter(PyODictObject *od) +{ + return odictiter_new(od, _odict_ITER_KEYS); +}; + +/* tp_init */ + +static int +odict_init(PyObject *self, PyObject *args, PyObject *kwds) +{ + PyObject *res; + Py_ssize_t len = PyObject_Length(args); + + if (len == -1) + return -1; + if (len > 1) { + char *msg = "expected at most 1 arguments, got %d"; + PyErr_Format(PyExc_TypeError, msg, len); + return -1; + } + + /* __init__() triggering update() is just the way things are! */ + res = odict_update(self, args, kwds); + if (res == NULL) { + return -1; + } else { + Py_DECREF(res); + return 0; + } +}; + +/* tp_new */ + +static PyObject * +odict_new(PyTypeObject *type, PyObject *args, PyObject *kwds) +{ + PyObject *od = PyDict_Type.tp_new(type, args, kwds); + if (od != NULL) { + ((PyODictObject *)od)->od_inst_dict = PyDict_New(); + ((PyODictObject *)od)->od_weakreflist = NULL; + if (_odict_initialize((PyODictObject *)od) < 0) + return NULL; + } + return od; +} + +/* PyODict_Type */ + +PyTypeObject PyODict_Type = { + PyVarObject_HEAD_INIT(&PyType_Type, 0) + "collections.OrderedDict", /* tp_name */ + sizeof(PyODictObject), /* tp_basicsize */ + 0, /* tp_itemsize */ + (destructor)odict_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_reserved */ + (reprfunc)odict_repr, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + &odict_as_mapping, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + 0, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,/* tp_flags */ + odict_doc, /* tp_doc */ + (traverseproc)odict_traverse, /* tp_traverse */ + (inquiry)odict_tp_clear, /* tp_clear */ + (richcmpfunc)odict_richcompare, /* tp_richcompare */ + offsetof(PyODictObject, od_weakreflist), /* tp_weaklistoffset */ + (getiterfunc)odict_iter, /* tp_iter */ + 0, /* tp_iternext */ + odict_methods, /* tp_methods */ + odict_members, /* tp_members */ + 0, /* tp_getset */ + &PyDict_Type, /* tp_base */ + 0, /* tp_dict */ + 0, /* tp_descr_get */ + 0, /* tp_descr_set */ + offsetof(PyODictObject, od_inst_dict), /* tp_dictoffset */ + (initproc)odict_init, /* tp_init */ + PyType_GenericAlloc, /* tp_alloc */ + (newfunc)odict_new, /* tp_new */ + 0, /* tp_free */ +}; + + +/* ---------------------------------------------- + * the public OrderedDict API + */ + +PyObject * +PyODict_New(void) { + return odict_new(&PyODict_Type, NULL, NULL); +}; + +int +PyODict_SetItem(PyObject *od, PyObject *key, PyObject *value) { + int res = PyDict_SetItem(od, key, value); + if (res == 0) { + res = _odict_add_new_node((PyODictObject *)od, key); + } + return res; +}; + +int +PyODict_DelItem(PyObject *od, PyObject *key) { + int res = _odict_clear_node((PyODictObject *)od, NULL, key); + if (res < 0) + return -1; + return PyDict_DelItem(od, key); +}; + + +/* ------------------------------------------- + * The OrderedDict views (keys/values/items) + */ + +typedef struct { + PyObject_HEAD + int kind; + PyODictObject *di_odict; + PyObject *di_current; + PyObject *di_result; /* reusable result tuple for iteritems */ +} odictiterobject; + +static void +odictiter_dealloc(odictiterobject *di) +{ + _PyObject_GC_UNTRACK(di); + Py_DECREF(di->di_odict); + Py_XDECREF(di->di_current); + if (di->kind & (_odict_ITER_KEYS | _odict_ITER_VALUES)) { + Py_DECREF(di->di_result); + } + PyObject_GC_Del(di); +} + +static int +odictiter_traverse(odictiterobject *di, visitproc visit, void *arg) +{ + Py_VISIT(di->di_odict); + Py_VISIT(di->di_current); /* A key could be any type, not just str. */ + Py_VISIT(di->di_result); + return 0; +} + +static PyObject * +odictiter_nextkey(odictiterobject *di) +{ + PyObject *key; + _ODictNode *node; + int reversed = di->kind & _odict_ITER_REVERSED; + + /* Get the key. */ + if (di->di_current == NULL) + return NULL; + node = _odict_find_node(di->di_odict, di->di_current); + if (node == NULL) { + /* Must have been deleted. */ + Py_DECREF(di->di_current); + di->di_current = NULL; + return NULL; + } + key = di->di_current; + + /* Advance to the next key. */ + node = reversed ? _odictnode_PREV(node) : _odictnode_NEXT(node); + if (node == NULL) { + /* Reached the end. */ + di->di_current = NULL; + } + else { + di->di_current = _odictnode_KEY(node); + Py_INCREF(di->di_current); + } + + return key; +} + +static PyObject * +odictiter_iternext(odictiterobject *di) +{ + PyObject *value; + PyObject *key = odictiter_nextkey(di); /* new reference */ + + if (key == NULL) + return NULL; + + /* Handle the keys case. */ + if (! (di->kind & _odict_ITER_VALUES)) { + return key; + } + + /* Handle the items case. */ + if (di->kind & _odict_ITER_KEYS) { + PyObject *result = di->di_result; + + value = PyODict_GetItem((PyObject *)di->di_odict, key); /* borrowed */ + + if (result->ob_refcnt == 1) { + /* not in use so we can reuse it + * (the common case during iteration) */ + Py_INCREF(result); + Py_DECREF(PyTuple_GET_ITEM(result, 0)); /* borrowed */ + Py_DECREF(PyTuple_GET_ITEM(result, 1)); /* borrowed */ + } + else { + result = PyTuple_New(2); + if (result == NULL) + return NULL; + } + + Py_INCREF(value); + PyTuple_SET_ITEM(result, 0, key); /* steals reference */ + PyTuple_SET_ITEM(result, 1, value); /* steals reference */ + + return result; + } + /* Handle the values case. */ + else { + value = PyODict_GetItem((PyObject *)di->di_odict, key); + Py_XINCREF(value); + Py_DECREF(key); + return value; + } +} + +/* No need for tp_clear because odictiterobject is not mutable. */ + +PyDoc_STRVAR(reduce_doc, "Return state information for pickling"); + +static PyObject * +odictiter_reduce(odictiterobject *di) +{ + PyObject *list; + + list = PyList_New(0); + if (!list) + return NULL; + + /* iterate the temporary into a list */ + for(;;) { + PyObject *element = odictiter_iternext(di); + if (element) { + if (PyList_Append(list, element)) { + Py_DECREF(element); + Py_DECREF(list); + return NULL; + } + Py_DECREF(element); + } + else { + /* done iterating? */ + break; + } + } + if (PyErr_Occurred()) { + Py_DECREF(list); + return NULL; + } + return Py_BuildValue("N(N)", _PyObject_GetBuiltin("iter"), list); +} + +static PyMethodDef odictiter_methods[] = { + {"__reduce__", (PyCFunction)odictiter_reduce, METH_NOARGS, reduce_doc}, + {NULL, NULL} /* sentinel */ +}; + +PyTypeObject PyODictIter_Type = { + PyVarObject_HEAD_INIT(&PyType_Type, 0) + "odict_iterator", /* tp_name */ + sizeof(odictiterobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)odictiter_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_reserved */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */ + 0, /* tp_doc */ + (traverseproc)odictiter_traverse, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + PyObject_SelfIter, /* tp_iter */ + (iternextfunc)odictiter_iternext, /* tp_iternext */ + odictiter_methods, /* tp_methods */ + 0, +}; + +static PyObject * +odictiter_new(PyODictObject *od, int kind) +{ + odictiterobject *di; + _ODictNode *node; + int reversed = kind & _odict_ITER_REVERSED; + + di = PyObject_GC_New(odictiterobject, &PyODictIter_Type); + if (di == NULL) + return NULL; + + if (kind & (_odict_ITER_KEYS | _odict_ITER_VALUES)){ + di->di_result = PyTuple_Pack(2, Py_None, Py_None); + if (di->di_result == NULL) { + Py_DECREF(di); + return NULL; + } + } + else + di->di_result = NULL; + + di->kind = kind; + node = reversed ? _odict_LAST(od) : _odict_FIRST(od); + di->di_current = node ? _odictnode_KEY(node) : NULL; + Py_XINCREF(di->di_current); + di->di_odict = od; + Py_INCREF(od); + + _PyObject_GC_TRACK(di); + return (PyObject *)di; +} + +/* keys() */ + +static PyObject * +odictkeys_iter(_PyDictViewObject *dv) +{ + if (dv->dv_dict == NULL) { + Py_RETURN_NONE; + } + return odictiter_new((PyODictObject *)dv->dv_dict, + _odict_ITER_KEYS); +} + +static PyObject * +odictkeys_reversed(_PyDictViewObject *dv) +{ + if (dv->dv_dict == NULL) { + Py_RETURN_NONE; + } + return odictiter_new((PyODictObject *)dv->dv_dict, + _odict_ITER_KEYS|_odict_ITER_REVERSED); +} + +static PyMethodDef odictkeys_methods[] = { + {"__reversed__", (PyCFunction)odictkeys_reversed, METH_NOARGS, NULL}, + {NULL, NULL} /* sentinel */ +}; + +PyTypeObject PyODictKeys_Type = { + PyVarObject_HEAD_INIT(&PyType_Type, 0) + "odict_keys", /* tp_name */ + 0, /* tp_basicsize */ + 0, /* tp_itemsize */ + 0, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_reserved */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + 0, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + 0, /* tp_flags */ + 0, /* tp_doc */ + 0, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)odictkeys_iter, /* tp_iter */ + 0, /* tp_iternext */ + odictkeys_methods, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + &PyDictKeys_Type, /* tp_base */ +}; + +static PyObject * +odictkeys_new(PyObject *od) +{ + return _PyDictView_New(od, &PyODictKeys_Type); +} + +/* items() */ + +static PyObject * +odictitems_iter(_PyDictViewObject *dv) +{ + if (dv->dv_dict == NULL) { + Py_RETURN_NONE; + } + return odictiter_new((PyODictObject *)dv->dv_dict, + _odict_ITER_KEYS|_odict_ITER_VALUES); +} + +static PyObject * +odictitems_reversed(_PyDictViewObject *dv) +{ + if (dv->dv_dict == NULL) { + Py_RETURN_NONE; + } + return odictiter_new((PyODictObject *)dv->dv_dict, + _odict_ITER_KEYS|_odict_ITER_VALUES|_odict_ITER_REVERSED); +} + +static PyMethodDef odictitems_methods[] = { + {"__reversed__", (PyCFunction)odictitems_reversed, METH_NOARGS, NULL}, + {NULL, NULL} /* sentinel */ +}; + +PyTypeObject PyODictItems_Type = { + PyVarObject_HEAD_INIT(&PyType_Type, 0) + "odict_items", /* tp_name */ + 0, /* tp_basicsize */ + 0, /* tp_itemsize */ + 0, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_reserved */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + 0, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + 0, /* tp_flags */ + 0, /* tp_doc */ + 0, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)odictitems_iter, /* tp_iter */ + 0, /* tp_iternext */ + odictitems_methods, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + &PyDictItems_Type, /* tp_base */ +}; + +static PyObject * +odictitems_new(PyObject *od) +{ + return _PyDictView_New(od, &PyODictItems_Type); +} + +/* values() */ + +static PyObject * +odictvalues_iter(_PyDictViewObject *dv) +{ + if (dv->dv_dict == NULL) { + Py_RETURN_NONE; + } + return odictiter_new((PyODictObject *)dv->dv_dict, + _odict_ITER_VALUES); +} + +static PyObject * +odictvalues_reversed(_PyDictViewObject *dv) +{ + if (dv->dv_dict == NULL) { + Py_RETURN_NONE; + } + return odictiter_new((PyODictObject *)dv->dv_dict, + _odict_ITER_VALUES|_odict_ITER_REVERSED); +} + +static PyMethodDef odictvalues_methods[] = { + {"__reversed__", (PyCFunction)odictvalues_reversed, METH_NOARGS, NULL}, + {NULL, NULL} /* sentinel */ +}; + +PyTypeObject PyODictValues_Type = { + PyVarObject_HEAD_INIT(&PyType_Type, 0) + "odict_values", /* tp_name */ + 0, /* tp_basicsize */ + 0, /* tp_itemsize */ + 0, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_reserved */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + 0, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + 0, /* tp_flags */ + 0, /* tp_doc */ + 0, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)odictvalues_iter, /* tp_iter */ + 0, /* tp_iternext */ + odictvalues_methods, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + &PyDictValues_Type, /* tp_base */ +}; + +static PyObject * +odictvalues_new(PyObject *od) +{ + return _PyDictView_New(od, &PyODictValues_Type); +} + + +/* ---------------------------------------------- + MutableMappping implementations + +Mapping: + +============ =========== +method uses +============ =========== +__contains__ __getitem__ +__eq__ items +__getitem__ + +__iter__ + +__len__ + +__ne__ __eq__ +get __getitem__ +items ItemsView +keys KeysView +values ValuesView +============ =========== + +ItemsView uses __len__, __iter__, and __getitem__. +KeysView uses __len__, __iter__, and __contains__. +ValuesView uses __len__, __iter__, and __getitem__. + +MutableMapping: + +============ =========== +method uses +============ =========== +__delitem__ + +__setitem__ + +clear popitem +pop __getitem__ + __delitem__ +popitem __iter__ + _getitem__ + __delitem__ +setdefault __getitem__ + __setitem__ +update __setitem__ +============ =========== +*/ + +static int +mutablemapping_add_pairs(PyObject *self, PyObject *pairs) +{ + PyObject *pair, *iterator, *unexpected; + int res = 0; + + iterator = PyObject_GetIter(pairs); + if (iterator == NULL) + return -1; + PyErr_Clear(); + + while ((pair = PyIter_Next(iterator)) != NULL) { + /* could be more efficient (see UNPACK_SEQUENCE in ceval.c) */ + PyObject * key, *value = NULL; + PyObject *pair_iterator = PyObject_GetIter(pair); + + key = PyIter_Next(pair_iterator); + if (key == NULL) { + if (!PyErr_Occurred()) + PyErr_SetString(PyExc_ValueError, + "need more than 0 values to unpack"); + goto Done; + } + + value = PyIter_Next(pair_iterator); + if (value == NULL) { + if (!PyErr_Occurred()) + PyErr_SetString(PyExc_ValueError, + "need more than 1 value to unpack"); + goto Done; + } + + unexpected = PyIter_Next(pair_iterator); + if (unexpected != NULL) { + Py_DECREF(unexpected); + PyErr_SetString(PyExc_ValueError, + "too many values to unpack (expected 2)"); + goto Done; + } + else if (PyErr_Occurred()) + goto Done; + + res = PyObject_SetItem(self, key, value); + +Done: + Py_DECREF(pair); + Py_DECREF(pair_iterator); + Py_XDECREF(key); + Py_XDECREF(value); + if (PyErr_Occurred()) + break; + } + Py_DECREF(iterator); + + if (res < 0 || PyErr_Occurred() != NULL) + return -1; + else + return 0; +} + +static PyObject * +mutablemapping_update(PyObject *self, PyObject *args, PyObject *kwargs) +{ + int res = 0; + Py_ssize_t len = (args != NULL) ? PyObject_Size(args) : 0; + + /* first handle args, if any */ + if (len < 0) + return NULL; + else if (len > 1) { + char *msg = "update() takes at most 1 positional argument (%d given)"; + PyErr_Format(PyExc_TypeError, msg, len); + return NULL; + } + else if (len == 1) { + PyObject *other = PyTuple_GET_ITEM(args, 0); /* borrowed reference */ + if (other == NULL) + return NULL; + Py_INCREF(other); + if (PyObject_HasAttrString(other, "items")) { + PyObject *items = PyMapping_Items(other); + Py_DECREF(other); + if (items == NULL) + return NULL; + res = mutablemapping_add_pairs(self, items); + Py_DECREF(items); + if (res == -1) + return NULL; + } + else if (PyObject_HasAttrString(other, "keys")) { + PyObject *keys, *iterator, *key; + keys = PyObject_CallMethod(other, "keys", NULL); + Py_DECREF(other); + if (keys == NULL) + return NULL; + iterator = PyObject_GetIter(keys); + Py_DECREF(keys); + if (iterator == NULL) + return NULL; + while (res == 0 && (key = PyIter_Next(iterator))) { + PyObject *value = PyObject_GetItem(other, key); + if (value != NULL) { + res = PyObject_SetItem(self, key, value); + Py_DECREF(value); + } + else { + res = -1; + } + Py_DECREF(key); + } + Py_DECREF(iterator); + if (res != 0 || PyErr_Occurred()) + return NULL; + } + else { + res = mutablemapping_add_pairs(self, other); + Py_DECREF(other); + if (res != 0) + return NULL; + } + } + + /* now handle kwargs */ + len = (kwargs != NULL) ? PyObject_Size(kwargs) : 0; + if (len < 0) + return NULL; + else if (len > 0) { + PyObject *items; + if (!PyMapping_Check(kwargs)) { + PyErr_SetString(PyExc_TypeError, "expected mapping for kwargs"); + return NULL; + } + items = PyMapping_Items(kwargs); + if (items == NULL) + return NULL; + res = mutablemapping_add_pairs(self, items); + Py_DECREF(items); + if (res == -1) + return NULL; + } + + Py_RETURN_NONE; +} |