blob: c10bfccdce679b8debde945a945a75fd7b2f4c96 [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"
Christian Heimes0ded5b52007-12-10 15:50:56 +000011#include "stringlib/eq.h"
Guido van Rossum4b1302b1993-03-27 18:11:32 +000012
Guido van Rossum16e93a81997-01-28 00:00:11 +000013
Thomas Wouters89f507f2006-12-13 04:49:30 +000014/* Set a key error with the specified argument, wrapping it in a
15 * tuple automatically so that tuple keys are not unpacked as the
16 * exception arguments. */
17static void
18set_key_error(PyObject *arg)
19{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000020 PyObject *tup;
21 tup = PyTuple_Pack(1, arg);
22 if (!tup)
23 return; /* caller will expect error to be set anyway */
24 PyErr_SetObject(PyExc_KeyError, tup);
25 Py_DECREF(tup);
Thomas Wouters89f507f2006-12-13 04:49:30 +000026}
27
Tim Peterseb28ef22001-06-02 05:27:19 +000028/* Define this out if you don't want conversion statistics on exit. */
Fred Drake1bff34a2000-08-31 19:31:38 +000029#undef SHOW_CONVERSION_COUNTS
30
Tim Peterseb28ef22001-06-02 05:27:19 +000031/* See large comment block below. This must be >= 1. */
32#define PERTURB_SHIFT 5
33
Guido van Rossum16e93a81997-01-28 00:00:11 +000034/*
Tim Peterseb28ef22001-06-02 05:27:19 +000035Major subtleties ahead: Most hash schemes depend on having a "good" hash
36function, in the sense of simulating randomness. Python doesn't: its most
37important hash functions (for strings and ints) are very regular in common
38cases:
Tim Peters15d49292001-05-27 07:39:22 +000039
Guido van Rossumdc5f6b22006-08-24 21:29:26 +000040 >>> map(hash, (0, 1, 2, 3))
41 [0, 1, 2, 3]
42 >>> map(hash, ("namea", "nameb", "namec", "named"))
43 [-1658398457, -1658398460, -1658398459, -1658398462]
44 >>>
Tim Peters15d49292001-05-27 07:39:22 +000045
Tim Peterseb28ef22001-06-02 05:27:19 +000046This isn't necessarily bad! To the contrary, in a table of size 2**i, taking
47the low-order i bits as the initial table index is extremely fast, and there
48are no collisions at all for dicts indexed by a contiguous range of ints.
49The same is approximately true when keys are "consecutive" strings. So this
50gives better-than-random behavior in common cases, and that's very desirable.
Tim Peters15d49292001-05-27 07:39:22 +000051
Tim Peterseb28ef22001-06-02 05:27:19 +000052OTOH, when collisions occur, the tendency to fill contiguous slices of the
53hash table makes a good collision resolution strategy crucial. Taking only
54the last i bits of the hash code is also vulnerable: for example, consider
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000055the list [i << 16 for i in range(20000)] as a set of keys. Since ints are
Guido van Rossumdc5f6b22006-08-24 21:29:26 +000056their own hash codes, and this fits in a dict of size 2**15, the last 15 bits
57 of every hash code are all 0: they *all* map to the same table index.
Tim Peters15d49292001-05-27 07:39:22 +000058
Tim Peterseb28ef22001-06-02 05:27:19 +000059But catering to unusual cases should not slow the usual ones, so we just take
60the last i bits anyway. It's up to collision resolution to do the rest. If
61we *usually* find the key we're looking for on the first try (and, it turns
62out, we usually do -- the table load factor is kept under 2/3, so the odds
63are solidly in our favor), then it makes best sense to keep the initial index
64computation dirt cheap.
Tim Peters15d49292001-05-27 07:39:22 +000065
Tim Peterseb28ef22001-06-02 05:27:19 +000066The first half of collision resolution is to visit table indices via this
67recurrence:
Tim Peters15d49292001-05-27 07:39:22 +000068
Tim Peterseb28ef22001-06-02 05:27:19 +000069 j = ((5*j) + 1) mod 2**i
Tim Peters15d49292001-05-27 07:39:22 +000070
Tim Peterseb28ef22001-06-02 05:27:19 +000071For any initial j in range(2**i), repeating that 2**i times generates each
72int in range(2**i) exactly once (see any text on random-number generation for
73proof). By itself, this doesn't help much: like linear probing (setting
74j += 1, or j -= 1, on each loop trip), it scans the table entries in a fixed
75order. This would be bad, except that's not the only thing we do, and it's
76actually *good* in the common cases where hash keys are consecutive. In an
77example that's really too small to make this entirely clear, for a table of
78size 2**3 the order of indices is:
Tim Peters15d49292001-05-27 07:39:22 +000079
Tim Peterseb28ef22001-06-02 05:27:19 +000080 0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating]
81
82If two things come in at index 5, the first place we look after is index 2,
83not 6, so if another comes in at index 6 the collision at 5 didn't hurt it.
84Linear probing is deadly in this case because there the fixed probe order
85is the *same* as the order consecutive keys are likely to arrive. But it's
86extremely unlikely hash codes will follow a 5*j+1 recurrence by accident,
87and certain that consecutive hash codes do not.
88
89The other half of the strategy is to get the other bits of the hash code
90into play. This is done by initializing a (unsigned) vrbl "perturb" to the
91full hash code, and changing the recurrence to:
92
93 j = (5*j) + 1 + perturb;
94 perturb >>= PERTURB_SHIFT;
95 use j % 2**i as the next table index;
96
97Now the probe sequence depends (eventually) on every bit in the hash code,
98and the pseudo-scrambling property of recurring on 5*j+1 is more valuable,
99because it quickly magnifies small differences in the bits that didn't affect
100the initial index. Note that because perturb is unsigned, if the recurrence
101is executed often enough perturb eventually becomes and remains 0. At that
102point (very rarely reached) the recurrence is on (just) 5*j+1 again, and
103that's certain to find an empty slot eventually (since it generates every int
104in range(2**i), and we make sure there's always at least one empty slot).
105
106Selecting a good value for PERTURB_SHIFT is a balancing act. You want it
107small so that the high bits of the hash code continue to affect the probe
108sequence across iterations; but you want it large so that in really bad cases
109the high-order hash bits have an effect on early iterations. 5 was "the
110best" in minimizing total collisions across experiments Tim Peters ran (on
111both normal and pathological cases), but 4 and 6 weren't significantly worse.
112
Guido van Rossumdc5f6b22006-08-24 21:29:26 +0000113Historical: Reimer Behrends contributed the idea of using a polynomial-based
Tim Peterseb28ef22001-06-02 05:27:19 +0000114approach, using repeated multiplication by x in GF(2**n) where an irreducible
115polynomial for each table size was chosen such that x was a primitive root.
116Christian Tismer later extended that to use division by x instead, as an
117efficient way to get the high bits of the hash code into play. This scheme
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000118also gave excellent collision statistics, but was more expensive: two
119if-tests were required inside the loop; computing "the next" index took about
120the same number of operations but without as much potential parallelism
121(e.g., computing 5*j can go on at the same time as computing 1+perturb in the
122above, and then shifting perturb can be done while the table index is being
123masked); and the PyDictObject struct required a member to hold the table's
124polynomial. In Tim's experiments the current scheme ran faster, produced
125equally good collision statistics, needed less code & used less memory.
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000126
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000127*/
Tim Petersdea48ec2001-05-22 20:40:22 +0000128
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000129/* Object used as dummy key to fill deleted entries */
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000130static PyObject *dummy = NULL; /* Initialized by first call to newPyDictObject() */
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000131
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000132#ifdef Py_REF_DEBUG
133PyObject *
134_PyDict_Dummy(void)
135{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000136 return dummy;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000137}
138#endif
139
Fred Drake1bff34a2000-08-31 19:31:38 +0000140/* forward declarations */
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000141static PyDictEntry *
Benjamin Petersone6baa462010-10-17 21:20:58 +0000142lookdict_unicode(PyDictObject *mp, PyObject *key, Py_hash_t hash);
Fred Drake1bff34a2000-08-31 19:31:38 +0000143
144#ifdef SHOW_CONVERSION_COUNTS
145static long created = 0L;
146static long converted = 0L;
147
148static void
149show_counts(void)
150{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000151 fprintf(stderr, "created %ld string dicts\n", created);
152 fprintf(stderr, "converted %ld to normal dicts\n", converted);
153 fprintf(stderr, "%.2f%% conversion rate\n", (100.0*converted)/created);
Fred Drake1bff34a2000-08-31 19:31:38 +0000154}
155#endif
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000156
Christian Heimes77c02eb2008-02-09 02:18:51 +0000157/* Debug statistic to compare allocations with reuse through the free list */
158#undef SHOW_ALLOC_COUNT
159#ifdef SHOW_ALLOC_COUNT
160static size_t count_alloc = 0;
161static size_t count_reuse = 0;
162
163static void
164show_alloc(void)
165{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000166 fprintf(stderr, "Dict allocations: %" PY_FORMAT_SIZE_T "d\n",
167 count_alloc);
168 fprintf(stderr, "Dict reuse through freelist: %" PY_FORMAT_SIZE_T
169 "d\n", count_reuse);
170 fprintf(stderr, "%.2f%% reuse rate\n\n",
171 (100.0*count_reuse/(count_alloc+count_reuse)));
Christian Heimes77c02eb2008-02-09 02:18:51 +0000172}
173#endif
174
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000175/* Debug statistic to count GC tracking of dicts */
176#ifdef SHOW_TRACK_COUNT
177static Py_ssize_t count_untracked = 0;
178static Py_ssize_t count_tracked = 0;
179
180static void
181show_track(void)
182{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000183 fprintf(stderr, "Dicts created: %" PY_FORMAT_SIZE_T "d\n",
184 count_tracked + count_untracked);
185 fprintf(stderr, "Dicts tracked by the GC: %" PY_FORMAT_SIZE_T
186 "d\n", count_tracked);
187 fprintf(stderr, "%.2f%% dict tracking rate\n\n",
188 (100.0*count_tracked/(count_untracked+count_tracked)));
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000189}
190#endif
191
192
Tim Peters6d6c1a32001-08-02 04:15:00 +0000193/* Initialization macros.
194 There are two ways to create a dict: PyDict_New() is the main C API
195 function, and the tp_new slot maps to dict_new(). In the latter case we
196 can save a little time over what PyDict_New does because it's guaranteed
197 that the PyDictObject struct is already zeroed out.
198 Everyone except dict_new() should use EMPTY_TO_MINSIZE (unless they have
199 an excellent reason not to).
200*/
201
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000202#define INIT_NONZERO_DICT_SLOTS(mp) do { \
203 (mp)->ma_table = (mp)->ma_smalltable; \
204 (mp)->ma_mask = PyDict_MINSIZE - 1; \
Tim Peters6d6c1a32001-08-02 04:15:00 +0000205 } while(0)
206
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000207#define EMPTY_TO_MINSIZE(mp) do { \
208 memset((mp)->ma_smalltable, 0, sizeof((mp)->ma_smalltable)); \
209 (mp)->ma_used = (mp)->ma_fill = 0; \
210 INIT_NONZERO_DICT_SLOTS(mp); \
Tim Petersdea48ec2001-05-22 20:40:22 +0000211 } while(0)
212
Raymond Hettinger43442782004-03-17 21:55:03 +0000213/* Dictionary reuse scheme to save calls to malloc, free, and memset */
Christian Heimes2202f872008-02-06 14:31:34 +0000214#ifndef PyDict_MAXFREELIST
215#define PyDict_MAXFREELIST 80
216#endif
217static PyDictObject *free_list[PyDict_MAXFREELIST];
218static int numfree = 0;
Raymond Hettinger43442782004-03-17 21:55:03 +0000219
Christian Heimes77c02eb2008-02-09 02:18:51 +0000220void
221PyDict_Fini(void)
222{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000223 PyDictObject *op;
Christian Heimes77c02eb2008-02-09 02:18:51 +0000224
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000225 while (numfree) {
226 op = free_list[--numfree];
227 assert(PyDict_CheckExact(op));
228 PyObject_GC_Del(op);
229 }
Christian Heimes77c02eb2008-02-09 02:18:51 +0000230}
231
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000232PyObject *
Thomas Wouters78890102000-07-22 19:25:51 +0000233PyDict_New(void)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000234{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000235 register PyDictObject *mp;
236 if (dummy == NULL) { /* Auto-initialize dummy */
237 dummy = PyUnicode_FromString("<dummy key>");
238 if (dummy == NULL)
239 return NULL;
Fred Drake1bff34a2000-08-31 19:31:38 +0000240#ifdef SHOW_CONVERSION_COUNTS
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000241 Py_AtExit(show_counts);
Fred Drake1bff34a2000-08-31 19:31:38 +0000242#endif
Christian Heimes77c02eb2008-02-09 02:18:51 +0000243#ifdef SHOW_ALLOC_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000244 Py_AtExit(show_alloc);
Christian Heimes77c02eb2008-02-09 02:18:51 +0000245#endif
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000246#ifdef SHOW_TRACK_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000247 Py_AtExit(show_track);
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000248#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000249 }
250 if (numfree) {
251 mp = free_list[--numfree];
252 assert (mp != NULL);
253 assert (Py_TYPE(mp) == &PyDict_Type);
254 _Py_NewReference((PyObject *)mp);
255 if (mp->ma_fill) {
256 EMPTY_TO_MINSIZE(mp);
257 } else {
258 /* At least set ma_table and ma_mask; these are wrong
259 if an empty but presized dict is added to freelist */
260 INIT_NONZERO_DICT_SLOTS(mp);
261 }
262 assert (mp->ma_used == 0);
263 assert (mp->ma_table == mp->ma_smalltable);
264 assert (mp->ma_mask == PyDict_MINSIZE - 1);
Christian Heimes77c02eb2008-02-09 02:18:51 +0000265#ifdef SHOW_ALLOC_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000266 count_reuse++;
Christian Heimes77c02eb2008-02-09 02:18:51 +0000267#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000268 } else {
269 mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
270 if (mp == NULL)
271 return NULL;
272 EMPTY_TO_MINSIZE(mp);
Christian Heimes77c02eb2008-02-09 02:18:51 +0000273#ifdef SHOW_ALLOC_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000274 count_alloc++;
Christian Heimes77c02eb2008-02-09 02:18:51 +0000275#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000276 }
277 mp->ma_lookup = lookdict_unicode;
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000278#ifdef SHOW_TRACK_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000279 count_untracked++;
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000280#endif
Fred Drake1bff34a2000-08-31 19:31:38 +0000281#ifdef SHOW_CONVERSION_COUNTS
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000282 ++created;
Fred Drake1bff34a2000-08-31 19:31:38 +0000283#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000284 return (PyObject *)mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000285}
286
287/*
288The basic lookup function used by all operations.
Guido van Rossum16e93a81997-01-28 00:00:11 +0000289This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000290Open addressing is preferred over chaining since the link overhead for
291chaining would be substantial (100% with typical malloc overhead).
292
Tim Peterseb28ef22001-06-02 05:27:19 +0000293The initial probe index is computed as hash mod the table size. Subsequent
294probe indices are computed as explained earlier.
Guido van Rossum2bc13791999-03-24 19:06:42 +0000295
296All arithmetic on hash should ignore overflow.
Guido van Rossum16e93a81997-01-28 00:00:11 +0000297
Guido van Rossumdc5f6b22006-08-24 21:29:26 +0000298The details in this version are due to Tim Peters, building on many past
Tim Peterseb28ef22001-06-02 05:27:19 +0000299contributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and
Guido van Rossumdc5f6b22006-08-24 21:29:26 +0000300Christian Tismer.
Fred Drake1bff34a2000-08-31 19:31:38 +0000301
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000302lookdict() is general-purpose, and may return NULL if (and only if) a
303comparison raises an exception (this was new in Python 2.5).
Guido van Rossum89d8c602007-09-18 17:26:56 +0000304lookdict_unicode() below is specialized to string keys, comparison of which can
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000305never raise an exception; that function can never return NULL. For both, when
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000306the key isn't found a PyDictEntry* is returned for which the me_value field is
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000307NULL; this is the slot in the dict at which the key would have been found, and
308the caller can (if it wishes) add the <key, value> pair to the returned
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000309PyDictEntry*.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000310*/
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000311static PyDictEntry *
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000312lookdict(PyDictObject *mp, PyObject *key, register Py_hash_t hash)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000313{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000314 register size_t i;
315 register size_t perturb;
316 register PyDictEntry *freeslot;
317 register size_t mask = (size_t)mp->ma_mask;
318 PyDictEntry *ep0 = mp->ma_table;
319 register PyDictEntry *ep;
320 register int cmp;
321 PyObject *startkey;
Tim Peterseb28ef22001-06-02 05:27:19 +0000322
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000323 i = (size_t)hash & mask;
324 ep = &ep0[i];
325 if (ep->me_key == NULL || ep->me_key == key)
326 return ep;
Tim Peters7b5d0af2001-06-03 04:14:43 +0000327
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000328 if (ep->me_key == dummy)
329 freeslot = ep;
330 else {
331 if (ep->me_hash == hash) {
332 startkey = ep->me_key;
333 Py_INCREF(startkey);
334 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
335 Py_DECREF(startkey);
336 if (cmp < 0)
337 return NULL;
338 if (ep0 == mp->ma_table && ep->me_key == startkey) {
339 if (cmp > 0)
340 return ep;
341 }
342 else {
343 /* The compare did major nasty stuff to the
344 * dict: start over.
345 * XXX A clever adversary could prevent this
346 * XXX from terminating.
347 */
348 return lookdict(mp, key, hash);
349 }
350 }
351 freeslot = NULL;
352 }
Tim Peters15d49292001-05-27 07:39:22 +0000353
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000354 /* In the loop, me_key == dummy is by far (factor of 100s) the
355 least likely outcome, so test for that last. */
356 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
357 i = (i << 2) + i + perturb + 1;
358 ep = &ep0[i & mask];
359 if (ep->me_key == NULL)
360 return freeslot == NULL ? ep : freeslot;
361 if (ep->me_key == key)
362 return ep;
363 if (ep->me_hash == hash && ep->me_key != dummy) {
364 startkey = ep->me_key;
365 Py_INCREF(startkey);
366 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
367 Py_DECREF(startkey);
368 if (cmp < 0)
369 return NULL;
370 if (ep0 == mp->ma_table && ep->me_key == startkey) {
371 if (cmp > 0)
372 return ep;
373 }
374 else {
375 /* The compare did major nasty stuff to the
376 * dict: start over.
377 * XXX A clever adversary could prevent this
378 * XXX from terminating.
379 */
380 return lookdict(mp, key, hash);
381 }
382 }
383 else if (ep->me_key == dummy && freeslot == NULL)
384 freeslot = ep;
385 }
386 assert(0); /* NOT REACHED */
387 return 0;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000388}
389
390/*
Guido van Rossum89d8c602007-09-18 17:26:56 +0000391 * Hacked up version of lookdict which can assume keys are always
392 * unicodes; this assumption allows testing for errors during
393 * PyObject_RichCompareBool() to be dropped; unicode-unicode
394 * comparisons never raise exceptions. This also means we don't need
395 * to go through PyObject_RichCompareBool(); we can always use
396 * unicode_eq() directly.
Fred Drake1bff34a2000-08-31 19:31:38 +0000397 *
Guido van Rossum89d8c602007-09-18 17:26:56 +0000398 * This is valuable because dicts with only unicode keys are very common.
Fred Drake1bff34a2000-08-31 19:31:38 +0000399 */
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000400static PyDictEntry *
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000401lookdict_unicode(PyDictObject *mp, PyObject *key, register Py_hash_t hash)
Fred Drake1bff34a2000-08-31 19:31:38 +0000402{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000403 register size_t i;
404 register size_t perturb;
405 register PyDictEntry *freeslot;
406 register size_t mask = (size_t)mp->ma_mask;
407 PyDictEntry *ep0 = mp->ma_table;
408 register PyDictEntry *ep;
Fred Drake1bff34a2000-08-31 19:31:38 +0000409
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000410 /* Make sure this function doesn't have to handle non-unicode keys,
411 including subclasses of str; e.g., one reason to subclass
412 unicodes is to override __eq__, and for speed we don't cater to
413 that here. */
414 if (!PyUnicode_CheckExact(key)) {
Fred Drake1bff34a2000-08-31 19:31:38 +0000415#ifdef SHOW_CONVERSION_COUNTS
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000416 ++converted;
Fred Drake1bff34a2000-08-31 19:31:38 +0000417#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000418 mp->ma_lookup = lookdict;
419 return lookdict(mp, key, hash);
420 }
421 i = hash & mask;
422 ep = &ep0[i];
423 if (ep->me_key == NULL || ep->me_key == key)
424 return ep;
425 if (ep->me_key == dummy)
426 freeslot = ep;
427 else {
428 if (ep->me_hash == hash && unicode_eq(ep->me_key, key))
429 return ep;
430 freeslot = NULL;
431 }
Tim Peters15d49292001-05-27 07:39:22 +0000432
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000433 /* In the loop, me_key == dummy is by far (factor of 100s) the
434 least likely outcome, so test for that last. */
435 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
436 i = (i << 2) + i + perturb + 1;
437 ep = &ep0[i & mask];
438 if (ep->me_key == NULL)
439 return freeslot == NULL ? ep : freeslot;
440 if (ep->me_key == key
441 || (ep->me_hash == hash
442 && ep->me_key != dummy
443 && unicode_eq(ep->me_key, key)))
444 return ep;
445 if (ep->me_key == dummy && freeslot == NULL)
446 freeslot = ep;
447 }
448 assert(0); /* NOT REACHED */
449 return 0;
Fred Drake1bff34a2000-08-31 19:31:38 +0000450}
451
Benjamin Petersonfb886362010-04-24 18:21:17 +0000452int
453_PyDict_HasOnlyStringKeys(PyObject *dict)
454{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000455 Py_ssize_t pos = 0;
456 PyObject *key, *value;
Benjamin Petersonf6096542010-11-17 22:33:12 +0000457 assert(PyDict_Check(dict));
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000458 /* Shortcut */
459 if (((PyDictObject *)dict)->ma_lookup == lookdict_unicode)
460 return 1;
461 while (PyDict_Next(dict, &pos, &key, &value))
462 if (!PyUnicode_Check(key))
463 return 0;
464 return 1;
Benjamin Petersonfb886362010-04-24 18:21:17 +0000465}
466
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000467#ifdef SHOW_TRACK_COUNT
468#define INCREASE_TRACK_COUNT \
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000469 (count_tracked++, count_untracked--);
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000470#define DECREASE_TRACK_COUNT \
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000471 (count_tracked--, count_untracked++);
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000472#else
473#define INCREASE_TRACK_COUNT
474#define DECREASE_TRACK_COUNT
475#endif
476
477#define MAINTAIN_TRACKING(mp, key, value) \
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000478 do { \
479 if (!_PyObject_GC_IS_TRACKED(mp)) { \
480 if (_PyObject_GC_MAY_BE_TRACKED(key) || \
481 _PyObject_GC_MAY_BE_TRACKED(value)) { \
482 _PyObject_GC_TRACK(mp); \
483 INCREASE_TRACK_COUNT \
484 } \
485 } \
486 } while(0)
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000487
488void
489_PyDict_MaybeUntrack(PyObject *op)
490{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000491 PyDictObject *mp;
492 PyObject *value;
493 Py_ssize_t mask, i;
494 PyDictEntry *ep;
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000495
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000496 if (!PyDict_CheckExact(op) || !_PyObject_GC_IS_TRACKED(op))
497 return;
498
499 mp = (PyDictObject *) op;
500 ep = mp->ma_table;
501 mask = mp->ma_mask;
502 for (i = 0; i <= mask; i++) {
503 if ((value = ep[i].me_value) == NULL)
504 continue;
505 if (_PyObject_GC_MAY_BE_TRACKED(value) ||
506 _PyObject_GC_MAY_BE_TRACKED(ep[i].me_key))
507 return;
508 }
509 DECREASE_TRACK_COUNT
510 _PyObject_GC_UNTRACK(op);
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000511}
512
Fred Drake1bff34a2000-08-31 19:31:38 +0000513/*
Antoine Pitroue965d972012-02-27 00:45:12 +0100514Internal routine to insert a new item into the table when you have entry object.
515Used by insertdict.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000516*/
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000517static int
Antoine Pitroue965d972012-02-27 00:45:12 +0100518insertdict_by_entry(register PyDictObject *mp, PyObject *key, Py_hash_t hash,
519 PyDictEntry *ep, PyObject *value)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000520{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000521 PyObject *old_value;
Tim Peters6d6c1a32001-08-02 04:15:00 +0000522
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000523 MAINTAIN_TRACKING(mp, key, value);
524 if (ep->me_value != NULL) {
525 old_value = ep->me_value;
526 ep->me_value = value;
527 Py_DECREF(old_value); /* which **CAN** re-enter */
528 Py_DECREF(key);
529 }
530 else {
531 if (ep->me_key == NULL)
532 mp->ma_fill++;
533 else {
534 assert(ep->me_key == dummy);
535 Py_DECREF(dummy);
536 }
537 ep->me_key = key;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000538 ep->me_hash = hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000539 ep->me_value = value;
540 mp->ma_used++;
541 }
542 return 0;
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000543}
544
Antoine Pitroue965d972012-02-27 00:45:12 +0100545
546/*
547Internal routine to insert a new item into the table.
548Used both by the internal resize routine and by the public insert routine.
549Eats a reference to key and one to value.
550Returns -1 if an error occurred, or 0 on success.
551*/
552static int
553insertdict(register PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
554{
555 register PyDictEntry *ep;
556
557 assert(mp->ma_lookup != NULL);
558 ep = mp->ma_lookup(mp, key, hash);
559 if (ep == NULL) {
560 Py_DECREF(key);
561 Py_DECREF(value);
562 return -1;
563 }
564 return insertdict_by_entry(mp, key, hash, ep, value);
565}
566
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000567/*
568Internal routine used by dictresize() to insert an item which is
569known to be absent from the dict. This routine also assumes that
570the dict contains no deleted entries. Besides the performance benefit,
571using insertdict() in dictresize() is dangerous (SF bug #1456209).
572Note that no refcounts are changed by this routine; if needed, the caller
573is responsible for incref'ing `key` and `value`.
574*/
575static void
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000576insertdict_clean(register PyDictObject *mp, PyObject *key, Py_hash_t hash,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000577 PyObject *value)
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000578{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000579 register size_t i;
580 register size_t perturb;
581 register size_t mask = (size_t)mp->ma_mask;
582 PyDictEntry *ep0 = mp->ma_table;
583 register PyDictEntry *ep;
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000584
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000585 MAINTAIN_TRACKING(mp, key, value);
586 i = hash & mask;
587 ep = &ep0[i];
588 for (perturb = hash; ep->me_key != NULL; perturb >>= PERTURB_SHIFT) {
589 i = (i << 2) + i + perturb + 1;
590 ep = &ep0[i & mask];
591 }
592 assert(ep->me_value == NULL);
593 mp->ma_fill++;
594 ep->me_key = key;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000595 ep->me_hash = hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000596 ep->me_value = value;
597 mp->ma_used++;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000598}
599
600/*
601Restructure the table by allocating a new table and reinserting all
602items again. When entries have been deleted, the new table may
603actually be smaller than the old one.
604*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000605static int
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000606dictresize(PyDictObject *mp, Py_ssize_t minused)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000607{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000608 Py_ssize_t newsize;
609 PyDictEntry *oldtable, *newtable, *ep;
610 Py_ssize_t i;
611 int is_oldtable_malloced;
612 PyDictEntry small_copy[PyDict_MINSIZE];
Tim Peters91a364d2001-05-19 07:04:38 +0000613
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000614 assert(minused >= 0);
Tim Peters0c6010b2001-05-23 23:33:57 +0000615
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000616 /* Find the smallest table size > minused. */
617 for (newsize = PyDict_MINSIZE;
618 newsize <= minused && newsize > 0;
619 newsize <<= 1)
620 ;
621 if (newsize <= 0) {
622 PyErr_NoMemory();
623 return -1;
624 }
Tim Peters0c6010b2001-05-23 23:33:57 +0000625
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000626 /* Get space for a new table. */
627 oldtable = mp->ma_table;
628 assert(oldtable != NULL);
629 is_oldtable_malloced = oldtable != mp->ma_smalltable;
Tim Peters0c6010b2001-05-23 23:33:57 +0000630
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000631 if (newsize == PyDict_MINSIZE) {
632 /* A large table is shrinking, or we can't get any smaller. */
633 newtable = mp->ma_smalltable;
634 if (newtable == oldtable) {
635 if (mp->ma_fill == mp->ma_used) {
636 /* No dummies, so no point doing anything. */
637 return 0;
638 }
639 /* We're not going to resize it, but rebuild the
640 table anyway to purge old dummy entries.
641 Subtle: This is *necessary* if fill==size,
642 as lookdict needs at least one virgin slot to
643 terminate failing searches. If fill < size, it's
644 merely desirable, as dummies slow searches. */
645 assert(mp->ma_fill > mp->ma_used);
646 memcpy(small_copy, oldtable, sizeof(small_copy));
647 oldtable = small_copy;
648 }
649 }
650 else {
651 newtable = PyMem_NEW(PyDictEntry, newsize);
652 if (newtable == NULL) {
653 PyErr_NoMemory();
654 return -1;
655 }
656 }
Tim Peters0c6010b2001-05-23 23:33:57 +0000657
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000658 /* Make the dict empty, using the new table. */
659 assert(newtable != oldtable);
660 mp->ma_table = newtable;
661 mp->ma_mask = newsize - 1;
662 memset(newtable, 0, sizeof(PyDictEntry) * newsize);
663 mp->ma_used = 0;
664 i = mp->ma_fill;
665 mp->ma_fill = 0;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000666
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000667 /* Copy the data over; this is refcount-neutral for active entries;
668 dummy entries aren't copied over, of course */
669 for (ep = oldtable; i > 0; ep++) {
670 if (ep->me_value != NULL) { /* active entry */
671 --i;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000672 insertdict_clean(mp, ep->me_key, ep->me_hash, ep->me_value);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000673 }
674 else if (ep->me_key != NULL) { /* dummy entry */
675 --i;
676 assert(ep->me_key == dummy);
677 Py_DECREF(ep->me_key);
678 }
679 /* else key == value == NULL: nothing to do */
680 }
Guido van Rossumd7047b31995-01-02 19:07:15 +0000681
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000682 if (is_oldtable_malloced)
683 PyMem_DEL(oldtable);
684 return 0;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000685}
686
Christian Heimes99170a52007-12-19 02:07:34 +0000687/* Create a new dictionary pre-sized to hold an estimated number of elements.
688 Underestimates are okay because the dictionary will resize as necessary.
689 Overestimates just mean the dictionary will be more sparse than usual.
690*/
691
692PyObject *
693_PyDict_NewPresized(Py_ssize_t minused)
694{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000695 PyObject *op = PyDict_New();
Christian Heimes99170a52007-12-19 02:07:34 +0000696
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000697 if (minused>5 && op != NULL && dictresize((PyDictObject *)op, minused) == -1) {
698 Py_DECREF(op);
699 return NULL;
700 }
701 return op;
Christian Heimes99170a52007-12-19 02:07:34 +0000702}
703
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000704/* Note that, for historical reasons, PyDict_GetItem() suppresses all errors
705 * that may occur (originally dicts supported only string keys, and exceptions
706 * weren't possible). So, while the original intent was that a NULL return
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000707 * meant the key wasn't present, in reality it can mean that, or that an error
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000708 * (suppressed) occurred while computing the key's hash, or that some error
709 * (suppressed) occurred when comparing keys in the dict's internal probe
710 * sequence. A nasty example of the latter is when a Python-coded comparison
711 * function hits a stack-depth error, which can cause this to return NULL
712 * even if the key is present.
713 */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000714PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000715PyDict_GetItem(PyObject *op, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000716{
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000717 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000718 PyDictObject *mp = (PyDictObject *)op;
719 PyDictEntry *ep;
720 PyThreadState *tstate;
721 if (!PyDict_Check(op))
722 return NULL;
723 if (!PyUnicode_CheckExact(key) ||
724 (hash = ((PyUnicodeObject *) key)->hash) == -1)
725 {
726 hash = PyObject_Hash(key);
727 if (hash == -1) {
728 PyErr_Clear();
729 return NULL;
730 }
731 }
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000732
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000733 /* We can arrive here with a NULL tstate during initialization: try
734 running "python -Wi" for an example related to string interning.
735 Let's just hope that no exception occurs then... This must be
736 _PyThreadState_Current and not PyThreadState_GET() because in debug
737 mode, the latter complains if tstate is NULL. */
738 tstate = (PyThreadState*)_Py_atomic_load_relaxed(
739 &_PyThreadState_Current);
740 if (tstate != NULL && tstate->curexc_type != NULL) {
741 /* preserve the existing exception */
742 PyObject *err_type, *err_value, *err_tb;
743 PyErr_Fetch(&err_type, &err_value, &err_tb);
744 ep = (mp->ma_lookup)(mp, key, hash);
745 /* ignore errors */
746 PyErr_Restore(err_type, err_value, err_tb);
747 if (ep == NULL)
748 return NULL;
749 }
750 else {
751 ep = (mp->ma_lookup)(mp, key, hash);
752 if (ep == NULL) {
753 PyErr_Clear();
754 return NULL;
755 }
756 }
757 return ep->me_value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000758}
759
Guido van Rossum47b9ff62006-08-24 00:41:19 +0000760/* Variant of PyDict_GetItem() that doesn't suppress exceptions.
761 This returns NULL *with* an exception set if an exception occurred.
762 It returns NULL *without* an exception set if the key wasn't present.
763*/
764PyObject *
765PyDict_GetItemWithError(PyObject *op, PyObject *key)
766{
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000767 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000768 PyDictObject*mp = (PyDictObject *)op;
769 PyDictEntry *ep;
Guido van Rossum47b9ff62006-08-24 00:41:19 +0000770
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000771 if (!PyDict_Check(op)) {
772 PyErr_BadInternalCall();
773 return NULL;
774 }
775 if (!PyUnicode_CheckExact(key) ||
776 (hash = ((PyUnicodeObject *) key)->hash) == -1)
777 {
778 hash = PyObject_Hash(key);
779 if (hash == -1) {
780 return NULL;
781 }
782 }
Guido van Rossum47b9ff62006-08-24 00:41:19 +0000783
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000784 ep = (mp->ma_lookup)(mp, key, hash);
785 if (ep == NULL)
786 return NULL;
787 return ep->me_value;
Guido van Rossum47b9ff62006-08-24 00:41:19 +0000788}
789
Antoine Pitroue965d972012-02-27 00:45:12 +0100790static int
791dict_set_item_by_hash_or_entry(register PyObject *op, PyObject *key,
792 Py_hash_t hash, PyDictEntry *ep, PyObject *value)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000793{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000794 register PyDictObject *mp;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000795 register Py_ssize_t n_used;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000796
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000797 mp = (PyDictObject *)op;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000798 assert(mp->ma_fill <= mp->ma_mask); /* at least one empty slot */
799 n_used = mp->ma_used;
800 Py_INCREF(value);
801 Py_INCREF(key);
Antoine Pitroue965d972012-02-27 00:45:12 +0100802 if (ep == NULL) {
803 if (insertdict(mp, key, hash, value) != 0)
804 return -1;
805 }
806 else {
807 if (insertdict_by_entry(mp, key, hash, ep, value) != 0)
808 return -1;
809 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000810 /* If we added a key, we can safely resize. Otherwise just return!
811 * If fill >= 2/3 size, adjust size. Normally, this doubles or
812 * quaduples the size, but it's also possible for the dict to shrink
813 * (if ma_fill is much larger than ma_used, meaning a lot of dict
814 * keys have been * deleted).
815 *
816 * Quadrupling the size improves average dictionary sparseness
817 * (reducing collisions) at the cost of some memory and iteration
818 * speed (which loops over every possible entry). It also halves
819 * the number of expensive resize operations in a growing dictionary.
820 *
821 * Very large dictionaries (over 50K items) use doubling instead.
822 * This may help applications with severe memory constraints.
823 */
824 if (!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))
825 return 0;
826 return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000827}
828
Antoine Pitroue965d972012-02-27 00:45:12 +0100829/* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
830 * dictionary if it's merely replacing the value for an existing key.
831 * This means that it's safe to loop over a dictionary with PyDict_Next()
832 * and occasionally replace a value -- but you can't insert new keys or
833 * remove them.
834 */
835int
836PyDict_SetItem(register PyObject *op, PyObject *key, PyObject *value)
837{
838 register Py_hash_t hash;
839
840 if (!PyDict_Check(op)) {
841 PyErr_BadInternalCall();
842 return -1;
843 }
844 assert(key);
845 assert(value);
846 if (PyUnicode_CheckExact(key)) {
847 hash = ((PyUnicodeObject *) key)->hash;
848 if (hash == -1)
849 hash = PyObject_Hash(key);
850 }
851 else {
852 hash = PyObject_Hash(key);
853 if (hash == -1)
854 return -1;
855 }
856 return dict_set_item_by_hash_or_entry(op, key, hash, NULL, value);
857}
858
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000859int
Tim Peters1f5871e2000-07-04 17:44:48 +0000860PyDict_DelItem(PyObject *op, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000861{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000862 register PyDictObject *mp;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000863 register Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000864 register PyDictEntry *ep;
865 PyObject *old_value, *old_key;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000866
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000867 if (!PyDict_Check(op)) {
868 PyErr_BadInternalCall();
869 return -1;
870 }
871 assert(key);
872 if (!PyUnicode_CheckExact(key) ||
873 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
874 hash = PyObject_Hash(key);
875 if (hash == -1)
876 return -1;
877 }
878 mp = (PyDictObject *)op;
879 ep = (mp->ma_lookup)(mp, key, hash);
880 if (ep == NULL)
881 return -1;
882 if (ep->me_value == NULL) {
883 set_key_error(key);
884 return -1;
885 }
886 old_key = ep->me_key;
887 Py_INCREF(dummy);
888 ep->me_key = dummy;
889 old_value = ep->me_value;
890 ep->me_value = NULL;
891 mp->ma_used--;
892 Py_DECREF(old_value);
893 Py_DECREF(old_key);
894 return 0;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000895}
896
Guido van Rossum25831651993-05-19 14:50:45 +0000897void
Tim Peters1f5871e2000-07-04 17:44:48 +0000898PyDict_Clear(PyObject *op)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000899{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000900 PyDictObject *mp;
901 PyDictEntry *ep, *table;
902 int table_is_malloced;
903 Py_ssize_t fill;
904 PyDictEntry small_copy[PyDict_MINSIZE];
Tim Petersdea48ec2001-05-22 20:40:22 +0000905#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000906 Py_ssize_t i, n;
Tim Petersdea48ec2001-05-22 20:40:22 +0000907#endif
908
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000909 if (!PyDict_Check(op))
910 return;
911 mp = (PyDictObject *)op;
Tim Petersdea48ec2001-05-22 20:40:22 +0000912#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000913 n = mp->ma_mask + 1;
914 i = 0;
Tim Petersdea48ec2001-05-22 20:40:22 +0000915#endif
916
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000917 table = mp->ma_table;
918 assert(table != NULL);
919 table_is_malloced = table != mp->ma_smalltable;
Tim Petersdea48ec2001-05-22 20:40:22 +0000920
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000921 /* This is delicate. During the process of clearing the dict,
922 * decrefs can cause the dict to mutate. To avoid fatal confusion
923 * (voice of experience), we have to make the dict empty before
924 * clearing the slots, and never refer to anything via mp->xxx while
925 * clearing.
926 */
927 fill = mp->ma_fill;
928 if (table_is_malloced)
929 EMPTY_TO_MINSIZE(mp);
Tim Petersdea48ec2001-05-22 20:40:22 +0000930
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000931 else if (fill > 0) {
932 /* It's a small table with something that needs to be cleared.
933 * Afraid the only safe way is to copy the dict entries into
934 * another small table first.
935 */
936 memcpy(small_copy, table, sizeof(small_copy));
937 table = small_copy;
938 EMPTY_TO_MINSIZE(mp);
939 }
940 /* else it's a small table that's already empty */
Tim Petersdea48ec2001-05-22 20:40:22 +0000941
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000942 /* Now we can finally clear things. If C had refcounts, we could
943 * assert that the refcount on table is 1 now, i.e. that this function
944 * has unique access to it, so decref side-effects can't alter it.
945 */
946 for (ep = table; fill > 0; ++ep) {
Tim Petersdea48ec2001-05-22 20:40:22 +0000947#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000948 assert(i < n);
949 ++i;
Tim Petersdea48ec2001-05-22 20:40:22 +0000950#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000951 if (ep->me_key) {
952 --fill;
953 Py_DECREF(ep->me_key);
954 Py_XDECREF(ep->me_value);
955 }
Tim Petersdea48ec2001-05-22 20:40:22 +0000956#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000957 else
958 assert(ep->me_value == NULL);
Tim Petersdea48ec2001-05-22 20:40:22 +0000959#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000960 }
Tim Petersdea48ec2001-05-22 20:40:22 +0000961
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000962 if (table_is_malloced)
963 PyMem_DEL(table);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000964}
965
Tim Peters080c88b2003-02-15 03:01:11 +0000966/*
967 * Iterate over a dict. Use like so:
968 *
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000969 * Py_ssize_t i;
Tim Peters080c88b2003-02-15 03:01:11 +0000970 * PyObject *key, *value;
971 * i = 0; # important! i should not otherwise be changed by you
Neal Norwitz07323012003-02-15 14:45:12 +0000972 * while (PyDict_Next(yourdict, &i, &key, &value)) {
Tim Peters080c88b2003-02-15 03:01:11 +0000973 * Refer to borrowed references in key and value.
974 * }
975 *
976 * CAUTION: In general, it isn't safe to use PyDict_Next in a loop that
Tim Peters67830702001-03-21 19:23:56 +0000977 * mutates the dict. One exception: it is safe if the loop merely changes
978 * the values associated with the keys (but doesn't insert new keys or
979 * delete keys), via PyDict_SetItem().
980 */
Guido van Rossum25831651993-05-19 14:50:45 +0000981int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000982PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000983{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000984 register Py_ssize_t i;
985 register Py_ssize_t mask;
986 register PyDictEntry *ep;
Raymond Hettinger43442782004-03-17 21:55:03 +0000987
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000988 if (!PyDict_Check(op))
989 return 0;
990 i = *ppos;
991 if (i < 0)
992 return 0;
993 ep = ((PyDictObject *)op)->ma_table;
994 mask = ((PyDictObject *)op)->ma_mask;
995 while (i <= mask && ep[i].me_value == NULL)
996 i++;
997 *ppos = i+1;
998 if (i > mask)
999 return 0;
1000 if (pkey)
1001 *pkey = ep[i].me_key;
1002 if (pvalue)
1003 *pvalue = ep[i].me_value;
1004 return 1;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001005}
1006
Thomas Wouterscf297e42007-02-23 15:07:44 +00001007/* Internal version of PyDict_Next that returns a hash value in addition to the key and value.*/
1008int
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001009_PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue, Py_hash_t *phash)
Thomas Wouterscf297e42007-02-23 15:07:44 +00001010{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001011 register Py_ssize_t i;
1012 register Py_ssize_t mask;
1013 register PyDictEntry *ep;
Thomas Wouterscf297e42007-02-23 15:07:44 +00001014
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001015 if (!PyDict_Check(op))
1016 return 0;
1017 i = *ppos;
1018 if (i < 0)
1019 return 0;
1020 ep = ((PyDictObject *)op)->ma_table;
1021 mask = ((PyDictObject *)op)->ma_mask;
1022 while (i <= mask && ep[i].me_value == NULL)
1023 i++;
1024 *ppos = i+1;
1025 if (i > mask)
1026 return 0;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001027 *phash = ep[i].me_hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001028 if (pkey)
1029 *pkey = ep[i].me_key;
1030 if (pvalue)
1031 *pvalue = ep[i].me_value;
1032 return 1;
Thomas Wouterscf297e42007-02-23 15:07:44 +00001033}
1034
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001035/* Methods */
1036
1037static void
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001038dict_dealloc(register PyDictObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001039{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001040 register PyDictEntry *ep;
1041 Py_ssize_t fill = mp->ma_fill;
1042 PyObject_GC_UnTrack(mp);
1043 Py_TRASHCAN_SAFE_BEGIN(mp)
1044 for (ep = mp->ma_table; fill > 0; ep++) {
1045 if (ep->me_key) {
1046 --fill;
1047 Py_DECREF(ep->me_key);
1048 Py_XDECREF(ep->me_value);
1049 }
1050 }
1051 if (mp->ma_table != mp->ma_smalltable)
1052 PyMem_DEL(mp->ma_table);
1053 if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
1054 free_list[numfree++] = mp;
1055 else
1056 Py_TYPE(mp)->tp_free((PyObject *)mp);
1057 Py_TRASHCAN_SAFE_END(mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001058}
1059
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001060static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001061dict_repr(PyDictObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001062{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001063 Py_ssize_t i;
1064 PyObject *s, *temp, *colon = NULL;
1065 PyObject *pieces = NULL, *result = NULL;
1066 PyObject *key, *value;
Guido van Rossum255443b1998-04-10 22:47:14 +00001067
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001068 i = Py_ReprEnter((PyObject *)mp);
1069 if (i != 0) {
1070 return i > 0 ? PyUnicode_FromString("{...}") : NULL;
1071 }
Guido van Rossum255443b1998-04-10 22:47:14 +00001072
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001073 if (mp->ma_used == 0) {
1074 result = PyUnicode_FromString("{}");
1075 goto Done;
1076 }
Tim Petersa7259592001-06-16 05:11:17 +00001077
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001078 pieces = PyList_New(0);
1079 if (pieces == NULL)
1080 goto Done;
Tim Petersa7259592001-06-16 05:11:17 +00001081
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001082 colon = PyUnicode_FromString(": ");
1083 if (colon == NULL)
1084 goto Done;
Tim Petersa7259592001-06-16 05:11:17 +00001085
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001086 /* Do repr() on each key+value pair, and insert ": " between them.
1087 Note that repr may mutate the dict. */
1088 i = 0;
1089 while (PyDict_Next((PyObject *)mp, &i, &key, &value)) {
1090 int status;
1091 /* Prevent repr from deleting value during key format. */
1092 Py_INCREF(value);
1093 s = PyObject_Repr(key);
1094 PyUnicode_Append(&s, colon);
1095 PyUnicode_AppendAndDel(&s, PyObject_Repr(value));
1096 Py_DECREF(value);
1097 if (s == NULL)
1098 goto Done;
1099 status = PyList_Append(pieces, s);
1100 Py_DECREF(s); /* append created a new ref */
1101 if (status < 0)
1102 goto Done;
1103 }
Tim Petersa7259592001-06-16 05:11:17 +00001104
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001105 /* Add "{}" decorations to the first and last items. */
1106 assert(PyList_GET_SIZE(pieces) > 0);
1107 s = PyUnicode_FromString("{");
1108 if (s == NULL)
1109 goto Done;
1110 temp = PyList_GET_ITEM(pieces, 0);
1111 PyUnicode_AppendAndDel(&s, temp);
1112 PyList_SET_ITEM(pieces, 0, s);
1113 if (s == NULL)
1114 goto Done;
Tim Petersa7259592001-06-16 05:11:17 +00001115
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001116 s = PyUnicode_FromString("}");
1117 if (s == NULL)
1118 goto Done;
1119 temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
1120 PyUnicode_AppendAndDel(&temp, s);
1121 PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
1122 if (temp == NULL)
1123 goto Done;
Tim Petersa7259592001-06-16 05:11:17 +00001124
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001125 /* Paste them all together with ", " between. */
1126 s = PyUnicode_FromString(", ");
1127 if (s == NULL)
1128 goto Done;
1129 result = PyUnicode_Join(s, pieces);
1130 Py_DECREF(s);
Tim Petersa7259592001-06-16 05:11:17 +00001131
1132Done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001133 Py_XDECREF(pieces);
1134 Py_XDECREF(colon);
1135 Py_ReprLeave((PyObject *)mp);
1136 return result;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001137}
1138
Martin v. Löwis18e16552006-02-15 17:27:45 +00001139static Py_ssize_t
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001140dict_length(PyDictObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001141{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001142 return mp->ma_used;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001143}
1144
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001145static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001146dict_subscript(PyDictObject *mp, register PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001147{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001148 PyObject *v;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001149 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001150 PyDictEntry *ep;
1151 assert(mp->ma_table != NULL);
1152 if (!PyUnicode_CheckExact(key) ||
1153 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
1154 hash = PyObject_Hash(key);
1155 if (hash == -1)
1156 return NULL;
1157 }
1158 ep = (mp->ma_lookup)(mp, key, hash);
1159 if (ep == NULL)
1160 return NULL;
1161 v = ep->me_value;
1162 if (v == NULL) {
1163 if (!PyDict_CheckExact(mp)) {
1164 /* Look up __missing__ method if we're a subclass. */
1165 PyObject *missing, *res;
1166 static PyObject *missing_str = NULL;
1167 missing = _PyObject_LookupSpecial((PyObject *)mp,
1168 "__missing__",
1169 &missing_str);
1170 if (missing != NULL) {
1171 res = PyObject_CallFunctionObjArgs(missing,
1172 key, NULL);
1173 Py_DECREF(missing);
1174 return res;
1175 }
1176 else if (PyErr_Occurred())
1177 return NULL;
1178 }
1179 set_key_error(key);
1180 return NULL;
1181 }
1182 else
1183 Py_INCREF(v);
1184 return v;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001185}
1186
1187static int
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001188dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001189{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001190 if (w == NULL)
1191 return PyDict_DelItem((PyObject *)mp, v);
1192 else
1193 return PyDict_SetItem((PyObject *)mp, v, w);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001194}
1195
Guido van Rossuma9e7a811997-05-13 21:02:11 +00001196static PyMappingMethods dict_as_mapping = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001197 (lenfunc)dict_length, /*mp_length*/
1198 (binaryfunc)dict_subscript, /*mp_subscript*/
1199 (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001200};
1201
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001202static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001203dict_keys(register PyDictObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001204{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001205 register PyObject *v;
1206 register Py_ssize_t i, j;
1207 PyDictEntry *ep;
1208 Py_ssize_t mask, n;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001209
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001210 again:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001211 n = mp->ma_used;
1212 v = PyList_New(n);
1213 if (v == NULL)
1214 return NULL;
1215 if (n != mp->ma_used) {
1216 /* Durnit. The allocations caused the dict to resize.
1217 * Just start over, this shouldn't normally happen.
1218 */
1219 Py_DECREF(v);
1220 goto again;
1221 }
1222 ep = mp->ma_table;
1223 mask = mp->ma_mask;
1224 for (i = 0, j = 0; i <= mask; i++) {
1225 if (ep[i].me_value != NULL) {
1226 PyObject *key = ep[i].me_key;
1227 Py_INCREF(key);
1228 PyList_SET_ITEM(v, j, key);
1229 j++;
1230 }
1231 }
1232 assert(j == n);
1233 return v;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001234}
1235
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001236static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001237dict_values(register PyDictObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001238{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001239 register PyObject *v;
1240 register Py_ssize_t i, j;
1241 PyDictEntry *ep;
1242 Py_ssize_t mask, n;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001243
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001244 again:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001245 n = mp->ma_used;
1246 v = PyList_New(n);
1247 if (v == NULL)
1248 return NULL;
1249 if (n != mp->ma_used) {
1250 /* Durnit. The allocations caused the dict to resize.
1251 * Just start over, this shouldn't normally happen.
1252 */
1253 Py_DECREF(v);
1254 goto again;
1255 }
1256 ep = mp->ma_table;
1257 mask = mp->ma_mask;
1258 for (i = 0, j = 0; i <= mask; i++) {
1259 if (ep[i].me_value != NULL) {
1260 PyObject *value = ep[i].me_value;
1261 Py_INCREF(value);
1262 PyList_SET_ITEM(v, j, value);
1263 j++;
1264 }
1265 }
1266 assert(j == n);
1267 return v;
Guido van Rossum25831651993-05-19 14:50:45 +00001268}
1269
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001270static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001271dict_items(register PyDictObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001272{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001273 register PyObject *v;
1274 register Py_ssize_t i, j, n;
1275 Py_ssize_t mask;
1276 PyObject *item, *key, *value;
1277 PyDictEntry *ep;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001278
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001279 /* Preallocate the list of tuples, to avoid allocations during
1280 * the loop over the items, which could trigger GC, which
1281 * could resize the dict. :-(
1282 */
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001283 again:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001284 n = mp->ma_used;
1285 v = PyList_New(n);
1286 if (v == NULL)
1287 return NULL;
1288 for (i = 0; i < n; i++) {
1289 item = PyTuple_New(2);
1290 if (item == NULL) {
1291 Py_DECREF(v);
1292 return NULL;
1293 }
1294 PyList_SET_ITEM(v, i, item);
1295 }
1296 if (n != mp->ma_used) {
1297 /* Durnit. The allocations caused the dict to resize.
1298 * Just start over, this shouldn't normally happen.
1299 */
1300 Py_DECREF(v);
1301 goto again;
1302 }
1303 /* Nothing we do below makes any function calls. */
1304 ep = mp->ma_table;
1305 mask = mp->ma_mask;
1306 for (i = 0, j = 0; i <= mask; i++) {
1307 if ((value=ep[i].me_value) != NULL) {
1308 key = ep[i].me_key;
1309 item = PyList_GET_ITEM(v, j);
1310 Py_INCREF(key);
1311 PyTuple_SET_ITEM(item, 0, key);
1312 Py_INCREF(value);
1313 PyTuple_SET_ITEM(item, 1, value);
1314 j++;
1315 }
1316 }
1317 assert(j == n);
1318 return v;
Guido van Rossum25831651993-05-19 14:50:45 +00001319}
1320
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001321static PyObject *
Tim Petersbca1cbc2002-12-09 22:56:13 +00001322dict_fromkeys(PyObject *cls, PyObject *args)
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001323{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001324 PyObject *seq;
1325 PyObject *value = Py_None;
1326 PyObject *it; /* iter(seq) */
1327 PyObject *key;
1328 PyObject *d;
1329 int status;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001330
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001331 if (!PyArg_UnpackTuple(args, "fromkeys", 1, 2, &seq, &value))
1332 return NULL;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001333
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001334 d = PyObject_CallObject(cls, NULL);
1335 if (d == NULL)
1336 return NULL;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001337
Benjamin Peterson9892f522012-10-31 14:22:12 -04001338 if (PyDict_CheckExact(d) && ((PyDictObject *)d)->ma_used == 0) {
Benjamin Petersond1f2cb32012-10-31 14:05:55 -04001339 if (PyDict_CheckExact(seq)) {
1340 PyDictObject *mp = (PyDictObject *)d;
1341 PyObject *oldvalue;
1342 Py_ssize_t pos = 0;
1343 PyObject *key;
1344 Py_hash_t hash;
Guido van Rossum58da9312007-11-10 23:39:45 +00001345
Benjamin Petersond1f2cb32012-10-31 14:05:55 -04001346 if (dictresize(mp, Py_SIZE(seq))) {
Petri Lehtinena94200e2011-10-24 21:12:58 +03001347 Py_DECREF(d);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001348 return NULL;
Petri Lehtinena94200e2011-10-24 21:12:58 +03001349 }
Benjamin Petersond1f2cb32012-10-31 14:05:55 -04001350
1351 while (_PyDict_Next(seq, &pos, &key, &oldvalue, &hash)) {
1352 Py_INCREF(key);
1353 Py_INCREF(value);
1354 if (insertdict(mp, key, hash, value)) {
1355 Py_DECREF(d);
1356 return NULL;
1357 }
1358 }
1359 return d;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001360 }
Benjamin Petersond1f2cb32012-10-31 14:05:55 -04001361 if (PyAnySet_CheckExact(seq)) {
1362 PyDictObject *mp = (PyDictObject *)d;
1363 Py_ssize_t pos = 0;
1364 PyObject *key;
1365 Py_hash_t hash;
Guido van Rossum58da9312007-11-10 23:39:45 +00001366
Benjamin Petersond1f2cb32012-10-31 14:05:55 -04001367 if (dictresize(mp, PySet_GET_SIZE(seq))) {
Petri Lehtinena94200e2011-10-24 21:12:58 +03001368 Py_DECREF(d);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001369 return NULL;
Petri Lehtinena94200e2011-10-24 21:12:58 +03001370 }
Benjamin Petersond1f2cb32012-10-31 14:05:55 -04001371
1372 while (_PySet_NextEntry(seq, &pos, &key, &hash)) {
1373 Py_INCREF(key);
1374 Py_INCREF(value);
1375 if (insertdict(mp, key, hash, value)) {
1376 Py_DECREF(d);
1377 return NULL;
1378 }
1379 }
1380 return d;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001381 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001382 }
Guido van Rossumd8faa362007-04-27 19:54:29 +00001383
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001384 it = PyObject_GetIter(seq);
1385 if (it == NULL){
1386 Py_DECREF(d);
1387 return NULL;
1388 }
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001389
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001390 if (PyDict_CheckExact(d)) {
1391 while ((key = PyIter_Next(it)) != NULL) {
1392 status = PyDict_SetItem(d, key, value);
1393 Py_DECREF(key);
1394 if (status < 0)
1395 goto Fail;
1396 }
1397 } else {
1398 while ((key = PyIter_Next(it)) != NULL) {
1399 status = PyObject_SetItem(d, key, value);
1400 Py_DECREF(key);
1401 if (status < 0)
1402 goto Fail;
1403 }
1404 }
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001405
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001406 if (PyErr_Occurred())
1407 goto Fail;
1408 Py_DECREF(it);
1409 return d;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001410
1411Fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001412 Py_DECREF(it);
1413 Py_DECREF(d);
1414 return NULL;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001415}
1416
Raymond Hettinger31017ae2004-03-04 08:25:44 +00001417static int
1418dict_update_common(PyObject *self, PyObject *args, PyObject *kwds, char *methname)
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001419{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001420 PyObject *arg = NULL;
1421 int result = 0;
Raymond Hettinger31017ae2004-03-04 08:25:44 +00001422
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001423 if (!PyArg_UnpackTuple(args, methname, 0, 1, &arg))
1424 result = -1;
Raymond Hettinger31017ae2004-03-04 08:25:44 +00001425
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001426 else if (arg != NULL) {
1427 if (PyObject_HasAttrString(arg, "keys"))
1428 result = PyDict_Merge(self, arg, 1);
1429 else
1430 result = PyDict_MergeFromSeq2(self, arg, 1);
1431 }
1432 if (result == 0 && kwds != NULL) {
1433 if (PyArg_ValidateKeywordArguments(kwds))
1434 result = PyDict_Merge(self, kwds, 1);
1435 else
1436 result = -1;
1437 }
1438 return result;
Raymond Hettinger31017ae2004-03-04 08:25:44 +00001439}
1440
1441static PyObject *
1442dict_update(PyObject *self, PyObject *args, PyObject *kwds)
1443{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001444 if (dict_update_common(self, args, kwds, "update") != -1)
1445 Py_RETURN_NONE;
1446 return NULL;
Tim Peters6d6c1a32001-08-02 04:15:00 +00001447}
1448
Guido van Rossum05ac6de2001-08-10 20:28:28 +00001449/* Update unconditionally replaces existing items.
1450 Merge has a 3rd argument 'override'; if set, it acts like Update,
Tim Peters1fc240e2001-10-26 05:06:50 +00001451 otherwise it leaves existing items unchanged.
1452
1453 PyDict_{Update,Merge} update/merge from a mapping object.
1454
Tim Petersf582b822001-12-11 18:51:08 +00001455 PyDict_MergeFromSeq2 updates/merges from any iterable object
Tim Peters1fc240e2001-10-26 05:06:50 +00001456 producing iterable objects of length 2.
1457*/
1458
Tim Petersf582b822001-12-11 18:51:08 +00001459int
Tim Peters1fc240e2001-10-26 05:06:50 +00001460PyDict_MergeFromSeq2(PyObject *d, PyObject *seq2, int override)
1461{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001462 PyObject *it; /* iter(seq2) */
1463 Py_ssize_t i; /* index into seq2 of current element */
1464 PyObject *item; /* seq2[i] */
1465 PyObject *fast; /* item as a 2-tuple or 2-list */
Tim Peters1fc240e2001-10-26 05:06:50 +00001466
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001467 assert(d != NULL);
1468 assert(PyDict_Check(d));
1469 assert(seq2 != NULL);
Tim Peters1fc240e2001-10-26 05:06:50 +00001470
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001471 it = PyObject_GetIter(seq2);
1472 if (it == NULL)
1473 return -1;
Tim Peters1fc240e2001-10-26 05:06:50 +00001474
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001475 for (i = 0; ; ++i) {
1476 PyObject *key, *value;
1477 Py_ssize_t n;
Tim Peters1fc240e2001-10-26 05:06:50 +00001478
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001479 fast = NULL;
1480 item = PyIter_Next(it);
1481 if (item == NULL) {
1482 if (PyErr_Occurred())
1483 goto Fail;
1484 break;
1485 }
Tim Peters1fc240e2001-10-26 05:06:50 +00001486
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001487 /* Convert item to sequence, and verify length 2. */
1488 fast = PySequence_Fast(item, "");
1489 if (fast == NULL) {
1490 if (PyErr_ExceptionMatches(PyExc_TypeError))
1491 PyErr_Format(PyExc_TypeError,
1492 "cannot convert dictionary update "
1493 "sequence element #%zd to a sequence",
1494 i);
1495 goto Fail;
1496 }
1497 n = PySequence_Fast_GET_SIZE(fast);
1498 if (n != 2) {
1499 PyErr_Format(PyExc_ValueError,
1500 "dictionary update sequence element #%zd "
1501 "has length %zd; 2 is required",
1502 i, n);
1503 goto Fail;
1504 }
Tim Peters1fc240e2001-10-26 05:06:50 +00001505
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001506 /* Update/merge with this (key, value) pair. */
1507 key = PySequence_Fast_GET_ITEM(fast, 0);
1508 value = PySequence_Fast_GET_ITEM(fast, 1);
1509 if (override || PyDict_GetItem(d, key) == NULL) {
1510 int status = PyDict_SetItem(d, key, value);
1511 if (status < 0)
1512 goto Fail;
1513 }
1514 Py_DECREF(fast);
1515 Py_DECREF(item);
1516 }
Tim Peters1fc240e2001-10-26 05:06:50 +00001517
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001518 i = 0;
1519 goto Return;
Tim Peters1fc240e2001-10-26 05:06:50 +00001520Fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001521 Py_XDECREF(item);
1522 Py_XDECREF(fast);
1523 i = -1;
Tim Peters1fc240e2001-10-26 05:06:50 +00001524Return:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001525 Py_DECREF(it);
1526 return Py_SAFE_DOWNCAST(i, Py_ssize_t, int);
Tim Peters1fc240e2001-10-26 05:06:50 +00001527}
1528
Tim Peters6d6c1a32001-08-02 04:15:00 +00001529int
1530PyDict_Update(PyObject *a, PyObject *b)
1531{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001532 return PyDict_Merge(a, b, 1);
Guido van Rossum05ac6de2001-08-10 20:28:28 +00001533}
1534
1535int
1536PyDict_Merge(PyObject *a, PyObject *b, int override)
1537{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001538 register PyDictObject *mp, *other;
1539 register Py_ssize_t i;
1540 PyDictEntry *entry;
Tim Peters6d6c1a32001-08-02 04:15:00 +00001541
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001542 /* We accept for the argument either a concrete dictionary object,
1543 * or an abstract "mapping" object. For the former, we can do
1544 * things quite efficiently. For the latter, we only require that
1545 * PyMapping_Keys() and PyObject_GetItem() be supported.
1546 */
1547 if (a == NULL || !PyDict_Check(a) || b == NULL) {
1548 PyErr_BadInternalCall();
1549 return -1;
1550 }
1551 mp = (PyDictObject*)a;
1552 if (PyDict_Check(b)) {
1553 other = (PyDictObject*)b;
1554 if (other == mp || other->ma_used == 0)
1555 /* a.update(a) or a.update({}); nothing to do */
1556 return 0;
1557 if (mp->ma_used == 0)
1558 /* Since the target dict is empty, PyDict_GetItem()
1559 * always returns NULL. Setting override to 1
1560 * skips the unnecessary test.
1561 */
1562 override = 1;
1563 /* Do one big resize at the start, rather than
1564 * incrementally resizing as we insert new items. Expect
1565 * that there will be no (or few) overlapping keys.
1566 */
1567 if ((mp->ma_fill + other->ma_used)*3 >= (mp->ma_mask+1)*2) {
1568 if (dictresize(mp, (mp->ma_used + other->ma_used)*2) != 0)
1569 return -1;
1570 }
1571 for (i = 0; i <= other->ma_mask; i++) {
1572 entry = &other->ma_table[i];
1573 if (entry->me_value != NULL &&
1574 (override ||
1575 PyDict_GetItem(a, entry->me_key) == NULL)) {
1576 Py_INCREF(entry->me_key);
1577 Py_INCREF(entry->me_value);
1578 if (insertdict(mp, entry->me_key,
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001579 entry->me_hash,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001580 entry->me_value) != 0)
1581 return -1;
1582 }
1583 }
1584 }
1585 else {
1586 /* Do it the generic, slower way */
1587 PyObject *keys = PyMapping_Keys(b);
1588 PyObject *iter;
1589 PyObject *key, *value;
1590 int status;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001591
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001592 if (keys == NULL)
1593 /* Docstring says this is equivalent to E.keys() so
1594 * if E doesn't have a .keys() method we want
1595 * AttributeError to percolate up. Might as well
1596 * do the same for any other error.
1597 */
1598 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001599
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001600 iter = PyObject_GetIter(keys);
1601 Py_DECREF(keys);
1602 if (iter == NULL)
1603 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001604
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001605 for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) {
1606 if (!override && PyDict_GetItem(a, key) != NULL) {
1607 Py_DECREF(key);
1608 continue;
1609 }
1610 value = PyObject_GetItem(b, key);
1611 if (value == NULL) {
1612 Py_DECREF(iter);
1613 Py_DECREF(key);
1614 return -1;
1615 }
1616 status = PyDict_SetItem(a, key, value);
1617 Py_DECREF(key);
1618 Py_DECREF(value);
1619 if (status < 0) {
1620 Py_DECREF(iter);
1621 return -1;
1622 }
1623 }
1624 Py_DECREF(iter);
1625 if (PyErr_Occurred())
1626 /* Iterator completed, via error */
1627 return -1;
1628 }
1629 return 0;
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001630}
1631
1632static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001633dict_copy(register PyDictObject *mp)
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001634{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001635 return PyDict_Copy((PyObject*)mp);
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001636}
1637
1638PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001639PyDict_Copy(PyObject *o)
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001640{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001641 PyObject *copy;
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001642
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001643 if (o == NULL || !PyDict_Check(o)) {
1644 PyErr_BadInternalCall();
1645 return NULL;
1646 }
1647 copy = PyDict_New();
1648 if (copy == NULL)
1649 return NULL;
1650 if (PyDict_Merge(copy, o, 1) == 0)
1651 return copy;
1652 Py_DECREF(copy);
1653 return NULL;
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001654}
1655
Martin v. Löwis18e16552006-02-15 17:27:45 +00001656Py_ssize_t
Tim Peters1f5871e2000-07-04 17:44:48 +00001657PyDict_Size(PyObject *mp)
Guido van Rossum4199fac1993-11-05 10:18:44 +00001658{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001659 if (mp == NULL || !PyDict_Check(mp)) {
1660 PyErr_BadInternalCall();
1661 return -1;
1662 }
1663 return ((PyDictObject *)mp)->ma_used;
Guido van Rossum4199fac1993-11-05 10:18:44 +00001664}
1665
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001666PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001667PyDict_Keys(PyObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001668{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001669 if (mp == NULL || !PyDict_Check(mp)) {
1670 PyErr_BadInternalCall();
1671 return NULL;
1672 }
1673 return dict_keys((PyDictObject *)mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001674}
1675
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001676PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001677PyDict_Values(PyObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001678{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001679 if (mp == NULL || !PyDict_Check(mp)) {
1680 PyErr_BadInternalCall();
1681 return NULL;
1682 }
1683 return dict_values((PyDictObject *)mp);
Guido van Rossum25831651993-05-19 14:50:45 +00001684}
1685
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001686PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001687PyDict_Items(PyObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001688{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001689 if (mp == NULL || !PyDict_Check(mp)) {
1690 PyErr_BadInternalCall();
1691 return NULL;
1692 }
1693 return dict_items((PyDictObject *)mp);
Guido van Rossum25831651993-05-19 14:50:45 +00001694}
1695
Tim Peterse63415e2001-05-08 04:38:29 +00001696/* Return 1 if dicts equal, 0 if not, -1 if error.
1697 * Gets out as soon as any difference is detected.
1698 * Uses only Py_EQ comparison.
1699 */
1700static int
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001701dict_equal(PyDictObject *a, PyDictObject *b)
Tim Peterse63415e2001-05-08 04:38:29 +00001702{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001703 Py_ssize_t i;
Tim Peterse63415e2001-05-08 04:38:29 +00001704
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001705 if (a->ma_used != b->ma_used)
1706 /* can't be equal if # of entries differ */
1707 return 0;
Tim Peterseb28ef22001-06-02 05:27:19 +00001708
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001709 /* Same # of entries -- check all of 'em. Exit early on any diff. */
1710 for (i = 0; i <= a->ma_mask; i++) {
1711 PyObject *aval = a->ma_table[i].me_value;
1712 if (aval != NULL) {
1713 int cmp;
1714 PyObject *bval;
1715 PyObject *key = a->ma_table[i].me_key;
1716 /* temporarily bump aval's refcount to ensure it stays
1717 alive until we're done with it */
1718 Py_INCREF(aval);
1719 /* ditto for key */
1720 Py_INCREF(key);
1721 bval = PyDict_GetItemWithError((PyObject *)b, key);
1722 Py_DECREF(key);
1723 if (bval == NULL) {
1724 Py_DECREF(aval);
1725 if (PyErr_Occurred())
1726 return -1;
1727 return 0;
1728 }
1729 cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
1730 Py_DECREF(aval);
1731 if (cmp <= 0) /* error or not equal */
1732 return cmp;
1733 }
1734 }
1735 return 1;
Tim Peterse63415e2001-05-08 04:38:29 +00001736 }
1737
1738static PyObject *
1739dict_richcompare(PyObject *v, PyObject *w, int op)
1740{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001741 int cmp;
1742 PyObject *res;
Tim Peterse63415e2001-05-08 04:38:29 +00001743
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001744 if (!PyDict_Check(v) || !PyDict_Check(w)) {
1745 res = Py_NotImplemented;
1746 }
1747 else if (op == Py_EQ || op == Py_NE) {
1748 cmp = dict_equal((PyDictObject *)v, (PyDictObject *)w);
1749 if (cmp < 0)
1750 return NULL;
1751 res = (cmp == (op == Py_EQ)) ? Py_True : Py_False;
1752 }
1753 else
1754 res = Py_NotImplemented;
1755 Py_INCREF(res);
1756 return res;
Tim Peterse63415e2001-05-08 04:38:29 +00001757 }
1758
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001759static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001760dict_contains(register PyDictObject *mp, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001761{
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001762 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001763 PyDictEntry *ep;
Thomas Wouters4d70c3d2006-06-08 14:42:34 +00001764
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001765 if (!PyUnicode_CheckExact(key) ||
1766 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
1767 hash = PyObject_Hash(key);
1768 if (hash == -1)
1769 return NULL;
1770 }
1771 ep = (mp->ma_lookup)(mp, key, hash);
1772 if (ep == NULL)
1773 return NULL;
1774 return PyBool_FromLong(ep->me_value != NULL);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001775}
1776
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001777static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001778dict_get(register PyDictObject *mp, PyObject *args)
Barry Warsawc38c5da1997-10-06 17:49:20 +00001779{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001780 PyObject *key;
1781 PyObject *failobj = Py_None;
1782 PyObject *val = NULL;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001783 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001784 PyDictEntry *ep;
Barry Warsawc38c5da1997-10-06 17:49:20 +00001785
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001786 if (!PyArg_UnpackTuple(args, "get", 1, 2, &key, &failobj))
1787 return NULL;
Barry Warsawc38c5da1997-10-06 17:49:20 +00001788
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001789 if (!PyUnicode_CheckExact(key) ||
1790 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
1791 hash = PyObject_Hash(key);
1792 if (hash == -1)
1793 return NULL;
1794 }
1795 ep = (mp->ma_lookup)(mp, key, hash);
1796 if (ep == NULL)
1797 return NULL;
1798 val = ep->me_value;
1799 if (val == NULL)
1800 val = failobj;
1801 Py_INCREF(val);
1802 return val;
Barry Warsawc38c5da1997-10-06 17:49:20 +00001803}
1804
1805
1806static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001807dict_setdefault(register PyDictObject *mp, PyObject *args)
Guido van Rossum164452c2000-08-08 16:12:54 +00001808{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001809 PyObject *key;
1810 PyObject *failobj = Py_None;
1811 PyObject *val = NULL;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001812 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001813 PyDictEntry *ep;
Guido van Rossum164452c2000-08-08 16:12:54 +00001814
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001815 if (!PyArg_UnpackTuple(args, "setdefault", 1, 2, &key, &failobj))
1816 return NULL;
Guido van Rossum164452c2000-08-08 16:12:54 +00001817
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001818 if (!PyUnicode_CheckExact(key) ||
1819 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
1820 hash = PyObject_Hash(key);
1821 if (hash == -1)
1822 return NULL;
1823 }
1824 ep = (mp->ma_lookup)(mp, key, hash);
1825 if (ep == NULL)
1826 return NULL;
1827 val = ep->me_value;
1828 if (val == NULL) {
Antoine Pitroue965d972012-02-27 00:45:12 +01001829 if (dict_set_item_by_hash_or_entry((PyObject*)mp, key, hash, ep,
1830 failobj) == 0)
1831 val = failobj;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001832 }
1833 Py_XINCREF(val);
1834 return val;
Guido van Rossum164452c2000-08-08 16:12:54 +00001835}
1836
1837
1838static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001839dict_clear(register PyDictObject *mp)
Guido van Rossumfb8f1ca1997-03-21 21:55:12 +00001840{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001841 PyDict_Clear((PyObject *)mp);
1842 Py_RETURN_NONE;
Guido van Rossumfb8f1ca1997-03-21 21:55:12 +00001843}
1844
Guido van Rossumba6ab842000-12-12 22:02:18 +00001845static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001846dict_pop(PyDictObject *mp, PyObject *args)
Guido van Rossume027d982002-04-12 15:11:59 +00001847{
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001848 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001849 PyDictEntry *ep;
1850 PyObject *old_value, *old_key;
1851 PyObject *key, *deflt = NULL;
Guido van Rossume027d982002-04-12 15:11:59 +00001852
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001853 if(!PyArg_UnpackTuple(args, "pop", 1, 2, &key, &deflt))
1854 return NULL;
1855 if (mp->ma_used == 0) {
1856 if (deflt) {
1857 Py_INCREF(deflt);
1858 return deflt;
1859 }
Raymond Hettingerdd421542010-10-30 08:10:29 +00001860 set_key_error(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001861 return NULL;
1862 }
1863 if (!PyUnicode_CheckExact(key) ||
1864 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
1865 hash = PyObject_Hash(key);
1866 if (hash == -1)
1867 return NULL;
1868 }
1869 ep = (mp->ma_lookup)(mp, key, hash);
1870 if (ep == NULL)
1871 return NULL;
1872 if (ep->me_value == NULL) {
1873 if (deflt) {
1874 Py_INCREF(deflt);
1875 return deflt;
1876 }
1877 set_key_error(key);
1878 return NULL;
1879 }
1880 old_key = ep->me_key;
1881 Py_INCREF(dummy);
1882 ep->me_key = dummy;
1883 old_value = ep->me_value;
1884 ep->me_value = NULL;
1885 mp->ma_used--;
1886 Py_DECREF(old_key);
1887 return old_value;
Guido van Rossume027d982002-04-12 15:11:59 +00001888}
1889
1890static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001891dict_popitem(PyDictObject *mp)
Guido van Rossumba6ab842000-12-12 22:02:18 +00001892{
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001893 Py_hash_t i = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001894 PyDictEntry *ep;
1895 PyObject *res;
Guido van Rossumba6ab842000-12-12 22:02:18 +00001896
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001897 /* Allocate the result tuple before checking the size. Believe it
1898 * or not, this allocation could trigger a garbage collection which
1899 * could empty the dict, so if we checked the size first and that
1900 * happened, the result would be an infinite loop (searching for an
1901 * entry that no longer exists). Note that the usual popitem()
1902 * idiom is "while d: k, v = d.popitem()". so needing to throw the
1903 * tuple away if the dict *is* empty isn't a significant
1904 * inefficiency -- possible, but unlikely in practice.
1905 */
1906 res = PyTuple_New(2);
1907 if (res == NULL)
1908 return NULL;
1909 if (mp->ma_used == 0) {
1910 Py_DECREF(res);
1911 PyErr_SetString(PyExc_KeyError,
1912 "popitem(): dictionary is empty");
1913 return NULL;
1914 }
1915 /* Set ep to "the first" dict entry with a value. We abuse the hash
1916 * field of slot 0 to hold a search finger:
1917 * If slot 0 has a value, use slot 0.
1918 * Else slot 0 is being used to hold a search finger,
1919 * and we use its hash value as the first index to look.
1920 */
1921 ep = &mp->ma_table[0];
1922 if (ep->me_value == NULL) {
1923 i = ep->me_hash;
1924 /* The hash field may be a real hash value, or it may be a
1925 * legit search finger, or it may be a once-legit search
1926 * finger that's out of bounds now because it wrapped around
1927 * or the table shrunk -- simply make sure it's in bounds now.
1928 */
1929 if (i > mp->ma_mask || i < 1)
1930 i = 1; /* skip slot 0 */
1931 while ((ep = &mp->ma_table[i])->me_value == NULL) {
1932 i++;
1933 if (i > mp->ma_mask)
1934 i = 1;
1935 }
1936 }
1937 PyTuple_SET_ITEM(res, 0, ep->me_key);
1938 PyTuple_SET_ITEM(res, 1, ep->me_value);
1939 Py_INCREF(dummy);
1940 ep->me_key = dummy;
1941 ep->me_value = NULL;
1942 mp->ma_used--;
1943 assert(mp->ma_table[0].me_value == NULL);
1944 mp->ma_table[0].me_hash = i + 1; /* next place to start */
1945 return res;
Guido van Rossumba6ab842000-12-12 22:02:18 +00001946}
1947
Jeremy Hylton8caad492000-06-23 14:18:11 +00001948static int
1949dict_traverse(PyObject *op, visitproc visit, void *arg)
1950{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001951 Py_ssize_t i = 0;
1952 PyObject *pk;
1953 PyObject *pv;
Jeremy Hylton8caad492000-06-23 14:18:11 +00001954
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001955 while (PyDict_Next(op, &i, &pk, &pv)) {
1956 Py_VISIT(pk);
1957 Py_VISIT(pv);
1958 }
1959 return 0;
Jeremy Hylton8caad492000-06-23 14:18:11 +00001960}
1961
1962static int
1963dict_tp_clear(PyObject *op)
1964{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001965 PyDict_Clear(op);
1966 return 0;
Jeremy Hylton8caad492000-06-23 14:18:11 +00001967}
1968
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001969static PyObject *dictiter_new(PyDictObject *, PyTypeObject *);
Guido van Rossum09e563a2001-05-01 12:10:21 +00001970
Martin v. Löwis00709aa2008-06-04 14:18:43 +00001971static PyObject *
1972dict_sizeof(PyDictObject *mp)
1973{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001974 Py_ssize_t res;
Martin v. Löwis00709aa2008-06-04 14:18:43 +00001975
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001976 res = sizeof(PyDictObject);
1977 if (mp->ma_table != mp->ma_smalltable)
1978 res = res + (mp->ma_mask + 1) * sizeof(PyDictEntry);
1979 return PyLong_FromSsize_t(res);
Martin v. Löwis00709aa2008-06-04 14:18:43 +00001980}
1981
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001982PyDoc_STRVAR(contains__doc__,
1983"D.__contains__(k) -> True if D has a key k, else False");
1984
1985PyDoc_STRVAR(getitem__doc__, "x.__getitem__(y) <==> x[y]");
1986
Martin v. Löwis00709aa2008-06-04 14:18:43 +00001987PyDoc_STRVAR(sizeof__doc__,
1988"D.__sizeof__() -> size of D in memory, in bytes");
1989
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001990PyDoc_STRVAR(get__doc__,
Guido van Rossumefae8862002-09-04 11:29:45 +00001991"D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.");
Tim Petersf7f88b12000-12-13 23:18:45 +00001992
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001993PyDoc_STRVAR(setdefault_doc__,
Guido van Rossumefae8862002-09-04 11:29:45 +00001994"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 +00001995
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001996PyDoc_STRVAR(pop__doc__,
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00001997"D.pop(k[,d]) -> v, remove specified key and return the corresponding value.\n\
Raymond Hettingera3e1e4c2003-03-06 23:54:28 +00001998If key is not found, d is returned if given, otherwise KeyError is raised");
Guido van Rossume027d982002-04-12 15:11:59 +00001999
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002000PyDoc_STRVAR(popitem__doc__,
Tim Petersf7f88b12000-12-13 23:18:45 +00002001"D.popitem() -> (k, v), remove and return some (key, value) pair as a\n\
Benjamin Petersonf10a79a2008-10-11 00:49:57 +000020022-tuple; but raise KeyError if D is empty.");
Tim Petersf7f88b12000-12-13 23:18:45 +00002003
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002004PyDoc_STRVAR(update__doc__,
Georg Brandlac0675c2011-12-18 19:30:55 +01002005"D.update([E, ]**F) -> None. Update D from dict/iterable E and F.\n"
2006"If E present and has a .keys() method, does: for k in E: D[k] = E[k]\n\
2007If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v\n\
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00002008In either case, this is followed by: for k in F: D[k] = F[k]");
Tim Petersf7f88b12000-12-13 23:18:45 +00002009
Raymond Hettingere33d3df2002-11-27 07:29:33 +00002010PyDoc_STRVAR(fromkeys__doc__,
2011"dict.fromkeys(S[,v]) -> New dict with keys from S and values equal to v.\n\
2012v defaults to None.");
2013
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002014PyDoc_STRVAR(clear__doc__,
2015"D.clear() -> None. Remove all items from D.");
Tim Petersf7f88b12000-12-13 23:18:45 +00002016
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002017PyDoc_STRVAR(copy__doc__,
2018"D.copy() -> a shallow copy of D");
Tim Petersf7f88b12000-12-13 23:18:45 +00002019
Guido van Rossumb90c8482007-02-10 01:11:45 +00002020/* Forward */
2021static PyObject *dictkeys_new(PyObject *);
2022static PyObject *dictitems_new(PyObject *);
2023static PyObject *dictvalues_new(PyObject *);
2024
Guido van Rossum45c85d12007-07-27 16:31:40 +00002025PyDoc_STRVAR(keys__doc__,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002026 "D.keys() -> a set-like object providing a view on D's keys");
Guido van Rossum45c85d12007-07-27 16:31:40 +00002027PyDoc_STRVAR(items__doc__,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002028 "D.items() -> a set-like object providing a view on D's items");
Guido van Rossum45c85d12007-07-27 16:31:40 +00002029PyDoc_STRVAR(values__doc__,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002030 "D.values() -> an object providing a view on D's values");
Guido van Rossumb90c8482007-02-10 01:11:45 +00002031
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002032static PyMethodDef mapp_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002033 {"__contains__",(PyCFunction)dict_contains, METH_O | METH_COEXIST,
2034 contains__doc__},
2035 {"__getitem__", (PyCFunction)dict_subscript, METH_O | METH_COEXIST,
2036 getitem__doc__},
2037 {"__sizeof__", (PyCFunction)dict_sizeof, METH_NOARGS,
2038 sizeof__doc__},
2039 {"get", (PyCFunction)dict_get, METH_VARARGS,
2040 get__doc__},
2041 {"setdefault", (PyCFunction)dict_setdefault, METH_VARARGS,
2042 setdefault_doc__},
2043 {"pop", (PyCFunction)dict_pop, METH_VARARGS,
2044 pop__doc__},
2045 {"popitem", (PyCFunction)dict_popitem, METH_NOARGS,
2046 popitem__doc__},
2047 {"keys", (PyCFunction)dictkeys_new, METH_NOARGS,
2048 keys__doc__},
2049 {"items", (PyCFunction)dictitems_new, METH_NOARGS,
2050 items__doc__},
2051 {"values", (PyCFunction)dictvalues_new, METH_NOARGS,
2052 values__doc__},
2053 {"update", (PyCFunction)dict_update, METH_VARARGS | METH_KEYWORDS,
2054 update__doc__},
2055 {"fromkeys", (PyCFunction)dict_fromkeys, METH_VARARGS | METH_CLASS,
2056 fromkeys__doc__},
2057 {"clear", (PyCFunction)dict_clear, METH_NOARGS,
2058 clear__doc__},
2059 {"copy", (PyCFunction)dict_copy, METH_NOARGS,
2060 copy__doc__},
2061 {NULL, NULL} /* sentinel */
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002062};
2063
Thomas Wouters4d70c3d2006-06-08 14:42:34 +00002064/* Return 1 if `key` is in dict `op`, 0 if not, and -1 on error. */
Raymond Hettingerbc0f2ab2003-11-25 21:12:14 +00002065int
2066PyDict_Contains(PyObject *op, PyObject *key)
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002067{
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002068 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002069 PyDictObject *mp = (PyDictObject *)op;
2070 PyDictEntry *ep;
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002071
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002072 if (!PyUnicode_CheckExact(key) ||
2073 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
2074 hash = PyObject_Hash(key);
2075 if (hash == -1)
2076 return -1;
2077 }
2078 ep = (mp->ma_lookup)(mp, key, hash);
2079 return ep == NULL ? -1 : (ep->me_value != NULL);
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002080}
2081
Thomas Wouterscf297e42007-02-23 15:07:44 +00002082/* Internal version of PyDict_Contains used when the hash value is already known */
2083int
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002084_PyDict_Contains(PyObject *op, PyObject *key, Py_hash_t hash)
Thomas Wouterscf297e42007-02-23 15:07:44 +00002085{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002086 PyDictObject *mp = (PyDictObject *)op;
2087 PyDictEntry *ep;
Thomas Wouterscf297e42007-02-23 15:07:44 +00002088
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002089 ep = (mp->ma_lookup)(mp, key, hash);
2090 return ep == NULL ? -1 : (ep->me_value != NULL);
Thomas Wouterscf297e42007-02-23 15:07:44 +00002091}
2092
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002093/* Hack to implement "key in dict" */
2094static PySequenceMethods dict_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002095 0, /* sq_length */
2096 0, /* sq_concat */
2097 0, /* sq_repeat */
2098 0, /* sq_item */
2099 0, /* sq_slice */
2100 0, /* sq_ass_item */
2101 0, /* sq_ass_slice */
2102 PyDict_Contains, /* sq_contains */
2103 0, /* sq_inplace_concat */
2104 0, /* sq_inplace_repeat */
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002105};
2106
Guido van Rossum09e563a2001-05-01 12:10:21 +00002107static PyObject *
Tim Peters6d6c1a32001-08-02 04:15:00 +00002108dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2109{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002110 PyObject *self;
Tim Peters6d6c1a32001-08-02 04:15:00 +00002111
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002112 assert(type != NULL && type->tp_alloc != NULL);
2113 self = type->tp_alloc(type, 0);
2114 if (self != NULL) {
2115 PyDictObject *d = (PyDictObject *)self;
2116 /* It's guaranteed that tp->alloc zeroed out the struct. */
2117 assert(d->ma_table == NULL && d->ma_fill == 0 && d->ma_used == 0);
2118 INIT_NONZERO_DICT_SLOTS(d);
2119 d->ma_lookup = lookdict_unicode;
Ezio Melotti13925002011-03-16 11:05:33 +02002120 /* The object has been implicitly tracked by tp_alloc */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002121 if (type == &PyDict_Type)
2122 _PyObject_GC_UNTRACK(d);
Tim Peters6d6c1a32001-08-02 04:15:00 +00002123#ifdef SHOW_CONVERSION_COUNTS
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002124 ++created;
Tim Peters6d6c1a32001-08-02 04:15:00 +00002125#endif
Antoine Pitrou3a652b12009-03-23 18:52:06 +00002126#ifdef SHOW_TRACK_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002127 if (_PyObject_GC_IS_TRACKED(d))
2128 count_tracked++;
2129 else
2130 count_untracked++;
Antoine Pitrou3a652b12009-03-23 18:52:06 +00002131#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002132 }
2133 return self;
Tim Peters6d6c1a32001-08-02 04:15:00 +00002134}
2135
Tim Peters25786c02001-09-02 08:22:48 +00002136static int
2137dict_init(PyObject *self, PyObject *args, PyObject *kwds)
2138{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002139 return dict_update_common(self, args, kwds, "dict");
Tim Peters25786c02001-09-02 08:22:48 +00002140}
2141
Tim Peters6d6c1a32001-08-02 04:15:00 +00002142static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00002143dict_iter(PyDictObject *dict)
Guido van Rossum09e563a2001-05-01 12:10:21 +00002144{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002145 return dictiter_new(dict, &PyDictIterKey_Type);
Guido van Rossum09e563a2001-05-01 12:10:21 +00002146}
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002147
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002148PyDoc_STRVAR(dictionary_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002149"dict() -> new empty dictionary\n"
Tim Petersa427a2b2001-10-29 22:25:45 +00002150"dict(mapping) -> new dictionary initialized from a mapping object's\n"
Ezio Melotti7f807b72010-03-01 04:08:34 +00002151" (key, value) pairs\n"
2152"dict(iterable) -> new dictionary initialized as if via:\n"
Tim Peters4d859532001-10-27 18:27:48 +00002153" d = {}\n"
Ezio Melotti7f807b72010-03-01 04:08:34 +00002154" for k, v in iterable:\n"
Just van Rossuma797d812002-11-23 09:45:04 +00002155" d[k] = v\n"
2156"dict(**kwargs) -> new dictionary initialized with the name=value pairs\n"
2157" in the keyword argument list. For example: dict(one=1, two=2)");
Tim Peters25786c02001-09-02 08:22:48 +00002158
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002159PyTypeObject PyDict_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002160 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2161 "dict",
2162 sizeof(PyDictObject),
2163 0,
2164 (destructor)dict_dealloc, /* tp_dealloc */
2165 0, /* tp_print */
2166 0, /* tp_getattr */
2167 0, /* tp_setattr */
2168 0, /* tp_reserved */
2169 (reprfunc)dict_repr, /* tp_repr */
2170 0, /* tp_as_number */
2171 &dict_as_sequence, /* tp_as_sequence */
2172 &dict_as_mapping, /* tp_as_mapping */
Georg Brandl00da4e02010-10-18 07:32:48 +00002173 PyObject_HashNotImplemented, /* tp_hash */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002174 0, /* tp_call */
2175 0, /* tp_str */
2176 PyObject_GenericGetAttr, /* tp_getattro */
2177 0, /* tp_setattro */
2178 0, /* tp_as_buffer */
2179 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2180 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_DICT_SUBCLASS, /* tp_flags */
2181 dictionary_doc, /* tp_doc */
2182 dict_traverse, /* tp_traverse */
2183 dict_tp_clear, /* tp_clear */
2184 dict_richcompare, /* tp_richcompare */
2185 0, /* tp_weaklistoffset */
2186 (getiterfunc)dict_iter, /* tp_iter */
2187 0, /* tp_iternext */
2188 mapp_methods, /* tp_methods */
2189 0, /* tp_members */
2190 0, /* tp_getset */
2191 0, /* tp_base */
2192 0, /* tp_dict */
2193 0, /* tp_descr_get */
2194 0, /* tp_descr_set */
2195 0, /* tp_dictoffset */
2196 dict_init, /* tp_init */
2197 PyType_GenericAlloc, /* tp_alloc */
2198 dict_new, /* tp_new */
2199 PyObject_GC_Del, /* tp_free */
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002200};
2201
Guido van Rossum3cca2451997-05-16 14:23:33 +00002202/* For backward compatibility with old dictionary interface */
2203
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002204PyObject *
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +00002205PyDict_GetItemString(PyObject *v, const char *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002206{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002207 PyObject *kv, *rv;
2208 kv = PyUnicode_FromString(key);
2209 if (kv == NULL)
2210 return NULL;
2211 rv = PyDict_GetItem(v, kv);
2212 Py_DECREF(kv);
2213 return rv;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002214}
2215
2216int
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +00002217PyDict_SetItemString(PyObject *v, const char *key, PyObject *item)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002218{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002219 PyObject *kv;
2220 int err;
2221 kv = PyUnicode_FromString(key);
2222 if (kv == NULL)
2223 return -1;
2224 PyUnicode_InternInPlace(&kv); /* XXX Should we really? */
2225 err = PyDict_SetItem(v, kv, item);
2226 Py_DECREF(kv);
2227 return err;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002228}
2229
2230int
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +00002231PyDict_DelItemString(PyObject *v, const char *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002232{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002233 PyObject *kv;
2234 int err;
2235 kv = PyUnicode_FromString(key);
2236 if (kv == NULL)
2237 return -1;
2238 err = PyDict_DelItem(v, kv);
2239 Py_DECREF(kv);
2240 return err;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002241}
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002242
Raymond Hettinger019a1482004-03-18 02:41:19 +00002243/* Dictionary iterator types */
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002244
2245typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002246 PyObject_HEAD
2247 PyDictObject *di_dict; /* Set to NULL when iterator is exhausted */
2248 Py_ssize_t di_used;
2249 Py_ssize_t di_pos;
2250 PyObject* di_result; /* reusable result tuple for iteritems */
2251 Py_ssize_t len;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002252} dictiterobject;
2253
2254static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00002255dictiter_new(PyDictObject *dict, PyTypeObject *itertype)
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002256{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002257 dictiterobject *di;
2258 di = PyObject_GC_New(dictiterobject, itertype);
2259 if (di == NULL)
2260 return NULL;
2261 Py_INCREF(dict);
2262 di->di_dict = dict;
2263 di->di_used = dict->ma_used;
2264 di->di_pos = 0;
2265 di->len = dict->ma_used;
2266 if (itertype == &PyDictIterItem_Type) {
2267 di->di_result = PyTuple_Pack(2, Py_None, Py_None);
2268 if (di->di_result == NULL) {
2269 Py_DECREF(di);
2270 return NULL;
2271 }
2272 }
2273 else
2274 di->di_result = NULL;
2275 _PyObject_GC_TRACK(di);
2276 return (PyObject *)di;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002277}
2278
2279static void
2280dictiter_dealloc(dictiterobject *di)
2281{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002282 Py_XDECREF(di->di_dict);
2283 Py_XDECREF(di->di_result);
2284 PyObject_GC_Del(di);
Antoine Pitrou7ddda782009-01-01 15:35:33 +00002285}
2286
2287static int
2288dictiter_traverse(dictiterobject *di, visitproc visit, void *arg)
2289{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002290 Py_VISIT(di->di_dict);
2291 Py_VISIT(di->di_result);
2292 return 0;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002293}
2294
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002295static PyObject *
Raymond Hettinger0ce6dc82004-03-18 08:38:00 +00002296dictiter_len(dictiterobject *di)
2297{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002298 Py_ssize_t len = 0;
2299 if (di->di_dict != NULL && di->di_used == di->di_dict->ma_used)
2300 len = di->len;
2301 return PyLong_FromSize_t(len);
Raymond Hettinger0ce6dc82004-03-18 08:38:00 +00002302}
2303
Guido van Rossumb90c8482007-02-10 01:11:45 +00002304PyDoc_STRVAR(length_hint_doc,
2305 "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002306
2307static PyMethodDef dictiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002308 {"__length_hint__", (PyCFunction)dictiter_len, METH_NOARGS,
2309 length_hint_doc},
2310 {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{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002315 PyObject *key;
2316 register Py_ssize_t i, mask;
2317 register PyDictEntry *ep;
2318 PyDictObject *d = di->di_dict;
Guido van Rossum213c7a62001-04-23 14:08:49 +00002319
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002320 if (d == NULL)
2321 return NULL;
2322 assert (PyDict_Check(d));
Guido van Rossum2147df72002-07-16 20:30:22 +00002323
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002324 if (di->di_used != d->ma_used) {
2325 PyErr_SetString(PyExc_RuntimeError,
2326 "dictionary changed size during iteration");
2327 di->di_used = -1; /* Make this state sticky */
2328 return NULL;
2329 }
Guido van Rossum2147df72002-07-16 20:30:22 +00002330
Antoine Pitrouf95a1b32010-05-09 15:52:27 +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;
2341 di->len--;
2342 key = ep[i].me_key;
2343 Py_INCREF(key);
2344 return key;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002345
2346fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002347 Py_DECREF(d);
2348 di->di_dict = NULL;
2349 return NULL;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002350}
2351
Raymond Hettinger019a1482004-03-18 02:41:19 +00002352PyTypeObject PyDictIterKey_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002353 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2354 "dict_keyiterator", /* tp_name */
2355 sizeof(dictiterobject), /* tp_basicsize */
2356 0, /* tp_itemsize */
2357 /* methods */
2358 (destructor)dictiter_dealloc, /* tp_dealloc */
2359 0, /* tp_print */
2360 0, /* tp_getattr */
2361 0, /* tp_setattr */
2362 0, /* tp_reserved */
2363 0, /* tp_repr */
2364 0, /* tp_as_number */
2365 0, /* tp_as_sequence */
2366 0, /* tp_as_mapping */
2367 0, /* tp_hash */
2368 0, /* tp_call */
2369 0, /* tp_str */
2370 PyObject_GenericGetAttr, /* tp_getattro */
2371 0, /* tp_setattro */
2372 0, /* tp_as_buffer */
2373 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2374 0, /* tp_doc */
2375 (traverseproc)dictiter_traverse, /* tp_traverse */
2376 0, /* tp_clear */
2377 0, /* tp_richcompare */
2378 0, /* tp_weaklistoffset */
2379 PyObject_SelfIter, /* tp_iter */
2380 (iternextfunc)dictiter_iternextkey, /* tp_iternext */
2381 dictiter_methods, /* tp_methods */
2382 0,
Raymond Hettinger019a1482004-03-18 02:41:19 +00002383};
2384
2385static PyObject *dictiter_iternextvalue(dictiterobject *di)
2386{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002387 PyObject *value;
2388 register Py_ssize_t i, mask;
2389 register PyDictEntry *ep;
2390 PyDictObject *d = di->di_dict;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002391
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002392 if (d == NULL)
2393 return NULL;
2394 assert (PyDict_Check(d));
Raymond Hettinger019a1482004-03-18 02:41:19 +00002395
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002396 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 }
Raymond Hettinger019a1482004-03-18 02:41:19 +00002402
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002403 i = di->di_pos;
2404 mask = d->ma_mask;
2405 if (i < 0 || i > mask)
2406 goto fail;
2407 ep = d->ma_table;
2408 while ((value=ep[i].me_value) == NULL) {
2409 i++;
2410 if (i > mask)
2411 goto fail;
2412 }
2413 di->di_pos = i+1;
2414 di->len--;
2415 Py_INCREF(value);
2416 return value;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002417
2418fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002419 Py_DECREF(d);
2420 di->di_dict = NULL;
2421 return NULL;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002422}
2423
2424PyTypeObject PyDictIterValue_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002425 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2426 "dict_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_reserved */
2435 0, /* tp_repr */
2436 0, /* tp_as_number */
2437 0, /* tp_as_sequence */
2438 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 | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2446 0, /* tp_doc */
2447 (traverseproc)dictiter_traverse, /* 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 */
2453 dictiter_methods, /* tp_methods */
2454 0,
Raymond Hettinger019a1482004-03-18 02:41:19 +00002455};
2456
2457static PyObject *dictiter_iternextitem(dictiterobject *di)
2458{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002459 PyObject *key, *value, *result = di->di_result;
2460 register Py_ssize_t i, mask;
2461 register PyDictEntry *ep;
2462 PyDictObject *d = di->di_dict;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002463
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002464 if (d == NULL)
2465 return NULL;
2466 assert (PyDict_Check(d));
Raymond Hettinger019a1482004-03-18 02:41:19 +00002467
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002468 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 }
Raymond Hettinger019a1482004-03-18 02:41:19 +00002474
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002475 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;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002485
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002486 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);
2492 if (result == NULL)
2493 return NULL;
2494 }
2495 di->len--;
2496 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;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002503
2504fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002505 Py_DECREF(d);
2506 di->di_dict = NULL;
2507 return NULL;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002508}
2509
2510PyTypeObject PyDictIterItem_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002511 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2512 "dict_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_reserved */
2521 0, /* tp_repr */
2522 0, /* tp_as_number */
2523 0, /* tp_as_sequence */
2524 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 | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2532 0, /* tp_doc */
2533 (traverseproc)dictiter_traverse, /* 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 */
2539 dictiter_methods, /* tp_methods */
2540 0,
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002541};
Guido van Rossumb90c8482007-02-10 01:11:45 +00002542
2543
Guido van Rossum3ac67412007-02-10 18:55:06 +00002544/***********************************************/
Guido van Rossumb90c8482007-02-10 01:11:45 +00002545/* View objects for keys(), items(), values(). */
Guido van Rossum3ac67412007-02-10 18:55:06 +00002546/***********************************************/
2547
Guido van Rossumb90c8482007-02-10 01:11:45 +00002548/* The instance lay-out is the same for all three; but the type differs. */
2549
2550typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002551 PyObject_HEAD
2552 PyDictObject *dv_dict;
Guido van Rossumb90c8482007-02-10 01:11:45 +00002553} dictviewobject;
2554
2555
2556static void
Guido van Rossum3ac67412007-02-10 18:55:06 +00002557dictview_dealloc(dictviewobject *dv)
Guido van Rossumb90c8482007-02-10 01:11:45 +00002558{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002559 Py_XDECREF(dv->dv_dict);
2560 PyObject_GC_Del(dv);
Antoine Pitrou7ddda782009-01-01 15:35:33 +00002561}
2562
2563static int
2564dictview_traverse(dictviewobject *dv, visitproc visit, void *arg)
2565{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002566 Py_VISIT(dv->dv_dict);
2567 return 0;
Guido van Rossumb90c8482007-02-10 01:11:45 +00002568}
2569
Guido van Rossum83825ac2007-02-10 04:54:19 +00002570static Py_ssize_t
Guido van Rossum3ac67412007-02-10 18:55:06 +00002571dictview_len(dictviewobject *dv)
Guido van Rossumb90c8482007-02-10 01:11:45 +00002572{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002573 Py_ssize_t len = 0;
2574 if (dv->dv_dict != NULL)
2575 len = dv->dv_dict->ma_used;
2576 return len;
Guido van Rossumb90c8482007-02-10 01:11:45 +00002577}
2578
2579static PyObject *
2580dictview_new(PyObject *dict, PyTypeObject *type)
2581{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002582 dictviewobject *dv;
2583 if (dict == NULL) {
2584 PyErr_BadInternalCall();
2585 return NULL;
2586 }
2587 if (!PyDict_Check(dict)) {
2588 /* XXX Get rid of this restriction later */
2589 PyErr_Format(PyExc_TypeError,
2590 "%s() requires a dict argument, not '%s'",
2591 type->tp_name, dict->ob_type->tp_name);
2592 return NULL;
2593 }
2594 dv = PyObject_GC_New(dictviewobject, type);
2595 if (dv == NULL)
2596 return NULL;
2597 Py_INCREF(dict);
2598 dv->dv_dict = (PyDictObject *)dict;
2599 _PyObject_GC_TRACK(dv);
2600 return (PyObject *)dv;
Guido van Rossumb90c8482007-02-10 01:11:45 +00002601}
2602
Neal Norwitze36f2ba2007-02-26 23:12:28 +00002603/* TODO(guido): The views objects are not complete:
2604
2605 * support more set operations
2606 * support arbitrary mappings?
2607 - either these should be static or exported in dictobject.h
2608 - if public then they should probably be in builtins
2609*/
2610
Guido van Rossumaac530c2007-08-24 22:33:45 +00002611/* Return 1 if self is a subset of other, iterating over self;
2612 0 if not; -1 if an error occurred. */
Guido van Rossumd9214d12007-02-12 02:23:40 +00002613static int
2614all_contained_in(PyObject *self, PyObject *other)
2615{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002616 PyObject *iter = PyObject_GetIter(self);
2617 int ok = 1;
Guido van Rossumd9214d12007-02-12 02:23:40 +00002618
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002619 if (iter == NULL)
2620 return -1;
2621 for (;;) {
2622 PyObject *next = PyIter_Next(iter);
2623 if (next == NULL) {
2624 if (PyErr_Occurred())
2625 ok = -1;
2626 break;
2627 }
2628 ok = PySequence_Contains(other, next);
2629 Py_DECREF(next);
2630 if (ok <= 0)
2631 break;
2632 }
2633 Py_DECREF(iter);
2634 return ok;
Guido van Rossumd9214d12007-02-12 02:23:40 +00002635}
2636
2637static PyObject *
2638dictview_richcompare(PyObject *self, PyObject *other, int op)
2639{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002640 Py_ssize_t len_self, len_other;
2641 int ok;
2642 PyObject *result;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002643
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002644 assert(self != NULL);
2645 assert(PyDictViewSet_Check(self));
2646 assert(other != NULL);
Guido van Rossumd9214d12007-02-12 02:23:40 +00002647
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002648 if (!PyAnySet_Check(other) && !PyDictViewSet_Check(other)) {
2649 Py_INCREF(Py_NotImplemented);
2650 return Py_NotImplemented;
2651 }
Guido van Rossumaac530c2007-08-24 22:33:45 +00002652
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002653 len_self = PyObject_Size(self);
2654 if (len_self < 0)
2655 return NULL;
2656 len_other = PyObject_Size(other);
2657 if (len_other < 0)
2658 return NULL;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002659
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002660 ok = 0;
2661 switch(op) {
Guido van Rossumaac530c2007-08-24 22:33:45 +00002662
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002663 case Py_NE:
2664 case Py_EQ:
2665 if (len_self == len_other)
2666 ok = all_contained_in(self, other);
2667 if (op == Py_NE && ok >= 0)
2668 ok = !ok;
2669 break;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002670
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002671 case Py_LT:
2672 if (len_self < len_other)
2673 ok = all_contained_in(self, other);
2674 break;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002675
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002676 case Py_LE:
2677 if (len_self <= len_other)
2678 ok = all_contained_in(self, other);
2679 break;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002680
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002681 case Py_GT:
2682 if (len_self > len_other)
2683 ok = all_contained_in(other, self);
2684 break;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002685
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002686 case Py_GE:
2687 if (len_self >= len_other)
2688 ok = all_contained_in(other, self);
2689 break;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002690
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002691 }
2692 if (ok < 0)
2693 return NULL;
2694 result = ok ? Py_True : Py_False;
2695 Py_INCREF(result);
2696 return result;
Guido van Rossumd9214d12007-02-12 02:23:40 +00002697}
2698
Raymond Hettingerb0d56af2009-03-03 10:52:49 +00002699static PyObject *
2700dictview_repr(dictviewobject *dv)
2701{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002702 PyObject *seq;
2703 PyObject *result;
Raymond Hettingerb0d56af2009-03-03 10:52:49 +00002704
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002705 seq = PySequence_List((PyObject *)dv);
2706 if (seq == NULL)
2707 return NULL;
2708
2709 result = PyUnicode_FromFormat("%s(%R)", Py_TYPE(dv)->tp_name, seq);
2710 Py_DECREF(seq);
2711 return result;
Raymond Hettingerb0d56af2009-03-03 10:52:49 +00002712}
2713
Guido van Rossum3ac67412007-02-10 18:55:06 +00002714/*** dict_keys ***/
Guido van Rossumb90c8482007-02-10 01:11:45 +00002715
2716static PyObject *
Guido van Rossum3ac67412007-02-10 18:55:06 +00002717dictkeys_iter(dictviewobject *dv)
Guido van Rossumb90c8482007-02-10 01:11:45 +00002718{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002719 if (dv->dv_dict == NULL) {
2720 Py_RETURN_NONE;
2721 }
2722 return dictiter_new(dv->dv_dict, &PyDictIterKey_Type);
Guido van Rossum3ac67412007-02-10 18:55:06 +00002723}
2724
2725static int
2726dictkeys_contains(dictviewobject *dv, PyObject *obj)
2727{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002728 if (dv->dv_dict == NULL)
2729 return 0;
2730 return PyDict_Contains((PyObject *)dv->dv_dict, obj);
Guido van Rossumb90c8482007-02-10 01:11:45 +00002731}
2732
Guido van Rossum83825ac2007-02-10 04:54:19 +00002733static PySequenceMethods dictkeys_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002734 (lenfunc)dictview_len, /* sq_length */
2735 0, /* sq_concat */
2736 0, /* sq_repeat */
2737 0, /* sq_item */
2738 0, /* sq_slice */
2739 0, /* sq_ass_item */
2740 0, /* sq_ass_slice */
2741 (objobjproc)dictkeys_contains, /* sq_contains */
Guido van Rossum83825ac2007-02-10 04:54:19 +00002742};
2743
Guido van Rossum523259b2007-08-24 23:41:22 +00002744static PyObject*
2745dictviews_sub(PyObject* self, PyObject *other)
2746{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002747 PyObject *result = PySet_New(self);
2748 PyObject *tmp;
2749 if (result == NULL)
2750 return NULL;
Guido van Rossum523259b2007-08-24 23:41:22 +00002751
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002752 tmp = PyObject_CallMethod(result, "difference_update", "O", other);
2753 if (tmp == NULL) {
2754 Py_DECREF(result);
2755 return NULL;
2756 }
Guido van Rossum523259b2007-08-24 23:41:22 +00002757
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002758 Py_DECREF(tmp);
2759 return result;
Guido van Rossum523259b2007-08-24 23:41:22 +00002760}
2761
2762static PyObject*
2763dictviews_and(PyObject* self, PyObject *other)
2764{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002765 PyObject *result = PySet_New(self);
2766 PyObject *tmp;
2767 if (result == NULL)
2768 return NULL;
Guido van Rossum523259b2007-08-24 23:41:22 +00002769
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002770 tmp = PyObject_CallMethod(result, "intersection_update", "O", other);
2771 if (tmp == NULL) {
2772 Py_DECREF(result);
2773 return NULL;
2774 }
Guido van Rossum523259b2007-08-24 23:41:22 +00002775
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002776 Py_DECREF(tmp);
2777 return result;
Guido van Rossum523259b2007-08-24 23:41:22 +00002778}
2779
2780static PyObject*
2781dictviews_or(PyObject* self, PyObject *other)
2782{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002783 PyObject *result = PySet_New(self);
2784 PyObject *tmp;
2785 if (result == NULL)
2786 return NULL;
Guido van Rossum523259b2007-08-24 23:41:22 +00002787
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002788 tmp = PyObject_CallMethod(result, "update", "O", other);
2789 if (tmp == NULL) {
2790 Py_DECREF(result);
2791 return NULL;
2792 }
Guido van Rossum523259b2007-08-24 23:41:22 +00002793
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002794 Py_DECREF(tmp);
2795 return result;
Guido van Rossum523259b2007-08-24 23:41:22 +00002796}
2797
2798static PyObject*
2799dictviews_xor(PyObject* self, PyObject *other)
2800{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002801 PyObject *result = PySet_New(self);
2802 PyObject *tmp;
2803 if (result == NULL)
2804 return NULL;
Guido van Rossum523259b2007-08-24 23:41:22 +00002805
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002806 tmp = PyObject_CallMethod(result, "symmetric_difference_update", "O",
2807 other);
2808 if (tmp == NULL) {
2809 Py_DECREF(result);
2810 return NULL;
2811 }
Guido van Rossum523259b2007-08-24 23:41:22 +00002812
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002813 Py_DECREF(tmp);
2814 return result;
Guido van Rossum523259b2007-08-24 23:41:22 +00002815}
2816
2817static PyNumberMethods dictviews_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002818 0, /*nb_add*/
2819 (binaryfunc)dictviews_sub, /*nb_subtract*/
2820 0, /*nb_multiply*/
2821 0, /*nb_remainder*/
2822 0, /*nb_divmod*/
2823 0, /*nb_power*/
2824 0, /*nb_negative*/
2825 0, /*nb_positive*/
2826 0, /*nb_absolute*/
2827 0, /*nb_bool*/
2828 0, /*nb_invert*/
2829 0, /*nb_lshift*/
2830 0, /*nb_rshift*/
2831 (binaryfunc)dictviews_and, /*nb_and*/
2832 (binaryfunc)dictviews_xor, /*nb_xor*/
2833 (binaryfunc)dictviews_or, /*nb_or*/
Guido van Rossum523259b2007-08-24 23:41:22 +00002834};
2835
Daniel Stutzbach045b3ba2010-09-02 15:06:06 +00002836static PyObject*
2837dictviews_isdisjoint(PyObject *self, PyObject *other)
2838{
2839 PyObject *it;
2840 PyObject *item = NULL;
2841
2842 if (self == other) {
2843 if (dictview_len((dictviewobject *)self) == 0)
2844 Py_RETURN_TRUE;
2845 else
2846 Py_RETURN_FALSE;
2847 }
2848
2849 /* Iterate over the shorter object (only if other is a set,
2850 * because PySequence_Contains may be expensive otherwise): */
2851 if (PyAnySet_Check(other) || PyDictViewSet_Check(other)) {
2852 Py_ssize_t len_self = dictview_len((dictviewobject *)self);
2853 Py_ssize_t len_other = PyObject_Size(other);
2854 if (len_other == -1)
2855 return NULL;
2856
2857 if ((len_other > len_self)) {
2858 PyObject *tmp = other;
2859 other = self;
2860 self = tmp;
2861 }
2862 }
2863
2864 it = PyObject_GetIter(other);
2865 if (it == NULL)
2866 return NULL;
2867
2868 while ((item = PyIter_Next(it)) != NULL) {
2869 int contains = PySequence_Contains(self, item);
2870 Py_DECREF(item);
2871 if (contains == -1) {
2872 Py_DECREF(it);
2873 return NULL;
2874 }
2875
2876 if (contains) {
2877 Py_DECREF(it);
2878 Py_RETURN_FALSE;
2879 }
2880 }
2881 Py_DECREF(it);
2882 if (PyErr_Occurred())
2883 return NULL; /* PyIter_Next raised an exception. */
2884 Py_RETURN_TRUE;
2885}
2886
2887PyDoc_STRVAR(isdisjoint_doc,
2888"Return True if the view and the given iterable have a null intersection.");
2889
Guido van Rossumb90c8482007-02-10 01:11:45 +00002890static PyMethodDef dictkeys_methods[] = {
Daniel Stutzbach045b3ba2010-09-02 15:06:06 +00002891 {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
2892 isdisjoint_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002893 {NULL, NULL} /* sentinel */
Guido van Rossumb90c8482007-02-10 01:11:45 +00002894};
2895
2896PyTypeObject PyDictKeys_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002897 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2898 "dict_keys", /* tp_name */
2899 sizeof(dictviewobject), /* tp_basicsize */
2900 0, /* tp_itemsize */
2901 /* methods */
2902 (destructor)dictview_dealloc, /* tp_dealloc */
2903 0, /* tp_print */
2904 0, /* tp_getattr */
2905 0, /* tp_setattr */
2906 0, /* tp_reserved */
2907 (reprfunc)dictview_repr, /* tp_repr */
2908 &dictviews_as_number, /* tp_as_number */
2909 &dictkeys_as_sequence, /* tp_as_sequence */
2910 0, /* tp_as_mapping */
2911 0, /* tp_hash */
2912 0, /* tp_call */
2913 0, /* tp_str */
2914 PyObject_GenericGetAttr, /* tp_getattro */
2915 0, /* tp_setattro */
2916 0, /* tp_as_buffer */
2917 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2918 0, /* tp_doc */
2919 (traverseproc)dictview_traverse, /* tp_traverse */
2920 0, /* tp_clear */
2921 dictview_richcompare, /* tp_richcompare */
2922 0, /* tp_weaklistoffset */
2923 (getiterfunc)dictkeys_iter, /* tp_iter */
2924 0, /* tp_iternext */
2925 dictkeys_methods, /* tp_methods */
2926 0,
Guido van Rossumb90c8482007-02-10 01:11:45 +00002927};
2928
2929static PyObject *
2930dictkeys_new(PyObject *dict)
2931{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002932 return dictview_new(dict, &PyDictKeys_Type);
Guido van Rossumb90c8482007-02-10 01:11:45 +00002933}
2934
Guido van Rossum3ac67412007-02-10 18:55:06 +00002935/*** dict_items ***/
Guido van Rossumb90c8482007-02-10 01:11:45 +00002936
2937static PyObject *
Guido van Rossum3ac67412007-02-10 18:55:06 +00002938dictitems_iter(dictviewobject *dv)
Guido van Rossumb90c8482007-02-10 01:11:45 +00002939{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002940 if (dv->dv_dict == NULL) {
2941 Py_RETURN_NONE;
2942 }
2943 return dictiter_new(dv->dv_dict, &PyDictIterItem_Type);
Guido van Rossum3ac67412007-02-10 18:55:06 +00002944}
2945
2946static int
2947dictitems_contains(dictviewobject *dv, PyObject *obj)
2948{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002949 PyObject *key, *value, *found;
2950 if (dv->dv_dict == NULL)
2951 return 0;
2952 if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 2)
2953 return 0;
2954 key = PyTuple_GET_ITEM(obj, 0);
2955 value = PyTuple_GET_ITEM(obj, 1);
2956 found = PyDict_GetItem((PyObject *)dv->dv_dict, key);
2957 if (found == NULL) {
2958 if (PyErr_Occurred())
2959 return -1;
2960 return 0;
2961 }
2962 return PyObject_RichCompareBool(value, found, Py_EQ);
Guido van Rossumb90c8482007-02-10 01:11:45 +00002963}
2964
Guido van Rossum83825ac2007-02-10 04:54:19 +00002965static PySequenceMethods dictitems_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002966 (lenfunc)dictview_len, /* sq_length */
2967 0, /* sq_concat */
2968 0, /* sq_repeat */
2969 0, /* sq_item */
2970 0, /* sq_slice */
2971 0, /* sq_ass_item */
2972 0, /* sq_ass_slice */
2973 (objobjproc)dictitems_contains, /* sq_contains */
Guido van Rossum83825ac2007-02-10 04:54:19 +00002974};
2975
Guido van Rossumb90c8482007-02-10 01:11:45 +00002976static PyMethodDef dictitems_methods[] = {
Daniel Stutzbach045b3ba2010-09-02 15:06:06 +00002977 {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
2978 isdisjoint_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002979 {NULL, NULL} /* sentinel */
Guido van Rossumb90c8482007-02-10 01:11:45 +00002980};
2981
2982PyTypeObject PyDictItems_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002983 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2984 "dict_items", /* tp_name */
2985 sizeof(dictviewobject), /* tp_basicsize */
2986 0, /* tp_itemsize */
2987 /* methods */
2988 (destructor)dictview_dealloc, /* tp_dealloc */
2989 0, /* tp_print */
2990 0, /* tp_getattr */
2991 0, /* tp_setattr */
2992 0, /* tp_reserved */
2993 (reprfunc)dictview_repr, /* tp_repr */
2994 &dictviews_as_number, /* tp_as_number */
2995 &dictitems_as_sequence, /* tp_as_sequence */
2996 0, /* tp_as_mapping */
2997 0, /* tp_hash */
2998 0, /* tp_call */
2999 0, /* tp_str */
3000 PyObject_GenericGetAttr, /* tp_getattro */
3001 0, /* tp_setattro */
3002 0, /* tp_as_buffer */
3003 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3004 0, /* tp_doc */
3005 (traverseproc)dictview_traverse, /* tp_traverse */
3006 0, /* tp_clear */
3007 dictview_richcompare, /* tp_richcompare */
3008 0, /* tp_weaklistoffset */
3009 (getiterfunc)dictitems_iter, /* tp_iter */
3010 0, /* tp_iternext */
3011 dictitems_methods, /* tp_methods */
3012 0,
Guido van Rossumb90c8482007-02-10 01:11:45 +00003013};
3014
3015static PyObject *
3016dictitems_new(PyObject *dict)
3017{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003018 return dictview_new(dict, &PyDictItems_Type);
Guido van Rossumb90c8482007-02-10 01:11:45 +00003019}
3020
Guido van Rossum3ac67412007-02-10 18:55:06 +00003021/*** dict_values ***/
Guido van Rossumb90c8482007-02-10 01:11:45 +00003022
3023static PyObject *
Guido van Rossum3ac67412007-02-10 18:55:06 +00003024dictvalues_iter(dictviewobject *dv)
Guido van Rossumb90c8482007-02-10 01:11:45 +00003025{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003026 if (dv->dv_dict == NULL) {
3027 Py_RETURN_NONE;
3028 }
3029 return dictiter_new(dv->dv_dict, &PyDictIterValue_Type);
Guido van Rossumb90c8482007-02-10 01:11:45 +00003030}
3031
Guido van Rossum83825ac2007-02-10 04:54:19 +00003032static PySequenceMethods dictvalues_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003033 (lenfunc)dictview_len, /* sq_length */
3034 0, /* sq_concat */
3035 0, /* sq_repeat */
3036 0, /* sq_item */
3037 0, /* sq_slice */
3038 0, /* sq_ass_item */
3039 0, /* sq_ass_slice */
3040 (objobjproc)0, /* sq_contains */
Guido van Rossum83825ac2007-02-10 04:54:19 +00003041};
3042
Guido van Rossumb90c8482007-02-10 01:11:45 +00003043static PyMethodDef dictvalues_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003044 {NULL, NULL} /* sentinel */
Guido van Rossumb90c8482007-02-10 01:11:45 +00003045};
3046
3047PyTypeObject PyDictValues_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003048 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3049 "dict_values", /* tp_name */
3050 sizeof(dictviewobject), /* tp_basicsize */
3051 0, /* tp_itemsize */
3052 /* methods */
3053 (destructor)dictview_dealloc, /* tp_dealloc */
3054 0, /* tp_print */
3055 0, /* tp_getattr */
3056 0, /* tp_setattr */
3057 0, /* tp_reserved */
3058 (reprfunc)dictview_repr, /* tp_repr */
3059 0, /* tp_as_number */
3060 &dictvalues_as_sequence, /* tp_as_sequence */
3061 0, /* tp_as_mapping */
3062 0, /* tp_hash */
3063 0, /* tp_call */
3064 0, /* tp_str */
3065 PyObject_GenericGetAttr, /* tp_getattro */
3066 0, /* tp_setattro */
3067 0, /* tp_as_buffer */
3068 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3069 0, /* tp_doc */
3070 (traverseproc)dictview_traverse, /* tp_traverse */
3071 0, /* tp_clear */
3072 0, /* tp_richcompare */
3073 0, /* tp_weaklistoffset */
3074 (getiterfunc)dictvalues_iter, /* tp_iter */
3075 0, /* tp_iternext */
3076 dictvalues_methods, /* tp_methods */
3077 0,
Guido van Rossumb90c8482007-02-10 01:11:45 +00003078};
3079
3080static PyObject *
3081dictvalues_new(PyObject *dict)
3082{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003083 return dictview_new(dict, &PyDictValues_Type);
Guido van Rossumb90c8482007-02-10 01:11:45 +00003084}