blob: e0ac475346af35a3f9c1571f72914038519edab4 [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,
Tim Peters60b29962006-01-01 01:19:23 +00005 describing explorations into dictionary design and optimization.
Raymond Hettinger930427b2003-05-03 06:51:59 +00006 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
Guido van Rossum16e93a81997-01-28 00:00:11 +000012
Georg Brandlb9f4ad32006-10-29 18:31:42 +000013/* Set a key error with the specified argument, wrapping it in a
14 * tuple automatically so that tuple keys are not unpacked as the
15 * exception arguments. */
16static void
17set_key_error(PyObject *arg)
18{
19 PyObject *tup;
20 tup = PyTuple_Pack(1, arg);
21 if (!tup)
22 return; /* caller will expect error to be set anyway */
23 PyErr_SetObject(PyExc_KeyError, tup);
Neal Norwitz7b932da2006-10-29 23:39:03 +000024 Py_DECREF(tup);
Georg Brandlb9f4ad32006-10-29 18:31:42 +000025}
26
Tim Peterseb28ef22001-06-02 05:27:19 +000027/* Define this out if you don't want conversion statistics on exit. */
Fred Drake1bff34a2000-08-31 19:31:38 +000028#undef SHOW_CONVERSION_COUNTS
29
Tim Peterseb28ef22001-06-02 05:27:19 +000030/* See large comment block below. This must be >= 1. */
31#define PERTURB_SHIFT 5
32
Guido van Rossum16e93a81997-01-28 00:00:11 +000033/*
Tim Peterseb28ef22001-06-02 05:27:19 +000034Major subtleties ahead: Most hash schemes depend on having a "good" hash
35function, in the sense of simulating randomness. Python doesn't: its most
36important hash functions (for strings and ints) are very regular in common
37cases:
Tim Peters15d49292001-05-27 07:39:22 +000038
Tim Peterseb28ef22001-06-02 05:27:19 +000039>>> map(hash, (0, 1, 2, 3))
40[0, 1, 2, 3]
41>>> map(hash, ("namea", "nameb", "namec", "named"))
42[-1658398457, -1658398460, -1658398459, -1658398462]
43>>>
Tim Peters15d49292001-05-27 07:39:22 +000044
Tim Peterseb28ef22001-06-02 05:27:19 +000045This isn't necessarily bad! To the contrary, in a table of size 2**i, taking
46the low-order i bits as the initial table index is extremely fast, and there
47are no collisions at all for dicts indexed by a contiguous range of ints.
48The same is approximately true when keys are "consecutive" strings. So this
49gives better-than-random behavior in common cases, and that's very desirable.
Tim Peters15d49292001-05-27 07:39:22 +000050
Tim Peterseb28ef22001-06-02 05:27:19 +000051OTOH, when collisions occur, the tendency to fill contiguous slices of the
52hash table makes a good collision resolution strategy crucial. Taking only
53the last i bits of the hash code is also vulnerable: for example, consider
54[i << 16 for i in range(20000)] as a set of keys. Since ints are their own
55hash codes, and this fits in a dict of size 2**15, the last 15 bits of every
56hash code are all 0: they *all* map to the same table index.
Tim Peters15d49292001-05-27 07:39:22 +000057
Tim Peterseb28ef22001-06-02 05:27:19 +000058But catering to unusual cases should not slow the usual ones, so we just take
59the last i bits anyway. It's up to collision resolution to do the rest. If
60we *usually* find the key we're looking for on the first try (and, it turns
61out, we usually do -- the table load factor is kept under 2/3, so the odds
62are solidly in our favor), then it makes best sense to keep the initial index
63computation dirt cheap.
Tim Peters15d49292001-05-27 07:39:22 +000064
Tim Peterseb28ef22001-06-02 05:27:19 +000065The first half of collision resolution is to visit table indices via this
66recurrence:
Tim Peters15d49292001-05-27 07:39:22 +000067
Tim Peterseb28ef22001-06-02 05:27:19 +000068 j = ((5*j) + 1) mod 2**i
Tim Peters15d49292001-05-27 07:39:22 +000069
Tim Peterseb28ef22001-06-02 05:27:19 +000070For any initial j in range(2**i), repeating that 2**i times generates each
71int in range(2**i) exactly once (see any text on random-number generation for
72proof). By itself, this doesn't help much: like linear probing (setting
73j += 1, or j -= 1, on each loop trip), it scans the table entries in a fixed
74order. This would be bad, except that's not the only thing we do, and it's
75actually *good* in the common cases where hash keys are consecutive. In an
76example that's really too small to make this entirely clear, for a table of
77size 2**3 the order of indices is:
Tim Peters15d49292001-05-27 07:39:22 +000078
Tim Peterseb28ef22001-06-02 05:27:19 +000079 0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating]
80
81If two things come in at index 5, the first place we look after is index 2,
82not 6, so if another comes in at index 6 the collision at 5 didn't hurt it.
83Linear probing is deadly in this case because there the fixed probe order
84is the *same* as the order consecutive keys are likely to arrive. But it's
85extremely unlikely hash codes will follow a 5*j+1 recurrence by accident,
86and certain that consecutive hash codes do not.
87
88The other half of the strategy is to get the other bits of the hash code
89into play. This is done by initializing a (unsigned) vrbl "perturb" to the
90full hash code, and changing the recurrence to:
91
92 j = (5*j) + 1 + perturb;
93 perturb >>= PERTURB_SHIFT;
94 use j % 2**i as the next table index;
95
96Now the probe sequence depends (eventually) on every bit in the hash code,
97and the pseudo-scrambling property of recurring on 5*j+1 is more valuable,
98because it quickly magnifies small differences in the bits that didn't affect
99the initial index. Note that because perturb is unsigned, if the recurrence
100is executed often enough perturb eventually becomes and remains 0. At that
101point (very rarely reached) the recurrence is on (just) 5*j+1 again, and
102that's certain to find an empty slot eventually (since it generates every int
103in range(2**i), and we make sure there's always at least one empty slot).
104
105Selecting a good value for PERTURB_SHIFT is a balancing act. You want it
106small so that the high bits of the hash code continue to affect the probe
107sequence across iterations; but you want it large so that in really bad cases
108the high-order hash bits have an effect on early iterations. 5 was "the
109best" in minimizing total collisions across experiments Tim Peters ran (on
110both normal and pathological cases), but 4 and 6 weren't significantly worse.
111
112Historical: Reimer Behrends contributed the idea of using a polynomial-based
113approach, using repeated multiplication by x in GF(2**n) where an irreducible
114polynomial for each table size was chosen such that x was a primitive root.
115Christian Tismer later extended that to use division by x instead, as an
116efficient way to get the high bits of the hash code into play. This scheme
117also gave excellent collision statistics, but was more expensive: two
118if-tests were required inside the loop; computing "the next" index took about
119the same number of operations but without as much potential parallelism
120(e.g., computing 5*j can go on at the same time as computing 1+perturb in the
121above, and then shifting perturb can be done while the table index is being
Brett Cannon77ae87c2007-10-10 00:07:50 +0000122masked); and the PyDictObject struct required a member to hold the table's
Tim Peterseb28ef22001-06-02 05:27:19 +0000123polynomial. In Tim's experiments the current scheme ran faster, produced
124equally good collision statistics, needed less code & used less memory.
Tim Peters9b10f7e2006-05-30 04:16:25 +0000125
126Theoretical Python 2.5 headache: hash codes are only C "long", but
127sizeof(Py_ssize_t) > sizeof(long) may be possible. In that case, and if a
128dict is genuinely huge, then only the slots directly reachable via indexing
129by a C long can be the first slot in a probe sequence. The probe sequence
130will still eventually reach every slot in the table, but the collision rate
131on initial probes may be much higher than this scheme was designed for.
132Getting a hash code as fat as Py_ssize_t is the only real cure. But in
133practice, this probably won't make a lick of difference for many years (at
134which point everyone will have terabytes of RAM on 64-bit boxes).
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000135*/
Tim Petersdea48ec2001-05-22 20:40:22 +0000136
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000137/* Object used as dummy key to fill deleted entries */
Brett Cannon77ae87c2007-10-10 00:07:50 +0000138static PyObject *dummy = NULL; /* Initialized by first call to newPyDictObject() */
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000139
Armin Rigoe1709372006-04-12 17:06:05 +0000140#ifdef Py_REF_DEBUG
141PyObject *
142_PyDict_Dummy(void)
143{
144 return dummy;
145}
146#endif
147
Fred Drake1bff34a2000-08-31 19:31:38 +0000148/* forward declarations */
Brett Cannon77ae87c2007-10-10 00:07:50 +0000149static PyDictEntry *
150lookdict_string(PyDictObject *mp, PyObject *key, long hash);
Fred Drake1bff34a2000-08-31 19:31:38 +0000151
152#ifdef SHOW_CONVERSION_COUNTS
153static long created = 0L;
154static long converted = 0L;
155
156static void
157show_counts(void)
158{
159 fprintf(stderr, "created %ld string dicts\n", created);
160 fprintf(stderr, "converted %ld to normal dicts\n", converted);
161 fprintf(stderr, "%.2f%% conversion rate\n", (100.0*converted)/created);
162}
163#endif
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000164
Tim Peters6d6c1a32001-08-02 04:15:00 +0000165/* Initialization macros.
166 There are two ways to create a dict: PyDict_New() is the main C API
167 function, and the tp_new slot maps to dict_new(). In the latter case we
168 can save a little time over what PyDict_New does because it's guaranteed
169 that the PyDictObject struct is already zeroed out.
170 Everyone except dict_new() should use EMPTY_TO_MINSIZE (unless they have
171 an excellent reason not to).
172*/
173
174#define INIT_NONZERO_DICT_SLOTS(mp) do { \
Tim Petersdea48ec2001-05-22 20:40:22 +0000175 (mp)->ma_table = (mp)->ma_smalltable; \
Tim Peters6d6c1a32001-08-02 04:15:00 +0000176 (mp)->ma_mask = PyDict_MINSIZE - 1; \
177 } while(0)
178
179#define EMPTY_TO_MINSIZE(mp) do { \
180 memset((mp)->ma_smalltable, 0, sizeof((mp)->ma_smalltable)); \
Tim Petersdea48ec2001-05-22 20:40:22 +0000181 (mp)->ma_used = (mp)->ma_fill = 0; \
Tim Peters6d6c1a32001-08-02 04:15:00 +0000182 INIT_NONZERO_DICT_SLOTS(mp); \
Tim Petersdea48ec2001-05-22 20:40:22 +0000183 } while(0)
184
Raymond Hettinger43442782004-03-17 21:55:03 +0000185/* Dictionary reuse scheme to save calls to malloc, free, and memset */
Christian Heimes5b970ad2008-02-06 13:33:44 +0000186#ifndef PyDict_MAXFREELIST
187#define PyDict_MAXFREELIST 80
188#endif
189static PyDictObject *free_list[PyDict_MAXFREELIST];
190static int numfree = 0;
Raymond Hettinger43442782004-03-17 21:55:03 +0000191
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000192PyObject *
Thomas Wouters78890102000-07-22 19:25:51 +0000193PyDict_New(void)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000194{
Brett Cannon77ae87c2007-10-10 00:07:50 +0000195 register PyDictObject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000196 if (dummy == NULL) { /* Auto-initialize dummy */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000197 dummy = PyString_FromString("<dummy key>");
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000198 if (dummy == NULL)
199 return NULL;
Fred Drake1bff34a2000-08-31 19:31:38 +0000200#ifdef SHOW_CONVERSION_COUNTS
201 Py_AtExit(show_counts);
202#endif
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000203 }
Christian Heimes5b970ad2008-02-06 13:33:44 +0000204 if (numfree) {
205 mp = free_list[--numfree];
Raymond Hettinger43442782004-03-17 21:55:03 +0000206 assert (mp != NULL);
Christian Heimese93237d2007-12-19 02:37:44 +0000207 assert (Py_TYPE(mp) == &PyDict_Type);
Raymond Hettinger43442782004-03-17 21:55:03 +0000208 _Py_NewReference((PyObject *)mp);
209 if (mp->ma_fill) {
210 EMPTY_TO_MINSIZE(mp);
211 }
212 assert (mp->ma_used == 0);
213 assert (mp->ma_table == mp->ma_smalltable);
214 assert (mp->ma_mask == PyDict_MINSIZE - 1);
215 } else {
Brett Cannon77ae87c2007-10-10 00:07:50 +0000216 mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
Raymond Hettinger43442782004-03-17 21:55:03 +0000217 if (mp == NULL)
218 return NULL;
219 EMPTY_TO_MINSIZE(mp);
220 }
Fred Drake1bff34a2000-08-31 19:31:38 +0000221 mp->ma_lookup = lookdict_string;
222#ifdef SHOW_CONVERSION_COUNTS
223 ++created;
224#endif
Neil Schemenauere83c00e2001-08-29 23:54:21 +0000225 _PyObject_GC_TRACK(mp);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000226 return (PyObject *)mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000227}
228
229/*
230The basic lookup function used by all operations.
Guido van Rossum16e93a81997-01-28 00:00:11 +0000231This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000232Open addressing is preferred over chaining since the link overhead for
233chaining would be substantial (100% with typical malloc overhead).
234
Tim Peterseb28ef22001-06-02 05:27:19 +0000235The initial probe index is computed as hash mod the table size. Subsequent
236probe indices are computed as explained earlier.
Guido van Rossum2bc13791999-03-24 19:06:42 +0000237
238All arithmetic on hash should ignore overflow.
Guido van Rossum16e93a81997-01-28 00:00:11 +0000239
Tim Peterseb28ef22001-06-02 05:27:19 +0000240(The details in this version are due to Tim Peters, building on many past
241contributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and
242Christian Tismer).
Fred Drake1bff34a2000-08-31 19:31:38 +0000243
Tim Petersd770ebd2006-06-01 15:50:44 +0000244lookdict() is general-purpose, and may return NULL if (and only if) a
245comparison raises an exception (this was new in Python 2.5).
246lookdict_string() below is specialized to string keys, comparison of which can
247never raise an exception; that function can never return NULL. For both, when
Brett Cannon77ae87c2007-10-10 00:07:50 +0000248the key isn't found a PyDictEntry* is returned for which the me_value field is
Tim Petersd770ebd2006-06-01 15:50:44 +0000249NULL; this is the slot in the dict at which the key would have been found, and
250the caller can (if it wishes) add the <key, value> pair to the returned
Brett Cannon77ae87c2007-10-10 00:07:50 +0000251PyDictEntry*.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000252*/
Brett Cannon77ae87c2007-10-10 00:07:50 +0000253static PyDictEntry *
254lookdict(PyDictObject *mp, PyObject *key, register long hash)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000255{
Tim Petersd770ebd2006-06-01 15:50:44 +0000256 register size_t i;
Martin v. Löwis18e16552006-02-15 17:27:45 +0000257 register size_t perturb;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000258 register PyDictEntry *freeslot;
Tim Petersd770ebd2006-06-01 15:50:44 +0000259 register size_t mask = (size_t)mp->ma_mask;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000260 PyDictEntry *ep0 = mp->ma_table;
261 register PyDictEntry *ep;
Fred Drakec88b99c2000-08-31 19:04:07 +0000262 register int cmp;
Tim Peters453163d2001-06-03 04:54:32 +0000263 PyObject *startkey;
Tim Peterseb28ef22001-06-02 05:27:19 +0000264
Tim Petersd770ebd2006-06-01 15:50:44 +0000265 i = (size_t)hash & mask;
Guido van Rossumefb46091997-01-29 15:53:56 +0000266 ep = &ep0[i];
Guido van Rossumc1c7b1a1998-10-06 16:01:14 +0000267 if (ep->me_key == NULL || ep->me_key == key)
Guido van Rossum7d181591997-01-16 21:06:45 +0000268 return ep;
Tim Peters7b5d0af2001-06-03 04:14:43 +0000269
Guido van Rossum16e93a81997-01-28 00:00:11 +0000270 if (ep->me_key == dummy)
Guido van Rossum7d181591997-01-16 21:06:45 +0000271 freeslot = ep;
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000272 else {
Fred Drakec88b99c2000-08-31 19:04:07 +0000273 if (ep->me_hash == hash) {
Tim Peters453163d2001-06-03 04:54:32 +0000274 startkey = ep->me_key;
Georg Brandlede3a322007-11-29 18:33:01 +0000275 Py_INCREF(startkey);
Tim Peters453163d2001-06-03 04:54:32 +0000276 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Georg Brandlede3a322007-11-29 18:33:01 +0000277 Py_DECREF(startkey);
Tim Peters7b5d0af2001-06-03 04:14:43 +0000278 if (cmp < 0)
Armin Rigo35f6d362006-06-01 13:19:12 +0000279 return NULL;
Tim Peters453163d2001-06-03 04:54:32 +0000280 if (ep0 == mp->ma_table && ep->me_key == startkey) {
281 if (cmp > 0)
Armin Rigo35f6d362006-06-01 13:19:12 +0000282 return ep;
Tim Peters453163d2001-06-03 04:54:32 +0000283 }
284 else {
285 /* The compare did major nasty stuff to the
286 * dict: start over.
287 * XXX A clever adversary could prevent this
288 * XXX from terminating.
289 */
Armin Rigo35f6d362006-06-01 13:19:12 +0000290 return lookdict(mp, key, hash);
Tim Peters453163d2001-06-03 04:54:32 +0000291 }
Guido van Rossumfd7a0b81997-08-18 21:52:47 +0000292 }
293 freeslot = NULL;
Guido van Rossum2a61e741997-01-18 07:55:05 +0000294 }
Tim Peters15d49292001-05-27 07:39:22 +0000295
Tim Peters342c65e2001-05-13 06:43:53 +0000296 /* In the loop, me_key == dummy is by far (factor of 100s) the
297 least likely outcome, so test for that last. */
Tim Peterseb28ef22001-06-02 05:27:19 +0000298 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
299 i = (i << 2) + i + perturb + 1;
300 ep = &ep0[i & mask];
Armin Rigo35f6d362006-06-01 13:19:12 +0000301 if (ep->me_key == NULL)
302 return freeslot == NULL ? ep : freeslot;
Tim Peters7b5d0af2001-06-03 04:14:43 +0000303 if (ep->me_key == key)
Armin Rigo35f6d362006-06-01 13:19:12 +0000304 return ep;
Tim Peters7b5d0af2001-06-03 04:14:43 +0000305 if (ep->me_hash == hash && ep->me_key != dummy) {
Tim Peters453163d2001-06-03 04:54:32 +0000306 startkey = ep->me_key;
Georg Brandlede3a322007-11-29 18:33:01 +0000307 Py_INCREF(startkey);
Tim Peters453163d2001-06-03 04:54:32 +0000308 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Georg Brandlede3a322007-11-29 18:33:01 +0000309 Py_DECREF(startkey);
Tim Peters7b5d0af2001-06-03 04:14:43 +0000310 if (cmp < 0)
Armin Rigo35f6d362006-06-01 13:19:12 +0000311 return NULL;
Tim Peters453163d2001-06-03 04:54:32 +0000312 if (ep0 == mp->ma_table && ep->me_key == startkey) {
313 if (cmp > 0)
Armin Rigo35f6d362006-06-01 13:19:12 +0000314 return ep;
Tim Peters453163d2001-06-03 04:54:32 +0000315 }
316 else {
317 /* The compare did major nasty stuff to the
318 * dict: start over.
319 * XXX A clever adversary could prevent this
320 * XXX from terminating.
321 */
Armin Rigo35f6d362006-06-01 13:19:12 +0000322 return lookdict(mp, key, hash);
Tim Peters453163d2001-06-03 04:54:32 +0000323 }
Guido van Rossum16e93a81997-01-28 00:00:11 +0000324 }
Tim Peters342c65e2001-05-13 06:43:53 +0000325 else if (ep->me_key == dummy && freeslot == NULL)
326 freeslot = ep;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000327 }
Neal Norwitza5ccda92006-10-28 21:16:54 +0000328 assert(0); /* NOT REACHED */
329 return 0;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000330}
331
332/*
Fred Drake1bff34a2000-08-31 19:31:38 +0000333 * Hacked up version of lookdict which can assume keys are always strings;
Tim Petersd770ebd2006-06-01 15:50:44 +0000334 * this assumption allows testing for errors during PyObject_RichCompareBool()
335 * to be dropped; string-string comparisons never raise exceptions. This also
336 * means we don't need to go through PyObject_RichCompareBool(); we can always
337 * use _PyString_Eq() directly.
Fred Drake1bff34a2000-08-31 19:31:38 +0000338 *
Tim Petersd770ebd2006-06-01 15:50:44 +0000339 * This is valuable because dicts with only string keys are very common.
Fred Drake1bff34a2000-08-31 19:31:38 +0000340 */
Brett Cannon77ae87c2007-10-10 00:07:50 +0000341static PyDictEntry *
342lookdict_string(PyDictObject *mp, PyObject *key, register long hash)
Fred Drake1bff34a2000-08-31 19:31:38 +0000343{
Tim Petersd770ebd2006-06-01 15:50:44 +0000344 register size_t i;
Martin v. Löwis18e16552006-02-15 17:27:45 +0000345 register size_t perturb;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000346 register PyDictEntry *freeslot;
Tim Petersd770ebd2006-06-01 15:50:44 +0000347 register size_t mask = (size_t)mp->ma_mask;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000348 PyDictEntry *ep0 = mp->ma_table;
349 register PyDictEntry *ep;
Fred Drake1bff34a2000-08-31 19:31:38 +0000350
Tim Peters0ab085c2001-09-14 00:25:33 +0000351 /* Make sure this function doesn't have to handle non-string keys,
352 including subclasses of str; e.g., one reason to subclass
353 strings is to override __eq__, and for speed we don't cater to
354 that here. */
355 if (!PyString_CheckExact(key)) {
Fred Drake1bff34a2000-08-31 19:31:38 +0000356#ifdef SHOW_CONVERSION_COUNTS
357 ++converted;
358#endif
359 mp->ma_lookup = lookdict;
360 return lookdict(mp, key, hash);
361 }
Tim Peters2f228e72001-05-13 00:19:31 +0000362 i = hash & mask;
Fred Drake1bff34a2000-08-31 19:31:38 +0000363 ep = &ep0[i];
364 if (ep->me_key == NULL || ep->me_key == key)
365 return ep;
366 if (ep->me_key == dummy)
367 freeslot = ep;
368 else {
Tim Petersd770ebd2006-06-01 15:50:44 +0000369 if (ep->me_hash == hash && _PyString_Eq(ep->me_key, key))
Fred Drake1bff34a2000-08-31 19:31:38 +0000370 return ep;
Fred Drake1bff34a2000-08-31 19:31:38 +0000371 freeslot = NULL;
372 }
Tim Peters15d49292001-05-27 07:39:22 +0000373
Tim Peters342c65e2001-05-13 06:43:53 +0000374 /* In the loop, me_key == dummy is by far (factor of 100s) the
375 least likely outcome, so test for that last. */
Tim Peterseb28ef22001-06-02 05:27:19 +0000376 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
377 i = (i << 2) + i + perturb + 1;
378 ep = &ep0[i & mask];
Tim Peters342c65e2001-05-13 06:43:53 +0000379 if (ep->me_key == NULL)
380 return freeslot == NULL ? ep : freeslot;
381 if (ep->me_key == key
382 || (ep->me_hash == hash
383 && ep->me_key != dummy
Martin v. Löwiscd353062001-05-24 16:56:35 +0000384 && _PyString_Eq(ep->me_key, key)))
Fred Drake1bff34a2000-08-31 19:31:38 +0000385 return ep;
Tim Petersdea48ec2001-05-22 20:40:22 +0000386 if (ep->me_key == dummy && freeslot == NULL)
Tim Peters342c65e2001-05-13 06:43:53 +0000387 freeslot = ep;
Fred Drake1bff34a2000-08-31 19:31:38 +0000388 }
Neal Norwitza5ccda92006-10-28 21:16:54 +0000389 assert(0); /* NOT REACHED */
390 return 0;
Fred Drake1bff34a2000-08-31 19:31:38 +0000391}
392
393/*
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000394Internal routine to insert a new item into the table.
395Used both by the internal resize routine and by the public insert routine.
396Eats a reference to key and one to value.
Tim Petersd770ebd2006-06-01 15:50:44 +0000397Returns -1 if an error occurred, or 0 on success.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000398*/
Armin Rigo35f6d362006-06-01 13:19:12 +0000399static int
Brett Cannon77ae87c2007-10-10 00:07:50 +0000400insertdict(register PyDictObject *mp, PyObject *key, long hash, PyObject *value)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000401{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000402 PyObject *old_value;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000403 register PyDictEntry *ep;
Tim Peters6d6c1a32001-08-02 04:15:00 +0000404 typedef PyDictEntry *(*lookupfunc)(PyDictObject *, PyObject *, long);
405
406 assert(mp->ma_lookup != NULL);
407 ep = mp->ma_lookup(mp, key, hash);
Armin Rigo35f6d362006-06-01 13:19:12 +0000408 if (ep == NULL) {
409 Py_DECREF(key);
410 Py_DECREF(value);
411 return -1;
412 }
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000413 if (ep->me_value != NULL) {
Guido van Rossumd7047b31995-01-02 19:07:15 +0000414 old_value = ep->me_value;
415 ep->me_value = value;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000416 Py_DECREF(old_value); /* which **CAN** re-enter */
417 Py_DECREF(key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000418 }
419 else {
420 if (ep->me_key == NULL)
421 mp->ma_fill++;
Raymond Hettinger07ead172005-02-05 23:42:57 +0000422 else {
423 assert(ep->me_key == dummy);
424 Py_DECREF(dummy);
425 }
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000426 ep->me_key = key;
Tim Peters9b10f7e2006-05-30 04:16:25 +0000427 ep->me_hash = (Py_ssize_t)hash;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000428 ep->me_value = value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000429 mp->ma_used++;
430 }
Armin Rigo35f6d362006-06-01 13:19:12 +0000431 return 0;
432}
433
434/*
435Internal routine used by dictresize() to insert an item which is
436known to be absent from the dict. This routine also assumes that
437the dict contains no deleted entries. Besides the performance benefit,
438using insertdict() in dictresize() is dangerous (SF bug #1456209).
Tim Petersd770ebd2006-06-01 15:50:44 +0000439Note that no refcounts are changed by this routine; if needed, the caller
440is responsible for incref'ing `key` and `value`.
Armin Rigo35f6d362006-06-01 13:19:12 +0000441*/
442static void
Brett Cannon77ae87c2007-10-10 00:07:50 +0000443insertdict_clean(register PyDictObject *mp, PyObject *key, long hash,
Armin Rigo35f6d362006-06-01 13:19:12 +0000444 PyObject *value)
445{
Tim Petersd770ebd2006-06-01 15:50:44 +0000446 register size_t i;
Armin Rigo35f6d362006-06-01 13:19:12 +0000447 register size_t perturb;
Tim Petersd770ebd2006-06-01 15:50:44 +0000448 register size_t mask = (size_t)mp->ma_mask;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000449 PyDictEntry *ep0 = mp->ma_table;
450 register PyDictEntry *ep;
Armin Rigo35f6d362006-06-01 13:19:12 +0000451
452 i = hash & mask;
453 ep = &ep0[i];
454 for (perturb = hash; ep->me_key != NULL; perturb >>= PERTURB_SHIFT) {
455 i = (i << 2) + i + perturb + 1;
456 ep = &ep0[i & mask];
457 }
Tim Petersd770ebd2006-06-01 15:50:44 +0000458 assert(ep->me_value == NULL);
Armin Rigo35f6d362006-06-01 13:19:12 +0000459 mp->ma_fill++;
460 ep->me_key = key;
461 ep->me_hash = (Py_ssize_t)hash;
462 ep->me_value = value;
463 mp->ma_used++;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000464}
465
466/*
467Restructure the table by allocating a new table and reinserting all
468items again. When entries have been deleted, the new table may
469actually be smaller than the old one.
470*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000471static int
Brett Cannon77ae87c2007-10-10 00:07:50 +0000472dictresize(PyDictObject *mp, Py_ssize_t minused)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000473{
Tim Peters9b10f7e2006-05-30 04:16:25 +0000474 Py_ssize_t newsize;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000475 PyDictEntry *oldtable, *newtable, *ep;
Tim Peters9b10f7e2006-05-30 04:16:25 +0000476 Py_ssize_t i;
Tim Peters0c6010b2001-05-23 23:33:57 +0000477 int is_oldtable_malloced;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000478 PyDictEntry small_copy[PyDict_MINSIZE];
Tim Peters91a364d2001-05-19 07:04:38 +0000479
480 assert(minused >= 0);
Tim Peters0c6010b2001-05-23 23:33:57 +0000481
Tim Peterseb28ef22001-06-02 05:27:19 +0000482 /* Find the smallest table size > minused. */
Tim Peters6d6c1a32001-08-02 04:15:00 +0000483 for (newsize = PyDict_MINSIZE;
Tim Peterseb28ef22001-06-02 05:27:19 +0000484 newsize <= minused && newsize > 0;
485 newsize <<= 1)
486 ;
487 if (newsize <= 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000488 PyErr_NoMemory();
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000489 return -1;
490 }
Tim Peters0c6010b2001-05-23 23:33:57 +0000491
492 /* Get space for a new table. */
493 oldtable = mp->ma_table;
494 assert(oldtable != NULL);
495 is_oldtable_malloced = oldtable != mp->ma_smalltable;
496
Tim Peters6d6c1a32001-08-02 04:15:00 +0000497 if (newsize == PyDict_MINSIZE) {
Tim Petersf8a548c2001-05-24 16:26:40 +0000498 /* A large table is shrinking, or we can't get any smaller. */
Tim Petersdea48ec2001-05-22 20:40:22 +0000499 newtable = mp->ma_smalltable;
Tim Peters0c6010b2001-05-23 23:33:57 +0000500 if (newtable == oldtable) {
Tim Petersf8a548c2001-05-24 16:26:40 +0000501 if (mp->ma_fill == mp->ma_used) {
502 /* No dummies, so no point doing anything. */
Tim Peters0c6010b2001-05-23 23:33:57 +0000503 return 0;
Tim Petersf8a548c2001-05-24 16:26:40 +0000504 }
505 /* We're not going to resize it, but rebuild the
506 table anyway to purge old dummy entries.
507 Subtle: This is *necessary* if fill==size,
508 as lookdict needs at least one virgin slot to
509 terminate failing searches. If fill < size, it's
510 merely desirable, as dummies slow searches. */
511 assert(mp->ma_fill > mp->ma_used);
Tim Peters0c6010b2001-05-23 23:33:57 +0000512 memcpy(small_copy, oldtable, sizeof(small_copy));
513 oldtable = small_copy;
514 }
Tim Petersdea48ec2001-05-22 20:40:22 +0000515 }
516 else {
Brett Cannon77ae87c2007-10-10 00:07:50 +0000517 newtable = PyMem_NEW(PyDictEntry, newsize);
Tim Petersdea48ec2001-05-22 20:40:22 +0000518 if (newtable == NULL) {
519 PyErr_NoMemory();
520 return -1;
521 }
522 }
Tim Peters0c6010b2001-05-23 23:33:57 +0000523
524 /* Make the dict empty, using the new table. */
Tim Petersdea48ec2001-05-22 20:40:22 +0000525 assert(newtable != oldtable);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000526 mp->ma_table = newtable;
Tim Petersafb6ae82001-06-04 21:00:21 +0000527 mp->ma_mask = newsize - 1;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000528 memset(newtable, 0, sizeof(PyDictEntry) * newsize);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000529 mp->ma_used = 0;
Tim Petersdea48ec2001-05-22 20:40:22 +0000530 i = mp->ma_fill;
531 mp->ma_fill = 0;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000532
Tim Peters19283142001-05-17 22:25:34 +0000533 /* Copy the data over; this is refcount-neutral for active entries;
534 dummy entries aren't copied over, of course */
Tim Petersdea48ec2001-05-22 20:40:22 +0000535 for (ep = oldtable; i > 0; ep++) {
536 if (ep->me_value != NULL) { /* active entry */
537 --i;
Armin Rigo35f6d362006-06-01 13:19:12 +0000538 insertdict_clean(mp, ep->me_key, (long)ep->me_hash,
539 ep->me_value);
Tim Petersdea48ec2001-05-22 20:40:22 +0000540 }
Tim Peters19283142001-05-17 22:25:34 +0000541 else if (ep->me_key != NULL) { /* dummy entry */
Tim Petersdea48ec2001-05-22 20:40:22 +0000542 --i;
Tim Peters19283142001-05-17 22:25:34 +0000543 assert(ep->me_key == dummy);
544 Py_DECREF(ep->me_key);
Guido van Rossum255443b1998-04-10 22:47:14 +0000545 }
Tim Peters19283142001-05-17 22:25:34 +0000546 /* else key == value == NULL: nothing to do */
Guido van Rossumd7047b31995-01-02 19:07:15 +0000547 }
548
Tim Peters0c6010b2001-05-23 23:33:57 +0000549 if (is_oldtable_malloced)
Guido van Rossumb18618d2000-05-03 23:44:39 +0000550 PyMem_DEL(oldtable);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000551 return 0;
552}
553
Raymond Hettingerfd7ed402007-12-18 21:24:09 +0000554/* Create a new dictionary pre-sized to hold an estimated number of elements.
555 Underestimates are okay because the dictionary will resize as necessary.
556 Overestimates just mean the dictionary will be more sparse than usual.
557*/
558
559PyObject *
560_PyDict_NewPresized(Py_ssize_t minused)
561{
562 PyObject *op = PyDict_New();
563
564 if (minused>5 && op != NULL && dictresize((PyDictObject *)op, minused) == -1) {
565 Py_DECREF(op);
566 return NULL;
567 }
568 return op;
569}
570
Tim Petersd770ebd2006-06-01 15:50:44 +0000571/* Note that, for historical reasons, PyDict_GetItem() suppresses all errors
572 * that may occur (originally dicts supported only string keys, and exceptions
573 * weren't possible). So, while the original intent was that a NULL return
Andrew M. Kuchling0067b5f2006-08-04 20:37:43 +0000574 * meant the key wasn't present, in reality it can mean that, or that an error
Tim Petersd770ebd2006-06-01 15:50:44 +0000575 * (suppressed) occurred while computing the key's hash, or that some error
576 * (suppressed) occurred when comparing keys in the dict's internal probe
577 * sequence. A nasty example of the latter is when a Python-coded comparison
578 * function hits a stack-depth error, which can cause this to return NULL
579 * even if the key is present.
580 */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000581PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000582PyDict_GetItem(PyObject *op, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000583{
584 long hash;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000585 PyDictObject *mp = (PyDictObject *)op;
586 PyDictEntry *ep;
Armin Rigo35f6d362006-06-01 13:19:12 +0000587 PyThreadState *tstate;
Tim Petersd770ebd2006-06-01 15:50:44 +0000588 if (!PyDict_Check(op))
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000589 return NULL;
Tim Peters0ab085c2001-09-14 00:25:33 +0000590 if (!PyString_CheckExact(key) ||
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000591 (hash = ((PyStringObject *) key)->ob_shash) == -1)
Guido van Rossumca756f21997-01-23 19:39:29 +0000592 {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000593 hash = PyObject_Hash(key);
Guido van Rossum474b19e1998-05-14 01:00:51 +0000594 if (hash == -1) {
595 PyErr_Clear();
Guido van Rossumca756f21997-01-23 19:39:29 +0000596 return NULL;
Guido van Rossum474b19e1998-05-14 01:00:51 +0000597 }
Guido van Rossumca756f21997-01-23 19:39:29 +0000598 }
Armin Rigo35f6d362006-06-01 13:19:12 +0000599
600 /* We can arrive here with a NULL tstate during initialization:
601 try running "python -Wi" for an example related to string
602 interning. Let's just hope that no exception occurs then... */
Armin Rigoacd0d6d2006-06-10 10:57:40 +0000603 tstate = _PyThreadState_Current;
Armin Rigo35f6d362006-06-01 13:19:12 +0000604 if (tstate != NULL && tstate->curexc_type != NULL) {
605 /* preserve the existing exception */
606 PyObject *err_type, *err_value, *err_tb;
607 PyErr_Fetch(&err_type, &err_value, &err_tb);
608 ep = (mp->ma_lookup)(mp, key, hash);
609 /* ignore errors */
610 PyErr_Restore(err_type, err_value, err_tb);
611 if (ep == NULL)
612 return NULL;
613 }
614 else {
615 ep = (mp->ma_lookup)(mp, key, hash);
616 if (ep == NULL) {
617 PyErr_Clear();
618 return NULL;
619 }
620 }
621 return ep->me_value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000622}
623
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000624/* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
Tim Peters60b29962006-01-01 01:19:23 +0000625 * dictionary if it's merely replacing the value for an existing key.
626 * This means that it's safe to loop over a dictionary with PyDict_Next()
627 * and occasionally replace a value -- but you can't insert new keys or
628 * remove them.
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000629 */
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000630int
Tim Peters1f5871e2000-07-04 17:44:48 +0000631PyDict_SetItem(register PyObject *op, PyObject *key, PyObject *value)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000632{
Brett Cannon77ae87c2007-10-10 00:07:50 +0000633 register PyDictObject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000634 register long hash;
Tim Peters9b10f7e2006-05-30 04:16:25 +0000635 register Py_ssize_t n_used;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000636
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000637 if (!PyDict_Check(op)) {
638 PyErr_BadInternalCall();
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000639 return -1;
640 }
Neal Norwitz48808a12006-07-21 05:29:58 +0000641 assert(key);
642 assert(value);
Brett Cannon77ae87c2007-10-10 00:07:50 +0000643 mp = (PyDictObject *)op;
Tim Peters0ab085c2001-09-14 00:25:33 +0000644 if (PyString_CheckExact(key)) {
Guido van Rossum45ec02a2002-08-19 21:43:18 +0000645 hash = ((PyStringObject *)key)->ob_shash;
646 if (hash == -1)
647 hash = PyObject_Hash(key);
Guido van Rossum2a61e741997-01-18 07:55:05 +0000648 }
Tim Peters1f7df352002-03-29 03:29:08 +0000649 else {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000650 hash = PyObject_Hash(key);
Guido van Rossum2a61e741997-01-18 07:55:05 +0000651 if (hash == -1)
652 return -1;
Guido van Rossum2a61e741997-01-18 07:55:05 +0000653 }
Tim Petersafb6ae82001-06-04 21:00:21 +0000654 assert(mp->ma_fill <= mp->ma_mask); /* at least one empty slot */
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000655 n_used = mp->ma_used;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000656 Py_INCREF(value);
657 Py_INCREF(key);
Armin Rigo35f6d362006-06-01 13:19:12 +0000658 if (insertdict(mp, key, hash, value) != 0)
659 return -1;
Raymond Hettinger3539f6b2003-05-05 22:22:10 +0000660 /* If we added a key, we can safely resize. Otherwise just return!
661 * If fill >= 2/3 size, adjust size. Normally, this doubles or
662 * quaduples the size, but it's also possible for the dict to shrink
Tim Peters60b29962006-01-01 01:19:23 +0000663 * (if ma_fill is much larger than ma_used, meaning a lot of dict
Raymond Hettinger3539f6b2003-05-05 22:22:10 +0000664 * keys have been * deleted).
Tim Peters60b29962006-01-01 01:19:23 +0000665 *
Raymond Hettinger3539f6b2003-05-05 22:22:10 +0000666 * Quadrupling the size improves average dictionary sparseness
667 * (reducing collisions) at the cost of some memory and iteration
668 * speed (which loops over every possible entry). It also halves
Neal Norwitz80af59c2006-05-30 04:19:21 +0000669 * the number of expensive resize operations in a growing dictionary.
Tim Peters60b29962006-01-01 01:19:23 +0000670 *
671 * Very large dictionaries (over 50K items) use doubling instead.
Raymond Hettinger3539f6b2003-05-05 22:22:10 +0000672 * This may help applications with severe memory constraints.
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000673 */
Raymond Hettinger3539f6b2003-05-05 22:22:10 +0000674 if (!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))
675 return 0;
Tim Peters9b10f7e2006-05-30 04:16:25 +0000676 return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000677}
678
679int
Tim Peters1f5871e2000-07-04 17:44:48 +0000680PyDict_DelItem(PyObject *op, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000681{
Brett Cannon77ae87c2007-10-10 00:07:50 +0000682 register PyDictObject *mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000683 register long hash;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000684 register PyDictEntry *ep;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000685 PyObject *old_value, *old_key;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000686
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000687 if (!PyDict_Check(op)) {
688 PyErr_BadInternalCall();
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000689 return -1;
690 }
Neal Norwitz48808a12006-07-21 05:29:58 +0000691 assert(key);
Tim Peters0ab085c2001-09-14 00:25:33 +0000692 if (!PyString_CheckExact(key) ||
Tim Peters1f7df352002-03-29 03:29:08 +0000693 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000694 hash = PyObject_Hash(key);
Guido van Rossumca756f21997-01-23 19:39:29 +0000695 if (hash == -1)
696 return -1;
697 }
Brett Cannon77ae87c2007-10-10 00:07:50 +0000698 mp = (PyDictObject *)op;
Fred Drake1bff34a2000-08-31 19:31:38 +0000699 ep = (mp->ma_lookup)(mp, key, hash);
Armin Rigo35f6d362006-06-01 13:19:12 +0000700 if (ep == NULL)
701 return -1;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000702 if (ep->me_value == NULL) {
Georg Brandlb9f4ad32006-10-29 18:31:42 +0000703 set_key_error(key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000704 return -1;
705 }
Guido van Rossumd7047b31995-01-02 19:07:15 +0000706 old_key = ep->me_key;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000707 Py_INCREF(dummy);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000708 ep->me_key = dummy;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000709 old_value = ep->me_value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000710 ep->me_value = NULL;
711 mp->ma_used--;
Tim Petersea8f2bf2000-12-13 01:02:46 +0000712 Py_DECREF(old_value);
713 Py_DECREF(old_key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000714 return 0;
715}
716
Guido van Rossum25831651993-05-19 14:50:45 +0000717void
Tim Peters1f5871e2000-07-04 17:44:48 +0000718PyDict_Clear(PyObject *op)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000719{
Brett Cannon77ae87c2007-10-10 00:07:50 +0000720 PyDictObject *mp;
721 PyDictEntry *ep, *table;
Tim Petersdea48ec2001-05-22 20:40:22 +0000722 int table_is_malloced;
Tim Peters9b10f7e2006-05-30 04:16:25 +0000723 Py_ssize_t fill;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000724 PyDictEntry small_copy[PyDict_MINSIZE];
Tim Petersdea48ec2001-05-22 20:40:22 +0000725#ifdef Py_DEBUG
Tim Peters9b10f7e2006-05-30 04:16:25 +0000726 Py_ssize_t i, n;
Tim Petersdea48ec2001-05-22 20:40:22 +0000727#endif
728
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000729 if (!PyDict_Check(op))
Guido van Rossum25831651993-05-19 14:50:45 +0000730 return;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000731 mp = (PyDictObject *)op;
Tim Petersdea48ec2001-05-22 20:40:22 +0000732#ifdef Py_DEBUG
Tim Petersafb6ae82001-06-04 21:00:21 +0000733 n = mp->ma_mask + 1;
Tim Petersdea48ec2001-05-22 20:40:22 +0000734 i = 0;
735#endif
736
737 table = mp->ma_table;
738 assert(table != NULL);
739 table_is_malloced = table != mp->ma_smalltable;
740
741 /* This is delicate. During the process of clearing the dict,
742 * decrefs can cause the dict to mutate. To avoid fatal confusion
743 * (voice of experience), we have to make the dict empty before
744 * clearing the slots, and never refer to anything via mp->xxx while
745 * clearing.
746 */
747 fill = mp->ma_fill;
748 if (table_is_malloced)
Tim Peters6d6c1a32001-08-02 04:15:00 +0000749 EMPTY_TO_MINSIZE(mp);
Tim Petersdea48ec2001-05-22 20:40:22 +0000750
751 else if (fill > 0) {
752 /* It's a small table with something that needs to be cleared.
753 * Afraid the only safe way is to copy the dict entries into
754 * another small table first.
755 */
756 memcpy(small_copy, table, sizeof(small_copy));
757 table = small_copy;
Tim Peters6d6c1a32001-08-02 04:15:00 +0000758 EMPTY_TO_MINSIZE(mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000759 }
Tim Petersdea48ec2001-05-22 20:40:22 +0000760 /* else it's a small table that's already empty */
761
762 /* Now we can finally clear things. If C had refcounts, we could
763 * assert that the refcount on table is 1 now, i.e. that this function
764 * has unique access to it, so decref side-effects can't alter it.
765 */
766 for (ep = table; fill > 0; ++ep) {
767#ifdef Py_DEBUG
768 assert(i < n);
769 ++i;
770#endif
771 if (ep->me_key) {
772 --fill;
773 Py_DECREF(ep->me_key);
774 Py_XDECREF(ep->me_value);
775 }
776#ifdef Py_DEBUG
777 else
778 assert(ep->me_value == NULL);
779#endif
780 }
781
782 if (table_is_malloced)
783 PyMem_DEL(table);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000784}
785
Tim Peters080c88b2003-02-15 03:01:11 +0000786/*
787 * Iterate over a dict. Use like so:
788 *
Tim Peters9b10f7e2006-05-30 04:16:25 +0000789 * Py_ssize_t i;
Tim Peters080c88b2003-02-15 03:01:11 +0000790 * PyObject *key, *value;
791 * i = 0; # important! i should not otherwise be changed by you
Neal Norwitz07323012003-02-15 14:45:12 +0000792 * while (PyDict_Next(yourdict, &i, &key, &value)) {
Tim Peters080c88b2003-02-15 03:01:11 +0000793 * Refer to borrowed references in key and value.
794 * }
795 *
796 * CAUTION: In general, it isn't safe to use PyDict_Next in a loop that
Tim Peters67830702001-03-21 19:23:56 +0000797 * mutates the dict. One exception: it is safe if the loop merely changes
798 * the values associated with the keys (but doesn't insert new keys or
799 * delete keys), via PyDict_SetItem().
800 */
Guido van Rossum25831651993-05-19 14:50:45 +0000801int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000802PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000803{
Martin v. Löwis18e16552006-02-15 17:27:45 +0000804 register Py_ssize_t i;
Tim Peters9b10f7e2006-05-30 04:16:25 +0000805 register Py_ssize_t mask;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000806 register PyDictEntry *ep;
Raymond Hettinger43442782004-03-17 21:55:03 +0000807
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000808 if (!PyDict_Check(op))
Guido van Rossum25831651993-05-19 14:50:45 +0000809 return 0;
Guido van Rossum25831651993-05-19 14:50:45 +0000810 i = *ppos;
811 if (i < 0)
812 return 0;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000813 ep = ((PyDictObject *)op)->ma_table;
814 mask = ((PyDictObject *)op)->ma_mask;
Raymond Hettinger43442782004-03-17 21:55:03 +0000815 while (i <= mask && ep[i].me_value == NULL)
Guido van Rossum25831651993-05-19 14:50:45 +0000816 i++;
817 *ppos = i+1;
Raymond Hettinger43442782004-03-17 21:55:03 +0000818 if (i > mask)
Guido van Rossum25831651993-05-19 14:50:45 +0000819 return 0;
820 if (pkey)
Raymond Hettinger43442782004-03-17 21:55:03 +0000821 *pkey = ep[i].me_key;
Guido van Rossum25831651993-05-19 14:50:45 +0000822 if (pvalue)
Raymond Hettinger43442782004-03-17 21:55:03 +0000823 *pvalue = ep[i].me_value;
Guido van Rossum25831651993-05-19 14:50:45 +0000824 return 1;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000825}
826
Raymond Hettingerd6fc72a2007-02-19 02:03:19 +0000827/* Internal version of PyDict_Next that returns a hash value in addition to the key and value.*/
828int
829_PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue, long *phash)
830{
831 register Py_ssize_t i;
832 register Py_ssize_t mask;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000833 register PyDictEntry *ep;
Raymond Hettingerd6fc72a2007-02-19 02:03:19 +0000834
835 if (!PyDict_Check(op))
836 return 0;
837 i = *ppos;
838 if (i < 0)
839 return 0;
Brett Cannon77ae87c2007-10-10 00:07:50 +0000840 ep = ((PyDictObject *)op)->ma_table;
841 mask = ((PyDictObject *)op)->ma_mask;
Raymond Hettingerd6fc72a2007-02-19 02:03:19 +0000842 while (i <= mask && ep[i].me_value == NULL)
843 i++;
844 *ppos = i+1;
845 if (i > mask)
846 return 0;
847 *phash = (long)(ep[i].me_hash);
848 if (pkey)
849 *pkey = ep[i].me_key;
850 if (pvalue)
851 *pvalue = ep[i].me_value;
852 return 1;
853}
854
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000855/* Methods */
856
857static void
Brett Cannon77ae87c2007-10-10 00:07:50 +0000858dict_dealloc(register PyDictObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000859{
Brett Cannon77ae87c2007-10-10 00:07:50 +0000860 register PyDictEntry *ep;
Tim Peters9b10f7e2006-05-30 04:16:25 +0000861 Py_ssize_t fill = mp->ma_fill;
Guido van Rossumff413af2002-03-28 20:34:59 +0000862 PyObject_GC_UnTrack(mp);
Guido van Rossumd724b232000-03-13 16:01:29 +0000863 Py_TRASHCAN_SAFE_BEGIN(mp)
Tim Petersdea48ec2001-05-22 20:40:22 +0000864 for (ep = mp->ma_table; fill > 0; ep++) {
865 if (ep->me_key) {
866 --fill;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000867 Py_DECREF(ep->me_key);
Tim Petersdea48ec2001-05-22 20:40:22 +0000868 Py_XDECREF(ep->me_value);
Guido van Rossum255443b1998-04-10 22:47:14 +0000869 }
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000870 }
Tim Petersdea48ec2001-05-22 20:40:22 +0000871 if (mp->ma_table != mp->ma_smalltable)
Guido van Rossumb18618d2000-05-03 23:44:39 +0000872 PyMem_DEL(mp->ma_table);
Christian Heimes5b970ad2008-02-06 13:33:44 +0000873 if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
874 free_list[numfree++] = mp;
Tim Peters60b29962006-01-01 01:19:23 +0000875 else
Christian Heimese93237d2007-12-19 02:37:44 +0000876 Py_TYPE(mp)->tp_free((PyObject *)mp);
Guido van Rossumd724b232000-03-13 16:01:29 +0000877 Py_TRASHCAN_SAFE_END(mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000878}
879
880static int
Brett Cannon77ae87c2007-10-10 00:07:50 +0000881dict_print(register PyDictObject *mp, register FILE *fp, register int flags)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000882{
Tim Peters9b10f7e2006-05-30 04:16:25 +0000883 register Py_ssize_t i;
884 register Py_ssize_t any;
Tim Peters33f4a6a2006-05-30 05:23:59 +0000885 int status;
Guido van Rossum255443b1998-04-10 22:47:14 +0000886
Tim Peters33f4a6a2006-05-30 05:23:59 +0000887 status = Py_ReprEnter((PyObject*)mp);
888 if (status != 0) {
889 if (status < 0)
890 return status;
Brett Cannon01531592007-09-17 03:28:34 +0000891 Py_BEGIN_ALLOW_THREADS
Guido van Rossum255443b1998-04-10 22:47:14 +0000892 fprintf(fp, "{...}");
Brett Cannon01531592007-09-17 03:28:34 +0000893 Py_END_ALLOW_THREADS
Guido van Rossum255443b1998-04-10 22:47:14 +0000894 return 0;
895 }
896
Brett Cannon01531592007-09-17 03:28:34 +0000897 Py_BEGIN_ALLOW_THREADS
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000898 fprintf(fp, "{");
Brett Cannon01531592007-09-17 03:28:34 +0000899 Py_END_ALLOW_THREADS
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000900 any = 0;
Tim Petersafb6ae82001-06-04 21:00:21 +0000901 for (i = 0; i <= mp->ma_mask; i++) {
Brett Cannon77ae87c2007-10-10 00:07:50 +0000902 PyDictEntry *ep = mp->ma_table + i;
Tim Peters23cf6be2001-06-02 08:02:56 +0000903 PyObject *pvalue = ep->me_value;
904 if (pvalue != NULL) {
905 /* Prevent PyObject_Repr from deleting value during
906 key format */
907 Py_INCREF(pvalue);
Brett Cannon01531592007-09-17 03:28:34 +0000908 if (any++ > 0) {
909 Py_BEGIN_ALLOW_THREADS
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000910 fprintf(fp, ", ");
Brett Cannon01531592007-09-17 03:28:34 +0000911 Py_END_ALLOW_THREADS
912 }
Guido van Rossum255443b1998-04-10 22:47:14 +0000913 if (PyObject_Print((PyObject *)ep->me_key, fp, 0)!=0) {
Tim Peters23cf6be2001-06-02 08:02:56 +0000914 Py_DECREF(pvalue);
Guido van Rossum255443b1998-04-10 22:47:14 +0000915 Py_ReprLeave((PyObject*)mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000916 return -1;
Guido van Rossum255443b1998-04-10 22:47:14 +0000917 }
Brett Cannon01531592007-09-17 03:28:34 +0000918 Py_BEGIN_ALLOW_THREADS
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000919 fprintf(fp, ": ");
Brett Cannon01531592007-09-17 03:28:34 +0000920 Py_END_ALLOW_THREADS
Tim Peters19b77cf2001-06-02 08:27:39 +0000921 if (PyObject_Print(pvalue, fp, 0) != 0) {
Tim Peters23cf6be2001-06-02 08:02:56 +0000922 Py_DECREF(pvalue);
Guido van Rossum255443b1998-04-10 22:47:14 +0000923 Py_ReprLeave((PyObject*)mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000924 return -1;
Guido van Rossum255443b1998-04-10 22:47:14 +0000925 }
Tim Peters23cf6be2001-06-02 08:02:56 +0000926 Py_DECREF(pvalue);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000927 }
928 }
Brett Cannon01531592007-09-17 03:28:34 +0000929 Py_BEGIN_ALLOW_THREADS
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000930 fprintf(fp, "}");
Brett Cannon01531592007-09-17 03:28:34 +0000931 Py_END_ALLOW_THREADS
Guido van Rossum255443b1998-04-10 22:47:14 +0000932 Py_ReprLeave((PyObject*)mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000933 return 0;
934}
935
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000936static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +0000937dict_repr(PyDictObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000938{
Martin v. Löwis18e16552006-02-15 17:27:45 +0000939 Py_ssize_t i;
Tim Petersa7259592001-06-16 05:11:17 +0000940 PyObject *s, *temp, *colon = NULL;
941 PyObject *pieces = NULL, *result = NULL;
942 PyObject *key, *value;
Guido van Rossum255443b1998-04-10 22:47:14 +0000943
Tim Petersa7259592001-06-16 05:11:17 +0000944 i = Py_ReprEnter((PyObject *)mp);
Guido van Rossum255443b1998-04-10 22:47:14 +0000945 if (i != 0) {
Tim Petersa7259592001-06-16 05:11:17 +0000946 return i > 0 ? PyString_FromString("{...}") : NULL;
Guido van Rossum255443b1998-04-10 22:47:14 +0000947 }
948
Tim Petersa7259592001-06-16 05:11:17 +0000949 if (mp->ma_used == 0) {
950 result = PyString_FromString("{}");
951 goto Done;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000952 }
Tim Petersa7259592001-06-16 05:11:17 +0000953
954 pieces = PyList_New(0);
955 if (pieces == NULL)
956 goto Done;
957
958 colon = PyString_FromString(": ");
959 if (colon == NULL)
960 goto Done;
961
962 /* Do repr() on each key+value pair, and insert ": " between them.
963 Note that repr may mutate the dict. */
Tim Petersc6057842001-06-16 07:52:53 +0000964 i = 0;
965 while (PyDict_Next((PyObject *)mp, &i, &key, &value)) {
Tim Petersa7259592001-06-16 05:11:17 +0000966 int status;
967 /* Prevent repr from deleting value during key format. */
968 Py_INCREF(value);
969 s = PyObject_Repr(key);
970 PyString_Concat(&s, colon);
971 PyString_ConcatAndDel(&s, PyObject_Repr(value));
972 Py_DECREF(value);
973 if (s == NULL)
974 goto Done;
975 status = PyList_Append(pieces, s);
976 Py_DECREF(s); /* append created a new ref */
977 if (status < 0)
978 goto Done;
979 }
980
981 /* Add "{}" decorations to the first and last items. */
982 assert(PyList_GET_SIZE(pieces) > 0);
983 s = PyString_FromString("{");
984 if (s == NULL)
985 goto Done;
986 temp = PyList_GET_ITEM(pieces, 0);
987 PyString_ConcatAndDel(&s, temp);
988 PyList_SET_ITEM(pieces, 0, s);
989 if (s == NULL)
990 goto Done;
991
992 s = PyString_FromString("}");
993 if (s == NULL)
994 goto Done;
995 temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
996 PyString_ConcatAndDel(&temp, s);
997 PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
998 if (temp == NULL)
999 goto Done;
1000
1001 /* Paste them all together with ", " between. */
1002 s = PyString_FromString(", ");
1003 if (s == NULL)
1004 goto Done;
1005 result = _PyString_Join(s, pieces);
Tim Peters0ab085c2001-09-14 00:25:33 +00001006 Py_DECREF(s);
Tim Petersa7259592001-06-16 05:11:17 +00001007
1008Done:
1009 Py_XDECREF(pieces);
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001010 Py_XDECREF(colon);
Tim Petersa7259592001-06-16 05:11:17 +00001011 Py_ReprLeave((PyObject *)mp);
1012 return result;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001013}
1014
Martin v. Löwis18e16552006-02-15 17:27:45 +00001015static Py_ssize_t
Brett Cannon77ae87c2007-10-10 00:07:50 +00001016dict_length(PyDictObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001017{
1018 return mp->ma_used;
1019}
1020
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001021static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00001022dict_subscript(PyDictObject *mp, register PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001023{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001024 PyObject *v;
Sjoerd Mullender3bb8a051993-10-22 12:04:32 +00001025 long hash;
Brett Cannon77ae87c2007-10-10 00:07:50 +00001026 PyDictEntry *ep;
Tim Petersdea48ec2001-05-22 20:40:22 +00001027 assert(mp->ma_table != NULL);
Tim Peters0ab085c2001-09-14 00:25:33 +00001028 if (!PyString_CheckExact(key) ||
Tim Peters1f7df352002-03-29 03:29:08 +00001029 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001030 hash = PyObject_Hash(key);
Guido van Rossumca756f21997-01-23 19:39:29 +00001031 if (hash == -1)
1032 return NULL;
1033 }
Armin Rigo35f6d362006-06-01 13:19:12 +00001034 ep = (mp->ma_lookup)(mp, key, hash);
1035 if (ep == NULL)
1036 return NULL;
1037 v = ep->me_value;
Guido van Rossum1968ad32006-02-25 22:38:04 +00001038 if (v == NULL) {
1039 if (!PyDict_CheckExact(mp)) {
1040 /* Look up __missing__ method if we're a subclass. */
Guido van Rossum4b92a822006-02-25 23:32:30 +00001041 PyObject *missing;
Guido van Rossum1968ad32006-02-25 22:38:04 +00001042 static PyObject *missing_str = NULL;
1043 if (missing_str == NULL)
Tim Peters9b10f7e2006-05-30 04:16:25 +00001044 missing_str =
Guido van Rossum1968ad32006-02-25 22:38:04 +00001045 PyString_InternFromString("__missing__");
Christian Heimese93237d2007-12-19 02:37:44 +00001046 missing = _PyType_Lookup(Py_TYPE(mp), missing_str);
Guido van Rossum1968ad32006-02-25 22:38:04 +00001047 if (missing != NULL)
1048 return PyObject_CallFunctionObjArgs(missing,
1049 (PyObject *)mp, key, NULL);
1050 }
Georg Brandlb9f4ad32006-10-29 18:31:42 +00001051 set_key_error(key);
Guido van Rossum1968ad32006-02-25 22:38:04 +00001052 return NULL;
1053 }
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001054 else
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001055 Py_INCREF(v);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001056 return v;
1057}
1058
1059static int
Brett Cannon77ae87c2007-10-10 00:07:50 +00001060dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001061{
1062 if (w == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001063 return PyDict_DelItem((PyObject *)mp, v);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001064 else
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001065 return PyDict_SetItem((PyObject *)mp, v, w);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001066}
1067
Guido van Rossuma9e7a811997-05-13 21:02:11 +00001068static PyMappingMethods dict_as_mapping = {
Martin v. Löwis18e16552006-02-15 17:27:45 +00001069 (lenfunc)dict_length, /*mp_length*/
Guido van Rossuma9e7a811997-05-13 21:02:11 +00001070 (binaryfunc)dict_subscript, /*mp_subscript*/
1071 (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001072};
1073
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001074static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00001075dict_keys(register PyDictObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001076{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001077 register PyObject *v;
Tim Peters9b10f7e2006-05-30 04:16:25 +00001078 register Py_ssize_t i, j;
Brett Cannon77ae87c2007-10-10 00:07:50 +00001079 PyDictEntry *ep;
Tim Peters9b10f7e2006-05-30 04:16:25 +00001080 Py_ssize_t mask, n;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001081
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001082 again:
1083 n = mp->ma_used;
1084 v = PyList_New(n);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001085 if (v == NULL)
1086 return NULL;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001087 if (n != mp->ma_used) {
1088 /* Durnit. The allocations caused the dict to resize.
1089 * Just start over, this shouldn't normally happen.
1090 */
1091 Py_DECREF(v);
1092 goto again;
1093 }
Raymond Hettinger43442782004-03-17 21:55:03 +00001094 ep = mp->ma_table;
1095 mask = mp->ma_mask;
1096 for (i = 0, j = 0; i <= mask; i++) {
1097 if (ep[i].me_value != NULL) {
1098 PyObject *key = ep[i].me_key;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001099 Py_INCREF(key);
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001100 PyList_SET_ITEM(v, j, key);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001101 j++;
1102 }
1103 }
Raymond Hettinger43442782004-03-17 21:55:03 +00001104 assert(j == n);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001105 return v;
1106}
1107
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001108static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00001109dict_values(register PyDictObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001110{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001111 register PyObject *v;
Tim Peters9b10f7e2006-05-30 04:16:25 +00001112 register Py_ssize_t i, j;
Brett Cannon77ae87c2007-10-10 00:07:50 +00001113 PyDictEntry *ep;
Tim Peters9b10f7e2006-05-30 04:16:25 +00001114 Py_ssize_t mask, n;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001115
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001116 again:
1117 n = mp->ma_used;
1118 v = PyList_New(n);
Guido van Rossum25831651993-05-19 14:50:45 +00001119 if (v == NULL)
1120 return NULL;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001121 if (n != mp->ma_used) {
1122 /* Durnit. The allocations caused the dict to resize.
1123 * Just start over, this shouldn't normally happen.
1124 */
1125 Py_DECREF(v);
1126 goto again;
1127 }
Raymond Hettinger43442782004-03-17 21:55:03 +00001128 ep = mp->ma_table;
1129 mask = mp->ma_mask;
1130 for (i = 0, j = 0; i <= mask; i++) {
1131 if (ep[i].me_value != NULL) {
1132 PyObject *value = ep[i].me_value;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001133 Py_INCREF(value);
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001134 PyList_SET_ITEM(v, j, value);
Guido van Rossum25831651993-05-19 14:50:45 +00001135 j++;
1136 }
1137 }
Raymond Hettinger43442782004-03-17 21:55:03 +00001138 assert(j == n);
Guido van Rossum25831651993-05-19 14:50:45 +00001139 return v;
1140}
1141
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001142static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00001143dict_items(register PyDictObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001144{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001145 register PyObject *v;
Tim Peters9b10f7e2006-05-30 04:16:25 +00001146 register Py_ssize_t i, j, n;
1147 Py_ssize_t mask;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001148 PyObject *item, *key, *value;
Brett Cannon77ae87c2007-10-10 00:07:50 +00001149 PyDictEntry *ep;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001150
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001151 /* Preallocate the list of tuples, to avoid allocations during
1152 * the loop over the items, which could trigger GC, which
1153 * could resize the dict. :-(
1154 */
1155 again:
1156 n = mp->ma_used;
1157 v = PyList_New(n);
Guido van Rossum25831651993-05-19 14:50:45 +00001158 if (v == NULL)
1159 return NULL;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001160 for (i = 0; i < n; i++) {
1161 item = PyTuple_New(2);
1162 if (item == NULL) {
1163 Py_DECREF(v);
1164 return NULL;
1165 }
1166 PyList_SET_ITEM(v, i, item);
1167 }
1168 if (n != mp->ma_used) {
1169 /* Durnit. The allocations caused the dict to resize.
1170 * Just start over, this shouldn't normally happen.
1171 */
1172 Py_DECREF(v);
1173 goto again;
1174 }
1175 /* Nothing we do below makes any function calls. */
Raymond Hettinger43442782004-03-17 21:55:03 +00001176 ep = mp->ma_table;
1177 mask = mp->ma_mask;
1178 for (i = 0, j = 0; i <= mask; i++) {
Raymond Hettinger06905122004-03-19 10:30:00 +00001179 if ((value=ep[i].me_value) != NULL) {
Raymond Hettinger43442782004-03-17 21:55:03 +00001180 key = ep[i].me_key;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001181 item = PyList_GET_ITEM(v, j);
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001182 Py_INCREF(key);
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001183 PyTuple_SET_ITEM(item, 0, key);
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001184 Py_INCREF(value);
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001185 PyTuple_SET_ITEM(item, 1, value);
Guido van Rossum25831651993-05-19 14:50:45 +00001186 j++;
1187 }
1188 }
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001189 assert(j == n);
Guido van Rossum25831651993-05-19 14:50:45 +00001190 return v;
1191}
1192
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001193static PyObject *
Tim Petersbca1cbc2002-12-09 22:56:13 +00001194dict_fromkeys(PyObject *cls, PyObject *args)
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001195{
1196 PyObject *seq;
1197 PyObject *value = Py_None;
1198 PyObject *it; /* iter(seq) */
1199 PyObject *key;
1200 PyObject *d;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001201 int status;
1202
Raymond Hettingerea3fdf42002-12-29 16:33:45 +00001203 if (!PyArg_UnpackTuple(args, "fromkeys", 1, 2, &seq, &value))
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001204 return NULL;
1205
1206 d = PyObject_CallObject(cls, NULL);
1207 if (d == NULL)
1208 return NULL;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001209
Raymond Hettingercdcf8872007-11-07 02:26:17 +00001210 if (PyDict_CheckExact(d) && PyDict_CheckExact(seq)) {
1211 PyDictObject *mp = (PyDictObject *)d;
1212 PyObject *oldvalue;
1213 Py_ssize_t pos = 0;
1214 PyObject *key;
1215 long hash;
1216
Raymond Hettinger34448792007-11-09 23:14:44 +00001217 if (dictresize(mp, PySet_GET_SIZE(seq)))
Raymond Hettingercdcf8872007-11-07 02:26:17 +00001218 return NULL;
1219
1220 while (_PyDict_Next(seq, &pos, &key, &oldvalue, &hash)) {
1221 Py_INCREF(key);
1222 Py_INCREF(value);
1223 if (insertdict(mp, key, hash, value))
1224 return NULL;
1225 }
1226 return d;
1227 }
1228
Raymond Hettinger0bbbfc42007-03-20 21:27:24 +00001229 if (PyDict_CheckExact(d) && PyAnySet_CheckExact(seq)) {
Brett Cannon77ae87c2007-10-10 00:07:50 +00001230 PyDictObject *mp = (PyDictObject *)d;
Raymond Hettinger0bbbfc42007-03-20 21:27:24 +00001231 Py_ssize_t pos = 0;
1232 PyObject *key;
1233 long hash;
1234
1235 if (dictresize(mp, PySet_GET_SIZE(seq)))
1236 return NULL;
1237
1238 while (_PySet_NextEntry(seq, &pos, &key, &hash)) {
1239 Py_INCREF(key);
Raymond Hettingere3146f52007-03-21 20:33:57 +00001240 Py_INCREF(value);
1241 if (insertdict(mp, key, hash, value))
Raymond Hettinger0bbbfc42007-03-20 21:27:24 +00001242 return NULL;
1243 }
1244 return d;
1245 }
1246
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001247 it = PyObject_GetIter(seq);
1248 if (it == NULL){
1249 Py_DECREF(d);
1250 return NULL;
1251 }
1252
Raymond Hettinger34448792007-11-09 23:14:44 +00001253 if (PyDict_CheckExact(d)) {
1254 while ((key = PyIter_Next(it)) != NULL) {
1255 status = PyDict_SetItem(d, key, value);
1256 Py_DECREF(key);
1257 if (status < 0)
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001258 goto Fail;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001259 }
Raymond Hettinger34448792007-11-09 23:14:44 +00001260 } else {
1261 while ((key = PyIter_Next(it)) != NULL) {
1262 status = PyObject_SetItem(d, key, value);
1263 Py_DECREF(key);
1264 if (status < 0)
1265 goto Fail;
1266 }
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001267 }
1268
Raymond Hettinger34448792007-11-09 23:14:44 +00001269 if (PyErr_Occurred())
1270 goto Fail;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001271 Py_DECREF(it);
1272 return d;
1273
1274Fail:
1275 Py_DECREF(it);
1276 Py_DECREF(d);
1277 return NULL;
1278}
1279
Raymond Hettinger31017ae2004-03-04 08:25:44 +00001280static int
1281dict_update_common(PyObject *self, PyObject *args, PyObject *kwds, char *methname)
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001282{
Raymond Hettinger31017ae2004-03-04 08:25:44 +00001283 PyObject *arg = NULL;
1284 int result = 0;
1285
1286 if (!PyArg_UnpackTuple(args, methname, 0, 1, &arg))
1287 result = -1;
1288
1289 else if (arg != NULL) {
1290 if (PyObject_HasAttrString(arg, "keys"))
1291 result = PyDict_Merge(self, arg, 1);
1292 else
1293 result = PyDict_MergeFromSeq2(self, arg, 1);
1294 }
1295 if (result == 0 && kwds != NULL)
1296 result = PyDict_Merge(self, kwds, 1);
1297 return result;
1298}
1299
1300static PyObject *
1301dict_update(PyObject *self, PyObject *args, PyObject *kwds)
1302{
Raymond Hettinger7892b1c2004-04-12 18:10:01 +00001303 if (dict_update_common(self, args, kwds, "update") != -1)
1304 Py_RETURN_NONE;
1305 return NULL;
Tim Peters6d6c1a32001-08-02 04:15:00 +00001306}
1307
Guido van Rossum05ac6de2001-08-10 20:28:28 +00001308/* Update unconditionally replaces existing items.
1309 Merge has a 3rd argument 'override'; if set, it acts like Update,
Tim Peters1fc240e2001-10-26 05:06:50 +00001310 otherwise it leaves existing items unchanged.
1311
1312 PyDict_{Update,Merge} update/merge from a mapping object.
1313
Tim Petersf582b822001-12-11 18:51:08 +00001314 PyDict_MergeFromSeq2 updates/merges from any iterable object
Tim Peters1fc240e2001-10-26 05:06:50 +00001315 producing iterable objects of length 2.
1316*/
1317
Tim Petersf582b822001-12-11 18:51:08 +00001318int
Tim Peters1fc240e2001-10-26 05:06:50 +00001319PyDict_MergeFromSeq2(PyObject *d, PyObject *seq2, int override)
1320{
1321 PyObject *it; /* iter(seq2) */
Tim Peters9b10f7e2006-05-30 04:16:25 +00001322 Py_ssize_t i; /* index into seq2 of current element */
Tim Peters1fc240e2001-10-26 05:06:50 +00001323 PyObject *item; /* seq2[i] */
1324 PyObject *fast; /* item as a 2-tuple or 2-list */
1325
1326 assert(d != NULL);
1327 assert(PyDict_Check(d));
1328 assert(seq2 != NULL);
1329
1330 it = PyObject_GetIter(seq2);
1331 if (it == NULL)
1332 return -1;
1333
1334 for (i = 0; ; ++i) {
1335 PyObject *key, *value;
Martin v. Löwis18e16552006-02-15 17:27:45 +00001336 Py_ssize_t n;
Tim Peters1fc240e2001-10-26 05:06:50 +00001337
1338 fast = NULL;
1339 item = PyIter_Next(it);
1340 if (item == NULL) {
1341 if (PyErr_Occurred())
1342 goto Fail;
1343 break;
1344 }
1345
1346 /* Convert item to sequence, and verify length 2. */
1347 fast = PySequence_Fast(item, "");
1348 if (fast == NULL) {
1349 if (PyErr_ExceptionMatches(PyExc_TypeError))
1350 PyErr_Format(PyExc_TypeError,
1351 "cannot convert dictionary update "
Neal Norwitzd3881b02006-05-30 04:25:05 +00001352 "sequence element #%zd to a sequence",
Tim Peters1fc240e2001-10-26 05:06:50 +00001353 i);
1354 goto Fail;
1355 }
1356 n = PySequence_Fast_GET_SIZE(fast);
1357 if (n != 2) {
1358 PyErr_Format(PyExc_ValueError,
Neal Norwitzd3881b02006-05-30 04:25:05 +00001359 "dictionary update sequence element #%zd "
Martin v. Löwis2c95cc62006-02-16 06:54:25 +00001360 "has length %zd; 2 is required",
Martin v. Löwise0e89f72006-02-16 06:59:22 +00001361 i, n);
Tim Peters1fc240e2001-10-26 05:06:50 +00001362 goto Fail;
1363 }
1364
1365 /* Update/merge with this (key, value) pair. */
1366 key = PySequence_Fast_GET_ITEM(fast, 0);
1367 value = PySequence_Fast_GET_ITEM(fast, 1);
1368 if (override || PyDict_GetItem(d, key) == NULL) {
1369 int status = PyDict_SetItem(d, key, value);
1370 if (status < 0)
1371 goto Fail;
1372 }
1373 Py_DECREF(fast);
1374 Py_DECREF(item);
1375 }
1376
1377 i = 0;
1378 goto Return;
1379Fail:
1380 Py_XDECREF(item);
1381 Py_XDECREF(fast);
1382 i = -1;
1383Return:
1384 Py_DECREF(it);
Neal Norwitzd3881b02006-05-30 04:25:05 +00001385 return Py_SAFE_DOWNCAST(i, Py_ssize_t, int);
Tim Peters1fc240e2001-10-26 05:06:50 +00001386}
1387
Tim Peters6d6c1a32001-08-02 04:15:00 +00001388int
1389PyDict_Update(PyObject *a, PyObject *b)
1390{
Guido van Rossum05ac6de2001-08-10 20:28:28 +00001391 return PyDict_Merge(a, b, 1);
1392}
1393
1394int
1395PyDict_Merge(PyObject *a, PyObject *b, int override)
1396{
Tim Peters6d6c1a32001-08-02 04:15:00 +00001397 register PyDictObject *mp, *other;
Tim Peters9b10f7e2006-05-30 04:16:25 +00001398 register Py_ssize_t i;
Brett Cannon77ae87c2007-10-10 00:07:50 +00001399 PyDictEntry *entry;
Tim Peters6d6c1a32001-08-02 04:15:00 +00001400
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001401 /* We accept for the argument either a concrete dictionary object,
1402 * or an abstract "mapping" object. For the former, we can do
1403 * things quite efficiently. For the latter, we only require that
1404 * PyMapping_Keys() and PyObject_GetItem() be supported.
1405 */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001406 if (a == NULL || !PyDict_Check(a) || b == NULL) {
1407 PyErr_BadInternalCall();
1408 return -1;
1409 }
Brett Cannon77ae87c2007-10-10 00:07:50 +00001410 mp = (PyDictObject*)a;
Raymond Hettinger3dbd4c52008-01-25 19:24:46 +00001411 if (PyDict_Check(b)) {
Brett Cannon77ae87c2007-10-10 00:07:50 +00001412 other = (PyDictObject*)b;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001413 if (other == mp || other->ma_used == 0)
1414 /* a.update(a) or a.update({}); nothing to do */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001415 return 0;
Raymond Hettinger186e7392005-05-14 18:08:25 +00001416 if (mp->ma_used == 0)
1417 /* Since the target dict is empty, PyDict_GetItem()
1418 * always returns NULL. Setting override to 1
1419 * skips the unnecessary test.
1420 */
1421 override = 1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001422 /* Do one big resize at the start, rather than
1423 * incrementally resizing as we insert new items. Expect
1424 * that there will be no (or few) overlapping keys.
1425 */
1426 if ((mp->ma_fill + other->ma_used)*3 >= (mp->ma_mask+1)*2) {
Raymond Hettingerc8d22902003-05-07 00:49:40 +00001427 if (dictresize(mp, (mp->ma_used + other->ma_used)*2) != 0)
Tim Peters6d6c1a32001-08-02 04:15:00 +00001428 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001429 }
1430 for (i = 0; i <= other->ma_mask; i++) {
1431 entry = &other->ma_table[i];
Guido van Rossum05ac6de2001-08-10 20:28:28 +00001432 if (entry->me_value != NULL &&
1433 (override ||
1434 PyDict_GetItem(a, entry->me_key) == NULL)) {
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001435 Py_INCREF(entry->me_key);
1436 Py_INCREF(entry->me_value);
Armin Rigo35f6d362006-06-01 13:19:12 +00001437 if (insertdict(mp, entry->me_key,
1438 (long)entry->me_hash,
1439 entry->me_value) != 0)
1440 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001441 }
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001442 }
1443 }
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001444 else {
1445 /* Do it the generic, slower way */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001446 PyObject *keys = PyMapping_Keys(b);
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001447 PyObject *iter;
1448 PyObject *key, *value;
1449 int status;
1450
1451 if (keys == NULL)
1452 /* Docstring says this is equivalent to E.keys() so
1453 * if E doesn't have a .keys() method we want
1454 * AttributeError to percolate up. Might as well
1455 * do the same for any other error.
1456 */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001457 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001458
1459 iter = PyObject_GetIter(keys);
1460 Py_DECREF(keys);
1461 if (iter == NULL)
Tim Peters6d6c1a32001-08-02 04:15:00 +00001462 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001463
1464 for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) {
Guido van Rossum05ac6de2001-08-10 20:28:28 +00001465 if (!override && PyDict_GetItem(a, key) != NULL) {
1466 Py_DECREF(key);
1467 continue;
1468 }
Tim Peters6d6c1a32001-08-02 04:15:00 +00001469 value = PyObject_GetItem(b, key);
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001470 if (value == NULL) {
1471 Py_DECREF(iter);
1472 Py_DECREF(key);
Tim Peters6d6c1a32001-08-02 04:15:00 +00001473 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001474 }
Guido van Rossum05ac6de2001-08-10 20:28:28 +00001475 status = PyDict_SetItem(a, key, value);
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001476 Py_DECREF(key);
1477 Py_DECREF(value);
1478 if (status < 0) {
1479 Py_DECREF(iter);
Tim Peters6d6c1a32001-08-02 04:15:00 +00001480 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001481 }
1482 }
1483 Py_DECREF(iter);
1484 if (PyErr_Occurred())
1485 /* Iterator completed, via error */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001486 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001487 }
Tim Peters6d6c1a32001-08-02 04:15:00 +00001488 return 0;
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001489}
1490
1491static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00001492dict_copy(register PyDictObject *mp)
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001493{
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001494 return PyDict_Copy((PyObject*)mp);
1495}
1496
1497PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001498PyDict_Copy(PyObject *o)
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001499{
Raymond Hettingerebedb2f2004-03-08 04:19:01 +00001500 PyObject *copy;
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001501
1502 if (o == NULL || !PyDict_Check(o)) {
1503 PyErr_BadInternalCall();
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001504 return NULL;
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001505 }
Raymond Hettingerebedb2f2004-03-08 04:19:01 +00001506 copy = PyDict_New();
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001507 if (copy == NULL)
1508 return NULL;
Raymond Hettingerebedb2f2004-03-08 04:19:01 +00001509 if (PyDict_Merge(copy, o, 1) == 0)
1510 return copy;
1511 Py_DECREF(copy);
Raymond Hettinger1356f782005-04-15 15:58:42 +00001512 return NULL;
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001513}
1514
Martin v. Löwis18e16552006-02-15 17:27:45 +00001515Py_ssize_t
Tim Peters1f5871e2000-07-04 17:44:48 +00001516PyDict_Size(PyObject *mp)
Guido van Rossum4199fac1993-11-05 10:18:44 +00001517{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001518 if (mp == NULL || !PyDict_Check(mp)) {
1519 PyErr_BadInternalCall();
Jeremy Hylton7083bb72004-02-17 20:10:11 +00001520 return -1;
Guido van Rossum4199fac1993-11-05 10:18:44 +00001521 }
Brett Cannon77ae87c2007-10-10 00:07:50 +00001522 return ((PyDictObject *)mp)->ma_used;
Guido van Rossum4199fac1993-11-05 10:18:44 +00001523}
1524
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001525PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001526PyDict_Keys(PyObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001527{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001528 if (mp == NULL || !PyDict_Check(mp)) {
1529 PyErr_BadInternalCall();
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001530 return NULL;
1531 }
Brett Cannon77ae87c2007-10-10 00:07:50 +00001532 return dict_keys((PyDictObject *)mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001533}
1534
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001535PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001536PyDict_Values(PyObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001537{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001538 if (mp == NULL || !PyDict_Check(mp)) {
1539 PyErr_BadInternalCall();
Guido van Rossum25831651993-05-19 14:50:45 +00001540 return NULL;
1541 }
Brett Cannon77ae87c2007-10-10 00:07:50 +00001542 return dict_values((PyDictObject *)mp);
Guido van Rossum25831651993-05-19 14:50:45 +00001543}
1544
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001545PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001546PyDict_Items(PyObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001547{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001548 if (mp == NULL || !PyDict_Check(mp)) {
1549 PyErr_BadInternalCall();
Guido van Rossum25831651993-05-19 14:50:45 +00001550 return NULL;
1551 }
Brett Cannon77ae87c2007-10-10 00:07:50 +00001552 return dict_items((PyDictObject *)mp);
Guido van Rossum25831651993-05-19 14:50:45 +00001553}
1554
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001555/* Subroutine which returns the smallest key in a for which b's value
1556 is different or absent. The value is returned too, through the
Tim Peters95bf9392001-05-10 08:32:44 +00001557 pval argument. Both are NULL if no key in a is found for which b's status
1558 differs. The refcounts on (and only on) non-NULL *pval and function return
1559 values must be decremented by the caller (characterize() increments them
1560 to ensure that mutating comparison and PyDict_GetItem calls can't delete
1561 them before the caller is done looking at them). */
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001562
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001563static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00001564characterize(PyDictObject *a, PyDictObject *b, PyObject **pval)
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001565{
Tim Peters95bf9392001-05-10 08:32:44 +00001566 PyObject *akey = NULL; /* smallest key in a s.t. a[akey] != b[akey] */
1567 PyObject *aval = NULL; /* a[akey] */
Tim Peters9b10f7e2006-05-30 04:16:25 +00001568 Py_ssize_t i;
1569 int cmp;
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001570
Tim Petersafb6ae82001-06-04 21:00:21 +00001571 for (i = 0; i <= a->ma_mask; i++) {
Tim Peters95bf9392001-05-10 08:32:44 +00001572 PyObject *thiskey, *thisaval, *thisbval;
1573 if (a->ma_table[i].me_value == NULL)
1574 continue;
1575 thiskey = a->ma_table[i].me_key;
1576 Py_INCREF(thiskey); /* keep alive across compares */
1577 if (akey != NULL) {
1578 cmp = PyObject_RichCompareBool(akey, thiskey, Py_LT);
1579 if (cmp < 0) {
1580 Py_DECREF(thiskey);
1581 goto Fail;
1582 }
1583 if (cmp > 0 ||
Tim Petersafb6ae82001-06-04 21:00:21 +00001584 i > a->ma_mask ||
Tim Peters95bf9392001-05-10 08:32:44 +00001585 a->ma_table[i].me_value == NULL)
1586 {
1587 /* Not the *smallest* a key; or maybe it is
1588 * but the compare shrunk the dict so we can't
1589 * find its associated value anymore; or
1590 * maybe it is but the compare deleted the
1591 * a[thiskey] entry.
Neal Norwitzd3881b02006-05-30 04:25:05 +00001592 */
Tim Peters95bf9392001-05-10 08:32:44 +00001593 Py_DECREF(thiskey);
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001594 continue;
Guido van Rossumb9324202001-01-18 00:39:02 +00001595 }
Tim Peters95bf9392001-05-10 08:32:44 +00001596 }
1597
1598 /* Compare a[thiskey] to b[thiskey]; cmp <- true iff equal. */
1599 thisaval = a->ma_table[i].me_value;
1600 assert(thisaval);
1601 Py_INCREF(thisaval); /* keep alive */
1602 thisbval = PyDict_GetItem((PyObject *)b, thiskey);
1603 if (thisbval == NULL)
1604 cmp = 0;
1605 else {
1606 /* both dicts have thiskey: same values? */
1607 cmp = PyObject_RichCompareBool(
1608 thisaval, thisbval, Py_EQ);
1609 if (cmp < 0) {
1610 Py_DECREF(thiskey);
1611 Py_DECREF(thisaval);
1612 goto Fail;
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001613 }
1614 }
Tim Peters95bf9392001-05-10 08:32:44 +00001615 if (cmp == 0) {
1616 /* New winner. */
1617 Py_XDECREF(akey);
1618 Py_XDECREF(aval);
1619 akey = thiskey;
1620 aval = thisaval;
1621 }
1622 else {
1623 Py_DECREF(thiskey);
1624 Py_DECREF(thisaval);
1625 }
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001626 }
Tim Peters95bf9392001-05-10 08:32:44 +00001627 *pval = aval;
1628 return akey;
1629
1630Fail:
1631 Py_XDECREF(akey);
1632 Py_XDECREF(aval);
1633 *pval = NULL;
1634 return NULL;
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001635}
1636
1637static int
Brett Cannon77ae87c2007-10-10 00:07:50 +00001638dict_compare(PyDictObject *a, PyDictObject *b)
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001639{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001640 PyObject *adiff, *bdiff, *aval, *bval;
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001641 int res;
1642
1643 /* Compare lengths first */
1644 if (a->ma_used < b->ma_used)
1645 return -1; /* a is shorter */
1646 else if (a->ma_used > b->ma_used)
1647 return 1; /* b is shorter */
Tim Peters95bf9392001-05-10 08:32:44 +00001648
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001649 /* Same length -- check all keys */
Tim Peters95bf9392001-05-10 08:32:44 +00001650 bdiff = bval = NULL;
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001651 adiff = characterize(a, b, &aval);
Tim Peters95bf9392001-05-10 08:32:44 +00001652 if (adiff == NULL) {
1653 assert(!aval);
Tim Peters3918fb22001-05-10 18:58:31 +00001654 /* Either an error, or a is a subset with the same length so
Tim Peters95bf9392001-05-10 08:32:44 +00001655 * must be equal.
1656 */
1657 res = PyErr_Occurred() ? -1 : 0;
1658 goto Finished;
1659 }
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001660 bdiff = characterize(b, a, &bval);
Tim Peters95bf9392001-05-10 08:32:44 +00001661 if (bdiff == NULL && PyErr_Occurred()) {
1662 assert(!bval);
1663 res = -1;
1664 goto Finished;
1665 }
1666 res = 0;
1667 if (bdiff) {
1668 /* bdiff == NULL "should be" impossible now, but perhaps
1669 * the last comparison done by the characterize() on a had
1670 * the side effect of making the dicts equal!
1671 */
1672 res = PyObject_Compare(adiff, bdiff);
1673 }
1674 if (res == 0 && bval != NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001675 res = PyObject_Compare(aval, bval);
Tim Peters95bf9392001-05-10 08:32:44 +00001676
1677Finished:
1678 Py_XDECREF(adiff);
1679 Py_XDECREF(bdiff);
1680 Py_XDECREF(aval);
1681 Py_XDECREF(bval);
Guido van Rossuma0a69b81996-12-05 21:55:55 +00001682 return res;
1683}
1684
Tim Peterse63415e2001-05-08 04:38:29 +00001685/* Return 1 if dicts equal, 0 if not, -1 if error.
1686 * Gets out as soon as any difference is detected.
1687 * Uses only Py_EQ comparison.
1688 */
1689static int
Brett Cannon77ae87c2007-10-10 00:07:50 +00001690dict_equal(PyDictObject *a, PyDictObject *b)
Tim Peterse63415e2001-05-08 04:38:29 +00001691{
Tim Peters9b10f7e2006-05-30 04:16:25 +00001692 Py_ssize_t i;
Tim Peterse63415e2001-05-08 04:38:29 +00001693
1694 if (a->ma_used != b->ma_used)
1695 /* can't be equal if # of entries differ */
1696 return 0;
Tim Peterseb28ef22001-06-02 05:27:19 +00001697
Tim Peterse63415e2001-05-08 04:38:29 +00001698 /* Same # of entries -- check all of 'em. Exit early on any diff. */
Tim Petersafb6ae82001-06-04 21:00:21 +00001699 for (i = 0; i <= a->ma_mask; i++) {
Tim Peterse63415e2001-05-08 04:38:29 +00001700 PyObject *aval = a->ma_table[i].me_value;
1701 if (aval != NULL) {
1702 int cmp;
1703 PyObject *bval;
1704 PyObject *key = a->ma_table[i].me_key;
1705 /* temporarily bump aval's refcount to ensure it stays
1706 alive until we're done with it */
1707 Py_INCREF(aval);
Neal Norwitza22975f2006-09-05 02:24:03 +00001708 /* ditto for key */
1709 Py_INCREF(key);
Tim Peterse63415e2001-05-08 04:38:29 +00001710 bval = PyDict_GetItem((PyObject *)b, key);
Neal Norwitza22975f2006-09-05 02:24:03 +00001711 Py_DECREF(key);
Tim Peterse63415e2001-05-08 04:38:29 +00001712 if (bval == NULL) {
1713 Py_DECREF(aval);
1714 return 0;
1715 }
1716 cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
1717 Py_DECREF(aval);
1718 if (cmp <= 0) /* error or not equal */
1719 return cmp;
1720 }
1721 }
1722 return 1;
1723 }
1724
1725static PyObject *
1726dict_richcompare(PyObject *v, PyObject *w, int op)
1727{
1728 int cmp;
1729 PyObject *res;
1730
1731 if (!PyDict_Check(v) || !PyDict_Check(w)) {
1732 res = Py_NotImplemented;
1733 }
1734 else if (op == Py_EQ || op == Py_NE) {
Brett Cannon77ae87c2007-10-10 00:07:50 +00001735 cmp = dict_equal((PyDictObject *)v, (PyDictObject *)w);
Tim Peterse63415e2001-05-08 04:38:29 +00001736 if (cmp < 0)
1737 return NULL;
1738 res = (cmp == (op == Py_EQ)) ? Py_True : Py_False;
1739 }
Tim Peters4fa58bf2001-05-10 21:45:19 +00001740 else
1741 res = Py_NotImplemented;
Tim Peterse63415e2001-05-08 04:38:29 +00001742 Py_INCREF(res);
1743 return res;
1744 }
1745
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001746static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00001747dict_contains(register PyDictObject *mp, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001748{
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001749 long hash;
Brett Cannon77ae87c2007-10-10 00:07:50 +00001750 PyDictEntry *ep;
Tim Petersd770ebd2006-06-01 15:50:44 +00001751
Tim Peters0ab085c2001-09-14 00:25:33 +00001752 if (!PyString_CheckExact(key) ||
Tim Peters1f7df352002-03-29 03:29:08 +00001753 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001754 hash = PyObject_Hash(key);
Guido van Rossumca756f21997-01-23 19:39:29 +00001755 if (hash == -1)
1756 return NULL;
1757 }
Armin Rigo35f6d362006-06-01 13:19:12 +00001758 ep = (mp->ma_lookup)(mp, key, hash);
1759 if (ep == NULL)
1760 return NULL;
Tim Petersd770ebd2006-06-01 15:50:44 +00001761 return PyBool_FromLong(ep->me_value != NULL);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001762}
1763
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001764static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00001765dict_has_key(register PyDictObject *mp, PyObject *key)
Neal Norwitz8b2bfbc2007-05-23 06:35:32 +00001766{
1767 if (Py_Py3kWarningFlag &&
1768 PyErr_Warn(PyExc_DeprecationWarning,
1769 "dict.has_key() not supported in 3.x") < 0)
1770 return NULL;
1771 return dict_contains(mp, key);
1772}
1773
1774static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00001775dict_get(register PyDictObject *mp, PyObject *args)
Barry Warsawc38c5da1997-10-06 17:49:20 +00001776{
1777 PyObject *key;
Barry Warsaw320ac331997-10-20 17:26:25 +00001778 PyObject *failobj = Py_None;
Barry Warsawc38c5da1997-10-06 17:49:20 +00001779 PyObject *val = NULL;
1780 long hash;
Brett Cannon77ae87c2007-10-10 00:07:50 +00001781 PyDictEntry *ep;
Barry Warsawc38c5da1997-10-06 17:49:20 +00001782
Raymond Hettingerea3fdf42002-12-29 16:33:45 +00001783 if (!PyArg_UnpackTuple(args, "get", 1, 2, &key, &failobj))
Barry Warsawc38c5da1997-10-06 17:49:20 +00001784 return NULL;
1785
Tim Peters0ab085c2001-09-14 00:25:33 +00001786 if (!PyString_CheckExact(key) ||
Tim Peters1f7df352002-03-29 03:29:08 +00001787 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
Barry Warsawc38c5da1997-10-06 17:49:20 +00001788 hash = PyObject_Hash(key);
1789 if (hash == -1)
1790 return NULL;
1791 }
Armin Rigo35f6d362006-06-01 13:19:12 +00001792 ep = (mp->ma_lookup)(mp, key, hash);
1793 if (ep == NULL)
1794 return NULL;
1795 val = ep->me_value;
Barry Warsawc38c5da1997-10-06 17:49:20 +00001796 if (val == NULL)
1797 val = failobj;
1798 Py_INCREF(val);
1799 return val;
1800}
1801
1802
1803static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00001804dict_setdefault(register PyDictObject *mp, PyObject *args)
Guido van Rossum164452c2000-08-08 16:12:54 +00001805{
1806 PyObject *key;
1807 PyObject *failobj = Py_None;
1808 PyObject *val = NULL;
1809 long hash;
Brett Cannon77ae87c2007-10-10 00:07:50 +00001810 PyDictEntry *ep;
Guido van Rossum164452c2000-08-08 16:12:54 +00001811
Raymond Hettingerea3fdf42002-12-29 16:33:45 +00001812 if (!PyArg_UnpackTuple(args, "setdefault", 1, 2, &key, &failobj))
Guido van Rossum164452c2000-08-08 16:12:54 +00001813 return NULL;
Guido van Rossum164452c2000-08-08 16:12:54 +00001814
Tim Peters0ab085c2001-09-14 00:25:33 +00001815 if (!PyString_CheckExact(key) ||
Tim Peters1f7df352002-03-29 03:29:08 +00001816 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
Guido van Rossum164452c2000-08-08 16:12:54 +00001817 hash = PyObject_Hash(key);
1818 if (hash == -1)
1819 return NULL;
1820 }
Armin Rigo35f6d362006-06-01 13:19:12 +00001821 ep = (mp->ma_lookup)(mp, key, hash);
1822 if (ep == NULL)
1823 return NULL;
1824 val = ep->me_value;
Guido van Rossum164452c2000-08-08 16:12:54 +00001825 if (val == NULL) {
1826 val = failobj;
1827 if (PyDict_SetItem((PyObject*)mp, key, failobj))
1828 val = NULL;
1829 }
1830 Py_XINCREF(val);
1831 return val;
1832}
1833
1834
1835static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00001836dict_clear(register PyDictObject *mp)
Guido van Rossumfb8f1ca1997-03-21 21:55:12 +00001837{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001838 PyDict_Clear((PyObject *)mp);
Raymond Hettinger7892b1c2004-04-12 18:10:01 +00001839 Py_RETURN_NONE;
Guido van Rossumfb8f1ca1997-03-21 21:55:12 +00001840}
1841
Guido van Rossumba6ab842000-12-12 22:02:18 +00001842static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00001843dict_pop(PyDictObject *mp, PyObject *args)
Guido van Rossume027d982002-04-12 15:11:59 +00001844{
1845 long hash;
Brett Cannon77ae87c2007-10-10 00:07:50 +00001846 PyDictEntry *ep;
Guido van Rossume027d982002-04-12 15:11:59 +00001847 PyObject *old_value, *old_key;
Raymond Hettingera3e1e4c2003-03-06 23:54:28 +00001848 PyObject *key, *deflt = NULL;
Guido van Rossume027d982002-04-12 15:11:59 +00001849
Raymond Hettingera3e1e4c2003-03-06 23:54:28 +00001850 if(!PyArg_UnpackTuple(args, "pop", 1, 2, &key, &deflt))
1851 return NULL;
Guido van Rossume027d982002-04-12 15:11:59 +00001852 if (mp->ma_used == 0) {
Raymond Hettingera3e1e4c2003-03-06 23:54:28 +00001853 if (deflt) {
1854 Py_INCREF(deflt);
1855 return deflt;
1856 }
Guido van Rossume027d982002-04-12 15:11:59 +00001857 PyErr_SetString(PyExc_KeyError,
1858 "pop(): dictionary is empty");
1859 return NULL;
1860 }
1861 if (!PyString_CheckExact(key) ||
1862 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
1863 hash = PyObject_Hash(key);
1864 if (hash == -1)
1865 return NULL;
1866 }
1867 ep = (mp->ma_lookup)(mp, key, hash);
Armin Rigo35f6d362006-06-01 13:19:12 +00001868 if (ep == NULL)
1869 return NULL;
Guido van Rossume027d982002-04-12 15:11:59 +00001870 if (ep->me_value == NULL) {
Raymond Hettingera3e1e4c2003-03-06 23:54:28 +00001871 if (deflt) {
1872 Py_INCREF(deflt);
1873 return deflt;
1874 }
Georg Brandlb9f4ad32006-10-29 18:31:42 +00001875 set_key_error(key);
Guido van Rossume027d982002-04-12 15:11:59 +00001876 return NULL;
1877 }
1878 old_key = ep->me_key;
1879 Py_INCREF(dummy);
1880 ep->me_key = dummy;
1881 old_value = ep->me_value;
1882 ep->me_value = NULL;
1883 mp->ma_used--;
1884 Py_DECREF(old_key);
1885 return old_value;
1886}
1887
1888static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00001889dict_popitem(PyDictObject *mp)
Guido van Rossumba6ab842000-12-12 22:02:18 +00001890{
Tim Peters9b10f7e2006-05-30 04:16:25 +00001891 Py_ssize_t i = 0;
Brett Cannon77ae87c2007-10-10 00:07:50 +00001892 PyDictEntry *ep;
Guido van Rossumba6ab842000-12-12 22:02:18 +00001893 PyObject *res;
1894
Tim Petersf4b33f62001-06-02 05:42:29 +00001895 /* Allocate the result tuple before checking the size. Believe it
1896 * or not, this allocation could trigger a garbage collection which
1897 * could empty the dict, so if we checked the size first and that
1898 * happened, the result would be an infinite loop (searching for an
1899 * entry that no longer exists). Note that the usual popitem()
1900 * idiom is "while d: k, v = d.popitem()". so needing to throw the
Tim Peters9b10f7e2006-05-30 04:16:25 +00001901 * tuple away if the dict *is* empty isn't a significant
Tim Petersf4b33f62001-06-02 05:42:29 +00001902 * inefficiency -- possible, but unlikely in practice.
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001903 */
1904 res = PyTuple_New(2);
1905 if (res == NULL)
1906 return NULL;
Guido van Rossume04eaec2001-04-16 00:02:32 +00001907 if (mp->ma_used == 0) {
1908 Py_DECREF(res);
1909 PyErr_SetString(PyExc_KeyError,
1910 "popitem(): dictionary is empty");
1911 return NULL;
1912 }
Guido van Rossumba6ab842000-12-12 22:02:18 +00001913 /* Set ep to "the first" dict entry with a value. We abuse the hash
1914 * field of slot 0 to hold a search finger:
1915 * If slot 0 has a value, use slot 0.
1916 * Else slot 0 is being used to hold a search finger,
Neal Norwitzd3881b02006-05-30 04:25:05 +00001917 * and we use its hash value as the first index to look.
Guido van Rossumba6ab842000-12-12 22:02:18 +00001918 */
1919 ep = &mp->ma_table[0];
1920 if (ep->me_value == NULL) {
Tim Peters9b10f7e2006-05-30 04:16:25 +00001921 i = ep->me_hash;
Tim Petersdea48ec2001-05-22 20:40:22 +00001922 /* The hash field may be a real hash value, or it may be a
1923 * legit search finger, or it may be a once-legit search
1924 * finger that's out of bounds now because it wrapped around
1925 * or the table shrunk -- simply make sure it's in bounds now.
Guido van Rossumba6ab842000-12-12 22:02:18 +00001926 */
Tim Petersafb6ae82001-06-04 21:00:21 +00001927 if (i > mp->ma_mask || i < 1)
Guido van Rossumba6ab842000-12-12 22:02:18 +00001928 i = 1; /* skip slot 0 */
1929 while ((ep = &mp->ma_table[i])->me_value == NULL) {
1930 i++;
Tim Petersafb6ae82001-06-04 21:00:21 +00001931 if (i > mp->ma_mask)
Guido van Rossumba6ab842000-12-12 22:02:18 +00001932 i = 1;
1933 }
1934 }
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001935 PyTuple_SET_ITEM(res, 0, ep->me_key);
1936 PyTuple_SET_ITEM(res, 1, ep->me_value);
1937 Py_INCREF(dummy);
1938 ep->me_key = dummy;
1939 ep->me_value = NULL;
1940 mp->ma_used--;
1941 assert(mp->ma_table[0].me_value == NULL);
1942 mp->ma_table[0].me_hash = i + 1; /* next place to start */
Guido van Rossumba6ab842000-12-12 22:02:18 +00001943 return res;
1944}
1945
Jeremy Hylton8caad492000-06-23 14:18:11 +00001946static int
1947dict_traverse(PyObject *op, visitproc visit, void *arg)
1948{
Martin v. Löwis18e16552006-02-15 17:27:45 +00001949 Py_ssize_t i = 0;
Jeremy Hylton8caad492000-06-23 14:18:11 +00001950 PyObject *pk;
1951 PyObject *pv;
1952
1953 while (PyDict_Next(op, &i, &pk, &pv)) {
Thomas Woutersc6e55062006-04-15 21:47:09 +00001954 Py_VISIT(pk);
1955 Py_VISIT(pv);
Jeremy Hylton8caad492000-06-23 14:18:11 +00001956 }
1957 return 0;
1958}
1959
1960static int
1961dict_tp_clear(PyObject *op)
1962{
1963 PyDict_Clear(op);
1964 return 0;
1965}
1966
Tim Petersf7f88b12000-12-13 23:18:45 +00001967
Raymond Hettinger019a1482004-03-18 02:41:19 +00001968extern PyTypeObject PyDictIterKey_Type; /* Forward */
1969extern PyTypeObject PyDictIterValue_Type; /* Forward */
1970extern PyTypeObject PyDictIterItem_Type; /* Forward */
Brett Cannon77ae87c2007-10-10 00:07:50 +00001971static PyObject *dictiter_new(PyDictObject *, PyTypeObject *);
Guido van Rossum09e563a2001-05-01 12:10:21 +00001972
1973static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00001974dict_iterkeys(PyDictObject *dict)
Guido van Rossum09e563a2001-05-01 12:10:21 +00001975{
Raymond Hettinger019a1482004-03-18 02:41:19 +00001976 return dictiter_new(dict, &PyDictIterKey_Type);
Guido van Rossum09e563a2001-05-01 12:10:21 +00001977}
1978
1979static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00001980dict_itervalues(PyDictObject *dict)
Guido van Rossum09e563a2001-05-01 12:10:21 +00001981{
Raymond Hettinger019a1482004-03-18 02:41:19 +00001982 return dictiter_new(dict, &PyDictIterValue_Type);
Guido van Rossum09e563a2001-05-01 12:10:21 +00001983}
1984
1985static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00001986dict_iteritems(PyDictObject *dict)
Guido van Rossum09e563a2001-05-01 12:10:21 +00001987{
Raymond Hettinger019a1482004-03-18 02:41:19 +00001988 return dictiter_new(dict, &PyDictIterItem_Type);
Guido van Rossum09e563a2001-05-01 12:10:21 +00001989}
1990
1991
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001992PyDoc_STRVAR(has_key__doc__,
Raymond Hettinger574aa322003-09-01 22:12:08 +00001993"D.has_key(k) -> True if D has a key k, else False");
Tim Petersf7f88b12000-12-13 23:18:45 +00001994
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001995PyDoc_STRVAR(contains__doc__,
1996"D.__contains__(k) -> True if D has a key k, else False");
1997
1998PyDoc_STRVAR(getitem__doc__, "x.__getitem__(y) <==> x[y]");
1999
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002000PyDoc_STRVAR(get__doc__,
Guido van Rossumefae8862002-09-04 11:29:45 +00002001"D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.");
Tim Petersf7f88b12000-12-13 23:18:45 +00002002
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002003PyDoc_STRVAR(setdefault_doc__,
Guido van Rossumefae8862002-09-04 11:29:45 +00002004"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 +00002005
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002006PyDoc_STRVAR(pop__doc__,
Raymond Hettingera3e1e4c2003-03-06 23:54:28 +00002007"D.pop(k[,d]) -> v, remove specified key and return the corresponding value\n\
2008If key is not found, d is returned if given, otherwise KeyError is raised");
Guido van Rossume027d982002-04-12 15:11:59 +00002009
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002010PyDoc_STRVAR(popitem__doc__,
Tim Petersf7f88b12000-12-13 23:18:45 +00002011"D.popitem() -> (k, v), remove and return some (key, value) pair as a\n\
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +000020122-tuple; but raise KeyError if D is empty");
Tim Petersf7f88b12000-12-13 23:18:45 +00002013
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002014PyDoc_STRVAR(keys__doc__,
2015"D.keys() -> list of D's keys");
Tim Petersf7f88b12000-12-13 23:18:45 +00002016
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002017PyDoc_STRVAR(items__doc__,
2018"D.items() -> list of D's (key, value) pairs, as 2-tuples");
Tim Petersf7f88b12000-12-13 23:18:45 +00002019
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002020PyDoc_STRVAR(values__doc__,
2021"D.values() -> list of D's values");
Tim Petersf7f88b12000-12-13 23:18:45 +00002022
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002023PyDoc_STRVAR(update__doc__,
Walter Dörwaldd70ad8a2004-05-28 20:59:21 +00002024"D.update(E, **F) -> None. Update D from E and F: for k in E: D[k] = E[k]\n\
2025(if E has keys else: for (k, v) in E: D[k] = v) then: for k in F: D[k] = F[k]");
Tim Petersf7f88b12000-12-13 23:18:45 +00002026
Raymond Hettingere33d3df2002-11-27 07:29:33 +00002027PyDoc_STRVAR(fromkeys__doc__,
2028"dict.fromkeys(S[,v]) -> New dict with keys from S and values equal to v.\n\
2029v defaults to None.");
2030
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002031PyDoc_STRVAR(clear__doc__,
2032"D.clear() -> None. Remove all items from D.");
Tim Petersf7f88b12000-12-13 23:18:45 +00002033
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002034PyDoc_STRVAR(copy__doc__,
2035"D.copy() -> a shallow copy of D");
Tim Petersf7f88b12000-12-13 23:18:45 +00002036
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002037PyDoc_STRVAR(iterkeys__doc__,
2038"D.iterkeys() -> an iterator over the keys of D");
Guido van Rossum09e563a2001-05-01 12:10:21 +00002039
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002040PyDoc_STRVAR(itervalues__doc__,
2041"D.itervalues() -> an iterator over the values of D");
Guido van Rossum09e563a2001-05-01 12:10:21 +00002042
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002043PyDoc_STRVAR(iteritems__doc__,
2044"D.iteritems() -> an iterator over the (key, value) items of D");
Guido van Rossum09e563a2001-05-01 12:10:21 +00002045
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002046static PyMethodDef mapp_methods[] = {
Neal Norwitzc7926292007-05-23 06:57:35 +00002047 {"__contains__",(PyCFunction)dict_contains, METH_O | METH_COEXIST,
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00002048 contains__doc__},
Raymond Hettinger0c669672003-12-13 13:31:55 +00002049 {"__getitem__", (PyCFunction)dict_subscript, METH_O | METH_COEXIST,
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00002050 getitem__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002051 {"has_key", (PyCFunction)dict_has_key, METH_O,
Tim Petersf7f88b12000-12-13 23:18:45 +00002052 has_key__doc__},
2053 {"get", (PyCFunction)dict_get, METH_VARARGS,
2054 get__doc__},
2055 {"setdefault", (PyCFunction)dict_setdefault, METH_VARARGS,
2056 setdefault_doc__},
Raymond Hettingera3e1e4c2003-03-06 23:54:28 +00002057 {"pop", (PyCFunction)dict_pop, METH_VARARGS,
Just van Rossuma797d812002-11-23 09:45:04 +00002058 pop__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002059 {"popitem", (PyCFunction)dict_popitem, METH_NOARGS,
Tim Petersf7f88b12000-12-13 23:18:45 +00002060 popitem__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002061 {"keys", (PyCFunction)dict_keys, METH_NOARGS,
Tim Petersf7f88b12000-12-13 23:18:45 +00002062 keys__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002063 {"items", (PyCFunction)dict_items, METH_NOARGS,
Tim Petersf7f88b12000-12-13 23:18:45 +00002064 items__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002065 {"values", (PyCFunction)dict_values, METH_NOARGS,
Tim Petersf7f88b12000-12-13 23:18:45 +00002066 values__doc__},
Raymond Hettinger31017ae2004-03-04 08:25:44 +00002067 {"update", (PyCFunction)dict_update, METH_VARARGS | METH_KEYWORDS,
Tim Petersf7f88b12000-12-13 23:18:45 +00002068 update__doc__},
Raymond Hettingere33d3df2002-11-27 07:29:33 +00002069 {"fromkeys", (PyCFunction)dict_fromkeys, METH_VARARGS | METH_CLASS,
2070 fromkeys__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002071 {"clear", (PyCFunction)dict_clear, METH_NOARGS,
Tim Petersf7f88b12000-12-13 23:18:45 +00002072 clear__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002073 {"copy", (PyCFunction)dict_copy, METH_NOARGS,
Tim Petersf7f88b12000-12-13 23:18:45 +00002074 copy__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002075 {"iterkeys", (PyCFunction)dict_iterkeys, METH_NOARGS,
Guido van Rossum09e563a2001-05-01 12:10:21 +00002076 iterkeys__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002077 {"itervalues", (PyCFunction)dict_itervalues, METH_NOARGS,
Guido van Rossum09e563a2001-05-01 12:10:21 +00002078 itervalues__doc__},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002079 {"iteritems", (PyCFunction)dict_iteritems, METH_NOARGS,
Guido van Rossum09e563a2001-05-01 12:10:21 +00002080 iteritems__doc__},
Tim Petersf7f88b12000-12-13 23:18:45 +00002081 {NULL, NULL} /* sentinel */
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002082};
2083
Tim Petersd770ebd2006-06-01 15:50:44 +00002084/* Return 1 if `key` is in dict `op`, 0 if not, and -1 on error. */
Raymond Hettingerbc0f2ab2003-11-25 21:12:14 +00002085int
2086PyDict_Contains(PyObject *op, PyObject *key)
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002087{
2088 long hash;
Brett Cannon77ae87c2007-10-10 00:07:50 +00002089 PyDictObject *mp = (PyDictObject *)op;
2090 PyDictEntry *ep;
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002091
Tim Peters0ab085c2001-09-14 00:25:33 +00002092 if (!PyString_CheckExact(key) ||
Tim Peters1f7df352002-03-29 03:29:08 +00002093 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002094 hash = PyObject_Hash(key);
2095 if (hash == -1)
2096 return -1;
2097 }
Armin Rigo35f6d362006-06-01 13:19:12 +00002098 ep = (mp->ma_lookup)(mp, key, hash);
Tim Petersd770ebd2006-06-01 15:50:44 +00002099 return ep == NULL ? -1 : (ep->me_value != NULL);
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002100}
2101
Raymond Hettingerd6fc72a2007-02-19 02:03:19 +00002102/* Internal version of PyDict_Contains used when the hash value is already known */
2103int
2104_PyDict_Contains(PyObject *op, PyObject *key, long hash)
2105{
Brett Cannon77ae87c2007-10-10 00:07:50 +00002106 PyDictObject *mp = (PyDictObject *)op;
2107 PyDictEntry *ep;
Raymond Hettingerd6fc72a2007-02-19 02:03:19 +00002108
2109 ep = (mp->ma_lookup)(mp, key, hash);
2110 return ep == NULL ? -1 : (ep->me_value != NULL);
2111}
2112
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002113/* Hack to implement "key in dict" */
2114static PySequenceMethods dict_as_sequence = {
Georg Brandl347b3002006-03-30 11:57:00 +00002115 0, /* sq_length */
2116 0, /* sq_concat */
2117 0, /* sq_repeat */
2118 0, /* sq_item */
2119 0, /* sq_slice */
2120 0, /* sq_ass_item */
2121 0, /* sq_ass_slice */
2122 PyDict_Contains, /* sq_contains */
2123 0, /* sq_inplace_concat */
2124 0, /* sq_inplace_repeat */
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002125};
2126
Guido van Rossum09e563a2001-05-01 12:10:21 +00002127static PyObject *
Tim Peters6d6c1a32001-08-02 04:15:00 +00002128dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2129{
2130 PyObject *self;
2131
2132 assert(type != NULL && type->tp_alloc != NULL);
2133 self = type->tp_alloc(type, 0);
2134 if (self != NULL) {
2135 PyDictObject *d = (PyDictObject *)self;
2136 /* It's guaranteed that tp->alloc zeroed out the struct. */
2137 assert(d->ma_table == NULL && d->ma_fill == 0 && d->ma_used == 0);
2138 INIT_NONZERO_DICT_SLOTS(d);
2139 d->ma_lookup = lookdict_string;
2140#ifdef SHOW_CONVERSION_COUNTS
2141 ++created;
2142#endif
2143 }
2144 return self;
2145}
2146
Tim Peters25786c02001-09-02 08:22:48 +00002147static int
2148dict_init(PyObject *self, PyObject *args, PyObject *kwds)
2149{
Raymond Hettinger31017ae2004-03-04 08:25:44 +00002150 return dict_update_common(self, args, kwds, "dict");
Tim Peters25786c02001-09-02 08:22:48 +00002151}
2152
Tim Peters6d6c1a32001-08-02 04:15:00 +00002153static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00002154dict_iter(PyDictObject *dict)
Guido van Rossum09e563a2001-05-01 12:10:21 +00002155{
Raymond Hettinger019a1482004-03-18 02:41:19 +00002156 return dictiter_new(dict, &PyDictIterKey_Type);
Guido van Rossum09e563a2001-05-01 12:10:21 +00002157}
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002158
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002159PyDoc_STRVAR(dictionary_doc,
Tim Petersa427a2b2001-10-29 22:25:45 +00002160"dict() -> new empty dictionary.\n"
2161"dict(mapping) -> new dictionary initialized from a mapping object's\n"
Tim Peters1fc240e2001-10-26 05:06:50 +00002162" (key, value) pairs.\n"
Tim Petersa427a2b2001-10-29 22:25:45 +00002163"dict(seq) -> new dictionary initialized as if via:\n"
Tim Peters4d859532001-10-27 18:27:48 +00002164" d = {}\n"
2165" for k, v in seq:\n"
Just van Rossuma797d812002-11-23 09:45:04 +00002166" d[k] = v\n"
2167"dict(**kwargs) -> new dictionary initialized with the name=value pairs\n"
2168" in the keyword argument list. For example: dict(one=1, two=2)");
Tim Peters25786c02001-09-02 08:22:48 +00002169
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002170PyTypeObject PyDict_Type = {
Martin v. Löwis68192102007-07-21 06:55:02 +00002171 PyVarObject_HEAD_INIT(&PyType_Type, 0)
Tim Petersa427a2b2001-10-29 22:25:45 +00002172 "dict",
Brett Cannon77ae87c2007-10-10 00:07:50 +00002173 sizeof(PyDictObject),
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002174 0,
Guido van Rossumb9324202001-01-18 00:39:02 +00002175 (destructor)dict_dealloc, /* tp_dealloc */
2176 (printfunc)dict_print, /* tp_print */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002177 0, /* tp_getattr */
Guido van Rossumb9324202001-01-18 00:39:02 +00002178 0, /* tp_setattr */
Tim Peters4fa58bf2001-05-10 21:45:19 +00002179 (cmpfunc)dict_compare, /* tp_compare */
Guido van Rossumb9324202001-01-18 00:39:02 +00002180 (reprfunc)dict_repr, /* tp_repr */
2181 0, /* tp_as_number */
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002182 &dict_as_sequence, /* tp_as_sequence */
Guido van Rossumb9324202001-01-18 00:39:02 +00002183 &dict_as_mapping, /* tp_as_mapping */
Guido van Rossum64c06e32007-11-22 00:55:51 +00002184 0, /* tp_hash */
Guido van Rossumb9324202001-01-18 00:39:02 +00002185 0, /* tp_call */
2186 0, /* tp_str */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002187 PyObject_GenericGetAttr, /* tp_getattro */
Guido van Rossumb9324202001-01-18 00:39:02 +00002188 0, /* tp_setattro */
2189 0, /* tp_as_buffer */
Neil Schemenauere83c00e2001-08-29 23:54:21 +00002190 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
Neal Norwitzee3a1b52007-02-25 19:44:48 +00002191 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_DICT_SUBCLASS, /* tp_flags */
Tim Peters25786c02001-09-02 08:22:48 +00002192 dictionary_doc, /* tp_doc */
Georg Brandl347b3002006-03-30 11:57:00 +00002193 dict_traverse, /* tp_traverse */
2194 dict_tp_clear, /* tp_clear */
Tim Peterse63415e2001-05-08 04:38:29 +00002195 dict_richcompare, /* tp_richcompare */
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002196 0, /* tp_weaklistoffset */
Guido van Rossum09e563a2001-05-01 12:10:21 +00002197 (getiterfunc)dict_iter, /* tp_iter */
Guido van Rossum213c7a62001-04-23 14:08:49 +00002198 0, /* tp_iternext */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002199 mapp_methods, /* tp_methods */
2200 0, /* tp_members */
2201 0, /* tp_getset */
2202 0, /* tp_base */
2203 0, /* tp_dict */
2204 0, /* tp_descr_get */
2205 0, /* tp_descr_set */
2206 0, /* tp_dictoffset */
Georg Brandl347b3002006-03-30 11:57:00 +00002207 dict_init, /* tp_init */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002208 PyType_GenericAlloc, /* tp_alloc */
2209 dict_new, /* tp_new */
Neil Schemenauer6189b892002-04-12 02:43:00 +00002210 PyObject_GC_Del, /* tp_free */
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002211};
2212
Guido van Rossum3cca2451997-05-16 14:23:33 +00002213/* For backward compatibility with old dictionary interface */
2214
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002215PyObject *
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +00002216PyDict_GetItemString(PyObject *v, const char *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002217{
Guido van Rossum3cca2451997-05-16 14:23:33 +00002218 PyObject *kv, *rv;
2219 kv = PyString_FromString(key);
2220 if (kv == NULL)
2221 return NULL;
Guido van Rossum3cca2451997-05-16 14:23:33 +00002222 rv = PyDict_GetItem(v, kv);
2223 Py_DECREF(kv);
2224 return rv;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002225}
2226
2227int
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +00002228PyDict_SetItemString(PyObject *v, const char *key, PyObject *item)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002229{
Guido van Rossum3cca2451997-05-16 14:23:33 +00002230 PyObject *kv;
2231 int err;
2232 kv = PyString_FromString(key);
2233 if (kv == NULL)
Guido van Rossum037b2201997-05-20 18:35:19 +00002234 return -1;
Guido van Rossum4f3bf1e1997-09-29 23:31:11 +00002235 PyString_InternInPlace(&kv); /* XXX Should we really? */
Guido van Rossum3cca2451997-05-16 14:23:33 +00002236 err = PyDict_SetItem(v, kv, item);
2237 Py_DECREF(kv);
2238 return err;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002239}
2240
2241int
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +00002242PyDict_DelItemString(PyObject *v, const char *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002243{
Guido van Rossum3cca2451997-05-16 14:23:33 +00002244 PyObject *kv;
2245 int err;
2246 kv = PyString_FromString(key);
2247 if (kv == NULL)
Guido van Rossum037b2201997-05-20 18:35:19 +00002248 return -1;
Guido van Rossum3cca2451997-05-16 14:23:33 +00002249 err = PyDict_DelItem(v, kv);
2250 Py_DECREF(kv);
2251 return err;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002252}
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002253
Raymond Hettinger019a1482004-03-18 02:41:19 +00002254/* Dictionary iterator types */
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002255
2256typedef struct {
2257 PyObject_HEAD
Brett Cannon77ae87c2007-10-10 00:07:50 +00002258 PyDictObject *di_dict; /* Set to NULL when iterator is exhausted */
Tim Peters9b10f7e2006-05-30 04:16:25 +00002259 Py_ssize_t di_used;
2260 Py_ssize_t di_pos;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002261 PyObject* di_result; /* reusable result tuple for iteritems */
Tim Peters9b10f7e2006-05-30 04:16:25 +00002262 Py_ssize_t len;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002263} dictiterobject;
2264
2265static PyObject *
Brett Cannon77ae87c2007-10-10 00:07:50 +00002266dictiter_new(PyDictObject *dict, PyTypeObject *itertype)
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002267{
2268 dictiterobject *di;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002269 di = PyObject_New(dictiterobject, itertype);
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002270 if (di == NULL)
2271 return NULL;
2272 Py_INCREF(dict);
2273 di->di_dict = dict;
Guido van Rossumb1f35bf2001-05-02 15:13:44 +00002274 di->di_used = dict->ma_used;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002275 di->di_pos = 0;
Raymond Hettinger0ce6dc82004-03-18 08:38:00 +00002276 di->len = dict->ma_used;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002277 if (itertype == &PyDictIterItem_Type) {
2278 di->di_result = PyTuple_Pack(2, Py_None, Py_None);
2279 if (di->di_result == NULL) {
2280 Py_DECREF(di);
2281 return NULL;
2282 }
2283 }
2284 else
2285 di->di_result = NULL;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002286 return (PyObject *)di;
2287}
2288
2289static void
2290dictiter_dealloc(dictiterobject *di)
2291{
Guido van Rossum2147df72002-07-16 20:30:22 +00002292 Py_XDECREF(di->di_dict);
Raymond Hettinger019a1482004-03-18 02:41:19 +00002293 Py_XDECREF(di->di_result);
Neil Schemenauer6189b892002-04-12 02:43:00 +00002294 PyObject_Del(di);
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002295}
2296
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002297static PyObject *
Raymond Hettinger0ce6dc82004-03-18 08:38:00 +00002298dictiter_len(dictiterobject *di)
2299{
Tim Peters9b10f7e2006-05-30 04:16:25 +00002300 Py_ssize_t len = 0;
Raymond Hettinger7892b1c2004-04-12 18:10:01 +00002301 if (di->di_dict != NULL && di->di_used == di->di_dict->ma_used)
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002302 len = di->len;
Tim Peters9b10f7e2006-05-30 04:16:25 +00002303 return PyInt_FromSize_t(len);
Raymond Hettinger0ce6dc82004-03-18 08:38:00 +00002304}
2305
Armin Rigof5b3e362006-02-11 21:32:43 +00002306PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002307
2308static PyMethodDef dictiter_methods[] = {
Armin Rigof5b3e362006-02-11 21:32:43 +00002309 {"__length_hint__", (PyCFunction)dictiter_len, METH_NOARGS, length_hint_doc},
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002310 {NULL, NULL} /* sentinel */
Raymond Hettinger0ce6dc82004-03-18 08:38:00 +00002311};
2312
Raymond Hettinger019a1482004-03-18 02:41:19 +00002313static PyObject *dictiter_iternextkey(dictiterobject *di)
Guido van Rossum213c7a62001-04-23 14:08:49 +00002314{
Raymond Hettinger019a1482004-03-18 02:41:19 +00002315 PyObject *key;
Tim Peters9b10f7e2006-05-30 04:16:25 +00002316 register Py_ssize_t i, mask;
Brett Cannon77ae87c2007-10-10 00:07:50 +00002317 register PyDictEntry *ep;
2318 PyDictObject *d = di->di_dict;
Guido van Rossum213c7a62001-04-23 14:08:49 +00002319
Raymond Hettinger019a1482004-03-18 02:41:19 +00002320 if (d == NULL)
Guido van Rossum2147df72002-07-16 20:30:22 +00002321 return NULL;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002322 assert (PyDict_Check(d));
Guido van Rossum2147df72002-07-16 20:30:22 +00002323
Raymond Hettinger019a1482004-03-18 02:41:19 +00002324 if (di->di_used != d->ma_used) {
Guido van Rossum213c7a62001-04-23 14:08:49 +00002325 PyErr_SetString(PyExc_RuntimeError,
2326 "dictionary changed size during iteration");
Guido van Rossum2147df72002-07-16 20:30:22 +00002327 di->di_used = -1; /* Make this state sticky */
Guido van Rossum213c7a62001-04-23 14:08:49 +00002328 return NULL;
2329 }
Guido van Rossum2147df72002-07-16 20:30:22 +00002330
Raymond Hettinger019a1482004-03-18 02:41:19 +00002331 i = di->di_pos;
2332 if (i < 0)
2333 goto fail;
2334 ep = d->ma_table;
2335 mask = d->ma_mask;
2336 while (i <= mask && ep[i].me_value == NULL)
2337 i++;
2338 di->di_pos = i+1;
2339 if (i > mask)
2340 goto fail;
Raymond Hettinger0ce6dc82004-03-18 08:38:00 +00002341 di->len--;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002342 key = ep[i].me_key;
2343 Py_INCREF(key);
2344 return key;
2345
2346fail:
2347 Py_DECREF(d);
Guido van Rossum2147df72002-07-16 20:30:22 +00002348 di->di_dict = NULL;
Guido van Rossum213c7a62001-04-23 14:08:49 +00002349 return NULL;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002350}
2351
Raymond Hettinger019a1482004-03-18 02:41:19 +00002352PyTypeObject PyDictIterKey_Type = {
Martin v. Löwis68192102007-07-21 06:55:02 +00002353 PyVarObject_HEAD_INIT(&PyType_Type, 0)
Raymond Hettinger0ce6dc82004-03-18 08:38:00 +00002354 "dictionary-keyiterator", /* tp_name */
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002355 sizeof(dictiterobject), /* tp_basicsize */
2356 0, /* tp_itemsize */
2357 /* methods */
2358 (destructor)dictiter_dealloc, /* tp_dealloc */
2359 0, /* tp_print */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002360 0, /* tp_getattr */
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002361 0, /* tp_setattr */
2362 0, /* tp_compare */
2363 0, /* tp_repr */
2364 0, /* tp_as_number */
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002365 0, /* tp_as_sequence */
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002366 0, /* tp_as_mapping */
2367 0, /* tp_hash */
2368 0, /* tp_call */
2369 0, /* tp_str */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002370 PyObject_GenericGetAttr, /* tp_getattro */
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002371 0, /* tp_setattro */
2372 0, /* tp_as_buffer */
2373 Py_TPFLAGS_DEFAULT, /* tp_flags */
2374 0, /* tp_doc */
2375 0, /* tp_traverse */
2376 0, /* tp_clear */
2377 0, /* tp_richcompare */
2378 0, /* tp_weaklistoffset */
Raymond Hettinger1da1dbf2003-03-17 19:46:11 +00002379 PyObject_SelfIter, /* tp_iter */
Raymond Hettinger019a1482004-03-18 02:41:19 +00002380 (iternextfunc)dictiter_iternextkey, /* tp_iternext */
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002381 dictiter_methods, /* tp_methods */
2382 0,
Raymond Hettinger019a1482004-03-18 02:41:19 +00002383};
2384
2385static PyObject *dictiter_iternextvalue(dictiterobject *di)
2386{
2387 PyObject *value;
Tim Peters9b10f7e2006-05-30 04:16:25 +00002388 register Py_ssize_t i, mask;
Brett Cannon77ae87c2007-10-10 00:07:50 +00002389 register PyDictEntry *ep;
2390 PyDictObject *d = di->di_dict;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002391
2392 if (d == NULL)
2393 return NULL;
2394 assert (PyDict_Check(d));
2395
2396 if (di->di_used != d->ma_used) {
2397 PyErr_SetString(PyExc_RuntimeError,
2398 "dictionary changed size during iteration");
2399 di->di_used = -1; /* Make this state sticky */
2400 return NULL;
2401 }
2402
2403 i = di->di_pos;
Guido van Rossum09240f62004-03-20 19:11:58 +00002404 mask = d->ma_mask;
2405 if (i < 0 || i > mask)
Raymond Hettinger019a1482004-03-18 02:41:19 +00002406 goto fail;
2407 ep = d->ma_table;
Guido van Rossum09240f62004-03-20 19:11:58 +00002408 while ((value=ep[i].me_value) == NULL) {
Raymond Hettinger019a1482004-03-18 02:41:19 +00002409 i++;
Guido van Rossum09240f62004-03-20 19:11:58 +00002410 if (i > mask)
2411 goto fail;
2412 }
Raymond Hettinger019a1482004-03-18 02:41:19 +00002413 di->di_pos = i+1;
Raymond Hettinger0ce6dc82004-03-18 08:38:00 +00002414 di->len--;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002415 Py_INCREF(value);
2416 return value;
2417
2418fail:
2419 Py_DECREF(d);
2420 di->di_dict = NULL;
2421 return NULL;
2422}
2423
2424PyTypeObject PyDictIterValue_Type = {
Martin v. Löwis68192102007-07-21 06:55:02 +00002425 PyVarObject_HEAD_INIT(&PyType_Type, 0)
Raymond Hettinger019a1482004-03-18 02:41:19 +00002426 "dictionary-valueiterator", /* tp_name */
2427 sizeof(dictiterobject), /* tp_basicsize */
2428 0, /* tp_itemsize */
2429 /* methods */
2430 (destructor)dictiter_dealloc, /* tp_dealloc */
2431 0, /* tp_print */
2432 0, /* tp_getattr */
2433 0, /* tp_setattr */
2434 0, /* tp_compare */
2435 0, /* tp_repr */
2436 0, /* tp_as_number */
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002437 0, /* tp_as_sequence */
Raymond Hettinger019a1482004-03-18 02:41:19 +00002438 0, /* tp_as_mapping */
2439 0, /* tp_hash */
2440 0, /* tp_call */
2441 0, /* tp_str */
2442 PyObject_GenericGetAttr, /* tp_getattro */
2443 0, /* tp_setattro */
2444 0, /* tp_as_buffer */
2445 Py_TPFLAGS_DEFAULT, /* tp_flags */
2446 0, /* tp_doc */
2447 0, /* tp_traverse */
2448 0, /* tp_clear */
2449 0, /* tp_richcompare */
2450 0, /* tp_weaklistoffset */
2451 PyObject_SelfIter, /* tp_iter */
2452 (iternextfunc)dictiter_iternextvalue, /* tp_iternext */
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002453 dictiter_methods, /* tp_methods */
2454 0,
Raymond Hettinger019a1482004-03-18 02:41:19 +00002455};
2456
2457static PyObject *dictiter_iternextitem(dictiterobject *di)
2458{
2459 PyObject *key, *value, *result = di->di_result;
Tim Peters9b10f7e2006-05-30 04:16:25 +00002460 register Py_ssize_t i, mask;
Brett Cannon77ae87c2007-10-10 00:07:50 +00002461 register PyDictEntry *ep;
2462 PyDictObject *d = di->di_dict;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002463
2464 if (d == NULL)
2465 return NULL;
2466 assert (PyDict_Check(d));
2467
2468 if (di->di_used != d->ma_used) {
2469 PyErr_SetString(PyExc_RuntimeError,
2470 "dictionary changed size during iteration");
2471 di->di_used = -1; /* Make this state sticky */
2472 return NULL;
2473 }
2474
2475 i = di->di_pos;
2476 if (i < 0)
2477 goto fail;
2478 ep = d->ma_table;
2479 mask = d->ma_mask;
2480 while (i <= mask && ep[i].me_value == NULL)
2481 i++;
2482 di->di_pos = i+1;
2483 if (i > mask)
2484 goto fail;
2485
2486 if (result->ob_refcnt == 1) {
2487 Py_INCREF(result);
2488 Py_DECREF(PyTuple_GET_ITEM(result, 0));
2489 Py_DECREF(PyTuple_GET_ITEM(result, 1));
2490 } else {
2491 result = PyTuple_New(2);
Tim Peters60b29962006-01-01 01:19:23 +00002492 if (result == NULL)
Raymond Hettinger019a1482004-03-18 02:41:19 +00002493 return NULL;
2494 }
Raymond Hettinger0ce6dc82004-03-18 08:38:00 +00002495 di->len--;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002496 key = ep[i].me_key;
2497 value = ep[i].me_value;
2498 Py_INCREF(key);
2499 Py_INCREF(value);
2500 PyTuple_SET_ITEM(result, 0, key);
2501 PyTuple_SET_ITEM(result, 1, value);
2502 return result;
2503
2504fail:
2505 Py_DECREF(d);
2506 di->di_dict = NULL;
2507 return NULL;
2508}
2509
2510PyTypeObject PyDictIterItem_Type = {
Martin v. Löwis68192102007-07-21 06:55:02 +00002511 PyVarObject_HEAD_INIT(&PyType_Type, 0)
Raymond Hettinger019a1482004-03-18 02:41:19 +00002512 "dictionary-itemiterator", /* tp_name */
2513 sizeof(dictiterobject), /* tp_basicsize */
2514 0, /* tp_itemsize */
2515 /* methods */
2516 (destructor)dictiter_dealloc, /* tp_dealloc */
2517 0, /* tp_print */
2518 0, /* tp_getattr */
2519 0, /* tp_setattr */
2520 0, /* tp_compare */
2521 0, /* tp_repr */
2522 0, /* tp_as_number */
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002523 0, /* tp_as_sequence */
Raymond Hettinger019a1482004-03-18 02:41:19 +00002524 0, /* tp_as_mapping */
2525 0, /* tp_hash */
2526 0, /* tp_call */
2527 0, /* tp_str */
2528 PyObject_GenericGetAttr, /* tp_getattro */
2529 0, /* tp_setattro */
2530 0, /* tp_as_buffer */
2531 Py_TPFLAGS_DEFAULT, /* tp_flags */
2532 0, /* tp_doc */
2533 0, /* tp_traverse */
2534 0, /* tp_clear */
2535 0, /* tp_richcompare */
2536 0, /* tp_weaklistoffset */
2537 PyObject_SelfIter, /* tp_iter */
2538 (iternextfunc)dictiter_iternextitem, /* tp_iternext */
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002539 dictiter_methods, /* tp_methods */
2540 0,
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002541};