blob: f789434462f9287c64bc73c037b527bf34e567e9 [file] [log] [blame]
Raymond Hettingerc991db22005-08-11 07:58:45 +00001
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002/* set object implementation
Raymond Hettingerae7b00e2013-09-07 15:05:00 -07003
Raymond Hettingera9d99362005-08-05 00:01:15 +00004 Written and maintained by Raymond D. Hettinger <python@rcn.com>
5 Derived from Lib/sets.py and Objects/dictobject.c.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00006
Raymond Hettingerbd9b2002015-01-18 16:10:30 -08007 Copyright (c) 2003-2015 Python Software Foundation.
Raymond Hettingera9d99362005-08-05 00:01:15 +00008 All rights reserved.
Raymond Hettingerae7b00e2013-09-07 15:05:00 -07009
10 The basic lookup function used by all operations.
11 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
12
13 The initial probe index is computed as hash mod the table size.
14 Subsequent probe indices are computed as explained in Objects/dictobject.c.
15
16 To improve cache locality, each probe inspects a series of consecutive
17 nearby entries before moving on to probes elsewhere in memory. This leaves
18 us with a hybrid of linear probing and open addressing. The linear probing
19 reduces the cost of hash collisions because consecutive memory accesses
20 tend to be much cheaper than scattered probes. After LINEAR_PROBES steps,
21 we then use open addressing with the upper bits from the hash value. This
22 helps break-up long chains of collisions.
23
24 All arithmetic on hash should ignore overflow.
25
26 Unlike the dictionary implementation, the lookkey functions can return
27 NULL if the rich comparison returns an error.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000028*/
29
Raymond Hettingera690a992003-11-16 16:17:49 +000030#include "Python.h"
Raymond Hettingera9d99362005-08-05 00:01:15 +000031#include "structmember.h"
Christian Heimes0ded5b52007-12-10 15:50:56 +000032#include "stringlib/eq.h"
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000033
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000034/* Object used as dummy key to fill deleted entries */
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -050035static PyObject _dummy_struct;
36
37#define dummy (&_dummy_struct)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000038
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000039
Raymond Hettinger04fd9dd2013-09-07 17:41:01 -070040/* ======================================================================== */
41/* ======= Begin logic for probing the hash table ========================= */
42
Raymond Hettinger710a67e2013-09-21 20:17:31 -070043/* Set this to zero to turn-off linear probing */
Raymond Hettinger8408dc52013-09-15 14:57:15 -070044#ifndef LINEAR_PROBES
Raymond Hettinger742d8712013-09-08 00:25:57 -070045#define LINEAR_PROBES 9
Raymond Hettinger8408dc52013-09-15 14:57:15 -070046#endif
Raymond Hettinger742d8712013-09-08 00:25:57 -070047
48/* This must be >= 1 */
49#define PERTURB_SHIFT 5
50
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000051static setentry *
Antoine Pitrou9ed5f272013-08-13 20:18:52 +020052set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000053{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000054 setentry *table = so->table;
Raymond Hettingerafe89092013-08-28 20:59:31 -070055 setentry *freeslot = NULL;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +020056 setentry *entry;
Raymond Hettingerafe89092013-08-28 20:59:31 -070057 size_t perturb = hash;
58 size_t mask = so->mask;
Raymond Hettingera35adf52013-09-02 03:23:21 -070059 size_t i = (size_t)hash; /* Unsigned for defined overflow behavior. */
Raymond Hettinger8408dc52013-09-15 14:57:15 -070060 size_t j;
Raymond Hettinger4ef05282013-09-21 15:39:49 -070061 int cmp;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000062
Raymond Hettingera35adf52013-09-02 03:23:21 -070063 entry = &table[i & mask];
Raymond Hettingerafe89092013-08-28 20:59:31 -070064 if (entry->key == NULL)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000065 return entry;
Raymond Hettinger237b34b2013-08-17 02:31:53 -070066
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -070067 while (1) {
Raymond Hettinger426d9952014-05-18 21:40:20 +010068 if (entry->hash == hash && entry->key != dummy) { /* dummy match unlikely */
Raymond Hettingerafe89092013-08-28 20:59:31 -070069 PyObject *startkey = entry->key;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -080070 if (startkey == key)
71 return entry;
Raymond Hettinger93035c42015-01-25 16:12:49 -080072 if (PyUnicode_CheckExact(startkey)
73 && PyUnicode_CheckExact(key)
74 && unicode_eq(startkey, key))
75 return entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000076 Py_INCREF(startkey);
77 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
78 Py_DECREF(startkey);
Raymond Hettinger426d9952014-05-18 21:40:20 +010079 if (cmp < 0) /* unlikely */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000080 return NULL;
Raymond Hettinger426d9952014-05-18 21:40:20 +010081 if (table != so->table || entry->key != startkey) /* unlikely */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000082 return set_lookkey(so, key, hash);
Raymond Hettinger426d9952014-05-18 21:40:20 +010083 if (cmp > 0) /* likely */
Raymond Hettingerafe89092013-08-28 20:59:31 -070084 return entry;
85 }
86 if (entry->key == dummy && freeslot == NULL)
87 freeslot = entry;
88
Raymond Hettingerc70a2b72013-09-21 14:02:55 -070089 for (j = 1 ; j <= LINEAR_PROBES ; j++) {
90 entry = &table[(i + j) & mask];
Raymond Hettingera35adf52013-09-02 03:23:21 -070091 if (entry->key == NULL)
92 goto found_null;
Raymond Hettingera35adf52013-09-02 03:23:21 -070093 if (entry->hash == hash && entry->key != dummy) {
94 PyObject *startkey = entry->key;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -080095 if (startkey == key)
96 return entry;
Raymond Hettinger93035c42015-01-25 16:12:49 -080097 if (PyUnicode_CheckExact(startkey)
98 && PyUnicode_CheckExact(key)
99 && unicode_eq(startkey, key))
100 return entry;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700101 Py_INCREF(startkey);
102 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
103 Py_DECREF(startkey);
104 if (cmp < 0)
105 return NULL;
106 if (table != so->table || entry->key != startkey)
107 return set_lookkey(so, key, hash);
108 if (cmp > 0)
109 return entry;
110 }
111 if (entry->key == dummy && freeslot == NULL)
112 freeslot = entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000113 }
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700114
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700115 perturb >>= PERTURB_SHIFT;
Raymond Hettingerc56e0e32013-09-02 16:32:27 -0700116 i = i * 5 + 1 + perturb;
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700117
Raymond Hettingera35adf52013-09-02 03:23:21 -0700118 entry = &table[i & mask];
Raymond Hettingerafe89092013-08-28 20:59:31 -0700119 if (entry->key == NULL)
Raymond Hettinger8408dc52013-09-15 14:57:15 -0700120 goto found_null;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000121 }
Raymond Hettingera35adf52013-09-02 03:23:21 -0700122 found_null:
Raymond Hettingerafe89092013-08-28 20:59:31 -0700123 return freeslot == NULL ? entry : freeslot;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000124}
125
126/*
Thomas Wouters89f507f2006-12-13 04:49:30 +0000127Internal routine used by set_table_resize() to insert an item which is
128known to be absent from the set. This routine also assumes that
129the set contains no deleted entries. Besides the performance benefit,
130using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
131Note that no refcounts are changed by this routine; if needed, the caller
132is responsible for incref'ing `key`.
133*/
134static void
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200135set_insert_clean(PySetObject *so, PyObject *key, Py_hash_t hash)
Thomas Wouters89f507f2006-12-13 04:49:30 +0000136{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000137 setentry *table = so->table;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200138 setentry *entry;
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700139 size_t perturb = hash;
140 size_t mask = (size_t)so->mask;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700141 size_t i = (size_t)hash;
142 size_t j;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000143
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700144 while (1) {
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800145 for (j = 0 ; j <= LINEAR_PROBES ; j++) {
Raymond Hettingera35adf52013-09-02 03:23:21 -0700146 entry = &table[(i + j) & mask];
147 if (entry->key == NULL)
148 goto found_null;
149 }
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700150 perturb >>= PERTURB_SHIFT;
Raymond Hettingerc56e0e32013-09-02 16:32:27 -0700151 i = i * 5 + 1 + perturb;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000152 }
Raymond Hettingera35adf52013-09-02 03:23:21 -0700153 found_null:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000154 entry->key = key;
155 entry->hash = hash;
Raymond Hettinger4ef05282013-09-21 15:39:49 -0700156 so->fill++;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000157 so->used++;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000158}
159
Raymond Hettinger04fd9dd2013-09-07 17:41:01 -0700160/* ======== End logic for probing the hash table ========================== */
161/* ======================================================================== */
162
163
164/*
165Internal routine to insert a new key into the table.
166Used by the public insert routine.
167Eats a reference to key.
168*/
169static int
170set_insert_key(PySetObject *so, PyObject *key, Py_hash_t hash)
171{
172 setentry *entry;
173
Raymond Hettinger93035c42015-01-25 16:12:49 -0800174 entry = set_lookkey(so, key, hash);
Raymond Hettinger04fd9dd2013-09-07 17:41:01 -0700175 if (entry == NULL)
176 return -1;
177 if (entry->key == NULL) {
178 /* UNUSED */
Raymond Hettinger04fd9dd2013-09-07 17:41:01 -0700179 entry->key = key;
180 entry->hash = hash;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800181 so->fill++;
Raymond Hettinger04fd9dd2013-09-07 17:41:01 -0700182 so->used++;
183 } else if (entry->key == dummy) {
184 /* DUMMY */
185 entry->key = key;
186 entry->hash = hash;
187 so->used++;
188 } else {
189 /* ACTIVE */
190 Py_DECREF(key);
191 }
192 return 0;
193}
194
Thomas Wouters89f507f2006-12-13 04:49:30 +0000195/*
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000196Restructure the table by allocating a new table and reinserting all
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000197keys again. When entries have been deleted, the new table may
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000198actually be smaller than the old one.
199*/
200static int
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000201set_table_resize(PySetObject *so, Py_ssize_t minused)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000202{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000203 Py_ssize_t newsize;
204 setentry *oldtable, *newtable, *entry;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800205 Py_ssize_t oldfill = so->fill;
206 Py_ssize_t oldused = so->used;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000207 int is_oldtable_malloced;
208 setentry small_copy[PySet_MINSIZE];
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000209
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000210 assert(minused >= 0);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000211
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000212 /* Find the smallest table size > minused. */
Raymond Hettinger426d9952014-05-18 21:40:20 +0100213 /* XXX speed-up with intrinsics */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000214 for (newsize = PySet_MINSIZE;
215 newsize <= minused && newsize > 0;
216 newsize <<= 1)
217 ;
218 if (newsize <= 0) {
219 PyErr_NoMemory();
220 return -1;
221 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000222
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000223 /* Get space for a new table. */
224 oldtable = so->table;
225 assert(oldtable != NULL);
226 is_oldtable_malloced = oldtable != so->smalltable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000227
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000228 if (newsize == PySet_MINSIZE) {
229 /* A large table is shrinking, or we can't get any smaller. */
230 newtable = so->smalltable;
231 if (newtable == oldtable) {
232 if (so->fill == so->used) {
233 /* No dummies, so no point doing anything. */
234 return 0;
235 }
236 /* We're not going to resize it, but rebuild the
237 table anyway to purge old dummy entries.
238 Subtle: This is *necessary* if fill==size,
239 as set_lookkey needs at least one virgin slot to
240 terminate failing searches. If fill < size, it's
241 merely desirable, as dummies slow searches. */
242 assert(so->fill > so->used);
243 memcpy(small_copy, oldtable, sizeof(small_copy));
244 oldtable = small_copy;
245 }
246 }
247 else {
248 newtable = PyMem_NEW(setentry, newsize);
249 if (newtable == NULL) {
250 PyErr_NoMemory();
251 return -1;
252 }
253 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000254
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000255 /* Make the set empty, using the new table. */
256 assert(newtable != oldtable);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000257 memset(newtable, 0, sizeof(setentry) * newsize);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000258 so->fill = 0;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800259 so->used = 0;
260 so->mask = newsize - 1;
261 so->table = newtable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000262
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000263 /* Copy the data over; this is refcount-neutral for active entries;
264 dummy entries aren't copied over, of course */
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800265 if (oldfill == oldused) {
266 for (entry = oldtable; oldused > 0; entry++) {
267 if (entry->key != NULL) {
268 oldused--;
269 set_insert_clean(so, entry->key, entry->hash);
270 }
271 }
272 } else {
273 for (entry = oldtable; oldused > 0; entry++) {
274 if (entry->key != NULL && entry->key != dummy) {
275 oldused--;
276 set_insert_clean(so, entry->key, entry->hash);
277 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000278 }
279 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000280
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000281 if (is_oldtable_malloced)
282 PyMem_DEL(oldtable);
283 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000284}
285
Raymond Hettingerc991db22005-08-11 07:58:45 +0000286/* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
287
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000288static int
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200289set_add_entry(PySetObject *so, setentry *entry)
Raymond Hettingerc991db22005-08-11 07:58:45 +0000290{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200291 Py_ssize_t n_used;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000292 PyObject *key = entry->key;
Éric Araujobbcfc1f2011-03-23 03:43:22 +0100293 Py_hash_t hash = entry->hash;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000294
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000295 assert(so->fill <= so->mask); /* at least one empty slot */
296 n_used = so->used;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000297 Py_INCREF(key);
Éric Araujo48049912011-03-23 02:08:07 +0100298 if (set_insert_key(so, key, hash) == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000299 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000300 return -1;
301 }
302 if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
303 return 0;
304 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettingerc991db22005-08-11 07:58:45 +0000305}
306
307static int
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200308set_add_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000309{
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800310 setentry entry;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200311 Py_hash_t hash;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000312
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000313 if (!PyUnicode_CheckExact(key) ||
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200314 (hash = ((PyASCIIObject *) key)->hash) == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000315 hash = PyObject_Hash(key);
316 if (hash == -1)
317 return -1;
318 }
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800319 entry.key = key;
320 entry.hash = hash;
321 return set_add_entry(so, &entry);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000322}
323
324#define DISCARD_NOTFOUND 0
325#define DISCARD_FOUND 1
326
327static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000328set_discard_entry(PySetObject *so, setentry *oldentry)
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800329{
330 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000331 PyObject *old_key;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000332
Raymond Hettinger93035c42015-01-25 16:12:49 -0800333 entry = set_lookkey(so, oldentry->key, oldentry->hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000334 if (entry == NULL)
335 return -1;
336 if (entry->key == NULL || entry->key == dummy)
337 return DISCARD_NOTFOUND;
338 old_key = entry->key;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000339 entry->key = dummy;
340 so->used--;
341 Py_DECREF(old_key);
342 return DISCARD_FOUND;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000343}
344
345static int
346set_discard_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000347{
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800348 setentry entry;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200349 Py_hash_t hash;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000350
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000351 assert (PyAnySet_Check(so));
Christian Heimes0ded5b52007-12-10 15:50:56 +0000352
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000353 if (!PyUnicode_CheckExact(key) ||
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200354 (hash = ((PyASCIIObject *) key)->hash) == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000355 hash = PyObject_Hash(key);
356 if (hash == -1)
357 return -1;
358 }
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800359 entry.key = key;
360 entry.hash = hash;
361 return set_discard_entry(so, &entry);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000362}
363
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700364static void
365set_empty_to_minsize(PySetObject *so)
366{
367 memset(so->smalltable, 0, sizeof(so->smalltable));
368 so->fill = 0;
369 so->used = 0;
370 so->mask = PySet_MINSIZE - 1;
371 so->table = so->smalltable;
372 so->hash = -1;
373}
374
Raymond Hettingerfe889f32005-08-06 05:43:39 +0000375static int
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000376set_clear_internal(PySetObject *so)
377{
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800378 setentry *entry;
379 setentry *table = so->table;
380 Py_ssize_t fill = so->fill;
381 Py_ssize_t used = so->used;
382 int table_is_malloced = table != so->smalltable;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000383 setentry small_copy[PySet_MINSIZE];
Raymond Hettingera580c472005-08-05 17:19:54 +0000384
Raymond Hettinger583cd032013-09-07 22:06:35 -0700385 assert (PyAnySet_Check(so));
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000386 assert(table != NULL);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000387
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000388 /* This is delicate. During the process of clearing the set,
389 * decrefs can cause the set to mutate. To avoid fatal confusion
390 * (voice of experience), we have to make the set empty before
391 * clearing the slots, and never refer to anything via so->ref while
392 * clearing.
393 */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000394 if (table_is_malloced)
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700395 set_empty_to_minsize(so);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000396
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000397 else if (fill > 0) {
398 /* It's a small table with something that needs to be cleared.
399 * Afraid the only safe way is to copy the set entries into
400 * another small table first.
401 */
402 memcpy(small_copy, table, sizeof(small_copy));
403 table = small_copy;
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700404 set_empty_to_minsize(so);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000405 }
406 /* else it's a small table that's already empty */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000407
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000408 /* Now we can finally clear things. If C had refcounts, we could
409 * assert that the refcount on table is 1 now, i.e. that this function
410 * has unique access to it, so decref side-effects can't alter it.
411 */
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800412 for (entry = table; used > 0; entry++) {
413 if (entry->key && entry->key != dummy) {
414 used--;
415 Py_DECREF(entry->key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000416 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000417 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000418
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000419 if (table_is_malloced)
420 PyMem_DEL(table);
421 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000422}
423
424/*
425 * Iterate over a set table. Use like so:
426 *
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000427 * Py_ssize_t pos;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000428 * setentry *entry;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000429 * pos = 0; # important! pos should not otherwise be changed by you
Raymond Hettingerc991db22005-08-11 07:58:45 +0000430 * while (set_next(yourset, &pos, &entry)) {
431 * Refer to borrowed reference in entry->key.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000432 * }
433 *
Raymond Hettingerc991db22005-08-11 07:58:45 +0000434 * CAUTION: In general, it isn't safe to use set_next in a loop that
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000435 * mutates the table.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000436 */
437static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000438set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000439{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000440 Py_ssize_t i;
441 Py_ssize_t mask;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200442 setentry *table;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000443
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000444 assert (PyAnySet_Check(so));
445 i = *pos_ptr;
446 assert(i >= 0);
447 table = so->table;
448 mask = so->mask;
449 while (i <= mask && (table[i].key == NULL || table[i].key == dummy))
450 i++;
451 *pos_ptr = i+1;
452 if (i > mask)
453 return 0;
454 assert(table[i].key != NULL);
455 *entry_ptr = &table[i];
456 return 1;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000457}
458
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000459static void
460set_dealloc(PySetObject *so)
461{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200462 setentry *entry;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800463 Py_ssize_t used = so->used;
464
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000465 PyObject_GC_UnTrack(so);
466 Py_TRASHCAN_SAFE_BEGIN(so)
467 if (so->weakreflist != NULL)
468 PyObject_ClearWeakRefs((PyObject *) so);
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000469
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800470 for (entry = so->table; used > 0; entry++) {
471 if (entry->key && entry->key != dummy) {
472 used--;
Raymond Hettingerfcf3b502013-08-22 08:20:31 -0700473 Py_DECREF(entry->key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000474 }
475 }
476 if (so->table != so->smalltable)
477 PyMem_DEL(so->table);
Raymond Hettinger8f8839e2013-09-07 20:26:50 -0700478 Py_TYPE(so)->tp_free(so);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000479 Py_TRASHCAN_SAFE_END(so)
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000480}
481
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000482static PyObject *
483set_repr(PySetObject *so)
484{
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200485 PyObject *result=NULL, *keys, *listrepr, *tmp;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000486 int status = Py_ReprEnter((PyObject*)so);
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000487
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000488 if (status != 0) {
489 if (status < 0)
490 return NULL;
491 return PyUnicode_FromFormat("%s(...)", Py_TYPE(so)->tp_name);
492 }
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000493
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000494 /* shortcut for the empty set */
495 if (!so->used) {
496 Py_ReprLeave((PyObject*)so);
497 return PyUnicode_FromFormat("%s()", Py_TYPE(so)->tp_name);
498 }
Georg Brandlc4996ba2006-08-28 19:37:11 +0000499
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000500 keys = PySequence_List((PyObject *)so);
501 if (keys == NULL)
502 goto done;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000503
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200504 /* repr(keys)[1:-1] */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000505 listrepr = PyObject_Repr(keys);
506 Py_DECREF(keys);
507 if (listrepr == NULL)
508 goto done;
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200509 tmp = PyUnicode_Substring(listrepr, 1, PyUnicode_GET_LENGTH(listrepr)-1);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000510 Py_DECREF(listrepr);
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200511 if (tmp == NULL)
512 goto done;
513 listrepr = tmp;
Victor Stinnera1a807b2011-05-26 14:24:30 +0200514
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200515 if (Py_TYPE(so) != &PySet_Type)
516 result = PyUnicode_FromFormat("%s({%U})",
517 Py_TYPE(so)->tp_name,
518 listrepr);
519 else
520 result = PyUnicode_FromFormat("{%U}", listrepr);
521 Py_DECREF(listrepr);
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000522done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000523 Py_ReprLeave((PyObject*)so);
524 return result;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000525}
526
Martin v. Löwis18e16552006-02-15 17:27:45 +0000527static Py_ssize_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000528set_len(PyObject *so)
529{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000530 return ((PySetObject *)so)->used;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000531}
532
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000533static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000534set_merge(PySetObject *so, PyObject *otherset)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000535{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000536 PySetObject *other;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000537 PyObject *key;
Éric Araujobbcfc1f2011-03-23 03:43:22 +0100538 Py_hash_t hash;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200539 Py_ssize_t i;
540 setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000541
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000542 assert (PyAnySet_Check(so));
543 assert (PyAnySet_Check(otherset));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000544
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000545 other = (PySetObject*)otherset;
546 if (other == so || other->used == 0)
547 /* a.update(a) or a.update({}); nothing to do */
548 return 0;
549 /* Do one big resize at the start, rather than
550 * incrementally resizing as we insert new keys. Expect
551 * that there will be no (or few) overlapping keys.
552 */
553 if ((so->fill + other->used)*3 >= (so->mask+1)*2) {
554 if (set_table_resize(so, (so->used + other->used)*2) != 0)
555 return -1;
556 }
557 for (i = 0; i <= other->mask; i++) {
558 entry = &other->table[i];
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000559 key = entry->key;
Éric Araujo48049912011-03-23 02:08:07 +0100560 hash = entry->hash;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000561 if (key != NULL &&
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -0500562 key != dummy) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000563 Py_INCREF(key);
Éric Araujo48049912011-03-23 02:08:07 +0100564 if (set_insert_key(so, key, hash) == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000565 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000566 return -1;
567 }
568 }
569 }
570 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000571}
572
573static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000574set_contains_entry(PySetObject *so, setentry *entry)
575{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000576 PyObject *key;
577 setentry *lu_entry;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000578
Raymond Hettinger93035c42015-01-25 16:12:49 -0800579 lu_entry = set_lookkey(so, entry->key, entry->hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000580 if (lu_entry == NULL)
581 return -1;
582 key = lu_entry->key;
583 return key != NULL && key != dummy;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000584}
585
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800586static int
587set_contains_key(PySetObject *so, PyObject *key)
588{
589 setentry entry;
590 Py_hash_t hash;
591
592 if (!PyUnicode_CheckExact(key) ||
593 (hash = ((PyASCIIObject *) key)->hash) == -1) {
594 hash = PyObject_Hash(key);
595 if (hash == -1)
596 return -1;
597 }
598 entry.key = key;
599 entry.hash = hash;
600 return set_contains_entry(so, &entry);
601}
602
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000603static PyObject *
604set_pop(PySetObject *so)
605{
Raymond Hettinger9cd6a782015-01-18 16:06:18 -0800606 /* Make sure the search finger is in bounds */
607 Py_ssize_t i = so->finger & so->mask;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200608 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000609 PyObject *key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000610
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000611 assert (PyAnySet_Check(so));
612 if (so->used == 0) {
613 PyErr_SetString(PyExc_KeyError, "pop from an empty set");
614 return NULL;
615 }
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000616
Raymond Hettinger1202a472015-01-18 13:12:42 -0800617 while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
618 i++;
Raymond Hettingered741d42015-01-18 21:25:15 -0800619 if (i > so->mask)
620 i = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000621 }
622 key = entry->key;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000623 entry->key = dummy;
624 so->used--;
Raymond Hettinger1202a472015-01-18 13:12:42 -0800625 so->finger = i + 1; /* next place to start */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000626 return key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000627}
628
Benjamin Petersonf10a79a2008-10-11 00:49:57 +0000629PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\
630Raises KeyError if the set is empty.");
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000631
632static int
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000633set_traverse(PySetObject *so, visitproc visit, void *arg)
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000634{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000635 Py_ssize_t pos = 0;
636 setentry *entry;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000637
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000638 while (set_next(so, &pos, &entry))
639 Py_VISIT(entry->key);
640 return 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000641}
642
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000643static Py_hash_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000644frozenset_hash(PyObject *self)
645{
Raymond Hettinger74fc8c42014-01-05 12:00:31 -0800646 /* Most of the constants in this hash algorithm are randomly choosen
647 large primes with "interesting bit patterns" and that passed
648 tests for good collision statistics on a variety of problematic
649 datasets such as:
650
651 ps = []
652 for r in range(21):
653 ps += itertools.combinations(range(20), r)
654 num_distinct_hashes = len({hash(frozenset(s)) for s in ps})
655
656 */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000657 PySetObject *so = (PySetObject *)self;
Gregory P. Smith27cbcd62012-12-10 18:15:46 -0800658 Py_uhash_t h, hash = 1927868237UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000659 setentry *entry;
660 Py_ssize_t pos = 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000661
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000662 if (so->hash != -1)
663 return so->hash;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000664
Mark Dickinson57e683e2011-09-24 18:18:40 +0100665 hash *= (Py_uhash_t)PySet_GET_SIZE(self) + 1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000666 while (set_next(so, &pos, &entry)) {
667 /* Work to increase the bit dispersion for closely spaced hash
668 values. The is important because some use cases have many
669 combinations of a small number of elements with nearby
670 hashes so that many distinct combinations collapse to only
671 a handful of distinct hash values. */
Antoine Pitroufbb1c612010-10-23 17:37:54 +0000672 h = entry->hash;
Raymond Hettinger74fc8c42014-01-05 12:00:31 -0800673 hash ^= ((h ^ 89869747UL) ^ (h << 16)) * 3644798167UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000674 }
Raymond Hettinger74fc8c42014-01-05 12:00:31 -0800675 /* Make the final result spread-out in a different pattern
Eric V. Smith6ba56652014-01-14 08:15:03 -0500676 than the algorithm for tuples or other python objects. */
Gregory P. Smithc2176e42012-12-10 18:32:53 -0800677 hash = hash * 69069U + 907133923UL;
Victor Stinner12174a52014-08-15 23:17:38 +0200678 if (hash == (Py_uhash_t)-1)
Gregory P. Smith27cbcd62012-12-10 18:15:46 -0800679 hash = 590923713UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000680 so->hash = hash;
681 return hash;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000682}
683
Raymond Hettingera9d99362005-08-05 00:01:15 +0000684/***** Set iterator type ***********************************************/
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000685
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000686typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000687 PyObject_HEAD
688 PySetObject *si_set; /* Set to NULL when iterator is exhausted */
689 Py_ssize_t si_used;
690 Py_ssize_t si_pos;
691 Py_ssize_t len;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000692} setiterobject;
693
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000694static void
695setiter_dealloc(setiterobject *si)
696{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000697 Py_XDECREF(si->si_set);
698 PyObject_GC_Del(si);
Antoine Pitrou7ddda782009-01-01 15:35:33 +0000699}
700
701static int
702setiter_traverse(setiterobject *si, visitproc visit, void *arg)
703{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000704 Py_VISIT(si->si_set);
705 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000706}
707
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000708static PyObject *
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000709setiter_len(setiterobject *si)
710{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000711 Py_ssize_t len = 0;
712 if (si->si_set != NULL && si->si_used == si->si_set->used)
713 len = si->len;
Antoine Pitrou671b4d92010-08-17 17:55:07 +0000714 return PyLong_FromSsize_t(len);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000715}
716
Armin Rigof5b3e362006-02-11 21:32:43 +0000717PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000718
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000719static PyObject *setiter_iternext(setiterobject *si);
720
721static PyObject *
722setiter_reduce(setiterobject *si)
723{
724 PyObject *list;
725 setiterobject tmp;
726
727 list = PyList_New(0);
728 if (!list)
729 return NULL;
730
Ezio Melotti0e1af282012-09-28 16:43:40 +0300731 /* copy the iterator state */
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000732 tmp = *si;
733 Py_XINCREF(tmp.si_set);
Ezio Melotti0e1af282012-09-28 16:43:40 +0300734
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000735 /* iterate the temporary into a list */
736 for(;;) {
737 PyObject *element = setiter_iternext(&tmp);
738 if (element) {
739 if (PyList_Append(list, element)) {
740 Py_DECREF(element);
741 Py_DECREF(list);
742 Py_XDECREF(tmp.si_set);
743 return NULL;
744 }
745 Py_DECREF(element);
746 } else
747 break;
748 }
749 Py_XDECREF(tmp.si_set);
750 /* check for error */
751 if (tmp.si_set != NULL) {
752 /* we have an error */
753 Py_DECREF(list);
754 return NULL;
755 }
Antoine Pitroua7013882012-04-05 00:04:20 +0200756 return Py_BuildValue("N(N)", _PyObject_GetBuiltin("iter"), list);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000757}
758
759PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
760
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000761static PyMethodDef setiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000762 {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000763 {"__reduce__", (PyCFunction)setiter_reduce, METH_NOARGS, reduce_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000764 {NULL, NULL} /* sentinel */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000765};
766
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000767static PyObject *setiter_iternext(setiterobject *si)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000768{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000769 PyObject *key;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200770 Py_ssize_t i, mask;
771 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000772 PySetObject *so = si->si_set;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000773
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000774 if (so == NULL)
775 return NULL;
776 assert (PyAnySet_Check(so));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000777
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000778 if (si->si_used != so->used) {
779 PyErr_SetString(PyExc_RuntimeError,
780 "Set changed size during iteration");
781 si->si_used = -1; /* Make this state sticky */
782 return NULL;
783 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000784
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000785 i = si->si_pos;
786 assert(i>=0);
787 entry = so->table;
788 mask = so->mask;
789 while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
790 i++;
791 si->si_pos = i+1;
792 if (i > mask)
793 goto fail;
794 si->len--;
795 key = entry[i].key;
796 Py_INCREF(key);
797 return key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000798
799fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000800 Py_DECREF(so);
801 si->si_set = NULL;
802 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000803}
804
Christian Heimesa22e8bd2007-11-29 22:35:39 +0000805PyTypeObject PySetIter_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000806 PyVarObject_HEAD_INIT(&PyType_Type, 0)
807 "set_iterator", /* tp_name */
808 sizeof(setiterobject), /* tp_basicsize */
809 0, /* tp_itemsize */
810 /* methods */
811 (destructor)setiter_dealloc, /* tp_dealloc */
812 0, /* tp_print */
813 0, /* tp_getattr */
814 0, /* tp_setattr */
815 0, /* tp_reserved */
816 0, /* tp_repr */
817 0, /* tp_as_number */
818 0, /* tp_as_sequence */
819 0, /* tp_as_mapping */
820 0, /* tp_hash */
821 0, /* tp_call */
822 0, /* tp_str */
823 PyObject_GenericGetAttr, /* tp_getattro */
824 0, /* tp_setattro */
825 0, /* tp_as_buffer */
826 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
827 0, /* tp_doc */
828 (traverseproc)setiter_traverse, /* tp_traverse */
829 0, /* tp_clear */
830 0, /* tp_richcompare */
831 0, /* tp_weaklistoffset */
832 PyObject_SelfIter, /* tp_iter */
833 (iternextfunc)setiter_iternext, /* tp_iternext */
834 setiter_methods, /* tp_methods */
835 0,
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000836};
837
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000838static PyObject *
839set_iter(PySetObject *so)
840{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000841 setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type);
842 if (si == NULL)
843 return NULL;
844 Py_INCREF(so);
845 si->si_set = so;
846 si->si_used = so->used;
847 si->si_pos = 0;
848 si->len = so->used;
849 _PyObject_GC_TRACK(si);
850 return (PyObject *)si;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000851}
852
Raymond Hettingerd7946662005-08-01 21:39:29 +0000853static int
Raymond Hettingerd7946662005-08-01 21:39:29 +0000854set_update_internal(PySetObject *so, PyObject *other)
Raymond Hettingera690a992003-11-16 16:17:49 +0000855{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000856 PyObject *key, *it;
Raymond Hettingera690a992003-11-16 16:17:49 +0000857
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000858 if (PyAnySet_Check(other))
859 return set_merge(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +0000860
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000861 if (PyDict_CheckExact(other)) {
862 PyObject *value;
863 Py_ssize_t pos = 0;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000864 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000865 Py_ssize_t dictsize = PyDict_Size(other);
Thomas Wouterscf297e42007-02-23 15:07:44 +0000866
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000867 /* Do one big resize at the start, rather than
868 * incrementally resizing as we insert new keys. Expect
869 * that there will be no (or few) overlapping keys.
870 */
871 if (dictsize == -1)
872 return -1;
873 if ((so->fill + dictsize)*3 >= (so->mask+1)*2) {
874 if (set_table_resize(so, (so->used + dictsize)*2) != 0)
875 return -1;
876 }
877 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
878 setentry an_entry;
Thomas Wouterscf297e42007-02-23 15:07:44 +0000879
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000880 an_entry.hash = hash;
881 an_entry.key = key;
882 if (set_add_entry(so, &an_entry) == -1)
883 return -1;
884 }
885 return 0;
886 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000887
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000888 it = PyObject_GetIter(other);
889 if (it == NULL)
890 return -1;
Raymond Hettingera690a992003-11-16 16:17:49 +0000891
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000892 while ((key = PyIter_Next(it)) != NULL) {
893 if (set_add_key(so, key) == -1) {
894 Py_DECREF(it);
895 Py_DECREF(key);
896 return -1;
897 }
898 Py_DECREF(key);
899 }
900 Py_DECREF(it);
901 if (PyErr_Occurred())
902 return -1;
903 return 0;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000904}
905
906static PyObject *
Georg Brandlc28e1fa2008-06-10 19:20:26 +0000907set_update(PySetObject *so, PyObject *args)
Raymond Hettingerd7946662005-08-01 21:39:29 +0000908{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000909 Py_ssize_t i;
Georg Brandlc28e1fa2008-06-10 19:20:26 +0000910
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000911 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
912 PyObject *other = PyTuple_GET_ITEM(args, i);
913 if (set_update_internal(so, other) == -1)
914 return NULL;
915 }
916 Py_RETURN_NONE;
Raymond Hettingera38123e2003-11-24 22:18:49 +0000917}
918
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000919PyDoc_STRVAR(update_doc,
Georg Brandlc28e1fa2008-06-10 19:20:26 +0000920"Update a set with the union of itself and others.");
Raymond Hettingera38123e2003-11-24 22:18:49 +0000921
Raymond Hettinger426d9952014-05-18 21:40:20 +0100922/* XXX Todo:
923 If aligned memory allocations become available, make the
924 set object 64 byte aligned so that most of the fields
925 can be retrieved or updated in a single cache line.
926*/
927
Raymond Hettingera38123e2003-11-24 22:18:49 +0000928static PyObject *
929make_new_set(PyTypeObject *type, PyObject *iterable)
930{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200931 PySetObject *so = NULL;
Raymond Hettingera38123e2003-11-24 22:18:49 +0000932
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000933 /* create PySetObject structure */
Raymond Hettinger8f8839e2013-09-07 20:26:50 -0700934 so = (PySetObject *)type->tp_alloc(type, 0);
935 if (so == NULL)
936 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000937
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700938 so->fill = 0;
939 so->used = 0;
940 so->mask = PySet_MINSIZE - 1;
941 so->table = so->smalltable;
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700942 so->hash = -1;
Raymond Hettinger1202a472015-01-18 13:12:42 -0800943 so->finger = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000944 so->weakreflist = NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +0000945
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000946 if (iterable != NULL) {
947 if (set_update_internal(so, iterable) == -1) {
948 Py_DECREF(so);
949 return NULL;
950 }
951 }
Raymond Hettingera38123e2003-11-24 22:18:49 +0000952
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000953 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +0000954}
955
Raymond Hettinger7d99f092008-11-16 11:44:54 +0000956static PyObject *
957make_new_set_basetype(PyTypeObject *type, PyObject *iterable)
958{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000959 if (type != &PySet_Type && type != &PyFrozenSet_Type) {
960 if (PyType_IsSubtype(type, &PySet_Type))
961 type = &PySet_Type;
962 else
963 type = &PyFrozenSet_Type;
964 }
965 return make_new_set(type, iterable);
Raymond Hettinger7d99f092008-11-16 11:44:54 +0000966}
967
Raymond Hettingerd7946662005-08-01 21:39:29 +0000968/* The empty frozenset is a singleton */
969static PyObject *emptyfrozenset = NULL;
970
Raymond Hettingera690a992003-11-16 16:17:49 +0000971static PyObject *
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000972frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
Raymond Hettingera690a992003-11-16 16:17:49 +0000973{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000974 PyObject *iterable = NULL, *result;
Raymond Hettingera690a992003-11-16 16:17:49 +0000975
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000976 if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds))
977 return NULL;
Georg Brandl02c42872005-08-26 06:42:30 +0000978
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000979 if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
980 return NULL;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000981
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000982 if (type != &PyFrozenSet_Type)
983 return make_new_set(type, iterable);
Raymond Hettingerd7946662005-08-01 21:39:29 +0000984
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000985 if (iterable != NULL) {
986 /* frozenset(f) is idempotent */
987 if (PyFrozenSet_CheckExact(iterable)) {
988 Py_INCREF(iterable);
989 return iterable;
990 }
991 result = make_new_set(type, iterable);
992 if (result == NULL || PySet_GET_SIZE(result))
993 return result;
994 Py_DECREF(result);
995 }
996 /* The empty frozenset is a singleton */
997 if (emptyfrozenset == NULL)
998 emptyfrozenset = make_new_set(type, NULL);
999 Py_XINCREF(emptyfrozenset);
1000 return emptyfrozenset;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001001}
1002
Antoine Pitrou093ce9c2011-12-16 11:24:27 +01001003int
1004PySet_ClearFreeList(void)
Raymond Hettingerd7946662005-08-01 21:39:29 +00001005{
Raymond Hettinger8f8839e2013-09-07 20:26:50 -07001006 return 0;
Antoine Pitrou093ce9c2011-12-16 11:24:27 +01001007}
1008
1009void
1010PySet_Fini(void)
1011{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001012 Py_CLEAR(emptyfrozenset);
Raymond Hettingera690a992003-11-16 16:17:49 +00001013}
1014
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001015static PyObject *
1016set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1017{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001018 if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds))
1019 return NULL;
1020
1021 return make_new_set(type, NULL);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001022}
1023
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001024/* set_swap_bodies() switches the contents of any two sets by moving their
1025 internal data pointers and, if needed, copying the internal smalltables.
1026 Semantically equivalent to:
1027
1028 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1029
1030 The function always succeeds and it leaves both objects in a stable state.
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001031 Useful for creating temporary frozensets from sets for membership testing
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001032 in __contains__(), discard(), and remove(). Also useful for operations
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001033 that update in-place (by allowing an intermediate result to be swapped
Raymond Hettinger9dcb17c2005-07-31 13:09:28 +00001034 into one of the original inputs).
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001035*/
1036
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001037static void
1038set_swap_bodies(PySetObject *a, PySetObject *b)
Raymond Hettingera690a992003-11-16 16:17:49 +00001039{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001040 Py_ssize_t t;
1041 setentry *u;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001042 setentry tab[PySet_MINSIZE];
Antoine Pitroufbb1c612010-10-23 17:37:54 +00001043 Py_hash_t h;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001044
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001045 t = a->fill; a->fill = b->fill; b->fill = t;
1046 t = a->used; a->used = b->used; b->used = t;
1047 t = a->mask; a->mask = b->mask; b->mask = t;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001048
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001049 u = a->table;
1050 if (a->table == a->smalltable)
1051 u = b->smalltable;
1052 a->table = b->table;
1053 if (b->table == b->smalltable)
1054 a->table = a->smalltable;
1055 b->table = u;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001056
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001057 if (a->table == a->smalltable || b->table == b->smalltable) {
1058 memcpy(tab, a->smalltable, sizeof(tab));
1059 memcpy(a->smalltable, b->smalltable, sizeof(tab));
1060 memcpy(b->smalltable, tab, sizeof(tab));
1061 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001062
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001063 if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type) &&
1064 PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) {
1065 h = a->hash; a->hash = b->hash; b->hash = h;
1066 } else {
1067 a->hash = -1;
1068 b->hash = -1;
1069 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001070}
1071
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001072static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001073set_copy(PySetObject *so)
1074{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001075 return make_new_set_basetype(Py_TYPE(so), (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001076}
1077
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001078static PyObject *
1079frozenset_copy(PySetObject *so)
1080{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001081 if (PyFrozenSet_CheckExact(so)) {
1082 Py_INCREF(so);
1083 return (PyObject *)so;
1084 }
1085 return set_copy(so);
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001086}
1087
Raymond Hettingera690a992003-11-16 16:17:49 +00001088PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
1089
1090static PyObject *
Raymond Hettingerc991db22005-08-11 07:58:45 +00001091set_clear(PySetObject *so)
1092{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001093 set_clear_internal(so);
1094 Py_RETURN_NONE;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001095}
1096
1097PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
1098
1099static PyObject *
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001100set_union(PySetObject *so, PyObject *args)
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001101{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001102 PySetObject *result;
1103 PyObject *other;
1104 Py_ssize_t i;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001105
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001106 result = (PySetObject *)set_copy(so);
1107 if (result == NULL)
1108 return NULL;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001109
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001110 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1111 other = PyTuple_GET_ITEM(args, i);
1112 if ((PyObject *)so == other)
1113 continue;
1114 if (set_update_internal(result, other) == -1) {
1115 Py_DECREF(result);
1116 return NULL;
1117 }
1118 }
1119 return (PyObject *)result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001120}
1121
1122PyDoc_STRVAR(union_doc,
1123 "Return the union of sets as a new set.\n\
1124\n\
1125(i.e. all elements that are in either set.)");
1126
1127static PyObject *
1128set_or(PySetObject *so, PyObject *other)
1129{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001130 PySetObject *result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001131
Brian Curtindfc80e32011-08-10 20:28:54 -05001132 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1133 Py_RETURN_NOTIMPLEMENTED;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001134
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001135 result = (PySetObject *)set_copy(so);
1136 if (result == NULL)
1137 return NULL;
1138 if ((PyObject *)so == other)
1139 return (PyObject *)result;
1140 if (set_update_internal(result, other) == -1) {
1141 Py_DECREF(result);
1142 return NULL;
1143 }
1144 return (PyObject *)result;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001145}
1146
Raymond Hettingera690a992003-11-16 16:17:49 +00001147static PyObject *
1148set_ior(PySetObject *so, PyObject *other)
1149{
Brian Curtindfc80e32011-08-10 20:28:54 -05001150 if (!PyAnySet_Check(other))
1151 Py_RETURN_NOTIMPLEMENTED;
1152
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001153 if (set_update_internal(so, other) == -1)
1154 return NULL;
1155 Py_INCREF(so);
1156 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001157}
1158
1159static PyObject *
1160set_intersection(PySetObject *so, PyObject *other)
1161{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001162 PySetObject *result;
1163 PyObject *key, *it, *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001164
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001165 if ((PyObject *)so == other)
1166 return set_copy(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001167
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001168 result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL);
1169 if (result == NULL)
1170 return NULL;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001171
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001172 if (PyAnySet_Check(other)) {
1173 Py_ssize_t pos = 0;
1174 setentry *entry;
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001175
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001176 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1177 tmp = (PyObject *)so;
1178 so = (PySetObject *)other;
1179 other = tmp;
1180 }
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001181
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001182 while (set_next((PySetObject *)other, &pos, &entry)) {
1183 int rv = set_contains_entry(so, entry);
1184 if (rv == -1) {
1185 Py_DECREF(result);
1186 return NULL;
1187 }
1188 if (rv) {
1189 if (set_add_entry(result, entry) == -1) {
1190 Py_DECREF(result);
1191 return NULL;
1192 }
1193 }
1194 }
1195 return (PyObject *)result;
1196 }
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001197
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001198 it = PyObject_GetIter(other);
1199 if (it == NULL) {
1200 Py_DECREF(result);
1201 return NULL;
1202 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001203
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001204 while ((key = PyIter_Next(it)) != NULL) {
1205 int rv;
1206 setentry entry;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001207 Py_hash_t hash = PyObject_Hash(key);
Thomas Wouters89f507f2006-12-13 04:49:30 +00001208
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001209 if (hash == -1) {
1210 Py_DECREF(it);
1211 Py_DECREF(result);
1212 Py_DECREF(key);
1213 return NULL;
1214 }
1215 entry.hash = hash;
1216 entry.key = key;
1217 rv = set_contains_entry(so, &entry);
1218 if (rv == -1) {
1219 Py_DECREF(it);
1220 Py_DECREF(result);
1221 Py_DECREF(key);
1222 return NULL;
1223 }
1224 if (rv) {
1225 if (set_add_entry(result, &entry) == -1) {
1226 Py_DECREF(it);
1227 Py_DECREF(result);
1228 Py_DECREF(key);
1229 return NULL;
1230 }
1231 }
1232 Py_DECREF(key);
1233 }
1234 Py_DECREF(it);
1235 if (PyErr_Occurred()) {
1236 Py_DECREF(result);
1237 return NULL;
1238 }
1239 return (PyObject *)result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001240}
1241
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001242static PyObject *
1243set_intersection_multi(PySetObject *so, PyObject *args)
1244{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001245 Py_ssize_t i;
1246 PyObject *result = (PyObject *)so;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001247
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001248 if (PyTuple_GET_SIZE(args) == 0)
1249 return set_copy(so);
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001250
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001251 Py_INCREF(so);
1252 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1253 PyObject *other = PyTuple_GET_ITEM(args, i);
1254 PyObject *newresult = set_intersection((PySetObject *)result, other);
1255 if (newresult == NULL) {
1256 Py_DECREF(result);
1257 return NULL;
1258 }
1259 Py_DECREF(result);
1260 result = newresult;
1261 }
1262 return result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001263}
1264
Raymond Hettingera690a992003-11-16 16:17:49 +00001265PyDoc_STRVAR(intersection_doc,
1266"Return the intersection of two sets as a new set.\n\
1267\n\
1268(i.e. all elements that are in both sets.)");
1269
1270static PyObject *
1271set_intersection_update(PySetObject *so, PyObject *other)
1272{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001273 PyObject *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001274
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001275 tmp = set_intersection(so, other);
1276 if (tmp == NULL)
1277 return NULL;
1278 set_swap_bodies(so, (PySetObject *)tmp);
1279 Py_DECREF(tmp);
1280 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001281}
1282
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001283static PyObject *
1284set_intersection_update_multi(PySetObject *so, PyObject *args)
1285{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001286 PyObject *tmp;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001287
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001288 tmp = set_intersection_multi(so, args);
1289 if (tmp == NULL)
1290 return NULL;
1291 set_swap_bodies(so, (PySetObject *)tmp);
1292 Py_DECREF(tmp);
1293 Py_RETURN_NONE;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001294}
1295
Raymond Hettingera690a992003-11-16 16:17:49 +00001296PyDoc_STRVAR(intersection_update_doc,
1297"Update a set with the intersection of itself and another.");
1298
1299static PyObject *
1300set_and(PySetObject *so, PyObject *other)
1301{
Brian Curtindfc80e32011-08-10 20:28:54 -05001302 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1303 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001304 return set_intersection(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001305}
1306
1307static PyObject *
1308set_iand(PySetObject *so, PyObject *other)
1309{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001310 PyObject *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001311
Brian Curtindfc80e32011-08-10 20:28:54 -05001312 if (!PyAnySet_Check(other))
1313 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001314 result = set_intersection_update(so, other);
1315 if (result == NULL)
1316 return NULL;
1317 Py_DECREF(result);
1318 Py_INCREF(so);
1319 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001320}
1321
Guido van Rossum58da9312007-11-10 23:39:45 +00001322static PyObject *
1323set_isdisjoint(PySetObject *so, PyObject *other)
1324{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001325 PyObject *key, *it, *tmp;
Guido van Rossum58da9312007-11-10 23:39:45 +00001326
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001327 if ((PyObject *)so == other) {
1328 if (PySet_GET_SIZE(so) == 0)
1329 Py_RETURN_TRUE;
1330 else
1331 Py_RETURN_FALSE;
1332 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001333
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001334 if (PyAnySet_CheckExact(other)) {
1335 Py_ssize_t pos = 0;
1336 setentry *entry;
Guido van Rossum58da9312007-11-10 23:39:45 +00001337
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001338 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1339 tmp = (PyObject *)so;
1340 so = (PySetObject *)other;
1341 other = tmp;
1342 }
1343 while (set_next((PySetObject *)other, &pos, &entry)) {
1344 int rv = set_contains_entry(so, entry);
1345 if (rv == -1)
1346 return NULL;
1347 if (rv)
1348 Py_RETURN_FALSE;
1349 }
1350 Py_RETURN_TRUE;
1351 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001352
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001353 it = PyObject_GetIter(other);
1354 if (it == NULL)
1355 return NULL;
Guido van Rossum58da9312007-11-10 23:39:45 +00001356
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001357 while ((key = PyIter_Next(it)) != NULL) {
1358 int rv;
1359 setentry entry;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001360 Py_hash_t hash = PyObject_Hash(key);
Guido van Rossum58da9312007-11-10 23:39:45 +00001361
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001362 if (hash == -1) {
1363 Py_DECREF(key);
1364 Py_DECREF(it);
1365 return NULL;
1366 }
1367 entry.hash = hash;
1368 entry.key = key;
1369 rv = set_contains_entry(so, &entry);
1370 Py_DECREF(key);
1371 if (rv == -1) {
1372 Py_DECREF(it);
1373 return NULL;
1374 }
1375 if (rv) {
1376 Py_DECREF(it);
1377 Py_RETURN_FALSE;
1378 }
1379 }
1380 Py_DECREF(it);
1381 if (PyErr_Occurred())
1382 return NULL;
1383 Py_RETURN_TRUE;
Guido van Rossum58da9312007-11-10 23:39:45 +00001384}
1385
1386PyDoc_STRVAR(isdisjoint_doc,
1387"Return True if two sets have a null intersection.");
1388
Neal Norwitz6576bd82005-11-13 18:41:28 +00001389static int
Raymond Hettingerc991db22005-08-11 07:58:45 +00001390set_difference_update_internal(PySetObject *so, PyObject *other)
1391{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001392 if ((PyObject *)so == other)
1393 return set_clear_internal(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001394
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001395 if (PyAnySet_Check(other)) {
1396 setentry *entry;
1397 Py_ssize_t pos = 0;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001398
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001399 while (set_next((PySetObject *)other, &pos, &entry))
1400 if (set_discard_entry(so, entry) == -1)
1401 return -1;
1402 } else {
1403 PyObject *key, *it;
1404 it = PyObject_GetIter(other);
1405 if (it == NULL)
1406 return -1;
1407
1408 while ((key = PyIter_Next(it)) != NULL) {
1409 if (set_discard_key(so, key) == -1) {
1410 Py_DECREF(it);
1411 Py_DECREF(key);
1412 return -1;
1413 }
1414 Py_DECREF(key);
1415 }
1416 Py_DECREF(it);
1417 if (PyErr_Occurred())
1418 return -1;
1419 }
1420 /* If more than 1/5 are dummies, then resize them away. */
1421 if ((so->fill - so->used) * 5 < so->mask)
1422 return 0;
1423 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001424}
1425
Raymond Hettingera690a992003-11-16 16:17:49 +00001426static PyObject *
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001427set_difference_update(PySetObject *so, PyObject *args)
Raymond Hettingera690a992003-11-16 16:17:49 +00001428{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001429 Py_ssize_t i;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001430
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001431 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1432 PyObject *other = PyTuple_GET_ITEM(args, i);
1433 if (set_difference_update_internal(so, other) == -1)
1434 return NULL;
1435 }
1436 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001437}
1438
1439PyDoc_STRVAR(difference_update_doc,
1440"Remove all elements of another set from this set.");
1441
1442static PyObject *
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001443set_copy_and_difference(PySetObject *so, PyObject *other)
1444{
1445 PyObject *result;
1446
1447 result = set_copy(so);
1448 if (result == NULL)
1449 return NULL;
1450 if (set_difference_update_internal((PySetObject *) result, other) != -1)
1451 return result;
1452 Py_DECREF(result);
1453 return NULL;
1454}
1455
1456static PyObject *
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001457set_difference(PySetObject *so, PyObject *other)
1458{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001459 PyObject *result;
1460 setentry *entry;
1461 Py_ssize_t pos = 0;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001462
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001463 if (!PyAnySet_Check(other) && !PyDict_CheckExact(other)) {
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001464 return set_copy_and_difference(so, other);
1465 }
1466
1467 /* If len(so) much more than len(other), it's more efficient to simply copy
1468 * so and then iterate other looking for common elements. */
1469 if ((PySet_GET_SIZE(so) >> 2) > PyObject_Size(other)) {
1470 return set_copy_and_difference(so, other);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001471 }
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001472
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001473 result = make_new_set_basetype(Py_TYPE(so), NULL);
1474 if (result == NULL)
1475 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001476
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001477 if (PyDict_CheckExact(other)) {
1478 while (set_next(so, &pos, &entry)) {
1479 setentry entrycopy;
1480 entrycopy.hash = entry->hash;
1481 entrycopy.key = entry->key;
Antoine Pitroufbb1c612010-10-23 17:37:54 +00001482 if (!_PyDict_Contains(other, entry->key, entry->hash)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001483 if (set_add_entry((PySetObject *)result, &entrycopy) == -1) {
1484 Py_DECREF(result);
1485 return NULL;
1486 }
1487 }
1488 }
1489 return result;
1490 }
1491
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001492 /* Iterate over so, checking for common elements in other. */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001493 while (set_next(so, &pos, &entry)) {
1494 int rv = set_contains_entry((PySetObject *)other, entry);
1495 if (rv == -1) {
1496 Py_DECREF(result);
1497 return NULL;
1498 }
1499 if (!rv) {
1500 if (set_add_entry((PySetObject *)result, entry) == -1) {
1501 Py_DECREF(result);
1502 return NULL;
1503 }
1504 }
1505 }
1506 return result;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001507}
1508
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001509static PyObject *
1510set_difference_multi(PySetObject *so, PyObject *args)
1511{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001512 Py_ssize_t i;
1513 PyObject *result, *other;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001514
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001515 if (PyTuple_GET_SIZE(args) == 0)
1516 return set_copy(so);
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001517
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001518 other = PyTuple_GET_ITEM(args, 0);
1519 result = set_difference(so, other);
1520 if (result == NULL)
1521 return NULL;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001522
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001523 for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) {
1524 other = PyTuple_GET_ITEM(args, i);
1525 if (set_difference_update_internal((PySetObject *)result, other) == -1) {
1526 Py_DECREF(result);
1527 return NULL;
1528 }
1529 }
1530 return result;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001531}
1532
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001533PyDoc_STRVAR(difference_doc,
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001534"Return the difference of two or more sets as a new set.\n\
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001535\n\
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001536(i.e. all elements that are in this set but not the others.)");
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001537static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001538set_sub(PySetObject *so, PyObject *other)
1539{
Brian Curtindfc80e32011-08-10 20:28:54 -05001540 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1541 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001542 return set_difference(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001543}
1544
1545static PyObject *
1546set_isub(PySetObject *so, PyObject *other)
1547{
Brian Curtindfc80e32011-08-10 20:28:54 -05001548 if (!PyAnySet_Check(other))
1549 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001550 if (set_difference_update_internal(so, other) == -1)
1551 return NULL;
1552 Py_INCREF(so);
1553 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001554}
1555
1556static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001557set_symmetric_difference_update(PySetObject *so, PyObject *other)
1558{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001559 PySetObject *otherset;
1560 PyObject *key;
1561 Py_ssize_t pos = 0;
1562 setentry *entry;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001563
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001564 if ((PyObject *)so == other)
1565 return set_clear(so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001566
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001567 if (PyDict_CheckExact(other)) {
1568 PyObject *value;
1569 int rv;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001570 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001571 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
1572 setentry an_entry;
Thomas Wouters89f507f2006-12-13 04:49:30 +00001573
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001574 Py_INCREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001575 an_entry.hash = hash;
1576 an_entry.key = key;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001577
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001578 rv = set_discard_entry(so, &an_entry);
Georg Brandl2d444492010-09-03 10:52:55 +00001579 if (rv == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001580 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001581 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001582 }
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001583 if (rv == DISCARD_NOTFOUND) {
1584 if (set_add_entry(so, &an_entry) == -1) {
1585 Py_DECREF(key);
1586 return NULL;
1587 }
1588 }
Georg Brandl2d444492010-09-03 10:52:55 +00001589 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001590 }
1591 Py_RETURN_NONE;
1592 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001593
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001594 if (PyAnySet_Check(other)) {
1595 Py_INCREF(other);
1596 otherset = (PySetObject *)other;
1597 } else {
1598 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1599 if (otherset == NULL)
1600 return NULL;
1601 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001602
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001603 while (set_next(otherset, &pos, &entry)) {
1604 int rv = set_discard_entry(so, entry);
1605 if (rv == -1) {
1606 Py_DECREF(otherset);
1607 return NULL;
1608 }
1609 if (rv == DISCARD_NOTFOUND) {
1610 if (set_add_entry(so, entry) == -1) {
1611 Py_DECREF(otherset);
1612 return NULL;
1613 }
1614 }
1615 }
1616 Py_DECREF(otherset);
1617 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001618}
1619
1620PyDoc_STRVAR(symmetric_difference_update_doc,
1621"Update a set with the symmetric difference of itself and another.");
1622
1623static PyObject *
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001624set_symmetric_difference(PySetObject *so, PyObject *other)
1625{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001626 PyObject *rv;
1627 PySetObject *otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001628
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001629 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1630 if (otherset == NULL)
1631 return NULL;
1632 rv = set_symmetric_difference_update(otherset, (PyObject *)so);
1633 if (rv == NULL)
1634 return NULL;
1635 Py_DECREF(rv);
1636 return (PyObject *)otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001637}
1638
1639PyDoc_STRVAR(symmetric_difference_doc,
1640"Return the symmetric difference of two sets as a new set.\n\
1641\n\
1642(i.e. all elements that are in exactly one of the sets.)");
1643
1644static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001645set_xor(PySetObject *so, PyObject *other)
1646{
Brian Curtindfc80e32011-08-10 20:28:54 -05001647 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1648 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001649 return set_symmetric_difference(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001650}
1651
1652static PyObject *
1653set_ixor(PySetObject *so, PyObject *other)
1654{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001655 PyObject *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001656
Brian Curtindfc80e32011-08-10 20:28:54 -05001657 if (!PyAnySet_Check(other))
1658 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001659 result = set_symmetric_difference_update(so, other);
1660 if (result == NULL)
1661 return NULL;
1662 Py_DECREF(result);
1663 Py_INCREF(so);
1664 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001665}
1666
1667static PyObject *
1668set_issubset(PySetObject *so, PyObject *other)
1669{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001670 setentry *entry;
1671 Py_ssize_t pos = 0;
Raymond Hettingera690a992003-11-16 16:17:49 +00001672
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001673 if (!PyAnySet_Check(other)) {
1674 PyObject *tmp, *result;
1675 tmp = make_new_set(&PySet_Type, other);
1676 if (tmp == NULL)
1677 return NULL;
1678 result = set_issubset(so, tmp);
1679 Py_DECREF(tmp);
1680 return result;
1681 }
1682 if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
1683 Py_RETURN_FALSE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001684
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001685 while (set_next(so, &pos, &entry)) {
1686 int rv = set_contains_entry((PySetObject *)other, entry);
1687 if (rv == -1)
1688 return NULL;
1689 if (!rv)
1690 Py_RETURN_FALSE;
1691 }
1692 Py_RETURN_TRUE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001693}
1694
1695PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
1696
1697static PyObject *
1698set_issuperset(PySetObject *so, PyObject *other)
1699{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001700 PyObject *tmp, *result;
Raymond Hettinger3fbec702003-11-21 07:56:36 +00001701
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001702 if (!PyAnySet_Check(other)) {
1703 tmp = make_new_set(&PySet_Type, other);
1704 if (tmp == NULL)
1705 return NULL;
1706 result = set_issuperset(so, tmp);
1707 Py_DECREF(tmp);
1708 return result;
1709 }
1710 return set_issubset((PySetObject *)other, (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001711}
1712
1713PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
1714
Raymond Hettingera690a992003-11-16 16:17:49 +00001715static PyObject *
1716set_richcompare(PySetObject *v, PyObject *w, int op)
1717{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001718 PyObject *r1, *r2;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001719
Brian Curtindfc80e32011-08-10 20:28:54 -05001720 if(!PyAnySet_Check(w))
1721 Py_RETURN_NOTIMPLEMENTED;
1722
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001723 switch (op) {
1724 case Py_EQ:
1725 if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
1726 Py_RETURN_FALSE;
1727 if (v->hash != -1 &&
1728 ((PySetObject *)w)->hash != -1 &&
1729 v->hash != ((PySetObject *)w)->hash)
1730 Py_RETURN_FALSE;
1731 return set_issubset(v, w);
1732 case Py_NE:
1733 r1 = set_richcompare(v, w, Py_EQ);
1734 if (r1 == NULL)
1735 return NULL;
1736 r2 = PyBool_FromLong(PyObject_Not(r1));
1737 Py_DECREF(r1);
1738 return r2;
1739 case Py_LE:
1740 return set_issubset(v, w);
1741 case Py_GE:
1742 return set_issuperset(v, w);
1743 case Py_LT:
1744 if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))
1745 Py_RETURN_FALSE;
1746 return set_issubset(v, w);
1747 case Py_GT:
1748 if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
1749 Py_RETURN_FALSE;
1750 return set_issuperset(v, w);
1751 }
Brian Curtindfc80e32011-08-10 20:28:54 -05001752 Py_RETURN_NOTIMPLEMENTED;
Raymond Hettingera690a992003-11-16 16:17:49 +00001753}
1754
Raymond Hettingera690a992003-11-16 16:17:49 +00001755static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001756set_add(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001757{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001758 if (set_add_key(so, key) == -1)
1759 return NULL;
1760 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001761}
1762
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001763PyDoc_STRVAR(add_doc,
Raymond Hettingera690a992003-11-16 16:17:49 +00001764"Add an element to a set.\n\
1765\n\
1766This has no effect if the element is already present.");
1767
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001768static int
1769set_contains(PySetObject *so, PyObject *key)
1770{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001771 PyObject *tmpkey;
1772 int rv;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001773
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001774 rv = set_contains_key(so, key);
1775 if (rv == -1) {
1776 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1777 return -1;
1778 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001779 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001780 if (tmpkey == NULL)
1781 return -1;
Petri Lehtinen5acc27e2011-10-30 13:56:41 +02001782 rv = set_contains_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001783 Py_DECREF(tmpkey);
1784 }
1785 return rv;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001786}
1787
1788static PyObject *
1789set_direct_contains(PySetObject *so, PyObject *key)
1790{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001791 long result;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001792
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001793 result = set_contains(so, key);
1794 if (result == -1)
1795 return NULL;
1796 return PyBool_FromLong(result);
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001797}
1798
1799PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
1800
Raymond Hettingera690a992003-11-16 16:17:49 +00001801static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001802set_remove(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001803{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001804 PyObject *tmpkey;
1805 int rv;
Raymond Hettingerbfd334a2003-11-22 03:55:23 +00001806
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001807 rv = set_discard_key(so, key);
1808 if (rv == -1) {
1809 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1810 return NULL;
1811 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001812 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001813 if (tmpkey == NULL)
1814 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001815 rv = set_discard_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001816 Py_DECREF(tmpkey);
1817 if (rv == -1)
1818 return NULL;
1819 }
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00001820
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001821 if (rv == DISCARD_NOTFOUND) {
Raymond Hettinger69492da2013-09-02 15:59:26 -07001822 _PyErr_SetKeyError(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001823 return NULL;
1824 }
1825 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001826}
1827
1828PyDoc_STRVAR(remove_doc,
1829"Remove an element from a set; it must be a member.\n\
1830\n\
1831If the element is not a member, raise a KeyError.");
1832
1833static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001834set_discard(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001835{
Benjamin Peterson2b50a012011-10-30 14:24:44 -04001836 PyObject *tmpkey;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001837 int rv;
Raymond Hettinger0deab622003-12-13 18:53:18 +00001838
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001839 rv = set_discard_key(so, key);
1840 if (rv == -1) {
1841 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1842 return NULL;
1843 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001844 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001845 if (tmpkey == NULL)
1846 return NULL;
Petri Lehtinene0aa8032011-10-30 14:31:27 +02001847 rv = set_discard_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001848 Py_DECREF(tmpkey);
Petri Lehtinene0aa8032011-10-30 14:31:27 +02001849 if (rv == -1)
1850 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001851 }
1852 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001853}
1854
1855PyDoc_STRVAR(discard_doc,
1856"Remove an element from a set if it is a member.\n\
1857\n\
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001858If the element is not a member, do nothing.");
Raymond Hettingera690a992003-11-16 16:17:49 +00001859
1860static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001861set_reduce(PySetObject *so)
1862{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001863 PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;
Martin v. Löwisbd928fe2011-10-14 10:20:37 +02001864 _Py_IDENTIFIER(__dict__);
Raymond Hettingera690a992003-11-16 16:17:49 +00001865
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001866 keys = PySequence_List((PyObject *)so);
1867 if (keys == NULL)
1868 goto done;
1869 args = PyTuple_Pack(1, keys);
1870 if (args == NULL)
1871 goto done;
Martin v. Löwis1ee1b6f2011-10-10 18:11:30 +02001872 dict = _PyObject_GetAttrId((PyObject *)so, &PyId___dict__);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001873 if (dict == NULL) {
1874 PyErr_Clear();
1875 dict = Py_None;
1876 Py_INCREF(dict);
1877 }
1878 result = PyTuple_Pack(3, Py_TYPE(so), args, dict);
Raymond Hettingera690a992003-11-16 16:17:49 +00001879done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001880 Py_XDECREF(args);
1881 Py_XDECREF(keys);
1882 Py_XDECREF(dict);
1883 return result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001884}
1885
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001886static PyObject *
1887set_sizeof(PySetObject *so)
1888{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001889 Py_ssize_t res;
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001890
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001891 res = sizeof(PySetObject);
1892 if (so->table != so->smalltable)
1893 res = res + (so->mask + 1) * sizeof(setentry);
1894 return PyLong_FromSsize_t(res);
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001895}
1896
1897PyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes");
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001898static int
1899set_init(PySetObject *self, PyObject *args, PyObject *kwds)
1900{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001901 PyObject *iterable = NULL;
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001902
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001903 if (!PyAnySet_Check(self))
1904 return -1;
1905 if (PySet_Check(self) && !_PyArg_NoKeywords("set()", kwds))
1906 return -1;
1907 if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable))
1908 return -1;
1909 set_clear_internal(self);
1910 self->hash = -1;
1911 if (iterable == NULL)
1912 return 0;
1913 return set_update_internal(self, iterable);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001914}
1915
Raymond Hettingera690a992003-11-16 16:17:49 +00001916static PySequenceMethods set_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001917 set_len, /* sq_length */
1918 0, /* sq_concat */
1919 0, /* sq_repeat */
1920 0, /* sq_item */
1921 0, /* sq_slice */
1922 0, /* sq_ass_item */
1923 0, /* sq_ass_slice */
1924 (objobjproc)set_contains, /* sq_contains */
Raymond Hettingera690a992003-11-16 16:17:49 +00001925};
1926
1927/* set object ********************************************************/
1928
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00001929#ifdef Py_DEBUG
1930static PyObject *test_c_api(PySetObject *so);
1931
1932PyDoc_STRVAR(test_c_api_doc, "Exercises C API. Returns True.\n\
1933All is well if assertions don't fail.");
1934#endif
1935
Raymond Hettingera690a992003-11-16 16:17:49 +00001936static PyMethodDef set_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001937 {"add", (PyCFunction)set_add, METH_O,
1938 add_doc},
1939 {"clear", (PyCFunction)set_clear, METH_NOARGS,
1940 clear_doc},
1941 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
1942 contains_doc},
1943 {"copy", (PyCFunction)set_copy, METH_NOARGS,
1944 copy_doc},
1945 {"discard", (PyCFunction)set_discard, METH_O,
1946 discard_doc},
1947 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
1948 difference_doc},
1949 {"difference_update", (PyCFunction)set_difference_update, METH_VARARGS,
1950 difference_update_doc},
1951 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
1952 intersection_doc},
1953 {"intersection_update",(PyCFunction)set_intersection_update_multi, METH_VARARGS,
1954 intersection_update_doc},
1955 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
1956 isdisjoint_doc},
1957 {"issubset", (PyCFunction)set_issubset, METH_O,
1958 issubset_doc},
1959 {"issuperset", (PyCFunction)set_issuperset, METH_O,
1960 issuperset_doc},
1961 {"pop", (PyCFunction)set_pop, METH_NOARGS,
1962 pop_doc},
1963 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
1964 reduce_doc},
1965 {"remove", (PyCFunction)set_remove, METH_O,
1966 remove_doc},
1967 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
1968 sizeof_doc},
1969 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
1970 symmetric_difference_doc},
1971 {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O,
1972 symmetric_difference_update_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00001973#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001974 {"test_c_api", (PyCFunction)test_c_api, METH_NOARGS,
1975 test_c_api_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00001976#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001977 {"union", (PyCFunction)set_union, METH_VARARGS,
1978 union_doc},
1979 {"update", (PyCFunction)set_update, METH_VARARGS,
1980 update_doc},
1981 {NULL, NULL} /* sentinel */
Raymond Hettingera690a992003-11-16 16:17:49 +00001982};
1983
1984static PyNumberMethods set_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001985 0, /*nb_add*/
1986 (binaryfunc)set_sub, /*nb_subtract*/
1987 0, /*nb_multiply*/
1988 0, /*nb_remainder*/
1989 0, /*nb_divmod*/
1990 0, /*nb_power*/
1991 0, /*nb_negative*/
1992 0, /*nb_positive*/
1993 0, /*nb_absolute*/
1994 0, /*nb_bool*/
1995 0, /*nb_invert*/
1996 0, /*nb_lshift*/
1997 0, /*nb_rshift*/
1998 (binaryfunc)set_and, /*nb_and*/
1999 (binaryfunc)set_xor, /*nb_xor*/
2000 (binaryfunc)set_or, /*nb_or*/
2001 0, /*nb_int*/
2002 0, /*nb_reserved*/
2003 0, /*nb_float*/
2004 0, /*nb_inplace_add*/
2005 (binaryfunc)set_isub, /*nb_inplace_subtract*/
2006 0, /*nb_inplace_multiply*/
2007 0, /*nb_inplace_remainder*/
2008 0, /*nb_inplace_power*/
2009 0, /*nb_inplace_lshift*/
2010 0, /*nb_inplace_rshift*/
2011 (binaryfunc)set_iand, /*nb_inplace_and*/
2012 (binaryfunc)set_ixor, /*nb_inplace_xor*/
2013 (binaryfunc)set_ior, /*nb_inplace_or*/
Raymond Hettingera690a992003-11-16 16:17:49 +00002014};
2015
2016PyDoc_STRVAR(set_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002017"set() -> new empty set object\n\
2018set(iterable) -> new set object\n\
Raymond Hettingera690a992003-11-16 16:17:49 +00002019\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002020Build an unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00002021
2022PyTypeObject PySet_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002023 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2024 "set", /* tp_name */
2025 sizeof(PySetObject), /* tp_basicsize */
2026 0, /* tp_itemsize */
2027 /* methods */
2028 (destructor)set_dealloc, /* tp_dealloc */
2029 0, /* tp_print */
2030 0, /* tp_getattr */
2031 0, /* tp_setattr */
2032 0, /* tp_reserved */
2033 (reprfunc)set_repr, /* tp_repr */
2034 &set_as_number, /* tp_as_number */
2035 &set_as_sequence, /* tp_as_sequence */
2036 0, /* tp_as_mapping */
Georg Brandl00da4e02010-10-18 07:32:48 +00002037 PyObject_HashNotImplemented, /* tp_hash */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002038 0, /* tp_call */
2039 0, /* tp_str */
2040 PyObject_GenericGetAttr, /* tp_getattro */
2041 0, /* tp_setattro */
2042 0, /* tp_as_buffer */
2043 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2044 Py_TPFLAGS_BASETYPE, /* tp_flags */
2045 set_doc, /* tp_doc */
2046 (traverseproc)set_traverse, /* tp_traverse */
2047 (inquiry)set_clear_internal, /* tp_clear */
2048 (richcmpfunc)set_richcompare, /* tp_richcompare */
Georg Brandl00da4e02010-10-18 07:32:48 +00002049 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2050 (getiterfunc)set_iter, /* tp_iter */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002051 0, /* tp_iternext */
2052 set_methods, /* tp_methods */
2053 0, /* tp_members */
2054 0, /* tp_getset */
2055 0, /* tp_base */
2056 0, /* tp_dict */
2057 0, /* tp_descr_get */
2058 0, /* tp_descr_set */
2059 0, /* tp_dictoffset */
2060 (initproc)set_init, /* tp_init */
2061 PyType_GenericAlloc, /* tp_alloc */
2062 set_new, /* tp_new */
2063 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002064};
2065
2066/* frozenset object ********************************************************/
2067
2068
2069static PyMethodDef frozenset_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002070 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2071 contains_doc},
2072 {"copy", (PyCFunction)frozenset_copy, METH_NOARGS,
2073 copy_doc},
2074 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2075 difference_doc},
2076 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2077 intersection_doc},
2078 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2079 isdisjoint_doc},
2080 {"issubset", (PyCFunction)set_issubset, METH_O,
2081 issubset_doc},
2082 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2083 issuperset_doc},
2084 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2085 reduce_doc},
2086 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2087 sizeof_doc},
2088 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2089 symmetric_difference_doc},
2090 {"union", (PyCFunction)set_union, METH_VARARGS,
2091 union_doc},
2092 {NULL, NULL} /* sentinel */
Raymond Hettingera690a992003-11-16 16:17:49 +00002093};
2094
2095static PyNumberMethods frozenset_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002096 0, /*nb_add*/
2097 (binaryfunc)set_sub, /*nb_subtract*/
2098 0, /*nb_multiply*/
2099 0, /*nb_remainder*/
2100 0, /*nb_divmod*/
2101 0, /*nb_power*/
2102 0, /*nb_negative*/
2103 0, /*nb_positive*/
2104 0, /*nb_absolute*/
2105 0, /*nb_bool*/
2106 0, /*nb_invert*/
2107 0, /*nb_lshift*/
2108 0, /*nb_rshift*/
2109 (binaryfunc)set_and, /*nb_and*/
2110 (binaryfunc)set_xor, /*nb_xor*/
2111 (binaryfunc)set_or, /*nb_or*/
Raymond Hettingera690a992003-11-16 16:17:49 +00002112};
2113
2114PyDoc_STRVAR(frozenset_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002115"frozenset() -> empty frozenset object\n\
2116frozenset(iterable) -> frozenset object\n\
Raymond Hettingera690a992003-11-16 16:17:49 +00002117\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002118Build an immutable unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00002119
2120PyTypeObject PyFrozenSet_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002121 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2122 "frozenset", /* tp_name */
2123 sizeof(PySetObject), /* tp_basicsize */
2124 0, /* tp_itemsize */
2125 /* methods */
2126 (destructor)set_dealloc, /* tp_dealloc */
2127 0, /* tp_print */
2128 0, /* tp_getattr */
2129 0, /* tp_setattr */
2130 0, /* tp_reserved */
2131 (reprfunc)set_repr, /* tp_repr */
2132 &frozenset_as_number, /* tp_as_number */
2133 &set_as_sequence, /* tp_as_sequence */
2134 0, /* tp_as_mapping */
2135 frozenset_hash, /* tp_hash */
2136 0, /* tp_call */
2137 0, /* tp_str */
2138 PyObject_GenericGetAttr, /* tp_getattro */
2139 0, /* tp_setattro */
2140 0, /* tp_as_buffer */
2141 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2142 Py_TPFLAGS_BASETYPE, /* tp_flags */
2143 frozenset_doc, /* tp_doc */
2144 (traverseproc)set_traverse, /* tp_traverse */
2145 (inquiry)set_clear_internal, /* tp_clear */
2146 (richcmpfunc)set_richcompare, /* tp_richcompare */
2147 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2148 (getiterfunc)set_iter, /* tp_iter */
2149 0, /* tp_iternext */
2150 frozenset_methods, /* tp_methods */
2151 0, /* tp_members */
2152 0, /* tp_getset */
2153 0, /* tp_base */
2154 0, /* tp_dict */
2155 0, /* tp_descr_get */
2156 0, /* tp_descr_set */
2157 0, /* tp_dictoffset */
2158 0, /* tp_init */
2159 PyType_GenericAlloc, /* tp_alloc */
2160 frozenset_new, /* tp_new */
2161 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002162};
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002163
2164
2165/***** C API functions *************************************************/
2166
2167PyObject *
2168PySet_New(PyObject *iterable)
2169{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002170 return make_new_set(&PySet_Type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002171}
2172
2173PyObject *
2174PyFrozenSet_New(PyObject *iterable)
2175{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002176 return make_new_set(&PyFrozenSet_Type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002177}
2178
Neal Norwitz8c49c822006-03-04 18:41:19 +00002179Py_ssize_t
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002180PySet_Size(PyObject *anyset)
2181{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002182 if (!PyAnySet_Check(anyset)) {
2183 PyErr_BadInternalCall();
2184 return -1;
2185 }
2186 return PySet_GET_SIZE(anyset);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002187}
2188
2189int
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002190PySet_Clear(PyObject *set)
2191{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002192 if (!PySet_Check(set)) {
2193 PyErr_BadInternalCall();
2194 return -1;
2195 }
2196 return set_clear_internal((PySetObject *)set);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002197}
2198
2199int
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002200PySet_Contains(PyObject *anyset, PyObject *key)
2201{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002202 if (!PyAnySet_Check(anyset)) {
2203 PyErr_BadInternalCall();
2204 return -1;
2205 }
2206 return set_contains_key((PySetObject *)anyset, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002207}
2208
2209int
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002210PySet_Discard(PyObject *set, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002211{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002212 if (!PySet_Check(set)) {
2213 PyErr_BadInternalCall();
2214 return -1;
2215 }
2216 return set_discard_key((PySetObject *)set, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002217}
2218
2219int
Christian Heimesfd66e512008-01-29 12:18:50 +00002220PySet_Add(PyObject *anyset, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002221{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002222 if (!PySet_Check(anyset) &&
2223 (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
2224 PyErr_BadInternalCall();
2225 return -1;
2226 }
2227 return set_add_key((PySetObject *)anyset, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002228}
2229
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002230int
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002231_PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash)
Guido van Rossumd8faa362007-04-27 19:54:29 +00002232{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002233 setentry *entry;
Guido van Rossumd8faa362007-04-27 19:54:29 +00002234
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002235 if (!PyAnySet_Check(set)) {
2236 PyErr_BadInternalCall();
2237 return -1;
2238 }
2239 if (set_next((PySetObject *)set, pos, &entry) == 0)
2240 return 0;
2241 *key = entry->key;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002242 *hash = entry->hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002243 return 1;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002244}
2245
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002246PyObject *
2247PySet_Pop(PyObject *set)
2248{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002249 if (!PySet_Check(set)) {
2250 PyErr_BadInternalCall();
2251 return NULL;
2252 }
2253 return set_pop((PySetObject *)set);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002254}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002255
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002256int
2257_PySet_Update(PyObject *set, PyObject *iterable)
2258{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002259 if (!PySet_Check(set)) {
2260 PyErr_BadInternalCall();
2261 return -1;
2262 }
2263 return set_update_internal((PySetObject *)set, iterable);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002264}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002265
Raymond Hettingere259f132013-12-15 11:56:14 -08002266/* Exported for the gdb plugin's benefit. */
2267PyObject *_PySet_Dummy = dummy;
2268
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002269#ifdef Py_DEBUG
2270
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002271/* Test code to be called with any three element set.
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002272 Returns True and original set is restored. */
2273
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002274#define assertRaises(call_return_value, exception) \
2275 do { \
2276 assert(call_return_value); \
2277 assert(PyErr_ExceptionMatches(exception)); \
2278 PyErr_Clear(); \
2279 } while(0)
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002280
2281static PyObject *
2282test_c_api(PySetObject *so)
2283{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002284 Py_ssize_t count;
2285 char *s;
2286 Py_ssize_t i;
Raymond Hettinger583cd032013-09-07 22:06:35 -07002287 PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x=NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002288 PyObject *ob = (PyObject *)so;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002289 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002290 PyObject *str;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002291
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002292 /* Verify preconditions */
2293 assert(PyAnySet_Check(ob));
2294 assert(PyAnySet_CheckExact(ob));
2295 assert(!PyFrozenSet_CheckExact(ob));
Victor Stinner08b36bd2010-03-13 00:19:17 +00002296
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002297 /* so.clear(); so |= set("abc"); */
2298 str = PyUnicode_FromString("abc");
2299 if (str == NULL)
2300 return NULL;
2301 set_clear_internal(so);
2302 if (set_update_internal(so, str) == -1) {
2303 Py_DECREF(str);
2304 return NULL;
2305 }
2306 Py_DECREF(str);
Victor Stinner08b36bd2010-03-13 00:19:17 +00002307
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002308 /* Exercise type/size checks */
2309 assert(PySet_Size(ob) == 3);
2310 assert(PySet_GET_SIZE(ob) == 3);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002311
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002312 /* Raise TypeError for non-iterable constructor arguments */
2313 assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
2314 assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002315
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002316 /* Raise TypeError for unhashable key */
2317 dup = PySet_New(ob);
2318 assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
2319 assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
2320 assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002321
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002322 /* Exercise successful pop, contains, add, and discard */
2323 elem = PySet_Pop(ob);
2324 assert(PySet_Contains(ob, elem) == 0);
2325 assert(PySet_GET_SIZE(ob) == 2);
2326 assert(PySet_Add(ob, elem) == 0);
2327 assert(PySet_Contains(ob, elem) == 1);
2328 assert(PySet_GET_SIZE(ob) == 3);
2329 assert(PySet_Discard(ob, elem) == 1);
2330 assert(PySet_GET_SIZE(ob) == 2);
2331 assert(PySet_Discard(ob, elem) == 0);
2332 assert(PySet_GET_SIZE(ob) == 2);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002333
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002334 /* Exercise clear */
2335 dup2 = PySet_New(dup);
2336 assert(PySet_Clear(dup2) == 0);
2337 assert(PySet_Size(dup2) == 0);
2338 Py_DECREF(dup2);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002339
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002340 /* Raise SystemError on clear or update of frozen set */
2341 f = PyFrozenSet_New(dup);
2342 assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
2343 assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
2344 assert(PySet_Add(f, elem) == 0);
2345 Py_INCREF(f);
2346 assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
2347 Py_DECREF(f);
2348 Py_DECREF(f);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002349
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002350 /* Exercise direct iteration */
2351 i = 0, count = 0;
2352 while (_PySet_NextEntry((PyObject *)dup, &i, &x, &hash)) {
2353 s = _PyUnicode_AsString(x);
2354 assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
2355 count++;
2356 }
2357 assert(count == 3);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002358
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002359 /* Exercise updates */
2360 dup2 = PySet_New(NULL);
2361 assert(_PySet_Update(dup2, dup) == 0);
2362 assert(PySet_Size(dup2) == 3);
2363 assert(_PySet_Update(dup2, dup) == 0);
2364 assert(PySet_Size(dup2) == 3);
2365 Py_DECREF(dup2);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002366
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002367 /* Raise SystemError when self argument is not a set or frozenset. */
2368 t = PyTuple_New(0);
2369 assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
2370 assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
2371 Py_DECREF(t);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002372
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002373 /* Raise SystemError when self argument is not a set. */
2374 f = PyFrozenSet_New(dup);
2375 assert(PySet_Size(f) == 3);
2376 assert(PyFrozenSet_CheckExact(f));
2377 assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
2378 assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
2379 Py_DECREF(f);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002380
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002381 /* Raise KeyError when popping from an empty set */
2382 assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
2383 Py_DECREF(ob);
2384 assert(PySet_GET_SIZE(ob) == 0);
2385 assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002386
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002387 /* Restore the set from the copy using the PyNumber API */
2388 assert(PyNumber_InPlaceOr(ob, dup) == ob);
2389 Py_DECREF(ob);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002390
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002391 /* Verify constructors accept NULL arguments */
2392 f = PySet_New(NULL);
2393 assert(f != NULL);
2394 assert(PySet_GET_SIZE(f) == 0);
2395 Py_DECREF(f);
2396 f = PyFrozenSet_New(NULL);
2397 assert(f != NULL);
2398 assert(PyFrozenSet_CheckExact(f));
2399 assert(PySet_GET_SIZE(f) == 0);
2400 Py_DECREF(f);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002401
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002402 Py_DECREF(elem);
2403 Py_DECREF(dup);
2404 Py_RETURN_TRUE;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002405}
2406
Raymond Hettinger9bda1d62005-09-16 07:14:21 +00002407#undef assertRaises
2408
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002409#endif
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -05002410
2411/***** Dummy Struct *************************************************/
2412
2413static PyObject *
2414dummy_repr(PyObject *op)
2415{
2416 return PyUnicode_FromString("<dummy key>");
2417}
2418
2419static void
2420dummy_dealloc(PyObject* ignore)
2421{
2422 Py_FatalError("deallocating <dummy key>");
2423}
2424
2425static PyTypeObject _PySetDummy_Type = {
2426 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2427 "<dummy key> type",
2428 0,
2429 0,
2430 dummy_dealloc, /*tp_dealloc*/ /*never called*/
2431 0, /*tp_print*/
2432 0, /*tp_getattr*/
2433 0, /*tp_setattr*/
2434 0, /*tp_reserved*/
2435 dummy_repr, /*tp_repr*/
2436 0, /*tp_as_number*/
2437 0, /*tp_as_sequence*/
2438 0, /*tp_as_mapping*/
2439 0, /*tp_hash */
2440 0, /*tp_call */
2441 0, /*tp_str */
2442 0, /*tp_getattro */
2443 0, /*tp_setattro */
2444 0, /*tp_as_buffer */
2445 Py_TPFLAGS_DEFAULT, /*tp_flags */
2446};
2447
2448static PyObject _dummy_struct = {
2449 _PyObject_EXTRA_INIT
2450 2, &_PySetDummy_Type
2451};
2452