diff options
Diffstat (limited to 'Objects/setobject.c')
| -rw-r--r-- | Objects/setobject.c | 131 |
1 files changed, 64 insertions, 67 deletions
diff --git a/Objects/setobject.c b/Objects/setobject.c index ea5a24c516..0db7e885e9 100644 --- a/Objects/setobject.c +++ b/Objects/setobject.c @@ -75,15 +75,15 @@ NULL if the rich comparison returns an error. */ static setentry * -set_lookkey(PySetObject *so, PyObject *key, register Py_hash_t hash) +set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) { - register size_t i; /* Unsigned for defined overflow behavior. */ - register size_t perturb; - register setentry *freeslot; - register size_t mask = so->mask; + size_t i; /* Unsigned for defined overflow behavior. */ + size_t perturb; + setentry *freeslot; + size_t mask = so->mask; setentry *table = so->table; - register setentry *entry; - register int cmp; + setentry *entry; + int cmp; PyObject *startkey; i = (size_t)hash & mask; @@ -91,34 +91,29 @@ set_lookkey(PySetObject *so, PyObject *key, register Py_hash_t hash) if (entry->key == NULL || entry->key == key) return entry; - if (entry->key == dummy) - freeslot = entry; - else { - if (entry->hash == hash) { - startkey = entry->key; - Py_INCREF(startkey); - cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); - Py_DECREF(startkey); - if (cmp < 0) - return NULL; - if (table == so->table && entry->key == startkey) { - if (cmp > 0) - return entry; - } - else { - /* The compare did major nasty stuff to the - * set: start over. - */ - return set_lookkey(so, key, hash); - } + if (entry->hash == hash) { + startkey = entry->key; + Py_INCREF(startkey); + cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); + Py_DECREF(startkey); + if (cmp < 0) + return NULL; + if (table == so->table && entry->key == startkey) { + if (cmp > 0) + return entry; + } + else { + /* Start over if the compare altered the set */ + return set_lookkey(so, key, hash); } - freeslot = NULL; } - /* In the loop, key == dummy is by far (factor of 100s) the - least likely outcome, so test for that last. */ + freeslot = (entry->key == dummy) ? entry : NULL; + + /* In the loop, key == dummy is by far (factor of 100s) + the least likely outcome, so test for that last. */ for (perturb = hash; ; perturb >>= PERTURB_SHIFT) { - i = (i << 2) + i + perturb + 1; + i = i * 5 + perturb + 1; entry = &table[i & mask]; if (entry->key == NULL) { if (freeslot != NULL) @@ -127,7 +122,7 @@ set_lookkey(PySetObject *so, PyObject *key, register Py_hash_t hash) } if (entry->key == key) break; - if (entry->hash == hash && entry->key != dummy) { + if (entry->hash == hash) { startkey = entry->key; Py_INCREF(startkey); cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); @@ -145,7 +140,7 @@ set_lookkey(PySetObject *so, PyObject *key, register Py_hash_t hash) return set_lookkey(so, key, hash); } } - else if (entry->key == dummy && freeslot == NULL) + if (entry->key == dummy && freeslot == NULL) freeslot = entry; } return entry; @@ -157,14 +152,14 @@ set_lookkey(PySetObject *so, PyObject *key, register Py_hash_t hash) * see if the comparison altered the table. */ static setentry * -set_lookkey_unicode(PySetObject *so, PyObject *key, register Py_hash_t hash) +set_lookkey_unicode(PySetObject *so, PyObject *key, Py_hash_t hash) { - register size_t i; /* Unsigned for defined overflow behavior. */ - register size_t perturb; - register setentry *freeslot; - register size_t mask = so->mask; + size_t i; /* Unsigned for defined overflow behavior. */ + size_t perturb; + setentry *freeslot; + size_t mask = so->mask; setentry *table = so->table; - register setentry *entry; + setentry *entry; /* Make sure this function doesn't have to handle non-unicode keys, including subclasses of str; e.g., one reason to subclass @@ -189,7 +184,7 @@ set_lookkey_unicode(PySetObject *so, PyObject *key, register Py_hash_t hash) /* In the loop, key == dummy is by far (factor of 100s) the least likely outcome, so test for that last. */ for (perturb = hash; ; perturb >>= PERTURB_SHIFT) { - i = (i << 2) + i + perturb + 1; + i = i * 5 + perturb + 1; entry = &table[i & mask]; if (entry->key == NULL) return freeslot == NULL ? entry : freeslot; @@ -211,9 +206,9 @@ Used by the public insert routine. Eats a reference to key. */ static int -set_insert_key(register PySetObject *so, PyObject *key, Py_hash_t hash) +set_insert_key(PySetObject *so, PyObject *key, Py_hash_t hash) { - register setentry *entry; + setentry *entry; assert(so->lookup != NULL); entry = so->lookup(so, key, hash); @@ -247,18 +242,18 @@ Note that no refcounts are changed by this routine; if needed, the caller is responsible for incref'ing `key`. */ static void -set_insert_clean(register PySetObject *so, PyObject *key, Py_hash_t hash) +set_insert_clean(PySetObject *so, PyObject *key, Py_hash_t hash) { - register size_t i; - register size_t perturb; - register size_t mask = (size_t)so->mask; + size_t i; + size_t perturb; + size_t mask = (size_t)so->mask; setentry *table = so->table; - register setentry *entry; + setentry *entry; i = (size_t)hash & mask; entry = &table[i]; for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) { - i = (i << 2) + i + perturb + 1; + i = i * 5 + perturb + 1; entry = &table[i & mask]; } so->fill++; @@ -280,6 +275,7 @@ set_table_resize(PySetObject *so, Py_ssize_t minused) Py_ssize_t i; int is_oldtable_malloced; setentry small_copy[PySet_MINSIZE]; + PyObject *dummy_entry; assert(minused >= 0); @@ -336,11 +332,12 @@ set_table_resize(PySetObject *so, Py_ssize_t minused) /* Copy the data over; this is refcount-neutral for active entries; dummy entries aren't copied over, of course */ + dummy_entry = dummy; for (entry = oldtable; i > 0; entry++) { if (entry->key == NULL) { /* UNUSED */ ; - } else if (entry->key == dummy) { + } else if (entry->key == dummy_entry) { /* DUMMY */ --i; assert(entry->key == dummy); @@ -360,9 +357,9 @@ set_table_resize(PySetObject *so, Py_ssize_t minused) /* CAUTION: set_add_key/entry() must guarantee it won't resize the table */ static int -set_add_entry(register PySetObject *so, setentry *entry) +set_add_entry(PySetObject *so, setentry *entry) { - register Py_ssize_t n_used; + Py_ssize_t n_used; PyObject *key = entry->key; Py_hash_t hash = entry->hash; @@ -379,10 +376,10 @@ set_add_entry(register PySetObject *so, setentry *entry) } static int -set_add_key(register PySetObject *so, PyObject *key) +set_add_key(PySetObject *so, PyObject *key) { - register Py_hash_t hash; - register Py_ssize_t n_used; + Py_hash_t hash; + Py_ssize_t n_used; if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *) key)->hash) == -1) { @@ -407,7 +404,7 @@ set_add_key(register PySetObject *so, PyObject *key) static int set_discard_entry(PySetObject *so, setentry *oldentry) -{ register setentry *entry; +{ setentry *entry; PyObject *old_key; entry = (so->lookup)(so, oldentry->key, oldentry->hash); @@ -426,8 +423,8 @@ set_discard_entry(PySetObject *so, setentry *oldentry) static int set_discard_key(PySetObject *so, PyObject *key) { - register Py_hash_t hash; - register setentry *entry; + Py_hash_t hash; + setentry *entry; PyObject *old_key; assert (PyAnySet_Check(so)); @@ -533,7 +530,7 @@ set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr) { Py_ssize_t i; Py_ssize_t mask; - register setentry *table; + setentry *table; assert (PyAnySet_Check(so)); i = *pos_ptr; @@ -553,7 +550,7 @@ set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr) static void set_dealloc(PySetObject *so) { - register setentry *entry; + setentry *entry; Py_ssize_t fill = so->fill; PyObject_GC_UnTrack(so); Py_TRASHCAN_SAFE_BEGIN(so) @@ -632,8 +629,8 @@ set_merge(PySetObject *so, PyObject *otherset) PySetObject *other; PyObject *key; Py_hash_t hash; - register Py_ssize_t i; - register setentry *entry; + Py_ssize_t i; + setentry *entry; assert (PyAnySet_Check(so)); assert (PyAnySet_Check(otherset)); @@ -701,8 +698,8 @@ set_contains_entry(PySetObject *so, setentry *entry) static PyObject * set_pop(PySetObject *so) { - register Py_ssize_t i = 0; - register setentry *entry; + Py_ssize_t i = 0; + setentry *entry; PyObject *key; assert (PyAnySet_Check(so)); @@ -869,8 +866,8 @@ static PyMethodDef setiter_methods[] = { static PyObject *setiter_iternext(setiterobject *si) { PyObject *key; - register Py_ssize_t i, mask; - register setentry *entry; + Py_ssize_t i, mask; + setentry *entry; PySetObject *so = si->si_set; if (so == NULL) @@ -1024,10 +1021,10 @@ PyDoc_STRVAR(update_doc, static PyObject * make_new_set(PyTypeObject *type, PyObject *iterable) { - register PySetObject *so = NULL; + PySetObject *so = NULL; if (dummy == NULL) { /* Auto-initialize dummy */ - dummy = PyUnicode_FromString("<dummy key>"); + dummy = _PyObject_New(&PyBaseObject_Type); if (dummy == NULL) return NULL; } |