blob: fd10008cf1b386d219b14ad66071f0eca382e07d [file] [log] [blame]
Raymond Hettingerc991db22005-08-11 07:58:45 +00001
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002/* set object implementation
Raymond Hettingerae7b00e2013-09-07 15:05:00 -07003
Raymond Hettingera9d99362005-08-05 00:01:15 +00004 Written and maintained by Raymond D. Hettinger <python@rcn.com>
5 Derived from Lib/sets.py and Objects/dictobject.c.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00006
Raymond Hettingerbd9b2002015-01-18 16:10:30 -08007 Copyright (c) 2003-2015 Python Software Foundation.
Raymond Hettingera9d99362005-08-05 00:01:15 +00008 All rights reserved.
Raymond Hettingerae7b00e2013-09-07 15:05:00 -07009
10 The basic lookup function used by all operations.
11 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
12
13 The initial probe index is computed as hash mod the table size.
14 Subsequent probe indices are computed as explained in Objects/dictobject.c.
15
16 To improve cache locality, each probe inspects a series of consecutive
17 nearby entries before moving on to probes elsewhere in memory. This leaves
18 us with a hybrid of linear probing and open addressing. The linear probing
19 reduces the cost of hash collisions because consecutive memory accesses
20 tend to be much cheaper than scattered probes. After LINEAR_PROBES steps,
21 we then use open addressing with the upper bits from the hash value. This
22 helps break-up long chains of collisions.
23
24 All arithmetic on hash should ignore overflow.
25
Raymond Hettinger4d45c102015-01-25 16:27:40 -080026 Unlike the dictionary implementation, the lookkey function can return
Raymond Hettingerae7b00e2013-09-07 15:05:00 -070027 NULL if the rich comparison returns an error.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000028*/
29
Raymond Hettingera690a992003-11-16 16:17:49 +000030#include "Python.h"
Raymond Hettingera9d99362005-08-05 00:01:15 +000031#include "structmember.h"
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000032
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000033/* Object used as dummy key to fill deleted entries */
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -050034static PyObject _dummy_struct;
35
36#define dummy (&_dummy_struct)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000037
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000038
Raymond Hettinger04fd9dd2013-09-07 17:41:01 -070039/* ======================================================================== */
40/* ======= Begin logic for probing the hash table ========================= */
41
Raymond Hettinger710a67e2013-09-21 20:17:31 -070042/* Set this to zero to turn-off linear probing */
Raymond Hettinger8408dc52013-09-15 14:57:15 -070043#ifndef LINEAR_PROBES
Raymond Hettinger742d8712013-09-08 00:25:57 -070044#define LINEAR_PROBES 9
Raymond Hettinger8408dc52013-09-15 14:57:15 -070045#endif
Raymond Hettinger742d8712013-09-08 00:25:57 -070046
47/* This must be >= 1 */
48#define PERTURB_SHIFT 5
49
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000050static setentry *
Antoine Pitrou9ed5f272013-08-13 20:18:52 +020051set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000052{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000053 setentry *table = so->table;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +020054 setentry *entry;
Raymond Hettinger38bb95e2015-06-24 01:22:19 -070055 size_t perturb;
Raymond Hettingerafe89092013-08-28 20:59:31 -070056 size_t mask = so->mask;
Raymond Hettinger59ecabd2015-01-31 02:45:12 -080057 size_t i = (size_t)hash & mask; /* Unsigned for defined overflow behavior */
Raymond Hettinger8408dc52013-09-15 14:57:15 -070058 size_t j;
Raymond Hettinger4ef05282013-09-21 15:39:49 -070059 int cmp;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000060
Raymond Hettinger59ecabd2015-01-31 02:45:12 -080061 entry = &table[i];
Raymond Hettingerafe89092013-08-28 20:59:31 -070062 if (entry->key == NULL)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000063 return entry;
Raymond Hettinger237b34b2013-08-17 02:31:53 -070064
Raymond Hettinger38bb95e2015-06-24 01:22:19 -070065 perturb = hash;
66
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -070067 while (1) {
Raymond Hettingera5ebbf62015-01-26 21:54:35 -080068 if (entry->hash == hash) {
Raymond Hettingerafe89092013-08-28 20:59:31 -070069 PyObject *startkey = entry->key;
Raymond Hettingera5ebbf62015-01-26 21:54:35 -080070 /* startkey cannot be a dummy because the dummy hash field is -1 */
71 assert(startkey != dummy);
Raymond Hettinger08e3dc02014-12-26 20:14:00 -080072 if (startkey == key)
73 return entry;
Raymond Hettinger93035c42015-01-25 16:12:49 -080074 if (PyUnicode_CheckExact(startkey)
75 && PyUnicode_CheckExact(key)
Raymond Hettingerac2ef652015-07-04 16:04:44 -070076 && _PyUnicode_EQ(startkey, key))
Raymond Hettinger93035c42015-01-25 16:12:49 -080077 return entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000078 Py_INCREF(startkey);
79 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
80 Py_DECREF(startkey);
Raymond Hettinger426d9952014-05-18 21:40:20 +010081 if (cmp < 0) /* unlikely */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000082 return NULL;
Raymond Hettinger426d9952014-05-18 21:40:20 +010083 if (table != so->table || entry->key != startkey) /* unlikely */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000084 return set_lookkey(so, key, hash);
Raymond Hettinger426d9952014-05-18 21:40:20 +010085 if (cmp > 0) /* likely */
Raymond Hettingerafe89092013-08-28 20:59:31 -070086 return entry;
Raymond Hettinger438f9132015-02-09 06:48:29 -060087 mask = so->mask; /* help avoid a register spill */
Raymond Hettingerafe89092013-08-28 20:59:31 -070088 }
Raymond Hettingerafe89092013-08-28 20:59:31 -070089
Raymond Hettingerc658d852015-02-02 08:35:00 -080090 if (i + LINEAR_PROBES <= mask) {
Raymond Hettinger82492822015-02-04 08:37:02 -080091 for (j = 0 ; j < LINEAR_PROBES ; j++) {
Raymond Hettingerc658d852015-02-02 08:35:00 -080092 entry++;
Raymond Hettinger8651a502015-05-27 10:37:20 -070093 if (entry->hash == 0 && entry->key == NULL)
94 return entry;
Raymond Hettingerc658d852015-02-02 08:35:00 -080095 if (entry->hash == hash) {
96 PyObject *startkey = entry->key;
97 assert(startkey != dummy);
98 if (startkey == key)
99 return entry;
100 if (PyUnicode_CheckExact(startkey)
101 && PyUnicode_CheckExact(key)
Raymond Hettingerac2ef652015-07-04 16:04:44 -0700102 && _PyUnicode_EQ(startkey, key))
Raymond Hettingerc658d852015-02-02 08:35:00 -0800103 return entry;
104 Py_INCREF(startkey);
105 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
106 Py_DECREF(startkey);
107 if (cmp < 0)
108 return NULL;
109 if (table != so->table || entry->key != startkey)
110 return set_lookkey(so, key, hash);
111 if (cmp > 0)
112 return entry;
Raymond Hettinger438f9132015-02-09 06:48:29 -0600113 mask = so->mask;
Raymond Hettingerc658d852015-02-02 08:35:00 -0800114 }
Raymond Hettinger8651a502015-05-27 10:37:20 -0700115 }
116 }
117
118 perturb >>= PERTURB_SHIFT;
119 i = (i * 5 + 1 + perturb) & mask;
120
121 entry = &table[i];
Raymond Hettinger7e3592d2015-06-21 10:47:20 -0700122 if (entry->key == NULL)
Raymond Hettinger8651a502015-05-27 10:37:20 -0700123 return entry;
124 }
125}
126
Raymond Hettinger15f08692015-07-03 17:21:17 -0700127static int set_table_resize(PySetObject *, Py_ssize_t);
128
Raymond Hettinger8651a502015-05-27 10:37:20 -0700129static int
Raymond Hettinger73799b12015-07-05 16:06:10 -0700130set_add_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger8651a502015-05-27 10:37:20 -0700131{
132 setentry *table = so->table;
Raymond Hettinger38bb95e2015-06-24 01:22:19 -0700133 setentry *freeslot;
Raymond Hettinger8651a502015-05-27 10:37:20 -0700134 setentry *entry;
Raymond Hettinger38bb95e2015-06-24 01:22:19 -0700135 size_t perturb;
Raymond Hettinger8651a502015-05-27 10:37:20 -0700136 size_t mask = so->mask;
137 size_t i = (size_t)hash & mask; /* Unsigned for defined overflow behavior */
138 size_t j;
139 int cmp;
140
141 entry = &table[i];
142 if (entry->key == NULL)
Raymond Hettinger15f08692015-07-03 17:21:17 -0700143 goto found_unused;
Raymond Hettinger6ee588f2015-06-20 21:39:51 -0700144
145 freeslot = NULL;
146 perturb = hash;
Raymond Hettinger8651a502015-05-27 10:37:20 -0700147
148 while (1) {
149 if (entry->hash == hash) {
150 PyObject *startkey = entry->key;
151 /* startkey cannot be a dummy because the dummy hash field is -1 */
152 assert(startkey != dummy);
153 if (startkey == key)
154 goto found_active;
155 if (PyUnicode_CheckExact(startkey)
156 && PyUnicode_CheckExact(key)
Raymond Hettingerac2ef652015-07-04 16:04:44 -0700157 && _PyUnicode_EQ(startkey, key))
Raymond Hettinger8651a502015-05-27 10:37:20 -0700158 goto found_active;
159 Py_INCREF(startkey);
160 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
161 Py_DECREF(startkey);
162 if (cmp < 0) /* unlikely */
163 return -1;
164 if (table != so->table || entry->key != startkey) /* unlikely */
Raymond Hettinger73799b12015-07-05 16:06:10 -0700165 return set_add_entry(so, key, hash);
Raymond Hettinger8651a502015-05-27 10:37:20 -0700166 if (cmp > 0) /* likely */
167 goto found_active;
168 mask = so->mask; /* help avoid a register spill */
169 }
170 if (entry->hash == -1 && freeslot == NULL)
171 freeslot = entry;
172
173 if (i + LINEAR_PROBES <= mask) {
174 for (j = 0 ; j < LINEAR_PROBES ; j++) {
175 entry++;
176 if (entry->hash == 0 && entry->key == NULL)
Raymond Hettinger15f08692015-07-03 17:21:17 -0700177 goto found_unused_or_dummy;
Raymond Hettinger8651a502015-05-27 10:37:20 -0700178 if (entry->hash == hash) {
179 PyObject *startkey = entry->key;
180 assert(startkey != dummy);
181 if (startkey == key)
182 goto found_active;
183 if (PyUnicode_CheckExact(startkey)
184 && PyUnicode_CheckExact(key)
Raymond Hettingerac2ef652015-07-04 16:04:44 -0700185 && _PyUnicode_EQ(startkey, key))
Raymond Hettinger8651a502015-05-27 10:37:20 -0700186 goto found_active;
187 Py_INCREF(startkey);
188 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
189 Py_DECREF(startkey);
190 if (cmp < 0)
191 return -1;
192 if (table != so->table || entry->key != startkey)
Raymond Hettinger73799b12015-07-05 16:06:10 -0700193 return set_add_entry(so, key, hash);
Raymond Hettinger8651a502015-05-27 10:37:20 -0700194 if (cmp > 0)
195 goto found_active;
196 mask = so->mask;
197 }
Raymond Hettinger91672612015-06-26 02:50:21 -0700198 else if (entry->hash == -1 && freeslot == NULL)
Raymond Hettingerc658d852015-02-02 08:35:00 -0800199 freeslot = entry;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700200 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000201 }
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700202
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700203 perturb >>= PERTURB_SHIFT;
Raymond Hettinger59ecabd2015-01-31 02:45:12 -0800204 i = (i * 5 + 1 + perturb) & mask;
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700205
Raymond Hettinger59ecabd2015-01-31 02:45:12 -0800206 entry = &table[i];
Raymond Hettinger7e3592d2015-06-21 10:47:20 -0700207 if (entry->key == NULL)
Raymond Hettinger15f08692015-07-03 17:21:17 -0700208 goto found_unused_or_dummy;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000209 }
Raymond Hettinger8651a502015-05-27 10:37:20 -0700210
Raymond Hettinger15f08692015-07-03 17:21:17 -0700211 found_unused_or_dummy:
212 if (freeslot == NULL)
213 goto found_unused;
214 Py_INCREF(key);
215 so->used++;
216 freeslot->key = key;
217 freeslot->hash = hash;
218 return 0;
219
220 found_unused:
Raymond Hettinger2eff9e92015-06-27 22:03:35 -0700221 Py_INCREF(key);
Raymond Hettinger6ee588f2015-06-20 21:39:51 -0700222 so->fill++;
223 so->used++;
224 entry->key = key;
225 entry->hash = hash;
Raymond Hettinger15f08692015-07-03 17:21:17 -0700226 if ((size_t)so->fill*3 < mask*2)
227 return 0;
Raymond Hettinger48973002015-07-03 20:00:03 -0700228 return set_table_resize(so, so->used);
Raymond Hettinger8651a502015-05-27 10:37:20 -0700229
230 found_active:
Raymond Hettinger8651a502015-05-27 10:37:20 -0700231 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000232}
233
234/*
Thomas Wouters89f507f2006-12-13 04:49:30 +0000235Internal routine used by set_table_resize() to insert an item which is
236known to be absent from the set. This routine also assumes that
237the set contains no deleted entries. Besides the performance benefit,
238using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
239Note that no refcounts are changed by this routine; if needed, the caller
240is responsible for incref'ing `key`.
241*/
242static void
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200243set_insert_clean(PySetObject *so, PyObject *key, Py_hash_t hash)
Thomas Wouters89f507f2006-12-13 04:49:30 +0000244{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000245 setentry *table = so->table;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200246 setentry *entry;
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700247 size_t perturb = hash;
248 size_t mask = (size_t)so->mask;
Raymond Hettinger3037e842015-01-26 21:33:48 -0800249 size_t i = (size_t)hash & mask;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700250 size_t j;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000251
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700252 while (1) {
Raymond Hettinger3037e842015-01-26 21:33:48 -0800253 entry = &table[i];
254 if (entry->key == NULL)
255 goto found_null;
256 if (i + LINEAR_PROBES <= mask) {
Raymond Hettinger82492822015-02-04 08:37:02 -0800257 for (j = 0; j < LINEAR_PROBES; j++) {
Raymond Hettinger9edd7532015-01-30 20:09:23 -0800258 entry++;
Raymond Hettinger3037e842015-01-26 21:33:48 -0800259 if (entry->key == NULL)
260 goto found_null;
261 }
Raymond Hettingera35adf52013-09-02 03:23:21 -0700262 }
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700263 perturb >>= PERTURB_SHIFT;
Raymond Hettinger3037e842015-01-26 21:33:48 -0800264 i = (i * 5 + 1 + perturb) & mask;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000265 }
Raymond Hettingera35adf52013-09-02 03:23:21 -0700266 found_null:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000267 entry->key = key;
268 entry->hash = hash;
Raymond Hettinger4ef05282013-09-21 15:39:49 -0700269 so->fill++;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000270 so->used++;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000271}
272
Raymond Hettinger04fd9dd2013-09-07 17:41:01 -0700273/* ======== End logic for probing the hash table ========================== */
274/* ======================================================================== */
275
Thomas Wouters89f507f2006-12-13 04:49:30 +0000276/*
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000277Restructure the table by allocating a new table and reinserting all
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000278keys again. When entries have been deleted, the new table may
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000279actually be smaller than the old one.
280*/
281static int
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000282set_table_resize(PySetObject *so, Py_ssize_t minused)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000283{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000284 Py_ssize_t newsize;
285 setentry *oldtable, *newtable, *entry;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800286 Py_ssize_t oldfill = so->fill;
287 Py_ssize_t oldused = so->used;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000288 int is_oldtable_malloced;
289 setentry small_copy[PySet_MINSIZE];
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000290
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000291 assert(minused >= 0);
Raymond Hettinger48973002015-07-03 20:00:03 -0700292 minused = (minused > 50000) ? minused * 2 : minused * 4;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000293
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000294 /* Find the smallest table size > minused. */
Raymond Hettinger426d9952014-05-18 21:40:20 +0100295 /* XXX speed-up with intrinsics */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000296 for (newsize = PySet_MINSIZE;
297 newsize <= minused && newsize > 0;
298 newsize <<= 1)
299 ;
300 if (newsize <= 0) {
301 PyErr_NoMemory();
302 return -1;
303 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000304
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000305 /* Get space for a new table. */
306 oldtable = so->table;
307 assert(oldtable != NULL);
308 is_oldtable_malloced = oldtable != so->smalltable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000309
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000310 if (newsize == PySet_MINSIZE) {
311 /* A large table is shrinking, or we can't get any smaller. */
312 newtable = so->smalltable;
313 if (newtable == oldtable) {
314 if (so->fill == so->used) {
315 /* No dummies, so no point doing anything. */
316 return 0;
317 }
318 /* We're not going to resize it, but rebuild the
319 table anyway to purge old dummy entries.
320 Subtle: This is *necessary* if fill==size,
321 as set_lookkey needs at least one virgin slot to
322 terminate failing searches. If fill < size, it's
323 merely desirable, as dummies slow searches. */
324 assert(so->fill > so->used);
325 memcpy(small_copy, oldtable, sizeof(small_copy));
326 oldtable = small_copy;
327 }
328 }
329 else {
330 newtable = PyMem_NEW(setentry, newsize);
331 if (newtable == NULL) {
332 PyErr_NoMemory();
333 return -1;
334 }
335 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000336
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000337 /* Make the set empty, using the new table. */
338 assert(newtable != oldtable);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000339 memset(newtable, 0, sizeof(setentry) * newsize);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000340 so->fill = 0;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800341 so->used = 0;
342 so->mask = newsize - 1;
343 so->table = newtable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000344
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000345 /* Copy the data over; this is refcount-neutral for active entries;
346 dummy entries aren't copied over, of course */
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800347 if (oldfill == oldused) {
348 for (entry = oldtable; oldused > 0; entry++) {
349 if (entry->key != NULL) {
350 oldused--;
351 set_insert_clean(so, entry->key, entry->hash);
352 }
353 }
354 } else {
355 for (entry = oldtable; oldused > 0; entry++) {
356 if (entry->key != NULL && entry->key != dummy) {
357 oldused--;
358 set_insert_clean(so, entry->key, entry->hash);
359 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000360 }
361 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000362
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000363 if (is_oldtable_malloced)
364 PyMem_DEL(oldtable);
365 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000366}
367
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000368static int
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200369set_add_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000370{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200371 Py_hash_t hash;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000372
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000373 if (!PyUnicode_CheckExact(key) ||
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200374 (hash = ((PyASCIIObject *) key)->hash) == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000375 hash = PyObject_Hash(key);
376 if (hash == -1)
377 return -1;
378 }
Raymond Hettinger73799b12015-07-05 16:06:10 -0700379 return set_add_entry(so, key, hash);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000380}
381
382#define DISCARD_NOTFOUND 0
383#define DISCARD_FOUND 1
384
385static int
Raymond Hettinger73799b12015-07-05 16:06:10 -0700386set_discard_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800387{
388 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000389 PyObject *old_key;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000390
Raymond Hettingerdc28d5a2015-07-05 10:03:20 -0700391 entry = set_lookkey(so, key, hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000392 if (entry == NULL)
393 return -1;
Raymond Hettinger8651a502015-05-27 10:37:20 -0700394 if (entry->key == NULL)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000395 return DISCARD_NOTFOUND;
396 old_key = entry->key;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000397 entry->key = dummy;
Raymond Hettingerb335dfe2015-01-25 16:38:52 -0800398 entry->hash = -1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000399 so->used--;
400 Py_DECREF(old_key);
401 return DISCARD_FOUND;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000402}
403
404static int
405set_discard_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000406{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200407 Py_hash_t hash;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000408
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000409 assert (PyAnySet_Check(so));
Christian Heimes0ded5b52007-12-10 15:50:56 +0000410
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000411 if (!PyUnicode_CheckExact(key) ||
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200412 (hash = ((PyASCIIObject *) key)->hash) == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000413 hash = PyObject_Hash(key);
414 if (hash == -1)
415 return -1;
416 }
Raymond Hettinger73799b12015-07-05 16:06:10 -0700417 return set_discard_entry(so, key, hash);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000418}
419
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700420static void
421set_empty_to_minsize(PySetObject *so)
422{
423 memset(so->smalltable, 0, sizeof(so->smalltable));
424 so->fill = 0;
425 so->used = 0;
426 so->mask = PySet_MINSIZE - 1;
427 so->table = so->smalltable;
428 so->hash = -1;
429}
430
Raymond Hettingerfe889f32005-08-06 05:43:39 +0000431static int
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000432set_clear_internal(PySetObject *so)
433{
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800434 setentry *entry;
435 setentry *table = so->table;
436 Py_ssize_t fill = so->fill;
437 Py_ssize_t used = so->used;
438 int table_is_malloced = table != so->smalltable;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000439 setentry small_copy[PySet_MINSIZE];
Raymond Hettingera580c472005-08-05 17:19:54 +0000440
Raymond Hettinger583cd032013-09-07 22:06:35 -0700441 assert (PyAnySet_Check(so));
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000442 assert(table != NULL);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000443
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000444 /* This is delicate. During the process of clearing the set,
445 * decrefs can cause the set to mutate. To avoid fatal confusion
446 * (voice of experience), we have to make the set empty before
447 * clearing the slots, and never refer to anything via so->ref while
448 * clearing.
449 */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000450 if (table_is_malloced)
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700451 set_empty_to_minsize(so);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000452
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000453 else if (fill > 0) {
454 /* It's a small table with something that needs to be cleared.
455 * Afraid the only safe way is to copy the set entries into
456 * another small table first.
457 */
458 memcpy(small_copy, table, sizeof(small_copy));
459 table = small_copy;
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700460 set_empty_to_minsize(so);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000461 }
462 /* else it's a small table that's already empty */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000463
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000464 /* Now we can finally clear things. If C had refcounts, we could
465 * assert that the refcount on table is 1 now, i.e. that this function
466 * has unique access to it, so decref side-effects can't alter it.
467 */
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800468 for (entry = table; used > 0; entry++) {
469 if (entry->key && entry->key != dummy) {
470 used--;
471 Py_DECREF(entry->key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000472 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000473 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000474
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000475 if (table_is_malloced)
476 PyMem_DEL(table);
477 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000478}
479
480/*
481 * Iterate over a set table. Use like so:
482 *
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000483 * Py_ssize_t pos;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000484 * setentry *entry;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000485 * pos = 0; # important! pos should not otherwise be changed by you
Raymond Hettingerc991db22005-08-11 07:58:45 +0000486 * while (set_next(yourset, &pos, &entry)) {
487 * Refer to borrowed reference in entry->key.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000488 * }
489 *
Raymond Hettingerc991db22005-08-11 07:58:45 +0000490 * CAUTION: In general, it isn't safe to use set_next in a loop that
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000491 * mutates the table.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000492 */
493static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000494set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000495{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000496 Py_ssize_t i;
497 Py_ssize_t mask;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200498 setentry *table;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000499
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000500 assert (PyAnySet_Check(so));
501 i = *pos_ptr;
502 assert(i >= 0);
503 table = so->table;
504 mask = so->mask;
505 while (i <= mask && (table[i].key == NULL || table[i].key == dummy))
506 i++;
507 *pos_ptr = i+1;
508 if (i > mask)
509 return 0;
510 assert(table[i].key != NULL);
511 *entry_ptr = &table[i];
512 return 1;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000513}
514
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000515static void
516set_dealloc(PySetObject *so)
517{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200518 setentry *entry;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800519 Py_ssize_t used = so->used;
520
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000521 PyObject_GC_UnTrack(so);
522 Py_TRASHCAN_SAFE_BEGIN(so)
523 if (so->weakreflist != NULL)
524 PyObject_ClearWeakRefs((PyObject *) so);
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000525
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800526 for (entry = so->table; used > 0; entry++) {
527 if (entry->key && entry->key != dummy) {
528 used--;
Raymond Hettingerfcf3b502013-08-22 08:20:31 -0700529 Py_DECREF(entry->key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000530 }
531 }
532 if (so->table != so->smalltable)
533 PyMem_DEL(so->table);
Raymond Hettinger8f8839e2013-09-07 20:26:50 -0700534 Py_TYPE(so)->tp_free(so);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000535 Py_TRASHCAN_SAFE_END(so)
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000536}
537
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000538static PyObject *
539set_repr(PySetObject *so)
540{
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200541 PyObject *result=NULL, *keys, *listrepr, *tmp;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000542 int status = Py_ReprEnter((PyObject*)so);
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000543
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000544 if (status != 0) {
545 if (status < 0)
546 return NULL;
547 return PyUnicode_FromFormat("%s(...)", Py_TYPE(so)->tp_name);
548 }
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000549
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000550 /* shortcut for the empty set */
551 if (!so->used) {
552 Py_ReprLeave((PyObject*)so);
553 return PyUnicode_FromFormat("%s()", Py_TYPE(so)->tp_name);
554 }
Georg Brandlc4996ba2006-08-28 19:37:11 +0000555
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000556 keys = PySequence_List((PyObject *)so);
557 if (keys == NULL)
558 goto done;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000559
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200560 /* repr(keys)[1:-1] */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000561 listrepr = PyObject_Repr(keys);
562 Py_DECREF(keys);
563 if (listrepr == NULL)
564 goto done;
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200565 tmp = PyUnicode_Substring(listrepr, 1, PyUnicode_GET_LENGTH(listrepr)-1);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000566 Py_DECREF(listrepr);
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200567 if (tmp == NULL)
568 goto done;
569 listrepr = tmp;
Victor Stinnera1a807b2011-05-26 14:24:30 +0200570
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200571 if (Py_TYPE(so) != &PySet_Type)
572 result = PyUnicode_FromFormat("%s({%U})",
573 Py_TYPE(so)->tp_name,
574 listrepr);
575 else
576 result = PyUnicode_FromFormat("{%U}", listrepr);
577 Py_DECREF(listrepr);
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000578done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000579 Py_ReprLeave((PyObject*)so);
580 return result;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000581}
582
Martin v. Löwis18e16552006-02-15 17:27:45 +0000583static Py_ssize_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000584set_len(PyObject *so)
585{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000586 return ((PySetObject *)so)->used;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000587}
588
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000589static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000590set_merge(PySetObject *so, PyObject *otherset)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000591{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000592 PySetObject *other;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000593 PyObject *key;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200594 Py_ssize_t i;
Raymond Hettinger1bd8d752015-05-13 01:26:14 -0700595 setentry *so_entry;
596 setentry *other_entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000597
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000598 assert (PyAnySet_Check(so));
599 assert (PyAnySet_Check(otherset));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000600
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000601 other = (PySetObject*)otherset;
602 if (other == so || other->used == 0)
Raymond Hettinger1bd8d752015-05-13 01:26:14 -0700603 /* a.update(a) or a.update(set()); nothing to do */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000604 return 0;
605 /* Do one big resize at the start, rather than
606 * incrementally resizing as we insert new keys. Expect
607 * that there will be no (or few) overlapping keys.
608 */
Raymond Hettinger15f08692015-07-03 17:21:17 -0700609 if ((so->fill + other->used)*3 >= so->mask*2) {
Raymond Hettinger48973002015-07-03 20:00:03 -0700610 if (set_table_resize(so, so->used + other->used) != 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000611 return -1;
612 }
Raymond Hettinger1bd8d752015-05-13 01:26:14 -0700613 so_entry = so->table;
614 other_entry = other->table;
615
616 /* If our table is empty, and both tables have the same size, and
617 there are no dummies to eliminate, then just copy the pointers. */
618 if (so->fill == 0 && so->mask == other->mask && other->fill == other->used) {
619 for (i = 0; i <= other->mask; i++, so_entry++, other_entry++) {
620 key = other_entry->key;
621 if (key != NULL) {
622 assert(so_entry->key == NULL);
623 Py_INCREF(key);
624 so_entry->key = key;
625 so_entry->hash = other_entry->hash;
626 }
627 }
628 so->fill = other->fill;
629 so->used = other->used;
630 return 0;
631 }
632
633 /* If our table is empty, we can use set_insert_clean() */
634 if (so->fill == 0) {
635 for (i = 0; i <= other->mask; i++, other_entry++) {
636 key = other_entry->key;
637 if (key != NULL && key != dummy) {
638 Py_INCREF(key);
639 set_insert_clean(so, key, other_entry->hash);
640 }
641 }
642 return 0;
643 }
644
645 /* We can't assure there are no duplicates, so do normal insertions */
646 for (i = 0; i <= other->mask; i++, other_entry++) {
647 key = other_entry->key;
648 if (key != NULL && key != dummy) {
Raymond Hettinger73799b12015-07-05 16:06:10 -0700649 if (set_add_entry(so, key, other_entry->hash))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000650 return -1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000651 }
652 }
653 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000654}
655
656static int
Raymond Hettinger73799b12015-07-05 16:06:10 -0700657set_contains_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettingerc991db22005-08-11 07:58:45 +0000658{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000659 setentry *lu_entry;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000660
Raymond Hettingerdc28d5a2015-07-05 10:03:20 -0700661 lu_entry = set_lookkey(so, key, hash);
662 if (lu_entry != NULL)
663 return lu_entry->key != NULL;
664 return -1;
665}
666
667static int
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800668set_contains_key(PySetObject *so, PyObject *key)
669{
Raymond Hettinger3c1f52e2015-07-03 18:31:09 -0700670 setentry *entry;
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800671 Py_hash_t hash;
672
673 if (!PyUnicode_CheckExact(key) ||
674 (hash = ((PyASCIIObject *) key)->hash) == -1) {
675 hash = PyObject_Hash(key);
676 if (hash == -1)
677 return -1;
678 }
Raymond Hettinger3c1f52e2015-07-03 18:31:09 -0700679 entry = set_lookkey(so, key, hash);
680 if (entry == NULL)
681 return -1;
682 return entry->key != NULL;
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800683}
684
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000685static PyObject *
686set_pop(PySetObject *so)
687{
Raymond Hettinger9cd6a782015-01-18 16:06:18 -0800688 /* Make sure the search finger is in bounds */
689 Py_ssize_t i = so->finger & so->mask;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200690 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000691 PyObject *key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000692
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000693 assert (PyAnySet_Check(so));
694 if (so->used == 0) {
695 PyErr_SetString(PyExc_KeyError, "pop from an empty set");
696 return NULL;
697 }
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000698
Raymond Hettinger1202a472015-01-18 13:12:42 -0800699 while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
700 i++;
Raymond Hettingered741d42015-01-18 21:25:15 -0800701 if (i > so->mask)
702 i = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000703 }
704 key = entry->key;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000705 entry->key = dummy;
Raymond Hettingerb335dfe2015-01-25 16:38:52 -0800706 entry->hash = -1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000707 so->used--;
Raymond Hettinger1202a472015-01-18 13:12:42 -0800708 so->finger = i + 1; /* next place to start */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000709 return key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000710}
711
Benjamin Petersonf10a79a2008-10-11 00:49:57 +0000712PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\
713Raises KeyError if the set is empty.");
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000714
715static int
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000716set_traverse(PySetObject *so, visitproc visit, void *arg)
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000717{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000718 Py_ssize_t pos = 0;
719 setentry *entry;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000720
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000721 while (set_next(so, &pos, &entry))
722 Py_VISIT(entry->key);
723 return 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000724}
725
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000726static Py_hash_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000727frozenset_hash(PyObject *self)
728{
Raymond Hettinger74fc8c42014-01-05 12:00:31 -0800729 /* Most of the constants in this hash algorithm are randomly choosen
730 large primes with "interesting bit patterns" and that passed
731 tests for good collision statistics on a variety of problematic
732 datasets such as:
733
734 ps = []
735 for r in range(21):
736 ps += itertools.combinations(range(20), r)
737 num_distinct_hashes = len({hash(frozenset(s)) for s in ps})
738
739 */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000740 PySetObject *so = (PySetObject *)self;
Gregory P. Smith27cbcd62012-12-10 18:15:46 -0800741 Py_uhash_t h, hash = 1927868237UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000742 setentry *entry;
743 Py_ssize_t pos = 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000744
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000745 if (so->hash != -1)
746 return so->hash;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000747
Mark Dickinson57e683e2011-09-24 18:18:40 +0100748 hash *= (Py_uhash_t)PySet_GET_SIZE(self) + 1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000749 while (set_next(so, &pos, &entry)) {
750 /* Work to increase the bit dispersion for closely spaced hash
Raymond Hettinger06a1c8d2015-01-30 18:02:15 -0800751 values. This is important because some use cases have many
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000752 combinations of a small number of elements with nearby
753 hashes so that many distinct combinations collapse to only
754 a handful of distinct hash values. */
Antoine Pitroufbb1c612010-10-23 17:37:54 +0000755 h = entry->hash;
Raymond Hettinger74fc8c42014-01-05 12:00:31 -0800756 hash ^= ((h ^ 89869747UL) ^ (h << 16)) * 3644798167UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000757 }
Raymond Hettinger74fc8c42014-01-05 12:00:31 -0800758 /* Make the final result spread-out in a different pattern
Eric V. Smith6ba56652014-01-14 08:15:03 -0500759 than the algorithm for tuples or other python objects. */
Gregory P. Smithc2176e42012-12-10 18:32:53 -0800760 hash = hash * 69069U + 907133923UL;
Victor Stinner12174a52014-08-15 23:17:38 +0200761 if (hash == (Py_uhash_t)-1)
Gregory P. Smith27cbcd62012-12-10 18:15:46 -0800762 hash = 590923713UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000763 so->hash = hash;
764 return hash;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000765}
766
Raymond Hettingera9d99362005-08-05 00:01:15 +0000767/***** Set iterator type ***********************************************/
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000768
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000769typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000770 PyObject_HEAD
771 PySetObject *si_set; /* Set to NULL when iterator is exhausted */
772 Py_ssize_t si_used;
773 Py_ssize_t si_pos;
774 Py_ssize_t len;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000775} setiterobject;
776
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000777static void
778setiter_dealloc(setiterobject *si)
779{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000780 Py_XDECREF(si->si_set);
781 PyObject_GC_Del(si);
Antoine Pitrou7ddda782009-01-01 15:35:33 +0000782}
783
784static int
785setiter_traverse(setiterobject *si, visitproc visit, void *arg)
786{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000787 Py_VISIT(si->si_set);
788 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000789}
790
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000791static PyObject *
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000792setiter_len(setiterobject *si)
793{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000794 Py_ssize_t len = 0;
795 if (si->si_set != NULL && si->si_used == si->si_set->used)
796 len = si->len;
Antoine Pitrou671b4d92010-08-17 17:55:07 +0000797 return PyLong_FromSsize_t(len);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000798}
799
Armin Rigof5b3e362006-02-11 21:32:43 +0000800PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000801
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000802static PyObject *setiter_iternext(setiterobject *si);
803
804static PyObject *
805setiter_reduce(setiterobject *si)
806{
807 PyObject *list;
808 setiterobject tmp;
809
810 list = PyList_New(0);
811 if (!list)
812 return NULL;
813
Ezio Melotti0e1af282012-09-28 16:43:40 +0300814 /* copy the iterator state */
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000815 tmp = *si;
816 Py_XINCREF(tmp.si_set);
Ezio Melotti0e1af282012-09-28 16:43:40 +0300817
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000818 /* iterate the temporary into a list */
819 for(;;) {
820 PyObject *element = setiter_iternext(&tmp);
821 if (element) {
822 if (PyList_Append(list, element)) {
823 Py_DECREF(element);
824 Py_DECREF(list);
825 Py_XDECREF(tmp.si_set);
826 return NULL;
827 }
828 Py_DECREF(element);
829 } else
830 break;
831 }
832 Py_XDECREF(tmp.si_set);
833 /* check for error */
834 if (tmp.si_set != NULL) {
835 /* we have an error */
836 Py_DECREF(list);
837 return NULL;
838 }
Antoine Pitroua7013882012-04-05 00:04:20 +0200839 return Py_BuildValue("N(N)", _PyObject_GetBuiltin("iter"), list);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000840}
841
842PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
843
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000844static PyMethodDef setiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000845 {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000846 {"__reduce__", (PyCFunction)setiter_reduce, METH_NOARGS, reduce_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000847 {NULL, NULL} /* sentinel */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000848};
849
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000850static PyObject *setiter_iternext(setiterobject *si)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000851{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000852 PyObject *key;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200853 Py_ssize_t i, mask;
854 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000855 PySetObject *so = si->si_set;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000856
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000857 if (so == NULL)
858 return NULL;
859 assert (PyAnySet_Check(so));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000860
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000861 if (si->si_used != so->used) {
862 PyErr_SetString(PyExc_RuntimeError,
863 "Set changed size during iteration");
864 si->si_used = -1; /* Make this state sticky */
865 return NULL;
866 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000867
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000868 i = si->si_pos;
869 assert(i>=0);
870 entry = so->table;
871 mask = so->mask;
872 while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
873 i++;
874 si->si_pos = i+1;
875 if (i > mask)
876 goto fail;
877 si->len--;
878 key = entry[i].key;
879 Py_INCREF(key);
880 return key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000881
882fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000883 Py_DECREF(so);
884 si->si_set = NULL;
885 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000886}
887
Christian Heimesa22e8bd2007-11-29 22:35:39 +0000888PyTypeObject PySetIter_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000889 PyVarObject_HEAD_INIT(&PyType_Type, 0)
890 "set_iterator", /* tp_name */
891 sizeof(setiterobject), /* tp_basicsize */
892 0, /* tp_itemsize */
893 /* methods */
894 (destructor)setiter_dealloc, /* tp_dealloc */
895 0, /* tp_print */
896 0, /* tp_getattr */
897 0, /* tp_setattr */
898 0, /* tp_reserved */
899 0, /* tp_repr */
900 0, /* tp_as_number */
901 0, /* tp_as_sequence */
902 0, /* tp_as_mapping */
903 0, /* tp_hash */
904 0, /* tp_call */
905 0, /* tp_str */
906 PyObject_GenericGetAttr, /* tp_getattro */
907 0, /* tp_setattro */
908 0, /* tp_as_buffer */
909 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
910 0, /* tp_doc */
911 (traverseproc)setiter_traverse, /* tp_traverse */
912 0, /* tp_clear */
913 0, /* tp_richcompare */
914 0, /* tp_weaklistoffset */
915 PyObject_SelfIter, /* tp_iter */
916 (iternextfunc)setiter_iternext, /* tp_iternext */
917 setiter_methods, /* tp_methods */
918 0,
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000919};
920
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000921static PyObject *
922set_iter(PySetObject *so)
923{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000924 setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type);
925 if (si == NULL)
926 return NULL;
927 Py_INCREF(so);
928 si->si_set = so;
929 si->si_used = so->used;
930 si->si_pos = 0;
931 si->len = so->used;
932 _PyObject_GC_TRACK(si);
933 return (PyObject *)si;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000934}
935
Raymond Hettingerd7946662005-08-01 21:39:29 +0000936static int
Raymond Hettingerd7946662005-08-01 21:39:29 +0000937set_update_internal(PySetObject *so, PyObject *other)
Raymond Hettingera690a992003-11-16 16:17:49 +0000938{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000939 PyObject *key, *it;
Raymond Hettingera690a992003-11-16 16:17:49 +0000940
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000941 if (PyAnySet_Check(other))
942 return set_merge(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +0000943
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000944 if (PyDict_CheckExact(other)) {
945 PyObject *value;
946 Py_ssize_t pos = 0;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000947 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000948 Py_ssize_t dictsize = PyDict_Size(other);
Thomas Wouterscf297e42007-02-23 15:07:44 +0000949
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000950 /* Do one big resize at the start, rather than
951 * incrementally resizing as we insert new keys. Expect
952 * that there will be no (or few) overlapping keys.
953 */
Raymond Hettingerc2480dc2015-07-04 08:46:31 -0700954 if (dictsize < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000955 return -1;
Raymond Hettinger15f08692015-07-03 17:21:17 -0700956 if ((so->fill + dictsize)*3 >= so->mask*2) {
Raymond Hettinger48973002015-07-03 20:00:03 -0700957 if (set_table_resize(so, so->used + dictsize) != 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000958 return -1;
959 }
960 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
Raymond Hettinger73799b12015-07-05 16:06:10 -0700961 if (set_add_entry(so, key, hash))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000962 return -1;
963 }
964 return 0;
965 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000966
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000967 it = PyObject_GetIter(other);
968 if (it == NULL)
969 return -1;
Raymond Hettingera690a992003-11-16 16:17:49 +0000970
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000971 while ((key = PyIter_Next(it)) != NULL) {
Raymond Hettinger5af9e132015-05-13 01:44:36 -0700972 if (set_add_key(so, key)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000973 Py_DECREF(it);
974 Py_DECREF(key);
975 return -1;
976 }
977 Py_DECREF(key);
978 }
979 Py_DECREF(it);
980 if (PyErr_Occurred())
981 return -1;
982 return 0;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000983}
984
985static PyObject *
Georg Brandlc28e1fa2008-06-10 19:20:26 +0000986set_update(PySetObject *so, PyObject *args)
Raymond Hettingerd7946662005-08-01 21:39:29 +0000987{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000988 Py_ssize_t i;
Georg Brandlc28e1fa2008-06-10 19:20:26 +0000989
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000990 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
991 PyObject *other = PyTuple_GET_ITEM(args, i);
Raymond Hettinger5af9e132015-05-13 01:44:36 -0700992 if (set_update_internal(so, other))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000993 return NULL;
994 }
995 Py_RETURN_NONE;
Raymond Hettingera38123e2003-11-24 22:18:49 +0000996}
997
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000998PyDoc_STRVAR(update_doc,
Georg Brandlc28e1fa2008-06-10 19:20:26 +0000999"Update a set with the union of itself and others.");
Raymond Hettingera38123e2003-11-24 22:18:49 +00001000
Raymond Hettinger426d9952014-05-18 21:40:20 +01001001/* XXX Todo:
1002 If aligned memory allocations become available, make the
1003 set object 64 byte aligned so that most of the fields
1004 can be retrieved or updated in a single cache line.
1005*/
1006
Raymond Hettingera38123e2003-11-24 22:18:49 +00001007static PyObject *
1008make_new_set(PyTypeObject *type, PyObject *iterable)
1009{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +02001010 PySetObject *so = NULL;
Raymond Hettingera38123e2003-11-24 22:18:49 +00001011
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001012 /* create PySetObject structure */
Raymond Hettinger8f8839e2013-09-07 20:26:50 -07001013 so = (PySetObject *)type->tp_alloc(type, 0);
1014 if (so == NULL)
1015 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001016
Raymond Hettinger4ea90802013-09-07 21:01:29 -07001017 so->fill = 0;
1018 so->used = 0;
1019 so->mask = PySet_MINSIZE - 1;
1020 so->table = so->smalltable;
Raymond Hettinger4ea90802013-09-07 21:01:29 -07001021 so->hash = -1;
Raymond Hettinger1202a472015-01-18 13:12:42 -08001022 so->finger = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001023 so->weakreflist = NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001024
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001025 if (iterable != NULL) {
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001026 if (set_update_internal(so, iterable)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001027 Py_DECREF(so);
1028 return NULL;
1029 }
1030 }
Raymond Hettingera38123e2003-11-24 22:18:49 +00001031
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001032 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001033}
1034
Raymond Hettinger7d99f092008-11-16 11:44:54 +00001035static PyObject *
1036make_new_set_basetype(PyTypeObject *type, PyObject *iterable)
1037{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001038 if (type != &PySet_Type && type != &PyFrozenSet_Type) {
1039 if (PyType_IsSubtype(type, &PySet_Type))
1040 type = &PySet_Type;
1041 else
1042 type = &PyFrozenSet_Type;
1043 }
1044 return make_new_set(type, iterable);
Raymond Hettinger7d99f092008-11-16 11:44:54 +00001045}
1046
Raymond Hettingerd7946662005-08-01 21:39:29 +00001047/* The empty frozenset is a singleton */
1048static PyObject *emptyfrozenset = NULL;
1049
Raymond Hettingera690a992003-11-16 16:17:49 +00001050static PyObject *
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001051frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
Raymond Hettingera690a992003-11-16 16:17:49 +00001052{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001053 PyObject *iterable = NULL, *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001054
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001055 if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds))
1056 return NULL;
Georg Brandl02c42872005-08-26 06:42:30 +00001057
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001058 if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
1059 return NULL;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001060
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001061 if (type != &PyFrozenSet_Type)
1062 return make_new_set(type, iterable);
Raymond Hettingerd7946662005-08-01 21:39:29 +00001063
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001064 if (iterable != NULL) {
1065 /* frozenset(f) is idempotent */
1066 if (PyFrozenSet_CheckExact(iterable)) {
1067 Py_INCREF(iterable);
1068 return iterable;
1069 }
1070 result = make_new_set(type, iterable);
1071 if (result == NULL || PySet_GET_SIZE(result))
1072 return result;
1073 Py_DECREF(result);
1074 }
1075 /* The empty frozenset is a singleton */
1076 if (emptyfrozenset == NULL)
1077 emptyfrozenset = make_new_set(type, NULL);
1078 Py_XINCREF(emptyfrozenset);
1079 return emptyfrozenset;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001080}
1081
Antoine Pitrou093ce9c2011-12-16 11:24:27 +01001082int
1083PySet_ClearFreeList(void)
Raymond Hettingerd7946662005-08-01 21:39:29 +00001084{
Raymond Hettinger8f8839e2013-09-07 20:26:50 -07001085 return 0;
Antoine Pitrou093ce9c2011-12-16 11:24:27 +01001086}
1087
1088void
1089PySet_Fini(void)
1090{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001091 Py_CLEAR(emptyfrozenset);
Raymond Hettingera690a992003-11-16 16:17:49 +00001092}
1093
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001094static PyObject *
1095set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1096{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001097 if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds))
1098 return NULL;
1099
1100 return make_new_set(type, NULL);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001101}
1102
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001103/* set_swap_bodies() switches the contents of any two sets by moving their
1104 internal data pointers and, if needed, copying the internal smalltables.
1105 Semantically equivalent to:
1106
1107 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1108
1109 The function always succeeds and it leaves both objects in a stable state.
Raymond Hettinger4d45c102015-01-25 16:27:40 -08001110 Useful for operations that update in-place (by allowing an intermediate
1111 result to be swapped into one of the original inputs).
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001112*/
1113
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001114static void
1115set_swap_bodies(PySetObject *a, PySetObject *b)
Raymond Hettingera690a992003-11-16 16:17:49 +00001116{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001117 Py_ssize_t t;
1118 setentry *u;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001119 setentry tab[PySet_MINSIZE];
Antoine Pitroufbb1c612010-10-23 17:37:54 +00001120 Py_hash_t h;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001121
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001122 t = a->fill; a->fill = b->fill; b->fill = t;
1123 t = a->used; a->used = b->used; b->used = t;
1124 t = a->mask; a->mask = b->mask; b->mask = t;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001125
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001126 u = a->table;
1127 if (a->table == a->smalltable)
1128 u = b->smalltable;
1129 a->table = b->table;
1130 if (b->table == b->smalltable)
1131 a->table = a->smalltable;
1132 b->table = u;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001133
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001134 if (a->table == a->smalltable || b->table == b->smalltable) {
1135 memcpy(tab, a->smalltable, sizeof(tab));
1136 memcpy(a->smalltable, b->smalltable, sizeof(tab));
1137 memcpy(b->smalltable, tab, sizeof(tab));
1138 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001139
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001140 if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type) &&
1141 PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) {
1142 h = a->hash; a->hash = b->hash; b->hash = h;
1143 } else {
1144 a->hash = -1;
1145 b->hash = -1;
1146 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001147}
1148
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001149static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001150set_copy(PySetObject *so)
1151{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001152 return make_new_set_basetype(Py_TYPE(so), (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001153}
1154
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001155static PyObject *
1156frozenset_copy(PySetObject *so)
1157{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001158 if (PyFrozenSet_CheckExact(so)) {
1159 Py_INCREF(so);
1160 return (PyObject *)so;
1161 }
1162 return set_copy(so);
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001163}
1164
Raymond Hettingera690a992003-11-16 16:17:49 +00001165PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
1166
1167static PyObject *
Raymond Hettingerc991db22005-08-11 07:58:45 +00001168set_clear(PySetObject *so)
1169{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001170 set_clear_internal(so);
1171 Py_RETURN_NONE;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001172}
1173
1174PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
1175
1176static PyObject *
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001177set_union(PySetObject *so, PyObject *args)
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001178{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001179 PySetObject *result;
1180 PyObject *other;
1181 Py_ssize_t i;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001182
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001183 result = (PySetObject *)set_copy(so);
1184 if (result == NULL)
1185 return NULL;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001186
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001187 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1188 other = PyTuple_GET_ITEM(args, i);
1189 if ((PyObject *)so == other)
1190 continue;
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001191 if (set_update_internal(result, other)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001192 Py_DECREF(result);
1193 return NULL;
1194 }
1195 }
1196 return (PyObject *)result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001197}
1198
1199PyDoc_STRVAR(union_doc,
1200 "Return the union of sets as a new set.\n\
1201\n\
1202(i.e. all elements that are in either set.)");
1203
1204static PyObject *
1205set_or(PySetObject *so, PyObject *other)
1206{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001207 PySetObject *result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001208
Brian Curtindfc80e32011-08-10 20:28:54 -05001209 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1210 Py_RETURN_NOTIMPLEMENTED;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001211
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001212 result = (PySetObject *)set_copy(so);
1213 if (result == NULL)
1214 return NULL;
1215 if ((PyObject *)so == other)
1216 return (PyObject *)result;
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001217 if (set_update_internal(result, other)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001218 Py_DECREF(result);
1219 return NULL;
1220 }
1221 return (PyObject *)result;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001222}
1223
Raymond Hettingera690a992003-11-16 16:17:49 +00001224static PyObject *
1225set_ior(PySetObject *so, PyObject *other)
1226{
Brian Curtindfc80e32011-08-10 20:28:54 -05001227 if (!PyAnySet_Check(other))
1228 Py_RETURN_NOTIMPLEMENTED;
1229
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001230 if (set_update_internal(so, other))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001231 return NULL;
1232 Py_INCREF(so);
1233 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001234}
1235
1236static PyObject *
1237set_intersection(PySetObject *so, PyObject *other)
1238{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001239 PySetObject *result;
1240 PyObject *key, *it, *tmp;
Raymond Hettinger73799b12015-07-05 16:06:10 -07001241 Py_hash_t hash;
1242 int rv;
Raymond Hettingera690a992003-11-16 16:17:49 +00001243
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001244 if ((PyObject *)so == other)
1245 return set_copy(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001246
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001247 result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL);
1248 if (result == NULL)
1249 return NULL;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001250
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001251 if (PyAnySet_Check(other)) {
1252 Py_ssize_t pos = 0;
1253 setentry *entry;
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001254
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001255 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1256 tmp = (PyObject *)so;
1257 so = (PySetObject *)other;
1258 other = tmp;
1259 }
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001260
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001261 while (set_next((PySetObject *)other, &pos, &entry)) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001262 key = entry->key;
1263 hash = entry->hash;
1264 rv = set_contains_entry(so, key, hash);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001265 if (rv < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001266 Py_DECREF(result);
1267 return NULL;
1268 }
1269 if (rv) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001270 if (set_add_entry(result, key, hash)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001271 Py_DECREF(result);
1272 return NULL;
1273 }
1274 }
1275 }
1276 return (PyObject *)result;
1277 }
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001278
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001279 it = PyObject_GetIter(other);
1280 if (it == NULL) {
1281 Py_DECREF(result);
1282 return NULL;
1283 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001284
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001285 while ((key = PyIter_Next(it)) != NULL) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001286 hash = PyObject_Hash(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001287 if (hash == -1) {
1288 Py_DECREF(it);
1289 Py_DECREF(result);
1290 Py_DECREF(key);
1291 return NULL;
1292 }
Raymond Hettinger73799b12015-07-05 16:06:10 -07001293 rv = set_contains_entry(so, key, hash);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001294 if (rv < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001295 Py_DECREF(it);
1296 Py_DECREF(result);
1297 Py_DECREF(key);
1298 return NULL;
1299 }
1300 if (rv) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001301 if (set_add_entry(result, key, hash)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001302 Py_DECREF(it);
1303 Py_DECREF(result);
1304 Py_DECREF(key);
1305 return NULL;
1306 }
1307 }
1308 Py_DECREF(key);
1309 }
1310 Py_DECREF(it);
1311 if (PyErr_Occurred()) {
1312 Py_DECREF(result);
1313 return NULL;
1314 }
1315 return (PyObject *)result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001316}
1317
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001318static PyObject *
1319set_intersection_multi(PySetObject *so, PyObject *args)
1320{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001321 Py_ssize_t i;
1322 PyObject *result = (PyObject *)so;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001323
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001324 if (PyTuple_GET_SIZE(args) == 0)
1325 return set_copy(so);
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001326
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001327 Py_INCREF(so);
1328 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1329 PyObject *other = PyTuple_GET_ITEM(args, i);
1330 PyObject *newresult = set_intersection((PySetObject *)result, other);
1331 if (newresult == NULL) {
1332 Py_DECREF(result);
1333 return NULL;
1334 }
1335 Py_DECREF(result);
1336 result = newresult;
1337 }
1338 return result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001339}
1340
Raymond Hettingera690a992003-11-16 16:17:49 +00001341PyDoc_STRVAR(intersection_doc,
1342"Return the intersection of two sets as a new set.\n\
1343\n\
1344(i.e. all elements that are in both sets.)");
1345
1346static PyObject *
1347set_intersection_update(PySetObject *so, PyObject *other)
1348{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001349 PyObject *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001350
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001351 tmp = set_intersection(so, other);
1352 if (tmp == NULL)
1353 return NULL;
1354 set_swap_bodies(so, (PySetObject *)tmp);
1355 Py_DECREF(tmp);
1356 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001357}
1358
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001359static PyObject *
1360set_intersection_update_multi(PySetObject *so, PyObject *args)
1361{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001362 PyObject *tmp;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001363
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001364 tmp = set_intersection_multi(so, args);
1365 if (tmp == NULL)
1366 return NULL;
1367 set_swap_bodies(so, (PySetObject *)tmp);
1368 Py_DECREF(tmp);
1369 Py_RETURN_NONE;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001370}
1371
Raymond Hettingera690a992003-11-16 16:17:49 +00001372PyDoc_STRVAR(intersection_update_doc,
1373"Update a set with the intersection of itself and another.");
1374
1375static PyObject *
1376set_and(PySetObject *so, PyObject *other)
1377{
Brian Curtindfc80e32011-08-10 20:28:54 -05001378 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1379 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001380 return set_intersection(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001381}
1382
1383static PyObject *
1384set_iand(PySetObject *so, PyObject *other)
1385{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001386 PyObject *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001387
Brian Curtindfc80e32011-08-10 20:28:54 -05001388 if (!PyAnySet_Check(other))
1389 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001390 result = set_intersection_update(so, other);
1391 if (result == NULL)
1392 return NULL;
1393 Py_DECREF(result);
1394 Py_INCREF(so);
1395 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001396}
1397
Guido van Rossum58da9312007-11-10 23:39:45 +00001398static PyObject *
1399set_isdisjoint(PySetObject *so, PyObject *other)
1400{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001401 PyObject *key, *it, *tmp;
Raymond Hettinger73799b12015-07-05 16:06:10 -07001402 int rv;
Guido van Rossum58da9312007-11-10 23:39:45 +00001403
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001404 if ((PyObject *)so == other) {
1405 if (PySet_GET_SIZE(so) == 0)
1406 Py_RETURN_TRUE;
1407 else
1408 Py_RETURN_FALSE;
1409 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001410
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001411 if (PyAnySet_CheckExact(other)) {
1412 Py_ssize_t pos = 0;
1413 setentry *entry;
Guido van Rossum58da9312007-11-10 23:39:45 +00001414
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001415 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1416 tmp = (PyObject *)so;
1417 so = (PySetObject *)other;
1418 other = tmp;
1419 }
1420 while (set_next((PySetObject *)other, &pos, &entry)) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001421 rv = set_contains_entry(so, entry->key, entry->hash);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001422 if (rv < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001423 return NULL;
1424 if (rv)
1425 Py_RETURN_FALSE;
1426 }
1427 Py_RETURN_TRUE;
1428 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001429
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001430 it = PyObject_GetIter(other);
1431 if (it == NULL)
1432 return NULL;
Guido van Rossum58da9312007-11-10 23:39:45 +00001433
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001434 while ((key = PyIter_Next(it)) != NULL) {
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001435 Py_hash_t hash = PyObject_Hash(key);
Guido van Rossum58da9312007-11-10 23:39:45 +00001436
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001437 if (hash == -1) {
1438 Py_DECREF(key);
1439 Py_DECREF(it);
1440 return NULL;
1441 }
Raymond Hettinger73799b12015-07-05 16:06:10 -07001442 rv = set_contains_entry(so, key, hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001443 Py_DECREF(key);
Raymond Hettingerc2480dc2015-07-04 08:46:31 -07001444 if (rv < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001445 Py_DECREF(it);
1446 return NULL;
1447 }
1448 if (rv) {
1449 Py_DECREF(it);
1450 Py_RETURN_FALSE;
1451 }
1452 }
1453 Py_DECREF(it);
1454 if (PyErr_Occurred())
1455 return NULL;
1456 Py_RETURN_TRUE;
Guido van Rossum58da9312007-11-10 23:39:45 +00001457}
1458
1459PyDoc_STRVAR(isdisjoint_doc,
1460"Return True if two sets have a null intersection.");
1461
Neal Norwitz6576bd82005-11-13 18:41:28 +00001462static int
Raymond Hettingerc991db22005-08-11 07:58:45 +00001463set_difference_update_internal(PySetObject *so, PyObject *other)
1464{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001465 if ((PyObject *)so == other)
1466 return set_clear_internal(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001467
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001468 if (PyAnySet_Check(other)) {
1469 setentry *entry;
1470 Py_ssize_t pos = 0;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001471
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001472 while (set_next((PySetObject *)other, &pos, &entry))
Raymond Hettinger73799b12015-07-05 16:06:10 -07001473 if (set_discard_entry(so, entry->key, entry->hash) < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001474 return -1;
1475 } else {
1476 PyObject *key, *it;
1477 it = PyObject_GetIter(other);
1478 if (it == NULL)
1479 return -1;
1480
1481 while ((key = PyIter_Next(it)) != NULL) {
Raymond Hettingerb3223262015-07-03 23:37:16 -07001482 if (set_discard_key(so, key) < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001483 Py_DECREF(it);
1484 Py_DECREF(key);
1485 return -1;
1486 }
1487 Py_DECREF(key);
1488 }
1489 Py_DECREF(it);
1490 if (PyErr_Occurred())
1491 return -1;
1492 }
Raymond Hettingere186c762015-07-04 11:28:35 -07001493 /* If more than 1/4th are dummies, then resize them away. */
1494 if ((size_t)(so->fill - so->used) <= (size_t)so->mask / 4)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001495 return 0;
Raymond Hettinger48973002015-07-03 20:00:03 -07001496 return set_table_resize(so, so->used);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001497}
1498
Raymond Hettingera690a992003-11-16 16:17:49 +00001499static PyObject *
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001500set_difference_update(PySetObject *so, PyObject *args)
Raymond Hettingera690a992003-11-16 16:17:49 +00001501{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001502 Py_ssize_t i;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001503
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001504 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1505 PyObject *other = PyTuple_GET_ITEM(args, i);
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001506 if (set_difference_update_internal(so, other))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001507 return NULL;
1508 }
1509 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001510}
1511
1512PyDoc_STRVAR(difference_update_doc,
1513"Remove all elements of another set from this set.");
1514
1515static PyObject *
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001516set_copy_and_difference(PySetObject *so, PyObject *other)
1517{
1518 PyObject *result;
1519
1520 result = set_copy(so);
1521 if (result == NULL)
1522 return NULL;
Raymond Hettingerb3223262015-07-03 23:37:16 -07001523 if (set_difference_update_internal((PySetObject *) result, other) == 0)
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001524 return result;
1525 Py_DECREF(result);
1526 return NULL;
1527}
1528
1529static PyObject *
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001530set_difference(PySetObject *so, PyObject *other)
1531{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001532 PyObject *result;
Raymond Hettinger73799b12015-07-05 16:06:10 -07001533 PyObject *key;
1534 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001535 setentry *entry;
1536 Py_ssize_t pos = 0;
Raymond Hettinger73799b12015-07-05 16:06:10 -07001537 int rv;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001538
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001539 if (!PyAnySet_Check(other) && !PyDict_CheckExact(other)) {
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001540 return set_copy_and_difference(so, other);
1541 }
1542
1543 /* If len(so) much more than len(other), it's more efficient to simply copy
1544 * so and then iterate other looking for common elements. */
1545 if ((PySet_GET_SIZE(so) >> 2) > PyObject_Size(other)) {
1546 return set_copy_and_difference(so, other);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001547 }
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001548
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001549 result = make_new_set_basetype(Py_TYPE(so), NULL);
1550 if (result == NULL)
1551 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001552
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001553 if (PyDict_CheckExact(other)) {
1554 while (set_next(so, &pos, &entry)) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001555 key = entry->key;
1556 hash = entry->hash;
Raymond Hettinger15f08692015-07-03 17:21:17 -07001557 rv = _PyDict_Contains(other, key, hash);
Serhiy Storchakafa494fd2015-05-30 17:45:22 +03001558 if (rv < 0) {
1559 Py_DECREF(result);
1560 return NULL;
1561 }
1562 if (!rv) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001563 if (set_add_entry((PySetObject *)result, key, hash)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001564 Py_DECREF(result);
1565 return NULL;
1566 }
1567 }
1568 }
1569 return result;
1570 }
1571
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001572 /* Iterate over so, checking for common elements in other. */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001573 while (set_next(so, &pos, &entry)) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001574 key = entry->key;
1575 hash = entry->hash;
1576 rv = set_contains_entry((PySetObject *)other, key, hash);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001577 if (rv < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001578 Py_DECREF(result);
1579 return NULL;
1580 }
1581 if (!rv) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001582 if (set_add_entry((PySetObject *)result, key, hash)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001583 Py_DECREF(result);
1584 return NULL;
1585 }
1586 }
1587 }
1588 return result;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001589}
1590
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001591static PyObject *
1592set_difference_multi(PySetObject *so, PyObject *args)
1593{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001594 Py_ssize_t i;
1595 PyObject *result, *other;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001596
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001597 if (PyTuple_GET_SIZE(args) == 0)
1598 return set_copy(so);
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001599
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001600 other = PyTuple_GET_ITEM(args, 0);
1601 result = set_difference(so, other);
1602 if (result == NULL)
1603 return NULL;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001604
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001605 for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) {
1606 other = PyTuple_GET_ITEM(args, i);
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001607 if (set_difference_update_internal((PySetObject *)result, other)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001608 Py_DECREF(result);
1609 return NULL;
1610 }
1611 }
1612 return result;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001613}
1614
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001615PyDoc_STRVAR(difference_doc,
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001616"Return the difference of two or more sets as a new set.\n\
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001617\n\
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001618(i.e. all elements that are in this set but not the others.)");
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001619static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001620set_sub(PySetObject *so, PyObject *other)
1621{
Brian Curtindfc80e32011-08-10 20:28:54 -05001622 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1623 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001624 return set_difference(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001625}
1626
1627static PyObject *
1628set_isub(PySetObject *so, PyObject *other)
1629{
Brian Curtindfc80e32011-08-10 20:28:54 -05001630 if (!PyAnySet_Check(other))
1631 Py_RETURN_NOTIMPLEMENTED;
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001632 if (set_difference_update_internal(so, other))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001633 return NULL;
1634 Py_INCREF(so);
1635 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001636}
1637
1638static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001639set_symmetric_difference_update(PySetObject *so, PyObject *other)
1640{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001641 PySetObject *otherset;
1642 PyObject *key;
1643 Py_ssize_t pos = 0;
Raymond Hettinger73799b12015-07-05 16:06:10 -07001644 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001645 setentry *entry;
Raymond Hettinger73799b12015-07-05 16:06:10 -07001646 int rv;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001647
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001648 if ((PyObject *)so == other)
1649 return set_clear(so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001650
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001651 if (PyDict_CheckExact(other)) {
1652 PyObject *value;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001653 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001654 Py_INCREF(key);
Raymond Hettinger73799b12015-07-05 16:06:10 -07001655 rv = set_discard_entry(so, key, hash);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001656 if (rv < 0) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001657 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001658 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001659 }
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001660 if (rv == DISCARD_NOTFOUND) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001661 if (set_add_entry(so, key, hash)) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001662 Py_DECREF(key);
1663 return NULL;
1664 }
1665 }
Georg Brandl2d444492010-09-03 10:52:55 +00001666 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001667 }
1668 Py_RETURN_NONE;
1669 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001670
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001671 if (PyAnySet_Check(other)) {
1672 Py_INCREF(other);
1673 otherset = (PySetObject *)other;
1674 } else {
1675 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1676 if (otherset == NULL)
1677 return NULL;
1678 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001679
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001680 while (set_next(otherset, &pos, &entry)) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001681 key = entry->key;
1682 hash = entry->hash;
1683 rv = set_discard_entry(so, key, hash);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001684 if (rv < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001685 Py_DECREF(otherset);
1686 return NULL;
1687 }
1688 if (rv == DISCARD_NOTFOUND) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001689 if (set_add_entry(so, key, hash)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001690 Py_DECREF(otherset);
1691 return NULL;
1692 }
1693 }
1694 }
1695 Py_DECREF(otherset);
1696 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001697}
1698
1699PyDoc_STRVAR(symmetric_difference_update_doc,
1700"Update a set with the symmetric difference of itself and another.");
1701
1702static PyObject *
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001703set_symmetric_difference(PySetObject *so, PyObject *other)
1704{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001705 PyObject *rv;
1706 PySetObject *otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001707
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001708 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1709 if (otherset == NULL)
1710 return NULL;
1711 rv = set_symmetric_difference_update(otherset, (PyObject *)so);
1712 if (rv == NULL)
1713 return NULL;
1714 Py_DECREF(rv);
1715 return (PyObject *)otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001716}
1717
1718PyDoc_STRVAR(symmetric_difference_doc,
1719"Return the symmetric difference of two sets as a new set.\n\
1720\n\
1721(i.e. all elements that are in exactly one of the sets.)");
1722
1723static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001724set_xor(PySetObject *so, PyObject *other)
1725{
Brian Curtindfc80e32011-08-10 20:28:54 -05001726 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1727 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001728 return set_symmetric_difference(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001729}
1730
1731static PyObject *
1732set_ixor(PySetObject *so, PyObject *other)
1733{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001734 PyObject *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001735
Brian Curtindfc80e32011-08-10 20:28:54 -05001736 if (!PyAnySet_Check(other))
1737 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001738 result = set_symmetric_difference_update(so, other);
1739 if (result == NULL)
1740 return NULL;
1741 Py_DECREF(result);
1742 Py_INCREF(so);
1743 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001744}
1745
1746static PyObject *
1747set_issubset(PySetObject *so, PyObject *other)
1748{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001749 setentry *entry;
1750 Py_ssize_t pos = 0;
Raymond Hettinger73799b12015-07-05 16:06:10 -07001751 int rv;
Raymond Hettingera690a992003-11-16 16:17:49 +00001752
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001753 if (!PyAnySet_Check(other)) {
1754 PyObject *tmp, *result;
1755 tmp = make_new_set(&PySet_Type, other);
1756 if (tmp == NULL)
1757 return NULL;
1758 result = set_issubset(so, tmp);
1759 Py_DECREF(tmp);
1760 return result;
1761 }
1762 if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
1763 Py_RETURN_FALSE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001764
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001765 while (set_next(so, &pos, &entry)) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001766 rv = set_contains_entry((PySetObject *)other, entry->key, entry->hash);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001767 if (rv < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001768 return NULL;
1769 if (!rv)
1770 Py_RETURN_FALSE;
1771 }
1772 Py_RETURN_TRUE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001773}
1774
1775PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
1776
1777static PyObject *
1778set_issuperset(PySetObject *so, PyObject *other)
1779{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001780 PyObject *tmp, *result;
Raymond Hettinger3fbec702003-11-21 07:56:36 +00001781
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001782 if (!PyAnySet_Check(other)) {
1783 tmp = make_new_set(&PySet_Type, other);
1784 if (tmp == NULL)
1785 return NULL;
1786 result = set_issuperset(so, tmp);
1787 Py_DECREF(tmp);
1788 return result;
1789 }
1790 return set_issubset((PySetObject *)other, (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001791}
1792
1793PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
1794
Raymond Hettingera690a992003-11-16 16:17:49 +00001795static PyObject *
1796set_richcompare(PySetObject *v, PyObject *w, int op)
1797{
Serhiy Storchakafa494fd2015-05-30 17:45:22 +03001798 PyObject *r1;
1799 int r2;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001800
Brian Curtindfc80e32011-08-10 20:28:54 -05001801 if(!PyAnySet_Check(w))
1802 Py_RETURN_NOTIMPLEMENTED;
1803
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001804 switch (op) {
1805 case Py_EQ:
1806 if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
1807 Py_RETURN_FALSE;
1808 if (v->hash != -1 &&
1809 ((PySetObject *)w)->hash != -1 &&
1810 v->hash != ((PySetObject *)w)->hash)
1811 Py_RETURN_FALSE;
1812 return set_issubset(v, w);
1813 case Py_NE:
1814 r1 = set_richcompare(v, w, Py_EQ);
1815 if (r1 == NULL)
1816 return NULL;
Serhiy Storchakafa494fd2015-05-30 17:45:22 +03001817 r2 = PyObject_IsTrue(r1);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001818 Py_DECREF(r1);
Serhiy Storchakafa494fd2015-05-30 17:45:22 +03001819 if (r2 < 0)
1820 return NULL;
1821 return PyBool_FromLong(!r2);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001822 case Py_LE:
1823 return set_issubset(v, w);
1824 case Py_GE:
1825 return set_issuperset(v, w);
1826 case Py_LT:
1827 if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))
1828 Py_RETURN_FALSE;
1829 return set_issubset(v, w);
1830 case Py_GT:
1831 if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
1832 Py_RETURN_FALSE;
1833 return set_issuperset(v, w);
1834 }
Brian Curtindfc80e32011-08-10 20:28:54 -05001835 Py_RETURN_NOTIMPLEMENTED;
Raymond Hettingera690a992003-11-16 16:17:49 +00001836}
1837
Raymond Hettingera690a992003-11-16 16:17:49 +00001838static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001839set_add(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001840{
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001841 if (set_add_key(so, key))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001842 return NULL;
1843 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001844}
1845
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001846PyDoc_STRVAR(add_doc,
Raymond Hettingera690a992003-11-16 16:17:49 +00001847"Add an element to a set.\n\
1848\n\
1849This has no effect if the element is already present.");
1850
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001851static int
1852set_contains(PySetObject *so, PyObject *key)
1853{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001854 PyObject *tmpkey;
1855 int rv;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001856
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001857 rv = set_contains_key(so, key);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001858 if (rv < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001859 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1860 return -1;
1861 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001862 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001863 if (tmpkey == NULL)
1864 return -1;
Petri Lehtinen5acc27e2011-10-30 13:56:41 +02001865 rv = set_contains_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001866 Py_DECREF(tmpkey);
1867 }
1868 return rv;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001869}
1870
1871static PyObject *
1872set_direct_contains(PySetObject *so, PyObject *key)
1873{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001874 long result;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001875
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001876 result = set_contains(so, key);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001877 if (result < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001878 return NULL;
1879 return PyBool_FromLong(result);
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001880}
1881
1882PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
1883
Raymond Hettingera690a992003-11-16 16:17:49 +00001884static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001885set_remove(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001886{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001887 PyObject *tmpkey;
1888 int rv;
Raymond Hettingerbfd334a2003-11-22 03:55:23 +00001889
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001890 rv = set_discard_key(so, key);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001891 if (rv < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001892 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1893 return NULL;
1894 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001895 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001896 if (tmpkey == NULL)
1897 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001898 rv = set_discard_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001899 Py_DECREF(tmpkey);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001900 if (rv < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001901 return NULL;
1902 }
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00001903
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001904 if (rv == DISCARD_NOTFOUND) {
Raymond Hettinger69492da2013-09-02 15:59:26 -07001905 _PyErr_SetKeyError(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001906 return NULL;
1907 }
1908 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001909}
1910
1911PyDoc_STRVAR(remove_doc,
1912"Remove an element from a set; it must be a member.\n\
1913\n\
1914If the element is not a member, raise a KeyError.");
1915
1916static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001917set_discard(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001918{
Benjamin Peterson2b50a012011-10-30 14:24:44 -04001919 PyObject *tmpkey;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001920 int rv;
Raymond Hettinger0deab622003-12-13 18:53:18 +00001921
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001922 rv = set_discard_key(so, key);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001923 if (rv < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001924 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1925 return NULL;
1926 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001927 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001928 if (tmpkey == NULL)
1929 return NULL;
Petri Lehtinene0aa8032011-10-30 14:31:27 +02001930 rv = set_discard_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001931 Py_DECREF(tmpkey);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001932 if (rv < 0)
Petri Lehtinene0aa8032011-10-30 14:31:27 +02001933 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001934 }
1935 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001936}
1937
1938PyDoc_STRVAR(discard_doc,
1939"Remove an element from a set if it is a member.\n\
1940\n\
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001941If the element is not a member, do nothing.");
Raymond Hettingera690a992003-11-16 16:17:49 +00001942
1943static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001944set_reduce(PySetObject *so)
1945{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001946 PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;
Martin v. Löwisbd928fe2011-10-14 10:20:37 +02001947 _Py_IDENTIFIER(__dict__);
Raymond Hettingera690a992003-11-16 16:17:49 +00001948
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001949 keys = PySequence_List((PyObject *)so);
1950 if (keys == NULL)
1951 goto done;
1952 args = PyTuple_Pack(1, keys);
1953 if (args == NULL)
1954 goto done;
Martin v. Löwis1ee1b6f2011-10-10 18:11:30 +02001955 dict = _PyObject_GetAttrId((PyObject *)so, &PyId___dict__);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001956 if (dict == NULL) {
1957 PyErr_Clear();
1958 dict = Py_None;
1959 Py_INCREF(dict);
1960 }
1961 result = PyTuple_Pack(3, Py_TYPE(so), args, dict);
Raymond Hettingera690a992003-11-16 16:17:49 +00001962done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001963 Py_XDECREF(args);
1964 Py_XDECREF(keys);
1965 Py_XDECREF(dict);
1966 return result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001967}
1968
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001969static PyObject *
1970set_sizeof(PySetObject *so)
1971{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001972 Py_ssize_t res;
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001973
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001974 res = sizeof(PySetObject);
1975 if (so->table != so->smalltable)
1976 res = res + (so->mask + 1) * sizeof(setentry);
1977 return PyLong_FromSsize_t(res);
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001978}
1979
1980PyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes");
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001981static int
1982set_init(PySetObject *self, PyObject *args, PyObject *kwds)
1983{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001984 PyObject *iterable = NULL;
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001985
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001986 if (!PyAnySet_Check(self))
1987 return -1;
1988 if (PySet_Check(self) && !_PyArg_NoKeywords("set()", kwds))
1989 return -1;
1990 if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable))
1991 return -1;
1992 set_clear_internal(self);
1993 self->hash = -1;
1994 if (iterable == NULL)
1995 return 0;
1996 return set_update_internal(self, iterable);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001997}
1998
Raymond Hettingera690a992003-11-16 16:17:49 +00001999static PySequenceMethods set_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002000 set_len, /* sq_length */
2001 0, /* sq_concat */
2002 0, /* sq_repeat */
2003 0, /* sq_item */
2004 0, /* sq_slice */
2005 0, /* sq_ass_item */
2006 0, /* sq_ass_slice */
2007 (objobjproc)set_contains, /* sq_contains */
Raymond Hettingera690a992003-11-16 16:17:49 +00002008};
2009
2010/* set object ********************************************************/
2011
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002012#ifdef Py_DEBUG
2013static PyObject *test_c_api(PySetObject *so);
2014
2015PyDoc_STRVAR(test_c_api_doc, "Exercises C API. Returns True.\n\
2016All is well if assertions don't fail.");
2017#endif
2018
Raymond Hettingera690a992003-11-16 16:17:49 +00002019static PyMethodDef set_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002020 {"add", (PyCFunction)set_add, METH_O,
2021 add_doc},
2022 {"clear", (PyCFunction)set_clear, METH_NOARGS,
2023 clear_doc},
2024 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2025 contains_doc},
2026 {"copy", (PyCFunction)set_copy, METH_NOARGS,
2027 copy_doc},
2028 {"discard", (PyCFunction)set_discard, METH_O,
2029 discard_doc},
2030 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2031 difference_doc},
2032 {"difference_update", (PyCFunction)set_difference_update, METH_VARARGS,
2033 difference_update_doc},
2034 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2035 intersection_doc},
2036 {"intersection_update",(PyCFunction)set_intersection_update_multi, METH_VARARGS,
2037 intersection_update_doc},
2038 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2039 isdisjoint_doc},
2040 {"issubset", (PyCFunction)set_issubset, METH_O,
2041 issubset_doc},
2042 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2043 issuperset_doc},
2044 {"pop", (PyCFunction)set_pop, METH_NOARGS,
2045 pop_doc},
2046 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2047 reduce_doc},
2048 {"remove", (PyCFunction)set_remove, METH_O,
2049 remove_doc},
2050 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2051 sizeof_doc},
2052 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2053 symmetric_difference_doc},
2054 {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O,
2055 symmetric_difference_update_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002056#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002057 {"test_c_api", (PyCFunction)test_c_api, METH_NOARGS,
2058 test_c_api_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002059#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002060 {"union", (PyCFunction)set_union, METH_VARARGS,
2061 union_doc},
2062 {"update", (PyCFunction)set_update, METH_VARARGS,
2063 update_doc},
2064 {NULL, NULL} /* sentinel */
Raymond Hettingera690a992003-11-16 16:17:49 +00002065};
2066
2067static PyNumberMethods set_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002068 0, /*nb_add*/
2069 (binaryfunc)set_sub, /*nb_subtract*/
2070 0, /*nb_multiply*/
2071 0, /*nb_remainder*/
2072 0, /*nb_divmod*/
2073 0, /*nb_power*/
2074 0, /*nb_negative*/
2075 0, /*nb_positive*/
2076 0, /*nb_absolute*/
2077 0, /*nb_bool*/
2078 0, /*nb_invert*/
2079 0, /*nb_lshift*/
2080 0, /*nb_rshift*/
2081 (binaryfunc)set_and, /*nb_and*/
2082 (binaryfunc)set_xor, /*nb_xor*/
2083 (binaryfunc)set_or, /*nb_or*/
2084 0, /*nb_int*/
2085 0, /*nb_reserved*/
2086 0, /*nb_float*/
2087 0, /*nb_inplace_add*/
2088 (binaryfunc)set_isub, /*nb_inplace_subtract*/
2089 0, /*nb_inplace_multiply*/
2090 0, /*nb_inplace_remainder*/
2091 0, /*nb_inplace_power*/
2092 0, /*nb_inplace_lshift*/
2093 0, /*nb_inplace_rshift*/
2094 (binaryfunc)set_iand, /*nb_inplace_and*/
2095 (binaryfunc)set_ixor, /*nb_inplace_xor*/
2096 (binaryfunc)set_ior, /*nb_inplace_or*/
Raymond Hettingera690a992003-11-16 16:17:49 +00002097};
2098
2099PyDoc_STRVAR(set_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002100"set() -> new empty set object\n\
2101set(iterable) -> new set object\n\
Raymond Hettingera690a992003-11-16 16:17:49 +00002102\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002103Build an unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00002104
2105PyTypeObject PySet_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002106 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2107 "set", /* tp_name */
2108 sizeof(PySetObject), /* tp_basicsize */
2109 0, /* tp_itemsize */
2110 /* methods */
2111 (destructor)set_dealloc, /* tp_dealloc */
2112 0, /* tp_print */
2113 0, /* tp_getattr */
2114 0, /* tp_setattr */
2115 0, /* tp_reserved */
2116 (reprfunc)set_repr, /* tp_repr */
2117 &set_as_number, /* tp_as_number */
2118 &set_as_sequence, /* tp_as_sequence */
2119 0, /* tp_as_mapping */
Georg Brandl00da4e02010-10-18 07:32:48 +00002120 PyObject_HashNotImplemented, /* tp_hash */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002121 0, /* tp_call */
2122 0, /* tp_str */
2123 PyObject_GenericGetAttr, /* tp_getattro */
2124 0, /* tp_setattro */
2125 0, /* tp_as_buffer */
2126 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2127 Py_TPFLAGS_BASETYPE, /* tp_flags */
2128 set_doc, /* tp_doc */
2129 (traverseproc)set_traverse, /* tp_traverse */
2130 (inquiry)set_clear_internal, /* tp_clear */
2131 (richcmpfunc)set_richcompare, /* tp_richcompare */
Georg Brandl00da4e02010-10-18 07:32:48 +00002132 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2133 (getiterfunc)set_iter, /* tp_iter */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002134 0, /* tp_iternext */
2135 set_methods, /* tp_methods */
2136 0, /* tp_members */
2137 0, /* tp_getset */
2138 0, /* tp_base */
2139 0, /* tp_dict */
2140 0, /* tp_descr_get */
2141 0, /* tp_descr_set */
2142 0, /* tp_dictoffset */
2143 (initproc)set_init, /* tp_init */
2144 PyType_GenericAlloc, /* tp_alloc */
2145 set_new, /* tp_new */
2146 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002147};
2148
2149/* frozenset object ********************************************************/
2150
2151
2152static PyMethodDef frozenset_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002153 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2154 contains_doc},
2155 {"copy", (PyCFunction)frozenset_copy, METH_NOARGS,
2156 copy_doc},
2157 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2158 difference_doc},
2159 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2160 intersection_doc},
2161 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2162 isdisjoint_doc},
2163 {"issubset", (PyCFunction)set_issubset, METH_O,
2164 issubset_doc},
2165 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2166 issuperset_doc},
2167 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2168 reduce_doc},
2169 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2170 sizeof_doc},
2171 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2172 symmetric_difference_doc},
2173 {"union", (PyCFunction)set_union, METH_VARARGS,
2174 union_doc},
2175 {NULL, NULL} /* sentinel */
Raymond Hettingera690a992003-11-16 16:17:49 +00002176};
2177
2178static PyNumberMethods frozenset_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002179 0, /*nb_add*/
2180 (binaryfunc)set_sub, /*nb_subtract*/
2181 0, /*nb_multiply*/
2182 0, /*nb_remainder*/
2183 0, /*nb_divmod*/
2184 0, /*nb_power*/
2185 0, /*nb_negative*/
2186 0, /*nb_positive*/
2187 0, /*nb_absolute*/
2188 0, /*nb_bool*/
2189 0, /*nb_invert*/
2190 0, /*nb_lshift*/
2191 0, /*nb_rshift*/
2192 (binaryfunc)set_and, /*nb_and*/
2193 (binaryfunc)set_xor, /*nb_xor*/
2194 (binaryfunc)set_or, /*nb_or*/
Raymond Hettingera690a992003-11-16 16:17:49 +00002195};
2196
2197PyDoc_STRVAR(frozenset_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002198"frozenset() -> empty frozenset object\n\
2199frozenset(iterable) -> frozenset object\n\
Raymond Hettingera690a992003-11-16 16:17:49 +00002200\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002201Build an immutable unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00002202
2203PyTypeObject PyFrozenSet_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002204 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2205 "frozenset", /* tp_name */
2206 sizeof(PySetObject), /* tp_basicsize */
2207 0, /* tp_itemsize */
2208 /* methods */
2209 (destructor)set_dealloc, /* tp_dealloc */
2210 0, /* tp_print */
2211 0, /* tp_getattr */
2212 0, /* tp_setattr */
2213 0, /* tp_reserved */
2214 (reprfunc)set_repr, /* tp_repr */
2215 &frozenset_as_number, /* tp_as_number */
2216 &set_as_sequence, /* tp_as_sequence */
2217 0, /* tp_as_mapping */
2218 frozenset_hash, /* tp_hash */
2219 0, /* tp_call */
2220 0, /* tp_str */
2221 PyObject_GenericGetAttr, /* tp_getattro */
2222 0, /* tp_setattro */
2223 0, /* tp_as_buffer */
2224 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2225 Py_TPFLAGS_BASETYPE, /* tp_flags */
2226 frozenset_doc, /* tp_doc */
2227 (traverseproc)set_traverse, /* tp_traverse */
2228 (inquiry)set_clear_internal, /* tp_clear */
2229 (richcmpfunc)set_richcompare, /* tp_richcompare */
2230 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2231 (getiterfunc)set_iter, /* tp_iter */
2232 0, /* tp_iternext */
2233 frozenset_methods, /* tp_methods */
2234 0, /* tp_members */
2235 0, /* tp_getset */
2236 0, /* tp_base */
2237 0, /* tp_dict */
2238 0, /* tp_descr_get */
2239 0, /* tp_descr_set */
2240 0, /* tp_dictoffset */
2241 0, /* tp_init */
2242 PyType_GenericAlloc, /* tp_alloc */
2243 frozenset_new, /* tp_new */
2244 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002245};
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002246
2247
2248/***** C API functions *************************************************/
2249
2250PyObject *
2251PySet_New(PyObject *iterable)
2252{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002253 return make_new_set(&PySet_Type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002254}
2255
2256PyObject *
2257PyFrozenSet_New(PyObject *iterable)
2258{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002259 return make_new_set(&PyFrozenSet_Type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002260}
2261
Neal Norwitz8c49c822006-03-04 18:41:19 +00002262Py_ssize_t
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002263PySet_Size(PyObject *anyset)
2264{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002265 if (!PyAnySet_Check(anyset)) {
2266 PyErr_BadInternalCall();
2267 return -1;
2268 }
2269 return PySet_GET_SIZE(anyset);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002270}
2271
2272int
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002273PySet_Clear(PyObject *set)
2274{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002275 if (!PySet_Check(set)) {
2276 PyErr_BadInternalCall();
2277 return -1;
2278 }
2279 return set_clear_internal((PySetObject *)set);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002280}
2281
2282int
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002283PySet_Contains(PyObject *anyset, PyObject *key)
2284{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002285 if (!PyAnySet_Check(anyset)) {
2286 PyErr_BadInternalCall();
2287 return -1;
2288 }
2289 return set_contains_key((PySetObject *)anyset, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002290}
2291
2292int
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002293PySet_Discard(PyObject *set, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002294{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002295 if (!PySet_Check(set)) {
2296 PyErr_BadInternalCall();
2297 return -1;
2298 }
2299 return set_discard_key((PySetObject *)set, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002300}
2301
2302int
Christian Heimesfd66e512008-01-29 12:18:50 +00002303PySet_Add(PyObject *anyset, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002304{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002305 if (!PySet_Check(anyset) &&
2306 (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
2307 PyErr_BadInternalCall();
2308 return -1;
2309 }
2310 return set_add_key((PySetObject *)anyset, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002311}
2312
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002313int
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002314_PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash)
Guido van Rossumd8faa362007-04-27 19:54:29 +00002315{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002316 setentry *entry;
Guido van Rossumd8faa362007-04-27 19:54:29 +00002317
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002318 if (!PyAnySet_Check(set)) {
2319 PyErr_BadInternalCall();
2320 return -1;
2321 }
2322 if (set_next((PySetObject *)set, pos, &entry) == 0)
2323 return 0;
2324 *key = entry->key;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002325 *hash = entry->hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002326 return 1;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002327}
2328
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002329PyObject *
2330PySet_Pop(PyObject *set)
2331{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002332 if (!PySet_Check(set)) {
2333 PyErr_BadInternalCall();
2334 return NULL;
2335 }
2336 return set_pop((PySetObject *)set);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002337}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002338
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002339int
2340_PySet_Update(PyObject *set, PyObject *iterable)
2341{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002342 if (!PySet_Check(set)) {
2343 PyErr_BadInternalCall();
2344 return -1;
2345 }
2346 return set_update_internal((PySetObject *)set, iterable);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002347}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002348
Raymond Hettingere259f132013-12-15 11:56:14 -08002349/* Exported for the gdb plugin's benefit. */
2350PyObject *_PySet_Dummy = dummy;
2351
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002352#ifdef Py_DEBUG
2353
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002354/* Test code to be called with any three element set.
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002355 Returns True and original set is restored. */
2356
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002357#define assertRaises(call_return_value, exception) \
2358 do { \
2359 assert(call_return_value); \
2360 assert(PyErr_ExceptionMatches(exception)); \
2361 PyErr_Clear(); \
2362 } while(0)
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002363
2364static PyObject *
2365test_c_api(PySetObject *so)
2366{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002367 Py_ssize_t count;
2368 char *s;
2369 Py_ssize_t i;
Raymond Hettinger583cd032013-09-07 22:06:35 -07002370 PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x=NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002371 PyObject *ob = (PyObject *)so;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002372 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002373 PyObject *str;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002374
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002375 /* Verify preconditions */
2376 assert(PyAnySet_Check(ob));
2377 assert(PyAnySet_CheckExact(ob));
2378 assert(!PyFrozenSet_CheckExact(ob));
Victor Stinner08b36bd2010-03-13 00:19:17 +00002379
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002380 /* so.clear(); so |= set("abc"); */
2381 str = PyUnicode_FromString("abc");
2382 if (str == NULL)
2383 return NULL;
2384 set_clear_internal(so);
Raymond Hettinger5af9e132015-05-13 01:44:36 -07002385 if (set_update_internal(so, str)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002386 Py_DECREF(str);
2387 return NULL;
2388 }
2389 Py_DECREF(str);
Victor Stinner08b36bd2010-03-13 00:19:17 +00002390
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002391 /* Exercise type/size checks */
2392 assert(PySet_Size(ob) == 3);
2393 assert(PySet_GET_SIZE(ob) == 3);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002394
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002395 /* Raise TypeError for non-iterable constructor arguments */
2396 assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
2397 assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002398
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002399 /* Raise TypeError for unhashable key */
2400 dup = PySet_New(ob);
2401 assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
2402 assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
2403 assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002404
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002405 /* Exercise successful pop, contains, add, and discard */
2406 elem = PySet_Pop(ob);
2407 assert(PySet_Contains(ob, elem) == 0);
2408 assert(PySet_GET_SIZE(ob) == 2);
2409 assert(PySet_Add(ob, elem) == 0);
2410 assert(PySet_Contains(ob, elem) == 1);
2411 assert(PySet_GET_SIZE(ob) == 3);
2412 assert(PySet_Discard(ob, elem) == 1);
2413 assert(PySet_GET_SIZE(ob) == 2);
2414 assert(PySet_Discard(ob, elem) == 0);
2415 assert(PySet_GET_SIZE(ob) == 2);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002416
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002417 /* Exercise clear */
2418 dup2 = PySet_New(dup);
2419 assert(PySet_Clear(dup2) == 0);
2420 assert(PySet_Size(dup2) == 0);
2421 Py_DECREF(dup2);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002422
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002423 /* Raise SystemError on clear or update of frozen set */
2424 f = PyFrozenSet_New(dup);
2425 assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
2426 assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
2427 assert(PySet_Add(f, elem) == 0);
2428 Py_INCREF(f);
2429 assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
2430 Py_DECREF(f);
2431 Py_DECREF(f);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002432
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002433 /* Exercise direct iteration */
2434 i = 0, count = 0;
2435 while (_PySet_NextEntry((PyObject *)dup, &i, &x, &hash)) {
2436 s = _PyUnicode_AsString(x);
2437 assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
2438 count++;
2439 }
2440 assert(count == 3);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002441
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002442 /* Exercise updates */
2443 dup2 = PySet_New(NULL);
2444 assert(_PySet_Update(dup2, dup) == 0);
2445 assert(PySet_Size(dup2) == 3);
2446 assert(_PySet_Update(dup2, dup) == 0);
2447 assert(PySet_Size(dup2) == 3);
2448 Py_DECREF(dup2);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002449
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002450 /* Raise SystemError when self argument is not a set or frozenset. */
2451 t = PyTuple_New(0);
2452 assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
2453 assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
2454 Py_DECREF(t);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002455
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002456 /* Raise SystemError when self argument is not a set. */
2457 f = PyFrozenSet_New(dup);
2458 assert(PySet_Size(f) == 3);
2459 assert(PyFrozenSet_CheckExact(f));
2460 assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
2461 assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
2462 Py_DECREF(f);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002463
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002464 /* Raise KeyError when popping from an empty set */
2465 assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
2466 Py_DECREF(ob);
2467 assert(PySet_GET_SIZE(ob) == 0);
2468 assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002469
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002470 /* Restore the set from the copy using the PyNumber API */
2471 assert(PyNumber_InPlaceOr(ob, dup) == ob);
2472 Py_DECREF(ob);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002473
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002474 /* Verify constructors accept NULL arguments */
2475 f = PySet_New(NULL);
2476 assert(f != NULL);
2477 assert(PySet_GET_SIZE(f) == 0);
2478 Py_DECREF(f);
2479 f = PyFrozenSet_New(NULL);
2480 assert(f != NULL);
2481 assert(PyFrozenSet_CheckExact(f));
2482 assert(PySet_GET_SIZE(f) == 0);
2483 Py_DECREF(f);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002484
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002485 Py_DECREF(elem);
2486 Py_DECREF(dup);
2487 Py_RETURN_TRUE;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002488}
2489
Raymond Hettinger9bda1d62005-09-16 07:14:21 +00002490#undef assertRaises
2491
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002492#endif
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -05002493
2494/***** Dummy Struct *************************************************/
2495
2496static PyObject *
2497dummy_repr(PyObject *op)
2498{
2499 return PyUnicode_FromString("<dummy key>");
2500}
2501
2502static void
2503dummy_dealloc(PyObject* ignore)
2504{
2505 Py_FatalError("deallocating <dummy key>");
2506}
2507
2508static PyTypeObject _PySetDummy_Type = {
2509 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2510 "<dummy key> type",
2511 0,
2512 0,
2513 dummy_dealloc, /*tp_dealloc*/ /*never called*/
2514 0, /*tp_print*/
2515 0, /*tp_getattr*/
2516 0, /*tp_setattr*/
2517 0, /*tp_reserved*/
2518 dummy_repr, /*tp_repr*/
2519 0, /*tp_as_number*/
2520 0, /*tp_as_sequence*/
2521 0, /*tp_as_mapping*/
2522 0, /*tp_hash */
2523 0, /*tp_call */
2524 0, /*tp_str */
2525 0, /*tp_getattro */
2526 0, /*tp_setattro */
2527 0, /*tp_as_buffer */
2528 Py_TPFLAGS_DEFAULT, /*tp_flags */
2529};
2530
2531static PyObject _dummy_struct = {
2532 _PyObject_EXTRA_INIT
2533 2, &_PySetDummy_Type
2534};
2535