153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* set object implementation 353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Written and maintained by Raymond D. Hettinger <python@rcn.com> 453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Derived from Lib/sets.py and Objects/dictobject.c. 553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Copyright (c) 2003-2007 Python Software Foundation. 753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel All rights reserved. 853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel*/ 953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 1053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#include "Python.h" 1153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#include "structmember.h" 1253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 1353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* Set a key error with the specified argument, wrapping it in a 1453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * tuple automatically so that tuple keys are not unpacked as the 1553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * exception arguments. */ 1653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic void 1753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_key_error(PyObject *arg) 1853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 1953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *tup; 2053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel tup = PyTuple_Pack(1, arg); 2153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!tup) 2253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return; /* caller will expect error to be set anyway */ 2353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_SetObject(PyExc_KeyError, tup); 2453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(tup); 2553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 2653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 2753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* This must be >= 1. */ 2853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#define PERTURB_SHIFT 5 2953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 3053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* Object used as dummy key to fill deleted entries */ 3153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject *dummy = NULL; /* Initialized by first call to make_new_set() */ 3253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 3353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#ifdef Py_REF_DEBUG 3453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyObject * 3553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel_PySet_Dummy(void) 3653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 3753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return dummy; 3853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 3953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#endif 4053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 4153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#define INIT_NONZERO_SET_SLOTS(so) do { \ 4253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (so)->table = (so)->smalltable; \ 4353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (so)->mask = PySet_MINSIZE - 1; \ 4453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (so)->hash = -1; \ 4553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } while(0) 4653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 4753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#define EMPTY_TO_MINSIZE(so) do { \ 4853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel memset((so)->smalltable, 0, sizeof((so)->smalltable)); \ 4953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (so)->used = (so)->fill = 0; \ 5053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel INIT_NONZERO_SET_SLOTS(so); \ 5153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } while(0) 5253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 5353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* Reuse scheme to save calls to malloc, free, and memset */ 5453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#ifndef PySet_MAXFREELIST 5553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#define PySet_MAXFREELIST 80 5653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#endif 5753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PySetObject *free_list[PySet_MAXFREELIST]; 5853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int numfree = 0; 5953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 6053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* 6153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielThe basic lookup function used by all operations. 6253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielThis is based on Algorithm D from Knuth Vol. 3, Sec. 6.4. 6353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielOpen addressing is preferred over chaining since the link overhead for 6453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielchaining would be substantial (100% with typical malloc overhead). 6553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 6653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielThe initial probe index is computed as hash mod the table size. Subsequent 6753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielprobe indices are computed as explained in Objects/dictobject.c. 6853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 6953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielAll arithmetic on hash should ignore overflow. 7053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 7153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielUnlike the dictionary implementation, the lookkey functions can return 7253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielNULL if the rich comparison returns an error. 7353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel*/ 7453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 7553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic setentry * 7653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_lookkey(PySetObject *so, PyObject *key, register long hash) 7753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 7853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register Py_ssize_t i; 7953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register size_t perturb; 8053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register setentry *freeslot; 8153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register size_t mask = so->mask; 8253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *table = so->table; 8353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register setentry *entry; 8453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register int cmp; 8553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *startkey; 8653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 8753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i = hash & mask; 8853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry = &table[i]; 8953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->key == NULL || entry->key == key) 9053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return entry; 9153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 9253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->key == dummy) 9353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel freeslot = entry; 9453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel else { 9553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->hash == hash) { 9653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel startkey = entry->key; 9753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(startkey); 9853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); 9953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(startkey); 10053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (cmp < 0) 10153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 10253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (table == so->table && entry->key == startkey) { 10353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (cmp > 0) 10453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return entry; 10553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 10653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel else { 10753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* The compare did major nasty stuff to the 10853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * set: start over. 10953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel */ 11053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_lookkey(so, key, hash); 11153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 11253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 11353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel freeslot = NULL; 11453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 11553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 11653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* In the loop, key == dummy is by far (factor of 100s) the 11753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel least likely outcome, so test for that last. */ 11853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel for (perturb = hash; ; perturb >>= PERTURB_SHIFT) { 11953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i = (i << 2) + i + perturb + 1; 12053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry = &table[i & mask]; 12153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->key == NULL) { 12253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (freeslot != NULL) 12353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry = freeslot; 12453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel break; 12553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 12653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->key == key) 12753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel break; 12853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->hash == hash && entry->key != dummy) { 12953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel startkey = entry->key; 13053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(startkey); 13153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); 13253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(startkey); 13353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (cmp < 0) 13453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 13553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (table == so->table && entry->key == startkey) { 13653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (cmp > 0) 13753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel break; 13853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 13953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel else { 14053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* The compare did major nasty stuff to the 14153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * set: start over. 14253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel */ 14353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_lookkey(so, key, hash); 14453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 14553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 14653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel else if (entry->key == dummy && freeslot == NULL) 14753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel freeslot = entry; 14853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 14953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return entry; 15053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 15153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 15253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* 15353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * Hacked up version of set_lookkey which can assume keys are always strings; 15453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * This means we can always use _PyString_Eq directly and not have to check to 15553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * see if the comparison altered the table. 15653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel */ 15753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic setentry * 15853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_lookkey_string(PySetObject *so, PyObject *key, register long hash) 15953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 16053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register Py_ssize_t i; 16153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register size_t perturb; 16253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register setentry *freeslot; 16353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register size_t mask = so->mask; 16453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *table = so->table; 16553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register setentry *entry; 16653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 16753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Make sure this function doesn't have to handle non-string keys, 16853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel including subclasses of str; e.g., one reason to subclass 16953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel strings is to override __eq__, and for speed we don't cater to 17053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel that here. */ 17153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyString_CheckExact(key)) { 17253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->lookup = set_lookkey; 17353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_lookkey(so, key, hash); 17453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 17553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i = hash & mask; 17653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry = &table[i]; 17753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->key == NULL || entry->key == key) 17853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return entry; 17953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->key == dummy) 18053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel freeslot = entry; 18153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel else { 18253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->hash == hash && _PyString_Eq(entry->key, key)) 18353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return entry; 18453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel freeslot = NULL; 18553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 18653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 18753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* In the loop, key == dummy is by far (factor of 100s) the 18853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel least likely outcome, so test for that last. */ 18953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel for (perturb = hash; ; perturb >>= PERTURB_SHIFT) { 19053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i = (i << 2) + i + perturb + 1; 19153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry = &table[i & mask]; 19253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->key == NULL) 19353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return freeslot == NULL ? entry : freeslot; 19453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->key == key 19553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel || (entry->hash == hash 19653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel && entry->key != dummy 19753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel && _PyString_Eq(entry->key, key))) 19853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return entry; 19953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->key == dummy && freeslot == NULL) 20053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel freeslot = entry; 20153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 20253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(0); /* NOT REACHED */ 20353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 20453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 20553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 20653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* 20753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielInternal routine to insert a new key into the table. 20853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielUsed by the public insert routine. 20953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielEats a reference to key. 21053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel*/ 21153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 21253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_insert_key(register PySetObject *so, PyObject *key, long hash) 21353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 21453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register setentry *entry; 21553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 21653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(so->lookup != NULL); 21753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry = so->lookup(so, key, hash); 21853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry == NULL) 21953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 22053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->key == NULL) { 22153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* UNUSED */ 22253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->fill++; 22353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry->key = key; 22453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry->hash = hash; 22553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->used++; 22653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } else if (entry->key == dummy) { 22753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* DUMMY */ 22853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry->key = key; 22953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry->hash = hash; 23053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->used++; 23153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(dummy); 23253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } else { 23353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* ACTIVE */ 23453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 23553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 23653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 23753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 23853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 23953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* 24053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielInternal routine used by set_table_resize() to insert an item which is 24153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielknown to be absent from the set. This routine also assumes that 24253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielthe set contains no deleted entries. Besides the performance benefit, 24353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielusing set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209). 24453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielNote that no refcounts are changed by this routine; if needed, the caller 24553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielis responsible for incref'ing `key`. 24653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel*/ 24753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic void 24853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_insert_clean(register PySetObject *so, PyObject *key, long hash) 24953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 25053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register size_t i; 25153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register size_t perturb; 25253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register size_t mask = (size_t)so->mask; 25353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *table = so->table; 25453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register setentry *entry; 25553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 25653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i = hash & mask; 25753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry = &table[i]; 25853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) { 25953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i = (i << 2) + i + perturb + 1; 26053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry = &table[i & mask]; 26153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 26253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->fill++; 26353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry->key = key; 26453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry->hash = hash; 26553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->used++; 26653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 26753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 26853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* 26953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielRestructure the table by allocating a new table and reinserting all 27053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielkeys again. When entries have been deleted, the new table may 27153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielactually be smaller than the old one. 27253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel*/ 27353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 27453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_table_resize(PySetObject *so, Py_ssize_t minused) 27553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 27653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t newsize; 27753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *oldtable, *newtable, *entry; 27853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t i; 27953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel int is_oldtable_malloced; 28053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry small_copy[PySet_MINSIZE]; 28153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 28253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(minused >= 0); 28353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 28453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Find the smallest table size > minused. */ 28553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel for (newsize = PySet_MINSIZE; 28653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel newsize <= minused && newsize > 0; 28753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel newsize <<= 1) 28853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel ; 28953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (newsize <= 0) { 29053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_NoMemory(); 29153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 29253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 29353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 29453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Get space for a new table. */ 29553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel oldtable = so->table; 29653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(oldtable != NULL); 29753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel is_oldtable_malloced = oldtable != so->smalltable; 29853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 29953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (newsize == PySet_MINSIZE) { 30053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* A large table is shrinking, or we can't get any smaller. */ 30153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel newtable = so->smalltable; 30253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (newtable == oldtable) { 30353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (so->fill == so->used) { 30453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* No dummies, so no point doing anything. */ 30553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 30653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 30753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* We're not going to resize it, but rebuild the 30853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel table anyway to purge old dummy entries. 30953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Subtle: This is *necessary* if fill==size, 31053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel as set_lookkey needs at least one virgin slot to 31153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel terminate failing searches. If fill < size, it's 31253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel merely desirable, as dummies slow searches. */ 31353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(so->fill > so->used); 31453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel memcpy(small_copy, oldtable, sizeof(small_copy)); 31553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel oldtable = small_copy; 31653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 31753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 31853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel else { 31953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel newtable = PyMem_NEW(setentry, newsize); 32053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (newtable == NULL) { 32153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_NoMemory(); 32253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 32353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 32453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 32553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 32653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Make the set empty, using the new table. */ 32753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(newtable != oldtable); 32853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->table = newtable; 32953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->mask = newsize - 1; 33053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel memset(newtable, 0, sizeof(setentry) * newsize); 33153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->used = 0; 33253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i = so->fill; 33353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->fill = 0; 33453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 33553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Copy the data over; this is refcount-neutral for active entries; 33653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel dummy entries aren't copied over, of course */ 33753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel for (entry = oldtable; i > 0; entry++) { 33853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->key == NULL) { 33953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* UNUSED */ 34053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel ; 34153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } else if (entry->key == dummy) { 34253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* DUMMY */ 34353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel --i; 34453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(entry->key == dummy); 34553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(entry->key); 34653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } else { 34753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* ACTIVE */ 34853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel --i; 34953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel set_insert_clean(so, entry->key, entry->hash); 35053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 35153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 35253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 35353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (is_oldtable_malloced) 35453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyMem_DEL(oldtable); 35553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 35653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 35753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 35853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* CAUTION: set_add_key/entry() must guarantee it won't resize the table */ 35953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 36053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 36153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_add_entry(register PySetObject *so, setentry *entry) 36253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 36353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register Py_ssize_t n_used; 36453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *key = entry->key; 36553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel long hash = entry->hash; 36653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 36753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(so->fill <= so->mask); /* at least one empty slot */ 36853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel n_used = so->used; 36953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(key); 37053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_insert_key(so, key, hash) == -1) { 37153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 37253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 37353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 37453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2)) 37553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 37653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4); 37753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 37853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 37953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 38053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_add_key(register PySetObject *so, PyObject *key) 38153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 38253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register long hash; 38353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register Py_ssize_t n_used; 38453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 38553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyString_CheckExact(key) || 38653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (hash = ((PyStringObject *) key)->ob_shash) == -1) { 38753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel hash = PyObject_Hash(key); 38853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (hash == -1) 38953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 39053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 39153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(so->fill <= so->mask); /* at least one empty slot */ 39253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel n_used = so->used; 39353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(key); 39453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_insert_key(so, key, hash) == -1) { 39553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 39653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 39753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 39853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2)) 39953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 40053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4); 40153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 40253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 40353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#define DISCARD_NOTFOUND 0 40453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#define DISCARD_FOUND 1 40553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 40653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 40753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_discard_entry(PySetObject *so, setentry *oldentry) 40853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ register setentry *entry; 40953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *old_key; 41053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 41153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry = (so->lookup)(so, oldentry->key, oldentry->hash); 41253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry == NULL) 41353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 41453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->key == NULL || entry->key == dummy) 41553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return DISCARD_NOTFOUND; 41653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel old_key = entry->key; 41753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(dummy); 41853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry->key = dummy; 41953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->used--; 42053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(old_key); 42153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return DISCARD_FOUND; 42253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 42353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 42453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 42553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_discard_key(PySetObject *so, PyObject *key) 42653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 42753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register long hash; 42853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register setentry *entry; 42953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *old_key; 43053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 43153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert (PyAnySet_Check(so)); 43253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyString_CheckExact(key) || 43353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (hash = ((PyStringObject *) key)->ob_shash) == -1) { 43453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel hash = PyObject_Hash(key); 43553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (hash == -1) 43653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 43753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 43853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry = (so->lookup)(so, key, hash); 43953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry == NULL) 44053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 44153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->key == NULL || entry->key == dummy) 44253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return DISCARD_NOTFOUND; 44353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel old_key = entry->key; 44453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(dummy); 44553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry->key = dummy; 44653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->used--; 44753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(old_key); 44853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return DISCARD_FOUND; 44953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 45053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 45153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 45253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_clear_internal(PySetObject *so) 45353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 45453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *entry, *table; 45553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel int table_is_malloced; 45653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t fill; 45753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry small_copy[PySet_MINSIZE]; 45853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#ifdef Py_DEBUG 45953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t i, n; 46053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert (PyAnySet_Check(so)); 46153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 46253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel n = so->mask + 1; 46353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i = 0; 46453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#endif 46553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 46653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel table = so->table; 46753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(table != NULL); 46853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel table_is_malloced = table != so->smalltable; 46953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 47053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* This is delicate. During the process of clearing the set, 47153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * decrefs can cause the set to mutate. To avoid fatal confusion 47253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * (voice of experience), we have to make the set empty before 47353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * clearing the slots, and never refer to anything via so->ref while 47453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * clearing. 47553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel */ 47653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel fill = so->fill; 47753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (table_is_malloced) 47853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel EMPTY_TO_MINSIZE(so); 47953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 48053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel else if (fill > 0) { 48153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* It's a small table with something that needs to be cleared. 48253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * Afraid the only safe way is to copy the set entries into 48353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * another small table first. 48453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel */ 48553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel memcpy(small_copy, table, sizeof(small_copy)); 48653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel table = small_copy; 48753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel EMPTY_TO_MINSIZE(so); 48853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 48953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* else it's a small table that's already empty */ 49053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 49153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Now we can finally clear things. If C had refcounts, we could 49253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * assert that the refcount on table is 1 now, i.e. that this function 49353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * has unique access to it, so decref side-effects can't alter it. 49453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel */ 49553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel for (entry = table; fill > 0; ++entry) { 49653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#ifdef Py_DEBUG 49753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(i < n); 49853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel ++i; 49953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#endif 50053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->key) { 50153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel --fill; 50253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(entry->key); 50353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 50453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#ifdef Py_DEBUG 50553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel else 50653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(entry->key == NULL); 50753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#endif 50853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 50953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 51053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (table_is_malloced) 51153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyMem_DEL(table); 51253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 51353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 51453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 51553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* 51653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * Iterate over a set table. Use like so: 51753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * 51853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * Py_ssize_t pos; 51953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * setentry *entry; 52053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * pos = 0; # important! pos should not otherwise be changed by you 52153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * while (set_next(yourset, &pos, &entry)) { 52253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * Refer to borrowed reference in entry->key. 52353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * } 52453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * 52553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * CAUTION: In general, it isn't safe to use set_next in a loop that 52653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * mutates the table. 52753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel */ 52853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 52953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr) 53053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 53153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t i; 53253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t mask; 53353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register setentry *table; 53453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 53553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert (PyAnySet_Check(so)); 53653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i = *pos_ptr; 53753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(i >= 0); 53853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel table = so->table; 53953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel mask = so->mask; 54053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while (i <= mask && (table[i].key == NULL || table[i].key == dummy)) 54153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i++; 54253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel *pos_ptr = i+1; 54353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (i > mask) 54453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 54553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(table[i].key != NULL); 54653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel *entry_ptr = &table[i]; 54753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 1; 54853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 54953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 55053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic void 55153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_dealloc(PySetObject *so) 55253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 55353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register setentry *entry; 55453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t fill = so->fill; 55553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject_GC_UnTrack(so); 55653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_TRASHCAN_SAFE_BEGIN(so) 55753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (so->weakreflist != NULL) 55853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject_ClearWeakRefs((PyObject *) so); 55953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 56053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel for (entry = so->table; fill > 0; entry++) { 56153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->key) { 56253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel --fill; 56353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(entry->key); 56453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 56553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 56653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (so->table != so->smalltable) 56753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyMem_DEL(so->table); 56853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (numfree < PySet_MAXFREELIST && PyAnySet_CheckExact(so)) 56953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel free_list[numfree++] = so; 57053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel else 57153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_TYPE(so)->tp_free(so); 57253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_TRASHCAN_SAFE_END(so) 57353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 57453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 57553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 57653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_tp_print(PySetObject *so, FILE *fp, int flags) 57753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 57853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *entry; 57953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t pos=0; 58053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel char *emit = ""; /* No separator emitted on first pass */ 58153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel char *separator = ", "; 58253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel int status = Py_ReprEnter((PyObject*)so); 58353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 58453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (status != 0) { 58553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (status < 0) 58653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return status; 58753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_BEGIN_ALLOW_THREADS 58853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel fprintf(fp, "%s(...)", so->ob_type->tp_name); 58953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_END_ALLOW_THREADS 59053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 59153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 59253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 59353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_BEGIN_ALLOW_THREADS 59453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel fprintf(fp, "%s([", so->ob_type->tp_name); 59553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_END_ALLOW_THREADS 59653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while (set_next(so, &pos, &entry)) { 59753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_BEGIN_ALLOW_THREADS 59853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel fputs(emit, fp); 59953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_END_ALLOW_THREADS 60053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel emit = separator; 60153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyObject_Print(entry->key, fp, 0) != 0) { 60253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ReprLeave((PyObject*)so); 60353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 60453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 60553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 60653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_BEGIN_ALLOW_THREADS 60753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel fputs("])", fp); 60853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_END_ALLOW_THREADS 60953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ReprLeave((PyObject*)so); 61053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 61153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 61253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 61353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 61453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_repr(PySetObject *so) 61553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 61653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *keys, *result=NULL, *listrepr; 61753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel int status = Py_ReprEnter((PyObject*)so); 61853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 61953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (status != 0) { 62053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (status < 0) 62153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 62253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return PyString_FromFormat("%s(...)", so->ob_type->tp_name); 62353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 62453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 62553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel keys = PySequence_List((PyObject *)so); 62653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (keys == NULL) 62753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel goto done; 62853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel listrepr = PyObject_Repr(keys); 62953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(keys); 63053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (listrepr == NULL) 63153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel goto done; 63253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 63353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel result = PyString_FromFormat("%s(%s)", so->ob_type->tp_name, 63453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyString_AS_STRING(listrepr)); 63553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(listrepr); 63653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanieldone: 63753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ReprLeave((PyObject*)so); 63853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return result; 63953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 64053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 64153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic Py_ssize_t 64253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_len(PyObject *so) 64353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 64453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return ((PySetObject *)so)->used; 64553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 64653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 64753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 64853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_merge(PySetObject *so, PyObject *otherset) 64953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 65053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PySetObject *other; 65153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *key; 65253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel long hash; 65353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register Py_ssize_t i; 65453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register setentry *entry; 65553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 65653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert (PyAnySet_Check(so)); 65753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert (PyAnySet_Check(otherset)); 65853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 65953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel other = (PySetObject*)otherset; 66053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (other == so || other->used == 0) 66153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* a.update(a) or a.update({}); nothing to do */ 66253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 66353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Do one big resize at the start, rather than 66453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * incrementally resizing as we insert new keys. Expect 66553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * that there will be no (or few) overlapping keys. 66653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel */ 66753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if ((so->fill + other->used)*3 >= (so->mask+1)*2) { 66853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_table_resize(so, (so->used + other->used)*2) != 0) 66953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 67053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 67153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel for (i = 0; i <= other->mask; i++) { 67253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry = &other->table[i]; 67353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel key = entry->key; 67453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel hash = entry->hash; 67553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (key != NULL && 67653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel key != dummy) { 67753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(key); 67853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_insert_key(so, key, hash) == -1) { 67953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 68053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 68153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 68253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 68353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 68453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 68553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 68653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 68753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 68853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_contains_key(PySetObject *so, PyObject *key) 68953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 69053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel long hash; 69153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *entry; 69253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 69353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyString_CheckExact(key) || 69453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (hash = ((PyStringObject *) key)->ob_shash) == -1) { 69553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel hash = PyObject_Hash(key); 69653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (hash == -1) 69753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 69853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 69953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry = (so->lookup)(so, key, hash); 70053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry == NULL) 70153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 70253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel key = entry->key; 70353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return key != NULL && key != dummy; 70453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 70553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 70653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 70753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_contains_entry(PySetObject *so, setentry *entry) 70853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 70953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *key; 71053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *lu_entry; 71153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 71253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel lu_entry = (so->lookup)(so, entry->key, entry->hash); 71353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (lu_entry == NULL) 71453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 71553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel key = lu_entry->key; 71653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return key != NULL && key != dummy; 71753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 71853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 71953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 72053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_pop(PySetObject *so) 72153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 72253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register Py_ssize_t i = 0; 72353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register setentry *entry; 72453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *key; 72553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 72653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert (PyAnySet_Check(so)); 72753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (so->used == 0) { 72853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_SetString(PyExc_KeyError, "pop from an empty set"); 72953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 73053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 73153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 73253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Set entry to "the first" unused or dummy set entry. We abuse 73353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * the hash field of slot 0 to hold a search finger: 73453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * If slot 0 has a value, use slot 0. 73553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * Else slot 0 is being used to hold a search finger, 73653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * and we use its hash value as the first index to look. 73753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel */ 73853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry = &so->table[0]; 73953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (entry->key == NULL || entry->key == dummy) { 74053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i = entry->hash; 74153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* The hash field may be a real hash value, or it may be a 74253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * legit search finger, or it may be a once-legit search 74353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * finger that's out of bounds now because it wrapped around 74453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * or the table shrunk -- simply make sure it's in bounds now. 74553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel */ 74653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (i > so->mask || i < 1) 74753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i = 1; /* skip slot 0 */ 74853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while ((entry = &so->table[i])->key == NULL || entry->key==dummy) { 74953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i++; 75053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (i > so->mask) 75153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i = 1; 75253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 75353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 75453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel key = entry->key; 75553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(dummy); 75653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry->key = dummy; 75753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->used--; 75853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->table[0].hash = i + 1; /* next place to start */ 75953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return key; 76053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 76153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 76253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\ 76353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielRaises KeyError if the set is empty."); 76453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 76553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 76653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_traverse(PySetObject *so, visitproc visit, void *arg) 76753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 76853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t pos = 0; 76953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *entry; 77053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 77153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while (set_next(so, &pos, &entry)) 77253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_VISIT(entry->key); 77353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 77453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 77553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 77653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic long 77753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielfrozenset_hash(PyObject *self) 77853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 77953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PySetObject *so = (PySetObject *)self; 78053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel long h, hash = 1927868237L; 78153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *entry; 78253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t pos = 0; 78353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 78453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (so->hash != -1) 78553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return so->hash; 78653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 78753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel hash *= PySet_GET_SIZE(self) + 1; 78853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while (set_next(so, &pos, &entry)) { 78953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Work to increase the bit dispersion for closely spaced hash 79053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel values. The is important because some use cases have many 79153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel combinations of a small number of elements with nearby 79253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel hashes so that many distinct combinations collapse to only 79353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel a handful of distinct hash values. */ 79453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel h = entry->hash; 79553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel hash ^= (h ^ (h << 16) ^ 89869747L) * 3644798167u; 79653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 79753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel hash = hash * 69069L + 907133923L; 79853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (hash == -1) 79953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel hash = 590923713L; 80053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->hash = hash; 80153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return hash; 80253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 80353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 80453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/***** Set iterator type ***********************************************/ 80553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 80653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanieltypedef struct { 80753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject_HEAD 80853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PySetObject *si_set; /* Set to NULL when iterator is exhausted */ 80953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t si_used; 81053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t si_pos; 81153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t len; 81253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} setiterobject; 81353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 81453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic void 81553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielsetiter_dealloc(setiterobject *si) 81653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 81753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_XDECREF(si->si_set); 81853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject_GC_Del(si); 81953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 82053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 82153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 82253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielsetiter_traverse(setiterobject *si, visitproc visit, void *arg) 82353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 82453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_VISIT(si->si_set); 82553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 82653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 82753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 82853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 82953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielsetiter_len(setiterobject *si) 83053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 83153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t len = 0; 83253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (si->si_set != NULL && si->si_used == si->si_set->used) 83353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel len = si->len; 83453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return PyInt_FromLong(len); 83553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 83653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 83753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it))."); 83853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 83953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyMethodDef setiter_methods[] = { 84053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc}, 84153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {NULL, NULL} /* sentinel */ 84253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel}; 84353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 84453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject *setiter_iternext(setiterobject *si) 84553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 84653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *key; 84753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register Py_ssize_t i, mask; 84853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register setentry *entry; 84953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PySetObject *so = si->si_set; 85053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 85153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (so == NULL) 85253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 85353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert (PyAnySet_Check(so)); 85453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 85553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (si->si_used != so->used) { 85653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_SetString(PyExc_RuntimeError, 85753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel "Set changed size during iteration"); 85853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel si->si_used = -1; /* Make this state sticky */ 85953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 86053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 86153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 86253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i = si->si_pos; 86353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(i>=0); 86453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry = so->table; 86553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel mask = so->mask; 86653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy)) 86753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i++; 86853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel si->si_pos = i+1; 86953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (i > mask) 87053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel goto fail; 87153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel si->len--; 87253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel key = entry[i].key; 87353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(key); 87453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return key; 87553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 87653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielfail: 87753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(so); 87853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel si->si_set = NULL; 87953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 88053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 88153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 88253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyTypeObject PySetIter_Type = { 88353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyVarObject_HEAD_INIT(&PyType_Type, 0) 88453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel "setiterator", /* tp_name */ 88553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel sizeof(setiterobject), /* tp_basicsize */ 88653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_itemsize */ 88753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* methods */ 88853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (destructor)setiter_dealloc, /* tp_dealloc */ 88953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_print */ 89053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_getattr */ 89153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_setattr */ 89253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_compare */ 89353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_repr */ 89453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_as_number */ 89553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_as_sequence */ 89653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_as_mapping */ 89753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_hash */ 89853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_call */ 89953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_str */ 90053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject_GenericGetAttr, /* tp_getattro */ 90153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_setattro */ 90253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_as_buffer */ 90353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ 90453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_doc */ 90553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (traverseproc)setiter_traverse, /* tp_traverse */ 90653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_clear */ 90753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_richcompare */ 90853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_weaklistoffset */ 90953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject_SelfIter, /* tp_iter */ 91053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (iternextfunc)setiter_iternext, /* tp_iternext */ 91153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setiter_methods, /* tp_methods */ 91253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, 91353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel}; 91453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 91553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 91653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_iter(PySetObject *so) 91753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 91853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type); 91953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (si == NULL) 92053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 92153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(so); 92253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel si->si_set = so; 92353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel si->si_used = so->used; 92453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel si->si_pos = 0; 92553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel si->len = so->used; 92653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel _PyObject_GC_TRACK(si); 92753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return (PyObject *)si; 92853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 92953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 93053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 93153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_update_internal(PySetObject *so, PyObject *other) 93253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 93353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *key, *it; 93453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 93553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyAnySet_Check(other)) 93653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_merge(so, other); 93753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 93853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyDict_CheckExact(other)) { 93953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *value; 94053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t pos = 0; 94153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel long hash; 94253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t dictsize = PyDict_Size(other); 94353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 94453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Do one big resize at the start, rather than 94553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * incrementally resizing as we insert new keys. Expect 94653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel * that there will be no (or few) overlapping keys. 94753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel */ 94853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (dictsize == -1) 94953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 95053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if ((so->fill + dictsize)*3 >= (so->mask+1)*2) { 95153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_table_resize(so, (so->used + dictsize)*2) != 0) 95253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 95353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 95453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while (_PyDict_Next(other, &pos, &key, &value, &hash)) { 95553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry an_entry; 95653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 95753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel an_entry.hash = hash; 95853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel an_entry.key = key; 95953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_add_entry(so, &an_entry) == -1) 96053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 96153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 96253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 96353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 96453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 96553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel it = PyObject_GetIter(other); 96653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (it == NULL) 96753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 96853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 96953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while ((key = PyIter_Next(it)) != NULL) { 97053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_add_key(so, key) == -1) { 97153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(it); 97253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 97353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 97453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 97553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 97653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 97753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(it); 97853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyErr_Occurred()) 97953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 98053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 98153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 98253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 98353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 98453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_update(PySetObject *so, PyObject *args) 98553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 98653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t i; 98753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 98853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) { 98953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *other = PyTuple_GET_ITEM(args, i); 99053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_update_internal(so, other) == -1) 99153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 99253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 99353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_NONE; 99453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 99553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 99653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(update_doc, 99753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel"Update a set with the union of itself and others."); 99853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 99953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 100053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielmake_new_set(PyTypeObject *type, PyObject *iterable) 100153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 100253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel register PySetObject *so = NULL; 100353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 100453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (dummy == NULL) { /* Auto-initialize dummy */ 100553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel dummy = PyString_FromString("<dummy key>"); 100653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (dummy == NULL) 100753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 100853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 100953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 101053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* create PySetObject structure */ 101153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (numfree && 101253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (type == &PySet_Type || type == &PyFrozenSet_Type)) { 101353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so = free_list[--numfree]; 101453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert (so != NULL && PyAnySet_CheckExact(so)); 101553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_TYPE(so) = type; 101653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel _Py_NewReference((PyObject *)so); 101753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel EMPTY_TO_MINSIZE(so); 101853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject_GC_Track(so); 101953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } else { 102053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so = (PySetObject *)type->tp_alloc(type, 0); 102153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (so == NULL) 102253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 102353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* tp_alloc has already zeroed the structure */ 102453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(so->table == NULL && so->fill == 0 && so->used == 0); 102553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel INIT_NONZERO_SET_SLOTS(so); 102653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 102753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 102853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->lookup = set_lookkey_string; 102953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so->weakreflist = NULL; 103053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 103153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (iterable != NULL) { 103253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_update_internal(so, iterable) == -1) { 103353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(so); 103453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 103553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 103653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 103753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 103853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return (PyObject *)so; 103953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 104053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 104153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* The empty frozenset is a singleton */ 104253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject *emptyfrozenset = NULL; 104353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 104453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 104553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielfrozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 104653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 104753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *iterable = NULL, *result; 104853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 104953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds)) 105053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 105153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 105253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable)) 105353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 105453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 105553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (type != &PyFrozenSet_Type) 105653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return make_new_set(type, iterable); 105753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 105853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (iterable != NULL) { 105953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* frozenset(f) is idempotent */ 106053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyFrozenSet_CheckExact(iterable)) { 106153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(iterable); 106253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return iterable; 106353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 106453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel result = make_new_set(type, iterable); 106553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (result == NULL || PySet_GET_SIZE(result)) 106653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return result; 106753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 106853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 106953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* The empty frozenset is a singleton */ 107053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (emptyfrozenset == NULL) 107153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel emptyfrozenset = make_new_set(type, NULL); 107253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_XINCREF(emptyfrozenset); 107353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return emptyfrozenset; 107453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 107553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 107653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielvoid 107753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPySet_Fini(void) 107853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 107953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PySetObject *so; 108053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 108153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while (numfree) { 108253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel numfree--; 108353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so = free_list[numfree]; 108453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject_GC_Del(so); 108553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 108653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_CLEAR(dummy); 108753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_CLEAR(emptyfrozenset); 108853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 108953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 109053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 109153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 109253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 109353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds)) 109453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 109553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 109653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return make_new_set(type, NULL); 109753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 109853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 109953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* set_swap_bodies() switches the contents of any two sets by moving their 110053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel internal data pointers and, if needed, copying the internal smalltables. 110153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Semantically equivalent to: 110253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 110353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t 110453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 110553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel The function always succeeds and it leaves both objects in a stable state. 110653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Useful for creating temporary frozensets from sets for membership testing 110753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel in __contains__(), discard(), and remove(). Also useful for operations 110853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel that update in-place (by allowing an intermediate result to be swapped 110953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel into one of the original inputs). 111053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel*/ 111153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 111253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic void 111353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_swap_bodies(PySetObject *a, PySetObject *b) 111453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 111553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t t; 111653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *u; 111753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *(*f)(PySetObject *so, PyObject *key, long hash); 111853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry tab[PySet_MINSIZE]; 111953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel long h; 112053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 112153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel t = a->fill; a->fill = b->fill; b->fill = t; 112253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel t = a->used; a->used = b->used; b->used = t; 112353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel t = a->mask; a->mask = b->mask; b->mask = t; 112453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 112553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel u = a->table; 112653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (a->table == a->smalltable) 112753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel u = b->smalltable; 112853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel a->table = b->table; 112953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (b->table == b->smalltable) 113053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel a->table = a->smalltable; 113153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel b->table = u; 113253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 113353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel f = a->lookup; a->lookup = b->lookup; b->lookup = f; 113453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 113553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (a->table == a->smalltable || b->table == b->smalltable) { 113653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel memcpy(tab, a->smalltable, sizeof(tab)); 113753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel memcpy(a->smalltable, b->smalltable, sizeof(tab)); 113853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel memcpy(b->smalltable, tab, sizeof(tab)); 113953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 114053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 114153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type) && 114253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) { 114353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel h = a->hash; a->hash = b->hash; b->hash = h; 114453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } else { 114553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel a->hash = -1; 114653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel b->hash = -1; 114753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 114853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 114953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 115053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 115153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_copy(PySetObject *so) 115253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 115353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return make_new_set(Py_TYPE(so), (PyObject *)so); 115453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 115553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 115653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 115753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielfrozenset_copy(PySetObject *so) 115853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 115953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyFrozenSet_CheckExact(so)) { 116053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(so); 116153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return (PyObject *)so; 116253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 116353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_copy(so); 116453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 116553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 116653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(copy_doc, "Return a shallow copy of a set."); 116753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 116853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 116953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_clear(PySetObject *so) 117053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 117153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel set_clear_internal(so); 117253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_NONE; 117353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 117453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 117553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(clear_doc, "Remove all elements from this set."); 117653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 117753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 117853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_union(PySetObject *so, PyObject *args) 117953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 118053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PySetObject *result; 118153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *other; 118253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t i; 118353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 118453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel result = (PySetObject *)set_copy(so); 118553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (result == NULL) 118653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 118753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 118853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) { 118953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel other = PyTuple_GET_ITEM(args, i); 119053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if ((PyObject *)so == other) 119153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel continue; 119253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_update_internal(result, other) == -1) { 119353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 119453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 119553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 119653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 119753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return (PyObject *)result; 119853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 119953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 120053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(union_doc, 120153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel "Return the union of sets as a new set.\n\ 120253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel\n\ 120353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel(i.e. all elements that are in either set.)"); 120453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 120553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 120653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_or(PySetObject *so, PyObject *other) 120753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 120853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PySetObject *result; 120953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 121053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) { 121153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(Py_NotImplemented); 121253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return Py_NotImplemented; 121353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 121453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 121553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel result = (PySetObject *)set_copy(so); 121653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (result == NULL) 121753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 121853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if ((PyObject *)so == other) 121953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return (PyObject *)result; 122053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_update_internal(result, other) == -1) { 122153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 122253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 122353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 122453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return (PyObject *)result; 122553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 122653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 122753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 122853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_ior(PySetObject *so, PyObject *other) 122953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 123053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyAnySet_Check(other)) { 123153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(Py_NotImplemented); 123253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return Py_NotImplemented; 123353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 123453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_update_internal(so, other) == -1) 123553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 123653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(so); 123753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return (PyObject *)so; 123853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 123953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 124053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 124153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_intersection(PySetObject *so, PyObject *other) 124253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 124353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PySetObject *result; 124453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *key, *it, *tmp; 124553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 124653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if ((PyObject *)so == other) 124753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_copy(so); 124853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 124953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel result = (PySetObject *)make_new_set(Py_TYPE(so), NULL); 125053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (result == NULL) 125153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 125253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 125353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyAnySet_Check(other)) { 125453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t pos = 0; 125553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *entry; 125653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 125753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) { 125853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel tmp = (PyObject *)so; 125953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so = (PySetObject *)other; 126053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel other = tmp; 126153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 126253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 126353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while (set_next((PySetObject *)other, &pos, &entry)) { 126453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel int rv = set_contains_entry(so, entry); 126553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == -1) { 126653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 126753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 126853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 126953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv) { 127053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_add_entry(result, entry) == -1) { 127153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 127253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 127353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 127453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 127553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 127653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return (PyObject *)result; 127753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 127853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 127953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel it = PyObject_GetIter(other); 128053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (it == NULL) { 128153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 128253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 128353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 128453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 128553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while ((key = PyIter_Next(it)) != NULL) { 128653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel int rv; 128753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry entry; 128853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel long hash = PyObject_Hash(key); 128953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 129053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (hash == -1) { 129153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(it); 129253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 129353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 129453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 129553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 129653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry.hash = hash; 129753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry.key = key; 129853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel rv = set_contains_entry(so, &entry); 129953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == -1) { 130053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(it); 130153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 130253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 130353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 130453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 130553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv) { 130653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_add_entry(result, &entry) == -1) { 130753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(it); 130853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 130953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 131053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 131153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 131253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 131353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 131453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 131553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(it); 131653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyErr_Occurred()) { 131753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 131853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 131953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 132053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return (PyObject *)result; 132153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 132253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 132353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 132453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_intersection_multi(PySetObject *so, PyObject *args) 132553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 132653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t i; 132753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *result = (PyObject *)so; 132853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 132953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyTuple_GET_SIZE(args) == 0) 133053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_copy(so); 133153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 133253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(so); 133353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) { 133453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *other = PyTuple_GET_ITEM(args, i); 133553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *newresult = set_intersection((PySetObject *)result, other); 133653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (newresult == NULL) { 133753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 133853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 133953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 134053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 134153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel result = newresult; 134253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 134353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return result; 134453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 134553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 134653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(intersection_doc, 134753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel"Return the intersection of two or more sets as a new set.\n\ 134853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel\n\ 134953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel(i.e. elements that are common to all of the sets.)"); 135053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 135153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 135253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_intersection_update(PySetObject *so, PyObject *other) 135353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 135453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *tmp; 135553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 135653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel tmp = set_intersection(so, other); 135753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (tmp == NULL) 135853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 135953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel set_swap_bodies(so, (PySetObject *)tmp); 136053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(tmp); 136153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_NONE; 136253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 136353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 136453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 136553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_intersection_update_multi(PySetObject *so, PyObject *args) 136653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 136753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *tmp; 136853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 136953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel tmp = set_intersection_multi(so, args); 137053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (tmp == NULL) 137153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 137253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel set_swap_bodies(so, (PySetObject *)tmp); 137353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(tmp); 137453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_NONE; 137553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 137653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 137753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(intersection_update_doc, 137853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel"Update a set with the intersection of itself and another."); 137953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 138053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 138153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_and(PySetObject *so, PyObject *other) 138253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 138353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) { 138453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(Py_NotImplemented); 138553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return Py_NotImplemented; 138653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 138753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_intersection(so, other); 138853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 138953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 139053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 139153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_iand(PySetObject *so, PyObject *other) 139253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 139353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *result; 139453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 139553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyAnySet_Check(other)) { 139653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(Py_NotImplemented); 139753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return Py_NotImplemented; 139853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 139953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel result = set_intersection_update(so, other); 140053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (result == NULL) 140153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 140253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 140353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(so); 140453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return (PyObject *)so; 140553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 140653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 140753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 140853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_isdisjoint(PySetObject *so, PyObject *other) 140953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 141053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *key, *it, *tmp; 141153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 141253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if ((PyObject *)so == other) { 141353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PySet_GET_SIZE(so) == 0) 141453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_TRUE; 141553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel else 141653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_FALSE; 141753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 141853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 141953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyAnySet_CheckExact(other)) { 142053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t pos = 0; 142153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *entry; 142253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 142353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) { 142453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel tmp = (PyObject *)so; 142553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel so = (PySetObject *)other; 142653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel other = tmp; 142753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 142853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while (set_next((PySetObject *)other, &pos, &entry)) { 142953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel int rv = set_contains_entry(so, entry); 143053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == -1) 143153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 143253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv) 143353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_FALSE; 143453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 143553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_TRUE; 143653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 143753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 143853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel it = PyObject_GetIter(other); 143953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (it == NULL) 144053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 144153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 144253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while ((key = PyIter_Next(it)) != NULL) { 144353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel int rv; 144453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry entry; 144553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel long hash = PyObject_Hash(key); 144653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 144753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (hash == -1) { 144853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 144953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(it); 145053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 145153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 145253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry.hash = hash; 145353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entry.key = key; 145453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel rv = set_contains_entry(so, &entry); 145553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 145653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == -1) { 145753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(it); 145853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 145953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 146053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv) { 146153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(it); 146253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_FALSE; 146353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 146453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 146553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(it); 146653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyErr_Occurred()) 146753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 146853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_TRUE; 146953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 147053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 147153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(isdisjoint_doc, 147253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel"Return True if two sets have a null intersection."); 147353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 147453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 147553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_difference_update_internal(PySetObject *so, PyObject *other) 147653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 147753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if ((PyObject *)so == other) 147853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_clear_internal(so); 147953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 148053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyAnySet_Check(other)) { 148153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *entry; 148253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t pos = 0; 148353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 148453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while (set_next((PySetObject *)other, &pos, &entry)) 148553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_discard_entry(so, entry) == -1) 148653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 148753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } else { 148853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *key, *it; 148953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel it = PyObject_GetIter(other); 149053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (it == NULL) 149153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 149253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 149353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while ((key = PyIter_Next(it)) != NULL) { 149453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_discard_key(so, key) == -1) { 149553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(it); 149653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 149753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 149853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 149953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 150053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 150153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(it); 150253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyErr_Occurred()) 150353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 150453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 150553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* If more than 1/5 are dummies, then resize them away. */ 150653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if ((so->fill - so->used) * 5 < so->mask) 150753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 150853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4); 150953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 151053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 151153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 151253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_difference_update(PySetObject *so, PyObject *args) 151353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 151453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t i; 151553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 151653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) { 151753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *other = PyTuple_GET_ITEM(args, i); 151853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_difference_update_internal(so, other) == -1) 151953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 152053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 152153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_NONE; 152253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 152353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 152453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(difference_update_doc, 152553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel"Remove all elements of another set from this set."); 152653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 152753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 152853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_difference(PySetObject *so, PyObject *other) 152953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 153053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *result; 153153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *entry; 153253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t pos = 0; 153353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 153453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyAnySet_Check(other) && !PyDict_CheckExact(other)) { 153553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel result = set_copy(so); 153653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (result == NULL) 153753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 153853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_difference_update_internal((PySetObject *)result, other) != -1) 153953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return result; 154053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 154153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 154253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 154353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 154453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel result = make_new_set(Py_TYPE(so), NULL); 154553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (result == NULL) 154653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 154753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 154853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyDict_CheckExact(other)) { 154953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while (set_next(so, &pos, &entry)) { 155053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry entrycopy; 155153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entrycopy.hash = entry->hash; 155253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel entrycopy.key = entry->key; 155353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!_PyDict_Contains(other, entry->key, entry->hash)) { 155453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_add_entry((PySetObject *)result, &entrycopy) == -1) { 155553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 155653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 155753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 155853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 155953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 156053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return result; 156153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 156253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 156353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while (set_next(so, &pos, &entry)) { 156453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel int rv = set_contains_entry((PySetObject *)other, entry); 156553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == -1) { 156653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 156753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 156853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 156953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!rv) { 157053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_add_entry((PySetObject *)result, entry) == -1) { 157153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 157253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 157353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 157453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 157553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 157653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return result; 157753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 157853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 157953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 158053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_difference_multi(PySetObject *so, PyObject *args) 158153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 158253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t i; 158353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *result, *other; 158453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 158553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyTuple_GET_SIZE(args) == 0) 158653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_copy(so); 158753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 158853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel other = PyTuple_GET_ITEM(args, 0); 158953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel result = set_difference(so, other); 159053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (result == NULL) 159153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 159253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 159353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) { 159453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel other = PyTuple_GET_ITEM(args, i); 159553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_difference_update_internal((PySetObject *)result, other) == -1) { 159653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 159753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 159853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 159953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 160053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return result; 160153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 160253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 160353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(difference_doc, 160453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel"Return the difference of two or more sets as a new set.\n\ 160553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel\n\ 160653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel(i.e. all elements that are in this set but not the others.)"); 160753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 160853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_sub(PySetObject *so, PyObject *other) 160953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 161053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) { 161153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(Py_NotImplemented); 161253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return Py_NotImplemented; 161353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 161453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_difference(so, other); 161553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 161653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 161753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 161853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_isub(PySetObject *so, PyObject *other) 161953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 162053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyAnySet_Check(other)) { 162153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(Py_NotImplemented); 162253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return Py_NotImplemented; 162353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 162453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_difference_update_internal(so, other) == -1) 162553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 162653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(so); 162753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return (PyObject *)so; 162853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 162953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 163053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 163153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_symmetric_difference_update(PySetObject *so, PyObject *other) 163253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 163353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PySetObject *otherset; 163453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *key; 163553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t pos = 0; 163653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *entry; 163753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 163853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if ((PyObject *)so == other) 163953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_clear(so); 164053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 164153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyDict_CheckExact(other)) { 164253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *value; 164353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel int rv; 164453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel long hash; 164553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while (_PyDict_Next(other, &pos, &key, &value, &hash)) { 164653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry an_entry; 164753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 164853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(key); 164953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel an_entry.hash = hash; 165053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel an_entry.key = key; 165153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 165253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel rv = set_discard_entry(so, &an_entry); 165353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == -1) { 165453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 165553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 165653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 165753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == DISCARD_NOTFOUND) { 165853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_add_entry(so, &an_entry) == -1) { 165953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 166053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 166153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 166253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 166353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(key); 166453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 166553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_NONE; 166653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 166753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 166853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PyAnySet_Check(other)) { 166953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(other); 167053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel otherset = (PySetObject *)other; 167153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } else { 167253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel otherset = (PySetObject *)make_new_set(Py_TYPE(so), other); 167353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (otherset == NULL) 167453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 167553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 167653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 167753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while (set_next(otherset, &pos, &entry)) { 167853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel int rv = set_discard_entry(so, entry); 167953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == -1) { 168053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(otherset); 168153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 168253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 168353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == DISCARD_NOTFOUND) { 168453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_add_entry(so, entry) == -1) { 168553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(otherset); 168653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 168753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 168853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 168953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 169053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(otherset); 169153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_NONE; 169253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 169353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 169453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(symmetric_difference_update_doc, 169553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel"Update a set with the symmetric difference of itself and another."); 169653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 169753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 169853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_symmetric_difference(PySetObject *so, PyObject *other) 169953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 170053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *rv; 170153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PySetObject *otherset; 170253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 170353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel otherset = (PySetObject *)make_new_set(Py_TYPE(so), other); 170453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (otherset == NULL) 170553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 170653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel rv = set_symmetric_difference_update(otherset, (PyObject *)so); 170753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == NULL) 170853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 170953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(rv); 171053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return (PyObject *)otherset; 171153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 171253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 171353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(symmetric_difference_doc, 171453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel"Return the symmetric difference of two sets as a new set.\n\ 171553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel\n\ 171653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel(i.e. all elements that are in exactly one of the sets.)"); 171753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 171853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 171953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_xor(PySetObject *so, PyObject *other) 172053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 172153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) { 172253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(Py_NotImplemented); 172353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return Py_NotImplemented; 172453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 172553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_symmetric_difference(so, other); 172653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 172753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 172853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 172953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_ixor(PySetObject *so, PyObject *other) 173053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 173153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *result; 173253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 173353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyAnySet_Check(other)) { 173453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(Py_NotImplemented); 173553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return Py_NotImplemented; 173653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 173753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel result = set_symmetric_difference_update(so, other); 173853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (result == NULL) 173953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 174053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(result); 174153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(so); 174253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return (PyObject *)so; 174353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 174453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 174553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 174653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_issubset(PySetObject *so, PyObject *other) 174753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 174853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *entry; 174953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t pos = 0; 175053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 175153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyAnySet_Check(other)) { 175253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *tmp, *result; 175353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel tmp = make_new_set(&PySet_Type, other); 175453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (tmp == NULL) 175553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 175653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel result = set_issubset(so, tmp); 175753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(tmp); 175853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return result; 175953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 176053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other)) 176153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_FALSE; 176253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 176353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while (set_next(so, &pos, &entry)) { 176453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel int rv = set_contains_entry((PySetObject *)other, entry); 176553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == -1) 176653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 176753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!rv) 176853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_FALSE; 176953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 177053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_TRUE; 177153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 177253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 177353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(issubset_doc, "Report whether another set contains this set."); 177453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 177553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 177653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_issuperset(PySetObject *so, PyObject *other) 177753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 177853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *tmp, *result; 177953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 178053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyAnySet_Check(other)) { 178153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel tmp = make_new_set(&PySet_Type, other); 178253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (tmp == NULL) 178353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 178453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel result = set_issuperset(so, tmp); 178553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(tmp); 178653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return result; 178753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 178853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_issubset((PySetObject *)other, (PyObject *)so); 178953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 179053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 179153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set."); 179253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 179353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 179453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_richcompare(PySetObject *v, PyObject *w, int op) 179553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 179653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *r1, *r2; 179753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 179853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if(!PyAnySet_Check(w)) { 179953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(Py_NotImplemented); 180053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return Py_NotImplemented; 180153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 180253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel switch (op) { 180353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel case Py_EQ: 180453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w)) 180553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_FALSE; 180653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (v->hash != -1 && 180753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel ((PySetObject *)w)->hash != -1 && 180853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel v->hash != ((PySetObject *)w)->hash) 180953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_FALSE; 181053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_issubset(v, w); 181153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel case Py_NE: 181253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel r1 = set_richcompare(v, w, Py_EQ); 181353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (r1 == NULL) 181453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 181553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel r2 = PyBool_FromLong(PyObject_Not(r1)); 181653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(r1); 181753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return r2; 181853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel case Py_LE: 181953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_issubset(v, w); 182053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel case Py_GE: 182153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_issuperset(v, w); 182253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel case Py_LT: 182353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w)) 182453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_FALSE; 182553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_issubset(v, w); 182653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel case Py_GT: 182753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w)) 182853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_FALSE; 182953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_issuperset(v, w); 183053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 183153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(Py_NotImplemented); 183253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return Py_NotImplemented; 183353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 183453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 183553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 183653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_nocmp(PyObject *self, PyObject *other) 183753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 183853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_SetString(PyExc_TypeError, "cannot compare sets using cmp()"); 183953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 184053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 184153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 184253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 184353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_add(PySetObject *so, PyObject *key) 184453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 184553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_add_key(so, key) == -1) 184653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 184753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_NONE; 184853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 184953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 185053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(add_doc, 185153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel"Add an element to a set.\n\ 185253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel\n\ 185353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielThis has no effect if the element is already present."); 185453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 185553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 185653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_contains(PySetObject *so, PyObject *key) 185753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 185853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *tmpkey; 185953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel int rv; 186053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 186153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel rv = set_contains_key(so, key); 186253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == -1) { 186353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError)) 186453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 186553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_Clear(); 186653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel tmpkey = make_new_set(&PyFrozenSet_Type, key); 186753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (tmpkey == NULL) 186853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 186953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel rv = set_contains_key(so, tmpkey); 187053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(tmpkey); 187153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 187253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return rv; 187353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 187453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 187553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 187653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_direct_contains(PySetObject *so, PyObject *key) 187753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 187853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel long result; 187953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 188053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel result = set_contains(so, key); 188153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (result == -1) 188253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 188353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return PyBool_FromLong(result); 188453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 188553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 188653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x."); 188753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 188853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 188953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_remove(PySetObject *so, PyObject *key) 189053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 189153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *tmpkey; 189253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel int rv; 189353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 189453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel rv = set_discard_key(so, key); 189553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == -1) { 189653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError)) 189753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 189853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_Clear(); 189953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel tmpkey = make_new_set(&PyFrozenSet_Type, key); 190053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (tmpkey == NULL) 190153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 190253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel rv = set_discard_key(so, tmpkey); 190353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(tmpkey); 190453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == -1) 190553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 190653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 190753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 190853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == DISCARD_NOTFOUND) { 190953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel set_key_error(key); 191053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 191153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 191253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_NONE; 191353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 191453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 191553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(remove_doc, 191653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel"Remove an element from a set; it must be a member.\n\ 191753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel\n\ 191853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielIf the element is not a member, raise a KeyError."); 191953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 192053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 192153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_discard(PySetObject *so, PyObject *key) 192253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 192353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *tmpkey; 192453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel int rv; 192553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 192653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel rv = set_discard_key(so, key); 192753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == -1) { 192853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError)) 192953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 193053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_Clear(); 193153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel tmpkey = make_new_set(&PyFrozenSet_Type, key); 193253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (tmpkey == NULL) 193353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 193453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel rv = set_discard_key(so, tmpkey); 193553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(tmpkey); 193653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (rv == -1) 193753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 193853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 193953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_NONE; 194053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 194153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 194253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(discard_doc, 194353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel"Remove an element from a set if it is a member.\n\ 194453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel\n\ 194553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielIf the element is not a member, do nothing."); 194653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 194753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 194853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_reduce(PySetObject *so) 194953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 195053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL; 195153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 195253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel keys = PySequence_List((PyObject *)so); 195353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (keys == NULL) 195453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel goto done; 195553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel args = PyTuple_Pack(1, keys); 195653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (args == NULL) 195753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel goto done; 195853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel dict = PyObject_GetAttrString((PyObject *)so, "__dict__"); 195953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (dict == NULL) { 196053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_Clear(); 196153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel dict = Py_None; 196253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(dict); 196353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 196453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel result = PyTuple_Pack(3, Py_TYPE(so), args, dict); 196553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanieldone: 196653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_XDECREF(args); 196753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_XDECREF(keys); 196853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_XDECREF(dict); 196953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return result; 197053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 197153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 197253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(reduce_doc, "Return state information for pickling."); 197353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 197453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 197553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_sizeof(PySetObject *so) 197653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 197753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t res; 197853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 197953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel res = sizeof(PySetObject); 198053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (so->table != so->smalltable) 198153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel res = res + (so->mask + 1) * sizeof(setentry); 198253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return PyInt_FromSsize_t(res); 198353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 198453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 198553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes"); 198653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic int 198753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset_init(PySetObject *self, PyObject *args, PyObject *kwds) 198853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 198953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *iterable = NULL; 199053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 199153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyAnySet_Check(self)) 199253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 199353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (PySet_Check(self) && !_PyArg_NoKeywords("set()", kwds)) 199453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 199553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable)) 199653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 199753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel set_clear_internal(self); 199853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel self->hash = -1; 199953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (iterable == NULL) 200053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 200153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_update_internal(self, iterable); 200253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 200353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 200453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PySequenceMethods set_as_sequence = { 200553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel set_len, /* sq_length */ 200653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* sq_concat */ 200753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* sq_repeat */ 200853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* sq_item */ 200953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* sq_slice */ 201053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* sq_ass_item */ 201153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* sq_ass_slice */ 201253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (objobjproc)set_contains, /* sq_contains */ 201353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel}; 201453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 201553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* set object ********************************************************/ 201653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 201753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#ifdef Py_DEBUG 201853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject *test_c_api(PySetObject *so); 201953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 202053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(test_c_api_doc, "Exercises C API. Returns True.\n\ 202153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielAll is well if assertions don't fail."); 202253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#endif 202353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 202453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyMethodDef set_methods[] = { 202553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"add", (PyCFunction)set_add, METH_O, 202653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel add_doc}, 202753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"clear", (PyCFunction)set_clear, METH_NOARGS, 202853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel clear_doc}, 202953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST, 203053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel contains_doc}, 203153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"copy", (PyCFunction)set_copy, METH_NOARGS, 203253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel copy_doc}, 203353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"discard", (PyCFunction)set_discard, METH_O, 203453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel discard_doc}, 203553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"difference", (PyCFunction)set_difference_multi, METH_VARARGS, 203653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel difference_doc}, 203753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"difference_update", (PyCFunction)set_difference_update, METH_VARARGS, 203853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel difference_update_doc}, 203953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS, 204053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel intersection_doc}, 204153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"intersection_update",(PyCFunction)set_intersection_update_multi, METH_VARARGS, 204253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel intersection_update_doc}, 204353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O, 204453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel isdisjoint_doc}, 204553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"issubset", (PyCFunction)set_issubset, METH_O, 204653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel issubset_doc}, 204753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"issuperset", (PyCFunction)set_issuperset, METH_O, 204853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel issuperset_doc}, 204953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"pop", (PyCFunction)set_pop, METH_NOARGS, 205053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel pop_doc}, 205153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS, 205253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel reduce_doc}, 205353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"remove", (PyCFunction)set_remove, METH_O, 205453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel remove_doc}, 205553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS, 205653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel sizeof_doc}, 205753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O, 205853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel symmetric_difference_doc}, 205953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O, 206053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel symmetric_difference_update_doc}, 206153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#ifdef Py_DEBUG 206253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"test_c_api", (PyCFunction)test_c_api, METH_NOARGS, 206353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel test_c_api_doc}, 206453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#endif 206553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"union", (PyCFunction)set_union, METH_VARARGS, 206653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel union_doc}, 206753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"update", (PyCFunction)set_update, METH_VARARGS, 206853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel update_doc}, 206953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {NULL, NULL} /* sentinel */ 207053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel}; 207153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 207253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyNumberMethods set_as_number = { 207353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_add*/ 207453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (binaryfunc)set_sub, /*nb_subtract*/ 207553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_multiply*/ 207653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_divide*/ 207753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_remainder*/ 207853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_divmod*/ 207953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_power*/ 208053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_negative*/ 208153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_positive*/ 208253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_absolute*/ 208353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_nonzero*/ 208453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_invert*/ 208553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_lshift*/ 208653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_rshift*/ 208753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (binaryfunc)set_and, /*nb_and*/ 208853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (binaryfunc)set_xor, /*nb_xor*/ 208953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (binaryfunc)set_or, /*nb_or*/ 209053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_coerce*/ 209153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_int*/ 209253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_long*/ 209353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_float*/ 209453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_oct*/ 209553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_hex*/ 209653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_inplace_add*/ 209753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (binaryfunc)set_isub, /*nb_inplace_subtract*/ 209853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_inplace_multiply*/ 209953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_inplace_divide*/ 210053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_inplace_remainder*/ 210153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_inplace_power*/ 210253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_inplace_lshift*/ 210353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_inplace_rshift*/ 210453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (binaryfunc)set_iand, /*nb_inplace_and*/ 210553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (binaryfunc)set_ixor, /*nb_inplace_xor*/ 210653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (binaryfunc)set_ior, /*nb_inplace_or*/ 210753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel}; 210853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 210953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(set_doc, 211053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel"set() -> new empty set object\n\ 211153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielset(iterable) -> new set object\n\ 211253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel\n\ 211353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielBuild an unordered collection of unique elements."); 211453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 211553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyTypeObject PySet_Type = { 211653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyVarObject_HEAD_INIT(&PyType_Type, 0) 211753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel "set", /* tp_name */ 211853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel sizeof(PySetObject), /* tp_basicsize */ 211953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_itemsize */ 212053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* methods */ 212153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (destructor)set_dealloc, /* tp_dealloc */ 212253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (printfunc)set_tp_print, /* tp_print */ 212353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_getattr */ 212453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_setattr */ 212553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel set_nocmp, /* tp_compare */ 212653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (reprfunc)set_repr, /* tp_repr */ 212753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel &set_as_number, /* tp_as_number */ 212853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel &set_as_sequence, /* tp_as_sequence */ 212953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_as_mapping */ 213053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (hashfunc)PyObject_HashNotImplemented, /* tp_hash */ 213153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_call */ 213253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_str */ 213353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject_GenericGetAttr, /* tp_getattro */ 213453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_setattro */ 213553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_as_buffer */ 213653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_CHECKTYPES | 213753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_TPFLAGS_BASETYPE, /* tp_flags */ 213853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel set_doc, /* tp_doc */ 213953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (traverseproc)set_traverse, /* tp_traverse */ 214053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (inquiry)set_clear_internal, /* tp_clear */ 214153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (richcmpfunc)set_richcompare, /* tp_richcompare */ 214253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */ 214353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (getiterfunc)set_iter, /* tp_iter */ 214453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_iternext */ 214553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel set_methods, /* tp_methods */ 214653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_members */ 214753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_getset */ 214853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_base */ 214953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_dict */ 215053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_descr_get */ 215153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_descr_set */ 215253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_dictoffset */ 215353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (initproc)set_init, /* tp_init */ 215453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyType_GenericAlloc, /* tp_alloc */ 215553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel set_new, /* tp_new */ 215653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject_GC_Del, /* tp_free */ 215753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel}; 215853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 215953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* frozenset object ********************************************************/ 216053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 216153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 216253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyMethodDef frozenset_methods[] = { 216353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST, 216453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel contains_doc}, 216553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"copy", (PyCFunction)frozenset_copy, METH_NOARGS, 216653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel copy_doc}, 216753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"difference", (PyCFunction)set_difference_multi, METH_VARARGS, 216853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel difference_doc}, 216953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS, 217053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel intersection_doc}, 217153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O, 217253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel isdisjoint_doc}, 217353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"issubset", (PyCFunction)set_issubset, METH_O, 217453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel issubset_doc}, 217553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"issuperset", (PyCFunction)set_issuperset, METH_O, 217653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel issuperset_doc}, 217753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS, 217853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel reduce_doc}, 217953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS, 218053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel sizeof_doc}, 218153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O, 218253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel symmetric_difference_doc}, 218353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {"union", (PyCFunction)set_union, METH_VARARGS, 218453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel union_doc}, 218553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel {NULL, NULL} /* sentinel */ 218653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel}; 218753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 218853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyNumberMethods frozenset_as_number = { 218953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_add*/ 219053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (binaryfunc)set_sub, /*nb_subtract*/ 219153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_multiply*/ 219253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_divide*/ 219353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_remainder*/ 219453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_divmod*/ 219553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_power*/ 219653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_negative*/ 219753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_positive*/ 219853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_absolute*/ 219953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_nonzero*/ 220053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_invert*/ 220153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_lshift*/ 220253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /*nb_rshift*/ 220353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (binaryfunc)set_and, /*nb_and*/ 220453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (binaryfunc)set_xor, /*nb_xor*/ 220553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (binaryfunc)set_or, /*nb_or*/ 220653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel}; 220753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 220853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyDoc_STRVAR(frozenset_doc, 220953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel"frozenset() -> empty frozenset object\n\ 221053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielfrozenset(iterable) -> frozenset object\n\ 221153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel\n\ 221253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielBuild an immutable unordered collection of unique elements."); 221353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 221453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyTypeObject PyFrozenSet_Type = { 221553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyVarObject_HEAD_INIT(&PyType_Type, 0) 221653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel "frozenset", /* tp_name */ 221753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel sizeof(PySetObject), /* tp_basicsize */ 221853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_itemsize */ 221953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* methods */ 222053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (destructor)set_dealloc, /* tp_dealloc */ 222153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (printfunc)set_tp_print, /* tp_print */ 222253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_getattr */ 222353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_setattr */ 222453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel set_nocmp, /* tp_compare */ 222553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (reprfunc)set_repr, /* tp_repr */ 222653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel &frozenset_as_number, /* tp_as_number */ 222753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel &set_as_sequence, /* tp_as_sequence */ 222853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_as_mapping */ 222953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel frozenset_hash, /* tp_hash */ 223053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_call */ 223153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_str */ 223253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject_GenericGetAttr, /* tp_getattro */ 223353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_setattro */ 223453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_as_buffer */ 223553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_CHECKTYPES | 223653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_TPFLAGS_BASETYPE, /* tp_flags */ 223753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel frozenset_doc, /* tp_doc */ 223853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (traverseproc)set_traverse, /* tp_traverse */ 223953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (inquiry)set_clear_internal, /* tp_clear */ 224053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (richcmpfunc)set_richcompare, /* tp_richcompare */ 224153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */ 224253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (getiterfunc)set_iter, /* tp_iter */ 224353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_iternext */ 224453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel frozenset_methods, /* tp_methods */ 224553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_members */ 224653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_getset */ 224753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_base */ 224853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_dict */ 224953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_descr_get */ 225053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_descr_set */ 225153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_dictoffset */ 225253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 0, /* tp_init */ 225353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyType_GenericAlloc, /* tp_alloc */ 225453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel frozenset_new, /* tp_new */ 225553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject_GC_Del, /* tp_free */ 225653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel}; 225753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 225853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 225953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/***** C API functions *************************************************/ 226053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 226153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyObject * 226253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPySet_New(PyObject *iterable) 226353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 226453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return make_new_set(&PySet_Type, iterable); 226553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 226653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 226753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyObject * 226853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyFrozenSet_New(PyObject *iterable) 226953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 227053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return make_new_set(&PyFrozenSet_Type, iterable); 227153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 227253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 227353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPy_ssize_t 227453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPySet_Size(PyObject *anyset) 227553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 227653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyAnySet_Check(anyset)) { 227753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_BadInternalCall(); 227853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 227953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 228053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return PySet_GET_SIZE(anyset); 228153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 228253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 228353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielint 228453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPySet_Clear(PyObject *set) 228553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 228653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PySet_Check(set)) { 228753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_BadInternalCall(); 228853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 228953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 229053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_clear_internal((PySetObject *)set); 229153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 229253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 229353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielint 229453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPySet_Contains(PyObject *anyset, PyObject *key) 229553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 229653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyAnySet_Check(anyset)) { 229753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_BadInternalCall(); 229853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 229953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 230053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_contains_key((PySetObject *)anyset, key); 230153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 230253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 230353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielint 230453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPySet_Discard(PyObject *set, PyObject *key) 230553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 230653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PySet_Check(set)) { 230753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_BadInternalCall(); 230853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 230953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 231053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_discard_key((PySetObject *)set, key); 231153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 231253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 231353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielint 231453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPySet_Add(PyObject *anyset, PyObject *key) 231553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 231653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PySet_Check(anyset) && 231753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) { 231853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_BadInternalCall(); 231953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 232053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 232153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_add_key((PySetObject *)anyset, key); 232253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 232353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 232453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielint 232553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel_PySet_Next(PyObject *set, Py_ssize_t *pos, PyObject **key) 232653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 232753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *entry_ptr; 232853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 232953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyAnySet_Check(set)) { 233053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_BadInternalCall(); 233153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 233253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 233353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_next((PySetObject *)set, pos, &entry_ptr) == 0) 233453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 233553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel *key = entry_ptr->key; 233653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 1; 233753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 233853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 233953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielint 234053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel_PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, long *hash) 234153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 234253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel setentry *entry; 234353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 234453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PyAnySet_Check(set)) { 234553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_BadInternalCall(); 234653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 234753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 234853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_next((PySetObject *)set, pos, &entry) == 0) 234953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 0; 235053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel *key = entry->key; 235153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel *hash = entry->hash; 235253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return 1; 235353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 235453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 235553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPyObject * 235653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielPySet_Pop(PyObject *set) 235753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 235853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PySet_Check(set)) { 235953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_BadInternalCall(); 236053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 236153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 236253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_pop((PySetObject *)set); 236353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 236453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 236553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielint 236653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel_PySet_Update(PyObject *set, PyObject *iterable) 236753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 236853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (!PySet_Check(set)) { 236953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_BadInternalCall(); 237053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return -1; 237153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 237253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return set_update_internal((PySetObject *)set, iterable); 237353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 237453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 237553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#ifdef Py_DEBUG 237653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 237753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel/* Test code to be called with any three element set. 237853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Returns True and original set is restored. */ 237953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 238053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#define assertRaises(call_return_value, exception) \ 238153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel do { \ 238253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(call_return_value); \ 238353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PyErr_ExceptionMatches(exception)); \ 238453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyErr_Clear(); \ 238553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } while(0) 238653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 238753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanielstatic PyObject * 238853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDanieltest_c_api(PySetObject *so) 238953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel{ 239053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t count; 239153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel char *s; 239253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_ssize_t i; 239353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x; 239453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *ob = (PyObject *)so; 239553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel PyObject *str; 239653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 239753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Verify preconditions */ 239853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PyAnySet_Check(ob)); 239953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PyAnySet_CheckExact(ob)); 240053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(!PyFrozenSet_CheckExact(ob)); 240153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 240253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* so.clear(); so |= set("abc"); */ 240353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel str = PyString_FromString("abc"); 240453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (str == NULL) 240553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 240653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel set_clear_internal(so); 240753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel if (set_update_internal(so, str) == -1) { 240853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(str); 240953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel return NULL; 241053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 241153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(str); 241253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 241353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Exercise type/size checks */ 241453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_Size(ob) == 3); 241553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_GET_SIZE(ob) == 3); 241653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 241753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Raise TypeError for non-iterable constructor arguments */ 241853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError); 241953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError); 242053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 242153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Raise TypeError for unhashable key */ 242253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel dup = PySet_New(ob); 242353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError); 242453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError); 242553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError); 242653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 242753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Exercise successful pop, contains, add, and discard */ 242853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel elem = PySet_Pop(ob); 242953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_Contains(ob, elem) == 0); 243053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_GET_SIZE(ob) == 2); 243153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_Add(ob, elem) == 0); 243253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_Contains(ob, elem) == 1); 243353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_GET_SIZE(ob) == 3); 243453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_Discard(ob, elem) == 1); 243553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_GET_SIZE(ob) == 2); 243653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_Discard(ob, elem) == 0); 243753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_GET_SIZE(ob) == 2); 243853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 243953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Exercise clear */ 244053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel dup2 = PySet_New(dup); 244153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_Clear(dup2) == 0); 244253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_Size(dup2) == 0); 244353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(dup2); 244453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 244553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Raise SystemError on clear or update of frozen set */ 244653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel f = PyFrozenSet_New(dup); 244753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assertRaises(PySet_Clear(f) == -1, PyExc_SystemError); 244853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError); 244953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_Add(f, elem) == 0); 245053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_INCREF(f); 245153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError); 245253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(f); 245353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(f); 245453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 245553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Exercise direct iteration */ 245653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel i = 0, count = 0; 245753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel while (_PySet_Next((PyObject *)dup, &i, &x)) { 245853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel s = PyString_AsString(x); 245953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c')); 246053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel count++; 246153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel } 246253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(count == 3); 246353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 246453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Exercise updates */ 246553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel dup2 = PySet_New(NULL); 246653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(_PySet_Update(dup2, dup) == 0); 246753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_Size(dup2) == 3); 246853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(_PySet_Update(dup2, dup) == 0); 246953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_Size(dup2) == 3); 247053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(dup2); 247153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 247253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Raise SystemError when self argument is not a set or frozenset. */ 247353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel t = PyTuple_New(0); 247453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assertRaises(PySet_Size(t) == -1, PyExc_SystemError); 247553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError); 247653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(t); 247753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 247853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Raise SystemError when self argument is not a set. */ 247953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel f = PyFrozenSet_New(dup); 248053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_Size(f) == 3); 248153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PyFrozenSet_CheckExact(f)); 248253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError); 248353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError); 248453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(f); 248553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 248653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Raise KeyError when popping from an empty set */ 248753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PyNumber_InPlaceSubtract(ob, ob) == ob); 248853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(ob); 248953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_GET_SIZE(ob) == 0); 249053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError); 249153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 249253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Restore the set from the copy using the PyNumber API */ 249353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PyNumber_InPlaceOr(ob, dup) == ob); 249453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(ob); 249553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 249653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel /* Verify constructors accept NULL arguments */ 249753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel f = PySet_New(NULL); 249853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(f != NULL); 249953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_GET_SIZE(f) == 0); 250053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(f); 250153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel f = PyFrozenSet_New(NULL); 250253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(f != NULL); 250353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PyFrozenSet_CheckExact(f)); 250453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel assert(PySet_GET_SIZE(f) == 0); 250553b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(f); 250653b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 250753b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(elem); 250853b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_DECREF(dup); 250953b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel Py_RETURN_TRUE; 251053b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel} 251153b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 251253b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#undef assertRaises 251353b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel 251453b2ba5790b57b3dcdfbb9fa5835a979d94908faDaryl McDaniel#endif 2515