blob: b374aeb64f046b2e6368e75cad874fd9cae3bbff [file] [log] [blame]
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001
Guido van Rossum2bc13791999-03-24 19:06:42 +00002/* Dictionary object implementation using a hash table */
Guido van Rossum9bfef441993-03-29 10:43:31 +00003
Guido van Rossumc0b618a1997-05-02 03:12:38 +00004#include "Python.h"
Guido van Rossum4b1302b1993-03-27 18:11:32 +00005
6
7/*
Guido van Rossuma9e7a811997-05-13 21:02:11 +00008 * MINSIZE is the minimum size of a dictionary.
Guido van Rossum16e93a81997-01-28 00:00:11 +00009 */
10
11#define MINSIZE 4
12
Fred Drake1bff34a2000-08-31 19:31:38 +000013/* define this out if you don't want conversion statistics on exit */
14#undef SHOW_CONVERSION_COUNTS
15
Guido van Rossum16e93a81997-01-28 00:00:11 +000016/*
17Table of irreducible polynomials to efficiently cycle through
Tim Petersea8f2bf2000-12-13 01:02:46 +000018GF(2^n)-{0}, 2<=n<=30. A table size is always a power of 2.
Guido van Rossum4b1302b1993-03-27 18:11:32 +000019*/
Guido van Rossum16e93a81997-01-28 00:00:11 +000020static long polys[] = {
Guido van Rossum9e5656c1997-01-29 04:45:16 +000021 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
Guido van Rossum4b1302b1993-03-27 18:11:32 +000051};
52
53/* Object used as dummy key to fill deleted entries */
Guido van Rossuma9e7a811997-05-13 21:02:11 +000054static PyObject *dummy; /* Initialized by first call to newdictobject() */
Guido van Rossum4b1302b1993-03-27 18:11:32 +000055
56/*
Tim Petersea8f2bf2000-12-13 01:02:46 +000057There are three kinds of slots in the table:
58
591. Unused. me_key == me_value == NULL
60 Does not hold an active (key, value) pair now and never did. Unused can
61 transition to Active upon key insertion. This is the only case in which
62 me_key is NULL, and is each slot's initial state.
63
642. Active. me_key != NULL and me_key != dummy and me_value != NULL
65 Holds an active (key, value) pair. Active can transition to Dummy upon
66 key deletion. This is the only case in which me_value != NULL.
67
Tim Petersf1c7c882000-12-13 19:58:25 +0000683. Dummy. me_key == dummy and me_value == NULL
Tim Petersea8f2bf2000-12-13 01:02:46 +000069 Previously held an active (key, value) pair, but that was deleted and an
70 active pair has not yet overwritten the slot. Dummy can transition to
71 Active upon key insertion. Dummy slots cannot be made Unused again
72 (cannot have me_key set to NULL), else the probe sequence in case of
73 collision would have no way to know they were once active.
Tim Petersf1c7c882000-12-13 19:58:25 +000074
75Note: .popitem() abuses the me_hash field of an Unused or Dummy slot to
76hold a search finger. The me_hash field of Unused or Dummy slots has no
77meaning otherwise.
Guido van Rossum4b1302b1993-03-27 18:11:32 +000078*/
79typedef struct {
Tim Petersea8f2bf2000-12-13 01:02:46 +000080 long me_hash; /* cached hash code of me_key */
Guido van Rossumc0b618a1997-05-02 03:12:38 +000081 PyObject *me_key;
82 PyObject *me_value;
Guido van Rossum36488841997-04-11 19:14:07 +000083#ifdef USE_CACHE_ALIGNED
84 long aligner;
85#endif
Guido van Rossuma9e7a811997-05-13 21:02:11 +000086} dictentry;
Guido van Rossum4b1302b1993-03-27 18:11:32 +000087
88/*
Tim Petersf1c7c882000-12-13 19:58:25 +000089To ensure the lookup algorithm terminates, there must be at least one Unused
Tim Petersea8f2bf2000-12-13 01:02:46 +000090slot (NULL key) in the table.
91The value ma_fill is the number of non-NULL keys (sum of Active and Dummy);
92ma_used is the number of non-NULL, non-dummy keys (== the number of non-NULL
93values == the number of Active items).
94To avoid slowing down lookups on a near-full table, we resize the table when
Tim Peters67830702001-03-21 19:23:56 +000095it's two-thirds full.
Guido van Rossum4b1302b1993-03-27 18:11:32 +000096*/
Fred Drake1bff34a2000-08-31 19:31:38 +000097typedef struct dictobject dictobject;
98struct dictobject {
Guido van Rossumc0b618a1997-05-02 03:12:38 +000099 PyObject_HEAD
Tim Petersea8f2bf2000-12-13 01:02:46 +0000100 int ma_fill; /* # Active + # Dummy */
101 int ma_used; /* # Active */
102 int ma_size; /* total # slots in ma_table */
103 int ma_poly; /* appopriate entry from polys vector */
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000104 dictentry *ma_table;
Fred Drake1bff34a2000-08-31 19:31:38 +0000105 dictentry *(*ma_lookup)(dictobject *mp, PyObject *key, long hash);
106};
107
108/* forward declarations */
109static dictentry *
110lookdict_string(dictobject *mp, PyObject *key, long hash);
111
112#ifdef SHOW_CONVERSION_COUNTS
113static long created = 0L;
114static long converted = 0L;
115
116static void
117show_counts(void)
118{
119 fprintf(stderr, "created %ld string dicts\n", created);
120 fprintf(stderr, "converted %ld to normal dicts\n", converted);
121 fprintf(stderr, "%.2f%% conversion rate\n", (100.0*converted)/created);
122}
123#endif
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000124
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000125PyObject *
Thomas Wouters78890102000-07-22 19:25:51 +0000126PyDict_New(void)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000127{
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000128 register dictobject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000129 if (dummy == NULL) { /* Auto-initialize dummy */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000130 dummy = PyString_FromString("<dummy key>");
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000131 if (dummy == NULL)
132 return NULL;
Fred Drake1bff34a2000-08-31 19:31:38 +0000133#ifdef SHOW_CONVERSION_COUNTS
134 Py_AtExit(show_counts);
135#endif
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000136 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000137 mp = PyObject_NEW(dictobject, &PyDict_Type);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000138 if (mp == NULL)
139 return NULL;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000140 mp->ma_size = 0;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000141 mp->ma_poly = 0;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000142 mp->ma_table = NULL;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000143 mp->ma_fill = 0;
144 mp->ma_used = 0;
Fred Drake1bff34a2000-08-31 19:31:38 +0000145 mp->ma_lookup = lookdict_string;
146#ifdef SHOW_CONVERSION_COUNTS
147 ++created;
148#endif
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000149 PyObject_GC_Init(mp);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000150 return (PyObject *)mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000151}
152
153/*
154The basic lookup function used by all operations.
Guido van Rossum16e93a81997-01-28 00:00:11 +0000155This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000156Open addressing is preferred over chaining since the link overhead for
157chaining would be substantial (100% with typical malloc overhead).
Guido van Rossum16e93a81997-01-28 00:00:11 +0000158However, instead of going through the table at constant steps, we cycle
Tim Petersea8f2bf2000-12-13 01:02:46 +0000159through the values of GF(2^n). This avoids modulo computations, being
Guido van Rossum16e93a81997-01-28 00:00:11 +0000160much cheaper on RISC machines, without leading to clustering.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000161
Guido van Rossum2bc13791999-03-24 19:06:42 +0000162The initial probe index is computed as hash mod the table size.
Tim Petersea8f2bf2000-12-13 01:02:46 +0000163Subsequent probe indices use the values of x^i in GF(2^n)-{0} as an offset,
164where x is a root. The initial offset is derived from hash, too.
Guido van Rossum2bc13791999-03-24 19:06:42 +0000165
166All arithmetic on hash should ignore overflow.
Guido van Rossum16e93a81997-01-28 00:00:11 +0000167
168(This version is due to Reimer Behrends, some ideas are also due to
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000169Jyrki Alakuijala and Vladimir Marangozov.)
Fred Drake1bff34a2000-08-31 19:31:38 +0000170
171This function must never return NULL; failures are indicated by returning
172a dictentry* for which the me_value field is NULL. Exceptions are never
173reported by this function, and outstanding exceptions are maintained.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000174*/
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000175static dictentry *
Tim Peters1f5871e2000-07-04 17:44:48 +0000176lookdict(dictobject *mp, PyObject *key, register long hash)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000177{
Guido van Rossum16e93a81997-01-28 00:00:11 +0000178 register int i;
179 register unsigned incr;
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000180 register dictentry *freeslot;
Guido van Rossum2095d241997-04-09 19:41:24 +0000181 register unsigned int mask = mp->ma_size-1;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000182 dictentry *ep0 = mp->ma_table;
183 register dictentry *ep;
Fred Drakec88b99c2000-08-31 19:04:07 +0000184 register int restore_error = 0;
185 register int checked_error = 0;
186 register int cmp;
187 PyObject *err_type, *err_value, *err_tb;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000188 /* We must come up with (i, incr) such that 0 <= i < ma_size
Tim Petersea8f2bf2000-12-13 01:02:46 +0000189 and 0 < incr < ma_size and both are a function of hash.
190 i is the initial table index and incr the initial probe offset. */
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000191 i = (~hash) & mask;
192 /* We use ~hash instead of hash, as degenerate hash functions, such
Guido van Rossum16e93a81997-01-28 00:00:11 +0000193 as for ints <sigh>, can have lots of leading zeros. It's not
Tim Petersea8f2bf2000-12-13 01:02:46 +0000194 really a performance risk, but better safe than sorry.
195 12-Dec-00 tim: so ~hash produces lots of leading ones instead --
196 what's the gain? */
Guido van Rossumefb46091997-01-29 15:53:56 +0000197 ep = &ep0[i];
Guido van Rossumc1c7b1a1998-10-06 16:01:14 +0000198 if (ep->me_key == NULL || ep->me_key == key)
Guido van Rossum7d181591997-01-16 21:06:45 +0000199 return ep;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000200 if (ep->me_key == dummy)
Guido van Rossum7d181591997-01-16 21:06:45 +0000201 freeslot = ep;
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000202 else {
Fred Drakec88b99c2000-08-31 19:04:07 +0000203 if (ep->me_hash == hash) {
204 /* error can't have been checked yet */
205 checked_error = 1;
206 if (PyErr_Occurred()) {
207 restore_error = 1;
208 PyErr_Fetch(&err_type, &err_value, &err_tb);
209 }
Guido van Rossumb9324202001-01-18 00:39:02 +0000210 cmp = PyObject_RichCompareBool(ep->me_key, key, Py_EQ);
211 if (cmp > 0) {
Fred Drakec88b99c2000-08-31 19:04:07 +0000212 if (restore_error)
213 PyErr_Restore(err_type, err_value,
214 err_tb);
215 return ep;
216 }
Guido van Rossumb9324202001-01-18 00:39:02 +0000217 else if (cmp < 0)
218 PyErr_Clear();
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000219 }
220 freeslot = NULL;
Guido van Rossum2a61e741997-01-18 07:55:05 +0000221 }
Guido van Rossum2bc13791999-03-24 19:06:42 +0000222 /* Derive incr from hash, just to make it more arbitrary. Note that
Guido van Rossum16e93a81997-01-28 00:00:11 +0000223 incr must not be 0, or we will get into an infinite loop.*/
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000224 incr = (hash ^ ((unsigned long)hash >> 3)) & mask;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000225 if (!incr)
226 incr = mask;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000227 for (;;) {
Guido van Rossumefb46091997-01-29 15:53:56 +0000228 ep = &ep0[(i+incr)&mask];
Guido van Rossum16e93a81997-01-28 00:00:11 +0000229 if (ep->me_key == NULL) {
Fred Drakec88b99c2000-08-31 19:04:07 +0000230 if (restore_error)
231 PyErr_Restore(err_type, err_value, err_tb);
Guido van Rossum16e93a81997-01-28 00:00:11 +0000232 if (freeslot != NULL)
233 return freeslot;
234 else
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000235 return ep;
236 }
Guido van Rossum16e93a81997-01-28 00:00:11 +0000237 if (ep->me_key == dummy) {
238 if (freeslot == NULL)
239 freeslot = ep;
240 }
Fred Drakec88b99c2000-08-31 19:04:07 +0000241 else if (ep->me_key == key) {
242 if (restore_error)
243 PyErr_Restore(err_type, err_value, err_tb);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000244 return ep;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000245 }
246 else if (ep->me_hash == hash) {
Fred Drakec88b99c2000-08-31 19:04:07 +0000247 if (!checked_error) {
248 checked_error = 1;
249 if (PyErr_Occurred()) {
250 restore_error = 1;
251 PyErr_Fetch(&err_type, &err_value,
252 &err_tb);
253 }
254 }
Guido van Rossumb9324202001-01-18 00:39:02 +0000255 cmp = PyObject_RichCompareBool(ep->me_key, key, Py_EQ);
256 if (cmp > 0) {
Fred Drakec88b99c2000-08-31 19:04:07 +0000257 if (restore_error)
258 PyErr_Restore(err_type, err_value,
259 err_tb);
260 return ep;
261 }
Guido van Rossumb9324202001-01-18 00:39:02 +0000262 else if (cmp < 0)
263 PyErr_Clear();
Guido van Rossum16e93a81997-01-28 00:00:11 +0000264 }
265 /* Cycle through GF(2^n)-{0} */
266 incr = incr << 1;
267 if (incr > mask)
Thomas Wouters7e474022000-07-16 12:04:32 +0000268 incr ^= mp->ma_poly; /* This will implicitly clear
Guido van Rossumf05fc711998-11-16 22:46:30 +0000269 the highest bit */
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000270 }
271}
272
273/*
Fred Drake1bff34a2000-08-31 19:31:38 +0000274 * Hacked up version of lookdict which can assume keys are always strings;
275 * this assumption allows testing for errors during PyObject_Compare() to
276 * be dropped; string-string comparisons never raise exceptions. This also
277 * means we don't need to go through PyObject_Compare(); we can always use
278 * the tp_compare slot of the string type object directly.
279 *
280 * This really only becomes meaningful if proper error handling in lookdict()
281 * is too expensive.
282 */
283static dictentry *
284lookdict_string(dictobject *mp, PyObject *key, register long hash)
285{
286 register int i;
287 register unsigned incr;
288 register dictentry *freeslot;
289 register unsigned int mask = mp->ma_size-1;
290 dictentry *ep0 = mp->ma_table;
291 register dictentry *ep;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000292 cmpfunc compare = PyString_Type.tp_compare;
Fred Drake1bff34a2000-08-31 19:31:38 +0000293
294 /* make sure this function doesn't have to handle non-string keys */
295 if (!PyString_Check(key)) {
296#ifdef SHOW_CONVERSION_COUNTS
297 ++converted;
298#endif
299 mp->ma_lookup = lookdict;
300 return lookdict(mp, key, hash);
301 }
302 /* We must come up with (i, incr) such that 0 <= i < ma_size
303 and 0 < incr < ma_size and both are a function of hash */
304 i = (~hash) & mask;
305 /* We use ~hash instead of hash, as degenerate hash functions, such
306 as for ints <sigh>, can have lots of leading zeros. It's not
307 really a performance risk, but better safe than sorry. */
308 ep = &ep0[i];
309 if (ep->me_key == NULL || ep->me_key == key)
310 return ep;
311 if (ep->me_key == dummy)
312 freeslot = ep;
313 else {
314 if (ep->me_hash == hash
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000315 && compare(ep->me_key, key) == 0) {
Fred Drake1bff34a2000-08-31 19:31:38 +0000316 return ep;
317 }
318 freeslot = NULL;
319 }
320 /* Derive incr from hash, just to make it more arbitrary. Note that
321 incr must not be 0, or we will get into an infinite loop.*/
322 incr = (hash ^ ((unsigned long)hash >> 3)) & mask;
323 if (!incr)
324 incr = mask;
325 for (;;) {
326 ep = &ep0[(i+incr)&mask];
327 if (ep->me_key == NULL) {
328 if (freeslot != NULL)
329 return freeslot;
330 else
331 return ep;
332 }
333 if (ep->me_key == dummy) {
334 if (freeslot == NULL)
335 freeslot = ep;
336 }
337 else if (ep->me_key == key
338 || (ep->me_hash == hash
339 && compare(ep->me_key, key) == 0)) {
340 return ep;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000341 }
Fred Drake1bff34a2000-08-31 19:31:38 +0000342 /* Cycle through GF(2^n)-{0} */
343 incr = incr << 1;
344 if (incr > mask)
345 incr ^= mp->ma_poly; /* This will implicitly clear
346 the highest bit */
347 }
348}
349
350/*
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000351Internal routine to insert a new item into the table.
352Used both by the internal resize routine and by the public insert routine.
353Eats a reference to key and one to value.
354*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000355static void
Tim Peters1f5871e2000-07-04 17:44:48 +0000356insertdict(register dictobject *mp, PyObject *key, long hash, PyObject *value)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000357{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000358 PyObject *old_value;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000359 register dictentry *ep;
Fred Drake1bff34a2000-08-31 19:31:38 +0000360 ep = (mp->ma_lookup)(mp, key, hash);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000361 if (ep->me_value != NULL) {
Guido van Rossumd7047b31995-01-02 19:07:15 +0000362 old_value = ep->me_value;
363 ep->me_value = value;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000364 Py_DECREF(old_value); /* which **CAN** re-enter */
365 Py_DECREF(key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000366 }
367 else {
368 if (ep->me_key == NULL)
369 mp->ma_fill++;
370 else
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000371 Py_DECREF(ep->me_key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000372 ep->me_key = key;
373 ep->me_hash = hash;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000374 ep->me_value = value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000375 mp->ma_used++;
376 }
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000377}
378
379/*
380Restructure the table by allocating a new table and reinserting all
381items again. When entries have been deleted, the new table may
382actually be smaller than the old one.
383*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000384static int
Tim Peters1f5871e2000-07-04 17:44:48 +0000385dictresize(dictobject *mp, int minused)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000386{
387 register int oldsize = mp->ma_size;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000388 register int newsize, newpoly;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000389 register dictentry *oldtable = mp->ma_table;
390 register dictentry *newtable;
391 register dictentry *ep;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000392 register int i;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000393 for (i = 0, newsize = MINSIZE; ; i++, newsize <<= 1) {
394 if (i > sizeof(polys)/sizeof(polys[0])) {
395 /* Ran out of polynomials */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000396 PyErr_NoMemory();
Guido van Rossum1d5735e1994-08-30 08:27:36 +0000397 return -1;
398 }
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000399 if (newsize > minused) {
Guido van Rossum16e93a81997-01-28 00:00:11 +0000400 newpoly = polys[i];
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000401 break;
402 }
403 }
Guido van Rossumb18618d2000-05-03 23:44:39 +0000404 newtable = PyMem_NEW(dictentry, newsize);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000405 if (newtable == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000406 PyErr_NoMemory();
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000407 return -1;
408 }
Guido van Rossum0fd00331998-07-16 15:06:13 +0000409 memset(newtable, '\0', sizeof(dictentry) * newsize);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000410 mp->ma_size = newsize;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000411 mp->ma_poly = newpoly;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000412 mp->ma_table = newtable;
413 mp->ma_fill = 0;
414 mp->ma_used = 0;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000415
416 /* Make two passes, so we can avoid decrefs
417 (and possible side effects) till the table is copied */
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000418 for (i = 0, ep = oldtable; i < oldsize; i++, ep++) {
419 if (ep->me_value != NULL)
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000420 insertdict(mp,ep->me_key,ep->me_hash,ep->me_value);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000421 }
Guido van Rossumd7047b31995-01-02 19:07:15 +0000422 for (i = 0, ep = oldtable; i < oldsize; i++, ep++) {
Guido van Rossum255443b1998-04-10 22:47:14 +0000423 if (ep->me_value == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000424 Py_XDECREF(ep->me_key);
Guido van Rossum255443b1998-04-10 22:47:14 +0000425 }
Guido van Rossumd7047b31995-01-02 19:07:15 +0000426 }
427
Guido van Rossumb18618d2000-05-03 23:44:39 +0000428 if (oldtable != NULL)
429 PyMem_DEL(oldtable);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000430 return 0;
431}
432
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000433PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000434PyDict_GetItem(PyObject *op, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000435{
436 long hash;
Fred Drake1bff34a2000-08-31 19:31:38 +0000437 dictobject *mp = (dictobject *)op;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000438 if (!PyDict_Check(op)) {
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000439 return NULL;
440 }
Fred Drake1bff34a2000-08-31 19:31:38 +0000441 if (mp->ma_table == NULL)
Guido van Rossumd7047b31995-01-02 19:07:15 +0000442 return NULL;
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000443#ifdef CACHE_HASH
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000444 if (!PyString_Check(key) ||
445 (hash = ((PyStringObject *) key)->ob_shash) == -1)
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000446#endif
Guido van Rossumca756f21997-01-23 19:39:29 +0000447 {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000448 hash = PyObject_Hash(key);
Guido van Rossum474b19e1998-05-14 01:00:51 +0000449 if (hash == -1) {
450 PyErr_Clear();
Guido van Rossumca756f21997-01-23 19:39:29 +0000451 return NULL;
Guido van Rossum474b19e1998-05-14 01:00:51 +0000452 }
Guido van Rossumca756f21997-01-23 19:39:29 +0000453 }
Fred Drake1bff34a2000-08-31 19:31:38 +0000454 return (mp->ma_lookup)(mp, key, hash)->me_value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000455}
456
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000457/* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
458 * dictionary if it is merely replacing the value for an existing key.
459 * This is means that it's safe to loop over a dictionary with
460 * PyDict_Next() and occasionally replace a value -- but you can't
461 * insert new keys or remove them.
462 */
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000463int
Tim Peters1f5871e2000-07-04 17:44:48 +0000464PyDict_SetItem(register PyObject *op, PyObject *key, PyObject *value)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000465{
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000466 register dictobject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000467 register long hash;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000468 register int n_used;
469
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000470 if (!PyDict_Check(op)) {
471 PyErr_BadInternalCall();
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000472 return -1;
473 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000474 mp = (dictobject *)op;
Guido van Rossum2a61e741997-01-18 07:55:05 +0000475#ifdef CACHE_HASH
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000476 if (PyString_Check(key)) {
Guido van Rossum2a61e741997-01-18 07:55:05 +0000477#ifdef INTERN_STRINGS
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000478 if (((PyStringObject *)key)->ob_sinterned != NULL) {
479 key = ((PyStringObject *)key)->ob_sinterned;
480 hash = ((PyStringObject *)key)->ob_shash;
Guido van Rossum2a61e741997-01-18 07:55:05 +0000481 }
482 else
483#endif
484 {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000485 hash = ((PyStringObject *)key)->ob_shash;
Guido van Rossum2a61e741997-01-18 07:55:05 +0000486 if (hash == -1)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000487 hash = PyObject_Hash(key);
Guido van Rossum2a61e741997-01-18 07:55:05 +0000488 }
489 }
490 else
491#endif
492 {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000493 hash = PyObject_Hash(key);
Guido van Rossum2a61e741997-01-18 07:55:05 +0000494 if (hash == -1)
495 return -1;
Guido van Rossum2a61e741997-01-18 07:55:05 +0000496 }
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000497 if (mp->ma_fill >= mp->ma_size) {
498 /* No room for a new key.
499 * This only happens when the dict is empty.
500 * Let dictresize() create a minimal dict.
501 */
502 assert(mp->ma_used == 0);
503 if (dictresize(mp, 0) != 0)
504 return -1;
505 assert(mp->ma_fill < mp->ma_size);
506 }
507 n_used = mp->ma_used;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000508 Py_INCREF(value);
509 Py_INCREF(key);
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000510 insertdict(mp, key, hash, value);
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000511 /* If we added a key, we can safely resize. Otherwise skip this!
512 * If fill >= 2/3 size, adjust size. Normally, this doubles the
513 * size, but it's also possible for the dict to shrink (if ma_fill is
514 * much larger than ma_used, meaning a lot of dict keys have been
515 * deleted).
516 */
517 if (mp->ma_used > n_used && mp->ma_fill*3 >= mp->ma_size*2) {
518 if (dictresize(mp, mp->ma_used*2) != 0)
519 return -1;
520 }
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000521 return 0;
522}
523
524int
Tim Peters1f5871e2000-07-04 17:44:48 +0000525PyDict_DelItem(PyObject *op, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000526{
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000527 register dictobject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000528 register long hash;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000529 register dictentry *ep;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000530 PyObject *old_value, *old_key;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000531
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000532 if (!PyDict_Check(op)) {
533 PyErr_BadInternalCall();
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000534 return -1;
535 }
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000536#ifdef CACHE_HASH
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000537 if (!PyString_Check(key) ||
538 (hash = ((PyStringObject *) key)->ob_shash) == -1)
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000539#endif
Guido van Rossumca756f21997-01-23 19:39:29 +0000540 {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000541 hash = PyObject_Hash(key);
Guido van Rossumca756f21997-01-23 19:39:29 +0000542 if (hash == -1)
543 return -1;
544 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000545 mp = (dictobject *)op;
546 if (((dictobject *)op)->ma_table == NULL)
Guido van Rossumefc87131995-01-02 19:42:39 +0000547 goto empty;
Fred Drake1bff34a2000-08-31 19:31:38 +0000548 ep = (mp->ma_lookup)(mp, key, hash);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000549 if (ep->me_value == NULL) {
Guido van Rossumefc87131995-01-02 19:42:39 +0000550 empty:
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000551 PyErr_SetObject(PyExc_KeyError, key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000552 return -1;
553 }
Guido van Rossumd7047b31995-01-02 19:07:15 +0000554 old_key = ep->me_key;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000555 Py_INCREF(dummy);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000556 ep->me_key = dummy;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000557 old_value = ep->me_value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000558 ep->me_value = NULL;
559 mp->ma_used--;
Tim Petersea8f2bf2000-12-13 01:02:46 +0000560 Py_DECREF(old_value);
561 Py_DECREF(old_key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000562 return 0;
563}
564
Guido van Rossum25831651993-05-19 14:50:45 +0000565void
Tim Peters1f5871e2000-07-04 17:44:48 +0000566PyDict_Clear(PyObject *op)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000567{
Guido van Rossumd7047b31995-01-02 19:07:15 +0000568 int i, n;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000569 register dictentry *table;
570 dictobject *mp;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000571 if (!PyDict_Check(op))
Guido van Rossum25831651993-05-19 14:50:45 +0000572 return;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000573 mp = (dictobject *)op;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000574 table = mp->ma_table;
575 if (table == NULL)
576 return;
577 n = mp->ma_size;
578 mp->ma_size = mp->ma_used = mp->ma_fill = 0;
579 mp->ma_table = NULL;
580 for (i = 0; i < n; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000581 Py_XDECREF(table[i].me_key);
582 Py_XDECREF(table[i].me_value);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000583 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000584 PyMem_DEL(table);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000585}
586
Tim Peters67830702001-03-21 19:23:56 +0000587/* CAUTION: In general, it isn't safe to use PyDict_Next in a loop that
588 * mutates the dict. One exception: it is safe if the loop merely changes
589 * the values associated with the keys (but doesn't insert new keys or
590 * delete keys), via PyDict_SetItem().
591 */
Guido van Rossum25831651993-05-19 14:50:45 +0000592int
Tim Peters1f5871e2000-07-04 17:44:48 +0000593PyDict_Next(PyObject *op, int *ppos, PyObject **pkey, PyObject **pvalue)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000594{
Guido van Rossum25831651993-05-19 14:50:45 +0000595 int i;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000596 register dictobject *mp;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000597 if (!PyDict_Check(op))
Guido van Rossum25831651993-05-19 14:50:45 +0000598 return 0;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000599 mp = (dictobject *)op;
Guido van Rossum25831651993-05-19 14:50:45 +0000600 i = *ppos;
601 if (i < 0)
602 return 0;
603 while (i < mp->ma_size && mp->ma_table[i].me_value == NULL)
604 i++;
605 *ppos = i+1;
606 if (i >= mp->ma_size)
607 return 0;
608 if (pkey)
609 *pkey = mp->ma_table[i].me_key;
610 if (pvalue)
611 *pvalue = mp->ma_table[i].me_value;
612 return 1;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000613}
614
615/* Methods */
616
617static void
Tim Peters1f5871e2000-07-04 17:44:48 +0000618dict_dealloc(register dictobject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000619{
620 register int i;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000621 register dictentry *ep;
Guido van Rossumd724b232000-03-13 16:01:29 +0000622 Py_TRASHCAN_SAFE_BEGIN(mp)
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +0000623 PyObject_GC_Fini(mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000624 for (i = 0, ep = mp->ma_table; i < mp->ma_size; i++, ep++) {
Guido van Rossum255443b1998-04-10 22:47:14 +0000625 if (ep->me_key != NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000626 Py_DECREF(ep->me_key);
Guido van Rossum255443b1998-04-10 22:47:14 +0000627 }
628 if (ep->me_value != NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000629 Py_DECREF(ep->me_value);
Guido van Rossum255443b1998-04-10 22:47:14 +0000630 }
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000631 }
Guido van Rossumb18618d2000-05-03 23:44:39 +0000632 if (mp->ma_table != NULL)
633 PyMem_DEL(mp->ma_table);
Guido van Rossum4cc6ac72000-07-01 01:00:38 +0000634 mp = (dictobject *) PyObject_AS_GC(mp);
Guido van Rossumb18618d2000-05-03 23:44:39 +0000635 PyObject_DEL(mp);
Guido van Rossumd724b232000-03-13 16:01:29 +0000636 Py_TRASHCAN_SAFE_END(mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000637}
638
639static int
Tim Peters1f5871e2000-07-04 17:44:48 +0000640dict_print(register dictobject *mp, register FILE *fp, register int flags)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000641{
642 register int i;
643 register int any;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000644 register dictentry *ep;
Guido van Rossum255443b1998-04-10 22:47:14 +0000645
646 i = Py_ReprEnter((PyObject*)mp);
647 if (i != 0) {
648 if (i < 0)
649 return i;
650 fprintf(fp, "{...}");
651 return 0;
652 }
653
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000654 fprintf(fp, "{");
655 any = 0;
656 for (i = 0, ep = mp->ma_table; i < mp->ma_size; i++, ep++) {
657 if (ep->me_value != NULL) {
658 if (any++ > 0)
659 fprintf(fp, ", ");
Guido van Rossum255443b1998-04-10 22:47:14 +0000660 if (PyObject_Print((PyObject *)ep->me_key, fp, 0)!=0) {
661 Py_ReprLeave((PyObject*)mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000662 return -1;
Guido van Rossum255443b1998-04-10 22:47:14 +0000663 }
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000664 fprintf(fp, ": ");
Guido van Rossum255443b1998-04-10 22:47:14 +0000665 if (PyObject_Print(ep->me_value, fp, 0) != 0) {
666 Py_ReprLeave((PyObject*)mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000667 return -1;
Guido van Rossum255443b1998-04-10 22:47:14 +0000668 }
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000669 }
670 }
671 fprintf(fp, "}");
Guido van Rossum255443b1998-04-10 22:47:14 +0000672 Py_ReprLeave((PyObject*)mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000673 return 0;
674}
675
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000676static PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000677dict_repr(dictobject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000678{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000679 auto PyObject *v;
680 PyObject *sepa, *colon;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000681 register int i;
682 register int any;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000683 register dictentry *ep;
Guido van Rossum255443b1998-04-10 22:47:14 +0000684
685 i = Py_ReprEnter((PyObject*)mp);
686 if (i != 0) {
687 if (i > 0)
688 return PyString_FromString("{...}");
689 return NULL;
690 }
691
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000692 v = PyString_FromString("{");
693 sepa = PyString_FromString(", ");
694 colon = PyString_FromString(": ");
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000695 any = 0;
Guido van Rossum1d5735e1994-08-30 08:27:36 +0000696 for (i = 0, ep = mp->ma_table; i < mp->ma_size && v; i++, ep++) {
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000697 if (ep->me_value != NULL) {
698 if (any++)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000699 PyString_Concat(&v, sepa);
700 PyString_ConcatAndDel(&v, PyObject_Repr(ep->me_key));
701 PyString_Concat(&v, colon);
702 PyString_ConcatAndDel(&v, PyObject_Repr(ep->me_value));
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000703 }
704 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000705 PyString_ConcatAndDel(&v, PyString_FromString("}"));
Guido van Rossum255443b1998-04-10 22:47:14 +0000706 Py_ReprLeave((PyObject*)mp);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000707 Py_XDECREF(sepa);
708 Py_XDECREF(colon);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000709 return v;
710}
711
712static int
Tim Peters1f5871e2000-07-04 17:44:48 +0000713dict_length(dictobject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000714{
715 return mp->ma_used;
716}
717
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000718static PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000719dict_subscript(dictobject *mp, register PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000720{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000721 PyObject *v;
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000722 long hash;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000723 if (mp->ma_table == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000724 PyErr_SetObject(PyExc_KeyError, key);
Guido van Rossumd7047b31995-01-02 19:07:15 +0000725 return NULL;
726 }
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000727#ifdef CACHE_HASH
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000728 if (!PyString_Check(key) ||
729 (hash = ((PyStringObject *) key)->ob_shash) == -1)
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000730#endif
Guido van Rossumca756f21997-01-23 19:39:29 +0000731 {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000732 hash = PyObject_Hash(key);
Guido van Rossumca756f21997-01-23 19:39:29 +0000733 if (hash == -1)
734 return NULL;
735 }
Fred Drake1bff34a2000-08-31 19:31:38 +0000736 v = (mp->ma_lookup)(mp, key, hash) -> me_value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000737 if (v == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000738 PyErr_SetObject(PyExc_KeyError, key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000739 else
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000740 Py_INCREF(v);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000741 return v;
742}
743
744static int
Tim Peters1f5871e2000-07-04 17:44:48 +0000745dict_ass_sub(dictobject *mp, PyObject *v, PyObject *w)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000746{
747 if (w == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000748 return PyDict_DelItem((PyObject *)mp, v);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000749 else
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000750 return PyDict_SetItem((PyObject *)mp, v, w);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000751}
752
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000753static PyMappingMethods dict_as_mapping = {
754 (inquiry)dict_length, /*mp_length*/
755 (binaryfunc)dict_subscript, /*mp_subscript*/
756 (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000757};
758
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000759static PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000760dict_keys(register dictobject *mp, PyObject *args)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000761{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000762 register PyObject *v;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000763 register int i, j, n;
764
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000765 if (!PyArg_NoArgs(args))
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000766 return NULL;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000767 again:
768 n = mp->ma_used;
769 v = PyList_New(n);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000770 if (v == NULL)
771 return NULL;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000772 if (n != mp->ma_used) {
773 /* Durnit. The allocations caused the dict to resize.
774 * Just start over, this shouldn't normally happen.
775 */
776 Py_DECREF(v);
777 goto again;
778 }
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000779 for (i = 0, j = 0; i < mp->ma_size; i++) {
780 if (mp->ma_table[i].me_value != NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000781 PyObject *key = mp->ma_table[i].me_key;
782 Py_INCREF(key);
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000783 PyList_SET_ITEM(v, j, key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000784 j++;
785 }
786 }
787 return v;
788}
789
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000790static PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000791dict_values(register dictobject *mp, PyObject *args)
Guido van Rossum25831651993-05-19 14:50:45 +0000792{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000793 register PyObject *v;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000794 register int i, j, n;
795
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000796 if (!PyArg_NoArgs(args))
Guido van Rossum25831651993-05-19 14:50:45 +0000797 return NULL;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000798 again:
799 n = mp->ma_used;
800 v = PyList_New(n);
Guido van Rossum25831651993-05-19 14:50:45 +0000801 if (v == NULL)
802 return NULL;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000803 if (n != mp->ma_used) {
804 /* Durnit. The allocations caused the dict to resize.
805 * Just start over, this shouldn't normally happen.
806 */
807 Py_DECREF(v);
808 goto again;
809 }
Guido van Rossum25831651993-05-19 14:50:45 +0000810 for (i = 0, j = 0; i < mp->ma_size; i++) {
811 if (mp->ma_table[i].me_value != NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000812 PyObject *value = mp->ma_table[i].me_value;
813 Py_INCREF(value);
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000814 PyList_SET_ITEM(v, j, value);
Guido van Rossum25831651993-05-19 14:50:45 +0000815 j++;
816 }
817 }
818 return v;
819}
820
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000821static PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000822dict_items(register dictobject *mp, PyObject *args)
Guido van Rossum25831651993-05-19 14:50:45 +0000823{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000824 register PyObject *v;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000825 register int i, j, n;
826 PyObject *item, *key, *value;
827
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000828 if (!PyArg_NoArgs(args))
Guido van Rossum25831651993-05-19 14:50:45 +0000829 return NULL;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000830 /* Preallocate the list of tuples, to avoid allocations during
831 * the loop over the items, which could trigger GC, which
832 * could resize the dict. :-(
833 */
834 again:
835 n = mp->ma_used;
836 v = PyList_New(n);
Guido van Rossum25831651993-05-19 14:50:45 +0000837 if (v == NULL)
838 return NULL;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000839 for (i = 0; i < n; i++) {
840 item = PyTuple_New(2);
841 if (item == NULL) {
842 Py_DECREF(v);
843 return NULL;
844 }
845 PyList_SET_ITEM(v, i, item);
846 }
847 if (n != mp->ma_used) {
848 /* Durnit. The allocations caused the dict to resize.
849 * Just start over, this shouldn't normally happen.
850 */
851 Py_DECREF(v);
852 goto again;
853 }
854 /* Nothing we do below makes any function calls. */
Guido van Rossum25831651993-05-19 14:50:45 +0000855 for (i = 0, j = 0; i < mp->ma_size; i++) {
856 if (mp->ma_table[i].me_value != NULL) {
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000857 key = mp->ma_table[i].me_key;
858 value = mp->ma_table[i].me_value;
859 item = PyList_GET_ITEM(v, j);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000860 Py_INCREF(key);
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000861 PyTuple_SET_ITEM(item, 0, key);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000862 Py_INCREF(value);
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000863 PyTuple_SET_ITEM(item, 1, value);
Guido van Rossum25831651993-05-19 14:50:45 +0000864 j++;
865 }
866 }
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000867 assert(j == n);
Guido van Rossum25831651993-05-19 14:50:45 +0000868 return v;
869}
870
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000871static PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000872dict_update(register dictobject *mp, PyObject *args)
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000873{
874 register int i;
875 dictobject *other;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000876 dictentry *entry;
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000877 if (!PyArg_Parse(args, "O!", &PyDict_Type, &other))
878 return NULL;
Jeremy Hylton1fb60882001-01-03 22:34:59 +0000879 if (other == mp || other->ma_used == 0)
880 goto done; /* a.update(a) or a.update({}); nothing to do */
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000881 /* Do one big resize at the start, rather than incrementally
882 resizing as we insert new items. Expect that there will be
883 no (or few) overlapping keys. */
884 if ((mp->ma_fill + other->ma_used)*3 >= mp->ma_size*2) {
885 if (dictresize(mp, (mp->ma_used + other->ma_used)*3/2) != 0)
886 return NULL;
887 }
888 for (i = 0; i < other->ma_size; i++) {
889 entry = &other->ma_table[i];
890 if (entry->me_value != NULL) {
891 Py_INCREF(entry->me_key);
892 Py_INCREF(entry->me_value);
893 insertdict(mp, entry->me_key, entry->me_hash,
894 entry->me_value);
895 }
896 }
897 done:
898 Py_INCREF(Py_None);
899 return Py_None;
900}
901
902static PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000903dict_copy(register dictobject *mp, PyObject *args)
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000904{
Jeremy Hyltona12c7a72000-03-30 22:27:31 +0000905 if (!PyArg_Parse(args, ""))
906 return NULL;
907 return PyDict_Copy((PyObject*)mp);
908}
909
910PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000911PyDict_Copy(PyObject *o)
Jeremy Hyltona12c7a72000-03-30 22:27:31 +0000912{
913 register dictobject *mp;
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000914 register int i;
915 dictobject *copy;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000916 dictentry *entry;
Jeremy Hyltona12c7a72000-03-30 22:27:31 +0000917
918 if (o == NULL || !PyDict_Check(o)) {
919 PyErr_BadInternalCall();
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000920 return NULL;
Jeremy Hyltona12c7a72000-03-30 22:27:31 +0000921 }
922 mp = (dictobject *)o;
Guido van Rossume3f5b9c1997-05-28 19:15:28 +0000923 copy = (dictobject *)PyDict_New();
924 if (copy == NULL)
925 return NULL;
926 if (mp->ma_used > 0) {
927 if (dictresize(copy, mp->ma_used*3/2) != 0)
928 return NULL;
929 for (i = 0; i < mp->ma_size; i++) {
930 entry = &mp->ma_table[i];
931 if (entry->me_value != NULL) {
932 Py_INCREF(entry->me_key);
933 Py_INCREF(entry->me_value);
934 insertdict(copy, entry->me_key, entry->me_hash,
935 entry->me_value);
936 }
937 }
938 }
939 return (PyObject *)copy;
940}
941
Guido van Rossum4199fac1993-11-05 10:18:44 +0000942int
Tim Peters1f5871e2000-07-04 17:44:48 +0000943PyDict_Size(PyObject *mp)
Guido van Rossum4199fac1993-11-05 10:18:44 +0000944{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000945 if (mp == NULL || !PyDict_Check(mp)) {
946 PyErr_BadInternalCall();
Guido van Rossumb376a4a1993-11-23 17:53:17 +0000947 return 0;
Guido van Rossum4199fac1993-11-05 10:18:44 +0000948 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000949 return ((dictobject *)mp)->ma_used;
Guido van Rossum4199fac1993-11-05 10:18:44 +0000950}
951
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000952PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000953PyDict_Keys(PyObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000954{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000955 if (mp == NULL || !PyDict_Check(mp)) {
956 PyErr_BadInternalCall();
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000957 return NULL;
958 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000959 return dict_keys((dictobject *)mp, (PyObject *)NULL);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000960}
961
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000962PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000963PyDict_Values(PyObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +0000964{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000965 if (mp == NULL || !PyDict_Check(mp)) {
966 PyErr_BadInternalCall();
Guido van Rossum25831651993-05-19 14:50:45 +0000967 return NULL;
968 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000969 return dict_values((dictobject *)mp, (PyObject *)NULL);
Guido van Rossum25831651993-05-19 14:50:45 +0000970}
971
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000972PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000973PyDict_Items(PyObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +0000974{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000975 if (mp == NULL || !PyDict_Check(mp)) {
976 PyErr_BadInternalCall();
Guido van Rossum25831651993-05-19 14:50:45 +0000977 return NULL;
978 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000979 return dict_items((dictobject *)mp, (PyObject *)NULL);
Guido van Rossum25831651993-05-19 14:50:45 +0000980}
981
Guido van Rossuma0a69b81996-12-05 21:55:55 +0000982/* Subroutine which returns the smallest key in a for which b's value
983 is different or absent. The value is returned too, through the
984 pval argument. No reference counts are incremented. */
985
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000986static PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000987characterize(dictobject *a, dictobject *b, PyObject **pval)
Guido van Rossuma0a69b81996-12-05 21:55:55 +0000988{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000989 PyObject *diff = NULL;
Guido van Rossumb9324202001-01-18 00:39:02 +0000990 int i, cmp;
Guido van Rossuma0a69b81996-12-05 21:55:55 +0000991
992 *pval = NULL;
993 for (i = 0; i < a->ma_size; i++) {
994 if (a->ma_table[i].me_value != NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000995 PyObject *key = a->ma_table[i].me_key;
996 PyObject *aval, *bval;
Guido van Rossumb9324202001-01-18 00:39:02 +0000997 if (diff != NULL) {
998 cmp = PyObject_RichCompareBool(diff, key, Py_LT);
999 if (cmp < 0)
1000 return NULL;
1001 if (cmp > 0)
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001002 continue;
Guido van Rossumb9324202001-01-18 00:39:02 +00001003 }
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001004 aval = a->ma_table[i].me_value;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001005 bval = PyDict_GetItem((PyObject *)b, key);
Guido van Rossumb9324202001-01-18 00:39:02 +00001006 if (bval == NULL)
1007 cmp = 0;
1008 else {
1009 cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
1010 if (cmp < 0)
1011 return NULL;
1012 }
1013 if (cmp == 0)
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001014 {
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001015 diff = key;
1016 *pval = aval;
1017 }
1018 }
1019 }
1020 return diff;
1021}
1022
1023static int
Tim Peters1f5871e2000-07-04 17:44:48 +00001024dict_compare(dictobject *a, dictobject *b)
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001025{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001026 PyObject *adiff, *bdiff, *aval, *bval;
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001027 int res;
1028
1029 /* Compare lengths first */
1030 if (a->ma_used < b->ma_used)
1031 return -1; /* a is shorter */
1032 else if (a->ma_used > b->ma_used)
1033 return 1; /* b is shorter */
1034 /* Same length -- check all keys */
1035 adiff = characterize(a, b, &aval);
Guido van Rossumb9324202001-01-18 00:39:02 +00001036 if (adiff == NULL && PyErr_Occurred())
Guido van Rossum5b2121b1997-05-23 00:01:41 +00001037 return -1;
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001038 if (adiff == NULL)
1039 return 0; /* a is a subset with the same length */
1040 bdiff = characterize(b, a, &bval);
Guido van Rossumb9324202001-01-18 00:39:02 +00001041 if (bdiff == NULL && PyErr_Occurred())
Guido van Rossum5b2121b1997-05-23 00:01:41 +00001042 return -1;
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001043 /* bdiff == NULL would be impossible now */
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001044 res = PyObject_Compare(adiff, bdiff);
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001045 if (res == 0)
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001046 res = PyObject_Compare(aval, bval);
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001047 return res;
1048}
1049
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001050static PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001051dict_has_key(register dictobject *mp, PyObject *args)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001052{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001053 PyObject *key;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001054 long hash;
1055 register long ok;
Fred Drake52fccfd2000-02-23 15:47:16 +00001056 if (!PyArg_ParseTuple(args, "O:has_key", &key))
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001057 return NULL;
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +00001058#ifdef CACHE_HASH
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001059 if (!PyString_Check(key) ||
1060 (hash = ((PyStringObject *) key)->ob_shash) == -1)
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +00001061#endif
Guido van Rossumca756f21997-01-23 19:39:29 +00001062 {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001063 hash = PyObject_Hash(key);
Guido van Rossumca756f21997-01-23 19:39:29 +00001064 if (hash == -1)
1065 return NULL;
1066 }
Fred Drake1bff34a2000-08-31 19:31:38 +00001067 ok = (mp->ma_size != 0
1068 && (mp->ma_lookup)(mp, key, hash)->me_value != NULL);
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001069 return PyInt_FromLong(ok);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001070}
1071
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001072static PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001073dict_get(register dictobject *mp, PyObject *args)
Barry Warsawc38c5da1997-10-06 17:49:20 +00001074{
1075 PyObject *key;
Barry Warsaw320ac331997-10-20 17:26:25 +00001076 PyObject *failobj = Py_None;
Barry Warsawc38c5da1997-10-06 17:49:20 +00001077 PyObject *val = NULL;
1078 long hash;
1079
Fred Drake52fccfd2000-02-23 15:47:16 +00001080 if (!PyArg_ParseTuple(args, "O|O:get", &key, &failobj))
Barry Warsawc38c5da1997-10-06 17:49:20 +00001081 return NULL;
Guido van Rossum6fcfa721997-10-20 20:10:00 +00001082 if (mp->ma_table == NULL)
1083 goto finally;
Barry Warsawc38c5da1997-10-06 17:49:20 +00001084
Barry Warsawc38c5da1997-10-06 17:49:20 +00001085#ifdef CACHE_HASH
1086 if (!PyString_Check(key) ||
1087 (hash = ((PyStringObject *) key)->ob_shash) == -1)
1088#endif
1089 {
1090 hash = PyObject_Hash(key);
1091 if (hash == -1)
1092 return NULL;
1093 }
Fred Drake1bff34a2000-08-31 19:31:38 +00001094 val = (mp->ma_lookup)(mp, key, hash)->me_value;
Barry Warsaw320ac331997-10-20 17:26:25 +00001095
Guido van Rossum6fcfa721997-10-20 20:10:00 +00001096 finally:
Barry Warsawc38c5da1997-10-06 17:49:20 +00001097 if (val == NULL)
1098 val = failobj;
1099 Py_INCREF(val);
1100 return val;
1101}
1102
1103
1104static PyObject *
Guido van Rossum164452c2000-08-08 16:12:54 +00001105dict_setdefault(register dictobject *mp, PyObject *args)
1106{
1107 PyObject *key;
1108 PyObject *failobj = Py_None;
1109 PyObject *val = NULL;
1110 long hash;
1111
1112 if (!PyArg_ParseTuple(args, "O|O:setdefault", &key, &failobj))
1113 return NULL;
1114 if (mp->ma_table == NULL)
1115 goto finally;
1116
1117#ifdef CACHE_HASH
1118 if (!PyString_Check(key) ||
1119 (hash = ((PyStringObject *) key)->ob_shash) == -1)
1120#endif
1121 {
1122 hash = PyObject_Hash(key);
1123 if (hash == -1)
1124 return NULL;
1125 }
Fred Drake1bff34a2000-08-31 19:31:38 +00001126 val = (mp->ma_lookup)(mp, key, hash)->me_value;
Guido van Rossum164452c2000-08-08 16:12:54 +00001127
1128 finally:
1129 if (val == NULL) {
1130 val = failobj;
1131 if (PyDict_SetItem((PyObject*)mp, key, failobj))
1132 val = NULL;
1133 }
1134 Py_XINCREF(val);
1135 return val;
1136}
1137
1138
1139static PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001140dict_clear(register dictobject *mp, PyObject *args)
Guido van Rossumfb8f1ca1997-03-21 21:55:12 +00001141{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001142 if (!PyArg_NoArgs(args))
Guido van Rossumfb8f1ca1997-03-21 21:55:12 +00001143 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001144 PyDict_Clear((PyObject *)mp);
1145 Py_INCREF(Py_None);
1146 return Py_None;
Guido van Rossumfb8f1ca1997-03-21 21:55:12 +00001147}
1148
Guido van Rossumba6ab842000-12-12 22:02:18 +00001149static PyObject *
1150dict_popitem(dictobject *mp, PyObject *args)
1151{
1152 int i = 0;
1153 dictentry *ep;
1154 PyObject *res;
1155
1156 if (!PyArg_NoArgs(args))
1157 return NULL;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001158 /* Allocate the result tuple first. Believe it or not,
1159 * this allocation could trigger a garbage collection which
1160 * could resize the dict, which would invalidate the pointer
1161 * (ep) into the dict calculated below.
1162 * So we have to do this first.
1163 */
1164 res = PyTuple_New(2);
1165 if (res == NULL)
1166 return NULL;
Guido van Rossume04eaec2001-04-16 00:02:32 +00001167 if (mp->ma_used == 0) {
1168 Py_DECREF(res);
1169 PyErr_SetString(PyExc_KeyError,
1170 "popitem(): dictionary is empty");
1171 return NULL;
1172 }
Guido van Rossumba6ab842000-12-12 22:02:18 +00001173 /* Set ep to "the first" dict entry with a value. We abuse the hash
1174 * field of slot 0 to hold a search finger:
1175 * If slot 0 has a value, use slot 0.
1176 * Else slot 0 is being used to hold a search finger,
1177 * and we use its hash value as the first index to look.
1178 */
1179 ep = &mp->ma_table[0];
1180 if (ep->me_value == NULL) {
1181 i = (int)ep->me_hash;
1182 /* The hash field may be uninitialized trash, or it
1183 * may be a real hash value, or it may be a legit
1184 * search finger, or it may be a once-legit search
1185 * finger that's out of bounds now because it
1186 * wrapped around or the table shrunk -- simply
1187 * make sure it's in bounds now.
1188 */
1189 if (i >= mp->ma_size || i < 1)
1190 i = 1; /* skip slot 0 */
1191 while ((ep = &mp->ma_table[i])->me_value == NULL) {
1192 i++;
1193 if (i >= mp->ma_size)
1194 i = 1;
1195 }
1196 }
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001197 PyTuple_SET_ITEM(res, 0, ep->me_key);
1198 PyTuple_SET_ITEM(res, 1, ep->me_value);
1199 Py_INCREF(dummy);
1200 ep->me_key = dummy;
1201 ep->me_value = NULL;
1202 mp->ma_used--;
1203 assert(mp->ma_table[0].me_value == NULL);
1204 mp->ma_table[0].me_hash = i + 1; /* next place to start */
Guido van Rossumba6ab842000-12-12 22:02:18 +00001205 return res;
1206}
1207
Jeremy Hylton8caad492000-06-23 14:18:11 +00001208static int
1209dict_traverse(PyObject *op, visitproc visit, void *arg)
1210{
1211 int i = 0, err;
1212 PyObject *pk;
1213 PyObject *pv;
1214
1215 while (PyDict_Next(op, &i, &pk, &pv)) {
1216 err = visit(pk, arg);
1217 if (err)
1218 return err;
1219 err = visit(pv, arg);
1220 if (err)
1221 return err;
1222 }
1223 return 0;
1224}
1225
1226static int
1227dict_tp_clear(PyObject *op)
1228{
1229 PyDict_Clear(op);
1230 return 0;
1231}
1232
Tim Petersf7f88b12000-12-13 23:18:45 +00001233
Guido van Rossum09e563a2001-05-01 12:10:21 +00001234staticforward PyObject *dictiter_new(dictobject *, binaryfunc);
1235
1236static PyObject *
1237select_key(PyObject *key, PyObject *value)
1238{
1239 Py_INCREF(key);
1240 return key;
1241}
1242
1243static PyObject *
1244select_value(PyObject *key, PyObject *value)
1245{
1246 Py_INCREF(value);
1247 return value;
1248}
1249
1250static PyObject *
1251select_item(PyObject *key, PyObject *value)
1252{
1253 PyObject *res = PyTuple_New(2);
1254
1255 if (res != NULL) {
1256 Py_INCREF(key);
1257 Py_INCREF(value);
1258 PyTuple_SET_ITEM(res, 0, key);
1259 PyTuple_SET_ITEM(res, 1, value);
1260 }
1261 return res;
1262}
1263
1264static PyObject *
1265dict_iterkeys(dictobject *dict, PyObject *args)
1266{
1267 if (!PyArg_ParseTuple(args, ""))
1268 return NULL;
1269 return dictiter_new(dict, select_key);
1270}
1271
1272static PyObject *
1273dict_itervalues(dictobject *dict, PyObject *args)
1274{
1275 if (!PyArg_ParseTuple(args, ""))
1276 return NULL;
1277 return dictiter_new(dict, select_value);
1278}
1279
1280static PyObject *
1281dict_iteritems(dictobject *dict, PyObject *args)
1282{
1283 if (!PyArg_ParseTuple(args, ""))
1284 return NULL;
1285 return dictiter_new(dict, select_item);
1286}
1287
1288
Tim Petersf7f88b12000-12-13 23:18:45 +00001289static char has_key__doc__[] =
1290"D.has_key(k) -> 1 if D has a key k, else 0";
1291
1292static char get__doc__[] =
1293"D.get(k[,d]) -> D[k] if D.has_key(k), else d. d defaults to None.";
1294
1295static char setdefault_doc__[] =
1296"D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if not D.has_key(k)";
1297
1298static char popitem__doc__[] =
1299"D.popitem() -> (k, v), remove and return some (key, value) pair as a\n\
13002-tuple; but raise KeyError if D is empty";
1301
1302static char keys__doc__[] =
1303"D.keys() -> list of D's keys";
1304
1305static char items__doc__[] =
1306"D.items() -> list of D's (key, value) pairs, as 2-tuples";
1307
1308static char values__doc__[] =
1309"D.values() -> list of D's values";
1310
1311static char update__doc__[] =
1312"D.update(E) -> None. Update D from E: for k in E.keys(): D[k] = E[k]";
1313
1314static char clear__doc__[] =
1315"D.clear() -> None. Remove all items from D.";
1316
1317static char copy__doc__[] =
1318"D.copy() -> a shallow copy of D";
1319
Guido van Rossum09e563a2001-05-01 12:10:21 +00001320static char iterkeys__doc__[] =
1321"D.iterkeys() -> an iterator over the keys of D";
1322
1323static char itervalues__doc__[] =
1324"D.itervalues() -> an iterator over the values of D";
1325
1326static char iteritems__doc__[] =
1327"D.iteritems() -> an iterator over the (key, value) items of D";
1328
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001329static PyMethodDef mapp_methods[] = {
Tim Petersf7f88b12000-12-13 23:18:45 +00001330 {"has_key", (PyCFunction)dict_has_key, METH_VARARGS,
1331 has_key__doc__},
1332 {"get", (PyCFunction)dict_get, METH_VARARGS,
1333 get__doc__},
1334 {"setdefault", (PyCFunction)dict_setdefault, METH_VARARGS,
1335 setdefault_doc__},
1336 {"popitem", (PyCFunction)dict_popitem, METH_OLDARGS,
1337 popitem__doc__},
1338 {"keys", (PyCFunction)dict_keys, METH_OLDARGS,
1339 keys__doc__},
1340 {"items", (PyCFunction)dict_items, METH_OLDARGS,
1341 items__doc__},
1342 {"values", (PyCFunction)dict_values, METH_OLDARGS,
1343 values__doc__},
1344 {"update", (PyCFunction)dict_update, METH_OLDARGS,
1345 update__doc__},
1346 {"clear", (PyCFunction)dict_clear, METH_OLDARGS,
1347 clear__doc__},
1348 {"copy", (PyCFunction)dict_copy, METH_OLDARGS,
1349 copy__doc__},
Guido van Rossum09e563a2001-05-01 12:10:21 +00001350 {"iterkeys", (PyCFunction)dict_iterkeys, METH_VARARGS,
1351 iterkeys__doc__},
1352 {"itervalues", (PyCFunction)dict_itervalues, METH_VARARGS,
1353 itervalues__doc__},
1354 {"iteritems", (PyCFunction)dict_iteritems, METH_VARARGS,
1355 iteritems__doc__},
Tim Petersf7f88b12000-12-13 23:18:45 +00001356 {NULL, NULL} /* sentinel */
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001357};
1358
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001359static PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001360dict_getattr(dictobject *mp, char *name)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001361{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001362 return Py_FindMethod(mapp_methods, (PyObject *)mp, name);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001363}
1364
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00001365static int
1366dict_contains(dictobject *mp, PyObject *key)
1367{
1368 long hash;
1369
1370#ifdef CACHE_HASH
1371 if (!PyString_Check(key) ||
1372 (hash = ((PyStringObject *) key)->ob_shash) == -1)
1373#endif
1374 {
1375 hash = PyObject_Hash(key);
1376 if (hash == -1)
1377 return -1;
1378 }
1379 return (mp->ma_size != 0
1380 && (mp->ma_lookup)(mp, key, hash)->me_value != NULL);
1381}
1382
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00001383/* Hack to implement "key in dict" */
1384static PySequenceMethods dict_as_sequence = {
1385 0, /* sq_length */
1386 0, /* sq_concat */
1387 0, /* sq_repeat */
1388 0, /* sq_item */
1389 0, /* sq_slice */
1390 0, /* sq_ass_item */
1391 0, /* sq_ass_slice */
1392 (objobjproc)dict_contains, /* sq_contains */
1393 0, /* sq_inplace_concat */
1394 0, /* sq_inplace_repeat */
1395};
1396
Guido van Rossum09e563a2001-05-01 12:10:21 +00001397static PyObject *
1398dict_iter(dictobject *dict)
1399{
1400 return dictiter_new(dict, select_key);
1401}
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00001402
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001403PyTypeObject PyDict_Type = {
1404 PyObject_HEAD_INIT(&PyType_Type)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001405 0,
Guido van Rossum9bfef441993-03-29 10:43:31 +00001406 "dictionary",
Jeremy Hyltonc5007aa2000-06-30 05:02:53 +00001407 sizeof(dictobject) + PyGC_HEAD_SIZE,
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001408 0,
Guido van Rossumb9324202001-01-18 00:39:02 +00001409 (destructor)dict_dealloc, /* tp_dealloc */
1410 (printfunc)dict_print, /* tp_print */
1411 (getattrfunc)dict_getattr, /* tp_getattr */
1412 0, /* tp_setattr */
1413 (cmpfunc)dict_compare, /* tp_compare */
1414 (reprfunc)dict_repr, /* tp_repr */
1415 0, /* tp_as_number */
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00001416 &dict_as_sequence, /* tp_as_sequence */
Guido van Rossumb9324202001-01-18 00:39:02 +00001417 &dict_as_mapping, /* tp_as_mapping */
1418 0, /* tp_hash */
1419 0, /* tp_call */
1420 0, /* tp_str */
1421 0, /* tp_getattro */
1422 0, /* tp_setattro */
1423 0, /* tp_as_buffer */
1424 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_GC, /* tp_flags */
1425 0, /* tp_doc */
1426 (traverseproc)dict_traverse, /* tp_traverse */
1427 (inquiry)dict_tp_clear, /* tp_clear */
1428 0, /* tp_richcompare */
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00001429 0, /* tp_weaklistoffset */
Guido van Rossum09e563a2001-05-01 12:10:21 +00001430 (getiterfunc)dict_iter, /* tp_iter */
Guido van Rossum213c7a62001-04-23 14:08:49 +00001431 0, /* tp_iternext */
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001432};
1433
Guido van Rossum3cca2451997-05-16 14:23:33 +00001434/* For backward compatibility with old dictionary interface */
1435
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001436PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001437PyDict_GetItemString(PyObject *v, char *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001438{
Guido van Rossum3cca2451997-05-16 14:23:33 +00001439 PyObject *kv, *rv;
1440 kv = PyString_FromString(key);
1441 if (kv == NULL)
1442 return NULL;
Guido van Rossum3cca2451997-05-16 14:23:33 +00001443 rv = PyDict_GetItem(v, kv);
1444 Py_DECREF(kv);
1445 return rv;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001446}
1447
1448int
Tim Peters1f5871e2000-07-04 17:44:48 +00001449PyDict_SetItemString(PyObject *v, char *key, PyObject *item)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001450{
Guido van Rossum3cca2451997-05-16 14:23:33 +00001451 PyObject *kv;
1452 int err;
1453 kv = PyString_FromString(key);
1454 if (kv == NULL)
Guido van Rossum037b2201997-05-20 18:35:19 +00001455 return -1;
Guido van Rossum4f3bf1e1997-09-29 23:31:11 +00001456 PyString_InternInPlace(&kv); /* XXX Should we really? */
Guido van Rossum3cca2451997-05-16 14:23:33 +00001457 err = PyDict_SetItem(v, kv, item);
1458 Py_DECREF(kv);
1459 return err;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001460}
1461
1462int
Tim Peters1f5871e2000-07-04 17:44:48 +00001463PyDict_DelItemString(PyObject *v, char *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001464{
Guido van Rossum3cca2451997-05-16 14:23:33 +00001465 PyObject *kv;
1466 int err;
1467 kv = PyString_FromString(key);
1468 if (kv == NULL)
Guido van Rossum037b2201997-05-20 18:35:19 +00001469 return -1;
Guido van Rossum3cca2451997-05-16 14:23:33 +00001470 err = PyDict_DelItem(v, kv);
1471 Py_DECREF(kv);
1472 return err;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001473}
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00001474
1475/* Dictionary iterator type */
1476
1477extern PyTypeObject PyDictIter_Type; /* Forward */
1478
1479typedef struct {
1480 PyObject_HEAD
1481 dictobject *di_dict;
1482 int di_size;
1483 int di_pos;
Guido van Rossum09e563a2001-05-01 12:10:21 +00001484 binaryfunc di_select;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00001485} dictiterobject;
1486
1487static PyObject *
Guido van Rossum09e563a2001-05-01 12:10:21 +00001488dictiter_new(dictobject *dict, binaryfunc select)
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00001489{
1490 dictiterobject *di;
1491 di = PyObject_NEW(dictiterobject, &PyDictIter_Type);
1492 if (di == NULL)
1493 return NULL;
1494 Py_INCREF(dict);
1495 di->di_dict = dict;
1496 di->di_size = dict->ma_size;
1497 di->di_pos = 0;
Guido van Rossum09e563a2001-05-01 12:10:21 +00001498 di->di_select = select;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00001499 return (PyObject *)di;
1500}
1501
1502static void
1503dictiter_dealloc(dictiterobject *di)
1504{
1505 Py_DECREF(di->di_dict);
1506 PyObject_DEL(di);
1507}
1508
1509static PyObject *
1510dictiter_next(dictiterobject *di, PyObject *args)
1511{
Guido van Rossum09e563a2001-05-01 12:10:21 +00001512 PyObject *key, *value;
Guido van Rossum213c7a62001-04-23 14:08:49 +00001513
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00001514 if (di->di_size != di->di_dict->ma_size) {
1515 PyErr_SetString(PyExc_RuntimeError,
1516 "dictionary changed size during iteration");
1517 return NULL;
1518 }
Guido van Rossum09e563a2001-05-01 12:10:21 +00001519 if (PyDict_Next((PyObject *)(di->di_dict), &di->di_pos, &key, &value)) {
1520 return (*di->di_select)(key, value);
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00001521 }
1522 PyErr_SetObject(PyExc_StopIteration, Py_None);
1523 return NULL;
1524}
1525
1526static PyObject *
1527dictiter_getiter(PyObject *it)
1528{
1529 Py_INCREF(it);
1530 return it;
1531}
1532
1533static PyMethodDef dictiter_methods[] = {
1534 {"next", (PyCFunction)dictiter_next, METH_VARARGS,
1535 "it.next() -- get the next value, or raise StopIteration"},
1536 {NULL, NULL} /* sentinel */
1537};
1538
1539static PyObject *
Guido van Rossum213c7a62001-04-23 14:08:49 +00001540dictiter_getattr(dictiterobject *di, char *name)
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00001541{
Guido van Rossum213c7a62001-04-23 14:08:49 +00001542 return Py_FindMethod(dictiter_methods, (PyObject *)di, name);
1543}
1544
1545static PyObject *dictiter_iternext(dictiterobject *di)
1546{
Guido van Rossum09e563a2001-05-01 12:10:21 +00001547 PyObject *key, *value;
Guido van Rossum213c7a62001-04-23 14:08:49 +00001548
1549 if (di->di_size != di->di_dict->ma_size) {
1550 PyErr_SetString(PyExc_RuntimeError,
1551 "dictionary changed size during iteration");
1552 return NULL;
1553 }
Guido van Rossum09e563a2001-05-01 12:10:21 +00001554 if (PyDict_Next((PyObject *)(di->di_dict), &di->di_pos, &key, &value)) {
1555 return (*di->di_select)(key, value);
Guido van Rossum213c7a62001-04-23 14:08:49 +00001556 }
1557 return NULL;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00001558}
1559
1560PyTypeObject PyDictIter_Type = {
1561 PyObject_HEAD_INIT(&PyType_Type)
1562 0, /* ob_size */
1563 "dictionary-iterator", /* tp_name */
1564 sizeof(dictiterobject), /* tp_basicsize */
1565 0, /* tp_itemsize */
1566 /* methods */
1567 (destructor)dictiter_dealloc, /* tp_dealloc */
1568 0, /* tp_print */
1569 (getattrfunc)dictiter_getattr, /* tp_getattr */
1570 0, /* tp_setattr */
1571 0, /* tp_compare */
1572 0, /* tp_repr */
1573 0, /* tp_as_number */
1574 0, /* tp_as_sequence */
1575 0, /* tp_as_mapping */
1576 0, /* tp_hash */
1577 0, /* tp_call */
1578 0, /* tp_str */
1579 0, /* tp_getattro */
1580 0, /* tp_setattro */
1581 0, /* tp_as_buffer */
1582 Py_TPFLAGS_DEFAULT, /* tp_flags */
1583 0, /* tp_doc */
1584 0, /* tp_traverse */
1585 0, /* tp_clear */
1586 0, /* tp_richcompare */
1587 0, /* tp_weaklistoffset */
1588 (getiterfunc)dictiter_getiter, /* tp_iter */
Guido van Rossum213c7a62001-04-23 14:08:49 +00001589 (iternextfunc)dictiter_iternext, /* tp_iternext */
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00001590};