blob: 66cec0c71cad720912998dc1f8c0871577836b3e [file] [log] [blame]
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001/***********************************************************
Guido van Rossum6610ad91995-01-04 19:07:38 +00002Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam,
3The Netherlands.
Guido van Rossum4b1302b1993-03-27 18:11:32 +00004
5 All Rights Reserved
6
Guido van Rossumd266eb41996-10-25 14:44:06 +00007Permission to use, copy, modify, and distribute this software and its
8documentation for any purpose and without fee is hereby granted,
Guido van Rossum4b1302b1993-03-27 18:11:32 +00009provided that the above copyright notice appear in all copies and that
Guido van Rossumd266eb41996-10-25 14:44:06 +000010both that copyright notice and this permission notice appear in
Guido van Rossum4b1302b1993-03-27 18:11:32 +000011supporting documentation, and that the names of Stichting Mathematisch
Guido van Rossumd266eb41996-10-25 14:44:06 +000012Centrum or CWI or Corporation for National Research Initiatives or
13CNRI not be used in advertising or publicity pertaining to
14distribution of the software without specific, written prior
15permission.
Guido van Rossum4b1302b1993-03-27 18:11:32 +000016
Guido van Rossumd266eb41996-10-25 14:44:06 +000017While CWI is the initial source for this software, a modified version
18is made available by the Corporation for National Research Initiatives
19(CNRI) at the Internet address ftp://ftp.python.org.
20
21STICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH
22REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
23MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH
24CENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
25DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
26PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
27TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
28PERFORMANCE OF THIS SOFTWARE.
Guido van Rossum4b1302b1993-03-27 18:11:32 +000029
30******************************************************************/
31
Guido van Rossuma9e7a811997-05-13 21:02:11 +000032/* Dictionaru object implementation using a hash table */
Guido van Rossum9bfef441993-03-29 10:43:31 +000033
Guido van Rossumc0b618a1997-05-02 03:12:38 +000034#include "Python.h"
Guido van Rossum4b1302b1993-03-27 18:11:32 +000035
36
37/*
Guido van Rossuma9e7a811997-05-13 21:02:11 +000038 * MINSIZE is the minimum size of a dictionary.
Guido van Rossum16e93a81997-01-28 00:00:11 +000039 */
40
41#define MINSIZE 4
42
43/*
44Table of irreducible polynomials to efficiently cycle through
45GF(2^n)-{0}, 2<=n<=30.
Guido van Rossum4b1302b1993-03-27 18:11:32 +000046*/
Guido van Rossum16e93a81997-01-28 00:00:11 +000047static long polys[] = {
Guido van Rossum9e5656c1997-01-29 04:45:16 +000048 4 + 3,
49 8 + 3,
50 16 + 3,
51 32 + 5,
52 64 + 3,
53 128 + 3,
54 256 + 29,
55 512 + 17,
56 1024 + 9,
57 2048 + 5,
58 4096 + 83,
59 8192 + 27,
60 16384 + 43,
61 32768 + 3,
62 65536 + 45,
63 131072 + 9,
64 262144 + 39,
65 524288 + 39,
66 1048576 + 9,
67 2097152 + 5,
68 4194304 + 3,
69 8388608 + 33,
70 16777216 + 27,
71 33554432 + 9,
72 67108864 + 71,
73 134217728 + 39,
74 268435456 + 9,
75 536870912 + 5,
76 1073741824 + 83,
77 0
Guido van Rossum4b1302b1993-03-27 18:11:32 +000078};
79
80/* Object used as dummy key to fill deleted entries */
Guido van Rossuma9e7a811997-05-13 21:02:11 +000081static PyObject *dummy; /* Initialized by first call to newdictobject() */
Guido van Rossum4b1302b1993-03-27 18:11:32 +000082
83/*
84Invariant for entries: when in use, de_value is not NULL and de_key is
85not NULL and not dummy; when not in use, de_value is NULL and de_key
86is either NULL or dummy. A dummy key value cannot be replaced by
87NULL, since otherwise other keys may be lost.
88*/
89typedef struct {
90 long me_hash;
Guido van Rossumc0b618a1997-05-02 03:12:38 +000091 PyObject *me_key;
92 PyObject *me_value;
Guido van Rossum36488841997-04-11 19:14:07 +000093#ifdef USE_CACHE_ALIGNED
94 long aligner;
95#endif
Guido van Rossuma9e7a811997-05-13 21:02:11 +000096} dictentry;
Guido van Rossum4b1302b1993-03-27 18:11:32 +000097
98/*
99To ensure the lookup algorithm terminates, the table size must be a
100prime number and there must be at least one NULL key in the table.
101The value ma_fill is the number of non-NULL keys; ma_used is the number
102of non-NULL, non-dummy keys.
103To avoid slowing down lookups on a near-full table, we resize the table
104when it is more than half filled.
105*/
106typedef struct {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000107 PyObject_HEAD
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000108 int ma_fill;
109 int ma_used;
110 int ma_size;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000111 int ma_poly;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000112 dictentry *ma_table;
113} dictobject;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000114
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000115PyObject *
116PyDict_New()
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000117{
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000118 register dictobject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000119 if (dummy == NULL) { /* Auto-initialize dummy */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000120 dummy = PyString_FromString("<dummy key>");
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000121 if (dummy == NULL)
122 return NULL;
123 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000124 mp = PyObject_NEW(dictobject, &PyDict_Type);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000125 if (mp == NULL)
126 return NULL;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000127 mp->ma_size = 0;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000128 mp->ma_poly = 0;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000129 mp->ma_table = NULL;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000130 mp->ma_fill = 0;
131 mp->ma_used = 0;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000132 return (PyObject *)mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000133}
134
135/*
136The basic lookup function used by all operations.
Guido van Rossum16e93a81997-01-28 00:00:11 +0000137This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000138Open addressing is preferred over chaining since the link overhead for
139chaining would be substantial (100% with typical malloc overhead).
Guido van Rossum16e93a81997-01-28 00:00:11 +0000140However, instead of going through the table at constant steps, we cycle
141through the values of GF(2^n)-{0}. This avoids modulo computations, being
142much cheaper on RISC machines, without leading to clustering.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000143
144First a 32-bit hash value, 'sum', is computed from the key string.
145The first character is added an extra time shifted by 8 to avoid hashing
146single-character keys (often heavily used variables) too close together.
147All arithmetic on sum should ignore overflow.
148
149The initial probe index is then computed as sum mod the table size.
Guido van Rossum16e93a81997-01-28 00:00:11 +0000150Subsequent probe indices use the values of x^i in GF(2^n) as an offset,
151where x is a root. The initial value is derived from sum, too.
152
153(This version is due to Reimer Behrends, some ideas are also due to
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000154Jyrki Alakuijala and Vladimir Marangozov.)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000155*/
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000156static dictentry *lookdict Py_PROTO((dictobject *, PyObject *, long));
157static dictentry *
158lookdict(mp, key, hash)
159 dictobject *mp;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000160 PyObject *key;
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000161 register long hash;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000162{
Guido van Rossum16e93a81997-01-28 00:00:11 +0000163 register int i;
164 register unsigned incr;
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000165 register dictentry *freeslot;
Guido van Rossum2095d241997-04-09 19:41:24 +0000166 register unsigned int mask = mp->ma_size-1;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000167 dictentry *ep0 = mp->ma_table;
168 register dictentry *ep;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000169 /* We must come up with (i, incr) such that 0 <= i < ma_size
170 and 0 < incr < ma_size and both are a function of hash */
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000171 i = (~hash) & mask;
172 /* We use ~hash instead of hash, as degenerate hash functions, such
Guido van Rossum16e93a81997-01-28 00:00:11 +0000173 as for ints <sigh>, can have lots of leading zeros. It's not
174 really a performance risk, but better safe than sorry. */
Guido van Rossumefb46091997-01-29 15:53:56 +0000175 ep = &ep0[i];
Guido van Rossum16e93a81997-01-28 00:00:11 +0000176 if (ep->me_key == NULL)
Guido van Rossum7d181591997-01-16 21:06:45 +0000177 return ep;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000178 if (ep->me_key == dummy)
Guido van Rossum7d181591997-01-16 21:06:45 +0000179 freeslot = ep;
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000180 else {
181 if (ep->me_key == key ||
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000182 (ep->me_hash == hash &&
183 PyObject_Compare(ep->me_key, key) == 0))
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000184 {
185 return ep;
186 }
187 freeslot = NULL;
Guido van Rossum2a61e741997-01-18 07:55:05 +0000188 }
Guido van Rossum5b2121b1997-05-23 00:01:41 +0000189 /* XXX What if PyObject_Compare returned an exception? */
Guido van Rossumefb46091997-01-29 15:53:56 +0000190 /* Derive incr from sum, just to make it more arbitrary. Note that
Guido van Rossum16e93a81997-01-28 00:00:11 +0000191 incr must not be 0, or we will get into an infinite loop.*/
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000192 incr = (hash ^ ((unsigned long)hash >> 3)) & mask;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000193 if (!incr)
194 incr = mask;
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000195 else if (incr > mask) /* Cycle through GF(2^n)-{0} */
Guido van Rossum16e93a81997-01-28 00:00:11 +0000196 incr ^= mp->ma_poly; /* This will implicitly clear the
197 highest bit */
198 for (;;) {
Guido van Rossumefb46091997-01-29 15:53:56 +0000199 ep = &ep0[(i+incr)&mask];
Guido van Rossum16e93a81997-01-28 00:00:11 +0000200 if (ep->me_key == NULL) {
201 if (freeslot != NULL)
202 return freeslot;
203 else
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000204 return ep;
205 }
Guido van Rossum16e93a81997-01-28 00:00:11 +0000206 if (ep->me_key == dummy) {
207 if (freeslot == NULL)
208 freeslot = ep;
209 }
210 else if (ep->me_key == key ||
211 (ep->me_hash == hash &&
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000212 PyObject_Compare(ep->me_key, key) == 0)) {
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000213 return ep;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000214 }
Guido van Rossum5b2121b1997-05-23 00:01:41 +0000215 /* XXX What if PyObject_Compare returned an exception? */
Guido van Rossum16e93a81997-01-28 00:00:11 +0000216 /* Cycle through GF(2^n)-{0} */
217 incr = incr << 1;
218 if (incr > mask)
219 incr ^= mp->ma_poly;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000220 }
221}
222
223/*
224Internal routine to insert a new item into the table.
225Used both by the internal resize routine and by the public insert routine.
226Eats a reference to key and one to value.
227*/
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000228static void insertdict
229 Py_PROTO((dictobject *, PyObject *, long, PyObject *));
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000230static void
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000231insertdict(mp, key, hash, value)
232 register dictobject *mp;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000233 PyObject *key;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000234 long hash;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000235 PyObject *value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000236{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000237 PyObject *old_value;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000238 register dictentry *ep;
239 ep = lookdict(mp, key, hash);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000240 if (ep->me_value != NULL) {
Guido van Rossumd7047b31995-01-02 19:07:15 +0000241 old_value = ep->me_value;
242 ep->me_value = value;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000243 Py_DECREF(old_value); /* which **CAN** re-enter */
244 Py_DECREF(key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000245 }
246 else {
247 if (ep->me_key == NULL)
248 mp->ma_fill++;
249 else
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000250 Py_DECREF(ep->me_key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000251 ep->me_key = key;
252 ep->me_hash = hash;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000253 ep->me_value = value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000254 mp->ma_used++;
255 }
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000256}
257
258/*
259Restructure the table by allocating a new table and reinserting all
260items again. When entries have been deleted, the new table may
261actually be smaller than the old one.
262*/
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000263static int dictresize Py_PROTO((dictobject *, int));
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000264static int
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000265dictresize(mp, minused)
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000266 dictobject *mp;
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000267 int minused;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000268{
269 register int oldsize = mp->ma_size;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000270 register int newsize, newpoly;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000271 register dictentry *oldtable = mp->ma_table;
272 register dictentry *newtable;
273 register dictentry *ep;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000274 register int i;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000275 for (i = 0, newsize = MINSIZE; ; i++, newsize <<= 1) {
276 if (i > sizeof(polys)/sizeof(polys[0])) {
277 /* Ran out of polynomials */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000278 PyErr_NoMemory();
Guido van Rossum1d5735e1994-08-30 08:27:36 +0000279 return -1;
280 }
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000281 if (newsize > minused) {
Guido van Rossum16e93a81997-01-28 00:00:11 +0000282 newpoly = polys[i];
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000283 break;
284 }
285 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000286 newtable = (dictentry *) calloc(sizeof(dictentry), newsize);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000287 if (newtable == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000288 PyErr_NoMemory();
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000289 return -1;
290 }
291 mp->ma_size = newsize;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000292 mp->ma_poly = newpoly;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000293 mp->ma_table = newtable;
294 mp->ma_fill = 0;
295 mp->ma_used = 0;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000296
297 /* Make two passes, so we can avoid decrefs
298 (and possible side effects) till the table is copied */
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000299 for (i = 0, ep = oldtable; i < oldsize; i++, ep++) {
300 if (ep->me_value != NULL)
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000301 insertdict(mp,ep->me_key,ep->me_hash,ep->me_value);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000302 }
Guido van Rossumd7047b31995-01-02 19:07:15 +0000303 for (i = 0, ep = oldtable; i < oldsize; i++, ep++) {
304 if (ep->me_value == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000305 Py_XDECREF(ep->me_key);
Guido van Rossumd7047b31995-01-02 19:07:15 +0000306 }
307
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000308 PyMem_XDEL(oldtable);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000309 return 0;
310}
311
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000312PyObject *
313PyDict_GetItem(op, key)
314 PyObject *op;
315 PyObject *key;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000316{
317 long hash;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000318 if (!PyDict_Check(op)) {
319 PyErr_BadInternalCall();
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000320 return NULL;
321 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000322 if (((dictobject *)op)->ma_table == NULL)
Guido van Rossumd7047b31995-01-02 19:07:15 +0000323 return NULL;
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000324#ifdef CACHE_HASH
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000325 if (!PyString_Check(key) ||
326 (hash = ((PyStringObject *) key)->ob_shash) == -1)
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000327#endif
Guido van Rossumca756f21997-01-23 19:39:29 +0000328 {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000329 hash = PyObject_Hash(key);
Guido van Rossumca756f21997-01-23 19:39:29 +0000330 if (hash == -1)
331 return NULL;
332 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000333 return lookdict((dictobject *)op, key, hash) -> me_value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000334}
335
336int
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000337PyDict_SetItem(op, key, value)
338 register PyObject *op;
339 PyObject *key;
340 PyObject *value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000341{
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000342 register dictobject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000343 register long hash;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000344 if (!PyDict_Check(op)) {
345 PyErr_BadInternalCall();
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000346 return -1;
347 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000348 mp = (dictobject *)op;
Guido van Rossum2a61e741997-01-18 07:55:05 +0000349#ifdef CACHE_HASH
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000350 if (PyString_Check(key)) {
Guido van Rossum2a61e741997-01-18 07:55:05 +0000351#ifdef INTERN_STRINGS
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000352 if (((PyStringObject *)key)->ob_sinterned != NULL) {
353 key = ((PyStringObject *)key)->ob_sinterned;
354 hash = ((PyStringObject *)key)->ob_shash;
Guido van Rossum2a61e741997-01-18 07:55:05 +0000355 }
356 else
357#endif
358 {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000359 hash = ((PyStringObject *)key)->ob_shash;
Guido van Rossum2a61e741997-01-18 07:55:05 +0000360 if (hash == -1)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000361 hash = PyObject_Hash(key);
Guido van Rossum2a61e741997-01-18 07:55:05 +0000362 }
363 }
364 else
365#endif
366 {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000367 hash = PyObject_Hash(key);
Guido van Rossum2a61e741997-01-18 07:55:05 +0000368 if (hash == -1)
369 return -1;
Guido van Rossum2a61e741997-01-18 07:55:05 +0000370 }
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000371 /* if fill >= 2/3 size, double in size */
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000372 if (mp->ma_fill*3 >= mp->ma_size*2) {
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000373 if (dictresize(mp, mp->ma_used*2) != 0) {
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000374 if (mp->ma_fill+1 > mp->ma_size)
375 return -1;
376 }
377 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000378 Py_INCREF(value);
379 Py_INCREF(key);
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000380 insertdict(mp, key, hash, value);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000381 return 0;
382}
383
384int
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000385PyDict_DelItem(op, key)
386 PyObject *op;
387 PyObject *key;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000388{
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000389 register dictobject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000390 register long hash;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000391 register dictentry *ep;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000392 PyObject *old_value, *old_key;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000393
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000394 if (!PyDict_Check(op)) {
395 PyErr_BadInternalCall();
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000396 return -1;
397 }
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000398#ifdef CACHE_HASH
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000399 if (!PyString_Check(key) ||
400 (hash = ((PyStringObject *) key)->ob_shash) == -1)
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000401#endif
Guido van Rossumca756f21997-01-23 19:39:29 +0000402 {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000403 hash = PyObject_Hash(key);
Guido van Rossumca756f21997-01-23 19:39:29 +0000404 if (hash == -1)
405 return -1;
406 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000407 mp = (dictobject *)op;
408 if (((dictobject *)op)->ma_table == NULL)
Guido van Rossumefc87131995-01-02 19:42:39 +0000409 goto empty;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000410 ep = lookdict(mp, key, hash);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000411 if (ep->me_value == NULL) {
Guido van Rossumefc87131995-01-02 19:42:39 +0000412 empty:
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000413 PyErr_SetObject(PyExc_KeyError, key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000414 return -1;
415 }
Guido van Rossumd7047b31995-01-02 19:07:15 +0000416 old_key = ep->me_key;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000417 Py_INCREF(dummy);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000418 ep->me_key = dummy;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000419 old_value = ep->me_value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000420 ep->me_value = NULL;
421 mp->ma_used--;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000422 Py_DECREF(old_value);
423 Py_DECREF(old_key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000424 return 0;
425}
426
Guido van Rossum25831651993-05-19 14:50:45 +0000427void
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000428PyDict_Clear(op)
429 PyObject *op;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000430{
Guido van Rossumd7047b31995-01-02 19:07:15 +0000431 int i, n;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000432 register dictentry *table;
433 dictobject *mp;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000434 if (!PyDict_Check(op))
Guido van Rossum25831651993-05-19 14:50:45 +0000435 return;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000436 mp = (dictobject *)op;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000437 table = mp->ma_table;
438 if (table == NULL)
439 return;
440 n = mp->ma_size;
441 mp->ma_size = mp->ma_used = mp->ma_fill = 0;
442 mp->ma_table = NULL;
443 for (i = 0; i < n; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000444 Py_XDECREF(table[i].me_key);
445 Py_XDECREF(table[i].me_value);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000446 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000447 PyMem_DEL(table);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000448}
449
Guido van Rossum25831651993-05-19 14:50:45 +0000450int
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000451PyDict_Next(op, ppos, pkey, pvalue)
452 PyObject *op;
Guido van Rossum25831651993-05-19 14:50:45 +0000453 int *ppos;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000454 PyObject **pkey;
455 PyObject **pvalue;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000456{
Guido van Rossum25831651993-05-19 14:50:45 +0000457 int i;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000458 register dictobject *mp;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000459 if (!PyDict_Check(op))
Guido van Rossum25831651993-05-19 14:50:45 +0000460 return 0;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000461 mp = (dictobject *)op;
Guido van Rossum25831651993-05-19 14:50:45 +0000462 i = *ppos;
463 if (i < 0)
464 return 0;
465 while (i < mp->ma_size && mp->ma_table[i].me_value == NULL)
466 i++;
467 *ppos = i+1;
468 if (i >= mp->ma_size)
469 return 0;
470 if (pkey)
471 *pkey = mp->ma_table[i].me_key;
472 if (pvalue)
473 *pvalue = mp->ma_table[i].me_value;
474 return 1;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000475}
476
477/* Methods */
478
479static void
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000480dict_dealloc(mp)
481 register dictobject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000482{
483 register int i;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000484 register dictentry *ep;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000485 for (i = 0, ep = mp->ma_table; i < mp->ma_size; i++, ep++) {
486 if (ep->me_key != NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000487 Py_DECREF(ep->me_key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000488 if (ep->me_value != NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000489 Py_DECREF(ep->me_value);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000490 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000491 PyMem_XDEL(mp->ma_table);
492 PyMem_DEL(mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000493}
494
495static int
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000496dict_print(mp, fp, flags)
497 register dictobject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000498 register FILE *fp;
499 register int flags;
500{
501 register int i;
502 register int any;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000503 register dictentry *ep;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000504 fprintf(fp, "{");
505 any = 0;
506 for (i = 0, ep = mp->ma_table; i < mp->ma_size; i++, ep++) {
507 if (ep->me_value != NULL) {
508 if (any++ > 0)
509 fprintf(fp, ", ");
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000510 if (PyObject_Print((PyObject *)ep->me_key, fp, 0) != 0)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000511 return -1;
512 fprintf(fp, ": ");
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000513 if (PyObject_Print(ep->me_value, fp, 0) != 0)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000514 return -1;
515 }
516 }
517 fprintf(fp, "}");
518 return 0;
519}
520
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000521static PyObject *
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000522dict_repr(mp)
523 dictobject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000524{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000525 auto PyObject *v;
526 PyObject *sepa, *colon;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000527 register int i;
528 register int any;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000529 register dictentry *ep;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000530 v = PyString_FromString("{");
531 sepa = PyString_FromString(", ");
532 colon = PyString_FromString(": ");
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000533 any = 0;
Guido van Rossum1d5735e1994-08-30 08:27:36 +0000534 for (i = 0, ep = mp->ma_table; i < mp->ma_size && v; i++, ep++) {
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000535 if (ep->me_value != NULL) {
536 if (any++)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000537 PyString_Concat(&v, sepa);
538 PyString_ConcatAndDel(&v, PyObject_Repr(ep->me_key));
539 PyString_Concat(&v, colon);
540 PyString_ConcatAndDel(&v, PyObject_Repr(ep->me_value));
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000541 }
542 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000543 PyString_ConcatAndDel(&v, PyString_FromString("}"));
544 Py_XDECREF(sepa);
545 Py_XDECREF(colon);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000546 return v;
547}
548
549static int
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000550dict_length(mp)
551 dictobject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000552{
553 return mp->ma_used;
554}
555
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000556static PyObject *
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000557dict_subscript(mp, key)
558 dictobject *mp;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000559 register PyObject *key;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000560{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000561 PyObject *v;
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000562 long hash;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000563 if (mp->ma_table == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000564 PyErr_SetObject(PyExc_KeyError, key);
Guido van Rossumd7047b31995-01-02 19:07:15 +0000565 return NULL;
566 }
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000567#ifdef CACHE_HASH
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000568 if (!PyString_Check(key) ||
569 (hash = ((PyStringObject *) key)->ob_shash) == -1)
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000570#endif
Guido van Rossumca756f21997-01-23 19:39:29 +0000571 {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000572 hash = PyObject_Hash(key);
Guido van Rossumca756f21997-01-23 19:39:29 +0000573 if (hash == -1)
574 return NULL;
575 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000576 v = lookdict(mp, key, hash) -> me_value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000577 if (v == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000578 PyErr_SetObject(PyExc_KeyError, key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000579 else
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000580 Py_INCREF(v);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000581 return v;
582}
583
584static int
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000585dict_ass_sub(mp, v, w)
586 dictobject *mp;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000587 PyObject *v, *w;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000588{
589 if (w == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000590 return PyDict_DelItem((PyObject *)mp, v);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000591 else
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000592 return PyDict_SetItem((PyObject *)mp, v, w);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000593}
594
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000595static PyMappingMethods dict_as_mapping = {
596 (inquiry)dict_length, /*mp_length*/
597 (binaryfunc)dict_subscript, /*mp_subscript*/
598 (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000599};
600
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000601static PyObject *
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000602dict_keys(mp, args)
603 register dictobject *mp;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000604 PyObject *args;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000605{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000606 register PyObject *v;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000607 register int i, j;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000608 if (!PyArg_NoArgs(args))
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000609 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000610 v = PyList_New(mp->ma_used);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000611 if (v == NULL)
612 return NULL;
613 for (i = 0, j = 0; i < mp->ma_size; i++) {
614 if (mp->ma_table[i].me_value != NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000615 PyObject *key = mp->ma_table[i].me_key;
616 Py_INCREF(key);
617 PyList_SetItem(v, j, key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000618 j++;
619 }
620 }
621 return v;
622}
623
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000624static PyObject *
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000625dict_values(mp, args)
626 register dictobject *mp;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000627 PyObject *args;
Guido van Rossum25831651993-05-19 14:50:45 +0000628{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000629 register PyObject *v;
Guido van Rossum25831651993-05-19 14:50:45 +0000630 register int i, j;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000631 if (!PyArg_NoArgs(args))
Guido van Rossum25831651993-05-19 14:50:45 +0000632 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000633 v = PyList_New(mp->ma_used);
Guido van Rossum25831651993-05-19 14:50:45 +0000634 if (v == NULL)
635 return NULL;
636 for (i = 0, j = 0; i < mp->ma_size; i++) {
637 if (mp->ma_table[i].me_value != NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000638 PyObject *value = mp->ma_table[i].me_value;
639 Py_INCREF(value);
640 PyList_SetItem(v, j, value);
Guido van Rossum25831651993-05-19 14:50:45 +0000641 j++;
642 }
643 }
644 return v;
645}
646
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000647static PyObject *
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000648dict_items(mp, args)
649 register dictobject *mp;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000650 PyObject *args;
Guido van Rossum25831651993-05-19 14:50:45 +0000651{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000652 register PyObject *v;
Guido van Rossum25831651993-05-19 14:50:45 +0000653 register int i, j;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000654 if (!PyArg_NoArgs(args))
Guido van Rossum25831651993-05-19 14:50:45 +0000655 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000656 v = PyList_New(mp->ma_used);
Guido van Rossum25831651993-05-19 14:50:45 +0000657 if (v == NULL)
658 return NULL;
659 for (i = 0, j = 0; i < mp->ma_size; i++) {
660 if (mp->ma_table[i].me_value != NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000661 PyObject *key = mp->ma_table[i].me_key;
662 PyObject *value = mp->ma_table[i].me_value;
663 PyObject *item = PyTuple_New(2);
Guido van Rossum25831651993-05-19 14:50:45 +0000664 if (item == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000665 Py_DECREF(v);
Guido van Rossum25831651993-05-19 14:50:45 +0000666 return NULL;
667 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000668 Py_INCREF(key);
669 PyTuple_SetItem(item, 0, key);
670 Py_INCREF(value);
671 PyTuple_SetItem(item, 1, value);
672 PyList_SetItem(v, j, item);
Guido van Rossum25831651993-05-19 14:50:45 +0000673 j++;
674 }
675 }
676 return v;
677}
678
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000679static PyObject *
Guido van Rossuma8d51311997-06-02 17:13:37 +0000680dict_update(mp, args)
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000681 register dictobject *mp;
682 PyObject *args;
683{
684 register int i;
685 dictobject *other;
686 dictentry *entry;
687 if (!PyArg_Parse(args, "O!", &PyDict_Type, &other))
688 return NULL;
689 if (other == mp)
Guido van Rossuma8d51311997-06-02 17:13:37 +0000690 goto done; /* a.update(a); nothing to do */
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000691 /* Do one big resize at the start, rather than incrementally
692 resizing as we insert new items. Expect that there will be
693 no (or few) overlapping keys. */
694 if ((mp->ma_fill + other->ma_used)*3 >= mp->ma_size*2) {
695 if (dictresize(mp, (mp->ma_used + other->ma_used)*3/2) != 0)
696 return NULL;
697 }
698 for (i = 0; i < other->ma_size; i++) {
699 entry = &other->ma_table[i];
700 if (entry->me_value != NULL) {
701 Py_INCREF(entry->me_key);
702 Py_INCREF(entry->me_value);
703 insertdict(mp, entry->me_key, entry->me_hash,
704 entry->me_value);
705 }
706 }
707 done:
708 Py_INCREF(Py_None);
709 return Py_None;
710}
711
712static PyObject *
713dict_copy(mp, args)
714 register dictobject *mp;
715 PyObject *args;
716{
717 register int i;
718 dictobject *copy;
719 dictentry *entry;
720 if (!PyArg_Parse(args, ""))
721 return NULL;
722 copy = (dictobject *)PyDict_New();
723 if (copy == NULL)
724 return NULL;
725 if (mp->ma_used > 0) {
726 if (dictresize(copy, mp->ma_used*3/2) != 0)
727 return NULL;
728 for (i = 0; i < mp->ma_size; i++) {
729 entry = &mp->ma_table[i];
730 if (entry->me_value != NULL) {
731 Py_INCREF(entry->me_key);
732 Py_INCREF(entry->me_value);
733 insertdict(copy, entry->me_key, entry->me_hash,
734 entry->me_value);
735 }
736 }
737 }
738 return (PyObject *)copy;
739}
740
Guido van Rossum4199fac1993-11-05 10:18:44 +0000741int
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000742PyDict_Size(mp)
743 PyObject *mp;
Guido van Rossum4199fac1993-11-05 10:18:44 +0000744{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000745 if (mp == NULL || !PyDict_Check(mp)) {
746 PyErr_BadInternalCall();
Guido van Rossumb376a4a1993-11-23 17:53:17 +0000747 return 0;
Guido van Rossum4199fac1993-11-05 10:18:44 +0000748 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000749 return ((dictobject *)mp)->ma_used;
Guido van Rossum4199fac1993-11-05 10:18:44 +0000750}
751
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000752PyObject *
753PyDict_Keys(mp)
754 PyObject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000755{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000756 if (mp == NULL || !PyDict_Check(mp)) {
757 PyErr_BadInternalCall();
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000758 return NULL;
759 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000760 return dict_keys((dictobject *)mp, (PyObject *)NULL);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000761}
762
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000763PyObject *
764PyDict_Values(mp)
765 PyObject *mp;
Guido van Rossum25831651993-05-19 14:50:45 +0000766{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000767 if (mp == NULL || !PyDict_Check(mp)) {
768 PyErr_BadInternalCall();
Guido van Rossum25831651993-05-19 14:50:45 +0000769 return NULL;
770 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000771 return dict_values((dictobject *)mp, (PyObject *)NULL);
Guido van Rossum25831651993-05-19 14:50:45 +0000772}
773
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000774PyObject *
775PyDict_Items(mp)
776 PyObject *mp;
Guido van Rossum25831651993-05-19 14:50:45 +0000777{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000778 if (mp == NULL || !PyDict_Check(mp)) {
779 PyErr_BadInternalCall();
Guido van Rossum25831651993-05-19 14:50:45 +0000780 return NULL;
781 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000782 return dict_items((dictobject *)mp, (PyObject *)NULL);
Guido van Rossum25831651993-05-19 14:50:45 +0000783}
784
Guido van Rossuma0a69b81996-12-05 21:55:55 +0000785#define NEWCMP
786
787#ifdef NEWCMP
788
789/* Subroutine which returns the smallest key in a for which b's value
790 is different or absent. The value is returned too, through the
791 pval argument. No reference counts are incremented. */
792
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000793static PyObject *
Guido van Rossuma0a69b81996-12-05 21:55:55 +0000794characterize(a, b, pval)
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000795 dictobject *a;
796 dictobject *b;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000797 PyObject **pval;
Guido van Rossuma0a69b81996-12-05 21:55:55 +0000798{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000799 PyObject *diff = NULL;
Guido van Rossuma0a69b81996-12-05 21:55:55 +0000800 int i;
801
802 *pval = NULL;
803 for (i = 0; i < a->ma_size; i++) {
804 if (a->ma_table[i].me_value != NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000805 PyObject *key = a->ma_table[i].me_key;
806 PyObject *aval, *bval;
Guido van Rossum5b2121b1997-05-23 00:01:41 +0000807 /* XXX What if PyObject_Compare raises an exception? */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000808 if (diff != NULL && PyObject_Compare(key, diff) > 0)
Guido van Rossuma0a69b81996-12-05 21:55:55 +0000809 continue;
810 aval = a->ma_table[i].me_value;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000811 bval = PyDict_GetItem((PyObject *)b, key);
Guido van Rossum5b2121b1997-05-23 00:01:41 +0000812 /* XXX What if PyObject_Compare raises an exception? */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000813 if (bval == NULL || PyObject_Compare(aval, bval) != 0)
814 {
Guido van Rossuma0a69b81996-12-05 21:55:55 +0000815 diff = key;
816 *pval = aval;
817 }
818 }
819 }
820 return diff;
821}
822
823static int
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000824dict_compare(a, b)
825 dictobject *a, *b;
Guido van Rossuma0a69b81996-12-05 21:55:55 +0000826{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000827 PyObject *adiff, *bdiff, *aval, *bval;
Guido van Rossuma0a69b81996-12-05 21:55:55 +0000828 int res;
829
830 /* Compare lengths first */
831 if (a->ma_used < b->ma_used)
832 return -1; /* a is shorter */
833 else if (a->ma_used > b->ma_used)
834 return 1; /* b is shorter */
835 /* Same length -- check all keys */
836 adiff = characterize(a, b, &aval);
Guido van Rossum5b2121b1997-05-23 00:01:41 +0000837 if (PyErr_Occurred())
838 return -1;
Guido van Rossuma0a69b81996-12-05 21:55:55 +0000839 if (adiff == NULL)
840 return 0; /* a is a subset with the same length */
841 bdiff = characterize(b, a, &bval);
Guido van Rossum5b2121b1997-05-23 00:01:41 +0000842 if (PyErr_Occurred())
843 return -1;
Guido van Rossuma0a69b81996-12-05 21:55:55 +0000844 /* bdiff == NULL would be impossible now */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000845 res = PyObject_Compare(adiff, bdiff);
Guido van Rossuma0a69b81996-12-05 21:55:55 +0000846 if (res == 0)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000847 res = PyObject_Compare(aval, bval);
Guido van Rossuma0a69b81996-12-05 21:55:55 +0000848 return res;
849}
850
851#else /* !NEWCMP */
852
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000853static int
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000854dict_compare(a, b)
855 dictobject *a, *b;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000856{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000857 PyObject *akeys, *bkeys;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000858 int i, n, res;
859 if (a == b)
860 return 0;
861 if (a->ma_used == 0) {
862 if (b->ma_used != 0)
863 return -1;
864 else
865 return 0;
866 }
867 else {
868 if (b->ma_used == 0)
869 return 1;
870 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000871 akeys = dict_keys(a, (PyObject *)NULL);
872 bkeys = dict_keys(b, (PyObject *)NULL);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000873 if (akeys == NULL || bkeys == NULL) {
874 /* Oops, out of memory -- what to do? */
875 /* For now, sort on address! */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000876 Py_XDECREF(akeys);
877 Py_XDECREF(bkeys);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000878 if (a < b)
879 return -1;
880 else
881 return 1;
882 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000883 PyList_Sort(akeys);
884 PyList_Sort(bkeys);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000885 n = a->ma_used < b->ma_used ? a->ma_used : b->ma_used; /* smallest */
886 res = 0;
887 for (i = 0; i < n; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000888 PyObject *akey, *bkey, *aval, *bval;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000889 long ahash, bhash;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000890 akey = PyList_GetItem(akeys, i);
891 bkey = PyList_GetItem(bkeys, i);
892 res = PyObject_Compare(akey, bkey);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000893 if (res != 0)
894 break;
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000895#ifdef CACHE_HASH
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000896 if (!PyString_Check(akey) ||
897 (ahash = ((PyStringObject *) akey)->ob_shash) == -1)
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000898#endif
Guido van Rossumca756f21997-01-23 19:39:29 +0000899 {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000900 ahash = PyObject_Hash(akey);
Guido van Rossumca756f21997-01-23 19:39:29 +0000901 if (ahash == -1)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000902 PyErr_Clear(); /* Don't want errors here */
Guido van Rossumca756f21997-01-23 19:39:29 +0000903 }
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000904#ifdef CACHE_HASH
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000905 if (!PyString_Check(bkey) ||
906 (bhash = ((PyStringObject *) bkey)->ob_shash) == -1)
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000907#endif
Guido van Rossumca756f21997-01-23 19:39:29 +0000908 {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000909 bhash = PyObject_Hash(bkey);
Guido van Rossumca756f21997-01-23 19:39:29 +0000910 if (bhash == -1)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000911 PyErr_Clear(); /* Don't want errors here */
Guido van Rossumca756f21997-01-23 19:39:29 +0000912 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000913 aval = lookdict(a, akey, ahash) -> me_value;
914 bval = lookdict(b, bkey, bhash) -> me_value;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000915 res = PyObject_Compare(aval, bval);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000916 if (res != 0)
917 break;
918 }
919 if (res == 0) {
920 if (a->ma_used < b->ma_used)
921 res = -1;
922 else if (a->ma_used > b->ma_used)
923 res = 1;
924 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000925 Py_DECREF(akeys);
926 Py_DECREF(bkeys);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000927 return res;
928}
929
Guido van Rossuma0a69b81996-12-05 21:55:55 +0000930#endif /* !NEWCMP */
931
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000932static PyObject *
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000933dict_has_key(mp, args)
934 register dictobject *mp;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000935 PyObject *args;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000936{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000937 PyObject *key;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000938 long hash;
939 register long ok;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000940 if (!PyArg_Parse(args, "O", &key))
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000941 return NULL;
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000942#ifdef CACHE_HASH
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000943 if (!PyString_Check(key) ||
944 (hash = ((PyStringObject *) key)->ob_shash) == -1)
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000945#endif
Guido van Rossumca756f21997-01-23 19:39:29 +0000946 {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000947 hash = PyObject_Hash(key);
Guido van Rossumca756f21997-01-23 19:39:29 +0000948 if (hash == -1)
949 return NULL;
950 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000951 ok = mp->ma_size != 0 && lookdict(mp, key, hash)->me_value != NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000952 return PyInt_FromLong(ok);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000953}
954
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000955static PyObject *
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000956dict_clear(mp, args)
957 register dictobject *mp;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000958 PyObject *args;
Guido van Rossumfb8f1ca1997-03-21 21:55:12 +0000959{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000960 if (!PyArg_NoArgs(args))
Guido van Rossumfb8f1ca1997-03-21 21:55:12 +0000961 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000962 PyDict_Clear((PyObject *)mp);
963 Py_INCREF(Py_None);
964 return Py_None;
Guido van Rossumfb8f1ca1997-03-21 21:55:12 +0000965}
966
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000967static PyMethodDef mapp_methods[] = {
Guido van Rossum5d8123f1997-07-13 03:58:01 +0000968 {"has_key", (PyCFunction)dict_has_key},
969 {"keys", (PyCFunction)dict_keys},
970 {"items", (PyCFunction)dict_items},
971 {"values", (PyCFunction)dict_values},
Guido van Rossuma8d51311997-06-02 17:13:37 +0000972 {"update", (PyCFunction)dict_update},
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000973 {"clear", (PyCFunction)dict_clear},
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000974 {"copy", (PyCFunction)dict_copy},
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000975 {NULL, NULL} /* sentinel */
976};
977
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000978static PyObject *
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000979dict_getattr(mp, name)
980 dictobject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000981 char *name;
982{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000983 return Py_FindMethod(mapp_methods, (PyObject *)mp, name);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000984}
985
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000986PyTypeObject PyDict_Type = {
987 PyObject_HEAD_INIT(&PyType_Type)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000988 0,
Guido van Rossum9bfef441993-03-29 10:43:31 +0000989 "dictionary",
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000990 sizeof(dictobject),
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000991 0,
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000992 (destructor)dict_dealloc, /*tp_dealloc*/
993 (printfunc)dict_print, /*tp_print*/
994 (getattrfunc)dict_getattr, /*tp_getattr*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000995 0, /*tp_setattr*/
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000996 (cmpfunc)dict_compare, /*tp_compare*/
997 (reprfunc)dict_repr, /*tp_repr*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000998 0, /*tp_as_number*/
999 0, /*tp_as_sequence*/
Guido van Rossuma9e7a811997-05-13 21:02:11 +00001000 &dict_as_mapping, /*tp_as_mapping*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001001};
1002
Guido van Rossum3cca2451997-05-16 14:23:33 +00001003/* For backward compatibility with old dictionary interface */
1004
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001005PyObject *
1006PyDict_GetItemString(v, key)
1007 PyObject *v;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001008 char *key;
1009{
Guido van Rossum3cca2451997-05-16 14:23:33 +00001010 PyObject *kv, *rv;
1011 kv = PyString_FromString(key);
1012 if (kv == NULL)
1013 return NULL;
1014 PyString_InternInPlace(&kv);
1015 rv = PyDict_GetItem(v, kv);
1016 Py_DECREF(kv);
1017 return rv;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001018}
1019
1020int
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001021PyDict_SetItemString(v, key, item)
1022 PyObject *v;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001023 char *key;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001024 PyObject *item;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001025{
Guido van Rossum3cca2451997-05-16 14:23:33 +00001026 PyObject *kv;
1027 int err;
1028 kv = PyString_FromString(key);
1029 if (kv == NULL)
Guido van Rossum037b2201997-05-20 18:35:19 +00001030 return -1;
Guido van Rossum3cca2451997-05-16 14:23:33 +00001031 PyString_InternInPlace(&kv);
1032 err = PyDict_SetItem(v, kv, item);
1033 Py_DECREF(kv);
1034 return err;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001035}
1036
1037int
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001038PyDict_DelItemString(v, key)
1039 PyObject *v;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001040 char *key;
1041{
Guido van Rossum3cca2451997-05-16 14:23:33 +00001042 PyObject *kv;
1043 int err;
1044 kv = PyString_FromString(key);
1045 if (kv == NULL)
Guido van Rossum037b2201997-05-20 18:35:19 +00001046 return -1;
Guido van Rossum3cca2451997-05-16 14:23:33 +00001047 PyString_InternInPlace(&kv);
1048 err = PyDict_DelItem(v, kv);
1049 Py_DECREF(kv);
1050 return err;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001051}