Objects/dictobject.c

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