1
2/* set object implementation
3
4 Written and maintained by Raymond D. Hettinger <[email protected]>
5 Derived from Lib/sets.py and Objects/dictobject.c.
6
7 The basic lookup function used by all operations.
8 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
9
10 The initial probe index is computed as hash mod the table size.
11 Subsequent probe indices are computed as explained in Objects/dictobject.c.
12
13 To improve cache locality, each probe inspects a series of consecutive
14 nearby entries before moving on to probes elsewhere in memory. This leaves
15 us with a hybrid of linear probing and randomized probing. The linear probing
16 reduces the cost of hash collisions because consecutive memory accesses
17 tend to be much cheaper than scattered probes. After LINEAR_PROBES steps,
18 we then use more of the upper bits from the hash value and apply a simple
19 linear congruential random number generator. This helps break-up long
20 chains of collisions.
21
22 All arithmetic on hash should ignore overflow.
23
24 Unlike the dictionary implementation, the lookkey function can return
25 NULL if the rich comparison returns an error.
26
27 Use cases for sets differ considerably from dictionaries where looked-up
28 keys are more likely to be present. In contrast, sets are primarily
29 about membership testing where the presence of an element is not known in
30 advance. Accordingly, the set implementation needs to optimize for both
31 the found and not-found case.
32*/
33
34#include "Python.h"
35#include "pycore_object.h" // _PyObject_GC_UNTRACK()
36#include <stddef.h> // offsetof()
37
38/* Object used as dummy key to fill deleted entries */
39static PyObject _dummy_struct;
40
41#define dummy (&_dummy_struct)
42
43
44/* ======================================================================== */
45/* ======= Begin logic for probing the hash table ========================= */
46
47/* Set this to zero to turn-off linear probing */
48#ifndef LINEAR_PROBES
49#define LINEAR_PROBES 9
50#endif
51
52/* This must be >= 1 */
53#define PERTURB_SHIFT 5
54
55static setentry *
56set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
57{
58 setentry *table;
59 setentry *entry;
60 size_t perturb = hash;
61 size_t mask = so->mask;
62 size_t i = (size_t)hash & mask; /* Unsigned for defined overflow behavior */
63 int probes;
64 int cmp;
65
66 while (1) {
67 entry = &so->table[i];
68 probes = (i + LINEAR_PROBES <= mask) ? LINEAR_PROBES: 0;
69 do {
70 if (entry->hash == 0 && entry->key == NULL)
71 return entry;
72 if (entry->hash == hash) {
73 PyObject *startkey = entry->key;
74 assert(startkey != dummy);
75 if (startkey == key)
76 return entry;
77 if (PyUnicode_CheckExact(startkey)
78 && PyUnicode_CheckExact(key)
79 && _PyUnicode_EQ(startkey, key))
80 return entry;
81 table = so->table;
82 Py_INCREF(startkey);
83 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
84 Py_DECREF(startkey);
85 if (cmp < 0)
86 return NULL;
87 if (table != so->table || entry->key != startkey)
88 return set_lookkey(so, key, hash);
89 if (cmp > 0)
90 return entry;
91 mask = so->mask;
92 }
93 entry++;
94 } while (probes--);
95 perturb >>= PERTURB_SHIFT;
96 i = (i * 5 + 1 + perturb) & mask;
97 }
98}
99
100static int set_table_resize(PySetObject *, Py_ssize_t);
101
102static int
103set_add_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
104{
105 setentry *table;
106 setentry *freeslot;
107 setentry *entry;
108 size_t perturb;
109 size_t mask;
110 size_t i; /* Unsigned for defined overflow behavior */
111 int probes;
112 int cmp;
113
114 /* Pre-increment is necessary to prevent arbitrary code in the rich
115 comparison from deallocating the key just before the insertion. */
116 Py_INCREF(key);
117
118 restart:
119
120 mask = so->mask;
121 i = (size_t)hash & mask;
122 freeslot = NULL;
123 perturb = hash;
124
125 while (1) {
126 entry = &so->table[i];
127 probes = (i + LINEAR_PROBES <= mask) ? LINEAR_PROBES: 0;
128 do {
129 if (entry->hash == 0 && entry->key == NULL)
130 goto found_unused_or_dummy;
131 if (entry->hash == hash) {
132 PyObject *startkey = entry->key;
133 assert(startkey != dummy);
134 if (startkey == key)
135 goto found_active;
136 if (PyUnicode_CheckExact(startkey)
137 && PyUnicode_CheckExact(key)
138 && _PyUnicode_EQ(startkey, key))
139 goto found_active;
140 table = so->table;
141 Py_INCREF(startkey);
142 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
143 Py_DECREF(startkey);
144 if (cmp > 0)
145 goto found_active;
146 if (cmp < 0)
147 goto comparison_error;
148 if (table != so->table || entry->key != startkey)
149 goto restart;
150 mask = so->mask;
151 }
152 else if (entry->hash == -1) {
153 assert (entry->key == dummy);
154 freeslot = entry;
155 }
156 entry++;
157 } while (probes--);
158 perturb >>= PERTURB_SHIFT;
159 i = (i * 5 + 1 + perturb) & mask;
160 }
161
162 found_unused_or_dummy:
163 if (freeslot == NULL)
164 goto found_unused;
165 so->used++;
166 freeslot->key = key;
167 freeslot->hash = hash;
168 return 0;
169
170 found_unused:
171 so->fill++;
172 so->used++;
173 entry->key = key;
174 entry->hash = hash;
175 if ((size_t)so->fill*5 < mask*3)
176 return 0;
177 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
178
179 found_active:
180 Py_DECREF(key);
181 return 0;
182
183 comparison_error:
184 Py_DECREF(key);
185 return -1;
186}
187
188/*
189Internal routine used by set_table_resize() to insert an item which is
190known to be absent from the set. Besides the performance benefit,
191there is also safety benefit since using set_add_entry() risks making
192a callback in the middle of a set_table_resize(), see issue 1456209.
193The caller is responsible for updating the key's reference count and
194the setobject's fill and used fields.
195*/
196static void
197set_insert_clean(setentry *table, size_t mask, PyObject *key, Py_hash_t hash)
198{
199 setentry *entry;
200 size_t perturb = hash;
201 size_t i = (size_t)hash & mask;
202 size_t j;
203
204 while (1) {
205 entry = &table[i];
206 if (entry->key == NULL)
207 goto found_null;
208 if (i + LINEAR_PROBES <= mask) {
209 for (j = 0; j < LINEAR_PROBES; j++) {
210 entry++;
211 if (entry->key == NULL)
212 goto found_null;
213 }
214 }
215 perturb >>= PERTURB_SHIFT;
216 i = (i * 5 + 1 + perturb) & mask;
217 }
218 found_null:
219 entry->key = key;
220 entry->hash = hash;
221}
222
223/* ======== End logic for probing the hash table ========================== */
224/* ======================================================================== */
225
226/*
227Restructure the table by allocating a new table and reinserting all
228keys again. When entries have been deleted, the new table may
229actually be smaller than the old one.
230*/
231static int
232set_table_resize(PySetObject *so, Py_ssize_t minused)
233{
234 setentry *oldtable, *newtable, *entry;
235 Py_ssize_t oldmask = so->mask;
236 size_t newmask;
237 int is_oldtable_malloced;
238 setentry small_copy[PySet_MINSIZE];
239
240 assert(minused >= 0);
241
242 /* Find the smallest table size > minused. */
243 /* XXX speed-up with intrinsics */
244 size_t newsize = PySet_MINSIZE;
245 while (newsize <= (size_t)minused) {
246 newsize <<= 1; // The largest possible value is PY_SSIZE_T_MAX + 1.
247 }
248
249 /* Get space for a new table. */
250 oldtable = so->table;
251 assert(oldtable != NULL);
252 is_oldtable_malloced = oldtable != so->smalltable;
253
254 if (newsize == PySet_MINSIZE) {
255 /* A large table is shrinking, or we can't get any smaller. */
256 newtable = so->smalltable;
257 if (newtable == oldtable) {
258 if (so->fill == so->used) {
259 /* No dummies, so no point doing anything. */
260 return 0;
261 }
262 /* We're not going to resize it, but rebuild the
263 table anyway to purge old dummy entries.
264 Subtle: This is *necessary* if fill==size,
265 as set_lookkey needs at least one virgin slot to
266 terminate failing searches. If fill < size, it's
267 merely desirable, as dummies slow searches. */
268 assert(so->fill > so->used);
269 memcpy(small_copy, oldtable, sizeof(small_copy));
270 oldtable = small_copy;
271 }
272 }
273 else {
274 newtable = PyMem_NEW(setentry, newsize);
275 if (newtable == NULL) {
276 PyErr_NoMemory();
277 return -1;
278 }
279 }
280
281 /* Make the set empty, using the new table. */
282 assert(newtable != oldtable);
283 memset(newtable, 0, sizeof(setentry) * newsize);
284 so->mask = newsize - 1;
285 so->table = newtable;
286
287 /* Copy the data over; this is refcount-neutral for active entries;
288 dummy entries aren't copied over, of course */
289 newmask = (size_t)so->mask;
290 if (so->fill == so->used) {
291 for (entry = oldtable; entry <= oldtable + oldmask; entry++) {
292 if (entry->key != NULL) {
293 set_insert_clean(newtable, newmask, entry->key, entry->hash);
294 }
295 }
296 } else {
297 so->fill = so->used;
298 for (entry = oldtable; entry <= oldtable + oldmask; entry++) {
299 if (entry->key != NULL && entry->key != dummy) {
300 set_insert_clean(newtable, newmask, entry->key, entry->hash);
301 }
302 }
303 }
304
305 if (is_oldtable_malloced)
306 PyMem_Free(oldtable);
307 return 0;
308}
309
310static int
311set_contains_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
312{
313 setentry *entry;
314
315 entry = set_lookkey(so, key, hash);
316 if (entry != NULL)
317 return entry->key != NULL;
318 return -1;
319}
320
321#define DISCARD_NOTFOUND 0
322#define DISCARD_FOUND 1
323
324static int
325set_discard_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
326{
327 setentry *entry;
328 PyObject *old_key;
329
330 entry = set_lookkey(so, key, hash);
331 if (entry == NULL)
332 return -1;
333 if (entry->key == NULL)
334 return DISCARD_NOTFOUND;
335 old_key = entry->key;
336 entry->key = dummy;
337 entry->hash = -1;
338 so->used--;
339 Py_DECREF(old_key);
340 return DISCARD_FOUND;
341}
342
343static int
344set_add_key(PySetObject *so, PyObject *key)
345{
346 Py_hash_t hash;
347
348 if (!PyUnicode_CheckExact(key) ||
349 (hash = ((PyASCIIObject *) key)->hash) == -1) {
350 hash = PyObject_Hash(key);
351 if (hash == -1)
352 return -1;
353 }
354 return set_add_entry(so, key, hash);
355}
356
357static int
358set_contains_key(PySetObject *so, PyObject *key)
359{
360 Py_hash_t hash;
361
362 if (!PyUnicode_CheckExact(key) ||
363 (hash = ((PyASCIIObject *) key)->hash) == -1) {
364 hash = PyObject_Hash(key);
365 if (hash == -1)
366 return -1;
367 }
368 return set_contains_entry(so, key, hash);
369}
370
371static int
372set_discard_key(PySetObject *so, PyObject *key)
373{
374 Py_hash_t hash;
375
376 if (!PyUnicode_CheckExact(key) ||
377 (hash = ((PyASCIIObject *) key)->hash) == -1) {
378 hash = PyObject_Hash(key);
379 if (hash == -1)
380 return -1;
381 }
382 return set_discard_entry(so, key, hash);
383}
384
385static void
386set_empty_to_minsize(PySetObject *so)
387{
388 memset(so->smalltable, 0, sizeof(so->smalltable));
389 so->fill = 0;
390 so->used = 0;
391 so->mask = PySet_MINSIZE - 1;
392 so->table = so->smalltable;
393 so->hash = -1;
394}
395
396static int
397set_clear_internal(PySetObject *so)
398{
399 setentry *entry;
400 setentry *table = so->table;
401 Py_ssize_t fill = so->fill;
402 Py_ssize_t used = so->used;
403 int table_is_malloced = table != so->smalltable;
404 setentry small_copy[PySet_MINSIZE];
405
406 assert (PyAnySet_Check(so));
407 assert(table != NULL);
408
409 /* This is delicate. During the process of clearing the set,
410 * decrefs can cause the set to mutate. To avoid fatal confusion
411 * (voice of experience), we have to make the set empty before
412 * clearing the slots, and never refer to anything via so->ref while
413 * clearing.
414 */
415 if (table_is_malloced)
416 set_empty_to_minsize(so);
417
418 else if (fill > 0) {
419 /* It's a small table with something that needs to be cleared.
420 * Afraid the only safe way is to copy the set entries into
421 * another small table first.
422 */
423 memcpy(small_copy, table, sizeof(small_copy));
424 table = small_copy;
425 set_empty_to_minsize(so);
426 }
427 /* else it's a small table that's already empty */
428
429 /* Now we can finally clear things. If C had refcounts, we could
430 * assert that the refcount on table is 1 now, i.e. that this function
431 * has unique access to it, so decref side-effects can't alter it.
432 */
433 for (entry = table; used > 0; entry++) {
434 if (entry->key && entry->key != dummy) {
435 used--;
436 Py_DECREF(entry->key);
437 }
438 }
439
440 if (table_is_malloced)
441 PyMem_Free(table);
442 return 0;
443}
444
445/*
446 * Iterate over a set table. Use like so:
447 *
448 * Py_ssize_t pos;
449 * setentry *entry;
450 * pos = 0; # important! pos should not otherwise be changed by you
451 * while (set_next(yourset, &pos, &entry)) {
452 * Refer to borrowed reference in entry->key.
453 * }
454 *
455 * CAUTION: In general, it isn't safe to use set_next in a loop that
456 * mutates the table.
457 */
458static int
459set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)
460{
461 Py_ssize_t i;
462 Py_ssize_t mask;
463 setentry *entry;
464
465 assert (PyAnySet_Check(so));
466 i = *pos_ptr;
467 assert(i >= 0);
468 mask = so->mask;
469 entry = &so->table[i];
470 while (i <= mask && (entry->key == NULL || entry->key == dummy)) {
471 i++;
472 entry++;
473 }
474 *pos_ptr = i+1;
475 if (i > mask)
476 return 0;
477 assert(entry != NULL);
478 *entry_ptr = entry;
479 return 1;
480}
481
482static void
483set_dealloc(PySetObject *so)
484{
485 setentry *entry;
486 Py_ssize_t used = so->used;
487
488 /* bpo-31095: UnTrack is needed before calling any callbacks */
489 PyObject_GC_UnTrack(so);
490 Py_TRASHCAN_BEGIN(so, set_dealloc)
491 if (so->weakreflist != NULL)
492 PyObject_ClearWeakRefs((PyObject *) so);
493
494 for (entry = so->table; used > 0; entry++) {
495 if (entry->key && entry->key != dummy) {
496 used--;
497 Py_DECREF(entry->key);
498 }
499 }
500 if (so->table != so->smalltable)
501 PyMem_Free(so->table);
502 Py_TYPE(so)->tp_free(so);
503 Py_TRASHCAN_END
504}
505
506static PyObject *
507set_repr(PySetObject *so)
508{
509 PyObject *result=NULL, *keys, *listrepr, *tmp;
510 int status = Py_ReprEnter((PyObject*)so);
511
512 if (status != 0) {
513 if (status < 0)
514 return NULL;
515 return PyUnicode_FromFormat("%s(...)", Py_TYPE(so)->tp_name);
516 }
517
518 /* shortcut for the empty set */
519 if (!so->used) {
520 Py_ReprLeave((PyObject*)so);
521 return PyUnicode_FromFormat("%s()", Py_TYPE(so)->tp_name);
522 }
523
524 keys = PySequence_List((PyObject *)so);
525 if (keys == NULL)
526 goto done;
527
528 /* repr(keys)[1:-1] */
529 listrepr = PyObject_Repr(keys);
530 Py_DECREF(keys);
531 if (listrepr == NULL)
532 goto done;
533 tmp = PyUnicode_Substring(listrepr, 1, PyUnicode_GET_LENGTH(listrepr)-1);
534 Py_DECREF(listrepr);
535 if (tmp == NULL)
536 goto done;
537 listrepr = tmp;
538
539 if (!PySet_CheckExact(so))
540 result = PyUnicode_FromFormat("%s({%U})",
541 Py_TYPE(so)->tp_name,
542 listrepr);
543 else
544 result = PyUnicode_FromFormat("{%U}", listrepr);
545 Py_DECREF(listrepr);
546done:
547 Py_ReprLeave((PyObject*)so);
548 return result;
549}
550
551static Py_ssize_t
552set_len(PyObject *so)
553{
554 return ((PySetObject *)so)->used;
555}
556
557static int
558set_merge(PySetObject *so, PyObject *otherset)
559{
560 PySetObject *other;
561 PyObject *key;
562 Py_ssize_t i;
563 setentry *so_entry;
564 setentry *other_entry;
565
566 assert (PyAnySet_Check(so));
567 assert (PyAnySet_Check(otherset));
568
569 other = (PySetObject*)otherset;
570 if (other == so || other->used == 0)
571 /* a.update(a) or a.update(set()); nothing to do */
572 return 0;
573 /* Do one big resize at the start, rather than
574 * incrementally resizing as we insert new keys. Expect
575 * that there will be no (or few) overlapping keys.
576 */
577 if ((so->fill + other->used)*5 >= so->mask*3) {
578 if (set_table_resize(so, (so->used + other->used)*2) != 0)
579 return -1;
580 }
581 so_entry = so->table;
582 other_entry = other->table;
583
584 /* If our table is empty, and both tables have the same size, and
585 there are no dummies to eliminate, then just copy the pointers. */
586 if (so->fill == 0 && so->mask == other->mask && other->fill == other->used) {
587 for (i = 0; i <= other->mask; i++, so_entry++, other_entry++) {
588 key = other_entry->key;
589 if (key != NULL) {
590 assert(so_entry->key == NULL);
591 Py_INCREF(key);
592 so_entry->key = key;
593 so_entry->hash = other_entry->hash;
594 }
595 }
596 so->fill = other->fill;
597 so->used = other->used;
598 return 0;
599 }
600
601 /* If our table is empty, we can use set_insert_clean() */
602 if (so->fill == 0) {
603 setentry *newtable = so->table;
604 size_t newmask = (size_t)so->mask;
605 so->fill = other->used;
606 so->used = other->used;
607 for (i = other->mask + 1; i > 0 ; i--, other_entry++) {
608 key = other_entry->key;
609 if (key != NULL && key != dummy) {
610 Py_INCREF(key);
611 set_insert_clean(newtable, newmask, key, other_entry->hash);
612 }
613 }
614 return 0;
615 }
616
617 /* We can't assure there are no duplicates, so do normal insertions */
618 for (i = 0; i <= other->mask; i++) {
619 other_entry = &other->table[i];
620 key = other_entry->key;
621 if (key != NULL && key != dummy) {
622 if (set_add_entry(so, key, other_entry->hash))
623 return -1;
624 }
625 }
626 return 0;
627}
628
629static PyObject *
630set_pop(PySetObject *so, PyObject *Py_UNUSED(ignored))
631{
632 /* Make sure the search finger is in bounds */
633 setentry *entry = so->table + (so->finger & so->mask);
634 setentry *limit = so->table + so->mask;
635 PyObject *key;
636
637 if (so->used == 0) {
638 PyErr_SetString(PyExc_KeyError, "pop from an empty set");
639 return NULL;
640 }
641 while (entry->key == NULL || entry->key==dummy) {
642 entry++;
643 if (entry > limit)
644 entry = so->table;
645 }
646 key = entry->key;
647 entry->key = dummy;
648 entry->hash = -1;
649 so->used--;
650 so->finger = entry - so->table + 1; /* next place to start */
651 return key;
652}
653
654PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\
655Raises KeyError if the set is empty.");
656
657static int
658set_traverse(PySetObject *so, visitproc visit, void *arg)
659{
660 Py_ssize_t pos = 0;
661 setentry *entry;
662
663 while (set_next(so, &pos, &entry))
664 Py_VISIT(entry->key);
665 return 0;
666}
667
668/* Work to increase the bit dispersion for closely spaced hash values.
669 This is important because some use cases have many combinations of a
670 small number of elements with nearby hashes so that many distinct
671 combinations collapse to only a handful of distinct hash values. */
672
673static Py_uhash_t
674_shuffle_bits(Py_uhash_t h)
675{
676 return ((h ^ 89869747UL) ^ (h << 16)) * 3644798167UL;
677}
678
679/* Most of the constants in this hash algorithm are randomly chosen
680 large primes with "interesting bit patterns" and that passed tests
681 for good collision statistics on a variety of problematic datasets
682 including powersets and graph structures (such as David Eppstein's
683 graph recipes in Lib/test/test_set.py) */
684
685static Py_hash_t
686frozenset_hash(PyObject *self)
687{
688 PySetObject *so = (PySetObject *)self;
689 Py_uhash_t hash = 0;
690 setentry *entry;
691
692 if (so->hash != -1)
693 return so->hash;
694
695 /* Xor-in shuffled bits from every entry's hash field because xor is
696 commutative and a frozenset hash should be independent of order.
697
698 For speed, include null entries and dummy entries and then
699 subtract out their effect afterwards so that the final hash
700 depends only on active entries. This allows the code to be
701 vectorized by the compiler and it saves the unpredictable
702 branches that would arise when trying to exclude null and dummy
703 entries on every iteration. */
704
705 for (entry = so->table; entry <= &so->table[so->mask]; entry++)
706 hash ^= _shuffle_bits(entry->hash);
707
708 /* Remove the effect of an odd number of NULL entries */
709 if ((so->mask + 1 - so->fill) & 1)
710 hash ^= _shuffle_bits(0);
711
712 /* Remove the effect of an odd number of dummy entries */
713 if ((so->fill - so->used) & 1)
714 hash ^= _shuffle_bits(-1);
715
716 /* Factor in the number of active entries */
717 hash ^= ((Py_uhash_t)PySet_GET_SIZE(self) + 1) * 1927868237UL;
718
719 /* Disperse patterns arising in nested frozensets */
720 hash ^= (hash >> 11) ^ (hash >> 25);
721 hash = hash * 69069U + 907133923UL;
722
723 /* -1 is reserved as an error code */
724 if (hash == (Py_uhash_t)-1)
725 hash = 590923713UL;
726
727 so->hash = hash;
728 return hash;
729}
730
731/***** Set iterator type ***********************************************/
732
733typedef struct {
734 PyObject_HEAD
735 PySetObject *si_set; /* Set to NULL when iterator is exhausted */
736 Py_ssize_t si_used;
737 Py_ssize_t si_pos;
738 Py_ssize_t len;
739} setiterobject;
740
741static void
742setiter_dealloc(setiterobject *si)
743{
744 /* bpo-31095: UnTrack is needed before calling any callbacks */
745 _PyObject_GC_UNTRACK(si);
746 Py_XDECREF(si->si_set);
747 PyObject_GC_Del(si);
748}
749
750static int
751setiter_traverse(setiterobject *si, visitproc visit, void *arg)
752{
753 Py_VISIT(si->si_set);
754 return 0;
755}
756
757static PyObject *
758setiter_len(setiterobject *si, PyObject *Py_UNUSED(ignored))
759{
760 Py_ssize_t len = 0;
761 if (si->si_set != NULL && si->si_used == si->si_set->used)
762 len = si->len;
763 return PyLong_FromSsize_t(len);
764}
765
766PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
767
768static PyObject *setiter_iternext(setiterobject *si);
769
770static PyObject *
771setiter_reduce(setiterobject *si, PyObject *Py_UNUSED(ignored))
772{
773 _Py_IDENTIFIER(iter);
774 /* copy the iterator state */
775 setiterobject tmp = *si;
776 Py_XINCREF(tmp.si_set);
777
778 /* iterate the temporary into a list */
779 PyObject *list = PySequence_List((PyObject*)&tmp);
780 Py_XDECREF(tmp.si_set);
781 if (list == NULL) {
782 return NULL;
783 }
784 return Py_BuildValue("N(N)", _PyEval_GetBuiltinId(&PyId_iter), list);
785}
786
787PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
788
789static PyMethodDef setiter_methods[] = {
790 {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
791 {"__reduce__", (PyCFunction)setiter_reduce, METH_NOARGS, reduce_doc},
792 {NULL, NULL} /* sentinel */
793};
794
795static PyObject *setiter_iternext(setiterobject *si)
796{
797 PyObject *key;
798 Py_ssize_t i, mask;
799 setentry *entry;
800 PySetObject *so = si->si_set;
801
802 if (so == NULL)
803 return NULL;
804 assert (PyAnySet_Check(so));
805
806 if (si->si_used != so->used) {
807 PyErr_SetString(PyExc_RuntimeError,
808 "Set changed size during iteration");
809 si->si_used = -1; /* Make this state sticky */
810 return NULL;
811 }
812
813 i = si->si_pos;
814 assert(i>=0);
815 entry = so->table;
816 mask = so->mask;
817 while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
818 i++;
819 si->si_pos = i+1;
820 if (i > mask)
821 goto fail;
822 si->len--;
823 key = entry[i].key;
824 Py_INCREF(key);
825 return key;
826
827fail:
828 si->si_set = NULL;
829 Py_DECREF(so);
830 return NULL;
831}
832
833PyTypeObject PySetIter_Type = {
834 PyVarObject_HEAD_INIT(&PyType_Type, 0)
835 "set_iterator", /* tp_name */
836 sizeof(setiterobject), /* tp_basicsize */
837 0, /* tp_itemsize */
838 /* methods */
839 (destructor)setiter_dealloc, /* tp_dealloc */
840 0, /* tp_vectorcall_offset */
841 0, /* tp_getattr */
842 0, /* tp_setattr */
843 0, /* tp_as_async */
844 0, /* tp_repr */
845 0, /* tp_as_number */
846 0, /* tp_as_sequence */
847 0, /* tp_as_mapping */
848 0, /* tp_hash */
849 0, /* tp_call */
850 0, /* tp_str */
851 PyObject_GenericGetAttr, /* tp_getattro */
852 0, /* tp_setattro */
853 0, /* tp_as_buffer */
854 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
855 0, /* tp_doc */
856 (traverseproc)setiter_traverse, /* tp_traverse */
857 0, /* tp_clear */
858 0, /* tp_richcompare */
859 0, /* tp_weaklistoffset */
860 PyObject_SelfIter, /* tp_iter */
861 (iternextfunc)setiter_iternext, /* tp_iternext */
862 setiter_methods, /* tp_methods */
863 0,
864};
865
866static PyObject *
867set_iter(PySetObject *so)
868{
869 setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type);
870 if (si == NULL)
871 return NULL;
872 Py_INCREF(so);
873 si->si_set = so;
874 si->si_used = so->used;
875 si->si_pos = 0;
876 si->len = so->used;
877 _PyObject_GC_TRACK(si);
878 return (PyObject *)si;
879}
880
881static int
882set_update_internal(PySetObject *so, PyObject *other)
883{
884 PyObject *key, *it;
885
886 if (PyAnySet_Check(other))
887 return set_merge(so, other);
888
889 if (PyDict_CheckExact(other)) {
890 PyObject *value;
891 Py_ssize_t pos = 0;
892 Py_hash_t hash;
893 Py_ssize_t dictsize = PyDict_GET_SIZE(other);
894
895 /* Do one big resize at the start, rather than
896 * incrementally resizing as we insert new keys. Expect
897 * that there will be no (or few) overlapping keys.
898 */
899 if (dictsize < 0)
900 return -1;
901 if ((so->fill + dictsize)*5 >= so->mask*3) {
902 if (set_table_resize(so, (so->used + dictsize)*2) != 0)
903 return -1;
904 }
905 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
906 if (set_add_entry(so, key, hash))
907 return -1;
908 }
909 return 0;
910 }
911
912 it = PyObject_GetIter(other);
913 if (it == NULL)
914 return -1;
915
916 while ((key = PyIter_Next(it)) != NULL) {
917 if (set_add_key(so, key)) {
918 Py_DECREF(it);
919 Py_DECREF(key);
920 return -1;
921 }
922 Py_DECREF(key);
923 }
924 Py_DECREF(it);
925 if (PyErr_Occurred())
926 return -1;
927 return 0;
928}
929
930static PyObject *
931set_update(PySetObject *so, PyObject *args)
932{
933 Py_ssize_t i;
934
935 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
936 PyObject *other = PyTuple_GET_ITEM(args, i);
937 if (set_update_internal(so, other))
938 return NULL;
939 }
940 Py_RETURN_NONE;
941}
942
943PyDoc_STRVAR(update_doc,
944"Update a set with the union of itself and others.");
945
946/* XXX Todo:
947 If aligned memory allocations become available, make the
948 set object 64 byte aligned so that most of the fields
949 can be retrieved or updated in a single cache line.
950*/
951
952static PyObject *
953make_new_set(PyTypeObject *type, PyObject *iterable)
954{
955 assert(PyType_Check(type));
956 PySetObject *so;
957
958 so = (PySetObject *)type->tp_alloc(type, 0);
959 if (so == NULL)
960 return NULL;
961
962 so->fill = 0;
963 so->used = 0;
964 so->mask = PySet_MINSIZE - 1;
965 so->table = so->smalltable;
966 so->hash = -1;
967 so->finger = 0;
968 so->weakreflist = NULL;
969
970 if (iterable != NULL) {
971 if (set_update_internal(so, iterable)) {
972 Py_DECREF(so);
973 return NULL;
974 }
975 }
976
977 return (PyObject *)so;
978}
979
980static PyObject *
981make_new_set_basetype(PyTypeObject *type, PyObject *iterable)
982{
983 if (type != &PySet_Type && type != &PyFrozenSet_Type) {
984 if (PyType_IsSubtype(type, &PySet_Type))
985 type = &PySet_Type;
986 else
987 type = &PyFrozenSet_Type;
988 }
989 return make_new_set(type, iterable);
990}
991
992static PyObject *
993make_new_frozenset(PyTypeObject *type, PyObject *iterable)
994{
995 if (type != &PyFrozenSet_Type) {
996 return make_new_set(type, iterable);
997 }
998
999 if (iterable != NULL && PyFrozenSet_CheckExact(iterable)) {
1000 /* frozenset(f) is idempotent */
1001 Py_INCREF(iterable);
1002 return iterable;
1003 }
1004 return make_new_set((PyTypeObject *)type, iterable);
1005}
1006
1007static PyObject *
1008frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1009{
1010 PyObject *iterable = NULL;
1011
1012 if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset", kwds)) {
1013 return NULL;
1014 }
1015
1016 if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable)) {
1017 return NULL;
1018 }
1019
1020 return make_new_frozenset(type, iterable);
1021}
1022
1023static PyObject *
1024frozenset_vectorcall(PyObject *type, PyObject * const*args,
1025 size_t nargsf, PyObject *kwnames)
1026{
1027 if (!_PyArg_NoKwnames("frozenset", kwnames)) {
1028 return NULL;
1029 }
1030
1031 Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);
1032 if (!_PyArg_CheckPositional("frozenset", nargs, 0, 1)) {
1033 return NULL;
1034 }
1035
1036 PyObject *iterable = (nargs ? args[0] : NULL);
1037 return make_new_frozenset((PyTypeObject *)type, iterable);
1038}
1039
1040static PyObject *
1041set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1042{
1043 return make_new_set(type, NULL);
1044}
1045
1046/* set_swap_bodies() switches the contents of any two sets by moving their
1047 internal data pointers and, if needed, copying the internal smalltables.
1048 Semantically equivalent to:
1049
1050 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1051
1052 The function always succeeds and it leaves both objects in a stable state.
1053 Useful for operations that update in-place (by allowing an intermediate
1054 result to be swapped into one of the original inputs).
1055*/
1056
1057static void
1058set_swap_bodies(PySetObject *a, PySetObject *b)
1059{
1060 Py_ssize_t t;
1061 setentry *u;
1062 setentry tab[PySet_MINSIZE];
1063 Py_hash_t h;
1064
1065 t = a->fill; a->fill = b->fill; b->fill = t;
1066 t = a->used; a->used = b->used; b->used = t;
1067 t = a->mask; a->mask = b->mask; b->mask = t;
1068
1069 u = a->table;
1070 if (a->table == a->smalltable)
1071 u = b->smalltable;
1072 a->table = b->table;
1073 if (b->table == b->smalltable)
1074 a->table = a->smalltable;
1075 b->table = u;
1076
1077 if (a->table == a->smalltable || b->table == b->smalltable) {
1078 memcpy(tab, a->smalltable, sizeof(tab));
1079 memcpy(a->smalltable, b->smalltable, sizeof(tab));
1080 memcpy(b->smalltable, tab, sizeof(tab));
1081 }
1082
1083 if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type) &&
1084 PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) {
1085 h = a->hash; a->hash = b->hash; b->hash = h;
1086 } else {
1087 a->hash = -1;
1088 b->hash = -1;
1089 }
1090}
1091
1092static PyObject *
1093set_copy(PySetObject *so, PyObject *Py_UNUSED(ignored))
1094{
1095 return make_new_set_basetype(Py_TYPE(so), (PyObject *)so);
1096}
1097
1098static PyObject *
1099frozenset_copy(PySetObject *so, PyObject *Py_UNUSED(ignored))
1100{
1101 if (PyFrozenSet_CheckExact(so)) {
1102 Py_INCREF(so);
1103 return (PyObject *)so;
1104 }
1105 return set_copy(so, NULL);
1106}
1107
1108PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
1109
1110static PyObject *
1111set_clear(PySetObject *so, PyObject *Py_UNUSED(ignored))
1112{
1113 set_clear_internal(so);
1114 Py_RETURN_NONE;
1115}
1116
1117PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
1118
1119static PyObject *
1120set_union(PySetObject *so, PyObject *args)
1121{
1122 PySetObject *result;
1123 PyObject *other;
1124 Py_ssize_t i;
1125
1126 result = (PySetObject *)set_copy(so, NULL);
1127 if (result == NULL)
1128 return NULL;
1129
1130 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1131 other = PyTuple_GET_ITEM(args, i);
1132 if ((PyObject *)so == other)
1133 continue;
1134 if (set_update_internal(result, other)) {
1135 Py_DECREF(result);
1136 return NULL;
1137 }
1138 }
1139 return (PyObject *)result;
1140}
1141
1142PyDoc_STRVAR(union_doc,
1143 "Return the union of sets as a new set.\n\
1144\n\
1145(i.e. all elements that are in either set.)");
1146
1147static PyObject *
1148set_or(PySetObject *so, PyObject *other)
1149{
1150 PySetObject *result;
1151
1152 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1153 Py_RETURN_NOTIMPLEMENTED;
1154
1155 result = (PySetObject *)set_copy(so, NULL);
1156 if (result == NULL)
1157 return NULL;
1158 if ((PyObject *)so == other)
1159 return (PyObject *)result;
1160 if (set_update_internal(result, other)) {
1161 Py_DECREF(result);
1162 return NULL;
1163 }
1164 return (PyObject *)result;
1165}
1166
1167static PyObject *
1168set_ior(PySetObject *so, PyObject *other)
1169{
1170 if (!PyAnySet_Check(other))
1171 Py_RETURN_NOTIMPLEMENTED;
1172
1173 if (set_update_internal(so, other))
1174 return NULL;
1175 Py_INCREF(so);
1176 return (PyObject *)so;
1177}
1178
1179static PyObject *
1180set_intersection(PySetObject *so, PyObject *other)
1181{
1182 PySetObject *result;
1183 PyObject *key, *it, *tmp;
1184 Py_hash_t hash;
1185 int rv;
1186
1187 if ((PyObject *)so == other)
1188 return set_copy(so, NULL);
1189
1190 result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL);
1191 if (result == NULL)
1192 return NULL;
1193
1194 if (PyAnySet_Check(other)) {
1195 Py_ssize_t pos = 0;
1196 setentry *entry;
1197
1198 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1199 tmp = (PyObject *)so;
1200 so = (PySetObject *)other;
1201 other = tmp;
1202 }
1203
1204 while (set_next((PySetObject *)other, &pos, &entry)) {
1205 key = entry->key;
1206 hash = entry->hash;
1207 Py_INCREF(key);
1208 rv = set_contains_entry(so, key, hash);
1209 if (rv < 0) {
1210 Py_DECREF(result);
1211 Py_DECREF(key);
1212 return NULL;
1213 }
1214 if (rv) {
1215 if (set_add_entry(result, key, hash)) {
1216 Py_DECREF(result);
1217 Py_DECREF(key);
1218 return NULL;
1219 }
1220 }
1221 Py_DECREF(key);
1222 }
1223 return (PyObject *)result;
1224 }
1225
1226 it = PyObject_GetIter(other);
1227 if (it == NULL) {
1228 Py_DECREF(result);
1229 return NULL;
1230 }
1231
1232 while ((key = PyIter_Next(it)) != NULL) {
1233 hash = PyObject_Hash(key);
1234 if (hash == -1)
1235 goto error;
1236 rv = set_contains_entry(so, key, hash);
1237 if (rv < 0)
1238 goto error;
1239 if (rv) {
1240 if (set_add_entry(result, key, hash))
1241 goto error;
1242 }
1243 Py_DECREF(key);
1244 }
1245 Py_DECREF(it);
1246 if (PyErr_Occurred()) {
1247 Py_DECREF(result);
1248 return NULL;
1249 }
1250 return (PyObject *)result;
1251 error:
1252 Py_DECREF(it);
1253 Py_DECREF(result);
1254 Py_DECREF(key);
1255 return NULL;
1256}
1257
1258static PyObject *
1259set_intersection_multi(PySetObject *so, PyObject *args)
1260{
1261 Py_ssize_t i;
1262 PyObject *result = (PyObject *)so;
1263
1264 if (PyTuple_GET_SIZE(args) == 0)
1265 return set_copy(so, NULL);
1266
1267 Py_INCREF(so);
1268 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1269 PyObject *other = PyTuple_GET_ITEM(args, i);
1270 PyObject *newresult = set_intersection((PySetObject *)result, other);
1271 if (newresult == NULL) {
1272 Py_DECREF(result);
1273 return NULL;
1274 }
1275 Py_DECREF(result);
1276 result = newresult;
1277 }
1278 return result;
1279}
1280
1281PyDoc_STRVAR(intersection_doc,
1282"Return the intersection of two sets as a new set.\n\
1283\n\
1284(i.e. all elements that are in both sets.)");
1285
1286static PyObject *
1287set_intersection_update(PySetObject *so, PyObject *other)
1288{
1289 PyObject *tmp;
1290
1291 tmp = set_intersection(so, other);
1292 if (tmp == NULL)
1293 return NULL;
1294 set_swap_bodies(so, (PySetObject *)tmp);
1295 Py_DECREF(tmp);
1296 Py_RETURN_NONE;
1297}
1298
1299static PyObject *
1300set_intersection_update_multi(PySetObject *so, PyObject *args)
1301{
1302 PyObject *tmp;
1303
1304 tmp = set_intersection_multi(so, args);
1305 if (tmp == NULL)
1306 return NULL;
1307 set_swap_bodies(so, (PySetObject *)tmp);
1308 Py_DECREF(tmp);
1309 Py_RETURN_NONE;
1310}
1311
1312PyDoc_STRVAR(intersection_update_doc,
1313"Update a set with the intersection of itself and another.");
1314
1315static PyObject *
1316set_and(PySetObject *so, PyObject *other)
1317{
1318 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1319 Py_RETURN_NOTIMPLEMENTED;
1320 return set_intersection(so, other);
1321}
1322
1323static PyObject *
1324set_iand(PySetObject *so, PyObject *other)
1325{
1326 PyObject *result;
1327
1328 if (!PyAnySet_Check(other))
1329 Py_RETURN_NOTIMPLEMENTED;
1330 result = set_intersection_update(so, other);
1331 if (result == NULL)
1332 return NULL;
1333 Py_DECREF(result);
1334 Py_INCREF(so);
1335 return (PyObject *)so;
1336}
1337
1338static PyObject *
1339set_isdisjoint(PySetObject *so, PyObject *other)
1340{
1341 PyObject *key, *it, *tmp;
1342 int rv;
1343
1344 if ((PyObject *)so == other) {
1345 if (PySet_GET_SIZE(so) == 0)
1346 Py_RETURN_TRUE;
1347 else
1348 Py_RETURN_FALSE;
1349 }
1350
1351 if (PyAnySet_CheckExact(other)) {
1352 Py_ssize_t pos = 0;
1353 setentry *entry;
1354
1355 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1356 tmp = (PyObject *)so;
1357 so = (PySetObject *)other;
1358 other = tmp;
1359 }
1360 while (set_next((PySetObject *)other, &pos, &entry)) {
1361 PyObject *key = entry->key;
1362 Py_INCREF(key);
1363 rv = set_contains_entry(so, key, entry->hash);
1364 Py_DECREF(key);
1365 if (rv < 0) {
1366 return NULL;
1367 }
1368 if (rv) {
1369 Py_RETURN_FALSE;
1370 }
1371 }
1372 Py_RETURN_TRUE;
1373 }
1374
1375 it = PyObject_GetIter(other);
1376 if (it == NULL)
1377 return NULL;
1378
1379 while ((key = PyIter_Next(it)) != NULL) {
1380 Py_hash_t hash = PyObject_Hash(key);
1381
1382 if (hash == -1) {
1383 Py_DECREF(key);
1384 Py_DECREF(it);
1385 return NULL;
1386 }
1387 rv = set_contains_entry(so, key, hash);
1388 Py_DECREF(key);
1389 if (rv < 0) {
1390 Py_DECREF(it);
1391 return NULL;
1392 }
1393 if (rv) {
1394 Py_DECREF(it);
1395 Py_RETURN_FALSE;
1396 }
1397 }
1398 Py_DECREF(it);
1399 if (PyErr_Occurred())
1400 return NULL;
1401 Py_RETURN_TRUE;
1402}
1403
1404PyDoc_STRVAR(isdisjoint_doc,
1405"Return True if two sets have a null intersection.");
1406
1407static int
1408set_difference_update_internal(PySetObject *so, PyObject *other)
1409{
1410 if ((PyObject *)so == other)
1411 return set_clear_internal(so);
1412
1413 if (PyAnySet_Check(other)) {
1414 setentry *entry;
1415 Py_ssize_t pos = 0;
1416
1417 /* Optimization: When the other set is more than 8 times
1418 larger than the base set, replace the other set with
1419 intersection of the two sets.
1420 */
1421 if ((PySet_GET_SIZE(other) >> 3) > PySet_GET_SIZE(so)) {
1422 other = set_intersection(so, other);
1423 if (other == NULL)
1424 return -1;
1425 } else {
1426 Py_INCREF(other);
1427 }
1428
1429 while (set_next((PySetObject *)other, &pos, &entry)) {
1430 PyObject *key = entry->key;
1431 Py_INCREF(key);
1432 if (set_discard_entry(so, key, entry->hash) < 0) {
1433 Py_DECREF(other);
1434 Py_DECREF(key);
1435 return -1;
1436 }
1437 Py_DECREF(key);
1438 }
1439
1440 Py_DECREF(other);
1441 } else {
1442 PyObject *key, *it;
1443 it = PyObject_GetIter(other);
1444 if (it == NULL)
1445 return -1;
1446
1447 while ((key = PyIter_Next(it)) != NULL) {
1448 if (set_discard_key(so, key) < 0) {
1449 Py_DECREF(it);
1450 Py_DECREF(key);
1451 return -1;
1452 }
1453 Py_DECREF(key);
1454 }
1455 Py_DECREF(it);
1456 if (PyErr_Occurred())
1457 return -1;
1458 }
1459 /* If more than 1/4th are dummies, then resize them away. */
1460 if ((size_t)(so->fill - so->used) <= (size_t)so->mask / 4)
1461 return 0;
1462 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
1463}
1464
1465static PyObject *
1466set_difference_update(PySetObject *so, PyObject *args)
1467{
1468 Py_ssize_t i;
1469
1470 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1471 PyObject *other = PyTuple_GET_ITEM(args, i);
1472 if (set_difference_update_internal(so, other))
1473 return NULL;
1474 }
1475 Py_RETURN_NONE;
1476}
1477
1478PyDoc_STRVAR(difference_update_doc,
1479"Remove all elements of another set from this set.");
1480
1481static PyObject *
1482set_copy_and_difference(PySetObject *so, PyObject *other)
1483{
1484 PyObject *result;
1485
1486 result = set_copy(so, NULL);
1487 if (result == NULL)
1488 return NULL;
1489 if (set_difference_update_internal((PySetObject *) result, other) == 0)
1490 return result;
1491 Py_DECREF(result);
1492 return NULL;
1493}
1494
1495static PyObject *
1496set_difference(PySetObject *so, PyObject *other)
1497{
1498 PyObject *result;
1499 PyObject *key;
1500 Py_hash_t hash;
1501 setentry *entry;
1502 Py_ssize_t pos = 0, other_size;
1503 int rv;
1504
1505 if (PyAnySet_Check(other)) {
1506 other_size = PySet_GET_SIZE(other);
1507 }
1508 else if (PyDict_CheckExact(other)) {
1509 other_size = PyDict_GET_SIZE(other);
1510 }
1511 else {
1512 return set_copy_and_difference(so, other);
1513 }
1514
1515 /* If len(so) much more than len(other), it's more efficient to simply copy
1516 * so and then iterate other looking for common elements. */
1517 if ((PySet_GET_SIZE(so) >> 2) > other_size) {
1518 return set_copy_and_difference(so, other);
1519 }
1520
1521 result = make_new_set_basetype(Py_TYPE(so), NULL);
1522 if (result == NULL)
1523 return NULL;
1524
1525 if (PyDict_CheckExact(other)) {
1526 while (set_next(so, &pos, &entry)) {
1527 key = entry->key;
1528 hash = entry->hash;
1529 Py_INCREF(key);
1530 rv = _PyDict_Contains_KnownHash(other, key, hash);
1531 if (rv < 0) {
1532 Py_DECREF(result);
1533 Py_DECREF(key);
1534 return NULL;
1535 }
1536 if (!rv) {
1537 if (set_add_entry((PySetObject *)result, key, hash)) {
1538 Py_DECREF(result);
1539 Py_DECREF(key);
1540 return NULL;
1541 }
1542 }
1543 Py_DECREF(key);
1544 }
1545 return result;
1546 }
1547
1548 /* Iterate over so, checking for common elements in other. */
1549 while (set_next(so, &pos, &entry)) {
1550 key = entry->key;
1551 hash = entry->hash;
1552 Py_INCREF(key);
1553 rv = set_contains_entry((PySetObject *)other, key, hash);
1554 if (rv < 0) {
1555 Py_DECREF(result);
1556 Py_DECREF(key);
1557 return NULL;
1558 }
1559 if (!rv) {
1560 if (set_add_entry((PySetObject *)result, key, hash)) {
1561 Py_DECREF(result);
1562 Py_DECREF(key);
1563 return NULL;
1564 }
1565 }
1566 Py_DECREF(key);
1567 }
1568 return result;
1569}
1570
1571static PyObject *
1572set_difference_multi(PySetObject *so, PyObject *args)
1573{
1574 Py_ssize_t i;
1575 PyObject *result, *other;
1576
1577 if (PyTuple_GET_SIZE(args) == 0)
1578 return set_copy(so, NULL);
1579
1580 other = PyTuple_GET_ITEM(args, 0);
1581 result = set_difference(so, other);
1582 if (result == NULL)
1583 return NULL;
1584
1585 for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) {
1586 other = PyTuple_GET_ITEM(args, i);
1587 if (set_difference_update_internal((PySetObject *)result, other)) {
1588 Py_DECREF(result);
1589 return NULL;
1590 }
1591 }
1592 return result;
1593}
1594
1595PyDoc_STRVAR(difference_doc,
1596"Return the difference of two or more sets as a new set.\n\
1597\n\
1598(i.e. all elements that are in this set but not the others.)");
1599static PyObject *
1600set_sub(PySetObject *so, PyObject *other)
1601{
1602 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1603 Py_RETURN_NOTIMPLEMENTED;
1604 return set_difference(so, other);
1605}
1606
1607static PyObject *
1608set_isub(PySetObject *so, PyObject *other)
1609{
1610 if (!PyAnySet_Check(other))
1611 Py_RETURN_NOTIMPLEMENTED;
1612 if (set_difference_update_internal(so, other))
1613 return NULL;
1614 Py_INCREF(so);
1615 return (PyObject *)so;
1616}
1617
1618static PyObject *
1619set_symmetric_difference_update(PySetObject *so, PyObject *other)
1620{
1621 PySetObject *otherset;
1622 PyObject *key;
1623 Py_ssize_t pos = 0;
1624 Py_hash_t hash;
1625 setentry *entry;
1626 int rv;
1627
1628 if ((PyObject *)so == other)
1629 return set_clear(so, NULL);
1630
1631 if (PyDict_CheckExact(other)) {
1632 PyObject *value;
1633 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
1634 Py_INCREF(key);
1635 rv = set_discard_entry(so, key, hash);
1636 if (rv < 0) {
1637 Py_DECREF(key);
1638 return NULL;
1639 }
1640 if (rv == DISCARD_NOTFOUND) {
1641 if (set_add_entry(so, key, hash)) {
1642 Py_DECREF(key);
1643 return NULL;
1644 }
1645 }
1646 Py_DECREF(key);
1647 }
1648 Py_RETURN_NONE;
1649 }
1650
1651 if (PyAnySet_Check(other)) {
1652 Py_INCREF(other);
1653 otherset = (PySetObject *)other;
1654 } else {
1655 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1656 if (otherset == NULL)
1657 return NULL;
1658 }
1659
1660 while (set_next(otherset, &pos, &entry)) {
1661 key = entry->key;
1662 hash = entry->hash;
1663 Py_INCREF(key);
1664 rv = set_discard_entry(so, key, hash);
1665 if (rv < 0) {
1666 Py_DECREF(otherset);
1667 Py_DECREF(key);
1668 return NULL;
1669 }
1670 if (rv == DISCARD_NOTFOUND) {
1671 if (set_add_entry(so, key, hash)) {
1672 Py_DECREF(otherset);
1673 Py_DECREF(key);
1674 return NULL;
1675 }
1676 }
1677 Py_DECREF(key);
1678 }
1679 Py_DECREF(otherset);
1680 Py_RETURN_NONE;
1681}
1682
1683PyDoc_STRVAR(symmetric_difference_update_doc,
1684"Update a set with the symmetric difference of itself and another.");
1685
1686static PyObject *
1687set_symmetric_difference(PySetObject *so, PyObject *other)
1688{
1689 PyObject *rv;
1690 PySetObject *otherset;
1691
1692 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1693 if (otherset == NULL)
1694 return NULL;
1695 rv = set_symmetric_difference_update(otherset, (PyObject *)so);
1696 if (rv == NULL) {
1697 Py_DECREF(otherset);
1698 return NULL;
1699 }
1700 Py_DECREF(rv);
1701 return (PyObject *)otherset;
1702}
1703
1704PyDoc_STRVAR(symmetric_difference_doc,
1705"Return the symmetric difference of two sets as a new set.\n\
1706\n\
1707(i.e. all elements that are in exactly one of the sets.)");
1708
1709static PyObject *
1710set_xor(PySetObject *so, PyObject *other)
1711{
1712 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1713 Py_RETURN_NOTIMPLEMENTED;
1714 return set_symmetric_difference(so, other);
1715}
1716
1717static PyObject *
1718set_ixor(PySetObject *so, PyObject *other)
1719{
1720 PyObject *result;
1721
1722 if (!PyAnySet_Check(other))
1723 Py_RETURN_NOTIMPLEMENTED;
1724 result = set_symmetric_difference_update(so, other);
1725 if (result == NULL)
1726 return NULL;
1727 Py_DECREF(result);
1728 Py_INCREF(so);
1729 return (PyObject *)so;
1730}
1731
1732static PyObject *
1733set_issubset(PySetObject *so, PyObject *other)
1734{
1735 setentry *entry;
1736 Py_ssize_t pos = 0;
1737 int rv;
1738
1739 if (!PyAnySet_Check(other)) {
1740 PyObject *tmp, *result;
1741 tmp = make_new_set(&PySet_Type, other);
1742 if (tmp == NULL)
1743 return NULL;
1744 result = set_issubset(so, tmp);
1745 Py_DECREF(tmp);
1746 return result;
1747 }
1748 if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
1749 Py_RETURN_FALSE;
1750
1751 while (set_next(so, &pos, &entry)) {
1752 PyObject *key = entry->key;
1753 Py_INCREF(key);
1754 rv = set_contains_entry((PySetObject *)other, key, entry->hash);
1755 Py_DECREF(key);
1756 if (rv < 0) {
1757 return NULL;
1758 }
1759 if (!rv) {
1760 Py_RETURN_FALSE;
1761 }
1762 }
1763 Py_RETURN_TRUE;
1764}
1765
1766PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
1767
1768static PyObject *
1769set_issuperset(PySetObject *so, PyObject *other)
1770{
1771 PyObject *tmp, *result;
1772
1773 if (!PyAnySet_Check(other)) {
1774 tmp = make_new_set(&PySet_Type, other);
1775 if (tmp == NULL)
1776 return NULL;
1777 result = set_issuperset(so, tmp);
1778 Py_DECREF(tmp);
1779 return result;
1780 }
1781 return set_issubset((PySetObject *)other, (PyObject *)so);
1782}
1783
1784PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
1785
1786static PyObject *
1787set_richcompare(PySetObject *v, PyObject *w, int op)
1788{
1789 PyObject *r1;
1790 int r2;
1791
1792 if(!PyAnySet_Check(w))
1793 Py_RETURN_NOTIMPLEMENTED;
1794
1795 switch (op) {
1796 case Py_EQ:
1797 if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
1798 Py_RETURN_FALSE;
1799 if (v->hash != -1 &&
1800 ((PySetObject *)w)->hash != -1 &&
1801 v->hash != ((PySetObject *)w)->hash)
1802 Py_RETURN_FALSE;
1803 return set_issubset(v, w);
1804 case Py_NE:
1805 r1 = set_richcompare(v, w, Py_EQ);
1806 if (r1 == NULL)
1807 return NULL;
1808 r2 = PyObject_IsTrue(r1);
1809 Py_DECREF(r1);
1810 if (r2 < 0)
1811 return NULL;
1812 return PyBool_FromLong(!r2);
1813 case Py_LE:
1814 return set_issubset(v, w);
1815 case Py_GE:
1816 return set_issuperset(v, w);
1817 case Py_LT:
1818 if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))
1819 Py_RETURN_FALSE;
1820 return set_issubset(v, w);
1821 case Py_GT:
1822 if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
1823 Py_RETURN_FALSE;
1824 return set_issuperset(v, w);
1825 }
1826 Py_RETURN_NOTIMPLEMENTED;
1827}
1828
1829static PyObject *
1830set_add(PySetObject *so, PyObject *key)
1831{
1832 if (set_add_key(so, key))
1833 return NULL;
1834 Py_RETURN_NONE;
1835}
1836
1837PyDoc_STRVAR(add_doc,
1838"Add an element to a set.\n\
1839\n\
1840This has no effect if the element is already present.");
1841
1842static int
1843set_contains(PySetObject *so, PyObject *key)
1844{
1845 PyObject *tmpkey;
1846 int rv;
1847
1848 rv = set_contains_key(so, key);
1849 if (rv < 0) {
1850 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1851 return -1;
1852 PyErr_Clear();
1853 tmpkey = make_new_set(&PyFrozenSet_Type, key);
1854 if (tmpkey == NULL)
1855 return -1;
1856 rv = set_contains_key(so, tmpkey);
1857 Py_DECREF(tmpkey);
1858 }
1859 return rv;
1860}
1861
1862static PyObject *
1863set_direct_contains(PySetObject *so, PyObject *key)
1864{
1865 long result;
1866
1867 result = set_contains(so, key);
1868 if (result < 0)
1869 return NULL;
1870 return PyBool_FromLong(result);
1871}
1872
1873PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
1874
1875static PyObject *
1876set_remove(PySetObject *so, PyObject *key)
1877{
1878 PyObject *tmpkey;
1879 int rv;
1880
1881 rv = set_discard_key(so, key);
1882 if (rv < 0) {
1883 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1884 return NULL;
1885 PyErr_Clear();
1886 tmpkey = make_new_set(&PyFrozenSet_Type, key);
1887 if (tmpkey == NULL)
1888 return NULL;
1889 rv = set_discard_key(so, tmpkey);
1890 Py_DECREF(tmpkey);
1891 if (rv < 0)
1892 return NULL;
1893 }
1894
1895 if (rv == DISCARD_NOTFOUND) {
1896 _PyErr_SetKeyError(key);
1897 return NULL;
1898 }
1899 Py_RETURN_NONE;
1900}
1901
1902PyDoc_STRVAR(remove_doc,
1903"Remove an element from a set; it must be a member.\n\
1904\n\
1905If the element is not a member, raise a KeyError.");
1906
1907static PyObject *
1908set_discard(PySetObject *so, PyObject *key)
1909{
1910 PyObject *tmpkey;
1911 int rv;
1912
1913 rv = set_discard_key(so, key);
1914 if (rv < 0) {
1915 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1916 return NULL;
1917 PyErr_Clear();
1918 tmpkey = make_new_set(&PyFrozenSet_Type, key);
1919 if (tmpkey == NULL)
1920 return NULL;
1921 rv = set_discard_key(so, tmpkey);
1922 Py_DECREF(tmpkey);
1923 if (rv < 0)
1924 return NULL;
1925 }
1926 Py_RETURN_NONE;
1927}
1928
1929PyDoc_STRVAR(discard_doc,
1930"Remove an element from a set if it is a member.\n\
1931\n\
1932If the element is not a member, do nothing.");
1933
1934static PyObject *
1935set_reduce(PySetObject *so, PyObject *Py_UNUSED(ignored))
1936{
1937 PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;
1938 _Py_IDENTIFIER(__dict__);
1939
1940 keys = PySequence_List((PyObject *)so);
1941 if (keys == NULL)
1942 goto done;
1943 args = PyTuple_Pack(1, keys);
1944 if (args == NULL)
1945 goto done;
1946 if (_PyObject_LookupAttrId((PyObject *)so, &PyId___dict__, &dict) < 0) {
1947 goto done;
1948 }
1949 if (dict == NULL) {
1950 dict = Py_None;
1951 Py_INCREF(dict);
1952 }
1953 result = PyTuple_Pack(3, Py_TYPE(so), args, dict);
1954done:
1955 Py_XDECREF(args);
1956 Py_XDECREF(keys);
1957 Py_XDECREF(dict);
1958 return result;
1959}
1960
1961static PyObject *
1962set_sizeof(PySetObject *so, PyObject *Py_UNUSED(ignored))
1963{
1964 Py_ssize_t res;
1965
1966 res = _PyObject_SIZE(Py_TYPE(so));
1967 if (so->table != so->smalltable)
1968 res = res + (so->mask + 1) * sizeof(setentry);
1969 return PyLong_FromSsize_t(res);
1970}
1971
1972PyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes");
1973static int
1974set_init(PySetObject *self, PyObject *args, PyObject *kwds)
1975{
1976 PyObject *iterable = NULL;
1977
1978 if (!_PyArg_NoKeywords("set", kwds))
1979 return -1;
1980 if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable))
1981 return -1;
1982 if (self->fill)
1983 set_clear_internal(self);
1984 self->hash = -1;
1985 if (iterable == NULL)
1986 return 0;
1987 return set_update_internal(self, iterable);
1988}
1989
1990static PyObject*
1991set_vectorcall(PyObject *type, PyObject * const*args,
1992 size_t nargsf, PyObject *kwnames)
1993{
1994 assert(PyType_Check(type));
1995
1996 if (!_PyArg_NoKwnames("set", kwnames)) {
1997 return NULL;
1998 }
1999
2000 Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);
2001 if (!_PyArg_CheckPositional("set", nargs, 0, 1)) {
2002 return NULL;
2003 }
2004
2005 if (nargs) {
2006 return make_new_set((PyTypeObject *)type, args[0]);
2007 }
2008
2009 return make_new_set((PyTypeObject *)type, NULL);
2010}
2011
2012static PySequenceMethods set_as_sequence = {
2013 set_len, /* sq_length */
2014 0, /* sq_concat */
2015 0, /* sq_repeat */
2016 0, /* sq_item */
2017 0, /* sq_slice */
2018 0, /* sq_ass_item */
2019 0, /* sq_ass_slice */
2020 (objobjproc)set_contains, /* sq_contains */
2021};
2022
2023/* set object ********************************************************/
2024
2025#ifdef Py_DEBUG
2026static PyObject *test_c_api(PySetObject *so, PyObject *Py_UNUSED(ignored));
2027
2028PyDoc_STRVAR(test_c_api_doc, "Exercises C API. Returns True.\n\
2029All is well if assertions don't fail.");
2030#endif
2031
2032static PyMethodDef set_methods[] = {
2033 {"add", (PyCFunction)set_add, METH_O,
2034 add_doc},
2035 {"clear", (PyCFunction)set_clear, METH_NOARGS,
2036 clear_doc},
2037 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2038 contains_doc},
2039 {"copy", (PyCFunction)set_copy, METH_NOARGS,
2040 copy_doc},
2041 {"discard", (PyCFunction)set_discard, METH_O,
2042 discard_doc},
2043 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2044 difference_doc},
2045 {"difference_update", (PyCFunction)set_difference_update, METH_VARARGS,
2046 difference_update_doc},
2047 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2048 intersection_doc},
2049 {"intersection_update",(PyCFunction)set_intersection_update_multi, METH_VARARGS,
2050 intersection_update_doc},
2051 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2052 isdisjoint_doc},
2053 {"issubset", (PyCFunction)set_issubset, METH_O,
2054 issubset_doc},
2055 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2056 issuperset_doc},
2057 {"pop", (PyCFunction)set_pop, METH_NOARGS,
2058 pop_doc},
2059 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2060 reduce_doc},
2061 {"remove", (PyCFunction)set_remove, METH_O,
2062 remove_doc},
2063 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2064 sizeof_doc},
2065 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2066 symmetric_difference_doc},
2067 {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O,
2068 symmetric_difference_update_doc},
2069#ifdef Py_DEBUG
2070 {"test_c_api", (PyCFunction)test_c_api, METH_NOARGS,
2071 test_c_api_doc},
2072#endif
2073 {"union", (PyCFunction)set_union, METH_VARARGS,
2074 union_doc},
2075 {"update", (PyCFunction)set_update, METH_VARARGS,
2076 update_doc},
2077 {"__class_getitem__", (PyCFunction)Py_GenericAlias, METH_O|METH_CLASS, PyDoc_STR("See PEP 585")},
2078 {NULL, NULL} /* sentinel */
2079};
2080
2081static PyNumberMethods set_as_number = {
2082 0, /*nb_add*/
2083 (binaryfunc)set_sub, /*nb_subtract*/
2084 0, /*nb_multiply*/
2085 0, /*nb_remainder*/
2086 0, /*nb_divmod*/
2087 0, /*nb_power*/
2088 0, /*nb_negative*/
2089 0, /*nb_positive*/
2090 0, /*nb_absolute*/
2091 0, /*nb_bool*/
2092 0, /*nb_invert*/
2093 0, /*nb_lshift*/
2094 0, /*nb_rshift*/
2095 (binaryfunc)set_and, /*nb_and*/
2096 (binaryfunc)set_xor, /*nb_xor*/
2097 (binaryfunc)set_or, /*nb_or*/
2098 0, /*nb_int*/
2099 0, /*nb_reserved*/
2100 0, /*nb_float*/
2101 0, /*nb_inplace_add*/
2102 (binaryfunc)set_isub, /*nb_inplace_subtract*/
2103 0, /*nb_inplace_multiply*/
2104 0, /*nb_inplace_remainder*/
2105 0, /*nb_inplace_power*/
2106 0, /*nb_inplace_lshift*/
2107 0, /*nb_inplace_rshift*/
2108 (binaryfunc)set_iand, /*nb_inplace_and*/
2109 (binaryfunc)set_ixor, /*nb_inplace_xor*/
2110 (binaryfunc)set_ior, /*nb_inplace_or*/
2111};
2112
2113PyDoc_STRVAR(set_doc,
2114"set() -> new empty set object\n\
2115set(iterable) -> new set object\n\
2116\n\
2117Build an unordered collection of unique elements.");
2118
2119PyTypeObject PySet_Type = {
2120 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2121 "set", /* tp_name */
2122 sizeof(PySetObject), /* tp_basicsize */
2123 0, /* tp_itemsize */
2124 /* methods */
2125 (destructor)set_dealloc, /* tp_dealloc */
2126 0, /* tp_vectorcall_offset */
2127 0, /* tp_getattr */
2128 0, /* tp_setattr */
2129 0, /* tp_as_async */
2130 (reprfunc)set_repr, /* tp_repr */
2131 &set_as_number, /* tp_as_number */
2132 &set_as_sequence, /* tp_as_sequence */
2133 0, /* tp_as_mapping */
2134 PyObject_HashNotImplemented, /* tp_hash */
2135 0, /* tp_call */
2136 0, /* tp_str */
2137 PyObject_GenericGetAttr, /* tp_getattro */
2138 0, /* tp_setattro */
2139 0, /* tp_as_buffer */
2140 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2141 Py_TPFLAGS_BASETYPE |
2142 _Py_TPFLAGS_MATCH_SELF, /* tp_flags */
2143 set_doc, /* tp_doc */
2144 (traverseproc)set_traverse, /* tp_traverse */
2145 (inquiry)set_clear_internal, /* tp_clear */
2146 (richcmpfunc)set_richcompare, /* tp_richcompare */
2147 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2148 (getiterfunc)set_iter, /* tp_iter */
2149 0, /* tp_iternext */
2150 set_methods, /* tp_methods */
2151 0, /* tp_members */
2152 0, /* tp_getset */
2153 0, /* tp_base */
2154 0, /* tp_dict */
2155 0, /* tp_descr_get */
2156 0, /* tp_descr_set */
2157 0, /* tp_dictoffset */
2158 (initproc)set_init, /* tp_init */
2159 PyType_GenericAlloc, /* tp_alloc */
2160 set_new, /* tp_new */
2161 PyObject_GC_Del, /* tp_free */
2162 .tp_vectorcall = set_vectorcall,
2163};
2164
2165/* frozenset object ********************************************************/
2166
2167
2168static PyMethodDef frozenset_methods[] = {
2169 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2170 contains_doc},
2171 {"copy", (PyCFunction)frozenset_copy, METH_NOARGS,
2172 copy_doc},
2173 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2174 difference_doc},
2175 {"intersection", (PyCFunction)set_intersection_multi, METH_VARARGS,
2176 intersection_doc},
2177 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2178 isdisjoint_doc},
2179 {"issubset", (PyCFunction)set_issubset, METH_O,
2180 issubset_doc},
2181 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2182 issuperset_doc},
2183 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2184 reduce_doc},
2185 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2186 sizeof_doc},
2187 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2188 symmetric_difference_doc},
2189 {"union", (PyCFunction)set_union, METH_VARARGS,
2190 union_doc},
2191 {"__class_getitem__", (PyCFunction)Py_GenericAlias, METH_O|METH_CLASS, PyDoc_STR("See PEP 585")},
2192 {NULL, NULL} /* sentinel */
2193};
2194
2195static PyNumberMethods frozenset_as_number = {
2196 0, /*nb_add*/
2197 (binaryfunc)set_sub, /*nb_subtract*/
2198 0, /*nb_multiply*/
2199 0, /*nb_remainder*/
2200 0, /*nb_divmod*/
2201 0, /*nb_power*/
2202 0, /*nb_negative*/
2203 0, /*nb_positive*/
2204 0, /*nb_absolute*/
2205 0, /*nb_bool*/
2206 0, /*nb_invert*/
2207 0, /*nb_lshift*/
2208 0, /*nb_rshift*/
2209 (binaryfunc)set_and, /*nb_and*/
2210 (binaryfunc)set_xor, /*nb_xor*/
2211 (binaryfunc)set_or, /*nb_or*/
2212};
2213
2214PyDoc_STRVAR(frozenset_doc,
2215"frozenset() -> empty frozenset object\n\
2216frozenset(iterable) -> frozenset object\n\
2217\n\
2218Build an immutable unordered collection of unique elements.");
2219
2220PyTypeObject PyFrozenSet_Type = {
2221 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2222 "frozenset", /* tp_name */
2223 sizeof(PySetObject), /* tp_basicsize */
2224 0, /* tp_itemsize */
2225 /* methods */
2226 (destructor)set_dealloc, /* tp_dealloc */
2227 0, /* tp_vectorcall_offset */
2228 0, /* tp_getattr */
2229 0, /* tp_setattr */
2230 0, /* tp_as_async */
2231 (reprfunc)set_repr, /* tp_repr */
2232 &frozenset_as_number, /* tp_as_number */
2233 &set_as_sequence, /* tp_as_sequence */
2234 0, /* tp_as_mapping */
2235 frozenset_hash, /* tp_hash */
2236 0, /* tp_call */
2237 0, /* tp_str */
2238 PyObject_GenericGetAttr, /* tp_getattro */
2239 0, /* tp_setattro */
2240 0, /* tp_as_buffer */
2241 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2242 Py_TPFLAGS_BASETYPE |
2243 _Py_TPFLAGS_MATCH_SELF, /* tp_flags */
2244 frozenset_doc, /* tp_doc */
2245 (traverseproc)set_traverse, /* tp_traverse */
2246 (inquiry)set_clear_internal, /* tp_clear */
2247 (richcmpfunc)set_richcompare, /* tp_richcompare */
2248 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2249 (getiterfunc)set_iter, /* tp_iter */
2250 0, /* tp_iternext */
2251 frozenset_methods, /* tp_methods */
2252 0, /* tp_members */
2253 0, /* tp_getset */
2254 0, /* tp_base */
2255 0, /* tp_dict */
2256 0, /* tp_descr_get */
2257 0, /* tp_descr_set */
2258 0, /* tp_dictoffset */
2259 0, /* tp_init */
2260 PyType_GenericAlloc, /* tp_alloc */
2261 frozenset_new, /* tp_new */
2262 PyObject_GC_Del, /* tp_free */
2263 .tp_vectorcall = frozenset_vectorcall,
2264};
2265
2266
2267/***** C API functions *************************************************/
2268
2269PyObject *
2270PySet_New(PyObject *iterable)
2271{
2272 return make_new_set(&PySet_Type, iterable);
2273}
2274
2275PyObject *
2276PyFrozenSet_New(PyObject *iterable)
2277{
2278 return make_new_set(&PyFrozenSet_Type, iterable);
2279}
2280
2281Py_ssize_t
2282PySet_Size(PyObject *anyset)
2283{
2284 if (!PyAnySet_Check(anyset)) {
2285 PyErr_BadInternalCall();
2286 return -1;
2287 }
2288 return PySet_GET_SIZE(anyset);
2289}
2290
2291int
2292PySet_Clear(PyObject *set)
2293{
2294 if (!PySet_Check(set)) {
2295 PyErr_BadInternalCall();
2296 return -1;
2297 }
2298 return set_clear_internal((PySetObject *)set);
2299}
2300
2301int
2302PySet_Contains(PyObject *anyset, PyObject *key)
2303{
2304 if (!PyAnySet_Check(anyset)) {
2305 PyErr_BadInternalCall();
2306 return -1;
2307 }
2308 return set_contains_key((PySetObject *)anyset, key);
2309}
2310
2311int
2312PySet_Discard(PyObject *set, PyObject *key)
2313{
2314 if (!PySet_Check(set)) {
2315 PyErr_BadInternalCall();
2316 return -1;
2317 }
2318 return set_discard_key((PySetObject *)set, key);
2319}
2320
2321int
2322PySet_Add(PyObject *anyset, PyObject *key)
2323{
2324 if (!PySet_Check(anyset) &&
2325 (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
2326 PyErr_BadInternalCall();
2327 return -1;
2328 }
2329 return set_add_key((PySetObject *)anyset, key);
2330}
2331
2332int
2333_PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash)
2334{
2335 setentry *entry;
2336
2337 if (!PyAnySet_Check(set)) {
2338 PyErr_BadInternalCall();
2339 return -1;
2340 }
2341 if (set_next((PySetObject *)set, pos, &entry) == 0)
2342 return 0;
2343 *key = entry->key;
2344 *hash = entry->hash;
2345 return 1;
2346}
2347
2348PyObject *
2349PySet_Pop(PyObject *set)
2350{
2351 if (!PySet_Check(set)) {
2352 PyErr_BadInternalCall();
2353 return NULL;
2354 }
2355 return set_pop((PySetObject *)set, NULL);
2356}
2357
2358int
2359_PySet_Update(PyObject *set, PyObject *iterable)
2360{
2361 if (!PySet_Check(set)) {
2362 PyErr_BadInternalCall();
2363 return -1;
2364 }
2365 return set_update_internal((PySetObject *)set, iterable);
2366}
2367
2368/* Exported for the gdb plugin's benefit. */
2369PyObject *_PySet_Dummy = dummy;
2370
2371#ifdef Py_DEBUG
2372
2373/* Test code to be called with any three element set.
2374 Returns True and original set is restored. */
2375
2376#define assertRaises(call_return_value, exception) \
2377 do { \
2378 assert(call_return_value); \
2379 assert(PyErr_ExceptionMatches(exception)); \
2380 PyErr_Clear(); \
2381 } while(0)
2382
2383static PyObject *
2384test_c_api(PySetObject *so, PyObject *Py_UNUSED(ignored))
2385{
2386 Py_ssize_t count;
2387 const char *s;
2388 Py_ssize_t i;
2389 PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x=NULL;
2390 PyObject *ob = (PyObject *)so;
2391 Py_hash_t hash;
2392 PyObject *str;
2393
2394 /* Verify preconditions */
2395 assert(PyAnySet_Check(ob));
2396 assert(PyAnySet_CheckExact(ob));
2397 assert(!PyFrozenSet_CheckExact(ob));
2398
2399 /* so.clear(); so |= set("abc"); */
2400 str = PyUnicode_FromString("abc");
2401 if (str == NULL)
2402 return NULL;
2403 set_clear_internal(so);
2404 if (set_update_internal(so, str)) {
2405 Py_DECREF(str);
2406 return NULL;
2407 }
2408 Py_DECREF(str);
2409
2410 /* Exercise type/size checks */
2411 assert(PySet_Size(ob) == 3);
2412 assert(PySet_GET_SIZE(ob) == 3);
2413
2414 /* Raise TypeError for non-iterable constructor arguments */
2415 assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
2416 assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);
2417
2418 /* Raise TypeError for unhashable key */
2419 dup = PySet_New(ob);
2420 assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
2421 assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
2422 assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);
2423
2424 /* Exercise successful pop, contains, add, and discard */
2425 elem = PySet_Pop(ob);
2426 assert(PySet_Contains(ob, elem) == 0);
2427 assert(PySet_GET_SIZE(ob) == 2);
2428 assert(PySet_Add(ob, elem) == 0);
2429 assert(PySet_Contains(ob, elem) == 1);
2430 assert(PySet_GET_SIZE(ob) == 3);
2431 assert(PySet_Discard(ob, elem) == 1);
2432 assert(PySet_GET_SIZE(ob) == 2);
2433 assert(PySet_Discard(ob, elem) == 0);
2434 assert(PySet_GET_SIZE(ob) == 2);
2435
2436 /* Exercise clear */
2437 dup2 = PySet_New(dup);
2438 assert(PySet_Clear(dup2) == 0);
2439 assert(PySet_Size(dup2) == 0);
2440 Py_DECREF(dup2);
2441
2442 /* Raise SystemError on clear or update of frozen set */
2443 f = PyFrozenSet_New(dup);
2444 assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
2445 assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
2446 assert(PySet_Add(f, elem) == 0);
2447 Py_INCREF(f);
2448 assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
2449 Py_DECREF(f);
2450 Py_DECREF(f);
2451
2452 /* Exercise direct iteration */
2453 i = 0, count = 0;
2454 while (_PySet_NextEntry((PyObject *)dup, &i, &x, &hash)) {
2455 s = PyUnicode_AsUTF8(x);
2456 assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
2457 count++;
2458 }
2459 assert(count == 3);
2460
2461 /* Exercise updates */
2462 dup2 = PySet_New(NULL);
2463 assert(_PySet_Update(dup2, dup) == 0);
2464 assert(PySet_Size(dup2) == 3);
2465 assert(_PySet_Update(dup2, dup) == 0);
2466 assert(PySet_Size(dup2) == 3);
2467 Py_DECREF(dup2);
2468
2469 /* Raise SystemError when self argument is not a set or frozenset. */
2470 t = PyTuple_New(0);
2471 assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
2472 assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
2473 Py_DECREF(t);
2474
2475 /* Raise SystemError when self argument is not a set. */
2476 f = PyFrozenSet_New(dup);
2477 assert(PySet_Size(f) == 3);
2478 assert(PyFrozenSet_CheckExact(f));
2479 assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
2480 assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
2481 Py_DECREF(f);
2482
2483 /* Raise KeyError when popping from an empty set */
2484 assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
2485 Py_DECREF(ob);
2486 assert(PySet_GET_SIZE(ob) == 0);
2487 assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);
2488
2489 /* Restore the set from the copy using the PyNumber API */
2490 assert(PyNumber_InPlaceOr(ob, dup) == ob);
2491 Py_DECREF(ob);
2492
2493 /* Verify constructors accept NULL arguments */
2494 f = PySet_New(NULL);
2495 assert(f != NULL);
2496 assert(PySet_GET_SIZE(f) == 0);
2497 Py_DECREF(f);
2498 f = PyFrozenSet_New(NULL);
2499 assert(f != NULL);
2500 assert(PyFrozenSet_CheckExact(f));
2501 assert(PySet_GET_SIZE(f) == 0);
2502 Py_DECREF(f);
2503
2504 Py_DECREF(elem);
2505 Py_DECREF(dup);
2506 Py_RETURN_TRUE;
2507}
2508
2509#undef assertRaises
2510
2511#endif
2512
2513/***** Dummy Struct *************************************************/
2514
2515static PyObject *
2516dummy_repr(PyObject *op)
2517{
2518 return PyUnicode_FromString("<dummy key>");
2519}
2520
2521static void _Py_NO_RETURN
2522dummy_dealloc(PyObject* ignore)
2523{
2524 Py_FatalError("deallocating <dummy key>");
2525}
2526
2527static PyTypeObject _PySetDummy_Type = {
2528 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2529 "<dummy key> type",
2530 0,
2531 0,
2532 dummy_dealloc, /*tp_dealloc*/ /*never called*/
2533 0, /*tp_vectorcall_offset*/
2534 0, /*tp_getattr*/
2535 0, /*tp_setattr*/
2536 0, /*tp_as_async*/
2537 dummy_repr, /*tp_repr*/
2538 0, /*tp_as_number*/
2539 0, /*tp_as_sequence*/
2540 0, /*tp_as_mapping*/
2541 0, /*tp_hash */
2542 0, /*tp_call */
2543 0, /*tp_str */
2544 0, /*tp_getattro */
2545 0, /*tp_setattro */
2546 0, /*tp_as_buffer */
2547 Py_TPFLAGS_DEFAULT, /*tp_flags */
2548};
2549
2550static PyObject _dummy_struct = {
2551 _PyObject_EXTRA_INIT
2552 2, &_PySetDummy_Type
2553};
2554