source: trunk/essentials/dev-lang/python/Objects/setobject.c@ 3326

Last change on this file since 3326 was 3225, checked in by bird, 19 years ago

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