diff options
Diffstat (limited to 'Objects/setobject.c')
-rw-r--r-- | Objects/setobject.c | 145 |
1 files changed, 41 insertions, 104 deletions
diff --git a/Objects/setobject.c b/Objects/setobject.c index 707ab95..d962c1e 100644 --- a/Objects/setobject.c +++ b/Objects/setobject.c @@ -52,6 +52,7 @@ static setentry * set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) { setentry *table = so->table; + setentry *freeslot = NULL; setentry *entry; size_t perturb = hash; size_t mask = so->mask; @@ -85,12 +86,14 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) return entry; mask = so->mask; /* help avoid a register spill */ } + if (entry->hash == -1 && freeslot == NULL) + freeslot = entry; if (i + LINEAR_PROBES <= mask) { for (j = 0 ; j < LINEAR_PROBES ; j++) { entry++; - if (entry->hash == 0 && entry->key == NULL) - return entry; + if (entry->key == NULL) + goto found_null; if (entry->hash == hash) { PyObject *startkey = entry->key; assert(startkey != dummy); @@ -111,89 +114,6 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) return entry; mask = so->mask; } - } - } - - perturb >>= PERTURB_SHIFT; - i = (i * 5 + 1 + perturb) & mask; - - entry = &table[i]; - if (entry->hash == 0 && entry->key == NULL) - return entry; - } -} - -/* -Internal routine to insert a new key into the table. -Used by the public insert routine. -Eats a reference to key. -*/ -static int -set_insert_key(PySetObject *so, PyObject *key, Py_hash_t hash) -{ - setentry *table = so->table; - setentry *freeslot = NULL; - setentry *entry; - size_t perturb = hash; - size_t mask = so->mask; - size_t i = (size_t)hash & mask; /* Unsigned for defined overflow behavior */ - size_t j; - int cmp; - - entry = &table[i]; - if (entry->key == NULL) - goto found_null; - - while (1) { - 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) - goto found_active; - if (PyUnicode_CheckExact(startkey) - && PyUnicode_CheckExact(key) - && unicode_eq(startkey, key)) - goto found_active; - Py_INCREF(startkey); - cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); - Py_DECREF(startkey); - if (cmp < 0) /* unlikely */ - return -1; - if (table != so->table || entry->key != startkey) /* unlikely */ - return set_insert_key(so, key, hash); - if (cmp > 0) /* likely */ - goto found_active; - mask = so->mask; /* help avoid a register spill */ - } - if (entry->hash == -1 && freeslot == NULL) - freeslot = entry; - - if (i + LINEAR_PROBES <= mask) { - for (j = 0 ; j < LINEAR_PROBES ; j++) { - entry++; - if (entry->hash == 0 && entry->key == NULL) - goto found_null; - if (entry->hash == hash) { - PyObject *startkey = entry->key; - assert(startkey != dummy); - if (startkey == key) - goto found_active; - if (PyUnicode_CheckExact(startkey) - && PyUnicode_CheckExact(key) - && unicode_eq(startkey, key)) - goto found_active; - Py_INCREF(startkey); - cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); - Py_DECREF(startkey); - if (cmp < 0) - return -1; - if (table != so->table || entry->key != startkey) - return set_insert_key(so, key, hash); - if (cmp > 0) - goto found_active; - mask = so->mask; - } if (entry->hash == -1 && freeslot == NULL) freeslot = entry; } @@ -203,26 +123,11 @@ set_insert_key(PySetObject *so, PyObject *key, Py_hash_t hash) i = (i * 5 + 1 + perturb) & mask; entry = &table[i]; - if (entry->hash == 0 && entry->key == NULL) + if (entry->key == NULL) goto found_null; } - found_null: - if (freeslot == NULL) { - /* UNUSED */ - so->fill++; - } else { - /* DUMMY */ - entry = freeslot; - } - so->used++; - entry->key = key; - entry->hash = hash; - return 0; - - found_active: - Py_DECREF(key); - return 0; + return freeslot == NULL ? entry : freeslot; } /* @@ -267,6 +172,38 @@ set_insert_clean(PySetObject *so, PyObject *key, Py_hash_t hash) /* ======== End logic for probing the hash table ========================== */ /* ======================================================================== */ + +/* +Internal routine to insert a new key into the table. +Used by the public insert routine. +Eats a reference to key. +*/ +static int +set_insert_key(PySetObject *so, PyObject *key, Py_hash_t hash) +{ + setentry *entry; + + entry = set_lookkey(so, key, hash); + if (entry == NULL) + return -1; + if (entry->key == NULL) { + /* UNUSED */ + entry->key = key; + entry->hash = hash; + so->fill++; + so->used++; + } else if (entry->key == dummy) { + /* DUMMY */ + entry->key = key; + entry->hash = hash; + so->used++; + } else { + /* ACTIVE */ + Py_DECREF(key); + } + return 0; +} + /* Restructure the table by allocating a new table and reinserting all keys again. When entries have been deleted, the new table may @@ -408,7 +345,7 @@ set_discard_entry(PySetObject *so, setentry *oldentry) entry = set_lookkey(so, oldentry->key, oldentry->hash); if (entry == NULL) return -1; - if (entry->key == NULL) + if (entry->key == NULL || entry->key == dummy) return DISCARD_NOTFOUND; old_key = entry->key; entry->key = dummy; @@ -686,7 +623,7 @@ set_contains_entry(PySetObject *so, setentry *entry) if (lu_entry == NULL) return -1; key = lu_entry->key; - return key != NULL; + return key != NULL && key != dummy; } static int |