blob: 8a3d4f2141b834d354fe55ca2c87cbab5b1a5086 [file] [log] [blame]
Raymond Hettingerc991db22005-08-11 07:58:45 +00001
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002/* set object implementation
Raymond Hettingera9d99362005-08-05 00:01:15 +00003 Written and maintained by Raymond D. Hettinger <python@rcn.com>
4 Derived from Lib/sets.py and Objects/dictobject.c.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00005
Raymond Hettinger6c3c1cc2013-08-31 21:34:24 -07006 Copyright (c) 2003-2013 Python Software Foundation.
Raymond Hettingera9d99362005-08-05 00:01:15 +00007 All rights reserved.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00008*/
9
Raymond Hettingera690a992003-11-16 16:17:49 +000010#include "Python.h"
Raymond Hettingera9d99362005-08-05 00:01:15 +000011#include "structmember.h"
Christian Heimes0ded5b52007-12-10 15:50:56 +000012#include "stringlib/eq.h"
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000013
Thomas Wouters89f507f2006-12-13 04:49:30 +000014/* Set a key error with the specified argument, wrapping it in a
15 * tuple automatically so that tuple keys are not unpacked as the
16 * exception arguments. */
17static void
18set_key_error(PyObject *arg)
19{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000020 PyObject *tup;
21 tup = PyTuple_Pack(1, arg);
22 if (!tup)
23 return; /* caller will expect error to be set anyway */
24 PyErr_SetObject(PyExc_KeyError, tup);
25 Py_DECREF(tup);
Thomas Wouters89f507f2006-12-13 04:49:30 +000026}
27
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000028/* This must be >= 1. */
29#define PERTURB_SHIFT 5
Raymond Hettingera35adf52013-09-02 03:23:21 -070030#define LINEAR_PROBES 9
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000031
32/* Object used as dummy key to fill deleted entries */
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -050033static PyObject _dummy_struct;
34
35#define dummy (&_dummy_struct)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000036
Antoine Pitrou9d952542013-08-24 21:07:07 +020037/* Exported for the gdb plugin's benefit. */
38PyObject *_PySet_Dummy = dummy;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000039
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000040#define INIT_NONZERO_SET_SLOTS(so) do { \
41 (so)->table = (so)->smalltable; \
42 (so)->mask = PySet_MINSIZE - 1; \
43 (so)->hash = -1; \
Raymond Hettingerbc841a12005-08-07 13:02:53 +000044 } while(0)
45
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000046#define EMPTY_TO_MINSIZE(so) do { \
47 memset((so)->smalltable, 0, sizeof((so)->smalltable)); \
48 (so)->used = (so)->fill = 0; \
49 INIT_NONZERO_SET_SLOTS(so); \
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000050 } while(0)
51
Raymond Hettingerbc841a12005-08-07 13:02:53 +000052/* Reuse scheme to save calls to malloc, free, and memset */
Christian Heimes2202f872008-02-06 14:31:34 +000053#ifndef PySet_MAXFREELIST
54#define PySet_MAXFREELIST 80
55#endif
56static PySetObject *free_list[PySet_MAXFREELIST];
57static int numfree = 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000058
Christian Heimes0ded5b52007-12-10 15:50:56 +000059
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000060/*
61The basic lookup function used by all operations.
62This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000063
Raymond Hettingera35adf52013-09-02 03:23:21 -070064The initial probe index is computed as hash mod the table size.
65Subsequent probe indices are computed as explained in Objects/dictobject.c.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000066
Raymond Hettingera35adf52013-09-02 03:23:21 -070067To improve cache locality, each probe inspects a series of consecutive
68nearby entries before moving on to probes elsewhere in memory. This leaves
69us with a hybrid of linear probing and open addressing. The linear probing
70reduces the cost of hash collisions because consecutive memory accesses
71tend to be much cheaper than scattered probes. After LINEAR_PROBES steps,
72we then use open addressing with the upper bits from the hash value. This
73helps break-up long chains of collisions.
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -070074
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000075All arithmetic on hash should ignore overflow.
76
Raymond Hettinger9bda1d62005-09-16 07:14:21 +000077Unlike the dictionary implementation, the lookkey functions can return
78NULL if the rich comparison returns an error.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000079*/
80
81static setentry *
Antoine Pitrou9ed5f272013-08-13 20:18:52 +020082set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000083{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000084 setentry *table = so->table;
Raymond Hettingerafe89092013-08-28 20:59:31 -070085 setentry *freeslot = NULL;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +020086 setentry *entry;
Raymond Hettingera35adf52013-09-02 03:23:21 -070087 setentry *limit;
Raymond Hettingerafe89092013-08-28 20:59:31 -070088 size_t perturb = hash;
89 size_t mask = so->mask;
Raymond Hettingera35adf52013-09-02 03:23:21 -070090 size_t i = (size_t)hash; /* Unsigned for defined overflow behavior. */
91 size_t j;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +020092 int cmp;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000093
Raymond Hettingera35adf52013-09-02 03:23:21 -070094 entry = &table[i & mask];
Raymond Hettingerafe89092013-08-28 20:59:31 -070095 if (entry->key == NULL)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000096 return entry;
Raymond Hettinger237b34b2013-08-17 02:31:53 -070097
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -070098 while (1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000099 if (entry->key == key)
Raymond Hettingerafe89092013-08-28 20:59:31 -0700100 return entry;
Raymond Hettingerae9e6162013-08-20 22:28:24 -0700101 if (entry->hash == hash && entry->key != dummy) {
Raymond Hettingerafe89092013-08-28 20:59:31 -0700102 PyObject *startkey = entry->key;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000103 Py_INCREF(startkey);
104 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
105 Py_DECREF(startkey);
106 if (cmp < 0)
107 return NULL;
Raymond Hettingerafe89092013-08-28 20:59:31 -0700108 if (table != so->table || entry->key != startkey)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000109 return set_lookkey(so, key, hash);
Raymond Hettingerafe89092013-08-28 20:59:31 -0700110 if (cmp > 0)
111 return entry;
112 }
113 if (entry->key == dummy && freeslot == NULL)
114 freeslot = entry;
115
Raymond Hettingera35adf52013-09-02 03:23:21 -0700116 limit = &table[mask];
117 for (j = 0 ; j < LINEAR_PROBES ; j++) {
118 entry = (entry == limit) ? &table[0] : entry + 1;
119 if (entry->key == NULL)
120 goto found_null;
121 if (entry->key == key)
Raymond Hettingerafe89092013-08-28 20:59:31 -0700122 return entry;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700123 if (entry->hash == hash && entry->key != dummy) {
124 PyObject *startkey = entry->key;
125 Py_INCREF(startkey);
126 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
127 Py_DECREF(startkey);
128 if (cmp < 0)
129 return NULL;
130 if (table != so->table || entry->key != startkey)
131 return set_lookkey(so, key, hash);
132 if (cmp > 0)
133 return entry;
134 }
135 if (entry->key == dummy && freeslot == NULL)
136 freeslot = entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000137 }
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700138
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700139 perturb >>= PERTURB_SHIFT;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700140 i = i * 5 + perturb + 1;
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700141
Raymond Hettingera35adf52013-09-02 03:23:21 -0700142 entry = &table[i & mask];
Raymond Hettingerafe89092013-08-28 20:59:31 -0700143 if (entry->key == NULL)
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700144 break;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000145 }
Raymond Hettingera35adf52013-09-02 03:23:21 -0700146 found_null:
Raymond Hettingerafe89092013-08-28 20:59:31 -0700147 return freeslot == NULL ? entry : freeslot;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000148}
149
150/*
Christian Heimes0ded5b52007-12-10 15:50:56 +0000151 * Hacked up version of set_lookkey which can assume keys are always unicode;
152 * This means we can always use unicode_eq directly and not have to check to
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000153 * see if the comparison altered the table.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000154 */
155static setentry *
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200156set_lookkey_unicode(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000157{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000158 setentry *table = so->table;
Raymond Hettingerafe89092013-08-28 20:59:31 -0700159 setentry *freeslot = NULL;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200160 setentry *entry;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700161 setentry *limit;
Raymond Hettingerafe89092013-08-28 20:59:31 -0700162 size_t perturb = hash;
163 size_t mask = so->mask;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700164 size_t i = (size_t)hash;
165 size_t j;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000166
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000167 /* Make sure this function doesn't have to handle non-unicode keys,
168 including subclasses of str; e.g., one reason to subclass
169 strings is to override __eq__, and for speed we don't cater to
170 that here. */
171 if (!PyUnicode_CheckExact(key)) {
172 so->lookup = set_lookkey;
173 return set_lookkey(so, key, hash);
174 }
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700175
Raymond Hettingera35adf52013-09-02 03:23:21 -0700176 entry = &table[i & mask];
Raymond Hettingerafe89092013-08-28 20:59:31 -0700177 if (entry->key == NULL)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000178 return entry;
Raymond Hettingered6c1ef2005-08-13 08:28:03 +0000179
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700180 while (1) {
Raymond Hettingerafe89092013-08-28 20:59:31 -0700181 if (entry->key == key
182 || (entry->hash == hash
183 && entry->key != dummy
184 && unicode_eq(entry->key, key)))
185 return entry;
186 if (entry->key == dummy && freeslot == NULL)
187 freeslot = entry;
188
Raymond Hettingera35adf52013-09-02 03:23:21 -0700189 limit = &table[mask];
190 for (j = 0 ; j < LINEAR_PROBES ; j++) {
191 entry = (entry == limit) ? &table[0] : entry + 1;
192 if (entry->key == NULL)
193 goto found_null;
194 if (entry->key == key
195 || (entry->hash == hash
196 && entry->key != dummy
197 && unicode_eq(entry->key, key)))
198 return entry;
199 if (entry->key == dummy && freeslot == NULL)
200 freeslot = entry;
201 }
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700202
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700203 perturb >>= PERTURB_SHIFT;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700204 i = i * 5 + perturb + 1;
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700205
Raymond Hettingera35adf52013-09-02 03:23:21 -0700206 entry = &table[i & mask];
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000207 if (entry->key == NULL)
Raymond Hettingerafe89092013-08-28 20:59:31 -0700208 break;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000209 }
Raymond Hettingera35adf52013-09-02 03:23:21 -0700210 found_null:
Raymond Hettingerafe89092013-08-28 20:59:31 -0700211 return freeslot == NULL ? entry : freeslot;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000212}
213
214/*
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000215Internal routine to insert a new key into the table.
Thomas Wouters89f507f2006-12-13 04:49:30 +0000216Used by the public insert routine.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000217Eats a reference to key.
218*/
Raymond Hettinger9bda1d62005-09-16 07:14:21 +0000219static int
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200220set_insert_key(PySetObject *so, PyObject *key, Py_hash_t hash)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000221{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200222 setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000223
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000224 assert(so->lookup != NULL);
225 entry = so->lookup(so, key, hash);
226 if (entry == NULL)
227 return -1;
228 if (entry->key == NULL) {
229 /* UNUSED */
230 so->fill++;
231 entry->key = key;
232 entry->hash = hash;
233 so->used++;
234 } else if (entry->key == dummy) {
235 /* DUMMY */
236 entry->key = key;
237 entry->hash = hash;
238 so->used++;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000239 } else {
240 /* ACTIVE */
241 Py_DECREF(key);
242 }
243 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000244}
245
246/*
Thomas Wouters89f507f2006-12-13 04:49:30 +0000247Internal routine used by set_table_resize() to insert an item which is
248known to be absent from the set. This routine also assumes that
249the set contains no deleted entries. Besides the performance benefit,
250using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
251Note that no refcounts are changed by this routine; if needed, the caller
252is responsible for incref'ing `key`.
253*/
254static void
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200255set_insert_clean(PySetObject *so, PyObject *key, Py_hash_t hash)
Thomas Wouters89f507f2006-12-13 04:49:30 +0000256{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000257 setentry *table = so->table;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200258 setentry *entry;
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700259 size_t perturb = hash;
260 size_t mask = (size_t)so->mask;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700261 size_t i = (size_t)hash;
262 size_t j;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000263
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700264 while (1) {
Raymond Hettingera35adf52013-09-02 03:23:21 -0700265 entry = &table[i & mask];
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700266 if (entry->key == NULL)
Raymond Hettingera35adf52013-09-02 03:23:21 -0700267 goto found_null;
268 for (j = 1 ; j <= LINEAR_PROBES ; j++) {
269 entry = &table[(i + j) & mask];
270 if (entry->key == NULL)
271 goto found_null;
272 }
Raymond Hettinger3c0a4f52013-08-19 07:36:04 -0700273 perturb >>= PERTURB_SHIFT;
Raymond Hettingera35adf52013-09-02 03:23:21 -0700274 i = i * 5 + perturb + 1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000275 }
Raymond Hettingera35adf52013-09-02 03:23:21 -0700276 found_null:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000277 so->fill++;
278 entry->key = key;
279 entry->hash = hash;
280 so->used++;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000281}
282
283/*
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000284Restructure the table by allocating a new table and reinserting all
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000285keys again. When entries have been deleted, the new table may
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000286actually be smaller than the old one.
287*/
288static int
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000289set_table_resize(PySetObject *so, Py_ssize_t minused)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000290{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000291 Py_ssize_t newsize;
292 setentry *oldtable, *newtable, *entry;
293 Py_ssize_t i;
294 int is_oldtable_malloced;
295 setentry small_copy[PySet_MINSIZE];
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000296
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000297 assert(minused >= 0);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000298
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000299 /* Find the smallest table size > minused. */
300 for (newsize = PySet_MINSIZE;
301 newsize <= minused && newsize > 0;
302 newsize <<= 1)
303 ;
304 if (newsize <= 0) {
305 PyErr_NoMemory();
306 return -1;
307 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000308
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000309 /* Get space for a new table. */
310 oldtable = so->table;
311 assert(oldtable != NULL);
312 is_oldtable_malloced = oldtable != so->smalltable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000313
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000314 if (newsize == PySet_MINSIZE) {
315 /* A large table is shrinking, or we can't get any smaller. */
316 newtable = so->smalltable;
317 if (newtable == oldtable) {
318 if (so->fill == so->used) {
319 /* No dummies, so no point doing anything. */
320 return 0;
321 }
322 /* We're not going to resize it, but rebuild the
323 table anyway to purge old dummy entries.
324 Subtle: This is *necessary* if fill==size,
325 as set_lookkey needs at least one virgin slot to
326 terminate failing searches. If fill < size, it's
327 merely desirable, as dummies slow searches. */
328 assert(so->fill > so->used);
329 memcpy(small_copy, oldtable, sizeof(small_copy));
330 oldtable = small_copy;
331 }
332 }
333 else {
334 newtable = PyMem_NEW(setentry, newsize);
335 if (newtable == NULL) {
336 PyErr_NoMemory();
337 return -1;
338 }
339 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000340
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000341 /* Make the set empty, using the new table. */
342 assert(newtable != oldtable);
343 so->table = newtable;
344 so->mask = newsize - 1;
345 memset(newtable, 0, sizeof(setentry) * newsize);
Raymond Hettingerfcf3b502013-08-22 08:20:31 -0700346 i = so->used;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000347 so->used = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000348 so->fill = 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000349
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000350 /* Copy the data over; this is refcount-neutral for active entries;
351 dummy entries aren't copied over, of course */
352 for (entry = oldtable; i > 0; entry++) {
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -0500353 if (entry->key != NULL && entry->key != dummy) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000354 --i;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000355 set_insert_clean(so, entry->key, entry->hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000356 }
357 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000358
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000359 if (is_oldtable_malloced)
360 PyMem_DEL(oldtable);
361 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000362}
363
Raymond Hettingerc991db22005-08-11 07:58:45 +0000364/* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
365
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000366static int
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200367set_add_entry(PySetObject *so, setentry *entry)
Raymond Hettingerc991db22005-08-11 07:58:45 +0000368{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200369 Py_ssize_t n_used;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000370 PyObject *key = entry->key;
Éric Araujobbcfc1f2011-03-23 03:43:22 +0100371 Py_hash_t hash = entry->hash;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000372
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000373 assert(so->fill <= so->mask); /* at least one empty slot */
374 n_used = so->used;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000375 Py_INCREF(key);
Éric Araujo48049912011-03-23 02:08:07 +0100376 if (set_insert_key(so, key, hash) == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000377 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000378 return -1;
379 }
380 if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
381 return 0;
382 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettingerc991db22005-08-11 07:58:45 +0000383}
384
385static int
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200386set_add_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000387{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200388 Py_hash_t hash;
389 Py_ssize_t n_used;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000390
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000391 if (!PyUnicode_CheckExact(key) ||
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200392 (hash = ((PyASCIIObject *) key)->hash) == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000393 hash = PyObject_Hash(key);
394 if (hash == -1)
395 return -1;
396 }
397 assert(so->fill <= so->mask); /* at least one empty slot */
398 n_used = so->used;
399 Py_INCREF(key);
400 if (set_insert_key(so, key, hash) == -1) {
401 Py_DECREF(key);
402 return -1;
403 }
404 if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
405 return 0;
406 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000407}
408
409#define DISCARD_NOTFOUND 0
410#define DISCARD_FOUND 1
411
412static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000413set_discard_entry(PySetObject *so, setentry *oldentry)
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200414{ setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000415 PyObject *old_key;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000416
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000417 entry = (so->lookup)(so, oldentry->key, oldentry->hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000418 if (entry == NULL)
419 return -1;
420 if (entry->key == NULL || entry->key == dummy)
421 return DISCARD_NOTFOUND;
422 old_key = entry->key;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000423 entry->key = dummy;
424 so->used--;
425 Py_DECREF(old_key);
426 return DISCARD_FOUND;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000427}
428
429static int
430set_discard_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000431{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200432 Py_hash_t hash;
433 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000434 PyObject *old_key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000435
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000436 assert (PyAnySet_Check(so));
Christian Heimes0ded5b52007-12-10 15:50:56 +0000437
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000438 if (!PyUnicode_CheckExact(key) ||
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200439 (hash = ((PyASCIIObject *) key)->hash) == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000440 hash = PyObject_Hash(key);
441 if (hash == -1)
442 return -1;
443 }
444 entry = (so->lookup)(so, key, hash);
445 if (entry == NULL)
446 return -1;
447 if (entry->key == NULL || entry->key == dummy)
448 return DISCARD_NOTFOUND;
449 old_key = entry->key;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000450 entry->key = dummy;
451 so->used--;
452 Py_DECREF(old_key);
453 return DISCARD_FOUND;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000454}
455
Raymond Hettingerfe889f32005-08-06 05:43:39 +0000456static int
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000457set_clear_internal(PySetObject *so)
458{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000459 setentry *entry, *table;
460 int table_is_malloced;
461 Py_ssize_t fill;
462 setentry small_copy[PySet_MINSIZE];
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000463#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000464 Py_ssize_t i, n;
465 assert (PyAnySet_Check(so));
Raymond Hettingera580c472005-08-05 17:19:54 +0000466
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000467 n = so->mask + 1;
468 i = 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000469#endif
470
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000471 table = so->table;
472 assert(table != NULL);
473 table_is_malloced = table != so->smalltable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000474
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000475 /* This is delicate. During the process of clearing the set,
476 * decrefs can cause the set to mutate. To avoid fatal confusion
477 * (voice of experience), we have to make the set empty before
478 * clearing the slots, and never refer to anything via so->ref while
479 * clearing.
480 */
481 fill = so->fill;
482 if (table_is_malloced)
483 EMPTY_TO_MINSIZE(so);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000484
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000485 else if (fill > 0) {
486 /* It's a small table with something that needs to be cleared.
487 * Afraid the only safe way is to copy the set entries into
488 * another small table first.
489 */
490 memcpy(small_copy, table, sizeof(small_copy));
491 table = small_copy;
492 EMPTY_TO_MINSIZE(so);
493 }
494 /* else it's a small table that's already empty */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000495
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000496 /* Now we can finally clear things. If C had refcounts, we could
497 * assert that the refcount on table is 1 now, i.e. that this function
498 * has unique access to it, so decref side-effects can't alter it.
499 */
500 for (entry = table; fill > 0; ++entry) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000501#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000502 assert(i < n);
503 ++i;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000504#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000505 if (entry->key) {
506 --fill;
Raymond Hettingerfcf3b502013-08-22 08:20:31 -0700507 if (entry->key != dummy)
508 Py_DECREF(entry->key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000509 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000510#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000511 else
512 assert(entry->key == NULL);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000513#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000514 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000515
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000516 if (table_is_malloced)
517 PyMem_DEL(table);
518 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000519}
520
521/*
522 * Iterate over a set table. Use like so:
523 *
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000524 * Py_ssize_t pos;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000525 * setentry *entry;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000526 * pos = 0; # important! pos should not otherwise be changed by you
Raymond Hettingerc991db22005-08-11 07:58:45 +0000527 * while (set_next(yourset, &pos, &entry)) {
528 * Refer to borrowed reference in entry->key.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000529 * }
530 *
Raymond Hettingerc991db22005-08-11 07:58:45 +0000531 * CAUTION: In general, it isn't safe to use set_next in a loop that
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000532 * mutates the table.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000533 */
534static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000535set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000536{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000537 Py_ssize_t i;
538 Py_ssize_t mask;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200539 setentry *table;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000540
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000541 assert (PyAnySet_Check(so));
542 i = *pos_ptr;
543 assert(i >= 0);
544 table = so->table;
545 mask = so->mask;
546 while (i <= mask && (table[i].key == NULL || table[i].key == dummy))
547 i++;
548 *pos_ptr = i+1;
549 if (i > mask)
550 return 0;
551 assert(table[i].key != NULL);
552 *entry_ptr = &table[i];
553 return 1;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000554}
555
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000556static void
557set_dealloc(PySetObject *so)
558{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200559 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000560 Py_ssize_t fill = so->fill;
561 PyObject_GC_UnTrack(so);
562 Py_TRASHCAN_SAFE_BEGIN(so)
563 if (so->weakreflist != NULL)
564 PyObject_ClearWeakRefs((PyObject *) so);
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000565
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000566 for (entry = so->table; fill > 0; entry++) {
567 if (entry->key) {
568 --fill;
Raymond Hettingerfcf3b502013-08-22 08:20:31 -0700569 if (entry->key != dummy)
570 Py_DECREF(entry->key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000571 }
572 }
573 if (so->table != so->smalltable)
574 PyMem_DEL(so->table);
575 if (numfree < PySet_MAXFREELIST && PyAnySet_CheckExact(so))
576 free_list[numfree++] = so;
577 else
578 Py_TYPE(so)->tp_free(so);
579 Py_TRASHCAN_SAFE_END(so)
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000580}
581
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000582static PyObject *
583set_repr(PySetObject *so)
584{
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200585 PyObject *result=NULL, *keys, *listrepr, *tmp;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000586 int status = Py_ReprEnter((PyObject*)so);
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000587
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000588 if (status != 0) {
589 if (status < 0)
590 return NULL;
591 return PyUnicode_FromFormat("%s(...)", Py_TYPE(so)->tp_name);
592 }
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000593
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000594 /* shortcut for the empty set */
595 if (!so->used) {
596 Py_ReprLeave((PyObject*)so);
597 return PyUnicode_FromFormat("%s()", Py_TYPE(so)->tp_name);
598 }
Georg Brandlc4996ba2006-08-28 19:37:11 +0000599
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000600 keys = PySequence_List((PyObject *)so);
601 if (keys == NULL)
602 goto done;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000603
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200604 /* repr(keys)[1:-1] */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000605 listrepr = PyObject_Repr(keys);
606 Py_DECREF(keys);
607 if (listrepr == NULL)
608 goto done;
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200609 tmp = PyUnicode_Substring(listrepr, 1, PyUnicode_GET_LENGTH(listrepr)-1);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000610 Py_DECREF(listrepr);
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200611 if (tmp == NULL)
612 goto done;
613 listrepr = tmp;
Victor Stinnera1a807b2011-05-26 14:24:30 +0200614
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200615 if (Py_TYPE(so) != &PySet_Type)
616 result = PyUnicode_FromFormat("%s({%U})",
617 Py_TYPE(so)->tp_name,
618 listrepr);
619 else
620 result = PyUnicode_FromFormat("{%U}", listrepr);
621 Py_DECREF(listrepr);
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000622done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000623 Py_ReprLeave((PyObject*)so);
624 return result;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000625}
626
Martin v. Löwis18e16552006-02-15 17:27:45 +0000627static Py_ssize_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000628set_len(PyObject *so)
629{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000630 return ((PySetObject *)so)->used;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000631}
632
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000633static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000634set_merge(PySetObject *so, PyObject *otherset)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000635{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000636 PySetObject *other;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000637 PyObject *key;
Éric Araujobbcfc1f2011-03-23 03:43:22 +0100638 Py_hash_t hash;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200639 Py_ssize_t i;
640 setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000641
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000642 assert (PyAnySet_Check(so));
643 assert (PyAnySet_Check(otherset));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000644
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000645 other = (PySetObject*)otherset;
646 if (other == so || other->used == 0)
647 /* a.update(a) or a.update({}); nothing to do */
648 return 0;
649 /* Do one big resize at the start, rather than
650 * incrementally resizing as we insert new keys. Expect
651 * that there will be no (or few) overlapping keys.
652 */
653 if ((so->fill + other->used)*3 >= (so->mask+1)*2) {
654 if (set_table_resize(so, (so->used + other->used)*2) != 0)
655 return -1;
656 }
657 for (i = 0; i <= other->mask; i++) {
658 entry = &other->table[i];
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000659 key = entry->key;
Éric Araujo48049912011-03-23 02:08:07 +0100660 hash = entry->hash;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000661 if (key != NULL &&
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -0500662 key != dummy) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000663 Py_INCREF(key);
Éric Araujo48049912011-03-23 02:08:07 +0100664 if (set_insert_key(so, key, hash) == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +0000665 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000666 return -1;
667 }
668 }
669 }
670 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000671}
672
673static int
Raymond Hettingerc991db22005-08-11 07:58:45 +0000674set_contains_key(PySetObject *so, PyObject *key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000675{
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000676 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000677 setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000678
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000679 if (!PyUnicode_CheckExact(key) ||
Martin v. Löwisd63a3b82011-09-28 07:41:54 +0200680 (hash = ((PyASCIIObject *) key)->hash) == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000681 hash = PyObject_Hash(key);
682 if (hash == -1)
683 return -1;
684 }
685 entry = (so->lookup)(so, key, hash);
686 if (entry == NULL)
687 return -1;
688 key = entry->key;
689 return key != NULL && key != dummy;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000690}
691
Raymond Hettingerc991db22005-08-11 07:58:45 +0000692static int
693set_contains_entry(PySetObject *so, setentry *entry)
694{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000695 PyObject *key;
696 setentry *lu_entry;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000697
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000698 lu_entry = (so->lookup)(so, entry->key, entry->hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000699 if (lu_entry == NULL)
700 return -1;
701 key = lu_entry->key;
702 return key != NULL && key != dummy;
Raymond Hettingerc991db22005-08-11 07:58:45 +0000703}
704
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000705static PyObject *
706set_pop(PySetObject *so)
707{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200708 Py_ssize_t i = 0;
709 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000710 PyObject *key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000711
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000712 assert (PyAnySet_Check(so));
713 if (so->used == 0) {
714 PyErr_SetString(PyExc_KeyError, "pop from an empty set");
715 return NULL;
716 }
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000717
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000718 /* Set entry to "the first" unused or dummy set entry. We abuse
719 * the hash field of slot 0 to hold a search finger:
720 * If slot 0 has a value, use slot 0.
721 * Else slot 0 is being used to hold a search finger,
722 * and we use its hash value as the first index to look.
723 */
724 entry = &so->table[0];
725 if (entry->key == NULL || entry->key == dummy) {
726 i = entry->hash;
727 /* The hash field may be a real hash value, or it may be a
728 * legit search finger, or it may be a once-legit search
729 * finger that's out of bounds now because it wrapped around
730 * or the table shrunk -- simply make sure it's in bounds now.
731 */
732 if (i > so->mask || i < 1)
733 i = 1; /* skip slot 0 */
734 while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
735 i++;
736 if (i > so->mask)
737 i = 1;
738 }
739 }
740 key = entry->key;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000741 entry->key = dummy;
742 so->used--;
743 so->table[0].hash = i + 1; /* next place to start */
744 return key;
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000745}
746
Benjamin Petersonf10a79a2008-10-11 00:49:57 +0000747PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\
748Raises KeyError if the set is empty.");
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000749
750static int
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000751set_traverse(PySetObject *so, visitproc visit, void *arg)
Raymond Hettingerce8185e2005-08-13 09:28:48 +0000752{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000753 Py_ssize_t pos = 0;
754 setentry *entry;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000755
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000756 while (set_next(so, &pos, &entry))
757 Py_VISIT(entry->key);
758 return 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000759}
760
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000761static Py_hash_t
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000762frozenset_hash(PyObject *self)
763{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000764 PySetObject *so = (PySetObject *)self;
Gregory P. Smith27cbcd62012-12-10 18:15:46 -0800765 Py_uhash_t h, hash = 1927868237UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000766 setentry *entry;
767 Py_ssize_t pos = 0;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000768
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000769 if (so->hash != -1)
770 return so->hash;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000771
Mark Dickinson57e683e2011-09-24 18:18:40 +0100772 hash *= (Py_uhash_t)PySet_GET_SIZE(self) + 1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000773 while (set_next(so, &pos, &entry)) {
774 /* Work to increase the bit dispersion for closely spaced hash
775 values. The is important because some use cases have many
776 combinations of a small number of elements with nearby
777 hashes so that many distinct combinations collapse to only
778 a handful of distinct hash values. */
Antoine Pitroufbb1c612010-10-23 17:37:54 +0000779 h = entry->hash;
Gregory P. Smith27cbcd62012-12-10 18:15:46 -0800780 hash ^= (h ^ (h << 16) ^ 89869747UL) * 3644798167UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000781 }
Gregory P. Smithc2176e42012-12-10 18:32:53 -0800782 hash = hash * 69069U + 907133923UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000783 if (hash == -1)
Gregory P. Smith27cbcd62012-12-10 18:15:46 -0800784 hash = 590923713UL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000785 so->hash = hash;
786 return hash;
Raymond Hettingerf408ddf2005-08-17 00:27:42 +0000787}
788
Raymond Hettingera9d99362005-08-05 00:01:15 +0000789/***** Set iterator type ***********************************************/
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000790
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000791typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000792 PyObject_HEAD
793 PySetObject *si_set; /* Set to NULL when iterator is exhausted */
794 Py_ssize_t si_used;
795 Py_ssize_t si_pos;
796 Py_ssize_t len;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000797} setiterobject;
798
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000799static void
800setiter_dealloc(setiterobject *si)
801{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000802 Py_XDECREF(si->si_set);
803 PyObject_GC_Del(si);
Antoine Pitrou7ddda782009-01-01 15:35:33 +0000804}
805
806static int
807setiter_traverse(setiterobject *si, visitproc visit, void *arg)
808{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000809 Py_VISIT(si->si_set);
810 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000811}
812
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000813static PyObject *
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000814setiter_len(setiterobject *si)
815{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000816 Py_ssize_t len = 0;
817 if (si->si_set != NULL && si->si_used == si->si_set->used)
818 len = si->len;
Antoine Pitrou671b4d92010-08-17 17:55:07 +0000819 return PyLong_FromSsize_t(len);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000820}
821
Armin Rigof5b3e362006-02-11 21:32:43 +0000822PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000823
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000824static PyObject *setiter_iternext(setiterobject *si);
825
826static PyObject *
827setiter_reduce(setiterobject *si)
828{
829 PyObject *list;
830 setiterobject tmp;
831
832 list = PyList_New(0);
833 if (!list)
834 return NULL;
835
Ezio Melotti0e1af282012-09-28 16:43:40 +0300836 /* copy the iterator state */
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000837 tmp = *si;
838 Py_XINCREF(tmp.si_set);
Ezio Melotti0e1af282012-09-28 16:43:40 +0300839
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000840 /* iterate the temporary into a list */
841 for(;;) {
842 PyObject *element = setiter_iternext(&tmp);
843 if (element) {
844 if (PyList_Append(list, element)) {
845 Py_DECREF(element);
846 Py_DECREF(list);
847 Py_XDECREF(tmp.si_set);
848 return NULL;
849 }
850 Py_DECREF(element);
851 } else
852 break;
853 }
854 Py_XDECREF(tmp.si_set);
855 /* check for error */
856 if (tmp.si_set != NULL) {
857 /* we have an error */
858 Py_DECREF(list);
859 return NULL;
860 }
Antoine Pitroua7013882012-04-05 00:04:20 +0200861 return Py_BuildValue("N(N)", _PyObject_GetBuiltin("iter"), list);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000862}
863
864PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
865
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000866static PyMethodDef setiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000867 {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +0000868 {"__reduce__", (PyCFunction)setiter_reduce, METH_NOARGS, reduce_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000869 {NULL, NULL} /* sentinel */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000870};
871
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000872static PyObject *setiter_iternext(setiterobject *si)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000873{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000874 PyObject *key;
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200875 Py_ssize_t i, mask;
876 setentry *entry;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000877 PySetObject *so = si->si_set;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000878
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000879 if (so == NULL)
880 return NULL;
881 assert (PyAnySet_Check(so));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000882
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000883 if (si->si_used != so->used) {
884 PyErr_SetString(PyExc_RuntimeError,
885 "Set changed size during iteration");
886 si->si_used = -1; /* Make this state sticky */
887 return NULL;
888 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000889
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000890 i = si->si_pos;
891 assert(i>=0);
892 entry = so->table;
893 mask = so->mask;
894 while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
895 i++;
896 si->si_pos = i+1;
897 if (i > mask)
898 goto fail;
899 si->len--;
900 key = entry[i].key;
901 Py_INCREF(key);
902 return key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000903
904fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000905 Py_DECREF(so);
906 si->si_set = NULL;
907 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000908}
909
Christian Heimesa22e8bd2007-11-29 22:35:39 +0000910PyTypeObject PySetIter_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000911 PyVarObject_HEAD_INIT(&PyType_Type, 0)
912 "set_iterator", /* tp_name */
913 sizeof(setiterobject), /* tp_basicsize */
914 0, /* tp_itemsize */
915 /* methods */
916 (destructor)setiter_dealloc, /* tp_dealloc */
917 0, /* tp_print */
918 0, /* tp_getattr */
919 0, /* tp_setattr */
920 0, /* tp_reserved */
921 0, /* tp_repr */
922 0, /* tp_as_number */
923 0, /* tp_as_sequence */
924 0, /* tp_as_mapping */
925 0, /* tp_hash */
926 0, /* tp_call */
927 0, /* tp_str */
928 PyObject_GenericGetAttr, /* tp_getattro */
929 0, /* tp_setattro */
930 0, /* tp_as_buffer */
931 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
932 0, /* tp_doc */
933 (traverseproc)setiter_traverse, /* tp_traverse */
934 0, /* tp_clear */
935 0, /* tp_richcompare */
936 0, /* tp_weaklistoffset */
937 PyObject_SelfIter, /* tp_iter */
938 (iternextfunc)setiter_iternext, /* tp_iternext */
939 setiter_methods, /* tp_methods */
940 0,
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000941};
942
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000943static PyObject *
944set_iter(PySetObject *so)
945{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000946 setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type);
947 if (si == NULL)
948 return NULL;
949 Py_INCREF(so);
950 si->si_set = so;
951 si->si_used = so->used;
952 si->si_pos = 0;
953 si->len = so->used;
954 _PyObject_GC_TRACK(si);
955 return (PyObject *)si;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000956}
957
Raymond Hettingerd7946662005-08-01 21:39:29 +0000958static int
Raymond Hettingerd7946662005-08-01 21:39:29 +0000959set_update_internal(PySetObject *so, PyObject *other)
Raymond Hettingera690a992003-11-16 16:17:49 +0000960{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000961 PyObject *key, *it;
Raymond Hettingera690a992003-11-16 16:17:49 +0000962
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000963 if (PyAnySet_Check(other))
964 return set_merge(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +0000965
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000966 if (PyDict_CheckExact(other)) {
967 PyObject *value;
968 Py_ssize_t pos = 0;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000969 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000970 Py_ssize_t dictsize = PyDict_Size(other);
Thomas Wouterscf297e42007-02-23 15:07:44 +0000971
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000972 /* Do one big resize at the start, rather than
973 * incrementally resizing as we insert new keys. Expect
974 * that there will be no (or few) overlapping keys.
975 */
976 if (dictsize == -1)
977 return -1;
978 if ((so->fill + dictsize)*3 >= (so->mask+1)*2) {
979 if (set_table_resize(so, (so->used + dictsize)*2) != 0)
980 return -1;
981 }
982 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
983 setentry an_entry;
Thomas Wouterscf297e42007-02-23 15:07:44 +0000984
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000985 an_entry.hash = hash;
986 an_entry.key = key;
987 if (set_add_entry(so, &an_entry) == -1)
988 return -1;
989 }
990 return 0;
991 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000992
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000993 it = PyObject_GetIter(other);
994 if (it == NULL)
995 return -1;
Raymond Hettingera690a992003-11-16 16:17:49 +0000996
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000997 while ((key = PyIter_Next(it)) != NULL) {
998 if (set_add_key(so, key) == -1) {
999 Py_DECREF(it);
1000 Py_DECREF(key);
1001 return -1;
1002 }
1003 Py_DECREF(key);
1004 }
1005 Py_DECREF(it);
1006 if (PyErr_Occurred())
1007 return -1;
1008 return 0;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001009}
1010
1011static PyObject *
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001012set_update(PySetObject *so, PyObject *args)
Raymond Hettingerd7946662005-08-01 21:39:29 +00001013{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001014 Py_ssize_t i;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001015
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001016 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1017 PyObject *other = PyTuple_GET_ITEM(args, i);
1018 if (set_update_internal(so, other) == -1)
1019 return NULL;
1020 }
1021 Py_RETURN_NONE;
Raymond Hettingera38123e2003-11-24 22:18:49 +00001022}
1023
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001024PyDoc_STRVAR(update_doc,
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001025"Update a set with the union of itself and others.");
Raymond Hettingera38123e2003-11-24 22:18:49 +00001026
1027static PyObject *
1028make_new_set(PyTypeObject *type, PyObject *iterable)
1029{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +02001030 PySetObject *so = NULL;
Raymond Hettingera38123e2003-11-24 22:18:49 +00001031
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001032 /* create PySetObject structure */
1033 if (numfree &&
1034 (type == &PySet_Type || type == &PyFrozenSet_Type)) {
1035 so = free_list[--numfree];
1036 assert (so != NULL && PyAnySet_CheckExact(so));
1037 Py_TYPE(so) = type;
1038 _Py_NewReference((PyObject *)so);
1039 EMPTY_TO_MINSIZE(so);
1040 PyObject_GC_Track(so);
1041 } else {
1042 so = (PySetObject *)type->tp_alloc(type, 0);
1043 if (so == NULL)
1044 return NULL;
1045 /* tp_alloc has already zeroed the structure */
1046 assert(so->table == NULL && so->fill == 0 && so->used == 0);
1047 INIT_NONZERO_SET_SLOTS(so);
1048 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001049
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001050 so->lookup = set_lookkey_unicode;
1051 so->weakreflist = NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001052
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001053 if (iterable != NULL) {
1054 if (set_update_internal(so, iterable) == -1) {
1055 Py_DECREF(so);
1056 return NULL;
1057 }
1058 }
Raymond Hettingera38123e2003-11-24 22:18:49 +00001059
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001060 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001061}
1062
Raymond Hettinger7d99f092008-11-16 11:44:54 +00001063static PyObject *
1064make_new_set_basetype(PyTypeObject *type, PyObject *iterable)
1065{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001066 if (type != &PySet_Type && type != &PyFrozenSet_Type) {
1067 if (PyType_IsSubtype(type, &PySet_Type))
1068 type = &PySet_Type;
1069 else
1070 type = &PyFrozenSet_Type;
1071 }
1072 return make_new_set(type, iterable);
Raymond Hettinger7d99f092008-11-16 11:44:54 +00001073}
1074
Raymond Hettingerd7946662005-08-01 21:39:29 +00001075/* The empty frozenset is a singleton */
1076static PyObject *emptyfrozenset = NULL;
1077
Raymond Hettingera690a992003-11-16 16:17:49 +00001078static PyObject *
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001079frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
Raymond Hettingera690a992003-11-16 16:17:49 +00001080{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001081 PyObject *iterable = NULL, *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001082
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001083 if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds))
1084 return NULL;
Georg Brandl02c42872005-08-26 06:42:30 +00001085
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001086 if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
1087 return NULL;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001088
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001089 if (type != &PyFrozenSet_Type)
1090 return make_new_set(type, iterable);
Raymond Hettingerd7946662005-08-01 21:39:29 +00001091
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001092 if (iterable != NULL) {
1093 /* frozenset(f) is idempotent */
1094 if (PyFrozenSet_CheckExact(iterable)) {
1095 Py_INCREF(iterable);
1096 return iterable;
1097 }
1098 result = make_new_set(type, iterable);
1099 if (result == NULL || PySet_GET_SIZE(result))
1100 return result;
1101 Py_DECREF(result);
1102 }
1103 /* The empty frozenset is a singleton */
1104 if (emptyfrozenset == NULL)
1105 emptyfrozenset = make_new_set(type, NULL);
1106 Py_XINCREF(emptyfrozenset);
1107 return emptyfrozenset;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001108}
1109
Antoine Pitrou093ce9c2011-12-16 11:24:27 +01001110int
1111PySet_ClearFreeList(void)
Raymond Hettingerd7946662005-08-01 21:39:29 +00001112{
Antoine Pitrou093ce9c2011-12-16 11:24:27 +01001113 int freelist_size = numfree;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001114 PySetObject *so;
Raymond Hettingerbc841a12005-08-07 13:02:53 +00001115
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001116 while (numfree) {
1117 numfree--;
1118 so = free_list[numfree];
1119 PyObject_GC_Del(so);
1120 }
Antoine Pitrou093ce9c2011-12-16 11:24:27 +01001121 return freelist_size;
1122}
1123
1124void
1125PySet_Fini(void)
1126{
1127 PySet_ClearFreeList();
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001128 Py_CLEAR(emptyfrozenset);
Raymond Hettingera690a992003-11-16 16:17:49 +00001129}
1130
David Malcolm49526f42012-06-22 14:55:41 -04001131/* Print summary info about the state of the optimized allocator */
1132void
1133_PySet_DebugMallocStats(FILE *out)
1134{
1135 _PyDebugAllocatorStats(out,
1136 "free PySetObject",
1137 numfree, sizeof(PySetObject));
1138}
1139
1140
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001141static PyObject *
1142set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1143{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001144 if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds))
1145 return NULL;
1146
1147 return make_new_set(type, NULL);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001148}
1149
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001150/* set_swap_bodies() switches the contents of any two sets by moving their
1151 internal data pointers and, if needed, copying the internal smalltables.
1152 Semantically equivalent to:
1153
1154 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1155
1156 The function always succeeds and it leaves both objects in a stable state.
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001157 Useful for creating temporary frozensets from sets for membership testing
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001158 in __contains__(), discard(), and remove(). Also useful for operations
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001159 that update in-place (by allowing an intermediate result to be swapped
Raymond Hettinger9dcb17c2005-07-31 13:09:28 +00001160 into one of the original inputs).
Raymond Hettinger934d63e2005-07-31 01:33:10 +00001161*/
1162
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001163static void
1164set_swap_bodies(PySetObject *a, PySetObject *b)
Raymond Hettingera690a992003-11-16 16:17:49 +00001165{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001166 Py_ssize_t t;
1167 setentry *u;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001168 setentry *(*f)(PySetObject *so, PyObject *key, Py_ssize_t hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001169 setentry tab[PySet_MINSIZE];
Antoine Pitroufbb1c612010-10-23 17:37:54 +00001170 Py_hash_t h;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001171
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001172 t = a->fill; a->fill = b->fill; b->fill = t;
1173 t = a->used; a->used = b->used; b->used = t;
1174 t = a->mask; a->mask = b->mask; b->mask = t;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001175
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001176 u = a->table;
1177 if (a->table == a->smalltable)
1178 u = b->smalltable;
1179 a->table = b->table;
1180 if (b->table == b->smalltable)
1181 a->table = a->smalltable;
1182 b->table = u;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001183
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001184 f = a->lookup; a->lookup = b->lookup; b->lookup = f;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001185
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001186 if (a->table == a->smalltable || b->table == b->smalltable) {
1187 memcpy(tab, a->smalltable, sizeof(tab));
1188 memcpy(a->smalltable, b->smalltable, sizeof(tab));
1189 memcpy(b->smalltable, tab, sizeof(tab));
1190 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001191
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001192 if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type) &&
1193 PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) {
1194 h = a->hash; a->hash = b->hash; b->hash = h;
1195 } else {
1196 a->hash = -1;
1197 b->hash = -1;
1198 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001199}
1200
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001201static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001202set_copy(PySetObject *so)
1203{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001204 return make_new_set_basetype(Py_TYPE(so), (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001205}
1206
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001207static PyObject *
1208frozenset_copy(PySetObject *so)
1209{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001210 if (PyFrozenSet_CheckExact(so)) {
1211 Py_INCREF(so);
1212 return (PyObject *)so;
1213 }
1214 return set_copy(so);
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001215}
1216
Raymond Hettingera690a992003-11-16 16:17:49 +00001217PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
1218
1219static PyObject *
Raymond Hettingerc991db22005-08-11 07:58:45 +00001220set_clear(PySetObject *so)
1221{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001222 set_clear_internal(so);
1223 Py_RETURN_NONE;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001224}
1225
1226PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
1227
1228static PyObject *
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001229set_union(PySetObject *so, PyObject *args)
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001230{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001231 PySetObject *result;
1232 PyObject *other;
1233 Py_ssize_t i;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001234
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001235 result = (PySetObject *)set_copy(so);
1236 if (result == NULL)
1237 return NULL;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001238
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001239 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1240 other = PyTuple_GET_ITEM(args, i);
1241 if ((PyObject *)so == other)
1242 continue;
1243 if (set_update_internal(result, other) == -1) {
1244 Py_DECREF(result);
1245 return NULL;
1246 }
1247 }
1248 return (PyObject *)result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001249}
1250
1251PyDoc_STRVAR(union_doc,
1252 "Return the union of sets as a new set.\n\
1253\n\
1254(i.e. all elements that are in either set.)");
1255
1256static PyObject *
1257set_or(PySetObject *so, PyObject *other)
1258{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001259 PySetObject *result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001260
Brian Curtindfc80e32011-08-10 20:28:54 -05001261 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1262 Py_RETURN_NOTIMPLEMENTED;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001263
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001264 result = (PySetObject *)set_copy(so);
1265 if (result == NULL)
1266 return NULL;
1267 if ((PyObject *)so == other)
1268 return (PyObject *)result;
1269 if (set_update_internal(result, other) == -1) {
1270 Py_DECREF(result);
1271 return NULL;
1272 }
1273 return (PyObject *)result;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001274}
1275
Raymond Hettingera690a992003-11-16 16:17:49 +00001276static PyObject *
1277set_ior(PySetObject *so, PyObject *other)
1278{
Brian Curtindfc80e32011-08-10 20:28:54 -05001279 if (!PyAnySet_Check(other))
1280 Py_RETURN_NOTIMPLEMENTED;
1281
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001282 if (set_update_internal(so, other) == -1)
1283 return NULL;
1284 Py_INCREF(so);
1285 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001286}
1287
1288static PyObject *
1289set_intersection(PySetObject *so, PyObject *other)
1290{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001291 PySetObject *result;
1292 PyObject *key, *it, *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001293
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001294 if ((PyObject *)so == other)
1295 return set_copy(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001296
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001297 result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL);
1298 if (result == NULL)
1299 return NULL;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001300
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001301 if (PyAnySet_Check(other)) {
1302 Py_ssize_t pos = 0;
1303 setentry *entry;
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001304
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001305 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1306 tmp = (PyObject *)so;
1307 so = (PySetObject *)other;
1308 other = tmp;
1309 }
Raymond Hettingerb02c35e2005-08-12 20:48:39 +00001310
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001311 while (set_next((PySetObject *)other, &pos, &entry)) {
1312 int rv = set_contains_entry(so, entry);
1313 if (rv == -1) {
1314 Py_DECREF(result);
1315 return NULL;
1316 }
1317 if (rv) {
1318 if (set_add_entry(result, entry) == -1) {
1319 Py_DECREF(result);
1320 return NULL;
1321 }
1322 }
1323 }
1324 return (PyObject *)result;
1325 }
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001326
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001327 it = PyObject_GetIter(other);
1328 if (it == NULL) {
1329 Py_DECREF(result);
1330 return NULL;
1331 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001332
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001333 while ((key = PyIter_Next(it)) != NULL) {
1334 int rv;
1335 setentry entry;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001336 Py_hash_t hash = PyObject_Hash(key);
Thomas Wouters89f507f2006-12-13 04:49:30 +00001337
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001338 if (hash == -1) {
1339 Py_DECREF(it);
1340 Py_DECREF(result);
1341 Py_DECREF(key);
1342 return NULL;
1343 }
1344 entry.hash = hash;
1345 entry.key = key;
1346 rv = set_contains_entry(so, &entry);
1347 if (rv == -1) {
1348 Py_DECREF(it);
1349 Py_DECREF(result);
1350 Py_DECREF(key);
1351 return NULL;
1352 }
1353 if (rv) {
1354 if (set_add_entry(result, &entry) == -1) {
1355 Py_DECREF(it);
1356 Py_DECREF(result);
1357 Py_DECREF(key);
1358 return NULL;
1359 }
1360 }
1361 Py_DECREF(key);
1362 }
1363 Py_DECREF(it);
1364 if (PyErr_Occurred()) {
1365 Py_DECREF(result);
1366 return NULL;
1367 }
1368 return (PyObject *)result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001369}
1370
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001371static PyObject *
1372set_intersection_multi(PySetObject *so, PyObject *args)
1373{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001374 Py_ssize_t i;
1375 PyObject *result = (PyObject *)so;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001376
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001377 if (PyTuple_GET_SIZE(args) == 0)
1378 return set_copy(so);
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001379
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001380 Py_INCREF(so);
1381 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1382 PyObject *other = PyTuple_GET_ITEM(args, i);
1383 PyObject *newresult = set_intersection((PySetObject *)result, other);
1384 if (newresult == NULL) {
1385 Py_DECREF(result);
1386 return NULL;
1387 }
1388 Py_DECREF(result);
1389 result = newresult;
1390 }
1391 return result;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001392}
1393
Raymond Hettingera690a992003-11-16 16:17:49 +00001394PyDoc_STRVAR(intersection_doc,
1395"Return the intersection of two sets as a new set.\n\
1396\n\
1397(i.e. all elements that are in both sets.)");
1398
1399static PyObject *
1400set_intersection_update(PySetObject *so, PyObject *other)
1401{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001402 PyObject *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001403
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001404 tmp = set_intersection(so, other);
1405 if (tmp == NULL)
1406 return NULL;
1407 set_swap_bodies(so, (PySetObject *)tmp);
1408 Py_DECREF(tmp);
1409 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001410}
1411
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001412static PyObject *
1413set_intersection_update_multi(PySetObject *so, PyObject *args)
1414{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001415 PyObject *tmp;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001416
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001417 tmp = set_intersection_multi(so, args);
1418 if (tmp == NULL)
1419 return NULL;
1420 set_swap_bodies(so, (PySetObject *)tmp);
1421 Py_DECREF(tmp);
1422 Py_RETURN_NONE;
Georg Brandlc28e1fa2008-06-10 19:20:26 +00001423}
1424
Raymond Hettingera690a992003-11-16 16:17:49 +00001425PyDoc_STRVAR(intersection_update_doc,
1426"Update a set with the intersection of itself and another.");
1427
1428static PyObject *
1429set_and(PySetObject *so, PyObject *other)
1430{
Brian Curtindfc80e32011-08-10 20:28:54 -05001431 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1432 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001433 return set_intersection(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001434}
1435
1436static PyObject *
1437set_iand(PySetObject *so, PyObject *other)
1438{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001439 PyObject *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001440
Brian Curtindfc80e32011-08-10 20:28:54 -05001441 if (!PyAnySet_Check(other))
1442 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001443 result = set_intersection_update(so, other);
1444 if (result == NULL)
1445 return NULL;
1446 Py_DECREF(result);
1447 Py_INCREF(so);
1448 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001449}
1450
Guido van Rossum58da9312007-11-10 23:39:45 +00001451static PyObject *
1452set_isdisjoint(PySetObject *so, PyObject *other)
1453{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001454 PyObject *key, *it, *tmp;
Guido van Rossum58da9312007-11-10 23:39:45 +00001455
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001456 if ((PyObject *)so == other) {
1457 if (PySet_GET_SIZE(so) == 0)
1458 Py_RETURN_TRUE;
1459 else
1460 Py_RETURN_FALSE;
1461 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001462
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001463 if (PyAnySet_CheckExact(other)) {
1464 Py_ssize_t pos = 0;
1465 setentry *entry;
Guido van Rossum58da9312007-11-10 23:39:45 +00001466
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001467 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1468 tmp = (PyObject *)so;
1469 so = (PySetObject *)other;
1470 other = tmp;
1471 }
1472 while (set_next((PySetObject *)other, &pos, &entry)) {
1473 int rv = set_contains_entry(so, entry);
1474 if (rv == -1)
1475 return NULL;
1476 if (rv)
1477 Py_RETURN_FALSE;
1478 }
1479 Py_RETURN_TRUE;
1480 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001481
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001482 it = PyObject_GetIter(other);
1483 if (it == NULL)
1484 return NULL;
Guido van Rossum58da9312007-11-10 23:39:45 +00001485
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001486 while ((key = PyIter_Next(it)) != NULL) {
1487 int rv;
1488 setentry entry;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001489 Py_hash_t hash = PyObject_Hash(key);
Guido van Rossum58da9312007-11-10 23:39:45 +00001490
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001491 if (hash == -1) {
1492 Py_DECREF(key);
1493 Py_DECREF(it);
1494 return NULL;
1495 }
1496 entry.hash = hash;
1497 entry.key = key;
1498 rv = set_contains_entry(so, &entry);
1499 Py_DECREF(key);
1500 if (rv == -1) {
1501 Py_DECREF(it);
1502 return NULL;
1503 }
1504 if (rv) {
1505 Py_DECREF(it);
1506 Py_RETURN_FALSE;
1507 }
1508 }
1509 Py_DECREF(it);
1510 if (PyErr_Occurred())
1511 return NULL;
1512 Py_RETURN_TRUE;
Guido van Rossum58da9312007-11-10 23:39:45 +00001513}
1514
1515PyDoc_STRVAR(isdisjoint_doc,
1516"Return True if two sets have a null intersection.");
1517
Neal Norwitz6576bd82005-11-13 18:41:28 +00001518static int
Raymond Hettingerc991db22005-08-11 07:58:45 +00001519set_difference_update_internal(PySetObject *so, PyObject *other)
1520{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001521 if ((PyObject *)so == other)
1522 return set_clear_internal(so);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001523
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001524 if (PyAnySet_Check(other)) {
1525 setentry *entry;
1526 Py_ssize_t pos = 0;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001527
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001528 while (set_next((PySetObject *)other, &pos, &entry))
1529 if (set_discard_entry(so, entry) == -1)
1530 return -1;
1531 } else {
1532 PyObject *key, *it;
1533 it = PyObject_GetIter(other);
1534 if (it == NULL)
1535 return -1;
1536
1537 while ((key = PyIter_Next(it)) != NULL) {
1538 if (set_discard_key(so, key) == -1) {
1539 Py_DECREF(it);
1540 Py_DECREF(key);
1541 return -1;
1542 }
1543 Py_DECREF(key);
1544 }
1545 Py_DECREF(it);
1546 if (PyErr_Occurred())
1547 return -1;
1548 }
1549 /* If more than 1/5 are dummies, then resize them away. */
1550 if ((so->fill - so->used) * 5 < so->mask)
1551 return 0;
1552 return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
Raymond Hettingerc991db22005-08-11 07:58:45 +00001553}
1554
Raymond Hettingera690a992003-11-16 16:17:49 +00001555static PyObject *
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001556set_difference_update(PySetObject *so, PyObject *args)
Raymond Hettingera690a992003-11-16 16:17:49 +00001557{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001558 Py_ssize_t i;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001559
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001560 for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1561 PyObject *other = PyTuple_GET_ITEM(args, i);
1562 if (set_difference_update_internal(so, other) == -1)
1563 return NULL;
1564 }
1565 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001566}
1567
1568PyDoc_STRVAR(difference_update_doc,
1569"Remove all elements of another set from this set.");
1570
1571static PyObject *
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001572set_copy_and_difference(PySetObject *so, PyObject *other)
1573{
1574 PyObject *result;
1575
1576 result = set_copy(so);
1577 if (result == NULL)
1578 return NULL;
1579 if (set_difference_update_internal((PySetObject *) result, other) != -1)
1580 return result;
1581 Py_DECREF(result);
1582 return NULL;
1583}
1584
1585static PyObject *
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001586set_difference(PySetObject *so, PyObject *other)
1587{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001588 PyObject *result;
1589 setentry *entry;
1590 Py_ssize_t pos = 0;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001591
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001592 if (!PyAnySet_Check(other) && !PyDict_CheckExact(other)) {
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001593 return set_copy_and_difference(so, other);
1594 }
1595
1596 /* If len(so) much more than len(other), it's more efficient to simply copy
1597 * so and then iterate other looking for common elements. */
1598 if ((PySet_GET_SIZE(so) >> 2) > PyObject_Size(other)) {
1599 return set_copy_and_difference(so, other);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001600 }
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001601
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001602 result = make_new_set_basetype(Py_TYPE(so), NULL);
1603 if (result == NULL)
1604 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001605
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001606 if (PyDict_CheckExact(other)) {
1607 while (set_next(so, &pos, &entry)) {
1608 setentry entrycopy;
1609 entrycopy.hash = entry->hash;
1610 entrycopy.key = entry->key;
Antoine Pitroufbb1c612010-10-23 17:37:54 +00001611 if (!_PyDict_Contains(other, entry->key, entry->hash)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001612 if (set_add_entry((PySetObject *)result, &entrycopy) == -1) {
1613 Py_DECREF(result);
1614 return NULL;
1615 }
1616 }
1617 }
1618 return result;
1619 }
1620
Antoine Pitrou715f3cd2010-11-30 22:23:20 +00001621 /* Iterate over so, checking for common elements in other. */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001622 while (set_next(so, &pos, &entry)) {
1623 int rv = set_contains_entry((PySetObject *)other, entry);
1624 if (rv == -1) {
1625 Py_DECREF(result);
1626 return NULL;
1627 }
1628 if (!rv) {
1629 if (set_add_entry((PySetObject *)result, entry) == -1) {
1630 Py_DECREF(result);
1631 return NULL;
1632 }
1633 }
1634 }
1635 return result;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001636}
1637
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001638static PyObject *
1639set_difference_multi(PySetObject *so, PyObject *args)
1640{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001641 Py_ssize_t i;
1642 PyObject *result, *other;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001643
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001644 if (PyTuple_GET_SIZE(args) == 0)
1645 return set_copy(so);
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001646
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001647 other = PyTuple_GET_ITEM(args, 0);
1648 result = set_difference(so, other);
1649 if (result == NULL)
1650 return NULL;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001651
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001652 for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) {
1653 other = PyTuple_GET_ITEM(args, i);
1654 if (set_difference_update_internal((PySetObject *)result, other) == -1) {
1655 Py_DECREF(result);
1656 return NULL;
1657 }
1658 }
1659 return result;
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001660}
1661
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001662PyDoc_STRVAR(difference_doc,
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001663"Return the difference of two or more sets as a new set.\n\
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001664\n\
Amaury Forgeot d'Arcfdfe62d2008-06-17 20:36:03 +00001665(i.e. all elements that are in this set but not the others.)");
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001666static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001667set_sub(PySetObject *so, PyObject *other)
1668{
Brian Curtindfc80e32011-08-10 20:28:54 -05001669 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1670 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001671 return set_difference(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001672}
1673
1674static PyObject *
1675set_isub(PySetObject *so, PyObject *other)
1676{
Brian Curtindfc80e32011-08-10 20:28:54 -05001677 if (!PyAnySet_Check(other))
1678 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001679 if (set_difference_update_internal(so, other) == -1)
1680 return NULL;
1681 Py_INCREF(so);
1682 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001683}
1684
1685static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001686set_symmetric_difference_update(PySetObject *so, PyObject *other)
1687{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001688 PySetObject *otherset;
1689 PyObject *key;
1690 Py_ssize_t pos = 0;
1691 setentry *entry;
Raymond Hettingerc991db22005-08-11 07:58:45 +00001692
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001693 if ((PyObject *)so == other)
1694 return set_clear(so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001695
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001696 if (PyDict_CheckExact(other)) {
1697 PyObject *value;
1698 int rv;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001699 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001700 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
1701 setentry an_entry;
Thomas Wouters89f507f2006-12-13 04:49:30 +00001702
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001703 Py_INCREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001704 an_entry.hash = hash;
1705 an_entry.key = key;
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001706
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001707 rv = set_discard_entry(so, &an_entry);
Georg Brandl2d444492010-09-03 10:52:55 +00001708 if (rv == -1) {
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001709 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001710 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001711 }
Raymond Hettingerfaf7b7f2010-09-03 10:00:50 +00001712 if (rv == DISCARD_NOTFOUND) {
1713 if (set_add_entry(so, &an_entry) == -1) {
1714 Py_DECREF(key);
1715 return NULL;
1716 }
1717 }
Georg Brandl2d444492010-09-03 10:52:55 +00001718 Py_DECREF(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001719 }
1720 Py_RETURN_NONE;
1721 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001722
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001723 if (PyAnySet_Check(other)) {
1724 Py_INCREF(other);
1725 otherset = (PySetObject *)other;
1726 } else {
1727 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1728 if (otherset == NULL)
1729 return NULL;
1730 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001731
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001732 while (set_next(otherset, &pos, &entry)) {
1733 int rv = set_discard_entry(so, entry);
1734 if (rv == -1) {
1735 Py_DECREF(otherset);
1736 return NULL;
1737 }
1738 if (rv == DISCARD_NOTFOUND) {
1739 if (set_add_entry(so, entry) == -1) {
1740 Py_DECREF(otherset);
1741 return NULL;
1742 }
1743 }
1744 }
1745 Py_DECREF(otherset);
1746 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001747}
1748
1749PyDoc_STRVAR(symmetric_difference_update_doc,
1750"Update a set with the symmetric difference of itself and another.");
1751
1752static PyObject *
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001753set_symmetric_difference(PySetObject *so, PyObject *other)
1754{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001755 PyObject *rv;
1756 PySetObject *otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001757
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001758 otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1759 if (otherset == NULL)
1760 return NULL;
1761 rv = set_symmetric_difference_update(otherset, (PyObject *)so);
1762 if (rv == NULL)
1763 return NULL;
1764 Py_DECREF(rv);
1765 return (PyObject *)otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001766}
1767
1768PyDoc_STRVAR(symmetric_difference_doc,
1769"Return the symmetric difference of two sets as a new set.\n\
1770\n\
1771(i.e. all elements that are in exactly one of the sets.)");
1772
1773static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001774set_xor(PySetObject *so, PyObject *other)
1775{
Brian Curtindfc80e32011-08-10 20:28:54 -05001776 if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1777 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001778 return set_symmetric_difference(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +00001779}
1780
1781static PyObject *
1782set_ixor(PySetObject *so, PyObject *other)
1783{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001784 PyObject *result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001785
Brian Curtindfc80e32011-08-10 20:28:54 -05001786 if (!PyAnySet_Check(other))
1787 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001788 result = set_symmetric_difference_update(so, other);
1789 if (result == NULL)
1790 return NULL;
1791 Py_DECREF(result);
1792 Py_INCREF(so);
1793 return (PyObject *)so;
Raymond Hettingera690a992003-11-16 16:17:49 +00001794}
1795
1796static PyObject *
1797set_issubset(PySetObject *so, PyObject *other)
1798{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001799 setentry *entry;
1800 Py_ssize_t pos = 0;
Raymond Hettingera690a992003-11-16 16:17:49 +00001801
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001802 if (!PyAnySet_Check(other)) {
1803 PyObject *tmp, *result;
1804 tmp = make_new_set(&PySet_Type, other);
1805 if (tmp == NULL)
1806 return NULL;
1807 result = set_issubset(so, tmp);
1808 Py_DECREF(tmp);
1809 return result;
1810 }
1811 if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
1812 Py_RETURN_FALSE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001813
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001814 while (set_next(so, &pos, &entry)) {
1815 int rv = set_contains_entry((PySetObject *)other, entry);
1816 if (rv == -1)
1817 return NULL;
1818 if (!rv)
1819 Py_RETURN_FALSE;
1820 }
1821 Py_RETURN_TRUE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001822}
1823
1824PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
1825
1826static PyObject *
1827set_issuperset(PySetObject *so, PyObject *other)
1828{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001829 PyObject *tmp, *result;
Raymond Hettinger3fbec702003-11-21 07:56:36 +00001830
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001831 if (!PyAnySet_Check(other)) {
1832 tmp = make_new_set(&PySet_Type, other);
1833 if (tmp == NULL)
1834 return NULL;
1835 result = set_issuperset(so, tmp);
1836 Py_DECREF(tmp);
1837 return result;
1838 }
1839 return set_issubset((PySetObject *)other, (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001840}
1841
1842PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
1843
Raymond Hettingera690a992003-11-16 16:17:49 +00001844static PyObject *
1845set_richcompare(PySetObject *v, PyObject *w, int op)
1846{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001847 PyObject *r1, *r2;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001848
Brian Curtindfc80e32011-08-10 20:28:54 -05001849 if(!PyAnySet_Check(w))
1850 Py_RETURN_NOTIMPLEMENTED;
1851
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001852 switch (op) {
1853 case Py_EQ:
1854 if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
1855 Py_RETURN_FALSE;
1856 if (v->hash != -1 &&
1857 ((PySetObject *)w)->hash != -1 &&
1858 v->hash != ((PySetObject *)w)->hash)
1859 Py_RETURN_FALSE;
1860 return set_issubset(v, w);
1861 case Py_NE:
1862 r1 = set_richcompare(v, w, Py_EQ);
1863 if (r1 == NULL)
1864 return NULL;
1865 r2 = PyBool_FromLong(PyObject_Not(r1));
1866 Py_DECREF(r1);
1867 return r2;
1868 case Py_LE:
1869 return set_issubset(v, w);
1870 case Py_GE:
1871 return set_issuperset(v, w);
1872 case Py_LT:
1873 if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))
1874 Py_RETURN_FALSE;
1875 return set_issubset(v, w);
1876 case Py_GT:
1877 if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
1878 Py_RETURN_FALSE;
1879 return set_issuperset(v, w);
1880 }
Brian Curtindfc80e32011-08-10 20:28:54 -05001881 Py_RETURN_NOTIMPLEMENTED;
Raymond Hettingera690a992003-11-16 16:17:49 +00001882}
1883
Raymond Hettingera690a992003-11-16 16:17:49 +00001884static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001885set_add(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001886{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001887 if (set_add_key(so, key) == -1)
1888 return NULL;
1889 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001890}
1891
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001892PyDoc_STRVAR(add_doc,
Raymond Hettingera690a992003-11-16 16:17:49 +00001893"Add an element to a set.\n\
1894\n\
1895This has no effect if the element is already present.");
1896
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001897static int
1898set_contains(PySetObject *so, PyObject *key)
1899{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001900 PyObject *tmpkey;
1901 int rv;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001902
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001903 rv = set_contains_key(so, key);
1904 if (rv == -1) {
1905 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1906 return -1;
1907 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001908 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001909 if (tmpkey == NULL)
1910 return -1;
Petri Lehtinen5acc27e2011-10-30 13:56:41 +02001911 rv = set_contains_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001912 Py_DECREF(tmpkey);
1913 }
1914 return rv;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001915}
1916
1917static PyObject *
1918set_direct_contains(PySetObject *so, PyObject *key)
1919{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001920 long result;
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001921
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001922 result = set_contains(so, key);
1923 if (result == -1)
1924 return NULL;
1925 return PyBool_FromLong(result);
Raymond Hettingerce8185e2005-08-13 09:28:48 +00001926}
1927
1928PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
1929
Raymond Hettingera690a992003-11-16 16:17:49 +00001930static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001931set_remove(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001932{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001933 PyObject *tmpkey;
1934 int rv;
Raymond Hettingerbfd334a2003-11-22 03:55:23 +00001935
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001936 rv = set_discard_key(so, key);
1937 if (rv == -1) {
1938 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1939 return NULL;
1940 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001941 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001942 if (tmpkey == NULL)
1943 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001944 rv = set_discard_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001945 Py_DECREF(tmpkey);
1946 if (rv == -1)
1947 return NULL;
1948 }
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00001949
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001950 if (rv == DISCARD_NOTFOUND) {
1951 set_key_error(key);
1952 return NULL;
1953 }
1954 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001955}
1956
1957PyDoc_STRVAR(remove_doc,
1958"Remove an element from a set; it must be a member.\n\
1959\n\
1960If the element is not a member, raise a KeyError.");
1961
1962static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001963set_discard(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001964{
Benjamin Peterson2b50a012011-10-30 14:24:44 -04001965 PyObject *tmpkey;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001966 int rv;
Raymond Hettinger0deab622003-12-13 18:53:18 +00001967
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001968 rv = set_discard_key(so, key);
1969 if (rv == -1) {
1970 if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1971 return NULL;
1972 PyErr_Clear();
Raymond Hettinger38bf2cc2010-08-06 09:52:17 +00001973 tmpkey = make_new_set(&PyFrozenSet_Type, key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001974 if (tmpkey == NULL)
1975 return NULL;
Petri Lehtinene0aa8032011-10-30 14:31:27 +02001976 rv = set_discard_key(so, tmpkey);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001977 Py_DECREF(tmpkey);
Petri Lehtinene0aa8032011-10-30 14:31:27 +02001978 if (rv == -1)
1979 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001980 }
1981 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001982}
1983
1984PyDoc_STRVAR(discard_doc,
1985"Remove an element from a set if it is a member.\n\
1986\n\
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001987If the element is not a member, do nothing.");
Raymond Hettingera690a992003-11-16 16:17:49 +00001988
1989static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001990set_reduce(PySetObject *so)
1991{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001992 PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;
Martin v. Löwisbd928fe2011-10-14 10:20:37 +02001993 _Py_IDENTIFIER(__dict__);
Raymond Hettingera690a992003-11-16 16:17:49 +00001994
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001995 keys = PySequence_List((PyObject *)so);
1996 if (keys == NULL)
1997 goto done;
1998 args = PyTuple_Pack(1, keys);
1999 if (args == NULL)
2000 goto done;
Martin v. Löwis1ee1b6f2011-10-10 18:11:30 +02002001 dict = _PyObject_GetAttrId((PyObject *)so, &PyId___dict__);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002002 if (dict == NULL) {
2003 PyErr_Clear();
2004 dict = Py_None;
2005 Py_INCREF(dict);
2006 }
2007 result = PyTuple_Pack(3, Py_TYPE(so), args, dict);
Raymond Hettingera690a992003-11-16 16:17:49 +00002008done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002009 Py_XDECREF(args);
2010 Py_XDECREF(keys);
2011 Py_XDECREF(dict);
2012 return result;
Raymond Hettingera690a992003-11-16 16:17:49 +00002013}
2014
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00002015static PyObject *
2016set_sizeof(PySetObject *so)
2017{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002018 Py_ssize_t res;
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00002019
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002020 res = sizeof(PySetObject);
2021 if (so->table != so->smalltable)
2022 res = res + (so->mask + 1) * sizeof(setentry);
2023 return PyLong_FromSsize_t(res);
Robert Schuppeniesfbe94c52008-07-14 10:13:31 +00002024}
2025
2026PyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes");
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00002027static int
2028set_init(PySetObject *self, PyObject *args, PyObject *kwds)
2029{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002030 PyObject *iterable = NULL;
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00002031
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002032 if (!PyAnySet_Check(self))
2033 return -1;
2034 if (PySet_Check(self) && !_PyArg_NoKeywords("set()", kwds))
2035 return -1;
2036 if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable))
2037 return -1;
2038 set_clear_internal(self);
2039 self->hash = -1;
2040 if (iterable == NULL)
2041 return 0;
2042 return set_update_internal(self, iterable);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00002043}
2044
Raymond Hettingera690a992003-11-16 16:17:49 +00002045static PySequenceMethods set_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002046 set_len, /* sq_length */
2047 0, /* sq_concat */
2048 0, /* sq_repeat */
2049 0, /* sq_item */
2050 0, /* sq_slice */
2051 0, /* sq_ass_item */
2052 0, /* sq_ass_slice */
2053 (objobjproc)set_contains, /* sq_contains */
Raymond Hettingera690a992003-11-16 16:17:49 +00002054};
2055
2056/* set object ********************************************************/
2057
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002058#ifdef Py_DEBUG
2059static PyObject *test_c_api(PySetObject *so);
2060
2061PyDoc_STRVAR(test_c_api_doc, "Exercises C API. Returns True.\n\
2062All is well if assertions don't fail.");
2063#endif
2064
Raymond Hettingera690a992003-11-16 16:17:49 +00002065static PyMethodDef set_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002066 {"add", (PyCFunction)set_add, METH_O,
2067 add_doc},
2068 {"clear", (PyCFunction)set_clear, METH_NOARGS,
2069 clear_doc},
2070 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2071 contains_doc},
2072 {"copy", (PyCFunction)set_copy, METH_NOARGS,
2073 copy_doc},
2074 {"discard", (PyCFunction)set_discard, METH_O,
2075 discard_doc},
2076 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2077 difference_doc},
2078 {"difference_update", (PyCFunction)set_difference_update, METH_VARARGS,
2079 difference_update_doc},
2080 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2081 intersection_doc},
2082 {"intersection_update",(PyCFunction)set_intersection_update_multi, METH_VARARGS,
2083 intersection_update_doc},
2084 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2085 isdisjoint_doc},
2086 {"issubset", (PyCFunction)set_issubset, METH_O,
2087 issubset_doc},
2088 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2089 issuperset_doc},
2090 {"pop", (PyCFunction)set_pop, METH_NOARGS,
2091 pop_doc},
2092 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2093 reduce_doc},
2094 {"remove", (PyCFunction)set_remove, METH_O,
2095 remove_doc},
2096 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2097 sizeof_doc},
2098 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2099 symmetric_difference_doc},
2100 {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O,
2101 symmetric_difference_update_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002102#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002103 {"test_c_api", (PyCFunction)test_c_api, METH_NOARGS,
2104 test_c_api_doc},
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002105#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002106 {"union", (PyCFunction)set_union, METH_VARARGS,
2107 union_doc},
2108 {"update", (PyCFunction)set_update, METH_VARARGS,
2109 update_doc},
2110 {NULL, NULL} /* sentinel */
Raymond Hettingera690a992003-11-16 16:17:49 +00002111};
2112
2113static PyNumberMethods set_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002114 0, /*nb_add*/
2115 (binaryfunc)set_sub, /*nb_subtract*/
2116 0, /*nb_multiply*/
2117 0, /*nb_remainder*/
2118 0, /*nb_divmod*/
2119 0, /*nb_power*/
2120 0, /*nb_negative*/
2121 0, /*nb_positive*/
2122 0, /*nb_absolute*/
2123 0, /*nb_bool*/
2124 0, /*nb_invert*/
2125 0, /*nb_lshift*/
2126 0, /*nb_rshift*/
2127 (binaryfunc)set_and, /*nb_and*/
2128 (binaryfunc)set_xor, /*nb_xor*/
2129 (binaryfunc)set_or, /*nb_or*/
2130 0, /*nb_int*/
2131 0, /*nb_reserved*/
2132 0, /*nb_float*/
2133 0, /*nb_inplace_add*/
2134 (binaryfunc)set_isub, /*nb_inplace_subtract*/
2135 0, /*nb_inplace_multiply*/
2136 0, /*nb_inplace_remainder*/
2137 0, /*nb_inplace_power*/
2138 0, /*nb_inplace_lshift*/
2139 0, /*nb_inplace_rshift*/
2140 (binaryfunc)set_iand, /*nb_inplace_and*/
2141 (binaryfunc)set_ixor, /*nb_inplace_xor*/
2142 (binaryfunc)set_ior, /*nb_inplace_or*/
Raymond Hettingera690a992003-11-16 16:17:49 +00002143};
2144
2145PyDoc_STRVAR(set_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002146"set() -> new empty set object\n\
2147set(iterable) -> new set object\n\
Raymond Hettingera690a992003-11-16 16:17:49 +00002148\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002149Build an unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00002150
2151PyTypeObject PySet_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002152 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2153 "set", /* tp_name */
2154 sizeof(PySetObject), /* tp_basicsize */
2155 0, /* tp_itemsize */
2156 /* methods */
2157 (destructor)set_dealloc, /* tp_dealloc */
2158 0, /* tp_print */
2159 0, /* tp_getattr */
2160 0, /* tp_setattr */
2161 0, /* tp_reserved */
2162 (reprfunc)set_repr, /* tp_repr */
2163 &set_as_number, /* tp_as_number */
2164 &set_as_sequence, /* tp_as_sequence */
2165 0, /* tp_as_mapping */
Georg Brandl00da4e02010-10-18 07:32:48 +00002166 PyObject_HashNotImplemented, /* tp_hash */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002167 0, /* tp_call */
2168 0, /* tp_str */
2169 PyObject_GenericGetAttr, /* tp_getattro */
2170 0, /* tp_setattro */
2171 0, /* tp_as_buffer */
2172 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2173 Py_TPFLAGS_BASETYPE, /* tp_flags */
2174 set_doc, /* tp_doc */
2175 (traverseproc)set_traverse, /* tp_traverse */
2176 (inquiry)set_clear_internal, /* tp_clear */
2177 (richcmpfunc)set_richcompare, /* tp_richcompare */
Georg Brandl00da4e02010-10-18 07:32:48 +00002178 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2179 (getiterfunc)set_iter, /* tp_iter */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002180 0, /* tp_iternext */
2181 set_methods, /* tp_methods */
2182 0, /* tp_members */
2183 0, /* tp_getset */
2184 0, /* tp_base */
2185 0, /* tp_dict */
2186 0, /* tp_descr_get */
2187 0, /* tp_descr_set */
2188 0, /* tp_dictoffset */
2189 (initproc)set_init, /* tp_init */
2190 PyType_GenericAlloc, /* tp_alloc */
2191 set_new, /* tp_new */
2192 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002193};
2194
2195/* frozenset object ********************************************************/
2196
2197
2198static PyMethodDef frozenset_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002199 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2200 contains_doc},
2201 {"copy", (PyCFunction)frozenset_copy, METH_NOARGS,
2202 copy_doc},
2203 {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2204 difference_doc},
2205 {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2206 intersection_doc},
2207 {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2208 isdisjoint_doc},
2209 {"issubset", (PyCFunction)set_issubset, METH_O,
2210 issubset_doc},
2211 {"issuperset", (PyCFunction)set_issuperset, METH_O,
2212 issuperset_doc},
2213 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2214 reduce_doc},
2215 {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2216 sizeof_doc},
2217 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2218 symmetric_difference_doc},
2219 {"union", (PyCFunction)set_union, METH_VARARGS,
2220 union_doc},
2221 {NULL, NULL} /* sentinel */
Raymond Hettingera690a992003-11-16 16:17:49 +00002222};
2223
2224static PyNumberMethods frozenset_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002225 0, /*nb_add*/
2226 (binaryfunc)set_sub, /*nb_subtract*/
2227 0, /*nb_multiply*/
2228 0, /*nb_remainder*/
2229 0, /*nb_divmod*/
2230 0, /*nb_power*/
2231 0, /*nb_negative*/
2232 0, /*nb_positive*/
2233 0, /*nb_absolute*/
2234 0, /*nb_bool*/
2235 0, /*nb_invert*/
2236 0, /*nb_lshift*/
2237 0, /*nb_rshift*/
2238 (binaryfunc)set_and, /*nb_and*/
2239 (binaryfunc)set_xor, /*nb_xor*/
2240 (binaryfunc)set_or, /*nb_or*/
Raymond Hettingera690a992003-11-16 16:17:49 +00002241};
2242
2243PyDoc_STRVAR(frozenset_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002244"frozenset() -> empty frozenset object\n\
2245frozenset(iterable) -> frozenset object\n\
Raymond Hettingera690a992003-11-16 16:17:49 +00002246\n\
Thomas Wouters0e3f5912006-08-11 14:57:12 +00002247Build an immutable unordered collection of unique elements.");
Raymond Hettingera690a992003-11-16 16:17:49 +00002248
2249PyTypeObject PyFrozenSet_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002250 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2251 "frozenset", /* tp_name */
2252 sizeof(PySetObject), /* tp_basicsize */
2253 0, /* tp_itemsize */
2254 /* methods */
2255 (destructor)set_dealloc, /* tp_dealloc */
2256 0, /* tp_print */
2257 0, /* tp_getattr */
2258 0, /* tp_setattr */
2259 0, /* tp_reserved */
2260 (reprfunc)set_repr, /* tp_repr */
2261 &frozenset_as_number, /* tp_as_number */
2262 &set_as_sequence, /* tp_as_sequence */
2263 0, /* tp_as_mapping */
2264 frozenset_hash, /* tp_hash */
2265 0, /* tp_call */
2266 0, /* tp_str */
2267 PyObject_GenericGetAttr, /* tp_getattro */
2268 0, /* tp_setattro */
2269 0, /* tp_as_buffer */
2270 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2271 Py_TPFLAGS_BASETYPE, /* tp_flags */
2272 frozenset_doc, /* tp_doc */
2273 (traverseproc)set_traverse, /* tp_traverse */
2274 (inquiry)set_clear_internal, /* tp_clear */
2275 (richcmpfunc)set_richcompare, /* tp_richcompare */
2276 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2277 (getiterfunc)set_iter, /* tp_iter */
2278 0, /* tp_iternext */
2279 frozenset_methods, /* tp_methods */
2280 0, /* tp_members */
2281 0, /* tp_getset */
2282 0, /* tp_base */
2283 0, /* tp_dict */
2284 0, /* tp_descr_get */
2285 0, /* tp_descr_set */
2286 0, /* tp_dictoffset */
2287 0, /* tp_init */
2288 PyType_GenericAlloc, /* tp_alloc */
2289 frozenset_new, /* tp_new */
2290 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00002291};
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002292
2293
2294/***** C API functions *************************************************/
2295
2296PyObject *
2297PySet_New(PyObject *iterable)
2298{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002299 return make_new_set(&PySet_Type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002300}
2301
2302PyObject *
2303PyFrozenSet_New(PyObject *iterable)
2304{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002305 return make_new_set(&PyFrozenSet_Type, iterable);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002306}
2307
Neal Norwitz8c49c822006-03-04 18:41:19 +00002308Py_ssize_t
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002309PySet_Size(PyObject *anyset)
2310{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002311 if (!PyAnySet_Check(anyset)) {
2312 PyErr_BadInternalCall();
2313 return -1;
2314 }
2315 return PySet_GET_SIZE(anyset);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002316}
2317
2318int
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002319PySet_Clear(PyObject *set)
2320{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002321 if (!PySet_Check(set)) {
2322 PyErr_BadInternalCall();
2323 return -1;
2324 }
2325 return set_clear_internal((PySetObject *)set);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002326}
2327
2328int
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002329PySet_Contains(PyObject *anyset, PyObject *key)
2330{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002331 if (!PyAnySet_Check(anyset)) {
2332 PyErr_BadInternalCall();
2333 return -1;
2334 }
2335 return set_contains_key((PySetObject *)anyset, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002336}
2337
2338int
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002339PySet_Discard(PyObject *set, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002340{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002341 if (!PySet_Check(set)) {
2342 PyErr_BadInternalCall();
2343 return -1;
2344 }
2345 return set_discard_key((PySetObject *)set, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002346}
2347
2348int
Christian Heimesfd66e512008-01-29 12:18:50 +00002349PySet_Add(PyObject *anyset, PyObject *key)
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002350{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002351 if (!PySet_Check(anyset) &&
2352 (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
2353 PyErr_BadInternalCall();
2354 return -1;
2355 }
2356 return set_add_key((PySetObject *)anyset, key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002357}
2358
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002359int
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002360_PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash)
Guido van Rossumd8faa362007-04-27 19:54:29 +00002361{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002362 setentry *entry;
Guido van Rossumd8faa362007-04-27 19:54:29 +00002363
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002364 if (!PyAnySet_Check(set)) {
2365 PyErr_BadInternalCall();
2366 return -1;
2367 }
2368 if (set_next((PySetObject *)set, pos, &entry) == 0)
2369 return 0;
2370 *key = entry->key;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002371 *hash = entry->hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002372 return 1;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002373}
2374
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002375PyObject *
2376PySet_Pop(PyObject *set)
2377{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002378 if (!PySet_Check(set)) {
2379 PyErr_BadInternalCall();
2380 return NULL;
2381 }
2382 return set_pop((PySetObject *)set);
Raymond Hettingerbeb31012005-08-16 03:47:52 +00002383}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002384
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002385int
2386_PySet_Update(PyObject *set, PyObject *iterable)
2387{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002388 if (!PySet_Check(set)) {
2389 PyErr_BadInternalCall();
2390 return -1;
2391 }
2392 return set_update_internal((PySetObject *)set, iterable);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002393}
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002394
2395#ifdef Py_DEBUG
2396
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002397/* Test code to be called with any three element set.
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002398 Returns True and original set is restored. */
2399
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002400#define assertRaises(call_return_value, exception) \
2401 do { \
2402 assert(call_return_value); \
2403 assert(PyErr_ExceptionMatches(exception)); \
2404 PyErr_Clear(); \
2405 } while(0)
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002406
2407static PyObject *
2408test_c_api(PySetObject *so)
2409{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002410 Py_ssize_t count;
2411 char *s;
2412 Py_ssize_t i;
2413 PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x;
2414 PyObject *ob = (PyObject *)so;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002415 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002416 PyObject *str;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002417
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002418 /* Verify preconditions */
2419 assert(PyAnySet_Check(ob));
2420 assert(PyAnySet_CheckExact(ob));
2421 assert(!PyFrozenSet_CheckExact(ob));
Victor Stinner08b36bd2010-03-13 00:19:17 +00002422
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002423 /* so.clear(); so |= set("abc"); */
2424 str = PyUnicode_FromString("abc");
2425 if (str == NULL)
2426 return NULL;
2427 set_clear_internal(so);
2428 if (set_update_internal(so, str) == -1) {
2429 Py_DECREF(str);
2430 return NULL;
2431 }
2432 Py_DECREF(str);
Victor Stinner08b36bd2010-03-13 00:19:17 +00002433
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002434 /* Exercise type/size checks */
2435 assert(PySet_Size(ob) == 3);
2436 assert(PySet_GET_SIZE(ob) == 3);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002437
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002438 /* Raise TypeError for non-iterable constructor arguments */
2439 assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
2440 assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002441
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002442 /* Raise TypeError for unhashable key */
2443 dup = PySet_New(ob);
2444 assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
2445 assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
2446 assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002447
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002448 /* Exercise successful pop, contains, add, and discard */
2449 elem = PySet_Pop(ob);
2450 assert(PySet_Contains(ob, elem) == 0);
2451 assert(PySet_GET_SIZE(ob) == 2);
2452 assert(PySet_Add(ob, elem) == 0);
2453 assert(PySet_Contains(ob, elem) == 1);
2454 assert(PySet_GET_SIZE(ob) == 3);
2455 assert(PySet_Discard(ob, elem) == 1);
2456 assert(PySet_GET_SIZE(ob) == 2);
2457 assert(PySet_Discard(ob, elem) == 0);
2458 assert(PySet_GET_SIZE(ob) == 2);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002459
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002460 /* Exercise clear */
2461 dup2 = PySet_New(dup);
2462 assert(PySet_Clear(dup2) == 0);
2463 assert(PySet_Size(dup2) == 0);
2464 Py_DECREF(dup2);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002465
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002466 /* Raise SystemError on clear or update of frozen set */
2467 f = PyFrozenSet_New(dup);
2468 assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
2469 assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
2470 assert(PySet_Add(f, elem) == 0);
2471 Py_INCREF(f);
2472 assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
2473 Py_DECREF(f);
2474 Py_DECREF(f);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002475
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002476 /* Exercise direct iteration */
2477 i = 0, count = 0;
2478 while (_PySet_NextEntry((PyObject *)dup, &i, &x, &hash)) {
2479 s = _PyUnicode_AsString(x);
2480 assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
2481 count++;
2482 }
2483 assert(count == 3);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002484
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002485 /* Exercise updates */
2486 dup2 = PySet_New(NULL);
2487 assert(_PySet_Update(dup2, dup) == 0);
2488 assert(PySet_Size(dup2) == 3);
2489 assert(_PySet_Update(dup2, dup) == 0);
2490 assert(PySet_Size(dup2) == 3);
2491 Py_DECREF(dup2);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002492
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002493 /* Raise SystemError when self argument is not a set or frozenset. */
2494 t = PyTuple_New(0);
2495 assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
2496 assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
2497 Py_DECREF(t);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002498
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002499 /* Raise SystemError when self argument is not a set. */
2500 f = PyFrozenSet_New(dup);
2501 assert(PySet_Size(f) == 3);
2502 assert(PyFrozenSet_CheckExact(f));
2503 assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
2504 assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
2505 Py_DECREF(f);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002506
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002507 /* Raise KeyError when popping from an empty set */
2508 assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
2509 Py_DECREF(ob);
2510 assert(PySet_GET_SIZE(ob) == 0);
2511 assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002512
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002513 /* Restore the set from the copy using the PyNumber API */
2514 assert(PyNumber_InPlaceOr(ob, dup) == ob);
2515 Py_DECREF(ob);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002516
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002517 /* Verify constructors accept NULL arguments */
2518 f = PySet_New(NULL);
2519 assert(f != NULL);
2520 assert(PySet_GET_SIZE(f) == 0);
2521 Py_DECREF(f);
2522 f = PyFrozenSet_New(NULL);
2523 assert(f != NULL);
2524 assert(PyFrozenSet_CheckExact(f));
2525 assert(PySet_GET_SIZE(f) == 0);
2526 Py_DECREF(f);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002527
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002528 Py_DECREF(elem);
2529 Py_DECREF(dup);
2530 Py_RETURN_TRUE;
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002531}
2532
Raymond Hettinger9bda1d62005-09-16 07:14:21 +00002533#undef assertRaises
2534
Raymond Hettingerc47e01d2005-08-16 10:44:15 +00002535#endif
Raymond Hettingerbfc1e1a2013-08-23 03:22:15 -05002536
2537/***** Dummy Struct *************************************************/
2538
2539static PyObject *
2540dummy_repr(PyObject *op)
2541{
2542 return PyUnicode_FromString("<dummy key>");
2543}
2544
2545static void
2546dummy_dealloc(PyObject* ignore)
2547{
2548 Py_FatalError("deallocating <dummy key>");
2549}
2550
2551static PyTypeObject _PySetDummy_Type = {
2552 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2553 "<dummy key> type",
2554 0,
2555 0,
2556 dummy_dealloc, /*tp_dealloc*/ /*never called*/
2557 0, /*tp_print*/
2558 0, /*tp_getattr*/
2559 0, /*tp_setattr*/
2560 0, /*tp_reserved*/
2561 dummy_repr, /*tp_repr*/
2562 0, /*tp_as_number*/
2563 0, /*tp_as_sequence*/
2564 0, /*tp_as_mapping*/
2565 0, /*tp_hash */
2566 0, /*tp_call */
2567 0, /*tp_str */
2568 0, /*tp_getattro */
2569 0, /*tp_setattro */
2570 0, /*tp_as_buffer */
2571 Py_TPFLAGS_DEFAULT, /*tp_flags */
2572};
2573
2574static PyObject _dummy_struct = {
2575 _PyObject_EXTRA_INIT
2576 2, &_PySetDummy_Type
2577};
2578