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-5 Python Software Foundation.
11 #include "structmember.h"
13 /* This must be >= 1. */
14 #define PERTURB_SHIFT 5
16 /* Object used as dummy key to fill deleted entries */
17 static PyObject
*dummy
= NULL
; /* Initialized by first call to make_new_set() */
19 #define INIT_NONZERO_SET_SLOTS(so) do { \
20 (so)->table = (so)->smalltable; \
21 (so)->mask = PySet_MINSIZE - 1; \
25 #define EMPTY_TO_MINSIZE(so) do { \
26 memset((so)->smalltable, 0, sizeof((so)->smalltable)); \
27 (so)->used = (so)->fill = 0; \
28 INIT_NONZERO_SET_SLOTS(so); \
31 /* Reuse scheme to save calls to malloc, free, and memset */
32 #define MAXFREESETS 80
33 static PySetObject
*free_sets
[MAXFREESETS
];
34 static int num_free_sets
= 0;
37 The basic lookup function used by all operations.
38 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
39 Open addressing is preferred over chaining since the link overhead for
40 chaining would be substantial (100% with typical malloc overhead).
42 The initial probe index is computed as hash mod the table size. Subsequent
43 probe indices are computed as explained in Objects/dictobject.c.
45 All arithmetic on hash should ignore overflow.
47 Unlike the dictionary implementation, the lookkey functions can return
48 NULL if the rich comparison returns an error.
52 set_lookkey(PySetObject
*so
, PyObject
*key
, register long hash
)
55 register unsigned int perturb
;
56 register setentry
*freeslot
;
57 register unsigned int mask
= so
->mask
;
58 setentry
*table
= so
->table
;
59 register setentry
*entry
;
65 if (entry
->key
== NULL
|| entry
->key
== key
)
68 if (entry
->key
== dummy
)
71 if (entry
->hash
== hash
) {
72 startkey
= entry
->key
;
73 cmp
= PyObject_RichCompareBool(startkey
, key
, Py_EQ
);
76 if (table
== so
->table
&& entry
->key
== startkey
) {
81 /* The compare did major nasty stuff to the
84 return set_lookkey(so
, key
, hash
);
90 /* In the loop, key == dummy is by far (factor of 100s) the
91 least likely outcome, so test for that last. */
92 for (perturb
= hash
; ; perturb
>>= PERTURB_SHIFT
) {
93 i
= (i
<< 2) + i
+ perturb
+ 1;
94 entry
= &table
[i
& mask
];
95 if (entry
->key
== NULL
) {
100 if (entry
->key
== key
)
102 if (entry
->hash
== hash
&& entry
->key
!= dummy
) {
103 startkey
= entry
->key
;
104 cmp
= PyObject_RichCompareBool(startkey
, key
, Py_EQ
);
107 if (table
== so
->table
&& entry
->key
== startkey
) {
112 /* The compare did major nasty stuff to the
115 return set_lookkey(so
, key
, hash
);
118 else if (entry
->key
== dummy
&& freeslot
== NULL
)
125 * Hacked up version of set_lookkey which can assume keys are always strings;
126 * This means we can always use _PyString_Eq directly and not have to check to
127 * see if the comparison altered the table.
130 set_lookkey_string(PySetObject
*so
, PyObject
*key
, register long hash
)
133 register unsigned int perturb
;
134 register setentry
*freeslot
;
135 register unsigned int mask
= so
->mask
;
136 setentry
*table
= so
->table
;
137 register setentry
*entry
;
139 /* Make sure this function doesn't have to handle non-string keys,
140 including subclasses of str; e.g., one reason to subclass
141 strings is to override __eq__, and for speed we don't cater to
143 if (!PyString_CheckExact(key
)) {
144 so
->lookup
= set_lookkey
;
145 return set_lookkey(so
, key
, hash
);
149 if (entry
->key
== NULL
|| entry
->key
== key
)
151 if (entry
->key
== dummy
)
154 if (entry
->hash
== hash
&& _PyString_Eq(entry
->key
, key
))
159 /* In the loop, key == dummy is by far (factor of 100s) the
160 least likely outcome, so test for that last. */
161 for (perturb
= hash
; ; perturb
>>= PERTURB_SHIFT
) {
162 i
= (i
<< 2) + i
+ perturb
+ 1;
163 entry
= &table
[i
& mask
];
164 if (entry
->key
== NULL
)
165 return freeslot
== NULL
? entry
: freeslot
;
166 if (entry
->key
== key
167 || (entry
->hash
== hash
168 && entry
->key
!= dummy
169 && _PyString_Eq(entry
->key
, key
)))
171 if (entry
->key
== dummy
&& freeslot
== NULL
)
177 Internal routine to insert a new key into the table.
178 Used both by the internal resize routine and by the public insert routine.
179 Eats a reference to key.
182 set_insert_key(register PySetObject
*so
, PyObject
*key
, long hash
)
184 register setentry
*entry
;
185 typedef setentry
*(*lookupfunc
)(PySetObject
*, PyObject
*, long);
187 assert(so
->lookup
!= NULL
);
188 entry
= so
->lookup(so
, key
, hash
);
191 if (entry
->key
== NULL
) {
197 } else if (entry
->key
== dummy
) {
211 Restructure the table by allocating a new table and reinserting all
212 keys again. When entries have been deleted, the new table may
213 actually be smaller than the old one.
216 set_table_resize(PySetObject
*so
, int minused
)
219 setentry
*oldtable
, *newtable
, *entry
;
221 int is_oldtable_malloced
;
222 setentry small_copy
[PySet_MINSIZE
];
224 assert(minused
>= 0);
226 /* Find the smallest table size > minused. */
227 for (newsize
= PySet_MINSIZE
;
228 newsize
<= minused
&& newsize
> 0;
236 /* Get space for a new table. */
237 oldtable
= so
->table
;
238 assert(oldtable
!= NULL
);
239 is_oldtable_malloced
= oldtable
!= so
->smalltable
;
241 if (newsize
== PySet_MINSIZE
) {
242 /* A large table is shrinking, or we can't get any smaller. */
243 newtable
= so
->smalltable
;
244 if (newtable
== oldtable
) {
245 if (so
->fill
== so
->used
) {
246 /* No dummies, so no point doing anything. */
249 /* We're not going to resize it, but rebuild the
250 table anyway to purge old dummy entries.
251 Subtle: This is *necessary* if fill==size,
252 as set_lookkey needs at least one virgin slot to
253 terminate failing searches. If fill < size, it's
254 merely desirable, as dummies slow searches. */
255 assert(so
->fill
> so
->used
);
256 memcpy(small_copy
, oldtable
, sizeof(small_copy
));
257 oldtable
= small_copy
;
261 newtable
= PyMem_NEW(setentry
, newsize
);
262 if (newtable
== NULL
) {
268 /* Make the set empty, using the new table. */
269 assert(newtable
!= oldtable
);
270 so
->table
= newtable
;
271 so
->mask
= newsize
- 1;
272 memset(newtable
, 0, sizeof(setentry
) * newsize
);
277 /* Copy the data over; this is refcount-neutral for active entries;
278 dummy entries aren't copied over, of course */
279 for (entry
= oldtable
; i
> 0; entry
++) {
280 if (entry
->key
== NULL
) {
283 } else if (entry
->key
== dummy
) {
286 assert(entry
->key
== dummy
);
287 Py_DECREF(entry
->key
);
291 if(set_insert_key(so
, entry
->key
, entry
->hash
) == -1) {
292 if (is_oldtable_malloced
)
299 if (is_oldtable_malloced
)
304 /* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
307 set_add_entry(register PySetObject
*so
, setentry
*entry
)
311 assert(so
->fill
<= so
->mask
); /* at least one empty slot */
313 Py_INCREF(entry
->key
);
314 if (set_insert_key(so
, entry
->key
, entry
->hash
) == -1)
316 if (!(so
->used
> n_used
&& so
->fill
*3 >= (so
->mask
+1)*2))
318 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
322 set_add_key(register PySetObject
*so
, PyObject
*key
)
327 if (!PyString_CheckExact(key
) ||
328 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
329 hash
= PyObject_Hash(key
);
333 assert(so
->fill
<= so
->mask
); /* at least one empty slot */
336 if (set_insert_key(so
, key
, hash
) == -1) {
340 if (!(so
->used
> n_used
&& so
->fill
*3 >= (so
->mask
+1)*2))
342 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
345 #define DISCARD_NOTFOUND 0
346 #define DISCARD_FOUND 1
349 set_discard_entry(PySetObject
*so
, setentry
*oldentry
)
350 { register setentry
*entry
;
353 entry
= (so
->lookup
)(so
, oldentry
->key
, oldentry
->hash
);
356 if (entry
->key
== NULL
|| entry
->key
== dummy
)
357 return DISCARD_NOTFOUND
;
358 old_key
= entry
->key
;
363 return DISCARD_FOUND
;
367 set_discard_key(PySetObject
*so
, PyObject
*key
)
370 register setentry
*entry
;
373 assert (PyAnySet_Check(so
));
374 if (!PyString_CheckExact(key
) ||
375 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
376 hash
= PyObject_Hash(key
);
380 entry
= (so
->lookup
)(so
, key
, hash
);
383 if (entry
->key
== NULL
|| entry
->key
== dummy
)
384 return DISCARD_NOTFOUND
;
385 old_key
= entry
->key
;
390 return DISCARD_FOUND
;
394 set_clear_internal(PySetObject
*so
)
396 setentry
*entry
, *table
;
397 int table_is_malloced
;
399 setentry small_copy
[PySet_MINSIZE
];
402 assert (PyAnySet_Check(so
));
409 assert(table
!= NULL
);
410 table_is_malloced
= table
!= so
->smalltable
;
412 /* This is delicate. During the process of clearing the set,
413 * decrefs can cause the set to mutate. To avoid fatal confusion
414 * (voice of experience), we have to make the set empty before
415 * clearing the slots, and never refer to anything via so->ref while
419 if (table_is_malloced
)
420 EMPTY_TO_MINSIZE(so
);
423 /* It's a small table with something that needs to be cleared.
424 * Afraid the only safe way is to copy the set entries into
425 * another small table first.
427 memcpy(small_copy
, table
, sizeof(small_copy
));
429 EMPTY_TO_MINSIZE(so
);
431 /* else it's a small table that's already empty */
433 /* Now we can finally clear things. If C had refcounts, we could
434 * assert that the refcount on table is 1 now, i.e. that this function
435 * has unique access to it, so decref side-effects can't alter it.
437 for (entry
= table
; fill
> 0; ++entry
) {
444 Py_DECREF(entry
->key
);
448 assert(entry
->key
== NULL
|| entry
->key
== dummy
);
452 if (table_is_malloced
)
458 * Iterate over a set table. Use like so:
462 * pos = 0; # important! pos should not otherwise be changed by you
463 * while (set_next(yourset, &pos, &entry)) {
464 * Refer to borrowed reference in entry->key.
467 * CAUTION: In general, it isn't safe to use set_next in a loop that
471 set_next(PySetObject
*so
, int *pos_ptr
, setentry
**entry_ptr
)
473 register int i
, mask
;
474 register setentry
*table
;
476 assert (PyAnySet_Check(so
));
481 while (i
<= mask
&& (table
[i
].key
== NULL
|| table
[i
].key
== dummy
))
486 assert(table
[i
].key
!= NULL
);
487 *entry_ptr
= &table
[i
];
492 set_dealloc(PySetObject
*so
)
494 register setentry
*entry
;
496 PyObject_GC_UnTrack(so
);
497 Py_TRASHCAN_SAFE_BEGIN(so
)
498 if (so
->weakreflist
!= NULL
)
499 PyObject_ClearWeakRefs((PyObject
*) so
);
501 for (entry
= so
->table
; fill
> 0; entry
++) {
504 Py_DECREF(entry
->key
);
507 if (so
->table
!= so
->smalltable
)
508 PyMem_DEL(so
->table
);
509 if (num_free_sets
< MAXFREESETS
&& PyAnySet_CheckExact(so
))
510 free_sets
[num_free_sets
++] = so
;
512 so
->ob_type
->tp_free(so
);
513 Py_TRASHCAN_SAFE_END(so
)
517 set_tp_print(PySetObject
*so
, FILE *fp
, int flags
)
521 char *emit
= ""; /* No separator emitted on first pass */
522 char *separator
= ", ";
524 fprintf(fp
, "%s([", so
->ob_type
->tp_name
);
525 while (set_next(so
, &pos
, &entry
)) {
528 if (PyObject_Print(entry
->key
, fp
, 0) != 0)
536 set_repr(PySetObject
*so
)
538 PyObject
*keys
, *result
, *listrepr
;
540 keys
= PySequence_List((PyObject
*)so
);
543 listrepr
= PyObject_Repr(keys
);
545 if (listrepr
== NULL
)
548 result
= PyString_FromFormat("%s(%s)", so
->ob_type
->tp_name
,
549 PyString_AS_STRING(listrepr
));
555 set_len(PyObject
*so
)
557 return ((PySetObject
*)so
)->used
;
561 set_merge(PySetObject
*so
, PyObject
*otherset
)
565 register setentry
*entry
;
567 assert (PyAnySet_Check(so
));
568 assert (PyAnySet_Check(otherset
));
570 other
= (PySetObject
*)otherset
;
571 if (other
== so
|| other
->used
== 0)
572 /* a.update(a) or a.update({}); nothing to do */
574 /* Do one big resize at the start, rather than
575 * incrementally resizing as we insert new keys. Expect
576 * that there will be no (or few) overlapping keys.
578 if ((so
->fill
+ other
->used
)*3 >= (so
->mask
+1)*2) {
579 if (set_table_resize(so
, (so
->used
+ other
->used
)*2) != 0)
582 for (i
= 0; i
<= other
->mask
; i
++) {
583 entry
= &other
->table
[i
];
584 if (entry
->key
!= NULL
&&
585 entry
->key
!= dummy
) {
586 Py_INCREF(entry
->key
);
587 if (set_insert_key(so
, entry
->key
, entry
->hash
) == -1) {
588 Py_DECREF(entry
->key
);
597 set_contains_key(PySetObject
*so
, PyObject
*key
)
602 if (!PyString_CheckExact(key
) ||
603 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
604 hash
= PyObject_Hash(key
);
608 entry
= (so
->lookup
)(so
, key
, hash
);
612 return key
!= NULL
&& key
!= dummy
;
616 set_contains_entry(PySetObject
*so
, setentry
*entry
)
621 lu_entry
= (so
->lookup
)(so
, entry
->key
, entry
->hash
);
622 if (lu_entry
== NULL
)
625 return key
!= NULL
&& key
!= dummy
;
629 set_pop(PySetObject
*so
)
632 register setentry
*entry
;
635 assert (PyAnySet_Check(so
));
637 PyErr_SetString(PyExc_KeyError
, "pop from an empty set");
641 /* Set entry to "the first" unused or dummy set entry. We abuse
642 * the hash field of slot 0 to hold a search finger:
643 * If slot 0 has a value, use slot 0.
644 * Else slot 0 is being used to hold a search finger,
645 * and we use its hash value as the first index to look.
647 entry
= &so
->table
[0];
648 if (entry
->key
== NULL
|| entry
->key
== dummy
) {
649 i
= (int)entry
->hash
;
650 /* The hash field may be a real hash value, or it may be a
651 * legit search finger, or it may be a once-legit search
652 * finger that's out of bounds now because it wrapped around
653 * or the table shrunk -- simply make sure it's in bounds now.
655 if (i
> so
->mask
|| i
< 1)
656 i
= 1; /* skip slot 0 */
657 while ((entry
= &so
->table
[i
])->key
== NULL
|| entry
->key
==dummy
) {
667 so
->table
[0].hash
= i
+ 1; /* next place to start */
671 PyDoc_STRVAR(pop_doc
, "Remove and return an arbitrary set element.");
674 set_traverse(PySetObject
*so
, visitproc visit
, void *arg
)
679 while (set_next(so
, &pos
, &entry
))
680 Py_VISIT(entry
->key
);
685 frozenset_hash(PyObject
*self
)
687 PySetObject
*so
= (PySetObject
*)self
;
688 long h
, hash
= 1927868237L;
695 hash
*= PySet_GET_SIZE(self
) + 1;
696 while (set_next(so
, &pos
, &entry
)) {
697 /* Work to increase the bit dispersion for closely spaced hash
698 values. The is important because some use cases have many
699 combinations of a small number of elements with nearby
700 hashes so that many distinct combinations collapse to only
701 a handful of distinct hash values. */
703 hash
^= (h
^ (h
<< 16) ^ 89869747L) * 3644798167u;
705 hash
= hash
* 69069L + 907133923L;
713 set_nohash(PyObject
*self
)
715 PyErr_SetString(PyExc_TypeError
, "set objects are unhashable");
719 /***** Set iterator type ***********************************************/
721 static PyTypeObject PySetIter_Type
; /* Forward */
725 PySetObject
*si_set
; /* Set to NULL when iterator is exhausted */
732 set_iter(PySetObject
*so
)
734 setiterobject
*si
= PyObject_New(setiterobject
, &PySetIter_Type
);
739 si
->si_used
= so
->used
;
742 return (PyObject
*)si
;
746 setiter_dealloc(setiterobject
*si
)
748 Py_XDECREF(si
->si_set
);
753 setiter_len(setiterobject
*si
)
756 if (si
->si_set
!= NULL
&& si
->si_used
== si
->si_set
->used
)
758 return PyInt_FromLong(len
);
761 PyDoc_STRVAR(length_cue_doc
, "Private method returning an estimate of len(list(it)).");
763 static PyMethodDef setiter_methods
[] = {
764 {"_length_cue", (PyCFunction
)setiter_len
, METH_NOARGS
, length_cue_doc
},
765 {NULL
, NULL
} /* sentinel */
768 static PyObject
*setiter_iternext(setiterobject
*si
)
771 register int i
, mask
;
772 register setentry
*entry
;
773 PySetObject
*so
= si
->si_set
;
777 assert (PyAnySet_Check(so
));
779 if (si
->si_used
!= so
->used
) {
780 PyErr_SetString(PyExc_RuntimeError
,
781 "Set changed size during iteration");
782 si
->si_used
= -1; /* Make this state sticky */
790 while (i
<= mask
&& (entry
[i
].key
== NULL
|| entry
[i
].key
== dummy
))
806 static PyTypeObject PySetIter_Type
= {
807 PyObject_HEAD_INIT(&PyType_Type
)
809 "setiterator", /* tp_name */
810 sizeof(setiterobject
), /* tp_basicsize */
813 (destructor
)setiter_dealloc
, /* tp_dealloc */
819 0, /* tp_as_number */
820 0, /* tp_as_sequence */
821 0, /* tp_as_mapping */
825 PyObject_GenericGetAttr
, /* tp_getattro */
827 0, /* tp_as_buffer */
828 Py_TPFLAGS_DEFAULT
, /* tp_flags */
832 0, /* tp_richcompare */
833 0, /* tp_weaklistoffset */
834 PyObject_SelfIter
, /* tp_iter */
835 (iternextfunc
)setiter_iternext
, /* tp_iternext */
836 setiter_methods
, /* tp_methods */
841 set_update_internal(PySetObject
*so
, PyObject
*other
)
845 if (PyAnySet_Check(other
))
846 return set_merge(so
, other
);
848 if (PyDict_Check(other
)) {
851 while (PyDict_Next(other
, &pos
, &key
, &value
)) {
852 if (set_add_key(so
, key
) == -1)
858 it
= PyObject_GetIter(other
);
862 while ((key
= PyIter_Next(it
)) != NULL
) {
863 if (set_add_key(so
, key
) == -1) {
871 if (PyErr_Occurred())
877 set_update(PySetObject
*so
, PyObject
*other
)
879 if (set_update_internal(so
, other
) == -1)
884 PyDoc_STRVAR(update_doc
,
885 "Update a set with the union of itself and another.");
888 make_new_set(PyTypeObject
*type
, PyObject
*iterable
)
890 register PySetObject
*so
= NULL
;
892 if (dummy
== NULL
) { /* Auto-initialize dummy */
893 dummy
= PyString_FromString("<dummy key>");
898 /* create PySetObject structure */
900 (type
== &PySet_Type
|| type
== &PyFrozenSet_Type
)) {
901 so
= free_sets
[--num_free_sets
];
902 assert (so
!= NULL
&& PyAnySet_CheckExact(so
));
904 _Py_NewReference((PyObject
*)so
);
905 EMPTY_TO_MINSIZE(so
);
906 PyObject_GC_Track(so
);
908 so
= (PySetObject
*)type
->tp_alloc(type
, 0);
911 /* tp_alloc has already zeroed the structure */
912 assert(so
->table
== NULL
&& so
->fill
== 0 && so
->used
== 0);
913 INIT_NONZERO_SET_SLOTS(so
);
916 so
->lookup
= set_lookkey_string
;
917 so
->weakreflist
= NULL
;
919 if (iterable
!= NULL
) {
920 if (set_update_internal(so
, iterable
) == -1) {
926 return (PyObject
*)so
;
929 /* The empty frozenset is a singleton */
930 static PyObject
*emptyfrozenset
= NULL
;
933 frozenset_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
935 PyObject
*iterable
= NULL
, *result
;
937 if (!_PyArg_NoKeywords("frozenset()", kwds
))
940 if (!PyArg_UnpackTuple(args
, type
->tp_name
, 0, 1, &iterable
))
943 if (type
!= &PyFrozenSet_Type
)
944 return make_new_set(type
, iterable
);
946 if (iterable
!= NULL
) {
947 /* frozenset(f) is idempotent */
948 if (PyFrozenSet_CheckExact(iterable
)) {
952 result
= make_new_set(type
, iterable
);
953 if (result
== NULL
|| PySet_GET_SIZE(result
))
957 /* The empty frozenset is a singleton */
958 if (emptyfrozenset
== NULL
)
959 emptyfrozenset
= make_new_set(type
, NULL
);
960 Py_XINCREF(emptyfrozenset
);
961 return emptyfrozenset
;
969 while (num_free_sets
) {
971 so
= free_sets
[num_free_sets
];
975 Py_XDECREF(emptyfrozenset
);
979 set_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
981 if (!_PyArg_NoKeywords("set()", kwds
))
984 return make_new_set(type
, NULL
);
987 /* set_swap_bodies() switches the contents of any two sets by moving their
988 internal data pointers and, if needed, copying the internal smalltables.
989 Semantically equivalent to:
991 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
993 The function always succeeds and it leaves both objects in a stable state.
994 Useful for creating temporary frozensets from sets for membership testing
995 in __contains__(), discard(), and remove(). Also useful for operations
996 that update in-place (by allowing an intermediate result to be swapped
997 into one of the original inputs).
1001 set_swap_bodies(PySetObject
*a
, PySetObject
*b
)
1005 setentry
*(*f
)(PySetObject
*so
, PyObject
*key
, long hash
);
1006 setentry tab
[PySet_MINSIZE
];
1009 t
= a
->fill
; a
->fill
= b
->fill
; b
->fill
= t
;
1010 t
= a
->used
; a
->used
= b
->used
; b
->used
= t
;
1011 t
= a
->mask
; a
->mask
= b
->mask
; b
->mask
= t
;
1014 if (a
->table
== a
->smalltable
)
1016 a
->table
= b
->table
;
1017 if (b
->table
== b
->smalltable
)
1018 a
->table
= a
->smalltable
;
1021 f
= a
->lookup
; a
->lookup
= b
->lookup
; b
->lookup
= f
;
1023 if (a
->table
== a
->smalltable
|| b
->table
== b
->smalltable
) {
1024 memcpy(tab
, a
->smalltable
, sizeof(tab
));
1025 memcpy(a
->smalltable
, b
->smalltable
, sizeof(tab
));
1026 memcpy(b
->smalltable
, tab
, sizeof(tab
));
1029 if (PyType_IsSubtype(a
->ob_type
, &PyFrozenSet_Type
) &&
1030 PyType_IsSubtype(b
->ob_type
, &PyFrozenSet_Type
)) {
1031 h
= a
->hash
; a
->hash
= b
->hash
; b
->hash
= h
;
1039 set_copy(PySetObject
*so
)
1041 return make_new_set(so
->ob_type
, (PyObject
*)so
);
1045 frozenset_copy(PySetObject
*so
)
1047 if (PyFrozenSet_CheckExact(so
)) {
1049 return (PyObject
*)so
;
1051 return set_copy(so
);
1054 PyDoc_STRVAR(copy_doc
, "Return a shallow copy of a set.");
1057 set_clear(PySetObject
*so
)
1059 set_clear_internal(so
);
1063 PyDoc_STRVAR(clear_doc
, "Remove all elements from this set.");
1066 set_union(PySetObject
*so
, PyObject
*other
)
1068 PySetObject
*result
;
1070 result
= (PySetObject
*)set_copy(so
);
1073 if ((PyObject
*)so
== other
)
1074 return (PyObject
*)result
;
1075 if (set_update_internal(result
, other
) == -1) {
1079 return (PyObject
*)result
;
1082 PyDoc_STRVAR(union_doc
,
1083 "Return the union of two sets as a new set.\n\
1085 (i.e. all elements that are in either set.)");
1088 set_or(PySetObject
*so
, PyObject
*other
)
1090 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1091 Py_INCREF(Py_NotImplemented
);
1092 return Py_NotImplemented
;
1094 return set_union(so
, other
);
1098 set_ior(PySetObject
*so
, PyObject
*other
)
1100 if (!PyAnySet_Check(other
)) {
1101 Py_INCREF(Py_NotImplemented
);
1102 return Py_NotImplemented
;
1104 if (set_update_internal(so
, other
) == -1)
1107 return (PyObject
*)so
;
1111 set_intersection(PySetObject
*so
, PyObject
*other
)
1113 PySetObject
*result
;
1114 PyObject
*key
, *it
, *tmp
;
1116 if ((PyObject
*)so
== other
)
1117 return set_copy(so
);
1119 result
= (PySetObject
*)make_new_set(so
->ob_type
, NULL
);
1123 if (PyAnySet_Check(other
)) {
1127 if (PySet_GET_SIZE(other
) > PySet_GET_SIZE(so
)) {
1128 tmp
= (PyObject
*)so
;
1129 so
= (PySetObject
*)other
;
1133 while (set_next((PySetObject
*)other
, &pos
, &entry
)) {
1134 if (set_contains_entry(so
, entry
)) {
1135 if (set_add_entry(result
, entry
) == -1) {
1141 return (PyObject
*)result
;
1144 it
= PyObject_GetIter(other
);
1150 while ((key
= PyIter_Next(it
)) != NULL
) {
1151 if (set_contains_key(so
, key
)) {
1152 if (set_add_key(result
, key
) == -1) {
1162 if (PyErr_Occurred()) {
1166 return (PyObject
*)result
;
1169 PyDoc_STRVAR(intersection_doc
,
1170 "Return the intersection of two sets as a new set.\n\
1172 (i.e. all elements that are in both sets.)");
1175 set_intersection_update(PySetObject
*so
, PyObject
*other
)
1179 tmp
= set_intersection(so
, other
);
1182 set_swap_bodies(so
, (PySetObject
*)tmp
);
1187 PyDoc_STRVAR(intersection_update_doc
,
1188 "Update a set with the intersection of itself and another.");
1191 set_and(PySetObject
*so
, PyObject
*other
)
1193 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1194 Py_INCREF(Py_NotImplemented
);
1195 return Py_NotImplemented
;
1197 return set_intersection(so
, other
);
1201 set_iand(PySetObject
*so
, PyObject
*other
)
1205 if (!PyAnySet_Check(other
)) {
1206 Py_INCREF(Py_NotImplemented
);
1207 return Py_NotImplemented
;
1209 result
= set_intersection_update(so
, other
);
1214 return (PyObject
*)so
;
1218 set_difference_update_internal(PySetObject
*so
, PyObject
*other
)
1220 if ((PyObject
*)so
== other
)
1221 return set_clear_internal(so
);
1223 if (PyAnySet_Check(other
)) {
1227 while (set_next((PySetObject
*)other
, &pos
, &entry
))
1228 set_discard_entry(so
, entry
);
1231 it
= PyObject_GetIter(other
);
1235 while ((key
= PyIter_Next(it
)) != NULL
) {
1236 if (set_discard_key(so
, key
) == -1) {
1244 if (PyErr_Occurred())
1247 /* If more than 1/5 are dummies, then resize them away. */
1248 if ((so
->fill
- so
->used
) * 5 < so
->mask
)
1250 return set_table_resize(so
, so
->used
>50000 ? so
->used
*2 : so
->used
*4);
1254 set_difference_update(PySetObject
*so
, PyObject
*other
)
1256 if (set_difference_update_internal(so
, other
) != -1)
1261 PyDoc_STRVAR(difference_update_doc
,
1262 "Remove all elements of another set from this set.");
1265 set_difference(PySetObject
*so
, PyObject
*other
)
1271 if (!PyAnySet_Check(other
) && !PyDict_Check(other
)) {
1272 result
= set_copy(so
);
1275 if (set_difference_update_internal((PySetObject
*)result
, other
) != -1)
1281 result
= make_new_set(so
->ob_type
, NULL
);
1285 if (PyDict_Check(other
)) {
1286 while (set_next(so
, &pos
, &entry
)) {
1288 entrycopy
.hash
= entry
->hash
;
1289 entrycopy
.key
= entry
->key
;
1290 if (!PyDict_Contains(other
, entry
->key
)) {
1291 if (set_add_entry((PySetObject
*)result
, &entrycopy
) == -1)
1298 while (set_next(so
, &pos
, &entry
)) {
1299 if (!set_contains_entry((PySetObject
*)other
, entry
)) {
1300 if (set_add_entry((PySetObject
*)result
, entry
) == -1)
1307 PyDoc_STRVAR(difference_doc
,
1308 "Return the difference of two sets as a new set.\n\
1310 (i.e. all elements that are in this set but not the other.)");
1312 set_sub(PySetObject
*so
, PyObject
*other
)
1314 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1315 Py_INCREF(Py_NotImplemented
);
1316 return Py_NotImplemented
;
1318 return set_difference(so
, other
);
1322 set_isub(PySetObject
*so
, PyObject
*other
)
1326 if (!PyAnySet_Check(other
)) {
1327 Py_INCREF(Py_NotImplemented
);
1328 return Py_NotImplemented
;
1330 result
= set_difference_update(so
, other
);
1335 return (PyObject
*)so
;
1339 set_symmetric_difference_update(PySetObject
*so
, PyObject
*other
)
1341 PySetObject
*otherset
;
1346 if ((PyObject
*)so
== other
)
1347 return set_clear(so
);
1349 if (PyDict_Check(other
)) {
1352 while (PyDict_Next(other
, &pos
, &key
, &value
)) {
1353 rv
= set_discard_key(so
, key
);
1356 if (rv
== DISCARD_NOTFOUND
) {
1357 if (set_add_key(so
, key
) == -1)
1364 if (PyAnySet_Check(other
)) {
1366 otherset
= (PySetObject
*)other
;
1368 otherset
= (PySetObject
*)make_new_set(so
->ob_type
, other
);
1369 if (otherset
== NULL
)
1373 while (set_next(otherset
, &pos
, &entry
)) {
1374 int rv
= set_discard_entry(so
, entry
);
1376 Py_XDECREF(otherset
);
1379 if (rv
== DISCARD_NOTFOUND
) {
1380 if (set_add_entry(so
, entry
) == -1) {
1381 Py_XDECREF(otherset
);
1386 Py_DECREF(otherset
);
1390 PyDoc_STRVAR(symmetric_difference_update_doc
,
1391 "Update a set with the symmetric difference of itself and another.");
1394 set_symmetric_difference(PySetObject
*so
, PyObject
*other
)
1397 PySetObject
*otherset
;
1399 otherset
= (PySetObject
*)make_new_set(so
->ob_type
, other
);
1400 if (otherset
== NULL
)
1402 rv
= set_symmetric_difference_update(otherset
, (PyObject
*)so
);
1406 return (PyObject
*)otherset
;
1409 PyDoc_STRVAR(symmetric_difference_doc
,
1410 "Return the symmetric difference of two sets as a new set.\n\
1412 (i.e. all elements that are in exactly one of the sets.)");
1415 set_xor(PySetObject
*so
, PyObject
*other
)
1417 if (!PyAnySet_Check(so
) || !PyAnySet_Check(other
)) {
1418 Py_INCREF(Py_NotImplemented
);
1419 return Py_NotImplemented
;
1421 return set_symmetric_difference(so
, other
);
1425 set_ixor(PySetObject
*so
, PyObject
*other
)
1429 if (!PyAnySet_Check(other
)) {
1430 Py_INCREF(Py_NotImplemented
);
1431 return Py_NotImplemented
;
1433 result
= set_symmetric_difference_update(so
, other
);
1438 return (PyObject
*)so
;
1442 set_issubset(PySetObject
*so
, PyObject
*other
)
1447 if (!PyAnySet_Check(other
)) {
1448 PyObject
*tmp
, *result
;
1449 tmp
= make_new_set(&PySet_Type
, other
);
1452 result
= set_issubset(so
, tmp
);
1456 if (PySet_GET_SIZE(so
) > PySet_GET_SIZE(other
))
1459 while (set_next(so
, &pos
, &entry
)) {
1460 if (!set_contains_entry((PySetObject
*)other
, entry
))
1466 PyDoc_STRVAR(issubset_doc
, "Report whether another set contains this set.");
1469 set_issuperset(PySetObject
*so
, PyObject
*other
)
1471 PyObject
*tmp
, *result
;
1473 if (!PyAnySet_Check(other
)) {
1474 tmp
= make_new_set(&PySet_Type
, other
);
1477 result
= set_issuperset(so
, tmp
);
1481 return set_issubset((PySetObject
*)other
, (PyObject
*)so
);
1484 PyDoc_STRVAR(issuperset_doc
, "Report whether this set contains another set.");
1487 set_richcompare(PySetObject
*v
, PyObject
*w
, int op
)
1491 if(!PyAnySet_Check(w
)) {
1496 PyErr_SetString(PyExc_TypeError
, "can only compare to a set");
1501 if (PySet_GET_SIZE(v
) != PySet_GET_SIZE(w
))
1503 if (v
->hash
!= -1 &&
1504 ((PySetObject
*)w
)->hash
!= -1 &&
1505 v
->hash
!= ((PySetObject
*)w
)->hash
)
1507 return set_issubset(v
, w
);
1509 r1
= set_richcompare(v
, w
, Py_EQ
);
1512 r2
= PyBool_FromLong(PyObject_Not(r1
));
1516 return set_issubset(v
, w
);
1518 return set_issuperset(v
, w
);
1520 if (PySet_GET_SIZE(v
) >= PySet_GET_SIZE(w
))
1522 return set_issubset(v
, w
);
1524 if (PySet_GET_SIZE(v
) <= PySet_GET_SIZE(w
))
1526 return set_issuperset(v
, w
);
1528 Py_INCREF(Py_NotImplemented
);
1529 return Py_NotImplemented
;
1533 set_nocmp(PyObject
*self
)
1535 PyErr_SetString(PyExc_TypeError
, "cannot compare sets using cmp()");
1540 set_add(PySetObject
*so
, PyObject
*key
)
1542 if (set_add_key(so
, key
) == -1)
1547 PyDoc_STRVAR(add_doc
,
1548 "Add an element to a set.\n\
1550 This has no effect if the element is already present.");
1553 set_contains(PySetObject
*so
, PyObject
*key
)
1558 rv
= set_contains_key(so
, key
);
1560 if (!PyAnySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1563 tmpkey
= make_new_set(&PyFrozenSet_Type
, NULL
);
1566 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1567 rv
= set_contains(so
, tmpkey
);
1568 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1575 set_direct_contains(PySetObject
*so
, PyObject
*key
)
1579 result
= set_contains(so
, key
);
1582 return PyBool_FromLong(result
);
1585 PyDoc_STRVAR(contains_doc
, "x.__contains__(y) <==> y in x.");
1588 set_remove(PySetObject
*so
, PyObject
*key
)
1590 PyObject
*tmpkey
, *result
;
1593 rv
= set_discard_key(so
, key
);
1595 if (!PyAnySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1598 tmpkey
= make_new_set(&PyFrozenSet_Type
, NULL
);
1601 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1602 result
= set_remove(so
, tmpkey
);
1603 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1606 } else if (rv
== DISCARD_NOTFOUND
) {
1607 PyErr_SetObject(PyExc_KeyError
, key
);
1613 PyDoc_STRVAR(remove_doc
,
1614 "Remove an element from a set; it must be a member.\n\
1616 If the element is not a member, raise a KeyError.");
1619 set_discard(PySetObject
*so
, PyObject
*key
)
1621 PyObject
*tmpkey
, *result
;
1624 rv
= set_discard_key(so
, key
);
1626 if (!PyAnySet_Check(key
) || !PyErr_ExceptionMatches(PyExc_TypeError
))
1629 tmpkey
= make_new_set(&PyFrozenSet_Type
, NULL
);
1632 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1633 result
= set_discard(so
, tmpkey
);
1634 set_swap_bodies((PySetObject
*)tmpkey
, (PySetObject
*)key
);
1641 PyDoc_STRVAR(discard_doc
,
1642 "Remove an element from a set if it is a member.\n\
1644 If the element is not a member, do nothing.");
1647 set_reduce(PySetObject
*so
)
1649 PyObject
*keys
=NULL
, *args
=NULL
, *result
=NULL
, *dict
=NULL
;
1651 keys
= PySequence_List((PyObject
*)so
);
1654 args
= PyTuple_Pack(1, keys
);
1657 dict
= PyObject_GetAttrString((PyObject
*)so
, "__dict__");
1663 result
= PyTuple_Pack(3, so
->ob_type
, args
, dict
);
1671 PyDoc_STRVAR(reduce_doc
, "Return state information for pickling.");
1674 set_init(PySetObject
*self
, PyObject
*args
, PyObject
*kwds
)
1676 PyObject
*iterable
= NULL
;
1678 if (!PyAnySet_Check(self
))
1680 if (!PyArg_UnpackTuple(args
, self
->ob_type
->tp_name
, 0, 1, &iterable
))
1682 set_clear_internal(self
);
1684 if (iterable
== NULL
)
1686 return set_update_internal(self
, iterable
);
1689 static PySequenceMethods set_as_sequence
= {
1690 (inquiry
)set_len
, /* sq_length */
1695 0, /* sq_ass_item */
1696 0, /* sq_ass_slice */
1697 (objobjproc
)set_contains
, /* sq_contains */
1700 /* set object ********************************************************/
1703 static PyObject
*test_c_api(PySetObject
*so
);
1705 PyDoc_STRVAR(test_c_api_doc
, "Exercises C API. Returns True.\n\
1706 All is well if assertions don't fail.");
1709 static PyMethodDef set_methods
[] = {
1710 {"add", (PyCFunction
)set_add
, METH_O
,
1712 {"clear", (PyCFunction
)set_clear
, METH_NOARGS
,
1714 {"__contains__",(PyCFunction
)set_direct_contains
, METH_O
| METH_COEXIST
,
1716 {"copy", (PyCFunction
)set_copy
, METH_NOARGS
,
1718 {"discard", (PyCFunction
)set_discard
, METH_O
,
1720 {"difference", (PyCFunction
)set_difference
, METH_O
,
1722 {"difference_update", (PyCFunction
)set_difference_update
, METH_O
,
1723 difference_update_doc
},
1724 {"intersection",(PyCFunction
)set_intersection
, METH_O
,
1726 {"intersection_update",(PyCFunction
)set_intersection_update
, METH_O
,
1727 intersection_update_doc
},
1728 {"issubset", (PyCFunction
)set_issubset
, METH_O
,
1730 {"issuperset", (PyCFunction
)set_issuperset
, METH_O
,
1732 {"pop", (PyCFunction
)set_pop
, METH_NOARGS
,
1734 {"__reduce__", (PyCFunction
)set_reduce
, METH_NOARGS
,
1736 {"remove", (PyCFunction
)set_remove
, METH_O
,
1738 {"symmetric_difference",(PyCFunction
)set_symmetric_difference
, METH_O
,
1739 symmetric_difference_doc
},
1740 {"symmetric_difference_update",(PyCFunction
)set_symmetric_difference_update
, METH_O
,
1741 symmetric_difference_update_doc
},
1743 {"test_c_api", (PyCFunction
)test_c_api
, METH_NOARGS
,
1746 {"union", (PyCFunction
)set_union
, METH_O
,
1748 {"update", (PyCFunction
)set_update
, METH_O
,
1750 {NULL
, NULL
} /* sentinel */
1753 static PyNumberMethods set_as_number
= {
1755 (binaryfunc
)set_sub
, /*nb_subtract*/
1768 (binaryfunc
)set_and
, /*nb_and*/
1769 (binaryfunc
)set_xor
, /*nb_xor*/
1770 (binaryfunc
)set_or
, /*nb_or*/
1777 0, /*nb_inplace_add*/
1778 (binaryfunc
)set_isub
, /*nb_inplace_subtract*/
1779 0, /*nb_inplace_multiply*/
1780 0, /*nb_inplace_divide*/
1781 0, /*nb_inplace_remainder*/
1782 0, /*nb_inplace_power*/
1783 0, /*nb_inplace_lshift*/
1784 0, /*nb_inplace_rshift*/
1785 (binaryfunc
)set_iand
, /*nb_inplace_and*/
1786 (binaryfunc
)set_ixor
, /*nb_inplace_xor*/
1787 (binaryfunc
)set_ior
, /*nb_inplace_or*/
1790 PyDoc_STRVAR(set_doc
,
1791 "set(iterable) --> set object\n\
1793 Build an unordered collection.");
1795 PyTypeObject PySet_Type
= {
1796 PyObject_HEAD_INIT(&PyType_Type
)
1798 "set", /* tp_name */
1799 sizeof(PySetObject
), /* tp_basicsize */
1800 0, /* tp_itemsize */
1802 (destructor
)set_dealloc
, /* tp_dealloc */
1803 (printfunc
)set_tp_print
, /* tp_print */
1806 (cmpfunc
)set_nocmp
, /* tp_compare */
1807 (reprfunc
)set_repr
, /* tp_repr */
1808 &set_as_number
, /* tp_as_number */
1809 &set_as_sequence
, /* tp_as_sequence */
1810 0, /* tp_as_mapping */
1811 set_nohash
, /* tp_hash */
1814 PyObject_GenericGetAttr
, /* tp_getattro */
1815 0, /* tp_setattro */
1816 0, /* tp_as_buffer */
1817 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
| Py_TPFLAGS_CHECKTYPES
|
1818 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1819 set_doc
, /* tp_doc */
1820 (traverseproc
)set_traverse
, /* tp_traverse */
1821 (inquiry
)set_clear_internal
, /* tp_clear */
1822 (richcmpfunc
)set_richcompare
, /* tp_richcompare */
1823 offsetof(PySetObject
, weakreflist
), /* tp_weaklistoffset */
1824 (getiterfunc
)set_iter
, /* tp_iter */
1825 0, /* tp_iternext */
1826 set_methods
, /* tp_methods */
1831 0, /* tp_descr_get */
1832 0, /* tp_descr_set */
1833 0, /* tp_dictoffset */
1834 (initproc
)set_init
, /* tp_init */
1835 PyType_GenericAlloc
, /* tp_alloc */
1836 set_new
, /* tp_new */
1837 PyObject_GC_Del
, /* tp_free */
1840 /* frozenset object ********************************************************/
1843 static PyMethodDef frozenset_methods
[] = {
1844 {"__contains__",(PyCFunction
)set_direct_contains
, METH_O
| METH_COEXIST
,
1846 {"copy", (PyCFunction
)frozenset_copy
, METH_NOARGS
,
1848 {"difference", (PyCFunction
)set_difference
, METH_O
,
1850 {"intersection",(PyCFunction
)set_intersection
, METH_O
,
1852 {"issubset", (PyCFunction
)set_issubset
, METH_O
,
1854 {"issuperset", (PyCFunction
)set_issuperset
, METH_O
,
1856 {"__reduce__", (PyCFunction
)set_reduce
, METH_NOARGS
,
1858 {"symmetric_difference",(PyCFunction
)set_symmetric_difference
, METH_O
,
1859 symmetric_difference_doc
},
1860 {"union", (PyCFunction
)set_union
, METH_O
,
1862 {NULL
, NULL
} /* sentinel */
1865 static PyNumberMethods frozenset_as_number
= {
1867 (binaryfunc
)set_sub
, /*nb_subtract*/
1880 (binaryfunc
)set_and
, /*nb_and*/
1881 (binaryfunc
)set_xor
, /*nb_xor*/
1882 (binaryfunc
)set_or
, /*nb_or*/
1885 PyDoc_STRVAR(frozenset_doc
,
1886 "frozenset(iterable) --> frozenset object\n\
1888 Build an immutable unordered collection.");
1890 PyTypeObject PyFrozenSet_Type
= {
1891 PyObject_HEAD_INIT(&PyType_Type
)
1893 "frozenset", /* tp_name */
1894 sizeof(PySetObject
), /* tp_basicsize */
1895 0, /* tp_itemsize */
1897 (destructor
)set_dealloc
, /* tp_dealloc */
1898 (printfunc
)set_tp_print
, /* tp_print */
1901 (cmpfunc
)set_nocmp
, /* tp_compare */
1902 (reprfunc
)set_repr
, /* tp_repr */
1903 &frozenset_as_number
, /* tp_as_number */
1904 &set_as_sequence
, /* tp_as_sequence */
1905 0, /* tp_as_mapping */
1906 frozenset_hash
, /* tp_hash */
1909 PyObject_GenericGetAttr
, /* tp_getattro */
1910 0, /* tp_setattro */
1911 0, /* tp_as_buffer */
1912 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
| Py_TPFLAGS_CHECKTYPES
|
1913 Py_TPFLAGS_BASETYPE
, /* tp_flags */
1914 frozenset_doc
, /* tp_doc */
1915 (traverseproc
)set_traverse
, /* tp_traverse */
1916 (inquiry
)set_clear_internal
, /* tp_clear */
1917 (richcmpfunc
)set_richcompare
, /* tp_richcompare */
1918 offsetof(PySetObject
, weakreflist
), /* tp_weaklistoffset */
1919 (getiterfunc
)set_iter
, /* tp_iter */
1920 0, /* tp_iternext */
1921 frozenset_methods
, /* tp_methods */
1926 0, /* tp_descr_get */
1927 0, /* tp_descr_set */
1928 0, /* tp_dictoffset */
1930 PyType_GenericAlloc
, /* tp_alloc */
1931 frozenset_new
, /* tp_new */
1932 PyObject_GC_Del
, /* tp_free */
1936 /***** C API functions *************************************************/
1939 PySet_New(PyObject
*iterable
)
1941 return make_new_set(&PySet_Type
, iterable
);
1945 PyFrozenSet_New(PyObject
*iterable
)
1947 PyObject
*args
, *result
;
1949 if (iterable
== NULL
)
1950 args
= PyTuple_New(0);
1952 args
= PyTuple_Pack(1, iterable
);
1955 result
= frozenset_new(&PyFrozenSet_Type
, args
, NULL
);
1961 PySet_Size(PyObject
*anyset
)
1963 if (!PyAnySet_Check(anyset
)) {
1964 PyErr_BadInternalCall();
1967 return PySet_GET_SIZE(anyset
);
1971 PySet_Contains(PyObject
*anyset
, PyObject
*key
)
1973 if (!PyAnySet_Check(anyset
)) {
1974 PyErr_BadInternalCall();
1977 return set_contains_key((PySetObject
*)anyset
, key
);
1981 PySet_Discard(PyObject
*set
, PyObject
*key
)
1983 if (!PyType_IsSubtype(set
->ob_type
, &PySet_Type
)) {
1984 PyErr_BadInternalCall();
1987 return set_discard_key((PySetObject
*)set
, key
);
1991 PySet_Add(PyObject
*set
, PyObject
*key
)
1993 if (!PyType_IsSubtype(set
->ob_type
, &PySet_Type
)) {
1994 PyErr_BadInternalCall();
1997 return set_add_key((PySetObject
*)set
, key
);
2001 PySet_Pop(PyObject
*set
)
2003 if (!PyType_IsSubtype(set
->ob_type
, &PySet_Type
)) {
2004 PyErr_BadInternalCall();
2007 return set_pop((PySetObject
*)set
);
2013 /* Test code to be called with any three element set.
2014 Returns True and original set is restored. */
2016 #define assertRaises(call_return_value, exception) \
2018 assert(call_return_value); \
2019 assert(PyErr_ExceptionMatches(exception)); \
2024 test_c_api(PySetObject
*so
)
2026 PyObject
*elem
, *dup
, *t
, *f
, *ob
= (PyObject
*)so
;
2028 /* Verify preconditions and exercise type/size checks */
2029 assert(PyAnySet_Check(ob
));
2030 assert(PyAnySet_CheckExact(ob
));
2031 assert(!PyFrozenSet_CheckExact(ob
));
2032 assert(PySet_Size(ob
) == 3);
2033 assert(PySet_GET_SIZE(ob
) == 3);
2035 /* Raise TypeError for non-iterable constructor arguments */
2036 assertRaises(PySet_New(Py_None
) == NULL
, PyExc_TypeError
);
2037 assertRaises(PyFrozenSet_New(Py_None
) == NULL
, PyExc_TypeError
);
2039 /* Raise TypeError for unhashable key */
2040 dup
= PySet_New(ob
);
2041 assertRaises(PySet_Discard(ob
, dup
) == -1, PyExc_TypeError
);
2042 assertRaises(PySet_Contains(ob
, dup
) == -1, PyExc_TypeError
);
2043 assertRaises(PySet_Add(ob
, dup
) == -1, PyExc_TypeError
);
2045 /* Exercise successful pop, contains, add, and discard */
2046 elem
= PySet_Pop(ob
);
2047 assert(PySet_Contains(ob
, elem
) == 0);
2048 assert(PySet_GET_SIZE(ob
) == 2);
2049 assert(PySet_Add(ob
, elem
) == 0);
2050 assert(PySet_Contains(ob
, elem
) == 1);
2051 assert(PySet_GET_SIZE(ob
) == 3);
2052 assert(PySet_Discard(ob
, elem
) == 1);
2053 assert(PySet_GET_SIZE(ob
) == 2);
2054 assert(PySet_Discard(ob
, elem
) == 0);
2055 assert(PySet_GET_SIZE(ob
) == 2);
2057 /* Raise SystemError when self argument is not a set or frozenset. */
2059 assertRaises(PySet_Size(t
) == -1, PyExc_SystemError
);
2060 assertRaises(PySet_Contains(t
, elem
) == -1, PyExc_SystemError
);
2063 /* Raise SystemError when self argument is not a set. */
2064 f
= PyFrozenSet_New(dup
);
2065 assert(PySet_Size(f
) == 3);
2066 assert(PyFrozenSet_CheckExact(f
));
2067 assertRaises(PySet_Add(f
, elem
) == -1, PyExc_SystemError
);
2068 assertRaises(PySet_Discard(f
, elem
) == -1, PyExc_SystemError
);
2069 assertRaises(PySet_Pop(f
) == NULL
, PyExc_SystemError
);
2072 /* Raise KeyError when popping from an empty set */
2073 assert(PyNumber_InPlaceSubtract(ob
, ob
) == ob
);
2075 assert(PySet_GET_SIZE(ob
) == 0);
2076 assertRaises(PySet_Pop(ob
) == NULL
, PyExc_KeyError
);
2078 /* Restore the set from the copy using the PyNumber API */
2079 assert(PyNumber_InPlaceOr(ob
, dup
) == ob
);
2082 /* Verify constructors accept NULL arguments */
2083 f
= PySet_New(NULL
);
2085 assert(PySet_GET_SIZE(f
) == 0);
2087 f
= PyFrozenSet_New(NULL
);
2089 assert(PyFrozenSet_CheckExact(f
));
2090 assert(PySet_GET_SIZE(f
) == 0);