blob: cdc27abc07ad329758f036650f5088ddc3ea4c91 [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
513
Fred Drake1bff34a2000-08-31 19:31:38 +0000514/*
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000515Internal routine to insert a new item into the table.
516Used both by the internal resize routine and by the public insert routine.
517Eats a reference to key and one to value.
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000518Returns -1 if an error occurred, or 0 on success.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000519*/
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000520static int
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000521insertdict(register PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000522{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000523 PyObject *old_value;
524 register PyDictEntry *ep;
Antoine Pitroufbb1c612010-10-23 17:37:54 +0000525 typedef PyDictEntry *(*lookupfunc)(PyDictObject *, PyObject *, Py_hash_t);
Tim Peters6d6c1a32001-08-02 04:15:00 +0000526
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000527 assert(mp->ma_lookup != NULL);
528 ep = mp->ma_lookup(mp, key, hash);
529 if (ep == NULL) {
530 Py_DECREF(key);
531 Py_DECREF(value);
532 return -1;
533 }
534 MAINTAIN_TRACKING(mp, key, value);
535 if (ep->me_value != NULL) {
536 old_value = ep->me_value;
537 ep->me_value = value;
538 Py_DECREF(old_value); /* which **CAN** re-enter */
539 Py_DECREF(key);
540 }
541 else {
542 if (ep->me_key == NULL)
543 mp->ma_fill++;
544 else {
545 assert(ep->me_key == dummy);
546 Py_DECREF(dummy);
547 }
548 ep->me_key = key;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000549 ep->me_hash = hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000550 ep->me_value = value;
551 mp->ma_used++;
552 }
553 return 0;
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000554}
555
556/*
557Internal routine used by dictresize() to insert an item which is
558known to be absent from the dict. This routine also assumes that
559the dict contains no deleted entries. Besides the performance benefit,
560using insertdict() in dictresize() is dangerous (SF bug #1456209).
561Note that no refcounts are changed by this routine; if needed, the caller
562is responsible for incref'ing `key` and `value`.
563*/
564static void
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000565insertdict_clean(register PyDictObject *mp, PyObject *key, Py_hash_t hash,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000566 PyObject *value)
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000567{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000568 register size_t i;
569 register size_t perturb;
570 register size_t mask = (size_t)mp->ma_mask;
571 PyDictEntry *ep0 = mp->ma_table;
572 register PyDictEntry *ep;
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000573
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000574 MAINTAIN_TRACKING(mp, key, value);
575 i = hash & mask;
576 ep = &ep0[i];
577 for (perturb = hash; ep->me_key != NULL; perturb >>= PERTURB_SHIFT) {
578 i = (i << 2) + i + perturb + 1;
579 ep = &ep0[i & mask];
580 }
581 assert(ep->me_value == NULL);
582 mp->ma_fill++;
583 ep->me_key = key;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000584 ep->me_hash = hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000585 ep->me_value = value;
586 mp->ma_used++;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000587}
588
589/*
590Restructure the table by allocating a new table and reinserting all
591items again. When entries have been deleted, the new table may
592actually be smaller than the old one.
593*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000594static int
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000595dictresize(PyDictObject *mp, Py_ssize_t minused)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000596{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000597 Py_ssize_t newsize;
598 PyDictEntry *oldtable, *newtable, *ep;
599 Py_ssize_t i;
600 int is_oldtable_malloced;
601 PyDictEntry small_copy[PyDict_MINSIZE];
Tim Peters91a364d2001-05-19 07:04:38 +0000602
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000603 assert(minused >= 0);
Tim Peters0c6010b2001-05-23 23:33:57 +0000604
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000605 /* Find the smallest table size > minused. */
606 for (newsize = PyDict_MINSIZE;
607 newsize <= minused && newsize > 0;
608 newsize <<= 1)
609 ;
610 if (newsize <= 0) {
611 PyErr_NoMemory();
612 return -1;
613 }
Tim Peters0c6010b2001-05-23 23:33:57 +0000614
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000615 /* Get space for a new table. */
616 oldtable = mp->ma_table;
617 assert(oldtable != NULL);
618 is_oldtable_malloced = oldtable != mp->ma_smalltable;
Tim Peters0c6010b2001-05-23 23:33:57 +0000619
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000620 if (newsize == PyDict_MINSIZE) {
621 /* A large table is shrinking, or we can't get any smaller. */
622 newtable = mp->ma_smalltable;
623 if (newtable == oldtable) {
624 if (mp->ma_fill == mp->ma_used) {
625 /* No dummies, so no point doing anything. */
626 return 0;
627 }
628 /* We're not going to resize it, but rebuild the
629 table anyway to purge old dummy entries.
630 Subtle: This is *necessary* if fill==size,
631 as lookdict needs at least one virgin slot to
632 terminate failing searches. If fill < size, it's
633 merely desirable, as dummies slow searches. */
634 assert(mp->ma_fill > mp->ma_used);
635 memcpy(small_copy, oldtable, sizeof(small_copy));
636 oldtable = small_copy;
637 }
638 }
639 else {
640 newtable = PyMem_NEW(PyDictEntry, newsize);
641 if (newtable == NULL) {
642 PyErr_NoMemory();
643 return -1;
644 }
645 }
Tim Peters0c6010b2001-05-23 23:33:57 +0000646
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000647 /* Make the dict empty, using the new table. */
648 assert(newtable != oldtable);
649 mp->ma_table = newtable;
650 mp->ma_mask = newsize - 1;
651 memset(newtable, 0, sizeof(PyDictEntry) * newsize);
652 mp->ma_used = 0;
653 i = mp->ma_fill;
654 mp->ma_fill = 0;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000655
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000656 /* Copy the data over; this is refcount-neutral for active entries;
657 dummy entries aren't copied over, of course */
658 for (ep = oldtable; i > 0; ep++) {
659 if (ep->me_value != NULL) { /* active entry */
660 --i;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000661 insertdict_clean(mp, ep->me_key, ep->me_hash, ep->me_value);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000662 }
663 else if (ep->me_key != NULL) { /* dummy entry */
664 --i;
665 assert(ep->me_key == dummy);
666 Py_DECREF(ep->me_key);
667 }
668 /* else key == value == NULL: nothing to do */
669 }
Guido van Rossumd7047b31995-01-02 19:07:15 +0000670
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000671 if (is_oldtable_malloced)
672 PyMem_DEL(oldtable);
673 return 0;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000674}
675
Christian Heimes99170a52007-12-19 02:07:34 +0000676/* Create a new dictionary pre-sized to hold an estimated number of elements.
677 Underestimates are okay because the dictionary will resize as necessary.
678 Overestimates just mean the dictionary will be more sparse than usual.
679*/
680
681PyObject *
682_PyDict_NewPresized(Py_ssize_t minused)
683{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000684 PyObject *op = PyDict_New();
Christian Heimes99170a52007-12-19 02:07:34 +0000685
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000686 if (minused>5 && op != NULL && dictresize((PyDictObject *)op, minused) == -1) {
687 Py_DECREF(op);
688 return NULL;
689 }
690 return op;
Christian Heimes99170a52007-12-19 02:07:34 +0000691}
692
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000693/* Note that, for historical reasons, PyDict_GetItem() suppresses all errors
694 * that may occur (originally dicts supported only string keys, and exceptions
695 * weren't possible). So, while the original intent was that a NULL return
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000696 * meant the key wasn't present, in reality it can mean that, or that an error
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000697 * (suppressed) occurred while computing the key's hash, or that some error
698 * (suppressed) occurred when comparing keys in the dict's internal probe
699 * sequence. A nasty example of the latter is when a Python-coded comparison
700 * function hits a stack-depth error, which can cause this to return NULL
701 * even if the key is present.
702 */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000703PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000704PyDict_GetItem(PyObject *op, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000705{
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000706 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000707 PyDictObject *mp = (PyDictObject *)op;
708 PyDictEntry *ep;
709 PyThreadState *tstate;
710 if (!PyDict_Check(op))
711 return NULL;
712 if (!PyUnicode_CheckExact(key) ||
713 (hash = ((PyUnicodeObject *) key)->hash) == -1)
714 {
715 hash = PyObject_Hash(key);
716 if (hash == -1) {
717 PyErr_Clear();
718 return NULL;
719 }
720 }
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000721
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000722 /* We can arrive here with a NULL tstate during initialization: try
723 running "python -Wi" for an example related to string interning.
724 Let's just hope that no exception occurs then... This must be
725 _PyThreadState_Current and not PyThreadState_GET() because in debug
726 mode, the latter complains if tstate is NULL. */
727 tstate = (PyThreadState*)_Py_atomic_load_relaxed(
728 &_PyThreadState_Current);
729 if (tstate != NULL && tstate->curexc_type != NULL) {
730 /* preserve the existing exception */
731 PyObject *err_type, *err_value, *err_tb;
732 PyErr_Fetch(&err_type, &err_value, &err_tb);
733 ep = (mp->ma_lookup)(mp, key, hash);
734 /* ignore errors */
735 PyErr_Restore(err_type, err_value, err_tb);
736 if (ep == NULL)
737 return NULL;
738 }
739 else {
740 ep = (mp->ma_lookup)(mp, key, hash);
741 if (ep == NULL) {
742 PyErr_Clear();
743 return NULL;
744 }
745 }
746 return ep->me_value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000747}
748
Guido van Rossum47b9ff62006-08-24 00:41:19 +0000749/* Variant of PyDict_GetItem() that doesn't suppress exceptions.
750 This returns NULL *with* an exception set if an exception occurred.
751 It returns NULL *without* an exception set if the key wasn't present.
752*/
753PyObject *
754PyDict_GetItemWithError(PyObject *op, PyObject *key)
755{
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000756 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000757 PyDictObject*mp = (PyDictObject *)op;
758 PyDictEntry *ep;
Guido van Rossum47b9ff62006-08-24 00:41:19 +0000759
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000760 if (!PyDict_Check(op)) {
761 PyErr_BadInternalCall();
762 return NULL;
763 }
764 if (!PyUnicode_CheckExact(key) ||
765 (hash = ((PyUnicodeObject *) key)->hash) == -1)
766 {
767 hash = PyObject_Hash(key);
768 if (hash == -1) {
769 return NULL;
770 }
771 }
Guido van Rossum47b9ff62006-08-24 00:41:19 +0000772
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000773 ep = (mp->ma_lookup)(mp, key, hash);
774 if (ep == NULL)
775 return NULL;
776 return ep->me_value;
Guido van Rossum47b9ff62006-08-24 00:41:19 +0000777}
778
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000779/* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
Tim Peters60b29962006-01-01 01:19:23 +0000780 * dictionary if it's merely replacing the value for an existing key.
781 * This means that it's safe to loop over a dictionary with PyDict_Next()
782 * and occasionally replace a value -- but you can't insert new keys or
783 * remove them.
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000784 */
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000785int
Tim Peters1f5871e2000-07-04 17:44:48 +0000786PyDict_SetItem(register PyObject *op, PyObject *key, PyObject *value)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000787{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000788 register PyDictObject *mp;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000789 register Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000790 register Py_ssize_t n_used;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000791
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000792 if (!PyDict_Check(op)) {
793 PyErr_BadInternalCall();
794 return -1;
795 }
796 assert(key);
797 assert(value);
798 mp = (PyDictObject *)op;
799 if (!PyUnicode_CheckExact(key) ||
800 (hash = ((PyUnicodeObject *) key)->hash) == -1)
801 {
802 hash = PyObject_Hash(key);
803 if (hash == -1)
804 return -1;
805 }
806 assert(mp->ma_fill <= mp->ma_mask); /* at least one empty slot */
807 n_used = mp->ma_used;
808 Py_INCREF(value);
809 Py_INCREF(key);
810 if (insertdict(mp, key, hash, value) != 0)
811 return -1;
812 /* If we added a key, we can safely resize. Otherwise just return!
813 * If fill >= 2/3 size, adjust size. Normally, this doubles or
814 * quaduples the size, but it's also possible for the dict to shrink
815 * (if ma_fill is much larger than ma_used, meaning a lot of dict
816 * keys have been * deleted).
817 *
818 * Quadrupling the size improves average dictionary sparseness
819 * (reducing collisions) at the cost of some memory and iteration
820 * speed (which loops over every possible entry). It also halves
821 * the number of expensive resize operations in a growing dictionary.
822 *
823 * Very large dictionaries (over 50K items) use doubling instead.
824 * This may help applications with severe memory constraints.
825 */
826 if (!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))
827 return 0;
828 return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000829}
830
831int
Tim Peters1f5871e2000-07-04 17:44:48 +0000832PyDict_DelItem(PyObject *op, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000833{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000834 register PyDictObject *mp;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000835 register Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000836 register PyDictEntry *ep;
837 PyObject *old_value, *old_key;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000838
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000839 if (!PyDict_Check(op)) {
840 PyErr_BadInternalCall();
841 return -1;
842 }
843 assert(key);
844 if (!PyUnicode_CheckExact(key) ||
845 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
846 hash = PyObject_Hash(key);
847 if (hash == -1)
848 return -1;
849 }
850 mp = (PyDictObject *)op;
851 ep = (mp->ma_lookup)(mp, key, hash);
852 if (ep == NULL)
853 return -1;
854 if (ep->me_value == NULL) {
855 set_key_error(key);
856 return -1;
857 }
858 old_key = ep->me_key;
859 Py_INCREF(dummy);
860 ep->me_key = dummy;
861 old_value = ep->me_value;
862 ep->me_value = NULL;
863 mp->ma_used--;
864 Py_DECREF(old_value);
865 Py_DECREF(old_key);
866 return 0;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000867}
868
Guido van Rossum25831651993-05-19 14:50:45 +0000869void
Tim Peters1f5871e2000-07-04 17:44:48 +0000870PyDict_Clear(PyObject *op)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000871{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000872 PyDictObject *mp;
873 PyDictEntry *ep, *table;
874 int table_is_malloced;
875 Py_ssize_t fill;
876 PyDictEntry small_copy[PyDict_MINSIZE];
Tim Petersdea48ec2001-05-22 20:40:22 +0000877#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000878 Py_ssize_t i, n;
Tim Petersdea48ec2001-05-22 20:40:22 +0000879#endif
880
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000881 if (!PyDict_Check(op))
882 return;
883 mp = (PyDictObject *)op;
Tim Petersdea48ec2001-05-22 20:40:22 +0000884#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000885 n = mp->ma_mask + 1;
886 i = 0;
Tim Petersdea48ec2001-05-22 20:40:22 +0000887#endif
888
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000889 table = mp->ma_table;
890 assert(table != NULL);
891 table_is_malloced = table != mp->ma_smalltable;
Tim Petersdea48ec2001-05-22 20:40:22 +0000892
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000893 /* This is delicate. During the process of clearing the dict,
894 * decrefs can cause the dict to mutate. To avoid fatal confusion
895 * (voice of experience), we have to make the dict empty before
896 * clearing the slots, and never refer to anything via mp->xxx while
897 * clearing.
898 */
899 fill = mp->ma_fill;
900 if (table_is_malloced)
901 EMPTY_TO_MINSIZE(mp);
Tim Petersdea48ec2001-05-22 20:40:22 +0000902
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000903 else if (fill > 0) {
904 /* It's a small table with something that needs to be cleared.
905 * Afraid the only safe way is to copy the dict entries into
906 * another small table first.
907 */
908 memcpy(small_copy, table, sizeof(small_copy));
909 table = small_copy;
910 EMPTY_TO_MINSIZE(mp);
911 }
912 /* else it's a small table that's already empty */
Tim Petersdea48ec2001-05-22 20:40:22 +0000913
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000914 /* Now we can finally clear things. If C had refcounts, we could
915 * assert that the refcount on table is 1 now, i.e. that this function
916 * has unique access to it, so decref side-effects can't alter it.
917 */
918 for (ep = table; fill > 0; ++ep) {
Tim Petersdea48ec2001-05-22 20:40:22 +0000919#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000920 assert(i < n);
921 ++i;
Tim Petersdea48ec2001-05-22 20:40:22 +0000922#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000923 if (ep->me_key) {
924 --fill;
925 Py_DECREF(ep->me_key);
926 Py_XDECREF(ep->me_value);
927 }
Tim Petersdea48ec2001-05-22 20:40:22 +0000928#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000929 else
930 assert(ep->me_value == NULL);
Tim Petersdea48ec2001-05-22 20:40:22 +0000931#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000932 }
Tim Petersdea48ec2001-05-22 20:40:22 +0000933
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000934 if (table_is_malloced)
935 PyMem_DEL(table);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000936}
937
Tim Peters080c88b2003-02-15 03:01:11 +0000938/*
939 * Iterate over a dict. Use like so:
940 *
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000941 * Py_ssize_t i;
Tim Peters080c88b2003-02-15 03:01:11 +0000942 * PyObject *key, *value;
943 * i = 0; # important! i should not otherwise be changed by you
Neal Norwitz07323012003-02-15 14:45:12 +0000944 * while (PyDict_Next(yourdict, &i, &key, &value)) {
Tim Peters080c88b2003-02-15 03:01:11 +0000945 * Refer to borrowed references in key and value.
946 * }
947 *
948 * CAUTION: In general, it isn't safe to use PyDict_Next in a loop that
Tim Peters67830702001-03-21 19:23:56 +0000949 * mutates the dict. One exception: it is safe if the loop merely changes
950 * the values associated with the keys (but doesn't insert new keys or
951 * delete keys), via PyDict_SetItem().
952 */
Guido van Rossum25831651993-05-19 14:50:45 +0000953int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000954PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000955{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000956 register Py_ssize_t i;
957 register Py_ssize_t mask;
958 register PyDictEntry *ep;
Raymond Hettinger43442782004-03-17 21:55:03 +0000959
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000960 if (!PyDict_Check(op))
961 return 0;
962 i = *ppos;
963 if (i < 0)
964 return 0;
965 ep = ((PyDictObject *)op)->ma_table;
966 mask = ((PyDictObject *)op)->ma_mask;
967 while (i <= mask && ep[i].me_value == NULL)
968 i++;
969 *ppos = i+1;
970 if (i > mask)
971 return 0;
972 if (pkey)
973 *pkey = ep[i].me_key;
974 if (pvalue)
975 *pvalue = ep[i].me_value;
976 return 1;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000977}
978
Thomas Wouterscf297e42007-02-23 15:07:44 +0000979/* Internal version of PyDict_Next that returns a hash value in addition to the key and value.*/
980int
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000981_PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue, Py_hash_t *phash)
Thomas Wouterscf297e42007-02-23 15:07:44 +0000982{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000983 register Py_ssize_t i;
984 register Py_ssize_t mask;
985 register PyDictEntry *ep;
Thomas Wouterscf297e42007-02-23 15:07:44 +0000986
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000987 if (!PyDict_Check(op))
988 return 0;
989 i = *ppos;
990 if (i < 0)
991 return 0;
992 ep = ((PyDictObject *)op)->ma_table;
993 mask = ((PyDictObject *)op)->ma_mask;
994 while (i <= mask && ep[i].me_value == NULL)
995 i++;
996 *ppos = i+1;
997 if (i > mask)
998 return 0;
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000999 *phash = ep[i].me_hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001000 if (pkey)
1001 *pkey = ep[i].me_key;
1002 if (pvalue)
1003 *pvalue = ep[i].me_value;
1004 return 1;
Thomas Wouterscf297e42007-02-23 15:07:44 +00001005}
1006
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001007/* Methods */
1008
1009static void
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001010dict_dealloc(register PyDictObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001011{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001012 register PyDictEntry *ep;
1013 Py_ssize_t fill = mp->ma_fill;
1014 PyObject_GC_UnTrack(mp);
1015 Py_TRASHCAN_SAFE_BEGIN(mp)
1016 for (ep = mp->ma_table; fill > 0; ep++) {
1017 if (ep->me_key) {
1018 --fill;
1019 Py_DECREF(ep->me_key);
1020 Py_XDECREF(ep->me_value);
1021 }
1022 }
1023 if (mp->ma_table != mp->ma_smalltable)
1024 PyMem_DEL(mp->ma_table);
1025 if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
1026 free_list[numfree++] = mp;
1027 else
1028 Py_TYPE(mp)->tp_free((PyObject *)mp);
1029 Py_TRASHCAN_SAFE_END(mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001030}
1031
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001032static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001033dict_repr(PyDictObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001034{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001035 Py_ssize_t i;
1036 PyObject *s, *temp, *colon = NULL;
1037 PyObject *pieces = NULL, *result = NULL;
1038 PyObject *key, *value;
Guido van Rossum255443b1998-04-10 22:47:14 +00001039
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001040 i = Py_ReprEnter((PyObject *)mp);
1041 if (i != 0) {
1042 return i > 0 ? PyUnicode_FromString("{...}") : NULL;
1043 }
Guido van Rossum255443b1998-04-10 22:47:14 +00001044
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001045 if (mp->ma_used == 0) {
1046 result = PyUnicode_FromString("{}");
1047 goto Done;
1048 }
Tim Petersa7259592001-06-16 05:11:17 +00001049
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001050 pieces = PyList_New(0);
1051 if (pieces == NULL)
1052 goto Done;
Tim Petersa7259592001-06-16 05:11:17 +00001053
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001054 colon = PyUnicode_FromString(": ");
1055 if (colon == NULL)
1056 goto Done;
Tim Petersa7259592001-06-16 05:11:17 +00001057
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001058 /* Do repr() on each key+value pair, and insert ": " between them.
1059 Note that repr may mutate the dict. */
1060 i = 0;
1061 while (PyDict_Next((PyObject *)mp, &i, &key, &value)) {
1062 int status;
1063 /* Prevent repr from deleting value during key format. */
1064 Py_INCREF(value);
1065 s = PyObject_Repr(key);
1066 PyUnicode_Append(&s, colon);
1067 PyUnicode_AppendAndDel(&s, PyObject_Repr(value));
1068 Py_DECREF(value);
1069 if (s == NULL)
1070 goto Done;
1071 status = PyList_Append(pieces, s);
1072 Py_DECREF(s); /* append created a new ref */
1073 if (status < 0)
1074 goto Done;
1075 }
Tim Petersa7259592001-06-16 05:11:17 +00001076
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001077 /* Add "{}" decorations to the first and last items. */
1078 assert(PyList_GET_SIZE(pieces) > 0);
1079 s = PyUnicode_FromString("{");
1080 if (s == NULL)
1081 goto Done;
1082 temp = PyList_GET_ITEM(pieces, 0);
1083 PyUnicode_AppendAndDel(&s, temp);
1084 PyList_SET_ITEM(pieces, 0, s);
1085 if (s == NULL)
1086 goto Done;
Tim Petersa7259592001-06-16 05:11:17 +00001087
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001088 s = PyUnicode_FromString("}");
1089 if (s == NULL)
1090 goto Done;
1091 temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
1092 PyUnicode_AppendAndDel(&temp, s);
1093 PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
1094 if (temp == NULL)
1095 goto Done;
Tim Petersa7259592001-06-16 05:11:17 +00001096
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001097 /* Paste them all together with ", " between. */
1098 s = PyUnicode_FromString(", ");
1099 if (s == NULL)
1100 goto Done;
1101 result = PyUnicode_Join(s, pieces);
1102 Py_DECREF(s);
Tim Petersa7259592001-06-16 05:11:17 +00001103
1104Done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001105 Py_XDECREF(pieces);
1106 Py_XDECREF(colon);
1107 Py_ReprLeave((PyObject *)mp);
1108 return result;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001109}
1110
Martin v. Löwis18e16552006-02-15 17:27:45 +00001111static Py_ssize_t
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001112dict_length(PyDictObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001113{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001114 return mp->ma_used;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001115}
1116
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001117static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001118dict_subscript(PyDictObject *mp, register PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001119{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001120 PyObject *v;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001121 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001122 PyDictEntry *ep;
1123 assert(mp->ma_table != NULL);
1124 if (!PyUnicode_CheckExact(key) ||
1125 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
1126 hash = PyObject_Hash(key);
1127 if (hash == -1)
1128 return NULL;
1129 }
1130 ep = (mp->ma_lookup)(mp, key, hash);
1131 if (ep == NULL)
1132 return NULL;
1133 v = ep->me_value;
1134 if (v == NULL) {
1135 if (!PyDict_CheckExact(mp)) {
1136 /* Look up __missing__ method if we're a subclass. */
1137 PyObject *missing, *res;
1138 static PyObject *missing_str = NULL;
1139 missing = _PyObject_LookupSpecial((PyObject *)mp,
1140 "__missing__",
1141 &missing_str);
1142 if (missing != NULL) {
1143 res = PyObject_CallFunctionObjArgs(missing,
1144 key, NULL);
1145 Py_DECREF(missing);
1146 return res;
1147 }
1148 else if (PyErr_Occurred())
1149 return NULL;
1150 }
1151 set_key_error(key);
1152 return NULL;
1153 }
1154 else
1155 Py_INCREF(v);
1156 return v;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001157}
1158
1159static int
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001160dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001161{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001162 if (w == NULL)
1163 return PyDict_DelItem((PyObject *)mp, v);
1164 else
1165 return PyDict_SetItem((PyObject *)mp, v, w);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001166}
1167
Guido van Rossuma9e7a811997-05-13 21:02:11 +00001168static PyMappingMethods dict_as_mapping = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001169 (lenfunc)dict_length, /*mp_length*/
1170 (binaryfunc)dict_subscript, /*mp_subscript*/
1171 (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001172};
1173
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001174static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001175dict_keys(register PyDictObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001176{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001177 register PyObject *v;
1178 register Py_ssize_t i, j;
1179 PyDictEntry *ep;
1180 Py_ssize_t mask, n;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001181
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001182 again:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001183 n = mp->ma_used;
1184 v = PyList_New(n);
1185 if (v == NULL)
1186 return NULL;
1187 if (n != mp->ma_used) {
1188 /* Durnit. The allocations caused the dict to resize.
1189 * Just start over, this shouldn't normally happen.
1190 */
1191 Py_DECREF(v);
1192 goto again;
1193 }
1194 ep = mp->ma_table;
1195 mask = mp->ma_mask;
1196 for (i = 0, j = 0; i <= mask; i++) {
1197 if (ep[i].me_value != NULL) {
1198 PyObject *key = ep[i].me_key;
1199 Py_INCREF(key);
1200 PyList_SET_ITEM(v, j, key);
1201 j++;
1202 }
1203 }
1204 assert(j == n);
1205 return v;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001206}
1207
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001208static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001209dict_values(register PyDictObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001210{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001211 register PyObject *v;
1212 register Py_ssize_t i, j;
1213 PyDictEntry *ep;
1214 Py_ssize_t mask, n;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001215
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001216 again:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001217 n = mp->ma_used;
1218 v = PyList_New(n);
1219 if (v == NULL)
1220 return NULL;
1221 if (n != mp->ma_used) {
1222 /* Durnit. The allocations caused the dict to resize.
1223 * Just start over, this shouldn't normally happen.
1224 */
1225 Py_DECREF(v);
1226 goto again;
1227 }
1228 ep = mp->ma_table;
1229 mask = mp->ma_mask;
1230 for (i = 0, j = 0; i <= mask; i++) {
1231 if (ep[i].me_value != NULL) {
1232 PyObject *value = ep[i].me_value;
1233 Py_INCREF(value);
1234 PyList_SET_ITEM(v, j, value);
1235 j++;
1236 }
1237 }
1238 assert(j == n);
1239 return v;
Guido van Rossum25831651993-05-19 14:50:45 +00001240}
1241
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001242static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001243dict_items(register PyDictObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001244{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001245 register PyObject *v;
1246 register Py_ssize_t i, j, n;
1247 Py_ssize_t mask;
1248 PyObject *item, *key, *value;
1249 PyDictEntry *ep;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001250
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001251 /* Preallocate the list of tuples, to avoid allocations during
1252 * the loop over the items, which could trigger GC, which
1253 * could resize the dict. :-(
1254 */
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001255 again:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001256 n = mp->ma_used;
1257 v = PyList_New(n);
1258 if (v == NULL)
1259 return NULL;
1260 for (i = 0; i < n; i++) {
1261 item = PyTuple_New(2);
1262 if (item == NULL) {
1263 Py_DECREF(v);
1264 return NULL;
1265 }
1266 PyList_SET_ITEM(v, i, item);
1267 }
1268 if (n != mp->ma_used) {
1269 /* Durnit. The allocations caused the dict to resize.
1270 * Just start over, this shouldn't normally happen.
1271 */
1272 Py_DECREF(v);
1273 goto again;
1274 }
1275 /* Nothing we do below makes any function calls. */
1276 ep = mp->ma_table;
1277 mask = mp->ma_mask;
1278 for (i = 0, j = 0; i <= mask; i++) {
1279 if ((value=ep[i].me_value) != NULL) {
1280 key = ep[i].me_key;
1281 item = PyList_GET_ITEM(v, j);
1282 Py_INCREF(key);
1283 PyTuple_SET_ITEM(item, 0, key);
1284 Py_INCREF(value);
1285 PyTuple_SET_ITEM(item, 1, value);
1286 j++;
1287 }
1288 }
1289 assert(j == n);
1290 return v;
Guido van Rossum25831651993-05-19 14:50:45 +00001291}
1292
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001293static PyObject *
Tim Petersbca1cbc2002-12-09 22:56:13 +00001294dict_fromkeys(PyObject *cls, PyObject *args)
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001295{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001296 PyObject *seq;
1297 PyObject *value = Py_None;
1298 PyObject *it; /* iter(seq) */
1299 PyObject *key;
1300 PyObject *d;
1301 int status;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001302
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001303 if (!PyArg_UnpackTuple(args, "fromkeys", 1, 2, &seq, &value))
1304 return NULL;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001305
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001306 d = PyObject_CallObject(cls, NULL);
1307 if (d == NULL)
1308 return NULL;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001309
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001310 if (PyDict_CheckExact(d) && PyDict_CheckExact(seq)) {
1311 PyDictObject *mp = (PyDictObject *)d;
1312 PyObject *oldvalue;
1313 Py_ssize_t pos = 0;
1314 PyObject *key;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001315 Py_hash_t hash;
Guido van Rossum58da9312007-11-10 23:39:45 +00001316
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001317 if (dictresize(mp, Py_SIZE(seq)))
1318 return NULL;
Guido van Rossum58da9312007-11-10 23:39:45 +00001319
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001320 while (_PyDict_Next(seq, &pos, &key, &oldvalue, &hash)) {
1321 Py_INCREF(key);
1322 Py_INCREF(value);
1323 if (insertdict(mp, key, hash, value))
1324 return NULL;
1325 }
1326 return d;
1327 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001328
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001329 if (PyDict_CheckExact(d) && PyAnySet_CheckExact(seq)) {
1330 PyDictObject *mp = (PyDictObject *)d;
1331 Py_ssize_t pos = 0;
1332 PyObject *key;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001333 Py_hash_t hash;
Guido van Rossumd8faa362007-04-27 19:54:29 +00001334
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001335 if (dictresize(mp, PySet_GET_SIZE(seq)))
1336 return NULL;
Guido van Rossumd8faa362007-04-27 19:54:29 +00001337
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001338 while (_PySet_NextEntry(seq, &pos, &key, &hash)) {
1339 Py_INCREF(key);
1340 Py_INCREF(value);
1341 if (insertdict(mp, key, hash, value))
1342 return NULL;
1343 }
1344 return d;
1345 }
Guido van Rossumd8faa362007-04-27 19:54:29 +00001346
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001347 it = PyObject_GetIter(seq);
1348 if (it == NULL){
1349 Py_DECREF(d);
1350 return NULL;
1351 }
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001352
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001353 if (PyDict_CheckExact(d)) {
1354 while ((key = PyIter_Next(it)) != NULL) {
1355 status = PyDict_SetItem(d, key, value);
1356 Py_DECREF(key);
1357 if (status < 0)
1358 goto Fail;
1359 }
1360 } else {
1361 while ((key = PyIter_Next(it)) != NULL) {
1362 status = PyObject_SetItem(d, key, value);
1363 Py_DECREF(key);
1364 if (status < 0)
1365 goto Fail;
1366 }
1367 }
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001368
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001369 if (PyErr_Occurred())
1370 goto Fail;
1371 Py_DECREF(it);
1372 return d;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001373
1374Fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001375 Py_DECREF(it);
1376 Py_DECREF(d);
1377 return NULL;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001378}
1379
Raymond Hettinger31017ae2004-03-04 08:25:44 +00001380static int
1381dict_update_common(PyObject *self, PyObject *args, PyObject *kwds, char *methname)
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001382{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001383 PyObject *arg = NULL;
1384 int result = 0;
Raymond Hettinger31017ae2004-03-04 08:25:44 +00001385
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001386 if (!PyArg_UnpackTuple(args, methname, 0, 1, &arg))
1387 result = -1;
Raymond Hettinger31017ae2004-03-04 08:25:44 +00001388
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001389 else if (arg != NULL) {
1390 if (PyObject_HasAttrString(arg, "keys"))
1391 result = PyDict_Merge(self, arg, 1);
1392 else
1393 result = PyDict_MergeFromSeq2(self, arg, 1);
1394 }
1395 if (result == 0 && kwds != NULL) {
1396 if (PyArg_ValidateKeywordArguments(kwds))
1397 result = PyDict_Merge(self, kwds, 1);
1398 else
1399 result = -1;
1400 }
1401 return result;
Raymond Hettinger31017ae2004-03-04 08:25:44 +00001402}
1403
1404static PyObject *
1405dict_update(PyObject *self, PyObject *args, PyObject *kwds)
1406{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001407 if (dict_update_common(self, args, kwds, "update") != -1)
1408 Py_RETURN_NONE;
1409 return NULL;
Tim Peters6d6c1a32001-08-02 04:15:00 +00001410}
1411
Guido van Rossum05ac6de2001-08-10 20:28:28 +00001412/* Update unconditionally replaces existing items.
1413 Merge has a 3rd argument 'override'; if set, it acts like Update,
Tim Peters1fc240e2001-10-26 05:06:50 +00001414 otherwise it leaves existing items unchanged.
1415
1416 PyDict_{Update,Merge} update/merge from a mapping object.
1417
Tim Petersf582b822001-12-11 18:51:08 +00001418 PyDict_MergeFromSeq2 updates/merges from any iterable object
Tim Peters1fc240e2001-10-26 05:06:50 +00001419 producing iterable objects of length 2.
1420*/
1421
Tim Petersf582b822001-12-11 18:51:08 +00001422int
Tim Peters1fc240e2001-10-26 05:06:50 +00001423PyDict_MergeFromSeq2(PyObject *d, PyObject *seq2, int override)
1424{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001425 PyObject *it; /* iter(seq2) */
1426 Py_ssize_t i; /* index into seq2 of current element */
1427 PyObject *item; /* seq2[i] */
1428 PyObject *fast; /* item as a 2-tuple or 2-list */
Tim Peters1fc240e2001-10-26 05:06:50 +00001429
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001430 assert(d != NULL);
1431 assert(PyDict_Check(d));
1432 assert(seq2 != NULL);
Tim Peters1fc240e2001-10-26 05:06:50 +00001433
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001434 it = PyObject_GetIter(seq2);
1435 if (it == NULL)
1436 return -1;
Tim Peters1fc240e2001-10-26 05:06:50 +00001437
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001438 for (i = 0; ; ++i) {
1439 PyObject *key, *value;
1440 Py_ssize_t n;
Tim Peters1fc240e2001-10-26 05:06:50 +00001441
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001442 fast = NULL;
1443 item = PyIter_Next(it);
1444 if (item == NULL) {
1445 if (PyErr_Occurred())
1446 goto Fail;
1447 break;
1448 }
Tim Peters1fc240e2001-10-26 05:06:50 +00001449
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001450 /* Convert item to sequence, and verify length 2. */
1451 fast = PySequence_Fast(item, "");
1452 if (fast == NULL) {
1453 if (PyErr_ExceptionMatches(PyExc_TypeError))
1454 PyErr_Format(PyExc_TypeError,
1455 "cannot convert dictionary update "
1456 "sequence element #%zd to a sequence",
1457 i);
1458 goto Fail;
1459 }
1460 n = PySequence_Fast_GET_SIZE(fast);
1461 if (n != 2) {
1462 PyErr_Format(PyExc_ValueError,
1463 "dictionary update sequence element #%zd "
1464 "has length %zd; 2 is required",
1465 i, n);
1466 goto Fail;
1467 }
Tim Peters1fc240e2001-10-26 05:06:50 +00001468
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001469 /* Update/merge with this (key, value) pair. */
1470 key = PySequence_Fast_GET_ITEM(fast, 0);
1471 value = PySequence_Fast_GET_ITEM(fast, 1);
1472 if (override || PyDict_GetItem(d, key) == NULL) {
1473 int status = PyDict_SetItem(d, key, value);
1474 if (status < 0)
1475 goto Fail;
1476 }
1477 Py_DECREF(fast);
1478 Py_DECREF(item);
1479 }
Tim Peters1fc240e2001-10-26 05:06:50 +00001480
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001481 i = 0;
1482 goto Return;
Tim Peters1fc240e2001-10-26 05:06:50 +00001483Fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001484 Py_XDECREF(item);
1485 Py_XDECREF(fast);
1486 i = -1;
Tim Peters1fc240e2001-10-26 05:06:50 +00001487Return:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001488 Py_DECREF(it);
1489 return Py_SAFE_DOWNCAST(i, Py_ssize_t, int);
Tim Peters1fc240e2001-10-26 05:06:50 +00001490}
1491
Tim Peters6d6c1a32001-08-02 04:15:00 +00001492int
1493PyDict_Update(PyObject *a, PyObject *b)
1494{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001495 return PyDict_Merge(a, b, 1);
Guido van Rossum05ac6de2001-08-10 20:28:28 +00001496}
1497
1498int
1499PyDict_Merge(PyObject *a, PyObject *b, int override)
1500{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001501 register PyDictObject *mp, *other;
1502 register Py_ssize_t i;
1503 PyDictEntry *entry;
Tim Peters6d6c1a32001-08-02 04:15:00 +00001504
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001505 /* We accept for the argument either a concrete dictionary object,
1506 * or an abstract "mapping" object. For the former, we can do
1507 * things quite efficiently. For the latter, we only require that
1508 * PyMapping_Keys() and PyObject_GetItem() be supported.
1509 */
1510 if (a == NULL || !PyDict_Check(a) || b == NULL) {
1511 PyErr_BadInternalCall();
1512 return -1;
1513 }
1514 mp = (PyDictObject*)a;
1515 if (PyDict_Check(b)) {
1516 other = (PyDictObject*)b;
1517 if (other == mp || other->ma_used == 0)
1518 /* a.update(a) or a.update({}); nothing to do */
1519 return 0;
1520 if (mp->ma_used == 0)
1521 /* Since the target dict is empty, PyDict_GetItem()
1522 * always returns NULL. Setting override to 1
1523 * skips the unnecessary test.
1524 */
1525 override = 1;
1526 /* Do one big resize at the start, rather than
1527 * incrementally resizing as we insert new items. Expect
1528 * that there will be no (or few) overlapping keys.
1529 */
1530 if ((mp->ma_fill + other->ma_used)*3 >= (mp->ma_mask+1)*2) {
1531 if (dictresize(mp, (mp->ma_used + other->ma_used)*2) != 0)
1532 return -1;
1533 }
1534 for (i = 0; i <= other->ma_mask; i++) {
1535 entry = &other->ma_table[i];
1536 if (entry->me_value != NULL &&
1537 (override ||
1538 PyDict_GetItem(a, entry->me_key) == NULL)) {
1539 Py_INCREF(entry->me_key);
1540 Py_INCREF(entry->me_value);
1541 if (insertdict(mp, entry->me_key,
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001542 entry->me_hash,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001543 entry->me_value) != 0)
1544 return -1;
1545 }
1546 }
1547 }
1548 else {
1549 /* Do it the generic, slower way */
1550 PyObject *keys = PyMapping_Keys(b);
1551 PyObject *iter;
1552 PyObject *key, *value;
1553 int status;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001554
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001555 if (keys == NULL)
1556 /* Docstring says this is equivalent to E.keys() so
1557 * if E doesn't have a .keys() method we want
1558 * AttributeError to percolate up. Might as well
1559 * do the same for any other error.
1560 */
1561 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001562
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001563 iter = PyObject_GetIter(keys);
1564 Py_DECREF(keys);
1565 if (iter == NULL)
1566 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001567
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001568 for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) {
1569 if (!override && PyDict_GetItem(a, key) != NULL) {
1570 Py_DECREF(key);
1571 continue;
1572 }
1573 value = PyObject_GetItem(b, key);
1574 if (value == NULL) {
1575 Py_DECREF(iter);
1576 Py_DECREF(key);
1577 return -1;
1578 }
1579 status = PyDict_SetItem(a, key, value);
1580 Py_DECREF(key);
1581 Py_DECREF(value);
1582 if (status < 0) {
1583 Py_DECREF(iter);
1584 return -1;
1585 }
1586 }
1587 Py_DECREF(iter);
1588 if (PyErr_Occurred())
1589 /* Iterator completed, via error */
1590 return -1;
1591 }
1592 return 0;
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001593}
1594
1595static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001596dict_copy(register PyDictObject *mp)
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001597{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001598 return PyDict_Copy((PyObject*)mp);
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001599}
1600
1601PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001602PyDict_Copy(PyObject *o)
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001603{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001604 PyObject *copy;
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001605
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001606 if (o == NULL || !PyDict_Check(o)) {
1607 PyErr_BadInternalCall();
1608 return NULL;
1609 }
1610 copy = PyDict_New();
1611 if (copy == NULL)
1612 return NULL;
1613 if (PyDict_Merge(copy, o, 1) == 0)
1614 return copy;
1615 Py_DECREF(copy);
1616 return NULL;
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001617}
1618
Martin v. Löwis18e16552006-02-15 17:27:45 +00001619Py_ssize_t
Tim Peters1f5871e2000-07-04 17:44:48 +00001620PyDict_Size(PyObject *mp)
Guido van Rossum4199fac1993-11-05 10:18:44 +00001621{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001622 if (mp == NULL || !PyDict_Check(mp)) {
1623 PyErr_BadInternalCall();
1624 return -1;
1625 }
1626 return ((PyDictObject *)mp)->ma_used;
Guido van Rossum4199fac1993-11-05 10:18:44 +00001627}
1628
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001629PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001630PyDict_Keys(PyObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001631{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001632 if (mp == NULL || !PyDict_Check(mp)) {
1633 PyErr_BadInternalCall();
1634 return NULL;
1635 }
1636 return dict_keys((PyDictObject *)mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001637}
1638
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001639PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001640PyDict_Values(PyObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001641{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001642 if (mp == NULL || !PyDict_Check(mp)) {
1643 PyErr_BadInternalCall();
1644 return NULL;
1645 }
1646 return dict_values((PyDictObject *)mp);
Guido van Rossum25831651993-05-19 14:50:45 +00001647}
1648
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001649PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001650PyDict_Items(PyObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001651{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001652 if (mp == NULL || !PyDict_Check(mp)) {
1653 PyErr_BadInternalCall();
1654 return NULL;
1655 }
1656 return dict_items((PyDictObject *)mp);
Guido van Rossum25831651993-05-19 14:50:45 +00001657}
1658
Tim Peterse63415e2001-05-08 04:38:29 +00001659/* Return 1 if dicts equal, 0 if not, -1 if error.
1660 * Gets out as soon as any difference is detected.
1661 * Uses only Py_EQ comparison.
1662 */
1663static int
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001664dict_equal(PyDictObject *a, PyDictObject *b)
Tim Peterse63415e2001-05-08 04:38:29 +00001665{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001666 Py_ssize_t i;
Tim Peterse63415e2001-05-08 04:38:29 +00001667
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001668 if (a->ma_used != b->ma_used)
1669 /* can't be equal if # of entries differ */
1670 return 0;
Tim Peterseb28ef22001-06-02 05:27:19 +00001671
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001672 /* Same # of entries -- check all of 'em. Exit early on any diff. */
1673 for (i = 0; i <= a->ma_mask; i++) {
1674 PyObject *aval = a->ma_table[i].me_value;
1675 if (aval != NULL) {
1676 int cmp;
1677 PyObject *bval;
1678 PyObject *key = a->ma_table[i].me_key;
1679 /* temporarily bump aval's refcount to ensure it stays
1680 alive until we're done with it */
1681 Py_INCREF(aval);
1682 /* ditto for key */
1683 Py_INCREF(key);
1684 bval = PyDict_GetItemWithError((PyObject *)b, key);
1685 Py_DECREF(key);
1686 if (bval == NULL) {
1687 Py_DECREF(aval);
1688 if (PyErr_Occurred())
1689 return -1;
1690 return 0;
1691 }
1692 cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
1693 Py_DECREF(aval);
1694 if (cmp <= 0) /* error or not equal */
1695 return cmp;
1696 }
1697 }
1698 return 1;
Tim Peterse63415e2001-05-08 04:38:29 +00001699 }
1700
1701static PyObject *
1702dict_richcompare(PyObject *v, PyObject *w, int op)
1703{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001704 int cmp;
1705 PyObject *res;
Tim Peterse63415e2001-05-08 04:38:29 +00001706
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001707 if (!PyDict_Check(v) || !PyDict_Check(w)) {
1708 res = Py_NotImplemented;
1709 }
1710 else if (op == Py_EQ || op == Py_NE) {
1711 cmp = dict_equal((PyDictObject *)v, (PyDictObject *)w);
1712 if (cmp < 0)
1713 return NULL;
1714 res = (cmp == (op == Py_EQ)) ? Py_True : Py_False;
1715 }
1716 else
1717 res = Py_NotImplemented;
1718 Py_INCREF(res);
1719 return res;
Tim Peterse63415e2001-05-08 04:38:29 +00001720 }
1721
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001722static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001723dict_contains(register PyDictObject *mp, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001724{
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001725 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001726 PyDictEntry *ep;
Thomas Wouters4d70c3d2006-06-08 14:42:34 +00001727
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001728 if (!PyUnicode_CheckExact(key) ||
1729 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
1730 hash = PyObject_Hash(key);
1731 if (hash == -1)
1732 return NULL;
1733 }
1734 ep = (mp->ma_lookup)(mp, key, hash);
1735 if (ep == NULL)
1736 return NULL;
1737 return PyBool_FromLong(ep->me_value != NULL);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001738}
1739
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001740static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001741dict_get(register PyDictObject *mp, PyObject *args)
Barry Warsawc38c5da1997-10-06 17:49:20 +00001742{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001743 PyObject *key;
1744 PyObject *failobj = Py_None;
1745 PyObject *val = NULL;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001746 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001747 PyDictEntry *ep;
Barry Warsawc38c5da1997-10-06 17:49:20 +00001748
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001749 if (!PyArg_UnpackTuple(args, "get", 1, 2, &key, &failobj))
1750 return NULL;
Barry Warsawc38c5da1997-10-06 17:49:20 +00001751
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001752 if (!PyUnicode_CheckExact(key) ||
1753 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
1754 hash = PyObject_Hash(key);
1755 if (hash == -1)
1756 return NULL;
1757 }
1758 ep = (mp->ma_lookup)(mp, key, hash);
1759 if (ep == NULL)
1760 return NULL;
1761 val = ep->me_value;
1762 if (val == NULL)
1763 val = failobj;
1764 Py_INCREF(val);
1765 return val;
Barry Warsawc38c5da1997-10-06 17:49:20 +00001766}
1767
1768
1769static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001770dict_setdefault(register PyDictObject *mp, PyObject *args)
Guido van Rossum164452c2000-08-08 16:12:54 +00001771{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001772 PyObject *key;
1773 PyObject *failobj = Py_None;
1774 PyObject *val = NULL;
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001775 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001776 PyDictEntry *ep;
Guido van Rossum164452c2000-08-08 16:12:54 +00001777
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001778 if (!PyArg_UnpackTuple(args, "setdefault", 1, 2, &key, &failobj))
1779 return NULL;
Guido van Rossum164452c2000-08-08 16:12:54 +00001780
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001781 if (!PyUnicode_CheckExact(key) ||
1782 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
1783 hash = PyObject_Hash(key);
1784 if (hash == -1)
1785 return NULL;
1786 }
1787 ep = (mp->ma_lookup)(mp, key, hash);
1788 if (ep == NULL)
1789 return NULL;
1790 val = ep->me_value;
1791 if (val == NULL) {
1792 val = failobj;
1793 if (PyDict_SetItem((PyObject*)mp, key, failobj))
1794 val = NULL;
1795 }
1796 Py_XINCREF(val);
1797 return val;
Guido van Rossum164452c2000-08-08 16:12:54 +00001798}
1799
1800
1801static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001802dict_clear(register PyDictObject *mp)
Guido van Rossumfb8f1ca1997-03-21 21:55:12 +00001803{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001804 PyDict_Clear((PyObject *)mp);
1805 Py_RETURN_NONE;
Guido van Rossumfb8f1ca1997-03-21 21:55:12 +00001806}
1807
Guido van Rossumba6ab842000-12-12 22:02:18 +00001808static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001809dict_pop(PyDictObject *mp, PyObject *args)
Guido van Rossume027d982002-04-12 15:11:59 +00001810{
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001811 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001812 PyDictEntry *ep;
1813 PyObject *old_value, *old_key;
1814 PyObject *key, *deflt = NULL;
Guido van Rossume027d982002-04-12 15:11:59 +00001815
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001816 if(!PyArg_UnpackTuple(args, "pop", 1, 2, &key, &deflt))
1817 return NULL;
1818 if (mp->ma_used == 0) {
1819 if (deflt) {
1820 Py_INCREF(deflt);
1821 return deflt;
1822 }
Raymond Hettingerdd421542010-10-30 08:10:29 +00001823 set_key_error(key);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001824 return NULL;
1825 }
1826 if (!PyUnicode_CheckExact(key) ||
1827 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
1828 hash = PyObject_Hash(key);
1829 if (hash == -1)
1830 return NULL;
1831 }
1832 ep = (mp->ma_lookup)(mp, key, hash);
1833 if (ep == NULL)
1834 return NULL;
1835 if (ep->me_value == NULL) {
1836 if (deflt) {
1837 Py_INCREF(deflt);
1838 return deflt;
1839 }
1840 set_key_error(key);
1841 return NULL;
1842 }
1843 old_key = ep->me_key;
1844 Py_INCREF(dummy);
1845 ep->me_key = dummy;
1846 old_value = ep->me_value;
1847 ep->me_value = NULL;
1848 mp->ma_used--;
1849 Py_DECREF(old_key);
1850 return old_value;
Guido van Rossume027d982002-04-12 15:11:59 +00001851}
1852
1853static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001854dict_popitem(PyDictObject *mp)
Guido van Rossumba6ab842000-12-12 22:02:18 +00001855{
Benjamin Peterson8f67d082010-10-17 20:54:53 +00001856 Py_hash_t i = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001857 PyDictEntry *ep;
1858 PyObject *res;
Guido van Rossumba6ab842000-12-12 22:02:18 +00001859
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001860 /* Allocate the result tuple before checking the size. Believe it
1861 * or not, this allocation could trigger a garbage collection which
1862 * could empty the dict, so if we checked the size first and that
1863 * happened, the result would be an infinite loop (searching for an
1864 * entry that no longer exists). Note that the usual popitem()
1865 * idiom is "while d: k, v = d.popitem()". so needing to throw the
1866 * tuple away if the dict *is* empty isn't a significant
1867 * inefficiency -- possible, but unlikely in practice.
1868 */
1869 res = PyTuple_New(2);
1870 if (res == NULL)
1871 return NULL;
1872 if (mp->ma_used == 0) {
1873 Py_DECREF(res);
1874 PyErr_SetString(PyExc_KeyError,
1875 "popitem(): dictionary is empty");
1876 return NULL;
1877 }
1878 /* Set ep to "the first" dict entry with a value. We abuse the hash
1879 * field of slot 0 to hold a search finger:
1880 * If slot 0 has a value, use slot 0.
1881 * Else slot 0 is being used to hold a search finger,
1882 * and we use its hash value as the first index to look.
1883 */
1884 ep = &mp->ma_table[0];
1885 if (ep->me_value == NULL) {
1886 i = ep->me_hash;
1887 /* The hash field may be a real hash value, or it may be a
1888 * legit search finger, or it may be a once-legit search
1889 * finger that's out of bounds now because it wrapped around
1890 * or the table shrunk -- simply make sure it's in bounds now.
1891 */
1892 if (i > mp->ma_mask || i < 1)
1893 i = 1; /* skip slot 0 */
1894 while ((ep = &mp->ma_table[i])->me_value == NULL) {
1895 i++;
1896 if (i > mp->ma_mask)
1897 i = 1;
1898 }
1899 }
1900 PyTuple_SET_ITEM(res, 0, ep->me_key);
1901 PyTuple_SET_ITEM(res, 1, ep->me_value);
1902 Py_INCREF(dummy);
1903 ep->me_key = dummy;
1904 ep->me_value = NULL;
1905 mp->ma_used--;
1906 assert(mp->ma_table[0].me_value == NULL);
1907 mp->ma_table[0].me_hash = i + 1; /* next place to start */
1908 return res;
Guido van Rossumba6ab842000-12-12 22:02:18 +00001909}
1910
Jeremy Hylton8caad492000-06-23 14:18:11 +00001911static int
1912dict_traverse(PyObject *op, visitproc visit, void *arg)
1913{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001914 Py_ssize_t i = 0;
1915 PyObject *pk;
1916 PyObject *pv;
Jeremy Hylton8caad492000-06-23 14:18:11 +00001917
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001918 while (PyDict_Next(op, &i, &pk, &pv)) {
1919 Py_VISIT(pk);
1920 Py_VISIT(pv);
1921 }
1922 return 0;
Jeremy Hylton8caad492000-06-23 14:18:11 +00001923}
1924
1925static int
1926dict_tp_clear(PyObject *op)
1927{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001928 PyDict_Clear(op);
1929 return 0;
Jeremy Hylton8caad492000-06-23 14:18:11 +00001930}
1931
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001932static PyObject *dictiter_new(PyDictObject *, PyTypeObject *);
Guido van Rossum09e563a2001-05-01 12:10:21 +00001933
Martin v. Löwis00709aa2008-06-04 14:18:43 +00001934static PyObject *
1935dict_sizeof(PyDictObject *mp)
1936{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001937 Py_ssize_t res;
Martin v. Löwis00709aa2008-06-04 14:18:43 +00001938
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001939 res = sizeof(PyDictObject);
1940 if (mp->ma_table != mp->ma_smalltable)
1941 res = res + (mp->ma_mask + 1) * sizeof(PyDictEntry);
1942 return PyLong_FromSsize_t(res);
Martin v. Löwis00709aa2008-06-04 14:18:43 +00001943}
1944
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001945PyDoc_STRVAR(contains__doc__,
1946"D.__contains__(k) -> True if D has a key k, else False");
1947
1948PyDoc_STRVAR(getitem__doc__, "x.__getitem__(y) <==> x[y]");
1949
Martin v. Löwis00709aa2008-06-04 14:18:43 +00001950PyDoc_STRVAR(sizeof__doc__,
1951"D.__sizeof__() -> size of D in memory, in bytes");
1952
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001953PyDoc_STRVAR(get__doc__,
Guido van Rossumefae8862002-09-04 11:29:45 +00001954"D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.");
Tim Petersf7f88b12000-12-13 23:18:45 +00001955
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001956PyDoc_STRVAR(setdefault_doc__,
Guido van Rossumefae8862002-09-04 11:29:45 +00001957"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 +00001958
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001959PyDoc_STRVAR(pop__doc__,
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00001960"D.pop(k[,d]) -> v, remove specified key and return the corresponding value.\n\
Raymond Hettingera3e1e4c2003-03-06 23:54:28 +00001961If key is not found, d is returned if given, otherwise KeyError is raised");
Guido van Rossume027d982002-04-12 15:11:59 +00001962
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001963PyDoc_STRVAR(popitem__doc__,
Tim Petersf7f88b12000-12-13 23:18:45 +00001964"D.popitem() -> (k, v), remove and return some (key, value) pair as a\n\
Benjamin Petersonf10a79a2008-10-11 00:49:57 +000019652-tuple; but raise KeyError if D is empty.");
Tim Petersf7f88b12000-12-13 23:18:45 +00001966
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001967PyDoc_STRVAR(update__doc__,
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00001968"D.update(E, **F) -> None. Update D from dict/iterable E and F.\n"
1969"If E has a .keys() method, does: for k in E: D[k] = E[k]\n\
1970If E lacks .keys() method, does: for (k, v) in E: D[k] = v\n\
1971In either case, this is followed by: for k in F: D[k] = F[k]");
Tim Petersf7f88b12000-12-13 23:18:45 +00001972
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001973PyDoc_STRVAR(fromkeys__doc__,
1974"dict.fromkeys(S[,v]) -> New dict with keys from S and values equal to v.\n\
1975v defaults to None.");
1976
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001977PyDoc_STRVAR(clear__doc__,
1978"D.clear() -> None. Remove all items from D.");
Tim Petersf7f88b12000-12-13 23:18:45 +00001979
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001980PyDoc_STRVAR(copy__doc__,
1981"D.copy() -> a shallow copy of D");
Tim Petersf7f88b12000-12-13 23:18:45 +00001982
Guido van Rossumb90c8482007-02-10 01:11:45 +00001983/* Forward */
1984static PyObject *dictkeys_new(PyObject *);
1985static PyObject *dictitems_new(PyObject *);
1986static PyObject *dictvalues_new(PyObject *);
1987
Guido van Rossum45c85d12007-07-27 16:31:40 +00001988PyDoc_STRVAR(keys__doc__,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001989 "D.keys() -> a set-like object providing a view on D's keys");
Guido van Rossum45c85d12007-07-27 16:31:40 +00001990PyDoc_STRVAR(items__doc__,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001991 "D.items() -> a set-like object providing a view on D's items");
Guido van Rossum45c85d12007-07-27 16:31:40 +00001992PyDoc_STRVAR(values__doc__,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001993 "D.values() -> an object providing a view on D's values");
Guido van Rossumb90c8482007-02-10 01:11:45 +00001994
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001995static PyMethodDef mapp_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001996 {"__contains__",(PyCFunction)dict_contains, METH_O | METH_COEXIST,
1997 contains__doc__},
1998 {"__getitem__", (PyCFunction)dict_subscript, METH_O | METH_COEXIST,
1999 getitem__doc__},
2000 {"__sizeof__", (PyCFunction)dict_sizeof, METH_NOARGS,
2001 sizeof__doc__},
2002 {"get", (PyCFunction)dict_get, METH_VARARGS,
2003 get__doc__},
2004 {"setdefault", (PyCFunction)dict_setdefault, METH_VARARGS,
2005 setdefault_doc__},
2006 {"pop", (PyCFunction)dict_pop, METH_VARARGS,
2007 pop__doc__},
2008 {"popitem", (PyCFunction)dict_popitem, METH_NOARGS,
2009 popitem__doc__},
2010 {"keys", (PyCFunction)dictkeys_new, METH_NOARGS,
2011 keys__doc__},
2012 {"items", (PyCFunction)dictitems_new, METH_NOARGS,
2013 items__doc__},
2014 {"values", (PyCFunction)dictvalues_new, METH_NOARGS,
2015 values__doc__},
2016 {"update", (PyCFunction)dict_update, METH_VARARGS | METH_KEYWORDS,
2017 update__doc__},
2018 {"fromkeys", (PyCFunction)dict_fromkeys, METH_VARARGS | METH_CLASS,
2019 fromkeys__doc__},
2020 {"clear", (PyCFunction)dict_clear, METH_NOARGS,
2021 clear__doc__},
2022 {"copy", (PyCFunction)dict_copy, METH_NOARGS,
2023 copy__doc__},
2024 {NULL, NULL} /* sentinel */
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002025};
2026
Thomas Wouters4d70c3d2006-06-08 14:42:34 +00002027/* Return 1 if `key` is in dict `op`, 0 if not, and -1 on error. */
Raymond Hettingerbc0f2ab2003-11-25 21:12:14 +00002028int
2029PyDict_Contains(PyObject *op, PyObject *key)
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002030{
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002031 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002032 PyDictObject *mp = (PyDictObject *)op;
2033 PyDictEntry *ep;
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002034
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002035 if (!PyUnicode_CheckExact(key) ||
2036 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
2037 hash = PyObject_Hash(key);
2038 if (hash == -1)
2039 return -1;
2040 }
2041 ep = (mp->ma_lookup)(mp, key, hash);
2042 return ep == NULL ? -1 : (ep->me_value != NULL);
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002043}
2044
Thomas Wouterscf297e42007-02-23 15:07:44 +00002045/* Internal version of PyDict_Contains used when the hash value is already known */
2046int
Benjamin Peterson8f67d082010-10-17 20:54:53 +00002047_PyDict_Contains(PyObject *op, PyObject *key, Py_hash_t hash)
Thomas Wouterscf297e42007-02-23 15:07:44 +00002048{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002049 PyDictObject *mp = (PyDictObject *)op;
2050 PyDictEntry *ep;
Thomas Wouterscf297e42007-02-23 15:07:44 +00002051
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002052 ep = (mp->ma_lookup)(mp, key, hash);
2053 return ep == NULL ? -1 : (ep->me_value != NULL);
Thomas Wouterscf297e42007-02-23 15:07:44 +00002054}
2055
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002056/* Hack to implement "key in dict" */
2057static PySequenceMethods dict_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002058 0, /* sq_length */
2059 0, /* sq_concat */
2060 0, /* sq_repeat */
2061 0, /* sq_item */
2062 0, /* sq_slice */
2063 0, /* sq_ass_item */
2064 0, /* sq_ass_slice */
2065 PyDict_Contains, /* sq_contains */
2066 0, /* sq_inplace_concat */
2067 0, /* sq_inplace_repeat */
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002068};
2069
Guido van Rossum09e563a2001-05-01 12:10:21 +00002070static PyObject *
Tim Peters6d6c1a32001-08-02 04:15:00 +00002071dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2072{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002073 PyObject *self;
Tim Peters6d6c1a32001-08-02 04:15:00 +00002074
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002075 assert(type != NULL && type->tp_alloc != NULL);
2076 self = type->tp_alloc(type, 0);
2077 if (self != NULL) {
2078 PyDictObject *d = (PyDictObject *)self;
2079 /* It's guaranteed that tp->alloc zeroed out the struct. */
2080 assert(d->ma_table == NULL && d->ma_fill == 0 && d->ma_used == 0);
2081 INIT_NONZERO_DICT_SLOTS(d);
2082 d->ma_lookup = lookdict_unicode;
Ezio Melotti13925002011-03-16 11:05:33 +02002083 /* The object has been implicitly tracked by tp_alloc */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002084 if (type == &PyDict_Type)
2085 _PyObject_GC_UNTRACK(d);
Tim Peters6d6c1a32001-08-02 04:15:00 +00002086#ifdef SHOW_CONVERSION_COUNTS
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002087 ++created;
Tim Peters6d6c1a32001-08-02 04:15:00 +00002088#endif
Antoine Pitrou3a652b12009-03-23 18:52:06 +00002089#ifdef SHOW_TRACK_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002090 if (_PyObject_GC_IS_TRACKED(d))
2091 count_tracked++;
2092 else
2093 count_untracked++;
Antoine Pitrou3a652b12009-03-23 18:52:06 +00002094#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002095 }
2096 return self;
Tim Peters6d6c1a32001-08-02 04:15:00 +00002097}
2098
Tim Peters25786c02001-09-02 08:22:48 +00002099static int
2100dict_init(PyObject *self, PyObject *args, PyObject *kwds)
2101{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002102 return dict_update_common(self, args, kwds, "dict");
Tim Peters25786c02001-09-02 08:22:48 +00002103}
2104
Tim Peters6d6c1a32001-08-02 04:15:00 +00002105static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00002106dict_iter(PyDictObject *dict)
Guido van Rossum09e563a2001-05-01 12:10:21 +00002107{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002108 return dictiter_new(dict, &PyDictIterKey_Type);
Guido van Rossum09e563a2001-05-01 12:10:21 +00002109}
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002110
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002111PyDoc_STRVAR(dictionary_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002112"dict() -> new empty dictionary\n"
Tim Petersa427a2b2001-10-29 22:25:45 +00002113"dict(mapping) -> new dictionary initialized from a mapping object's\n"
Ezio Melotti7f807b72010-03-01 04:08:34 +00002114" (key, value) pairs\n"
2115"dict(iterable) -> new dictionary initialized as if via:\n"
Tim Peters4d859532001-10-27 18:27:48 +00002116" d = {}\n"
Ezio Melotti7f807b72010-03-01 04:08:34 +00002117" for k, v in iterable:\n"
Just van Rossuma797d812002-11-23 09:45:04 +00002118" d[k] = v\n"
2119"dict(**kwargs) -> new dictionary initialized with the name=value pairs\n"
2120" in the keyword argument list. For example: dict(one=1, two=2)");
Tim Peters25786c02001-09-02 08:22:48 +00002121
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002122PyTypeObject PyDict_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002123 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2124 "dict",
2125 sizeof(PyDictObject),
2126 0,
2127 (destructor)dict_dealloc, /* tp_dealloc */
2128 0, /* tp_print */
2129 0, /* tp_getattr */
2130 0, /* tp_setattr */
2131 0, /* tp_reserved */
2132 (reprfunc)dict_repr, /* tp_repr */
2133 0, /* tp_as_number */
2134 &dict_as_sequence, /* tp_as_sequence */
2135 &dict_as_mapping, /* tp_as_mapping */
Georg Brandl00da4e02010-10-18 07:32:48 +00002136 PyObject_HashNotImplemented, /* tp_hash */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002137 0, /* tp_call */
2138 0, /* tp_str */
2139 PyObject_GenericGetAttr, /* tp_getattro */
2140 0, /* tp_setattro */
2141 0, /* tp_as_buffer */
2142 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2143 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_DICT_SUBCLASS, /* tp_flags */
2144 dictionary_doc, /* tp_doc */
2145 dict_traverse, /* tp_traverse */
2146 dict_tp_clear, /* tp_clear */
2147 dict_richcompare, /* tp_richcompare */
2148 0, /* tp_weaklistoffset */
2149 (getiterfunc)dict_iter, /* tp_iter */
2150 0, /* tp_iternext */
2151 mapp_methods, /* tp_methods */
2152 0, /* tp_members */
2153 0, /* tp_getset */
2154 0, /* tp_base */
2155 0, /* tp_dict */
2156 0, /* tp_descr_get */
2157 0, /* tp_descr_set */
2158 0, /* tp_dictoffset */
2159 dict_init, /* tp_init */
2160 PyType_GenericAlloc, /* tp_alloc */
2161 dict_new, /* tp_new */
2162 PyObject_GC_Del, /* tp_free */
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002163};
2164
Guido van Rossum3cca2451997-05-16 14:23:33 +00002165/* For backward compatibility with old dictionary interface */
2166
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002167PyObject *
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +00002168PyDict_GetItemString(PyObject *v, const char *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002169{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002170 PyObject *kv, *rv;
2171 kv = PyUnicode_FromString(key);
2172 if (kv == NULL)
2173 return NULL;
2174 rv = PyDict_GetItem(v, kv);
2175 Py_DECREF(kv);
2176 return rv;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002177}
2178
2179int
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +00002180PyDict_SetItemString(PyObject *v, const char *key, PyObject *item)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002181{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002182 PyObject *kv;
2183 int err;
2184 kv = PyUnicode_FromString(key);
2185 if (kv == NULL)
2186 return -1;
2187 PyUnicode_InternInPlace(&kv); /* XXX Should we really? */
2188 err = PyDict_SetItem(v, kv, item);
2189 Py_DECREF(kv);
2190 return err;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002191}
2192
2193int
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +00002194PyDict_DelItemString(PyObject *v, const char *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002195{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002196 PyObject *kv;
2197 int err;
2198 kv = PyUnicode_FromString(key);
2199 if (kv == NULL)
2200 return -1;
2201 err = PyDict_DelItem(v, kv);
2202 Py_DECREF(kv);
2203 return err;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002204}
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002205
Raymond Hettinger019a1482004-03-18 02:41:19 +00002206/* Dictionary iterator types */
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002207
2208typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002209 PyObject_HEAD
2210 PyDictObject *di_dict; /* Set to NULL when iterator is exhausted */
2211 Py_ssize_t di_used;
2212 Py_ssize_t di_pos;
2213 PyObject* di_result; /* reusable result tuple for iteritems */
2214 Py_ssize_t len;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002215} dictiterobject;
2216
2217static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00002218dictiter_new(PyDictObject *dict, PyTypeObject *itertype)
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002219{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002220 dictiterobject *di;
2221 di = PyObject_GC_New(dictiterobject, itertype);
2222 if (di == NULL)
2223 return NULL;
2224 Py_INCREF(dict);
2225 di->di_dict = dict;
2226 di->di_used = dict->ma_used;
2227 di->di_pos = 0;
2228 di->len = dict->ma_used;
2229 if (itertype == &PyDictIterItem_Type) {
2230 di->di_result = PyTuple_Pack(2, Py_None, Py_None);
2231 if (di->di_result == NULL) {
2232 Py_DECREF(di);
2233 return NULL;
2234 }
2235 }
2236 else
2237 di->di_result = NULL;
2238 _PyObject_GC_TRACK(di);
2239 return (PyObject *)di;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002240}
2241
2242static void
2243dictiter_dealloc(dictiterobject *di)
2244{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002245 Py_XDECREF(di->di_dict);
2246 Py_XDECREF(di->di_result);
2247 PyObject_GC_Del(di);
Antoine Pitrou7ddda782009-01-01 15:35:33 +00002248}
2249
2250static int
2251dictiter_traverse(dictiterobject *di, visitproc visit, void *arg)
2252{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002253 Py_VISIT(di->di_dict);
2254 Py_VISIT(di->di_result);
2255 return 0;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002256}
2257
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002258static PyObject *
Raymond Hettinger0ce6dc82004-03-18 08:38:00 +00002259dictiter_len(dictiterobject *di)
2260{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002261 Py_ssize_t len = 0;
2262 if (di->di_dict != NULL && di->di_used == di->di_dict->ma_used)
2263 len = di->len;
2264 return PyLong_FromSize_t(len);
Raymond Hettinger0ce6dc82004-03-18 08:38:00 +00002265}
2266
Guido van Rossumb90c8482007-02-10 01:11:45 +00002267PyDoc_STRVAR(length_hint_doc,
2268 "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002269
2270static PyMethodDef dictiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002271 {"__length_hint__", (PyCFunction)dictiter_len, METH_NOARGS,
2272 length_hint_doc},
2273 {NULL, NULL} /* sentinel */
Raymond Hettinger0ce6dc82004-03-18 08:38:00 +00002274};
2275
Raymond Hettinger019a1482004-03-18 02:41:19 +00002276static PyObject *dictiter_iternextkey(dictiterobject *di)
Guido van Rossum213c7a62001-04-23 14:08:49 +00002277{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002278 PyObject *key;
2279 register Py_ssize_t i, mask;
2280 register PyDictEntry *ep;
2281 PyDictObject *d = di->di_dict;
Guido van Rossum213c7a62001-04-23 14:08:49 +00002282
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002283 if (d == NULL)
2284 return NULL;
2285 assert (PyDict_Check(d));
Guido van Rossum2147df72002-07-16 20:30:22 +00002286
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002287 if (di->di_used != d->ma_used) {
2288 PyErr_SetString(PyExc_RuntimeError,
2289 "dictionary changed size during iteration");
2290 di->di_used = -1; /* Make this state sticky */
2291 return NULL;
2292 }
Guido van Rossum2147df72002-07-16 20:30:22 +00002293
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002294 i = di->di_pos;
2295 if (i < 0)
2296 goto fail;
2297 ep = d->ma_table;
2298 mask = d->ma_mask;
2299 while (i <= mask && ep[i].me_value == NULL)
2300 i++;
2301 di->di_pos = i+1;
2302 if (i > mask)
2303 goto fail;
2304 di->len--;
2305 key = ep[i].me_key;
2306 Py_INCREF(key);
2307 return key;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002308
2309fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002310 Py_DECREF(d);
2311 di->di_dict = NULL;
2312 return NULL;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002313}
2314
Raymond Hettinger019a1482004-03-18 02:41:19 +00002315PyTypeObject PyDictIterKey_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002316 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2317 "dict_keyiterator", /* tp_name */
2318 sizeof(dictiterobject), /* tp_basicsize */
2319 0, /* tp_itemsize */
2320 /* methods */
2321 (destructor)dictiter_dealloc, /* tp_dealloc */
2322 0, /* tp_print */
2323 0, /* tp_getattr */
2324 0, /* tp_setattr */
2325 0, /* tp_reserved */
2326 0, /* tp_repr */
2327 0, /* tp_as_number */
2328 0, /* tp_as_sequence */
2329 0, /* tp_as_mapping */
2330 0, /* tp_hash */
2331 0, /* tp_call */
2332 0, /* tp_str */
2333 PyObject_GenericGetAttr, /* tp_getattro */
2334 0, /* tp_setattro */
2335 0, /* tp_as_buffer */
2336 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2337 0, /* tp_doc */
2338 (traverseproc)dictiter_traverse, /* tp_traverse */
2339 0, /* tp_clear */
2340 0, /* tp_richcompare */
2341 0, /* tp_weaklistoffset */
2342 PyObject_SelfIter, /* tp_iter */
2343 (iternextfunc)dictiter_iternextkey, /* tp_iternext */
2344 dictiter_methods, /* tp_methods */
2345 0,
Raymond Hettinger019a1482004-03-18 02:41:19 +00002346};
2347
2348static PyObject *dictiter_iternextvalue(dictiterobject *di)
2349{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002350 PyObject *value;
2351 register Py_ssize_t i, mask;
2352 register PyDictEntry *ep;
2353 PyDictObject *d = di->di_dict;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002354
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002355 if (d == NULL)
2356 return NULL;
2357 assert (PyDict_Check(d));
Raymond Hettinger019a1482004-03-18 02:41:19 +00002358
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002359 if (di->di_used != d->ma_used) {
2360 PyErr_SetString(PyExc_RuntimeError,
2361 "dictionary changed size during iteration");
2362 di->di_used = -1; /* Make this state sticky */
2363 return NULL;
2364 }
Raymond Hettinger019a1482004-03-18 02:41:19 +00002365
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002366 i = di->di_pos;
2367 mask = d->ma_mask;
2368 if (i < 0 || i > mask)
2369 goto fail;
2370 ep = d->ma_table;
2371 while ((value=ep[i].me_value) == NULL) {
2372 i++;
2373 if (i > mask)
2374 goto fail;
2375 }
2376 di->di_pos = i+1;
2377 di->len--;
2378 Py_INCREF(value);
2379 return value;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002380
2381fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002382 Py_DECREF(d);
2383 di->di_dict = NULL;
2384 return NULL;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002385}
2386
2387PyTypeObject PyDictIterValue_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002388 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2389 "dict_valueiterator", /* tp_name */
2390 sizeof(dictiterobject), /* tp_basicsize */
2391 0, /* tp_itemsize */
2392 /* methods */
2393 (destructor)dictiter_dealloc, /* tp_dealloc */
2394 0, /* tp_print */
2395 0, /* tp_getattr */
2396 0, /* tp_setattr */
2397 0, /* tp_reserved */
2398 0, /* tp_repr */
2399 0, /* tp_as_number */
2400 0, /* tp_as_sequence */
2401 0, /* tp_as_mapping */
2402 0, /* tp_hash */
2403 0, /* tp_call */
2404 0, /* tp_str */
2405 PyObject_GenericGetAttr, /* tp_getattro */
2406 0, /* tp_setattro */
2407 0, /* tp_as_buffer */
2408 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2409 0, /* tp_doc */
2410 (traverseproc)dictiter_traverse, /* tp_traverse */
2411 0, /* tp_clear */
2412 0, /* tp_richcompare */
2413 0, /* tp_weaklistoffset */
2414 PyObject_SelfIter, /* tp_iter */
2415 (iternextfunc)dictiter_iternextvalue, /* tp_iternext */
2416 dictiter_methods, /* tp_methods */
2417 0,
Raymond Hettinger019a1482004-03-18 02:41:19 +00002418};
2419
2420static PyObject *dictiter_iternextitem(dictiterobject *di)
2421{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002422 PyObject *key, *value, *result = di->di_result;
2423 register Py_ssize_t i, mask;
2424 register PyDictEntry *ep;
2425 PyDictObject *d = di->di_dict;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002426
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002427 if (d == NULL)
2428 return NULL;
2429 assert (PyDict_Check(d));
Raymond Hettinger019a1482004-03-18 02:41:19 +00002430
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002431 if (di->di_used != d->ma_used) {
2432 PyErr_SetString(PyExc_RuntimeError,
2433 "dictionary changed size during iteration");
2434 di->di_used = -1; /* Make this state sticky */
2435 return NULL;
2436 }
Raymond Hettinger019a1482004-03-18 02:41:19 +00002437
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002438 i = di->di_pos;
2439 if (i < 0)
2440 goto fail;
2441 ep = d->ma_table;
2442 mask = d->ma_mask;
2443 while (i <= mask && ep[i].me_value == NULL)
2444 i++;
2445 di->di_pos = i+1;
2446 if (i > mask)
2447 goto fail;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002448
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002449 if (result->ob_refcnt == 1) {
2450 Py_INCREF(result);
2451 Py_DECREF(PyTuple_GET_ITEM(result, 0));
2452 Py_DECREF(PyTuple_GET_ITEM(result, 1));
2453 } else {
2454 result = PyTuple_New(2);
2455 if (result == NULL)
2456 return NULL;
2457 }
2458 di->len--;
2459 key = ep[i].me_key;
2460 value = ep[i].me_value;
2461 Py_INCREF(key);
2462 Py_INCREF(value);
2463 PyTuple_SET_ITEM(result, 0, key);
2464 PyTuple_SET_ITEM(result, 1, value);
2465 return result;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002466
2467fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002468 Py_DECREF(d);
2469 di->di_dict = NULL;
2470 return NULL;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002471}
2472
2473PyTypeObject PyDictIterItem_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002474 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2475 "dict_itemiterator", /* tp_name */
2476 sizeof(dictiterobject), /* tp_basicsize */
2477 0, /* tp_itemsize */
2478 /* methods */
2479 (destructor)dictiter_dealloc, /* tp_dealloc */
2480 0, /* tp_print */
2481 0, /* tp_getattr */
2482 0, /* tp_setattr */
2483 0, /* tp_reserved */
2484 0, /* tp_repr */
2485 0, /* tp_as_number */
2486 0, /* tp_as_sequence */
2487 0, /* tp_as_mapping */
2488 0, /* tp_hash */
2489 0, /* tp_call */
2490 0, /* tp_str */
2491 PyObject_GenericGetAttr, /* tp_getattro */
2492 0, /* tp_setattro */
2493 0, /* tp_as_buffer */
2494 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2495 0, /* tp_doc */
2496 (traverseproc)dictiter_traverse, /* tp_traverse */
2497 0, /* tp_clear */
2498 0, /* tp_richcompare */
2499 0, /* tp_weaklistoffset */
2500 PyObject_SelfIter, /* tp_iter */
2501 (iternextfunc)dictiter_iternextitem, /* tp_iternext */
2502 dictiter_methods, /* tp_methods */
2503 0,
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002504};
Guido van Rossumb90c8482007-02-10 01:11:45 +00002505
2506
Guido van Rossum3ac67412007-02-10 18:55:06 +00002507/***********************************************/
Guido van Rossumb90c8482007-02-10 01:11:45 +00002508/* View objects for keys(), items(), values(). */
Guido van Rossum3ac67412007-02-10 18:55:06 +00002509/***********************************************/
2510
Guido van Rossumb90c8482007-02-10 01:11:45 +00002511/* The instance lay-out is the same for all three; but the type differs. */
2512
2513typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002514 PyObject_HEAD
2515 PyDictObject *dv_dict;
Guido van Rossumb90c8482007-02-10 01:11:45 +00002516} dictviewobject;
2517
2518
2519static void
Guido van Rossum3ac67412007-02-10 18:55:06 +00002520dictview_dealloc(dictviewobject *dv)
Guido van Rossumb90c8482007-02-10 01:11:45 +00002521{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002522 Py_XDECREF(dv->dv_dict);
2523 PyObject_GC_Del(dv);
Antoine Pitrou7ddda782009-01-01 15:35:33 +00002524}
2525
2526static int
2527dictview_traverse(dictviewobject *dv, visitproc visit, void *arg)
2528{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002529 Py_VISIT(dv->dv_dict);
2530 return 0;
Guido van Rossumb90c8482007-02-10 01:11:45 +00002531}
2532
Guido van Rossum83825ac2007-02-10 04:54:19 +00002533static Py_ssize_t
Guido van Rossum3ac67412007-02-10 18:55:06 +00002534dictview_len(dictviewobject *dv)
Guido van Rossumb90c8482007-02-10 01:11:45 +00002535{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002536 Py_ssize_t len = 0;
2537 if (dv->dv_dict != NULL)
2538 len = dv->dv_dict->ma_used;
2539 return len;
Guido van Rossumb90c8482007-02-10 01:11:45 +00002540}
2541
2542static PyObject *
2543dictview_new(PyObject *dict, PyTypeObject *type)
2544{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002545 dictviewobject *dv;
2546 if (dict == NULL) {
2547 PyErr_BadInternalCall();
2548 return NULL;
2549 }
2550 if (!PyDict_Check(dict)) {
2551 /* XXX Get rid of this restriction later */
2552 PyErr_Format(PyExc_TypeError,
2553 "%s() requires a dict argument, not '%s'",
2554 type->tp_name, dict->ob_type->tp_name);
2555 return NULL;
2556 }
2557 dv = PyObject_GC_New(dictviewobject, type);
2558 if (dv == NULL)
2559 return NULL;
2560 Py_INCREF(dict);
2561 dv->dv_dict = (PyDictObject *)dict;
2562 _PyObject_GC_TRACK(dv);
2563 return (PyObject *)dv;
Guido van Rossumb90c8482007-02-10 01:11:45 +00002564}
2565
Neal Norwitze36f2ba2007-02-26 23:12:28 +00002566/* TODO(guido): The views objects are not complete:
2567
2568 * support more set operations
2569 * support arbitrary mappings?
2570 - either these should be static or exported in dictobject.h
2571 - if public then they should probably be in builtins
2572*/
2573
Guido van Rossumaac530c2007-08-24 22:33:45 +00002574/* Return 1 if self is a subset of other, iterating over self;
2575 0 if not; -1 if an error occurred. */
Guido van Rossumd9214d12007-02-12 02:23:40 +00002576static int
2577all_contained_in(PyObject *self, PyObject *other)
2578{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002579 PyObject *iter = PyObject_GetIter(self);
2580 int ok = 1;
Guido van Rossumd9214d12007-02-12 02:23:40 +00002581
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002582 if (iter == NULL)
2583 return -1;
2584 for (;;) {
2585 PyObject *next = PyIter_Next(iter);
2586 if (next == NULL) {
2587 if (PyErr_Occurred())
2588 ok = -1;
2589 break;
2590 }
2591 ok = PySequence_Contains(other, next);
2592 Py_DECREF(next);
2593 if (ok <= 0)
2594 break;
2595 }
2596 Py_DECREF(iter);
2597 return ok;
Guido van Rossumd9214d12007-02-12 02:23:40 +00002598}
2599
2600static PyObject *
2601dictview_richcompare(PyObject *self, PyObject *other, int op)
2602{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002603 Py_ssize_t len_self, len_other;
2604 int ok;
2605 PyObject *result;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002606
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002607 assert(self != NULL);
2608 assert(PyDictViewSet_Check(self));
2609 assert(other != NULL);
Guido van Rossumd9214d12007-02-12 02:23:40 +00002610
Brian Curtindfc80e32011-08-10 20:28:54 -05002611 if (!PyAnySet_Check(other) && !PyDictViewSet_Check(other))
2612 Py_RETURN_NOTIMPLEMENTED;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002613
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002614 len_self = PyObject_Size(self);
2615 if (len_self < 0)
2616 return NULL;
2617 len_other = PyObject_Size(other);
2618 if (len_other < 0)
2619 return NULL;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002620
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002621 ok = 0;
2622 switch(op) {
Guido van Rossumaac530c2007-08-24 22:33:45 +00002623
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002624 case Py_NE:
2625 case Py_EQ:
2626 if (len_self == len_other)
2627 ok = all_contained_in(self, other);
2628 if (op == Py_NE && ok >= 0)
2629 ok = !ok;
2630 break;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002631
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002632 case Py_LT:
2633 if (len_self < len_other)
2634 ok = all_contained_in(self, other);
2635 break;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002636
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002637 case Py_LE:
2638 if (len_self <= len_other)
2639 ok = all_contained_in(self, other);
2640 break;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002641
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002642 case Py_GT:
2643 if (len_self > len_other)
2644 ok = all_contained_in(other, self);
2645 break;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002646
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002647 case Py_GE:
2648 if (len_self >= len_other)
2649 ok = all_contained_in(other, self);
2650 break;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002651
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002652 }
2653 if (ok < 0)
2654 return NULL;
2655 result = ok ? Py_True : Py_False;
2656 Py_INCREF(result);
2657 return result;
Guido van Rossumd9214d12007-02-12 02:23:40 +00002658}
2659
Raymond Hettingerb0d56af2009-03-03 10:52:49 +00002660static PyObject *
2661dictview_repr(dictviewobject *dv)
2662{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002663 PyObject *seq;
2664 PyObject *result;
Raymond Hettingerb0d56af2009-03-03 10:52:49 +00002665
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002666 seq = PySequence_List((PyObject *)dv);
2667 if (seq == NULL)
2668 return NULL;
2669
2670 result = PyUnicode_FromFormat("%s(%R)", Py_TYPE(dv)->tp_name, seq);
2671 Py_DECREF(seq);
2672 return result;
Raymond Hettingerb0d56af2009-03-03 10:52:49 +00002673}
2674
Guido van Rossum3ac67412007-02-10 18:55:06 +00002675/*** dict_keys ***/
Guido van Rossumb90c8482007-02-10 01:11:45 +00002676
2677static PyObject *
Guido van Rossum3ac67412007-02-10 18:55:06 +00002678dictkeys_iter(dictviewobject *dv)
Guido van Rossumb90c8482007-02-10 01:11:45 +00002679{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002680 if (dv->dv_dict == NULL) {
2681 Py_RETURN_NONE;
2682 }
2683 return dictiter_new(dv->dv_dict, &PyDictIterKey_Type);
Guido van Rossum3ac67412007-02-10 18:55:06 +00002684}
2685
2686static int
2687dictkeys_contains(dictviewobject *dv, PyObject *obj)
2688{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002689 if (dv->dv_dict == NULL)
2690 return 0;
2691 return PyDict_Contains((PyObject *)dv->dv_dict, obj);
Guido van Rossumb90c8482007-02-10 01:11:45 +00002692}
2693
Guido van Rossum83825ac2007-02-10 04:54:19 +00002694static PySequenceMethods dictkeys_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002695 (lenfunc)dictview_len, /* sq_length */
2696 0, /* sq_concat */
2697 0, /* sq_repeat */
2698 0, /* sq_item */
2699 0, /* sq_slice */
2700 0, /* sq_ass_item */
2701 0, /* sq_ass_slice */
2702 (objobjproc)dictkeys_contains, /* sq_contains */
Guido van Rossum83825ac2007-02-10 04:54:19 +00002703};
2704
Guido van Rossum523259b2007-08-24 23:41:22 +00002705static PyObject*
2706dictviews_sub(PyObject* self, PyObject *other)
2707{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002708 PyObject *result = PySet_New(self);
2709 PyObject *tmp;
2710 if (result == NULL)
2711 return NULL;
Guido van Rossum523259b2007-08-24 23:41:22 +00002712
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002713 tmp = PyObject_CallMethod(result, "difference_update", "O", other);
2714 if (tmp == NULL) {
2715 Py_DECREF(result);
2716 return NULL;
2717 }
Guido van Rossum523259b2007-08-24 23:41:22 +00002718
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002719 Py_DECREF(tmp);
2720 return result;
Guido van Rossum523259b2007-08-24 23:41:22 +00002721}
2722
2723static PyObject*
2724dictviews_and(PyObject* self, PyObject *other)
2725{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002726 PyObject *result = PySet_New(self);
2727 PyObject *tmp;
2728 if (result == NULL)
2729 return NULL;
Guido van Rossum523259b2007-08-24 23:41:22 +00002730
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002731 tmp = PyObject_CallMethod(result, "intersection_update", "O", other);
2732 if (tmp == NULL) {
2733 Py_DECREF(result);
2734 return NULL;
2735 }
Guido van Rossum523259b2007-08-24 23:41:22 +00002736
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002737 Py_DECREF(tmp);
2738 return result;
Guido van Rossum523259b2007-08-24 23:41:22 +00002739}
2740
2741static PyObject*
2742dictviews_or(PyObject* self, PyObject *other)
2743{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002744 PyObject *result = PySet_New(self);
2745 PyObject *tmp;
2746 if (result == NULL)
2747 return NULL;
Guido van Rossum523259b2007-08-24 23:41:22 +00002748
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002749 tmp = PyObject_CallMethod(result, "update", "O", other);
2750 if (tmp == NULL) {
2751 Py_DECREF(result);
2752 return NULL;
2753 }
Guido van Rossum523259b2007-08-24 23:41:22 +00002754
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002755 Py_DECREF(tmp);
2756 return result;
Guido van Rossum523259b2007-08-24 23:41:22 +00002757}
2758
2759static PyObject*
2760dictviews_xor(PyObject* self, PyObject *other)
2761{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002762 PyObject *result = PySet_New(self);
2763 PyObject *tmp;
2764 if (result == NULL)
2765 return NULL;
Guido van Rossum523259b2007-08-24 23:41:22 +00002766
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002767 tmp = PyObject_CallMethod(result, "symmetric_difference_update", "O",
2768 other);
2769 if (tmp == NULL) {
2770 Py_DECREF(result);
2771 return NULL;
2772 }
Guido van Rossum523259b2007-08-24 23:41:22 +00002773
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002774 Py_DECREF(tmp);
2775 return result;
Guido van Rossum523259b2007-08-24 23:41:22 +00002776}
2777
2778static PyNumberMethods dictviews_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002779 0, /*nb_add*/
2780 (binaryfunc)dictviews_sub, /*nb_subtract*/
2781 0, /*nb_multiply*/
2782 0, /*nb_remainder*/
2783 0, /*nb_divmod*/
2784 0, /*nb_power*/
2785 0, /*nb_negative*/
2786 0, /*nb_positive*/
2787 0, /*nb_absolute*/
2788 0, /*nb_bool*/
2789 0, /*nb_invert*/
2790 0, /*nb_lshift*/
2791 0, /*nb_rshift*/
2792 (binaryfunc)dictviews_and, /*nb_and*/
2793 (binaryfunc)dictviews_xor, /*nb_xor*/
2794 (binaryfunc)dictviews_or, /*nb_or*/
Guido van Rossum523259b2007-08-24 23:41:22 +00002795};
2796
Daniel Stutzbach045b3ba2010-09-02 15:06:06 +00002797static PyObject*
2798dictviews_isdisjoint(PyObject *self, PyObject *other)
2799{
2800 PyObject *it;
2801 PyObject *item = NULL;
2802
2803 if (self == other) {
2804 if (dictview_len((dictviewobject *)self) == 0)
2805 Py_RETURN_TRUE;
2806 else
2807 Py_RETURN_FALSE;
2808 }
2809
2810 /* Iterate over the shorter object (only if other is a set,
2811 * because PySequence_Contains may be expensive otherwise): */
2812 if (PyAnySet_Check(other) || PyDictViewSet_Check(other)) {
2813 Py_ssize_t len_self = dictview_len((dictviewobject *)self);
2814 Py_ssize_t len_other = PyObject_Size(other);
2815 if (len_other == -1)
2816 return NULL;
2817
2818 if ((len_other > len_self)) {
2819 PyObject *tmp = other;
2820 other = self;
2821 self = tmp;
2822 }
2823 }
2824
2825 it = PyObject_GetIter(other);
2826 if (it == NULL)
2827 return NULL;
2828
2829 while ((item = PyIter_Next(it)) != NULL) {
2830 int contains = PySequence_Contains(self, item);
2831 Py_DECREF(item);
2832 if (contains == -1) {
2833 Py_DECREF(it);
2834 return NULL;
2835 }
2836
2837 if (contains) {
2838 Py_DECREF(it);
2839 Py_RETURN_FALSE;
2840 }
2841 }
2842 Py_DECREF(it);
2843 if (PyErr_Occurred())
2844 return NULL; /* PyIter_Next raised an exception. */
2845 Py_RETURN_TRUE;
2846}
2847
2848PyDoc_STRVAR(isdisjoint_doc,
2849"Return True if the view and the given iterable have a null intersection.");
2850
Guido van Rossumb90c8482007-02-10 01:11:45 +00002851static PyMethodDef dictkeys_methods[] = {
Daniel Stutzbach045b3ba2010-09-02 15:06:06 +00002852 {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
2853 isdisjoint_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002854 {NULL, NULL} /* sentinel */
Guido van Rossumb90c8482007-02-10 01:11:45 +00002855};
2856
2857PyTypeObject PyDictKeys_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002858 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2859 "dict_keys", /* tp_name */
2860 sizeof(dictviewobject), /* tp_basicsize */
2861 0, /* tp_itemsize */
2862 /* methods */
2863 (destructor)dictview_dealloc, /* tp_dealloc */
2864 0, /* tp_print */
2865 0, /* tp_getattr */
2866 0, /* tp_setattr */
2867 0, /* tp_reserved */
2868 (reprfunc)dictview_repr, /* tp_repr */
2869 &dictviews_as_number, /* tp_as_number */
2870 &dictkeys_as_sequence, /* tp_as_sequence */
2871 0, /* tp_as_mapping */
2872 0, /* tp_hash */
2873 0, /* tp_call */
2874 0, /* tp_str */
2875 PyObject_GenericGetAttr, /* tp_getattro */
2876 0, /* tp_setattro */
2877 0, /* tp_as_buffer */
2878 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2879 0, /* tp_doc */
2880 (traverseproc)dictview_traverse, /* tp_traverse */
2881 0, /* tp_clear */
2882 dictview_richcompare, /* tp_richcompare */
2883 0, /* tp_weaklistoffset */
2884 (getiterfunc)dictkeys_iter, /* tp_iter */
2885 0, /* tp_iternext */
2886 dictkeys_methods, /* tp_methods */
2887 0,
Guido van Rossumb90c8482007-02-10 01:11:45 +00002888};
2889
2890static PyObject *
2891dictkeys_new(PyObject *dict)
2892{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002893 return dictview_new(dict, &PyDictKeys_Type);
Guido van Rossumb90c8482007-02-10 01:11:45 +00002894}
2895
Guido van Rossum3ac67412007-02-10 18:55:06 +00002896/*** dict_items ***/
Guido van Rossumb90c8482007-02-10 01:11:45 +00002897
2898static PyObject *
Guido van Rossum3ac67412007-02-10 18:55:06 +00002899dictitems_iter(dictviewobject *dv)
Guido van Rossumb90c8482007-02-10 01:11:45 +00002900{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002901 if (dv->dv_dict == NULL) {
2902 Py_RETURN_NONE;
2903 }
2904 return dictiter_new(dv->dv_dict, &PyDictIterItem_Type);
Guido van Rossum3ac67412007-02-10 18:55:06 +00002905}
2906
2907static int
2908dictitems_contains(dictviewobject *dv, PyObject *obj)
2909{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002910 PyObject *key, *value, *found;
2911 if (dv->dv_dict == NULL)
2912 return 0;
2913 if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 2)
2914 return 0;
2915 key = PyTuple_GET_ITEM(obj, 0);
2916 value = PyTuple_GET_ITEM(obj, 1);
2917 found = PyDict_GetItem((PyObject *)dv->dv_dict, key);
2918 if (found == NULL) {
2919 if (PyErr_Occurred())
2920 return -1;
2921 return 0;
2922 }
2923 return PyObject_RichCompareBool(value, found, Py_EQ);
Guido van Rossumb90c8482007-02-10 01:11:45 +00002924}
2925
Guido van Rossum83825ac2007-02-10 04:54:19 +00002926static PySequenceMethods dictitems_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002927 (lenfunc)dictview_len, /* sq_length */
2928 0, /* sq_concat */
2929 0, /* sq_repeat */
2930 0, /* sq_item */
2931 0, /* sq_slice */
2932 0, /* sq_ass_item */
2933 0, /* sq_ass_slice */
2934 (objobjproc)dictitems_contains, /* sq_contains */
Guido van Rossum83825ac2007-02-10 04:54:19 +00002935};
2936
Guido van Rossumb90c8482007-02-10 01:11:45 +00002937static PyMethodDef dictitems_methods[] = {
Daniel Stutzbach045b3ba2010-09-02 15:06:06 +00002938 {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
2939 isdisjoint_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002940 {NULL, NULL} /* sentinel */
Guido van Rossumb90c8482007-02-10 01:11:45 +00002941};
2942
2943PyTypeObject PyDictItems_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002944 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2945 "dict_items", /* tp_name */
2946 sizeof(dictviewobject), /* tp_basicsize */
2947 0, /* tp_itemsize */
2948 /* methods */
2949 (destructor)dictview_dealloc, /* tp_dealloc */
2950 0, /* tp_print */
2951 0, /* tp_getattr */
2952 0, /* tp_setattr */
2953 0, /* tp_reserved */
2954 (reprfunc)dictview_repr, /* tp_repr */
2955 &dictviews_as_number, /* tp_as_number */
2956 &dictitems_as_sequence, /* tp_as_sequence */
2957 0, /* tp_as_mapping */
2958 0, /* tp_hash */
2959 0, /* tp_call */
2960 0, /* tp_str */
2961 PyObject_GenericGetAttr, /* tp_getattro */
2962 0, /* tp_setattro */
2963 0, /* tp_as_buffer */
2964 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2965 0, /* tp_doc */
2966 (traverseproc)dictview_traverse, /* tp_traverse */
2967 0, /* tp_clear */
2968 dictview_richcompare, /* tp_richcompare */
2969 0, /* tp_weaklistoffset */
2970 (getiterfunc)dictitems_iter, /* tp_iter */
2971 0, /* tp_iternext */
2972 dictitems_methods, /* tp_methods */
2973 0,
Guido van Rossumb90c8482007-02-10 01:11:45 +00002974};
2975
2976static PyObject *
2977dictitems_new(PyObject *dict)
2978{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002979 return dictview_new(dict, &PyDictItems_Type);
Guido van Rossumb90c8482007-02-10 01:11:45 +00002980}
2981
Guido van Rossum3ac67412007-02-10 18:55:06 +00002982/*** dict_values ***/
Guido van Rossumb90c8482007-02-10 01:11:45 +00002983
2984static PyObject *
Guido van Rossum3ac67412007-02-10 18:55:06 +00002985dictvalues_iter(dictviewobject *dv)
Guido van Rossumb90c8482007-02-10 01:11:45 +00002986{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002987 if (dv->dv_dict == NULL) {
2988 Py_RETURN_NONE;
2989 }
2990 return dictiter_new(dv->dv_dict, &PyDictIterValue_Type);
Guido van Rossumb90c8482007-02-10 01:11:45 +00002991}
2992
Guido van Rossum83825ac2007-02-10 04:54:19 +00002993static PySequenceMethods dictvalues_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002994 (lenfunc)dictview_len, /* sq_length */
2995 0, /* sq_concat */
2996 0, /* sq_repeat */
2997 0, /* sq_item */
2998 0, /* sq_slice */
2999 0, /* sq_ass_item */
3000 0, /* sq_ass_slice */
3001 (objobjproc)0, /* sq_contains */
Guido van Rossum83825ac2007-02-10 04:54:19 +00003002};
3003
Guido van Rossumb90c8482007-02-10 01:11:45 +00003004static PyMethodDef dictvalues_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003005 {NULL, NULL} /* sentinel */
Guido van Rossumb90c8482007-02-10 01:11:45 +00003006};
3007
3008PyTypeObject PyDictValues_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003009 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3010 "dict_values", /* tp_name */
3011 sizeof(dictviewobject), /* tp_basicsize */
3012 0, /* tp_itemsize */
3013 /* methods */
3014 (destructor)dictview_dealloc, /* tp_dealloc */
3015 0, /* tp_print */
3016 0, /* tp_getattr */
3017 0, /* tp_setattr */
3018 0, /* tp_reserved */
3019 (reprfunc)dictview_repr, /* tp_repr */
3020 0, /* tp_as_number */
3021 &dictvalues_as_sequence, /* tp_as_sequence */
3022 0, /* tp_as_mapping */
3023 0, /* tp_hash */
3024 0, /* tp_call */
3025 0, /* tp_str */
3026 PyObject_GenericGetAttr, /* tp_getattro */
3027 0, /* tp_setattro */
3028 0, /* tp_as_buffer */
3029 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3030 0, /* tp_doc */
3031 (traverseproc)dictview_traverse, /* tp_traverse */
3032 0, /* tp_clear */
3033 0, /* tp_richcompare */
3034 0, /* tp_weaklistoffset */
3035 (getiterfunc)dictvalues_iter, /* tp_iter */
3036 0, /* tp_iternext */
3037 dictvalues_methods, /* tp_methods */
3038 0,
Guido van Rossumb90c8482007-02-10 01:11:45 +00003039};
3040
3041static PyObject *
3042dictvalues_new(PyObject *dict)
3043{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003044 return dictview_new(dict, &PyDictValues_Type);
Guido van Rossumb90c8482007-02-10 01:11:45 +00003045}