blob: 013f5f2cb810d76fb7cf5973bf4efbd86048f1c6 [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
Raymond Hettinger930427b2003-05-03 06:51:59 +00004/* The distribution includes a separate file, Objects/dictnotes.txt,
5 describing explorations into dictionary design and optimization.
6 It covers typical dictionary use patterns, the parameters for
7 tuning dictionaries, and several ideas for possible optimizations.
8*/
9
Guido van Rossumc0b618a1997-05-02 03:12:38 +000010#include "Python.h"
Guido van Rossum4b1302b1993-03-27 18:11:32 +000011
Tim Peters6d6c1a32001-08-02 04:15:00 +000012typedef PyDictEntry dictentry;
13typedef PyDictObject dictobject;
Guido van Rossum16e93a81997-01-28 00:00:11 +000014
Tim Peterseb28ef22001-06-02 05:27:19 +000015/* Define this out if you don't want conversion statistics on exit. */
Fred Drake1bff34a2000-08-31 19:31:38 +000016#undef SHOW_CONVERSION_COUNTS
17
Tim Peterseb28ef22001-06-02 05:27:19 +000018/* See large comment block below. This must be >= 1. */
19#define PERTURB_SHIFT 5
20
Guido van Rossum16e93a81997-01-28 00:00:11 +000021/*
Tim Peterseb28ef22001-06-02 05:27:19 +000022Major subtleties ahead: Most hash schemes depend on having a "good" hash
23function, in the sense of simulating randomness. Python doesn't: its most
24important hash functions (for strings and ints) are very regular in common
25cases:
Tim Peters15d49292001-05-27 07:39:22 +000026
Tim Peterseb28ef22001-06-02 05:27:19 +000027>>> map(hash, (0, 1, 2, 3))
28[0, 1, 2, 3]
29>>> map(hash, ("namea", "nameb", "namec", "named"))
30[-1658398457, -1658398460, -1658398459, -1658398462]
31>>>
Tim Peters15d49292001-05-27 07:39:22 +000032
Tim Peterseb28ef22001-06-02 05:27:19 +000033This isn't necessarily bad! To the contrary, in a table of size 2**i, taking
34the low-order i bits as the initial table index is extremely fast, and there
35are no collisions at all for dicts indexed by a contiguous range of ints.
36The same is approximately true when keys are "consecutive" strings. So this
37gives better-than-random behavior in common cases, and that's very desirable.
Tim Peters15d49292001-05-27 07:39:22 +000038
Tim Peterseb28ef22001-06-02 05:27:19 +000039OTOH, when collisions occur, the tendency to fill contiguous slices of the
40hash table makes a good collision resolution strategy crucial. Taking only
41the last i bits of the hash code is also vulnerable: for example, consider
42[i << 16 for i in range(20000)] as a set of keys. Since ints are their own
43hash codes, and this fits in a dict of size 2**15, the last 15 bits of every
44hash code are all 0: they *all* map to the same table index.
Tim Peters15d49292001-05-27 07:39:22 +000045
Tim Peterseb28ef22001-06-02 05:27:19 +000046But catering to unusual cases should not slow the usual ones, so we just take
47the last i bits anyway. It's up to collision resolution to do the rest. If
48we *usually* find the key we're looking for on the first try (and, it turns
49out, we usually do -- the table load factor is kept under 2/3, so the odds
50are solidly in our favor), then it makes best sense to keep the initial index
51computation dirt cheap.
Tim Peters15d49292001-05-27 07:39:22 +000052
Tim Peterseb28ef22001-06-02 05:27:19 +000053The first half of collision resolution is to visit table indices via this
54recurrence:
Tim Peters15d49292001-05-27 07:39:22 +000055
Tim Peterseb28ef22001-06-02 05:27:19 +000056 j = ((5*j) + 1) mod 2**i
Tim Peters15d49292001-05-27 07:39:22 +000057
Tim Peterseb28ef22001-06-02 05:27:19 +000058For any initial j in range(2**i), repeating that 2**i times generates each
59int in range(2**i) exactly once (see any text on random-number generation for
60proof). By itself, this doesn't help much: like linear probing (setting
61j += 1, or j -= 1, on each loop trip), it scans the table entries in a fixed
62order. This would be bad, except that's not the only thing we do, and it's
63actually *good* in the common cases where hash keys are consecutive. In an
64example that's really too small to make this entirely clear, for a table of
65size 2**3 the order of indices is:
Tim Peters15d49292001-05-27 07:39:22 +000066
Tim Peterseb28ef22001-06-02 05:27:19 +000067 0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating]
68
69If two things come in at index 5, the first place we look after is index 2,
70not 6, so if another comes in at index 6 the collision at 5 didn't hurt it.
71Linear probing is deadly in this case because there the fixed probe order
72is the *same* as the order consecutive keys are likely to arrive. But it's
73extremely unlikely hash codes will follow a 5*j+1 recurrence by accident,
74and certain that consecutive hash codes do not.
75
76The other half of the strategy is to get the other bits of the hash code
77into play. This is done by initializing a (unsigned) vrbl "perturb" to the
78full hash code, and changing the recurrence to:
79
80 j = (5*j) + 1 + perturb;
81 perturb >>= PERTURB_SHIFT;
82 use j % 2**i as the next table index;
83
84Now the probe sequence depends (eventually) on every bit in the hash code,
85and the pseudo-scrambling property of recurring on 5*j+1 is more valuable,
86because it quickly magnifies small differences in the bits that didn't affect
87the initial index. Note that because perturb is unsigned, if the recurrence
88is executed often enough perturb eventually becomes and remains 0. At that
89point (very rarely reached) the recurrence is on (just) 5*j+1 again, and
90that's certain to find an empty slot eventually (since it generates every int
91in range(2**i), and we make sure there's always at least one empty slot).
92
93Selecting a good value for PERTURB_SHIFT is a balancing act. You want it
94small so that the high bits of the hash code continue to affect the probe
95sequence across iterations; but you want it large so that in really bad cases
96the high-order hash bits have an effect on early iterations. 5 was "the
97best" in minimizing total collisions across experiments Tim Peters ran (on
98both normal and pathological cases), but 4 and 6 weren't significantly worse.
99
100Historical: Reimer Behrends contributed the idea of using a polynomial-based
101approach, using repeated multiplication by x in GF(2**n) where an irreducible
102polynomial for each table size was chosen such that x was a primitive root.
103Christian Tismer later extended that to use division by x instead, as an
104efficient way to get the high bits of the hash code into play. This scheme
105also gave excellent collision statistics, but was more expensive: two
106if-tests were required inside the loop; computing "the next" index took about
107the same number of operations but without as much potential parallelism
108(e.g., computing 5*j can go on at the same time as computing 1+perturb in the
109above, and then shifting perturb can be done while the table index is being
110masked); and the dictobject struct required a member to hold the table's
111polynomial. In Tim's experiments the current scheme ran faster, produced
112equally good collision statistics, needed less code & used less memory.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000113*/
Tim Petersdea48ec2001-05-22 20:40:22 +0000114
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000115/* Object used as dummy key to fill deleted entries */
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000116static PyObject *dummy; /* Initialized by first call to newdictobject() */
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000117
Fred Drake1bff34a2000-08-31 19:31:38 +0000118/* forward declarations */
119static dictentry *
120lookdict_string(dictobject *mp, PyObject *key, long hash);
121
122#ifdef SHOW_CONVERSION_COUNTS
123static long created = 0L;
124static long converted = 0L;
125
126static void
127show_counts(void)
128{
129 fprintf(stderr, "created %ld string dicts\n", created);
130 fprintf(stderr, "converted %ld to normal dicts\n", converted);
131 fprintf(stderr, "%.2f%% conversion rate\n", (100.0*converted)/created);
132}
133#endif
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000134
Tim Peters6d6c1a32001-08-02 04:15:00 +0000135/* Initialization macros.
136 There are two ways to create a dict: PyDict_New() is the main C API
137 function, and the tp_new slot maps to dict_new(). In the latter case we
138 can save a little time over what PyDict_New does because it's guaranteed
139 that the PyDictObject struct is already zeroed out.
140 Everyone except dict_new() should use EMPTY_TO_MINSIZE (unless they have
141 an excellent reason not to).
142*/
143
144#define INIT_NONZERO_DICT_SLOTS(mp) do { \
Tim Petersdea48ec2001-05-22 20:40:22 +0000145 (mp)->ma_table = (mp)->ma_smalltable; \
Tim Peters6d6c1a32001-08-02 04:15:00 +0000146 (mp)->ma_mask = PyDict_MINSIZE - 1; \
147 } while(0)
148
149#define EMPTY_TO_MINSIZE(mp) do { \
150 memset((mp)->ma_smalltable, 0, sizeof((mp)->ma_smalltable)); \
Tim Petersdea48ec2001-05-22 20:40:22 +0000151 (mp)->ma_used = (mp)->ma_fill = 0; \
Tim Peters6d6c1a32001-08-02 04:15:00 +0000152 INIT_NONZERO_DICT_SLOTS(mp); \
Tim Petersdea48ec2001-05-22 20:40:22 +0000153 } while(0)
154
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000155PyObject *
Thomas Wouters78890102000-07-22 19:25:51 +0000156PyDict_New(void)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000157{
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000158 register dictobject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000159 if (dummy == NULL) { /* Auto-initialize dummy */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000160 dummy = PyString_FromString("<dummy key>");
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000161 if (dummy == NULL)
162 return NULL;
Fred Drake1bff34a2000-08-31 19:31:38 +0000163#ifdef SHOW_CONVERSION_COUNTS
164 Py_AtExit(show_counts);
165#endif
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000166 }
Neil Schemenauere83c00e2001-08-29 23:54:21 +0000167 mp = PyObject_GC_New(dictobject, &PyDict_Type);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000168 if (mp == NULL)
169 return NULL;
Tim Peters6d6c1a32001-08-02 04:15:00 +0000170 EMPTY_TO_MINSIZE(mp);
Fred Drake1bff34a2000-08-31 19:31:38 +0000171 mp->ma_lookup = lookdict_string;
172#ifdef SHOW_CONVERSION_COUNTS
173 ++created;
174#endif
Neil Schemenauere83c00e2001-08-29 23:54:21 +0000175 _PyObject_GC_TRACK(mp);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000176 return (PyObject *)mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000177}
178
179/*
180The basic lookup function used by all operations.
Guido van Rossum16e93a81997-01-28 00:00:11 +0000181This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000182Open addressing is preferred over chaining since the link overhead for
183chaining would be substantial (100% with typical malloc overhead).
184
Tim Peterseb28ef22001-06-02 05:27:19 +0000185The initial probe index is computed as hash mod the table size. Subsequent
186probe indices are computed as explained earlier.
Guido van Rossum2bc13791999-03-24 19:06:42 +0000187
188All arithmetic on hash should ignore overflow.
Guido van Rossum16e93a81997-01-28 00:00:11 +0000189
Tim Peterseb28ef22001-06-02 05:27:19 +0000190(The details in this version are due to Tim Peters, building on many past
191contributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and
192Christian Tismer).
Fred Drake1bff34a2000-08-31 19:31:38 +0000193
194This function must never return NULL; failures are indicated by returning
195a dictentry* for which the me_value field is NULL. Exceptions are never
196reported by this function, and outstanding exceptions are maintained.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000197*/
Tim Peterseb28ef22001-06-02 05:27:19 +0000198
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000199static dictentry *
Tim Peters1f5871e2000-07-04 17:44:48 +0000200lookdict(dictobject *mp, PyObject *key, register long hash)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000201{
Guido van Rossum16e93a81997-01-28 00:00:11 +0000202 register int i;
Tim Peterseb28ef22001-06-02 05:27:19 +0000203 register unsigned int perturb;
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000204 register dictentry *freeslot;
Tim Petersafb6ae82001-06-04 21:00:21 +0000205 register unsigned int mask = mp->ma_mask;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000206 dictentry *ep0 = mp->ma_table;
207 register dictentry *ep;
Tim Peters7b5d0af2001-06-03 04:14:43 +0000208 register int restore_error;
209 register int checked_error;
Fred Drakec88b99c2000-08-31 19:04:07 +0000210 register int cmp;
211 PyObject *err_type, *err_value, *err_tb;
Tim Peters453163d2001-06-03 04:54:32 +0000212 PyObject *startkey;
Tim Peterseb28ef22001-06-02 05:27:19 +0000213
Tim Peters2f228e72001-05-13 00:19:31 +0000214 i = hash & mask;
Guido van Rossumefb46091997-01-29 15:53:56 +0000215 ep = &ep0[i];
Guido van Rossumc1c7b1a1998-10-06 16:01:14 +0000216 if (ep->me_key == NULL || ep->me_key == key)
Guido van Rossum7d181591997-01-16 21:06:45 +0000217 return ep;
Tim Peters7b5d0af2001-06-03 04:14:43 +0000218
219 restore_error = checked_error = 0;
Guido van Rossum16e93a81997-01-28 00:00:11 +0000220 if (ep->me_key == dummy)
Guido van Rossum7d181591997-01-16 21:06:45 +0000221 freeslot = ep;
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000222 else {
Fred Drakec88b99c2000-08-31 19:04:07 +0000223 if (ep->me_hash == hash) {
224 /* error can't have been checked yet */
225 checked_error = 1;
226 if (PyErr_Occurred()) {
227 restore_error = 1;
228 PyErr_Fetch(&err_type, &err_value, &err_tb);
229 }
Tim Peters453163d2001-06-03 04:54:32 +0000230 startkey = ep->me_key;
231 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Tim Peters7b5d0af2001-06-03 04:14:43 +0000232 if (cmp < 0)
Guido van Rossumb9324202001-01-18 00:39:02 +0000233 PyErr_Clear();
Tim Peters453163d2001-06-03 04:54:32 +0000234 if (ep0 == mp->ma_table && ep->me_key == startkey) {
235 if (cmp > 0)
236 goto Done;
237 }
238 else {
239 /* The compare did major nasty stuff to the
240 * dict: start over.
241 * XXX A clever adversary could prevent this
242 * XXX from terminating.
243 */
244 ep = lookdict(mp, key, hash);
245 goto Done;
246 }
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000247 }
248 freeslot = NULL;
Guido van Rossum2a61e741997-01-18 07:55:05 +0000249 }
Tim Peters15d49292001-05-27 07:39:22 +0000250
Tim Peters342c65e2001-05-13 06:43:53 +0000251 /* In the loop, me_key == dummy is by far (factor of 100s) the
252 least likely outcome, so test for that last. */
Tim Peterseb28ef22001-06-02 05:27:19 +0000253 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
254 i = (i << 2) + i + perturb + 1;
255 ep = &ep0[i & mask];
Guido van Rossum16e93a81997-01-28 00:00:11 +0000256 if (ep->me_key == NULL) {
Tim Peters7b5d0af2001-06-03 04:14:43 +0000257 if (freeslot != NULL)
258 ep = freeslot;
259 break;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000260 }
Tim Peters7b5d0af2001-06-03 04:14:43 +0000261 if (ep->me_key == key)
262 break;
263 if (ep->me_hash == hash && ep->me_key != dummy) {
Fred Drakec88b99c2000-08-31 19:04:07 +0000264 if (!checked_error) {
265 checked_error = 1;
266 if (PyErr_Occurred()) {
267 restore_error = 1;
268 PyErr_Fetch(&err_type, &err_value,
269 &err_tb);
270 }
271 }
Tim Peters453163d2001-06-03 04:54:32 +0000272 startkey = ep->me_key;
273 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Tim Peters7b5d0af2001-06-03 04:14:43 +0000274 if (cmp < 0)
Guido van Rossumb9324202001-01-18 00:39:02 +0000275 PyErr_Clear();
Tim Peters453163d2001-06-03 04:54:32 +0000276 if (ep0 == mp->ma_table && ep->me_key == startkey) {
277 if (cmp > 0)
278 break;
279 }
280 else {
281 /* The compare did major nasty stuff to the
282 * dict: start over.
283 * XXX A clever adversary could prevent this
284 * XXX from terminating.
285 */
286 ep = lookdict(mp, key, hash);
287 break;
288 }
Guido van Rossum16e93a81997-01-28 00:00:11 +0000289 }
Tim Peters342c65e2001-05-13 06:43:53 +0000290 else if (ep->me_key == dummy && freeslot == NULL)
291 freeslot = ep;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000292 }
Tim Peters7b5d0af2001-06-03 04:14:43 +0000293
294Done:
295 if (restore_error)
296 PyErr_Restore(err_type, err_value, err_tb);
297 return ep;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000298}
299
300/*
Fred Drake1bff34a2000-08-31 19:31:38 +0000301 * Hacked up version of lookdict which can assume keys are always strings;
302 * this assumption allows testing for errors during PyObject_Compare() to
303 * be dropped; string-string comparisons never raise exceptions. This also
304 * means we don't need to go through PyObject_Compare(); we can always use
Martin v. Löwiscd353062001-05-24 16:56:35 +0000305 * _PyString_Eq directly.
Fred Drake1bff34a2000-08-31 19:31:38 +0000306 *
Tim Peters0ab085c2001-09-14 00:25:33 +0000307 * This is valuable because the general-case error handling in lookdict() is
308 * expensive, and dicts with pure-string keys are very common.
Fred Drake1bff34a2000-08-31 19:31:38 +0000309 */
310static dictentry *
311lookdict_string(dictobject *mp, PyObject *key, register long hash)
312{
313 register int i;
Tim Peterseb28ef22001-06-02 05:27:19 +0000314 register unsigned int perturb;
Fred Drake1bff34a2000-08-31 19:31:38 +0000315 register dictentry *freeslot;
Tim Petersafb6ae82001-06-04 21:00:21 +0000316 register unsigned int mask = mp->ma_mask;
Fred Drake1bff34a2000-08-31 19:31:38 +0000317 dictentry *ep0 = mp->ma_table;
318 register dictentry *ep;
Fred Drake1bff34a2000-08-31 19:31:38 +0000319
Tim Peters0ab085c2001-09-14 00:25:33 +0000320 /* Make sure this function doesn't have to handle non-string keys,
321 including subclasses of str; e.g., one reason to subclass
322 strings is to override __eq__, and for speed we don't cater to
323 that here. */
324 if (!PyString_CheckExact(key)) {
Fred Drake1bff34a2000-08-31 19:31:38 +0000325#ifdef SHOW_CONVERSION_COUNTS
326 ++converted;
327#endif
328 mp->ma_lookup = lookdict;
329 return lookdict(mp, key, hash);
330 }
Tim Peters2f228e72001-05-13 00:19:31 +0000331 i = hash & mask;
Fred Drake1bff34a2000-08-31 19:31:38 +0000332 ep = &ep0[i];
333 if (ep->me_key == NULL || ep->me_key == key)
334 return ep;
335 if (ep->me_key == dummy)
336 freeslot = ep;
337 else {
338 if (ep->me_hash == hash
Martin v. Löwiscd353062001-05-24 16:56:35 +0000339 && _PyString_Eq(ep->me_key, key)) {
Fred Drake1bff34a2000-08-31 19:31:38 +0000340 return ep;
341 }
342 freeslot = NULL;
343 }
Tim Peters15d49292001-05-27 07:39:22 +0000344
Tim Peters342c65e2001-05-13 06:43:53 +0000345 /* In the loop, me_key == dummy is by far (factor of 100s) the
346 least likely outcome, so test for that last. */
Tim Peterseb28ef22001-06-02 05:27:19 +0000347 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
348 i = (i << 2) + i + perturb + 1;
349 ep = &ep0[i & mask];
Tim Peters342c65e2001-05-13 06:43:53 +0000350 if (ep->me_key == NULL)
351 return freeslot == NULL ? ep : freeslot;
352 if (ep->me_key == key
353 || (ep->me_hash == hash
354 && ep->me_key != dummy
Martin v. Löwiscd353062001-05-24 16:56:35 +0000355 && _PyString_Eq(ep->me_key, key)))
Fred Drake1bff34a2000-08-31 19:31:38 +0000356 return ep;
Tim Petersdea48ec2001-05-22 20:40:22 +0000357 if (ep->me_key == dummy && freeslot == NULL)
Tim Peters342c65e2001-05-13 06:43:53 +0000358 freeslot = ep;
Fred Drake1bff34a2000-08-31 19:31:38 +0000359 }
360}
361
362/*
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000363Internal routine to insert a new item into the table.
364Used both by the internal resize routine and by the public insert routine.
365Eats a reference to key and one to value.
366*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000367static void
Tim Peters1f5871e2000-07-04 17:44:48 +0000368insertdict(register dictobject *mp, PyObject *key, long hash, PyObject *value)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000369{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000370 PyObject *old_value;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000371 register dictentry *ep;
Tim Peters6d6c1a32001-08-02 04:15:00 +0000372 typedef PyDictEntry *(*lookupfunc)(PyDictObject *, PyObject *, long);
373
374 assert(mp->ma_lookup != NULL);
375 ep = mp->ma_lookup(mp, key, hash);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000376 if (ep->me_value != NULL) {
Guido van Rossumd7047b31995-01-02 19:07:15 +0000377 old_value = ep->me_value;
378 ep->me_value = value;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000379 Py_DECREF(old_value); /* which **CAN** re-enter */
380 Py_DECREF(key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000381 }
382 else {
383 if (ep->me_key == NULL)
384 mp->ma_fill++;
385 else
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000386 Py_DECREF(ep->me_key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000387 ep->me_key = key;
388 ep->me_hash = hash;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000389 ep->me_value = value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000390 mp->ma_used++;
391 }
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000392}
393
394/*
395Restructure the table by allocating a new table and reinserting all
396items again. When entries have been deleted, the new table may
397actually be smaller than the old one.
398*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000399static int
Tim Peters1f5871e2000-07-04 17:44:48 +0000400dictresize(dictobject *mp, int minused)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000401{
Tim Peterseb28ef22001-06-02 05:27:19 +0000402 int newsize;
Tim Peters0c6010b2001-05-23 23:33:57 +0000403 dictentry *oldtable, *newtable, *ep;
404 int i;
405 int is_oldtable_malloced;
Tim Peters6d6c1a32001-08-02 04:15:00 +0000406 dictentry small_copy[PyDict_MINSIZE];
Tim Peters91a364d2001-05-19 07:04:38 +0000407
408 assert(minused >= 0);
Tim Peters0c6010b2001-05-23 23:33:57 +0000409
Tim Peterseb28ef22001-06-02 05:27:19 +0000410 /* Find the smallest table size > minused. */
Tim Peters6d6c1a32001-08-02 04:15:00 +0000411 for (newsize = PyDict_MINSIZE;
Tim Peterseb28ef22001-06-02 05:27:19 +0000412 newsize <= minused && newsize > 0;
413 newsize <<= 1)
414 ;
415 if (newsize <= 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000416 PyErr_NoMemory();
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000417 return -1;
418 }
Tim Peters0c6010b2001-05-23 23:33:57 +0000419
420 /* Get space for a new table. */
421 oldtable = mp->ma_table;
422 assert(oldtable != NULL);
423 is_oldtable_malloced = oldtable != mp->ma_smalltable;
424
Tim Peters6d6c1a32001-08-02 04:15:00 +0000425 if (newsize == PyDict_MINSIZE) {
Tim Petersf8a548c2001-05-24 16:26:40 +0000426 /* A large table is shrinking, or we can't get any smaller. */
Tim Petersdea48ec2001-05-22 20:40:22 +0000427 newtable = mp->ma_smalltable;
Tim Peters0c6010b2001-05-23 23:33:57 +0000428 if (newtable == oldtable) {
Tim Petersf8a548c2001-05-24 16:26:40 +0000429 if (mp->ma_fill == mp->ma_used) {
430 /* No dummies, so no point doing anything. */
Tim Peters0c6010b2001-05-23 23:33:57 +0000431 return 0;
Tim Petersf8a548c2001-05-24 16:26:40 +0000432 }
433 /* We're not going to resize it, but rebuild the
434 table anyway to purge old dummy entries.
435 Subtle: This is *necessary* if fill==size,
436 as lookdict needs at least one virgin slot to
437 terminate failing searches. If fill < size, it's
438 merely desirable, as dummies slow searches. */
439 assert(mp->ma_fill > mp->ma_used);
Tim Peters0c6010b2001-05-23 23:33:57 +0000440 memcpy(small_copy, oldtable, sizeof(small_copy));
441 oldtable = small_copy;
442 }
Tim Petersdea48ec2001-05-22 20:40:22 +0000443 }
444 else {
445 newtable = PyMem_NEW(dictentry, newsize);
446 if (newtable == NULL) {
447 PyErr_NoMemory();
448 return -1;
449 }
450 }
Tim Peters0c6010b2001-05-23 23:33:57 +0000451
452 /* Make the dict empty, using the new table. */
Tim Petersdea48ec2001-05-22 20:40:22 +0000453 assert(newtable != oldtable);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000454 mp->ma_table = newtable;
Tim Petersafb6ae82001-06-04 21:00:21 +0000455 mp->ma_mask = newsize - 1;
Tim Petersdea48ec2001-05-22 20:40:22 +0000456 memset(newtable, 0, sizeof(dictentry) * newsize);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000457 mp->ma_used = 0;
Tim Petersdea48ec2001-05-22 20:40:22 +0000458 i = mp->ma_fill;
459 mp->ma_fill = 0;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000460
Tim Peters19283142001-05-17 22:25:34 +0000461 /* Copy the data over; this is refcount-neutral for active entries;
462 dummy entries aren't copied over, of course */
Tim Petersdea48ec2001-05-22 20:40:22 +0000463 for (ep = oldtable; i > 0; ep++) {
464 if (ep->me_value != NULL) { /* active entry */
465 --i;
Tim Peters19283142001-05-17 22:25:34 +0000466 insertdict(mp, ep->me_key, ep->me_hash, ep->me_value);
Tim Petersdea48ec2001-05-22 20:40:22 +0000467 }
Tim Peters19283142001-05-17 22:25:34 +0000468 else if (ep->me_key != NULL) { /* dummy entry */
Tim Petersdea48ec2001-05-22 20:40:22 +0000469 --i;
Tim Peters19283142001-05-17 22:25:34 +0000470 assert(ep->me_key == dummy);
471 Py_DECREF(ep->me_key);
Guido van Rossum255443b1998-04-10 22:47:14 +0000472 }
Tim Peters19283142001-05-17 22:25:34 +0000473 /* else key == value == NULL: nothing to do */
Guido van Rossumd7047b31995-01-02 19:07:15 +0000474 }
475
Tim Peters0c6010b2001-05-23 23:33:57 +0000476 if (is_oldtable_malloced)
Guido van Rossumb18618d2000-05-03 23:44:39 +0000477 PyMem_DEL(oldtable);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000478 return 0;
479}
480
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000481PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000482PyDict_GetItem(PyObject *op, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000483{
484 long hash;
Fred Drake1bff34a2000-08-31 19:31:38 +0000485 dictobject *mp = (dictobject *)op;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000486 if (!PyDict_Check(op)) {
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000487 return NULL;
488 }
Tim Peters0ab085c2001-09-14 00:25:33 +0000489 if (!PyString_CheckExact(key) ||
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000490 (hash = ((PyStringObject *) key)->ob_shash) == -1)
Guido van Rossumca756f21997-01-23 19:39:29 +0000491 {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000492 hash = PyObject_Hash(key);
Guido van Rossum474b19e1998-05-14 01:00:51 +0000493 if (hash == -1) {
494 PyErr_Clear();
Guido van Rossumca756f21997-01-23 19:39:29 +0000495 return NULL;
Guido van Rossum474b19e1998-05-14 01:00:51 +0000496 }
Guido van Rossumca756f21997-01-23 19:39:29 +0000497 }
Fred Drake1bff34a2000-08-31 19:31:38 +0000498 return (mp->ma_lookup)(mp, key, hash)->me_value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000499}
500
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +0000501static PyObject *
502dict_getitem(PyObject *op, PyObject *key)
503{
504 long hash;
505 dictobject *mp = (dictobject *)op;
506 PyObject *v;
507
508 if (!PyDict_Check(op)) {
509 return NULL;
510 }
511 if (!PyString_CheckExact(key) ||
512 (hash = ((PyStringObject *) key)->ob_shash) == -1)
513 {
514 hash = PyObject_Hash(key);
515 if (hash == -1)
516 return NULL;
517 }
518 v = (mp->ma_lookup)(mp, key, hash) -> me_value;
519 if (v == NULL)
520 PyErr_SetObject(PyExc_KeyError, key);
521 else
522 Py_INCREF(v);
523 return v;
524}
525
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000526/* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
527 * dictionary if it is merely replacing the value for an existing key.
528 * This is means that it's safe to loop over a dictionary with
529 * PyDict_Next() and occasionally replace a value -- but you can't
530 * insert new keys or remove them.
531 */
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000532int
Tim Peters1f5871e2000-07-04 17:44:48 +0000533PyDict_SetItem(register PyObject *op, PyObject *key, PyObject *value)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000534{
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000535 register dictobject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000536 register long hash;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000537 register int n_used;
538
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000539 if (!PyDict_Check(op)) {
540 PyErr_BadInternalCall();
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000541 return -1;
542 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000543 mp = (dictobject *)op;
Tim Peters0ab085c2001-09-14 00:25:33 +0000544 if (PyString_CheckExact(key)) {
Guido van Rossum45ec02a2002-08-19 21:43:18 +0000545 hash = ((PyStringObject *)key)->ob_shash;
546 if (hash == -1)
547 hash = PyObject_Hash(key);
Guido van Rossum2a61e741997-01-18 07:55:05 +0000548 }
Tim Peters1f7df352002-03-29 03:29:08 +0000549 else {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000550 hash = PyObject_Hash(key);
Guido van Rossum2a61e741997-01-18 07:55:05 +0000551 if (hash == -1)
552 return -1;
Guido van Rossum2a61e741997-01-18 07:55:05 +0000553 }
Tim Petersafb6ae82001-06-04 21:00:21 +0000554 assert(mp->ma_fill <= mp->ma_mask); /* at least one empty slot */
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000555 n_used = mp->ma_used;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000556 Py_INCREF(value);
557 Py_INCREF(key);
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000558 insertdict(mp, key, hash, value);
Raymond Hettinger3539f6b2003-05-05 22:22:10 +0000559 /* If we added a key, we can safely resize. Otherwise just return!
560 * If fill >= 2/3 size, adjust size. Normally, this doubles or
561 * quaduples the size, but it's also possible for the dict to shrink
562 * (if ma_fill is much larger than ma_used, meaning a lot of dict
563 * keys have been * deleted).
564 *
565 * Quadrupling the size improves average dictionary sparseness
566 * (reducing collisions) at the cost of some memory and iteration
567 * speed (which loops over every possible entry). It also halves
568 * the number of expensive resize operations in a growing dictionary.
569 *
570 * Very large dictionaries (over 50K items) use doubling instead.
571 * This may help applications with severe memory constraints.
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000572 */
Raymond Hettinger3539f6b2003-05-05 22:22:10 +0000573 if (!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))
574 return 0;
575 return dictresize(mp, mp->ma_used*(mp->ma_used>50000 ? 2 : 4));
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000576}
577
578int
Tim Peters1f5871e2000-07-04 17:44:48 +0000579PyDict_DelItem(PyObject *op, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000580{
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000581 register dictobject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000582 register long hash;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000583 register dictentry *ep;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000584 PyObject *old_value, *old_key;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000585
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000586 if (!PyDict_Check(op)) {
587 PyErr_BadInternalCall();
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000588 return -1;
589 }
Tim Peters0ab085c2001-09-14 00:25:33 +0000590 if (!PyString_CheckExact(key) ||
Tim Peters1f7df352002-03-29 03:29:08 +0000591 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000592 hash = PyObject_Hash(key);
Guido van Rossumca756f21997-01-23 19:39:29 +0000593 if (hash == -1)
594 return -1;
595 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000596 mp = (dictobject *)op;
Fred Drake1bff34a2000-08-31 19:31:38 +0000597 ep = (mp->ma_lookup)(mp, key, hash);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000598 if (ep->me_value == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000599 PyErr_SetObject(PyExc_KeyError, key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000600 return -1;
601 }
Guido van Rossumd7047b31995-01-02 19:07:15 +0000602 old_key = ep->me_key;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000603 Py_INCREF(dummy);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000604 ep->me_key = dummy;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000605 old_value = ep->me_value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000606 ep->me_value = NULL;
607 mp->ma_used--;
Tim Petersea8f2bf2000-12-13 01:02:46 +0000608 Py_DECREF(old_value);
609 Py_DECREF(old_key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000610 return 0;
611}
612
Guido van Rossum25831651993-05-19 14:50:45 +0000613void
Tim Peters1f5871e2000-07-04 17:44:48 +0000614PyDict_Clear(PyObject *op)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000615{
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000616 dictobject *mp;
Tim Petersdea48ec2001-05-22 20:40:22 +0000617 dictentry *ep, *table;
618 int table_is_malloced;
619 int fill;
Tim Peters6d6c1a32001-08-02 04:15:00 +0000620 dictentry small_copy[PyDict_MINSIZE];
Tim Petersdea48ec2001-05-22 20:40:22 +0000621#ifdef Py_DEBUG
622 int i, n;
623#endif
624
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000625 if (!PyDict_Check(op))
Guido van Rossum25831651993-05-19 14:50:45 +0000626 return;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000627 mp = (dictobject *)op;
Tim Petersdea48ec2001-05-22 20:40:22 +0000628#ifdef Py_DEBUG
Tim Petersafb6ae82001-06-04 21:00:21 +0000629 n = mp->ma_mask + 1;
Tim Petersdea48ec2001-05-22 20:40:22 +0000630 i = 0;
631#endif
632
633 table = mp->ma_table;
634 assert(table != NULL);
635 table_is_malloced = table != mp->ma_smalltable;
636
637 /* This is delicate. During the process of clearing the dict,
638 * decrefs can cause the dict to mutate. To avoid fatal confusion
639 * (voice of experience), we have to make the dict empty before
640 * clearing the slots, and never refer to anything via mp->xxx while
641 * clearing.
642 */
643 fill = mp->ma_fill;
644 if (table_is_malloced)
Tim Peters6d6c1a32001-08-02 04:15:00 +0000645 EMPTY_TO_MINSIZE(mp);
Tim Petersdea48ec2001-05-22 20:40:22 +0000646
647 else if (fill > 0) {
648 /* It's a small table with something that needs to be cleared.
649 * Afraid the only safe way is to copy the dict entries into
650 * another small table first.
651 */
652 memcpy(small_copy, table, sizeof(small_copy));
653 table = small_copy;
Tim Peters6d6c1a32001-08-02 04:15:00 +0000654 EMPTY_TO_MINSIZE(mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000655 }
Tim Petersdea48ec2001-05-22 20:40:22 +0000656 /* else it's a small table that's already empty */
657
658 /* Now we can finally clear things. If C had refcounts, we could
659 * assert that the refcount on table is 1 now, i.e. that this function
660 * has unique access to it, so decref side-effects can't alter it.
661 */
662 for (ep = table; fill > 0; ++ep) {
663#ifdef Py_DEBUG
664 assert(i < n);
665 ++i;
666#endif
667 if (ep->me_key) {
668 --fill;
669 Py_DECREF(ep->me_key);
670 Py_XDECREF(ep->me_value);
671 }
672#ifdef Py_DEBUG
673 else
674 assert(ep->me_value == NULL);
675#endif
676 }
677
678 if (table_is_malloced)
679 PyMem_DEL(table);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000680}
681
Tim Peters080c88b2003-02-15 03:01:11 +0000682/*
683 * Iterate over a dict. Use like so:
684 *
685 * int i;
686 * PyObject *key, *value;
687 * i = 0; # important! i should not otherwise be changed by you
Neal Norwitz07323012003-02-15 14:45:12 +0000688 * while (PyDict_Next(yourdict, &i, &key, &value)) {
Tim Peters080c88b2003-02-15 03:01:11 +0000689 * Refer to borrowed references in key and value.
690 * }
691 *
692 * CAUTION: In general, it isn't safe to use PyDict_Next in a loop that
Tim Peters67830702001-03-21 19:23:56 +0000693 * mutates the dict. One exception: it is safe if the loop merely changes
694 * the values associated with the keys (but doesn't insert new keys or
695 * delete keys), via PyDict_SetItem().
696 */
Guido van Rossum25831651993-05-19 14:50:45 +0000697int
Tim Peters1f5871e2000-07-04 17:44:48 +0000698PyDict_Next(PyObject *op, int *ppos, PyObject **pkey, PyObject **pvalue)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000699{
Guido van Rossum25831651993-05-19 14:50:45 +0000700 int i;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000701 register dictobject *mp;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000702 if (!PyDict_Check(op))
Guido van Rossum25831651993-05-19 14:50:45 +0000703 return 0;
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000704 mp = (dictobject *)op;
Guido van Rossum25831651993-05-19 14:50:45 +0000705 i = *ppos;
706 if (i < 0)
707 return 0;
Tim Petersafb6ae82001-06-04 21:00:21 +0000708 while (i <= mp->ma_mask && mp->ma_table[i].me_value == NULL)
Guido van Rossum25831651993-05-19 14:50:45 +0000709 i++;
710 *ppos = i+1;
Tim Petersafb6ae82001-06-04 21:00:21 +0000711 if (i > mp->ma_mask)
Guido van Rossum25831651993-05-19 14:50:45 +0000712 return 0;
713 if (pkey)
714 *pkey = mp->ma_table[i].me_key;
715 if (pvalue)
716 *pvalue = mp->ma_table[i].me_value;
717 return 1;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000718}
719
720/* Methods */
721
722static void
Tim Peters1f5871e2000-07-04 17:44:48 +0000723dict_dealloc(register dictobject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000724{
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000725 register dictentry *ep;
Tim Petersdea48ec2001-05-22 20:40:22 +0000726 int fill = mp->ma_fill;
Guido van Rossumff413af2002-03-28 20:34:59 +0000727 PyObject_GC_UnTrack(mp);
Guido van Rossumd724b232000-03-13 16:01:29 +0000728 Py_TRASHCAN_SAFE_BEGIN(mp)
Tim Petersdea48ec2001-05-22 20:40:22 +0000729 for (ep = mp->ma_table; fill > 0; ep++) {
730 if (ep->me_key) {
731 --fill;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000732 Py_DECREF(ep->me_key);
Tim Petersdea48ec2001-05-22 20:40:22 +0000733 Py_XDECREF(ep->me_value);
Guido van Rossum255443b1998-04-10 22:47:14 +0000734 }
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000735 }
Tim Petersdea48ec2001-05-22 20:40:22 +0000736 if (mp->ma_table != mp->ma_smalltable)
Guido van Rossumb18618d2000-05-03 23:44:39 +0000737 PyMem_DEL(mp->ma_table);
Guido van Rossum9475a232001-10-05 20:51:39 +0000738 mp->ob_type->tp_free((PyObject *)mp);
Guido van Rossumd724b232000-03-13 16:01:29 +0000739 Py_TRASHCAN_SAFE_END(mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000740}
741
742static int
Tim Peters1f5871e2000-07-04 17:44:48 +0000743dict_print(register dictobject *mp, register FILE *fp, register int flags)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000744{
745 register int i;
746 register int any;
Guido van Rossum255443b1998-04-10 22:47:14 +0000747
748 i = Py_ReprEnter((PyObject*)mp);
749 if (i != 0) {
750 if (i < 0)
751 return i;
752 fprintf(fp, "{...}");
753 return 0;
754 }
755
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000756 fprintf(fp, "{");
757 any = 0;
Tim Petersafb6ae82001-06-04 21:00:21 +0000758 for (i = 0; i <= mp->ma_mask; i++) {
Tim Peters23cf6be2001-06-02 08:02:56 +0000759 dictentry *ep = mp->ma_table + i;
760 PyObject *pvalue = ep->me_value;
761 if (pvalue != NULL) {
762 /* Prevent PyObject_Repr from deleting value during
763 key format */
764 Py_INCREF(pvalue);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000765 if (any++ > 0)
766 fprintf(fp, ", ");
Guido van Rossum255443b1998-04-10 22:47:14 +0000767 if (PyObject_Print((PyObject *)ep->me_key, fp, 0)!=0) {
Tim Peters23cf6be2001-06-02 08:02:56 +0000768 Py_DECREF(pvalue);
Guido van Rossum255443b1998-04-10 22:47:14 +0000769 Py_ReprLeave((PyObject*)mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000770 return -1;
Guido van Rossum255443b1998-04-10 22:47:14 +0000771 }
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000772 fprintf(fp, ": ");
Tim Peters19b77cf2001-06-02 08:27:39 +0000773 if (PyObject_Print(pvalue, fp, 0) != 0) {
Tim Peters23cf6be2001-06-02 08:02:56 +0000774 Py_DECREF(pvalue);
Guido van Rossum255443b1998-04-10 22:47:14 +0000775 Py_ReprLeave((PyObject*)mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000776 return -1;
Guido van Rossum255443b1998-04-10 22:47:14 +0000777 }
Tim Peters23cf6be2001-06-02 08:02:56 +0000778 Py_DECREF(pvalue);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000779 }
780 }
781 fprintf(fp, "}");
Guido van Rossum255443b1998-04-10 22:47:14 +0000782 Py_ReprLeave((PyObject*)mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000783 return 0;
784}
785
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000786static PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000787dict_repr(dictobject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000788{
Tim Petersc6057842001-06-16 07:52:53 +0000789 int i;
Tim Petersa7259592001-06-16 05:11:17 +0000790 PyObject *s, *temp, *colon = NULL;
791 PyObject *pieces = NULL, *result = NULL;
792 PyObject *key, *value;
Guido van Rossum255443b1998-04-10 22:47:14 +0000793
Tim Petersa7259592001-06-16 05:11:17 +0000794 i = Py_ReprEnter((PyObject *)mp);
Guido van Rossum255443b1998-04-10 22:47:14 +0000795 if (i != 0) {
Tim Petersa7259592001-06-16 05:11:17 +0000796 return i > 0 ? PyString_FromString("{...}") : NULL;
Guido van Rossum255443b1998-04-10 22:47:14 +0000797 }
798
Tim Petersa7259592001-06-16 05:11:17 +0000799 if (mp->ma_used == 0) {
800 result = PyString_FromString("{}");
801 goto Done;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000802 }
Tim Petersa7259592001-06-16 05:11:17 +0000803
804 pieces = PyList_New(0);
805 if (pieces == NULL)
806 goto Done;
807
808 colon = PyString_FromString(": ");
809 if (colon == NULL)
810 goto Done;
811
812 /* Do repr() on each key+value pair, and insert ": " between them.
813 Note that repr may mutate the dict. */
Tim Petersc6057842001-06-16 07:52:53 +0000814 i = 0;
815 while (PyDict_Next((PyObject *)mp, &i, &key, &value)) {
Tim Petersa7259592001-06-16 05:11:17 +0000816 int status;
817 /* Prevent repr from deleting value during key format. */
818 Py_INCREF(value);
819 s = PyObject_Repr(key);
820 PyString_Concat(&s, colon);
821 PyString_ConcatAndDel(&s, PyObject_Repr(value));
822 Py_DECREF(value);
823 if (s == NULL)
824 goto Done;
825 status = PyList_Append(pieces, s);
826 Py_DECREF(s); /* append created a new ref */
827 if (status < 0)
828 goto Done;
829 }
830
831 /* Add "{}" decorations to the first and last items. */
832 assert(PyList_GET_SIZE(pieces) > 0);
833 s = PyString_FromString("{");
834 if (s == NULL)
835 goto Done;
836 temp = PyList_GET_ITEM(pieces, 0);
837 PyString_ConcatAndDel(&s, temp);
838 PyList_SET_ITEM(pieces, 0, s);
839 if (s == NULL)
840 goto Done;
841
842 s = PyString_FromString("}");
843 if (s == NULL)
844 goto Done;
845 temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
846 PyString_ConcatAndDel(&temp, s);
847 PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
848 if (temp == NULL)
849 goto Done;
850
851 /* Paste them all together with ", " between. */
852 s = PyString_FromString(", ");
853 if (s == NULL)
854 goto Done;
855 result = _PyString_Join(s, pieces);
Tim Peters0ab085c2001-09-14 00:25:33 +0000856 Py_DECREF(s);
Tim Petersa7259592001-06-16 05:11:17 +0000857
858Done:
859 Py_XDECREF(pieces);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000860 Py_XDECREF(colon);
Tim Petersa7259592001-06-16 05:11:17 +0000861 Py_ReprLeave((PyObject *)mp);
862 return result;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000863}
864
865static int
Tim Peters1f5871e2000-07-04 17:44:48 +0000866dict_length(dictobject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000867{
868 return mp->ma_used;
869}
870
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000871static PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000872dict_subscript(dictobject *mp, register PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000873{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000874 PyObject *v;
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +0000875 long hash;
Tim Petersdea48ec2001-05-22 20:40:22 +0000876 assert(mp->ma_table != NULL);
Tim Peters0ab085c2001-09-14 00:25:33 +0000877 if (!PyString_CheckExact(key) ||
Tim Peters1f7df352002-03-29 03:29:08 +0000878 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000879 hash = PyObject_Hash(key);
Guido van Rossumca756f21997-01-23 19:39:29 +0000880 if (hash == -1)
881 return NULL;
882 }
Fred Drake1bff34a2000-08-31 19:31:38 +0000883 v = (mp->ma_lookup)(mp, key, hash) -> me_value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000884 if (v == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000885 PyErr_SetObject(PyExc_KeyError, key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000886 else
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000887 Py_INCREF(v);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000888 return v;
889}
890
891static int
Tim Peters1f5871e2000-07-04 17:44:48 +0000892dict_ass_sub(dictobject *mp, PyObject *v, PyObject *w)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000893{
894 if (w == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000895 return PyDict_DelItem((PyObject *)mp, v);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000896 else
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000897 return PyDict_SetItem((PyObject *)mp, v, w);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000898}
899
Guido van Rossuma9e7a811997-05-13 21:02:11 +0000900static PyMappingMethods dict_as_mapping = {
901 (inquiry)dict_length, /*mp_length*/
902 (binaryfunc)dict_subscript, /*mp_subscript*/
903 (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000904};
905
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000906static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +0000907dict_keys(register dictobject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000908{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000909 register PyObject *v;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000910 register int i, j, n;
911
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000912 again:
913 n = mp->ma_used;
914 v = PyList_New(n);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000915 if (v == NULL)
916 return NULL;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000917 if (n != mp->ma_used) {
918 /* Durnit. The allocations caused the dict to resize.
919 * Just start over, this shouldn't normally happen.
920 */
921 Py_DECREF(v);
922 goto again;
923 }
Tim Petersafb6ae82001-06-04 21:00:21 +0000924 for (i = 0, j = 0; i <= mp->ma_mask; i++) {
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000925 if (mp->ma_table[i].me_value != NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000926 PyObject *key = mp->ma_table[i].me_key;
927 Py_INCREF(key);
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000928 PyList_SET_ITEM(v, j, key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000929 j++;
930 }
931 }
932 return v;
933}
934
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000935static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +0000936dict_values(register dictobject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +0000937{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000938 register PyObject *v;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000939 register int i, j, n;
940
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000941 again:
942 n = mp->ma_used;
943 v = PyList_New(n);
Guido van Rossum25831651993-05-19 14:50:45 +0000944 if (v == NULL)
945 return NULL;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000946 if (n != mp->ma_used) {
947 /* Durnit. The allocations caused the dict to resize.
948 * Just start over, this shouldn't normally happen.
949 */
950 Py_DECREF(v);
951 goto again;
952 }
Tim Petersafb6ae82001-06-04 21:00:21 +0000953 for (i = 0, j = 0; i <= mp->ma_mask; i++) {
Guido van Rossum25831651993-05-19 14:50:45 +0000954 if (mp->ma_table[i].me_value != NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000955 PyObject *value = mp->ma_table[i].me_value;
956 Py_INCREF(value);
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000957 PyList_SET_ITEM(v, j, value);
Guido van Rossum25831651993-05-19 14:50:45 +0000958 j++;
959 }
960 }
961 return v;
962}
963
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000964static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +0000965dict_items(register dictobject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +0000966{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000967 register PyObject *v;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000968 register int i, j, n;
969 PyObject *item, *key, *value;
970
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000971 /* Preallocate the list of tuples, to avoid allocations during
972 * the loop over the items, which could trigger GC, which
973 * could resize the dict. :-(
974 */
975 again:
976 n = mp->ma_used;
977 v = PyList_New(n);
Guido van Rossum25831651993-05-19 14:50:45 +0000978 if (v == NULL)
979 return NULL;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000980 for (i = 0; i < n; i++) {
981 item = PyTuple_New(2);
982 if (item == NULL) {
983 Py_DECREF(v);
984 return NULL;
985 }
986 PyList_SET_ITEM(v, i, item);
987 }
988 if (n != mp->ma_used) {
989 /* Durnit. The allocations caused the dict to resize.
990 * Just start over, this shouldn't normally happen.
991 */
992 Py_DECREF(v);
993 goto again;
994 }
995 /* Nothing we do below makes any function calls. */
Tim Petersafb6ae82001-06-04 21:00:21 +0000996 for (i = 0, j = 0; i <= mp->ma_mask; i++) {
Guido van Rossum25831651993-05-19 14:50:45 +0000997 if (mp->ma_table[i].me_value != NULL) {
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000998 key = mp->ma_table[i].me_key;
999 value = mp->ma_table[i].me_value;
1000 item = PyList_GET_ITEM(v, j);
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001001 Py_INCREF(key);
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001002 PyTuple_SET_ITEM(item, 0, key);
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001003 Py_INCREF(value);
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001004 PyTuple_SET_ITEM(item, 1, value);
Guido van Rossum25831651993-05-19 14:50:45 +00001005 j++;
1006 }
1007 }
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001008 assert(j == n);
Guido van Rossum25831651993-05-19 14:50:45 +00001009 return v;
1010}
1011
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001012static PyObject *
Tim Petersbca1cbc2002-12-09 22:56:13 +00001013dict_fromkeys(PyObject *cls, PyObject *args)
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001014{
1015 PyObject *seq;
1016 PyObject *value = Py_None;
1017 PyObject *it; /* iter(seq) */
1018 PyObject *key;
1019 PyObject *d;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001020 int status;
1021
Raymond Hettingerea3fdf42002-12-29 16:33:45 +00001022 if (!PyArg_UnpackTuple(args, "fromkeys", 1, 2, &seq, &value))
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001023 return NULL;
1024
1025 d = PyObject_CallObject(cls, NULL);
1026 if (d == NULL)
1027 return NULL;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001028
1029 it = PyObject_GetIter(seq);
1030 if (it == NULL){
1031 Py_DECREF(d);
1032 return NULL;
1033 }
1034
1035 for (;;) {
1036 key = PyIter_Next(it);
1037 if (key == NULL) {
1038 if (PyErr_Occurred())
1039 goto Fail;
1040 break;
1041 }
Raymond Hettingere03e5b12002-12-07 08:10:51 +00001042 status = PyObject_SetItem(d, key, value);
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001043 Py_DECREF(key);
1044 if (status < 0)
1045 goto Fail;
1046 }
1047
1048 Py_DECREF(it);
1049 return d;
1050
1051Fail:
1052 Py_DECREF(it);
1053 Py_DECREF(d);
1054 return NULL;
1055}
1056
1057static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001058dict_update(PyObject *mp, PyObject *other)
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001059{
Tim Peters6d6c1a32001-08-02 04:15:00 +00001060 if (PyDict_Update(mp, other) < 0)
1061 return NULL;
1062 Py_INCREF(Py_None);
1063 return Py_None;
1064}
1065
Guido van Rossum05ac6de2001-08-10 20:28:28 +00001066/* Update unconditionally replaces existing items.
1067 Merge has a 3rd argument 'override'; if set, it acts like Update,
Tim Peters1fc240e2001-10-26 05:06:50 +00001068 otherwise it leaves existing items unchanged.
1069
1070 PyDict_{Update,Merge} update/merge from a mapping object.
1071
Tim Petersf582b822001-12-11 18:51:08 +00001072 PyDict_MergeFromSeq2 updates/merges from any iterable object
Tim Peters1fc240e2001-10-26 05:06:50 +00001073 producing iterable objects of length 2.
1074*/
1075
Tim Petersf582b822001-12-11 18:51:08 +00001076int
Tim Peters1fc240e2001-10-26 05:06:50 +00001077PyDict_MergeFromSeq2(PyObject *d, PyObject *seq2, int override)
1078{
1079 PyObject *it; /* iter(seq2) */
1080 int i; /* index into seq2 of current element */
1081 PyObject *item; /* seq2[i] */
1082 PyObject *fast; /* item as a 2-tuple or 2-list */
1083
1084 assert(d != NULL);
1085 assert(PyDict_Check(d));
1086 assert(seq2 != NULL);
1087
1088 it = PyObject_GetIter(seq2);
1089 if (it == NULL)
1090 return -1;
1091
1092 for (i = 0; ; ++i) {
1093 PyObject *key, *value;
1094 int n;
1095
1096 fast = NULL;
1097 item = PyIter_Next(it);
1098 if (item == NULL) {
1099 if (PyErr_Occurred())
1100 goto Fail;
1101 break;
1102 }
1103
1104 /* Convert item to sequence, and verify length 2. */
1105 fast = PySequence_Fast(item, "");
1106 if (fast == NULL) {
1107 if (PyErr_ExceptionMatches(PyExc_TypeError))
1108 PyErr_Format(PyExc_TypeError,
1109 "cannot convert dictionary update "
1110 "sequence element #%d to a sequence",
1111 i);
1112 goto Fail;
1113 }
1114 n = PySequence_Fast_GET_SIZE(fast);
1115 if (n != 2) {
1116 PyErr_Format(PyExc_ValueError,
1117 "dictionary update sequence element #%d "
1118 "has length %d; 2 is required",
1119 i, n);
1120 goto Fail;
1121 }
1122
1123 /* Update/merge with this (key, value) pair. */
1124 key = PySequence_Fast_GET_ITEM(fast, 0);
1125 value = PySequence_Fast_GET_ITEM(fast, 1);
1126 if (override || PyDict_GetItem(d, key) == NULL) {
1127 int status = PyDict_SetItem(d, key, value);
1128 if (status < 0)
1129 goto Fail;
1130 }
1131 Py_DECREF(fast);
1132 Py_DECREF(item);
1133 }
1134
1135 i = 0;
1136 goto Return;
1137Fail:
1138 Py_XDECREF(item);
1139 Py_XDECREF(fast);
1140 i = -1;
1141Return:
1142 Py_DECREF(it);
1143 return i;
1144}
1145
Tim Peters6d6c1a32001-08-02 04:15:00 +00001146int
1147PyDict_Update(PyObject *a, PyObject *b)
1148{
Guido van Rossum05ac6de2001-08-10 20:28:28 +00001149 return PyDict_Merge(a, b, 1);
1150}
1151
1152int
1153PyDict_Merge(PyObject *a, PyObject *b, int override)
1154{
Tim Peters6d6c1a32001-08-02 04:15:00 +00001155 register PyDictObject *mp, *other;
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001156 register int i;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001157 dictentry *entry;
Tim Peters6d6c1a32001-08-02 04:15:00 +00001158
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001159 /* We accept for the argument either a concrete dictionary object,
1160 * or an abstract "mapping" object. For the former, we can do
1161 * things quite efficiently. For the latter, we only require that
1162 * PyMapping_Keys() and PyObject_GetItem() be supported.
1163 */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001164 if (a == NULL || !PyDict_Check(a) || b == NULL) {
1165 PyErr_BadInternalCall();
1166 return -1;
1167 }
1168 mp = (dictobject*)a;
1169 if (PyDict_Check(b)) {
1170 other = (dictobject*)b;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001171 if (other == mp || other->ma_used == 0)
1172 /* a.update(a) or a.update({}); nothing to do */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001173 return 0;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001174 /* Do one big resize at the start, rather than
1175 * incrementally resizing as we insert new items. Expect
1176 * that there will be no (or few) overlapping keys.
1177 */
1178 if ((mp->ma_fill + other->ma_used)*3 >= (mp->ma_mask+1)*2) {
Raymond Hettingerc8d22902003-05-07 00:49:40 +00001179 if (dictresize(mp, (mp->ma_used + other->ma_used)*2) != 0)
Tim Peters6d6c1a32001-08-02 04:15:00 +00001180 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001181 }
1182 for (i = 0; i <= other->ma_mask; i++) {
1183 entry = &other->ma_table[i];
Guido van Rossum05ac6de2001-08-10 20:28:28 +00001184 if (entry->me_value != NULL &&
1185 (override ||
1186 PyDict_GetItem(a, entry->me_key) == NULL)) {
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001187 Py_INCREF(entry->me_key);
1188 Py_INCREF(entry->me_value);
1189 insertdict(mp, entry->me_key, entry->me_hash,
1190 entry->me_value);
1191 }
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001192 }
1193 }
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001194 else {
1195 /* Do it the generic, slower way */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001196 PyObject *keys = PyMapping_Keys(b);
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001197 PyObject *iter;
1198 PyObject *key, *value;
1199 int status;
1200
1201 if (keys == NULL)
1202 /* Docstring says this is equivalent to E.keys() so
1203 * if E doesn't have a .keys() method we want
1204 * AttributeError to percolate up. Might as well
1205 * do the same for any other error.
1206 */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001207 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001208
1209 iter = PyObject_GetIter(keys);
1210 Py_DECREF(keys);
1211 if (iter == NULL)
Tim Peters6d6c1a32001-08-02 04:15:00 +00001212 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001213
1214 for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) {
Guido van Rossum05ac6de2001-08-10 20:28:28 +00001215 if (!override && PyDict_GetItem(a, key) != NULL) {
1216 Py_DECREF(key);
1217 continue;
1218 }
Tim Peters6d6c1a32001-08-02 04:15:00 +00001219 value = PyObject_GetItem(b, key);
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001220 if (value == NULL) {
1221 Py_DECREF(iter);
1222 Py_DECREF(key);
Tim Peters6d6c1a32001-08-02 04:15:00 +00001223 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001224 }
Guido van Rossum05ac6de2001-08-10 20:28:28 +00001225 status = PyDict_SetItem(a, key, value);
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001226 Py_DECREF(key);
1227 Py_DECREF(value);
1228 if (status < 0) {
1229 Py_DECREF(iter);
Tim Peters6d6c1a32001-08-02 04:15:00 +00001230 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001231 }
1232 }
1233 Py_DECREF(iter);
1234 if (PyErr_Occurred())
1235 /* Iterator completed, via error */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001236 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001237 }
Tim Peters6d6c1a32001-08-02 04:15:00 +00001238 return 0;
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001239}
1240
1241static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001242dict_copy(register dictobject *mp)
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001243{
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001244 return PyDict_Copy((PyObject*)mp);
1245}
1246
1247PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001248PyDict_Copy(PyObject *o)
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001249{
1250 register dictobject *mp;
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001251 register int i;
1252 dictobject *copy;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001253 dictentry *entry;
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001254
1255 if (o == NULL || !PyDict_Check(o)) {
1256 PyErr_BadInternalCall();
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001257 return NULL;
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001258 }
1259 mp = (dictobject *)o;
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001260 copy = (dictobject *)PyDict_New();
1261 if (copy == NULL)
1262 return NULL;
1263 if (mp->ma_used > 0) {
Raymond Hettingerc8d22902003-05-07 00:49:40 +00001264 if (dictresize(copy, mp->ma_used*2) != 0)
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001265 return NULL;
Tim Petersafb6ae82001-06-04 21:00:21 +00001266 for (i = 0; i <= mp->ma_mask; i++) {
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001267 entry = &mp->ma_table[i];
1268 if (entry->me_value != NULL) {
1269 Py_INCREF(entry->me_key);
1270 Py_INCREF(entry->me_value);
1271 insertdict(copy, entry->me_key, entry->me_hash,
1272 entry->me_value);
1273 }
1274 }
1275 }
1276 return (PyObject *)copy;
1277}
1278
Guido van Rossum4199fac1993-11-05 10:18:44 +00001279int
Tim Peters1f5871e2000-07-04 17:44:48 +00001280PyDict_Size(PyObject *mp)
Guido van Rossum4199fac1993-11-05 10:18:44 +00001281{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001282 if (mp == NULL || !PyDict_Check(mp)) {
1283 PyErr_BadInternalCall();
Guido van Rossumb376a4a1993-11-23 17:53:17 +00001284 return 0;
Guido van Rossum4199fac1993-11-05 10:18:44 +00001285 }
Guido van Rossuma9e7a811997-05-13 21:02:11 +00001286 return ((dictobject *)mp)->ma_used;
Guido van Rossum4199fac1993-11-05 10:18:44 +00001287}
1288
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001289PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001290PyDict_Keys(PyObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001291{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001292 if (mp == NULL || !PyDict_Check(mp)) {
1293 PyErr_BadInternalCall();
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001294 return NULL;
1295 }
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001296 return dict_keys((dictobject *)mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001297}
1298
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001299PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001300PyDict_Values(PyObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001301{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001302 if (mp == NULL || !PyDict_Check(mp)) {
1303 PyErr_BadInternalCall();
Guido van Rossum25831651993-05-19 14:50:45 +00001304 return NULL;
1305 }
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001306 return dict_values((dictobject *)mp);
Guido van Rossum25831651993-05-19 14:50:45 +00001307}
1308
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001309PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001310PyDict_Items(PyObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001311{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001312 if (mp == NULL || !PyDict_Check(mp)) {
1313 PyErr_BadInternalCall();
Guido van Rossum25831651993-05-19 14:50:45 +00001314 return NULL;
1315 }
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001316 return dict_items((dictobject *)mp);
Guido van Rossum25831651993-05-19 14:50:45 +00001317}
1318
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001319/* Subroutine which returns the smallest key in a for which b's value
1320 is different or absent. The value is returned too, through the
Tim Peters95bf9392001-05-10 08:32:44 +00001321 pval argument. Both are NULL if no key in a is found for which b's status
1322 differs. The refcounts on (and only on) non-NULL *pval and function return
1323 values must be decremented by the caller (characterize() increments them
1324 to ensure that mutating comparison and PyDict_GetItem calls can't delete
1325 them before the caller is done looking at them). */
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001326
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001327static PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001328characterize(dictobject *a, dictobject *b, PyObject **pval)
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001329{
Tim Peters95bf9392001-05-10 08:32:44 +00001330 PyObject *akey = NULL; /* smallest key in a s.t. a[akey] != b[akey] */
1331 PyObject *aval = NULL; /* a[akey] */
Guido van Rossumb9324202001-01-18 00:39:02 +00001332 int i, cmp;
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001333
Tim Petersafb6ae82001-06-04 21:00:21 +00001334 for (i = 0; i <= a->ma_mask; i++) {
Tim Peters95bf9392001-05-10 08:32:44 +00001335 PyObject *thiskey, *thisaval, *thisbval;
1336 if (a->ma_table[i].me_value == NULL)
1337 continue;
1338 thiskey = a->ma_table[i].me_key;
1339 Py_INCREF(thiskey); /* keep alive across compares */
1340 if (akey != NULL) {
1341 cmp = PyObject_RichCompareBool(akey, thiskey, Py_LT);
1342 if (cmp < 0) {
1343 Py_DECREF(thiskey);
1344 goto Fail;
1345 }
1346 if (cmp > 0 ||
Tim Petersafb6ae82001-06-04 21:00:21 +00001347 i > a->ma_mask ||
Tim Peters95bf9392001-05-10 08:32:44 +00001348 a->ma_table[i].me_value == NULL)
1349 {
1350 /* Not the *smallest* a key; or maybe it is
1351 * but the compare shrunk the dict so we can't
1352 * find its associated value anymore; or
1353 * maybe it is but the compare deleted the
1354 * a[thiskey] entry.
1355 */
1356 Py_DECREF(thiskey);
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001357 continue;
Guido van Rossumb9324202001-01-18 00:39:02 +00001358 }
Tim Peters95bf9392001-05-10 08:32:44 +00001359 }
1360
1361 /* Compare a[thiskey] to b[thiskey]; cmp <- true iff equal. */
1362 thisaval = a->ma_table[i].me_value;
1363 assert(thisaval);
1364 Py_INCREF(thisaval); /* keep alive */
1365 thisbval = PyDict_GetItem((PyObject *)b, thiskey);
1366 if (thisbval == NULL)
1367 cmp = 0;
1368 else {
1369 /* both dicts have thiskey: same values? */
1370 cmp = PyObject_RichCompareBool(
1371 thisaval, thisbval, Py_EQ);
1372 if (cmp < 0) {
1373 Py_DECREF(thiskey);
1374 Py_DECREF(thisaval);
1375 goto Fail;
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001376 }
1377 }
Tim Peters95bf9392001-05-10 08:32:44 +00001378 if (cmp == 0) {
1379 /* New winner. */
1380 Py_XDECREF(akey);
1381 Py_XDECREF(aval);
1382 akey = thiskey;
1383 aval = thisaval;
1384 }
1385 else {
1386 Py_DECREF(thiskey);
1387 Py_DECREF(thisaval);
1388 }
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001389 }
Tim Peters95bf9392001-05-10 08:32:44 +00001390 *pval = aval;
1391 return akey;
1392
1393Fail:
1394 Py_XDECREF(akey);
1395 Py_XDECREF(aval);
1396 *pval = NULL;
1397 return NULL;
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001398}
1399
1400static int
Tim Peters1f5871e2000-07-04 17:44:48 +00001401dict_compare(dictobject *a, dictobject *b)
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001402{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001403 PyObject *adiff, *bdiff, *aval, *bval;
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001404 int res;
1405
1406 /* Compare lengths first */
1407 if (a->ma_used < b->ma_used)
1408 return -1; /* a is shorter */
1409 else if (a->ma_used > b->ma_used)
1410 return 1; /* b is shorter */
Tim Peters95bf9392001-05-10 08:32:44 +00001411
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001412 /* Same length -- check all keys */
Tim Peters95bf9392001-05-10 08:32:44 +00001413 bdiff = bval = NULL;
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001414 adiff = characterize(a, b, &aval);
Tim Peters95bf9392001-05-10 08:32:44 +00001415 if (adiff == NULL) {
1416 assert(!aval);
Tim Peters3918fb22001-05-10 18:58:31 +00001417 /* Either an error, or a is a subset with the same length so
Tim Peters95bf9392001-05-10 08:32:44 +00001418 * must be equal.
1419 */
1420 res = PyErr_Occurred() ? -1 : 0;
1421 goto Finished;
1422 }
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001423 bdiff = characterize(b, a, &bval);
Tim Peters95bf9392001-05-10 08:32:44 +00001424 if (bdiff == NULL && PyErr_Occurred()) {
1425 assert(!bval);
1426 res = -1;
1427 goto Finished;
1428 }
1429 res = 0;
1430 if (bdiff) {
1431 /* bdiff == NULL "should be" impossible now, but perhaps
1432 * the last comparison done by the characterize() on a had
1433 * the side effect of making the dicts equal!
1434 */
1435 res = PyObject_Compare(adiff, bdiff);
1436 }
1437 if (res == 0 && bval != NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001438 res = PyObject_Compare(aval, bval);
Tim Peters95bf9392001-05-10 08:32:44 +00001439
1440Finished:
1441 Py_XDECREF(adiff);
1442 Py_XDECREF(bdiff);
1443 Py_XDECREF(aval);
1444 Py_XDECREF(bval);
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001445 return res;
1446}
1447
Tim Peterse63415e2001-05-08 04:38:29 +00001448/* Return 1 if dicts equal, 0 if not, -1 if error.
1449 * Gets out as soon as any difference is detected.
1450 * Uses only Py_EQ comparison.
1451 */
1452static int
1453dict_equal(dictobject *a, dictobject *b)
1454{
1455 int i;
1456
1457 if (a->ma_used != b->ma_used)
1458 /* can't be equal if # of entries differ */
1459 return 0;
Tim Peterseb28ef22001-06-02 05:27:19 +00001460
Tim Peterse63415e2001-05-08 04:38:29 +00001461 /* Same # of entries -- check all of 'em. Exit early on any diff. */
Tim Petersafb6ae82001-06-04 21:00:21 +00001462 for (i = 0; i <= a->ma_mask; i++) {
Tim Peterse63415e2001-05-08 04:38:29 +00001463 PyObject *aval = a->ma_table[i].me_value;
1464 if (aval != NULL) {
1465 int cmp;
1466 PyObject *bval;
1467 PyObject *key = a->ma_table[i].me_key;
1468 /* temporarily bump aval's refcount to ensure it stays
1469 alive until we're done with it */
1470 Py_INCREF(aval);
1471 bval = PyDict_GetItem((PyObject *)b, key);
1472 if (bval == NULL) {
1473 Py_DECREF(aval);
1474 return 0;
1475 }
1476 cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
1477 Py_DECREF(aval);
1478 if (cmp <= 0) /* error or not equal */
1479 return cmp;
1480 }
1481 }
1482 return 1;
1483 }
1484
1485static PyObject *
1486dict_richcompare(PyObject *v, PyObject *w, int op)
1487{
1488 int cmp;
1489 PyObject *res;
1490
1491 if (!PyDict_Check(v) || !PyDict_Check(w)) {
1492 res = Py_NotImplemented;
1493 }
1494 else if (op == Py_EQ || op == Py_NE) {
1495 cmp = dict_equal((dictobject *)v, (dictobject *)w);
1496 if (cmp < 0)
1497 return NULL;
1498 res = (cmp == (op == Py_EQ)) ? Py_True : Py_False;
1499 }
Tim Peters4fa58bf2001-05-10 21:45:19 +00001500 else
1501 res = Py_NotImplemented;
Tim Peterse63415e2001-05-08 04:38:29 +00001502 Py_INCREF(res);
1503 return res;
1504 }
1505
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001506static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001507dict_has_key(register dictobject *mp, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001508{
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001509 long hash;
1510 register long ok;
Tim Peters0ab085c2001-09-14 00:25:33 +00001511 if (!PyString_CheckExact(key) ||
Tim Peters1f7df352002-03-29 03:29:08 +00001512 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001513 hash = PyObject_Hash(key);
Guido van Rossumca756f21997-01-23 19:39:29 +00001514 if (hash == -1)
1515 return NULL;
1516 }
Tim Petersdea48ec2001-05-22 20:40:22 +00001517 ok = (mp->ma_lookup)(mp, key, hash)->me_value != NULL;
Guido van Rossum77f6a652002-04-03 22:41:51 +00001518 return PyBool_FromLong(ok);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001519}
1520
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001521static PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001522dict_get(register dictobject *mp, PyObject *args)
Barry Warsawc38c5da1997-10-06 17:49:20 +00001523{
1524 PyObject *key;
Barry Warsaw320ac331997-10-20 17:26:25 +00001525 PyObject *failobj = Py_None;
Barry Warsawc38c5da1997-10-06 17:49:20 +00001526 PyObject *val = NULL;
1527 long hash;
1528
Raymond Hettingerea3fdf42002-12-29 16:33:45 +00001529 if (!PyArg_UnpackTuple(args, "get", 1, 2, &key, &failobj))
Barry Warsawc38c5da1997-10-06 17:49:20 +00001530 return NULL;
1531
Tim Peters0ab085c2001-09-14 00:25:33 +00001532 if (!PyString_CheckExact(key) ||
Tim Peters1f7df352002-03-29 03:29:08 +00001533 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
Barry Warsawc38c5da1997-10-06 17:49:20 +00001534 hash = PyObject_Hash(key);
1535 if (hash == -1)
1536 return NULL;
1537 }
Fred Drake1bff34a2000-08-31 19:31:38 +00001538 val = (mp->ma_lookup)(mp, key, hash)->me_value;
Barry Warsaw320ac331997-10-20 17:26:25 +00001539
Barry Warsawc38c5da1997-10-06 17:49:20 +00001540 if (val == NULL)
1541 val = failobj;
1542 Py_INCREF(val);
1543 return val;
1544}
1545
1546
1547static PyObject *
Guido van Rossum164452c2000-08-08 16:12:54 +00001548dict_setdefault(register dictobject *mp, PyObject *args)
1549{
1550 PyObject *key;
1551 PyObject *failobj = Py_None;
1552 PyObject *val = NULL;
1553 long hash;
1554
Raymond Hettingerea3fdf42002-12-29 16:33:45 +00001555 if (!PyArg_UnpackTuple(args, "setdefault", 1, 2, &key, &failobj))
Guido van Rossum164452c2000-08-08 16:12:54 +00001556 return NULL;
Guido van Rossum164452c2000-08-08 16:12:54 +00001557
Tim Peters0ab085c2001-09-14 00:25:33 +00001558 if (!PyString_CheckExact(key) ||
Tim Peters1f7df352002-03-29 03:29:08 +00001559 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
Guido van Rossum164452c2000-08-08 16:12:54 +00001560 hash = PyObject_Hash(key);
1561 if (hash == -1)
1562 return NULL;
1563 }
Fred Drake1bff34a2000-08-31 19:31:38 +00001564 val = (mp->ma_lookup)(mp, key, hash)->me_value;
Guido van Rossum164452c2000-08-08 16:12:54 +00001565 if (val == NULL) {
1566 val = failobj;
1567 if (PyDict_SetItem((PyObject*)mp, key, failobj))
1568 val = NULL;
1569 }
1570 Py_XINCREF(val);
1571 return val;
1572}
1573
1574
1575static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001576dict_clear(register dictobject *mp)
Guido van Rossumfb8f1ca1997-03-21 21:55:12 +00001577{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001578 PyDict_Clear((PyObject *)mp);
1579 Py_INCREF(Py_None);
1580 return Py_None;
Guido van Rossumfb8f1ca1997-03-21 21:55:12 +00001581}
1582
Guido van Rossumba6ab842000-12-12 22:02:18 +00001583static PyObject *
Raymond Hettingera3e1e4c2003-03-06 23:54:28 +00001584dict_pop(dictobject *mp, PyObject *args)
Guido van Rossume027d982002-04-12 15:11:59 +00001585{
1586 long hash;
1587 dictentry *ep;
1588 PyObject *old_value, *old_key;
Raymond Hettingera3e1e4c2003-03-06 23:54:28 +00001589 PyObject *key, *deflt = NULL;
Guido van Rossume027d982002-04-12 15:11:59 +00001590
Raymond Hettingera3e1e4c2003-03-06 23:54:28 +00001591 if(!PyArg_UnpackTuple(args, "pop", 1, 2, &key, &deflt))
1592 return NULL;
Guido van Rossume027d982002-04-12 15:11:59 +00001593 if (mp->ma_used == 0) {
Raymond Hettingera3e1e4c2003-03-06 23:54:28 +00001594 if (deflt) {
1595 Py_INCREF(deflt);
1596 return deflt;
1597 }
Guido van Rossume027d982002-04-12 15:11:59 +00001598 PyErr_SetString(PyExc_KeyError,
1599 "pop(): dictionary is empty");
1600 return NULL;
1601 }
1602 if (!PyString_CheckExact(key) ||
1603 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
1604 hash = PyObject_Hash(key);
1605 if (hash == -1)
1606 return NULL;
1607 }
1608 ep = (mp->ma_lookup)(mp, key, hash);
1609 if (ep->me_value == NULL) {
Raymond Hettingera3e1e4c2003-03-06 23:54:28 +00001610 if (deflt) {
1611 Py_INCREF(deflt);
1612 return deflt;
1613 }
Guido van Rossume027d982002-04-12 15:11:59 +00001614 PyErr_SetObject(PyExc_KeyError, key);
1615 return NULL;
1616 }
1617 old_key = ep->me_key;
1618 Py_INCREF(dummy);
1619 ep->me_key = dummy;
1620 old_value = ep->me_value;
1621 ep->me_value = NULL;
1622 mp->ma_used--;
1623 Py_DECREF(old_key);
1624 return old_value;
1625}
1626
1627static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001628dict_popitem(dictobject *mp)
Guido van Rossumba6ab842000-12-12 22:02:18 +00001629{
1630 int i = 0;
1631 dictentry *ep;
1632 PyObject *res;
1633
Tim Petersf4b33f62001-06-02 05:42:29 +00001634 /* Allocate the result tuple before checking the size. Believe it
1635 * or not, this allocation could trigger a garbage collection which
1636 * could empty the dict, so if we checked the size first and that
1637 * happened, the result would be an infinite loop (searching for an
1638 * entry that no longer exists). Note that the usual popitem()
1639 * idiom is "while d: k, v = d.popitem()". so needing to throw the
1640 * tuple away if the dict *is* empty isn't a significant
1641 * inefficiency -- possible, but unlikely in practice.
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001642 */
1643 res = PyTuple_New(2);
1644 if (res == NULL)
1645 return NULL;
Guido van Rossume04eaec2001-04-16 00:02:32 +00001646 if (mp->ma_used == 0) {
1647 Py_DECREF(res);
1648 PyErr_SetString(PyExc_KeyError,
1649 "popitem(): dictionary is empty");
1650 return NULL;
1651 }
Guido van Rossumba6ab842000-12-12 22:02:18 +00001652 /* Set ep to "the first" dict entry with a value. We abuse the hash
1653 * field of slot 0 to hold a search finger:
1654 * If slot 0 has a value, use slot 0.
1655 * Else slot 0 is being used to hold a search finger,
1656 * and we use its hash value as the first index to look.
1657 */
1658 ep = &mp->ma_table[0];
1659 if (ep->me_value == NULL) {
1660 i = (int)ep->me_hash;
Tim Petersdea48ec2001-05-22 20:40:22 +00001661 /* The hash field may be a real hash value, or it may be a
1662 * legit search finger, or it may be a once-legit search
1663 * finger that's out of bounds now because it wrapped around
1664 * or the table shrunk -- simply make sure it's in bounds now.
Guido van Rossumba6ab842000-12-12 22:02:18 +00001665 */
Tim Petersafb6ae82001-06-04 21:00:21 +00001666 if (i > mp->ma_mask || i < 1)
Guido van Rossumba6ab842000-12-12 22:02:18 +00001667 i = 1; /* skip slot 0 */
1668 while ((ep = &mp->ma_table[i])->me_value == NULL) {
1669 i++;
Tim Petersafb6ae82001-06-04 21:00:21 +00001670 if (i > mp->ma_mask)
Guido van Rossumba6ab842000-12-12 22:02:18 +00001671 i = 1;
1672 }
1673 }
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001674 PyTuple_SET_ITEM(res, 0, ep->me_key);
1675 PyTuple_SET_ITEM(res, 1, ep->me_value);
1676 Py_INCREF(dummy);
1677 ep->me_key = dummy;
1678 ep->me_value = NULL;
1679 mp->ma_used--;
1680 assert(mp->ma_table[0].me_value == NULL);
1681 mp->ma_table[0].me_hash = i + 1; /* next place to start */
Guido van Rossumba6ab842000-12-12 22:02:18 +00001682 return res;
1683}
1684
Jeremy Hylton8caad492000-06-23 14:18:11 +00001685static int
1686dict_traverse(PyObject *op, visitproc visit, void *arg)
1687{
1688 int i = 0, err;
1689 PyObject *pk;
1690 PyObject *pv;
1691
1692 while (PyDict_Next(op, &i, &pk, &pv)) {
1693 err = visit(pk, arg);
1694 if (err)
1695 return err;
1696 err = visit(pv, arg);
1697 if (err)
1698 return err;
1699 }
1700 return 0;
1701}
1702
1703static int
1704dict_tp_clear(PyObject *op)
1705{
1706 PyDict_Clear(op);
1707 return 0;
1708}
1709
Tim Petersf7f88b12000-12-13 23:18:45 +00001710
Jeremy Hylton938ace62002-07-17 16:30:39 +00001711static PyObject *dictiter_new(dictobject *, binaryfunc);
Guido van Rossum09e563a2001-05-01 12:10:21 +00001712
1713static PyObject *
1714select_key(PyObject *key, PyObject *value)
1715{
1716 Py_INCREF(key);
1717 return key;
1718}
1719
1720static PyObject *
1721select_value(PyObject *key, PyObject *value)
1722{
1723 Py_INCREF(value);
1724 return value;
1725}
1726
1727static PyObject *
1728select_item(PyObject *key, PyObject *value)
1729{
1730 PyObject *res = PyTuple_New(2);
1731
1732 if (res != NULL) {
1733 Py_INCREF(key);
1734 Py_INCREF(value);
1735 PyTuple_SET_ITEM(res, 0, key);
1736 PyTuple_SET_ITEM(res, 1, value);
1737 }
1738 return res;
1739}
1740
1741static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001742dict_iterkeys(dictobject *dict)
Guido van Rossum09e563a2001-05-01 12:10:21 +00001743{
Guido van Rossum09e563a2001-05-01 12:10:21 +00001744 return dictiter_new(dict, select_key);
1745}
1746
1747static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001748dict_itervalues(dictobject *dict)
Guido van Rossum09e563a2001-05-01 12:10:21 +00001749{
Guido van Rossum09e563a2001-05-01 12:10:21 +00001750 return dictiter_new(dict, select_value);
1751}
1752
1753static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001754dict_iteritems(dictobject *dict)
Guido van Rossum09e563a2001-05-01 12:10:21 +00001755{
Guido van Rossum09e563a2001-05-01 12:10:21 +00001756 return dictiter_new(dict, select_item);
1757}
1758
1759
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001760PyDoc_STRVAR(has_key__doc__,
Raymond Hettinger574aa322003-09-01 22:12:08 +00001761"D.has_key(k) -> True if D has a key k, else False");
Tim Petersf7f88b12000-12-13 23:18:45 +00001762
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001763PyDoc_STRVAR(contains__doc__,
1764"D.__contains__(k) -> True if D has a key k, else False");
1765
1766PyDoc_STRVAR(getitem__doc__, "x.__getitem__(y) <==> x[y]");
1767
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001768PyDoc_STRVAR(get__doc__,
Guido van Rossumefae8862002-09-04 11:29:45 +00001769"D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.");
Tim Petersf7f88b12000-12-13 23:18:45 +00001770
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001771PyDoc_STRVAR(setdefault_doc__,
Guido van Rossumefae8862002-09-04 11:29:45 +00001772"D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D");
Tim Petersf7f88b12000-12-13 23:18:45 +00001773
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001774PyDoc_STRVAR(pop__doc__,
Raymond Hettingera3e1e4c2003-03-06 23:54:28 +00001775"D.pop(k[,d]) -> v, remove specified key and return the corresponding value\n\
1776If key is not found, d is returned if given, otherwise KeyError is raised");
Guido van Rossume027d982002-04-12 15:11:59 +00001777
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001778PyDoc_STRVAR(popitem__doc__,
Tim Petersf7f88b12000-12-13 23:18:45 +00001779"D.popitem() -> (k, v), remove and return some (key, value) pair as a\n\
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +000017802-tuple; but raise KeyError if D is empty");
Tim Petersf7f88b12000-12-13 23:18:45 +00001781
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001782PyDoc_STRVAR(keys__doc__,
1783"D.keys() -> list of D's keys");
Tim Petersf7f88b12000-12-13 23:18:45 +00001784
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001785PyDoc_STRVAR(items__doc__,
1786"D.items() -> list of D's (key, value) pairs, as 2-tuples");
Tim Petersf7f88b12000-12-13 23:18:45 +00001787
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001788PyDoc_STRVAR(values__doc__,
1789"D.values() -> list of D's values");
Tim Petersf7f88b12000-12-13 23:18:45 +00001790
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001791PyDoc_STRVAR(update__doc__,
1792"D.update(E) -> None. Update D from E: for k in E.keys(): D[k] = E[k]");
Tim Petersf7f88b12000-12-13 23:18:45 +00001793
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001794PyDoc_STRVAR(fromkeys__doc__,
1795"dict.fromkeys(S[,v]) -> New dict with keys from S and values equal to v.\n\
1796v defaults to None.");
1797
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001798PyDoc_STRVAR(clear__doc__,
1799"D.clear() -> None. Remove all items from D.");
Tim Petersf7f88b12000-12-13 23:18:45 +00001800
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001801PyDoc_STRVAR(copy__doc__,
1802"D.copy() -> a shallow copy of D");
Tim Petersf7f88b12000-12-13 23:18:45 +00001803
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001804PyDoc_STRVAR(iterkeys__doc__,
1805"D.iterkeys() -> an iterator over the keys of D");
Guido van Rossum09e563a2001-05-01 12:10:21 +00001806
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001807PyDoc_STRVAR(itervalues__doc__,
1808"D.itervalues() -> an iterator over the values of D");
Guido van Rossum09e563a2001-05-01 12:10:21 +00001809
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001810PyDoc_STRVAR(iteritems__doc__,
1811"D.iteritems() -> an iterator over the (key, value) items of D");
Guido van Rossum09e563a2001-05-01 12:10:21 +00001812
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001813static PyMethodDef mapp_methods[] = {
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001814 {"__contains__",(PyCFunction)dict_has_key, METH_O | METH_COEXIST,
1815 contains__doc__},
1816 {"__getitem__", (PyCFunction)dict_getitem, METH_O | METH_COEXIST,
1817 getitem__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001818 {"has_key", (PyCFunction)dict_has_key, METH_O,
Tim Petersf7f88b12000-12-13 23:18:45 +00001819 has_key__doc__},
1820 {"get", (PyCFunction)dict_get, METH_VARARGS,
1821 get__doc__},
1822 {"setdefault", (PyCFunction)dict_setdefault, METH_VARARGS,
1823 setdefault_doc__},
Raymond Hettingera3e1e4c2003-03-06 23:54:28 +00001824 {"pop", (PyCFunction)dict_pop, METH_VARARGS,
Just van Rossuma797d812002-11-23 09:45:04 +00001825 pop__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001826 {"popitem", (PyCFunction)dict_popitem, METH_NOARGS,
Tim Petersf7f88b12000-12-13 23:18:45 +00001827 popitem__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001828 {"keys", (PyCFunction)dict_keys, METH_NOARGS,
Tim Petersf7f88b12000-12-13 23:18:45 +00001829 keys__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001830 {"items", (PyCFunction)dict_items, METH_NOARGS,
Tim Petersf7f88b12000-12-13 23:18:45 +00001831 items__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001832 {"values", (PyCFunction)dict_values, METH_NOARGS,
Tim Petersf7f88b12000-12-13 23:18:45 +00001833 values__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001834 {"update", (PyCFunction)dict_update, METH_O,
Tim Petersf7f88b12000-12-13 23:18:45 +00001835 update__doc__},
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001836 {"fromkeys", (PyCFunction)dict_fromkeys, METH_VARARGS | METH_CLASS,
1837 fromkeys__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001838 {"clear", (PyCFunction)dict_clear, METH_NOARGS,
Tim Petersf7f88b12000-12-13 23:18:45 +00001839 clear__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001840 {"copy", (PyCFunction)dict_copy, METH_NOARGS,
Tim Petersf7f88b12000-12-13 23:18:45 +00001841 copy__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001842 {"iterkeys", (PyCFunction)dict_iterkeys, METH_NOARGS,
Guido van Rossum09e563a2001-05-01 12:10:21 +00001843 iterkeys__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001844 {"itervalues", (PyCFunction)dict_itervalues, METH_NOARGS,
Guido van Rossum09e563a2001-05-01 12:10:21 +00001845 itervalues__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001846 {"iteritems", (PyCFunction)dict_iteritems, METH_NOARGS,
Guido van Rossum09e563a2001-05-01 12:10:21 +00001847 iteritems__doc__},
Tim Petersf7f88b12000-12-13 23:18:45 +00001848 {NULL, NULL} /* sentinel */
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001849};
1850
Raymond Hettingerbc0f2ab2003-11-25 21:12:14 +00001851int
1852PyDict_Contains(PyObject *op, PyObject *key)
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00001853{
1854 long hash;
Raymond Hettingerbc0f2ab2003-11-25 21:12:14 +00001855 dictobject *mp = (dictobject *)op;
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00001856
Tim Peters0ab085c2001-09-14 00:25:33 +00001857 if (!PyString_CheckExact(key) ||
Tim Peters1f7df352002-03-29 03:29:08 +00001858 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00001859 hash = PyObject_Hash(key);
1860 if (hash == -1)
1861 return -1;
1862 }
Tim Petersdea48ec2001-05-22 20:40:22 +00001863 return (mp->ma_lookup)(mp, key, hash)->me_value != NULL;
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00001864}
1865
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00001866/* Hack to implement "key in dict" */
1867static PySequenceMethods dict_as_sequence = {
1868 0, /* sq_length */
1869 0, /* sq_concat */
1870 0, /* sq_repeat */
1871 0, /* sq_item */
1872 0, /* sq_slice */
1873 0, /* sq_ass_item */
1874 0, /* sq_ass_slice */
Raymond Hettingerbc0f2ab2003-11-25 21:12:14 +00001875 (objobjproc)PyDict_Contains, /* sq_contains */
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00001876 0, /* sq_inplace_concat */
1877 0, /* sq_inplace_repeat */
1878};
1879
Guido van Rossum09e563a2001-05-01 12:10:21 +00001880static PyObject *
Tim Peters6d6c1a32001-08-02 04:15:00 +00001881dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1882{
1883 PyObject *self;
1884
1885 assert(type != NULL && type->tp_alloc != NULL);
1886 self = type->tp_alloc(type, 0);
1887 if (self != NULL) {
1888 PyDictObject *d = (PyDictObject *)self;
1889 /* It's guaranteed that tp->alloc zeroed out the struct. */
1890 assert(d->ma_table == NULL && d->ma_fill == 0 && d->ma_used == 0);
1891 INIT_NONZERO_DICT_SLOTS(d);
1892 d->ma_lookup = lookdict_string;
1893#ifdef SHOW_CONVERSION_COUNTS
1894 ++created;
1895#endif
1896 }
1897 return self;
1898}
1899
Tim Peters25786c02001-09-02 08:22:48 +00001900static int
1901dict_init(PyObject *self, PyObject *args, PyObject *kwds)
1902{
1903 PyObject *arg = NULL;
Tim Peters1fc240e2001-10-26 05:06:50 +00001904 int result = 0;
Tim Peters25786c02001-09-02 08:22:48 +00001905
Raymond Hettingerea3fdf42002-12-29 16:33:45 +00001906 if (!PyArg_UnpackTuple(args, "dict", 0, 1, &arg))
Tim Peters1fc240e2001-10-26 05:06:50 +00001907 result = -1;
1908
1909 else if (arg != NULL) {
1910 if (PyObject_HasAttrString(arg, "keys"))
1911 result = PyDict_Merge(self, arg, 1);
1912 else
1913 result = PyDict_MergeFromSeq2(self, arg, 1);
Tim Peters25786c02001-09-02 08:22:48 +00001914 }
Just van Rossuma797d812002-11-23 09:45:04 +00001915 if (result == 0 && kwds != NULL)
1916 result = PyDict_Merge(self, kwds, 1);
Tim Peters1fc240e2001-10-26 05:06:50 +00001917 return result;
Tim Peters25786c02001-09-02 08:22:48 +00001918}
1919
Guido van Rossumdbb53d92001-12-03 16:32:18 +00001920static long
1921dict_nohash(PyObject *self)
1922{
1923 PyErr_SetString(PyExc_TypeError, "dict objects are unhashable");
1924 return -1;
1925}
1926
Tim Peters6d6c1a32001-08-02 04:15:00 +00001927static PyObject *
Guido van Rossum09e563a2001-05-01 12:10:21 +00001928dict_iter(dictobject *dict)
1929{
1930 return dictiter_new(dict, select_key);
1931}
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00001932
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001933PyDoc_STRVAR(dictionary_doc,
Tim Petersa427a2b2001-10-29 22:25:45 +00001934"dict() -> new empty dictionary.\n"
1935"dict(mapping) -> new dictionary initialized from a mapping object's\n"
Tim Peters1fc240e2001-10-26 05:06:50 +00001936" (key, value) pairs.\n"
Tim Petersa427a2b2001-10-29 22:25:45 +00001937"dict(seq) -> new dictionary initialized as if via:\n"
Tim Peters4d859532001-10-27 18:27:48 +00001938" d = {}\n"
1939" for k, v in seq:\n"
Just van Rossuma797d812002-11-23 09:45:04 +00001940" d[k] = v\n"
1941"dict(**kwargs) -> new dictionary initialized with the name=value pairs\n"
1942" in the keyword argument list. For example: dict(one=1, two=2)");
Tim Peters25786c02001-09-02 08:22:48 +00001943
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001944PyTypeObject PyDict_Type = {
1945 PyObject_HEAD_INIT(&PyType_Type)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001946 0,
Tim Petersa427a2b2001-10-29 22:25:45 +00001947 "dict",
Neil Schemenauere83c00e2001-08-29 23:54:21 +00001948 sizeof(dictobject),
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001949 0,
Guido van Rossumb9324202001-01-18 00:39:02 +00001950 (destructor)dict_dealloc, /* tp_dealloc */
1951 (printfunc)dict_print, /* tp_print */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001952 0, /* tp_getattr */
Guido van Rossumb9324202001-01-18 00:39:02 +00001953 0, /* tp_setattr */
Tim Peters4fa58bf2001-05-10 21:45:19 +00001954 (cmpfunc)dict_compare, /* tp_compare */
Guido van Rossumb9324202001-01-18 00:39:02 +00001955 (reprfunc)dict_repr, /* tp_repr */
1956 0, /* tp_as_number */
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00001957 &dict_as_sequence, /* tp_as_sequence */
Guido van Rossumb9324202001-01-18 00:39:02 +00001958 &dict_as_mapping, /* tp_as_mapping */
Guido van Rossumdbb53d92001-12-03 16:32:18 +00001959 dict_nohash, /* tp_hash */
Guido van Rossumb9324202001-01-18 00:39:02 +00001960 0, /* tp_call */
1961 0, /* tp_str */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001962 PyObject_GenericGetAttr, /* tp_getattro */
Guido van Rossumb9324202001-01-18 00:39:02 +00001963 0, /* tp_setattro */
1964 0, /* tp_as_buffer */
Neil Schemenauere83c00e2001-08-29 23:54:21 +00001965 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
Tim Peters6d6c1a32001-08-02 04:15:00 +00001966 Py_TPFLAGS_BASETYPE, /* tp_flags */
Tim Peters25786c02001-09-02 08:22:48 +00001967 dictionary_doc, /* tp_doc */
Guido van Rossumb9324202001-01-18 00:39:02 +00001968 (traverseproc)dict_traverse, /* tp_traverse */
1969 (inquiry)dict_tp_clear, /* tp_clear */
Tim Peterse63415e2001-05-08 04:38:29 +00001970 dict_richcompare, /* tp_richcompare */
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00001971 0, /* tp_weaklistoffset */
Guido van Rossum09e563a2001-05-01 12:10:21 +00001972 (getiterfunc)dict_iter, /* tp_iter */
Guido van Rossum213c7a62001-04-23 14:08:49 +00001973 0, /* tp_iternext */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001974 mapp_methods, /* tp_methods */
1975 0, /* tp_members */
1976 0, /* tp_getset */
1977 0, /* tp_base */
1978 0, /* tp_dict */
1979 0, /* tp_descr_get */
1980 0, /* tp_descr_set */
1981 0, /* tp_dictoffset */
Tim Peters25786c02001-09-02 08:22:48 +00001982 (initproc)dict_init, /* tp_init */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001983 PyType_GenericAlloc, /* tp_alloc */
1984 dict_new, /* tp_new */
Neil Schemenauer6189b892002-04-12 02:43:00 +00001985 PyObject_GC_Del, /* tp_free */
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001986};
1987
Guido van Rossum3cca2451997-05-16 14:23:33 +00001988/* For backward compatibility with old dictionary interface */
1989
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001990PyObject *
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +00001991PyDict_GetItemString(PyObject *v, const char *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001992{
Guido van Rossum3cca2451997-05-16 14:23:33 +00001993 PyObject *kv, *rv;
1994 kv = PyString_FromString(key);
1995 if (kv == NULL)
1996 return NULL;
Guido van Rossum3cca2451997-05-16 14:23:33 +00001997 rv = PyDict_GetItem(v, kv);
1998 Py_DECREF(kv);
1999 return rv;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002000}
2001
2002int
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +00002003PyDict_SetItemString(PyObject *v, const char *key, PyObject *item)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002004{
Guido van Rossum3cca2451997-05-16 14:23:33 +00002005 PyObject *kv;
2006 int err;
2007 kv = PyString_FromString(key);
2008 if (kv == NULL)
Guido van Rossum037b2201997-05-20 18:35:19 +00002009 return -1;
Guido van Rossum4f3bf1e1997-09-29 23:31:11 +00002010 PyString_InternInPlace(&kv); /* XXX Should we really? */
Guido van Rossum3cca2451997-05-16 14:23:33 +00002011 err = PyDict_SetItem(v, kv, item);
2012 Py_DECREF(kv);
2013 return err;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002014}
2015
2016int
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +00002017PyDict_DelItemString(PyObject *v, const char *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002018{
Guido van Rossum3cca2451997-05-16 14:23:33 +00002019 PyObject *kv;
2020 int err;
2021 kv = PyString_FromString(key);
2022 if (kv == NULL)
Guido van Rossum037b2201997-05-20 18:35:19 +00002023 return -1;
Guido van Rossum3cca2451997-05-16 14:23:33 +00002024 err = PyDict_DelItem(v, kv);
2025 Py_DECREF(kv);
2026 return err;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002027}
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002028
2029/* Dictionary iterator type */
2030
2031extern PyTypeObject PyDictIter_Type; /* Forward */
2032
2033typedef struct {
2034 PyObject_HEAD
Guido van Rossum2147df72002-07-16 20:30:22 +00002035 dictobject *di_dict; /* Set to NULL when iterator is exhausted */
Guido van Rossumb1f35bf2001-05-02 15:13:44 +00002036 int di_used;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002037 int di_pos;
Guido van Rossum09e563a2001-05-01 12:10:21 +00002038 binaryfunc di_select;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002039} dictiterobject;
2040
2041static PyObject *
Guido van Rossum09e563a2001-05-01 12:10:21 +00002042dictiter_new(dictobject *dict, binaryfunc select)
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002043{
2044 dictiterobject *di;
Neil Schemenauer6189b892002-04-12 02:43:00 +00002045 di = PyObject_New(dictiterobject, &PyDictIter_Type);
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002046 if (di == NULL)
2047 return NULL;
2048 Py_INCREF(dict);
2049 di->di_dict = dict;
Guido van Rossumb1f35bf2001-05-02 15:13:44 +00002050 di->di_used = dict->ma_used;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002051 di->di_pos = 0;
Guido van Rossum09e563a2001-05-01 12:10:21 +00002052 di->di_select = select;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002053 return (PyObject *)di;
2054}
2055
2056static void
2057dictiter_dealloc(dictiterobject *di)
2058{
Guido van Rossum2147df72002-07-16 20:30:22 +00002059 Py_XDECREF(di->di_dict);
Neil Schemenauer6189b892002-04-12 02:43:00 +00002060 PyObject_Del(di);
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002061}
2062
Guido van Rossum213c7a62001-04-23 14:08:49 +00002063static PyObject *dictiter_iternext(dictiterobject *di)
2064{
Guido van Rossum09e563a2001-05-01 12:10:21 +00002065 PyObject *key, *value;
Guido van Rossum213c7a62001-04-23 14:08:49 +00002066
Guido van Rossum2147df72002-07-16 20:30:22 +00002067 if (di->di_dict == NULL)
2068 return NULL;
2069
Guido van Rossumb1f35bf2001-05-02 15:13:44 +00002070 if (di->di_used != di->di_dict->ma_used) {
Guido van Rossum213c7a62001-04-23 14:08:49 +00002071 PyErr_SetString(PyExc_RuntimeError,
2072 "dictionary changed size during iteration");
Guido van Rossum2147df72002-07-16 20:30:22 +00002073 di->di_used = -1; /* Make this state sticky */
Guido van Rossum213c7a62001-04-23 14:08:49 +00002074 return NULL;
2075 }
Guido van Rossum2147df72002-07-16 20:30:22 +00002076 if (PyDict_Next((PyObject *)(di->di_dict), &di->di_pos, &key, &value))
Guido van Rossum09e563a2001-05-01 12:10:21 +00002077 return (*di->di_select)(key, value);
Guido van Rossum2147df72002-07-16 20:30:22 +00002078
2079 Py_DECREF(di->di_dict);
2080 di->di_dict = NULL;
Guido van Rossum213c7a62001-04-23 14:08:49 +00002081 return NULL;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002082}
2083
2084PyTypeObject PyDictIter_Type = {
2085 PyObject_HEAD_INIT(&PyType_Type)
2086 0, /* ob_size */
2087 "dictionary-iterator", /* tp_name */
2088 sizeof(dictiterobject), /* tp_basicsize */
2089 0, /* tp_itemsize */
2090 /* methods */
2091 (destructor)dictiter_dealloc, /* tp_dealloc */
2092 0, /* tp_print */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002093 0, /* tp_getattr */
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002094 0, /* tp_setattr */
2095 0, /* tp_compare */
2096 0, /* tp_repr */
2097 0, /* tp_as_number */
2098 0, /* tp_as_sequence */
2099 0, /* tp_as_mapping */
2100 0, /* tp_hash */
2101 0, /* tp_call */
2102 0, /* tp_str */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002103 PyObject_GenericGetAttr, /* tp_getattro */
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002104 0, /* tp_setattro */
2105 0, /* tp_as_buffer */
2106 Py_TPFLAGS_DEFAULT, /* tp_flags */
2107 0, /* tp_doc */
2108 0, /* tp_traverse */
2109 0, /* tp_clear */
2110 0, /* tp_richcompare */
2111 0, /* tp_weaklistoffset */
Raymond Hettinger1da1dbf2003-03-17 19:46:11 +00002112 PyObject_SelfIter, /* tp_iter */
Guido van Rossum213c7a62001-04-23 14:08:49 +00002113 (iternextfunc)dictiter_iternext, /* tp_iternext */
Guido van Rossum2147df72002-07-16 20:30:22 +00002114 0, /* tp_methods */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002115 0, /* tp_members */
2116 0, /* tp_getset */
2117 0, /* tp_base */
2118 0, /* tp_dict */
2119 0, /* tp_descr_get */
2120 0, /* tp_descr_set */
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002121};