#include "Python.h"

#include "structmember.h"

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);

}

#define PERTURB_SHIFT 5

static PyObject *dummy = NULL; /* Initialized by first call to make_new_set() */

#ifdef Py_REF_DEBUG

PyObject *

_PySet_Dummy(void)

{

return dummy;

}

#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)

#ifndef PySet_MAXFREELIST

#define PySet_MAXFREELIST 80

static PySetObject *free_list[PySet_MAXFREELIST];

static int numfree = 0;

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;

Py_INCREF(startkey);

cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);

Py_DECREF(startkey);

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

return set_lookkey(so, key, hash);

}

}

freeslot = NULL;

}

/* In the loop, key == dummy is by far (factor of 100s) the

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;

Py_INCREF(startkey);

cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);

Py_DECREF(startkey);

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

return set_lookkey(so, key, hash);

}

}

else if (entry->key == dummy && freeslot == NULL)

freeslot = entry;

}

return entry;

}

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,

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

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;

}

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;

}

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++;

}

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

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;

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;

}

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;

table = so->table;

assert(table != NULL);

table_is_malloced = table != so->smalltable;

/* This is delicate. During the process of clearing the set,

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.

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

for (entry = table; fill > 0; ++entry) {

#ifdef Py_DEBUG

assert(i < n);

++i;

if (entry->key) {

--fill;

Py_DECREF(entry->key);

}

#ifdef Py_DEBUG

else

assert(entry->key == NULL);

}

if (table_is_malloced)

PyMem_DEL(table);

return 0;

}

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 (numfree < PySet_MAXFREELIST && PyAnySet_CheckExact(so))

free_list[numfree++] = 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);

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

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

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

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.\n\

Raises KeyError if the set is empty.");

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

h = entry->hash;

hash ^= (h ^ (h << 16) ^ 89869747L) * 3644798167u;

}

hash = hash * 69069L + 907133923L;

if (hash == -1)

hash = 590923713L;

so->hash = hash;

return hash;

}

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_GC_Del(si);

}

static int

setiter_traverse(setiterobject *si, visitproc visit, void *arg)

{

Py_VISIT(si->si_set);

return 0;

}

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 | Py_TPFLAGS_HAVE_GC,/* tp_flags */

0, /* tp_doc */

(traverseproc)setiter_traverse, /* tp_traverse */

0, /* tp_clear */

0, /* tp_richcompare */

0, /* tp_weaklistoffset */

PyObject_SelfIter, /* tp_iter */

(iternextfunc)setiter_iternext, /* tp_iternext */

setiter_methods, /* tp_methods */

0,

};

static PyObject *

set_iter(PySetObject *so)

{

setiterobject *si = PyObject_GC_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;

_PyObject_GC_TRACK(si);

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_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

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 *args)

{

Py_ssize_t i;

for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {

PyObject *other = PyTuple_GET_ITEM(args, i);

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 others.");

static PyObject *

make_new_set(PyTypeObject *type, PyObject *iterable)

{

register PySetObject *so = NULL;

if (dummy == NULL) { /* Auto-initialize dummy */

dummy = PyString_FromString("<dummy key>");