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