[Python-checkins] cpython: Issue 23261: Clean-up the hack to store the set.pop() search finger in a hash

[raymond.hettinger]

https://hg.python.org/cpython/rev/0f90a3bd07f7
changeset:   94214:0f90a3bd07f7
user:        Raymond Hettinger <python at rcn.com>
date:        Sun Jan 18 13:12:42 2015 -0800
summary:
  Issue 23261:  Clean-up the hack to store the set.pop() search finger in a hash field instead of the setobject.

files:
  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
--- a/Include/setobject.h
+++ b/Include/setobject.h
@@ -14,9 +14,7 @@
 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 @@
     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
--- a/Lib/test/test_sys.py
+++ b/Lib/test/test_sys.py
@@ -994,7 +994,7 @@
         # 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
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -668,32 +668,22 @@
         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 @@
     so->table = so->smalltable;
     so->lookup = set_lookkey_unicode;
     so->hash = -1;
+    so->finger = 0;
     so->weakreflist = NULL;
 
     if (iterable != NULL) {

-- 
Repository URL: https://hg.python.org/cpython