From a5ebbf6295fef4e9033774f5c711a53407d766c9 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Mon, 26 Jan 2015 21:54:35 -0800 Subject: Remove unneeded dummy test from the set search loop (when the hashes match we know the key is not a dummy). --- 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 index a8b8d33..bb5316f 100644 --- a/Include/setobject.h +++ b/Include/setobject.h @@ -14,7 +14,10 @@ extern "C" { 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 index dc33a34..673490d 100644 --- a/Objects/setobject.c +++ b/Objects/setobject.c @@ -65,8 +65,10 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) 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 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) 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 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) 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; -- cgit v0.12