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 not be used in advertising or publicity pertaining to
  13 distribution of the software without specific, written prior permission.
  14
  15 STICHTING MATHEMATISCH CENTRUM DISCLAIMS ALL WARRANTIES WITH REGARD TO
  16 THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  17 FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH CENTRUM BE LIABLE
  18 FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  19 WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  20 ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
  21 OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  22
  23 ******************************************************************/
  24
  25 /* Mapping object implementation; using a hash table */
  26
  27 /* This file should really be called "dictobject.c", since "mapping"
  28   is the generic name for objects with an unorderred arbitrary key
  29   set (just like lists are sequences), but since it improves (and was
  30   originally derived from) a file by that name I had to change its
  31   name.  For the user these objects are still called "dictionaries". */
  32
  33 #include "allobjects.h"
  34 #include "modsupport.h"
  35
  36
  37 /*
  38 Table of primes suitable as keys, in ascending order.
  39 The first line are the largest primes less than some powers of two,
  40 the second line is the largest prime less than 6000,
  41 the third line is a selection from Knuth, Vol. 3, Sec. 6.1, Table 1,
  42 and the next three lines were suggested by Steve Kirsch.
  43 The final value is a sentinel.
  44 */
  45 static long primes[] = {
  46         3, 7, 13, 31, 61, 127, 251, 509, 1021, 2017, 4093,
  47         5987,
  48         9551, 15683, 19609, 31397,
  49         65521L, 131071L, 262139L, 524287L, 1048573L, 2097143L,
  50         4194301L, 8388593L, 16777213L, 33554393L, 67108859L,
  51         134217689L, 268435399L, 536870909L, 1073741789L,
  52         0
  53 };
  54
  55 /* Object used as dummy key to fill deleted entries */
  56 static object *dummy; /* Initialized by first call to newmappingobject() */
  57
  58 /*
  59 Invariant for entries: when in use, de_value is not NULL and de_key is
  60 not NULL and not dummy; when not in use, de_value is NULL and de_key
  61 is either NULL or dummy.  A dummy key value cannot be replaced by
  62 NULL, since otherwise other keys may be lost.
  63 */
  64 typedef struct {
  65         long me_hash;
  66         object *me_key;
  67         object *me_value;
  68 } mappingentry;
  69
  70 /*
  71 To ensure the lookup algorithm terminates, the table size must be a
  72 prime number and there must be at least one NULL key in the table.
  73 The value ma_fill is the number of non-NULL keys; ma_used is the number
  74 of non-NULL, non-dummy keys.
  75 To avoid slowing down lookups on a near-full table, we resize the table
  76 when it is more than half filled.
  77 */
  78 typedef struct {
  79         OB_HEAD
  80         int ma_fill;
  81         int ma_used;
  82         int ma_size;
  83         mappingentry *ma_table;
  84 } mappingobject;
  85
  86 object *
  87 newmappingobject()
  88 {
  89         register mappingobject *mp;
  90         if (dummy == NULL) { /* Auto-initialize dummy */
  91                 dummy = newstringobject("<dummy key>");
  92                 if (dummy == NULL)
  93                         return NULL;
  94         }
  95         mp = NEWOBJ(mappingobject, &Mappingtype);
  96         if (mp == NULL)
  97                 return NULL;
  98         mp->ma_size = 0;
  99         mp->ma_table = NULL;
 100         mp->ma_fill = 0;
 101         mp->ma_used = 0;
 102         return (object *)mp;
 103 }
 104
 105 /*
 106 The basic lookup function used by all operations.
 107 This is essentially Algorithm D from Knuth Vol. 3, Sec. 6.4.
 108 Open addressing is preferred over chaining since the link overhead for
 109 chaining would be substantial (100% with typical malloc overhead).
 110
 111 First a 32-bit hash value, 'sum', is computed from the key string.
 112 The first character is added an extra time shifted by 8 to avoid hashing
 113 single-character keys (often heavily used variables) too close together.
 114 All arithmetic on sum should ignore overflow.
 115
 116 The initial probe index is then computed as sum mod the table size.
 117 Subsequent probe indices are incr apart (mod table size), where incr
 118 is also derived from sum, with the additional requirement that it is
 119 relative prime to the table size (i.e., 1 <= incr < size, since the size
 120 is a prime number).  My choice for incr is somewhat arbitrary.
 121 */
 122 static mappingentry *lookmapping PROTO((mappingobject *, object *, long));
 123 static mappingentry *
 124 lookmapping(mp, key, hash)
 125         register mappingobject *mp;
 126         object *key;
 127         long hash;
 128 {
 129         register int i, incr;
 130         register unsigned long sum = (unsigned long) hash;
 131         register mappingentry *freeslot = NULL;
 132         /* We must come up with (i, incr) such that 0 <= i < ma_size
 133            and 0 < incr < ma_size and both are a function of hash */
 134         i = sum % mp->ma_size;
 135         do {
 136                 sum = 3*sum + 1;
 137                 incr = sum % mp->ma_size;
 138         } while (incr == 0);
 139         for (;;) {
 140                 register mappingentry *ep = &mp->ma_table[i];
 141                 if (ep->me_key == NULL) {
 142                         if (freeslot != NULL)
 143                                 return freeslot;
 144                         else
 145                                 return ep;
 146                 }
 147                 if (ep->me_key == dummy) {
 148                         if (freeslot == NULL)
 149                                 freeslot = ep;
 150                 }
 151                 else if (ep->me_hash == hash &&
 152                          cmpobject(ep->me_key, key) == 0) {
 153                         return ep;
 154                 }
 155                 i = (i + incr) % mp->ma_size;
 156         }
 157 }
 158
 159 /*
 160 Internal routine to insert a new item into the table.
 161 Used both by the internal resize routine and by the public insert routine.
 162 Eats a reference to key and one to value.
 163 */
 164 static void insertmapping PROTO((mappingobject *, object *, long, object *));
 165 static void
 166 insertmapping(mp, key, hash, value)
 167         register mappingobject *mp;
 168         object *key;
 169         long hash;
 170         object *value;
 171 {
 172         object *old_value;
 173         register mappingentry *ep;
 174         ep = lookmapping(mp, key, hash);
 175         if (ep->me_value != NULL) {
 176                 old_value = ep->me_value;
 177                 ep->me_value = value;
 178                 DECREF(old_value); /* which **CAN** re-enter */
 179                 DECREF(key);
 180         }
 181         else {
 182                 if (ep->me_key == NULL)
 183                         mp->ma_fill++;
 184                 else
 185                         DECREF(ep->me_key);
 186                 ep->me_key = key;
 187                 ep->me_hash = hash;
 188                 ep->me_value = value;
 189                 mp->ma_used++;
 190         }
 191 }
 192
 193 /*
 194 Restructure the table by allocating a new table and reinserting all
 195 items again.  When entries have been deleted, the new table may
 196 actually be smaller than the old one.
 197 */
 198 static int mappingresize PROTO((mappingobject *));
 199 static int
 200 mappingresize(mp)
 201         mappingobject *mp;
 202 {
 203         register int oldsize = mp->ma_size;
 204         register int newsize;
 205         register mappingentry *oldtable = mp->ma_table;
 206         register mappingentry *newtable;
 207         register mappingentry *ep;
 208         register int i;
 209         newsize = mp->ma_size;
 210         for (i = 0; ; i++) {
 211                 if (primes[i] <= 0) {
 212                         /* Ran out of primes */
 213                         err_nomem();
 214                         return -1;
 215                 }
 216                 if (primes[i] > mp->ma_used*2) {
 217                         newsize = primes[i];
 218                         if (newsize != primes[i]) {
 219                                 /* Integer truncation */
 220                                 err_nomem();
 221                                 return -1;
 222                         }
 223                         break;
 224                 }
 225         }
 226         newtable = (mappingentry *) calloc(sizeof(mappingentry), newsize);
 227         if (newtable == NULL) {
 228                 err_nomem();
 229                 return -1;
 230         }
 231         mp->ma_size = newsize;
 232         mp->ma_table = newtable;
 233         mp->ma_fill = 0;
 234         mp->ma_used = 0;
 235
 236         /* Make two passes, so we can avoid decrefs
 237            (and possible side effects) till the table is copied */
 238         for (i = 0, ep = oldtable; i < oldsize; i++, ep++) {
 239                 if (ep->me_value != NULL)
 240                         insertmapping(mp,ep->me_key,ep->me_hash,ep->me_value);
 241         }
 242         for (i = 0, ep = oldtable; i < oldsize; i++, ep++) {
 243                 if (ep->me_value == NULL)
 244                         XDECREF(ep->me_key);
 245         }
 246
 247         XDEL(oldtable);
 248         return 0;
 249 }
 250
 251 object *
 252 mappinglookup(op, key)
 253         object *op;
 254         object *key;
 255 {
 256         long hash;
 257         if (!is_mappingobject(op)) {
 258                 err_badcall();
 259                 return NULL;
 260         }
 261         if (((mappingobject *)op)->ma_table == NULL)
 262                 return NULL;
 263 #ifdef CACHE_HASH
 264         if (!is_stringobject(key) || (hash = ((stringobject *) key)->ob_shash) == -1)
 265 #endif
 266         hash = hashobject(key);
 267         if (hash == -1)
 268                 return NULL;
 269         return lookmapping((mappingobject *)op, key, hash) -> me_value;
 270 }
 271
 272 int
 273 mappinginsert(op, key, value)
 274         register object *op;
 275         object *key;
 276         object *value;
 277 {
 278         register mappingobject *mp;
 279         register long hash;
 280         if (!is_mappingobject(op)) {
 281                 err_badcall();
 282                 return -1;
 283         }
 284 #ifdef CACHE_HASH
 285         if (!is_stringobject(key) || (hash = ((stringobject *) key)->ob_shash) == -1)
 286 #endif
 287         hash = hashobject(key);
 288         if (hash == -1)
 289                 return -1;
 290         mp = (mappingobject *)op;
 291         /* if fill >= 2/3 size, resize */
 292         if (mp->ma_fill*3 >= mp->ma_size*2) {
 293                 if (mappingresize(mp) != 0) {
 294                         if (mp->ma_fill+1 > mp->ma_size)
 295                                 return -1;
 296                 }
 297         }
 298         INCREF(value);
 299         INCREF(key);
 300         insertmapping(mp, key, hash, value);
 301         return 0;
 302 }
 303
 304 int
 305 mappingremove(op, key)
 306         object *op;
 307         object *key;
 308 {
 309         register mappingobject *mp;
 310         register long hash;
 311         register mappingentry *ep;
 312         object *old_value, *old_key;
 313
 314         if (!is_mappingobject(op)) {
 315                 err_badcall();
 316                 return -1;
 317         }
 318 #ifdef CACHE_HASH
 319         if (!is_stringobject(key) || (hash = ((stringobject *) key)->ob_shash) == -1)
 320 #endif
 321         hash = hashobject(key);
 322         if (hash == -1)
 323                 return -1;
 324         mp = (mappingobject *)op;
 325         if (((mappingobject *)op)->ma_table == NULL)
 326                 goto empty;
 327         ep = lookmapping(mp, key, hash);
 328         if (ep->me_value == NULL) {
 329         empty:
 330                 err_setval(KeyError, key);
 331                 return -1;
 332         }
 333         old_key = ep->me_key;
 334         INCREF(dummy);
 335         ep->me_key = dummy;
 336         old_value = ep->me_value;
 337         ep->me_value = NULL;
 338         mp->ma_used--;
 339         DECREF(old_value);
 340         DECREF(old_key);
 341         return 0;
 342 }
 343
 344 void
 345 mappingclear(op)
 346         object *op;
 347 {
 348         int i, n;
 349         register mappingentry *table;
 350         mappingobject *mp;
 351         if (!is_mappingobject(op))
 352                 return;
 353         mp = (mappingobject *)op;
 354         table = mp->ma_table;
 355         if (table == NULL)
 356                 return;
 357         n = mp->ma_size;
 358         mp->ma_size = mp->ma_used = mp->ma_fill = 0;
 359         mp->ma_table = NULL;
 360         for (i = 0; i < n; i++) {
 361                 XDECREF(table[i].me_key);
 362                 XDECREF(table[i].me_value);
 363         }
 364         DEL(table);
 365 }
 366
 367 int
 368 mappinggetnext(op, ppos, pkey, pvalue)
 369         object *op;
 370         int *ppos;
 371         object **pkey;
 372         object **pvalue;
 373 {
 374         int i;
 375         register mappingobject *mp;
 376         if (!is_dictobject(op))
 377                 return 0;
 378         mp = (mappingobject *)op;
 379         i = *ppos;
 380         if (i < 0)
 381                 return 0;
 382         while (i < mp->ma_size && mp->ma_table[i].me_value == NULL)
 383                 i++;
 384         *ppos = i+1;
 385         if (i >= mp->ma_size)
 386                 return 0;
 387         if (pkey)
 388                 *pkey = mp->ma_table[i].me_key;
 389         if (pvalue)
 390                 *pvalue = mp->ma_table[i].me_value;
 391         return 1;
 392 }
 393
 394 /* Methods */
 395
 396 static void
 397 mapping_dealloc(mp)
 398         register mappingobject *mp;
 399 {
 400         register int i;
 401         register mappingentry *ep;
 402         for (i = 0, ep = mp->ma_table; i < mp->ma_size; i++, ep++) {
 403                 if (ep->me_key != NULL)
 404                         DECREF(ep->me_key);
 405                 if (ep->me_value != NULL)
 406                         DECREF(ep->me_value);
 407         }
 408         XDEL(mp->ma_table);
 409         DEL(mp);
 410 }
 411
 412 static int
 413 mapping_print(mp, fp, flags)
 414         register mappingobject *mp;
 415         register FILE *fp;
 416         register int flags;
 417 {
 418         register int i;
 419         register int any;
 420         register mappingentry *ep;
 421         fprintf(fp, "{");
 422         any = 0;
 423         for (i = 0, ep = mp->ma_table; i < mp->ma_size; i++, ep++) {
 424                 if (ep->me_value != NULL) {
 425                         if (any++ > 0)
 426                                 fprintf(fp, ", ");
 427                         if (printobject((object *)ep->me_key, fp, 0) != 0)
 428                                 return -1;
 429                         fprintf(fp, ": ");
 430                         if (printobject(ep->me_value, fp, 0) != 0)
 431                                 return -1;
 432                 }
 433         }
 434         fprintf(fp, "}");
 435         return 0;
 436 }
 437
 438 static object *
 439 mapping_repr(mp)
 440         mappingobject *mp;
 441 {
 442         auto object *v;
 443         object *sepa, *colon;
 444         register int i;
 445         register int any;
 446         register mappingentry *ep;
 447         v = newstringobject("{");
 448         sepa = newstringobject(", ");
 449         colon = newstringobject(": ");
 450         any = 0;
 451         for (i = 0, ep = mp->ma_table; i < mp->ma_size && v; i++, ep++) {
 452                 if (ep->me_value != NULL) {
 453                         if (any++)
 454                                 joinstring(&v, sepa);
 455                         joinstring_decref(&v, reprobject(ep->me_key));
 456                         joinstring(&v, colon);
 457                         joinstring_decref(&v, reprobject(ep->me_value));
 458                 }
 459         }
 460         joinstring_decref(&v, newstringobject("}"));
 461         XDECREF(sepa);
 462         XDECREF(colon);
 463         return v;
 464 }
 465
 466 static int
 467 mapping_length(mp)
 468         mappingobject *mp;
 469 {
 470         return mp->ma_used;
 471 }
 472
 473 static object *
 474 mapping_subscript(mp, key)
 475         mappingobject *mp;
 476         register object *key;
 477 {
 478         object *v;
 479         long hash;
 480         if (mp->ma_table == NULL) {
 481                 err_setval(KeyError, key);
 482                 return NULL;
 483         }
 484 #ifdef CACHE_HASH
 485         if (!is_stringobject(key) || (hash = ((stringobject *) key)->ob_shash) == -1)
 486 #endif
 487         hash = hashobject(key);
 488         if (hash == -1)
 489                 return NULL;
 490         v = lookmapping(mp, key, hash) -> me_value;
 491         if (v == NULL)
 492                 err_setval(KeyError, key);
 493         else
 494                 INCREF(v);
 495         return v;
 496 }
 497
 498 static int
 499 mapping_ass_sub(mp, v, w)
 500         mappingobject *mp;
 501         object *v, *w;
 502 {
 503         if (w == NULL)
 504                 return mappingremove((object *)mp, v);
 505         else
 506                 return mappinginsert((object *)mp, v, w);
 507 }
 508
 509 static mapping_methods mapping_as_mapping = {
 510         (inquiry)mapping_length, /*mp_length*/
 511         (binaryfunc)mapping_subscript, /*mp_subscript*/
 512         (objobjargproc)mapping_ass_sub, /*mp_ass_subscript*/
 513 };
 514
 515 static object *
 516 mapping_keys(mp, args)
 517         register mappingobject *mp;
 518         object *args;
 519 {
 520         register object *v;
 521         register int i, j;
 522         if (!getnoarg(args))
 523                 return NULL;
 524         v = newlistobject(mp->ma_used);
 525         if (v == NULL)
 526                 return NULL;
 527         for (i = 0, j = 0; i < mp->ma_size; i++) {
 528                 if (mp->ma_table[i].me_value != NULL) {
 529                         object *key = mp->ma_table[i].me_key;
 530                         INCREF(key);
 531                         setlistitem(v, j, key);
 532                         j++;
 533                 }
 534         }
 535         return v;
 536 }
 537
 538 static object *
 539 mapping_values(mp, args)
 540         register mappingobject *mp;
 541         object *args;
 542 {
 543         register object *v;
 544         register int i, j;
 545         if (!getnoarg(args))
 546                 return NULL;
 547         v = newlistobject(mp->ma_used);
 548         if (v == NULL)
 549                 return NULL;
 550         for (i = 0, j = 0; i < mp->ma_size; i++) {
 551                 if (mp->ma_table[i].me_value != NULL) {
 552                         object *value = mp->ma_table[i].me_value;
 553                         INCREF(value);
 554                         setlistitem(v, j, value);
 555                         j++;
 556                 }
 557         }
 558         return v;
 559 }
 560
 561 static object *
 562 mapping_items(mp, args)
 563         register mappingobject *mp;
 564         object *args;
 565 {
 566         register object *v;
 567         register int i, j;
 568         if (!getnoarg(args))
 569                 return NULL;
 570         v = newlistobject(mp->ma_used);
 571         if (v == NULL)
 572                 return NULL;
 573         for (i = 0, j = 0; i < mp->ma_size; i++) {
 574                 if (mp->ma_table[i].me_value != NULL) {
 575                         object *key = mp->ma_table[i].me_key;
 576                         object *value = mp->ma_table[i].me_value;
 577                         object *item = newtupleobject(2);
 578                         if (item == NULL) {
 579                                 DECREF(v);
 580                                 return NULL;
 581                         }
 582                         INCREF(key);
 583                         settupleitem(item, 0, key);
 584                         INCREF(value);
 585                         settupleitem(item, 1, value);
 586                         setlistitem(v, j, item);
 587                         j++;
 588                 }
 589         }
 590         return v;
 591 }
 592
 593 int
 594 getmappingsize(mp)
 595         object *mp;
 596 {
 597         if (mp == NULL || !is_mappingobject(mp)) {
 598                 err_badcall();
 599                 return 0;
 600         }
 601         return ((mappingobject *)mp)->ma_used;
 602 }
 603
 604 object *
 605 getmappingkeys(mp)
 606         object *mp;
 607 {
 608         if (mp == NULL || !is_mappingobject(mp)) {
 609                 err_badcall();
 610                 return NULL;
 611         }
 612         return mapping_keys((mappingobject *)mp, (object *)NULL);
 613 }
 614
 615 object *
 616 getmappingvalues(mp)
 617         object *mp;
 618 {
 619         if (mp == NULL || !is_mappingobject(mp)) {
 620                 err_badcall();
 621                 return NULL;
 622         }
 623         return mapping_values((mappingobject *)mp, (object *)NULL);
 624 }
 625
 626 object *
 627 getmappingitems(mp)
 628         object *mp;
 629 {
 630         if (mp == NULL || !is_mappingobject(mp)) {
 631                 err_badcall();
 632                 return NULL;
 633         }
 634         return mapping_items((mappingobject *)mp, (object *)NULL);
 635 }
 636
 637 static int
 638 mapping_compare(a, b)
 639         mappingobject *a, *b;
 640 {
 641         object *akeys, *bkeys;
 642         int i, n, res;
 643         if (a == b)
 644                 return 0;
 645         if (a->ma_used == 0) {
 646                 if (b->ma_used != 0)
 647                         return -1;
 648                 else
 649                         return 0;
 650         }
 651         else {
 652                 if (b->ma_used == 0)
 653                         return 1;
 654         }
 655         akeys = mapping_keys(a, (object *)NULL);
 656         bkeys = mapping_keys(b, (object *)NULL);
 657         if (akeys == NULL || bkeys == NULL) {
 658                 /* Oops, out of memory -- what to do? */
 659                 /* For now, sort on address! */
 660                 XDECREF(akeys);
 661                 XDECREF(bkeys);
 662                 if (a < b)
 663                         return -1;
 664                 else
 665                         return 1;
 666         }
 667         sortlist(akeys);
 668         sortlist(bkeys);
 669         n = a->ma_used < b->ma_used ? a->ma_used : b->ma_used; /* smallest */
 670         res = 0;
 671         for (i = 0; i < n; i++) {
 672                 object *akey, *bkey, *aval, *bval;
 673                 long ahash, bhash;
 674                 akey = getlistitem(akeys, i);
 675                 bkey = getlistitem(bkeys, i);
 676                 res = cmpobject(akey, bkey);
 677                 if (res != 0)
 678                         break;
 679 #ifdef CACHE_HASH
 680                 if (!is_stringobject(akey) || (ahash = ((stringobject *) akey)->ob_shash) == -1)
 681 #endif
 682                 ahash = hashobject(akey);
 683                 if (ahash == -1)
 684                         err_clear(); /* Don't want errors here */
 685 #ifdef CACHE_HASH
 686                 if (!is_stringobject(bkey) || (bhash = ((stringobject *) bkey)->ob_shash) == -1)
 687 #endif
 688                 bhash = hashobject(bkey);
 689                 if (bhash == -1)
 690                         err_clear(); /* Don't want errors here */
 691                 aval = lookmapping(a, akey, ahash) -> me_value;
 692                 bval = lookmapping(b, bkey, bhash) -> me_value;
 693                 res = cmpobject(aval, bval);
 694                 if (res != 0)
 695                         break;
 696         }
 697         if (res == 0) {
 698                 if (a->ma_used < b->ma_used)
 699                         res = -1;
 700                 else if (a->ma_used > b->ma_used)
 701                         res = 1;
 702         }
 703         DECREF(akeys);
 704         DECREF(bkeys);
 705         return res;
 706 }
 707
 708 static object *
 709 mapping_has_key(mp, args)
 710         register mappingobject *mp;
 711         object *args;
 712 {
 713         object *key;
 714         long hash;
 715         register long ok;
 716         if (!getargs(args, "O", &key))
 717                 return NULL;
 718 #ifdef CACHE_HASH
 719         if (!is_stringobject(key) || (hash = ((stringobject *) key)->ob_shash) == -1)
 720 #endif
 721         hash = hashobject(key);
 722         if (hash == -1)
 723                 return NULL;
 724         ok = mp->ma_size != 0 && lookmapping(mp, key, hash)->me_value != NULL;
 725         return newintobject(ok);
 726 }
 727
 728 static struct methodlist mapp_methods[] = {
 729         {"has_key",     (method)mapping_has_key},
 730         {"items",       (method)mapping_items},
 731         {"keys",        (method)mapping_keys},
 732         {"values",      (method)mapping_values},
 733         {NULL,          NULL}           /* sentinel */
 734 };
 735
 736 static object *
 737 mapping_getattr(mp, name)
 738         mappingobject *mp;
 739         char *name;
 740 {
 741         return findmethod(mapp_methods, (object *)mp, name);
 742 }
 743
 744 typeobject Mappingtype = {
 745         OB_HEAD_INIT(&Typetype)
 746         0,
 747         "dictionary",
 748         sizeof(mappingobject),
 749         0,
 750         (destructor)mapping_dealloc, /*tp_dealloc*/
 751         (printfunc)mapping_print, /*tp_print*/
 752         (getattrfunc)mapping_getattr, /*tp_getattr*/
 753         0,                      /*tp_setattr*/
 754         (cmpfunc)mapping_compare, /*tp_compare*/
 755         (reprfunc)mapping_repr, /*tp_repr*/
 756         0,                      /*tp_as_number*/
 757         0,                      /*tp_as_sequence*/
 758         &mapping_as_mapping,    /*tp_as_mapping*/
 759 };
 760
 761 /* For backward compatibility with old dictionary interface */
 762
 763 static object *last_name_object;
 764 static char *last_name_char;
 765
 766 object *
 767 getattro(v, name)
 768         object *v;
 769         object *name;
 770 {
 771         if (name != last_name_object) {
 772                 XDECREF(last_name_object);
 773                 INCREF(name);
 774                 last_name_object = name;
 775                 last_name_char = getstringvalue(name);
 776         }
 777         return getattr(v, last_name_char);
 778 }
 779
 780 int
 781 setattro(v, name, value)
 782         object *v;
 783         object *name;
 784         object *value;
 785 {
 786         if (name != last_name_object) {
 787                 XDECREF(last_name_object);
 788                 INCREF(name);
 789                 last_name_object = name;
 790                 last_name_char = getstringvalue(name);
 791         }
 792         return setattr(v, last_name_char, value);
 793 }
 794
 795 object *
 796 dictlookup(v, key)
 797         object *v;
 798         char *key;
 799 {
 800         if (key != last_name_char ||
 801             strcmp(key, getstringvalue(last_name_object)) != 0) {
 802                 XDECREF(last_name_object);
 803                 last_name_object = newstringobject(key);
 804                 if (last_name_object == NULL) {
 805                         last_name_char = NULL;
 806                         return NULL;
 807                 }
 808                 last_name_char = key;
 809         }
 810         return mappinglookup(v, last_name_object);
 811 }
 812
 813 int
 814 dictinsert(v, key, item)
 815         object *v;
 816         char *key;
 817         object *item;
 818 {
 819         if (key != last_name_char ||
 820             strcmp(key, getstringvalue(last_name_object)) != 0) {
 821                 XDECREF(last_name_object);
 822                 last_name_object = newstringobject(key);
 823                 if (last_name_object == NULL) {
 824                         last_name_char = NULL;
 825                         return -1;
 826                 }
 827                 last_name_char = key;
 828         }
 829         return mappinginsert(v, last_name_object, item);
 830 }
 831
 832 int
 833 dictremove(v, key)
 834         object *v;
 835         char *key;
 836 {
 837         if (key != last_name_char ||
 838             strcmp(key, getstringvalue(last_name_object)) != 0) {
 839                 XDECREF(last_name_object);
 840                 last_name_object = newstringobject(key);
 841                 if (last_name_object == NULL) {
 842                         last_name_char = NULL;
 843                         return -1;
 844                 }
 845                 last_name_char = key;
 846         }
 847         return mappingremove(v, last_name_object);
 848 }