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