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-6 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 #define MAXFREESETS 80
55 static PySetObject
*free_sets
[MAXFREESETS
];
56 static int num_free_sets
= 0;
59 The basic lookup function used by all operations.
60 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
61 Open addressing is preferred over chaining since the link overhead for
62 chaining would be substantial (100% with typical malloc overhead).
64 The initial probe index is computed as hash mod the table size. Subsequent
65 probe indices are computed as explained in Objects/dictobject.c.
67 All arithmetic on hash should ignore overflow.
69 Unlike the dictionary implementation, the lookkey functions can return
70 NULL if the rich comparison returns an error.
74 set_lookkey(PySetObject
*so
, PyObject
*key
, register long hash
)
76 register Py_ssize_t i
;
77 register size_t perturb
;
78 register setentry
*freeslot
;
79 register size_t mask
= so
->mask
;
80 setentry
*table
= so
->table
;
81 register setentry
*entry
;
87 if (entry
->key
== NULL
|| entry
->key
== key
)
90 if (entry
->key
== dummy
)
93 if (entry
->hash
== hash
) {
94 startkey
= entry
->key
;
95 cmp
= PyObject_RichCompareBool(startkey
, key
, Py_EQ
);
98 if (table
== so
->table
&& entry
->key
== startkey
) {
103 /* The compare did major nasty stuff to the
106 return set_lookkey(so
, key
, hash
);
112 /* In the loop, key == dummy is by far (factor of 100s) the
113 least likely outcome, so test for that last. */
114 for (perturb
= hash
; ; perturb
>>= PERTURB_SHIFT
) {
115 i
= (i
<< 2) + i
+ perturb
+ 1;
116 entry
= &table
[i
& mask
];
117 if (entry
->key
== NULL
) {
118 if (freeslot
!= NULL
)
122 if (entry
->key
== key
)
124 if (entry
->hash
== hash
&& entry
->key
!= dummy
) {
125 startkey
= entry
->key
;
126 cmp
= PyObject_RichCompareBool(startkey
, key
, Py_EQ
);
129 if (table
== so
->table
&& entry
->key
== startkey
) {
134 /* The compare did major nasty stuff to the
137 return set_lookkey(so
, key
, hash
);
140 else if (entry
->key
== dummy
&& freeslot
== NULL
)
147 * Hacked up version of set_lookkey which can assume keys are always strings;
148 * This means we can always use _PyString_Eq directly and not have to check to
149 * see if the comparison altered the table.
152 set_lookkey_string(PySetObject
*so
, PyObject
*key
, register long hash
)
154 register Py_ssize_t i
;
155 register size_t perturb
;
156 register setentry
*freeslot
;
157 register size_t mask
= so
->mask
;
158 setentry
*table
= so
->table
;
159 register setentry
*entry
;
161 /* Make sure this function doesn't have to handle non-string keys,
162 including subclasses of str; e.g., one reason to subclass
163 strings is to override __eq__, and for speed we don't cater to
165 if (!PyString_CheckExact(key
)) {
166 so
->lookup
= set_lookkey
;
167 return set_lookkey(so
, key
, hash
);
171 if (entry
->key
== NULL
|| entry
->key
== key
)
173 if (entry
->key
== dummy
)
176 if (entry
->hash
== hash
&& _PyString_Eq(entry
->key
, key
))
181 /* In the loop, key == dummy is by far (factor of 100s) the
182 least likely outcome, so test for that last. */
183 for (perturb
= hash
; ; perturb
>>= PERTURB_SHIFT
) {
184 i
= (i
<< 2) + i
+ perturb
+ 1;
185 entry
= &table
[i
& mask
];
186 if (entry
->key
== NULL
)
187 return freeslot
== NULL
? entry
: freeslot
;
188 if (entry
->key
== key
189 || (entry
->hash
== hash
190 && entry
->key
!= dummy
191 && _PyString_Eq(entry
->key
, key
)))
193 if (entry
->key
== dummy
&& freeslot
== NULL
)
196 assert(0); /* NOT REACHED */
201 Internal routine to insert a new key into the table.
202 Used by the public insert routine.
203 Eats a reference to key.
206 set_insert_key(register PySetObject
*so
, PyObject
*key
, long hash
)
208 register setentry
*entry
;
209 typedef setentry
*(*lookupfunc
)(PySetObject
*, PyObject
*, long);
211 assert(so
->lookup
!= NULL
);
212 entry
= so
->lookup(so
, key
, hash
);
215 if (entry
->key
== NULL
) {
221 } else if (entry
->key
== dummy
) {
235 Internal routine used by set_table_resize() to insert an item which is
236 known to be absent from the set. This routine also assumes that
237 the set contains no deleted entries. Besides the performance benefit,
238 using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
239 Note that no refcounts are changed by this routine; if needed, the caller
240 is responsible for incref'ing `key`.
243 set_insert_clean(register PySetObject
*so
, PyObject
*key
, long hash
)
246 register size_t perturb
;
247 register size_t mask
= (size_t)so
->mask
;
248 setentry
*table
= so
->table
;
249 register setentry
*entry
;
253 for (perturb
= hash
; entry
->key
!= NULL
; perturb
>>= PERTURB_SHIFT
) {
254 i
= (i
<< 2) + i
+ perturb
+ 1;
255 entry
= &table
[i
& mask
];
264 Restructure the table by allocating a new table and reinserting all
265 keys again. When entries have been deleted, the new table may
266 actually be smaller than the old one.
269 set_table_resize(PySetObject
*so
, Py_ssize_t minused
)
272 setentry
*oldtable
, *newtable
, *entry
;
274 int is_oldtable_malloced
;
275 setentry small_copy
[PySet_MINSIZE
];
277 assert(minused
>= 0);
279 /* Find the smallest table size > minused. */
280 for (newsize
= PySet_MINSIZE
;
281 newsize
<= minused
&& newsize
> 0;
289 /* Get space for a new table. */
290 oldtable
= so
->table
;
291 assert(oldtable
!= NULL
);
292 is_oldtable_malloced
= oldtable
!= so
->smalltable
;
294 if (newsize
== PySet_MINSIZE
) {
295 /* A large table is shrinking, or we can't get any smaller. */
296 newtable
= so
->smalltable
;
297 if (newtable
== oldtable
) {
298 if (so
->fill
== so
->used
) {
299 /* No dummies, so no point doing anything. */
302 /* We're not going to resize it, but rebuild the
303 table anyway to purge old dummy entries.
304 Subtle: This is *necessary* if fill==size,
305 as set_lookkey needs at least one virgin slot to
306 terminate failing searches. If fill < size, it's
307 merely desirable, as dummies slow searches. */
308 assert(so
->fill
> so
->used
);
309 memcpy(small_copy
, oldtable
, sizeof(small_copy
));
310 oldtable
= small_copy
;
314 newtable
= PyMem_NEW(setentry
, newsize
);
315 if (newtable
== NULL
) {
321 /* Make the set empty, using the new table. */
322 assert(newtable
!= oldtable
);
323 so
->table
= newtable
;
324 so
->mask
= newsize
- 1;
325 memset(newtable
, 0, sizeof(setentry
) * newsize
);
330 /* Copy the data over; this is refcount-neutral for active entries;
331 dummy entries aren't copied over, of course */
332 for (entry
= oldtable
; i
> 0; entry
++) {
333 if (entry
->key
== NULL
) {
336 } else if (entry
->key
== dummy
) {
339 assert(entry
->key
== dummy
);
340 Py_DECREF(entry
->key
);
344 set_insert_clean(so
, entry
->key
, entry
->hash
);
348 if (is_oldtable_malloced
)
353 /* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
356 set_add_entry(register PySetObject
*so
, setentry
*entry
)
358 register Py_ssize_t n_used
;
360 assert(so
->fill
<= so
->mask
); /* at least one empty slot */
362 Py_INCREF(entry
->key
);
363 if (set_insert_key(so
, entry
->key
, entry
->hash
) == -1) {
364 Py_DECREF(entry
->key
);
367 if (!(so
->used
> n_used
&& so
->fill
*3 >= (so
->mask
+1)*2))
369 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
373 set_add_key(register PySetObject
*so
, PyObject
*key
)
376 register Py_ssize_t n_used
;
378 if (!PyString_CheckExact(key
) ||
379 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
380 hash
= PyObject_Hash(key
);
384 assert(so
->fill
<= so
->mask
); /* at least one empty slot */
387 if (set_insert_key(so
, key
, hash
) == -1) {
391 if (!(so
->used
> n_used
&& so
->fill
*3 >= (so
->mask
+1)*2))
393 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
396 #define DISCARD_NOTFOUND 0
397 #define DISCARD_FOUND 1
400 set_discard_entry(PySetObject
*so
, setentry
*oldentry
)
401 { register setentry
*entry
;
404 entry
= (so
->lookup
)(so
, oldentry
->key
, oldentry
->hash
);
407 if (entry
->key
== NULL
|| entry
->key
== dummy
)
408 return DISCARD_NOTFOUND
;
409 old_key
= entry
->key
;
414 return DISCARD_FOUND
;
418 set_discard_key(PySetObject
*so
, PyObject
*key
)
421 register setentry
*entry
;
424 assert (PyAnySet_Check(so
));
425 if (!PyString_CheckExact(key
) ||
426 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
427 hash
= PyObject_Hash(key
);
431 entry
= (so
->lookup
)(so
, key
, hash
);
434 if (entry
->key
== NULL
|| entry
->key
== dummy
)
435 return DISCARD_NOTFOUND
;
436 old_key
= entry
->key
;
441 return DISCARD_FOUND
;
445 set_clear_internal(PySetObject
*so
)
447 setentry
*entry
, *table
;
448 int table_is_malloced
;
450 setentry small_copy
[PySet_MINSIZE
];
453 assert (PyAnySet_Check(so
));
460 assert(table
!= NULL
);
461 table_is_malloced
= table
!= so
->smalltable
;
463 /* This is delicate. During the process of clearing the set,
464 * decrefs can cause the set to mutate. To avoid fatal confusion
465 * (voice of experience), we have to make the set empty before
466 * clearing the slots, and never refer to anything via so->ref while
470 if (table_is_malloced
)
471 EMPTY_TO_MINSIZE(so
);
474 /* It's a small table with something that needs to be cleared.
475 * Afraid the only safe way is to copy the set entries into
476 * another small table first.
478 memcpy(small_copy
, table
, sizeof(small_copy
));
480 EMPTY_TO_MINSIZE(so
);
482 /* else it's a small table that's already empty */
484 /* Now we can finally clear things. If C had refcounts, we could
485 * assert that the refcount on table is 1 now, i.e. that this function
486 * has unique access to it, so decref side-effects can't alter it.
488 for (entry
= table
; fill
> 0; ++entry
) {
495 Py_DECREF(entry
->key
);
499 assert(entry
->key
== NULL
);
503 if (table_is_malloced
)
509 * Iterate over a set table. Use like so:
513 * pos = 0; # important! pos should not otherwise be changed by you
514 * while (set_next(yourset, &pos, &entry)) {
515 * Refer to borrowed reference in entry->key.
518 * CAUTION: In general, it isn't safe to use set_next in a loop that
522 set_next(PySetObject
*so
, Py_ssize_t
*pos_ptr
, setentry
**entry_ptr
)
526 register setentry
*table
;
528 assert (PyAnySet_Check(so
));
533 while (i
<= mask
&& (table
[i
].key
== NULL
|| table
[i
].key
== dummy
))
538 assert(table
[i
].key
!= NULL
);
539 *entry_ptr
= &table
[i
];
544 set_dealloc(PySetObject
*so
)
546 register setentry
*entry
;
547 Py_ssize_t fill
= so
->fill
;
548 PyObject_GC_UnTrack(so
);
549 Py_TRASHCAN_SAFE_BEGIN(so
)
550 if (so
->weakreflist
!= NULL
)
551 PyObject_ClearWeakRefs((PyObject
*) so
);
553 for (entry
= so
->table
; fill
> 0; entry
++) {
556 Py_DECREF(entry
->key
);
559 if (so
->table
!= so
->smalltable
)
560 PyMem_DEL(so
->table
);
561 if (num_free_sets
< MAXFREESETS
&& PyAnySet_CheckExact(so
))
562 free_sets
[num_free_sets
++] = so
;
564 so
->ob_type
->tp_free(so
);
565 Py_TRASHCAN_SAFE_END(so
)
569 set_tp_print(PySetObject
*so
, FILE *fp
, int flags
)
573 char *emit
= ""; /* No separator emitted on first pass */
574 char *separator
= ", ";
576 fprintf(fp
, "%s([", so
->ob_type
->tp_name
);
577 while (set_next(so
, &pos
, &entry
)) {
580 if (PyObject_Print(entry
->key
, fp
, 0) != 0)
588 set_repr(PySetObject
*so
)
590 PyObject
*keys
, *result
, *listrepr
;
592 keys
= PySequence_List((PyObject
*)so
);
595 listrepr
= PyObject_Repr(keys
);
597 if (listrepr
== NULL
)
600 result
= PyString_FromFormat("%s(%s)", so
->ob_type
->tp_name
,
601 PyString_AS_STRING(listrepr
));
607 set_len(PyObject
*so
)
609 return ((PySetObject
*)so
)->used
;
613 set_merge(PySetObject
*so
, PyObject
*otherset
)
616 register Py_ssize_t i
;
617 register setentry
*entry
;
619 assert (PyAnySet_Check(so
));
620 assert (PyAnySet_Check(otherset
));
622 other
= (PySetObject
*)otherset
;
623 if (other
== so
|| other
->used
== 0)
624 /* a.update(a) or a.update({}); nothing to do */
626 /* Do one big resize at the start, rather than
627 * incrementally resizing as we insert new keys. Expect
628 * that there will be no (or few) overlapping keys.
630 if ((so
->fill
+ other
->used
)*3 >= (so
->mask
+1)*2) {
631 if (set_table_resize(so
, (so
->used
+ other
->used
)*2) != 0)
634 for (i
= 0; i
<= other
->mask
; i
++) {
635 entry
= &other
->table
[i
];
636 if (entry
->key
!= NULL
&&
637 entry
->key
!= dummy
) {
638 Py_INCREF(entry
->key
);
639 if (set_insert_key(so
, entry
->key
, entry
->hash
) == -1) {
640 Py_DECREF(entry
->key
);
649 set_contains_key(PySetObject
*so
, PyObject
*key
)
654 if (!PyString_CheckExact(key
) ||
655 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
656 hash
= PyObject_Hash(key
);
660 entry
= (so
->lookup
)(so
, key
, hash
);
664 return key
!= NULL
&& key
!= dummy
;
668 set_contains_entry(PySetObject
*so
, setentry
*entry
)
673 lu_entry
= (so
->lookup
)(so
, entry
->key
, entry
->hash
);
674 if (lu_entry
== NULL
)
677 return key
!= NULL
&& key
!= dummy
;
681 set_pop(PySetObject
*so
)
683 register Py_ssize_t i
= 0;
684 register setentry
*entry
;
687 assert (PyAnySet_Check(so
));
689 PyErr_SetString(PyExc_KeyError
, "pop from an empty set");
693 /* Set entry to "the first" unused or dummy set entry. We abuse
694 * the hash field of slot 0 to hold a search finger:
695 * If slot 0 has a value, use slot 0.
696 * Else slot 0 is being used to hold a search finger,
697 * and we use its hash value as the first index to look.
699 entry
= &so
->table
[0];
700 if (entry
->key
== NULL
|| entry
->key
== dummy
) {
702 /* The hash field may be a real hash value, or it may be a
703 * legit search finger, or it may be a once-legit search
704 * finger that's out of bounds now because it wrapped around
705 * or the table shrunk -- simply make sure it's in bounds now.
707 if (i
> so
->mask
|| i
< 1)
708 i
= 1; /* skip slot 0 */
709 while ((entry
= &so
->table
[i
])->key
== NULL
|| entry
->key
==dummy
) {
719 so
->table
[0].hash
= i
+ 1; /* next place to start */
723 PyDoc_STRVAR(pop_doc
, "Remove and return an arbitrary set element.");
726 set_traverse(PySetObject
*so
, visitproc visit
, void *arg
)
731 while (set_next(so
, &pos
, &entry
))
732 Py_VISIT(entry
->key
);
737 frozenset_hash(PyObject
*self
)
739 PySetObject
*so
= (PySetObject
*)self
;
740 long h
, hash
= 1927868237L;
747 hash
*= PySet_GET_SIZE(self
) + 1;
748 while (set_next(so
, &pos
, &entry
)) {
749 /* Work to increase the bit dispersion for closely spaced hash
750 values. The is important because some use cases have many
751 combinations of a small number of elements with nearby
752 hashes so that many distinct combinations collapse to only
753 a handful of distinct hash values. */
755 hash
^= (h
^ (h
<< 16) ^ 89869747L) * 3644798167u;
757 hash
= hash
* 69069L + 907133923L;
765 set_nohash(PyObject
*self
)
767 PyErr_SetString(PyExc_TypeError
, "set objects are unhashable");
771 /***** Set iterator type ***********************************************/
775 PySetObject
*si_set
; /* Set to NULL when iterator is exhausted */
782 setiter_dealloc(setiterobject
*si
)
784 Py_XDECREF(si
->si_set
);
789 setiter_len(setiterobject
*si
)
792 if (si
->si_set
!= NULL
&& si
->si_used
== si
->si_set
->used
)
794 return PyInt_FromLong(len
);
797 PyDoc_STRVAR(length_hint_doc
, "Private method returning an estimate of len(list(it)).");
799 static PyMethodDef setiter_methods
[] = {
800 {"__length_hint__", (PyCFunction
)setiter_len
, METH_NOARGS
, length_hint_doc
},
801 {NULL
, NULL
} /* sentinel */
804 static PyObject
*setiter_iternext(setiterobject
*si
)
807 register Py_ssize_t i
, mask
;
808 register setentry
*entry
;
809 PySetObject
*so
= si
->si_set
;
813 assert (PyAnySet_Check(so
));
815 if (si
->si_used
!= so
->used
) {
816 PyErr_SetString(PyExc_RuntimeError
,
817 "Set changed size during iteration");
818 si
->si_used
= -1; /* Make this state sticky */
826 while (i
<= mask
&& (entry
[i
].key
== NULL
|| entry
[i
].key
== dummy
))
842 static PyTypeObject PySetIter_Type
= {
843 PyObject_HEAD_INIT(&PyType_Type
)
845 "setiterator", /* tp_name */
846 sizeof(setiterobject
), /* tp_basicsize */
849 (destructor
)setiter_dealloc
, /* tp_dealloc */
855 0, /* tp_as_number */
856 0, /* tp_as_sequence */
857 0, /* tp_as_mapping */
861 PyObject_GenericGetAttr
, /* tp_getattro */
863 0, /* tp_as_buffer */
864 Py_TPFLAGS_DEFAULT
, /* tp_flags */
868 0, /* tp_richcompare */
869 0, /* tp_weaklistoffset */
870 PyObject_SelfIter
, /* tp_iter */
871 (iternextfunc
)setiter_iternext
, /* tp_iternext */
872 setiter_methods
, /* tp_methods */
877 set_iter(PySetObject
*so
)
879 setiterobject
*si
= PyObject_New(setiterobject
, &PySetIter_Type
);
884 si
->si_used
= so
->used
;
887 return (PyObject
*)si
;
891 set_update_internal(PySetObject
*so
, PyObject
*other
)
895 if (PyAnySet_Check(other
))
896 return set_merge(so
, other
);
898 if (PyDict_Check(other
)) {
901 while (PyDict_Next(other
, &pos
, &key
, &value
)) {
902 if (set_add_key(so
, key
) == -1)
908 it
= PyObject_GetIter(other
);
912 while ((key
= PyIter_Next(it
)) != NULL
) {
913 if (set_add_key(so
, key
) == -1) {
921 if (PyErr_Occurred())
927 set_update(PySetObject
*so
, PyObject
*other
)
929 if (set_update_internal(so
, other
) == -1)
934 PyDoc_STRVAR(update_doc
,
935 "Update a set with the union of itself and another.");
938 make_new_set(PyTypeObject
*type
, PyObject
*iterable
)
940 register PySetObject
*so
= NULL
;
942 if (dummy
== NULL
) { /* Auto-initialize dummy */
943 dummy
= PyString_FromString("<dummy key>");
948 /* create PySetObject structure */
950 (type
== &PySet_Type
|| type
== &PyFrozenSet_Type
)) {
951 so
= free_sets
[--num_free_sets
];
952 assert (so
!= NULL
&& PyAnySet_CheckExact(so
));
954 _Py_NewReference((PyObject
*)so
);
955 EMPTY_TO_MINSIZE(so
);
956 PyObject_GC_Track(so
);
958 so
= (PySetObject
*)type
->tp_alloc(type
, 0);
961 /* tp_alloc has already zeroed the structure */
962 assert(so
->table
== NULL
&& so
->fill
== 0 && so
->used
== 0);
963 INIT_NONZERO_SET_SLOTS(so
);
966 so
->lookup
= set_lookkey_string
;
967 so
->weakreflist
= NULL
;
969 if (iterable
!= NULL
) {
970 if (set_update_internal(so
, iterable
) == -1) {
976 return (PyObject
*)so
;
979 /* The empty frozenset is a singleton */
980 static PyObject
*emptyfrozenset
= NULL
;
983 frozenset_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
985 PyObject
*iterable
= NULL
, *result
;
987 if (!_PyArg_NoKeywords("frozenset()", kwds
))
990 if (!PyArg_UnpackTuple(args
, type
->tp_name
, 0, 1, &iterable
))
993 if (type
!= &PyFrozenSet_Type
)
994 return make_new_set(type
, iterable
);
996 if (iterable
!= NULL
) {
997 /* frozenset(f) is idempotent */
998 if (PyFrozenSet_CheckExact(iterable
)) {
1002 result
= make_new_set(type
, iterable
);
1003 if (result
== NULL
|| PySet_GET_SIZE(result
))
1007 /* The empty frozenset is a singleton */
1008 if (emptyfrozenset
== NULL
)
1009 emptyfrozenset
= make_new_set(type
, NULL
);
1010 Py_XINCREF(emptyfrozenset
);
1011 return emptyfrozenset
;
1019 while (num_free_sets
) {
1021 so
= free_sets
[num_free_sets
];
1022 PyObject_GC_Del(so
);
1025 Py_CLEAR(emptyfrozenset
);
1029 set_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1031 if (!_PyArg_NoKeywords("set()", kwds
))
1034 return make_new_set(type
, NULL
);
1037 /* set_swap_bodies() switches the contents of any two sets by moving their
1038 internal data pointers and, if needed, copying the internal smalltables.
1039 Semantically equivalent to:
1041 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1043 The function always succeeds and it leaves both objects in a stable state.
1044 Useful for creating temporary frozensets from sets for membership testing
1045 in __contains__(), discard(), and remove(). Also useful for operations
1046 that update in-place (by allowing an intermediate result to be swapped
1047 into one of the original inputs).
1051 set_swap_bodies(PySetObject
*a
, PySetObject
*b
)
1055 setentry
*(*f
)(PySetObject
*so
, PyObject
*key
, long hash
);
1056 setentry tab
[PySet_MINSIZE
];
1059 t
= a
->fill
; a
->fill
= b
->fill
; b
->fill
= t
;
1060 t
= a
->used
; a
->used
= b
->used
; b
->used
= t
;
1061 t
= a
->mask
; a
->mask
= b
->mask
; b
->mask
= t
;
1064 if (a
->table
== a
->smalltable
)
1066 a
->table
= b
->table
;
1067 if (b
->table
== b
->smalltable
)
1068 a
->table
= a
->smalltable
;
1071 f
= a
->lookup
; a
->lookup
= b
->lookup
; b
->lookup
= f
;
1073 if (a
->table
== a
->smalltable
|| b
->table
== b
->smalltable
) {
1074 memcpy(tab
, a
->smalltable
, sizeof(tab
));
1075 memcpy(a
->smalltable
, b
->smalltable
, sizeof(tab
));
1076 memcpy(b
->smalltable
, tab
, sizeof(tab
));
1079 if (PyType_IsSubtype(a
->ob_type
, &PyFrozenSet_Type
) &&
1080 PyType_IsSubtype(b
->ob_type
, &PyFrozenSet_Type
)) {
1081 h
= a
->hash
; a
->hash
= b
->hash
; b
->hash
= h
;
1089 set_copy(PySetObject
*so
)
1091 return make_new_set(so
->ob_type
, (PyObject
*)so
);
1095 frozenset_copy(PySetObject
*so
)
1097 if (PyFrozenSet_CheckExact(so
)) {
1099 return (PyObject
*)so
;
1101 return set_copy(so
);
1104 PyDoc_STRVAR(copy_doc
, "Return a shallow copy of a set.");
1107 set_clear(PySetObject
*so
)
1109 set_clear_internal(so
);
1113 PyDoc_STRVAR(clear_doc
, "Remove all elements from this set.");
1116 set_union(PySetObject
*so
, PyObject
*other
)
1118 PySetObject
*result
;
1120 result
= (PySetObject
*)set_copy(so
);
1123 if ((PyObject
*)so
== other
)
1124 return (PyObject
*)result
;
1125 if (set_update_internal(result
, other
) == -1) {
1129 return (PyObject
*)result
;
1132 PyDoc_STRVAR(union_doc
,
1133 "Return the union of two sets as a new set.\n\
1135 (i.e. all elements that are in either set.)");
1138 set_or(PySetObject
*so
, PyObject
*other
)
1140 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1141 Py_INCREF(Py_NotImplemented
);
1142 return Py_NotImplemented
;
1144 return set_union(so
, other
);
1148 set_ior(PySetObject
*so
, PyObject
*other
)
1150 if (!PyAnySet_Check(other
)) {
1151 Py_INCREF(Py_NotImplemented
);
1152 return Py_NotImplemented
;
1154 if (set_update_internal(so
, other
) == -1)
1157 return (PyObject
*)so
;
1161 set_intersection(PySetObject
*so
, PyObject
*other
)
1163 PySetObject
*result
;
1164 PyObject
*key
, *it
, *tmp
;
1166 if ((PyObject
*)so
== other
)
1167 return set_copy(so
);
1169 result
= (PySetObject
*)make_new_set(so
->ob_type
, NULL
);
1173 if (PyAnySet_Check(other
)) {
1177 if (PySet_GET_SIZE(other
) > PySet_GET_SIZE(so
)) {
1178 tmp
= (PyObject
*)so
;
1179 so
= (PySetObject
*)other
;
1183 while (set_next((PySetObject
*)other
, &pos
, &entry
)) {
1184 int rv
= set_contains_entry(so
, entry
);
1190 if (set_add_entry(result
, entry
) == -1) {
1196 return (PyObject
*)result
;
1199 it
= PyObject_GetIter(other
);
1205 while ((key
= PyIter_Next(it
)) != NULL
) {
1208 long hash
= PyObject_Hash(key
);
1218 rv
= set_contains_entry(so
, &entry
);
1226 if (set_add_entry(result
, &entry
) == -1) {
1236 if (PyErr_Occurred()) {
1240 return (PyObject
*)result
;
1243 PyDoc_STRVAR(intersection_doc
,
1244 "Return the intersection of two sets as a new set.\n\
1246 (i.e. all elements that are in both sets.)");
1249 set_intersection_update(PySetObject
*so
, PyObject
*other
)
1253 tmp
= set_intersection(so
, other
);
1256 set_swap_bodies(so
, (PySetObject
*)tmp
);
1261 PyDoc_STRVAR(intersection_update_doc
,
1262 "Update a set with the intersection of itself and another.");
1265 set_and(PySetObject
*so
, PyObject
*other
)
1267 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1268 Py_INCREF(Py_NotImplemented
);
1269 return Py_NotImplemented
;
1271 return set_intersection(so
, other
);
1275 set_iand(PySetObject
*so
, PyObject
*other
)
1279 if (!PyAnySet_Check(other
)) {
1280 Py_INCREF(Py_NotImplemented
);
1281 return Py_NotImplemented
;
1283 result
= set_intersection_update(so
, other
);
1288 return (PyObject
*)so
;
1292 set_difference_update_internal(PySetObject
*so
, PyObject
*other
)
1294 if ((PyObject
*)so
== other
)
1295 return set_clear_internal(so
);
1297 if (PyAnySet_Check(other
)) {
1301 while (set_next((PySetObject
*)other
, &pos
, &entry
))
1302 if (set_discard_entry(so
, entry
) == -1)
1306 it
= PyObject_GetIter(other
);
1310 while ((key
= PyIter_Next(it
)) != NULL
) {
1311 if (set_discard_key(so
, key
) == -1) {
1319 if (PyErr_Occurred())
1322 /* If more than 1/5 are dummies, then resize them away. */
1323 if ((so
->fill
- so
->used
) * 5 < so
->mask
)
1325 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
1329 set_difference_update(PySetObject
*so
, PyObject
*other
)
1331 if (set_difference_update_internal(so
, other
) != -1)
1336 PyDoc_STRVAR(difference_update_doc
,
1337 "Remove all elements of another set from this set.");
1340 set_difference(PySetObject
*so
, PyObject
*other
)
1346 if (!PyAnySet_Check(other
) && !PyDict_Check(other
)) {
1347 result
= set_copy(so
);
1350 if (set_difference_update_internal((PySetObject
*)result
, other
) != -1)
1356 result
= make_new_set(so
->ob_type
, NULL
);
1360 if (PyDict_Check(other
)) {
1361 while (set_next(so
, &pos
, &entry
)) {
1363 entrycopy
.hash
= entry
->hash
;
1364 entrycopy
.key
= entry
->key
;
1365 if (!PyDict_Contains(other
, entry
->key
)) {
1366 if (set_add_entry((PySetObject
*)result
, &entrycopy
) == -1) {
1375 while (set_next(so
, &pos
, &entry
)) {
1376 int rv
= set_contains_entry((PySetObject
*)other
, entry
);
1382 if (set_add_entry((PySetObject
*)result
, entry
) == -1) {
1391 PyDoc_STRVAR(difference_doc
,
1392 "Return the difference of two sets as a new set.\n\
1394 (i.e. all elements that are in this set but not the other.)");
1396 set_sub(PySetObject
*so
, PyObject
*other
)
1398 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1399 Py_INCREF(Py_NotImplemented
);
1400 return Py_NotImplemented
;
1402 return set_difference(so
, other
);
1406 set_isub(PySetObject
*so
, PyObject
*other
)
1410 if (!PyAnySet_Check(other
)) {
1411 Py_INCREF(Py_NotImplemented
);
1412 return Py_NotImplemented
;
1414 result
= set_difference_update(so
, other
);
1419 return (PyObject
*)so
;
1423 set_symmetric_difference_update(PySetObject
*so
, PyObject
*other
)
1425 PySetObject
*otherset
;
1430 if ((PyObject
*)so
== other
)
1431 return set_clear(so
);
1433 if (PyDict_Check(other
)) {
1436 while (PyDict_Next(other
, &pos
, &key
, &value
)) {
1438 long hash
= PyObject_Hash(key
);
1442 an_entry
.hash
= hash
;
1444 rv
= set_discard_entry(so
, &an_entry
);
1447 if (rv
== DISCARD_NOTFOUND
) {
1448 if (set_add_entry(so
, &an_entry
) == -1)
1455 if (PyAnySet_Check(other
)) {
1457 otherset
= (PySetObject
*)other
;
1459 otherset
= (PySetObject
*)make_new_set(so
->ob_type
, other
);
1460 if (otherset
== NULL
)
1464 while (set_next(otherset
, &pos
, &entry
)) {
1465 int rv
= set_discard_entry(so
, entry
);
1467 Py_DECREF(otherset
);
1470 if (rv
== DISCARD_NOTFOUND
) {
1471 if (set_add_entry(so
, entry
) == -1) {
1472 Py_DECREF(otherset
);
1477 Py_DECREF(otherset
);
1481 PyDoc_STRVAR(symmetric_difference_update_doc
,
1482 "Update a set with the symmetric difference of itself and another.");
1485 set_symmetric_difference(PySetObject
*so
, PyObject
*other
)
1488 PySetObject
*otherset
;
1490 otherset
= (PySetObject
*)make_new_set(so
->ob_type
, other
);
1491 if (otherset
== NULL
)
1493 rv
= set_symmetric_difference_update(otherset
, (PyObject
*)so
);
1497 return (PyObject
*)otherset
;
1500 PyDoc_STRVAR(symmetric_difference_doc
,
1501 "Return the symmetric difference of two sets as a new set.\n\
1503 (i.e. all elements that are in exactly one of the sets.)");
1506 set_xor(PySetObject
*so
, PyObject
*other
)
1508 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1509 Py_INCREF(Py_NotImplemented
);
1510 return Py_NotImplemented
;
1512 return set_symmetric_difference(so
, other
);
1516 set_ixor(PySetObject
*so
, PyObject
*other
)
1520 if (!PyAnySet_Check(other
)) {
1521 Py_INCREF(Py_NotImplemented
);
1522 return Py_NotImplemented
;
1524 result
= set_symmetric_difference_update(so
, other
);
1529 return (PyObject
*)so
;
1533 set_issubset(PySetObject
*so
, PyObject
*other
)
1538 if (!PyAnySet_Check(other
)) {
1539 PyObject
*tmp
, *result
;
1540 tmp
= make_new_set(&PySet_Type
, other
);
1543 result
= set_issubset(so
, tmp
);
1547 if (PySet_GET_SIZE(so
) > PySet_GET_SIZE(other
))
1550 while (set_next(so
, &pos
, &entry
)) {
1551 int rv
= set_contains_entry((PySetObject
*)other
, entry
);
1560 PyDoc_STRVAR(issubset_doc
, "Report whether another set contains this set.");
1563 set_issuperset(PySetObject
*so
, PyObject
*other
)
1565 PyObject
*tmp
, *result
;
1567 if (!PyAnySet_Check(other
)) {
1568 tmp
= make_new_set(&PySet_Type
, other
);
1571 result
= set_issuperset(so
, tmp
);
1575 return set_issubset((PySetObject
*)other
, (PyObject
*)so
);
1578 PyDoc_STRVAR(issuperset_doc
, "Report whether this set contains another set.");
1581 set_richcompare(PySetObject
*v
, PyObject
*w
, int op
)
1585 if(!PyAnySet_Check(w
)) {
1590 PyErr_SetString(PyExc_TypeError
, "can only compare to a set");
1595 if (PySet_GET_SIZE(v
) != PySet_GET_SIZE(w
))
1597 if (v
->hash
!= -1 &&
1598 ((PySetObject
*)w
)->hash
!= -1 &&
1599 v
->hash
!= ((PySetObject
*)w
)->hash
)
1601 return set_issubset(v
, w
);
1603 r1
= set_richcompare(v
, w
, Py_EQ
);
1606 r2
= PyBool_FromLong(PyObject_Not(r1
));
1610 return set_issubset(v
, w
);
1612 return set_issuperset(v
, w
);
1614 if (PySet_GET_SIZE(v
) >= PySet_GET_SIZE(w
))
1616 return set_issubset(v
, w
);
1618 if (PySet_GET_SIZE(v
) <= PySet_GET_SIZE(w
))
1620 return set_issuperset(v
, w
);
1622 Py_INCREF(Py_NotImplemented
);
1623 return Py_NotImplemented
;
1627 set_nocmp(PyObject
*self
, PyObject
*other
)
1629 PyErr_SetString(PyExc_TypeError
, "cannot compare sets using cmp()");
1634 set_add(PySetObject
*so
, PyObject
*key
)
1636 if (set_add_key(so
, key
) == -1)
1641 PyDoc_STRVAR(add_doc
,
1642 "Add an element to a set.\n\
1644 This has no effect if the element is already present.");
1647 set_contains(PySetObject
*so
, PyObject
*key
)
1652 rv
= set_contains_key(so
, key
);
1654 if (!PyAnySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1657 tmpkey
= make_new_set(&PyFrozenSet_Type
, NULL
);
1660 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1661 rv
= set_contains(so
, tmpkey
);
1662 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1669 set_direct_contains(PySetObject
*so
, PyObject
*key
)
1673 result
= set_contains(so
, key
);
1676 return PyBool_FromLong(result
);
1679 PyDoc_STRVAR(contains_doc
, "x.__contains__(y) <==> y in x.");
1682 set_remove(PySetObject
*so
, PyObject
*key
)
1684 PyObject
*tmpkey
, *result
;
1687 rv
= set_discard_key(so
, key
);
1689 if (!PyAnySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1692 tmpkey
= make_new_set(&PyFrozenSet_Type
, NULL
);
1695 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1696 result
= set_remove(so
, tmpkey
);
1697 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1700 } else if (rv
== DISCARD_NOTFOUND
) {
1707 PyDoc_STRVAR(remove_doc
,
1708 "Remove an element from a set; it must be a member.\n\
1710 If the element is not a member, raise a KeyError.");
1713 set_discard(PySetObject
*so
, PyObject
*key
)
1715 PyObject
*tmpkey
, *result
;
1718 rv
= set_discard_key(so
, key
);
1720 if (!PyAnySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1723 tmpkey
= make_new_set(&PyFrozenSet_Type
, NULL
);
1726 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1727 result
= set_discard(so
, tmpkey
);
1728 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1735 PyDoc_STRVAR(discard_doc
,
1736 "Remove an element from a set if it is a member.\n\
1738 If the element is not a member, do nothing.");
1741 set_reduce(PySetObject
*so
)
1743 PyObject
*keys
=NULL
, *args
=NULL
, *result
=NULL
, *dict
=NULL
;
1745 keys
= PySequence_List((PyObject
*)so
);
1748 args
= PyTuple_Pack(1, keys
);
1751 dict
= PyObject_GetAttrString((PyObject
*)so
, "__dict__");
1757 result
= PyTuple_Pack(3, so
->ob_type
, args
, dict
);
1765 PyDoc_STRVAR(reduce_doc
, "Return state information for pickling.");
1768 set_init(PySetObject
*self
, PyObject
*args
, PyObject
*kwds
)
1770 PyObject
*iterable
= NULL
;
1772 if (!PyAnySet_Check(self
))
1774 if (!PyArg_UnpackTuple(args
, self
->ob_type
->tp_name
, 0, 1, &iterable
))
1776 set_clear_internal(self
);
1778 if (iterable
== NULL
)
1780 return set_update_internal(self
, iterable
);
1783 static PySequenceMethods set_as_sequence
= {
1784 set_len
, /* sq_length */
1789 0, /* sq_ass_item */
1790 0, /* sq_ass_slice */
1791 (objobjproc
)set_contains
, /* sq_contains */
1794 /* set object ********************************************************/
1797 static PyObject
*test_c_api(PySetObject
*so
);
1799 PyDoc_STRVAR(test_c_api_doc
, "Exercises C API. Returns True.\n\
1800 All is well if assertions don't fail.");
1803 static PyMethodDef set_methods
[] = {
1804 {"add", (PyCFunction
)set_add
, METH_O
,
1806 {"clear", (PyCFunction
)set_clear
, METH_NOARGS
,
1808 {"__contains__",(PyCFunction
)set_direct_contains
, METH_O
| METH_COEXIST
,
1810 {"copy", (PyCFunction
)set_copy
, METH_NOARGS
,
1812 {"discard", (PyCFunction
)set_discard
, METH_O
,
1814 {"difference", (PyCFunction
)set_difference
, METH_O
,
1816 {"difference_update", (PyCFunction
)set_difference_update
, METH_O
,
1817 difference_update_doc
},
1818 {"intersection",(PyCFunction
)set_intersection
, METH_O
,
1820 {"intersection_update",(PyCFunction
)set_intersection_update
, METH_O
,
1821 intersection_update_doc
},
1822 {"issubset", (PyCFunction
)set_issubset
, METH_O
,
1824 {"issuperset", (PyCFunction
)set_issuperset
, METH_O
,
1826 {"pop", (PyCFunction
)set_pop
, METH_NOARGS
,
1828 {"__reduce__", (PyCFunction
)set_reduce
, METH_NOARGS
,
1830 {"remove", (PyCFunction
)set_remove
, METH_O
,
1832 {"symmetric_difference",(PyCFunction
)set_symmetric_difference
, METH_O
,
1833 symmetric_difference_doc
},
1834 {"symmetric_difference_update",(PyCFunction
)set_symmetric_difference_update
, METH_O
,
1835 symmetric_difference_update_doc
},
1837 {"test_c_api", (PyCFunction
)test_c_api
, METH_NOARGS
,
1840 {"union", (PyCFunction
)set_union
, METH_O
,
1842 {"update", (PyCFunction
)set_update
, METH_O
,
1844 {NULL
, NULL
} /* sentinel */
1847 static PyNumberMethods set_as_number
= {
1849 (binaryfunc
)set_sub
, /*nb_subtract*/
1862 (binaryfunc
)set_and
, /*nb_and*/
1863 (binaryfunc
)set_xor
, /*nb_xor*/
1864 (binaryfunc
)set_or
, /*nb_or*/
1871 0, /*nb_inplace_add*/
1872 (binaryfunc
)set_isub
, /*nb_inplace_subtract*/
1873 0, /*nb_inplace_multiply*/
1874 0, /*nb_inplace_divide*/
1875 0, /*nb_inplace_remainder*/
1876 0, /*nb_inplace_power*/
1877 0, /*nb_inplace_lshift*/
1878 0, /*nb_inplace_rshift*/
1879 (binaryfunc
)set_iand
, /*nb_inplace_and*/
1880 (binaryfunc
)set_ixor
, /*nb_inplace_xor*/
1881 (binaryfunc
)set_ior
, /*nb_inplace_or*/
1884 PyDoc_STRVAR(set_doc
,
1885 "set(iterable) --> set object\n\
1887 Build an unordered collection of unique elements.");
1889 PyTypeObject PySet_Type
= {
1890 PyObject_HEAD_INIT(&PyType_Type
)
1892 "set", /* tp_name */
1893 sizeof(PySetObject
), /* tp_basicsize */
1894 0, /* tp_itemsize */
1896 (destructor
)set_dealloc
, /* tp_dealloc */
1897 (printfunc
)set_tp_print
, /* tp_print */
1900 set_nocmp
, /* tp_compare */
1901 (reprfunc
)set_repr
, /* tp_repr */
1902 &set_as_number
, /* tp_as_number */
1903 &set_as_sequence
, /* tp_as_sequence */
1904 0, /* tp_as_mapping */
1905 set_nohash
, /* tp_hash */
1908 PyObject_GenericGetAttr
, /* tp_getattro */
1909 0, /* tp_setattro */
1910 0, /* tp_as_buffer */
1911 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
| Py_TPFLAGS_CHECKTYPES
|
1912 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1913 set_doc
, /* tp_doc */
1914 (traverseproc
)set_traverse
, /* tp_traverse */
1915 (inquiry
)set_clear_internal
, /* tp_clear */
1916 (richcmpfunc
)set_richcompare
, /* tp_richcompare */
1917 offsetof(PySetObject
, weakreflist
), /* tp_weaklistoffset */
1918 (getiterfunc
)set_iter
, /* tp_iter */
1919 0, /* tp_iternext */
1920 set_methods
, /* tp_methods */
1925 0, /* tp_descr_get */
1926 0, /* tp_descr_set */
1927 0, /* tp_dictoffset */
1928 (initproc
)set_init
, /* tp_init */
1929 PyType_GenericAlloc
, /* tp_alloc */
1930 set_new
, /* tp_new */
1931 PyObject_GC_Del
, /* tp_free */
1934 /* frozenset object ********************************************************/
1937 static PyMethodDef frozenset_methods
[] = {
1938 {"__contains__",(PyCFunction
)set_direct_contains
, METH_O
| METH_COEXIST
,
1940 {"copy", (PyCFunction
)frozenset_copy
, METH_NOARGS
,
1942 {"difference", (PyCFunction
)set_difference
, METH_O
,
1944 {"intersection",(PyCFunction
)set_intersection
, METH_O
,
1946 {"issubset", (PyCFunction
)set_issubset
, METH_O
,
1948 {"issuperset", (PyCFunction
)set_issuperset
, METH_O
,
1950 {"__reduce__", (PyCFunction
)set_reduce
, METH_NOARGS
,
1952 {"symmetric_difference",(PyCFunction
)set_symmetric_difference
, METH_O
,
1953 symmetric_difference_doc
},
1954 {"union", (PyCFunction
)set_union
, METH_O
,
1956 {NULL
, NULL
} /* sentinel */
1959 static PyNumberMethods frozenset_as_number
= {
1961 (binaryfunc
)set_sub
, /*nb_subtract*/
1974 (binaryfunc
)set_and
, /*nb_and*/
1975 (binaryfunc
)set_xor
, /*nb_xor*/
1976 (binaryfunc
)set_or
, /*nb_or*/
1979 PyDoc_STRVAR(frozenset_doc
,
1980 "frozenset(iterable) --> frozenset object\n\
1982 Build an immutable unordered collection of unique elements.");
1984 PyTypeObject PyFrozenSet_Type
= {
1985 PyObject_HEAD_INIT(&PyType_Type
)
1987 "frozenset", /* tp_name */
1988 sizeof(PySetObject
), /* tp_basicsize */
1989 0, /* tp_itemsize */
1991 (destructor
)set_dealloc
, /* tp_dealloc */
1992 (printfunc
)set_tp_print
, /* tp_print */
1995 set_nocmp
, /* tp_compare */
1996 (reprfunc
)set_repr
, /* tp_repr */
1997 &frozenset_as_number
, /* tp_as_number */
1998 &set_as_sequence
, /* tp_as_sequence */
1999 0, /* tp_as_mapping */
2000 frozenset_hash
, /* tp_hash */
2003 PyObject_GenericGetAttr
, /* tp_getattro */
2004 0, /* tp_setattro */
2005 0, /* tp_as_buffer */
2006 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
| Py_TPFLAGS_CHECKTYPES
|
2007 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2008 frozenset_doc
, /* tp_doc */
2009 (traverseproc
)set_traverse
, /* tp_traverse */
2010 (inquiry
)set_clear_internal
, /* tp_clear */
2011 (richcmpfunc
)set_richcompare
, /* tp_richcompare */
2012 offsetof(PySetObject
, weakreflist
), /* tp_weaklistoffset */
2013 (getiterfunc
)set_iter
, /* tp_iter */
2014 0, /* tp_iternext */
2015 frozenset_methods
, /* tp_methods */
2020 0, /* tp_descr_get */
2021 0, /* tp_descr_set */
2022 0, /* tp_dictoffset */
2024 PyType_GenericAlloc
, /* tp_alloc */
2025 frozenset_new
, /* tp_new */
2026 PyObject_GC_Del
, /* tp_free */
2030 /***** C API functions *************************************************/
2033 PySet_New(PyObject
*iterable
)
2035 return make_new_set(&PySet_Type
, iterable
);
2039 PyFrozenSet_New(PyObject
*iterable
)
2041 PyObject
*args
, *result
;
2043 if (iterable
== NULL
)
2044 args
= PyTuple_New(0);
2046 args
= PyTuple_Pack(1, iterable
);
2049 result
= frozenset_new(&PyFrozenSet_Type
, args
, NULL
);
2055 PySet_Size(PyObject
*anyset
)
2057 if (!PyAnySet_Check(anyset
)) {
2058 PyErr_BadInternalCall();
2061 return PySet_GET_SIZE(anyset
);
2065 PySet_Clear(PyObject
*set
)
2067 if (!PyType_IsSubtype(set
->ob_type
, &PySet_Type
)) {
2068 PyErr_BadInternalCall();
2071 return set_clear_internal((PySetObject
*)set
);
2075 PySet_Contains(PyObject
*anyset
, PyObject
*key
)
2077 if (!PyAnySet_Check(anyset
)) {
2078 PyErr_BadInternalCall();
2081 return set_contains_key((PySetObject
*)anyset
, key
);
2085 PySet_Discard(PyObject
*set
, PyObject
*key
)
2087 if (!PyType_IsSubtype(set
->ob_type
, &PySet_Type
)) {
2088 PyErr_BadInternalCall();
2091 return set_discard_key((PySetObject
*)set
, key
);
2095 PySet_Add(PyObject
*set
, PyObject
*key
)
2097 if (!PyType_IsSubtype(set
->ob_type
, &PySet_Type
)) {
2098 PyErr_BadInternalCall();
2101 return set_add_key((PySetObject
*)set
, key
);
2105 _PySet_Next(PyObject
*set
, Py_ssize_t
*pos
, PyObject
**entry
)
2107 setentry
*entry_ptr
;
2109 if (!PyAnySet_Check(set
)) {
2110 PyErr_BadInternalCall();
2113 if (set_next((PySetObject
*)set
, pos
, &entry_ptr
) == 0)
2115 *entry
= entry_ptr
->key
;
2120 PySet_Pop(PyObject
*set
)
2122 if (!PyType_IsSubtype(set
->ob_type
, &PySet_Type
)) {
2123 PyErr_BadInternalCall();
2126 return set_pop((PySetObject
*)set
);
2130 _PySet_Update(PyObject
*set
, PyObject
*iterable
)
2132 if (!PyType_IsSubtype(set
->ob_type
, &PySet_Type
)) {
2133 PyErr_BadInternalCall();
2136 return set_update_internal((PySetObject
*)set
, iterable
);
2141 /* Test code to be called with any three element set.
2142 Returns True and original set is restored. */
2144 #define assertRaises(call_return_value, exception) \
2146 assert(call_return_value); \
2147 assert(PyErr_ExceptionMatches(exception)); \
2152 test_c_api(PySetObject
*so
)
2157 PyObject
*elem
, *dup
, *t
, *f
, *dup2
;
2158 PyObject
*ob
= (PyObject
*)so
;
2160 /* Verify preconditions and exercise type/size checks */
2161 assert(PyAnySet_Check(ob
));
2162 assert(PyAnySet_CheckExact(ob
));
2163 assert(!PyFrozenSet_CheckExact(ob
));
2164 assert(PySet_Size(ob
) == 3);
2165 assert(PySet_GET_SIZE(ob
) == 3);
2167 /* Raise TypeError for non-iterable constructor arguments */
2168 assertRaises(PySet_New(Py_None
) == NULL
, PyExc_TypeError
);
2169 assertRaises(PyFrozenSet_New(Py_None
) == NULL
, PyExc_TypeError
);
2171 /* Raise TypeError for unhashable key */
2172 dup
= PySet_New(ob
);
2173 assertRaises(PySet_Discard(ob
, dup
) == -1, PyExc_TypeError
);
2174 assertRaises(PySet_Contains(ob
, dup
) == -1, PyExc_TypeError
);
2175 assertRaises(PySet_Add(ob
, dup
) == -1, PyExc_TypeError
);
2177 /* Exercise successful pop, contains, add, and discard */
2178 elem
= PySet_Pop(ob
);
2179 assert(PySet_Contains(ob
, elem
) == 0);
2180 assert(PySet_GET_SIZE(ob
) == 2);
2181 assert(PySet_Add(ob
, elem
) == 0);
2182 assert(PySet_Contains(ob
, elem
) == 1);
2183 assert(PySet_GET_SIZE(ob
) == 3);
2184 assert(PySet_Discard(ob
, elem
) == 1);
2185 assert(PySet_GET_SIZE(ob
) == 2);
2186 assert(PySet_Discard(ob
, elem
) == 0);
2187 assert(PySet_GET_SIZE(ob
) == 2);
2189 /* Exercise clear */
2190 dup2
= PySet_New(dup
);
2191 assert(PySet_Clear(dup2
) == 0);
2192 assert(PySet_Size(dup2
) == 0);
2195 /* Raise SystemError on clear or update of frozen set */
2196 f
= PyFrozenSet_New(dup
);
2197 assertRaises(PySet_Clear(f
) == -1, PyExc_SystemError
);
2198 assertRaises(_PySet_Update(f
, dup
) == -1, PyExc_SystemError
);
2201 /* Exercise direct iteration */
2203 while (_PySet_Next((PyObject
*)dup
, &i
, &elem
)) {
2204 s
= PyString_AsString(elem
);
2205 assert(s
&& (s
[0] == 'a' || s
[0] == 'b' || s
[0] == 'c'));
2210 /* Exercise updates */
2211 dup2
= PySet_New(NULL
);
2212 assert(_PySet_Update(dup2
, dup
) == 0);
2213 assert(PySet_Size(dup2
) == 3);
2214 assert(_PySet_Update(dup2
, dup
) == 0);
2215 assert(PySet_Size(dup2
) == 3);
2218 /* Raise SystemError when self argument is not a set or frozenset. */
2220 assertRaises(PySet_Size(t
) == -1, PyExc_SystemError
);
2221 assertRaises(PySet_Contains(t
, elem
) == -1, PyExc_SystemError
);
2224 /* Raise SystemError when self argument is not a set. */
2225 f
= PyFrozenSet_New(dup
);
2226 assert(PySet_Size(f
) == 3);
2227 assert(PyFrozenSet_CheckExact(f
));
2228 assertRaises(PySet_Add(f
, elem
) == -1, PyExc_SystemError
);
2229 assertRaises(PySet_Discard(f
, elem
) == -1, PyExc_SystemError
);
2230 assertRaises(PySet_Pop(f
) == NULL
, PyExc_SystemError
);
2233 /* Raise KeyError when popping from an empty set */
2234 assert(PyNumber_InPlaceSubtract(ob
, ob
) == ob
);
2236 assert(PySet_GET_SIZE(ob
) == 0);
2237 assertRaises(PySet_Pop(ob
) == NULL
, PyExc_KeyError
);
2239 /* Restore the set from the copy using the PyNumber API */
2240 assert(PyNumber_InPlaceOr(ob
, dup
) == ob
);
2243 /* Verify constructors accept NULL arguments */
2244 f
= PySet_New(NULL
);
2246 assert(PySet_GET_SIZE(f
) == 0);
2248 f
= PyFrozenSet_New(NULL
);
2250 assert(PyFrozenSet_CheckExact(f
));
2251 assert(PySet_GET_SIZE(f
) == 0);