[mirror_edk2.git] / AppPkg / Applications / Python / Python-2.7.10 / Objects / setobject.c

\r
/* set object implementation\r
   Written and maintained by Raymond D. Hettinger <python@rcn.com>\r
   Derived from Lib/sets.py and Objects/dictobject.c.\r
\r
   Copyright (c) 2003-2007 Python Software Foundation.\r
   All rights reserved.\r
*/\r
\r
#include "Python.h"\r
#include "structmember.h"\r
\r
/* Set a key error with the specified argument, wrapping it in a\r
 * tuple automatically so that tuple keys are not unpacked as the\r
 * exception arguments. */\r
static void\r
set_key_error(PyObject *arg)\r
{\r
    PyObject *tup;\r
    tup = PyTuple_Pack(1, arg);\r
    if (!tup)\r
        return; /* caller will expect error to be set anyway */\r
    PyErr_SetObject(PyExc_KeyError, tup);\r
    Py_DECREF(tup);\r
}\r
\r
/* This must be >= 1. */\r
#define PERTURB_SHIFT 5\r
\r
/* Object used as dummy key to fill deleted entries */\r
static PyObject *dummy = NULL; /* Initialized by first call to make_new_set() */\r
\r
#ifdef Py_REF_DEBUG\r
PyObject *\r
_PySet_Dummy(void)\r
{\r
    return dummy;\r
}\r
#endif\r
\r
#define INIT_NONZERO_SET_SLOTS(so) do {                         \\r
    (so)->table = (so)->smalltable;                             \\r
    (so)->mask = PySet_MINSIZE - 1;                             \\r
    (so)->hash = -1;                                            \\r
    } while(0)\r
\r
#define EMPTY_TO_MINSIZE(so) do {                               \\r
    memset((so)->smalltable, 0, sizeof((so)->smalltable));      \\r
    (so)->used = (so)->fill = 0;                                \\r
    INIT_NONZERO_SET_SLOTS(so);                                 \\r
    } while(0)\r
\r
/* Reuse scheme to save calls to malloc, free, and memset */\r
#ifndef PySet_MAXFREELIST\r
#define PySet_MAXFREELIST 80\r
#endif\r
static PySetObject *free_list[PySet_MAXFREELIST];\r
static int numfree = 0;\r
\r
/*\r
The basic lookup function used by all operations.\r
This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.\r
Open addressing is preferred over chaining since the link overhead for\r
chaining would be substantial (100% with typical malloc overhead).\r
\r
The initial probe index is computed as hash mod the table size. Subsequent\r
probe indices are computed as explained in Objects/dictobject.c.\r
\r
All arithmetic on hash should ignore overflow.\r
\r
Unlike the dictionary implementation, the lookkey functions can return\r
NULL if the rich comparison returns an error.\r
*/\r
\r
static setentry *\r
set_lookkey(PySetObject *so, PyObject *key, register long hash)\r
{\r
    register Py_ssize_t i;\r
    register size_t perturb;\r
    register setentry *freeslot;\r
    register size_t mask = so->mask;\r
    setentry *table = so->table;\r
    register setentry *entry;\r
    register int cmp;\r
    PyObject *startkey;\r
\r
    i = hash & mask;\r
    entry = &table[i];\r
    if (entry->key == NULL || entry->key == key)\r
        return entry;\r
\r
    if (entry->key == dummy)\r
        freeslot = entry;\r
    else {\r
        if (entry->hash == hash) {\r
            startkey = entry->key;\r
            Py_INCREF(startkey);\r
            cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);\r
            Py_DECREF(startkey);\r
            if (cmp < 0)\r
                return NULL;\r
            if (table == so->table && entry->key == startkey) {\r
                if (cmp > 0)\r
                    return entry;\r
            }\r
            else {\r
                /* The compare did major nasty stuff to the\r
                 * set:  start over.\r
                 */\r
                return set_lookkey(so, key, hash);\r
            }\r
        }\r
        freeslot = NULL;\r
    }\r
\r
    /* In the loop, key == dummy is by far (factor of 100s) the\r
       least likely outcome, so test for that last. */\r
    for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {\r
        i = (i << 2) + i + perturb + 1;\r
        entry = &table[i & mask];\r
        if (entry->key == NULL) {\r
            if (freeslot != NULL)\r
                entry = freeslot;\r
            break;\r
        }\r
        if (entry->key == key)\r
            break;\r
        if (entry->hash == hash && entry->key != dummy) {\r
            startkey = entry->key;\r
            Py_INCREF(startkey);\r
            cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);\r
            Py_DECREF(startkey);\r
            if (cmp < 0)\r
                return NULL;\r
            if (table == so->table && entry->key == startkey) {\r
                if (cmp > 0)\r
                    break;\r
            }\r
            else {\r
                /* The compare did major nasty stuff to the\r
                 * set:  start over.\r
                 */\r
                return set_lookkey(so, key, hash);\r
            }\r
        }\r
        else if (entry->key == dummy && freeslot == NULL)\r
            freeslot = entry;\r
    }\r
    return entry;\r
}\r
\r
/*\r
 * Hacked up version of set_lookkey which can assume keys are always strings;\r
 * This means we can always use _PyString_Eq directly and not have to check to\r
 * see if the comparison altered the table.\r
 */\r
static setentry *\r
set_lookkey_string(PySetObject *so, PyObject *key, register long hash)\r
{\r
    register Py_ssize_t i;\r
    register size_t perturb;\r
    register setentry *freeslot;\r
    register size_t mask = so->mask;\r
    setentry *table = so->table;\r
    register setentry *entry;\r
\r
    /* Make sure this function doesn't have to handle non-string keys,\r
       including subclasses of str; e.g., one reason to subclass\r
       strings is to override __eq__, and for speed we don't cater to\r
       that here. */\r
    if (!PyString_CheckExact(key)) {\r
        so->lookup = set_lookkey;\r
        return set_lookkey(so, key, hash);\r
    }\r
    i = hash & mask;\r
    entry = &table[i];\r
    if (entry->key == NULL || entry->key == key)\r
        return entry;\r
    if (entry->key == dummy)\r
        freeslot = entry;\r
    else {\r
        if (entry->hash == hash && _PyString_Eq(entry->key, key))\r
            return entry;\r
        freeslot = NULL;\r
    }\r
\r
    /* In the loop, key == dummy is by far (factor of 100s) the\r
       least likely outcome, so test for that last. */\r
    for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {\r
        i = (i << 2) + i + perturb + 1;\r
        entry = &table[i & mask];\r
        if (entry->key == NULL)\r
            return freeslot == NULL ? entry : freeslot;\r
        if (entry->key == key\r
            || (entry->hash == hash\r
            && entry->key != dummy\r
            && _PyString_Eq(entry->key, key)))\r
            return entry;\r
        if (entry->key == dummy && freeslot == NULL)\r
            freeslot = entry;\r
    }\r
    assert(0);          /* NOT REACHED */\r
    return 0;\r
}\r
\r
/*\r
Internal routine to insert a new key into the table.\r
Used by the public insert routine.\r
Eats a reference to key.\r
*/\r
static int\r
set_insert_key(register PySetObject *so, PyObject *key, long hash)\r
{\r
    register setentry *entry;\r
\r
    assert(so->lookup != NULL);\r
    entry = so->lookup(so, key, hash);\r
    if (entry == NULL)\r
        return -1;\r
    if (entry->key == NULL) {\r
        /* UNUSED */\r
        so->fill++;\r
        entry->key = key;\r
        entry->hash = hash;\r
        so->used++;\r
    } else if (entry->key == dummy) {\r
        /* DUMMY */\r
        entry->key = key;\r
        entry->hash = hash;\r
        so->used++;\r
        Py_DECREF(dummy);\r
    } else {\r
        /* ACTIVE */\r
        Py_DECREF(key);\r
    }\r
    return 0;\r
}\r
\r
/*\r
Internal routine used by set_table_resize() to insert an item which is\r
known to be absent from the set.  This routine also assumes that\r
the set contains no deleted entries.  Besides the performance benefit,\r
using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).\r
Note that no refcounts are changed by this routine; if needed, the caller\r
is responsible for incref'ing `key`.\r
*/\r
static void\r
set_insert_clean(register PySetObject *so, PyObject *key, long hash)\r
{\r
    register size_t i;\r
    register size_t perturb;\r
    register size_t mask = (size_t)so->mask;\r
    setentry *table = so->table;\r
    register setentry *entry;\r
\r
    i = hash & mask;\r
    entry = &table[i];\r
    for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) {\r
        i = (i << 2) + i + perturb + 1;\r
        entry = &table[i & mask];\r
    }\r
    so->fill++;\r
    entry->key = key;\r
    entry->hash = hash;\r
    so->used++;\r
}\r
\r
/*\r
Restructure the table by allocating a new table and reinserting all\r
keys again.  When entries have been deleted, the new table may\r
actually be smaller than the old one.\r
*/\r
static int\r
set_table_resize(PySetObject *so, Py_ssize_t minused)\r
{\r
    Py_ssize_t newsize;\r
    setentry *oldtable, *newtable, *entry;\r
    Py_ssize_t i;\r
    int is_oldtable_malloced;\r
    setentry small_copy[PySet_MINSIZE];\r
\r
    assert(minused >= 0);\r
\r
    /* Find the smallest table size > minused. */\r
    for (newsize = PySet_MINSIZE;\r
         newsize <= minused && newsize > 0;\r
         newsize <<= 1)\r
        ;\r
    if (newsize <= 0) {\r
        PyErr_NoMemory();\r
        return -1;\r
    }\r
\r
    /* Get space for a new table. */\r
    oldtable = so->table;\r
    assert(oldtable != NULL);\r
    is_oldtable_malloced = oldtable != so->smalltable;\r
\r
    if (newsize == PySet_MINSIZE) {\r
        /* A large table is shrinking, or we can't get any smaller. */\r
        newtable = so->smalltable;\r
        if (newtable == oldtable) {\r
            if (so->fill == so->used) {\r
                /* No dummies, so no point doing anything. */\r
                return 0;\r
            }\r
            /* We're not going to resize it, but rebuild the\r
               table anyway to purge old dummy entries.\r
               Subtle:  This is *necessary* if fill==size,\r
               as set_lookkey needs at least one virgin slot to\r
               terminate failing searches.  If fill < size, it's\r
               merely desirable, as dummies slow searches. */\r
            assert(so->fill > so->used);\r
            memcpy(small_copy, oldtable, sizeof(small_copy));\r
            oldtable = small_copy;\r
        }\r
    }\r
    else {\r
        newtable = PyMem_NEW(setentry, newsize);\r
        if (newtable == NULL) {\r
            PyErr_NoMemory();\r
            return -1;\r
        }\r
    }\r
\r
    /* Make the set empty, using the new table. */\r
    assert(newtable != oldtable);\r
    so->table = newtable;\r
    so->mask = newsize - 1;\r
    memset(newtable, 0, sizeof(setentry) * newsize);\r
    so->used = 0;\r
    i = so->fill;\r
    so->fill = 0;\r
\r
    /* Copy the data over; this is refcount-neutral for active entries;\r
       dummy entries aren't copied over, of course */\r
    for (entry = oldtable; i > 0; entry++) {\r
        if (entry->key == NULL) {\r
            /* UNUSED */\r
            ;\r
        } else if (entry->key == dummy) {\r
            /* DUMMY */\r
            --i;\r
            assert(entry->key == dummy);\r
            Py_DECREF(entry->key);\r
        } else {\r
            /* ACTIVE */\r
            --i;\r
            set_insert_clean(so, entry->key, entry->hash);\r
        }\r
    }\r
\r
    if (is_oldtable_malloced)\r
        PyMem_DEL(oldtable);\r
    return 0;\r
}\r
\r
/* CAUTION: set_add_key/entry() must guarantee it won't resize the table */\r
\r
static int\r
set_add_entry(register PySetObject *so, setentry *entry)\r
{\r
    register Py_ssize_t n_used;\r
    PyObject *key = entry->key;\r
    long hash = entry->hash;\r
\r
    assert(so->fill <= so->mask);  /* at least one empty slot */\r
    n_used = so->used;\r
    Py_INCREF(key);\r
    if (set_insert_key(so, key, hash) == -1) {\r
        Py_DECREF(key);\r
        return -1;\r
    }\r
    if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))\r
        return 0;\r
    return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);\r
}\r
\r
static int\r
set_add_key(register PySetObject *so, PyObject *key)\r
{\r
    register long hash;\r
    register Py_ssize_t n_used;\r
\r
    if (!PyString_CheckExact(key) ||\r
        (hash = ((PyStringObject *) key)->ob_shash) == -1) {\r
        hash = PyObject_Hash(key);\r
        if (hash == -1)\r
            return -1;\r
    }\r
    assert(so->fill <= so->mask);  /* at least one empty slot */\r
    n_used = so->used;\r
    Py_INCREF(key);\r
    if (set_insert_key(so, key, hash) == -1) {\r
        Py_DECREF(key);\r
        return -1;\r
    }\r
    if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))\r
        return 0;\r
    return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);\r
}\r
\r
#define DISCARD_NOTFOUND 0\r
#define DISCARD_FOUND 1\r
\r
static int\r
set_discard_entry(PySetObject *so, setentry *oldentry)\r
{       register setentry *entry;\r
    PyObject *old_key;\r
\r
    entry = (so->lookup)(so, oldentry->key, oldentry->hash);\r
    if (entry == NULL)\r
        return -1;\r
    if (entry->key == NULL  ||  entry->key == dummy)\r
        return DISCARD_NOTFOUND;\r
    old_key = entry->key;\r
    Py_INCREF(dummy);\r
    entry->key = dummy;\r
    so->used--;\r
    Py_DECREF(old_key);\r
    return DISCARD_FOUND;\r
}\r
\r
static int\r
set_discard_key(PySetObject *so, PyObject *key)\r
{\r
    register long hash;\r
    register setentry *entry;\r
    PyObject *old_key;\r
\r
    assert (PyAnySet_Check(so));\r
    if (!PyString_CheckExact(key) ||\r
        (hash = ((PyStringObject *) key)->ob_shash) == -1) {\r
        hash = PyObject_Hash(key);\r
        if (hash == -1)\r
            return -1;\r
    }\r
    entry = (so->lookup)(so, key, hash);\r
    if (entry == NULL)\r
        return -1;\r
    if (entry->key == NULL  ||  entry->key == dummy)\r
        return DISCARD_NOTFOUND;\r
    old_key = entry->key;\r
    Py_INCREF(dummy);\r
    entry->key = dummy;\r
    so->used--;\r
    Py_DECREF(old_key);\r
    return DISCARD_FOUND;\r
}\r
\r
static int\r
set_clear_internal(PySetObject *so)\r
{\r
    setentry *entry, *table;\r
    int table_is_malloced;\r
    Py_ssize_t fill;\r
    setentry small_copy[PySet_MINSIZE];\r
#ifdef Py_DEBUG\r
    Py_ssize_t i, n;\r
    assert (PyAnySet_Check(so));\r
\r
    n = so->mask + 1;\r
    i = 0;\r
#endif\r
\r
    table = so->table;\r
    assert(table != NULL);\r
    table_is_malloced = table != so->smalltable;\r
\r
    /* This is delicate.  During the process of clearing the set,\r
     * decrefs can cause the set to mutate.  To avoid fatal confusion\r
     * (voice of experience), we have to make the set empty before\r
     * clearing the slots, and never refer to anything via so->ref while\r
     * clearing.\r
     */\r
    fill = so->fill;\r
    if (table_is_malloced)\r
        EMPTY_TO_MINSIZE(so);\r
\r
    else if (fill > 0) {\r
        /* It's a small table with something that needs to be cleared.\r
         * Afraid the only safe way is to copy the set entries into\r
         * another small table first.\r
         */\r
        memcpy(small_copy, table, sizeof(small_copy));\r
        table = small_copy;\r
        EMPTY_TO_MINSIZE(so);\r
    }\r
    /* else it's a small table that's already empty */\r
\r
    /* Now we can finally clear things.  If C had refcounts, we could\r
     * assert that the refcount on table is 1 now, i.e. that this function\r
     * has unique access to it, so decref side-effects can't alter it.\r
     */\r
    for (entry = table; fill > 0; ++entry) {\r
#ifdef Py_DEBUG\r
        assert(i < n);\r
        ++i;\r
#endif\r
        if (entry->key) {\r
            --fill;\r
            Py_DECREF(entry->key);\r
        }\r
#ifdef Py_DEBUG\r
        else\r
            assert(entry->key == NULL);\r
#endif\r
    }\r
\r
    if (table_is_malloced)\r
        PyMem_DEL(table);\r
    return 0;\r
}\r
\r
/*\r
 * Iterate over a set table.  Use like so:\r
 *\r
 *     Py_ssize_t pos;\r
 *     setentry *entry;\r
 *     pos = 0;   # important!  pos should not otherwise be changed by you\r
 *     while (set_next(yourset, &pos, &entry)) {\r
 *              Refer to borrowed reference in entry->key.\r
 *     }\r
 *\r
 * CAUTION:  In general, it isn't safe to use set_next in a loop that\r
 * mutates the table.\r
 */\r
static int\r
set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)\r
{\r
    Py_ssize_t i;\r
    Py_ssize_t mask;\r
    register setentry *table;\r
\r
    assert (PyAnySet_Check(so));\r
    i = *pos_ptr;\r
    assert(i >= 0);\r
    table = so->table;\r
    mask = so->mask;\r
    while (i <= mask && (table[i].key == NULL || table[i].key == dummy))\r
        i++;\r
    *pos_ptr = i+1;\r
    if (i > mask)\r
        return 0;\r
    assert(table[i].key != NULL);\r
    *entry_ptr = &table[i];\r
    return 1;\r
}\r
\r
static void\r
set_dealloc(PySetObject *so)\r
{\r
    register setentry *entry;\r
    Py_ssize_t fill = so->fill;\r
    PyObject_GC_UnTrack(so);\r
    Py_TRASHCAN_SAFE_BEGIN(so)\r
    if (so->weakreflist != NULL)\r
        PyObject_ClearWeakRefs((PyObject *) so);\r
\r
    for (entry = so->table; fill > 0; entry++) {\r
        if (entry->key) {\r
            --fill;\r
            Py_DECREF(entry->key);\r
        }\r
    }\r
    if (so->table != so->smalltable)\r
        PyMem_DEL(so->table);\r
    if (numfree < PySet_MAXFREELIST && PyAnySet_CheckExact(so))\r
        free_list[numfree++] = so;\r
    else\r
        Py_TYPE(so)->tp_free(so);\r
    Py_TRASHCAN_SAFE_END(so)\r
}\r
\r
static int\r
set_tp_print(PySetObject *so, FILE *fp, int flags)\r
{\r
    setentry *entry;\r
    Py_ssize_t pos=0;\r
    char *emit = "";            /* No separator emitted on first pass */\r
    char *separator = ", ";\r
    int status = Py_ReprEnter((PyObject*)so);\r
\r
    if (status != 0) {\r
        if (status < 0)\r
            return status;\r
        Py_BEGIN_ALLOW_THREADS\r
        fprintf(fp, "%s(...)", so->ob_type->tp_name);\r
        Py_END_ALLOW_THREADS\r
        return 0;\r
    }\r
\r
    Py_BEGIN_ALLOW_THREADS\r
    fprintf(fp, "%s([", so->ob_type->tp_name);\r
    Py_END_ALLOW_THREADS\r
    while (set_next(so, &pos, &entry)) {\r
        Py_BEGIN_ALLOW_THREADS\r
        fputs(emit, fp);\r
        Py_END_ALLOW_THREADS\r
        emit = separator;\r
        if (PyObject_Print(entry->key, fp, 0) != 0) {\r
            Py_ReprLeave((PyObject*)so);\r
            return -1;\r
        }\r
    }\r
    Py_BEGIN_ALLOW_THREADS\r
    fputs("])", fp);\r
    Py_END_ALLOW_THREADS\r
    Py_ReprLeave((PyObject*)so);\r
    return 0;\r
}\r
\r
static PyObject *\r
set_repr(PySetObject *so)\r
{\r
    PyObject *keys, *result=NULL, *listrepr;\r
    int status = Py_ReprEnter((PyObject*)so);\r
\r
    if (status != 0) {\r
        if (status < 0)\r
            return NULL;\r
        return PyString_FromFormat("%s(...)", so->ob_type->tp_name);\r
    }\r
\r
    keys = PySequence_List((PyObject *)so);\r
    if (keys == NULL)\r
        goto done;\r
    listrepr = PyObject_Repr(keys);\r
    Py_DECREF(keys);\r
    if (listrepr == NULL)\r
        goto done;\r
\r
    result = PyString_FromFormat("%s(%s)", so->ob_type->tp_name,\r
        PyString_AS_STRING(listrepr));\r
    Py_DECREF(listrepr);\r
done:\r
    Py_ReprLeave((PyObject*)so);\r
    return result;\r
}\r
\r
static Py_ssize_t\r
set_len(PyObject *so)\r
{\r
    return ((PySetObject *)so)->used;\r
}\r
\r
static int\r
set_merge(PySetObject *so, PyObject *otherset)\r
{\r
    PySetObject *other;\r
    PyObject *key;\r
    long hash;\r
    register Py_ssize_t i;\r
    register setentry *entry;\r
\r
    assert (PyAnySet_Check(so));\r
    assert (PyAnySet_Check(otherset));\r
\r
    other = (PySetObject*)otherset;\r
    if (other == so || other->used == 0)\r
        /* a.update(a) or a.update({}); nothing to do */\r
        return 0;\r
    /* Do one big resize at the start, rather than\r
     * incrementally resizing as we insert new keys.  Expect\r
     * that there will be no (or few) overlapping keys.\r
     */\r
    if ((so->fill + other->used)*3 >= (so->mask+1)*2) {\r
       if (set_table_resize(so, (so->used + other->used)*2) != 0)\r
           return -1;\r
    }\r
    for (i = 0; i <= other->mask; i++) {\r
        entry = &other->table[i];\r
        key = entry->key;\r
        hash = entry->hash;\r
        if (key != NULL &&\r
            key != dummy) {\r
            Py_INCREF(key);\r
            if (set_insert_key(so, key, hash) == -1) {\r
                Py_DECREF(key);\r
                return -1;\r
            }\r
        }\r
    }\r
    return 0;\r
}\r
\r
static int\r
set_contains_key(PySetObject *so, PyObject *key)\r
{\r
    long hash;\r
    setentry *entry;\r
\r
    if (!PyString_CheckExact(key) ||\r
        (hash = ((PyStringObject *) key)->ob_shash) == -1) {\r
        hash = PyObject_Hash(key);\r
        if (hash == -1)\r
            return -1;\r
    }\r
    entry = (so->lookup)(so, key, hash);\r
    if (entry == NULL)\r
        return -1;\r
    key = entry->key;\r
    return key != NULL && key != dummy;\r
}\r
\r
static int\r
set_contains_entry(PySetObject *so, setentry *entry)\r
{\r
    PyObject *key;\r
    setentry *lu_entry;\r
\r
    lu_entry = (so->lookup)(so, entry->key, entry->hash);\r
    if (lu_entry == NULL)\r
        return -1;\r
    key = lu_entry->key;\r
    return key != NULL && key != dummy;\r
}\r
\r
static PyObject *\r
set_pop(PySetObject *so)\r
{\r
    register Py_ssize_t i = 0;\r
    register setentry *entry;\r
    PyObject *key;\r
\r
    assert (PyAnySet_Check(so));\r
    if (so->used == 0) {\r
        PyErr_SetString(PyExc_KeyError, "pop from an empty set");\r
        return NULL;\r
    }\r
\r
    /* Set entry to "the first" unused or dummy set entry.  We abuse\r
     * the hash field of slot 0 to hold a search finger:\r
     * If slot 0 has a value, use slot 0.\r
     * Else slot 0 is being used to hold a search finger,\r
     * and we use its hash value as the first index to look.\r
     */\r
    entry = &so->table[0];\r
    if (entry->key == NULL || entry->key == dummy) {\r
        i = entry->hash;\r
        /* The hash field may be a real hash value, or it may be a\r
         * legit search finger, or it may be a once-legit search\r
         * finger that's out of bounds now because it wrapped around\r
         * or the table shrunk -- simply make sure it's in bounds now.\r
         */\r
        if (i > so->mask || i < 1)\r
            i = 1;              /* skip slot 0 */\r
        while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {\r
            i++;\r
            if (i > so->mask)\r
                i = 1;\r
        }\r
    }\r
    key = entry->key;\r
    Py_INCREF(dummy);\r
    entry->key = dummy;\r
    so->used--;\r
    so->table[0].hash = i + 1;  /* next place to start */\r
    return key;\r
}\r
\r
PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\\r
Raises KeyError if the set is empty.");\r
\r
static int\r
set_traverse(PySetObject *so, visitproc visit, void *arg)\r
{\r
    Py_ssize_t pos = 0;\r
    setentry *entry;\r
\r
    while (set_next(so, &pos, &entry))\r
        Py_VISIT(entry->key);\r
    return 0;\r
}\r
\r
static long\r
frozenset_hash(PyObject *self)\r
{\r
    PySetObject *so = (PySetObject *)self;\r
    long h, hash = 1927868237L;\r
    setentry *entry;\r
    Py_ssize_t pos = 0;\r
\r
    if (so->hash != -1)\r
        return so->hash;\r
\r
    hash *= PySet_GET_SIZE(self) + 1;\r
    while (set_next(so, &pos, &entry)) {\r
        /* Work to increase the bit dispersion for closely spaced hash\r
           values.  The is important because some use cases have many\r
           combinations of a small number of elements with nearby\r
           hashes so that many distinct combinations collapse to only\r
           a handful of distinct hash values. */\r
        h = entry->hash;\r
        hash ^= (h ^ (h << 16) ^ 89869747L)  * 3644798167u;\r
    }\r
    hash = hash * 69069L + 907133923L;\r
    if (hash == -1)\r
        hash = 590923713L;\r
    so->hash = hash;\r
    return hash;\r
}\r
\r
/***** Set iterator type ***********************************************/\r
\r
typedef struct {\r
    PyObject_HEAD\r
    PySetObject *si_set; /* Set to NULL when iterator is exhausted */\r
    Py_ssize_t si_used;\r
    Py_ssize_t si_pos;\r
    Py_ssize_t len;\r
} setiterobject;\r
\r
static void\r
setiter_dealloc(setiterobject *si)\r
{\r
    Py_XDECREF(si->si_set);\r
    PyObject_GC_Del(si);\r
}\r
\r
static int\r
setiter_traverse(setiterobject *si, visitproc visit, void *arg)\r
{\r
    Py_VISIT(si->si_set);\r
    return 0;\r
}\r
\r
static PyObject *\r
setiter_len(setiterobject *si)\r
{\r
    Py_ssize_t len = 0;\r
    if (si->si_set != NULL && si->si_used == si->si_set->used)\r
        len = si->len;\r
    return PyInt_FromLong(len);\r
}\r
\r
PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");\r
\r
static PyMethodDef setiter_methods[] = {\r
    {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},\r
    {NULL,              NULL}           /* sentinel */\r
};\r
\r
static PyObject *setiter_iternext(setiterobject *si)\r
{\r
    PyObject *key;\r
    register Py_ssize_t i, mask;\r
    register setentry *entry;\r
    PySetObject *so = si->si_set;\r
\r
    if (so == NULL)\r
        return NULL;\r
    assert (PyAnySet_Check(so));\r
\r
    if (si->si_used != so->used) {\r
        PyErr_SetString(PyExc_RuntimeError,\r
                        "Set changed size during iteration");\r
        si->si_used = -1; /* Make this state sticky */\r
        return NULL;\r
    }\r
\r
    i = si->si_pos;\r
    assert(i>=0);\r
    entry = so->table;\r
    mask = so->mask;\r
    while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))\r
        i++;\r
    si->si_pos = i+1;\r
    if (i > mask)\r
        goto fail;\r
    si->len--;\r
    key = entry[i].key;\r
    Py_INCREF(key);\r
    return key;\r
\r
fail:\r
    Py_DECREF(so);\r
    si->si_set = NULL;\r
    return NULL;\r
}\r
\r
static PyTypeObject PySetIter_Type = {\r
    PyVarObject_HEAD_INIT(&PyType_Type, 0)\r
    "setiterator",                              /* tp_name */\r
    sizeof(setiterobject),                      /* tp_basicsize */\r
    0,                                          /* tp_itemsize */\r
    /* methods */\r
    (destructor)setiter_dealloc,                /* tp_dealloc */\r
    0,                                          /* tp_print */\r
    0,                                          /* tp_getattr */\r
    0,                                          /* tp_setattr */\r
    0,                                          /* tp_compare */\r
    0,                                          /* tp_repr */\r
    0,                                          /* tp_as_number */\r
    0,                                          /* tp_as_sequence */\r
    0,                                          /* tp_as_mapping */\r
    0,                                          /* tp_hash */\r
    0,                                          /* tp_call */\r
    0,                                          /* tp_str */\r
    PyObject_GenericGetAttr,                    /* tp_getattro */\r
    0,                                          /* tp_setattro */\r
    0,                                          /* tp_as_buffer */\r
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */\r
    0,                                          /* tp_doc */\r
    (traverseproc)setiter_traverse,             /* tp_traverse */\r
    0,                                          /* tp_clear */\r
    0,                                          /* tp_richcompare */\r
    0,                                          /* tp_weaklistoffset */\r
    PyObject_SelfIter,                          /* tp_iter */\r
    (iternextfunc)setiter_iternext,             /* tp_iternext */\r
    setiter_methods,                            /* tp_methods */\r
    0,\r
};\r
\r
static PyObject *\r
set_iter(PySetObject *so)\r
{\r
    setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type);\r
    if (si == NULL)\r
        return NULL;\r
    Py_INCREF(so);\r
    si->si_set = so;\r
    si->si_used = so->used;\r
    si->si_pos = 0;\r
    si->len = so->used;\r
    _PyObject_GC_TRACK(si);\r
    return (PyObject *)si;\r
}\r
\r
static int\r
set_update_internal(PySetObject *so, PyObject *other)\r
{\r
    PyObject *key, *it;\r
\r
    if (PyAnySet_Check(other))\r
        return set_merge(so, other);\r
\r
    if (PyDict_CheckExact(other)) {\r
        PyObject *value;\r
        Py_ssize_t pos = 0;\r
        long hash;\r
        Py_ssize_t dictsize = PyDict_Size(other);\r
\r
        /* Do one big resize at the start, rather than\r
        * incrementally resizing as we insert new keys.  Expect\r
        * that there will be no (or few) overlapping keys.\r
        */\r
        if (dictsize == -1)\r
            return -1;\r
        if ((so->fill + dictsize)*3 >= (so->mask+1)*2) {\r
            if (set_table_resize(so, (so->used + dictsize)*2) != 0)\r
                return -1;\r
        }\r
        while (_PyDict_Next(other, &pos, &key, &value, &hash)) {\r
            setentry an_entry;\r
\r
            an_entry.hash = hash;\r
            an_entry.key = key;\r
            if (set_add_entry(so, &an_entry) == -1)\r
                return -1;\r
        }\r
        return 0;\r
    }\r
\r
    it = PyObject_GetIter(other);\r
    if (it == NULL)\r
        return -1;\r
\r
    while ((key = PyIter_Next(it)) != NULL) {\r
        if (set_add_key(so, key) == -1) {\r
            Py_DECREF(it);\r
            Py_DECREF(key);\r
            return -1;\r
        }\r
        Py_DECREF(key);\r
    }\r
    Py_DECREF(it);\r
    if (PyErr_Occurred())\r
        return -1;\r
    return 0;\r
}\r
\r
static PyObject *\r
set_update(PySetObject *so, PyObject *args)\r
{\r
    Py_ssize_t i;\r
\r
    for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {\r
        PyObject *other = PyTuple_GET_ITEM(args, i);\r
        if (set_update_internal(so, other) == -1)\r
            return NULL;\r
    }\r
    Py_RETURN_NONE;\r
}\r
\r
PyDoc_STRVAR(update_doc,\r
"Update a set with the union of itself and others.");\r
\r
static PyObject *\r
make_new_set(PyTypeObject *type, PyObject *iterable)\r
{\r
    register PySetObject *so = NULL;\r
\r
    if (dummy == NULL) { /* Auto-initialize dummy */\r
        dummy = PyString_FromString("<dummy key>");\r
        if (dummy == NULL)\r
            return NULL;\r
    }\r
\r
    /* create PySetObject structure */\r
    if (numfree &&\r
        (type == &PySet_Type  ||  type == &PyFrozenSet_Type)) {\r
        so = free_list[--numfree];\r
        assert (so != NULL && PyAnySet_CheckExact(so));\r
        Py_TYPE(so) = type;\r
        _Py_NewReference((PyObject *)so);\r
        EMPTY_TO_MINSIZE(so);\r
        PyObject_GC_Track(so);\r
    } else {\r
        so = (PySetObject *)type->tp_alloc(type, 0);\r
        if (so == NULL)\r
            return NULL;\r
        /* tp_alloc has already zeroed the structure */\r
        assert(so->table == NULL && so->fill == 0 && so->used == 0);\r
        INIT_NONZERO_SET_SLOTS(so);\r
    }\r
\r
    so->lookup = set_lookkey_string;\r
    so->weakreflist = NULL;\r
\r
    if (iterable != NULL) {\r
        if (set_update_internal(so, iterable) == -1) {\r
            Py_DECREF(so);\r
            return NULL;\r
        }\r
    }\r
\r
    return (PyObject *)so;\r
}\r
\r
/* The empty frozenset is a singleton */\r
static PyObject *emptyfrozenset = NULL;\r
\r
static PyObject *\r
frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)\r
{\r
    PyObject *iterable = NULL, *result;\r
\r
    if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds))\r
        return NULL;\r
\r
    if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))\r
        return NULL;\r
\r
    if (type != &PyFrozenSet_Type)\r
        return make_new_set(type, iterable);\r
\r
    if (iterable != NULL) {\r
        /* frozenset(f) is idempotent */\r
        if (PyFrozenSet_CheckExact(iterable)) {\r
            Py_INCREF(iterable);\r
            return iterable;\r
        }\r
        result = make_new_set(type, iterable);\r
        if (result == NULL || PySet_GET_SIZE(result))\r
            return result;\r
        Py_DECREF(result);\r
    }\r
    /* The empty frozenset is a singleton */\r
    if (emptyfrozenset == NULL)\r
        emptyfrozenset = make_new_set(type, NULL);\r
    Py_XINCREF(emptyfrozenset);\r
    return emptyfrozenset;\r
}\r
\r
void\r
PySet_Fini(void)\r
{\r
    PySetObject *so;\r
\r
    while (numfree) {\r
        numfree--;\r
        so = free_list[numfree];\r
        PyObject_GC_Del(so);\r
    }\r
    Py_CLEAR(dummy);\r
    Py_CLEAR(emptyfrozenset);\r
}\r
\r
static PyObject *\r
set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)\r
{\r
    if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds))\r
        return NULL;\r
\r
    return make_new_set(type, NULL);\r
}\r
\r
/* set_swap_bodies() switches the contents of any two sets by moving their\r
   internal data pointers and, if needed, copying the internal smalltables.\r
   Semantically equivalent to:\r
\r
     t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t\r
\r
   The function always succeeds and it leaves both objects in a stable state.\r
   Useful for creating temporary frozensets from sets for membership testing\r
   in __contains__(), discard(), and remove().  Also useful for operations\r
   that update in-place (by allowing an intermediate result to be swapped\r
   into one of the original inputs).\r
*/\r
\r
static void\r
set_swap_bodies(PySetObject *a, PySetObject *b)\r
{\r
    Py_ssize_t t;\r
    setentry *u;\r
    setentry *(*f)(PySetObject *so, PyObject *key, long hash);\r
    setentry tab[PySet_MINSIZE];\r
    long h;\r
\r
    t = a->fill;     a->fill   = b->fill;        b->fill  = t;\r
    t = a->used;     a->used   = b->used;        b->used  = t;\r
    t = a->mask;     a->mask   = b->mask;        b->mask  = t;\r
\r
    u = a->table;\r
    if (a->table == a->smalltable)\r
        u = b->smalltable;\r
    a->table  = b->table;\r
    if (b->table == b->smalltable)\r
        a->table = a->smalltable;\r
    b->table = u;\r
\r
    f = a->lookup;   a->lookup = b->lookup;      b->lookup = f;\r
\r
    if (a->table == a->smalltable || b->table == b->smalltable) {\r
        memcpy(tab, a->smalltable, sizeof(tab));\r
        memcpy(a->smalltable, b->smalltable, sizeof(tab));\r
        memcpy(b->smalltable, tab, sizeof(tab));\r
    }\r
\r
    if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type)  &&\r
        PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) {\r
        h = a->hash;     a->hash = b->hash;  b->hash = h;\r
    } else {\r
        a->hash = -1;\r
        b->hash = -1;\r
    }\r
}\r
\r
static PyObject *\r
set_copy(PySetObject *so)\r
{\r
    return make_new_set(Py_TYPE(so), (PyObject *)so);\r
}\r
\r
static PyObject *\r
frozenset_copy(PySetObject *so)\r
{\r
    if (PyFrozenSet_CheckExact(so)) {\r
        Py_INCREF(so);\r
        return (PyObject *)so;\r
    }\r
    return set_copy(so);\r
}\r
\r
PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");\r
\r
static PyObject *\r
set_clear(PySetObject *so)\r
{\r
    set_clear_internal(so);\r
    Py_RETURN_NONE;\r
}\r
\r
PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");\r
\r
static PyObject *\r
set_union(PySetObject *so, PyObject *args)\r
{\r
    PySetObject *result;\r
    PyObject *other;\r
    Py_ssize_t i;\r
\r
    result = (PySetObject *)set_copy(so);\r
    if (result == NULL)\r
        return NULL;\r
\r
    for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {\r
        other = PyTuple_GET_ITEM(args, i);\r
        if ((PyObject *)so == other)\r
            continue;\r
        if (set_update_internal(result, other) == -1) {\r
            Py_DECREF(result);\r
            return NULL;\r
        }\r
    }\r
    return (PyObject *)result;\r
}\r
\r
PyDoc_STRVAR(union_doc,\r
 "Return the union of sets as a new set.\n\\r
\n\\r
(i.e. all elements that are in either set.)");\r
\r
static PyObject *\r
set_or(PySetObject *so, PyObject *other)\r
{\r
    PySetObject *result;\r
\r
    if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {\r
        Py_INCREF(Py_NotImplemented);\r
        return Py_NotImplemented;\r
    }\r
\r
    result = (PySetObject *)set_copy(so);\r
    if (result == NULL)\r
        return NULL;\r
    if ((PyObject *)so == other)\r
        return (PyObject *)result;\r
    if (set_update_internal(result, other) == -1) {\r
        Py_DECREF(result);\r
        return NULL;\r
    }\r
    return (PyObject *)result;\r
}\r
\r
static PyObject *\r
set_ior(PySetObject *so, PyObject *other)\r
{\r
    if (!PyAnySet_Check(other)) {\r
        Py_INCREF(Py_NotImplemented);\r
        return Py_NotImplemented;\r
    }\r
    if (set_update_internal(so, other) == -1)\r
        return NULL;\r
    Py_INCREF(so);\r
    return (PyObject *)so;\r
}\r
\r
static PyObject *\r
set_intersection(PySetObject *so, PyObject *other)\r
{\r
    PySetObject *result;\r
    PyObject *key, *it, *tmp;\r
\r
    if ((PyObject *)so == other)\r
        return set_copy(so);\r
\r
    result = (PySetObject *)make_new_set(Py_TYPE(so), NULL);\r
    if (result == NULL)\r
        return NULL;\r
\r
    if (PyAnySet_Check(other)) {\r
        Py_ssize_t pos = 0;\r
        setentry *entry;\r
\r
        if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {\r
            tmp = (PyObject *)so;\r
            so = (PySetObject *)other;\r
            other = tmp;\r
        }\r
\r
        while (set_next((PySetObject *)other, &pos, &entry)) {\r
            int rv = set_contains_entry(so, entry);\r
            if (rv == -1) {\r
                Py_DECREF(result);\r
                return NULL;\r
            }\r
            if (rv) {\r
                if (set_add_entry(result, entry) == -1) {\r
                    Py_DECREF(result);\r
                    return NULL;\r
                }\r
            }\r
        }\r
        return (PyObject *)result;\r
    }\r
\r
    it = PyObject_GetIter(other);\r
    if (it == NULL) {\r
        Py_DECREF(result);\r
        return NULL;\r
    }\r
\r
    while ((key = PyIter_Next(it)) != NULL) {\r
        int rv;\r
        setentry entry;\r
        long hash = PyObject_Hash(key);\r
\r
        if (hash == -1) {\r
            Py_DECREF(it);\r
            Py_DECREF(result);\r
            Py_DECREF(key);\r
            return NULL;\r
        }\r
        entry.hash = hash;\r
        entry.key = key;\r
        rv = set_contains_entry(so, &entry);\r
        if (rv == -1) {\r
            Py_DECREF(it);\r
            Py_DECREF(result);\r
            Py_DECREF(key);\r
            return NULL;\r
        }\r
        if (rv) {\r
            if (set_add_entry(result, &entry) == -1) {\r
                Py_DECREF(it);\r
                Py_DECREF(result);\r
                Py_DECREF(key);\r
                return NULL;\r
            }\r
        }\r
        Py_DECREF(key);\r
    }\r
    Py_DECREF(it);\r
    if (PyErr_Occurred()) {\r
        Py_DECREF(result);\r
        return NULL;\r
    }\r
    return (PyObject *)result;\r
}\r
\r
static PyObject *\r
set_intersection_multi(PySetObject *so, PyObject *args)\r
{\r
    Py_ssize_t i;\r
    PyObject *result = (PyObject *)so;\r
\r
    if (PyTuple_GET_SIZE(args) == 0)\r
        return set_copy(so);\r
\r
    Py_INCREF(so);\r
    for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {\r
        PyObject *other = PyTuple_GET_ITEM(args, i);\r
        PyObject *newresult = set_intersection((PySetObject *)result, other);\r
        if (newresult == NULL) {\r
            Py_DECREF(result);\r
            return NULL;\r
        }\r
        Py_DECREF(result);\r
        result = newresult;\r
    }\r
    return result;\r
}\r
\r
PyDoc_STRVAR(intersection_doc,\r
"Return the intersection of two or more sets as a new set.\n\\r
\n\\r
(i.e. elements that are common to all of the sets.)");\r
\r
static PyObject *\r
set_intersection_update(PySetObject *so, PyObject *other)\r
{\r
    PyObject *tmp;\r
\r
    tmp = set_intersection(so, other);\r
    if (tmp == NULL)\r
        return NULL;\r
    set_swap_bodies(so, (PySetObject *)tmp);\r
    Py_DECREF(tmp);\r
    Py_RETURN_NONE;\r
}\r
\r
static PyObject *\r
set_intersection_update_multi(PySetObject *so, PyObject *args)\r
{\r
    PyObject *tmp;\r
\r
    tmp = set_intersection_multi(so, args);\r
    if (tmp == NULL)\r
        return NULL;\r
    set_swap_bodies(so, (PySetObject *)tmp);\r
    Py_DECREF(tmp);\r
    Py_RETURN_NONE;\r
}\r
\r
PyDoc_STRVAR(intersection_update_doc,\r
"Update a set with the intersection of itself and another.");\r
\r
static PyObject *\r
set_and(PySetObject *so, PyObject *other)\r
{\r
    if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {\r
        Py_INCREF(Py_NotImplemented);\r
        return Py_NotImplemented;\r
    }\r
    return set_intersection(so, other);\r
}\r
\r
static PyObject *\r
set_iand(PySetObject *so, PyObject *other)\r
{\r
    PyObject *result;\r
\r
    if (!PyAnySet_Check(other)) {\r
        Py_INCREF(Py_NotImplemented);\r
        return Py_NotImplemented;\r
    }\r
    result = set_intersection_update(so, other);\r
    if (result == NULL)\r
        return NULL;\r
    Py_DECREF(result);\r
    Py_INCREF(so);\r
    return (PyObject *)so;\r
}\r
\r
static PyObject *\r
set_isdisjoint(PySetObject *so, PyObject *other)\r
{\r
    PyObject *key, *it, *tmp;\r
\r
    if ((PyObject *)so == other) {\r
        if (PySet_GET_SIZE(so) == 0)\r
            Py_RETURN_TRUE;\r
        else\r
            Py_RETURN_FALSE;\r
    }\r
\r
    if (PyAnySet_CheckExact(other)) {\r
        Py_ssize_t pos = 0;\r
        setentry *entry;\r
\r
        if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {\r
            tmp = (PyObject *)so;\r
            so = (PySetObject *)other;\r
            other = tmp;\r
        }\r
        while (set_next((PySetObject *)other, &pos, &entry)) {\r
            int rv = set_contains_entry(so, entry);\r
            if (rv == -1)\r
                return NULL;\r
            if (rv)\r
                Py_RETURN_FALSE;\r
        }\r
        Py_RETURN_TRUE;\r
    }\r
\r
    it = PyObject_GetIter(other);\r
    if (it == NULL)\r
        return NULL;\r
\r
    while ((key = PyIter_Next(it)) != NULL) {\r
        int rv;\r
        setentry entry;\r
        long hash = PyObject_Hash(key);\r
\r
        if (hash == -1) {\r
            Py_DECREF(key);\r
            Py_DECREF(it);\r
            return NULL;\r
        }\r
        entry.hash = hash;\r
        entry.key = key;\r
        rv = set_contains_entry(so, &entry);\r
        Py_DECREF(key);\r
        if (rv == -1) {\r
            Py_DECREF(it);\r
            return NULL;\r
        }\r
        if (rv) {\r
            Py_DECREF(it);\r
            Py_RETURN_FALSE;\r
        }\r
    }\r
    Py_DECREF(it);\r
    if (PyErr_Occurred())\r
        return NULL;\r
    Py_RETURN_TRUE;\r
}\r
\r
PyDoc_STRVAR(isdisjoint_doc,\r
"Return True if two sets have a null intersection.");\r
\r
static int\r
set_difference_update_internal(PySetObject *so, PyObject *other)\r
{\r
    if ((PyObject *)so == other)\r
        return set_clear_internal(so);\r
\r
    if (PyAnySet_Check(other)) {\r
        setentry *entry;\r
        Py_ssize_t pos = 0;\r
\r
        while (set_next((PySetObject *)other, &pos, &entry))\r
            if (set_discard_entry(so, entry) == -1)\r
                return -1;\r
    } else {\r
        PyObject *key, *it;\r
        it = PyObject_GetIter(other);\r
        if (it == NULL)\r
            return -1;\r
\r
        while ((key = PyIter_Next(it)) != NULL) {\r
            if (set_discard_key(so, key) == -1) {\r
                Py_DECREF(it);\r
                Py_DECREF(key);\r
                return -1;\r
            }\r
            Py_DECREF(key);\r
        }\r
        Py_DECREF(it);\r
        if (PyErr_Occurred())\r
            return -1;\r
    }\r
    /* If more than 1/5 are dummies, then resize them away. */\r
    if ((so->fill - so->used) * 5 < so->mask)\r
        return 0;\r
    return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);\r
}\r
\r
static PyObject *\r
set_difference_update(PySetObject *so, PyObject *args)\r
{\r
    Py_ssize_t i;\r
\r
    for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {\r
        PyObject *other = PyTuple_GET_ITEM(args, i);\r
        if (set_difference_update_internal(so, other) == -1)\r
            return NULL;\r
    }\r
    Py_RETURN_NONE;\r
}\r
\r
PyDoc_STRVAR(difference_update_doc,\r
"Remove all elements of another set from this set.");\r
\r
static PyObject *\r
set_difference(PySetObject *so, PyObject *other)\r
{\r
    PyObject *result;\r
    setentry *entry;\r
    Py_ssize_t pos = 0;\r
\r
    if (!PyAnySet_Check(other)  && !PyDict_CheckExact(other)) {\r
        result = set_copy(so);\r
        if (result == NULL)\r
            return NULL;\r
        if (set_difference_update_internal((PySetObject *)result, other) != -1)\r
            return result;\r
        Py_DECREF(result);\r
        return NULL;\r
    }\r
\r
    result = make_new_set(Py_TYPE(so), NULL);\r
    if (result == NULL)\r
        return NULL;\r
\r
    if (PyDict_CheckExact(other)) {\r
        while (set_next(so, &pos, &entry)) {\r
            setentry entrycopy;\r
            entrycopy.hash = entry->hash;\r
            entrycopy.key = entry->key;\r
            if (!_PyDict_Contains(other, entry->key, entry->hash)) {\r
                if (set_add_entry((PySetObject *)result, &entrycopy) == -1) {\r
                    Py_DECREF(result);\r
                    return NULL;\r
                }\r
            }\r
        }\r
        return result;\r
    }\r
\r
    while (set_next(so, &pos, &entry)) {\r
        int rv = set_contains_entry((PySetObject *)other, entry);\r
        if (rv == -1) {\r
            Py_DECREF(result);\r
            return NULL;\r
        }\r
        if (!rv) {\r
            if (set_add_entry((PySetObject *)result, entry) == -1) {\r
                Py_DECREF(result);\r
                return NULL;\r
            }\r
        }\r
    }\r
    return result;\r
}\r
\r
static PyObject *\r
set_difference_multi(PySetObject *so, PyObject *args)\r
{\r
    Py_ssize_t i;\r
    PyObject *result, *other;\r
\r
    if (PyTuple_GET_SIZE(args) == 0)\r
        return set_copy(so);\r
\r
    other = PyTuple_GET_ITEM(args, 0);\r
    result = set_difference(so, other);\r
    if (result == NULL)\r
        return NULL;\r
\r
    for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) {\r
        other = PyTuple_GET_ITEM(args, i);\r
        if (set_difference_update_internal((PySetObject *)result, other) == -1) {\r
            Py_DECREF(result);\r
            return NULL;\r
        }\r
    }\r
    return result;\r
}\r
\r
PyDoc_STRVAR(difference_doc,\r
"Return the difference of two or more sets as a new set.\n\\r
\n\\r
(i.e. all elements that are in this set but not the others.)");\r
static PyObject *\r
set_sub(PySetObject *so, PyObject *other)\r
{\r
    if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {\r
        Py_INCREF(Py_NotImplemented);\r
        return Py_NotImplemented;\r
    }\r
    return set_difference(so, other);\r
}\r
\r
static PyObject *\r
set_isub(PySetObject *so, PyObject *other)\r
{\r
    if (!PyAnySet_Check(other)) {\r
        Py_INCREF(Py_NotImplemented);\r
        return Py_NotImplemented;\r
    }\r
    if (set_difference_update_internal(so, other) == -1)\r
        return NULL;\r
    Py_INCREF(so);\r
    return (PyObject *)so;\r
}\r
\r
static PyObject *\r
set_symmetric_difference_update(PySetObject *so, PyObject *other)\r
{\r
    PySetObject *otherset;\r
    PyObject *key;\r
    Py_ssize_t pos = 0;\r
    setentry *entry;\r
\r
    if ((PyObject *)so == other)\r
        return set_clear(so);\r
\r
    if (PyDict_CheckExact(other)) {\r
        PyObject *value;\r
        int rv;\r
        long hash;\r
        while (_PyDict_Next(other, &pos, &key, &value, &hash)) {\r
            setentry an_entry;\r
\r
            Py_INCREF(key);\r
            an_entry.hash = hash;\r
            an_entry.key = key;\r
\r
            rv = set_discard_entry(so, &an_entry);\r
            if (rv == -1) {\r
                Py_DECREF(key);\r
                return NULL;\r
            }\r
            if (rv == DISCARD_NOTFOUND) {\r
                if (set_add_entry(so, &an_entry) == -1) {\r
                    Py_DECREF(key);\r
                    return NULL;\r
                }\r
            }\r
            Py_DECREF(key);\r
        }\r
        Py_RETURN_NONE;\r
    }\r
\r
    if (PyAnySet_Check(other)) {\r
        Py_INCREF(other);\r
        otherset = (PySetObject *)other;\r
    } else {\r
        otherset = (PySetObject *)make_new_set(Py_TYPE(so), other);\r
        if (otherset == NULL)\r
            return NULL;\r
    }\r
\r
    while (set_next(otherset, &pos, &entry)) {\r
        int rv = set_discard_entry(so, entry);\r
        if (rv == -1) {\r
            Py_DECREF(otherset);\r
            return NULL;\r
        }\r
        if (rv == DISCARD_NOTFOUND) {\r
            if (set_add_entry(so, entry) == -1) {\r
                Py_DECREF(otherset);\r
                return NULL;\r
            }\r
        }\r
    }\r
    Py_DECREF(otherset);\r
    Py_RETURN_NONE;\r
}\r
\r
PyDoc_STRVAR(symmetric_difference_update_doc,\r
"Update a set with the symmetric difference of itself and another.");\r
\r
static PyObject *\r
set_symmetric_difference(PySetObject *so, PyObject *other)\r
{\r
    PyObject *rv;\r
    PySetObject *otherset;\r
\r
    otherset = (PySetObject *)make_new_set(Py_TYPE(so), other);\r
    if (otherset == NULL)\r
        return NULL;\r
    rv = set_symmetric_difference_update(otherset, (PyObject *)so);\r
    if (rv == NULL)\r
        return NULL;\r
    Py_DECREF(rv);\r
    return (PyObject *)otherset;\r
}\r
\r
PyDoc_STRVAR(symmetric_difference_doc,\r
"Return the symmetric difference of two sets as a new set.\n\\r
\n\\r
(i.e. all elements that are in exactly one of the sets.)");\r
\r
static PyObject *\r
set_xor(PySetObject *so, PyObject *other)\r
{\r
    if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {\r
        Py_INCREF(Py_NotImplemented);\r
        return Py_NotImplemented;\r
    }\r
    return set_symmetric_difference(so, other);\r
}\r
\r
static PyObject *\r
set_ixor(PySetObject *so, PyObject *other)\r
{\r
    PyObject *result;\r
\r
    if (!PyAnySet_Check(other)) {\r
        Py_INCREF(Py_NotImplemented);\r
        return Py_NotImplemented;\r
    }\r
    result = set_symmetric_difference_update(so, other);\r
    if (result == NULL)\r
        return NULL;\r
    Py_DECREF(result);\r
    Py_INCREF(so);\r
    return (PyObject *)so;\r
}\r
\r
static PyObject *\r
set_issubset(PySetObject *so, PyObject *other)\r
{\r
    setentry *entry;\r
    Py_ssize_t pos = 0;\r
\r
    if (!PyAnySet_Check(other)) {\r
        PyObject *tmp, *result;\r
        tmp = make_new_set(&PySet_Type, other);\r
        if (tmp == NULL)\r
            return NULL;\r
        result = set_issubset(so, tmp);\r
        Py_DECREF(tmp);\r
        return result;\r
    }\r
    if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))\r
        Py_RETURN_FALSE;\r
\r
    while (set_next(so, &pos, &entry)) {\r
        int rv = set_contains_entry((PySetObject *)other, entry);\r
        if (rv == -1)\r
            return NULL;\r
        if (!rv)\r
            Py_RETURN_FALSE;\r
    }\r
    Py_RETURN_TRUE;\r
}\r
\r
PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");\r
\r
static PyObject *\r
set_issuperset(PySetObject *so, PyObject *other)\r
{\r
    PyObject *tmp, *result;\r
\r
    if (!PyAnySet_Check(other)) {\r
        tmp = make_new_set(&PySet_Type, other);\r
        if (tmp == NULL)\r
            return NULL;\r
        result = set_issuperset(so, tmp);\r
        Py_DECREF(tmp);\r
        return result;\r
    }\r
    return set_issubset((PySetObject *)other, (PyObject *)so);\r
}\r
\r
PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");\r
\r
static PyObject *\r
set_richcompare(PySetObject *v, PyObject *w, int op)\r
{\r
    PyObject *r1, *r2;\r
\r
    if(!PyAnySet_Check(w)) {\r
        Py_INCREF(Py_NotImplemented);\r
        return Py_NotImplemented;\r
    }\r
    switch (op) {\r
    case Py_EQ:\r
        if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))\r
            Py_RETURN_FALSE;\r
        if (v->hash != -1  &&\r
            ((PySetObject *)w)->hash != -1 &&\r
            v->hash != ((PySetObject *)w)->hash)\r
            Py_RETURN_FALSE;\r
        return set_issubset(v, w);\r
    case Py_NE:\r
        r1 = set_richcompare(v, w, Py_EQ);\r
        if (r1 == NULL)\r
            return NULL;\r
        r2 = PyBool_FromLong(PyObject_Not(r1));\r
        Py_DECREF(r1);\r
        return r2;\r
    case Py_LE:\r
        return set_issubset(v, w);\r
    case Py_GE:\r
        return set_issuperset(v, w);\r
    case Py_LT:\r
        if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))\r
            Py_RETURN_FALSE;\r
        return set_issubset(v, w);\r
    case Py_GT:\r
        if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))\r
            Py_RETURN_FALSE;\r
        return set_issuperset(v, w);\r
    }\r
    Py_INCREF(Py_NotImplemented);\r
    return Py_NotImplemented;\r
}\r
\r
static int\r
set_nocmp(PyObject *self, PyObject *other)\r
{\r
    PyErr_SetString(PyExc_TypeError, "cannot compare sets using cmp()");\r
    return -1;\r
}\r
\r
static PyObject *\r
set_add(PySetObject *so, PyObject *key)\r
{\r
    if (set_add_key(so, key) == -1)\r
        return NULL;\r
    Py_RETURN_NONE;\r
}\r
\r
PyDoc_STRVAR(add_doc,\r
"Add an element to a set.\n\\r
\n\\r
This has no effect if the element is already present.");\r
\r
static int\r
set_contains(PySetObject *so, PyObject *key)\r
{\r
    PyObject *tmpkey;\r
    int rv;\r
\r
    rv = set_contains_key(so, key);\r
    if (rv == -1) {\r
        if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))\r
            return -1;\r
        PyErr_Clear();\r
        tmpkey = make_new_set(&PyFrozenSet_Type, key);\r
        if (tmpkey == NULL)\r
            return -1;\r
        rv = set_contains_key(so, tmpkey);\r
        Py_DECREF(tmpkey);\r
    }\r
    return rv;\r
}\r
\r
static PyObject *\r
set_direct_contains(PySetObject *so, PyObject *key)\r
{\r
    long result;\r
\r
    result = set_contains(so, key);\r
    if (result == -1)\r
        return NULL;\r
    return PyBool_FromLong(result);\r
}\r
\r
PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");\r
\r
static PyObject *\r
set_remove(PySetObject *so, PyObject *key)\r
{\r
    PyObject *tmpkey;\r
    int rv;\r
\r
    rv = set_discard_key(so, key);\r
    if (rv == -1) {\r
        if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))\r
            return NULL;\r
        PyErr_Clear();\r
        tmpkey = make_new_set(&PyFrozenSet_Type, key);\r
        if (tmpkey == NULL)\r
            return NULL;\r
        rv = set_discard_key(so, tmpkey);\r
        Py_DECREF(tmpkey);\r
        if (rv == -1)\r
            return NULL;\r
    }\r
\r
    if (rv == DISCARD_NOTFOUND) {\r
        set_key_error(key);\r
        return NULL;\r
    }\r
    Py_RETURN_NONE;\r
}\r
\r
PyDoc_STRVAR(remove_doc,\r
"Remove an element from a set; it must be a member.\n\\r
\n\\r
If the element is not a member, raise a KeyError.");\r
\r
static PyObject *\r
set_discard(PySetObject *so, PyObject *key)\r
{\r
    PyObject *tmpkey;\r
    int rv;\r
\r
    rv = set_discard_key(so, key);\r
    if (rv == -1) {\r
        if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))\r
            return NULL;\r
        PyErr_Clear();\r
        tmpkey = make_new_set(&PyFrozenSet_Type, key);\r
        if (tmpkey == NULL)\r
            return NULL;\r
        rv = set_discard_key(so, tmpkey);\r
        Py_DECREF(tmpkey);\r
        if (rv == -1)\r
            return NULL;\r
    }\r
    Py_RETURN_NONE;\r
}\r
\r
PyDoc_STRVAR(discard_doc,\r
"Remove an element from a set if it is a member.\n\\r
\n\\r
If the element is not a member, do nothing.");\r
\r
static PyObject *\r
set_reduce(PySetObject *so)\r
{\r
    PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;\r
\r
    keys = PySequence_List((PyObject *)so);\r
    if (keys == NULL)\r
        goto done;\r
    args = PyTuple_Pack(1, keys);\r
    if (args == NULL)\r
        goto done;\r
    dict = PyObject_GetAttrString((PyObject *)so, "__dict__");\r
    if (dict == NULL) {\r
        PyErr_Clear();\r
        dict = Py_None;\r
        Py_INCREF(dict);\r
    }\r
    result = PyTuple_Pack(3, Py_TYPE(so), args, dict);\r
done:\r
    Py_XDECREF(args);\r
    Py_XDECREF(keys);\r
    Py_XDECREF(dict);\r
    return result;\r
}\r
\r
PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");\r
\r
static PyObject *\r
set_sizeof(PySetObject *so)\r
{\r
    Py_ssize_t res;\r
\r
    res = sizeof(PySetObject);\r
    if (so->table != so->smalltable)\r
        res = res + (so->mask + 1) * sizeof(setentry);\r
    return PyInt_FromSsize_t(res);\r
}\r
\r
PyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes");\r
static int\r
set_init(PySetObject *self, PyObject *args, PyObject *kwds)\r
{\r
    PyObject *iterable = NULL;\r
\r
    if (!PyAnySet_Check(self))\r
        return -1;\r
    if (PySet_Check(self) && !_PyArg_NoKeywords("set()", kwds))\r
        return -1;\r
    if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable))\r
        return -1;\r
    set_clear_internal(self);\r
    self->hash = -1;\r
    if (iterable == NULL)\r
        return 0;\r
    return set_update_internal(self, iterable);\r
}\r
\r
static PySequenceMethods set_as_sequence = {\r
    set_len,                            /* sq_length */\r
    0,                                  /* sq_concat */\r
    0,                                  /* sq_repeat */\r
    0,                                  /* sq_item */\r
    0,                                  /* sq_slice */\r
    0,                                  /* sq_ass_item */\r
    0,                                  /* sq_ass_slice */\r
    (objobjproc)set_contains,           /* sq_contains */\r
};\r
\r
/* set object ********************************************************/\r
\r
#ifdef Py_DEBUG\r
static PyObject *test_c_api(PySetObject *so);\r
\r
PyDoc_STRVAR(test_c_api_doc, "Exercises C API.  Returns True.\n\\r
All is well if assertions don't fail.");\r
#endif\r
\r
static PyMethodDef set_methods[] = {\r
    {"add",             (PyCFunction)set_add,           METH_O,\r
     add_doc},\r
    {"clear",           (PyCFunction)set_clear,         METH_NOARGS,\r
     clear_doc},\r
    {"__contains__",(PyCFunction)set_direct_contains,           METH_O | METH_COEXIST,\r
     contains_doc},\r
    {"copy",            (PyCFunction)set_copy,          METH_NOARGS,\r
     copy_doc},\r
    {"discard",         (PyCFunction)set_discard,       METH_O,\r
     discard_doc},\r
    {"difference",      (PyCFunction)set_difference_multi,      METH_VARARGS,\r
     difference_doc},\r
    {"difference_update",       (PyCFunction)set_difference_update,     METH_VARARGS,\r
     difference_update_doc},\r
    {"intersection",(PyCFunction)set_intersection_multi,        METH_VARARGS,\r
     intersection_doc},\r
    {"intersection_update",(PyCFunction)set_intersection_update_multi,          METH_VARARGS,\r
     intersection_update_doc},\r
    {"isdisjoint",      (PyCFunction)set_isdisjoint,    METH_O,\r
     isdisjoint_doc},\r
    {"issubset",        (PyCFunction)set_issubset,      METH_O,\r
     issubset_doc},\r
    {"issuperset",      (PyCFunction)set_issuperset,    METH_O,\r
     issuperset_doc},\r
    {"pop",             (PyCFunction)set_pop,           METH_NOARGS,\r
     pop_doc},\r
    {"__reduce__",      (PyCFunction)set_reduce,        METH_NOARGS,\r
     reduce_doc},\r
    {"remove",          (PyCFunction)set_remove,        METH_O,\r
     remove_doc},\r
    {"__sizeof__",      (PyCFunction)set_sizeof,        METH_NOARGS,\r
     sizeof_doc},\r
    {"symmetric_difference",(PyCFunction)set_symmetric_difference,      METH_O,\r
     symmetric_difference_doc},\r
    {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update,        METH_O,\r
     symmetric_difference_update_doc},\r
#ifdef Py_DEBUG\r
    {"test_c_api",      (PyCFunction)test_c_api,        METH_NOARGS,\r
     test_c_api_doc},\r
#endif\r
    {"union",           (PyCFunction)set_union,         METH_VARARGS,\r
     union_doc},\r
    {"update",          (PyCFunction)set_update,        METH_VARARGS,\r
     update_doc},\r
    {NULL,              NULL}   /* sentinel */\r
};\r
\r
static PyNumberMethods set_as_number = {\r
    0,                                  /*nb_add*/\r
    (binaryfunc)set_sub,                /*nb_subtract*/\r
    0,                                  /*nb_multiply*/\r
    0,                                  /*nb_divide*/\r
    0,                                  /*nb_remainder*/\r
    0,                                  /*nb_divmod*/\r
    0,                                  /*nb_power*/\r
    0,                                  /*nb_negative*/\r
    0,                                  /*nb_positive*/\r
    0,                                  /*nb_absolute*/\r
    0,                                  /*nb_nonzero*/\r
    0,                                  /*nb_invert*/\r
    0,                                  /*nb_lshift*/\r
    0,                                  /*nb_rshift*/\r
    (binaryfunc)set_and,                /*nb_and*/\r
    (binaryfunc)set_xor,                /*nb_xor*/\r
    (binaryfunc)set_or,                 /*nb_or*/\r
    0,                                  /*nb_coerce*/\r
    0,                                  /*nb_int*/\r
    0,                                  /*nb_long*/\r
    0,                                  /*nb_float*/\r
    0,                                  /*nb_oct*/\r
    0,                                  /*nb_hex*/\r
    0,                                  /*nb_inplace_add*/\r
    (binaryfunc)set_isub,               /*nb_inplace_subtract*/\r
    0,                                  /*nb_inplace_multiply*/\r
    0,                                  /*nb_inplace_divide*/\r
    0,                                  /*nb_inplace_remainder*/\r
    0,                                  /*nb_inplace_power*/\r
    0,                                  /*nb_inplace_lshift*/\r
    0,                                  /*nb_inplace_rshift*/\r
    (binaryfunc)set_iand,               /*nb_inplace_and*/\r
    (binaryfunc)set_ixor,               /*nb_inplace_xor*/\r
    (binaryfunc)set_ior,                /*nb_inplace_or*/\r
};\r
\r
PyDoc_STRVAR(set_doc,\r
"set() -> new empty set object\n\\r
set(iterable) -> new set object\n\\r
\n\\r
Build an unordered collection of unique elements.");\r
\r
PyTypeObject PySet_Type = {\r
    PyVarObject_HEAD_INIT(&PyType_Type, 0)\r
    "set",                              /* tp_name */\r
    sizeof(PySetObject),                /* tp_basicsize */\r
    0,                                  /* tp_itemsize */\r
    /* methods */\r
    (destructor)set_dealloc,            /* tp_dealloc */\r
    (printfunc)set_tp_print,            /* tp_print */\r
    0,                                  /* tp_getattr */\r
    0,                                  /* tp_setattr */\r
    set_nocmp,                          /* tp_compare */\r
    (reprfunc)set_repr,                 /* tp_repr */\r
    &set_as_number,                     /* tp_as_number */\r
    &set_as_sequence,                   /* tp_as_sequence */\r
    0,                                  /* tp_as_mapping */\r
    (hashfunc)PyObject_HashNotImplemented,      /* tp_hash */\r
    0,                                  /* tp_call */\r
    0,                                  /* tp_str */\r
    PyObject_GenericGetAttr,            /* tp_getattro */\r
    0,                                  /* tp_setattro */\r
    0,                                  /* tp_as_buffer */\r
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_CHECKTYPES |\r
        Py_TPFLAGS_BASETYPE,            /* tp_flags */\r
    set_doc,                            /* tp_doc */\r
    (traverseproc)set_traverse,         /* tp_traverse */\r
    (inquiry)set_clear_internal,        /* tp_clear */\r
    (richcmpfunc)set_richcompare,       /* tp_richcompare */\r
    offsetof(PySetObject, weakreflist),         /* tp_weaklistoffset */\r
    (getiterfunc)set_iter,      /* tp_iter */\r
    0,                                  /* tp_iternext */\r
    set_methods,                        /* tp_methods */\r
    0,                                  /* tp_members */\r
    0,                                  /* tp_getset */\r
    0,                                  /* tp_base */\r
    0,                                  /* tp_dict */\r
    0,                                  /* tp_descr_get */\r
    0,                                  /* tp_descr_set */\r
    0,                                  /* tp_dictoffset */\r
    (initproc)set_init,                 /* tp_init */\r
    PyType_GenericAlloc,                /* tp_alloc */\r
    set_new,                            /* tp_new */\r
    PyObject_GC_Del,                    /* tp_free */\r
};\r
\r
/* frozenset object ********************************************************/\r
\r
\r
static PyMethodDef frozenset_methods[] = {\r
    {"__contains__",(PyCFunction)set_direct_contains,           METH_O | METH_COEXIST,\r
     contains_doc},\r
    {"copy",            (PyCFunction)frozenset_copy,    METH_NOARGS,\r
     copy_doc},\r
    {"difference",      (PyCFunction)set_difference_multi,      METH_VARARGS,\r
     difference_doc},\r
    {"intersection",(PyCFunction)set_intersection_multi,        METH_VARARGS,\r
     intersection_doc},\r
    {"isdisjoint",      (PyCFunction)set_isdisjoint,    METH_O,\r
     isdisjoint_doc},\r
    {"issubset",        (PyCFunction)set_issubset,      METH_O,\r
     issubset_doc},\r
    {"issuperset",      (PyCFunction)set_issuperset,    METH_O,\r
     issuperset_doc},\r
    {"__reduce__",      (PyCFunction)set_reduce,        METH_NOARGS,\r
     reduce_doc},\r
    {"__sizeof__",      (PyCFunction)set_sizeof,        METH_NOARGS,\r
     sizeof_doc},\r
    {"symmetric_difference",(PyCFunction)set_symmetric_difference,      METH_O,\r
     symmetric_difference_doc},\r
    {"union",           (PyCFunction)set_union,         METH_VARARGS,\r
     union_doc},\r
    {NULL,              NULL}   /* sentinel */\r
};\r
\r
static PyNumberMethods frozenset_as_number = {\r
    0,                                  /*nb_add*/\r
    (binaryfunc)set_sub,                /*nb_subtract*/\r
    0,                                  /*nb_multiply*/\r
    0,                                  /*nb_divide*/\r
    0,                                  /*nb_remainder*/\r
    0,                                  /*nb_divmod*/\r
    0,                                  /*nb_power*/\r
    0,                                  /*nb_negative*/\r
    0,                                  /*nb_positive*/\r
    0,                                  /*nb_absolute*/\r
    0,                                  /*nb_nonzero*/\r
    0,                                  /*nb_invert*/\r
    0,                                  /*nb_lshift*/\r
    0,                                  /*nb_rshift*/\r
    (binaryfunc)set_and,                /*nb_and*/\r
    (binaryfunc)set_xor,                /*nb_xor*/\r
    (binaryfunc)set_or,                 /*nb_or*/\r
};\r
\r
PyDoc_STRVAR(frozenset_doc,\r
"frozenset() -> empty frozenset object\n\\r
frozenset(iterable) -> frozenset object\n\\r
\n\\r
Build an immutable unordered collection of unique elements.");\r
\r
PyTypeObject PyFrozenSet_Type = {\r
    PyVarObject_HEAD_INIT(&PyType_Type, 0)\r
    "frozenset",                        /* tp_name */\r
    sizeof(PySetObject),                /* tp_basicsize */\r
    0,                                  /* tp_itemsize */\r
    /* methods */\r
    (destructor)set_dealloc,            /* tp_dealloc */\r
    (printfunc)set_tp_print,            /* tp_print */\r
    0,                                  /* tp_getattr */\r
    0,                                  /* tp_setattr */\r
    set_nocmp,                          /* tp_compare */\r
    (reprfunc)set_repr,                 /* tp_repr */\r
    &frozenset_as_number,               /* tp_as_number */\r
    &set_as_sequence,                   /* tp_as_sequence */\r
    0,                                  /* tp_as_mapping */\r
    frozenset_hash,                     /* tp_hash */\r
    0,                                  /* tp_call */\r
    0,                                  /* tp_str */\r
    PyObject_GenericGetAttr,            /* tp_getattro */\r
    0,                                  /* tp_setattro */\r
    0,                                  /* tp_as_buffer */\r
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_CHECKTYPES |\r
        Py_TPFLAGS_BASETYPE,            /* tp_flags */\r
    frozenset_doc,                      /* tp_doc */\r
    (traverseproc)set_traverse,         /* tp_traverse */\r
    (inquiry)set_clear_internal,        /* tp_clear */\r
    (richcmpfunc)set_richcompare,       /* tp_richcompare */\r
    offsetof(PySetObject, weakreflist),         /* tp_weaklistoffset */\r
    (getiterfunc)set_iter,              /* tp_iter */\r
    0,                                  /* tp_iternext */\r
    frozenset_methods,                  /* tp_methods */\r
    0,                                  /* tp_members */\r
    0,                                  /* tp_getset */\r
    0,                                  /* tp_base */\r
    0,                                  /* tp_dict */\r
    0,                                  /* tp_descr_get */\r
    0,                                  /* tp_descr_set */\r
    0,                                  /* tp_dictoffset */\r
    0,                                  /* tp_init */\r
    PyType_GenericAlloc,                /* tp_alloc */\r
    frozenset_new,                      /* tp_new */\r
    PyObject_GC_Del,                    /* tp_free */\r
};\r
\r
\r
/***** C API functions *************************************************/\r
\r
PyObject *\r
PySet_New(PyObject *iterable)\r
{\r
    return make_new_set(&PySet_Type, iterable);\r
}\r
\r
PyObject *\r
PyFrozenSet_New(PyObject *iterable)\r
{\r
    return make_new_set(&PyFrozenSet_Type, iterable);\r
}\r
\r
Py_ssize_t\r
PySet_Size(PyObject *anyset)\r
{\r
    if (!PyAnySet_Check(anyset)) {\r
        PyErr_BadInternalCall();\r
        return -1;\r
    }\r
    return PySet_GET_SIZE(anyset);\r
}\r
\r
int\r
PySet_Clear(PyObject *set)\r
{\r
    if (!PySet_Check(set)) {\r
        PyErr_BadInternalCall();\r
        return -1;\r
    }\r
    return set_clear_internal((PySetObject *)set);\r
}\r
\r
int\r
PySet_Contains(PyObject *anyset, PyObject *key)\r
{\r
    if (!PyAnySet_Check(anyset)) {\r
        PyErr_BadInternalCall();\r
        return -1;\r
    }\r
    return set_contains_key((PySetObject *)anyset, key);\r
}\r
\r
int\r
PySet_Discard(PyObject *set, PyObject *key)\r
{\r
    if (!PySet_Check(set)) {\r
        PyErr_BadInternalCall();\r
        return -1;\r
    }\r
    return set_discard_key((PySetObject *)set, key);\r
}\r
\r
int\r
PySet_Add(PyObject *anyset, PyObject *key)\r
{\r
    if (!PySet_Check(anyset) &&\r
        (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {\r
        PyErr_BadInternalCall();\r
        return -1;\r
    }\r
    return set_add_key((PySetObject *)anyset, key);\r
}\r
\r
int\r
_PySet_Next(PyObject *set, Py_ssize_t *pos, PyObject **key)\r
{\r
    setentry *entry_ptr;\r
\r
    if (!PyAnySet_Check(set)) {\r
        PyErr_BadInternalCall();\r
        return -1;\r
    }\r
    if (set_next((PySetObject *)set, pos, &entry_ptr) == 0)\r
        return 0;\r
    *key = entry_ptr->key;\r
    return 1;\r
}\r
\r
int\r
_PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, long *hash)\r
{\r
    setentry *entry;\r
\r
    if (!PyAnySet_Check(set)) {\r
        PyErr_BadInternalCall();\r
        return -1;\r
    }\r
    if (set_next((PySetObject *)set, pos, &entry) == 0)\r
        return 0;\r
    *key = entry->key;\r
    *hash = entry->hash;\r
    return 1;\r
}\r
\r
PyObject *\r
PySet_Pop(PyObject *set)\r
{\r
    if (!PySet_Check(set)) {\r
        PyErr_BadInternalCall();\r
        return NULL;\r
    }\r
    return set_pop((PySetObject *)set);\r
}\r
\r
int\r
_PySet_Update(PyObject *set, PyObject *iterable)\r
{\r
    if (!PySet_Check(set)) {\r
        PyErr_BadInternalCall();\r
        return -1;\r
    }\r
    return set_update_internal((PySetObject *)set, iterable);\r
}\r
\r
#ifdef Py_DEBUG\r
\r
/* Test code to be called with any three element set.\r
   Returns True and original set is restored. */\r
\r
#define assertRaises(call_return_value, exception)              \\r
    do {                                                        \\r
        assert(call_return_value);                              \\r
        assert(PyErr_ExceptionMatches(exception));              \\r
        PyErr_Clear();                                          \\r
    } while(0)\r
\r
static PyObject *\r
test_c_api(PySetObject *so)\r
{\r
    Py_ssize_t count;\r
    char *s;\r
    Py_ssize_t i;\r
    PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x;\r
    PyObject *ob = (PyObject *)so;\r
    PyObject *str;\r
\r
    /* Verify preconditions */\r
    assert(PyAnySet_Check(ob));\r
    assert(PyAnySet_CheckExact(ob));\r
    assert(!PyFrozenSet_CheckExact(ob));\r
\r
    /* so.clear(); so |= set("abc"); */\r
    str = PyString_FromString("abc");\r
    if (str == NULL)\r
        return NULL;\r
    set_clear_internal(so);\r
    if (set_update_internal(so, str) == -1) {\r
        Py_DECREF(str);\r
        return NULL;\r
    }\r
    Py_DECREF(str);\r
\r
    /* Exercise type/size checks */\r
    assert(PySet_Size(ob) == 3);\r
    assert(PySet_GET_SIZE(ob) == 3);\r
\r
    /* Raise TypeError for non-iterable constructor arguments */\r
    assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);\r
    assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);\r
\r
    /* Raise TypeError for unhashable key */\r
    dup = PySet_New(ob);\r
    assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);\r
    assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);\r
    assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);\r
\r
    /* Exercise successful pop, contains, add, and discard */\r
    elem = PySet_Pop(ob);\r
    assert(PySet_Contains(ob, elem) == 0);\r
    assert(PySet_GET_SIZE(ob) == 2);\r
    assert(PySet_Add(ob, elem) == 0);\r
    assert(PySet_Contains(ob, elem) == 1);\r
    assert(PySet_GET_SIZE(ob) == 3);\r
    assert(PySet_Discard(ob, elem) == 1);\r
    assert(PySet_GET_SIZE(ob) == 2);\r
    assert(PySet_Discard(ob, elem) == 0);\r
    assert(PySet_GET_SIZE(ob) == 2);\r
\r
    /* Exercise clear */\r
    dup2 = PySet_New(dup);\r
    assert(PySet_Clear(dup2) == 0);\r
    assert(PySet_Size(dup2) == 0);\r
    Py_DECREF(dup2);\r
\r
    /* Raise SystemError on clear or update of frozen set */\r
    f = PyFrozenSet_New(dup);\r
    assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);\r
    assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);\r
    assert(PySet_Add(f, elem) == 0);\r
    Py_INCREF(f);\r
    assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);\r
    Py_DECREF(f);\r
    Py_DECREF(f);\r
\r
    /* Exercise direct iteration */\r
    i = 0, count = 0;\r
    while (_PySet_Next((PyObject *)dup, &i, &x)) {\r
        s = PyString_AsString(x);\r
        assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));\r
        count++;\r
    }\r
    assert(count == 3);\r
\r
    /* Exercise updates */\r
    dup2 = PySet_New(NULL);\r
    assert(_PySet_Update(dup2, dup) == 0);\r
    assert(PySet_Size(dup2) == 3);\r
    assert(_PySet_Update(dup2, dup) == 0);\r
    assert(PySet_Size(dup2) == 3);\r
    Py_DECREF(dup2);\r
\r
    /* Raise SystemError when self argument is not a set or frozenset. */\r
    t = PyTuple_New(0);\r
    assertRaises(PySet_Size(t) == -1, PyExc_SystemError);\r
    assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);\r
    Py_DECREF(t);\r
\r
    /* Raise SystemError when self argument is not a set. */\r
    f = PyFrozenSet_New(dup);\r
    assert(PySet_Size(f) == 3);\r
    assert(PyFrozenSet_CheckExact(f));\r
    assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);\r
    assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);\r
    Py_DECREF(f);\r
\r
    /* Raise KeyError when popping from an empty set */\r
    assert(PyNumber_InPlaceSubtract(ob, ob) == ob);\r
    Py_DECREF(ob);\r
    assert(PySet_GET_SIZE(ob) == 0);\r
    assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);\r
\r
    /* Restore the set from the copy using the PyNumber API */\r
    assert(PyNumber_InPlaceOr(ob, dup) == ob);\r
    Py_DECREF(ob);\r
\r
    /* Verify constructors accept NULL arguments */\r
    f = PySet_New(NULL);\r
    assert(f != NULL);\r
    assert(PySet_GET_SIZE(f) == 0);\r
    Py_DECREF(f);\r
    f = PyFrozenSet_New(NULL);\r
    assert(f != NULL);\r
    assert(PyFrozenSet_CheckExact(f));\r
    assert(PySet_GET_SIZE(f) == 0);\r
    Py_DECREF(f);\r
\r
    Py_DECREF(elem);\r
    Py_DECREF(dup);\r
    Py_RETURN_TRUE;\r
}\r
\r
#undef assertRaises\r
\r
#endif\r