[Python-checkins] cpython (merge 3.5 -> default): Merge from 3.5 (issue #24667).

Sat Aug 8 01:49:54 CEST 2015

https://hg.python.org/cpython/rev/47287c998bb0
changeset: 97320:47287c998bb0
parent: 97318:2028c413929b
parent: 97319:adb510322c8f
user: Eric Snow <ericsnowcurrently at gmail.com>
date: Fri Aug 07 17:47:35 2015 -0600
summary:
 Merge from 3.5 (issue #24667).
files:
 Lib/test/test_collections.py | 23 +++++++++++++++++++++++
 Misc/NEWS | 2 ++
 Objects/odictobject.c | 17 ++++++++++-------
 3 files changed, 35 insertions(+), 7 deletions(-)

diff --git a/Lib/test/test_collections.py b/Lib/test/test_collections.py
--- a/Lib/test/test_collections.py
+++ b/Lib/test/test_collections.py
@@ -2106,6 +2106,29 @@
 # This should not crash.
 od.popitem()
 
+ def test_issue24667(self):
+ """
+ dict resizes after a certain number of insertion operations,
+ whether or not there were deletions that freed up slots in the
+ hash table. During fast node lookup, OrderedDict must correctly
+ respond to all resizes, even if the current "size" is the same
+ as the old one. We verify that here by forcing a dict resize
+ on a sparse odict and then perform an operation that should
+ trigger an odict resize (e.g. popitem). One key aspect here is
+ that we will keep the size of the odict the same at each popitem
+ call. This verifies that we handled the dict resize properly.
+ """
+ OrderedDict = self.module.OrderedDict
+
+ od = OrderedDict()
+ for c0 in '0123456789ABCDEF':
+ for c1 in '0123456789ABCDEF':
+ if len(od) == 4:
+ # This should not raise a KeyError.
+ od.popitem(last=False)
+ key = c0 + c1
+ od[key] = key
+
 
 class PurePythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
 
diff --git a/Misc/NEWS b/Misc/NEWS
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -10,6 +10,8 @@
 Core and Builtins
 -----------------
 
+- Issue #24667: Resize odict in all cases that the underlying dict resizes.
+
 Library
 -------
 
diff --git a/Objects/odictobject.c b/Objects/odictobject.c
--- a/Objects/odictobject.c
+++ b/Objects/odictobject.c
@@ -483,9 +483,11 @@
 PyDictObject od_dict; /* the underlying dict */
 _ODictNode *od_first; /* first node in the linked list, if any */
 _ODictNode *od_last; /* last node in the linked list, if any */
- /* od_size and od_fast_nodes are managed by _odict_resize() */
- Py_ssize_t od_size; /* hash table that mirrors the dict table */
- _ODictNode **od_fast_nodes; /* managed by _odict_resize() */
+ /* od_fast_nodes and od_resize_sentinel are managed by _odict_resize()
+ * Note that we rely on implementation details of dict for both. */
+ _ODictNode **od_fast_nodes; /* hash table that mirrors the dict table */
+ Py_uintptr_t od_resize_sentinel; /* changes if odict should be resized */
+
 size_t od_state; /* incremented whenever the LL changes */
 PyObject *od_inst_dict; /* OrderedDict().__dict__ */
 PyObject *od_weakreflist; /* holds weakrefs to the odict */
@@ -510,7 +512,6 @@
 /* borrowed reference */
 #define _odictnode_VALUE(node, od) \
 PyODict_GetItemWithError((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)
 
@@ -520,6 +521,7 @@
 #define _odict_FOREACH(od, node) \
 for (node = _odict_FIRST(od); node != NULL; node = _odictnode_NEXT(node))
 
+#define _odict_FAST_SIZE(od) ((PyDictObject *)od)->ma_keys->dk_size
 
 static void
 _odict_free_fast_nodes(PyODictObject *od) {
@@ -573,7 +575,7 @@
 /* Replace the old fast nodes table. */
 _odict_free_fast_nodes(od);
 od->od_fast_nodes = fast_nodes;
- od->od_size = size;
+ od->od_resize_sentinel = (Py_uintptr_t)(((PyDictObject *)od)->ma_keys);
 return 0;
 }
 
@@ -591,7 +593,7 @@
 keys = ((PyDictObject *)od)->ma_keys;
 
 /* Ensure od_fast_nodes and dk_entries are in sync. */
- if (keys->dk_size != od->od_size) {
+ if (od->od_resize_sentinel != (Py_uintptr_t)keys) {
 int resize_res = _odict_resize(od);
 if (resize_res < 0)
 return -1;
@@ -656,6 +658,7 @@
 _odictnode_NEXT(_odict_LAST(od)) = node;
 _odict_LAST(od) = node;
 }
+
 od->od_state++;
 }
 
@@ -980,7 +983,7 @@
 return NULL;
 res += temp;
 
- res += sizeof(_ODictNode) * od->od_size; /* od_fast_nodes */
+ res += sizeof(_ODictNode) * _odict_FAST_SIZE(od); /* od_fast_nodes */
 if (!_odict_EMPTY(od)) {
 res += sizeof(_ODictNode) * PyODict_SIZE(od); /* linked-list */
 }
-- 
Repository URL: https://hg.python.org/cpython
