blob: dc33a34294d0c3405244b5ee81c93c6748544d25 [file] [log] [blame]
Raymond Hettingerc991db22005-08-11 07:58:45 +00001
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002/* set object implementation
Raymond Hettingerae7b00e2013-09-07 15:05:00 -07003
Raymond Hettingera9d99362005-08-05 00:01:15 +00004 Written and maintained by Raymond D. Hettinger <python@rcn.com>
5 Derived from Lib/sets.py and Objects/dictobject.c.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00006
Raymond Hettingerbd9b2002015-01-18 16:10:30 -08007 Copyright (c) 2003-2015 Python Software Foundation.
Raymond Hettingera9d99362005-08-05 00:01:15 +00008 All rights reserved.
Raymond Hettingerae7b00e2013-09-07 15:05:00 -07009
10 The basic lookup function used by all operations.
11 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
12
13 The initial probe index is computed as hash mod the table size.
14 Subsequent probe indices are computed as explained in Objects/dictobject.c.
15
16 To improve cache locality, each probe inspects a series of consecutive
17 nearby entries before moving on to probes elsewhere in memory. This leaves
18 us with a hybrid of linear probing and open addressing. The linear probing
19 reduces the cost of hash collisions because consecutive memory accesses
20 tend to be much cheaper than scattered probes. After LINEAR_PROBES steps,
21 we then use open addressing with the upper bits from the hash value. This
22 helps break-up long chains of collisions.
23
24 All arithmetic on hash should ignore overflow.
25
Raymond Hettinger4d45c102015-01-25 16:27:40 -080026 Unlike the dictionary implementation, the lookkey function can return
Raymond Hettingerae7b00e2013-09-07 15:05:00 -070027 NULL if the rich comparison returns an error.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000028*/
29
Raymond Hettingera690a992003-11-16 16:17:49 +000030#include "Python.h"
Raymond Hettingera9d99362005-08-05 00:01:15 +000031#include "structmember.h"
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 Hettinger3037e842015-01-26 21:33:48 -0800141 size_t i = (size_t)hash & mask;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700142 size_t j;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000143
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700144 while (1) {
Raymond Hettinger3037e842015-01-26 21:33:48 -0800145 entry = &table[i];
146 if (entry->key == NULL)
147 goto found_null;
148 if (i + LINEAR_PROBES <= mask) {
149 for (j = 1; j <= LINEAR_PROBES; j++) {
150 entry = &table[i + j];
151 if (entry->key == NULL)
152 goto found_null;
153 }
154 } else {
155 for (j = 1; j <= LINEAR_PROBES; j++) {
156 entry = &table[(i + j) & mask];
157 if (entry->key == NULL)
158 goto found_null;
159 }
Raymond Hettingera35adf52013-09-02 03:23:21 -0700160 }
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700161 perturb >>= PERTURB_SHIFT;
Raymond Hettinger3037e842015-01-26 21:33:48 -0800162 i = (i * 5 + 1 + perturb) & mask;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000163 }
Raymond Hettingera35adf52013-09-02 03:23:21 -0700164 found_null:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000165 entry->key = key;
166 entry->hash = hash;
Raymond Hettinger4ef05282013-09-21 15:39:49 -0700167 so->fill++;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000168 so->used++;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000169}
170
Raymond Hettinger04fd9dd2013-09-07 17:41:01 -0700171/* ======== End logic for probing the hash table ========================== */
172/* ======================================================================== */
173
174
175/*
176Internal routine to insert a new key into the table.
177Used by the public insert routine.
178Eats a reference to key.
179*/
180static int
181set_insert_key(PySetObject *so, PyObject *key, Py_hash_t hash)
182{
183 setentry *entry;
184
Raymond Hettinger93035c42015-01-25 16:12:49 -0800185 entry = set_lookkey(so, key, hash);
Raymond Hettinger04fd9dd2013-09-07 17:41:01 -0700186 if (entry == NULL)
187 return -1;
188 if (entry->key == NULL) {
189 /* UNUSED */
Raymond Hettinger04fd9dd2013-09-07 17:41:01 -0700190 entry->key = key;
191 entry->hash = hash;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800192 so->fill++;
Raymond Hettinger04fd9dd2013-09-07 17:41:01 -0700193 so->used++;
194 } else if (entry->key == dummy) {
195 /* DUMMY */
196 entry->key = key;
197 entry->hash = hash;
198 so->used++;
199 } else {
200 /* ACTIVE */
201 Py_DECREF(key);
202 }
203 return 0;
204}
205
Thomas Wouters89f507f2006-12-13 04:49:30 +0000206/*
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000207Restructure the table by allocating a new table and reinserting all
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000208keys again. When entries have been deleted, the new table may
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000209actually be smaller than the old one.
210*/
211static int
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000212set_table_resize(PySetObject *so, Py_ssize_t minused)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000213{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000214 Py_ssize_t newsize;
215 setentry *oldtable, *newtable, *entry;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800216 Py_ssize_t oldfill = so->fill;
217 Py_ssize_t oldused = so->used;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000218 int is_oldtable_malloced;
219 setentry small_copy[PySet_MINSIZE];
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000220
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000221 assert(minused >= 0);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000222
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000223 /* Find the smallest table size > minused. */
Raymond Hettinger426d9952014-05-18 21:40:20 +0100224 /* XXX speed-up with intrinsics */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000225 for (newsize = PySet_MINSIZE;
226 newsize <= minused && newsize > 0;
227 newsize <<= 1)
228 ;
229 if (newsize <= 0) {
230 PyErr_NoMemory();
231 return -1;
232 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000233
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000234 /* Get space for a new table. */
235 oldtable = so->table;
236 assert(oldtable != NULL);
237 is_oldtable_malloced = oldtable != so->smalltable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000238
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000239 if (newsize == PySet_MINSIZE) {
240 /* A large table is shrinking, or we can't get any smaller. */
241 newtable = so->smalltable;
242 if (newtable == oldtable) {
243 if (so->fill == so->used) {
244 /* No dummies, so no point doing anything. */
245 return 0;
246 }
247 /* We're not going to resize it, but rebuild the
248 table anyway to purge old dummy entries.
249 Subtle: This is *necessary* if fill==size,
250 as set_lookkey needs at least one virgin slot to
251 terminate failing searches. If fill < size, it's
252 merely desirable, as dummies slow searches. */
253 assert(so->fill > so->used);
254 memcpy(small_copy, oldtable, sizeof(small_copy));
255 oldtable = small_copy;
256 }
257 }
258 else {
259 newtable = PyMem_NEW(setentry, newsize);
260 if (newtable == NULL) {
261 PyErr_NoMemory();
262 return -1;
263 }
264 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000265
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000266 /* Make the set empty, using the new table. */
267 assert(newtable != oldtable);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000268 memset(newtable, 0, sizeof(setentry) * newsize);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000269 so->fill = 0;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800270 so->used = 0;
271 so->mask = newsize - 1;
272 so->table = newtable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000273
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000274 /* Copy the data over; this is refcount-neutral for active entries;
275 dummy entries aren't copied over, of course */
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800276 if (oldfill == oldused) {
277 for (entry = oldtable; oldused > 0; entry++) {
278 if (entry->key != NULL) {
279 oldused--;
280 set_insert_clean(so, entry->key, entry->hash);
281 }
282 }
283 } else {
284 for (entry = oldtable; oldused > 0; entry++) {
285 if (entry->key != NULL && entry->key != dummy) {
286 oldused--;
287 set_insert_clean(so, entry->key, entry->hash);
288 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000289 }
290 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000291
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000292 if (is_oldtable_malloced)
293 PyMem_DEL(oldtable);
294 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000295}
296
Raymond Hettingerc991db22005-08-11 07:58:45 +0000297/* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
298
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000299static int
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200300set_add_entry(PySetObject *so, setentry *entry)
Raymond Hettingerc991db22005-08-11 07:58:45 +0000301{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200302 Py_ssize_t n_used;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000303 PyObject *key = entry->key;
Éric Araujobbcfc1f2011-03-23 03:43:22 +0100304 Py_hash_t hash = entry->hash;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000305
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000306 assert(so->fill <= so->mask); /* at least one empty slot */
307 n_used = so->used;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000308 Py_INCREF(key);
Éric Araujo48049912011-03-23 02:08:07 +0100309 if (set_insert_key(so, key, hash) == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000310 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000311 return -1;
312 }
313 if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
314 return 0;
315 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettingerc991db22005-08-11 07:58:45 +0000316}
317
318static int
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200319set_add_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000320{
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800321 setentry entry;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200322 Py_hash_t hash;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000323
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000324 if (!PyUnicode_CheckExact(key) ||
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200325 (hash = ((PyASCIIObject *) key)->hash) == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000326 hash = PyObject_Hash(key);
327 if (hash == -1)
328 return -1;
329 }
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800330 entry.key = key;
331 entry.hash = hash;
332 return set_add_entry(so, &entry);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000333}
334
335#define DISCARD_NOTFOUND 0
336#define DISCARD_FOUND 1
337
338static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000339set_discard_entry(PySetObject *so, setentry *oldentry)
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800340{
341 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000342 PyObject *old_key;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000343
Raymond Hettinger93035c42015-01-25 16:12:49 -0800344 entry = set_lookkey(so, oldentry->key, oldentry->hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000345 if (entry == NULL)
346 return -1;
347 if (entry->key == NULL || entry->key == dummy)
348 return DISCARD_NOTFOUND;
349 old_key = entry->key;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000350 entry->key = dummy;
Raymond Hettingerb335dfe2015-01-25 16:38:52 -0800351 entry->hash = -1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000352 so->used--;
353 Py_DECREF(old_key);
354 return DISCARD_FOUND;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000355}
356
357static int
358set_discard_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000359{
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800360 setentry entry;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200361 Py_hash_t hash;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000362
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000363 assert (PyAnySet_Check(so));
Christian Heimes0ded5b52007-12-10 15:50:56 +0000364
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000365 if (!PyUnicode_CheckExact(key) ||
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200366 (hash = ((PyASCIIObject *) key)->hash) == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000367 hash = PyObject_Hash(key);
368 if (hash == -1)
369 return -1;
370 }
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800371 entry.key = key;
372 entry.hash = hash;
373 return set_discard_entry(so, &entry);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000374}
375
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700376static void
377set_empty_to_minsize(PySetObject *so)
378{
379 memset(so->smalltable, 0, sizeof(so->smalltable));
380 so->fill = 0;
381 so->used = 0;
382 so->mask = PySet_MINSIZE - 1;
383 so->table = so->smalltable;
384 so->hash = -1;
385}
386
Raymond Hettingerfe889f32005-08-06 05:43:39 +0000387static int
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000388set_clear_internal(PySetObject *so)
389{
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800390 setentry *entry;
391 setentry *table = so->table;
392 Py_ssize_t fill = so->fill;
393 Py_ssize_t used = so->used;
394 int table_is_malloced = table != so->smalltable;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000395 setentry small_copy[PySet_MINSIZE];
Raymond Hettingera580c472005-08-05 17:19:54 +0000396
Raymond Hettinger583cd032013-09-07 22:06:35 -0700397 assert (PyAnySet_Check(so));
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000398 assert(table != NULL);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000399
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000400 /* This is delicate. During the process of clearing the set,
401 * decrefs can cause the set to mutate. To avoid fatal confusion
402 * (voice of experience), we have to make the set empty before
403 * clearing the slots, and never refer to anything via so->ref while
404 * clearing.
405 */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000406 if (table_is_malloced)
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700407 set_empty_to_minsize(so);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000408
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000409 else if (fill > 0) {
410 /* It's a small table with something that needs to be cleared.
411 * Afraid the only safe way is to copy the set entries into
412 * another small table first.
413 */
414 memcpy(small_copy, table, sizeof(small_copy));
415 table = small_copy;
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700416 set_empty_to_minsize(so);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000417 }
418 /* else it's a small table that's already empty */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000419
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000420 /* Now we can finally clear things. If C had refcounts, we could
421 * assert that the refcount on table is 1 now, i.e. that this function
422 * has unique access to it, so decref side-effects can't alter it.
423 */
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800424 for (entry = table; used > 0; entry++) {
425 if (entry->key && entry->key != dummy) {
426 used--;
427 Py_DECREF(entry->key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000428 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000429 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000430
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000431 if (table_is_malloced)
432 PyMem_DEL(table);
433 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000434}
435
436/*
437 * Iterate over a set table. Use like so:
438 *
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000439 * Py_ssize_t pos;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000440 * setentry *entry;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000441 * pos = 0; # important! pos should not otherwise be changed by you
Raymond Hettingerc991db22005-08-11 07:58:45 +0000442 * while (set_next(yourset, &pos, &entry)) {
443 * Refer to borrowed reference in entry->key.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000444 * }
445 *
Raymond Hettingerc991db22005-08-11 07:58:45 +0000446 * CAUTION: In general, it isn't safe to use set_next in a loop that
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000447 * mutates the table.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000448 */
449static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000450set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000451{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000452 Py_ssize_t i;
453 Py_ssize_t mask;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200454 setentry *table;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000455
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000456 assert (PyAnySet_Check(so));
457 i = *pos_ptr;
458 assert(i >= 0);
459 table = so->table;
460 mask = so->mask;
461 while (i <= mask && (table[i].key == NULL || table[i].key == dummy))
462 i++;
463 *pos_ptr = i+1;
464 if (i > mask)
465 return 0;
466 assert(table[i].key != NULL);
467 *entry_ptr = &table[i];
468 return 1;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000469}
470
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000471static void
472set_dealloc(PySetObject *so)
473{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200474 setentry *entry;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800475 Py_ssize_t used = so->used;
476
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000477 PyObject_GC_UnTrack(so);
478 Py_TRASHCAN_SAFE_BEGIN(so)
479 if (so->weakreflist != NULL)
480 PyObject_ClearWeakRefs((PyObject *) so);
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000481
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800482 for (entry = so->table; used > 0; entry++) {
483 if (entry->key && entry->key != dummy) {
484 used--;
Raymond Hettingerfcf3b502013-08-22 08:20:31 -0700485 Py_DECREF(entry->key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000486 }
487 }
488 if (so->table != so->smalltable)
489 PyMem_DEL(so->table);
Raymond Hettinger8f8839e2013-09-07 20:26:50 -0700490 Py_TYPE(so)->tp_free(so);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000491 Py_TRASHCAN_SAFE_END(so)
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000492}
493
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000494static PyObject *
495set_repr(PySetObject *so)
496{
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200497 PyObject *result=NULL, *keys, *listrepr, *tmp;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000498 int status = Py_ReprEnter((PyObject*)so);
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000499
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000500 if (status != 0) {
501 if (status < 0)
502 return NULL;
503 return PyUnicode_FromFormat("%s(...)", Py_TYPE(so)->tp_name);
504 }
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000505
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000506 /* shortcut for the empty set */
507 if (!so->used) {
508 Py_ReprLeave((PyObject*)so);
509 return PyUnicode_FromFormat("%s()", Py_TYPE(so)->tp_name);
510 }
Georg Brandlc4996ba2006-08-28 19:37:11 +0000511
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000512 keys = PySequence_List((PyObject *)so);
513 if (keys == NULL)
514 goto done;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000515
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200516 /* repr(keys)[1:-1] */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000517 listrepr = PyObject_Repr(keys);
518 Py_DECREF(keys);
519 if (listrepr == NULL)
520 goto done;
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200521 tmp = PyUnicode_Substring(listrepr, 1, PyUnicode_GET_LENGTH(listrepr)-1);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000522 Py_DECREF(listrepr);
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200523 if (tmp == NULL)
524 goto done;
525 listrepr = tmp;
Victor Stinnera1a807b2011-05-26 14:24:30 +0200526
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200527 if (Py_TYPE(so) != &PySet_Type)
528 result = PyUnicode_FromFormat("%s({%U})",
529 Py_TYPE(so)->tp_name,
530 listrepr);
531 else
532 result = PyUnicode_FromFormat("{%U}", listrepr);
533 Py_DECREF(listrepr);
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000534done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000535 Py_ReprLeave((PyObject*)so);
536 return result;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000537}
538
Martin v. Löwis18e16552006-02-15 17:27:45 +0000539static Py_ssize_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000540set_len(PyObject *so)
541{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000542 return ((PySetObject *)so)->used;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000543}
544
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000545static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000546set_merge(PySetObject *so, PyObject *otherset)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000547{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000548 PySetObject *other;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000549 PyObject *key;
Éric Araujobbcfc1f2011-03-23 03:43:22 +0100550 Py_hash_t hash;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200551 Py_ssize_t i;
552 setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000553
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000554 assert (PyAnySet_Check(so));
555 assert (PyAnySet_Check(otherset));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000556
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000557 other = (PySetObject*)otherset;
558 if (other == so || other->used == 0)
559 /* a.update(a) or a.update({}); nothing to do */
560 return 0;
561 /* Do one big resize at the start, rather than
562 * incrementally resizing as we insert new keys. Expect
563 * that there will be no (or few) overlapping keys.
564 */
565 if ((so->fill + other->used)*3 >= (so->mask+1)*2) {
566 if (set_table_resize(so, (so->used + other->used)*2) != 0)
567 return -1;
568 }
569 for (i = 0; i <= other->mask; i++) {
570 entry = &other->table[i];
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000571 key = entry->key;
Éric Araujo48049912011-03-23 02:08:07 +0100572 hash = entry->hash;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000573 if (key != NULL &&
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -0500574 key != dummy) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000575 Py_INCREF(key);
Éric Araujo48049912011-03-23 02:08:07 +0100576 if (set_insert_key(so, key, hash) == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000577 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000578 return -1;
579 }
580 }
581 }
582 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000583}
584
585static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000586set_contains_entry(PySetObject *so, setentry *entry)
587{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000588 PyObject *key;
589 setentry *lu_entry;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000590
Raymond Hettinger93035c42015-01-25 16:12:49 -0800591 lu_entry = set_lookkey(so, entry->key, entry->hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000592 if (lu_entry == NULL)
593 return -1;
594 key = lu_entry->key;
595 return key != NULL && key != dummy;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000596}
597
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800598static int
599set_contains_key(PySetObject *so, PyObject *key)
600{
601 setentry entry;
602 Py_hash_t hash;
603
604 if (!PyUnicode_CheckExact(key) ||
605 (hash = ((PyASCIIObject *) key)->hash) == -1) {
606 hash = PyObject_Hash(key);
607 if (hash == -1)
608 return -1;
609 }
610 entry.key = key;
611 entry.hash = hash;
612 return set_contains_entry(so, &entry);
613}
614
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000615static PyObject *
616set_pop(PySetObject *so)
617{
Raymond Hettinger9cd6a782015-01-18 16:06:18 -0800618 /* Make sure the search finger is in bounds */
619 Py_ssize_t i = so->finger & so->mask;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200620 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000621 PyObject *key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000622
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000623 assert (PyAnySet_Check(so));
624 if (so->used == 0) {
625 PyErr_SetString(PyExc_KeyError, "pop from an empty set");
626 return NULL;
627 }
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000628
Raymond Hettinger1202a472015-01-18 13:12:42 -0800629 while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
630 i++;
Raymond Hettingered741d42015-01-18 21:25:15 -0800631 if (i > so->mask)
632 i = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000633 }
634 key = entry->key;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000635 entry->key = dummy;
Raymond Hettingerb335dfe2015-01-25 16:38:52 -0800636 entry->hash = -1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000637 so->used--;
Raymond Hettinger1202a472015-01-18 13:12:42 -0800638 so->finger = i + 1; /* next place to start */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000639 return key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000640}
641
Benjamin Petersonf10a79a2008-10-11 00:49:57 +0000642PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\
643Raises KeyError if the set is empty.");
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000644
645static int
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000646set_traverse(PySetObject *so, visitproc visit, void *arg)
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000647{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000648 Py_ssize_t pos = 0;
649 setentry *entry;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000650
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000651 while (set_next(so, &pos, &entry))
652 Py_VISIT(entry->key);
653 return 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000654}
655
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000656static Py_hash_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000657frozenset_hash(PyObject *self)
658{
Raymond Hettinger74fc8c42014-01-05 12:00:31 -0800659 /* Most of the constants in this hash algorithm are randomly choosen
660 large primes with "interesting bit patterns" and that passed
661 tests for good collision statistics on a variety of problematic
662 datasets such as:
663
664 ps = []
665 for r in range(21):
666 ps += itertools.combinations(range(20), r)
667 num_distinct_hashes = len({hash(frozenset(s)) for s in ps})
668
669 */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000670 PySetObject *so = (PySetObject *)self;
Gregory P. Smith27cbcd62012-12-10 18:15:46 -0800671 Py_uhash_t h, hash = 1927868237UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000672 setentry *entry;
673 Py_ssize_t pos = 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000674
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000675 if (so->hash != -1)
676 return so->hash;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000677
Mark Dickinson57e683e2011-09-24 18:18:40 +0100678 hash *= (Py_uhash_t)PySet_GET_SIZE(self) + 1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000679 while (set_next(so, &pos, &entry)) {
680 /* Work to increase the bit dispersion for closely spaced hash
681 values. The is important because some use cases have many
682 combinations of a small number of elements with nearby
683 hashes so that many distinct combinations collapse to only
684 a handful of distinct hash values. */
Antoine Pitroufbb1c612010-10-23 17:37:54 +0000685 h = entry->hash;
Raymond Hettinger74fc8c42014-01-05 12:00:31 -0800686 hash ^= ((h ^ 89869747UL) ^ (h << 16)) * 3644798167UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000687 }
Raymond Hettinger74fc8c42014-01-05 12:00:31 -0800688 /* Make the final result spread-out in a different pattern
Eric V. Smith6ba56652014-01-14 08:15:03 -0500689 than the algorithm for tuples or other python objects. */
Gregory P. Smithc2176e42012-12-10 18:32:53 -0800690 hash = hash * 69069U + 907133923UL;
Victor Stinner12174a52014-08-15 23:17:38 +0200691 if (hash == (Py_uhash_t)-1)
Gregory P. Smith27cbcd62012-12-10 18:15:46 -0800692 hash = 590923713UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000693 so->hash = hash;
694 return hash;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000695}
696
Raymond Hettingera9d99362005-08-05 00:01:15 +0000697/***** Set iterator type ***********************************************/
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000698
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000699typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000700 PyObject_HEAD
701 PySetObject *si_set; /* Set to NULL when iterator is exhausted */
702 Py_ssize_t si_used;
703 Py_ssize_t si_pos;
704 Py_ssize_t len;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000705} setiterobject;
706
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000707static void
708setiter_dealloc(setiterobject *si)
709{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000710 Py_XDECREF(si->si_set);
711 PyObject_GC_Del(si);
Antoine Pitrou7ddda782009-01-01 15:35:33 +0000712}
713
714static int
715setiter_traverse(setiterobject *si, visitproc visit, void *arg)
716{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000717 Py_VISIT(si->si_set);
718 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000719}
720
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000721static PyObject *
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000722setiter_len(setiterobject *si)
723{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000724 Py_ssize_t len = 0;
725 if (si->si_set != NULL && si->si_used == si->si_set->used)
726 len = si->len;
Antoine Pitrou671b4d92010-08-17 17:55:07 +0000727 return PyLong_FromSsize_t(len);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000728}
729
Armin Rigof5b3e362006-02-11 21:32:43 +0000730PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000731
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000732static PyObject *setiter_iternext(setiterobject *si);
733
734static PyObject *
735setiter_reduce(setiterobject *si)
736{
737 PyObject *list;
738 setiterobject tmp;
739
740 list = PyList_New(0);
741 if (!list)
742 return NULL;
743
Ezio Melotti0e1af282012-09-28 16:43:40 +0300744 /* copy the iterator state */
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000745 tmp = *si;
746 Py_XINCREF(tmp.si_set);
Ezio Melotti0e1af282012-09-28 16:43:40 +0300747
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000748 /* iterate the temporary into a list */
749 for(;;) {
750 PyObject *element = setiter_iternext(&tmp);
751 if (element) {
752 if (PyList_Append(list, element)) {
753 Py_DECREF(element);
754 Py_DECREF(list);
755 Py_XDECREF(tmp.si_set);
756 return NULL;
757 }
758 Py_DECREF(element);
759 } else
760 break;
761 }
762 Py_XDECREF(tmp.si_set);
763 /* check for error */
764 if (tmp.si_set != NULL) {
765 /* we have an error */
766 Py_DECREF(list);
767 return NULL;
768 }
Antoine Pitroua7013882012-04-05 00:04:20 +0200769 return Py_BuildValue("N(N)", _PyObject_GetBuiltin("iter"), list);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000770}
771
772PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
773
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000774static PyMethodDef setiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000775 {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000776 {"__reduce__", (PyCFunction)setiter_reduce, METH_NOARGS, reduce_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000777 {NULL, NULL} /* sentinel */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000778};
779
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000780static PyObject *setiter_iternext(setiterobject *si)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000781{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000782 PyObject *key;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200783 Py_ssize_t i, mask;
784 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000785 PySetObject *so = si->si_set;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000786
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000787 if (so == NULL)
788 return NULL;
789 assert (PyAnySet_Check(so));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000790
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000791 if (si->si_used != so->used) {
792 PyErr_SetString(PyExc_RuntimeError,
793 "Set changed size during iteration");
794 si->si_used = -1; /* Make this state sticky */
795 return NULL;
796 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000797
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000798 i = si->si_pos;
799 assert(i>=0);
800 entry = so->table;
801 mask = so->mask;
802 while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
803 i++;
804 si->si_pos = i+1;
805 if (i > mask)
806 goto fail;
807 si->len--;
808 key = entry[i].key;
809 Py_INCREF(key);
810 return key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000811
812fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000813 Py_DECREF(so);
814 si->si_set = NULL;
815 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000816}
817
Christian Heimesa22e8bd2007-11-29 22:35:39 +0000818PyTypeObject PySetIter_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000819 PyVarObject_HEAD_INIT(&PyType_Type, 0)
820 "set_iterator", /* tp_name */
821 sizeof(setiterobject), /* tp_basicsize */
822 0, /* tp_itemsize */
823 /* methods */
824 (destructor)setiter_dealloc, /* tp_dealloc */
825 0, /* tp_print */
826 0, /* tp_getattr */
827 0, /* tp_setattr */
828 0, /* tp_reserved */
829 0, /* tp_repr */
830 0, /* tp_as_number */
831 0, /* tp_as_sequence */
832 0, /* tp_as_mapping */
833 0, /* tp_hash */
834 0, /* tp_call */
835 0, /* tp_str */
836 PyObject_GenericGetAttr, /* tp_getattro */
837 0, /* tp_setattro */
838 0, /* tp_as_buffer */
839 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
840 0, /* tp_doc */
841 (traverseproc)setiter_traverse, /* tp_traverse */
842 0, /* tp_clear */
843 0, /* tp_richcompare */
844 0, /* tp_weaklistoffset */
845 PyObject_SelfIter, /* tp_iter */
846 (iternextfunc)setiter_iternext, /* tp_iternext */
847 setiter_methods, /* tp_methods */
848 0,
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000849};
850
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000851static PyObject *
852set_iter(PySetObject *so)
853{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000854 setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type);
855 if (si == NULL)
856 return NULL;
857 Py_INCREF(so);
858 si->si_set = so;
859 si->si_used = so->used;
860 si->si_pos = 0;
861 si->len = so->used;
862 _PyObject_GC_TRACK(si);
863 return (PyObject *)si;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000864}
865
Raymond Hettingerd7946662005-08-01 21:39:29 +0000866static int
Raymond Hettingerd7946662005-08-01 21:39:29 +0000867set_update_internal(PySetObject *so, PyObject *other)
Raymond Hettingera690a992003-11-16 16:17:49 +0000868{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000869 PyObject *key, *it;
Raymond Hettingera690a992003-11-16 16:17:49 +0000870
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000871 if (PyAnySet_Check(other))
872 return set_merge(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +0000873
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000874 if (PyDict_CheckExact(other)) {
875 PyObject *value;
876 Py_ssize_t pos = 0;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000877 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000878 Py_ssize_t dictsize = PyDict_Size(other);
Thomas Wouterscf297e42007-02-23 15:07:44 +0000879
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000880 /* Do one big resize at the start, rather than
881 * incrementally resizing as we insert new keys. Expect
882 * that there will be no (or few) overlapping keys.
883 */
884 if (dictsize == -1)
885 return -1;
886 if ((so->fill + dictsize)*3 >= (so->mask+1)*2) {
887 if (set_table_resize(so, (so->used + dictsize)*2) != 0)
888 return -1;
889 }
890 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
891 setentry an_entry;
Thomas Wouterscf297e42007-02-23 15:07:44 +0000892
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000893 an_entry.hash = hash;
894 an_entry.key = key;
895 if (set_add_entry(so, &an_entry) == -1)
896 return -1;
897 }
898 return 0;
899 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000900
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000901 it = PyObject_GetIter(other);
902 if (it == NULL)
903 return -1;
Raymond Hettingera690a992003-11-16 16:17:49 +0000904
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000905 while ((key = PyIter_Next(it)) != NULL) {
906 if (set_add_key(so, key) == -1) {
907 Py_DECREF(it);
908 Py_DECREF(key);
909 return -1;
910 }
911 Py_DECREF(key);
912 }
913 Py_DECREF(it);
914 if (PyErr_Occurred())
915 return -1;
916 return 0;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000917}
918
919static PyObject *
Georg Brandlc28e1fa2008-06-10 19:20:26 +0000920set_update(PySetObject *so, PyObject *args)
Raymond Hettingerd7946662005-08-01 21:39:29 +0000921{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000922 Py_ssize_t i;
Georg Brandlc28e1fa2008-06-10 19:20:26 +0000923
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000924 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
925 PyObject *other = PyTuple_GET_ITEM(args, i);
926 if (set_update_internal(so, other) == -1)
927 return NULL;
928 }
929 Py_RETURN_NONE;
Raymond Hettingera38123e2003-11-24 22:18:49 +0000930}
931
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000932PyDoc_STRVAR(update_doc,
Georg Brandlc28e1fa2008-06-10 19:20:26 +0000933"Update a set with the union of itself and others.");
Raymond Hettingera38123e2003-11-24 22:18:49 +0000934
Raymond Hettinger426d9952014-05-18 21:40:20 +0100935/* XXX Todo:
936 If aligned memory allocations become available, make the
937 set object 64 byte aligned so that most of the fields
938 can be retrieved or updated in a single cache line.
939*/
940
Raymond Hettingera38123e2003-11-24 22:18:49 +0000941static PyObject *
942make_new_set(PyTypeObject *type, PyObject *iterable)
943{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200944 PySetObject *so = NULL;
Raymond Hettingera38123e2003-11-24 22:18:49 +0000945
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000946 /* create PySetObject structure */
Raymond Hettinger8f8839e2013-09-07 20:26:50 -0700947 so = (PySetObject *)type->tp_alloc(type, 0);
948 if (so == NULL)
949 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000950
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700951 so->fill = 0;
952 so->used = 0;
953 so->mask = PySet_MINSIZE - 1;
954 so->table = so->smalltable;
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700955 so->hash = -1;
Raymond Hettinger1202a472015-01-18 13:12:42 -0800956 so->finger = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000957 so->weakreflist = NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +0000958
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000959 if (iterable != NULL) {
960 if (set_update_internal(so, iterable) == -1) {
961 Py_DECREF(so);
962 return NULL;
963 }
964 }
Raymond Hettingera38123e2003-11-24 22:18:49 +0000965
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000966 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +0000967}
968
Raymond Hettinger7d99f092008-11-16 11:44:54 +0000969static PyObject *
970make_new_set_basetype(PyTypeObject *type, PyObject *iterable)
971{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000972 if (type != &PySet_Type && type != &PyFrozenSet_Type) {
973 if (PyType_IsSubtype(type, &PySet_Type))
974 type = &PySet_Type;
975 else
976 type = &PyFrozenSet_Type;
977 }
978 return make_new_set(type, iterable);
Raymond Hettinger7d99f092008-11-16 11:44:54 +0000979}
980
Raymond Hettingerd7946662005-08-01 21:39:29 +0000981/* The empty frozenset is a singleton */
982static PyObject *emptyfrozenset = NULL;
983
Raymond Hettingera690a992003-11-16 16:17:49 +0000984static PyObject *
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000985frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
Raymond Hettingera690a992003-11-16 16:17:49 +0000986{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000987 PyObject *iterable = NULL, *result;
Raymond Hettingera690a992003-11-16 16:17:49 +0000988
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000989 if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds))
990 return NULL;
Georg Brandl02c42872005-08-26 06:42:30 +0000991
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000992 if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
993 return NULL;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000994
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000995 if (type != &PyFrozenSet_Type)
996 return make_new_set(type, iterable);
Raymond Hettingerd7946662005-08-01 21:39:29 +0000997
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000998 if (iterable != NULL) {
999 /* frozenset(f) is idempotent */
1000 if (PyFrozenSet_CheckExact(iterable)) {
1001 Py_INCREF(iterable);
1002 return iterable;
1003 }
1004 result = make_new_set(type, iterable);
1005 if (result == NULL || PySet_GET_SIZE(result))
1006 return result;
1007 Py_DECREF(result);
1008 }
1009 /* The empty frozenset is a singleton */
1010 if (emptyfrozenset == NULL)
1011 emptyfrozenset = make_new_set(type, NULL);
1012 Py_XINCREF(emptyfrozenset);
1013 return emptyfrozenset;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001014}
1015
Antoine Pitrou093ce9c2011-12-16 11:24:27 +01001016int
1017PySet_ClearFreeList(void)
Raymond Hettingerd7946662005-08-01 21:39:29 +00001018{
Raymond Hettinger8f8839e2013-09-07 20:26:50 -07001019 return 0;
Antoine Pitrou093ce9c2011-12-16 11:24:27 +01001020}
1021
1022void
1023PySet_Fini(void)
1024{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001025 Py_CLEAR(emptyfrozenset);
Raymond Hettingera690a992003-11-16 16:17:49 +00001026}
1027
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001028static PyObject *
1029set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1030{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001031 if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds))
1032 return NULL;
1033
1034 return make_new_set(type, NULL);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001035}
1036
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001037/* set_swap_bodies() switches the contents of any two sets by moving their
1038 internal data pointers and, if needed, copying the internal smalltables.
1039 Semantically equivalent to:
1040
1041 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1042
1043 The function always succeeds and it leaves both objects in a stable state.
Raymond Hettinger4d45c102015-01-25 16:27:40 -08001044 Useful for operations that update in-place (by allowing an intermediate
1045 result to be swapped into one of the original inputs).
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001046*/
1047
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001048static void
1049set_swap_bodies(PySetObject *a, PySetObject *b)
Raymond Hettingera690a992003-11-16 16:17:49 +00001050{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001051 Py_ssize_t t;
1052 setentry *u;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001053 setentry tab[PySet_MINSIZE];
Antoine Pitroufbb1c612010-10-23 17:37:54 +00001054 Py_hash_t h;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001055
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001056 t = a->fill; a->fill = b->fill; b->fill = t;
1057 t = a->used; a->used = b->used; b->used = t;
1058 t = a->mask; a->mask = b->mask; b->mask = t;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001059
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001060 u = a->table;
1061 if (a->table == a->smalltable)
1062 u = b->smalltable;
1063 a->table = b->table;
1064 if (b->table == b->smalltable)
1065 a->table = a->smalltable;
1066 b->table = u;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001067
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001068 if (a->table == a->smalltable || b->table == b->smalltable) {
1069 memcpy(tab, a->smalltable, sizeof(tab));
1070 memcpy(a->smalltable, b->smalltable, sizeof(tab));
1071 memcpy(b->smalltable, tab, sizeof(tab));
1072 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001073
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001074 if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type) &&
1075 PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) {
1076 h = a->hash; a->hash = b->hash; b->hash = h;
1077 } else {
1078 a->hash = -1;
1079 b->hash = -1;
1080 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001081}
1082
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001083static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001084set_copy(PySetObject *so)
1085{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001086 return make_new_set_basetype(Py_TYPE(so), (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001087}
1088
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001089static PyObject *
1090frozenset_copy(PySetObject *so)
1091{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001092 if (PyFrozenSet_CheckExact(so)) {
1093 Py_INCREF(so);
1094 return (PyObject *)so;
1095 }
1096 return set_copy(so);
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001097}
1098
Raymond Hettingera690a992003-11-16 16:17:49 +00001099PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
1100
1101static PyObject *
Raymond Hettingerc991db22005-08-11 07:58:45 +00001102set_clear(PySetObject *so)
1103{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001104 set_clear_internal(so);
1105 Py_RETURN_NONE;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001106}
1107
1108PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
1109
1110static PyObject *
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001111set_union(PySetObject *so, PyObject *args)
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001112{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001113 PySetObject *result;
1114 PyObject *other;
1115 Py_ssize_t i;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001116
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001117 result = (PySetObject *)set_copy(so);
1118 if (result == NULL)
1119 return NULL;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001120
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001121 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1122 other = PyTuple_GET_ITEM(args, i);
1123 if ((PyObject *)so == other)
1124 continue;
1125 if (set_update_internal(result, other) == -1) {
1126 Py_DECREF(result);
1127 return NULL;
1128 }
1129 }
1130 return (PyObject *)result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001131}
1132
1133PyDoc_STRVAR(union_doc,
1134 "Return the union of sets as a new set.\n\
1135\n\
1136(i.e. all elements that are in either set.)");
1137
1138static PyObject *
1139set_or(PySetObject *so, PyObject *other)
1140{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001141 PySetObject *result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001142
Brian Curtindfc80e32011-08-10 20:28:54 -05001143 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1144 Py_RETURN_NOTIMPLEMENTED;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001145
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001146 result = (PySetObject *)set_copy(so);
1147 if (result == NULL)
1148 return NULL;
1149 if ((PyObject *)so == other)
1150 return (PyObject *)result;
1151 if (set_update_internal(result, other) == -1) {
1152 Py_DECREF(result);
1153 return NULL;
1154 }
1155 return (PyObject *)result;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001156}
1157
Raymond Hettingera690a992003-11-16 16:17:49 +00001158static PyObject *
1159set_ior(PySetObject *so, PyObject *other)
1160{
Brian Curtindfc80e32011-08-10 20:28:54 -05001161 if (!PyAnySet_Check(other))
1162 Py_RETURN_NOTIMPLEMENTED;
1163
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001164 if (set_update_internal(so, other) == -1)
1165 return NULL;
1166 Py_INCREF(so);
1167 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001168}
1169
1170static PyObject *
1171set_intersection(PySetObject *so, PyObject *other)
1172{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001173 PySetObject *result;
1174 PyObject *key, *it, *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001175
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001176 if ((PyObject *)so == other)
1177 return set_copy(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001178
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001179 result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL);
1180 if (result == NULL)
1181 return NULL;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001182
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001183 if (PyAnySet_Check(other)) {
1184 Py_ssize_t pos = 0;
1185 setentry *entry;
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001186
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001187 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1188 tmp = (PyObject *)so;
1189 so = (PySetObject *)other;
1190 other = tmp;
1191 }
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001192
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001193 while (set_next((PySetObject *)other, &pos, &entry)) {
1194 int rv = set_contains_entry(so, entry);
1195 if (rv == -1) {
1196 Py_DECREF(result);
1197 return NULL;
1198 }
1199 if (rv) {
1200 if (set_add_entry(result, entry) == -1) {
1201 Py_DECREF(result);
1202 return NULL;
1203 }
1204 }
1205 }
1206 return (PyObject *)result;
1207 }
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001208
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001209 it = PyObject_GetIter(other);
1210 if (it == NULL) {
1211 Py_DECREF(result);
1212 return NULL;
1213 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001214
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001215 while ((key = PyIter_Next(it)) != NULL) {
1216 int rv;
1217 setentry entry;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001218 Py_hash_t hash = PyObject_Hash(key);
Thomas Wouters89f507f2006-12-13 04:49:30 +00001219
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001220 if (hash == -1) {
1221 Py_DECREF(it);
1222 Py_DECREF(result);
1223 Py_DECREF(key);
1224 return NULL;
1225 }
1226 entry.hash = hash;
1227 entry.key = key;
1228 rv = set_contains_entry(so, &entry);
1229 if (rv == -1) {
1230 Py_DECREF(it);
1231 Py_DECREF(result);
1232 Py_DECREF(key);
1233 return NULL;
1234 }
1235 if (rv) {
1236 if (set_add_entry(result, &entry) == -1) {
1237 Py_DECREF(it);
1238 Py_DECREF(result);
1239 Py_DECREF(key);
1240 return NULL;
1241 }
1242 }
1243 Py_DECREF(key);
1244 }
1245 Py_DECREF(it);
1246 if (PyErr_Occurred()) {
1247 Py_DECREF(result);
1248 return NULL;
1249 }
1250 return (PyObject *)result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001251}
1252
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001253static PyObject *
1254set_intersection_multi(PySetObject *so, PyObject *args)
1255{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001256 Py_ssize_t i;
1257 PyObject *result = (PyObject *)so;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001258
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001259 if (PyTuple_GET_SIZE(args) == 0)
1260 return set_copy(so);
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001261
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001262 Py_INCREF(so);
1263 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1264 PyObject *other = PyTuple_GET_ITEM(args, i);
1265 PyObject *newresult = set_intersection((PySetObject *)result, other);
1266 if (newresult == NULL) {
1267 Py_DECREF(result);
1268 return NULL;
1269 }
1270 Py_DECREF(result);
1271 result = newresult;
1272 }
1273 return result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001274}
1275
Raymond Hettingera690a992003-11-16 16:17:49 +00001276PyDoc_STRVAR(intersection_doc,
1277"Return the intersection of two sets as a new set.\n\
1278\n\
1279(i.e. all elements that are in both sets.)");
1280
1281static PyObject *
1282set_intersection_update(PySetObject *so, PyObject *other)
1283{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001284 PyObject *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001285
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001286 tmp = set_intersection(so, other);
1287 if (tmp == NULL)
1288 return NULL;
1289 set_swap_bodies(so, (PySetObject *)tmp);
1290 Py_DECREF(tmp);
1291 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001292}
1293
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001294static PyObject *
1295set_intersection_update_multi(PySetObject *so, PyObject *args)
1296{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001297 PyObject *tmp;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001298
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001299 tmp = set_intersection_multi(so, args);
1300 if (tmp == NULL)
1301 return NULL;
1302 set_swap_bodies(so, (PySetObject *)tmp);
1303 Py_DECREF(tmp);
1304 Py_RETURN_NONE;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001305}
1306
Raymond Hettingera690a992003-11-16 16:17:49 +00001307PyDoc_STRVAR(intersection_update_doc,
1308"Update a set with the intersection of itself and another.");
1309
1310static PyObject *
1311set_and(PySetObject *so, PyObject *other)
1312{
Brian Curtindfc80e32011-08-10 20:28:54 -05001313 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1314 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001315 return set_intersection(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001316}
1317
1318static PyObject *
1319set_iand(PySetObject *so, PyObject *other)
1320{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001321 PyObject *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001322
Brian Curtindfc80e32011-08-10 20:28:54 -05001323 if (!PyAnySet_Check(other))
1324 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001325 result = set_intersection_update(so, other);
1326 if (result == NULL)
1327 return NULL;
1328 Py_DECREF(result);
1329 Py_INCREF(so);
1330 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001331}
1332
Guido van Rossum58da9312007-11-10 23:39:45 +00001333static PyObject *
1334set_isdisjoint(PySetObject *so, PyObject *other)
1335{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001336 PyObject *key, *it, *tmp;
Guido van Rossum58da9312007-11-10 23:39:45 +00001337
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001338 if ((PyObject *)so == other) {
1339 if (PySet_GET_SIZE(so) == 0)
1340 Py_RETURN_TRUE;
1341 else
1342 Py_RETURN_FALSE;
1343 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001344
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001345 if (PyAnySet_CheckExact(other)) {
1346 Py_ssize_t pos = 0;
1347 setentry *entry;
Guido van Rossum58da9312007-11-10 23:39:45 +00001348
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001349 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1350 tmp = (PyObject *)so;
1351 so = (PySetObject *)other;
1352 other = tmp;
1353 }
1354 while (set_next((PySetObject *)other, &pos, &entry)) {
1355 int rv = set_contains_entry(so, entry);
1356 if (rv == -1)
1357 return NULL;
1358 if (rv)
1359 Py_RETURN_FALSE;
1360 }
1361 Py_RETURN_TRUE;
1362 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001363
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001364 it = PyObject_GetIter(other);
1365 if (it == NULL)
1366 return NULL;
Guido van Rossum58da9312007-11-10 23:39:45 +00001367
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001368 while ((key = PyIter_Next(it)) != NULL) {
1369 int rv;
1370 setentry entry;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001371 Py_hash_t hash = PyObject_Hash(key);
Guido van Rossum58da9312007-11-10 23:39:45 +00001372
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001373 if (hash == -1) {
1374 Py_DECREF(key);
1375 Py_DECREF(it);
1376 return NULL;
1377 }
1378 entry.hash = hash;
1379 entry.key = key;
1380 rv = set_contains_entry(so, &entry);
1381 Py_DECREF(key);
1382 if (rv == -1) {
1383 Py_DECREF(it);
1384 return NULL;
1385 }
1386 if (rv) {
1387 Py_DECREF(it);
1388 Py_RETURN_FALSE;
1389 }
1390 }
1391 Py_DECREF(it);
1392 if (PyErr_Occurred())
1393 return NULL;
1394 Py_RETURN_TRUE;
Guido van Rossum58da9312007-11-10 23:39:45 +00001395}
1396
1397PyDoc_STRVAR(isdisjoint_doc,
1398"Return True if two sets have a null intersection.");
1399
Neal Norwitz6576bd82005-11-13 18:41:28 +00001400static int
Raymond Hettingerc991db22005-08-11 07:58:45 +00001401set_difference_update_internal(PySetObject *so, PyObject *other)
1402{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001403 if ((PyObject *)so == other)
1404 return set_clear_internal(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001405
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001406 if (PyAnySet_Check(other)) {
1407 setentry *entry;
1408 Py_ssize_t pos = 0;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001409
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001410 while (set_next((PySetObject *)other, &pos, &entry))
1411 if (set_discard_entry(so, entry) == -1)
1412 return -1;
1413 } else {
1414 PyObject *key, *it;
1415 it = PyObject_GetIter(other);
1416 if (it == NULL)
1417 return -1;
1418
1419 while ((key = PyIter_Next(it)) != NULL) {
1420 if (set_discard_key(so, key) == -1) {
1421 Py_DECREF(it);
1422 Py_DECREF(key);
1423 return -1;
1424 }
1425 Py_DECREF(key);
1426 }
1427 Py_DECREF(it);
1428 if (PyErr_Occurred())
1429 return -1;
1430 }
1431 /* If more than 1/5 are dummies, then resize them away. */
1432 if ((so->fill - so->used) * 5 < so->mask)
1433 return 0;
1434 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001435}
1436
Raymond Hettingera690a992003-11-16 16:17:49 +00001437static PyObject *
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001438set_difference_update(PySetObject *so, PyObject *args)
Raymond Hettingera690a992003-11-16 16:17:49 +00001439{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001440 Py_ssize_t i;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001441
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001442 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1443 PyObject *other = PyTuple_GET_ITEM(args, i);
1444 if (set_difference_update_internal(so, other) == -1)
1445 return NULL;
1446 }
1447 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001448}
1449
1450PyDoc_STRVAR(difference_update_doc,
1451"Remove all elements of another set from this set.");
1452
1453static PyObject *
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001454set_copy_and_difference(PySetObject *so, PyObject *other)
1455{
1456 PyObject *result;
1457
1458 result = set_copy(so);
1459 if (result == NULL)
1460 return NULL;
1461 if (set_difference_update_internal((PySetObject *) result, other) != -1)
1462 return result;
1463 Py_DECREF(result);
1464 return NULL;
1465}
1466
1467static PyObject *
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001468set_difference(PySetObject *so, PyObject *other)
1469{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001470 PyObject *result;
1471 setentry *entry;
1472 Py_ssize_t pos = 0;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001473
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001474 if (!PyAnySet_Check(other) && !PyDict_CheckExact(other)) {
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001475 return set_copy_and_difference(so, other);
1476 }
1477
1478 /* If len(so) much more than len(other), it's more efficient to simply copy
1479 * so and then iterate other looking for common elements. */
1480 if ((PySet_GET_SIZE(so) >> 2) > PyObject_Size(other)) {
1481 return set_copy_and_difference(so, other);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001482 }
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001483
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001484 result = make_new_set_basetype(Py_TYPE(so), NULL);
1485 if (result == NULL)
1486 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001487
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001488 if (PyDict_CheckExact(other)) {
1489 while (set_next(so, &pos, &entry)) {
1490 setentry entrycopy;
1491 entrycopy.hash = entry->hash;
1492 entrycopy.key = entry->key;
Antoine Pitroufbb1c612010-10-23 17:37:54 +00001493 if (!_PyDict_Contains(other, entry->key, entry->hash)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001494 if (set_add_entry((PySetObject *)result, &entrycopy) == -1) {
1495 Py_DECREF(result);
1496 return NULL;
1497 }
1498 }
1499 }
1500 return result;
1501 }
1502
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001503 /* Iterate over so, checking for common elements in other. */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001504 while (set_next(so, &pos, &entry)) {
1505 int rv = set_contains_entry((PySetObject *)other, entry);
1506 if (rv == -1) {
1507 Py_DECREF(result);
1508 return NULL;
1509 }
1510 if (!rv) {
1511 if (set_add_entry((PySetObject *)result, entry) == -1) {
1512 Py_DECREF(result);
1513 return NULL;
1514 }
1515 }
1516 }
1517 return result;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001518}
1519
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001520static PyObject *
1521set_difference_multi(PySetObject *so, PyObject *args)
1522{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001523 Py_ssize_t i;
1524 PyObject *result, *other;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001525
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001526 if (PyTuple_GET_SIZE(args) == 0)
1527 return set_copy(so);
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001528
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001529 other = PyTuple_GET_ITEM(args, 0);
1530 result = set_difference(so, other);
1531 if (result == NULL)
1532 return NULL;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001533
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001534 for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) {
1535 other = PyTuple_GET_ITEM(args, i);
1536 if (set_difference_update_internal((PySetObject *)result, other) == -1) {
1537 Py_DECREF(result);
1538 return NULL;
1539 }
1540 }
1541 return result;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001542}
1543
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001544PyDoc_STRVAR(difference_doc,
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001545"Return the difference of two or more sets as a new set.\n\
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001546\n\
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001547(i.e. all elements that are in this set but not the others.)");
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001548static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001549set_sub(PySetObject *so, PyObject *other)
1550{
Brian Curtindfc80e32011-08-10 20:28:54 -05001551 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1552 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001553 return set_difference(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001554}
1555
1556static PyObject *
1557set_isub(PySetObject *so, PyObject *other)
1558{
Brian Curtindfc80e32011-08-10 20:28:54 -05001559 if (!PyAnySet_Check(other))
1560 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001561 if (set_difference_update_internal(so, other) == -1)
1562 return NULL;
1563 Py_INCREF(so);
1564 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001565}
1566
1567static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001568set_symmetric_difference_update(PySetObject *so, PyObject *other)
1569{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001570 PySetObject *otherset;
1571 PyObject *key;
1572 Py_ssize_t pos = 0;
1573 setentry *entry;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001574
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001575 if ((PyObject *)so == other)
1576 return set_clear(so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001577
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001578 if (PyDict_CheckExact(other)) {
1579 PyObject *value;
1580 int rv;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001581 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001582 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
1583 setentry an_entry;
Thomas Wouters89f507f2006-12-13 04:49:30 +00001584
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001585 Py_INCREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001586 an_entry.hash = hash;
1587 an_entry.key = key;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001588
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001589 rv = set_discard_entry(so, &an_entry);
Georg Brandl2d444492010-09-03 10:52:55 +00001590 if (rv == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001591 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001592 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001593 }
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001594 if (rv == DISCARD_NOTFOUND) {
1595 if (set_add_entry(so, &an_entry) == -1) {
1596 Py_DECREF(key);
1597 return NULL;
1598 }
1599 }
Georg Brandl2d444492010-09-03 10:52:55 +00001600 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001601 }
1602 Py_RETURN_NONE;
1603 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001604
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001605 if (PyAnySet_Check(other)) {
1606 Py_INCREF(other);
1607 otherset = (PySetObject *)other;
1608 } else {
1609 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1610 if (otherset == NULL)
1611 return NULL;
1612 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001613
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001614 while (set_next(otherset, &pos, &entry)) {
1615 int rv = set_discard_entry(so, entry);
1616 if (rv == -1) {
1617 Py_DECREF(otherset);
1618 return NULL;
1619 }
1620 if (rv == DISCARD_NOTFOUND) {
1621 if (set_add_entry(so, entry) == -1) {
1622 Py_DECREF(otherset);
1623 return NULL;
1624 }
1625 }
1626 }
1627 Py_DECREF(otherset);
1628 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001629}
1630
1631PyDoc_STRVAR(symmetric_difference_update_doc,
1632"Update a set with the symmetric difference of itself and another.");
1633
1634static PyObject *
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001635set_symmetric_difference(PySetObject *so, PyObject *other)
1636{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001637 PyObject *rv;
1638 PySetObject *otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001639
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001640 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1641 if (otherset == NULL)
1642 return NULL;
1643 rv = set_symmetric_difference_update(otherset, (PyObject *)so);
1644 if (rv == NULL)
1645 return NULL;
1646 Py_DECREF(rv);
1647 return (PyObject *)otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001648}
1649
1650PyDoc_STRVAR(symmetric_difference_doc,
1651"Return the symmetric difference of two sets as a new set.\n\
1652\n\
1653(i.e. all elements that are in exactly one of the sets.)");
1654
1655static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001656set_xor(PySetObject *so, PyObject *other)
1657{
Brian Curtindfc80e32011-08-10 20:28:54 -05001658 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1659 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001660 return set_symmetric_difference(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001661}
1662
1663static PyObject *
1664set_ixor(PySetObject *so, PyObject *other)
1665{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001666 PyObject *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001667
Brian Curtindfc80e32011-08-10 20:28:54 -05001668 if (!PyAnySet_Check(other))
1669 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001670 result = set_symmetric_difference_update(so, other);
1671 if (result == NULL)
1672 return NULL;
1673 Py_DECREF(result);
1674 Py_INCREF(so);
1675 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001676}
1677
1678static PyObject *
1679set_issubset(PySetObject *so, PyObject *other)
1680{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001681 setentry *entry;
1682 Py_ssize_t pos = 0;
Raymond Hettingera690a992003-11-16 16:17:49 +00001683
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001684 if (!PyAnySet_Check(other)) {
1685 PyObject *tmp, *result;
1686 tmp = make_new_set(&PySet_Type, other);
1687 if (tmp == NULL)
1688 return NULL;
1689 result = set_issubset(so, tmp);
1690 Py_DECREF(tmp);
1691 return result;
1692 }
1693 if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
1694 Py_RETURN_FALSE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001695
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001696 while (set_next(so, &pos, &entry)) {
1697 int rv = set_contains_entry((PySetObject *)other, entry);
1698 if (rv == -1)
1699 return NULL;
1700 if (!rv)
1701 Py_RETURN_FALSE;
1702 }
1703 Py_RETURN_TRUE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001704}
1705
1706PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
1707
1708static PyObject *
1709set_issuperset(PySetObject *so, PyObject *other)
1710{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001711 PyObject *tmp, *result;
Raymond Hettinger3fbec702003-11-21 07:56:36 +00001712
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001713 if (!PyAnySet_Check(other)) {
1714 tmp = make_new_set(&PySet_Type, other);
1715 if (tmp == NULL)
1716 return NULL;
1717 result = set_issuperset(so, tmp);
1718 Py_DECREF(tmp);
1719 return result;
1720 }
1721 return set_issubset((PySetObject *)other, (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001722}
1723
1724PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
1725
Raymond Hettingera690a992003-11-16 16:17:49 +00001726static PyObject *
1727set_richcompare(PySetObject *v, PyObject *w, int op)
1728{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001729 PyObject *r1, *r2;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001730
Brian Curtindfc80e32011-08-10 20:28:54 -05001731 if(!PyAnySet_Check(w))
1732 Py_RETURN_NOTIMPLEMENTED;
1733
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001734 switch (op) {
1735 case Py_EQ:
1736 if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
1737 Py_RETURN_FALSE;
1738 if (v->hash != -1 &&
1739 ((PySetObject *)w)->hash != -1 &&
1740 v->hash != ((PySetObject *)w)->hash)
1741 Py_RETURN_FALSE;
1742 return set_issubset(v, w);
1743 case Py_NE:
1744 r1 = set_richcompare(v, w, Py_EQ);
1745 if (r1 == NULL)
1746 return NULL;
1747 r2 = PyBool_FromLong(PyObject_Not(r1));
1748 Py_DECREF(r1);
1749 return r2;
1750 case Py_LE:
1751 return set_issubset(v, w);
1752 case Py_GE:
1753 return set_issuperset(v, w);
1754 case Py_LT:
1755 if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))
1756 Py_RETURN_FALSE;
1757 return set_issubset(v, w);
1758 case Py_GT:
1759 if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
1760 Py_RETURN_FALSE;
1761 return set_issuperset(v, w);
1762 }
Brian Curtindfc80e32011-08-10 20:28:54 -05001763 Py_RETURN_NOTIMPLEMENTED;
Raymond Hettingera690a992003-11-16 16:17:49 +00001764}
1765
Raymond Hettingera690a992003-11-16 16:17:49 +00001766static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001767set_add(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001768{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001769 if (set_add_key(so, key) == -1)
1770 return NULL;
1771 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001772}
1773
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001774PyDoc_STRVAR(add_doc,
Raymond Hettingera690a992003-11-16 16:17:49 +00001775"Add an element to a set.\n\
1776\n\
1777This has no effect if the element is already present.");
1778
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001779static int
1780set_contains(PySetObject *so, PyObject *key)
1781{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001782 PyObject *tmpkey;
1783 int rv;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001784
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001785 rv = set_contains_key(so, key);
1786 if (rv == -1) {
1787 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1788 return -1;
1789 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001790 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001791 if (tmpkey == NULL)
1792 return -1;
Petri Lehtinen5acc27e2011-10-30 13:56:41 +02001793 rv = set_contains_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001794 Py_DECREF(tmpkey);
1795 }
1796 return rv;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001797}
1798
1799static PyObject *
1800set_direct_contains(PySetObject *so, PyObject *key)
1801{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001802 long result;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001803
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001804 result = set_contains(so, key);
1805 if (result == -1)
1806 return NULL;
1807 return PyBool_FromLong(result);
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001808}
1809
1810PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
1811
Raymond Hettingera690a992003-11-16 16:17:49 +00001812static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001813set_remove(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001814{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001815 PyObject *tmpkey;
1816 int rv;
Raymond Hettingerbfd334a2003-11-22 03:55:23 +00001817
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001818 rv = set_discard_key(so, key);
1819 if (rv == -1) {
1820 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1821 return NULL;
1822 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001823 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001824 if (tmpkey == NULL)
1825 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001826 rv = set_discard_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001827 Py_DECREF(tmpkey);
1828 if (rv == -1)
1829 return NULL;
1830 }
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00001831
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001832 if (rv == DISCARD_NOTFOUND) {
Raymond Hettinger69492da2013-09-02 15:59:26 -07001833 _PyErr_SetKeyError(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001834 return NULL;
1835 }
1836 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001837}
1838
1839PyDoc_STRVAR(remove_doc,
1840"Remove an element from a set; it must be a member.\n\
1841\n\
1842If the element is not a member, raise a KeyError.");
1843
1844static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001845set_discard(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001846{
Benjamin Peterson2b50a012011-10-30 14:24:44 -04001847 PyObject *tmpkey;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001848 int rv;
Raymond Hettinger0deab622003-12-13 18:53:18 +00001849
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001850 rv = set_discard_key(so, key);
1851 if (rv == -1) {
1852 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1853 return NULL;
1854 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001855 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001856 if (tmpkey == NULL)
1857 return NULL;
Petri Lehtinene0aa8032011-10-30 14:31:27 +02001858 rv = set_discard_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001859 Py_DECREF(tmpkey);
Petri Lehtinene0aa8032011-10-30 14:31:27 +02001860 if (rv == -1)
1861 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001862 }
1863 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001864}
1865
1866PyDoc_STRVAR(discard_doc,
1867"Remove an element from a set if it is a member.\n\
1868\n\
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001869If the element is not a member, do nothing.");
Raymond Hettingera690a992003-11-16 16:17:49 +00001870
1871static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001872set_reduce(PySetObject *so)
1873{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001874 PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;
Martin v. Löwisbd928fe2011-10-14 10:20:37 +02001875 _Py_IDENTIFIER(__dict__);
Raymond Hettingera690a992003-11-16 16:17:49 +00001876
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001877 keys = PySequence_List((PyObject *)so);
1878 if (keys == NULL)
1879 goto done;
1880 args = PyTuple_Pack(1, keys);
1881 if (args == NULL)
1882 goto done;
Martin v. Löwis1ee1b6f2011-10-10 18:11:30 +02001883 dict = _PyObject_GetAttrId((PyObject *)so, &PyId___dict__);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001884 if (dict == NULL) {
1885 PyErr_Clear();
1886 dict = Py_None;
1887 Py_INCREF(dict);
1888 }
1889 result = PyTuple_Pack(3, Py_TYPE(so), args, dict);
Raymond Hettingera690a992003-11-16 16:17:49 +00001890done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001891 Py_XDECREF(args);
1892 Py_XDECREF(keys);
1893 Py_XDECREF(dict);
1894 return result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001895}
1896
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001897static PyObject *
1898set_sizeof(PySetObject *so)
1899{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001900 Py_ssize_t res;
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001901
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001902 res = sizeof(PySetObject);
1903 if (so->table != so->smalltable)
1904 res = res + (so->mask + 1) * sizeof(setentry);
1905 return PyLong_FromSsize_t(res);
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001906}
1907
1908PyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes");
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001909static int
1910set_init(PySetObject *self, PyObject *args, PyObject *kwds)
1911{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001912 PyObject *iterable = NULL;
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001913
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001914 if (!PyAnySet_Check(self))
1915 return -1;
1916 if (PySet_Check(self) && !_PyArg_NoKeywords("set()", kwds))
1917 return -1;
1918 if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable))
1919 return -1;
1920 set_clear_internal(self);
1921 self->hash = -1;
1922 if (iterable == NULL)
1923 return 0;
1924 return set_update_internal(self, iterable);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001925}
1926
Raymond Hettingera690a992003-11-16 16:17:49 +00001927static PySequenceMethods set_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001928 set_len, /* sq_length */
1929 0, /* sq_concat */
1930 0, /* sq_repeat */
1931 0, /* sq_item */
1932 0, /* sq_slice */
1933 0, /* sq_ass_item */
1934 0, /* sq_ass_slice */
1935 (objobjproc)set_contains, /* sq_contains */
Raymond Hettingera690a992003-11-16 16:17:49 +00001936};
1937
1938/* set object ********************************************************/
1939
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00001940#ifdef Py_DEBUG
1941static PyObject *test_c_api(PySetObject *so);
1942
1943PyDoc_STRVAR(test_c_api_doc, "Exercises C API. Returns True.\n\
1944All is well if assertions don't fail.");
1945#endif
1946
Raymond Hettingera690a992003-11-16 16:17:49 +00001947static PyMethodDef set_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001948 {"add", (PyCFunction)set_add, METH_O,
1949 add_doc},
1950 {"clear", (PyCFunction)set_clear, METH_NOARGS,
1951 clear_doc},
1952 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
1953 contains_doc},
1954 {"copy", (PyCFunction)set_copy, METH_NOARGS,
1955 copy_doc},
1956 {"discard", (PyCFunction)set_discard, METH_O,
1957 discard_doc},
1958 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
1959 difference_doc},
1960 {"difference_update", (PyCFunction)set_difference_update, METH_VARARGS,
1961 difference_update_doc},
1962 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
1963 intersection_doc},
1964 {"intersection_update",(PyCFunction)set_intersection_update_multi, METH_VARARGS,
1965 intersection_update_doc},
1966 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
1967 isdisjoint_doc},
1968 {"issubset", (PyCFunction)set_issubset, METH_O,
1969 issubset_doc},
1970 {"issuperset", (PyCFunction)set_issuperset, METH_O,
1971 issuperset_doc},
1972 {"pop", (PyCFunction)set_pop, METH_NOARGS,
1973 pop_doc},
1974 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
1975 reduce_doc},
1976 {"remove", (PyCFunction)set_remove, METH_O,
1977 remove_doc},
1978 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
1979 sizeof_doc},
1980 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
1981 symmetric_difference_doc},
1982 {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O,
1983 symmetric_difference_update_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00001984#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001985 {"test_c_api", (PyCFunction)test_c_api, METH_NOARGS,
1986 test_c_api_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00001987#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001988 {"union", (PyCFunction)set_union, METH_VARARGS,
1989 union_doc},
1990 {"update", (PyCFunction)set_update, METH_VARARGS,
1991 update_doc},
1992 {NULL, NULL} /* sentinel */
Raymond Hettingera690a992003-11-16 16:17:49 +00001993};
1994
1995static PyNumberMethods set_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001996 0, /*nb_add*/
1997 (binaryfunc)set_sub, /*nb_subtract*/
1998 0, /*nb_multiply*/
1999 0, /*nb_remainder*/
2000 0, /*nb_divmod*/
2001 0, /*nb_power*/
2002 0, /*nb_negative*/
2003 0, /*nb_positive*/
2004 0, /*nb_absolute*/
2005 0, /*nb_bool*/
2006 0, /*nb_invert*/
2007 0, /*nb_lshift*/
2008 0, /*nb_rshift*/
2009 (binaryfunc)set_and, /*nb_and*/
2010 (binaryfunc)set_xor, /*nb_xor*/
2011 (binaryfunc)set_or, /*nb_or*/
2012 0, /*nb_int*/
2013 0, /*nb_reserved*/
2014 0, /*nb_float*/
2015 0, /*nb_inplace_add*/
2016 (binaryfunc)set_isub, /*nb_inplace_subtract*/
2017 0, /*nb_inplace_multiply*/
2018 0, /*nb_inplace_remainder*/
2019 0, /*nb_inplace_power*/
2020 0, /*nb_inplace_lshift*/
2021 0, /*nb_inplace_rshift*/
2022 (binaryfunc)set_iand, /*nb_inplace_and*/
2023 (binaryfunc)set_ixor, /*nb_inplace_xor*/
2024 (binaryfunc)set_ior, /*nb_inplace_or*/
Raymond Hettingera690a992003-11-16 16:17:49 +00002025};
2026
2027PyDoc_STRVAR(set_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002028"set() -> new empty set object\n\
2029set(iterable) -> new set object\n\
Raymond Hettingera690a992003-11-16 16:17:49 +00002030\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002031Build an unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00002032
2033PyTypeObject PySet_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002034 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2035 "set", /* tp_name */
2036 sizeof(PySetObject), /* tp_basicsize */
2037 0, /* tp_itemsize */
2038 /* methods */
2039 (destructor)set_dealloc, /* tp_dealloc */
2040 0, /* tp_print */
2041 0, /* tp_getattr */
2042 0, /* tp_setattr */
2043 0, /* tp_reserved */
2044 (reprfunc)set_repr, /* tp_repr */
2045 &set_as_number, /* tp_as_number */
2046 &set_as_sequence, /* tp_as_sequence */
2047 0, /* tp_as_mapping */
Georg Brandl00da4e02010-10-18 07:32:48 +00002048 PyObject_HashNotImplemented, /* tp_hash */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002049 0, /* tp_call */
2050 0, /* tp_str */
2051 PyObject_GenericGetAttr, /* tp_getattro */
2052 0, /* tp_setattro */
2053 0, /* tp_as_buffer */
2054 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2055 Py_TPFLAGS_BASETYPE, /* tp_flags */
2056 set_doc, /* tp_doc */
2057 (traverseproc)set_traverse, /* tp_traverse */
2058 (inquiry)set_clear_internal, /* tp_clear */
2059 (richcmpfunc)set_richcompare, /* tp_richcompare */
Georg Brandl00da4e02010-10-18 07:32:48 +00002060 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2061 (getiterfunc)set_iter, /* tp_iter */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002062 0, /* tp_iternext */
2063 set_methods, /* tp_methods */
2064 0, /* tp_members */
2065 0, /* tp_getset */
2066 0, /* tp_base */
2067 0, /* tp_dict */
2068 0, /* tp_descr_get */
2069 0, /* tp_descr_set */
2070 0, /* tp_dictoffset */
2071 (initproc)set_init, /* tp_init */
2072 PyType_GenericAlloc, /* tp_alloc */
2073 set_new, /* tp_new */
2074 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002075};
2076
2077/* frozenset object ********************************************************/
2078
2079
2080static PyMethodDef frozenset_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002081 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2082 contains_doc},
2083 {"copy", (PyCFunction)frozenset_copy, METH_NOARGS,
2084 copy_doc},
2085 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2086 difference_doc},
2087 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2088 intersection_doc},
2089 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2090 isdisjoint_doc},
2091 {"issubset", (PyCFunction)set_issubset, METH_O,
2092 issubset_doc},
2093 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2094 issuperset_doc},
2095 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2096 reduce_doc},
2097 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2098 sizeof_doc},
2099 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2100 symmetric_difference_doc},
2101 {"union", (PyCFunction)set_union, METH_VARARGS,
2102 union_doc},
2103 {NULL, NULL} /* sentinel */
Raymond Hettingera690a992003-11-16 16:17:49 +00002104};
2105
2106static PyNumberMethods frozenset_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002107 0, /*nb_add*/
2108 (binaryfunc)set_sub, /*nb_subtract*/
2109 0, /*nb_multiply*/
2110 0, /*nb_remainder*/
2111 0, /*nb_divmod*/
2112 0, /*nb_power*/
2113 0, /*nb_negative*/
2114 0, /*nb_positive*/
2115 0, /*nb_absolute*/
2116 0, /*nb_bool*/
2117 0, /*nb_invert*/
2118 0, /*nb_lshift*/
2119 0, /*nb_rshift*/
2120 (binaryfunc)set_and, /*nb_and*/
2121 (binaryfunc)set_xor, /*nb_xor*/
2122 (binaryfunc)set_or, /*nb_or*/
Raymond Hettingera690a992003-11-16 16:17:49 +00002123};
2124
2125PyDoc_STRVAR(frozenset_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002126"frozenset() -> empty frozenset object\n\
2127frozenset(iterable) -> frozenset object\n\
Raymond Hettingera690a992003-11-16 16:17:49 +00002128\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002129Build an immutable unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00002130
2131PyTypeObject PyFrozenSet_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002132 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2133 "frozenset", /* tp_name */
2134 sizeof(PySetObject), /* tp_basicsize */
2135 0, /* tp_itemsize */
2136 /* methods */
2137 (destructor)set_dealloc, /* tp_dealloc */
2138 0, /* tp_print */
2139 0, /* tp_getattr */
2140 0, /* tp_setattr */
2141 0, /* tp_reserved */
2142 (reprfunc)set_repr, /* tp_repr */
2143 &frozenset_as_number, /* tp_as_number */
2144 &set_as_sequence, /* tp_as_sequence */
2145 0, /* tp_as_mapping */
2146 frozenset_hash, /* tp_hash */
2147 0, /* tp_call */
2148 0, /* tp_str */
2149 PyObject_GenericGetAttr, /* tp_getattro */
2150 0, /* tp_setattro */
2151 0, /* tp_as_buffer */
2152 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2153 Py_TPFLAGS_BASETYPE, /* tp_flags */
2154 frozenset_doc, /* tp_doc */
2155 (traverseproc)set_traverse, /* tp_traverse */
2156 (inquiry)set_clear_internal, /* tp_clear */
2157 (richcmpfunc)set_richcompare, /* tp_richcompare */
2158 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2159 (getiterfunc)set_iter, /* tp_iter */
2160 0, /* tp_iternext */
2161 frozenset_methods, /* tp_methods */
2162 0, /* tp_members */
2163 0, /* tp_getset */
2164 0, /* tp_base */
2165 0, /* tp_dict */
2166 0, /* tp_descr_get */
2167 0, /* tp_descr_set */
2168 0, /* tp_dictoffset */
2169 0, /* tp_init */
2170 PyType_GenericAlloc, /* tp_alloc */
2171 frozenset_new, /* tp_new */
2172 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002173};
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002174
2175
2176/***** C API functions *************************************************/
2177
2178PyObject *
2179PySet_New(PyObject *iterable)
2180{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002181 return make_new_set(&PySet_Type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002182}
2183
2184PyObject *
2185PyFrozenSet_New(PyObject *iterable)
2186{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002187 return make_new_set(&PyFrozenSet_Type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002188}
2189
Neal Norwitz8c49c822006-03-04 18:41:19 +00002190Py_ssize_t
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002191PySet_Size(PyObject *anyset)
2192{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002193 if (!PyAnySet_Check(anyset)) {
2194 PyErr_BadInternalCall();
2195 return -1;
2196 }
2197 return PySet_GET_SIZE(anyset);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002198}
2199
2200int
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002201PySet_Clear(PyObject *set)
2202{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002203 if (!PySet_Check(set)) {
2204 PyErr_BadInternalCall();
2205 return -1;
2206 }
2207 return set_clear_internal((PySetObject *)set);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002208}
2209
2210int
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002211PySet_Contains(PyObject *anyset, PyObject *key)
2212{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002213 if (!PyAnySet_Check(anyset)) {
2214 PyErr_BadInternalCall();
2215 return -1;
2216 }
2217 return set_contains_key((PySetObject *)anyset, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002218}
2219
2220int
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002221PySet_Discard(PyObject *set, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002222{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002223 if (!PySet_Check(set)) {
2224 PyErr_BadInternalCall();
2225 return -1;
2226 }
2227 return set_discard_key((PySetObject *)set, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002228}
2229
2230int
Christian Heimesfd66e512008-01-29 12:18:50 +00002231PySet_Add(PyObject *anyset, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002232{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002233 if (!PySet_Check(anyset) &&
2234 (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
2235 PyErr_BadInternalCall();
2236 return -1;
2237 }
2238 return set_add_key((PySetObject *)anyset, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002239}
2240
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002241int
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002242_PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash)
Guido van Rossumd8faa362007-04-27 19:54:29 +00002243{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002244 setentry *entry;
Guido van Rossumd8faa362007-04-27 19:54:29 +00002245
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002246 if (!PyAnySet_Check(set)) {
2247 PyErr_BadInternalCall();
2248 return -1;
2249 }
2250 if (set_next((PySetObject *)set, pos, &entry) == 0)
2251 return 0;
2252 *key = entry->key;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002253 *hash = entry->hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002254 return 1;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002255}
2256
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002257PyObject *
2258PySet_Pop(PyObject *set)
2259{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002260 if (!PySet_Check(set)) {
2261 PyErr_BadInternalCall();
2262 return NULL;
2263 }
2264 return set_pop((PySetObject *)set);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002265}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002266
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002267int
2268_PySet_Update(PyObject *set, PyObject *iterable)
2269{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002270 if (!PySet_Check(set)) {
2271 PyErr_BadInternalCall();
2272 return -1;
2273 }
2274 return set_update_internal((PySetObject *)set, iterable);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002275}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002276
Raymond Hettingere259f132013-12-15 11:56:14 -08002277/* Exported for the gdb plugin's benefit. */
2278PyObject *_PySet_Dummy = dummy;
2279
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002280#ifdef Py_DEBUG
2281
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002282/* Test code to be called with any three element set.
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002283 Returns True and original set is restored. */
2284
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002285#define assertRaises(call_return_value, exception) \
2286 do { \
2287 assert(call_return_value); \
2288 assert(PyErr_ExceptionMatches(exception)); \
2289 PyErr_Clear(); \
2290 } while(0)
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002291
2292static PyObject *
2293test_c_api(PySetObject *so)
2294{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002295 Py_ssize_t count;
2296 char *s;
2297 Py_ssize_t i;
Raymond Hettinger583cd032013-09-07 22:06:35 -07002298 PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x=NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002299 PyObject *ob = (PyObject *)so;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002300 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002301 PyObject *str;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002302
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002303 /* Verify preconditions */
2304 assert(PyAnySet_Check(ob));
2305 assert(PyAnySet_CheckExact(ob));
2306 assert(!PyFrozenSet_CheckExact(ob));
Victor Stinner08b36bd2010-03-13 00:19:17 +00002307
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002308 /* so.clear(); so |= set("abc"); */
2309 str = PyUnicode_FromString("abc");
2310 if (str == NULL)
2311 return NULL;
2312 set_clear_internal(so);
2313 if (set_update_internal(so, str) == -1) {
2314 Py_DECREF(str);
2315 return NULL;
2316 }
2317 Py_DECREF(str);
Victor Stinner08b36bd2010-03-13 00:19:17 +00002318
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002319 /* Exercise type/size checks */
2320 assert(PySet_Size(ob) == 3);
2321 assert(PySet_GET_SIZE(ob) == 3);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002322
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002323 /* Raise TypeError for non-iterable constructor arguments */
2324 assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
2325 assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002326
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002327 /* Raise TypeError for unhashable key */
2328 dup = PySet_New(ob);
2329 assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
2330 assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
2331 assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002332
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002333 /* Exercise successful pop, contains, add, and discard */
2334 elem = PySet_Pop(ob);
2335 assert(PySet_Contains(ob, elem) == 0);
2336 assert(PySet_GET_SIZE(ob) == 2);
2337 assert(PySet_Add(ob, elem) == 0);
2338 assert(PySet_Contains(ob, elem) == 1);
2339 assert(PySet_GET_SIZE(ob) == 3);
2340 assert(PySet_Discard(ob, elem) == 1);
2341 assert(PySet_GET_SIZE(ob) == 2);
2342 assert(PySet_Discard(ob, elem) == 0);
2343 assert(PySet_GET_SIZE(ob) == 2);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002344
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002345 /* Exercise clear */
2346 dup2 = PySet_New(dup);
2347 assert(PySet_Clear(dup2) == 0);
2348 assert(PySet_Size(dup2) == 0);
2349 Py_DECREF(dup2);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002350
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002351 /* Raise SystemError on clear or update of frozen set */
2352 f = PyFrozenSet_New(dup);
2353 assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
2354 assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
2355 assert(PySet_Add(f, elem) == 0);
2356 Py_INCREF(f);
2357 assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
2358 Py_DECREF(f);
2359 Py_DECREF(f);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002360
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002361 /* Exercise direct iteration */
2362 i = 0, count = 0;
2363 while (_PySet_NextEntry((PyObject *)dup, &i, &x, &hash)) {
2364 s = _PyUnicode_AsString(x);
2365 assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
2366 count++;
2367 }
2368 assert(count == 3);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002369
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002370 /* Exercise updates */
2371 dup2 = PySet_New(NULL);
2372 assert(_PySet_Update(dup2, dup) == 0);
2373 assert(PySet_Size(dup2) == 3);
2374 assert(_PySet_Update(dup2, dup) == 0);
2375 assert(PySet_Size(dup2) == 3);
2376 Py_DECREF(dup2);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002377
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002378 /* Raise SystemError when self argument is not a set or frozenset. */
2379 t = PyTuple_New(0);
2380 assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
2381 assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
2382 Py_DECREF(t);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002383
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002384 /* Raise SystemError when self argument is not a set. */
2385 f = PyFrozenSet_New(dup);
2386 assert(PySet_Size(f) == 3);
2387 assert(PyFrozenSet_CheckExact(f));
2388 assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
2389 assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
2390 Py_DECREF(f);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002391
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002392 /* Raise KeyError when popping from an empty set */
2393 assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
2394 Py_DECREF(ob);
2395 assert(PySet_GET_SIZE(ob) == 0);
2396 assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002397
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002398 /* Restore the set from the copy using the PyNumber API */
2399 assert(PyNumber_InPlaceOr(ob, dup) == ob);
2400 Py_DECREF(ob);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002401
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002402 /* Verify constructors accept NULL arguments */
2403 f = PySet_New(NULL);
2404 assert(f != NULL);
2405 assert(PySet_GET_SIZE(f) == 0);
2406 Py_DECREF(f);
2407 f = PyFrozenSet_New(NULL);
2408 assert(f != NULL);
2409 assert(PyFrozenSet_CheckExact(f));
2410 assert(PySet_GET_SIZE(f) == 0);
2411 Py_DECREF(f);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002412
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002413 Py_DECREF(elem);
2414 Py_DECREF(dup);
2415 Py_RETURN_TRUE;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002416}
2417
Raymond Hettinger9bda1d62005-09-16 07:14:21 +00002418#undef assertRaises
2419
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002420#endif
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -05002421
2422/***** Dummy Struct *************************************************/
2423
2424static PyObject *
2425dummy_repr(PyObject *op)
2426{
2427 return PyUnicode_FromString("<dummy key>");
2428}
2429
2430static void
2431dummy_dealloc(PyObject* ignore)
2432{
2433 Py_FatalError("deallocating <dummy key>");
2434}
2435
2436static PyTypeObject _PySetDummy_Type = {
2437 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2438 "<dummy key> type",
2439 0,
2440 0,
2441 dummy_dealloc, /*tp_dealloc*/ /*never called*/
2442 0, /*tp_print*/
2443 0, /*tp_getattr*/
2444 0, /*tp_setattr*/
2445 0, /*tp_reserved*/
2446 dummy_repr, /*tp_repr*/
2447 0, /*tp_as_number*/
2448 0, /*tp_as_sequence*/
2449 0, /*tp_as_mapping*/
2450 0, /*tp_hash */
2451 0, /*tp_call */
2452 0, /*tp_str */
2453 0, /*tp_getattro */
2454 0, /*tp_setattro */
2455 0, /*tp_as_buffer */
2456 Py_TPFLAGS_DEFAULT, /*tp_flags */
2457};
2458
2459static PyObject _dummy_struct = {
2460 _PyObject_EXTRA_INIT
2461 2, &_PySetDummy_Type
2462};
2463