Merged revisions 83951 via svnmerge from
[python/dscho.git] / Objects / setobject.c
blobe7966bb28bb5d8105f17cb22f96506d5916dfb66
2 /* set object implementation
3 Written and maintained by Raymond D. Hettinger <python@rcn.com>
4 Derived from Lib/sets.py and Objects/dictobject.c.
6 Copyright (c) 2003-2008 Python Software Foundation.
7 All rights reserved.
8 */
10 #include "Python.h"
11 #include "structmember.h"
12 #include "stringlib/eq.h"
14 /* Set a key error with the specified argument, wrapping it in a
15 * tuple automatically so that tuple keys are not unpacked as the
16 * exception arguments. */
17 static void
18 set_key_error(PyObject *arg)
20 PyObject *tup;
21 tup = PyTuple_Pack(1, arg);
22 if (!tup)
23 return; /* caller will expect error to be set anyway */
24 PyErr_SetObject(PyExc_KeyError, tup);
25 Py_DECREF(tup);
28 /* This must be >= 1. */
29 #define PERTURB_SHIFT 5
31 /* Object used as dummy key to fill deleted entries */
32 static PyObject *dummy = NULL; /* Initialized by first call to make_new_set() */
34 #ifdef Py_REF_DEBUG
35 PyObject *
36 _PySet_Dummy(void)
38 return dummy;
40 #endif
42 #define INIT_NONZERO_SET_SLOTS(so) do { \
43 (so)->table = (so)->smalltable; \
44 (so)->mask = PySet_MINSIZE - 1; \
45 (so)->hash = -1; \
46 } while(0)
48 #define EMPTY_TO_MINSIZE(so) do { \
49 memset((so)->smalltable, 0, sizeof((so)->smalltable)); \
50 (so)->used = (so)->fill = 0; \
51 INIT_NONZERO_SET_SLOTS(so); \
52 } while(0)
54 /* Reuse scheme to save calls to malloc, free, and memset */
55 #ifndef PySet_MAXFREELIST
56 #define PySet_MAXFREELIST 80
57 #endif
58 static PySetObject *free_list[PySet_MAXFREELIST];
59 static int numfree = 0;
63 The basic lookup function used by all operations.
64 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
65 Open addressing is preferred over chaining since the link overhead for
66 chaining would be substantial (100% with typical malloc overhead).
68 The initial probe index is computed as hash mod the table size. Subsequent
69 probe indices are computed as explained in Objects/dictobject.c.
71 All arithmetic on hash should ignore overflow.
73 Unlike the dictionary implementation, the lookkey functions can return
74 NULL if the rich comparison returns an error.
77 static setentry *
78 set_lookkey(PySetObject *so, PyObject *key, register long hash)
80 register Py_ssize_t i;
81 register size_t perturb;
82 register setentry *freeslot;
83 register size_t mask = so->mask;
84 setentry *table = so->table;
85 register setentry *entry;
86 register int cmp;
87 PyObject *startkey;
89 i = hash & mask;
90 entry = &table[i];
91 if (entry->key == NULL || entry->key == key)
92 return entry;
94 if (entry->key == dummy)
95 freeslot = entry;
96 else {
97 if (entry->hash == hash) {
98 startkey = entry->key;
99 Py_INCREF(startkey);
100 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
101 Py_DECREF(startkey);
102 if (cmp < 0)
103 return NULL;
104 if (table == so->table && entry->key == startkey) {
105 if (cmp > 0)
106 return entry;
108 else {
109 /* The compare did major nasty stuff to the
110 * set: start over.
112 return set_lookkey(so, key, hash);
115 freeslot = NULL;
118 /* In the loop, key == dummy is by far (factor of 100s) the
119 least likely outcome, so test for that last. */
120 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
121 i = (i << 2) + i + perturb + 1;
122 entry = &table[i & mask];
123 if (entry->key == NULL) {
124 if (freeslot != NULL)
125 entry = freeslot;
126 break;
128 if (entry->key == key)
129 break;
130 if (entry->hash == hash && entry->key != dummy) {
131 startkey = entry->key;
132 Py_INCREF(startkey);
133 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
134 Py_DECREF(startkey);
135 if (cmp < 0)
136 return NULL;
137 if (table == so->table && entry->key == startkey) {
138 if (cmp > 0)
139 break;
141 else {
142 /* The compare did major nasty stuff to the
143 * set: start over.
145 return set_lookkey(so, key, hash);
148 else if (entry->key == dummy && freeslot == NULL)
149 freeslot = entry;
151 return entry;
155 * Hacked up version of set_lookkey which can assume keys are always unicode;
156 * This means we can always use unicode_eq directly and not have to check to
157 * see if the comparison altered the table.
159 static setentry *
160 set_lookkey_unicode(PySetObject *so, PyObject *key, register long hash)
162 register Py_ssize_t i;
163 register size_t perturb;
164 register setentry *freeslot;
165 register size_t mask = so->mask;
166 setentry *table = so->table;
167 register setentry *entry;
169 /* Make sure this function doesn't have to handle non-unicode keys,
170 including subclasses of str; e.g., one reason to subclass
171 strings is to override __eq__, and for speed we don't cater to
172 that here. */
173 if (!PyUnicode_CheckExact(key)) {
174 so->lookup = set_lookkey;
175 return set_lookkey(so, key, hash);
177 i = hash & mask;
178 entry = &table[i];
179 if (entry->key == NULL || entry->key == key)
180 return entry;
181 if (entry->key == dummy)
182 freeslot = entry;
183 else {
184 if (entry->hash == hash && unicode_eq(entry->key, key))
185 return entry;
186 freeslot = NULL;
189 /* In the loop, key == dummy is by far (factor of 100s) the
190 least likely outcome, so test for that last. */
191 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
192 i = (i << 2) + i + perturb + 1;
193 entry = &table[i & mask];
194 if (entry->key == NULL)
195 return freeslot == NULL ? entry : freeslot;
196 if (entry->key == key
197 || (entry->hash == hash
198 && entry->key != dummy
199 && unicode_eq(entry->key, key)))
200 return entry;
201 if (entry->key == dummy && freeslot == NULL)
202 freeslot = entry;
204 assert(0); /* NOT REACHED */
205 return 0;
209 Internal routine to insert a new key into the table.
210 Used by the public insert routine.
211 Eats a reference to key.
213 static int
214 set_insert_key(register PySetObject *so, PyObject *key, long hash)
216 register setentry *entry;
217 typedef setentry *(*lookupfunc)(PySetObject *, PyObject *, long);
219 assert(so->lookup != NULL);
220 entry = so->lookup(so, key, hash);
221 if (entry == NULL)
222 return -1;
223 if (entry->key == NULL) {
224 /* UNUSED */
225 so->fill++;
226 entry->key = key;
227 entry->hash = hash;
228 so->used++;
229 } else if (entry->key == dummy) {
230 /* DUMMY */
231 entry->key = key;
232 entry->hash = hash;
233 so->used++;
234 Py_DECREF(dummy);
235 } else {
236 /* ACTIVE */
237 Py_DECREF(key);
239 return 0;
243 Internal routine used by set_table_resize() to insert an item which is
244 known to be absent from the set. This routine also assumes that
245 the set contains no deleted entries. Besides the performance benefit,
246 using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
247 Note that no refcounts are changed by this routine; if needed, the caller
248 is responsible for incref'ing `key`.
250 static void
251 set_insert_clean(register PySetObject *so, PyObject *key, long hash)
253 register size_t i;
254 register size_t perturb;
255 register size_t mask = (size_t)so->mask;
256 setentry *table = so->table;
257 register setentry *entry;
259 i = hash & mask;
260 entry = &table[i];
261 for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) {
262 i = (i << 2) + i + perturb + 1;
263 entry = &table[i & mask];
265 so->fill++;
266 entry->key = key;
267 entry->hash = hash;
268 so->used++;
272 Restructure the table by allocating a new table and reinserting all
273 keys again. When entries have been deleted, the new table may
274 actually be smaller than the old one.
276 static int
277 set_table_resize(PySetObject *so, Py_ssize_t minused)
279 Py_ssize_t newsize;
280 setentry *oldtable, *newtable, *entry;
281 Py_ssize_t i;
282 int is_oldtable_malloced;
283 setentry small_copy[PySet_MINSIZE];
285 assert(minused >= 0);
287 /* Find the smallest table size > minused. */
288 for (newsize = PySet_MINSIZE;
289 newsize <= minused && newsize > 0;
290 newsize <<= 1)
292 if (newsize <= 0) {
293 PyErr_NoMemory();
294 return -1;
297 /* Get space for a new table. */
298 oldtable = so->table;
299 assert(oldtable != NULL);
300 is_oldtable_malloced = oldtable != so->smalltable;
302 if (newsize == PySet_MINSIZE) {
303 /* A large table is shrinking, or we can't get any smaller. */
304 newtable = so->smalltable;
305 if (newtable == oldtable) {
306 if (so->fill == so->used) {
307 /* No dummies, so no point doing anything. */
308 return 0;
310 /* We're not going to resize it, but rebuild the
311 table anyway to purge old dummy entries.
312 Subtle: This is *necessary* if fill==size,
313 as set_lookkey needs at least one virgin slot to
314 terminate failing searches. If fill < size, it's
315 merely desirable, as dummies slow searches. */
316 assert(so->fill > so->used);
317 memcpy(small_copy, oldtable, sizeof(small_copy));
318 oldtable = small_copy;
321 else {
322 newtable = PyMem_NEW(setentry, newsize);
323 if (newtable == NULL) {
324 PyErr_NoMemory();
325 return -1;
329 /* Make the set empty, using the new table. */
330 assert(newtable != oldtable);
331 so->table = newtable;
332 so->mask = newsize - 1;
333 memset(newtable, 0, sizeof(setentry) * newsize);
334 so->used = 0;
335 i = so->fill;
336 so->fill = 0;
338 /* Copy the data over; this is refcount-neutral for active entries;
339 dummy entries aren't copied over, of course */
340 for (entry = oldtable; i > 0; entry++) {
341 if (entry->key == NULL) {
342 /* UNUSED */
344 } else if (entry->key == dummy) {
345 /* DUMMY */
346 --i;
347 assert(entry->key == dummy);
348 Py_DECREF(entry->key);
349 } else {
350 /* ACTIVE */
351 --i;
352 set_insert_clean(so, entry->key, entry->hash);
356 if (is_oldtable_malloced)
357 PyMem_DEL(oldtable);
358 return 0;
361 /* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
363 static int
364 set_add_entry(register PySetObject *so, setentry *entry)
366 register Py_ssize_t n_used;
368 assert(so->fill <= so->mask); /* at least one empty slot */
369 n_used = so->used;
370 Py_INCREF(entry->key);
371 if (set_insert_key(so, entry->key, entry->hash) == -1) {
372 Py_DECREF(entry->key);
373 return -1;
375 if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
376 return 0;
377 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
380 static int
381 set_add_key(register PySetObject *so, PyObject *key)
383 register long hash;
384 register Py_ssize_t n_used;
386 if (!PyUnicode_CheckExact(key) ||
387 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
388 hash = PyObject_Hash(key);
389 if (hash == -1)
390 return -1;
392 assert(so->fill <= so->mask); /* at least one empty slot */
393 n_used = so->used;
394 Py_INCREF(key);
395 if (set_insert_key(so, key, hash) == -1) {
396 Py_DECREF(key);
397 return -1;
399 if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
400 return 0;
401 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
404 #define DISCARD_NOTFOUND 0
405 #define DISCARD_FOUND 1
407 static int
408 set_discard_entry(PySetObject *so, setentry *oldentry)
409 { register setentry *entry;
410 PyObject *old_key;
412 entry = (so->lookup)(so, oldentry->key, oldentry->hash);
413 if (entry == NULL)
414 return -1;
415 if (entry->key == NULL || entry->key == dummy)
416 return DISCARD_NOTFOUND;
417 old_key = entry->key;
418 Py_INCREF(dummy);
419 entry->key = dummy;
420 so->used--;
421 Py_DECREF(old_key);
422 return DISCARD_FOUND;
425 static int
426 set_discard_key(PySetObject *so, PyObject *key)
428 register long hash;
429 register setentry *entry;
430 PyObject *old_key;
432 assert (PyAnySet_Check(so));
434 if (!PyUnicode_CheckExact(key) ||
435 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
436 hash = PyObject_Hash(key);
437 if (hash == -1)
438 return -1;
440 entry = (so->lookup)(so, key, hash);
441 if (entry == NULL)
442 return -1;
443 if (entry->key == NULL || entry->key == dummy)
444 return DISCARD_NOTFOUND;
445 old_key = entry->key;
446 Py_INCREF(dummy);
447 entry->key = dummy;
448 so->used--;
449 Py_DECREF(old_key);
450 return DISCARD_FOUND;
453 static int
454 set_clear_internal(PySetObject *so)
456 setentry *entry, *table;
457 int table_is_malloced;
458 Py_ssize_t fill;
459 setentry small_copy[PySet_MINSIZE];
460 #ifdef Py_DEBUG
461 Py_ssize_t i, n;
462 assert (PyAnySet_Check(so));
464 n = so->mask + 1;
465 i = 0;
466 #endif
468 table = so->table;
469 assert(table != NULL);
470 table_is_malloced = table != so->smalltable;
472 /* This is delicate. During the process of clearing the set,
473 * decrefs can cause the set to mutate. To avoid fatal confusion
474 * (voice of experience), we have to make the set empty before
475 * clearing the slots, and never refer to anything via so->ref while
476 * clearing.
478 fill = so->fill;
479 if (table_is_malloced)
480 EMPTY_TO_MINSIZE(so);
482 else if (fill > 0) {
483 /* It's a small table with something that needs to be cleared.
484 * Afraid the only safe way is to copy the set entries into
485 * another small table first.
487 memcpy(small_copy, table, sizeof(small_copy));
488 table = small_copy;
489 EMPTY_TO_MINSIZE(so);
491 /* else it's a small table that's already empty */
493 /* Now we can finally clear things. If C had refcounts, we could
494 * assert that the refcount on table is 1 now, i.e. that this function
495 * has unique access to it, so decref side-effects can't alter it.
497 for (entry = table; fill > 0; ++entry) {
498 #ifdef Py_DEBUG
499 assert(i < n);
500 ++i;
501 #endif
502 if (entry->key) {
503 --fill;
504 Py_DECREF(entry->key);
506 #ifdef Py_DEBUG
507 else
508 assert(entry->key == NULL);
509 #endif
512 if (table_is_malloced)
513 PyMem_DEL(table);
514 return 0;
518 * Iterate over a set table. Use like so:
520 * Py_ssize_t pos;
521 * setentry *entry;
522 * pos = 0; # important! pos should not otherwise be changed by you
523 * while (set_next(yourset, &pos, &entry)) {
524 * Refer to borrowed reference in entry->key.
527 * CAUTION: In general, it isn't safe to use set_next in a loop that
528 * mutates the table.
530 static int
531 set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)
533 Py_ssize_t i;
534 Py_ssize_t mask;
535 register setentry *table;
537 assert (PyAnySet_Check(so));
538 i = *pos_ptr;
539 assert(i >= 0);
540 table = so->table;
541 mask = so->mask;
542 while (i <= mask && (table[i].key == NULL || table[i].key == dummy))
543 i++;
544 *pos_ptr = i+1;
545 if (i > mask)
546 return 0;
547 assert(table[i].key != NULL);
548 *entry_ptr = &table[i];
549 return 1;
552 static void
553 set_dealloc(PySetObject *so)
555 register setentry *entry;
556 Py_ssize_t fill = so->fill;
557 PyObject_GC_UnTrack(so);
558 Py_TRASHCAN_SAFE_BEGIN(so)
559 if (so->weakreflist != NULL)
560 PyObject_ClearWeakRefs((PyObject *) so);
562 for (entry = so->table; fill > 0; entry++) {
563 if (entry->key) {
564 --fill;
565 Py_DECREF(entry->key);
568 if (so->table != so->smalltable)
569 PyMem_DEL(so->table);
570 if (numfree < PySet_MAXFREELIST && PyAnySet_CheckExact(so))
571 free_list[numfree++] = so;
572 else
573 Py_TYPE(so)->tp_free(so);
574 Py_TRASHCAN_SAFE_END(so)
577 static PyObject *
578 set_repr(PySetObject *so)
580 PyObject *keys, *result=NULL;
581 Py_UNICODE *u;
582 int status = Py_ReprEnter((PyObject*)so);
583 PyObject *listrepr;
584 Py_ssize_t newsize;
586 if (status != 0) {
587 if (status < 0)
588 return NULL;
589 return PyUnicode_FromFormat("%s(...)", Py_TYPE(so)->tp_name);
592 /* shortcut for the empty set */
593 if (!so->used) {
594 Py_ReprLeave((PyObject*)so);
595 return PyUnicode_FromFormat("%s()", Py_TYPE(so)->tp_name);
598 keys = PySequence_List((PyObject *)so);
599 if (keys == NULL)
600 goto done;
602 listrepr = PyObject_Repr(keys);
603 Py_DECREF(keys);
604 if (listrepr == NULL)
605 goto done;
606 newsize = PyUnicode_GET_SIZE(listrepr);
607 result = PyUnicode_FromUnicode(NULL, newsize);
608 if (result) {
609 u = PyUnicode_AS_UNICODE(result);
610 *u++ = '{';
611 /* Omit the brackets from the listrepr */
612 Py_UNICODE_COPY(u, PyUnicode_AS_UNICODE(listrepr)+1,
613 PyUnicode_GET_SIZE(listrepr)-2);
614 u += newsize-2;
615 *u++ = '}';
617 Py_DECREF(listrepr);
618 if (Py_TYPE(so) != &PySet_Type) {
619 PyObject *tmp = PyUnicode_FromFormat("%s(%U)",
620 Py_TYPE(so)->tp_name,
621 result);
622 Py_DECREF(result);
623 result = tmp;
625 done:
626 Py_ReprLeave((PyObject*)so);
627 return result;
630 static Py_ssize_t
631 set_len(PyObject *so)
633 return ((PySetObject *)so)->used;
636 static int
637 set_merge(PySetObject *so, PyObject *otherset)
639 PySetObject *other;
640 register Py_ssize_t i;
641 register setentry *entry;
643 assert (PyAnySet_Check(so));
644 assert (PyAnySet_Check(otherset));
646 other = (PySetObject*)otherset;
647 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
651 * incrementally resizing as we insert new keys. Expect
652 * that there will be no (or few) overlapping keys.
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;
658 for (i = 0; i <= other->mask; i++) {
659 entry = &other->table[i];
660 if (entry->key != NULL &&
661 entry->key != dummy) {
662 Py_INCREF(entry->key);
663 if (set_insert_key(so, entry->key, entry->hash) == -1) {
664 Py_DECREF(entry->key);
665 return -1;
669 return 0;
672 static int
673 set_contains_key(PySetObject *so, PyObject *key)
675 long hash;
676 setentry *entry;
678 if (!PyUnicode_CheckExact(key) ||
679 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
680 hash = PyObject_Hash(key);
681 if (hash == -1)
682 return -1;
684 entry = (so->lookup)(so, key, hash);
685 if (entry == NULL)
686 return -1;
687 key = entry->key;
688 return key != NULL && key != dummy;
691 static int
692 set_contains_entry(PySetObject *so, setentry *entry)
694 PyObject *key;
695 setentry *lu_entry;
697 lu_entry = (so->lookup)(so, entry->key, entry->hash);
698 if (lu_entry == NULL)
699 return -1;
700 key = lu_entry->key;
701 return key != NULL && key != dummy;
704 static PyObject *
705 set_pop(PySetObject *so)
707 register Py_ssize_t i = 0;
708 register setentry *entry;
709 PyObject *key;
711 assert (PyAnySet_Check(so));
712 if (so->used == 0) {
713 PyErr_SetString(PyExc_KeyError, "pop from an empty set");
714 return NULL;
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.
723 entry = &so->table[0];
724 if (entry->key == NULL || entry->key == dummy) {
725 i = entry->hash;
726 /* 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.
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;
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;
747 PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\
748 Raises KeyError if the set is empty.");
750 static int
751 set_traverse(PySetObject *so, visitproc visit, void *arg)
753 Py_ssize_t pos = 0;
754 setentry *entry;
756 while (set_next(so, &pos, &entry))
757 Py_VISIT(entry->key);
758 return 0;
761 static long
762 frozenset_hash(PyObject *self)
764 PySetObject *so = (PySetObject *)self;
765 long h, hash = 1927868237L;
766 setentry *entry;
767 Py_ssize_t pos = 0;
769 if (so->hash != -1)
770 return so->hash;
772 hash *= PySet_GET_SIZE(self) + 1;
773 while (set_next(so, &pos, &entry)) {
774 /* Work to increase the bit dispersion for closely spaced hash
775 values. The is important because some use cases have many
776 combinations of a small number of elements with nearby
777 hashes so that many distinct combinations collapse to only
778 a handful of distinct hash values. */
779 h = entry->hash;
780 hash ^= (h ^ (h << 16) ^ 89869747L) * 3644798167u;
782 hash = hash * 69069L + 907133923L;
783 if (hash == -1)
784 hash = 590923713L;
785 so->hash = hash;
786 return hash;
789 /***** Set iterator type ***********************************************/
791 typedef struct {
792 PyObject_HEAD
793 PySetObject *si_set; /* Set to NULL when iterator is exhausted */
794 Py_ssize_t si_used;
795 Py_ssize_t si_pos;
796 Py_ssize_t len;
797 } setiterobject;
799 static void
800 setiter_dealloc(setiterobject *si)
802 Py_XDECREF(si->si_set);
803 PyObject_GC_Del(si);
806 static int
807 setiter_traverse(setiterobject *si, visitproc visit, void *arg)
809 Py_VISIT(si->si_set);
810 return 0;
813 static PyObject *
814 setiter_len(setiterobject *si)
816 Py_ssize_t len = 0;
817 if (si->si_set != NULL && si->si_used == si->si_set->used)
818 len = si->len;
819 return PyLong_FromLong(len);
822 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
824 static PyMethodDef setiter_methods[] = {
825 {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
826 {NULL, NULL} /* sentinel */
829 static PyObject *setiter_iternext(setiterobject *si)
831 PyObject *key;
832 register Py_ssize_t i, mask;
833 register setentry *entry;
834 PySetObject *so = si->si_set;
836 if (so == NULL)
837 return NULL;
838 assert (PyAnySet_Check(so));
840 if (si->si_used != so->used) {
841 PyErr_SetString(PyExc_RuntimeError,
842 "Set changed size during iteration");
843 si->si_used = -1; /* Make this state sticky */
844 return NULL;
847 i = si->si_pos;
848 assert(i>=0);
849 entry = so->table;
850 mask = so->mask;
851 while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
852 i++;
853 si->si_pos = i+1;
854 if (i > mask)
855 goto fail;
856 si->len--;
857 key = entry[i].key;
858 Py_INCREF(key);
859 return key;
861 fail:
862 Py_DECREF(so);
863 si->si_set = NULL;
864 return NULL;
867 PyTypeObject PySetIter_Type = {
868 PyVarObject_HEAD_INIT(&PyType_Type, 0)
869 "set_iterator", /* tp_name */
870 sizeof(setiterobject), /* tp_basicsize */
871 0, /* tp_itemsize */
872 /* methods */
873 (destructor)setiter_dealloc, /* tp_dealloc */
874 0, /* tp_print */
875 0, /* tp_getattr */
876 0, /* tp_setattr */
877 0, /* tp_reserved */
878 0, /* tp_repr */
879 0, /* tp_as_number */
880 0, /* tp_as_sequence */
881 0, /* tp_as_mapping */
882 0, /* tp_hash */
883 0, /* tp_call */
884 0, /* tp_str */
885 PyObject_GenericGetAttr, /* tp_getattro */
886 0, /* tp_setattro */
887 0, /* tp_as_buffer */
888 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
889 0, /* tp_doc */
890 (traverseproc)setiter_traverse, /* tp_traverse */
891 0, /* tp_clear */
892 0, /* tp_richcompare */
893 0, /* tp_weaklistoffset */
894 PyObject_SelfIter, /* tp_iter */
895 (iternextfunc)setiter_iternext, /* tp_iternext */
896 setiter_methods, /* tp_methods */
900 static PyObject *
901 set_iter(PySetObject *so)
903 setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type);
904 if (si == NULL)
905 return NULL;
906 Py_INCREF(so);
907 si->si_set = so;
908 si->si_used = so->used;
909 si->si_pos = 0;
910 si->len = so->used;
911 _PyObject_GC_TRACK(si);
912 return (PyObject *)si;
915 static int
916 set_update_internal(PySetObject *so, PyObject *other)
918 PyObject *key, *it;
920 if (PyAnySet_Check(other))
921 return set_merge(so, other);
923 if (PyDict_CheckExact(other)) {
924 PyObject *value;
925 Py_ssize_t pos = 0;
926 long hash;
927 Py_ssize_t dictsize = PyDict_Size(other);
929 /* Do one big resize at the start, rather than
930 * incrementally resizing as we insert new keys. Expect
931 * that there will be no (or few) overlapping keys.
933 if (dictsize == -1)
934 return -1;
935 if ((so->fill + dictsize)*3 >= (so->mask+1)*2) {
936 if (set_table_resize(so, (so->used + dictsize)*2) != 0)
937 return -1;
939 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
940 setentry an_entry;
942 an_entry.hash = hash;
943 an_entry.key = key;
944 if (set_add_entry(so, &an_entry) == -1)
945 return -1;
947 return 0;
950 it = PyObject_GetIter(other);
951 if (it == NULL)
952 return -1;
954 while ((key = PyIter_Next(it)) != NULL) {
955 if (set_add_key(so, key) == -1) {
956 Py_DECREF(it);
957 Py_DECREF(key);
958 return -1;
960 Py_DECREF(key);
962 Py_DECREF(it);
963 if (PyErr_Occurred())
964 return -1;
965 return 0;
968 static PyObject *
969 set_update(PySetObject *so, PyObject *args)
971 Py_ssize_t i;
973 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
974 PyObject *other = PyTuple_GET_ITEM(args, i);
975 if (set_update_internal(so, other) == -1)
976 return NULL;
978 Py_RETURN_NONE;
981 PyDoc_STRVAR(update_doc,
982 "Update a set with the union of itself and others.");
984 static PyObject *
985 make_new_set(PyTypeObject *type, PyObject *iterable)
987 register PySetObject *so = NULL;
989 if (dummy == NULL) { /* Auto-initialize dummy */
990 dummy = PyUnicode_FromString("<dummy key>");
991 if (dummy == NULL)
992 return NULL;
995 /* create PySetObject structure */
996 if (numfree &&
997 (type == &PySet_Type || type == &PyFrozenSet_Type)) {
998 so = free_list[--numfree];
999 assert (so != NULL && PyAnySet_CheckExact(so));
1000 Py_TYPE(so) = type;
1001 _Py_NewReference((PyObject *)so);
1002 EMPTY_TO_MINSIZE(so);
1003 PyObject_GC_Track(so);
1004 } else {
1005 so = (PySetObject *)type->tp_alloc(type, 0);
1006 if (so == NULL)
1007 return NULL;
1008 /* tp_alloc has already zeroed the structure */
1009 assert(so->table == NULL && so->fill == 0 && so->used == 0);
1010 INIT_NONZERO_SET_SLOTS(so);
1013 so->lookup = set_lookkey_unicode;
1014 so->weakreflist = NULL;
1016 if (iterable != NULL) {
1017 if (set_update_internal(so, iterable) == -1) {
1018 Py_DECREF(so);
1019 return NULL;
1023 return (PyObject *)so;
1026 static PyObject *
1027 make_new_set_basetype(PyTypeObject *type, PyObject *iterable)
1029 if (type != &PySet_Type && type != &PyFrozenSet_Type) {
1030 if (PyType_IsSubtype(type, &PySet_Type))
1031 type = &PySet_Type;
1032 else
1033 type = &PyFrozenSet_Type;
1035 return make_new_set(type, iterable);
1038 /* The empty frozenset is a singleton */
1039 static PyObject *emptyfrozenset = NULL;
1041 static PyObject *
1042 frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1044 PyObject *iterable = NULL, *result;
1046 if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds))
1047 return NULL;
1049 if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
1050 return NULL;
1052 if (type != &PyFrozenSet_Type)
1053 return make_new_set(type, iterable);
1055 if (iterable != NULL) {
1056 /* frozenset(f) is idempotent */
1057 if (PyFrozenSet_CheckExact(iterable)) {
1058 Py_INCREF(iterable);
1059 return iterable;
1061 result = make_new_set(type, iterable);
1062 if (result == NULL || PySet_GET_SIZE(result))
1063 return result;
1064 Py_DECREF(result);
1066 /* The empty frozenset is a singleton */
1067 if (emptyfrozenset == NULL)
1068 emptyfrozenset = make_new_set(type, NULL);
1069 Py_XINCREF(emptyfrozenset);
1070 return emptyfrozenset;
1073 void
1074 PySet_Fini(void)
1076 PySetObject *so;
1078 while (numfree) {
1079 numfree--;
1080 so = free_list[numfree];
1081 PyObject_GC_Del(so);
1083 Py_CLEAR(dummy);
1084 Py_CLEAR(emptyfrozenset);
1087 static PyObject *
1088 set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1090 if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds))
1091 return NULL;
1093 return make_new_set(type, NULL);
1096 /* set_swap_bodies() switches the contents of any two sets by moving their
1097 internal data pointers and, if needed, copying the internal smalltables.
1098 Semantically equivalent to:
1100 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1102 The function always succeeds and it leaves both objects in a stable state.
1103 Useful for creating temporary frozensets from sets for membership testing
1104 in __contains__(), discard(), and remove(). Also useful for operations
1105 that update in-place (by allowing an intermediate result to be swapped
1106 into one of the original inputs).
1109 static void
1110 set_swap_bodies(PySetObject *a, PySetObject *b)
1112 Py_ssize_t t;
1113 setentry *u;
1114 setentry *(*f)(PySetObject *so, PyObject *key, long hash);
1115 setentry tab[PySet_MINSIZE];
1116 long h;
1118 t = a->fill; a->fill = b->fill; b->fill = t;
1119 t = a->used; a->used = b->used; b->used = t;
1120 t = a->mask; a->mask = b->mask; b->mask = t;
1122 u = a->table;
1123 if (a->table == a->smalltable)
1124 u = b->smalltable;
1125 a->table = b->table;
1126 if (b->table == b->smalltable)
1127 a->table = a->smalltable;
1128 b->table = u;
1130 f = a->lookup; a->lookup = b->lookup; b->lookup = f;
1132 if (a->table == a->smalltable || b->table == b->smalltable) {
1133 memcpy(tab, a->smalltable, sizeof(tab));
1134 memcpy(a->smalltable, b->smalltable, sizeof(tab));
1135 memcpy(b->smalltable, tab, sizeof(tab));
1138 if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type) &&
1139 PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) {
1140 h = a->hash; a->hash = b->hash; b->hash = h;
1141 } else {
1142 a->hash = -1;
1143 b->hash = -1;
1147 static PyObject *
1148 set_copy(PySetObject *so)
1150 return make_new_set_basetype(Py_TYPE(so), (PyObject *)so);
1153 static PyObject *
1154 frozenset_copy(PySetObject *so)
1156 if (PyFrozenSet_CheckExact(so)) {
1157 Py_INCREF(so);
1158 return (PyObject *)so;
1160 return set_copy(so);
1163 PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
1165 static PyObject *
1166 set_clear(PySetObject *so)
1168 set_clear_internal(so);
1169 Py_RETURN_NONE;
1172 PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
1174 static PyObject *
1175 set_union(PySetObject *so, PyObject *args)
1177 PySetObject *result;
1178 PyObject *other;
1179 Py_ssize_t i;
1181 result = (PySetObject *)set_copy(so);
1182 if (result == NULL)
1183 return NULL;
1185 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1186 other = PyTuple_GET_ITEM(args, i);
1187 if ((PyObject *)so == other)
1188 continue;
1189 if (set_update_internal(result, other) == -1) {
1190 Py_DECREF(result);
1191 return NULL;
1194 return (PyObject *)result;
1197 PyDoc_STRVAR(union_doc,
1198 "Return the union of sets as a new set.\n\
1200 (i.e. all elements that are in either set.)");
1202 static PyObject *
1203 set_or(PySetObject *so, PyObject *other)
1205 PySetObject *result;
1207 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
1208 Py_INCREF(Py_NotImplemented);
1209 return Py_NotImplemented;
1212 result = (PySetObject *)set_copy(so);
1213 if (result == NULL)
1214 return NULL;
1215 if ((PyObject *)so == other)
1216 return (PyObject *)result;
1217 if (set_update_internal(result, other) == -1) {
1218 Py_DECREF(result);
1219 return NULL;
1221 return (PyObject *)result;
1224 static PyObject *
1225 set_ior(PySetObject *so, PyObject *other)
1227 if (!PyAnySet_Check(other)) {
1228 Py_INCREF(Py_NotImplemented);
1229 return Py_NotImplemented;
1231 if (set_update_internal(so, other) == -1)
1232 return NULL;
1233 Py_INCREF(so);
1234 return (PyObject *)so;
1237 static PyObject *
1238 set_intersection(PySetObject *so, PyObject *other)
1240 PySetObject *result;
1241 PyObject *key, *it, *tmp;
1243 if ((PyObject *)so == other)
1244 return set_copy(so);
1246 result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL);
1247 if (result == NULL)
1248 return NULL;
1250 if (PyAnySet_Check(other)) {
1251 Py_ssize_t pos = 0;
1252 setentry *entry;
1254 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1255 tmp = (PyObject *)so;
1256 so = (PySetObject *)other;
1257 other = tmp;
1260 while (set_next((PySetObject *)other, &pos, &entry)) {
1261 int rv = set_contains_entry(so, entry);
1262 if (rv == -1) {
1263 Py_DECREF(result);
1264 return NULL;
1266 if (rv) {
1267 if (set_add_entry(result, entry) == -1) {
1268 Py_DECREF(result);
1269 return NULL;
1273 return (PyObject *)result;
1276 it = PyObject_GetIter(other);
1277 if (it == NULL) {
1278 Py_DECREF(result);
1279 return NULL;
1282 while ((key = PyIter_Next(it)) != NULL) {
1283 int rv;
1284 setentry entry;
1285 long hash = PyObject_Hash(key);
1287 if (hash == -1) {
1288 Py_DECREF(it);
1289 Py_DECREF(result);
1290 Py_DECREF(key);
1291 return NULL;
1293 entry.hash = hash;
1294 entry.key = key;
1295 rv = set_contains_entry(so, &entry);
1296 if (rv == -1) {
1297 Py_DECREF(it);
1298 Py_DECREF(result);
1299 Py_DECREF(key);
1300 return NULL;
1302 if (rv) {
1303 if (set_add_entry(result, &entry) == -1) {
1304 Py_DECREF(it);
1305 Py_DECREF(result);
1306 Py_DECREF(key);
1307 return NULL;
1310 Py_DECREF(key);
1312 Py_DECREF(it);
1313 if (PyErr_Occurred()) {
1314 Py_DECREF(result);
1315 return NULL;
1317 return (PyObject *)result;
1320 static PyObject *
1321 set_intersection_multi(PySetObject *so, PyObject *args)
1323 Py_ssize_t i;
1324 PyObject *result = (PyObject *)so;
1326 if (PyTuple_GET_SIZE(args) == 0)
1327 return set_copy(so);
1329 Py_INCREF(so);
1330 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1331 PyObject *other = PyTuple_GET_ITEM(args, i);
1332 PyObject *newresult = set_intersection((PySetObject *)result, other);
1333 if (newresult == NULL) {
1334 Py_DECREF(result);
1335 return NULL;
1337 Py_DECREF(result);
1338 result = newresult;
1340 return result;
1343 PyDoc_STRVAR(intersection_doc,
1344 "Return the intersection of two or more sets as a new set.\n\
1346 (i.e. elements that are common to all of the sets.)");
1348 static PyObject *
1349 set_intersection_update(PySetObject *so, PyObject *other)
1351 PyObject *tmp;
1353 tmp = set_intersection(so, other);
1354 if (tmp == NULL)
1355 return NULL;
1356 set_swap_bodies(so, (PySetObject *)tmp);
1357 Py_DECREF(tmp);
1358 Py_RETURN_NONE;
1361 static PyObject *
1362 set_intersection_update_multi(PySetObject *so, PyObject *args)
1364 PyObject *tmp;
1366 tmp = set_intersection_multi(so, args);
1367 if (tmp == NULL)
1368 return NULL;
1369 set_swap_bodies(so, (PySetObject *)tmp);
1370 Py_DECREF(tmp);
1371 Py_RETURN_NONE;
1374 PyDoc_STRVAR(intersection_update_doc,
1375 "Update a set with the intersection of itself and another.");
1377 static PyObject *
1378 set_and(PySetObject *so, PyObject *other)
1380 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
1381 Py_INCREF(Py_NotImplemented);
1382 return Py_NotImplemented;
1384 return set_intersection(so, other);
1387 static PyObject *
1388 set_iand(PySetObject *so, PyObject *other)
1390 PyObject *result;
1392 if (!PyAnySet_Check(other)) {
1393 Py_INCREF(Py_NotImplemented);
1394 return Py_NotImplemented;
1396 result = set_intersection_update(so, other);
1397 if (result == NULL)
1398 return NULL;
1399 Py_DECREF(result);
1400 Py_INCREF(so);
1401 return (PyObject *)so;
1404 static PyObject *
1405 set_isdisjoint(PySetObject *so, PyObject *other)
1407 PyObject *key, *it, *tmp;
1409 if ((PyObject *)so == other) {
1410 if (PySet_GET_SIZE(so) == 0)
1411 Py_RETURN_TRUE;
1412 else
1413 Py_RETURN_FALSE;
1416 if (PyAnySet_CheckExact(other)) {
1417 Py_ssize_t pos = 0;
1418 setentry *entry;
1420 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1421 tmp = (PyObject *)so;
1422 so = (PySetObject *)other;
1423 other = tmp;
1425 while (set_next((PySetObject *)other, &pos, &entry)) {
1426 int rv = set_contains_entry(so, entry);
1427 if (rv == -1)
1428 return NULL;
1429 if (rv)
1430 Py_RETURN_FALSE;
1432 Py_RETURN_TRUE;
1435 it = PyObject_GetIter(other);
1436 if (it == NULL)
1437 return NULL;
1439 while ((key = PyIter_Next(it)) != NULL) {
1440 int rv;
1441 setentry entry;
1442 long hash = PyObject_Hash(key);;
1444 if (hash == -1) {
1445 Py_DECREF(key);
1446 Py_DECREF(it);
1447 return NULL;
1449 entry.hash = hash;
1450 entry.key = key;
1451 rv = set_contains_entry(so, &entry);
1452 Py_DECREF(key);
1453 if (rv == -1) {
1454 Py_DECREF(it);
1455 return NULL;
1457 if (rv) {
1458 Py_DECREF(it);
1459 Py_RETURN_FALSE;
1462 Py_DECREF(it);
1463 if (PyErr_Occurred())
1464 return NULL;
1465 Py_RETURN_TRUE;
1468 PyDoc_STRVAR(isdisjoint_doc,
1469 "Return True if two sets have a null intersection.");
1471 static int
1472 set_difference_update_internal(PySetObject *so, PyObject *other)
1474 if ((PyObject *)so == other)
1475 return set_clear_internal(so);
1477 if (PyAnySet_Check(other)) {
1478 setentry *entry;
1479 Py_ssize_t pos = 0;
1481 while (set_next((PySetObject *)other, &pos, &entry))
1482 if (set_discard_entry(so, entry) == -1)
1483 return -1;
1484 } else {
1485 PyObject *key, *it;
1486 it = PyObject_GetIter(other);
1487 if (it == NULL)
1488 return -1;
1490 while ((key = PyIter_Next(it)) != NULL) {
1491 if (set_discard_key(so, key) == -1) {
1492 Py_DECREF(it);
1493 Py_DECREF(key);
1494 return -1;
1496 Py_DECREF(key);
1498 Py_DECREF(it);
1499 if (PyErr_Occurred())
1500 return -1;
1502 /* If more than 1/5 are dummies, then resize them away. */
1503 if ((so->fill - so->used) * 5 < so->mask)
1504 return 0;
1505 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
1508 static PyObject *
1509 set_difference_update(PySetObject *so, PyObject *args)
1511 Py_ssize_t i;
1513 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1514 PyObject *other = PyTuple_GET_ITEM(args, i);
1515 if (set_difference_update_internal(so, other) == -1)
1516 return NULL;
1518 Py_RETURN_NONE;
1521 PyDoc_STRVAR(difference_update_doc,
1522 "Remove all elements of another set from this set.");
1524 static PyObject *
1525 set_difference(PySetObject *so, PyObject *other)
1527 PyObject *result;
1528 setentry *entry;
1529 Py_ssize_t pos = 0;
1531 if (!PyAnySet_Check(other) && !PyDict_CheckExact(other)) {
1532 result = set_copy(so);
1533 if (result == NULL)
1534 return NULL;
1535 if (set_difference_update_internal((PySetObject *)result, other) != -1)
1536 return result;
1537 Py_DECREF(result);
1538 return NULL;
1541 result = make_new_set_basetype(Py_TYPE(so), NULL);
1542 if (result == NULL)
1543 return NULL;
1545 if (PyDict_CheckExact(other)) {
1546 while (set_next(so, &pos, &entry)) {
1547 setentry entrycopy;
1548 entrycopy.hash = entry->hash;
1549 entrycopy.key = entry->key;
1550 if (!_PyDict_Contains(other, entry->key, entry->hash)) {
1551 if (set_add_entry((PySetObject *)result, &entrycopy) == -1) {
1552 Py_DECREF(result);
1553 return NULL;
1557 return result;
1560 while (set_next(so, &pos, &entry)) {
1561 int rv = set_contains_entry((PySetObject *)other, entry);
1562 if (rv == -1) {
1563 Py_DECREF(result);
1564 return NULL;
1566 if (!rv) {
1567 if (set_add_entry((PySetObject *)result, entry) == -1) {
1568 Py_DECREF(result);
1569 return NULL;
1573 return result;
1576 static PyObject *
1577 set_difference_multi(PySetObject *so, PyObject *args)
1579 Py_ssize_t i;
1580 PyObject *result, *other;
1582 if (PyTuple_GET_SIZE(args) == 0)
1583 return set_copy(so);
1585 other = PyTuple_GET_ITEM(args, 0);
1586 result = set_difference(so, other);
1587 if (result == NULL)
1588 return NULL;
1590 for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) {
1591 other = PyTuple_GET_ITEM(args, i);
1592 if (set_difference_update_internal((PySetObject *)result, other) == -1) {
1593 Py_DECREF(result);
1594 return NULL;
1597 return result;
1600 PyDoc_STRVAR(difference_doc,
1601 "Return the difference of two or more sets as a new set.\n\
1603 (i.e. all elements that are in this set but not the others.)");
1604 static PyObject *
1605 set_sub(PySetObject *so, PyObject *other)
1607 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
1608 Py_INCREF(Py_NotImplemented);
1609 return Py_NotImplemented;
1611 return set_difference(so, other);
1614 static PyObject *
1615 set_isub(PySetObject *so, PyObject *other)
1617 if (!PyAnySet_Check(other)) {
1618 Py_INCREF(Py_NotImplemented);
1619 return Py_NotImplemented;
1621 if (set_difference_update_internal(so, other) == -1)
1622 return NULL;
1623 Py_INCREF(so);
1624 return (PyObject *)so;
1627 static PyObject *
1628 set_symmetric_difference_update(PySetObject *so, PyObject *other)
1630 PySetObject *otherset;
1631 PyObject *key;
1632 Py_ssize_t pos = 0;
1633 setentry *entry;
1635 if ((PyObject *)so == other)
1636 return set_clear(so);
1638 if (PyDict_CheckExact(other)) {
1639 PyObject *value;
1640 int rv;
1641 long hash;
1642 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
1643 setentry an_entry;
1645 an_entry.hash = hash;
1646 an_entry.key = key;
1647 rv = set_discard_entry(so, &an_entry);
1648 if (rv == -1)
1649 return NULL;
1650 if (rv == DISCARD_NOTFOUND) {
1651 if (set_add_entry(so, &an_entry) == -1)
1652 return NULL;
1655 Py_RETURN_NONE;
1658 if (PyAnySet_Check(other)) {
1659 Py_INCREF(other);
1660 otherset = (PySetObject *)other;
1661 } else {
1662 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1663 if (otherset == NULL)
1664 return NULL;
1667 while (set_next(otherset, &pos, &entry)) {
1668 int rv = set_discard_entry(so, entry);
1669 if (rv == -1) {
1670 Py_DECREF(otherset);
1671 return NULL;
1673 if (rv == DISCARD_NOTFOUND) {
1674 if (set_add_entry(so, entry) == -1) {
1675 Py_DECREF(otherset);
1676 return NULL;
1680 Py_DECREF(otherset);
1681 Py_RETURN_NONE;
1684 PyDoc_STRVAR(symmetric_difference_update_doc,
1685 "Update a set with the symmetric difference of itself and another.");
1687 static PyObject *
1688 set_symmetric_difference(PySetObject *so, PyObject *other)
1690 PyObject *rv;
1691 PySetObject *otherset;
1693 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1694 if (otherset == NULL)
1695 return NULL;
1696 rv = set_symmetric_difference_update(otherset, (PyObject *)so);
1697 if (rv == NULL)
1698 return NULL;
1699 Py_DECREF(rv);
1700 return (PyObject *)otherset;
1703 PyDoc_STRVAR(symmetric_difference_doc,
1704 "Return the symmetric difference of two sets as a new set.\n\
1706 (i.e. all elements that are in exactly one of the sets.)");
1708 static PyObject *
1709 set_xor(PySetObject *so, PyObject *other)
1711 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
1712 Py_INCREF(Py_NotImplemented);
1713 return Py_NotImplemented;
1715 return set_symmetric_difference(so, other);
1718 static PyObject *
1719 set_ixor(PySetObject *so, PyObject *other)
1721 PyObject *result;
1723 if (!PyAnySet_Check(other)) {
1724 Py_INCREF(Py_NotImplemented);
1725 return Py_NotImplemented;
1727 result = set_symmetric_difference_update(so, other);
1728 if (result == NULL)
1729 return NULL;
1730 Py_DECREF(result);
1731 Py_INCREF(so);
1732 return (PyObject *)so;
1735 static PyObject *
1736 set_issubset(PySetObject *so, PyObject *other)
1738 setentry *entry;
1739 Py_ssize_t pos = 0;
1741 if (!PyAnySet_Check(other)) {
1742 PyObject *tmp, *result;
1743 tmp = make_new_set(&PySet_Type, other);
1744 if (tmp == NULL)
1745 return NULL;
1746 result = set_issubset(so, tmp);
1747 Py_DECREF(tmp);
1748 return result;
1750 if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
1751 Py_RETURN_FALSE;
1753 while (set_next(so, &pos, &entry)) {
1754 int rv = set_contains_entry((PySetObject *)other, entry);
1755 if (rv == -1)
1756 return NULL;
1757 if (!rv)
1758 Py_RETURN_FALSE;
1760 Py_RETURN_TRUE;
1763 PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
1765 static PyObject *
1766 set_issuperset(PySetObject *so, PyObject *other)
1768 PyObject *tmp, *result;
1770 if (!PyAnySet_Check(other)) {
1771 tmp = make_new_set(&PySet_Type, other);
1772 if (tmp == NULL)
1773 return NULL;
1774 result = set_issuperset(so, tmp);
1775 Py_DECREF(tmp);
1776 return result;
1778 return set_issubset((PySetObject *)other, (PyObject *)so);
1781 PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
1783 static PyObject *
1784 set_richcompare(PySetObject *v, PyObject *w, int op)
1786 PyObject *r1, *r2;
1788 if(!PyAnySet_Check(w)) {
1789 Py_INCREF(Py_NotImplemented);
1790 return Py_NotImplemented;
1792 switch (op) {
1793 case Py_EQ:
1794 if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
1795 Py_RETURN_FALSE;
1796 if (v->hash != -1 &&
1797 ((PySetObject *)w)->hash != -1 &&
1798 v->hash != ((PySetObject *)w)->hash)
1799 Py_RETURN_FALSE;
1800 return set_issubset(v, w);
1801 case Py_NE:
1802 r1 = set_richcompare(v, w, Py_EQ);
1803 if (r1 == NULL)
1804 return NULL;
1805 r2 = PyBool_FromLong(PyObject_Not(r1));
1806 Py_DECREF(r1);
1807 return r2;
1808 case Py_LE:
1809 return set_issubset(v, w);
1810 case Py_GE:
1811 return set_issuperset(v, w);
1812 case Py_LT:
1813 if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))
1814 Py_RETURN_FALSE;
1815 return set_issubset(v, w);
1816 case Py_GT:
1817 if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
1818 Py_RETURN_FALSE;
1819 return set_issuperset(v, w);
1821 Py_INCREF(Py_NotImplemented);
1822 return Py_NotImplemented;
1825 static PyObject *
1826 set_add(PySetObject *so, PyObject *key)
1828 if (set_add_key(so, key) == -1)
1829 return NULL;
1830 Py_RETURN_NONE;
1833 PyDoc_STRVAR(add_doc,
1834 "Add an element to a set.\n\
1836 This has no effect if the element is already present.");
1838 static int
1839 set_contains(PySetObject *so, PyObject *key)
1841 PyObject *tmpkey;
1842 int rv;
1844 rv = set_contains_key(so, key);
1845 if (rv == -1) {
1846 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1847 return -1;
1848 PyErr_Clear();
1849 tmpkey = make_new_set(&PyFrozenSet_Type, key);
1850 if (tmpkey == NULL)
1851 return -1;
1852 rv = set_contains(so, tmpkey);
1853 Py_DECREF(tmpkey);
1855 return rv;
1858 static PyObject *
1859 set_direct_contains(PySetObject *so, PyObject *key)
1861 long result;
1863 result = set_contains(so, key);
1864 if (result == -1)
1865 return NULL;
1866 return PyBool_FromLong(result);
1869 PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
1871 static PyObject *
1872 set_remove(PySetObject *so, PyObject *key)
1874 PyObject *tmpkey;
1875 int rv;
1877 rv = set_discard_key(so, key);
1878 if (rv == -1) {
1879 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1880 return NULL;
1881 PyErr_Clear();
1882 tmpkey = make_new_set(&PyFrozenSet_Type, key);
1883 if (tmpkey == NULL)
1884 return NULL;
1885 rv = set_discard_key(so, tmpkey);
1886 Py_DECREF(tmpkey);
1887 if (rv == -1)
1888 return NULL;
1891 if (rv == DISCARD_NOTFOUND) {
1892 set_key_error(key);
1893 return NULL;
1895 Py_RETURN_NONE;
1898 PyDoc_STRVAR(remove_doc,
1899 "Remove an element from a set; it must be a member.\n\
1901 If the element is not a member, raise a KeyError.");
1903 static PyObject *
1904 set_discard(PySetObject *so, PyObject *key)
1906 PyObject *tmpkey, *result;
1907 int rv;
1909 rv = set_discard_key(so, key);
1910 if (rv == -1) {
1911 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1912 return NULL;
1913 PyErr_Clear();
1914 tmpkey = make_new_set(&PyFrozenSet_Type, key);
1915 if (tmpkey == NULL)
1916 return NULL;
1917 result = set_discard(so, tmpkey);
1918 Py_DECREF(tmpkey);
1919 return result;
1921 Py_RETURN_NONE;
1924 PyDoc_STRVAR(discard_doc,
1925 "Remove an element from a set if it is a member.\n\
1927 If the element is not a member, do nothing.");
1929 static PyObject *
1930 set_reduce(PySetObject *so)
1932 PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;
1934 keys = PySequence_List((PyObject *)so);
1935 if (keys == NULL)
1936 goto done;
1937 args = PyTuple_Pack(1, keys);
1938 if (args == NULL)
1939 goto done;
1940 dict = PyObject_GetAttrString((PyObject *)so, "__dict__");
1941 if (dict == NULL) {
1942 PyErr_Clear();
1943 dict = Py_None;
1944 Py_INCREF(dict);
1946 result = PyTuple_Pack(3, Py_TYPE(so), args, dict);
1947 done:
1948 Py_XDECREF(args);
1949 Py_XDECREF(keys);
1950 Py_XDECREF(dict);
1951 return result;
1954 PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1956 static PyObject *
1957 set_sizeof(PySetObject *so)
1959 Py_ssize_t res;
1961 res = sizeof(PySetObject);
1962 if (so->table != so->smalltable)
1963 res = res + (so->mask + 1) * sizeof(setentry);
1964 return PyLong_FromSsize_t(res);
1967 PyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes");
1968 static int
1969 set_init(PySetObject *self, PyObject *args, PyObject *kwds)
1971 PyObject *iterable = NULL;
1973 if (!PyAnySet_Check(self))
1974 return -1;
1975 if (PySet_Check(self) && !_PyArg_NoKeywords("set()", kwds))
1976 return -1;
1977 if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable))
1978 return -1;
1979 set_clear_internal(self);
1980 self->hash = -1;
1981 if (iterable == NULL)
1982 return 0;
1983 return set_update_internal(self, iterable);
1986 static PySequenceMethods set_as_sequence = {
1987 set_len, /* sq_length */
1988 0, /* sq_concat */
1989 0, /* sq_repeat */
1990 0, /* sq_item */
1991 0, /* sq_slice */
1992 0, /* sq_ass_item */
1993 0, /* sq_ass_slice */
1994 (objobjproc)set_contains, /* sq_contains */
1997 /* set object ********************************************************/
1999 #ifdef Py_DEBUG
2000 static PyObject *test_c_api(PySetObject *so);
2002 PyDoc_STRVAR(test_c_api_doc, "Exercises C API. Returns True.\n\
2003 All is well if assertions don't fail.");
2004 #endif
2006 static PyMethodDef set_methods[] = {
2007 {"add", (PyCFunction)set_add, METH_O,
2008 add_doc},
2009 {"clear", (PyCFunction)set_clear, METH_NOARGS,
2010 clear_doc},
2011 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2012 contains_doc},
2013 {"copy", (PyCFunction)set_copy, METH_NOARGS,
2014 copy_doc},
2015 {"discard", (PyCFunction)set_discard, METH_O,
2016 discard_doc},
2017 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2018 difference_doc},
2019 {"difference_update", (PyCFunction)set_difference_update, METH_VARARGS,
2020 difference_update_doc},
2021 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2022 intersection_doc},
2023 {"intersection_update",(PyCFunction)set_intersection_update_multi, METH_VARARGS,
2024 intersection_update_doc},
2025 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2026 isdisjoint_doc},
2027 {"issubset", (PyCFunction)set_issubset, METH_O,
2028 issubset_doc},
2029 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2030 issuperset_doc},
2031 {"pop", (PyCFunction)set_pop, METH_NOARGS,
2032 pop_doc},
2033 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2034 reduce_doc},
2035 {"remove", (PyCFunction)set_remove, METH_O,
2036 remove_doc},
2037 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2038 sizeof_doc},
2039 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2040 symmetric_difference_doc},
2041 {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O,
2042 symmetric_difference_update_doc},
2043 #ifdef Py_DEBUG
2044 {"test_c_api", (PyCFunction)test_c_api, METH_NOARGS,
2045 test_c_api_doc},
2046 #endif
2047 {"union", (PyCFunction)set_union, METH_VARARGS,
2048 union_doc},
2049 {"update", (PyCFunction)set_update, METH_VARARGS,
2050 update_doc},
2051 {NULL, NULL} /* sentinel */
2054 static PyNumberMethods set_as_number = {
2055 0, /*nb_add*/
2056 (binaryfunc)set_sub, /*nb_subtract*/
2057 0, /*nb_multiply*/
2058 0, /*nb_remainder*/
2059 0, /*nb_divmod*/
2060 0, /*nb_power*/
2061 0, /*nb_negative*/
2062 0, /*nb_positive*/
2063 0, /*nb_absolute*/
2064 0, /*nb_bool*/
2065 0, /*nb_invert*/
2066 0, /*nb_lshift*/
2067 0, /*nb_rshift*/
2068 (binaryfunc)set_and, /*nb_and*/
2069 (binaryfunc)set_xor, /*nb_xor*/
2070 (binaryfunc)set_or, /*nb_or*/
2071 0, /*nb_int*/
2072 0, /*nb_reserved*/
2073 0, /*nb_float*/
2074 0, /*nb_inplace_add*/
2075 (binaryfunc)set_isub, /*nb_inplace_subtract*/
2076 0, /*nb_inplace_multiply*/
2077 0, /*nb_inplace_remainder*/
2078 0, /*nb_inplace_power*/
2079 0, /*nb_inplace_lshift*/
2080 0, /*nb_inplace_rshift*/
2081 (binaryfunc)set_iand, /*nb_inplace_and*/
2082 (binaryfunc)set_ixor, /*nb_inplace_xor*/
2083 (binaryfunc)set_ior, /*nb_inplace_or*/
2086 PyDoc_STRVAR(set_doc,
2087 "set() -> new empty set object\n\
2088 set(iterable) -> new set object\n\
2090 Build an unordered collection of unique elements.");
2092 PyTypeObject PySet_Type = {
2093 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2094 "set", /* tp_name */
2095 sizeof(PySetObject), /* tp_basicsize */
2096 0, /* tp_itemsize */
2097 /* methods */
2098 (destructor)set_dealloc, /* tp_dealloc */
2099 0, /* tp_print */
2100 0, /* tp_getattr */
2101 0, /* tp_setattr */
2102 0, /* tp_reserved */
2103 (reprfunc)set_repr, /* tp_repr */
2104 &set_as_number, /* tp_as_number */
2105 &set_as_sequence, /* tp_as_sequence */
2106 0, /* tp_as_mapping */
2107 (hashfunc)PyObject_HashNotImplemented, /* tp_hash */
2108 0, /* tp_call */
2109 0, /* tp_str */
2110 PyObject_GenericGetAttr, /* tp_getattro */
2111 0, /* tp_setattro */
2112 0, /* tp_as_buffer */
2113 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2114 Py_TPFLAGS_BASETYPE, /* tp_flags */
2115 set_doc, /* tp_doc */
2116 (traverseproc)set_traverse, /* tp_traverse */
2117 (inquiry)set_clear_internal, /* tp_clear */
2118 (richcmpfunc)set_richcompare, /* tp_richcompare */
2119 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2120 (getiterfunc)set_iter, /* tp_iter */
2121 0, /* tp_iternext */
2122 set_methods, /* tp_methods */
2123 0, /* tp_members */
2124 0, /* tp_getset */
2125 0, /* tp_base */
2126 0, /* tp_dict */
2127 0, /* tp_descr_get */
2128 0, /* tp_descr_set */
2129 0, /* tp_dictoffset */
2130 (initproc)set_init, /* tp_init */
2131 PyType_GenericAlloc, /* tp_alloc */
2132 set_new, /* tp_new */
2133 PyObject_GC_Del, /* tp_free */
2136 /* frozenset object ********************************************************/
2139 static PyMethodDef frozenset_methods[] = {
2140 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2141 contains_doc},
2142 {"copy", (PyCFunction)frozenset_copy, METH_NOARGS,
2143 copy_doc},
2144 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2145 difference_doc},
2146 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2147 intersection_doc},
2148 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2149 isdisjoint_doc},
2150 {"issubset", (PyCFunction)set_issubset, METH_O,
2151 issubset_doc},
2152 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2153 issuperset_doc},
2154 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2155 reduce_doc},
2156 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2157 sizeof_doc},
2158 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2159 symmetric_difference_doc},
2160 {"union", (PyCFunction)set_union, METH_VARARGS,
2161 union_doc},
2162 {NULL, NULL} /* sentinel */
2165 static PyNumberMethods frozenset_as_number = {
2166 0, /*nb_add*/
2167 (binaryfunc)set_sub, /*nb_subtract*/
2168 0, /*nb_multiply*/
2169 0, /*nb_remainder*/
2170 0, /*nb_divmod*/
2171 0, /*nb_power*/
2172 0, /*nb_negative*/
2173 0, /*nb_positive*/
2174 0, /*nb_absolute*/
2175 0, /*nb_bool*/
2176 0, /*nb_invert*/
2177 0, /*nb_lshift*/
2178 0, /*nb_rshift*/
2179 (binaryfunc)set_and, /*nb_and*/
2180 (binaryfunc)set_xor, /*nb_xor*/
2181 (binaryfunc)set_or, /*nb_or*/
2184 PyDoc_STRVAR(frozenset_doc,
2185 "frozenset() -> empty frozenset object\n\
2186 frozenset(iterable) -> frozenset object\n\
2188 Build an immutable unordered collection of unique elements.");
2190 PyTypeObject PyFrozenSet_Type = {
2191 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2192 "frozenset", /* tp_name */
2193 sizeof(PySetObject), /* tp_basicsize */
2194 0, /* tp_itemsize */
2195 /* methods */
2196 (destructor)set_dealloc, /* tp_dealloc */
2197 0, /* tp_print */
2198 0, /* tp_getattr */
2199 0, /* tp_setattr */
2200 0, /* tp_reserved */
2201 (reprfunc)set_repr, /* tp_repr */
2202 &frozenset_as_number, /* tp_as_number */
2203 &set_as_sequence, /* tp_as_sequence */
2204 0, /* tp_as_mapping */
2205 frozenset_hash, /* tp_hash */
2206 0, /* tp_call */
2207 0, /* tp_str */
2208 PyObject_GenericGetAttr, /* tp_getattro */
2209 0, /* tp_setattro */
2210 0, /* tp_as_buffer */
2211 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2212 Py_TPFLAGS_BASETYPE, /* tp_flags */
2213 frozenset_doc, /* tp_doc */
2214 (traverseproc)set_traverse, /* tp_traverse */
2215 (inquiry)set_clear_internal, /* tp_clear */
2216 (richcmpfunc)set_richcompare, /* tp_richcompare */
2217 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2218 (getiterfunc)set_iter, /* tp_iter */
2219 0, /* tp_iternext */
2220 frozenset_methods, /* tp_methods */
2221 0, /* tp_members */
2222 0, /* tp_getset */
2223 0, /* tp_base */
2224 0, /* tp_dict */
2225 0, /* tp_descr_get */
2226 0, /* tp_descr_set */
2227 0, /* tp_dictoffset */
2228 0, /* tp_init */
2229 PyType_GenericAlloc, /* tp_alloc */
2230 frozenset_new, /* tp_new */
2231 PyObject_GC_Del, /* tp_free */
2235 /***** C API functions *************************************************/
2237 PyObject *
2238 PySet_New(PyObject *iterable)
2240 return make_new_set(&PySet_Type, iterable);
2243 PyObject *
2244 PyFrozenSet_New(PyObject *iterable)
2246 return make_new_set(&PyFrozenSet_Type, iterable);
2249 Py_ssize_t
2250 PySet_Size(PyObject *anyset)
2252 if (!PyAnySet_Check(anyset)) {
2253 PyErr_BadInternalCall();
2254 return -1;
2256 return PySet_GET_SIZE(anyset);
2260 PySet_Clear(PyObject *set)
2262 if (!PySet_Check(set)) {
2263 PyErr_BadInternalCall();
2264 return -1;
2266 return set_clear_internal((PySetObject *)set);
2270 PySet_Contains(PyObject *anyset, PyObject *key)
2272 if (!PyAnySet_Check(anyset)) {
2273 PyErr_BadInternalCall();
2274 return -1;
2276 return set_contains_key((PySetObject *)anyset, key);
2280 PySet_Discard(PyObject *set, PyObject *key)
2282 if (!PySet_Check(set)) {
2283 PyErr_BadInternalCall();
2284 return -1;
2286 return set_discard_key((PySetObject *)set, key);
2290 PySet_Add(PyObject *anyset, PyObject *key)
2292 if (!PySet_Check(anyset) &&
2293 (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
2294 PyErr_BadInternalCall();
2295 return -1;
2297 return set_add_key((PySetObject *)anyset, key);
2301 _PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, long *hash)
2303 setentry *entry;
2305 if (!PyAnySet_Check(set)) {
2306 PyErr_BadInternalCall();
2307 return -1;
2309 if (set_next((PySetObject *)set, pos, &entry) == 0)
2310 return 0;
2311 *key = entry->key;
2312 *hash = entry->hash;
2313 return 1;
2316 PyObject *
2317 PySet_Pop(PyObject *set)
2319 if (!PySet_Check(set)) {
2320 PyErr_BadInternalCall();
2321 return NULL;
2323 return set_pop((PySetObject *)set);
2327 _PySet_Update(PyObject *set, PyObject *iterable)
2329 if (!PySet_Check(set)) {
2330 PyErr_BadInternalCall();
2331 return -1;
2333 return set_update_internal((PySetObject *)set, iterable);
2336 #ifdef Py_DEBUG
2338 /* Test code to be called with any three element set.
2339 Returns True and original set is restored. */
2341 #define assertRaises(call_return_value, exception) \
2342 do { \
2343 assert(call_return_value); \
2344 assert(PyErr_ExceptionMatches(exception)); \
2345 PyErr_Clear(); \
2346 } while(0)
2348 static PyObject *
2349 test_c_api(PySetObject *so)
2351 Py_ssize_t count;
2352 char *s;
2353 Py_ssize_t i;
2354 PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x;
2355 PyObject *ob = (PyObject *)so;
2356 long hash;
2358 /* Verify preconditions and exercise type/size checks */
2359 assert(PyAnySet_Check(ob));
2360 assert(PyAnySet_CheckExact(ob));
2361 assert(!PyFrozenSet_CheckExact(ob));
2362 assert(PySet_Size(ob) == 3);
2363 assert(PySet_GET_SIZE(ob) == 3);
2365 /* Raise TypeError for non-iterable constructor arguments */
2366 assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
2367 assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);
2369 /* Raise TypeError for unhashable key */
2370 dup = PySet_New(ob);
2371 assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
2372 assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
2373 assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);
2375 /* Exercise successful pop, contains, add, and discard */
2376 elem = PySet_Pop(ob);
2377 assert(PySet_Contains(ob, elem) == 0);
2378 assert(PySet_GET_SIZE(ob) == 2);
2379 assert(PySet_Add(ob, elem) == 0);
2380 assert(PySet_Contains(ob, elem) == 1);
2381 assert(PySet_GET_SIZE(ob) == 3);
2382 assert(PySet_Discard(ob, elem) == 1);
2383 assert(PySet_GET_SIZE(ob) == 2);
2384 assert(PySet_Discard(ob, elem) == 0);
2385 assert(PySet_GET_SIZE(ob) == 2);
2387 /* Exercise clear */
2388 dup2 = PySet_New(dup);
2389 assert(PySet_Clear(dup2) == 0);
2390 assert(PySet_Size(dup2) == 0);
2391 Py_DECREF(dup2);
2393 /* Raise SystemError on clear or update of frozen set */
2394 f = PyFrozenSet_New(dup);
2395 assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
2396 assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
2397 assert(PySet_Add(f, elem) == 0);
2398 Py_INCREF(f);
2399 assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
2400 Py_DECREF(f);
2401 Py_DECREF(f);
2403 /* Exercise direct iteration */
2404 i = 0, count = 0;
2405 while (_PySet_NextEntry((PyObject *)dup, &i, &x, &hash)) {
2406 s = _PyUnicode_AsString(x);
2407 assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
2408 count++;
2410 assert(count == 3);
2412 /* Exercise updates */
2413 dup2 = PySet_New(NULL);
2414 assert(_PySet_Update(dup2, dup) == 0);
2415 assert(PySet_Size(dup2) == 3);
2416 assert(_PySet_Update(dup2, dup) == 0);
2417 assert(PySet_Size(dup2) == 3);
2418 Py_DECREF(dup2);
2420 /* Raise SystemError when self argument is not a set or frozenset. */
2421 t = PyTuple_New(0);
2422 assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
2423 assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
2424 Py_DECREF(t);
2426 /* Raise SystemError when self argument is not a set. */
2427 f = PyFrozenSet_New(dup);
2428 assert(PySet_Size(f) == 3);
2429 assert(PyFrozenSet_CheckExact(f));
2430 assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
2431 assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
2432 Py_DECREF(f);
2434 /* Raise KeyError when popping from an empty set */
2435 assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
2436 Py_DECREF(ob);
2437 assert(PySet_GET_SIZE(ob) == 0);
2438 assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);
2440 /* Restore the set from the copy using the PyNumber API */
2441 assert(PyNumber_InPlaceOr(ob, dup) == ob);
2442 Py_DECREF(ob);
2444 /* Verify constructors accept NULL arguments */
2445 f = PySet_New(NULL);
2446 assert(f != NULL);
2447 assert(PySet_GET_SIZE(f) == 0);
2448 Py_DECREF(f);
2449 f = PyFrozenSet_New(NULL);
2450 assert(f != NULL);
2451 assert(PyFrozenSet_CheckExact(f));
2452 assert(PySet_GET_SIZE(f) == 0);
2453 Py_DECREF(f);
2455 Py_DECREF(elem);
2456 Py_DECREF(dup);
2457 Py_RETURN_TRUE;
2460 #undef assertRaises
2462 #endif