[Python-checkins] bpo-27275: Change popitem() and pop() methods of collections.OrderedDict (GH-27530)
ambv
webhook-mailer at python.org
Tue Aug 3 07:01:31 EDT 2021
https://github.com/python/cpython/commit/8c9f847997196aa76500d1ae104cbe7fe2a467ed
commit: 8c9f847997196aa76500d1ae104cbe7fe2a467ed
branch: main
author: Serhiy Storchaka <storchaka at gmail.com>
committer: ambv <lukasz at langa.pl>
date: 2021-08-03T13:00:55+02:00
summary:
bpo-27275: Change popitem() and pop() methods of collections.OrderedDict (GH-27530)
* Unify the C and Python implementations of OrderedDict.popitem().
The C implementation no longer calls ``__getitem__`` and ``__delitem__``
methods of the OrderedDict subclasses.
* Change popitem() and pop() methods of collections.OrderedDict
For consistency with dict both implementations (pure Python and C)
of these methods in OrderedDict no longer call __getitem__ and
__delitem__ methods of the OrderedDict subclasses.
Previously only the Python implementation of popitem() did not
call them.
files:
A Misc/NEWS.d/next/Library/2021-08-01-19-49-09.bpo-27275.QsvE0k.rst
M Lib/collections/__init__.py
M Lib/test/test_ordered_dict.py
M Objects/odictobject.c
diff --git a/Lib/collections/__init__.py b/Lib/collections/__init__.py
index bae0805d6686c5..d989d85d6d8293 100644
--- a/Lib/collections/__init__.py
+++ b/Lib/collections/__init__.py
@@ -236,11 +236,19 @@ def pop(self, key, default=__marker):
is raised.
'''
- if key in self:
- result = self[key]
- del self[key]
+ marker = self.__marker
+ result = dict.pop(self, key, marker)
+ if result is not marker:
+ # The same as in __delitem__().
+ link = self.__map.pop(key)
+ link_prev = link.prev
+ link_next = link.next
+ link_prev.next = link_next
+ link_next.prev = link_prev
+ link.prev = None
+ link.next = None
return result
- if default is self.__marker:
+ if default is marker:
raise KeyError(key)
return default
diff --git a/Lib/test/test_ordered_dict.py b/Lib/test/test_ordered_dict.py
index d48edb5881a14d..d51296a2d12441 100644
--- a/Lib/test/test_ordered_dict.py
+++ b/Lib/test/test_ordered_dict.py
@@ -896,5 +896,88 @@ def test_popitem(self):
self.assertRaises(KeyError, d.popitem)
+class SimpleLRUCache:
+
+ def __init__(self, size):
+ super().__init__()
+ self.size = size
+ self.counts = dict.fromkeys(('get', 'set', 'del'), 0)
+
+ def __getitem__(self, item):
+ self.counts['get'] += 1
+ value = super().__getitem__(item)
+ self.move_to_end(item)
+ return value
+
+ def __setitem__(self, key, value):
+ self.counts['set'] += 1
+ while key not in self and len(self) >= self.size:
+ self.popitem(last=False)
+ super().__setitem__(key, value)
+ self.move_to_end(key)
+
+ def __delitem__(self, key):
+ self.counts['del'] += 1
+ super().__delitem__(key)
+
+
+class SimpleLRUCacheTests:
+
+ def test_add_after_full(self):
+ c = self.type2test(2)
+ c['t1'] = 1
+ c['t2'] = 2
+ c['t3'] = 3
+ self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
+ self.assertEqual(list(c), ['t2', 't3'])
+ self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
+
+ def test_popitem(self):
+ c = self.type2test(3)
+ for i in range(1, 4):
+ c[i] = i
+ self.assertEqual(c.popitem(last=False), (1, 1))
+ self.assertEqual(c.popitem(last=True), (3, 3))
+ self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
+
+ def test_pop(self):
+ c = self.type2test(3)
+ for i in range(1, 4):
+ c[i] = i
+ self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
+ self.assertEqual(c.pop(2), 2)
+ self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
+ self.assertEqual(c.pop(4, 0), 0)
+ self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
+ self.assertRaises(KeyError, c.pop, 4)
+ self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
+
+ def test_change_order_on_get(self):
+ c = self.type2test(3)
+ for i in range(1, 4):
+ c[i] = i
+ self.assertEqual(list(c), list(range(1, 4)))
+ self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
+ self.assertEqual(c[2], 2)
+ self.assertEqual(c.counts, {'get': 1, 'set': 3, 'del': 0})
+ self.assertEqual(list(c), [1, 3, 2])
+
+
+class PySimpleLRUCacheTests(SimpleLRUCacheTests, unittest.TestCase):
+
+ class type2test(SimpleLRUCache, py_coll.OrderedDict):
+ pass
+
+
+ at unittest.skipUnless(c_coll, 'requires the C version of the collections module')
+class CSimpleLRUCacheTests(SimpleLRUCacheTests, unittest.TestCase):
+
+ @classmethod
+ def setUpClass(cls):
+ class type2test(SimpleLRUCache, c_coll.OrderedDict):
+ pass
+ cls.type2test = type2test
+
+
if __name__ == "__main__":
unittest.main()
diff --git a/Misc/NEWS.d/next/Library/2021-08-01-19-49-09.bpo-27275.QsvE0k.rst b/Misc/NEWS.d/next/Library/2021-08-01-19-49-09.bpo-27275.QsvE0k.rst
new file mode 100644
index 00000000000000..1f5afaf4d108e4
--- /dev/null
+++ b/Misc/NEWS.d/next/Library/2021-08-01-19-49-09.bpo-27275.QsvE0k.rst
@@ -0,0 +1,3 @@
+:meth:`collections.OrderedDict.popitem` and :meth:`collections.OrderedDict.pop`
+no longer call ``__getitem__`` and ``__delitem__`` methods of the OrderedDict
+subclasses.
diff --git a/Objects/odictobject.c b/Objects/odictobject.c
index fb1ac0ce48dcfc..e5361da6dcdedb 100644
--- a/Objects/odictobject.c
+++ b/Objects/odictobject.c
@@ -1047,81 +1047,26 @@ OrderedDict_setdefault_impl(PyODictObject *self, PyObject *key,
/* pop() */
-/* forward */
-static PyObject * _odict_popkey(PyObject *, PyObject *, PyObject *);
-
-/* Skips __missing__() calls. */
-/*[clinic input]
-OrderedDict.pop
-
- key: object
- default: object = NULL
-
-od.pop(key[,default]) -> v, remove specified key and return the corresponding value.
-
-If the key is not found, return the default if given; otherwise,
-raise a KeyError.
-[clinic start generated code]*/
-
-static PyObject *
-OrderedDict_pop_impl(PyODictObject *self, PyObject *key,
- PyObject *default_value)
-/*[clinic end generated code: output=7a6447d104e7494b input=7efe36601007dff7]*/
-{
- return _odict_popkey((PyObject *)self, key, default_value);
-}
-
static PyObject *
_odict_popkey_hash(PyObject *od, PyObject *key, PyObject *failobj,
Py_hash_t hash)
{
- _ODictNode *node;
PyObject *value = NULL;
- /* 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_hash((PyODictObject *)od, key, hash);
- if (node == NULL) {
- if (PyErr_Occurred())
- return NULL;
- }
- else {
+ _ODictNode *node = _odict_find_node_hash((PyODictObject *)od, key, hash);
+ if (node != NULL) {
+ /* Pop the node first to avoid a possible dict resize (due to
+ eval loop reentrancy) and complications due to hash collision
+ resolution. */
int res = _odict_clear_node((PyODictObject *)od, node, key, hash);
if (res < 0) {
return NULL;
}
+ /* Now delete the value from the dict. */
+ value = _PyDict_Pop_KnownHash(od, key, hash, failobj);
}
-
- /* Now delete the value from the dict. */
- if (PyODict_CheckExact(od)) {
- if (node != NULL) {
- value = _PyDict_GetItem_KnownHash(od, key, hash); /* borrowed */
- if (value != NULL) {
- Py_INCREF(value);
- if (_PyDict_DelItem_KnownHash(od, key, hash) < 0) {
- Py_DECREF(value);
- return NULL;
- }
- }
- }
- }
- else {
- int exists = PySequence_Contains(od, key);
- if (exists < 0)
- return NULL;
- if (exists) {
- value = PyObject_GetItem(od, key);
- if (value != NULL) {
- if (PyObject_DelItem(od, key) == -1) {
- Py_CLEAR(value);
- }
- }
- }
- }
-
- /* Apply the fallback value, if necessary. */
- if (value == NULL && !PyErr_Occurred()) {
+ else if (value == NULL && !PyErr_Occurred()) {
+ /* Apply the fallback value, if necessary. */
if (failobj) {
value = failobj;
Py_INCREF(failobj);
@@ -1134,14 +1079,28 @@ _odict_popkey_hash(PyObject *od, PyObject *key, PyObject *failobj,
return value;
}
+/* Skips __missing__() calls. */
+/*[clinic input]
+OrderedDict.pop
+
+ key: object
+ default: object = NULL
+
+od.pop(key[,default]) -> v, remove specified key and return the corresponding value.
+
+If the key is not found, return the default if given; otherwise,
+raise a KeyError.
+[clinic start generated code]*/
+
static PyObject *
-_odict_popkey(PyObject *od, PyObject *key, PyObject *failobj)
+OrderedDict_pop_impl(PyODictObject *self, PyObject *key,
+ PyObject *default_value)
+/*[clinic end generated code: output=7a6447d104e7494b input=7efe36601007dff7]*/
{
Py_hash_t hash = PyObject_Hash(key);
if (hash == -1)
return NULL;
-
- return _odict_popkey_hash(od, key, failobj, hash);
+ return _odict_popkey_hash((PyObject *)self, key, default_value, hash);
}
More information about the Python-checkins
mailing list