Line data Source code
1 :
2 : /* set object implementation
3 : Written and maintained by Raymond D. Hettinger <python@rcn.com>
4 : Derived from Lib/sets.py and Objects/dictobject.c.
5 :
6 : Copyright (c) 2003-2008 Python Software Foundation.
7 : All rights reserved.
8 : */
9 :
10 : #include "Python.h"
11 : #include "structmember.h"
12 : #include "stringlib/eq.h"
13 :
14 : /* 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. */
17 : static void
18 0 : set_key_error(PyObject *arg)
19 : {
20 : PyObject *tup;
21 0 : tup = PyTuple_Pack(1, arg);
22 0 : if (!tup)
23 0 : return; /* caller will expect error to be set anyway */
24 0 : PyErr_SetObject(PyExc_KeyError, tup);
25 0 : Py_DECREF(tup);
26 : }
27 :
28 : /* This must be >= 1. */
29 : #define PERTURB_SHIFT 5
30 :
31 : /* Object used as dummy key to fill deleted entries */
32 : static PyObject *dummy = NULL; /* Initialized by first call to make_new_set() */
33 :
34 : #ifdef Py_REF_DEBUG
35 : PyObject *
36 : _PySet_Dummy(void)
37 : {
38 : return dummy;
39 : }
40 : #endif
41 :
42 : #define INIT_NONZERO_SET_SLOTS(so) do { \
43 : (so)->table = (so)->smalltable; \
44 : (so)->mask = PySet_MINSIZE - 1; \
45 : (so)->hash = -1; \
46 : } while(0)
47 :
48 : #define EMPTY_TO_MINSIZE(so) do { \
49 : memset((so)->smalltable, 0, sizeof((so)->smalltable)); \
50 : (so)->used = (so)->fill = 0; \
51 : INIT_NONZERO_SET_SLOTS(so); \
52 : } while(0)
53 :
54 : /* Reuse scheme to save calls to malloc, free, and memset */
55 : #ifndef PySet_MAXFREELIST
56 : #define PySet_MAXFREELIST 80
57 : #endif
58 : static PySetObject *free_list[PySet_MAXFREELIST];
59 : static int numfree = 0;
60 :
61 :
62 : /*
63 : The basic lookup function used by all operations.
64 : This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
65 : Open addressing is preferred over chaining since the link overhead for
66 : chaining would be substantial (100% with typical malloc overhead).
67 :
68 : The initial probe index is computed as hash mod the table size. Subsequent
69 : probe indices are computed as explained in Objects/dictobject.c.
70 :
71 : All arithmetic on hash should ignore overflow.
72 :
73 : Unlike the dictionary implementation, the lookkey functions can return
74 : NULL if the rich comparison returns an error.
75 : */
76 :
77 : static setentry *
78 2180 : set_lookkey(PySetObject *so, PyObject *key, register Py_hash_t hash)
79 : {
80 : register size_t i;
81 : register size_t perturb;
82 : register setentry *freeslot;
83 2180 : register size_t mask = so->mask;
84 2180 : setentry *table = so->table;
85 : register setentry *entry;
86 : register int cmp;
87 : PyObject *startkey;
88 :
89 2180 : i = (size_t)hash & mask;
90 2180 : entry = &table[i];
91 2180 : if (entry->key == NULL || entry->key == key)
92 1940 : return entry;
93 :
94 240 : if (entry->key == dummy)
95 5 : freeslot = entry;
96 : else {
97 235 : if (entry->hash == hash) {
98 0 : startkey = entry->key;
99 0 : Py_INCREF(startkey);
100 0 : cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
101 0 : Py_DECREF(startkey);
102 0 : if (cmp < 0)
103 0 : return NULL;
104 0 : if (table == so->table && entry->key == startkey) {
105 0 : if (cmp > 0)
106 0 : return entry;
107 : }
108 : else {
109 : /* The compare did major nasty stuff to the
110 : * set: start over.
111 : */
112 0 : return set_lookkey(so, key, hash);
113 : }
114 : }
115 235 : freeslot = NULL;
116 : }
117 :
118 : /* In the loop, key == dummy is by far (factor of 100s) the
119 : least likely outcome, so test for that last. */
120 381 : for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
121 381 : i = (i << 2) + i + perturb + 1;
122 381 : entry = &table[i & mask];
123 381 : if (entry->key == NULL) {
124 237 : if (freeslot != NULL)
125 5 : entry = freeslot;
126 237 : break;
127 : }
128 144 : if (entry->key == key)
129 3 : break;
130 141 : if (entry->hash == hash && entry->key != dummy) {
131 0 : startkey = entry->key;
132 0 : Py_INCREF(startkey);
133 0 : cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
134 0 : Py_DECREF(startkey);
135 0 : if (cmp < 0)
136 0 : return NULL;
137 0 : if (table == so->table && entry->key == startkey) {
138 0 : if (cmp > 0)
139 0 : break;
140 : }
141 : else {
142 : /* The compare did major nasty stuff to the
143 : * set: start over.
144 : */
145 0 : return set_lookkey(so, key, hash);
146 : }
147 : }
148 141 : else if (entry->key == dummy && freeslot == NULL)
149 0 : freeslot = entry;
150 141 : }
151 240 : return entry;
152 : }
153 :
154 : /*
155 : * Hacked up version of set_lookkey which can assume keys are always unicode;
156 : * This means we can always use unicode_eq directly and not have to check to
157 : * see if the comparison altered the table.
158 : */
159 : static setentry *
160 8724 : set_lookkey_unicode(PySetObject *so, PyObject *key, register Py_hash_t hash)
161 : {
162 : register size_t i;
163 : register size_t perturb;
164 : register setentry *freeslot;
165 8724 : register size_t mask = so->mask;
166 8724 : setentry *table = so->table;
167 : register setentry *entry;
168 :
169 : /* Make sure this function doesn't have to handle non-unicode keys,
170 : including subclasses of str; e.g., one reason to subclass
171 : strings is to override __eq__, and for speed we don't cater to
172 : that here. */
173 8724 : if (!PyUnicode_CheckExact(key)) {
174 74 : so->lookup = set_lookkey;
175 74 : return set_lookkey(so, key, hash);
176 : }
177 8650 : i = (size_t)hash & mask;
178 8650 : entry = &table[i];
179 8650 : if (entry->key == NULL || entry->key == key)
180 6817 : return entry;
181 1833 : if (entry->key == dummy)
182 0 : freeslot = entry;
183 : else {
184 1833 : if (entry->hash == hash && unicode_eq(entry->key, key))
185 43 : return entry;
186 1790 : freeslot = NULL;
187 : }
188 :
189 : /* In the loop, key == dummy is by far (factor of 100s) the
190 : least likely outcome, so test for that last. */
191 3096 : for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
192 3096 : i = (i << 2) + i + perturb + 1;
193 3096 : entry = &table[i & mask];
194 3096 : if (entry->key == NULL)
195 1783 : return freeslot == NULL ? entry : freeslot;
196 1313 : if (entry->key == key
197 1313 : || (entry->hash == hash
198 7 : && entry->key != dummy
199 7 : && unicode_eq(entry->key, key)))
200 7 : return entry;
201 1306 : if (entry->key == dummy && freeslot == NULL)
202 0 : freeslot = entry;
203 1306 : }
204 : assert(0); /* NOT REACHED */
205 : return 0;
206 : }
207 :
208 : /*
209 : Internal routine to insert a new key into the table.
210 : Used by the public insert routine.
211 : Eats a reference to key.
212 : */
213 : static int
214 2096 : set_insert_key(register PySetObject *so, PyObject *key, Py_hash_t hash)
215 : {
216 : register setentry *entry;
217 : typedef setentry *(*lookupfunc)(PySetObject *, PyObject *, Py_hash_t);
218 :
219 : assert(so->lookup != NULL);
220 2096 : entry = so->lookup(so, key, hash);
221 2096 : if (entry == NULL)
222 0 : return -1;
223 2096 : if (entry->key == NULL) {
224 : /* UNUSED */
225 2080 : so->fill++;
226 2080 : entry->key = key;
227 2080 : entry->hash = hash;
228 2080 : so->used++;
229 16 : } else if (entry->key == dummy) {
230 : /* DUMMY */
231 5 : entry->key = key;
232 5 : entry->hash = hash;
233 5 : so->used++;
234 5 : Py_DECREF(dummy);
235 : } else {
236 : /* ACTIVE */
237 11 : Py_DECREF(key);
238 : }
239 2096 : return 0;
240 : }
241 :
242 : /*
243 : Internal routine used by set_table_resize() to insert an item which is
244 : known to be absent from the set. This routine also assumes that
245 : the set contains no deleted entries. Besides the performance benefit,
246 : using set_insert_clean() in set_table_resize() is dangerous (SF bug #1456209).
247 : Note that no refcounts are changed by this routine; if needed, the caller
248 : is responsible for incref'ing `key`.
249 : */
250 : static void
251 927 : set_insert_clean(register PySetObject *so, PyObject *key, Py_hash_t hash)
252 : {
253 : register size_t i;
254 : register size_t perturb;
255 927 : register size_t mask = (size_t)so->mask;
256 927 : setentry *table = so->table;
257 : register setentry *entry;
258 :
259 927 : i = (size_t)hash & mask;
260 927 : entry = &table[i];
261 1011 : for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) {
262 84 : i = (i << 2) + i + perturb + 1;
263 84 : entry = &table[i & mask];
264 : }
265 927 : so->fill++;
266 927 : entry->key = key;
267 927 : entry->hash = hash;
268 927 : so->used++;
269 927 : }
270 :
271 : /*
272 : Restructure the table by allocating a new table and reinserting all
273 : keys again. When entries have been deleted, the new table may
274 : actually be smaller than the old one.
275 : */
276 : static int
277 54 : set_table_resize(PySetObject *so, Py_ssize_t minused)
278 : {
279 : Py_ssize_t newsize;
280 : setentry *oldtable, *newtable, *entry;
281 : Py_ssize_t i;
282 : int is_oldtable_malloced;
283 : setentry small_copy[PySet_MINSIZE];
284 :
285 : assert(minused >= 0);
286 :
287 : /* Find the smallest table size > minused. */
288 260 : for (newsize = PySet_MINSIZE;
289 152 : newsize <= minused && newsize > 0;
290 152 : newsize <<= 1)
291 : ;
292 54 : if (newsize <= 0) {
293 0 : PyErr_NoMemory();
294 0 : return -1;
295 : }
296 :
297 : /* Get space for a new table. */
298 54 : oldtable = so->table;
299 : assert(oldtable != NULL);
300 54 : is_oldtable_malloced = oldtable != so->smalltable;
301 :
302 54 : if (newsize == PySet_MINSIZE) {
303 : /* A large table is shrinking, or we can't get any smaller. */
304 0 : newtable = so->smalltable;
305 0 : if (newtable == oldtable) {
306 0 : if (so->fill == so->used) {
307 : /* No dummies, so no point doing anything. */
308 0 : return 0;
309 : }
310 : /* We're not going to resize it, but rebuild the
311 : table anyway to purge old dummy entries.
312 : Subtle: This is *necessary* if fill==size,
313 : as set_lookkey needs at least one virgin slot to
314 : terminate failing searches. If fill < size, it's
315 : merely desirable, as dummies slow searches. */
316 : assert(so->fill > so->used);
317 0 : memcpy(small_copy, oldtable, sizeof(small_copy));
318 0 : oldtable = small_copy;
319 : }
320 : }
321 : else {
322 54 : newtable = PyMem_NEW(setentry, newsize);
323 54 : if (newtable == NULL) {
324 0 : PyErr_NoMemory();
325 0 : return -1;
326 : }
327 : }
328 :
329 : /* Make the set empty, using the new table. */
330 : assert(newtable != oldtable);
331 54 : so->table = newtable;
332 54 : so->mask = newsize - 1;
333 54 : memset(newtable, 0, sizeof(setentry) * newsize);
334 54 : so->used = 0;
335 54 : i = so->fill;
336 54 : so->fill = 0;
337 :
338 : /* Copy the data over; this is refcount-neutral for active entries;
339 : dummy entries aren't copied over, of course */
340 1384 : for (entry = oldtable; i > 0; entry++) {
341 1330 : if (entry->key == NULL) {
342 : /* UNUSED */
343 : ;
344 927 : } else if (entry->key == dummy) {
345 : /* DUMMY */
346 0 : --i;
347 : assert(entry->key == dummy);
348 0 : Py_DECREF(entry->key);
349 : } else {
350 : /* ACTIVE */
351 927 : --i;
352 927 : set_insert_clean(so, entry->key, entry->hash);
353 : }
354 : }
355 :
356 54 : if (is_oldtable_malloced)
357 19 : PyMem_DEL(oldtable);
358 54 : return 0;
359 : }
360 :
361 : /* CAUTION: set_add_key/entry() must guarantee it won't resize the table */
362 :
363 : static int
364 0 : set_add_entry(register PySetObject *so, setentry *entry)
365 : {
366 : register Py_ssize_t n_used;
367 0 : PyObject *key = entry->key;
368 0 : Py_hash_t hash = entry->hash;
369 :
370 : assert(so->fill <= so->mask); /* at least one empty slot */
371 0 : n_used = so->used;
372 0 : Py_INCREF(key);
373 0 : if (set_insert_key(so, key, hash) == -1) {
374 0 : Py_DECREF(key);
375 0 : return -1;
376 : }
377 0 : if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
378 0 : return 0;
379 0 : return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
380 : }
381 :
382 : static int
383 1946 : set_add_key(register PySetObject *so, PyObject *key)
384 : {
385 : register Py_hash_t hash;
386 : register Py_ssize_t n_used;
387 :
388 3654 : if (!PyUnicode_CheckExact(key) ||
389 1708 : (hash = ((PyASCIIObject *) key)->hash) == -1) {
390 1177 : hash = PyObject_Hash(key);
391 1177 : if (hash == -1)
392 0 : return -1;
393 : }
394 : assert(so->fill <= so->mask); /* at least one empty slot */
395 1946 : n_used = so->used;
396 1946 : Py_INCREF(key);
397 1946 : if (set_insert_key(so, key, hash) == -1) {
398 0 : Py_DECREF(key);
399 0 : return -1;
400 : }
401 1946 : if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
402 1898 : return 0;
403 48 : return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
404 : }
405 :
406 : #define DISCARD_NOTFOUND 0
407 : #define DISCARD_FOUND 1
408 :
409 : static int
410 0 : set_discard_entry(PySetObject *so, setentry *oldentry)
411 : { register setentry *entry;
412 : PyObject *old_key;
413 :
414 0 : entry = (so->lookup)(so, oldentry->key, oldentry->hash);
415 0 : if (entry == NULL)
416 0 : return -1;
417 0 : if (entry->key == NULL || entry->key == dummy)
418 0 : return DISCARD_NOTFOUND;
419 0 : old_key = entry->key;
420 0 : Py_INCREF(dummy);
421 0 : entry->key = dummy;
422 0 : so->used--;
423 0 : Py_DECREF(old_key);
424 0 : return DISCARD_FOUND;
425 : }
426 :
427 : static int
428 168 : set_discard_key(PySetObject *so, PyObject *key)
429 : {
430 : register Py_hash_t hash;
431 : register setentry *entry;
432 : PyObject *old_key;
433 :
434 : assert (PyAnySet_Check(so));
435 :
436 314 : if (!PyUnicode_CheckExact(key) ||
437 146 : (hash = ((PyASCIIObject *) key)->hash) == -1) {
438 22 : hash = PyObject_Hash(key);
439 22 : if (hash == -1)
440 0 : return -1;
441 : }
442 168 : entry = (so->lookup)(so, key, hash);
443 168 : if (entry == NULL)
444 0 : return -1;
445 168 : if (entry->key == NULL || entry->key == dummy)
446 146 : return DISCARD_NOTFOUND;
447 22 : old_key = entry->key;
448 22 : Py_INCREF(dummy);
449 22 : entry->key = dummy;
450 22 : so->used--;
451 22 : Py_DECREF(old_key);
452 22 : return DISCARD_FOUND;
453 : }
454 :
455 : static int
456 292 : set_clear_internal(PySetObject *so)
457 : {
458 : setentry *entry, *table;
459 : int table_is_malloced;
460 : Py_ssize_t fill;
461 : setentry small_copy[PySet_MINSIZE];
462 : #ifdef Py_DEBUG
463 : Py_ssize_t i, n;
464 : assert (PyAnySet_Check(so));
465 :
466 : n = so->mask + 1;
467 : i = 0;
468 : #endif
469 :
470 292 : table = so->table;
471 : assert(table != NULL);
472 292 : table_is_malloced = table != so->smalltable;
473 :
474 : /* This is delicate. During the process of clearing the set,
475 : * decrefs can cause the set to mutate. To avoid fatal confusion
476 : * (voice of experience), we have to make the set empty before
477 : * clearing the slots, and never refer to anything via so->ref while
478 : * clearing.
479 : */
480 292 : fill = so->fill;
481 292 : if (table_is_malloced)
482 0 : EMPTY_TO_MINSIZE(so);
483 :
484 292 : else if (fill > 0) {
485 : /* It's a small table with something that needs to be cleared.
486 : * Afraid the only safe way is to copy the set entries into
487 : * another small table first.
488 : */
489 0 : memcpy(small_copy, table, sizeof(small_copy));
490 0 : table = small_copy;
491 0 : EMPTY_TO_MINSIZE(so);
492 : }
493 : /* else it's a small table that's already empty */
494 :
495 : /* Now we can finally clear things. If C had refcounts, we could
496 : * assert that the refcount on table is 1 now, i.e. that this function
497 : * has unique access to it, so decref side-effects can't alter it.
498 : */
499 292 : for (entry = table; fill > 0; ++entry) {
500 : #ifdef Py_DEBUG
501 : assert(i < n);
502 : ++i;
503 : #endif
504 0 : if (entry->key) {
505 0 : --fill;
506 0 : Py_DECREF(entry->key);
507 : }
508 : #ifdef Py_DEBUG
509 : else
510 : assert(entry->key == NULL);
511 : #endif
512 : }
513 :
514 292 : if (table_is_malloced)
515 0 : PyMem_DEL(table);
516 292 : return 0;
517 : }
518 :
519 : /*
520 : * Iterate over a set table. Use like so:
521 : *
522 : * Py_ssize_t pos;
523 : * setentry *entry;
524 : * pos = 0; # important! pos should not otherwise be changed by you
525 : * while (set_next(yourset, &pos, &entry)) {
526 : * Refer to borrowed reference in entry->key.
527 : * }
528 : *
529 : * CAUTION: In general, it isn't safe to use set_next in a loop that
530 : * mutates the table.
531 : */
532 : static int
533 5286 : set_next(PySetObject *so, Py_ssize_t *pos_ptr, setentry **entry_ptr)
534 : {
535 : Py_ssize_t i;
536 : Py_ssize_t mask;
537 : register setentry *table;
538 :
539 : assert (PyAnySet_Check(so));
540 5286 : i = *pos_ptr;
541 : assert(i >= 0);
542 5286 : table = so->table;
543 5286 : mask = so->mask;
544 23046 : while (i <= mask && (table[i].key == NULL || table[i].key == dummy))
545 12474 : i++;
546 5286 : *pos_ptr = i+1;
547 5286 : if (i > mask)
548 832 : return 0;
549 : assert(table[i].key != NULL);
550 4454 : *entry_ptr = &table[i];
551 4454 : return 1;
552 : }
553 :
554 : static void
555 358 : set_dealloc(PySetObject *so)
556 : {
557 : register setentry *entry;
558 358 : Py_ssize_t fill = so->fill;
559 358 : PyObject_GC_UnTrack(so);
560 358 : Py_TRASHCAN_SAFE_BEGIN(so)
561 358 : if (so->weakreflist != NULL)
562 0 : PyObject_ClearWeakRefs((PyObject *) so);
563 :
564 1266 : for (entry = so->table; fill > 0; entry++) {
565 908 : if (entry->key) {
566 382 : --fill;
567 382 : Py_DECREF(entry->key);
568 : }
569 : }
570 358 : if (so->table != so->smalltable)
571 15 : PyMem_DEL(so->table);
572 358 : if (numfree < PySet_MAXFREELIST && PyAnySet_CheckExact(so))
573 358 : free_list[numfree++] = so;
574 : else
575 0 : Py_TYPE(so)->tp_free(so);
576 358 : Py_TRASHCAN_SAFE_END(so)
577 358 : }
578 :
579 : static PyObject *
580 0 : set_repr(PySetObject *so)
581 : {
582 0 : PyObject *result=NULL, *keys, *listrepr, *tmp;
583 0 : int status = Py_ReprEnter((PyObject*)so);
584 :
585 0 : if (status != 0) {
586 0 : if (status < 0)
587 0 : return NULL;
588 0 : return PyUnicode_FromFormat("%s(...)", Py_TYPE(so)->tp_name);
589 : }
590 :
591 : /* shortcut for the empty set */
592 0 : if (!so->used) {
593 0 : Py_ReprLeave((PyObject*)so);
594 0 : return PyUnicode_FromFormat("%s()", Py_TYPE(so)->tp_name);
595 : }
596 :
597 0 : keys = PySequence_List((PyObject *)so);
598 0 : if (keys == NULL)
599 0 : goto done;
600 :
601 : /* repr(keys)[1:-1] */
602 0 : listrepr = PyObject_Repr(keys);
603 0 : Py_DECREF(keys);
604 0 : if (listrepr == NULL)
605 0 : goto done;
606 0 : tmp = PyUnicode_Substring(listrepr, 1, PyUnicode_GET_LENGTH(listrepr)-1);
607 0 : Py_DECREF(listrepr);
608 0 : if (tmp == NULL)
609 0 : goto done;
610 0 : listrepr = tmp;
611 :
612 0 : if (Py_TYPE(so) != &PySet_Type)
613 0 : result = PyUnicode_FromFormat("%s({%U})",
614 0 : Py_TYPE(so)->tp_name,
615 : listrepr);
616 : else
617 0 : result = PyUnicode_FromFormat("{%U}", listrepr);
618 0 : Py_DECREF(listrepr);
619 : done:
620 0 : Py_ReprLeave((PyObject*)so);
621 0 : return result;
622 : }
623 :
624 : static Py_ssize_t
625 51 : set_len(PyObject *so)
626 : {
627 51 : return ((PySetObject *)so)->used;
628 : }
629 :
630 : static int
631 278 : set_merge(PySetObject *so, PyObject *otherset)
632 : {
633 : PySetObject *other;
634 : PyObject *key;
635 : Py_hash_t hash;
636 : register Py_ssize_t i;
637 : register setentry *entry;
638 :
639 : assert (PyAnySet_Check(so));
640 : assert (PyAnySet_Check(otherset));
641 :
642 278 : other = (PySetObject*)otherset;
643 278 : if (other == so || other->used == 0)
644 : /* a.update(a) or a.update({}); nothing to do */
645 193 : return 0;
646 : /* Do one big resize at the start, rather than
647 : * incrementally resizing as we insert new keys. Expect
648 : * that there will be no (or few) overlapping keys.
649 : */
650 85 : if ((so->fill + other->used)*3 >= (so->mask+1)*2) {
651 6 : if (set_table_resize(so, (so->used + other->used)*2) != 0)
652 0 : return -1;
653 : }
654 837 : for (i = 0; i <= other->mask; i++) {
655 752 : entry = &other->table[i];
656 752 : key = entry->key;
657 752 : hash = entry->hash;
658 902 : if (key != NULL &&
659 150 : key != dummy) {
660 150 : Py_INCREF(key);
661 150 : if (set_insert_key(so, key, hash) == -1) {
662 0 : Py_DECREF(key);
663 0 : return -1;
664 : }
665 : }
666 : }
667 85 : return 0;
668 : }
669 :
670 : static int
671 8562 : set_contains_key(PySetObject *so, PyObject *key)
672 : {
673 : Py_hash_t hash;
674 : setentry *entry;
675 :
676 16992 : if (!PyUnicode_CheckExact(key) ||
677 8430 : (hash = ((PyASCIIObject *) key)->hash) == -1) {
678 1192 : hash = PyObject_Hash(key);
679 1192 : if (hash == -1)
680 0 : return -1;
681 : }
682 8562 : entry = (so->lookup)(so, key, hash);
683 8562 : if (entry == NULL)
684 0 : return -1;
685 8562 : key = entry->key;
686 8562 : return key != NULL && key != dummy;
687 : }
688 :
689 : static int
690 4 : set_contains_entry(PySetObject *so, setentry *entry)
691 : {
692 : PyObject *key;
693 : setentry *lu_entry;
694 :
695 4 : lu_entry = (so->lookup)(so, entry->key, entry->hash);
696 4 : if (lu_entry == NULL)
697 0 : return -1;
698 4 : key = lu_entry->key;
699 4 : return key != NULL && key != dummy;
700 : }
701 :
702 : static PyObject *
703 0 : set_pop(PySetObject *so)
704 : {
705 0 : register Py_ssize_t i = 0;
706 : register setentry *entry;
707 : PyObject *key;
708 :
709 : assert (PyAnySet_Check(so));
710 0 : if (so->used == 0) {
711 0 : PyErr_SetString(PyExc_KeyError, "pop from an empty set");
712 0 : return NULL;
713 : }
714 :
715 : /* Set entry to "the first" unused or dummy set entry. We abuse
716 : * the hash field of slot 0 to hold a search finger:
717 : * If slot 0 has a value, use slot 0.
718 : * Else slot 0 is being used to hold a search finger,
719 : * and we use its hash value as the first index to look.
720 : */
721 0 : entry = &so->table[0];
722 0 : if (entry->key == NULL || entry->key == dummy) {
723 0 : i = entry->hash;
724 : /* The hash field may be a real hash value, or it may be a
725 : * legit search finger, or it may be a once-legit search
726 : * finger that's out of bounds now because it wrapped around
727 : * or the table shrunk -- simply make sure it's in bounds now.
728 : */
729 0 : if (i > so->mask || i < 1)
730 0 : i = 1; /* skip slot 0 */
731 0 : while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
732 0 : i++;
733 0 : if (i > so->mask)
734 0 : i = 1;
735 : }
736 : }
737 0 : key = entry->key;
738 0 : Py_INCREF(dummy);
739 0 : entry->key = dummy;
740 0 : so->used--;
741 0 : so->table[0].hash = i + 1; /* next place to start */
742 0 : return key;
743 : }
744 :
745 : PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\
746 : Raises KeyError if the set is empty.");
747 :
748 : static int
749 830 : set_traverse(PySetObject *so, visitproc visit, void *arg)
750 : {
751 830 : Py_ssize_t pos = 0;
752 : setentry *entry;
753 :
754 6110 : while (set_next(so, &pos, &entry))
755 4450 : Py_VISIT(entry->key);
756 830 : return 0;
757 : }
758 :
759 : static Py_hash_t
760 0 : frozenset_hash(PyObject *self)
761 : {
762 0 : PySetObject *so = (PySetObject *)self;
763 0 : Py_uhash_t h, hash = 1927868237U;
764 : setentry *entry;
765 0 : Py_ssize_t pos = 0;
766 :
767 0 : if (so->hash != -1)
768 0 : return so->hash;
769 :
770 0 : hash *= (Py_uhash_t)PySet_GET_SIZE(self) + 1;
771 0 : while (set_next(so, &pos, &entry)) {
772 : /* Work to increase the bit dispersion for closely spaced hash
773 : values. The is important because some use cases have many
774 : combinations of a small number of elements with nearby
775 : hashes so that many distinct combinations collapse to only
776 : a handful of distinct hash values. */
777 0 : h = entry->hash;
778 0 : hash ^= (h ^ (h << 16) ^ 89869747U) * 3644798167U;
779 : }
780 0 : hash = hash * 69069U + 907133923U;
781 0 : if (hash == -1)
782 0 : hash = 590923713U;
783 0 : so->hash = hash;
784 0 : return hash;
785 : }
786 :
787 : /***** Set iterator type ***********************************************/
788 :
789 : typedef struct {
790 : PyObject_HEAD
791 : PySetObject *si_set; /* Set to NULL when iterator is exhausted */
792 : Py_ssize_t si_used;
793 : Py_ssize_t si_pos;
794 : Py_ssize_t len;
795 : } setiterobject;
796 :
797 : static void
798 89 : setiter_dealloc(setiterobject *si)
799 : {
800 89 : Py_XDECREF(si->si_set);
801 89 : PyObject_GC_Del(si);
802 89 : }
803 :
804 : static int
805 0 : setiter_traverse(setiterobject *si, visitproc visit, void *arg)
806 : {
807 0 : Py_VISIT(si->si_set);
808 0 : return 0;
809 : }
810 :
811 : static PyObject *
812 0 : setiter_len(setiterobject *si)
813 : {
814 0 : Py_ssize_t len = 0;
815 0 : if (si->si_set != NULL && si->si_used == si->si_set->used)
816 0 : len = si->len;
817 0 : return PyLong_FromSsize_t(len);
818 : }
819 :
820 : PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
821 :
822 : static PyObject *setiter_iternext(setiterobject *si);
823 :
824 : static PyObject *
825 0 : setiter_reduce(setiterobject *si)
826 : {
827 : PyObject *list;
828 : setiterobject tmp;
829 :
830 0 : list = PyList_New(0);
831 0 : if (!list)
832 0 : return NULL;
833 :
834 : /* copy the itertor state */
835 0 : tmp = *si;
836 0 : Py_XINCREF(tmp.si_set);
837 :
838 : /* iterate the temporary into a list */
839 : for(;;) {
840 0 : PyObject *element = setiter_iternext(&tmp);
841 0 : if (element) {
842 0 : if (PyList_Append(list, element)) {
843 0 : Py_DECREF(element);
844 0 : Py_DECREF(list);
845 0 : Py_XDECREF(tmp.si_set);
846 0 : return NULL;
847 : }
848 0 : Py_DECREF(element);
849 : } else
850 0 : break;
851 0 : }
852 0 : Py_XDECREF(tmp.si_set);
853 : /* check for error */
854 0 : if (tmp.si_set != NULL) {
855 : /* we have an error */
856 0 : Py_DECREF(list);
857 0 : return NULL;
858 : }
859 0 : return Py_BuildValue("N(N)", _PyObject_GetBuiltin("iter"), list);
860 : }
861 :
862 : PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
863 :
864 : static PyMethodDef setiter_methods[] = {
865 : {"__length_hint__", (PyCFunction)setiter_len, METH_NOARGS, length_hint_doc},
866 : {"__reduce__", (PyCFunction)setiter_reduce, METH_NOARGS, reduce_doc},
867 : {NULL, NULL} /* sentinel */
868 : };
869 :
870 213 : static PyObject *setiter_iternext(setiterobject *si)
871 : {
872 : PyObject *key;
873 : register Py_ssize_t i, mask;
874 : register setentry *entry;
875 213 : PySetObject *so = si->si_set;
876 :
877 213 : if (so == NULL)
878 0 : return NULL;
879 : assert (PyAnySet_Check(so));
880 :
881 213 : if (si->si_used != so->used) {
882 0 : PyErr_SetString(PyExc_RuntimeError,
883 : "Set changed size during iteration");
884 0 : si->si_used = -1; /* Make this state sticky */
885 0 : return NULL;
886 : }
887 :
888 213 : i = si->si_pos;
889 : assert(i>=0);
890 213 : entry = so->table;
891 213 : mask = so->mask;
892 1125 : while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
893 699 : i++;
894 213 : si->si_pos = i+1;
895 213 : if (i > mask)
896 88 : goto fail;
897 125 : si->len--;
898 125 : key = entry[i].key;
899 125 : Py_INCREF(key);
900 125 : return key;
901 :
902 : fail:
903 88 : Py_DECREF(so);
904 88 : si->si_set = NULL;
905 88 : return NULL;
906 : }
907 :
908 : PyTypeObject PySetIter_Type = {
909 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
910 : "set_iterator", /* tp_name */
911 : sizeof(setiterobject), /* tp_basicsize */
912 : 0, /* tp_itemsize */
913 : /* methods */
914 : (destructor)setiter_dealloc, /* tp_dealloc */
915 : 0, /* tp_print */
916 : 0, /* tp_getattr */
917 : 0, /* tp_setattr */
918 : 0, /* tp_reserved */
919 : 0, /* tp_repr */
920 : 0, /* tp_as_number */
921 : 0, /* tp_as_sequence */
922 : 0, /* tp_as_mapping */
923 : 0, /* tp_hash */
924 : 0, /* tp_call */
925 : 0, /* tp_str */
926 : PyObject_GenericGetAttr, /* tp_getattro */
927 : 0, /* tp_setattro */
928 : 0, /* tp_as_buffer */
929 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
930 : 0, /* tp_doc */
931 : (traverseproc)setiter_traverse, /* tp_traverse */
932 : 0, /* tp_clear */
933 : 0, /* tp_richcompare */
934 : 0, /* tp_weaklistoffset */
935 : PyObject_SelfIter, /* tp_iter */
936 : (iternextfunc)setiter_iternext, /* tp_iternext */
937 : setiter_methods, /* tp_methods */
938 : 0,
939 : };
940 :
941 : static PyObject *
942 89 : set_iter(PySetObject *so)
943 : {
944 89 : setiterobject *si = PyObject_GC_New(setiterobject, &PySetIter_Type);
945 89 : if (si == NULL)
946 0 : return NULL;
947 89 : Py_INCREF(so);
948 89 : si->si_set = so;
949 89 : si->si_used = so->used;
950 89 : si->si_pos = 0;
951 89 : si->len = so->used;
952 89 : _PyObject_GC_TRACK(si);
953 89 : return (PyObject *)si;
954 : }
955 :
956 : static int
957 309 : set_update_internal(PySetObject *so, PyObject *other)
958 : {
959 : PyObject *key, *it;
960 :
961 309 : if (PyAnySet_Check(other))
962 278 : return set_merge(so, other);
963 :
964 31 : if (PyDict_CheckExact(other)) {
965 : PyObject *value;
966 0 : Py_ssize_t pos = 0;
967 : Py_hash_t hash;
968 0 : Py_ssize_t dictsize = PyDict_Size(other);
969 :
970 : /* Do one big resize at the start, rather than
971 : * incrementally resizing as we insert new keys. Expect
972 : * that there will be no (or few) overlapping keys.
973 : */
974 0 : if (dictsize == -1)
975 0 : return -1;
976 0 : if ((so->fill + dictsize)*3 >= (so->mask+1)*2) {
977 0 : if (set_table_resize(so, (so->used + dictsize)*2) != 0)
978 0 : return -1;
979 : }
980 0 : while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
981 : setentry an_entry;
982 :
983 0 : an_entry.hash = hash;
984 0 : an_entry.key = key;
985 0 : if (set_add_entry(so, &an_entry) == -1)
986 0 : return -1;
987 : }
988 0 : return 0;
989 : }
990 :
991 31 : it = PyObject_GetIter(other);
992 31 : if (it == NULL)
993 0 : return -1;
994 :
995 1682 : while ((key = PyIter_Next(it)) != NULL) {
996 1620 : if (set_add_key(so, key) == -1) {
997 0 : Py_DECREF(it);
998 0 : Py_DECREF(key);
999 0 : return -1;
1000 : }
1001 1620 : Py_DECREF(key);
1002 : }
1003 31 : Py_DECREF(it);
1004 31 : if (PyErr_Occurred())
1005 0 : return -1;
1006 31 : return 0;
1007 : }
1008 :
1009 : static PyObject *
1010 0 : set_update(PySetObject *so, PyObject *args)
1011 : {
1012 : Py_ssize_t i;
1013 :
1014 0 : for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1015 0 : PyObject *other = PyTuple_GET_ITEM(args, i);
1016 0 : if (set_update_internal(so, other) == -1)
1017 0 : return NULL;
1018 : }
1019 0 : Py_RETURN_NONE;
1020 : }
1021 :
1022 : PyDoc_STRVAR(update_doc,
1023 : "Update a set with the union of itself and others.");
1024 :
1025 : static PyObject *
1026 596 : make_new_set(PyTypeObject *type, PyObject *iterable)
1027 : {
1028 596 : register PySetObject *so = NULL;
1029 :
1030 596 : if (dummy == NULL) { /* Auto-initialize dummy */
1031 1 : dummy = PyUnicode_FromString("<dummy key>");
1032 1 : if (dummy == NULL)
1033 0 : return NULL;
1034 : }
1035 :
1036 : /* create PySetObject structure */
1037 596 : if (numfree &&
1038 29 : (type == &PySet_Type || type == &PyFrozenSet_Type)) {
1039 339 : so = free_list[--numfree];
1040 : assert (so != NULL && PyAnySet_CheckExact(so));
1041 339 : Py_TYPE(so) = type;
1042 339 : _Py_NewReference((PyObject *)so);
1043 339 : EMPTY_TO_MINSIZE(so);
1044 339 : PyObject_GC_Track(so);
1045 : } else {
1046 257 : so = (PySetObject *)type->tp_alloc(type, 0);
1047 257 : if (so == NULL)
1048 0 : return NULL;
1049 : /* tp_alloc has already zeroed the structure */
1050 : assert(so->table == NULL && so->fill == 0 && so->used == 0);
1051 257 : INIT_NONZERO_SET_SLOTS(so);
1052 : }
1053 :
1054 596 : so->lookup = set_lookkey_unicode;
1055 596 : so->weakreflist = NULL;
1056 :
1057 596 : if (iterable != NULL) {
1058 113 : if (set_update_internal(so, iterable) == -1) {
1059 0 : Py_DECREF(so);
1060 0 : return NULL;
1061 : }
1062 : }
1063 :
1064 596 : return (PyObject *)so;
1065 : }
1066 :
1067 : static PyObject *
1068 0 : make_new_set_basetype(PyTypeObject *type, PyObject *iterable)
1069 : {
1070 0 : if (type != &PySet_Type && type != &PyFrozenSet_Type) {
1071 0 : if (PyType_IsSubtype(type, &PySet_Type))
1072 0 : type = &PySet_Type;
1073 : else
1074 0 : type = &PyFrozenSet_Type;
1075 : }
1076 0 : return make_new_set(type, iterable);
1077 : }
1078 :
1079 : /* The empty frozenset is a singleton */
1080 : static PyObject *emptyfrozenset = NULL;
1081 :
1082 : static PyObject *
1083 32 : frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1084 : {
1085 32 : PyObject *iterable = NULL, *result;
1086 :
1087 32 : if (type == &PyFrozenSet_Type && !_PyArg_NoKeywords("frozenset()", kwds))
1088 0 : return NULL;
1089 :
1090 32 : if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
1091 0 : return NULL;
1092 :
1093 32 : if (type != &PyFrozenSet_Type)
1094 0 : return make_new_set(type, iterable);
1095 :
1096 32 : if (iterable != NULL) {
1097 : /* frozenset(f) is idempotent */
1098 32 : if (PyFrozenSet_CheckExact(iterable)) {
1099 0 : Py_INCREF(iterable);
1100 0 : return iterable;
1101 : }
1102 32 : result = make_new_set(type, iterable);
1103 32 : if (result == NULL || PySet_GET_SIZE(result))
1104 16 : return result;
1105 16 : Py_DECREF(result);
1106 : }
1107 : /* The empty frozenset is a singleton */
1108 16 : if (emptyfrozenset == NULL)
1109 1 : emptyfrozenset = make_new_set(type, NULL);
1110 16 : Py_XINCREF(emptyfrozenset);
1111 16 : return emptyfrozenset;
1112 : }
1113 :
1114 : int
1115 0 : PySet_ClearFreeList(void)
1116 : {
1117 0 : int freelist_size = numfree;
1118 : PySetObject *so;
1119 :
1120 0 : while (numfree) {
1121 0 : numfree--;
1122 0 : so = free_list[numfree];
1123 0 : PyObject_GC_Del(so);
1124 : }
1125 0 : return freelist_size;
1126 : }
1127 :
1128 : void
1129 0 : PySet_Fini(void)
1130 : {
1131 0 : PySet_ClearFreeList();
1132 0 : Py_CLEAR(dummy);
1133 0 : Py_CLEAR(emptyfrozenset);
1134 0 : }
1135 :
1136 : /* Print summary info about the state of the optimized allocator */
1137 : void
1138 0 : _PySet_DebugMallocStats(FILE *out)
1139 : {
1140 0 : _PyDebugAllocatorStats(out,
1141 : "free PySetObject",
1142 : numfree, sizeof(PySetObject));
1143 0 : }
1144 :
1145 :
1146 : static PyObject *
1147 292 : set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1148 : {
1149 292 : if (type == &PySet_Type && !_PyArg_NoKeywords("set()", kwds))
1150 0 : return NULL;
1151 :
1152 292 : return make_new_set(type, NULL);
1153 : }
1154 :
1155 : /* set_swap_bodies() switches the contents of any two sets by moving their
1156 : internal data pointers and, if needed, copying the internal smalltables.
1157 : Semantically equivalent to:
1158 :
1159 : t=set(a); a.clear(); a.update(b); b.clear(); b.update(t); del t
1160 :
1161 : The function always succeeds and it leaves both objects in a stable state.
1162 : Useful for creating temporary frozensets from sets for membership testing
1163 : in __contains__(), discard(), and remove(). Also useful for operations
1164 : that update in-place (by allowing an intermediate result to be swapped
1165 : into one of the original inputs).
1166 : */
1167 :
1168 : static void
1169 0 : set_swap_bodies(PySetObject *a, PySetObject *b)
1170 : {
1171 : Py_ssize_t t;
1172 : setentry *u;
1173 : setentry *(*f)(PySetObject *so, PyObject *key, Py_ssize_t hash);
1174 : setentry tab[PySet_MINSIZE];
1175 : Py_hash_t h;
1176 :
1177 0 : t = a->fill; a->fill = b->fill; b->fill = t;
1178 0 : t = a->used; a->used = b->used; b->used = t;
1179 0 : t = a->mask; a->mask = b->mask; b->mask = t;
1180 :
1181 0 : u = a->table;
1182 0 : if (a->table == a->smalltable)
1183 0 : u = b->smalltable;
1184 0 : a->table = b->table;
1185 0 : if (b->table == b->smalltable)
1186 0 : a->table = a->smalltable;
1187 0 : b->table = u;
1188 :
1189 0 : f = a->lookup; a->lookup = b->lookup; b->lookup = f;
1190 :
1191 0 : if (a->table == a->smalltable || b->table == b->smalltable) {
1192 0 : memcpy(tab, a->smalltable, sizeof(tab));
1193 0 : memcpy(a->smalltable, b->smalltable, sizeof(tab));
1194 0 : memcpy(b->smalltable, tab, sizeof(tab));
1195 : }
1196 :
1197 0 : if (PyType_IsSubtype(Py_TYPE(a), &PyFrozenSet_Type) &&
1198 0 : PyType_IsSubtype(Py_TYPE(b), &PyFrozenSet_Type)) {
1199 0 : h = a->hash; a->hash = b->hash; b->hash = h;
1200 : } else {
1201 0 : a->hash = -1;
1202 0 : b->hash = -1;
1203 : }
1204 0 : }
1205 :
1206 : static PyObject *
1207 0 : set_copy(PySetObject *so)
1208 : {
1209 0 : return make_new_set_basetype(Py_TYPE(so), (PyObject *)so);
1210 : }
1211 :
1212 : static PyObject *
1213 0 : frozenset_copy(PySetObject *so)
1214 : {
1215 0 : if (PyFrozenSet_CheckExact(so)) {
1216 0 : Py_INCREF(so);
1217 0 : return (PyObject *)so;
1218 : }
1219 0 : return set_copy(so);
1220 : }
1221 :
1222 : PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
1223 :
1224 : static PyObject *
1225 0 : set_clear(PySetObject *so)
1226 : {
1227 0 : set_clear_internal(so);
1228 0 : Py_RETURN_NONE;
1229 : }
1230 :
1231 : PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
1232 :
1233 : static PyObject *
1234 0 : set_union(PySetObject *so, PyObject *args)
1235 : {
1236 : PySetObject *result;
1237 : PyObject *other;
1238 : Py_ssize_t i;
1239 :
1240 0 : result = (PySetObject *)set_copy(so);
1241 0 : if (result == NULL)
1242 0 : return NULL;
1243 :
1244 0 : for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1245 0 : other = PyTuple_GET_ITEM(args, i);
1246 0 : if ((PyObject *)so == other)
1247 0 : continue;
1248 0 : if (set_update_internal(result, other) == -1) {
1249 0 : Py_DECREF(result);
1250 0 : return NULL;
1251 : }
1252 : }
1253 0 : return (PyObject *)result;
1254 : }
1255 :
1256 : PyDoc_STRVAR(union_doc,
1257 : "Return the union of sets as a new set.\n\
1258 : \n\
1259 : (i.e. all elements that are in either set.)");
1260 :
1261 : static PyObject *
1262 0 : set_or(PySetObject *so, PyObject *other)
1263 : {
1264 : PySetObject *result;
1265 :
1266 0 : if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1267 0 : Py_RETURN_NOTIMPLEMENTED;
1268 :
1269 0 : result = (PySetObject *)set_copy(so);
1270 0 : if (result == NULL)
1271 0 : return NULL;
1272 0 : if ((PyObject *)so == other)
1273 0 : return (PyObject *)result;
1274 0 : if (set_update_internal(result, other) == -1) {
1275 0 : Py_DECREF(result);
1276 0 : return NULL;
1277 : }
1278 0 : return (PyObject *)result;
1279 : }
1280 :
1281 : static PyObject *
1282 168 : set_ior(PySetObject *so, PyObject *other)
1283 : {
1284 168 : if (!PyAnySet_Check(other))
1285 0 : Py_RETURN_NOTIMPLEMENTED;
1286 :
1287 168 : if (set_update_internal(so, other) == -1)
1288 0 : return NULL;
1289 168 : Py_INCREF(so);
1290 168 : return (PyObject *)so;
1291 : }
1292 :
1293 : static PyObject *
1294 0 : set_intersection(PySetObject *so, PyObject *other)
1295 : {
1296 : PySetObject *result;
1297 : PyObject *key, *it, *tmp;
1298 :
1299 0 : if ((PyObject *)so == other)
1300 0 : return set_copy(so);
1301 :
1302 0 : result = (PySetObject *)make_new_set_basetype(Py_TYPE(so), NULL);
1303 0 : if (result == NULL)
1304 0 : return NULL;
1305 :
1306 0 : if (PyAnySet_Check(other)) {
1307 0 : Py_ssize_t pos = 0;
1308 : setentry *entry;
1309 :
1310 0 : if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1311 0 : tmp = (PyObject *)so;
1312 0 : so = (PySetObject *)other;
1313 0 : other = tmp;
1314 : }
1315 :
1316 0 : while (set_next((PySetObject *)other, &pos, &entry)) {
1317 0 : int rv = set_contains_entry(so, entry);
1318 0 : if (rv == -1) {
1319 0 : Py_DECREF(result);
1320 0 : return NULL;
1321 : }
1322 0 : if (rv) {
1323 0 : if (set_add_entry(result, entry) == -1) {
1324 0 : Py_DECREF(result);
1325 0 : return NULL;
1326 : }
1327 : }
1328 : }
1329 0 : return (PyObject *)result;
1330 : }
1331 :
1332 0 : it = PyObject_GetIter(other);
1333 0 : if (it == NULL) {
1334 0 : Py_DECREF(result);
1335 0 : return NULL;
1336 : }
1337 :
1338 0 : while ((key = PyIter_Next(it)) != NULL) {
1339 : int rv;
1340 : setentry entry;
1341 0 : Py_hash_t hash = PyObject_Hash(key);
1342 :
1343 0 : if (hash == -1) {
1344 0 : Py_DECREF(it);
1345 0 : Py_DECREF(result);
1346 0 : Py_DECREF(key);
1347 0 : return NULL;
1348 : }
1349 0 : entry.hash = hash;
1350 0 : entry.key = key;
1351 0 : rv = set_contains_entry(so, &entry);
1352 0 : if (rv == -1) {
1353 0 : Py_DECREF(it);
1354 0 : Py_DECREF(result);
1355 0 : Py_DECREF(key);
1356 0 : return NULL;
1357 : }
1358 0 : if (rv) {
1359 0 : if (set_add_entry(result, &entry) == -1) {
1360 0 : Py_DECREF(it);
1361 0 : Py_DECREF(result);
1362 0 : Py_DECREF(key);
1363 0 : return NULL;
1364 : }
1365 : }
1366 0 : Py_DECREF(key);
1367 : }
1368 0 : Py_DECREF(it);
1369 0 : if (PyErr_Occurred()) {
1370 0 : Py_DECREF(result);
1371 0 : return NULL;
1372 : }
1373 0 : return (PyObject *)result;
1374 : }
1375 :
1376 : static PyObject *
1377 0 : set_intersection_multi(PySetObject *so, PyObject *args)
1378 : {
1379 : Py_ssize_t i;
1380 0 : PyObject *result = (PyObject *)so;
1381 :
1382 0 : if (PyTuple_GET_SIZE(args) == 0)
1383 0 : return set_copy(so);
1384 :
1385 0 : Py_INCREF(so);
1386 0 : for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1387 0 : PyObject *other = PyTuple_GET_ITEM(args, i);
1388 0 : PyObject *newresult = set_intersection((PySetObject *)result, other);
1389 0 : if (newresult == NULL) {
1390 0 : Py_DECREF(result);
1391 0 : return NULL;
1392 : }
1393 0 : Py_DECREF(result);
1394 0 : result = newresult;
1395 : }
1396 0 : return result;
1397 : }
1398 :
1399 : PyDoc_STRVAR(intersection_doc,
1400 : "Return the intersection of two sets as a new set.\n\
1401 : \n\
1402 : (i.e. all elements that are in both sets.)");
1403 :
1404 : static PyObject *
1405 0 : set_intersection_update(PySetObject *so, PyObject *other)
1406 : {
1407 : PyObject *tmp;
1408 :
1409 0 : tmp = set_intersection(so, other);
1410 0 : if (tmp == NULL)
1411 0 : return NULL;
1412 0 : set_swap_bodies(so, (PySetObject *)tmp);
1413 0 : Py_DECREF(tmp);
1414 0 : Py_RETURN_NONE;
1415 : }
1416 :
1417 : static PyObject *
1418 0 : set_intersection_update_multi(PySetObject *so, PyObject *args)
1419 : {
1420 : PyObject *tmp;
1421 :
1422 0 : tmp = set_intersection_multi(so, args);
1423 0 : if (tmp == NULL)
1424 0 : return NULL;
1425 0 : set_swap_bodies(so, (PySetObject *)tmp);
1426 0 : Py_DECREF(tmp);
1427 0 : Py_RETURN_NONE;
1428 : }
1429 :
1430 : PyDoc_STRVAR(intersection_update_doc,
1431 : "Update a set with the intersection of itself and another.");
1432 :
1433 : static PyObject *
1434 0 : set_and(PySetObject *so, PyObject *other)
1435 : {
1436 0 : if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1437 0 : Py_RETURN_NOTIMPLEMENTED;
1438 0 : return set_intersection(so, other);
1439 : }
1440 :
1441 : static PyObject *
1442 0 : set_iand(PySetObject *so, PyObject *other)
1443 : {
1444 : PyObject *result;
1445 :
1446 0 : if (!PyAnySet_Check(other))
1447 0 : Py_RETURN_NOTIMPLEMENTED;
1448 0 : result = set_intersection_update(so, other);
1449 0 : if (result == NULL)
1450 0 : return NULL;
1451 0 : Py_DECREF(result);
1452 0 : Py_INCREF(so);
1453 0 : return (PyObject *)so;
1454 : }
1455 :
1456 : static PyObject *
1457 0 : set_isdisjoint(PySetObject *so, PyObject *other)
1458 : {
1459 : PyObject *key, *it, *tmp;
1460 :
1461 0 : if ((PyObject *)so == other) {
1462 0 : if (PySet_GET_SIZE(so) == 0)
1463 0 : Py_RETURN_TRUE;
1464 : else
1465 0 : Py_RETURN_FALSE;
1466 : }
1467 :
1468 0 : if (PyAnySet_CheckExact(other)) {
1469 0 : Py_ssize_t pos = 0;
1470 : setentry *entry;
1471 :
1472 0 : if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
1473 0 : tmp = (PyObject *)so;
1474 0 : so = (PySetObject *)other;
1475 0 : other = tmp;
1476 : }
1477 0 : while (set_next((PySetObject *)other, &pos, &entry)) {
1478 0 : int rv = set_contains_entry(so, entry);
1479 0 : if (rv == -1)
1480 0 : return NULL;
1481 0 : if (rv)
1482 0 : Py_RETURN_FALSE;
1483 : }
1484 0 : Py_RETURN_TRUE;
1485 : }
1486 :
1487 0 : it = PyObject_GetIter(other);
1488 0 : if (it == NULL)
1489 0 : return NULL;
1490 :
1491 0 : while ((key = PyIter_Next(it)) != NULL) {
1492 : int rv;
1493 : setentry entry;
1494 0 : Py_hash_t hash = PyObject_Hash(key);
1495 :
1496 0 : if (hash == -1) {
1497 0 : Py_DECREF(key);
1498 0 : Py_DECREF(it);
1499 0 : return NULL;
1500 : }
1501 0 : entry.hash = hash;
1502 0 : entry.key = key;
1503 0 : rv = set_contains_entry(so, &entry);
1504 0 : Py_DECREF(key);
1505 0 : if (rv == -1) {
1506 0 : Py_DECREF(it);
1507 0 : return NULL;
1508 : }
1509 0 : if (rv) {
1510 0 : Py_DECREF(it);
1511 0 : Py_RETURN_FALSE;
1512 : }
1513 : }
1514 0 : Py_DECREF(it);
1515 0 : if (PyErr_Occurred())
1516 0 : return NULL;
1517 0 : Py_RETURN_TRUE;
1518 : }
1519 :
1520 : PyDoc_STRVAR(isdisjoint_doc,
1521 : "Return True if two sets have a null intersection.");
1522 :
1523 : static int
1524 0 : set_difference_update_internal(PySetObject *so, PyObject *other)
1525 : {
1526 0 : if ((PyObject *)so == other)
1527 0 : return set_clear_internal(so);
1528 :
1529 0 : if (PyAnySet_Check(other)) {
1530 : setentry *entry;
1531 0 : Py_ssize_t pos = 0;
1532 :
1533 0 : while (set_next((PySetObject *)other, &pos, &entry))
1534 0 : if (set_discard_entry(so, entry) == -1)
1535 0 : return -1;
1536 : } else {
1537 : PyObject *key, *it;
1538 0 : it = PyObject_GetIter(other);
1539 0 : if (it == NULL)
1540 0 : return -1;
1541 :
1542 0 : while ((key = PyIter_Next(it)) != NULL) {
1543 0 : if (set_discard_key(so, key) == -1) {
1544 0 : Py_DECREF(it);
1545 0 : Py_DECREF(key);
1546 0 : return -1;
1547 : }
1548 0 : Py_DECREF(key);
1549 : }
1550 0 : Py_DECREF(it);
1551 0 : if (PyErr_Occurred())
1552 0 : return -1;
1553 : }
1554 : /* If more than 1/5 are dummies, then resize them away. */
1555 0 : if ((so->fill - so->used) * 5 < so->mask)
1556 0 : return 0;
1557 0 : return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
1558 : }
1559 :
1560 : static PyObject *
1561 0 : set_difference_update(PySetObject *so, PyObject *args)
1562 : {
1563 : Py_ssize_t i;
1564 :
1565 0 : for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
1566 0 : PyObject *other = PyTuple_GET_ITEM(args, i);
1567 0 : if (set_difference_update_internal(so, other) == -1)
1568 0 : return NULL;
1569 : }
1570 0 : Py_RETURN_NONE;
1571 : }
1572 :
1573 : PyDoc_STRVAR(difference_update_doc,
1574 : "Remove all elements of another set from this set.");
1575 :
1576 : static PyObject *
1577 0 : set_copy_and_difference(PySetObject *so, PyObject *other)
1578 : {
1579 : PyObject *result;
1580 :
1581 0 : result = set_copy(so);
1582 0 : if (result == NULL)
1583 0 : return NULL;
1584 0 : if (set_difference_update_internal((PySetObject *) result, other) != -1)
1585 0 : return result;
1586 0 : Py_DECREF(result);
1587 0 : return NULL;
1588 : }
1589 :
1590 : static PyObject *
1591 0 : set_difference(PySetObject *so, PyObject *other)
1592 : {
1593 : PyObject *result;
1594 : setentry *entry;
1595 0 : Py_ssize_t pos = 0;
1596 :
1597 0 : if (!PyAnySet_Check(other) && !PyDict_CheckExact(other)) {
1598 0 : return set_copy_and_difference(so, other);
1599 : }
1600 :
1601 : /* If len(so) much more than len(other), it's more efficient to simply copy
1602 : * so and then iterate other looking for common elements. */
1603 0 : if ((PySet_GET_SIZE(so) >> 2) > PyObject_Size(other)) {
1604 0 : return set_copy_and_difference(so, other);
1605 : }
1606 :
1607 0 : result = make_new_set_basetype(Py_TYPE(so), NULL);
1608 0 : if (result == NULL)
1609 0 : return NULL;
1610 :
1611 0 : if (PyDict_CheckExact(other)) {
1612 0 : while (set_next(so, &pos, &entry)) {
1613 : setentry entrycopy;
1614 0 : entrycopy.hash = entry->hash;
1615 0 : entrycopy.key = entry->key;
1616 0 : if (!_PyDict_Contains(other, entry->key, entry->hash)) {
1617 0 : if (set_add_entry((PySetObject *)result, &entrycopy) == -1) {
1618 0 : Py_DECREF(result);
1619 0 : return NULL;
1620 : }
1621 : }
1622 : }
1623 0 : return result;
1624 : }
1625 :
1626 : /* Iterate over so, checking for common elements in other. */
1627 0 : while (set_next(so, &pos, &entry)) {
1628 0 : int rv = set_contains_entry((PySetObject *)other, entry);
1629 0 : if (rv == -1) {
1630 0 : Py_DECREF(result);
1631 0 : return NULL;
1632 : }
1633 0 : if (!rv) {
1634 0 : if (set_add_entry((PySetObject *)result, entry) == -1) {
1635 0 : Py_DECREF(result);
1636 0 : return NULL;
1637 : }
1638 : }
1639 : }
1640 0 : return result;
1641 : }
1642 :
1643 : static PyObject *
1644 0 : set_difference_multi(PySetObject *so, PyObject *args)
1645 : {
1646 : Py_ssize_t i;
1647 : PyObject *result, *other;
1648 :
1649 0 : if (PyTuple_GET_SIZE(args) == 0)
1650 0 : return set_copy(so);
1651 :
1652 0 : other = PyTuple_GET_ITEM(args, 0);
1653 0 : result = set_difference(so, other);
1654 0 : if (result == NULL)
1655 0 : return NULL;
1656 :
1657 0 : for (i=1 ; i<PyTuple_GET_SIZE(args) ; i++) {
1658 0 : other = PyTuple_GET_ITEM(args, i);
1659 0 : if (set_difference_update_internal((PySetObject *)result, other) == -1) {
1660 0 : Py_DECREF(result);
1661 0 : return NULL;
1662 : }
1663 : }
1664 0 : return result;
1665 : }
1666 :
1667 : PyDoc_STRVAR(difference_doc,
1668 : "Return the difference of two or more sets as a new set.\n\
1669 : \n\
1670 : (i.e. all elements that are in this set but not the others.)");
1671 : static PyObject *
1672 0 : set_sub(PySetObject *so, PyObject *other)
1673 : {
1674 0 : if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1675 0 : Py_RETURN_NOTIMPLEMENTED;
1676 0 : return set_difference(so, other);
1677 : }
1678 :
1679 : static PyObject *
1680 0 : set_isub(PySetObject *so, PyObject *other)
1681 : {
1682 0 : if (!PyAnySet_Check(other))
1683 0 : Py_RETURN_NOTIMPLEMENTED;
1684 0 : if (set_difference_update_internal(so, other) == -1)
1685 0 : return NULL;
1686 0 : Py_INCREF(so);
1687 0 : return (PyObject *)so;
1688 : }
1689 :
1690 : static PyObject *
1691 0 : set_symmetric_difference_update(PySetObject *so, PyObject *other)
1692 : {
1693 : PySetObject *otherset;
1694 : PyObject *key;
1695 0 : Py_ssize_t pos = 0;
1696 : setentry *entry;
1697 :
1698 0 : if ((PyObject *)so == other)
1699 0 : return set_clear(so);
1700 :
1701 0 : if (PyDict_CheckExact(other)) {
1702 : PyObject *value;
1703 : int rv;
1704 : Py_hash_t hash;
1705 0 : while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
1706 : setentry an_entry;
1707 :
1708 0 : Py_INCREF(key);
1709 0 : an_entry.hash = hash;
1710 0 : an_entry.key = key;
1711 :
1712 0 : rv = set_discard_entry(so, &an_entry);
1713 0 : if (rv == -1) {
1714 0 : Py_DECREF(key);
1715 0 : return NULL;
1716 : }
1717 0 : if (rv == DISCARD_NOTFOUND) {
1718 0 : if (set_add_entry(so, &an_entry) == -1) {
1719 0 : Py_DECREF(key);
1720 0 : return NULL;
1721 : }
1722 : }
1723 0 : Py_DECREF(key);
1724 : }
1725 0 : Py_RETURN_NONE;
1726 : }
1727 :
1728 0 : if (PyAnySet_Check(other)) {
1729 0 : Py_INCREF(other);
1730 0 : otherset = (PySetObject *)other;
1731 : } else {
1732 0 : otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1733 0 : if (otherset == NULL)
1734 0 : return NULL;
1735 : }
1736 :
1737 0 : while (set_next(otherset, &pos, &entry)) {
1738 0 : int rv = set_discard_entry(so, entry);
1739 0 : if (rv == -1) {
1740 0 : Py_DECREF(otherset);
1741 0 : return NULL;
1742 : }
1743 0 : if (rv == DISCARD_NOTFOUND) {
1744 0 : if (set_add_entry(so, entry) == -1) {
1745 0 : Py_DECREF(otherset);
1746 0 : return NULL;
1747 : }
1748 : }
1749 : }
1750 0 : Py_DECREF(otherset);
1751 0 : Py_RETURN_NONE;
1752 : }
1753 :
1754 : PyDoc_STRVAR(symmetric_difference_update_doc,
1755 : "Update a set with the symmetric difference of itself and another.");
1756 :
1757 : static PyObject *
1758 0 : set_symmetric_difference(PySetObject *so, PyObject *other)
1759 : {
1760 : PyObject *rv;
1761 : PySetObject *otherset;
1762 :
1763 0 : otherset = (PySetObject *)make_new_set_basetype(Py_TYPE(so), other);
1764 0 : if (otherset == NULL)
1765 0 : return NULL;
1766 0 : rv = set_symmetric_difference_update(otherset, (PyObject *)so);
1767 0 : if (rv == NULL)
1768 0 : return NULL;
1769 0 : Py_DECREF(rv);
1770 0 : return (PyObject *)otherset;
1771 : }
1772 :
1773 : PyDoc_STRVAR(symmetric_difference_doc,
1774 : "Return the symmetric difference of two sets as a new set.\n\
1775 : \n\
1776 : (i.e. all elements that are in exactly one of the sets.)");
1777 :
1778 : static PyObject *
1779 0 : set_xor(PySetObject *so, PyObject *other)
1780 : {
1781 0 : if (!PyAnySet_Check(so) || !PyAnySet_Check(other))
1782 0 : Py_RETURN_NOTIMPLEMENTED;
1783 0 : return set_symmetric_difference(so, other);
1784 : }
1785 :
1786 : static PyObject *
1787 0 : set_ixor(PySetObject *so, PyObject *other)
1788 : {
1789 : PyObject *result;
1790 :
1791 0 : if (!PyAnySet_Check(other))
1792 0 : Py_RETURN_NOTIMPLEMENTED;
1793 0 : result = set_symmetric_difference_update(so, other);
1794 0 : if (result == NULL)
1795 0 : return NULL;
1796 0 : Py_DECREF(result);
1797 0 : Py_INCREF(so);
1798 0 : return (PyObject *)so;
1799 : }
1800 :
1801 : static PyObject *
1802 2 : set_issubset(PySetObject *so, PyObject *other)
1803 : {
1804 : setentry *entry;
1805 2 : Py_ssize_t pos = 0;
1806 :
1807 2 : if (!PyAnySet_Check(other)) {
1808 : PyObject *tmp, *result;
1809 0 : tmp = make_new_set(&PySet_Type, other);
1810 0 : if (tmp == NULL)
1811 0 : return NULL;
1812 0 : result = set_issubset(so, tmp);
1813 0 : Py_DECREF(tmp);
1814 0 : return result;
1815 : }
1816 2 : if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
1817 0 : Py_RETURN_FALSE;
1818 :
1819 8 : while (set_next(so, &pos, &entry)) {
1820 4 : int rv = set_contains_entry((PySetObject *)other, entry);
1821 4 : if (rv == -1)
1822 0 : return NULL;
1823 4 : if (!rv)
1824 0 : Py_RETURN_FALSE;
1825 : }
1826 2 : Py_RETURN_TRUE;
1827 : }
1828 :
1829 : PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
1830 :
1831 : static PyObject *
1832 0 : set_issuperset(PySetObject *so, PyObject *other)
1833 : {
1834 : PyObject *tmp, *result;
1835 :
1836 0 : if (!PyAnySet_Check(other)) {
1837 0 : tmp = make_new_set(&PySet_Type, other);
1838 0 : if (tmp == NULL)
1839 0 : return NULL;
1840 0 : result = set_issuperset(so, tmp);
1841 0 : Py_DECREF(tmp);
1842 0 : return result;
1843 : }
1844 0 : return set_issubset((PySetObject *)other, (PyObject *)so);
1845 : }
1846 :
1847 : PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
1848 :
1849 : static PyObject *
1850 2 : set_richcompare(PySetObject *v, PyObject *w, int op)
1851 : {
1852 : PyObject *r1, *r2;
1853 :
1854 2 : if(!PyAnySet_Check(w))
1855 0 : Py_RETURN_NOTIMPLEMENTED;
1856 :
1857 2 : switch (op) {
1858 : case Py_EQ:
1859 0 : if (PySet_GET_SIZE(v) != PySet_GET_SIZE(w))
1860 0 : Py_RETURN_FALSE;
1861 0 : if (v->hash != -1 &&
1862 0 : ((PySetObject *)w)->hash != -1 &&
1863 0 : v->hash != ((PySetObject *)w)->hash)
1864 0 : Py_RETURN_FALSE;
1865 0 : return set_issubset(v, w);
1866 : case Py_NE:
1867 0 : r1 = set_richcompare(v, w, Py_EQ);
1868 0 : if (r1 == NULL)
1869 0 : return NULL;
1870 0 : r2 = PyBool_FromLong(PyObject_Not(r1));
1871 0 : Py_DECREF(r1);
1872 0 : return r2;
1873 : case Py_LE:
1874 2 : return set_issubset(v, w);
1875 : case Py_GE:
1876 0 : return set_issuperset(v, w);
1877 : case Py_LT:
1878 0 : if (PySet_GET_SIZE(v) >= PySet_GET_SIZE(w))
1879 0 : Py_RETURN_FALSE;
1880 0 : return set_issubset(v, w);
1881 : case Py_GT:
1882 0 : if (PySet_GET_SIZE(v) <= PySet_GET_SIZE(w))
1883 0 : Py_RETURN_FALSE;
1884 0 : return set_issuperset(v, w);
1885 : }
1886 0 : Py_RETURN_NOTIMPLEMENTED;
1887 : }
1888 :
1889 : static PyObject *
1890 149 : set_add(PySetObject *so, PyObject *key)
1891 : {
1892 149 : if (set_add_key(so, key) == -1)
1893 0 : return NULL;
1894 149 : Py_RETURN_NONE;
1895 : }
1896 :
1897 : PyDoc_STRVAR(add_doc,
1898 : "Add an element to a set.\n\
1899 : \n\
1900 : This has no effect if the element is already present.");
1901 :
1902 : static int
1903 8340 : set_contains(PySetObject *so, PyObject *key)
1904 : {
1905 : PyObject *tmpkey;
1906 : int rv;
1907 :
1908 8340 : rv = set_contains_key(so, key);
1909 8340 : if (rv == -1) {
1910 0 : if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1911 0 : return -1;
1912 0 : PyErr_Clear();
1913 0 : tmpkey = make_new_set(&PyFrozenSet_Type, key);
1914 0 : if (tmpkey == NULL)
1915 0 : return -1;
1916 0 : rv = set_contains_key(so, tmpkey);
1917 0 : Py_DECREF(tmpkey);
1918 : }
1919 8340 : return rv;
1920 : }
1921 :
1922 : static PyObject *
1923 11 : set_direct_contains(PySetObject *so, PyObject *key)
1924 : {
1925 : long result;
1926 :
1927 11 : result = set_contains(so, key);
1928 11 : if (result == -1)
1929 0 : return NULL;
1930 11 : return PyBool_FromLong(result);
1931 : }
1932 :
1933 : PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
1934 :
1935 : static PyObject *
1936 22 : set_remove(PySetObject *so, PyObject *key)
1937 : {
1938 : PyObject *tmpkey;
1939 : int rv;
1940 :
1941 22 : rv = set_discard_key(so, key);
1942 22 : if (rv == -1) {
1943 0 : if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1944 0 : return NULL;
1945 0 : PyErr_Clear();
1946 0 : tmpkey = make_new_set(&PyFrozenSet_Type, key);
1947 0 : if (tmpkey == NULL)
1948 0 : return NULL;
1949 0 : rv = set_discard_key(so, tmpkey);
1950 0 : Py_DECREF(tmpkey);
1951 0 : if (rv == -1)
1952 0 : return NULL;
1953 : }
1954 :
1955 22 : if (rv == DISCARD_NOTFOUND) {
1956 0 : set_key_error(key);
1957 0 : return NULL;
1958 : }
1959 22 : Py_RETURN_NONE;
1960 : }
1961 :
1962 : PyDoc_STRVAR(remove_doc,
1963 : "Remove an element from a set; it must be a member.\n\
1964 : \n\
1965 : If the element is not a member, raise a KeyError.");
1966 :
1967 : static PyObject *
1968 0 : set_discard(PySetObject *so, PyObject *key)
1969 : {
1970 : PyObject *tmpkey;
1971 : int rv;
1972 :
1973 0 : rv = set_discard_key(so, key);
1974 0 : if (rv == -1) {
1975 0 : if (!PySet_Check(key) || !PyErr_ExceptionMatches(PyExc_TypeError))
1976 0 : return NULL;
1977 0 : PyErr_Clear();
1978 0 : tmpkey = make_new_set(&PyFrozenSet_Type, key);
1979 0 : if (tmpkey == NULL)
1980 0 : return NULL;
1981 0 : rv = set_discard_key(so, tmpkey);
1982 0 : Py_DECREF(tmpkey);
1983 0 : if (rv == -1)
1984 0 : return NULL;
1985 : }
1986 0 : Py_RETURN_NONE;
1987 : }
1988 :
1989 : PyDoc_STRVAR(discard_doc,
1990 : "Remove an element from a set if it is a member.\n\
1991 : \n\
1992 : If the element is not a member, do nothing.");
1993 :
1994 : static PyObject *
1995 0 : set_reduce(PySetObject *so)
1996 : {
1997 0 : PyObject *keys=NULL, *args=NULL, *result=NULL, *dict=NULL;
1998 : _Py_IDENTIFIER(__dict__);
1999 :
2000 0 : keys = PySequence_List((PyObject *)so);
2001 0 : if (keys == NULL)
2002 0 : goto done;
2003 0 : args = PyTuple_Pack(1, keys);
2004 0 : if (args == NULL)
2005 0 : goto done;
2006 0 : dict = _PyObject_GetAttrId((PyObject *)so, &PyId___dict__);
2007 0 : if (dict == NULL) {
2008 0 : PyErr_Clear();
2009 0 : dict = Py_None;
2010 0 : Py_INCREF(dict);
2011 : }
2012 0 : result = PyTuple_Pack(3, Py_TYPE(so), args, dict);
2013 : done:
2014 0 : Py_XDECREF(args);
2015 0 : Py_XDECREF(keys);
2016 0 : Py_XDECREF(dict);
2017 0 : return result;
2018 : }
2019 :
2020 : static PyObject *
2021 0 : set_sizeof(PySetObject *so)
2022 : {
2023 : Py_ssize_t res;
2024 :
2025 0 : res = sizeof(PySetObject);
2026 0 : if (so->table != so->smalltable)
2027 0 : res = res + (so->mask + 1) * sizeof(setentry);
2028 0 : return PyLong_FromSsize_t(res);
2029 : }
2030 :
2031 : PyDoc_STRVAR(sizeof_doc, "S.__sizeof__() -> size of S in memory, in bytes");
2032 : static int
2033 292 : set_init(PySetObject *self, PyObject *args, PyObject *kwds)
2034 : {
2035 292 : PyObject *iterable = NULL;
2036 :
2037 292 : if (!PyAnySet_Check(self))
2038 0 : return -1;
2039 292 : if (PySet_Check(self) && !_PyArg_NoKeywords("set()", kwds))
2040 0 : return -1;
2041 292 : if (!PyArg_UnpackTuple(args, Py_TYPE(self)->tp_name, 0, 1, &iterable))
2042 0 : return -1;
2043 292 : set_clear_internal(self);
2044 292 : self->hash = -1;
2045 292 : if (iterable == NULL)
2046 264 : return 0;
2047 28 : return set_update_internal(self, iterable);
2048 : }
2049 :
2050 : static PySequenceMethods set_as_sequence = {
2051 : set_len, /* sq_length */
2052 : 0, /* sq_concat */
2053 : 0, /* sq_repeat */
2054 : 0, /* sq_item */
2055 : 0, /* sq_slice */
2056 : 0, /* sq_ass_item */
2057 : 0, /* sq_ass_slice */
2058 : (objobjproc)set_contains, /* sq_contains */
2059 : };
2060 :
2061 : /* set object ********************************************************/
2062 :
2063 : #ifdef Py_DEBUG
2064 : static PyObject *test_c_api(PySetObject *so);
2065 :
2066 : PyDoc_STRVAR(test_c_api_doc, "Exercises C API. Returns True.\n\
2067 : All is well if assertions don't fail.");
2068 : #endif
2069 :
2070 : static PyMethodDef set_methods[] = {
2071 : {"add", (PyCFunction)set_add, METH_O,
2072 : add_doc},
2073 : {"clear", (PyCFunction)set_clear, METH_NOARGS,
2074 : clear_doc},
2075 : {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2076 : contains_doc},
2077 : {"copy", (PyCFunction)set_copy, METH_NOARGS,
2078 : copy_doc},
2079 : {"discard", (PyCFunction)set_discard, METH_O,
2080 : discard_doc},
2081 : {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2082 : difference_doc},
2083 : {"difference_update", (PyCFunction)set_difference_update, METH_VARARGS,
2084 : difference_update_doc},
2085 : {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2086 : intersection_doc},
2087 : {"intersection_update",(PyCFunction)set_intersection_update_multi, METH_VARARGS,
2088 : intersection_update_doc},
2089 : {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2090 : isdisjoint_doc},
2091 : {"issubset", (PyCFunction)set_issubset, METH_O,
2092 : issubset_doc},
2093 : {"issuperset", (PyCFunction)set_issuperset, METH_O,
2094 : issuperset_doc},
2095 : {"pop", (PyCFunction)set_pop, METH_NOARGS,
2096 : pop_doc},
2097 : {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2098 : reduce_doc},
2099 : {"remove", (PyCFunction)set_remove, METH_O,
2100 : remove_doc},
2101 : {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2102 : sizeof_doc},
2103 : {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2104 : symmetric_difference_doc},
2105 : {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O,
2106 : symmetric_difference_update_doc},
2107 : #ifdef Py_DEBUG
2108 : {"test_c_api", (PyCFunction)test_c_api, METH_NOARGS,
2109 : test_c_api_doc},
2110 : #endif
2111 : {"union", (PyCFunction)set_union, METH_VARARGS,
2112 : union_doc},
2113 : {"update", (PyCFunction)set_update, METH_VARARGS,
2114 : update_doc},
2115 : {NULL, NULL} /* sentinel */
2116 : };
2117 :
2118 : static PyNumberMethods set_as_number = {
2119 : 0, /*nb_add*/
2120 : (binaryfunc)set_sub, /*nb_subtract*/
2121 : 0, /*nb_multiply*/
2122 : 0, /*nb_remainder*/
2123 : 0, /*nb_divmod*/
2124 : 0, /*nb_power*/
2125 : 0, /*nb_negative*/
2126 : 0, /*nb_positive*/
2127 : 0, /*nb_absolute*/
2128 : 0, /*nb_bool*/
2129 : 0, /*nb_invert*/
2130 : 0, /*nb_lshift*/
2131 : 0, /*nb_rshift*/
2132 : (binaryfunc)set_and, /*nb_and*/
2133 : (binaryfunc)set_xor, /*nb_xor*/
2134 : (binaryfunc)set_or, /*nb_or*/
2135 : 0, /*nb_int*/
2136 : 0, /*nb_reserved*/
2137 : 0, /*nb_float*/
2138 : 0, /*nb_inplace_add*/
2139 : (binaryfunc)set_isub, /*nb_inplace_subtract*/
2140 : 0, /*nb_inplace_multiply*/
2141 : 0, /*nb_inplace_remainder*/
2142 : 0, /*nb_inplace_power*/
2143 : 0, /*nb_inplace_lshift*/
2144 : 0, /*nb_inplace_rshift*/
2145 : (binaryfunc)set_iand, /*nb_inplace_and*/
2146 : (binaryfunc)set_ixor, /*nb_inplace_xor*/
2147 : (binaryfunc)set_ior, /*nb_inplace_or*/
2148 : };
2149 :
2150 : PyDoc_STRVAR(set_doc,
2151 : "set() -> new empty set object\n\
2152 : set(iterable) -> new set object\n\
2153 : \n\
2154 : Build an unordered collection of unique elements.");
2155 :
2156 : PyTypeObject PySet_Type = {
2157 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
2158 : "set", /* tp_name */
2159 : sizeof(PySetObject), /* tp_basicsize */
2160 : 0, /* tp_itemsize */
2161 : /* methods */
2162 : (destructor)set_dealloc, /* tp_dealloc */
2163 : 0, /* tp_print */
2164 : 0, /* tp_getattr */
2165 : 0, /* tp_setattr */
2166 : 0, /* tp_reserved */
2167 : (reprfunc)set_repr, /* tp_repr */
2168 : &set_as_number, /* tp_as_number */
2169 : &set_as_sequence, /* tp_as_sequence */
2170 : 0, /* tp_as_mapping */
2171 : PyObject_HashNotImplemented, /* tp_hash */
2172 : 0, /* tp_call */
2173 : 0, /* tp_str */
2174 : PyObject_GenericGetAttr, /* tp_getattro */
2175 : 0, /* tp_setattro */
2176 : 0, /* tp_as_buffer */
2177 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2178 : Py_TPFLAGS_BASETYPE, /* tp_flags */
2179 : set_doc, /* tp_doc */
2180 : (traverseproc)set_traverse, /* tp_traverse */
2181 : (inquiry)set_clear_internal, /* tp_clear */
2182 : (richcmpfunc)set_richcompare, /* tp_richcompare */
2183 : offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2184 : (getiterfunc)set_iter, /* tp_iter */
2185 : 0, /* tp_iternext */
2186 : set_methods, /* tp_methods */
2187 : 0, /* tp_members */
2188 : 0, /* tp_getset */
2189 : 0, /* tp_base */
2190 : 0, /* tp_dict */
2191 : 0, /* tp_descr_get */
2192 : 0, /* tp_descr_set */
2193 : 0, /* tp_dictoffset */
2194 : (initproc)set_init, /* tp_init */
2195 : PyType_GenericAlloc, /* tp_alloc */
2196 : set_new, /* tp_new */
2197 : PyObject_GC_Del, /* tp_free */
2198 : };
2199 :
2200 : /* frozenset object ********************************************************/
2201 :
2202 :
2203 : static PyMethodDef frozenset_methods[] = {
2204 : {"__contains__",(PyCFunction)set_direct_contains, METH_O | METH_COEXIST,
2205 : contains_doc},
2206 : {"copy", (PyCFunction)frozenset_copy, METH_NOARGS,
2207 : copy_doc},
2208 : {"difference", (PyCFunction)set_difference_multi, METH_VARARGS,
2209 : difference_doc},
2210 : {"intersection",(PyCFunction)set_intersection_multi, METH_VARARGS,
2211 : intersection_doc},
2212 : {"isdisjoint", (PyCFunction)set_isdisjoint, METH_O,
2213 : isdisjoint_doc},
2214 : {"issubset", (PyCFunction)set_issubset, METH_O,
2215 : issubset_doc},
2216 : {"issuperset", (PyCFunction)set_issuperset, METH_O,
2217 : issuperset_doc},
2218 : {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
2219 : reduce_doc},
2220 : {"__sizeof__", (PyCFunction)set_sizeof, METH_NOARGS,
2221 : sizeof_doc},
2222 : {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
2223 : symmetric_difference_doc},
2224 : {"union", (PyCFunction)set_union, METH_VARARGS,
2225 : union_doc},
2226 : {NULL, NULL} /* sentinel */
2227 : };
2228 :
2229 : static PyNumberMethods frozenset_as_number = {
2230 : 0, /*nb_add*/
2231 : (binaryfunc)set_sub, /*nb_subtract*/
2232 : 0, /*nb_multiply*/
2233 : 0, /*nb_remainder*/
2234 : 0, /*nb_divmod*/
2235 : 0, /*nb_power*/
2236 : 0, /*nb_negative*/
2237 : 0, /*nb_positive*/
2238 : 0, /*nb_absolute*/
2239 : 0, /*nb_bool*/
2240 : 0, /*nb_invert*/
2241 : 0, /*nb_lshift*/
2242 : 0, /*nb_rshift*/
2243 : (binaryfunc)set_and, /*nb_and*/
2244 : (binaryfunc)set_xor, /*nb_xor*/
2245 : (binaryfunc)set_or, /*nb_or*/
2246 : };
2247 :
2248 : PyDoc_STRVAR(frozenset_doc,
2249 : "frozenset() -> empty frozenset object\n\
2250 : frozenset(iterable) -> frozenset object\n\
2251 : \n\
2252 : Build an immutable unordered collection of unique elements.");
2253 :
2254 : PyTypeObject PyFrozenSet_Type = {
2255 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
2256 : "frozenset", /* tp_name */
2257 : sizeof(PySetObject), /* tp_basicsize */
2258 : 0, /* tp_itemsize */
2259 : /* methods */
2260 : (destructor)set_dealloc, /* tp_dealloc */
2261 : 0, /* tp_print */
2262 : 0, /* tp_getattr */
2263 : 0, /* tp_setattr */
2264 : 0, /* tp_reserved */
2265 : (reprfunc)set_repr, /* tp_repr */
2266 : &frozenset_as_number, /* tp_as_number */
2267 : &set_as_sequence, /* tp_as_sequence */
2268 : 0, /* tp_as_mapping */
2269 : frozenset_hash, /* tp_hash */
2270 : 0, /* tp_call */
2271 : 0, /* tp_str */
2272 : PyObject_GenericGetAttr, /* tp_getattro */
2273 : 0, /* tp_setattro */
2274 : 0, /* tp_as_buffer */
2275 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2276 : Py_TPFLAGS_BASETYPE, /* tp_flags */
2277 : frozenset_doc, /* tp_doc */
2278 : (traverseproc)set_traverse, /* tp_traverse */
2279 : (inquiry)set_clear_internal, /* tp_clear */
2280 : (richcmpfunc)set_richcompare, /* tp_richcompare */
2281 : offsetof(PySetObject, weakreflist), /* tp_weaklistoffset */
2282 : (getiterfunc)set_iter, /* tp_iter */
2283 : 0, /* tp_iternext */
2284 : frozenset_methods, /* tp_methods */
2285 : 0, /* tp_members */
2286 : 0, /* tp_getset */
2287 : 0, /* tp_base */
2288 : 0, /* tp_dict */
2289 : 0, /* tp_descr_get */
2290 : 0, /* tp_descr_set */
2291 : 0, /* tp_dictoffset */
2292 : 0, /* tp_init */
2293 : PyType_GenericAlloc, /* tp_alloc */
2294 : frozenset_new, /* tp_new */
2295 : PyObject_GC_Del, /* tp_free */
2296 : };
2297 :
2298 :
2299 : /***** C API functions *************************************************/
2300 :
2301 : PyObject *
2302 270 : PySet_New(PyObject *iterable)
2303 : {
2304 270 : return make_new_set(&PySet_Type, iterable);
2305 : }
2306 :
2307 : PyObject *
2308 1 : PyFrozenSet_New(PyObject *iterable)
2309 : {
2310 1 : return make_new_set(&PyFrozenSet_Type, iterable);
2311 : }
2312 :
2313 : Py_ssize_t
2314 0 : PySet_Size(PyObject *anyset)
2315 : {
2316 0 : if (!PyAnySet_Check(anyset)) {
2317 0 : PyErr_BadInternalCall();
2318 0 : return -1;
2319 : }
2320 0 : return PySet_GET_SIZE(anyset);
2321 : }
2322 :
2323 : int
2324 0 : PySet_Clear(PyObject *set)
2325 : {
2326 0 : if (!PySet_Check(set)) {
2327 0 : PyErr_BadInternalCall();
2328 0 : return -1;
2329 : }
2330 0 : return set_clear_internal((PySetObject *)set);
2331 : }
2332 :
2333 : int
2334 222 : PySet_Contains(PyObject *anyset, PyObject *key)
2335 : {
2336 222 : if (!PyAnySet_Check(anyset)) {
2337 0 : PyErr_BadInternalCall();
2338 0 : return -1;
2339 : }
2340 222 : return set_contains_key((PySetObject *)anyset, key);
2341 : }
2342 :
2343 : int
2344 146 : PySet_Discard(PyObject *set, PyObject *key)
2345 : {
2346 146 : if (!PySet_Check(set)) {
2347 0 : PyErr_BadInternalCall();
2348 0 : return -1;
2349 : }
2350 146 : return set_discard_key((PySetObject *)set, key);
2351 : }
2352 :
2353 : int
2354 177 : PySet_Add(PyObject *anyset, PyObject *key)
2355 : {
2356 180 : if (!PySet_Check(anyset) &&
2357 3 : (!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
2358 0 : PyErr_BadInternalCall();
2359 0 : return -1;
2360 : }
2361 177 : return set_add_key((PySetObject *)anyset, key);
2362 : }
2363 :
2364 : int
2365 0 : _PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash)
2366 : {
2367 : setentry *entry;
2368 :
2369 0 : if (!PyAnySet_Check(set)) {
2370 0 : PyErr_BadInternalCall();
2371 0 : return -1;
2372 : }
2373 0 : if (set_next((PySetObject *)set, pos, &entry) == 0)
2374 0 : return 0;
2375 0 : *key = entry->key;
2376 0 : *hash = entry->hash;
2377 0 : return 1;
2378 : }
2379 :
2380 : PyObject *
2381 0 : PySet_Pop(PyObject *set)
2382 : {
2383 0 : if (!PySet_Check(set)) {
2384 0 : PyErr_BadInternalCall();
2385 0 : return NULL;
2386 : }
2387 0 : return set_pop((PySetObject *)set);
2388 : }
2389 :
2390 : int
2391 0 : _PySet_Update(PyObject *set, PyObject *iterable)
2392 : {
2393 0 : if (!PySet_Check(set)) {
2394 0 : PyErr_BadInternalCall();
2395 0 : return -1;
2396 : }
2397 0 : return set_update_internal((PySetObject *)set, iterable);
2398 : }
2399 :
2400 : #ifdef Py_DEBUG
2401 :
2402 : /* Test code to be called with any three element set.
2403 : Returns True and original set is restored. */
2404 :
2405 : #define assertRaises(call_return_value, exception) \
2406 : do { \
2407 : assert(call_return_value); \
2408 : assert(PyErr_ExceptionMatches(exception)); \
2409 : PyErr_Clear(); \
2410 : } while(0)
2411 :
2412 : static PyObject *
2413 : test_c_api(PySetObject *so)
2414 : {
2415 : Py_ssize_t count;
2416 : char *s;
2417 : Py_ssize_t i;
2418 : PyObject *elem=NULL, *dup=NULL, *t, *f, *dup2, *x;
2419 : PyObject *ob = (PyObject *)so;
2420 : Py_hash_t hash;
2421 : PyObject *str;
2422 :
2423 : /* Verify preconditions */
2424 : assert(PyAnySet_Check(ob));
2425 : assert(PyAnySet_CheckExact(ob));
2426 : assert(!PyFrozenSet_CheckExact(ob));
2427 :
2428 : /* so.clear(); so |= set("abc"); */
2429 : str = PyUnicode_FromString("abc");
2430 : if (str == NULL)
2431 : return NULL;
2432 : set_clear_internal(so);
2433 : if (set_update_internal(so, str) == -1) {
2434 : Py_DECREF(str);
2435 : return NULL;
2436 : }
2437 : Py_DECREF(str);
2438 :
2439 : /* Exercise type/size checks */
2440 : assert(PySet_Size(ob) == 3);
2441 : assert(PySet_GET_SIZE(ob) == 3);
2442 :
2443 : /* Raise TypeError for non-iterable constructor arguments */
2444 : assertRaises(PySet_New(Py_None) == NULL, PyExc_TypeError);
2445 : assertRaises(PyFrozenSet_New(Py_None) == NULL, PyExc_TypeError);
2446 :
2447 : /* Raise TypeError for unhashable key */
2448 : dup = PySet_New(ob);
2449 : assertRaises(PySet_Discard(ob, dup) == -1, PyExc_TypeError);
2450 : assertRaises(PySet_Contains(ob, dup) == -1, PyExc_TypeError);
2451 : assertRaises(PySet_Add(ob, dup) == -1, PyExc_TypeError);
2452 :
2453 : /* Exercise successful pop, contains, add, and discard */
2454 : elem = PySet_Pop(ob);
2455 : assert(PySet_Contains(ob, elem) == 0);
2456 : assert(PySet_GET_SIZE(ob) == 2);
2457 : assert(PySet_Add(ob, elem) == 0);
2458 : assert(PySet_Contains(ob, elem) == 1);
2459 : assert(PySet_GET_SIZE(ob) == 3);
2460 : assert(PySet_Discard(ob, elem) == 1);
2461 : assert(PySet_GET_SIZE(ob) == 2);
2462 : assert(PySet_Discard(ob, elem) == 0);
2463 : assert(PySet_GET_SIZE(ob) == 2);
2464 :
2465 : /* Exercise clear */
2466 : dup2 = PySet_New(dup);
2467 : assert(PySet_Clear(dup2) == 0);
2468 : assert(PySet_Size(dup2) == 0);
2469 : Py_DECREF(dup2);
2470 :
2471 : /* Raise SystemError on clear or update of frozen set */
2472 : f = PyFrozenSet_New(dup);
2473 : assertRaises(PySet_Clear(f) == -1, PyExc_SystemError);
2474 : assertRaises(_PySet_Update(f, dup) == -1, PyExc_SystemError);
2475 : assert(PySet_Add(f, elem) == 0);
2476 : Py_INCREF(f);
2477 : assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
2478 : Py_DECREF(f);
2479 : Py_DECREF(f);
2480 :
2481 : /* Exercise direct iteration */
2482 : i = 0, count = 0;
2483 : while (_PySet_NextEntry((PyObject *)dup, &i, &x, &hash)) {
2484 : s = _PyUnicode_AsString(x);
2485 : assert(s && (s[0] == 'a' || s[0] == 'b' || s[0] == 'c'));
2486 : count++;
2487 : }
2488 : assert(count == 3);
2489 :
2490 : /* Exercise updates */
2491 : dup2 = PySet_New(NULL);
2492 : assert(_PySet_Update(dup2, dup) == 0);
2493 : assert(PySet_Size(dup2) == 3);
2494 : assert(_PySet_Update(dup2, dup) == 0);
2495 : assert(PySet_Size(dup2) == 3);
2496 : Py_DECREF(dup2);
2497 :
2498 : /* Raise SystemError when self argument is not a set or frozenset. */
2499 : t = PyTuple_New(0);
2500 : assertRaises(PySet_Size(t) == -1, PyExc_SystemError);
2501 : assertRaises(PySet_Contains(t, elem) == -1, PyExc_SystemError);
2502 : Py_DECREF(t);
2503 :
2504 : /* Raise SystemError when self argument is not a set. */
2505 : f = PyFrozenSet_New(dup);
2506 : assert(PySet_Size(f) == 3);
2507 : assert(PyFrozenSet_CheckExact(f));
2508 : assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
2509 : assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
2510 : Py_DECREF(f);
2511 :
2512 : /* Raise KeyError when popping from an empty set */
2513 : assert(PyNumber_InPlaceSubtract(ob, ob) == ob);
2514 : Py_DECREF(ob);
2515 : assert(PySet_GET_SIZE(ob) == 0);
2516 : assertRaises(PySet_Pop(ob) == NULL, PyExc_KeyError);
2517 :
2518 : /* Restore the set from the copy using the PyNumber API */
2519 : assert(PyNumber_InPlaceOr(ob, dup) == ob);
2520 : Py_DECREF(ob);
2521 :
2522 : /* Verify constructors accept NULL arguments */
2523 : f = PySet_New(NULL);
2524 : assert(f != NULL);
2525 : assert(PySet_GET_SIZE(f) == 0);
2526 : Py_DECREF(f);
2527 : f = PyFrozenSet_New(NULL);
2528 : assert(f != NULL);
2529 : assert(PyFrozenSet_CheckExact(f));
2530 : assert(PySet_GET_SIZE(f) == 0);
2531 : Py_DECREF(f);
2532 :
2533 : Py_DECREF(elem);
2534 : Py_DECREF(dup);
2535 : Py_RETURN_TRUE;
2536 : }
2537 :
2538 : #undef assertRaises
2539 :
2540 : #endif
|
