diff options
Diffstat (limited to 'Objects/setobject.c')
| -rw-r--r-- | Objects/setobject.c | 1528 |
1 files changed, 744 insertions, 784 deletions
diff --git a/Objects/setobject.c b/Objects/setobject.c index 924885d..31da3db 100644 --- a/Objects/setobject.c +++ b/Objects/setobject.c @@ -1,300 +1,267 @@ /* set object implementation - Written and maintained by Raymond D. Hettinger <python@rcn.com> Derived from Lib/sets.py and Objects/dictobject.c. - - The basic lookup function used by all operations. - This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4. - - The initial probe index is computed as hash mod the table size. - Subsequent probe indices are computed as explained in Objects/dictobject.c. - - To improve cache locality, each probe inspects a series of consecutive - nearby entries before moving on to probes elsewhere in memory. This leaves - us with a hybrid of linear probing and randomized probing. The linear probing - reduces the cost of hash collisions because consecutive memory accesses - tend to be much cheaper than scattered probes. After LINEAR_PROBES steps, - we then use more of the upper bits from the hash value and apply a simple - linear congruential random number genearator. This helps break-up long - chains of collisions. - - All arithmetic on hash should ignore overflow. - - Unlike the dictionary implementation, the lookkey function can return - NULL if the rich comparison returns an error. - - Use cases for sets differ considerably from dictionaries where looked-up - keys are more likely to be present. In contrast, sets are primarily - about membership testing where the presence of an element is not known in - advance. Accordingly, the set implementation needs to optimize for both - the found and not-found case. */ #include "Python.h" -#include "pycore_object.h" -#include "pycore_pystate.h" #include "structmember.h" +/* Set a key error with the specified argument, wrapping it in a + * tuple automatically so that tuple keys are not unpacked as the + * exception arguments. */ +static void +set_key_error(PyObject *arg) +{ + PyObject *tup; + tup = PyTuple_Pack(1, arg); + if (!tup) + return; /* caller will expect error to be set anyway */ + PyErr_SetObject(PyExc_KeyError, tup); + Py_DECREF(tup); +} + +/* This must be >= 1. */ +#define PERTURB_SHIFT 5 + /* Object used as dummy key to fill deleted entries */ -static PyObject _dummy_struct; +static PyObject *dummy = NULL; /* Initialized by first call to make_new_set() */ -#define dummy (&_dummy_struct) +#ifdef Py_REF_DEBUG +PyObject * +_PySet_Dummy(void) +{ + return dummy; +} +#endif +#define INIT_NONZERO_SET_SLOTS(so) do { \ + (so)->table = (so)->smalltable; \ + (so)->mask = PySet_MINSIZE - 1; \ + (so)->hash = -1; \ + } while(0) -/* ======================================================================== */ -/* ======= Begin logic for probing the hash table ========================= */ +#define EMPTY_TO_MINSIZE(so) do { \ + memset((so)->smalltable, 0, sizeof((so)->smalltable)); \ + (so)->used = (so)->fill = 0; \ + INIT_NONZERO_SET_SLOTS(so); \ + } while(0) -/* Set this to zero to turn-off linear probing */ -#ifndef LINEAR_PROBES -#define LINEAR_PROBES 9 +/* Reuse scheme to save calls to malloc, free, and memset */ +#ifndef PySet_MAXFREELIST +#define PySet_MAXFREELIST 80 #endif +static PySetObject *free_list[PySet_MAXFREELIST]; +static int numfree = 0; -/* This must be >= 1 */ -#define PERTURB_SHIFT 5 +/* +The basic lookup function used by all operations. +This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4. +Open addressing is preferred over chaining since the link overhead for +chaining would be substantial (100% with typical malloc overhead). + +The initial probe index is computed as hash mod the table size. Subsequent +probe indices are computed as explained in Objects/dictobject.c. + +All arithmetic on hash should ignore overflow. + +Unlike the dictionary implementation, the lookkey functions can return +NULL if the rich comparison returns an error. +*/ static setentry * -set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) +set_lookkey(PySetObject *so, PyObject *key, register long hash) { - setentry *table; - setentry *entry; - size_t perturb; - size_t mask = so->mask; - size_t i = (size_t)hash & mask; /* Unsigned for defined overflow behavior */ - size_t j; - int cmp; - - entry = &so->table[i]; - if (entry->key == NULL) - return entry; + register Py_ssize_t i; + register size_t perturb; + register setentry *freeslot; + register size_t mask = so->mask; + setentry *table = so->table; + register setentry *entry; + register int cmp; + PyObject *startkey; - perturb = hash; + i = hash & mask; + entry = &table[i]; + if (entry->key == NULL || entry->key == key) + return entry; - while (1) { + if (entry->key == dummy) + freeslot = entry; + else { 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) - && PyUnicode_CheckExact(key) - && _PyUnicode_EQ(startkey, key)) - return entry; - table = so->table; + startkey = entry->key; Py_INCREF(startkey); cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); Py_DECREF(startkey); - if (cmp < 0) /* unlikely */ + if (cmp < 0) return NULL; - if (table != so->table || entry->key != startkey) /* unlikely */ - return set_lookkey(so, key, hash); - if (cmp > 0) /* likely */ - return entry; - mask = so->mask; /* help avoid a register spill */ - } - - if (i + LINEAR_PROBES <= mask) { - for (j = 0 ; j < LINEAR_PROBES ; j++) { - entry++; - if (entry->hash == 0 && entry->key == NULL) + if (table == so->table && entry->key == startkey) { + if (cmp > 0) return entry; - if (entry->hash == hash) { - PyObject *startkey = entry->key; - assert(startkey != dummy); - if (startkey == key) - return entry; - if (PyUnicode_CheckExact(startkey) - && PyUnicode_CheckExact(key) - && _PyUnicode_EQ(startkey, key)) - return entry; - table = so->table; - 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) - return set_lookkey(so, key, hash); - if (cmp > 0) - return entry; - mask = so->mask; - } + } + else { + /* The compare did major nasty stuff to the + * set: start over. + */ + return set_lookkey(so, key, hash); } } - - perturb >>= PERTURB_SHIFT; - i = (i * 5 + 1 + perturb) & mask; - - entry = &so->table[i]; - if (entry->key == NULL) - return entry; - } -} - -static int set_table_resize(PySetObject *, Py_ssize_t); - -static int -set_add_entry(PySetObject *so, PyObject *key, Py_hash_t hash) -{ - setentry *table; - setentry *freeslot; - setentry *entry; - size_t perturb; - size_t mask; - size_t i; /* Unsigned for defined overflow behavior */ - size_t j; - int cmp; - - /* Pre-increment is necessary to prevent arbitrary code in the rich - comparison from deallocating the key just before the insertion. */ - Py_INCREF(key); - - restart: - - mask = so->mask; - i = (size_t)hash & mask; - - entry = &so->table[i]; - if (entry->key == NULL) - goto found_unused; - - freeslot = NULL; - perturb = hash; - - 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) - && _PyUnicode_EQ(startkey, key)) - goto found_active; - table = so->table; + freeslot = 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; + entry = &table[i & mask]; + if (entry->key == NULL) { + if (freeslot != NULL) + entry = freeslot; + break; + } + if (entry->key == key) + break; + if (entry->hash == hash && entry->key != dummy) { + startkey = entry->key; Py_INCREF(startkey); cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); Py_DECREF(startkey); - if (cmp > 0) /* likely */ - goto found_active; if (cmp < 0) - goto comparison_error; - /* Continuing the search from the current entry only makes - sense if the table and entry are unchanged; otherwise, - we have to restart from the beginning */ - if (table != so->table || entry->key != startkey) - goto restart; - mask = so->mask; /* help avoid a register spill */ - } - else if (entry->hash == -1) - freeslot = entry; - - if (i + LINEAR_PROBES <= mask) { - for (j = 0 ; j < LINEAR_PROBES ; j++) { - entry++; - if (entry->hash == 0 && entry->key == NULL) - goto found_unused_or_dummy; - if (entry->hash == hash) { - PyObject *startkey = entry->key; - assert(startkey != dummy); - if (startkey == key) - goto found_active; - if (PyUnicode_CheckExact(startkey) - && PyUnicode_CheckExact(key) - && _PyUnicode_EQ(startkey, key)) - goto found_active; - table = so->table; - Py_INCREF(startkey); - cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); - Py_DECREF(startkey); - if (cmp > 0) - goto found_active; - if (cmp < 0) - goto comparison_error; - if (table != so->table || entry->key != startkey) - goto restart; - mask = so->mask; - } - else if (entry->hash == -1) - freeslot = entry; + return NULL; + if (table == so->table && entry->key == startkey) { + if (cmp > 0) + break; + } + else { + /* The compare did major nasty stuff to the + * set: start over. + */ + return set_lookkey(so, key, hash); } } + else if (entry->key == dummy && freeslot == NULL) + freeslot = entry; + } + return entry; +} - perturb >>= PERTURB_SHIFT; - i = (i * 5 + 1 + perturb) & mask; +/* + * Hacked up version of set_lookkey which can assume keys are always strings; + * This means we can always use _PyString_Eq directly and not have to check to + * see if the comparison altered the table. + */ +static setentry * +set_lookkey_string(PySetObject *so, PyObject *key, register long hash) +{ + register Py_ssize_t i; + register size_t perturb; + register setentry *freeslot; + register size_t mask = so->mask; + setentry *table = so->table; + register setentry *entry; + + /* Make sure this function doesn't have to handle non-string keys, + including subclasses of str; e.g., one reason to subclass + strings is to override __eq__, and for speed we don't cater to + that here. */ + if (!PyString_CheckExact(key)) { + so->lookup = set_lookkey; + return set_lookkey(so, key, hash); + } + i = hash & mask; + entry = &table[i]; + if (entry->key == NULL || entry->key == key) + return entry; + if (entry->key == dummy) + freeslot = entry; + else { + if (entry->hash == hash && _PyString_Eq(entry->key, key)) + return entry; + freeslot = NULL; + } - entry = &so->table[i]; + /* 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; + entry = &table[i & mask]; if (entry->key == NULL) - goto found_unused_or_dummy; + return freeslot == NULL ? entry : freeslot; + if (entry->key == key + || (entry->hash == hash + && entry->key != dummy + && _PyString_Eq(entry->key, key))) + return entry; + if (entry->key == dummy && freeslot == NULL) + freeslot = entry; } - - found_unused_or_dummy: - if (freeslot == NULL) - goto found_unused; - so->used++; - freeslot->key = key; - freeslot->hash = hash; + assert(0); /* NOT REACHED */ return 0; +} - found_unused: - so->fill++; - so->used++; - entry->key = key; - entry->hash = hash; - if ((size_t)so->fill*5 < mask*3) - return 0; - return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4); +/* +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(register PySetObject *so, PyObject *key, long hash) +{ + register setentry *entry; - found_active: - Py_DECREF(key); + assert(so->lookup != NULL); + entry = so->lookup(so, key, hash); + if (entry == NULL) + return -1; + if (entry->key == NULL) { + /* UNUSED */ + so->fill++; + entry->key = key; + entry->hash = hash; + so->used++; + } else if (entry->key == dummy) { + /* DUMMY */ + entry->key = key; + entry->hash = hash; + so->used++; + Py_DECREF(dummy); + } else { + /* ACTIVE */ + Py_DECREF(key); + } return 0; - - comparison_error: - Py_DECREF(key); - return -1; } /* Internal routine used by set_table_resize() to insert an item which is known to be absent from the set. This routine also assumes that the set contains no deleted entries. Besides the performance benefit, -there is also safety benefit since using set_add_entry() risks making -a callback in the middle of a set_table_resize(), see issue 1456209. -The caller is responsible for updating the key's reference count and -the setobject's fill and used fields. +using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209). +Note that no refcounts are changed by this routine; if needed, the caller +is responsible for incref'ing `key`. */ static void -set_insert_clean(setentry *table, size_t mask, PyObject *key, Py_hash_t hash) +set_insert_clean(register PySetObject *so, PyObject *key, long hash) { - setentry *entry; - size_t perturb = hash; - size_t i = (size_t)hash & mask; - size_t j; + register size_t i; + register size_t perturb; + register size_t mask = (size_t)so->mask; + setentry *table = so->table; + register setentry *entry; - while (1) { - entry = &table[i]; - if (entry->key == NULL) - goto found_null; - if (i + LINEAR_PROBES <= mask) { - for (j = 0; j < LINEAR_PROBES; j++) { - entry++; - if (entry->key == NULL) - goto found_null; - } - } - perturb >>= PERTURB_SHIFT; - i = (i * 5 + 1 + perturb) & mask; + i = hash & mask; + entry = &table[i]; + for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) { + i = (i << 2) + i + perturb + 1; + entry = &table[i & mask]; } - found_null: + so->fill++; entry->key = key; entry->hash = hash; + so->used++; } -/* ======== End logic for probing the hash table ========================== */ -/* ======================================================================== */ - /* Restructure the table by allocating a new table and reinserting all keys again. When entries have been deleted, the new table may @@ -303,19 +270,22 @@ actually be smaller than the old one. static int set_table_resize(PySetObject *so, Py_ssize_t minused) { + Py_ssize_t newsize; setentry *oldtable, *newtable, *entry; - Py_ssize_t oldmask = so->mask; - size_t newmask; + Py_ssize_t i; int is_oldtable_malloced; setentry small_copy[PySet_MINSIZE]; assert(minused >= 0); /* Find the smallest table size > minused. */ - /* XXX speed-up with intrinsics */ - size_t newsize = PySet_MINSIZE; - while (newsize <= (size_t)minused) { - newsize <<= 1; // The largest possible value is PY_SSIZE_T_MAX + 1. + for (newsize = PySet_MINSIZE; + newsize <= minused && newsize > 0; + newsize <<= 1) + ; + if (newsize <= 0) { + PyErr_NoMemory(); + return -1; } /* Get space for a new table. */ @@ -352,25 +322,28 @@ set_table_resize(PySetObject *so, Py_ssize_t minused) /* Make the set empty, using the new table. */ assert(newtable != oldtable); - memset(newtable, 0, sizeof(setentry) * newsize); - so->mask = newsize - 1; so->table = newtable; + so->mask = newsize - 1; + memset(newtable, 0, sizeof(setentry) * newsize); + so->used = 0; + i = so->fill; + so->fill = 0; /* Copy the data over; this is refcount-neutral for active entries; dummy entries aren't copied over, of course */ - newmask = (size_t)so->mask; - if (so->fill == so->used) { - for (entry = oldtable; entry <= oldtable + oldmask; entry++) { - if (entry->key != NULL) { - set_insert_clean(newtable, newmask, entry->key, entry->hash); - } - } - } else { - so->fill = so->used; - for (entry = oldtable; entry <= oldtable + oldmask; entry++) { - if (entry->key != NULL && entry->key != dummy) { - set_insert_clean(newtable, newmask, entry->key, entry->hash); - } + for (entry = oldtable; i > 0; entry++) { + if (entry->key == NULL) { + /* UNUSED */ + ; + } else if (entry->key == dummy) { + /* DUMMY */ + --i; + assert(entry->key == dummy); + Py_DECREF(entry->key); + } else { + /* ACTIVE */ + --i; + set_insert_clean(so, entry->key, entry->hash); } } @@ -379,104 +352,117 @@ set_table_resize(PySetObject *so, Py_ssize_t minused) return 0; } +/* CAUTION: set_add_key/entry() must guarantee it won't resize the table */ + static int -set_contains_entry(PySetObject *so, PyObject *key, Py_hash_t hash) +set_add_entry(register PySetObject *so, setentry *entry) { - setentry *entry; + register Py_ssize_t n_used; + PyObject *key = entry->key; + long hash = entry->hash; - entry = set_lookkey(so, key, hash); - if (entry != NULL) - return entry->key != NULL; - return -1; + assert(so->fill <= so->mask); /* at least one empty slot */ + n_used = so->used; + Py_INCREF(key); + if (set_insert_key(so, key, hash) == -1) { + Py_DECREF(key); + return -1; + } + if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2)) + return 0; + return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4); +} + +static int +set_add_key(register PySetObject *so, PyObject *key) +{ + register long hash; + register Py_ssize_t n_used; + + if (!PyString_CheckExact(key) || + (hash = ((PyStringObject *) key)->ob_shash) == -1) { + hash = PyObject_Hash(key); + if (hash == -1) + return -1; + } + assert(so->fill <= so->mask); /* at least one empty slot */ + n_used = so->used; + Py_INCREF(key); + if (set_insert_key(so, key, hash) == -1) { + Py_DECREF(key); + return -1; + } + if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2)) + return 0; + return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4); } #define DISCARD_NOTFOUND 0 #define DISCARD_FOUND 1 static int -set_discard_entry(PySetObject *so, PyObject *key, Py_hash_t hash) -{ - setentry *entry; +set_discard_entry(PySetObject *so, setentry *oldentry) +{ register setentry *entry; PyObject *old_key; - entry = set_lookkey(so, key, hash); + entry = (so->lookup)(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; + Py_INCREF(dummy); entry->key = dummy; - entry->hash = -1; so->used--; Py_DECREF(old_key); return DISCARD_FOUND; } static int -set_add_key(PySetObject *so, PyObject *key) -{ - Py_hash_t hash; - - if (!PyUnicode_CheckExact(key) || - (hash = ((PyASCIIObject *) key)->hash) == -1) { - hash = PyObject_Hash(key); - if (hash == -1) - return -1; - } - return set_add_entry(so, key, hash); -} - -static int -set_contains_key(PySetObject *so, PyObject *key) -{ - Py_hash_t hash; - - if (!PyUnicode_CheckExact(key) || - (hash = ((PyASCIIObject *) key)->hash) == -1) { - hash = PyObject_Hash(key); - if (hash == -1) - return -1; - } - return set_contains_entry(so, key, hash); -} - -static int set_discard_key(PySetObject *so, PyObject *key) { - Py_hash_t hash; + register long hash; + register setentry *entry; + PyObject *old_key; - if (!PyUnicode_CheckExact(key) || - (hash = ((PyASCIIObject *) key)->hash) == -1) { + assert (PyAnySet_Check(so)); + if (!PyString_CheckExact(key) || + (hash = ((PyStringObject *) key)->ob_shash) == -1) { hash = PyObject_Hash(key); if (hash == -1) return -1; } - return set_discard_entry(so, key, hash); -} - -static void -set_empty_to_minsize(PySetObject *so) -{ - memset(so->smalltable, 0, sizeof(so->smalltable)); - so->fill = 0; - so->used = 0; - so->mask = PySet_MINSIZE - 1; - so->table = so->smalltable; - so->hash = -1; + entry = (so->lookup)(so, key, hash); + if (entry == NULL) + return -1; + if (entry->key == NULL || entry->key == dummy) + return DISCARD_NOTFOUND; + old_key = entry->key; + Py_INCREF(dummy); + entry->key = dummy; + so->used--; + Py_DECREF(old_key); + return DISCARD_FOUND; } static int set_clear_internal(PySetObject *so) { - setentry *entry; - setentry *table = so->table; - Py_ssize_t fill = so->fill; - Py_ssize_t used = so->used; - int table_is_malloced = table != so->smalltable; + setentry *entry, *table; + int table_is_malloced; + Py_ssize_t fill; setentry small_copy[PySet_MINSIZE]; - +#ifdef Py_DEBUG + Py_ssize_t i, n; assert (PyAnySet_Check(so)); + + n = so->mask + 1; + i = 0; +#endif + + table = so->table; assert(table != NULL); + table_is_malloced = table != so->smalltable; /* This is delicate. During the process of clearing the set, * decrefs can cause the set to mutate. To avoid fatal confusion @@ -484,8 +470,9 @@ set_clear_internal(PySetObject *so) * clearing the slots, and never refer to anything via so->ref while * clearing. */ + fill = so->fill; if (table_is_malloced) - set_empty_to_minsize(so); + EMPTY_TO_MINSIZE(so); else if (fill > 0) { /* It's a small table with something that needs to be cleared. @@ -494,7 +481,7 @@ set_clear_internal(PySetObject *so) */ memcpy(small_copy, table, sizeof(small_copy)); table = small_copy; - set_empty_to_minsize(so); + EMPTY_TO_MINSIZE(so); } /* else it's a small table that's already empty */ @@ -502,11 +489,19 @@ set_clear_internal(PySetObject *so) * assert that the refcount on table is 1 now, i.e. that this function * has unique access to it, so decref side-effects can't alter it. */ - for (entry = table; used > 0; entry++) { - if (entry->key && entry->key != dummy) { - used--; + for (entry = table; fill > 0; ++entry) { +#ifdef Py_DEBUG + assert(i < n); + ++i; +#endif + if (entry->key) { + --fill; Py_DECREF(entry->key); } +#ifdef Py_DEBUG + else + assert(entry->key == NULL); +#endif } if (table_is_malloced) @@ -532,88 +527,109 @@ set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr) { Py_ssize_t i; Py_ssize_t mask; - setentry *entry; + register setentry *table; assert (PyAnySet_Check(so)); i = *pos_ptr; assert(i >= 0); + table = so->table; mask = so->mask; - entry = &so->table[i]; - while (i <= mask && (entry->key == NULL || entry->key == dummy)) { + while (i <= mask && (table[i].key == NULL || table[i].key == dummy)) i++; - entry++; - } *pos_ptr = i+1; if (i > mask) return 0; - assert(entry != NULL); - *entry_ptr = entry; + assert(table[i].key != NULL); + *entry_ptr = &table[i]; return 1; } static void set_dealloc(PySetObject *so) { - setentry *entry; - Py_ssize_t used = so->used; - + register setentry *entry; + Py_ssize_t fill = so->fill; /* bpo-31095: UnTrack is needed before calling any callbacks */ PyObject_GC_UnTrack(so); - Py_TRASHCAN_BEGIN(so, set_dealloc) + Py_TRASHCAN_SAFE_BEGIN(so) if (so->weakreflist != NULL) PyObject_ClearWeakRefs((PyObject *) so); - for (entry = so->table; used > 0; entry++) { - if (entry->key && entry->key != dummy) { - used--; - Py_DECREF(entry->key); + for (entry = so->table; fill > 0; entry++) { + if (entry->key) { + --fill; + Py_DECREF(entry->key); } } if (so->table != so->smalltable) PyMem_DEL(so->table); - Py_TYPE(so)->tp_free(so); - Py_TRASHCAN_END + if (numfree < PySet_MAXFREELIST && PyAnySet_CheckExact(so)) + free_list[numfree++] = so; + else + Py_TYPE(so)->tp_free(so); + Py_TRASHCAN_SAFE_END(so) +} + +static int +set_tp_print(PySetObject *so, FILE *fp, int flags) +{ + setentry *entry; + Py_ssize_t pos=0; + char *emit = ""; /* No separator emitted on first pass */ + char *separator = ", "; + int status = Py_ReprEnter((PyObject*)so); + + if (status != 0) { + if (status < 0) + return status; + Py_BEGIN_ALLOW_THREADS + fprintf(fp, "%s(...)", Py_TYPE(so)->tp_name); + Py_END_ALLOW_THREADS + return 0; + } + + Py_BEGIN_ALLOW_THREADS + fprintf(fp, "%s([", Py_TYPE(so)->tp_name); + Py_END_ALLOW_THREADS + while (set_next(so, &pos, &entry)) { + Py_BEGIN_ALLOW_THREADS + fputs(emit, fp); + Py_END_ALLOW_THREADS + emit = separator; + if (PyObject_Print(entry->key, fp, 0) != 0) { + Py_ReprLeave((PyObject*)so); + return -1; + } + } + Py_BEGIN_ALLOW_THREADS + fputs("])", fp); + Py_END_ALLOW_THREADS + Py_ReprLeave((PyObject*)so); + return 0; } static PyObject * set_repr(PySetObject *so) { - PyObject *result=NULL, *keys, *listrepr, *tmp; + PyObject *keys, *result=NULL, *listrepr; int status = Py_ReprEnter((PyObject*)so); if (status != 0) { if (status < 0) return NULL; - return PyUnicode_FromFormat("%s(...)", Py_TYPE(so)->tp_name); - } - - /* shortcut for the empty set */ - if (!so->used) { - Py_ReprLeave((PyObject*)so); - return PyUnicode_FromFormat("%s()", Py_TYPE(so)->tp_name); + return PyString_FromFormat("%s(...)", Py_TYPE(so)->tp_name); } keys = PySequence_List((PyObject *)so); if (keys == NULL) goto done; - - /* repr(keys)[1:-1] */ listrepr = PyObject_Repr(keys); Py_DECREF(keys); if (listrepr == NULL) goto done; - tmp = PyUnicode_Substring(listrepr, 1, PyUnicode_GET_LENGTH(listrepr)-1); - Py_DECREF(listrepr); - if (tmp == NULL) - goto done; - listrepr = tmp; - if (Py_TYPE(so) != &PySet_Type) - result = PyUnicode_FromFormat("%s({%U})", - Py_TYPE(so)->tp_name, - listrepr); - else - result = PyUnicode_FromFormat("{%U}", listrepr); + result = PyString_FromFormat("%s(%s)", Py_TYPE(so)->tp_name, + PyString_AS_STRING(listrepr)); Py_DECREF(listrepr); done: Py_ReprLeave((PyObject*)so); @@ -631,95 +647,113 @@ set_merge(PySetObject *so, PyObject *otherset) { PySetObject *other; PyObject *key; - Py_ssize_t i; - setentry *so_entry; - setentry *other_entry; + long hash; + register Py_ssize_t i; + register setentry *entry; assert (PyAnySet_Check(so)); assert (PyAnySet_Check(otherset)); other = (PySetObject*)otherset; if (other == so || other->used == 0) - /* a.update(a) or a.update(set()); nothing to do */ + /* a.update(a) or a.update({}); nothing to do */ return 0; /* Do one big resize at the start, rather than * incrementally resizing as we insert new keys. Expect * that there will be no (or few) overlapping keys. */ - if ((so->fill + other->used)*5 >= so->mask*3) { - if (set_table_resize(so, (so->used + other->used)*2) != 0) - return -1; + if ((so->fill + other->used)*3 >= (so->mask+1)*2) { + if (set_table_resize(so, (so->used + other->used)*2) != 0) + return -1; } - so_entry = so->table; - other_entry = other->table; - - /* If our table is empty, and both tables have the same size, and - there are no dummies to eliminate, then just copy the pointers. */ - if (so->fill == 0 && so->mask == other->mask && other->fill == other->used) { - for (i = 0; i <= other->mask; i++, so_entry++, other_entry++) { - key = other_entry->key; - if (key != NULL) { - assert(so_entry->key == NULL); - Py_INCREF(key); - so_entry->key = key; - so_entry->hash = other_entry->hash; + for (i = 0; i <= other->mask; i++) { + entry = &other->table[i]; + key = entry->key; + hash = entry->hash; + if (key != NULL && + key != dummy) { + Py_INCREF(key); + if (set_insert_key(so, key, hash) == -1) { + Py_DECREF(key); + return -1; } } - so->fill = other->fill; - so->used = other->used; - return 0; } + return 0; +} - /* If our table is empty, we can use set_insert_clean() */ - if (so->fill == 0) { - setentry *newtable = so->table; - size_t newmask = (size_t)so->mask; - so->fill = other->used; - so->used = other->used; - for (i = other->mask + 1; i > 0 ; i--, other_entry++) { - key = other_entry->key; - if (key != NULL && key != dummy) { - Py_INCREF(key); - set_insert_clean(newtable, newmask, key, other_entry->hash); - } - } - return 0; - } +static int +set_contains_key(PySetObject *so, PyObject *key) +{ + long hash; + setentry *entry; - /* We can't assure there are no duplicates, so do normal insertions */ - for (i = 0; i <= other->mask; i++) { - other_entry = &other->table[i]; - key = other_entry->key; - if (key != NULL && key != dummy) { - if (set_add_entry(so, key, other_entry->hash)) - return -1; - } + if (!PyString_CheckExact(key) || + (hash = ((PyStringObject *) key)->ob_shash) == -1) { + hash = PyObject_Hash(key); + if (hash == -1) + return -1; } - return 0; + entry = (so->lookup)(so, key, hash); + if (entry == NULL) + return -1; + key = entry->key; + return key != NULL && key != dummy; +} + +static int +set_contains_entry(PySetObject *so, setentry *entry) +{ + PyObject *key; + setentry *lu_entry; + + lu_entry = (so->lookup)(so, entry->key, entry->hash); + if (lu_entry == NULL) + return -1; + key = lu_entry->key; + return key != NULL && key != dummy; } static PyObject * -set_pop(PySetObject *so, PyObject *Py_UNUSED(ignored)) +set_pop(PySetObject *so) { - /* Make sure the search finger is in bounds */ - setentry *entry = so->table + (so->finger & so->mask); - setentry *limit = so->table + so->mask; + register Py_ssize_t i = 0; + register setentry *entry; PyObject *key; + assert (PyAnySet_Check(so)); if (so->used == 0) { PyErr_SetString(PyExc_KeyError, "pop from an empty set"); return NULL; } - while (entry->key == NULL || entry->key==dummy) { - entry++; - if (entry > limit) - entry = so->table; + + /* Set entry to "the first" unused or dummy set entry. We abuse + * the hash field of slot 0 to hold a search finger: + * If slot 0 has a value, use slot 0. + * Else slot 0 is being used to hold a search finger, + * and we use its hash value as the first index to look. + */ + entry = &so->table[0]; + if (entry->key == NULL || entry->key == dummy) { + i = entry->hash; + /* The hash field may be a real hash value, or it may be a + * legit search finger, or it may be a once-legit search + * finger that's out of bounds now because it wrapped around + * or the table shrunk -- simply make sure it's in bounds now. + */ + if (i > so->mask || i < 1) + i = 1; /* skip slot 0 */ + while ((entry = &so->table[i])->key == NULL || entry->key==dummy) { + i++; + if (i > so->mask) + i = 1; + } } key = entry->key; + Py_INCREF(dummy); entry->key = dummy; - entry->hash = -1; so->used--; - so->finger = entry - so->table + 1; /* next place to start */ + so->table[0].hash = i + 1; /* next place to start */ return key; } @@ -737,65 +771,30 @@ set_traverse(PySetObject *so, visitproc visit, void *arg) return 0; } -/* Work to increase the bit dispersion for closely spaced hash values. - This is important because some use cases have many combinations of a - small number of elements with nearby hashes so that many distinct - combinations collapse to only a handful of distinct hash values. */ - -static Py_uhash_t -_shuffle_bits(Py_uhash_t h) -{ - return ((h ^ 89869747UL) ^ (h << 16)) * 3644798167UL; -} - -/* Most of the constants in this hash algorithm are randomly chosen - large primes with "interesting bit patterns" and that passed tests - for good collision statistics on a variety of problematic datasets - including powersets and graph structures (such as David Eppstein's - graph recipes in Lib/test/test_set.py) */ - -static Py_hash_t +static long frozenset_hash(PyObject *self) { PySetObject *so = (PySetObject *)self; - Py_uhash_t hash = 0; + long h, hash = 1927868237L; setentry *entry; + Py_ssize_t pos = 0; if (so->hash != -1) return so->hash; - /* Xor-in shuffled bits from every entry's hash field because xor is - commutative and a frozenset hash should be independent of order. - - For speed, include null entries and dummy entries and then - subtract out their effect afterwards so that the final hash - depends only on active entries. This allows the code to be - vectorized by the compiler and it saves the unpredictable - branches that would arise when trying to exclude null and dummy - entries on every iteration. */ - - for (entry = so->table; entry <= &so->table[so->mask]; entry++) - hash ^= _shuffle_bits(entry->hash); - - /* Remove the effect of an odd number of NULL entries */ - if ((so->mask + 1 - so->fill) & 1) - hash ^= _shuffle_bits(0); - - /* Remove the effect of an odd number of dummy entries */ - if ((so->fill - so->used) & 1) - hash ^= _shuffle_bits(-1); - - /* Factor in the number of active entries */ - hash ^= ((Py_uhash_t)PySet_GET_SIZE(self) + 1) * 1927868237UL; - - /* Disperse patterns arising in nested frozensets */ - hash ^= (hash >> 11) ^ (hash >> 25); - hash = hash * 69069U + 907133923UL; - - /* -1 is reserved as an error code */ - if (hash == (Py_uhash_t)-1) - hash = 590923713UL; - + hash *= PySet_GET_SIZE(self) + 1; + while (set_next(so, &pos, &entry)) { + /* Work to increase the bit dispersion for closely spaced hash + values. This is important because some use cases have many + combinations of a small number of elements with nearby + hashes so that many distinct combinations collapse to only + a handful of distinct hash values. */ + h = entry->hash; + hash ^= (h ^ (h << 16) ^ 89869747L) * 3644798167u; + } + hash = hash * 69069L + 907133923L; + if (hash == -1) + hash = 590923713L; so->hash = hash; return hash; } @@ -827,48 +826,26 @@ setiter_traverse(setiterobject *si, visitproc visit, void *arg) } static PyObject * -setiter_len(setiterobject *si, PyObject *Py_UNUSED(ignored)) +setiter_len(setiterobject *si) { Py_ssize_t len = 0; if (si->si_set != NULL && si->si_used == si->si_set->used) len = si->len; - return PyLong_FromSsize_t(len); + return PyInt_FromLong(len); } PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it))."); -static PyObject *setiter_iternext(setiterobject *si); - -static PyObject * -setiter_reduce(setiterobject *si, PyObject *Py_UNUSED(ignored)) -{ - _Py_IDENTIFIER(iter); - /* copy the iterator state */ - setiterobject tmp = *si; - Py_XINCREF(tmp.si_set); - - /* iterate the temporary into a list */ - PyObject *list = PySequence_List((PyObject*)&tmp); - Py_XDECREF(tmp.si_set); - if (list == NULL) { - return NULL; - } - return Py_BuildValue("N(N)", _PyEval_GetBuiltinId(&PyId_iter), list); -} - -PyDoc_STRVAR(reduce_doc, "Return state information for pickling."); - static PyMethodDef setiter_methods[] = { {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc}, - {"__reduce__", (PyCFunction)setiter_reduce, METH_NOARGS, reduce_doc}, {NULL, NULL} /* sentinel */ }; static PyObject *setiter_iternext(setiterobject *si) { PyObject *key; - Py_ssize_t i, mask; - setentry *entry; + register Py_ssize_t i, mask; + register setentry *entry; PySetObject *so = si->si_set; if (so == NULL) @@ -902,17 +879,17 @@ fail: return NULL; } -PyTypeObject PySetIter_Type = { +static PyTypeObject PySetIter_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) - "set_iterator", /* tp_name */ + "setiterator", /* tp_name */ sizeof(setiterobject), /* tp_basicsize */ 0, /* tp_itemsize */ /* methods */ (destructor)setiter_dealloc, /* tp_dealloc */ - 0, /* tp_vectorcall_offset */ + 0, /* tp_print */ 0, /* tp_getattr */ 0, /* tp_setattr */ - 0, /* tp_as_async */ + 0, /* tp_compare */ 0, /* tp_repr */ 0, /* tp_as_number */ 0, /* tp_as_sequence */ @@ -923,7 +900,7 @@ PyTypeObject PySetIter_Type = { PyObject_GenericGetAttr, /* tp_getattro */ 0, /* tp_setattro */ 0, /* tp_as_buffer */ - Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ 0, /* tp_doc */ (traverseproc)setiter_traverse, /* tp_traverse */ 0, /* tp_clear */ @@ -961,21 +938,25 @@ set_update_internal(PySetObject *so, PyObject *other) if (PyDict_CheckExact(other)) { PyObject *value; Py_ssize_t pos = 0; - Py_hash_t hash; - Py_ssize_t dictsize = PyDict_GET_SIZE(other); + long hash; + Py_ssize_t dictsize = PyDict_Size(other); /* Do one big resize at the start, rather than * incrementally resizing as we insert new keys. Expect * that there will be no (or few) overlapping keys. */ - if (dictsize < 0) + if (dictsize == -1) return -1; - if ((so->fill + dictsize)*5 >= so->mask*3) { + if ((so->fill + dictsize)*3 >= (so->mask+1)*2) { if (set_table_resize(so, (so->used + dictsize)*2) != 0) return -1; } while (_PyDict_Next(other, &pos, &key, &value, &hash)) { - if (set_add_entry(so, key, hash)) + setentry an_entry; + + an_entry.hash = hash; + an_entry.key = key; + if (set_add_entry(so, &an_entry) == -1) return -1; } return 0; @@ -986,7 +967,7 @@ set_update_internal(PySetObject *so, PyObject *other) return -1; while ((key = PyIter_Next(it)) != NULL) { - if (set_add_key(so, key)) { + if (set_add_key(so, key) == -1) { Py_DECREF(it); Py_DECREF(key); return -1; @@ -1006,7 +987,7 @@ set_update(PySetObject *so, PyObject *args) for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) { PyObject *other = PyTuple_GET_ITEM(args, i); - if (set_update_internal(so, other)) + if (set_update_internal(so, other) == -1) return NULL; } Py_RETURN_NONE; @@ -1015,31 +996,40 @@ set_update(PySetObject *so, PyObject *args) PyDoc_STRVAR(update_doc, "Update a set with the union of itself and others."); -/* XXX Todo: - If aligned memory allocations become available, make the - set object 64 byte aligned so that most of the fields - can be retrieved or updated in a single cache line. -*/ - static PyObject * make_new_set(PyTypeObject *type, PyObject *iterable) { - PySetObject *so; + register PySetObject *so = NULL; - so = (PySetObject *)type->tp_alloc(type, 0); - if (so == NULL) - return NULL; + if (dummy == NULL) { /* Auto-initialize dummy */ + dummy = PyString_FromString("<dummy key>"); + if (dummy == NULL) + return NULL; + } - so->fill = 0; - so->used = 0; - so->mask = PySet_MINSIZE - 1; - so->table = so->smalltable; - so->hash = -1; - so->finger = 0; + /* create PySetObject structure */ + if (numfree && + (type == &PySet_Type || type == &PyFrozenSet_Type)) { + so = free_list[--numfree]; + assert (so != NULL && PyAnySet_CheckExact(so)); + Py_TYPE(so) = type; + _Py_NewReference((PyObject *)so); + EMPTY_TO_MINSIZE(so); + PyObject_GC_Track(so); + } else { + so = (PySetObject *)type->tp_alloc(type, 0); + if (so == NULL) + return NULL; + /* tp_alloc has already zeroed the structure */ + assert(so->table == NULL && so->fill == 0 && so->used == 0); + INIT_NONZERO_SET_SLOTS(so); + } + + so->lookup = set_lookkey_string; so->weakreflist = NULL; if (iterable != NULL) { - if (set_update_internal(so, iterable)) { + if (set_update_internal(so, iterable) == -1) { Py_DECREF(so); return NULL; } @@ -1048,18 +1038,6 @@ make_new_set(PyTypeObject *type, PyObject *iterable) return (PyObject *)so; } -static PyObject * -make_new_set_basetype(PyTypeObject *type, PyObject *iterable) -{ - if (type != &PySet_Type && type != &PyFrozenSet_Type) { - if (PyType_IsSubtype(type, &PySet_Type)) - type = &PySet_Type; - else - type = &PyFrozenSet_Type; - } - return make_new_set(type, iterable); -} - /* The empty frozenset is a singleton */ static PyObject *emptyfrozenset = NULL; @@ -1068,7 +1046,7 @@ frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds) { PyObject *iterable = NULL, *result; - if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset", kwds)) + if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds)) return NULL; if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable)) @@ -1095,9 +1073,26 @@ frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds) return emptyfrozenset; } +void +PySet_Fini(void) +{ + PySetObject *so; + + while (numfree) { + numfree--; + so = free_list[numfree]; + PyObject_GC_Del(so); + } + Py_CLEAR(dummy); + Py_CLEAR(emptyfrozenset); +} + static PyObject * set_new(PyTypeObject *type, PyObject *args, PyObject *kwds) { + if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds)) + return NULL; + return make_new_set(type, NULL); } @@ -1108,8 +1103,10 @@ set_new(PyTypeObject *type, PyObject *args, PyObject *kwds) t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t The function always succeeds and it leaves both objects in a stable state. - Useful for operations that update in-place (by allowing an intermediate - result to be swapped into one of the original inputs). + Useful for creating temporary frozensets from sets for membership testing + in __contains__(), discard(), and remove(). Also useful for operations + that update in-place (by allowing an intermediate result to be swapped + into one of the original inputs). */ static void @@ -1117,8 +1114,9 @@ set_swap_bodies(PySetObject *a, PySetObject *b) { Py_ssize_t t; setentry *u; + setentry *(*f)(PySetObject *so, PyObject *key, long hash); setentry tab[PySet_MINSIZE]; - Py_hash_t h; + long h; t = a->fill; a->fill = b->fill; b->fill = t; t = a->used; a->used = b->used; b->used = t; @@ -1132,6 +1130,8 @@ set_swap_bodies(PySetObject *a, PySetObject *b) a->table = a->smalltable; b->table = u; + f = a->lookup; a->lookup = b->lookup; b->lookup = f; + if (a->table == a->smalltable || b->table == b->smalltable) { memcpy(tab, a->smalltable, sizeof(tab)); memcpy(a->smalltable, b->smalltable, sizeof(tab)); @@ -1148,25 +1148,25 @@ set_swap_bodies(PySetObject *a, PySetObject *b) } static PyObject * -set_copy(PySetObject *so, PyObject *Py_UNUSED(ignored)) +set_copy(PySetObject *so) { - return make_new_set_basetype(Py_TYPE(so), (PyObject *)so); + return make_new_set(Py_TYPE(so), (PyObject *)so); } static PyObject * -frozenset_copy(PySetObject *so, PyObject *Py_UNUSED(ignored)) +frozenset_copy(PySetObject *so) { if (PyFrozenSet_CheckExact(so)) { Py_INCREF(so); return (PyObject *)so; } - return set_copy(so, NULL); + return set_copy(so); } PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set."); static PyObject * -set_clear(PySetObject *so, PyObject *Py_UNUSED(ignored)) +set_clear(PySetObject *so) { set_clear_internal(so); Py_RETURN_NONE; @@ -1181,7 +1181,7 @@ set_union(PySetObject *so, PyObject *args) PyObject *other; Py_ssize_t i; - result = (PySetObject *)set_copy(so, NULL); + result = (PySetObject *)set_copy(so); if (result == NULL) return NULL; @@ -1189,7 +1189,7 @@ set_union(PySetObject *so, PyObject *args) other = PyTuple_GET_ITEM(args, i); if ((PyObject *)so == other) continue; - if (set_update_internal(result, other)) { + if (set_update_internal(result, other) == -1) { Py_DECREF(result); return NULL; } @@ -1207,15 +1207,17 @@ set_or(PySetObject *so, PyObject *other) { PySetObject *result; - if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) - Py_RETURN_NOTIMPLEMENTED; + if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) { + Py_INCREF(Py_NotImplemented); + return Py_NotImplemented; + } - result = (PySetObject *)set_copy(so, NULL); + result = (PySetObject *)set_copy(so); if (result == NULL) return NULL; if ((PyObject *)so == other) return (PyObject *)result; - if (set_update_internal(result, other)) { + if (set_update_internal(result, other) == -1) { Py_DECREF(result); return NULL; } @@ -1225,10 +1227,11 @@ set_or(PySetObject *so, PyObject *other) static PyObject * set_ior(PySetObject *so, PyObject *other) { - if (!PyAnySet_Check(other)) - Py_RETURN_NOTIMPLEMENTED; - - if (set_update_internal(so, other)) + if (!PyAnySet_Check(other)) { + Py_INCREF(Py_NotImplemented); + return Py_NotImplemented; + } + if (set_update_internal(so, other) == -1) return NULL; Py_INCREF(so); return (PyObject *)so; @@ -1239,13 +1242,11 @@ set_intersection(PySetObject *so, PyObject *other) { PySetObject *result; PyObject *key, *it, *tmp; - Py_hash_t hash; - int rv; if ((PyObject *)so == other) - return set_copy(so, NULL); + return set_copy(so); - result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL); + result = (PySetObject *)make_new_set(Py_TYPE(so), NULL); if (result == NULL) return NULL; @@ -1260,15 +1261,13 @@ set_intersection(PySetObject *so, PyObject *other) } while (set_next((PySetObject *)other, &pos, &entry)) { - key = entry->key; - hash = entry->hash; - rv = set_contains_entry(so, key, hash); - if (rv < 0) { + int rv = set_contains_entry(so, entry); + if (rv == -1) { Py_DECREF(result); return NULL; } if (rv) { - if (set_add_entry(result, key, hash)) { + if (set_add_entry(result, entry) == -1) { Py_DECREF(result); return NULL; } @@ -1284,15 +1283,32 @@ set_intersection(PySetObject *so, PyObject *other) } while ((key = PyIter_Next(it)) != NULL) { - hash = PyObject_Hash(key); - if (hash == -1) - goto error; - rv = set_contains_entry(so, key, hash); - if (rv < 0) - goto error; + int rv; + setentry entry; + long hash = PyObject_Hash(key); + + if (hash == -1) { + Py_DECREF(it); + Py_DECREF(result); + Py_DECREF(key); + return NULL; + } + entry.hash = hash; + entry.key = key; + rv = set_contains_entry(so, &entry); + if (rv == -1) { + Py_DECREF(it); + Py_DECREF(result); + Py_DECREF(key); + return NULL; + } if (rv) { - if (set_add_entry(result, key, hash)) - goto error; + if (set_add_entry(result, &entry) == -1) { + Py_DECREF(it); + Py_DECREF(result); + Py_DECREF(key); + return NULL; + } } Py_DECREF(key); } @@ -1302,11 +1318,6 @@ set_intersection(PySetObject *so, PyObject *other) return NULL; } return (PyObject *)result; - error: - Py_DECREF(it); - Py_DECREF(result); - Py_DECREF(key); - return NULL; } static PyObject * @@ -1316,7 +1327,7 @@ set_intersection_multi(PySetObject *so, PyObject *args) PyObject *result = (PyObject *)so; if (PyTuple_GET_SIZE(args) == 0) - return set_copy(so, NULL); + return set_copy(so); Py_INCREF(so); for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) { @@ -1333,9 +1344,9 @@ set_intersection_multi(PySetObject *so, PyObject *args) } PyDoc_STRVAR(intersection_doc, -"Return the intersection of two sets as a new set.\n\ +"Return the intersection of two or more sets as a new set.\n\ \n\ -(i.e. all elements that are in both sets.)"); +(i.e. elements that are common to all of the sets.)"); static PyObject * set_intersection_update(PySetObject *so, PyObject *other) @@ -1369,8 +1380,10 @@ PyDoc_STRVAR(intersection_update_doc, static PyObject * set_and(PySetObject *so, PyObject *other) { - if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) - Py_RETURN_NOTIMPLEMENTED; + if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) { + Py_INCREF(Py_NotImplemented); + return Py_NotImplemented; + } return set_intersection(so, other); } @@ -1379,8 +1392,10 @@ set_iand(PySetObject *so, PyObject *other) { PyObject *result; - if (!PyAnySet_Check(other)) - Py_RETURN_NOTIMPLEMENTED; + if (!PyAnySet_Check(other)) { + Py_INCREF(Py_NotImplemented); + return Py_NotImplemented; + } result = set_intersection_update(so, other); if (result == NULL) return NULL; @@ -1393,7 +1408,6 @@ static PyObject * set_isdisjoint(PySetObject *so, PyObject *other) { PyObject *key, *it, *tmp; - int rv; if ((PyObject *)so == other) { if (PySet_GET_SIZE(so) == 0) @@ -1412,8 +1426,8 @@ set_isdisjoint(PySetObject *so, PyObject *other) other = tmp; } while (set_next((PySetObject *)other, &pos, &entry)) { - rv = set_contains_entry(so, entry->key, entry->hash); - if (rv < 0) + int rv = set_contains_entry(so, entry); + if (rv == -1) return NULL; if (rv) Py_RETURN_FALSE; @@ -1426,16 +1440,20 @@ set_isdisjoint(PySetObject *so, PyObject *other) return NULL; while ((key = PyIter_Next(it)) != NULL) { - Py_hash_t hash = PyObject_Hash(key); + int rv; + setentry entry; + long hash = PyObject_Hash(key); if (hash == -1) { Py_DECREF(key); Py_DECREF(it); return NULL; } - rv = set_contains_entry(so, key, hash); + entry.hash = hash; + entry.key = key; + rv = set_contains_entry(so, &entry); Py_DECREF(key); - if (rv < 0) { + if (rv == -1) { Py_DECREF(it); return NULL; } @@ -1463,25 +1481,9 @@ set_difference_update_internal(PySetObject *so, PyObject *other) setentry *entry; Py_ssize_t pos = 0; - /* Optimization: When the other set is more than 8 times - larger than the base set, replace the other set with - interesection of the two sets. - */ - if ((PySet_GET_SIZE(other) >> 3) > PySet_GET_SIZE(so)) { - other = set_intersection(so, other); - if (other == NULL) - return -1; - } else { - Py_INCREF(other); - } - while (set_next((PySetObject *)other, &pos, &entry)) - if (set_discard_entry(so, entry->key, entry->hash) < 0) { - Py_DECREF(other); + if (set_discard_entry(so, entry) == -1) return -1; - } - - Py_DECREF(other); } else { PyObject *key, *it; it = PyObject_GetIter(other); @@ -1489,7 +1491,7 @@ set_difference_update_internal(PySetObject *so, PyObject *other) return -1; while ((key = PyIter_Next(it)) != NULL) { - if (set_discard_key(so, key) < 0) { + if (set_discard_key(so, key) == -1) { Py_DECREF(it); Py_DECREF(key); return -1; @@ -1500,8 +1502,8 @@ set_difference_update_internal(PySetObject *so, PyObject *other) if (PyErr_Occurred()) return -1; } - /* If more than 1/4th are dummies, then resize them away. */ - if ((size_t)(so->fill - so->used) <= (size_t)so->mask / 4) + /* If more than 1/5 are dummies, then resize them away. */ + if ((so->fill - so->used) * 5 < so->mask) return 0; return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4); } @@ -1513,7 +1515,7 @@ set_difference_update(PySetObject *so, PyObject *args) for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) { PyObject *other = PyTuple_GET_ITEM(args, i); - if (set_difference_update_internal(so, other)) + if (set_difference_update_internal(so, other) == -1) return NULL; } Py_RETURN_NONE; @@ -1523,60 +1525,39 @@ PyDoc_STRVAR(difference_update_doc, "Remove all elements of another set from this set."); static PyObject * -set_copy_and_difference(PySetObject *so, PyObject *other) -{ - PyObject *result; - - result = set_copy(so, NULL); - if (result == NULL) - return NULL; - if (set_difference_update_internal((PySetObject *) result, other) == 0) - return result; - Py_DECREF(result); - return NULL; -} - -static PyObject * set_difference(PySetObject *so, PyObject *other) { PyObject *result; - PyObject *key; - Py_hash_t hash; setentry *entry; - Py_ssize_t pos = 0, other_size; - int rv; - - if (PyAnySet_Check(other)) { - other_size = PySet_GET_SIZE(other); - } - else if (PyDict_CheckExact(other)) { - other_size = PyDict_GET_SIZE(other); - } - else { - return set_copy_and_difference(so, other); - } + Py_ssize_t pos = 0; - /* If len(so) much more than len(other), it's more efficient to simply copy - * so and then iterate other looking for common elements. */ - if ((PySet_GET_SIZE(so) >> 2) > other_size) { - return set_copy_and_difference(so, other); + if (!PyAnySet_Check(other) && !PyDict_CheckExact(other)) { + result = set_copy(so); + if (result == NULL) + return NULL; + if (set_difference_update_internal((PySetObject *)result, other) != -1) + return result; + Py_DECREF(result); + return NULL; } - result = make_new_set_basetype(Py_TYPE(so), NULL); + result = make_new_set(Py_TYPE(so), NULL); if (result == NULL) return NULL; if (PyDict_CheckExact(other)) { while (set_next(so, &pos, &entry)) { - key = entry->key; - hash = entry->hash; - rv = _PyDict_Contains(other, key, hash); + setentry entrycopy; + int rv; + entrycopy.hash = entry->hash; + entrycopy.key = entry->key; + rv = _PyDict_Contains(other, entry->key, entry->hash); if (rv < 0) { Py_DECREF(result); return NULL; } if (!rv) { - if (set_add_entry((PySetObject *)result, key, hash)) { + if (set_add_entry((PySetObject *)result, &entrycopy) == -1) { Py_DECREF(result); return NULL; } @@ -1585,17 +1566,14 @@ set_difference(PySetObject *so, PyObject *other) return result; } - /* Iterate over so, checking for common elements in other. */ while (set_next(so, &pos, &entry)) { - key = entry->key; - hash = entry->hash; - rv = set_contains_entry((PySetObject *)other, key, hash); - if (rv < 0) { + int rv = set_contains_entry((PySetObject *)other, entry); + if (rv == -1) { Py_DECREF(result); return NULL; } if (!rv) { - if (set_add_entry((PySetObject *)result, key, hash)) { + if (set_add_entry((PySetObject *)result, entry) == -1) { Py_DECREF(result); return NULL; } @@ -1611,7 +1589,7 @@ set_difference_multi(PySetObject *so, PyObject *args) PyObject *result, *other; if (PyTuple_GET_SIZE(args) == 0) - return set_copy(so, NULL); + return set_copy(so); other = PyTuple_GET_ITEM(args, 0); result = set_difference(so, other); @@ -1620,7 +1598,7 @@ set_difference_multi(PySetObject *so, PyObject *args) for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) { other = PyTuple_GET_ITEM(args, i); - if (set_difference_update_internal((PySetObject *)result, other)) { + if (set_difference_update_internal((PySetObject *)result, other) == -1) { Py_DECREF(result); return NULL; } @@ -1635,17 +1613,21 @@ PyDoc_STRVAR(difference_doc, static PyObject * set_sub(PySetObject *so, PyObject *other) { - if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) - Py_RETURN_NOTIMPLEMENTED; + if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) { + Py_INCREF(Py_NotImplemented); + return Py_NotImplemented; + } return set_difference(so, other); } static PyObject * set_isub(PySetObject *so, PyObject *other) { - if (!PyAnySet_Check(other)) - Py_RETURN_NOTIMPLEMENTED; - if (set_difference_update_internal(so, other)) + if (!PyAnySet_Check(other)) { + Py_INCREF(Py_NotImplemented); + return Py_NotImplemented; + } + if (set_difference_update_internal(so, other) == -1) return NULL; Py_INCREF(so); return (PyObject *)so; @@ -1657,24 +1639,29 @@ set_symmetric_difference_update(PySetObject *so, PyObject *other) PySetObject *otherset; PyObject *key; Py_ssize_t pos = 0; - Py_hash_t hash; setentry *entry; - int rv; if ((PyObject *)so == other) - return set_clear(so, NULL); + return set_clear(so); if (PyDict_CheckExact(other)) { PyObject *value; + int rv; + long hash; while (_PyDict_Next(other, &pos, &key, &value, &hash)) { + setentry an_entry; + Py_INCREF(key); - rv = set_discard_entry(so, key, hash); - if (rv < 0) { + an_entry.hash = hash; + an_entry.key = key; + + rv = set_discard_entry(so, &an_entry); + if (rv == -1) { Py_DECREF(key); return NULL; } if (rv == DISCARD_NOTFOUND) { - if (set_add_entry(so, key, hash)) { + if (set_add_entry(so, &an_entry) == -1) { Py_DECREF(key); return NULL; } @@ -1688,21 +1675,19 @@ set_symmetric_difference_update(PySetObject *so, PyObject *other) Py_INCREF(other); otherset = (PySetObject *)other; } else { - otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other); + otherset = (PySetObject *)make_new_set(Py_TYPE(so), other); if (otherset == NULL) return NULL; } while (set_next(otherset, &pos, &entry)) { - key = entry->key; - hash = entry->hash; - rv = set_discard_entry(so, key, hash); - if (rv < 0) { + int rv = set_discard_entry(so, entry); + if (rv == -1) { Py_DECREF(otherset); return NULL; } if (rv == DISCARD_NOTFOUND) { - if (set_add_entry(so, key, hash)) { + if (set_add_entry(so, entry) == -1) { Py_DECREF(otherset); return NULL; } @@ -1721,7 +1706,7 @@ set_symmetric_difference(PySetObject *so, PyObject *other) PyObject *rv; PySetObject *otherset; - otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other); + otherset = (PySetObject *)make_new_set(Py_TYPE(so), other); if (otherset == NULL) return NULL; rv = set_symmetric_difference_update(otherset, (PyObject *)so); @@ -1741,8 +1726,10 @@ PyDoc_STRVAR(symmetric_difference_doc, static PyObject * set_xor(PySetObject *so, PyObject *other) { - if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) - Py_RETURN_NOTIMPLEMENTED; + if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) { + Py_INCREF(Py_NotImplemented); + return Py_NotImplemented; + } return set_symmetric_difference(so, other); } @@ -1751,8 +1738,10 @@ set_ixor(PySetObject *so, PyObject *other) { PyObject *result; - if (!PyAnySet_Check(other)) - Py_RETURN_NOTIMPLEMENTED; + if (!PyAnySet_Check(other)) { + Py_INCREF(Py_NotImplemented); + return Py_NotImplemented; + } result = set_symmetric_difference_update(so, other); if (result == NULL) return NULL; @@ -1766,7 +1755,6 @@ set_issubset(PySetObject *so, PyObject *other) { setentry *entry; Py_ssize_t pos = 0; - int rv; if (!PyAnySet_Check(other)) { PyObject *tmp, *result; @@ -1781,8 +1769,8 @@ set_issubset(PySetObject *so, PyObject *other) Py_RETURN_FALSE; while (set_next(so, &pos, &entry)) { - rv = set_contains_entry((PySetObject *)other, entry->key, entry->hash); - if (rv < 0) + int rv = set_contains_entry((PySetObject *)other, entry); + if (rv == -1) return NULL; if (!rv) Py_RETURN_FALSE; @@ -1816,9 +1804,10 @@ set_richcompare(PySetObject *v, PyObject *w, int op) PyObject *r1; int r2; - if(!PyAnySet_Check(w)) - Py_RETURN_NOTIMPLEMENTED; - + if(!PyAnySet_Check(w)) { + Py_INCREF(Py_NotImplemented); + return Py_NotImplemented; + } switch (op) { case Py_EQ: if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w)) @@ -1850,13 +1839,21 @@ set_richcompare(PySetObject *v, PyObject *w, int op) Py_RETURN_FALSE; return set_issuperset(v, w); } - Py_RETURN_NOTIMPLEMENTED; + Py_INCREF(Py_NotImplemented); + return Py_NotImplemented; +} + +static int +set_nocmp(PyObject *self, PyObject *other) +{ + PyErr_SetString(PyExc_TypeError, "cannot compare sets using cmp()"); + return -1; } static PyObject * set_add(PySetObject *so, PyObject *key) { - if (set_add_key(so, key)) + if (set_add_key(so, key) == -1) return NULL; Py_RETURN_NONE; } @@ -1873,7 +1870,7 @@ set_contains(PySetObject *so, PyObject *key) int rv; rv = set_contains_key(so, key); - if (rv < 0) { + if (rv == -1) { if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError)) return -1; PyErr_Clear(); @@ -1892,7 +1889,7 @@ set_direct_contains(PySetObject *so, PyObject *key) long result; result = set_contains(so, key); - if (result < 0) + if (result == -1) return NULL; return PyBool_FromLong(result); } @@ -1906,7 +1903,7 @@ set_remove(PySetObject *so, PyObject *key) int rv; rv = set_discard_key(so, key); - if (rv < 0) { + if (rv == -1) { if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError)) return NULL; PyErr_Clear(); @@ -1915,12 +1912,12 @@ set_remove(PySetObject *so, PyObject *key) return NULL; rv = set_discard_key(so, tmpkey); Py_DECREF(tmpkey); - if (rv < 0) + if (rv == -1) return NULL; } if (rv == DISCARD_NOTFOUND) { - _PyErr_SetKeyError(key); + set_key_error(key); return NULL; } Py_RETURN_NONE; @@ -1938,7 +1935,7 @@ set_discard(PySetObject *so, PyObject *key) int rv; rv = set_discard_key(so, key); - if (rv < 0) { + if (rv == -1) { if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError)) return NULL; PyErr_Clear(); @@ -1947,7 +1944,7 @@ set_discard(PySetObject *so, PyObject *key) return NULL; rv = set_discard_key(so, tmpkey); Py_DECREF(tmpkey); - if (rv < 0) + if (rv == -1) return NULL; } Py_RETURN_NONE; @@ -1959,10 +1956,9 @@ PyDoc_STRVAR(discard_doc, If the element is not a member, do nothing."); static PyObject * -set_reduce(PySetObject *so, PyObject *Py_UNUSED(ignored)) +set_reduce(PySetObject *so) { PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL; - _Py_IDENTIFIER(__dict__); keys = PySequence_List((PyObject *)so); if (keys == NULL) @@ -1970,10 +1966,9 @@ set_reduce(PySetObject *so, PyObject *Py_UNUSED(ignored)) args = PyTuple_Pack(1, keys); if (args == NULL) goto done; - if (_PyObject_LookupAttrId((PyObject *)so, &PyId___dict__, &dict) < 0) { - goto done; - } + dict = PyObject_GetAttrString((PyObject *)so, "__dict__"); if (dict == NULL) { + PyErr_Clear(); dict = Py_None; Py_INCREF(dict); } @@ -1985,15 +1980,17 @@ done: return result; } +PyDoc_STRVAR(reduce_doc, "Return state information for pickling."); + static PyObject * -set_sizeof(PySetObject *so, PyObject *Py_UNUSED(ignored)) +set_sizeof(PySetObject *so) { Py_ssize_t res; res = _PyObject_SIZE(Py_TYPE(so)); if (so->table != so->smalltable) res = res + (so->mask + 1) * sizeof(setentry); - return PyLong_FromSsize_t(res); + return PyInt_FromSsize_t(res); } PyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes"); @@ -2002,12 +1999,13 @@ set_init(PySetObject *self, PyObject *args, PyObject *kwds) { PyObject *iterable = NULL; - if (!_PyArg_NoKeywords("set", kwds)) + if (!PyAnySet_Check(self)) + return -1; + if (PySet_Check(self) && !_PyArg_NoKeywords("set()", kwds)) return -1; if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable)) return -1; - if (self->fill) - set_clear_internal(self); + set_clear_internal(self); self->hash = -1; if (iterable == NULL) return 0; @@ -2028,7 +2026,7 @@ static PySequenceMethods set_as_sequence = { /* set object ********************************************************/ #ifdef Py_DEBUG -static PyObject *test_c_api(PySetObject *so, PyObject *Py_UNUSED(ignored)); +static PyObject *test_c_api(PySetObject *so); PyDoc_STRVAR(test_c_api_doc, "Exercises C API. Returns True.\n\ All is well if assertions don't fail."); @@ -2086,25 +2084,30 @@ static PyNumberMethods set_as_number = { 0, /*nb_add*/ (binaryfunc)set_sub, /*nb_subtract*/ 0, /*nb_multiply*/ + 0, /*nb_divide*/ 0, /*nb_remainder*/ 0, /*nb_divmod*/ 0, /*nb_power*/ 0, /*nb_negative*/ 0, /*nb_positive*/ 0, /*nb_absolute*/ - 0, /*nb_bool*/ + 0, /*nb_nonzero*/ 0, /*nb_invert*/ 0, /*nb_lshift*/ 0, /*nb_rshift*/ (binaryfunc)set_and, /*nb_and*/ (binaryfunc)set_xor, /*nb_xor*/ (binaryfunc)set_or, /*nb_or*/ + 0, /*nb_coerce*/ 0, /*nb_int*/ - 0, /*nb_reserved*/ + 0, /*nb_long*/ 0, /*nb_float*/ + 0, /*nb_oct*/ + 0, /*nb_hex*/ 0, /*nb_inplace_add*/ (binaryfunc)set_isub, /*nb_inplace_subtract*/ 0, /*nb_inplace_multiply*/ + 0, /*nb_inplace_divide*/ 0, /*nb_inplace_remainder*/ 0, /*nb_inplace_power*/ 0, /*nb_inplace_lshift*/ @@ -2127,28 +2130,28 @@ PyTypeObject PySet_Type = { 0, /* tp_itemsize */ /* methods */ (destructor)set_dealloc, /* tp_dealloc */ - 0, /* tp_vectorcall_offset */ + (printfunc)set_tp_print, /* tp_print */ 0, /* tp_getattr */ 0, /* tp_setattr */ - 0, /* tp_as_async */ + set_nocmp, /* tp_compare */ (reprfunc)set_repr, /* tp_repr */ &set_as_number, /* tp_as_number */ &set_as_sequence, /* tp_as_sequence */ 0, /* tp_as_mapping */ - PyObject_HashNotImplemented, /* tp_hash */ + (hashfunc)PyObject_HashNotImplemented, /* tp_hash */ 0, /* tp_call */ 0, /* tp_str */ PyObject_GenericGetAttr, /* tp_getattro */ 0, /* tp_setattro */ 0, /* tp_as_buffer */ - Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_CHECKTYPES | Py_TPFLAGS_BASETYPE, /* tp_flags */ set_doc, /* tp_doc */ (traverseproc)set_traverse, /* tp_traverse */ (inquiry)set_clear_internal, /* tp_clear */ (richcmpfunc)set_richcompare, /* tp_richcompare */ - offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */ - (getiterfunc)set_iter, /* tp_iter */ + offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */ + (getiterfunc)set_iter, /* tp_iter */ 0, /* tp_iternext */ set_methods, /* tp_methods */ 0, /* tp_members */ @@ -2174,7 +2177,7 @@ static PyMethodDef frozenset_methods[] = { copy_doc}, {"difference", (PyCFunction)set_difference_multi, METH_VARARGS, difference_doc}, - {"intersection", (PyCFunction)set_intersection_multi, METH_VARARGS, + {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS, intersection_doc}, {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O, isdisjoint_doc}, @@ -2197,13 +2200,14 @@ static PyNumberMethods frozenset_as_number = { 0, /*nb_add*/ (binaryfunc)set_sub, /*nb_subtract*/ 0, /*nb_multiply*/ + 0, /*nb_divide*/ 0, /*nb_remainder*/ 0, /*nb_divmod*/ 0, /*nb_power*/ 0, /*nb_negative*/ 0, /*nb_positive*/ 0, /*nb_absolute*/ - 0, /*nb_bool*/ + 0, /*nb_nonzero*/ 0, /*nb_invert*/ 0, /*nb_lshift*/ 0, /*nb_rshift*/ @@ -2225,10 +2229,10 @@ PyTypeObject PyFrozenSet_Type = { 0, /* tp_itemsize */ /* methods */ (destructor)set_dealloc, /* tp_dealloc */ - 0, /* tp_vectorcall_offset */ + (printfunc)set_tp_print, /* tp_print */ 0, /* tp_getattr */ 0, /* tp_setattr */ - 0, /* tp_as_async */ + set_nocmp, /* tp_compare */ (reprfunc)set_repr, /* tp_repr */ &frozenset_as_number, /* tp_as_number */ &set_as_sequence, /* tp_as_sequence */ @@ -2239,13 +2243,13 @@ PyTypeObject PyFrozenSet_Type = { PyObject_GenericGetAttr, /* tp_getattro */ 0, /* tp_setattro */ 0, /* tp_as_buffer */ - Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_CHECKTYPES | Py_TPFLAGS_BASETYPE, /* tp_flags */ frozenset_doc, /* tp_doc */ (traverseproc)set_traverse, /* tp_traverse */ (inquiry)set_clear_internal, /* tp_clear */ (richcmpfunc)set_richcompare, /* tp_richcompare */ - offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */ + offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */ (getiterfunc)set_iter, /* tp_iter */ 0, /* tp_iternext */ frozenset_methods, /* tp_methods */ @@ -2329,19 +2333,22 @@ PySet_Add(PyObject *anyset, PyObject *key) } int -PySet_ClearFreeList(void) +_PySet_Next(PyObject *set, Py_ssize_t *pos, PyObject **key) { - return 0; -} + setentry *entry_ptr; -void -_PySet_Fini(void) -{ - Py_CLEAR(emptyfrozenset); + if (!PyAnySet_Check(set)) { + PyErr_BadInternalCall(); + return -1; + } + if (set_next((PySetObject *)set, pos, &entry_ptr) == 0) + return 0; + *key = entry_ptr->key; + return 1; } int -_PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash) +_PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, long *hash) { setentry *entry; @@ -2363,7 +2370,7 @@ PySet_Pop(PyObject *set) PyErr_BadInternalCall(); return NULL; } - return set_pop((PySetObject *)set, NULL); + return set_pop((PySetObject *)set); } int @@ -2376,9 +2383,6 @@ _PySet_Update(PyObject *set, PyObject *iterable) return set_update_internal((PySetObject *)set, iterable); } -/* Exported for the gdb plugin's benefit. */ -PyObject *_PySet_Dummy = dummy; - #ifdef Py_DEBUG /* Test code to be called with any three element set. @@ -2392,14 +2396,13 @@ PyObject *_PySet_Dummy = dummy; } while(0) static PyObject * -test_c_api(PySetObject *so, PyObject *Py_UNUSED(ignored)) +test_c_api(PySetObject *so) { Py_ssize_t count; - const char *s; + char *s; Py_ssize_t i; - PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x=NULL; + PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x; PyObject *ob = (PyObject *)so; - Py_hash_t hash; PyObject *str; /* Verify preconditions */ @@ -2408,11 +2411,11 @@ test_c_api(PySetObject *so, PyObject *Py_UNUSED(ignored)) assert(!PyFrozenSet_CheckExact(ob)); /* so.clear(); so |= set("abc"); */ - str = PyUnicode_FromString("abc"); + str = PyString_FromString("abc"); if (str == NULL) return NULL; set_clear_internal(so); - if (set_update_internal(so, str)) { + if (set_update_internal(so, str) == -1) { Py_DECREF(str); return NULL; } @@ -2462,8 +2465,8 @@ test_c_api(PySetObject *so, PyObject *Py_UNUSED(ignored)) /* Exercise direct iteration */ i = 0, count = 0; - while (_PySet_NextEntry((PyObject *)dup, &i, &x, &hash)) { - s = PyUnicode_AsUTF8(x); + while (_PySet_Next((PyObject *)dup, &i, &x)) { + s = PyString_AsString(x); assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c')); count++; } @@ -2520,46 +2523,3 @@ test_c_api(PySetObject *so, PyObject *Py_UNUSED(ignored)) #undef assertRaises #endif - -/***** Dummy Struct *************************************************/ - -static PyObject * -dummy_repr(PyObject *op) -{ - return PyUnicode_FromString("<dummy key>"); -} - -static void -dummy_dealloc(PyObject* ignore) -{ - Py_FatalError("deallocating <dummy key>"); -} - -static PyTypeObject _PySetDummy_Type = { - PyVarObject_HEAD_INIT(&PyType_Type, 0) - "<dummy key> type", - 0, - 0, - dummy_dealloc, /*tp_dealloc*/ /*never called*/ - 0, /*tp_vectorcall_offset*/ - 0, /*tp_getattr*/ - 0, /*tp_setattr*/ - 0, /*tp_as_async*/ - dummy_repr, /*tp_repr*/ - 0, /*tp_as_number*/ - 0, /*tp_as_sequence*/ - 0, /*tp_as_mapping*/ - 0, /*tp_hash */ - 0, /*tp_call */ - 0, /*tp_str */ - 0, /*tp_getattro */ - 0, /*tp_setattro */ - 0, /*tp_as_buffer */ - Py_TPFLAGS_DEFAULT, /*tp_flags */ -}; - -static PyObject _dummy_struct = { - _PyObject_EXTRA_INIT - 2, &_PySetDummy_Type -}; - |