https://hg.python.org/cpython/rev/a6a79053aec4 changeset: 104870:a6a79053aec4 parent: 104868:b671422240cd parent: 104869:4e9c7704f373 user: INADA Naoki <songofacandy@gmail.com> date: Wed Nov 02 18:47:24 2016 +0900 summary: Issue #28583: PyDict_SetDefault didn't combine split table when needed. Patch by Xiang Zhang. files: Lib/test/test_dict.py | 17 ++++++++ Misc/NEWS | 3 + Objects/dictobject.c | 60 +++++++++++++++++++++++------- 3 files changed, 65 insertions(+), 15 deletions(-) diff --git a/Lib/test/test_dict.py b/Lib/test/test_dict.py --- a/Lib/test/test_dict.py +++ b/Lib/test/test_dict.py @@ -852,6 +852,23 @@ return dicts @support.cpython_only + def test_splittable_setdefault(self): + """split table must be combined when setdefault() + breaks insertion order""" + a, b = self.make_shared_key_dict(2) + + a['a'] = 1 + size_a = sys.getsizeof(a) + a['b'] = 2 + b.setdefault('b', 2) + size_b = sys.getsizeof(b) + b['a'] = 1 + + self.assertGreater(size_b, size_a) + self.assertEqual(list(a), ['x', 'y', 'z', 'a', 'b']) + self.assertEqual(list(b), ['x', 'y', 'z', 'b', 'a']) + + @support.cpython_only def test_splittable_del(self): """split table must be combined when del d[k]""" a, b = self.make_shared_key_dict(2) diff --git a/Misc/NEWS b/Misc/NEWS --- a/Misc/NEWS +++ b/Misc/NEWS @@ -10,6 +10,9 @@ Core and Builtins ----------------- +- Issue #28583: PyDict_SetDefault didn't combine split table when needed. + Patch by Xiang Zhang. + - Issue #28128: Deprecation warning for invalid str and byte escape sequences now prints better information about where the error occurs. Patch by Serhiy Storchaka and Eric Smith. diff --git a/Objects/dictobject.c b/Objects/dictobject.c --- a/Objects/dictobject.c +++ b/Objects/dictobject.c @@ -2758,58 +2758,88 @@ PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj) { PyDictObject *mp = (PyDictObject *)d; - PyObject *val = NULL; + PyObject *value; Py_hash_t hash; Py_ssize_t hashpos, ix; - PyDictKeyEntry *ep; PyObject **value_addr; if (!PyDict_Check(d)) { PyErr_BadInternalCall(); return NULL; } + if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *) key)->hash) == -1) { hash = PyObject_Hash(key); if (hash == -1) return NULL; } + + if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) { + if (insertion_resize(mp) < 0) + return NULL; + } + ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, &hashpos); if (ix == DKIX_ERROR) return NULL; - if (ix == DKIX_EMPTY || *value_addr == NULL) { - val = defaultobj; + + if (_PyDict_HasSplitTable(mp) && + ((ix >= 0 && *value_addr == NULL && mp->ma_used != ix) || + (ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) { + if (insertion_resize(mp) < 0) { + return NULL; + } + find_empty_slot(mp, key, hash, &value_addr, &hashpos); + ix = DKIX_EMPTY; + } + + if (ix == DKIX_EMPTY) { + PyDictKeyEntry *ep, *ep0; + value = defaultobj; if (mp->ma_keys->dk_usable <= 0) { - /* Need to resize. */ if (insertion_resize(mp) < 0) { return NULL; } find_empty_slot(mp, key, hash, &value_addr, &hashpos); } - ix = mp->ma_keys->dk_nentries; - Py_INCREF(defaultobj); + ep0 = DK_ENTRIES(mp->ma_keys); + ep = &ep0[mp->ma_keys->dk_nentries]; + dk_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries); Py_INCREF(key); - MAINTAIN_TRACKING(mp, key, defaultobj); - dk_set_index(mp->ma_keys, hashpos, ix); - ep = &DK_ENTRIES(mp->ma_keys)[ix]; + Py_INCREF(value); + MAINTAIN_TRACKING(mp, key, value); ep->me_key = key; ep->me_hash = hash; if (mp->ma_values) { - mp->ma_values[ix] = val; + assert(mp->ma_values[mp->ma_keys->dk_nentries] == NULL); + mp->ma_values[mp->ma_keys->dk_nentries] = value; } else { - ep->me_value = val; + ep->me_value = value; } + mp->ma_used++; + mp->ma_version_tag = DICT_NEXT_VERSION(); mp->ma_keys->dk_usable--; mp->ma_keys->dk_nentries++; + assert(mp->ma_keys->dk_usable >= 0); + } + else if (*value_addr == NULL) { + value = defaultobj; + assert(_PyDict_HasSplitTable(mp)); + assert(ix == mp->ma_used); + Py_INCREF(value); + MAINTAIN_TRACKING(mp, key, value); + *value_addr = value; mp->ma_used++; mp->ma_version_tag = DICT_NEXT_VERSION(); - assert(_PyDict_CheckConsistency(mp)); } else { - val = *value_addr; + value = *value_addr; } - return val; + + assert(_PyDict_CheckConsistency(mp)); + return value; } static PyObject * -- Repository URL: https://hg.python.org/cpython