summaryrefslogtreecommitdiffstats
path: root/Objects
diff options
context:
space:
mode:
authorRaymond Hettinger <python@rcn.com>2015-01-27 05:33:48 (GMT)
committerRaymond Hettinger <python@rcn.com>2015-01-27 05:33:48 (GMT)
commit3037e84ad14424759298966579dbcce77a212621 (patch)
tree8a72e713241aec0e8c9761d161df70d89362c373 /Objects
parent618e315f9399fe7497e8ba139b9ef7e03357cdb4 (diff)
downloadcpython-3037e84ad14424759298966579dbcce77a212621.zip
cpython-3037e84ad14424759298966579dbcce77a212621.tar.gz
cpython-3037e84ad14424759298966579dbcce77a212621.tar.bz2
Issue #23269: Tighten search_loop in set_insert_clean()
Instead of masking and shifting every loopup, move the wrap-around test outside of the inner-loop.
Diffstat (limited to 'Objects')
-rw-r--r--Objects/setobject.c23
1 files changed, 17 insertions, 6 deletions
diff --git a/Objects/setobject.c b/Objects/setobject.c
index f44f562..dc33a34 100644
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -138,17 +138,28 @@ set_insert_clean(PySetObject *so, PyObject *key, Py_hash_t hash)
setentry *entry;
size_t perturb = hash;
size_t mask = (size_t)so->mask;
- size_t i = (size_t)hash;
+ size_t i = (size_t)hash & mask;
size_t j;
while (1) {
- for (j = 0 ; j <= LINEAR_PROBES ; j++) {
- entry = &table[(i + j) & mask];
- if (entry->key == NULL)
- goto found_null;
+ entry = &table[i];
+ if (entry->key == NULL)
+ goto found_null;
+ if (i + LINEAR_PROBES <= mask) {
+ for (j = 1; j <= LINEAR_PROBES; j++) {
+ entry = &table[i + j];
+ if (entry->key == NULL)
+ goto found_null;
+ }
+ } else {
+ for (j = 1; j <= LINEAR_PROBES; j++) {
+ entry = &table[(i + j) & mask];
+ if (entry->key == NULL)
+ goto found_null;
+ }
}
perturb >>= PERTURB_SHIFT;
- i = i * 5 + 1 + perturb;
+ i = (i * 5 + 1 + perturb) & mask;
}
found_null:
entry->key = key;