Skip to content

Commit f15d7ce

Browse files
serhiy-storchakaserhiy-storchaka
committed
bpo-27275: Unify the C and Python implementations of OrderedDict.popitem().
The C implementation no longer calls ``__getitem__`` and ``__delitem__`` methods of the OrderedDict subclasses.
1 parent 208a7e9 commit f15d7ce

3 files changed

Lines changed: 134 additions & 60 deletions

File tree

‎Lib/test/test_ordered_dict.py‎

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -896,5 +896,88 @@ def test_popitem(self):
896896
self.assertRaises(KeyError, d.popitem)
897897

898898

899+
class SimpleLRUCache:
900+
901+
def __init__(self, size):
902+
super().__init__()
903+
self.size = size
904+
self.counts = dict.fromkeys(('get', 'set', 'del'), 0)
905+
906+
def __getitem__(self, item):
907+
self.counts['get'] += 1
908+
value = super().__getitem__(item)
909+
self.move_to_end(item)
910+
return value
911+
912+
def __setitem__(self, key, value):
913+
self.counts['set'] += 1
914+
while key not in self and len(self) >= self.size:
915+
self.popitem(last=False)
916+
super().__setitem__(key, value)
917+
self.move_to_end(key)
918+
919+
def __delitem__(self, key):
920+
self.counts['del'] += 1
921+
super().__delitem__(key)
922+
923+
924+
class SimpleLRUCacheTests:
925+
926+
def test_add_after_full(self):
927+
c = self.type2test(2)
928+
c['t1'] = 1
929+
c['t2'] = 2
930+
c['t3'] = 3
931+
self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
932+
self.assertEqual(list(c), ['t2', 't3'])
933+
self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
934+
935+
def test_popitem(self):
936+
c = self.type2test(3)
937+
for i in range(1, 4):
938+
c[i] = i
939+
self.assertEqual(c.popitem(last=False), (1, 1))
940+
self.assertEqual(c.popitem(last=True), (3, 3))
941+
self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
942+
943+
def test_pop(self):
944+
c = self.type2test(3)
945+
for i in range(1, 4):
946+
c[i] = i
947+
self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
948+
self.assertEqual(c.pop(2), 2)
949+
self.assertEqual(c.counts, {'get': 1, 'set': 3, 'del': 1})
950+
self.assertEqual(c.pop(4, 0), 0)
951+
self.assertEqual(c.counts, {'get': 1, 'set': 3, 'del': 1})
952+
self.assertRaises(KeyError, c.pop, 4)
953+
self.assertEqual(c.counts, {'get': 1, 'set': 3, 'del': 1})
954+
955+
def test_change_order_on_get(self):
956+
c = self.type2test(3)
957+
for i in range(1, 4):
958+
c[i] = i
959+
self.assertEqual(list(c), list(range(1, 4)))
960+
self.assertEqual(c.counts, {'get': 0, 'set': 3, 'del': 0})
961+
self.assertEqual(c[2], 2)
962+
self.assertEqual(c.counts, {'get': 1, 'set': 3, 'del': 0})
963+
self.assertEqual(list(c), [1, 3, 2])
964+
965+
966+
class PySimpleLRUCacheTests(SimpleLRUCacheTests, unittest.TestCase):
967+
968+
class type2test(SimpleLRUCache, py_coll.OrderedDict):
969+
pass
970+
971+
972+
@unittest.skipUnless(c_coll, 'requires the C version of the collections module')
973+
class CSimpleLRUCacheTests(SimpleLRUCacheTests, unittest.TestCase):
974+
975+
@classmethod
976+
def setUpClass(cls):
977+
class type2test(SimpleLRUCache, c_coll.OrderedDict):
978+
pass
979+
cls.type2test = type2test
980+
981+
899982
if __name__ == "__main__":
900983
unittest.main()

‎Misc/NEWS.d/next/Library/2021-08-01-19-49-09.bpo-27275.QsvE0k.rst‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
Make the C implementation of :meth:`collections.OrderedDict.popitem` in
2+
conform with the pure Python implementation. It no longer calls
3+
``__getitem__`` and ``__delitem__`` methods of the OrderedDict subclasses.

‎Objects/odictobject.c‎

Lines changed: 48 additions & 60 deletions
Original file line numberDiff line numberDiff line change
@@ -1047,8 +1047,37 @@ OrderedDict_setdefault_impl(PyODictObject *self, PyObject *key,
10471047

10481048
/* pop() */
10491049

1050-
/* forward */
1051-
static PyObject * _odict_popkey(PyObject *, PyObject *, PyObject *);
1050+
static PyObject *
1051+
_odict_popkey_hash(PyObject *od, PyObject *key, PyObject *failobj,
1052+
Py_hash_t hash)
1053+
{
1054+
PyObject *value = NULL;
1055+
1056+
_ODictNode *node = _odict_find_node_hash((PyODictObject *)od, key, hash);
1057+
if (node != NULL) {
1058+
/* Pop the node first to avoid a possible dict resize (due to
1059+
eval loop reentrancy) and complications due to hash collision
1060+
resolution. */
1061+
int res = _odict_clear_node((PyODictObject *)od, node, key, hash);
1062+
if (res < 0) {
1063+
return NULL;
1064+
}
1065+
/* Now delete the value from the dict. */
1066+
value = _PyDict_Pop_KnownHash(od, key, hash, failobj);
1067+
}
1068+
else if (value == NULL && !PyErr_Occurred()) {
1069+
/* Apply the fallback value, if necessary. */
1070+
if (failobj) {
1071+
value = failobj;
1072+
Py_INCREF(failobj);
1073+
}
1074+
else {
1075+
PyErr_SetObject(PyExc_KeyError, key);
1076+
}
1077+
}
1078+
1079+
return value;
1080+
}
10521081

10531082
/* Skips __missing__() calls. */
10541083
/*[clinic input]
@@ -1068,63 +1097,32 @@ OrderedDict_pop_impl(PyODictObject *self, PyObject *key,
10681097
PyObject *default_value)
10691098
/*[clinic end generated code: output=7a6447d104e7494b input=7efe36601007dff7]*/
10701099
{
1071-
return _odict_popkey((PyObject *)self, key, default_value);
1072-
}
1073-
1074-
static PyObject *
1075-
_odict_popkey_hash(PyObject *od, PyObject *key, PyObject *failobj,
1076-
Py_hash_t hash)
1077-
{
1078-
_ODictNode *node;
1079-
PyObject *value = NULL;
1080-
1081-
/* Pop the node first to avoid a possible dict resize (due to
1082-
eval loop reentrancy) and complications due to hash collision
1083-
resolution. */
1084-
node = _odict_find_node_hash((PyODictObject *)od, key, hash);
1085-
if (node == NULL) {
1086-
if (PyErr_Occurred())
1087-
return NULL;
1088-
}
1089-
else {
1090-
int res = _odict_clear_node((PyODictObject *)od, node, key, hash);
1091-
if (res < 0) {
1100+
PyObject *od = (PyObject *)self;
1101+
if (PyODict_CheckExact(od)) {
1102+
Py_hash_t hash = PyObject_Hash(key);
1103+
if (hash == -1)
10921104
return NULL;
1093-
}
1105+
return _odict_popkey_hash(od, key, default_value, hash);
10941106
}
10951107

1096-
/* Now delete the value from the dict. */
1097-
if (PyODict_CheckExact(od)) {
1098-
if (node != NULL) {
1099-
value = _PyDict_GetItem_KnownHash(od, key, hash); /* borrowed */
1100-
if (value != NULL) {
1101-
Py_INCREF(value);
1102-
if (_PyDict_DelItem_KnownHash(od, key, hash) < 0) {
1103-
Py_DECREF(value);
1104-
return NULL;
1105-
}
1106-
}
1107-
}
1108-
}
1109-
else {
1110-
int exists = PySequence_Contains(od, key);
1111-
if (exists < 0)
1112-
return NULL;
1113-
if (exists) {
1114-
value = PyObject_GetItem(od, key);
1115-
if (value != NULL) {
1116-
if (PyObject_DelItem(od, key) == -1) {
1117-
Py_CLEAR(value);
1118-
}
1108+
PyObject *value = NULL;
1109+
int exists = PySequence_Contains(od, key);
1110+
if (exists < 0)
1111+
return NULL;
1112+
if (exists) {
1113+
value = PyObject_GetItem(od, key);
1114+
if (value != NULL) {
1115+
if (PyObject_DelItem(od, key) == -1) {
1116+
Py_CLEAR(value);
11191117
}
11201118
}
11211119
}
11221120

11231121
/* Apply the fallback value, if necessary. */
11241122
if (value == NULL && !PyErr_Occurred()) {
1125-
if (failobj) {
1126-
value = failobj;
1127-
Py_INCREF(failobj);
1123+
if (default_value) {
1124+
value = default_value;
1125+
Py_INCREF(default_value);
11281126
}
11291127
else {
11301128
PyErr_SetObject(PyExc_KeyError, key);
@@ -1134,16 +1132,6 @@ _odict_popkey_hash(PyObject *od, PyObject *key, PyObject *failobj,
11341132
return value;
11351133
}
11361134

1137-
static PyObject *
1138-
_odict_popkey(PyObject *od, PyObject *key, PyObject *failobj)
1139-
{
1140-
Py_hash_t hash = PyObject_Hash(key);
1141-
if (hash == -1)
1142-
return NULL;
1143-
1144-
return _odict_popkey_hash(od, key, failobj, hash);
1145-
}
1146-
11471135

11481136
/* popitem() */
11491137

0 commit comments

Comments
 (0)