LCOV - code coverage report
Current view: top level - Objects - setobject.c (source / functions) Hit Total Coverage
Test: CPython lcov report Lines: 328 1055 31.1 %
Date: 2017-04-19 Functions: 34 80 42.5 %

          Line data    Source code
       1             : 
       2             : /* set object implementation
       3             :    Written and maintained by Raymond D. Hettinger <python@rcn.com>
       4             :    Derived from Lib/sets.py and Objects/dictobject.c.
       5             : */
       6             : 
       7             : #include "Python.h"
       8             : #include "structmember.h"
       9             : 
      10             : /* Set a key error with the specified argument, wrapping it in a
      11             :  * tuple automatically so that tuple keys are not unpacked as the
      12             :  * exception arguments. */
      13             : static void
      14           0 : set_key_error(PyObject *arg)
      15             : {
      16             :     PyObject *tup;
      17           0 :     tup = PyTuple_Pack(1, arg);
      18           0 :     if (!tup)
      19           0 :         return; /* caller will expect error to be set anyway */
      20           0 :     PyErr_SetObject(PyExc_KeyError, tup);
      21           0 :     Py_DECREF(tup);
      22             : }
      23             : 
      24             : /* This must be >= 1. */
      25             : #define PERTURB_SHIFT 5
      26             : 
      27             : /* Object used as dummy key to fill deleted entries */
      28             : static PyObject *dummy = NULL; /* Initialized by first call to make_new_set() */
      29             : 
      30             : #ifdef Py_REF_DEBUG
      31             : PyObject *
      32             : _PySet_Dummy(void)
      33             : {
      34             :     return dummy;
      35             : }
      36             : #endif
      37             : 
      38             : #define INIT_NONZERO_SET_SLOTS(so) do {                         \
      39             :     (so)->table = (so)->smalltable;                             \
      40             :     (so)->mask = PySet_MINSIZE - 1;                             \
      41             :     (so)->hash = -1;                                            \
      42             :     } while(0)
      43             : 
      44             : #define EMPTY_TO_MINSIZE(so) do {                               \
      45             :     memset((so)->smalltable, 0, sizeof((so)->smalltable));      \
      46             :     (so)->used = (so)->fill = 0;                                \
      47             :     INIT_NONZERO_SET_SLOTS(so);                                 \
      48             :     } while(0)
      49             : 
      50             : /* Reuse scheme to save calls to malloc, free, and memset */
      51             : #ifndef PySet_MAXFREELIST
      52             : #define PySet_MAXFREELIST 80
      53             : #endif
      54             : static PySetObject *free_list[PySet_MAXFREELIST];
      55             : static int numfree = 0;
      56             : 
      57             : /*
      58             : The basic lookup function used by all operations.
      59             : This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
      60             : Open addressing is preferred over chaining since the link overhead for
      61             : chaining would be substantial (100% with typical malloc overhead).
      62             : 
      63             : The initial probe index is computed as hash mod the table size. Subsequent
      64             : probe indices are computed as explained in Objects/dictobject.c.
      65             : 
      66             : All arithmetic on hash should ignore overflow.
      67             : 
      68             : Unlike the dictionary implementation, the lookkey functions can return
      69             : NULL if the rich comparison returns an error.
      70             : */
      71             : 
      72             : static setentry *
      73        6471 : set_lookkey(PySetObject *so, PyObject *key, register long hash)
      74             : {
      75             :     register Py_ssize_t i;
      76             :     register size_t perturb;
      77             :     register setentry *freeslot;
      78        6471 :     register size_t mask = so->mask;
      79        6471 :     setentry *table = so->table;
      80             :     register setentry *entry;
      81             :     register int cmp;
      82             :     PyObject *startkey;
      83             : 
      84        6471 :     i = hash & mask;
      85        6471 :     entry = &table[i];
      86        6471 :     if (entry->key == NULL || entry->key == key)
      87        5983 :         return entry;
      88             : 
      89         488 :     if (entry->key == dummy)
      90          23 :         freeslot = entry;
      91             :     else {
      92         465 :         if (entry->hash == hash) {
      93           0 :             startkey = entry->key;
      94           0 :             Py_INCREF(startkey);
      95           0 :             cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
      96           0 :             Py_DECREF(startkey);
      97           0 :             if (cmp < 0)
      98           0 :                 return NULL;
      99           0 :             if (table == so->table && entry->key == startkey) {
     100           0 :                 if (cmp > 0)
     101           0 :                     return entry;
     102             :             }
     103             :             else {
     104             :                 /* The compare did major nasty stuff to the
     105             :                  * set:  start over.
     106             :                  */
     107           0 :                 return set_lookkey(so, key, hash);
     108             :             }
     109             :         }
     110         465 :         freeslot = NULL;
     111             :     }
     112             : 
     113             :     /* In the loop, key == dummy is by far (factor of 100s) the
     114             :        least likely outcome, so test for that last. */
     115         488 :     for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
     116         488 :         i = (i << 2) + i + perturb + 1;
     117         488 :         entry = &table[i & mask];
     118         488 :         if (entry->key == NULL) {
     119         488 :             if (freeslot != NULL)
     120          23 :                 entry = freeslot;
     121         488 :             break;
     122             :         }
     123           0 :         if (entry->key == key)
     124           0 :             break;
     125           0 :         if (entry->hash == hash && entry->key != dummy) {
     126           0 :             startkey = entry->key;
     127           0 :             Py_INCREF(startkey);
     128           0 :             cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
     129           0 :             Py_DECREF(startkey);
     130           0 :             if (cmp < 0)
     131           0 :                 return NULL;
     132           0 :             if (table == so->table && entry->key == startkey) {
     133           0 :                 if (cmp > 0)
     134           0 :                     break;
     135             :             }
     136             :             else {
     137             :                 /* The compare did major nasty stuff to the
     138             :                  * set:  start over.
     139             :                  */
     140           0 :                 return set_lookkey(so, key, hash);
     141             :             }
     142             :         }
     143           0 :         else if (entry->key == dummy && freeslot == NULL)
     144           0 :             freeslot = entry;
     145           0 :     }
     146         488 :     return entry;
     147             : }
     148             : 
     149             : /*
     150             :  * Hacked up version of set_lookkey which can assume keys are always strings;
     151             :  * This means we can always use _PyString_Eq directly and not have to check to
     152             :  * see if the comparison altered the table.
     153             :  */
     154             : static setentry *
     155       11385 : set_lookkey_string(PySetObject *so, PyObject *key, register long hash)
     156             : {
     157             :     register Py_ssize_t i;
     158             :     register size_t perturb;
     159             :     register setentry *freeslot;
     160       11385 :     register size_t mask = so->mask;
     161       11385 :     setentry *table = so->table;
     162             :     register setentry *entry;
     163             : 
     164             :     /* Make sure this function doesn't have to handle non-string keys,
     165             :        including subclasses of str; e.g., one reason to subclass
     166             :        strings is to override __eq__, and for speed we don't cater to
     167             :        that here. */
     168       11385 :     if (!PyString_CheckExact(key)) {
     169         177 :         so->lookup = set_lookkey;
     170         177 :         return set_lookkey(so, key, hash);
     171             :     }
     172       11208 :     i = hash & mask;
     173       11208 :     entry = &table[i];
     174       11208 :     if (entry->key == NULL || entry->key == key)
     175       10419 :         return entry;
     176         789 :     if (entry->key == dummy)
     177           0 :         freeslot = entry;
     178             :     else {
     179         789 :         if (entry->hash == hash && _PyString_Eq(entry->key, key))
     180          33 :             return entry;
     181         756 :         freeslot = NULL;
     182             :     }
     183             : 
     184             :     /* In the loop, key == dummy is by far (factor of 100s) the
     185             :        least likely outcome, so test for that last. */
     186         903 :     for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
     187         903 :         i = (i << 2) + i + perturb + 1;
     188         903 :         entry = &table[i & mask];
     189         903 :         if (entry->key == NULL)
     190         756 :             return freeslot == NULL ? entry : freeslot;
     191         147 :         if (entry->key == key
     192         147 :             || (entry->hash == hash
     193           0 :             && entry->key != dummy
     194           0 :             && _PyString_Eq(entry->key, key)))
     195           0 :             return entry;
     196         147 :         if (entry->key == dummy && freeslot == NULL)
     197           0 :             freeslot = entry;
     198         147 :     }
     199             :     assert(0);          /* NOT REACHED */
     200             :     return 0;
     201             : }
     202             : 
     203             : /*
     204             : Internal routine to insert a new key into the table.
     205             : Used by the public insert routine.
     206             : Eats a reference to key.
     207             : */
     208             : static int
     209        1263 : set_insert_key(register PySetObject *so, PyObject *key, long hash)
     210             : {
     211             :     register setentry *entry;
     212             : 
     213             :     assert(so->lookup != NULL);
     214        1263 :     entry = so->lookup(so, key, hash);
     215        1263 :     if (entry == NULL)
     216           0 :         return -1;
     217        1263 :     if (entry->key == NULL) {
     218             :         /* UNUSED */
     219        1192 :         so->fill++;
     220        1192 :         entry->key = key;
     221        1192 :         entry->hash = hash;
     222        1192 :         so->used++;
     223          71 :     } else if (entry->key == dummy) {
     224             :         /* DUMMY */
     225          23 :         entry->key = key;
     226          23 :         entry->hash = hash;
     227          23 :         so->used++;
     228          23 :         Py_DECREF(dummy);
     229             :     } else {
     230             :         /* ACTIVE */
     231          48 :         Py_DECREF(key);
     232             :     }
     233        1263 :     return 0;
     234             : }
     235             : 
     236             : /*
     237             : Internal routine used by set_table_resize() to insert an item which is
     238             : known to be absent from the set.  This routine also assumes that
     239             : the set contains no deleted entries.  Besides the performance benefit,
     240             : using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
     241             : Note that no refcounts are changed by this routine; if needed, the caller
     242             : is responsible for incref'ing `key`.
     243             : */
     244             : static void
     245         546 : set_insert_clean(register PySetObject *so, PyObject *key, long hash)
     246             : {
     247             :     register size_t i;
     248             :     register size_t perturb;
     249         546 :     register size_t mask = (size_t)so->mask;
     250         546 :     setentry *table = so->table;
     251             :     register setentry *entry;
     252             : 
     253         546 :     i = hash & mask;
     254         546 :     entry = &table[i];
     255         573 :     for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) {
     256          27 :         i = (i << 2) + i + perturb + 1;
     257          27 :         entry = &table[i & mask];
     258             :     }
     259         546 :     so->fill++;
     260         546 :     entry->key = key;
     261         546 :     entry->hash = hash;
     262         546 :     so->used++;
     263         546 : }
     264             : 
     265             : /*
     266             : Restructure the table by allocating a new table and reinserting all
     267             : keys again.  When entries have been deleted, the new table may
     268             : actually be smaller than the old one.
     269             : */
     270             : static int
     271          54 : set_table_resize(PySetObject *so, Py_ssize_t minused)
     272             : {
     273             :     Py_ssize_t newsize;
     274             :     setentry *oldtable, *newtable, *entry;
     275             :     Py_ssize_t i;
     276             :     int is_oldtable_malloced;
     277             :     setentry small_copy[PySet_MINSIZE];
     278             : 
     279             :     assert(minused >= 0);
     280             : 
     281             :     /* Find the smallest table size > minused. */
     282         246 :     for (newsize = PySet_MINSIZE;
     283         138 :          newsize <= minused && newsize > 0;
     284         138 :          newsize <<= 1)
     285             :         ;
     286          54 :     if (newsize <= 0) {
     287           0 :         PyErr_NoMemory();
     288           0 :         return -1;
     289             :     }
     290             : 
     291             :     /* Get space for a new table. */
     292          54 :     oldtable = so->table;
     293             :     assert(oldtable != NULL);
     294          54 :     is_oldtable_malloced = oldtable != so->smalltable;
     295             : 
     296          54 :     if (newsize == PySet_MINSIZE) {
     297             :         /* A large table is shrinking, or we can't get any smaller. */
     298           0 :         newtable = so->smalltable;
     299           0 :         if (newtable == oldtable) {
     300           0 :             if (so->fill == so->used) {
     301             :                 /* No dummies, so no point doing anything. */
     302           0 :                 return 0;
     303             :             }
     304             :             /* We're not going to resize it, but rebuild the
     305             :                table anyway to purge old dummy entries.
     306             :                Subtle:  This is *necessary* if fill==size,
     307             :                as set_lookkey needs at least one virgin slot to
     308             :                terminate failing searches.  If fill < size, it's
     309             :                merely desirable, as dummies slow searches. */
     310             :             assert(so->fill > so->used);
     311           0 :             memcpy(small_copy, oldtable, sizeof(small_copy));
     312           0 :             oldtable = small_copy;
     313             :         }
     314             :     }
     315             :     else {
     316          54 :         newtable = PyMem_NEW(setentry, newsize);
     317          54 :         if (newtable == NULL) {
     318           0 :             PyErr_NoMemory();
     319           0 :             return -1;
     320             :         }
     321             :     }
     322             : 
     323             :     /* Make the set empty, using the new table. */
     324             :     assert(newtable != oldtable);
     325          54 :     so->table = newtable;
     326          54 :     so->mask = newsize - 1;
     327          54 :     memset(newtable, 0, sizeof(setentry) * newsize);
     328          54 :     so->used = 0;
     329          54 :     i = so->fill;
     330          54 :     so->fill = 0;
     331             : 
     332             :     /* Copy the data over; this is refcount-neutral for active entries;
     333             :        dummy entries aren't copied over, of course */
     334         798 :     for (entry = oldtable; i > 0; entry++) {
     335         744 :         if (entry->key == NULL) {
     336             :             /* UNUSED */
     337             :             ;
     338         546 :         } else if (entry->key == dummy) {
     339             :             /* DUMMY */
     340           0 :             --i;
     341             :             assert(entry->key == dummy);
     342           0 :             Py_DECREF(entry->key);
     343             :         } else {
     344             :             /* ACTIVE */
     345         546 :             --i;
     346         546 :             set_insert_clean(so, entry->key, entry->hash);
     347             :         }
     348             :     }
     349             : 
     350          54 :     if (is_oldtable_malloced)
     351          18 :         PyMem_DEL(oldtable);
     352          54 :     return 0;
     353             : }
     354             : 
     355             : /* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
     356             : 
     357             : static int
     358           0 : set_add_entry(register PySetObject *so, setentry *entry)
     359             : {
     360             :     register Py_ssize_t n_used;
     361           0 :     PyObject *key = entry->key;
     362           0 :     long hash = entry->hash;
     363             : 
     364             :     assert(so->fill <= so->mask);  /* at least one empty slot */
     365           0 :     n_used = so->used;
     366           0 :     Py_INCREF(key);
     367           0 :     if (set_insert_key(so, key, hash) == -1) {
     368           0 :         Py_DECREF(key);
     369           0 :         return -1;
     370             :     }
     371           0 :     if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
     372           0 :         return 0;
     373           0 :     return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
     374             : }
     375             : 
     376             : static int
     377        1086 : set_add_key(register PySetObject *so, PyObject *key)
     378             : {
     379             :     register long hash;
     380             :     register Py_ssize_t n_used;
     381             : 
     382        1983 :     if (!PyString_CheckExact(key) ||
     383         897 :         (hash = ((PyStringObject *) key)->ob_shash) == -1) {
     384         263 :         hash = PyObject_Hash(key);
     385         263 :         if (hash == -1)
     386           0 :             return -1;
     387             :     }
     388             :     assert(so->fill <= so->mask);  /* at least one empty slot */
     389        1086 :     n_used = so->used;
     390        1086 :     Py_INCREF(key);
     391        1086 :     if (set_insert_key(so, key, hash) == -1) {
     392           0 :         Py_DECREF(key);
     393           0 :         return -1;
     394             :     }
     395        1086 :     if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
     396        1038 :         return 0;
     397          48 :     return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
     398             : }
     399             : 
     400             : #define DISCARD_NOTFOUND 0
     401             : #define DISCARD_FOUND 1
     402             : 
     403             : static int
     404           0 : set_discard_entry(PySetObject *so, setentry *oldentry)
     405             : {       register setentry *entry;
     406             :     PyObject *old_key;
     407             : 
     408           0 :     entry = (so->lookup)(so, oldentry->key, oldentry->hash);
     409           0 :     if (entry == NULL)
     410           0 :         return -1;
     411           0 :     if (entry->key == NULL  ||  entry->key == dummy)
     412           0 :         return DISCARD_NOTFOUND;
     413           0 :     old_key = entry->key;
     414           0 :     Py_INCREF(dummy);
     415           0 :     entry->key = dummy;
     416           0 :     so->used--;
     417           0 :     Py_DECREF(old_key);
     418           0 :     return DISCARD_FOUND;
     419             : }
     420             : 
     421             : static int
     422          69 : set_discard_key(PySetObject *so, PyObject *key)
     423             : {
     424             :     register long hash;
     425             :     register setentry *entry;
     426             :     PyObject *old_key;
     427             : 
     428             :     assert (PyAnySet_Check(so));
     429          69 :     if (!PyString_CheckExact(key) ||
     430           0 :         (hash = ((PyStringObject *) key)->ob_shash) == -1) {
     431          69 :         hash = PyObject_Hash(key);
     432          69 :         if (hash == -1)
     433           0 :             return -1;
     434             :     }
     435          69 :     entry = (so->lookup)(so, key, hash);
     436          69 :     if (entry == NULL)
     437           0 :         return -1;
     438          69 :     if (entry->key == NULL  ||  entry->key == dummy)
     439           0 :         return DISCARD_NOTFOUND;
     440          69 :     old_key = entry->key;
     441          69 :     Py_INCREF(dummy);
     442          69 :     entry->key = dummy;
     443          69 :     so->used--;
     444          69 :     Py_DECREF(old_key);
     445          69 :     return DISCARD_FOUND;
     446             : }
     447             : 
     448             : static int
     449         636 : set_clear_internal(PySetObject *so)
     450             : {
     451             :     setentry *entry, *table;
     452             :     int table_is_malloced;
     453             :     Py_ssize_t fill;
     454             :     setentry small_copy[PySet_MINSIZE];
     455             : #ifdef Py_DEBUG
     456             :     Py_ssize_t i, n;
     457             :     assert (PyAnySet_Check(so));
     458             : 
     459             :     n = so->mask + 1;
     460             :     i = 0;
     461             : #endif
     462             : 
     463         636 :     table = so->table;
     464             :     assert(table != NULL);
     465         636 :     table_is_malloced = table != so->smalltable;
     466             : 
     467             :     /* This is delicate.  During the process of clearing the set,
     468             :      * decrefs can cause the set to mutate.  To avoid fatal confusion
     469             :      * (voice of experience), we have to make the set empty before
     470             :      * clearing the slots, and never refer to anything via so->ref while
     471             :      * clearing.
     472             :      */
     473         636 :     fill = so->fill;
     474         636 :     if (table_is_malloced)
     475           0 :         EMPTY_TO_MINSIZE(so);
     476             : 
     477         636 :     else if (fill > 0) {
     478             :         /* It's a small table with something that needs to be cleared.
     479             :          * Afraid the only safe way is to copy the set entries into
     480             :          * another small table first.
     481             :          */
     482           0 :         memcpy(small_copy, table, sizeof(small_copy));
     483           0 :         table = small_copy;
     484           0 :         EMPTY_TO_MINSIZE(so);
     485             :     }
     486             :     /* else it's a small table that's already empty */
     487             : 
     488             :     /* Now we can finally clear things.  If C had refcounts, we could
     489             :      * assert that the refcount on table is 1 now, i.e. that this function
     490             :      * has unique access to it, so decref side-effects can't alter it.
     491             :      */
     492         636 :     for (entry = table; fill > 0; ++entry) {
     493             : #ifdef Py_DEBUG
     494             :         assert(i < n);
     495             :         ++i;
     496             : #endif
     497           0 :         if (entry->key) {
     498           0 :             --fill;
     499           0 :             Py_DECREF(entry->key);
     500             :         }
     501             : #ifdef Py_DEBUG
     502             :         else
     503             :             assert(entry->key == NULL);
     504             : #endif
     505             :     }
     506             : 
     507         636 :     if (table_is_malloced)
     508           0 :         PyMem_DEL(table);
     509         636 :     return 0;
     510             : }
     511             : 
     512             : /*
     513             :  * Iterate over a set table.  Use like so:
     514             :  *
     515             :  *     Py_ssize_t pos;
     516             :  *     setentry *entry;
     517             :  *     pos = 0;   # important!  pos should not otherwise be changed by you
     518             :  *     while (set_next(yourset, &pos, &entry)) {
     519             :  *              Refer to borrowed reference in entry->key.
     520             :  *     }
     521             :  *
     522             :  * CAUTION:  In general, it isn't safe to use set_next in a loop that
     523             :  * mutates the table.
     524             :  */
     525             : static int
     526        7508 : set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)
     527             : {
     528             :     Py_ssize_t i;
     529             :     Py_ssize_t mask;
     530             :     register setentry *table;
     531             : 
     532             :     assert (PyAnySet_Check(so));
     533        7508 :     i = *pos_ptr;
     534             :     assert(i >= 0);
     535        7508 :     table = so->table;
     536        7508 :     mask = so->mask;
     537       42692 :     while (i <= mask && (table[i].key == NULL || table[i].key == dummy))
     538       27676 :         i++;
     539        7508 :     *pos_ptr = i+1;
     540        7508 :     if (i > mask)
     541        2720 :         return 0;
     542             :     assert(table[i].key != NULL);
     543        4788 :     *entry_ptr = &table[i];
     544        4788 :     return 1;
     545             : }
     546             : 
     547             : static void
     548         315 : set_dealloc(PySetObject *so)
     549             : {
     550             :     register setentry *entry;
     551         315 :     Py_ssize_t fill = so->fill;
     552         315 :     PyObject_GC_UnTrack(so);
     553         315 :     Py_TRASHCAN_SAFE_BEGIN(so)
     554         315 :     if (so->weakreflist != NULL)
     555           0 :         PyObject_ClearWeakRefs((PyObject *) so);
     556             : 
     557        3477 :     for (entry = so->table; fill > 0; entry++) {
     558        3162 :         if (entry->key) {
     559         966 :             --fill;
     560         966 :             Py_DECREF(entry->key);
     561             :         }
     562             :     }
     563         315 :     if (so->table != so->smalltable)
     564          36 :         PyMem_DEL(so->table);
     565         315 :     if (numfree < PySet_MAXFREELIST && PyAnySet_CheckExact(so))
     566         315 :         free_list[numfree++] = so;
     567             :     else
     568           0 :         Py_TYPE(so)->tp_free(so);
     569         315 :     Py_TRASHCAN_SAFE_END(so)
     570         315 : }
     571             : 
     572             : static int
     573           0 : set_tp_print(PySetObject *so, FILE *fp, int flags)
     574             : {
     575             :     setentry *entry;
     576           0 :     Py_ssize_t pos=0;
     577           0 :     char *emit = "";            /* No separator emitted on first pass */
     578           0 :     char *separator = ", ";
     579           0 :     int status = Py_ReprEnter((PyObject*)so);
     580             : 
     581           0 :     if (status != 0) {
     582           0 :         if (status < 0)
     583           0 :             return status;
     584             :         Py_BEGIN_ALLOW_THREADS
     585           0 :         fprintf(fp, "%s(...)", so->ob_type->tp_name);
     586             :         Py_END_ALLOW_THREADS
     587           0 :         return 0;
     588             :     }
     589             : 
     590             :     Py_BEGIN_ALLOW_THREADS
     591           0 :     fprintf(fp, "%s([", so->ob_type->tp_name);
     592             :     Py_END_ALLOW_THREADS
     593           0 :     while (set_next(so, &pos, &entry)) {
     594             :         Py_BEGIN_ALLOW_THREADS
     595           0 :         fputs(emit, fp);
     596             :         Py_END_ALLOW_THREADS
     597           0 :         emit = separator;
     598           0 :         if (PyObject_Print(entry->key, fp, 0) != 0) {
     599           0 :             Py_ReprLeave((PyObject*)so);
     600           0 :             return -1;
     601             :         }
     602             :     }
     603             :     Py_BEGIN_ALLOW_THREADS
     604           0 :     fputs("])", fp);
     605             :     Py_END_ALLOW_THREADS
     606           0 :     Py_ReprLeave((PyObject*)so);
     607           0 :     return 0;
     608             : }
     609             : 
     610             : static PyObject *
     611           0 : set_repr(PySetObject *so)
     612             : {
     613           0 :     PyObject *keys, *result=NULL, *listrepr;
     614           0 :     int status = Py_ReprEnter((PyObject*)so);
     615             : 
     616           0 :     if (status != 0) {
     617           0 :         if (status < 0)
     618           0 :             return NULL;
     619           0 :         return PyString_FromFormat("%s(...)", so->ob_type->tp_name);
     620             :     }
     621             : 
     622           0 :     keys = PySequence_List((PyObject *)so);
     623           0 :     if (keys == NULL)
     624           0 :         goto done;
     625           0 :     listrepr = PyObject_Repr(keys);
     626           0 :     Py_DECREF(keys);
     627           0 :     if (listrepr == NULL)
     628           0 :         goto done;
     629             : 
     630           0 :     result = PyString_FromFormat("%s(%s)", so->ob_type->tp_name,
     631           0 :         PyString_AS_STRING(listrepr));
     632           0 :     Py_DECREF(listrepr);
     633             : done:
     634           0 :     Py_ReprLeave((PyObject*)so);
     635           0 :     return result;
     636             : }
     637             : 
     638             : static Py_ssize_t
     639         132 : set_len(PyObject *so)
     640             : {
     641         132 :     return ((PySetObject *)so)->used;
     642             : }
     643             : 
     644             : static int
     645          66 : set_merge(PySetObject *so, PyObject *otherset)
     646             : {
     647             :     PySetObject *other;
     648             :     PyObject *key;
     649             :     long hash;
     650             :     register Py_ssize_t i;
     651             :     register setentry *entry;
     652             : 
     653             :     assert (PyAnySet_Check(so));
     654             :     assert (PyAnySet_Check(otherset));
     655             : 
     656          66 :     other = (PySetObject*)otherset;
     657          66 :     if (other == so || other->used == 0)
     658             :         /* a.update(a) or a.update({}); nothing to do */
     659          24 :         return 0;
     660             :     /* Do one big resize at the start, rather than
     661             :      * incrementally resizing as we insert new keys.  Expect
     662             :      * that there will be no (or few) overlapping keys.
     663             :      */
     664          42 :     if ((so->fill + other->used)*3 >= (so->mask+1)*2) {
     665           6 :        if (set_table_resize(so, (so->used + other->used)*2) != 0)
     666           0 :            return -1;
     667             :     }
     668         810 :     for (i = 0; i <= other->mask; i++) {
     669         768 :         entry = &other->table[i];
     670         768 :         key = entry->key;
     671         768 :         hash = entry->hash;
     672         945 :         if (key != NULL &&
     673         177 :             key != dummy) {
     674         177 :             Py_INCREF(key);
     675         177 :             if (set_insert_key(so, key, hash) == -1) {
     676           0 :                 Py_DECREF(key);
     677           0 :                 return -1;
     678             :             }
     679             :         }
     680             :     }
     681          42 :     return 0;
     682             : }
     683             : 
     684             : static int
     685       16347 : set_contains_key(PySetObject *so, PyObject *key)
     686             : {
     687             :     long hash;
     688             :     setentry *entry;
     689             : 
     690       31743 :     if (!PyString_CheckExact(key) ||
     691       15396 :         (hash = ((PyStringObject *) key)->ob_shash) == -1) {
     692        2238 :         hash = PyObject_Hash(key);
     693        2238 :         if (hash == -1)
     694           0 :             return -1;
     695             :     }
     696       16347 :     entry = (so->lookup)(so, key, hash);
     697       16347 :     if (entry == NULL)
     698           0 :         return -1;
     699       16347 :     key = entry->key;
     700       16347 :     return key != NULL && key != dummy;
     701             : }
     702             : 
     703             : static int
     704           0 : set_contains_entry(PySetObject *so, setentry *entry)
     705             : {
     706             :     PyObject *key;
     707             :     setentry *lu_entry;
     708             : 
     709           0 :     lu_entry = (so->lookup)(so, entry->key, entry->hash);
     710           0 :     if (lu_entry == NULL)
     711           0 :         return -1;
     712           0 :     key = lu_entry->key;
     713           0 :     return key != NULL && key != dummy;
     714             : }
     715             : 
     716             : static PyObject *
     717           0 : set_pop(PySetObject *so)
     718             : {
     719           0 :     register Py_ssize_t i = 0;
     720             :     register setentry *entry;
     721             :     PyObject *key;
     722             : 
     723             :     assert (PyAnySet_Check(so));
     724           0 :     if (so->used == 0) {
     725           0 :         PyErr_SetString(PyExc_KeyError, "pop from an empty set");
     726           0 :         return NULL;
     727             :     }
     728             : 
     729             :     /* Set entry to "the first" unused or dummy set entry.  We abuse
     730             :      * the hash field of slot 0 to hold a search finger:
     731             :      * If slot 0 has a value, use slot 0.
     732             :      * Else slot 0 is being used to hold a search finger,
     733             :      * and we use its hash value as the first index to look.
     734             :      */
     735           0 :     entry = &so->table[0];
     736           0 :     if (entry->key == NULL || entry->key == dummy) {
     737           0 :         i = entry->hash;
     738             :         /* The hash field may be a real hash value, or it may be a
     739             :          * legit search finger, or it may be a once-legit search
     740             :          * finger that's out of bounds now because it wrapped around
     741             :          * or the table shrunk -- simply make sure it's in bounds now.
     742             :          */
     743           0 :         if (i > so->mask || i < 1)
     744           0 :             i = 1;              /* skip slot 0 */
     745           0 :         while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
     746           0 :             i++;
     747           0 :             if (i > so->mask)
     748           0 :                 i = 1;
     749             :         }
     750             :     }
     751           0 :     key = entry->key;
     752           0 :     Py_INCREF(dummy);
     753           0 :     entry->key = dummy;
     754           0 :     so->used--;
     755           0 :     so->table[0].hash = i + 1;  /* next place to start */
     756           0 :     return key;
     757             : }
     758             : 
     759             : PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\
     760             : Raises KeyError if the set is empty.");
     761             : 
     762             : static int
     763        2720 : set_traverse(PySetObject *so, visitproc visit, void *arg)
     764             : {
     765        2720 :     Py_ssize_t pos = 0;
     766             :     setentry *entry;
     767             : 
     768       10228 :     while (set_next(so, &pos, &entry))
     769        4788 :         Py_VISIT(entry->key);
     770        2720 :     return 0;
     771             : }
     772             : 
     773             : static long
     774           0 : frozenset_hash(PyObject *self)
     775             : {
     776           0 :     PySetObject *so = (PySetObject *)self;
     777           0 :     long h, hash = 1927868237L;
     778             :     setentry *entry;
     779           0 :     Py_ssize_t pos = 0;
     780             : 
     781           0 :     if (so->hash != -1)
     782           0 :         return so->hash;
     783             : 
     784           0 :     hash *= PySet_GET_SIZE(self) + 1;
     785           0 :     while (set_next(so, &pos, &entry)) {
     786             :         /* Work to increase the bit dispersion for closely spaced hash
     787             :            values.  This is important because some use cases have many
     788             :            combinations of a small number of elements with nearby
     789             :            hashes so that many distinct combinations collapse to only
     790             :            a handful of distinct hash values. */
     791           0 :         h = entry->hash;
     792           0 :         hash ^= (h ^ (h << 16) ^ 89869747L)  * 3644798167u;
     793             :     }
     794           0 :     hash = hash * 69069L + 907133923L;
     795           0 :     if (hash == -1)
     796           0 :         hash = 590923713L;
     797           0 :     so->hash = hash;
     798           0 :     return hash;
     799             : }
     800             : 
     801             : /***** Set iterator type ***********************************************/
     802             : 
     803             : typedef struct {
     804             :     PyObject_HEAD
     805             :     PySetObject *si_set; /* Set to NULL when iterator is exhausted */
     806             :     Py_ssize_t si_used;
     807             :     Py_ssize_t si_pos;
     808             :     Py_ssize_t len;
     809             : } setiterobject;
     810             : 
     811             : static void
     812         144 : setiter_dealloc(setiterobject *si)
     813             : {
     814         144 :     Py_XDECREF(si->si_set);
     815         144 :     PyObject_GC_Del(si);
     816         144 : }
     817             : 
     818             : static int
     819           0 : setiter_traverse(setiterobject *si, visitproc visit, void *arg)
     820             : {
     821           0 :     Py_VISIT(si->si_set);
     822           0 :     return 0;
     823             : }
     824             : 
     825             : static PyObject *
     826           0 : setiter_len(setiterobject *si)
     827             : {
     828           0 :     Py_ssize_t len = 0;
     829           0 :     if (si->si_set != NULL && si->si_used == si->si_set->used)
     830           0 :         len = si->len;
     831           0 :     return PyInt_FromLong(len);
     832             : }
     833             : 
     834             : PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
     835             : 
     836             : static PyMethodDef setiter_methods[] = {
     837             :     {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
     838             :     {NULL,              NULL}           /* sentinel */
     839             : };
     840             : 
     841         351 : static PyObject *setiter_iternext(setiterobject *si)
     842             : {
     843             :     PyObject *key;
     844             :     register Py_ssize_t i, mask;
     845             :     register setentry *entry;
     846         351 :     PySetObject *so = si->si_set;
     847             : 
     848         351 :     if (so == NULL)
     849           0 :         return NULL;
     850             :     assert (PyAnySet_Check(so));
     851             : 
     852         351 :     if (si->si_used != so->used) {
     853           0 :         PyErr_SetString(PyExc_RuntimeError,
     854             :                         "Set changed size during iteration");
     855           0 :         si->si_used = -1; /* Make this state sticky */
     856           0 :         return NULL;
     857             :     }
     858             : 
     859         351 :     i = si->si_pos;
     860             :     assert(i>=0);
     861         351 :     entry = so->table;
     862         351 :     mask = so->mask;
     863        2007 :     while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
     864        1305 :         i++;
     865         351 :     si->si_pos = i+1;
     866         351 :     if (i > mask)
     867         144 :         goto fail;
     868         207 :     si->len--;
     869         207 :     key = entry[i].key;
     870         207 :     Py_INCREF(key);
     871         207 :     return key;
     872             : 
     873             : fail:
     874         144 :     si->si_set = NULL;
     875         144 :     Py_DECREF(so);
     876         144 :     return NULL;
     877             : }
     878             : 
     879             : static PyTypeObject PySetIter_Type = {
     880             :     PyVarObject_HEAD_INIT(&PyType_Type, 0)
     881             :     "setiterator",                              /* tp_name */
     882             :     sizeof(setiterobject),                      /* tp_basicsize */
     883             :     0,                                          /* tp_itemsize */
     884             :     /* methods */
     885             :     (destructor)setiter_dealloc,                /* tp_dealloc */
     886             :     0,                                          /* tp_print */
     887             :     0,                                          /* tp_getattr */
     888             :     0,                                          /* tp_setattr */
     889             :     0,                                          /* tp_compare */
     890             :     0,                                          /* tp_repr */
     891             :     0,                                          /* tp_as_number */
     892             :     0,                                          /* tp_as_sequence */
     893             :     0,                                          /* tp_as_mapping */
     894             :     0,                                          /* tp_hash */
     895             :     0,                                          /* tp_call */
     896             :     0,                                          /* tp_str */
     897             :     PyObject_GenericGetAttr,                    /* tp_getattro */
     898             :     0,                                          /* tp_setattro */
     899             :     0,                                          /* tp_as_buffer */
     900             :     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
     901             :     0,                                          /* tp_doc */
     902             :     (traverseproc)setiter_traverse,             /* tp_traverse */
     903             :     0,                                          /* tp_clear */
     904             :     0,                                          /* tp_richcompare */
     905             :     0,                                          /* tp_weaklistoffset */
     906             :     PyObject_SelfIter,                          /* tp_iter */
     907             :     (iternextfunc)setiter_iternext,             /* tp_iternext */
     908             :     setiter_methods,                            /* tp_methods */
     909             :     0,
     910             : };
     911             : 
     912             : static PyObject *
     913         144 : set_iter(PySetObject *so)
     914             : {
     915         144 :     setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type);
     916         144 :     if (si == NULL)
     917           0 :         return NULL;
     918         144 :     Py_INCREF(so);
     919         144 :     si->si_set = so;
     920         144 :     si->si_used = so->used;
     921         144 :     si->si_pos = 0;
     922         144 :     si->len = so->used;
     923         144 :     _PyObject_GC_TRACK(si);
     924         144 :     return (PyObject *)si;
     925             : }
     926             : 
     927             : static int
     928         180 : set_update_internal(PySetObject *so, PyObject *other)
     929             : {
     930             :     PyObject *key, *it;
     931             : 
     932         180 :     if (PyAnySet_Check(other))
     933          66 :         return set_merge(so, other);
     934             : 
     935         114 :     if (PyDict_CheckExact(other)) {
     936             :         PyObject *value;
     937           0 :         Py_ssize_t pos = 0;
     938             :         long hash;
     939           0 :         Py_ssize_t dictsize = PyDict_Size(other);
     940             : 
     941             :         /* Do one big resize at the start, rather than
     942             :         * incrementally resizing as we insert new keys.  Expect
     943             :         * that there will be no (or few) overlapping keys.
     944             :         */
     945           0 :         if (dictsize == -1)
     946           0 :             return -1;
     947           0 :         if ((so->fill + dictsize)*3 >= (so->mask+1)*2) {
     948           0 :             if (set_table_resize(so, (so->used + dictsize)*2) != 0)
     949           0 :                 return -1;
     950             :         }
     951           0 :         while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
     952             :             setentry an_entry;
     953             : 
     954           0 :             an_entry.hash = hash;
     955           0 :             an_entry.key = key;
     956           0 :             if (set_add_entry(so, &an_entry) == -1)
     957           0 :                 return -1;
     958             :         }
     959           0 :         return 0;
     960             :     }
     961             : 
     962         114 :     it = PyObject_GetIter(other);
     963         114 :     if (it == NULL)
     964           0 :         return -1;
     965             : 
     966         888 :     while ((key = PyIter_Next(it)) != NULL) {
     967         660 :         if (set_add_key(so, key) == -1) {
     968           0 :             Py_DECREF(it);
     969           0 :             Py_DECREF(key);
     970           0 :             return -1;
     971             :         }
     972         660 :         Py_DECREF(key);
     973             :     }
     974         114 :     Py_DECREF(it);
     975         114 :     if (PyErr_Occurred())
     976           0 :         return -1;
     977         114 :     return 0;
     978             : }
     979             : 
     980             : static PyObject *
     981           6 : set_update(PySetObject *so, PyObject *args)
     982             : {
     983             :     Py_ssize_t i;
     984             : 
     985          12 :     for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
     986           6 :         PyObject *other = PyTuple_GET_ITEM(args, i);
     987           6 :         if (set_update_internal(so, other) == -1)
     988           0 :             return NULL;
     989             :     }
     990           6 :     Py_RETURN_NONE;
     991             : }
     992             : 
     993             : PyDoc_STRVAR(update_doc,
     994             : "Update a set with the union of itself and others.");
     995             : 
     996             : static PyObject *
     997         714 : make_new_set(PyTypeObject *type, PyObject *iterable)
     998             : {
     999         714 :     register PySetObject *so = NULL;
    1000             : 
    1001         714 :     if (dummy == NULL) { /* Auto-initialize dummy */
    1002           3 :         dummy = PyString_FromString("<dummy key>");
    1003           3 :         if (dummy == NULL)
    1004           0 :             return NULL;
    1005             :     }
    1006             : 
    1007             :     /* create PySetObject structure */
    1008         714 :     if (numfree &&
    1009          48 :         (type == &PySet_Type  ||  type == &PyFrozenSet_Type)) {
    1010         258 :         so = free_list[--numfree];
    1011             :         assert (so != NULL && PyAnySet_CheckExact(so));
    1012         258 :         Py_TYPE(so) = type;
    1013         258 :         _Py_NewReference((PyObject *)so);
    1014         258 :         EMPTY_TO_MINSIZE(so);
    1015         258 :         PyObject_GC_Track(so);
    1016             :     } else {
    1017         456 :         so = (PySetObject *)type->tp_alloc(type, 0);
    1018         456 :         if (so == NULL)
    1019           0 :             return NULL;
    1020             :         /* tp_alloc has already zeroed the structure */
    1021             :         assert(so->table == NULL && so->fill == 0 && so->used == 0);
    1022         456 :         INIT_NONZERO_SET_SLOTS(so);
    1023             :     }
    1024             : 
    1025         714 :     so->lookup = set_lookkey_string;
    1026         714 :     so->weakreflist = NULL;
    1027             : 
    1028         714 :     if (iterable != NULL) {
    1029          69 :         if (set_update_internal(so, iterable) == -1) {
    1030           0 :             Py_DECREF(so);
    1031           0 :             return NULL;
    1032             :         }
    1033             :     }
    1034             : 
    1035         714 :     return (PyObject *)so;
    1036             : }
    1037             : 
    1038             : /* The empty frozenset is a singleton */
    1039             : static PyObject *emptyfrozenset = NULL;
    1040             : 
    1041             : static PyObject *
    1042          66 : frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    1043             : {
    1044          66 :     PyObject *iterable = NULL, *result;
    1045             : 
    1046          66 :     if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds))
    1047           0 :         return NULL;
    1048             : 
    1049          66 :     if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
    1050           0 :         return NULL;
    1051             : 
    1052          66 :     if (type != &PyFrozenSet_Type)
    1053           0 :         return make_new_set(type, iterable);
    1054             : 
    1055          66 :     if (iterable != NULL) {
    1056             :         /* frozenset(f) is idempotent */
    1057          66 :         if (PyFrozenSet_CheckExact(iterable)) {
    1058           0 :             Py_INCREF(iterable);
    1059           0 :             return iterable;
    1060             :         }
    1061          66 :         result = make_new_set(type, iterable);
    1062          66 :         if (result == NULL || PySet_GET_SIZE(result))
    1063          42 :             return result;
    1064          24 :         Py_DECREF(result);
    1065             :     }
    1066             :     /* The empty frozenset is a singleton */
    1067          24 :     if (emptyfrozenset == NULL)
    1068           3 :         emptyfrozenset = make_new_set(type, NULL);
    1069          24 :     Py_XINCREF(emptyfrozenset);
    1070          24 :     return emptyfrozenset;
    1071             : }
    1072             : 
    1073             : void
    1074           3 : PySet_Fini(void)
    1075             : {
    1076             :     PySetObject *so;
    1077             : 
    1078          63 :     while (numfree) {
    1079          57 :         numfree--;
    1080          57 :         so = free_list[numfree];
    1081          57 :         PyObject_GC_Del(so);
    1082             :     }
    1083           3 :     Py_CLEAR(dummy);
    1084           3 :     Py_CLEAR(emptyfrozenset);
    1085           3 : }
    1086             : 
    1087             : static PyObject *
    1088         636 : set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    1089             : {
    1090         636 :     if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds))
    1091           0 :         return NULL;
    1092             : 
    1093         636 :     return make_new_set(type, NULL);
    1094             : }
    1095             : 
    1096             : /* set_swap_bodies() switches the contents of any two sets by moving their
    1097             :    internal data pointers and, if needed, copying the internal smalltables.
    1098             :    Semantically equivalent to:
    1099             : 
    1100             :      t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
    1101             : 
    1102             :    The function always succeeds and it leaves both objects in a stable state.
    1103             :    Useful for creating temporary frozensets from sets for membership testing
    1104             :    in __contains__(), discard(), and remove().  Also useful for operations
    1105             :    that update in-place (by allowing an intermediate result to be swapped
    1106             :    into one of the original inputs).
    1107             : */
    1108             : 
    1109             : static void
    1110           0 : set_swap_bodies(PySetObject *a, PySetObject *b)
    1111             : {
    1112             :     Py_ssize_t t;
    1113             :     setentry *u;
    1114             :     setentry *(*f)(PySetObject *so, PyObject *key, long hash);
    1115             :     setentry tab[PySet_MINSIZE];
    1116             :     long h;
    1117             : 
    1118           0 :     t = a->fill;     a->fill   = b->fill;        b->fill  = t;
    1119           0 :     t = a->used;     a->used   = b->used;        b->used  = t;
    1120           0 :     t = a->mask;     a->mask   = b->mask;        b->mask  = t;
    1121             : 
    1122           0 :     u = a->table;
    1123           0 :     if (a->table == a->smalltable)
    1124           0 :         u = b->smalltable;
    1125           0 :     a->table  = b->table;
    1126           0 :     if (b->table == b->smalltable)
    1127           0 :         a->table = a->smalltable;
    1128           0 :     b->table = u;
    1129             : 
    1130           0 :     f = a->lookup;   a->lookup = b->lookup;      b->lookup = f;
    1131             : 
    1132           0 :     if (a->table == a->smalltable || b->table == b->smalltable) {
    1133           0 :         memcpy(tab, a->smalltable, sizeof(tab));
    1134           0 :         memcpy(a->smalltable, b->smalltable, sizeof(tab));
    1135           0 :         memcpy(b->smalltable, tab, sizeof(tab));
    1136             :     }
    1137             : 
    1138           0 :     if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type)  &&
    1139           0 :         PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) {
    1140           0 :         h = a->hash;     a->hash = b->hash;  b->hash = h;
    1141             :     } else {
    1142           0 :         a->hash = -1;
    1143           0 :         b->hash = -1;
    1144             :     }
    1145           0 : }
    1146             : 
    1147             : static PyObject *
    1148           3 : set_copy(PySetObject *so)
    1149             : {
    1150           3 :     return make_new_set(Py_TYPE(so), (PyObject *)so);
    1151             : }
    1152             : 
    1153             : static PyObject *
    1154           0 : frozenset_copy(PySetObject *so)
    1155             : {
    1156           0 :     if (PyFrozenSet_CheckExact(so)) {
    1157           0 :         Py_INCREF(so);
    1158           0 :         return (PyObject *)so;
    1159             :     }
    1160           0 :     return set_copy(so);
    1161             : }
    1162             : 
    1163             : PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
    1164             : 
    1165             : static PyObject *
    1166           0 : set_clear(PySetObject *so)
    1167             : {
    1168           0 :     set_clear_internal(so);
    1169           0 :     Py_RETURN_NONE;
    1170             : }
    1171             : 
    1172             : PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
    1173             : 
    1174             : static PyObject *
    1175           3 : set_union(PySetObject *so, PyObject *args)
    1176             : {
    1177             :     PySetObject *result;
    1178             :     PyObject *other;
    1179             :     Py_ssize_t i;
    1180             : 
    1181           3 :     result = (PySetObject *)set_copy(so);
    1182           3 :     if (result == NULL)
    1183           0 :         return NULL;
    1184             : 
    1185           6 :     for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
    1186           3 :         other = PyTuple_GET_ITEM(args, i);
    1187           3 :         if ((PyObject *)so == other)
    1188           0 :             continue;
    1189           3 :         if (set_update_internal(result, other) == -1) {
    1190           0 :             Py_DECREF(result);
    1191           0 :             return NULL;
    1192             :         }
    1193             :     }
    1194           3 :     return (PyObject *)result;
    1195             : }
    1196             : 
    1197             : PyDoc_STRVAR(union_doc,
    1198             :  "Return the union of sets as a new set.\n\
    1199             : \n\
    1200             : (i.e. all elements that are in either set.)");
    1201             : 
    1202             : static PyObject *
    1203           0 : set_or(PySetObject *so, PyObject *other)
    1204             : {
    1205             :     PySetObject *result;
    1206             : 
    1207           0 :     if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
    1208           0 :         Py_INCREF(Py_NotImplemented);
    1209           0 :         return Py_NotImplemented;
    1210             :     }
    1211             : 
    1212           0 :     result = (PySetObject *)set_copy(so);
    1213           0 :     if (result == NULL)
    1214           0 :         return NULL;
    1215           0 :     if ((PyObject *)so == other)
    1216           0 :         return (PyObject *)result;
    1217           0 :     if (set_update_internal(result, other) == -1) {
    1218           0 :         Py_DECREF(result);
    1219           0 :         return NULL;
    1220             :     }
    1221           0 :     return (PyObject *)result;
    1222             : }
    1223             : 
    1224             : static PyObject *
    1225           0 : set_ior(PySetObject *so, PyObject *other)
    1226             : {
    1227           0 :     if (!PyAnySet_Check(other)) {
    1228           0 :         Py_INCREF(Py_NotImplemented);
    1229           0 :         return Py_NotImplemented;
    1230             :     }
    1231           0 :     if (set_update_internal(so, other) == -1)
    1232           0 :         return NULL;
    1233           0 :     Py_INCREF(so);
    1234           0 :     return (PyObject *)so;
    1235             : }
    1236             : 
    1237             : static PyObject *
    1238           0 : set_intersection(PySetObject *so, PyObject *other)
    1239             : {
    1240             :     PySetObject *result;
    1241             :     PyObject *key, *it, *tmp;
    1242             : 
    1243           0 :     if ((PyObject *)so == other)
    1244           0 :         return set_copy(so);
    1245             : 
    1246           0 :     result = (PySetObject *)make_new_set(Py_TYPE(so), NULL);
    1247           0 :     if (result == NULL)
    1248           0 :         return NULL;
    1249             : 
    1250           0 :     if (PyAnySet_Check(other)) {
    1251           0 :         Py_ssize_t pos = 0;
    1252             :         setentry *entry;
    1253             : 
    1254           0 :         if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
    1255           0 :             tmp = (PyObject *)so;
    1256           0 :             so = (PySetObject *)other;
    1257           0 :             other = tmp;
    1258             :         }
    1259             : 
    1260           0 :         while (set_next((PySetObject *)other, &pos, &entry)) {
    1261           0 :             int rv = set_contains_entry(so, entry);
    1262           0 :             if (rv == -1) {
    1263           0 :                 Py_DECREF(result);
    1264           0 :                 return NULL;
    1265             :             }
    1266           0 :             if (rv) {
    1267           0 :                 if (set_add_entry(result, entry) == -1) {
    1268           0 :                     Py_DECREF(result);
    1269           0 :                     return NULL;
    1270             :                 }
    1271             :             }
    1272             :         }
    1273           0 :         return (PyObject *)result;
    1274             :     }
    1275             : 
    1276           0 :     it = PyObject_GetIter(other);
    1277           0 :     if (it == NULL) {
    1278           0 :         Py_DECREF(result);
    1279           0 :         return NULL;
    1280             :     }
    1281             : 
    1282           0 :     while ((key = PyIter_Next(it)) != NULL) {
    1283             :         int rv;
    1284             :         setentry entry;
    1285           0 :         long hash = PyObject_Hash(key);
    1286             : 
    1287           0 :         if (hash == -1) {
    1288           0 :             Py_DECREF(it);
    1289           0 :             Py_DECREF(result);
    1290           0 :             Py_DECREF(key);
    1291           0 :             return NULL;
    1292             :         }
    1293           0 :         entry.hash = hash;
    1294           0 :         entry.key = key;
    1295           0 :         rv = set_contains_entry(so, &entry);
    1296           0 :         if (rv == -1) {
    1297           0 :             Py_DECREF(it);
    1298           0 :             Py_DECREF(result);
    1299           0 :             Py_DECREF(key);
    1300           0 :             return NULL;
    1301             :         }
    1302           0 :         if (rv) {
    1303           0 :             if (set_add_entry(result, &entry) == -1) {
    1304           0 :                 Py_DECREF(it);
    1305           0 :                 Py_DECREF(result);
    1306           0 :                 Py_DECREF(key);
    1307           0 :                 return NULL;
    1308             :             }
    1309             :         }
    1310           0 :         Py_DECREF(key);
    1311             :     }
    1312           0 :     Py_DECREF(it);
    1313           0 :     if (PyErr_Occurred()) {
    1314           0 :         Py_DECREF(result);
    1315           0 :         return NULL;
    1316             :     }
    1317           0 :     return (PyObject *)result;
    1318             : }
    1319             : 
    1320             : static PyObject *
    1321           0 : set_intersection_multi(PySetObject *so, PyObject *args)
    1322             : {
    1323             :     Py_ssize_t i;
    1324           0 :     PyObject *result = (PyObject *)so;
    1325             : 
    1326           0 :     if (PyTuple_GET_SIZE(args) == 0)
    1327           0 :         return set_copy(so);
    1328             : 
    1329           0 :     Py_INCREF(so);
    1330           0 :     for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
    1331           0 :         PyObject *other = PyTuple_GET_ITEM(args, i);
    1332           0 :         PyObject *newresult = set_intersection((PySetObject *)result, other);
    1333           0 :         if (newresult == NULL) {
    1334           0 :             Py_DECREF(result);
    1335           0 :             return NULL;
    1336             :         }
    1337           0 :         Py_DECREF(result);
    1338           0 :         result = newresult;
    1339             :     }
    1340           0 :     return result;
    1341             : }
    1342             : 
    1343             : PyDoc_STRVAR(intersection_doc,
    1344             : "Return the intersection of two or more sets as a new set.\n\
    1345             : \n\
    1346             : (i.e. elements that are common to all of the sets.)");
    1347             : 
    1348             : static PyObject *
    1349           0 : set_intersection_update(PySetObject *so, PyObject *other)
    1350             : {
    1351             :     PyObject *tmp;
    1352             : 
    1353           0 :     tmp = set_intersection(so, other);
    1354           0 :     if (tmp == NULL)
    1355           0 :         return NULL;
    1356           0 :     set_swap_bodies(so, (PySetObject *)tmp);
    1357           0 :     Py_DECREF(tmp);
    1358           0 :     Py_RETURN_NONE;
    1359             : }
    1360             : 
    1361             : static PyObject *
    1362           0 : set_intersection_update_multi(PySetObject *so, PyObject *args)
    1363             : {
    1364             :     PyObject *tmp;
    1365             : 
    1366           0 :     tmp = set_intersection_multi(so, args);
    1367           0 :     if (tmp == NULL)
    1368           0 :         return NULL;
    1369           0 :     set_swap_bodies(so, (PySetObject *)tmp);
    1370           0 :     Py_DECREF(tmp);
    1371           0 :     Py_RETURN_NONE;
    1372             : }
    1373             : 
    1374             : PyDoc_STRVAR(intersection_update_doc,
    1375             : "Update a set with the intersection of itself and another.");
    1376             : 
    1377             : static PyObject *
    1378           0 : set_and(PySetObject *so, PyObject *other)
    1379             : {
    1380           0 :     if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
    1381           0 :         Py_INCREF(Py_NotImplemented);
    1382           0 :         return Py_NotImplemented;
    1383             :     }
    1384           0 :     return set_intersection(so, other);
    1385             : }
    1386             : 
    1387             : static PyObject *
    1388           0 : set_iand(PySetObject *so, PyObject *other)
    1389             : {
    1390             :     PyObject *result;
    1391             : 
    1392           0 :     if (!PyAnySet_Check(other)) {
    1393           0 :         Py_INCREF(Py_NotImplemented);
    1394           0 :         return Py_NotImplemented;
    1395             :     }
    1396           0 :     result = set_intersection_update(so, other);
    1397           0 :     if (result == NULL)
    1398           0 :         return NULL;
    1399           0 :     Py_DECREF(result);
    1400           0 :     Py_INCREF(so);
    1401           0 :     return (PyObject *)so;
    1402             : }
    1403             : 
    1404             : static PyObject *
    1405           0 : set_isdisjoint(PySetObject *so, PyObject *other)
    1406             : {
    1407             :     PyObject *key, *it, *tmp;
    1408             : 
    1409           0 :     if ((PyObject *)so == other) {
    1410           0 :         if (PySet_GET_SIZE(so) == 0)
    1411           0 :             Py_RETURN_TRUE;
    1412             :         else
    1413           0 :             Py_RETURN_FALSE;
    1414             :     }
    1415             : 
    1416           0 :     if (PyAnySet_CheckExact(other)) {
    1417           0 :         Py_ssize_t pos = 0;
    1418             :         setentry *entry;
    1419             : 
    1420           0 :         if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
    1421           0 :             tmp = (PyObject *)so;
    1422           0 :             so = (PySetObject *)other;
    1423           0 :             other = tmp;
    1424             :         }
    1425           0 :         while (set_next((PySetObject *)other, &pos, &entry)) {
    1426           0 :             int rv = set_contains_entry(so, entry);
    1427           0 :             if (rv == -1)
    1428           0 :                 return NULL;
    1429           0 :             if (rv)
    1430           0 :                 Py_RETURN_FALSE;
    1431             :         }
    1432           0 :         Py_RETURN_TRUE;
    1433             :     }
    1434             : 
    1435           0 :     it = PyObject_GetIter(other);
    1436           0 :     if (it == NULL)
    1437           0 :         return NULL;
    1438             : 
    1439           0 :     while ((key = PyIter_Next(it)) != NULL) {
    1440             :         int rv;
    1441             :         setentry entry;
    1442           0 :         long hash = PyObject_Hash(key);
    1443             : 
    1444           0 :         if (hash == -1) {
    1445           0 :             Py_DECREF(key);
    1446           0 :             Py_DECREF(it);
    1447           0 :             return NULL;
    1448             :         }
    1449           0 :         entry.hash = hash;
    1450           0 :         entry.key = key;
    1451           0 :         rv = set_contains_entry(so, &entry);
    1452           0 :         Py_DECREF(key);
    1453           0 :         if (rv == -1) {
    1454           0 :             Py_DECREF(it);
    1455           0 :             return NULL;
    1456             :         }
    1457           0 :         if (rv) {
    1458           0 :             Py_DECREF(it);
    1459           0 :             Py_RETURN_FALSE;
    1460             :         }
    1461             :     }
    1462           0 :     Py_DECREF(it);
    1463           0 :     if (PyErr_Occurred())
    1464           0 :         return NULL;
    1465           0 :     Py_RETURN_TRUE;
    1466             : }
    1467             : 
    1468             : PyDoc_STRVAR(isdisjoint_doc,
    1469             : "Return True if two sets have a null intersection.");
    1470             : 
    1471             : static int
    1472           0 : set_difference_update_internal(PySetObject *so, PyObject *other)
    1473             : {
    1474           0 :     if ((PyObject *)so == other)
    1475           0 :         return set_clear_internal(so);
    1476             : 
    1477           0 :     if (PyAnySet_Check(other)) {
    1478             :         setentry *entry;
    1479           0 :         Py_ssize_t pos = 0;
    1480             : 
    1481           0 :         while (set_next((PySetObject *)other, &pos, &entry))
    1482           0 :             if (set_discard_entry(so, entry) == -1)
    1483           0 :                 return -1;
    1484             :     } else {
    1485             :         PyObject *key, *it;
    1486           0 :         it = PyObject_GetIter(other);
    1487           0 :         if (it == NULL)
    1488           0 :             return -1;
    1489             : 
    1490           0 :         while ((key = PyIter_Next(it)) != NULL) {
    1491           0 :             if (set_discard_key(so, key) == -1) {
    1492           0 :                 Py_DECREF(it);
    1493           0 :                 Py_DECREF(key);
    1494           0 :                 return -1;
    1495             :             }
    1496           0 :             Py_DECREF(key);
    1497             :         }
    1498           0 :         Py_DECREF(it);
    1499           0 :         if (PyErr_Occurred())
    1500           0 :             return -1;
    1501             :     }
    1502             :     /* If more than 1/5 are dummies, then resize them away. */
    1503           0 :     if ((so->fill - so->used) * 5 < so->mask)
    1504           0 :         return 0;
    1505           0 :     return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
    1506             : }
    1507             : 
    1508             : static PyObject *
    1509           0 : set_difference_update(PySetObject *so, PyObject *args)
    1510             : {
    1511             :     Py_ssize_t i;
    1512             : 
    1513           0 :     for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
    1514           0 :         PyObject *other = PyTuple_GET_ITEM(args, i);
    1515           0 :         if (set_difference_update_internal(so, other) == -1)
    1516           0 :             return NULL;
    1517             :     }
    1518           0 :     Py_RETURN_NONE;
    1519             : }
    1520             : 
    1521             : PyDoc_STRVAR(difference_update_doc,
    1522             : "Remove all elements of another set from this set.");
    1523             : 
    1524             : static PyObject *
    1525           0 : set_difference(PySetObject *so, PyObject *other)
    1526             : {
    1527             :     PyObject *result;
    1528             :     setentry *entry;
    1529           0 :     Py_ssize_t pos = 0;
    1530             : 
    1531           0 :     if (!PyAnySet_Check(other)  && !PyDict_CheckExact(other)) {
    1532           0 :         result = set_copy(so);
    1533           0 :         if (result == NULL)
    1534           0 :             return NULL;
    1535           0 :         if (set_difference_update_internal((PySetObject *)result, other) != -1)
    1536           0 :             return result;
    1537           0 :         Py_DECREF(result);
    1538           0 :         return NULL;
    1539             :     }
    1540             : 
    1541           0 :     result = make_new_set(Py_TYPE(so), NULL);
    1542           0 :     if (result == NULL)
    1543           0 :         return NULL;
    1544             : 
    1545           0 :     if (PyDict_CheckExact(other)) {
    1546           0 :         while (set_next(so, &pos, &entry)) {
    1547             :             setentry entrycopy;
    1548             :             int rv;
    1549           0 :             entrycopy.hash = entry->hash;
    1550           0 :             entrycopy.key = entry->key;
    1551           0 :             rv = _PyDict_Contains(other, entry->key, entry->hash);
    1552           0 :             if (rv < 0) {
    1553           0 :                 Py_DECREF(result);
    1554           0 :                 return NULL;
    1555             :             }
    1556           0 :             if (!rv) {
    1557           0 :                 if (set_add_entry((PySetObject *)result, &entrycopy) == -1) {
    1558           0 :                     Py_DECREF(result);
    1559           0 :                     return NULL;
    1560             :                 }
    1561             :             }
    1562             :         }
    1563           0 :         return result;
    1564             :     }
    1565             : 
    1566           0 :     while (set_next(so, &pos, &entry)) {
    1567           0 :         int rv = set_contains_entry((PySetObject *)other, entry);
    1568           0 :         if (rv == -1) {
    1569           0 :             Py_DECREF(result);
    1570           0 :             return NULL;
    1571             :         }
    1572           0 :         if (!rv) {
    1573           0 :             if (set_add_entry((PySetObject *)result, entry) == -1) {
    1574           0 :                 Py_DECREF(result);
    1575           0 :                 return NULL;
    1576             :             }
    1577             :         }
    1578             :     }
    1579           0 :     return result;
    1580             : }
    1581             : 
    1582             : static PyObject *
    1583           0 : set_difference_multi(PySetObject *so, PyObject *args)
    1584             : {
    1585             :     Py_ssize_t i;
    1586             :     PyObject *result, *other;
    1587             : 
    1588           0 :     if (PyTuple_GET_SIZE(args) == 0)
    1589           0 :         return set_copy(so);
    1590             : 
    1591           0 :     other = PyTuple_GET_ITEM(args, 0);
    1592           0 :     result = set_difference(so, other);
    1593           0 :     if (result == NULL)
    1594           0 :         return NULL;
    1595             : 
    1596           0 :     for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) {
    1597           0 :         other = PyTuple_GET_ITEM(args, i);
    1598           0 :         if (set_difference_update_internal((PySetObject *)result, other) == -1) {
    1599           0 :             Py_DECREF(result);
    1600           0 :             return NULL;
    1601             :         }
    1602             :     }
    1603           0 :     return result;
    1604             : }
    1605             : 
    1606             : PyDoc_STRVAR(difference_doc,
    1607             : "Return the difference of two or more sets as a new set.\n\
    1608             : \n\
    1609             : (i.e. all elements that are in this set but not the others.)");
    1610             : static PyObject *
    1611           0 : set_sub(PySetObject *so, PyObject *other)
    1612             : {
    1613           0 :     if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
    1614           0 :         Py_INCREF(Py_NotImplemented);
    1615           0 :         return Py_NotImplemented;
    1616             :     }
    1617           0 :     return set_difference(so, other);
    1618             : }
    1619             : 
    1620             : static PyObject *
    1621           0 : set_isub(PySetObject *so, PyObject *other)
    1622             : {
    1623           0 :     if (!PyAnySet_Check(other)) {
    1624           0 :         Py_INCREF(Py_NotImplemented);
    1625           0 :         return Py_NotImplemented;
    1626             :     }
    1627           0 :     if (set_difference_update_internal(so, other) == -1)
    1628           0 :         return NULL;
    1629           0 :     Py_INCREF(so);
    1630           0 :     return (PyObject *)so;
    1631             : }
    1632             : 
    1633             : static PyObject *
    1634           0 : set_symmetric_difference_update(PySetObject *so, PyObject *other)
    1635             : {
    1636             :     PySetObject *otherset;
    1637             :     PyObject *key;
    1638           0 :     Py_ssize_t pos = 0;
    1639             :     setentry *entry;
    1640             : 
    1641           0 :     if ((PyObject *)so == other)
    1642           0 :         return set_clear(so);
    1643             : 
    1644           0 :     if (PyDict_CheckExact(other)) {
    1645             :         PyObject *value;
    1646             :         int rv;
    1647             :         long hash;
    1648           0 :         while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
    1649             :             setentry an_entry;
    1650             : 
    1651           0 :             Py_INCREF(key);
    1652           0 :             an_entry.hash = hash;
    1653           0 :             an_entry.key = key;
    1654             : 
    1655           0 :             rv = set_discard_entry(so, &an_entry);
    1656           0 :             if (rv == -1) {
    1657           0 :                 Py_DECREF(key);
    1658           0 :                 return NULL;
    1659             :             }
    1660           0 :             if (rv == DISCARD_NOTFOUND) {
    1661           0 :                 if (set_add_entry(so, &an_entry) == -1) {
    1662           0 :                     Py_DECREF(key);
    1663           0 :                     return NULL;
    1664             :                 }
    1665             :             }
    1666           0 :             Py_DECREF(key);
    1667             :         }
    1668           0 :         Py_RETURN_NONE;
    1669             :     }
    1670             : 
    1671           0 :     if (PyAnySet_Check(other)) {
    1672           0 :         Py_INCREF(other);
    1673           0 :         otherset = (PySetObject *)other;
    1674             :     } else {
    1675           0 :         otherset = (PySetObject *)make_new_set(Py_TYPE(so), other);
    1676           0 :         if (otherset == NULL)
    1677           0 :             return NULL;
    1678             :     }
    1679             : 
    1680           0 :     while (set_next(otherset, &pos, &entry)) {
    1681           0 :         int rv = set_discard_entry(so, entry);
    1682           0 :         if (rv == -1) {
    1683           0 :             Py_DECREF(otherset);
    1684           0 :             return NULL;
    1685             :         }
    1686           0 :         if (rv == DISCARD_NOTFOUND) {
    1687           0 :             if (set_add_entry(so, entry) == -1) {
    1688           0 :                 Py_DECREF(otherset);
    1689           0 :                 return NULL;
    1690             :             }
    1691             :         }
    1692             :     }
    1693           0 :     Py_DECREF(otherset);
    1694           0 :     Py_RETURN_NONE;
    1695             : }
    1696             : 
    1697             : PyDoc_STRVAR(symmetric_difference_update_doc,
    1698             : "Update a set with the symmetric difference of itself and another.");
    1699             : 
    1700             : static PyObject *
    1701           0 : set_symmetric_difference(PySetObject *so, PyObject *other)
    1702             : {
    1703             :     PyObject *rv;
    1704             :     PySetObject *otherset;
    1705             : 
    1706           0 :     otherset = (PySetObject *)make_new_set(Py_TYPE(so), other);
    1707           0 :     if (otherset == NULL)
    1708           0 :         return NULL;
    1709           0 :     rv = set_symmetric_difference_update(otherset, (PyObject *)so);
    1710           0 :     if (rv == NULL)
    1711           0 :         return NULL;
    1712           0 :     Py_DECREF(rv);
    1713           0 :     return (PyObject *)otherset;
    1714             : }
    1715             : 
    1716             : PyDoc_STRVAR(symmetric_difference_doc,
    1717             : "Return the symmetric difference of two sets as a new set.\n\
    1718             : \n\
    1719             : (i.e. all elements that are in exactly one of the sets.)");
    1720             : 
    1721             : static PyObject *
    1722           0 : set_xor(PySetObject *so, PyObject *other)
    1723             : {
    1724           0 :     if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
    1725           0 :         Py_INCREF(Py_NotImplemented);
    1726           0 :         return Py_NotImplemented;
    1727             :     }
    1728           0 :     return set_symmetric_difference(so, other);
    1729             : }
    1730             : 
    1731             : static PyObject *
    1732           0 : set_ixor(PySetObject *so, PyObject *other)
    1733             : {
    1734             :     PyObject *result;
    1735             : 
    1736           0 :     if (!PyAnySet_Check(other)) {
    1737           0 :         Py_INCREF(Py_NotImplemented);
    1738           0 :         return Py_NotImplemented;
    1739             :     }
    1740           0 :     result = set_symmetric_difference_update(so, other);
    1741           0 :     if (result == NULL)
    1742           0 :         return NULL;
    1743           0 :     Py_DECREF(result);
    1744           0 :     Py_INCREF(so);
    1745           0 :     return (PyObject *)so;
    1746             : }
    1747             : 
    1748             : static PyObject *
    1749           0 : set_issubset(PySetObject *so, PyObject *other)
    1750             : {
    1751             :     setentry *entry;
    1752           0 :     Py_ssize_t pos = 0;
    1753             : 
    1754           0 :     if (!PyAnySet_Check(other)) {
    1755             :         PyObject *tmp, *result;
    1756           0 :         tmp = make_new_set(&PySet_Type, other);
    1757           0 :         if (tmp == NULL)
    1758           0 :             return NULL;
    1759           0 :         result = set_issubset(so, tmp);
    1760           0 :         Py_DECREF(tmp);
    1761           0 :         return result;
    1762             :     }
    1763           0 :     if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
    1764           0 :         Py_RETURN_FALSE;
    1765             : 
    1766           0 :     while (set_next(so, &pos, &entry)) {
    1767           0 :         int rv = set_contains_entry((PySetObject *)other, entry);
    1768           0 :         if (rv == -1)
    1769           0 :             return NULL;
    1770           0 :         if (!rv)
    1771           0 :             Py_RETURN_FALSE;
    1772             :     }
    1773           0 :     Py_RETURN_TRUE;
    1774             : }
    1775             : 
    1776             : PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
    1777             : 
    1778             : static PyObject *
    1779           0 : set_issuperset(PySetObject *so, PyObject *other)
    1780             : {
    1781             :     PyObject *tmp, *result;
    1782             : 
    1783           0 :     if (!PyAnySet_Check(other)) {
    1784           0 :         tmp = make_new_set(&PySet_Type, other);
    1785           0 :         if (tmp == NULL)
    1786           0 :             return NULL;
    1787           0 :         result = set_issuperset(so, tmp);
    1788           0 :         Py_DECREF(tmp);
    1789           0 :         return result;
    1790             :     }
    1791           0 :     return set_issubset((PySetObject *)other, (PyObject *)so);
    1792             : }
    1793             : 
    1794             : PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
    1795             : 
    1796             : static PyObject *
    1797           0 : set_richcompare(PySetObject *v, PyObject *w, int op)
    1798             : {
    1799             :     PyObject *r1;
    1800             :     int r2;
    1801             : 
    1802           0 :     if(!PyAnySet_Check(w)) {
    1803           0 :         Py_INCREF(Py_NotImplemented);
    1804           0 :         return Py_NotImplemented;
    1805             :     }
    1806           0 :     switch (op) {
    1807             :     case Py_EQ:
    1808           0 :         if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
    1809           0 :             Py_RETURN_FALSE;
    1810           0 :         if (v->hash != -1  &&
    1811           0 :             ((PySetObject *)w)->hash != -1 &&
    1812           0 :             v->hash != ((PySetObject *)w)->hash)
    1813           0 :             Py_RETURN_FALSE;
    1814           0 :         return set_issubset(v, w);
    1815             :     case Py_NE:
    1816           0 :         r1 = set_richcompare(v, w, Py_EQ);
    1817           0 :         if (r1 == NULL)
    1818           0 :             return NULL;
    1819           0 :         r2 = PyObject_IsTrue(r1);
    1820           0 :         Py_DECREF(r1);
    1821           0 :         if (r2 < 0)
    1822           0 :             return NULL;
    1823           0 :         return PyBool_FromLong(!r2);
    1824             :     case Py_LE:
    1825           0 :         return set_issubset(v, w);
    1826             :     case Py_GE:
    1827           0 :         return set_issuperset(v, w);
    1828             :     case Py_LT:
    1829           0 :         if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))
    1830           0 :             Py_RETURN_FALSE;
    1831           0 :         return set_issubset(v, w);
    1832             :     case Py_GT:
    1833           0 :         if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
    1834           0 :             Py_RETURN_FALSE;
    1835           0 :         return set_issuperset(v, w);
    1836             :     }
    1837           0 :     Py_INCREF(Py_NotImplemented);
    1838           0 :     return Py_NotImplemented;
    1839             : }
    1840             : 
    1841             : static int
    1842           0 : set_nocmp(PyObject *self, PyObject *other)
    1843             : {
    1844           0 :     PyErr_SetString(PyExc_TypeError, "cannot compare sets using cmp()");
    1845           0 :     return -1;
    1846             : }
    1847             : 
    1848             : static PyObject *
    1849         345 : set_add(PySetObject *so, PyObject *key)
    1850             : {
    1851         345 :     if (set_add_key(so, key) == -1)
    1852           0 :         return NULL;
    1853         345 :     Py_RETURN_NONE;
    1854             : }
    1855             : 
    1856             : PyDoc_STRVAR(add_doc,
    1857             : "Add an element to a set.\n\
    1858             : \n\
    1859             : This has no effect if the element is already present.");
    1860             : 
    1861             : static int
    1862       16347 : set_contains(PySetObject *so, PyObject *key)
    1863             : {
    1864             :     PyObject *tmpkey;
    1865             :     int rv;
    1866             : 
    1867       16347 :     rv = set_contains_key(so, key);
    1868       16347 :     if (rv == -1) {
    1869           0 :         if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
    1870           0 :             return -1;
    1871           0 :         PyErr_Clear();
    1872           0 :         tmpkey = make_new_set(&PyFrozenSet_Type, key);
    1873           0 :         if (tmpkey == NULL)
    1874           0 :             return -1;
    1875           0 :         rv = set_contains_key(so, tmpkey);
    1876           0 :         Py_DECREF(tmpkey);
    1877             :     }
    1878       16347 :     return rv;
    1879             : }
    1880             : 
    1881             : static PyObject *
    1882         141 : set_direct_contains(PySetObject *so, PyObject *key)
    1883             : {
    1884             :     long result;
    1885             : 
    1886         141 :     result = set_contains(so, key);
    1887         141 :     if (result == -1)
    1888           0 :         return NULL;
    1889         141 :     return PyBool_FromLong(result);
    1890             : }
    1891             : 
    1892             : PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
    1893             : 
    1894             : static PyObject *
    1895          63 : set_remove(PySetObject *so, PyObject *key)
    1896             : {
    1897             :     PyObject *tmpkey;
    1898             :     int rv;
    1899             : 
    1900          63 :     rv = set_discard_key(so, key);
    1901          63 :     if (rv == -1) {
    1902           0 :         if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
    1903           0 :             return NULL;
    1904           0 :         PyErr_Clear();
    1905           0 :         tmpkey = make_new_set(&PyFrozenSet_Type, key);
    1906           0 :         if (tmpkey == NULL)
    1907           0 :             return NULL;
    1908           0 :         rv = set_discard_key(so, tmpkey);
    1909           0 :         Py_DECREF(tmpkey);
    1910           0 :         if (rv == -1)
    1911           0 :             return NULL;
    1912             :     }
    1913             : 
    1914          63 :     if (rv == DISCARD_NOTFOUND) {
    1915           0 :         set_key_error(key);
    1916           0 :         return NULL;
    1917             :     }
    1918          63 :     Py_RETURN_NONE;
    1919             : }
    1920             : 
    1921             : PyDoc_STRVAR(remove_doc,
    1922             : "Remove an element from a set; it must be a member.\n\
    1923             : \n\
    1924             : If the element is not a member, raise a KeyError.");
    1925             : 
    1926             : static PyObject *
    1927           6 : set_discard(PySetObject *so, PyObject *key)
    1928             : {
    1929             :     PyObject *tmpkey;
    1930             :     int rv;
    1931             : 
    1932           6 :     rv = set_discard_key(so, key);
    1933           6 :     if (rv == -1) {
    1934           0 :         if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
    1935           0 :             return NULL;
    1936           0 :         PyErr_Clear();
    1937           0 :         tmpkey = make_new_set(&PyFrozenSet_Type, key);
    1938           0 :         if (tmpkey == NULL)
    1939           0 :             return NULL;
    1940           0 :         rv = set_discard_key(so, tmpkey);
    1941           0 :         Py_DECREF(tmpkey);
    1942           0 :         if (rv == -1)
    1943           0 :             return NULL;
    1944             :     }
    1945           6 :     Py_RETURN_NONE;
    1946             : }
    1947             : 
    1948             : PyDoc_STRVAR(discard_doc,
    1949             : "Remove an element from a set if it is a member.\n\
    1950             : \n\
    1951             : If the element is not a member, do nothing.");
    1952             : 
    1953             : static PyObject *
    1954           0 : set_reduce(PySetObject *so)
    1955             : {
    1956           0 :     PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;
    1957             : 
    1958           0 :     keys = PySequence_List((PyObject *)so);
    1959           0 :     if (keys == NULL)
    1960           0 :         goto done;
    1961           0 :     args = PyTuple_Pack(1, keys);
    1962           0 :     if (args == NULL)
    1963           0 :         goto done;
    1964           0 :     dict = PyObject_GetAttrString((PyObject *)so, "__dict__");
    1965           0 :     if (dict == NULL) {
    1966           0 :         PyErr_Clear();
    1967           0 :         dict = Py_None;
    1968           0 :         Py_INCREF(dict);
    1969             :     }
    1970           0 :     result = PyTuple_Pack(3, Py_TYPE(so), args, dict);
    1971             : done:
    1972           0 :     Py_XDECREF(args);
    1973           0 :     Py_XDECREF(keys);
    1974           0 :     Py_XDECREF(dict);
    1975           0 :     return result;
    1976             : }
    1977             : 
    1978             : PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
    1979             : 
    1980             : static PyObject *
    1981           0 : set_sizeof(PySetObject *so)
    1982             : {
    1983             :     Py_ssize_t res;
    1984             : 
    1985           0 :     res = _PyObject_SIZE(Py_TYPE(so));
    1986           0 :     if (so->table != so->smalltable)
    1987           0 :         res = res + (so->mask + 1) * sizeof(setentry);
    1988           0 :     return PyInt_FromSsize_t(res);
    1989             : }
    1990             : 
    1991             : PyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes");
    1992             : static int
    1993         636 : set_init(PySetObject *self, PyObject *args, PyObject *kwds)
    1994             : {
    1995         636 :     PyObject *iterable = NULL;
    1996             : 
    1997         636 :     if (!PyAnySet_Check(self))
    1998           0 :         return -1;
    1999         636 :     if (PySet_Check(self) && !_PyArg_NoKeywords("set()", kwds))
    2000           0 :         return -1;
    2001         636 :     if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable))
    2002           0 :         return -1;
    2003         636 :     set_clear_internal(self);
    2004         636 :     self->hash = -1;
    2005         636 :     if (iterable == NULL)
    2006         534 :         return 0;
    2007         102 :     return set_update_internal(self, iterable);
    2008             : }
    2009             : 
    2010             : static PySequenceMethods set_as_sequence = {
    2011             :     set_len,                            /* sq_length */
    2012             :     0,                                  /* sq_concat */
    2013             :     0,                                  /* sq_repeat */
    2014             :     0,                                  /* sq_item */
    2015             :     0,                                  /* sq_slice */
    2016             :     0,                                  /* sq_ass_item */
    2017             :     0,                                  /* sq_ass_slice */
    2018             :     (objobjproc)set_contains,           /* sq_contains */
    2019             : };
    2020             : 
    2021             : /* set object ********************************************************/
    2022             : 
    2023             : #ifdef Py_DEBUG
    2024             : static PyObject *test_c_api(PySetObject *so);
    2025             : 
    2026             : PyDoc_STRVAR(test_c_api_doc, "Exercises C API.  Returns True.\n\
    2027             : All is well if assertions don't fail.");
    2028             : #endif
    2029             : 
    2030             : static PyMethodDef set_methods[] = {
    2031             :     {"add",             (PyCFunction)set_add,           METH_O,
    2032             :      add_doc},
    2033             :     {"clear",           (PyCFunction)set_clear,         METH_NOARGS,
    2034             :      clear_doc},
    2035             :     {"__contains__",(PyCFunction)set_direct_contains,           METH_O | METH_COEXIST,
    2036             :      contains_doc},
    2037             :     {"copy",            (PyCFunction)set_copy,          METH_NOARGS,
    2038             :      copy_doc},
    2039             :     {"discard",         (PyCFunction)set_discard,       METH_O,
    2040             :      discard_doc},
    2041             :     {"difference",      (PyCFunction)set_difference_multi,      METH_VARARGS,
    2042             :      difference_doc},
    2043             :     {"difference_update",       (PyCFunction)set_difference_update,     METH_VARARGS,
    2044             :      difference_update_doc},
    2045             :     {"intersection",(PyCFunction)set_intersection_multi,        METH_VARARGS,
    2046             :      intersection_doc},
    2047             :     {"intersection_update",(PyCFunction)set_intersection_update_multi,          METH_VARARGS,
    2048             :      intersection_update_doc},
    2049             :     {"isdisjoint",      (PyCFunction)set_isdisjoint,    METH_O,
    2050             :      isdisjoint_doc},
    2051             :     {"issubset",        (PyCFunction)set_issubset,      METH_O,
    2052             :      issubset_doc},
    2053             :     {"issuperset",      (PyCFunction)set_issuperset,    METH_O,
    2054             :      issuperset_doc},
    2055             :     {"pop",             (PyCFunction)set_pop,           METH_NOARGS,
    2056             :      pop_doc},
    2057             :     {"__reduce__",      (PyCFunction)set_reduce,        METH_NOARGS,
    2058             :      reduce_doc},
    2059             :     {"remove",          (PyCFunction)set_remove,        METH_O,
    2060             :      remove_doc},
    2061             :     {"__sizeof__",      (PyCFunction)set_sizeof,        METH_NOARGS,
    2062             :      sizeof_doc},
    2063             :     {"symmetric_difference",(PyCFunction)set_symmetric_difference,      METH_O,
    2064             :      symmetric_difference_doc},
    2065             :     {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update,        METH_O,
    2066             :      symmetric_difference_update_doc},
    2067             : #ifdef Py_DEBUG
    2068             :     {"test_c_api",      (PyCFunction)test_c_api,        METH_NOARGS,
    2069             :      test_c_api_doc},
    2070             : #endif
    2071             :     {"union",           (PyCFunction)set_union,         METH_VARARGS,
    2072             :      union_doc},
    2073             :     {"update",          (PyCFunction)set_update,        METH_VARARGS,
    2074             :      update_doc},
    2075             :     {NULL,              NULL}   /* sentinel */
    2076             : };
    2077             : 
    2078             : static PyNumberMethods set_as_number = {
    2079             :     0,                                  /*nb_add*/
    2080             :     (binaryfunc)set_sub,                /*nb_subtract*/
    2081             :     0,                                  /*nb_multiply*/
    2082             :     0,                                  /*nb_divide*/
    2083             :     0,                                  /*nb_remainder*/
    2084             :     0,                                  /*nb_divmod*/
    2085             :     0,                                  /*nb_power*/
    2086             :     0,                                  /*nb_negative*/
    2087             :     0,                                  /*nb_positive*/
    2088             :     0,                                  /*nb_absolute*/
    2089             :     0,                                  /*nb_nonzero*/
    2090             :     0,                                  /*nb_invert*/
    2091             :     0,                                  /*nb_lshift*/
    2092             :     0,                                  /*nb_rshift*/
    2093             :     (binaryfunc)set_and,                /*nb_and*/
    2094             :     (binaryfunc)set_xor,                /*nb_xor*/
    2095             :     (binaryfunc)set_or,                 /*nb_or*/
    2096             :     0,                                  /*nb_coerce*/
    2097             :     0,                                  /*nb_int*/
    2098             :     0,                                  /*nb_long*/
    2099             :     0,                                  /*nb_float*/
    2100             :     0,                                  /*nb_oct*/
    2101             :     0,                                  /*nb_hex*/
    2102             :     0,                                  /*nb_inplace_add*/
    2103             :     (binaryfunc)set_isub,               /*nb_inplace_subtract*/
    2104             :     0,                                  /*nb_inplace_multiply*/
    2105             :     0,                                  /*nb_inplace_divide*/
    2106             :     0,                                  /*nb_inplace_remainder*/
    2107             :     0,                                  /*nb_inplace_power*/
    2108             :     0,                                  /*nb_inplace_lshift*/
    2109             :     0,                                  /*nb_inplace_rshift*/
    2110             :     (binaryfunc)set_iand,               /*nb_inplace_and*/
    2111             :     (binaryfunc)set_ixor,               /*nb_inplace_xor*/
    2112             :     (binaryfunc)set_ior,                /*nb_inplace_or*/
    2113             : };
    2114             : 
    2115             : PyDoc_STRVAR(set_doc,
    2116             : "set() -> new empty set object\n\
    2117             : set(iterable) -> new set object\n\
    2118             : \n\
    2119             : Build an unordered collection of unique elements.");
    2120             : 
    2121             : PyTypeObject PySet_Type = {
    2122             :     PyVarObject_HEAD_INIT(&PyType_Type, 0)
    2123             :     "set",                              /* tp_name */
    2124             :     sizeof(PySetObject),                /* tp_basicsize */
    2125             :     0,                                  /* tp_itemsize */
    2126             :     /* methods */
    2127             :     (destructor)set_dealloc,            /* tp_dealloc */
    2128             :     (printfunc)set_tp_print,            /* tp_print */
    2129             :     0,                                  /* tp_getattr */
    2130             :     0,                                  /* tp_setattr */
    2131             :     set_nocmp,                          /* tp_compare */
    2132             :     (reprfunc)set_repr,                 /* tp_repr */
    2133             :     &set_as_number,                     /* tp_as_number */
    2134             :     &set_as_sequence,                   /* tp_as_sequence */
    2135             :     0,                                  /* tp_as_mapping */
    2136             :     (hashfunc)PyObject_HashNotImplemented,      /* tp_hash */
    2137             :     0,                                  /* tp_call */
    2138             :     0,                                  /* tp_str */
    2139             :     PyObject_GenericGetAttr,            /* tp_getattro */
    2140             :     0,                                  /* tp_setattro */
    2141             :     0,                                  /* tp_as_buffer */
    2142             :     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_CHECKTYPES |
    2143             :         Py_TPFLAGS_BASETYPE,            /* tp_flags */
    2144             :     set_doc,                            /* tp_doc */
    2145             :     (traverseproc)set_traverse,         /* tp_traverse */
    2146             :     (inquiry)set_clear_internal,        /* tp_clear */
    2147             :     (richcmpfunc)set_richcompare,       /* tp_richcompare */
    2148             :     offsetof(PySetObject, weakreflist),         /* tp_weaklistoffset */
    2149             :     (getiterfunc)set_iter,      /* tp_iter */
    2150             :     0,                                  /* tp_iternext */
    2151             :     set_methods,                        /* tp_methods */
    2152             :     0,                                  /* tp_members */
    2153             :     0,                                  /* tp_getset */
    2154             :     0,                                  /* tp_base */
    2155             :     0,                                  /* tp_dict */
    2156             :     0,                                  /* tp_descr_get */
    2157             :     0,                                  /* tp_descr_set */
    2158             :     0,                                  /* tp_dictoffset */
    2159             :     (initproc)set_init,                 /* tp_init */
    2160             :     PyType_GenericAlloc,                /* tp_alloc */
    2161             :     set_new,                            /* tp_new */
    2162             :     PyObject_GC_Del,                    /* tp_free */
    2163             : };
    2164             : 
    2165             : /* frozenset object ********************************************************/
    2166             : 
    2167             : 
    2168             : static PyMethodDef frozenset_methods[] = {
    2169             :     {"__contains__",(PyCFunction)set_direct_contains,           METH_O | METH_COEXIST,
    2170             :      contains_doc},
    2171             :     {"copy",            (PyCFunction)frozenset_copy,    METH_NOARGS,
    2172             :      copy_doc},
    2173             :     {"difference",      (PyCFunction)set_difference_multi,      METH_VARARGS,
    2174             :      difference_doc},
    2175             :     {"intersection",(PyCFunction)set_intersection_multi,        METH_VARARGS,
    2176             :      intersection_doc},
    2177             :     {"isdisjoint",      (PyCFunction)set_isdisjoint,    METH_O,
    2178             :      isdisjoint_doc},
    2179             :     {"issubset",        (PyCFunction)set_issubset,      METH_O,
    2180             :      issubset_doc},
    2181             :     {"issuperset",      (PyCFunction)set_issuperset,    METH_O,
    2182             :      issuperset_doc},
    2183             :     {"__reduce__",      (PyCFunction)set_reduce,        METH_NOARGS,
    2184             :      reduce_doc},
    2185             :     {"__sizeof__",      (PyCFunction)set_sizeof,        METH_NOARGS,
    2186             :      sizeof_doc},
    2187             :     {"symmetric_difference",(PyCFunction)set_symmetric_difference,      METH_O,
    2188             :      symmetric_difference_doc},
    2189             :     {"union",           (PyCFunction)set_union,         METH_VARARGS,
    2190             :      union_doc},
    2191             :     {NULL,              NULL}   /* sentinel */
    2192             : };
    2193             : 
    2194             : static PyNumberMethods frozenset_as_number = {
    2195             :     0,                                  /*nb_add*/
    2196             :     (binaryfunc)set_sub,                /*nb_subtract*/
    2197             :     0,                                  /*nb_multiply*/
    2198             :     0,                                  /*nb_divide*/
    2199             :     0,                                  /*nb_remainder*/
    2200             :     0,                                  /*nb_divmod*/
    2201             :     0,                                  /*nb_power*/
    2202             :     0,                                  /*nb_negative*/
    2203             :     0,                                  /*nb_positive*/
    2204             :     0,                                  /*nb_absolute*/
    2205             :     0,                                  /*nb_nonzero*/
    2206             :     0,                                  /*nb_invert*/
    2207             :     0,                                  /*nb_lshift*/
    2208             :     0,                                  /*nb_rshift*/
    2209             :     (binaryfunc)set_and,                /*nb_and*/
    2210             :     (binaryfunc)set_xor,                /*nb_xor*/
    2211             :     (binaryfunc)set_or,                 /*nb_or*/
    2212             : };
    2213             : 
    2214             : PyDoc_STRVAR(frozenset_doc,
    2215             : "frozenset() -> empty frozenset object\n\
    2216             : frozenset(iterable) -> frozenset object\n\
    2217             : \n\
    2218             : Build an immutable unordered collection of unique elements.");
    2219             : 
    2220             : PyTypeObject PyFrozenSet_Type = {
    2221             :     PyVarObject_HEAD_INIT(&PyType_Type, 0)
    2222             :     "frozenset",                        /* tp_name */
    2223             :     sizeof(PySetObject),                /* tp_basicsize */
    2224             :     0,                                  /* tp_itemsize */
    2225             :     /* methods */
    2226             :     (destructor)set_dealloc,            /* tp_dealloc */
    2227             :     (printfunc)set_tp_print,            /* tp_print */
    2228             :     0,                                  /* tp_getattr */
    2229             :     0,                                  /* tp_setattr */
    2230             :     set_nocmp,                          /* tp_compare */
    2231             :     (reprfunc)set_repr,                 /* tp_repr */
    2232             :     &frozenset_as_number,               /* tp_as_number */
    2233             :     &set_as_sequence,                   /* tp_as_sequence */
    2234             :     0,                                  /* tp_as_mapping */
    2235             :     frozenset_hash,                     /* tp_hash */
    2236             :     0,                                  /* tp_call */
    2237             :     0,                                  /* tp_str */
    2238             :     PyObject_GenericGetAttr,            /* tp_getattro */
    2239             :     0,                                  /* tp_setattro */
    2240             :     0,                                  /* tp_as_buffer */
    2241             :     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_CHECKTYPES |
    2242             :         Py_TPFLAGS_BASETYPE,            /* tp_flags */
    2243             :     frozenset_doc,                      /* tp_doc */
    2244             :     (traverseproc)set_traverse,         /* tp_traverse */
    2245             :     (inquiry)set_clear_internal,        /* tp_clear */
    2246             :     (richcmpfunc)set_richcompare,       /* tp_richcompare */
    2247             :     offsetof(PySetObject, weakreflist),         /* tp_weaklistoffset */
    2248             :     (getiterfunc)set_iter,              /* tp_iter */
    2249             :     0,                                  /* tp_iternext */
    2250             :     frozenset_methods,                  /* tp_methods */
    2251             :     0,                                  /* tp_members */
    2252             :     0,                                  /* tp_getset */
    2253             :     0,                                  /* tp_base */
    2254             :     0,                                  /* tp_dict */
    2255             :     0,                                  /* tp_descr_get */
    2256             :     0,                                  /* tp_descr_set */
    2257             :     0,                                  /* tp_dictoffset */
    2258             :     0,                                  /* tp_init */
    2259             :     PyType_GenericAlloc,                /* tp_alloc */
    2260             :     frozenset_new,                      /* tp_new */
    2261             :     PyObject_GC_Del,                    /* tp_free */
    2262             : };
    2263             : 
    2264             : 
    2265             : /***** C API functions *************************************************/
    2266             : 
    2267             : PyObject *
    2268           3 : PySet_New(PyObject *iterable)
    2269             : {
    2270           3 :     return make_new_set(&PySet_Type, iterable);
    2271             : }
    2272             : 
    2273             : PyObject *
    2274           3 : PyFrozenSet_New(PyObject *iterable)
    2275             : {
    2276           3 :     return make_new_set(&PyFrozenSet_Type, iterable);
    2277             : }
    2278             : 
    2279             : Py_ssize_t
    2280           0 : PySet_Size(PyObject *anyset)
    2281             : {
    2282           0 :     if (!PyAnySet_Check(anyset)) {
    2283           0 :         PyErr_BadInternalCall();
    2284           0 :         return -1;
    2285             :     }
    2286           0 :     return PySet_GET_SIZE(anyset);
    2287             : }
    2288             : 
    2289             : int
    2290           0 : PySet_Clear(PyObject *set)
    2291             : {
    2292           0 :     if (!PySet_Check(set)) {
    2293           0 :         PyErr_BadInternalCall();
    2294           0 :         return -1;
    2295             :     }
    2296           0 :     return set_clear_internal((PySetObject *)set);
    2297             : }
    2298             : 
    2299             : int
    2300           0 : PySet_Contains(PyObject *anyset, PyObject *key)
    2301             : {
    2302           0 :     if (!PyAnySet_Check(anyset)) {
    2303           0 :         PyErr_BadInternalCall();
    2304           0 :         return -1;
    2305             :     }
    2306           0 :     return set_contains_key((PySetObject *)anyset, key);
    2307             : }
    2308             : 
    2309             : int
    2310           0 : PySet_Discard(PyObject *set, PyObject *key)
    2311             : {
    2312           0 :     if (!PySet_Check(set)) {
    2313           0 :         PyErr_BadInternalCall();
    2314           0 :         return -1;
    2315             :     }
    2316           0 :     return set_discard_key((PySetObject *)set, key);
    2317             : }
    2318             : 
    2319             : int
    2320          81 : PySet_Add(PyObject *anyset, PyObject *key)
    2321             : {
    2322         153 :     if (!PySet_Check(anyset) &&
    2323          72 :         (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
    2324           0 :         PyErr_BadInternalCall();
    2325           0 :         return -1;
    2326             :     }
    2327          81 :     return set_add_key((PySetObject *)anyset, key);
    2328             : }
    2329             : 
    2330             : int
    2331           0 : _PySet_Next(PyObject *set, Py_ssize_t *pos, PyObject **key)
    2332             : {
    2333             :     setentry *entry_ptr;
    2334             : 
    2335           0 :     if (!PyAnySet_Check(set)) {
    2336           0 :         PyErr_BadInternalCall();
    2337           0 :         return -1;
    2338             :     }
    2339           0 :     if (set_next((PySetObject *)set, pos, &entry_ptr) == 0)
    2340           0 :         return 0;
    2341           0 :     *key = entry_ptr->key;
    2342           0 :     return 1;
    2343             : }
    2344             : 
    2345             : int
    2346           0 : _PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, long *hash)
    2347             : {
    2348             :     setentry *entry;
    2349             : 
    2350           0 :     if (!PyAnySet_Check(set)) {
    2351           0 :         PyErr_BadInternalCall();
    2352           0 :         return -1;
    2353             :     }
    2354           0 :     if (set_next((PySetObject *)set, pos, &entry) == 0)
    2355           0 :         return 0;
    2356           0 :     *key = entry->key;
    2357           0 :     *hash = entry->hash;
    2358           0 :     return 1;
    2359             : }
    2360             : 
    2361             : PyObject *
    2362           0 : PySet_Pop(PyObject *set)
    2363             : {
    2364           0 :     if (!PySet_Check(set)) {
    2365           0 :         PyErr_BadInternalCall();
    2366           0 :         return NULL;
    2367             :     }
    2368           0 :     return set_pop((PySetObject *)set);
    2369             : }
    2370             : 
    2371             : int
    2372           0 : _PySet_Update(PyObject *set, PyObject *iterable)
    2373             : {
    2374           0 :     if (!PySet_Check(set)) {
    2375           0 :         PyErr_BadInternalCall();
    2376           0 :         return -1;
    2377             :     }
    2378           0 :     return set_update_internal((PySetObject *)set, iterable);
    2379             : }
    2380             : 
    2381             : #ifdef Py_DEBUG
    2382             : 
    2383             : /* Test code to be called with any three element set.
    2384             :    Returns True and original set is restored. */
    2385             : 
    2386             : #define assertRaises(call_return_value, exception)              \
    2387             :     do {                                                        \
    2388             :         assert(call_return_value);                              \
    2389             :         assert(PyErr_ExceptionMatches(exception));              \
    2390             :         PyErr_Clear();                                          \
    2391             :     } while(0)
    2392             : 
    2393             : static PyObject *
    2394             : test_c_api(PySetObject *so)
    2395             : {
    2396             :     Py_ssize_t count;
    2397             :     char *s;
    2398             :     Py_ssize_t i;
    2399             :     PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x;
    2400             :     PyObject *ob = (PyObject *)so;
    2401             :     PyObject *str;
    2402             : 
    2403             :     /* Verify preconditions */
    2404             :     assert(PyAnySet_Check(ob));
    2405             :     assert(PyAnySet_CheckExact(ob));
    2406             :     assert(!PyFrozenSet_CheckExact(ob));
    2407             : 
    2408             :     /* so.clear(); so |= set("abc"); */
    2409             :     str = PyString_FromString("abc");
    2410             :     if (str == NULL)
    2411             :         return NULL;
    2412             :     set_clear_internal(so);
    2413             :     if (set_update_internal(so, str) == -1) {
    2414             :         Py_DECREF(str);
    2415             :         return NULL;
    2416             :     }
    2417             :     Py_DECREF(str);
    2418             : 
    2419             :     /* Exercise type/size checks */
    2420             :     assert(PySet_Size(ob) == 3);
    2421             :     assert(PySet_GET_SIZE(ob) == 3);
    2422             : 
    2423             :     /* Raise TypeError for non-iterable constructor arguments */
    2424             :     assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
    2425             :     assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);
    2426             : 
    2427             :     /* Raise TypeError for unhashable key */
    2428             :     dup = PySet_New(ob);
    2429             :     assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
    2430             :     assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
    2431             :     assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);
    2432             : 
    2433             :     /* Exercise successful pop, contains, add, and discard */
    2434             :     elem = PySet_Pop(ob);
    2435             :     assert(PySet_Contains(ob, elem) == 0);
    2436             :     assert(PySet_GET_SIZE(ob) == 2);
    2437             :     assert(PySet_Add(ob, elem) == 0);
    2438             :     assert(PySet_Contains(ob, elem) == 1);
    2439             :     assert(PySet_GET_SIZE(ob) == 3);
    2440             :     assert(PySet_Discard(ob, elem) == 1);
    2441             :     assert(PySet_GET_SIZE(ob) == 2);
    2442             :     assert(PySet_Discard(ob, elem) == 0);
    2443             :     assert(PySet_GET_SIZE(ob) == 2);
    2444             : 
    2445             :     /* Exercise clear */
    2446             :     dup2 = PySet_New(dup);
    2447             :     assert(PySet_Clear(dup2) == 0);
    2448             :     assert(PySet_Size(dup2) == 0);
    2449             :     Py_DECREF(dup2);
    2450             : 
    2451             :     /* Raise SystemError on clear or update of frozen set */
    2452             :     f = PyFrozenSet_New(dup);
    2453             :     assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
    2454             :     assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
    2455             :     assert(PySet_Add(f, elem) == 0);
    2456             :     Py_INCREF(f);
    2457             :     assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
    2458             :     Py_DECREF(f);
    2459             :     Py_DECREF(f);
    2460             : 
    2461             :     /* Exercise direct iteration */
    2462             :     i = 0, count = 0;
    2463             :     while (_PySet_Next((PyObject *)dup, &i, &x)) {
    2464             :         s = PyString_AsString(x);
    2465             :         assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
    2466             :         count++;
    2467             :     }
    2468             :     assert(count == 3);
    2469             : 
    2470             :     /* Exercise updates */
    2471             :     dup2 = PySet_New(NULL);
    2472             :     assert(_PySet_Update(dup2, dup) == 0);
    2473             :     assert(PySet_Size(dup2) == 3);
    2474             :     assert(_PySet_Update(dup2, dup) == 0);
    2475             :     assert(PySet_Size(dup2) == 3);
    2476             :     Py_DECREF(dup2);
    2477             : 
    2478             :     /* Raise SystemError when self argument is not a set or frozenset. */
    2479             :     t = PyTuple_New(0);
    2480             :     assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
    2481             :     assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
    2482             :     Py_DECREF(t);
    2483             : 
    2484             :     /* Raise SystemError when self argument is not a set. */
    2485             :     f = PyFrozenSet_New(dup);
    2486             :     assert(PySet_Size(f) == 3);
    2487             :     assert(PyFrozenSet_CheckExact(f));
    2488             :     assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
    2489             :     assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
    2490             :     Py_DECREF(f);
    2491             : 
    2492             :     /* Raise KeyError when popping from an empty set */
    2493             :     assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
    2494             :     Py_DECREF(ob);
    2495             :     assert(PySet_GET_SIZE(ob) == 0);
    2496             :     assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);
    2497             : 
    2498             :     /* Restore the set from the copy using the PyNumber API */
    2499             :     assert(PyNumber_InPlaceOr(ob, dup) == ob);
    2500             :     Py_DECREF(ob);
    2501             : 
    2502             :     /* Verify constructors accept NULL arguments */
    2503             :     f = PySet_New(NULL);
    2504             :     assert(f != NULL);
    2505             :     assert(PySet_GET_SIZE(f) == 0);
    2506             :     Py_DECREF(f);
    2507             :     f = PyFrozenSet_New(NULL);
    2508             :     assert(f != NULL);
    2509             :     assert(PyFrozenSet_CheckExact(f));
    2510             :     assert(PySet_GET_SIZE(f) == 0);
    2511             :     Py_DECREF(f);
    2512             : 
    2513             :     Py_DECREF(elem);
    2514             :     Py_DECREF(dup);
    2515             :     Py_RETURN_TRUE;
    2516             : }
    2517             : 
    2518             : #undef assertRaises
    2519             : 
    2520             : #endif

Generated by: LCOV version 1.10