blob: 0af1f154fefcbd50bf4663474f898a98437177fb [file] [log] [blame]
Raymond Hettingerc991db22005-08-11 07:58:45 +00001
Raymond Hettingera9d99362005-08-05 00:01:15 +00002/* set object implementation
3 Written and maintained by Raymond D. Hettinger <python@rcn.com>
4 Derived from Lib/sets.py and Objects/dictobject.c.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00005
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00006 Copyright (c) 2003-6 Python Software Foundation.
Raymond Hettingera9d99362005-08-05 00:01:15 +00007 All rights reserved.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00008*/
9
Raymond Hettingera690a992003-11-16 16:17:49 +000010#include "Python.h"
Raymond Hettingera9d99362005-08-05 00:01:15 +000011#include "structmember.h"
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000012
Thomas Wouters89f507f2006-12-13 04:49:30 +000013/* Set a key error with the specified argument, wrapping it in a
14 * tuple automatically so that tuple keys are not unpacked as the
15 * exception arguments. */
16static void
17set_key_error(PyObject *arg)
18{
19 PyObject *tup;
20 tup = PyTuple_Pack(1, arg);
21 if (!tup)
22 return; /* caller will expect error to be set anyway */
23 PyErr_SetObject(PyExc_KeyError, tup);
24 Py_DECREF(tup);
25}
26
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000027/* This must be >= 1. */
28#define PERTURB_SHIFT 5
29
30/* Object used as dummy key to fill deleted entries */
Raymond Hettingera9d99362005-08-05 00:01:15 +000031static PyObject *dummy = NULL; /* Initialized by first call to make_new_set() */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000032
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000033#ifdef Py_REF_DEBUG
34PyObject *
35_PySet_Dummy(void)
36{
37 return dummy;
38}
39#endif
40
Raymond Hettingerbc841a12005-08-07 13:02:53 +000041#define INIT_NONZERO_SET_SLOTS(so) do { \
42 (so)->table = (so)->smalltable; \
43 (so)->mask = PySet_MINSIZE - 1; \
44 (so)->hash = -1; \
45 } while(0)
46
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000047#define EMPTY_TO_MINSIZE(so) do { \
48 memset((so)->smalltable, 0, sizeof((so)->smalltable)); \
49 (so)->used = (so)->fill = 0; \
Raymond Hettingerbc841a12005-08-07 13:02:53 +000050 INIT_NONZERO_SET_SLOTS(so); \
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000051 } while(0)
52
Raymond Hettingerbc841a12005-08-07 13:02:53 +000053/* Reuse scheme to save calls to malloc, free, and memset */
54#define MAXFREESETS 80
55static PySetObject *free_sets[MAXFREESETS];
56static int num_free_sets = 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000057
58/*
59The basic lookup function used by all operations.
60This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
61Open addressing is preferred over chaining since the link overhead for
62chaining would be substantial (100% with typical malloc overhead).
63
64The initial probe index is computed as hash mod the table size. Subsequent
Raymond Hettingerbc841a12005-08-07 13:02:53 +000065probe indices are computed as explained in Objects/dictobject.c.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000066
67All arithmetic on hash should ignore overflow.
68
Raymond Hettinger9bda1d62005-09-16 07:14:21 +000069Unlike the dictionary implementation, the lookkey functions can return
70NULL if the rich comparison returns an error.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000071*/
72
73static setentry *
74set_lookkey(PySetObject *so, PyObject *key, register long hash)
75{
Martin v. Löwis18e16552006-02-15 17:27:45 +000076 register Py_ssize_t i;
77 register size_t perturb;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000078 register setentry *freeslot;
Thomas Wouters0e3f5912006-08-11 14:57:12 +000079 register size_t mask = so->mask;
Raymond Hettingera580c472005-08-05 17:19:54 +000080 setentry *table = so->table;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +000081 register setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000082 register int cmp;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000083 PyObject *startkey;
84
85 i = hash & mask;
Raymond Hettingera580c472005-08-05 17:19:54 +000086 entry = &table[i];
Raymond Hettinger06d8cf82005-07-31 15:36:06 +000087 if (entry->key == NULL || entry->key == key)
88 return entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000089
Raymond Hettinger06d8cf82005-07-31 15:36:06 +000090 if (entry->key == dummy)
91 freeslot = entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000092 else {
Raymond Hettinger06d8cf82005-07-31 15:36:06 +000093 if (entry->hash == hash) {
Raymond Hettinger06d8cf82005-07-31 15:36:06 +000094 startkey = entry->key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000095 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
96 if (cmp < 0)
Raymond Hettinger9bda1d62005-09-16 07:14:21 +000097 return NULL;
Raymond Hettingera580c472005-08-05 17:19:54 +000098 if (table == so->table && entry->key == startkey) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000099 if (cmp > 0)
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000100 return entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000101 }
102 else {
103 /* The compare did major nasty stuff to the
104 * set: start over.
105 */
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000106 return set_lookkey(so, key, hash);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000107 }
108 }
109 freeslot = NULL;
110 }
111
112 /* In the loop, key == dummy is by far (factor of 100s) the
113 least likely outcome, so test for that last. */
114 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
115 i = (i << 2) + i + perturb + 1;
Raymond Hettingera580c472005-08-05 17:19:54 +0000116 entry = &table[i & mask];
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000117 if (entry->key == NULL) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000118 if (freeslot != NULL)
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000119 entry = freeslot;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000120 break;
121 }
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000122 if (entry->key == key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000123 break;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000124 if (entry->hash == hash && entry->key != dummy) {
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000125 startkey = entry->key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000126 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
127 if (cmp < 0)
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000128 return NULL;
Raymond Hettingera580c472005-08-05 17:19:54 +0000129 if (table == so->table && entry->key == startkey) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000130 if (cmp > 0)
131 break;
132 }
133 else {
134 /* The compare did major nasty stuff to the
135 * set: start over.
136 */
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000137 return set_lookkey(so, key, hash);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000138 }
139 }
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000140 else if (entry->key == dummy && freeslot == NULL)
141 freeslot = entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000142 }
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000143 return entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000144}
145
146/*
147 * Hacked up version of set_lookkey which can assume keys are always strings;
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000148 * This means we can always use _PyString_Eq directly and not have to check to
149 * see if the comparison altered the table.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000150 */
151static setentry *
152set_lookkey_string(PySetObject *so, PyObject *key, register long hash)
153{
Martin v. Löwis18e16552006-02-15 17:27:45 +0000154 register Py_ssize_t i;
155 register size_t perturb;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000156 register setentry *freeslot;
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000157 register size_t mask = so->mask;
Raymond Hettingera580c472005-08-05 17:19:54 +0000158 setentry *table = so->table;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000159 register setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000160
161 /* Make sure this function doesn't have to handle non-string keys,
162 including subclasses of str; e.g., one reason to subclass
163 strings is to override __eq__, and for speed we don't cater to
164 that here. */
165 if (!PyString_CheckExact(key)) {
166 so->lookup = set_lookkey;
167 return set_lookkey(so, key, hash);
168 }
169 i = hash & mask;
Raymond Hettingera580c472005-08-05 17:19:54 +0000170 entry = &table[i];
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000171 if (entry->key == NULL || entry->key == key)
172 return entry;
Raymond Hettingered6c1ef2005-08-13 08:28:03 +0000173 if (entry->key == dummy)
174 freeslot = entry;
175 else {
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000176 if (entry->hash == hash && _PyString_Eq(entry->key, key))
177 return entry;
Raymond Hettingered6c1ef2005-08-13 08:28:03 +0000178 freeslot = NULL;
179 }
180
181 /* In the loop, key == dummy is by far (factor of 100s) the
182 least likely outcome, so test for that last. */
183 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
184 i = (i << 2) + i + perturb + 1;
185 entry = &table[i & mask];
186 if (entry->key == NULL)
187 return freeslot == NULL ? entry : freeslot;
188 if (entry->key == key
189 || (entry->hash == hash
190 && entry->key != dummy
191 && _PyString_Eq(entry->key, key)))
192 return entry;
193 if (entry->key == dummy && freeslot == NULL)
194 freeslot = entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000195 }
Thomas Wouters89f507f2006-12-13 04:49:30 +0000196 assert(0); /* NOT REACHED */
197 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000198}
199
200/*
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000201Internal routine to insert a new key into the table.
Thomas Wouters89f507f2006-12-13 04:49:30 +0000202Used by the public insert routine.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000203Eats a reference to key.
204*/
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000205static int
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000206set_insert_key(register PySetObject *so, PyObject *key, long hash)
207{
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000208 register setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000209 typedef setentry *(*lookupfunc)(PySetObject *, PyObject *, long);
210
211 assert(so->lookup != NULL);
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000212 entry = so->lookup(so, key, hash);
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000213 if (entry == NULL)
214 return -1;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000215 if (entry->key == NULL) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000216 /* UNUSED */
217 so->fill++;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000218 entry->key = key;
219 entry->hash = hash;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000220 so->used++;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000221 } else if (entry->key == dummy) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000222 /* DUMMY */
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000223 entry->key = key;
224 entry->hash = hash;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000225 so->used++;
226 Py_DECREF(dummy);
227 } else {
228 /* ACTIVE */
229 Py_DECREF(key);
230 }
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000231 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000232}
233
234/*
Thomas Wouters89f507f2006-12-13 04:49:30 +0000235Internal routine used by set_table_resize() to insert an item which is
236known to be absent from the set. This routine also assumes that
237the set contains no deleted entries. Besides the performance benefit,
238using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
239Note that no refcounts are changed by this routine; if needed, the caller
240is responsible for incref'ing `key`.
241*/
242static void
243set_insert_clean(register PySetObject *so, PyObject *key, long hash)
244{
245 register size_t i;
246 register size_t perturb;
247 register size_t mask = (size_t)so->mask;
248 setentry *table = so->table;
249 register setentry *entry;
250
251 i = hash & mask;
252 entry = &table[i];
253 for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) {
254 i = (i << 2) + i + perturb + 1;
255 entry = &table[i & mask];
256 }
257 so->fill++;
258 entry->key = key;
259 entry->hash = hash;
260 so->used++;
261}
262
263/*
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000264Restructure the table by allocating a new table and reinserting all
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000265keys again. When entries have been deleted, the new table may
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000266actually be smaller than the old one.
267*/
268static int
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000269set_table_resize(PySetObject *so, Py_ssize_t minused)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000270{
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000271 Py_ssize_t newsize;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000272 setentry *oldtable, *newtable, *entry;
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000273 Py_ssize_t i;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000274 int is_oldtable_malloced;
275 setentry small_copy[PySet_MINSIZE];
276
277 assert(minused >= 0);
278
279 /* Find the smallest table size > minused. */
280 for (newsize = PySet_MINSIZE;
281 newsize <= minused && newsize > 0;
282 newsize <<= 1)
283 ;
284 if (newsize <= 0) {
285 PyErr_NoMemory();
286 return -1;
287 }
288
289 /* Get space for a new table. */
290 oldtable = so->table;
291 assert(oldtable != NULL);
292 is_oldtable_malloced = oldtable != so->smalltable;
293
294 if (newsize == PySet_MINSIZE) {
295 /* A large table is shrinking, or we can't get any smaller. */
296 newtable = so->smalltable;
297 if (newtable == oldtable) {
298 if (so->fill == so->used) {
299 /* No dummies, so no point doing anything. */
300 return 0;
301 }
302 /* We're not going to resize it, but rebuild the
303 table anyway to purge old dummy entries.
304 Subtle: This is *necessary* if fill==size,
305 as set_lookkey needs at least one virgin slot to
306 terminate failing searches. If fill < size, it's
307 merely desirable, as dummies slow searches. */
308 assert(so->fill > so->used);
309 memcpy(small_copy, oldtable, sizeof(small_copy));
310 oldtable = small_copy;
311 }
312 }
313 else {
314 newtable = PyMem_NEW(setentry, newsize);
315 if (newtable == NULL) {
316 PyErr_NoMemory();
317 return -1;
318 }
319 }
320
321 /* Make the set empty, using the new table. */
322 assert(newtable != oldtable);
323 so->table = newtable;
324 so->mask = newsize - 1;
325 memset(newtable, 0, sizeof(setentry) * newsize);
326 so->used = 0;
327 i = so->fill;
328 so->fill = 0;
329
330 /* Copy the data over; this is refcount-neutral for active entries;
331 dummy entries aren't copied over, of course */
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000332 for (entry = oldtable; i > 0; entry++) {
333 if (entry->key == NULL) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000334 /* UNUSED */
335 ;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000336 } else if (entry->key == dummy) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000337 /* DUMMY */
338 --i;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000339 assert(entry->key == dummy);
340 Py_DECREF(entry->key);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000341 } else {
342 /* ACTIVE */
343 --i;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000344 set_insert_clean(so, entry->key, entry->hash);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000345 }
346 }
347
348 if (is_oldtable_malloced)
349 PyMem_DEL(oldtable);
350 return 0;
351}
352
Raymond Hettingerc991db22005-08-11 07:58:45 +0000353/* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
354
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000355static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000356set_add_entry(register PySetObject *so, setentry *entry)
357{
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000358 register Py_ssize_t n_used;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000359
360 assert(so->fill <= so->mask); /* at least one empty slot */
361 n_used = so->used;
362 Py_INCREF(entry->key);
Thomas Wouters89f507f2006-12-13 04:49:30 +0000363 if (set_insert_key(so, entry->key, entry->hash) == -1) {
364 Py_DECREF(entry->key);
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000365 return -1;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000366 }
Raymond Hettingerc991db22005-08-11 07:58:45 +0000367 if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
368 return 0;
369 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
370}
371
372static int
373set_add_key(register PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000374{
375 register long hash;
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000376 register Py_ssize_t n_used;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000377
Raymond Hettingerc991db22005-08-11 07:58:45 +0000378 if (!PyString_CheckExact(key) ||
379 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000380 hash = PyObject_Hash(key);
381 if (hash == -1)
382 return -1;
383 }
384 assert(so->fill <= so->mask); /* at least one empty slot */
385 n_used = so->used;
386 Py_INCREF(key);
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000387 if (set_insert_key(so, key, hash) == -1) {
388 Py_DECREF(key);
389 return -1;
390 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000391 if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
392 return 0;
Raymond Hettingerbc841a12005-08-07 13:02:53 +0000393 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000394}
395
396#define DISCARD_NOTFOUND 0
397#define DISCARD_FOUND 1
398
399static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000400set_discard_entry(PySetObject *so, setentry *oldentry)
401{ register setentry *entry;
402 PyObject *old_key;
403
404 entry = (so->lookup)(so, oldentry->key, oldentry->hash);
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000405 if (entry == NULL)
406 return -1;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000407 if (entry->key == NULL || entry->key == dummy)
408 return DISCARD_NOTFOUND;
409 old_key = entry->key;
410 Py_INCREF(dummy);
411 entry->key = dummy;
412 so->used--;
413 Py_DECREF(old_key);
414 return DISCARD_FOUND;
415}
416
417static int
418set_discard_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000419{
420 register long hash;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000421 register setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000422 PyObject *old_key;
423
424 assert (PyAnySet_Check(so));
425 if (!PyString_CheckExact(key) ||
426 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
427 hash = PyObject_Hash(key);
428 if (hash == -1)
429 return -1;
430 }
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000431 entry = (so->lookup)(so, key, hash);
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000432 if (entry == NULL)
433 return -1;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000434 if (entry->key == NULL || entry->key == dummy)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000435 return DISCARD_NOTFOUND;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000436 old_key = entry->key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000437 Py_INCREF(dummy);
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000438 entry->key = dummy;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000439 so->used--;
440 Py_DECREF(old_key);
441 return DISCARD_FOUND;
442}
443
Raymond Hettingerfe889f32005-08-06 05:43:39 +0000444static int
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000445set_clear_internal(PySetObject *so)
446{
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000447 setentry *entry, *table;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000448 int table_is_malloced;
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000449 Py_ssize_t fill;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000450 setentry small_copy[PySet_MINSIZE];
451#ifdef Py_DEBUG
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000452 Py_ssize_t i, n;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000453 assert (PyAnySet_Check(so));
Raymond Hettingera580c472005-08-05 17:19:54 +0000454
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000455 n = so->mask + 1;
456 i = 0;
457#endif
458
459 table = so->table;
460 assert(table != NULL);
461 table_is_malloced = table != so->smalltable;
462
463 /* This is delicate. During the process of clearing the set,
464 * decrefs can cause the set to mutate. To avoid fatal confusion
465 * (voice of experience), we have to make the set empty before
Raymond Hettingerfe889f32005-08-06 05:43:39 +0000466 * clearing the slots, and never refer to anything via so->ref while
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000467 * clearing.
468 */
469 fill = so->fill;
470 if (table_is_malloced)
471 EMPTY_TO_MINSIZE(so);
472
473 else if (fill > 0) {
474 /* It's a small table with something that needs to be cleared.
475 * Afraid the only safe way is to copy the set entries into
476 * another small table first.
477 */
478 memcpy(small_copy, table, sizeof(small_copy));
479 table = small_copy;
480 EMPTY_TO_MINSIZE(so);
481 }
482 /* else it's a small table that's already empty */
483
484 /* Now we can finally clear things. If C had refcounts, we could
485 * assert that the refcount on table is 1 now, i.e. that this function
486 * has unique access to it, so decref side-effects can't alter it.
487 */
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000488 for (entry = table; fill > 0; ++entry) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000489#ifdef Py_DEBUG
490 assert(i < n);
491 ++i;
492#endif
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000493 if (entry->key) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000494 --fill;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000495 Py_DECREF(entry->key);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000496 }
497#ifdef Py_DEBUG
498 else
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000499 assert(entry->key == NULL);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000500#endif
501 }
502
503 if (table_is_malloced)
504 PyMem_DEL(table);
Raymond Hettingerfe889f32005-08-06 05:43:39 +0000505 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000506}
507
508/*
509 * Iterate over a set table. Use like so:
510 *
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000511 * Py_ssize_t pos;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000512 * setentry *entry;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000513 * pos = 0; # important! pos should not otherwise be changed by you
Raymond Hettingerc991db22005-08-11 07:58:45 +0000514 * while (set_next(yourset, &pos, &entry)) {
515 * Refer to borrowed reference in entry->key.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000516 * }
517 *
Raymond Hettingerc991db22005-08-11 07:58:45 +0000518 * CAUTION: In general, it isn't safe to use set_next in a loop that
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000519 * mutates the table.
520 */
521static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000522set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000523{
Martin v. Löwis18e16552006-02-15 17:27:45 +0000524 Py_ssize_t i;
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000525 Py_ssize_t mask;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000526 register setentry *table;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000527
528 assert (PyAnySet_Check(so));
Raymond Hettingerc991db22005-08-11 07:58:45 +0000529 i = *pos_ptr;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000530 assert(i >= 0);
Raymond Hettingerc991db22005-08-11 07:58:45 +0000531 table = so->table;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000532 mask = so->mask;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000533 while (i <= mask && (table[i].key == NULL || table[i].key == dummy))
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000534 i++;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000535 *pos_ptr = i+1;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000536 if (i > mask)
537 return 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000538 assert(table[i].key != NULL);
539 *entry_ptr = &table[i];
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000540 return 1;
541}
542
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000543static void
544set_dealloc(PySetObject *so)
545{
546 register setentry *entry;
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000547 Py_ssize_t fill = so->fill;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000548 PyObject_GC_UnTrack(so);
549 Py_TRASHCAN_SAFE_BEGIN(so)
550 if (so->weakreflist != NULL)
551 PyObject_ClearWeakRefs((PyObject *) so);
552
553 for (entry = so->table; fill > 0; entry++) {
554 if (entry->key) {
555 --fill;
556 Py_DECREF(entry->key);
557 }
558 }
559 if (so->table != so->smalltable)
560 PyMem_DEL(so->table);
561 if (num_free_sets < MAXFREESETS && PyAnySet_CheckExact(so))
562 free_sets[num_free_sets++] = so;
563 else
564 so->ob_type->tp_free(so);
565 Py_TRASHCAN_SAFE_END(so)
566}
567
568static int
569set_tp_print(PySetObject *so, FILE *fp, int flags)
570{
571 setentry *entry;
Martin v. Löwis18e16552006-02-15 17:27:45 +0000572 Py_ssize_t pos=0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000573 char *emit = ""; /* No separator emitted on first pass */
574 char *separator = ", ";
Georg Brandlc4996ba2006-08-28 19:37:11 +0000575 int literalform = 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000576
Georg Brandlc4996ba2006-08-28 19:37:11 +0000577 if (!so->used) {
578 fprintf(fp, "%s()", so->ob_type->tp_name);
579 return 0;
580 }
581
582 if (so->ob_type == &PySet_Type) {
583 literalform = 1;
Guido van Rossum86e58e22006-08-28 15:27:34 +0000584 fprintf(fp, "{");
Georg Brandlc4996ba2006-08-28 19:37:11 +0000585 } else
Guido van Rossum86e58e22006-08-28 15:27:34 +0000586 fprintf(fp, "%s([", so->ob_type->tp_name);
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000587 while (set_next(so, &pos, &entry)) {
588 fputs(emit, fp);
589 emit = separator;
590 if (PyObject_Print(entry->key, fp, 0) != 0)
591 return -1;
592 }
Georg Brandlc4996ba2006-08-28 19:37:11 +0000593 if (literalform)
Guido van Rossum86e58e22006-08-28 15:27:34 +0000594 fputs("}", fp);
595 else
596 fputs("])", fp);
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000597 return 0;
598}
599
600static PyObject *
601set_repr(PySetObject *so)
602{
603 PyObject *keys, *result, *listrepr;
604
Georg Brandlc4996ba2006-08-28 19:37:11 +0000605 /* shortcut for the empty set */
606 if (!so->used)
607 return PyString_FromFormat("%s()", so->ob_type->tp_name);
608
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000609 keys = PySequence_List((PyObject *)so);
610 if (keys == NULL)
611 return NULL;
612 listrepr = PyObject_Repr(keys);
613 Py_DECREF(keys);
614 if (listrepr == NULL)
615 return NULL;
616
Guido van Rossum86e58e22006-08-28 15:27:34 +0000617 if (so->ob_type == &PySet_Type) {
618 char *s = PyString_AS_STRING(listrepr);
619 s += 1;
620 s[strlen(s)-1] = 0;
621 result = PyString_FromFormat("{%s}", s);
622 } else {
623 result = PyString_FromFormat("%s(%s)", so->ob_type->tp_name,
Georg Brandlc4996ba2006-08-28 19:37:11 +0000624 PyString_AS_STRING(listrepr));
Guido van Rossum86e58e22006-08-28 15:27:34 +0000625 }
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000626 Py_DECREF(listrepr);
627 return result;
628}
629
Martin v. Löwis18e16552006-02-15 17:27:45 +0000630static Py_ssize_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000631set_len(PyObject *so)
632{
633 return ((PySetObject *)so)->used;
634}
635
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000636static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000637set_merge(PySetObject *so, PyObject *otherset)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000638{
Raymond Hettingerd7946662005-08-01 21:39:29 +0000639 PySetObject *other;
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000640 register Py_ssize_t i;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000641 register setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000642
643 assert (PyAnySet_Check(so));
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000644 assert (PyAnySet_Check(otherset));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000645
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000646 other = (PySetObject*)otherset;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000647 if (other == so || other->used == 0)
648 /* a.update(a) or a.update({}); nothing to do */
649 return 0;
650 /* Do one big resize at the start, rather than
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000651 * incrementally resizing as we insert new keys. Expect
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000652 * that there will be no (or few) overlapping keys.
653 */
654 if ((so->fill + other->used)*3 >= (so->mask+1)*2) {
655 if (set_table_resize(so, (so->used + other->used)*2) != 0)
656 return -1;
657 }
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000658 for (i = 0; i <= other->mask; i++) {
659 entry = &other->table[i];
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000660 if (entry->key != NULL &&
661 entry->key != dummy) {
662 Py_INCREF(entry->key);
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000663 if (set_insert_key(so, entry->key, entry->hash) == -1) {
664 Py_DECREF(entry->key);
665 return -1;
666 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000667 }
668 }
669 return 0;
670}
671
672static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000673set_contains_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000674{
675 long hash;
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000676 setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000677
678 if (!PyString_CheckExact(key) ||
679 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
680 hash = PyObject_Hash(key);
681 if (hash == -1)
682 return -1;
683 }
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000684 entry = (so->lookup)(so, key, hash);
685 if (entry == NULL)
686 return -1;
687 key = entry->key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000688 return key != NULL && key != dummy;
689}
690
Raymond Hettingerc991db22005-08-11 07:58:45 +0000691static int
692set_contains_entry(PySetObject *so, setentry *entry)
693{
694 PyObject *key;
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000695 setentry *lu_entry;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000696
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000697 lu_entry = (so->lookup)(so, entry->key, entry->hash);
698 if (lu_entry == NULL)
699 return -1;
700 key = lu_entry->key;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000701 return key != NULL && key != dummy;
702}
703
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000704static PyObject *
705set_pop(PySetObject *so)
706{
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000707 register Py_ssize_t i = 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000708 register setentry *entry;
709 PyObject *key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000710
711 assert (PyAnySet_Check(so));
712 if (so->used == 0) {
713 PyErr_SetString(PyExc_KeyError, "pop from an empty set");
714 return NULL;
715 }
716
717 /* Set entry to "the first" unused or dummy set entry. We abuse
718 * the hash field of slot 0 to hold a search finger:
719 * If slot 0 has a value, use slot 0.
720 * Else slot 0 is being used to hold a search finger,
721 * and we use its hash value as the first index to look.
722 */
723 entry = &so->table[0];
724 if (entry->key == NULL || entry->key == dummy) {
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000725 i = entry->hash;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000726 /* The hash field may be a real hash value, or it may be a
727 * legit search finger, or it may be a once-legit search
728 * finger that's out of bounds now because it wrapped around
729 * or the table shrunk -- simply make sure it's in bounds now.
730 */
731 if (i > so->mask || i < 1)
732 i = 1; /* skip slot 0 */
733 while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
734 i++;
735 if (i > so->mask)
736 i = 1;
737 }
738 }
739 key = entry->key;
740 Py_INCREF(dummy);
741 entry->key = dummy;
742 so->used--;
743 so->table[0].hash = i + 1; /* next place to start */
744 return key;
745}
746
747PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.");
748
749static int
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000750set_traverse(PySetObject *so, visitproc visit, void *arg)
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000751{
Martin v. Löwis18e16552006-02-15 17:27:45 +0000752 Py_ssize_t pos = 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000753 setentry *entry;
754
755 while (set_next(so, &pos, &entry))
756 Py_VISIT(entry->key);
757 return 0;
758}
759
760static long
761frozenset_hash(PyObject *self)
762{
763 PySetObject *so = (PySetObject *)self;
764 long h, hash = 1927868237L;
765 setentry *entry;
Martin v. Löwis18e16552006-02-15 17:27:45 +0000766 Py_ssize_t pos = 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000767
768 if (so->hash != -1)
769 return so->hash;
770
771 hash *= PySet_GET_SIZE(self) + 1;
772 while (set_next(so, &pos, &entry)) {
773 /* Work to increase the bit dispersion for closely spaced hash
774 values. The is important because some use cases have many
775 combinations of a small number of elements with nearby
776 hashes so that many distinct combinations collapse to only
777 a handful of distinct hash values. */
778 h = entry->hash;
779 hash ^= (h ^ (h << 16) ^ 89869747L) * 3644798167u;
780 }
781 hash = hash * 69069L + 907133923L;
782 if (hash == -1)
783 hash = 590923713L;
784 so->hash = hash;
785 return hash;
786}
787
Raymond Hettingera9d99362005-08-05 00:01:15 +0000788/***** Set iterator type ***********************************************/
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000789
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000790typedef struct {
791 PyObject_HEAD
792 PySetObject *si_set; /* Set to NULL when iterator is exhausted */
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000793 Py_ssize_t si_used;
794 Py_ssize_t si_pos;
795 Py_ssize_t len;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000796} setiterobject;
797
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000798static void
799setiter_dealloc(setiterobject *si)
800{
801 Py_XDECREF(si->si_set);
802 PyObject_Del(si);
803}
804
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000805static PyObject *
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000806setiter_len(setiterobject *si)
807{
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000808 Py_ssize_t len = 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000809 if (si->si_set != NULL && si->si_used == si->si_set->used)
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000810 len = si->len;
811 return PyInt_FromLong(len);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000812}
813
Armin Rigof5b3e362006-02-11 21:32:43 +0000814PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000815
816static PyMethodDef setiter_methods[] = {
Armin Rigof5b3e362006-02-11 21:32:43 +0000817 {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000818 {NULL, NULL} /* sentinel */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000819};
820
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000821static PyObject *setiter_iternext(setiterobject *si)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000822{
823 PyObject *key;
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000824 register Py_ssize_t i, mask;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000825 register setentry *entry;
826 PySetObject *so = si->si_set;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000827
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000828 if (so == NULL)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000829 return NULL;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000830 assert (PyAnySet_Check(so));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000831
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000832 if (si->si_used != so->used) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000833 PyErr_SetString(PyExc_RuntimeError,
834 "Set changed size during iteration");
835 si->si_used = -1; /* Make this state sticky */
836 return NULL;
837 }
838
839 i = si->si_pos;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000840 assert(i>=0);
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000841 entry = so->table;
842 mask = so->mask;
843 while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000844 i++;
845 si->si_pos = i+1;
846 if (i > mask)
847 goto fail;
848 si->len--;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000849 key = entry[i].key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000850 Py_INCREF(key);
851 return key;
852
853fail:
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000854 Py_DECREF(so);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000855 si->si_set = NULL;
856 return NULL;
857}
858
Hye-Shik Change2956762005-08-01 05:26:41 +0000859static PyTypeObject PySetIter_Type = {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000860 PyObject_HEAD_INIT(&PyType_Type)
861 0, /* ob_size */
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000862 "setiterator", /* tp_name */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000863 sizeof(setiterobject), /* tp_basicsize */
864 0, /* tp_itemsize */
865 /* methods */
866 (destructor)setiter_dealloc, /* tp_dealloc */
867 0, /* tp_print */
868 0, /* tp_getattr */
869 0, /* tp_setattr */
870 0, /* tp_compare */
871 0, /* tp_repr */
872 0, /* tp_as_number */
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000873 0, /* tp_as_sequence */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000874 0, /* tp_as_mapping */
875 0, /* tp_hash */
876 0, /* tp_call */
877 0, /* tp_str */
878 PyObject_GenericGetAttr, /* tp_getattro */
879 0, /* tp_setattro */
880 0, /* tp_as_buffer */
881 Py_TPFLAGS_DEFAULT, /* tp_flags */
882 0, /* tp_doc */
883 0, /* tp_traverse */
884 0, /* tp_clear */
885 0, /* tp_richcompare */
886 0, /* tp_weaklistoffset */
887 PyObject_SelfIter, /* tp_iter */
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000888 (iternextfunc)setiter_iternext, /* tp_iternext */
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000889 setiter_methods, /* tp_methods */
890 0,
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000891};
892
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000893static PyObject *
894set_iter(PySetObject *so)
895{
896 setiterobject *si = PyObject_New(setiterobject, &PySetIter_Type);
897 if (si == NULL)
898 return NULL;
899 Py_INCREF(so);
900 si->si_set = so;
901 si->si_used = so->used;
902 si->si_pos = 0;
903 si->len = so->used;
904 return (PyObject *)si;
905}
906
Raymond Hettingerd7946662005-08-01 21:39:29 +0000907static int
Raymond Hettingerd7946662005-08-01 21:39:29 +0000908set_update_internal(PySetObject *so, PyObject *other)
Raymond Hettingera690a992003-11-16 16:17:49 +0000909{
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000910 PyObject *key, *it;
Raymond Hettingera690a992003-11-16 16:17:49 +0000911
Raymond Hettingerd7946662005-08-01 21:39:29 +0000912 if (PyAnySet_Check(other))
Raymond Hettingerc991db22005-08-11 07:58:45 +0000913 return set_merge(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +0000914
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000915 if (PyDict_Check(other)) {
Neal Norwitz0c6e2f12006-01-08 06:13:44 +0000916 PyObject *value;
Martin v. Löwis18e16552006-02-15 17:27:45 +0000917 Py_ssize_t pos = 0;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000918 while (PyDict_Next(other, &pos, &key, &value)) {
Raymond Hettingerc991db22005-08-11 07:58:45 +0000919 if (set_add_key(so, key) == -1)
Raymond Hettingerd7946662005-08-01 21:39:29 +0000920 return -1;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000921 }
Raymond Hettingerd7946662005-08-01 21:39:29 +0000922 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000923 }
924
Raymond Hettingera38123e2003-11-24 22:18:49 +0000925 it = PyObject_GetIter(other);
926 if (it == NULL)
Raymond Hettingerd7946662005-08-01 21:39:29 +0000927 return -1;
Raymond Hettingera690a992003-11-16 16:17:49 +0000928
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000929 while ((key = PyIter_Next(it)) != NULL) {
Raymond Hettingerc991db22005-08-11 07:58:45 +0000930 if (set_add_key(so, key) == -1) {
Raymond Hettingera38123e2003-11-24 22:18:49 +0000931 Py_DECREF(it);
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000932 Py_DECREF(key);
Raymond Hettingerd7946662005-08-01 21:39:29 +0000933 return -1;
Raymond Hettingera690a992003-11-16 16:17:49 +0000934 }
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000935 Py_DECREF(key);
Raymond Hettingera690a992003-11-16 16:17:49 +0000936 }
Raymond Hettingera38123e2003-11-24 22:18:49 +0000937 Py_DECREF(it);
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +0000938 if (PyErr_Occurred())
Raymond Hettingerd7946662005-08-01 21:39:29 +0000939 return -1;
940 return 0;
941}
942
943static PyObject *
944set_update(PySetObject *so, PyObject *other)
945{
946 if (set_update_internal(so, other) == -1)
Raymond Hettingera38123e2003-11-24 22:18:49 +0000947 return NULL;
948 Py_RETURN_NONE;
949}
950
951PyDoc_STRVAR(update_doc,
952"Update a set with the union of itself and another.");
953
954static PyObject *
955make_new_set(PyTypeObject *type, PyObject *iterable)
956{
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000957 register PySetObject *so = NULL;
Raymond Hettingera38123e2003-11-24 22:18:49 +0000958
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000959 if (dummy == NULL) { /* Auto-initialize dummy */
960 dummy = PyString_FromString("<dummy key>");
961 if (dummy == NULL)
962 return NULL;
963 }
Raymond Hettingera690a992003-11-16 16:17:49 +0000964
965 /* create PySetObject structure */
Raymond Hettingerbc841a12005-08-07 13:02:53 +0000966 if (num_free_sets &&
967 (type == &PySet_Type || type == &PyFrozenSet_Type)) {
968 so = free_sets[--num_free_sets];
969 assert (so != NULL && PyAnySet_CheckExact(so));
970 so->ob_type = type;
971 _Py_NewReference((PyObject *)so);
972 EMPTY_TO_MINSIZE(so);
973 PyObject_GC_Track(so);
974 } else {
975 so = (PySetObject *)type->tp_alloc(type, 0);
976 if (so == NULL)
977 return NULL;
978 /* tp_alloc has already zeroed the structure */
979 assert(so->table == NULL && so->fill == 0 && so->used == 0);
980 INIT_NONZERO_SET_SLOTS(so);
981 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000982
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000983 so->lookup = set_lookkey_string;
Raymond Hettinger691d8052004-05-30 07:26:47 +0000984 so->weakreflist = NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +0000985
Raymond Hettingera38123e2003-11-24 22:18:49 +0000986 if (iterable != NULL) {
Raymond Hettingerd7946662005-08-01 21:39:29 +0000987 if (set_update_internal(so, iterable) == -1) {
Raymond Hettingera38123e2003-11-24 22:18:49 +0000988 Py_DECREF(so);
989 return NULL;
990 }
Raymond Hettingera38123e2003-11-24 22:18:49 +0000991 }
992
Raymond Hettingera690a992003-11-16 16:17:49 +0000993 return (PyObject *)so;
994}
995
Raymond Hettingerd7946662005-08-01 21:39:29 +0000996/* The empty frozenset is a singleton */
997static PyObject *emptyfrozenset = NULL;
998
Raymond Hettingera690a992003-11-16 16:17:49 +0000999static PyObject *
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001000frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
Raymond Hettingera690a992003-11-16 16:17:49 +00001001{
Raymond Hettingerd7946662005-08-01 21:39:29 +00001002 PyObject *iterable = NULL, *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001003
Georg Brandl02c42872005-08-26 06:42:30 +00001004 if (!_PyArg_NoKeywords("frozenset()", kwds))
1005 return NULL;
1006
Raymond Hettingera690a992003-11-16 16:17:49 +00001007 if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
1008 return NULL;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001009
1010 if (type != &PyFrozenSet_Type)
1011 return make_new_set(type, iterable);
1012
1013 if (iterable != NULL) {
1014 /* frozenset(f) is idempotent */
1015 if (PyFrozenSet_CheckExact(iterable)) {
1016 Py_INCREF(iterable);
1017 return iterable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001018 }
Raymond Hettingerd7946662005-08-01 21:39:29 +00001019 result = make_new_set(type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00001020 if (result == NULL || PySet_GET_SIZE(result))
Raymond Hettingerd7946662005-08-01 21:39:29 +00001021 return result;
1022 Py_DECREF(result);
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001023 }
Raymond Hettingerd7946662005-08-01 21:39:29 +00001024 /* The empty frozenset is a singleton */
1025 if (emptyfrozenset == NULL)
1026 emptyfrozenset = make_new_set(type, NULL);
1027 Py_XINCREF(emptyfrozenset);
1028 return emptyfrozenset;
1029}
1030
1031void
1032PySet_Fini(void)
1033{
Raymond Hettingerbc841a12005-08-07 13:02:53 +00001034 PySetObject *so;
1035
1036 while (num_free_sets) {
1037 num_free_sets--;
1038 so = free_sets[num_free_sets];
1039 PyObject_GC_Del(so);
1040 }
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001041 Py_CLEAR(dummy);
1042 Py_CLEAR(emptyfrozenset);
Raymond Hettingera690a992003-11-16 16:17:49 +00001043}
1044
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001045static PyObject *
1046set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1047{
Georg Brandl02c42872005-08-26 06:42:30 +00001048 if (!_PyArg_NoKeywords("set()", kwds))
1049 return NULL;
1050
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001051 return make_new_set(type, NULL);
1052}
1053
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001054/* set_swap_bodies() switches the contents of any two sets by moving their
1055 internal data pointers and, if needed, copying the internal smalltables.
1056 Semantically equivalent to:
1057
1058 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1059
1060 The function always succeeds and it leaves both objects in a stable state.
1061 Useful for creating temporary frozensets from sets for membership testing
1062 in __contains__(), discard(), and remove(). Also useful for operations
1063 that update in-place (by allowing an intermediate result to be swapped
Raymond Hettinger9dcb17c2005-07-31 13:09:28 +00001064 into one of the original inputs).
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001065*/
1066
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001067static void
1068set_swap_bodies(PySetObject *a, PySetObject *b)
Raymond Hettingera690a992003-11-16 16:17:49 +00001069{
Thomas Wouters0e3f5912006-08-11 14:57:12 +00001070 Py_ssize_t t;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001071 setentry *u;
1072 setentry *(*f)(PySetObject *so, PyObject *key, long hash);
1073 setentry tab[PySet_MINSIZE];
1074 long h;
1075
1076 t = a->fill; a->fill = b->fill; b->fill = t;
1077 t = a->used; a->used = b->used; b->used = t;
1078 t = a->mask; a->mask = b->mask; b->mask = t;
1079
1080 u = a->table;
1081 if (a->table == a->smalltable)
1082 u = b->smalltable;
1083 a->table = b->table;
1084 if (b->table == b->smalltable)
1085 a->table = a->smalltable;
1086 b->table = u;
1087
1088 f = a->lookup; a->lookup = b->lookup; b->lookup = f;
1089
1090 if (a->table == a->smalltable || b->table == b->smalltable) {
1091 memcpy(tab, a->smalltable, sizeof(tab));
1092 memcpy(a->smalltable, b->smalltable, sizeof(tab));
1093 memcpy(b->smalltable, tab, sizeof(tab));
1094 }
1095
Raymond Hettingera580c472005-08-05 17:19:54 +00001096 if (PyType_IsSubtype(a->ob_type, &PyFrozenSet_Type) &&
1097 PyType_IsSubtype(b->ob_type, &PyFrozenSet_Type)) {
1098 h = a->hash; a->hash = b->hash; b->hash = h;
1099 } else {
1100 a->hash = -1;
1101 b->hash = -1;
1102 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001103}
1104
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001105static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001106set_copy(PySetObject *so)
1107{
Raymond Hettingera38123e2003-11-24 22:18:49 +00001108 return make_new_set(so->ob_type, (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001109}
1110
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001111static PyObject *
1112frozenset_copy(PySetObject *so)
1113{
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001114 if (PyFrozenSet_CheckExact(so)) {
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001115 Py_INCREF(so);
1116 return (PyObject *)so;
1117 }
1118 return set_copy(so);
1119}
1120
Raymond Hettingera690a992003-11-16 16:17:49 +00001121PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
1122
1123static PyObject *
Raymond Hettingerc991db22005-08-11 07:58:45 +00001124set_clear(PySetObject *so)
1125{
1126 set_clear_internal(so);
1127 Py_RETURN_NONE;
1128}
1129
1130PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
1131
1132static PyObject *
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001133set_union(PySetObject *so, PyObject *other)
1134{
1135 PySetObject *result;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001136
1137 result = (PySetObject *)set_copy(so);
1138 if (result == NULL)
1139 return NULL;
Raymond Hettingerd8e13382005-08-17 12:27:17 +00001140 if ((PyObject *)so == other)
1141 return (PyObject *)result;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001142 if (set_update_internal(result, other) == -1) {
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001143 Py_DECREF(result);
1144 return NULL;
1145 }
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001146 return (PyObject *)result;
1147}
1148
1149PyDoc_STRVAR(union_doc,
1150 "Return the union of two sets as a new set.\n\
1151\n\
1152(i.e. all elements that are in either set.)");
1153
1154static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001155set_or(PySetObject *so, PyObject *other)
1156{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001157 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001158 Py_INCREF(Py_NotImplemented);
1159 return Py_NotImplemented;
1160 }
1161 return set_union(so, other);
1162}
1163
1164static PyObject *
1165set_ior(PySetObject *so, PyObject *other)
1166{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001167 if (!PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001168 Py_INCREF(Py_NotImplemented);
1169 return Py_NotImplemented;
1170 }
Raymond Hettingerd7946662005-08-01 21:39:29 +00001171 if (set_update_internal(so, other) == -1)
Raymond Hettingera690a992003-11-16 16:17:49 +00001172 return NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001173 Py_INCREF(so);
1174 return (PyObject *)so;
1175}
1176
1177static PyObject *
1178set_intersection(PySetObject *so, PyObject *other)
1179{
1180 PySetObject *result;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001181 PyObject *key, *it, *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001182
Raymond Hettingerd8e13382005-08-17 12:27:17 +00001183 if ((PyObject *)so == other)
1184 return set_copy(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001185
Raymond Hettingera690a992003-11-16 16:17:49 +00001186 result = (PySetObject *)make_new_set(so->ob_type, NULL);
1187 if (result == NULL)
1188 return NULL;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001189
Raymond Hettingerc991db22005-08-11 07:58:45 +00001190 if (PyAnySet_Check(other)) {
Martin v. Löwis18e16552006-02-15 17:27:45 +00001191 Py_ssize_t pos = 0;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001192 setentry *entry;
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001193
Raymond Hettingerbeb31012005-08-16 03:47:52 +00001194 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001195 tmp = (PyObject *)so;
1196 so = (PySetObject *)other;
1197 other = tmp;
1198 }
1199
Raymond Hettingerc991db22005-08-11 07:58:45 +00001200 while (set_next((PySetObject *)other, &pos, &entry)) {
Thomas Wouters89f507f2006-12-13 04:49:30 +00001201 int rv = set_contains_entry(so, entry);
1202 if (rv == -1) {
1203 Py_DECREF(result);
1204 return NULL;
1205 }
1206 if (rv) {
Raymond Hettingerc991db22005-08-11 07:58:45 +00001207 if (set_add_entry(result, entry) == -1) {
Raymond Hettingera3b11e72003-12-31 14:08:58 +00001208 Py_DECREF(result);
1209 return NULL;
1210 }
1211 }
1212 }
1213 return (PyObject *)result;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001214 }
1215
Raymond Hettingera690a992003-11-16 16:17:49 +00001216 it = PyObject_GetIter(other);
1217 if (it == NULL) {
1218 Py_DECREF(result);
1219 return NULL;
1220 }
1221
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001222 while ((key = PyIter_Next(it)) != NULL) {
Thomas Wouters89f507f2006-12-13 04:49:30 +00001223 int rv;
1224 setentry entry;
1225 long hash = PyObject_Hash(key);
1226
1227 if (hash == -1) {
1228 Py_DECREF(it);
1229 Py_DECREF(result);
1230 Py_DECREF(key);
1231 return NULL;
1232 }
1233 entry.hash = hash;
1234 entry.key = key;
1235 rv = set_contains_entry(so, &entry);
1236 if (rv == -1) {
1237 Py_DECREF(it);
1238 Py_DECREF(result);
1239 Py_DECREF(key);
1240 return NULL;
1241 }
1242 if (rv) {
1243 if (set_add_entry(result, &entry) == -1) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001244 Py_DECREF(it);
1245 Py_DECREF(result);
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001246 Py_DECREF(key);
Raymond Hettingera690a992003-11-16 16:17:49 +00001247 return NULL;
1248 }
1249 }
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001250 Py_DECREF(key);
Raymond Hettingera690a992003-11-16 16:17:49 +00001251 }
1252 Py_DECREF(it);
1253 if (PyErr_Occurred()) {
1254 Py_DECREF(result);
1255 return NULL;
1256 }
1257 return (PyObject *)result;
1258}
1259
1260PyDoc_STRVAR(intersection_doc,
1261"Return the intersection of two sets as a new set.\n\
1262\n\
1263(i.e. all elements that are in both sets.)");
1264
1265static PyObject *
1266set_intersection_update(PySetObject *so, PyObject *other)
1267{
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001268 PyObject *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001269
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001270 tmp = set_intersection(so, other);
1271 if (tmp == NULL)
Raymond Hettingera690a992003-11-16 16:17:49 +00001272 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001273 set_swap_bodies(so, (PySetObject *)tmp);
Raymond Hettingera690a992003-11-16 16:17:49 +00001274 Py_DECREF(tmp);
1275 Py_RETURN_NONE;
1276}
1277
1278PyDoc_STRVAR(intersection_update_doc,
1279"Update a set with the intersection of itself and another.");
1280
1281static PyObject *
1282set_and(PySetObject *so, PyObject *other)
1283{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001284 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001285 Py_INCREF(Py_NotImplemented);
1286 return Py_NotImplemented;
1287 }
1288 return set_intersection(so, other);
1289}
1290
1291static PyObject *
1292set_iand(PySetObject *so, PyObject *other)
1293{
1294 PyObject *result;
1295
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001296 if (!PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001297 Py_INCREF(Py_NotImplemented);
1298 return Py_NotImplemented;
1299 }
1300 result = set_intersection_update(so, other);
1301 if (result == NULL)
1302 return NULL;
1303 Py_DECREF(result);
1304 Py_INCREF(so);
1305 return (PyObject *)so;
1306}
1307
Neal Norwitz6576bd82005-11-13 18:41:28 +00001308static int
Raymond Hettingerc991db22005-08-11 07:58:45 +00001309set_difference_update_internal(PySetObject *so, PyObject *other)
1310{
1311 if ((PyObject *)so == other)
1312 return set_clear_internal(so);
1313
1314 if (PyAnySet_Check(other)) {
1315 setentry *entry;
Martin v. Löwis18e16552006-02-15 17:27:45 +00001316 Py_ssize_t pos = 0;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001317
1318 while (set_next((PySetObject *)other, &pos, &entry))
Thomas Wouters89f507f2006-12-13 04:49:30 +00001319 if (set_discard_entry(so, entry) == -1)
1320 return -1;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001321 } else {
1322 PyObject *key, *it;
1323 it = PyObject_GetIter(other);
1324 if (it == NULL)
1325 return -1;
1326
1327 while ((key = PyIter_Next(it)) != NULL) {
1328 if (set_discard_key(so, key) == -1) {
1329 Py_DECREF(it);
1330 Py_DECREF(key);
1331 return -1;
1332 }
1333 Py_DECREF(key);
1334 }
1335 Py_DECREF(it);
1336 if (PyErr_Occurred())
1337 return -1;
1338 }
1339 /* If more than 1/5 are dummies, then resize them away. */
1340 if ((so->fill - so->used) * 5 < so->mask)
1341 return 0;
1342 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
1343}
1344
Raymond Hettingera690a992003-11-16 16:17:49 +00001345static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001346set_difference_update(PySetObject *so, PyObject *other)
1347{
Raymond Hettingerc991db22005-08-11 07:58:45 +00001348 if (set_difference_update_internal(so, other) != -1)
Raymond Hettingerbc841a12005-08-07 13:02:53 +00001349 Py_RETURN_NONE;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001350 return NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001351}
1352
1353PyDoc_STRVAR(difference_update_doc,
1354"Remove all elements of another set from this set.");
1355
1356static PyObject *
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001357set_difference(PySetObject *so, PyObject *other)
1358{
Raymond Hettingerc991db22005-08-11 07:58:45 +00001359 PyObject *result;
1360 setentry *entry;
Martin v. Löwis18e16552006-02-15 17:27:45 +00001361 Py_ssize_t pos = 0;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001362
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001363 if (!PyAnySet_Check(other) && !PyDict_Check(other)) {
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001364 result = set_copy(so);
1365 if (result == NULL)
Raymond Hettingerc991db22005-08-11 07:58:45 +00001366 return NULL;
1367 if (set_difference_update_internal((PySetObject *)result, other) != -1)
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001368 return result;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001369 Py_DECREF(result);
1370 return NULL;
1371 }
1372
1373 result = make_new_set(so->ob_type, NULL);
1374 if (result == NULL)
1375 return NULL;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001376
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001377 if (PyDict_Check(other)) {
Raymond Hettingerc991db22005-08-11 07:58:45 +00001378 while (set_next(so, &pos, &entry)) {
1379 setentry entrycopy;
1380 entrycopy.hash = entry->hash;
1381 entrycopy.key = entry->key;
1382 if (!PyDict_Contains(other, entry->key)) {
Thomas Wouters89f507f2006-12-13 04:49:30 +00001383 if (set_add_entry((PySetObject *)result, &entrycopy) == -1) {
1384 Py_DECREF(result);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001385 return NULL;
Thomas Wouters89f507f2006-12-13 04:49:30 +00001386 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001387 }
1388 }
1389 return result;
1390 }
1391
Raymond Hettingerc991db22005-08-11 07:58:45 +00001392 while (set_next(so, &pos, &entry)) {
Thomas Wouters89f507f2006-12-13 04:49:30 +00001393 int rv = set_contains_entry((PySetObject *)other, entry);
1394 if (rv == -1) {
1395 Py_DECREF(result);
1396 return NULL;
1397 }
1398 if (!rv) {
1399 if (set_add_entry((PySetObject *)result, entry) == -1) {
1400 Py_DECREF(result);
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001401 return NULL;
Thomas Wouters89f507f2006-12-13 04:49:30 +00001402 }
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001403 }
1404 }
1405 return result;
1406}
1407
1408PyDoc_STRVAR(difference_doc,
1409"Return the difference of two sets as a new set.\n\
1410\n\
1411(i.e. all elements that are in this set but not the other.)");
1412static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001413set_sub(PySetObject *so, PyObject *other)
1414{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001415 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001416 Py_INCREF(Py_NotImplemented);
1417 return Py_NotImplemented;
1418 }
1419 return set_difference(so, other);
1420}
1421
1422static PyObject *
1423set_isub(PySetObject *so, PyObject *other)
1424{
1425 PyObject *result;
1426
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001427 if (!PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001428 Py_INCREF(Py_NotImplemented);
1429 return Py_NotImplemented;
1430 }
1431 result = set_difference_update(so, other);
1432 if (result == NULL)
1433 return NULL;
1434 Py_DECREF(result);
1435 Py_INCREF(so);
1436 return (PyObject *)so;
1437}
1438
1439static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001440set_symmetric_difference_update(PySetObject *so, PyObject *other)
1441{
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001442 PySetObject *otherset;
1443 PyObject *key;
Martin v. Löwis18e16552006-02-15 17:27:45 +00001444 Py_ssize_t pos = 0;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001445 setentry *entry;
1446
1447 if ((PyObject *)so == other)
1448 return set_clear(so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001449
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001450 if (PyDict_Check(other)) {
1451 PyObject *value;
1452 int rv;
1453 while (PyDict_Next(other, &pos, &key, &value)) {
Thomas Wouters89f507f2006-12-13 04:49:30 +00001454 setentry an_entry;
1455 long hash = PyObject_Hash(key);
1456
1457 if (hash == -1)
1458 return NULL;
1459 an_entry.hash = hash;
1460 an_entry.key = key;
1461 rv = set_discard_entry(so, &an_entry);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001462 if (rv == -1)
1463 return NULL;
1464 if (rv == DISCARD_NOTFOUND) {
Thomas Wouters89f507f2006-12-13 04:49:30 +00001465 if (set_add_entry(so, &an_entry) == -1)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001466 return NULL;
1467 }
1468 }
1469 Py_RETURN_NONE;
1470 }
1471
1472 if (PyAnySet_Check(other)) {
1473 Py_INCREF(other);
1474 otherset = (PySetObject *)other;
1475 } else {
Raymond Hettingera690a992003-11-16 16:17:49 +00001476 otherset = (PySetObject *)make_new_set(so->ob_type, other);
1477 if (otherset == NULL)
1478 return NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001479 }
1480
Raymond Hettingerc991db22005-08-11 07:58:45 +00001481 while (set_next(otherset, &pos, &entry)) {
1482 int rv = set_discard_entry(so, entry);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001483 if (rv == -1) {
Thomas Wouters0e3f5912006-08-11 14:57:12 +00001484 Py_DECREF(otherset);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001485 return NULL;
1486 }
1487 if (rv == DISCARD_NOTFOUND) {
Raymond Hettingerc991db22005-08-11 07:58:45 +00001488 if (set_add_entry(so, entry) == -1) {
Thomas Wouters0e3f5912006-08-11 14:57:12 +00001489 Py_DECREF(otherset);
Raymond Hettingera690a992003-11-16 16:17:49 +00001490 return NULL;
1491 }
1492 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001493 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001494 Py_DECREF(otherset);
Raymond Hettingera690a992003-11-16 16:17:49 +00001495 Py_RETURN_NONE;
1496}
1497
1498PyDoc_STRVAR(symmetric_difference_update_doc,
1499"Update a set with the symmetric difference of itself and another.");
1500
1501static PyObject *
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001502set_symmetric_difference(PySetObject *so, PyObject *other)
1503{
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001504 PyObject *rv;
1505 PySetObject *otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001506
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001507 otherset = (PySetObject *)make_new_set(so->ob_type, other);
1508 if (otherset == NULL)
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001509 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001510 rv = set_symmetric_difference_update(otherset, (PyObject *)so);
1511 if (rv == NULL)
1512 return NULL;
1513 Py_DECREF(rv);
1514 return (PyObject *)otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001515}
1516
1517PyDoc_STRVAR(symmetric_difference_doc,
1518"Return the symmetric difference of two sets as a new set.\n\
1519\n\
1520(i.e. all elements that are in exactly one of the sets.)");
1521
1522static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001523set_xor(PySetObject *so, PyObject *other)
1524{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001525 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001526 Py_INCREF(Py_NotImplemented);
1527 return Py_NotImplemented;
1528 }
1529 return set_symmetric_difference(so, other);
1530}
1531
1532static PyObject *
1533set_ixor(PySetObject *so, PyObject *other)
1534{
1535 PyObject *result;
1536
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001537 if (!PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001538 Py_INCREF(Py_NotImplemented);
1539 return Py_NotImplemented;
1540 }
1541 result = set_symmetric_difference_update(so, other);
1542 if (result == NULL)
1543 return NULL;
1544 Py_DECREF(result);
1545 Py_INCREF(so);
1546 return (PyObject *)so;
1547}
1548
1549static PyObject *
1550set_issubset(PySetObject *so, PyObject *other)
1551{
Raymond Hettingered6c1ef2005-08-13 08:28:03 +00001552 setentry *entry;
Martin v. Löwis18e16552006-02-15 17:27:45 +00001553 Py_ssize_t pos = 0;
Raymond Hettingera690a992003-11-16 16:17:49 +00001554
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001555 if (!PyAnySet_Check(other)) {
Raymond Hettingered6c1ef2005-08-13 08:28:03 +00001556 PyObject *tmp, *result;
Raymond Hettinger3fbec702003-11-21 07:56:36 +00001557 tmp = make_new_set(&PySet_Type, other);
1558 if (tmp == NULL)
1559 return NULL;
1560 result = set_issubset(so, tmp);
1561 Py_DECREF(tmp);
1562 return result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001563 }
Raymond Hettingerbeb31012005-08-16 03:47:52 +00001564 if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
Raymond Hettingera690a992003-11-16 16:17:49 +00001565 Py_RETURN_FALSE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001566
Raymond Hettingered6c1ef2005-08-13 08:28:03 +00001567 while (set_next(so, &pos, &entry)) {
Thomas Wouters89f507f2006-12-13 04:49:30 +00001568 int rv = set_contains_entry((PySetObject *)other, entry);
1569 if (rv == -1)
1570 return NULL;
1571 if (!rv)
Raymond Hettingera690a992003-11-16 16:17:49 +00001572 Py_RETURN_FALSE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001573 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001574 Py_RETURN_TRUE;
1575}
1576
1577PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
1578
1579static PyObject *
1580set_issuperset(PySetObject *so, PyObject *other)
1581{
Raymond Hettinger3fbec702003-11-21 07:56:36 +00001582 PyObject *tmp, *result;
1583
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001584 if (!PyAnySet_Check(other)) {
Raymond Hettinger3fbec702003-11-21 07:56:36 +00001585 tmp = make_new_set(&PySet_Type, other);
1586 if (tmp == NULL)
1587 return NULL;
1588 result = set_issuperset(so, tmp);
1589 Py_DECREF(tmp);
1590 return result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001591 }
1592 return set_issubset((PySetObject *)other, (PyObject *)so);
1593}
1594
1595PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
1596
Raymond Hettingera690a992003-11-16 16:17:49 +00001597static PyObject *
1598set_richcompare(PySetObject *v, PyObject *w, int op)
1599{
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001600 PyObject *r1, *r2;
1601
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001602 if(!PyAnySet_Check(w)) {
1603 if (op == Py_EQ)
1604 Py_RETURN_FALSE;
1605 if (op == Py_NE)
1606 Py_RETURN_TRUE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001607 PyErr_SetString(PyExc_TypeError, "can only compare to a set");
1608 return NULL;
1609 }
1610 switch (op) {
1611 case Py_EQ:
Raymond Hettingerbeb31012005-08-16 03:47:52 +00001612 if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
Raymond Hettingera690a992003-11-16 16:17:49 +00001613 Py_RETURN_FALSE;
Raymond Hettinger9c1491f2005-08-24 00:24:40 +00001614 if (v->hash != -1 &&
1615 ((PySetObject *)w)->hash != -1 &&
1616 v->hash != ((PySetObject *)w)->hash)
1617 Py_RETURN_FALSE;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001618 return set_issubset(v, w);
1619 case Py_NE:
Raymond Hettinger9c1491f2005-08-24 00:24:40 +00001620 r1 = set_richcompare(v, w, Py_EQ);
1621 if (r1 == NULL)
1622 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001623 r2 = PyBool_FromLong(PyObject_Not(r1));
1624 Py_DECREF(r1);
1625 return r2;
1626 case Py_LE:
1627 return set_issubset(v, w);
1628 case Py_GE:
1629 return set_issuperset(v, w);
1630 case Py_LT:
Raymond Hettingerbeb31012005-08-16 03:47:52 +00001631 if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001632 Py_RETURN_FALSE;
1633 return set_issubset(v, w);
1634 case Py_GT:
Raymond Hettingerbeb31012005-08-16 03:47:52 +00001635 if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001636 Py_RETURN_FALSE;
1637 return set_issuperset(v, w);
Raymond Hettingera690a992003-11-16 16:17:49 +00001638 }
1639 Py_INCREF(Py_NotImplemented);
1640 return Py_NotImplemented;
1641}
1642
Raymond Hettingered6c1ef2005-08-13 08:28:03 +00001643static int
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001644set_nocmp(PyObject *self, PyObject *other)
Raymond Hettingered6c1ef2005-08-13 08:28:03 +00001645{
1646 PyErr_SetString(PyExc_TypeError, "cannot compare sets using cmp()");
1647 return -1;
1648}
1649
Raymond Hettingera690a992003-11-16 16:17:49 +00001650static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001651set_add(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001652{
Raymond Hettingerc991db22005-08-11 07:58:45 +00001653 if (set_add_key(so, key) == -1)
Raymond Hettingera690a992003-11-16 16:17:49 +00001654 return NULL;
Raymond Hettinger438e02d2003-12-13 19:38:47 +00001655 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001656}
1657
1658PyDoc_STRVAR(add_doc,
1659"Add an element to a set.\n\
1660\n\
1661This has no effect if the element is already present.");
1662
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001663static int
1664set_contains(PySetObject *so, PyObject *key)
1665{
1666 PyObject *tmpkey;
1667 int rv;
1668
1669 rv = set_contains_key(so, key);
1670 if (rv == -1) {
1671 if (!PyAnySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1672 return -1;
1673 PyErr_Clear();
1674 tmpkey = make_new_set(&PyFrozenSet_Type, NULL);
1675 if (tmpkey == NULL)
1676 return -1;
1677 set_swap_bodies((PySetObject *)tmpkey, (PySetObject *)key);
1678 rv = set_contains(so, tmpkey);
1679 set_swap_bodies((PySetObject *)tmpkey, (PySetObject *)key);
1680 Py_DECREF(tmpkey);
1681 }
1682 return rv;
1683}
1684
1685static PyObject *
1686set_direct_contains(PySetObject *so, PyObject *key)
1687{
1688 long result;
1689
1690 result = set_contains(so, key);
1691 if (result == -1)
1692 return NULL;
1693 return PyBool_FromLong(result);
1694}
1695
1696PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
1697
Raymond Hettingera690a992003-11-16 16:17:49 +00001698static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001699set_remove(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001700{
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001701 PyObject *tmpkey, *result;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001702 int rv;
Raymond Hettingerbfd334a2003-11-22 03:55:23 +00001703
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001704 rv = set_discard_key(so, key);
1705 if (rv == -1) {
1706 if (!PyAnySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1707 return NULL;
1708 PyErr_Clear();
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001709 tmpkey = make_new_set(&PyFrozenSet_Type, NULL);
1710 if (tmpkey == NULL)
Raymond Hettingerbfd334a2003-11-22 03:55:23 +00001711 return NULL;
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001712 set_swap_bodies((PySetObject *)tmpkey, (PySetObject *)key);
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001713 result = set_remove(so, tmpkey);
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001714 set_swap_bodies((PySetObject *)tmpkey, (PySetObject *)key);
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001715 Py_DECREF(tmpkey);
Raymond Hettinger0deab622003-12-13 18:53:18 +00001716 return result;
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001717 } else if (rv == DISCARD_NOTFOUND) {
Thomas Wouters89f507f2006-12-13 04:49:30 +00001718 set_key_error(key);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001719 return NULL;
1720 }
Raymond Hettinger438e02d2003-12-13 19:38:47 +00001721 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001722}
1723
1724PyDoc_STRVAR(remove_doc,
1725"Remove an element from a set; it must be a member.\n\
1726\n\
1727If the element is not a member, raise a KeyError.");
1728
1729static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001730set_discard(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001731{
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001732 PyObject *tmpkey, *result;
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001733 int rv;
Raymond Hettinger0deab622003-12-13 18:53:18 +00001734
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001735 rv = set_discard_key(so, key);
1736 if (rv == -1) {
1737 if (!PyAnySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1738 return NULL;
1739 PyErr_Clear();
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001740 tmpkey = make_new_set(&PyFrozenSet_Type, NULL);
1741 if (tmpkey == NULL)
Raymond Hettinger0deab622003-12-13 18:53:18 +00001742 return NULL;
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001743 set_swap_bodies((PySetObject *)tmpkey, (PySetObject *)key);
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001744 result = set_discard(so, tmpkey);
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001745 set_swap_bodies((PySetObject *)tmpkey, (PySetObject *)key);
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001746 Py_DECREF(tmpkey);
Raymond Hettinger0deab622003-12-13 18:53:18 +00001747 return result;
1748 }
Raymond Hettinger438e02d2003-12-13 19:38:47 +00001749 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001750}
1751
1752PyDoc_STRVAR(discard_doc,
1753"Remove an element from a set if it is a member.\n\
1754\n\
1755If the element is not a member, do nothing.");
1756
1757static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001758set_reduce(PySetObject *so)
1759{
Raymond Hettinger15056a52004-11-09 07:25:31 +00001760 PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001761
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001762 keys = PySequence_List((PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001763 if (keys == NULL)
1764 goto done;
1765 args = PyTuple_Pack(1, keys);
1766 if (args == NULL)
1767 goto done;
Raymond Hettinger15056a52004-11-09 07:25:31 +00001768 dict = PyObject_GetAttrString((PyObject *)so, "__dict__");
1769 if (dict == NULL) {
1770 PyErr_Clear();
1771 dict = Py_None;
1772 Py_INCREF(dict);
1773 }
1774 result = PyTuple_Pack(3, so->ob_type, args, dict);
Raymond Hettingera690a992003-11-16 16:17:49 +00001775done:
1776 Py_XDECREF(args);
1777 Py_XDECREF(keys);
Raymond Hettinger15056a52004-11-09 07:25:31 +00001778 Py_XDECREF(dict);
Raymond Hettingera690a992003-11-16 16:17:49 +00001779 return result;
1780}
1781
1782PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1783
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001784static int
1785set_init(PySetObject *self, PyObject *args, PyObject *kwds)
1786{
1787 PyObject *iterable = NULL;
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001788
1789 if (!PyAnySet_Check(self))
1790 return -1;
1791 if (!PyArg_UnpackTuple(args, self->ob_type->tp_name, 0, 1, &iterable))
1792 return -1;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001793 set_clear_internal(self);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001794 self->hash = -1;
1795 if (iterable == NULL)
1796 return 0;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001797 return set_update_internal(self, iterable);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001798}
1799
Raymond Hettingera690a992003-11-16 16:17:49 +00001800static PySequenceMethods set_as_sequence = {
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001801 set_len, /* sq_length */
Raymond Hettingera690a992003-11-16 16:17:49 +00001802 0, /* sq_concat */
1803 0, /* sq_repeat */
1804 0, /* sq_item */
1805 0, /* sq_slice */
1806 0, /* sq_ass_item */
1807 0, /* sq_ass_slice */
1808 (objobjproc)set_contains, /* sq_contains */
1809};
1810
1811/* set object ********************************************************/
1812
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00001813#ifdef Py_DEBUG
1814static PyObject *test_c_api(PySetObject *so);
1815
1816PyDoc_STRVAR(test_c_api_doc, "Exercises C API. Returns True.\n\
1817All is well if assertions don't fail.");
1818#endif
1819
Raymond Hettingera690a992003-11-16 16:17:49 +00001820static PyMethodDef set_methods[] = {
1821 {"add", (PyCFunction)set_add, METH_O,
1822 add_doc},
1823 {"clear", (PyCFunction)set_clear, METH_NOARGS,
1824 clear_doc},
Raymond Hettinger0deab622003-12-13 18:53:18 +00001825 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001826 contains_doc},
Raymond Hettingera690a992003-11-16 16:17:49 +00001827 {"copy", (PyCFunction)set_copy, METH_NOARGS,
1828 copy_doc},
Raymond Hettingera690a992003-11-16 16:17:49 +00001829 {"discard", (PyCFunction)set_discard, METH_O,
1830 discard_doc},
1831 {"difference", (PyCFunction)set_difference, METH_O,
1832 difference_doc},
1833 {"difference_update", (PyCFunction)set_difference_update, METH_O,
1834 difference_update_doc},
1835 {"intersection",(PyCFunction)set_intersection, METH_O,
1836 intersection_doc},
1837 {"intersection_update",(PyCFunction)set_intersection_update, METH_O,
1838 intersection_update_doc},
1839 {"issubset", (PyCFunction)set_issubset, METH_O,
1840 issubset_doc},
1841 {"issuperset", (PyCFunction)set_issuperset, METH_O,
1842 issuperset_doc},
1843 {"pop", (PyCFunction)set_pop, METH_NOARGS,
1844 pop_doc},
1845 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
1846 reduce_doc},
1847 {"remove", (PyCFunction)set_remove, METH_O,
1848 remove_doc},
1849 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
1850 symmetric_difference_doc},
1851 {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O,
1852 symmetric_difference_update_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00001853#ifdef Py_DEBUG
1854 {"test_c_api", (PyCFunction)test_c_api, METH_NOARGS,
1855 test_c_api_doc},
1856#endif
Raymond Hettingera690a992003-11-16 16:17:49 +00001857 {"union", (PyCFunction)set_union, METH_O,
1858 union_doc},
Raymond Hettingera38123e2003-11-24 22:18:49 +00001859 {"update", (PyCFunction)set_update, METH_O,
1860 update_doc},
Raymond Hettingera690a992003-11-16 16:17:49 +00001861 {NULL, NULL} /* sentinel */
1862};
1863
1864static PyNumberMethods set_as_number = {
1865 0, /*nb_add*/
1866 (binaryfunc)set_sub, /*nb_subtract*/
1867 0, /*nb_multiply*/
Raymond Hettingera690a992003-11-16 16:17:49 +00001868 0, /*nb_remainder*/
1869 0, /*nb_divmod*/
1870 0, /*nb_power*/
1871 0, /*nb_negative*/
1872 0, /*nb_positive*/
1873 0, /*nb_absolute*/
Jack Diederich4dafcc42006-11-28 19:15:13 +00001874 0, /*nb_bool*/
Raymond Hettingera690a992003-11-16 16:17:49 +00001875 0, /*nb_invert*/
1876 0, /*nb_lshift*/
1877 0, /*nb_rshift*/
1878 (binaryfunc)set_and, /*nb_and*/
1879 (binaryfunc)set_xor, /*nb_xor*/
1880 (binaryfunc)set_or, /*nb_or*/
1881 0, /*nb_coerce*/
1882 0, /*nb_int*/
1883 0, /*nb_long*/
1884 0, /*nb_float*/
1885 0, /*nb_oct*/
1886 0, /*nb_hex*/
1887 0, /*nb_inplace_add*/
1888 (binaryfunc)set_isub, /*nb_inplace_subtract*/
1889 0, /*nb_inplace_multiply*/
Raymond Hettingera690a992003-11-16 16:17:49 +00001890 0, /*nb_inplace_remainder*/
1891 0, /*nb_inplace_power*/
1892 0, /*nb_inplace_lshift*/
1893 0, /*nb_inplace_rshift*/
1894 (binaryfunc)set_iand, /*nb_inplace_and*/
1895 (binaryfunc)set_ixor, /*nb_inplace_xor*/
1896 (binaryfunc)set_ior, /*nb_inplace_or*/
1897};
1898
1899PyDoc_STRVAR(set_doc,
1900"set(iterable) --> set object\n\
1901\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00001902Build an unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00001903
1904PyTypeObject PySet_Type = {
1905 PyObject_HEAD_INIT(&PyType_Type)
1906 0, /* ob_size */
1907 "set", /* tp_name */
1908 sizeof(PySetObject), /* tp_basicsize */
1909 0, /* tp_itemsize */
1910 /* methods */
1911 (destructor)set_dealloc, /* tp_dealloc */
1912 (printfunc)set_tp_print, /* tp_print */
1913 0, /* tp_getattr */
1914 0, /* tp_setattr */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001915 set_nocmp, /* tp_compare */
Raymond Hettingera690a992003-11-16 16:17:49 +00001916 (reprfunc)set_repr, /* tp_repr */
1917 &set_as_number, /* tp_as_number */
1918 &set_as_sequence, /* tp_as_sequence */
1919 0, /* tp_as_mapping */
Guido van Rossum50e9fb92006-08-17 05:42:55 +00001920 0, /* tp_hash */
Raymond Hettingera690a992003-11-16 16:17:49 +00001921 0, /* tp_call */
1922 0, /* tp_str */
1923 PyObject_GenericGetAttr, /* tp_getattro */
1924 0, /* tp_setattro */
1925 0, /* tp_as_buffer */
Guido van Rossum3cf5b1e2006-07-27 21:53:35 +00001926 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001927 Py_TPFLAGS_BASETYPE, /* tp_flags */
Raymond Hettingera690a992003-11-16 16:17:49 +00001928 set_doc, /* tp_doc */
Raymond Hettingerbb999b52005-06-18 21:00:26 +00001929 (traverseproc)set_traverse, /* tp_traverse */
Raymond Hettingerfe889f32005-08-06 05:43:39 +00001930 (inquiry)set_clear_internal, /* tp_clear */
Raymond Hettingera690a992003-11-16 16:17:49 +00001931 (richcmpfunc)set_richcompare, /* tp_richcompare */
Raymond Hettinger691d8052004-05-30 07:26:47 +00001932 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001933 (getiterfunc)set_iter, /* tp_iter */
Raymond Hettingera690a992003-11-16 16:17:49 +00001934 0, /* tp_iternext */
1935 set_methods, /* tp_methods */
1936 0, /* tp_members */
1937 0, /* tp_getset */
1938 0, /* tp_base */
1939 0, /* tp_dict */
1940 0, /* tp_descr_get */
1941 0, /* tp_descr_set */
1942 0, /* tp_dictoffset */
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001943 (initproc)set_init, /* tp_init */
Raymond Hettingera690a992003-11-16 16:17:49 +00001944 PyType_GenericAlloc, /* tp_alloc */
1945 set_new, /* tp_new */
Raymond Hettingerbb999b52005-06-18 21:00:26 +00001946 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00001947};
1948
1949/* frozenset object ********************************************************/
1950
1951
1952static PyMethodDef frozenset_methods[] = {
Raymond Hettinger0deab622003-12-13 18:53:18 +00001953 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001954 contains_doc},
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001955 {"copy", (PyCFunction)frozenset_copy, METH_NOARGS,
Raymond Hettingera690a992003-11-16 16:17:49 +00001956 copy_doc},
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001957 {"difference", (PyCFunction)set_difference, METH_O,
Raymond Hettingera690a992003-11-16 16:17:49 +00001958 difference_doc},
1959 {"intersection",(PyCFunction)set_intersection, METH_O,
1960 intersection_doc},
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001961 {"issubset", (PyCFunction)set_issubset, METH_O,
Raymond Hettingera690a992003-11-16 16:17:49 +00001962 issubset_doc},
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001963 {"issuperset", (PyCFunction)set_issuperset, METH_O,
Raymond Hettingera690a992003-11-16 16:17:49 +00001964 issuperset_doc},
1965 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
1966 reduce_doc},
1967 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
1968 symmetric_difference_doc},
1969 {"union", (PyCFunction)set_union, METH_O,
1970 union_doc},
1971 {NULL, NULL} /* sentinel */
1972};
1973
1974static PyNumberMethods frozenset_as_number = {
1975 0, /*nb_add*/
1976 (binaryfunc)set_sub, /*nb_subtract*/
1977 0, /*nb_multiply*/
Raymond Hettingera690a992003-11-16 16:17:49 +00001978 0, /*nb_remainder*/
1979 0, /*nb_divmod*/
1980 0, /*nb_power*/
1981 0, /*nb_negative*/
1982 0, /*nb_positive*/
1983 0, /*nb_absolute*/
Jack Diederich4dafcc42006-11-28 19:15:13 +00001984 0, /*nb_bool*/
Raymond Hettingera690a992003-11-16 16:17:49 +00001985 0, /*nb_invert*/
1986 0, /*nb_lshift*/
1987 0, /*nb_rshift*/
1988 (binaryfunc)set_and, /*nb_and*/
1989 (binaryfunc)set_xor, /*nb_xor*/
1990 (binaryfunc)set_or, /*nb_or*/
1991};
1992
1993PyDoc_STRVAR(frozenset_doc,
1994"frozenset(iterable) --> frozenset object\n\
1995\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00001996Build an immutable unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00001997
1998PyTypeObject PyFrozenSet_Type = {
1999 PyObject_HEAD_INIT(&PyType_Type)
2000 0, /* ob_size */
2001 "frozenset", /* tp_name */
2002 sizeof(PySetObject), /* tp_basicsize */
Raymond Hettingera3b11e72003-12-31 14:08:58 +00002003 0, /* tp_itemsize */
2004 /* methods */
Raymond Hettingera690a992003-11-16 16:17:49 +00002005 (destructor)set_dealloc, /* tp_dealloc */
2006 (printfunc)set_tp_print, /* tp_print */
2007 0, /* tp_getattr */
2008 0, /* tp_setattr */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002009 set_nocmp, /* tp_compare */
Raymond Hettingera690a992003-11-16 16:17:49 +00002010 (reprfunc)set_repr, /* tp_repr */
2011 &frozenset_as_number, /* tp_as_number */
2012 &set_as_sequence, /* tp_as_sequence */
2013 0, /* tp_as_mapping */
2014 frozenset_hash, /* tp_hash */
2015 0, /* tp_call */
2016 0, /* tp_str */
2017 PyObject_GenericGetAttr, /* tp_getattro */
2018 0, /* tp_setattro */
2019 0, /* tp_as_buffer */
Guido van Rossum3cf5b1e2006-07-27 21:53:35 +00002020 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00002021 Py_TPFLAGS_BASETYPE, /* tp_flags */
Raymond Hettingera690a992003-11-16 16:17:49 +00002022 frozenset_doc, /* tp_doc */
Raymond Hettingerbb999b52005-06-18 21:00:26 +00002023 (traverseproc)set_traverse, /* tp_traverse */
Raymond Hettingerfe889f32005-08-06 05:43:39 +00002024 (inquiry)set_clear_internal, /* tp_clear */
Raymond Hettingera690a992003-11-16 16:17:49 +00002025 (richcmpfunc)set_richcompare, /* tp_richcompare */
Raymond Hettinger691d8052004-05-30 07:26:47 +00002026 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
Raymond Hettingera690a992003-11-16 16:17:49 +00002027 (getiterfunc)set_iter, /* tp_iter */
2028 0, /* tp_iternext */
2029 frozenset_methods, /* tp_methods */
2030 0, /* tp_members */
2031 0, /* tp_getset */
2032 0, /* tp_base */
2033 0, /* tp_dict */
2034 0, /* tp_descr_get */
2035 0, /* tp_descr_set */
2036 0, /* tp_dictoffset */
2037 0, /* tp_init */
2038 PyType_GenericAlloc, /* tp_alloc */
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00002039 frozenset_new, /* tp_new */
Raymond Hettingerbb999b52005-06-18 21:00:26 +00002040 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002041};
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002042
2043
2044/***** C API functions *************************************************/
2045
2046PyObject *
2047PySet_New(PyObject *iterable)
2048{
2049 return make_new_set(&PySet_Type, iterable);
2050}
2051
2052PyObject *
2053PyFrozenSet_New(PyObject *iterable)
2054{
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002055 PyObject *args, *result;
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002056
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002057 if (iterable == NULL)
2058 args = PyTuple_New(0);
2059 else
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002060 args = PyTuple_Pack(1, iterable);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002061 if (args == NULL)
2062 return NULL;
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002063 result = frozenset_new(&PyFrozenSet_Type, args, NULL);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002064 Py_DECREF(args);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002065 return result;
2066}
2067
Neal Norwitz8c49c822006-03-04 18:41:19 +00002068Py_ssize_t
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002069PySet_Size(PyObject *anyset)
2070{
2071 if (!PyAnySet_Check(anyset)) {
2072 PyErr_BadInternalCall();
2073 return -1;
2074 }
Raymond Hettinger9c1491f2005-08-24 00:24:40 +00002075 return PySet_GET_SIZE(anyset);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002076}
2077
2078int
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002079PySet_Clear(PyObject *set)
2080{
2081 if (!PyType_IsSubtype(set->ob_type, &PySet_Type)) {
2082 PyErr_BadInternalCall();
2083 return -1;
2084 }
2085 return set_clear_internal((PySetObject *)set);
2086}
2087
2088int
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002089PySet_Contains(PyObject *anyset, PyObject *key)
2090{
2091 if (!PyAnySet_Check(anyset)) {
2092 PyErr_BadInternalCall();
2093 return -1;
2094 }
2095 return set_contains_key((PySetObject *)anyset, key);
2096}
2097
2098int
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002099PySet_Discard(PyObject *set, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002100{
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002101 if (!PyType_IsSubtype(set->ob_type, &PySet_Type)) {
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002102 PyErr_BadInternalCall();
2103 return -1;
2104 }
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002105 return set_discard_key((PySetObject *)set, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002106}
2107
2108int
2109PySet_Add(PyObject *set, PyObject *key)
2110{
2111 if (!PyType_IsSubtype(set->ob_type, &PySet_Type)) {
2112 PyErr_BadInternalCall();
2113 return -1;
2114 }
2115 return set_add_key((PySetObject *)set, key);
2116}
2117
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002118int
2119_PySet_Next(PyObject *set, Py_ssize_t *pos, PyObject **entry)
2120{
2121 setentry *entry_ptr;
2122
2123 if (!PyAnySet_Check(set)) {
2124 PyErr_BadInternalCall();
2125 return -1;
2126 }
2127 if (set_next((PySetObject *)set, pos, &entry_ptr) == 0)
2128 return 0;
2129 *entry = entry_ptr->key;
2130 return 1;
2131}
2132
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002133PyObject *
2134PySet_Pop(PyObject *set)
2135{
2136 if (!PyType_IsSubtype(set->ob_type, &PySet_Type)) {
2137 PyErr_BadInternalCall();
2138 return NULL;
2139 }
2140 return set_pop((PySetObject *)set);
2141}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002142
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002143int
2144_PySet_Update(PyObject *set, PyObject *iterable)
2145{
2146 if (!PyType_IsSubtype(set->ob_type, &PySet_Type)) {
2147 PyErr_BadInternalCall();
2148 return -1;
2149 }
2150 return set_update_internal((PySetObject *)set, iterable);
2151}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002152
2153#ifdef Py_DEBUG
2154
2155/* Test code to be called with any three element set.
2156 Returns True and original set is restored. */
2157
2158#define assertRaises(call_return_value, exception) \
2159 do { \
2160 assert(call_return_value); \
2161 assert(PyErr_ExceptionMatches(exception)); \
2162 PyErr_Clear(); \
2163 } while(0)
2164
2165static PyObject *
2166test_c_api(PySetObject *so)
2167{
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002168 Py_ssize_t count;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002169 char *s;
2170 Py_ssize_t i;
2171 PyObject *elem, *dup, *t, *f, *dup2;
2172 PyObject *ob = (PyObject *)so;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002173
2174 /* Verify preconditions and exercise type/size checks */
2175 assert(PyAnySet_Check(ob));
2176 assert(PyAnySet_CheckExact(ob));
2177 assert(!PyFrozenSet_CheckExact(ob));
2178 assert(PySet_Size(ob) == 3);
2179 assert(PySet_GET_SIZE(ob) == 3);
2180
2181 /* Raise TypeError for non-iterable constructor arguments */
2182 assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
2183 assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);
2184
2185 /* Raise TypeError for unhashable key */
2186 dup = PySet_New(ob);
2187 assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
2188 assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
2189 assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);
2190
2191 /* Exercise successful pop, contains, add, and discard */
2192 elem = PySet_Pop(ob);
2193 assert(PySet_Contains(ob, elem) == 0);
2194 assert(PySet_GET_SIZE(ob) == 2);
2195 assert(PySet_Add(ob, elem) == 0);
2196 assert(PySet_Contains(ob, elem) == 1);
2197 assert(PySet_GET_SIZE(ob) == 3);
2198 assert(PySet_Discard(ob, elem) == 1);
2199 assert(PySet_GET_SIZE(ob) == 2);
2200 assert(PySet_Discard(ob, elem) == 0);
2201 assert(PySet_GET_SIZE(ob) == 2);
2202
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002203 /* Exercise clear */
2204 dup2 = PySet_New(dup);
2205 assert(PySet_Clear(dup2) == 0);
2206 assert(PySet_Size(dup2) == 0);
2207 Py_DECREF(dup2);
2208
2209 /* Raise SystemError on clear or update of frozen set */
2210 f = PyFrozenSet_New(dup);
2211 assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
2212 assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
2213 Py_DECREF(f);
2214
2215 /* Exercise direct iteration */
2216 i = 0, count = 0;
2217 while (_PySet_Next((PyObject *)dup, &i, &elem)) {
2218 s = PyString_AsString(elem);
2219 assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
2220 count++;
2221 }
2222 assert(count == 3);
2223
2224 /* Exercise updates */
2225 dup2 = PySet_New(NULL);
2226 assert(_PySet_Update(dup2, dup) == 0);
2227 assert(PySet_Size(dup2) == 3);
2228 assert(_PySet_Update(dup2, dup) == 0);
2229 assert(PySet_Size(dup2) == 3);
2230 Py_DECREF(dup2);
2231
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002232 /* Raise SystemError when self argument is not a set or frozenset. */
2233 t = PyTuple_New(0);
2234 assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
2235 assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
2236 Py_DECREF(t);
2237
2238 /* Raise SystemError when self argument is not a set. */
2239 f = PyFrozenSet_New(dup);
2240 assert(PySet_Size(f) == 3);
2241 assert(PyFrozenSet_CheckExact(f));
2242 assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
2243 assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
2244 assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
2245 Py_DECREF(f);
2246
2247 /* Raise KeyError when popping from an empty set */
Raymond Hettingerd8e13382005-08-17 12:27:17 +00002248 assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
2249 Py_DECREF(ob);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002250 assert(PySet_GET_SIZE(ob) == 0);
2251 assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);
2252
Raymond Hettingerd8e13382005-08-17 12:27:17 +00002253 /* Restore the set from the copy using the PyNumber API */
2254 assert(PyNumber_InPlaceOr(ob, dup) == ob);
2255 Py_DECREF(ob);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002256
2257 /* Verify constructors accept NULL arguments */
2258 f = PySet_New(NULL);
2259 assert(f != NULL);
2260 assert(PySet_GET_SIZE(f) == 0);
2261 Py_DECREF(f);
2262 f = PyFrozenSet_New(NULL);
2263 assert(f != NULL);
2264 assert(PyFrozenSet_CheckExact(f));
2265 assert(PySet_GET_SIZE(f) == 0);
2266 Py_DECREF(f);
2267
2268 Py_DECREF(elem);
2269 Py_DECREF(dup);
2270 Py_RETURN_TRUE;
2271}
2272
Raymond Hettinger9bda1d62005-09-16 07:14:21 +00002273#undef assertRaises
2274
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002275#endif