blob: 5846045376d64396bca2ba1bd4033f90a4d05e13 [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 Hettingerae7b00e2013-09-07 15:05:00 -07007 The basic lookup function used by all operations.
8 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
9
10 The initial probe index is computed as hash mod the table size.
11 Subsequent probe indices are computed as explained in Objects/dictobject.c.
12
13 To improve cache locality, each probe inspects a series of consecutive
14 nearby entries before moving on to probes elsewhere in memory. This leaves
15 us with a hybrid of linear probing and open addressing. The linear probing
16 reduces the cost of hash collisions because consecutive memory accesses
17 tend to be much cheaper than scattered probes. After LINEAR_PROBES steps,
18 we then use open addressing with the upper bits from the hash value. This
19 helps break-up long chains of collisions.
20
21 All arithmetic on hash should ignore overflow.
22
Raymond Hettinger4d45c102015-01-25 16:27:40 -080023 Unlike the dictionary implementation, the lookkey function can return
Raymond Hettingerae7b00e2013-09-07 15:05:00 -070024 NULL if the rich comparison returns an error.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000025*/
26
Raymond Hettingera690a992003-11-16 16:17:49 +000027#include "Python.h"
Raymond Hettingera9d99362005-08-05 00:01:15 +000028#include "structmember.h"
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000029
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000030/* Object used as dummy key to fill deleted entries */
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -050031static PyObject _dummy_struct;
32
33#define dummy (&_dummy_struct)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000034
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000035
Raymond Hettinger04fd9dd2013-09-07 17:41:01 -070036/* ======================================================================== */
37/* ======= Begin logic for probing the hash table ========================= */
38
Raymond Hettinger710a67e2013-09-21 20:17:31 -070039/* Set this to zero to turn-off linear probing */
Raymond Hettinger8408dc52013-09-15 14:57:15 -070040#ifndef LINEAR_PROBES
Raymond Hettinger742d8712013-09-08 00:25:57 -070041#define LINEAR_PROBES 9
Raymond Hettinger8408dc52013-09-15 14:57:15 -070042#endif
Raymond Hettinger742d8712013-09-08 00:25:57 -070043
44/* This must be >= 1 */
45#define PERTURB_SHIFT 5
46
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000047static setentry *
Antoine Pitrou9ed5f272013-08-13 20:18:52 +020048set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000049{
Raymond Hettinger70559b52015-07-23 07:42:23 -040050 setentry *table;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +020051 setentry *entry;
Raymond Hettinger38bb95e2015-06-24 01:22:19 -070052 size_t perturb;
Raymond Hettingerafe89092013-08-28 20:59:31 -070053 size_t mask = so->mask;
Raymond Hettinger59ecabd2015-01-31 02:45:12 -080054 size_t i = (size_t)hash & mask; /* Unsigned for defined overflow behavior */
Raymond Hettinger8408dc52013-09-15 14:57:15 -070055 size_t j;
Raymond Hettinger4ef05282013-09-21 15:39:49 -070056 int cmp;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000057
Raymond Hettinger70559b52015-07-23 07:42:23 -040058 entry = &so->table[i];
Raymond Hettingerafe89092013-08-28 20:59:31 -070059 if (entry->key == NULL)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000060 return entry;
Raymond Hettinger237b34b2013-08-17 02:31:53 -070061
Raymond Hettinger38bb95e2015-06-24 01:22:19 -070062 perturb = hash;
63
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -070064 while (1) {
Raymond Hettingera5ebbf62015-01-26 21:54:35 -080065 if (entry->hash == hash) {
Raymond Hettingerafe89092013-08-28 20:59:31 -070066 PyObject *startkey = entry->key;
Raymond Hettingera5ebbf62015-01-26 21:54:35 -080067 /* startkey cannot be a dummy because the dummy hash field is -1 */
68 assert(startkey != dummy);
Raymond Hettinger08e3dc02014-12-26 20:14:00 -080069 if (startkey == key)
70 return entry;
Raymond Hettinger93035c42015-01-25 16:12:49 -080071 if (PyUnicode_CheckExact(startkey)
72 && PyUnicode_CheckExact(key)
Raymond Hettingerac2ef652015-07-04 16:04:44 -070073 && _PyUnicode_EQ(startkey, key))
Raymond Hettinger93035c42015-01-25 16:12:49 -080074 return entry;
Raymond Hettinger70559b52015-07-23 07:42:23 -040075 table = so->table;
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;
Raymond Hettinger438f9132015-02-09 06:48:29 -060085 mask = so->mask; /* help avoid a register spill */
Raymond Hettingerafe89092013-08-28 20:59:31 -070086 }
Raymond Hettingerafe89092013-08-28 20:59:31 -070087
Raymond Hettingerc658d852015-02-02 08:35:00 -080088 if (i + LINEAR_PROBES <= mask) {
Raymond Hettinger82492822015-02-04 08:37:02 -080089 for (j = 0 ; j < LINEAR_PROBES ; j++) {
Raymond Hettingerc658d852015-02-02 08:35:00 -080090 entry++;
Raymond Hettinger8651a502015-05-27 10:37:20 -070091 if (entry->hash == 0 && entry->key == NULL)
92 return entry;
Raymond Hettingerc658d852015-02-02 08:35:00 -080093 if (entry->hash == hash) {
94 PyObject *startkey = entry->key;
95 assert(startkey != dummy);
96 if (startkey == key)
97 return entry;
98 if (PyUnicode_CheckExact(startkey)
99 && PyUnicode_CheckExact(key)
Raymond Hettingerac2ef652015-07-04 16:04:44 -0700100 && _PyUnicode_EQ(startkey, key))
Raymond Hettingerc658d852015-02-02 08:35:00 -0800101 return entry;
Raymond Hettinger70559b52015-07-23 07:42:23 -0400102 table = so->table;
Raymond Hettingerc658d852015-02-02 08:35:00 -0800103 Py_INCREF(startkey);
104 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
105 Py_DECREF(startkey);
106 if (cmp < 0)
107 return NULL;
108 if (table != so->table || entry->key != startkey)
109 return set_lookkey(so, key, hash);
110 if (cmp > 0)
111 return entry;
Raymond Hettinger438f9132015-02-09 06:48:29 -0600112 mask = so->mask;
Raymond Hettingerc658d852015-02-02 08:35:00 -0800113 }
Raymond Hettinger8651a502015-05-27 10:37:20 -0700114 }
115 }
116
117 perturb >>= PERTURB_SHIFT;
118 i = (i * 5 + 1 + perturb) & mask;
119
Raymond Hettinger70559b52015-07-23 07:42:23 -0400120 entry = &so->table[i];
Raymond Hettinger7e3592d2015-06-21 10:47:20 -0700121 if (entry->key == NULL)
Raymond Hettinger8651a502015-05-27 10:37:20 -0700122 return entry;
123 }
124}
125
Raymond Hettinger15f08692015-07-03 17:21:17 -0700126static int set_table_resize(PySetObject *, Py_ssize_t);
127
Raymond Hettinger8651a502015-05-27 10:37:20 -0700128static int
Raymond Hettingerff9e18a2015-07-20 07:34:05 -0400129set_add_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger8651a502015-05-27 10:37:20 -0700130{
Raymond Hettingerff9e18a2015-07-20 07:34:05 -0400131 setentry *table;
Raymond Hettinger38bb95e2015-06-24 01:22:19 -0700132 setentry *freeslot;
Raymond Hettinger8651a502015-05-27 10:37:20 -0700133 setentry *entry;
Raymond Hettinger38bb95e2015-06-24 01:22:19 -0700134 size_t perturb;
Raymond Hettingerff9e18a2015-07-20 07:34:05 -0400135 size_t mask;
136 size_t i; /* Unsigned for defined overflow behavior */
Raymond Hettinger8651a502015-05-27 10:37:20 -0700137 size_t j;
138 int cmp;
139
Raymond Hettingerff9e18a2015-07-20 07:34:05 -0400140 /* Pre-increment is necessary to prevent arbitrary code in the rich
141 comparison from deallocating the key just before the insertion. */
142 Py_INCREF(key);
143
144 restart:
145
Raymond Hettingerff9e18a2015-07-20 07:34:05 -0400146 mask = so->mask;
147 i = (size_t)hash & mask;
148
Raymond Hettinger70559b52015-07-23 07:42:23 -0400149 entry = &so->table[i];
Raymond Hettinger8651a502015-05-27 10:37:20 -0700150 if (entry->key == NULL)
Raymond Hettinger15f08692015-07-03 17:21:17 -0700151 goto found_unused;
Raymond Hettinger6ee588f2015-06-20 21:39:51 -0700152
153 freeslot = NULL;
154 perturb = hash;
Raymond Hettinger8651a502015-05-27 10:37:20 -0700155
156 while (1) {
157 if (entry->hash == hash) {
158 PyObject *startkey = entry->key;
159 /* startkey cannot be a dummy because the dummy hash field is -1 */
160 assert(startkey != dummy);
161 if (startkey == key)
162 goto found_active;
163 if (PyUnicode_CheckExact(startkey)
164 && PyUnicode_CheckExact(key)
Raymond Hettingerac2ef652015-07-04 16:04:44 -0700165 && _PyUnicode_EQ(startkey, key))
Raymond Hettinger8651a502015-05-27 10:37:20 -0700166 goto found_active;
Raymond Hettinger70559b52015-07-23 07:42:23 -0400167 table = so->table;
Raymond Hettinger8651a502015-05-27 10:37:20 -0700168 Py_INCREF(startkey);
169 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
170 Py_DECREF(startkey);
Raymond Hettinger8651a502015-05-27 10:37:20 -0700171 if (cmp > 0) /* likely */
172 goto found_active;
Raymond Hettingerdaffc912015-07-31 07:58:56 -0700173 if (cmp < 0)
174 goto comparison_error;
175 /* Continuing the search from the current entry only makes
176 sense if the table and entry are unchanged; otherwise,
177 we have to restart from the beginning */
178 if (table != so->table || entry->key != startkey)
179 goto restart;
Raymond Hettinger8651a502015-05-27 10:37:20 -0700180 mask = so->mask; /* help avoid a register spill */
181 }
Raymond Hettinger70559b52015-07-23 07:42:23 -0400182 else if (entry->hash == -1 && freeslot == NULL)
Raymond Hettinger8651a502015-05-27 10:37:20 -0700183 freeslot = entry;
184
185 if (i + LINEAR_PROBES <= mask) {
186 for (j = 0 ; j < LINEAR_PROBES ; j++) {
187 entry++;
188 if (entry->hash == 0 && entry->key == NULL)
Raymond Hettinger15f08692015-07-03 17:21:17 -0700189 goto found_unused_or_dummy;
Raymond Hettinger8651a502015-05-27 10:37:20 -0700190 if (entry->hash == hash) {
191 PyObject *startkey = entry->key;
192 assert(startkey != dummy);
193 if (startkey == key)
194 goto found_active;
195 if (PyUnicode_CheckExact(startkey)
196 && PyUnicode_CheckExact(key)
Raymond Hettingerac2ef652015-07-04 16:04:44 -0700197 && _PyUnicode_EQ(startkey, key))
Raymond Hettinger8651a502015-05-27 10:37:20 -0700198 goto found_active;
Raymond Hettinger70559b52015-07-23 07:42:23 -0400199 table = so->table;
Raymond Hettinger8651a502015-05-27 10:37:20 -0700200 Py_INCREF(startkey);
201 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
202 Py_DECREF(startkey);
Raymond Hettingerdaffc912015-07-31 07:58:56 -0700203 if (cmp > 0)
204 goto found_active;
Raymond Hettinger8651a502015-05-27 10:37:20 -0700205 if (cmp < 0)
Raymond Hettingerff9e18a2015-07-20 07:34:05 -0400206 goto comparison_error;
Raymond Hettinger8651a502015-05-27 10:37:20 -0700207 if (table != so->table || entry->key != startkey)
Raymond Hettingerff9e18a2015-07-20 07:34:05 -0400208 goto restart;
Raymond Hettinger8651a502015-05-27 10:37:20 -0700209 mask = so->mask;
210 }
Raymond Hettinger91672612015-06-26 02:50:21 -0700211 else if (entry->hash == -1 && freeslot == NULL)
Raymond Hettingerc658d852015-02-02 08:35:00 -0800212 freeslot = entry;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700213 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000214 }
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700215
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700216 perturb >>= PERTURB_SHIFT;
Raymond Hettinger59ecabd2015-01-31 02:45:12 -0800217 i = (i * 5 + 1 + perturb) & mask;
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700218
Raymond Hettinger70559b52015-07-23 07:42:23 -0400219 entry = &so->table[i];
Raymond Hettinger7e3592d2015-06-21 10:47:20 -0700220 if (entry->key == NULL)
Raymond Hettinger15f08692015-07-03 17:21:17 -0700221 goto found_unused_or_dummy;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000222 }
Raymond Hettinger8651a502015-05-27 10:37:20 -0700223
Raymond Hettinger15f08692015-07-03 17:21:17 -0700224 found_unused_or_dummy:
225 if (freeslot == NULL)
226 goto found_unused;
Raymond Hettinger15f08692015-07-03 17:21:17 -0700227 so->used++;
228 freeslot->key = key;
229 freeslot->hash = hash;
230 return 0;
231
232 found_unused:
Raymond Hettinger6ee588f2015-06-20 21:39:51 -0700233 so->fill++;
234 so->used++;
235 entry->key = key;
236 entry->hash = hash;
Raymond Hettinger15f08692015-07-03 17:21:17 -0700237 if ((size_t)so->fill*3 < mask*2)
238 return 0;
Raymond Hettingerff9e18a2015-07-20 07:34:05 -0400239 return set_table_resize(so, so->used);
Raymond Hettinger8651a502015-05-27 10:37:20 -0700240
241 found_active:
Raymond Hettinger482c05c2015-07-20 01:23:32 -0400242 Py_DECREF(key);
Raymond Hettinger8651a502015-05-27 10:37:20 -0700243 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000244
Raymond Hettingerff9e18a2015-07-20 07:34:05 -0400245 comparison_error:
Raymond Hettinger061091a2015-07-15 23:54:02 -0700246 Py_DECREF(key);
247 return -1;
248}
249
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000250/*
Thomas Wouters89f507f2006-12-13 04:49:30 +0000251Internal routine used by set_table_resize() to insert an item which is
252known to be absent from the set. This routine also assumes that
253the set contains no deleted entries. Besides the performance benefit,
Raymond Hettinger6019c8c2015-11-17 08:28:07 -0800254there is also safety benefit since using set_add_entry() risks making
255a callback in the middle of a set_table_resize(), see issue 1456209.
256The caller is responsible for updating the key's reference count and
257the setobject's fill and used fields.
Thomas Wouters89f507f2006-12-13 04:49:30 +0000258*/
259static void
Raymond Hettinger5088f602015-12-13 18:45:01 -0800260set_insert_clean(setentry *table, size_t mask, PyObject *key, Py_hash_t hash)
Thomas Wouters89f507f2006-12-13 04:49:30 +0000261{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200262 setentry *entry;
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700263 size_t perturb = hash;
Raymond Hettinger3037e842015-01-26 21:33:48 -0800264 size_t i = (size_t)hash & mask;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700265 size_t j;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000266
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700267 while (1) {
Raymond Hettinger3037e842015-01-26 21:33:48 -0800268 entry = &table[i];
269 if (entry->key == NULL)
270 goto found_null;
271 if (i + LINEAR_PROBES <= mask) {
Raymond Hettinger82492822015-02-04 08:37:02 -0800272 for (j = 0; j < LINEAR_PROBES; j++) {
Raymond Hettinger9edd7532015-01-30 20:09:23 -0800273 entry++;
Raymond Hettinger3037e842015-01-26 21:33:48 -0800274 if (entry->key == NULL)
275 goto found_null;
276 }
Raymond Hettingera35adf52013-09-02 03:23:21 -0700277 }
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700278 perturb >>= PERTURB_SHIFT;
Raymond Hettinger3037e842015-01-26 21:33:48 -0800279 i = (i * 5 + 1 + perturb) & mask;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000280 }
Raymond Hettingera35adf52013-09-02 03:23:21 -0700281 found_null:
Raymond Hettinger5088f602015-12-13 18:45:01 -0800282 entry->key = key;
Raymond Hettinger86d322f2015-12-13 19:27:17 -0800283 entry->hash = hash;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000284}
285
Raymond Hettinger04fd9dd2013-09-07 17:41:01 -0700286/* ======== End logic for probing the hash table ========================== */
287/* ======================================================================== */
288
Thomas Wouters89f507f2006-12-13 04:49:30 +0000289/*
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000290Restructure the table by allocating a new table and reinserting all
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000291keys again. When entries have been deleted, the new table may
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000292actually be smaller than the old one.
293*/
294static int
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000295set_table_resize(PySetObject *so, Py_ssize_t minused)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000296{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000297 Py_ssize_t newsize;
298 setentry *oldtable, *newtable, *entry;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800299 Py_ssize_t oldfill = so->fill;
300 Py_ssize_t oldused = so->used;
Raymond Hettinger5088f602015-12-13 18:45:01 -0800301 Py_ssize_t oldmask = so->mask;
302 size_t newmask;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000303 int is_oldtable_malloced;
304 setentry small_copy[PySet_MINSIZE];
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000305
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000306 assert(minused >= 0);
Raymond Hettinger48973002015-07-03 20:00:03 -0700307 minused = (minused > 50000) ? minused * 2 : minused * 4;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000308
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000309 /* Find the smallest table size > minused. */
Raymond Hettinger426d9952014-05-18 21:40:20 +0100310 /* XXX speed-up with intrinsics */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000311 for (newsize = PySet_MINSIZE;
312 newsize <= minused && newsize > 0;
313 newsize <<= 1)
314 ;
315 if (newsize <= 0) {
316 PyErr_NoMemory();
317 return -1;
318 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000319
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000320 /* Get space for a new table. */
321 oldtable = so->table;
322 assert(oldtable != NULL);
323 is_oldtable_malloced = oldtable != so->smalltable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000324
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000325 if (newsize == PySet_MINSIZE) {
326 /* A large table is shrinking, or we can't get any smaller. */
327 newtable = so->smalltable;
328 if (newtable == oldtable) {
329 if (so->fill == so->used) {
330 /* No dummies, so no point doing anything. */
331 return 0;
332 }
333 /* We're not going to resize it, but rebuild the
334 table anyway to purge old dummy entries.
335 Subtle: This is *necessary* if fill==size,
336 as set_lookkey needs at least one virgin slot to
337 terminate failing searches. If fill < size, it's
338 merely desirable, as dummies slow searches. */
339 assert(so->fill > so->used);
340 memcpy(small_copy, oldtable, sizeof(small_copy));
341 oldtable = small_copy;
342 }
343 }
344 else {
345 newtable = PyMem_NEW(setentry, newsize);
346 if (newtable == NULL) {
347 PyErr_NoMemory();
348 return -1;
349 }
350 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000351
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000352 /* Make the set empty, using the new table. */
353 assert(newtable != oldtable);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000354 memset(newtable, 0, sizeof(setentry) * newsize);
Raymond Hettinger6019c8c2015-11-17 08:28:07 -0800355 so->fill = oldused;
356 so->used = oldused;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800357 so->mask = newsize - 1;
358 so->table = newtable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000359
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000360 /* Copy the data over; this is refcount-neutral for active entries;
361 dummy entries aren't copied over, of course */
Raymond Hettinger5088f602015-12-13 18:45:01 -0800362 newmask = (size_t)so->mask;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800363 if (oldfill == oldused) {
Raymond Hettinger5088f602015-12-13 18:45:01 -0800364 for (entry = oldtable; entry <= oldtable + oldmask; entry++) {
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800365 if (entry->key != NULL) {
Raymond Hettinger5088f602015-12-13 18:45:01 -0800366 set_insert_clean(newtable, newmask, entry->key, entry->hash);
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800367 }
368 }
369 } else {
Raymond Hettinger5088f602015-12-13 18:45:01 -0800370 for (entry = oldtable; entry <= oldtable + oldmask; entry++) {
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800371 if (entry->key != NULL && entry->key != dummy) {
Raymond Hettinger5088f602015-12-13 18:45:01 -0800372 set_insert_clean(newtable, newmask, entry->key, entry->hash);
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800373 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000374 }
375 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000376
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000377 if (is_oldtable_malloced)
378 PyMem_DEL(oldtable);
379 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000380}
381
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000382static int
Raymond Hettingerb48d6a62015-07-05 16:27:44 -0700383set_contains_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000384{
Raymond Hettingerb48d6a62015-07-05 16:27:44 -0700385 setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000386
Raymond Hettingerb48d6a62015-07-05 16:27:44 -0700387 entry = set_lookkey(so, key, hash);
388 if (entry != NULL)
389 return entry->key != NULL;
390 return -1;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000391}
392
393#define DISCARD_NOTFOUND 0
394#define DISCARD_FOUND 1
395
396static int
Raymond Hettinger73799b12015-07-05 16:06:10 -0700397set_discard_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger8edf27c2014-12-26 23:08:58 -0800398{
399 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000400 PyObject *old_key;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000401
Raymond Hettingerdc28d5a2015-07-05 10:03:20 -0700402 entry = set_lookkey(so, key, hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000403 if (entry == NULL)
404 return -1;
Raymond Hettinger8651a502015-05-27 10:37:20 -0700405 if (entry->key == NULL)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000406 return DISCARD_NOTFOUND;
407 old_key = entry->key;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000408 entry->key = dummy;
Raymond Hettingerb335dfe2015-01-25 16:38:52 -0800409 entry->hash = -1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000410 so->used--;
411 Py_DECREF(old_key);
412 return DISCARD_FOUND;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000413}
414
415static int
Raymond Hettingerb48d6a62015-07-05 16:27:44 -0700416set_add_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000417{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200418 Py_hash_t hash;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000419
Raymond Hettingerb48d6a62015-07-05 16:27:44 -0700420 if (!PyUnicode_CheckExact(key) ||
421 (hash = ((PyASCIIObject *) key)->hash) == -1) {
422 hash = PyObject_Hash(key);
423 if (hash == -1)
424 return -1;
425 }
426 return set_add_entry(so, key, hash);
427}
428
429static int
430set_contains_key(PySetObject *so, PyObject *key)
431{
432 Py_hash_t hash;
433
434 if (!PyUnicode_CheckExact(key) ||
435 (hash = ((PyASCIIObject *) key)->hash) == -1) {
436 hash = PyObject_Hash(key);
437 if (hash == -1)
438 return -1;
439 }
440 return set_contains_entry(so, key, hash);
441}
442
443static int
444set_discard_key(PySetObject *so, PyObject *key)
445{
446 Py_hash_t hash;
Christian Heimes0ded5b52007-12-10 15:50:56 +0000447
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000448 if (!PyUnicode_CheckExact(key) ||
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200449 (hash = ((PyASCIIObject *) key)->hash) == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000450 hash = PyObject_Hash(key);
451 if (hash == -1)
452 return -1;
453 }
Raymond Hettinger73799b12015-07-05 16:06:10 -0700454 return set_discard_entry(so, key, hash);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000455}
456
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700457static void
458set_empty_to_minsize(PySetObject *so)
459{
460 memset(so->smalltable, 0, sizeof(so->smalltable));
461 so->fill = 0;
462 so->used = 0;
463 so->mask = PySet_MINSIZE - 1;
464 so->table = so->smalltable;
465 so->hash = -1;
466}
467
Raymond Hettingerfe889f32005-08-06 05:43:39 +0000468static int
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000469set_clear_internal(PySetObject *so)
470{
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800471 setentry *entry;
472 setentry *table = so->table;
473 Py_ssize_t fill = so->fill;
474 Py_ssize_t used = so->used;
475 int table_is_malloced = table != so->smalltable;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000476 setentry small_copy[PySet_MINSIZE];
Raymond Hettingera580c472005-08-05 17:19:54 +0000477
Raymond Hettinger583cd032013-09-07 22:06:35 -0700478 assert (PyAnySet_Check(so));
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000479 assert(table != NULL);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000480
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000481 /* This is delicate. During the process of clearing the set,
482 * decrefs can cause the set to mutate. To avoid fatal confusion
483 * (voice of experience), we have to make the set empty before
484 * clearing the slots, and never refer to anything via so->ref while
485 * clearing.
486 */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000487 if (table_is_malloced)
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700488 set_empty_to_minsize(so);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000489
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000490 else if (fill > 0) {
491 /* It's a small table with something that needs to be cleared.
492 * Afraid the only safe way is to copy the set entries into
493 * another small table first.
494 */
495 memcpy(small_copy, table, sizeof(small_copy));
496 table = small_copy;
Raymond Hettinger4ea90802013-09-07 21:01:29 -0700497 set_empty_to_minsize(so);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000498 }
499 /* else it's a small table that's already empty */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000500
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000501 /* Now we can finally clear things. If C had refcounts, we could
502 * assert that the refcount on table is 1 now, i.e. that this function
503 * has unique access to it, so decref side-effects can't alter it.
504 */
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800505 for (entry = table; used > 0; entry++) {
506 if (entry->key && entry->key != dummy) {
507 used--;
508 Py_DECREF(entry->key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000509 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000510 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000511
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000512 if (table_is_malloced)
513 PyMem_DEL(table);
514 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000515}
516
517/*
518 * Iterate over a set table. Use like so:
519 *
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000520 * Py_ssize_t pos;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000521 * setentry *entry;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000522 * pos = 0; # important! pos should not otherwise be changed by you
Raymond Hettingerc991db22005-08-11 07:58:45 +0000523 * while (set_next(yourset, &pos, &entry)) {
524 * Refer to borrowed reference in entry->key.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000525 * }
526 *
Raymond Hettingerc991db22005-08-11 07:58:45 +0000527 * CAUTION: In general, it isn't safe to use set_next in a loop that
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000528 * mutates the table.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000529 */
530static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000531set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000532{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000533 Py_ssize_t i;
534 Py_ssize_t mask;
Raymond Hettingeref6bd7d2015-07-06 08:43:37 -0700535 setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000536
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000537 assert (PyAnySet_Check(so));
538 i = *pos_ptr;
539 assert(i >= 0);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000540 mask = so->mask;
Raymond Hettingeref6bd7d2015-07-06 08:43:37 -0700541 entry = &so->table[i];
542 while (i <= mask && (entry->key == NULL || entry->key == dummy)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000543 i++;
Raymond Hettingeref6bd7d2015-07-06 08:43:37 -0700544 entry++;
545 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000546 *pos_ptr = i+1;
547 if (i > mask)
548 return 0;
Raymond Hettingeref6bd7d2015-07-06 08:43:37 -0700549 assert(entry != NULL);
550 *entry_ptr = entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000551 return 1;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000552}
553
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000554static void
555set_dealloc(PySetObject *so)
556{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200557 setentry *entry;
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800558 Py_ssize_t used = so->used;
559
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000560 PyObject_GC_UnTrack(so);
561 Py_TRASHCAN_SAFE_BEGIN(so)
562 if (so->weakreflist != NULL)
563 PyObject_ClearWeakRefs((PyObject *) so);
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000564
Raymond Hettinger08e3dc02014-12-26 20:14:00 -0800565 for (entry = so->table; used > 0; entry++) {
566 if (entry->key && entry->key != dummy) {
567 used--;
Raymond Hettingerfcf3b502013-08-22 08:20:31 -0700568 Py_DECREF(entry->key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000569 }
570 }
571 if (so->table != so->smalltable)
572 PyMem_DEL(so->table);
Raymond Hettinger8f8839e2013-09-07 20:26:50 -0700573 Py_TYPE(so)->tp_free(so);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000574 Py_TRASHCAN_SAFE_END(so)
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000575}
576
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000577static PyObject *
578set_repr(PySetObject *so)
579{
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200580 PyObject *result=NULL, *keys, *listrepr, *tmp;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000581 int status = Py_ReprEnter((PyObject*)so);
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000582
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000583 if (status != 0) {
584 if (status < 0)
585 return NULL;
586 return PyUnicode_FromFormat("%s(...)", Py_TYPE(so)->tp_name);
587 }
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000588
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000589 /* shortcut for the empty set */
590 if (!so->used) {
591 Py_ReprLeave((PyObject*)so);
592 return PyUnicode_FromFormat("%s()", Py_TYPE(so)->tp_name);
593 }
Georg Brandlc4996ba2006-08-28 19:37:11 +0000594
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000595 keys = PySequence_List((PyObject *)so);
596 if (keys == NULL)
597 goto done;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000598
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200599 /* repr(keys)[1:-1] */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000600 listrepr = PyObject_Repr(keys);
601 Py_DECREF(keys);
602 if (listrepr == NULL)
603 goto done;
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200604 tmp = PyUnicode_Substring(listrepr, 1, PyUnicode_GET_LENGTH(listrepr)-1);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000605 Py_DECREF(listrepr);
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200606 if (tmp == NULL)
607 goto done;
608 listrepr = tmp;
Victor Stinnera1a807b2011-05-26 14:24:30 +0200609
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200610 if (Py_TYPE(so) != &PySet_Type)
611 result = PyUnicode_FromFormat("%s({%U})",
612 Py_TYPE(so)->tp_name,
613 listrepr);
614 else
615 result = PyUnicode_FromFormat("{%U}", listrepr);
616 Py_DECREF(listrepr);
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000617done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000618 Py_ReprLeave((PyObject*)so);
619 return result;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000620}
621
Martin v. Löwis18e16552006-02-15 17:27:45 +0000622static Py_ssize_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000623set_len(PyObject *so)
624{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000625 return ((PySetObject *)so)->used;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000626}
627
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000628static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000629set_merge(PySetObject *so, PyObject *otherset)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000630{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000631 PySetObject *other;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000632 PyObject *key;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200633 Py_ssize_t i;
Raymond Hettinger1bd8d752015-05-13 01:26:14 -0700634 setentry *so_entry;
635 setentry *other_entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000636
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000637 assert (PyAnySet_Check(so));
638 assert (PyAnySet_Check(otherset));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000639
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000640 other = (PySetObject*)otherset;
641 if (other == so || other->used == 0)
Raymond Hettinger1bd8d752015-05-13 01:26:14 -0700642 /* a.update(a) or a.update(set()); nothing to do */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000643 return 0;
644 /* Do one big resize at the start, rather than
645 * incrementally resizing as we insert new keys. Expect
646 * that there will be no (or few) overlapping keys.
647 */
Raymond Hettinger15f08692015-07-03 17:21:17 -0700648 if ((so->fill + other->used)*3 >= so->mask*2) {
Raymond Hettinger48973002015-07-03 20:00:03 -0700649 if (set_table_resize(so, so->used + other->used) != 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000650 return -1;
651 }
Raymond Hettinger1bd8d752015-05-13 01:26:14 -0700652 so_entry = so->table;
653 other_entry = other->table;
654
655 /* If our table is empty, and both tables have the same size, and
656 there are no dummies to eliminate, then just copy the pointers. */
657 if (so->fill == 0 && so->mask == other->mask && other->fill == other->used) {
658 for (i = 0; i <= other->mask; i++, so_entry++, other_entry++) {
659 key = other_entry->key;
660 if (key != NULL) {
661 assert(so_entry->key == NULL);
662 Py_INCREF(key);
663 so_entry->key = key;
664 so_entry->hash = other_entry->hash;
665 }
666 }
667 so->fill = other->fill;
668 so->used = other->used;
669 return 0;
670 }
671
672 /* If our table is empty, we can use set_insert_clean() */
673 if (so->fill == 0) {
Raymond Hettinger5088f602015-12-13 18:45:01 -0800674 setentry *newtable = so->table;
675 size_t newmask = (size_t)so->mask;
Raymond Hettinger6019c8c2015-11-17 08:28:07 -0800676 so->fill = other->used;
677 so->used = other->used;
Raymond Hettingere4495872015-12-15 00:42:30 -0800678 for (i = other->mask + 1; i > 0 ; i--, other_entry++) {
Raymond Hettinger1bd8d752015-05-13 01:26:14 -0700679 key = other_entry->key;
680 if (key != NULL && key != dummy) {
681 Py_INCREF(key);
Raymond Hettinger5088f602015-12-13 18:45:01 -0800682 set_insert_clean(newtable, newmask, key, other_entry->hash);
Raymond Hettinger1bd8d752015-05-13 01:26:14 -0700683 }
684 }
685 return 0;
686 }
687
688 /* We can't assure there are no duplicates, so do normal insertions */
Raymond Hettingera3626bc2015-07-15 23:50:14 -0700689 for (i = 0; i <= other->mask; i++) {
690 other_entry = &other->table[i];
Raymond Hettinger1bd8d752015-05-13 01:26:14 -0700691 key = other_entry->key;
692 if (key != NULL && key != dummy) {
Raymond Hettinger73799b12015-07-05 16:06:10 -0700693 if (set_add_entry(so, key, other_entry->hash))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000694 return -1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000695 }
696 }
697 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000698}
699
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000700static PyObject *
701set_pop(PySetObject *so)
702{
Raymond Hettinger9cd6a782015-01-18 16:06:18 -0800703 /* Make sure the search finger is in bounds */
704 Py_ssize_t i = so->finger & so->mask;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200705 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000706 PyObject *key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000707
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000708 assert (PyAnySet_Check(so));
709 if (so->used == 0) {
710 PyErr_SetString(PyExc_KeyError, "pop from an empty set");
711 return NULL;
712 }
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000713
Raymond Hettinger1202a472015-01-18 13:12:42 -0800714 while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
715 i++;
Raymond Hettingered741d42015-01-18 21:25:15 -0800716 if (i > so->mask)
717 i = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000718 }
719 key = entry->key;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000720 entry->key = dummy;
Raymond Hettingerb335dfe2015-01-25 16:38:52 -0800721 entry->hash = -1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000722 so->used--;
Raymond Hettinger1202a472015-01-18 13:12:42 -0800723 so->finger = i + 1; /* next place to start */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000724 return key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000725}
726
Benjamin Petersonf10a79a2008-10-11 00:49:57 +0000727PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\
728Raises KeyError if the set is empty.");
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000729
730static int
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000731set_traverse(PySetObject *so, visitproc visit, void *arg)
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000732{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000733 Py_ssize_t pos = 0;
734 setentry *entry;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000735
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000736 while (set_next(so, &pos, &entry))
737 Py_VISIT(entry->key);
738 return 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000739}
740
Raymond Hettingerfbffdef2015-08-01 09:53:00 -0700741/* Work to increase the bit dispersion for closely spaced hash values.
742 This is important because some use cases have many combinations of a
743 small number of elements with nearby hashes so that many distinct
744 combinations collapse to only a handful of distinct hash values. */
745
746static Py_uhash_t
747_shuffle_bits(Py_uhash_t h)
748{
749 return ((h ^ 89869747UL) ^ (h << 16)) * 3644798167UL;
750}
751
752/* Most of the constants in this hash algorithm are randomly chosen
753 large primes with "interesting bit patterns" and that passed tests
754 for good collision statistics on a variety of problematic datasets
755 including powersets and graph structures (such as David Eppstein's
756 graph recipes in Lib/test/test_set.py) */
757
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000758static Py_hash_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000759frozenset_hash(PyObject *self)
760{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000761 PySetObject *so = (PySetObject *)self;
Raymond Hettinger41481952015-08-07 00:43:39 -0700762 Py_uhash_t hash = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000763 setentry *entry;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000764
Raymond Hettingerb501a272015-08-06 22:15:22 -0700765 if (so->hash != -1)
766 return so->hash;
767
Raymond Hettingerfbffdef2015-08-01 09:53:00 -0700768 /* Xor-in shuffled bits from every entry's hash field because xor is
769 commutative and a frozenset hash should be independent of order.
770
771 For speed, include null entries and dummy entries and then
772 subtract out their effect afterwards so that the final hash
773 depends only on active entries. This allows the code to be
774 vectorized by the compiler and it saves the unpredictable
775 branches that would arise when trying to exclude null and dummy
776 entries on every iteration. */
777
778 for (entry = so->table; entry <= &so->table[so->mask]; entry++)
779 hash ^= _shuffle_bits(entry->hash);
780
Raymond Hettingera286a512015-08-01 11:07:11 -0700781 /* Remove the effect of an odd number of NULL entries */
Raymond Hettingerfbffdef2015-08-01 09:53:00 -0700782 if ((so->mask + 1 - so->fill) & 1)
783 hash ^= _shuffle_bits(0);
784
785 /* Remove the effect of an odd number of dummy entries */
786 if ((so->fill - so->used) & 1)
787 hash ^= _shuffle_bits(-1);
788
Raymond Hettinger41481952015-08-07 00:43:39 -0700789 /* Factor in the number of active entries */
790 hash ^= ((Py_uhash_t)PySet_GET_SIZE(self) + 1) * 1927868237UL;
791
Raymond Hettingerfbffdef2015-08-01 09:53:00 -0700792 /* Disperse patterns arising in nested frozensets */
Gregory P. Smithc2176e42012-12-10 18:32:53 -0800793 hash = hash * 69069U + 907133923UL;
Raymond Hettingerfbffdef2015-08-01 09:53:00 -0700794
Raymond Hettinger36c05002015-08-01 10:57:42 -0700795 /* -1 is reserved as an error code */
Victor Stinner12174a52014-08-15 23:17:38 +0200796 if (hash == (Py_uhash_t)-1)
Gregory P. Smith27cbcd62012-12-10 18:15:46 -0800797 hash = 590923713UL;
Raymond Hettinger36c05002015-08-01 10:57:42 -0700798
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000799 so->hash = hash;
800 return hash;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000801}
802
Raymond Hettingera9d99362005-08-05 00:01:15 +0000803/***** Set iterator type ***********************************************/
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000804
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000805typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000806 PyObject_HEAD
807 PySetObject *si_set; /* Set to NULL when iterator is exhausted */
808 Py_ssize_t si_used;
Raymond Hettinger9632a7d2015-07-07 15:29:24 -0700809 Py_ssize_t si_pos;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000810 Py_ssize_t len;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000811} setiterobject;
812
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000813static void
814setiter_dealloc(setiterobject *si)
815{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000816 Py_XDECREF(si->si_set);
817 PyObject_GC_Del(si);
Antoine Pitrou7ddda782009-01-01 15:35:33 +0000818}
819
820static int
821setiter_traverse(setiterobject *si, visitproc visit, void *arg)
822{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000823 Py_VISIT(si->si_set);
824 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000825}
826
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000827static PyObject *
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000828setiter_len(setiterobject *si)
829{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000830 Py_ssize_t len = 0;
831 if (si->si_set != NULL && si->si_used == si->si_set->used)
832 len = si->len;
Antoine Pitrou671b4d92010-08-17 17:55:07 +0000833 return PyLong_FromSsize_t(len);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000834}
835
Armin Rigof5b3e362006-02-11 21:32:43 +0000836PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000837
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000838static PyObject *setiter_iternext(setiterobject *si);
839
840static PyObject *
841setiter_reduce(setiterobject *si)
842{
843 PyObject *list;
844 setiterobject tmp;
845
846 list = PyList_New(0);
847 if (!list)
848 return NULL;
849
Ezio Melotti0e1af282012-09-28 16:43:40 +0300850 /* copy the iterator state */
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000851 tmp = *si;
852 Py_XINCREF(tmp.si_set);
Ezio Melotti0e1af282012-09-28 16:43:40 +0300853
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000854 /* iterate the temporary into a list */
855 for(;;) {
856 PyObject *element = setiter_iternext(&tmp);
857 if (element) {
858 if (PyList_Append(list, element)) {
859 Py_DECREF(element);
860 Py_DECREF(list);
861 Py_XDECREF(tmp.si_set);
862 return NULL;
863 }
864 Py_DECREF(element);
865 } else
866 break;
867 }
868 Py_XDECREF(tmp.si_set);
869 /* check for error */
870 if (tmp.si_set != NULL) {
871 /* we have an error */
872 Py_DECREF(list);
873 return NULL;
874 }
Antoine Pitroua7013882012-04-05 00:04:20 +0200875 return Py_BuildValue("N(N)", _PyObject_GetBuiltin("iter"), list);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000876}
877
878PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
879
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000880static PyMethodDef setiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000881 {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000882 {"__reduce__", (PyCFunction)setiter_reduce, METH_NOARGS, reduce_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000883 {NULL, NULL} /* sentinel */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000884};
885
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000886static PyObject *setiter_iternext(setiterobject *si)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000887{
Raymond Hettinger9632a7d2015-07-07 15:29:24 -0700888 PyObject *key;
889 Py_ssize_t i, mask;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200890 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000891 PySetObject *so = si->si_set;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000892
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000893 if (so == NULL)
894 return NULL;
895 assert (PyAnySet_Check(so));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000896
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000897 if (si->si_used != so->used) {
898 PyErr_SetString(PyExc_RuntimeError,
899 "Set changed size during iteration");
900 si->si_used = -1; /* Make this state sticky */
901 return NULL;
902 }
Raymond Hettinger9632a7d2015-07-07 15:29:24 -0700903
904 i = si->si_pos;
905 assert(i>=0);
906 entry = so->table;
907 mask = so->mask;
908 while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
909 i++;
910 si->si_pos = i+1;
911 if (i > mask)
912 goto fail;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000913 si->len--;
Raymond Hettinger9632a7d2015-07-07 15:29:24 -0700914 key = entry[i].key;
915 Py_INCREF(key);
916 return key;
917
918fail:
Raymond Hettinger9632a7d2015-07-07 15:29:24 -0700919 si->si_set = NULL;
Serhiy Storchakafbb1c5e2016-03-30 20:40:02 +0300920 Py_DECREF(so);
Raymond Hettinger9632a7d2015-07-07 15:29:24 -0700921 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000922}
923
Christian Heimesa22e8bd2007-11-29 22:35:39 +0000924PyTypeObject PySetIter_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000925 PyVarObject_HEAD_INIT(&PyType_Type, 0)
926 "set_iterator", /* tp_name */
927 sizeof(setiterobject), /* tp_basicsize */
928 0, /* tp_itemsize */
929 /* methods */
930 (destructor)setiter_dealloc, /* tp_dealloc */
931 0, /* tp_print */
932 0, /* tp_getattr */
933 0, /* tp_setattr */
934 0, /* tp_reserved */
935 0, /* tp_repr */
936 0, /* tp_as_number */
937 0, /* tp_as_sequence */
938 0, /* tp_as_mapping */
939 0, /* tp_hash */
940 0, /* tp_call */
941 0, /* tp_str */
942 PyObject_GenericGetAttr, /* tp_getattro */
943 0, /* tp_setattro */
944 0, /* tp_as_buffer */
Raymond Hettinger5d2385f2015-07-08 11:52:27 -0700945 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000946 0, /* tp_doc */
947 (traverseproc)setiter_traverse, /* tp_traverse */
948 0, /* tp_clear */
949 0, /* tp_richcompare */
950 0, /* tp_weaklistoffset */
951 PyObject_SelfIter, /* tp_iter */
952 (iternextfunc)setiter_iternext, /* tp_iternext */
953 setiter_methods, /* tp_methods */
954 0,
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000955};
956
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000957static PyObject *
958set_iter(PySetObject *so)
959{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000960 setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type);
961 if (si == NULL)
962 return NULL;
963 Py_INCREF(so);
964 si->si_set = so;
965 si->si_used = so->used;
Raymond Hettinger9632a7d2015-07-07 15:29:24 -0700966 si->si_pos = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000967 si->len = so->used;
968 _PyObject_GC_TRACK(si);
969 return (PyObject *)si;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000970}
971
Raymond Hettingerd7946662005-08-01 21:39:29 +0000972static int
Raymond Hettingerd7946662005-08-01 21:39:29 +0000973set_update_internal(PySetObject *so, PyObject *other)
Raymond Hettingera690a992003-11-16 16:17:49 +0000974{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000975 PyObject *key, *it;
Raymond Hettingera690a992003-11-16 16:17:49 +0000976
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000977 if (PyAnySet_Check(other))
978 return set_merge(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +0000979
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000980 if (PyDict_CheckExact(other)) {
981 PyObject *value;
982 Py_ssize_t pos = 0;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000983 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000984 Py_ssize_t dictsize = PyDict_Size(other);
Thomas Wouterscf297e42007-02-23 15:07:44 +0000985
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000986 /* Do one big resize at the start, rather than
987 * incrementally resizing as we insert new keys. Expect
988 * that there will be no (or few) overlapping keys.
989 */
Raymond Hettingerc2480dc2015-07-04 08:46:31 -0700990 if (dictsize < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000991 return -1;
Raymond Hettinger15f08692015-07-03 17:21:17 -0700992 if ((so->fill + dictsize)*3 >= so->mask*2) {
Raymond Hettinger48973002015-07-03 20:00:03 -0700993 if (set_table_resize(so, so->used + dictsize) != 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000994 return -1;
995 }
996 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
Raymond Hettinger73799b12015-07-05 16:06:10 -0700997 if (set_add_entry(so, key, hash))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000998 return -1;
999 }
1000 return 0;
1001 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001002
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001003 it = PyObject_GetIter(other);
1004 if (it == NULL)
1005 return -1;
Raymond Hettingera690a992003-11-16 16:17:49 +00001006
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001007 while ((key = PyIter_Next(it)) != NULL) {
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001008 if (set_add_key(so, key)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001009 Py_DECREF(it);
1010 Py_DECREF(key);
1011 return -1;
1012 }
1013 Py_DECREF(key);
1014 }
1015 Py_DECREF(it);
1016 if (PyErr_Occurred())
1017 return -1;
1018 return 0;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001019}
1020
1021static PyObject *
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001022set_update(PySetObject *so, PyObject *args)
Raymond Hettingerd7946662005-08-01 21:39:29 +00001023{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001024 Py_ssize_t i;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001025
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001026 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1027 PyObject *other = PyTuple_GET_ITEM(args, i);
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001028 if (set_update_internal(so, other))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001029 return NULL;
1030 }
1031 Py_RETURN_NONE;
Raymond Hettingera38123e2003-11-24 22:18:49 +00001032}
1033
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001034PyDoc_STRVAR(update_doc,
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001035"Update a set with the union of itself and others.");
Raymond Hettingera38123e2003-11-24 22:18:49 +00001036
Raymond Hettinger426d9952014-05-18 21:40:20 +01001037/* XXX Todo:
1038 If aligned memory allocations become available, make the
1039 set object 64 byte aligned so that most of the fields
1040 can be retrieved or updated in a single cache line.
1041*/
1042
Raymond Hettingera38123e2003-11-24 22:18:49 +00001043static PyObject *
1044make_new_set(PyTypeObject *type, PyObject *iterable)
1045{
Raymond Hettinger8421d712016-04-29 01:37:05 -07001046 PySetObject *so;
Raymond Hettingera38123e2003-11-24 22:18:49 +00001047
Raymond Hettinger8f8839e2013-09-07 20:26:50 -07001048 so = (PySetObject *)type->tp_alloc(type, 0);
1049 if (so == NULL)
1050 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001051
Raymond Hettinger4ea90802013-09-07 21:01:29 -07001052 so->fill = 0;
1053 so->used = 0;
1054 so->mask = PySet_MINSIZE - 1;
1055 so->table = so->smalltable;
Raymond Hettinger4ea90802013-09-07 21:01:29 -07001056 so->hash = -1;
Raymond Hettinger1202a472015-01-18 13:12:42 -08001057 so->finger = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001058 so->weakreflist = NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001059
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001060 if (iterable != NULL) {
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001061 if (set_update_internal(so, iterable)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001062 Py_DECREF(so);
1063 return NULL;
1064 }
1065 }
Raymond Hettingera38123e2003-11-24 22:18:49 +00001066
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001067 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001068}
1069
Raymond Hettinger7d99f092008-11-16 11:44:54 +00001070static PyObject *
1071make_new_set_basetype(PyTypeObject *type, PyObject *iterable)
1072{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001073 if (type != &PySet_Type && type != &PyFrozenSet_Type) {
1074 if (PyType_IsSubtype(type, &PySet_Type))
1075 type = &PySet_Type;
1076 else
1077 type = &PyFrozenSet_Type;
1078 }
1079 return make_new_set(type, iterable);
Raymond Hettinger7d99f092008-11-16 11:44:54 +00001080}
1081
Raymond Hettingerd7946662005-08-01 21:39:29 +00001082/* The empty frozenset is a singleton */
1083static PyObject *emptyfrozenset = NULL;
1084
Raymond Hettingera690a992003-11-16 16:17:49 +00001085static PyObject *
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001086frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
Raymond Hettingera690a992003-11-16 16:17:49 +00001087{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001088 PyObject *iterable = NULL, *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001089
Raymond Hettingerf5021542016-02-04 02:46:16 -08001090 if (kwds != NULL && type == &PyFrozenSet_Type
1091 && !_PyArg_NoKeywords("frozenset()", kwds))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001092 return NULL;
Georg Brandl02c42872005-08-26 06:42:30 +00001093
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001094 if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
1095 return NULL;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001096
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001097 if (type != &PyFrozenSet_Type)
1098 return make_new_set(type, iterable);
Raymond Hettingerd7946662005-08-01 21:39:29 +00001099
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001100 if (iterable != NULL) {
1101 /* frozenset(f) is idempotent */
1102 if (PyFrozenSet_CheckExact(iterable)) {
1103 Py_INCREF(iterable);
1104 return iterable;
1105 }
1106 result = make_new_set(type, iterable);
1107 if (result == NULL || PySet_GET_SIZE(result))
1108 return result;
1109 Py_DECREF(result);
1110 }
1111 /* The empty frozenset is a singleton */
1112 if (emptyfrozenset == NULL)
1113 emptyfrozenset = make_new_set(type, NULL);
1114 Py_XINCREF(emptyfrozenset);
1115 return emptyfrozenset;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001116}
1117
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001118static PyObject *
1119set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1120{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001121 return make_new_set(type, NULL);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001122}
1123
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001124/* set_swap_bodies() switches the contents of any two sets by moving their
1125 internal data pointers and, if needed, copying the internal smalltables.
1126 Semantically equivalent to:
1127
1128 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1129
1130 The function always succeeds and it leaves both objects in a stable state.
Raymond Hettinger4d45c102015-01-25 16:27:40 -08001131 Useful for operations that update in-place (by allowing an intermediate
1132 result to be swapped into one of the original inputs).
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001133*/
1134
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001135static void
1136set_swap_bodies(PySetObject *a, PySetObject *b)
Raymond Hettingera690a992003-11-16 16:17:49 +00001137{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001138 Py_ssize_t t;
1139 setentry *u;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001140 setentry tab[PySet_MINSIZE];
Antoine Pitroufbb1c612010-10-23 17:37:54 +00001141 Py_hash_t h;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001142
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001143 t = a->fill; a->fill = b->fill; b->fill = t;
1144 t = a->used; a->used = b->used; b->used = t;
1145 t = a->mask; a->mask = b->mask; b->mask = t;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001146
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001147 u = a->table;
1148 if (a->table == a->smalltable)
1149 u = b->smalltable;
1150 a->table = b->table;
1151 if (b->table == b->smalltable)
1152 a->table = a->smalltable;
1153 b->table = u;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001154
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001155 if (a->table == a->smalltable || b->table == b->smalltable) {
1156 memcpy(tab, a->smalltable, sizeof(tab));
1157 memcpy(a->smalltable, b->smalltable, sizeof(tab));
1158 memcpy(b->smalltable, tab, sizeof(tab));
1159 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001160
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001161 if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type) &&
1162 PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) {
1163 h = a->hash; a->hash = b->hash; b->hash = h;
1164 } else {
1165 a->hash = -1;
1166 b->hash = -1;
1167 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001168}
1169
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001170static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001171set_copy(PySetObject *so)
1172{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001173 return make_new_set_basetype(Py_TYPE(so), (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001174}
1175
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001176static PyObject *
1177frozenset_copy(PySetObject *so)
1178{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001179 if (PyFrozenSet_CheckExact(so)) {
1180 Py_INCREF(so);
1181 return (PyObject *)so;
1182 }
1183 return set_copy(so);
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001184}
1185
Raymond Hettingera690a992003-11-16 16:17:49 +00001186PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
1187
1188static PyObject *
Raymond Hettingerc991db22005-08-11 07:58:45 +00001189set_clear(PySetObject *so)
1190{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001191 set_clear_internal(so);
1192 Py_RETURN_NONE;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001193}
1194
1195PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
1196
1197static PyObject *
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001198set_union(PySetObject *so, PyObject *args)
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001199{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001200 PySetObject *result;
1201 PyObject *other;
1202 Py_ssize_t i;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001203
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001204 result = (PySetObject *)set_copy(so);
1205 if (result == NULL)
1206 return NULL;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001207
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001208 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1209 other = PyTuple_GET_ITEM(args, i);
1210 if ((PyObject *)so == other)
1211 continue;
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001212 if (set_update_internal(result, other)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001213 Py_DECREF(result);
1214 return NULL;
1215 }
1216 }
1217 return (PyObject *)result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001218}
1219
1220PyDoc_STRVAR(union_doc,
1221 "Return the union of sets as a new set.\n\
1222\n\
1223(i.e. all elements that are in either set.)");
1224
1225static PyObject *
1226set_or(PySetObject *so, PyObject *other)
1227{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001228 PySetObject *result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001229
Brian Curtindfc80e32011-08-10 20:28:54 -05001230 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1231 Py_RETURN_NOTIMPLEMENTED;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001232
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001233 result = (PySetObject *)set_copy(so);
1234 if (result == NULL)
1235 return NULL;
1236 if ((PyObject *)so == other)
1237 return (PyObject *)result;
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001238 if (set_update_internal(result, other)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001239 Py_DECREF(result);
1240 return NULL;
1241 }
1242 return (PyObject *)result;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001243}
1244
Raymond Hettingera690a992003-11-16 16:17:49 +00001245static PyObject *
1246set_ior(PySetObject *so, PyObject *other)
1247{
Brian Curtindfc80e32011-08-10 20:28:54 -05001248 if (!PyAnySet_Check(other))
1249 Py_RETURN_NOTIMPLEMENTED;
1250
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001251 if (set_update_internal(so, other))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001252 return NULL;
1253 Py_INCREF(so);
1254 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001255}
1256
1257static PyObject *
1258set_intersection(PySetObject *so, PyObject *other)
1259{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001260 PySetObject *result;
1261 PyObject *key, *it, *tmp;
Raymond Hettinger73799b12015-07-05 16:06:10 -07001262 Py_hash_t hash;
1263 int rv;
Raymond Hettingera690a992003-11-16 16:17:49 +00001264
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001265 if ((PyObject *)so == other)
1266 return set_copy(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001267
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001268 result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL);
1269 if (result == NULL)
1270 return NULL;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001271
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001272 if (PyAnySet_Check(other)) {
1273 Py_ssize_t pos = 0;
1274 setentry *entry;
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001275
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001276 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1277 tmp = (PyObject *)so;
1278 so = (PySetObject *)other;
1279 other = tmp;
1280 }
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001281
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001282 while (set_next((PySetObject *)other, &pos, &entry)) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001283 key = entry->key;
1284 hash = entry->hash;
1285 rv = set_contains_entry(so, key, hash);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001286 if (rv < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001287 Py_DECREF(result);
1288 return NULL;
1289 }
1290 if (rv) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001291 if (set_add_entry(result, key, hash)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001292 Py_DECREF(result);
1293 return NULL;
1294 }
1295 }
1296 }
1297 return (PyObject *)result;
1298 }
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001299
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001300 it = PyObject_GetIter(other);
1301 if (it == NULL) {
1302 Py_DECREF(result);
1303 return NULL;
1304 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001305
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001306 while ((key = PyIter_Next(it)) != NULL) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001307 hash = PyObject_Hash(key);
Raymond Hettinger11ce8e62015-07-06 19:08:49 -07001308 if (hash == -1)
1309 goto error;
Raymond Hettinger73799b12015-07-05 16:06:10 -07001310 rv = set_contains_entry(so, key, hash);
Raymond Hettinger11ce8e62015-07-06 19:08:49 -07001311 if (rv < 0)
1312 goto error;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001313 if (rv) {
Raymond Hettinger11ce8e62015-07-06 19:08:49 -07001314 if (set_add_entry(result, key, hash))
1315 goto error;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001316 }
1317 Py_DECREF(key);
1318 }
1319 Py_DECREF(it);
1320 if (PyErr_Occurred()) {
1321 Py_DECREF(result);
1322 return NULL;
1323 }
1324 return (PyObject *)result;
Raymond Hettinger11ce8e62015-07-06 19:08:49 -07001325 error:
1326 Py_DECREF(it);
1327 Py_DECREF(result);
1328 Py_DECREF(key);
1329 return NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001330}
1331
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001332static PyObject *
1333set_intersection_multi(PySetObject *so, PyObject *args)
1334{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001335 Py_ssize_t i;
1336 PyObject *result = (PyObject *)so;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001337
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001338 if (PyTuple_GET_SIZE(args) == 0)
1339 return set_copy(so);
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001340
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001341 Py_INCREF(so);
1342 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1343 PyObject *other = PyTuple_GET_ITEM(args, i);
1344 PyObject *newresult = set_intersection((PySetObject *)result, other);
1345 if (newresult == NULL) {
1346 Py_DECREF(result);
1347 return NULL;
1348 }
1349 Py_DECREF(result);
1350 result = newresult;
1351 }
1352 return result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001353}
1354
Raymond Hettingera690a992003-11-16 16:17:49 +00001355PyDoc_STRVAR(intersection_doc,
1356"Return the intersection of two sets as a new set.\n\
1357\n\
1358(i.e. all elements that are in both sets.)");
1359
1360static PyObject *
1361set_intersection_update(PySetObject *so, PyObject *other)
1362{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001363 PyObject *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001364
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001365 tmp = set_intersection(so, other);
1366 if (tmp == NULL)
1367 return NULL;
1368 set_swap_bodies(so, (PySetObject *)tmp);
1369 Py_DECREF(tmp);
1370 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001371}
1372
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001373static PyObject *
1374set_intersection_update_multi(PySetObject *so, PyObject *args)
1375{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001376 PyObject *tmp;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001377
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001378 tmp = set_intersection_multi(so, args);
1379 if (tmp == NULL)
1380 return NULL;
1381 set_swap_bodies(so, (PySetObject *)tmp);
1382 Py_DECREF(tmp);
1383 Py_RETURN_NONE;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001384}
1385
Raymond Hettingera690a992003-11-16 16:17:49 +00001386PyDoc_STRVAR(intersection_update_doc,
1387"Update a set with the intersection of itself and another.");
1388
1389static PyObject *
1390set_and(PySetObject *so, PyObject *other)
1391{
Brian Curtindfc80e32011-08-10 20:28:54 -05001392 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1393 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001394 return set_intersection(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001395}
1396
1397static PyObject *
1398set_iand(PySetObject *so, PyObject *other)
1399{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001400 PyObject *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001401
Brian Curtindfc80e32011-08-10 20:28:54 -05001402 if (!PyAnySet_Check(other))
1403 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001404 result = set_intersection_update(so, other);
1405 if (result == NULL)
1406 return NULL;
1407 Py_DECREF(result);
1408 Py_INCREF(so);
1409 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001410}
1411
Guido van Rossum58da9312007-11-10 23:39:45 +00001412static PyObject *
1413set_isdisjoint(PySetObject *so, PyObject *other)
1414{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001415 PyObject *key, *it, *tmp;
Raymond Hettinger73799b12015-07-05 16:06:10 -07001416 int rv;
Guido van Rossum58da9312007-11-10 23:39:45 +00001417
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001418 if ((PyObject *)so == other) {
1419 if (PySet_GET_SIZE(so) == 0)
1420 Py_RETURN_TRUE;
1421 else
1422 Py_RETURN_FALSE;
1423 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001424
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001425 if (PyAnySet_CheckExact(other)) {
1426 Py_ssize_t pos = 0;
1427 setentry *entry;
Guido van Rossum58da9312007-11-10 23:39:45 +00001428
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001429 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1430 tmp = (PyObject *)so;
1431 so = (PySetObject *)other;
1432 other = tmp;
1433 }
1434 while (set_next((PySetObject *)other, &pos, &entry)) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001435 rv = set_contains_entry(so, entry->key, entry->hash);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001436 if (rv < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001437 return NULL;
1438 if (rv)
1439 Py_RETURN_FALSE;
1440 }
1441 Py_RETURN_TRUE;
1442 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001443
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001444 it = PyObject_GetIter(other);
1445 if (it == NULL)
1446 return NULL;
Guido van Rossum58da9312007-11-10 23:39:45 +00001447
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001448 while ((key = PyIter_Next(it)) != NULL) {
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001449 Py_hash_t hash = PyObject_Hash(key);
Guido van Rossum58da9312007-11-10 23:39:45 +00001450
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001451 if (hash == -1) {
1452 Py_DECREF(key);
1453 Py_DECREF(it);
1454 return NULL;
1455 }
Raymond Hettinger73799b12015-07-05 16:06:10 -07001456 rv = set_contains_entry(so, key, hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001457 Py_DECREF(key);
Raymond Hettingerc2480dc2015-07-04 08:46:31 -07001458 if (rv < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001459 Py_DECREF(it);
1460 return NULL;
1461 }
1462 if (rv) {
1463 Py_DECREF(it);
1464 Py_RETURN_FALSE;
1465 }
1466 }
1467 Py_DECREF(it);
1468 if (PyErr_Occurred())
1469 return NULL;
1470 Py_RETURN_TRUE;
Guido van Rossum58da9312007-11-10 23:39:45 +00001471}
1472
1473PyDoc_STRVAR(isdisjoint_doc,
1474"Return True if two sets have a null intersection.");
1475
Neal Norwitz6576bd82005-11-13 18:41:28 +00001476static int
Raymond Hettingerc991db22005-08-11 07:58:45 +00001477set_difference_update_internal(PySetObject *so, PyObject *other)
1478{
Raymond Hettinger4103e4d2016-09-11 22:02:28 -07001479 if (PySet_GET_SIZE(so) == 0) {
1480 return 0;
1481 }
1482
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001483 if ((PyObject *)so == other)
1484 return set_clear_internal(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001485
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001486 if (PyAnySet_Check(other)) {
1487 setentry *entry;
1488 Py_ssize_t pos = 0;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001489
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001490 while (set_next((PySetObject *)other, &pos, &entry))
Raymond Hettinger73799b12015-07-05 16:06:10 -07001491 if (set_discard_entry(so, entry->key, entry->hash) < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001492 return -1;
1493 } else {
1494 PyObject *key, *it;
1495 it = PyObject_GetIter(other);
1496 if (it == NULL)
1497 return -1;
1498
1499 while ((key = PyIter_Next(it)) != NULL) {
Raymond Hettingerb3223262015-07-03 23:37:16 -07001500 if (set_discard_key(so, key) < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001501 Py_DECREF(it);
1502 Py_DECREF(key);
1503 return -1;
1504 }
1505 Py_DECREF(key);
1506 }
1507 Py_DECREF(it);
1508 if (PyErr_Occurred())
1509 return -1;
1510 }
Raymond Hettingere186c762015-07-04 11:28:35 -07001511 /* If more than 1/4th are dummies, then resize them away. */
1512 if ((size_t)(so->fill - so->used) <= (size_t)so->mask / 4)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001513 return 0;
Raymond Hettinger48973002015-07-03 20:00:03 -07001514 return set_table_resize(so, so->used);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001515}
1516
Raymond Hettingera690a992003-11-16 16:17:49 +00001517static PyObject *
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001518set_difference_update(PySetObject *so, PyObject *args)
Raymond Hettingera690a992003-11-16 16:17:49 +00001519{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001520 Py_ssize_t i;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001521
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001522 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1523 PyObject *other = PyTuple_GET_ITEM(args, i);
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001524 if (set_difference_update_internal(so, other))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001525 return NULL;
1526 }
1527 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001528}
1529
1530PyDoc_STRVAR(difference_update_doc,
1531"Remove all elements of another set from this set.");
1532
1533static PyObject *
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001534set_copy_and_difference(PySetObject *so, PyObject *other)
1535{
1536 PyObject *result;
1537
1538 result = set_copy(so);
1539 if (result == NULL)
1540 return NULL;
Raymond Hettingerb3223262015-07-03 23:37:16 -07001541 if (set_difference_update_internal((PySetObject *) result, other) == 0)
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001542 return result;
1543 Py_DECREF(result);
1544 return NULL;
1545}
1546
1547static PyObject *
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001548set_difference(PySetObject *so, PyObject *other)
1549{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001550 PyObject *result;
Raymond Hettinger73799b12015-07-05 16:06:10 -07001551 PyObject *key;
1552 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001553 setentry *entry;
1554 Py_ssize_t pos = 0;
Raymond Hettinger73799b12015-07-05 16:06:10 -07001555 int rv;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001556
Raymond Hettinger4103e4d2016-09-11 22:02:28 -07001557 if (PySet_GET_SIZE(so) == 0) {
1558 return set_copy(so);
1559 }
1560
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001561 if (!PyAnySet_Check(other) && !PyDict_CheckExact(other)) {
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001562 return set_copy_and_difference(so, other);
1563 }
1564
1565 /* If len(so) much more than len(other), it's more efficient to simply copy
1566 * so and then iterate other looking for common elements. */
1567 if ((PySet_GET_SIZE(so) >> 2) > PyObject_Size(other)) {
1568 return set_copy_and_difference(so, other);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001569 }
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001570
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001571 result = make_new_set_basetype(Py_TYPE(so), NULL);
1572 if (result == NULL)
1573 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001574
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001575 if (PyDict_CheckExact(other)) {
1576 while (set_next(so, &pos, &entry)) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001577 key = entry->key;
1578 hash = entry->hash;
Raymond Hettinger15f08692015-07-03 17:21:17 -07001579 rv = _PyDict_Contains(other, key, hash);
Serhiy Storchakafa494fd2015-05-30 17:45:22 +03001580 if (rv < 0) {
1581 Py_DECREF(result);
1582 return NULL;
1583 }
1584 if (!rv) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001585 if (set_add_entry((PySetObject *)result, key, hash)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001586 Py_DECREF(result);
1587 return NULL;
1588 }
1589 }
1590 }
1591 return result;
1592 }
1593
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001594 /* Iterate over so, checking for common elements in other. */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001595 while (set_next(so, &pos, &entry)) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001596 key = entry->key;
1597 hash = entry->hash;
1598 rv = set_contains_entry((PySetObject *)other, key, hash);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001599 if (rv < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001600 Py_DECREF(result);
1601 return NULL;
1602 }
1603 if (!rv) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001604 if (set_add_entry((PySetObject *)result, key, hash)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001605 Py_DECREF(result);
1606 return NULL;
1607 }
1608 }
1609 }
1610 return result;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001611}
1612
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001613static PyObject *
1614set_difference_multi(PySetObject *so, PyObject *args)
1615{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001616 Py_ssize_t i;
1617 PyObject *result, *other;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001618
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001619 if (PyTuple_GET_SIZE(args) == 0)
1620 return set_copy(so);
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001621
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001622 other = PyTuple_GET_ITEM(args, 0);
1623 result = set_difference(so, other);
1624 if (result == NULL)
1625 return NULL;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001626
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001627 for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) {
1628 other = PyTuple_GET_ITEM(args, i);
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001629 if (set_difference_update_internal((PySetObject *)result, other)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001630 Py_DECREF(result);
1631 return NULL;
1632 }
1633 }
1634 return result;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001635}
1636
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001637PyDoc_STRVAR(difference_doc,
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001638"Return the difference of two or more sets as a new set.\n\
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001639\n\
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001640(i.e. all elements that are in this set but not the others.)");
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001641static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001642set_sub(PySetObject *so, PyObject *other)
1643{
Brian Curtindfc80e32011-08-10 20:28:54 -05001644 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1645 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001646 return set_difference(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001647}
1648
1649static PyObject *
1650set_isub(PySetObject *so, PyObject *other)
1651{
Brian Curtindfc80e32011-08-10 20:28:54 -05001652 if (!PyAnySet_Check(other))
1653 Py_RETURN_NOTIMPLEMENTED;
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001654 if (set_difference_update_internal(so, other))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001655 return NULL;
1656 Py_INCREF(so);
1657 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001658}
1659
1660static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001661set_symmetric_difference_update(PySetObject *so, PyObject *other)
1662{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001663 PySetObject *otherset;
1664 PyObject *key;
1665 Py_ssize_t pos = 0;
Raymond Hettinger73799b12015-07-05 16:06:10 -07001666 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001667 setentry *entry;
Raymond Hettinger73799b12015-07-05 16:06:10 -07001668 int rv;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001669
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001670 if ((PyObject *)so == other)
1671 return set_clear(so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001672
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001673 if (PyDict_CheckExact(other)) {
1674 PyObject *value;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001675 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001676 Py_INCREF(key);
Raymond Hettinger73799b12015-07-05 16:06:10 -07001677 rv = set_discard_entry(so, key, hash);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001678 if (rv < 0) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001679 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001680 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001681 }
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001682 if (rv == DISCARD_NOTFOUND) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001683 if (set_add_entry(so, key, hash)) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001684 Py_DECREF(key);
1685 return NULL;
1686 }
1687 }
Georg Brandl2d444492010-09-03 10:52:55 +00001688 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001689 }
1690 Py_RETURN_NONE;
1691 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001692
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001693 if (PyAnySet_Check(other)) {
1694 Py_INCREF(other);
1695 otherset = (PySetObject *)other;
1696 } else {
1697 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1698 if (otherset == NULL)
1699 return NULL;
1700 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001701
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001702 while (set_next(otherset, &pos, &entry)) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001703 key = entry->key;
1704 hash = entry->hash;
1705 rv = set_discard_entry(so, key, hash);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001706 if (rv < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001707 Py_DECREF(otherset);
1708 return NULL;
1709 }
1710 if (rv == DISCARD_NOTFOUND) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001711 if (set_add_entry(so, key, hash)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001712 Py_DECREF(otherset);
1713 return NULL;
1714 }
1715 }
1716 }
1717 Py_DECREF(otherset);
1718 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001719}
1720
1721PyDoc_STRVAR(symmetric_difference_update_doc,
1722"Update a set with the symmetric difference of itself and another.");
1723
1724static PyObject *
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001725set_symmetric_difference(PySetObject *so, PyObject *other)
1726{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001727 PyObject *rv;
1728 PySetObject *otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001729
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001730 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1731 if (otherset == NULL)
1732 return NULL;
1733 rv = set_symmetric_difference_update(otherset, (PyObject *)so);
1734 if (rv == NULL)
1735 return NULL;
1736 Py_DECREF(rv);
1737 return (PyObject *)otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001738}
1739
1740PyDoc_STRVAR(symmetric_difference_doc,
1741"Return the symmetric difference of two sets as a new set.\n\
1742\n\
1743(i.e. all elements that are in exactly one of the sets.)");
1744
1745static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001746set_xor(PySetObject *so, PyObject *other)
1747{
Brian Curtindfc80e32011-08-10 20:28:54 -05001748 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1749 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001750 return set_symmetric_difference(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001751}
1752
1753static PyObject *
1754set_ixor(PySetObject *so, PyObject *other)
1755{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001756 PyObject *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001757
Brian Curtindfc80e32011-08-10 20:28:54 -05001758 if (!PyAnySet_Check(other))
1759 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001760 result = set_symmetric_difference_update(so, other);
1761 if (result == NULL)
1762 return NULL;
1763 Py_DECREF(result);
1764 Py_INCREF(so);
1765 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001766}
1767
1768static PyObject *
1769set_issubset(PySetObject *so, PyObject *other)
1770{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001771 setentry *entry;
1772 Py_ssize_t pos = 0;
Raymond Hettinger73799b12015-07-05 16:06:10 -07001773 int rv;
Raymond Hettingera690a992003-11-16 16:17:49 +00001774
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001775 if (!PyAnySet_Check(other)) {
1776 PyObject *tmp, *result;
1777 tmp = make_new_set(&PySet_Type, other);
1778 if (tmp == NULL)
1779 return NULL;
1780 result = set_issubset(so, tmp);
1781 Py_DECREF(tmp);
1782 return result;
1783 }
1784 if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
1785 Py_RETURN_FALSE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001786
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001787 while (set_next(so, &pos, &entry)) {
Raymond Hettinger73799b12015-07-05 16:06:10 -07001788 rv = set_contains_entry((PySetObject *)other, entry->key, entry->hash);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001789 if (rv < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001790 return NULL;
1791 if (!rv)
1792 Py_RETURN_FALSE;
1793 }
1794 Py_RETURN_TRUE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001795}
1796
1797PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
1798
1799static PyObject *
1800set_issuperset(PySetObject *so, PyObject *other)
1801{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001802 PyObject *tmp, *result;
Raymond Hettinger3fbec702003-11-21 07:56:36 +00001803
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001804 if (!PyAnySet_Check(other)) {
1805 tmp = make_new_set(&PySet_Type, other);
1806 if (tmp == NULL)
1807 return NULL;
1808 result = set_issuperset(so, tmp);
1809 Py_DECREF(tmp);
1810 return result;
1811 }
1812 return set_issubset((PySetObject *)other, (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001813}
1814
1815PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
1816
Raymond Hettingera690a992003-11-16 16:17:49 +00001817static PyObject *
1818set_richcompare(PySetObject *v, PyObject *w, int op)
1819{
Serhiy Storchakafa494fd2015-05-30 17:45:22 +03001820 PyObject *r1;
1821 int r2;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001822
Brian Curtindfc80e32011-08-10 20:28:54 -05001823 if(!PyAnySet_Check(w))
1824 Py_RETURN_NOTIMPLEMENTED;
1825
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001826 switch (op) {
1827 case Py_EQ:
1828 if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
1829 Py_RETURN_FALSE;
1830 if (v->hash != -1 &&
1831 ((PySetObject *)w)->hash != -1 &&
1832 v->hash != ((PySetObject *)w)->hash)
1833 Py_RETURN_FALSE;
1834 return set_issubset(v, w);
1835 case Py_NE:
1836 r1 = set_richcompare(v, w, Py_EQ);
1837 if (r1 == NULL)
1838 return NULL;
Serhiy Storchakafa494fd2015-05-30 17:45:22 +03001839 r2 = PyObject_IsTrue(r1);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001840 Py_DECREF(r1);
Serhiy Storchakafa494fd2015-05-30 17:45:22 +03001841 if (r2 < 0)
1842 return NULL;
1843 return PyBool_FromLong(!r2);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001844 case Py_LE:
1845 return set_issubset(v, w);
1846 case Py_GE:
1847 return set_issuperset(v, w);
1848 case Py_LT:
1849 if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))
1850 Py_RETURN_FALSE;
1851 return set_issubset(v, w);
1852 case Py_GT:
1853 if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
1854 Py_RETURN_FALSE;
1855 return set_issuperset(v, w);
1856 }
Brian Curtindfc80e32011-08-10 20:28:54 -05001857 Py_RETURN_NOTIMPLEMENTED;
Raymond Hettingera690a992003-11-16 16:17:49 +00001858}
1859
Raymond Hettingera690a992003-11-16 16:17:49 +00001860static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001861set_add(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001862{
Raymond Hettinger5af9e132015-05-13 01:44:36 -07001863 if (set_add_key(so, key))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001864 return NULL;
1865 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001866}
1867
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001868PyDoc_STRVAR(add_doc,
Raymond Hettingera690a992003-11-16 16:17:49 +00001869"Add an element to a set.\n\
1870\n\
1871This has no effect if the element is already present.");
1872
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001873static int
1874set_contains(PySetObject *so, PyObject *key)
1875{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001876 PyObject *tmpkey;
1877 int rv;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001878
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001879 rv = set_contains_key(so, key);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001880 if (rv < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001881 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1882 return -1;
1883 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001884 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001885 if (tmpkey == NULL)
1886 return -1;
Petri Lehtinen5acc27e2011-10-30 13:56:41 +02001887 rv = set_contains_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001888 Py_DECREF(tmpkey);
1889 }
1890 return rv;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001891}
1892
1893static PyObject *
1894set_direct_contains(PySetObject *so, PyObject *key)
1895{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001896 long result;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001897
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001898 result = set_contains(so, key);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001899 if (result < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001900 return NULL;
1901 return PyBool_FromLong(result);
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001902}
1903
1904PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
1905
Raymond Hettingera690a992003-11-16 16:17:49 +00001906static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001907set_remove(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001908{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001909 PyObject *tmpkey;
1910 int rv;
Raymond Hettingerbfd334a2003-11-22 03:55:23 +00001911
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001912 rv = set_discard_key(so, key);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001913 if (rv < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001914 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1915 return NULL;
1916 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001917 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001918 if (tmpkey == NULL)
1919 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001920 rv = set_discard_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001921 Py_DECREF(tmpkey);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001922 if (rv < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001923 return NULL;
1924 }
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00001925
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001926 if (rv == DISCARD_NOTFOUND) {
Raymond Hettinger69492da2013-09-02 15:59:26 -07001927 _PyErr_SetKeyError(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001928 return NULL;
1929 }
1930 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001931}
1932
1933PyDoc_STRVAR(remove_doc,
1934"Remove an element from a set; it must be a member.\n\
1935\n\
1936If the element is not a member, raise a KeyError.");
1937
1938static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001939set_discard(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001940{
Benjamin Peterson2b50a012011-10-30 14:24:44 -04001941 PyObject *tmpkey;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001942 int rv;
Raymond Hettinger0deab622003-12-13 18:53:18 +00001943
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001944 rv = set_discard_key(so, key);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001945 if (rv < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001946 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1947 return NULL;
1948 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001949 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001950 if (tmpkey == NULL)
1951 return NULL;
Petri Lehtinene0aa8032011-10-30 14:31:27 +02001952 rv = set_discard_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001953 Py_DECREF(tmpkey);
Raymond Hettingerb3223262015-07-03 23:37:16 -07001954 if (rv < 0)
Petri Lehtinene0aa8032011-10-30 14:31:27 +02001955 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001956 }
1957 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001958}
1959
1960PyDoc_STRVAR(discard_doc,
1961"Remove an element from a set if it is a member.\n\
1962\n\
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001963If the element is not a member, do nothing.");
Raymond Hettingera690a992003-11-16 16:17:49 +00001964
1965static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001966set_reduce(PySetObject *so)
1967{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001968 PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;
Martin v. Löwisbd928fe2011-10-14 10:20:37 +02001969 _Py_IDENTIFIER(__dict__);
Raymond Hettingera690a992003-11-16 16:17:49 +00001970
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001971 keys = PySequence_List((PyObject *)so);
1972 if (keys == NULL)
1973 goto done;
1974 args = PyTuple_Pack(1, keys);
1975 if (args == NULL)
1976 goto done;
Martin v. Löwis1ee1b6f2011-10-10 18:11:30 +02001977 dict = _PyObject_GetAttrId((PyObject *)so, &PyId___dict__);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001978 if (dict == NULL) {
1979 PyErr_Clear();
1980 dict = Py_None;
1981 Py_INCREF(dict);
1982 }
1983 result = PyTuple_Pack(3, Py_TYPE(so), args, dict);
Raymond Hettingera690a992003-11-16 16:17:49 +00001984done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001985 Py_XDECREF(args);
1986 Py_XDECREF(keys);
1987 Py_XDECREF(dict);
1988 return result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001989}
1990
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001991static PyObject *
1992set_sizeof(PySetObject *so)
1993{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001994 Py_ssize_t res;
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00001995
Serhiy Storchaka5c4064e2015-12-19 20:05:25 +02001996 res = _PyObject_SIZE(Py_TYPE(so));
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001997 if (so->table != so->smalltable)
1998 res = res + (so->mask + 1) * sizeof(setentry);
1999 return PyLong_FromSsize_t(res);
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00002000}
2001
2002PyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes");
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00002003static int
2004set_init(PySetObject *self, PyObject *args, PyObject *kwds)
2005{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002006 PyObject *iterable = NULL;
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00002007
Serhiy Storchakafa070292016-04-29 11:31:52 +03002008 if (kwds != NULL && !_PyArg_NoKeywords("set()", kwds))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002009 return -1;
2010 if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable))
2011 return -1;
Raymond Hettingerb72e21b2016-03-25 02:29:59 -07002012 if (self->fill)
2013 set_clear_internal(self);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002014 self->hash = -1;
2015 if (iterable == NULL)
2016 return 0;
2017 return set_update_internal(self, iterable);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00002018}
2019
Raymond Hettingera690a992003-11-16 16:17:49 +00002020static PySequenceMethods set_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002021 set_len, /* sq_length */
2022 0, /* sq_concat */
2023 0, /* sq_repeat */
2024 0, /* sq_item */
2025 0, /* sq_slice */
2026 0, /* sq_ass_item */
2027 0, /* sq_ass_slice */
2028 (objobjproc)set_contains, /* sq_contains */
Raymond Hettingera690a992003-11-16 16:17:49 +00002029};
2030
2031/* set object ********************************************************/
2032
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002033#ifdef Py_DEBUG
2034static PyObject *test_c_api(PySetObject *so);
2035
2036PyDoc_STRVAR(test_c_api_doc, "Exercises C API. Returns True.\n\
2037All is well if assertions don't fail.");
2038#endif
2039
Raymond Hettingera690a992003-11-16 16:17:49 +00002040static PyMethodDef set_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002041 {"add", (PyCFunction)set_add, METH_O,
2042 add_doc},
2043 {"clear", (PyCFunction)set_clear, METH_NOARGS,
2044 clear_doc},
2045 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2046 contains_doc},
2047 {"copy", (PyCFunction)set_copy, METH_NOARGS,
2048 copy_doc},
2049 {"discard", (PyCFunction)set_discard, METH_O,
2050 discard_doc},
2051 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2052 difference_doc},
2053 {"difference_update", (PyCFunction)set_difference_update, METH_VARARGS,
2054 difference_update_doc},
2055 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2056 intersection_doc},
2057 {"intersection_update",(PyCFunction)set_intersection_update_multi, METH_VARARGS,
2058 intersection_update_doc},
2059 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2060 isdisjoint_doc},
2061 {"issubset", (PyCFunction)set_issubset, METH_O,
2062 issubset_doc},
2063 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2064 issuperset_doc},
2065 {"pop", (PyCFunction)set_pop, METH_NOARGS,
2066 pop_doc},
2067 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2068 reduce_doc},
2069 {"remove", (PyCFunction)set_remove, METH_O,
2070 remove_doc},
2071 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2072 sizeof_doc},
2073 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2074 symmetric_difference_doc},
2075 {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O,
2076 symmetric_difference_update_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002077#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002078 {"test_c_api", (PyCFunction)test_c_api, METH_NOARGS,
2079 test_c_api_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002080#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002081 {"union", (PyCFunction)set_union, METH_VARARGS,
2082 union_doc},
2083 {"update", (PyCFunction)set_update, METH_VARARGS,
2084 update_doc},
2085 {NULL, NULL} /* sentinel */
Raymond Hettingera690a992003-11-16 16:17:49 +00002086};
2087
2088static PyNumberMethods set_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002089 0, /*nb_add*/
2090 (binaryfunc)set_sub, /*nb_subtract*/
2091 0, /*nb_multiply*/
2092 0, /*nb_remainder*/
2093 0, /*nb_divmod*/
2094 0, /*nb_power*/
2095 0, /*nb_negative*/
2096 0, /*nb_positive*/
2097 0, /*nb_absolute*/
2098 0, /*nb_bool*/
2099 0, /*nb_invert*/
2100 0, /*nb_lshift*/
2101 0, /*nb_rshift*/
2102 (binaryfunc)set_and, /*nb_and*/
2103 (binaryfunc)set_xor, /*nb_xor*/
2104 (binaryfunc)set_or, /*nb_or*/
2105 0, /*nb_int*/
2106 0, /*nb_reserved*/
2107 0, /*nb_float*/
2108 0, /*nb_inplace_add*/
2109 (binaryfunc)set_isub, /*nb_inplace_subtract*/
2110 0, /*nb_inplace_multiply*/
2111 0, /*nb_inplace_remainder*/
2112 0, /*nb_inplace_power*/
2113 0, /*nb_inplace_lshift*/
2114 0, /*nb_inplace_rshift*/
2115 (binaryfunc)set_iand, /*nb_inplace_and*/
2116 (binaryfunc)set_ixor, /*nb_inplace_xor*/
2117 (binaryfunc)set_ior, /*nb_inplace_or*/
Raymond Hettingera690a992003-11-16 16:17:49 +00002118};
2119
2120PyDoc_STRVAR(set_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002121"set() -> new empty set object\n\
2122set(iterable) -> new set object\n\
Raymond Hettingera690a992003-11-16 16:17:49 +00002123\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002124Build an unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00002125
2126PyTypeObject PySet_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002127 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2128 "set", /* tp_name */
2129 sizeof(PySetObject), /* tp_basicsize */
2130 0, /* tp_itemsize */
2131 /* methods */
2132 (destructor)set_dealloc, /* tp_dealloc */
2133 0, /* tp_print */
2134 0, /* tp_getattr */
2135 0, /* tp_setattr */
2136 0, /* tp_reserved */
2137 (reprfunc)set_repr, /* tp_repr */
2138 &set_as_number, /* tp_as_number */
2139 &set_as_sequence, /* tp_as_sequence */
2140 0, /* tp_as_mapping */
Georg Brandl00da4e02010-10-18 07:32:48 +00002141 PyObject_HashNotImplemented, /* tp_hash */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002142 0, /* tp_call */
2143 0, /* tp_str */
2144 PyObject_GenericGetAttr, /* tp_getattro */
2145 0, /* tp_setattro */
2146 0, /* tp_as_buffer */
2147 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2148 Py_TPFLAGS_BASETYPE, /* tp_flags */
2149 set_doc, /* tp_doc */
2150 (traverseproc)set_traverse, /* tp_traverse */
2151 (inquiry)set_clear_internal, /* tp_clear */
2152 (richcmpfunc)set_richcompare, /* tp_richcompare */
Georg Brandl00da4e02010-10-18 07:32:48 +00002153 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2154 (getiterfunc)set_iter, /* tp_iter */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002155 0, /* tp_iternext */
2156 set_methods, /* tp_methods */
2157 0, /* tp_members */
2158 0, /* tp_getset */
2159 0, /* tp_base */
2160 0, /* tp_dict */
2161 0, /* tp_descr_get */
2162 0, /* tp_descr_set */
2163 0, /* tp_dictoffset */
2164 (initproc)set_init, /* tp_init */
2165 PyType_GenericAlloc, /* tp_alloc */
2166 set_new, /* tp_new */
2167 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002168};
2169
2170/* frozenset object ********************************************************/
2171
2172
2173static PyMethodDef frozenset_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002174 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2175 contains_doc},
2176 {"copy", (PyCFunction)frozenset_copy, METH_NOARGS,
2177 copy_doc},
2178 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2179 difference_doc},
Raymond Hettinger5d2385f2015-07-08 11:52:27 -07002180 {"intersection", (PyCFunction)set_intersection_multi, METH_VARARGS,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002181 intersection_doc},
2182 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2183 isdisjoint_doc},
2184 {"issubset", (PyCFunction)set_issubset, METH_O,
2185 issubset_doc},
2186 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2187 issuperset_doc},
2188 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2189 reduce_doc},
2190 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2191 sizeof_doc},
2192 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2193 symmetric_difference_doc},
2194 {"union", (PyCFunction)set_union, METH_VARARGS,
2195 union_doc},
2196 {NULL, NULL} /* sentinel */
Raymond Hettingera690a992003-11-16 16:17:49 +00002197};
2198
2199static PyNumberMethods frozenset_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002200 0, /*nb_add*/
2201 (binaryfunc)set_sub, /*nb_subtract*/
2202 0, /*nb_multiply*/
2203 0, /*nb_remainder*/
2204 0, /*nb_divmod*/
2205 0, /*nb_power*/
2206 0, /*nb_negative*/
2207 0, /*nb_positive*/
2208 0, /*nb_absolute*/
2209 0, /*nb_bool*/
2210 0, /*nb_invert*/
2211 0, /*nb_lshift*/
2212 0, /*nb_rshift*/
2213 (binaryfunc)set_and, /*nb_and*/
2214 (binaryfunc)set_xor, /*nb_xor*/
2215 (binaryfunc)set_or, /*nb_or*/
Raymond Hettingera690a992003-11-16 16:17:49 +00002216};
2217
2218PyDoc_STRVAR(frozenset_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002219"frozenset() -> empty frozenset object\n\
2220frozenset(iterable) -> frozenset object\n\
Raymond Hettingera690a992003-11-16 16:17:49 +00002221\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002222Build an immutable unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00002223
2224PyTypeObject PyFrozenSet_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002225 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2226 "frozenset", /* tp_name */
2227 sizeof(PySetObject), /* tp_basicsize */
2228 0, /* tp_itemsize */
2229 /* methods */
2230 (destructor)set_dealloc, /* tp_dealloc */
2231 0, /* tp_print */
2232 0, /* tp_getattr */
2233 0, /* tp_setattr */
2234 0, /* tp_reserved */
2235 (reprfunc)set_repr, /* tp_repr */
2236 &frozenset_as_number, /* tp_as_number */
2237 &set_as_sequence, /* tp_as_sequence */
2238 0, /* tp_as_mapping */
2239 frozenset_hash, /* tp_hash */
2240 0, /* tp_call */
2241 0, /* tp_str */
2242 PyObject_GenericGetAttr, /* tp_getattro */
2243 0, /* tp_setattro */
2244 0, /* tp_as_buffer */
2245 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2246 Py_TPFLAGS_BASETYPE, /* tp_flags */
2247 frozenset_doc, /* tp_doc */
2248 (traverseproc)set_traverse, /* tp_traverse */
2249 (inquiry)set_clear_internal, /* tp_clear */
2250 (richcmpfunc)set_richcompare, /* tp_richcompare */
Raymond Hettinger5d2385f2015-07-08 11:52:27 -07002251 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002252 (getiterfunc)set_iter, /* tp_iter */
2253 0, /* tp_iternext */
2254 frozenset_methods, /* tp_methods */
2255 0, /* tp_members */
2256 0, /* tp_getset */
2257 0, /* tp_base */
2258 0, /* tp_dict */
2259 0, /* tp_descr_get */
2260 0, /* tp_descr_set */
2261 0, /* tp_dictoffset */
2262 0, /* tp_init */
2263 PyType_GenericAlloc, /* tp_alloc */
2264 frozenset_new, /* tp_new */
2265 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002266};
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002267
2268
2269/***** C API functions *************************************************/
2270
2271PyObject *
2272PySet_New(PyObject *iterable)
2273{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002274 return make_new_set(&PySet_Type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002275}
2276
2277PyObject *
2278PyFrozenSet_New(PyObject *iterable)
2279{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002280 return make_new_set(&PyFrozenSet_Type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002281}
2282
Neal Norwitz8c49c822006-03-04 18:41:19 +00002283Py_ssize_t
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002284PySet_Size(PyObject *anyset)
2285{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002286 if (!PyAnySet_Check(anyset)) {
2287 PyErr_BadInternalCall();
2288 return -1;
2289 }
2290 return PySet_GET_SIZE(anyset);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002291}
2292
2293int
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002294PySet_Clear(PyObject *set)
2295{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002296 if (!PySet_Check(set)) {
2297 PyErr_BadInternalCall();
2298 return -1;
2299 }
2300 return set_clear_internal((PySetObject *)set);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002301}
2302
2303int
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002304PySet_Contains(PyObject *anyset, PyObject *key)
2305{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002306 if (!PyAnySet_Check(anyset)) {
2307 PyErr_BadInternalCall();
2308 return -1;
2309 }
2310 return set_contains_key((PySetObject *)anyset, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002311}
2312
2313int
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002314PySet_Discard(PyObject *set, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002315{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002316 if (!PySet_Check(set)) {
2317 PyErr_BadInternalCall();
2318 return -1;
2319 }
2320 return set_discard_key((PySetObject *)set, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002321}
2322
2323int
Christian Heimesfd66e512008-01-29 12:18:50 +00002324PySet_Add(PyObject *anyset, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002325{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002326 if (!PySet_Check(anyset) &&
2327 (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
2328 PyErr_BadInternalCall();
2329 return -1;
2330 }
2331 return set_add_key((PySetObject *)anyset, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002332}
2333
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002334int
Raymond Hettinger3625af52016-03-27 01:15:07 -07002335PySet_ClearFreeList(void)
2336{
2337 return 0;
2338}
2339
2340void
2341PySet_Fini(void)
2342{
2343 Py_CLEAR(emptyfrozenset);
2344}
2345
2346int
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002347_PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash)
Guido van Rossumd8faa362007-04-27 19:54:29 +00002348{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002349 setentry *entry;
Guido van Rossumd8faa362007-04-27 19:54:29 +00002350
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002351 if (!PyAnySet_Check(set)) {
2352 PyErr_BadInternalCall();
2353 return -1;
2354 }
2355 if (set_next((PySetObject *)set, pos, &entry) == 0)
2356 return 0;
2357 *key = entry->key;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002358 *hash = entry->hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002359 return 1;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002360}
2361
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002362PyObject *
2363PySet_Pop(PyObject *set)
2364{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002365 if (!PySet_Check(set)) {
2366 PyErr_BadInternalCall();
2367 return NULL;
2368 }
2369 return set_pop((PySetObject *)set);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002370}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002371
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002372int
2373_PySet_Update(PyObject *set, PyObject *iterable)
2374{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002375 if (!PySet_Check(set)) {
2376 PyErr_BadInternalCall();
2377 return -1;
2378 }
2379 return set_update_internal((PySetObject *)set, iterable);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002380}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002381
Raymond Hettingere259f132013-12-15 11:56:14 -08002382/* Exported for the gdb plugin's benefit. */
2383PyObject *_PySet_Dummy = dummy;
2384
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002385#ifdef Py_DEBUG
2386
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002387/* Test code to be called with any three element set.
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002388 Returns True and original set is restored. */
2389
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002390#define assertRaises(call_return_value, exception) \
2391 do { \
2392 assert(call_return_value); \
2393 assert(PyErr_ExceptionMatches(exception)); \
2394 PyErr_Clear(); \
2395 } while(0)
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002396
2397static PyObject *
2398test_c_api(PySetObject *so)
2399{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002400 Py_ssize_t count;
2401 char *s;
2402 Py_ssize_t i;
Raymond Hettinger583cd032013-09-07 22:06:35 -07002403 PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x=NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002404 PyObject *ob = (PyObject *)so;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002405 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002406 PyObject *str;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002407
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002408 /* Verify preconditions */
2409 assert(PyAnySet_Check(ob));
2410 assert(PyAnySet_CheckExact(ob));
2411 assert(!PyFrozenSet_CheckExact(ob));
Victor Stinner08b36bd2010-03-13 00:19:17 +00002412
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002413 /* so.clear(); so |= set("abc"); */
2414 str = PyUnicode_FromString("abc");
2415 if (str == NULL)
2416 return NULL;
2417 set_clear_internal(so);
Raymond Hettinger5af9e132015-05-13 01:44:36 -07002418 if (set_update_internal(so, str)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002419 Py_DECREF(str);
2420 return NULL;
2421 }
2422 Py_DECREF(str);
Victor Stinner08b36bd2010-03-13 00:19:17 +00002423
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002424 /* Exercise type/size checks */
2425 assert(PySet_Size(ob) == 3);
2426 assert(PySet_GET_SIZE(ob) == 3);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002427
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002428 /* Raise TypeError for non-iterable constructor arguments */
2429 assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
2430 assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002431
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002432 /* Raise TypeError for unhashable key */
2433 dup = PySet_New(ob);
2434 assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
2435 assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
2436 assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002437
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002438 /* Exercise successful pop, contains, add, and discard */
2439 elem = PySet_Pop(ob);
2440 assert(PySet_Contains(ob, elem) == 0);
2441 assert(PySet_GET_SIZE(ob) == 2);
2442 assert(PySet_Add(ob, elem) == 0);
2443 assert(PySet_Contains(ob, elem) == 1);
2444 assert(PySet_GET_SIZE(ob) == 3);
2445 assert(PySet_Discard(ob, elem) == 1);
2446 assert(PySet_GET_SIZE(ob) == 2);
2447 assert(PySet_Discard(ob, elem) == 0);
2448 assert(PySet_GET_SIZE(ob) == 2);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002449
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002450 /* Exercise clear */
2451 dup2 = PySet_New(dup);
2452 assert(PySet_Clear(dup2) == 0);
2453 assert(PySet_Size(dup2) == 0);
2454 Py_DECREF(dup2);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002455
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002456 /* Raise SystemError on clear or update of frozen set */
2457 f = PyFrozenSet_New(dup);
2458 assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
2459 assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
2460 assert(PySet_Add(f, elem) == 0);
2461 Py_INCREF(f);
2462 assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
2463 Py_DECREF(f);
2464 Py_DECREF(f);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002465
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002466 /* Exercise direct iteration */
2467 i = 0, count = 0;
2468 while (_PySet_NextEntry((PyObject *)dup, &i, &x, &hash)) {
2469 s = _PyUnicode_AsString(x);
2470 assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
2471 count++;
2472 }
2473 assert(count == 3);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002474
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002475 /* Exercise updates */
2476 dup2 = PySet_New(NULL);
2477 assert(_PySet_Update(dup2, dup) == 0);
2478 assert(PySet_Size(dup2) == 3);
2479 assert(_PySet_Update(dup2, dup) == 0);
2480 assert(PySet_Size(dup2) == 3);
2481 Py_DECREF(dup2);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002482
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002483 /* Raise SystemError when self argument is not a set or frozenset. */
2484 t = PyTuple_New(0);
2485 assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
2486 assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
2487 Py_DECREF(t);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002488
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002489 /* Raise SystemError when self argument is not a set. */
2490 f = PyFrozenSet_New(dup);
2491 assert(PySet_Size(f) == 3);
2492 assert(PyFrozenSet_CheckExact(f));
2493 assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
2494 assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
2495 Py_DECREF(f);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002496
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002497 /* Raise KeyError when popping from an empty set */
2498 assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
2499 Py_DECREF(ob);
2500 assert(PySet_GET_SIZE(ob) == 0);
2501 assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002502
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002503 /* Restore the set from the copy using the PyNumber API */
2504 assert(PyNumber_InPlaceOr(ob, dup) == ob);
2505 Py_DECREF(ob);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002506
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002507 /* Verify constructors accept NULL arguments */
2508 f = PySet_New(NULL);
2509 assert(f != NULL);
2510 assert(PySet_GET_SIZE(f) == 0);
2511 Py_DECREF(f);
2512 f = PyFrozenSet_New(NULL);
2513 assert(f != NULL);
2514 assert(PyFrozenSet_CheckExact(f));
2515 assert(PySet_GET_SIZE(f) == 0);
2516 Py_DECREF(f);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002517
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002518 Py_DECREF(elem);
2519 Py_DECREF(dup);
2520 Py_RETURN_TRUE;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002521}
2522
Raymond Hettinger9bda1d62005-09-16 07:14:21 +00002523#undef assertRaises
2524
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002525#endif
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -05002526
2527/***** Dummy Struct *************************************************/
2528
2529static PyObject *
2530dummy_repr(PyObject *op)
2531{
2532 return PyUnicode_FromString("<dummy key>");
2533}
2534
2535static void
2536dummy_dealloc(PyObject* ignore)
2537{
2538 Py_FatalError("deallocating <dummy key>");
2539}
2540
2541static PyTypeObject _PySetDummy_Type = {
2542 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2543 "<dummy key> type",
2544 0,
2545 0,
2546 dummy_dealloc, /*tp_dealloc*/ /*never called*/
2547 0, /*tp_print*/
2548 0, /*tp_getattr*/
2549 0, /*tp_setattr*/
2550 0, /*tp_reserved*/
2551 dummy_repr, /*tp_repr*/
2552 0, /*tp_as_number*/
2553 0, /*tp_as_sequence*/
2554 0, /*tp_as_mapping*/
2555 0, /*tp_hash */
2556 0, /*tp_call */
2557 0, /*tp_str */
2558 0, /*tp_getattro */
2559 0, /*tp_setattro */
2560 0, /*tp_as_buffer */
2561 Py_TPFLAGS_DEFAULT, /*tp_flags */
2562};
2563
2564static PyObject _dummy_struct = {
2565 _PyObject_EXTRA_INIT
2566 2, &_PySetDummy_Type
2567};
2568