blob: eff91c566d17d1b8a320f73982d47c787e11db69 [file] [log] [blame]
Raymond Hettingerc991db22005-08-11 07:58:45 +00001
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002/* set object implementation
Raymond Hettingera9d99362005-08-05 00:01:15 +00003 Written and maintained by Raymond D. Hettinger <python@rcn.com>
4 Derived from Lib/sets.py and Objects/dictobject.c.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00005
Raymond Hettinger2212e522008-11-30 23:43:36 +00006 Copyright (c) 2003-2008 Python Software Foundation.
Raymond Hettingera9d99362005-08-05 00:01:15 +00007 All rights reserved.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00008*/
9
Raymond Hettingera690a992003-11-16 16:17:49 +000010#include "Python.h"
Raymond Hettingera9d99362005-08-05 00:01:15 +000011#include "structmember.h"
Christian Heimes0ded5b52007-12-10 15:50:56 +000012#include "stringlib/eq.h"
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000013
Thomas Wouters89f507f2006-12-13 04:49:30 +000014/* Set a key error with the specified argument, wrapping it in a
15 * tuple automatically so that tuple keys are not unpacked as the
16 * exception arguments. */
17static void
18set_key_error(PyObject *arg)
19{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000020 PyObject *tup;
21 tup = PyTuple_Pack(1, arg);
22 if (!tup)
23 return; /* caller will expect error to be set anyway */
24 PyErr_SetObject(PyExc_KeyError, tup);
25 Py_DECREF(tup);
Thomas Wouters89f507f2006-12-13 04:49:30 +000026}
27
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000028/* This must be >= 1. */
29#define PERTURB_SHIFT 5
30
31/* Object used as dummy key to fill deleted entries */
Raymond Hettingera9d99362005-08-05 00:01:15 +000032static PyObject *dummy = NULL; /* Initialized by first call to make_new_set() */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000033
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000034#ifdef Py_REF_DEBUG
35PyObject *
36_PySet_Dummy(void)
37{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000038 return dummy;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000039}
40#endif
41
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000042#define INIT_NONZERO_SET_SLOTS(so) do { \
43 (so)->table = (so)->smalltable; \
44 (so)->mask = PySet_MINSIZE - 1; \
45 (so)->hash = -1; \
Raymond Hettingerbc841a12005-08-07 13:02:53 +000046 } while(0)
47
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000048#define EMPTY_TO_MINSIZE(so) do { \
49 memset((so)->smalltable, 0, sizeof((so)->smalltable)); \
50 (so)->used = (so)->fill = 0; \
51 INIT_NONZERO_SET_SLOTS(so); \
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000052 } while(0)
53
Raymond Hettingerbc841a12005-08-07 13:02:53 +000054/* Reuse scheme to save calls to malloc, free, and memset */
Christian Heimes2202f872008-02-06 14:31:34 +000055#ifndef PySet_MAXFREELIST
56#define PySet_MAXFREELIST 80
57#endif
58static PySetObject *free_list[PySet_MAXFREELIST];
59static int numfree = 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000060
Christian Heimes0ded5b52007-12-10 15:50:56 +000061
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000062/*
63The basic lookup function used by all operations.
64This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
65Open addressing is preferred over chaining since the link overhead for
66chaining would be substantial (100% with typical malloc overhead).
67
68The initial probe index is computed as hash mod the table size. Subsequent
Raymond Hettingerbc841a12005-08-07 13:02:53 +000069probe indices are computed as explained in Objects/dictobject.c.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000070
71All arithmetic on hash should ignore overflow.
72
Raymond Hettinger9bda1d62005-09-16 07:14:21 +000073Unlike the dictionary implementation, the lookkey functions can return
74NULL if the rich comparison returns an error.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000075*/
76
77static setentry *
Antoine Pitrou9ed5f272013-08-13 20:18:52 +020078set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000079{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +020080 size_t i; /* Unsigned for defined overflow behavior. */
81 size_t perturb;
82 setentry *freeslot;
83 size_t mask = so->mask;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000084 setentry *table = so->table;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +020085 setentry *entry;
86 int cmp;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000087 PyObject *startkey;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000088
Mark Dickinson57e683e2011-09-24 18:18:40 +010089 i = (size_t)hash & mask;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000090 entry = &table[i];
91 if (entry->key == NULL || entry->key == key)
92 return entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000093
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000094 if (entry->key == dummy)
95 freeslot = entry;
96 else {
97 if (entry->hash == hash) {
98 startkey = entry->key;
99 Py_INCREF(startkey);
100 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
101 Py_DECREF(startkey);
102 if (cmp < 0)
103 return NULL;
104 if (table == so->table && entry->key == startkey) {
105 if (cmp > 0)
106 return entry;
107 }
108 else {
109 /* The compare did major nasty stuff to the
110 * set: start over.
111 */
112 return set_lookkey(so, key, hash);
113 }
114 }
115 freeslot = NULL;
116 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000117
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000118 /* In the loop, key == dummy is by far (factor of 100s) the
119 least likely outcome, so test for that last. */
120 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
Raymond Hettingerc629d4c2013-08-05 22:24:50 -0700121 i = i * 5 + perturb + 1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000122 entry = &table[i & mask];
123 if (entry->key == NULL) {
124 if (freeslot != NULL)
125 entry = freeslot;
126 break;
127 }
128 if (entry->key == key)
129 break;
130 if (entry->hash == hash && entry->key != dummy) {
131 startkey = entry->key;
132 Py_INCREF(startkey);
133 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
134 Py_DECREF(startkey);
135 if (cmp < 0)
136 return NULL;
137 if (table == so->table && entry->key == startkey) {
138 if (cmp > 0)
139 break;
140 }
141 else {
142 /* The compare did major nasty stuff to the
143 * set: start over.
144 */
145 return set_lookkey(so, key, hash);
146 }
147 }
148 else if (entry->key == dummy && freeslot == NULL)
149 freeslot = entry;
150 }
151 return entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000152}
153
154/*
Christian Heimes0ded5b52007-12-10 15:50:56 +0000155 * Hacked up version of set_lookkey which can assume keys are always unicode;
156 * This means we can always use unicode_eq directly and not have to check to
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000157 * see if the comparison altered the table.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000158 */
159static setentry *
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200160set_lookkey_unicode(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000161{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200162 size_t i; /* Unsigned for defined overflow behavior. */
163 size_t perturb;
164 setentry *freeslot;
165 size_t mask = so->mask;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000166 setentry *table = so->table;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200167 setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000168
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000169 /* Make sure this function doesn't have to handle non-unicode keys,
170 including subclasses of str; e.g., one reason to subclass
171 strings is to override __eq__, and for speed we don't cater to
172 that here. */
173 if (!PyUnicode_CheckExact(key)) {
174 so->lookup = set_lookkey;
175 return set_lookkey(so, key, hash);
176 }
Mark Dickinson57e683e2011-09-24 18:18:40 +0100177 i = (size_t)hash & mask;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000178 entry = &table[i];
179 if (entry->key == NULL || entry->key == key)
180 return entry;
181 if (entry->key == dummy)
182 freeslot = entry;
183 else {
184 if (entry->hash == hash && unicode_eq(entry->key, key))
185 return entry;
186 freeslot = NULL;
187 }
Raymond Hettingered6c1ef2005-08-13 08:28:03 +0000188
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000189 /* In the loop, key == dummy is by far (factor of 100s) the
190 least likely outcome, so test for that last. */
191 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
Raymond Hettingerc629d4c2013-08-05 22:24:50 -0700192 i = i * 5 + perturb + 1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000193 entry = &table[i & mask];
194 if (entry->key == NULL)
195 return freeslot == NULL ? entry : freeslot;
196 if (entry->key == key
197 || (entry->hash == hash
198 && entry->key != dummy
199 && unicode_eq(entry->key, key)))
200 return entry;
201 if (entry->key == dummy && freeslot == NULL)
202 freeslot = entry;
203 }
204 assert(0); /* NOT REACHED */
205 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000206}
207
208/*
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000209Internal routine to insert a new key into the table.
Thomas Wouters89f507f2006-12-13 04:49:30 +0000210Used by the public insert routine.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000211Eats a reference to key.
212*/
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000213static int
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200214set_insert_key(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000215{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200216 setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000217
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000218 assert(so->lookup != NULL);
219 entry = so->lookup(so, key, hash);
220 if (entry == NULL)
221 return -1;
222 if (entry->key == NULL) {
223 /* UNUSED */
224 so->fill++;
225 entry->key = key;
226 entry->hash = hash;
227 so->used++;
228 } else if (entry->key == dummy) {
229 /* DUMMY */
230 entry->key = key;
231 entry->hash = hash;
232 so->used++;
233 Py_DECREF(dummy);
234 } else {
235 /* ACTIVE */
236 Py_DECREF(key);
237 }
238 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000239}
240
241/*
Thomas Wouters89f507f2006-12-13 04:49:30 +0000242Internal routine used by set_table_resize() to insert an item which is
243known to be absent from the set. This routine also assumes that
244the set contains no deleted entries. Besides the performance benefit,
245using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
246Note that no refcounts are changed by this routine; if needed, the caller
247is responsible for incref'ing `key`.
248*/
249static void
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200250set_insert_clean(PySetObject *so, PyObject *key, Py_hash_t hash)
Thomas Wouters89f507f2006-12-13 04:49:30 +0000251{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200252 size_t i;
253 size_t perturb;
254 size_t mask = (size_t)so->mask;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000255 setentry *table = so->table;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200256 setentry *entry;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000257
Mark Dickinson57e683e2011-09-24 18:18:40 +0100258 i = (size_t)hash & mask;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000259 entry = &table[i];
260 for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) {
Raymond Hettingerc629d4c2013-08-05 22:24:50 -0700261 i = i * 5 + perturb + 1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000262 entry = &table[i & mask];
263 }
264 so->fill++;
265 entry->key = key;
266 entry->hash = hash;
267 so->used++;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000268}
269
270/*
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000271Restructure the table by allocating a new table and reinserting all
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000272keys again. When entries have been deleted, the new table may
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000273actually be smaller than the old one.
274*/
275static int
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000276set_table_resize(PySetObject *so, Py_ssize_t minused)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000277{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000278 Py_ssize_t newsize;
279 setentry *oldtable, *newtable, *entry;
280 Py_ssize_t i;
281 int is_oldtable_malloced;
282 setentry small_copy[PySet_MINSIZE];
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000283
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000284 assert(minused >= 0);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000285
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000286 /* Find the smallest table size > minused. */
287 for (newsize = PySet_MINSIZE;
288 newsize <= minused && newsize > 0;
289 newsize <<= 1)
290 ;
291 if (newsize <= 0) {
292 PyErr_NoMemory();
293 return -1;
294 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000295
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000296 /* Get space for a new table. */
297 oldtable = so->table;
298 assert(oldtable != NULL);
299 is_oldtable_malloced = oldtable != so->smalltable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000300
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000301 if (newsize == PySet_MINSIZE) {
302 /* A large table is shrinking, or we can't get any smaller. */
303 newtable = so->smalltable;
304 if (newtable == oldtable) {
305 if (so->fill == so->used) {
306 /* No dummies, so no point doing anything. */
307 return 0;
308 }
309 /* We're not going to resize it, but rebuild the
310 table anyway to purge old dummy entries.
311 Subtle: This is *necessary* if fill==size,
312 as set_lookkey needs at least one virgin slot to
313 terminate failing searches. If fill < size, it's
314 merely desirable, as dummies slow searches. */
315 assert(so->fill > so->used);
316 memcpy(small_copy, oldtable, sizeof(small_copy));
317 oldtable = small_copy;
318 }
319 }
320 else {
321 newtable = PyMem_NEW(setentry, newsize);
322 if (newtable == NULL) {
323 PyErr_NoMemory();
324 return -1;
325 }
326 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000327
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000328 /* Make the set empty, using the new table. */
329 assert(newtable != oldtable);
330 so->table = newtable;
331 so->mask = newsize - 1;
332 memset(newtable, 0, sizeof(setentry) * newsize);
333 so->used = 0;
334 i = so->fill;
335 so->fill = 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000336
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000337 /* Copy the data over; this is refcount-neutral for active entries;
338 dummy entries aren't copied over, of course */
339 for (entry = oldtable; i > 0; entry++) {
340 if (entry->key == NULL) {
341 /* UNUSED */
342 ;
343 } else if (entry->key == dummy) {
344 /* DUMMY */
345 --i;
346 assert(entry->key == dummy);
347 Py_DECREF(entry->key);
348 } else {
349 /* ACTIVE */
350 --i;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000351 set_insert_clean(so, entry->key, entry->hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000352 }
353 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000354
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000355 if (is_oldtable_malloced)
356 PyMem_DEL(oldtable);
357 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000358}
359
Raymond Hettingerc991db22005-08-11 07:58:45 +0000360/* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
361
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000362static int
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200363set_add_entry(PySetObject *so, setentry *entry)
Raymond Hettingerc991db22005-08-11 07:58:45 +0000364{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200365 Py_ssize_t n_used;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000366 PyObject *key = entry->key;
Éric Araujobbcfc1f2011-03-23 03:43:22 +0100367 Py_hash_t hash = entry->hash;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000368
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000369 assert(so->fill <= so->mask); /* at least one empty slot */
370 n_used = so->used;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000371 Py_INCREF(key);
Éric Araujo48049912011-03-23 02:08:07 +0100372 if (set_insert_key(so, key, hash) == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000373 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000374 return -1;
375 }
376 if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
377 return 0;
378 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettingerc991db22005-08-11 07:58:45 +0000379}
380
381static int
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200382set_add_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000383{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200384 Py_hash_t hash;
385 Py_ssize_t n_used;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000386
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000387 if (!PyUnicode_CheckExact(key) ||
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200388 (hash = ((PyASCIIObject *) key)->hash) == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000389 hash = PyObject_Hash(key);
390 if (hash == -1)
391 return -1;
392 }
393 assert(so->fill <= so->mask); /* at least one empty slot */
394 n_used = so->used;
395 Py_INCREF(key);
396 if (set_insert_key(so, key, hash) == -1) {
397 Py_DECREF(key);
398 return -1;
399 }
400 if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
401 return 0;
402 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000403}
404
405#define DISCARD_NOTFOUND 0
406#define DISCARD_FOUND 1
407
408static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000409set_discard_entry(PySetObject *so, setentry *oldentry)
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200410{ setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000411 PyObject *old_key;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000412
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000413 entry = (so->lookup)(so, oldentry->key, oldentry->hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000414 if (entry == NULL)
415 return -1;
416 if (entry->key == NULL || entry->key == dummy)
417 return DISCARD_NOTFOUND;
418 old_key = entry->key;
419 Py_INCREF(dummy);
420 entry->key = dummy;
421 so->used--;
422 Py_DECREF(old_key);
423 return DISCARD_FOUND;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000424}
425
426static int
427set_discard_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000428{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200429 Py_hash_t hash;
430 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000431 PyObject *old_key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000432
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000433 assert (PyAnySet_Check(so));
Christian Heimes0ded5b52007-12-10 15:50:56 +0000434
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000435 if (!PyUnicode_CheckExact(key) ||
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200436 (hash = ((PyASCIIObject *) key)->hash) == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000437 hash = PyObject_Hash(key);
438 if (hash == -1)
439 return -1;
440 }
441 entry = (so->lookup)(so, key, hash);
442 if (entry == NULL)
443 return -1;
444 if (entry->key == NULL || entry->key == dummy)
445 return DISCARD_NOTFOUND;
446 old_key = entry->key;
447 Py_INCREF(dummy);
448 entry->key = dummy;
449 so->used--;
450 Py_DECREF(old_key);
451 return DISCARD_FOUND;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000452}
453
Raymond Hettingerfe889f32005-08-06 05:43:39 +0000454static int
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000455set_clear_internal(PySetObject *so)
456{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000457 setentry *entry, *table;
458 int table_is_malloced;
459 Py_ssize_t fill;
460 setentry small_copy[PySet_MINSIZE];
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000461#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000462 Py_ssize_t i, n;
463 assert (PyAnySet_Check(so));
Raymond Hettingera580c472005-08-05 17:19:54 +0000464
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000465 n = so->mask + 1;
466 i = 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000467#endif
468
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000469 table = so->table;
470 assert(table != NULL);
471 table_is_malloced = table != so->smalltable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000472
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000473 /* This is delicate. During the process of clearing the set,
474 * decrefs can cause the set to mutate. To avoid fatal confusion
475 * (voice of experience), we have to make the set empty before
476 * clearing the slots, and never refer to anything via so->ref while
477 * clearing.
478 */
479 fill = so->fill;
480 if (table_is_malloced)
481 EMPTY_TO_MINSIZE(so);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000482
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000483 else if (fill > 0) {
484 /* It's a small table with something that needs to be cleared.
485 * Afraid the only safe way is to copy the set entries into
486 * another small table first.
487 */
488 memcpy(small_copy, table, sizeof(small_copy));
489 table = small_copy;
490 EMPTY_TO_MINSIZE(so);
491 }
492 /* else it's a small table that's already empty */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000493
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000494 /* Now we can finally clear things. If C had refcounts, we could
495 * assert that the refcount on table is 1 now, i.e. that this function
496 * has unique access to it, so decref side-effects can't alter it.
497 */
498 for (entry = table; fill > 0; ++entry) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000499#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000500 assert(i < n);
501 ++i;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000502#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000503 if (entry->key) {
504 --fill;
505 Py_DECREF(entry->key);
506 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000507#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000508 else
509 assert(entry->key == NULL);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000510#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000511 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000512
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000513 if (table_is_malloced)
514 PyMem_DEL(table);
515 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000516}
517
518/*
519 * Iterate over a set table. Use like so:
520 *
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000521 * Py_ssize_t pos;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000522 * setentry *entry;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000523 * pos = 0; # important! pos should not otherwise be changed by you
Raymond Hettingerc991db22005-08-11 07:58:45 +0000524 * while (set_next(yourset, &pos, &entry)) {
525 * Refer to borrowed reference in entry->key.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000526 * }
527 *
Raymond Hettingerc991db22005-08-11 07:58:45 +0000528 * CAUTION: In general, it isn't safe to use set_next in a loop that
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000529 * mutates the table.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000530 */
531static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000532set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000533{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000534 Py_ssize_t i;
535 Py_ssize_t mask;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200536 setentry *table;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000537
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000538 assert (PyAnySet_Check(so));
539 i = *pos_ptr;
540 assert(i >= 0);
541 table = so->table;
542 mask = so->mask;
543 while (i <= mask && (table[i].key == NULL || table[i].key == dummy))
544 i++;
545 *pos_ptr = i+1;
546 if (i > mask)
547 return 0;
548 assert(table[i].key != NULL);
549 *entry_ptr = &table[i];
550 return 1;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000551}
552
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000553static void
554set_dealloc(PySetObject *so)
555{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200556 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000557 Py_ssize_t fill = so->fill;
558 PyObject_GC_UnTrack(so);
559 Py_TRASHCAN_SAFE_BEGIN(so)
560 if (so->weakreflist != NULL)
561 PyObject_ClearWeakRefs((PyObject *) so);
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000562
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000563 for (entry = so->table; fill > 0; entry++) {
564 if (entry->key) {
565 --fill;
566 Py_DECREF(entry->key);
567 }
568 }
569 if (so->table != so->smalltable)
570 PyMem_DEL(so->table);
571 if (numfree < PySet_MAXFREELIST && PyAnySet_CheckExact(so))
572 free_list[numfree++] = so;
573 else
574 Py_TYPE(so)->tp_free(so);
575 Py_TRASHCAN_SAFE_END(so)
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000576}
577
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000578static PyObject *
579set_repr(PySetObject *so)
580{
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200581 PyObject *result=NULL, *keys, *listrepr, *tmp;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000582 int status = Py_ReprEnter((PyObject*)so);
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000583
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000584 if (status != 0) {
585 if (status < 0)
586 return NULL;
587 return PyUnicode_FromFormat("%s(...)", Py_TYPE(so)->tp_name);
588 }
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000589
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000590 /* shortcut for the empty set */
591 if (!so->used) {
592 Py_ReprLeave((PyObject*)so);
593 return PyUnicode_FromFormat("%s()", Py_TYPE(so)->tp_name);
594 }
Georg Brandlc4996ba2006-08-28 19:37:11 +0000595
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000596 keys = PySequence_List((PyObject *)so);
597 if (keys == NULL)
598 goto done;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000599
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200600 /* repr(keys)[1:-1] */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000601 listrepr = PyObject_Repr(keys);
602 Py_DECREF(keys);
603 if (listrepr == NULL)
604 goto done;
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200605 tmp = PyUnicode_Substring(listrepr, 1, PyUnicode_GET_LENGTH(listrepr)-1);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000606 Py_DECREF(listrepr);
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200607 if (tmp == NULL)
608 goto done;
609 listrepr = tmp;
Victor Stinnera1a807b2011-05-26 14:24:30 +0200610
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200611 if (Py_TYPE(so) != &PySet_Type)
612 result = PyUnicode_FromFormat("%s({%U})",
613 Py_TYPE(so)->tp_name,
614 listrepr);
615 else
616 result = PyUnicode_FromFormat("{%U}", listrepr);
617 Py_DECREF(listrepr);
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000618done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000619 Py_ReprLeave((PyObject*)so);
620 return result;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000621}
622
Martin v. Löwis18e16552006-02-15 17:27:45 +0000623static Py_ssize_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000624set_len(PyObject *so)
625{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000626 return ((PySetObject *)so)->used;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000627}
628
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000629static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000630set_merge(PySetObject *so, PyObject *otherset)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000631{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000632 PySetObject *other;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000633 PyObject *key;
Éric Araujobbcfc1f2011-03-23 03:43:22 +0100634 Py_hash_t hash;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200635 Py_ssize_t i;
636 setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000637
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000638 assert (PyAnySet_Check(so));
639 assert (PyAnySet_Check(otherset));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000640
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000641 other = (PySetObject*)otherset;
642 if (other == so || other->used == 0)
643 /* a.update(a) or a.update({}); nothing to do */
644 return 0;
645 /* Do one big resize at the start, rather than
646 * incrementally resizing as we insert new keys. Expect
647 * that there will be no (or few) overlapping keys.
648 */
649 if ((so->fill + other->used)*3 >= (so->mask+1)*2) {
650 if (set_table_resize(so, (so->used + other->used)*2) != 0)
651 return -1;
652 }
653 for (i = 0; i <= other->mask; i++) {
654 entry = &other->table[i];
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000655 key = entry->key;
Éric Araujo48049912011-03-23 02:08:07 +0100656 hash = entry->hash;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000657 if (key != NULL &&
658 key != dummy) {
659 Py_INCREF(key);
Éric Araujo48049912011-03-23 02:08:07 +0100660 if (set_insert_key(so, key, hash) == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000661 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000662 return -1;
663 }
664 }
665 }
666 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000667}
668
669static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000670set_contains_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000671{
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000672 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000673 setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000674
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000675 if (!PyUnicode_CheckExact(key) ||
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200676 (hash = ((PyASCIIObject *) key)->hash) == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000677 hash = PyObject_Hash(key);
678 if (hash == -1)
679 return -1;
680 }
681 entry = (so->lookup)(so, key, hash);
682 if (entry == NULL)
683 return -1;
684 key = entry->key;
685 return key != NULL && key != dummy;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000686}
687
Raymond Hettingerc991db22005-08-11 07:58:45 +0000688static int
689set_contains_entry(PySetObject *so, setentry *entry)
690{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000691 PyObject *key;
692 setentry *lu_entry;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000693
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000694 lu_entry = (so->lookup)(so, entry->key, entry->hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000695 if (lu_entry == NULL)
696 return -1;
697 key = lu_entry->key;
698 return key != NULL && key != dummy;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000699}
700
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000701static PyObject *
702set_pop(PySetObject *so)
703{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200704 Py_ssize_t i = 0;
705 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000706 PyObject *key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000707
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000708 assert (PyAnySet_Check(so));
709 if (so->used == 0) {
710 PyErr_SetString(PyExc_KeyError, "pop from an empty set");
711 return NULL;
712 }
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000713
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000714 /* Set entry to "the first" unused or dummy set entry. We abuse
715 * the hash field of slot 0 to hold a search finger:
716 * If slot 0 has a value, use slot 0.
717 * Else slot 0 is being used to hold a search finger,
718 * and we use its hash value as the first index to look.
719 */
720 entry = &so->table[0];
721 if (entry->key == NULL || entry->key == dummy) {
722 i = entry->hash;
723 /* The hash field may be a real hash value, or it may be a
724 * legit search finger, or it may be a once-legit search
725 * finger that's out of bounds now because it wrapped around
726 * or the table shrunk -- simply make sure it's in bounds now.
727 */
728 if (i > so->mask || i < 1)
729 i = 1; /* skip slot 0 */
730 while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
731 i++;
732 if (i > so->mask)
733 i = 1;
734 }
735 }
736 key = entry->key;
737 Py_INCREF(dummy);
738 entry->key = dummy;
739 so->used--;
740 so->table[0].hash = i + 1; /* next place to start */
741 return key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000742}
743
Benjamin Petersonf10a79a2008-10-11 00:49:57 +0000744PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\
745Raises KeyError if the set is empty.");
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000746
747static int
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000748set_traverse(PySetObject *so, visitproc visit, void *arg)
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000749{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000750 Py_ssize_t pos = 0;
751 setentry *entry;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000752
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000753 while (set_next(so, &pos, &entry))
754 Py_VISIT(entry->key);
755 return 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000756}
757
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000758static Py_hash_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000759frozenset_hash(PyObject *self)
760{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000761 PySetObject *so = (PySetObject *)self;
Gregory P. Smith27cbcd62012-12-10 18:15:46 -0800762 Py_uhash_t h, hash = 1927868237UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000763 setentry *entry;
764 Py_ssize_t pos = 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000765
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000766 if (so->hash != -1)
767 return so->hash;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000768
Mark Dickinson57e683e2011-09-24 18:18:40 +0100769 hash *= (Py_uhash_t)PySet_GET_SIZE(self) + 1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000770 while (set_next(so, &pos, &entry)) {
771 /* Work to increase the bit dispersion for closely spaced hash
772 values. The is important because some use cases have many
773 combinations of a small number of elements with nearby
774 hashes so that many distinct combinations collapse to only
775 a handful of distinct hash values. */
Antoine Pitroufbb1c612010-10-23 17:37:54 +0000776 h = entry->hash;
Gregory P. Smith27cbcd62012-12-10 18:15:46 -0800777 hash ^= (h ^ (h << 16) ^ 89869747UL) * 3644798167UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000778 }
Gregory P. Smithc2176e42012-12-10 18:32:53 -0800779 hash = hash * 69069U + 907133923UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000780 if (hash == -1)
Gregory P. Smith27cbcd62012-12-10 18:15:46 -0800781 hash = 590923713UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000782 so->hash = hash;
783 return hash;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000784}
785
Raymond Hettingera9d99362005-08-05 00:01:15 +0000786/***** Set iterator type ***********************************************/
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000787
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000788typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000789 PyObject_HEAD
790 PySetObject *si_set; /* Set to NULL when iterator is exhausted */
791 Py_ssize_t si_used;
792 Py_ssize_t si_pos;
793 Py_ssize_t len;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000794} setiterobject;
795
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000796static void
797setiter_dealloc(setiterobject *si)
798{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000799 Py_XDECREF(si->si_set);
800 PyObject_GC_Del(si);
Antoine Pitrou7ddda782009-01-01 15:35:33 +0000801}
802
803static int
804setiter_traverse(setiterobject *si, visitproc visit, void *arg)
805{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000806 Py_VISIT(si->si_set);
807 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000808}
809
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000810static PyObject *
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000811setiter_len(setiterobject *si)
812{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000813 Py_ssize_t len = 0;
814 if (si->si_set != NULL && si->si_used == si->si_set->used)
815 len = si->len;
Antoine Pitrou671b4d92010-08-17 17:55:07 +0000816 return PyLong_FromSsize_t(len);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000817}
818
Armin Rigof5b3e362006-02-11 21:32:43 +0000819PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000820
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000821static PyObject *setiter_iternext(setiterobject *si);
822
823static PyObject *
824setiter_reduce(setiterobject *si)
825{
826 PyObject *list;
827 setiterobject tmp;
828
829 list = PyList_New(0);
830 if (!list)
831 return NULL;
832
Ezio Melotti0e1af282012-09-28 16:43:40 +0300833 /* copy the iterator state */
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000834 tmp = *si;
835 Py_XINCREF(tmp.si_set);
Ezio Melotti0e1af282012-09-28 16:43:40 +0300836
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000837 /* iterate the temporary into a list */
838 for(;;) {
839 PyObject *element = setiter_iternext(&tmp);
840 if (element) {
841 if (PyList_Append(list, element)) {
842 Py_DECREF(element);
843 Py_DECREF(list);
844 Py_XDECREF(tmp.si_set);
845 return NULL;
846 }
847 Py_DECREF(element);
848 } else
849 break;
850 }
851 Py_XDECREF(tmp.si_set);
852 /* check for error */
853 if (tmp.si_set != NULL) {
854 /* we have an error */
855 Py_DECREF(list);
856 return NULL;
857 }
Antoine Pitroua7013882012-04-05 00:04:20 +0200858 return Py_BuildValue("N(N)", _PyObject_GetBuiltin("iter"), list);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000859}
860
861PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
862
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000863static PyMethodDef setiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000864 {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000865 {"__reduce__", (PyCFunction)setiter_reduce, METH_NOARGS, reduce_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000866 {NULL, NULL} /* sentinel */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000867};
868
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000869static PyObject *setiter_iternext(setiterobject *si)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000870{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000871 PyObject *key;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200872 Py_ssize_t i, mask;
873 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000874 PySetObject *so = si->si_set;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000875
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000876 if (so == NULL)
877 return NULL;
878 assert (PyAnySet_Check(so));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000879
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000880 if (si->si_used != so->used) {
881 PyErr_SetString(PyExc_RuntimeError,
882 "Set changed size during iteration");
883 si->si_used = -1; /* Make this state sticky */
884 return NULL;
885 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000886
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000887 i = si->si_pos;
888 assert(i>=0);
889 entry = so->table;
890 mask = so->mask;
891 while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
892 i++;
893 si->si_pos = i+1;
894 if (i > mask)
895 goto fail;
896 si->len--;
897 key = entry[i].key;
898 Py_INCREF(key);
899 return key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000900
901fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000902 Py_DECREF(so);
903 si->si_set = NULL;
904 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000905}
906
Christian Heimesa22e8bd2007-11-29 22:35:39 +0000907PyTypeObject PySetIter_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000908 PyVarObject_HEAD_INIT(&PyType_Type, 0)
909 "set_iterator", /* tp_name */
910 sizeof(setiterobject), /* tp_basicsize */
911 0, /* tp_itemsize */
912 /* methods */
913 (destructor)setiter_dealloc, /* tp_dealloc */
914 0, /* tp_print */
915 0, /* tp_getattr */
916 0, /* tp_setattr */
917 0, /* tp_reserved */
918 0, /* tp_repr */
919 0, /* tp_as_number */
920 0, /* tp_as_sequence */
921 0, /* tp_as_mapping */
922 0, /* tp_hash */
923 0, /* tp_call */
924 0, /* tp_str */
925 PyObject_GenericGetAttr, /* tp_getattro */
926 0, /* tp_setattro */
927 0, /* tp_as_buffer */
928 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
929 0, /* tp_doc */
930 (traverseproc)setiter_traverse, /* tp_traverse */
931 0, /* tp_clear */
932 0, /* tp_richcompare */
933 0, /* tp_weaklistoffset */
934 PyObject_SelfIter, /* tp_iter */
935 (iternextfunc)setiter_iternext, /* tp_iternext */
936 setiter_methods, /* tp_methods */
937 0,
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000938};
939
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000940static PyObject *
941set_iter(PySetObject *so)
942{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000943 setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type);
944 if (si == NULL)
945 return NULL;
946 Py_INCREF(so);
947 si->si_set = so;
948 si->si_used = so->used;
949 si->si_pos = 0;
950 si->len = so->used;
951 _PyObject_GC_TRACK(si);
952 return (PyObject *)si;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000953}
954
Raymond Hettingerd7946662005-08-01 21:39:29 +0000955static int
Raymond Hettingerd7946662005-08-01 21:39:29 +0000956set_update_internal(PySetObject *so, PyObject *other)
Raymond Hettingera690a992003-11-16 16:17:49 +0000957{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000958 PyObject *key, *it;
Raymond Hettingera690a992003-11-16 16:17:49 +0000959
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000960 if (PyAnySet_Check(other))
961 return set_merge(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +0000962
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000963 if (PyDict_CheckExact(other)) {
964 PyObject *value;
965 Py_ssize_t pos = 0;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000966 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000967 Py_ssize_t dictsize = PyDict_Size(other);
Thomas Wouterscf297e42007-02-23 15:07:44 +0000968
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000969 /* Do one big resize at the start, rather than
970 * incrementally resizing as we insert new keys. Expect
971 * that there will be no (or few) overlapping keys.
972 */
973 if (dictsize == -1)
974 return -1;
975 if ((so->fill + dictsize)*3 >= (so->mask+1)*2) {
976 if (set_table_resize(so, (so->used + dictsize)*2) != 0)
977 return -1;
978 }
979 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
980 setentry an_entry;
Thomas Wouterscf297e42007-02-23 15:07:44 +0000981
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000982 an_entry.hash = hash;
983 an_entry.key = key;
984 if (set_add_entry(so, &an_entry) == -1)
985 return -1;
986 }
987 return 0;
988 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000989
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000990 it = PyObject_GetIter(other);
991 if (it == NULL)
992 return -1;
Raymond Hettingera690a992003-11-16 16:17:49 +0000993
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000994 while ((key = PyIter_Next(it)) != NULL) {
995 if (set_add_key(so, key) == -1) {
996 Py_DECREF(it);
997 Py_DECREF(key);
998 return -1;
999 }
1000 Py_DECREF(key);
1001 }
1002 Py_DECREF(it);
1003 if (PyErr_Occurred())
1004 return -1;
1005 return 0;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001006}
1007
1008static PyObject *
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001009set_update(PySetObject *so, PyObject *args)
Raymond Hettingerd7946662005-08-01 21:39:29 +00001010{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001011 Py_ssize_t i;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001012
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001013 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1014 PyObject *other = PyTuple_GET_ITEM(args, i);
1015 if (set_update_internal(so, other) == -1)
1016 return NULL;
1017 }
1018 Py_RETURN_NONE;
Raymond Hettingera38123e2003-11-24 22:18:49 +00001019}
1020
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001021PyDoc_STRVAR(update_doc,
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001022"Update a set with the union of itself and others.");
Raymond Hettingera38123e2003-11-24 22:18:49 +00001023
1024static PyObject *
1025make_new_set(PyTypeObject *type, PyObject *iterable)
1026{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +02001027 PySetObject *so = NULL;
Raymond Hettingera38123e2003-11-24 22:18:49 +00001028
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001029 if (dummy == NULL) { /* Auto-initialize dummy */
1030 dummy = PyUnicode_FromString("<dummy key>");
1031 if (dummy == NULL)
1032 return NULL;
1033 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001034
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001035 /* create PySetObject structure */
1036 if (numfree &&
1037 (type == &PySet_Type || type == &PyFrozenSet_Type)) {
1038 so = free_list[--numfree];
1039 assert (so != NULL && PyAnySet_CheckExact(so));
1040 Py_TYPE(so) = type;
1041 _Py_NewReference((PyObject *)so);
1042 EMPTY_TO_MINSIZE(so);
1043 PyObject_GC_Track(so);
1044 } else {
1045 so = (PySetObject *)type->tp_alloc(type, 0);
1046 if (so == NULL)
1047 return NULL;
1048 /* tp_alloc has already zeroed the structure */
1049 assert(so->table == NULL && so->fill == 0 && so->used == 0);
1050 INIT_NONZERO_SET_SLOTS(so);
1051 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001052
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001053 so->lookup = set_lookkey_unicode;
1054 so->weakreflist = NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001055
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001056 if (iterable != NULL) {
1057 if (set_update_internal(so, iterable) == -1) {
1058 Py_DECREF(so);
1059 return NULL;
1060 }
1061 }
Raymond Hettingera38123e2003-11-24 22:18:49 +00001062
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001063 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001064}
1065
Raymond Hettinger7d99f092008-11-16 11:44:54 +00001066static PyObject *
1067make_new_set_basetype(PyTypeObject *type, PyObject *iterable)
1068{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001069 if (type != &PySet_Type && type != &PyFrozenSet_Type) {
1070 if (PyType_IsSubtype(type, &PySet_Type))
1071 type = &PySet_Type;
1072 else
1073 type = &PyFrozenSet_Type;
1074 }
1075 return make_new_set(type, iterable);
Raymond Hettinger7d99f092008-11-16 11:44:54 +00001076}
1077
Raymond Hettingerd7946662005-08-01 21:39:29 +00001078/* The empty frozenset is a singleton */
1079static PyObject *emptyfrozenset = NULL;
1080
Raymond Hettingera690a992003-11-16 16:17:49 +00001081static PyObject *
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001082frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
Raymond Hettingera690a992003-11-16 16:17:49 +00001083{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001084 PyObject *iterable = NULL, *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001085
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001086 if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds))
1087 return NULL;
Georg Brandl02c42872005-08-26 06:42:30 +00001088
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001089 if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
1090 return NULL;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001091
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001092 if (type != &PyFrozenSet_Type)
1093 return make_new_set(type, iterable);
Raymond Hettingerd7946662005-08-01 21:39:29 +00001094
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001095 if (iterable != NULL) {
1096 /* frozenset(f) is idempotent */
1097 if (PyFrozenSet_CheckExact(iterable)) {
1098 Py_INCREF(iterable);
1099 return iterable;
1100 }
1101 result = make_new_set(type, iterable);
1102 if (result == NULL || PySet_GET_SIZE(result))
1103 return result;
1104 Py_DECREF(result);
1105 }
1106 /* The empty frozenset is a singleton */
1107 if (emptyfrozenset == NULL)
1108 emptyfrozenset = make_new_set(type, NULL);
1109 Py_XINCREF(emptyfrozenset);
1110 return emptyfrozenset;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001111}
1112
Antoine Pitrou093ce9c2011-12-16 11:24:27 +01001113int
1114PySet_ClearFreeList(void)
Raymond Hettingerd7946662005-08-01 21:39:29 +00001115{
Antoine Pitrou093ce9c2011-12-16 11:24:27 +01001116 int freelist_size = numfree;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001117 PySetObject *so;
Raymond Hettingerbc841a12005-08-07 13:02:53 +00001118
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001119 while (numfree) {
1120 numfree--;
1121 so = free_list[numfree];
1122 PyObject_GC_Del(so);
1123 }
Antoine Pitrou093ce9c2011-12-16 11:24:27 +01001124 return freelist_size;
1125}
1126
1127void
1128PySet_Fini(void)
1129{
1130 PySet_ClearFreeList();
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001131 Py_CLEAR(dummy);
1132 Py_CLEAR(emptyfrozenset);
Raymond Hettingera690a992003-11-16 16:17:49 +00001133}
1134
David Malcolm49526f42012-06-22 14:55:41 -04001135/* Print summary info about the state of the optimized allocator */
1136void
1137_PySet_DebugMallocStats(FILE *out)
1138{
1139 _PyDebugAllocatorStats(out,
1140 "free PySetObject",
1141 numfree, sizeof(PySetObject));
1142}
1143
1144
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001145static PyObject *
1146set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1147{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001148 if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds))
1149 return NULL;
1150
1151 return make_new_set(type, NULL);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001152}
1153
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001154/* set_swap_bodies() switches the contents of any two sets by moving their
1155 internal data pointers and, if needed, copying the internal smalltables.
1156 Semantically equivalent to:
1157
1158 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1159
1160 The function always succeeds and it leaves both objects in a stable state.
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001161 Useful for creating temporary frozensets from sets for membership testing
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001162 in __contains__(), discard(), and remove(). Also useful for operations
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001163 that update in-place (by allowing an intermediate result to be swapped
Raymond Hettinger9dcb17c2005-07-31 13:09:28 +00001164 into one of the original inputs).
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001165*/
1166
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001167static void
1168set_swap_bodies(PySetObject *a, PySetObject *b)
Raymond Hettingera690a992003-11-16 16:17:49 +00001169{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001170 Py_ssize_t t;
1171 setentry *u;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001172 setentry *(*f)(PySetObject *so, PyObject *key, Py_ssize_t hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001173 setentry tab[PySet_MINSIZE];
Antoine Pitroufbb1c612010-10-23 17:37:54 +00001174 Py_hash_t h;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001175
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001176 t = a->fill; a->fill = b->fill; b->fill = t;
1177 t = a->used; a->used = b->used; b->used = t;
1178 t = a->mask; a->mask = b->mask; b->mask = t;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001179
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001180 u = a->table;
1181 if (a->table == a->smalltable)
1182 u = b->smalltable;
1183 a->table = b->table;
1184 if (b->table == b->smalltable)
1185 a->table = a->smalltable;
1186 b->table = u;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001187
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001188 f = a->lookup; a->lookup = b->lookup; b->lookup = f;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001189
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001190 if (a->table == a->smalltable || b->table == b->smalltable) {
1191 memcpy(tab, a->smalltable, sizeof(tab));
1192 memcpy(a->smalltable, b->smalltable, sizeof(tab));
1193 memcpy(b->smalltable, tab, sizeof(tab));
1194 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001195
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001196 if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type) &&
1197 PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) {
1198 h = a->hash; a->hash = b->hash; b->hash = h;
1199 } else {
1200 a->hash = -1;
1201 b->hash = -1;
1202 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001203}
1204
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001205static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001206set_copy(PySetObject *so)
1207{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001208 return make_new_set_basetype(Py_TYPE(so), (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001209}
1210
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001211static PyObject *
1212frozenset_copy(PySetObject *so)
1213{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001214 if (PyFrozenSet_CheckExact(so)) {
1215 Py_INCREF(so);
1216 return (PyObject *)so;
1217 }
1218 return set_copy(so);
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001219}
1220
Raymond Hettingera690a992003-11-16 16:17:49 +00001221PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
1222
1223static PyObject *
Raymond Hettingerc991db22005-08-11 07:58:45 +00001224set_clear(PySetObject *so)
1225{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001226 set_clear_internal(so);
1227 Py_RETURN_NONE;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001228}
1229
1230PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
1231
1232static PyObject *
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001233set_union(PySetObject *so, PyObject *args)
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001234{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001235 PySetObject *result;
1236 PyObject *other;
1237 Py_ssize_t i;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001238
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001239 result = (PySetObject *)set_copy(so);
1240 if (result == NULL)
1241 return NULL;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001242
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001243 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1244 other = PyTuple_GET_ITEM(args, i);
1245 if ((PyObject *)so == other)
1246 continue;
1247 if (set_update_internal(result, other) == -1) {
1248 Py_DECREF(result);
1249 return NULL;
1250 }
1251 }
1252 return (PyObject *)result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001253}
1254
1255PyDoc_STRVAR(union_doc,
1256 "Return the union of sets as a new set.\n\
1257\n\
1258(i.e. all elements that are in either set.)");
1259
1260static PyObject *
1261set_or(PySetObject *so, PyObject *other)
1262{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001263 PySetObject *result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001264
Brian Curtindfc80e32011-08-10 20:28:54 -05001265 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1266 Py_RETURN_NOTIMPLEMENTED;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001267
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001268 result = (PySetObject *)set_copy(so);
1269 if (result == NULL)
1270 return NULL;
1271 if ((PyObject *)so == other)
1272 return (PyObject *)result;
1273 if (set_update_internal(result, other) == -1) {
1274 Py_DECREF(result);
1275 return NULL;
1276 }
1277 return (PyObject *)result;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001278}
1279
Raymond Hettingera690a992003-11-16 16:17:49 +00001280static PyObject *
1281set_ior(PySetObject *so, PyObject *other)
1282{
Brian Curtindfc80e32011-08-10 20:28:54 -05001283 if (!PyAnySet_Check(other))
1284 Py_RETURN_NOTIMPLEMENTED;
1285
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001286 if (set_update_internal(so, other) == -1)
1287 return NULL;
1288 Py_INCREF(so);
1289 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001290}
1291
1292static PyObject *
1293set_intersection(PySetObject *so, PyObject *other)
1294{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001295 PySetObject *result;
1296 PyObject *key, *it, *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001297
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001298 if ((PyObject *)so == other)
1299 return set_copy(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001300
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001301 result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL);
1302 if (result == NULL)
1303 return NULL;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001304
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001305 if (PyAnySet_Check(other)) {
1306 Py_ssize_t pos = 0;
1307 setentry *entry;
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001308
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001309 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1310 tmp = (PyObject *)so;
1311 so = (PySetObject *)other;
1312 other = tmp;
1313 }
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001314
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001315 while (set_next((PySetObject *)other, &pos, &entry)) {
1316 int rv = set_contains_entry(so, entry);
1317 if (rv == -1) {
1318 Py_DECREF(result);
1319 return NULL;
1320 }
1321 if (rv) {
1322 if (set_add_entry(result, entry) == -1) {
1323 Py_DECREF(result);
1324 return NULL;
1325 }
1326 }
1327 }
1328 return (PyObject *)result;
1329 }
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001330
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001331 it = PyObject_GetIter(other);
1332 if (it == NULL) {
1333 Py_DECREF(result);
1334 return NULL;
1335 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001336
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001337 while ((key = PyIter_Next(it)) != NULL) {
1338 int rv;
1339 setentry entry;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001340 Py_hash_t hash = PyObject_Hash(key);
Thomas Wouters89f507f2006-12-13 04:49:30 +00001341
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001342 if (hash == -1) {
1343 Py_DECREF(it);
1344 Py_DECREF(result);
1345 Py_DECREF(key);
1346 return NULL;
1347 }
1348 entry.hash = hash;
1349 entry.key = key;
1350 rv = set_contains_entry(so, &entry);
1351 if (rv == -1) {
1352 Py_DECREF(it);
1353 Py_DECREF(result);
1354 Py_DECREF(key);
1355 return NULL;
1356 }
1357 if (rv) {
1358 if (set_add_entry(result, &entry) == -1) {
1359 Py_DECREF(it);
1360 Py_DECREF(result);
1361 Py_DECREF(key);
1362 return NULL;
1363 }
1364 }
1365 Py_DECREF(key);
1366 }
1367 Py_DECREF(it);
1368 if (PyErr_Occurred()) {
1369 Py_DECREF(result);
1370 return NULL;
1371 }
1372 return (PyObject *)result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001373}
1374
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001375static PyObject *
1376set_intersection_multi(PySetObject *so, PyObject *args)
1377{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001378 Py_ssize_t i;
1379 PyObject *result = (PyObject *)so;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001380
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001381 if (PyTuple_GET_SIZE(args) == 0)
1382 return set_copy(so);
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001383
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001384 Py_INCREF(so);
1385 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1386 PyObject *other = PyTuple_GET_ITEM(args, i);
1387 PyObject *newresult = set_intersection((PySetObject *)result, other);
1388 if (newresult == NULL) {
1389 Py_DECREF(result);
1390 return NULL;
1391 }
1392 Py_DECREF(result);
1393 result = newresult;
1394 }
1395 return result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001396}
1397
Raymond Hettingera690a992003-11-16 16:17:49 +00001398PyDoc_STRVAR(intersection_doc,
1399"Return the intersection of two sets as a new set.\n\
1400\n\
1401(i.e. all elements that are in both sets.)");
1402
1403static PyObject *
1404set_intersection_update(PySetObject *so, PyObject *other)
1405{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001406 PyObject *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001407
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001408 tmp = set_intersection(so, other);
1409 if (tmp == NULL)
1410 return NULL;
1411 set_swap_bodies(so, (PySetObject *)tmp);
1412 Py_DECREF(tmp);
1413 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001414}
1415
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001416static PyObject *
1417set_intersection_update_multi(PySetObject *so, PyObject *args)
1418{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001419 PyObject *tmp;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001420
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001421 tmp = set_intersection_multi(so, args);
1422 if (tmp == NULL)
1423 return NULL;
1424 set_swap_bodies(so, (PySetObject *)tmp);
1425 Py_DECREF(tmp);
1426 Py_RETURN_NONE;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001427}
1428
Raymond Hettingera690a992003-11-16 16:17:49 +00001429PyDoc_STRVAR(intersection_update_doc,
1430"Update a set with the intersection of itself and another.");
1431
1432static PyObject *
1433set_and(PySetObject *so, PyObject *other)
1434{
Brian Curtindfc80e32011-08-10 20:28:54 -05001435 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1436 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001437 return set_intersection(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001438}
1439
1440static PyObject *
1441set_iand(PySetObject *so, PyObject *other)
1442{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001443 PyObject *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001444
Brian Curtindfc80e32011-08-10 20:28:54 -05001445 if (!PyAnySet_Check(other))
1446 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001447 result = set_intersection_update(so, other);
1448 if (result == NULL)
1449 return NULL;
1450 Py_DECREF(result);
1451 Py_INCREF(so);
1452 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001453}
1454
Guido van Rossum58da9312007-11-10 23:39:45 +00001455static PyObject *
1456set_isdisjoint(PySetObject *so, PyObject *other)
1457{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001458 PyObject *key, *it, *tmp;
Guido van Rossum58da9312007-11-10 23:39:45 +00001459
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001460 if ((PyObject *)so == other) {
1461 if (PySet_GET_SIZE(so) == 0)
1462 Py_RETURN_TRUE;
1463 else
1464 Py_RETURN_FALSE;
1465 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001466
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001467 if (PyAnySet_CheckExact(other)) {
1468 Py_ssize_t pos = 0;
1469 setentry *entry;
Guido van Rossum58da9312007-11-10 23:39:45 +00001470
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001471 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1472 tmp = (PyObject *)so;
1473 so = (PySetObject *)other;
1474 other = tmp;
1475 }
1476 while (set_next((PySetObject *)other, &pos, &entry)) {
1477 int rv = set_contains_entry(so, entry);
1478 if (rv == -1)
1479 return NULL;
1480 if (rv)
1481 Py_RETURN_FALSE;
1482 }
1483 Py_RETURN_TRUE;
1484 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001485
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001486 it = PyObject_GetIter(other);
1487 if (it == NULL)
1488 return NULL;
Guido van Rossum58da9312007-11-10 23:39:45 +00001489
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001490 while ((key = PyIter_Next(it)) != NULL) {
1491 int rv;
1492 setentry entry;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001493 Py_hash_t hash = PyObject_Hash(key);
Guido van Rossum58da9312007-11-10 23:39:45 +00001494
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001495 if (hash == -1) {
1496 Py_DECREF(key);
1497 Py_DECREF(it);
1498 return NULL;
1499 }
1500 entry.hash = hash;
1501 entry.key = key;
1502 rv = set_contains_entry(so, &entry);
1503 Py_DECREF(key);
1504 if (rv == -1) {
1505 Py_DECREF(it);
1506 return NULL;
1507 }
1508 if (rv) {
1509 Py_DECREF(it);
1510 Py_RETURN_FALSE;
1511 }
1512 }
1513 Py_DECREF(it);
1514 if (PyErr_Occurred())
1515 return NULL;
1516 Py_RETURN_TRUE;
Guido van Rossum58da9312007-11-10 23:39:45 +00001517}
1518
1519PyDoc_STRVAR(isdisjoint_doc,
1520"Return True if two sets have a null intersection.");
1521
Neal Norwitz6576bd82005-11-13 18:41:28 +00001522static int
Raymond Hettingerc991db22005-08-11 07:58:45 +00001523set_difference_update_internal(PySetObject *so, PyObject *other)
1524{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001525 if ((PyObject *)so == other)
1526 return set_clear_internal(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001527
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001528 if (PyAnySet_Check(other)) {
1529 setentry *entry;
1530 Py_ssize_t pos = 0;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001531
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001532 while (set_next((PySetObject *)other, &pos, &entry))
1533 if (set_discard_entry(so, entry) == -1)
1534 return -1;
1535 } else {
1536 PyObject *key, *it;
1537 it = PyObject_GetIter(other);
1538 if (it == NULL)
1539 return -1;
1540
1541 while ((key = PyIter_Next(it)) != NULL) {
1542 if (set_discard_key(so, key) == -1) {
1543 Py_DECREF(it);
1544 Py_DECREF(key);
1545 return -1;
1546 }
1547 Py_DECREF(key);
1548 }
1549 Py_DECREF(it);
1550 if (PyErr_Occurred())
1551 return -1;
1552 }
1553 /* If more than 1/5 are dummies, then resize them away. */
1554 if ((so->fill - so->used) * 5 < so->mask)
1555 return 0;
1556 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001557}
1558
Raymond Hettingera690a992003-11-16 16:17:49 +00001559static PyObject *
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001560set_difference_update(PySetObject *so, PyObject *args)
Raymond Hettingera690a992003-11-16 16:17:49 +00001561{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001562 Py_ssize_t i;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001563
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001564 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1565 PyObject *other = PyTuple_GET_ITEM(args, i);
1566 if (set_difference_update_internal(so, other) == -1)
1567 return NULL;
1568 }
1569 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001570}
1571
1572PyDoc_STRVAR(difference_update_doc,
1573"Remove all elements of another set from this set.");
1574
1575static PyObject *
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001576set_copy_and_difference(PySetObject *so, PyObject *other)
1577{
1578 PyObject *result;
1579
1580 result = set_copy(so);
1581 if (result == NULL)
1582 return NULL;
1583 if (set_difference_update_internal((PySetObject *) result, other) != -1)
1584 return result;
1585 Py_DECREF(result);
1586 return NULL;
1587}
1588
1589static PyObject *
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001590set_difference(PySetObject *so, PyObject *other)
1591{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001592 PyObject *result;
1593 setentry *entry;
1594 Py_ssize_t pos = 0;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001595
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001596 if (!PyAnySet_Check(other) && !PyDict_CheckExact(other)) {
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001597 return set_copy_and_difference(so, other);
1598 }
1599
1600 /* If len(so) much more than len(other), it's more efficient to simply copy
1601 * so and then iterate other looking for common elements. */
1602 if ((PySet_GET_SIZE(so) >> 2) > PyObject_Size(other)) {
1603 return set_copy_and_difference(so, other);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001604 }
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001605
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001606 result = make_new_set_basetype(Py_TYPE(so), NULL);
1607 if (result == NULL)
1608 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001609
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001610 if (PyDict_CheckExact(other)) {
1611 while (set_next(so, &pos, &entry)) {
1612 setentry entrycopy;
1613 entrycopy.hash = entry->hash;
1614 entrycopy.key = entry->key;
Antoine Pitroufbb1c612010-10-23 17:37:54 +00001615 if (!_PyDict_Contains(other, entry->key, entry->hash)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001616 if (set_add_entry((PySetObject *)result, &entrycopy) == -1) {
1617 Py_DECREF(result);
1618 return NULL;
1619 }
1620 }
1621 }
1622 return result;
1623 }
1624
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001625 /* Iterate over so, checking for common elements in other. */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001626 while (set_next(so, &pos, &entry)) {
1627 int rv = set_contains_entry((PySetObject *)other, entry);
1628 if (rv == -1) {
1629 Py_DECREF(result);
1630 return NULL;
1631 }
1632 if (!rv) {
1633 if (set_add_entry((PySetObject *)result, entry) == -1) {
1634 Py_DECREF(result);
1635 return NULL;
1636 }
1637 }
1638 }
1639 return result;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001640}
1641
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001642static PyObject *
1643set_difference_multi(PySetObject *so, PyObject *args)
1644{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001645 Py_ssize_t i;
1646 PyObject *result, *other;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001647
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001648 if (PyTuple_GET_SIZE(args) == 0)
1649 return set_copy(so);
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001650
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001651 other = PyTuple_GET_ITEM(args, 0);
1652 result = set_difference(so, other);
1653 if (result == NULL)
1654 return NULL;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001655
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001656 for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) {
1657 other = PyTuple_GET_ITEM(args, i);
1658 if (set_difference_update_internal((PySetObject *)result, other) == -1) {
1659 Py_DECREF(result);
1660 return NULL;
1661 }
1662 }
1663 return result;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001664}
1665
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001666PyDoc_STRVAR(difference_doc,
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001667"Return the difference of two or more sets as a new set.\n\
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001668\n\
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001669(i.e. all elements that are in this set but not the others.)");
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001670static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001671set_sub(PySetObject *so, PyObject *other)
1672{
Brian Curtindfc80e32011-08-10 20:28:54 -05001673 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1674 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001675 return set_difference(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001676}
1677
1678static PyObject *
1679set_isub(PySetObject *so, PyObject *other)
1680{
Brian Curtindfc80e32011-08-10 20:28:54 -05001681 if (!PyAnySet_Check(other))
1682 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001683 if (set_difference_update_internal(so, other) == -1)
1684 return NULL;
1685 Py_INCREF(so);
1686 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001687}
1688
1689static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001690set_symmetric_difference_update(PySetObject *so, PyObject *other)
1691{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001692 PySetObject *otherset;
1693 PyObject *key;
1694 Py_ssize_t pos = 0;
1695 setentry *entry;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001696
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001697 if ((PyObject *)so == other)
1698 return set_clear(so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001699
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001700 if (PyDict_CheckExact(other)) {
1701 PyObject *value;
1702 int rv;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001703 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001704 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
1705 setentry an_entry;
Thomas Wouters89f507f2006-12-13 04:49:30 +00001706
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001707 Py_INCREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001708 an_entry.hash = hash;
1709 an_entry.key = key;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001710
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001711 rv = set_discard_entry(so, &an_entry);
Georg Brandl2d444492010-09-03 10:52:55 +00001712 if (rv == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001713 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001714 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001715 }
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001716 if (rv == DISCARD_NOTFOUND) {
1717 if (set_add_entry(so, &an_entry) == -1) {
1718 Py_DECREF(key);
1719 return NULL;
1720 }
1721 }
Georg Brandl2d444492010-09-03 10:52:55 +00001722 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001723 }
1724 Py_RETURN_NONE;
1725 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001726
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001727 if (PyAnySet_Check(other)) {
1728 Py_INCREF(other);
1729 otherset = (PySetObject *)other;
1730 } else {
1731 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1732 if (otherset == NULL)
1733 return NULL;
1734 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001735
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001736 while (set_next(otherset, &pos, &entry)) {
1737 int rv = set_discard_entry(so, entry);
1738 if (rv == -1) {
1739 Py_DECREF(otherset);
1740 return NULL;
1741 }
1742 if (rv == DISCARD_NOTFOUND) {
1743 if (set_add_entry(so, entry) == -1) {
1744 Py_DECREF(otherset);
1745 return NULL;
1746 }
1747 }
1748 }
1749 Py_DECREF(otherset);
1750 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001751}
1752
1753PyDoc_STRVAR(symmetric_difference_update_doc,
1754"Update a set with the symmetric difference of itself and another.");
1755
1756static PyObject *
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001757set_symmetric_difference(PySetObject *so, PyObject *other)
1758{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001759 PyObject *rv;
1760 PySetObject *otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001761
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001762 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1763 if (otherset == NULL)
1764 return NULL;
1765 rv = set_symmetric_difference_update(otherset, (PyObject *)so);
1766 if (rv == NULL)
1767 return NULL;
1768 Py_DECREF(rv);
1769 return (PyObject *)otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001770}
1771
1772PyDoc_STRVAR(symmetric_difference_doc,
1773"Return the symmetric difference of two sets as a new set.\n\
1774\n\
1775(i.e. all elements that are in exactly one of the sets.)");
1776
1777static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001778set_xor(PySetObject *so, PyObject *other)
1779{
Brian Curtindfc80e32011-08-10 20:28:54 -05001780 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1781 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001782 return set_symmetric_difference(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001783}
1784
1785static PyObject *
1786set_ixor(PySetObject *so, PyObject *other)
1787{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001788 PyObject *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001789
Brian Curtindfc80e32011-08-10 20:28:54 -05001790 if (!PyAnySet_Check(other))
1791 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001792 result = set_symmetric_difference_update(so, other);
1793 if (result == NULL)
1794 return NULL;
1795 Py_DECREF(result);
1796 Py_INCREF(so);
1797 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001798}
1799
1800static PyObject *
1801set_issubset(PySetObject *so, PyObject *other)
1802{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001803 setentry *entry;
1804 Py_ssize_t pos = 0;
Raymond Hettingera690a992003-11-16 16:17:49 +00001805
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001806 if (!PyAnySet_Check(other)) {
1807 PyObject *tmp, *result;
1808 tmp = make_new_set(&PySet_Type, other);
1809 if (tmp == NULL)
1810 return NULL;
1811 result = set_issubset(so, tmp);
1812 Py_DECREF(tmp);
1813 return result;
1814 }
1815 if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
1816 Py_RETURN_FALSE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001817
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001818 while (set_next(so, &pos, &entry)) {
1819 int rv = set_contains_entry((PySetObject *)other, entry);
1820 if (rv == -1)
1821 return NULL;
1822 if (!rv)
1823 Py_RETURN_FALSE;
1824 }
1825 Py_RETURN_TRUE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001826}
1827
1828PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
1829
1830static PyObject *
1831set_issuperset(PySetObject *so, PyObject *other)
1832{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001833 PyObject *tmp, *result;
Raymond Hettinger3fbec702003-11-21 07:56:36 +00001834
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001835 if (!PyAnySet_Check(other)) {
1836 tmp = make_new_set(&PySet_Type, other);
1837 if (tmp == NULL)
1838 return NULL;
1839 result = set_issuperset(so, tmp);
1840 Py_DECREF(tmp);
1841 return result;
1842 }
1843 return set_issubset((PySetObject *)other, (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001844}
1845
1846PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
1847
Raymond Hettingera690a992003-11-16 16:17:49 +00001848static PyObject *
1849set_richcompare(PySetObject *v, PyObject *w, int op)
1850{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001851 PyObject *r1, *r2;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001852
Brian Curtindfc80e32011-08-10 20:28:54 -05001853 if(!PyAnySet_Check(w))
1854 Py_RETURN_NOTIMPLEMENTED;
1855
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001856 switch (op) {
1857 case Py_EQ:
1858 if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
1859 Py_RETURN_FALSE;
1860 if (v->hash != -1 &&
1861 ((PySetObject *)w)->hash != -1 &&
1862 v->hash != ((PySetObject *)w)->hash)
1863 Py_RETURN_FALSE;
1864 return set_issubset(v, w);
1865 case Py_NE:
1866 r1 = set_richcompare(v, w, Py_EQ);
1867 if (r1 == NULL)
1868 return NULL;
1869 r2 = PyBool_FromLong(PyObject_Not(r1));
1870 Py_DECREF(r1);
1871 return r2;
1872 case Py_LE:
1873 return set_issubset(v, w);
1874 case Py_GE:
1875 return set_issuperset(v, w);
1876 case Py_LT:
1877 if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))
1878 Py_RETURN_FALSE;
1879 return set_issubset(v, w);
1880 case Py_GT:
1881 if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
1882 Py_RETURN_FALSE;
1883 return set_issuperset(v, w);
1884 }
Brian Curtindfc80e32011-08-10 20:28:54 -05001885 Py_RETURN_NOTIMPLEMENTED;
Raymond Hettingera690a992003-11-16 16:17:49 +00001886}
1887
Raymond Hettingera690a992003-11-16 16:17:49 +00001888static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001889set_add(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001890{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001891 if (set_add_key(so, key) == -1)
1892 return NULL;
1893 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001894}
1895
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001896PyDoc_STRVAR(add_doc,
Raymond Hettingera690a992003-11-16 16:17:49 +00001897"Add an element to a set.\n\
1898\n\
1899This has no effect if the element is already present.");
1900
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001901static int
1902set_contains(PySetObject *so, PyObject *key)
1903{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001904 PyObject *tmpkey;
1905 int rv;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001906
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001907 rv = set_contains_key(so, key);
1908 if (rv == -1) {
1909 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1910 return -1;
1911 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001912 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001913 if (tmpkey == NULL)
1914 return -1;
Petri Lehtinen5acc27e2011-10-30 13:56:41 +02001915 rv = set_contains_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001916 Py_DECREF(tmpkey);
1917 }
1918 return rv;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001919}
1920
1921static PyObject *
1922set_direct_contains(PySetObject *so, PyObject *key)
1923{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001924 long result;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001925
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001926 result = set_contains(so, key);
1927 if (result == -1)
1928 return NULL;
1929 return PyBool_FromLong(result);
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001930}
1931
1932PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
1933
Raymond Hettingera690a992003-11-16 16:17:49 +00001934static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001935set_remove(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001936{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001937 PyObject *tmpkey;
1938 int rv;
Raymond Hettingerbfd334a2003-11-22 03:55:23 +00001939
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001940 rv = set_discard_key(so, key);
1941 if (rv == -1) {
1942 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1943 return NULL;
1944 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001945 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001946 if (tmpkey == NULL)
1947 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001948 rv = set_discard_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001949 Py_DECREF(tmpkey);
1950 if (rv == -1)
1951 return NULL;
1952 }
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00001953
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001954 if (rv == DISCARD_NOTFOUND) {
1955 set_key_error(key);
1956 return NULL;
1957 }
1958 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001959}
1960
1961PyDoc_STRVAR(remove_doc,
1962"Remove an element from a set; it must be a member.\n\
1963\n\
1964If the element is not a member, raise a KeyError.");
1965
1966static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001967set_discard(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001968{
Benjamin Peterson2b50a012011-10-30 14:24:44 -04001969 PyObject *tmpkey;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001970 int rv;
Raymond Hettinger0deab622003-12-13 18:53:18 +00001971
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001972 rv = set_discard_key(so, key);
1973 if (rv == -1) {
1974 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1975 return NULL;
1976 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001977 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001978 if (tmpkey == NULL)
1979 return NULL;
Petri Lehtinene0aa8032011-10-30 14:31:27 +02001980 rv = set_discard_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001981 Py_DECREF(tmpkey);
Petri Lehtinene0aa8032011-10-30 14:31:27 +02001982 if (rv == -1)
1983 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001984 }
1985 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001986}
1987
1988PyDoc_STRVAR(discard_doc,
1989"Remove an element from a set if it is a member.\n\
1990\n\
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001991If the element is not a member, do nothing.");
Raymond Hettingera690a992003-11-16 16:17:49 +00001992
1993static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001994set_reduce(PySetObject *so)
1995{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001996 PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;
Martin v. Löwisbd928fe2011-10-14 10:20:37 +02001997 _Py_IDENTIFIER(__dict__);
Raymond Hettingera690a992003-11-16 16:17:49 +00001998
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001999 keys = PySequence_List((PyObject *)so);
2000 if (keys == NULL)
2001 goto done;
2002 args = PyTuple_Pack(1, keys);
2003 if (args == NULL)
2004 goto done;
Martin v. Löwis1ee1b6f2011-10-10 18:11:30 +02002005 dict = _PyObject_GetAttrId((PyObject *)so, &PyId___dict__);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002006 if (dict == NULL) {
2007 PyErr_Clear();
2008 dict = Py_None;
2009 Py_INCREF(dict);
2010 }
2011 result = PyTuple_Pack(3, Py_TYPE(so), args, dict);
Raymond Hettingera690a992003-11-16 16:17:49 +00002012done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002013 Py_XDECREF(args);
2014 Py_XDECREF(keys);
2015 Py_XDECREF(dict);
2016 return result;
Raymond Hettingera690a992003-11-16 16:17:49 +00002017}
2018
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00002019static PyObject *
2020set_sizeof(PySetObject *so)
2021{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002022 Py_ssize_t res;
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00002023
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002024 res = sizeof(PySetObject);
2025 if (so->table != so->smalltable)
2026 res = res + (so->mask + 1) * sizeof(setentry);
2027 return PyLong_FromSsize_t(res);
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00002028}
2029
2030PyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes");
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00002031static int
2032set_init(PySetObject *self, PyObject *args, PyObject *kwds)
2033{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002034 PyObject *iterable = NULL;
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00002035
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002036 if (!PyAnySet_Check(self))
2037 return -1;
2038 if (PySet_Check(self) && !_PyArg_NoKeywords("set()", kwds))
2039 return -1;
2040 if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable))
2041 return -1;
2042 set_clear_internal(self);
2043 self->hash = -1;
2044 if (iterable == NULL)
2045 return 0;
2046 return set_update_internal(self, iterable);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00002047}
2048
Raymond Hettingera690a992003-11-16 16:17:49 +00002049static PySequenceMethods set_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002050 set_len, /* sq_length */
2051 0, /* sq_concat */
2052 0, /* sq_repeat */
2053 0, /* sq_item */
2054 0, /* sq_slice */
2055 0, /* sq_ass_item */
2056 0, /* sq_ass_slice */
2057 (objobjproc)set_contains, /* sq_contains */
Raymond Hettingera690a992003-11-16 16:17:49 +00002058};
2059
2060/* set object ********************************************************/
2061
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002062#ifdef Py_DEBUG
2063static PyObject *test_c_api(PySetObject *so);
2064
2065PyDoc_STRVAR(test_c_api_doc, "Exercises C API. Returns True.\n\
2066All is well if assertions don't fail.");
2067#endif
2068
Raymond Hettingera690a992003-11-16 16:17:49 +00002069static PyMethodDef set_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002070 {"add", (PyCFunction)set_add, METH_O,
2071 add_doc},
2072 {"clear", (PyCFunction)set_clear, METH_NOARGS,
2073 clear_doc},
2074 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2075 contains_doc},
2076 {"copy", (PyCFunction)set_copy, METH_NOARGS,
2077 copy_doc},
2078 {"discard", (PyCFunction)set_discard, METH_O,
2079 discard_doc},
2080 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2081 difference_doc},
2082 {"difference_update", (PyCFunction)set_difference_update, METH_VARARGS,
2083 difference_update_doc},
2084 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2085 intersection_doc},
2086 {"intersection_update",(PyCFunction)set_intersection_update_multi, METH_VARARGS,
2087 intersection_update_doc},
2088 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2089 isdisjoint_doc},
2090 {"issubset", (PyCFunction)set_issubset, METH_O,
2091 issubset_doc},
2092 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2093 issuperset_doc},
2094 {"pop", (PyCFunction)set_pop, METH_NOARGS,
2095 pop_doc},
2096 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2097 reduce_doc},
2098 {"remove", (PyCFunction)set_remove, METH_O,
2099 remove_doc},
2100 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2101 sizeof_doc},
2102 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2103 symmetric_difference_doc},
2104 {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O,
2105 symmetric_difference_update_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002106#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002107 {"test_c_api", (PyCFunction)test_c_api, METH_NOARGS,
2108 test_c_api_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002109#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002110 {"union", (PyCFunction)set_union, METH_VARARGS,
2111 union_doc},
2112 {"update", (PyCFunction)set_update, METH_VARARGS,
2113 update_doc},
2114 {NULL, NULL} /* sentinel */
Raymond Hettingera690a992003-11-16 16:17:49 +00002115};
2116
2117static PyNumberMethods set_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002118 0, /*nb_add*/
2119 (binaryfunc)set_sub, /*nb_subtract*/
2120 0, /*nb_multiply*/
2121 0, /*nb_remainder*/
2122 0, /*nb_divmod*/
2123 0, /*nb_power*/
2124 0, /*nb_negative*/
2125 0, /*nb_positive*/
2126 0, /*nb_absolute*/
2127 0, /*nb_bool*/
2128 0, /*nb_invert*/
2129 0, /*nb_lshift*/
2130 0, /*nb_rshift*/
2131 (binaryfunc)set_and, /*nb_and*/
2132 (binaryfunc)set_xor, /*nb_xor*/
2133 (binaryfunc)set_or, /*nb_or*/
2134 0, /*nb_int*/
2135 0, /*nb_reserved*/
2136 0, /*nb_float*/
2137 0, /*nb_inplace_add*/
2138 (binaryfunc)set_isub, /*nb_inplace_subtract*/
2139 0, /*nb_inplace_multiply*/
2140 0, /*nb_inplace_remainder*/
2141 0, /*nb_inplace_power*/
2142 0, /*nb_inplace_lshift*/
2143 0, /*nb_inplace_rshift*/
2144 (binaryfunc)set_iand, /*nb_inplace_and*/
2145 (binaryfunc)set_ixor, /*nb_inplace_xor*/
2146 (binaryfunc)set_ior, /*nb_inplace_or*/
Raymond Hettingera690a992003-11-16 16:17:49 +00002147};
2148
2149PyDoc_STRVAR(set_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002150"set() -> new empty set object\n\
2151set(iterable) -> new set object\n\
Raymond Hettingera690a992003-11-16 16:17:49 +00002152\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002153Build an unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00002154
2155PyTypeObject PySet_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002156 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2157 "set", /* tp_name */
2158 sizeof(PySetObject), /* tp_basicsize */
2159 0, /* tp_itemsize */
2160 /* methods */
2161 (destructor)set_dealloc, /* tp_dealloc */
2162 0, /* tp_print */
2163 0, /* tp_getattr */
2164 0, /* tp_setattr */
2165 0, /* tp_reserved */
2166 (reprfunc)set_repr, /* tp_repr */
2167 &set_as_number, /* tp_as_number */
2168 &set_as_sequence, /* tp_as_sequence */
2169 0, /* tp_as_mapping */
Georg Brandl00da4e02010-10-18 07:32:48 +00002170 PyObject_HashNotImplemented, /* tp_hash */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002171 0, /* tp_call */
2172 0, /* tp_str */
2173 PyObject_GenericGetAttr, /* tp_getattro */
2174 0, /* tp_setattro */
2175 0, /* tp_as_buffer */
2176 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2177 Py_TPFLAGS_BASETYPE, /* tp_flags */
2178 set_doc, /* tp_doc */
2179 (traverseproc)set_traverse, /* tp_traverse */
2180 (inquiry)set_clear_internal, /* tp_clear */
2181 (richcmpfunc)set_richcompare, /* tp_richcompare */
Georg Brandl00da4e02010-10-18 07:32:48 +00002182 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2183 (getiterfunc)set_iter, /* tp_iter */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002184 0, /* tp_iternext */
2185 set_methods, /* tp_methods */
2186 0, /* tp_members */
2187 0, /* tp_getset */
2188 0, /* tp_base */
2189 0, /* tp_dict */
2190 0, /* tp_descr_get */
2191 0, /* tp_descr_set */
2192 0, /* tp_dictoffset */
2193 (initproc)set_init, /* tp_init */
2194 PyType_GenericAlloc, /* tp_alloc */
2195 set_new, /* tp_new */
2196 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002197};
2198
2199/* frozenset object ********************************************************/
2200
2201
2202static PyMethodDef frozenset_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002203 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2204 contains_doc},
2205 {"copy", (PyCFunction)frozenset_copy, METH_NOARGS,
2206 copy_doc},
2207 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2208 difference_doc},
2209 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2210 intersection_doc},
2211 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2212 isdisjoint_doc},
2213 {"issubset", (PyCFunction)set_issubset, METH_O,
2214 issubset_doc},
2215 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2216 issuperset_doc},
2217 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2218 reduce_doc},
2219 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2220 sizeof_doc},
2221 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2222 symmetric_difference_doc},
2223 {"union", (PyCFunction)set_union, METH_VARARGS,
2224 union_doc},
2225 {NULL, NULL} /* sentinel */
Raymond Hettingera690a992003-11-16 16:17:49 +00002226};
2227
2228static PyNumberMethods frozenset_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002229 0, /*nb_add*/
2230 (binaryfunc)set_sub, /*nb_subtract*/
2231 0, /*nb_multiply*/
2232 0, /*nb_remainder*/
2233 0, /*nb_divmod*/
2234 0, /*nb_power*/
2235 0, /*nb_negative*/
2236 0, /*nb_positive*/
2237 0, /*nb_absolute*/
2238 0, /*nb_bool*/
2239 0, /*nb_invert*/
2240 0, /*nb_lshift*/
2241 0, /*nb_rshift*/
2242 (binaryfunc)set_and, /*nb_and*/
2243 (binaryfunc)set_xor, /*nb_xor*/
2244 (binaryfunc)set_or, /*nb_or*/
Raymond Hettingera690a992003-11-16 16:17:49 +00002245};
2246
2247PyDoc_STRVAR(frozenset_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002248"frozenset() -> empty frozenset object\n\
2249frozenset(iterable) -> frozenset object\n\
Raymond Hettingera690a992003-11-16 16:17:49 +00002250\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002251Build an immutable unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00002252
2253PyTypeObject PyFrozenSet_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002254 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2255 "frozenset", /* tp_name */
2256 sizeof(PySetObject), /* tp_basicsize */
2257 0, /* tp_itemsize */
2258 /* methods */
2259 (destructor)set_dealloc, /* tp_dealloc */
2260 0, /* tp_print */
2261 0, /* tp_getattr */
2262 0, /* tp_setattr */
2263 0, /* tp_reserved */
2264 (reprfunc)set_repr, /* tp_repr */
2265 &frozenset_as_number, /* tp_as_number */
2266 &set_as_sequence, /* tp_as_sequence */
2267 0, /* tp_as_mapping */
2268 frozenset_hash, /* tp_hash */
2269 0, /* tp_call */
2270 0, /* tp_str */
2271 PyObject_GenericGetAttr, /* tp_getattro */
2272 0, /* tp_setattro */
2273 0, /* tp_as_buffer */
2274 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2275 Py_TPFLAGS_BASETYPE, /* tp_flags */
2276 frozenset_doc, /* tp_doc */
2277 (traverseproc)set_traverse, /* tp_traverse */
2278 (inquiry)set_clear_internal, /* tp_clear */
2279 (richcmpfunc)set_richcompare, /* tp_richcompare */
2280 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2281 (getiterfunc)set_iter, /* tp_iter */
2282 0, /* tp_iternext */
2283 frozenset_methods, /* tp_methods */
2284 0, /* tp_members */
2285 0, /* tp_getset */
2286 0, /* tp_base */
2287 0, /* tp_dict */
2288 0, /* tp_descr_get */
2289 0, /* tp_descr_set */
2290 0, /* tp_dictoffset */
2291 0, /* tp_init */
2292 PyType_GenericAlloc, /* tp_alloc */
2293 frozenset_new, /* tp_new */
2294 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002295};
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002296
2297
2298/***** C API functions *************************************************/
2299
2300PyObject *
2301PySet_New(PyObject *iterable)
2302{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002303 return make_new_set(&PySet_Type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002304}
2305
2306PyObject *
2307PyFrozenSet_New(PyObject *iterable)
2308{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002309 return make_new_set(&PyFrozenSet_Type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002310}
2311
Neal Norwitz8c49c822006-03-04 18:41:19 +00002312Py_ssize_t
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002313PySet_Size(PyObject *anyset)
2314{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002315 if (!PyAnySet_Check(anyset)) {
2316 PyErr_BadInternalCall();
2317 return -1;
2318 }
2319 return PySet_GET_SIZE(anyset);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002320}
2321
2322int
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002323PySet_Clear(PyObject *set)
2324{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002325 if (!PySet_Check(set)) {
2326 PyErr_BadInternalCall();
2327 return -1;
2328 }
2329 return set_clear_internal((PySetObject *)set);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002330}
2331
2332int
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002333PySet_Contains(PyObject *anyset, PyObject *key)
2334{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002335 if (!PyAnySet_Check(anyset)) {
2336 PyErr_BadInternalCall();
2337 return -1;
2338 }
2339 return set_contains_key((PySetObject *)anyset, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002340}
2341
2342int
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002343PySet_Discard(PyObject *set, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002344{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002345 if (!PySet_Check(set)) {
2346 PyErr_BadInternalCall();
2347 return -1;
2348 }
2349 return set_discard_key((PySetObject *)set, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002350}
2351
2352int
Christian Heimesfd66e512008-01-29 12:18:50 +00002353PySet_Add(PyObject *anyset, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002354{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002355 if (!PySet_Check(anyset) &&
2356 (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
2357 PyErr_BadInternalCall();
2358 return -1;
2359 }
2360 return set_add_key((PySetObject *)anyset, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002361}
2362
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002363int
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002364_PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash)
Guido van Rossumd8faa362007-04-27 19:54:29 +00002365{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002366 setentry *entry;
Guido van Rossumd8faa362007-04-27 19:54:29 +00002367
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002368 if (!PyAnySet_Check(set)) {
2369 PyErr_BadInternalCall();
2370 return -1;
2371 }
2372 if (set_next((PySetObject *)set, pos, &entry) == 0)
2373 return 0;
2374 *key = entry->key;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002375 *hash = entry->hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002376 return 1;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002377}
2378
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002379PyObject *
2380PySet_Pop(PyObject *set)
2381{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002382 if (!PySet_Check(set)) {
2383 PyErr_BadInternalCall();
2384 return NULL;
2385 }
2386 return set_pop((PySetObject *)set);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002387}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002388
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002389int
2390_PySet_Update(PyObject *set, PyObject *iterable)
2391{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002392 if (!PySet_Check(set)) {
2393 PyErr_BadInternalCall();
2394 return -1;
2395 }
2396 return set_update_internal((PySetObject *)set, iterable);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002397}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002398
2399#ifdef Py_DEBUG
2400
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002401/* Test code to be called with any three element set.
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002402 Returns True and original set is restored. */
2403
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002404#define assertRaises(call_return_value, exception) \
2405 do { \
2406 assert(call_return_value); \
2407 assert(PyErr_ExceptionMatches(exception)); \
2408 PyErr_Clear(); \
2409 } while(0)
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002410
2411static PyObject *
2412test_c_api(PySetObject *so)
2413{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002414 Py_ssize_t count;
2415 char *s;
2416 Py_ssize_t i;
2417 PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x;
2418 PyObject *ob = (PyObject *)so;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002419 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002420 PyObject *str;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002421
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002422 /* Verify preconditions */
2423 assert(PyAnySet_Check(ob));
2424 assert(PyAnySet_CheckExact(ob));
2425 assert(!PyFrozenSet_CheckExact(ob));
Victor Stinner08b36bd2010-03-13 00:19:17 +00002426
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002427 /* so.clear(); so |= set("abc"); */
2428 str = PyUnicode_FromString("abc");
2429 if (str == NULL)
2430 return NULL;
2431 set_clear_internal(so);
2432 if (set_update_internal(so, str) == -1) {
2433 Py_DECREF(str);
2434 return NULL;
2435 }
2436 Py_DECREF(str);
Victor Stinner08b36bd2010-03-13 00:19:17 +00002437
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002438 /* Exercise type/size checks */
2439 assert(PySet_Size(ob) == 3);
2440 assert(PySet_GET_SIZE(ob) == 3);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002441
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002442 /* Raise TypeError for non-iterable constructor arguments */
2443 assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
2444 assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002445
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002446 /* Raise TypeError for unhashable key */
2447 dup = PySet_New(ob);
2448 assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
2449 assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
2450 assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002451
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002452 /* Exercise successful pop, contains, add, and discard */
2453 elem = PySet_Pop(ob);
2454 assert(PySet_Contains(ob, elem) == 0);
2455 assert(PySet_GET_SIZE(ob) == 2);
2456 assert(PySet_Add(ob, elem) == 0);
2457 assert(PySet_Contains(ob, elem) == 1);
2458 assert(PySet_GET_SIZE(ob) == 3);
2459 assert(PySet_Discard(ob, elem) == 1);
2460 assert(PySet_GET_SIZE(ob) == 2);
2461 assert(PySet_Discard(ob, elem) == 0);
2462 assert(PySet_GET_SIZE(ob) == 2);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002463
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002464 /* Exercise clear */
2465 dup2 = PySet_New(dup);
2466 assert(PySet_Clear(dup2) == 0);
2467 assert(PySet_Size(dup2) == 0);
2468 Py_DECREF(dup2);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002469
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002470 /* Raise SystemError on clear or update of frozen set */
2471 f = PyFrozenSet_New(dup);
2472 assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
2473 assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
2474 assert(PySet_Add(f, elem) == 0);
2475 Py_INCREF(f);
2476 assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
2477 Py_DECREF(f);
2478 Py_DECREF(f);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002479
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002480 /* Exercise direct iteration */
2481 i = 0, count = 0;
2482 while (_PySet_NextEntry((PyObject *)dup, &i, &x, &hash)) {
2483 s = _PyUnicode_AsString(x);
2484 assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
2485 count++;
2486 }
2487 assert(count == 3);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002488
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002489 /* Exercise updates */
2490 dup2 = PySet_New(NULL);
2491 assert(_PySet_Update(dup2, dup) == 0);
2492 assert(PySet_Size(dup2) == 3);
2493 assert(_PySet_Update(dup2, dup) == 0);
2494 assert(PySet_Size(dup2) == 3);
2495 Py_DECREF(dup2);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002496
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002497 /* Raise SystemError when self argument is not a set or frozenset. */
2498 t = PyTuple_New(0);
2499 assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
2500 assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
2501 Py_DECREF(t);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002502
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002503 /* Raise SystemError when self argument is not a set. */
2504 f = PyFrozenSet_New(dup);
2505 assert(PySet_Size(f) == 3);
2506 assert(PyFrozenSet_CheckExact(f));
2507 assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
2508 assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
2509 Py_DECREF(f);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002510
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002511 /* Raise KeyError when popping from an empty set */
2512 assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
2513 Py_DECREF(ob);
2514 assert(PySet_GET_SIZE(ob) == 0);
2515 assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002516
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002517 /* Restore the set from the copy using the PyNumber API */
2518 assert(PyNumber_InPlaceOr(ob, dup) == ob);
2519 Py_DECREF(ob);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002520
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002521 /* Verify constructors accept NULL arguments */
2522 f = PySet_New(NULL);
2523 assert(f != NULL);
2524 assert(PySet_GET_SIZE(f) == 0);
2525 Py_DECREF(f);
2526 f = PyFrozenSet_New(NULL);
2527 assert(f != NULL);
2528 assert(PyFrozenSet_CheckExact(f));
2529 assert(PySet_GET_SIZE(f) == 0);
2530 Py_DECREF(f);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002531
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002532 Py_DECREF(elem);
2533 Py_DECREF(dup);
2534 Py_RETURN_TRUE;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002535}
2536
Raymond Hettinger9bda1d62005-09-16 07:14:21 +00002537#undef assertRaises
2538
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002539#endif