Objects/setobject.c

   1 #include "Python.h"
   2 #include "structmember.h"
   3
   4 /* set object implementation
   5    written and maintained by Raymond D. Hettinger <python@rcn.com>
   6    derived from sets.py written by Greg V. Wilson, Alex Martelli,
   7    Guido van Rossum, Raymond Hettinger, and Tim Peters.
   8
   9    Copyright (c) 2003 Python Software Foundation.
  10    All rights reserved.
  11 */
  12
  13 #ifdef __SUNPRO_C
  14 #pragma error_messages (off,E_END_OF_LOOP_CODE_NOT_REACHED)
  15 #endif
  16
  17 static PyObject *
  18 set_update(PySetObject *so, PyObject *other)
  19 {
  20         PyObject *item, *data, *it;
  21
  22         if (PyAnySet_Check(other)) {
  23                 if (PyDict_Merge(so->data, ((PySetObject *)other)->data, 1) == -1)
  24                         return NULL;
  25                 Py_RETURN_NONE;
  26         }
  27
  28         it = PyObject_GetIter(other);
  29         if (it == NULL)
  30                 return NULL;
  31         data = so->data;
  32
  33         while ((item = PyIter_Next(it)) != NULL) {
  34                 if (PyDict_SetItem(data, item, Py_True) == -1) {
  35                         Py_DECREF(it);
  36                         Py_DECREF(item);
  37                         return NULL;
  38                 }
  39                 Py_DECREF(item);
  40         }
  41         Py_DECREF(it);
  42         if (PyErr_Occurred())
  43                 return NULL;
  44         Py_RETURN_NONE;
  45 }
  46
  47 PyDoc_STRVAR(update_doc,
  48 "Update a set with the union of itself and another.");
  49
  50 static PyObject *
  51 make_new_set(PyTypeObject *type, PyObject *iterable)
  52 {
  53         PyObject *data = NULL;
  54         PyObject *tmp;
  55         PySetObject *so = NULL;
  56
  57         data = PyDict_New();
  58         if (data == NULL)
  59                 return NULL;
  60
  61         /* create PySetObject structure */
  62         so = (PySetObject *)type->tp_alloc(type, 0);
  63         if (so == NULL) {
  64                 Py_DECREF(data);
  65                 return NULL;
  66         }
  67         so->data = data;
  68         so->hash = -1;
  69         so->weakreflist = NULL;
  70
  71         if (iterable != NULL) {
  72                 tmp = set_update(so, iterable);
  73                 if (tmp == NULL) {
  74                         Py_DECREF(so);
  75                         return NULL;
  76                 }
  77                 Py_DECREF(tmp);
  78         }
  79
  80         return (PyObject *)so;
  81 }
  82
  83 static PyObject *
  84 frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
  85 {
  86         PyObject *iterable = NULL;
  87
  88         if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
  89                 return NULL;
  90         if (iterable != NULL && PyFrozenSet_CheckExact(iterable)) {
  91                 Py_INCREF(iterable);
  92                 return iterable;
  93         }
  94         return make_new_set(type, iterable);
  95 }
  96
  97 static PyObject *
  98 set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
  99 {
 100         return make_new_set(type, NULL);
 101 }
 102
 103 static PyObject *
 104 frozenset_dict_wrapper(PyObject *d)
 105 {
 106         PySetObject *w;
 107
 108         assert(PyDict_Check(d));
 109         w = (PySetObject *)make_new_set(&PyFrozenSet_Type, NULL);
 110         if (w == NULL)
 111                 return NULL;
 112         Py_DECREF(w->data);
 113         Py_INCREF(d);
 114         w->data = d;
 115         return (PyObject *)w;
 116 }
 117
 118 static void
 119 set_dealloc(PySetObject *so)
 120 {
 121         if (so->weakreflist != NULL)
 122                 PyObject_ClearWeakRefs((PyObject *) so);
 123         Py_XDECREF(so->data);
 124         so->ob_type->tp_free(so);
 125 }
 126
 127 static PyObject *
 128 set_iter(PySetObject *so)
 129 {
 130         return PyObject_GetIter(so->data);
 131 }
 132
 133 static int
 134 set_len(PySetObject *so)
 135 {
 136         return PyDict_Size(so->data);
 137 }
 138
 139 static int
 140 set_contains(PySetObject *so, PyObject *key)
 141 {
 142         PyObject *tmp;
 143         int result;
 144
 145         result = PyDict_Contains(so->data, key);
 146         if (result == -1 && PyAnySet_Check(key)) {
 147                 PyErr_Clear();
 148                 tmp = frozenset_dict_wrapper(((PySetObject *)(key))->data);
 149                 if (tmp == NULL)
 150                         return -1;
 151                 result = PyDict_Contains(so->data, tmp);
 152                 Py_DECREF(tmp);
 153         }
 154         return result;
 155 }
 156
 157 static PyObject *
 158 set_direct_contains(PySetObject *so, PyObject *key)
 159 {
 160         long result;
 161
 162         result = set_contains(so, key);
 163         if (result == -1)
 164                 return NULL;
 165         return PyBool_FromLong(result);
 166 }
 167
 168 PyDoc_STRVAR(contains_doc, "x.__contains__(y) <==> y in x.");
 169
 170 static PyObject *
 171 set_copy(PySetObject *so)
 172 {
 173         return make_new_set(so->ob_type, (PyObject *)so);
 174 }
 175
 176 static PyObject *
 177 frozenset_copy(PySetObject *so)
 178 {
 179         if (PyFrozenSet_CheckExact(so)) {
 180                 Py_INCREF(so);
 181                 return (PyObject *)so;
 182         }
 183         return set_copy(so);
 184 }
 185
 186 PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
 187
 188 static PyObject *
 189 set_union(PySetObject *so, PyObject *other)
 190 {
 191         PySetObject *result;
 192         PyObject *rv;
 193
 194         result = (PySetObject *)set_copy(so);
 195         if (result == NULL)
 196                 return NULL;
 197         rv = set_update(result, other);
 198         if (rv == NULL) {
 199                 Py_DECREF(result);
 200                 return NULL;
 201         }
 202         Py_DECREF(rv);
 203         return (PyObject *)result;
 204 }
 205
 206 PyDoc_STRVAR(union_doc,
 207  "Return the union of two sets as a new set.\n\
 208 \n\
 209 (i.e. all elements that are in either set.)");
 210
 211 static PyObject *
 212 set_or(PySetObject *so, PyObject *other)
 213 {
 214         if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
 215                 Py_INCREF(Py_NotImplemented);
 216                 return Py_NotImplemented;
 217         }
 218         return set_union(so, other);
 219 }
 220
 221 static PyObject *
 222 set_ior(PySetObject *so, PyObject *other)
 223 {
 224         PyObject *result;
 225
 226         if (!PyAnySet_Check(other)) {
 227                 Py_INCREF(Py_NotImplemented);
 228                 return Py_NotImplemented;
 229         }
 230         result = set_update(so, other);
 231         if (result == NULL)
 232                 return NULL;
 233         Py_DECREF(result);
 234         Py_INCREF(so);
 235         return (PyObject *)so;
 236 }
 237
 238 static PyObject *
 239 set_intersection(PySetObject *so, PyObject *other)
 240 {
 241         PySetObject *result;
 242         PyObject *item, *selfdata, *tgtdata, *it, *tmp;
 243
 244         result = (PySetObject *)make_new_set(so->ob_type, NULL);
 245         if (result == NULL)
 246                 return NULL;
 247         tgtdata = result->data;
 248         selfdata = so->data;
 249
 250         if (PyAnySet_Check(other))
 251                 other = ((PySetObject *)other)->data;
 252
 253         if (PyDict_Check(other) && PyDict_Size(other) > PyDict_Size(selfdata)) {
 254                 tmp = selfdata;
 255                 selfdata = other;
 256                 other = tmp;
 257         }
 258
 259         if (PyDict_CheckExact(other)) {
 260                 PyObject *value;
 261                 int pos = 0;
 262                 while (PyDict_Next(other, &pos, &item, &value)) {
 263                         if (PyDict_Contains(selfdata, item)) {
 264                                 if (PyDict_SetItem(tgtdata, item, Py_True) == -1) {
 265                                         Py_DECREF(result);
 266                                         return NULL;
 267                                 }
 268                         }
 269                 }
 270                 return (PyObject *)result;
 271         }
 272
 273         it = PyObject_GetIter(other);
 274         if (it == NULL) {
 275                 Py_DECREF(result);
 276                 return NULL;
 277         }
 278
 279         while ((item = PyIter_Next(it)) != NULL) {
 280                 if (PyDict_Contains(selfdata, item)) {
 281                         if (PyDict_SetItem(tgtdata, item, Py_True) == -1) {
 282                                 Py_DECREF(it);
 283                                 Py_DECREF(result);
 284                                 Py_DECREF(item);
 285                                 return NULL;
 286                         }
 287                 }
 288                 Py_DECREF(item);
 289         }
 290         Py_DECREF(it);
 291         if (PyErr_Occurred()) {
 292                 Py_DECREF(result);
 293                 return NULL;
 294         }
 295         return (PyObject *)result;
 296 }
 297
 298 PyDoc_STRVAR(intersection_doc,
 299 "Return the intersection of two sets as a new set.\n\
 300 \n\
 301 (i.e. all elements that are in both sets.)");
 302
 303 static PyObject *
 304 set_intersection_update(PySetObject *so, PyObject *other)
 305 {
 306         PyObject *item, *selfdata, *it, *newdict, *tmp;
 307
 308         newdict = PyDict_New();
 309         if (newdict == NULL)
 310                 return newdict;
 311
 312         it = PyObject_GetIter(other);
 313         if (it == NULL) {
 314                 Py_DECREF(newdict);
 315                 return NULL;
 316         }
 317
 318         selfdata = so->data;
 319         while ((item = PyIter_Next(it)) != NULL) {
 320                 if (PyDict_Contains(selfdata, item)) {
 321                         if (PyDict_SetItem(newdict, item, Py_True) == -1) {
 322                                 Py_DECREF(newdict);
 323                                 Py_DECREF(it);
 324                                 Py_DECREF(item);
 325                                 return NULL;
 326                         }
 327                 }
 328                 Py_DECREF(item);
 329         }
 330         Py_DECREF(it);
 331         if (PyErr_Occurred()) {
 332                 Py_DECREF(newdict);
 333                 return NULL;
 334         }
 335         tmp = so->data;
 336         so->data = newdict;
 337         Py_DECREF(tmp);
 338         Py_RETURN_NONE;
 339 }
 340
 341 PyDoc_STRVAR(intersection_update_doc,
 342 "Update a set with the intersection of itself and another.");
 343
 344 static PyObject *
 345 set_and(PySetObject *so, PyObject *other)
 346 {
 347         if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
 348                 Py_INCREF(Py_NotImplemented);
 349                 return Py_NotImplemented;
 350         }
 351         return set_intersection(so, other);
 352 }
 353
 354 static PyObject *
 355 set_iand(PySetObject *so, PyObject *other)
 356 {
 357         PyObject *result;
 358
 359         if (!PyAnySet_Check(other)) {
 360                 Py_INCREF(Py_NotImplemented);
 361                 return Py_NotImplemented;
 362         }
 363         result = set_intersection_update(so, other);
 364         if (result == NULL)
 365                 return NULL;
 366         Py_DECREF(result);
 367         Py_INCREF(so);
 368         return (PyObject *)so;
 369 }
 370
 371 static PyObject *
 372 set_difference_update(PySetObject *so, PyObject *other)
 373 {
 374         PyObject *item, *tgtdata, *it;
 375
 376         it = PyObject_GetIter(other);
 377         if (it == NULL)
 378                 return NULL;
 379
 380         tgtdata = so->data;
 381         while ((item = PyIter_Next(it)) != NULL) {
 382                 if (PyDict_DelItem(tgtdata, item) == -1) {
 383                         if (PyErr_ExceptionMatches(PyExc_KeyError))
 384                                 PyErr_Clear();
 385                         else {
 386                                 Py_DECREF(it);
 387                                 Py_DECREF(item);
 388                                 return NULL;
 389                         }
 390                 }
 391                 Py_DECREF(item);
 392         }
 393         Py_DECREF(it);
 394         if (PyErr_Occurred())
 395                 return NULL;
 396         Py_RETURN_NONE;
 397 }
 398
 399 PyDoc_STRVAR(difference_update_doc,
 400 "Remove all elements of another set from this set.");
 401
 402 static PyObject *
 403 set_difference(PySetObject *so, PyObject *other)
 404 {
 405         PyObject *result, *tmp;
 406         PyObject *otherdata, *tgtdata;
 407         PyObject *key, *value;
 408         int pos = 0;
 409
 410         if (PyDict_Check(other))
 411                 otherdata = other;
 412         else if (PyAnySet_Check(other))
 413                 otherdata = ((PySetObject *)other)->data;
 414         else {
 415                 result = set_copy(so);
 416                 if (result == NULL)
 417                         return result;
 418                 tmp = set_difference_update((PySetObject *)result, other);
 419                 if (tmp != NULL) {
 420                         Py_DECREF(tmp);
 421                         return result;
 422                 }
 423                 Py_DECREF(result);
 424                 return NULL;
 425         }
 426
 427         result = make_new_set(so->ob_type, NULL);
 428         if (result == NULL)
 429                 return NULL;
 430         tgtdata = ((PySetObject *)result)->data;
 431
 432         while (PyDict_Next(so->data, &pos, &key, &value)) {
 433                 if (!PyDict_Contains(otherdata, key)) {
 434                         if (PyDict_SetItem(tgtdata, key, Py_True) == -1)
 435                                 return NULL;
 436                 }
 437         }
 438         return result;
 439 }
 440
 441 PyDoc_STRVAR(difference_doc,
 442 "Return the difference of two sets as a new set.\n\
 443 \n\
 444 (i.e. all elements that are in this set but not the other.)");
 445 static PyObject *
 446 set_sub(PySetObject *so, PyObject *other)
 447 {
 448         if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
 449                 Py_INCREF(Py_NotImplemented);
 450                 return Py_NotImplemented;
 451         }
 452         return set_difference(so, other);
 453 }
 454
 455 static PyObject *
 456 set_isub(PySetObject *so, PyObject *other)
 457 {
 458         PyObject *result;
 459
 460         if (!PyAnySet_Check(other)) {
 461                 Py_INCREF(Py_NotImplemented);
 462                 return Py_NotImplemented;
 463         }
 464         result = set_difference_update(so, other);
 465         if (result == NULL)
 466                 return NULL;
 467         Py_DECREF(result);
 468         Py_INCREF(so);
 469         return (PyObject *)so;
 470 }
 471
 472 static PyObject *
 473 set_symmetric_difference_update(PySetObject *so, PyObject *other)
 474 {
 475         PyObject *selfdata, *otherdata;
 476         PySetObject *otherset = NULL;
 477         PyObject *key, *value;
 478         int pos = 0;
 479
 480         selfdata = so->data;
 481         if (PyDict_Check(other))
 482                 otherdata = other;
 483         else if (PyAnySet_Check(other))
 484                 otherdata = ((PySetObject *)other)->data;
 485         else {
 486                 otherset = (PySetObject *)make_new_set(so->ob_type, other);
 487                 if (otherset == NULL)
 488                         return NULL;
 489                 otherdata = otherset->data;
 490         }
 491
 492         while (PyDict_Next(otherdata, &pos, &key, &value)) {
 493                 if (PyDict_Contains(selfdata, key)) {
 494                         if (PyDict_DelItem(selfdata, key) == -1) {
 495                                 Py_XDECREF(otherset);
 496                                 return NULL;
 497                         }
 498                 } else {
 499                         if (PyDict_SetItem(selfdata, key, Py_True) == -1) {
 500                                 Py_XDECREF(otherset);
 501                                 return NULL;
 502                         }
 503                 }
 504         }
 505         Py_XDECREF(otherset);
 506         Py_RETURN_NONE;
 507 }
 508
 509 PyDoc_STRVAR(symmetric_difference_update_doc,
 510 "Update a set with the symmetric difference of itself and another.");
 511
 512 static PyObject *
 513 set_symmetric_difference(PySetObject *so, PyObject *other)
 514 {
 515         PySetObject *result;
 516         PyObject *selfdata, *otherdata, *tgtdata, *rv, *otherset;
 517         PyObject *key, *value;
 518         int pos = 0;
 519
 520         if (PyDict_Check(other))
 521                 otherdata = other;
 522         else if (PyAnySet_Check(other))
 523                 otherdata = ((PySetObject *)other)->data;
 524         else {
 525                 otherset = make_new_set(so->ob_type, other);
 526                 if (otherset == NULL)
 527                         return NULL;
 528                 rv = set_symmetric_difference_update((PySetObject *)otherset, (PyObject *)so);
 529                 if (rv == NULL)
 530                         return NULL;
 531                 Py_DECREF(rv);
 532                 return otherset;
 533         }
 534
 535         result = (PySetObject *)make_new_set(so->ob_type, NULL);
 536         if (result == NULL)
 537                 return NULL;
 538         tgtdata = result->data;
 539         selfdata = so->data;
 540
 541         while (PyDict_Next(otherdata, &pos, &key, &value)) {
 542                 if (!PyDict_Contains(selfdata, key)) {
 543                         if (PyDict_SetItem(tgtdata, key, Py_True) == -1) {
 544                                 Py_DECREF(result);
 545                                 return NULL;
 546                         }
 547                 }
 548         }
 549
 550         pos = 0;
 551         while (PyDict_Next(selfdata, &pos, &key, &value)) {
 552                 if (!PyDict_Contains(otherdata, key)) {
 553                         if (PyDict_SetItem(tgtdata, key, Py_True) == -1) {
 554                                 Py_DECREF(result);
 555                                 return NULL;
 556                         }
 557                 }
 558         }
 559
 560         return (PyObject *)result;
 561 }
 562
 563 PyDoc_STRVAR(symmetric_difference_doc,
 564 "Return the symmetric difference of two sets as a new set.\n\
 565 \n\
 566 (i.e. all elements that are in exactly one of the sets.)");
 567
 568 static PyObject *
 569 set_xor(PySetObject *so, PyObject *other)
 570 {
 571         if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
 572                 Py_INCREF(Py_NotImplemented);
 573                 return Py_NotImplemented;
 574         }
 575         return set_symmetric_difference(so, other);
 576 }
 577
 578 static PyObject *
 579 set_ixor(PySetObject *so, PyObject *other)
 580 {
 581         PyObject *result;
 582
 583         if (!PyAnySet_Check(other)) {
 584                 Py_INCREF(Py_NotImplemented);
 585                 return Py_NotImplemented;
 586         }
 587         result = set_symmetric_difference_update(so, other);
 588         if (result == NULL)
 589                 return NULL;
 590         Py_DECREF(result);
 591         Py_INCREF(so);
 592         return (PyObject *)so;
 593 }
 594
 595 static PyObject *
 596 set_issubset(PySetObject *so, PyObject *other)
 597 {
 598         PyObject *otherdata, *tmp, *result;
 599         PyObject *key, *value;
 600         int pos = 0;
 601
 602         if (!PyAnySet_Check(other)) {
 603                 tmp = make_new_set(&PySet_Type, other);
 604                 if (tmp == NULL)
 605                         return NULL;
 606                 result = set_issubset(so, tmp);
 607                 Py_DECREF(tmp);
 608                 return result;
 609         }
 610         if (set_len(so) > set_len((PySetObject *)other))
 611                 Py_RETURN_FALSE;
 612
 613         otherdata = ((PySetObject *)other)->data;
 614         while (PyDict_Next(((PySetObject *)so)->data, &pos, &key, &value)) {
 615                 if (!PyDict_Contains(otherdata, key))
 616                         Py_RETURN_FALSE;
 617         }
 618         Py_RETURN_TRUE;
 619 }
 620
 621 PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
 622
 623 static PyObject *
 624 set_issuperset(PySetObject *so, PyObject *other)
 625 {
 626         PyObject *tmp, *result;
 627
 628         if (!PyAnySet_Check(other)) {
 629                 tmp = make_new_set(&PySet_Type, other);
 630                 if (tmp == NULL)
 631                         return NULL;
 632                 result = set_issuperset(so, tmp);
 633                 Py_DECREF(tmp);
 634                 return result;
 635         }
 636         return set_issubset((PySetObject *)other, (PyObject *)so);
 637 }
 638
 639 PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
 640
 641 static long
 642 set_nohash(PyObject *self)
 643 {
 644         PyErr_SetString(PyExc_TypeError, "set objects are unhashable");
 645         return -1;
 646 }
 647
 648 static int
 649 set_nocmp(PyObject *self)
 650 {
 651         PyErr_SetString(PyExc_TypeError, "cannot compare sets using cmp()");
 652         return -1;
 653 }
 654
 655 static long
 656 frozenset_hash(PyObject *self)
 657 {
 658         PySetObject *so = (PySetObject *)self;
 659         PyObject *key, *value;
 660         int pos = 0;
 661         long hash = 1927868237L;
 662
 663         if (so->hash != -1)
 664                 return so->hash;
 665
 666         hash *= (PyDict_Size(so->data) + 1);
 667         while (PyDict_Next(so->data, &pos, &key, &value)) {
 668                 /* Work to increase the bit dispersion for closely spaced hash
 669                    values.  The is important because some use cases have many
 670                    combinations of a small number of elements with nearby
 671                    hashes so that many distinct combinations collapse to only
 672                    a handful of distinct hash values. */
 673                 long h = PyObject_Hash(key);
 674                 hash ^= (h ^ (h << 16) ^ 89869747L)  * 3644798167u;
 675         }
 676         hash = hash * 69069L + 907133923L;
 677         if (hash == -1)
 678                 hash = 590923713L;
 679         so->hash = hash;
 680         return hash;
 681 }
 682
 683 static PyObject *
 684 set_richcompare(PySetObject *v, PyObject *w, int op)
 685 {
 686         if(!PyAnySet_Check(w)) {
 687                 if (op == Py_EQ)
 688                         Py_RETURN_FALSE;
 689                 if (op == Py_NE)
 690                         Py_RETURN_TRUE;
 691                 PyErr_SetString(PyExc_TypeError, "can only compare to a set");
 692                 return NULL;
 693         }
 694         switch (op) {
 695         case Py_EQ:
 696         case Py_NE:
 697                 return PyObject_RichCompare(((PySetObject *)v)->data,
 698                         ((PySetObject *)w)->data, op);
 699         case Py_LE:
 700                 return set_issubset((PySetObject *)v, w);
 701         case Py_GE:
 702                 return set_issuperset((PySetObject *)v, w);
 703         case Py_LT:
 704                 if (set_len(v) >= set_len((PySetObject *)w))
 705                         Py_RETURN_FALSE;
 706                 return set_issubset((PySetObject *)v, w);
 707         case Py_GT:
 708                 if (set_len(v) <= set_len((PySetObject *)w))
 709                         Py_RETURN_FALSE;
 710                 return set_issuperset((PySetObject *)v, w);
 711         }
 712         Py_INCREF(Py_NotImplemented);
 713         return Py_NotImplemented;
 714 }
 715
 716 static PyObject *
 717 set_repr(PySetObject *so)
 718 {
 719         PyObject *keys, *result, *listrepr;
 720
 721         keys = PyDict_Keys(so->data);
 722         if (keys == NULL)
 723                 return NULL;
 724         listrepr = PyObject_Repr(keys);
 725         Py_DECREF(keys);
 726         if (listrepr == NULL)
 727                 return NULL;
 728
 729         result = PyString_FromFormat("%s(%s)", so->ob_type->tp_name,
 730                 PyString_AS_STRING(listrepr));
 731         Py_DECREF(listrepr);
 732         return result;
 733 }
 734
 735 static int
 736 set_tp_print(PySetObject *so, FILE *fp, int flags)
 737 {
 738         PyObject *key, *value;
 739         int pos=0;
 740         char *emit = "";        /* No separator emitted on first pass */
 741         char *separator = ", ";
 742
 743         fprintf(fp, "%s([", so->ob_type->tp_name);
 744         while (PyDict_Next(so->data, &pos, &key, &value)) {
 745                 fputs(emit, fp);
 746                 emit = separator;
 747                 if (PyObject_Print(key, fp, 0) != 0)
 748                         return -1;
 749         }
 750         fputs("])", fp);
 751         return 0;
 752 }
 753
 754 static PyObject *
 755 set_clear(PySetObject *so)
 756 {
 757         PyDict_Clear(so->data);
 758         so->hash = -1;
 759         Py_RETURN_NONE;
 760 }
 761
 762 PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
 763
 764 static PyObject *
 765 set_add(PySetObject *so, PyObject *item)
 766 {
 767         if (PyDict_SetItem(so->data, item, Py_True) == -1)
 768                 return NULL;
 769         Py_RETURN_NONE;
 770 }
 771
 772 PyDoc_STRVAR(add_doc,
 773 "Add an element to a set.\n\
 774 \n\
 775 This has no effect if the element is already present.");
 776
 777 static PyObject *
 778 set_remove(PySetObject *so, PyObject *item)
 779 {
 780         PyObject *tmp, *result;
 781
 782         if (PyType_IsSubtype(item->ob_type, &PySet_Type)) {
 783                 tmp = frozenset_dict_wrapper(((PySetObject *)(item))->data);
 784                 if (tmp == NULL)
 785                         return NULL;
 786                 result = set_remove(so, tmp);
 787                 Py_DECREF(tmp);
 788                 return result;
 789         }
 790
 791         if (PyDict_DelItem(so->data, item) == -1)
 792                 return NULL;
 793         Py_RETURN_NONE;
 794 }
 795
 796 PyDoc_STRVAR(remove_doc,
 797 "Remove an element from a set; it must be a member.\n\
 798 \n\
 799 If the element is not a member, raise a KeyError.");
 800
 801 static PyObject *
 802 set_discard(PySetObject *so, PyObject *item)
 803 {
 804         PyObject *tmp, *result;
 805
 806         if (PyType_IsSubtype(item->ob_type, &PySet_Type)) {
 807                 tmp = frozenset_dict_wrapper(((PySetObject *)(item))->data);
 808                 if (tmp == NULL)
 809                         return NULL;
 810                 result = set_discard(so, tmp);
 811                 Py_DECREF(tmp);
 812                 return result;
 813         }
 814
 815         if (PyDict_DelItem(so->data, item) == -1) {
 816                 if (!PyErr_ExceptionMatches(PyExc_KeyError))
 817                         return NULL;
 818                 PyErr_Clear();
 819         }
 820         Py_RETURN_NONE;
 821 }
 822
 823 PyDoc_STRVAR(discard_doc,
 824 "Remove an element from a set if it is a member.\n\
 825 \n\
 826 If the element is not a member, do nothing.");
 827
 828 static PyObject *
 829 set_pop(PySetObject *so)
 830 {
 831         PyObject *key, *value;
 832         int pos = 0;
 833
 834         if (!PyDict_Next(so->data, &pos, &key, &value)) {
 835                 PyErr_SetString(PyExc_KeyError, "pop from an empty set");
 836                 return NULL;
 837         }
 838         Py_INCREF(key);
 839         if (PyDict_DelItem(so->data, key) == -1) {
 840                 Py_DECREF(key);
 841                 return NULL;
 842         }
 843         return key;
 844 }
 845
 846 PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.");
 847
 848 static PyObject *
 849 set_reduce(PySetObject *so)
 850 {
 851         PyObject *keys=NULL, *args=NULL, *result=NULL;
 852
 853         keys = PyDict_Keys(so->data);
 854         if (keys == NULL)
 855                 goto done;
 856         args = PyTuple_Pack(1, keys);
 857         if (args == NULL)
 858                 goto done;
 859         result = PyTuple_Pack(2, so->ob_type, args);
 860 done:
 861         Py_XDECREF(args);
 862         Py_XDECREF(keys);
 863         return result;
 864 }
 865
 866 PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
 867
 868 static int
 869 set_init(PySetObject *self, PyObject *args, PyObject *kwds)
 870 {
 871         PyObject *iterable = NULL;
 872         PyObject *result;
 873
 874         if (!PyAnySet_Check(self))
 875                 return -1;
 876         if (!PyArg_UnpackTuple(args, self->ob_type->tp_name, 0, 1, &iterable))
 877                 return -1;
 878         PyDict_Clear(self->data);
 879         self->hash = -1;
 880         if (iterable == NULL)
 881                 return 0;
 882         result = set_update(self, iterable);
 883         if (result != NULL) {
 884                 Py_DECREF(result);
 885                 return 0;
 886         }
 887         return -1;
 888 }
 889
 890 static PySequenceMethods set_as_sequence = {
 891         (inquiry)set_len,               /* sq_length */
 892         0,                              /* sq_concat */
 893         0,                              /* sq_repeat */
 894         0,                              /* sq_item */
 895         0,                              /* sq_slice */
 896         0,                              /* sq_ass_item */
 897         0,                              /* sq_ass_slice */
 898         (objobjproc)set_contains,       /* sq_contains */
 899 };
 900
 901 /* set object ********************************************************/
 902
 903 static PyMethodDef set_methods[] = {
 904         {"add",         (PyCFunction)set_add,           METH_O,
 905          add_doc},
 906         {"clear",       (PyCFunction)set_clear,         METH_NOARGS,
 907          clear_doc},
 908         {"__contains__",(PyCFunction)set_direct_contains,       METH_O | METH_COEXIST,
 909          contains_doc},
 910         {"copy",        (PyCFunction)set_copy,          METH_NOARGS,
 911          copy_doc},
 912         {"discard",     (PyCFunction)set_discard,       METH_O,
 913          discard_doc},
 914         {"difference",  (PyCFunction)set_difference,    METH_O,
 915          difference_doc},
 916         {"difference_update",   (PyCFunction)set_difference_update,     METH_O,
 917          difference_update_doc},
 918         {"intersection",(PyCFunction)set_intersection,  METH_O,
 919          intersection_doc},
 920         {"intersection_update",(PyCFunction)set_intersection_update,    METH_O,
 921          intersection_update_doc},
 922         {"issubset",    (PyCFunction)set_issubset,      METH_O,
 923          issubset_doc},
 924         {"issuperset",  (PyCFunction)set_issuperset,    METH_O,
 925          issuperset_doc},
 926         {"pop",         (PyCFunction)set_pop,           METH_NOARGS,
 927          pop_doc},
 928         {"__reduce__",  (PyCFunction)set_reduce,        METH_NOARGS,
 929          reduce_doc},
 930         {"remove",      (PyCFunction)set_remove,        METH_O,
 931          remove_doc},
 932         {"symmetric_difference",(PyCFunction)set_symmetric_difference,  METH_O,
 933          symmetric_difference_doc},
 934         {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update,    METH_O,
 935          symmetric_difference_update_doc},
 936         {"union",       (PyCFunction)set_union,         METH_O,
 937          union_doc},
 938         {"update",      (PyCFunction)set_update,        METH_O,
 939          update_doc},
 940         {NULL,          NULL}   /* sentinel */
 941 };
 942
 943 static PyNumberMethods set_as_number = {
 944         0,                              /*nb_add*/
 945         (binaryfunc)set_sub,            /*nb_subtract*/
 946         0,                              /*nb_multiply*/
 947         0,                              /*nb_divide*/
 948         0,                              /*nb_remainder*/
 949         0,                              /*nb_divmod*/
 950         0,                              /*nb_power*/
 951         0,                              /*nb_negative*/
 952         0,                              /*nb_positive*/
 953         0,                              /*nb_absolute*/
 954         0,                              /*nb_nonzero*/
 955         0,                              /*nb_invert*/
 956         0,                              /*nb_lshift*/
 957         0,                              /*nb_rshift*/
 958         (binaryfunc)set_and,            /*nb_and*/
 959         (binaryfunc)set_xor,            /*nb_xor*/
 960         (binaryfunc)set_or,             /*nb_or*/
 961         0,                              /*nb_coerce*/
 962         0,                              /*nb_int*/
 963         0,                              /*nb_long*/
 964         0,                              /*nb_float*/
 965         0,                              /*nb_oct*/
 966         0,                              /*nb_hex*/
 967         0,                              /*nb_inplace_add*/
 968         (binaryfunc)set_isub,           /*nb_inplace_subtract*/
 969         0,                              /*nb_inplace_multiply*/
 970         0,                              /*nb_inplace_divide*/
 971         0,                              /*nb_inplace_remainder*/
 972         0,                              /*nb_inplace_power*/
 973         0,                              /*nb_inplace_lshift*/
 974         0,                              /*nb_inplace_rshift*/
 975         (binaryfunc)set_iand,           /*nb_inplace_and*/
 976         (binaryfunc)set_ixor,           /*nb_inplace_xor*/
 977         (binaryfunc)set_ior,            /*nb_inplace_or*/
 978 };
 979
 980 PyDoc_STRVAR(set_doc,
 981 "set(iterable) --> set object\n\
 982 \n\
 983 Build an unordered collection.");
 984
 985 PyTypeObject PySet_Type = {
 986         PyObject_HEAD_INIT(&PyType_Type)
 987         0,                              /* ob_size */
 988         "set",                          /* tp_name */
 989         sizeof(PySetObject),            /* tp_basicsize */
 990         0,                              /* tp_itemsize */
 991         /* methods */
 992         (destructor)set_dealloc,        /* tp_dealloc */
 993         (printfunc)set_tp_print,        /* tp_print */
 994         0,                              /* tp_getattr */
 995         0,                              /* tp_setattr */
 996         (cmpfunc)set_nocmp,             /* tp_compare */
 997         (reprfunc)set_repr,             /* tp_repr */
 998         &set_as_number,                 /* tp_as_number */
 999         &set_as_sequence,               /* tp_as_sequence */
1000         0,                              /* tp_as_mapping */
1001         set_nohash,                     /* tp_hash */
1002         0,                              /* tp_call */
1003         0,                              /* tp_str */
1004         PyObject_GenericGetAttr,        /* tp_getattro */
1005         0,                              /* tp_setattro */
1006         0,                              /* tp_as_buffer */
1007         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
1008                 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_WEAKREFS, /* tp_flags */
1009         set_doc,                        /* tp_doc */
1010         0,                              /* tp_traverse */
1011         0,                              /* tp_clear */
1012         (richcmpfunc)set_richcompare,   /* tp_richcompare */
1013         offsetof(PySetObject, weakreflist),     /* tp_weaklistoffset */
1014         (getiterfunc)set_iter,          /* tp_iter */
1015         0,                              /* tp_iternext */
1016         set_methods,                    /* tp_methods */
1017         0,                              /* tp_members */
1018         0,                              /* tp_getset */
1019         0,                              /* tp_base */
1020         0,                              /* tp_dict */
1021         0,                              /* tp_descr_get */
1022         0,                              /* tp_descr_set */
1023         0,                              /* tp_dictoffset */
1024         (initproc)set_init,             /* tp_init */
1025         PyType_GenericAlloc,            /* tp_alloc */
1026         set_new,                        /* tp_new */
1027         PyObject_Del,                   /* tp_free */
1028 };
1029
1030 /* frozenset object ********************************************************/
1031
1032
1033 static PyMethodDef frozenset_methods[] = {
1034         {"__contains__",(PyCFunction)set_direct_contains,       METH_O | METH_COEXIST,
1035          contains_doc},
1036         {"copy",        (PyCFunction)frozenset_copy,    METH_NOARGS,
1037          copy_doc},
1038         {"difference",  (PyCFunction)set_difference,    METH_O,
1039          difference_doc},
1040         {"intersection",(PyCFunction)set_intersection,  METH_O,
1041          intersection_doc},
1042         {"issubset",    (PyCFunction)set_issubset,      METH_O,
1043          issubset_doc},
1044         {"issuperset",  (PyCFunction)set_issuperset,    METH_O,
1045          issuperset_doc},
1046         {"__reduce__",  (PyCFunction)set_reduce,        METH_NOARGS,
1047          reduce_doc},
1048         {"symmetric_difference",(PyCFunction)set_symmetric_difference,  METH_O,
1049          symmetric_difference_doc},
1050         {"union",       (PyCFunction)set_union,         METH_O,
1051          union_doc},
1052         {NULL,          NULL}   /* sentinel */
1053 };
1054
1055 static PyNumberMethods frozenset_as_number = {
1056         0,                              /*nb_add*/
1057         (binaryfunc)set_sub,            /*nb_subtract*/
1058         0,                              /*nb_multiply*/
1059         0,                              /*nb_divide*/
1060         0,                              /*nb_remainder*/
1061         0,                              /*nb_divmod*/
1062         0,                              /*nb_power*/
1063         0,                              /*nb_negative*/
1064         0,                              /*nb_positive*/
1065         0,                              /*nb_absolute*/
1066         0,                              /*nb_nonzero*/
1067         0,                              /*nb_invert*/
1068         0,                              /*nb_lshift*/
1069         0,                              /*nb_rshift*/
1070         (binaryfunc)set_and,            /*nb_and*/
1071         (binaryfunc)set_xor,            /*nb_xor*/
1072         (binaryfunc)set_or,             /*nb_or*/
1073 };
1074
1075 PyDoc_STRVAR(frozenset_doc,
1076 "frozenset(iterable) --> frozenset object\n\
1077 \n\
1078 Build an immutable unordered collection.");
1079
1080 PyTypeObject PyFrozenSet_Type = {
1081         PyObject_HEAD_INIT(&PyType_Type)
1082         0,                              /* ob_size */
1083         "frozenset",                    /* tp_name */
1084         sizeof(PySetObject),            /* tp_basicsize */
1085         0,                              /* tp_itemsize */
1086         /* methods */
1087         (destructor)set_dealloc,        /* tp_dealloc */
1088         (printfunc)set_tp_print,        /* tp_print */
1089         0,                              /* tp_getattr */
1090         0,                              /* tp_setattr */
1091         (cmpfunc)set_nocmp,             /* tp_compare */
1092         (reprfunc)set_repr,             /* tp_repr */
1093         &frozenset_as_number,           /* tp_as_number */
1094         &set_as_sequence,               /* tp_as_sequence */
1095         0,                              /* tp_as_mapping */
1096         frozenset_hash,                 /* tp_hash */
1097         0,                              /* tp_call */
1098         0,                              /* tp_str */
1099         PyObject_GenericGetAttr,        /* tp_getattro */
1100         0,                              /* tp_setattro */
1101         0,                              /* tp_as_buffer */
1102         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
1103                 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_WEAKREFS, /* tp_flags */
1104         frozenset_doc,                  /* tp_doc */
1105         0,                              /* tp_traverse */
1106         0,                              /* tp_clear */
1107         (richcmpfunc)set_richcompare,   /* tp_richcompare */
1108         offsetof(PySetObject, weakreflist),     /* tp_weaklistoffset */
1109         (getiterfunc)set_iter,          /* tp_iter */
1110         0,                              /* tp_iternext */
1111         frozenset_methods,              /* tp_methods */
1112         0,                              /* tp_members */
1113         0,                              /* tp_getset */
1114         0,                              /* tp_base */
1115         0,                              /* tp_dict */
1116         0,                              /* tp_descr_get */
1117         0,                              /* tp_descr_set */
1118         0,                              /* tp_dictoffset */
1119         0,                              /* tp_init */
1120         PyType_GenericAlloc,            /* tp_alloc */
1121         frozenset_new,                  /* tp_new */
1122         PyObject_Del,                   /* tp_free */
1123 };