<commit_before>
/* set object implementation 
   Written and maintained by <NAME> <<EMAIL>>
   Derived from Lib/sets.py and Objects/dictobject.c.

   Copyright (c) 2003-2007 Python Software Foundation.
   All rights reserved.
*/

#include "Python.h"
#include "structmember.h"

/* Set a key error with the specified argument, wrapping it in a
 * tuple automatically so that tuple keys are not unpacked as the
 * exception arguments. */
static void
set_key_error(PyObject *arg)
{
	PyObject *tup;
	tup = PyTuple_Pack(1, arg);
	if (!tup)
		return; /* caller will expect error to be set anyway */
	PyErr_SetObject(PyExc_KeyError, tup);
	Py_DECREF(tup);
}

/* This must be >= 1. */
#define PERTURB_SHIFT 5

/* Object used as dummy key to fill deleted entries */
static PyObject *dummy = NULL; /* Initialized by first call to make_new_set() */

#ifdef Py_REF_DEBUG
PyObject *
_PySet_Dummy(void)
{
	return dummy;
}
#endif

#define INIT_NONZERO_SET_SLOTS(so) do {				\
	(so)->table = (so)->smalltable;				\
	(so)->mask = PySet_MINSIZE - 1;				\
	(so)->hash = -1;					\
    } while(0)

#define EMPTY_TO_MINSIZE(so) do {				\
	memset((so)->smalltable, 0, sizeof((so)->smalltable));	\
	(so)->used = (so)->fill = 0;				\
	INIT_NONZERO_SET_SLOTS(so);				\
    } while(0)

/* Reuse scheme to save calls to malloc, free, and memset */
#define MAXFREESETS 80
static PySetObject *free_sets[MAXFREESETS];
static int num_free_sets = 0;

/*
The basic lookup function used by all operations.
This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
Open addressing is preferred over chaining since the link overhead for
chaining would be substantial (100% with typical malloc overhead).

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

All arithmetic on hash should ignore overflow.

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

static setentry *
set_lookkey(PySetObject *so, PyObject *key, register long hash)
{
	register Py_ssize_t i;
	register size_t perturb;
	register setentry *freeslot;
	register size_t mask = so->mask;
	setentry *table = so->table;
	register setentry *entry;
	register int cmp;
	PyObject *startkey;

	i = hash & mask;
	entry = &table[i];
	if (entry->key == NULL || entry->key == key)
		return entry;

	if (entry->key == dummy)
		freeslot = entry;
	else {
		if (entry->hash == hash) {
			startkey = entry->key;
			cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
			if (cmp < 0)
				return NULL;
			if (table == so->table && entry->key == startkey) {
				if (cmp > 0)
					return entry;
			}
			else {
				/* The compare did major nasty stuff to the
				 * set:  start over.
 				 */
 				return set_lookkey(so, key, hash);
 			}
		}
		freeslot = NULL;
	}

	/* In the loop, key == dummy is by far (factor of 100s) the
	   least likely outcome, so test for that last. */
	for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
		i = (i << 2) + i + perturb + 1;
		entry = &table[i & mask];
		if (entry->key == NULL) {
			if (freeslot != NULL)
				entry = freeslot;
			break;
		}
		if (entry->key == key)
			break;
		if (entry->hash == hash && entry->key != dummy) {
			startkey = entry->key;
			cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
			if (cmp < 0)
				return NULL;
			if (table == so->table && entry->key == startkey) {
				if (cmp > 0)
					break;
			}
			else {
				/* The compare did major nasty stuff to the
				 * set:  start over.
 				 */
 				return set_lookkey(so, key, hash);
 			}
		}
		else if (entry->key == dummy && freeslot == NULL)
			freeslot = entry;
	}
	return entry;
}

/*
 * Hacked up version of set_lookkey which can assume keys are always strings;
 * This means we can always use _PyString_Eq directly and not have to check to
 * see if the comparison altered the table.
 */
static setentry *
set_lookkey_string(PySetObject *so, PyObject *key, register long hash)
{
	register Py_ssize_t i;
	register size_t perturb;
	register setentry *freeslot;
	register size_t mask = so->mask;
	setentry *table = so->table;
	register setentry *entry;

	/* Make sure this function doesn't have to handle non-string keys,
	   including subclasses of str; e.g., one reason to subclass
	   strings is to override __eq__, and for speed we don't cater to
	   that here. */
	if (!PyString_CheckExact(key)) {
		so->lookup = set_lookkey;
		return set_lookkey(so, key, hash);
	}
	i = hash & mask;
	entry = &table[i];
	if (entry->key == NULL || entry->key == key)
		return entry;
	if (entry->key == dummy)
		freeslot = entry;
	else {
		if (entry->hash == hash && _PyString_Eq(entry->key, key))
			return entry;
		freeslot = NULL;
	}

	/* In the loop, key == dummy is by far (factor of 100s) the
	   least likely outcome, so test for that last. */
	for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
		i = (i << 2) + i + perturb + 1;
		entry = &table[i & mask];
		if (entry->key == NULL)
			return freeslot == NULL ? entry : freeslot;
		if (entry->key == key
		    || (entry->hash == hash
			&& entry->key != dummy
			&& _PyString_Eq(entry->key, key)))
			return entry;
		if (entry->key == dummy && freeslot == NULL)
			freeslot = entry;
	}
	assert(0);	/* NOT REACHED */
	return 0;
}

/*
Internal routine to insert a new key into the table.
Used by the public insert routine.
Eats a reference to key.
*/
static int
set_insert_key(register PySetObject *so, PyObject *key, long hash)
{
	register setentry *entry;
	typedef setentry *(*lookupfunc)(PySetObject *, PyObject *, long);

	assert(so->lookup != NULL);
	entry = so->lookup(so, key, hash);
	if (entry == NULL)
		return -1;
	if (entry->key == NULL) {
		/* UNUSED */
		so->fill++; 
		entry->key = key;
		entry->hash = hash;
		so->used++;
	} else if (entry->key == dummy) {
		/* DUMMY */
		entry->key = key;
		entry->hash = hash;
		so->used++;
		Py_DECREF(dummy);
	} else {
		/* ACTIVE */
		Py_DECREF(key);
	}
	return 0;
}

/*
Internal routine used by set_table_resize() to insert an item which is
known to be absent from the set.  This routine also assumes that
the set contains no deleted entries.  Besides the performance benefit,
using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
Note that no refcounts are changed by this routine; if needed, the caller
is responsible for incref'ing `key`.
*/
static void
set_insert_clean(register PySetObject *so, PyObject *key, long hash)
{
	register size_t i;
	register size_t perturb;
	register size_t mask = (size_t)so->mask;
	setentry *table = so->table;
	register setentry *entry;

	i = hash & mask;
	entry = &table[i];
	for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) {
		i = (i << 2) + i + perturb + 1;
		entry = &table[i & mask];
	}
	so->fill++;
	entry->key = key;
	entry->hash = hash;
	so->used++;
}

/*
Restructure the table by allocating a new table and reinserting all
keys again.  When entries have been deleted, the new table may
actually be smaller than the old one.
*/
static int
set_table_resize(PySetObject *so, Py_ssize_t minused)
{
	Py_ssize_t newsize;
	setentry *oldtable, *newtable, *entry;
	Py_ssize_t i;
	int is_oldtable_malloced;
	setentry small_copy[PySet_MINSIZE];

	assert(minused >= 0);

	/* Find the smallest table size > minused. */
	for (newsize = PySet_MINSIZE;
	     newsize <= minused && newsize > 0;
	     newsize <<= 1)
		;
	if (newsize <= 0) {
		PyErr_NoMemory();
		return -1;
	}

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

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

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

	/* Copy the data over; this is refcount-neutral for active entries;
	   dummy entries aren't copied over, of course */
	for (entry = oldtable; i > 0; entry++) {
		if (entry->key == NULL) {
			/* UNUSED */
			;
		} else if (entry->key == dummy) {
			/* DUMMY */
			--i;
			assert(entry->key == dummy);
			Py_DECREF(entry->key);
		} else {
			/* ACTIVE */
			--i;
			set_insert_clean(so, entry->key, entry->hash);
		}
	}

	if (is_oldtable_malloced)
		PyMem_DEL(oldtable);
	return 0;
}

/* CAUTION: set_add_key/entry() must guarantee it won't resize the table */

static int
set_add_entry(register PySetObject *so, setentry *entry)
{
	register Py_ssize_t n_used;

	assert(so->fill <= so->mask);  /* at least one empty slot */
	n_used = so->used;
	Py_INCREF(entry->key);
	if (set_insert_key(so, entry->key, entry->hash) == -1) {
		Py_DECREF(entry->key);
		return -1;
	}
	if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
		return 0;
	return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
}

static int
set_add_key(register PySetObject *so, PyObject *key)
{
	register long hash;
	register Py_ssize_t n_used;

	if (!PyString_CheckExact(key) ||
	    (hash = ((PyStringObject *) key)->ob_shash) == -1) {
		hash = PyObject_Hash(key);
		if (hash == -1)
			return -1;
	}
	assert(so->fill <= so->mask);  /* at least one empty slot */
	n_used = so->used;
	Py_INCREF(key);
	if (set_insert_key(so, key, hash) == -1) {
		Py_DECREF(key);
		return -1;
	}
	if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
		return 0;
	return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
}

#define DISCARD_NOTFOUND 0
#define DISCARD_FOUND 1

static int
set_discard_entry(PySetObject *so, setentry *oldentry)
{	register setentry *entry;
	PyObject *old_key;

	entry = (so->lookup)(so, oldentry->key, oldentry->hash);
	if (entry == NULL)
		return -1;
	if (entry->key == NULL  ||  entry->key == dummy)
		return DISCARD_NOTFOUND;
	old_key = entry->key;
	Py_INCREF(dummy);
	entry->key = dummy;
	so->used--;
	Py_DECREF(old_key);
	return DISCARD_FOUND;
}

static int
set_discard_key(PySetObject *so, PyObject *key)
{
	register long hash;
	register setentry *entry;
	PyObject *old_key;

	assert (PyAnySet_Check(so));
	if (!PyString_CheckExact(key) ||
	    (hash = ((PyStringObject *) key)->ob_shash) == -1) {
		hash = PyObject_Hash(key);
		if (hash == -1)
			return -1;
	}
	entry = (so->lookup)(so, key, hash);
	if (entry == NULL)
		return -1;
	if (entry->key == NULL  ||  entry->key == dummy)
		return DISCARD_NOTFOUND;
	old_key = entry->key;
	Py_INCREF(dummy);
	entry->key = dummy;
	so->used--;
	Py_DECREF(old_key);
	return DISCARD_FOUND;
}

static int
set_clear_internal(PySetObject *so)
{
	setentry *entry, *table;
	int table_is_malloced;
	Py_ssize_t fill;
	setentry small_copy[PySet_MINSIZE];
#ifdef Py_DEBUG
	Py_ssize_t i, n;
	assert (PyAnySet_Check(so));

	n = so->mask + 1;
	i = 0;
#endif

	table = so->table;
	assert(table != NULL);
	table_is_malloced = table != so->smalltable;

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

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

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

	if (table_is_malloced)
		PyMem_DEL(table);
	return 0;
}

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

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

static void
set_dealloc(PySetObject *so)
{
	register setentry *entry;
	Py_ssize_t fill = so->fill;
	PyObject_GC_UnTrack(so);
	Py_TRASHCAN_SAFE_BEGIN(so)
	if (so->weakreflist != NULL)
		PyObject_ClearWeakRefs((PyObject *) so);

	for (entry = so->table; fill > 0; entry++) {
		if (entry->key) {
			--fill;
			Py_DECREF(entry->key);
		}
	}
	if (so->table != so->smalltable)
		PyMem_DEL(so->table);
	if (num_free_sets < MAXFREESETS && PyAnySet_CheckExact(so))
		free_sets[num_free_sets++] = so;
	else 
		Py_Type(so)->tp_free(so);
	Py_TRASHCAN_SAFE_END(so)
}

static int
set_tp_print(PySetObject *so, FILE *fp, int flags)
{
	setentry *entry;
	Py_ssize_t pos=0;
	char *emit = "";	/* No separator emitted on first pass */
	char *separator = ", ";
	int status = Py_ReprEnter((PyObject*)so);

	if (status != 0) {
		if (status < 0)
			return status;
		Py_BEGIN_ALLOW_THREADS
		fprintf(fp, "%s(...)", so->ob_type->tp_name);
		Py_END_ALLOW_THREADS
		return 0;
	}        

	Py_BEGIN_ALLOW_THREADS
	fprintf(fp, "%s([", so->ob_type->tp_name);
	Py_END_ALLOW_THREADS
	while (set_next(so, &pos, &entry)) {
		Py_BEGIN_ALLOW_THREADS
		fputs(emit, fp);
		Py_END_ALLOW_THREADS
		emit = separator;
		if (PyObject_Print(entry->key, fp, 0) != 0) {
			Py_ReprLeave((PyObject*)so);
			return -1;
		}
	}
	Py_BEGIN_ALLOW_THREADS
	fputs("])", fp);
	Py_END_ALLOW_THREADS
	Py_ReprLeave((PyObject*)so);        
	return 0;
}

static PyObject *
set_repr(PySetObject *so)
{
	PyObject *keys, *result=NULL, *listrepr;
	int status = Py_ReprEnter((PyObject*)so);

	if (status != 0) {
		if (status < 0)
			return NULL;
		return PyString_FromFormat("%s(...)", so->ob_type->tp_name);
	}

	keys = PySequence_List((PyObject *)so);
	if (keys == NULL)
		goto done;
	listrepr = PyObject_Repr(keys);
	Py_DECREF(keys);
	if (listrepr == NULL)
		goto done;

	result = PyString_FromFormat("%s(%s)", so->ob_type->tp_name,
		PyString_AS_STRING(listrepr));
	Py_DECREF(listrepr);
done:
	Py_ReprLeave((PyObject*)so);
	return result;
}

static Py_ssize_t
set_len(PyObject *so)
{
	return ((PySetObject *)so)->used;
}

static int
set_merge(PySetObject *so, PyObject *otherset)
{
	PySetObject *other;
	register Py_ssize_t i;
	register setentry *entry;

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

	other = (PySetObject*)otherset;
	if (other == so || other->used == 0)
		/* a.update(a) or a.update({}); nothing to do */
		return 0;
	/* Do one big resize at the start, rather than
	 * incrementally resizing as we insert new keys.  Expect
	 * that there will be no (or few) overlapping keys.
	 */
	if ((so->fill + other->used)*3 >= (so->mask+1)*2) {
	   if (set_table_resize(so, (so->used + other->used)*2) != 0)
		   return -1;
	}
	for (i = 0; i <= other->mask; i++) {
		entry = &other->table[i];
		if (entry->key != NULL && 
		    entry->key != dummy) {
			Py_INCREF(entry->key);
			if (set_insert_key(so, entry->key, entry->hash) == -1) {
				Py_DECREF(entry->key);
				return -1;
			}
		}
	}
	return 0;
}

static int
set_contains_key(PySetObject *so, PyObject *key)
{
	long hash;
	setentry *entry;

	if (!PyString_CheckExact(key) ||
	    (hash = ((PyStringObject *) key)->ob_shash) == -1) {
		hash = PyObject_Hash(key);
		if (hash == -1)
			return -1;
	}
	entry = (so->lookup)(so, key, hash);
	if (entry == NULL)
		return -1;
	key = entry->key;
	return key != NULL && key != dummy;
}

static int
set_contains_entry(PySetObject *so, setentry *entry)
{
	PyObject *key;
	setentry *lu_entry;

	lu_entry = (so->lookup)(so, entry->key, entry->hash);
	if (lu_entry == NULL)
		return -1;
	key = lu_entry->key; 
	return key != NULL && key != dummy;
}

static PyObject *
set_pop(PySetObject *so)
{
	register Py_ssize_t i = 0;
	register setentry *entry;
	PyObject *key;

	assert (PyAnySet_Check(so));
	if (so->used == 0) {
		PyErr_SetString(PyExc_KeyError, "pop from an empty set");
		return NULL;
	}

	/* Set entry to "the first" unused or dummy set entry.  We abuse
	 * the hash field of slot 0 to hold a search finger:
	 * If slot 0 has a value, use slot 0.
	 * Else slot 0 is being used to hold a search finger,
	 * and we use its hash value as the first index to look.
	 */
	entry = &so->table[0];
	if (entry->key == NULL || entry->key == dummy) {
		i = entry->hash;
		/* The hash field may be a real hash value, or it may be a
		 * legit search finger, or it may be a once-legit search
		 * finger that's out of bounds now because it wrapped around
		 * or the table shrunk -- simply make sure it's in bounds now.
		 */
		if (i > so->mask || i < 1)
			i = 1;	/* skip slot 0 */
		while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
			i++;
			if (i > so->mask)
				i = 1;
		}
	}
	key = entry->key;
	Py_INCREF(dummy);
	entry->key = dummy;
	so->used--;
	so->table[0].hash = i + 1;  /* next place to start */
	return key;
}

PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.");

static int
set_traverse(PySetObject *so, visitproc visit, void *arg)
{
	Py_ssize_t pos = 0;
	setentry *entry;

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

static long
frozenset_hash(PyObject *self)
{
	PySetObject *so = (PySetObject *)self;
	long h, hash = 1927868237L;
	setentry *entry;
	Py_ssize_t pos = 0;

	if (so->hash != -1)
		return so->hash;

	hash *= PySet_GET_SIZE(self) + 1;
	while (set_next(so, &pos, &entry)) {
		/* Work to increase the bit dispersion for closely spaced hash
		   values.  The is important because some use cases have many 
		   combinations of a small number of elements with nearby 
		   hashes so that many distinct combinations collapse to only 
		   a handful of distinct hash values. */
		h = entry->hash;
		hash ^= (h ^ (h << 16) ^ 89869747L)  * 3644798167u;
	}
	hash = hash * 69069L + 907133923L;
	if (hash == -1)
		hash = 590923713L;
	so->hash = hash;
	return hash;
}

static long
set_nohash(PyObject *self)
{
	PyErr_SetString(PyExc_TypeError, "set objects are unhashable");
	return -1;
}

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

typedef struct {
	PyObject_HEAD
	PySetObject *si_set; /* Set to NULL when iterator is exhausted */
	Py_ssize_t si_used;
	Py_ssize_t si_pos;
	Py_ssize_t len;
} setiterobject;

static void
setiter_dealloc(setiterobject *si)
{
	Py_XDECREF(si->si_set);
	PyObject_Del(si);
}

static PyObject *
setiter_len(setiterobject *si)
{
	Py_ssize_t len = 0;
	if (si->si_set != NULL && si->si_used == si->si_set->used)
		len = si->len;
	return PyInt_FromLong(len);
}

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

static PyMethodDef setiter_methods[] = {
	{"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
 	{NULL,		NULL}		/* sentinel */
};

static PyObject *setiter_iternext(setiterobject *si)
{
	PyObject *key;
	register Py_ssize_t i, mask;
	register setentry *entry;
	PySetObject *so = si->si_set;

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

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

	i = si->si_pos;
	assert(i>=0);
	entry = so->table;
	mask = so->mask;
	while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
		i++;
	si->si_pos = i+1;
	if (i > mask)
		goto fail;
	si->len--;
	key = entry[i].key;
	Py_INCREF(key);
	return key;

fail:
	Py_DECREF(so);
	si->si_set = NULL;
	return NULL;
}

static PyTypeObject PySetIter_Type = {
	PyVarObject_HEAD_INIT(&PyType_Type, 0)
	"setiterator",				/* tp_name */
	sizeof(setiterobject),			/* tp_basicsize */
	0,					/* tp_itemsize */
	/* methods */
	(destructor)setiter_dealloc, 		/* tp_dealloc */
	0,					/* tp_print */
	0,					/* tp_getattr */
	0,					/* tp_setattr */
	0,					/* tp_compare */
	0,					/* tp_repr */
	0,					/* tp_as_number */
	0,					/* tp_as_sequence */
	0,					/* tp_as_mapping */
	0,					/* tp_hash */
	0,					/* tp_call */
	0,					/* tp_str */
	PyObject_GenericGetAttr,		/* tp_getattro */
	0,					/* tp_setattro */
	0,					/* tp_as_buffer */
	Py_TPFLAGS_DEFAULT,			/* tp_flags */
 	0,					/* tp_doc */
 	0,					/* tp_traverse */
 	0,					/* tp_clear */
	0,					/* tp_richcompare */
	0,					/* tp_weaklistoffset */
	PyObject_SelfIter,			/* tp_iter */
	(iternextfunc)setiter_iternext,		/* tp_iternext */
	setiter_methods,			/* tp_methods */
	0,
};

static PyObject *
set_iter(PySetObject *so)
{
	setiterobject *si = PyObject_New(setiterobject, &PySetIter_Type);
	if (si == NULL)
		return NULL;
	Py_INCREF(so);
	si->si_set = so;
	si->si_used = so->used;
	si->si_pos = 0;
	si->len = so->used;
	return (PyObject *)si;
}

static int
set_update_internal(PySetObject *so, PyObject *other)
{
	PyObject *key, *it;

	if (PyAnySet_CheckExact(other))
		return set_merge(so, other);

	if (PyDict_CheckExact(other)) {
		PyObject *value;
		Py_ssize_t pos = 0;
		long hash;
		Py_ssize_t dictsize = PyDict_Size(other);

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

			an_entry.hash = hash;
			an_entry.key = key;
			if (set_add_entry(so, &an_entry) == -1)
				return -1;
		}
		return 0;
	}

	it = PyObject_GetIter(other);
	if (it == NULL)
		return -1;

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

static PyObject *
set_update(PySetObject *so, PyObject *other)
{
	if (set_update_internal(so, other) == -1)
		return NULL;
	Py_RETURN_NONE;
}

PyDoc_STRVAR(update_doc, 
"Update a set with the union of itself and another.");

static PyObject *
make_new_set(PyTypeObject *type, PyObject *iterable)
{
	register PySetObject *so = NULL;

	if (dummy == NULL) { /* Auto-initialize dummy */
		dummy = PyString_FromString("<dummy key>");
		if (dummy == NULL)
			return NULL;
	}

	/* create PySetObject structure */
	if (num_free_sets && 
	    (type == &PySet_Type  ||  type == &PyFrozenSet_Type)) {
		so = free_sets[--num_free_sets];
		assert (so != NULL && PyAnySet_CheckExact(so));
		Py_Type(so) = type;
		_Py_NewReference((PyObject *)so);
		EMPTY_TO_MINSIZE(so);
		PyObject_GC_Track(so);
	} else {
		so = (PySetObject *)type->tp_alloc(type, 0);
		if (so == NULL)
			return NULL;
		/* tp_alloc has already zeroed the structure */
		assert(so->table == NULL && so->fill == 0 && so->used == 0);
		INIT_NONZERO_SET_SLOTS(so);
	}

	so->lookup = set_lookkey_string;
	so->weakreflist = NULL;

	if (iterable != NULL) {
		if (set_update_internal(so, iterable) == -1) {
			Py_DECREF(so);
			return NULL;
		}
	}

	return (PyObject *)so;
}

/* The empty frozenset is a singleton */
static PyObject *emptyfrozenset = NULL;

static PyObject *
frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
	PyObject *iterable = NULL, *result;

	if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds))
		return NULL;

	if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
		return NULL;

	if (type != &PyFrozenSet_Type)
		return make_new_set(type, iterable);

	if (iterable != NULL) {
		/* frozenset(f) is idempotent */
		if (PyFrozenSet_CheckExact(iterable)) {
			Py_INCREF(iterable);
			return iterable;
		}
		result = make_new_set(type, iterable);
		if (result == NULL || PySet_GET_SIZE(result))
			return result;
		Py_DECREF(result);
	}
	/* The empty frozenset is a singleton */
	if (emptyfrozenset == NULL)
		emptyfrozenset = make_new_set(type, NULL);
	Py_XINCREF(emptyfrozenset);
	return emptyfrozenset;
}

void
PySet_Fini(void)
{
	PySetObject *so;

	while (num_free_sets) {
		num_free_sets--;
		so = free_sets[num_free_sets];
		PyObject_GC_Del(so);
	}
	Py_CLEAR(dummy);
	Py_CLEAR(emptyfrozenset);
}

static PyObject *
set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
	if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds))
		return NULL;
	
	return make_new_set(type, NULL);
}

/* set_swap_bodies() switches the contents of any two sets by moving their
   internal data pointers and, if needed, copying the internal smalltables.
   Semantically equivalent to:

     t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t

   The function always succeeds and it leaves both objects in a stable state.
   Useful for creating temporary frozensets from sets for membership testing 
   in __contains__(), discard(), and remove().  Also useful for operations
   that update in-place (by allowing an intermediate result to be swapped 
   into one of the original inputs).
*/

static void
set_swap_bodies(PySetObject *a, PySetObject *b)
{
	Py_ssize_t t;
	setentry *u;
	setentry *(*f)(PySetObject *so, PyObject *key, long hash);
	setentry tab[PySet_MINSIZE];
	long h;

	t = a->fill;     a->fill   = b->fill;        b->fill  = t;
	t = a->used;     a->used   = b->used;        b->used  = t;
	t = a->mask;     a->mask   = b->mask;        b->mask  = t;

	u = a->table;
	if (a->table == a->smalltable)
		u = b->smalltable;
	a->table  = b->table;
	if (b->table == b->smalltable)
		a->table = a->smalltable;
	b->table = u;

	f = a->lookup;   a->lookup = b->lookup;      b->lookup = f;

	if (a->table == a->smalltable || b->table == b->smalltable) {
		memcpy(tab, a->smalltable, sizeof(tab));
		memcpy(a->smalltable, b->smalltable, sizeof(tab));
		memcpy(b->smalltable, tab, sizeof(tab));
	}

	if (PyType_IsSubtype(Py_Type(a), &PyFrozenSet_Type)  &&
	    PyType_IsSubtype(Py_Type(b), &PyFrozenSet_Type)) {
		h = a->hash;     a->hash = b->hash;  b->hash = h;
	} else {
		a->hash = -1;
		b->hash = -1;
	}
}

static PyObject *
set_copy(PySetObject *so)
{
	return make_new_set(Py_Type(so), (PyObject *)so);
}

static PyObject *
frozenset_copy(PySetObject *so)
{
	if (PyFrozenSet_CheckExact(so)) {
		Py_INCREF(so);
		return (PyObject *)so;
	}
	return set_copy(so);
}

PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");

static PyObject *
set_clear(PySetObject *so)
{
	set_clear_internal(so);
	Py_RETURN_NONE;
}

PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");

static PyObject *
set_union(PySetObject *so, PyObject *other)
{
	PySetObject *result;

	result = (PySetObject *)set_copy(so);
	if (result == NULL)
		return NULL;
	if ((PyObject *)so == other)
		return (PyObject *)result;
	if (set_update_internal(result, other) == -1) {
		Py_DECREF(result);
		return NULL;
	}
	return (PyObject *)result;
}

PyDoc_STRVAR(union_doc,
 "Return the union of two sets as a new set.\n\
\n\
(i.e. all elements that are in either set.)");

static PyObject *
set_or(PySetObject *so, PyObject *other)
{
	if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
		Py_INCREF(Py_NotImplemented);
		return Py_NotImplemented;
	}
	return set_union(so, other);
}

static PyObject *
set_ior(PySetObject *so, PyObject *other)
{
	if (!PyAnySet_Check(other)) {
		Py_INCREF(Py_NotImplemented);
		return Py_NotImplemented;
	}
	if (set_update_internal(so, other) == -1)
		return NULL;
	Py_INCREF(so);
	return (PyObject *)so;
}

static PyObject *
set_intersection(PySetObject *so, PyObject *other)
{
	PySetObject *result;
	PyObject *key, *it, *tmp;

	if ((PyObject *)so == other)
		return set_copy(so);

	result = (PySetObject *)make_new_set(Py_Type(so), NULL);
	if (result == NULL)
		return NULL;

	if (PyAnySet_CheckExact(other)) {		
		Py_ssize_t pos = 0;
		setentry *entry;

		if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
			tmp = (PyObject *)so;
			so = (PySetObject *)other;
			other = tmp;
		}

		while (set_next((PySetObject *)other, &pos, &entry)) {
			int rv = set_contains_entry(so, entry);
			if (rv == -1) {
				Py_DECREF(result);
				return NULL;
			}
			if (rv) {
				if (set_add_entry(result, entry) == -1) {
					Py_DECREF(result);
					return NULL;
				}
			}
		}
		return (PyObject *)result;
	}

	it = PyObject_GetIter(other);
	if (it == NULL) {
		Py_DECREF(result);
		return NULL;
	}

	while ((key = PyIter_Next(it)) != NULL) {
		int rv;
		setentry entry;
		long hash = PyObject_Hash(key);

		if (hash == -1) {
			Py_DECREF(it);
			Py_DECREF(result);
			Py_DECREF(key);
			return NULL;
		}
		entry.hash = hash;
		entry.key = key;
		rv = set_contains_entry(so, &entry);
		if (rv == -1) {
			Py_DECREF(it);
			Py_DECREF(result);
			Py_DECREF(key);
			return NULL;
		}
		if (rv) {
			if (set_add_entry(result, &entry) == -1) {
				Py_DECREF(it);
				Py_DECREF(result);
				Py_DECREF(key);
				return NULL;
			}
		}
		Py_DECREF(key);
	}
	Py_DECREF(it);
	if (PyErr_Occurred()) {
		Py_DECREF(result);
		return NULL;
	}
	return (PyObject *)result;
}

PyDoc_STRVAR(intersection_doc,
"Return the intersection of two sets as a new set.\n\
\n\
(i.e. all elements that are in both sets.)");

static PyObject *
set_intersection_update(PySetObject *so, PyObject *other)
{
	PyObject *tmp;

	tmp = set_intersection(so, other);
	if (tmp == NULL)
		return NULL;
	set_swap_bodies(so, (PySetObject *)tmp);
	Py_DECREF(tmp);
	Py_RETURN_NONE;
}

PyDoc_STRVAR(intersection_update_doc,
"Update a set with the intersection of itself and another.");

static PyObject *
set_and(PySetObject *so, PyObject *other)
{
	if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
		Py_INCREF(Py_NotImplemented);
		return Py_NotImplemented;
	}
	return set_intersection(so, other);
}

static PyObject *
set_iand(PySetObject *so, PyObject *other)
{
	PyObject *result;

	if (!PyAnySet_Check(other)) {
		Py_INCREF(Py_NotImplemented);
		return Py_NotImplemented;
	}
	result = set_intersection_update(so, other);
	if (result == NULL)
		return NULL;
	Py_DECREF(result);
	Py_INCREF(so);
	return (PyObject *)so;
}

static PyObject *
set_isdisjoint(PySetObject *so, PyObject *other)
{
	PyObject *key, *it, *tmp;

	if ((PyObject *)so == other) {
		if (PySet_GET_SIZE(so) == 0)
			Py_RETURN_TRUE;
		else
			Py_RETURN_FALSE;
	}

	if (PyAnySet_CheckExact(other)) {		
		Py_ssize_t pos = 0;
		setentry *entry;

		if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
			tmp = (PyObject *)so;
			so = (PySetObject *)other;
			other = tmp;
		}
		while (set_next((PySetObject *)other, &pos, &entry)) {
			int rv = set_contains_entry(so, entry);
			if (rv == -1)
				return NULL;
			if (rv)
				Py_RETURN_FALSE;
		}
		Py_RETURN_TRUE;
	}

	it = PyObject_GetIter(other);
	if (it == NULL)
		return NULL;

	while ((key = PyIter_Next(it)) != NULL) {
		int rv;
		setentry entry;
		long hash = PyObject_Hash(key);

		Py_DECREF(key);
		if (hash == -1) {
			Py_DECREF(it);
			return NULL;
		}
		entry.hash = hash;
		entry.key = key;
		rv = set_contains_entry(so, &entry);
		if (rv == -1) {
			Py_DECREF(it);
			return NULL;
		}
		if (rv) {
			Py_DECREF(it);
			Py_RETURN_FALSE;
		}
	}
	Py_DECREF(it);
	if (PyErr_Occurred())
		return NULL;
	Py_RETURN_TRUE;
}<commit_msg>Reposition the decref (spotted by eagle-eye norwitz).<commit_after>
/* set object implementation 
   Written and maintained by <NAME> <<EMAIL>>
   Derived from Lib/sets.py and Objects/dictobject.c.

   Copyright (c) 2003-2007 Python Software Foundation.
   All rights reserved.
*/

#include "Python.h"
#include "structmember.h"

/* Set a key error with the specified argument, wrapping it in a
 * tuple automatically so that tuple keys are not unpacked as the
 * exception arguments. */
static void
set_key_error(PyObject *arg)
{
	PyObject *tup;
	tup = PyTuple_Pack(1, arg);
	if (!tup)
		return; /* caller will expect error to be set anyway */
	PyErr_SetObject(PyExc_KeyError, tup);
	Py_DECREF(tup);
}

/* This must be >= 1. */
#define PERTURB_SHIFT 5

/* Object used as dummy key to fill deleted entries */
static PyObject *dummy = NULL; /* Initialized by first call to make_new_set() */

#ifdef Py_REF_DEBUG
PyObject *
_PySet_Dummy(void)
{
	return dummy;
}
#endif

#define INIT_NONZERO_SET_SLOTS(so) do {				\
	(so)->table = (so)->smalltable;				\
	(so)->mask = PySet_MINSIZE - 1;				\
	(so)->hash = -1;					\
    } while(0)

#define EMPTY_TO_MINSIZE(so) do {				\
	memset((so)->smalltable, 0, sizeof((so)->smalltable));	\
	(so)->used = (so)->fill = 0;				\
	INIT_NONZERO_SET_SLOTS(so);				\
    } while(0)

/* Reuse scheme to save calls to malloc, free, and memset */
#define MAXFREESETS 80
static PySetObject *free_sets[MAXFREESETS];
static int num_free_sets = 0;

/*
The basic lookup function used by all operations.
This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
Open addressing is preferred over chaining since the link overhead for
chaining would be substantial (100% with typical malloc overhead).

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

All arithmetic on hash should ignore overflow.

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

static setentry *
set_lookkey(PySetObject *so, PyObject *key, register long hash)
{
	register Py_ssize_t i;
	register size_t perturb;
	register setentry *freeslot;
	register size_t mask = so->mask;
	setentry *table = so->table;
	register setentry *entry;
	register int cmp;
	PyObject *startkey;

	i = hash & mask;
	entry = &table[i];
	if (entry->key == NULL || entry->key == key)
		return entry;

	if (entry->key == dummy)
		freeslot = entry;
	else {
		if (entry->hash == hash) {
			startkey = entry->key;
			cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
			if (cmp < 0)
				return NULL;
			if (table == so->table && entry->key == startkey) {
				if (cmp > 0)
					return entry;
			}
			else {
				/* The compare did major nasty stuff to the
				 * set:  start over.
 				 */
 				return set_lookkey(so, key, hash);
 			}
		}
		freeslot = NULL;
	}

	/* In the loop, key == dummy is by far (factor of 100s) the
	   least likely outcome, so test for that last. */
	for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
		i = (i << 2) + i + perturb + 1;
		entry = &table[i & mask];
		if (entry->key == NULL) {
			if (freeslot != NULL)
				entry = freeslot;
			break;
		}
		if (entry->key == key)
			break;
		if (entry->hash == hash && entry->key != dummy) {
			startkey = entry->key;
			cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
			if (cmp < 0)
				return NULL;
			if (table == so->table && entry->key == startkey) {
				if (cmp > 0)
					break;
			}
			else {
				/* The compare did major nasty stuff to the
				 * set:  start over.
 				 */
 				return set_lookkey(so, key, hash);
 			}
		}
		else if (entry->key == dummy && freeslot == NULL)
			freeslot = entry;
	}
	return entry;
}

/*
 * Hacked up version of set_lookkey which can assume keys are always strings;
 * This means we can always use _PyString_Eq directly and not have to check to
 * see if the comparison altered the table.
 */
static setentry *
set_lookkey_string(PySetObject *so, PyObject *key, register long hash)
{
	register Py_ssize_t i;
	register size_t perturb;
	register setentry *freeslot;
	register size_t mask = so->mask;
	setentry *table = so->table;
	register setentry *entry;

	/* Make sure this function doesn't have to handle non-string keys,
	   including subclasses of str; e.g., one reason to subclass
	   strings is to override __eq__, and for speed we don't cater to
	   that here. */
	if (!PyString_CheckExact(key)) {
		so->lookup = set_lookkey;
		return set_lookkey(so, key, hash);
	}
	i = hash & mask;
	entry = &table[i];
	if (entry->key == NULL || entry->key == key)
		return entry;
	if (entry->key == dummy)
		freeslot = entry;
	else {
		if (entry->hash == hash && _PyString_Eq(entry->key, key))
			return entry;
		freeslot = NULL;
	}

	/* In the loop, key == dummy is by far (factor of 100s) the
	   least likely outcome, so test for that last. */
	for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
		i = (i << 2) + i + perturb + 1;
		entry = &table[i & mask];
		if (entry->key == NULL)
			return freeslot == NULL ? entry : freeslot;
		if (entry->key == key
		    || (entry->hash == hash
			&& entry->key != dummy
			&& _PyString_Eq(entry->key, key)))
			return entry;
		if (entry->key == dummy && freeslot == NULL)
			freeslot = entry;
	}
	assert(0);	/* NOT REACHED */
	return 0;
}

/*
Internal routine to insert a new key into the table.
Used by the public insert routine.
Eats a reference to key.
*/
static int
set_insert_key(register PySetObject *so, PyObject *key, long hash)
{
	register setentry *entry;
	typedef setentry *(*lookupfunc)(PySetObject *, PyObject *, long);

	assert(so->lookup != NULL);
	entry = so->lookup(so, key, hash);
	if (entry == NULL)
		return -1;
	if (entry->key == NULL) {
		/* UNUSED */
		so->fill++; 
		entry->key = key;
		entry->hash = hash;
		so->used++;
	} else if (entry->key == dummy) {
		/* DUMMY */
		entry->key = key;
		entry->hash = hash;
		so->used++;
		Py_DECREF(dummy);
	} else {
		/* ACTIVE */
		Py_DECREF(key);
	}
	return 0;
}

/*
Internal routine used by set_table_resize() to insert an item which is
known to be absent from the set.  This routine also assumes that
the set contains no deleted entries.  Besides the performance benefit,
using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
Note that no refcounts are changed by this routine; if needed, the caller
is responsible for incref'ing `key`.
*/
static void
set_insert_clean(register PySetObject *so, PyObject *key, long hash)
{
	register size_t i;
	register size_t perturb;
	register size_t mask = (size_t)so->mask;
	setentry *table = so->table;
	register setentry *entry;

	i = hash & mask;
	entry = &table[i];
	for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) {
		i = (i << 2) + i + perturb + 1;
		entry = &table[i & mask];
	}
	so->fill++;
	entry->key = key;
	entry->hash = hash;
	so->used++;
}

/*
Restructure the table by allocating a new table and reinserting all
keys again.  When entries have been deleted, the new table may
actually be smaller than the old one.
*/
static int
set_table_resize(PySetObject *so, Py_ssize_t minused)
{
	Py_ssize_t newsize;
	setentry *oldtable, *newtable, *entry;
	Py_ssize_t i;
	int is_oldtable_malloced;
	setentry small_copy[PySet_MINSIZE];

	assert(minused >= 0);

	/* Find the smallest table size > minused. */
	for (newsize = PySet_MINSIZE;
	     newsize <= minused && newsize > 0;
	     newsize <<= 1)
		;
	if (newsize <= 0) {
		PyErr_NoMemory();
		return -1;
	}

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

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

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

	/* Copy the data over; this is refcount-neutral for active entries;
	   dummy entries aren't copied over, of course */
	for (entry = oldtable; i > 0; entry++) {
		if (entry->key == NULL) {
			/* UNUSED */
			;
		} else if (entry->key == dummy) {
			/* DUMMY */
			--i;
			assert(entry->key == dummy);
			Py_DECREF(entry->key);
		} else {
			/* ACTIVE */
			--i;
			set_insert_clean(so, entry->key, entry->hash);
		}
	}

	if (is_oldtable_malloced)
		PyMem_DEL(oldtable);
	return 0;
}

/* CAUTION: set_add_key/entry() must guarantee it won't resize the table */

static int
set_add_entry(register PySetObject *so, setentry *entry)
{
	register Py_ssize_t n_used;

	assert(so->fill <= so->mask);  /* at least one empty slot */
	n_used = so->used;
	Py_INCREF(entry->key);
	if (set_insert_key(so, entry->key, entry->hash) == -1) {
		Py_DECREF(entry->key);
		return -1;
	}
	if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
		return 0;
	return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
}

static int
set_add_key(register PySetObject *so, PyObject *key)
{
	register long hash;
	register Py_ssize_t n_used;

	if (!PyString_CheckExact(key) ||
	    (hash = ((PyStringObject *) key)->ob_shash) == -1) {
		hash = PyObject_Hash(key);
		if (hash == -1)
			return -1;
	}
	assert(so->fill <= so->mask);  /* at least one empty slot */
	n_used = so->used;
	Py_INCREF(key);
	if (set_insert_key(so, key, hash) == -1) {
		Py_DECREF(key);
		return -1;
	}
	if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
		return 0;
	return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
}

#define DISCARD_NOTFOUND 0
#define DISCARD_FOUND 1

static int
set_discard_entry(PySetObject *so, setentry *oldentry)
{	register setentry *entry;
	PyObject *old_key;

	entry = (so->lookup)(so, oldentry->key, oldentry->hash);
	if (entry == NULL)
		return -1;
	if (entry->key == NULL  ||  entry->key == dummy)
		return DISCARD_NOTFOUND;
	old_key = entry->key;
	Py_INCREF(dummy);
	entry->key = dummy;
	so->used--;
	Py_DECREF(old_key);
	return DISCARD_FOUND;
}

static int
set_discard_key(PySetObject *so, PyObject *key)
{
	register long hash;
	register setentry *entry;
	PyObject *old_key;

	assert (PyAnySet_Check(so));
	if (!PyString_CheckExact(key) ||
	    (hash = ((PyStringObject *) key)->ob_shash) == -1) {
		hash = PyObject_Hash(key);
		if (hash == -1)
			return -1;
	}
	entry = (so->lookup)(so, key, hash);
	if (entry == NULL)
		return -1;
	if (entry->key == NULL  ||  entry->key == dummy)
		return DISCARD_NOTFOUND;
	old_key = entry->key;
	Py_INCREF(dummy);
	entry->key = dummy;
	so->used--;
	Py_DECREF(old_key);
	return DISCARD_FOUND;
}

static int
set_clear_internal(PySetObject *so)
{
	setentry *entry, *table;
	int table_is_malloced;
	Py_ssize_t fill;
	setentry small_copy[PySet_MINSIZE];
#ifdef Py_DEBUG
	Py_ssize_t i, n;
	assert (PyAnySet_Check(so));

	n = so->mask + 1;
	i = 0;
#endif

	table = so->table;
	assert(table != NULL);
	table_is_malloced = table != so->smalltable;

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

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

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

	if (table_is_malloced)
		PyMem_DEL(table);
	return 0;
}

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

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

static void
set_dealloc(PySetObject *so)
{
	register setentry *entry;
	Py_ssize_t fill = so->fill;
	PyObject_GC_UnTrack(so);
	Py_TRASHCAN_SAFE_BEGIN(so)
	if (so->weakreflist != NULL)
		PyObject_ClearWeakRefs((PyObject *) so);

	for (entry = so->table; fill > 0; entry++) {
		if (entry->key) {
			--fill;
			Py_DECREF(entry->key);
		}
	}
	if (so->table != so->smalltable)
		PyMem_DEL(so->table);
	if (num_free_sets < MAXFREESETS && PyAnySet_CheckExact(so))
		free_sets[num_free_sets++] = so;
	else 
		Py_Type(so)->tp_free(so);
	Py_TRASHCAN_SAFE_END(so)
}

static int
set_tp_print(PySetObject *so, FILE *fp, int flags)
{
	setentry *entry;
	Py_ssize_t pos=0;
	char *emit = "";	/* No separator emitted on first pass */
	char *separator = ", ";
	int status = Py_ReprEnter((PyObject*)so);

	if (status != 0) {
		if (status < 0)
			return status;
		Py_BEGIN_ALLOW_THREADS
		fprintf(fp, "%s(...)", so->ob_type->tp_name);
		Py_END_ALLOW_THREADS
		return 0;
	}        

	Py_BEGIN_ALLOW_THREADS
	fprintf(fp, "%s([", so->ob_type->tp_name);
	Py_END_ALLOW_THREADS
	while (set_next(so, &pos, &entry)) {
		Py_BEGIN_ALLOW_THREADS
		fputs(emit, fp);
		Py_END_ALLOW_THREADS
		emit = separator;
		if (PyObject_Print(entry->key, fp, 0) != 0) {
			Py_ReprLeave((PyObject*)so);
			return -1;
		}
	}
	Py_BEGIN_ALLOW_THREADS
	fputs("])", fp);
	Py_END_ALLOW_THREADS
	Py_ReprLeave((PyObject*)so);        
	return 0;
}

static PyObject *
set_repr(PySetObject *so)
{
	PyObject *keys, *result=NULL, *listrepr;
	int status = Py_ReprEnter((PyObject*)so);

	if (status != 0) {
		if (status < 0)
			return NULL;
		return PyString_FromFormat("%s(...)", so->ob_type->tp_name);
	}

	keys = PySequence_List((PyObject *)so);
	if (keys == NULL)
		goto done;
	listrepr = PyObject_Repr(keys);
	Py_DECREF(keys);
	if (listrepr == NULL)
		goto done;

	result = PyString_FromFormat("%s(%s)", so->ob_type->tp_name,
		PyString_AS_STRING(listrepr));
	Py_DECREF(listrepr);
done:
	Py_ReprLeave((PyObject*)so);
	return result;
}

static Py_ssize_t
set_len(PyObject *so)
{
	return ((PySetObject *)so)->used;
}

static int
set_merge(PySetObject *so, PyObject *otherset)
{
	PySetObject *other;
	register Py_ssize_t i;
	register setentry *entry;

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

	other = (PySetObject*)otherset;
	if (other == so || other->used == 0)
		/* a.update(a) or a.update({}); nothing to do */
		return 0;
	/* Do one big resize at the start, rather than
	 * incrementally resizing as we insert new keys.  Expect
	 * that there will be no (or few) overlapping keys.
	 */
	if ((so->fill + other->used)*3 >= (so->mask+1)*2) {
	   if (set_table_resize(so, (so->used + other->used)*2) != 0)
		   return -1;
	}
	for (i = 0; i <= other->mask; i++) {
		entry = &other->table[i];
		if (entry->key != NULL && 
		    entry->key != dummy) {
			Py_INCREF(entry->key);
			if (set_insert_key(so, entry->key, entry->hash) == -1) {
				Py_DECREF(entry->key);
				return -1;
			}
		}
	}
	return 0;
}

static int
set_contains_key(PySetObject *so, PyObject *key)
{
	long hash;
	setentry *entry;

	if (!PyString_CheckExact(key) ||
	    (hash = ((PyStringObject *) key)->ob_shash) == -1) {
		hash = PyObject_Hash(key);
		if (hash == -1)
			return -1;
	}
	entry = (so->lookup)(so, key, hash);
	if (entry == NULL)
		return -1;
	key = entry->key;
	return key != NULL && key != dummy;
}

static int
set_contains_entry(PySetObject *so, setentry *entry)
{
	PyObject *key;
	setentry *lu_entry;

	lu_entry = (so->lookup)(so, entry->key, entry->hash);
	if (lu_entry == NULL)
		return -1;
	key = lu_entry->key; 
	return key != NULL && key != dummy;
}

static PyObject *
set_pop(PySetObject *so)
{
	register Py_ssize_t i = 0;
	register setentry *entry;
	PyObject *key;

	assert (PyAnySet_Check(so));
	if (so->used == 0) {
		PyErr_SetString(PyExc_KeyError, "pop from an empty set");
		return NULL;
	}

	/* Set entry to "the first" unused or dummy set entry.  We abuse
	 * the hash field of slot 0 to hold a search finger:
	 * If slot 0 has a value, use slot 0.
	 * Else slot 0 is being used to hold a search finger,
	 * and we use its hash value as the first index to look.
	 */
	entry = &so->table[0];
	if (entry->key == NULL || entry->key == dummy) {
		i = entry->hash;
		/* The hash field may be a real hash value, or it may be a
		 * legit search finger, or it may be a once-legit search
		 * finger that's out of bounds now because it wrapped around
		 * or the table shrunk -- simply make sure it's in bounds now.
		 */
		if (i > so->mask || i < 1)
			i = 1;	/* skip slot 0 */
		while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
			i++;
			if (i > so->mask)
				i = 1;
		}
	}
	key = entry->key;
	Py_INCREF(dummy);
	entry->key = dummy;
	so->used--;
	so->table[0].hash = i + 1;  /* next place to start */
	return key;
}

PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.");

static int
set_traverse(PySetObject *so, visitproc visit, void *arg)
{
	Py_ssize_t pos = 0;
	setentry *entry;

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

static long
frozenset_hash(PyObject *self)
{
	PySetObject *so = (PySetObject *)self;
	long h, hash = 1927868237L;
	setentry *entry;
	Py_ssize_t pos = 0;

	if (so->hash != -1)
		return so->hash;

	hash *= PySet_GET_SIZE(self) + 1;
	while (set_next(so, &pos, &entry)) {
		/* Work to increase the bit dispersion for closely spaced hash
		   values.  The is important because some use cases have many 
		   combinations of a small number of elements with nearby 
		   hashes so that many distinct combinations collapse to only 
		   a handful of distinct hash values. */
		h = entry->hash;
		hash ^= (h ^ (h << 16) ^ 89869747L)  * 3644798167u;
	}
	hash = hash * 69069L + 907133923L;
	if (hash == -1)
		hash = 590923713L;
	so->hash = hash;
	return hash;
}

static long
set_nohash(PyObject *self)
{
	PyErr_SetString(PyExc_TypeError, "set objects are unhashable");
	return -1;
}

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

typedef struct {
	PyObject_HEAD
	PySetObject *si_set; /* Set to NULL when iterator is exhausted */
	Py_ssize_t si_used;
	Py_ssize_t si_pos;
	Py_ssize_t len;
} setiterobject;

static void
setiter_dealloc(setiterobject *si)
{
	Py_XDECREF(si->si_set);
	PyObject_Del(si);
}

static PyObject *
setiter_len(setiterobject *si)
{
	Py_ssize_t len = 0;
	if (si->si_set != NULL && si->si_used == si->si_set->used)
		len = si->len;
	return PyInt_FromLong(len);
}

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

static PyMethodDef setiter_methods[] = {
	{"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
 	{NULL,		NULL}		/* sentinel */
};

static PyObject *setiter_iternext(setiterobject *si)
{
	PyObject *key;
	register Py_ssize_t i, mask;
	register setentry *entry;
	PySetObject *so = si->si_set;

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

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

	i = si->si_pos;
	assert(i>=0);
	entry = so->table;
	mask = so->mask;
	while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
		i++;
	si->si_pos = i+1;
	if (i > mask)
		goto fail;
	si->len--;
	key = entry[i].key;
	Py_INCREF(key);
	return key;

fail:
	Py_DECREF(so);
	si->si_set = NULL;
	return NULL;
}

static PyTypeObject PySetIter_Type = {
	PyVarObject_HEAD_INIT(&PyType_Type, 0)
	"setiterator",				/* tp_name */
	sizeof(setiterobject),			/* tp_basicsize */
	0,					/* tp_itemsize */
	/* methods */
	(destructor)setiter_dealloc, 		/* tp_dealloc */
	0,					/* tp_print */
	0,					/* tp_getattr */
	0,					/* tp_setattr */
	0,					/* tp_compare */
	0,					/* tp_repr */
	0,					/* tp_as_number */
	0,					/* tp_as_sequence */
	0,					/* tp_as_mapping */
	0,					/* tp_hash */
	0,					/* tp_call */
	0,					/* tp_str */
	PyObject_GenericGetAttr,		/* tp_getattro */
	0,					/* tp_setattro */
	0,					/* tp_as_buffer */
	Py_TPFLAGS_DEFAULT,			/* tp_flags */
 	0,					/* tp_doc */
 	0,					/* tp_traverse */
 	0,					/* tp_clear */
	0,					/* tp_richcompare */
	0,					/* tp_weaklistoffset */
	PyObject_SelfIter,			/* tp_iter */
	(iternextfunc)setiter_iternext,		/* tp_iternext */
	setiter_methods,			/* tp_methods */
	0,
};

static PyObject *
set_iter(PySetObject *so)
{
	setiterobject *si = PyObject_New(setiterobject, &PySetIter_Type);
	if (si == NULL)
		return NULL;
	Py_INCREF(so);
	si->si_set = so;
	si->si_used = so->used;
	si->si_pos = 0;
	si->len = so->used;
	return (PyObject *)si;
}

static int
set_update_internal(PySetObject *so, PyObject *other)
{
	PyObject *key, *it;

	if (PyAnySet_CheckExact(other))
		return set_merge(so, other);

	if (PyDict_CheckExact(other)) {
		PyObject *value;
		Py_ssize_t pos = 0;
		long hash;
		Py_ssize_t dictsize = PyDict_Size(other);

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

			an_entry.hash = hash;
			an_entry.key = key;
			if (set_add_entry(so, &an_entry) == -1)
				return -1;
		}
		return 0;
	}

	it = PyObject_GetIter(other);
	if (it == NULL)
		return -1;

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

static PyObject *
set_update(PySetObject *so, PyObject *other)
{
	if (set_update_internal(so, other) == -1)
		return NULL;
	Py_RETURN_NONE;
}

PyDoc_STRVAR(update_doc, 
"Update a set with the union of itself and another.");

static PyObject *
make_new_set(PyTypeObject *type, PyObject *iterable)
{
	register PySetObject *so = NULL;

	if (dummy == NULL) { /* Auto-initialize dummy */
		dummy = PyString_FromString("<dummy key>");
		if (dummy == NULL)
			return NULL;
	}

	/* create PySetObject structure */
	if (num_free_sets && 
	    (type == &PySet_Type  ||  type == &PyFrozenSet_Type)) {
		so = free_sets[--num_free_sets];
		assert (so != NULL && PyAnySet_CheckExact(so));
		Py_Type(so) = type;
		_Py_NewReference((PyObject *)so);
		EMPTY_TO_MINSIZE(so);
		PyObject_GC_Track(so);
	} else {
		so = (PySetObject *)type->tp_alloc(type, 0);
		if (so == NULL)
			return NULL;
		/* tp_alloc has already zeroed the structure */
		assert(so->table == NULL && so->fill == 0 && so->used == 0);
		INIT_NONZERO_SET_SLOTS(so);
	}

	so->lookup = set_lookkey_string;
	so->weakreflist = NULL;

	if (iterable != NULL) {
		if (set_update_internal(so, iterable) == -1) {
			Py_DECREF(so);
			return NULL;
		}
	}

	return (PyObject *)so;
}

/* The empty frozenset is a singleton */
static PyObject *emptyfrozenset = NULL;

static PyObject *
frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
	PyObject *iterable = NULL, *result;

	if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds))
		return NULL;

	if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
		return NULL;

	if (type != &PyFrozenSet_Type)
		return make_new_set(type, iterable);

	if (iterable != NULL) {
		/* frozenset(f) is idempotent */
		if (PyFrozenSet_CheckExact(iterable)) {
			Py_INCREF(iterable);
			return iterable;
		}
		result = make_new_set(type, iterable);
		if (result == NULL || PySet_GET_SIZE(result))
			return result;
		Py_DECREF(result);
	}
	/* The empty frozenset is a singleton */
	if (emptyfrozenset == NULL)
		emptyfrozenset = make_new_set(type, NULL);
	Py_XINCREF(emptyfrozenset);
	return emptyfrozenset;
}

void
PySet_Fini(void)
{
	PySetObject *so;

	while (num_free_sets) {
		num_free_sets--;
		so = free_sets[num_free_sets];
		PyObject_GC_Del(so);
	}
	Py_CLEAR(dummy);
	Py_CLEAR(emptyfrozenset);
}

static PyObject *
set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
	if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds))
		return NULL;
	
	return make_new_set(type, NULL);
}

/* set_swap_bodies() switches the contents of any two sets by moving their
   internal data pointers and, if needed, copying the internal smalltables.
   Semantically equivalent to:

     t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t

   The function always succeeds and it leaves both objects in a stable state.
   Useful for creating temporary frozensets from sets for membership testing 
   in __contains__(), discard(), and remove().  Also useful for operations
   that update in-place (by allowing an intermediate result to be swapped 
   into one of the original inputs).
*/

static void
set_swap_bodies(PySetObject *a, PySetObject *b)
{
	Py_ssize_t t;
	setentry *u;
	setentry *(*f)(PySetObject *so, PyObject *key, long hash);
	setentry tab[PySet_MINSIZE];
	long h;

	t = a->fill;     a->fill   = b->fill;        b->fill  = t;
	t = a->used;     a->used   = b->used;        b->used  = t;
	t = a->mask;     a->mask   = b->mask;        b->mask  = t;

	u = a->table;
	if (a->table == a->smalltable)
		u = b->smalltable;
	a->table  = b->table;
	if (b->table == b->smalltable)
		a->table = a->smalltable;
	b->table = u;

	f = a->lookup;   a->lookup = b->lookup;      b->lookup = f;

	if (a->table == a->smalltable || b->table == b->smalltable) {
		memcpy(tab, a->smalltable, sizeof(tab));
		memcpy(a->smalltable, b->smalltable, sizeof(tab));
		memcpy(b->smalltable, tab, sizeof(tab));
	}

	if (PyType_IsSubtype(Py_Type(a), &PyFrozenSet_Type)  &&
	    PyType_IsSubtype(Py_Type(b), &PyFrozenSet_Type)) {
		h = a->hash;     a->hash = b->hash;  b->hash = h;
	} else {
		a->hash = -1;
		b->hash = -1;
	}
}

static PyObject *
set_copy(PySetObject *so)
{
	return make_new_set(Py_Type(so), (PyObject *)so);
}

static PyObject *
frozenset_copy(PySetObject *so)
{
	if (PyFrozenSet_CheckExact(so)) {
		Py_INCREF(so);
		return (PyObject *)so;
	}
	return set_copy(so);
}

PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");

static PyObject *
set_clear(PySetObject *so)
{
	set_clear_internal(so);
	Py_RETURN_NONE;
}

PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");

static PyObject *
set_union(PySetObject *so, PyObject *other)
{
	PySetObject *result;

	result = (PySetObject *)set_copy(so);
	if (result == NULL)
		return NULL;
	if ((PyObject *)so == other)
		return (PyObject *)result;
	if (set_update_internal(result, other) == -1) {
		Py_DECREF(result);
		return NULL;
	}
	return (PyObject *)result;
}

PyDoc_STRVAR(union_doc,
 "Return the union of two sets as a new set.\n\
\n\
(i.e. all elements that are in either set.)");

static PyObject *
set_or(PySetObject *so, PyObject *other)
{
	if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
		Py_INCREF(Py_NotImplemented);
		return Py_NotImplemented;
	}
	return set_union(so, other);
}

static PyObject *
set_ior(PySetObject *so, PyObject *other)
{
	if (!PyAnySet_Check(other)) {
		Py_INCREF(Py_NotImplemented);
		return Py_NotImplemented;
	}
	if (set_update_internal(so, other) == -1)
		return NULL;
	Py_INCREF(so);
	return (PyObject *)so;
}

static PyObject *
set_intersection(PySetObject *so, PyObject *other)
{
	PySetObject *result;
	PyObject *key, *it, *tmp;

	if ((PyObject *)so == other)
		return set_copy(so);

	result = (PySetObject *)make_new_set(Py_Type(so), NULL);
	if (result == NULL)
		return NULL;

	if (PyAnySet_CheckExact(other)) {		
		Py_ssize_t pos = 0;
		setentry *entry;

		if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
			tmp = (PyObject *)so;
			so = (PySetObject *)other;
			other = tmp;
		}

		while (set_next((PySetObject *)other, &pos, &entry)) {
			int rv = set_contains_entry(so, entry);
			if (rv == -1) {
				Py_DECREF(result);
				return NULL;
			}
			if (rv) {
				if (set_add_entry(result, entry) == -1) {
					Py_DECREF(result);
					return NULL;
				}
			}
		}
		return (PyObject *)result;
	}

	it = PyObject_GetIter(other);
	if (it == NULL) {
		Py_DECREF(result);
		return NULL;
	}

	while ((key = PyIter_Next(it)) != NULL) {
		int rv;
		setentry entry;
		long hash = PyObject_Hash(key);

		if (hash == -1) {
			Py_DECREF(it);
			Py_DECREF(result);
			Py_DECREF(key);
			return NULL;
		}
		entry.hash = hash;
		entry.key = key;
		rv = set_contains_entry(so, &entry);
		if (rv == -1) {
			Py_DECREF(it);
			Py_DECREF(result);
			Py_DECREF(key);
			return NULL;
		}
		if (rv) {
			if (set_add_entry(result, &entry) == -1) {
				Py_DECREF(it);
				Py_DECREF(result);
				Py_DECREF(key);
				return NULL;
			}
		}
		Py_DECREF(key);
	}
	Py_DECREF(it);
	if (PyErr_Occurred()) {
		Py_DECREF(result);
		return NULL;
	}
	return (PyObject *)result;
}

PyDoc_STRVAR(intersection_doc,
"Return the intersection of two sets as a new set.\n\
\n\
(i.e. all elements that are in both sets.)");

static PyObject *
set_intersection_update(PySetObject *so, PyObject *other)
{
	PyObject *tmp;

	tmp = set_intersection(so, other);
	if (tmp == NULL)
		return NULL;
	set_swap_bodies(so, (PySetObject *)tmp);
	Py_DECREF(tmp);
	Py_RETURN_NONE;
}

PyDoc_STRVAR(intersection_update_doc,
"Update a set with the intersection of itself and another.");

static PyObject *
set_and(PySetObject *so, PyObject *other)
{
	if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
		Py_INCREF(Py_NotImplemented);
		return Py_NotImplemented;
	}
	return set_intersection(so, other);
}

static PyObject *
set_iand(PySetObject *so, PyObject *other)
{
	PyObject *result;

	if (!PyAnySet_Check(other)) {
		Py_INCREF(Py_NotImplemented);
		return Py_NotImplemented;
	}
	result = set_intersection_update(so, other);
	if (result == NULL)
		return NULL;
	Py_DECREF(result);
	Py_INCREF(so);
	return (PyObject *)so;
}

static PyObject *
set_isdisjoint(PySetObject *so, PyObject *other)
{
	PyObject *key, *it, *tmp;

	if ((PyObject *)so == other) {
		if (PySet_GET_SIZE(so) == 0)
			Py_RETURN_TRUE;
		else
			Py_RETURN_FALSE;
	}

	if (PyAnySet_CheckExact(other)) {		
		Py_ssize_t pos = 0;
		setentry *entry;

		if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
			tmp = (PyObject *)so;
			so = (PySetObject *)other;
			other = tmp;
		}
		while (set_next((PySetObject *)other, &pos, &entry)) {
			int rv = set_contains_entry(so, entry);
			if (rv == -1)
				return NULL;
			if (rv)
				Py_RETURN_FALSE;
		}
		Py_RETURN_TRUE;
	}

	it = PyObject_GetIter(other);
	if (it == NULL)
		return NULL;

	while ((key = PyIter_Next(it)) != NULL) {
		int rv;
		setentry entry;
		long hash = PyObject_Hash(key);

		if (hash == -1) {
			Py_DECREF(key);
			Py_DECREF(it);
			return NULL;
		}
		entry.hash = hash;
		entry.key = key;
		rv = set_contains_entry(so, &entry);
		Py_DECREF(key);
		if (rv == -1) {
			Py_DECREF(it);
			return NULL;
		}
		if (rv) {
			Py_DECREF(it);
			Py_RETURN_FALSE;
		}
	}
	Py_DECREF(it);
	if (PyErr_Occurred())
		return NULL;
	Py_RETURN_TRUE;
}
{'fraction_non_alphanumeric': 0.1446095343238726, 'fraction_numerical': 0.008556051336308018, 'mean_word_length': 3.5192987318966114, 'pattern_counts': {'":': 0, '<': 61, '<?xml version=': 0, '>': 589, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2837682', 'n_tokens_mistral': 26664, 'n_tokens_neox': 24901, 'n_words': 6717}