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
;
97 cmp
= PyObject_RichCompareBool(startkey
, key
, Py_EQ
);
100 if (table
== so
->table
&& entry
->key
== startkey
) {
105 /* The compare did major nasty stuff to the
108 return set_lookkey(so
, key
, hash
);
114 /* In the loop, key == dummy is by far (factor of 100s) the
115 least likely outcome, so test for that last. */
116 for (perturb
= hash
; ; perturb
>>= PERTURB_SHIFT
) {
117 i
= (i
<< 2) + i
+ perturb
+ 1;
118 entry
= &table
[i
& mask
];
119 if (entry
->key
== NULL
) {
120 if (freeslot
!= NULL
)
124 if (entry
->key
== key
)
126 if (entry
->hash
== hash
&& entry
->key
!= dummy
) {
127 startkey
= entry
->key
;
128 cmp
= PyObject_RichCompareBool(startkey
, key
, Py_EQ
);
131 if (table
== so
->table
&& entry
->key
== startkey
) {
136 /* The compare did major nasty stuff to the
139 return set_lookkey(so
, key
, hash
);
142 else if (entry
->key
== dummy
&& freeslot
== NULL
)
149 * Hacked up version of set_lookkey which can assume keys are always strings;
150 * This means we can always use _PyString_Eq directly and not have to check to
151 * see if the comparison altered the table.
154 set_lookkey_string(PySetObject
*so
, PyObject
*key
, register long hash
)
156 register Py_ssize_t i
;
157 register size_t perturb
;
158 register setentry
*freeslot
;
159 register size_t mask
= so
->mask
;
160 setentry
*table
= so
->table
;
161 register setentry
*entry
;
163 /* Make sure this function doesn't have to handle non-string keys,
164 including subclasses of str; e.g., one reason to subclass
165 strings is to override __eq__, and for speed we don't cater to
167 if (!PyString_CheckExact(key
)) {
168 so
->lookup
= set_lookkey
;
169 return set_lookkey(so
, key
, hash
);
173 if (entry
->key
== NULL
|| entry
->key
== key
)
175 if (entry
->key
== dummy
)
178 if (entry
->hash
== hash
&& _PyString_Eq(entry
->key
, key
))
183 /* In the loop, key == dummy is by far (factor of 100s) the
184 least likely outcome, so test for that last. */
185 for (perturb
= hash
; ; perturb
>>= PERTURB_SHIFT
) {
186 i
= (i
<< 2) + i
+ perturb
+ 1;
187 entry
= &table
[i
& mask
];
188 if (entry
->key
== NULL
)
189 return freeslot
== NULL
? entry
: freeslot
;
190 if (entry
->key
== key
191 || (entry
->hash
== hash
192 && entry
->key
!= dummy
193 && _PyString_Eq(entry
->key
, key
)))
195 if (entry
->key
== dummy
&& freeslot
== NULL
)
198 assert(0); /* NOT REACHED */
203 Internal routine to insert a new key into the table.
204 Used by the public insert routine.
205 Eats a reference to key.
208 set_insert_key(register PySetObject
*so
, PyObject
*key
, long hash
)
210 register setentry
*entry
;
211 typedef setentry
*(*lookupfunc
)(PySetObject
*, PyObject
*, long);
213 assert(so
->lookup
!= NULL
);
214 entry
= so
->lookup(so
, key
, hash
);
217 if (entry
->key
== NULL
) {
223 } else if (entry
->key
== dummy
) {
237 Internal routine used by set_table_resize() to insert an item which is
238 known to be absent from the set. This routine also assumes that
239 the set contains no deleted entries. Besides the performance benefit,
240 using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
241 Note that no refcounts are changed by this routine; if needed, the caller
242 is responsible for incref'ing `key`.
245 set_insert_clean(register PySetObject
*so
, PyObject
*key
, long hash
)
248 register size_t perturb
;
249 register size_t mask
= (size_t)so
->mask
;
250 setentry
*table
= so
->table
;
251 register setentry
*entry
;
255 for (perturb
= hash
; entry
->key
!= NULL
; perturb
>>= PERTURB_SHIFT
) {
256 i
= (i
<< 2) + i
+ perturb
+ 1;
257 entry
= &table
[i
& mask
];
266 Restructure the table by allocating a new table and reinserting all
267 keys again. When entries have been deleted, the new table may
268 actually be smaller than the old one.
271 set_table_resize(PySetObject
*so
, Py_ssize_t minused
)
274 setentry
*oldtable
, *newtable
, *entry
;
276 int is_oldtable_malloced
;
277 setentry small_copy
[PySet_MINSIZE
];
279 assert(minused
>= 0);
281 /* Find the smallest table size > minused. */
282 for (newsize
= PySet_MINSIZE
;
283 newsize
<= minused
&& newsize
> 0;
291 /* Get space for a new table. */
292 oldtable
= so
->table
;
293 assert(oldtable
!= NULL
);
294 is_oldtable_malloced
= oldtable
!= so
->smalltable
;
296 if (newsize
== PySet_MINSIZE
) {
297 /* A large table is shrinking, or we can't get any smaller. */
298 newtable
= so
->smalltable
;
299 if (newtable
== oldtable
) {
300 if (so
->fill
== so
->used
) {
301 /* No dummies, so no point doing anything. */
304 /* We're not going to resize it, but rebuild the
305 table anyway to purge old dummy entries.
306 Subtle: This is *necessary* if fill==size,
307 as set_lookkey needs at least one virgin slot to
308 terminate failing searches. If fill < size, it's
309 merely desirable, as dummies slow searches. */
310 assert(so
->fill
> so
->used
);
311 memcpy(small_copy
, oldtable
, sizeof(small_copy
));
312 oldtable
= small_copy
;
316 newtable
= PyMem_NEW(setentry
, newsize
);
317 if (newtable
== NULL
) {
323 /* Make the set empty, using the new table. */
324 assert(newtable
!= oldtable
);
325 so
->table
= newtable
;
326 so
->mask
= newsize
- 1;
327 memset(newtable
, 0, sizeof(setentry
) * newsize
);
332 /* Copy the data over; this is refcount-neutral for active entries;
333 dummy entries aren't copied over, of course */
334 for (entry
= oldtable
; i
> 0; entry
++) {
335 if (entry
->key
== NULL
) {
338 } else if (entry
->key
== dummy
) {
341 assert(entry
->key
== dummy
);
342 Py_DECREF(entry
->key
);
346 set_insert_clean(so
, entry
->key
, entry
->hash
);
350 if (is_oldtable_malloced
)
355 /* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
358 set_add_entry(register PySetObject
*so
, setentry
*entry
)
360 register Py_ssize_t n_used
;
362 assert(so
->fill
<= so
->mask
); /* at least one empty slot */
364 Py_INCREF(entry
->key
);
365 if (set_insert_key(so
, entry
->key
, entry
->hash
) == -1) {
366 Py_DECREF(entry
->key
);
369 if (!(so
->used
> n_used
&& so
->fill
*3 >= (so
->mask
+1)*2))
371 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
375 set_add_key(register PySetObject
*so
, PyObject
*key
)
378 register Py_ssize_t n_used
;
380 if (!PyString_CheckExact(key
) ||
381 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
382 hash
= PyObject_Hash(key
);
386 assert(so
->fill
<= so
->mask
); /* at least one empty slot */
389 if (set_insert_key(so
, key
, hash
) == -1) {
393 if (!(so
->used
> n_used
&& so
->fill
*3 >= (so
->mask
+1)*2))
395 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
398 #define DISCARD_NOTFOUND 0
399 #define DISCARD_FOUND 1
402 set_discard_entry(PySetObject
*so
, setentry
*oldentry
)
403 { register setentry
*entry
;
406 entry
= (so
->lookup
)(so
, oldentry
->key
, oldentry
->hash
);
409 if (entry
->key
== NULL
|| entry
->key
== dummy
)
410 return DISCARD_NOTFOUND
;
411 old_key
= entry
->key
;
416 return DISCARD_FOUND
;
420 set_discard_key(PySetObject
*so
, PyObject
*key
)
423 register setentry
*entry
;
426 assert (PyAnySet_Check(so
));
427 if (!PyString_CheckExact(key
) ||
428 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
429 hash
= PyObject_Hash(key
);
433 entry
= (so
->lookup
)(so
, key
, hash
);
436 if (entry
->key
== NULL
|| entry
->key
== dummy
)
437 return DISCARD_NOTFOUND
;
438 old_key
= entry
->key
;
443 return DISCARD_FOUND
;
447 set_clear_internal(PySetObject
*so
)
449 setentry
*entry
, *table
;
450 int table_is_malloced
;
452 setentry small_copy
[PySet_MINSIZE
];
455 assert (PyAnySet_Check(so
));
462 assert(table
!= NULL
);
463 table_is_malloced
= table
!= so
->smalltable
;
465 /* This is delicate. During the process of clearing the set,
466 * decrefs can cause the set to mutate. To avoid fatal confusion
467 * (voice of experience), we have to make the set empty before
468 * clearing the slots, and never refer to anything via so->ref while
472 if (table_is_malloced
)
473 EMPTY_TO_MINSIZE(so
);
476 /* It's a small table with something that needs to be cleared.
477 * Afraid the only safe way is to copy the set entries into
478 * another small table first.
480 memcpy(small_copy
, table
, sizeof(small_copy
));
482 EMPTY_TO_MINSIZE(so
);
484 /* else it's a small table that's already empty */
486 /* Now we can finally clear things. If C had refcounts, we could
487 * assert that the refcount on table is 1 now, i.e. that this function
488 * has unique access to it, so decref side-effects can't alter it.
490 for (entry
= table
; fill
> 0; ++entry
) {
497 Py_DECREF(entry
->key
);
501 assert(entry
->key
== NULL
);
505 if (table_is_malloced
)
511 * Iterate over a set table. Use like so:
515 * pos = 0; # important! pos should not otherwise be changed by you
516 * while (set_next(yourset, &pos, &entry)) {
517 * Refer to borrowed reference in entry->key.
520 * CAUTION: In general, it isn't safe to use set_next in a loop that
524 set_next(PySetObject
*so
, Py_ssize_t
*pos_ptr
, setentry
**entry_ptr
)
528 register setentry
*table
;
530 assert (PyAnySet_Check(so
));
535 while (i
<= mask
&& (table
[i
].key
== NULL
|| table
[i
].key
== dummy
))
540 assert(table
[i
].key
!= NULL
);
541 *entry_ptr
= &table
[i
];
546 set_dealloc(PySetObject
*so
)
548 register setentry
*entry
;
549 Py_ssize_t fill
= so
->fill
;
550 PyObject_GC_UnTrack(so
);
551 Py_TRASHCAN_SAFE_BEGIN(so
)
552 if (so
->weakreflist
!= NULL
)
553 PyObject_ClearWeakRefs((PyObject
*) so
);
555 for (entry
= so
->table
; fill
> 0; entry
++) {
558 Py_DECREF(entry
->key
);
561 if (so
->table
!= so
->smalltable
)
562 PyMem_DEL(so
->table
);
563 if (numfree
< PySet_MAXFREELIST
&& PyAnySet_CheckExact(so
))
564 free_list
[numfree
++] = so
;
566 Py_TYPE(so
)->tp_free(so
);
567 Py_TRASHCAN_SAFE_END(so
)
571 set_tp_print(PySetObject
*so
, FILE *fp
, int flags
)
575 char *emit
= ""; /* No separator emitted on first pass */
576 char *separator
= ", ";
577 int status
= Py_ReprEnter((PyObject
*)so
);
582 Py_BEGIN_ALLOW_THREADS
583 fprintf(fp
, "%s(...)", so
->ob_type
->tp_name
);
588 Py_BEGIN_ALLOW_THREADS
589 fprintf(fp
, "%s([", so
->ob_type
->tp_name
);
591 while (set_next(so
, &pos
, &entry
)) {
592 Py_BEGIN_ALLOW_THREADS
596 if (PyObject_Print(entry
->key
, fp
, 0) != 0) {
597 Py_ReprLeave((PyObject
*)so
);
601 Py_BEGIN_ALLOW_THREADS
604 Py_ReprLeave((PyObject
*)so
);
609 set_repr(PySetObject
*so
)
611 PyObject
*keys
, *result
=NULL
, *listrepr
;
612 int status
= Py_ReprEnter((PyObject
*)so
);
617 return PyString_FromFormat("%s(...)", so
->ob_type
->tp_name
);
620 keys
= PySequence_List((PyObject
*)so
);
623 listrepr
= PyObject_Repr(keys
);
625 if (listrepr
== NULL
)
628 result
= PyString_FromFormat("%s(%s)", so
->ob_type
->tp_name
,
629 PyString_AS_STRING(listrepr
));
632 Py_ReprLeave((PyObject
*)so
);
637 set_len(PyObject
*so
)
639 return ((PySetObject
*)so
)->used
;
643 set_merge(PySetObject
*so
, PyObject
*otherset
)
646 register Py_ssize_t i
;
647 register setentry
*entry
;
649 assert (PyAnySet_Check(so
));
650 assert (PyAnySet_Check(otherset
));
652 other
= (PySetObject
*)otherset
;
653 if (other
== so
|| other
->used
== 0)
654 /* a.update(a) or a.update({}); nothing to do */
656 /* Do one big resize at the start, rather than
657 * incrementally resizing as we insert new keys. Expect
658 * that there will be no (or few) overlapping keys.
660 if ((so
->fill
+ other
->used
)*3 >= (so
->mask
+1)*2) {
661 if (set_table_resize(so
, (so
->used
+ other
->used
)*2) != 0)
664 for (i
= 0; i
<= other
->mask
; i
++) {
665 entry
= &other
->table
[i
];
666 if (entry
->key
!= NULL
&&
667 entry
->key
!= dummy
) {
668 Py_INCREF(entry
->key
);
669 if (set_insert_key(so
, entry
->key
, entry
->hash
) == -1) {
670 Py_DECREF(entry
->key
);
679 set_contains_key(PySetObject
*so
, PyObject
*key
)
684 if (!PyString_CheckExact(key
) ||
685 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
686 hash
= PyObject_Hash(key
);
690 entry
= (so
->lookup
)(so
, key
, hash
);
694 return key
!= NULL
&& key
!= dummy
;
698 set_contains_entry(PySetObject
*so
, setentry
*entry
)
703 lu_entry
= (so
->lookup
)(so
, entry
->key
, entry
->hash
);
704 if (lu_entry
== NULL
)
707 return key
!= NULL
&& key
!= dummy
;
711 set_pop(PySetObject
*so
)
713 register Py_ssize_t i
= 0;
714 register setentry
*entry
;
717 assert (PyAnySet_Check(so
));
719 PyErr_SetString(PyExc_KeyError
, "pop from an empty set");
723 /* Set entry to "the first" unused or dummy set entry. We abuse
724 * the hash field of slot 0 to hold a search finger:
725 * If slot 0 has a value, use slot 0.
726 * Else slot 0 is being used to hold a search finger,
727 * and we use its hash value as the first index to look.
729 entry
= &so
->table
[0];
730 if (entry
->key
== NULL
|| entry
->key
== dummy
) {
732 /* The hash field may be a real hash value, or it may be a
733 * legit search finger, or it may be a once-legit search
734 * finger that's out of bounds now because it wrapped around
735 * or the table shrunk -- simply make sure it's in bounds now.
737 if (i
> so
->mask
|| i
< 1)
738 i
= 1; /* skip slot 0 */
739 while ((entry
= &so
->table
[i
])->key
== NULL
|| entry
->key
==dummy
) {
749 so
->table
[0].hash
= i
+ 1; /* next place to start */
753 PyDoc_STRVAR(pop_doc
, "Remove and return an arbitrary set element.");
756 set_traverse(PySetObject
*so
, visitproc visit
, void *arg
)
761 while (set_next(so
, &pos
, &entry
))
762 Py_VISIT(entry
->key
);
767 frozenset_hash(PyObject
*self
)
769 PySetObject
*so
= (PySetObject
*)self
;
770 long h
, hash
= 1927868237L;
777 hash
*= PySet_GET_SIZE(self
) + 1;
778 while (set_next(so
, &pos
, &entry
)) {
779 /* Work to increase the bit dispersion for closely spaced hash
780 values. The is important because some use cases have many
781 combinations of a small number of elements with nearby
782 hashes so that many distinct combinations collapse to only
783 a handful of distinct hash values. */
785 hash
^= (h
^ (h
<< 16) ^ 89869747L) * 3644798167u;
787 hash
= hash
* 69069L + 907133923L;
794 /***** Set iterator type ***********************************************/
798 PySetObject
*si_set
; /* Set to NULL when iterator is exhausted */
805 setiter_dealloc(setiterobject
*si
)
807 Py_XDECREF(si
->si_set
);
812 setiter_len(setiterobject
*si
)
815 if (si
->si_set
!= NULL
&& si
->si_used
== si
->si_set
->used
)
817 return PyInt_FromLong(len
);
820 PyDoc_STRVAR(length_hint_doc
, "Private method returning an estimate of len(list(it)).");
822 static PyMethodDef setiter_methods
[] = {
823 {"__length_hint__", (PyCFunction
)setiter_len
, METH_NOARGS
, length_hint_doc
},
824 {NULL
, NULL
} /* sentinel */
827 static PyObject
*setiter_iternext(setiterobject
*si
)
830 register Py_ssize_t i
, mask
;
831 register setentry
*entry
;
832 PySetObject
*so
= si
->si_set
;
836 assert (PyAnySet_Check(so
));
838 if (si
->si_used
!= so
->used
) {
839 PyErr_SetString(PyExc_RuntimeError
,
840 "Set changed size during iteration");
841 si
->si_used
= -1; /* Make this state sticky */
849 while (i
<= mask
&& (entry
[i
].key
== NULL
|| entry
[i
].key
== dummy
))
865 static PyTypeObject PySetIter_Type
= {
866 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
867 "setiterator", /* tp_name */
868 sizeof(setiterobject
), /* tp_basicsize */
871 (destructor
)setiter_dealloc
, /* tp_dealloc */
877 0, /* tp_as_number */
878 0, /* tp_as_sequence */
879 0, /* tp_as_mapping */
883 PyObject_GenericGetAttr
, /* tp_getattro */
885 0, /* tp_as_buffer */
886 Py_TPFLAGS_DEFAULT
, /* tp_flags */
890 0, /* tp_richcompare */
891 0, /* tp_weaklistoffset */
892 PyObject_SelfIter
, /* tp_iter */
893 (iternextfunc
)setiter_iternext
, /* tp_iternext */
894 setiter_methods
, /* tp_methods */
899 set_iter(PySetObject
*so
)
901 setiterobject
*si
= PyObject_New(setiterobject
, &PySetIter_Type
);
906 si
->si_used
= so
->used
;
909 return (PyObject
*)si
;
913 set_update_internal(PySetObject
*so
, PyObject
*other
)
917 if (PyAnySet_Check(other
))
918 return set_merge(so
, other
);
920 if (PyDict_CheckExact(other
)) {
924 Py_ssize_t dictsize
= PyDict_Size(other
);
926 /* Do one big resize at the start, rather than
927 * incrementally resizing as we insert new keys. Expect
928 * that there will be no (or few) overlapping keys.
932 if ((so
->fill
+ dictsize
)*3 >= (so
->mask
+1)*2) {
933 if (set_table_resize(so
, (so
->used
+ dictsize
)*2) != 0)
936 while (_PyDict_Next(other
, &pos
, &key
, &value
, &hash
)) {
939 an_entry
.hash
= hash
;
941 if (set_add_entry(so
, &an_entry
) == -1)
947 it
= PyObject_GetIter(other
);
951 while ((key
= PyIter_Next(it
)) != NULL
) {
952 if (set_add_key(so
, key
) == -1) {
960 if (PyErr_Occurred())
966 set_update(PySetObject
*so
, PyObject
*other
)
968 if (set_update_internal(so
, other
) == -1)
973 PyDoc_STRVAR(update_doc
,
974 "Update a set with the union of itself and another.");
977 make_new_set(PyTypeObject
*type
, PyObject
*iterable
)
979 register PySetObject
*so
= NULL
;
981 if (dummy
== NULL
) { /* Auto-initialize dummy */
982 dummy
= PyString_FromString("<dummy key>");
987 /* create PySetObject structure */
989 (type
== &PySet_Type
|| type
== &PyFrozenSet_Type
)) {
990 so
= free_list
[--numfree
];
991 assert (so
!= NULL
&& PyAnySet_CheckExact(so
));
993 _Py_NewReference((PyObject
*)so
);
994 EMPTY_TO_MINSIZE(so
);
995 PyObject_GC_Track(so
);
997 so
= (PySetObject
*)type
->tp_alloc(type
, 0);
1000 /* tp_alloc has already zeroed the structure */
1001 assert(so
->table
== NULL
&& so
->fill
== 0 && so
->used
== 0);
1002 INIT_NONZERO_SET_SLOTS(so
);
1005 so
->lookup
= set_lookkey_string
;
1006 so
->weakreflist
= NULL
;
1008 if (iterable
!= NULL
) {
1009 if (set_update_internal(so
, iterable
) == -1) {
1015 return (PyObject
*)so
;
1018 /* The empty frozenset is a singleton */
1019 static PyObject
*emptyfrozenset
= NULL
;
1022 frozenset_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1024 PyObject
*iterable
= NULL
, *result
;
1026 if (type
== &PyFrozenSet_Type
&& !_PyArg_NoKeywords("frozenset()", kwds
))
1029 if (!PyArg_UnpackTuple(args
, type
->tp_name
, 0, 1, &iterable
))
1032 if (type
!= &PyFrozenSet_Type
)
1033 return make_new_set(type
, iterable
);
1035 if (iterable
!= NULL
) {
1036 /* frozenset(f) is idempotent */
1037 if (PyFrozenSet_CheckExact(iterable
)) {
1038 Py_INCREF(iterable
);
1041 result
= make_new_set(type
, iterable
);
1042 if (result
== NULL
|| PySet_GET_SIZE(result
))
1046 /* The empty frozenset is a singleton */
1047 if (emptyfrozenset
== NULL
)
1048 emptyfrozenset
= make_new_set(type
, NULL
);
1049 Py_XINCREF(emptyfrozenset
);
1050 return emptyfrozenset
;
1060 so
= free_list
[numfree
];
1061 PyObject_GC_Del(so
);
1064 Py_CLEAR(emptyfrozenset
);
1068 set_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1070 if (type
== &PySet_Type
&& !_PyArg_NoKeywords("set()", kwds
))
1073 return make_new_set(type
, NULL
);
1076 /* set_swap_bodies() switches the contents of any two sets by moving their
1077 internal data pointers and, if needed, copying the internal smalltables.
1078 Semantically equivalent to:
1080 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1082 The function always succeeds and it leaves both objects in a stable state.
1083 Useful for creating temporary frozensets from sets for membership testing
1084 in __contains__(), discard(), and remove(). Also useful for operations
1085 that update in-place (by allowing an intermediate result to be swapped
1086 into one of the original inputs).
1090 set_swap_bodies(PySetObject
*a
, PySetObject
*b
)
1094 setentry
*(*f
)(PySetObject
*so
, PyObject
*key
, long hash
);
1095 setentry tab
[PySet_MINSIZE
];
1098 t
= a
->fill
; a
->fill
= b
->fill
; b
->fill
= t
;
1099 t
= a
->used
; a
->used
= b
->used
; b
->used
= t
;
1100 t
= a
->mask
; a
->mask
= b
->mask
; b
->mask
= t
;
1103 if (a
->table
== a
->smalltable
)
1105 a
->table
= b
->table
;
1106 if (b
->table
== b
->smalltable
)
1107 a
->table
= a
->smalltable
;
1110 f
= a
->lookup
; a
->lookup
= b
->lookup
; b
->lookup
= f
;
1112 if (a
->table
== a
->smalltable
|| b
->table
== b
->smalltable
) {
1113 memcpy(tab
, a
->smalltable
, sizeof(tab
));
1114 memcpy(a
->smalltable
, b
->smalltable
, sizeof(tab
));
1115 memcpy(b
->smalltable
, tab
, sizeof(tab
));
1118 if (PyType_IsSubtype(Py_TYPE(a
), &PyFrozenSet_Type
) &&
1119 PyType_IsSubtype(Py_TYPE(b
), &PyFrozenSet_Type
)) {
1120 h
= a
->hash
; a
->hash
= b
->hash
; b
->hash
= h
;
1128 set_copy(PySetObject
*so
)
1130 return make_new_set(Py_TYPE(so
), (PyObject
*)so
);
1134 frozenset_copy(PySetObject
*so
)
1136 if (PyFrozenSet_CheckExact(so
)) {
1138 return (PyObject
*)so
;
1140 return set_copy(so
);
1143 PyDoc_STRVAR(copy_doc
, "Return a shallow copy of a set.");
1146 set_clear(PySetObject
*so
)
1148 set_clear_internal(so
);
1152 PyDoc_STRVAR(clear_doc
, "Remove all elements from this set.");
1155 set_union(PySetObject
*so
, PyObject
*other
)
1157 PySetObject
*result
;
1159 result
= (PySetObject
*)set_copy(so
);
1162 if ((PyObject
*)so
== other
)
1163 return (PyObject
*)result
;
1164 if (set_update_internal(result
, other
) == -1) {
1168 return (PyObject
*)result
;
1171 PyDoc_STRVAR(union_doc
,
1172 "Return the union of two sets as a new set.\n\
1174 (i.e. all elements that are in either set.)");
1177 set_or(PySetObject
*so
, PyObject
*other
)
1179 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1180 Py_INCREF(Py_NotImplemented
);
1181 return Py_NotImplemented
;
1183 return set_union(so
, other
);
1187 set_ior(PySetObject
*so
, PyObject
*other
)
1189 if (!PyAnySet_Check(other
)) {
1190 Py_INCREF(Py_NotImplemented
);
1191 return Py_NotImplemented
;
1193 if (set_update_internal(so
, other
) == -1)
1196 return (PyObject
*)so
;
1200 set_intersection(PySetObject
*so
, PyObject
*other
)
1202 PySetObject
*result
;
1203 PyObject
*key
, *it
, *tmp
;
1205 if ((PyObject
*)so
== other
)
1206 return set_copy(so
);
1208 result
= (PySetObject
*)make_new_set(Py_TYPE(so
), NULL
);
1212 if (PyAnySet_Check(other
)) {
1216 if (PySet_GET_SIZE(other
) > PySet_GET_SIZE(so
)) {
1217 tmp
= (PyObject
*)so
;
1218 so
= (PySetObject
*)other
;
1222 while (set_next((PySetObject
*)other
, &pos
, &entry
)) {
1223 int rv
= set_contains_entry(so
, entry
);
1229 if (set_add_entry(result
, entry
) == -1) {
1235 return (PyObject
*)result
;
1238 it
= PyObject_GetIter(other
);
1244 while ((key
= PyIter_Next(it
)) != NULL
) {
1247 long hash
= PyObject_Hash(key
);
1257 rv
= set_contains_entry(so
, &entry
);
1265 if (set_add_entry(result
, &entry
) == -1) {
1275 if (PyErr_Occurred()) {
1279 return (PyObject
*)result
;
1282 PyDoc_STRVAR(intersection_doc
,
1283 "Return the intersection of two sets as a new set.\n\
1285 (i.e. all elements that are in both sets.)");
1288 set_intersection_update(PySetObject
*so
, PyObject
*other
)
1292 tmp
= set_intersection(so
, other
);
1295 set_swap_bodies(so
, (PySetObject
*)tmp
);
1300 PyDoc_STRVAR(intersection_update_doc
,
1301 "Update a set with the intersection of itself and another.");
1304 set_and(PySetObject
*so
, PyObject
*other
)
1306 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1307 Py_INCREF(Py_NotImplemented
);
1308 return Py_NotImplemented
;
1310 return set_intersection(so
, other
);
1314 set_iand(PySetObject
*so
, PyObject
*other
)
1318 if (!PyAnySet_Check(other
)) {
1319 Py_INCREF(Py_NotImplemented
);
1320 return Py_NotImplemented
;
1322 result
= set_intersection_update(so
, other
);
1327 return (PyObject
*)so
;
1331 set_isdisjoint(PySetObject
*so
, PyObject
*other
)
1333 PyObject
*key
, *it
, *tmp
;
1335 if ((PyObject
*)so
== other
) {
1336 if (PySet_GET_SIZE(so
) == 0)
1342 if (PyAnySet_CheckExact(other
)) {
1346 if (PySet_GET_SIZE(other
) > PySet_GET_SIZE(so
)) {
1347 tmp
= (PyObject
*)so
;
1348 so
= (PySetObject
*)other
;
1351 while (set_next((PySetObject
*)other
, &pos
, &entry
)) {
1352 int rv
= set_contains_entry(so
, entry
);
1361 it
= PyObject_GetIter(other
);
1365 while ((key
= PyIter_Next(it
)) != NULL
) {
1368 long hash
= PyObject_Hash(key
);
1377 rv
= set_contains_entry(so
, &entry
);
1389 if (PyErr_Occurred())
1394 PyDoc_STRVAR(isdisjoint_doc
,
1395 "Return True if two sets have a null intersection.");
1398 set_difference_update_internal(PySetObject
*so
, PyObject
*other
)
1400 if ((PyObject
*)so
== other
)
1401 return set_clear_internal(so
);
1403 if (PyAnySet_Check(other
)) {
1407 while (set_next((PySetObject
*)other
, &pos
, &entry
))
1408 if (set_discard_entry(so
, entry
) == -1)
1412 it
= PyObject_GetIter(other
);
1416 while ((key
= PyIter_Next(it
)) != NULL
) {
1417 if (set_discard_key(so
, key
) == -1) {
1425 if (PyErr_Occurred())
1428 /* If more than 1/5 are dummies, then resize them away. */
1429 if ((so
->fill
- so
->used
) * 5 < so
->mask
)
1431 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
1435 set_difference_update(PySetObject
*so
, PyObject
*other
)
1437 if (set_difference_update_internal(so
, other
) != -1)
1442 PyDoc_STRVAR(difference_update_doc
,
1443 "Remove all elements of another set from this set.");
1446 set_difference(PySetObject
*so
, PyObject
*other
)
1452 if (!PyAnySet_Check(other
) && !PyDict_CheckExact(other
)) {
1453 result
= set_copy(so
);
1456 if (set_difference_update_internal((PySetObject
*)result
, other
) != -1)
1462 result
= make_new_set(Py_TYPE(so
), NULL
);
1466 if (PyDict_CheckExact(other
)) {
1467 while (set_next(so
, &pos
, &entry
)) {
1469 entrycopy
.hash
= entry
->hash
;
1470 entrycopy
.key
= entry
->key
;
1471 if (!_PyDict_Contains(other
, entry
->key
, entry
->hash
)) {
1472 if (set_add_entry((PySetObject
*)result
, &entrycopy
) == -1) {
1481 while (set_next(so
, &pos
, &entry
)) {
1482 int rv
= set_contains_entry((PySetObject
*)other
, entry
);
1488 if (set_add_entry((PySetObject
*)result
, entry
) == -1) {
1497 PyDoc_STRVAR(difference_doc
,
1498 "Return the difference of two sets as a new set.\n\
1500 (i.e. all elements that are in this set but not the other.)");
1502 set_sub(PySetObject
*so
, PyObject
*other
)
1504 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1505 Py_INCREF(Py_NotImplemented
);
1506 return Py_NotImplemented
;
1508 return set_difference(so
, other
);
1512 set_isub(PySetObject
*so
, PyObject
*other
)
1516 if (!PyAnySet_Check(other
)) {
1517 Py_INCREF(Py_NotImplemented
);
1518 return Py_NotImplemented
;
1520 result
= set_difference_update(so
, other
);
1525 return (PyObject
*)so
;
1529 set_symmetric_difference_update(PySetObject
*so
, PyObject
*other
)
1531 PySetObject
*otherset
;
1536 if ((PyObject
*)so
== other
)
1537 return set_clear(so
);
1539 if (PyDict_CheckExact(other
)) {
1543 while (_PyDict_Next(other
, &pos
, &key
, &value
, &hash
)) {
1546 an_entry
.hash
= hash
;
1548 rv
= set_discard_entry(so
, &an_entry
);
1551 if (rv
== DISCARD_NOTFOUND
) {
1552 if (set_add_entry(so
, &an_entry
) == -1)
1559 if (PyAnySet_Check(other
)) {
1561 otherset
= (PySetObject
*)other
;
1563 otherset
= (PySetObject
*)make_new_set(Py_TYPE(so
), other
);
1564 if (otherset
== NULL
)
1568 while (set_next(otherset
, &pos
, &entry
)) {
1569 int rv
= set_discard_entry(so
, entry
);
1571 Py_DECREF(otherset
);
1574 if (rv
== DISCARD_NOTFOUND
) {
1575 if (set_add_entry(so
, entry
) == -1) {
1576 Py_DECREF(otherset
);
1581 Py_DECREF(otherset
);
1585 PyDoc_STRVAR(symmetric_difference_update_doc
,
1586 "Update a set with the symmetric difference of itself and another.");
1589 set_symmetric_difference(PySetObject
*so
, PyObject
*other
)
1592 PySetObject
*otherset
;
1594 otherset
= (PySetObject
*)make_new_set(Py_TYPE(so
), other
);
1595 if (otherset
== NULL
)
1597 rv
= set_symmetric_difference_update(otherset
, (PyObject
*)so
);
1601 return (PyObject
*)otherset
;
1604 PyDoc_STRVAR(symmetric_difference_doc
,
1605 "Return the symmetric difference of two sets as a new set.\n\
1607 (i.e. all elements that are in exactly one of the sets.)");
1610 set_xor(PySetObject
*so
, PyObject
*other
)
1612 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1613 Py_INCREF(Py_NotImplemented
);
1614 return Py_NotImplemented
;
1616 return set_symmetric_difference(so
, other
);
1620 set_ixor(PySetObject
*so
, PyObject
*other
)
1624 if (!PyAnySet_Check(other
)) {
1625 Py_INCREF(Py_NotImplemented
);
1626 return Py_NotImplemented
;
1628 result
= set_symmetric_difference_update(so
, other
);
1633 return (PyObject
*)so
;
1637 set_issubset(PySetObject
*so
, PyObject
*other
)
1642 if (!PyAnySet_Check(other
)) {
1643 PyObject
*tmp
, *result
;
1644 tmp
= make_new_set(&PySet_Type
, other
);
1647 result
= set_issubset(so
, tmp
);
1651 if (PySet_GET_SIZE(so
) > PySet_GET_SIZE(other
))
1654 while (set_next(so
, &pos
, &entry
)) {
1655 int rv
= set_contains_entry((PySetObject
*)other
, entry
);
1664 PyDoc_STRVAR(issubset_doc
, "Report whether another set contains this set.");
1667 set_issuperset(PySetObject
*so
, PyObject
*other
)
1669 PyObject
*tmp
, *result
;
1671 if (!PyAnySet_Check(other
)) {
1672 tmp
= make_new_set(&PySet_Type
, other
);
1675 result
= set_issuperset(so
, tmp
);
1679 return set_issubset((PySetObject
*)other
, (PyObject
*)so
);
1682 PyDoc_STRVAR(issuperset_doc
, "Report whether this set contains another set.");
1685 set_richcompare(PySetObject
*v
, PyObject
*w
, int op
)
1689 if(!PyAnySet_Check(w
)) {
1694 PyErr_SetString(PyExc_TypeError
, "can only compare to a set");
1699 if (PySet_GET_SIZE(v
) != PySet_GET_SIZE(w
))
1701 if (v
->hash
!= -1 &&
1702 ((PySetObject
*)w
)->hash
!= -1 &&
1703 v
->hash
!= ((PySetObject
*)w
)->hash
)
1705 return set_issubset(v
, w
);
1707 r1
= set_richcompare(v
, w
, Py_EQ
);
1710 r2
= PyBool_FromLong(PyObject_Not(r1
));
1714 return set_issubset(v
, w
);
1716 return set_issuperset(v
, w
);
1718 if (PySet_GET_SIZE(v
) >= PySet_GET_SIZE(w
))
1720 return set_issubset(v
, w
);
1722 if (PySet_GET_SIZE(v
) <= PySet_GET_SIZE(w
))
1724 return set_issuperset(v
, w
);
1726 Py_INCREF(Py_NotImplemented
);
1727 return Py_NotImplemented
;
1731 set_nocmp(PyObject
*self
, PyObject
*other
)
1733 PyErr_SetString(PyExc_TypeError
, "cannot compare sets using cmp()");
1738 set_add(PySetObject
*so
, PyObject
*key
)
1740 if (set_add_key(so
, key
) == -1)
1745 PyDoc_STRVAR(add_doc
,
1746 "Add an element to a set.\n\
1748 This has no effect if the element is already present.");
1751 set_contains(PySetObject
*so
, PyObject
*key
)
1756 rv
= set_contains_key(so
, key
);
1758 if (!PySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1761 tmpkey
= make_new_set(&PyFrozenSet_Type
, NULL
);
1764 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1765 rv
= set_contains(so
, tmpkey
);
1766 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1773 set_direct_contains(PySetObject
*so
, PyObject
*key
)
1777 result
= set_contains(so
, key
);
1780 return PyBool_FromLong(result
);
1783 PyDoc_STRVAR(contains_doc
, "x.__contains__(y) <==> y in x.");
1786 set_remove(PySetObject
*so
, PyObject
*key
)
1788 PyObject
*tmpkey
, *result
;
1791 rv
= set_discard_key(so
, key
);
1793 if (!PySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1796 tmpkey
= make_new_set(&PyFrozenSet_Type
, NULL
);
1799 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1800 result
= set_remove(so
, tmpkey
);
1801 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1804 } else if (rv
== DISCARD_NOTFOUND
) {
1811 PyDoc_STRVAR(remove_doc
,
1812 "Remove an element from a set; it must be a member.\n\
1814 If the element is not a member, raise a KeyError.");
1817 set_discard(PySetObject
*so
, PyObject
*key
)
1819 PyObject
*tmpkey
, *result
;
1822 rv
= set_discard_key(so
, key
);
1824 if (!PySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1827 tmpkey
= make_new_set(&PyFrozenSet_Type
, NULL
);
1830 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1831 result
= set_discard(so
, tmpkey
);
1832 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1839 PyDoc_STRVAR(discard_doc
,
1840 "Remove an element from a set if it is a member.\n\
1842 If the element is not a member, do nothing.");
1845 set_reduce(PySetObject
*so
)
1847 PyObject
*keys
=NULL
, *args
=NULL
, *result
=NULL
, *dict
=NULL
;
1849 keys
= PySequence_List((PyObject
*)so
);
1852 args
= PyTuple_Pack(1, keys
);
1855 dict
= PyObject_GetAttrString((PyObject
*)so
, "__dict__");
1861 result
= PyTuple_Pack(3, Py_TYPE(so
), args
, dict
);
1869 PyDoc_STRVAR(reduce_doc
, "Return state information for pickling.");
1872 set_init(PySetObject
*self
, PyObject
*args
, PyObject
*kwds
)
1874 PyObject
*iterable
= NULL
;
1876 if (!PyAnySet_Check(self
))
1878 if (!PyArg_UnpackTuple(args
, Py_TYPE(self
)->tp_name
, 0, 1, &iterable
))
1880 set_clear_internal(self
);
1882 if (iterable
== NULL
)
1884 return set_update_internal(self
, iterable
);
1887 static PySequenceMethods set_as_sequence
= {
1888 set_len
, /* sq_length */
1893 0, /* sq_ass_item */
1894 0, /* sq_ass_slice */
1895 (objobjproc
)set_contains
, /* sq_contains */
1898 /* set object ********************************************************/
1901 static PyObject
*test_c_api(PySetObject
*so
);
1903 PyDoc_STRVAR(test_c_api_doc
, "Exercises C API. Returns True.\n\
1904 All is well if assertions don't fail.");
1907 static PyMethodDef set_methods
[] = {
1908 {"add", (PyCFunction
)set_add
, METH_O
,
1910 {"clear", (PyCFunction
)set_clear
, METH_NOARGS
,
1912 {"__contains__",(PyCFunction
)set_direct_contains
, METH_O
| METH_COEXIST
,
1914 {"copy", (PyCFunction
)set_copy
, METH_NOARGS
,
1916 {"discard", (PyCFunction
)set_discard
, METH_O
,
1918 {"difference", (PyCFunction
)set_difference
, METH_O
,
1920 {"difference_update", (PyCFunction
)set_difference_update
, METH_O
,
1921 difference_update_doc
},
1922 {"intersection",(PyCFunction
)set_intersection
, METH_O
,
1924 {"intersection_update",(PyCFunction
)set_intersection_update
, METH_O
,
1925 intersection_update_doc
},
1926 {"isdisjoint", (PyCFunction
)set_isdisjoint
, METH_O
,
1928 {"issubset", (PyCFunction
)set_issubset
, METH_O
,
1930 {"issuperset", (PyCFunction
)set_issuperset
, METH_O
,
1932 {"pop", (PyCFunction
)set_pop
, METH_NOARGS
,
1934 {"__reduce__", (PyCFunction
)set_reduce
, METH_NOARGS
,
1936 {"remove", (PyCFunction
)set_remove
, METH_O
,
1938 {"symmetric_difference",(PyCFunction
)set_symmetric_difference
, METH_O
,
1939 symmetric_difference_doc
},
1940 {"symmetric_difference_update",(PyCFunction
)set_symmetric_difference_update
, METH_O
,
1941 symmetric_difference_update_doc
},
1943 {"test_c_api", (PyCFunction
)test_c_api
, METH_NOARGS
,
1946 {"union", (PyCFunction
)set_union
, METH_O
,
1948 {"update", (PyCFunction
)set_update
, METH_O
,
1950 {NULL
, NULL
} /* sentinel */
1953 static PyNumberMethods set_as_number
= {
1955 (binaryfunc
)set_sub
, /*nb_subtract*/
1968 (binaryfunc
)set_and
, /*nb_and*/
1969 (binaryfunc
)set_xor
, /*nb_xor*/
1970 (binaryfunc
)set_or
, /*nb_or*/
1977 0, /*nb_inplace_add*/
1978 (binaryfunc
)set_isub
, /*nb_inplace_subtract*/
1979 0, /*nb_inplace_multiply*/
1980 0, /*nb_inplace_divide*/
1981 0, /*nb_inplace_remainder*/
1982 0, /*nb_inplace_power*/
1983 0, /*nb_inplace_lshift*/
1984 0, /*nb_inplace_rshift*/
1985 (binaryfunc
)set_iand
, /*nb_inplace_and*/
1986 (binaryfunc
)set_ixor
, /*nb_inplace_xor*/
1987 (binaryfunc
)set_ior
, /*nb_inplace_or*/
1990 PyDoc_STRVAR(set_doc
,
1991 "set(iterable) --> set object\n\
1993 Build an unordered collection of unique elements.");
1995 PyTypeObject PySet_Type
= {
1996 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
1997 "set", /* tp_name */
1998 sizeof(PySetObject
), /* tp_basicsize */
1999 0, /* tp_itemsize */
2001 (destructor
)set_dealloc
, /* tp_dealloc */
2002 (printfunc
)set_tp_print
, /* tp_print */
2005 set_nocmp
, /* tp_compare */
2006 (reprfunc
)set_repr
, /* tp_repr */
2007 &set_as_number
, /* tp_as_number */
2008 &set_as_sequence
, /* tp_as_sequence */
2009 0, /* tp_as_mapping */
2013 PyObject_GenericGetAttr
, /* tp_getattro */
2014 0, /* tp_setattro */
2015 0, /* tp_as_buffer */
2016 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
| Py_TPFLAGS_CHECKTYPES
|
2017 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2018 set_doc
, /* tp_doc */
2019 (traverseproc
)set_traverse
, /* tp_traverse */
2020 (inquiry
)set_clear_internal
, /* tp_clear */
2021 (richcmpfunc
)set_richcompare
, /* tp_richcompare */
2022 offsetof(PySetObject
, weakreflist
), /* tp_weaklistoffset */
2023 (getiterfunc
)set_iter
, /* tp_iter */
2024 0, /* tp_iternext */
2025 set_methods
, /* tp_methods */
2030 0, /* tp_descr_get */
2031 0, /* tp_descr_set */
2032 0, /* tp_dictoffset */
2033 (initproc
)set_init
, /* tp_init */
2034 PyType_GenericAlloc
, /* tp_alloc */
2035 set_new
, /* tp_new */
2036 PyObject_GC_Del
, /* tp_free */
2039 /* frozenset object ********************************************************/
2042 static PyMethodDef frozenset_methods
[] = {
2043 {"__contains__",(PyCFunction
)set_direct_contains
, METH_O
| METH_COEXIST
,
2045 {"copy", (PyCFunction
)frozenset_copy
, METH_NOARGS
,
2047 {"difference", (PyCFunction
)set_difference
, METH_O
,
2049 {"intersection",(PyCFunction
)set_intersection
, METH_O
,
2051 {"isdisjoint", (PyCFunction
)set_isdisjoint
, METH_O
,
2053 {"issubset", (PyCFunction
)set_issubset
, METH_O
,
2055 {"issuperset", (PyCFunction
)set_issuperset
, METH_O
,
2057 {"__reduce__", (PyCFunction
)set_reduce
, METH_NOARGS
,
2059 {"symmetric_difference",(PyCFunction
)set_symmetric_difference
, METH_O
,
2060 symmetric_difference_doc
},
2061 {"union", (PyCFunction
)set_union
, METH_O
,
2063 {NULL
, NULL
} /* sentinel */
2066 static PyNumberMethods frozenset_as_number
= {
2068 (binaryfunc
)set_sub
, /*nb_subtract*/
2081 (binaryfunc
)set_and
, /*nb_and*/
2082 (binaryfunc
)set_xor
, /*nb_xor*/
2083 (binaryfunc
)set_or
, /*nb_or*/
2086 PyDoc_STRVAR(frozenset_doc
,
2087 "frozenset(iterable) --> frozenset object\n\
2089 Build an immutable unordered collection of unique elements.");
2091 PyTypeObject PyFrozenSet_Type
= {
2092 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2093 "frozenset", /* tp_name */
2094 sizeof(PySetObject
), /* tp_basicsize */
2095 0, /* tp_itemsize */
2097 (destructor
)set_dealloc
, /* tp_dealloc */
2098 (printfunc
)set_tp_print
, /* tp_print */
2101 set_nocmp
, /* tp_compare */
2102 (reprfunc
)set_repr
, /* tp_repr */
2103 &frozenset_as_number
, /* tp_as_number */
2104 &set_as_sequence
, /* tp_as_sequence */
2105 0, /* tp_as_mapping */
2106 frozenset_hash
, /* tp_hash */
2109 PyObject_GenericGetAttr
, /* tp_getattro */
2110 0, /* tp_setattro */
2111 0, /* tp_as_buffer */
2112 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
| Py_TPFLAGS_CHECKTYPES
|
2113 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2114 frozenset_doc
, /* tp_doc */
2115 (traverseproc
)set_traverse
, /* tp_traverse */
2116 (inquiry
)set_clear_internal
, /* tp_clear */
2117 (richcmpfunc
)set_richcompare
, /* tp_richcompare */
2118 offsetof(PySetObject
, weakreflist
), /* tp_weaklistoffset */
2119 (getiterfunc
)set_iter
, /* tp_iter */
2120 0, /* tp_iternext */
2121 frozenset_methods
, /* tp_methods */
2126 0, /* tp_descr_get */
2127 0, /* tp_descr_set */
2128 0, /* tp_dictoffset */
2130 PyType_GenericAlloc
, /* tp_alloc */
2131 frozenset_new
, /* tp_new */
2132 PyObject_GC_Del
, /* tp_free */
2136 /***** C API functions *************************************************/
2139 PySet_New(PyObject
*iterable
)
2141 return make_new_set(&PySet_Type
, iterable
);
2145 PyFrozenSet_New(PyObject
*iterable
)
2147 return make_new_set(&PyFrozenSet_Type
, iterable
);
2151 PySet_Size(PyObject
*anyset
)
2153 if (!PyAnySet_Check(anyset
)) {
2154 PyErr_BadInternalCall();
2157 return PySet_GET_SIZE(anyset
);
2161 PySet_Clear(PyObject
*set
)
2163 if (!PySet_Check(set
)) {
2164 PyErr_BadInternalCall();
2167 return set_clear_internal((PySetObject
*)set
);
2171 PySet_Contains(PyObject
*anyset
, PyObject
*key
)
2173 if (!PyAnySet_Check(anyset
)) {
2174 PyErr_BadInternalCall();
2177 return set_contains_key((PySetObject
*)anyset
, key
);
2181 PySet_Discard(PyObject
*set
, PyObject
*key
)
2183 if (!PySet_Check(set
)) {
2184 PyErr_BadInternalCall();
2187 return set_discard_key((PySetObject
*)set
, key
);
2191 PySet_Add(PyObject
*anyset
, PyObject
*key
)
2193 if (!PySet_Check(anyset
) &&
2194 (!PyFrozenSet_Check(anyset
) || Py_REFCNT(anyset
) != 1)) {
2195 PyErr_BadInternalCall();
2198 return set_add_key((PySetObject
*)anyset
, key
);
2202 _PySet_Next(PyObject
*set
, Py_ssize_t
*pos
, PyObject
**key
)
2204 setentry
*entry_ptr
;
2206 if (!PyAnySet_Check(set
)) {
2207 PyErr_BadInternalCall();
2210 if (set_next((PySetObject
*)set
, pos
, &entry_ptr
) == 0)
2212 *key
= entry_ptr
->key
;
2217 _PySet_NextEntry(PyObject
*set
, Py_ssize_t
*pos
, PyObject
**key
, long *hash
)
2221 if (!PyAnySet_Check(set
)) {
2222 PyErr_BadInternalCall();
2225 if (set_next((PySetObject
*)set
, pos
, &entry
) == 0)
2228 *hash
= entry
->hash
;
2233 PySet_Pop(PyObject
*set
)
2235 if (!PySet_Check(set
)) {
2236 PyErr_BadInternalCall();
2239 return set_pop((PySetObject
*)set
);
2243 _PySet_Update(PyObject
*set
, PyObject
*iterable
)
2245 if (!PySet_Check(set
)) {
2246 PyErr_BadInternalCall();
2249 return set_update_internal((PySetObject
*)set
, iterable
);
2254 /* Test code to be called with any three element set.
2255 Returns True and original set is restored. */
2257 #define assertRaises(call_return_value, exception) \
2259 assert(call_return_value); \
2260 assert(PyErr_ExceptionMatches(exception)); \
2265 test_c_api(PySetObject
*so
)
2270 PyObject
*elem
=NULL
, *dup
=NULL
, *t
, *f
, *dup2
, *x
;
2271 PyObject
*ob
= (PyObject
*)so
;
2273 /* Verify preconditions and exercise type/size checks */
2274 assert(PyAnySet_Check(ob
));
2275 assert(PyAnySet_CheckExact(ob
));
2276 assert(!PyFrozenSet_CheckExact(ob
));
2277 assert(PySet_Size(ob
) == 3);
2278 assert(PySet_GET_SIZE(ob
) == 3);
2280 /* Raise TypeError for non-iterable constructor arguments */
2281 assertRaises(PySet_New(Py_None
) == NULL
, PyExc_TypeError
);
2282 assertRaises(PyFrozenSet_New(Py_None
) == NULL
, PyExc_TypeError
);
2284 /* Raise TypeError for unhashable key */
2285 dup
= PySet_New(ob
);
2286 assertRaises(PySet_Discard(ob
, dup
) == -1, PyExc_TypeError
);
2287 assertRaises(PySet_Contains(ob
, dup
) == -1, PyExc_TypeError
);
2288 assertRaises(PySet_Add(ob
, dup
) == -1, PyExc_TypeError
);
2290 /* Exercise successful pop, contains, add, and discard */
2291 elem
= PySet_Pop(ob
);
2292 assert(PySet_Contains(ob
, elem
) == 0);
2293 assert(PySet_GET_SIZE(ob
) == 2);
2294 assert(PySet_Add(ob
, elem
) == 0);
2295 assert(PySet_Contains(ob
, elem
) == 1);
2296 assert(PySet_GET_SIZE(ob
) == 3);
2297 assert(PySet_Discard(ob
, elem
) == 1);
2298 assert(PySet_GET_SIZE(ob
) == 2);
2299 assert(PySet_Discard(ob
, elem
) == 0);
2300 assert(PySet_GET_SIZE(ob
) == 2);
2302 /* Exercise clear */
2303 dup2
= PySet_New(dup
);
2304 assert(PySet_Clear(dup2
) == 0);
2305 assert(PySet_Size(dup2
) == 0);
2308 /* Raise SystemError on clear or update of frozen set */
2309 f
= PyFrozenSet_New(dup
);
2310 assertRaises(PySet_Clear(f
) == -1, PyExc_SystemError
);
2311 assertRaises(_PySet_Update(f
, dup
) == -1, PyExc_SystemError
);
2312 assert(PySet_Add(f
, elem
) == 0);
2314 assertRaises(PySet_Add(f
, elem
) == -1, PyExc_SystemError
);
2318 /* Exercise direct iteration */
2320 while (_PySet_Next((PyObject
*)dup
, &i
, &x
)) {
2321 s
= PyString_AsString(x
);
2322 assert(s
&& (s
[0] == 'a' || s
[0] == 'b' || s
[0] == 'c'));
2327 /* Exercise updates */
2328 dup2
= PySet_New(NULL
);
2329 assert(_PySet_Update(dup2
, dup
) == 0);
2330 assert(PySet_Size(dup2
) == 3);
2331 assert(_PySet_Update(dup2
, dup
) == 0);
2332 assert(PySet_Size(dup2
) == 3);
2335 /* Raise SystemError when self argument is not a set or frozenset. */
2337 assertRaises(PySet_Size(t
) == -1, PyExc_SystemError
);
2338 assertRaises(PySet_Contains(t
, elem
) == -1, PyExc_SystemError
);
2341 /* Raise SystemError when self argument is not a set. */
2342 f
= PyFrozenSet_New(dup
);
2343 assert(PySet_Size(f
) == 3);
2344 assert(PyFrozenSet_CheckExact(f
));
2345 assertRaises(PySet_Discard(f
, elem
) == -1, PyExc_SystemError
);
2346 assertRaises(PySet_Pop(f
) == NULL
, PyExc_SystemError
);
2349 /* Raise KeyError when popping from an empty set */
2350 assert(PyNumber_InPlaceSubtract(ob
, ob
) == ob
);
2352 assert(PySet_GET_SIZE(ob
) == 0);
2353 assertRaises(PySet_Pop(ob
) == NULL
, PyExc_KeyError
);
2355 /* Restore the set from the copy using the PyNumber API */
2356 assert(PyNumber_InPlaceOr(ob
, dup
) == ob
);
2359 /* Verify constructors accept NULL arguments */
2360 f
= PySet_New(NULL
);
2362 assert(PySet_GET_SIZE(f
) == 0);
2364 f
= PyFrozenSet_New(NULL
);
2366 assert(PyFrozenSet_CheckExact(f
));
2367 assert(PySet_GET_SIZE(f
) == 0);