blob: 3abeefb97d9400a5945e5b9c9ad67e4325b89c89 [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 *
Benjamin Peterson8f67d082010-10-17 20:54:53 +000078set_lookkey(PySetObject *so, PyObject *key, register Py_hash_t hash)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000079{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000080 register Py_ssize_t i;
81 register size_t perturb;
82 register setentry *freeslot;
83 register size_t mask = so->mask;
84 setentry *table = so->table;
85 register setentry *entry;
86 register int cmp;
87 PyObject *startkey;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000088
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000089 i = hash & mask;
90 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) {
121 i = (i << 2) + i + perturb + 1;
122 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 *
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000160set_lookkey_unicode(PySetObject *so, PyObject *key, register Py_hash_t hash)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000161{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000162 register Py_ssize_t i;
163 register size_t perturb;
164 register setentry *freeslot;
165 register size_t mask = so->mask;
166 setentry *table = so->table;
167 register 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 }
177 i = hash & mask;
178 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) {
192 i = (i << 2) + i + perturb + 1;
193 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
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000214set_insert_key(register PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000215{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000216 register setentry *entry;
Antoine Pitroufbb1c612010-10-23 17:37:54 +0000217 typedef setentry *(*lookupfunc)(PySetObject *, PyObject *, Py_hash_t);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000218
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000219 assert(so->lookup != NULL);
220 entry = so->lookup(so, key, hash);
221 if (entry == NULL)
222 return -1;
223 if (entry->key == NULL) {
224 /* UNUSED */
225 so->fill++;
226 entry->key = key;
227 entry->hash = hash;
228 so->used++;
229 } else if (entry->key == dummy) {
230 /* DUMMY */
231 entry->key = key;
232 entry->hash = hash;
233 so->used++;
234 Py_DECREF(dummy);
235 } else {
236 /* ACTIVE */
237 Py_DECREF(key);
238 }
239 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000240}
241
242/*
Thomas Wouters89f507f2006-12-13 04:49:30 +0000243Internal routine used by set_table_resize() to insert an item which is
244known to be absent from the set. This routine also assumes that
245the set contains no deleted entries. Besides the performance benefit,
246using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
247Note that no refcounts are changed by this routine; if needed, the caller
248is responsible for incref'ing `key`.
249*/
250static void
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000251set_insert_clean(register PySetObject *so, PyObject *key, Py_hash_t hash)
Thomas Wouters89f507f2006-12-13 04:49:30 +0000252{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000253 register size_t i;
254 register size_t perturb;
255 register size_t mask = (size_t)so->mask;
256 setentry *table = so->table;
257 register setentry *entry;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000258
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000259 i = hash & mask;
260 entry = &table[i];
261 for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) {
262 i = (i << 2) + i + perturb + 1;
263 entry = &table[i & mask];
264 }
265 so->fill++;
266 entry->key = key;
267 entry->hash = hash;
268 so->used++;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000269}
270
271/*
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000272Restructure the table by allocating a new table and reinserting all
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000273keys again. When entries have been deleted, the new table may
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000274actually be smaller than the old one.
275*/
276static int
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000277set_table_resize(PySetObject *so, Py_ssize_t minused)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000278{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000279 Py_ssize_t newsize;
280 setentry *oldtable, *newtable, *entry;
281 Py_ssize_t i;
282 int is_oldtable_malloced;
283 setentry small_copy[PySet_MINSIZE];
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000284
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000285 assert(minused >= 0);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000286
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000287 /* Find the smallest table size > minused. */
288 for (newsize = PySet_MINSIZE;
289 newsize <= minused && newsize > 0;
290 newsize <<= 1)
291 ;
292 if (newsize <= 0) {
293 PyErr_NoMemory();
294 return -1;
295 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000296
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000297 /* Get space for a new table. */
298 oldtable = so->table;
299 assert(oldtable != NULL);
300 is_oldtable_malloced = oldtable != so->smalltable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000301
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000302 if (newsize == PySet_MINSIZE) {
303 /* A large table is shrinking, or we can't get any smaller. */
304 newtable = so->smalltable;
305 if (newtable == oldtable) {
306 if (so->fill == so->used) {
307 /* No dummies, so no point doing anything. */
308 return 0;
309 }
310 /* We're not going to resize it, but rebuild the
311 table anyway to purge old dummy entries.
312 Subtle: This is *necessary* if fill==size,
313 as set_lookkey needs at least one virgin slot to
314 terminate failing searches. If fill < size, it's
315 merely desirable, as dummies slow searches. */
316 assert(so->fill > so->used);
317 memcpy(small_copy, oldtable, sizeof(small_copy));
318 oldtable = small_copy;
319 }
320 }
321 else {
322 newtable = PyMem_NEW(setentry, newsize);
323 if (newtable == NULL) {
324 PyErr_NoMemory();
325 return -1;
326 }
327 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000328
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000329 /* Make the set empty, using the new table. */
330 assert(newtable != oldtable);
331 so->table = newtable;
332 so->mask = newsize - 1;
333 memset(newtable, 0, sizeof(setentry) * newsize);
334 so->used = 0;
335 i = so->fill;
336 so->fill = 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000337
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000338 /* Copy the data over; this is refcount-neutral for active entries;
339 dummy entries aren't copied over, of course */
340 for (entry = oldtable; i > 0; entry++) {
341 if (entry->key == NULL) {
342 /* UNUSED */
343 ;
344 } else if (entry->key == dummy) {
345 /* DUMMY */
346 --i;
347 assert(entry->key == dummy);
348 Py_DECREF(entry->key);
349 } else {
350 /* ACTIVE */
351 --i;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000352 set_insert_clean(so, entry->key, entry->hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000353 }
354 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000355
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000356 if (is_oldtable_malloced)
357 PyMem_DEL(oldtable);
358 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000359}
360
Raymond Hettingerc991db22005-08-11 07:58:45 +0000361/* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
362
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000363static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000364set_add_entry(register PySetObject *so, setentry *entry)
365{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000366 register Py_ssize_t n_used;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000367 PyObject *key = entry->key;
Éric Araujobbcfc1f2011-03-23 03:43:22 +0100368 Py_hash_t hash = entry->hash;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000369
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000370 assert(so->fill <= so->mask); /* at least one empty slot */
371 n_used = so->used;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000372 Py_INCREF(key);
Éric Araujo48049912011-03-23 02:08:07 +0100373 if (set_insert_key(so, key, hash) == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000374 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000375 return -1;
376 }
377 if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
378 return 0;
379 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettingerc991db22005-08-11 07:58:45 +0000380}
381
382static int
383set_add_key(register PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000384{
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000385 register Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000386 register Py_ssize_t n_used;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000387
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000388 if (!PyUnicode_CheckExact(key) ||
389 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
390 hash = PyObject_Hash(key);
391 if (hash == -1)
392 return -1;
393 }
394 assert(so->fill <= so->mask); /* at least one empty slot */
395 n_used = so->used;
396 Py_INCREF(key);
397 if (set_insert_key(so, key, hash) == -1) {
398 Py_DECREF(key);
399 return -1;
400 }
401 if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
402 return 0;
403 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000404}
405
406#define DISCARD_NOTFOUND 0
407#define DISCARD_FOUND 1
408
409static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000410set_discard_entry(PySetObject *so, setentry *oldentry)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000411{ register setentry *entry;
412 PyObject *old_key;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000413
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000414 entry = (so->lookup)(so, oldentry->key, oldentry->hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000415 if (entry == NULL)
416 return -1;
417 if (entry->key == NULL || entry->key == dummy)
418 return DISCARD_NOTFOUND;
419 old_key = entry->key;
420 Py_INCREF(dummy);
421 entry->key = dummy;
422 so->used--;
423 Py_DECREF(old_key);
424 return DISCARD_FOUND;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000425}
426
427static int
428set_discard_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000429{
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000430 register Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000431 register setentry *entry;
432 PyObject *old_key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000433
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000434 assert (PyAnySet_Check(so));
Christian Heimes0ded5b52007-12-10 15:50:56 +0000435
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000436 if (!PyUnicode_CheckExact(key) ||
437 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
438 hash = PyObject_Hash(key);
439 if (hash == -1)
440 return -1;
441 }
442 entry = (so->lookup)(so, key, hash);
443 if (entry == NULL)
444 return -1;
445 if (entry->key == NULL || entry->key == dummy)
446 return DISCARD_NOTFOUND;
447 old_key = entry->key;
448 Py_INCREF(dummy);
449 entry->key = dummy;
450 so->used--;
451 Py_DECREF(old_key);
452 return DISCARD_FOUND;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000453}
454
Raymond Hettingerfe889f32005-08-06 05:43:39 +0000455static int
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000456set_clear_internal(PySetObject *so)
457{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000458 setentry *entry, *table;
459 int table_is_malloced;
460 Py_ssize_t fill;
461 setentry small_copy[PySet_MINSIZE];
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000462#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000463 Py_ssize_t i, n;
464 assert (PyAnySet_Check(so));
Raymond Hettingera580c472005-08-05 17:19:54 +0000465
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000466 n = so->mask + 1;
467 i = 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000468#endif
469
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000470 table = so->table;
471 assert(table != NULL);
472 table_is_malloced = table != so->smalltable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000473
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000474 /* This is delicate. During the process of clearing the set,
475 * decrefs can cause the set to mutate. To avoid fatal confusion
476 * (voice of experience), we have to make the set empty before
477 * clearing the slots, and never refer to anything via so->ref while
478 * clearing.
479 */
480 fill = so->fill;
481 if (table_is_malloced)
482 EMPTY_TO_MINSIZE(so);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000483
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000484 else if (fill > 0) {
485 /* It's a small table with something that needs to be cleared.
486 * Afraid the only safe way is to copy the set entries into
487 * another small table first.
488 */
489 memcpy(small_copy, table, sizeof(small_copy));
490 table = small_copy;
491 EMPTY_TO_MINSIZE(so);
492 }
493 /* else it's a small table that's already empty */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000494
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000495 /* Now we can finally clear things. If C had refcounts, we could
496 * assert that the refcount on table is 1 now, i.e. that this function
497 * has unique access to it, so decref side-effects can't alter it.
498 */
499 for (entry = table; fill > 0; ++entry) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000500#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000501 assert(i < n);
502 ++i;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000503#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000504 if (entry->key) {
505 --fill;
506 Py_DECREF(entry->key);
507 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000508#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000509 else
510 assert(entry->key == NULL);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000511#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000512 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000513
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000514 if (table_is_malloced)
515 PyMem_DEL(table);
516 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000517}
518
519/*
520 * Iterate over a set table. Use like so:
521 *
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000522 * Py_ssize_t pos;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000523 * setentry *entry;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000524 * pos = 0; # important! pos should not otherwise be changed by you
Raymond Hettingerc991db22005-08-11 07:58:45 +0000525 * while (set_next(yourset, &pos, &entry)) {
526 * Refer to borrowed reference in entry->key.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000527 * }
528 *
Raymond Hettingerc991db22005-08-11 07:58:45 +0000529 * CAUTION: In general, it isn't safe to use set_next in a loop that
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000530 * mutates the table.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000531 */
532static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000533set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000534{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000535 Py_ssize_t i;
536 Py_ssize_t mask;
537 register setentry *table;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000538
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000539 assert (PyAnySet_Check(so));
540 i = *pos_ptr;
541 assert(i >= 0);
542 table = so->table;
543 mask = so->mask;
544 while (i <= mask && (table[i].key == NULL || table[i].key == dummy))
545 i++;
546 *pos_ptr = i+1;
547 if (i > mask)
548 return 0;
549 assert(table[i].key != NULL);
550 *entry_ptr = &table[i];
551 return 1;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000552}
553
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000554static void
555set_dealloc(PySetObject *so)
556{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000557 register setentry *entry;
558 Py_ssize_t fill = so->fill;
559 PyObject_GC_UnTrack(so);
560 Py_TRASHCAN_SAFE_BEGIN(so)
561 if (so->weakreflist != NULL)
562 PyObject_ClearWeakRefs((PyObject *) so);
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000563
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000564 for (entry = so->table; fill > 0; entry++) {
565 if (entry->key) {
566 --fill;
567 Py_DECREF(entry->key);
568 }
569 }
570 if (so->table != so->smalltable)
571 PyMem_DEL(so->table);
572 if (numfree < PySet_MAXFREELIST && PyAnySet_CheckExact(so))
573 free_list[numfree++] = so;
574 else
575 Py_TYPE(so)->tp_free(so);
576 Py_TRASHCAN_SAFE_END(so)
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000577}
578
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000579static PyObject *
580set_repr(PySetObject *so)
581{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000582 PyObject *keys, *result=NULL;
583 Py_UNICODE *u;
584 int status = Py_ReprEnter((PyObject*)so);
585 PyObject *listrepr;
586 Py_ssize_t newsize;
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000587
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000588 if (status != 0) {
589 if (status < 0)
590 return NULL;
591 return PyUnicode_FromFormat("%s(...)", Py_TYPE(so)->tp_name);
592 }
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000593
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000594 /* shortcut for the empty set */
595 if (!so->used) {
596 Py_ReprLeave((PyObject*)so);
597 return PyUnicode_FromFormat("%s()", Py_TYPE(so)->tp_name);
598 }
Georg Brandlc4996ba2006-08-28 19:37:11 +0000599
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000600 keys = PySequence_List((PyObject *)so);
601 if (keys == NULL)
602 goto done;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000603
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000604 listrepr = PyObject_Repr(keys);
605 Py_DECREF(keys);
606 if (listrepr == NULL)
607 goto done;
608 newsize = PyUnicode_GET_SIZE(listrepr);
609 result = PyUnicode_FromUnicode(NULL, newsize);
610 if (result) {
611 u = PyUnicode_AS_UNICODE(result);
612 *u++ = '{';
613 /* Omit the brackets from the listrepr */
614 Py_UNICODE_COPY(u, PyUnicode_AS_UNICODE(listrepr)+1,
615 PyUnicode_GET_SIZE(listrepr)-2);
616 u += newsize-2;
617 *u++ = '}';
618 }
619 Py_DECREF(listrepr);
620 if (Py_TYPE(so) != &PySet_Type) {
621 PyObject *tmp = PyUnicode_FromFormat("%s(%U)",
622 Py_TYPE(so)->tp_name,
623 result);
624 Py_DECREF(result);
625 result = tmp;
626 }
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000627done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000628 Py_ReprLeave((PyObject*)so);
629 return result;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000630}
631
Martin v. Löwis18e16552006-02-15 17:27:45 +0000632static Py_ssize_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000633set_len(PyObject *so)
634{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000635 return ((PySetObject *)so)->used;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000636}
637
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000638static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000639set_merge(PySetObject *so, PyObject *otherset)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000640{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000641 PySetObject *other;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000642 PyObject *key;
Éric Araujobbcfc1f2011-03-23 03:43:22 +0100643 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000644 register Py_ssize_t i;
645 register setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000646
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000647 assert (PyAnySet_Check(so));
648 assert (PyAnySet_Check(otherset));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000649
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000650 other = (PySetObject*)otherset;
651 if (other == so || other->used == 0)
652 /* a.update(a) or a.update({}); nothing to do */
653 return 0;
654 /* Do one big resize at the start, rather than
655 * incrementally resizing as we insert new keys. Expect
656 * that there will be no (or few) overlapping keys.
657 */
658 if ((so->fill + other->used)*3 >= (so->mask+1)*2) {
659 if (set_table_resize(so, (so->used + other->used)*2) != 0)
660 return -1;
661 }
662 for (i = 0; i <= other->mask; i++) {
663 entry = &other->table[i];
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000664 key = entry->key;
Éric Araujo48049912011-03-23 02:08:07 +0100665 hash = entry->hash;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000666 if (key != NULL &&
667 key != dummy) {
668 Py_INCREF(key);
Éric Araujo48049912011-03-23 02:08:07 +0100669 if (set_insert_key(so, key, hash) == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000670 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000671 return -1;
672 }
673 }
674 }
675 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000676}
677
678static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000679set_contains_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000680{
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000681 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000682 setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000683
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000684 if (!PyUnicode_CheckExact(key) ||
685 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
686 hash = PyObject_Hash(key);
687 if (hash == -1)
688 return -1;
689 }
690 entry = (so->lookup)(so, key, hash);
691 if (entry == NULL)
692 return -1;
693 key = entry->key;
694 return key != NULL && key != dummy;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000695}
696
Raymond Hettingerc991db22005-08-11 07:58:45 +0000697static int
698set_contains_entry(PySetObject *so, setentry *entry)
699{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000700 PyObject *key;
701 setentry *lu_entry;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000702
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000703 lu_entry = (so->lookup)(so, entry->key, entry->hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000704 if (lu_entry == NULL)
705 return -1;
706 key = lu_entry->key;
707 return key != NULL && key != dummy;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000708}
709
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000710static PyObject *
711set_pop(PySetObject *so)
712{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000713 register Py_ssize_t i = 0;
714 register setentry *entry;
715 PyObject *key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000716
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000717 assert (PyAnySet_Check(so));
718 if (so->used == 0) {
719 PyErr_SetString(PyExc_KeyError, "pop from an empty set");
720 return NULL;
721 }
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000722
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000723 /* Set entry to "the first" unused or dummy set entry. We abuse
724 * the hash field of slot 0 to hold a search finger:
725 * If slot 0 has a value, use slot 0.
726 * Else slot 0 is being used to hold a search finger,
727 * and we use its hash value as the first index to look.
728 */
729 entry = &so->table[0];
730 if (entry->key == NULL || entry->key == dummy) {
731 i = entry->hash;
732 /* The hash field may be a real hash value, or it may be a
733 * legit search finger, or it may be a once-legit search
734 * finger that's out of bounds now because it wrapped around
735 * or the table shrunk -- simply make sure it's in bounds now.
736 */
737 if (i > so->mask || i < 1)
738 i = 1; /* skip slot 0 */
739 while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
740 i++;
741 if (i > so->mask)
742 i = 1;
743 }
744 }
745 key = entry->key;
746 Py_INCREF(dummy);
747 entry->key = dummy;
748 so->used--;
749 so->table[0].hash = i + 1; /* next place to start */
750 return key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000751}
752
Benjamin Petersonf10a79a2008-10-11 00:49:57 +0000753PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\
754Raises KeyError if the set is empty.");
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000755
756static int
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000757set_traverse(PySetObject *so, visitproc visit, void *arg)
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000758{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000759 Py_ssize_t pos = 0;
760 setentry *entry;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000761
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000762 while (set_next(so, &pos, &entry))
763 Py_VISIT(entry->key);
764 return 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000765}
766
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000767static Py_hash_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000768frozenset_hash(PyObject *self)
769{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000770 PySetObject *so = (PySetObject *)self;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000771 Py_hash_t h, hash = 1927868237L;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000772 setentry *entry;
773 Py_ssize_t pos = 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000774
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000775 if (so->hash != -1)
776 return so->hash;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000777
Antoine Pitroufbb1c612010-10-23 17:37:54 +0000778 hash *= PySet_GET_SIZE(self) + 1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000779 while (set_next(so, &pos, &entry)) {
780 /* Work to increase the bit dispersion for closely spaced hash
781 values. The is important because some use cases have many
782 combinations of a small number of elements with nearby
783 hashes so that many distinct combinations collapse to only
784 a handful of distinct hash values. */
Antoine Pitroufbb1c612010-10-23 17:37:54 +0000785 h = entry->hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000786 hash ^= (h ^ (h << 16) ^ 89869747L) * 3644798167u;
787 }
788 hash = hash * 69069L + 907133923L;
789 if (hash == -1)
790 hash = 590923713L;
791 so->hash = hash;
792 return hash;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000793}
794
Raymond Hettingera9d99362005-08-05 00:01:15 +0000795/***** Set iterator type ***********************************************/
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000796
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000797typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000798 PyObject_HEAD
799 PySetObject *si_set; /* Set to NULL when iterator is exhausted */
800 Py_ssize_t si_used;
801 Py_ssize_t si_pos;
802 Py_ssize_t len;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000803} setiterobject;
804
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000805static void
806setiter_dealloc(setiterobject *si)
807{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000808 Py_XDECREF(si->si_set);
809 PyObject_GC_Del(si);
Antoine Pitrou7ddda782009-01-01 15:35:33 +0000810}
811
812static int
813setiter_traverse(setiterobject *si, visitproc visit, void *arg)
814{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000815 Py_VISIT(si->si_set);
816 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000817}
818
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000819static PyObject *
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000820setiter_len(setiterobject *si)
821{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000822 Py_ssize_t len = 0;
823 if (si->si_set != NULL && si->si_used == si->si_set->used)
824 len = si->len;
Antoine Pitrou671b4d92010-08-17 17:55:07 +0000825 return PyLong_FromSsize_t(len);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000826}
827
Armin Rigof5b3e362006-02-11 21:32:43 +0000828PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000829
830static PyMethodDef setiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000831 {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
832 {NULL, NULL} /* sentinel */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000833};
834
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000835static PyObject *setiter_iternext(setiterobject *si)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000836{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000837 PyObject *key;
838 register Py_ssize_t i, mask;
839 register setentry *entry;
840 PySetObject *so = si->si_set;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000841
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000842 if (so == NULL)
843 return NULL;
844 assert (PyAnySet_Check(so));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000845
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000846 if (si->si_used != so->used) {
847 PyErr_SetString(PyExc_RuntimeError,
848 "Set changed size during iteration");
849 si->si_used = -1; /* Make this state sticky */
850 return NULL;
851 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000852
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000853 i = si->si_pos;
854 assert(i>=0);
855 entry = so->table;
856 mask = so->mask;
857 while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
858 i++;
859 si->si_pos = i+1;
860 if (i > mask)
861 goto fail;
862 si->len--;
863 key = entry[i].key;
864 Py_INCREF(key);
865 return key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000866
867fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000868 Py_DECREF(so);
869 si->si_set = NULL;
870 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000871}
872
Christian Heimesa22e8bd2007-11-29 22:35:39 +0000873PyTypeObject PySetIter_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000874 PyVarObject_HEAD_INIT(&PyType_Type, 0)
875 "set_iterator", /* tp_name */
876 sizeof(setiterobject), /* tp_basicsize */
877 0, /* tp_itemsize */
878 /* methods */
879 (destructor)setiter_dealloc, /* tp_dealloc */
880 0, /* tp_print */
881 0, /* tp_getattr */
882 0, /* tp_setattr */
883 0, /* tp_reserved */
884 0, /* tp_repr */
885 0, /* tp_as_number */
886 0, /* tp_as_sequence */
887 0, /* tp_as_mapping */
888 0, /* tp_hash */
889 0, /* tp_call */
890 0, /* tp_str */
891 PyObject_GenericGetAttr, /* tp_getattro */
892 0, /* tp_setattro */
893 0, /* tp_as_buffer */
894 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
895 0, /* tp_doc */
896 (traverseproc)setiter_traverse, /* tp_traverse */
897 0, /* tp_clear */
898 0, /* tp_richcompare */
899 0, /* tp_weaklistoffset */
900 PyObject_SelfIter, /* tp_iter */
901 (iternextfunc)setiter_iternext, /* tp_iternext */
902 setiter_methods, /* tp_methods */
903 0,
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000904};
905
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000906static PyObject *
907set_iter(PySetObject *so)
908{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000909 setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type);
910 if (si == NULL)
911 return NULL;
912 Py_INCREF(so);
913 si->si_set = so;
914 si->si_used = so->used;
915 si->si_pos = 0;
916 si->len = so->used;
917 _PyObject_GC_TRACK(si);
918 return (PyObject *)si;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000919}
920
Raymond Hettingerd7946662005-08-01 21:39:29 +0000921static int
Raymond Hettingerd7946662005-08-01 21:39:29 +0000922set_update_internal(PySetObject *so, PyObject *other)
Raymond Hettingera690a992003-11-16 16:17:49 +0000923{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000924 PyObject *key, *it;
Raymond Hettingera690a992003-11-16 16:17:49 +0000925
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000926 if (PyAnySet_Check(other))
927 return set_merge(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +0000928
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000929 if (PyDict_CheckExact(other)) {
930 PyObject *value;
931 Py_ssize_t pos = 0;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000932 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000933 Py_ssize_t dictsize = PyDict_Size(other);
Thomas Wouterscf297e42007-02-23 15:07:44 +0000934
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000935 /* Do one big resize at the start, rather than
936 * incrementally resizing as we insert new keys. Expect
937 * that there will be no (or few) overlapping keys.
938 */
939 if (dictsize == -1)
940 return -1;
941 if ((so->fill + dictsize)*3 >= (so->mask+1)*2) {
942 if (set_table_resize(so, (so->used + dictsize)*2) != 0)
943 return -1;
944 }
945 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
946 setentry an_entry;
Thomas Wouterscf297e42007-02-23 15:07:44 +0000947
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000948 an_entry.hash = hash;
949 an_entry.key = key;
950 if (set_add_entry(so, &an_entry) == -1)
951 return -1;
952 }
953 return 0;
954 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000955
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000956 it = PyObject_GetIter(other);
957 if (it == NULL)
958 return -1;
Raymond Hettingera690a992003-11-16 16:17:49 +0000959
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000960 while ((key = PyIter_Next(it)) != NULL) {
961 if (set_add_key(so, key) == -1) {
962 Py_DECREF(it);
963 Py_DECREF(key);
964 return -1;
965 }
966 Py_DECREF(key);
967 }
968 Py_DECREF(it);
969 if (PyErr_Occurred())
970 return -1;
971 return 0;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000972}
973
974static PyObject *
Georg Brandlc28e1fa2008-06-10 19:20:26 +0000975set_update(PySetObject *so, PyObject *args)
Raymond Hettingerd7946662005-08-01 21:39:29 +0000976{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000977 Py_ssize_t i;
Georg Brandlc28e1fa2008-06-10 19:20:26 +0000978
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000979 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
980 PyObject *other = PyTuple_GET_ITEM(args, i);
981 if (set_update_internal(so, other) == -1)
982 return NULL;
983 }
984 Py_RETURN_NONE;
Raymond Hettingera38123e2003-11-24 22:18:49 +0000985}
986
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000987PyDoc_STRVAR(update_doc,
Georg Brandlc28e1fa2008-06-10 19:20:26 +0000988"Update a set with the union of itself and others.");
Raymond Hettingera38123e2003-11-24 22:18:49 +0000989
990static PyObject *
991make_new_set(PyTypeObject *type, PyObject *iterable)
992{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000993 register PySetObject *so = NULL;
Raymond Hettingera38123e2003-11-24 22:18:49 +0000994
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000995 if (dummy == NULL) { /* Auto-initialize dummy */
996 dummy = PyUnicode_FromString("<dummy key>");
997 if (dummy == NULL)
998 return NULL;
999 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001000
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001001 /* create PySetObject structure */
1002 if (numfree &&
1003 (type == &PySet_Type || type == &PyFrozenSet_Type)) {
1004 so = free_list[--numfree];
1005 assert (so != NULL && PyAnySet_CheckExact(so));
1006 Py_TYPE(so) = type;
1007 _Py_NewReference((PyObject *)so);
1008 EMPTY_TO_MINSIZE(so);
1009 PyObject_GC_Track(so);
1010 } else {
1011 so = (PySetObject *)type->tp_alloc(type, 0);
1012 if (so == NULL)
1013 return NULL;
1014 /* tp_alloc has already zeroed the structure */
1015 assert(so->table == NULL && so->fill == 0 && so->used == 0);
1016 INIT_NONZERO_SET_SLOTS(so);
1017 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001018
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001019 so->lookup = set_lookkey_unicode;
1020 so->weakreflist = NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001021
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001022 if (iterable != NULL) {
1023 if (set_update_internal(so, iterable) == -1) {
1024 Py_DECREF(so);
1025 return NULL;
1026 }
1027 }
Raymond Hettingera38123e2003-11-24 22:18:49 +00001028
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001029 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001030}
1031
Raymond Hettinger7d99f092008-11-16 11:44:54 +00001032static PyObject *
1033make_new_set_basetype(PyTypeObject *type, PyObject *iterable)
1034{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001035 if (type != &PySet_Type && type != &PyFrozenSet_Type) {
1036 if (PyType_IsSubtype(type, &PySet_Type))
1037 type = &PySet_Type;
1038 else
1039 type = &PyFrozenSet_Type;
1040 }
1041 return make_new_set(type, iterable);
Raymond Hettinger7d99f092008-11-16 11:44:54 +00001042}
1043
Raymond Hettingerd7946662005-08-01 21:39:29 +00001044/* The empty frozenset is a singleton */
1045static PyObject *emptyfrozenset = NULL;
1046
Raymond Hettingera690a992003-11-16 16:17:49 +00001047static PyObject *
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001048frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
Raymond Hettingera690a992003-11-16 16:17:49 +00001049{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001050 PyObject *iterable = NULL, *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001051
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001052 if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds))
1053 return NULL;
Georg Brandl02c42872005-08-26 06:42:30 +00001054
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001055 if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
1056 return NULL;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001057
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001058 if (type != &PyFrozenSet_Type)
1059 return make_new_set(type, iterable);
Raymond Hettingerd7946662005-08-01 21:39:29 +00001060
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001061 if (iterable != NULL) {
1062 /* frozenset(f) is idempotent */
1063 if (PyFrozenSet_CheckExact(iterable)) {
1064 Py_INCREF(iterable);
1065 return iterable;
1066 }
1067 result = make_new_set(type, iterable);
1068 if (result == NULL || PySet_GET_SIZE(result))
1069 return result;
1070 Py_DECREF(result);
1071 }
1072 /* The empty frozenset is a singleton */
1073 if (emptyfrozenset == NULL)
1074 emptyfrozenset = make_new_set(type, NULL);
1075 Py_XINCREF(emptyfrozenset);
1076 return emptyfrozenset;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001077}
1078
1079void
1080PySet_Fini(void)
1081{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001082 PySetObject *so;
Raymond Hettingerbc841a12005-08-07 13:02:53 +00001083
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001084 while (numfree) {
1085 numfree--;
1086 so = free_list[numfree];
1087 PyObject_GC_Del(so);
1088 }
1089 Py_CLEAR(dummy);
1090 Py_CLEAR(emptyfrozenset);
Raymond Hettingera690a992003-11-16 16:17:49 +00001091}
1092
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001093static PyObject *
1094set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1095{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001096 if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds))
1097 return NULL;
1098
1099 return make_new_set(type, NULL);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001100}
1101
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001102/* set_swap_bodies() switches the contents of any two sets by moving their
1103 internal data pointers and, if needed, copying the internal smalltables.
1104 Semantically equivalent to:
1105
1106 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1107
1108 The function always succeeds and it leaves both objects in a stable state.
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001109 Useful for creating temporary frozensets from sets for membership testing
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001110 in __contains__(), discard(), and remove(). Also useful for operations
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001111 that update in-place (by allowing an intermediate result to be swapped
Raymond Hettinger9dcb17c2005-07-31 13:09:28 +00001112 into one of the original inputs).
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001113*/
1114
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001115static void
1116set_swap_bodies(PySetObject *a, PySetObject *b)
Raymond Hettingera690a992003-11-16 16:17:49 +00001117{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001118 Py_ssize_t t;
1119 setentry *u;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001120 setentry *(*f)(PySetObject *so, PyObject *key, Py_ssize_t hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001121 setentry tab[PySet_MINSIZE];
Antoine Pitroufbb1c612010-10-23 17:37:54 +00001122 Py_hash_t h;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001123
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001124 t = a->fill; a->fill = b->fill; b->fill = t;
1125 t = a->used; a->used = b->used; b->used = t;
1126 t = a->mask; a->mask = b->mask; b->mask = t;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001127
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001128 u = a->table;
1129 if (a->table == a->smalltable)
1130 u = b->smalltable;
1131 a->table = b->table;
1132 if (b->table == b->smalltable)
1133 a->table = a->smalltable;
1134 b->table = u;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001135
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001136 f = a->lookup; a->lookup = b->lookup; b->lookup = f;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001137
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001138 if (a->table == a->smalltable || b->table == b->smalltable) {
1139 memcpy(tab, a->smalltable, sizeof(tab));
1140 memcpy(a->smalltable, b->smalltable, sizeof(tab));
1141 memcpy(b->smalltable, tab, sizeof(tab));
1142 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001143
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001144 if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type) &&
1145 PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) {
1146 h = a->hash; a->hash = b->hash; b->hash = h;
1147 } else {
1148 a->hash = -1;
1149 b->hash = -1;
1150 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001151}
1152
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001153static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001154set_copy(PySetObject *so)
1155{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001156 return make_new_set_basetype(Py_TYPE(so), (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001157}
1158
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001159static PyObject *
1160frozenset_copy(PySetObject *so)
1161{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001162 if (PyFrozenSet_CheckExact(so)) {
1163 Py_INCREF(so);
1164 return (PyObject *)so;
1165 }
1166 return set_copy(so);
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001167}
1168
Raymond Hettingera690a992003-11-16 16:17:49 +00001169PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
1170
1171static PyObject *
Raymond Hettingerc991db22005-08-11 07:58:45 +00001172set_clear(PySetObject *so)
1173{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001174 set_clear_internal(so);
1175 Py_RETURN_NONE;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001176}
1177
1178PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
1179
1180static PyObject *
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001181set_union(PySetObject *so, PyObject *args)
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001182{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001183 PySetObject *result;
1184 PyObject *other;
1185 Py_ssize_t i;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001186
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001187 result = (PySetObject *)set_copy(so);
1188 if (result == NULL)
1189 return NULL;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001190
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001191 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1192 other = PyTuple_GET_ITEM(args, i);
1193 if ((PyObject *)so == other)
1194 continue;
1195 if (set_update_internal(result, other) == -1) {
1196 Py_DECREF(result);
1197 return NULL;
1198 }
1199 }
1200 return (PyObject *)result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001201}
1202
1203PyDoc_STRVAR(union_doc,
1204 "Return the union of sets as a new set.\n\
1205\n\
1206(i.e. all elements that are in either set.)");
1207
1208static PyObject *
1209set_or(PySetObject *so, PyObject *other)
1210{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001211 PySetObject *result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001212
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001213 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
1214 Py_INCREF(Py_NotImplemented);
1215 return Py_NotImplemented;
1216 }
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001217
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001218 result = (PySetObject *)set_copy(so);
1219 if (result == NULL)
1220 return NULL;
1221 if ((PyObject *)so == other)
1222 return (PyObject *)result;
1223 if (set_update_internal(result, other) == -1) {
1224 Py_DECREF(result);
1225 return NULL;
1226 }
1227 return (PyObject *)result;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001228}
1229
Raymond Hettingera690a992003-11-16 16:17:49 +00001230static PyObject *
1231set_ior(PySetObject *so, PyObject *other)
1232{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001233 if (!PyAnySet_Check(other)) {
1234 Py_INCREF(Py_NotImplemented);
1235 return Py_NotImplemented;
1236 }
1237 if (set_update_internal(so, other) == -1)
1238 return NULL;
1239 Py_INCREF(so);
1240 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001241}
1242
1243static PyObject *
1244set_intersection(PySetObject *so, PyObject *other)
1245{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001246 PySetObject *result;
1247 PyObject *key, *it, *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001248
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001249 if ((PyObject *)so == other)
1250 return set_copy(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001251
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001252 result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL);
1253 if (result == NULL)
1254 return NULL;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001255
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001256 if (PyAnySet_Check(other)) {
1257 Py_ssize_t pos = 0;
1258 setentry *entry;
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001259
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001260 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1261 tmp = (PyObject *)so;
1262 so = (PySetObject *)other;
1263 other = tmp;
1264 }
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001265
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001266 while (set_next((PySetObject *)other, &pos, &entry)) {
1267 int rv = set_contains_entry(so, entry);
1268 if (rv == -1) {
1269 Py_DECREF(result);
1270 return NULL;
1271 }
1272 if (rv) {
1273 if (set_add_entry(result, entry) == -1) {
1274 Py_DECREF(result);
1275 return NULL;
1276 }
1277 }
1278 }
1279 return (PyObject *)result;
1280 }
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001281
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001282 it = PyObject_GetIter(other);
1283 if (it == NULL) {
1284 Py_DECREF(result);
1285 return NULL;
1286 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001287
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001288 while ((key = PyIter_Next(it)) != NULL) {
1289 int rv;
1290 setentry entry;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001291 Py_hash_t hash = PyObject_Hash(key);
Thomas Wouters89f507f2006-12-13 04:49:30 +00001292
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001293 if (hash == -1) {
1294 Py_DECREF(it);
1295 Py_DECREF(result);
1296 Py_DECREF(key);
1297 return NULL;
1298 }
1299 entry.hash = hash;
1300 entry.key = key;
1301 rv = set_contains_entry(so, &entry);
1302 if (rv == -1) {
1303 Py_DECREF(it);
1304 Py_DECREF(result);
1305 Py_DECREF(key);
1306 return NULL;
1307 }
1308 if (rv) {
1309 if (set_add_entry(result, &entry) == -1) {
1310 Py_DECREF(it);
1311 Py_DECREF(result);
1312 Py_DECREF(key);
1313 return NULL;
1314 }
1315 }
1316 Py_DECREF(key);
1317 }
1318 Py_DECREF(it);
1319 if (PyErr_Occurred()) {
1320 Py_DECREF(result);
1321 return NULL;
1322 }
1323 return (PyObject *)result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001324}
1325
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001326static PyObject *
1327set_intersection_multi(PySetObject *so, PyObject *args)
1328{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001329 Py_ssize_t i;
1330 PyObject *result = (PyObject *)so;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001331
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001332 if (PyTuple_GET_SIZE(args) == 0)
1333 return set_copy(so);
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001334
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001335 Py_INCREF(so);
1336 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1337 PyObject *other = PyTuple_GET_ITEM(args, i);
1338 PyObject *newresult = set_intersection((PySetObject *)result, other);
1339 if (newresult == NULL) {
1340 Py_DECREF(result);
1341 return NULL;
1342 }
1343 Py_DECREF(result);
1344 result = newresult;
1345 }
1346 return result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001347}
1348
Raymond Hettingera690a992003-11-16 16:17:49 +00001349PyDoc_STRVAR(intersection_doc,
1350"Return the intersection of two sets as a new set.\n\
1351\n\
1352(i.e. all elements that are in both sets.)");
1353
1354static PyObject *
1355set_intersection_update(PySetObject *so, PyObject *other)
1356{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001357 PyObject *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001358
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001359 tmp = set_intersection(so, other);
1360 if (tmp == NULL)
1361 return NULL;
1362 set_swap_bodies(so, (PySetObject *)tmp);
1363 Py_DECREF(tmp);
1364 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001365}
1366
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001367static PyObject *
1368set_intersection_update_multi(PySetObject *so, PyObject *args)
1369{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001370 PyObject *tmp;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001371
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001372 tmp = set_intersection_multi(so, args);
1373 if (tmp == NULL)
1374 return NULL;
1375 set_swap_bodies(so, (PySetObject *)tmp);
1376 Py_DECREF(tmp);
1377 Py_RETURN_NONE;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001378}
1379
Raymond Hettingera690a992003-11-16 16:17:49 +00001380PyDoc_STRVAR(intersection_update_doc,
1381"Update a set with the intersection of itself and another.");
1382
1383static PyObject *
1384set_and(PySetObject *so, PyObject *other)
1385{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001386 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
1387 Py_INCREF(Py_NotImplemented);
1388 return Py_NotImplemented;
1389 }
1390 return set_intersection(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001391}
1392
1393static PyObject *
1394set_iand(PySetObject *so, PyObject *other)
1395{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001396 PyObject *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001397
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001398 if (!PyAnySet_Check(other)) {
1399 Py_INCREF(Py_NotImplemented);
1400 return Py_NotImplemented;
1401 }
1402 result = set_intersection_update(so, other);
1403 if (result == NULL)
1404 return NULL;
1405 Py_DECREF(result);
1406 Py_INCREF(so);
1407 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001408}
1409
Guido van Rossum58da9312007-11-10 23:39:45 +00001410static PyObject *
1411set_isdisjoint(PySetObject *so, PyObject *other)
1412{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001413 PyObject *key, *it, *tmp;
Guido van Rossum58da9312007-11-10 23:39:45 +00001414
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001415 if ((PyObject *)so == other) {
1416 if (PySet_GET_SIZE(so) == 0)
1417 Py_RETURN_TRUE;
1418 else
1419 Py_RETURN_FALSE;
1420 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001421
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001422 if (PyAnySet_CheckExact(other)) {
1423 Py_ssize_t pos = 0;
1424 setentry *entry;
Guido van Rossum58da9312007-11-10 23:39:45 +00001425
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001426 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1427 tmp = (PyObject *)so;
1428 so = (PySetObject *)other;
1429 other = tmp;
1430 }
1431 while (set_next((PySetObject *)other, &pos, &entry)) {
1432 int rv = set_contains_entry(so, entry);
1433 if (rv == -1)
1434 return NULL;
1435 if (rv)
1436 Py_RETURN_FALSE;
1437 }
1438 Py_RETURN_TRUE;
1439 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001440
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001441 it = PyObject_GetIter(other);
1442 if (it == NULL)
1443 return NULL;
Guido van Rossum58da9312007-11-10 23:39:45 +00001444
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001445 while ((key = PyIter_Next(it)) != NULL) {
1446 int rv;
1447 setentry entry;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001448 Py_hash_t hash = PyObject_Hash(key);
Guido van Rossum58da9312007-11-10 23:39:45 +00001449
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001450 if (hash == -1) {
1451 Py_DECREF(key);
1452 Py_DECREF(it);
1453 return NULL;
1454 }
1455 entry.hash = hash;
1456 entry.key = key;
1457 rv = set_contains_entry(so, &entry);
1458 Py_DECREF(key);
1459 if (rv == -1) {
1460 Py_DECREF(it);
1461 return NULL;
1462 }
1463 if (rv) {
1464 Py_DECREF(it);
1465 Py_RETURN_FALSE;
1466 }
1467 }
1468 Py_DECREF(it);
1469 if (PyErr_Occurred())
1470 return NULL;
1471 Py_RETURN_TRUE;
Guido van Rossum58da9312007-11-10 23:39:45 +00001472}
1473
1474PyDoc_STRVAR(isdisjoint_doc,
1475"Return True if two sets have a null intersection.");
1476
Neal Norwitz6576bd82005-11-13 18:41:28 +00001477static int
Raymond Hettingerc991db22005-08-11 07:58:45 +00001478set_difference_update_internal(PySetObject *so, PyObject *other)
1479{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001480 if ((PyObject *)so == other)
1481 return set_clear_internal(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001482
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001483 if (PyAnySet_Check(other)) {
1484 setentry *entry;
1485 Py_ssize_t pos = 0;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001486
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001487 while (set_next((PySetObject *)other, &pos, &entry))
1488 if (set_discard_entry(so, entry) == -1)
1489 return -1;
1490 } else {
1491 PyObject *key, *it;
1492 it = PyObject_GetIter(other);
1493 if (it == NULL)
1494 return -1;
1495
1496 while ((key = PyIter_Next(it)) != NULL) {
1497 if (set_discard_key(so, key) == -1) {
1498 Py_DECREF(it);
1499 Py_DECREF(key);
1500 return -1;
1501 }
1502 Py_DECREF(key);
1503 }
1504 Py_DECREF(it);
1505 if (PyErr_Occurred())
1506 return -1;
1507 }
1508 /* If more than 1/5 are dummies, then resize them away. */
1509 if ((so->fill - so->used) * 5 < so->mask)
1510 return 0;
1511 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001512}
1513
Raymond Hettingera690a992003-11-16 16:17:49 +00001514static PyObject *
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001515set_difference_update(PySetObject *so, PyObject *args)
Raymond Hettingera690a992003-11-16 16:17:49 +00001516{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001517 Py_ssize_t i;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001518
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001519 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1520 PyObject *other = PyTuple_GET_ITEM(args, i);
1521 if (set_difference_update_internal(so, other) == -1)
1522 return NULL;
1523 }
1524 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001525}
1526
1527PyDoc_STRVAR(difference_update_doc,
1528"Remove all elements of another set from this set.");
1529
1530static PyObject *
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001531set_copy_and_difference(PySetObject *so, PyObject *other)
1532{
1533 PyObject *result;
1534
1535 result = set_copy(so);
1536 if (result == NULL)
1537 return NULL;
1538 if (set_difference_update_internal((PySetObject *) result, other) != -1)
1539 return result;
1540 Py_DECREF(result);
1541 return NULL;
1542}
1543
1544static PyObject *
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001545set_difference(PySetObject *so, PyObject *other)
1546{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001547 PyObject *result;
1548 setentry *entry;
1549 Py_ssize_t pos = 0;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001550
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001551 if (!PyAnySet_Check(other) && !PyDict_CheckExact(other)) {
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001552 return set_copy_and_difference(so, other);
1553 }
1554
1555 /* If len(so) much more than len(other), it's more efficient to simply copy
1556 * so and then iterate other looking for common elements. */
1557 if ((PySet_GET_SIZE(so) >> 2) > PyObject_Size(other)) {
1558 return set_copy_and_difference(so, other);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001559 }
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001560
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001561 result = make_new_set_basetype(Py_TYPE(so), NULL);
1562 if (result == NULL)
1563 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001564
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001565 if (PyDict_CheckExact(other)) {
1566 while (set_next(so, &pos, &entry)) {
1567 setentry entrycopy;
1568 entrycopy.hash = entry->hash;
1569 entrycopy.key = entry->key;
Antoine Pitroufbb1c612010-10-23 17:37:54 +00001570 if (!_PyDict_Contains(other, entry->key, entry->hash)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001571 if (set_add_entry((PySetObject *)result, &entrycopy) == -1) {
1572 Py_DECREF(result);
1573 return NULL;
1574 }
1575 }
1576 }
1577 return result;
1578 }
1579
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001580 /* Iterate over so, checking for common elements in other. */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001581 while (set_next(so, &pos, &entry)) {
1582 int rv = set_contains_entry((PySetObject *)other, entry);
1583 if (rv == -1) {
1584 Py_DECREF(result);
1585 return NULL;
1586 }
1587 if (!rv) {
1588 if (set_add_entry((PySetObject *)result, entry) == -1) {
1589 Py_DECREF(result);
1590 return NULL;
1591 }
1592 }
1593 }
1594 return result;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001595}
1596
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001597static PyObject *
1598set_difference_multi(PySetObject *so, PyObject *args)
1599{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001600 Py_ssize_t i;
1601 PyObject *result, *other;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001602
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001603 if (PyTuple_GET_SIZE(args) == 0)
1604 return set_copy(so);
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001605
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001606 other = PyTuple_GET_ITEM(args, 0);
1607 result = set_difference(so, other);
1608 if (result == NULL)
1609 return NULL;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001610
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001611 for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) {
1612 other = PyTuple_GET_ITEM(args, i);
1613 if (set_difference_update_internal((PySetObject *)result, other) == -1) {
1614 Py_DECREF(result);
1615 return NULL;
1616 }
1617 }
1618 return result;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001619}
1620
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001621PyDoc_STRVAR(difference_doc,
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001622"Return the difference of two or more sets as a new set.\n\
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001623\n\
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001624(i.e. all elements that are in this set but not the others.)");
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001625static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001626set_sub(PySetObject *so, PyObject *other)
1627{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001628 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
1629 Py_INCREF(Py_NotImplemented);
1630 return Py_NotImplemented;
1631 }
1632 return set_difference(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001633}
1634
1635static PyObject *
1636set_isub(PySetObject *so, PyObject *other)
1637{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001638 if (!PyAnySet_Check(other)) {
1639 Py_INCREF(Py_NotImplemented);
1640 return Py_NotImplemented;
1641 }
1642 if (set_difference_update_internal(so, other) == -1)
1643 return NULL;
1644 Py_INCREF(so);
1645 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001646}
1647
1648static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001649set_symmetric_difference_update(PySetObject *so, PyObject *other)
1650{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001651 PySetObject *otherset;
1652 PyObject *key;
1653 Py_ssize_t pos = 0;
1654 setentry *entry;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001655
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001656 if ((PyObject *)so == other)
1657 return set_clear(so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001658
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001659 if (PyDict_CheckExact(other)) {
1660 PyObject *value;
1661 int rv;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001662 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001663 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
1664 setentry an_entry;
Thomas Wouters89f507f2006-12-13 04:49:30 +00001665
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001666 Py_INCREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001667 an_entry.hash = hash;
1668 an_entry.key = key;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001669
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001670 rv = set_discard_entry(so, &an_entry);
Georg Brandl2d444492010-09-03 10:52:55 +00001671 if (rv == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001672 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001673 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001674 }
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001675 if (rv == DISCARD_NOTFOUND) {
1676 if (set_add_entry(so, &an_entry) == -1) {
1677 Py_DECREF(key);
1678 return NULL;
1679 }
1680 }
Georg Brandl2d444492010-09-03 10:52:55 +00001681 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001682 }
1683 Py_RETURN_NONE;
1684 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001685
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001686 if (PyAnySet_Check(other)) {
1687 Py_INCREF(other);
1688 otherset = (PySetObject *)other;
1689 } else {
1690 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1691 if (otherset == NULL)
1692 return NULL;
1693 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001694
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001695 while (set_next(otherset, &pos, &entry)) {
1696 int rv = set_discard_entry(so, entry);
1697 if (rv == -1) {
1698 Py_DECREF(otherset);
1699 return NULL;
1700 }
1701 if (rv == DISCARD_NOTFOUND) {
1702 if (set_add_entry(so, entry) == -1) {
1703 Py_DECREF(otherset);
1704 return NULL;
1705 }
1706 }
1707 }
1708 Py_DECREF(otherset);
1709 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001710}
1711
1712PyDoc_STRVAR(symmetric_difference_update_doc,
1713"Update a set with the symmetric difference of itself and another.");
1714
1715static PyObject *
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001716set_symmetric_difference(PySetObject *so, PyObject *other)
1717{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001718 PyObject *rv;
1719 PySetObject *otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001720
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001721 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1722 if (otherset == NULL)
1723 return NULL;
1724 rv = set_symmetric_difference_update(otherset, (PyObject *)so);
1725 if (rv == NULL)
1726 return NULL;
1727 Py_DECREF(rv);
1728 return (PyObject *)otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001729}
1730
1731PyDoc_STRVAR(symmetric_difference_doc,
1732"Return the symmetric difference of two sets as a new set.\n\
1733\n\
1734(i.e. all elements that are in exactly one of the sets.)");
1735
1736static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001737set_xor(PySetObject *so, PyObject *other)
1738{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001739 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
1740 Py_INCREF(Py_NotImplemented);
1741 return Py_NotImplemented;
1742 }
1743 return set_symmetric_difference(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001744}
1745
1746static PyObject *
1747set_ixor(PySetObject *so, PyObject *other)
1748{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001749 PyObject *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001750
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001751 if (!PyAnySet_Check(other)) {
1752 Py_INCREF(Py_NotImplemented);
1753 return Py_NotImplemented;
1754 }
1755 result = set_symmetric_difference_update(so, other);
1756 if (result == NULL)
1757 return NULL;
1758 Py_DECREF(result);
1759 Py_INCREF(so);
1760 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001761}
1762
1763static PyObject *
1764set_issubset(PySetObject *so, PyObject *other)
1765{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001766 setentry *entry;
1767 Py_ssize_t pos = 0;
Raymond Hettingera690a992003-11-16 16:17:49 +00001768
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001769 if (!PyAnySet_Check(other)) {
1770 PyObject *tmp, *result;
1771 tmp = make_new_set(&PySet_Type, other);
1772 if (tmp == NULL)
1773 return NULL;
1774 result = set_issubset(so, tmp);
1775 Py_DECREF(tmp);
1776 return result;
1777 }
1778 if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
1779 Py_RETURN_FALSE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001780
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001781 while (set_next(so, &pos, &entry)) {
1782 int rv = set_contains_entry((PySetObject *)other, entry);
1783 if (rv == -1)
1784 return NULL;
1785 if (!rv)
1786 Py_RETURN_FALSE;
1787 }
1788 Py_RETURN_TRUE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001789}
1790
1791PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
1792
1793static PyObject *
1794set_issuperset(PySetObject *so, PyObject *other)
1795{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001796 PyObject *tmp, *result;
Raymond Hettinger3fbec702003-11-21 07:56:36 +00001797
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001798 if (!PyAnySet_Check(other)) {
1799 tmp = make_new_set(&PySet_Type, other);
1800 if (tmp == NULL)
1801 return NULL;
1802 result = set_issuperset(so, tmp);
1803 Py_DECREF(tmp);
1804 return result;
1805 }
1806 return set_issubset((PySetObject *)other, (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001807}
1808
1809PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
1810
Raymond Hettingera690a992003-11-16 16:17:49 +00001811static PyObject *
1812set_richcompare(PySetObject *v, PyObject *w, int op)
1813{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001814 PyObject *r1, *r2;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001815
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001816 if(!PyAnySet_Check(w)) {
1817 Py_INCREF(Py_NotImplemented);
1818 return Py_NotImplemented;
1819 }
1820 switch (op) {
1821 case Py_EQ:
1822 if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
1823 Py_RETURN_FALSE;
1824 if (v->hash != -1 &&
1825 ((PySetObject *)w)->hash != -1 &&
1826 v->hash != ((PySetObject *)w)->hash)
1827 Py_RETURN_FALSE;
1828 return set_issubset(v, w);
1829 case Py_NE:
1830 r1 = set_richcompare(v, w, Py_EQ);
1831 if (r1 == NULL)
1832 return NULL;
1833 r2 = PyBool_FromLong(PyObject_Not(r1));
1834 Py_DECREF(r1);
1835 return r2;
1836 case Py_LE:
1837 return set_issubset(v, w);
1838 case Py_GE:
1839 return set_issuperset(v, w);
1840 case Py_LT:
1841 if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))
1842 Py_RETURN_FALSE;
1843 return set_issubset(v, w);
1844 case Py_GT:
1845 if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
1846 Py_RETURN_FALSE;
1847 return set_issuperset(v, w);
1848 }
1849 Py_INCREF(Py_NotImplemented);
1850 return Py_NotImplemented;
Raymond Hettingera690a992003-11-16 16:17:49 +00001851}
1852
Raymond Hettingera690a992003-11-16 16:17:49 +00001853static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001854set_add(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001855{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001856 if (set_add_key(so, key) == -1)
1857 return NULL;
1858 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001859}
1860
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001861PyDoc_STRVAR(add_doc,
Raymond Hettingera690a992003-11-16 16:17:49 +00001862"Add an element to a set.\n\
1863\n\
1864This has no effect if the element is already present.");
1865
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001866static int
1867set_contains(PySetObject *so, PyObject *key)
1868{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001869 PyObject *tmpkey;
1870 int rv;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001871
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001872 rv = set_contains_key(so, key);
1873 if (rv == -1) {
1874 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1875 return -1;
1876 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001877 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001878 if (tmpkey == NULL)
1879 return -1;
Petri Lehtinen5acc27e2011-10-30 13:56:41 +02001880 rv = set_contains_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001881 Py_DECREF(tmpkey);
1882 }
1883 return rv;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001884}
1885
1886static PyObject *
1887set_direct_contains(PySetObject *so, PyObject *key)
1888{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001889 long result;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001890
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001891 result = set_contains(so, key);
1892 if (result == -1)
1893 return NULL;
1894 return PyBool_FromLong(result);
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001895}
1896
1897PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
1898
Raymond Hettingera690a992003-11-16 16:17:49 +00001899static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001900set_remove(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001901{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001902 PyObject *tmpkey;
1903 int rv;
Raymond Hettingerbfd334a2003-11-22 03:55:23 +00001904
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001905 rv = set_discard_key(so, key);
1906 if (rv == -1) {
1907 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1908 return NULL;
1909 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001910 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001911 if (tmpkey == NULL)
1912 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001913 rv = set_discard_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001914 Py_DECREF(tmpkey);
1915 if (rv == -1)
1916 return NULL;
1917 }
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00001918
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001919 if (rv == DISCARD_NOTFOUND) {
1920 set_key_error(key);
1921 return NULL;
1922 }
1923 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001924}
1925
1926PyDoc_STRVAR(remove_doc,
1927"Remove an element from a set; it must be a member.\n\
1928\n\
1929If the element is not a member, raise a KeyError.");
1930
1931static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001932set_discard(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001933{
Benjamin Peterson2b50a012011-10-30 14:24:44 -04001934 PyObject *tmpkey;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001935 int rv;
Raymond Hettinger0deab622003-12-13 18:53:18 +00001936
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001937 rv = set_discard_key(so, key);
1938 if (rv == -1) {
1939 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1940 return NULL;
1941 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001942 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001943 if (tmpkey == NULL)
1944 return NULL;
Petri Lehtinene0aa8032011-10-30 14:31:27 +02001945 rv = set_discard_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001946 Py_DECREF(tmpkey);
Petri Lehtinene0aa8032011-10-30 14:31:27 +02001947 if (rv == -1)
1948 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001949 }
1950 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001951}
1952
1953PyDoc_STRVAR(discard_doc,
1954"Remove an element from a set if it is a member.\n\
1955\n\
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001956If the element is not a member, do nothing.");
Raymond Hettingera690a992003-11-16 16:17:49 +00001957
1958static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001959set_reduce(PySetObject *so)
1960{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001961 PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001962
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001963 keys = PySequence_List((PyObject *)so);
1964 if (keys == NULL)
1965 goto done;
1966 args = PyTuple_Pack(1, keys);
1967 if (args == NULL)
1968 goto done;
1969 dict = PyObject_GetAttrString((PyObject *)so, "__dict__");
1970 if (dict == NULL) {
1971 PyErr_Clear();
1972 dict = Py_None;
1973 Py_INCREF(dict);
1974 }
1975 result = PyTuple_Pack(3, Py_TYPE(so), args, dict);
Raymond Hettingera690a992003-11-16 16:17:49 +00001976done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001977 Py_XDECREF(args);
1978 Py_XDECREF(keys);
1979 Py_XDECREF(dict);
1980 return result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001981}
1982
1983PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1984
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001985static PyObject *
1986set_sizeof(PySetObject *so)
1987{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001988 Py_ssize_t res;
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001989
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001990 res = sizeof(PySetObject);
1991 if (so->table != so->smalltable)
1992 res = res + (so->mask + 1) * sizeof(setentry);
1993 return PyLong_FromSsize_t(res);
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001994}
1995
1996PyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes");
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001997static int
1998set_init(PySetObject *self, PyObject *args, PyObject *kwds)
1999{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002000 PyObject *iterable = NULL;
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00002001
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002002 if (!PyAnySet_Check(self))
2003 return -1;
2004 if (PySet_Check(self) && !_PyArg_NoKeywords("set()", kwds))
2005 return -1;
2006 if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable))
2007 return -1;
2008 set_clear_internal(self);
2009 self->hash = -1;
2010 if (iterable == NULL)
2011 return 0;
2012 return set_update_internal(self, iterable);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00002013}
2014
Raymond Hettingera690a992003-11-16 16:17:49 +00002015static PySequenceMethods set_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002016 set_len, /* sq_length */
2017 0, /* sq_concat */
2018 0, /* sq_repeat */
2019 0, /* sq_item */
2020 0, /* sq_slice */
2021 0, /* sq_ass_item */
2022 0, /* sq_ass_slice */
2023 (objobjproc)set_contains, /* sq_contains */
Raymond Hettingera690a992003-11-16 16:17:49 +00002024};
2025
2026/* set object ********************************************************/
2027
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002028#ifdef Py_DEBUG
2029static PyObject *test_c_api(PySetObject *so);
2030
2031PyDoc_STRVAR(test_c_api_doc, "Exercises C API. Returns True.\n\
2032All is well if assertions don't fail.");
2033#endif
2034
Raymond Hettingera690a992003-11-16 16:17:49 +00002035static PyMethodDef set_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002036 {"add", (PyCFunction)set_add, METH_O,
2037 add_doc},
2038 {"clear", (PyCFunction)set_clear, METH_NOARGS,
2039 clear_doc},
2040 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2041 contains_doc},
2042 {"copy", (PyCFunction)set_copy, METH_NOARGS,
2043 copy_doc},
2044 {"discard", (PyCFunction)set_discard, METH_O,
2045 discard_doc},
2046 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2047 difference_doc},
2048 {"difference_update", (PyCFunction)set_difference_update, METH_VARARGS,
2049 difference_update_doc},
2050 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2051 intersection_doc},
2052 {"intersection_update",(PyCFunction)set_intersection_update_multi, METH_VARARGS,
2053 intersection_update_doc},
2054 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2055 isdisjoint_doc},
2056 {"issubset", (PyCFunction)set_issubset, METH_O,
2057 issubset_doc},
2058 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2059 issuperset_doc},
2060 {"pop", (PyCFunction)set_pop, METH_NOARGS,
2061 pop_doc},
2062 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2063 reduce_doc},
2064 {"remove", (PyCFunction)set_remove, METH_O,
2065 remove_doc},
2066 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2067 sizeof_doc},
2068 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2069 symmetric_difference_doc},
2070 {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O,
2071 symmetric_difference_update_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002072#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002073 {"test_c_api", (PyCFunction)test_c_api, METH_NOARGS,
2074 test_c_api_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002075#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002076 {"union", (PyCFunction)set_union, METH_VARARGS,
2077 union_doc},
2078 {"update", (PyCFunction)set_update, METH_VARARGS,
2079 update_doc},
2080 {NULL, NULL} /* sentinel */
Raymond Hettingera690a992003-11-16 16:17:49 +00002081};
2082
2083static PyNumberMethods set_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002084 0, /*nb_add*/
2085 (binaryfunc)set_sub, /*nb_subtract*/
2086 0, /*nb_multiply*/
2087 0, /*nb_remainder*/
2088 0, /*nb_divmod*/
2089 0, /*nb_power*/
2090 0, /*nb_negative*/
2091 0, /*nb_positive*/
2092 0, /*nb_absolute*/
2093 0, /*nb_bool*/
2094 0, /*nb_invert*/
2095 0, /*nb_lshift*/
2096 0, /*nb_rshift*/
2097 (binaryfunc)set_and, /*nb_and*/
2098 (binaryfunc)set_xor, /*nb_xor*/
2099 (binaryfunc)set_or, /*nb_or*/
2100 0, /*nb_int*/
2101 0, /*nb_reserved*/
2102 0, /*nb_float*/
2103 0, /*nb_inplace_add*/
2104 (binaryfunc)set_isub, /*nb_inplace_subtract*/
2105 0, /*nb_inplace_multiply*/
2106 0, /*nb_inplace_remainder*/
2107 0, /*nb_inplace_power*/
2108 0, /*nb_inplace_lshift*/
2109 0, /*nb_inplace_rshift*/
2110 (binaryfunc)set_iand, /*nb_inplace_and*/
2111 (binaryfunc)set_ixor, /*nb_inplace_xor*/
2112 (binaryfunc)set_ior, /*nb_inplace_or*/
Raymond Hettingera690a992003-11-16 16:17:49 +00002113};
2114
2115PyDoc_STRVAR(set_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002116"set() -> new empty set object\n\
2117set(iterable) -> new set object\n\
Raymond Hettingera690a992003-11-16 16:17:49 +00002118\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002119Build an unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00002120
2121PyTypeObject PySet_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002122 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2123 "set", /* tp_name */
2124 sizeof(PySetObject), /* tp_basicsize */
2125 0, /* tp_itemsize */
2126 /* methods */
2127 (destructor)set_dealloc, /* tp_dealloc */
2128 0, /* tp_print */
2129 0, /* tp_getattr */
2130 0, /* tp_setattr */
2131 0, /* tp_reserved */
2132 (reprfunc)set_repr, /* tp_repr */
2133 &set_as_number, /* tp_as_number */
2134 &set_as_sequence, /* tp_as_sequence */
2135 0, /* tp_as_mapping */
Georg Brandl00da4e02010-10-18 07:32:48 +00002136 PyObject_HashNotImplemented, /* tp_hash */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002137 0, /* tp_call */
2138 0, /* tp_str */
2139 PyObject_GenericGetAttr, /* tp_getattro */
2140 0, /* tp_setattro */
2141 0, /* tp_as_buffer */
2142 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2143 Py_TPFLAGS_BASETYPE, /* tp_flags */
2144 set_doc, /* tp_doc */
2145 (traverseproc)set_traverse, /* tp_traverse */
2146 (inquiry)set_clear_internal, /* tp_clear */
2147 (richcmpfunc)set_richcompare, /* tp_richcompare */
Georg Brandl00da4e02010-10-18 07:32:48 +00002148 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2149 (getiterfunc)set_iter, /* tp_iter */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002150 0, /* tp_iternext */
2151 set_methods, /* tp_methods */
2152 0, /* tp_members */
2153 0, /* tp_getset */
2154 0, /* tp_base */
2155 0, /* tp_dict */
2156 0, /* tp_descr_get */
2157 0, /* tp_descr_set */
2158 0, /* tp_dictoffset */
2159 (initproc)set_init, /* tp_init */
2160 PyType_GenericAlloc, /* tp_alloc */
2161 set_new, /* tp_new */
2162 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002163};
2164
2165/* frozenset object ********************************************************/
2166
2167
2168static PyMethodDef frozenset_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002169 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2170 contains_doc},
2171 {"copy", (PyCFunction)frozenset_copy, METH_NOARGS,
2172 copy_doc},
2173 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2174 difference_doc},
2175 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2176 intersection_doc},
2177 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2178 isdisjoint_doc},
2179 {"issubset", (PyCFunction)set_issubset, METH_O,
2180 issubset_doc},
2181 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2182 issuperset_doc},
2183 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2184 reduce_doc},
2185 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2186 sizeof_doc},
2187 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2188 symmetric_difference_doc},
2189 {"union", (PyCFunction)set_union, METH_VARARGS,
2190 union_doc},
2191 {NULL, NULL} /* sentinel */
Raymond Hettingera690a992003-11-16 16:17:49 +00002192};
2193
2194static PyNumberMethods frozenset_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002195 0, /*nb_add*/
2196 (binaryfunc)set_sub, /*nb_subtract*/
2197 0, /*nb_multiply*/
2198 0, /*nb_remainder*/
2199 0, /*nb_divmod*/
2200 0, /*nb_power*/
2201 0, /*nb_negative*/
2202 0, /*nb_positive*/
2203 0, /*nb_absolute*/
2204 0, /*nb_bool*/
2205 0, /*nb_invert*/
2206 0, /*nb_lshift*/
2207 0, /*nb_rshift*/
2208 (binaryfunc)set_and, /*nb_and*/
2209 (binaryfunc)set_xor, /*nb_xor*/
2210 (binaryfunc)set_or, /*nb_or*/
Raymond Hettingera690a992003-11-16 16:17:49 +00002211};
2212
2213PyDoc_STRVAR(frozenset_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002214"frozenset() -> empty frozenset object\n\
2215frozenset(iterable) -> frozenset object\n\
Raymond Hettingera690a992003-11-16 16:17:49 +00002216\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002217Build an immutable unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00002218
2219PyTypeObject PyFrozenSet_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002220 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2221 "frozenset", /* tp_name */
2222 sizeof(PySetObject), /* tp_basicsize */
2223 0, /* tp_itemsize */
2224 /* methods */
2225 (destructor)set_dealloc, /* tp_dealloc */
2226 0, /* tp_print */
2227 0, /* tp_getattr */
2228 0, /* tp_setattr */
2229 0, /* tp_reserved */
2230 (reprfunc)set_repr, /* tp_repr */
2231 &frozenset_as_number, /* tp_as_number */
2232 &set_as_sequence, /* tp_as_sequence */
2233 0, /* tp_as_mapping */
2234 frozenset_hash, /* tp_hash */
2235 0, /* tp_call */
2236 0, /* tp_str */
2237 PyObject_GenericGetAttr, /* tp_getattro */
2238 0, /* tp_setattro */
2239 0, /* tp_as_buffer */
2240 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2241 Py_TPFLAGS_BASETYPE, /* tp_flags */
2242 frozenset_doc, /* tp_doc */
2243 (traverseproc)set_traverse, /* tp_traverse */
2244 (inquiry)set_clear_internal, /* tp_clear */
2245 (richcmpfunc)set_richcompare, /* tp_richcompare */
2246 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2247 (getiterfunc)set_iter, /* tp_iter */
2248 0, /* tp_iternext */
2249 frozenset_methods, /* tp_methods */
2250 0, /* tp_members */
2251 0, /* tp_getset */
2252 0, /* tp_base */
2253 0, /* tp_dict */
2254 0, /* tp_descr_get */
2255 0, /* tp_descr_set */
2256 0, /* tp_dictoffset */
2257 0, /* tp_init */
2258 PyType_GenericAlloc, /* tp_alloc */
2259 frozenset_new, /* tp_new */
2260 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002261};
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002262
2263
2264/***** C API functions *************************************************/
2265
2266PyObject *
2267PySet_New(PyObject *iterable)
2268{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002269 return make_new_set(&PySet_Type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002270}
2271
2272PyObject *
2273PyFrozenSet_New(PyObject *iterable)
2274{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002275 return make_new_set(&PyFrozenSet_Type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002276}
2277
Neal Norwitz8c49c822006-03-04 18:41:19 +00002278Py_ssize_t
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002279PySet_Size(PyObject *anyset)
2280{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002281 if (!PyAnySet_Check(anyset)) {
2282 PyErr_BadInternalCall();
2283 return -1;
2284 }
2285 return PySet_GET_SIZE(anyset);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002286}
2287
2288int
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002289PySet_Clear(PyObject *set)
2290{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002291 if (!PySet_Check(set)) {
2292 PyErr_BadInternalCall();
2293 return -1;
2294 }
2295 return set_clear_internal((PySetObject *)set);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002296}
2297
2298int
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002299PySet_Contains(PyObject *anyset, PyObject *key)
2300{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002301 if (!PyAnySet_Check(anyset)) {
2302 PyErr_BadInternalCall();
2303 return -1;
2304 }
2305 return set_contains_key((PySetObject *)anyset, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002306}
2307
2308int
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002309PySet_Discard(PyObject *set, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002310{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002311 if (!PySet_Check(set)) {
2312 PyErr_BadInternalCall();
2313 return -1;
2314 }
2315 return set_discard_key((PySetObject *)set, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002316}
2317
2318int
Christian Heimesfd66e512008-01-29 12:18:50 +00002319PySet_Add(PyObject *anyset, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002320{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002321 if (!PySet_Check(anyset) &&
2322 (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
2323 PyErr_BadInternalCall();
2324 return -1;
2325 }
2326 return set_add_key((PySetObject *)anyset, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002327}
2328
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002329int
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002330_PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash)
Guido van Rossumd8faa362007-04-27 19:54:29 +00002331{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002332 setentry *entry;
Guido van Rossumd8faa362007-04-27 19:54:29 +00002333
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002334 if (!PyAnySet_Check(set)) {
2335 PyErr_BadInternalCall();
2336 return -1;
2337 }
2338 if (set_next((PySetObject *)set, pos, &entry) == 0)
2339 return 0;
2340 *key = entry->key;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002341 *hash = entry->hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002342 return 1;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002343}
2344
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002345PyObject *
2346PySet_Pop(PyObject *set)
2347{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002348 if (!PySet_Check(set)) {
2349 PyErr_BadInternalCall();
2350 return NULL;
2351 }
2352 return set_pop((PySetObject *)set);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002353}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002354
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002355int
2356_PySet_Update(PyObject *set, PyObject *iterable)
2357{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002358 if (!PySet_Check(set)) {
2359 PyErr_BadInternalCall();
2360 return -1;
2361 }
2362 return set_update_internal((PySetObject *)set, iterable);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002363}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002364
2365#ifdef Py_DEBUG
2366
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002367/* Test code to be called with any three element set.
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002368 Returns True and original set is restored. */
2369
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002370#define assertRaises(call_return_value, exception) \
2371 do { \
2372 assert(call_return_value); \
2373 assert(PyErr_ExceptionMatches(exception)); \
2374 PyErr_Clear(); \
2375 } while(0)
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002376
2377static PyObject *
2378test_c_api(PySetObject *so)
2379{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002380 Py_ssize_t count;
2381 char *s;
2382 Py_ssize_t i;
2383 PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x;
2384 PyObject *ob = (PyObject *)so;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002385 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002386 PyObject *str;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002387
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002388 /* Verify preconditions */
2389 assert(PyAnySet_Check(ob));
2390 assert(PyAnySet_CheckExact(ob));
2391 assert(!PyFrozenSet_CheckExact(ob));
Victor Stinner08b36bd2010-03-13 00:19:17 +00002392
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002393 /* so.clear(); so |= set("abc"); */
2394 str = PyUnicode_FromString("abc");
2395 if (str == NULL)
2396 return NULL;
2397 set_clear_internal(so);
2398 if (set_update_internal(so, str) == -1) {
2399 Py_DECREF(str);
2400 return NULL;
2401 }
2402 Py_DECREF(str);
Victor Stinner08b36bd2010-03-13 00:19:17 +00002403
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002404 /* Exercise type/size checks */
2405 assert(PySet_Size(ob) == 3);
2406 assert(PySet_GET_SIZE(ob) == 3);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002407
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002408 /* Raise TypeError for non-iterable constructor arguments */
2409 assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
2410 assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002411
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002412 /* Raise TypeError for unhashable key */
2413 dup = PySet_New(ob);
2414 assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
2415 assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
2416 assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002417
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002418 /* Exercise successful pop, contains, add, and discard */
2419 elem = PySet_Pop(ob);
2420 assert(PySet_Contains(ob, elem) == 0);
2421 assert(PySet_GET_SIZE(ob) == 2);
2422 assert(PySet_Add(ob, elem) == 0);
2423 assert(PySet_Contains(ob, elem) == 1);
2424 assert(PySet_GET_SIZE(ob) == 3);
2425 assert(PySet_Discard(ob, elem) == 1);
2426 assert(PySet_GET_SIZE(ob) == 2);
2427 assert(PySet_Discard(ob, elem) == 0);
2428 assert(PySet_GET_SIZE(ob) == 2);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002429
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002430 /* Exercise clear */
2431 dup2 = PySet_New(dup);
2432 assert(PySet_Clear(dup2) == 0);
2433 assert(PySet_Size(dup2) == 0);
2434 Py_DECREF(dup2);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002435
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002436 /* Raise SystemError on clear or update of frozen set */
2437 f = PyFrozenSet_New(dup);
2438 assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
2439 assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
2440 assert(PySet_Add(f, elem) == 0);
2441 Py_INCREF(f);
2442 assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
2443 Py_DECREF(f);
2444 Py_DECREF(f);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002445
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002446 /* Exercise direct iteration */
2447 i = 0, count = 0;
2448 while (_PySet_NextEntry((PyObject *)dup, &i, &x, &hash)) {
2449 s = _PyUnicode_AsString(x);
2450 assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
2451 count++;
2452 }
2453 assert(count == 3);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002454
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002455 /* Exercise updates */
2456 dup2 = PySet_New(NULL);
2457 assert(_PySet_Update(dup2, dup) == 0);
2458 assert(PySet_Size(dup2) == 3);
2459 assert(_PySet_Update(dup2, dup) == 0);
2460 assert(PySet_Size(dup2) == 3);
2461 Py_DECREF(dup2);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002462
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002463 /* Raise SystemError when self argument is not a set or frozenset. */
2464 t = PyTuple_New(0);
2465 assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
2466 assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
2467 Py_DECREF(t);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002468
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002469 /* Raise SystemError when self argument is not a set. */
2470 f = PyFrozenSet_New(dup);
2471 assert(PySet_Size(f) == 3);
2472 assert(PyFrozenSet_CheckExact(f));
2473 assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
2474 assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
2475 Py_DECREF(f);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002476
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002477 /* Raise KeyError when popping from an empty set */
2478 assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
2479 Py_DECREF(ob);
2480 assert(PySet_GET_SIZE(ob) == 0);
2481 assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002482
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002483 /* Restore the set from the copy using the PyNumber API */
2484 assert(PyNumber_InPlaceOr(ob, dup) == ob);
2485 Py_DECREF(ob);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002486
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002487 /* Verify constructors accept NULL arguments */
2488 f = PySet_New(NULL);
2489 assert(f != NULL);
2490 assert(PySet_GET_SIZE(f) == 0);
2491 Py_DECREF(f);
2492 f = PyFrozenSet_New(NULL);
2493 assert(f != NULL);
2494 assert(PyFrozenSet_CheckExact(f));
2495 assert(PySet_GET_SIZE(f) == 0);
2496 Py_DECREF(f);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002497
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002498 Py_DECREF(elem);
2499 Py_DECREF(dup);
2500 Py_RETURN_TRUE;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002501}
2502
Raymond Hettinger9bda1d62005-09-16 07:14:21 +00002503#undef assertRaises
2504
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002505#endif