[Python-checkins] cpython: Remove unneeded dummy test from the set search loop (when the hashes match we

[raymond.hettinger]

https://hg.python.org/cpython/rev/ed8cc03eed9c
changeset:   94333:ed8cc03eed9c
user:        Raymond Hettinger <python at rcn.com>
date:        Mon Jan 26 21:54:35 2015 -0800
summary:
  Remove unneeded dummy test from the set search loop (when the hashes match we know the key is not a dummy).

files:
  Include/setobject.h |   5 ++++-
  Objects/setobject.c |  15 +++++++++++----
  2 files changed, 15 insertions(+), 5 deletions(-)


diff --git a/Include/setobject.h b/Include/setobject.h
--- a/Include/setobject.h
+++ b/Include/setobject.h
@@ -14,7 +14,10 @@
 2. Active:  key != NULL and key != dummy
 3. Dummy:   key == dummy
 
-The hash field of Unused or Dummy slots have no meaning.
+The hash field of Unused slots have no meaning.
+The hash field of Dummny slots are set to -1
+meaning that dummy entries can be detected by
+either entry->key==dummy or by entry->hash==-1.
 */
 
 #define PySet_MINSIZE 8
diff --git a/Objects/setobject.c b/Objects/setobject.c
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -65,8 +65,10 @@
         return entry;
 
     while (1) {
-        if (entry->hash == hash && entry->key != dummy) {         /* dummy match unlikely */
+        if (entry->hash == hash) {
             PyObject *startkey = entry->key;
+            /* startkey cannot be a dummy because the dummy hash field is -1 */
+            assert(startkey != dummy);
             if (startkey == key)
                 return entry;
             if (PyUnicode_CheckExact(startkey)
@@ -83,15 +85,18 @@
             if (cmp > 0)                                          /* likely */
                 return entry;
         }
-        if (entry->key == dummy && freeslot == NULL)
+        if (entry->hash == -1 && freeslot == NULL) {
+            assert(entry->key == dummy);
             freeslot = entry;
+        }
 
         for (j = 1 ; j <= LINEAR_PROBES ; j++) {
             entry = &table[(i + j) & mask];
             if (entry->key == NULL)
                 goto found_null;
-            if (entry->hash == hash && entry->key != dummy) {
+            if (entry->hash == hash) {
                 PyObject *startkey = entry->key;
+                assert(startkey != dummy);
                 if (startkey == key)
                     return entry;
                 if (PyUnicode_CheckExact(startkey)
@@ -108,8 +113,10 @@
                 if (cmp > 0)
                     return entry;
             }
-            if (entry->key == dummy && freeslot == NULL)
+            if (entry->hash == -1 && freeslot == NULL) {
+                assert(entry->key == dummy);
                 freeslot = entry;
+            }
         }
 
         perturb >>= PERTURB_SHIFT;

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