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-2008 Python Software Foundation.
11 #include "structmember.h"
12 #include "stringlib/eq.h"
14 /* Set a key error with the specified argument, wrapping it in a
15 * tuple automatically so that tuple keys are not unpacked as the
16 * exception arguments. */
18 set_key_error(PyObject
*arg
)
21 tup
= PyTuple_Pack(1, arg
);
23 return; /* caller will expect error to be set anyway */
24 PyErr_SetObject(PyExc_KeyError
, tup
);
28 /* This must be >= 1. */
29 #define PERTURB_SHIFT 5
31 /* Object used as dummy key to fill deleted entries */
32 static PyObject
*dummy
= NULL
; /* Initialized by first call to make_new_set() */
42 #define INIT_NONZERO_SET_SLOTS(so) do { \
43 (so)->table = (so)->smalltable; \
44 (so)->mask = PySet_MINSIZE - 1; \
48 #define EMPTY_TO_MINSIZE(so) do { \
49 memset((so)->smalltable, 0, sizeof((so)->smalltable)); \
50 (so)->used = (so)->fill = 0; \
51 INIT_NONZERO_SET_SLOTS(so); \
54 /* Reuse scheme to save calls to malloc, free, and memset */
55 #ifndef PySet_MAXFREELIST
56 #define PySet_MAXFREELIST 80
58 static PySetObject
*free_list
[PySet_MAXFREELIST
];
59 static int numfree
= 0;
63 The basic lookup function used by all operations.
64 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
65 Open addressing is preferred over chaining since the link overhead for
66 chaining would be substantial (100% with typical malloc overhead).
68 The initial probe index is computed as hash mod the table size. Subsequent
69 probe indices are computed as explained in Objects/dictobject.c.
71 All arithmetic on hash should ignore overflow.
73 Unlike the dictionary implementation, the lookkey functions can return
74 NULL if the rich comparison returns an error.
78 set_lookkey(PySetObject
*so
, PyObject
*key
, register long hash
)
80 register Py_ssize_t i
;
81 register size_t perturb
;
82 register setentry
*freeslot
;
83 register size_t mask
= so
->mask
;
84 setentry
*table
= so
->table
;
85 register setentry
*entry
;
91 if (entry
->key
== NULL
|| entry
->key
== key
)
94 if (entry
->key
== dummy
)
97 if (entry
->hash
== hash
) {
98 startkey
= entry
->key
;
100 cmp
= PyObject_RichCompareBool(startkey
, key
, Py_EQ
);
104 if (table
== so
->table
&& entry
->key
== startkey
) {
109 /* The compare did major nasty stuff to the
112 return set_lookkey(so
, key
, hash
);
118 /* In the loop, key == dummy is by far (factor of 100s) the
119 least likely outcome, so test for that last. */
120 for (perturb
= hash
; ; perturb
>>= PERTURB_SHIFT
) {
121 i
= (i
<< 2) + i
+ perturb
+ 1;
122 entry
= &table
[i
& mask
];
123 if (entry
->key
== NULL
) {
124 if (freeslot
!= NULL
)
128 if (entry
->key
== key
)
130 if (entry
->hash
== hash
&& entry
->key
!= dummy
) {
131 startkey
= entry
->key
;
133 cmp
= PyObject_RichCompareBool(startkey
, key
, Py_EQ
);
137 if (table
== so
->table
&& entry
->key
== startkey
) {
142 /* The compare did major nasty stuff to the
145 return set_lookkey(so
, key
, hash
);
148 else if (entry
->key
== dummy
&& freeslot
== NULL
)
155 * Hacked up version of set_lookkey which can assume keys are always unicode;
156 * This means we can always use unicode_eq directly and not have to check to
157 * see if the comparison altered the table.
160 set_lookkey_unicode(PySetObject
*so
, PyObject
*key
, register long hash
)
162 register Py_ssize_t i
;
163 register size_t perturb
;
164 register setentry
*freeslot
;
165 register size_t mask
= so
->mask
;
166 setentry
*table
= so
->table
;
167 register setentry
*entry
;
169 /* Make sure this function doesn't have to handle non-unicode keys,
170 including subclasses of str; e.g., one reason to subclass
171 strings is to override __eq__, and for speed we don't cater to
173 if (!PyUnicode_CheckExact(key
)) {
174 so
->lookup
= set_lookkey
;
175 return set_lookkey(so
, key
, hash
);
179 if (entry
->key
== NULL
|| entry
->key
== key
)
181 if (entry
->key
== dummy
)
184 if (entry
->hash
== hash
&& unicode_eq(entry
->key
, key
))
189 /* In the loop, key == dummy is by far (factor of 100s) the
190 least likely outcome, so test for that last. */
191 for (perturb
= hash
; ; perturb
>>= PERTURB_SHIFT
) {
192 i
= (i
<< 2) + i
+ perturb
+ 1;
193 entry
= &table
[i
& mask
];
194 if (entry
->key
== NULL
)
195 return freeslot
== NULL
? entry
: freeslot
;
196 if (entry
->key
== key
197 || (entry
->hash
== hash
198 && entry
->key
!= dummy
199 && unicode_eq(entry
->key
, key
)))
201 if (entry
->key
== dummy
&& freeslot
== NULL
)
204 assert(0); /* NOT REACHED */
209 Internal routine to insert a new key into the table.
210 Used by the public insert routine.
211 Eats a reference to key.
214 set_insert_key(register PySetObject
*so
, PyObject
*key
, long hash
)
216 register setentry
*entry
;
217 typedef setentry
*(*lookupfunc
)(PySetObject
*, PyObject
*, long);
219 assert(so
->lookup
!= NULL
);
220 entry
= so
->lookup(so
, key
, hash
);
223 if (entry
->key
== NULL
) {
229 } else if (entry
->key
== dummy
) {
243 Internal routine used by set_table_resize() to insert an item which is
244 known to be absent from the set. This routine also assumes that
245 the set contains no deleted entries. Besides the performance benefit,
246 using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
247 Note that no refcounts are changed by this routine; if needed, the caller
248 is responsible for incref'ing `key`.
251 set_insert_clean(register PySetObject
*so
, PyObject
*key
, long hash
)
254 register size_t perturb
;
255 register size_t mask
= (size_t)so
->mask
;
256 setentry
*table
= so
->table
;
257 register setentry
*entry
;
261 for (perturb
= hash
; entry
->key
!= NULL
; perturb
>>= PERTURB_SHIFT
) {
262 i
= (i
<< 2) + i
+ perturb
+ 1;
263 entry
= &table
[i
& mask
];
272 Restructure the table by allocating a new table and reinserting all
273 keys again. When entries have been deleted, the new table may
274 actually be smaller than the old one.
277 set_table_resize(PySetObject
*so
, Py_ssize_t minused
)
280 setentry
*oldtable
, *newtable
, *entry
;
282 int is_oldtable_malloced
;
283 setentry small_copy
[PySet_MINSIZE
];
285 assert(minused
>= 0);
287 /* Find the smallest table size > minused. */
288 for (newsize
= PySet_MINSIZE
;
289 newsize
<= minused
&& newsize
> 0;
297 /* Get space for a new table. */
298 oldtable
= so
->table
;
299 assert(oldtable
!= NULL
);
300 is_oldtable_malloced
= oldtable
!= so
->smalltable
;
302 if (newsize
== PySet_MINSIZE
) {
303 /* A large table is shrinking, or we can't get any smaller. */
304 newtable
= so
->smalltable
;
305 if (newtable
== oldtable
) {
306 if (so
->fill
== so
->used
) {
307 /* No dummies, so no point doing anything. */
310 /* We're not going to resize it, but rebuild the
311 table anyway to purge old dummy entries.
312 Subtle: This is *necessary* if fill==size,
313 as set_lookkey needs at least one virgin slot to
314 terminate failing searches. If fill < size, it's
315 merely desirable, as dummies slow searches. */
316 assert(so
->fill
> so
->used
);
317 memcpy(small_copy
, oldtable
, sizeof(small_copy
));
318 oldtable
= small_copy
;
322 newtable
= PyMem_NEW(setentry
, newsize
);
323 if (newtable
== NULL
) {
329 /* Make the set empty, using the new table. */
330 assert(newtable
!= oldtable
);
331 so
->table
= newtable
;
332 so
->mask
= newsize
- 1;
333 memset(newtable
, 0, sizeof(setentry
) * newsize
);
338 /* Copy the data over; this is refcount-neutral for active entries;
339 dummy entries aren't copied over, of course */
340 for (entry
= oldtable
; i
> 0; entry
++) {
341 if (entry
->key
== NULL
) {
344 } else if (entry
->key
== dummy
) {
347 assert(entry
->key
== dummy
);
348 Py_DECREF(entry
->key
);
352 set_insert_clean(so
, entry
->key
, entry
->hash
);
356 if (is_oldtable_malloced
)
361 /* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
364 set_add_entry(register PySetObject
*so
, setentry
*entry
)
366 register Py_ssize_t n_used
;
368 assert(so
->fill
<= so
->mask
); /* at least one empty slot */
370 Py_INCREF(entry
->key
);
371 if (set_insert_key(so
, entry
->key
, entry
->hash
) == -1) {
372 Py_DECREF(entry
->key
);
375 if (!(so
->used
> n_used
&& so
->fill
*3 >= (so
->mask
+1)*2))
377 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
381 set_add_key(register PySetObject
*so
, PyObject
*key
)
384 register Py_ssize_t n_used
;
386 if (!PyUnicode_CheckExact(key
) ||
387 (hash
= ((PyUnicodeObject
*) key
)->hash
) == -1) {
388 hash
= PyObject_Hash(key
);
392 assert(so
->fill
<= so
->mask
); /* at least one empty slot */
395 if (set_insert_key(so
, key
, hash
) == -1) {
399 if (!(so
->used
> n_used
&& so
->fill
*3 >= (so
->mask
+1)*2))
401 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
404 #define DISCARD_NOTFOUND 0
405 #define DISCARD_FOUND 1
408 set_discard_entry(PySetObject
*so
, setentry
*oldentry
)
409 { register setentry
*entry
;
412 entry
= (so
->lookup
)(so
, oldentry
->key
, oldentry
->hash
);
415 if (entry
->key
== NULL
|| entry
->key
== dummy
)
416 return DISCARD_NOTFOUND
;
417 old_key
= entry
->key
;
422 return DISCARD_FOUND
;
426 set_discard_key(PySetObject
*so
, PyObject
*key
)
429 register setentry
*entry
;
432 assert (PyAnySet_Check(so
));
434 if (!PyUnicode_CheckExact(key
) ||
435 (hash
= ((PyUnicodeObject
*) key
)->hash
) == -1) {
436 hash
= PyObject_Hash(key
);
440 entry
= (so
->lookup
)(so
, key
, hash
);
443 if (entry
->key
== NULL
|| entry
->key
== dummy
)
444 return DISCARD_NOTFOUND
;
445 old_key
= entry
->key
;
450 return DISCARD_FOUND
;
454 set_clear_internal(PySetObject
*so
)
456 setentry
*entry
, *table
;
457 int table_is_malloced
;
459 setentry small_copy
[PySet_MINSIZE
];
462 assert (PyAnySet_Check(so
));
469 assert(table
!= NULL
);
470 table_is_malloced
= table
!= so
->smalltable
;
472 /* This is delicate. During the process of clearing the set,
473 * decrefs can cause the set to mutate. To avoid fatal confusion
474 * (voice of experience), we have to make the set empty before
475 * clearing the slots, and never refer to anything via so->ref while
479 if (table_is_malloced
)
480 EMPTY_TO_MINSIZE(so
);
483 /* It's a small table with something that needs to be cleared.
484 * Afraid the only safe way is to copy the set entries into
485 * another small table first.
487 memcpy(small_copy
, table
, sizeof(small_copy
));
489 EMPTY_TO_MINSIZE(so
);
491 /* else it's a small table that's already empty */
493 /* Now we can finally clear things. If C had refcounts, we could
494 * assert that the refcount on table is 1 now, i.e. that this function
495 * has unique access to it, so decref side-effects can't alter it.
497 for (entry
= table
; fill
> 0; ++entry
) {
504 Py_DECREF(entry
->key
);
508 assert(entry
->key
== NULL
);
512 if (table_is_malloced
)
518 * Iterate over a set table. Use like so:
522 * pos = 0; # important! pos should not otherwise be changed by you
523 * while (set_next(yourset, &pos, &entry)) {
524 * Refer to borrowed reference in entry->key.
527 * CAUTION: In general, it isn't safe to use set_next in a loop that
531 set_next(PySetObject
*so
, Py_ssize_t
*pos_ptr
, setentry
**entry_ptr
)
535 register setentry
*table
;
537 assert (PyAnySet_Check(so
));
542 while (i
<= mask
&& (table
[i
].key
== NULL
|| table
[i
].key
== dummy
))
547 assert(table
[i
].key
!= NULL
);
548 *entry_ptr
= &table
[i
];
553 set_dealloc(PySetObject
*so
)
555 register setentry
*entry
;
556 Py_ssize_t fill
= so
->fill
;
557 PyObject_GC_UnTrack(so
);
558 Py_TRASHCAN_SAFE_BEGIN(so
)
559 if (so
->weakreflist
!= NULL
)
560 PyObject_ClearWeakRefs((PyObject
*) so
);
562 for (entry
= so
->table
; fill
> 0; entry
++) {
565 Py_DECREF(entry
->key
);
568 if (so
->table
!= so
->smalltable
)
569 PyMem_DEL(so
->table
);
570 if (numfree
< PySet_MAXFREELIST
&& PyAnySet_CheckExact(so
))
571 free_list
[numfree
++] = so
;
573 Py_TYPE(so
)->tp_free(so
);
574 Py_TRASHCAN_SAFE_END(so
)
578 set_repr(PySetObject
*so
)
580 PyObject
*keys
, *result
=NULL
;
582 int status
= Py_ReprEnter((PyObject
*)so
);
589 return PyUnicode_FromFormat("%s(...)", Py_TYPE(so
)->tp_name
);
592 /* shortcut for the empty set */
594 Py_ReprLeave((PyObject
*)so
);
595 return PyUnicode_FromFormat("%s()", Py_TYPE(so
)->tp_name
);
598 keys
= PySequence_List((PyObject
*)so
);
602 listrepr
= PyObject_Repr(keys
);
604 if (listrepr
== NULL
)
606 newsize
= PyUnicode_GET_SIZE(listrepr
);
607 result
= PyUnicode_FromUnicode(NULL
, newsize
);
609 u
= PyUnicode_AS_UNICODE(result
);
611 /* Omit the brackets from the listrepr */
612 Py_UNICODE_COPY(u
, PyUnicode_AS_UNICODE(listrepr
)+1,
613 PyUnicode_GET_SIZE(listrepr
)-2);
618 if (Py_TYPE(so
) != &PySet_Type
) {
619 PyObject
*tmp
= PyUnicode_FromFormat("%s(%U)",
620 Py_TYPE(so
)->tp_name
,
626 Py_ReprLeave((PyObject
*)so
);
631 set_len(PyObject
*so
)
633 return ((PySetObject
*)so
)->used
;
637 set_merge(PySetObject
*so
, PyObject
*otherset
)
640 register Py_ssize_t i
;
641 register setentry
*entry
;
643 assert (PyAnySet_Check(so
));
644 assert (PyAnySet_Check(otherset
));
646 other
= (PySetObject
*)otherset
;
647 if (other
== so
|| other
->used
== 0)
648 /* a.update(a) or a.update({}); nothing to do */
650 /* Do one big resize at the start, rather than
651 * incrementally resizing as we insert new keys. Expect
652 * that there will be no (or few) overlapping keys.
654 if ((so
->fill
+ other
->used
)*3 >= (so
->mask
+1)*2) {
655 if (set_table_resize(so
, (so
->used
+ other
->used
)*2) != 0)
658 for (i
= 0; i
<= other
->mask
; i
++) {
659 entry
= &other
->table
[i
];
660 if (entry
->key
!= NULL
&&
661 entry
->key
!= dummy
) {
662 Py_INCREF(entry
->key
);
663 if (set_insert_key(so
, entry
->key
, entry
->hash
) == -1) {
664 Py_DECREF(entry
->key
);
673 set_contains_key(PySetObject
*so
, PyObject
*key
)
678 if (!PyUnicode_CheckExact(key
) ||
679 (hash
= ((PyUnicodeObject
*) key
)->hash
) == -1) {
680 hash
= PyObject_Hash(key
);
684 entry
= (so
->lookup
)(so
, key
, hash
);
688 return key
!= NULL
&& key
!= dummy
;
692 set_contains_entry(PySetObject
*so
, setentry
*entry
)
697 lu_entry
= (so
->lookup
)(so
, entry
->key
, entry
->hash
);
698 if (lu_entry
== NULL
)
701 return key
!= NULL
&& key
!= dummy
;
705 set_pop(PySetObject
*so
)
707 register Py_ssize_t i
= 0;
708 register setentry
*entry
;
711 assert (PyAnySet_Check(so
));
713 PyErr_SetString(PyExc_KeyError
, "pop from an empty set");
717 /* Set entry to "the first" unused or dummy set entry. We abuse
718 * the hash field of slot 0 to hold a search finger:
719 * If slot 0 has a value, use slot 0.
720 * Else slot 0 is being used to hold a search finger,
721 * and we use its hash value as the first index to look.
723 entry
= &so
->table
[0];
724 if (entry
->key
== NULL
|| entry
->key
== dummy
) {
726 /* The hash field may be a real hash value, or it may be a
727 * legit search finger, or it may be a once-legit search
728 * finger that's out of bounds now because it wrapped around
729 * or the table shrunk -- simply make sure it's in bounds now.
731 if (i
> so
->mask
|| i
< 1)
732 i
= 1; /* skip slot 0 */
733 while ((entry
= &so
->table
[i
])->key
== NULL
|| entry
->key
==dummy
) {
743 so
->table
[0].hash
= i
+ 1; /* next place to start */
747 PyDoc_STRVAR(pop_doc
, "Remove and return an arbitrary set element.\n\
748 Raises KeyError if the set is empty.");
751 set_traverse(PySetObject
*so
, visitproc visit
, void *arg
)
756 while (set_next(so
, &pos
, &entry
))
757 Py_VISIT(entry
->key
);
762 frozenset_hash(PyObject
*self
)
764 PySetObject
*so
= (PySetObject
*)self
;
765 long h
, hash
= 1927868237L;
772 hash
*= PySet_GET_SIZE(self
) + 1;
773 while (set_next(so
, &pos
, &entry
)) {
774 /* Work to increase the bit dispersion for closely spaced hash
775 values. The is important because some use cases have many
776 combinations of a small number of elements with nearby
777 hashes so that many distinct combinations collapse to only
778 a handful of distinct hash values. */
780 hash
^= (h
^ (h
<< 16) ^ 89869747L) * 3644798167u;
782 hash
= hash
* 69069L + 907133923L;
789 /***** Set iterator type ***********************************************/
793 PySetObject
*si_set
; /* Set to NULL when iterator is exhausted */
800 setiter_dealloc(setiterobject
*si
)
802 Py_XDECREF(si
->si_set
);
807 setiter_traverse(setiterobject
*si
, visitproc visit
, void *arg
)
809 Py_VISIT(si
->si_set
);
814 setiter_len(setiterobject
*si
)
817 if (si
->si_set
!= NULL
&& si
->si_used
== si
->si_set
->used
)
819 return PyLong_FromLong(len
);
822 PyDoc_STRVAR(length_hint_doc
, "Private method returning an estimate of len(list(it)).");
824 static PyMethodDef setiter_methods
[] = {
825 {"__length_hint__", (PyCFunction
)setiter_len
, METH_NOARGS
, length_hint_doc
},
826 {NULL
, NULL
} /* sentinel */
829 static PyObject
*setiter_iternext(setiterobject
*si
)
832 register Py_ssize_t i
, mask
;
833 register setentry
*entry
;
834 PySetObject
*so
= si
->si_set
;
838 assert (PyAnySet_Check(so
));
840 if (si
->si_used
!= so
->used
) {
841 PyErr_SetString(PyExc_RuntimeError
,
842 "Set changed size during iteration");
843 si
->si_used
= -1; /* Make this state sticky */
851 while (i
<= mask
&& (entry
[i
].key
== NULL
|| entry
[i
].key
== dummy
))
867 PyTypeObject PySetIter_Type
= {
868 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
869 "set_iterator", /* tp_name */
870 sizeof(setiterobject
), /* tp_basicsize */
873 (destructor
)setiter_dealloc
, /* tp_dealloc */
879 0, /* tp_as_number */
880 0, /* tp_as_sequence */
881 0, /* tp_as_mapping */
885 PyObject_GenericGetAttr
, /* tp_getattro */
887 0, /* tp_as_buffer */
888 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
890 (traverseproc
)setiter_traverse
, /* tp_traverse */
892 0, /* tp_richcompare */
893 0, /* tp_weaklistoffset */
894 PyObject_SelfIter
, /* tp_iter */
895 (iternextfunc
)setiter_iternext
, /* tp_iternext */
896 setiter_methods
, /* tp_methods */
901 set_iter(PySetObject
*so
)
903 setiterobject
*si
= PyObject_GC_New(setiterobject
, &PySetIter_Type
);
908 si
->si_used
= so
->used
;
911 _PyObject_GC_TRACK(si
);
912 return (PyObject
*)si
;
916 set_update_internal(PySetObject
*so
, PyObject
*other
)
920 if (PyAnySet_Check(other
))
921 return set_merge(so
, other
);
923 if (PyDict_CheckExact(other
)) {
927 Py_ssize_t dictsize
= PyDict_Size(other
);
929 /* Do one big resize at the start, rather than
930 * incrementally resizing as we insert new keys. Expect
931 * that there will be no (or few) overlapping keys.
935 if ((so
->fill
+ dictsize
)*3 >= (so
->mask
+1)*2) {
936 if (set_table_resize(so
, (so
->used
+ dictsize
)*2) != 0)
939 while (_PyDict_Next(other
, &pos
, &key
, &value
, &hash
)) {
942 an_entry
.hash
= hash
;
944 if (set_add_entry(so
, &an_entry
) == -1)
950 it
= PyObject_GetIter(other
);
954 while ((key
= PyIter_Next(it
)) != NULL
) {
955 if (set_add_key(so
, key
) == -1) {
963 if (PyErr_Occurred())
969 set_update(PySetObject
*so
, PyObject
*args
)
973 for (i
=0 ; i
<PyTuple_GET_SIZE(args
) ; i
++) {
974 PyObject
*other
= PyTuple_GET_ITEM(args
, i
);
975 if (set_update_internal(so
, other
) == -1)
981 PyDoc_STRVAR(update_doc
,
982 "Update a set with the union of itself and others.");
985 make_new_set(PyTypeObject
*type
, PyObject
*iterable
)
987 register PySetObject
*so
= NULL
;
989 if (dummy
== NULL
) { /* Auto-initialize dummy */
990 dummy
= PyUnicode_FromString("<dummy key>");
995 /* create PySetObject structure */
997 (type
== &PySet_Type
|| type
== &PyFrozenSet_Type
)) {
998 so
= free_list
[--numfree
];
999 assert (so
!= NULL
&& PyAnySet_CheckExact(so
));
1001 _Py_NewReference((PyObject
*)so
);
1002 EMPTY_TO_MINSIZE(so
);
1003 PyObject_GC_Track(so
);
1005 so
= (PySetObject
*)type
->tp_alloc(type
, 0);
1008 /* tp_alloc has already zeroed the structure */
1009 assert(so
->table
== NULL
&& so
->fill
== 0 && so
->used
== 0);
1010 INIT_NONZERO_SET_SLOTS(so
);
1013 so
->lookup
= set_lookkey_unicode
;
1014 so
->weakreflist
= NULL
;
1016 if (iterable
!= NULL
) {
1017 if (set_update_internal(so
, iterable
) == -1) {
1023 return (PyObject
*)so
;
1027 make_new_set_basetype(PyTypeObject
*type
, PyObject
*iterable
)
1029 if (type
!= &PySet_Type
&& type
!= &PyFrozenSet_Type
) {
1030 if (PyType_IsSubtype(type
, &PySet_Type
))
1033 type
= &PyFrozenSet_Type
;
1035 return make_new_set(type
, iterable
);
1038 /* The empty frozenset is a singleton */
1039 static PyObject
*emptyfrozenset
= NULL
;
1042 frozenset_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1044 PyObject
*iterable
= NULL
, *result
;
1046 if (type
== &PyFrozenSet_Type
&& !_PyArg_NoKeywords("frozenset()", kwds
))
1049 if (!PyArg_UnpackTuple(args
, type
->tp_name
, 0, 1, &iterable
))
1052 if (type
!= &PyFrozenSet_Type
)
1053 return make_new_set(type
, iterable
);
1055 if (iterable
!= NULL
) {
1056 /* frozenset(f) is idempotent */
1057 if (PyFrozenSet_CheckExact(iterable
)) {
1058 Py_INCREF(iterable
);
1061 result
= make_new_set(type
, iterable
);
1062 if (result
== NULL
|| PySet_GET_SIZE(result
))
1066 /* The empty frozenset is a singleton */
1067 if (emptyfrozenset
== NULL
)
1068 emptyfrozenset
= make_new_set(type
, NULL
);
1069 Py_XINCREF(emptyfrozenset
);
1070 return emptyfrozenset
;
1080 so
= free_list
[numfree
];
1081 PyObject_GC_Del(so
);
1084 Py_CLEAR(emptyfrozenset
);
1088 set_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1090 if (type
== &PySet_Type
&& !_PyArg_NoKeywords("set()", kwds
))
1093 return make_new_set(type
, NULL
);
1096 /* set_swap_bodies() switches the contents of any two sets by moving their
1097 internal data pointers and, if needed, copying the internal smalltables.
1098 Semantically equivalent to:
1100 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1102 The function always succeeds and it leaves both objects in a stable state.
1103 Useful for creating temporary frozensets from sets for membership testing
1104 in __contains__(), discard(), and remove(). Also useful for operations
1105 that update in-place (by allowing an intermediate result to be swapped
1106 into one of the original inputs).
1110 set_swap_bodies(PySetObject
*a
, PySetObject
*b
)
1114 setentry
*(*f
)(PySetObject
*so
, PyObject
*key
, long hash
);
1115 setentry tab
[PySet_MINSIZE
];
1118 t
= a
->fill
; a
->fill
= b
->fill
; b
->fill
= t
;
1119 t
= a
->used
; a
->used
= b
->used
; b
->used
= t
;
1120 t
= a
->mask
; a
->mask
= b
->mask
; b
->mask
= t
;
1123 if (a
->table
== a
->smalltable
)
1125 a
->table
= b
->table
;
1126 if (b
->table
== b
->smalltable
)
1127 a
->table
= a
->smalltable
;
1130 f
= a
->lookup
; a
->lookup
= b
->lookup
; b
->lookup
= f
;
1132 if (a
->table
== a
->smalltable
|| b
->table
== b
->smalltable
) {
1133 memcpy(tab
, a
->smalltable
, sizeof(tab
));
1134 memcpy(a
->smalltable
, b
->smalltable
, sizeof(tab
));
1135 memcpy(b
->smalltable
, tab
, sizeof(tab
));
1138 if (PyType_IsSubtype(Py_TYPE(a
), &PyFrozenSet_Type
) &&
1139 PyType_IsSubtype(Py_TYPE(b
), &PyFrozenSet_Type
)) {
1140 h
= a
->hash
; a
->hash
= b
->hash
; b
->hash
= h
;
1148 set_copy(PySetObject
*so
)
1150 return make_new_set_basetype(Py_TYPE(so
), (PyObject
*)so
);
1154 frozenset_copy(PySetObject
*so
)
1156 if (PyFrozenSet_CheckExact(so
)) {
1158 return (PyObject
*)so
;
1160 return set_copy(so
);
1163 PyDoc_STRVAR(copy_doc
, "Return a shallow copy of a set.");
1166 set_clear(PySetObject
*so
)
1168 set_clear_internal(so
);
1172 PyDoc_STRVAR(clear_doc
, "Remove all elements from this set.");
1175 set_union(PySetObject
*so
, PyObject
*args
)
1177 PySetObject
*result
;
1181 result
= (PySetObject
*)set_copy(so
);
1185 for (i
=0 ; i
<PyTuple_GET_SIZE(args
) ; i
++) {
1186 other
= PyTuple_GET_ITEM(args
, i
);
1187 if ((PyObject
*)so
== other
)
1189 if (set_update_internal(result
, other
) == -1) {
1194 return (PyObject
*)result
;
1197 PyDoc_STRVAR(union_doc
,
1198 "Return the union of sets as a new set.\n\
1200 (i.e. all elements that are in either set.)");
1203 set_or(PySetObject
*so
, PyObject
*other
)
1205 PySetObject
*result
;
1207 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1208 Py_INCREF(Py_NotImplemented
);
1209 return Py_NotImplemented
;
1212 result
= (PySetObject
*)set_copy(so
);
1215 if ((PyObject
*)so
== other
)
1216 return (PyObject
*)result
;
1217 if (set_update_internal(result
, other
) == -1) {
1221 return (PyObject
*)result
;
1225 set_ior(PySetObject
*so
, PyObject
*other
)
1227 if (!PyAnySet_Check(other
)) {
1228 Py_INCREF(Py_NotImplemented
);
1229 return Py_NotImplemented
;
1231 if (set_update_internal(so
, other
) == -1)
1234 return (PyObject
*)so
;
1238 set_intersection(PySetObject
*so
, PyObject
*other
)
1240 PySetObject
*result
;
1241 PyObject
*key
, *it
, *tmp
;
1243 if ((PyObject
*)so
== other
)
1244 return set_copy(so
);
1246 result
= (PySetObject
*)make_new_set_basetype(Py_TYPE(so
), NULL
);
1250 if (PyAnySet_Check(other
)) {
1254 if (PySet_GET_SIZE(other
) > PySet_GET_SIZE(so
)) {
1255 tmp
= (PyObject
*)so
;
1256 so
= (PySetObject
*)other
;
1260 while (set_next((PySetObject
*)other
, &pos
, &entry
)) {
1261 int rv
= set_contains_entry(so
, entry
);
1267 if (set_add_entry(result
, entry
) == -1) {
1273 return (PyObject
*)result
;
1276 it
= PyObject_GetIter(other
);
1282 while ((key
= PyIter_Next(it
)) != NULL
) {
1285 long hash
= PyObject_Hash(key
);
1295 rv
= set_contains_entry(so
, &entry
);
1303 if (set_add_entry(result
, &entry
) == -1) {
1313 if (PyErr_Occurred()) {
1317 return (PyObject
*)result
;
1321 set_intersection_multi(PySetObject
*so
, PyObject
*args
)
1324 PyObject
*result
= (PyObject
*)so
;
1326 if (PyTuple_GET_SIZE(args
) == 0)
1327 return set_copy(so
);
1330 for (i
=0 ; i
<PyTuple_GET_SIZE(args
) ; i
++) {
1331 PyObject
*other
= PyTuple_GET_ITEM(args
, i
);
1332 PyObject
*newresult
= set_intersection((PySetObject
*)result
, other
);
1333 if (newresult
== NULL
) {
1343 PyDoc_STRVAR(intersection_doc
,
1344 "Return the intersection of two or more sets as a new set.\n\
1346 (i.e. elements that are common to all of the sets.)");
1349 set_intersection_update(PySetObject
*so
, PyObject
*other
)
1353 tmp
= set_intersection(so
, other
);
1356 set_swap_bodies(so
, (PySetObject
*)tmp
);
1362 set_intersection_update_multi(PySetObject
*so
, PyObject
*args
)
1366 tmp
= set_intersection_multi(so
, args
);
1369 set_swap_bodies(so
, (PySetObject
*)tmp
);
1374 PyDoc_STRVAR(intersection_update_doc
,
1375 "Update a set with the intersection of itself and another.");
1378 set_and(PySetObject
*so
, PyObject
*other
)
1380 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1381 Py_INCREF(Py_NotImplemented
);
1382 return Py_NotImplemented
;
1384 return set_intersection(so
, other
);
1388 set_iand(PySetObject
*so
, PyObject
*other
)
1392 if (!PyAnySet_Check(other
)) {
1393 Py_INCREF(Py_NotImplemented
);
1394 return Py_NotImplemented
;
1396 result
= set_intersection_update(so
, other
);
1401 return (PyObject
*)so
;
1405 set_isdisjoint(PySetObject
*so
, PyObject
*other
)
1407 PyObject
*key
, *it
, *tmp
;
1409 if ((PyObject
*)so
== other
) {
1410 if (PySet_GET_SIZE(so
) == 0)
1416 if (PyAnySet_CheckExact(other
)) {
1420 if (PySet_GET_SIZE(other
) > PySet_GET_SIZE(so
)) {
1421 tmp
= (PyObject
*)so
;
1422 so
= (PySetObject
*)other
;
1425 while (set_next((PySetObject
*)other
, &pos
, &entry
)) {
1426 int rv
= set_contains_entry(so
, entry
);
1435 it
= PyObject_GetIter(other
);
1439 while ((key
= PyIter_Next(it
)) != NULL
) {
1442 long hash
= PyObject_Hash(key
);;
1451 rv
= set_contains_entry(so
, &entry
);
1463 if (PyErr_Occurred())
1468 PyDoc_STRVAR(isdisjoint_doc
,
1469 "Return True if two sets have a null intersection.");
1472 set_difference_update_internal(PySetObject
*so
, PyObject
*other
)
1474 if ((PyObject
*)so
== other
)
1475 return set_clear_internal(so
);
1477 if (PyAnySet_Check(other
)) {
1481 while (set_next((PySetObject
*)other
, &pos
, &entry
))
1482 if (set_discard_entry(so
, entry
) == -1)
1486 it
= PyObject_GetIter(other
);
1490 while ((key
= PyIter_Next(it
)) != NULL
) {
1491 if (set_discard_key(so
, key
) == -1) {
1499 if (PyErr_Occurred())
1502 /* If more than 1/5 are dummies, then resize them away. */
1503 if ((so
->fill
- so
->used
) * 5 < so
->mask
)
1505 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
1509 set_difference_update(PySetObject
*so
, PyObject
*args
)
1513 for (i
=0 ; i
<PyTuple_GET_SIZE(args
) ; i
++) {
1514 PyObject
*other
= PyTuple_GET_ITEM(args
, i
);
1515 if (set_difference_update_internal(so
, other
) == -1)
1521 PyDoc_STRVAR(difference_update_doc
,
1522 "Remove all elements of another set from this set.");
1525 set_difference(PySetObject
*so
, PyObject
*other
)
1531 if (!PyAnySet_Check(other
) && !PyDict_CheckExact(other
)) {
1532 result
= set_copy(so
);
1535 if (set_difference_update_internal((PySetObject
*)result
, other
) != -1)
1541 result
= make_new_set_basetype(Py_TYPE(so
), NULL
);
1545 if (PyDict_CheckExact(other
)) {
1546 while (set_next(so
, &pos
, &entry
)) {
1548 entrycopy
.hash
= entry
->hash
;
1549 entrycopy
.key
= entry
->key
;
1550 if (!_PyDict_Contains(other
, entry
->key
, entry
->hash
)) {
1551 if (set_add_entry((PySetObject
*)result
, &entrycopy
) == -1) {
1560 while (set_next(so
, &pos
, &entry
)) {
1561 int rv
= set_contains_entry((PySetObject
*)other
, entry
);
1567 if (set_add_entry((PySetObject
*)result
, entry
) == -1) {
1577 set_difference_multi(PySetObject
*so
, PyObject
*args
)
1580 PyObject
*result
, *other
;
1582 if (PyTuple_GET_SIZE(args
) == 0)
1583 return set_copy(so
);
1585 other
= PyTuple_GET_ITEM(args
, 0);
1586 result
= set_difference(so
, other
);
1590 for (i
=1 ; i
<PyTuple_GET_SIZE(args
) ; i
++) {
1591 other
= PyTuple_GET_ITEM(args
, i
);
1592 if (set_difference_update_internal((PySetObject
*)result
, other
) == -1) {
1600 PyDoc_STRVAR(difference_doc
,
1601 "Return the difference of two or more sets as a new set.\n\
1603 (i.e. all elements that are in this set but not the others.)");
1605 set_sub(PySetObject
*so
, PyObject
*other
)
1607 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1608 Py_INCREF(Py_NotImplemented
);
1609 return Py_NotImplemented
;
1611 return set_difference(so
, other
);
1615 set_isub(PySetObject
*so
, PyObject
*other
)
1617 if (!PyAnySet_Check(other
)) {
1618 Py_INCREF(Py_NotImplemented
);
1619 return Py_NotImplemented
;
1621 if (set_difference_update_internal(so
, other
) == -1)
1624 return (PyObject
*)so
;
1628 set_symmetric_difference_update(PySetObject
*so
, PyObject
*other
)
1630 PySetObject
*otherset
;
1635 if ((PyObject
*)so
== other
)
1636 return set_clear(so
);
1638 if (PyDict_CheckExact(other
)) {
1642 while (_PyDict_Next(other
, &pos
, &key
, &value
, &hash
)) {
1645 an_entry
.hash
= hash
;
1647 rv
= set_discard_entry(so
, &an_entry
);
1650 if (rv
== DISCARD_NOTFOUND
) {
1651 if (set_add_entry(so
, &an_entry
) == -1)
1658 if (PyAnySet_Check(other
)) {
1660 otherset
= (PySetObject
*)other
;
1662 otherset
= (PySetObject
*)make_new_set_basetype(Py_TYPE(so
), other
);
1663 if (otherset
== NULL
)
1667 while (set_next(otherset
, &pos
, &entry
)) {
1668 int rv
= set_discard_entry(so
, entry
);
1670 Py_DECREF(otherset
);
1673 if (rv
== DISCARD_NOTFOUND
) {
1674 if (set_add_entry(so
, entry
) == -1) {
1675 Py_DECREF(otherset
);
1680 Py_DECREF(otherset
);
1684 PyDoc_STRVAR(symmetric_difference_update_doc
,
1685 "Update a set with the symmetric difference of itself and another.");
1688 set_symmetric_difference(PySetObject
*so
, PyObject
*other
)
1691 PySetObject
*otherset
;
1693 otherset
= (PySetObject
*)make_new_set_basetype(Py_TYPE(so
), other
);
1694 if (otherset
== NULL
)
1696 rv
= set_symmetric_difference_update(otherset
, (PyObject
*)so
);
1700 return (PyObject
*)otherset
;
1703 PyDoc_STRVAR(symmetric_difference_doc
,
1704 "Return the symmetric difference of two sets as a new set.\n\
1706 (i.e. all elements that are in exactly one of the sets.)");
1709 set_xor(PySetObject
*so
, PyObject
*other
)
1711 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1712 Py_INCREF(Py_NotImplemented
);
1713 return Py_NotImplemented
;
1715 return set_symmetric_difference(so
, other
);
1719 set_ixor(PySetObject
*so
, PyObject
*other
)
1723 if (!PyAnySet_Check(other
)) {
1724 Py_INCREF(Py_NotImplemented
);
1725 return Py_NotImplemented
;
1727 result
= set_symmetric_difference_update(so
, other
);
1732 return (PyObject
*)so
;
1736 set_issubset(PySetObject
*so
, PyObject
*other
)
1741 if (!PyAnySet_Check(other
)) {
1742 PyObject
*tmp
, *result
;
1743 tmp
= make_new_set(&PySet_Type
, other
);
1746 result
= set_issubset(so
, tmp
);
1750 if (PySet_GET_SIZE(so
) > PySet_GET_SIZE(other
))
1753 while (set_next(so
, &pos
, &entry
)) {
1754 int rv
= set_contains_entry((PySetObject
*)other
, entry
);
1763 PyDoc_STRVAR(issubset_doc
, "Report whether another set contains this set.");
1766 set_issuperset(PySetObject
*so
, PyObject
*other
)
1768 PyObject
*tmp
, *result
;
1770 if (!PyAnySet_Check(other
)) {
1771 tmp
= make_new_set(&PySet_Type
, other
);
1774 result
= set_issuperset(so
, tmp
);
1778 return set_issubset((PySetObject
*)other
, (PyObject
*)so
);
1781 PyDoc_STRVAR(issuperset_doc
, "Report whether this set contains another set.");
1784 set_richcompare(PySetObject
*v
, PyObject
*w
, int op
)
1788 if(!PyAnySet_Check(w
)) {
1789 Py_INCREF(Py_NotImplemented
);
1790 return Py_NotImplemented
;
1794 if (PySet_GET_SIZE(v
) != PySet_GET_SIZE(w
))
1796 if (v
->hash
!= -1 &&
1797 ((PySetObject
*)w
)->hash
!= -1 &&
1798 v
->hash
!= ((PySetObject
*)w
)->hash
)
1800 return set_issubset(v
, w
);
1802 r1
= set_richcompare(v
, w
, Py_EQ
);
1805 r2
= PyBool_FromLong(PyObject_Not(r1
));
1809 return set_issubset(v
, w
);
1811 return set_issuperset(v
, w
);
1813 if (PySet_GET_SIZE(v
) >= PySet_GET_SIZE(w
))
1815 return set_issubset(v
, w
);
1817 if (PySet_GET_SIZE(v
) <= PySet_GET_SIZE(w
))
1819 return set_issuperset(v
, w
);
1821 Py_INCREF(Py_NotImplemented
);
1822 return Py_NotImplemented
;
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
, key
);
1852 rv
= set_contains(so
, tmpkey
);
1859 set_direct_contains(PySetObject
*so
, PyObject
*key
)
1863 result
= set_contains(so
, key
);
1866 return PyBool_FromLong(result
);
1869 PyDoc_STRVAR(contains_doc
, "x.__contains__(y) <==> y in x.");
1872 set_remove(PySetObject
*so
, PyObject
*key
)
1877 rv
= set_discard_key(so
, key
);
1879 if (!PySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1882 tmpkey
= make_new_set(&PyFrozenSet_Type
, key
);
1885 rv
= set_discard_key(so
, tmpkey
);
1891 if (rv
== DISCARD_NOTFOUND
) {
1898 PyDoc_STRVAR(remove_doc
,
1899 "Remove an element from a set; it must be a member.\n\
1901 If the element is not a member, raise a KeyError.");
1904 set_discard(PySetObject
*so
, PyObject
*key
)
1906 PyObject
*tmpkey
, *result
;
1909 rv
= set_discard_key(so
, key
);
1911 if (!PySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1914 tmpkey
= make_new_set(&PyFrozenSet_Type
, key
);
1917 result
= set_discard(so
, tmpkey
);
1924 PyDoc_STRVAR(discard_doc
,
1925 "Remove an element from a set if it is a member.\n\
1927 If the element is not a member, do nothing.");
1930 set_reduce(PySetObject
*so
)
1932 PyObject
*keys
=NULL
, *args
=NULL
, *result
=NULL
, *dict
=NULL
;
1934 keys
= PySequence_List((PyObject
*)so
);
1937 args
= PyTuple_Pack(1, keys
);
1940 dict
= PyObject_GetAttrString((PyObject
*)so
, "__dict__");
1946 result
= PyTuple_Pack(3, Py_TYPE(so
), args
, dict
);
1954 PyDoc_STRVAR(reduce_doc
, "Return state information for pickling.");
1957 set_sizeof(PySetObject
*so
)
1961 res
= sizeof(PySetObject
);
1962 if (so
->table
!= so
->smalltable
)
1963 res
= res
+ (so
->mask
+ 1) * sizeof(setentry
);
1964 return PyLong_FromSsize_t(res
);
1967 PyDoc_STRVAR(sizeof_doc
, "S.__sizeof__() -> size of S in memory, in bytes");
1969 set_init(PySetObject
*self
, PyObject
*args
, PyObject
*kwds
)
1971 PyObject
*iterable
= NULL
;
1973 if (!PyAnySet_Check(self
))
1975 if (PySet_Check(self
) && !_PyArg_NoKeywords("set()", kwds
))
1977 if (!PyArg_UnpackTuple(args
, Py_TYPE(self
)->tp_name
, 0, 1, &iterable
))
1979 set_clear_internal(self
);
1981 if (iterable
== NULL
)
1983 return set_update_internal(self
, iterable
);
1986 static PySequenceMethods set_as_sequence
= {
1987 set_len
, /* sq_length */
1992 0, /* sq_ass_item */
1993 0, /* sq_ass_slice */
1994 (objobjproc
)set_contains
, /* sq_contains */
1997 /* set object ********************************************************/
2000 static PyObject
*test_c_api(PySetObject
*so
);
2002 PyDoc_STRVAR(test_c_api_doc
, "Exercises C API. Returns True.\n\
2003 All is well if assertions don't fail.");
2006 static PyMethodDef set_methods
[] = {
2007 {"add", (PyCFunction
)set_add
, METH_O
,
2009 {"clear", (PyCFunction
)set_clear
, METH_NOARGS
,
2011 {"__contains__",(PyCFunction
)set_direct_contains
, METH_O
| METH_COEXIST
,
2013 {"copy", (PyCFunction
)set_copy
, METH_NOARGS
,
2015 {"discard", (PyCFunction
)set_discard
, METH_O
,
2017 {"difference", (PyCFunction
)set_difference_multi
, METH_VARARGS
,
2019 {"difference_update", (PyCFunction
)set_difference_update
, METH_VARARGS
,
2020 difference_update_doc
},
2021 {"intersection",(PyCFunction
)set_intersection_multi
, METH_VARARGS
,
2023 {"intersection_update",(PyCFunction
)set_intersection_update_multi
, METH_VARARGS
,
2024 intersection_update_doc
},
2025 {"isdisjoint", (PyCFunction
)set_isdisjoint
, METH_O
,
2027 {"issubset", (PyCFunction
)set_issubset
, METH_O
,
2029 {"issuperset", (PyCFunction
)set_issuperset
, METH_O
,
2031 {"pop", (PyCFunction
)set_pop
, METH_NOARGS
,
2033 {"__reduce__", (PyCFunction
)set_reduce
, METH_NOARGS
,
2035 {"remove", (PyCFunction
)set_remove
, METH_O
,
2037 {"__sizeof__", (PyCFunction
)set_sizeof
, METH_NOARGS
,
2039 {"symmetric_difference",(PyCFunction
)set_symmetric_difference
, METH_O
,
2040 symmetric_difference_doc
},
2041 {"symmetric_difference_update",(PyCFunction
)set_symmetric_difference_update
, METH_O
,
2042 symmetric_difference_update_doc
},
2044 {"test_c_api", (PyCFunction
)test_c_api
, METH_NOARGS
,
2047 {"union", (PyCFunction
)set_union
, METH_VARARGS
,
2049 {"update", (PyCFunction
)set_update
, METH_VARARGS
,
2051 {NULL
, NULL
} /* sentinel */
2054 static PyNumberMethods set_as_number
= {
2056 (binaryfunc
)set_sub
, /*nb_subtract*/
2068 (binaryfunc
)set_and
, /*nb_and*/
2069 (binaryfunc
)set_xor
, /*nb_xor*/
2070 (binaryfunc
)set_or
, /*nb_or*/
2074 0, /*nb_inplace_add*/
2075 (binaryfunc
)set_isub
, /*nb_inplace_subtract*/
2076 0, /*nb_inplace_multiply*/
2077 0, /*nb_inplace_remainder*/
2078 0, /*nb_inplace_power*/
2079 0, /*nb_inplace_lshift*/
2080 0, /*nb_inplace_rshift*/
2081 (binaryfunc
)set_iand
, /*nb_inplace_and*/
2082 (binaryfunc
)set_ixor
, /*nb_inplace_xor*/
2083 (binaryfunc
)set_ior
, /*nb_inplace_or*/
2086 PyDoc_STRVAR(set_doc
,
2087 "set() -> new empty set object\n\
2088 set(iterable) -> new set object\n\
2090 Build an unordered collection of unique elements.");
2092 PyTypeObject PySet_Type
= {
2093 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2094 "set", /* tp_name */
2095 sizeof(PySetObject
), /* tp_basicsize */
2096 0, /* tp_itemsize */
2098 (destructor
)set_dealloc
, /* tp_dealloc */
2102 0, /* tp_reserved */
2103 (reprfunc
)set_repr
, /* tp_repr */
2104 &set_as_number
, /* tp_as_number */
2105 &set_as_sequence
, /* tp_as_sequence */
2106 0, /* tp_as_mapping */
2107 (hashfunc
)PyObject_HashNotImplemented
, /* tp_hash */
2110 PyObject_GenericGetAttr
, /* tp_getattro */
2111 0, /* tp_setattro */
2112 0, /* tp_as_buffer */
2113 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2114 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2115 set_doc
, /* tp_doc */
2116 (traverseproc
)set_traverse
, /* tp_traverse */
2117 (inquiry
)set_clear_internal
, /* tp_clear */
2118 (richcmpfunc
)set_richcompare
, /* tp_richcompare */
2119 offsetof(PySetObject
, weakreflist
), /* tp_weaklistoffset */
2120 (getiterfunc
)set_iter
, /* tp_iter */
2121 0, /* tp_iternext */
2122 set_methods
, /* tp_methods */
2127 0, /* tp_descr_get */
2128 0, /* tp_descr_set */
2129 0, /* tp_dictoffset */
2130 (initproc
)set_init
, /* tp_init */
2131 PyType_GenericAlloc
, /* tp_alloc */
2132 set_new
, /* tp_new */
2133 PyObject_GC_Del
, /* tp_free */
2136 /* frozenset object ********************************************************/
2139 static PyMethodDef frozenset_methods
[] = {
2140 {"__contains__",(PyCFunction
)set_direct_contains
, METH_O
| METH_COEXIST
,
2142 {"copy", (PyCFunction
)frozenset_copy
, METH_NOARGS
,
2144 {"difference", (PyCFunction
)set_difference_multi
, METH_VARARGS
,
2146 {"intersection",(PyCFunction
)set_intersection_multi
, METH_VARARGS
,
2148 {"isdisjoint", (PyCFunction
)set_isdisjoint
, METH_O
,
2150 {"issubset", (PyCFunction
)set_issubset
, METH_O
,
2152 {"issuperset", (PyCFunction
)set_issuperset
, METH_O
,
2154 {"__reduce__", (PyCFunction
)set_reduce
, METH_NOARGS
,
2156 {"__sizeof__", (PyCFunction
)set_sizeof
, METH_NOARGS
,
2158 {"symmetric_difference",(PyCFunction
)set_symmetric_difference
, METH_O
,
2159 symmetric_difference_doc
},
2160 {"union", (PyCFunction
)set_union
, METH_VARARGS
,
2162 {NULL
, NULL
} /* sentinel */
2165 static PyNumberMethods frozenset_as_number
= {
2167 (binaryfunc
)set_sub
, /*nb_subtract*/
2179 (binaryfunc
)set_and
, /*nb_and*/
2180 (binaryfunc
)set_xor
, /*nb_xor*/
2181 (binaryfunc
)set_or
, /*nb_or*/
2184 PyDoc_STRVAR(frozenset_doc
,
2185 "frozenset() -> empty frozenset object\n\
2186 frozenset(iterable) -> frozenset object\n\
2188 Build an immutable unordered collection of unique elements.");
2190 PyTypeObject PyFrozenSet_Type
= {
2191 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2192 "frozenset", /* tp_name */
2193 sizeof(PySetObject
), /* tp_basicsize */
2194 0, /* tp_itemsize */
2196 (destructor
)set_dealloc
, /* tp_dealloc */
2200 0, /* tp_reserved */
2201 (reprfunc
)set_repr
, /* tp_repr */
2202 &frozenset_as_number
, /* tp_as_number */
2203 &set_as_sequence
, /* tp_as_sequence */
2204 0, /* tp_as_mapping */
2205 frozenset_hash
, /* tp_hash */
2208 PyObject_GenericGetAttr
, /* tp_getattro */
2209 0, /* tp_setattro */
2210 0, /* tp_as_buffer */
2211 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2212 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2213 frozenset_doc
, /* tp_doc */
2214 (traverseproc
)set_traverse
, /* tp_traverse */
2215 (inquiry
)set_clear_internal
, /* tp_clear */
2216 (richcmpfunc
)set_richcompare
, /* tp_richcompare */
2217 offsetof(PySetObject
, weakreflist
), /* tp_weaklistoffset */
2218 (getiterfunc
)set_iter
, /* tp_iter */
2219 0, /* tp_iternext */
2220 frozenset_methods
, /* tp_methods */
2225 0, /* tp_descr_get */
2226 0, /* tp_descr_set */
2227 0, /* tp_dictoffset */
2229 PyType_GenericAlloc
, /* tp_alloc */
2230 frozenset_new
, /* tp_new */
2231 PyObject_GC_Del
, /* tp_free */
2235 /***** C API functions *************************************************/
2238 PySet_New(PyObject
*iterable
)
2240 return make_new_set(&PySet_Type
, iterable
);
2244 PyFrozenSet_New(PyObject
*iterable
)
2246 return make_new_set(&PyFrozenSet_Type
, iterable
);
2250 PySet_Size(PyObject
*anyset
)
2252 if (!PyAnySet_Check(anyset
)) {
2253 PyErr_BadInternalCall();
2256 return PySet_GET_SIZE(anyset
);
2260 PySet_Clear(PyObject
*set
)
2262 if (!PySet_Check(set
)) {
2263 PyErr_BadInternalCall();
2266 return set_clear_internal((PySetObject
*)set
);
2270 PySet_Contains(PyObject
*anyset
, PyObject
*key
)
2272 if (!PyAnySet_Check(anyset
)) {
2273 PyErr_BadInternalCall();
2276 return set_contains_key((PySetObject
*)anyset
, key
);
2280 PySet_Discard(PyObject
*set
, PyObject
*key
)
2282 if (!PySet_Check(set
)) {
2283 PyErr_BadInternalCall();
2286 return set_discard_key((PySetObject
*)set
, key
);
2290 PySet_Add(PyObject
*anyset
, PyObject
*key
)
2292 if (!PySet_Check(anyset
) &&
2293 (!PyFrozenSet_Check(anyset
) || Py_REFCNT(anyset
) != 1)) {
2294 PyErr_BadInternalCall();
2297 return set_add_key((PySetObject
*)anyset
, key
);
2301 _PySet_NextEntry(PyObject
*set
, Py_ssize_t
*pos
, PyObject
**key
, long *hash
)
2305 if (!PyAnySet_Check(set
)) {
2306 PyErr_BadInternalCall();
2309 if (set_next((PySetObject
*)set
, pos
, &entry
) == 0)
2312 *hash
= entry
->hash
;
2317 PySet_Pop(PyObject
*set
)
2319 if (!PySet_Check(set
)) {
2320 PyErr_BadInternalCall();
2323 return set_pop((PySetObject
*)set
);
2327 _PySet_Update(PyObject
*set
, PyObject
*iterable
)
2329 if (!PySet_Check(set
)) {
2330 PyErr_BadInternalCall();
2333 return set_update_internal((PySetObject
*)set
, iterable
);
2338 /* Test code to be called with any three element set.
2339 Returns True and original set is restored. */
2341 #define assertRaises(call_return_value, exception) \
2343 assert(call_return_value); \
2344 assert(PyErr_ExceptionMatches(exception)); \
2349 test_c_api(PySetObject
*so
)
2354 PyObject
*elem
=NULL
, *dup
=NULL
, *t
, *f
, *dup2
, *x
;
2355 PyObject
*ob
= (PyObject
*)so
;
2358 /* Verify preconditions and exercise type/size checks */
2359 assert(PyAnySet_Check(ob
));
2360 assert(PyAnySet_CheckExact(ob
));
2361 assert(!PyFrozenSet_CheckExact(ob
));
2362 assert(PySet_Size(ob
) == 3);
2363 assert(PySet_GET_SIZE(ob
) == 3);
2365 /* Raise TypeError for non-iterable constructor arguments */
2366 assertRaises(PySet_New(Py_None
) == NULL
, PyExc_TypeError
);
2367 assertRaises(PyFrozenSet_New(Py_None
) == NULL
, PyExc_TypeError
);
2369 /* Raise TypeError for unhashable key */
2370 dup
= PySet_New(ob
);
2371 assertRaises(PySet_Discard(ob
, dup
) == -1, PyExc_TypeError
);
2372 assertRaises(PySet_Contains(ob
, dup
) == -1, PyExc_TypeError
);
2373 assertRaises(PySet_Add(ob
, dup
) == -1, PyExc_TypeError
);
2375 /* Exercise successful pop, contains, add, and discard */
2376 elem
= PySet_Pop(ob
);
2377 assert(PySet_Contains(ob
, elem
) == 0);
2378 assert(PySet_GET_SIZE(ob
) == 2);
2379 assert(PySet_Add(ob
, elem
) == 0);
2380 assert(PySet_Contains(ob
, elem
) == 1);
2381 assert(PySet_GET_SIZE(ob
) == 3);
2382 assert(PySet_Discard(ob
, elem
) == 1);
2383 assert(PySet_GET_SIZE(ob
) == 2);
2384 assert(PySet_Discard(ob
, elem
) == 0);
2385 assert(PySet_GET_SIZE(ob
) == 2);
2387 /* Exercise clear */
2388 dup2
= PySet_New(dup
);
2389 assert(PySet_Clear(dup2
) == 0);
2390 assert(PySet_Size(dup2
) == 0);
2393 /* Raise SystemError on clear or update of frozen set */
2394 f
= PyFrozenSet_New(dup
);
2395 assertRaises(PySet_Clear(f
) == -1, PyExc_SystemError
);
2396 assertRaises(_PySet_Update(f
, dup
) == -1, PyExc_SystemError
);
2397 assert(PySet_Add(f
, elem
) == 0);
2399 assertRaises(PySet_Add(f
, elem
) == -1, PyExc_SystemError
);
2403 /* Exercise direct iteration */
2405 while (_PySet_NextEntry((PyObject
*)dup
, &i
, &x
, &hash
)) {
2406 s
= _PyUnicode_AsString(x
);
2407 assert(s
&& (s
[0] == 'a' || s
[0] == 'b' || s
[0] == 'c'));
2412 /* Exercise updates */
2413 dup2
= PySet_New(NULL
);
2414 assert(_PySet_Update(dup2
, dup
) == 0);
2415 assert(PySet_Size(dup2
) == 3);
2416 assert(_PySet_Update(dup2
, dup
) == 0);
2417 assert(PySet_Size(dup2
) == 3);
2420 /* Raise SystemError when self argument is not a set or frozenset. */
2422 assertRaises(PySet_Size(t
) == -1, PyExc_SystemError
);
2423 assertRaises(PySet_Contains(t
, elem
) == -1, PyExc_SystemError
);
2426 /* Raise SystemError when self argument is not a set. */
2427 f
= PyFrozenSet_New(dup
);
2428 assert(PySet_Size(f
) == 3);
2429 assert(PyFrozenSet_CheckExact(f
));
2430 assertRaises(PySet_Discard(f
, elem
) == -1, PyExc_SystemError
);
2431 assertRaises(PySet_Pop(f
) == NULL
, PyExc_SystemError
);
2434 /* Raise KeyError when popping from an empty set */
2435 assert(PyNumber_InPlaceSubtract(ob
, ob
) == ob
);
2437 assert(PySet_GET_SIZE(ob
) == 0);
2438 assertRaises(PySet_Pop(ob
) == NULL
, PyExc_KeyError
);
2440 /* Restore the set from the copy using the PyNumber API */
2441 assert(PyNumber_InPlaceOr(ob
, dup
) == ob
);
2444 /* Verify constructors accept NULL arguments */
2445 f
= PySet_New(NULL
);
2447 assert(PySet_GET_SIZE(f
) == 0);
2449 f
= PyFrozenSet_New(NULL
);
2451 assert(PyFrozenSet_CheckExact(f
));
2452 assert(PySet_GET_SIZE(f
) == 0);