/home/mdboom/Work/builds/cpython/Objects/setobject.c
Line | Count | Source (jump to first uncovered line) |
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 | 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) { Branch (66:12): [Folded - Ignored]
|
67 | entry = &so->table[i]; |
68 | probes = (i + LINEAR_PROBES <= mask) ? LINEAR_PROBES4.84M : 06.69M ; Branch (68:18): [True: 4.84M, False: 6.69M]
|
69 | do { |
70 | if (entry->hash == 0 && entry->key == NULL6.43M ) Branch (70:17): [True: 6.43M, False: 8.23M]
Branch (70:37): [True: 6.32M, False: 103k]
|
71 | return entry; |
72 | if (entry->hash == hash) { Branch (72:17): [True: 2.74M, False: 5.59M]
|
73 | PyObject *startkey = entry->key; |
74 | assert(startkey != dummy); |
75 | if (startkey == key) Branch (75:21): [True: 1.29M, False: 1.44M]
|
76 | return entry; |
77 | if (PyUnicode_CheckExact(startkey) |
78 | && PyUnicode_CheckExact(key) |
79 | && _PyUnicode_EQ(startkey, key)379k ) Branch (79:24): [True: 379k, False: 0]
|
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) Branch (85:21): [True: 8, False: 1.06M]
|
86 | return NULL; |
87 | if (table != so->table || entry->key != startkey1.06M ) Branch (87:21): [True: 2.54k, False: 1.06M]
Branch (87:43): [True: 242, False: 1.06M]
|
88 | return set_lookkey(so, key, hash); |
89 | if (cmp > 0) Branch (89:21): [True: 1.03M, False: 33.5k]
|
90 | return entry; |
91 | mask = so->mask; |
92 | } |
93 | entry++; |
94 | } while (probes--); Branch (94:18): [True: 3.12M, False: 2.49M]
|
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) { Branch (125:12): [Folded - Ignored]
|
126 | entry = &so->table[i]; |
127 | probes = (i + LINEAR_PROBES <= mask) ? LINEAR_PROBES10.8M : 015.7M ; Branch (127:18): [True: 10.8M, False: 15.7M]
|
128 | do { |
129 | if (entry->hash == 0 && entry->key == NULL27.0M ) Branch (129:17): [True: 27.0M, False: 18.1M]
Branch (129:37): [True: 19.9M, False: 7.07M]
|
130 | goto found_unused_or_dummy; |
131 | if (entry->hash == hash) { Branch (131:17): [True: 9.22M, False: 16.0M]
|
132 | PyObject *startkey = entry->key; |
133 | assert(startkey != dummy); |
134 | if (startkey == key) Branch (134:21): [True: 1.62M, False: 7.60M]
|
135 | goto found_active; |
136 | if (PyUnicode_CheckExact(startkey) |
137 | && PyUnicode_CheckExact(key) |
138 | && _PyUnicode_EQ(startkey, key)63.0k ) Branch (138:24): [True: 63.0k, False: 0]
|
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) Branch (144:21): [True: 448k, False: 7.09M]
|
145 | goto found_active; |
146 | if (cmp < 0) Branch (146:21): [True: 7, False: 7.09M]
|
147 | goto comparison_error; |
148 | if (table != so->table || entry->key != startkey7.09M ) Branch (148:21): [True: 284, False: 7.09M]
Branch (148:43): [True: 152, False: 7.09M]
|
149 | goto restart; |
150 | mask = so->mask; |
151 | } |
152 | else if (entry->hash == -1) { Branch (152:22): [True: 108k, False: 15.9M]
|
153 | assert (entry->key == dummy); |
154 | freeslot = entry; |
155 | } |
156 | entry++; |
157 | } while (probes--); Branch (157:18): [True: 18.6M, False: 4.45M]
|
158 | perturb >>= PERTURB_SHIFT; |
159 | i = (i * 5 + 1 + perturb) & mask; |
160 | } |
161 | |
162 | found_unused_or_dummy: |
163 | if (freeslot == NULL) Branch (163:9): [True: 19.9M, False: 65.9k]
|
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) Branch (175:9): [True: 18.5M, False: 1.37M]
|
176 | return 0; |
177 | return set_table_resize(so, so->used>50000 ? so->used*28 : so->used*41.37M ); Branch (177:33): [True: 8, False: 1.37M]
|
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) { Branch (204:12): [Folded - Ignored]
|
205 | entry = &table[i]; |
206 | if (entry->key == NULL) Branch (206:13): [True: 13.0M, False: 2.01M]
|
207 | goto found_null; |
208 | if (i + LINEAR_PROBES <= mask) { Branch (208:13): [True: 1.80M, False: 210k]
|
209 | for (j = 0; j < LINEAR_PROBES; j++4.35M ) { Branch (209:25): [True: 5.87M, False: 287k]
|
210 | entry++; |
211 | if (entry->key == NULL) Branch (211:21): [True: 1.51M, False: 4.35M]
|
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) { Branch (245:12): [True: 2.92M, False: 1.40M]
|
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) { Branch (254:9): [True: 1.02k, False: 1.40M]
|
255 | /* A large table is shrinking, or we can't get any smaller. */ |
256 | newtable = so->smalltable; |
257 | if (newtable == oldtable) { Branch (257:13): [True: 831, False: 192]
|
258 | if (so->fill == so->used) { Branch (258:17): [True: 0, False: 831]
|
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) { Branch (275:13): [True: 0, False: 1.40M]
|
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) { Branch (290:9): [True: 1.40M, False: 1.55k]
|
291 | for (entry = oldtable; entry <= oldtable + oldmask; entry++22.7M ) { Branch (291:32): [True: 22.7M, False: 1.40M]
|
292 | if (entry->key != NULL) { Branch (292:17): [True: 13.7M, False: 9.00M]
|
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++45.7k ) { Branch (298:32): [True: 45.7k, False: 1.55k]
|
299 | if (entry->key != NULL && entry->key != 24.0k dummy24.0k ) { Branch (299:17): [True: 24.0k, False: 21.7k]
Branch (299:39): [True: 8.95k, False: 15.0k]
|
300 | set_insert_clean(newtable, newmask, entry->key, entry->hash); |
301 | } |
302 | } |
303 | } |
304 | |
305 | if (is_oldtable_malloced) Branch (305:9): [True: 35.2k, False: 1.36M]
|
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) Branch (316:9): [True: 8.74M, False: 4]
|
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) Branch (331:9): [True: 4, False: 292k]
|
332 | return -1; |
333 | if (entry->key == NULL) Branch (333:9): [True: 167k, False: 125k]
|
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) || Branch (348:9): [True: 15.2M, False: 6.70M]
|
349 | (hash = 6.70M _PyASCIIObject_CAST6.70M (key)->hash) == -1) { Branch (349:9): [True: 3.14M, False: 3.56M]
|
350 | hash = PyObject_Hash(key); |
351 | if (hash == -1) Branch (351:13): [True: 23, False: 18.3M]
|
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) || Branch (362:9): [True: 1.78M, False: 5.73M]
|
363 | (hash = 5.73M _PyASCIIObject_CAST5.73M (key)->hash) == -1) { Branch (363:9): [True: 1.24M, False: 4.48M]
|
364 | hash = PyObject_Hash(key); |
365 | if (hash == -1) Branch (365:13): [True: 14, False: 3.03M]
|
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) || Branch (376:9): [True: 121k, False: 110k]
|
377 | (hash = 110k _PyASCIIObject_CAST110k (key)->hash) == -1) { Branch (377:9): [True: 1, False: 110k]
|
378 | hash = PyObject_Hash(key); |
379 | if (hash == -1) Branch (379:13): [True: 20, False: 121k]
|
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) Branch (415:9): [True: 11.6k, False: 10.8k]
|
416 | set_empty_to_minsize(so); |
417 | |
418 | else if (fill > 0) { Branch (418:14): [True: 7.08k, False: 3.81k]
|
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++567k ) { Branch (433:25): [True: 567k, False: 22.5k]
|
434 | if (entry->key && entry->key != 314k dummy314k ) { Branch (434:13): [True: 314k, False: 253k]
Branch (434:27): [True: 309k, False: 5.07k]
|
435 | used--; |
436 | Py_DECREF(entry->key); |
437 | } |
438 | } |
439 | |
440 | if (table_is_malloced) Branch (440:9): [True: 11.6k, False: 10.8k]
|
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 && (793M entry->key == NULL793M || entry->key == 205M dummy205M )) { Branch (470:12): [True: 793M, False: 38.2M]
Branch (470:26): [True: 588M, False: 205M]
Branch (470:48): [True: 29.8M, False: 175M]
|
471 | i++; |
472 | entry++; |
473 | } |
474 | *pos_ptr = i+1; |
475 | if (i > mask) Branch (475:9): [True: 38.2M, False: 175M]
|
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) Branch (491:9): [True: 101, False: 3.19M]
|
492 | PyObject_ClearWeakRefs((PyObject *) so); |
493 | |
494 | for (entry = so->table; used > 0; entry++55.5M ) { Branch (494:29): [True: 55.5M, False: 3.19M]
|
495 | if (entry->key && entry->key != 20.8M dummy20.8M ) { Branch (495:13): [True: 20.8M, False: 34.6M]
Branch (495:27): [True: 20.8M, False: 19.2k]
|
496 | used--; |
497 | Py_DECREF(entry->key); |
498 | } |
499 | } |
500 | if (so->table != so->smalltable) Branch (500:9): [True: 1.35M, False: 1.84M]
|
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) { Branch (512:9): [True: 7, False: 1.18k]
|
513 | if (status < 0) Branch (513:13): [True: 0, False: 7]
|
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) { Branch (519:9): [True: 203, False: 978]
|
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) Branch (525:9): [True: 0, False: 978]
|
526 | goto done; |
527 | |
528 | /* repr(keys)[1:-1] */ |
529 | listrepr = PyObject_Repr(keys); |
530 | Py_DECREF(keys); |
531 | if (listrepr == NULL) Branch (531:9): [True: 0, False: 978]
|
532 | goto done; |
533 | tmp = PyUnicode_Substring(listrepr, 1, PyUnicode_GET_LENGTH(listrepr)-1); |
534 | Py_DECREF(listrepr); |
535 | if (tmp == NULL) Branch (535:9): [True: 0, False: 978]
|
536 | goto done; |
537 | listrepr = tmp; |
538 | |
539 | if (!PySet_CheckExact(so)) Branch (539:9): [True: 664, False: 314]
|
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 == 0432k ) Branch (570:9): [True: 2, False: 432k]
Branch (570:24): [True: 324k, False: 108k]
|
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) { Branch (577:9): [True: 30.5k, False: 77.6k]
|
578 | if (set_table_resize(so, (so->used + other->used)*2) != 0) Branch (578:13): [True: 0, False: 30.5k]
|
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->mask76.8k && other->fill == other->used63.2k ) { Branch (586:9): [True: 76.8k, False: 31.4k]
Branch (586:26): [True: 63.2k, False: 13.6k]
Branch (586:53): [True: 63.1k, False: 71]
|
587 | for (i = 0; i <= other->mask; i++, so_entry++, other_entry++2.02M ) { Branch (587:21): [True: 2.02M, False: 63.1k]
|
588 | key = other_entry->key; |
589 | if (key != NULL) { Branch (589:17): [True: 587k, False: 1.43M]
|
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) { Branch (602:9): [True: 13.7k, False: 31.4k]
|
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++1.51M ) { Branch (607:35): [True: 1.51M, False: 13.7k]
|
608 | key = other_entry->key; |
609 | if (key != NULL && key != 737k dummy737k ) { Branch (609:17): [True: 737k, False: 774k]
Branch (609:32): [True: 737k, False: 113]
|
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; 31.4k i <= other->mask; i++355k ) { Branch (618:17): [True: 355k, False: 31.4k]
|
619 | other_entry = &other->table[i]; |
620 | key = other_entry->key; |
621 | if (key != NULL && key != 100k dummy100k ) { Branch (621:13): [True: 100k, False: 254k]
Branch (621:28): [True: 100k, False: 82]
|
622 | if (set_add_entry(so, key, other_entry->hash)) Branch (622:17): [True: 1, False: 100k]
|
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) { Branch (637:9): [True: 3, False: 6.12k]
|
638 | PyErr_SetString(PyExc_KeyError, "pop from an empty set"); |
639 | return NULL; |
640 | } |
641 | while (6.12k entry->key == NULL || entry->key==6.12k dummy6.12k ) { Branch (641:12): [True: 16.0k, False: 6.12k]
Branch (641:34): [True: 0, False: 6.12k]
|
642 | entry++; |
643 | if (entry > limit) Branch (643:13): [True: 0, False: 16.0k]
|
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)) Branch (663:12): [True: 174M, False: 38.1M]
|
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) Branch (692:9): [True: 4.20M, False: 1.06M]
|
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; 1.06M entry <= &so->table[so->mask]; entry++32.8M ) Branch (705:29): [True: 32.8M, False: 1.06M]
|
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) Branch (709:9): [True: 533k, False: 533k]
|
710 | hash ^= _shuffle_bits(0); |
711 | |
712 | /* Remove the effect of an odd number of dummy entries */ |
713 | if ((so->fill - so->used) & 1) Branch (713:9): [True: 60, False: 1.06M]
|
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) Branch (724:9): [True: 0, False: 1.06M]
|
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->used7.93k ) Branch (761:9): [True: 7.93k, False: 1]
Branch (761:31): [True: 7.93k, False: 1]
|
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 | /* copy the iterator state */ |
774 | setiterobject tmp = *si; |
775 | Py_XINCREF(tmp.si_set); |
776 | |
777 | /* iterate the temporary into a list */ |
778 | PyObject *list = PySequence_List((PyObject*)&tmp); |
779 | Py_XDECREF(tmp.si_set); |
780 | if (list == NULL) { Branch (780:9): [True: 0, False: 24]
|
781 | return NULL; |
782 | } |
783 | 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 | static PyObject *setiter_iternext(setiterobject *si) |
795 | { |
796 | PyObject *key; |
797 | Py_ssize_t i, mask; |
798 | setentry *entry; |
799 | PySetObject *so = si->si_set; |
800 | |
801 | if (so == NULL) Branch (801:9): [True: 4, False: 1.36M]
|
802 | return NULL; |
803 | assert (PyAnySet_Check(so)); |
804 | |
805 | if (si->si_used != so->used) { Branch (805:9): [True: 6, False: 1.36M]
|
806 | PyErr_SetString(PyExc_RuntimeError, |
807 | "Set changed size during iteration"); |
808 | si->si_used = -1; /* Make this state sticky */ |
809 | return NULL; |
810 | } |
811 | |
812 | i = si->si_pos; |
813 | assert(i>=0); |
814 | entry = so->table; |
815 | mask = so->mask; |
816 | while (i <= mask && (7.08M entry[i].key == NULL7.08M || entry[i].key == 2.29M dummy2.29M )) Branch (816:12): [True: 7.08M, False: 167k]
Branch (816:26): [True: 4.78M, False: 2.29M]
Branch (816:50): [True: 1.09M, False: 1.19M]
|
817 | i++; |
818 | si->si_pos = i+1; |
819 | if (i > mask) Branch (819:9): [True: 167k, False: 1.19M]
|
820 | goto fail; |
821 | si->len--; |
822 | key = entry[i].key; |
823 | Py_INCREF(key); |
824 | return key; |
825 | |
826 | fail: |
827 | si->si_set = NULL; |
828 | Py_DECREF(so); |
829 | 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 | set_iter(PySetObject *so) |
867 | { |
868 | setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type); |
869 | if (si == NULL) Branch (869:9): [True: 0, False: 169k]
|
870 | return NULL; |
871 | Py_INCREF(so); |
872 | si->si_set = so; |
873 | si->si_used = so->used; |
874 | si->si_pos = 0; |
875 | si->len = so->used; |
876 | _PyObject_GC_TRACK(si); |
877 | return (PyObject *)si; |
878 | } |
879 | |
880 | static int |
881 | set_update_internal(PySetObject *so, PyObject *other) |
882 | { |
883 | PyObject *key, *it; |
884 | |
885 | if (PyAnySet_Check(other)) |
886 | return set_merge(so, other); |
887 | |
888 | if (PyDict_CheckExact(other)) { |
889 | PyObject *value; |
890 | Py_ssize_t pos = 0; |
891 | Py_hash_t hash; |
892 | 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 | if (dictsize < 0) Branch (898:13): [True: 0, False: 5.44k]
|
899 | return -1; |
900 | if ((so->fill + dictsize)*5 >= so->mask*3) { Branch (900:13): [True: 967, False: 4.48k]
|
901 | if (set_table_resize(so, (so->used + dictsize)*2) != 0) Branch (901:17): [True: 0, False: 967]
|
902 | return -1; |
903 | } |
904 | while (5.44k _PyDict_Next(other, &pos, &key, &value, &hash)) { Branch (904:16): [True: 18.6k, False: 5.44k]
|
905 | if (set_add_entry(so, key, hash)) Branch (905:17): [True: 0, False: 18.6k]
|
906 | return -1; |
907 | } |
908 | return 0; |
909 | } |
910 | |
911 | it = PyObject_GetIter(other); |
912 | if (it == NULL) Branch (912:9): [True: 83, False: 1.68M]
|
913 | return -1; |
914 | |
915 | while (1.68M (key = PyIter_Next(it)) != NULL) { Branch (915:12): [True: 16.9M, False: 1.68M]
|
916 | if (set_add_key(so, key)) { Branch (916:13): [True: 24, False: 16.9M]
|
917 | Py_DECREF(it); |
918 | Py_DECREF(key); |
919 | return -1; |
920 | } |
921 | Py_DECREF(key); |
922 | } |
923 | Py_DECREF(it); |
924 | if (PyErr_Occurred()) Branch (924:9): [True: 55, False: 1.68M]
|
925 | return -1; |
926 | return 0; |
927 | } |
928 | |
929 | static PyObject * |
930 | set_update(PySetObject *so, PyObject *args) |
931 | { |
932 | Py_ssize_t i; |
933 | |
934 | for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++1.42k ) { Branch (934:16): [True: 1.44k, False: 1.36k]
|
935 | PyObject *other = PyTuple_GET_ITEM(args, i); |
936 | if (set_update_internal(so, other)) Branch (936:13): [True: 25, False: 1.42k]
|
937 | return NULL; |
938 | } |
939 | Py_RETURN_NONE1.36k ; |
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 | make_new_set(PyTypeObject *type, PyObject *iterable) |
953 | { |
954 | assert(PyType_Check(type)); |
955 | PySetObject *so; |
956 | |
957 | so = (PySetObject *)type->tp_alloc(type, 0); |
958 | if (so == NULL) Branch (958:9): [True: 0, False: 3.20M]
|
959 | return NULL; |
960 | |
961 | so->fill = 0; |
962 | so->used = 0; |
963 | so->mask = PySet_MINSIZE - 1; |
964 | so->table = so->smalltable; |
965 | so->hash = -1; |
966 | so->finger = 0; |
967 | so->weakreflist = NULL; |
968 | |
969 | if (iterable != NULL) { Branch (969:9): [True: 1.78M, False: 1.41M]
|
970 | if (set_update_internal(so, iterable)) { Branch (970:13): [True: 102, False: 1.78M]
|
971 | Py_DECREF(so); |
972 | return NULL; |
973 | } |
974 | } |
975 | |
976 | return (PyObject *)so; |
977 | } |
978 | |
979 | static PyObject * |
980 | make_new_set_basetype(PyTypeObject *type, PyObject *iterable) |
981 | { |
982 | if (type != &PySet_Type && type != &PyFrozenSet_Type3.22k ) { Branch (982:9): [True: 3.22k, False: 101k]
Branch (982:32): [True: 2.39k, False: 833]
|
983 | if (PyType_IsSubtype(type, &PySet_Type)) Branch (983:13): [True: 2.24k, False: 153]
|
984 | type = &PySet_Type; |
985 | else |
986 | type = &PyFrozenSet_Type; |
987 | } |
988 | return make_new_set(type, iterable); |
989 | } |
990 | |
991 | static PyObject * |
992 | make_new_frozenset(PyTypeObject *type, PyObject *iterable) |
993 | { |
994 | if (type != &PyFrozenSet_Type) { Branch (994:9): [True: 744, False: 1.07M]
|
995 | return make_new_set(type, iterable); |
996 | } |
997 | |
998 | if (iterable != NULL && PyFrozenSet_CheckExact1.07M (iterable)) { Branch (998:9): [True: 1.07M, False: 93]
|
999 | /* frozenset(f) is idempotent */ |
1000 | Py_INCREF(iterable); |
1001 | return iterable; |
1002 | } |
1003 | return make_new_set(type, iterable); |
1004 | } |
1005 | |
1006 | static PyObject * |
1007 | frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds) |
1008 | { |
1009 | PyObject *iterable = NULL; |
1010 | |
1011 | if ((type == &PyFrozenSet_Type || Branch (1011:10): [True: 0, False: 746]
|
1012 | type->tp_init == PyFrozenSet_Type.tp_init) && Branch (1012:10): [True: 745, False: 1]
|
1013 | !745 _PyArg_NoKeywords745 ("frozenset", kwds)) { |
1014 | return NULL; |
1015 | } |
1016 | |
1017 | if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable)) { Branch (1017:9): [True: 1, False: 744]
|
1018 | return NULL; |
1019 | } |
1020 | |
1021 | return make_new_frozenset(type, iterable); |
1022 | } |
1023 | |
1024 | static PyObject * |
1025 | frozenset_vectorcall(PyObject *type, PyObject * const*args, |
1026 | size_t nargsf, PyObject *kwnames) |
1027 | { |
1028 | if (!_PyArg_NoKwnames("frozenset", kwnames)) { |
1029 | return NULL; |
1030 | } |
1031 | |
1032 | Py_ssize_t nargs = PyVectorcall_NARGS(nargsf); |
1033 | if (!_PyArg_CheckPositional("frozenset", nargs, 0, 1)) { |
1034 | return NULL; |
1035 | } |
1036 | |
1037 | PyObject *iterable = (nargs ? args[0]1.07M : NULL); Branch (1037:27): [True: 1.07M, False: 93]
|
1038 | return make_new_frozenset(_PyType_CAST(type), iterable); |
1039 | } |
1040 | |
1041 | static PyObject * |
1042 | set_new(PyTypeObject *type, PyObject *args, PyObject *kwds) |
1043 | { |
1044 | 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 | 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 | t = a->fill; a->fill = b->fill; b->fill = t; |
1067 | t = a->used; a->used = b->used; b->used = t; |
1068 | t = a->mask; a->mask = b->mask; b->mask = t; |
1069 | |
1070 | u = a->table; |
1071 | if (a->table == a->smalltable) Branch (1071:9): [True: 611, False: 530]
|
1072 | u = b->smalltable; |
1073 | a->table = b->table; |
1074 | if (b->table == b->smalltable) Branch (1074:9): [True: 1.07k, False: 71]
|
1075 | a->table = a->smalltable; |
1076 | b->table = u; |
1077 | |
1078 | if (a->table == a->smalltable || b->table == b->smalltable71 ) { Branch (1078:9): [True: 1.07k, False: 71]
Branch (1078:38): [True: 42, False: 29]
|
1079 | memcpy(tab, a->smalltable, sizeof(tab)); |
1080 | memcpy(a->smalltable, b->smalltable, sizeof(tab)); |
1081 | memcpy(b->smalltable, tab, sizeof(tab)); |
1082 | } |
1083 | |
1084 | if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type) && Branch (1084:9): [True: 0, False: 1.14k]
|
1085 | PyType_IsSubtype(0 Py_TYPE0 (b), &PyFrozenSet_Type)) { Branch (1085:9): [True: 0, False: 0]
|
1086 | h = a->hash; a->hash = b->hash; b->hash = h; |
1087 | } else { |
1088 | a->hash = -1; |
1089 | b->hash = -1; |
1090 | } |
1091 | } |
1092 | |
1093 | static PyObject * |
1094 | set_copy(PySetObject *so, PyObject *Py_UNUSED(ignored)) |
1095 | { |
1096 | return make_new_set_basetype(Py_TYPE(so), (PyObject *)so); |
1097 | } |
1098 | |
1099 | static PyObject * |
1100 | frozenset_copy(PySetObject *so, PyObject *Py_UNUSED(ignored)) |
1101 | { |
1102 | if (PyFrozenSet_CheckExact(so)) { |
1103 | Py_INCREF(so); |
1104 | return (PyObject *)so; |
1105 | } |
1106 | return set_copy(so, NULL); |
1107 | } |
1108 | |
1109 | PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set."); |
1110 | |
1111 | static PyObject * |
1112 | set_clear(PySetObject *so, PyObject *Py_UNUSED(ignored)) |
1113 | { |
1114 | set_clear_internal(so); |
1115 | Py_RETURN_NONE; |
1116 | } |
1117 | |
1118 | PyDoc_STRVAR(clear_doc, "Remove all elements from this set."); |
1119 | |
1120 | static PyObject * |
1121 | set_union(PySetObject *so, PyObject *args) |
1122 | { |
1123 | PySetObject *result; |
1124 | PyObject *other; |
1125 | Py_ssize_t i; |
1126 | |
1127 | result = (PySetObject *)set_copy(so, NULL); |
1128 | if (result == NULL) Branch (1128:9): [True: 0, False: 864]
|
1129 | return NULL; |
1130 | |
1131 | for (i=0 ; 864 i<PyTuple_GET_SIZE(args) ; i++887 ) { Branch (1131:16): [True: 915, False: 836]
|
1132 | other = PyTuple_GET_ITEM(args, i); |
1133 | if ((PyObject *)so == other) Branch (1133:13): [True: 5, False: 910]
|
1134 | continue; |
1135 | if (set_update_internal(result, other)) { Branch (1135:13): [True: 28, False: 882]
|
1136 | Py_DECREF(result); |
1137 | return NULL; |
1138 | } |
1139 | } |
1140 | 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 | set_or(PySetObject *so, PyObject *other) |
1150 | { |
1151 | PySetObject *result; |
1152 | |
1153 | if (!PyAnySet_Check(so) || !22.5k PyAnySet_Check22.5k (other)) |
1154 | Py_RETURN_NOTIMPLEMENTED; |
1155 | |
1156 | result = (PySetObject *)set_copy(so, NULL); |
1157 | if (result == NULL) Branch (1157:9): [True: 0, False: 22.5k]
|
1158 | return NULL; |
1159 | if ((PyObject *)so == other) Branch (1159:9): [True: 7, False: 22.5k]
|
1160 | return (PyObject *)result; |
1161 | if (set_update_internal(result, other)) { Branch (1161:9): [True: 0, False: 22.5k]
|
1162 | Py_DECREF(result); |
1163 | return NULL; |
1164 | } |
1165 | return (PyObject *)result; |
1166 | } |
1167 | |
1168 | static PyObject * |
1169 | set_ior(PySetObject *so, PyObject *other) |
1170 | { |
1171 | if (!PyAnySet_Check(other)) |
1172 | Py_RETURN_NOTIMPLEMENTED; |
1173 | |
1174 | if (set_update_internal(so, other)) Branch (1174:9): [True: 0, False: 294k]
|
1175 | return NULL; |
1176 | Py_INCREF(so); |
1177 | return (PyObject *)so; |
1178 | } |
1179 | |
1180 | static PyObject * |
1181 | 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 | if ((PyObject *)so == other) Branch (1188:9): [True: 9, False: 20.5k]
|
1189 | return set_copy(so, NULL); |
1190 | |
1191 | result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL); |
1192 | if (result == NULL) Branch (1192:9): [True: 0, False: 20.5k]
|
1193 | return NULL; |
1194 | |
1195 | if (PyAnySet_Check(other)) { |
1196 | Py_ssize_t pos = 0; |
1197 | setentry *entry; |
1198 | |
1199 | if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) { Branch (1199:13): [True: 5.63k, False: 11.2k]
|
1200 | tmp = (PyObject *)so; |
1201 | so = (PySetObject *)other; |
1202 | other = tmp; |
1203 | } |
1204 | |
1205 | while (set_next((PySetObject *)other, &pos, &entry)) { Branch (1205:16): [True: 39.6k, False: 16.8k]
|
1206 | key = entry->key; |
1207 | hash = entry->hash; |
1208 | Py_INCREF(key); |
1209 | rv = set_contains_entry(so, key, hash); |
1210 | if (rv < 0) { Branch (1210:17): [True: 0, False: 39.6k]
|
1211 | Py_DECREF(result); |
1212 | Py_DECREF(key); |
1213 | return NULL; |
1214 | } |
1215 | if (rv) { Branch (1215:17): [True: 9.42k, False: 30.2k]
|
1216 | if (set_add_entry(result, key, hash)) { Branch (1216:21): [True: 0, False: 9.42k]
|
1217 | Py_DECREF(result); |
1218 | Py_DECREF(key); |
1219 | return NULL; |
1220 | } |
1221 | } |
1222 | Py_DECREF(key); |
1223 | } |
1224 | return (PyObject *)result; |
1225 | } |
1226 | |
1227 | it = PyObject_GetIter(other); |
1228 | if (it == NULL) { Branch (1228:9): [True: 28, False: 3.62k]
|
1229 | Py_DECREF(result); |
1230 | return NULL; |
1231 | } |
1232 | |
1233 | while (3.62k (key = PyIter_Next(it)) != NULL) { Branch (1233:12): [True: 78.2k, False: 3.13k]
|
1234 | hash = PyObject_Hash(key); |
1235 | if (hash == -1) Branch (1235:13): [True: 2, False: 78.2k]
|
1236 | goto error; |
1237 | rv = set_contains_entry(so, key, hash); |
1238 | if (rv < 0) Branch (1238:13): [True: 0, False: 78.2k]
|
1239 | goto error; |
1240 | if (rv) { Branch (1240:13): [True: 15.5k, False: 62.7k]
|
1241 | if (set_add_entry(result, key, hash)) Branch (1241:17): [True: 0, False: 15.5k]
|
1242 | goto error; |
1243 | if (PySet_GET_SIZE(result) >= PySet_GET_SIZE(so)) { Branch (1243:17): [True: 486, False: 15.0k]
|
1244 | Py_DECREF(key); |
1245 | break; |
1246 | } |
1247 | } |
1248 | Py_DECREF(key); |
1249 | } |
1250 | Py_DECREF(it); |
1251 | if (PyErr_Occurred()) { Branch (1251:9): [True: 140, False: 3.47k]
|
1252 | Py_DECREF(result); |
1253 | return NULL; |
1254 | } |
1255 | return (PyObject *)result; |
1256 | error: |
1257 | Py_DECREF(it); |
1258 | Py_DECREF(result); |
1259 | Py_DECREF(key); |
1260 | return NULL; |
1261 | } |
1262 | |
1263 | static PyObject * |
1264 | set_intersection_multi(PySetObject *so, PyObject *args) |
1265 | { |
1266 | Py_ssize_t i; |
1267 | PyObject *result = (PyObject *)so; |
1268 | |
1269 | if (PyTuple_GET_SIZE(args) == 0) Branch (1269:9): [True: 4, False: 5.06k]
|
1270 | return set_copy(so, NULL); |
1271 | |
1272 | Py_INCREF(so); |
1273 | for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++5.00k ) { Branch (1273:16): [True: 5.13k, False: 4.93k]
|
1274 | PyObject *other = PyTuple_GET_ITEM(args, i); |
1275 | PyObject *newresult = set_intersection((PySetObject *)result, other); |
1276 | if (newresult == NULL) { Branch (1276:13): [True: 132, False: 5.00k]
|
1277 | Py_DECREF(result); |
1278 | return NULL; |
1279 | } |
1280 | Py_DECREF(result); |
1281 | result = newresult; |
1282 | } |
1283 | 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 | set_intersection_update(PySetObject *so, PyObject *other) |
1293 | { |
1294 | PyObject *tmp; |
1295 | |
1296 | tmp = set_intersection(so, other); |
1297 | if (tmp == NULL) Branch (1297:9): [True: 0, False: 408]
|
1298 | return NULL; |
1299 | set_swap_bodies(so, (PySetObject *)tmp); |
1300 | Py_DECREF(tmp); |
1301 | Py_RETURN_NONE; |
1302 | } |
1303 | |
1304 | static PyObject * |
1305 | set_intersection_update_multi(PySetObject *so, PyObject *args) |
1306 | { |
1307 | PyObject *tmp; |
1308 | |
1309 | tmp = set_intersection_multi(so, args); |
1310 | if (tmp == NULL) Branch (1310:9): [True: 70, False: 733]
|
1311 | return NULL; |
1312 | set_swap_bodies(so, (PySetObject *)tmp); |
1313 | Py_DECREF(tmp); |
1314 | 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 | set_and(PySetObject *so, PyObject *other) |
1322 | { |
1323 | if (!PyAnySet_Check(so) || !14.7k PyAnySet_Check14.7k (other)) |
1324 | Py_RETURN_NOTIMPLEMENTED; |
1325 | return set_intersection(so, other); |
1326 | } |
1327 | |
1328 | static PyObject * |
1329 | set_iand(PySetObject *so, PyObject *other) |
1330 | { |
1331 | PyObject *result; |
1332 | |
1333 | if (!PyAnySet_Check(other)) |
1334 | Py_RETURN_NOTIMPLEMENTED; |
1335 | result = set_intersection_update(so, other); |
1336 | if (result == NULL) Branch (1336:9): [True: 0, False: 408]
|
1337 | return NULL; |
1338 | Py_DECREF(result); |
1339 | Py_INCREF(so); |
1340 | return (PyObject *)so; |
1341 | } |
1342 | |
1343 | static PyObject * |
1344 | set_isdisjoint(PySetObject *so, PyObject *other) |
1345 | { |
1346 | PyObject *key, *it, *tmp; |
1347 | int rv; |
1348 | |
1349 | if ((PyObject *)so == other) { Branch (1349:9): [True: 7, False: 4.05k]
|
1350 | if (PySet_GET_SIZE(so) == 0) Branch (1350:13): [True: 1, False: 6]
|
1351 | Py_RETURN_TRUE; |
1352 | else |
1353 | Py_RETURN_FALSE; |
1354 | } |
1355 | |
1356 | if (PyAnySet_CheckExact(other)) { |
1357 | Py_ssize_t pos = 0; |
1358 | setentry *entry; |
1359 | |
1360 | if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) { Branch (1360:13): [True: 388, False: 630]
|
1361 | tmp = (PyObject *)so; |
1362 | so = (PySetObject *)other; |
1363 | other = tmp; |
1364 | } |
1365 | while (set_next((PySetObject *)other, &pos, &entry)) { Branch (1365:16): [True: 1.33k, False: 495]
|
1366 | PyObject *key = entry->key; |
1367 | Py_INCREF(key); |
1368 | rv = set_contains_entry(so, key, entry->hash); |
1369 | Py_DECREF(key); |
1370 | if (rv < 0) { Branch (1370:17): [True: 0, False: 1.33k]
|
1371 | return NULL; |
1372 | } |
1373 | if (rv) { Branch (1373:17): [True: 523, False: 809]
|
1374 | Py_RETURN_FALSE; |
1375 | } |
1376 | } |
1377 | Py_RETURN_TRUE495 ; |
1378 | } |
1379 | |
1380 | it = PyObject_GetIter(other); |
1381 | if (it == NULL) Branch (1381:9): [True: 12, False: 3.02k]
|
1382 | return NULL; |
1383 | |
1384 | while (3.02k (key = PyIter_Next(it)) != NULL) { Branch (1384:12): [True: 18.3k, False: 1.88k]
|
1385 | rv = set_contains_key(so, key); |
1386 | Py_DECREF(key); |
1387 | if (rv < 0) { Branch (1387:13): [True: 0, False: 18.3k]
|
1388 | Py_DECREF(it); |
1389 | return NULL; |
1390 | } |
1391 | if (rv) { Branch (1391:13): [True: 1.14k, False: 17.2k]
|
1392 | Py_DECREF(it); |
1393 | Py_RETURN_FALSE; |
1394 | } |
1395 | } |
1396 | Py_DECREF(it); |
1397 | if (PyErr_Occurred()) Branch (1397:9): [True: 10, False: 1.87k]
|
1398 | return NULL; |
1399 | Py_RETURN_TRUE1.87k ; |
1400 | } |
1401 | |
1402 | PyDoc_STRVAR(isdisjoint_doc, |
1403 | "Return True if two sets have a null intersection."); |
1404 | |
1405 | static int |
1406 | set_difference_update_internal(PySetObject *so, PyObject *other) |
1407 | { |
1408 | if ((PyObject *)so == other) Branch (1408:9): [True: 2, False: 13.9k]
|
1409 | return set_clear_internal(so); |
1410 | |
1411 | if (PyAnySet_Check(other)) { |
1412 | setentry *entry; |
1413 | 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 | if ((PySet_GET_SIZE(other) >> 3) > PySet_GET_SIZE(so)) { Branch (1419:13): [True: 45, False: 6.52k]
|
1420 | other = set_intersection(so, other); |
1421 | if (other == NULL) Branch (1421:17): [True: 0, False: 45]
|
1422 | return -1; |
1423 | } else { |
1424 | Py_INCREF(other); |
1425 | } |
1426 | |
1427 | while (6.56k set_next((PySetObject *)other, &pos, &entry)) { Branch (1427:16): [True: 29.0k, False: 6.56k]
|
1428 | PyObject *key = entry->key; |
1429 | Py_INCREF(key); |
1430 | if (set_discard_entry(so, key, entry->hash) < 0) { Branch (1430:17): [True: 0, False: 29.0k]
|
1431 | Py_DECREF(other); |
1432 | Py_DECREF(key); |
1433 | return -1; |
1434 | } |
1435 | Py_DECREF(key); |
1436 | } |
1437 | |
1438 | Py_DECREF(other); |
1439 | } else { |
1440 | PyObject *key, *it; |
1441 | it = PyObject_GetIter(other); |
1442 | if (it == NULL) Branch (1442:13): [True: 45, False: 7.34k]
|
1443 | return -1; |
1444 | |
1445 | while (7.34k (key = PyIter_Next(it)) != NULL) { Branch (1445:16): [True: 29.8k, False: 7.33k]
|
1446 | if (set_discard_key(so, key) < 0) { Branch (1446:17): [True: 6, False: 29.8k]
|
1447 | Py_DECREF(it); |
1448 | Py_DECREF(key); |
1449 | return -1; |
1450 | } |
1451 | Py_DECREF(key); |
1452 | } |
1453 | Py_DECREF(it); |
1454 | if (PyErr_Occurred()) Branch (1454:13): [True: 64, False: 7.27k]
|
1455 | return -1; |
1456 | } |
1457 | /* If more than 1/4th are dummies, then resize them away. */ |
1458 | if ((size_t)(so->fill - so->used) <= (size_t)so->mask / 4) Branch (1458:9): [True: 12.8k, False: 1.00k]
|
1459 | return 0; |
1460 | return set_table_resize(so, so->used>50000 ? so->used*20 : so->used*4); Branch (1460:33): [True: 0, False: 1.00k]
|
1461 | } |
1462 | |
1463 | static PyObject * |
1464 | set_difference_update(PySetObject *so, PyObject *args) |
1465 | { |
1466 | Py_ssize_t i; |
1467 | |
1468 | for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++7.54k ) { Branch (1468:16): [True: 7.62k, False: 7.54k]
|
1469 | PyObject *other = PyTuple_GET_ITEM(args, i); |
1470 | if (set_difference_update_internal(so, other)) Branch (1470:13): [True: 76, False: 7.54k]
|
1471 | return NULL; |
1472 | } |
1473 | Py_RETURN_NONE7.54k ; |
1474 | } |
1475 | |
1476 | PyDoc_STRVAR(difference_update_doc, |
1477 | "Remove all elements of another set from this set."); |
1478 | |
1479 | static PyObject * |
1480 | set_copy_and_difference(PySetObject *so, PyObject *other) |
1481 | { |
1482 | PyObject *result; |
1483 | |
1484 | result = set_copy(so, NULL); |
1485 | if (result == NULL) Branch (1485:9): [True: 0, False: 5.86k]
|
1486 | return NULL; |
1487 | if (set_difference_update_internal((PySetObject *) result, other) == 0) Branch (1487:9): [True: 5.83k, False: 39]
|
1488 | return result; |
1489 | Py_DECREF(result); |
1490 | return NULL; |
1491 | } |
1492 | |
1493 | static PyObject * |
1494 | set_difference(PySetObject *so, PyObject *other) |
1495 | { |
1496 | PyObject *result; |
1497 | PyObject *key; |
1498 | Py_hash_t hash; |
1499 | setentry *entry; |
1500 | Py_ssize_t pos = 0, other_size; |
1501 | int rv; |
1502 | |
1503 | if (PyAnySet_Check(other)) { |
1504 | other_size = PySet_GET_SIZE(other); |
1505 | } |
1506 | else if (PyDict_CheckExact(other)) { |
1507 | other_size = PyDict_GET_SIZE(other); |
1508 | } |
1509 | else { |
1510 | 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 | if ((PySet_GET_SIZE(so) >> 2) > other_size) { Branch (1515:9): [True: 5.59k, False: 52.6k]
|
1516 | return set_copy_and_difference(so, other); |
1517 | } |
1518 | |
1519 | result = make_new_set_basetype(Py_TYPE(so), NULL); |
1520 | if (result == NULL) Branch (1520:9): [True: 0, False: 52.6k]
|
1521 | return NULL; |
1522 | |
1523 | if (PyDict_CheckExact(other)) { |
1524 | while (set_next(so, &pos, &entry)) { Branch (1524:16): [True: 1.03k, False: 116]
|
1525 | key = entry->key; |
1526 | hash = entry->hash; |
1527 | Py_INCREF(key); |
1528 | rv = _PyDict_Contains_KnownHash(other, key, hash); |
1529 | if (rv < 0) { Branch (1529:17): [True: 0, False: 1.03k]
|
1530 | Py_DECREF(result); |
1531 | Py_DECREF(key); |
1532 | return NULL; |
1533 | } |
1534 | if (!rv) { Branch (1534:17): [True: 570, False: 460]
|
1535 | if (set_add_entry((PySetObject *)result, key, hash)) { Branch (1535:21): [True: 0, False: 570]
|
1536 | Py_DECREF(result); |
1537 | Py_DECREF(key); |
1538 | return NULL; |
1539 | } |
1540 | } |
1541 | Py_DECREF(key); |
1542 | } |
1543 | return result; |
1544 | } |
1545 | |
1546 | /* Iterate over so, checking for common elements in other. */ |
1547 | while (52.5k set_next(so, &pos, &entry)) { Branch (1547:12): [True: 1.04M, False: 52.5k]
|
1548 | key = entry->key; |
1549 | hash = entry->hash; |
1550 | Py_INCREF(key); |
1551 | rv = set_contains_entry((PySetObject *)other, key, hash); |
1552 | if (rv < 0) { Branch (1552:13): [True: 0, False: 1.04M]
|
1553 | Py_DECREF(result); |
1554 | Py_DECREF(key); |
1555 | return NULL; |
1556 | } |
1557 | if (!rv) { Branch (1557:13): [True: 11.9k, False: 1.03M]
|
1558 | if (set_add_entry((PySetObject *)result, key, hash)) { Branch (1558:17): [True: 0, False: 11.9k]
|
1559 | Py_DECREF(result); |
1560 | Py_DECREF(key); |
1561 | return NULL; |
1562 | } |
1563 | } |
1564 | Py_DECREF(key); |
1565 | } |
1566 | return result; |
1567 | } |
1568 | |
1569 | static PyObject * |
1570 | set_difference_multi(PySetObject *so, PyObject *args) |
1571 | { |
1572 | Py_ssize_t i; |
1573 | PyObject *result, *other; |
1574 | |
1575 | if (PyTuple_GET_SIZE(args) == 0) Branch (1575:9): [True: 24, False: 39.1k]
|
1576 | return set_copy(so, NULL); |
1577 | |
1578 | other = PyTuple_GET_ITEM(args, 0); |
1579 | result = set_difference(so, other); |
1580 | if (result == NULL) Branch (1580:9): [True: 39, False: 39.1k]
|
1581 | return NULL; |
1582 | |
1583 | for (i=1 ; 39.1k i<PyTuple_GET_SIZE(args) ; i++24 ) { Branch (1583:16): [True: 24, False: 39.1k]
|
1584 | other = PyTuple_GET_ITEM(args, i); |
1585 | if (set_difference_update_internal((PySetObject *)result, other)) { Branch (1585:13): [True: 0, False: 24]
|
1586 | Py_DECREF(result); |
1587 | return NULL; |
1588 | } |
1589 | } |
1590 | 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 | set_sub(PySetObject *so, PyObject *other) |
1599 | { |
1600 | if (!PyAnySet_Check(so) || !19.3k PyAnySet_Check19.3k (other)) |
1601 | Py_RETURN_NOTIMPLEMENTED; |
1602 | return set_difference(so, other); |
1603 | } |
1604 | |
1605 | static PyObject * |
1606 | set_isub(PySetObject *so, PyObject *other) |
1607 | { |
1608 | if (!PyAnySet_Check(other)) |
1609 | Py_RETURN_NOTIMPLEMENTED; |
1610 | if (set_difference_update_internal(so, other)) Branch (1610:9): [True: 0, False: 439]
|
1611 | return NULL; |
1612 | Py_INCREF(so); |
1613 | return (PyObject *)so; |
1614 | } |
1615 | |
1616 | static PyObject * |
1617 | set_symmetric_difference_update(PySetObject *so, PyObject *other) |
1618 | { |
1619 | PySetObject *otherset; |
1620 | PyObject *key; |
1621 | Py_ssize_t pos = 0; |
1622 | Py_hash_t hash; |
1623 | setentry *entry; |
1624 | int rv; |
1625 | |
1626 | if ((PyObject *)so == other) Branch (1626:9): [True: 2, False: 2.70k]
|
1627 | return set_clear(so, NULL); |
1628 | |
1629 | if (PyDict_CheckExact(other)) { |
1630 | PyObject *value; |
1631 | while (_PyDict_Next(other, &pos, &key, &value, &hash)) { Branch (1631:16): [True: 1.09k, False: 112]
|
1632 | Py_INCREF(key); |
1633 | rv = set_discard_entry(so, key, hash); |
1634 | if (rv < 0) { Branch (1634:17): [True: 0, False: 1.09k]
|
1635 | Py_DECREF(key); |
1636 | return NULL; |
1637 | } |
1638 | if (rv == DISCARD_NOTFOUND) { Branch (1638:17): [True: 446, False: 652]
|
1639 | if (set_add_entry(so, key, hash)) { Branch (1639:21): [True: 0, False: 446]
|
1640 | Py_DECREF(key); |
1641 | return NULL; |
1642 | } |
1643 | } |
1644 | Py_DECREF(key); |
1645 | } |
1646 | Py_RETURN_NONE; |
1647 | } |
1648 | |
1649 | if (PyAnySet_Check(other)) { |
1650 | Py_INCREF(other); |
1651 | otherset = (PySetObject *)other; |
1652 | } else { |
1653 | otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other); |
1654 | if (otherset == NULL) Branch (1654:13): [True: 31, False: 215]
|
1655 | return NULL; |
1656 | } |
1657 | |
1658 | while (2.56k set_next(otherset, &pos, &entry)) { Branch (1658:12): [True: 30.3k, False: 2.56k]
|
1659 | key = entry->key; |
1660 | hash = entry->hash; |
1661 | Py_INCREF(key); |
1662 | rv = set_discard_entry(so, key, hash); |
1663 | if (rv < 0) { Branch (1663:13): [True: 0, False: 30.3k]
|
1664 | Py_DECREF(otherset); |
1665 | Py_DECREF(key); |
1666 | return NULL; |
1667 | } |
1668 | if (rv == DISCARD_NOTFOUND) { Branch (1668:13): [True: 18.1k, False: 12.2k]
|
1669 | if (set_add_entry(so, key, hash)) { Branch (1669:17): [True: 0, False: 18.1k]
|
1670 | Py_DECREF(otherset); |
1671 | Py_DECREF(key); |
1672 | return NULL; |
1673 | } |
1674 | } |
1675 | Py_DECREF(key); |
1676 | } |
1677 | Py_DECREF(otherset); |
1678 | 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 | set_symmetric_difference(PySetObject *so, PyObject *other) |
1686 | { |
1687 | PyObject *rv; |
1688 | PySetObject *otherset; |
1689 | |
1690 | otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other); |
1691 | if (otherset == NULL) Branch (1691:9): [True: 28, False: 1.52k]
|
1692 | return NULL; |
1693 | rv = set_symmetric_difference_update(otherset, (PyObject *)so); |
1694 | if (rv == NULL) { Branch (1694:9): [True: 0, False: 1.52k]
|
1695 | Py_DECREF(otherset); |
1696 | return NULL; |
1697 | } |
1698 | Py_DECREF(rv); |
1699 | 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 | set_xor(PySetObject *so, PyObject *other) |
1709 | { |
1710 | if (!PyAnySet_Check(so) || !768 PyAnySet_Check768 (other)) |
1711 | Py_RETURN_NOTIMPLEMENTED; |
1712 | return set_symmetric_difference(so, other); |
1713 | } |
1714 | |
1715 | static PyObject * |
1716 | set_ixor(PySetObject *so, PyObject *other) |
1717 | { |
1718 | PyObject *result; |
1719 | |
1720 | if (!PyAnySet_Check(other)) |
1721 | Py_RETURN_NOTIMPLEMENTED; |
1722 | result = set_symmetric_difference_update(so, other); |
1723 | if (result == NULL) Branch (1723:9): [True: 0, False: 408]
|
1724 | return NULL; |
1725 | Py_DECREF(result); |
1726 | Py_INCREF(so); |
1727 | return (PyObject *)so; |
1728 | } |
1729 | |
1730 | static PyObject * |
1731 | set_issubset(PySetObject *so, PyObject *other) |
1732 | { |
1733 | setentry *entry; |
1734 | Py_ssize_t pos = 0; |
1735 | int rv; |
1736 | |
1737 | if (!PyAnySet_Check(other)) { |
1738 | PyObject *tmp = set_intersection(so, other); |
1739 | if (tmp == NULL) { Branch (1739:13): [True: 38, False: 175]
|
1740 | return NULL; |
1741 | } |
1742 | int result = (PySet_GET_SIZE(tmp) == PySet_GET_SIZE(so)); |
1743 | Py_DECREF(tmp); |
1744 | return PyBool_FromLong(result); |
1745 | } |
1746 | if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other)) Branch (1746:9): [True: 3.63k, False: 32.2k]
|
1747 | Py_RETURN_FALSE; |
1748 | |
1749 | while (32.2k set_next(so, &pos, &entry)) { Branch (1749:12): [True: 56.8k, False: 27.7k]
|
1750 | PyObject *key = entry->key; |
1751 | Py_INCREF(key); |
1752 | rv = set_contains_entry((PySetObject *)other, key, entry->hash); |
1753 | Py_DECREF(key); |
1754 | if (rv < 0) { Branch (1754:13): [True: 0, False: 56.8k]
|
1755 | return NULL; |
1756 | } |
1757 | if (!rv) { Branch (1757:13): [True: 4.50k, False: 52.3k]
|
1758 | Py_RETURN_FALSE; |
1759 | } |
1760 | } |
1761 | Py_RETURN_TRUE27.7k ; |
1762 | } |
1763 | |
1764 | PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set."); |
1765 | |
1766 | static PyObject * |
1767 | set_issuperset(PySetObject *so, PyObject *other) |
1768 | { |
1769 | if (PyAnySet_Check(other)) { |
1770 | return set_issubset((PySetObject *)other, (PyObject *)so); |
1771 | } |
1772 | |
1773 | PyObject *key, *it = PyObject_GetIter(other); |
1774 | if (it == NULL) { Branch (1774:9): [True: 0, False: 7.29k]
|
1775 | return NULL; |
1776 | } |
1777 | while (7.29k (key = PyIter_Next(it)) != NULL) { Branch (1777:12): [True: 19.7k, False: 7.15k]
|
1778 | int rv = set_contains_key(so, key); |
1779 | Py_DECREF(key); |
1780 | if (rv < 0) { Branch (1780:13): [True: 0, False: 19.7k]
|
1781 | Py_DECREF(it); |
1782 | return NULL; |
1783 | } |
1784 | if (!rv) { Branch (1784:13): [True: 143, False: 19.6k]
|
1785 | Py_DECREF(it); |
1786 | Py_RETURN_FALSE; |
1787 | } |
1788 | } |
1789 | Py_DECREF(it); |
1790 | if (PyErr_Occurred()) { Branch (1790:9): [True: 34, False: 7.12k]
|
1791 | return NULL; |
1792 | } |
1793 | Py_RETURN_TRUE7.12k ; |
1794 | } |
1795 | |
1796 | PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set."); |
1797 | |
1798 | static PyObject * |
1799 | set_richcompare(PySetObject *v, PyObject *w, int op) |
1800 | { |
1801 | PyObject *r1; |
1802 | int r2; |
1803 | |
1804 | if(!PyAnySet_Check(w)) |
1805 | Py_RETURN_NOTIMPLEMENTED; |
1806 | |
1807 | switch (op) { Branch (1807:13): [True: 0, False: 54.3k]
|
1808 | case Py_EQ: Branch (1808:5): [True: 25.4k, False: 28.8k]
|
1809 | if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w)) Branch (1809:13): [True: 6.73k, False: 18.7k]
|
1810 | Py_RETURN_FALSE; |
1811 | if (v->hash != -1 && Branch (1811:13): [True: 10.0k, False: 8.72k]
|
1812 | ((PySetObject *)w)->hash != -110.0k && Branch (1812:13): [True: 10.0k, False: 28]
|
1813 | v->hash != ((PySetObject *)w)->hash10.0k ) Branch (1813:13): [True: 1.94k, False: 8.06k]
|
1814 | Py_RETURN_FALSE; |
1815 | return set_issubset(v, w); |
1816 | case Py_NE: Branch (1816:5): [True: 4.72k, False: 49.6k]
|
1817 | r1 = set_richcompare(v, w, Py_EQ); |
1818 | if (r1 == NULL) Branch (1818:13): [True: 0, False: 4.72k]
|
1819 | return NULL; |
1820 | r2 = PyObject_IsTrue(r1); |
1821 | Py_DECREF(r1); |
1822 | if (r2 < 0) Branch (1822:13): [True: 0, False: 4.72k]
|
1823 | return NULL; |
1824 | return PyBool_FromLong(!r2); |
1825 | case Py_LE: Branch (1825:5): [True: 10.4k, False: 43.9k]
|
1826 | return set_issubset(v, w); |
1827 | case Py_GE: Branch (1827:5): [True: 4.54k, False: 49.8k]
|
1828 | return set_issuperset(v, w); |
1829 | case Py_LT: Branch (1829:5): [True: 4.64k, False: 49.7k]
|
1830 | if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w)) Branch (1830:13): [True: 3.00k, False: 1.63k]
|
1831 | Py_RETURN_FALSE; |
1832 | return set_issubset(v, w); |
1833 | case Py_GT: Branch (1833:5): [True: 4.52k, False: 49.8k]
|
1834 | if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w)) Branch (1834:13): [True: 2.89k, False: 1.62k]
|
1835 | Py_RETURN_FALSE; |
1836 | return set_issuperset(v, w); |
1837 | } |
1838 | Py_RETURN_NOTIMPLEMENTED0 ; |
1839 | } |
1840 | |
1841 | static PyObject * |
1842 | set_add(PySetObject *so, PyObject *key) |
1843 | { |
1844 | if (set_add_key(so, key)) Branch (1844:9): [True: 4, False: 706k]
|
1845 | return NULL; |
1846 | Py_RETURN_NONE706k ; |
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 | set_contains(PySetObject *so, PyObject *key) |
1856 | { |
1857 | PyObject *tmpkey; |
1858 | int rv; |
1859 | |
1860 | rv = set_contains_key(so, key); |
1861 | if (rv < 0) { Branch (1861:9): [True: 18, False: 6.49M]
|
1862 | if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError)10 ) Branch (1862:34): [True: 0, False: 10]
|
1863 | return -1; |
1864 | PyErr_Clear(); |
1865 | tmpkey = make_new_set(&PyFrozenSet_Type, key); |
1866 | if (tmpkey == NULL) Branch (1866:13): [True: 0, False: 10]
|
1867 | return -1; |
1868 | rv = set_contains_key(so, tmpkey); |
1869 | Py_DECREF(tmpkey); |
1870 | } |
1871 | return rv; |
1872 | } |
1873 | |
1874 | static PyObject * |
1875 | set_direct_contains(PySetObject *so, PyObject *key) |
1876 | { |
1877 | long result; |
1878 | |
1879 | result = set_contains(so, key); |
1880 | if (result < 0) Branch (1880:9): [True: 8, False: 351k]
|
1881 | return NULL; |
1882 | return PyBool_FromLong(result); |
1883 | } |
1884 | |
1885 | PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x."); |
1886 | |
1887 | static PyObject * |
1888 | set_remove(PySetObject *so, PyObject *key) |
1889 | { |
1890 | PyObject *tmpkey; |
1891 | int rv; |
1892 | |
1893 | rv = set_discard_key(so, key); |
1894 | if (rv < 0) { Branch (1894:9): [True: 10, False: 63.1k]
|
1895 | if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError)6 ) Branch (1895:34): [True: 0, False: 6]
|
1896 | return NULL; |
1897 | PyErr_Clear(); |
1898 | tmpkey = make_new_set(&PyFrozenSet_Type, key); |
1899 | if (tmpkey == NULL) Branch (1899:13): [True: 0, False: 6]
|
1900 | return NULL; |
1901 | rv = set_discard_key(so, tmpkey); |
1902 | Py_DECREF(tmpkey); |
1903 | if (rv < 0) Branch (1903:13): [True: 0, False: 6]
|
1904 | return NULL; |
1905 | } |
1906 | |
1907 | if (rv == DISCARD_NOTFOUND) { Branch (1907:9): [True: 17, False: 63.1k]
|
1908 | _PyErr_SetKeyError(key); |
1909 | return NULL; |
1910 | } |
1911 | Py_RETURN_NONE63.1k ; |
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 | set_discard(PySetObject *so, PyObject *key) |
1921 | { |
1922 | PyObject *tmpkey; |
1923 | int rv; |
1924 | |
1925 | rv = set_discard_key(so, key); |
1926 | if (rv < 0) { Branch (1926:9): [True: 8, False: 26.6k]
|
1927 | if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError)4 ) Branch (1927:34): [True: 0, False: 4]
|
1928 | return NULL; |
1929 | PyErr_Clear(); |
1930 | tmpkey = make_new_set(&PyFrozenSet_Type, key); |
1931 | if (tmpkey == NULL) Branch (1931:13): [True: 0, False: 4]
|
1932 | return NULL; |
1933 | rv = set_discard_key(so, tmpkey); |
1934 | Py_DECREF(tmpkey); |
1935 | if (rv < 0) Branch (1935:13): [True: 0, False: 4]
|
1936 | return NULL; |
1937 | } |
1938 | Py_RETURN_NONE26.6k ; |
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 | set_reduce(PySetObject *so, PyObject *Py_UNUSED(ignored)) |
1949 | { |
1950 | PyObject *keys=NULL, *args=NULL, *result=NULL, *state=NULL; |
1951 | |
1952 | keys = PySequence_List((PyObject *)so); |
1953 | if (keys == NULL) Branch (1953:9): [True: 0, False: 433]
|
1954 | goto done; |
1955 | args = PyTuple_Pack(1, keys); |
1956 | if (args == NULL) Branch (1956:9): [True: 0, False: 433]
|
1957 | goto done; |
1958 | state = _PyObject_GetState((PyObject *)so); |
1959 | if (state == NULL) Branch (1959:9): [True: 0, False: 433]
|
1960 | goto done; |
1961 | result = PyTuple_Pack(3, Py_TYPE(so), args, state); |
1962 | done: |
1963 | Py_XDECREF(args); |
1964 | Py_XDECREF(keys); |
1965 | Py_XDECREF(state); |
1966 | return result; |
1967 | } |
1968 | |
1969 | static PyObject * |
1970 | set_sizeof(PySetObject *so, PyObject *Py_UNUSED(ignored)) |
1971 | { |
1972 | Py_ssize_t res; |
1973 | |
1974 | res = _PyObject_SIZE(Py_TYPE(so)); |
1975 | if (so->table != so->smalltable) Branch (1975:9): [True: 4, False: 6]
|
1976 | res = res + (so->mask + 1) * sizeof(setentry); |
1977 | 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 | set_init(PySetObject *self, PyObject *args, PyObject *kwds) |
1983 | { |
1984 | PyObject *iterable = NULL; |
1985 | |
1986 | if (!_PyArg_NoKeywords("set", kwds)) |
1987 | return -1; |
1988 | if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable)) Branch (1988:9): [True: 3, False: 12.0k]
|
1989 | return -1; |
1990 | if (self->fill) Branch (1990:9): [True: 4, False: 12.0k]
|
1991 | set_clear_internal(self); |
1992 | self->hash = -1; |
1993 | if (iterable == NULL) Branch (1993:9): [True: 22, False: 12.0k]
|
1994 | return 0; |
1995 | return set_update_internal(self, iterable); |
1996 | } |
1997 | |
1998 | static PyObject* |
1999 | set_vectorcall(PyObject *type, PyObject * const*args, |
2000 | size_t nargsf, PyObject *kwnames) |
2001 | { |
2002 | assert(PyType_Check(type)); |
2003 | |
2004 | if (!_PyArg_NoKwnames("set", kwnames)) { |
2005 | return NULL; |
2006 | } |
2007 | |
2008 | Py_ssize_t nargs = PyVectorcall_NARGS(nargsf); |
2009 | if (!_PyArg_CheckPositional("set", nargs, 0, 1)) { |
2010 | return NULL; |
2011 | } |
2012 | |
2013 | if (nargs) { Branch (2013:9): [True: 604k, False: 102k]
|
2014 | return make_new_set(_PyType_CAST(type), args[0]); |
2015 | } |
2016 | |
2017 | 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 | PySet_New(PyObject *iterable) |
2279 | { |
2280 | return make_new_set(&PySet_Type, iterable); |
2281 | } |
2282 | |
2283 | PyObject * |
2284 | PyFrozenSet_New(PyObject *iterable) |
2285 | { |
2286 | return make_new_set(&PyFrozenSet_Type, iterable); |
2287 | } |
2288 | |
2289 | Py_ssize_t |
2290 | PySet_Size(PyObject *anyset) |
2291 | { |
2292 | if (!PyAnySet_Check(anyset)) { |
2293 | PyErr_BadInternalCall(); |
2294 | return -1; |
2295 | } |
2296 | return PySet_GET_SIZE(anyset); |
2297 | } |
2298 | |
2299 | int |
2300 | PySet_Clear(PyObject *set) |
2301 | { |
2302 | if (!PySet_Check(set)) { |
2303 | PyErr_BadInternalCall(); |
2304 | return -1; |
2305 | } |
2306 | return set_clear_internal((PySetObject *)set); |
2307 | } |
2308 | |
2309 | int |
2310 | PySet_Contains(PyObject *anyset, PyObject *key) |
2311 | { |
2312 | if (!PyAnySet_Check(anyset)) { |
2313 | PyErr_BadInternalCall(); |
2314 | return -1; |
2315 | } |
2316 | return set_contains_key((PySetObject *)anyset, key); |
2317 | } |
2318 | |
2319 | int |
2320 | PySet_Discard(PyObject *set, PyObject *key) |
2321 | { |
2322 | if (!PySet_Check(set)) { |
2323 | PyErr_BadInternalCall(); |
2324 | return -1; |
2325 | } |
2326 | return set_discard_key((PySetObject *)set, key); |
2327 | } |
2328 | |
2329 | int |
2330 | PySet_Add(PyObject *anyset, PyObject *key) |
2331 | { |
2332 | if (!PySet_Check(anyset) && |
2333 | (16.2k !16.2k PyFrozenSet_Check16.2k (anyset) || Py_REFCNT16.2k (anyset) != 116.2k )) { Branch (2333:40): [True: 0, False: 16.2k]
|
2334 | PyErr_BadInternalCall(); |
2335 | return -1; |
2336 | } |
2337 | return set_add_key((PySetObject *)anyset, key); |
2338 | } |
2339 | |
2340 | int |
2341 | _PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash) |
2342 | { |
2343 | setentry *entry; |
2344 | |
2345 | if (!PyAnySet_Check(set)) { |
2346 | PyErr_BadInternalCall(); |
2347 | return -1; |
2348 | } |
2349 | if (set_next((PySetObject *)set, pos, &entry) == 0) Branch (2349:9): [True: 5.40k, False: 30.6k]
|
2350 | return 0; |
2351 | *key = entry->key; |
2352 | *hash = entry->hash; |
2353 | return 1; |
2354 | } |
2355 | |
2356 | PyObject * |
2357 | PySet_Pop(PyObject *set) |
2358 | { |
2359 | if (!PySet_Check(set)) { |
2360 | PyErr_BadInternalCall(); |
2361 | return NULL; |
2362 | } |
2363 | return set_pop((PySetObject *)set, NULL); |
2364 | } |
2365 | |
2366 | int |
2367 | _PySet_Update(PyObject *set, PyObject *iterable) |
2368 | { |
2369 | if (!PySet_Check(set)) { |
2370 | PyErr_BadInternalCall(); |
2371 | return -1; |
2372 | } |
2373 | 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 | dummy_repr(PyObject *op) |
2525 | { |
2526 | return PyUnicode_FromString("<dummy key>"); |
2527 | } |
2528 | |
2529 | static void _Py_NO_RETURN |
2530 | 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 | }; |