summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRaymond Hettinger <python@rcn.com>2015-01-18 21:12:42 (GMT)
committerRaymond Hettinger <python@rcn.com>2015-01-18 21:12:42 (GMT)
commit1202a4733e6ffbf3149425aae14f7c4eeeb115c0 (patch)
treed0c2393c496b6df4b26ab1ee8606dcc70b8578f1
parenta556af77a7853cf198011eaa5a3258751d72853f (diff)
downloadcpython-1202a4733e6ffbf3149425aae14f7c4eeeb115c0.zip
cpython-1202a4733e6ffbf3149425aae14f7c4eeeb115c0.tar.gz
cpython-1202a4733e6ffbf3149425aae14f7c4eeeb115c0.tar.bz2
Issue 23261: Clean-up the hack to store the set.pop() search finger in a hash field instead of the setobject.
-rw-r--r--Include/setobject.h5
-rw-r--r--Lib/test/test_sys.py2
-rw-r--r--Objects/setobject.c33
3 files changed, 15 insertions, 25 deletions
diff --git a/Include/setobject.h b/Include/setobject.h
index 8f8e34f..79124d0 100644
--- a/Include/setobject.h
+++ b/Include/setobject.h
@@ -14,9 +14,7 @@ extern "C" {
2. Active: key != NULL and key != dummy
3. Dummy: key == dummy
-Note: .pop() abuses the hash field of an Unused or Dummy slot to
-hold a search finger. The hash field of Unused or Dummy slots has
-no meaning otherwise.
+The hash field of Unused or Dummy slots have no meaning.
*/
#define PySet_MINSIZE 8
@@ -59,6 +57,7 @@ typedef struct _setobject {
Py_hash_t hash; /* Only used by frozenset objects */
setentry smalltable[PySet_MINSIZE];
+ Py_ssize_t finger; /* Search finger for pop() */
PyObject *weakreflist; /* List of weak references */
} PySetObject;
diff --git a/Lib/test/test_sys.py b/Lib/test/test_sys.py
index ec2eaf3..2da987f 100644
--- a/Lib/test/test_sys.py
+++ b/Lib/test/test_sys.py
@@ -994,7 +994,7 @@ class SizeofTest(unittest.TestCase):
# frozenset
PySet_MINSIZE = 8
samples = [[], range(10), range(50)]
- s = size('3n2P' + PySet_MINSIZE*'nP' + 'nP')
+ s = size('3n2P' + PySet_MINSIZE*'nP' + '2nP')
for sample in samples:
minused = len(sample)
if minused == 0: tmp = 1
diff --git a/Objects/setobject.c b/Objects/setobject.c
index 4fba897..9dc88c8 100644
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -668,32 +668,22 @@ set_pop(PySetObject *so)
return NULL;
}
- /* Set entry to "the first" unused or dummy set entry. We abuse
- * the hash field of slot 0 to hold a search finger:
- * If slot 0 has a value, use slot 0.
- * Else slot 0 is being used to hold a search finger,
- * and we use its hash value as the first index to look.
+ i = so->finger;
+ /* This may be a legit search finger, or it may be a once legit
+ * search finger that's out of bounds now (due to wrapping or
+ * resizing). We simply make sure it's in bounds now.
*/
- entry = &so->table[0];
- if (entry->key == NULL || entry->key == dummy) {
- i = entry->hash;
- /* The hash field may be a real hash value, or it may be a
- * legit search finger, or it may be a once-legit search
- * finger that's out of bounds now because it wrapped around
- * or the table shrunk -- simply make sure it's in bounds now.
- */
- if (i > so->mask || i < 1)
- i = 1; /* skip slot 0 */
- while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
- i++;
- if (i > so->mask)
- i = 1;
- }
+ if (i > so->mask)
+ i = 0;
+ while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
+ i++;
+ if (i > so->mask)
+ i = 0;
}
key = entry->key;
entry->key = dummy;
so->used--;
- so->table[0].hash = i + 1; /* next place to start */
+ so->finger = i + 1; /* next place to start */
return key;
}
@@ -1012,6 +1002,7 @@ make_new_set(PyTypeObject *type, PyObject *iterable)
so->table = so->smalltable;
so->lookup = set_lookkey_unicode;
so->hash = -1;
+ so->finger = 0;
so->weakreflist = NULL;
if (iterable != NULL) {