14710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 24710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* set object implementation 34710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Written and maintained by Raymond D. Hettinger <python@rcn.com> 44710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Derived from Lib/sets.py and Objects/dictobject.c. 54710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 64710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Copyright (c) 2003-2007 Python Software Foundation. 74710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm All rights reserved. 84710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm*/ 94710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#include "Python.h" 114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#include "structmember.h" 124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* Set a key error with the specified argument, wrapping it in a 144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * tuple automatically so that tuple keys are not unpacked as the 154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * exception arguments. */ 164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic void 174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_key_error(PyObject *arg) 184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *tup; 204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm tup = PyTuple_Pack(1, arg); 214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!tup) 224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return; /* caller will expect error to be set anyway */ 234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_SetObject(PyExc_KeyError, tup); 244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(tup); 254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* This must be >= 1. */ 284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define PERTURB_SHIFT 5 294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* Object used as dummy key to fill deleted entries */ 314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject *dummy = NULL; /* Initialized by first call to make_new_set() */ 324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#ifdef Py_REF_DEBUG 344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyObject * 354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm_PySet_Dummy(void) 364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return dummy; 384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define INIT_NONZERO_SET_SLOTS(so) do { \ 424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (so)->table = (so)->smalltable; \ 434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (so)->mask = PySet_MINSIZE - 1; \ 444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (so)->hash = -1; \ 454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } while(0) 464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define EMPTY_TO_MINSIZE(so) do { \ 484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm memset((so)->smalltable, 0, sizeof((so)->smalltable)); \ 494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (so)->used = (so)->fill = 0; \ 504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm INIT_NONZERO_SET_SLOTS(so); \ 514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } while(0) 524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* Reuse scheme to save calls to malloc, free, and memset */ 544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#ifndef PySet_MAXFREELIST 554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define PySet_MAXFREELIST 80 564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PySetObject *free_list[PySet_MAXFREELIST]; 584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int numfree = 0; 594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* 614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmThe basic lookup function used by all operations. 624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmThis is based on Algorithm D from Knuth Vol. 3, Sec. 6.4. 634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmOpen addressing is preferred over chaining since the link overhead for 644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmchaining would be substantial (100% with typical malloc overhead). 654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmThe initial probe index is computed as hash mod the table size. Subsequent 674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmprobe indices are computed as explained in Objects/dictobject.c. 684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmAll arithmetic on hash should ignore overflow. 704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmUnlike the dictionary implementation, the lookkey functions can return 724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmNULL if the rich comparison returns an error. 734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm*/ 744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic setentry * 764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_lookkey(PySetObject *so, PyObject *key, register long hash) 774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register Py_ssize_t i; 794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register size_t perturb; 804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register setentry *freeslot; 814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register size_t mask = so->mask; 824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *table = so->table; 834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register setentry *entry; 844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register int cmp; 854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *startkey; 864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i = hash & mask; 884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry = &table[i]; 894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->key == NULL || entry->key == key) 904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return entry; 914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->key == dummy) 934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm freeslot = entry; 944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else { 954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->hash == hash) { 964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm startkey = entry->key; 974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(startkey); 984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); 994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(startkey); 1004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (cmp < 0) 1014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 1024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (table == so->table && entry->key == startkey) { 1034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (cmp > 0) 1044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return entry; 1054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else { 1074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* The compare did major nasty stuff to the 1084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * set: start over. 1094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 1104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_lookkey(so, key, hash); 1114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm freeslot = NULL; 1144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* In the loop, key == dummy is by far (factor of 100s) the 1174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm least likely outcome, so test for that last. */ 1184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (perturb = hash; ; perturb >>= PERTURB_SHIFT) { 1194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i = (i << 2) + i + perturb + 1; 1204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry = &table[i & mask]; 1214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->key == NULL) { 1224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (freeslot != NULL) 1234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry = freeslot; 1244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm break; 1254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->key == key) 1274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm break; 1284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->hash == hash && entry->key != dummy) { 1294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm startkey = entry->key; 1304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(startkey); 1314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); 1324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(startkey); 1334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (cmp < 0) 1344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 1354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (table == so->table && entry->key == startkey) { 1364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (cmp > 0) 1374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm break; 1384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else { 1404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* The compare did major nasty stuff to the 1414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * set: start over. 1424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 1434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_lookkey(so, key, hash); 1444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else if (entry->key == dummy && freeslot == NULL) 1474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm freeslot = entry; 1484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return entry; 1504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 1514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* 1534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * Hacked up version of set_lookkey which can assume keys are always strings; 1544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * This means we can always use _PyString_Eq directly and not have to check to 1554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * see if the comparison altered the table. 1564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 1574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic setentry * 1584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_lookkey_string(PySetObject *so, PyObject *key, register long hash) 1594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 1604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register Py_ssize_t i; 1614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register size_t perturb; 1624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register setentry *freeslot; 1634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register size_t mask = so->mask; 1644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *table = so->table; 1654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register setentry *entry; 1664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Make sure this function doesn't have to handle non-string keys, 1684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm including subclasses of str; e.g., one reason to subclass 1694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm strings is to override __eq__, and for speed we don't cater to 1704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm that here. */ 1714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyString_CheckExact(key)) { 1724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->lookup = set_lookkey; 1734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_lookkey(so, key, hash); 1744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i = hash & mask; 1764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry = &table[i]; 1774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->key == NULL || entry->key == key) 1784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return entry; 1794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->key == dummy) 1804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm freeslot = entry; 1814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else { 1824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->hash == hash && _PyString_Eq(entry->key, key)) 1834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return entry; 1844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm freeslot = NULL; 1854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* In the loop, key == dummy is by far (factor of 100s) the 1884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm least likely outcome, so test for that last. */ 1894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (perturb = hash; ; perturb >>= PERTURB_SHIFT) { 1904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i = (i << 2) + i + perturb + 1; 1914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry = &table[i & mask]; 1924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->key == NULL) 1934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return freeslot == NULL ? entry : freeslot; 1944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->key == key 1954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm || (entry->hash == hash 1964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm && entry->key != dummy 1974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm && _PyString_Eq(entry->key, key))) 1984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return entry; 1994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->key == dummy && freeslot == NULL) 2004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm freeslot = entry; 2014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 2024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(0); /* NOT REACHED */ 2034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 2044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 2054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* 2074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmInternal routine to insert a new key into the table. 2084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmUsed by the public insert routine. 2094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmEats a reference to key. 2104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm*/ 2114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 2124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_insert_key(register PySetObject *so, PyObject *key, long hash) 2134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 2144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register setentry *entry; 2154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm typedef setentry *(*lookupfunc)(PySetObject *, PyObject *, long); 2164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(so->lookup != NULL); 2184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry = so->lookup(so, key, hash); 2194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry == NULL) 2204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 2214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->key == NULL) { 2224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* UNUSED */ 2234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->fill++; 2244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry->key = key; 2254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry->hash = hash; 2264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->used++; 2274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } else if (entry->key == dummy) { 2284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* DUMMY */ 2294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry->key = key; 2304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry->hash = hash; 2314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->used++; 2324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(dummy); 2334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } else { 2344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* ACTIVE */ 2354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 2364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 2374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 2384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 2394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* 2414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmInternal routine used by set_table_resize() to insert an item which is 2424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmknown to be absent from the set. This routine also assumes that 2434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmthe set contains no deleted entries. Besides the performance benefit, 2444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmusing set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209). 2454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmNote that no refcounts are changed by this routine; if needed, the caller 2464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmis responsible for incref'ing `key`. 2474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm*/ 2484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic void 2494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_insert_clean(register PySetObject *so, PyObject *key, long hash) 2504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 2514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register size_t i; 2524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register size_t perturb; 2534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register size_t mask = (size_t)so->mask; 2544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *table = so->table; 2554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register setentry *entry; 2564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i = hash & mask; 2584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry = &table[i]; 2594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) { 2604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i = (i << 2) + i + perturb + 1; 2614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry = &table[i & mask]; 2624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 2634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->fill++; 2644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry->key = key; 2654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry->hash = hash; 2664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->used++; 2674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 2684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* 2704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmRestructure the table by allocating a new table and reinserting all 2714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmkeys again. When entries have been deleted, the new table may 2724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmactually be smaller than the old one. 2734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm*/ 2744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 2754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_table_resize(PySetObject *so, Py_ssize_t minused) 2764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 2774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t newsize; 2784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *oldtable, *newtable, *entry; 2794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t i; 2804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int is_oldtable_malloced; 2814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry small_copy[PySet_MINSIZE]; 2824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(minused >= 0); 2844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Find the smallest table size > minused. */ 2864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (newsize = PySet_MINSIZE; 2874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm newsize <= minused && newsize > 0; 2884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm newsize <<= 1) 2894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ; 2904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (newsize <= 0) { 2914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_NoMemory(); 2924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 2934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 2944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Get space for a new table. */ 2964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm oldtable = so->table; 2974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(oldtable != NULL); 2984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm is_oldtable_malloced = oldtable != so->smalltable; 2994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (newsize == PySet_MINSIZE) { 3014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* A large table is shrinking, or we can't get any smaller. */ 3024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm newtable = so->smalltable; 3034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (newtable == oldtable) { 3044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (so->fill == so->used) { 3054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* No dummies, so no point doing anything. */ 3064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 3074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 3084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* We're not going to resize it, but rebuild the 3094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm table anyway to purge old dummy entries. 3104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Subtle: This is *necessary* if fill==size, 3114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm as set_lookkey needs at least one virgin slot to 3124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm terminate failing searches. If fill < size, it's 3134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm merely desirable, as dummies slow searches. */ 3144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(so->fill > so->used); 3154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm memcpy(small_copy, oldtable, sizeof(small_copy)); 3164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm oldtable = small_copy; 3174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 3184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 3194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else { 3204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm newtable = PyMem_NEW(setentry, newsize); 3214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (newtable == NULL) { 3224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_NoMemory(); 3234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 3244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 3254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 3264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Make the set empty, using the new table. */ 3284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(newtable != oldtable); 3294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->table = newtable; 3304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->mask = newsize - 1; 3314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm memset(newtable, 0, sizeof(setentry) * newsize); 3324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->used = 0; 3334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i = so->fill; 3344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->fill = 0; 3354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Copy the data over; this is refcount-neutral for active entries; 3374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm dummy entries aren't copied over, of course */ 3384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (entry = oldtable; i > 0; entry++) { 3394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->key == NULL) { 3404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* UNUSED */ 3414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ; 3424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } else if (entry->key == dummy) { 3434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* DUMMY */ 3444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm --i; 3454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(entry->key == dummy); 3464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(entry->key); 3474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } else { 3484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* ACTIVE */ 3494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm --i; 3504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm set_insert_clean(so, entry->key, entry->hash); 3514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 3524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 3534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (is_oldtable_malloced) 3554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyMem_DEL(oldtable); 3564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 3574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 3584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* CAUTION: set_add_key/entry() must guarantee it won't resize the table */ 3604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 3624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_add_entry(register PySetObject *so, setentry *entry) 3634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 3644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register Py_ssize_t n_used; 3654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *key = entry->key; 3664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm long hash = entry->hash; 3674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(so->fill <= so->mask); /* at least one empty slot */ 3694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm n_used = so->used; 3704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(key); 3714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_insert_key(so, key, hash) == -1) { 3724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 3734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 3744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 3754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2)) 3764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 3774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4); 3784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 3794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 3814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_add_key(register PySetObject *so, PyObject *key) 3824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 3834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register long hash; 3844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register Py_ssize_t n_used; 3854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyString_CheckExact(key) || 3874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (hash = ((PyStringObject *) key)->ob_shash) == -1) { 3884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm hash = PyObject_Hash(key); 3894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (hash == -1) 3904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 3914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 3924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(so->fill <= so->mask); /* at least one empty slot */ 3934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm n_used = so->used; 3944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(key); 3954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_insert_key(so, key, hash) == -1) { 3964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 3974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 3984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 3994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2)) 4004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 4014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4); 4024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 4034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define DISCARD_NOTFOUND 0 4054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define DISCARD_FOUND 1 4064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 4084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_discard_entry(PySetObject *so, setentry *oldentry) 4094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ register setentry *entry; 4104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *old_key; 4114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry = (so->lookup)(so, oldentry->key, oldentry->hash); 4134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry == NULL) 4144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 4154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->key == NULL || entry->key == dummy) 4164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return DISCARD_NOTFOUND; 4174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm old_key = entry->key; 4184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(dummy); 4194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry->key = dummy; 4204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->used--; 4214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(old_key); 4224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return DISCARD_FOUND; 4234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 4244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 4264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_discard_key(PySetObject *so, PyObject *key) 4274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 4284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register long hash; 4294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register setentry *entry; 4304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *old_key; 4314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert (PyAnySet_Check(so)); 4334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyString_CheckExact(key) || 4344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (hash = ((PyStringObject *) key)->ob_shash) == -1) { 4354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm hash = PyObject_Hash(key); 4364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (hash == -1) 4374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 4384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 4394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry = (so->lookup)(so, key, hash); 4404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry == NULL) 4414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 4424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->key == NULL || entry->key == dummy) 4434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return DISCARD_NOTFOUND; 4444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm old_key = entry->key; 4454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(dummy); 4464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry->key = dummy; 4474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->used--; 4484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(old_key); 4494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return DISCARD_FOUND; 4504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 4514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 4534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_clear_internal(PySetObject *so) 4544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 4554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *entry, *table; 4564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int table_is_malloced; 4574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t fill; 4584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry small_copy[PySet_MINSIZE]; 4594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#ifdef Py_DEBUG 4604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t i, n; 4614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert (PyAnySet_Check(so)); 4624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm n = so->mask + 1; 4644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i = 0; 4654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 4664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm table = so->table; 4684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(table != NULL); 4694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm table_is_malloced = table != so->smalltable; 4704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* This is delicate. During the process of clearing the set, 4724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * decrefs can cause the set to mutate. To avoid fatal confusion 4734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * (voice of experience), we have to make the set empty before 4744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * clearing the slots, and never refer to anything via so->ref while 4754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * clearing. 4764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 4774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm fill = so->fill; 4784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (table_is_malloced) 4794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm EMPTY_TO_MINSIZE(so); 4804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else if (fill > 0) { 4824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* It's a small table with something that needs to be cleared. 4834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * Afraid the only safe way is to copy the set entries into 4844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * another small table first. 4854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 4864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm memcpy(small_copy, table, sizeof(small_copy)); 4874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm table = small_copy; 4884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm EMPTY_TO_MINSIZE(so); 4894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 4904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* else it's a small table that's already empty */ 4914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Now we can finally clear things. If C had refcounts, we could 4934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * assert that the refcount on table is 1 now, i.e. that this function 4944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * has unique access to it, so decref side-effects can't alter it. 4954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 4964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (entry = table; fill > 0; ++entry) { 4974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#ifdef Py_DEBUG 4984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(i < n); 4994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ++i; 5004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 5014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->key) { 5024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm --fill; 5034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(entry->key); 5044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 5054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#ifdef Py_DEBUG 5064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else 5074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(entry->key == NULL); 5084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 5094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 5104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (table_is_malloced) 5124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyMem_DEL(table); 5134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 5144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 5154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* 5174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * Iterate over a set table. Use like so: 5184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * 5194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * Py_ssize_t pos; 5204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * setentry *entry; 5214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * pos = 0; # important! pos should not otherwise be changed by you 5224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * while (set_next(yourset, &pos, &entry)) { 5234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * Refer to borrowed reference in entry->key. 5244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * } 5254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * 5264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * CAUTION: In general, it isn't safe to use set_next in a loop that 5274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * mutates the table. 5284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 5294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 5304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr) 5314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 5324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t i; 5334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t mask; 5344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register setentry *table; 5354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert (PyAnySet_Check(so)); 5374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i = *pos_ptr; 5384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(i >= 0); 5394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm table = so->table; 5404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm mask = so->mask; 5414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (i <= mask && (table[i].key == NULL || table[i].key == dummy)) 5424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i++; 5434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm *pos_ptr = i+1; 5444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (i > mask) 5454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 5464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(table[i].key != NULL); 5474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm *entry_ptr = &table[i]; 5484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 1; 5494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 5504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic void 5524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_dealloc(PySetObject *so) 5534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 5544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register setentry *entry; 5554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t fill = so->fill; 5564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject_GC_UnTrack(so); 5574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_TRASHCAN_SAFE_BEGIN(so) 5584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (so->weakreflist != NULL) 5594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject_ClearWeakRefs((PyObject *) so); 5604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (entry = so->table; fill > 0; entry++) { 5624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->key) { 5634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm --fill; 5644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(entry->key); 5654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 5664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 5674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (so->table != so->smalltable) 5684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyMem_DEL(so->table); 5694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (numfree < PySet_MAXFREELIST && PyAnySet_CheckExact(so)) 5704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm free_list[numfree++] = so; 5714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else 5724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_TYPE(so)->tp_free(so); 5734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_TRASHCAN_SAFE_END(so) 5744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 5754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 5774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_tp_print(PySetObject *so, FILE *fp, int flags) 5784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 5794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *entry; 5804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t pos=0; 5814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm char *emit = ""; /* No separator emitted on first pass */ 5824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm char *separator = ", "; 5834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int status = Py_ReprEnter((PyObject*)so); 5844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (status != 0) { 5864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (status < 0) 5874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return status; 5884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_BEGIN_ALLOW_THREADS 5894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm fprintf(fp, "%s(...)", so->ob_type->tp_name); 5904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_END_ALLOW_THREADS 5914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 5924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 5934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_BEGIN_ALLOW_THREADS 5954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm fprintf(fp, "%s([", so->ob_type->tp_name); 5964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_END_ALLOW_THREADS 5974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (set_next(so, &pos, &entry)) { 5984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_BEGIN_ALLOW_THREADS 5994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm fputs(emit, fp); 6004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_END_ALLOW_THREADS 6014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm emit = separator; 6024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyObject_Print(entry->key, fp, 0) != 0) { 6034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ReprLeave((PyObject*)so); 6044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 6054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 6064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 6074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_BEGIN_ALLOW_THREADS 6084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm fputs("])", fp); 6094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_END_ALLOW_THREADS 6104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ReprLeave((PyObject*)so); 6114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 6124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 6134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 6154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_repr(PySetObject *so) 6164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 6174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *keys, *result=NULL, *listrepr; 6184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int status = Py_ReprEnter((PyObject*)so); 6194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (status != 0) { 6214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (status < 0) 6224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 6234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return PyString_FromFormat("%s(...)", so->ob_type->tp_name); 6244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 6254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm keys = PySequence_List((PyObject *)so); 6274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (keys == NULL) 6284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm goto done; 6294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm listrepr = PyObject_Repr(keys); 6304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(keys); 6314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (listrepr == NULL) 6324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm goto done; 6334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = PyString_FromFormat("%s(%s)", so->ob_type->tp_name, 6354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyString_AS_STRING(listrepr)); 6364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(listrepr); 6374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdone: 6384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ReprLeave((PyObject*)so); 6394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result; 6404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 6414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic Py_ssize_t 6434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_len(PyObject *so) 6444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 6454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return ((PySetObject *)so)->used; 6464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 6474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 6494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_merge(PySetObject *so, PyObject *otherset) 6504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 6514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PySetObject *other; 6524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *key; 6534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm long hash; 6544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register Py_ssize_t i; 6554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register setentry *entry; 6564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert (PyAnySet_Check(so)); 6584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert (PyAnySet_Check(otherset)); 6594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm other = (PySetObject*)otherset; 6614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (other == so || other->used == 0) 6624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* a.update(a) or a.update({}); nothing to do */ 6634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 6644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Do one big resize at the start, rather than 6654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * incrementally resizing as we insert new keys. Expect 6664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * that there will be no (or few) overlapping keys. 6674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 6684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if ((so->fill + other->used)*3 >= (so->mask+1)*2) { 6694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_table_resize(so, (so->used + other->used)*2) != 0) 6704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 6714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 6724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (i = 0; i <= other->mask; i++) { 6734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry = &other->table[i]; 6744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm key = entry->key; 6754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm hash = entry->hash; 6764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (key != NULL && 6774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm key != dummy) { 6784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(key); 6794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_insert_key(so, key, hash) == -1) { 6804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 6814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 6824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 6834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 6844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 6854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 6864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 6874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 6894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_contains_key(PySetObject *so, PyObject *key) 6904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 6914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm long hash; 6924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *entry; 6934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyString_CheckExact(key) || 6954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (hash = ((PyStringObject *) key)->ob_shash) == -1) { 6964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm hash = PyObject_Hash(key); 6974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (hash == -1) 6984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 6994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 7004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry = (so->lookup)(so, key, hash); 7014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry == NULL) 7024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 7034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm key = entry->key; 7044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return key != NULL && key != dummy; 7054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 7064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 7074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 7084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_contains_entry(PySetObject *so, setentry *entry) 7094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 7104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *key; 7114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *lu_entry; 7124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 7134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm lu_entry = (so->lookup)(so, entry->key, entry->hash); 7144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (lu_entry == NULL) 7154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 7164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm key = lu_entry->key; 7174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return key != NULL && key != dummy; 7184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 7194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 7204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 7214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_pop(PySetObject *so) 7224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 7234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register Py_ssize_t i = 0; 7244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register setentry *entry; 7254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *key; 7264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 7274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert (PyAnySet_Check(so)); 7284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (so->used == 0) { 7294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_SetString(PyExc_KeyError, "pop from an empty set"); 7304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 7314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 7324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 7334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Set entry to "the first" unused or dummy set entry. We abuse 7344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * the hash field of slot 0 to hold a search finger: 7354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * If slot 0 has a value, use slot 0. 7364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * Else slot 0 is being used to hold a search finger, 7374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * and we use its hash value as the first index to look. 7384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 7394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry = &so->table[0]; 7404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (entry->key == NULL || entry->key == dummy) { 7414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i = entry->hash; 7424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* The hash field may be a real hash value, or it may be a 7434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * legit search finger, or it may be a once-legit search 7444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * finger that's out of bounds now because it wrapped around 7454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * or the table shrunk -- simply make sure it's in bounds now. 7464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 7474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (i > so->mask || i < 1) 7484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i = 1; /* skip slot 0 */ 7494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while ((entry = &so->table[i])->key == NULL || entry->key==dummy) { 7504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i++; 7514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (i > so->mask) 7524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i = 1; 7534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 7544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 7554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm key = entry->key; 7564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(dummy); 7574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry->key = dummy; 7584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->used--; 7594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->table[0].hash = i + 1; /* next place to start */ 7604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return key; 7614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 7624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 7634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\ 7644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmRaises KeyError if the set is empty."); 7654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 7664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 7674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_traverse(PySetObject *so, visitproc visit, void *arg) 7684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 7694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t pos = 0; 7704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *entry; 7714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 7724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (set_next(so, &pos, &entry)) 7734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_VISIT(entry->key); 7744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 7754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 7764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 7774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic long 7784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmfrozenset_hash(PyObject *self) 7794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 7804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PySetObject *so = (PySetObject *)self; 7814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm long h, hash = 1927868237L; 7824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *entry; 7834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t pos = 0; 7844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 7854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (so->hash != -1) 7864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return so->hash; 7874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 7884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm hash *= PySet_GET_SIZE(self) + 1; 7894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (set_next(so, &pos, &entry)) { 7904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Work to increase the bit dispersion for closely spaced hash 7914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm values. The is important because some use cases have many 7924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm combinations of a small number of elements with nearby 7934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm hashes so that many distinct combinations collapse to only 7944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm a handful of distinct hash values. */ 7954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm h = entry->hash; 7964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm hash ^= (h ^ (h << 16) ^ 89869747L) * 3644798167u; 7974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 7984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm hash = hash * 69069L + 907133923L; 7994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (hash == -1) 8004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm hash = 590923713L; 8014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->hash = hash; 8024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return hash; 8034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 8044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 8054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/***** Set iterator type ***********************************************/ 8064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 8074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmtypedef struct { 8084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject_HEAD 8094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PySetObject *si_set; /* Set to NULL when iterator is exhausted */ 8104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t si_used; 8114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t si_pos; 8124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t len; 8134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} setiterobject; 8144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 8154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic void 8164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmsetiter_dealloc(setiterobject *si) 8174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 8184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_XDECREF(si->si_set); 8194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject_GC_Del(si); 8204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 8214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 8224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 8234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmsetiter_traverse(setiterobject *si, visitproc visit, void *arg) 8244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 8254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_VISIT(si->si_set); 8264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 8274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 8284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 8294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 8304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmsetiter_len(setiterobject *si) 8314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 8324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t len = 0; 8334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (si->si_set != NULL && si->si_used == si->si_set->used) 8344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm len = si->len; 8354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return PyInt_FromLong(len); 8364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 8374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 8384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it))."); 8394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 8404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyMethodDef setiter_methods[] = { 8414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc}, 8424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {NULL, NULL} /* sentinel */ 8434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm}; 8444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 8454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject *setiter_iternext(setiterobject *si) 8464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 8474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *key; 8484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register Py_ssize_t i, mask; 8494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register setentry *entry; 8504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PySetObject *so = si->si_set; 8514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 8524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (so == NULL) 8534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 8544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert (PyAnySet_Check(so)); 8554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 8564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (si->si_used != so->used) { 8574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_SetString(PyExc_RuntimeError, 8584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "Set changed size during iteration"); 8594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm si->si_used = -1; /* Make this state sticky */ 8604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 8614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 8624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 8634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i = si->si_pos; 8644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(i>=0); 8654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry = so->table; 8664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm mask = so->mask; 8674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy)) 8684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i++; 8694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm si->si_pos = i+1; 8704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (i > mask) 8714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm goto fail; 8724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm si->len--; 8734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm key = entry[i].key; 8744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(key); 8754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return key; 8764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 8774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmfail: 8784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(so); 8794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm si->si_set = NULL; 8804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 8814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 8824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 8834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyTypeObject PySetIter_Type = { 8844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyVarObject_HEAD_INIT(&PyType_Type, 0) 8854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "setiterator", /* tp_name */ 8864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm sizeof(setiterobject), /* tp_basicsize */ 8874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_itemsize */ 8884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* methods */ 8894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (destructor)setiter_dealloc, /* tp_dealloc */ 8904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_print */ 8914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_getattr */ 8924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_setattr */ 8934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_compare */ 8944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_repr */ 8954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_as_number */ 8964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_as_sequence */ 8974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_as_mapping */ 8984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_hash */ 8994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_call */ 9004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_str */ 9014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject_GenericGetAttr, /* tp_getattro */ 9024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_setattro */ 9034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_as_buffer */ 9044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ 9054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_doc */ 9064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (traverseproc)setiter_traverse, /* tp_traverse */ 9074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_clear */ 9084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_richcompare */ 9094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_weaklistoffset */ 9104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject_SelfIter, /* tp_iter */ 9114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (iternextfunc)setiter_iternext, /* tp_iternext */ 9124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setiter_methods, /* tp_methods */ 9134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, 9144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm}; 9154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 9164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 9174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_iter(PySetObject *so) 9184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 9194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type); 9204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (si == NULL) 9214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 9224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(so); 9234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm si->si_set = so; 9244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm si->si_used = so->used; 9254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm si->si_pos = 0; 9264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm si->len = so->used; 9274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm _PyObject_GC_TRACK(si); 9284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (PyObject *)si; 9294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 9304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 9314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 9324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_update_internal(PySetObject *so, PyObject *other) 9334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 9344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *key, *it; 9354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 9364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyAnySet_Check(other)) 9374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_merge(so, other); 9384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 9394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyDict_CheckExact(other)) { 9404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *value; 9414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t pos = 0; 9424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm long hash; 9434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t dictsize = PyDict_Size(other); 9444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 9454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Do one big resize at the start, rather than 9464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * incrementally resizing as we insert new keys. Expect 9474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * that there will be no (or few) overlapping keys. 9484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 9494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (dictsize == -1) 9504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 9514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if ((so->fill + dictsize)*3 >= (so->mask+1)*2) { 9524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_table_resize(so, (so->used + dictsize)*2) != 0) 9534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 9544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 9554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (_PyDict_Next(other, &pos, &key, &value, &hash)) { 9564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry an_entry; 9574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 9584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm an_entry.hash = hash; 9594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm an_entry.key = key; 9604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_add_entry(so, &an_entry) == -1) 9614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 9624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 9634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 9644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 9654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 9664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm it = PyObject_GetIter(other); 9674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (it == NULL) 9684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 9694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 9704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while ((key = PyIter_Next(it)) != NULL) { 9714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_add_key(so, key) == -1) { 9724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(it); 9734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 9744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 9754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 9764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 9774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 9784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(it); 9794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyErr_Occurred()) 9804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 9814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 9824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 9834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 9844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 9854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_update(PySetObject *so, PyObject *args) 9864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 9874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t i; 9884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 9894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) { 9904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *other = PyTuple_GET_ITEM(args, i); 9914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_update_internal(so, other) == -1) 9924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 9934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 9944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_NONE; 9954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 9964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 9974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(update_doc, 9984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm"Update a set with the union of itself and others."); 9994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 10004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 10014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmmake_new_set(PyTypeObject *type, PyObject *iterable) 10024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 10034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm register PySetObject *so = NULL; 10044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 10054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (dummy == NULL) { /* Auto-initialize dummy */ 10064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm dummy = PyString_FromString("<dummy key>"); 10074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (dummy == NULL) 10084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 10094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 10104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 10114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* create PySetObject structure */ 10124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (numfree && 10134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (type == &PySet_Type || type == &PyFrozenSet_Type)) { 10144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so = free_list[--numfree]; 10154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert (so != NULL && PyAnySet_CheckExact(so)); 10164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_TYPE(so) = type; 10174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm _Py_NewReference((PyObject *)so); 10184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm EMPTY_TO_MINSIZE(so); 10194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject_GC_Track(so); 10204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } else { 10214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so = (PySetObject *)type->tp_alloc(type, 0); 10224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (so == NULL) 10234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 10244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* tp_alloc has already zeroed the structure */ 10254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(so->table == NULL && so->fill == 0 && so->used == 0); 10264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm INIT_NONZERO_SET_SLOTS(so); 10274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 10284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 10294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->lookup = set_lookkey_string; 10304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so->weakreflist = NULL; 10314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 10324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (iterable != NULL) { 10334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_update_internal(so, iterable) == -1) { 10344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(so); 10354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 10364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 10374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 10384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 10394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (PyObject *)so; 10404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 10414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 10424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* The empty frozenset is a singleton */ 10434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject *emptyfrozenset = NULL; 10444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 10454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 10464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmfrozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 10474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 10484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *iterable = NULL, *result; 10494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 10504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds)) 10514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 10524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 10534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable)) 10544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 10554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 10564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (type != &PyFrozenSet_Type) 10574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return make_new_set(type, iterable); 10584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 10594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (iterable != NULL) { 10604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* frozenset(f) is idempotent */ 10614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyFrozenSet_CheckExact(iterable)) { 10624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(iterable); 10634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return iterable; 10644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 10654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = make_new_set(type, iterable); 10664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (result == NULL || PySet_GET_SIZE(result)) 10674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result; 10684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 10694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 10704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* The empty frozenset is a singleton */ 10714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (emptyfrozenset == NULL) 10724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm emptyfrozenset = make_new_set(type, NULL); 10734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_XINCREF(emptyfrozenset); 10744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return emptyfrozenset; 10754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 10764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 10774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmvoid 10784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPySet_Fini(void) 10794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 10804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PySetObject *so; 10814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 10824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (numfree) { 10834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm numfree--; 10844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so = free_list[numfree]; 10854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject_GC_Del(so); 10864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 10874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_CLEAR(dummy); 10884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_CLEAR(emptyfrozenset); 10894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 10904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 10914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 10924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 10934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 10944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds)) 10954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 10964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 10974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return make_new_set(type, NULL); 10984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 10994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* set_swap_bodies() switches the contents of any two sets by moving their 11014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm internal data pointers and, if needed, copying the internal smalltables. 11024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Semantically equivalent to: 11034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t 11054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm The function always succeeds and it leaves both objects in a stable state. 11074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Useful for creating temporary frozensets from sets for membership testing 11084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm in __contains__(), discard(), and remove(). Also useful for operations 11094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm that update in-place (by allowing an intermediate result to be swapped 11104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm into one of the original inputs). 11114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm*/ 11124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic void 11144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_swap_bodies(PySetObject *a, PySetObject *b) 11154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 11164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t t; 11174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *u; 11184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *(*f)(PySetObject *so, PyObject *key, long hash); 11194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry tab[PySet_MINSIZE]; 11204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm long h; 11214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm t = a->fill; a->fill = b->fill; b->fill = t; 11234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm t = a->used; a->used = b->used; b->used = t; 11244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm t = a->mask; a->mask = b->mask; b->mask = t; 11254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm u = a->table; 11274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (a->table == a->smalltable) 11284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm u = b->smalltable; 11294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm a->table = b->table; 11304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (b->table == b->smalltable) 11314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm a->table = a->smalltable; 11324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm b->table = u; 11334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm f = a->lookup; a->lookup = b->lookup; b->lookup = f; 11354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (a->table == a->smalltable || b->table == b->smalltable) { 11374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm memcpy(tab, a->smalltable, sizeof(tab)); 11384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm memcpy(a->smalltable, b->smalltable, sizeof(tab)); 11394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm memcpy(b->smalltable, tab, sizeof(tab)); 11404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 11414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type) && 11434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) { 11444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm h = a->hash; a->hash = b->hash; b->hash = h; 11454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } else { 11464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm a->hash = -1; 11474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm b->hash = -1; 11484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 11494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 11504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 11524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_copy(PySetObject *so) 11534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 11544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return make_new_set(Py_TYPE(so), (PyObject *)so); 11554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 11564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 11584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmfrozenset_copy(PySetObject *so) 11594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 11604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyFrozenSet_CheckExact(so)) { 11614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(so); 11624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (PyObject *)so; 11634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 11644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_copy(so); 11654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 11664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(copy_doc, "Return a shallow copy of a set."); 11684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 11704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_clear(PySetObject *so) 11714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 11724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm set_clear_internal(so); 11734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_NONE; 11744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 11754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(clear_doc, "Remove all elements from this set."); 11774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 11794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_union(PySetObject *so, PyObject *args) 11804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 11814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PySetObject *result; 11824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *other; 11834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t i; 11844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = (PySetObject *)set_copy(so); 11864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (result == NULL) 11874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 11884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) { 11904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm other = PyTuple_GET_ITEM(args, i); 11914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if ((PyObject *)so == other) 11924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm continue; 11934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_update_internal(result, other) == -1) { 11944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 11954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 11964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 11974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 11984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (PyObject *)result; 11994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 12004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 12014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(union_doc, 12024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "Return the union of sets as a new set.\n\ 12034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm\n\ 12044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm(i.e. all elements that are in either set.)"); 12054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 12064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 12074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_or(PySetObject *so, PyObject *other) 12084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 12094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PySetObject *result; 12104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 12114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) { 12124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(Py_NotImplemented); 12134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Py_NotImplemented; 12144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 12154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 12164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = (PySetObject *)set_copy(so); 12174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (result == NULL) 12184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 12194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if ((PyObject *)so == other) 12204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (PyObject *)result; 12214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_update_internal(result, other) == -1) { 12224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 12234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 12244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 12254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (PyObject *)result; 12264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 12274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 12284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 12294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_ior(PySetObject *so, PyObject *other) 12304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 12314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyAnySet_Check(other)) { 12324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(Py_NotImplemented); 12334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Py_NotImplemented; 12344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 12354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_update_internal(so, other) == -1) 12364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 12374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(so); 12384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (PyObject *)so; 12394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 12404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 12414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 12424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_intersection(PySetObject *so, PyObject *other) 12434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 12444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PySetObject *result; 12454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *key, *it, *tmp; 12464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 12474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if ((PyObject *)so == other) 12484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_copy(so); 12494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 12504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = (PySetObject *)make_new_set(Py_TYPE(so), NULL); 12514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (result == NULL) 12524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 12534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 12544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyAnySet_Check(other)) { 12554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t pos = 0; 12564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *entry; 12574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 12584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) { 12594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm tmp = (PyObject *)so; 12604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so = (PySetObject *)other; 12614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm other = tmp; 12624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 12634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 12644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (set_next((PySetObject *)other, &pos, &entry)) { 12654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int rv = set_contains_entry(so, entry); 12664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv == -1) { 12674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 12684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 12694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 12704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv) { 12714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_add_entry(result, entry) == -1) { 12724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 12734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 12744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 12754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 12764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 12774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (PyObject *)result; 12784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 12794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 12804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm it = PyObject_GetIter(other); 12814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (it == NULL) { 12824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 12834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 12844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 12854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 12864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while ((key = PyIter_Next(it)) != NULL) { 12874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int rv; 12884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry entry; 12894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm long hash = PyObject_Hash(key); 12904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 12914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (hash == -1) { 12924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(it); 12934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 12944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 12954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 12964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 12974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry.hash = hash; 12984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry.key = key; 12994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rv = set_contains_entry(so, &entry); 13004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv == -1) { 13014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(it); 13024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 13034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 13044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 13054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 13064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv) { 13074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_add_entry(result, &entry) == -1) { 13084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(it); 13094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 13104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 13114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 13124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 13134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 13144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 13154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 13164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(it); 13174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyErr_Occurred()) { 13184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 13194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 13204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 13214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (PyObject *)result; 13224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 13234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 13244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 13254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_intersection_multi(PySetObject *so, PyObject *args) 13264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 13274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t i; 13284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *result = (PyObject *)so; 13294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 13304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyTuple_GET_SIZE(args) == 0) 13314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_copy(so); 13324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 13334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(so); 13344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) { 13354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *other = PyTuple_GET_ITEM(args, i); 13364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *newresult = set_intersection((PySetObject *)result, other); 13374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (newresult == NULL) { 13384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 13394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 13404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 13414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 13424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = newresult; 13434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 13444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result; 13454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 13464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 13474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(intersection_doc, 13484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm"Return the intersection of two or more sets as a new set.\n\ 13494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm\n\ 13504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm(i.e. elements that are common to all of the sets.)"); 13514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 13524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 13534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_intersection_update(PySetObject *so, PyObject *other) 13544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 13554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *tmp; 13564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 13574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm tmp = set_intersection(so, other); 13584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (tmp == NULL) 13594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 13604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm set_swap_bodies(so, (PySetObject *)tmp); 13614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(tmp); 13624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_NONE; 13634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 13644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 13654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 13664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_intersection_update_multi(PySetObject *so, PyObject *args) 13674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 13684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *tmp; 13694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 13704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm tmp = set_intersection_multi(so, args); 13714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (tmp == NULL) 13724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 13734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm set_swap_bodies(so, (PySetObject *)tmp); 13744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(tmp); 13754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_NONE; 13764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 13774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 13784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(intersection_update_doc, 13794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm"Update a set with the intersection of itself and another."); 13804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 13814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 13824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_and(PySetObject *so, PyObject *other) 13834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 13844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) { 13854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(Py_NotImplemented); 13864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Py_NotImplemented; 13874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 13884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_intersection(so, other); 13894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 13904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 13914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 13924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_iand(PySetObject *so, PyObject *other) 13934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 13944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *result; 13954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 13964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyAnySet_Check(other)) { 13974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(Py_NotImplemented); 13984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Py_NotImplemented; 13994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 14004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = set_intersection_update(so, other); 14014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (result == NULL) 14024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 14034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 14044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(so); 14054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (PyObject *)so; 14064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 14074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 14084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 14094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_isdisjoint(PySetObject *so, PyObject *other) 14104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 14114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *key, *it, *tmp; 14124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 14134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if ((PyObject *)so == other) { 14144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PySet_GET_SIZE(so) == 0) 14154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_TRUE; 14164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else 14174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_FALSE; 14184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 14194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 14204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyAnySet_CheckExact(other)) { 14214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t pos = 0; 14224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *entry; 14234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 14244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) { 14254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm tmp = (PyObject *)so; 14264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so = (PySetObject *)other; 14274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm other = tmp; 14284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 14294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (set_next((PySetObject *)other, &pos, &entry)) { 14304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int rv = set_contains_entry(so, entry); 14314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv == -1) 14324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 14334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv) 14344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_FALSE; 14354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 14364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_TRUE; 14374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 14384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 14394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm it = PyObject_GetIter(other); 14404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (it == NULL) 14414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 14424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 14434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while ((key = PyIter_Next(it)) != NULL) { 14444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int rv; 14454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry entry; 14464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm long hash = PyObject_Hash(key); 14474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 14484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (hash == -1) { 14494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 14504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(it); 14514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 14524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 14534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry.hash = hash; 14544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entry.key = key; 14554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rv = set_contains_entry(so, &entry); 14564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 14574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv == -1) { 14584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(it); 14594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 14604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 14614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv) { 14624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(it); 14634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_FALSE; 14644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 14654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 14664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(it); 14674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyErr_Occurred()) 14684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 14694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_TRUE; 14704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 14714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 14724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(isdisjoint_doc, 14734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm"Return True if two sets have a null intersection."); 14744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 14754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 14764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_difference_update_internal(PySetObject *so, PyObject *other) 14774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 14784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if ((PyObject *)so == other) 14794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_clear_internal(so); 14804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 14814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyAnySet_Check(other)) { 14824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *entry; 14834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t pos = 0; 14844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 14854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (set_next((PySetObject *)other, &pos, &entry)) 14864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_discard_entry(so, entry) == -1) 14874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 14884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } else { 14894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *key, *it; 14904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm it = PyObject_GetIter(other); 14914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (it == NULL) 14924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 14934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 14944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while ((key = PyIter_Next(it)) != NULL) { 14954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_discard_key(so, key) == -1) { 14964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(it); 14974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 14984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 14994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 15004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 15014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 15024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(it); 15034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyErr_Occurred()) 15044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 15054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 15064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* If more than 1/5 are dummies, then resize them away. */ 15074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if ((so->fill - so->used) * 5 < so->mask) 15084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 15094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4); 15104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 15114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 15124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 15134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_difference_update(PySetObject *so, PyObject *args) 15144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 15154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t i; 15164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 15174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) { 15184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *other = PyTuple_GET_ITEM(args, i); 15194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_difference_update_internal(so, other) == -1) 15204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 15214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 15224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_NONE; 15234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 15244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 15254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(difference_update_doc, 15264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm"Remove all elements of another set from this set."); 15274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 15284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 15294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_difference(PySetObject *so, PyObject *other) 15304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 15314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *result; 15324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *entry; 15334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t pos = 0; 15344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 15354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyAnySet_Check(other) && !PyDict_CheckExact(other)) { 15364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = set_copy(so); 15374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (result == NULL) 15384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 15394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_difference_update_internal((PySetObject *)result, other) != -1) 15404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result; 15414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 15424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 15434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 15444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 15454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = make_new_set(Py_TYPE(so), NULL); 15464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (result == NULL) 15474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 15484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 15494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyDict_CheckExact(other)) { 15504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (set_next(so, &pos, &entry)) { 15514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry entrycopy; 15524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entrycopy.hash = entry->hash; 15534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm entrycopy.key = entry->key; 15544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!_PyDict_Contains(other, entry->key, entry->hash)) { 15554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_add_entry((PySetObject *)result, &entrycopy) == -1) { 15564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 15574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 15584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 15594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 15604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 15614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result; 15624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 15634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 15644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (set_next(so, &pos, &entry)) { 15654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int rv = set_contains_entry((PySetObject *)other, entry); 15664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv == -1) { 15674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 15684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 15694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 15704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!rv) { 15714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_add_entry((PySetObject *)result, entry) == -1) { 15724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 15734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 15744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 15754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 15764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 15774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result; 15784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 15794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 15804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 15814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_difference_multi(PySetObject *so, PyObject *args) 15824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 15834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t i; 15844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *result, *other; 15854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 15864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyTuple_GET_SIZE(args) == 0) 15874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_copy(so); 15884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 15894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm other = PyTuple_GET_ITEM(args, 0); 15904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = set_difference(so, other); 15914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (result == NULL) 15924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 15934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 15944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) { 15954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm other = PyTuple_GET_ITEM(args, i); 15964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_difference_update_internal((PySetObject *)result, other) == -1) { 15974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 15984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 15994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 16004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 16014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result; 16024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 16034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 16044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(difference_doc, 16054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm"Return the difference of two or more sets as a new set.\n\ 16064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm\n\ 16074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm(i.e. all elements that are in this set but not the others.)"); 16084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 16094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_sub(PySetObject *so, PyObject *other) 16104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 16114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) { 16124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(Py_NotImplemented); 16134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Py_NotImplemented; 16144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 16154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_difference(so, other); 16164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 16174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 16184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 16194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_isub(PySetObject *so, PyObject *other) 16204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 16214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyAnySet_Check(other)) { 16224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(Py_NotImplemented); 16234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Py_NotImplemented; 16244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 16254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_difference_update_internal(so, other) == -1) 16264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 16274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(so); 16284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (PyObject *)so; 16294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 16304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 16314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 16324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_symmetric_difference_update(PySetObject *so, PyObject *other) 16334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 16344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PySetObject *otherset; 16354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *key; 16364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t pos = 0; 16374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *entry; 16384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 16394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if ((PyObject *)so == other) 16404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_clear(so); 16414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 16424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyDict_CheckExact(other)) { 16434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *value; 16444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int rv; 16454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm long hash; 16464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (_PyDict_Next(other, &pos, &key, &value, &hash)) { 16474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry an_entry; 16484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 16494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(key); 16504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm an_entry.hash = hash; 16514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm an_entry.key = key; 16524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 16534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rv = set_discard_entry(so, &an_entry); 16544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv == -1) { 16554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 16564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 16574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 16584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv == DISCARD_NOTFOUND) { 16594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_add_entry(so, &an_entry) == -1) { 16604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 16614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 16624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 16634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 16644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(key); 16654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 16664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_NONE; 16674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 16684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 16694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PyAnySet_Check(other)) { 16704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(other); 16714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm otherset = (PySetObject *)other; 16724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } else { 16734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm otherset = (PySetObject *)make_new_set(Py_TYPE(so), other); 16744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (otherset == NULL) 16754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 16764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 16774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 16784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (set_next(otherset, &pos, &entry)) { 16794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int rv = set_discard_entry(so, entry); 16804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv == -1) { 16814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(otherset); 16824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 16834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 16844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv == DISCARD_NOTFOUND) { 16854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_add_entry(so, entry) == -1) { 16864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(otherset); 16874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 16884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 16894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 16904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 16914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(otherset); 16924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_NONE; 16934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 16944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 16954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(symmetric_difference_update_doc, 16964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm"Update a set with the symmetric difference of itself and another."); 16974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 16984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 16994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_symmetric_difference(PySetObject *so, PyObject *other) 17004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 17014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *rv; 17024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PySetObject *otherset; 17034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 17044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm otherset = (PySetObject *)make_new_set(Py_TYPE(so), other); 17054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (otherset == NULL) 17064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 17074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rv = set_symmetric_difference_update(otherset, (PyObject *)so); 17084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv == NULL) 17094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 17104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(rv); 17114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (PyObject *)otherset; 17124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 17134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 17144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(symmetric_difference_doc, 17154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm"Return the symmetric difference of two sets as a new set.\n\ 17164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm\n\ 17174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm(i.e. all elements that are in exactly one of the sets.)"); 17184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 17194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 17204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_xor(PySetObject *so, PyObject *other) 17214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 17224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) { 17234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(Py_NotImplemented); 17244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Py_NotImplemented; 17254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 17264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_symmetric_difference(so, other); 17274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 17284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 17294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 17304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_ixor(PySetObject *so, PyObject *other) 17314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 17324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *result; 17334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 17344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyAnySet_Check(other)) { 17354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(Py_NotImplemented); 17364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Py_NotImplemented; 17374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 17384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = set_symmetric_difference_update(so, other); 17394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (result == NULL) 17404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 17414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(result); 17424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(so); 17434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (PyObject *)so; 17444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 17454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 17464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 17474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_issubset(PySetObject *so, PyObject *other) 17484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 17494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *entry; 17504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t pos = 0; 17514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 17524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyAnySet_Check(other)) { 17534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *tmp, *result; 17544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm tmp = make_new_set(&PySet_Type, other); 17554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (tmp == NULL) 17564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 17574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = set_issubset(so, tmp); 17584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(tmp); 17594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result; 17604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 17614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other)) 17624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_FALSE; 17634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 17644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (set_next(so, &pos, &entry)) { 17654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int rv = set_contains_entry((PySetObject *)other, entry); 17664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv == -1) 17674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 17684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!rv) 17694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_FALSE; 17704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 17714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_TRUE; 17724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 17734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 17744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(issubset_doc, "Report whether another set contains this set."); 17754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 17764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 17774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_issuperset(PySetObject *so, PyObject *other) 17784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 17794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *tmp, *result; 17804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 17814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyAnySet_Check(other)) { 17824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm tmp = make_new_set(&PySet_Type, other); 17834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (tmp == NULL) 17844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 17854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = set_issuperset(so, tmp); 17864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(tmp); 17874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result; 17884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 17894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_issubset((PySetObject *)other, (PyObject *)so); 17904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 17914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 17924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set."); 17934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 17944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 17954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_richcompare(PySetObject *v, PyObject *w, int op) 17964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 17974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *r1, *r2; 17984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 17994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if(!PyAnySet_Check(w)) { 18004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (op == Py_EQ) 18014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_FALSE; 18024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (op == Py_NE) 18034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_TRUE; 18044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_SetString(PyExc_TypeError, "can only compare to a set"); 18054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 18064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 18074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm switch (op) { 18084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm case Py_EQ: 18094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w)) 18104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_FALSE; 18114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (v->hash != -1 && 18124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ((PySetObject *)w)->hash != -1 && 18134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm v->hash != ((PySetObject *)w)->hash) 18144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_FALSE; 18154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_issubset(v, w); 18164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm case Py_NE: 18174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm r1 = set_richcompare(v, w, Py_EQ); 18184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (r1 == NULL) 18194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 18204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm r2 = PyBool_FromLong(PyObject_Not(r1)); 18214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(r1); 18224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return r2; 18234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm case Py_LE: 18244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_issubset(v, w); 18254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm case Py_GE: 18264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_issuperset(v, w); 18274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm case Py_LT: 18284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w)) 18294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_FALSE; 18304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_issubset(v, w); 18314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm case Py_GT: 18324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w)) 18334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_FALSE; 18344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_issuperset(v, w); 18354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 18364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(Py_NotImplemented); 18374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Py_NotImplemented; 18384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 18394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 18404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 18414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_nocmp(PyObject *self, PyObject *other) 18424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 18434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_SetString(PyExc_TypeError, "cannot compare sets using cmp()"); 18444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 18454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 18464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 18474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 18484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_add(PySetObject *so, PyObject *key) 18494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 18504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_add_key(so, key) == -1) 18514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 18524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_NONE; 18534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 18544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 18554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(add_doc, 18564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm"Add an element to a set.\n\ 18574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm\n\ 18584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmThis has no effect if the element is already present."); 18594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 18604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 18614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_contains(PySetObject *so, PyObject *key) 18624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 18634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *tmpkey; 18644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int rv; 18654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 18664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rv = set_contains_key(so, key); 18674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv == -1) { 18684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError)) 18694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 18704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_Clear(); 18714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm tmpkey = make_new_set(&PyFrozenSet_Type, key); 18724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (tmpkey == NULL) 18734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 18744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rv = set_contains(so, tmpkey); 18754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(tmpkey); 18764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 18774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return rv; 18784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 18794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 18804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 18814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_direct_contains(PySetObject *so, PyObject *key) 18824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 18834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm long result; 18844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 18854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = set_contains(so, key); 18864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (result == -1) 18874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 18884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return PyBool_FromLong(result); 18894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 18904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 18914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x."); 18924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 18934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 18944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_remove(PySetObject *so, PyObject *key) 18954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 18964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *tmpkey; 18974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int rv; 18984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 18994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rv = set_discard_key(so, key); 19004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv == -1) { 19014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError)) 19024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 19034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_Clear(); 19044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm tmpkey = make_new_set(&PyFrozenSet_Type, key); 19054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (tmpkey == NULL) 19064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 19074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rv = set_discard_key(so, tmpkey); 19084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(tmpkey); 19094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv == -1) 19104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 19114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 19124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 19134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv == DISCARD_NOTFOUND) { 19144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm set_key_error(key); 19154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 19164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 19174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_NONE; 19184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 19194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 19204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(remove_doc, 19214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm"Remove an element from a set; it must be a member.\n\ 19224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm\n\ 19234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmIf the element is not a member, raise a KeyError."); 19244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 19254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 19264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_discard(PySetObject *so, PyObject *key) 19274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 19284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *tmpkey, *result; 19294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int rv; 19304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 19314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm rv = set_discard_key(so, key); 19324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (rv == -1) { 19334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError)) 19344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 19354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_Clear(); 19364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm tmpkey = make_new_set(&PyFrozenSet_Type, key); 19374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (tmpkey == NULL) 19384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 19394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = set_discard(so, tmpkey); 19404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(tmpkey); 19414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result; 19424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 19434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_NONE; 19444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 19454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 19464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(discard_doc, 19474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm"Remove an element from a set if it is a member.\n\ 19484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm\n\ 19494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmIf the element is not a member, do nothing."); 19504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 19514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 19524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_reduce(PySetObject *so) 19534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 19544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL; 19554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 19564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm keys = PySequence_List((PyObject *)so); 19574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (keys == NULL) 19584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm goto done; 19594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm args = PyTuple_Pack(1, keys); 19604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (args == NULL) 19614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm goto done; 19624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm dict = PyObject_GetAttrString((PyObject *)so, "__dict__"); 19634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (dict == NULL) { 19644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_Clear(); 19654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm dict = Py_None; 19664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(dict); 19674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 19684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = PyTuple_Pack(3, Py_TYPE(so), args, dict); 19694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdone: 19704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_XDECREF(args); 19714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_XDECREF(keys); 19724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_XDECREF(dict); 19734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result; 19744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 19754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 19764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(reduce_doc, "Return state information for pickling."); 19774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 19784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 19794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_sizeof(PySetObject *so) 19804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 19814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t res; 19824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 19834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm res = sizeof(PySetObject); 19844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (so->table != so->smalltable) 19854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm res = res + (so->mask + 1) * sizeof(setentry); 19864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return PyInt_FromSsize_t(res); 19874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 19884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 19894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes"); 19904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic int 19914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset_init(PySetObject *self, PyObject *args, PyObject *kwds) 19924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 19934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *iterable = NULL; 19944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 19954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyAnySet_Check(self)) 19964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 19974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (PySet_Check(self) && !_PyArg_NoKeywords("set()", kwds)) 19984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 19994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable)) 20004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 20014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm set_clear_internal(self); 20024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self->hash = -1; 20034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (iterable == NULL) 20044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 20054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_update_internal(self, iterable); 20064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 20074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 20084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PySequenceMethods set_as_sequence = { 20094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm set_len, /* sq_length */ 20104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* sq_concat */ 20114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* sq_repeat */ 20124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* sq_item */ 20134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* sq_slice */ 20144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* sq_ass_item */ 20154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* sq_ass_slice */ 20164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (objobjproc)set_contains, /* sq_contains */ 20174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm}; 20184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 20194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* set object ********************************************************/ 20204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 20214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#ifdef Py_DEBUG 20224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject *test_c_api(PySetObject *so); 20234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 20244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(test_c_api_doc, "Exercises C API. Returns True.\n\ 20254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmAll is well if assertions don't fail."); 20264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 20274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 20284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyMethodDef set_methods[] = { 20294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"add", (PyCFunction)set_add, METH_O, 20304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm add_doc}, 20314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"clear", (PyCFunction)set_clear, METH_NOARGS, 20324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm clear_doc}, 20334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST, 20344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm contains_doc}, 20354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"copy", (PyCFunction)set_copy, METH_NOARGS, 20364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm copy_doc}, 20374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"discard", (PyCFunction)set_discard, METH_O, 20384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm discard_doc}, 20394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"difference", (PyCFunction)set_difference_multi, METH_VARARGS, 20404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm difference_doc}, 20414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"difference_update", (PyCFunction)set_difference_update, METH_VARARGS, 20424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm difference_update_doc}, 20434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS, 20444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm intersection_doc}, 20454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"intersection_update",(PyCFunction)set_intersection_update_multi, METH_VARARGS, 20464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm intersection_update_doc}, 20474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O, 20484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm isdisjoint_doc}, 20494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"issubset", (PyCFunction)set_issubset, METH_O, 20504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm issubset_doc}, 20514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"issuperset", (PyCFunction)set_issuperset, METH_O, 20524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm issuperset_doc}, 20534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"pop", (PyCFunction)set_pop, METH_NOARGS, 20544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm pop_doc}, 20554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS, 20564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm reduce_doc}, 20574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"remove", (PyCFunction)set_remove, METH_O, 20584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm remove_doc}, 20594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS, 20604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm sizeof_doc}, 20614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O, 20624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm symmetric_difference_doc}, 20634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O, 20644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm symmetric_difference_update_doc}, 20654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#ifdef Py_DEBUG 20664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"test_c_api", (PyCFunction)test_c_api, METH_NOARGS, 20674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm test_c_api_doc}, 20684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 20694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"union", (PyCFunction)set_union, METH_VARARGS, 20704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm union_doc}, 20714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"update", (PyCFunction)set_update, METH_VARARGS, 20724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm update_doc}, 20734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {NULL, NULL} /* sentinel */ 20744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm}; 20754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 20764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyNumberMethods set_as_number = { 20774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_add*/ 20784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (binaryfunc)set_sub, /*nb_subtract*/ 20794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_multiply*/ 20804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_divide*/ 20814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_remainder*/ 20824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_divmod*/ 20834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_power*/ 20844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_negative*/ 20854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_positive*/ 20864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_absolute*/ 20874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_nonzero*/ 20884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_invert*/ 20894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_lshift*/ 20904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_rshift*/ 20914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (binaryfunc)set_and, /*nb_and*/ 20924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (binaryfunc)set_xor, /*nb_xor*/ 20934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (binaryfunc)set_or, /*nb_or*/ 20944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_coerce*/ 20954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_int*/ 20964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_long*/ 20974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_float*/ 20984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_oct*/ 20994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_hex*/ 21004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_inplace_add*/ 21014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (binaryfunc)set_isub, /*nb_inplace_subtract*/ 21024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_inplace_multiply*/ 21034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_inplace_divide*/ 21044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_inplace_remainder*/ 21054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_inplace_power*/ 21064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_inplace_lshift*/ 21074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_inplace_rshift*/ 21084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (binaryfunc)set_iand, /*nb_inplace_and*/ 21094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (binaryfunc)set_ixor, /*nb_inplace_xor*/ 21104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (binaryfunc)set_ior, /*nb_inplace_or*/ 21114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm}; 21124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 21134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(set_doc, 21144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm"set() -> new empty set object\n\ 21154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmset(iterable) -> new set object\n\ 21164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm\n\ 21174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmBuild an unordered collection of unique elements."); 21184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 21194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyTypeObject PySet_Type = { 21204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyVarObject_HEAD_INIT(&PyType_Type, 0) 21214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "set", /* tp_name */ 21224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm sizeof(PySetObject), /* tp_basicsize */ 21234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_itemsize */ 21244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* methods */ 21254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (destructor)set_dealloc, /* tp_dealloc */ 21264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (printfunc)set_tp_print, /* tp_print */ 21274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_getattr */ 21284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_setattr */ 21294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm set_nocmp, /* tp_compare */ 21304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (reprfunc)set_repr, /* tp_repr */ 21314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm &set_as_number, /* tp_as_number */ 21324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm &set_as_sequence, /* tp_as_sequence */ 21334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_as_mapping */ 21344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (hashfunc)PyObject_HashNotImplemented, /* tp_hash */ 21354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_call */ 21364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_str */ 21374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject_GenericGetAttr, /* tp_getattro */ 21384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_setattro */ 21394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_as_buffer */ 21404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_CHECKTYPES | 21414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_TPFLAGS_BASETYPE, /* tp_flags */ 21424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm set_doc, /* tp_doc */ 21434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (traverseproc)set_traverse, /* tp_traverse */ 21444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (inquiry)set_clear_internal, /* tp_clear */ 21454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (richcmpfunc)set_richcompare, /* tp_richcompare */ 21464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */ 21474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (getiterfunc)set_iter, /* tp_iter */ 21484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_iternext */ 21494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm set_methods, /* tp_methods */ 21504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_members */ 21514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_getset */ 21524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_base */ 21534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_dict */ 21544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_descr_get */ 21554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_descr_set */ 21564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_dictoffset */ 21574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (initproc)set_init, /* tp_init */ 21584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyType_GenericAlloc, /* tp_alloc */ 21594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm set_new, /* tp_new */ 21604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject_GC_Del, /* tp_free */ 21614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm}; 21624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 21634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* frozenset object ********************************************************/ 21644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 21654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 21664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyMethodDef frozenset_methods[] = { 21674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST, 21684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm contains_doc}, 21694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"copy", (PyCFunction)frozenset_copy, METH_NOARGS, 21704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm copy_doc}, 21714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"difference", (PyCFunction)set_difference_multi, METH_VARARGS, 21724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm difference_doc}, 21734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS, 21744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm intersection_doc}, 21754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O, 21764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm isdisjoint_doc}, 21774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"issubset", (PyCFunction)set_issubset, METH_O, 21784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm issubset_doc}, 21794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"issuperset", (PyCFunction)set_issuperset, METH_O, 21804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm issuperset_doc}, 21814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS, 21824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm reduce_doc}, 21834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS, 21844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm sizeof_doc}, 21854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O, 21864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm symmetric_difference_doc}, 21874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {"union", (PyCFunction)set_union, METH_VARARGS, 21884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm union_doc}, 21894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm {NULL, NULL} /* sentinel */ 21904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm}; 21914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 21924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyNumberMethods frozenset_as_number = { 21934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_add*/ 21944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (binaryfunc)set_sub, /*nb_subtract*/ 21954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_multiply*/ 21964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_divide*/ 21974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_remainder*/ 21984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_divmod*/ 21994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_power*/ 22004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_negative*/ 22014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_positive*/ 22024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_absolute*/ 22034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_nonzero*/ 22044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_invert*/ 22054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_lshift*/ 22064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /*nb_rshift*/ 22074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (binaryfunc)set_and, /*nb_and*/ 22084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (binaryfunc)set_xor, /*nb_xor*/ 22094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (binaryfunc)set_or, /*nb_or*/ 22104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm}; 22114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 22124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyDoc_STRVAR(frozenset_doc, 22134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm"frozenset() -> empty frozenset object\n\ 22144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmfrozenset(iterable) -> frozenset object\n\ 22154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm\n\ 22164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmBuild an immutable unordered collection of unique elements."); 22174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 22184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyTypeObject PyFrozenSet_Type = { 22194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyVarObject_HEAD_INIT(&PyType_Type, 0) 22204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "frozenset", /* tp_name */ 22214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm sizeof(PySetObject), /* tp_basicsize */ 22224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_itemsize */ 22234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* methods */ 22244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (destructor)set_dealloc, /* tp_dealloc */ 22254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (printfunc)set_tp_print, /* tp_print */ 22264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_getattr */ 22274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_setattr */ 22284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm set_nocmp, /* tp_compare */ 22294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (reprfunc)set_repr, /* tp_repr */ 22304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm &frozenset_as_number, /* tp_as_number */ 22314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm &set_as_sequence, /* tp_as_sequence */ 22324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_as_mapping */ 22334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm frozenset_hash, /* tp_hash */ 22344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_call */ 22354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_str */ 22364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject_GenericGetAttr, /* tp_getattro */ 22374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_setattro */ 22384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_as_buffer */ 22394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_CHECKTYPES | 22404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_TPFLAGS_BASETYPE, /* tp_flags */ 22414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm frozenset_doc, /* tp_doc */ 22424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (traverseproc)set_traverse, /* tp_traverse */ 22434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (inquiry)set_clear_internal, /* tp_clear */ 22444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (richcmpfunc)set_richcompare, /* tp_richcompare */ 22454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */ 22464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (getiterfunc)set_iter, /* tp_iter */ 22474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_iternext */ 22484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm frozenset_methods, /* tp_methods */ 22494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_members */ 22504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_getset */ 22514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_base */ 22524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_dict */ 22534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_descr_get */ 22544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_descr_set */ 22554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_dictoffset */ 22564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0, /* tp_init */ 22574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyType_GenericAlloc, /* tp_alloc */ 22584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm frozenset_new, /* tp_new */ 22594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject_GC_Del, /* tp_free */ 22604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm}; 22614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 22624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 22634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/***** C API functions *************************************************/ 22644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 22654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyObject * 22664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPySet_New(PyObject *iterable) 22674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 22684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return make_new_set(&PySet_Type, iterable); 22694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 22704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 22714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyObject * 22724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyFrozenSet_New(PyObject *iterable) 22734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 22744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return make_new_set(&PyFrozenSet_Type, iterable); 22754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 22764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 22774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPy_ssize_t 22784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPySet_Size(PyObject *anyset) 22794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 22804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyAnySet_Check(anyset)) { 22814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_BadInternalCall(); 22824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 22834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 22844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return PySet_GET_SIZE(anyset); 22854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 22864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 22874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmint 22884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPySet_Clear(PyObject *set) 22894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 22904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PySet_Check(set)) { 22914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_BadInternalCall(); 22924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 22934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 22944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_clear_internal((PySetObject *)set); 22954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 22964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 22974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmint 22984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPySet_Contains(PyObject *anyset, PyObject *key) 22994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 23004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyAnySet_Check(anyset)) { 23014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_BadInternalCall(); 23024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 23034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 23044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_contains_key((PySetObject *)anyset, key); 23054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 23064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 23074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmint 23084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPySet_Discard(PyObject *set, PyObject *key) 23094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 23104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PySet_Check(set)) { 23114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_BadInternalCall(); 23124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 23134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 23144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_discard_key((PySetObject *)set, key); 23154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 23164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 23174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmint 23184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPySet_Add(PyObject *anyset, PyObject *key) 23194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 23204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PySet_Check(anyset) && 23214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) { 23224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_BadInternalCall(); 23234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 23244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 23254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_add_key((PySetObject *)anyset, key); 23264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 23274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 23284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmint 23294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm_PySet_Next(PyObject *set, Py_ssize_t *pos, PyObject **key) 23304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 23314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *entry_ptr; 23324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 23334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyAnySet_Check(set)) { 23344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_BadInternalCall(); 23354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 23364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 23374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_next((PySetObject *)set, pos, &entry_ptr) == 0) 23384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 23394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm *key = entry_ptr->key; 23404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 1; 23414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 23424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 23434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmint 23444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm_PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, long *hash) 23454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 23464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm setentry *entry; 23474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 23484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PyAnySet_Check(set)) { 23494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_BadInternalCall(); 23504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 23514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 23524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_next((PySetObject *)set, pos, &entry) == 0) 23534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0; 23544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm *key = entry->key; 23554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm *hash = entry->hash; 23564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 1; 23574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 23584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 23594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPyObject * 23604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPySet_Pop(PyObject *set) 23614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 23624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PySet_Check(set)) { 23634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_BadInternalCall(); 23644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 23654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 23664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_pop((PySetObject *)set); 23674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 23684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 23694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmint 23704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm_PySet_Update(PyObject *set, PyObject *iterable) 23714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 23724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (!PySet_Check(set)) { 23734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_BadInternalCall(); 23744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -1; 23754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 23764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return set_update_internal((PySetObject *)set, iterable); 23774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 23784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 23794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#ifdef Py_DEBUG 23804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 23814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* Test code to be called with any three element set. 23824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Returns True and original set is restored. */ 23834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 23844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define assertRaises(call_return_value, exception) \ 23854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm do { \ 23864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(call_return_value); \ 23874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PyErr_ExceptionMatches(exception)); \ 23884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyErr_Clear(); \ 23894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } while(0) 23904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 23914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic PyObject * 23924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmtest_c_api(PySetObject *so) 23934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 23944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t count; 23954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm char *s; 23964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_ssize_t i; 23974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x; 23984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *ob = (PyObject *)so; 23994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject *str; 24004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 24014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Verify preconditions */ 24024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PyAnySet_Check(ob)); 24034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PyAnySet_CheckExact(ob)); 24044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(!PyFrozenSet_CheckExact(ob)); 24054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 24064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* so.clear(); so |= set("abc"); */ 24074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm str = PyString_FromString("abc"); 24084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (str == NULL) 24094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 24104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm set_clear_internal(so); 24114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (set_update_internal(so, str) == -1) { 24124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(str); 24134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NULL; 24144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 24154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(str); 24164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 24174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Exercise type/size checks */ 24184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_Size(ob) == 3); 24194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_GET_SIZE(ob) == 3); 24204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 24214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Raise TypeError for non-iterable constructor arguments */ 24224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError); 24234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError); 24244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 24254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Raise TypeError for unhashable key */ 24264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm dup = PySet_New(ob); 24274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError); 24284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError); 24294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError); 24304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 24314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Exercise successful pop, contains, add, and discard */ 24324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elem = PySet_Pop(ob); 24334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_Contains(ob, elem) == 0); 24344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_GET_SIZE(ob) == 2); 24354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_Add(ob, elem) == 0); 24364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_Contains(ob, elem) == 1); 24374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_GET_SIZE(ob) == 3); 24384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_Discard(ob, elem) == 1); 24394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_GET_SIZE(ob) == 2); 24404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_Discard(ob, elem) == 0); 24414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_GET_SIZE(ob) == 2); 24424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 24434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Exercise clear */ 24444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm dup2 = PySet_New(dup); 24454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_Clear(dup2) == 0); 24464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_Size(dup2) == 0); 24474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(dup2); 24484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 24494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Raise SystemError on clear or update of frozen set */ 24504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm f = PyFrozenSet_New(dup); 24514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assertRaises(PySet_Clear(f) == -1, PyExc_SystemError); 24524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError); 24534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_Add(f, elem) == 0); 24544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_INCREF(f); 24554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError); 24564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(f); 24574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(f); 24584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 24594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Exercise direct iteration */ 24604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm i = 0, count = 0; 24614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while (_PySet_Next((PyObject *)dup, &i, &x)) { 24624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm s = PyString_AsString(x); 24634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c')); 24644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm count++; 24654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 24664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(count == 3); 24674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 24684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Exercise updates */ 24694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm dup2 = PySet_New(NULL); 24704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(_PySet_Update(dup2, dup) == 0); 24714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_Size(dup2) == 3); 24724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(_PySet_Update(dup2, dup) == 0); 24734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_Size(dup2) == 3); 24744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(dup2); 24754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 24764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Raise SystemError when self argument is not a set or frozenset. */ 24774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm t = PyTuple_New(0); 24784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assertRaises(PySet_Size(t) == -1, PyExc_SystemError); 24794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError); 24804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(t); 24814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 24824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Raise SystemError when self argument is not a set. */ 24834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm f = PyFrozenSet_New(dup); 24844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_Size(f) == 3); 24854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PyFrozenSet_CheckExact(f)); 24864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError); 24874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError); 24884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(f); 24894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 24904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Raise KeyError when popping from an empty set */ 24914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PyNumber_InPlaceSubtract(ob, ob) == ob); 24924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(ob); 24934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_GET_SIZE(ob) == 0); 24944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError); 24954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 24964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Restore the set from the copy using the PyNumber API */ 24974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PyNumber_InPlaceOr(ob, dup) == ob); 24984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(ob); 24994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 25004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Verify constructors accept NULL arguments */ 25014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm f = PySet_New(NULL); 25024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(f != NULL); 25034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_GET_SIZE(f) == 0); 25044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(f); 25054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm f = PyFrozenSet_New(NULL); 25064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(f != NULL); 25074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PyFrozenSet_CheckExact(f)); 25084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert(PySet_GET_SIZE(f) == 0); 25094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(f); 25104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 25114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(elem); 25124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_DECREF(dup); 25134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_RETURN_TRUE; 25144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 25154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 25164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#undef assertRaises 25174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 25184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 2519