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
;
216 assert(so
->lookup
!= NULL
);
217 entry
= so
->lookup(so
, key
, hash
);
220 if (entry
->key
== NULL
) {
226 } else if (entry
->key
== dummy
) {
240 Internal routine used by set_table_resize() to insert an item which is
241 known to be absent from the set. This routine also assumes that
242 the set contains no deleted entries. Besides the performance benefit,
243 using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
244 Note that no refcounts are changed by this routine; if needed, the caller
245 is responsible for incref'ing `key`.
248 set_insert_clean(register PySetObject
*so
, PyObject
*key
, long hash
)
251 register size_t perturb
;
252 register size_t mask
= (size_t)so
->mask
;
253 setentry
*table
= so
->table
;
254 register setentry
*entry
;
258 for (perturb
= hash
; entry
->key
!= NULL
; perturb
>>= PERTURB_SHIFT
) {
259 i
= (i
<< 2) + i
+ perturb
+ 1;
260 entry
= &table
[i
& mask
];
269 Restructure the table by allocating a new table and reinserting all
270 keys again. When entries have been deleted, the new table may
271 actually be smaller than the old one.
274 set_table_resize(PySetObject
*so
, Py_ssize_t minused
)
277 setentry
*oldtable
, *newtable
, *entry
;
279 int is_oldtable_malloced
;
280 setentry small_copy
[PySet_MINSIZE
];
282 assert(minused
>= 0);
284 /* Find the smallest table size > minused. */
285 for (newsize
= PySet_MINSIZE
;
286 newsize
<= minused
&& newsize
> 0;
294 /* Get space for a new table. */
295 oldtable
= so
->table
;
296 assert(oldtable
!= NULL
);
297 is_oldtable_malloced
= oldtable
!= so
->smalltable
;
299 if (newsize
== PySet_MINSIZE
) {
300 /* A large table is shrinking, or we can't get any smaller. */
301 newtable
= so
->smalltable
;
302 if (newtable
== oldtable
) {
303 if (so
->fill
== so
->used
) {
304 /* No dummies, so no point doing anything. */
307 /* We're not going to resize it, but rebuild the
308 table anyway to purge old dummy entries.
309 Subtle: This is *necessary* if fill==size,
310 as set_lookkey needs at least one virgin slot to
311 terminate failing searches. If fill < size, it's
312 merely desirable, as dummies slow searches. */
313 assert(so
->fill
> so
->used
);
314 memcpy(small_copy
, oldtable
, sizeof(small_copy
));
315 oldtable
= small_copy
;
319 newtable
= PyMem_NEW(setentry
, newsize
);
320 if (newtable
== NULL
) {
326 /* Make the set empty, using the new table. */
327 assert(newtable
!= oldtable
);
328 so
->table
= newtable
;
329 so
->mask
= newsize
- 1;
330 memset(newtable
, 0, sizeof(setentry
) * newsize
);
335 /* Copy the data over; this is refcount-neutral for active entries;
336 dummy entries aren't copied over, of course */
337 for (entry
= oldtable
; i
> 0; entry
++) {
338 if (entry
->key
== NULL
) {
341 } else if (entry
->key
== dummy
) {
344 assert(entry
->key
== dummy
);
345 Py_DECREF(entry
->key
);
349 set_insert_clean(so
, entry
->key
, entry
->hash
);
353 if (is_oldtable_malloced
)
358 /* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
361 set_add_entry(register PySetObject
*so
, setentry
*entry
)
363 register Py_ssize_t n_used
;
364 PyObject
*key
= entry
->key
;
365 long hash
= entry
->hash
;
367 assert(so
->fill
<= so
->mask
); /* at least one empty slot */
370 if (set_insert_key(so
, key
, hash
) == -1) {
374 if (!(so
->used
> n_used
&& so
->fill
*3 >= (so
->mask
+1)*2))
376 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
380 set_add_key(register PySetObject
*so
, PyObject
*key
)
383 register Py_ssize_t n_used
;
385 if (!PyString_CheckExact(key
) ||
386 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
387 hash
= PyObject_Hash(key
);
391 assert(so
->fill
<= so
->mask
); /* at least one empty slot */
394 if (set_insert_key(so
, key
, hash
) == -1) {
398 if (!(so
->used
> n_used
&& so
->fill
*3 >= (so
->mask
+1)*2))
400 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
403 #define DISCARD_NOTFOUND 0
404 #define DISCARD_FOUND 1
407 set_discard_entry(PySetObject
*so
, setentry
*oldentry
)
408 { register setentry
*entry
;
411 entry
= (so
->lookup
)(so
, oldentry
->key
, oldentry
->hash
);
414 if (entry
->key
== NULL
|| entry
->key
== dummy
)
415 return DISCARD_NOTFOUND
;
416 old_key
= entry
->key
;
421 return DISCARD_FOUND
;
425 set_discard_key(PySetObject
*so
, PyObject
*key
)
428 register setentry
*entry
;
431 assert (PyAnySet_Check(so
));
432 if (!PyString_CheckExact(key
) ||
433 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
434 hash
= PyObject_Hash(key
);
438 entry
= (so
->lookup
)(so
, key
, hash
);
441 if (entry
->key
== NULL
|| entry
->key
== dummy
)
442 return DISCARD_NOTFOUND
;
443 old_key
= entry
->key
;
448 return DISCARD_FOUND
;
452 set_clear_internal(PySetObject
*so
)
454 setentry
*entry
, *table
;
455 int table_is_malloced
;
457 setentry small_copy
[PySet_MINSIZE
];
460 assert (PyAnySet_Check(so
));
467 assert(table
!= NULL
);
468 table_is_malloced
= table
!= so
->smalltable
;
470 /* This is delicate. During the process of clearing the set,
471 * decrefs can cause the set to mutate. To avoid fatal confusion
472 * (voice of experience), we have to make the set empty before
473 * clearing the slots, and never refer to anything via so->ref while
477 if (table_is_malloced
)
478 EMPTY_TO_MINSIZE(so
);
481 /* It's a small table with something that needs to be cleared.
482 * Afraid the only safe way is to copy the set entries into
483 * another small table first.
485 memcpy(small_copy
, table
, sizeof(small_copy
));
487 EMPTY_TO_MINSIZE(so
);
489 /* else it's a small table that's already empty */
491 /* Now we can finally clear things. If C had refcounts, we could
492 * assert that the refcount on table is 1 now, i.e. that this function
493 * has unique access to it, so decref side-effects can't alter it.
495 for (entry
= table
; fill
> 0; ++entry
) {
502 Py_DECREF(entry
->key
);
506 assert(entry
->key
== NULL
);
510 if (table_is_malloced
)
516 * Iterate over a set table. Use like so:
520 * pos = 0; # important! pos should not otherwise be changed by you
521 * while (set_next(yourset, &pos, &entry)) {
522 * Refer to borrowed reference in entry->key.
525 * CAUTION: In general, it isn't safe to use set_next in a loop that
529 set_next(PySetObject
*so
, Py_ssize_t
*pos_ptr
, setentry
**entry_ptr
)
533 register setentry
*table
;
535 assert (PyAnySet_Check(so
));
540 while (i
<= mask
&& (table
[i
].key
== NULL
|| table
[i
].key
== dummy
))
545 assert(table
[i
].key
!= NULL
);
546 *entry_ptr
= &table
[i
];
551 set_dealloc(PySetObject
*so
)
553 register setentry
*entry
;
554 Py_ssize_t fill
= so
->fill
;
555 PyObject_GC_UnTrack(so
);
556 Py_TRASHCAN_SAFE_BEGIN(so
)
557 if (so
->weakreflist
!= NULL
)
558 PyObject_ClearWeakRefs((PyObject
*) so
);
560 for (entry
= so
->table
; fill
> 0; entry
++) {
563 Py_DECREF(entry
->key
);
566 if (so
->table
!= so
->smalltable
)
567 PyMem_DEL(so
->table
);
568 if (numfree
< PySet_MAXFREELIST
&& PyAnySet_CheckExact(so
))
569 free_list
[numfree
++] = so
;
571 Py_TYPE(so
)->tp_free(so
);
572 Py_TRASHCAN_SAFE_END(so
)
576 set_tp_print(PySetObject
*so
, FILE *fp
, int flags
)
580 char *emit
= ""; /* No separator emitted on first pass */
581 char *separator
= ", ";
582 int status
= Py_ReprEnter((PyObject
*)so
);
587 Py_BEGIN_ALLOW_THREADS
588 fprintf(fp
, "%s(...)", so
->ob_type
->tp_name
);
593 Py_BEGIN_ALLOW_THREADS
594 fprintf(fp
, "%s([", so
->ob_type
->tp_name
);
596 while (set_next(so
, &pos
, &entry
)) {
597 Py_BEGIN_ALLOW_THREADS
601 if (PyObject_Print(entry
->key
, fp
, 0) != 0) {
602 Py_ReprLeave((PyObject
*)so
);
606 Py_BEGIN_ALLOW_THREADS
609 Py_ReprLeave((PyObject
*)so
);
614 set_repr(PySetObject
*so
)
616 PyObject
*keys
, *result
=NULL
, *listrepr
;
617 int status
= Py_ReprEnter((PyObject
*)so
);
622 return PyString_FromFormat("%s(...)", so
->ob_type
->tp_name
);
625 keys
= PySequence_List((PyObject
*)so
);
628 listrepr
= PyObject_Repr(keys
);
630 if (listrepr
== NULL
)
633 result
= PyString_FromFormat("%s(%s)", so
->ob_type
->tp_name
,
634 PyString_AS_STRING(listrepr
));
637 Py_ReprLeave((PyObject
*)so
);
642 set_len(PyObject
*so
)
644 return ((PySetObject
*)so
)->used
;
648 set_merge(PySetObject
*so
, PyObject
*otherset
)
653 register Py_ssize_t i
;
654 register setentry
*entry
;
656 assert (PyAnySet_Check(so
));
657 assert (PyAnySet_Check(otherset
));
659 other
= (PySetObject
*)otherset
;
660 if (other
== so
|| other
->used
== 0)
661 /* a.update(a) or a.update({}); nothing to do */
663 /* Do one big resize at the start, rather than
664 * incrementally resizing as we insert new keys. Expect
665 * that there will be no (or few) overlapping keys.
667 if ((so
->fill
+ other
->used
)*3 >= (so
->mask
+1)*2) {
668 if (set_table_resize(so
, (so
->used
+ other
->used
)*2) != 0)
671 for (i
= 0; i
<= other
->mask
; i
++) {
672 entry
= &other
->table
[i
];
678 if (set_insert_key(so
, key
, hash
) == -1) {
688 set_contains_key(PySetObject
*so
, PyObject
*key
)
693 if (!PyString_CheckExact(key
) ||
694 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
695 hash
= PyObject_Hash(key
);
699 entry
= (so
->lookup
)(so
, key
, hash
);
703 return key
!= NULL
&& key
!= dummy
;
707 set_contains_entry(PySetObject
*so
, setentry
*entry
)
712 lu_entry
= (so
->lookup
)(so
, entry
->key
, entry
->hash
);
713 if (lu_entry
== NULL
)
716 return key
!= NULL
&& key
!= dummy
;
720 set_pop(PySetObject
*so
)
722 register Py_ssize_t i
= 0;
723 register setentry
*entry
;
726 assert (PyAnySet_Check(so
));
728 PyErr_SetString(PyExc_KeyError
, "pop from an empty set");
732 /* Set entry to "the first" unused or dummy set entry. We abuse
733 * the hash field of slot 0 to hold a search finger:
734 * If slot 0 has a value, use slot 0.
735 * Else slot 0 is being used to hold a search finger,
736 * and we use its hash value as the first index to look.
738 entry
= &so
->table
[0];
739 if (entry
->key
== NULL
|| entry
->key
== dummy
) {
741 /* The hash field may be a real hash value, or it may be a
742 * legit search finger, or it may be a once-legit search
743 * finger that's out of bounds now because it wrapped around
744 * or the table shrunk -- simply make sure it's in bounds now.
746 if (i
> so
->mask
|| i
< 1)
747 i
= 1; /* skip slot 0 */
748 while ((entry
= &so
->table
[i
])->key
== NULL
|| entry
->key
==dummy
) {
758 so
->table
[0].hash
= i
+ 1; /* next place to start */
762 PyDoc_STRVAR(pop_doc
, "Remove and return an arbitrary set element.\n\
763 Raises KeyError if the set is empty.");
766 set_traverse(PySetObject
*so
, visitproc visit
, void *arg
)
771 while (set_next(so
, &pos
, &entry
))
772 Py_VISIT(entry
->key
);
777 frozenset_hash(PyObject
*self
)
779 PySetObject
*so
= (PySetObject
*)self
;
780 long h
, hash
= 1927868237L;
787 hash
*= PySet_GET_SIZE(self
) + 1;
788 while (set_next(so
, &pos
, &entry
)) {
789 /* Work to increase the bit dispersion for closely spaced hash
790 values. The is important because some use cases have many
791 combinations of a small number of elements with nearby
792 hashes so that many distinct combinations collapse to only
793 a handful of distinct hash values. */
795 hash
^= (h
^ (h
<< 16) ^ 89869747L) * 3644798167u;
797 hash
= hash
* 69069L + 907133923L;
804 /***** Set iterator type ***********************************************/
808 PySetObject
*si_set
; /* Set to NULL when iterator is exhausted */
815 setiter_dealloc(setiterobject
*si
)
817 Py_XDECREF(si
->si_set
);
822 setiter_traverse(setiterobject
*si
, visitproc visit
, void *arg
)
824 Py_VISIT(si
->si_set
);
829 setiter_len(setiterobject
*si
)
832 if (si
->si_set
!= NULL
&& si
->si_used
== si
->si_set
->used
)
834 return PyInt_FromLong(len
);
837 PyDoc_STRVAR(length_hint_doc
, "Private method returning an estimate of len(list(it)).");
839 static PyMethodDef setiter_methods
[] = {
840 {"__length_hint__", (PyCFunction
)setiter_len
, METH_NOARGS
, length_hint_doc
},
841 {NULL
, NULL
} /* sentinel */
844 static PyObject
*setiter_iternext(setiterobject
*si
)
847 register Py_ssize_t i
, mask
;
848 register setentry
*entry
;
849 PySetObject
*so
= si
->si_set
;
853 assert (PyAnySet_Check(so
));
855 if (si
->si_used
!= so
->used
) {
856 PyErr_SetString(PyExc_RuntimeError
,
857 "Set changed size during iteration");
858 si
->si_used
= -1; /* Make this state sticky */
866 while (i
<= mask
&& (entry
[i
].key
== NULL
|| entry
[i
].key
== dummy
))
882 static PyTypeObject PySetIter_Type
= {
883 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
884 "setiterator", /* tp_name */
885 sizeof(setiterobject
), /* tp_basicsize */
888 (destructor
)setiter_dealloc
, /* tp_dealloc */
894 0, /* tp_as_number */
895 0, /* tp_as_sequence */
896 0, /* tp_as_mapping */
900 PyObject_GenericGetAttr
, /* tp_getattro */
902 0, /* tp_as_buffer */
903 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
905 (traverseproc
)setiter_traverse
, /* tp_traverse */
907 0, /* tp_richcompare */
908 0, /* tp_weaklistoffset */
909 PyObject_SelfIter
, /* tp_iter */
910 (iternextfunc
)setiter_iternext
, /* tp_iternext */
911 setiter_methods
, /* tp_methods */
916 set_iter(PySetObject
*so
)
918 setiterobject
*si
= PyObject_GC_New(setiterobject
, &PySetIter_Type
);
923 si
->si_used
= so
->used
;
926 _PyObject_GC_TRACK(si
);
927 return (PyObject
*)si
;
931 set_update_internal(PySetObject
*so
, PyObject
*other
)
935 if (PyAnySet_Check(other
))
936 return set_merge(so
, other
);
938 if (PyDict_CheckExact(other
)) {
942 Py_ssize_t dictsize
= PyDict_Size(other
);
944 /* Do one big resize at the start, rather than
945 * incrementally resizing as we insert new keys. Expect
946 * that there will be no (or few) overlapping keys.
950 if ((so
->fill
+ dictsize
)*3 >= (so
->mask
+1)*2) {
951 if (set_table_resize(so
, (so
->used
+ dictsize
)*2) != 0)
954 while (_PyDict_Next(other
, &pos
, &key
, &value
, &hash
)) {
957 an_entry
.hash
= hash
;
959 if (set_add_entry(so
, &an_entry
) == -1)
965 it
= PyObject_GetIter(other
);
969 while ((key
= PyIter_Next(it
)) != NULL
) {
970 if (set_add_key(so
, key
) == -1) {
978 if (PyErr_Occurred())
984 set_update(PySetObject
*so
, PyObject
*args
)
988 for (i
=0 ; i
<PyTuple_GET_SIZE(args
) ; i
++) {
989 PyObject
*other
= PyTuple_GET_ITEM(args
, i
);
990 if (set_update_internal(so
, other
) == -1)
996 PyDoc_STRVAR(update_doc
,
997 "Update a set with the union of itself and others.");
1000 make_new_set(PyTypeObject
*type
, PyObject
*iterable
)
1002 register PySetObject
*so
= NULL
;
1004 if (dummy
== NULL
) { /* Auto-initialize dummy */
1005 dummy
= PyString_FromString("<dummy key>");
1010 /* create PySetObject structure */
1012 (type
== &PySet_Type
|| type
== &PyFrozenSet_Type
)) {
1013 so
= free_list
[--numfree
];
1014 assert (so
!= NULL
&& PyAnySet_CheckExact(so
));
1016 _Py_NewReference((PyObject
*)so
);
1017 EMPTY_TO_MINSIZE(so
);
1018 PyObject_GC_Track(so
);
1020 so
= (PySetObject
*)type
->tp_alloc(type
, 0);
1023 /* tp_alloc has already zeroed the structure */
1024 assert(so
->table
== NULL
&& so
->fill
== 0 && so
->used
== 0);
1025 INIT_NONZERO_SET_SLOTS(so
);
1028 so
->lookup
= set_lookkey_string
;
1029 so
->weakreflist
= NULL
;
1031 if (iterable
!= NULL
) {
1032 if (set_update_internal(so
, iterable
) == -1) {
1038 return (PyObject
*)so
;
1041 /* The empty frozenset is a singleton */
1042 static PyObject
*emptyfrozenset
= NULL
;
1045 frozenset_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1047 PyObject
*iterable
= NULL
, *result
;
1049 if (type
== &PyFrozenSet_Type
&& !_PyArg_NoKeywords("frozenset()", kwds
))
1052 if (!PyArg_UnpackTuple(args
, type
->tp_name
, 0, 1, &iterable
))
1055 if (type
!= &PyFrozenSet_Type
)
1056 return make_new_set(type
, iterable
);
1058 if (iterable
!= NULL
) {
1059 /* frozenset(f) is idempotent */
1060 if (PyFrozenSet_CheckExact(iterable
)) {
1061 Py_INCREF(iterable
);
1064 result
= make_new_set(type
, iterable
);
1065 if (result
== NULL
|| PySet_GET_SIZE(result
))
1069 /* The empty frozenset is a singleton */
1070 if (emptyfrozenset
== NULL
)
1071 emptyfrozenset
= make_new_set(type
, NULL
);
1072 Py_XINCREF(emptyfrozenset
);
1073 return emptyfrozenset
;
1083 so
= free_list
[numfree
];
1084 PyObject_GC_Del(so
);
1087 Py_CLEAR(emptyfrozenset
);
1091 set_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1093 if (type
== &PySet_Type
&& !_PyArg_NoKeywords("set()", kwds
))
1096 return make_new_set(type
, NULL
);
1099 /* set_swap_bodies() switches the contents of any two sets by moving their
1100 internal data pointers and, if needed, copying the internal smalltables.
1101 Semantically equivalent to:
1103 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1105 The function always succeeds and it leaves both objects in a stable state.
1106 Useful for creating temporary frozensets from sets for membership testing
1107 in __contains__(), discard(), and remove(). Also useful for operations
1108 that update in-place (by allowing an intermediate result to be swapped
1109 into one of the original inputs).
1113 set_swap_bodies(PySetObject
*a
, PySetObject
*b
)
1117 setentry
*(*f
)(PySetObject
*so
, PyObject
*key
, long hash
);
1118 setentry tab
[PySet_MINSIZE
];
1121 t
= a
->fill
; a
->fill
= b
->fill
; b
->fill
= t
;
1122 t
= a
->used
; a
->used
= b
->used
; b
->used
= t
;
1123 t
= a
->mask
; a
->mask
= b
->mask
; b
->mask
= t
;
1126 if (a
->table
== a
->smalltable
)
1128 a
->table
= b
->table
;
1129 if (b
->table
== b
->smalltable
)
1130 a
->table
= a
->smalltable
;
1133 f
= a
->lookup
; a
->lookup
= b
->lookup
; b
->lookup
= f
;
1135 if (a
->table
== a
->smalltable
|| b
->table
== b
->smalltable
) {
1136 memcpy(tab
, a
->smalltable
, sizeof(tab
));
1137 memcpy(a
->smalltable
, b
->smalltable
, sizeof(tab
));
1138 memcpy(b
->smalltable
, tab
, sizeof(tab
));
1141 if (PyType_IsSubtype(Py_TYPE(a
), &PyFrozenSet_Type
) &&
1142 PyType_IsSubtype(Py_TYPE(b
), &PyFrozenSet_Type
)) {
1143 h
= a
->hash
; a
->hash
= b
->hash
; b
->hash
= h
;
1151 set_copy(PySetObject
*so
)
1153 return make_new_set(Py_TYPE(so
), (PyObject
*)so
);
1157 frozenset_copy(PySetObject
*so
)
1159 if (PyFrozenSet_CheckExact(so
)) {
1161 return (PyObject
*)so
;
1163 return set_copy(so
);
1166 PyDoc_STRVAR(copy_doc
, "Return a shallow copy of a set.");
1169 set_clear(PySetObject
*so
)
1171 set_clear_internal(so
);
1175 PyDoc_STRVAR(clear_doc
, "Remove all elements from this set.");
1178 set_union(PySetObject
*so
, PyObject
*args
)
1180 PySetObject
*result
;
1184 result
= (PySetObject
*)set_copy(so
);
1188 for (i
=0 ; i
<PyTuple_GET_SIZE(args
) ; i
++) {
1189 other
= PyTuple_GET_ITEM(args
, i
);
1190 if ((PyObject
*)so
== other
)
1192 if (set_update_internal(result
, other
) == -1) {
1197 return (PyObject
*)result
;
1200 PyDoc_STRVAR(union_doc
,
1201 "Return the union of sets as a new set.\n\
1203 (i.e. all elements that are in either set.)");
1206 set_or(PySetObject
*so
, PyObject
*other
)
1208 PySetObject
*result
;
1210 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1211 Py_INCREF(Py_NotImplemented
);
1212 return Py_NotImplemented
;
1215 result
= (PySetObject
*)set_copy(so
);
1218 if ((PyObject
*)so
== other
)
1219 return (PyObject
*)result
;
1220 if (set_update_internal(result
, other
) == -1) {
1224 return (PyObject
*)result
;
1228 set_ior(PySetObject
*so
, PyObject
*other
)
1230 if (!PyAnySet_Check(other
)) {
1231 Py_INCREF(Py_NotImplemented
);
1232 return Py_NotImplemented
;
1234 if (set_update_internal(so
, other
) == -1)
1237 return (PyObject
*)so
;
1241 set_intersection(PySetObject
*so
, PyObject
*other
)
1243 PySetObject
*result
;
1244 PyObject
*key
, *it
, *tmp
;
1246 if ((PyObject
*)so
== other
)
1247 return set_copy(so
);
1249 result
= (PySetObject
*)make_new_set(Py_TYPE(so
), NULL
);
1253 if (PyAnySet_Check(other
)) {
1257 if (PySet_GET_SIZE(other
) > PySet_GET_SIZE(so
)) {
1258 tmp
= (PyObject
*)so
;
1259 so
= (PySetObject
*)other
;
1263 while (set_next((PySetObject
*)other
, &pos
, &entry
)) {
1264 int rv
= set_contains_entry(so
, entry
);
1270 if (set_add_entry(result
, entry
) == -1) {
1276 return (PyObject
*)result
;
1279 it
= PyObject_GetIter(other
);
1285 while ((key
= PyIter_Next(it
)) != NULL
) {
1288 long hash
= PyObject_Hash(key
);
1298 rv
= set_contains_entry(so
, &entry
);
1306 if (set_add_entry(result
, &entry
) == -1) {
1316 if (PyErr_Occurred()) {
1320 return (PyObject
*)result
;
1324 set_intersection_multi(PySetObject
*so
, PyObject
*args
)
1327 PyObject
*result
= (PyObject
*)so
;
1329 if (PyTuple_GET_SIZE(args
) == 0)
1330 return set_copy(so
);
1333 for (i
=0 ; i
<PyTuple_GET_SIZE(args
) ; i
++) {
1334 PyObject
*other
= PyTuple_GET_ITEM(args
, i
);
1335 PyObject
*newresult
= set_intersection((PySetObject
*)result
, other
);
1336 if (newresult
== NULL
) {
1346 PyDoc_STRVAR(intersection_doc
,
1347 "Return the intersection of two or more sets as a new set.\n\
1349 (i.e. elements that are common to all of the sets.)");
1352 set_intersection_update(PySetObject
*so
, PyObject
*other
)
1356 tmp
= set_intersection(so
, other
);
1359 set_swap_bodies(so
, (PySetObject
*)tmp
);
1365 set_intersection_update_multi(PySetObject
*so
, PyObject
*args
)
1369 tmp
= set_intersection_multi(so
, args
);
1372 set_swap_bodies(so
, (PySetObject
*)tmp
);
1377 PyDoc_STRVAR(intersection_update_doc
,
1378 "Update a set with the intersection of itself and another.");
1381 set_and(PySetObject
*so
, PyObject
*other
)
1383 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1384 Py_INCREF(Py_NotImplemented
);
1385 return Py_NotImplemented
;
1387 return set_intersection(so
, other
);
1391 set_iand(PySetObject
*so
, PyObject
*other
)
1395 if (!PyAnySet_Check(other
)) {
1396 Py_INCREF(Py_NotImplemented
);
1397 return Py_NotImplemented
;
1399 result
= set_intersection_update(so
, other
);
1404 return (PyObject
*)so
;
1408 set_isdisjoint(PySetObject
*so
, PyObject
*other
)
1410 PyObject
*key
, *it
, *tmp
;
1412 if ((PyObject
*)so
== other
) {
1413 if (PySet_GET_SIZE(so
) == 0)
1419 if (PyAnySet_CheckExact(other
)) {
1423 if (PySet_GET_SIZE(other
) > PySet_GET_SIZE(so
)) {
1424 tmp
= (PyObject
*)so
;
1425 so
= (PySetObject
*)other
;
1428 while (set_next((PySetObject
*)other
, &pos
, &entry
)) {
1429 int rv
= set_contains_entry(so
, entry
);
1438 it
= PyObject_GetIter(other
);
1442 while ((key
= PyIter_Next(it
)) != NULL
) {
1445 long hash
= PyObject_Hash(key
);
1454 rv
= set_contains_entry(so
, &entry
);
1466 if (PyErr_Occurred())
1471 PyDoc_STRVAR(isdisjoint_doc
,
1472 "Return True if two sets have a null intersection.");
1475 set_difference_update_internal(PySetObject
*so
, PyObject
*other
)
1477 if ((PyObject
*)so
== other
)
1478 return set_clear_internal(so
);
1480 if (PyAnySet_Check(other
)) {
1484 while (set_next((PySetObject
*)other
, &pos
, &entry
))
1485 if (set_discard_entry(so
, entry
) == -1)
1489 it
= PyObject_GetIter(other
);
1493 while ((key
= PyIter_Next(it
)) != NULL
) {
1494 if (set_discard_key(so
, key
) == -1) {
1502 if (PyErr_Occurred())
1505 /* If more than 1/5 are dummies, then resize them away. */
1506 if ((so
->fill
- so
->used
) * 5 < so
->mask
)
1508 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
1512 set_difference_update(PySetObject
*so
, PyObject
*args
)
1516 for (i
=0 ; i
<PyTuple_GET_SIZE(args
) ; i
++) {
1517 PyObject
*other
= PyTuple_GET_ITEM(args
, i
);
1518 if (set_difference_update_internal(so
, other
) == -1)
1524 PyDoc_STRVAR(difference_update_doc
,
1525 "Remove all elements of another set from this set.");
1528 set_difference(PySetObject
*so
, PyObject
*other
)
1534 if (!PyAnySet_Check(other
) && !PyDict_CheckExact(other
)) {
1535 result
= set_copy(so
);
1538 if (set_difference_update_internal((PySetObject
*)result
, other
) != -1)
1544 result
= make_new_set(Py_TYPE(so
), NULL
);
1548 if (PyDict_CheckExact(other
)) {
1549 while (set_next(so
, &pos
, &entry
)) {
1551 entrycopy
.hash
= entry
->hash
;
1552 entrycopy
.key
= entry
->key
;
1553 if (!_PyDict_Contains(other
, entry
->key
, entry
->hash
)) {
1554 if (set_add_entry((PySetObject
*)result
, &entrycopy
) == -1) {
1563 while (set_next(so
, &pos
, &entry
)) {
1564 int rv
= set_contains_entry((PySetObject
*)other
, entry
);
1570 if (set_add_entry((PySetObject
*)result
, entry
) == -1) {
1580 set_difference_multi(PySetObject
*so
, PyObject
*args
)
1583 PyObject
*result
, *other
;
1585 if (PyTuple_GET_SIZE(args
) == 0)
1586 return set_copy(so
);
1588 other
= PyTuple_GET_ITEM(args
, 0);
1589 result
= set_difference(so
, other
);
1593 for (i
=1 ; i
<PyTuple_GET_SIZE(args
) ; i
++) {
1594 other
= PyTuple_GET_ITEM(args
, i
);
1595 if (set_difference_update_internal((PySetObject
*)result
, other
) == -1) {
1603 PyDoc_STRVAR(difference_doc
,
1604 "Return the difference of two or more sets as a new set.\n\
1606 (i.e. all elements that are in this set but not the others.)");
1608 set_sub(PySetObject
*so
, PyObject
*other
)
1610 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1611 Py_INCREF(Py_NotImplemented
);
1612 return Py_NotImplemented
;
1614 return set_difference(so
, other
);
1618 set_isub(PySetObject
*so
, PyObject
*other
)
1620 if (!PyAnySet_Check(other
)) {
1621 Py_INCREF(Py_NotImplemented
);
1622 return Py_NotImplemented
;
1624 if (set_difference_update_internal(so
, other
) == -1)
1627 return (PyObject
*)so
;
1631 set_symmetric_difference_update(PySetObject
*so
, PyObject
*other
)
1633 PySetObject
*otherset
;
1638 if ((PyObject
*)so
== other
)
1639 return set_clear(so
);
1641 if (PyDict_CheckExact(other
)) {
1645 while (_PyDict_Next(other
, &pos
, &key
, &value
, &hash
)) {
1649 an_entry
.hash
= hash
;
1652 rv
= set_discard_entry(so
, &an_entry
);
1657 if (rv
== DISCARD_NOTFOUND
) {
1658 if (set_add_entry(so
, &an_entry
) == -1) {
1668 if (PyAnySet_Check(other
)) {
1670 otherset
= (PySetObject
*)other
;
1672 otherset
= (PySetObject
*)make_new_set(Py_TYPE(so
), other
);
1673 if (otherset
== NULL
)
1677 while (set_next(otherset
, &pos
, &entry
)) {
1678 int rv
= set_discard_entry(so
, entry
);
1680 Py_DECREF(otherset
);
1683 if (rv
== DISCARD_NOTFOUND
) {
1684 if (set_add_entry(so
, entry
) == -1) {
1685 Py_DECREF(otherset
);
1690 Py_DECREF(otherset
);
1694 PyDoc_STRVAR(symmetric_difference_update_doc
,
1695 "Update a set with the symmetric difference of itself and another.");
1698 set_symmetric_difference(PySetObject
*so
, PyObject
*other
)
1701 PySetObject
*otherset
;
1703 otherset
= (PySetObject
*)make_new_set(Py_TYPE(so
), other
);
1704 if (otherset
== NULL
)
1706 rv
= set_symmetric_difference_update(otherset
, (PyObject
*)so
);
1710 return (PyObject
*)otherset
;
1713 PyDoc_STRVAR(symmetric_difference_doc
,
1714 "Return the symmetric difference of two sets as a new set.\n\
1716 (i.e. all elements that are in exactly one of the sets.)");
1719 set_xor(PySetObject
*so
, PyObject
*other
)
1721 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1722 Py_INCREF(Py_NotImplemented
);
1723 return Py_NotImplemented
;
1725 return set_symmetric_difference(so
, other
);
1729 set_ixor(PySetObject
*so
, PyObject
*other
)
1733 if (!PyAnySet_Check(other
)) {
1734 Py_INCREF(Py_NotImplemented
);
1735 return Py_NotImplemented
;
1737 result
= set_symmetric_difference_update(so
, other
);
1742 return (PyObject
*)so
;
1746 set_issubset(PySetObject
*so
, PyObject
*other
)
1751 if (!PyAnySet_Check(other
)) {
1752 PyObject
*tmp
, *result
;
1753 tmp
= make_new_set(&PySet_Type
, other
);
1756 result
= set_issubset(so
, tmp
);
1760 if (PySet_GET_SIZE(so
) > PySet_GET_SIZE(other
))
1763 while (set_next(so
, &pos
, &entry
)) {
1764 int rv
= set_contains_entry((PySetObject
*)other
, entry
);
1773 PyDoc_STRVAR(issubset_doc
, "Report whether another set contains this set.");
1776 set_issuperset(PySetObject
*so
, PyObject
*other
)
1778 PyObject
*tmp
, *result
;
1780 if (!PyAnySet_Check(other
)) {
1781 tmp
= make_new_set(&PySet_Type
, other
);
1784 result
= set_issuperset(so
, tmp
);
1788 return set_issubset((PySetObject
*)other
, (PyObject
*)so
);
1791 PyDoc_STRVAR(issuperset_doc
, "Report whether this set contains another set.");
1794 set_richcompare(PySetObject
*v
, PyObject
*w
, int op
)
1798 if(!PyAnySet_Check(w
)) {
1799 Py_INCREF(Py_NotImplemented
);
1800 return Py_NotImplemented
;
1804 if (PySet_GET_SIZE(v
) != PySet_GET_SIZE(w
))
1806 if (v
->hash
!= -1 &&
1807 ((PySetObject
*)w
)->hash
!= -1 &&
1808 v
->hash
!= ((PySetObject
*)w
)->hash
)
1810 return set_issubset(v
, w
);
1812 r1
= set_richcompare(v
, w
, Py_EQ
);
1815 r2
= PyBool_FromLong(PyObject_Not(r1
));
1819 return set_issubset(v
, w
);
1821 return set_issuperset(v
, w
);
1823 if (PySet_GET_SIZE(v
) >= PySet_GET_SIZE(w
))
1825 return set_issubset(v
, w
);
1827 if (PySet_GET_SIZE(v
) <= PySet_GET_SIZE(w
))
1829 return set_issuperset(v
, w
);
1831 Py_INCREF(Py_NotImplemented
);
1832 return Py_NotImplemented
;
1836 set_nocmp(PyObject
*self
, PyObject
*other
)
1838 PyErr_SetString(PyExc_TypeError
, "cannot compare sets using cmp()");
1843 set_add(PySetObject
*so
, PyObject
*key
)
1845 if (set_add_key(so
, key
) == -1)
1850 PyDoc_STRVAR(add_doc
,
1851 "Add an element to a set.\n\
1853 This has no effect if the element is already present.");
1856 set_contains(PySetObject
*so
, PyObject
*key
)
1861 rv
= set_contains_key(so
, key
);
1863 if (!PySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1866 tmpkey
= make_new_set(&PyFrozenSet_Type
, key
);
1869 rv
= set_contains_key(so
, tmpkey
);
1876 set_direct_contains(PySetObject
*so
, PyObject
*key
)
1880 result
= set_contains(so
, key
);
1883 return PyBool_FromLong(result
);
1886 PyDoc_STRVAR(contains_doc
, "x.__contains__(y) <==> y in x.");
1889 set_remove(PySetObject
*so
, PyObject
*key
)
1894 rv
= set_discard_key(so
, key
);
1896 if (!PySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1899 tmpkey
= make_new_set(&PyFrozenSet_Type
, key
);
1902 rv
= set_discard_key(so
, tmpkey
);
1908 if (rv
== DISCARD_NOTFOUND
) {
1915 PyDoc_STRVAR(remove_doc
,
1916 "Remove an element from a set; it must be a member.\n\
1918 If the element is not a member, raise a KeyError.");
1921 set_discard(PySetObject
*so
, PyObject
*key
)
1926 rv
= set_discard_key(so
, key
);
1928 if (!PySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1931 tmpkey
= make_new_set(&PyFrozenSet_Type
, key
);
1934 rv
= set_discard_key(so
, tmpkey
);
1942 PyDoc_STRVAR(discard_doc
,
1943 "Remove an element from a set if it is a member.\n\
1945 If the element is not a member, do nothing.");
1948 set_reduce(PySetObject
*so
)
1950 PyObject
*keys
=NULL
, *args
=NULL
, *result
=NULL
, *dict
=NULL
;
1952 keys
= PySequence_List((PyObject
*)so
);
1955 args
= PyTuple_Pack(1, keys
);
1958 dict
= PyObject_GetAttrString((PyObject
*)so
, "__dict__");
1964 result
= PyTuple_Pack(3, Py_TYPE(so
), args
, dict
);
1972 PyDoc_STRVAR(reduce_doc
, "Return state information for pickling.");
1975 set_sizeof(PySetObject
*so
)
1979 res
= sizeof(PySetObject
);
1980 if (so
->table
!= so
->smalltable
)
1981 res
= res
+ (so
->mask
+ 1) * sizeof(setentry
);
1982 return PyInt_FromSsize_t(res
);
1985 PyDoc_STRVAR(sizeof_doc
, "S.__sizeof__() -> size of S in memory, in bytes");
1987 set_init(PySetObject
*self
, PyObject
*args
, PyObject
*kwds
)
1989 PyObject
*iterable
= NULL
;
1991 if (!PyAnySet_Check(self
))
1993 if (PySet_Check(self
) && !_PyArg_NoKeywords("set()", kwds
))
1995 if (!PyArg_UnpackTuple(args
, Py_TYPE(self
)->tp_name
, 0, 1, &iterable
))
1997 set_clear_internal(self
);
1999 if (iterable
== NULL
)
2001 return set_update_internal(self
, iterable
);
2004 static PySequenceMethods set_as_sequence
= {
2005 set_len
, /* sq_length */
2010 0, /* sq_ass_item */
2011 0, /* sq_ass_slice */
2012 (objobjproc
)set_contains
, /* sq_contains */
2015 /* set object ********************************************************/
2018 static PyObject
*test_c_api(PySetObject
*so
);
2020 PyDoc_STRVAR(test_c_api_doc
, "Exercises C API. Returns True.\n\
2021 All is well if assertions don't fail.");
2024 static PyMethodDef set_methods
[] = {
2025 {"add", (PyCFunction
)set_add
, METH_O
,
2027 {"clear", (PyCFunction
)set_clear
, METH_NOARGS
,
2029 {"__contains__",(PyCFunction
)set_direct_contains
, METH_O
| METH_COEXIST
,
2031 {"copy", (PyCFunction
)set_copy
, METH_NOARGS
,
2033 {"discard", (PyCFunction
)set_discard
, METH_O
,
2035 {"difference", (PyCFunction
)set_difference_multi
, METH_VARARGS
,
2037 {"difference_update", (PyCFunction
)set_difference_update
, METH_VARARGS
,
2038 difference_update_doc
},
2039 {"intersection",(PyCFunction
)set_intersection_multi
, METH_VARARGS
,
2041 {"intersection_update",(PyCFunction
)set_intersection_update_multi
, METH_VARARGS
,
2042 intersection_update_doc
},
2043 {"isdisjoint", (PyCFunction
)set_isdisjoint
, METH_O
,
2045 {"issubset", (PyCFunction
)set_issubset
, METH_O
,
2047 {"issuperset", (PyCFunction
)set_issuperset
, METH_O
,
2049 {"pop", (PyCFunction
)set_pop
, METH_NOARGS
,
2051 {"__reduce__", (PyCFunction
)set_reduce
, METH_NOARGS
,
2053 {"remove", (PyCFunction
)set_remove
, METH_O
,
2055 {"__sizeof__", (PyCFunction
)set_sizeof
, METH_NOARGS
,
2057 {"symmetric_difference",(PyCFunction
)set_symmetric_difference
, METH_O
,
2058 symmetric_difference_doc
},
2059 {"symmetric_difference_update",(PyCFunction
)set_symmetric_difference_update
, METH_O
,
2060 symmetric_difference_update_doc
},
2062 {"test_c_api", (PyCFunction
)test_c_api
, METH_NOARGS
,
2065 {"union", (PyCFunction
)set_union
, METH_VARARGS
,
2067 {"update", (PyCFunction
)set_update
, METH_VARARGS
,
2069 {NULL
, NULL
} /* sentinel */
2072 static PyNumberMethods set_as_number
= {
2074 (binaryfunc
)set_sub
, /*nb_subtract*/
2087 (binaryfunc
)set_and
, /*nb_and*/
2088 (binaryfunc
)set_xor
, /*nb_xor*/
2089 (binaryfunc
)set_or
, /*nb_or*/
2096 0, /*nb_inplace_add*/
2097 (binaryfunc
)set_isub
, /*nb_inplace_subtract*/
2098 0, /*nb_inplace_multiply*/
2099 0, /*nb_inplace_divide*/
2100 0, /*nb_inplace_remainder*/
2101 0, /*nb_inplace_power*/
2102 0, /*nb_inplace_lshift*/
2103 0, /*nb_inplace_rshift*/
2104 (binaryfunc
)set_iand
, /*nb_inplace_and*/
2105 (binaryfunc
)set_ixor
, /*nb_inplace_xor*/
2106 (binaryfunc
)set_ior
, /*nb_inplace_or*/
2109 PyDoc_STRVAR(set_doc
,
2110 "set() -> new empty set object\n\
2111 set(iterable) -> new set object\n\
2113 Build an unordered collection of unique elements.");
2115 PyTypeObject PySet_Type
= {
2116 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2117 "set", /* tp_name */
2118 sizeof(PySetObject
), /* tp_basicsize */
2119 0, /* tp_itemsize */
2121 (destructor
)set_dealloc
, /* tp_dealloc */
2122 (printfunc
)set_tp_print
, /* tp_print */
2125 set_nocmp
, /* tp_compare */
2126 (reprfunc
)set_repr
, /* tp_repr */
2127 &set_as_number
, /* tp_as_number */
2128 &set_as_sequence
, /* tp_as_sequence */
2129 0, /* tp_as_mapping */
2130 (hashfunc
)PyObject_HashNotImplemented
, /* tp_hash */
2133 PyObject_GenericGetAttr
, /* tp_getattro */
2134 0, /* tp_setattro */
2135 0, /* tp_as_buffer */
2136 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
| Py_TPFLAGS_CHECKTYPES
|
2137 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2138 set_doc
, /* tp_doc */
2139 (traverseproc
)set_traverse
, /* tp_traverse */
2140 (inquiry
)set_clear_internal
, /* tp_clear */
2141 (richcmpfunc
)set_richcompare
, /* tp_richcompare */
2142 offsetof(PySetObject
, weakreflist
), /* tp_weaklistoffset */
2143 (getiterfunc
)set_iter
, /* tp_iter */
2144 0, /* tp_iternext */
2145 set_methods
, /* tp_methods */
2150 0, /* tp_descr_get */
2151 0, /* tp_descr_set */
2152 0, /* tp_dictoffset */
2153 (initproc
)set_init
, /* tp_init */
2154 PyType_GenericAlloc
, /* tp_alloc */
2155 set_new
, /* tp_new */
2156 PyObject_GC_Del
, /* tp_free */
2159 /* frozenset object ********************************************************/
2162 static PyMethodDef frozenset_methods
[] = {
2163 {"__contains__",(PyCFunction
)set_direct_contains
, METH_O
| METH_COEXIST
,
2165 {"copy", (PyCFunction
)frozenset_copy
, METH_NOARGS
,
2167 {"difference", (PyCFunction
)set_difference_multi
, METH_VARARGS
,
2169 {"intersection",(PyCFunction
)set_intersection_multi
, METH_VARARGS
,
2171 {"isdisjoint", (PyCFunction
)set_isdisjoint
, METH_O
,
2173 {"issubset", (PyCFunction
)set_issubset
, METH_O
,
2175 {"issuperset", (PyCFunction
)set_issuperset
, METH_O
,
2177 {"__reduce__", (PyCFunction
)set_reduce
, METH_NOARGS
,
2179 {"__sizeof__", (PyCFunction
)set_sizeof
, METH_NOARGS
,
2181 {"symmetric_difference",(PyCFunction
)set_symmetric_difference
, METH_O
,
2182 symmetric_difference_doc
},
2183 {"union", (PyCFunction
)set_union
, METH_VARARGS
,
2185 {NULL
, NULL
} /* sentinel */
2188 static PyNumberMethods frozenset_as_number
= {
2190 (binaryfunc
)set_sub
, /*nb_subtract*/
2203 (binaryfunc
)set_and
, /*nb_and*/
2204 (binaryfunc
)set_xor
, /*nb_xor*/
2205 (binaryfunc
)set_or
, /*nb_or*/
2208 PyDoc_STRVAR(frozenset_doc
,
2209 "frozenset() -> empty frozenset object\n\
2210 frozenset(iterable) -> frozenset object\n\
2212 Build an immutable unordered collection of unique elements.");
2214 PyTypeObject PyFrozenSet_Type
= {
2215 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2216 "frozenset", /* tp_name */
2217 sizeof(PySetObject
), /* tp_basicsize */
2218 0, /* tp_itemsize */
2220 (destructor
)set_dealloc
, /* tp_dealloc */
2221 (printfunc
)set_tp_print
, /* tp_print */
2224 set_nocmp
, /* tp_compare */
2225 (reprfunc
)set_repr
, /* tp_repr */
2226 &frozenset_as_number
, /* tp_as_number */
2227 &set_as_sequence
, /* tp_as_sequence */
2228 0, /* tp_as_mapping */
2229 frozenset_hash
, /* tp_hash */
2232 PyObject_GenericGetAttr
, /* tp_getattro */
2233 0, /* tp_setattro */
2234 0, /* tp_as_buffer */
2235 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
| Py_TPFLAGS_CHECKTYPES
|
2236 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2237 frozenset_doc
, /* tp_doc */
2238 (traverseproc
)set_traverse
, /* tp_traverse */
2239 (inquiry
)set_clear_internal
, /* tp_clear */
2240 (richcmpfunc
)set_richcompare
, /* tp_richcompare */
2241 offsetof(PySetObject
, weakreflist
), /* tp_weaklistoffset */
2242 (getiterfunc
)set_iter
, /* tp_iter */
2243 0, /* tp_iternext */
2244 frozenset_methods
, /* tp_methods */
2249 0, /* tp_descr_get */
2250 0, /* tp_descr_set */
2251 0, /* tp_dictoffset */
2253 PyType_GenericAlloc
, /* tp_alloc */
2254 frozenset_new
, /* tp_new */
2255 PyObject_GC_Del
, /* tp_free */
2259 /***** C API functions *************************************************/
2262 PySet_New(PyObject
*iterable
)
2264 return make_new_set(&PySet_Type
, iterable
);
2268 PyFrozenSet_New(PyObject
*iterable
)
2270 return make_new_set(&PyFrozenSet_Type
, iterable
);
2274 PySet_Size(PyObject
*anyset
)
2276 if (!PyAnySet_Check(anyset
)) {
2277 PyErr_BadInternalCall();
2280 return PySet_GET_SIZE(anyset
);
2284 PySet_Clear(PyObject
*set
)
2286 if (!PySet_Check(set
)) {
2287 PyErr_BadInternalCall();
2290 return set_clear_internal((PySetObject
*)set
);
2294 PySet_Contains(PyObject
*anyset
, PyObject
*key
)
2296 if (!PyAnySet_Check(anyset
)) {
2297 PyErr_BadInternalCall();
2300 return set_contains_key((PySetObject
*)anyset
, key
);
2304 PySet_Discard(PyObject
*set
, PyObject
*key
)
2306 if (!PySet_Check(set
)) {
2307 PyErr_BadInternalCall();
2310 return set_discard_key((PySetObject
*)set
, key
);
2314 PySet_Add(PyObject
*anyset
, PyObject
*key
)
2316 if (!PySet_Check(anyset
) &&
2317 (!PyFrozenSet_Check(anyset
) || Py_REFCNT(anyset
) != 1)) {
2318 PyErr_BadInternalCall();
2321 return set_add_key((PySetObject
*)anyset
, key
);
2325 _PySet_Next(PyObject
*set
, Py_ssize_t
*pos
, PyObject
**key
)
2327 setentry
*entry_ptr
;
2329 if (!PyAnySet_Check(set
)) {
2330 PyErr_BadInternalCall();
2333 if (set_next((PySetObject
*)set
, pos
, &entry_ptr
) == 0)
2335 *key
= entry_ptr
->key
;
2340 _PySet_NextEntry(PyObject
*set
, Py_ssize_t
*pos
, PyObject
**key
, long *hash
)
2344 if (!PyAnySet_Check(set
)) {
2345 PyErr_BadInternalCall();
2348 if (set_next((PySetObject
*)set
, pos
, &entry
) == 0)
2351 *hash
= entry
->hash
;
2356 PySet_Pop(PyObject
*set
)
2358 if (!PySet_Check(set
)) {
2359 PyErr_BadInternalCall();
2362 return set_pop((PySetObject
*)set
);
2366 _PySet_Update(PyObject
*set
, PyObject
*iterable
)
2368 if (!PySet_Check(set
)) {
2369 PyErr_BadInternalCall();
2372 return set_update_internal((PySetObject
*)set
, iterable
);
2377 /* Test code to be called with any three element set.
2378 Returns True and original set is restored. */
2380 #define assertRaises(call_return_value, exception) \
2382 assert(call_return_value); \
2383 assert(PyErr_ExceptionMatches(exception)); \
2388 test_c_api(PySetObject
*so
)
2393 PyObject
*elem
=NULL
, *dup
=NULL
, *t
, *f
, *dup2
, *x
;
2394 PyObject
*ob
= (PyObject
*)so
;
2397 /* Verify preconditions */
2398 assert(PyAnySet_Check(ob
));
2399 assert(PyAnySet_CheckExact(ob
));
2400 assert(!PyFrozenSet_CheckExact(ob
));
2402 /* so.clear(); so |= set("abc"); */
2403 str
= PyString_FromString("abc");
2406 set_clear_internal(so
);
2407 if (set_update_internal(so
, str
) == -1) {
2413 /* Exercise type/size checks */
2414 assert(PySet_Size(ob
) == 3);
2415 assert(PySet_GET_SIZE(ob
) == 3);
2417 /* Raise TypeError for non-iterable constructor arguments */
2418 assertRaises(PySet_New(Py_None
) == NULL
, PyExc_TypeError
);
2419 assertRaises(PyFrozenSet_New(Py_None
) == NULL
, PyExc_TypeError
);
2421 /* Raise TypeError for unhashable key */
2422 dup
= PySet_New(ob
);
2423 assertRaises(PySet_Discard(ob
, dup
) == -1, PyExc_TypeError
);
2424 assertRaises(PySet_Contains(ob
, dup
) == -1, PyExc_TypeError
);
2425 assertRaises(PySet_Add(ob
, dup
) == -1, PyExc_TypeError
);
2427 /* Exercise successful pop, contains, add, and discard */
2428 elem
= PySet_Pop(ob
);
2429 assert(PySet_Contains(ob
, elem
) == 0);
2430 assert(PySet_GET_SIZE(ob
) == 2);
2431 assert(PySet_Add(ob
, elem
) == 0);
2432 assert(PySet_Contains(ob
, elem
) == 1);
2433 assert(PySet_GET_SIZE(ob
) == 3);
2434 assert(PySet_Discard(ob
, elem
) == 1);
2435 assert(PySet_GET_SIZE(ob
) == 2);
2436 assert(PySet_Discard(ob
, elem
) == 0);
2437 assert(PySet_GET_SIZE(ob
) == 2);
2439 /* Exercise clear */
2440 dup2
= PySet_New(dup
);
2441 assert(PySet_Clear(dup2
) == 0);
2442 assert(PySet_Size(dup2
) == 0);
2445 /* Raise SystemError on clear or update of frozen set */
2446 f
= PyFrozenSet_New(dup
);
2447 assertRaises(PySet_Clear(f
) == -1, PyExc_SystemError
);
2448 assertRaises(_PySet_Update(f
, dup
) == -1, PyExc_SystemError
);
2449 assert(PySet_Add(f
, elem
) == 0);
2451 assertRaises(PySet_Add(f
, elem
) == -1, PyExc_SystemError
);
2455 /* Exercise direct iteration */
2457 while (_PySet_Next((PyObject
*)dup
, &i
, &x
)) {
2458 s
= PyString_AsString(x
);
2459 assert(s
&& (s
[0] == 'a' || s
[0] == 'b' || s
[0] == 'c'));
2464 /* Exercise updates */
2465 dup2
= PySet_New(NULL
);
2466 assert(_PySet_Update(dup2
, dup
) == 0);
2467 assert(PySet_Size(dup2
) == 3);
2468 assert(_PySet_Update(dup2
, dup
) == 0);
2469 assert(PySet_Size(dup2
) == 3);
2472 /* Raise SystemError when self argument is not a set or frozenset. */
2474 assertRaises(PySet_Size(t
) == -1, PyExc_SystemError
);
2475 assertRaises(PySet_Contains(t
, elem
) == -1, PyExc_SystemError
);
2478 /* Raise SystemError when self argument is not a set. */
2479 f
= PyFrozenSet_New(dup
);
2480 assert(PySet_Size(f
) == 3);
2481 assert(PyFrozenSet_CheckExact(f
));
2482 assertRaises(PySet_Discard(f
, elem
) == -1, PyExc_SystemError
);
2483 assertRaises(PySet_Pop(f
) == NULL
, PyExc_SystemError
);
2486 /* Raise KeyError when popping from an empty set */
2487 assert(PyNumber_InPlaceSubtract(ob
, ob
) == ob
);
2489 assert(PySet_GET_SIZE(ob
) == 0);
2490 assertRaises(PySet_Pop(ob
) == NULL
, PyExc_KeyError
);
2492 /* Restore the set from the copy using the PyNumber API */
2493 assert(PyNumber_InPlaceOr(ob
, dup
) == ob
);
2496 /* Verify constructors accept NULL arguments */
2497 f
= PySet_New(NULL
);
2499 assert(PySet_GET_SIZE(f
) == 0);
2501 f
= PyFrozenSet_New(NULL
);
2503 assert(PyFrozenSet_CheckExact(f
));
2504 assert(PySet_GET_SIZE(f
) == 0);