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