blob: 9952ec0487bc65ff26952a9c9f686e2fb5d39920 [file] [log] [blame]
Raymond Hettingera9d99362005-08-05 00:01:15 +00001/* set object implementation
2 Written and maintained by Raymond D. Hettinger <python@rcn.com>
3 Derived from Lib/sets.py and Objects/dictobject.c.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00004
Raymond Hettingera9d99362005-08-05 00:01:15 +00005 Copyright (c) 2003-5 Python Software Foundation.
6 All rights reserved.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00007*/
8
Raymond Hettingera690a992003-11-16 16:17:49 +00009#include "Python.h"
Raymond Hettingera9d99362005-08-05 00:01:15 +000010#include "structmember.h"
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000011
12/* This must be >= 1. */
13#define PERTURB_SHIFT 5
14
15/* Object used as dummy key to fill deleted entries */
Raymond Hettingera9d99362005-08-05 00:01:15 +000016static PyObject *dummy = NULL; /* Initialized by first call to make_new_set() */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000017
18#define EMPTY_TO_MINSIZE(so) do { \
19 memset((so)->smalltable, 0, sizeof((so)->smalltable)); \
20 (so)->used = (so)->fill = 0; \
21 (so)->table = (so)->smalltable; \
22 (so)->mask = PySet_MINSIZE - 1; \
23 } while(0)
24
25
26/*
27The basic lookup function used by all operations.
28This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
29Open addressing is preferred over chaining since the link overhead for
30chaining would be substantial (100% with typical malloc overhead).
31
32The initial probe index is computed as hash mod the table size. Subsequent
33probe indices are computed as explained earlier.
34
35All arithmetic on hash should ignore overflow.
36
37This function must never return NULL; failures are indicated by returning
38a setentry* for which the value field is NULL. Exceptions are never
39reported by this function, and outstanding exceptions are maintained.
40*/
41
42static setentry *
43set_lookkey(PySetObject *so, PyObject *key, register long hash)
44{
45 register int i;
46 register unsigned int perturb;
47 register setentry *freeslot;
48 register unsigned int mask = so->mask;
Raymond Hettingera580c472005-08-05 17:19:54 +000049 setentry *table = so->table;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +000050 register setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000051 register int restore_error;
52 register int checked_error;
53 register int cmp;
54 PyObject *err_type, *err_value, *err_tb;
55 PyObject *startkey;
56
57 i = hash & mask;
Raymond Hettingera580c472005-08-05 17:19:54 +000058 entry = &table[i];
Raymond Hettinger06d8cf82005-07-31 15:36:06 +000059 if (entry->key == NULL || entry->key == key)
60 return entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000061
62 restore_error = checked_error = 0;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +000063 if (entry->key == dummy)
64 freeslot = entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000065 else {
Raymond Hettinger06d8cf82005-07-31 15:36:06 +000066 if (entry->hash == hash) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000067 /* error can't have been checked yet */
68 checked_error = 1;
69 if (PyErr_Occurred()) {
70 restore_error = 1;
71 PyErr_Fetch(&err_type, &err_value, &err_tb);
72 }
Raymond Hettinger06d8cf82005-07-31 15:36:06 +000073 startkey = entry->key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000074 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
75 if (cmp < 0)
76 PyErr_Clear();
Raymond Hettingera580c472005-08-05 17:19:54 +000077 if (table == so->table && entry->key == startkey) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000078 if (cmp > 0)
79 goto Done;
80 }
81 else {
82 /* The compare did major nasty stuff to the
83 * set: start over.
84 */
Raymond Hettinger06d8cf82005-07-31 15:36:06 +000085 entry = set_lookkey(so, key, hash);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000086 goto Done;
87 }
88 }
89 freeslot = NULL;
90 }
91
92 /* In the loop, key == dummy is by far (factor of 100s) the
93 least likely outcome, so test for that last. */
94 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
95 i = (i << 2) + i + perturb + 1;
Raymond Hettingera580c472005-08-05 17:19:54 +000096 entry = &table[i & mask];
Raymond Hettinger06d8cf82005-07-31 15:36:06 +000097 if (entry->key == NULL) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000098 if (freeslot != NULL)
Raymond Hettinger06d8cf82005-07-31 15:36:06 +000099 entry = freeslot;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000100 break;
101 }
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000102 if (entry->key == key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000103 break;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000104 if (entry->hash == hash && entry->key != dummy) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000105 if (!checked_error) {
106 checked_error = 1;
107 if (PyErr_Occurred()) {
108 restore_error = 1;
109 PyErr_Fetch(&err_type, &err_value,
110 &err_tb);
111 }
112 }
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000113 startkey = entry->key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000114 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
115 if (cmp < 0)
116 PyErr_Clear();
Raymond Hettingera580c472005-08-05 17:19:54 +0000117 if (table == so->table && entry->key == startkey) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000118 if (cmp > 0)
119 break;
120 }
121 else {
122 /* The compare did major nasty stuff to the
123 * set: start over.
124 */
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000125 entry = set_lookkey(so, key, hash);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000126 break;
127 }
128 }
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000129 else if (entry->key == dummy && freeslot == NULL)
130 freeslot = entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000131 }
132
133Done:
134 if (restore_error)
135 PyErr_Restore(err_type, err_value, err_tb);
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000136 return entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000137}
138
139/*
140 * Hacked up version of set_lookkey which can assume keys are always strings;
141 * this assumption allows testing for errors during PyObject_Compare() to
142 * be dropped; string-string comparisons never raise exceptions. This also
143 * means we don't need to go through PyObject_Compare(); we can always use
144 * _PyString_Eq directly.
145 *
146 * This is valuable because the general-case error handling in set_lookkey() is
147 * expensive, and sets with pure-string keys may be very common.
148 */
149static setentry *
150set_lookkey_string(PySetObject *so, PyObject *key, register long hash)
151{
152 register int i;
153 register unsigned int perturb;
154 register setentry *freeslot;
155 register unsigned int mask = so->mask;
Raymond Hettingera580c472005-08-05 17:19:54 +0000156 setentry *table = so->table;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000157 register setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000158
159 /* Make sure this function doesn't have to handle non-string keys,
160 including subclasses of str; e.g., one reason to subclass
161 strings is to override __eq__, and for speed we don't cater to
162 that here. */
163 if (!PyString_CheckExact(key)) {
164 so->lookup = set_lookkey;
165 return set_lookkey(so, key, hash);
166 }
167 i = hash & mask;
Raymond Hettingera580c472005-08-05 17:19:54 +0000168 entry = &table[i];
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000169 if (entry->key == NULL || entry->key == key)
170 return entry;
Raymond Hettingera580c472005-08-05 17:19:54 +0000171 if (so->fill != so->used) {
172 if (entry->key == dummy)
173 freeslot = entry;
174 else {
175 if (entry->hash == hash && _PyString_Eq(entry->key, key))
176 return entry;
177 freeslot = NULL;
178 }
179
180 /* In the loop, key == dummy is by far (factor of 100s) the
181 least likely outcome, so test for that last. */
182 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
183 i = (i << 2) + i + perturb + 1;
184 entry = &table[i & mask];
185 if (entry->key == NULL)
186 return freeslot == NULL ? entry : freeslot;
187 if (entry->key == key
188 || (entry->hash == hash
189 && entry->key != dummy
190 && _PyString_Eq(entry->key, key)))
191 return entry;
192 if (entry->key == dummy && freeslot == NULL)
193 freeslot = entry;
194 }
195 } else {
196 /* Simplified loop that can assume are no dummy entries */
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000197 if (entry->hash == hash && _PyString_Eq(entry->key, key))
198 return entry;
Raymond Hettingera580c472005-08-05 17:19:54 +0000199 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
200 i = (i << 2) + i + perturb + 1;
201 entry = &table[i & mask];
202 if (entry->key == NULL)
203 return entry;
204 if (entry->key == key
205 || (entry->hash == hash
206 && _PyString_Eq(entry->key, key)))
207 return entry;
208 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000209 }
210}
211
212/*
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000213Internal routine to insert a new key into the table.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000214Used both by the internal resize routine and by the public insert routine.
215Eats a reference to key.
216*/
217static void
218set_insert_key(register PySetObject *so, PyObject *key, long hash)
219{
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000220 register setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000221 typedef setentry *(*lookupfunc)(PySetObject *, PyObject *, long);
222
223 assert(so->lookup != NULL);
224
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000225 entry = so->lookup(so, key, hash);
226 if (entry->key == NULL) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000227 /* UNUSED */
228 so->fill++;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000229 entry->key = key;
230 entry->hash = hash;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000231 so->used++;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000232 } else if (entry->key == dummy) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000233 /* DUMMY */
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000234 entry->key = key;
235 entry->hash = hash;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000236 so->used++;
237 Py_DECREF(dummy);
238 } else {
239 /* ACTIVE */
240 Py_DECREF(key);
241 }
242}
243
244/*
245Restructure the table by allocating a new table and reinserting all
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000246keys again. When entries have been deleted, the new table may
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000247actually be smaller than the old one.
248*/
249static int
250set_table_resize(PySetObject *so, int minused)
251{
252 int newsize;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000253 setentry *oldtable, *newtable, *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000254 int i;
255 int is_oldtable_malloced;
256 setentry small_copy[PySet_MINSIZE];
257
258 assert(minused >= 0);
259
260 /* Find the smallest table size > minused. */
261 for (newsize = PySet_MINSIZE;
262 newsize <= minused && newsize > 0;
263 newsize <<= 1)
264 ;
265 if (newsize <= 0) {
266 PyErr_NoMemory();
267 return -1;
268 }
269
270 /* Get space for a new table. */
271 oldtable = so->table;
272 assert(oldtable != NULL);
273 is_oldtable_malloced = oldtable != so->smalltable;
274
275 if (newsize == PySet_MINSIZE) {
276 /* A large table is shrinking, or we can't get any smaller. */
277 newtable = so->smalltable;
278 if (newtable == oldtable) {
279 if (so->fill == so->used) {
280 /* No dummies, so no point doing anything. */
281 return 0;
282 }
283 /* We're not going to resize it, but rebuild the
284 table anyway to purge old dummy entries.
285 Subtle: This is *necessary* if fill==size,
286 as set_lookkey needs at least one virgin slot to
287 terminate failing searches. If fill < size, it's
288 merely desirable, as dummies slow searches. */
289 assert(so->fill > so->used);
290 memcpy(small_copy, oldtable, sizeof(small_copy));
291 oldtable = small_copy;
292 }
293 }
294 else {
295 newtable = PyMem_NEW(setentry, newsize);
296 if (newtable == NULL) {
297 PyErr_NoMemory();
298 return -1;
299 }
300 }
301
302 /* Make the set empty, using the new table. */
303 assert(newtable != oldtable);
304 so->table = newtable;
305 so->mask = newsize - 1;
306 memset(newtable, 0, sizeof(setentry) * newsize);
307 so->used = 0;
308 i = so->fill;
309 so->fill = 0;
310
311 /* Copy the data over; this is refcount-neutral for active entries;
312 dummy entries aren't copied over, of course */
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000313 for (entry = oldtable; i > 0; entry++) {
314 if (entry->key == NULL) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000315 /* UNUSED */
316 ;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000317 } else if (entry->key == dummy) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000318 /* DUMMY */
319 --i;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000320 assert(entry->key == dummy);
321 Py_DECREF(entry->key);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000322 } else {
323 /* ACTIVE */
324 --i;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000325 set_insert_key(so, entry->key, entry->hash);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000326 }
327 }
328
329 if (is_oldtable_malloced)
330 PyMem_DEL(oldtable);
331 return 0;
332}
333
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000334/* CAUTION: set_add_internal() must guarantee that it won't resize the table */
335static int
336set_add_internal(register PySetObject *so, PyObject *key)
337{
338 register long hash;
339 register int n_used;
340
341 if (PyString_CheckExact(key)) {
342 hash = ((PyStringObject *)key)->ob_shash;
343 if (hash == -1)
344 hash = PyObject_Hash(key);
345 } else {
346 hash = PyObject_Hash(key);
347 if (hash == -1)
348 return -1;
349 }
350 assert(so->fill <= so->mask); /* at least one empty slot */
351 n_used = so->used;
352 Py_INCREF(key);
353 set_insert_key(so, key, hash);
354 if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
355 return 0;
356 return set_table_resize(so, so->used*(so->used>50000 ? 2 : 4));
357}
358
359#define DISCARD_NOTFOUND 0
360#define DISCARD_FOUND 1
361
362static int
363set_discard_internal(PySetObject *so, PyObject *key)
364{
365 register long hash;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000366 register setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000367 PyObject *old_key;
368
369 assert (PyAnySet_Check(so));
370 if (!PyString_CheckExact(key) ||
371 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
372 hash = PyObject_Hash(key);
373 if (hash == -1)
374 return -1;
375 }
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000376 entry = (so->lookup)(so, key, hash);
377 if (entry->key == NULL || entry->key == dummy)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000378 return DISCARD_NOTFOUND;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000379 old_key = entry->key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000380 Py_INCREF(dummy);
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000381 entry->key = dummy;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000382 so->used--;
383 Py_DECREF(old_key);
384 return DISCARD_FOUND;
385}
386
Raymond Hettingerfe889f32005-08-06 05:43:39 +0000387static int
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000388set_clear_internal(PySetObject *so)
389{
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000390 setentry *entry, *table;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000391 int table_is_malloced;
392 int fill;
393 setentry small_copy[PySet_MINSIZE];
394#ifdef Py_DEBUG
395 int i, n;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000396 assert (PyAnySet_Check(so));
Raymond Hettingera580c472005-08-05 17:19:54 +0000397
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000398 n = so->mask + 1;
399 i = 0;
400#endif
401
402 table = so->table;
403 assert(table != NULL);
404 table_is_malloced = table != so->smalltable;
405
406 /* This is delicate. During the process of clearing the set,
407 * decrefs can cause the set to mutate. To avoid fatal confusion
408 * (voice of experience), we have to make the set empty before
Raymond Hettingerfe889f32005-08-06 05:43:39 +0000409 * clearing the slots, and never refer to anything via so->ref while
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000410 * clearing.
411 */
412 fill = so->fill;
413 if (table_is_malloced)
414 EMPTY_TO_MINSIZE(so);
415
416 else if (fill > 0) {
417 /* It's a small table with something that needs to be cleared.
418 * Afraid the only safe way is to copy the set entries into
419 * another small table first.
420 */
421 memcpy(small_copy, table, sizeof(small_copy));
422 table = small_copy;
423 EMPTY_TO_MINSIZE(so);
424 }
425 /* else it's a small table that's already empty */
426
427 /* Now we can finally clear things. If C had refcounts, we could
428 * assert that the refcount on table is 1 now, i.e. that this function
429 * has unique access to it, so decref side-effects can't alter it.
430 */
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000431 for (entry = table; fill > 0; ++entry) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000432#ifdef Py_DEBUG
433 assert(i < n);
434 ++i;
435#endif
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000436 if (entry->key) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000437 --fill;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000438 Py_DECREF(entry->key);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000439 }
440#ifdef Py_DEBUG
441 else
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000442 assert(entry->key == NULL || entry->key == dummy);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000443#endif
444 }
445
446 if (table_is_malloced)
447 PyMem_DEL(table);
Raymond Hettingerfe889f32005-08-06 05:43:39 +0000448 so->hash = -1;
449 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000450}
451
452/*
453 * Iterate over a set table. Use like so:
454 *
Raymond Hettingerd7946662005-08-01 21:39:29 +0000455 * int pos;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000456 * PyObject *key;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000457 * pos = 0; # important! pos should not otherwise be changed by you
458 * while (set_next_internal(yourset, &pos, &key)) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000459 * Refer to borrowed reference in key.
460 * }
461 *
462 * CAUTION: In general, it isn't safe to use set_next_internal in a loop that
463 * mutates the table.
464 */
465static int
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000466set_next_internal(PySetObject *so, int *pos, PyObject **key)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000467{
468 register int i, mask;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000469 register setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000470
471 assert (PyAnySet_Check(so));
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000472 i = *pos;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000473 if (i < 0)
474 return 0;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000475 entry = so->table;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000476 mask = so->mask;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000477 while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000478 i++;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000479 *pos = i+1;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000480 if (i > mask)
481 return 0;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000482 if (key)
483 *key = entry[i].key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000484 return 1;
485}
486
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000487static int
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000488set_merge_internal(PySetObject *so, PyObject *otherset)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000489{
Raymond Hettingerd7946662005-08-01 21:39:29 +0000490 PySetObject *other;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000491 register int i;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000492 register setentry *entry, *othertable;
493 register int othermask;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000494
495 assert (PyAnySet_Check(so));
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000496 assert (PyAnySet_Check(otherset));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000497
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000498 other = (PySetObject*)otherset;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000499 if (other == so || other->used == 0)
500 /* a.update(a) or a.update({}); nothing to do */
501 return 0;
502 /* Do one big resize at the start, rather than
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000503 * incrementally resizing as we insert new keys. Expect
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000504 * that there will be no (or few) overlapping keys.
505 */
506 if ((so->fill + other->used)*3 >= (so->mask+1)*2) {
507 if (set_table_resize(so, (so->used + other->used)*2) != 0)
508 return -1;
509 }
Raymond Hettingerd7946662005-08-01 21:39:29 +0000510 othermask = other->mask;
511 othertable = other->table;
512 for (i = 0; i <= othermask; i++) {
513 entry = &othertable[i];
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000514 if (entry->key != NULL &&
515 entry->key != dummy) {
516 Py_INCREF(entry->key);
517 set_insert_key(so, entry->key, entry->hash);
518 }
519 }
520 return 0;
521}
522
523static int
524set_contains_internal(PySetObject *so, PyObject *key)
525{
526 long hash;
527
528 if (!PyString_CheckExact(key) ||
529 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
530 hash = PyObject_Hash(key);
531 if (hash == -1)
532 return -1;
533 }
534 key = (so->lookup)(so, key, hash)->key;
535 return key != NULL && key != dummy;
536}
537
Raymond Hettingera9d99362005-08-05 00:01:15 +0000538/***** Set iterator type ***********************************************/
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000539
Raymond Hettingerd7946662005-08-01 21:39:29 +0000540static PyTypeObject PySetIter_Type; /* Forward */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000541
542typedef struct {
543 PyObject_HEAD
544 PySetObject *si_set; /* Set to NULL when iterator is exhausted */
545 int si_used;
546 int si_pos;
547 long len;
548} setiterobject;
549
550static PyObject *
551set_iter(PySetObject *so)
552{
553 setiterobject *si = PyObject_New(setiterobject, &PySetIter_Type);
554 if (si == NULL)
555 return NULL;
556 Py_INCREF(so);
557 si->si_set = so;
558 si->si_used = so->used;
559 si->si_pos = 0;
560 si->len = so->used;
561 return (PyObject *)si;
562}
563
564static void
565setiter_dealloc(setiterobject *si)
566{
567 Py_XDECREF(si->si_set);
568 PyObject_Del(si);
569}
570
571static int
572setiter_len(setiterobject *si)
573{
574 if (si->si_set != NULL && si->si_used == si->si_set->used)
575 return si->len;
576 return 0;
577}
578
579static PySequenceMethods setiter_as_sequence = {
580 (inquiry)setiter_len, /* sq_length */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000581};
582
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000583static PyObject *setiter_iternext(setiterobject *si)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000584{
585 PyObject *key;
586 register int i, mask;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000587 register setentry *entry;
588 PySetObject *so = si->si_set;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000589
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000590 if (so == NULL)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000591 return NULL;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000592 assert (PyAnySet_Check(so));
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000593
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000594 if (si->si_used != so->used) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000595 PyErr_SetString(PyExc_RuntimeError,
596 "Set changed size during iteration");
597 si->si_used = -1; /* Make this state sticky */
598 return NULL;
599 }
600
601 i = si->si_pos;
602 if (i < 0)
603 goto fail;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000604 entry = so->table;
605 mask = so->mask;
606 while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000607 i++;
608 si->si_pos = i+1;
609 if (i > mask)
610 goto fail;
611 si->len--;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000612 key = entry[i].key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000613 Py_INCREF(key);
614 return key;
615
616fail:
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000617 Py_DECREF(so);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000618 si->si_set = NULL;
619 return NULL;
620}
621
Hye-Shik Change2956762005-08-01 05:26:41 +0000622static PyTypeObject PySetIter_Type = {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000623 PyObject_HEAD_INIT(&PyType_Type)
624 0, /* ob_size */
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000625 "setiterator", /* tp_name */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000626 sizeof(setiterobject), /* tp_basicsize */
627 0, /* tp_itemsize */
628 /* methods */
629 (destructor)setiter_dealloc, /* tp_dealloc */
630 0, /* tp_print */
631 0, /* tp_getattr */
632 0, /* tp_setattr */
633 0, /* tp_compare */
634 0, /* tp_repr */
635 0, /* tp_as_number */
636 &setiter_as_sequence, /* tp_as_sequence */
637 0, /* tp_as_mapping */
638 0, /* tp_hash */
639 0, /* tp_call */
640 0, /* tp_str */
641 PyObject_GenericGetAttr, /* tp_getattro */
642 0, /* tp_setattro */
643 0, /* tp_as_buffer */
644 Py_TPFLAGS_DEFAULT, /* tp_flags */
645 0, /* tp_doc */
646 0, /* tp_traverse */
647 0, /* tp_clear */
648 0, /* tp_richcompare */
649 0, /* tp_weaklistoffset */
650 PyObject_SelfIter, /* tp_iter */
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000651 (iternextfunc)setiter_iternext, /* tp_iternext */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000652};
653
Raymond Hettingerd7946662005-08-01 21:39:29 +0000654static int
655set_len(PyObject *so)
656{
657 return ((PySetObject *)so)->used;
658}
659
660static int
661set_update_internal(PySetObject *so, PyObject *other)
Raymond Hettingera690a992003-11-16 16:17:49 +0000662{
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000663 PyObject *key, *it;
Raymond Hettingera690a992003-11-16 16:17:49 +0000664
Raymond Hettingerd7946662005-08-01 21:39:29 +0000665 if (PyAnySet_Check(other))
666 return set_merge_internal(so, other);
Raymond Hettingera690a992003-11-16 16:17:49 +0000667
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000668 if (PyDict_Check(other)) {
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000669 PyObject *key, *value;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000670 int pos = 0;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000671 while (PyDict_Next(other, &pos, &key, &value)) {
672 if (set_add_internal(so, key) == -1)
Raymond Hettingerd7946662005-08-01 21:39:29 +0000673 return -1;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000674 }
Raymond Hettingerd7946662005-08-01 21:39:29 +0000675 return 0;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000676 }
677
Raymond Hettingera38123e2003-11-24 22:18:49 +0000678 it = PyObject_GetIter(other);
679 if (it == NULL)
Raymond Hettingerd7946662005-08-01 21:39:29 +0000680 return -1;
Raymond Hettingera690a992003-11-16 16:17:49 +0000681
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000682 while ((key = PyIter_Next(it)) != NULL) {
683 if (set_add_internal(so, key) == -1) {
Raymond Hettingera38123e2003-11-24 22:18:49 +0000684 Py_DECREF(it);
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000685 Py_DECREF(key);
Raymond Hettingerd7946662005-08-01 21:39:29 +0000686 return -1;
Raymond Hettingera690a992003-11-16 16:17:49 +0000687 }
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000688 Py_DECREF(key);
Raymond Hettingera690a992003-11-16 16:17:49 +0000689 }
Raymond Hettingera38123e2003-11-24 22:18:49 +0000690 Py_DECREF(it);
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +0000691 if (PyErr_Occurred())
Raymond Hettingerd7946662005-08-01 21:39:29 +0000692 return -1;
693 return 0;
694}
695
696static PyObject *
697set_update(PySetObject *so, PyObject *other)
698{
699 if (set_update_internal(so, other) == -1)
Raymond Hettingera38123e2003-11-24 22:18:49 +0000700 return NULL;
701 Py_RETURN_NONE;
702}
703
704PyDoc_STRVAR(update_doc,
705"Update a set with the union of itself and another.");
706
707static PyObject *
708make_new_set(PyTypeObject *type, PyObject *iterable)
709{
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000710 register PySetObject *so = NULL;
Raymond Hettingera38123e2003-11-24 22:18:49 +0000711
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000712 if (dummy == NULL) { /* Auto-initialize dummy */
713 dummy = PyString_FromString("<dummy key>");
714 if (dummy == NULL)
715 return NULL;
716 }
Raymond Hettingera690a992003-11-16 16:17:49 +0000717
718 /* create PySetObject structure */
719 so = (PySetObject *)type->tp_alloc(type, 0);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000720 if (so == NULL)
Raymond Hettingera38123e2003-11-24 22:18:49 +0000721 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000722
723 EMPTY_TO_MINSIZE(so);
724 so->lookup = set_lookkey_string;
Raymond Hettingera690a992003-11-16 16:17:49 +0000725 so->hash = -1;
Raymond Hettinger691d8052004-05-30 07:26:47 +0000726 so->weakreflist = NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +0000727
Raymond Hettingera38123e2003-11-24 22:18:49 +0000728 if (iterable != NULL) {
Raymond Hettingerd7946662005-08-01 21:39:29 +0000729 if (set_update_internal(so, iterable) == -1) {
Raymond Hettingera38123e2003-11-24 22:18:49 +0000730 Py_DECREF(so);
731 return NULL;
732 }
Raymond Hettingera38123e2003-11-24 22:18:49 +0000733 }
734
Raymond Hettingera690a992003-11-16 16:17:49 +0000735 return (PyObject *)so;
736}
737
Raymond Hettingerd7946662005-08-01 21:39:29 +0000738/* The empty frozenset is a singleton */
739static PyObject *emptyfrozenset = NULL;
740
Raymond Hettingera690a992003-11-16 16:17:49 +0000741static PyObject *
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000742frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
Raymond Hettingera690a992003-11-16 16:17:49 +0000743{
Raymond Hettingerd7946662005-08-01 21:39:29 +0000744 PyObject *iterable = NULL, *result;
Raymond Hettingera690a992003-11-16 16:17:49 +0000745
746 if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
747 return NULL;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000748
749 if (type != &PyFrozenSet_Type)
750 return make_new_set(type, iterable);
751
752 if (iterable != NULL) {
753 /* frozenset(f) is idempotent */
754 if (PyFrozenSet_CheckExact(iterable)) {
755 Py_INCREF(iterable);
756 return iterable;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000757 }
Raymond Hettingerd7946662005-08-01 21:39:29 +0000758 result = make_new_set(type, iterable);
759 if (result == NULL || set_len(result))
760 return result;
761 Py_DECREF(result);
Raymond Hettinger49ba4c32003-11-23 02:49:05 +0000762 }
Raymond Hettingerd7946662005-08-01 21:39:29 +0000763 /* The empty frozenset is a singleton */
764 if (emptyfrozenset == NULL)
765 emptyfrozenset = make_new_set(type, NULL);
766 Py_XINCREF(emptyfrozenset);
767 return emptyfrozenset;
768}
769
770void
771PySet_Fini(void)
772{
Raymond Hettingera9d99362005-08-05 00:01:15 +0000773 Py_XDECREF(dummy);
Raymond Hettingerd7946662005-08-01 21:39:29 +0000774 Py_XDECREF(emptyfrozenset);
Raymond Hettingera690a992003-11-16 16:17:49 +0000775}
776
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000777static PyObject *
778set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
779{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000780 return make_new_set(type, NULL);
781}
782
Raymond Hettingera690a992003-11-16 16:17:49 +0000783static void
784set_dealloc(PySetObject *so)
785{
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000786 register setentry *entry;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000787 int fill = so->fill;
788
Raymond Hettingerbb999b52005-06-18 21:00:26 +0000789 PyObject_GC_UnTrack(so);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000790 Py_TRASHCAN_SAFE_BEGIN(so)
Raymond Hettinger691d8052004-05-30 07:26:47 +0000791 if (so->weakreflist != NULL)
792 PyObject_ClearWeakRefs((PyObject *) so);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000793
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000794 for (entry = so->table; fill > 0; entry++) {
795 if (entry->key) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000796 --fill;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000797 Py_DECREF(entry->key);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000798 }
799 }
800 if (so->table != so->smalltable)
801 PyMem_DEL(so->table);
802
Raymond Hettingera690a992003-11-16 16:17:49 +0000803 so->ob_type->tp_free(so);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000804 Py_TRASHCAN_SAFE_END(so)
Raymond Hettingera690a992003-11-16 16:17:49 +0000805}
806
Raymond Hettingerbb999b52005-06-18 21:00:26 +0000807static int
808set_traverse(PySetObject *so, visitproc visit, void *arg)
809{
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000810 int pos = 0;
811 PyObject *key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000812
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000813 while (set_next_internal(so, &pos, &key))
814 Py_VISIT(key);
Raymond Hettingerbb999b52005-06-18 21:00:26 +0000815 return 0;
816}
817
Raymond Hettinger934d63e2005-07-31 01:33:10 +0000818/* set_swap_bodies() switches the contents of any two sets by moving their
819 internal data pointers and, if needed, copying the internal smalltables.
820 Semantically equivalent to:
821
822 t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
823
824 The function always succeeds and it leaves both objects in a stable state.
825 Useful for creating temporary frozensets from sets for membership testing
826 in __contains__(), discard(), and remove(). Also useful for operations
827 that update in-place (by allowing an intermediate result to be swapped
Raymond Hettinger9dcb17c2005-07-31 13:09:28 +0000828 into one of the original inputs).
Raymond Hettinger934d63e2005-07-31 01:33:10 +0000829*/
830
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000831static void
832set_swap_bodies(PySetObject *a, PySetObject *b)
Raymond Hettingera690a992003-11-16 16:17:49 +0000833{
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000834 int t;
835 setentry *u;
836 setentry *(*f)(PySetObject *so, PyObject *key, long hash);
837 setentry tab[PySet_MINSIZE];
838 long h;
839
840 t = a->fill; a->fill = b->fill; b->fill = t;
841 t = a->used; a->used = b->used; b->used = t;
842 t = a->mask; a->mask = b->mask; b->mask = t;
843
844 u = a->table;
845 if (a->table == a->smalltable)
846 u = b->smalltable;
847 a->table = b->table;
848 if (b->table == b->smalltable)
849 a->table = a->smalltable;
850 b->table = u;
851
852 f = a->lookup; a->lookup = b->lookup; b->lookup = f;
853
854 if (a->table == a->smalltable || b->table == b->smalltable) {
855 memcpy(tab, a->smalltable, sizeof(tab));
856 memcpy(a->smalltable, b->smalltable, sizeof(tab));
857 memcpy(b->smalltable, tab, sizeof(tab));
858 }
859
Raymond Hettingera580c472005-08-05 17:19:54 +0000860 if (PyType_IsSubtype(a->ob_type, &PyFrozenSet_Type) &&
861 PyType_IsSubtype(b->ob_type, &PyFrozenSet_Type)) {
862 h = a->hash; a->hash = b->hash; b->hash = h;
863 } else {
864 a->hash = -1;
865 b->hash = -1;
866 }
Raymond Hettingera690a992003-11-16 16:17:49 +0000867}
868
869static int
870set_contains(PySetObject *so, PyObject *key)
871{
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000872 PyObject *tmpkey;
Raymond Hettinger19c2d772003-11-21 18:36:54 +0000873 int result;
874
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000875 result = set_contains_internal(so, key);
Raymond Hettingera38123e2003-11-24 22:18:49 +0000876 if (result == -1 && PyAnySet_Check(key)) {
Raymond Hettinger19c2d772003-11-21 18:36:54 +0000877 PyErr_Clear();
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000878 tmpkey = make_new_set(&PyFrozenSet_Type, NULL);
879 if (tmpkey == NULL)
Raymond Hettinger19c2d772003-11-21 18:36:54 +0000880 return -1;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000881 set_swap_bodies((PySetObject *)tmpkey, (PySetObject *)key);
882 result = set_contains_internal(so, tmpkey);
883 set_swap_bodies((PySetObject *)tmpkey, (PySetObject *)key);
884 Py_DECREF(tmpkey);
Raymond Hettinger19c2d772003-11-21 18:36:54 +0000885 }
886 return result;
Raymond Hettingera690a992003-11-16 16:17:49 +0000887}
888
889static PyObject *
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +0000890set_direct_contains(PySetObject *so, PyObject *key)
891{
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +0000892 long result;
893
Raymond Hettinger438e02d2003-12-13 19:38:47 +0000894 result = set_contains(so, key);
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +0000895 if (result == -1)
896 return NULL;
897 return PyBool_FromLong(result);
898}
899
900PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
901
902static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +0000903set_copy(PySetObject *so)
904{
Raymond Hettingera38123e2003-11-24 22:18:49 +0000905 return make_new_set(so->ob_type, (PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +0000906}
907
Raymond Hettinger49ba4c32003-11-23 02:49:05 +0000908static PyObject *
909frozenset_copy(PySetObject *so)
910{
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +0000911 if (PyFrozenSet_CheckExact(so)) {
Raymond Hettinger49ba4c32003-11-23 02:49:05 +0000912 Py_INCREF(so);
913 return (PyObject *)so;
914 }
915 return set_copy(so);
916}
917
Raymond Hettingera690a992003-11-16 16:17:49 +0000918PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
919
920static PyObject *
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +0000921set_union(PySetObject *so, PyObject *other)
922{
923 PySetObject *result;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +0000924
925 result = (PySetObject *)set_copy(so);
926 if (result == NULL)
927 return NULL;
Raymond Hettingerd7946662005-08-01 21:39:29 +0000928 if (set_update_internal(result, other) == -1) {
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +0000929 Py_DECREF(result);
930 return NULL;
931 }
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +0000932 return (PyObject *)result;
933}
934
935PyDoc_STRVAR(union_doc,
936 "Return the union of two sets as a new set.\n\
937\n\
938(i.e. all elements that are in either set.)");
939
940static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +0000941set_or(PySetObject *so, PyObject *other)
942{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000943 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000944 Py_INCREF(Py_NotImplemented);
945 return Py_NotImplemented;
946 }
947 return set_union(so, other);
948}
949
950static PyObject *
951set_ior(PySetObject *so, PyObject *other)
952{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000953 if (!PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000954 Py_INCREF(Py_NotImplemented);
955 return Py_NotImplemented;
956 }
Raymond Hettingerd7946662005-08-01 21:39:29 +0000957 if (set_update_internal(so, other) == -1)
Raymond Hettingera690a992003-11-16 16:17:49 +0000958 return NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +0000959 Py_INCREF(so);
960 return (PyObject *)so;
961}
962
963static PyObject *
964set_intersection(PySetObject *so, PyObject *other)
965{
966 PySetObject *result;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000967 PyObject *key, *it, *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +0000968
969 result = (PySetObject *)make_new_set(so->ob_type, NULL);
970 if (result == NULL)
971 return NULL;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +0000972
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000973 if (PyAnySet_Check(other) && set_len(other) > set_len((PyObject *)so)) {
974 tmp = (PyObject *)so;
975 so = (PySetObject *)other;
Raymond Hettingera3b11e72003-12-31 14:08:58 +0000976 other = tmp;
977 }
978
Raymond Hettinger9f1a6792005-07-31 01:16:36 +0000979 if (PyAnySet_Check(other)) {
Raymond Hettingera3b11e72003-12-31 14:08:58 +0000980 int pos = 0;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000981 while (set_next_internal((PySetObject *)other, &pos, &key)) {
982 if (set_contains_internal(so, key)) {
983 if (set_add_internal(result, key) == -1) {
Raymond Hettingera3b11e72003-12-31 14:08:58 +0000984 Py_DECREF(result);
985 return NULL;
986 }
987 }
988 }
989 return (PyObject *)result;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +0000990 }
991
Raymond Hettingera690a992003-11-16 16:17:49 +0000992 it = PyObject_GetIter(other);
993 if (it == NULL) {
994 Py_DECREF(result);
995 return NULL;
996 }
997
Raymond Hettinger06d8cf82005-07-31 15:36:06 +0000998 while ((key = PyIter_Next(it)) != NULL) {
999 if (set_contains_internal(so, key)) {
1000 if (set_add_internal(result, key) == -1) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001001 Py_DECREF(it);
1002 Py_DECREF(result);
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001003 Py_DECREF(key);
Raymond Hettingera690a992003-11-16 16:17:49 +00001004 return NULL;
1005 }
1006 }
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001007 Py_DECREF(key);
Raymond Hettingera690a992003-11-16 16:17:49 +00001008 }
1009 Py_DECREF(it);
1010 if (PyErr_Occurred()) {
1011 Py_DECREF(result);
1012 return NULL;
1013 }
1014 return (PyObject *)result;
1015}
1016
1017PyDoc_STRVAR(intersection_doc,
1018"Return the intersection of two sets as a new set.\n\
1019\n\
1020(i.e. all elements that are in both sets.)");
1021
1022static PyObject *
1023set_intersection_update(PySetObject *so, PyObject *other)
1024{
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001025 PyObject *tmp;
Raymond Hettingera690a992003-11-16 16:17:49 +00001026
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001027 tmp = set_intersection(so, other);
1028 if (tmp == NULL)
Raymond Hettingera690a992003-11-16 16:17:49 +00001029 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001030 set_swap_bodies(so, (PySetObject *)tmp);
Raymond Hettingera690a992003-11-16 16:17:49 +00001031 Py_DECREF(tmp);
1032 Py_RETURN_NONE;
1033}
1034
1035PyDoc_STRVAR(intersection_update_doc,
1036"Update a set with the intersection of itself and another.");
1037
1038static PyObject *
1039set_and(PySetObject *so, PyObject *other)
1040{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001041 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001042 Py_INCREF(Py_NotImplemented);
1043 return Py_NotImplemented;
1044 }
1045 return set_intersection(so, other);
1046}
1047
1048static PyObject *
1049set_iand(PySetObject *so, PyObject *other)
1050{
1051 PyObject *result;
1052
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001053 if (!PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001054 Py_INCREF(Py_NotImplemented);
1055 return Py_NotImplemented;
1056 }
1057 result = set_intersection_update(so, other);
1058 if (result == NULL)
1059 return NULL;
1060 Py_DECREF(result);
1061 Py_INCREF(so);
1062 return (PyObject *)so;
1063}
1064
1065static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001066set_difference_update(PySetObject *so, PyObject *other)
1067{
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001068 PyObject *key, *it;
Raymond Hettingera690a992003-11-16 16:17:49 +00001069
1070 it = PyObject_GetIter(other);
1071 if (it == NULL)
1072 return NULL;
1073
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001074 while ((key = PyIter_Next(it)) != NULL) {
1075 if (set_discard_internal(so, key) == -1) {
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001076 Py_DECREF(it);
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001077 Py_DECREF(key);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001078 return NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001079 }
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001080 Py_DECREF(key);
Raymond Hettingera690a992003-11-16 16:17:49 +00001081 }
1082 Py_DECREF(it);
1083 if (PyErr_Occurred())
1084 return NULL;
1085 Py_RETURN_NONE;
1086}
1087
1088PyDoc_STRVAR(difference_update_doc,
1089"Remove all elements of another set from this set.");
1090
1091static PyObject *
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001092set_difference(PySetObject *so, PyObject *other)
1093{
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001094 PyObject *tmp, *key, *result;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001095 int pos = 0;
1096
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001097 if (!PyAnySet_Check(other) && !PyDict_Check(other)) {
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001098 result = set_copy(so);
1099 if (result == NULL)
1100 return result;
1101 tmp = set_difference_update((PySetObject *)result, other);
1102 if (tmp != NULL) {
1103 Py_DECREF(tmp);
1104 return result;
1105 }
1106 Py_DECREF(result);
1107 return NULL;
1108 }
1109
1110 result = make_new_set(so->ob_type, NULL);
1111 if (result == NULL)
1112 return NULL;
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001113
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001114 if (PyDict_Check(other)) {
1115 while (set_next_internal(so, &pos, &key)) {
1116 if (!PyDict_Contains(other, key)) {
1117 if (set_add_internal((PySetObject *)result, key) == -1)
1118 return NULL;
1119 }
1120 }
1121 return result;
1122 }
1123
1124 while (set_next_internal(so, &pos, &key)) {
1125 if (!set_contains_internal((PySetObject *)other, key)) {
1126 if (set_add_internal((PySetObject *)result, key) == -1)
Raymond Hettingerfb4e33a2003-12-15 13:23:55 +00001127 return NULL;
1128 }
1129 }
1130 return result;
1131}
1132
1133PyDoc_STRVAR(difference_doc,
1134"Return the difference of two sets as a new set.\n\
1135\n\
1136(i.e. all elements that are in this set but not the other.)");
1137static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001138set_sub(PySetObject *so, PyObject *other)
1139{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001140 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001141 Py_INCREF(Py_NotImplemented);
1142 return Py_NotImplemented;
1143 }
1144 return set_difference(so, other);
1145}
1146
1147static PyObject *
1148set_isub(PySetObject *so, PyObject *other)
1149{
1150 PyObject *result;
1151
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001152 if (!PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001153 Py_INCREF(Py_NotImplemented);
1154 return Py_NotImplemented;
1155 }
1156 result = set_difference_update(so, other);
1157 if (result == NULL)
1158 return NULL;
1159 Py_DECREF(result);
1160 Py_INCREF(so);
1161 return (PyObject *)so;
1162}
1163
1164static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001165set_symmetric_difference_update(PySetObject *so, PyObject *other)
1166{
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001167 PySetObject *otherset;
1168 PyObject *key;
Raymond Hettingerdc5ae112003-12-13 14:46:46 +00001169 int pos = 0;
Raymond Hettingera690a992003-11-16 16:17:49 +00001170
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001171 if (PyDict_Check(other)) {
1172 PyObject *value;
1173 int rv;
1174 while (PyDict_Next(other, &pos, &key, &value)) {
1175 rv = set_discard_internal(so, key);
1176 if (rv == -1)
1177 return NULL;
1178 if (rv == DISCARD_NOTFOUND) {
1179 if (set_add_internal(so, key) == -1)
1180 return NULL;
1181 }
1182 }
1183 Py_RETURN_NONE;
1184 }
1185
1186 if (PyAnySet_Check(other)) {
1187 Py_INCREF(other);
1188 otherset = (PySetObject *)other;
1189 } else {
Raymond Hettingera690a992003-11-16 16:17:49 +00001190 otherset = (PySetObject *)make_new_set(so->ob_type, other);
1191 if (otherset == NULL)
1192 return NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001193 }
1194
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001195 while (set_next_internal(otherset, &pos, &key)) {
1196 int rv = set_discard_internal(so, key);
1197 if (rv == -1) {
1198 Py_XDECREF(otherset);
1199 return NULL;
1200 }
1201 if (rv == DISCARD_NOTFOUND) {
1202 if (set_add_internal(so, key) == -1) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001203 Py_XDECREF(otherset);
Raymond Hettingera690a992003-11-16 16:17:49 +00001204 return NULL;
1205 }
1206 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001207 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001208 Py_DECREF(otherset);
Raymond Hettingera690a992003-11-16 16:17:49 +00001209 Py_RETURN_NONE;
1210}
1211
1212PyDoc_STRVAR(symmetric_difference_update_doc,
1213"Update a set with the symmetric difference of itself and another.");
1214
1215static PyObject *
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001216set_symmetric_difference(PySetObject *so, PyObject *other)
1217{
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001218 PyObject *rv;
1219 PySetObject *otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001220
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001221 otherset = (PySetObject *)make_new_set(so->ob_type, other);
1222 if (otherset == NULL)
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001223 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001224 rv = set_symmetric_difference_update(otherset, (PyObject *)so);
1225 if (rv == NULL)
1226 return NULL;
1227 Py_DECREF(rv);
1228 return (PyObject *)otherset;
Raymond Hettingerf5f41bf2003-11-24 02:57:33 +00001229}
1230
1231PyDoc_STRVAR(symmetric_difference_doc,
1232"Return the symmetric difference of two sets as a new set.\n\
1233\n\
1234(i.e. all elements that are in exactly one of the sets.)");
1235
1236static PyObject *
Raymond Hettingera690a992003-11-16 16:17:49 +00001237set_xor(PySetObject *so, PyObject *other)
1238{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001239 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001240 Py_INCREF(Py_NotImplemented);
1241 return Py_NotImplemented;
1242 }
1243 return set_symmetric_difference(so, other);
1244}
1245
1246static PyObject *
1247set_ixor(PySetObject *so, PyObject *other)
1248{
1249 PyObject *result;
1250
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001251 if (!PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001252 Py_INCREF(Py_NotImplemented);
1253 return Py_NotImplemented;
1254 }
1255 result = set_symmetric_difference_update(so, other);
1256 if (result == NULL)
1257 return NULL;
1258 Py_DECREF(result);
1259 Py_INCREF(so);
1260 return (PyObject *)so;
1261}
1262
1263static PyObject *
1264set_issubset(PySetObject *so, PyObject *other)
1265{
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001266 PyObject *tmp, *result;
1267 PyObject *key;
Raymond Hettingerdc5ae112003-12-13 14:46:46 +00001268 int pos = 0;
Raymond Hettingera690a992003-11-16 16:17:49 +00001269
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001270 if (!PyAnySet_Check(other)) {
Raymond Hettinger3fbec702003-11-21 07:56:36 +00001271 tmp = make_new_set(&PySet_Type, other);
1272 if (tmp == NULL)
1273 return NULL;
1274 result = set_issubset(so, tmp);
1275 Py_DECREF(tmp);
1276 return result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001277 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001278 if (set_len((PyObject *)so) > set_len(other))
Raymond Hettingera690a992003-11-16 16:17:49 +00001279 Py_RETURN_FALSE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001280
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001281 while (set_next_internal(so, &pos, &key)) {
1282 if (!set_contains_internal((PySetObject *)other, key))
Raymond Hettingera690a992003-11-16 16:17:49 +00001283 Py_RETURN_FALSE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001284 }
Raymond Hettingera690a992003-11-16 16:17:49 +00001285 Py_RETURN_TRUE;
1286}
1287
1288PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
1289
1290static PyObject *
1291set_issuperset(PySetObject *so, PyObject *other)
1292{
Raymond Hettinger3fbec702003-11-21 07:56:36 +00001293 PyObject *tmp, *result;
1294
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001295 if (!PyAnySet_Check(other)) {
Raymond Hettinger3fbec702003-11-21 07:56:36 +00001296 tmp = make_new_set(&PySet_Type, other);
1297 if (tmp == NULL)
1298 return NULL;
1299 result = set_issuperset(so, tmp);
1300 Py_DECREF(tmp);
1301 return result;
Raymond Hettingera690a992003-11-16 16:17:49 +00001302 }
1303 return set_issubset((PySetObject *)other, (PyObject *)so);
1304}
1305
1306PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
1307
1308static long
1309set_nohash(PyObject *self)
1310{
1311 PyErr_SetString(PyExc_TypeError, "set objects are unhashable");
1312 return -1;
1313}
1314
1315static int
1316set_nocmp(PyObject *self)
1317{
1318 PyErr_SetString(PyExc_TypeError, "cannot compare sets using cmp()");
1319 return -1;
1320}
1321
1322static long
1323frozenset_hash(PyObject *self)
1324{
Raymond Hettingera690a992003-11-16 16:17:49 +00001325 PySetObject *so = (PySetObject *)self;
Raymond Hettingera580c472005-08-05 17:19:54 +00001326 long h, hash = 1927868237L;
1327 setentry *entry;
1328 int i;
Raymond Hettinger438e02d2003-12-13 19:38:47 +00001329
Raymond Hettingera690a992003-11-16 16:17:49 +00001330 if (so->hash != -1)
1331 return so->hash;
Raymond Hettingera690a992003-11-16 16:17:49 +00001332
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001333 hash *= set_len(self) + 1;
Raymond Hettingera580c472005-08-05 17:19:54 +00001334 entry = &so->table[0];
1335 for (i=so->used ; i ; entry++, i--) {
1336 while (entry->key == NULL || entry->key==dummy)
1337 entry++;
Raymond Hettingerc9786332004-06-10 22:41:48 +00001338 /* Work to increase the bit dispersion for closely spaced hash
1339 values. The is important because some use cases have many
1340 combinations of a small number of elements with nearby
1341 hashes so that many distinct combinations collapse to only
1342 a handful of distinct hash values. */
Raymond Hettingera9d99362005-08-05 00:01:15 +00001343 h = entry->hash;
Raymond Hettingerc9786332004-06-10 22:41:48 +00001344 hash ^= (h ^ (h << 16) ^ 89869747L) * 3644798167u;
Raymond Hettingera690a992003-11-16 16:17:49 +00001345 }
Raymond Hettingerc9786332004-06-10 22:41:48 +00001346 hash = hash * 69069L + 907133923L;
Raymond Hettinger27e403e2004-06-10 21:38:41 +00001347 if (hash == -1)
1348 hash = 590923713L;
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001349 so->hash = hash;
Raymond Hettingera690a992003-11-16 16:17:49 +00001350 return hash;
1351}
1352
1353static PyObject *
1354set_richcompare(PySetObject *v, PyObject *w, int op)
1355{
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001356 PyObject *r1, *r2;
1357
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001358 if(!PyAnySet_Check(w)) {
1359 if (op == Py_EQ)
1360 Py_RETURN_FALSE;
1361 if (op == Py_NE)
1362 Py_RETURN_TRUE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001363 PyErr_SetString(PyExc_TypeError, "can only compare to a set");
1364 return NULL;
1365 }
1366 switch (op) {
1367 case Py_EQ:
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001368 if (set_len((PyObject *)v) != set_len(w))
Raymond Hettingera690a992003-11-16 16:17:49 +00001369 Py_RETURN_FALSE;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001370 return set_issubset(v, w);
1371 case Py_NE:
1372 if (set_len((PyObject *)v) != set_len(w))
1373 Py_RETURN_TRUE;
1374 r1 = set_issubset(v, w);
1375 assert (r1 != NULL);
1376 r2 = PyBool_FromLong(PyObject_Not(r1));
1377 Py_DECREF(r1);
1378 return r2;
1379 case Py_LE:
1380 return set_issubset(v, w);
1381 case Py_GE:
1382 return set_issuperset(v, w);
1383 case Py_LT:
1384 if (set_len((PyObject *)v) >= set_len(w))
1385 Py_RETURN_FALSE;
1386 return set_issubset(v, w);
1387 case Py_GT:
1388 if (set_len((PyObject *)v) <= set_len(w))
1389 Py_RETURN_FALSE;
1390 return set_issuperset(v, w);
Raymond Hettingera690a992003-11-16 16:17:49 +00001391 }
1392 Py_INCREF(Py_NotImplemented);
1393 return Py_NotImplemented;
1394}
1395
1396static PyObject *
1397set_repr(PySetObject *so)
1398{
1399 PyObject *keys, *result, *listrepr;
1400
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001401 keys = PySequence_List((PyObject *)so);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001402 if (keys == NULL)
1403 return NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001404 listrepr = PyObject_Repr(keys);
1405 Py_DECREF(keys);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001406 if (listrepr == NULL)
1407 return NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001408
1409 result = PyString_FromFormat("%s(%s)", so->ob_type->tp_name,
1410 PyString_AS_STRING(listrepr));
1411 Py_DECREF(listrepr);
1412 return result;
1413}
1414
1415static int
1416set_tp_print(PySetObject *so, FILE *fp, int flags)
1417{
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001418 PyObject *key;
Raymond Hettingera3b11e72003-12-31 14:08:58 +00001419 int pos=0;
1420 char *emit = ""; /* No separator emitted on first pass */
1421 char *separator = ", ";
Raymond Hettingera690a992003-11-16 16:17:49 +00001422
Raymond Hettingera690a992003-11-16 16:17:49 +00001423 fprintf(fp, "%s([", so->ob_type->tp_name);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001424 while (set_next_internal(so, &pos, &key)) {
Raymond Hettingera3b11e72003-12-31 14:08:58 +00001425 fputs(emit, fp);
1426 emit = separator;
Raymond Hettingerdc5ae112003-12-13 14:46:46 +00001427 if (PyObject_Print(key, fp, 0) != 0)
Raymond Hettingera690a992003-11-16 16:17:49 +00001428 return -1;
Raymond Hettingera690a992003-11-16 16:17:49 +00001429 }
Raymond Hettingera3b11e72003-12-31 14:08:58 +00001430 fputs("])", fp);
Raymond Hettingera690a992003-11-16 16:17:49 +00001431 return 0;
1432}
1433
1434static PyObject *
1435set_clear(PySetObject *so)
1436{
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001437 set_clear_internal(so);
Raymond Hettinger438e02d2003-12-13 19:38:47 +00001438 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001439}
1440
1441PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
1442
Raymond Hettingera690a992003-11-16 16:17:49 +00001443static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001444set_add(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001445{
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001446 if (set_add_internal(so, key) == -1)
Raymond Hettingera690a992003-11-16 16:17:49 +00001447 return NULL;
Raymond Hettinger438e02d2003-12-13 19:38:47 +00001448 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001449}
1450
1451PyDoc_STRVAR(add_doc,
1452"Add an element to a set.\n\
1453\n\
1454This has no effect if the element is already present.");
1455
1456static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001457set_remove(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001458{
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001459 PyObject *tmpkey, *result;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001460 int rv;
Raymond Hettingerbfd334a2003-11-22 03:55:23 +00001461
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001462 if (PyType_IsSubtype(key->ob_type, &PySet_Type)) {
1463 tmpkey = make_new_set(&PyFrozenSet_Type, NULL);
1464 if (tmpkey == NULL)
Raymond Hettingerbfd334a2003-11-22 03:55:23 +00001465 return NULL;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001466 set_swap_bodies((PySetObject *)key, (PySetObject *)tmpkey);
1467 result = set_remove(so, tmpkey);
1468 set_swap_bodies((PySetObject *)key, (PySetObject *)tmpkey);
1469 Py_DECREF(tmpkey);
Raymond Hettinger0deab622003-12-13 18:53:18 +00001470 return result;
Raymond Hettingerbfd334a2003-11-22 03:55:23 +00001471 }
Raymond Hettinger0deab622003-12-13 18:53:18 +00001472
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001473 rv = set_discard_internal(so, key);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001474 if (rv == -1)
Raymond Hettinger0deab622003-12-13 18:53:18 +00001475 return NULL;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001476 else if (rv == DISCARD_NOTFOUND) {
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001477 PyErr_SetObject(PyExc_KeyError, key);
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001478 return NULL;
1479 }
Raymond Hettinger438e02d2003-12-13 19:38:47 +00001480 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001481}
1482
1483PyDoc_STRVAR(remove_doc,
1484"Remove an element from a set; it must be a member.\n\
1485\n\
1486If the element is not a member, raise a KeyError.");
1487
1488static PyObject *
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001489set_discard(PySetObject *so, PyObject *key)
Raymond Hettingera690a992003-11-16 16:17:49 +00001490{
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001491 PyObject *tmpkey, *result;
Raymond Hettinger0deab622003-12-13 18:53:18 +00001492
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001493 if (PyType_IsSubtype(key->ob_type, &PySet_Type)) {
1494 tmpkey = make_new_set(&PyFrozenSet_Type, NULL);
1495 if (tmpkey == NULL)
Raymond Hettinger0deab622003-12-13 18:53:18 +00001496 return NULL;
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001497 set_swap_bodies((PySetObject *)key, (PySetObject *)tmpkey);
1498 result = set_discard(so, tmpkey);
1499 set_swap_bodies((PySetObject *)key, (PySetObject *)tmpkey);
1500 Py_DECREF(tmpkey);
Raymond Hettinger0deab622003-12-13 18:53:18 +00001501 return result;
1502 }
Raymond Hettingerbfd334a2003-11-22 03:55:23 +00001503
Raymond Hettinger06d8cf82005-07-31 15:36:06 +00001504 if (set_discard_internal(so, key) == -1)
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001505 return NULL;
Raymond Hettinger438e02d2003-12-13 19:38:47 +00001506 Py_RETURN_NONE;
Raymond Hettingera690a992003-11-16 16:17:49 +00001507}
1508
1509PyDoc_STRVAR(discard_doc,
1510"Remove an element from a set if it is a member.\n\
1511\n\
1512If the element is not a member, do nothing.");
1513
1514static PyObject *
1515set_pop(PySetObject *so)
1516{
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001517 PyObject *key;
Raymond Hettinger67962ab2005-08-02 03:45:16 +00001518 register setentry *entry;
1519 register int i = 0;
Raymond Hettingera690a992003-11-16 16:17:49 +00001520
Raymond Hettinger67962ab2005-08-02 03:45:16 +00001521 assert (PyAnySet_Check(so));
1522 if (so->used == 0) {
Raymond Hettingera690a992003-11-16 16:17:49 +00001523 PyErr_SetString(PyExc_KeyError, "pop from an empty set");
1524 return NULL;
1525 }
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001526
Raymond Hettinger67962ab2005-08-02 03:45:16 +00001527 /* Set entry to "the first" unused or dummy set entry. We abuse
1528 * the hash field of slot 0 to hold a search finger:
1529 * If slot 0 has a value, use slot 0.
1530 * Else slot 0 is being used to hold a search finger,
1531 * and we use its hash value as the first index to look.
1532 */
1533 entry = &so->table[0];
1534 if (entry->key == NULL || entry->key == dummy) {
1535 i = (int)entry->hash;
1536 /* The hash field may be a real hash value, or it may be a
1537 * legit search finger, or it may be a once-legit search
1538 * finger that's out of bounds now because it wrapped around
1539 * or the table shrunk -- simply make sure it's in bounds now.
1540 */
1541 if (i > so->mask || i < 1)
1542 i = 1; /* skip slot 0 */
1543 while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
1544 i++;
1545 if (i > so->mask)
1546 i = 1;
1547 }
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001548 }
Raymond Hettinger67962ab2005-08-02 03:45:16 +00001549 key = entry->key;
1550 Py_INCREF(dummy);
1551 entry->key = dummy;
1552 so->used--;
1553 so->table[0].hash = i + 1; /* next place to start */
Raymond Hettingera690a992003-11-16 16:17:49 +00001554 return key;
1555}
1556
1557PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.");
1558
1559static PyObject *
1560set_reduce(PySetObject *so)
1561{
Raymond Hettinger15056a52004-11-09 07:25:31 +00001562 PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +00001563
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001564 keys = PySequence_List((PyObject *)so);
Raymond Hettingera690a992003-11-16 16:17:49 +00001565 if (keys == NULL)
1566 goto done;
1567 args = PyTuple_Pack(1, keys);
1568 if (args == NULL)
1569 goto done;
Raymond Hettinger15056a52004-11-09 07:25:31 +00001570 dict = PyObject_GetAttrString((PyObject *)so, "__dict__");
1571 if (dict == NULL) {
1572 PyErr_Clear();
1573 dict = Py_None;
1574 Py_INCREF(dict);
1575 }
1576 result = PyTuple_Pack(3, so->ob_type, args, dict);
Raymond Hettingera690a992003-11-16 16:17:49 +00001577done:
1578 Py_XDECREF(args);
1579 Py_XDECREF(keys);
Raymond Hettinger15056a52004-11-09 07:25:31 +00001580 Py_XDECREF(dict);
Raymond Hettingera690a992003-11-16 16:17:49 +00001581 return result;
1582}
1583
1584PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1585
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001586static int
1587set_init(PySetObject *self, PyObject *args, PyObject *kwds)
1588{
1589 PyObject *iterable = NULL;
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001590
1591 if (!PyAnySet_Check(self))
1592 return -1;
1593 if (!PyArg_UnpackTuple(args, self->ob_type->tp_name, 0, 1, &iterable))
1594 return -1;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001595 set_clear_internal(self);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001596 self->hash = -1;
1597 if (iterable == NULL)
1598 return 0;
Raymond Hettingerd7946662005-08-01 21:39:29 +00001599 return set_update_internal(self, iterable);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001600}
1601
Raymond Hettingera690a992003-11-16 16:17:49 +00001602static PySequenceMethods set_as_sequence = {
1603 (inquiry)set_len, /* sq_length */
1604 0, /* sq_concat */
1605 0, /* sq_repeat */
1606 0, /* sq_item */
1607 0, /* sq_slice */
1608 0, /* sq_ass_item */
1609 0, /* sq_ass_slice */
1610 (objobjproc)set_contains, /* sq_contains */
1611};
1612
1613/* set object ********************************************************/
1614
1615static PyMethodDef set_methods[] = {
1616 {"add", (PyCFunction)set_add, METH_O,
1617 add_doc},
1618 {"clear", (PyCFunction)set_clear, METH_NOARGS,
1619 clear_doc},
Raymond Hettinger0deab622003-12-13 18:53:18 +00001620 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001621 contains_doc},
Raymond Hettingera690a992003-11-16 16:17:49 +00001622 {"copy", (PyCFunction)set_copy, METH_NOARGS,
1623 copy_doc},
Raymond Hettingera690a992003-11-16 16:17:49 +00001624 {"discard", (PyCFunction)set_discard, METH_O,
1625 discard_doc},
1626 {"difference", (PyCFunction)set_difference, METH_O,
1627 difference_doc},
1628 {"difference_update", (PyCFunction)set_difference_update, METH_O,
1629 difference_update_doc},
1630 {"intersection",(PyCFunction)set_intersection, METH_O,
1631 intersection_doc},
1632 {"intersection_update",(PyCFunction)set_intersection_update, METH_O,
1633 intersection_update_doc},
1634 {"issubset", (PyCFunction)set_issubset, METH_O,
1635 issubset_doc},
1636 {"issuperset", (PyCFunction)set_issuperset, METH_O,
1637 issuperset_doc},
1638 {"pop", (PyCFunction)set_pop, METH_NOARGS,
1639 pop_doc},
1640 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
1641 reduce_doc},
1642 {"remove", (PyCFunction)set_remove, METH_O,
1643 remove_doc},
1644 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
1645 symmetric_difference_doc},
1646 {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O,
1647 symmetric_difference_update_doc},
1648 {"union", (PyCFunction)set_union, METH_O,
1649 union_doc},
Raymond Hettingera38123e2003-11-24 22:18:49 +00001650 {"update", (PyCFunction)set_update, METH_O,
1651 update_doc},
Raymond Hettingera690a992003-11-16 16:17:49 +00001652 {NULL, NULL} /* sentinel */
1653};
1654
1655static PyNumberMethods set_as_number = {
1656 0, /*nb_add*/
1657 (binaryfunc)set_sub, /*nb_subtract*/
1658 0, /*nb_multiply*/
1659 0, /*nb_divide*/
1660 0, /*nb_remainder*/
1661 0, /*nb_divmod*/
1662 0, /*nb_power*/
1663 0, /*nb_negative*/
1664 0, /*nb_positive*/
1665 0, /*nb_absolute*/
1666 0, /*nb_nonzero*/
1667 0, /*nb_invert*/
1668 0, /*nb_lshift*/
1669 0, /*nb_rshift*/
1670 (binaryfunc)set_and, /*nb_and*/
1671 (binaryfunc)set_xor, /*nb_xor*/
1672 (binaryfunc)set_or, /*nb_or*/
1673 0, /*nb_coerce*/
1674 0, /*nb_int*/
1675 0, /*nb_long*/
1676 0, /*nb_float*/
1677 0, /*nb_oct*/
1678 0, /*nb_hex*/
1679 0, /*nb_inplace_add*/
1680 (binaryfunc)set_isub, /*nb_inplace_subtract*/
1681 0, /*nb_inplace_multiply*/
1682 0, /*nb_inplace_divide*/
1683 0, /*nb_inplace_remainder*/
1684 0, /*nb_inplace_power*/
1685 0, /*nb_inplace_lshift*/
1686 0, /*nb_inplace_rshift*/
1687 (binaryfunc)set_iand, /*nb_inplace_and*/
1688 (binaryfunc)set_ixor, /*nb_inplace_xor*/
1689 (binaryfunc)set_ior, /*nb_inplace_or*/
1690};
1691
1692PyDoc_STRVAR(set_doc,
1693"set(iterable) --> set object\n\
1694\n\
1695Build an unordered collection.");
1696
1697PyTypeObject PySet_Type = {
1698 PyObject_HEAD_INIT(&PyType_Type)
1699 0, /* ob_size */
1700 "set", /* tp_name */
1701 sizeof(PySetObject), /* tp_basicsize */
1702 0, /* tp_itemsize */
1703 /* methods */
1704 (destructor)set_dealloc, /* tp_dealloc */
1705 (printfunc)set_tp_print, /* tp_print */
1706 0, /* tp_getattr */
1707 0, /* tp_setattr */
1708 (cmpfunc)set_nocmp, /* tp_compare */
1709 (reprfunc)set_repr, /* tp_repr */
1710 &set_as_number, /* tp_as_number */
1711 &set_as_sequence, /* tp_as_sequence */
1712 0, /* tp_as_mapping */
1713 set_nohash, /* tp_hash */
1714 0, /* tp_call */
1715 0, /* tp_str */
1716 PyObject_GenericGetAttr, /* tp_getattro */
1717 0, /* tp_setattro */
1718 0, /* tp_as_buffer */
Raymond Hettingerbb999b52005-06-18 21:00:26 +00001719 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_CHECKTYPES |
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001720 Py_TPFLAGS_BASETYPE, /* tp_flags */
Raymond Hettingera690a992003-11-16 16:17:49 +00001721 set_doc, /* tp_doc */
Raymond Hettingerbb999b52005-06-18 21:00:26 +00001722 (traverseproc)set_traverse, /* tp_traverse */
Raymond Hettingerfe889f32005-08-06 05:43:39 +00001723 (inquiry)set_clear_internal, /* tp_clear */
Raymond Hettingera690a992003-11-16 16:17:49 +00001724 (richcmpfunc)set_richcompare, /* tp_richcompare */
Raymond Hettinger691d8052004-05-30 07:26:47 +00001725 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001726 (getiterfunc)set_iter, /* tp_iter */
Raymond Hettingera690a992003-11-16 16:17:49 +00001727 0, /* tp_iternext */
1728 set_methods, /* tp_methods */
1729 0, /* tp_members */
1730 0, /* tp_getset */
1731 0, /* tp_base */
1732 0, /* tp_dict */
1733 0, /* tp_descr_get */
1734 0, /* tp_descr_set */
1735 0, /* tp_dictoffset */
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001736 (initproc)set_init, /* tp_init */
Raymond Hettingera690a992003-11-16 16:17:49 +00001737 PyType_GenericAlloc, /* tp_alloc */
1738 set_new, /* tp_new */
Raymond Hettingerbb999b52005-06-18 21:00:26 +00001739 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00001740};
1741
1742/* frozenset object ********************************************************/
1743
1744
1745static PyMethodDef frozenset_methods[] = {
Raymond Hettinger0deab622003-12-13 18:53:18 +00001746 {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001747 contains_doc},
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001748 {"copy", (PyCFunction)frozenset_copy, METH_NOARGS,
Raymond Hettingera690a992003-11-16 16:17:49 +00001749 copy_doc},
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001750 {"difference", (PyCFunction)set_difference, METH_O,
Raymond Hettingera690a992003-11-16 16:17:49 +00001751 difference_doc},
1752 {"intersection",(PyCFunction)set_intersection, METH_O,
1753 intersection_doc},
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001754 {"issubset", (PyCFunction)set_issubset, METH_O,
Raymond Hettingera690a992003-11-16 16:17:49 +00001755 issubset_doc},
Raymond Hettinger49ba4c32003-11-23 02:49:05 +00001756 {"issuperset", (PyCFunction)set_issuperset, METH_O,
Raymond Hettingera690a992003-11-16 16:17:49 +00001757 issuperset_doc},
1758 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
1759 reduce_doc},
1760 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
1761 symmetric_difference_doc},
1762 {"union", (PyCFunction)set_union, METH_O,
1763 union_doc},
1764 {NULL, NULL} /* sentinel */
1765};
1766
1767static PyNumberMethods frozenset_as_number = {
1768 0, /*nb_add*/
1769 (binaryfunc)set_sub, /*nb_subtract*/
1770 0, /*nb_multiply*/
1771 0, /*nb_divide*/
1772 0, /*nb_remainder*/
1773 0, /*nb_divmod*/
1774 0, /*nb_power*/
1775 0, /*nb_negative*/
1776 0, /*nb_positive*/
1777 0, /*nb_absolute*/
1778 0, /*nb_nonzero*/
1779 0, /*nb_invert*/
1780 0, /*nb_lshift*/
1781 0, /*nb_rshift*/
1782 (binaryfunc)set_and, /*nb_and*/
1783 (binaryfunc)set_xor, /*nb_xor*/
1784 (binaryfunc)set_or, /*nb_or*/
1785};
1786
1787PyDoc_STRVAR(frozenset_doc,
1788"frozenset(iterable) --> frozenset object\n\
1789\n\
1790Build an immutable unordered collection.");
1791
1792PyTypeObject PyFrozenSet_Type = {
1793 PyObject_HEAD_INIT(&PyType_Type)
1794 0, /* ob_size */
1795 "frozenset", /* tp_name */
1796 sizeof(PySetObject), /* tp_basicsize */
Raymond Hettingera3b11e72003-12-31 14:08:58 +00001797 0, /* tp_itemsize */
1798 /* methods */
Raymond Hettingera690a992003-11-16 16:17:49 +00001799 (destructor)set_dealloc, /* tp_dealloc */
1800 (printfunc)set_tp_print, /* tp_print */
1801 0, /* tp_getattr */
1802 0, /* tp_setattr */
1803 (cmpfunc)set_nocmp, /* tp_compare */
1804 (reprfunc)set_repr, /* tp_repr */
1805 &frozenset_as_number, /* tp_as_number */
1806 &set_as_sequence, /* tp_as_sequence */
1807 0, /* tp_as_mapping */
1808 frozenset_hash, /* tp_hash */
1809 0, /* tp_call */
1810 0, /* tp_str */
1811 PyObject_GenericGetAttr, /* tp_getattro */
1812 0, /* tp_setattro */
1813 0, /* tp_as_buffer */
Raymond Hettingerbb999b52005-06-18 21:00:26 +00001814 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_CHECKTYPES |
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00001815 Py_TPFLAGS_BASETYPE, /* tp_flags */
Raymond Hettingera690a992003-11-16 16:17:49 +00001816 frozenset_doc, /* tp_doc */
Raymond Hettingerbb999b52005-06-18 21:00:26 +00001817 (traverseproc)set_traverse, /* tp_traverse */
Raymond Hettingerfe889f32005-08-06 05:43:39 +00001818 (inquiry)set_clear_internal, /* tp_clear */
Raymond Hettingera690a992003-11-16 16:17:49 +00001819 (richcmpfunc)set_richcompare, /* tp_richcompare */
Raymond Hettinger691d8052004-05-30 07:26:47 +00001820 offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
Raymond Hettingera690a992003-11-16 16:17:49 +00001821 (getiterfunc)set_iter, /* tp_iter */
1822 0, /* tp_iternext */
1823 frozenset_methods, /* tp_methods */
1824 0, /* tp_members */
1825 0, /* tp_getset */
1826 0, /* tp_base */
1827 0, /* tp_dict */
1828 0, /* tp_descr_get */
1829 0, /* tp_descr_set */
1830 0, /* tp_dictoffset */
1831 0, /* tp_init */
1832 PyType_GenericAlloc, /* tp_alloc */
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001833 frozenset_new, /* tp_new */
Raymond Hettingerbb999b52005-06-18 21:00:26 +00001834 PyObject_GC_Del, /* tp_free */
Raymond Hettingera690a992003-11-16 16:17:49 +00001835};