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