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