From 1202a4733e6ffbf3149425aae14f7c4eeeb115c0 Mon Sep 17 00:00:00 2001
From: Raymond Hettinger <python@rcn.com>
Date: Sun, 18 Jan 2015 13:12:42 -0800
Subject: Issue 23261:  Clean-up the hack to store the set.pop() search finger
 in a hash field instead of the setobject.

---
 Include/setobject.h  |  5 ++---
 Lib/test/test_sys.py |  2 +-
 Objects/setobject.c  | 33 ++++++++++++---------------------
 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) {
-- 
cgit v0.12