setobject.c

/* set object implementation

 Written and maintained by Raymond D. Hettinger <python@rcn.com>
 Derived from Objects/dictobject.c.

 The basic lookup function used by all operations.
 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.

 The initial probe index is computed as hash mod the table size.
 Subsequent probe indices are computed as explained in Objects/dictobject.c.

 To improve cache locality, each probe inspects a series of consecutive
 nearby entries before moving on to probes elsewhere in memory. This leaves
 us with a hybrid of linear probing and randomized probing. The linear probing
 reduces the cost of hash collisions because consecutive memory accesses
 tend to be much cheaper than scattered probes. After LINEAR_PROBES steps,
 we then use more of the upper bits from the hash value and apply a simple
 linear congruential random number generator. This helps break-up long
 chains of collisions.

 All arithmetic on hash should ignore overflow.

 Unlike the dictionary implementation, the lookkey function can return
 NULL if the rich comparison returns an error.

 Use cases for sets differ considerably from dictionaries where looked-up
 keys are more likely to be present. In contrast, sets are primarily
 about membership testing where the presence of an element is not known in
 advance. Accordingly, the set implementation needs to optimize for both
 the found and not-found case.
*/

#include"Python.h"
#include"pycore_ceval.h"// _PyEval_GetBuiltin()
#include"pycore_critical_section.h"// Py_BEGIN_CRITICAL_SECTION, Py_END_CRITICAL_SECTION
#include"pycore_dict.h"// _PyDict_Contains_KnownHash()
#include"pycore_modsupport.h"// _PyArg_NoKwnames()
#include"pycore_object.h"// _PyObject_GC_UNTRACK()
#include"pycore_pyatomic_ft_wrappers.h"// FT_ATOMIC_LOAD_SSIZE_RELAXED()
#include"pycore_pyerrors.h"// _PyErr_SetKeyError()
#include"pycore_setobject.h"// _PySet_NextEntry() definition
#include<stddef.h>// offsetof()
#include"clinic/setobject.c.h"

/*[clinic input]
class set "PySetObject *" "&PySet_Type"
class frozenset "PySetObject *" "&PyFrozenSet_Type"
[clinic start generated code]*/
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=97ad1d3e9f117079]*/

/*[python input]
class setobject_converter(self_converter):
 type = "PySetObject *"
[python start generated code]*/
/*[python end generated code: output=da39a3ee5e6b4b0d input=33a44506d4d57793]*/

/* Object used as dummy key to fill deleted entries */
staticPyObject_dummy_struct;

#definedummy (&_dummy_struct)


/* ======================================================================== */
/* ======= Begin logic for probing the hash table ========================= */

/* Set this to zero to turn-off linear probing */
#ifndefLINEAR_PROBES
#defineLINEAR_PROBES 9
#endif

/* This must be >= 1 */
#definePERTURB_SHIFT 5

staticsetentry*
set_lookkey(PySetObject*so, PyObject*key, Py_hash_thash)
{
setentry*table;
setentry*entry;
size_tperturb=hash;
size_tmask=so->mask;
size_ti= (size_t)hash&mask; /* Unsigned for defined overflow behavior */
intprobes;
intcmp;

while (1) {
entry=&so->table[i];
probes= (i+LINEAR_PROBES <= mask) ? LINEAR_PROBES: 0;
do {
if (entry->hash==0&&entry->key==NULL)
returnentry;
if (entry->hash==hash) {
PyObject*startkey=entry->key;
assert(startkey!=dummy);
if (startkey==key)
returnentry;
if (PyUnicode_CheckExact(startkey)
&&PyUnicode_CheckExact(key)
&&_PyUnicode_EQ(startkey, key))
returnentry;
table=so->table;
Py_INCREF(startkey);
cmp=PyObject_RichCompareBool(startkey, key, Py_EQ);
Py_DECREF(startkey);
if (cmp<0)
returnNULL;
if (table!=so->table||entry->key!=startkey)
returnset_lookkey(so, key, hash);
if (cmp>0)
returnentry;
mask=so->mask;
 }
entry++;
 } while (probes--);
perturb >>= PERTURB_SHIFT;
i= (i*5+1+perturb) &mask;
 }
}

staticintset_table_resize(PySetObject*, Py_ssize_t);

staticint
set_add_entry(PySetObject*so, PyObject*key, Py_hash_thash)
{
setentry*table;
setentry*freeslot;
setentry*entry;
size_tperturb;
size_tmask;
size_ti; /* Unsigned for defined overflow behavior */
intprobes;
intcmp;

_Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(so);

/* Pre-increment is necessary to prevent arbitrary code in the rich
 comparison from deallocating the key just before the insertion. */
Py_INCREF(key);

restart:

mask=so->mask;
i= (size_t)hash&mask;
freeslot=NULL;
perturb=hash;

while (1) {
entry=&so->table[i];
probes= (i+LINEAR_PROBES <= mask) ? LINEAR_PROBES: 0;
do {
if (entry->hash==0&&entry->key==NULL)
 goto found_unused_or_dummy;
if (entry->hash==hash) {
PyObject*startkey=entry->key;
assert(startkey!=dummy);
if (startkey==key)
 goto found_active;
if (PyUnicode_CheckExact(startkey)
&&PyUnicode_CheckExact(key)
&&_PyUnicode_EQ(startkey, key))
 goto found_active;
table=so->table;
Py_INCREF(startkey);
cmp=PyObject_RichCompareBool(startkey, key, Py_EQ);
Py_DECREF(startkey);
if (cmp>0)
 goto found_active;
if (cmp<0)
 goto comparison_error;
if (table!=so->table||entry->key!=startkey)
 goto restart;
mask=so->mask;
 }
elseif (entry->hash==-1) {
assert (entry->key==dummy);
freeslot=entry;
 }
entry++;
 } while (probes--);
perturb >>= PERTURB_SHIFT;
i= (i*5+1+perturb) &mask;
 }

found_unused_or_dummy:
if (freeslot==NULL)
 goto found_unused;
FT_ATOMIC_STORE_SSIZE_RELAXED(so->used, so->used+1);
freeslot->key=key;
freeslot->hash=hash;
return0;

found_unused:
so->fill++;
FT_ATOMIC_STORE_SSIZE_RELAXED(so->used, so->used+1);
entry->key=key;
entry->hash=hash;
if ((size_t)so->fill*5<mask*3)
return0;
returnset_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);

found_active:
Py_DECREF(key);
return0;

comparison_error:
Py_DECREF(key);
return-1;
}

/*
Internal routine used by set_table_resize() to insert an item which is
known to be absent from the set. Besides the performance benefit,
there is also safety benefit since using set_add_entry() risks making
a callback in the middle of a set_table_resize(), see issue 1456209.
The caller is responsible for updating the key's reference count and
the setobject's fill and used fields.
*/
staticvoid
set_insert_clean(setentry*table, size_tmask, PyObject*key, Py_hash_thash)
{
setentry*entry;
size_tperturb=hash;
size_ti= (size_t)hash&mask;
size_tj;

while (1) {
entry=&table[i];
if (entry->key==NULL)
 goto found_null;
if (i+LINEAR_PROBES <= mask) {
for (j=0; j<LINEAR_PROBES; j++) {
entry++;
if (entry->key==NULL)
 goto found_null;
 }
 }
perturb >>= PERTURB_SHIFT;
i= (i*5+1+perturb) &mask;
 }
found_null:
entry->key=key;
entry->hash=hash;
}

/* ======== End logic for probing the hash table ========================== */
/* ======================================================================== */

/*
Restructure the table by allocating a new table and reinserting all
keys again. When entries have been deleted, the new table may
actually be smaller than the old one.
*/
staticint
set_table_resize(PySetObject*so, Py_ssize_tminused)
{
setentry*oldtable, *newtable, *entry;
Py_ssize_toldmask=so->mask;
size_tnewmask;
intis_oldtable_malloced;
setentrysmall_copy[PySet_MINSIZE];

assert(minused >= 0);

/* Find the smallest table size > minused. */
/* XXX speed-up with intrinsics */
size_tnewsize=PySet_MINSIZE;
while (newsize <= (size_t)minused) {
newsize <<= 1; // The largest possible value is PY_SSIZE_T_MAX + 1.
 }

/* Get space for a new table. */
oldtable=so->table;
assert(oldtable!=NULL);
is_oldtable_malloced=oldtable!=so->smalltable;

if (newsize==PySet_MINSIZE) {
/* A large table is shrinking, or we can't get any smaller. */
newtable=so->smalltable;
if (newtable==oldtable) {
if (so->fill==so->used) {
/* No dummies, so no point doing anything. */
return0;
 }
/* We're not going to resize it, but rebuild the
 table anyway to purge old dummy entries.
 Subtle: This is *necessary* if fill==size,
 as set_lookkey needs at least one virgin slot to
 terminate failing searches. If fill < size, it's
 merely desirable, as dummies slow searches. */
assert(so->fill>so->used);
memcpy(small_copy, oldtable, sizeof(small_copy));
oldtable=small_copy;
 }
 }
else {
newtable=PyMem_NEW(setentry, newsize);
if (newtable==NULL) {
PyErr_NoMemory();
return-1;
 }
 }

/* Make the set empty, using the new table. */
assert(newtable!=oldtable);
memset(newtable, 0, sizeof(setentry) *newsize);
so->mask=newsize-1;
so->table=newtable;

/* Copy the data over; this is refcount-neutral for active entries;
 dummy entries aren't copied over, of course */
newmask= (size_t)so->mask;
if (so->fill==so->used) {
for (entry=oldtable; entry <= oldtable+oldmask; entry++) {
if (entry->key!=NULL) {
set_insert_clean(newtable, newmask, entry->key, entry->hash);
 }
 }
 } else {
so->fill=so->used;
for (entry=oldtable; entry <= oldtable+oldmask; entry++) {
if (entry->key!=NULL&&entry->key!=dummy) {
set_insert_clean(newtable, newmask, entry->key, entry->hash);
 }
 }
 }

if (is_oldtable_malloced)
PyMem_Free(oldtable);
return0;
}

staticint
set_contains_entry(PySetObject*so, PyObject*key, Py_hash_thash)
{
setentry*entry;

entry=set_lookkey(so, key, hash);
if (entry!=NULL)
returnentry->key!=NULL;
return-1;
}

#defineDISCARD_NOTFOUND 0
#defineDISCARD_FOUND 1

staticint
set_discard_entry(PySetObject*so, PyObject*key, Py_hash_thash)
{
setentry*entry;
PyObject*old_key;

entry=set_lookkey(so, key, hash);
if (entry==NULL)
return-1;
if (entry->key==NULL)
returnDISCARD_NOTFOUND;
old_key=entry->key;
entry->key=dummy;
entry->hash=-1;
FT_ATOMIC_STORE_SSIZE_RELAXED(so->used, so->used-1);
Py_DECREF(old_key);
returnDISCARD_FOUND;
}

staticint
set_add_key(PySetObject*so, PyObject*key)
{
Py_hash_thash=_PyObject_HashFast(key);
if (hash==-1) {
return-1;
 }
returnset_add_entry(so, key, hash);
}

staticint
set_contains_key(PySetObject*so, PyObject*key)
{
Py_hash_thash=_PyObject_HashFast(key);
if (hash==-1) {
return-1;
 }
returnset_contains_entry(so, key, hash);
}

staticint
set_discard_key(PySetObject*so, PyObject*key)
{
Py_hash_thash=_PyObject_HashFast(key);
if (hash==-1) {
return-1;
 }
returnset_discard_entry(so, key, hash);
}

staticvoid
set_empty_to_minsize(PySetObject*so)
{
memset(so->smalltable, 0, sizeof(so->smalltable));
so->fill=0;
FT_ATOMIC_STORE_SSIZE_RELAXED(so->used, 0);
so->mask=PySet_MINSIZE-1;
so->table=so->smalltable;
FT_ATOMIC_STORE_SSIZE_RELAXED(so->hash, -1);
}

staticint
set_clear_internal(PySetObject*so)
{
setentry*entry;
setentry*table=so->table;
Py_ssize_tfill=so->fill;
Py_ssize_tused=so->used;
inttable_is_malloced=table!=so->smalltable;
setentrysmall_copy[PySet_MINSIZE];

assert (PyAnySet_Check(so));
assert(table!=NULL);

/* This is delicate. During the process of clearing the set,
 * decrefs can cause the set to mutate. To avoid fatal confusion
 * (voice of experience), we have to make the set empty before
 * clearing the slots, and never refer to anything via so->ref while
 * clearing.
 */
if (table_is_malloced)
set_empty_to_minsize(so);

elseif (fill>0) {
/* It's a small table with something that needs to be cleared.
 * Afraid the only safe way is to copy the set entries into
 * another small table first.
 */
memcpy(small_copy, table, sizeof(small_copy));
table=small_copy;
set_empty_to_minsize(so);
 }
/* else it's a small table that's already empty */

/* Now we can finally clear things. If C had refcounts, we could
 * assert that the refcount on table is 1 now, i.e. that this function
 * has unique access to it, so decref side-effects can't alter it.
 */
for (entry=table; used>0; entry++) {
if (entry->key&&entry->key!=dummy) {
used--;
Py_DECREF(entry->key);
 }
 }

if (table_is_malloced)
PyMem_Free(table);
return0;
}

/*
 * Iterate over a set table. Use like so:
 *
 * Py_ssize_t pos;
 * setentry *entry;
 * pos = 0; # important! pos should not otherwise be changed by you
 * while (set_next(yourset, &pos, &entry)) {
 * Refer to borrowed reference in entry->key.
 * }
 *
 * CAUTION: In general, it isn't safe to use set_next in a loop that
 * mutates the table.
 */
staticint
set_next(PySetObject*so, Py_ssize_t*pos_ptr, setentry**entry_ptr)
{
Py_ssize_ti;
Py_ssize_tmask;
setentry*entry;

assert (PyAnySet_Check(so));
i=*pos_ptr;
assert(i >= 0);
mask=so->mask;
entry=&so->table[i];
while (i <= mask&& (entry->key==NULL||entry->key==dummy)) {
i++;
entry++;
 }
*pos_ptr=i+1;
if (i>mask)
return0;
assert(entry!=NULL);
*entry_ptr=entry;
return1;
}

staticvoid
set_dealloc(PySetObject*so)
{
setentry*entry;
Py_ssize_tused=so->used;

/* bpo-31095: UnTrack is needed before calling any callbacks */
PyObject_GC_UnTrack(so);
Py_TRASHCAN_BEGIN(so, set_dealloc)
if (so->weakreflist!=NULL)
PyObject_ClearWeakRefs((PyObject*) so);

for (entry=so->table; used>0; entry++) {
if (entry->key&&entry->key!=dummy) {
used--;
Py_DECREF(entry->key);
 }
 }
if (so->table!=so->smalltable)
PyMem_Free(so->table);
Py_TYPE(so)->tp_free(so);
Py_TRASHCAN_END
}

staticPyObject*
set_repr_lock_held(PySetObject*so)
{
PyObject*result=NULL, *keys, *listrepr, *tmp;
intstatus=Py_ReprEnter((PyObject*)so);

if (status!=0) {
if (status<0)
returnNULL;
returnPyUnicode_FromFormat("%s(...)", Py_TYPE(so)->tp_name);
 }

/* shortcut for the empty set */
if (!so->used) {
Py_ReprLeave((PyObject*)so);
returnPyUnicode_FromFormat("%s()", Py_TYPE(so)->tp_name);
 }

// gh-129967: avoid PySequence_List because it might re-lock the object
// lock or the GIL and allow something to clear the set from underneath us.
keys=PyList_New(so->used);
if (keys==NULL) {
 goto done;
 }

Py_ssize_tpos=0, idx=0;
setentry*entry;
while (set_next(so, &pos, &entry)) {
PyList_SET_ITEM(keys, idx++, Py_NewRef(entry->key));
 }

/* repr(keys)[1:-1] */
listrepr=PyObject_Repr(keys);
Py_DECREF(keys);
if (listrepr==NULL)
 goto done;
tmp=PyUnicode_Substring(listrepr, 1, PyUnicode_GET_LENGTH(listrepr)-1);
Py_DECREF(listrepr);
if (tmp==NULL)
 goto done;
listrepr=tmp;

if (!PySet_CheckExact(so))
result=PyUnicode_FromFormat("%s({%U})",
Py_TYPE(so)->tp_name,
listrepr);
else
result=PyUnicode_FromFormat("{%U}", listrepr);
Py_DECREF(listrepr);
done:
Py_ReprLeave((PyObject*)so);
returnresult;
}

staticPyObject*
set_repr(PySetObject*so)
{
PyObject*result;
Py_BEGIN_CRITICAL_SECTION(so);
result=set_repr_lock_held(so);
Py_END_CRITICAL_SECTION();
returnresult;
}

staticPy_ssize_t
set_len(PySetObject*so)
{
returnFT_ATOMIC_LOAD_SSIZE_RELAXED(so->used);
}

staticint
set_merge_lock_held(PySetObject*so, PyObject*otherset)
{
PySetObject*other;
PyObject*key;
Py_ssize_ti;
setentry*so_entry;
setentry*other_entry;

assert (PyAnySet_Check(so));
assert (PyAnySet_Check(otherset));
_Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(so);
_Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(otherset);

other= (PySetObject*)otherset;
if (other==so||other->used==0)
/* a.update(a) or a.update(set()); nothing to do */
return0;
/* Do one big resize at the start, rather than
 * incrementally resizing as we insert new keys. Expect
 * that there will be no (or few) overlapping keys.
 */
if ((so->fill+other->used)*5 >= so->mask*3) {
if (set_table_resize(so, (so->used+other->used)*2) !=0)
return-1;
 }
so_entry=so->table;
other_entry=other->table;

/* If our table is empty, and both tables have the same size, and
 there are no dummies to eliminate, then just copy the pointers. */
if (so->fill==0&&so->mask==other->mask&&other->fill==other->used) {
for (i=0; i <= other->mask; i++, so_entry++, other_entry++) {
key=other_entry->key;
if (key!=NULL) {
assert(so_entry->key==NULL);
so_entry->key=Py_NewRef(key);
so_entry->hash=other_entry->hash;
 }
 }
so->fill=other->fill;
FT_ATOMIC_STORE_SSIZE_RELAXED(so->used, other->used);
return0;
 }

/* If our table is empty, we can use set_insert_clean() */
if (so->fill==0) {
setentry*newtable=so->table;
size_tnewmask= (size_t)so->mask;
so->fill=other->used;
FT_ATOMIC_STORE_SSIZE_RELAXED(so->used, other->used);
for (i=other->mask+1; i>0 ; i--, other_entry++) {
key=other_entry->key;
if (key!=NULL&&key!=dummy) {
set_insert_clean(newtable, newmask, Py_NewRef(key),
other_entry->hash);
 }
 }
return0;
 }

/* We can't assure there are no duplicates, so do normal insertions */
for (i=0; i <= other->mask; i++) {
other_entry=&other->table[i];
key=other_entry->key;
if (key!=NULL&&key!=dummy) {
if (set_add_entry(so, key, other_entry->hash))
return-1;
 }
 }
return0;
}

/*[clinic input]
@critical_section
set.pop
 so: setobject

Remove and return an arbitrary set element.

Raises KeyError if the set is empty.
[clinic start generated code]*/

staticPyObject*
set_pop_impl(PySetObject*so)
/*[clinic end generated code: output=4d65180f1271871b input=9296c84921125060]*/
{
/* Make sure the search finger is in bounds */
setentry*entry=so->table+ (so->finger&so->mask);
setentry*limit=so->table+so->mask;
PyObject*key;

if (so->used==0) {
PyErr_SetString(PyExc_KeyError, "pop from an empty set");
returnNULL;
 }
while (entry->key==NULL||entry->key==dummy) {
entry++;
if (entry>limit)
entry=so->table;
 }
key=entry->key;
entry->key=dummy;
entry->hash=-1;
FT_ATOMIC_STORE_SSIZE_RELAXED(so->used, so->used-1);
so->finger=entry-so->table+1; /* next place to start */
returnkey;
}

staticint
set_traverse(PySetObject*so, visitprocvisit, void*arg)
{
Py_ssize_tpos=0;
setentry*entry;

while (set_next(so, &pos, &entry))
Py_VISIT(entry->key);
return0;
}

/* Work to increase the bit dispersion for closely spaced hash values.
 This is important because some use cases have many combinations of a
 small number of elements with nearby hashes so that many distinct
 combinations collapse to only a handful of distinct hash values. */

staticPy_uhash_t
_shuffle_bits(Py_uhash_th)
{
return ((h ^ 89869747UL) ^ (h << 16)) *3644798167UL;
}

/* Most of the constants in this hash algorithm are randomly chosen
 large primes with "interesting bit patterns" and that passed tests
 for good collision statistics on a variety of problematic datasets
 including powersets and graph structures (such as David Eppstein's
 graph recipes in Lib/test/test_set.py). */

staticPy_hash_t
frozenset_hash_impl(PyObject*self)
{
PySetObject*so=_PySet_CAST(self);
Py_uhash_thash=0;
setentry*entry;

/* Xor-in shuffled bits from every entry's hash field because xor is
 commutative and a frozenset hash should be independent of order.

 For speed, include null entries and dummy entries and then
 subtract out their effect afterwards so that the final hash
 depends only on active entries. This allows the code to be
 vectorized by the compiler and it saves the unpredictable
 branches that would arise when trying to exclude null and dummy
 entries on every iteration. */

for (entry=so->table; entry <= &so->table[so->mask]; entry++)
hash ^= _shuffle_bits(entry->hash);

/* Remove the effect of an odd number of NULL entries */
if ((so->mask+1-so->fill) &1)
hash ^= _shuffle_bits(0);

/* Remove the effect of an odd number of dummy entries */
if ((so->fill-so->used) &1)
hash ^= _shuffle_bits(-1);

/* Factor in the number of active entries */
hash ^= ((Py_uhash_t)PySet_GET_SIZE(self) +1) *1927868237UL;

/* Disperse patterns arising in nested frozensets */
hash ^= (hash >> 11) ^ (hash >> 25);
hash=hash*69069U+907133923UL;

/* -1 is reserved as an error code */
if (hash== (Py_uhash_t)-1)
hash=590923713UL;

return (Py_hash_t)hash;
}

staticPy_hash_t
frozenset_hash(PyObject*self)
{
PySetObject*so=_PySet_CAST(self);
Py_uhash_thash;

if (FT_ATOMIC_LOAD_SSIZE_RELAXED(so->hash) !=-1) {
returnFT_ATOMIC_LOAD_SSIZE_RELAXED(so->hash);
 }

hash=frozenset_hash_impl(self);
FT_ATOMIC_STORE_SSIZE_RELAXED(so->hash, hash);
returnhash;
}

/***** Set iterator type ***********************************************/

typedefstruct {
PyObject_HEAD
PySetObject*si_set; /* Set to NULL when iterator is exhausted */
Py_ssize_tsi_used;
Py_ssize_tsi_pos;
Py_ssize_tlen;
} setiterobject;

staticvoid
setiter_dealloc(setiterobject*si)
{
/* bpo-31095: UnTrack is needed before calling any callbacks */
_PyObject_GC_UNTRACK(si);
Py_XDECREF(si->si_set);
PyObject_GC_Del(si);
}

staticint
setiter_traverse(setiterobject*si, visitprocvisit, void*arg)
{
Py_VISIT(si->si_set);
return0;
}

staticPyObject*
setiter_len(setiterobject*si, PyObject*Py_UNUSED(ignored))
{
Py_ssize_tlen=0;
if (si->si_set!=NULL&&si->si_used==si->si_set->used)
len=si->len;
returnPyLong_FromSsize_t(len);
}

PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");

staticPyObject*setiter_iternext(setiterobject*si);

staticPyObject*
setiter_reduce(setiterobject*si, PyObject*Py_UNUSED(ignored))
{
/* copy the iterator state */
setiterobjecttmp=*si;
Py_XINCREF(tmp.si_set);

/* iterate the temporary into a list */
PyObject*list=PySequence_List((PyObject*)&tmp);
Py_XDECREF(tmp.si_set);
if (list==NULL) {
returnNULL;
 }
returnPy_BuildValue("N(N)", _PyEval_GetBuiltin(&_Py_ID(iter)), list);
}

PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");

staticPyMethodDefsetiter_methods[] = {
 {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
 {"__reduce__", (PyCFunction)setiter_reduce, METH_NOARGS, reduce_doc},
 {NULL, NULL} /* sentinel */
};

staticPyObject*setiter_iternext(setiterobject*si)
{
PyObject*key=NULL;
Py_ssize_ti, mask;
setentry*entry;
PySetObject*so=si->si_set;

if (so==NULL)
returnNULL;
assert (PyAnySet_Check(so));

Py_ssize_tso_used=FT_ATOMIC_LOAD_SSIZE(so->used);
Py_ssize_tsi_used=FT_ATOMIC_LOAD_SSIZE(si->si_used);
if (si_used!=so_used) {
PyErr_SetString(PyExc_RuntimeError,
"Set changed size during iteration");
si->si_used=-1; /* Make this state sticky */
returnNULL;
 }

Py_BEGIN_CRITICAL_SECTION(so);
i=si->si_pos;
assert(i>=0);
entry=so->table;
mask=so->mask;
while (i <= mask&& (entry[i].key==NULL||entry[i].key==dummy)) {
i++;
 }
if (i <= mask) {
key=Py_NewRef(entry[i].key);
 }
Py_END_CRITICAL_SECTION();
si->si_pos=i+1;
if (key==NULL) {
si->si_set=NULL;
Py_DECREF(so);
returnNULL;
 }
si->len--;
returnkey;
}

PyTypeObjectPySetIter_Type= {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"set_iterator", /* tp_name */
sizeof(setiterobject), /* tp_basicsize */
0, /* tp_itemsize */
/* methods */
 (destructor)setiter_dealloc, /* tp_dealloc */
0, /* tp_vectorcall_offset */
0, /* tp_getattr */
0, /* tp_setattr */
0, /* tp_as_async */
0, /* tp_repr */
0, /* tp_as_number */
0, /* tp_as_sequence */
0, /* tp_as_mapping */
0, /* tp_hash */
0, /* tp_call */
0, /* tp_str */
PyObject_GenericGetAttr, /* tp_getattro */
0, /* tp_setattro */
0, /* tp_as_buffer */
Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
0, /* tp_doc */
 (traverseproc)setiter_traverse, /* tp_traverse */
0, /* tp_clear */
0, /* tp_richcompare */
0, /* tp_weaklistoffset */
PyObject_SelfIter, /* tp_iter */
 (iternextfunc)setiter_iternext, /* tp_iternext */
setiter_methods, /* tp_methods */
0,
};

staticPyObject*
set_iter(PySetObject*so)
{
Py_ssize_tsize=set_len(so);
setiterobject*si=PyObject_GC_New(setiterobject, &PySetIter_Type);
if (si==NULL)
returnNULL;
si->si_set= (PySetObject*)Py_NewRef(so);
si->si_used=size;
si->si_pos=0;
si->len=size;
_PyObject_GC_TRACK(si);
return (PyObject*)si;
}

staticint
set_update_dict_lock_held(PySetObject*so, PyObject*other)
{
assert(PyDict_CheckExact(other));

_Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(so);
_Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(other);

/* Do one big resize at the start, rather than
 * incrementally resizing as we insert new keys. Expect
 * that there will be no (or few) overlapping keys.
 */
Py_ssize_tdictsize=PyDict_GET_SIZE(other);
if ((so->fill+dictsize)*5 >= so->mask*3) {
if (set_table_resize(so, (so->used+dictsize)*2) !=0) {
return-1;
 }
 }

Py_ssize_tpos=0;
PyObject*key;
PyObject*value;
Py_hash_thash;
while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
if (set_add_entry(so, key, hash)) {
return-1;
 }
 }
return0;
}

staticint
set_update_iterable_lock_held(PySetObject*so, PyObject*other)
{
_Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(so);

PyObject*it=PyObject_GetIter(other);
if (it==NULL) {
return-1;
 }

PyObject*key;
while ((key=PyIter_Next(it)) !=NULL) {
if (set_add_key(so, key)) {
Py_DECREF(it);
Py_DECREF(key);
return-1;
 }
Py_DECREF(key);
 }
Py_DECREF(it);
if (PyErr_Occurred())
return-1;
return0;
}

staticint
set_update_lock_held(PySetObject*so, PyObject*other)
{
if (PyAnySet_Check(other)) {
returnset_merge_lock_held(so, other);
 }
elseif (PyDict_CheckExact(other)) {
returnset_update_dict_lock_held(so, other);
 }
returnset_update_iterable_lock_held(so, other);
}