2 /* set object implementation
3 Written and maintained by Raymond D. Hettinger <python@rcn.com>
4 Derived from Lib/sets.py and Objects/dictobject.c.
6 Copyright (c) 2003-2007 Python Software Foundation.
11 #include "structmember.h"
13 /* Set a key error with the specified argument, wrapping it in a
14 * tuple automatically so that tuple keys are not unpacked as the
15 * exception arguments. */
17 set_key_error(PyObject
*arg
)
20 tup
= PyTuple_Pack(1, arg
);
22 return; /* caller will expect error to be set anyway */
23 PyErr_SetObject(PyExc_KeyError
, tup
);
27 /* This must be >= 1. */
28 #define PERTURB_SHIFT 5
30 /* Object used as dummy key to fill deleted entries */
31 static PyObject
*dummy
= NULL
; /* Initialized by first call to make_new_set() */
41 #define INIT_NONZERO_SET_SLOTS(so) do { \
42 (so)->table = (so)->smalltable; \
43 (so)->mask = PySet_MINSIZE - 1; \
47 #define EMPTY_TO_MINSIZE(so) do { \
48 memset((so)->smalltable, 0, sizeof((so)->smalltable)); \
49 (so)->used = (so)->fill = 0; \
50 INIT_NONZERO_SET_SLOTS(so); \
53 /* Reuse scheme to save calls to malloc, free, and memset */
54 #ifndef PySet_MAXFREELIST
55 #define PySet_MAXFREELIST 80
57 static PySetObject
*free_list
[PySet_MAXFREELIST
];
58 static int numfree
= 0;
61 The basic lookup function used by all operations.
62 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
63 Open addressing is preferred over chaining since the link overhead for
64 chaining would be substantial (100% with typical malloc overhead).
66 The initial probe index is computed as hash mod the table size. Subsequent
67 probe indices are computed as explained in Objects/dictobject.c.
69 All arithmetic on hash should ignore overflow.
71 Unlike the dictionary implementation, the lookkey functions can return
72 NULL if the rich comparison returns an error.
76 set_lookkey(PySetObject
*so
, PyObject
*key
, register long hash
)
78 register Py_ssize_t i
;
79 register size_t perturb
;
80 register setentry
*freeslot
;
81 register size_t mask
= so
->mask
;
82 setentry
*table
= so
->table
;
83 register setentry
*entry
;
89 if (entry
->key
== NULL
|| entry
->key
== key
)
92 if (entry
->key
== dummy
)
95 if (entry
->hash
== hash
) {
96 startkey
= entry
->key
;
98 cmp
= PyObject_RichCompareBool(startkey
, key
, Py_EQ
);
102 if (table
== so
->table
&& entry
->key
== startkey
) {
107 /* The compare did major nasty stuff to the
110 return set_lookkey(so
, key
, hash
);
116 /* In the loop, key == dummy is by far (factor of 100s) the
117 least likely outcome, so test for that last. */
118 for (perturb
= hash
; ; perturb
>>= PERTURB_SHIFT
) {
119 i
= (i
<< 2) + i
+ perturb
+ 1;
120 entry
= &table
[i
& mask
];
121 if (entry
->key
== NULL
) {
122 if (freeslot
!= NULL
)
126 if (entry
->key
== key
)
128 if (entry
->hash
== hash
&& entry
->key
!= dummy
) {
129 startkey
= entry
->key
;
131 cmp
= PyObject_RichCompareBool(startkey
, key
, Py_EQ
);
135 if (table
== so
->table
&& entry
->key
== startkey
) {
140 /* The compare did major nasty stuff to the
143 return set_lookkey(so
, key
, hash
);
146 else if (entry
->key
== dummy
&& freeslot
== NULL
)
153 * Hacked up version of set_lookkey which can assume keys are always strings;
154 * This means we can always use _PyString_Eq directly and not have to check to
155 * see if the comparison altered the table.
158 set_lookkey_string(PySetObject
*so
, PyObject
*key
, register long hash
)
160 register Py_ssize_t i
;
161 register size_t perturb
;
162 register setentry
*freeslot
;
163 register size_t mask
= so
->mask
;
164 setentry
*table
= so
->table
;
165 register setentry
*entry
;
167 /* Make sure this function doesn't have to handle non-string keys,
168 including subclasses of str; e.g., one reason to subclass
169 strings is to override __eq__, and for speed we don't cater to
171 if (!PyString_CheckExact(key
)) {
172 so
->lookup
= set_lookkey
;
173 return set_lookkey(so
, key
, hash
);
177 if (entry
->key
== NULL
|| entry
->key
== key
)
179 if (entry
->key
== dummy
)
182 if (entry
->hash
== hash
&& _PyString_Eq(entry
->key
, key
))
187 /* In the loop, key == dummy is by far (factor of 100s) the
188 least likely outcome, so test for that last. */
189 for (perturb
= hash
; ; perturb
>>= PERTURB_SHIFT
) {
190 i
= (i
<< 2) + i
+ perturb
+ 1;
191 entry
= &table
[i
& mask
];
192 if (entry
->key
== NULL
)
193 return freeslot
== NULL
? entry
: freeslot
;
194 if (entry
->key
== key
195 || (entry
->hash
== hash
196 && entry
->key
!= dummy
197 && _PyString_Eq(entry
->key
, key
)))
199 if (entry
->key
== dummy
&& freeslot
== NULL
)
202 assert(0); /* NOT REACHED */
207 Internal routine to insert a new key into the table.
208 Used by the public insert routine.
209 Eats a reference to key.
212 set_insert_key(register PySetObject
*so
, PyObject
*key
, long hash
)
214 register setentry
*entry
;
215 typedef setentry
*(*lookupfunc
)(PySetObject
*, PyObject
*, long);
217 assert(so
->lookup
!= NULL
);
218 entry
= so
->lookup(so
, key
, hash
);
221 if (entry
->key
== NULL
) {
227 } else if (entry
->key
== dummy
) {
241 Internal routine used by set_table_resize() to insert an item which is
242 known to be absent from the set. This routine also assumes that
243 the set contains no deleted entries. Besides the performance benefit,
244 using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
245 Note that no refcounts are changed by this routine; if needed, the caller
246 is responsible for incref'ing `key`.
249 set_insert_clean(register PySetObject
*so
, PyObject
*key
, long hash
)
252 register size_t perturb
;
253 register size_t mask
= (size_t)so
->mask
;
254 setentry
*table
= so
->table
;
255 register setentry
*entry
;
259 for (perturb
= hash
; entry
->key
!= NULL
; perturb
>>= PERTURB_SHIFT
) {
260 i
= (i
<< 2) + i
+ perturb
+ 1;
261 entry
= &table
[i
& mask
];
270 Restructure the table by allocating a new table and reinserting all
271 keys again. When entries have been deleted, the new table may
272 actually be smaller than the old one.
275 set_table_resize(PySetObject
*so
, Py_ssize_t minused
)
278 setentry
*oldtable
, *newtable
, *entry
;
280 int is_oldtable_malloced
;
281 setentry small_copy
[PySet_MINSIZE
];
283 assert(minused
>= 0);
285 /* Find the smallest table size > minused. */
286 for (newsize
= PySet_MINSIZE
;
287 newsize
<= minused
&& newsize
> 0;
295 /* Get space for a new table. */
296 oldtable
= so
->table
;
297 assert(oldtable
!= NULL
);
298 is_oldtable_malloced
= oldtable
!= so
->smalltable
;
300 if (newsize
== PySet_MINSIZE
) {
301 /* A large table is shrinking, or we can't get any smaller. */
302 newtable
= so
->smalltable
;
303 if (newtable
== oldtable
) {
304 if (so
->fill
== so
->used
) {
305 /* No dummies, so no point doing anything. */
308 /* We're not going to resize it, but rebuild the
309 table anyway to purge old dummy entries.
310 Subtle: This is *necessary* if fill==size,
311 as set_lookkey needs at least one virgin slot to
312 terminate failing searches. If fill < size, it's
313 merely desirable, as dummies slow searches. */
314 assert(so
->fill
> so
->used
);
315 memcpy(small_copy
, oldtable
, sizeof(small_copy
));
316 oldtable
= small_copy
;
320 newtable
= PyMem_NEW(setentry
, newsize
);
321 if (newtable
== NULL
) {
327 /* Make the set empty, using the new table. */
328 assert(newtable
!= oldtable
);
329 so
->table
= newtable
;
330 so
->mask
= newsize
- 1;
331 memset(newtable
, 0, sizeof(setentry
) * newsize
);
336 /* Copy the data over; this is refcount-neutral for active entries;
337 dummy entries aren't copied over, of course */
338 for (entry
= oldtable
; i
> 0; entry
++) {
339 if (entry
->key
== NULL
) {
342 } else if (entry
->key
== dummy
) {
345 assert(entry
->key
== dummy
);
346 Py_DECREF(entry
->key
);
350 set_insert_clean(so
, entry
->key
, entry
->hash
);
354 if (is_oldtable_malloced
)
359 /* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
362 set_add_entry(register PySetObject
*so
, setentry
*entry
)
364 register Py_ssize_t n_used
;
366 assert(so
->fill
<= so
->mask
); /* at least one empty slot */
368 Py_INCREF(entry
->key
);
369 if (set_insert_key(so
, entry
->key
, entry
->hash
) == -1) {
370 Py_DECREF(entry
->key
);
373 if (!(so
->used
> n_used
&& so
->fill
*3 >= (so
->mask
+1)*2))
375 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
379 set_add_key(register PySetObject
*so
, PyObject
*key
)
382 register Py_ssize_t n_used
;
384 if (!PyString_CheckExact(key
) ||
385 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
386 hash
= PyObject_Hash(key
);
390 assert(so
->fill
<= so
->mask
); /* at least one empty slot */
393 if (set_insert_key(so
, key
, hash
) == -1) {
397 if (!(so
->used
> n_used
&& so
->fill
*3 >= (so
->mask
+1)*2))
399 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
402 #define DISCARD_NOTFOUND 0
403 #define DISCARD_FOUND 1
406 set_discard_entry(PySetObject
*so
, setentry
*oldentry
)
407 { register setentry
*entry
;
410 entry
= (so
->lookup
)(so
, oldentry
->key
, oldentry
->hash
);
413 if (entry
->key
== NULL
|| entry
->key
== dummy
)
414 return DISCARD_NOTFOUND
;
415 old_key
= entry
->key
;
420 return DISCARD_FOUND
;
424 set_discard_key(PySetObject
*so
, PyObject
*key
)
427 register setentry
*entry
;
430 assert (PyAnySet_Check(so
));
431 if (!PyString_CheckExact(key
) ||
432 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
433 hash
= PyObject_Hash(key
);
437 entry
= (so
->lookup
)(so
, key
, hash
);
440 if (entry
->key
== NULL
|| entry
->key
== dummy
)
441 return DISCARD_NOTFOUND
;
442 old_key
= entry
->key
;
447 return DISCARD_FOUND
;
451 set_clear_internal(PySetObject
*so
)
453 setentry
*entry
, *table
;
454 int table_is_malloced
;
456 setentry small_copy
[PySet_MINSIZE
];
459 assert (PyAnySet_Check(so
));
466 assert(table
!= NULL
);
467 table_is_malloced
= table
!= so
->smalltable
;
469 /* This is delicate. During the process of clearing the set,
470 * decrefs can cause the set to mutate. To avoid fatal confusion
471 * (voice of experience), we have to make the set empty before
472 * clearing the slots, and never refer to anything via so->ref while
476 if (table_is_malloced
)
477 EMPTY_TO_MINSIZE(so
);
480 /* It's a small table with something that needs to be cleared.
481 * Afraid the only safe way is to copy the set entries into
482 * another small table first.
484 memcpy(small_copy
, table
, sizeof(small_copy
));
486 EMPTY_TO_MINSIZE(so
);
488 /* else it's a small table that's already empty */
490 /* Now we can finally clear things. If C had refcounts, we could
491 * assert that the refcount on table is 1 now, i.e. that this function
492 * has unique access to it, so decref side-effects can't alter it.
494 for (entry
= table
; fill
> 0; ++entry
) {
501 Py_DECREF(entry
->key
);
505 assert(entry
->key
== NULL
);
509 if (table_is_malloced
)
515 * Iterate over a set table. Use like so:
519 * pos = 0; # important! pos should not otherwise be changed by you
520 * while (set_next(yourset, &pos, &entry)) {
521 * Refer to borrowed reference in entry->key.
524 * CAUTION: In general, it isn't safe to use set_next in a loop that
528 set_next(PySetObject
*so
, Py_ssize_t
*pos_ptr
, setentry
**entry_ptr
)
532 register setentry
*table
;
534 assert (PyAnySet_Check(so
));
539 while (i
<= mask
&& (table
[i
].key
== NULL
|| table
[i
].key
== dummy
))
544 assert(table
[i
].key
!= NULL
);
545 *entry_ptr
= &table
[i
];
550 set_dealloc(PySetObject
*so
)
552 register setentry
*entry
;
553 Py_ssize_t fill
= so
->fill
;
554 PyObject_GC_UnTrack(so
);
555 Py_TRASHCAN_SAFE_BEGIN(so
)
556 if (so
->weakreflist
!= NULL
)
557 PyObject_ClearWeakRefs((PyObject
*) so
);
559 for (entry
= so
->table
; fill
> 0; entry
++) {
562 Py_DECREF(entry
->key
);
565 if (so
->table
!= so
->smalltable
)
566 PyMem_DEL(so
->table
);
567 if (numfree
< PySet_MAXFREELIST
&& PyAnySet_CheckExact(so
))
568 free_list
[numfree
++] = so
;
570 Py_TYPE(so
)->tp_free(so
);
571 Py_TRASHCAN_SAFE_END(so
)
575 set_tp_print(PySetObject
*so
, FILE *fp
, int flags
)
579 char *emit
= ""; /* No separator emitted on first pass */
580 char *separator
= ", ";
581 int status
= Py_ReprEnter((PyObject
*)so
);
586 Py_BEGIN_ALLOW_THREADS
587 fprintf(fp
, "%s(...)", so
->ob_type
->tp_name
);
592 Py_BEGIN_ALLOW_THREADS
593 fprintf(fp
, "%s([", so
->ob_type
->tp_name
);
595 while (set_next(so
, &pos
, &entry
)) {
596 Py_BEGIN_ALLOW_THREADS
600 if (PyObject_Print(entry
->key
, fp
, 0) != 0) {
601 Py_ReprLeave((PyObject
*)so
);
605 Py_BEGIN_ALLOW_THREADS
608 Py_ReprLeave((PyObject
*)so
);
613 set_repr(PySetObject
*so
)
615 PyObject
*keys
, *result
=NULL
, *listrepr
;
616 int status
= Py_ReprEnter((PyObject
*)so
);
621 return PyString_FromFormat("%s(...)", so
->ob_type
->tp_name
);
624 keys
= PySequence_List((PyObject
*)so
);
627 listrepr
= PyObject_Repr(keys
);
629 if (listrepr
== NULL
)
632 result
= PyString_FromFormat("%s(%s)", so
->ob_type
->tp_name
,
633 PyString_AS_STRING(listrepr
));
636 Py_ReprLeave((PyObject
*)so
);
641 set_len(PyObject
*so
)
643 return ((PySetObject
*)so
)->used
;
647 set_merge(PySetObject
*so
, PyObject
*otherset
)
650 register Py_ssize_t i
;
651 register setentry
*entry
;
653 assert (PyAnySet_Check(so
));
654 assert (PyAnySet_Check(otherset
));
656 other
= (PySetObject
*)otherset
;
657 if (other
== so
|| other
->used
== 0)
658 /* a.update(a) or a.update({}); nothing to do */
660 /* Do one big resize at the start, rather than
661 * incrementally resizing as we insert new keys. Expect
662 * that there will be no (or few) overlapping keys.
664 if ((so
->fill
+ other
->used
)*3 >= (so
->mask
+1)*2) {
665 if (set_table_resize(so
, (so
->used
+ other
->used
)*2) != 0)
668 for (i
= 0; i
<= other
->mask
; i
++) {
669 entry
= &other
->table
[i
];
670 if (entry
->key
!= NULL
&&
671 entry
->key
!= dummy
) {
672 Py_INCREF(entry
->key
);
673 if (set_insert_key(so
, entry
->key
, entry
->hash
) == -1) {
674 Py_DECREF(entry
->key
);
683 set_contains_key(PySetObject
*so
, PyObject
*key
)
688 if (!PyString_CheckExact(key
) ||
689 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
690 hash
= PyObject_Hash(key
);
694 entry
= (so
->lookup
)(so
, key
, hash
);
698 return key
!= NULL
&& key
!= dummy
;
702 set_contains_entry(PySetObject
*so
, setentry
*entry
)
707 lu_entry
= (so
->lookup
)(so
, entry
->key
, entry
->hash
);
708 if (lu_entry
== NULL
)
711 return key
!= NULL
&& key
!= dummy
;
715 set_pop(PySetObject
*so
)
717 register Py_ssize_t i
= 0;
718 register setentry
*entry
;
721 assert (PyAnySet_Check(so
));
723 PyErr_SetString(PyExc_KeyError
, "pop from an empty set");
727 /* Set entry to "the first" unused or dummy set entry. We abuse
728 * the hash field of slot 0 to hold a search finger:
729 * If slot 0 has a value, use slot 0.
730 * Else slot 0 is being used to hold a search finger,
731 * and we use its hash value as the first index to look.
733 entry
= &so
->table
[0];
734 if (entry
->key
== NULL
|| entry
->key
== dummy
) {
736 /* The hash field may be a real hash value, or it may be a
737 * legit search finger, or it may be a once-legit search
738 * finger that's out of bounds now because it wrapped around
739 * or the table shrunk -- simply make sure it's in bounds now.
741 if (i
> so
->mask
|| i
< 1)
742 i
= 1; /* skip slot 0 */
743 while ((entry
= &so
->table
[i
])->key
== NULL
|| entry
->key
==dummy
) {
753 so
->table
[0].hash
= i
+ 1; /* next place to start */
757 PyDoc_STRVAR(pop_doc
, "Remove and return an arbitrary set element.");
760 set_traverse(PySetObject
*so
, visitproc visit
, void *arg
)
765 while (set_next(so
, &pos
, &entry
))
766 Py_VISIT(entry
->key
);
771 frozenset_hash(PyObject
*self
)
773 PySetObject
*so
= (PySetObject
*)self
;
774 long h
, hash
= 1927868237L;
781 hash
*= PySet_GET_SIZE(self
) + 1;
782 while (set_next(so
, &pos
, &entry
)) {
783 /* Work to increase the bit dispersion for closely spaced hash
784 values. The is important because some use cases have many
785 combinations of a small number of elements with nearby
786 hashes so that many distinct combinations collapse to only
787 a handful of distinct hash values. */
789 hash
^= (h
^ (h
<< 16) ^ 89869747L) * 3644798167u;
791 hash
= hash
* 69069L + 907133923L;
798 /***** Set iterator type ***********************************************/
802 PySetObject
*si_set
; /* Set to NULL when iterator is exhausted */
809 setiter_dealloc(setiterobject
*si
)
811 Py_XDECREF(si
->si_set
);
816 setiter_len(setiterobject
*si
)
819 if (si
->si_set
!= NULL
&& si
->si_used
== si
->si_set
->used
)
821 return PyInt_FromLong(len
);
824 PyDoc_STRVAR(length_hint_doc
, "Private method returning an estimate of len(list(it)).");
826 static PyMethodDef setiter_methods
[] = {
827 {"__length_hint__", (PyCFunction
)setiter_len
, METH_NOARGS
, length_hint_doc
},
828 {NULL
, NULL
} /* sentinel */
831 static PyObject
*setiter_iternext(setiterobject
*si
)
834 register Py_ssize_t i
, mask
;
835 register setentry
*entry
;
836 PySetObject
*so
= si
->si_set
;
840 assert (PyAnySet_Check(so
));
842 if (si
->si_used
!= so
->used
) {
843 PyErr_SetString(PyExc_RuntimeError
,
844 "Set changed size during iteration");
845 si
->si_used
= -1; /* Make this state sticky */
853 while (i
<= mask
&& (entry
[i
].key
== NULL
|| entry
[i
].key
== dummy
))
869 static PyTypeObject PySetIter_Type
= {
870 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
871 "setiterator", /* tp_name */
872 sizeof(setiterobject
), /* tp_basicsize */
875 (destructor
)setiter_dealloc
, /* tp_dealloc */
881 0, /* tp_as_number */
882 0, /* tp_as_sequence */
883 0, /* tp_as_mapping */
887 PyObject_GenericGetAttr
, /* tp_getattro */
889 0, /* tp_as_buffer */
890 Py_TPFLAGS_DEFAULT
, /* tp_flags */
894 0, /* tp_richcompare */
895 0, /* tp_weaklistoffset */
896 PyObject_SelfIter
, /* tp_iter */
897 (iternextfunc
)setiter_iternext
, /* tp_iternext */
898 setiter_methods
, /* tp_methods */
903 set_iter(PySetObject
*so
)
905 setiterobject
*si
= PyObject_New(setiterobject
, &PySetIter_Type
);
910 si
->si_used
= so
->used
;
913 return (PyObject
*)si
;
917 set_update_internal(PySetObject
*so
, PyObject
*other
)
921 if (PyAnySet_Check(other
))
922 return set_merge(so
, other
);
924 if (PyDict_CheckExact(other
)) {
928 Py_ssize_t dictsize
= PyDict_Size(other
);
930 /* Do one big resize at the start, rather than
931 * incrementally resizing as we insert new keys. Expect
932 * that there will be no (or few) overlapping keys.
936 if ((so
->fill
+ dictsize
)*3 >= (so
->mask
+1)*2) {
937 if (set_table_resize(so
, (so
->used
+ dictsize
)*2) != 0)
940 while (_PyDict_Next(other
, &pos
, &key
, &value
, &hash
)) {
943 an_entry
.hash
= hash
;
945 if (set_add_entry(so
, &an_entry
) == -1)
951 it
= PyObject_GetIter(other
);
955 while ((key
= PyIter_Next(it
)) != NULL
) {
956 if (set_add_key(so
, key
) == -1) {
964 if (PyErr_Occurred())
970 set_update(PySetObject
*so
, PyObject
*args
)
974 for (i
=0 ; i
<PyTuple_GET_SIZE(args
) ; i
++) {
975 PyObject
*other
= PyTuple_GET_ITEM(args
, i
);
976 if (set_update_internal(so
, other
) == -1)
982 PyDoc_STRVAR(update_doc
,
983 "Update a set with the union of itself and others.");
986 make_new_set(PyTypeObject
*type
, PyObject
*iterable
)
988 register PySetObject
*so
= NULL
;
990 if (dummy
== NULL
) { /* Auto-initialize dummy */
991 dummy
= PyString_FromString("<dummy key>");
996 /* create PySetObject structure */
998 (type
== &PySet_Type
|| type
== &PyFrozenSet_Type
)) {
999 so
= free_list
[--numfree
];
1000 assert (so
!= NULL
&& PyAnySet_CheckExact(so
));
1002 _Py_NewReference((PyObject
*)so
);
1003 EMPTY_TO_MINSIZE(so
);
1004 PyObject_GC_Track(so
);
1006 so
= (PySetObject
*)type
->tp_alloc(type
, 0);
1009 /* tp_alloc has already zeroed the structure */
1010 assert(so
->table
== NULL
&& so
->fill
== 0 && so
->used
== 0);
1011 INIT_NONZERO_SET_SLOTS(so
);
1014 so
->lookup
= set_lookkey_string
;
1015 so
->weakreflist
= NULL
;
1017 if (iterable
!= NULL
) {
1018 if (set_update_internal(so
, iterable
) == -1) {
1024 return (PyObject
*)so
;
1027 /* The empty frozenset is a singleton */
1028 static PyObject
*emptyfrozenset
= NULL
;
1031 frozenset_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1033 PyObject
*iterable
= NULL
, *result
;
1035 if (type
== &PyFrozenSet_Type
&& !_PyArg_NoKeywords("frozenset()", kwds
))
1038 if (!PyArg_UnpackTuple(args
, type
->tp_name
, 0, 1, &iterable
))
1041 if (type
!= &PyFrozenSet_Type
)
1042 return make_new_set(type
, iterable
);
1044 if (iterable
!= NULL
) {
1045 /* frozenset(f) is idempotent */
1046 if (PyFrozenSet_CheckExact(iterable
)) {
1047 Py_INCREF(iterable
);
1050 result
= make_new_set(type
, iterable
);
1051 if (result
== NULL
|| PySet_GET_SIZE(result
))
1055 /* The empty frozenset is a singleton */
1056 if (emptyfrozenset
== NULL
)
1057 emptyfrozenset
= make_new_set(type
, NULL
);
1058 Py_XINCREF(emptyfrozenset
);
1059 return emptyfrozenset
;
1069 so
= free_list
[numfree
];
1070 PyObject_GC_Del(so
);
1073 Py_CLEAR(emptyfrozenset
);
1077 set_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1079 if (type
== &PySet_Type
&& !_PyArg_NoKeywords("set()", kwds
))
1082 return make_new_set(type
, NULL
);
1085 /* set_swap_bodies() switches the contents of any two sets by moving their
1086 internal data pointers and, if needed, copying the internal smalltables.
1087 Semantically equivalent to:
1089 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1091 The function always succeeds and it leaves both objects in a stable state.
1092 Useful for creating temporary frozensets from sets for membership testing
1093 in __contains__(), discard(), and remove(). Also useful for operations
1094 that update in-place (by allowing an intermediate result to be swapped
1095 into one of the original inputs).
1099 set_swap_bodies(PySetObject
*a
, PySetObject
*b
)
1103 setentry
*(*f
)(PySetObject
*so
, PyObject
*key
, long hash
);
1104 setentry tab
[PySet_MINSIZE
];
1107 t
= a
->fill
; a
->fill
= b
->fill
; b
->fill
= t
;
1108 t
= a
->used
; a
->used
= b
->used
; b
->used
= t
;
1109 t
= a
->mask
; a
->mask
= b
->mask
; b
->mask
= t
;
1112 if (a
->table
== a
->smalltable
)
1114 a
->table
= b
->table
;
1115 if (b
->table
== b
->smalltable
)
1116 a
->table
= a
->smalltable
;
1119 f
= a
->lookup
; a
->lookup
= b
->lookup
; b
->lookup
= f
;
1121 if (a
->table
== a
->smalltable
|| b
->table
== b
->smalltable
) {
1122 memcpy(tab
, a
->smalltable
, sizeof(tab
));
1123 memcpy(a
->smalltable
, b
->smalltable
, sizeof(tab
));
1124 memcpy(b
->smalltable
, tab
, sizeof(tab
));
1127 if (PyType_IsSubtype(Py_TYPE(a
), &PyFrozenSet_Type
) &&
1128 PyType_IsSubtype(Py_TYPE(b
), &PyFrozenSet_Type
)) {
1129 h
= a
->hash
; a
->hash
= b
->hash
; b
->hash
= h
;
1137 set_copy(PySetObject
*so
)
1139 return make_new_set(Py_TYPE(so
), (PyObject
*)so
);
1143 frozenset_copy(PySetObject
*so
)
1145 if (PyFrozenSet_CheckExact(so
)) {
1147 return (PyObject
*)so
;
1149 return set_copy(so
);
1152 PyDoc_STRVAR(copy_doc
, "Return a shallow copy of a set.");
1155 set_clear(PySetObject
*so
)
1157 set_clear_internal(so
);
1161 PyDoc_STRVAR(clear_doc
, "Remove all elements from this set.");
1164 set_union(PySetObject
*so
, PyObject
*args
)
1166 PySetObject
*result
;
1170 result
= (PySetObject
*)set_copy(so
);
1174 for (i
=0 ; i
<PyTuple_GET_SIZE(args
) ; i
++) {
1175 other
= PyTuple_GET_ITEM(args
, i
);
1176 if ((PyObject
*)so
== other
)
1177 return (PyObject
*)result
;
1178 if (set_update_internal(result
, other
) == -1) {
1183 return (PyObject
*)result
;
1186 PyDoc_STRVAR(union_doc
,
1187 "Return the union of sets as a new set.\n\
1189 (i.e. all elements that are in either set.)");
1192 set_or(PySetObject
*so
, PyObject
*other
)
1194 PySetObject
*result
;
1196 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1197 Py_INCREF(Py_NotImplemented
);
1198 return Py_NotImplemented
;
1201 result
= (PySetObject
*)set_copy(so
);
1204 if ((PyObject
*)so
== other
)
1205 return (PyObject
*)result
;
1206 if (set_update_internal(result
, other
) == -1) {
1210 return (PyObject
*)result
;
1214 set_ior(PySetObject
*so
, PyObject
*other
)
1216 if (!PyAnySet_Check(other
)) {
1217 Py_INCREF(Py_NotImplemented
);
1218 return Py_NotImplemented
;
1220 if (set_update_internal(so
, other
) == -1)
1223 return (PyObject
*)so
;
1227 set_intersection(PySetObject
*so
, PyObject
*other
)
1229 PySetObject
*result
;
1230 PyObject
*key
, *it
, *tmp
;
1232 if ((PyObject
*)so
== other
)
1233 return set_copy(so
);
1235 result
= (PySetObject
*)make_new_set(Py_TYPE(so
), NULL
);
1239 if (PyAnySet_Check(other
)) {
1243 if (PySet_GET_SIZE(other
) > PySet_GET_SIZE(so
)) {
1244 tmp
= (PyObject
*)so
;
1245 so
= (PySetObject
*)other
;
1249 while (set_next((PySetObject
*)other
, &pos
, &entry
)) {
1250 int rv
= set_contains_entry(so
, entry
);
1256 if (set_add_entry(result
, entry
) == -1) {
1262 return (PyObject
*)result
;
1265 it
= PyObject_GetIter(other
);
1271 while ((key
= PyIter_Next(it
)) != NULL
) {
1274 long hash
= PyObject_Hash(key
);
1284 rv
= set_contains_entry(so
, &entry
);
1292 if (set_add_entry(result
, &entry
) == -1) {
1302 if (PyErr_Occurred()) {
1306 return (PyObject
*)result
;
1310 set_intersection_multi(PySetObject
*so
, PyObject
*args
)
1313 PyObject
*result
= (PyObject
*)so
;
1315 if (PyTuple_GET_SIZE(args
) == 0)
1316 return set_copy(so
);
1319 for (i
=0 ; i
<PyTuple_GET_SIZE(args
) ; i
++) {
1320 PyObject
*other
= PyTuple_GET_ITEM(args
, i
);
1321 PyObject
*newresult
= set_intersection((PySetObject
*)result
, other
);
1322 if (newresult
== NULL
) {
1332 PyDoc_STRVAR(intersection_doc
,
1333 "Return the intersection of two sets as a new set.\n\
1335 (i.e. all elements that are in both sets.)");
1338 set_intersection_update(PySetObject
*so
, PyObject
*other
)
1342 tmp
= set_intersection(so
, other
);
1345 set_swap_bodies(so
, (PySetObject
*)tmp
);
1351 set_intersection_update_multi(PySetObject
*so
, PyObject
*args
)
1355 tmp
= set_intersection_multi(so
, args
);
1358 set_swap_bodies(so
, (PySetObject
*)tmp
);
1363 PyDoc_STRVAR(intersection_update_doc
,
1364 "Update a set with the intersection of itself and another.");
1367 set_and(PySetObject
*so
, PyObject
*other
)
1369 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1370 Py_INCREF(Py_NotImplemented
);
1371 return Py_NotImplemented
;
1373 return set_intersection(so
, other
);
1377 set_iand(PySetObject
*so
, PyObject
*other
)
1381 if (!PyAnySet_Check(other
)) {
1382 Py_INCREF(Py_NotImplemented
);
1383 return Py_NotImplemented
;
1385 result
= set_intersection_update(so
, other
);
1390 return (PyObject
*)so
;
1394 set_isdisjoint(PySetObject
*so
, PyObject
*other
)
1396 PyObject
*key
, *it
, *tmp
;
1398 if ((PyObject
*)so
== other
) {
1399 if (PySet_GET_SIZE(so
) == 0)
1405 if (PyAnySet_CheckExact(other
)) {
1409 if (PySet_GET_SIZE(other
) > PySet_GET_SIZE(so
)) {
1410 tmp
= (PyObject
*)so
;
1411 so
= (PySetObject
*)other
;
1414 while (set_next((PySetObject
*)other
, &pos
, &entry
)) {
1415 int rv
= set_contains_entry(so
, entry
);
1424 it
= PyObject_GetIter(other
);
1428 while ((key
= PyIter_Next(it
)) != NULL
) {
1431 long hash
= PyObject_Hash(key
);
1440 rv
= set_contains_entry(so
, &entry
);
1452 if (PyErr_Occurred())
1457 PyDoc_STRVAR(isdisjoint_doc
,
1458 "Return True if two sets have a null intersection.");
1461 set_difference_update_internal(PySetObject
*so
, PyObject
*other
)
1463 if ((PyObject
*)so
== other
)
1464 return set_clear_internal(so
);
1466 if (PyAnySet_Check(other
)) {
1470 while (set_next((PySetObject
*)other
, &pos
, &entry
))
1471 if (set_discard_entry(so
, entry
) == -1)
1475 it
= PyObject_GetIter(other
);
1479 while ((key
= PyIter_Next(it
)) != NULL
) {
1480 if (set_discard_key(so
, key
) == -1) {
1488 if (PyErr_Occurred())
1491 /* If more than 1/5 are dummies, then resize them away. */
1492 if ((so
->fill
- so
->used
) * 5 < so
->mask
)
1494 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
1498 set_difference_update(PySetObject
*so
, PyObject
*args
)
1502 for (i
=0 ; i
<PyTuple_GET_SIZE(args
) ; i
++) {
1503 PyObject
*other
= PyTuple_GET_ITEM(args
, i
);
1504 if (set_difference_update_internal(so
, other
) == -1)
1510 PyDoc_STRVAR(difference_update_doc
,
1511 "Remove all elements of another set from this set.");
1514 set_difference(PySetObject
*so
, PyObject
*other
)
1520 if (!PyAnySet_Check(other
) && !PyDict_CheckExact(other
)) {
1521 result
= set_copy(so
);
1524 if (set_difference_update_internal((PySetObject
*)result
, other
) != -1)
1530 result
= make_new_set(Py_TYPE(so
), NULL
);
1534 if (PyDict_CheckExact(other
)) {
1535 while (set_next(so
, &pos
, &entry
)) {
1537 entrycopy
.hash
= entry
->hash
;
1538 entrycopy
.key
= entry
->key
;
1539 if (!_PyDict_Contains(other
, entry
->key
, entry
->hash
)) {
1540 if (set_add_entry((PySetObject
*)result
, &entrycopy
) == -1) {
1549 while (set_next(so
, &pos
, &entry
)) {
1550 int rv
= set_contains_entry((PySetObject
*)other
, entry
);
1556 if (set_add_entry((PySetObject
*)result
, entry
) == -1) {
1566 set_difference_multi(PySetObject
*so
, PyObject
*args
)
1569 PyObject
*result
, *other
;
1571 if (PyTuple_GET_SIZE(args
) == 0)
1572 return set_copy(so
);
1574 other
= PyTuple_GET_ITEM(args
, 0);
1575 result
= set_difference(so
, other
);
1579 for (i
=1 ; i
<PyTuple_GET_SIZE(args
) ; i
++) {
1580 other
= PyTuple_GET_ITEM(args
, i
);
1581 if (set_difference_update_internal((PySetObject
*)result
, other
) == -1) {
1589 PyDoc_STRVAR(difference_doc
,
1590 "Return the difference of two or more sets as a new set.\n\
1592 (i.e. all elements that are in this set but not the others.)");
1594 set_sub(PySetObject
*so
, PyObject
*other
)
1596 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1597 Py_INCREF(Py_NotImplemented
);
1598 return Py_NotImplemented
;
1600 return set_difference(so
, other
);
1604 set_isub(PySetObject
*so
, PyObject
*other
)
1606 if (!PyAnySet_Check(other
)) {
1607 Py_INCREF(Py_NotImplemented
);
1608 return Py_NotImplemented
;
1610 if (set_difference_update_internal(so
, other
) == -1)
1613 return (PyObject
*)so
;
1617 set_symmetric_difference_update(PySetObject
*so
, PyObject
*other
)
1619 PySetObject
*otherset
;
1624 if ((PyObject
*)so
== other
)
1625 return set_clear(so
);
1627 if (PyDict_CheckExact(other
)) {
1631 while (_PyDict_Next(other
, &pos
, &key
, &value
, &hash
)) {
1634 an_entry
.hash
= hash
;
1636 rv
= set_discard_entry(so
, &an_entry
);
1639 if (rv
== DISCARD_NOTFOUND
) {
1640 if (set_add_entry(so
, &an_entry
) == -1)
1647 if (PyAnySet_Check(other
)) {
1649 otherset
= (PySetObject
*)other
;
1651 otherset
= (PySetObject
*)make_new_set(Py_TYPE(so
), other
);
1652 if (otherset
== NULL
)
1656 while (set_next(otherset
, &pos
, &entry
)) {
1657 int rv
= set_discard_entry(so
, entry
);
1659 Py_DECREF(otherset
);
1662 if (rv
== DISCARD_NOTFOUND
) {
1663 if (set_add_entry(so
, entry
) == -1) {
1664 Py_DECREF(otherset
);
1669 Py_DECREF(otherset
);
1673 PyDoc_STRVAR(symmetric_difference_update_doc
,
1674 "Update a set with the symmetric difference of itself and another.");
1677 set_symmetric_difference(PySetObject
*so
, PyObject
*other
)
1680 PySetObject
*otherset
;
1682 otherset
= (PySetObject
*)make_new_set(Py_TYPE(so
), other
);
1683 if (otherset
== NULL
)
1685 rv
= set_symmetric_difference_update(otherset
, (PyObject
*)so
);
1689 return (PyObject
*)otherset
;
1692 PyDoc_STRVAR(symmetric_difference_doc
,
1693 "Return the symmetric difference of two sets as a new set.\n\
1695 (i.e. all elements that are in exactly one of the sets.)");
1698 set_xor(PySetObject
*so
, PyObject
*other
)
1700 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1701 Py_INCREF(Py_NotImplemented
);
1702 return Py_NotImplemented
;
1704 return set_symmetric_difference(so
, other
);
1708 set_ixor(PySetObject
*so
, PyObject
*other
)
1712 if (!PyAnySet_Check(other
)) {
1713 Py_INCREF(Py_NotImplemented
);
1714 return Py_NotImplemented
;
1716 result
= set_symmetric_difference_update(so
, other
);
1721 return (PyObject
*)so
;
1725 set_issubset(PySetObject
*so
, PyObject
*other
)
1730 if (!PyAnySet_Check(other
)) {
1731 PyObject
*tmp
, *result
;
1732 tmp
= make_new_set(&PySet_Type
, other
);
1735 result
= set_issubset(so
, tmp
);
1739 if (PySet_GET_SIZE(so
) > PySet_GET_SIZE(other
))
1742 while (set_next(so
, &pos
, &entry
)) {
1743 int rv
= set_contains_entry((PySetObject
*)other
, entry
);
1752 PyDoc_STRVAR(issubset_doc
, "Report whether another set contains this set.");
1755 set_issuperset(PySetObject
*so
, PyObject
*other
)
1757 PyObject
*tmp
, *result
;
1759 if (!PyAnySet_Check(other
)) {
1760 tmp
= make_new_set(&PySet_Type
, other
);
1763 result
= set_issuperset(so
, tmp
);
1767 return set_issubset((PySetObject
*)other
, (PyObject
*)so
);
1770 PyDoc_STRVAR(issuperset_doc
, "Report whether this set contains another set.");
1773 set_richcompare(PySetObject
*v
, PyObject
*w
, int op
)
1777 if(!PyAnySet_Check(w
)) {
1782 PyErr_SetString(PyExc_TypeError
, "can only compare to a set");
1787 if (PySet_GET_SIZE(v
) != PySet_GET_SIZE(w
))
1789 if (v
->hash
!= -1 &&
1790 ((PySetObject
*)w
)->hash
!= -1 &&
1791 v
->hash
!= ((PySetObject
*)w
)->hash
)
1793 return set_issubset(v
, w
);
1795 r1
= set_richcompare(v
, w
, Py_EQ
);
1798 r2
= PyBool_FromLong(PyObject_Not(r1
));
1802 return set_issubset(v
, w
);
1804 return set_issuperset(v
, w
);
1806 if (PySet_GET_SIZE(v
) >= PySet_GET_SIZE(w
))
1808 return set_issubset(v
, w
);
1810 if (PySet_GET_SIZE(v
) <= PySet_GET_SIZE(w
))
1812 return set_issuperset(v
, w
);
1814 Py_INCREF(Py_NotImplemented
);
1815 return Py_NotImplemented
;
1819 set_nocmp(PyObject
*self
, PyObject
*other
)
1821 PyErr_SetString(PyExc_TypeError
, "cannot compare sets using cmp()");
1826 set_add(PySetObject
*so
, PyObject
*key
)
1828 if (set_add_key(so
, key
) == -1)
1833 PyDoc_STRVAR(add_doc
,
1834 "Add an element to a set.\n\
1836 This has no effect if the element is already present.");
1839 set_contains(PySetObject
*so
, PyObject
*key
)
1844 rv
= set_contains_key(so
, key
);
1846 if (!PySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1849 tmpkey
= make_new_set(&PyFrozenSet_Type
, NULL
);
1852 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1853 rv
= set_contains(so
, tmpkey
);
1854 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1861 set_direct_contains(PySetObject
*so
, PyObject
*key
)
1865 result
= set_contains(so
, key
);
1868 return PyBool_FromLong(result
);
1871 PyDoc_STRVAR(contains_doc
, "x.__contains__(y) <==> y in x.");
1874 set_remove(PySetObject
*so
, PyObject
*key
)
1876 PyObject
*tmpkey
, *result
;
1879 rv
= set_discard_key(so
, key
);
1881 if (!PySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1884 tmpkey
= make_new_set(&PyFrozenSet_Type
, NULL
);
1887 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1888 result
= set_remove(so
, tmpkey
);
1889 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1892 } else if (rv
== DISCARD_NOTFOUND
) {
1899 PyDoc_STRVAR(remove_doc
,
1900 "Remove an element from a set; it must be a member.\n\
1902 If the element is not a member, raise a KeyError.");
1905 set_discard(PySetObject
*so
, PyObject
*key
)
1907 PyObject
*tmpkey
, *result
;
1910 rv
= set_discard_key(so
, key
);
1912 if (!PySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1915 tmpkey
= make_new_set(&PyFrozenSet_Type
, NULL
);
1918 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1919 result
= set_discard(so
, tmpkey
);
1920 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1927 PyDoc_STRVAR(discard_doc
,
1928 "Remove an element from a set if it is a member.\n\
1930 If the element is not a member, do nothing.");
1933 set_reduce(PySetObject
*so
)
1935 PyObject
*keys
=NULL
, *args
=NULL
, *result
=NULL
, *dict
=NULL
;
1937 keys
= PySequence_List((PyObject
*)so
);
1940 args
= PyTuple_Pack(1, keys
);
1943 dict
= PyObject_GetAttrString((PyObject
*)so
, "__dict__");
1949 result
= PyTuple_Pack(3, Py_TYPE(so
), args
, dict
);
1957 PyDoc_STRVAR(reduce_doc
, "Return state information for pickling.");
1960 set_init(PySetObject
*self
, PyObject
*args
, PyObject
*kwds
)
1962 PyObject
*iterable
= NULL
;
1964 if (!PyAnySet_Check(self
))
1966 if (!PyArg_UnpackTuple(args
, Py_TYPE(self
)->tp_name
, 0, 1, &iterable
))
1968 set_clear_internal(self
);
1970 if (iterable
== NULL
)
1972 return set_update_internal(self
, iterable
);
1975 static PySequenceMethods set_as_sequence
= {
1976 set_len
, /* sq_length */
1981 0, /* sq_ass_item */
1982 0, /* sq_ass_slice */
1983 (objobjproc
)set_contains
, /* sq_contains */
1986 /* set object ********************************************************/
1989 static PyObject
*test_c_api(PySetObject
*so
);
1991 PyDoc_STRVAR(test_c_api_doc
, "Exercises C API. Returns True.\n\
1992 All is well if assertions don't fail.");
1995 static PyMethodDef set_methods
[] = {
1996 {"add", (PyCFunction
)set_add
, METH_O
,
1998 {"clear", (PyCFunction
)set_clear
, METH_NOARGS
,
2000 {"__contains__",(PyCFunction
)set_direct_contains
, METH_O
| METH_COEXIST
,
2002 {"copy", (PyCFunction
)set_copy
, METH_NOARGS
,
2004 {"discard", (PyCFunction
)set_discard
, METH_O
,
2006 {"difference", (PyCFunction
)set_difference_multi
, METH_VARARGS
,
2008 {"difference_update", (PyCFunction
)set_difference_update
, METH_VARARGS
,
2009 difference_update_doc
},
2010 {"intersection",(PyCFunction
)set_intersection_multi
, METH_VARARGS
,
2012 {"intersection_update",(PyCFunction
)set_intersection_update_multi
, METH_VARARGS
,
2013 intersection_update_doc
},
2014 {"isdisjoint", (PyCFunction
)set_isdisjoint
, METH_O
,
2016 {"issubset", (PyCFunction
)set_issubset
, METH_O
,
2018 {"issuperset", (PyCFunction
)set_issuperset
, METH_O
,
2020 {"pop", (PyCFunction
)set_pop
, METH_NOARGS
,
2022 {"__reduce__", (PyCFunction
)set_reduce
, METH_NOARGS
,
2024 {"remove", (PyCFunction
)set_remove
, METH_O
,
2026 {"symmetric_difference",(PyCFunction
)set_symmetric_difference
, METH_O
,
2027 symmetric_difference_doc
},
2028 {"symmetric_difference_update",(PyCFunction
)set_symmetric_difference_update
, METH_O
,
2029 symmetric_difference_update_doc
},
2031 {"test_c_api", (PyCFunction
)test_c_api
, METH_NOARGS
,
2034 {"union", (PyCFunction
)set_union
, METH_VARARGS
,
2036 {"update", (PyCFunction
)set_update
, METH_VARARGS
,
2038 {NULL
, NULL
} /* sentinel */
2041 static PyNumberMethods set_as_number
= {
2043 (binaryfunc
)set_sub
, /*nb_subtract*/
2056 (binaryfunc
)set_and
, /*nb_and*/
2057 (binaryfunc
)set_xor
, /*nb_xor*/
2058 (binaryfunc
)set_or
, /*nb_or*/
2065 0, /*nb_inplace_add*/
2066 (binaryfunc
)set_isub
, /*nb_inplace_subtract*/
2067 0, /*nb_inplace_multiply*/
2068 0, /*nb_inplace_divide*/
2069 0, /*nb_inplace_remainder*/
2070 0, /*nb_inplace_power*/
2071 0, /*nb_inplace_lshift*/
2072 0, /*nb_inplace_rshift*/
2073 (binaryfunc
)set_iand
, /*nb_inplace_and*/
2074 (binaryfunc
)set_ixor
, /*nb_inplace_xor*/
2075 (binaryfunc
)set_ior
, /*nb_inplace_or*/
2078 PyDoc_STRVAR(set_doc
,
2079 "set(iterable) --> set object\n\
2081 Build an unordered collection of unique elements.");
2083 PyTypeObject PySet_Type
= {
2084 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2085 "set", /* tp_name */
2086 sizeof(PySetObject
), /* tp_basicsize */
2087 0, /* tp_itemsize */
2089 (destructor
)set_dealloc
, /* tp_dealloc */
2090 (printfunc
)set_tp_print
, /* tp_print */
2093 set_nocmp
, /* tp_compare */
2094 (reprfunc
)set_repr
, /* tp_repr */
2095 &set_as_number
, /* tp_as_number */
2096 &set_as_sequence
, /* tp_as_sequence */
2097 0, /* tp_as_mapping */
2101 PyObject_GenericGetAttr
, /* tp_getattro */
2102 0, /* tp_setattro */
2103 0, /* tp_as_buffer */
2104 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
| Py_TPFLAGS_CHECKTYPES
|
2105 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2106 set_doc
, /* tp_doc */
2107 (traverseproc
)set_traverse
, /* tp_traverse */
2108 (inquiry
)set_clear_internal
, /* tp_clear */
2109 (richcmpfunc
)set_richcompare
, /* tp_richcompare */
2110 offsetof(PySetObject
, weakreflist
), /* tp_weaklistoffset */
2111 (getiterfunc
)set_iter
, /* tp_iter */
2112 0, /* tp_iternext */
2113 set_methods
, /* tp_methods */
2118 0, /* tp_descr_get */
2119 0, /* tp_descr_set */
2120 0, /* tp_dictoffset */
2121 (initproc
)set_init
, /* tp_init */
2122 PyType_GenericAlloc
, /* tp_alloc */
2123 set_new
, /* tp_new */
2124 PyObject_GC_Del
, /* tp_free */
2127 /* frozenset object ********************************************************/
2130 static PyMethodDef frozenset_methods
[] = {
2131 {"__contains__",(PyCFunction
)set_direct_contains
, METH_O
| METH_COEXIST
,
2133 {"copy", (PyCFunction
)frozenset_copy
, METH_NOARGS
,
2135 {"difference", (PyCFunction
)set_difference_multi
, METH_VARARGS
,
2137 {"intersection",(PyCFunction
)set_intersection_multi
, METH_VARARGS
,
2139 {"isdisjoint", (PyCFunction
)set_isdisjoint
, METH_O
,
2141 {"issubset", (PyCFunction
)set_issubset
, METH_O
,
2143 {"issuperset", (PyCFunction
)set_issuperset
, METH_O
,
2145 {"__reduce__", (PyCFunction
)set_reduce
, METH_NOARGS
,
2147 {"symmetric_difference",(PyCFunction
)set_symmetric_difference
, METH_O
,
2148 symmetric_difference_doc
},
2149 {"union", (PyCFunction
)set_union
, METH_VARARGS
,
2151 {NULL
, NULL
} /* sentinel */
2154 static PyNumberMethods frozenset_as_number
= {
2156 (binaryfunc
)set_sub
, /*nb_subtract*/
2169 (binaryfunc
)set_and
, /*nb_and*/
2170 (binaryfunc
)set_xor
, /*nb_xor*/
2171 (binaryfunc
)set_or
, /*nb_or*/
2174 PyDoc_STRVAR(frozenset_doc
,
2175 "frozenset(iterable) --> frozenset object\n\
2177 Build an immutable unordered collection of unique elements.");
2179 PyTypeObject PyFrozenSet_Type
= {
2180 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2181 "frozenset", /* tp_name */
2182 sizeof(PySetObject
), /* tp_basicsize */
2183 0, /* tp_itemsize */
2185 (destructor
)set_dealloc
, /* tp_dealloc */
2186 (printfunc
)set_tp_print
, /* tp_print */
2189 set_nocmp
, /* tp_compare */
2190 (reprfunc
)set_repr
, /* tp_repr */
2191 &frozenset_as_number
, /* tp_as_number */
2192 &set_as_sequence
, /* tp_as_sequence */
2193 0, /* tp_as_mapping */
2194 frozenset_hash
, /* tp_hash */
2197 PyObject_GenericGetAttr
, /* tp_getattro */
2198 0, /* tp_setattro */
2199 0, /* tp_as_buffer */
2200 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
| Py_TPFLAGS_CHECKTYPES
|
2201 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2202 frozenset_doc
, /* tp_doc */
2203 (traverseproc
)set_traverse
, /* tp_traverse */
2204 (inquiry
)set_clear_internal
, /* tp_clear */
2205 (richcmpfunc
)set_richcompare
, /* tp_richcompare */
2206 offsetof(PySetObject
, weakreflist
), /* tp_weaklistoffset */
2207 (getiterfunc
)set_iter
, /* tp_iter */
2208 0, /* tp_iternext */
2209 frozenset_methods
, /* tp_methods */
2214 0, /* tp_descr_get */
2215 0, /* tp_descr_set */
2216 0, /* tp_dictoffset */
2218 PyType_GenericAlloc
, /* tp_alloc */
2219 frozenset_new
, /* tp_new */
2220 PyObject_GC_Del
, /* tp_free */
2224 /***** C API functions *************************************************/
2227 PySet_New(PyObject
*iterable
)
2229 return make_new_set(&PySet_Type
, iterable
);
2233 PyFrozenSet_New(PyObject
*iterable
)
2235 return make_new_set(&PyFrozenSet_Type
, iterable
);
2239 PySet_Size(PyObject
*anyset
)
2241 if (!PyAnySet_Check(anyset
)) {
2242 PyErr_BadInternalCall();
2245 return PySet_GET_SIZE(anyset
);
2249 PySet_Clear(PyObject
*set
)
2251 if (!PySet_Check(set
)) {
2252 PyErr_BadInternalCall();
2255 return set_clear_internal((PySetObject
*)set
);
2259 PySet_Contains(PyObject
*anyset
, PyObject
*key
)
2261 if (!PyAnySet_Check(anyset
)) {
2262 PyErr_BadInternalCall();
2265 return set_contains_key((PySetObject
*)anyset
, key
);
2269 PySet_Discard(PyObject
*set
, PyObject
*key
)
2271 if (!PySet_Check(set
)) {
2272 PyErr_BadInternalCall();
2275 return set_discard_key((PySetObject
*)set
, key
);
2279 PySet_Add(PyObject
*anyset
, PyObject
*key
)
2281 if (!PySet_Check(anyset
) &&
2282 (!PyFrozenSet_Check(anyset
) || Py_REFCNT(anyset
) != 1)) {
2283 PyErr_BadInternalCall();
2286 return set_add_key((PySetObject
*)anyset
, key
);
2290 _PySet_Next(PyObject
*set
, Py_ssize_t
*pos
, PyObject
**key
)
2292 setentry
*entry_ptr
;
2294 if (!PyAnySet_Check(set
)) {
2295 PyErr_BadInternalCall();
2298 if (set_next((PySetObject
*)set
, pos
, &entry_ptr
) == 0)
2300 *key
= entry_ptr
->key
;
2305 _PySet_NextEntry(PyObject
*set
, Py_ssize_t
*pos
, PyObject
**key
, long *hash
)
2309 if (!PyAnySet_Check(set
)) {
2310 PyErr_BadInternalCall();
2313 if (set_next((PySetObject
*)set
, pos
, &entry
) == 0)
2316 *hash
= entry
->hash
;
2321 PySet_Pop(PyObject
*set
)
2323 if (!PySet_Check(set
)) {
2324 PyErr_BadInternalCall();
2327 return set_pop((PySetObject
*)set
);
2331 _PySet_Update(PyObject
*set
, PyObject
*iterable
)
2333 if (!PySet_Check(set
)) {
2334 PyErr_BadInternalCall();
2337 return set_update_internal((PySetObject
*)set
, iterable
);
2342 /* Test code to be called with any three element set.
2343 Returns True and original set is restored. */
2345 #define assertRaises(call_return_value, exception) \
2347 assert(call_return_value); \
2348 assert(PyErr_ExceptionMatches(exception)); \
2353 test_c_api(PySetObject
*so
)
2358 PyObject
*elem
=NULL
, *dup
=NULL
, *t
, *f
, *dup2
, *x
;
2359 PyObject
*ob
= (PyObject
*)so
;
2361 /* Verify preconditions and exercise type/size checks */
2362 assert(PyAnySet_Check(ob
));
2363 assert(PyAnySet_CheckExact(ob
));
2364 assert(!PyFrozenSet_CheckExact(ob
));
2365 assert(PySet_Size(ob
) == 3);
2366 assert(PySet_GET_SIZE(ob
) == 3);
2368 /* Raise TypeError for non-iterable constructor arguments */
2369 assertRaises(PySet_New(Py_None
) == NULL
, PyExc_TypeError
);
2370 assertRaises(PyFrozenSet_New(Py_None
) == NULL
, PyExc_TypeError
);
2372 /* Raise TypeError for unhashable key */
2373 dup
= PySet_New(ob
);
2374 assertRaises(PySet_Discard(ob
, dup
) == -1, PyExc_TypeError
);
2375 assertRaises(PySet_Contains(ob
, dup
) == -1, PyExc_TypeError
);
2376 assertRaises(PySet_Add(ob
, dup
) == -1, PyExc_TypeError
);
2378 /* Exercise successful pop, contains, add, and discard */
2379 elem
= PySet_Pop(ob
);
2380 assert(PySet_Contains(ob
, elem
) == 0);
2381 assert(PySet_GET_SIZE(ob
) == 2);
2382 assert(PySet_Add(ob
, elem
) == 0);
2383 assert(PySet_Contains(ob
, elem
) == 1);
2384 assert(PySet_GET_SIZE(ob
) == 3);
2385 assert(PySet_Discard(ob
, elem
) == 1);
2386 assert(PySet_GET_SIZE(ob
) == 2);
2387 assert(PySet_Discard(ob
, elem
) == 0);
2388 assert(PySet_GET_SIZE(ob
) == 2);
2390 /* Exercise clear */
2391 dup2
= PySet_New(dup
);
2392 assert(PySet_Clear(dup2
) == 0);
2393 assert(PySet_Size(dup2
) == 0);
2396 /* Raise SystemError on clear or update of frozen set */
2397 f
= PyFrozenSet_New(dup
);
2398 assertRaises(PySet_Clear(f
) == -1, PyExc_SystemError
);
2399 assertRaises(_PySet_Update(f
, dup
) == -1, PyExc_SystemError
);
2400 assert(PySet_Add(f
, elem
) == 0);
2402 assertRaises(PySet_Add(f
, elem
) == -1, PyExc_SystemError
);
2406 /* Exercise direct iteration */
2408 while (_PySet_Next((PyObject
*)dup
, &i
, &x
)) {
2409 s
= PyString_AsString(x
);
2410 assert(s
&& (s
[0] == 'a' || s
[0] == 'b' || s
[0] == 'c'));
2415 /* Exercise updates */
2416 dup2
= PySet_New(NULL
);
2417 assert(_PySet_Update(dup2
, dup
) == 0);
2418 assert(PySet_Size(dup2
) == 3);
2419 assert(_PySet_Update(dup2
, dup
) == 0);
2420 assert(PySet_Size(dup2
) == 3);
2423 /* Raise SystemError when self argument is not a set or frozenset. */
2425 assertRaises(PySet_Size(t
) == -1, PyExc_SystemError
);
2426 assertRaises(PySet_Contains(t
, elem
) == -1, PyExc_SystemError
);
2429 /* Raise SystemError when self argument is not a set. */
2430 f
= PyFrozenSet_New(dup
);
2431 assert(PySet_Size(f
) == 3);
2432 assert(PyFrozenSet_CheckExact(f
));
2433 assertRaises(PySet_Discard(f
, elem
) == -1, PyExc_SystemError
);
2434 assertRaises(PySet_Pop(f
) == NULL
, PyExc_SystemError
);
2437 /* Raise KeyError when popping from an empty set */
2438 assert(PyNumber_InPlaceSubtract(ob
, ob
) == ob
);
2440 assert(PySet_GET_SIZE(ob
) == 0);
2441 assertRaises(PySet_Pop(ob
) == NULL
, PyExc_KeyError
);
2443 /* Restore the set from the copy using the PyNumber API */
2444 assert(PyNumber_InPlaceOr(ob
, dup
) == ob
);
2447 /* Verify constructors accept NULL arguments */
2448 f
= PySet_New(NULL
);
2450 assert(PySet_GET_SIZE(f
) == 0);
2452 f
= PyFrozenSet_New(NULL
);
2454 assert(PyFrozenSet_CheckExact(f
));
2455 assert(PySet_GET_SIZE(f
) == 0);