Branch data 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 : 39969485 : set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
57 : : {
58 : : setentry *table;
59 : : setentry *entry;
60 : 39969485 : size_t perturb = hash;
61 : 39969485 : size_t mask = so->mask;
62 : 39969485 : size_t i = (size_t)hash & mask; /* Unsigned for defined overflow behavior */
63 : : int probes;
64 : : int cmp;
65 : :
66 : : while (1) {
67 : 42910992 : entry = &so->table[i];
68 [ + + ]: 42910992 : probes = (i + LINEAR_PROBES <= mask) ? LINEAR_PROBES: 0;
69 : : do {
70 [ + + + + ]: 77192582 : if (entry->hash == 0 && entry->key == NULL)
71 : 34386036 : return entry;
72 [ + + ]: 42806546 : if (entry->hash == hash) {
73 : 5617880 : PyObject *startkey = entry->key;
74 : : assert(startkey != dummy);
75 [ + + ]: 5617880 : if (startkey == key)
76 : 3893801 : return entry;
77 [ + + ]: 1724079 : if (PyUnicode_CheckExact(startkey)
78 [ + + ]: 634005 : && PyUnicode_CheckExact(key)
79 [ + - ]: 633923 : && _PyUnicode_EQ(startkey, key))
80 : 633923 : return entry;
81 : 1090156 : table = so->table;
82 : 1090156 : Py_INCREF(startkey);
83 : 1090156 : cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
84 : 1090156 : Py_DECREF(startkey);
85 [ + + ]: 1090156 : if (cmp < 0)
86 : 8 : return NULL;
87 [ + + + + ]: 1090148 : if (table != so->table || entry->key != startkey)
88 : 2729 : return set_lookkey(so, key, hash);
89 [ + + ]: 1087419 : if (cmp > 0)
90 : 1052988 : return entry;
91 : 34431 : mask = so->mask;
92 : : }
93 : 37223097 : entry++;
94 [ + + ]: 37223097 : } while (probes--);
95 : 2941507 : perturb >>= PERTURB_SHIFT;
96 : 2941507 : i = (i * 5 + 1 + perturb) & mask;
97 : : }
98 : : }
99 : :
100 : : static int set_table_resize(PySetObject *, Py_ssize_t);
101 : :
102 : : static int
103 : 23593493 : 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 : 23593493 : Py_INCREF(key);
117 : :
118 : 23593917 : restart:
119 : :
120 : 23593917 : mask = so->mask;
121 : 23593917 : i = (size_t)hash & mask;
122 : 23593917 : freeslot = NULL;
123 : 23593917 : perturb = hash;
124 : :
125 : : while (1) {
126 : 27908697 : entry = &so->table[i];
127 [ + + ]: 27908697 : probes = (i + LINEAR_PROBES <= mask) ? LINEAR_PROBES: 0;
128 : : do {
129 [ + + + + ]: 45312411 : if (entry->hash == 0 && entry->key == NULL)
130 : 21343992 : goto found_unused_or_dummy;
131 [ + + ]: 23968419 : if (entry->hash == hash) {
132 : 9319464 : PyObject *startkey = entry->key;
133 : : assert(startkey != dummy);
134 [ + + ]: 9319464 : if (startkey == key)
135 : 1689015 : goto found_active;
136 [ + + ]: 7630449 : if (PyUnicode_CheckExact(startkey)
137 [ + + ]: 111420 : && PyUnicode_CheckExact(key)
138 [ + - ]: 111287 : && _PyUnicode_EQ(startkey, key))
139 : 111287 : goto found_active;
140 : 7519162 : table = so->table;
141 : 7519162 : Py_INCREF(startkey);
142 : 7519162 : cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
143 : 7519162 : Py_DECREF(startkey);
144 [ + + ]: 7519162 : if (cmp > 0)
145 : 449192 : goto found_active;
146 [ + + ]: 7069970 : if (cmp < 0)
147 : 7 : goto comparison_error;
148 [ + + + + ]: 7069963 : if (table != so->table || entry->key != startkey)
149 : 424 : goto restart;
150 : 7069539 : mask = so->mask;
151 : : }
152 [ + + ]: 14648955 : else if (entry->hash == -1) {
153 : : assert (entry->key == dummy);
154 : 115133 : freeslot = entry;
155 : : }
156 : 21718494 : entry++;
157 [ + + ]: 21718494 : } while (probes--);
158 : 4314780 : perturb >>= PERTURB_SHIFT;
159 : 4314780 : i = (i * 5 + 1 + perturb) & mask;
160 : : }
161 : :
162 : 21343992 : found_unused_or_dummy:
163 [ + + ]: 21343992 : if (freeslot == NULL)
164 : 21279252 : goto found_unused;
165 : 64740 : so->used++;
166 : 64740 : freeslot->key = key;
167 : 64740 : freeslot->hash = hash;
168 : 64740 : return 0;
169 : :
170 : 21279252 : found_unused:
171 : 21279252 : so->fill++;
172 : 21279252 : so->used++;
173 : 21279252 : entry->key = key;
174 : 21279252 : entry->hash = hash;
175 [ + + ]: 21279252 : if ((size_t)so->fill*5 < mask*3)
176 : 19771673 : return 0;
177 [ + + ]: 1507579 : return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
178 : :
179 : 2249494 : found_active:
180 : 2249494 : Py_DECREF(key);
181 : 2249494 : 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 : 12730803 : set_insert_clean(setentry *table, size_t mask, PyObject *key, Py_hash_t hash)
198 : : {
199 : : setentry *entry;
200 : 12730803 : size_t perturb = hash;
201 : 12730803 : size_t i = (size_t)hash & mask;
202 : : size_t j;
203 : :
204 : : while (1) {
205 : 13205489 : entry = &table[i];
206 [ + + ]: 13205489 : if (entry->key == NULL)
207 : 11867675 : goto found_null;
208 [ + + ]: 1337814 : if (i + LINEAR_PROBES <= mask) {
209 [ + + ]: 5222253 : for (j = 0; j < LINEAR_PROBES; j++) {
210 : 4933010 : entry++;
211 [ + + ]: 4933010 : if (entry->key == NULL)
212 : 863128 : goto found_null;
213 : : }
214 : : }
215 : 474686 : perturb >>= PERTURB_SHIFT;
216 : 474686 : i = (i * 5 + 1 + perturb) & mask;
217 : : }
218 : 12730803 : found_null:
219 : 12730803 : entry->key = key;
220 : 12730803 : entry->hash = hash;
221 : 12730803 : }
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 : 1725945 : set_table_resize(PySetObject *so, Py_ssize_t minused)
233 : : {
234 : : setentry *oldtable, *newtable, *entry;
235 : 1725945 : Py_ssize_t oldmask = so->mask;
236 : : size_t newmask;
237 : : int is_oldtable_malloced;
238 : : setentry small_copy[PySet_MINSIZE];
239 : :
240 : : assert(minused >= 0);
241 : :
242 : : /* Find the smallest table size > minused. */
243 : : /* XXX speed-up with intrinsics */
244 : 1725945 : size_t newsize = PySet_MINSIZE;
245 [ + + ]: 5367561 : while (newsize <= (size_t)minused) {
246 : 3641616 : newsize <<= 1; // The largest possible value is PY_SSIZE_T_MAX + 1.
247 : : }
248 : :
249 : : /* Get space for a new table. */
250 : 1725945 : oldtable = so->table;
251 : : assert(oldtable != NULL);
252 : 1725945 : is_oldtable_malloced = oldtable != so->smalltable;
253 : :
254 [ + + ]: 1725945 : if (newsize == PySet_MINSIZE) {
255 : : /* A large table is shrinking, or we can't get any smaller. */
256 : 1771 : newtable = so->smalltable;
257 [ + + ]: 1771 : if (newtable == oldtable) {
258 [ - + ]: 1536 : 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 : : assert(so->fill > so->used);
269 : 1536 : memcpy(small_copy, oldtable, sizeof(small_copy));
270 : 1536 : oldtable = small_copy;
271 : : }
272 : : }
273 : : else {
274 [ + - ]: 1724174 : newtable = PyMem_NEW(setentry, newsize);
275 [ - + ]: 1724174 : if (newtable == NULL) {
276 : : PyErr_NoMemory();
277 : 0 : return -1;
278 : : }
279 : : }
280 : :
281 : : /* Make the set empty, using the new table. */
282 : : assert(newtable != oldtable);
283 : 1725945 : memset(newtable, 0, sizeof(setentry) * newsize);
284 : 1725945 : so->mask = newsize - 1;
285 : 1725945 : 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 : 1725945 : newmask = (size_t)so->mask;
290 [ + + ]: 1725945 : if (so->fill == so->used) {
291 [ + + ]: 22044531 : for (entry = oldtable; entry <= oldtable + oldmask; entry++) {
292 [ + + ]: 20321088 : if (entry->key != NULL) {
293 : 11557338 : set_insert_clean(newtable, newmask, entry->key, entry->hash);
294 : : }
295 : : }
296 : : } else {
297 : 2502 : so->fill = so->used;
298 [ + + ]: 68886 : for (entry = oldtable; entry <= oldtable + oldmask; entry++) {
299 [ + + + + ]: 66384 : if (entry->key != NULL && entry->key != dummy) {
300 : 9612 : set_insert_clean(newtable, newmask, entry->key, entry->hash);
301 : : }
302 : : }
303 : : }
304 : :
305 [ + + ]: 1725945 : if (is_oldtable_malloced)
306 : 90731 : PyMem_Free(oldtable);
307 : 1725945 : return 0;
308 : : }
309 : :
310 : : static int
311 : 38158871 : set_contains_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
312 : : {
313 : : setentry *entry;
314 : :
315 : 38158871 : entry = set_lookkey(so, key, hash);
316 [ + + ]: 38158871 : if (entry != NULL)
317 : 38158867 : 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 : 1807885 : set_discard_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
326 : : {
327 : : setentry *entry;
328 : : PyObject *old_key;
329 : :
330 : 1807885 : entry = set_lookkey(so, key, hash);
331 [ + + ]: 1807885 : if (entry == NULL)
332 : 4 : return -1;
333 [ + + ]: 1807881 : if (entry->key == NULL)
334 : 1650352 : return DISCARD_NOTFOUND;
335 : 157529 : old_key = entry->key;
336 : 157529 : entry->key = dummy;
337 : 157529 : entry->hash = -1;
338 : 157529 : so->used--;
339 : 157529 : Py_DECREF(old_key);
340 : 157529 : return DISCARD_FOUND;
341 : : }
342 : :
343 : : static int
344 : 22789659 : set_add_key(PySetObject *so, PyObject *key)
345 : : {
346 : : Py_hash_t hash;
347 : :
348 [ + + ]: 22789659 : if (!PyUnicode_CheckExact(key) ||
349 [ + + ]: 7762866 : (hash = _PyASCIIObject_CAST(key)->hash) == -1) {
350 : 18643169 : hash = PyObject_Hash(key);
351 [ + + ]: 18643169 : if (hash == -1)
352 : 23 : return -1;
353 : : }
354 : 22789636 : return set_add_entry(so, key, hash);
355 : : }
356 : :
357 : : static int
358 : 36882032 : set_contains_key(PySetObject *so, PyObject *key)
359 : : {
360 : : Py_hash_t hash;
361 : :
362 [ + + ]: 36882032 : if (!PyUnicode_CheckExact(key) ||
363 [ + + ]: 32642323 : (hash = _PyASCIIObject_CAST(key)->hash) == -1) {
364 : 13371158 : hash = PyObject_Hash(key);
365 [ + + ]: 13371158 : if (hash == -1)
366 : 14 : return -1;
367 : : }
368 : 36882018 : return set_contains_entry(so, key, hash);
369 : : }
370 : :
371 : : static int
372 : 1744583 : set_discard_key(PySetObject *so, PyObject *key)
373 : : {
374 : : Py_hash_t hash;
375 : :
376 [ + + ]: 1744583 : if (!PyUnicode_CheckExact(key) ||
377 [ + + ]: 1621550 : (hash = _PyASCIIObject_CAST(key)->hash) == -1) {
378 : 125784 : hash = PyObject_Hash(key);
379 [ + + ]: 125784 : if (hash == -1)
380 : 20 : return -1;
381 : : }
382 : 1744563 : return set_discard_entry(so, key, hash);
383 : : }
384 : :
385 : : static void
386 : 53640 : set_empty_to_minsize(PySetObject *so)
387 : : {
388 : 53640 : memset(so->smalltable, 0, sizeof(so->smalltable));
389 : 53640 : so->fill = 0;
390 : 53640 : so->used = 0;
391 : 53640 : so->mask = PySet_MINSIZE - 1;
392 : 53640 : so->table = so->smalltable;
393 : 53640 : so->hash = -1;
394 : 53640 : }
395 : :
396 : : static int
397 : 57531 : set_clear_internal(PySetObject *so)
398 : : {
399 : : setentry *entry;
400 : 57531 : setentry *table = so->table;
401 : 57531 : Py_ssize_t fill = so->fill;
402 : 57531 : Py_ssize_t used = so->used;
403 : 57531 : int table_is_malloced = table != so->smalltable;
404 : : setentry small_copy[PySet_MINSIZE];
405 : :
406 : : assert (PyAnySet_Check(so));
407 : : assert(table != NULL);
408 : :
409 : : /* This is delicate. During the process of clearing the set,
410 : : * decrefs can cause the set to mutate. To avoid fatal confusion
411 : : * (voice of experience), we have to make the set empty before
412 : : * clearing the slots, and never refer to anything via so->ref while
413 : : * clearing.
414 : : */
415 [ + + ]: 57531 : if (table_is_malloced)
416 : 11926 : set_empty_to_minsize(so);
417 : :
418 [ + + ]: 45605 : 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 : 41714 : memcpy(small_copy, table, sizeof(small_copy));
424 : 41714 : table = small_copy;
425 : 41714 : 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 [ + + ]: 789675 : for (entry = table; used > 0; entry++) {
434 [ + + + + ]: 732144 : if (entry->key && entry->key != dummy) {
435 : 359817 : used--;
436 : 359817 : Py_DECREF(entry->key);
437 : : }
438 : : }
439 : :
440 [ + + ]: 57531 : if (table_is_malloced)
441 : 11926 : PyMem_Free(table);
442 : 57531 : 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 : 109839916 : 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 : : assert (PyAnySet_Check(so));
466 : 109839916 : i = *pos_ptr;
467 : : assert(i >= 0);
468 : 109839916 : mask = so->mask;
469 : 109839916 : entry = &so->table[i];
470 [ + + + + : 373160181 : while (i <= mask && (entry->key == NULL || entry->key == dummy)) {
+ + ]
471 : 263320265 : i++;
472 : 263320265 : entry++;
473 : : }
474 : 109839916 : *pos_ptr = i+1;
475 [ + + ]: 109839916 : if (i > mask)
476 : 10579259 : return 0;
477 : : assert(entry != NULL);
478 : 99260657 : *entry_ptr = entry;
479 : 99260657 : return 1;
480 : : }
481 : :
482 : : static void
483 : 6282002 : set_dealloc(PySetObject *so)
484 : : {
485 : : setentry *entry;
486 : 6282002 : Py_ssize_t used = so->used;
487 : :
488 : : /* bpo-31095: UnTrack is needed before calling any callbacks */
489 : 6282002 : PyObject_GC_UnTrack(so);
490 [ + + + + ]: 6282002 : Py_TRASHCAN_BEGIN(so, set_dealloc)
491 [ + + ]: 6282000 : if (so->weakreflist != NULL)
492 : 102 : PyObject_ClearWeakRefs((PyObject *) so);
493 : :
494 [ + + ]: 73167741 : for (entry = so->table; used > 0; entry++) {
495 [ + + + + ]: 66885741 : if (entry->key && entry->key != dummy) {
496 : 24291422 : used--;
497 : 24291422 : Py_DECREF(entry->key);
498 : : }
499 : : }
500 [ + + ]: 6282000 : if (so->table != so->smalltable)
501 : 1620997 : PyMem_Free(so->table);
502 : 6282000 : Py_TYPE(so)->tp_free(so);
503 [ + + ]: 6282000 : Py_TRASHCAN_END
504 : 6282002 : }
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 : 203 : Py_ReprLeave((PyObject*)so);
521 : 203 : return PyUnicode_FromFormat("%s()", Py_TYPE(so)->tp_name);
522 : : }
523 : :
524 : 994 : keys = PySequence_List((PyObject *)so);
525 [ - + ]: 994 : if (keys == NULL)
526 : 0 : goto done;
527 : :
528 : : /* repr(keys)[1:-1] */
529 : 994 : listrepr = PyObject_Repr(keys);
530 : 994 : Py_DECREF(keys);
531 [ - + ]: 994 : if (listrepr == NULL)
532 : 0 : goto done;
533 : 994 : tmp = PyUnicode_Substring(listrepr, 1, PyUnicode_GET_LENGTH(listrepr)-1);
534 : 994 : Py_DECREF(listrepr);
535 [ - + ]: 994 : if (tmp == NULL)
536 : 0 : goto done;
537 : 994 : listrepr = tmp;
538 : :
539 [ + + ]: 994 : if (!PySet_CheckExact(so))
540 : 677 : result = PyUnicode_FromFormat("%s({%U})",
541 : 677 : Py_TYPE(so)->tp_name,
542 : : listrepr);
543 : : else
544 : 317 : result = PyUnicode_FromFormat("{%U}", listrepr);
545 : 994 : Py_DECREF(listrepr);
546 : 994 : done:
547 : 994 : Py_ReprLeave((PyObject*)so);
548 : 994 : return result;
549 : : }
550 : :
551 : : static Py_ssize_t
552 : 1314617 : set_len(PyObject *so)
553 : : {
554 : 1314617 : return ((PySetObject *)so)->used;
555 : : }
556 : :
557 : : static int
558 : 3530331 : 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 : : assert (PyAnySet_Check(so));
567 : : assert (PyAnySet_Check(otherset));
568 : :
569 : 3530331 : other = (PySetObject*)otherset;
570 [ + + + + ]: 3530331 : if (other == so || other->used == 0)
571 : : /* a.update(a) or a.update(set()); nothing to do */
572 : 2586391 : 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 [ + + ]: 943940 : if ((so->fill + other->used)*5 >= so->mask*3) {
578 [ - + ]: 213558 : if (set_table_resize(so, (so->used + other->used)*2) != 0)
579 : 0 : return -1;
580 : : }
581 : 943940 : so_entry = so->table;
582 : 943940 : 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 [ + + + + : 943940 : if (so->fill == 0 && so->mask == other->mask && other->fill == other->used) {
+ + ]
587 [ + + ]: 9263763 : for (i = 0; i <= other->mask; i++, so_entry++, other_entry++) {
588 : 8626280 : key = other_entry->key;
589 [ + + ]: 8626280 : if (key != NULL) {
590 : : assert(so_entry->key == NULL);
591 : 2344884 : Py_INCREF(key);
592 : 2344884 : so_entry->key = key;
593 : 2344884 : so_entry->hash = other_entry->hash;
594 : : }
595 : : }
596 : 637483 : so->fill = other->fill;
597 : 637483 : so->used = other->used;
598 : 637483 : return 0;
599 : : }
600 : :
601 : : /* If our table is empty, we can use set_insert_clean() */
602 [ + + ]: 306457 : if (so->fill == 0) {
603 : 72240 : setentry *newtable = so->table;
604 : 72240 : size_t newmask = (size_t)so->mask;
605 : 72240 : so->fill = other->used;
606 : 72240 : so->used = other->used;
607 [ + + ]: 3664816 : for (i = other->mask + 1; i > 0 ; i--, other_entry++) {
608 : 3592576 : key = other_entry->key;
609 [ + + + + ]: 3592576 : if (key != NULL && key != dummy) {
610 : 1163853 : Py_INCREF(key);
611 : 1163853 : set_insert_clean(newtable, newmask, key, other_entry->hash);
612 : : }
613 : : }
614 : 72240 : return 0;
615 : : }
616 : :
617 : : /* We can't assure there are no duplicates, so do normal insertions */
618 [ + + ]: 3097210 : for (i = 0; i <= other->mask; i++) {
619 : 2862994 : other_entry = &other->table[i];
620 : 2862994 : key = other_entry->key;
621 [ + + + + ]: 2862994 : if (key != NULL && key != dummy) {
622 [ + + ]: 698227 : if (set_add_entry(so, key, other_entry->hash))
623 : 1 : return -1;
624 : : }
625 : : }
626 : 234216 : return 0;
627 : : }
628 : :
629 : : static PyObject *
630 : 24362 : set_pop(PySetObject *so, PyObject *Py_UNUSED(ignored))
631 : : {
632 : : /* Make sure the search finger is in bounds */
633 : 24362 : setentry *entry = so->table + (so->finger & so->mask);
634 : 24362 : setentry *limit = so->table + so->mask;
635 : : PyObject *key;
636 : :
637 [ + + ]: 24362 : if (so->used == 0) {
638 : 3 : PyErr_SetString(PyExc_KeyError, "pop from an empty set");
639 : 3 : return NULL;
640 : : }
641 [ + + - + ]: 125553 : while (entry->key == NULL || entry->key==dummy) {
642 : 76835 : entry++;
643 [ + - ]: 76835 : if (entry > limit)
644 : 0 : entry = so->table;
645 : : }
646 : 24359 : key = entry->key;
647 : 24359 : entry->key = dummy;
648 : 24359 : entry->hash = -1;
649 : 24359 : so->used--;
650 : 24359 : so->finger = entry - so->table + 1; /* next place to start */
651 : 24359 : 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 : 10396936 : set_traverse(PySetObject *so, visitproc visit, void *arg)
659 : : {
660 : 10396936 : Py_ssize_t pos = 0;
661 : : setentry *entry;
662 : :
663 [ + + ]: 118670127 : while (set_next(so, &pos, &entry))
664 [ - + - + ]: 97876255 : Py_VISIT(entry->key);
665 : 10396936 : 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 : 33594002 : _shuffle_bits(Py_uhash_t h)
675 : : {
676 : 33594002 : 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 : 5290311 : frozenset_hash(PyObject *self)
687 : : {
688 : 5290311 : PySetObject *so = (PySetObject *)self;
689 : 5290311 : Py_uhash_t hash = 0;
690 : : setentry *entry;
691 : :
692 [ + + ]: 5290311 : if (so->hash != -1)
693 : 4213319 : 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 [ + + ]: 34134784 : for (entry = so->table; entry <= &so->table[so->mask]; entry++)
706 : 33057792 : hash ^= _shuffle_bits(entry->hash);
707 : :
708 : : /* Remove the effect of an odd number of NULL entries */
709 [ + + ]: 1076992 : if ((so->mask + 1 - so->fill) & 1)
710 : 536150 : hash ^= _shuffle_bits(0);
711 : :
712 : : /* Remove the effect of an odd number of dummy entries */
713 [ + + ]: 1076992 : if ((so->fill - so->used) & 1)
714 : 60 : hash ^= _shuffle_bits(-1);
715 : :
716 : : /* Factor in the number of active entries */
717 : 1076992 : hash ^= ((Py_uhash_t)PySet_GET_SIZE(self) + 1) * 1927868237UL;
718 : :
719 : : /* Disperse patterns arising in nested frozensets */
720 : 1076992 : hash ^= (hash >> 11) ^ (hash >> 25);
721 : 1076992 : hash = hash * 69069U + 907133923UL;
722 : :
723 : : /* -1 is reserved as an error code */
724 [ - + ]: 1076992 : if (hash == (Py_uhash_t)-1)
725 : 0 : hash = 590923713UL;
726 : :
727 : 1076992 : so->hash = hash;
728 : 1076992 : 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 : 770977 : setiter_dealloc(setiterobject *si)
743 : : {
744 : : /* bpo-31095: UnTrack is needed before calling any callbacks */
745 : 770977 : _PyObject_GC_UNTRACK(si);
746 : 770977 : Py_XDECREF(si->si_set);
747 : 770977 : PyObject_GC_Del(si);
748 : 770977 : }
749 : :
750 : : static int
751 : 866 : setiter_traverse(setiterobject *si, visitproc visit, void *arg)
752 : : {
753 [ + + - + ]: 866 : Py_VISIT(si->si_set);
754 : 866 : return 0;
755 : : }
756 : :
757 : : static PyObject *
758 : 8343 : setiter_len(setiterobject *si, PyObject *Py_UNUSED(ignored))
759 : : {
760 : 8343 : Py_ssize_t len = 0;
761 [ + + + + ]: 8343 : if (si->si_set != NULL && si->si_used == si->si_set->used)
762 : 8341 : len = si->len;
763 : 8343 : 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 : 2522201 : static PyObject *setiter_iternext(setiterobject *si)
795 : : {
796 : : PyObject *key;
797 : : Py_ssize_t i, mask;
798 : : setentry *entry;
799 : 2522201 : PySetObject *so = si->si_set;
800 : :
801 [ + + ]: 2522201 : if (so == NULL)
802 : 4 : return NULL;
803 : : assert (PyAnySet_Check(so));
804 : :
805 [ + + ]: 2522197 : if (si->si_used != so->used) {
806 : 5 : PyErr_SetString(PyExc_RuntimeError,
807 : : "Set changed size during iteration");
808 : 5 : si->si_used = -1; /* Make this state sticky */
809 : 5 : return NULL;
810 : : }
811 : :
812 : 2522192 : i = si->si_pos;
813 : : assert(i>=0);
814 : 2522192 : entry = so->table;
815 : 2522192 : mask = so->mask;
816 [ + + + + : 12028643 : while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
+ + ]
817 : 9506451 : i++;
818 : 2522192 : si->si_pos = i+1;
819 [ + + ]: 2522192 : if (i > mask)
820 : 765988 : goto fail;
821 : 1756204 : si->len--;
822 : 1756204 : key = entry[i].key;
823 : 1756204 : Py_INCREF(key);
824 : 1756204 : return key;
825 : :
826 : 765988 : fail:
827 : 765988 : si->si_set = NULL;
828 : 765988 : Py_DECREF(so);
829 : 765988 : 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 : 770977 : set_iter(PySetObject *so)
867 : : {
868 : 770977 : setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type);
869 [ - + ]: 770977 : if (si == NULL)
870 : 0 : return NULL;
871 : 770977 : Py_INCREF(so);
872 : 770977 : si->si_set = so;
873 : 770977 : si->si_used = so->used;
874 : 770977 : si->si_pos = 0;
875 : 770977 : si->len = so->used;
876 : 770977 : _PyObject_GC_TRACK(si);
877 : 770977 : return (PyObject *)si;
878 : : }
879 : :
880 : : static int
881 : 5325916 : set_update_internal(PySetObject *so, PyObject *other)
882 : : {
883 : : PyObject *key, *it;
884 : :
885 [ + + + + : 5325916 : if (PyAnySet_Check(other))
+ + + + ]
886 : 3530331 : return set_merge(so, other);
887 : :
888 [ + + ]: 1795585 : if (PyDict_CheckExact(other)) {
889 : : PyObject *value;
890 : 23068 : Py_ssize_t pos = 0;
891 : : Py_hash_t hash;
892 : 23068 : 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 [ - + ]: 23068 : if (dictsize < 0)
899 : 0 : return -1;
900 [ + + ]: 23068 : if ((so->fill + dictsize)*5 >= so->mask*3) {
901 [ - + ]: 3056 : if (set_table_resize(so, (so->used + dictsize)*2) != 0)
902 : 0 : return -1;
903 : : }
904 [ + + ]: 70451 : while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
905 [ - + ]: 47383 : if (set_add_entry(so, key, hash))
906 : 0 : return -1;
907 : : }
908 : 23068 : return 0;
909 : : }
910 : :
911 : 1772517 : it = PyObject_GetIter(other);
912 [ + + ]: 1772517 : if (it == NULL)
913 : 83 : return -1;
914 : :
915 [ + + ]: 19320748 : while ((key = PyIter_Next(it)) != NULL) {
916 [ + + ]: 17548338 : if (set_add_key(so, key)) {
917 : 24 : Py_DECREF(it);
918 : 24 : Py_DECREF(key);
919 : 24 : return -1;
920 : : }
921 : 17548314 : Py_DECREF(key);
922 : : }
923 : 1772410 : Py_DECREF(it);
924 [ + + ]: 1772410 : if (PyErr_Occurred())
925 : 55 : return -1;
926 : 1772355 : return 0;
927 : : }
928 : :
929 : : static PyObject *
930 : 3461 : set_update(PySetObject *so, PyObject *args)
931 : : {
932 : : Py_ssize_t i;
933 : :
934 [ + + ]: 6957 : for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
935 : 3521 : PyObject *other = PyTuple_GET_ITEM(args, i);
936 [ + + ]: 3521 : if (set_update_internal(so, other))
937 : 25 : return NULL;
938 : : }
939 : 3436 : 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 : 6285690 : make_new_set(PyTypeObject *type, PyObject *iterable)
953 : : {
954 : : assert(PyType_Check(type));
955 : : PySetObject *so;
956 : :
957 : 6285690 : so = (PySetObject *)type->tp_alloc(type, 0);
958 [ + + ]: 6285690 : if (so == NULL)
959 : 34 : return NULL;
960 : :
961 : 6285656 : so->fill = 0;
962 : 6285656 : so->used = 0;
963 : 6285656 : so->mask = PySet_MINSIZE - 1;
964 : 6285656 : so->table = so->smalltable;
965 : 6285656 : so->hash = -1;
966 : 6285656 : so->finger = 0;
967 : 6285656 : so->weakreflist = NULL;
968 : :
969 [ + + ]: 6285656 : if (iterable != NULL) {
970 [ + + ]: 2876815 : if (set_update_internal(so, iterable)) {
971 : 102 : Py_DECREF(so);
972 : 102 : return NULL;
973 : : }
974 : : }
975 : :
976 : 6285554 : return (PyObject *)so;
977 : : }
978 : :
979 : : static PyObject *
980 : 127448 : make_new_set_basetype(PyTypeObject *type, PyObject *iterable)
981 : : {
982 [ + + + + ]: 127448 : if (type != &PySet_Type && type != &PyFrozenSet_Type) {
983 [ + + ]: 2393 : if (PyType_IsSubtype(type, &PySet_Type))
984 : 2240 : type = &PySet_Type;
985 : : else
986 : 153 : type = &PyFrozenSet_Type;
987 : : }
988 : 127448 : return make_new_set(type, iterable);
989 : : }
990 : :
991 : : static PyObject *
992 : 1105018 : make_new_frozenset(PyTypeObject *type, PyObject *iterable)
993 : : {
994 [ + + ]: 1105018 : if (type != &PyFrozenSet_Type) {
995 : 744 : return make_new_set(type, iterable);
996 : : }
997 : :
998 [ + + + + ]: 1104274 : if (iterable != NULL && PyFrozenSet_CheckExact(iterable)) {
999 : : /* frozenset(f) is idempotent */
1000 : 33 : Py_INCREF(iterable);
1001 : 33 : return iterable;
1002 : : }
1003 : 1104241 : 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 : 1104275 : frozenset_vectorcall(PyObject *type, PyObject * const*args,
1026 : : size_t nargsf, PyObject *kwnames)
1027 : : {
1028 [ - + - - ]: 1104275 : if (!_PyArg_NoKwnames("frozenset", kwnames)) {
1029 : 0 : return NULL;
1030 : : }
1031 : :
1032 : 1104275 : Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);
1033 [ + - + + : 1104275 : if (!_PyArg_CheckPositional("frozenset", nargs, 0, 1)) {
+ - ]
1034 : 1 : return NULL;
1035 : : }
1036 : :
1037 [ + + ]: 1104274 : PyObject *iterable = (nargs ? args[0] : NULL);
1038 : 1104274 : 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 : 621 : u = b->smalltable;
1073 : 1145 : a->table = b->table;
1074 [ + + ]: 1145 : if (b->table == b->smalltable)
1075 : 1073 : a->table = a->smalltable;
1076 : 1145 : b->table = u;
1077 : :
1078 [ + + + + ]: 1145 : if (a->table == a->smalltable || b->table == b->smalltable) {
1079 : 1108 : memcpy(tab, a->smalltable, sizeof(tab));
1080 : 1108 : memcpy(a->smalltable, b->smalltable, sizeof(tab));
1081 : 1108 : 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 : 34732 : set_copy(PySetObject *so, PyObject *Py_UNUSED(ignored))
1095 : : {
1096 : 34732 : 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 : 12273 : set_clear(PySetObject *so, PyObject *Py_UNUSED(ignored))
1113 : : {
1114 : 12273 : set_clear_internal(so);
1115 : 12273 : Py_RETURN_NONE;
1116 : : }
1117 : :
1118 : : PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
1119 : :
1120 : : static PyObject *
1121 : 1297 : set_union(PySetObject *so, PyObject *args)
1122 : : {
1123 : : PySetObject *result;
1124 : : PyObject *other;
1125 : : Py_ssize_t i;
1126 : :
1127 : 1297 : result = (PySetObject *)set_copy(so, NULL);
1128 [ - + ]: 1297 : if (result == NULL)
1129 : 0 : return NULL;
1130 : :
1131 [ + + ]: 2617 : for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1132 : 1348 : other = PyTuple_GET_ITEM(args, i);
1133 [ + + ]: 1348 : if ((PyObject *)so == other)
1134 : 5 : continue;
1135 [ + + ]: 1343 : if (set_update_internal(result, other)) {
1136 : 28 : Py_DECREF(result);
1137 : 28 : return NULL;
1138 : : }
1139 : : }
1140 : 1269 : 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 : 27290 : set_or(PySetObject *so, PyObject *other)
1150 : : {
1151 : : PySetObject *result;
1152 : :
1153 [ + + + + : 27290 : if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
+ + + + +
+ + + + +
+ - ]
1154 : 25 : Py_RETURN_NOTIMPLEMENTED;
1155 : :
1156 : 27265 : result = (PySetObject *)set_copy(so, NULL);
1157 [ - + ]: 27265 : if (result == NULL)
1158 : 0 : return NULL;
1159 [ + + ]: 27265 : if ((PyObject *)so == other)
1160 : 7 : return (PyObject *)result;
1161 [ - + ]: 27258 : if (set_update_internal(result, other)) {
1162 : 0 : Py_DECREF(result);
1163 : 0 : return NULL;
1164 : : }
1165 : 27258 : return (PyObject *)result;
1166 : : }
1167 : :
1168 : : static PyObject *
1169 : 2398129 : set_ior(PySetObject *so, PyObject *other)
1170 : : {
1171 [ + + + - : 2398129 : if (!PyAnySet_Check(other))
+ + + - ]
1172 : 6 : Py_RETURN_NOTIMPLEMENTED;
1173 : :
1174 [ - + ]: 2398123 : if (set_update_internal(so, other))
1175 : 0 : return NULL;
1176 : 2398123 : Py_INCREF(so);
1177 : 2398123 : return (PyObject *)so;
1178 : : }
1179 : :
1180 : : static PyObject *
1181 : 38147 : 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 [ + + ]: 38147 : if ((PyObject *)so == other)
1189 : 9 : return set_copy(so, NULL);
1190 : :
1191 : 38138 : result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL);
1192 [ - + ]: 38138 : if (result == NULL)
1193 : 0 : return NULL;
1194 : :
1195 [ + + + + : 38138 : if (PyAnySet_Check(other)) {
+ + - + ]
1196 : 34490 : Py_ssize_t pos = 0;
1197 : : setentry *entry;
1198 : :
1199 [ + + ]: 34490 : if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1200 : 16747 : tmp = (PyObject *)so;
1201 : 16747 : so = (PySetObject *)other;
1202 : 16747 : other = tmp;
1203 : : }
1204 : :
1205 [ + + ]: 87351 : while (set_next((PySetObject *)other, &pos, &entry)) {
1206 : 52861 : key = entry->key;
1207 : 52861 : hash = entry->hash;
1208 : 52861 : Py_INCREF(key);
1209 : 52861 : rv = set_contains_entry(so, key, hash);
1210 [ - + ]: 52861 : if (rv < 0) {
1211 : 0 : Py_DECREF(result);
1212 : 0 : Py_DECREF(key);
1213 : 0 : return NULL;
1214 : : }
1215 [ + + ]: 52861 : if (rv) {
1216 [ - + ]: 9633 : if (set_add_entry(result, key, hash)) {
1217 : 0 : Py_DECREF(result);
1218 : 0 : Py_DECREF(key);
1219 : 0 : return NULL;
1220 : : }
1221 : : }
1222 : 52861 : Py_DECREF(key);
1223 : : }
1224 : 34490 : 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 [ + + ]: 81267 : while ((key = PyIter_Next(it)) != NULL) {
1234 : 78136 : hash = PyObject_Hash(key);
1235 [ + + ]: 78136 : if (hash == -1)
1236 : 2 : goto error;
1237 : 78134 : rv = set_contains_entry(so, key, hash);
1238 [ - + ]: 78134 : if (rv < 0)
1239 : 0 : goto error;
1240 [ + + ]: 78134 : if (rv) {
1241 [ - + ]: 15571 : if (set_add_entry(result, key, hash))
1242 : 0 : goto error;
1243 [ + + ]: 15571 : if (PySet_GET_SIZE(result) >= PySet_GET_SIZE(so)) {
1244 : 487 : Py_DECREF(key);
1245 : 487 : break;
1246 : : }
1247 : : }
1248 : 77647 : Py_DECREF(key);
1249 : : }
1250 : 3618 : Py_DECREF(it);
1251 [ + + ]: 3618 : if (PyErr_Occurred()) {
1252 : 146 : Py_DECREF(result);
1253 : 146 : return NULL;
1254 : : }
1255 : 3472 : 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 [ + + ]: 10080 : 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 : 132 : Py_DECREF(result);
1278 : 132 : return NULL;
1279 : : }
1280 : 5010 : Py_DECREF(result);
1281 : 5010 : result = newresult;
1282 : : }
1283 : 4938 : 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 : 32371 : set_and(PySetObject *so, PyObject *other)
1322 : : {
1323 [ + + + + : 32371 : if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
+ + + + +
+ + + + +
+ - ]
1324 : 24 : Py_RETURN_NOTIMPLEMENTED;
1325 : 32347 : 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 : 381 : tmp = (PyObject *)so;
1362 : 381 : so = (PySetObject *)other;
1363 : 381 : other = tmp;
1364 : : }
1365 [ + + ]: 1906 : while (set_next((PySetObject *)other, &pos, &entry)) {
1366 : 1408 : PyObject *key = entry->key;
1367 : 1408 : Py_INCREF(key);
1368 : 1408 : rv = set_contains_entry(so, key, entry->hash);
1369 : 1408 : Py_DECREF(key);
1370 [ - + ]: 1408 : if (rv < 0) {
1371 : 0 : return NULL;
1372 : : }
1373 [ + + ]: 1408 : if (rv) {
1374 : 520 : Py_RETURN_FALSE;
1375 : : }
1376 : : }
1377 : 498 : Py_RETURN_TRUE;
1378 : : }
1379 : :
1380 : 3048 : it = PyObject_GetIter(other);
1381 [ + + ]: 3048 : if (it == NULL)
1382 : 12 : return NULL;
1383 : :
1384 [ + + ]: 27706 : while ((key = PyIter_Next(it)) != NULL) {
1385 : 25836 : rv = set_contains_key(so, key);
1386 : 25836 : Py_DECREF(key);
1387 [ - + ]: 25836 : if (rv < 0) {
1388 : 0 : Py_DECREF(it);
1389 : 0 : return NULL;
1390 : : }
1391 [ + + ]: 25836 : if (rv) {
1392 : 1166 : Py_DECREF(it);
1393 : 1166 : Py_RETURN_FALSE;
1394 : : }
1395 : : }
1396 : 1870 : Py_DECREF(it);
1397 [ + + ]: 1870 : if (PyErr_Occurred())
1398 : 10 : return NULL;
1399 : 1860 : 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 : 20166 : set_difference_update_internal(PySetObject *so, PyObject *other)
1407 : : {
1408 [ + + ]: 20166 : if ((PyObject *)so == other)
1409 : 2 : return set_clear_internal(so);
1410 : :
1411 [ + + + + : 26786 : if (PyAnySet_Check(other)) {
+ + - + ]
1412 : : setentry *entry;
1413 : 6622 : 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 [ + + ]: 6622 : if ((PySet_GET_SIZE(other) >> 3) > PySet_GET_SIZE(so)) {
1420 : 37 : other = set_intersection(so, other);
1421 [ - + ]: 37 : if (other == NULL)
1422 : 0 : return -1;
1423 : : } else {
1424 : 6585 : Py_INCREF(other);
1425 : : }
1426 : :
1427 [ + + ]: 38273 : while (set_next((PySetObject *)other, &pos, &entry)) {
1428 : 31651 : PyObject *key = entry->key;
1429 : 31651 : Py_INCREF(key);
1430 [ - + ]: 31651 : 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 : 31651 : Py_DECREF(key);
1436 : : }
1437 : :
1438 : 6622 : Py_DECREF(other);
1439 : : } else {
1440 : : PyObject *key, *it;
1441 : 13542 : it = PyObject_GetIter(other);
1442 [ + + ]: 13542 : if (it == NULL)
1443 : 45 : return -1;
1444 : :
1445 [ + + ]: 46375 : while ((key = PyIter_Next(it)) != NULL) {
1446 [ + + ]: 32884 : if (set_discard_key(so, key) < 0) {
1447 : 6 : Py_DECREF(it);
1448 : 6 : Py_DECREF(key);
1449 : 6 : return -1;
1450 : : }
1451 : 32878 : Py_DECREF(key);
1452 : : }
1453 : 13491 : Py_DECREF(it);
1454 [ + + ]: 13491 : if (PyErr_Occurred())
1455 : 67 : return -1;
1456 : : }
1457 : : /* If more than 1/4th are dummies, then resize them away. */
1458 [ + + ]: 20046 : if ((size_t)(so->fill - so->used) <= (size_t)so->mask / 4)
1459 : 18294 : return 0;
1460 [ - + ]: 1752 : return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
1461 : : }
1462 : :
1463 : : static PyObject *
1464 : 13784 : set_difference_update(PySetObject *so, PyObject *args)
1465 : : {
1466 : : Py_ssize_t i;
1467 : :
1468 [ + + ]: 27490 : for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1469 : 13784 : PyObject *other = PyTuple_GET_ITEM(args, i);
1470 [ + + ]: 13784 : if (set_difference_update_internal(so, other))
1471 : 78 : return NULL;
1472 : : }
1473 : 13706 : 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 : 5898 : set_copy_and_difference(PySetObject *so, PyObject *other)
1481 : : {
1482 : : PyObject *result;
1483 : :
1484 : 5898 : result = set_copy(so, NULL);
1485 [ - + ]: 5898 : if (result == NULL)
1486 : 0 : return NULL;
1487 [ + + ]: 5898 : if (set_difference_update_internal((PySetObject *) result, other) == 0)
1488 : 5858 : return result;
1489 : 40 : Py_DECREF(result);
1490 : 40 : return NULL;
1491 : : }
1492 : :
1493 : : static PyObject *
1494 : 58680 : set_difference(PySetObject *so, PyObject *other)
1495 : : {
1496 : : PyObject *result;
1497 : : PyObject *key;
1498 : : Py_hash_t hash;
1499 : : setentry *entry;
1500 : 58680 : Py_ssize_t pos = 0, other_size;
1501 : : int rv;
1502 : :
1503 [ + + + + : 58680 : if (PyAnySet_Check(other)) {
+ + + + ]
1504 : 58285 : 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 [ + + ]: 58410 : if ((PySet_GET_SIZE(so) >> 2) > other_size) {
1516 : 5628 : return set_copy_and_difference(so, other);
1517 : : }
1518 : :
1519 : 52782 : result = make_new_set_basetype(Py_TYPE(so), NULL);
1520 [ - + ]: 52782 : if (result == NULL)
1521 : 0 : return NULL;
1522 : :
1523 [ + + ]: 52782 : if (PyDict_CheckExact(other)) {
1524 [ + + ]: 1028 : while (set_next(so, &pos, &entry)) {
1525 : 913 : key = entry->key;
1526 : 913 : hash = entry->hash;
1527 : 913 : Py_INCREF(key);
1528 : 913 : rv = _PyDict_Contains_KnownHash(other, key, hash);
1529 [ - + ]: 913 : if (rv < 0) {
1530 : 0 : Py_DECREF(result);
1531 : 0 : Py_DECREF(key);
1532 : 0 : return NULL;
1533 : : }
1534 [ + + ]: 913 : if (!rv) {
1535 [ - + ]: 431 : 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 : 913 : Py_DECREF(key);
1542 : : }
1543 : 115 : return result;
1544 : : }
1545 : :
1546 : : /* Iterate over so, checking for common elements in other. */
1547 [ + + ]: 1102096 : while (set_next(so, &pos, &entry)) {
1548 : 1049429 : key = entry->key;
1549 : 1049429 : hash = entry->hash;
1550 : 1049429 : Py_INCREF(key);
1551 : 1049429 : rv = set_contains_entry((PySetObject *)other, key, hash);
1552 [ - + ]: 1049429 : if (rv < 0) {
1553 : 0 : Py_DECREF(result);
1554 : 0 : Py_DECREF(key);
1555 : 0 : return NULL;
1556 : : }
1557 [ + + ]: 1049429 : if (!rv) {
1558 [ - + ]: 14024 : 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 : 1049429 : Py_DECREF(key);
1565 : : }
1566 : 52667 : return result;
1567 : : }
1568 : :
1569 : : static PyObject *
1570 : 39221 : set_difference_multi(PySetObject *so, PyObject *args)
1571 : : {
1572 : : Py_ssize_t i;
1573 : : PyObject *result, *other;
1574 : :
1575 [ + + ]: 39221 : if (PyTuple_GET_SIZE(args) == 0)
1576 : 24 : return set_copy(so, NULL);
1577 : :
1578 : 39197 : other = PyTuple_GET_ITEM(args, 0);
1579 : 39197 : result = set_difference(so, other);
1580 [ + + ]: 39197 : if (result == NULL)
1581 : 40 : return NULL;
1582 : :
1583 [ + + ]: 39181 : 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 : 39157 : 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 : 19510 : set_sub(PySetObject *so, PyObject *other)
1599 : : {
1600 [ + + + + : 19510 : if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
+ + + + +
+ + + + +
+ + ]
1601 : 27 : Py_RETURN_NOTIMPLEMENTED;
1602 : 19483 : return set_difference(so, other);
1603 : : }
1604 : :
1605 : : static PyObject *
1606 : 466 : set_isub(PySetObject *so, PyObject *other)
1607 : : {
1608 [ + + + - : 466 : if (!PyAnySet_Check(other))
+ + + - ]
1609 : 6 : Py_RETURN_NOTIMPLEMENTED;
1610 [ - + ]: 460 : if (set_difference_update_internal(so, other))
1611 : 0 : return NULL;
1612 : 460 : Py_INCREF(so);
1613 : 460 : 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 [ + + ]: 1256 : while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
1632 : 1144 : Py_INCREF(key);
1633 : 1144 : rv = set_discard_entry(so, key, hash);
1634 [ - + ]: 1144 : if (rv < 0) {
1635 : 0 : Py_DECREF(key);
1636 : 0 : return NULL;
1637 : : }
1638 [ + + ]: 1144 : if (rv == DISCARD_NOTFOUND) {
1639 [ - + ]: 515 : if (set_add_entry(so, key, hash)) {
1640 : 0 : Py_DECREF(key);
1641 : 0 : return NULL;
1642 : : }
1643 : : }
1644 : 1144 : 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 [ + + ]: 33090 : while (set_next(otherset, &pos, &entry)) {
1659 : 30527 : key = entry->key;
1660 : 30527 : hash = entry->hash;
1661 : 30527 : Py_INCREF(key);
1662 : 30527 : rv = set_discard_entry(so, key, hash);
1663 [ - + ]: 30527 : if (rv < 0) {
1664 : 0 : Py_DECREF(otherset);
1665 : 0 : Py_DECREF(key);
1666 : 0 : return NULL;
1667 : : }
1668 [ + + ]: 30527 : if (rv == DISCARD_NOTFOUND) {
1669 [ - + ]: 18073 : if (set_add_entry(so, key, hash)) {
1670 : 0 : Py_DECREF(otherset);
1671 : 0 : Py_DECREF(key);
1672 : 0 : return NULL;
1673 : : }
1674 : : }
1675 : 30527 : 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 : 51198 : set_issubset(PySetObject *so, PyObject *other)
1732 : : {
1733 : : setentry *entry;
1734 : 51198 : Py_ssize_t pos = 0;
1735 : : int rv;
1736 : :
1737 [ + + + + : 51198 : if (!PyAnySet_Check(other)) {
+ + + + ]
1738 : 213 : PyObject *tmp = set_intersection(so, other);
1739 [ + + ]: 213 : if (tmp == NULL) {
1740 : 44 : return NULL;
1741 : : }
1742 : 169 : int result = (PySet_GET_SIZE(tmp) == PySet_GET_SIZE(so));
1743 : 169 : Py_DECREF(tmp);
1744 : 169 : return PyBool_FromLong(result);
1745 : : }
1746 [ + + ]: 50985 : if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
1747 : 3599 : Py_RETURN_FALSE;
1748 : :
1749 [ + + ]: 137450 : while (set_next(so, &pos, &entry)) {
1750 : 95021 : PyObject *key = entry->key;
1751 : 95021 : Py_INCREF(key);
1752 : 95021 : rv = set_contains_entry((PySetObject *)other, key, entry->hash);
1753 : 95021 : Py_DECREF(key);
1754 [ - + ]: 95021 : if (rv < 0) {
1755 : 0 : return NULL;
1756 : : }
1757 [ + + ]: 95021 : if (!rv) {
1758 : 4957 : Py_RETURN_FALSE;
1759 : : }
1760 : : }
1761 : 42429 : Py_RETURN_TRUE;
1762 : : }
1763 : :
1764 : : PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
1765 : :
1766 : : static PyObject *
1767 : 14126 : set_issuperset(PySetObject *so, PyObject *other)
1768 : : {
1769 [ + + + + : 14126 : if (PyAnySet_Check(other)) {
+ + + + ]
1770 : 6580 : 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 [ + + ]: 27932 : while ((key = PyIter_Next(it)) != NULL) {
1778 : 20510 : int rv = set_contains_key(so, key);
1779 : 20510 : Py_DECREF(key);
1780 [ - + ]: 20510 : if (rv < 0) {
1781 : 0 : Py_DECREF(it);
1782 : 0 : return NULL;
1783 : : }
1784 [ + + ]: 20510 : if (!rv) {
1785 : 124 : Py_DECREF(it);
1786 : 124 : Py_RETURN_FALSE;
1787 : : }
1788 : : }
1789 : 7422 : Py_DECREF(it);
1790 [ + + ]: 7422 : if (PyErr_Occurred()) {
1791 : 43 : return NULL;
1792 : : }
1793 : 7379 : Py_RETURN_TRUE;
1794 : : }
1795 : :
1796 : : PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
1797 : :
1798 : : static PyObject *
1799 : 69806 : set_richcompare(PySetObject *v, PyObject *w, int op)
1800 : : {
1801 : : PyObject *r1;
1802 : : int r2;
1803 : :
1804 [ + + + + : 69806 : if(!PyAnySet_Check(w))
+ + + + ]
1805 : 136 : Py_RETURN_NOTIMPLEMENTED;
1806 : :
1807 [ + + + + : 69670 : switch (op) {
+ + - ]
1808 : 25810 : case Py_EQ:
1809 [ + + ]: 25810 : if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
1810 : 6803 : Py_RETURN_FALSE;
1811 [ + + ]: 19007 : if (v->hash != -1 &&
1812 [ + + ]: 10234 : ((PySetObject *)w)->hash != -1 &&
1813 [ + + ]: 10206 : v->hash != ((PySetObject *)w)->hash)
1814 : 1944 : Py_RETURN_FALSE;
1815 : 17063 : 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 : 25296 : case Py_LE:
1826 : 25296 : 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 : 3005 : Py_RETURN_FALSE;
1832 : 1635 : return set_issubset(v, w);
1833 : 4524 : case Py_GT:
1834 [ + + ]: 4524 : if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
1835 : 2899 : Py_RETURN_FALSE;
1836 : 1625 : return set_issuperset(v, w);
1837 : : }
1838 : 0 : Py_RETURN_NOTIMPLEMENTED;
1839 : : }
1840 : :
1841 : : static PyObject *
1842 : 1387830 : set_add(PySetObject *so, PyObject *key)
1843 : : {
1844 [ + + ]: 1387830 : if (set_add_key(so, key))
1845 : 4 : return NULL;
1846 : 1387826 : 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 : 33625705 : set_contains(PySetObject *so, PyObject *key)
1856 : : {
1857 : : PyObject *tmpkey;
1858 : : int rv;
1859 : :
1860 : 33625705 : rv = set_contains_key(so, key);
1861 [ + + ]: 33625705 : 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 : 33625697 : return rv;
1872 : : }
1873 : :
1874 : : static PyObject *
1875 : 516948 : set_direct_contains(PySetObject *so, PyObject *key)
1876 : : {
1877 : : long result;
1878 : :
1879 : 516948 : result = set_contains(so, key);
1880 [ + + ]: 516948 : if (result < 0)
1881 : 8 : return NULL;
1882 : 516940 : return PyBool_FromLong(result);
1883 : : }
1884 : :
1885 : : PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
1886 : :
1887 : : static PyObject *
1888 : 61328 : set_remove(PySetObject *so, PyObject *key)
1889 : : {
1890 : : PyObject *tmpkey;
1891 : : int rv;
1892 : :
1893 : 61328 : rv = set_discard_key(so, key);
1894 [ + + ]: 61328 : 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 [ + + ]: 61324 : if (rv == DISCARD_NOTFOUND) {
1908 : 17 : _PyErr_SetKeyError(key);
1909 : 17 : return NULL;
1910 : : }
1911 : 61307 : 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 : 29973 : set_discard(PySetObject *so, PyObject *key)
1921 : : {
1922 : : PyObject *tmpkey;
1923 : : int rv;
1924 : :
1925 : 29973 : rv = set_discard_key(so, key);
1926 [ + + ]: 29973 : 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 : 29969 : 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 : 12067 : set_init(PySetObject *self, PyObject *args, PyObject *kwds)
1983 : : {
1984 : 12067 : PyObject *iterable = NULL;
1985 : :
1986 [ + + + + ]: 12067 : if (!_PyArg_NoKeywords("set", kwds))
1987 : 6 : return -1;
1988 [ + + ]: 12061 : if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable))
1989 : 3 : return -1;
1990 [ + + ]: 12058 : if (self->fill)
1991 : 4 : set_clear_internal(self);
1992 : 12058 : self->hash = -1;
1993 [ + + ]: 12058 : if (iterable == NULL)
1994 : 22 : return 0;
1995 : 12036 : return set_update_internal(self, iterable);
1996 : : }
1997 : :
1998 : : static PyObject*
1999 : 997431 : set_vectorcall(PyObject *type, PyObject * const*args,
2000 : : size_t nargsf, PyObject *kwnames)
2001 : : {
2002 : : assert(PyType_Check(type));
2003 : :
2004 [ - + - - ]: 997431 : if (!_PyArg_NoKwnames("set", kwnames)) {
2005 : 0 : return NULL;
2006 : : }
2007 : :
2008 : 997431 : Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);
2009 [ + - + + : 997431 : if (!_PyArg_CheckPositional("set", nargs, 0, 1)) {
+ - ]
2010 : 1 : return NULL;
2011 : : }
2012 : :
2013 [ + + ]: 997430 : if (nargs) {
2014 : 685906 : return make_new_set(_PyType_CAST(type), args[0]);
2015 : : }
2016 : :
2017 : 311524 : 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 : 3831952 : PySet_New(PyObject *iterable)
2279 : : {
2280 : 3831952 : return make_new_set(&PySet_Type, iterable);
2281 : : }
2282 : :
2283 : : PyObject *
2284 : 211620 : PyFrozenSet_New(PyObject *iterable)
2285 : : {
2286 : 211620 : return make_new_set(&PyFrozenSet_Type, iterable);
2287 : : }
2288 : :
2289 : : Py_ssize_t
2290 : 37974 : PySet_Size(PyObject *anyset)
2291 : : {
2292 [ - + - - : 37974 : if (!PyAnySet_Check(anyset)) {
- - - - ]
2293 : 0 : PyErr_BadInternalCall();
2294 : 0 : return -1;
2295 : : }
2296 : 37974 : return PySet_GET_SIZE(anyset);
2297 : : }
2298 : :
2299 : : int
2300 : 37673 : PySet_Clear(PyObject *set)
2301 : : {
2302 [ - + - - ]: 37673 : if (!PySet_Check(set)) {
2303 : 0 : PyErr_BadInternalCall();
2304 : 0 : return -1;
2305 : : }
2306 : 37673 : return set_clear_internal((PySetObject *)set);
2307 : : }
2308 : :
2309 : : int
2310 : 3209971 : PySet_Contains(PyObject *anyset, PyObject *key)
2311 : : {
2312 [ - + - - : 3209971 : if (!PyAnySet_Check(anyset)) {
- - - - ]
2313 : 0 : PyErr_BadInternalCall();
2314 : 0 : return -1;
2315 : : }
2316 : 3209971 : return set_contains_key((PySetObject *)anyset, key);
2317 : : }
2318 : :
2319 : : int
2320 : 1620388 : PySet_Discard(PyObject *set, PyObject *key)
2321 : : {
2322 [ - + - - ]: 1620388 : if (!PySet_Check(set)) {
2323 : 0 : PyErr_BadInternalCall();
2324 : 0 : return -1;
2325 : : }
2326 : 1620388 : return set_discard_key((PySetObject *)set, key);
2327 : : }
2328 : :
2329 : : int
2330 : 3853491 : PySet_Add(PyObject *anyset, PyObject *key)
2331 : : {
2332 [ + + + - : 4126955 : if (!PySet_Check(anyset) &&
- + ]
2333 [ - - - + ]: 546928 : (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
2334 : 0 : PyErr_BadInternalCall();
2335 : 0 : return -1;
2336 : : }
2337 : 3853491 : return set_add_key((PySetObject *)anyset, key);
2338 : : }
2339 : :
2340 : : int
2341 : 165531 : _PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash)
2342 : : {
2343 : : setentry *entry;
2344 : :
2345 [ + + - + : 165531 : if (!PyAnySet_Check(set)) {
- - - - ]
2346 : 0 : PyErr_BadInternalCall();
2347 : 0 : return -1;
2348 : : }
2349 [ + + ]: 165531 : if (set_next((PySetObject *)set, pos, &entry) == 0)
2350 : 42939 : return 0;
2351 : 122592 : *key = entry->key;
2352 : 122592 : *hash = entry->hash;
2353 : 122592 : return 1;
2354 : : }
2355 : :
2356 : : PyObject *
2357 : 0 : PySet_Pop(PyObject *set)
2358 : : {
2359 [ # # # # ]: 0 : if (!PySet_Check(set)) {
2360 : 0 : PyErr_BadInternalCall();
2361 : 0 : return NULL;
2362 : : }
2363 : 0 : return set_pop((PySetObject *)set, NULL);
2364 : : }
2365 : :
2366 : : int
2367 : 6820 : _PySet_Update(PyObject *set, PyObject *iterable)
2368 : : {
2369 [ - + - - ]: 6820 : if (!PySet_Check(set)) {
2370 : 0 : PyErr_BadInternalCall();
2371 : 0 : return -1;
2372 : : }
2373 : 6820 : 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 : : 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 : : PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x=NULL;
2398 : : PyObject *ob = (PyObject *)so;
2399 : : Py_hash_t hash;
2400 : : PyObject *str;
2401 : :
2402 : : /* Verify preconditions */
2403 : : assert(PyAnySet_Check(ob));
2404 : : assert(PyAnySet_CheckExact(ob));
2405 : : assert(!PyFrozenSet_CheckExact(ob));
2406 : :
2407 : : /* so.clear(); so |= set("abc"); */
2408 : : str = PyUnicode_FromString("abc");
2409 : : if (str == NULL)
2410 : : return NULL;
2411 : : set_clear_internal(so);
2412 : : if (set_update_internal(so, str)) {
2413 : : Py_DECREF(str);
2414 : : return NULL;
2415 : : }
2416 : : Py_DECREF(str);
2417 : :
2418 : : /* Exercise type/size checks */
2419 : : assert(PySet_Size(ob) == 3);
2420 : : assert(PySet_GET_SIZE(ob) == 3);
2421 : :
2422 : : /* Raise TypeError for non-iterable constructor arguments */
2423 : : assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
2424 : : assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);
2425 : :
2426 : : /* Raise TypeError for unhashable key */
2427 : : dup = PySet_New(ob);
2428 : : assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
2429 : : assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
2430 : : assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);
2431 : :
2432 : : /* Exercise successful pop, contains, add, and discard */
2433 : : elem = PySet_Pop(ob);
2434 : : assert(PySet_Contains(ob, elem) == 0);
2435 : : assert(PySet_GET_SIZE(ob) == 2);
2436 : : assert(PySet_Add(ob, elem) == 0);
2437 : : assert(PySet_Contains(ob, elem) == 1);
2438 : : assert(PySet_GET_SIZE(ob) == 3);
2439 : : assert(PySet_Discard(ob, elem) == 1);
2440 : : assert(PySet_GET_SIZE(ob) == 2);
2441 : : assert(PySet_Discard(ob, elem) == 0);
2442 : : assert(PySet_GET_SIZE(ob) == 2);
2443 : :
2444 : : /* Exercise clear */
2445 : : dup2 = PySet_New(dup);
2446 : : assert(PySet_Clear(dup2) == 0);
2447 : : assert(PySet_Size(dup2) == 0);
2448 : : Py_DECREF(dup2);
2449 : :
2450 : : /* Raise SystemError on clear or update of frozen set */
2451 : : f = PyFrozenSet_New(dup);
2452 : : assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
2453 : : assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
2454 : : assert(PySet_Add(f, elem) == 0);
2455 : : Py_INCREF(f);
2456 : : assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
2457 : : Py_DECREF(f);
2458 : : Py_DECREF(f);
2459 : :
2460 : : /* Exercise direct iteration */
2461 : : i = 0, count = 0;
2462 : : while (_PySet_NextEntry((PyObject *)dup, &i, &x, &hash)) {
2463 : : s = PyUnicode_AsUTF8(x);
2464 : : assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
2465 : : count++;
2466 : : }
2467 : : assert(count == 3);
2468 : :
2469 : : /* Exercise updates */
2470 : : dup2 = PySet_New(NULL);
2471 : : assert(_PySet_Update(dup2, dup) == 0);
2472 : : assert(PySet_Size(dup2) == 3);
2473 : : assert(_PySet_Update(dup2, dup) == 0);
2474 : : assert(PySet_Size(dup2) == 3);
2475 : : Py_DECREF(dup2);
2476 : :
2477 : : /* Raise SystemError when self argument is not a set or frozenset. */
2478 : : t = PyTuple_New(0);
2479 : : assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
2480 : : assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
2481 : : Py_DECREF(t);
2482 : :
2483 : : /* Raise SystemError when self argument is not a set. */
2484 : : f = PyFrozenSet_New(dup);
2485 : : assert(PySet_Size(f) == 3);
2486 : : assert(PyFrozenSet_CheckExact(f));
2487 : : assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
2488 : : assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
2489 : : Py_DECREF(f);
2490 : :
2491 : : /* Raise KeyError when popping from an empty set */
2492 : : assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
2493 : : Py_DECREF(ob);
2494 : : assert(PySet_GET_SIZE(ob) == 0);
2495 : : assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);
2496 : :
2497 : : /* Restore the set from the copy using the PyNumber API */
2498 : : assert(PyNumber_InPlaceOr(ob, dup) == ob);
2499 : : Py_DECREF(ob);
2500 : :
2501 : : /* Verify constructors accept NULL arguments */
2502 : : f = PySet_New(NULL);
2503 : : assert(f != NULL);
2504 : : assert(PySet_GET_SIZE(f) == 0);
2505 : : Py_DECREF(f);
2506 : : f = PyFrozenSet_New(NULL);
2507 : : assert(f != NULL);
2508 : : assert(PyFrozenSet_CheckExact(f));
2509 : : assert(PySet_GET_SIZE(f) == 0);
2510 : : Py_DECREF(f);
2511 : :
2512 : : Py_DECREF(elem);
2513 : : Py_DECREF(dup);
2514 : : 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 : : 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 : : };
|
