Objects/setobject.c

/* set object implementation 
   Written and maintained by Raymond D. Hettinger <python@rcn.com>
   Derived from Lib/sets.py and Objects/dictobject.c.

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

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

/* 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() */

#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 unsigned int 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 unsigned int 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;
	}
}

/*
Internal routine to insert a new key into the table.
Used both by the internal resize routine and 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;
}

/*
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, int minused)
{
	int newsize;
	setentry *oldtable, *newtable, *entry;
	int 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;
			if(set_insert_key(so, entry->key, entry->hash) == -1) {
				if (is_oldtable_malloced)
					PyMem_DEL(oldtable);
				return -1;
			}
		}
	}

	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 int 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)
		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 int 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;
	int fill;
	setentry small_copy[PySet_MINSIZE];
#ifdef Py_DEBUG
	int 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:
 *
 *     int 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;
	int 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;
	int 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 
		so->ob_type->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 = ", ";

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

static PyObject *
set_repr(PySetObject *so)
{
	PyObject *keys, *result, *listrepr;

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

	result = PyString_FromFormat("%s(%s)", so->ob_type->tp_name,
		PyString_AS_STRING(listrepr));
	Py_DECREF(listrepr);
	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 int 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 int 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 = (int)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 */
	int si_used;
	int si_pos;
	long len;
} setiterobject;

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

static PyObject *
setiter_len(setiterobject *si)
{
	long 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 int 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 = {
	PyObject_HEAD_INIT(&PyType_Type)
	0,					/* ob_size */
	"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_Check(other))
		return set_merge(so, other);

	if (PyDict_Check(other)) {
		PyObject *value;
		Py_ssize_t pos = 0;
		while (PyDict_Next(other, &pos, &key, &value)) {
			if (set_add_key(so, key) == -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));
		so->ob_type = 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 (!_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_XDECREF(dummy);
	Py_XDECREF(emptyfrozenset);
}

static PyObject *
set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
	if (!_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)
{
	int 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(a->ob_type, &PyFrozenSet_Type)  &&
	    PyType_IsSubtype(b->ob_type, &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(so->ob_type, (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(so->ob_type, NULL);
	if (result == NULL)
		return NULL;

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

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

		while (set_next((PySetObject *)other, &pos, &entry)) {
			if (set_contains_entry(so, entry)) {
				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) {
		if (set_contains_key(so, key)) {
			if (set_add_key(result, key) == -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 int
set_difference_update_internal(PySetObject *so, PyObject *other)
{
	if ((PyObject *)so == other)
		return set_clear_internal(so);
	
	if (PyAnySet_Check(other)) {
		setentry *entry;
		Py_ssize_t pos = 0;

		while (set_next((PySetObject *)other, &pos, &entry))
			set_discard_entry(so, entry);
	} else {
		PyObject *key, *it;
		it = PyObject_GetIter(other);
		if (it == NULL)
			return -1;

		while ((key = PyIter_Next(it)) != NULL) {
			if (set_discard_key(so, key) == -1) {
				Py_DECREF(it);
				Py_DECREF(key);
				return -1;
			}
			Py_DECREF(key);
		}
		Py_DECREF(it);
		if (PyErr_Occurred())
			return -1;
	}
	/* If more than 1/5 are dummies, then resize them away. */
	if ((so->fill - so->used) * 5 < so->mask)
		return 0;
	return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
}

static PyObject *
set_difference_update(PySetObject *so, PyObject *other)
{
	if (set_difference_update_internal(so, other) != -1)
		Py_RETURN_NONE;
	return NULL;
}

PyDoc_STRVAR(difference_update_doc,
"Remove all elements of another set from this set.");

static PyObject *
set_difference(PySetObject *so, PyObject *other)
{
	PyObject *result;
	setentry *entry;
	Py_ssize_t pos = 0;

	if (!PyAnySet_Check(other)  && !PyDict_Check(other)) {
		result = set_copy(so);
		if (result == NULL)
			return NULL;
		if (set_difference_update_internal((PySetObject *)result, other) != -1)
			return result;
		Py_DECREF(result);
		return NULL;
	}
	
	result = make_new_set(so->ob_type, NULL);
	if (result == NULL)
		return NULL;

	if (PyDict_Check(other)) {
		while (set_next(so, &pos, &entry)) {
			setentry entrycopy;
			entrycopy.hash = entry->hash;
			entrycopy.key = entry->key;
			if (!PyDict_Contains(other, entry->key)) {
				if (set_add_entry((PySetObject *)result, &entrycopy) == -1)
					return NULL;
			}
		}
		return result;
	}

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

PyDoc_STRVAR(difference_doc,
"Return the difference of two sets as a new set.\n\
\n\
(i.e. all elements that are in this set but not the other.)");
static PyObject *
set_sub(PySetObject *so, PyObject *other)
{
	if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
		Py_INCREF(Py_NotImplemented);
		return Py_NotImplemented;
	}
	return set_difference(so, other);
}

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

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

static PyObject *
set_symmetric_difference_update(PySetObject *so, PyObject *other)
{
	PySetObject *otherset;
	PyObject *key;
	Py_ssize_t pos = 0;
	setentry *entry;

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

	if (PyDict_Check(other)) {
		PyObject *value;
		int rv;
		while (PyDict_Next(other, &pos, &key, &value)) {
			rv = set_discard_key(so, key);
			if (rv == -1)
				return NULL;
			if (rv == DISCARD_NOTFOUND) {
				if (set_add_key(so, key) == -1)
					return NULL;
			}
		}
		Py_RETURN_NONE;
	}

	if (PyAnySet_Check(other)) {
		Py_INCREF(other);
		otherset = (PySetObject *)other;
	} else {
		otherset = (PySetObject *)make_new_set(so->ob_type, other);
		if (otherset == NULL)
			return NULL;
	}

	while (set_next(otherset, &pos, &entry)) {
		int rv = set_discard_entry(so, entry);
		if (rv == -1) {
			Py_XDECREF(otherset);
			return NULL;
		}
		if (rv == DISCARD_NOTFOUND) {
			if (set_add_entry(so, entry) == -1) {
				Py_XDECREF(otherset);
				return NULL;
			}
		}
	}
	Py_DECREF(otherset);
	Py_RETURN_NONE;
}

PyDoc_STRVAR(symmetric_difference_update_doc,
"Update a set with the symmetric difference of itself and another.");

static PyObject *
set_symmetric_difference(PySetObject *so, PyObject *other)
{
	PyObject *rv;
	PySetObject *otherset;

	otherset = (PySetObject *)make_new_set(so->ob_type, other);
	if (otherset == NULL)
		return NULL;
	rv = set_symmetric_difference_update(otherset, (PyObject *)so);
	if (rv == NULL)
		return NULL;
	Py_DECREF(rv);
	return (PyObject *)otherset;
}

PyDoc_STRVAR(symmetric_difference_doc,
"Return the symmetric difference of two sets as a new set.\n\
\n\
(i.e. all elements that are in exactly one of the sets.)");

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

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

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

static PyObject *
set_issubset(PySetObject *so, PyObject *other)
{
	setentry *entry;
	Py_ssize_t pos = 0;

	if (!PyAnySet_Check(other)) {
		PyObject *tmp, *result;
		tmp = make_new_set(&PySet_Type, other);
		if (tmp == NULL)
			return NULL;
		result = set_issubset(so, tmp);
		Py_DECREF(tmp);
		return result;
	}
	if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other)) 
		Py_RETURN_FALSE;

	while (set_next(so, &pos, &entry)) {
		if (!set_contains_entry((PySetObject *)other, entry))
			Py_RETURN_FALSE;
	}
	Py_RETURN_TRUE;
}

PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");

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

	if (!PyAnySet_Check(other)) {
		tmp = make_new_set(&PySet_Type, other);
		if (tmp == NULL)
			return NULL;
		result = set_issuperset(so, tmp);
		Py_DECREF(tmp);
		return result;
	}
	return set_issubset((PySetObject *)other, (PyObject *)so);
}

PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");

static PyObject *
set_richcompare(PySetObject *v, PyObject *w, int op)
{
	PyObject *r1, *r2;

	if(!PyAnySet_Check(w)) {
		if (op == Py_EQ)
			Py_RETURN_FALSE;
		if (op == Py_NE)
			Py_RETURN_TRUE;
		PyErr_SetString(PyExc_TypeError, "can only compare to a set");
		return NULL;
	}
	switch (op) {
	case Py_EQ:
		if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
			Py_RETURN_FALSE;
		if (v->hash != -1  &&
		    ((PySetObject *)w)->hash != -1 &&
		    v->hash != ((PySetObject *)w)->hash)
			Py_RETURN_FALSE;
		return set_issubset(v, w);
	case Py_NE:
		r1 = set_richcompare(v, w, Py_EQ);
		if (r1 == NULL)
			return NULL;
		r2 = PyBool_FromLong(PyObject_Not(r1));
		Py_DECREF(r1);
		return r2;
	case Py_LE:
		return set_issubset(v, w);
	case Py_GE:
		return set_issuperset(v, w);
	case Py_LT:
		if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))
			Py_RETURN_FALSE;		
		return set_issubset(v, w);
	case Py_GT:
		if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
			Py_RETURN_FALSE;
		return set_issuperset(v, w);
	}
	Py_INCREF(Py_NotImplemented);
	return Py_NotImplemented;
}

static int
set_nocmp(PyObject *self, PyObject *other)
{
	PyErr_SetString(PyExc_TypeError, "cannot compare sets using cmp()");
	return -1;
}

static PyObject *
set_add(PySetObject *so, PyObject *key)
{
	if (set_add_key(so, key) == -1)
		return NULL;
	Py_RETURN_NONE;
}

PyDoc_STRVAR(add_doc, 
"Add an element to a set.\n\
\n\
This has no effect if the element is already present.");

static int
set_contains(PySetObject *so, PyObject *key)
{
	PyObject *tmpkey;
	int rv;

	rv = set_contains_key(so, key);
	if (rv == -1) {
		if (!PyAnySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
			return -1;
		PyErr_Clear();
		tmpkey = make_new_set(&PyFrozenSet_Type, NULL);
		if (tmpkey == NULL)
			return -1;
		set_swap_bodies((PySetObject *)tmpkey, (PySetObject *)key);
		rv = set_contains(so, tmpkey);
		set_swap_bodies((PySetObject *)tmpkey, (PySetObject *)key);
		Py_DECREF(tmpkey);
	}
	return rv;
}

static PyObject *
set_direct_contains(PySetObject *so, PyObject *key)
{
	long result;

	result = set_contains(so, key);
	if (result == -1)
		return NULL;
	return PyBool_FromLong(result);
}

PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");

static PyObject *
set_remove(PySetObject *so, PyObject *key)
{
	PyObject *tmpkey, *result;
	int rv;

	rv = set_discard_key(so, key);
	if (rv == -1) {
		if (!PyAnySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
			return NULL;
		PyErr_Clear();
		tmpkey = make_new_set(&PyFrozenSet_Type, NULL);
		if (tmpkey == NULL)
			return NULL;
		set_swap_bodies((PySetObject *)tmpkey, (PySetObject *)key);
		result = set_remove(so, tmpkey);
		set_swap_bodies((PySetObject *)tmpkey, (PySetObject *)key);
		Py_DECREF(tmpkey);
		return result;
	} else if (rv == DISCARD_NOTFOUND) {
		PyErr_SetObject(PyExc_KeyError, key);
		return NULL;
	}
	Py_RETURN_NONE;
}

PyDoc_STRVAR(remove_doc,
"Remove an element from a set; it must be a member.\n\
\n\
If the element is not a member, raise a KeyError.");

static PyObject *
set_discard(PySetObject *so, PyObject *key)
{
	PyObject *tmpkey, *result;
	int rv;

	rv = set_discard_key(so, key);
	if (rv == -1) {
		if (!PyAnySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
			return NULL;
		PyErr_Clear();
		tmpkey = make_new_set(&PyFrozenSet_Type, NULL);
		if (tmpkey == NULL)
			return NULL;
		set_swap_bodies((PySetObject *)tmpkey, (PySetObject *)key);
		result = set_discard(so, tmpkey);
		set_swap_bodies((PySetObject *)tmpkey, (PySetObject *)key);
		Py_DECREF(tmpkey);
		return result;
	}
	Py_RETURN_NONE;
}

PyDoc_STRVAR(discard_doc,
"Remove an element from a set if it is a member.\n\
\n\
If the element is not a member, do nothing."); 

static PyObject *
set_reduce(PySetObject *so)
{
	PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;

	keys = PySequence_List((PyObject *)so);
	if (keys == NULL)
		goto done;
	args = PyTuple_Pack(1, keys);
	if (args == NULL)
		goto done;
	dict = PyObject_GetAttrString((PyObject *)so, "__dict__");
	if (dict == NULL) {
		PyErr_Clear();
		dict = Py_None;
		Py_INCREF(dict);
	}
	result = PyTuple_Pack(3, so->ob_type, args, dict);
done:
	Py_XDECREF(args);
	Py_XDECREF(keys);
	Py_XDECREF(dict);
	return result;
}

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

static int
set_init(PySetObject *self, PyObject *args, PyObject *kwds)
{
	PyObject *iterable = NULL;

	if (!PyAnySet_Check(self))
		return -1;
	if (!PyArg_UnpackTuple(args, self->ob_type->tp_name, 0, 1, &iterable))
		return -1;
	set_clear_internal(self);
	self->hash = -1;
	if (iterable == NULL)
		return 0;
	return set_update_internal(self, iterable);
}

static PySequenceMethods set_as_sequence = {
	set_len,			/* sq_length */
	0,				/* sq_concat */
	0,				/* sq_repeat */
	0,				/* sq_item */
	0,				/* sq_slice */
	0,				/* sq_ass_item */
	0,				/* sq_ass_slice */
	(objobjproc)set_contains,	/* sq_contains */
};

/* set object ********************************************************/

#ifdef Py_DEBUG
static PyObject *test_c_api(PySetObject *so);

PyDoc_STRVAR(test_c_api_doc, "Exercises C API.  Returns True.\n\
All is well if assertions don't fail.");
#endif

static PyMethodDef set_methods[] = {
	{"add",		(PyCFunction)set_add,		METH_O,
	 add_doc},
	{"clear",	(PyCFunction)set_clear,		METH_NOARGS,
	 clear_doc},
	{"__contains__",(PyCFunction)set_direct_contains,	METH_O | METH_COEXIST,
	 contains_doc},
	{"copy",	(PyCFunction)set_copy,		METH_NOARGS,
	 copy_doc},
	{"discard",	(PyCFunction)set_discard,	METH_O,
	 discard_doc},
	{"difference",	(PyCFunction)set_difference,	METH_O,
	 difference_doc},
	{"difference_update",	(PyCFunction)set_difference_update,	METH_O,
	 difference_update_doc},
	{"intersection",(PyCFunction)set_intersection,	METH_O,
	 intersection_doc},
	{"intersection_update",(PyCFunction)set_intersection_update,	METH_O,
	 intersection_update_doc},
	{"issubset",	(PyCFunction)set_issubset,	METH_O,
	 issubset_doc},
	{"issuperset",	(PyCFunction)set_issuperset,	METH_O,
	 issuperset_doc},
	{"pop",		(PyCFunction)set_pop,		METH_NOARGS,
	 pop_doc},
	{"__reduce__",	(PyCFunction)set_reduce,	METH_NOARGS,
	 reduce_doc},
	{"remove",	(PyCFunction)set_remove,	METH_O,
	 remove_doc},
	{"symmetric_difference",(PyCFunction)set_symmetric_difference,	METH_O,
	 symmetric_difference_doc},
	{"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update,	METH_O,
	 symmetric_difference_update_doc},
#ifdef Py_DEBUG
	{"test_c_api",	(PyCFunction)test_c_api,	METH_NOARGS,
	 test_c_api_doc},
#endif
	{"union",	(PyCFunction)set_union,		METH_O,
	 union_doc},
	{"update",	(PyCFunction)set_update,	METH_O,
	 update_doc},
	{NULL,		NULL}	/* sentinel */
};

static PyNumberMethods set_as_number = {
	0,				/*nb_add*/
	(binaryfunc)set_sub,		/*nb_subtract*/
	0,				/*nb_multiply*/
	0,				/*nb_divide*/
	0,				/*nb_remainder*/
	0,				/*nb_divmod*/
	0,				/*nb_power*/
	0,				/*nb_negative*/
	0,				/*nb_positive*/
	0,				/*nb_absolute*/
	0,				/*nb_nonzero*/
	0,				/*nb_invert*/
	0,				/*nb_lshift*/
	0,				/*nb_rshift*/
	(binaryfunc)set_and,		/*nb_and*/
	(binaryfunc)set_xor,		/*nb_xor*/
	(binaryfunc)set_or,		/*nb_or*/
	0,				/*nb_coerce*/
	0,				/*nb_int*/
	0,				/*nb_long*/
	0,				/*nb_float*/
	0,				/*nb_oct*/
	0, 				/*nb_hex*/
	0,				/*nb_inplace_add*/
	(binaryfunc)set_isub,		/*nb_inplace_subtract*/
	0,				/*nb_inplace_multiply*/
	0,				/*nb_inplace_divide*/
	0,				/*nb_inplace_remainder*/
	0,				/*nb_inplace_power*/
	0,				/*nb_inplace_lshift*/
	0,				/*nb_inplace_rshift*/
	(binaryfunc)set_iand,		/*nb_inplace_and*/
	(binaryfunc)set_ixor,		/*nb_inplace_xor*/
	(binaryfunc)set_ior,		/*nb_inplace_or*/
};

PyDoc_STRVAR(set_doc,
"set(iterable) --> set object\n\
\n\
Build an unordered collection.");

PyTypeObject PySet_Type = {
	PyObject_HEAD_INIT(&PyType_Type)
	0,				/* ob_size */
	"set",				/* tp_name */
	sizeof(PySetObject),		/* tp_basicsize */
	0,				/* tp_itemsize */
	/* methods */
	(destructor)set_dealloc,	/* tp_dealloc */
	(printfunc)set_tp_print,	/* tp_print */
	0,				/* tp_getattr */
	0,				/* tp_setattr */
	set_nocmp,			/* tp_compare */
	(reprfunc)set_repr,		/* tp_repr */
	&set_as_number,			/* tp_as_number */
	&set_as_sequence,		/* tp_as_sequence */
	0,				/* tp_as_mapping */
	set_nohash,			/* tp_hash */
	0,				/* tp_call */
	0,				/* tp_str */
	PyObject_GenericGetAttr,	/* tp_getattro */
	0,				/* tp_setattro */
	0,				/* tp_as_buffer */
	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_CHECKTYPES |
		Py_TPFLAGS_BASETYPE,	/* tp_flags */
	set_doc,			/* tp_doc */
	(traverseproc)set_traverse,	/* tp_traverse */
	(inquiry)set_clear_internal,	/* tp_clear */
	(richcmpfunc)set_richcompare,	/* tp_richcompare */
	offsetof(PySetObject, weakreflist),	/* tp_weaklistoffset */
	(getiterfunc)set_iter,	/* tp_iter */
	0,				/* tp_iternext */
	set_methods,			/* tp_methods */
	0,				/* tp_members */
	0,				/* tp_getset */
	0,				/* tp_base */
	0,				/* tp_dict */
	0,				/* tp_descr_get */
	0,				/* tp_descr_set */
	0,				/* tp_dictoffset */
	(initproc)set_init,		/* tp_init */
	PyType_GenericAlloc,		/* tp_alloc */
	set_new,			/* tp_new */
	PyObject_GC_Del,		/* tp_free */
};

/* frozenset object ********************************************************/


static PyMethodDef frozenset_methods[] = {
	{"__contains__",(PyCFunction)set_direct_contains,	METH_O | METH_COEXIST,
	 contains_doc},
	{"copy",	(PyCFunction)frozenset_copy,	METH_NOARGS,
	 copy_doc},
	{"difference",	(PyCFunction)set_difference,	METH_O,
	 difference_doc},
	{"intersection",(PyCFunction)set_intersection,	METH_O,
	 intersection_doc},
	{"issubset",	(PyCFunction)set_issubset,	METH_O,
	 issubset_doc},
	{"issuperset",	(PyCFunction)set_issuperset,	METH_O,
	 issuperset_doc},
	{"__reduce__",	(PyCFunction)set_reduce,	METH_NOARGS,
	 reduce_doc},
	{"symmetric_difference",(PyCFunction)set_symmetric_difference,	METH_O,
	 symmetric_difference_doc},
	{"union",	(PyCFunction)set_union,		METH_O,
	 union_doc},
	{NULL,		NULL}	/* sentinel */
};

static PyNumberMethods frozenset_as_number = {
	0,				/*nb_add*/
	(binaryfunc)set_sub,		/*nb_subtract*/
	0,				/*nb_multiply*/
	0,				/*nb_divide*/
	0,				/*nb_remainder*/
	0,				/*nb_divmod*/
	0,				/*nb_power*/
	0,				/*nb_negative*/
	0,				/*nb_positive*/
	0,				/*nb_absolute*/
	0,				/*nb_nonzero*/
	0,				/*nb_invert*/
	0,				/*nb_lshift*/
	0,				/*nb_rshift*/
	(binaryfunc)set_and,		/*nb_and*/
	(binaryfunc)set_xor,		/*nb_xor*/
	(binaryfunc)set_or,		/*nb_or*/
};

PyDoc_STRVAR(frozenset_doc,
"frozenset(iterable) --> frozenset object\n\
\n\
Build an immutable unordered collection.");

PyTypeObject PyFrozenSet_Type = {
	PyObject_HEAD_INIT(&PyType_Type)
	0,				/* ob_size */
	"frozenset",			/* tp_name */
	sizeof(PySetObject),		/* tp_basicsize */
	0,				/* tp_itemsize */
	/* methods */
	(destructor)set_dealloc,	/* tp_dealloc */
	(printfunc)set_tp_print,	/* tp_print */
	0,				/* tp_getattr */
	0,				/* tp_setattr */
	set_nocmp,			/* tp_compare */
	(reprfunc)set_repr,		/* tp_repr */
	&frozenset_as_number,		/* tp_as_number */
	&set_as_sequence,		/* tp_as_sequence */
	0,				/* tp_as_mapping */
	frozenset_hash,			/* tp_hash */
	0,				/* tp_call */
	0,				/* tp_str */
	PyObject_GenericGetAttr,	/* tp_getattro */
	0,				/* tp_setattro */
	0,				/* tp_as_buffer */
	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_CHECKTYPES |
		Py_TPFLAGS_BASETYPE,	/* tp_flags */
	frozenset_doc,			/* tp_doc */
	(traverseproc)set_traverse,	/* tp_traverse */
	(inquiry)set_clear_internal,	/* tp_clear */
	(richcmpfunc)set_richcompare,	/* tp_richcompare */
	offsetof(PySetObject, weakreflist),	/* tp_weaklistoffset */
	(getiterfunc)set_iter,		/* tp_iter */
	0,				/* tp_iternext */
	frozenset_methods,		/* tp_methods */
	0,				/* tp_members */
	0,				/* tp_getset */
	0,				/* tp_base */
	0,				/* tp_dict */
	0,				/* tp_descr_get */
	0,				/* tp_descr_set */
	0,				/* tp_dictoffset */
	0,				/* tp_init */
	PyType_GenericAlloc,		/* tp_alloc */
	frozenset_new,			/* tp_new */
	PyObject_GC_Del,		/* tp_free */
};


/***** C API functions *************************************************/

PyObject *
PySet_New(PyObject *iterable)
{
	return make_new_set(&PySet_Type, iterable);
}

PyObject *
PyFrozenSet_New(PyObject *iterable)
{
	PyObject *args, *result;

	if (iterable == NULL)
		args = PyTuple_New(0);
	else
		args = PyTuple_Pack(1, iterable);
	if (args == NULL)
		return NULL;
	result = frozenset_new(&PyFrozenSet_Type, args, NULL);
	Py_DECREF(args);
	return result;
}

Py_ssize_t
PySet_Size(PyObject *anyset)
{
	if (!PyAnySet_Check(anyset)) {
		PyErr_BadInternalCall();
		return -1;
	}
	return PySet_GET_SIZE(anyset);
}

int
PySet_Clear(PyObject *set)
{
	if (!PyType_IsSubtype(set->ob_type, &PySet_Type)) {
		PyErr_BadInternalCall();
		return -1;
	}
	return set_clear_internal((PySetObject *)set);
}

int
PySet_Contains(PyObject *anyset, PyObject *key)
{
	if (!PyAnySet_Check(anyset)) {
		PyErr_BadInternalCall();
		return -1;
	}
	return set_contains_key((PySetObject *)anyset, key);
}

int
PySet_Discard(PyObject *set, PyObject *key)
{
	if (!PyType_IsSubtype(set->ob_type, &PySet_Type)) {
		PyErr_BadInternalCall();
		return -1;
	}
	return set_discard_key((PySetObject *)set, key);
}

int
PySet_Add(PyObject *set, PyObject *key)
{
	if (!PyType_IsSubtype(set->ob_type, &PySet_Type)) {
		PyErr_BadInternalCall();
		return -1;
	}
	return set_add_key((PySetObject *)set, key);
}

int
_PySet_Next(PyObject *set, Py_ssize_t *pos, PyObject **entry)
{
	setentry *entry_ptr;

	if (!PyAnySet_Check(set)) {
		PyErr_BadInternalCall();
		return -1;
	}
	if (set_next((PySetObject *)set, pos, &entry_ptr) == 0)
		return 0;
	*entry = entry_ptr->key;
	return 1;
}

PyObject *
PySet_Pop(PyObject *set)
{
	if (!PyType_IsSubtype(set->ob_type, &PySet_Type)) {
		PyErr_BadInternalCall();
		return NULL;
	}
	return set_pop((PySetObject *)set);
}

int
_PySet_Update(PyObject *set, PyObject *iterable)
{
	if (!PyType_IsSubtype(set->ob_type, &PySet_Type)) {
		PyErr_BadInternalCall();
		return -1;
	}
	return set_update_internal((PySetObject *)set, iterable);
}

#ifdef Py_DEBUG

/* Test code to be called with any three element set. 
   Returns True and original set is restored. */

#define assertRaises(call_return_value, exception)		\
	do {							\
		assert(call_return_value);			\
		assert(PyErr_ExceptionMatches(exception));	\
		PyErr_Clear();					\
	} while(0)

static PyObject *
test_c_api(PySetObject *so)
{
	int count;
	char *s;
	Py_ssize_t i;
	PyObject *elem, *dup, *t, *f, *dup2;
	PyObject *ob = (PyObject *)so;

	/* Verify preconditions and exercise type/size checks */
	assert(PyAnySet_Check(ob));
	assert(PyAnySet_CheckExact(ob));
	assert(!PyFrozenSet_CheckExact(ob));
	assert(PySet_Size(ob) == 3);
	assert(PySet_GET_SIZE(ob) == 3);

	/* Raise TypeError for non-iterable constructor arguments */
	assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
	assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);

	/* Raise TypeError for unhashable key */
	dup = PySet_New(ob);
	assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
	assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
	assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);

	/* Exercise successful pop, contains, add, and discard */
	elem = PySet_Pop(ob);
	assert(PySet_Contains(ob, elem) == 0);
	assert(PySet_GET_SIZE(ob) == 2);
	assert(PySet_Add(ob, elem) == 0);
	assert(PySet_Contains(ob, elem) == 1);
	assert(PySet_GET_SIZE(ob) == 3);
	assert(PySet_Discard(ob, elem) == 1);
	assert(PySet_GET_SIZE(ob) == 2);
	assert(PySet_Discard(ob, elem) == 0);
	assert(PySet_GET_SIZE(ob) == 2);

	/* Exercise clear */
	dup2 = PySet_New(dup);
	assert(PySet_Clear(dup2) == 0);
	assert(PySet_Size(dup2) == 0);
	Py_DECREF(dup2);

	/* Raise SystemError on clear or update of frozen set */
	f = PyFrozenSet_New(dup);
	assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
	assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
	Py_DECREF(f);

	/* Exercise direct iteration */
	i = 0, count = 0;
	while (_PySet_Next((PyObject *)dup, &i, &elem)) {
		s = PyString_AsString(elem);
		assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
		count++;
	}
	assert(count == 3);

	/* Exercise updates */
	dup2 = PySet_New(NULL);
	assert(_PySet_Update(dup2, dup) == 0);
	assert(PySet_Size(dup2) == 3);
	assert(_PySet_Update(dup2, dup) == 0);
	assert(PySet_Size(dup2) == 3);
	Py_DECREF(dup2);

	/* Raise SystemError when self argument is not a set or frozenset. */
	t = PyTuple_New(0);
	assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
	assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
	Py_DECREF(t);

	/* Raise SystemError when self argument is not a set. */
	f = PyFrozenSet_New(dup);
	assert(PySet_Size(f) == 3);
	assert(PyFrozenSet_CheckExact(f));
	assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
	assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
	assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
	Py_DECREF(f);

	/* Raise KeyError when popping from an empty set */
	assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
	Py_DECREF(ob);
	assert(PySet_GET_SIZE(ob) == 0);
	assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);

	/* Restore the set from the copy using the PyNumber API */
	assert(PyNumber_InPlaceOr(ob, dup) == ob);
	Py_DECREF(ob);

	/* Verify constructors accept NULL arguments */
	f = PySet_New(NULL);
	assert(f != NULL);
	assert(PySet_GET_SIZE(f) == 0);
	Py_DECREF(f);
	f = PyFrozenSet_New(NULL);
	assert(f != NULL);
	assert(PyFrozenSet_CheckExact(f));
	assert(PySet_GET_SIZE(f) == 0);
	Py_DECREF(f);

	Py_DECREF(elem);
	Py_DECREF(dup);
	Py_RETURN_TRUE;
}

#undef assertRaises

#endif