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