Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 2cc9b84

Browse filesBrowse files
rhettingerrhettinger
authored
Improve code clarity for the set lookup logic (GH-20028)
1 parent 2fbc57a commit 2cc9b84
Copy full SHA for 2cc9b84

File tree

Expand file treeCollapse file tree

1 file changed

+55
-125
lines changed
Filter options
Expand file treeCollapse file tree

1 file changed

+55
-125
lines changed

‎Objects/setobject.c

Copy file name to clipboardExpand all lines: Objects/setobject.c
+55-125Lines changed: 55 additions & 125 deletions
Original file line numberDiff line numberDiff line change
@@ -57,77 +57,43 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
5757
{
5858
setentry *table;
5959
setentry *entry;
60-
size_t perturb;
60+
size_t perturb = hash;
6161
size_t mask = so->mask;
6262
size_t i = (size_t)hash & mask; /* Unsigned for defined overflow behavior */
63-
size_t j;
63+
int probes;
6464
int cmp;
6565

66-
entry = &so->table[i];
67-
if (entry->key == NULL)
68-
return entry;
69-
70-
perturb = hash;
71-
7266
while (1) {
73-
if (entry->hash == hash) {
74-
PyObject *startkey = entry->key;
75-
/* startkey cannot be a dummy because the dummy hash field is -1 */
76-
assert(startkey != dummy);
77-
if (startkey == key)
78-
return entry;
79-
if (PyUnicode_CheckExact(startkey)
80-
&& PyUnicode_CheckExact(key)
81-
&& _PyUnicode_EQ(startkey, key))
82-
return entry;
83-
table = so->table;
84-
Py_INCREF(startkey);
85-
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
86-
Py_DECREF(startkey);
87-
if (cmp < 0) /* unlikely */
88-
return NULL;
89-
if (table != so->table || entry->key != startkey) /* unlikely */
90-
return set_lookkey(so, key, hash);
91-
if (cmp > 0) /* likely */
67+
entry = &so->table[i];
68+
probes = (i + LINEAR_PROBES <= mask) ? LINEAR_PROBES: 0;
69+
do {
70+
if (entry->hash == 0 && entry->key == NULL)
9271
return entry;
93-
mask = so->mask; /* help avoid a register spill */
94-
}
95-
96-
if (i + LINEAR_PROBES <= mask) {
97-
for (j = 0 ; j < LINEAR_PROBES ; j++) {
98-
entry++;
99-
if (entry->hash == 0 && entry->key == NULL)
72+
if (entry->hash == hash) {
73+
PyObject *startkey = entry->key;
74+
assert(startkey != dummy);
75+
if (startkey == key)
10076
return entry;
101-
if (entry->hash == hash) {
102-
PyObject *startkey = entry->key;
103-
assert(startkey != dummy);
104-
if (startkey == key)
105-
return entry;
106-
if (PyUnicode_CheckExact(startkey)
107-
&& PyUnicode_CheckExact(key)
108-
&& _PyUnicode_EQ(startkey, key))
109-
return entry;
110-
table = so->table;
111-
Py_INCREF(startkey);
112-
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
113-
Py_DECREF(startkey);
114-
if (cmp < 0)
115-
return NULL;
116-
if (table != so->table || entry->key != startkey)
117-
return set_lookkey(so, key, hash);
118-
if (cmp > 0)
119-
return entry;
120-
mask = so->mask;
121-
}
77+
if (PyUnicode_CheckExact(startkey)
78+
&& PyUnicode_CheckExact(key)
79+
&& _PyUnicode_EQ(startkey, key))
80+
return entry;
81+
table = so->table;
82+
Py_INCREF(startkey);
83+
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
84+
Py_DECREF(startkey);
85+
if (cmp < 0)
86+
return NULL;
87+
if (table != so->table || entry->key != startkey)
88+
return set_lookkey(so, key, hash);
89+
if (cmp > 0)
90+
return entry;
91+
mask = so->mask;
12292
}
123-
}
124-
93+
entry++;
94+
} while (probes--);
12595
perturb >>= PERTURB_SHIFT;
12696
i = (i * 5 + 1 + perturb) & mask;
127-
128-
entry = &so->table[i];
129-
if (entry->key == NULL)
130-
return entry;
13197
}
13298
}
13399

@@ -141,7 +107,7 @@ set_add_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
141107
size_t perturb;
142108
size_t mask;
143109
size_t i; /* Unsigned for defined overflow behavior */
144-
size_t j;
110+
int probes;
145111
int cmp;
146112

147113
/* Pre-increment is necessary to prevent arbitrary code in the rich
@@ -152,75 +118,39 @@ set_add_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
152118

153119
mask = so->mask;
154120
i = (size_t)hash & mask;
155-
156-
entry = &so->table[i];
157-
if (entry->key == NULL)
158-
goto found_unused;
159-
160121
perturb = hash;
161122

162123
while (1) {
163-
if (entry->hash == hash) {
164-
PyObject *startkey = entry->key;
165-
/* startkey cannot be a dummy because the dummy hash field is -1 */
166-
assert(startkey != dummy);
167-
if (startkey == key)
168-
goto found_active;
169-
if (PyUnicode_CheckExact(startkey)
170-
&& PyUnicode_CheckExact(key)
171-
&& _PyUnicode_EQ(startkey, key))
172-
goto found_active;
173-
table = so->table;
174-
Py_INCREF(startkey);
175-
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
176-
Py_DECREF(startkey);
177-
if (cmp > 0) /* likely */
178-
goto found_active;
179-
if (cmp < 0)
180-
goto comparison_error;
181-
/* Continuing the search from the current entry only makes
182-
sense if the table and entry are unchanged; otherwise,
183-
we have to restart from the beginning */
184-
if (table != so->table || entry->key != startkey)
185-
goto restart;
186-
mask = so->mask; /* help avoid a register spill */
187-
}
188-
189-
if (i + LINEAR_PROBES <= mask) {
190-
for (j = 0 ; j < LINEAR_PROBES ; j++) {
191-
entry++;
192-
if (entry->hash == 0 && entry->key == NULL)
193-
goto found_unused;
194-
if (entry->hash == hash) {
195-
PyObject *startkey = entry->key;
196-
assert(startkey != dummy);
197-
if (startkey == key)
198-
goto found_active;
199-
if (PyUnicode_CheckExact(startkey)
200-
&& PyUnicode_CheckExact(key)
201-
&& _PyUnicode_EQ(startkey, key))
202-
goto found_active;
203-
table = so->table;
204-
Py_INCREF(startkey);
205-
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
206-
Py_DECREF(startkey);
207-
if (cmp > 0)
208-
goto found_active;
209-
if (cmp < 0)
210-
goto comparison_error;
211-
if (table != so->table || entry->key != startkey)
212-
goto restart;
213-
mask = so->mask;
214-
}
124+
entry = &so->table[i];
125+
probes = (i + LINEAR_PROBES <= mask) ? LINEAR_PROBES: 0;
126+
do {
127+
if (entry->hash == 0 && entry->key == NULL)
128+
goto found_unused;
129+
if (entry->hash == hash) {
130+
PyObject *startkey = entry->key;
131+
assert(startkey != dummy);
132+
if (startkey == key)
133+
goto found_active;
134+
if (PyUnicode_CheckExact(startkey)
135+
&& PyUnicode_CheckExact(key)
136+
&& _PyUnicode_EQ(startkey, key))
137+
goto found_active;
138+
table = so->table;
139+
Py_INCREF(startkey);
140+
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
141+
Py_DECREF(startkey);
142+
if (cmp > 0)
143+
goto found_active;
144+
if (cmp < 0)
145+
goto comparison_error;
146+
if (table != so->table || entry->key != startkey)
147+
goto restart;
148+
mask = so->mask;
215149
}
216-
}
217-
150+
entry++;
151+
} while (probes--);
218152
perturb >>= PERTURB_SHIFT;
219153
i = (i * 5 + 1 + perturb) & mask;
220-
221-
entry = &so->table[i];
222-
if (entry->key == NULL)
223-
goto found_unused;
224154
}
225155

226156
found_unused:

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.