diff options
Diffstat (limited to 'AppPkg/Applications/Python/Python-2.7.2/Objects/setobject.c')
| -rw-r--r-- | AppPkg/Applications/Python/Python-2.7.2/Objects/setobject.c | 2518 |
1 files changed, 2518 insertions, 0 deletions
diff --git a/AppPkg/Applications/Python/Python-2.7.2/Objects/setobject.c b/AppPkg/Applications/Python/Python-2.7.2/Objects/setobject.c new file mode 100644 index 0000000000..40a127c5e5 --- /dev/null +++ b/AppPkg/Applications/Python/Python-2.7.2/Objects/setobject.c @@ -0,0 +1,2518 @@ +
+/* set object implementation
+ Written and maintained by Raymond D. Hettinger <python@rcn.com>
+ Derived from Lib/sets.py and Objects/dictobject.c.
+
+ Copyright (c) 2003-2007 Python Software Foundation.
+ All rights reserved.
+*/
+
+#include "Python.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 = NULL; /* Initialized by first call to make_new_set() */
+
+#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)
+
+#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)
+
+/* 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;
+
+/*
+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, 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;
+ register int cmp;
+ PyObject *startkey;
+
+ 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) {
+ 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);
+ }
+ }
+ 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)
+ 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;
+}
+
+/*
+ * 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;
+ }
+
+ /* 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)
+ 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;
+ }
+ assert(0); /* NOT REACHED */
+ return 0;
+}
+
+/*
+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;
+ typedef setentry *(*lookupfunc)(PySetObject *, PyObject *, long);
+
+ 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;
+}
+
+/*
+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,
+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(register PySetObject *so, PyObject *key, long hash)
+{
+ register size_t i;
+ register size_t perturb;
+ register size_t mask = (size_t)so->mask;
+ setentry *table = so->table;
+ register setentry *entry;
+
+ 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];
+ }
+ so->fill++;
+ entry->key = key;
+ entry->hash = hash;
+ so->used++;
+}
+
+/*
+Restructure the table by allocating a new table and reinserting all
+keys again. When entries have been deleted, the new table may
+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 i;
+ int is_oldtable_malloced;
+ setentry small_copy[PySet_MINSIZE];
+
+ assert(minused >= 0);
+
+ /* Find the smallest table size > minused. */
+ for (newsize = PySet_MINSIZE;
+ newsize <= minused && newsize > 0;
+ newsize <<= 1)
+ ;
+ if (newsize <= 0) {
+ PyErr_NoMemory();
+ return -1;
+ }
+
+ /* Get space for a new table. */
+ oldtable = so->table;
+ assert(oldtable != NULL);
+ is_oldtable_malloced = oldtable != so->smalltable;
+
+ if (newsize == PySet_MINSIZE) {
+ /* A large table is shrinking, or we can't get any smaller. */
+ newtable = so->smalltable;
+ if (newtable == oldtable) {
+ if (so->fill == so->used) {
+ /* No dummies, so no point doing anything. */
+ return 0;
+ }
+ /* We're not going to resize it, but rebuild the
+ table anyway to purge old dummy entries.
+ Subtle: This is *necessary* if fill==size,
+ as set_lookkey needs at least one virgin slot to
+ terminate failing searches. If fill < size, it's
+ merely desirable, as dummies slow searches. */
+ assert(so->fill > so->used);
+ memcpy(small_copy, oldtable, sizeof(small_copy));
+ oldtable = small_copy;
+ }
+ }
+ else {
+ newtable = PyMem_NEW(setentry, newsize);
+ if (newtable == NULL) {
+ PyErr_NoMemory();
+ return -1;
+ }
+ }
+
+ /* Make the set empty, using the new table. */
+ assert(newtable != oldtable);
+ 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 */
+ 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);
+ }
+ }
+
+ if (is_oldtable_malloced)
+ PyMem_DEL(oldtable);
+ return 0;
+}
+
+/* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
+
+static int
+set_add_entry(register PySetObject *so, setentry *entry)
+{
+ register Py_ssize_t n_used;
+ PyObject *key = entry->key;
+ long hash = entry->hash;
+
+ 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, setentry *oldentry)
+{ register setentry *entry;
+ PyObject *old_key;
+
+ entry = (so->lookup)(so, oldentry->key, oldentry->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_discard_key(PySetObject *so, PyObject *key)
+{
+ register long hash;
+ register setentry *entry;
+ PyObject *old_key;
+
+ assert (PyAnySet_Check(so));
+ if (!PyString_CheckExact(key) ||
+ (hash = ((PyStringObject *) key)->ob_shash) == -1) {
+ hash = PyObject_Hash(key);
+ if (hash == -1)
+ return -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, *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
+ * (voice of experience), we have to make the set empty before
+ * clearing the slots, and never refer to anything via so->ref while
+ * clearing.
+ */
+ fill = so->fill;
+ if (table_is_malloced)
+ EMPTY_TO_MINSIZE(so);
+
+ else if (fill > 0) {
+ /* It's a small table with something that needs to be cleared.
+ * Afraid the only safe way is to copy the set entries into
+ * another small table first.
+ */
+ memcpy(small_copy, table, sizeof(small_copy));
+ table = small_copy;
+ EMPTY_TO_MINSIZE(so);
+ }
+ /* else it's a small table that's already empty */
+
+ /* Now we can finally clear things. If C had refcounts, we could
+ * 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; 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)
+ PyMem_DEL(table);
+ return 0;
+}
+
+/*
+ * Iterate over a set table. Use like so:
+ *
+ * Py_ssize_t pos;
+ * setentry *entry;
+ * pos = 0; # important! pos should not otherwise be changed by you
+ * while (set_next(yourset, &pos, &entry)) {
+ * Refer to borrowed reference in entry->key.
+ * }
+ *
+ * CAUTION: In general, it isn't safe to use set_next in a loop that
+ * mutates the table.
+ */
+static int
+set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)
+{
+ Py_ssize_t i;
+ Py_ssize_t mask;
+ register setentry *table;
+
+ assert (PyAnySet_Check(so));
+ i = *pos_ptr;
+ assert(i >= 0);
+ table = so->table;
+ mask = so->mask;
+ while (i <= mask && (table[i].key == NULL || table[i].key == dummy))
+ i++;
+ *pos_ptr = i+1;
+ if (i > mask)
+ return 0;
+ assert(table[i].key != NULL);
+ *entry_ptr = &table[i];
+ return 1;
+}
+
+static void
+set_dealloc(PySetObject *so)
+{
+ register setentry *entry;
+ Py_ssize_t fill = so->fill;
+ PyObject_GC_UnTrack(so);
+ Py_TRASHCAN_SAFE_BEGIN(so)
+ if (so->weakreflist != NULL)
+ PyObject_ClearWeakRefs((PyObject *) so);
+
+ for (entry = so->table; fill > 0; entry++) {
+ if (entry->key) {
+ --fill;
+ Py_DECREF(entry->key);
+ }
+ }
+ if (so->table != so->smalltable)
+ PyMem_DEL(so->table);
+ 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(...)", so->ob_type->tp_name);
+ Py_END_ALLOW_THREADS
+ return 0;
+ }
+
+ Py_BEGIN_ALLOW_THREADS
+ fprintf(fp, "%s([", so->ob_type->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 *keys, *result=NULL, *listrepr;
+ int status = Py_ReprEnter((PyObject*)so);
+
+ if (status != 0) {
+ if (status < 0)
+ return NULL;
+ return PyString_FromFormat("%s(...)", so->ob_type->tp_name);
+ }
+
+ keys = PySequence_List((PyObject *)so);
+ if (keys == NULL)
+ goto done;
+ listrepr = PyObject_Repr(keys);
+ Py_DECREF(keys);
+ if (listrepr == NULL)
+ goto done;
+
+ result = PyString_FromFormat("%s(%s)", so->ob_type->tp_name,
+ PyString_AS_STRING(listrepr));
+ Py_DECREF(listrepr);
+done:
+ Py_ReprLeave((PyObject*)so);
+ return result;
+}
+
+static Py_ssize_t
+set_len(PyObject *so)
+{
+ return ((PySetObject *)so)->used;
+}
+
+static int
+set_merge(PySetObject *so, PyObject *otherset)
+{
+ PySetObject *other;
+ PyObject *key;
+ 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({}); 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)*3 >= (so->mask+1)*2) {
+ if (set_table_resize(so, (so->used + other->used)*2) != 0)
+ return -1;
+ }
+ 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;
+ }
+ }
+ }
+ return 0;
+}
+
+static int
+set_contains_key(PySetObject *so, PyObject *key)
+{
+ long hash;
+ setentry *entry;
+
+ if (!PyString_CheckExact(key) ||
+ (hash = ((PyStringObject *) key)->ob_shash) == -1) {
+ hash = PyObject_Hash(key);
+ if (hash == -1)
+ return -1;
+ }
+ 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)
+{
+ 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;
+ }
+
+ /* 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;
+ so->used--;
+ so->table[0].hash = i + 1; /* next place to start */
+ return key;
+}
+
+PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\
+Raises KeyError if the set is empty.");
+
+static int
+set_traverse(PySetObject *so, visitproc visit, void *arg)
+{
+ Py_ssize_t pos = 0;
+ setentry *entry;
+
+ while (set_next(so, &pos, &entry))
+ Py_VISIT(entry->key);
+ return 0;
+}
+
+static long
+frozenset_hash(PyObject *self)
+{
+ PySetObject *so = (PySetObject *)self;
+ long h, hash = 1927868237L;
+ setentry *entry;
+ Py_ssize_t pos = 0;
+
+ if (so->hash != -1)
+ return so->hash;
+
+ hash *= PySet_GET_SIZE(self) + 1;
+ while (set_next(so, &pos, &entry)) {
+ /* Work to increase the bit dispersion for closely spaced hash
+ values. The 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;
+}
+
+/***** Set iterator type ***********************************************/
+
+typedef struct {
+ PyObject_HEAD
+ PySetObject *si_set; /* Set to NULL when iterator is exhausted */
+ Py_ssize_t si_used;
+ Py_ssize_t si_pos;
+ Py_ssize_t len;
+} setiterobject;
+
+static void
+setiter_dealloc(setiterobject *si)
+{
+ Py_XDECREF(si->si_set);
+ PyObject_GC_Del(si);
+}
+
+static int
+setiter_traverse(setiterobject *si, visitproc visit, void *arg)
+{
+ Py_VISIT(si->si_set);
+ return 0;
+}
+
+static PyObject *
+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 PyInt_FromLong(len);
+}
+
+PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
+
+static PyMethodDef setiter_methods[] = {
+ {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
+ {NULL, NULL} /* sentinel */
+};
+
+static PyObject *setiter_iternext(setiterobject *si)
+{
+ PyObject *key;
+ register Py_ssize_t i, mask;
+ register setentry *entry;
+ PySetObject *so = si->si_set;
+
+ if (so == NULL)
+ return NULL;
+ assert (PyAnySet_Check(so));
+
+ if (si->si_used != so->used) {
+ PyErr_SetString(PyExc_RuntimeError,
+ "Set changed size during iteration");
+ si->si_used = -1; /* Make this state sticky */
+ return NULL;
+ }
+
+ i = si->si_pos;
+ assert(i>=0);
+ entry = so->table;
+ mask = so->mask;
+ while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
+ i++;
+ si->si_pos = i+1;
+ if (i > mask)
+ goto fail;
+ si->len--;
+ key = entry[i].key;
+ Py_INCREF(key);
+ return key;
+
+fail:
+ Py_DECREF(so);
+ si->si_set = NULL;
+ return NULL;
+}
+
+static PyTypeObject PySetIter_Type = {
+ PyVarObject_HEAD_INIT(&PyType_Type, 0)
+ "setiterator", /* tp_name */
+ sizeof(setiterobject), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ /* methods */
+ (destructor)setiter_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ 0, /* tp_repr */
+ 0, /* tp_as_number */
+ 0, /* tp_as_sequence */
+ 0, /* tp_as_mapping */
+ 0, /* 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,/* tp_flags */
+ 0, /* tp_doc */
+ (traverseproc)setiter_traverse, /* tp_traverse */
+ 0, /* tp_clear */
+ 0, /* tp_richcompare */
+ 0, /* tp_weaklistoffset */
+ PyObject_SelfIter, /* tp_iter */
+ (iternextfunc)setiter_iternext, /* tp_iternext */
+ setiter_methods, /* tp_methods */
+ 0,
+};
+
+static PyObject *
+set_iter(PySetObject *so)
+{
+ setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type);
+ if (si == NULL)
+ return NULL;
+ Py_INCREF(so);
+ si->si_set = so;
+ si->si_used = so->used;
+ si->si_pos = 0;
+ si->len = so->used;
+ _PyObject_GC_TRACK(si);
+ return (PyObject *)si;
+}
+
+static int
+set_update_internal(PySetObject *so, PyObject *other)
+{
+ PyObject *key, *it;
+
+ if (PyAnySet_Check(other))
+ return set_merge(so, other);
+
+ if (PyDict_CheckExact(other)) {
+ PyObject *value;
+ Py_ssize_t pos = 0;
+ 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 == -1)
+ return -1;
+ 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)) {
+ setentry an_entry;
+
+ an_entry.hash = hash;
+ an_entry.key = key;
+ if (set_add_entry(so, &an_entry) == -1)
+ return -1;
+ }
+ return 0;
+ }
+
+ it = PyObject_GetIter(other);
+ if (it == NULL)
+ return -1;
+
+ while ((key = PyIter_Next(it)) != NULL) {
+ if (set_add_key(so, key) == -1) {
+ Py_DECREF(it);
+ Py_DECREF(key);
+ return -1;
+ }
+ Py_DECREF(key);
+ }
+ Py_DECREF(it);
+ if (PyErr_Occurred())
+ return -1;
+ return 0;
+}
+
+static PyObject *
+set_update(PySetObject *so, PyObject *args)
+{
+ Py_ssize_t i;
+
+ for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
+ PyObject *other = PyTuple_GET_ITEM(args, i);
+ if (set_update_internal(so, other) == -1)
+ return NULL;
+ }
+ Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(update_doc,
+"Update a set with the union of itself and others.");
+
+static PyObject *
+make_new_set(PyTypeObject *type, PyObject *iterable)
+{
+ register PySetObject *so = NULL;
+
+ if (dummy == NULL) { /* Auto-initialize dummy */
+ dummy = PyString_FromString("<dummy key>");
+ if (dummy == NULL)
+ return NULL;
+ }
+
+ /* 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) == -1) {
+ Py_DECREF(so);
+ return NULL;
+ }
+ }
+
+ return (PyObject *)so;
+}
+
+/* The empty frozenset is a singleton */
+static PyObject *emptyfrozenset = NULL;
+
+static PyObject *
+frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
+{
+ PyObject *iterable = NULL, *result;
+
+ if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds))
+ return NULL;
+
+ if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
+ return NULL;
+
+ if (type != &PyFrozenSet_Type)
+ return make_new_set(type, iterable);
+
+ if (iterable != NULL) {
+ /* frozenset(f) is idempotent */
+ if (PyFrozenSet_CheckExact(iterable)) {
+ Py_INCREF(iterable);
+ return iterable;
+ }
+ result = make_new_set(type, iterable);
+ if (result == NULL || PySet_GET_SIZE(result))
+ return result;
+ Py_DECREF(result);
+ }
+ /* The empty frozenset is a singleton */
+ if (emptyfrozenset == NULL)
+ emptyfrozenset = make_new_set(type, NULL);
+ Py_XINCREF(emptyfrozenset);
+ 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);
+}
+
+/* set_swap_bodies() switches the contents of any two sets by moving their
+ internal data pointers and, if needed, copying the internal smalltables.
+ Semantically equivalent to:
+
+ 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 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
+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];
+ long h;
+
+ t = a->fill; a->fill = b->fill; b->fill = t;
+ t = a->used; a->used = b->used; b->used = t;
+ t = a->mask; a->mask = b->mask; b->mask = t;
+
+ u = a->table;
+ if (a->table == a->smalltable)
+ u = b->smalltable;
+ a->table = b->table;
+ if (b->table == b->smalltable)
+ 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));
+ memcpy(b->smalltable, tab, sizeof(tab));
+ }
+
+ if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type) &&
+ PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) {
+ h = a->hash; a->hash = b->hash; b->hash = h;
+ } else {
+ a->hash = -1;
+ b->hash = -1;
+ }
+}
+
+static PyObject *
+set_copy(PySetObject *so)
+{
+ return make_new_set(Py_TYPE(so), (PyObject *)so);
+}
+
+static PyObject *
+frozenset_copy(PySetObject *so)
+{
+ if (PyFrozenSet_CheckExact(so)) {
+ Py_INCREF(so);
+ return (PyObject *)so;
+ }
+ return set_copy(so);
+}
+
+PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
+
+static PyObject *
+set_clear(PySetObject *so)
+{
+ set_clear_internal(so);
+ Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
+
+static PyObject *
+set_union(PySetObject *so, PyObject *args)
+{
+ PySetObject *result;
+ PyObject *other;
+ Py_ssize_t i;
+
+ result = (PySetObject *)set_copy(so);
+ if (result == NULL)
+ return NULL;
+
+ for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
+ other = PyTuple_GET_ITEM(args, i);
+ if ((PyObject *)so == other)
+ continue;
+ if (set_update_internal(result, other) == -1) {
+ Py_DECREF(result);
+ return NULL;
+ }
+ }
+ return (PyObject *)result;
+}
+
+PyDoc_STRVAR(union_doc,
+ "Return the union of sets as a new set.\n\
+\n\
+(i.e. all elements that are in either set.)");
+
+static PyObject *
+set_or(PySetObject *so, PyObject *other)
+{
+ PySetObject *result;
+
+ if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
+ Py_INCREF(Py_NotImplemented);
+ return Py_NotImplemented;
+ }
+
+ result = (PySetObject *)set_copy(so);
+ if (result == NULL)
+ return NULL;
+ if ((PyObject *)so == other)
+ return (PyObject *)result;
+ if (set_update_internal(result, other) == -1) {
+ Py_DECREF(result);
+ return NULL;
+ }
+ return (PyObject *)result;
+}
+
+static PyObject *
+set_ior(PySetObject *so, PyObject *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;
+}
+
+static PyObject *
+set_intersection(PySetObject *so, PyObject *other)
+{
+ PySetObject *result;
+ PyObject *key, *it, *tmp;
+
+ if ((PyObject *)so == other)
+ return set_copy(so);
+
+ result = (PySetObject *)make_new_set(Py_TYPE(so), NULL);
+ if (result == NULL)
+ return NULL;
+
+ if (PyAnySet_Check(other)) {
+ Py_ssize_t pos = 0;
+ setentry *entry;
+
+ if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
+ tmp = (PyObject *)so;
+ so = (PySetObject *)other;
+ other = tmp;
+ }
+
+ while (set_next((PySetObject *)other, &pos, &entry)) {
+ int rv = set_contains_entry(so, entry);
+ if (rv == -1) {
+ Py_DECREF(result);
+ return NULL;
+ }
+ if (rv) {
+ if (set_add_entry(result, entry) == -1) {
+ Py_DECREF(result);
+ return NULL;
+ }
+ }
+ }
+ return (PyObject *)result;
+ }
+
+ it = PyObject_GetIter(other);
+ if (it == NULL) {
+ Py_DECREF(result);
+ return NULL;
+ }
+
+ while ((key = PyIter_Next(it)) != NULL) {
+ 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, &entry) == -1) {
+ Py_DECREF(it);
+ Py_DECREF(result);
+ Py_DECREF(key);
+ return NULL;
+ }
+ }
+ Py_DECREF(key);
+ }
+ Py_DECREF(it);
+ if (PyErr_Occurred()) {
+ Py_DECREF(result);
+ return NULL;
+ }
+ return (PyObject *)result;
+}
+
+static PyObject *
+set_intersection_multi(PySetObject *so, PyObject *args)
+{
+ Py_ssize_t i;
+ PyObject *result = (PyObject *)so;
+
+ if (PyTuple_GET_SIZE(args) == 0)
+ return set_copy(so);
+
+ Py_INCREF(so);
+ for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
+ PyObject *other = PyTuple_GET_ITEM(args, i);
+ PyObject *newresult = set_intersection((PySetObject *)result, other);
+ if (newresult == NULL) {
+ Py_DECREF(result);
+ return NULL;
+ }
+ Py_DECREF(result);
+ result = newresult;
+ }
+ return result;
+}
+
+PyDoc_STRVAR(intersection_doc,
+"Return the intersection of two or more sets as a new set.\n\
+\n\
+(i.e. elements that are common to all of the sets.)");
+
+static PyObject *
+set_intersection_update(PySetObject *so, PyObject *other)
+{
+ PyObject *tmp;
+
+ tmp = set_intersection(so, other);
+ if (tmp == NULL)
+ return NULL;
+ set_swap_bodies(so, (PySetObject *)tmp);
+ Py_DECREF(tmp);
+ Py_RETURN_NONE;
+}
+
+static PyObject *
+set_intersection_update_multi(PySetObject *so, PyObject *args)
+{
+ PyObject *tmp;
+
+ tmp = set_intersection_multi(so, args);
+ if (tmp == NULL)
+ return NULL;
+ set_swap_bodies(so, (PySetObject *)tmp);
+ Py_DECREF(tmp);
+ Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(intersection_update_doc,
+"Update a set with the intersection of itself and another.");
+
+static PyObject *
+set_and(PySetObject *so, PyObject *other)
+{
+ if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
+ Py_INCREF(Py_NotImplemented);
+ return Py_NotImplemented;
+ }
+ return set_intersection(so, other);
+}
+
+static PyObject *
+set_iand(PySetObject *so, PyObject *other)
+{
+ PyObject *result;
+
+ if (!PyAnySet_Check(other)) {
+ Py_INCREF(Py_NotImplemented);
+ return Py_NotImplemented;
+ }
+ result = set_intersection_update(so, other);
+ if (result == NULL)
+ return NULL;
+ Py_DECREF(result);
+ Py_INCREF(so);
+ return (PyObject *)so;
+}
+
+static PyObject *
+set_isdisjoint(PySetObject *so, PyObject *other)
+{
+ PyObject *key, *it, *tmp;
+
+ if ((PyObject *)so == other) {
+ if (PySet_GET_SIZE(so) == 0)
+ Py_RETURN_TRUE;
+ else
+ Py_RETURN_FALSE;
+ }
+
+ if (PyAnySet_CheckExact(other)) {
+ Py_ssize_t pos = 0;
+ setentry *entry;
+
+ if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
+ tmp = (PyObject *)so;
+ so = (PySetObject *)other;
+ other = tmp;
+ }
+ while (set_next((PySetObject *)other, &pos, &entry)) {
+ int rv = set_contains_entry(so, entry);
+ if (rv == -1)
+ return NULL;
+ if (rv)
+ Py_RETURN_FALSE;
+ }
+ Py_RETURN_TRUE;
+ }
+
+ it = PyObject_GetIter(other);
+ if (it == NULL)
+ return NULL;
+
+ while ((key = PyIter_Next(it)) != NULL) {
+ int rv;
+ setentry entry;
+ long hash = PyObject_Hash(key);
+
+ if (hash == -1) {
+ Py_DECREF(key);
+ Py_DECREF(it);
+ return NULL;
+ }
+ entry.hash = hash;
+ entry.key = key;
+ rv = set_contains_entry(so, &entry);
+ Py_DECREF(key);
+ if (rv == -1) {
+ Py_DECREF(it);
+ return NULL;
+ }
+ if (rv) {
+ Py_DECREF(it);
+ Py_RETURN_FALSE;
+ }
+ }
+ Py_DECREF(it);
+ if (PyErr_Occurred())
+ return NULL;
+ Py_RETURN_TRUE;
+}
+
+PyDoc_STRVAR(isdisjoint_doc,
+"Return True if two sets have a null intersection.");
+
+static int
+set_difference_update_internal(PySetObject *so, PyObject *other)
+{
+ if ((PyObject *)so == other)
+ return set_clear_internal(so);
+
+ if (PyAnySet_Check(other)) {
+ setentry *entry;
+ Py_ssize_t pos = 0;
+
+ while (set_next((PySetObject *)other, &pos, &entry))
+ if (set_discard_entry(so, entry) == -1)
+ return -1;
+ } else {
+ PyObject *key, *it;
+ it = PyObject_GetIter(other);
+ if (it == NULL)
+ return -1;
+
+ while ((key = PyIter_Next(it)) != NULL) {
+ if (set_discard_key(so, key) == -1) {
+ Py_DECREF(it);
+ Py_DECREF(key);
+ return -1;
+ }
+ Py_DECREF(key);
+ }
+ Py_DECREF(it);
+ if (PyErr_Occurred())
+ return -1;
+ }
+ /* 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);
+}
+
+static PyObject *
+set_difference_update(PySetObject *so, PyObject *args)
+{
+ Py_ssize_t i;
+
+ for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
+ PyObject *other = PyTuple_GET_ITEM(args, i);
+ if (set_difference_update_internal(so, other) == -1)
+ return NULL;
+ }
+ Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(difference_update_doc,
+"Remove all elements of another set from this set.");
+
+static PyObject *
+set_difference(PySetObject *so, PyObject *other)
+{
+ PyObject *result;
+ setentry *entry;
+ Py_ssize_t pos = 0;
+
+ 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(Py_TYPE(so), NULL);
+ if (result == NULL)
+ return NULL;
+
+ if (PyDict_CheckExact(other)) {
+ while (set_next(so, &pos, &entry)) {
+ setentry entrycopy;
+ entrycopy.hash = entry->hash;
+ entrycopy.key = entry->key;
+ if (!_PyDict_Contains(other, entry->key, entry->hash)) {
+ if (set_add_entry((PySetObject *)result, &entrycopy) == -1) {
+ Py_DECREF(result);
+ return NULL;
+ }
+ }
+ }
+ return result;
+ }
+
+ while (set_next(so, &pos, &entry)) {
+ int rv = set_contains_entry((PySetObject *)other, entry);
+ if (rv == -1) {
+ Py_DECREF(result);
+ return NULL;
+ }
+ if (!rv) {
+ if (set_add_entry((PySetObject *)result, entry) == -1) {
+ Py_DECREF(result);
+ return NULL;
+ }
+ }
+ }
+ return result;
+}
+
+static PyObject *
+set_difference_multi(PySetObject *so, PyObject *args)
+{
+ Py_ssize_t i;
+ PyObject *result, *other;
+
+ if (PyTuple_GET_SIZE(args) == 0)
+ return set_copy(so);
+
+ other = PyTuple_GET_ITEM(args, 0);
+ result = set_difference(so, other);
+ if (result == NULL)
+ return NULL;
+
+ for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) {
+ other = PyTuple_GET_ITEM(args, i);
+ if (set_difference_update_internal((PySetObject *)result, other) == -1) {
+ Py_DECREF(result);
+ return NULL;
+ }
+ }
+ return result;
+}
+
+PyDoc_STRVAR(difference_doc,
+"Return the difference of two or more sets as a new set.\n\
+\n\
+(i.e. all elements that are in this set but not the others.)");
+static PyObject *
+set_sub(PySetObject *so, PyObject *other)
+{
+ 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_INCREF(Py_NotImplemented);
+ return Py_NotImplemented;
+ }
+ if (set_difference_update_internal(so, other) == -1)
+ return NULL;
+ Py_INCREF(so);
+ return (PyObject *)so;
+}
+
+static PyObject *
+set_symmetric_difference_update(PySetObject *so, PyObject *other)
+{
+ PySetObject *otherset;
+ PyObject *key;
+ Py_ssize_t pos = 0;
+ setentry *entry;
+
+ if ((PyObject *)so == other)
+ 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);
+ 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, &an_entry) == -1) {
+ Py_DECREF(key);
+ return NULL;
+ }
+ }
+ Py_DECREF(key);
+ }
+ Py_RETURN_NONE;
+ }
+
+ if (PyAnySet_Check(other)) {
+ Py_INCREF(other);
+ otherset = (PySetObject *)other;
+ } else {
+ otherset = (PySetObject *)make_new_set(Py_TYPE(so), other);
+ if (otherset == NULL)
+ return NULL;
+ }
+
+ while (set_next(otherset, &pos, &entry)) {
+ int rv = set_discard_entry(so, entry);
+ if (rv == -1) {
+ Py_DECREF(otherset);
+ return NULL;
+ }
+ if (rv == DISCARD_NOTFOUND) {
+ if (set_add_entry(so, entry) == -1) {
+ Py_DECREF(otherset);
+ return NULL;
+ }
+ }
+ }
+ Py_DECREF(otherset);
+ Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(symmetric_difference_update_doc,
+"Update a set with the symmetric difference of itself and another.");
+
+static PyObject *
+set_symmetric_difference(PySetObject *so, PyObject *other)
+{
+ PyObject *rv;
+ PySetObject *otherset;
+
+ otherset = (PySetObject *)make_new_set(Py_TYPE(so), other);
+ if (otherset == NULL)
+ return NULL;
+ rv = set_symmetric_difference_update(otherset, (PyObject *)so);
+ if (rv == NULL)
+ return NULL;
+ Py_DECREF(rv);
+ return (PyObject *)otherset;
+}
+
+PyDoc_STRVAR(symmetric_difference_doc,
+"Return the symmetric difference of two sets as a new set.\n\
+\n\
+(i.e. all elements that are in exactly one of the sets.)");
+
+static PyObject *
+set_xor(PySetObject *so, PyObject *other)
+{
+ if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
+ Py_INCREF(Py_NotImplemented);
+ return Py_NotImplemented;
+ }
+ return set_symmetric_difference(so, other);
+}
+
+static PyObject *
+set_ixor(PySetObject *so, PyObject *other)
+{
+ PyObject *result;
+
+ if (!PyAnySet_Check(other)) {
+ Py_INCREF(Py_NotImplemented);
+ return Py_NotImplemented;
+ }
+ result = set_symmetric_difference_update(so, other);
+ if (result == NULL)
+ return NULL;
+ Py_DECREF(result);
+ Py_INCREF(so);
+ return (PyObject *)so;
+}
+
+static PyObject *
+set_issubset(PySetObject *so, PyObject *other)
+{
+ setentry *entry;
+ Py_ssize_t pos = 0;
+
+ if (!PyAnySet_Check(other)) {
+ PyObject *tmp, *result;
+ tmp = make_new_set(&PySet_Type, other);
+ if (tmp == NULL)
+ return NULL;
+ result = set_issubset(so, tmp);
+ Py_DECREF(tmp);
+ return result;
+ }
+ if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
+ Py_RETURN_FALSE;
+
+ while (set_next(so, &pos, &entry)) {
+ int rv = set_contains_entry((PySetObject *)other, entry);
+ if (rv == -1)
+ return NULL;
+ if (!rv)
+ Py_RETURN_FALSE;
+ }
+ Py_RETURN_TRUE;
+}
+
+PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
+
+static PyObject *
+set_issuperset(PySetObject *so, PyObject *other)
+{
+ PyObject *tmp, *result;
+
+ if (!PyAnySet_Check(other)) {
+ tmp = make_new_set(&PySet_Type, other);
+ if (tmp == NULL)
+ return NULL;
+ result = set_issuperset(so, tmp);
+ Py_DECREF(tmp);
+ return result;
+ }
+ return set_issubset((PySetObject *)other, (PyObject *)so);
+}
+
+PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
+
+static PyObject *
+set_richcompare(PySetObject *v, PyObject *w, int op)
+{
+ PyObject *r1, *r2;
+
+ if(!PyAnySet_Check(w)) {
+ if (op == Py_EQ)
+ Py_RETURN_FALSE;
+ if (op == Py_NE)
+ Py_RETURN_TRUE;
+ PyErr_SetString(PyExc_TypeError, "can only compare to a set");
+ return NULL;
+ }
+ switch (op) {
+ case Py_EQ:
+ if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
+ Py_RETURN_FALSE;
+ if (v->hash != -1 &&
+ ((PySetObject *)w)->hash != -1 &&
+ v->hash != ((PySetObject *)w)->hash)
+ Py_RETURN_FALSE;
+ return set_issubset(v, w);
+ case Py_NE:
+ r1 = set_richcompare(v, w, Py_EQ);
+ if (r1 == NULL)
+ return NULL;
+ r2 = PyBool_FromLong(PyObject_Not(r1));
+ Py_DECREF(r1);
+ return r2;
+ case Py_LE:
+ return set_issubset(v, w);
+ case Py_GE:
+ return set_issuperset(v, w);
+ case Py_LT:
+ if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))
+ Py_RETURN_FALSE;
+ return set_issubset(v, w);
+ case Py_GT:
+ if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
+ Py_RETURN_FALSE;
+ return set_issuperset(v, w);
+ }
+ 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) == -1)
+ return NULL;
+ Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(add_doc,
+"Add an element to a set.\n\
+\n\
+This has no effect if the element is already present.");
+
+static int
+set_contains(PySetObject *so, PyObject *key)
+{
+ PyObject *tmpkey;
+ int rv;
+
+ rv = set_contains_key(so, key);
+ if (rv == -1) {
+ if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
+ return -1;
+ PyErr_Clear();
+ tmpkey = make_new_set(&PyFrozenSet_Type, key);
+ if (tmpkey == NULL)
+ return -1;
+ rv = set_contains(so, tmpkey);
+ Py_DECREF(tmpkey);
+ }
+ return rv;
+}
+
+static PyObject *
+set_direct_contains(PySetObject *so, PyObject *key)
+{
+ long result;
+
+ result = set_contains(so, key);
+ if (result == -1)
+ return NULL;
+ return PyBool_FromLong(result);
+}
+
+PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
+
+static PyObject *
+set_remove(PySetObject *so, PyObject *key)
+{
+ PyObject *tmpkey;
+ int rv;
+
+ rv = set_discard_key(so, key);
+ if (rv == -1) {
+ if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
+ return NULL;
+ PyErr_Clear();
+ tmpkey = make_new_set(&PyFrozenSet_Type, key);
+ if (tmpkey == NULL)
+ return NULL;
+ rv = set_discard_key(so, tmpkey);
+ Py_DECREF(tmpkey);
+ if (rv == -1)
+ return NULL;
+ }
+
+ if (rv == DISCARD_NOTFOUND) {
+ set_key_error(key);
+ return NULL;
+ }
+ Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(remove_doc,
+"Remove an element from a set; it must be a member.\n\
+\n\
+If the element is not a member, raise a KeyError.");
+
+static PyObject *
+set_discard(PySetObject *so, PyObject *key)
+{
+ PyObject *tmpkey, *result;
+ int rv;
+
+ rv = set_discard_key(so, key);
+ if (rv == -1) {
+ if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
+ return NULL;
+ PyErr_Clear();
+ tmpkey = make_new_set(&PyFrozenSet_Type, key);
+ if (tmpkey == NULL)
+ return NULL;
+ result = set_discard(so, tmpkey);
+ Py_DECREF(tmpkey);
+ return result;
+ }
+ Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(discard_doc,
+"Remove an element from a set if it is a member.\n\
+\n\
+If the element is not a member, do nothing.");
+
+static PyObject *
+set_reduce(PySetObject *so)
+{
+ PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;
+
+ keys = PySequence_List((PyObject *)so);
+ if (keys == NULL)
+ goto done;
+ args = PyTuple_Pack(1, keys);
+ if (args == NULL)
+ goto done;
+ dict = PyObject_GetAttrString((PyObject *)so, "__dict__");
+ if (dict == NULL) {
+ PyErr_Clear();
+ dict = Py_None;
+ Py_INCREF(dict);
+ }
+ result = PyTuple_Pack(3, Py_TYPE(so), args, dict);
+done:
+ Py_XDECREF(args);
+ Py_XDECREF(keys);
+ Py_XDECREF(dict);
+ return result;
+}
+
+PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
+
+static PyObject *
+set_sizeof(PySetObject *so)
+{
+ Py_ssize_t res;
+
+ res = sizeof(PySetObject);
+ if (so->table != so->smalltable)
+ res = res + (so->mask + 1) * sizeof(setentry);
+ return PyInt_FromSsize_t(res);
+}
+
+PyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes");
+static int
+set_init(PySetObject *self, PyObject *args, PyObject *kwds)
+{
+ PyObject *iterable = NULL;
+
+ 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;
+ set_clear_internal(self);
+ self->hash = -1;
+ if (iterable == NULL)
+ return 0;
+ return set_update_internal(self, iterable);
+}
+
+static PySequenceMethods set_as_sequence = {
+ set_len, /* sq_length */
+ 0, /* sq_concat */
+ 0, /* sq_repeat */
+ 0, /* sq_item */
+ 0, /* sq_slice */
+ 0, /* sq_ass_item */
+ 0, /* sq_ass_slice */
+ (objobjproc)set_contains, /* sq_contains */
+};
+
+/* set object ********************************************************/
+
+#ifdef Py_DEBUG
+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.");
+#endif
+
+static PyMethodDef set_methods[] = {
+ {"add", (PyCFunction)set_add, METH_O,
+ add_doc},
+ {"clear", (PyCFunction)set_clear, METH_NOARGS,
+ clear_doc},
+ {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
+ contains_doc},
+ {"copy", (PyCFunction)set_copy, METH_NOARGS,
+ copy_doc},
+ {"discard", (PyCFunction)set_discard, METH_O,
+ discard_doc},
+ {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
+ difference_doc},
+ {"difference_update", (PyCFunction)set_difference_update, METH_VARARGS,
+ difference_update_doc},
+ {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
+ intersection_doc},
+ {"intersection_update",(PyCFunction)set_intersection_update_multi, METH_VARARGS,
+ intersection_update_doc},
+ {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
+ isdisjoint_doc},
+ {"issubset", (PyCFunction)set_issubset, METH_O,
+ issubset_doc},
+ {"issuperset", (PyCFunction)set_issuperset, METH_O,
+ issuperset_doc},
+ {"pop", (PyCFunction)set_pop, METH_NOARGS,
+ pop_doc},
+ {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
+ reduce_doc},
+ {"remove", (PyCFunction)set_remove, METH_O,
+ remove_doc},
+ {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
+ sizeof_doc},
+ {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
+ symmetric_difference_doc},
+ {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O,
+ symmetric_difference_update_doc},
+#ifdef Py_DEBUG
+ {"test_c_api", (PyCFunction)test_c_api, METH_NOARGS,
+ test_c_api_doc},
+#endif
+ {"union", (PyCFunction)set_union, METH_VARARGS,
+ union_doc},
+ {"update", (PyCFunction)set_update, METH_VARARGS,
+ update_doc},
+ {NULL, NULL} /* sentinel */
+};
+
+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_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_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*/
+ 0, /*nb_inplace_rshift*/
+ (binaryfunc)set_iand, /*nb_inplace_and*/
+ (binaryfunc)set_ixor, /*nb_inplace_xor*/
+ (binaryfunc)set_ior, /*nb_inplace_or*/
+};
+
+PyDoc_STRVAR(set_doc,
+"set() -> new empty set object\n\
+set(iterable) -> new set object\n\
+\n\
+Build an unordered collection of unique elements.");
+
+PyTypeObject PySet_Type = {
+ PyVarObject_HEAD_INIT(&PyType_Type, 0)
+ "set", /* tp_name */
+ sizeof(PySetObject), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ /* methods */
+ (destructor)set_dealloc, /* tp_dealloc */
+ (printfunc)set_tp_print, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 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 */
+ (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_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 */
+ 0, /* tp_iternext */
+ set_methods, /* tp_methods */
+ 0, /* tp_members */
+ 0, /* tp_getset */
+ 0, /* tp_base */
+ 0, /* tp_dict */
+ 0, /* tp_descr_get */
+ 0, /* tp_descr_set */
+ 0, /* tp_dictoffset */
+ (initproc)set_init, /* tp_init */
+ PyType_GenericAlloc, /* tp_alloc */
+ set_new, /* tp_new */
+ PyObject_GC_Del, /* tp_free */
+};
+
+/* frozenset object ********************************************************/
+
+
+static PyMethodDef frozenset_methods[] = {
+ {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
+ contains_doc},
+ {"copy", (PyCFunction)frozenset_copy, METH_NOARGS,
+ copy_doc},
+ {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
+ difference_doc},
+ {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
+ intersection_doc},
+ {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
+ isdisjoint_doc},
+ {"issubset", (PyCFunction)set_issubset, METH_O,
+ issubset_doc},
+ {"issuperset", (PyCFunction)set_issuperset, METH_O,
+ issuperset_doc},
+ {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
+ reduce_doc},
+ {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
+ sizeof_doc},
+ {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
+ symmetric_difference_doc},
+ {"union", (PyCFunction)set_union, METH_VARARGS,
+ union_doc},
+ {NULL, NULL} /* sentinel */
+};
+
+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_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*/
+};
+
+PyDoc_STRVAR(frozenset_doc,
+"frozenset() -> empty frozenset object\n\
+frozenset(iterable) -> frozenset object\n\
+\n\
+Build an immutable unordered collection of unique elements.");
+
+PyTypeObject PyFrozenSet_Type = {
+ PyVarObject_HEAD_INIT(&PyType_Type, 0)
+ "frozenset", /* tp_name */
+ sizeof(PySetObject), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ /* methods */
+ (destructor)set_dealloc, /* tp_dealloc */
+ (printfunc)set_tp_print, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ set_nocmp, /* tp_compare */
+ (reprfunc)set_repr, /* tp_repr */
+ &frozenset_as_number, /* tp_as_number */
+ &set_as_sequence, /* tp_as_sequence */
+ 0, /* tp_as_mapping */
+ frozenset_hash, /* 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_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 */
+ (getiterfunc)set_iter, /* tp_iter */
+ 0, /* tp_iternext */
+ frozenset_methods, /* tp_methods */
+ 0, /* tp_members */
+ 0, /* tp_getset */
+ 0, /* tp_base */
+ 0, /* tp_dict */
+ 0, /* tp_descr_get */
+ 0, /* tp_descr_set */
+ 0, /* tp_dictoffset */
+ 0, /* tp_init */
+ PyType_GenericAlloc, /* tp_alloc */
+ frozenset_new, /* tp_new */
+ PyObject_GC_Del, /* tp_free */
+};
+
+
+/***** C API functions *************************************************/
+
+PyObject *
+PySet_New(PyObject *iterable)
+{
+ return make_new_set(&PySet_Type, iterable);
+}
+
+PyObject *
+PyFrozenSet_New(PyObject *iterable)
+{
+ return make_new_set(&PyFrozenSet_Type, iterable);
+}
+
+Py_ssize_t
+PySet_Size(PyObject *anyset)
+{
+ if (!PyAnySet_Check(anyset)) {
+ PyErr_BadInternalCall();
+ return -1;
+ }
+ return PySet_GET_SIZE(anyset);
+}
+
+int
+PySet_Clear(PyObject *set)
+{
+ if (!PySet_Check(set)) {
+ PyErr_BadInternalCall();
+ return -1;
+ }
+ return set_clear_internal((PySetObject *)set);
+}
+
+int
+PySet_Contains(PyObject *anyset, PyObject *key)
+{
+ if (!PyAnySet_Check(anyset)) {
+ PyErr_BadInternalCall();
+ return -1;
+ }
+ return set_contains_key((PySetObject *)anyset, key);
+}
+
+int
+PySet_Discard(PyObject *set, PyObject *key)
+{
+ if (!PySet_Check(set)) {
+ PyErr_BadInternalCall();
+ return -1;
+ }
+ return set_discard_key((PySetObject *)set, key);
+}
+
+int
+PySet_Add(PyObject *anyset, PyObject *key)
+{
+ if (!PySet_Check(anyset) &&
+ (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
+ PyErr_BadInternalCall();
+ return -1;
+ }
+ return set_add_key((PySetObject *)anyset, key);
+}
+
+int
+_PySet_Next(PyObject *set, Py_ssize_t *pos, PyObject **key)
+{
+ setentry *entry_ptr;
+
+ 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, long *hash)
+{
+ setentry *entry;
+
+ if (!PyAnySet_Check(set)) {
+ PyErr_BadInternalCall();
+ return -1;
+ }
+ if (set_next((PySetObject *)set, pos, &entry) == 0)
+ return 0;
+ *key = entry->key;
+ *hash = entry->hash;
+ return 1;
+}
+
+PyObject *
+PySet_Pop(PyObject *set)
+{
+ if (!PySet_Check(set)) {
+ PyErr_BadInternalCall();
+ return NULL;
+ }
+ return set_pop((PySetObject *)set);
+}
+
+int
+_PySet_Update(PyObject *set, PyObject *iterable)
+{
+ if (!PySet_Check(set)) {
+ PyErr_BadInternalCall();
+ return -1;
+ }
+ return set_update_internal((PySetObject *)set, iterable);
+}
+
+#ifdef Py_DEBUG
+
+/* Test code to be called with any three element set.
+ Returns True and original set is restored. */
+
+#define assertRaises(call_return_value, exception) \
+ do { \
+ assert(call_return_value); \
+ assert(PyErr_ExceptionMatches(exception)); \
+ PyErr_Clear(); \
+ } while(0)
+
+static PyObject *
+test_c_api(PySetObject *so)
+{
+ Py_ssize_t count;
+ char *s;
+ Py_ssize_t i;
+ PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x;
+ PyObject *ob = (PyObject *)so;
+ PyObject *str;
+
+ /* Verify preconditions */
+ assert(PyAnySet_Check(ob));
+ assert(PyAnySet_CheckExact(ob));
+ assert(!PyFrozenSet_CheckExact(ob));
+
+ /* so.clear(); so |= set("abc"); */
+ str = PyString_FromString("abc");
+ if (str == NULL)
+ return NULL;
+ set_clear_internal(so);
+ if (set_update_internal(so, str) == -1) {
+ Py_DECREF(str);
+ return NULL;
+ }
+ Py_DECREF(str);
+
+ /* Exercise type/size checks */
+ assert(PySet_Size(ob) == 3);
+ assert(PySet_GET_SIZE(ob) == 3);
+
+ /* Raise TypeError for non-iterable constructor arguments */
+ assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
+ assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);
+
+ /* Raise TypeError for unhashable key */
+ dup = PySet_New(ob);
+ assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
+ assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
+ assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);
+
+ /* Exercise successful pop, contains, add, and discard */
+ elem = PySet_Pop(ob);
+ assert(PySet_Contains(ob, elem) == 0);
+ assert(PySet_GET_SIZE(ob) == 2);
+ assert(PySet_Add(ob, elem) == 0);
+ assert(PySet_Contains(ob, elem) == 1);
+ assert(PySet_GET_SIZE(ob) == 3);
+ assert(PySet_Discard(ob, elem) == 1);
+ assert(PySet_GET_SIZE(ob) == 2);
+ assert(PySet_Discard(ob, elem) == 0);
+ assert(PySet_GET_SIZE(ob) == 2);
+
+ /* Exercise clear */
+ dup2 = PySet_New(dup);
+ assert(PySet_Clear(dup2) == 0);
+ assert(PySet_Size(dup2) == 0);
+ Py_DECREF(dup2);
+
+ /* Raise SystemError on clear or update of frozen set */
+ f = PyFrozenSet_New(dup);
+ assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
+ assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
+ assert(PySet_Add(f, elem) == 0);
+ Py_INCREF(f);
+ assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
+ Py_DECREF(f);
+ Py_DECREF(f);
+
+ /* Exercise direct iteration */
+ i = 0, count = 0;
+ while (_PySet_Next((PyObject *)dup, &i, &x)) {
+ s = PyString_AsString(x);
+ assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
+ count++;
+ }
+ assert(count == 3);
+
+ /* Exercise updates */
+ dup2 = PySet_New(NULL);
+ assert(_PySet_Update(dup2, dup) == 0);
+ assert(PySet_Size(dup2) == 3);
+ assert(_PySet_Update(dup2, dup) == 0);
+ assert(PySet_Size(dup2) == 3);
+ Py_DECREF(dup2);
+
+ /* Raise SystemError when self argument is not a set or frozenset. */
+ t = PyTuple_New(0);
+ assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
+ assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
+ Py_DECREF(t);
+
+ /* Raise SystemError when self argument is not a set. */
+ f = PyFrozenSet_New(dup);
+ assert(PySet_Size(f) == 3);
+ assert(PyFrozenSet_CheckExact(f));
+ assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
+ assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
+ Py_DECREF(f);
+
+ /* Raise KeyError when popping from an empty set */
+ assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
+ Py_DECREF(ob);
+ assert(PySet_GET_SIZE(ob) == 0);
+ assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);
+
+ /* Restore the set from the copy using the PyNumber API */
+ assert(PyNumber_InPlaceOr(ob, dup) == ob);
+ Py_DECREF(ob);
+
+ /* Verify constructors accept NULL arguments */
+ f = PySet_New(NULL);
+ assert(f != NULL);
+ assert(PySet_GET_SIZE(f) == 0);
+ Py_DECREF(f);
+ f = PyFrozenSet_New(NULL);
+ assert(f != NULL);
+ assert(PyFrozenSet_CheckExact(f));
+ assert(PySet_GET_SIZE(f) == 0);
+ Py_DECREF(f);
+
+ Py_DECREF(elem);
+ Py_DECREF(dup);
+ Py_RETURN_TRUE;
+}
+
+#undef assertRaises
+
+#endif
|