} 	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 intset_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 voidset_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 		so->ob_type->tp_free(so);	Py_TRASHCAN_SAFE_END(so)} static intset_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;		fprintf(fp, "%s(...)", so->ob_type->tp_name);		return 0;	}         	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) {			Py_ReprLeave((PyObject*)so);			return -1;		}	}	fputs("])", fp);	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_tset_len(PyObject *so){	return ((PySetObject *)so)->used;} static intset_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 intset_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 intset_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 intset_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 longfrozenset_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 longset_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 voidsetiter_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 = {	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 intset_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		* 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));		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);

Lines 501–1000 of 2312. Previous lines Load more