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