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