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