Objects/dictobject.c

   1 /***********************************************************
   2 Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam,
   3 The Netherlands.
   4
   5                         All Rights Reserved
   6
   7 Permission to use, copy, modify, and distribute this software and its
   8 documentation for any purpose and without fee is hereby granted,
   9 provided that the above copyright notice appear in all copies and that
  10 both that copyright notice and this permission notice appear in
  11 supporting documentation, and that the names of Stichting Mathematisch
  12 Centrum or CWI or Corporation for National Research Initiatives or
  13 CNRI not be used in advertising or publicity pertaining to
  14 distribution of the software without specific, written prior
  15 permission.
  16
  17 While CWI is the initial source for this software, a modified version
  18 is made available by the Corporation for National Research Initiatives
  19 (CNRI) at the Internet address ftp://ftp.python.org.
  20
  21 STICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH
  22 REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
  23 MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH
  24 CENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  25 DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  26 PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  27 TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  28 PERFORMANCE OF THIS SOFTWARE.
  29
  30 ******************************************************************/
  31
  32 /* Dictionary object implementation using a hash table */
  33
  34 #include "Python.h"
  35
  36
  37 /*
  38  * MINSIZE is the minimum size of a dictionary.
  39  */
  40
  41 #define MINSIZE 4
  42
  43 /*
  44 Table of irreducible polynomials to efficiently cycle through
  45 GF(2^n)-{0}, 2<=n<=30.
  46 */
  47 static long polys[] = {
  48         4 + 3,
  49         8 + 3,
  50         16 + 3,
  51         32 + 5,
  52         64 + 3,
  53         128 + 3,
  54         256 + 29,
  55         512 + 17,
  56         1024 + 9,
  57         2048 + 5,
  58         4096 + 83,
  59         8192 + 27,
  60         16384 + 43,
  61         32768 + 3,
  62         65536 + 45,
  63         131072 + 9,
  64         262144 + 39,
  65         524288 + 39,
  66         1048576 + 9,
  67         2097152 + 5,
  68         4194304 + 3,
  69         8388608 + 33,
  70         16777216 + 27,
  71         33554432 + 9,
  72         67108864 + 71,
  73         134217728 + 39,
  74         268435456 + 9,
  75         536870912 + 5,
  76         1073741824 + 83,
  77         0
  78 };
  79
  80 /* Object used as dummy key to fill deleted entries */
  81 static PyObject *dummy; /* Initialized by first call to newdictobject() */
  82
  83 /*
  84 Invariant for entries: when in use, me_value is not NULL and me_key is
  85 not NULL and not dummy; when not in use, me_value is NULL and me_key
  86 is either NULL or dummy.  A dummy key value cannot be replaced by
  87 NULL, since otherwise other keys may be lost.
  88 */
  89 typedef struct {
  90         long me_hash;
  91         PyObject *me_key;
  92         PyObject *me_value;
  93 #ifdef USE_CACHE_ALIGNED
  94         long    aligner;
  95 #endif
  96 } dictentry;
  97
  98 /*
  99 To ensure the lookup algorithm terminates, the table size must be a
 100 prime number and there must be at least one NULL key in the table.
 101 The value ma_fill is the number of non-NULL keys; ma_used is the number
 102 of non-NULL, non-dummy keys.
 103 To avoid slowing down lookups on a near-full table, we resize the table
 104 when it is more than half filled.
 105 */
 106 typedef struct {
 107         PyObject_HEAD
 108         int ma_fill;
 109         int ma_used;
 110         int ma_size;
 111         int ma_poly;
 112         dictentry *ma_table;
 113 } dictobject;
 114
 115 PyObject *
 116 PyDict_New()
 117 {
 118         register dictobject *mp;
 119         if (dummy == NULL) { /* Auto-initialize dummy */
 120                 dummy = PyString_FromString("<dummy key>");
 121                 if (dummy == NULL)
 122                         return NULL;
 123         }
 124         mp = PyObject_NEW(dictobject, &PyDict_Type);
 125         if (mp == NULL)
 126                 return NULL;
 127         mp->ma_size = 0;
 128         mp->ma_poly = 0;
 129         mp->ma_table = NULL;
 130         mp->ma_fill = 0;
 131         mp->ma_used = 0;
 132         return (PyObject *)mp;
 133 }
 134
 135 /*
 136 The basic lookup function used by all operations.
 137 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
 138 Open addressing is preferred over chaining since the link overhead for
 139 chaining would be substantial (100% with typical malloc overhead).
 140 However, instead of going through the table at constant steps, we cycle
 141 through the values of GF(2^n)-{0}. This avoids modulo computations, being
 142 much cheaper on RISC machines, without leading to clustering.
 143
 144 The initial probe index is computed as hash mod the table size.
 145 Subsequent probe indices use the values of x^i in GF(2^n) as an offset,
 146 where x is a root. The initial value is derived from hash, too.
 147
 148 All arithmetic on hash should ignore overflow.
 149
 150 (This version is due to Reimer Behrends, some ideas are also due to
 151 Jyrki Alakuijala and Vladimir Marangozov.)
 152 */
 153 static dictentry *lookdict Py_PROTO((dictobject *, PyObject *, long));
 154 static dictentry *
 155 lookdict(mp, key, hash)
 156         dictobject *mp;
 157         PyObject *key;
 158         register long hash;
 159 {
 160         register int i;
 161         register unsigned incr;
 162         register dictentry *freeslot;
 163         register unsigned int mask = mp->ma_size-1;
 164         dictentry *ep0 = mp->ma_table;
 165         register dictentry *ep;
 166         /* We must come up with (i, incr) such that 0 <= i < ma_size
 167            and 0 < incr < ma_size and both are a function of hash */
 168         i = (~hash) & mask;
 169         /* We use ~hash instead of hash, as degenerate hash functions, such
 170            as for ints <sigh>, can have lots of leading zeros. It's not
 171            really a performance risk, but better safe than sorry. */
 172         ep = &ep0[i];
 173         if (ep->me_key == NULL || ep->me_key == key)
 174                 return ep;
 175         if (ep->me_key == dummy)
 176                 freeslot = ep;
 177         else {
 178                 if (ep->me_hash == hash &&
 179                     PyObject_Compare(ep->me_key, key) == 0)
 180                 {
 181                         return ep;
 182                 }
 183                 freeslot = NULL;
 184         }
 185         /* XXX What if PyObject_Compare returned an exception? */
 186         /* Derive incr from hash, just to make it more arbitrary. Note that
 187            incr must not be 0, or we will get into an infinite loop.*/
 188         incr = (hash ^ ((unsigned long)hash >> 3)) & mask;
 189         if (!incr)
 190                 incr = mask;
 191         for (;;) {
 192                 ep = &ep0[(i+incr)&mask];
 193                 if (ep->me_key == NULL) {
 194                         if (freeslot != NULL)
 195                                 return freeslot;
 196                         else
 197                                 return ep;
 198                 }
 199                 if (ep->me_key == dummy) {
 200                         if (freeslot == NULL)
 201                                 freeslot = ep;
 202                 }
 203                 else if (ep->me_key == key ||
 204                          (ep->me_hash == hash &&
 205                           PyObject_Compare(ep->me_key, key) == 0)) {
 206                         return ep;
 207                 }
 208                 /* XXX What if PyObject_Compare returned an exception? */
 209                 /* Cycle through GF(2^n)-{0} */
 210                 incr = incr << 1;
 211                 if (incr > mask)
 212                         incr ^= mp->ma_poly; /* This will implicitely clear
 213                                                 the highest bit */
 214         }
 215 }
 216
 217 /*
 218 Internal routine to insert a new item into the table.
 219 Used both by the internal resize routine and by the public insert routine.
 220 Eats a reference to key and one to value.
 221 */
 222 static void insertdict
 223         Py_PROTO((dictobject *, PyObject *, long, PyObject *));
 224 static void
 225 insertdict(mp, key, hash, value)
 226         register dictobject *mp;
 227         PyObject *key;
 228         long hash;
 229         PyObject *value;
 230 {
 231         PyObject *old_value;
 232         register dictentry *ep;
 233         ep = lookdict(mp, key, hash);
 234         if (ep->me_value != NULL) {
 235                 old_value = ep->me_value;
 236                 ep->me_value = value;
 237                 Py_DECREF(old_value); /* which **CAN** re-enter */
 238                 Py_DECREF(key);
 239         }
 240         else {
 241                 if (ep->me_key == NULL)
 242                         mp->ma_fill++;
 243                 else
 244                         Py_DECREF(ep->me_key);
 245                 ep->me_key = key;
 246                 ep->me_hash = hash;
 247                 ep->me_value = value;
 248                 mp->ma_used++;
 249         }
 250 }
 251
 252 /*
 253 Restructure the table by allocating a new table and reinserting all
 254 items again.  When entries have been deleted, the new table may
 255 actually be smaller than the old one.
 256 */
 257 static int dictresize Py_PROTO((dictobject *, int));
 258 static int
 259 dictresize(mp, minused)
 260         dictobject *mp;
 261         int minused;
 262 {
 263         register int oldsize = mp->ma_size;
 264         register int newsize, newpoly;
 265         register dictentry *oldtable = mp->ma_table;
 266         register dictentry *newtable;
 267         register dictentry *ep;
 268         register int i;
 269         for (i = 0, newsize = MINSIZE; ; i++, newsize <<= 1) {
 270                 if (i > sizeof(polys)/sizeof(polys[0])) {
 271                         /* Ran out of polynomials */
 272                         PyErr_NoMemory();
 273                         return -1;
 274                 }
 275                 if (newsize > minused) {
 276                         newpoly = polys[i];
 277                         break;
 278                 }
 279         }
 280         newtable = (dictentry *) malloc(sizeof(dictentry) * newsize);
 281         if (newtable == NULL) {
 282                 PyErr_NoMemory();
 283                 return -1;
 284         }
 285         memset(newtable, '\0', sizeof(dictentry) * newsize);
 286         mp->ma_size = newsize;
 287         mp->ma_poly = newpoly;
 288         mp->ma_table = newtable;
 289         mp->ma_fill = 0;
 290         mp->ma_used = 0;
 291
 292         /* Make two passes, so we can avoid decrefs
 293            (and possible side effects) till the table is copied */
 294         for (i = 0, ep = oldtable; i < oldsize; i++, ep++) {
 295                 if (ep->me_value != NULL)
 296                         insertdict(mp,ep->me_key,ep->me_hash,ep->me_value);
 297         }
 298         for (i = 0, ep = oldtable; i < oldsize; i++, ep++) {
 299                 if (ep->me_value == NULL) {
 300                         Py_XDECREF(ep->me_key);
 301                 }
 302         }
 303
 304         PyMem_XDEL(oldtable);
 305         return 0;
 306 }
 307
 308 PyObject *
 309 PyDict_GetItem(op, key)
 310         PyObject *op;
 311         PyObject *key;
 312 {
 313         long hash;
 314         if (!PyDict_Check(op)) {
 315                 return NULL;
 316         }
 317         if (((dictobject *)op)->ma_table == NULL)
 318                 return NULL;
 319 #ifdef CACHE_HASH
 320         if (!PyString_Check(key) ||
 321             (hash = ((PyStringObject *) key)->ob_shash) == -1)
 322 #endif
 323         {
 324                 hash = PyObject_Hash(key);
 325                 if (hash == -1) {
 326                         PyErr_Clear();
 327                         return NULL;
 328                 }
 329         }
 330         return lookdict((dictobject *)op, key, hash) -> me_value;
 331 }
 332
 333 int
 334 PyDict_SetItem(op, key, value)
 335         register PyObject *op;
 336         PyObject *key;
 337         PyObject *value;
 338 {
 339         register dictobject *mp;
 340         register long hash;
 341         if (!PyDict_Check(op)) {
 342                 PyErr_BadInternalCall();
 343                 return -1;
 344         }
 345         mp = (dictobject *)op;
 346 #ifdef CACHE_HASH
 347         if (PyString_Check(key)) {
 348 #ifdef INTERN_STRINGS
 349                 if (((PyStringObject *)key)->ob_sinterned != NULL) {
 350                         key = ((PyStringObject *)key)->ob_sinterned;
 351                         hash = ((PyStringObject *)key)->ob_shash;
 352                 }
 353                 else
 354 #endif
 355                 {
 356                         hash = ((PyStringObject *)key)->ob_shash;
 357                         if (hash == -1)
 358                                 hash = PyObject_Hash(key);
 359                 }
 360         }
 361         else
 362 #endif
 363         {
 364                 hash = PyObject_Hash(key);
 365                 if (hash == -1)
 366                         return -1;
 367         }
 368         /* if fill >= 2/3 size, double in size */
 369         if (mp->ma_fill*3 >= mp->ma_size*2) {
 370                 if (dictresize(mp, mp->ma_used*2) != 0) {
 371                         if (mp->ma_fill+1 > mp->ma_size)
 372                                 return -1;
 373                 }
 374         }
 375         Py_INCREF(value);
 376         Py_INCREF(key);
 377         insertdict(mp, key, hash, value);
 378         return 0;
 379 }
 380
 381 int
 382 PyDict_DelItem(op, key)
 383         PyObject *op;
 384         PyObject *key;
 385 {
 386         register dictobject *mp;
 387         register long hash;
 388         register dictentry *ep;
 389         PyObject *old_value, *old_key;
 390
 391         if (!PyDict_Check(op)) {
 392                 PyErr_BadInternalCall();
 393                 return -1;
 394         }
 395 #ifdef CACHE_HASH
 396         if (!PyString_Check(key) ||
 397             (hash = ((PyStringObject *) key)->ob_shash) == -1)
 398 #endif
 399         {
 400                 hash = PyObject_Hash(key);
 401                 if (hash == -1)
 402                         return -1;
 403         }
 404         mp = (dictobject *)op;
 405         if (((dictobject *)op)->ma_table == NULL)
 406                 goto empty;
 407         ep = lookdict(mp, key, hash);
 408         if (ep->me_value == NULL) {
 409         empty:
 410                 PyErr_SetObject(PyExc_KeyError, key);
 411                 return -1;
 412         }
 413         old_key = ep->me_key;
 414         Py_INCREF(dummy);
 415         ep->me_key = dummy;
 416         old_value = ep->me_value;
 417         ep->me_value = NULL;
 418         mp->ma_used--;
 419         Py_DECREF(old_value);
 420         Py_DECREF(old_key);
 421         return 0;
 422 }
 423
 424 void
 425 PyDict_Clear(op)
 426         PyObject *op;
 427 {
 428         int i, n;
 429         register dictentry *table;
 430         dictobject *mp;
 431         if (!PyDict_Check(op))
 432                 return;
 433         mp = (dictobject *)op;
 434         table = mp->ma_table;
 435         if (table == NULL)
 436                 return;
 437         n = mp->ma_size;
 438         mp->ma_size = mp->ma_used = mp->ma_fill = 0;
 439         mp->ma_table = NULL;
 440         for (i = 0; i < n; i++) {
 441                 Py_XDECREF(table[i].me_key);
 442                 Py_XDECREF(table[i].me_value);
 443         }
 444         PyMem_DEL(table);
 445 }
 446
 447 int
 448 PyDict_Next(op, ppos, pkey, pvalue)
 449         PyObject *op;
 450         int *ppos;
 451         PyObject **pkey;
 452         PyObject **pvalue;
 453 {
 454         int i;
 455         register dictobject *mp;
 456         if (!PyDict_Check(op))
 457                 return 0;
 458         mp = (dictobject *)op;
 459         i = *ppos;
 460         if (i < 0)
 461                 return 0;
 462         while (i < mp->ma_size && mp->ma_table[i].me_value == NULL)
 463                 i++;
 464         *ppos = i+1;
 465         if (i >= mp->ma_size)
 466                 return 0;
 467         if (pkey)
 468                 *pkey = mp->ma_table[i].me_key;
 469         if (pvalue)
 470                 *pvalue = mp->ma_table[i].me_value;
 471         return 1;
 472 }
 473
 474 /* Methods */
 475
 476 static void
 477 dict_dealloc(mp)
 478         register dictobject *mp;
 479 {
 480         register int i;
 481         register dictentry *ep;
 482         for (i = 0, ep = mp->ma_table; i < mp->ma_size; i++, ep++) {
 483                 if (ep->me_key != NULL) {
 484                         Py_DECREF(ep->me_key);
 485                 }
 486                 if (ep->me_value != NULL) {
 487                         Py_DECREF(ep->me_value);
 488                 }
 489         }
 490         PyMem_XDEL(mp->ma_table);
 491         PyMem_DEL(mp);
 492 }
 493
 494 static int
 495 dict_print(mp, fp, flags)
 496         register dictobject *mp;
 497         register FILE *fp;
 498         register int flags;
 499 {
 500         register int i;
 501         register int any;
 502         register dictentry *ep;
 503
 504         i = Py_ReprEnter((PyObject*)mp);
 505         if (i != 0) {
 506                 if (i < 0)
 507                         return i;
 508                 fprintf(fp, "{...}");
 509                 return 0;
 510         }
 511
 512         fprintf(fp, "{");
 513         any = 0;
 514         for (i = 0, ep = mp->ma_table; i < mp->ma_size; i++, ep++) {
 515                 if (ep->me_value != NULL) {
 516                         if (any++ > 0)
 517                                 fprintf(fp, ", ");
 518                         if (PyObject_Print((PyObject *)ep->me_key, fp, 0)!=0) {
 519                                 Py_ReprLeave((PyObject*)mp);
 520                                 return -1;
 521                         }
 522                         fprintf(fp, ": ");
 523                         if (PyObject_Print(ep->me_value, fp, 0) != 0) {
 524                                 Py_ReprLeave((PyObject*)mp);
 525                                 return -1;
 526                         }
 527                 }
 528         }
 529         fprintf(fp, "}");
 530         Py_ReprLeave((PyObject*)mp);
 531         return 0;
 532 }
 533
 534 static PyObject *
 535 dict_repr(mp)
 536         dictobject *mp;
 537 {
 538         auto PyObject *v;
 539         PyObject *sepa, *colon;
 540         register int i;
 541         register int any;
 542         register dictentry *ep;
 543
 544         i = Py_ReprEnter((PyObject*)mp);
 545         if (i != 0) {
 546                 if (i > 0)
 547                         return PyString_FromString("{...}");
 548                 return NULL;
 549         }
 550
 551         v = PyString_FromString("{");
 552         sepa = PyString_FromString(", ");
 553         colon = PyString_FromString(": ");
 554         any = 0;
 555         for (i = 0, ep = mp->ma_table; i < mp->ma_size && v; i++, ep++) {
 556                 if (ep->me_value != NULL) {
 557                         if (any++)
 558                                 PyString_Concat(&v, sepa);
 559                         PyString_ConcatAndDel(&v, PyObject_Repr(ep->me_key));
 560                         PyString_Concat(&v, colon);
 561                         PyString_ConcatAndDel(&v, PyObject_Repr(ep->me_value));
 562                 }
 563         }
 564         PyString_ConcatAndDel(&v, PyString_FromString("}"));
 565         Py_ReprLeave((PyObject*)mp);
 566         Py_XDECREF(sepa);
 567         Py_XDECREF(colon);
 568         return v;
 569 }
 570
 571 static int
 572 dict_length(mp)
 573         dictobject *mp;
 574 {
 575         return mp->ma_used;
 576 }
 577
 578 static PyObject *
 579 dict_subscript(mp, key)
 580         dictobject *mp;
 581         register PyObject *key;
 582 {
 583         PyObject *v;
 584         long hash;
 585         if (mp->ma_table == NULL) {
 586                 PyErr_SetObject(PyExc_KeyError, key);
 587                 return NULL;
 588         }
 589 #ifdef CACHE_HASH
 590         if (!PyString_Check(key) ||
 591             (hash = ((PyStringObject *) key)->ob_shash) == -1)
 592 #endif
 593         {
 594                 hash = PyObject_Hash(key);
 595                 if (hash == -1)
 596                         return NULL;
 597         }
 598         v = lookdict(mp, key, hash) -> me_value;
 599         if (v == NULL)
 600                 PyErr_SetObject(PyExc_KeyError, key);
 601         else
 602                 Py_INCREF(v);
 603         return v;
 604 }
 605
 606 static int
 607 dict_ass_sub(mp, v, w)
 608         dictobject *mp;
 609         PyObject *v, *w;
 610 {
 611         if (w == NULL)
 612                 return PyDict_DelItem((PyObject *)mp, v);
 613         else
 614                 return PyDict_SetItem((PyObject *)mp, v, w);
 615 }
 616
 617 static PyMappingMethods dict_as_mapping = {
 618         (inquiry)dict_length, /*mp_length*/
 619         (binaryfunc)dict_subscript, /*mp_subscript*/
 620         (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
 621 };
 622
 623 static PyObject *
 624 dict_keys(mp, args)
 625         register dictobject *mp;
 626         PyObject *args;
 627 {
 628         register PyObject *v;
 629         register int i, j;
 630         if (!PyArg_NoArgs(args))
 631                 return NULL;
 632         v = PyList_New(mp->ma_used);
 633         if (v == NULL)
 634                 return NULL;
 635         for (i = 0, j = 0; i < mp->ma_size; i++) {
 636                 if (mp->ma_table[i].me_value != NULL) {
 637                         PyObject *key = mp->ma_table[i].me_key;
 638                         Py_INCREF(key);
 639                         PyList_SetItem(v, j, key);
 640                         j++;
 641                 }
 642         }
 643         return v;
 644 }
 645
 646 static PyObject *
 647 dict_values(mp, args)
 648         register dictobject *mp;
 649         PyObject *args;
 650 {
 651         register PyObject *v;
 652         register int i, j;
 653         if (!PyArg_NoArgs(args))
 654                 return NULL;
 655         v = PyList_New(mp->ma_used);
 656         if (v == NULL)
 657                 return NULL;
 658         for (i = 0, j = 0; i < mp->ma_size; i++) {
 659                 if (mp->ma_table[i].me_value != NULL) {
 660                         PyObject *value = mp->ma_table[i].me_value;
 661                         Py_INCREF(value);
 662                         PyList_SetItem(v, j, value);
 663                         j++;
 664                 }
 665         }
 666         return v;
 667 }
 668
 669 static PyObject *
 670 dict_items(mp, args)
 671         register dictobject *mp;
 672         PyObject *args;
 673 {
 674         register PyObject *v;
 675         register int i, j;
 676         if (!PyArg_NoArgs(args))
 677                 return NULL;
 678         v = PyList_New(mp->ma_used);
 679         if (v == NULL)
 680                 return NULL;
 681         for (i = 0, j = 0; i < mp->ma_size; i++) {
 682                 if (mp->ma_table[i].me_value != NULL) {
 683                         PyObject *key = mp->ma_table[i].me_key;
 684                         PyObject *value = mp->ma_table[i].me_value;
 685                         PyObject *item = PyTuple_New(2);
 686                         if (item == NULL) {
 687                                 Py_DECREF(v);
 688                                 return NULL;
 689                         }
 690                         Py_INCREF(key);
 691                         PyTuple_SetItem(item, 0, key);
 692                         Py_INCREF(value);
 693                         PyTuple_SetItem(item, 1, value);
 694                         PyList_SetItem(v, j, item);
 695                         j++;
 696                 }
 697         }
 698         return v;
 699 }
 700
 701 static PyObject *
 702 dict_update(mp, args)
 703       register dictobject *mp;
 704       PyObject *args;
 705 {
 706         register int i;
 707         dictobject *other;
 708         dictentry *entry;
 709         if (!PyArg_Parse(args, "O!", &PyDict_Type, &other))
 710                 return NULL;
 711         if (other == mp)
 712                 goto done; /* a.update(a); nothing to do */
 713         /* Do one big resize at the start, rather than incrementally
 714            resizing as we insert new items.  Expect that there will be
 715            no (or few) overlapping keys. */
 716         if ((mp->ma_fill + other->ma_used)*3 >= mp->ma_size*2) {
 717                 if (dictresize(mp, (mp->ma_used + other->ma_used)*3/2) != 0)
 718                         return NULL;
 719         }
 720         for (i = 0; i < other->ma_size; i++) {
 721                 entry = &other->ma_table[i];
 722                 if (entry->me_value != NULL) {
 723                         Py_INCREF(entry->me_key);
 724                         Py_INCREF(entry->me_value);
 725                         insertdict(mp, entry->me_key, entry->me_hash,
 726                                    entry->me_value);
 727                 }
 728         }
 729   done:
 730         Py_INCREF(Py_None);
 731         return Py_None;
 732 }
 733
 734 static PyObject *
 735 dict_copy(mp, args)
 736       register dictobject *mp;
 737       PyObject *args;
 738 {
 739         register int i;
 740         dictobject *copy;
 741         dictentry *entry;
 742         if (!PyArg_Parse(args, ""))
 743                 return NULL;
 744         copy = (dictobject *)PyDict_New();
 745         if (copy == NULL)
 746                 return NULL;
 747         if (mp->ma_used > 0) {
 748                 if (dictresize(copy, mp->ma_used*3/2) != 0)
 749                         return NULL;
 750                 for (i = 0; i < mp->ma_size; i++) {
 751                         entry = &mp->ma_table[i];
 752                         if (entry->me_value != NULL) {
 753                                 Py_INCREF(entry->me_key);
 754                                 Py_INCREF(entry->me_value);
 755                                 insertdict(copy, entry->me_key, entry->me_hash,
 756                                            entry->me_value);
 757                         }
 758                 }
 759         }
 760         return (PyObject *)copy;
 761 }
 762
 763 int
 764 PyDict_Size(mp)
 765         PyObject *mp;
 766 {
 767         if (mp == NULL || !PyDict_Check(mp)) {
 768                 PyErr_BadInternalCall();
 769                 return 0;
 770         }
 771         return ((dictobject *)mp)->ma_used;
 772 }
 773
 774 PyObject *
 775 PyDict_Keys(mp)
 776         PyObject *mp;
 777 {
 778         if (mp == NULL || !PyDict_Check(mp)) {
 779                 PyErr_BadInternalCall();
 780                 return NULL;
 781         }
 782         return dict_keys((dictobject *)mp, (PyObject *)NULL);
 783 }
 784
 785 PyObject *
 786 PyDict_Values(mp)
 787         PyObject *mp;
 788 {
 789         if (mp == NULL || !PyDict_Check(mp)) {
 790                 PyErr_BadInternalCall();
 791                 return NULL;
 792         }
 793         return dict_values((dictobject *)mp, (PyObject *)NULL);
 794 }
 795
 796 PyObject *
 797 PyDict_Items(mp)
 798         PyObject *mp;
 799 {
 800         if (mp == NULL || !PyDict_Check(mp)) {
 801                 PyErr_BadInternalCall();
 802                 return NULL;
 803         }
 804         return dict_items((dictobject *)mp, (PyObject *)NULL);
 805 }
 806
 807 #define NEWCMP
 808
 809 #ifdef NEWCMP
 810
 811 /* Subroutine which returns the smallest key in a for which b's value
 812    is different or absent.  The value is returned too, through the
 813    pval argument.  No reference counts are incremented. */
 814
 815 static PyObject *
 816 characterize(a, b, pval)
 817         dictobject *a;
 818         dictobject *b;
 819         PyObject **pval;
 820 {
 821         PyObject *diff = NULL;
 822         int i;
 823
 824         *pval = NULL;
 825         for (i = 0; i < a->ma_size; i++) {
 826                 if (a->ma_table[i].me_value != NULL) {
 827                         PyObject *key = a->ma_table[i].me_key;
 828                         PyObject *aval, *bval;
 829                         /* XXX What if PyObject_Compare raises an exception? */
 830                         if (diff != NULL && PyObject_Compare(key, diff) > 0)
 831                                 continue;
 832                         aval = a->ma_table[i].me_value;
 833                         bval = PyDict_GetItem((PyObject *)b, key);
 834                         /* XXX What if PyObject_Compare raises an exception? */
 835                         if (bval == NULL || PyObject_Compare(aval, bval) != 0)
 836                         {
 837                                 diff = key;
 838                                 *pval = aval;
 839                         }
 840                 }
 841         }
 842         return diff;
 843 }
 844
 845 static int
 846 dict_compare(a, b)
 847         dictobject *a, *b;
 848 {
 849         PyObject *adiff, *bdiff, *aval, *bval;
 850         int res;
 851
 852         /* Compare lengths first */
 853         if (a->ma_used < b->ma_used)
 854                 return -1;      /* a is shorter */
 855         else if (a->ma_used > b->ma_used)
 856                 return 1;       /* b is shorter */
 857         /* Same length -- check all keys */
 858         adiff = characterize(a, b, &aval);
 859         if (PyErr_Occurred())
 860                 return -1;
 861         if (adiff == NULL)
 862                 return 0;       /* a is a subset with the same length */
 863         bdiff = characterize(b, a, &bval);
 864         if (PyErr_Occurred())
 865                 return -1;
 866         /* bdiff == NULL would be impossible now */
 867         res = PyObject_Compare(adiff, bdiff);
 868         if (res == 0)
 869                 res = PyObject_Compare(aval, bval);
 870         return res;
 871 }
 872
 873 #else /* !NEWCMP */
 874
 875 static int
 876 dict_compare(a, b)
 877         dictobject *a, *b;
 878 {
 879         PyObject *akeys, *bkeys;
 880         int i, n, res;
 881         if (a == b)
 882                 return 0;
 883         if (a->ma_used == 0) {
 884                 if (b->ma_used != 0)
 885                         return -1;
 886                 else
 887                         return 0;
 888         }
 889         else {
 890                 if (b->ma_used == 0)
 891                         return 1;
 892         }
 893         akeys = dict_keys(a, (PyObject *)NULL);
 894         bkeys = dict_keys(b, (PyObject *)NULL);
 895         if (akeys == NULL || bkeys == NULL) {
 896                 /* Oops, out of memory -- what to do? */
 897                 /* For now, sort on address! */
 898                 Py_XDECREF(akeys);
 899                 Py_XDECREF(bkeys);
 900                 if (a < b)
 901                         return -1;
 902                 else
 903                         return 1;
 904         }
 905         PyList_Sort(akeys);
 906         PyList_Sort(bkeys);
 907         n = a->ma_used < b->ma_used ? a->ma_used : b->ma_used; /* smallest */
 908         res = 0;
 909         for (i = 0; i < n; i++) {
 910                 PyObject *akey, *bkey, *aval, *bval;
 911                 long ahash, bhash;
 912                 akey = PyList_GetItem(akeys, i);
 913                 bkey = PyList_GetItem(bkeys, i);
 914                 res = PyObject_Compare(akey, bkey);
 915                 if (res != 0)
 916                         break;
 917 #ifdef CACHE_HASH
 918                 if (!PyString_Check(akey) ||
 919                     (ahash = ((PyStringObject *) akey)->ob_shash) == -1)
 920 #endif
 921                 {
 922                         ahash = PyObject_Hash(akey);
 923                         if (ahash == -1)
 924                                 PyErr_Clear(); /* Don't want errors here */
 925                 }
 926 #ifdef CACHE_HASH
 927                 if (!PyString_Check(bkey) ||
 928                     (bhash = ((PyStringObject *) bkey)->ob_shash) == -1)
 929 #endif
 930                 {
 931                         bhash = PyObject_Hash(bkey);
 932                         if (bhash == -1)
 933                                 PyErr_Clear(); /* Don't want errors here */
 934                 }
 935                 aval = lookdict(a, akey, ahash) -> me_value;
 936                 bval = lookdict(b, bkey, bhash) -> me_value;
 937                 res = PyObject_Compare(aval, bval);
 938                 if (res != 0)
 939                         break;
 940         }
 941         if (res == 0) {
 942                 if (a->ma_used < b->ma_used)
 943                         res = -1;
 944                 else if (a->ma_used > b->ma_used)
 945                         res = 1;
 946         }
 947         Py_DECREF(akeys);
 948         Py_DECREF(bkeys);
 949         return res;
 950 }
 951
 952 #endif /* !NEWCMP */
 953
 954 static PyObject *
 955 dict_has_key(mp, args)
 956         register dictobject *mp;
 957         PyObject *args;
 958 {
 959         PyObject *key;
 960         long hash;
 961         register long ok;
 962         if (!PyArg_Parse(args, "O", &key))
 963                 return NULL;
 964 #ifdef CACHE_HASH
 965         if (!PyString_Check(key) ||
 966             (hash = ((PyStringObject *) key)->ob_shash) == -1)
 967 #endif
 968         {
 969                 hash = PyObject_Hash(key);
 970                 if (hash == -1)
 971                         return NULL;
 972         }
 973         ok = mp->ma_size != 0 && lookdict(mp, key, hash)->me_value != NULL;
 974         return PyInt_FromLong(ok);
 975 }
 976
 977 static PyObject *
 978 dict_get(mp, args)
 979         register dictobject *mp;
 980         PyObject *args;
 981 {
 982         PyObject *key;
 983         PyObject *failobj = Py_None;
 984         PyObject *val = NULL;
 985         long hash;
 986
 987         if (!PyArg_ParseTuple(args, "O|O", &key, &failobj))
 988                 return NULL;
 989         if (mp->ma_table == NULL)
 990                 goto finally;
 991
 992 #ifdef CACHE_HASH
 993         if (!PyString_Check(key) ||
 994             (hash = ((PyStringObject *) key)->ob_shash) == -1)
 995 #endif
 996         {
 997                 hash = PyObject_Hash(key);
 998                 if (hash == -1)
 999                         return NULL;
1000         }
1001         val = lookdict(mp, key, hash)->me_value;
1002
1003   finally:
1004         if (val == NULL)
1005                 val = failobj;
1006         Py_INCREF(val);
1007         return val;
1008 }
1009
1010
1011 static PyObject *
1012 dict_clear(mp, args)
1013         register dictobject *mp;
1014         PyObject *args;
1015 {
1016         if (!PyArg_NoArgs(args))
1017                 return NULL;
1018         PyDict_Clear((PyObject *)mp);
1019         Py_INCREF(Py_None);
1020         return Py_None;
1021 }
1022
1023 static PyMethodDef mapp_methods[] = {
1024         {"has_key",     (PyCFunction)dict_has_key},
1025         {"keys",        (PyCFunction)dict_keys},
1026         {"items",       (PyCFunction)dict_items},
1027         {"values",      (PyCFunction)dict_values},
1028         {"update",      (PyCFunction)dict_update},
1029         {"clear",       (PyCFunction)dict_clear},
1030         {"copy",        (PyCFunction)dict_copy},
1031         {"get",         (PyCFunction)dict_get, 1},
1032         {NULL,          NULL}           /* sentinel */
1033 };
1034
1035 static PyObject *
1036 dict_getattr(mp, name)
1037         dictobject *mp;
1038         char *name;
1039 {
1040         return Py_FindMethod(mapp_methods, (PyObject *)mp, name);
1041 }
1042
1043 PyTypeObject PyDict_Type = {
1044         PyObject_HEAD_INIT(&PyType_Type)
1045         0,
1046         "dictionary",
1047         sizeof(dictobject),
1048         0,
1049         (destructor)dict_dealloc, /*tp_dealloc*/
1050         (printfunc)dict_print, /*tp_print*/
1051         (getattrfunc)dict_getattr, /*tp_getattr*/
1052         0,                      /*tp_setattr*/
1053         (cmpfunc)dict_compare, /*tp_compare*/
1054         (reprfunc)dict_repr, /*tp_repr*/
1055         0,                      /*tp_as_number*/
1056         0,                      /*tp_as_sequence*/
1057         &dict_as_mapping,       /*tp_as_mapping*/
1058 };
1059
1060 /* For backward compatibility with old dictionary interface */
1061
1062 PyObject *
1063 PyDict_GetItemString(v, key)
1064         PyObject *v;
1065         char *key;
1066 {
1067         PyObject *kv, *rv;
1068         kv = PyString_FromString(key);
1069         if (kv == NULL)
1070                 return NULL;
1071         rv = PyDict_GetItem(v, kv);
1072         Py_DECREF(kv);
1073         return rv;
1074 }
1075
1076 int
1077 PyDict_SetItemString(v, key, item)
1078         PyObject *v;
1079         char *key;
1080         PyObject *item;
1081 {
1082         PyObject *kv;
1083         int err;
1084         kv = PyString_FromString(key);
1085         if (kv == NULL)
1086                 return -1;
1087         PyString_InternInPlace(&kv); /* XXX Should we really? */
1088         err = PyDict_SetItem(v, kv, item);
1089         Py_DECREF(kv);
1090         return err;
1091 }
1092
1093 int
1094 PyDict_DelItemString(v, key)
1095         PyObject *v;
1096         char *key;
1097 {
1098         PyObject *kv;
1099         int err;
1100         kv = PyString_FromString(key);
1101         if (kv == NULL)
1102                 return -1;
1103         err = PyDict_DelItem(v, kv);
1104         Py_DECREF(kv);
1105         return err;
1106 }