blob: 23d624f9158e70525bc7b2d30da6f14052b2d958 [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 Hettinger6c3c1cc2013-08-31 21:34:24 -07007 Copyright (c) 2003-2013 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
26 Unlike the dictionary implementation, the lookkey functions can return
27 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"
Christian Heimes0ded5b52007-12-10 15:50:56 +000032#include "stringlib/eq.h"
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000033
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000034/* Object used as dummy key to fill deleted entries */
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -050035static PyObject _dummy_struct;
36
37#define dummy (&_dummy_struct)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000038
Antoine Pitrou9d952542013-08-24 21:07:07 +020039/* Exported for the gdb plugin's benefit. */
40PyObject *_PySet_Dummy = dummy;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000041
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000042
Raymond Hettinger04fd9dd2013-09-07 17:41:01 -070043/* ======================================================================== */
44/* ======= Begin logic for probing the hash table ========================= */
45
Raymond Hettinger742d8712013-09-08 00:25:57 -070046/* This should be >= PySet_MINSIZE - 1 */
47#define LINEAR_PROBES 9
48
49/* This must be >= 1 */
50#define PERTURB_SHIFT 5
51
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000052static setentry *
Antoine Pitrou9ed5f272013-08-13 20:18:52 +020053set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000054{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000055 setentry *table = so->table;
Raymond Hettingerafe89092013-08-28 20:59:31 -070056 setentry *freeslot = NULL;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +020057 setentry *entry;
Raymond Hettingera35adf52013-09-02 03:23:21 -070058 setentry *limit;
Raymond Hettingerafe89092013-08-28 20:59:31 -070059 size_t perturb = hash;
60 size_t mask = so->mask;
Raymond Hettingera35adf52013-09-02 03:23:21 -070061 size_t i = (size_t)hash; /* Unsigned for defined overflow behavior. */
62 size_t j;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +020063 int cmp;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000064
Raymond Hettingera35adf52013-09-02 03:23:21 -070065 entry = &table[i & mask];
Raymond Hettingerafe89092013-08-28 20:59:31 -070066 if (entry->key == NULL)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000067 return entry;
Raymond Hettinger237b34b2013-08-17 02:31:53 -070068
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -070069 while (1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000070 if (entry->key == key)
Raymond Hettingerafe89092013-08-28 20:59:31 -070071 return entry;
Raymond Hettingerae9e6162013-08-20 22:28:24 -070072 if (entry->hash == hash && entry->key != dummy) {
Raymond Hettingerafe89092013-08-28 20:59:31 -070073 PyObject *startkey = entry->key;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000074 Py_INCREF(startkey);
75 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
76 Py_DECREF(startkey);
77 if (cmp < 0)
78 return NULL;
Raymond Hettingerafe89092013-08-28 20:59:31 -070079 if (table != so->table || entry->key != startkey)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000080 return set_lookkey(so, key, hash);
Raymond Hettingerafe89092013-08-28 20:59:31 -070081 if (cmp > 0)
82 return entry;
83 }
84 if (entry->key == dummy && freeslot == NULL)
85 freeslot = entry;
86
Raymond Hettingera35adf52013-09-02 03:23:21 -070087 limit = &table[mask];
88 for (j = 0 ; j < LINEAR_PROBES ; j++) {
89 entry = (entry == limit) ? &table[0] : entry + 1;
90 if (entry->key == NULL)
91 goto found_null;
92 if (entry->key == key)
Raymond Hettingerafe89092013-08-28 20:59:31 -070093 return entry;
Raymond Hettingera35adf52013-09-02 03:23:21 -070094 if (entry->hash == hash && entry->key != dummy) {
95 PyObject *startkey = entry->key;
96 Py_INCREF(startkey);
97 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
98 Py_DECREF(startkey);
99 if (cmp < 0)
100 return NULL;
101 if (table != so->table || entry->key != startkey)
102 return set_lookkey(so, key, hash);
103 if (cmp > 0)
104 return entry;
105 }
106 if (entry->key == dummy && freeslot == NULL)
107 freeslot = entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000108 }
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700109
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700110 perturb >>= PERTURB_SHIFT;
Raymond Hettingerc56e0e32013-09-02 16:32:27 -0700111 i = i * 5 + 1 + perturb;
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700112
Raymond Hettingera35adf52013-09-02 03:23:21 -0700113 entry = &table[i & mask];
Raymond Hettingerafe89092013-08-28 20:59:31 -0700114 if (entry->key == NULL)
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700115 break;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000116 }
Raymond Hettingera35adf52013-09-02 03:23:21 -0700117 found_null:
Raymond Hettingerafe89092013-08-28 20:59:31 -0700118 return freeslot == NULL ? entry : freeslot;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000119}
120
121/*
Christian Heimes0ded5b52007-12-10 15:50:56 +0000122 * Hacked up version of set_lookkey which can assume keys are always unicode;
123 * This means we can always use unicode_eq directly and not have to check to
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000124 * see if the comparison altered the table.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000125 */
126static setentry *
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200127set_lookkey_unicode(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000128{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000129 setentry *table = so->table;
Raymond Hettingerafe89092013-08-28 20:59:31 -0700130 setentry *freeslot = NULL;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200131 setentry *entry;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700132 setentry *limit;
Raymond Hettingerafe89092013-08-28 20:59:31 -0700133 size_t perturb = hash;
134 size_t mask = so->mask;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700135 size_t i = (size_t)hash;
136 size_t j;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000137
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000138 /* Make sure this function doesn't have to handle non-unicode keys,
139 including subclasses of str; e.g., one reason to subclass
140 strings is to override __eq__, and for speed we don't cater to
141 that here. */
142 if (!PyUnicode_CheckExact(key)) {
143 so->lookup = set_lookkey;
144 return set_lookkey(so, key, hash);
145 }
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700146
Raymond Hettingera35adf52013-09-02 03:23:21 -0700147 entry = &table[i & mask];
Raymond Hettingerafe89092013-08-28 20:59:31 -0700148 if (entry->key == NULL)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000149 return entry;
Raymond Hettingered6c1ef2005-08-13 08:28:03 +0000150
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700151 while (1) {
Raymond Hettingerafe89092013-08-28 20:59:31 -0700152 if (entry->key == key
153 || (entry->hash == hash
Raymond Hettinger742d8712013-09-08 00:25:57 -0700154 && entry->key != dummy
155 && unicode_eq(entry->key, key)))
Raymond Hettingerafe89092013-08-28 20:59:31 -0700156 return entry;
157 if (entry->key == dummy && freeslot == NULL)
158 freeslot = entry;
159
Raymond Hettingera35adf52013-09-02 03:23:21 -0700160 limit = &table[mask];
161 for (j = 0 ; j < LINEAR_PROBES ; j++) {
162 entry = (entry == limit) ? &table[0] : entry + 1;
163 if (entry->key == NULL)
164 goto found_null;
165 if (entry->key == key
166 || (entry->hash == hash
167 && entry->key != dummy
168 && unicode_eq(entry->key, key)))
169 return entry;
170 if (entry->key == dummy && freeslot == NULL)
171 freeslot = entry;
172 }
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700173
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700174 perturb >>= PERTURB_SHIFT;
Raymond Hettingerc56e0e32013-09-02 16:32:27 -0700175 i = i * 5 + 1 + perturb;
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700176
Raymond Hettingera35adf52013-09-02 03:23:21 -0700177 entry = &table[i & mask];
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000178 if (entry->key == NULL)
Raymond Hettingerafe89092013-08-28 20:59:31 -0700179 break;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000180 }
Raymond Hettingera35adf52013-09-02 03:23:21 -0700181 found_null:
Raymond Hettingerafe89092013-08-28 20:59:31 -0700182 return freeslot == NULL ? entry : freeslot;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000183}
184
185/*
Thomas Wouters89f507f2006-12-13 04:49:30 +0000186Internal routine used by set_table_resize() to insert an item which is
187known to be absent from the set. This routine also assumes that
188the set contains no deleted entries. Besides the performance benefit,
189using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
190Note that no refcounts are changed by this routine; if needed, the caller
191is responsible for incref'ing `key`.
192*/
193static void
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200194set_insert_clean(PySetObject *so, PyObject *key, Py_hash_t hash)
Thomas Wouters89f507f2006-12-13 04:49:30 +0000195{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000196 setentry *table = so->table;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200197 setentry *entry;
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700198 size_t perturb = hash;
199 size_t mask = (size_t)so->mask;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700200 size_t i = (size_t)hash;
201 size_t j;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000202
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700203 while (1) {
Raymond Hettingera35adf52013-09-02 03:23:21 -0700204 entry = &table[i & mask];
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700205 if (entry->key == NULL)
Raymond Hettingera35adf52013-09-02 03:23:21 -0700206 goto found_null;
207 for (j = 1 ; j <= LINEAR_PROBES ; j++) {
208 entry = &table[(i + j) & mask];
209 if (entry->key == NULL)
210 goto found_null;
211 }
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700212 perturb >>= PERTURB_SHIFT;
Raymond Hettingerc56e0e32013-09-02 16:32:27 -0700213 i = i * 5 + 1 + perturb;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000214 }
Raymond Hettingera35adf52013-09-02 03:23:21 -0700215 found_null:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000216 so->fill++;
217 entry->key = key;
218 entry->hash = hash;
219 so->used++;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000220}
221
Raymond Hettinger04fd9dd2013-09-07 17:41:01 -0700222/* ======== End logic for probing the hash table ========================== */
223/* ======================================================================== */
224
225
226/*
227Internal routine to insert a new key into the table.
228Used by the public insert routine.
229Eats a reference to key.
230*/
231static int
232set_insert_key(PySetObject *so, PyObject *key, Py_hash_t hash)
233{
234 setentry *entry;
235
236 assert(so->lookup != NULL);
237 entry = so->lookup(so, key, hash);
238 if (entry == NULL)
239 return -1;
240 if (entry->key == NULL) {
241 /* UNUSED */
242 so->fill++;
243 entry->key = key;
244 entry->hash = hash;
245 so->used++;
246 } else if (entry->key == dummy) {
247 /* DUMMY */
248 entry->key = key;
249 entry->hash = hash;
250 so->used++;
251 } else {
252 /* ACTIVE */
253 Py_DECREF(key);
254 }
255 return 0;
256}
257
Thomas Wouters89f507f2006-12-13 04:49:30 +0000258/*
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000259Restructure the table by allocating a new table and reinserting all
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000260keys again. When entries have been deleted, the new table may
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000261actually be smaller than the old one.
262*/
263static int
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000264set_table_resize(PySetObject *so, Py_ssize_t minused)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000265{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000266 Py_ssize_t newsize;
267 setentry *oldtable, *newtable, *entry;
268 Py_ssize_t i;
269 int is_oldtable_malloced;
270 setentry small_copy[PySet_MINSIZE];
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000271
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000272 assert(minused >= 0);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000273
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000274 /* Find the smallest table size > minused. */
275 for (newsize = PySet_MINSIZE;
276 newsize <= minused && newsize > 0;
277 newsize <<= 1)
278 ;
279 if (newsize <= 0) {
280 PyErr_NoMemory();
281 return -1;
282 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000283
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000284 /* Get space for a new table. */
285 oldtable = so->table;
286 assert(oldtable != NULL);
287 is_oldtable_malloced = oldtable != so->smalltable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000288
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000289 if (newsize == PySet_MINSIZE) {
290 /* A large table is shrinking, or we can't get any smaller. */
291 newtable = so->smalltable;
292 if (newtable == oldtable) {
293 if (so->fill == so->used) {
294 /* No dummies, so no point doing anything. */
295 return 0;
296 }
297 /* We're not going to resize it, but rebuild the
298 table anyway to purge old dummy entries.
299 Subtle: This is *necessary* if fill==size,
300 as set_lookkey needs at least one virgin slot to
301 terminate failing searches. If fill < size, it's
302 merely desirable, as dummies slow searches. */
303 assert(so->fill > so->used);
304 memcpy(small_copy, oldtable, sizeof(small_copy));
305 oldtable = small_copy;
306 }
307 }
308 else {
309 newtable = PyMem_NEW(setentry, newsize);
310 if (newtable == NULL) {
311 PyErr_NoMemory();
312 return -1;
313 }
314 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000315
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000316 /* Make the set empty, using the new table. */
317 assert(newtable != oldtable);
318 so->table = newtable;
319 so->mask = newsize - 1;
320 memset(newtable, 0, sizeof(setentry) * newsize);
Raymond Hettingerfcf3b502013-08-22 08:20:31 -0700321 i = so->used;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000322 so->used = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000323 so->fill = 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000324
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000325 /* Copy the data over; this is refcount-neutral for active entries;
326 dummy entries aren't copied over, of course */
327 for (entry = oldtable; i > 0; entry++) {
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -0500328 if (entry->key != NULL && entry->key != dummy) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000329 --i;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000330 set_insert_clean(so, entry->key, entry->hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000331 }
332 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000333
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000334 if (is_oldtable_malloced)
335 PyMem_DEL(oldtable);
336 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000337}
338
Raymond Hettingerc991db22005-08-11 07:58:45 +0000339/* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
340
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000341static int
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200342set_add_entry(PySetObject *so, setentry *entry)
Raymond Hettingerc991db22005-08-11 07:58:45 +0000343{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200344 Py_ssize_t n_used;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000345 PyObject *key = entry->key;
Éric Araujobbcfc1f2011-03-23 03:43:22 +0100346 Py_hash_t hash = entry->hash;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000347
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000348 assert(so->fill <= so->mask); /* at least one empty slot */
349 n_used = so->used;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000350 Py_INCREF(key);
Éric Araujo48049912011-03-23 02:08:07 +0100351 if (set_insert_key(so, key, hash) == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000352 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000353 return -1;
354 }
355 if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
356 return 0;
357 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettingerc991db22005-08-11 07:58:45 +0000358}
359
360static int
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200361set_add_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000362{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200363 Py_hash_t hash;
364 Py_ssize_t n_used;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000365
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000366 if (!PyUnicode_CheckExact(key) ||
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200367 (hash = ((PyASCIIObject *) key)->hash) == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000368 hash = PyObject_Hash(key);
369 if (hash == -1)
370 return -1;
371 }
372 assert(so->fill <= so->mask); /* at least one empty slot */
373 n_used = so->used;
374 Py_INCREF(key);
375 if (set_insert_key(so, key, hash) == -1) {
376 Py_DECREF(key);
377 return -1;
378 }
379 if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
380 return 0;
381 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000382}
383
384#define DISCARD_NOTFOUND 0
385#define DISCARD_FOUND 1
386
387static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000388set_discard_entry(PySetObject *so, setentry *oldentry)
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200389{ setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000390 PyObject *old_key;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000391
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000392 entry = (so->lookup)(so, oldentry->key, oldentry->hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000393 if (entry == NULL)
394 return -1;
395 if (entry->key == NULL || entry->key == dummy)
396 return DISCARD_NOTFOUND;
397 old_key = entry->key;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000398 entry->key = dummy;
399 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;
408 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000409 PyObject *old_key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000410
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000411 assert (PyAnySet_Check(so));
Christian Heimes0ded5b52007-12-10 15:50:56 +0000412
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000413 if (!PyUnicode_CheckExact(key) ||
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200414 (hash = ((PyASCIIObject *) key)->hash) == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000415 hash = PyObject_Hash(key);
416 if (hash == -1)
417 return -1;
418 }
419 entry = (so->lookup)(so, key, hash);
420 if (entry == NULL)
421 return -1;
422 if (entry->key == NULL || entry->key == dummy)
423 return DISCARD_NOTFOUND;
424 old_key = entry->key;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000425 entry->key = dummy;
426 so->used--;
427 Py_DECREF(old_key);
428 return DISCARD_FOUND;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000429}
430
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700431static void
432set_empty_to_minsize(PySetObject *so)
433{
434 memset(so->smalltable, 0, sizeof(so->smalltable));
435 so->fill = 0;
436 so->used = 0;
437 so->mask = PySet_MINSIZE - 1;
438 so->table = so->smalltable;
439 so->hash = -1;
440}
441
Raymond Hettingerfe889f32005-08-06 05:43:39 +0000442static int
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000443set_clear_internal(PySetObject *so)
444{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000445 setentry *entry, *table;
446 int table_is_malloced;
447 Py_ssize_t fill;
448 setentry small_copy[PySet_MINSIZE];
Raymond Hettingera580c472005-08-05 17:19:54 +0000449
Raymond Hettinger583cd032013-09-07 22:06:35 -0700450#ifdef Py_DEBUG
451 Py_ssize_t i = 0;
452 Py_ssize_t n = so->mask + 1;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000453#endif
454
Raymond Hettinger583cd032013-09-07 22:06:35 -0700455 assert (PyAnySet_Check(so));
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000456 table = so->table;
457 assert(table != NULL);
458 table_is_malloced = table != so->smalltable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000459
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000460 /* This is delicate. During the process of clearing the set,
461 * decrefs can cause the set to mutate. To avoid fatal confusion
462 * (voice of experience), we have to make the set empty before
463 * clearing the slots, and never refer to anything via so->ref while
464 * clearing.
465 */
466 fill = so->fill;
467 if (table_is_malloced)
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700468 set_empty_to_minsize(so);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000469
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000470 else if (fill > 0) {
471 /* It's a small table with something that needs to be cleared.
472 * Afraid the only safe way is to copy the set entries into
473 * another small table first.
474 */
475 memcpy(small_copy, table, sizeof(small_copy));
476 table = small_copy;
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700477 set_empty_to_minsize(so);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000478 }
479 /* else it's a small table that's already empty */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000480
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000481 /* Now we can finally clear things. If C had refcounts, we could
482 * assert that the refcount on table is 1 now, i.e. that this function
483 * has unique access to it, so decref side-effects can't alter it.
484 */
485 for (entry = table; fill > 0; ++entry) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000486#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000487 assert(i < n);
488 ++i;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000489#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000490 if (entry->key) {
491 --fill;
Raymond Hettingerfcf3b502013-08-22 08:20:31 -0700492 if (entry->key != dummy)
493 Py_DECREF(entry->key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000494 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000495#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000496 else
497 assert(entry->key == NULL);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000498#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000499 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000500
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000501 if (table_is_malloced)
502 PyMem_DEL(table);
503 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000504}
505
506/*
507 * Iterate over a set table. Use like so:
508 *
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000509 * Py_ssize_t pos;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000510 * setentry *entry;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000511 * pos = 0; # important! pos should not otherwise be changed by you
Raymond Hettingerc991db22005-08-11 07:58:45 +0000512 * while (set_next(yourset, &pos, &entry)) {
513 * Refer to borrowed reference in entry->key.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000514 * }
515 *
Raymond Hettingerc991db22005-08-11 07:58:45 +0000516 * CAUTION: In general, it isn't safe to use set_next in a loop that
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000517 * mutates the table.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000518 */
519static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000520set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000521{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000522 Py_ssize_t i;
523 Py_ssize_t mask;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200524 setentry *table;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000525
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000526 assert (PyAnySet_Check(so));
527 i = *pos_ptr;
528 assert(i >= 0);
529 table = so->table;
530 mask = so->mask;
531 while (i <= mask && (table[i].key == NULL || table[i].key == dummy))
532 i++;
533 *pos_ptr = i+1;
534 if (i > mask)
535 return 0;
536 assert(table[i].key != NULL);
537 *entry_ptr = &table[i];
538 return 1;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000539}
540
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000541static void
542set_dealloc(PySetObject *so)
543{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200544 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000545 Py_ssize_t fill = so->fill;
546 PyObject_GC_UnTrack(so);
547 Py_TRASHCAN_SAFE_BEGIN(so)
548 if (so->weakreflist != NULL)
549 PyObject_ClearWeakRefs((PyObject *) so);
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000550
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000551 for (entry = so->table; fill > 0; entry++) {
552 if (entry->key) {
553 --fill;
Raymond Hettingerfcf3b502013-08-22 08:20:31 -0700554 if (entry->key != dummy)
555 Py_DECREF(entry->key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000556 }
557 }
558 if (so->table != so->smalltable)
559 PyMem_DEL(so->table);
Raymond Hettinger8f8839e2013-09-07 20:26:50 -0700560 Py_TYPE(so)->tp_free(so);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000561 Py_TRASHCAN_SAFE_END(so)
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000562}
563
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000564static PyObject *
565set_repr(PySetObject *so)
566{
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200567 PyObject *result=NULL, *keys, *listrepr, *tmp;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000568 int status = Py_ReprEnter((PyObject*)so);
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000569
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000570 if (status != 0) {
571 if (status < 0)
572 return NULL;
573 return PyUnicode_FromFormat("%s(...)", Py_TYPE(so)->tp_name);
574 }
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000575
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000576 /* shortcut for the empty set */
577 if (!so->used) {
578 Py_ReprLeave((PyObject*)so);
579 return PyUnicode_FromFormat("%s()", Py_TYPE(so)->tp_name);
580 }
Georg Brandlc4996ba2006-08-28 19:37:11 +0000581
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000582 keys = PySequence_List((PyObject *)so);
583 if (keys == NULL)
584 goto done;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000585
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200586 /* repr(keys)[1:-1] */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000587 listrepr = PyObject_Repr(keys);
588 Py_DECREF(keys);
589 if (listrepr == NULL)
590 goto done;
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200591 tmp = PyUnicode_Substring(listrepr, 1, PyUnicode_GET_LENGTH(listrepr)-1);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000592 Py_DECREF(listrepr);
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200593 if (tmp == NULL)
594 goto done;
595 listrepr = tmp;
Victor Stinnera1a807b2011-05-26 14:24:30 +0200596
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200597 if (Py_TYPE(so) != &PySet_Type)
598 result = PyUnicode_FromFormat("%s({%U})",
599 Py_TYPE(so)->tp_name,
600 listrepr);
601 else
602 result = PyUnicode_FromFormat("{%U}", listrepr);
603 Py_DECREF(listrepr);
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000604done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000605 Py_ReprLeave((PyObject*)so);
606 return result;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000607}
608
Martin v. Löwis18e16552006-02-15 17:27:45 +0000609static Py_ssize_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000610set_len(PyObject *so)
611{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000612 return ((PySetObject *)so)->used;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000613}
614
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000615static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000616set_merge(PySetObject *so, PyObject *otherset)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000617{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000618 PySetObject *other;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000619 PyObject *key;
Éric Araujobbcfc1f2011-03-23 03:43:22 +0100620 Py_hash_t hash;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200621 Py_ssize_t i;
622 setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000623
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000624 assert (PyAnySet_Check(so));
625 assert (PyAnySet_Check(otherset));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000626
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000627 other = (PySetObject*)otherset;
628 if (other == so || other->used == 0)
629 /* a.update(a) or a.update({}); nothing to do */
630 return 0;
631 /* Do one big resize at the start, rather than
632 * incrementally resizing as we insert new keys. Expect
633 * that there will be no (or few) overlapping keys.
634 */
635 if ((so->fill + other->used)*3 >= (so->mask+1)*2) {
636 if (set_table_resize(so, (so->used + other->used)*2) != 0)
637 return -1;
638 }
639 for (i = 0; i <= other->mask; i++) {
640 entry = &other->table[i];
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000641 key = entry->key;
Éric Araujo48049912011-03-23 02:08:07 +0100642 hash = entry->hash;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000643 if (key != NULL &&
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -0500644 key != dummy) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000645 Py_INCREF(key);
Éric Araujo48049912011-03-23 02:08:07 +0100646 if (set_insert_key(so, key, hash) == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000647 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000648 return -1;
649 }
650 }
651 }
652 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000653}
654
655static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000656set_contains_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000657{
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000658 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000659 setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000660
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000661 if (!PyUnicode_CheckExact(key) ||
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200662 (hash = ((PyASCIIObject *) key)->hash) == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000663 hash = PyObject_Hash(key);
664 if (hash == -1)
665 return -1;
666 }
667 entry = (so->lookup)(so, key, hash);
668 if (entry == NULL)
669 return -1;
670 key = entry->key;
671 return key != NULL && key != dummy;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000672}
673
Raymond Hettingerc991db22005-08-11 07:58:45 +0000674static int
675set_contains_entry(PySetObject *so, setentry *entry)
676{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000677 PyObject *key;
678 setentry *lu_entry;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000679
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000680 lu_entry = (so->lookup)(so, entry->key, entry->hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000681 if (lu_entry == NULL)
682 return -1;
683 key = lu_entry->key;
684 return key != NULL && key != dummy;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000685}
686
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000687static PyObject *
688set_pop(PySetObject *so)
689{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200690 Py_ssize_t i = 0;
691 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000692 PyObject *key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000693
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000694 assert (PyAnySet_Check(so));
695 if (so->used == 0) {
696 PyErr_SetString(PyExc_KeyError, "pop from an empty set");
697 return NULL;
698 }
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000699
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000700 /* Set entry to "the first" unused or dummy set entry. We abuse
701 * the hash field of slot 0 to hold a search finger:
702 * If slot 0 has a value, use slot 0.
703 * Else slot 0 is being used to hold a search finger,
704 * and we use its hash value as the first index to look.
705 */
706 entry = &so->table[0];
707 if (entry->key == NULL || entry->key == dummy) {
708 i = entry->hash;
709 /* The hash field may be a real hash value, or it may be a
710 * legit search finger, or it may be a once-legit search
711 * finger that's out of bounds now because it wrapped around
712 * or the table shrunk -- simply make sure it's in bounds now.
713 */
714 if (i > so->mask || i < 1)
715 i = 1; /* skip slot 0 */
716 while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
717 i++;
718 if (i > so->mask)
719 i = 1;
720 }
721 }
722 key = entry->key;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000723 entry->key = dummy;
724 so->used--;
725 so->table[0].hash = i + 1; /* next place to start */
726 return key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000727}
728
Benjamin Petersonf10a79a2008-10-11 00:49:57 +0000729PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\
730Raises KeyError if the set is empty.");
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000731
732static int
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000733set_traverse(PySetObject *so, visitproc visit, void *arg)
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000734{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000735 Py_ssize_t pos = 0;
736 setentry *entry;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000737
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000738 while (set_next(so, &pos, &entry))
739 Py_VISIT(entry->key);
740 return 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000741}
742
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000743static Py_hash_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000744frozenset_hash(PyObject *self)
745{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000746 PySetObject *so = (PySetObject *)self;
Gregory P. Smith27cbcd62012-12-10 18:15:46 -0800747 Py_uhash_t h, hash = 1927868237UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000748 setentry *entry;
749 Py_ssize_t pos = 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000750
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000751 if (so->hash != -1)
752 return so->hash;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000753
Mark Dickinson57e683e2011-09-24 18:18:40 +0100754 hash *= (Py_uhash_t)PySet_GET_SIZE(self) + 1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000755 while (set_next(so, &pos, &entry)) {
756 /* Work to increase the bit dispersion for closely spaced hash
757 values. The is important because some use cases have many
758 combinations of a small number of elements with nearby
759 hashes so that many distinct combinations collapse to only
760 a handful of distinct hash values. */
Antoine Pitroufbb1c612010-10-23 17:37:54 +0000761 h = entry->hash;
Gregory P. Smith27cbcd62012-12-10 18:15:46 -0800762 hash ^= (h ^ (h << 16) ^ 89869747UL) * 3644798167UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000763 }
Gregory P. Smithc2176e42012-12-10 18:32:53 -0800764 hash = hash * 69069U + 907133923UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000765 if (hash == -1)
Gregory P. Smith27cbcd62012-12-10 18:15:46 -0800766 hash = 590923713UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000767 so->hash = hash;
768 return hash;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000769}
770
Raymond Hettingera9d99362005-08-05 00:01:15 +0000771/***** Set iterator type ***********************************************/
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000772
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000773typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000774 PyObject_HEAD
775 PySetObject *si_set; /* Set to NULL when iterator is exhausted */
776 Py_ssize_t si_used;
777 Py_ssize_t si_pos;
778 Py_ssize_t len;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000779} setiterobject;
780
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000781static void
782setiter_dealloc(setiterobject *si)
783{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000784 Py_XDECREF(si->si_set);
785 PyObject_GC_Del(si);
Antoine Pitrou7ddda782009-01-01 15:35:33 +0000786}
787
788static int
789setiter_traverse(setiterobject *si, visitproc visit, void *arg)
790{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000791 Py_VISIT(si->si_set);
792 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000793}
794
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000795static PyObject *
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000796setiter_len(setiterobject *si)
797{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000798 Py_ssize_t len = 0;
799 if (si->si_set != NULL && si->si_used == si->si_set->used)
800 len = si->len;
Antoine Pitrou671b4d92010-08-17 17:55:07 +0000801 return PyLong_FromSsize_t(len);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000802}
803
Armin Rigof5b3e362006-02-11 21:32:43 +0000804PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000805
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000806static PyObject *setiter_iternext(setiterobject *si);
807
808static PyObject *
809setiter_reduce(setiterobject *si)
810{
811 PyObject *list;
812 setiterobject tmp;
813
814 list = PyList_New(0);
815 if (!list)
816 return NULL;
817
Ezio Melotti0e1af282012-09-28 16:43:40 +0300818 /* copy the iterator state */
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000819 tmp = *si;
820 Py_XINCREF(tmp.si_set);
Ezio Melotti0e1af282012-09-28 16:43:40 +0300821
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000822 /* iterate the temporary into a list */
823 for(;;) {
824 PyObject *element = setiter_iternext(&tmp);
825 if (element) {
826 if (PyList_Append(list, element)) {
827 Py_DECREF(element);
828 Py_DECREF(list);
829 Py_XDECREF(tmp.si_set);
830 return NULL;
831 }
832 Py_DECREF(element);
833 } else
834 break;
835 }
836 Py_XDECREF(tmp.si_set);
837 /* check for error */
838 if (tmp.si_set != NULL) {
839 /* we have an error */
840 Py_DECREF(list);
841 return NULL;
842 }
Antoine Pitroua7013882012-04-05 00:04:20 +0200843 return Py_BuildValue("N(N)", _PyObject_GetBuiltin("iter"), list);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000844}
845
846PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
847
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000848static PyMethodDef setiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000849 {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000850 {"__reduce__", (PyCFunction)setiter_reduce, METH_NOARGS, reduce_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000851 {NULL, NULL} /* sentinel */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000852};
853
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000854static PyObject *setiter_iternext(setiterobject *si)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000855{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000856 PyObject *key;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200857 Py_ssize_t i, mask;
858 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000859 PySetObject *so = si->si_set;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000860
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000861 if (so == NULL)
862 return NULL;
863 assert (PyAnySet_Check(so));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000864
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000865 if (si->si_used != so->used) {
866 PyErr_SetString(PyExc_RuntimeError,
867 "Set changed size during iteration");
868 si->si_used = -1; /* Make this state sticky */
869 return NULL;
870 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000871
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000872 i = si->si_pos;
873 assert(i>=0);
874 entry = so->table;
875 mask = so->mask;
876 while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
877 i++;
878 si->si_pos = i+1;
879 if (i > mask)
880 goto fail;
881 si->len--;
882 key = entry[i].key;
883 Py_INCREF(key);
884 return key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000885
886fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000887 Py_DECREF(so);
888 si->si_set = NULL;
889 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000890}
891
Christian Heimesa22e8bd2007-11-29 22:35:39 +0000892PyTypeObject PySetIter_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000893 PyVarObject_HEAD_INIT(&PyType_Type, 0)
894 "set_iterator", /* tp_name */
895 sizeof(setiterobject), /* tp_basicsize */
896 0, /* tp_itemsize */
897 /* methods */
898 (destructor)setiter_dealloc, /* tp_dealloc */
899 0, /* tp_print */
900 0, /* tp_getattr */
901 0, /* tp_setattr */
902 0, /* tp_reserved */
903 0, /* tp_repr */
904 0, /* tp_as_number */
905 0, /* tp_as_sequence */
906 0, /* tp_as_mapping */
907 0, /* tp_hash */
908 0, /* tp_call */
909 0, /* tp_str */
910 PyObject_GenericGetAttr, /* tp_getattro */
911 0, /* tp_setattro */
912 0, /* tp_as_buffer */
913 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
914 0, /* tp_doc */
915 (traverseproc)setiter_traverse, /* tp_traverse */
916 0, /* tp_clear */
917 0, /* tp_richcompare */
918 0, /* tp_weaklistoffset */
919 PyObject_SelfIter, /* tp_iter */
920 (iternextfunc)setiter_iternext, /* tp_iternext */
921 setiter_methods, /* tp_methods */
922 0,
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000923};
924
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000925static PyObject *
926set_iter(PySetObject *so)
927{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000928 setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type);
929 if (si == NULL)
930 return NULL;
931 Py_INCREF(so);
932 si->si_set = so;
933 si->si_used = so->used;
934 si->si_pos = 0;
935 si->len = so->used;
936 _PyObject_GC_TRACK(si);
937 return (PyObject *)si;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000938}
939
Raymond Hettingerd7946662005-08-01 21:39:29 +0000940static int
Raymond Hettingerd7946662005-08-01 21:39:29 +0000941set_update_internal(PySetObject *so, PyObject *other)
Raymond Hettingera690a992003-11-16 16:17:49 +0000942{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000943 PyObject *key, *it;
Raymond Hettingera690a992003-11-16 16:17:49 +0000944
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000945 if (PyAnySet_Check(other))
946 return set_merge(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +0000947
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000948 if (PyDict_CheckExact(other)) {
949 PyObject *value;
950 Py_ssize_t pos = 0;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000951 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000952 Py_ssize_t dictsize = PyDict_Size(other);
Thomas Wouterscf297e42007-02-23 15:07:44 +0000953
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000954 /* Do one big resize at the start, rather than
955 * incrementally resizing as we insert new keys. Expect
956 * that there will be no (or few) overlapping keys.
957 */
958 if (dictsize == -1)
959 return -1;
960 if ((so->fill + dictsize)*3 >= (so->mask+1)*2) {
961 if (set_table_resize(so, (so->used + dictsize)*2) != 0)
962 return -1;
963 }
964 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
965 setentry an_entry;
Thomas Wouterscf297e42007-02-23 15:07:44 +0000966
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000967 an_entry.hash = hash;
968 an_entry.key = key;
969 if (set_add_entry(so, &an_entry) == -1)
970 return -1;
971 }
972 return 0;
973 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000974
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000975 it = PyObject_GetIter(other);
976 if (it == NULL)
977 return -1;
Raymond Hettingera690a992003-11-16 16:17:49 +0000978
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000979 while ((key = PyIter_Next(it)) != NULL) {
980 if (set_add_key(so, key) == -1) {
981 Py_DECREF(it);
982 Py_DECREF(key);
983 return -1;
984 }
985 Py_DECREF(key);
986 }
987 Py_DECREF(it);
988 if (PyErr_Occurred())
989 return -1;
990 return 0;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000991}
992
993static PyObject *
Georg Brandlc28e1fa2008-06-10 19:20:26 +0000994set_update(PySetObject *so, PyObject *args)
Raymond Hettingerd7946662005-08-01 21:39:29 +0000995{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000996 Py_ssize_t i;
Georg Brandlc28e1fa2008-06-10 19:20:26 +0000997
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000998 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
999 PyObject *other = PyTuple_GET_ITEM(args, i);
1000 if (set_update_internal(so, other) == -1)
1001 return NULL;
1002 }
1003 Py_RETURN_NONE;
Raymond Hettingera38123e2003-11-24 22:18:49 +00001004}
1005
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001006PyDoc_STRVAR(update_doc,
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001007"Update a set with the union of itself and others.");
Raymond Hettingera38123e2003-11-24 22:18:49 +00001008
1009static PyObject *
1010make_new_set(PyTypeObject *type, PyObject *iterable)
1011{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +02001012 PySetObject *so = NULL;
Raymond Hettingera38123e2003-11-24 22:18:49 +00001013
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001014 /* create PySetObject structure */
Raymond Hettinger8f8839e2013-09-07 20:26:50 -07001015 so = (PySetObject *)type->tp_alloc(type, 0);
1016 if (so == NULL)
1017 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001018
Raymond Hettinger4ea90802013-09-07 21:01:29 -07001019 so->fill = 0;
1020 so->used = 0;
1021 so->mask = PySet_MINSIZE - 1;
1022 so->table = so->smalltable;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001023 so->lookup = set_lookkey_unicode;
Raymond Hettinger4ea90802013-09-07 21:01:29 -07001024 so->hash = -1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001025 so->weakreflist = NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001026
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001027 if (iterable != NULL) {
1028 if (set_update_internal(so, iterable) == -1) {
1029 Py_DECREF(so);
1030 return NULL;
1031 }
1032 }
Raymond Hettingera38123e2003-11-24 22:18:49 +00001033
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001034 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001035}
1036
Raymond Hettinger7d99f092008-11-16 11:44:54 +00001037static PyObject *
1038make_new_set_basetype(PyTypeObject *type, PyObject *iterable)
1039{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001040 if (type != &PySet_Type && type != &PyFrozenSet_Type) {
1041 if (PyType_IsSubtype(type, &PySet_Type))
1042 type = &PySet_Type;
1043 else
1044 type = &PyFrozenSet_Type;
1045 }
1046 return make_new_set(type, iterable);
Raymond Hettinger7d99f092008-11-16 11:44:54 +00001047}
1048
Raymond Hettingerd7946662005-08-01 21:39:29 +00001049/* The empty frozenset is a singleton */
1050static PyObject *emptyfrozenset = NULL;
1051
Raymond Hettingera690a992003-11-16 16:17:49 +00001052static PyObject *
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001053frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
Raymond Hettingera690a992003-11-16 16:17:49 +00001054{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001055 PyObject *iterable = NULL, *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001056
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001057 if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds))
1058 return NULL;
Georg Brandl02c42872005-08-26 06:42:30 +00001059
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001060 if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
1061 return NULL;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001062
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001063 if (type != &PyFrozenSet_Type)
1064 return make_new_set(type, iterable);
Raymond Hettingerd7946662005-08-01 21:39:29 +00001065
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001066 if (iterable != NULL) {
1067 /* frozenset(f) is idempotent */
1068 if (PyFrozenSet_CheckExact(iterable)) {
1069 Py_INCREF(iterable);
1070 return iterable;
1071 }
1072 result = make_new_set(type, iterable);
1073 if (result == NULL || PySet_GET_SIZE(result))
1074 return result;
1075 Py_DECREF(result);
1076 }
1077 /* The empty frozenset is a singleton */
1078 if (emptyfrozenset == NULL)
1079 emptyfrozenset = make_new_set(type, NULL);
1080 Py_XINCREF(emptyfrozenset);
1081 return emptyfrozenset;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001082}
1083
Antoine Pitrou093ce9c2011-12-16 11:24:27 +01001084int
1085PySet_ClearFreeList(void)
Raymond Hettingerd7946662005-08-01 21:39:29 +00001086{
Raymond Hettinger8f8839e2013-09-07 20:26:50 -07001087 return 0;
Antoine Pitrou093ce9c2011-12-16 11:24:27 +01001088}
1089
1090void
1091PySet_Fini(void)
1092{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001093 Py_CLEAR(emptyfrozenset);
Raymond Hettingera690a992003-11-16 16:17:49 +00001094}
1095
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001096static PyObject *
1097set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1098{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001099 if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds))
1100 return NULL;
1101
1102 return make_new_set(type, NULL);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001103}
1104
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001105/* set_swap_bodies() switches the contents of any two sets by moving their
1106 internal data pointers and, if needed, copying the internal smalltables.
1107 Semantically equivalent to:
1108
1109 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1110
1111 The function always succeeds and it leaves both objects in a stable state.
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001112 Useful for creating temporary frozensets from sets for membership testing
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001113 in __contains__(), discard(), and remove(). Also useful for operations
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001114 that update in-place (by allowing an intermediate result to be swapped
Raymond Hettinger9dcb17c2005-07-31 13:09:28 +00001115 into one of the original inputs).
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001116*/
1117
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001118static void
1119set_swap_bodies(PySetObject *a, PySetObject *b)
Raymond Hettingera690a992003-11-16 16:17:49 +00001120{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001121 Py_ssize_t t;
1122 setentry *u;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001123 setentry *(*f)(PySetObject *so, PyObject *key, Py_ssize_t hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001124 setentry tab[PySet_MINSIZE];
Antoine Pitroufbb1c612010-10-23 17:37:54 +00001125 Py_hash_t h;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001126
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001127 t = a->fill; a->fill = b->fill; b->fill = t;
1128 t = a->used; a->used = b->used; b->used = t;
1129 t = a->mask; a->mask = b->mask; b->mask = t;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001130
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001131 u = a->table;
1132 if (a->table == a->smalltable)
1133 u = b->smalltable;
1134 a->table = b->table;
1135 if (b->table == b->smalltable)
1136 a->table = a->smalltable;
1137 b->table = u;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001138
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001139 f = a->lookup; a->lookup = b->lookup; b->lookup = f;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001140
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001141 if (a->table == a->smalltable || b->table == b->smalltable) {
1142 memcpy(tab, a->smalltable, sizeof(tab));
1143 memcpy(a->smalltable, b->smalltable, sizeof(tab));
1144 memcpy(b->smalltable, tab, sizeof(tab));
1145 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001146
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001147 if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type) &&
1148 PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) {
1149 h = a->hash; a->hash = b->hash; b->hash = h;
1150 } else {
1151 a->hash = -1;
1152 b->hash = -1;
1153 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001154}
1155
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001156static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001157set_copy(PySetObject *so)
1158{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001159 return make_new_set_basetype(Py_TYPE(so), (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001160}
1161
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001162static PyObject *
1163frozenset_copy(PySetObject *so)
1164{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001165 if (PyFrozenSet_CheckExact(so)) {
1166 Py_INCREF(so);
1167 return (PyObject *)so;
1168 }
1169 return set_copy(so);
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001170}
1171
Raymond Hettingera690a992003-11-16 16:17:49 +00001172PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
1173
1174static PyObject *
Raymond Hettingerc991db22005-08-11 07:58:45 +00001175set_clear(PySetObject *so)
1176{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001177 set_clear_internal(so);
1178 Py_RETURN_NONE;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001179}
1180
1181PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
1182
1183static PyObject *
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001184set_union(PySetObject *so, PyObject *args)
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001185{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001186 PySetObject *result;
1187 PyObject *other;
1188 Py_ssize_t i;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001189
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001190 result = (PySetObject *)set_copy(so);
1191 if (result == NULL)
1192 return NULL;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001193
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001194 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1195 other = PyTuple_GET_ITEM(args, i);
1196 if ((PyObject *)so == other)
1197 continue;
1198 if (set_update_internal(result, other) == -1) {
1199 Py_DECREF(result);
1200 return NULL;
1201 }
1202 }
1203 return (PyObject *)result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001204}
1205
1206PyDoc_STRVAR(union_doc,
1207 "Return the union of sets as a new set.\n\
1208\n\
1209(i.e. all elements that are in either set.)");
1210
1211static PyObject *
1212set_or(PySetObject *so, PyObject *other)
1213{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001214 PySetObject *result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001215
Brian Curtindfc80e32011-08-10 20:28:54 -05001216 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1217 Py_RETURN_NOTIMPLEMENTED;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001218
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001219 result = (PySetObject *)set_copy(so);
1220 if (result == NULL)
1221 return NULL;
1222 if ((PyObject *)so == other)
1223 return (PyObject *)result;
1224 if (set_update_internal(result, other) == -1) {
1225 Py_DECREF(result);
1226 return NULL;
1227 }
1228 return (PyObject *)result;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001229}
1230
Raymond Hettingera690a992003-11-16 16:17:49 +00001231static PyObject *
1232set_ior(PySetObject *so, PyObject *other)
1233{
Brian Curtindfc80e32011-08-10 20:28:54 -05001234 if (!PyAnySet_Check(other))
1235 Py_RETURN_NOTIMPLEMENTED;
1236
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001237 if (set_update_internal(so, other) == -1)
1238 return NULL;
1239 Py_INCREF(so);
1240 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001241}
1242
1243static PyObject *
1244set_intersection(PySetObject *so, PyObject *other)
1245{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001246 PySetObject *result;
1247 PyObject *key, *it, *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001248
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001249 if ((PyObject *)so == other)
1250 return set_copy(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001251
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001252 result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL);
1253 if (result == NULL)
1254 return NULL;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001255
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001256 if (PyAnySet_Check(other)) {
1257 Py_ssize_t pos = 0;
1258 setentry *entry;
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001259
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001260 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1261 tmp = (PyObject *)so;
1262 so = (PySetObject *)other;
1263 other = tmp;
1264 }
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001265
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001266 while (set_next((PySetObject *)other, &pos, &entry)) {
1267 int rv = set_contains_entry(so, entry);
1268 if (rv == -1) {
1269 Py_DECREF(result);
1270 return NULL;
1271 }
1272 if (rv) {
1273 if (set_add_entry(result, entry) == -1) {
1274 Py_DECREF(result);
1275 return NULL;
1276 }
1277 }
1278 }
1279 return (PyObject *)result;
1280 }
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001281
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001282 it = PyObject_GetIter(other);
1283 if (it == NULL) {
1284 Py_DECREF(result);
1285 return NULL;
1286 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001287
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001288 while ((key = PyIter_Next(it)) != NULL) {
1289 int rv;
1290 setentry entry;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001291 Py_hash_t hash = PyObject_Hash(key);
Thomas Wouters89f507f2006-12-13 04:49:30 +00001292
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001293 if (hash == -1) {
1294 Py_DECREF(it);
1295 Py_DECREF(result);
1296 Py_DECREF(key);
1297 return NULL;
1298 }
1299 entry.hash = hash;
1300 entry.key = key;
1301 rv = set_contains_entry(so, &entry);
1302 if (rv == -1) {
1303 Py_DECREF(it);
1304 Py_DECREF(result);
1305 Py_DECREF(key);
1306 return NULL;
1307 }
1308 if (rv) {
1309 if (set_add_entry(result, &entry) == -1) {
1310 Py_DECREF(it);
1311 Py_DECREF(result);
1312 Py_DECREF(key);
1313 return NULL;
1314 }
1315 }
1316 Py_DECREF(key);
1317 }
1318 Py_DECREF(it);
1319 if (PyErr_Occurred()) {
1320 Py_DECREF(result);
1321 return NULL;
1322 }
1323 return (PyObject *)result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001324}
1325
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001326static PyObject *
1327set_intersection_multi(PySetObject *so, PyObject *args)
1328{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001329 Py_ssize_t i;
1330 PyObject *result = (PyObject *)so;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001331
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001332 if (PyTuple_GET_SIZE(args) == 0)
1333 return set_copy(so);
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001334
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001335 Py_INCREF(so);
1336 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1337 PyObject *other = PyTuple_GET_ITEM(args, i);
1338 PyObject *newresult = set_intersection((PySetObject *)result, other);
1339 if (newresult == NULL) {
1340 Py_DECREF(result);
1341 return NULL;
1342 }
1343 Py_DECREF(result);
1344 result = newresult;
1345 }
1346 return result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001347}
1348
Raymond Hettingera690a992003-11-16 16:17:49 +00001349PyDoc_STRVAR(intersection_doc,
1350"Return the intersection of two sets as a new set.\n\
1351\n\
1352(i.e. all elements that are in both sets.)");
1353
1354static PyObject *
1355set_intersection_update(PySetObject *so, PyObject *other)
1356{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001357 PyObject *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001358
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001359 tmp = set_intersection(so, other);
1360 if (tmp == NULL)
1361 return NULL;
1362 set_swap_bodies(so, (PySetObject *)tmp);
1363 Py_DECREF(tmp);
1364 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001365}
1366
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001367static PyObject *
1368set_intersection_update_multi(PySetObject *so, PyObject *args)
1369{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001370 PyObject *tmp;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001371
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001372 tmp = set_intersection_multi(so, args);
1373 if (tmp == NULL)
1374 return NULL;
1375 set_swap_bodies(so, (PySetObject *)tmp);
1376 Py_DECREF(tmp);
1377 Py_RETURN_NONE;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001378}
1379
Raymond Hettingera690a992003-11-16 16:17:49 +00001380PyDoc_STRVAR(intersection_update_doc,
1381"Update a set with the intersection of itself and another.");
1382
1383static PyObject *
1384set_and(PySetObject *so, PyObject *other)
1385{
Brian Curtindfc80e32011-08-10 20:28:54 -05001386 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1387 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001388 return set_intersection(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001389}
1390
1391static PyObject *
1392set_iand(PySetObject *so, PyObject *other)
1393{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001394 PyObject *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001395
Brian Curtindfc80e32011-08-10 20:28:54 -05001396 if (!PyAnySet_Check(other))
1397 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001398 result = set_intersection_update(so, other);
1399 if (result == NULL)
1400 return NULL;
1401 Py_DECREF(result);
1402 Py_INCREF(so);
1403 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001404}
1405
Guido van Rossum58da9312007-11-10 23:39:45 +00001406static PyObject *
1407set_isdisjoint(PySetObject *so, PyObject *other)
1408{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001409 PyObject *key, *it, *tmp;
Guido van Rossum58da9312007-11-10 23:39:45 +00001410
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001411 if ((PyObject *)so == other) {
1412 if (PySet_GET_SIZE(so) == 0)
1413 Py_RETURN_TRUE;
1414 else
1415 Py_RETURN_FALSE;
1416 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001417
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001418 if (PyAnySet_CheckExact(other)) {
1419 Py_ssize_t pos = 0;
1420 setentry *entry;
Guido van Rossum58da9312007-11-10 23:39:45 +00001421
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001422 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1423 tmp = (PyObject *)so;
1424 so = (PySetObject *)other;
1425 other = tmp;
1426 }
1427 while (set_next((PySetObject *)other, &pos, &entry)) {
1428 int rv = set_contains_entry(so, entry);
1429 if (rv == -1)
1430 return NULL;
1431 if (rv)
1432 Py_RETURN_FALSE;
1433 }
1434 Py_RETURN_TRUE;
1435 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001436
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001437 it = PyObject_GetIter(other);
1438 if (it == NULL)
1439 return NULL;
Guido van Rossum58da9312007-11-10 23:39:45 +00001440
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001441 while ((key = PyIter_Next(it)) != NULL) {
1442 int rv;
1443 setentry entry;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001444 Py_hash_t hash = PyObject_Hash(key);
Guido van Rossum58da9312007-11-10 23:39:45 +00001445
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001446 if (hash == -1) {
1447 Py_DECREF(key);
1448 Py_DECREF(it);
1449 return NULL;
1450 }
1451 entry.hash = hash;
1452 entry.key = key;
1453 rv = set_contains_entry(so, &entry);
1454 Py_DECREF(key);
1455 if (rv == -1) {
1456 Py_DECREF(it);
1457 return NULL;
1458 }
1459 if (rv) {
1460 Py_DECREF(it);
1461 Py_RETURN_FALSE;
1462 }
1463 }
1464 Py_DECREF(it);
1465 if (PyErr_Occurred())
1466 return NULL;
1467 Py_RETURN_TRUE;
Guido van Rossum58da9312007-11-10 23:39:45 +00001468}
1469
1470PyDoc_STRVAR(isdisjoint_doc,
1471"Return True if two sets have a null intersection.");
1472
Neal Norwitz6576bd82005-11-13 18:41:28 +00001473static int
Raymond Hettingerc991db22005-08-11 07:58:45 +00001474set_difference_update_internal(PySetObject *so, PyObject *other)
1475{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001476 if ((PyObject *)so == other)
1477 return set_clear_internal(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001478
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001479 if (PyAnySet_Check(other)) {
1480 setentry *entry;
1481 Py_ssize_t pos = 0;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001482
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001483 while (set_next((PySetObject *)other, &pos, &entry))
1484 if (set_discard_entry(so, entry) == -1)
1485 return -1;
1486 } else {
1487 PyObject *key, *it;
1488 it = PyObject_GetIter(other);
1489 if (it == NULL)
1490 return -1;
1491
1492 while ((key = PyIter_Next(it)) != NULL) {
1493 if (set_discard_key(so, key) == -1) {
1494 Py_DECREF(it);
1495 Py_DECREF(key);
1496 return -1;
1497 }
1498 Py_DECREF(key);
1499 }
1500 Py_DECREF(it);
1501 if (PyErr_Occurred())
1502 return -1;
1503 }
1504 /* If more than 1/5 are dummies, then resize them away. */
1505 if ((so->fill - so->used) * 5 < so->mask)
1506 return 0;
1507 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001508}
1509
Raymond Hettingera690a992003-11-16 16:17:49 +00001510static PyObject *
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001511set_difference_update(PySetObject *so, PyObject *args)
Raymond Hettingera690a992003-11-16 16:17:49 +00001512{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001513 Py_ssize_t i;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001514
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001515 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1516 PyObject *other = PyTuple_GET_ITEM(args, i);
1517 if (set_difference_update_internal(so, other) == -1)
1518 return NULL;
1519 }
1520 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001521}
1522
1523PyDoc_STRVAR(difference_update_doc,
1524"Remove all elements of another set from this set.");
1525
1526static PyObject *
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001527set_copy_and_difference(PySetObject *so, PyObject *other)
1528{
1529 PyObject *result;
1530
1531 result = set_copy(so);
1532 if (result == NULL)
1533 return NULL;
1534 if (set_difference_update_internal((PySetObject *) result, other) != -1)
1535 return result;
1536 Py_DECREF(result);
1537 return NULL;
1538}
1539
1540static PyObject *
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001541set_difference(PySetObject *so, PyObject *other)
1542{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001543 PyObject *result;
1544 setentry *entry;
1545 Py_ssize_t pos = 0;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001546
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001547 if (!PyAnySet_Check(other) && !PyDict_CheckExact(other)) {
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001548 return set_copy_and_difference(so, other);
1549 }
1550
1551 /* If len(so) much more than len(other), it's more efficient to simply copy
1552 * so and then iterate other looking for common elements. */
1553 if ((PySet_GET_SIZE(so) >> 2) > PyObject_Size(other)) {
1554 return set_copy_and_difference(so, other);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001555 }
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001556
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001557 result = make_new_set_basetype(Py_TYPE(so), NULL);
1558 if (result == NULL)
1559 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001560
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001561 if (PyDict_CheckExact(other)) {
1562 while (set_next(so, &pos, &entry)) {
1563 setentry entrycopy;
1564 entrycopy.hash = entry->hash;
1565 entrycopy.key = entry->key;
Antoine Pitroufbb1c612010-10-23 17:37:54 +00001566 if (!_PyDict_Contains(other, entry->key, entry->hash)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001567 if (set_add_entry((PySetObject *)result, &entrycopy) == -1) {
1568 Py_DECREF(result);
1569 return NULL;
1570 }
1571 }
1572 }
1573 return result;
1574 }
1575
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001576 /* Iterate over so, checking for common elements in other. */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001577 while (set_next(so, &pos, &entry)) {
1578 int rv = set_contains_entry((PySetObject *)other, entry);
1579 if (rv == -1) {
1580 Py_DECREF(result);
1581 return NULL;
1582 }
1583 if (!rv) {
1584 if (set_add_entry((PySetObject *)result, entry) == -1) {
1585 Py_DECREF(result);
1586 return NULL;
1587 }
1588 }
1589 }
1590 return result;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001591}
1592
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001593static PyObject *
1594set_difference_multi(PySetObject *so, PyObject *args)
1595{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001596 Py_ssize_t i;
1597 PyObject *result, *other;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001598
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001599 if (PyTuple_GET_SIZE(args) == 0)
1600 return set_copy(so);
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001601
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001602 other = PyTuple_GET_ITEM(args, 0);
1603 result = set_difference(so, other);
1604 if (result == NULL)
1605 return NULL;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001606
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001607 for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) {
1608 other = PyTuple_GET_ITEM(args, i);
1609 if (set_difference_update_internal((PySetObject *)result, other) == -1) {
1610 Py_DECREF(result);
1611 return NULL;
1612 }
1613 }
1614 return result;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001615}
1616
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001617PyDoc_STRVAR(difference_doc,
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001618"Return the difference of two or more sets as a new set.\n\
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001619\n\
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001620(i.e. all elements that are in this set but not the others.)");
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001621static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001622set_sub(PySetObject *so, PyObject *other)
1623{
Brian Curtindfc80e32011-08-10 20:28:54 -05001624 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1625 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001626 return set_difference(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001627}
1628
1629static PyObject *
1630set_isub(PySetObject *so, PyObject *other)
1631{
Brian Curtindfc80e32011-08-10 20:28:54 -05001632 if (!PyAnySet_Check(other))
1633 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001634 if (set_difference_update_internal(so, other) == -1)
1635 return NULL;
1636 Py_INCREF(so);
1637 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001638}
1639
1640static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001641set_symmetric_difference_update(PySetObject *so, PyObject *other)
1642{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001643 PySetObject *otherset;
1644 PyObject *key;
1645 Py_ssize_t pos = 0;
1646 setentry *entry;
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;
1653 int rv;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001654 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001655 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
1656 setentry an_entry;
Thomas Wouters89f507f2006-12-13 04:49:30 +00001657
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001658 Py_INCREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001659 an_entry.hash = hash;
1660 an_entry.key = key;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001661
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001662 rv = set_discard_entry(so, &an_entry);
Georg Brandl2d444492010-09-03 10:52:55 +00001663 if (rv == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001664 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001665 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001666 }
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001667 if (rv == DISCARD_NOTFOUND) {
1668 if (set_add_entry(so, &an_entry) == -1) {
1669 Py_DECREF(key);
1670 return NULL;
1671 }
1672 }
Georg Brandl2d444492010-09-03 10:52:55 +00001673 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001674 }
1675 Py_RETURN_NONE;
1676 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001677
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001678 if (PyAnySet_Check(other)) {
1679 Py_INCREF(other);
1680 otherset = (PySetObject *)other;
1681 } else {
1682 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1683 if (otherset == NULL)
1684 return NULL;
1685 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001686
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001687 while (set_next(otherset, &pos, &entry)) {
1688 int rv = set_discard_entry(so, entry);
1689 if (rv == -1) {
1690 Py_DECREF(otherset);
1691 return NULL;
1692 }
1693 if (rv == DISCARD_NOTFOUND) {
1694 if (set_add_entry(so, entry) == -1) {
1695 Py_DECREF(otherset);
1696 return NULL;
1697 }
1698 }
1699 }
1700 Py_DECREF(otherset);
1701 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001702}
1703
1704PyDoc_STRVAR(symmetric_difference_update_doc,
1705"Update a set with the symmetric difference of itself and another.");
1706
1707static PyObject *
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001708set_symmetric_difference(PySetObject *so, PyObject *other)
1709{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001710 PyObject *rv;
1711 PySetObject *otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001712
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001713 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1714 if (otherset == NULL)
1715 return NULL;
1716 rv = set_symmetric_difference_update(otherset, (PyObject *)so);
1717 if (rv == NULL)
1718 return NULL;
1719 Py_DECREF(rv);
1720 return (PyObject *)otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001721}
1722
1723PyDoc_STRVAR(symmetric_difference_doc,
1724"Return the symmetric difference of two sets as a new set.\n\
1725\n\
1726(i.e. all elements that are in exactly one of the sets.)");
1727
1728static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001729set_xor(PySetObject *so, PyObject *other)
1730{
Brian Curtindfc80e32011-08-10 20:28:54 -05001731 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1732 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001733 return set_symmetric_difference(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001734}
1735
1736static PyObject *
1737set_ixor(PySetObject *so, PyObject *other)
1738{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001739 PyObject *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001740
Brian Curtindfc80e32011-08-10 20:28:54 -05001741 if (!PyAnySet_Check(other))
1742 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001743 result = set_symmetric_difference_update(so, other);
1744 if (result == NULL)
1745 return NULL;
1746 Py_DECREF(result);
1747 Py_INCREF(so);
1748 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001749}
1750
1751static PyObject *
1752set_issubset(PySetObject *so, PyObject *other)
1753{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001754 setentry *entry;
1755 Py_ssize_t pos = 0;
Raymond Hettingera690a992003-11-16 16:17:49 +00001756
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001757 if (!PyAnySet_Check(other)) {
1758 PyObject *tmp, *result;
1759 tmp = make_new_set(&PySet_Type, other);
1760 if (tmp == NULL)
1761 return NULL;
1762 result = set_issubset(so, tmp);
1763 Py_DECREF(tmp);
1764 return result;
1765 }
1766 if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
1767 Py_RETURN_FALSE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001768
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001769 while (set_next(so, &pos, &entry)) {
1770 int rv = set_contains_entry((PySetObject *)other, entry);
1771 if (rv == -1)
1772 return NULL;
1773 if (!rv)
1774 Py_RETURN_FALSE;
1775 }
1776 Py_RETURN_TRUE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001777}
1778
1779PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
1780
1781static PyObject *
1782set_issuperset(PySetObject *so, PyObject *other)
1783{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001784 PyObject *tmp, *result;
Raymond Hettinger3fbec702003-11-21 07:56:36 +00001785
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001786 if (!PyAnySet_Check(other)) {
1787 tmp = make_new_set(&PySet_Type, other);
1788 if (tmp == NULL)
1789 return NULL;
1790 result = set_issuperset(so, tmp);
1791 Py_DECREF(tmp);
1792 return result;
1793 }
1794 return set_issubset((PySetObject *)other, (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001795}
1796
1797PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
1798
Raymond Hettingera690a992003-11-16 16:17:49 +00001799static PyObject *
1800set_richcompare(PySetObject *v, PyObject *w, int op)
1801{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001802 PyObject *r1, *r2;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001803
Brian Curtindfc80e32011-08-10 20:28:54 -05001804 if(!PyAnySet_Check(w))
1805 Py_RETURN_NOTIMPLEMENTED;
1806
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001807 switch (op) {
1808 case Py_EQ:
1809 if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
1810 Py_RETURN_FALSE;
1811 if (v->hash != -1 &&
1812 ((PySetObject *)w)->hash != -1 &&
1813 v->hash != ((PySetObject *)w)->hash)
1814 Py_RETURN_FALSE;
1815 return set_issubset(v, w);
1816 case Py_NE:
1817 r1 = set_richcompare(v, w, Py_EQ);
1818 if (r1 == NULL)
1819 return NULL;
1820 r2 = PyBool_FromLong(PyObject_Not(r1));
1821 Py_DECREF(r1);
1822 return r2;
1823 case Py_LE:
1824 return set_issubset(v, w);
1825 case Py_GE:
1826 return set_issuperset(v, w);
1827 case Py_LT:
1828 if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))
1829 Py_RETURN_FALSE;
1830 return set_issubset(v, w);
1831 case Py_GT:
1832 if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
1833 Py_RETURN_FALSE;
1834 return set_issuperset(v, w);
1835 }
Brian Curtindfc80e32011-08-10 20:28:54 -05001836 Py_RETURN_NOTIMPLEMENTED;
Raymond Hettingera690a992003-11-16 16:17:49 +00001837}
1838
Raymond Hettingera690a992003-11-16 16:17:49 +00001839static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001840set_add(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001841{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001842 if (set_add_key(so, key) == -1)
1843 return NULL;
1844 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001845}
1846
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001847PyDoc_STRVAR(add_doc,
Raymond Hettingera690a992003-11-16 16:17:49 +00001848"Add an element to a set.\n\
1849\n\
1850This has no effect if the element is already present.");
1851
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001852static int
1853set_contains(PySetObject *so, PyObject *key)
1854{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001855 PyObject *tmpkey;
1856 int rv;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001857
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001858 rv = set_contains_key(so, key);
1859 if (rv == -1) {
1860 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1861 return -1;
1862 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001863 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001864 if (tmpkey == NULL)
1865 return -1;
Petri Lehtinen5acc27e2011-10-30 13:56:41 +02001866 rv = set_contains_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001867 Py_DECREF(tmpkey);
1868 }
1869 return rv;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001870}
1871
1872static PyObject *
1873set_direct_contains(PySetObject *so, PyObject *key)
1874{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001875 long result;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001876
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001877 result = set_contains(so, key);
1878 if (result == -1)
1879 return NULL;
1880 return PyBool_FromLong(result);
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001881}
1882
1883PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
1884
Raymond Hettingera690a992003-11-16 16:17:49 +00001885static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001886set_remove(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001887{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001888 PyObject *tmpkey;
1889 int rv;
Raymond Hettingerbfd334a2003-11-22 03:55:23 +00001890
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001891 rv = set_discard_key(so, key);
1892 if (rv == -1) {
1893 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1894 return NULL;
1895 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001896 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001897 if (tmpkey == NULL)
1898 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001899 rv = set_discard_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001900 Py_DECREF(tmpkey);
1901 if (rv == -1)
1902 return NULL;
1903 }
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00001904
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001905 if (rv == DISCARD_NOTFOUND) {
Raymond Hettinger69492da2013-09-02 15:59:26 -07001906 _PyErr_SetKeyError(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001907 return NULL;
1908 }
1909 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001910}
1911
1912PyDoc_STRVAR(remove_doc,
1913"Remove an element from a set; it must be a member.\n\
1914\n\
1915If the element is not a member, raise a KeyError.");
1916
1917static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001918set_discard(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001919{
Benjamin Peterson2b50a012011-10-30 14:24:44 -04001920 PyObject *tmpkey;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001921 int rv;
Raymond Hettinger0deab622003-12-13 18:53:18 +00001922
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001923 rv = set_discard_key(so, key);
1924 if (rv == -1) {
1925 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1926 return NULL;
1927 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001928 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001929 if (tmpkey == NULL)
1930 return NULL;
Petri Lehtinene0aa8032011-10-30 14:31:27 +02001931 rv = set_discard_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001932 Py_DECREF(tmpkey);
Petri Lehtinene0aa8032011-10-30 14:31:27 +02001933 if (rv == -1)
1934 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001935 }
1936 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001937}
1938
1939PyDoc_STRVAR(discard_doc,
1940"Remove an element from a set if it is a member.\n\
1941\n\
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001942If the element is not a member, do nothing.");
Raymond Hettingera690a992003-11-16 16:17:49 +00001943
1944static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001945set_reduce(PySetObject *so)
1946{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001947 PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;
Martin v. Löwisbd928fe2011-10-14 10:20:37 +02001948 _Py_IDENTIFIER(__dict__);
Raymond Hettingera690a992003-11-16 16:17:49 +00001949
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001950 keys = PySequence_List((PyObject *)so);
1951 if (keys == NULL)
1952 goto done;
1953 args = PyTuple_Pack(1, keys);
1954 if (args == NULL)
1955 goto done;
Martin v. Löwis1ee1b6f2011-10-10 18:11:30 +02001956 dict = _PyObject_GetAttrId((PyObject *)so, &PyId___dict__);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001957 if (dict == NULL) {
1958 PyErr_Clear();
1959 dict = Py_None;
1960 Py_INCREF(dict);
1961 }
1962 result = PyTuple_Pack(3, Py_TYPE(so), args, dict);
Raymond Hettingera690a992003-11-16 16:17:49 +00001963done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001964 Py_XDECREF(args);
1965 Py_XDECREF(keys);
1966 Py_XDECREF(dict);
1967 return result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001968}
1969
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001970static PyObject *
1971set_sizeof(PySetObject *so)
1972{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001973 Py_ssize_t res;
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001974
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001975 res = sizeof(PySetObject);
1976 if (so->table != so->smalltable)
1977 res = res + (so->mask + 1) * sizeof(setentry);
1978 return PyLong_FromSsize_t(res);
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001979}
1980
1981PyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes");
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001982static int
1983set_init(PySetObject *self, PyObject *args, PyObject *kwds)
1984{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001985 PyObject *iterable = NULL;
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001986
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001987 if (!PyAnySet_Check(self))
1988 return -1;
1989 if (PySet_Check(self) && !_PyArg_NoKeywords("set()", kwds))
1990 return -1;
1991 if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable))
1992 return -1;
1993 set_clear_internal(self);
1994 self->hash = -1;
1995 if (iterable == NULL)
1996 return 0;
1997 return set_update_internal(self, iterable);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001998}
1999
Raymond Hettingera690a992003-11-16 16:17:49 +00002000static PySequenceMethods set_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002001 set_len, /* sq_length */
2002 0, /* sq_concat */
2003 0, /* sq_repeat */
2004 0, /* sq_item */
2005 0, /* sq_slice */
2006 0, /* sq_ass_item */
2007 0, /* sq_ass_slice */
2008 (objobjproc)set_contains, /* sq_contains */
Raymond Hettingera690a992003-11-16 16:17:49 +00002009};
2010
2011/* set object ********************************************************/
2012
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002013#ifdef Py_DEBUG
2014static PyObject *test_c_api(PySetObject *so);
2015
2016PyDoc_STRVAR(test_c_api_doc, "Exercises C API. Returns True.\n\
2017All is well if assertions don't fail.");
2018#endif
2019
Raymond Hettingera690a992003-11-16 16:17:49 +00002020static PyMethodDef set_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002021 {"add", (PyCFunction)set_add, METH_O,
2022 add_doc},
2023 {"clear", (PyCFunction)set_clear, METH_NOARGS,
2024 clear_doc},
2025 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2026 contains_doc},
2027 {"copy", (PyCFunction)set_copy, METH_NOARGS,
2028 copy_doc},
2029 {"discard", (PyCFunction)set_discard, METH_O,
2030 discard_doc},
2031 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2032 difference_doc},
2033 {"difference_update", (PyCFunction)set_difference_update, METH_VARARGS,
2034 difference_update_doc},
2035 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2036 intersection_doc},
2037 {"intersection_update",(PyCFunction)set_intersection_update_multi, METH_VARARGS,
2038 intersection_update_doc},
2039 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2040 isdisjoint_doc},
2041 {"issubset", (PyCFunction)set_issubset, METH_O,
2042 issubset_doc},
2043 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2044 issuperset_doc},
2045 {"pop", (PyCFunction)set_pop, METH_NOARGS,
2046 pop_doc},
2047 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2048 reduce_doc},
2049 {"remove", (PyCFunction)set_remove, METH_O,
2050 remove_doc},
2051 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2052 sizeof_doc},
2053 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2054 symmetric_difference_doc},
2055 {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O,
2056 symmetric_difference_update_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002057#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002058 {"test_c_api", (PyCFunction)test_c_api, METH_NOARGS,
2059 test_c_api_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002060#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002061 {"union", (PyCFunction)set_union, METH_VARARGS,
2062 union_doc},
2063 {"update", (PyCFunction)set_update, METH_VARARGS,
2064 update_doc},
2065 {NULL, NULL} /* sentinel */
Raymond Hettingera690a992003-11-16 16:17:49 +00002066};
2067
2068static PyNumberMethods set_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002069 0, /*nb_add*/
2070 (binaryfunc)set_sub, /*nb_subtract*/
2071 0, /*nb_multiply*/
2072 0, /*nb_remainder*/
2073 0, /*nb_divmod*/
2074 0, /*nb_power*/
2075 0, /*nb_negative*/
2076 0, /*nb_positive*/
2077 0, /*nb_absolute*/
2078 0, /*nb_bool*/
2079 0, /*nb_invert*/
2080 0, /*nb_lshift*/
2081 0, /*nb_rshift*/
2082 (binaryfunc)set_and, /*nb_and*/
2083 (binaryfunc)set_xor, /*nb_xor*/
2084 (binaryfunc)set_or, /*nb_or*/
2085 0, /*nb_int*/
2086 0, /*nb_reserved*/
2087 0, /*nb_float*/
2088 0, /*nb_inplace_add*/
2089 (binaryfunc)set_isub, /*nb_inplace_subtract*/
2090 0, /*nb_inplace_multiply*/
2091 0, /*nb_inplace_remainder*/
2092 0, /*nb_inplace_power*/
2093 0, /*nb_inplace_lshift*/
2094 0, /*nb_inplace_rshift*/
2095 (binaryfunc)set_iand, /*nb_inplace_and*/
2096 (binaryfunc)set_ixor, /*nb_inplace_xor*/
2097 (binaryfunc)set_ior, /*nb_inplace_or*/
Raymond Hettingera690a992003-11-16 16:17:49 +00002098};
2099
2100PyDoc_STRVAR(set_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002101"set() -> new empty set object\n\
2102set(iterable) -> new set object\n\
Raymond Hettingera690a992003-11-16 16:17:49 +00002103\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002104Build an unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00002105
2106PyTypeObject PySet_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002107 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2108 "set", /* tp_name */
2109 sizeof(PySetObject), /* tp_basicsize */
2110 0, /* tp_itemsize */
2111 /* methods */
2112 (destructor)set_dealloc, /* tp_dealloc */
2113 0, /* tp_print */
2114 0, /* tp_getattr */
2115 0, /* tp_setattr */
2116 0, /* tp_reserved */
2117 (reprfunc)set_repr, /* tp_repr */
2118 &set_as_number, /* tp_as_number */
2119 &set_as_sequence, /* tp_as_sequence */
2120 0, /* tp_as_mapping */
Georg Brandl00da4e02010-10-18 07:32:48 +00002121 PyObject_HashNotImplemented, /* tp_hash */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002122 0, /* tp_call */
2123 0, /* tp_str */
2124 PyObject_GenericGetAttr, /* tp_getattro */
2125 0, /* tp_setattro */
2126 0, /* tp_as_buffer */
2127 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2128 Py_TPFLAGS_BASETYPE, /* tp_flags */
2129 set_doc, /* tp_doc */
2130 (traverseproc)set_traverse, /* tp_traverse */
2131 (inquiry)set_clear_internal, /* tp_clear */
2132 (richcmpfunc)set_richcompare, /* tp_richcompare */
Georg Brandl00da4e02010-10-18 07:32:48 +00002133 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2134 (getiterfunc)set_iter, /* tp_iter */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002135 0, /* tp_iternext */
2136 set_methods, /* tp_methods */
2137 0, /* tp_members */
2138 0, /* tp_getset */
2139 0, /* tp_base */
2140 0, /* tp_dict */
2141 0, /* tp_descr_get */
2142 0, /* tp_descr_set */
2143 0, /* tp_dictoffset */
2144 (initproc)set_init, /* tp_init */
2145 PyType_GenericAlloc, /* tp_alloc */
2146 set_new, /* tp_new */
2147 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002148};
2149
2150/* frozenset object ********************************************************/
2151
2152
2153static PyMethodDef frozenset_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002154 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2155 contains_doc},
2156 {"copy", (PyCFunction)frozenset_copy, METH_NOARGS,
2157 copy_doc},
2158 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2159 difference_doc},
2160 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2161 intersection_doc},
2162 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2163 isdisjoint_doc},
2164 {"issubset", (PyCFunction)set_issubset, METH_O,
2165 issubset_doc},
2166 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2167 issuperset_doc},
2168 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2169 reduce_doc},
2170 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2171 sizeof_doc},
2172 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2173 symmetric_difference_doc},
2174 {"union", (PyCFunction)set_union, METH_VARARGS,
2175 union_doc},
2176 {NULL, NULL} /* sentinel */
Raymond Hettingera690a992003-11-16 16:17:49 +00002177};
2178
2179static PyNumberMethods frozenset_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002180 0, /*nb_add*/
2181 (binaryfunc)set_sub, /*nb_subtract*/
2182 0, /*nb_multiply*/
2183 0, /*nb_remainder*/
2184 0, /*nb_divmod*/
2185 0, /*nb_power*/
2186 0, /*nb_negative*/
2187 0, /*nb_positive*/
2188 0, /*nb_absolute*/
2189 0, /*nb_bool*/
2190 0, /*nb_invert*/
2191 0, /*nb_lshift*/
2192 0, /*nb_rshift*/
2193 (binaryfunc)set_and, /*nb_and*/
2194 (binaryfunc)set_xor, /*nb_xor*/
2195 (binaryfunc)set_or, /*nb_or*/
Raymond Hettingera690a992003-11-16 16:17:49 +00002196};
2197
2198PyDoc_STRVAR(frozenset_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002199"frozenset() -> empty frozenset object\n\
2200frozenset(iterable) -> frozenset object\n\
Raymond Hettingera690a992003-11-16 16:17:49 +00002201\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002202Build an immutable unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00002203
2204PyTypeObject PyFrozenSet_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002205 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2206 "frozenset", /* tp_name */
2207 sizeof(PySetObject), /* tp_basicsize */
2208 0, /* tp_itemsize */
2209 /* methods */
2210 (destructor)set_dealloc, /* tp_dealloc */
2211 0, /* tp_print */
2212 0, /* tp_getattr */
2213 0, /* tp_setattr */
2214 0, /* tp_reserved */
2215 (reprfunc)set_repr, /* tp_repr */
2216 &frozenset_as_number, /* tp_as_number */
2217 &set_as_sequence, /* tp_as_sequence */
2218 0, /* tp_as_mapping */
2219 frozenset_hash, /* tp_hash */
2220 0, /* tp_call */
2221 0, /* tp_str */
2222 PyObject_GenericGetAttr, /* tp_getattro */
2223 0, /* tp_setattro */
2224 0, /* tp_as_buffer */
2225 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2226 Py_TPFLAGS_BASETYPE, /* tp_flags */
2227 frozenset_doc, /* tp_doc */
2228 (traverseproc)set_traverse, /* tp_traverse */
2229 (inquiry)set_clear_internal, /* tp_clear */
2230 (richcmpfunc)set_richcompare, /* tp_richcompare */
2231 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2232 (getiterfunc)set_iter, /* tp_iter */
2233 0, /* tp_iternext */
2234 frozenset_methods, /* tp_methods */
2235 0, /* tp_members */
2236 0, /* tp_getset */
2237 0, /* tp_base */
2238 0, /* tp_dict */
2239 0, /* tp_descr_get */
2240 0, /* tp_descr_set */
2241 0, /* tp_dictoffset */
2242 0, /* tp_init */
2243 PyType_GenericAlloc, /* tp_alloc */
2244 frozenset_new, /* tp_new */
2245 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002246};
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002247
2248
2249/***** C API functions *************************************************/
2250
2251PyObject *
2252PySet_New(PyObject *iterable)
2253{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002254 return make_new_set(&PySet_Type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002255}
2256
2257PyObject *
2258PyFrozenSet_New(PyObject *iterable)
2259{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002260 return make_new_set(&PyFrozenSet_Type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002261}
2262
Neal Norwitz8c49c822006-03-04 18:41:19 +00002263Py_ssize_t
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002264PySet_Size(PyObject *anyset)
2265{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002266 if (!PyAnySet_Check(anyset)) {
2267 PyErr_BadInternalCall();
2268 return -1;
2269 }
2270 return PySet_GET_SIZE(anyset);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002271}
2272
2273int
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002274PySet_Clear(PyObject *set)
2275{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002276 if (!PySet_Check(set)) {
2277 PyErr_BadInternalCall();
2278 return -1;
2279 }
2280 return set_clear_internal((PySetObject *)set);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002281}
2282
2283int
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002284PySet_Contains(PyObject *anyset, PyObject *key)
2285{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002286 if (!PyAnySet_Check(anyset)) {
2287 PyErr_BadInternalCall();
2288 return -1;
2289 }
2290 return set_contains_key((PySetObject *)anyset, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002291}
2292
2293int
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002294PySet_Discard(PyObject *set, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002295{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002296 if (!PySet_Check(set)) {
2297 PyErr_BadInternalCall();
2298 return -1;
2299 }
2300 return set_discard_key((PySetObject *)set, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002301}
2302
2303int
Christian Heimesfd66e512008-01-29 12:18:50 +00002304PySet_Add(PyObject *anyset, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002305{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002306 if (!PySet_Check(anyset) &&
2307 (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
2308 PyErr_BadInternalCall();
2309 return -1;
2310 }
2311 return set_add_key((PySetObject *)anyset, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002312}
2313
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002314int
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002315_PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash)
Guido van Rossumd8faa362007-04-27 19:54:29 +00002316{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002317 setentry *entry;
Guido van Rossumd8faa362007-04-27 19:54:29 +00002318
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002319 if (!PyAnySet_Check(set)) {
2320 PyErr_BadInternalCall();
2321 return -1;
2322 }
2323 if (set_next((PySetObject *)set, pos, &entry) == 0)
2324 return 0;
2325 *key = entry->key;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002326 *hash = entry->hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002327 return 1;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002328}
2329
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002330PyObject *
2331PySet_Pop(PyObject *set)
2332{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002333 if (!PySet_Check(set)) {
2334 PyErr_BadInternalCall();
2335 return NULL;
2336 }
2337 return set_pop((PySetObject *)set);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002338}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002339
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002340int
2341_PySet_Update(PyObject *set, PyObject *iterable)
2342{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002343 if (!PySet_Check(set)) {
2344 PyErr_BadInternalCall();
2345 return -1;
2346 }
2347 return set_update_internal((PySetObject *)set, iterable);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002348}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002349
2350#ifdef Py_DEBUG
2351
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002352/* Test code to be called with any three element set.
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002353 Returns True and original set is restored. */
2354
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002355#define assertRaises(call_return_value, exception) \
2356 do { \
2357 assert(call_return_value); \
2358 assert(PyErr_ExceptionMatches(exception)); \
2359 PyErr_Clear(); \
2360 } while(0)
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002361
2362static PyObject *
2363test_c_api(PySetObject *so)
2364{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002365 Py_ssize_t count;
2366 char *s;
2367 Py_ssize_t i;
Raymond Hettinger583cd032013-09-07 22:06:35 -07002368 PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x=NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002369 PyObject *ob = (PyObject *)so;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002370 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002371 PyObject *str;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002372
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002373 /* Verify preconditions */
2374 assert(PyAnySet_Check(ob));
2375 assert(PyAnySet_CheckExact(ob));
2376 assert(!PyFrozenSet_CheckExact(ob));
Victor Stinner08b36bd2010-03-13 00:19:17 +00002377
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002378 /* so.clear(); so |= set("abc"); */
2379 str = PyUnicode_FromString("abc");
2380 if (str == NULL)
2381 return NULL;
2382 set_clear_internal(so);
2383 if (set_update_internal(so, str) == -1) {
2384 Py_DECREF(str);
2385 return NULL;
2386 }
2387 Py_DECREF(str);
Victor Stinner08b36bd2010-03-13 00:19:17 +00002388
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002389 /* Exercise type/size checks */
2390 assert(PySet_Size(ob) == 3);
2391 assert(PySet_GET_SIZE(ob) == 3);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002392
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002393 /* Raise TypeError for non-iterable constructor arguments */
2394 assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
2395 assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002396
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002397 /* Raise TypeError for unhashable key */
2398 dup = PySet_New(ob);
2399 assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
2400 assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
2401 assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002402
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002403 /* Exercise successful pop, contains, add, and discard */
2404 elem = PySet_Pop(ob);
2405 assert(PySet_Contains(ob, elem) == 0);
2406 assert(PySet_GET_SIZE(ob) == 2);
2407 assert(PySet_Add(ob, elem) == 0);
2408 assert(PySet_Contains(ob, elem) == 1);
2409 assert(PySet_GET_SIZE(ob) == 3);
2410 assert(PySet_Discard(ob, elem) == 1);
2411 assert(PySet_GET_SIZE(ob) == 2);
2412 assert(PySet_Discard(ob, elem) == 0);
2413 assert(PySet_GET_SIZE(ob) == 2);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002414
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002415 /* Exercise clear */
2416 dup2 = PySet_New(dup);
2417 assert(PySet_Clear(dup2) == 0);
2418 assert(PySet_Size(dup2) == 0);
2419 Py_DECREF(dup2);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002420
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002421 /* Raise SystemError on clear or update of frozen set */
2422 f = PyFrozenSet_New(dup);
2423 assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
2424 assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
2425 assert(PySet_Add(f, elem) == 0);
2426 Py_INCREF(f);
2427 assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
2428 Py_DECREF(f);
2429 Py_DECREF(f);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002430
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002431 /* Exercise direct iteration */
2432 i = 0, count = 0;
2433 while (_PySet_NextEntry((PyObject *)dup, &i, &x, &hash)) {
2434 s = _PyUnicode_AsString(x);
2435 assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
2436 count++;
2437 }
2438 assert(count == 3);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002439
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002440 /* Exercise updates */
2441 dup2 = PySet_New(NULL);
2442 assert(_PySet_Update(dup2, dup) == 0);
2443 assert(PySet_Size(dup2) == 3);
2444 assert(_PySet_Update(dup2, dup) == 0);
2445 assert(PySet_Size(dup2) == 3);
2446 Py_DECREF(dup2);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002447
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002448 /* Raise SystemError when self argument is not a set or frozenset. */
2449 t = PyTuple_New(0);
2450 assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
2451 assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
2452 Py_DECREF(t);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002453
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002454 /* Raise SystemError when self argument is not a set. */
2455 f = PyFrozenSet_New(dup);
2456 assert(PySet_Size(f) == 3);
2457 assert(PyFrozenSet_CheckExact(f));
2458 assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
2459 assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
2460 Py_DECREF(f);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002461
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002462 /* Raise KeyError when popping from an empty set */
2463 assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
2464 Py_DECREF(ob);
2465 assert(PySet_GET_SIZE(ob) == 0);
2466 assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002467
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002468 /* Restore the set from the copy using the PyNumber API */
2469 assert(PyNumber_InPlaceOr(ob, dup) == ob);
2470 Py_DECREF(ob);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002471
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002472 /* Verify constructors accept NULL arguments */
2473 f = PySet_New(NULL);
2474 assert(f != NULL);
2475 assert(PySet_GET_SIZE(f) == 0);
2476 Py_DECREF(f);
2477 f = PyFrozenSet_New(NULL);
2478 assert(f != NULL);
2479 assert(PyFrozenSet_CheckExact(f));
2480 assert(PySet_GET_SIZE(f) == 0);
2481 Py_DECREF(f);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002482
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002483 Py_DECREF(elem);
2484 Py_DECREF(dup);
2485 Py_RETURN_TRUE;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002486}
2487
Raymond Hettinger9bda1d62005-09-16 07:14:21 +00002488#undef assertRaises
2489
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002490#endif
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -05002491
2492/***** Dummy Struct *************************************************/
2493
2494static PyObject *
2495dummy_repr(PyObject *op)
2496{
2497 return PyUnicode_FromString("<dummy key>");
2498}
2499
2500static void
2501dummy_dealloc(PyObject* ignore)
2502{
2503 Py_FatalError("deallocating <dummy key>");
2504}
2505
2506static PyTypeObject _PySetDummy_Type = {
2507 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2508 "<dummy key> type",
2509 0,
2510 0,
2511 dummy_dealloc, /*tp_dealloc*/ /*never called*/
2512 0, /*tp_print*/
2513 0, /*tp_getattr*/
2514 0, /*tp_setattr*/
2515 0, /*tp_reserved*/
2516 dummy_repr, /*tp_repr*/
2517 0, /*tp_as_number*/
2518 0, /*tp_as_sequence*/
2519 0, /*tp_as_mapping*/
2520 0, /*tp_hash */
2521 0, /*tp_call */
2522 0, /*tp_str */
2523 0, /*tp_getattro */
2524 0, /*tp_setattro */
2525 0, /*tp_as_buffer */
2526 Py_TPFLAGS_DEFAULT, /*tp_flags */
2527};
2528
2529static PyObject _dummy_struct = {
2530 _PyObject_EXTRA_INIT
2531 2, &_PySetDummy_Type
2532};
2533