blob: 241790ceba27d0212b05d73e3372198aa1dbe2a7 [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
127Theoretical Python 2.5 headache: hash codes are only C "long", but
128sizeof(Py_ssize_t) > sizeof(long) may be possible. In that case, and if a
129dict is genuinely huge, then only the slots directly reachable via indexing
130by a C long can be the first slot in a probe sequence. The probe sequence
131will still eventually reach every slot in the table, but the collision rate
132on initial probes may be much higher than this scheme was designed for.
133Getting a hash code as fat as Py_ssize_t is the only real cure. But in
134practice, this probably won't make a lick of difference for many years (at
135which point everyone will have terabytes of RAM on 64-bit boxes).
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000136*/
Tim Petersdea48ec2001-05-22 20:40:22 +0000137
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000138/* Object used as dummy key to fill deleted entries */
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000139static PyObject *dummy = NULL; /* Initialized by first call to newPyDictObject() */
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000140
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000141#ifdef Py_REF_DEBUG
142PyObject *
143_PyDict_Dummy(void)
144{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000145 return dummy;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000146}
147#endif
148
Fred Drake1bff34a2000-08-31 19:31:38 +0000149/* forward declarations */
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000150static PyDictEntry *
151lookdict_unicode(PyDictObject *mp, PyObject *key, long hash);
Fred Drake1bff34a2000-08-31 19:31:38 +0000152
153#ifdef SHOW_CONVERSION_COUNTS
154static long created = 0L;
155static long converted = 0L;
156
157static void
158show_counts(void)
159{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000160 fprintf(stderr, "created %ld string dicts\n", created);
161 fprintf(stderr, "converted %ld to normal dicts\n", converted);
162 fprintf(stderr, "%.2f%% conversion rate\n", (100.0*converted)/created);
Fred Drake1bff34a2000-08-31 19:31:38 +0000163}
164#endif
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000165
Christian Heimes77c02eb2008-02-09 02:18:51 +0000166/* Debug statistic to compare allocations with reuse through the free list */
167#undef SHOW_ALLOC_COUNT
168#ifdef SHOW_ALLOC_COUNT
169static size_t count_alloc = 0;
170static size_t count_reuse = 0;
171
172static void
173show_alloc(void)
174{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000175 fprintf(stderr, "Dict allocations: %" PY_FORMAT_SIZE_T "d\n",
176 count_alloc);
177 fprintf(stderr, "Dict reuse through freelist: %" PY_FORMAT_SIZE_T
178 "d\n", count_reuse);
179 fprintf(stderr, "%.2f%% reuse rate\n\n",
180 (100.0*count_reuse/(count_alloc+count_reuse)));
Christian Heimes77c02eb2008-02-09 02:18:51 +0000181}
182#endif
183
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000184/* Debug statistic to count GC tracking of dicts */
185#ifdef SHOW_TRACK_COUNT
186static Py_ssize_t count_untracked = 0;
187static Py_ssize_t count_tracked = 0;
188
189static void
190show_track(void)
191{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000192 fprintf(stderr, "Dicts created: %" PY_FORMAT_SIZE_T "d\n",
193 count_tracked + count_untracked);
194 fprintf(stderr, "Dicts tracked by the GC: %" PY_FORMAT_SIZE_T
195 "d\n", count_tracked);
196 fprintf(stderr, "%.2f%% dict tracking rate\n\n",
197 (100.0*count_tracked/(count_untracked+count_tracked)));
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000198}
199#endif
200
201
Tim Peters6d6c1a32001-08-02 04:15:00 +0000202/* Initialization macros.
203 There are two ways to create a dict: PyDict_New() is the main C API
204 function, and the tp_new slot maps to dict_new(). In the latter case we
205 can save a little time over what PyDict_New does because it's guaranteed
206 that the PyDictObject struct is already zeroed out.
207 Everyone except dict_new() should use EMPTY_TO_MINSIZE (unless they have
208 an excellent reason not to).
209*/
210
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000211#define INIT_NONZERO_DICT_SLOTS(mp) do { \
212 (mp)->ma_table = (mp)->ma_smalltable; \
213 (mp)->ma_mask = PyDict_MINSIZE - 1; \
Tim Peters6d6c1a32001-08-02 04:15:00 +0000214 } while(0)
215
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000216#define EMPTY_TO_MINSIZE(mp) do { \
217 memset((mp)->ma_smalltable, 0, sizeof((mp)->ma_smalltable)); \
218 (mp)->ma_used = (mp)->ma_fill = 0; \
219 INIT_NONZERO_DICT_SLOTS(mp); \
Tim Petersdea48ec2001-05-22 20:40:22 +0000220 } while(0)
221
Raymond Hettinger43442782004-03-17 21:55:03 +0000222/* Dictionary reuse scheme to save calls to malloc, free, and memset */
Christian Heimes2202f872008-02-06 14:31:34 +0000223#ifndef PyDict_MAXFREELIST
224#define PyDict_MAXFREELIST 80
225#endif
226static PyDictObject *free_list[PyDict_MAXFREELIST];
227static int numfree = 0;
Raymond Hettinger43442782004-03-17 21:55:03 +0000228
Christian Heimes77c02eb2008-02-09 02:18:51 +0000229void
230PyDict_Fini(void)
231{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000232 PyDictObject *op;
Christian Heimes77c02eb2008-02-09 02:18:51 +0000233
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000234 while (numfree) {
235 op = free_list[--numfree];
236 assert(PyDict_CheckExact(op));
237 PyObject_GC_Del(op);
238 }
Christian Heimes77c02eb2008-02-09 02:18:51 +0000239}
240
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000241PyObject *
Thomas Wouters78890102000-07-22 19:25:51 +0000242PyDict_New(void)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000243{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000244 register PyDictObject *mp;
245 if (dummy == NULL) { /* Auto-initialize dummy */
246 dummy = PyUnicode_FromString("<dummy key>");
247 if (dummy == NULL)
248 return NULL;
Fred Drake1bff34a2000-08-31 19:31:38 +0000249#ifdef SHOW_CONVERSION_COUNTS
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000250 Py_AtExit(show_counts);
Fred Drake1bff34a2000-08-31 19:31:38 +0000251#endif
Christian Heimes77c02eb2008-02-09 02:18:51 +0000252#ifdef SHOW_ALLOC_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000253 Py_AtExit(show_alloc);
Christian Heimes77c02eb2008-02-09 02:18:51 +0000254#endif
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000255#ifdef SHOW_TRACK_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000256 Py_AtExit(show_track);
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000257#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000258 }
259 if (numfree) {
260 mp = free_list[--numfree];
261 assert (mp != NULL);
262 assert (Py_TYPE(mp) == &PyDict_Type);
263 _Py_NewReference((PyObject *)mp);
264 if (mp->ma_fill) {
265 EMPTY_TO_MINSIZE(mp);
266 } else {
267 /* At least set ma_table and ma_mask; these are wrong
268 if an empty but presized dict is added to freelist */
269 INIT_NONZERO_DICT_SLOTS(mp);
270 }
271 assert (mp->ma_used == 0);
272 assert (mp->ma_table == mp->ma_smalltable);
273 assert (mp->ma_mask == PyDict_MINSIZE - 1);
Christian Heimes77c02eb2008-02-09 02:18:51 +0000274#ifdef SHOW_ALLOC_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000275 count_reuse++;
Christian Heimes77c02eb2008-02-09 02:18:51 +0000276#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000277 } else {
278 mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
279 if (mp == NULL)
280 return NULL;
281 EMPTY_TO_MINSIZE(mp);
Christian Heimes77c02eb2008-02-09 02:18:51 +0000282#ifdef SHOW_ALLOC_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000283 count_alloc++;
Christian Heimes77c02eb2008-02-09 02:18:51 +0000284#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000285 }
286 mp->ma_lookup = lookdict_unicode;
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000287#ifdef SHOW_TRACK_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000288 count_untracked++;
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000289#endif
Fred Drake1bff34a2000-08-31 19:31:38 +0000290#ifdef SHOW_CONVERSION_COUNTS
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000291 ++created;
Fred Drake1bff34a2000-08-31 19:31:38 +0000292#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000293 return (PyObject *)mp;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000294}
295
296/*
297The basic lookup function used by all operations.
Guido van Rossum16e93a81997-01-28 00:00:11 +0000298This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000299Open addressing is preferred over chaining since the link overhead for
300chaining would be substantial (100% with typical malloc overhead).
301
Tim Peterseb28ef22001-06-02 05:27:19 +0000302The initial probe index is computed as hash mod the table size. Subsequent
303probe indices are computed as explained earlier.
Guido van Rossum2bc13791999-03-24 19:06:42 +0000304
305All arithmetic on hash should ignore overflow.
Guido van Rossum16e93a81997-01-28 00:00:11 +0000306
Guido van Rossumdc5f6b22006-08-24 21:29:26 +0000307The details in this version are due to Tim Peters, building on many past
Tim Peterseb28ef22001-06-02 05:27:19 +0000308contributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and
Guido van Rossumdc5f6b22006-08-24 21:29:26 +0000309Christian Tismer.
Fred Drake1bff34a2000-08-31 19:31:38 +0000310
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000311lookdict() is general-purpose, and may return NULL if (and only if) a
312comparison raises an exception (this was new in Python 2.5).
Guido van Rossum89d8c602007-09-18 17:26:56 +0000313lookdict_unicode() below is specialized to string keys, comparison of which can
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000314never raise an exception; that function can never return NULL. For both, when
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000315the key isn't found a PyDictEntry* is returned for which the me_value field is
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000316NULL; this is the slot in the dict at which the key would have been found, and
317the caller can (if it wishes) add the <key, value> pair to the returned
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000318PyDictEntry*.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000319*/
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000320static PyDictEntry *
321lookdict(PyDictObject *mp, PyObject *key, register long hash)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000322{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000323 register size_t i;
324 register size_t perturb;
325 register PyDictEntry *freeslot;
326 register size_t mask = (size_t)mp->ma_mask;
327 PyDictEntry *ep0 = mp->ma_table;
328 register PyDictEntry *ep;
329 register int cmp;
330 PyObject *startkey;
Tim Peterseb28ef22001-06-02 05:27:19 +0000331
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000332 i = (size_t)hash & mask;
333 ep = &ep0[i];
334 if (ep->me_key == NULL || ep->me_key == key)
335 return ep;
Tim Peters7b5d0af2001-06-03 04:14:43 +0000336
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000337 if (ep->me_key == dummy)
338 freeslot = ep;
339 else {
340 if (ep->me_hash == hash) {
341 startkey = ep->me_key;
342 Py_INCREF(startkey);
343 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
344 Py_DECREF(startkey);
345 if (cmp < 0)
346 return NULL;
347 if (ep0 == mp->ma_table && ep->me_key == startkey) {
348 if (cmp > 0)
349 return ep;
350 }
351 else {
352 /* The compare did major nasty stuff to the
353 * dict: start over.
354 * XXX A clever adversary could prevent this
355 * XXX from terminating.
356 */
357 return lookdict(mp, key, hash);
358 }
359 }
360 freeslot = NULL;
361 }
Tim Peters15d49292001-05-27 07:39:22 +0000362
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000363 /* In the loop, me_key == dummy is by far (factor of 100s) the
364 least likely outcome, so test for that last. */
365 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
366 i = (i << 2) + i + perturb + 1;
367 ep = &ep0[i & mask];
368 if (ep->me_key == NULL)
369 return freeslot == NULL ? ep : freeslot;
370 if (ep->me_key == key)
371 return ep;
372 if (ep->me_hash == hash && ep->me_key != dummy) {
373 startkey = ep->me_key;
374 Py_INCREF(startkey);
375 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
376 Py_DECREF(startkey);
377 if (cmp < 0)
378 return NULL;
379 if (ep0 == mp->ma_table && ep->me_key == startkey) {
380 if (cmp > 0)
381 return ep;
382 }
383 else {
384 /* The compare did major nasty stuff to the
385 * dict: start over.
386 * XXX A clever adversary could prevent this
387 * XXX from terminating.
388 */
389 return lookdict(mp, key, hash);
390 }
391 }
392 else if (ep->me_key == dummy && freeslot == NULL)
393 freeslot = ep;
394 }
395 assert(0); /* NOT REACHED */
396 return 0;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000397}
398
399/*
Guido van Rossum89d8c602007-09-18 17:26:56 +0000400 * Hacked up version of lookdict which can assume keys are always
401 * unicodes; this assumption allows testing for errors during
402 * PyObject_RichCompareBool() to be dropped; unicode-unicode
403 * comparisons never raise exceptions. This also means we don't need
404 * to go through PyObject_RichCompareBool(); we can always use
405 * unicode_eq() directly.
Fred Drake1bff34a2000-08-31 19:31:38 +0000406 *
Guido van Rossum89d8c602007-09-18 17:26:56 +0000407 * This is valuable because dicts with only unicode keys are very common.
Fred Drake1bff34a2000-08-31 19:31:38 +0000408 */
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000409static PyDictEntry *
410lookdict_unicode(PyDictObject *mp, PyObject *key, register long hash)
Fred Drake1bff34a2000-08-31 19:31:38 +0000411{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000412 register size_t i;
413 register size_t perturb;
414 register PyDictEntry *freeslot;
415 register size_t mask = (size_t)mp->ma_mask;
416 PyDictEntry *ep0 = mp->ma_table;
417 register PyDictEntry *ep;
Fred Drake1bff34a2000-08-31 19:31:38 +0000418
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000419 /* Make sure this function doesn't have to handle non-unicode keys,
420 including subclasses of str; e.g., one reason to subclass
421 unicodes is to override __eq__, and for speed we don't cater to
422 that here. */
423 if (!PyUnicode_CheckExact(key)) {
Fred Drake1bff34a2000-08-31 19:31:38 +0000424#ifdef SHOW_CONVERSION_COUNTS
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000425 ++converted;
Fred Drake1bff34a2000-08-31 19:31:38 +0000426#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000427 mp->ma_lookup = lookdict;
428 return lookdict(mp, key, hash);
429 }
430 i = hash & mask;
431 ep = &ep0[i];
432 if (ep->me_key == NULL || ep->me_key == key)
433 return ep;
434 if (ep->me_key == dummy)
435 freeslot = ep;
436 else {
437 if (ep->me_hash == hash && unicode_eq(ep->me_key, key))
438 return ep;
439 freeslot = NULL;
440 }
Tim Peters15d49292001-05-27 07:39:22 +0000441
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000442 /* In the loop, me_key == dummy is by far (factor of 100s) the
443 least likely outcome, so test for that last. */
444 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
445 i = (i << 2) + i + perturb + 1;
446 ep = &ep0[i & mask];
447 if (ep->me_key == NULL)
448 return freeslot == NULL ? ep : freeslot;
449 if (ep->me_key == key
450 || (ep->me_hash == hash
451 && ep->me_key != dummy
452 && unicode_eq(ep->me_key, key)))
453 return ep;
454 if (ep->me_key == dummy && freeslot == NULL)
455 freeslot = ep;
456 }
457 assert(0); /* NOT REACHED */
458 return 0;
Fred Drake1bff34a2000-08-31 19:31:38 +0000459}
460
Benjamin Petersonfb886362010-04-24 18:21:17 +0000461int
462_PyDict_HasOnlyStringKeys(PyObject *dict)
463{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000464 Py_ssize_t pos = 0;
465 PyObject *key, *value;
466 assert(PyDict_CheckExact(dict));
467 /* Shortcut */
468 if (((PyDictObject *)dict)->ma_lookup == lookdict_unicode)
469 return 1;
470 while (PyDict_Next(dict, &pos, &key, &value))
471 if (!PyUnicode_Check(key))
472 return 0;
473 return 1;
Benjamin Petersonfb886362010-04-24 18:21:17 +0000474}
475
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000476#ifdef SHOW_TRACK_COUNT
477#define INCREASE_TRACK_COUNT \
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000478 (count_tracked++, count_untracked--);
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000479#define DECREASE_TRACK_COUNT \
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000480 (count_tracked--, count_untracked++);
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000481#else
482#define INCREASE_TRACK_COUNT
483#define DECREASE_TRACK_COUNT
484#endif
485
486#define MAINTAIN_TRACKING(mp, key, value) \
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000487 do { \
488 if (!_PyObject_GC_IS_TRACKED(mp)) { \
489 if (_PyObject_GC_MAY_BE_TRACKED(key) || \
490 _PyObject_GC_MAY_BE_TRACKED(value)) { \
491 _PyObject_GC_TRACK(mp); \
492 INCREASE_TRACK_COUNT \
493 } \
494 } \
495 } while(0)
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000496
497void
498_PyDict_MaybeUntrack(PyObject *op)
499{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000500 PyDictObject *mp;
501 PyObject *value;
502 Py_ssize_t mask, i;
503 PyDictEntry *ep;
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000504
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000505 if (!PyDict_CheckExact(op) || !_PyObject_GC_IS_TRACKED(op))
506 return;
507
508 mp = (PyDictObject *) op;
509 ep = mp->ma_table;
510 mask = mp->ma_mask;
511 for (i = 0; i <= mask; i++) {
512 if ((value = ep[i].me_value) == NULL)
513 continue;
514 if (_PyObject_GC_MAY_BE_TRACKED(value) ||
515 _PyObject_GC_MAY_BE_TRACKED(ep[i].me_key))
516 return;
517 }
518 DECREASE_TRACK_COUNT
519 _PyObject_GC_UNTRACK(op);
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000520}
521
522
Fred Drake1bff34a2000-08-31 19:31:38 +0000523/*
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000524Internal routine to insert a new item into the table.
525Used both by the internal resize routine and by the public insert routine.
526Eats a reference to key and one to value.
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000527Returns -1 if an error occurred, or 0 on success.
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000528*/
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000529static int
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000530insertdict(register PyDictObject *mp, PyObject *key, long hash, PyObject *value)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000531{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000532 PyObject *old_value;
533 register PyDictEntry *ep;
534 typedef PyDictEntry *(*lookupfunc)(PyDictObject *, PyObject *, long);
Tim Peters6d6c1a32001-08-02 04:15:00 +0000535
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000536 assert(mp->ma_lookup != NULL);
537 ep = mp->ma_lookup(mp, key, hash);
538 if (ep == NULL) {
539 Py_DECREF(key);
540 Py_DECREF(value);
541 return -1;
542 }
543 MAINTAIN_TRACKING(mp, key, value);
544 if (ep->me_value != NULL) {
545 old_value = ep->me_value;
546 ep->me_value = value;
547 Py_DECREF(old_value); /* which **CAN** re-enter */
548 Py_DECREF(key);
549 }
550 else {
551 if (ep->me_key == NULL)
552 mp->ma_fill++;
553 else {
554 assert(ep->me_key == dummy);
555 Py_DECREF(dummy);
556 }
557 ep->me_key = key;
558 ep->me_hash = (Py_ssize_t)hash;
559 ep->me_value = value;
560 mp->ma_used++;
561 }
562 return 0;
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000563}
564
565/*
566Internal routine used by dictresize() to insert an item which is
567known to be absent from the dict. This routine also assumes that
568the dict contains no deleted entries. Besides the performance benefit,
569using insertdict() in dictresize() is dangerous (SF bug #1456209).
570Note that no refcounts are changed by this routine; if needed, the caller
571is responsible for incref'ing `key` and `value`.
572*/
573static void
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000574insertdict_clean(register PyDictObject *mp, PyObject *key, long hash,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000575 PyObject *value)
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000576{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000577 register size_t i;
578 register size_t perturb;
579 register size_t mask = (size_t)mp->ma_mask;
580 PyDictEntry *ep0 = mp->ma_table;
581 register PyDictEntry *ep;
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000582
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000583 MAINTAIN_TRACKING(mp, key, value);
584 i = hash & mask;
585 ep = &ep0[i];
586 for (perturb = hash; ep->me_key != NULL; perturb >>= PERTURB_SHIFT) {
587 i = (i << 2) + i + perturb + 1;
588 ep = &ep0[i & mask];
589 }
590 assert(ep->me_value == NULL);
591 mp->ma_fill++;
592 ep->me_key = key;
593 ep->me_hash = (Py_ssize_t)hash;
594 ep->me_value = value;
595 mp->ma_used++;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000596}
597
598/*
599Restructure the table by allocating a new table and reinserting all
600items again. When entries have been deleted, the new table may
601actually be smaller than the old one.
602*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000603static int
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000604dictresize(PyDictObject *mp, Py_ssize_t minused)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000605{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000606 Py_ssize_t newsize;
607 PyDictEntry *oldtable, *newtable, *ep;
608 Py_ssize_t i;
609 int is_oldtable_malloced;
610 PyDictEntry small_copy[PyDict_MINSIZE];
Tim Peters91a364d2001-05-19 07:04:38 +0000611
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000612 assert(minused >= 0);
Tim Peters0c6010b2001-05-23 23:33:57 +0000613
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000614 /* Find the smallest table size > minused. */
615 for (newsize = PyDict_MINSIZE;
616 newsize <= minused && newsize > 0;
617 newsize <<= 1)
618 ;
619 if (newsize <= 0) {
620 PyErr_NoMemory();
621 return -1;
622 }
Tim Peters0c6010b2001-05-23 23:33:57 +0000623
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000624 /* Get space for a new table. */
625 oldtable = mp->ma_table;
626 assert(oldtable != NULL);
627 is_oldtable_malloced = oldtable != mp->ma_smalltable;
Tim Peters0c6010b2001-05-23 23:33:57 +0000628
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000629 if (newsize == PyDict_MINSIZE) {
630 /* A large table is shrinking, or we can't get any smaller. */
631 newtable = mp->ma_smalltable;
632 if (newtable == oldtable) {
633 if (mp->ma_fill == mp->ma_used) {
634 /* No dummies, so no point doing anything. */
635 return 0;
636 }
637 /* We're not going to resize it, but rebuild the
638 table anyway to purge old dummy entries.
639 Subtle: This is *necessary* if fill==size,
640 as lookdict needs at least one virgin slot to
641 terminate failing searches. If fill < size, it's
642 merely desirable, as dummies slow searches. */
643 assert(mp->ma_fill > mp->ma_used);
644 memcpy(small_copy, oldtable, sizeof(small_copy));
645 oldtable = small_copy;
646 }
647 }
648 else {
649 newtable = PyMem_NEW(PyDictEntry, newsize);
650 if (newtable == NULL) {
651 PyErr_NoMemory();
652 return -1;
653 }
654 }
Tim Peters0c6010b2001-05-23 23:33:57 +0000655
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000656 /* Make the dict empty, using the new table. */
657 assert(newtable != oldtable);
658 mp->ma_table = newtable;
659 mp->ma_mask = newsize - 1;
660 memset(newtable, 0, sizeof(PyDictEntry) * newsize);
661 mp->ma_used = 0;
662 i = mp->ma_fill;
663 mp->ma_fill = 0;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000664
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000665 /* Copy the data over; this is refcount-neutral for active entries;
666 dummy entries aren't copied over, of course */
667 for (ep = oldtable; i > 0; ep++) {
668 if (ep->me_value != NULL) { /* active entry */
669 --i;
670 insertdict_clean(mp, ep->me_key, (long)ep->me_hash,
671 ep->me_value);
672 }
673 else if (ep->me_key != NULL) { /* dummy entry */
674 --i;
675 assert(ep->me_key == dummy);
676 Py_DECREF(ep->me_key);
677 }
678 /* else key == value == NULL: nothing to do */
679 }
Guido van Rossumd7047b31995-01-02 19:07:15 +0000680
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000681 if (is_oldtable_malloced)
682 PyMem_DEL(oldtable);
683 return 0;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000684}
685
Christian Heimes99170a52007-12-19 02:07:34 +0000686/* Create a new dictionary pre-sized to hold an estimated number of elements.
687 Underestimates are okay because the dictionary will resize as necessary.
688 Overestimates just mean the dictionary will be more sparse than usual.
689*/
690
691PyObject *
692_PyDict_NewPresized(Py_ssize_t minused)
693{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000694 PyObject *op = PyDict_New();
Christian Heimes99170a52007-12-19 02:07:34 +0000695
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000696 if (minused>5 && op != NULL && dictresize((PyDictObject *)op, minused) == -1) {
697 Py_DECREF(op);
698 return NULL;
699 }
700 return op;
Christian Heimes99170a52007-12-19 02:07:34 +0000701}
702
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000703/* Note that, for historical reasons, PyDict_GetItem() suppresses all errors
704 * that may occur (originally dicts supported only string keys, and exceptions
705 * weren't possible). So, while the original intent was that a NULL return
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000706 * meant the key wasn't present, in reality it can mean that, or that an error
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000707 * (suppressed) occurred while computing the key's hash, or that some error
708 * (suppressed) occurred when comparing keys in the dict's internal probe
709 * sequence. A nasty example of the latter is when a Python-coded comparison
710 * function hits a stack-depth error, which can cause this to return NULL
711 * even if the key is present.
712 */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000713PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +0000714PyDict_GetItem(PyObject *op, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000715{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000716 long hash;
717 PyDictObject *mp = (PyDictObject *)op;
718 PyDictEntry *ep;
719 PyThreadState *tstate;
720 if (!PyDict_Check(op))
721 return NULL;
722 if (!PyUnicode_CheckExact(key) ||
723 (hash = ((PyUnicodeObject *) key)->hash) == -1)
724 {
725 hash = PyObject_Hash(key);
726 if (hash == -1) {
727 PyErr_Clear();
728 return NULL;
729 }
730 }
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000731
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000732 /* We can arrive here with a NULL tstate during initialization: try
733 running "python -Wi" for an example related to string interning.
734 Let's just hope that no exception occurs then... This must be
735 _PyThreadState_Current and not PyThreadState_GET() because in debug
736 mode, the latter complains if tstate is NULL. */
737 tstate = (PyThreadState*)_Py_atomic_load_relaxed(
738 &_PyThreadState_Current);
739 if (tstate != NULL && tstate->curexc_type != NULL) {
740 /* preserve the existing exception */
741 PyObject *err_type, *err_value, *err_tb;
742 PyErr_Fetch(&err_type, &err_value, &err_tb);
743 ep = (mp->ma_lookup)(mp, key, hash);
744 /* ignore errors */
745 PyErr_Restore(err_type, err_value, err_tb);
746 if (ep == NULL)
747 return NULL;
748 }
749 else {
750 ep = (mp->ma_lookup)(mp, key, hash);
751 if (ep == NULL) {
752 PyErr_Clear();
753 return NULL;
754 }
755 }
756 return ep->me_value;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000757}
758
Guido van Rossum47b9ff62006-08-24 00:41:19 +0000759/* Variant of PyDict_GetItem() that doesn't suppress exceptions.
760 This returns NULL *with* an exception set if an exception occurred.
761 It returns NULL *without* an exception set if the key wasn't present.
762*/
763PyObject *
764PyDict_GetItemWithError(PyObject *op, PyObject *key)
765{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000766 long hash;
767 PyDictObject*mp = (PyDictObject *)op;
768 PyDictEntry *ep;
Guido van Rossum47b9ff62006-08-24 00:41:19 +0000769
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000770 if (!PyDict_Check(op)) {
771 PyErr_BadInternalCall();
772 return NULL;
773 }
774 if (!PyUnicode_CheckExact(key) ||
775 (hash = ((PyUnicodeObject *) key)->hash) == -1)
776 {
777 hash = PyObject_Hash(key);
778 if (hash == -1) {
779 return NULL;
780 }
781 }
Guido van Rossum47b9ff62006-08-24 00:41:19 +0000782
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000783 ep = (mp->ma_lookup)(mp, key, hash);
784 if (ep == NULL)
785 return NULL;
786 return ep->me_value;
Guido van Rossum47b9ff62006-08-24 00:41:19 +0000787}
788
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000789/* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
Tim Peters60b29962006-01-01 01:19:23 +0000790 * dictionary if it's merely replacing the value for an existing key.
791 * This means that it's safe to loop over a dictionary with PyDict_Next()
792 * and occasionally replace a value -- but you can't insert new keys or
793 * remove them.
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000794 */
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000795int
Tim Peters1f5871e2000-07-04 17:44:48 +0000796PyDict_SetItem(register PyObject *op, PyObject *key, PyObject *value)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000797{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000798 register PyDictObject *mp;
799 register long hash;
800 register Py_ssize_t n_used;
Guido van Rossuma4dd0112001-04-15 22:16:26 +0000801
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000802 if (!PyDict_Check(op)) {
803 PyErr_BadInternalCall();
804 return -1;
805 }
806 assert(key);
807 assert(value);
808 mp = (PyDictObject *)op;
809 if (!PyUnicode_CheckExact(key) ||
810 (hash = ((PyUnicodeObject *) key)->hash) == -1)
811 {
812 hash = PyObject_Hash(key);
813 if (hash == -1)
814 return -1;
815 }
816 assert(mp->ma_fill <= mp->ma_mask); /* at least one empty slot */
817 n_used = mp->ma_used;
818 Py_INCREF(value);
819 Py_INCREF(key);
820 if (insertdict(mp, key, hash, value) != 0)
821 return -1;
822 /* If we added a key, we can safely resize. Otherwise just return!
823 * If fill >= 2/3 size, adjust size. Normally, this doubles or
824 * quaduples the size, but it's also possible for the dict to shrink
825 * (if ma_fill is much larger than ma_used, meaning a lot of dict
826 * keys have been * deleted).
827 *
828 * Quadrupling the size improves average dictionary sparseness
829 * (reducing collisions) at the cost of some memory and iteration
830 * speed (which loops over every possible entry). It also halves
831 * the number of expensive resize operations in a growing dictionary.
832 *
833 * Very large dictionaries (over 50K items) use doubling instead.
834 * This may help applications with severe memory constraints.
835 */
836 if (!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))
837 return 0;
838 return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000839}
840
841int
Tim Peters1f5871e2000-07-04 17:44:48 +0000842PyDict_DelItem(PyObject *op, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000843{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000844 register PyDictObject *mp;
845 register long hash;
846 register PyDictEntry *ep;
847 PyObject *old_value, *old_key;
Guido van Rossumd7047b31995-01-02 19:07:15 +0000848
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000849 if (!PyDict_Check(op)) {
850 PyErr_BadInternalCall();
851 return -1;
852 }
853 assert(key);
854 if (!PyUnicode_CheckExact(key) ||
855 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
856 hash = PyObject_Hash(key);
857 if (hash == -1)
858 return -1;
859 }
860 mp = (PyDictObject *)op;
861 ep = (mp->ma_lookup)(mp, key, hash);
862 if (ep == NULL)
863 return -1;
864 if (ep->me_value == NULL) {
865 set_key_error(key);
866 return -1;
867 }
868 old_key = ep->me_key;
869 Py_INCREF(dummy);
870 ep->me_key = dummy;
871 old_value = ep->me_value;
872 ep->me_value = NULL;
873 mp->ma_used--;
874 Py_DECREF(old_value);
875 Py_DECREF(old_key);
876 return 0;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000877}
878
Guido van Rossum25831651993-05-19 14:50:45 +0000879void
Tim Peters1f5871e2000-07-04 17:44:48 +0000880PyDict_Clear(PyObject *op)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000881{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000882 PyDictObject *mp;
883 PyDictEntry *ep, *table;
884 int table_is_malloced;
885 Py_ssize_t fill;
886 PyDictEntry small_copy[PyDict_MINSIZE];
Tim Petersdea48ec2001-05-22 20:40:22 +0000887#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000888 Py_ssize_t i, n;
Tim Petersdea48ec2001-05-22 20:40:22 +0000889#endif
890
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000891 if (!PyDict_Check(op))
892 return;
893 mp = (PyDictObject *)op;
Tim Petersdea48ec2001-05-22 20:40:22 +0000894#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000895 n = mp->ma_mask + 1;
896 i = 0;
Tim Petersdea48ec2001-05-22 20:40:22 +0000897#endif
898
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000899 table = mp->ma_table;
900 assert(table != NULL);
901 table_is_malloced = table != mp->ma_smalltable;
Tim Petersdea48ec2001-05-22 20:40:22 +0000902
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000903 /* This is delicate. During the process of clearing the dict,
904 * decrefs can cause the dict to mutate. To avoid fatal confusion
905 * (voice of experience), we have to make the dict empty before
906 * clearing the slots, and never refer to anything via mp->xxx while
907 * clearing.
908 */
909 fill = mp->ma_fill;
910 if (table_is_malloced)
911 EMPTY_TO_MINSIZE(mp);
Tim Petersdea48ec2001-05-22 20:40:22 +0000912
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000913 else if (fill > 0) {
914 /* It's a small table with something that needs to be cleared.
915 * Afraid the only safe way is to copy the dict entries into
916 * another small table first.
917 */
918 memcpy(small_copy, table, sizeof(small_copy));
919 table = small_copy;
920 EMPTY_TO_MINSIZE(mp);
921 }
922 /* else it's a small table that's already empty */
Tim Petersdea48ec2001-05-22 20:40:22 +0000923
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000924 /* Now we can finally clear things. If C had refcounts, we could
925 * assert that the refcount on table is 1 now, i.e. that this function
926 * has unique access to it, so decref side-effects can't alter it.
927 */
928 for (ep = table; fill > 0; ++ep) {
Tim Petersdea48ec2001-05-22 20:40:22 +0000929#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000930 assert(i < n);
931 ++i;
Tim Petersdea48ec2001-05-22 20:40:22 +0000932#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000933 if (ep->me_key) {
934 --fill;
935 Py_DECREF(ep->me_key);
936 Py_XDECREF(ep->me_value);
937 }
Tim Petersdea48ec2001-05-22 20:40:22 +0000938#ifdef Py_DEBUG
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000939 else
940 assert(ep->me_value == NULL);
Tim Petersdea48ec2001-05-22 20:40:22 +0000941#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000942 }
Tim Petersdea48ec2001-05-22 20:40:22 +0000943
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000944 if (table_is_malloced)
945 PyMem_DEL(table);
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000946}
947
Tim Peters080c88b2003-02-15 03:01:11 +0000948/*
949 * Iterate over a dict. Use like so:
950 *
Thomas Wouters4d70c3d2006-06-08 14:42:34 +0000951 * Py_ssize_t i;
Tim Peters080c88b2003-02-15 03:01:11 +0000952 * PyObject *key, *value;
953 * i = 0; # important! i should not otherwise be changed by you
Neal Norwitz07323012003-02-15 14:45:12 +0000954 * while (PyDict_Next(yourdict, &i, &key, &value)) {
Tim Peters080c88b2003-02-15 03:01:11 +0000955 * Refer to borrowed references in key and value.
956 * }
957 *
958 * CAUTION: In general, it isn't safe to use PyDict_Next in a loop that
Tim Peters67830702001-03-21 19:23:56 +0000959 * mutates the dict. One exception: it is safe if the loop merely changes
960 * the values associated with the keys (but doesn't insert new keys or
961 * delete keys), via PyDict_SetItem().
962 */
Guido van Rossum25831651993-05-19 14:50:45 +0000963int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000964PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue)
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000965{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000966 register Py_ssize_t i;
967 register Py_ssize_t mask;
968 register PyDictEntry *ep;
Raymond Hettinger43442782004-03-17 21:55:03 +0000969
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000970 if (!PyDict_Check(op))
971 return 0;
972 i = *ppos;
973 if (i < 0)
974 return 0;
975 ep = ((PyDictObject *)op)->ma_table;
976 mask = ((PyDictObject *)op)->ma_mask;
977 while (i <= mask && ep[i].me_value == NULL)
978 i++;
979 *ppos = i+1;
980 if (i > mask)
981 return 0;
982 if (pkey)
983 *pkey = ep[i].me_key;
984 if (pvalue)
985 *pvalue = ep[i].me_value;
986 return 1;
Guido van Rossum4b1302b1993-03-27 18:11:32 +0000987}
988
Thomas Wouterscf297e42007-02-23 15:07:44 +0000989/* Internal version of PyDict_Next that returns a hash value in addition to the key and value.*/
990int
991_PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue, long *phash)
992{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000993 register Py_ssize_t i;
994 register Py_ssize_t mask;
995 register PyDictEntry *ep;
Thomas Wouterscf297e42007-02-23 15:07:44 +0000996
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000997 if (!PyDict_Check(op))
998 return 0;
999 i = *ppos;
1000 if (i < 0)
1001 return 0;
1002 ep = ((PyDictObject *)op)->ma_table;
1003 mask = ((PyDictObject *)op)->ma_mask;
1004 while (i <= mask && ep[i].me_value == NULL)
1005 i++;
1006 *ppos = i+1;
1007 if (i > mask)
1008 return 0;
1009 *phash = (long)(ep[i].me_hash);
1010 if (pkey)
1011 *pkey = ep[i].me_key;
1012 if (pvalue)
1013 *pvalue = ep[i].me_value;
1014 return 1;
Thomas Wouterscf297e42007-02-23 15:07:44 +00001015}
1016
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001017/* Methods */
1018
1019static void
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001020dict_dealloc(register PyDictObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001021{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001022 register PyDictEntry *ep;
1023 Py_ssize_t fill = mp->ma_fill;
1024 PyObject_GC_UnTrack(mp);
1025 Py_TRASHCAN_SAFE_BEGIN(mp)
1026 for (ep = mp->ma_table; fill > 0; ep++) {
1027 if (ep->me_key) {
1028 --fill;
1029 Py_DECREF(ep->me_key);
1030 Py_XDECREF(ep->me_value);
1031 }
1032 }
1033 if (mp->ma_table != mp->ma_smalltable)
1034 PyMem_DEL(mp->ma_table);
1035 if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
1036 free_list[numfree++] = mp;
1037 else
1038 Py_TYPE(mp)->tp_free((PyObject *)mp);
1039 Py_TRASHCAN_SAFE_END(mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001040}
1041
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001042static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001043dict_repr(PyDictObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001044{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001045 Py_ssize_t i;
1046 PyObject *s, *temp, *colon = NULL;
1047 PyObject *pieces = NULL, *result = NULL;
1048 PyObject *key, *value;
Guido van Rossum255443b1998-04-10 22:47:14 +00001049
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001050 i = Py_ReprEnter((PyObject *)mp);
1051 if (i != 0) {
1052 return i > 0 ? PyUnicode_FromString("{...}") : NULL;
1053 }
Guido van Rossum255443b1998-04-10 22:47:14 +00001054
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001055 if (mp->ma_used == 0) {
1056 result = PyUnicode_FromString("{}");
1057 goto Done;
1058 }
Tim Petersa7259592001-06-16 05:11:17 +00001059
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001060 pieces = PyList_New(0);
1061 if (pieces == NULL)
1062 goto Done;
Tim Petersa7259592001-06-16 05:11:17 +00001063
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001064 colon = PyUnicode_FromString(": ");
1065 if (colon == NULL)
1066 goto Done;
Tim Petersa7259592001-06-16 05:11:17 +00001067
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001068 /* Do repr() on each key+value pair, and insert ": " between them.
1069 Note that repr may mutate the dict. */
1070 i = 0;
1071 while (PyDict_Next((PyObject *)mp, &i, &key, &value)) {
1072 int status;
1073 /* Prevent repr from deleting value during key format. */
1074 Py_INCREF(value);
1075 s = PyObject_Repr(key);
1076 PyUnicode_Append(&s, colon);
1077 PyUnicode_AppendAndDel(&s, PyObject_Repr(value));
1078 Py_DECREF(value);
1079 if (s == NULL)
1080 goto Done;
1081 status = PyList_Append(pieces, s);
1082 Py_DECREF(s); /* append created a new ref */
1083 if (status < 0)
1084 goto Done;
1085 }
Tim Petersa7259592001-06-16 05:11:17 +00001086
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001087 /* Add "{}" decorations to the first and last items. */
1088 assert(PyList_GET_SIZE(pieces) > 0);
1089 s = PyUnicode_FromString("{");
1090 if (s == NULL)
1091 goto Done;
1092 temp = PyList_GET_ITEM(pieces, 0);
1093 PyUnicode_AppendAndDel(&s, temp);
1094 PyList_SET_ITEM(pieces, 0, s);
1095 if (s == NULL)
1096 goto Done;
Tim Petersa7259592001-06-16 05:11:17 +00001097
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001098 s = PyUnicode_FromString("}");
1099 if (s == NULL)
1100 goto Done;
1101 temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
1102 PyUnicode_AppendAndDel(&temp, s);
1103 PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
1104 if (temp == NULL)
1105 goto Done;
Tim Petersa7259592001-06-16 05:11:17 +00001106
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001107 /* Paste them all together with ", " between. */
1108 s = PyUnicode_FromString(", ");
1109 if (s == NULL)
1110 goto Done;
1111 result = PyUnicode_Join(s, pieces);
1112 Py_DECREF(s);
Tim Petersa7259592001-06-16 05:11:17 +00001113
1114Done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001115 Py_XDECREF(pieces);
1116 Py_XDECREF(colon);
1117 Py_ReprLeave((PyObject *)mp);
1118 return result;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001119}
1120
Martin v. Löwis18e16552006-02-15 17:27:45 +00001121static Py_ssize_t
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001122dict_length(PyDictObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001123{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001124 return mp->ma_used;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001125}
1126
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001127static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001128dict_subscript(PyDictObject *mp, register PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001129{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001130 PyObject *v;
1131 long hash;
1132 PyDictEntry *ep;
1133 assert(mp->ma_table != NULL);
1134 if (!PyUnicode_CheckExact(key) ||
1135 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
1136 hash = PyObject_Hash(key);
1137 if (hash == -1)
1138 return NULL;
1139 }
1140 ep = (mp->ma_lookup)(mp, key, hash);
1141 if (ep == NULL)
1142 return NULL;
1143 v = ep->me_value;
1144 if (v == NULL) {
1145 if (!PyDict_CheckExact(mp)) {
1146 /* Look up __missing__ method if we're a subclass. */
1147 PyObject *missing, *res;
1148 static PyObject *missing_str = NULL;
1149 missing = _PyObject_LookupSpecial((PyObject *)mp,
1150 "__missing__",
1151 &missing_str);
1152 if (missing != NULL) {
1153 res = PyObject_CallFunctionObjArgs(missing,
1154 key, NULL);
1155 Py_DECREF(missing);
1156 return res;
1157 }
1158 else if (PyErr_Occurred())
1159 return NULL;
1160 }
1161 set_key_error(key);
1162 return NULL;
1163 }
1164 else
1165 Py_INCREF(v);
1166 return v;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001167}
1168
1169static int
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001170dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001171{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001172 if (w == NULL)
1173 return PyDict_DelItem((PyObject *)mp, v);
1174 else
1175 return PyDict_SetItem((PyObject *)mp, v, w);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001176}
1177
Guido van Rossuma9e7a811997-05-13 21:02:11 +00001178static PyMappingMethods dict_as_mapping = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001179 (lenfunc)dict_length, /*mp_length*/
1180 (binaryfunc)dict_subscript, /*mp_subscript*/
1181 (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001182};
1183
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001184static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001185dict_keys(register PyDictObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001186{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001187 register PyObject *v;
1188 register Py_ssize_t i, j;
1189 PyDictEntry *ep;
1190 Py_ssize_t mask, n;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001191
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001192 again:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001193 n = mp->ma_used;
1194 v = PyList_New(n);
1195 if (v == NULL)
1196 return NULL;
1197 if (n != mp->ma_used) {
1198 /* Durnit. The allocations caused the dict to resize.
1199 * Just start over, this shouldn't normally happen.
1200 */
1201 Py_DECREF(v);
1202 goto again;
1203 }
1204 ep = mp->ma_table;
1205 mask = mp->ma_mask;
1206 for (i = 0, j = 0; i <= mask; i++) {
1207 if (ep[i].me_value != NULL) {
1208 PyObject *key = ep[i].me_key;
1209 Py_INCREF(key);
1210 PyList_SET_ITEM(v, j, key);
1211 j++;
1212 }
1213 }
1214 assert(j == n);
1215 return v;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001216}
1217
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001218static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001219dict_values(register PyDictObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001220{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001221 register PyObject *v;
1222 register Py_ssize_t i, j;
1223 PyDictEntry *ep;
1224 Py_ssize_t mask, n;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001225
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001226 again:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001227 n = mp->ma_used;
1228 v = PyList_New(n);
1229 if (v == NULL)
1230 return NULL;
1231 if (n != mp->ma_used) {
1232 /* Durnit. The allocations caused the dict to resize.
1233 * Just start over, this shouldn't normally happen.
1234 */
1235 Py_DECREF(v);
1236 goto again;
1237 }
1238 ep = mp->ma_table;
1239 mask = mp->ma_mask;
1240 for (i = 0, j = 0; i <= mask; i++) {
1241 if (ep[i].me_value != NULL) {
1242 PyObject *value = ep[i].me_value;
1243 Py_INCREF(value);
1244 PyList_SET_ITEM(v, j, value);
1245 j++;
1246 }
1247 }
1248 assert(j == n);
1249 return v;
Guido van Rossum25831651993-05-19 14:50:45 +00001250}
1251
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001252static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001253dict_items(register PyDictObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001254{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001255 register PyObject *v;
1256 register Py_ssize_t i, j, n;
1257 Py_ssize_t mask;
1258 PyObject *item, *key, *value;
1259 PyDictEntry *ep;
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001260
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001261 /* Preallocate the list of tuples, to avoid allocations during
1262 * the loop over the items, which could trigger GC, which
1263 * could resize the dict. :-(
1264 */
Guido van Rossuma4dd0112001-04-15 22:16:26 +00001265 again:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001266 n = mp->ma_used;
1267 v = PyList_New(n);
1268 if (v == NULL)
1269 return NULL;
1270 for (i = 0; i < n; i++) {
1271 item = PyTuple_New(2);
1272 if (item == NULL) {
1273 Py_DECREF(v);
1274 return NULL;
1275 }
1276 PyList_SET_ITEM(v, i, item);
1277 }
1278 if (n != mp->ma_used) {
1279 /* Durnit. The allocations caused the dict to resize.
1280 * Just start over, this shouldn't normally happen.
1281 */
1282 Py_DECREF(v);
1283 goto again;
1284 }
1285 /* Nothing we do below makes any function calls. */
1286 ep = mp->ma_table;
1287 mask = mp->ma_mask;
1288 for (i = 0, j = 0; i <= mask; i++) {
1289 if ((value=ep[i].me_value) != NULL) {
1290 key = ep[i].me_key;
1291 item = PyList_GET_ITEM(v, j);
1292 Py_INCREF(key);
1293 PyTuple_SET_ITEM(item, 0, key);
1294 Py_INCREF(value);
1295 PyTuple_SET_ITEM(item, 1, value);
1296 j++;
1297 }
1298 }
1299 assert(j == n);
1300 return v;
Guido van Rossum25831651993-05-19 14:50:45 +00001301}
1302
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001303static PyObject *
Tim Petersbca1cbc2002-12-09 22:56:13 +00001304dict_fromkeys(PyObject *cls, PyObject *args)
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001305{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001306 PyObject *seq;
1307 PyObject *value = Py_None;
1308 PyObject *it; /* iter(seq) */
1309 PyObject *key;
1310 PyObject *d;
1311 int status;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001312
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001313 if (!PyArg_UnpackTuple(args, "fromkeys", 1, 2, &seq, &value))
1314 return NULL;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001315
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001316 d = PyObject_CallObject(cls, NULL);
1317 if (d == NULL)
1318 return NULL;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001319
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001320 if (PyDict_CheckExact(d) && PyDict_CheckExact(seq)) {
1321 PyDictObject *mp = (PyDictObject *)d;
1322 PyObject *oldvalue;
1323 Py_ssize_t pos = 0;
1324 PyObject *key;
1325 long hash;
Guido van Rossum58da9312007-11-10 23:39:45 +00001326
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001327 if (dictresize(mp, Py_SIZE(seq)))
1328 return NULL;
Guido van Rossum58da9312007-11-10 23:39:45 +00001329
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001330 while (_PyDict_Next(seq, &pos, &key, &oldvalue, &hash)) {
1331 Py_INCREF(key);
1332 Py_INCREF(value);
1333 if (insertdict(mp, key, hash, value))
1334 return NULL;
1335 }
1336 return d;
1337 }
Guido van Rossum58da9312007-11-10 23:39:45 +00001338
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001339 if (PyDict_CheckExact(d) && PyAnySet_CheckExact(seq)) {
1340 PyDictObject *mp = (PyDictObject *)d;
1341 Py_ssize_t pos = 0;
1342 PyObject *key;
1343 long hash;
Guido van Rossumd8faa362007-04-27 19:54:29 +00001344
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001345 if (dictresize(mp, PySet_GET_SIZE(seq)))
1346 return NULL;
Guido van Rossumd8faa362007-04-27 19:54:29 +00001347
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001348 while (_PySet_NextEntry(seq, &pos, &key, &hash)) {
1349 Py_INCREF(key);
1350 Py_INCREF(value);
1351 if (insertdict(mp, key, hash, value))
1352 return NULL;
1353 }
1354 return d;
1355 }
Guido van Rossumd8faa362007-04-27 19:54:29 +00001356
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001357 it = PyObject_GetIter(seq);
1358 if (it == NULL){
1359 Py_DECREF(d);
1360 return NULL;
1361 }
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001362
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001363 if (PyDict_CheckExact(d)) {
1364 while ((key = PyIter_Next(it)) != NULL) {
1365 status = PyDict_SetItem(d, key, value);
1366 Py_DECREF(key);
1367 if (status < 0)
1368 goto Fail;
1369 }
1370 } else {
1371 while ((key = PyIter_Next(it)) != NULL) {
1372 status = PyObject_SetItem(d, key, value);
1373 Py_DECREF(key);
1374 if (status < 0)
1375 goto Fail;
1376 }
1377 }
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001378
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001379 if (PyErr_Occurred())
1380 goto Fail;
1381 Py_DECREF(it);
1382 return d;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001383
1384Fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001385 Py_DECREF(it);
1386 Py_DECREF(d);
1387 return NULL;
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001388}
1389
Raymond Hettinger31017ae2004-03-04 08:25:44 +00001390static int
1391dict_update_common(PyObject *self, PyObject *args, PyObject *kwds, char *methname)
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001392{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001393 PyObject *arg = NULL;
1394 int result = 0;
Raymond Hettinger31017ae2004-03-04 08:25:44 +00001395
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001396 if (!PyArg_UnpackTuple(args, methname, 0, 1, &arg))
1397 result = -1;
Raymond Hettinger31017ae2004-03-04 08:25:44 +00001398
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001399 else if (arg != NULL) {
1400 if (PyObject_HasAttrString(arg, "keys"))
1401 result = PyDict_Merge(self, arg, 1);
1402 else
1403 result = PyDict_MergeFromSeq2(self, arg, 1);
1404 }
1405 if (result == 0 && kwds != NULL) {
1406 if (PyArg_ValidateKeywordArguments(kwds))
1407 result = PyDict_Merge(self, kwds, 1);
1408 else
1409 result = -1;
1410 }
1411 return result;
Raymond Hettinger31017ae2004-03-04 08:25:44 +00001412}
1413
1414static PyObject *
1415dict_update(PyObject *self, PyObject *args, PyObject *kwds)
1416{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001417 if (dict_update_common(self, args, kwds, "update") != -1)
1418 Py_RETURN_NONE;
1419 return NULL;
Tim Peters6d6c1a32001-08-02 04:15:00 +00001420}
1421
Guido van Rossum05ac6de2001-08-10 20:28:28 +00001422/* Update unconditionally replaces existing items.
1423 Merge has a 3rd argument 'override'; if set, it acts like Update,
Tim Peters1fc240e2001-10-26 05:06:50 +00001424 otherwise it leaves existing items unchanged.
1425
1426 PyDict_{Update,Merge} update/merge from a mapping object.
1427
Tim Petersf582b822001-12-11 18:51:08 +00001428 PyDict_MergeFromSeq2 updates/merges from any iterable object
Tim Peters1fc240e2001-10-26 05:06:50 +00001429 producing iterable objects of length 2.
1430*/
1431
Tim Petersf582b822001-12-11 18:51:08 +00001432int
Tim Peters1fc240e2001-10-26 05:06:50 +00001433PyDict_MergeFromSeq2(PyObject *d, PyObject *seq2, int override)
1434{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001435 PyObject *it; /* iter(seq2) */
1436 Py_ssize_t i; /* index into seq2 of current element */
1437 PyObject *item; /* seq2[i] */
1438 PyObject *fast; /* item as a 2-tuple or 2-list */
Tim Peters1fc240e2001-10-26 05:06:50 +00001439
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001440 assert(d != NULL);
1441 assert(PyDict_Check(d));
1442 assert(seq2 != NULL);
Tim Peters1fc240e2001-10-26 05:06:50 +00001443
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001444 it = PyObject_GetIter(seq2);
1445 if (it == NULL)
1446 return -1;
Tim Peters1fc240e2001-10-26 05:06:50 +00001447
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001448 for (i = 0; ; ++i) {
1449 PyObject *key, *value;
1450 Py_ssize_t n;
Tim Peters1fc240e2001-10-26 05:06:50 +00001451
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001452 fast = NULL;
1453 item = PyIter_Next(it);
1454 if (item == NULL) {
1455 if (PyErr_Occurred())
1456 goto Fail;
1457 break;
1458 }
Tim Peters1fc240e2001-10-26 05:06:50 +00001459
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001460 /* Convert item to sequence, and verify length 2. */
1461 fast = PySequence_Fast(item, "");
1462 if (fast == NULL) {
1463 if (PyErr_ExceptionMatches(PyExc_TypeError))
1464 PyErr_Format(PyExc_TypeError,
1465 "cannot convert dictionary update "
1466 "sequence element #%zd to a sequence",
1467 i);
1468 goto Fail;
1469 }
1470 n = PySequence_Fast_GET_SIZE(fast);
1471 if (n != 2) {
1472 PyErr_Format(PyExc_ValueError,
1473 "dictionary update sequence element #%zd "
1474 "has length %zd; 2 is required",
1475 i, n);
1476 goto Fail;
1477 }
Tim Peters1fc240e2001-10-26 05:06:50 +00001478
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001479 /* Update/merge with this (key, value) pair. */
1480 key = PySequence_Fast_GET_ITEM(fast, 0);
1481 value = PySequence_Fast_GET_ITEM(fast, 1);
1482 if (override || PyDict_GetItem(d, key) == NULL) {
1483 int status = PyDict_SetItem(d, key, value);
1484 if (status < 0)
1485 goto Fail;
1486 }
1487 Py_DECREF(fast);
1488 Py_DECREF(item);
1489 }
Tim Peters1fc240e2001-10-26 05:06:50 +00001490
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001491 i = 0;
1492 goto Return;
Tim Peters1fc240e2001-10-26 05:06:50 +00001493Fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001494 Py_XDECREF(item);
1495 Py_XDECREF(fast);
1496 i = -1;
Tim Peters1fc240e2001-10-26 05:06:50 +00001497Return:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001498 Py_DECREF(it);
1499 return Py_SAFE_DOWNCAST(i, Py_ssize_t, int);
Tim Peters1fc240e2001-10-26 05:06:50 +00001500}
1501
Tim Peters6d6c1a32001-08-02 04:15:00 +00001502int
1503PyDict_Update(PyObject *a, PyObject *b)
1504{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001505 return PyDict_Merge(a, b, 1);
Guido van Rossum05ac6de2001-08-10 20:28:28 +00001506}
1507
1508int
1509PyDict_Merge(PyObject *a, PyObject *b, int override)
1510{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001511 register PyDictObject *mp, *other;
1512 register Py_ssize_t i;
1513 PyDictEntry *entry;
Tim Peters6d6c1a32001-08-02 04:15:00 +00001514
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001515 /* We accept for the argument either a concrete dictionary object,
1516 * or an abstract "mapping" object. For the former, we can do
1517 * things quite efficiently. For the latter, we only require that
1518 * PyMapping_Keys() and PyObject_GetItem() be supported.
1519 */
1520 if (a == NULL || !PyDict_Check(a) || b == NULL) {
1521 PyErr_BadInternalCall();
1522 return -1;
1523 }
1524 mp = (PyDictObject*)a;
1525 if (PyDict_Check(b)) {
1526 other = (PyDictObject*)b;
1527 if (other == mp || other->ma_used == 0)
1528 /* a.update(a) or a.update({}); nothing to do */
1529 return 0;
1530 if (mp->ma_used == 0)
1531 /* Since the target dict is empty, PyDict_GetItem()
1532 * always returns NULL. Setting override to 1
1533 * skips the unnecessary test.
1534 */
1535 override = 1;
1536 /* Do one big resize at the start, rather than
1537 * incrementally resizing as we insert new items. Expect
1538 * that there will be no (or few) overlapping keys.
1539 */
1540 if ((mp->ma_fill + other->ma_used)*3 >= (mp->ma_mask+1)*2) {
1541 if (dictresize(mp, (mp->ma_used + other->ma_used)*2) != 0)
1542 return -1;
1543 }
1544 for (i = 0; i <= other->ma_mask; i++) {
1545 entry = &other->ma_table[i];
1546 if (entry->me_value != NULL &&
1547 (override ||
1548 PyDict_GetItem(a, entry->me_key) == NULL)) {
1549 Py_INCREF(entry->me_key);
1550 Py_INCREF(entry->me_value);
1551 if (insertdict(mp, entry->me_key,
1552 (long)entry->me_hash,
1553 entry->me_value) != 0)
1554 return -1;
1555 }
1556 }
1557 }
1558 else {
1559 /* Do it the generic, slower way */
1560 PyObject *keys = PyMapping_Keys(b);
1561 PyObject *iter;
1562 PyObject *key, *value;
1563 int status;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001564
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001565 if (keys == NULL)
1566 /* Docstring says this is equivalent to E.keys() so
1567 * if E doesn't have a .keys() method we want
1568 * AttributeError to percolate up. Might as well
1569 * do the same for any other error.
1570 */
1571 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001572
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001573 iter = PyObject_GetIter(keys);
1574 Py_DECREF(keys);
1575 if (iter == NULL)
1576 return -1;
Barry Warsaw66a0d1d2001-06-26 20:08:32 +00001577
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001578 for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) {
1579 if (!override && PyDict_GetItem(a, key) != NULL) {
1580 Py_DECREF(key);
1581 continue;
1582 }
1583 value = PyObject_GetItem(b, key);
1584 if (value == NULL) {
1585 Py_DECREF(iter);
1586 Py_DECREF(key);
1587 return -1;
1588 }
1589 status = PyDict_SetItem(a, key, value);
1590 Py_DECREF(key);
1591 Py_DECREF(value);
1592 if (status < 0) {
1593 Py_DECREF(iter);
1594 return -1;
1595 }
1596 }
1597 Py_DECREF(iter);
1598 if (PyErr_Occurred())
1599 /* Iterator completed, via error */
1600 return -1;
1601 }
1602 return 0;
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001603}
1604
1605static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001606dict_copy(register PyDictObject *mp)
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001607{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001608 return PyDict_Copy((PyObject*)mp);
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001609}
1610
1611PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001612PyDict_Copy(PyObject *o)
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001613{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001614 PyObject *copy;
Jeremy Hyltona12c7a72000-03-30 22:27:31 +00001615
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001616 if (o == NULL || !PyDict_Check(o)) {
1617 PyErr_BadInternalCall();
1618 return NULL;
1619 }
1620 copy = PyDict_New();
1621 if (copy == NULL)
1622 return NULL;
1623 if (PyDict_Merge(copy, o, 1) == 0)
1624 return copy;
1625 Py_DECREF(copy);
1626 return NULL;
Guido van Rossume3f5b9c1997-05-28 19:15:28 +00001627}
1628
Martin v. Löwis18e16552006-02-15 17:27:45 +00001629Py_ssize_t
Tim Peters1f5871e2000-07-04 17:44:48 +00001630PyDict_Size(PyObject *mp)
Guido van Rossum4199fac1993-11-05 10:18:44 +00001631{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001632 if (mp == NULL || !PyDict_Check(mp)) {
1633 PyErr_BadInternalCall();
1634 return -1;
1635 }
1636 return ((PyDictObject *)mp)->ma_used;
Guido van Rossum4199fac1993-11-05 10:18:44 +00001637}
1638
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001639PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001640PyDict_Keys(PyObject *mp)
Guido van Rossum4b1302b1993-03-27 18:11:32 +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_keys((PyDictObject *)mp);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001647}
1648
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001649PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001650PyDict_Values(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_values((PyDictObject *)mp);
Guido van Rossum25831651993-05-19 14:50:45 +00001657}
1658
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001659PyObject *
Tim Peters1f5871e2000-07-04 17:44:48 +00001660PyDict_Items(PyObject *mp)
Guido van Rossum25831651993-05-19 14:50:45 +00001661{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001662 if (mp == NULL || !PyDict_Check(mp)) {
1663 PyErr_BadInternalCall();
1664 return NULL;
1665 }
1666 return dict_items((PyDictObject *)mp);
Guido van Rossum25831651993-05-19 14:50:45 +00001667}
1668
Tim Peterse63415e2001-05-08 04:38:29 +00001669/* Return 1 if dicts equal, 0 if not, -1 if error.
1670 * Gets out as soon as any difference is detected.
1671 * Uses only Py_EQ comparison.
1672 */
1673static int
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001674dict_equal(PyDictObject *a, PyDictObject *b)
Tim Peterse63415e2001-05-08 04:38:29 +00001675{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001676 Py_ssize_t i;
Tim Peterse63415e2001-05-08 04:38:29 +00001677
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001678 if (a->ma_used != b->ma_used)
1679 /* can't be equal if # of entries differ */
1680 return 0;
Tim Peterseb28ef22001-06-02 05:27:19 +00001681
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001682 /* Same # of entries -- check all of 'em. Exit early on any diff. */
1683 for (i = 0; i <= a->ma_mask; i++) {
1684 PyObject *aval = a->ma_table[i].me_value;
1685 if (aval != NULL) {
1686 int cmp;
1687 PyObject *bval;
1688 PyObject *key = a->ma_table[i].me_key;
1689 /* temporarily bump aval's refcount to ensure it stays
1690 alive until we're done with it */
1691 Py_INCREF(aval);
1692 /* ditto for key */
1693 Py_INCREF(key);
1694 bval = PyDict_GetItemWithError((PyObject *)b, key);
1695 Py_DECREF(key);
1696 if (bval == NULL) {
1697 Py_DECREF(aval);
1698 if (PyErr_Occurred())
1699 return -1;
1700 return 0;
1701 }
1702 cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
1703 Py_DECREF(aval);
1704 if (cmp <= 0) /* error or not equal */
1705 return cmp;
1706 }
1707 }
1708 return 1;
Tim Peterse63415e2001-05-08 04:38:29 +00001709 }
1710
1711static PyObject *
1712dict_richcompare(PyObject *v, PyObject *w, int op)
1713{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001714 int cmp;
1715 PyObject *res;
Tim Peterse63415e2001-05-08 04:38:29 +00001716
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001717 if (!PyDict_Check(v) || !PyDict_Check(w)) {
1718 res = Py_NotImplemented;
1719 }
1720 else if (op == Py_EQ || op == Py_NE) {
1721 cmp = dict_equal((PyDictObject *)v, (PyDictObject *)w);
1722 if (cmp < 0)
1723 return NULL;
1724 res = (cmp == (op == Py_EQ)) ? Py_True : Py_False;
1725 }
1726 else
1727 res = Py_NotImplemented;
1728 Py_INCREF(res);
1729 return res;
Tim Peterse63415e2001-05-08 04:38:29 +00001730 }
1731
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001732static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001733dict_contains(register PyDictObject *mp, PyObject *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001734{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001735 long hash;
1736 PyDictEntry *ep;
Thomas Wouters4d70c3d2006-06-08 14:42:34 +00001737
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001738 if (!PyUnicode_CheckExact(key) ||
1739 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
1740 hash = PyObject_Hash(key);
1741 if (hash == -1)
1742 return NULL;
1743 }
1744 ep = (mp->ma_lookup)(mp, key, hash);
1745 if (ep == NULL)
1746 return NULL;
1747 return PyBool_FromLong(ep->me_value != NULL);
Guido van Rossum4b1302b1993-03-27 18:11:32 +00001748}
1749
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001750static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001751dict_get(register PyDictObject *mp, PyObject *args)
Barry Warsawc38c5da1997-10-06 17:49:20 +00001752{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001753 PyObject *key;
1754 PyObject *failobj = Py_None;
1755 PyObject *val = NULL;
1756 long hash;
1757 PyDictEntry *ep;
Barry Warsawc38c5da1997-10-06 17:49:20 +00001758
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001759 if (!PyArg_UnpackTuple(args, "get", 1, 2, &key, &failobj))
1760 return NULL;
Barry Warsawc38c5da1997-10-06 17:49:20 +00001761
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001762 if (!PyUnicode_CheckExact(key) ||
1763 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
1764 hash = PyObject_Hash(key);
1765 if (hash == -1)
1766 return NULL;
1767 }
1768 ep = (mp->ma_lookup)(mp, key, hash);
1769 if (ep == NULL)
1770 return NULL;
1771 val = ep->me_value;
1772 if (val == NULL)
1773 val = failobj;
1774 Py_INCREF(val);
1775 return val;
Barry Warsawc38c5da1997-10-06 17:49:20 +00001776}
1777
1778
1779static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001780dict_setdefault(register PyDictObject *mp, PyObject *args)
Guido van Rossum164452c2000-08-08 16:12:54 +00001781{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001782 PyObject *key;
1783 PyObject *failobj = Py_None;
1784 PyObject *val = NULL;
1785 long hash;
1786 PyDictEntry *ep;
Guido van Rossum164452c2000-08-08 16:12:54 +00001787
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001788 if (!PyArg_UnpackTuple(args, "setdefault", 1, 2, &key, &failobj))
1789 return NULL;
Guido van Rossum164452c2000-08-08 16:12:54 +00001790
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001791 if (!PyUnicode_CheckExact(key) ||
1792 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
1793 hash = PyObject_Hash(key);
1794 if (hash == -1)
1795 return NULL;
1796 }
1797 ep = (mp->ma_lookup)(mp, key, hash);
1798 if (ep == NULL)
1799 return NULL;
1800 val = ep->me_value;
1801 if (val == NULL) {
1802 val = failobj;
1803 if (PyDict_SetItem((PyObject*)mp, key, failobj))
1804 val = NULL;
1805 }
1806 Py_XINCREF(val);
1807 return val;
Guido van Rossum164452c2000-08-08 16:12:54 +00001808}
1809
1810
1811static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001812dict_clear(register PyDictObject *mp)
Guido van Rossumfb8f1ca1997-03-21 21:55:12 +00001813{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001814 PyDict_Clear((PyObject *)mp);
1815 Py_RETURN_NONE;
Guido van Rossumfb8f1ca1997-03-21 21:55:12 +00001816}
1817
Guido van Rossumba6ab842000-12-12 22:02:18 +00001818static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001819dict_pop(PyDictObject *mp, PyObject *args)
Guido van Rossume027d982002-04-12 15:11:59 +00001820{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001821 long hash;
1822 PyDictEntry *ep;
1823 PyObject *old_value, *old_key;
1824 PyObject *key, *deflt = NULL;
Guido van Rossume027d982002-04-12 15:11:59 +00001825
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001826 if(!PyArg_UnpackTuple(args, "pop", 1, 2, &key, &deflt))
1827 return NULL;
1828 if (mp->ma_used == 0) {
1829 if (deflt) {
1830 Py_INCREF(deflt);
1831 return deflt;
1832 }
1833 PyErr_SetString(PyExc_KeyError,
1834 "pop(): dictionary is empty");
1835 return NULL;
1836 }
1837 if (!PyUnicode_CheckExact(key) ||
1838 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
1839 hash = PyObject_Hash(key);
1840 if (hash == -1)
1841 return NULL;
1842 }
1843 ep = (mp->ma_lookup)(mp, key, hash);
1844 if (ep == NULL)
1845 return NULL;
1846 if (ep->me_value == NULL) {
1847 if (deflt) {
1848 Py_INCREF(deflt);
1849 return deflt;
1850 }
1851 set_key_error(key);
1852 return NULL;
1853 }
1854 old_key = ep->me_key;
1855 Py_INCREF(dummy);
1856 ep->me_key = dummy;
1857 old_value = ep->me_value;
1858 ep->me_value = NULL;
1859 mp->ma_used--;
1860 Py_DECREF(old_key);
1861 return old_value;
Guido van Rossume027d982002-04-12 15:11:59 +00001862}
1863
1864static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001865dict_popitem(PyDictObject *mp)
Guido van Rossumba6ab842000-12-12 22:02:18 +00001866{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001867 Py_ssize_t i = 0;
1868 PyDictEntry *ep;
1869 PyObject *res;
Guido van Rossumba6ab842000-12-12 22:02:18 +00001870
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001871 /* Allocate the result tuple before checking the size. Believe it
1872 * or not, this allocation could trigger a garbage collection which
1873 * could empty the dict, so if we checked the size first and that
1874 * happened, the result would be an infinite loop (searching for an
1875 * entry that no longer exists). Note that the usual popitem()
1876 * idiom is "while d: k, v = d.popitem()". so needing to throw the
1877 * tuple away if the dict *is* empty isn't a significant
1878 * inefficiency -- possible, but unlikely in practice.
1879 */
1880 res = PyTuple_New(2);
1881 if (res == NULL)
1882 return NULL;
1883 if (mp->ma_used == 0) {
1884 Py_DECREF(res);
1885 PyErr_SetString(PyExc_KeyError,
1886 "popitem(): dictionary is empty");
1887 return NULL;
1888 }
1889 /* Set ep to "the first" dict entry with a value. We abuse the hash
1890 * field of slot 0 to hold a search finger:
1891 * If slot 0 has a value, use slot 0.
1892 * Else slot 0 is being used to hold a search finger,
1893 * and we use its hash value as the first index to look.
1894 */
1895 ep = &mp->ma_table[0];
1896 if (ep->me_value == NULL) {
1897 i = ep->me_hash;
1898 /* The hash field may be a real hash value, or it may be a
1899 * legit search finger, or it may be a once-legit search
1900 * finger that's out of bounds now because it wrapped around
1901 * or the table shrunk -- simply make sure it's in bounds now.
1902 */
1903 if (i > mp->ma_mask || i < 1)
1904 i = 1; /* skip slot 0 */
1905 while ((ep = &mp->ma_table[i])->me_value == NULL) {
1906 i++;
1907 if (i > mp->ma_mask)
1908 i = 1;
1909 }
1910 }
1911 PyTuple_SET_ITEM(res, 0, ep->me_key);
1912 PyTuple_SET_ITEM(res, 1, ep->me_value);
1913 Py_INCREF(dummy);
1914 ep->me_key = dummy;
1915 ep->me_value = NULL;
1916 mp->ma_used--;
1917 assert(mp->ma_table[0].me_value == NULL);
1918 mp->ma_table[0].me_hash = i + 1; /* next place to start */
1919 return res;
Guido van Rossumba6ab842000-12-12 22:02:18 +00001920}
1921
Jeremy Hylton8caad492000-06-23 14:18:11 +00001922static int
1923dict_traverse(PyObject *op, visitproc visit, void *arg)
1924{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001925 Py_ssize_t i = 0;
1926 PyObject *pk;
1927 PyObject *pv;
Jeremy Hylton8caad492000-06-23 14:18:11 +00001928
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001929 while (PyDict_Next(op, &i, &pk, &pv)) {
1930 Py_VISIT(pk);
1931 Py_VISIT(pv);
1932 }
1933 return 0;
Jeremy Hylton8caad492000-06-23 14:18:11 +00001934}
1935
1936static int
1937dict_tp_clear(PyObject *op)
1938{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001939 PyDict_Clear(op);
1940 return 0;
Jeremy Hylton8caad492000-06-23 14:18:11 +00001941}
1942
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001943static PyObject *dictiter_new(PyDictObject *, PyTypeObject *);
Guido van Rossum09e563a2001-05-01 12:10:21 +00001944
Martin v. Löwis00709aa2008-06-04 14:18:43 +00001945static PyObject *
1946dict_sizeof(PyDictObject *mp)
1947{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001948 Py_ssize_t res;
Martin v. Löwis00709aa2008-06-04 14:18:43 +00001949
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001950 res = sizeof(PyDictObject);
1951 if (mp->ma_table != mp->ma_smalltable)
1952 res = res + (mp->ma_mask + 1) * sizeof(PyDictEntry);
1953 return PyLong_FromSsize_t(res);
Martin v. Löwis00709aa2008-06-04 14:18:43 +00001954}
1955
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00001956PyDoc_STRVAR(contains__doc__,
1957"D.__contains__(k) -> True if D has a key k, else False");
1958
1959PyDoc_STRVAR(getitem__doc__, "x.__getitem__(y) <==> x[y]");
1960
Martin v. Löwis00709aa2008-06-04 14:18:43 +00001961PyDoc_STRVAR(sizeof__doc__,
1962"D.__sizeof__() -> size of D in memory, in bytes");
1963
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001964PyDoc_STRVAR(get__doc__,
Guido van Rossumefae8862002-09-04 11:29:45 +00001965"D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.");
Tim Petersf7f88b12000-12-13 23:18:45 +00001966
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001967PyDoc_STRVAR(setdefault_doc__,
Guido van Rossumefae8862002-09-04 11:29:45 +00001968"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 +00001969
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001970PyDoc_STRVAR(pop__doc__,
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00001971"D.pop(k[,d]) -> v, remove specified key and return the corresponding value.\n\
Raymond Hettingera3e1e4c2003-03-06 23:54:28 +00001972If key is not found, d is returned if given, otherwise KeyError is raised");
Guido van Rossume027d982002-04-12 15:11:59 +00001973
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001974PyDoc_STRVAR(popitem__doc__,
Tim Petersf7f88b12000-12-13 23:18:45 +00001975"D.popitem() -> (k, v), remove and return some (key, value) pair as a\n\
Benjamin Petersonf10a79a2008-10-11 00:49:57 +000019762-tuple; but raise KeyError if D is empty.");
Tim Petersf7f88b12000-12-13 23:18:45 +00001977
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001978PyDoc_STRVAR(update__doc__,
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00001979"D.update(E, **F) -> None. Update D from dict/iterable E and F.\n"
1980"If E has a .keys() method, does: for k in E: D[k] = E[k]\n\
1981If E lacks .keys() method, does: for (k, v) in E: D[k] = v\n\
1982In either case, this is followed by: for k in F: D[k] = F[k]");
Tim Petersf7f88b12000-12-13 23:18:45 +00001983
Raymond Hettingere33d3df2002-11-27 07:29:33 +00001984PyDoc_STRVAR(fromkeys__doc__,
1985"dict.fromkeys(S[,v]) -> New dict with keys from S and values equal to v.\n\
1986v defaults to None.");
1987
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001988PyDoc_STRVAR(clear__doc__,
1989"D.clear() -> None. Remove all items from D.");
Tim Petersf7f88b12000-12-13 23:18:45 +00001990
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001991PyDoc_STRVAR(copy__doc__,
1992"D.copy() -> a shallow copy of D");
Tim Petersf7f88b12000-12-13 23:18:45 +00001993
Guido van Rossumb90c8482007-02-10 01:11:45 +00001994/* Forward */
1995static PyObject *dictkeys_new(PyObject *);
1996static PyObject *dictitems_new(PyObject *);
1997static PyObject *dictvalues_new(PyObject *);
1998
Guido van Rossum45c85d12007-07-27 16:31:40 +00001999PyDoc_STRVAR(keys__doc__,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002000 "D.keys() -> a set-like object providing a view on D's keys");
Guido van Rossum45c85d12007-07-27 16:31:40 +00002001PyDoc_STRVAR(items__doc__,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002002 "D.items() -> a set-like object providing a view on D's items");
Guido van Rossum45c85d12007-07-27 16:31:40 +00002003PyDoc_STRVAR(values__doc__,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002004 "D.values() -> an object providing a view on D's values");
Guido van Rossumb90c8482007-02-10 01:11:45 +00002005
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002006static PyMethodDef mapp_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002007 {"__contains__",(PyCFunction)dict_contains, METH_O | METH_COEXIST,
2008 contains__doc__},
2009 {"__getitem__", (PyCFunction)dict_subscript, METH_O | METH_COEXIST,
2010 getitem__doc__},
2011 {"__sizeof__", (PyCFunction)dict_sizeof, METH_NOARGS,
2012 sizeof__doc__},
2013 {"get", (PyCFunction)dict_get, METH_VARARGS,
2014 get__doc__},
2015 {"setdefault", (PyCFunction)dict_setdefault, METH_VARARGS,
2016 setdefault_doc__},
2017 {"pop", (PyCFunction)dict_pop, METH_VARARGS,
2018 pop__doc__},
2019 {"popitem", (PyCFunction)dict_popitem, METH_NOARGS,
2020 popitem__doc__},
2021 {"keys", (PyCFunction)dictkeys_new, METH_NOARGS,
2022 keys__doc__},
2023 {"items", (PyCFunction)dictitems_new, METH_NOARGS,
2024 items__doc__},
2025 {"values", (PyCFunction)dictvalues_new, METH_NOARGS,
2026 values__doc__},
2027 {"update", (PyCFunction)dict_update, METH_VARARGS | METH_KEYWORDS,
2028 update__doc__},
2029 {"fromkeys", (PyCFunction)dict_fromkeys, METH_VARARGS | METH_CLASS,
2030 fromkeys__doc__},
2031 {"clear", (PyCFunction)dict_clear, METH_NOARGS,
2032 clear__doc__},
2033 {"copy", (PyCFunction)dict_copy, METH_NOARGS,
2034 copy__doc__},
2035 {NULL, NULL} /* sentinel */
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002036};
2037
Thomas Wouters4d70c3d2006-06-08 14:42:34 +00002038/* Return 1 if `key` is in dict `op`, 0 if not, and -1 on error. */
Raymond Hettingerbc0f2ab2003-11-25 21:12:14 +00002039int
2040PyDict_Contains(PyObject *op, PyObject *key)
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002041{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002042 long hash;
2043 PyDictObject *mp = (PyDictObject *)op;
2044 PyDictEntry *ep;
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002045
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002046 if (!PyUnicode_CheckExact(key) ||
2047 (hash = ((PyUnicodeObject *) key)->hash) == -1) {
2048 hash = PyObject_Hash(key);
2049 if (hash == -1)
2050 return -1;
2051 }
2052 ep = (mp->ma_lookup)(mp, key, hash);
2053 return ep == NULL ? -1 : (ep->me_value != NULL);
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002054}
2055
Thomas Wouterscf297e42007-02-23 15:07:44 +00002056/* Internal version of PyDict_Contains used when the hash value is already known */
2057int
2058_PyDict_Contains(PyObject *op, PyObject *key, long hash)
2059{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002060 PyDictObject *mp = (PyDictObject *)op;
2061 PyDictEntry *ep;
Thomas Wouterscf297e42007-02-23 15:07:44 +00002062
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002063 ep = (mp->ma_lookup)(mp, key, hash);
2064 return ep == NULL ? -1 : (ep->me_value != NULL);
Thomas Wouterscf297e42007-02-23 15:07:44 +00002065}
2066
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002067/* Hack to implement "key in dict" */
2068static PySequenceMethods dict_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002069 0, /* sq_length */
2070 0, /* sq_concat */
2071 0, /* sq_repeat */
2072 0, /* sq_item */
2073 0, /* sq_slice */
2074 0, /* sq_ass_item */
2075 0, /* sq_ass_slice */
2076 PyDict_Contains, /* sq_contains */
2077 0, /* sq_inplace_concat */
2078 0, /* sq_inplace_repeat */
Guido van Rossum0dbb4fb2001-04-20 16:50:40 +00002079};
2080
Guido van Rossum09e563a2001-05-01 12:10:21 +00002081static PyObject *
Tim Peters6d6c1a32001-08-02 04:15:00 +00002082dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2083{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002084 PyObject *self;
Tim Peters6d6c1a32001-08-02 04:15:00 +00002085
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002086 assert(type != NULL && type->tp_alloc != NULL);
2087 self = type->tp_alloc(type, 0);
2088 if (self != NULL) {
2089 PyDictObject *d = (PyDictObject *)self;
2090 /* It's guaranteed that tp->alloc zeroed out the struct. */
2091 assert(d->ma_table == NULL && d->ma_fill == 0 && d->ma_used == 0);
2092 INIT_NONZERO_DICT_SLOTS(d);
2093 d->ma_lookup = lookdict_unicode;
2094 /* The object has been implicitely tracked by tp_alloc */
2095 if (type == &PyDict_Type)
2096 _PyObject_GC_UNTRACK(d);
Tim Peters6d6c1a32001-08-02 04:15:00 +00002097#ifdef SHOW_CONVERSION_COUNTS
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002098 ++created;
Tim Peters6d6c1a32001-08-02 04:15:00 +00002099#endif
Antoine Pitrou3a652b12009-03-23 18:52:06 +00002100#ifdef SHOW_TRACK_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002101 if (_PyObject_GC_IS_TRACKED(d))
2102 count_tracked++;
2103 else
2104 count_untracked++;
Antoine Pitrou3a652b12009-03-23 18:52:06 +00002105#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002106 }
2107 return self;
Tim Peters6d6c1a32001-08-02 04:15:00 +00002108}
2109
Tim Peters25786c02001-09-02 08:22:48 +00002110static int
2111dict_init(PyObject *self, PyObject *args, PyObject *kwds)
2112{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002113 return dict_update_common(self, args, kwds, "dict");
Tim Peters25786c02001-09-02 08:22:48 +00002114}
2115
Tim Peters6d6c1a32001-08-02 04:15:00 +00002116static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00002117dict_iter(PyDictObject *dict)
Guido van Rossum09e563a2001-05-01 12:10:21 +00002118{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002119 return dictiter_new(dict, &PyDictIterKey_Type);
Guido van Rossum09e563a2001-05-01 12:10:21 +00002120}
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002121
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002122PyDoc_STRVAR(dictionary_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002123"dict() -> new empty dictionary\n"
Tim Petersa427a2b2001-10-29 22:25:45 +00002124"dict(mapping) -> new dictionary initialized from a mapping object's\n"
Ezio Melotti7f807b72010-03-01 04:08:34 +00002125" (key, value) pairs\n"
2126"dict(iterable) -> new dictionary initialized as if via:\n"
Tim Peters4d859532001-10-27 18:27:48 +00002127" d = {}\n"
Ezio Melotti7f807b72010-03-01 04:08:34 +00002128" for k, v in iterable:\n"
Just van Rossuma797d812002-11-23 09:45:04 +00002129" d[k] = v\n"
2130"dict(**kwargs) -> new dictionary initialized with the name=value pairs\n"
2131" in the keyword argument list. For example: dict(one=1, two=2)");
Tim Peters25786c02001-09-02 08:22:48 +00002132
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002133PyTypeObject PyDict_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002134 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2135 "dict",
2136 sizeof(PyDictObject),
2137 0,
2138 (destructor)dict_dealloc, /* tp_dealloc */
2139 0, /* tp_print */
2140 0, /* tp_getattr */
2141 0, /* tp_setattr */
2142 0, /* tp_reserved */
2143 (reprfunc)dict_repr, /* tp_repr */
2144 0, /* tp_as_number */
2145 &dict_as_sequence, /* tp_as_sequence */
2146 &dict_as_mapping, /* tp_as_mapping */
2147 (hashfunc)PyObject_HashNotImplemented, /* tp_hash */
2148 0, /* tp_call */
2149 0, /* tp_str */
2150 PyObject_GenericGetAttr, /* tp_getattro */
2151 0, /* tp_setattro */
2152 0, /* tp_as_buffer */
2153 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2154 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_DICT_SUBCLASS, /* tp_flags */
2155 dictionary_doc, /* tp_doc */
2156 dict_traverse, /* tp_traverse */
2157 dict_tp_clear, /* tp_clear */
2158 dict_richcompare, /* tp_richcompare */
2159 0, /* tp_weaklistoffset */
2160 (getiterfunc)dict_iter, /* tp_iter */
2161 0, /* tp_iternext */
2162 mapp_methods, /* tp_methods */
2163 0, /* tp_members */
2164 0, /* tp_getset */
2165 0, /* tp_base */
2166 0, /* tp_dict */
2167 0, /* tp_descr_get */
2168 0, /* tp_descr_set */
2169 0, /* tp_dictoffset */
2170 dict_init, /* tp_init */
2171 PyType_GenericAlloc, /* tp_alloc */
2172 dict_new, /* tp_new */
2173 PyObject_GC_Del, /* tp_free */
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002174};
2175
Guido van Rossum3cca2451997-05-16 14:23:33 +00002176/* For backward compatibility with old dictionary interface */
2177
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002178PyObject *
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +00002179PyDict_GetItemString(PyObject *v, const char *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002180{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002181 PyObject *kv, *rv;
2182 kv = PyUnicode_FromString(key);
2183 if (kv == NULL)
2184 return NULL;
2185 rv = PyDict_GetItem(v, kv);
2186 Py_DECREF(kv);
2187 return rv;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002188}
2189
2190int
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +00002191PyDict_SetItemString(PyObject *v, const char *key, PyObject *item)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002192{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002193 PyObject *kv;
2194 int err;
2195 kv = PyUnicode_FromString(key);
2196 if (kv == NULL)
2197 return -1;
2198 PyUnicode_InternInPlace(&kv); /* XXX Should we really? */
2199 err = PyDict_SetItem(v, kv, item);
2200 Py_DECREF(kv);
2201 return err;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002202}
2203
2204int
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +00002205PyDict_DelItemString(PyObject *v, const char *key)
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002206{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002207 PyObject *kv;
2208 int err;
2209 kv = PyUnicode_FromString(key);
2210 if (kv == NULL)
2211 return -1;
2212 err = PyDict_DelItem(v, kv);
2213 Py_DECREF(kv);
2214 return err;
Guido van Rossum4b1302b1993-03-27 18:11:32 +00002215}
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002216
Raymond Hettinger019a1482004-03-18 02:41:19 +00002217/* Dictionary iterator types */
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002218
2219typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002220 PyObject_HEAD
2221 PyDictObject *di_dict; /* Set to NULL when iterator is exhausted */
2222 Py_ssize_t di_used;
2223 Py_ssize_t di_pos;
2224 PyObject* di_result; /* reusable result tuple for iteritems */
2225 Py_ssize_t len;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002226} dictiterobject;
2227
2228static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +00002229dictiter_new(PyDictObject *dict, PyTypeObject *itertype)
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002230{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002231 dictiterobject *di;
2232 di = PyObject_GC_New(dictiterobject, itertype);
2233 if (di == NULL)
2234 return NULL;
2235 Py_INCREF(dict);
2236 di->di_dict = dict;
2237 di->di_used = dict->ma_used;
2238 di->di_pos = 0;
2239 di->len = dict->ma_used;
2240 if (itertype == &PyDictIterItem_Type) {
2241 di->di_result = PyTuple_Pack(2, Py_None, Py_None);
2242 if (di->di_result == NULL) {
2243 Py_DECREF(di);
2244 return NULL;
2245 }
2246 }
2247 else
2248 di->di_result = NULL;
2249 _PyObject_GC_TRACK(di);
2250 return (PyObject *)di;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002251}
2252
2253static void
2254dictiter_dealloc(dictiterobject *di)
2255{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002256 Py_XDECREF(di->di_dict);
2257 Py_XDECREF(di->di_result);
2258 PyObject_GC_Del(di);
Antoine Pitrou7ddda782009-01-01 15:35:33 +00002259}
2260
2261static int
2262dictiter_traverse(dictiterobject *di, visitproc visit, void *arg)
2263{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002264 Py_VISIT(di->di_dict);
2265 Py_VISIT(di->di_result);
2266 return 0;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002267}
2268
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002269static PyObject *
Raymond Hettinger0ce6dc82004-03-18 08:38:00 +00002270dictiter_len(dictiterobject *di)
2271{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002272 Py_ssize_t len = 0;
2273 if (di->di_dict != NULL && di->di_used == di->di_dict->ma_used)
2274 len = di->len;
2275 return PyLong_FromSize_t(len);
Raymond Hettinger0ce6dc82004-03-18 08:38:00 +00002276}
2277
Guido van Rossumb90c8482007-02-10 01:11:45 +00002278PyDoc_STRVAR(length_hint_doc,
2279 "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002280
2281static PyMethodDef dictiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002282 {"__length_hint__", (PyCFunction)dictiter_len, METH_NOARGS,
2283 length_hint_doc},
2284 {NULL, NULL} /* sentinel */
Raymond Hettinger0ce6dc82004-03-18 08:38:00 +00002285};
2286
Raymond Hettinger019a1482004-03-18 02:41:19 +00002287static PyObject *dictiter_iternextkey(dictiterobject *di)
Guido van Rossum213c7a62001-04-23 14:08:49 +00002288{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002289 PyObject *key;
2290 register Py_ssize_t i, mask;
2291 register PyDictEntry *ep;
2292 PyDictObject *d = di->di_dict;
Guido van Rossum213c7a62001-04-23 14:08:49 +00002293
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002294 if (d == NULL)
2295 return NULL;
2296 assert (PyDict_Check(d));
Guido van Rossum2147df72002-07-16 20:30:22 +00002297
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002298 if (di->di_used != d->ma_used) {
2299 PyErr_SetString(PyExc_RuntimeError,
2300 "dictionary changed size during iteration");
2301 di->di_used = -1; /* Make this state sticky */
2302 return NULL;
2303 }
Guido van Rossum2147df72002-07-16 20:30:22 +00002304
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002305 i = di->di_pos;
2306 if (i < 0)
2307 goto fail;
2308 ep = d->ma_table;
2309 mask = d->ma_mask;
2310 while (i <= mask && ep[i].me_value == NULL)
2311 i++;
2312 di->di_pos = i+1;
2313 if (i > mask)
2314 goto fail;
2315 di->len--;
2316 key = ep[i].me_key;
2317 Py_INCREF(key);
2318 return key;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002319
2320fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002321 Py_DECREF(d);
2322 di->di_dict = NULL;
2323 return NULL;
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002324}
2325
Raymond Hettinger019a1482004-03-18 02:41:19 +00002326PyTypeObject PyDictIterKey_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002327 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2328 "dict_keyiterator", /* tp_name */
2329 sizeof(dictiterobject), /* tp_basicsize */
2330 0, /* tp_itemsize */
2331 /* methods */
2332 (destructor)dictiter_dealloc, /* tp_dealloc */
2333 0, /* tp_print */
2334 0, /* tp_getattr */
2335 0, /* tp_setattr */
2336 0, /* tp_reserved */
2337 0, /* tp_repr */
2338 0, /* tp_as_number */
2339 0, /* tp_as_sequence */
2340 0, /* tp_as_mapping */
2341 0, /* tp_hash */
2342 0, /* tp_call */
2343 0, /* tp_str */
2344 PyObject_GenericGetAttr, /* tp_getattro */
2345 0, /* tp_setattro */
2346 0, /* tp_as_buffer */
2347 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2348 0, /* tp_doc */
2349 (traverseproc)dictiter_traverse, /* tp_traverse */
2350 0, /* tp_clear */
2351 0, /* tp_richcompare */
2352 0, /* tp_weaklistoffset */
2353 PyObject_SelfIter, /* tp_iter */
2354 (iternextfunc)dictiter_iternextkey, /* tp_iternext */
2355 dictiter_methods, /* tp_methods */
2356 0,
Raymond Hettinger019a1482004-03-18 02:41:19 +00002357};
2358
2359static PyObject *dictiter_iternextvalue(dictiterobject *di)
2360{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002361 PyObject *value;
2362 register Py_ssize_t i, mask;
2363 register PyDictEntry *ep;
2364 PyDictObject *d = di->di_dict;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002365
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002366 if (d == NULL)
2367 return NULL;
2368 assert (PyDict_Check(d));
Raymond Hettinger019a1482004-03-18 02:41:19 +00002369
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002370 if (di->di_used != d->ma_used) {
2371 PyErr_SetString(PyExc_RuntimeError,
2372 "dictionary changed size during iteration");
2373 di->di_used = -1; /* Make this state sticky */
2374 return NULL;
2375 }
Raymond Hettinger019a1482004-03-18 02:41:19 +00002376
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002377 i = di->di_pos;
2378 mask = d->ma_mask;
2379 if (i < 0 || i > mask)
2380 goto fail;
2381 ep = d->ma_table;
2382 while ((value=ep[i].me_value) == NULL) {
2383 i++;
2384 if (i > mask)
2385 goto fail;
2386 }
2387 di->di_pos = i+1;
2388 di->len--;
2389 Py_INCREF(value);
2390 return value;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002391
2392fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002393 Py_DECREF(d);
2394 di->di_dict = NULL;
2395 return NULL;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002396}
2397
2398PyTypeObject PyDictIterValue_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002399 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2400 "dict_valueiterator", /* tp_name */
2401 sizeof(dictiterobject), /* tp_basicsize */
2402 0, /* tp_itemsize */
2403 /* methods */
2404 (destructor)dictiter_dealloc, /* tp_dealloc */
2405 0, /* tp_print */
2406 0, /* tp_getattr */
2407 0, /* tp_setattr */
2408 0, /* tp_reserved */
2409 0, /* tp_repr */
2410 0, /* tp_as_number */
2411 0, /* tp_as_sequence */
2412 0, /* tp_as_mapping */
2413 0, /* tp_hash */
2414 0, /* tp_call */
2415 0, /* tp_str */
2416 PyObject_GenericGetAttr, /* tp_getattro */
2417 0, /* tp_setattro */
2418 0, /* tp_as_buffer */
2419 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2420 0, /* tp_doc */
2421 (traverseproc)dictiter_traverse, /* tp_traverse */
2422 0, /* tp_clear */
2423 0, /* tp_richcompare */
2424 0, /* tp_weaklistoffset */
2425 PyObject_SelfIter, /* tp_iter */
2426 (iternextfunc)dictiter_iternextvalue, /* tp_iternext */
2427 dictiter_methods, /* tp_methods */
2428 0,
Raymond Hettinger019a1482004-03-18 02:41:19 +00002429};
2430
2431static PyObject *dictiter_iternextitem(dictiterobject *di)
2432{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002433 PyObject *key, *value, *result = di->di_result;
2434 register Py_ssize_t i, mask;
2435 register PyDictEntry *ep;
2436 PyDictObject *d = di->di_dict;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002437
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002438 if (d == NULL)
2439 return NULL;
2440 assert (PyDict_Check(d));
Raymond Hettinger019a1482004-03-18 02:41:19 +00002441
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002442 if (di->di_used != d->ma_used) {
2443 PyErr_SetString(PyExc_RuntimeError,
2444 "dictionary changed size during iteration");
2445 di->di_used = -1; /* Make this state sticky */
2446 return NULL;
2447 }
Raymond Hettinger019a1482004-03-18 02:41:19 +00002448
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002449 i = di->di_pos;
2450 if (i < 0)
2451 goto fail;
2452 ep = d->ma_table;
2453 mask = d->ma_mask;
2454 while (i <= mask && ep[i].me_value == NULL)
2455 i++;
2456 di->di_pos = i+1;
2457 if (i > mask)
2458 goto fail;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002459
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002460 if (result->ob_refcnt == 1) {
2461 Py_INCREF(result);
2462 Py_DECREF(PyTuple_GET_ITEM(result, 0));
2463 Py_DECREF(PyTuple_GET_ITEM(result, 1));
2464 } else {
2465 result = PyTuple_New(2);
2466 if (result == NULL)
2467 return NULL;
2468 }
2469 di->len--;
2470 key = ep[i].me_key;
2471 value = ep[i].me_value;
2472 Py_INCREF(key);
2473 Py_INCREF(value);
2474 PyTuple_SET_ITEM(result, 0, key);
2475 PyTuple_SET_ITEM(result, 1, value);
2476 return result;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002477
2478fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002479 Py_DECREF(d);
2480 di->di_dict = NULL;
2481 return NULL;
Raymond Hettinger019a1482004-03-18 02:41:19 +00002482}
2483
2484PyTypeObject PyDictIterItem_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002485 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2486 "dict_itemiterator", /* tp_name */
2487 sizeof(dictiterobject), /* tp_basicsize */
2488 0, /* tp_itemsize */
2489 /* methods */
2490 (destructor)dictiter_dealloc, /* tp_dealloc */
2491 0, /* tp_print */
2492 0, /* tp_getattr */
2493 0, /* tp_setattr */
2494 0, /* tp_reserved */
2495 0, /* tp_repr */
2496 0, /* tp_as_number */
2497 0, /* tp_as_sequence */
2498 0, /* tp_as_mapping */
2499 0, /* tp_hash */
2500 0, /* tp_call */
2501 0, /* tp_str */
2502 PyObject_GenericGetAttr, /* tp_getattro */
2503 0, /* tp_setattro */
2504 0, /* tp_as_buffer */
2505 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2506 0, /* tp_doc */
2507 (traverseproc)dictiter_traverse, /* tp_traverse */
2508 0, /* tp_clear */
2509 0, /* tp_richcompare */
2510 0, /* tp_weaklistoffset */
2511 PyObject_SelfIter, /* tp_iter */
2512 (iternextfunc)dictiter_iternextitem, /* tp_iternext */
2513 dictiter_methods, /* tp_methods */
2514 0,
Guido van Rossum59d1d2b2001-04-20 19:13:02 +00002515};
Guido van Rossumb90c8482007-02-10 01:11:45 +00002516
2517
Guido van Rossum3ac67412007-02-10 18:55:06 +00002518/***********************************************/
Guido van Rossumb90c8482007-02-10 01:11:45 +00002519/* View objects for keys(), items(), values(). */
Guido van Rossum3ac67412007-02-10 18:55:06 +00002520/***********************************************/
2521
Guido van Rossumb90c8482007-02-10 01:11:45 +00002522/* The instance lay-out is the same for all three; but the type differs. */
2523
2524typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002525 PyObject_HEAD
2526 PyDictObject *dv_dict;
Guido van Rossumb90c8482007-02-10 01:11:45 +00002527} dictviewobject;
2528
2529
2530static void
Guido van Rossum3ac67412007-02-10 18:55:06 +00002531dictview_dealloc(dictviewobject *dv)
Guido van Rossumb90c8482007-02-10 01:11:45 +00002532{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002533 Py_XDECREF(dv->dv_dict);
2534 PyObject_GC_Del(dv);
Antoine Pitrou7ddda782009-01-01 15:35:33 +00002535}
2536
2537static int
2538dictview_traverse(dictviewobject *dv, visitproc visit, void *arg)
2539{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002540 Py_VISIT(dv->dv_dict);
2541 return 0;
Guido van Rossumb90c8482007-02-10 01:11:45 +00002542}
2543
Guido van Rossum83825ac2007-02-10 04:54:19 +00002544static Py_ssize_t
Guido van Rossum3ac67412007-02-10 18:55:06 +00002545dictview_len(dictviewobject *dv)
Guido van Rossumb90c8482007-02-10 01:11:45 +00002546{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002547 Py_ssize_t len = 0;
2548 if (dv->dv_dict != NULL)
2549 len = dv->dv_dict->ma_used;
2550 return len;
Guido van Rossumb90c8482007-02-10 01:11:45 +00002551}
2552
2553static PyObject *
2554dictview_new(PyObject *dict, PyTypeObject *type)
2555{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002556 dictviewobject *dv;
2557 if (dict == NULL) {
2558 PyErr_BadInternalCall();
2559 return NULL;
2560 }
2561 if (!PyDict_Check(dict)) {
2562 /* XXX Get rid of this restriction later */
2563 PyErr_Format(PyExc_TypeError,
2564 "%s() requires a dict argument, not '%s'",
2565 type->tp_name, dict->ob_type->tp_name);
2566 return NULL;
2567 }
2568 dv = PyObject_GC_New(dictviewobject, type);
2569 if (dv == NULL)
2570 return NULL;
2571 Py_INCREF(dict);
2572 dv->dv_dict = (PyDictObject *)dict;
2573 _PyObject_GC_TRACK(dv);
2574 return (PyObject *)dv;
Guido van Rossumb90c8482007-02-10 01:11:45 +00002575}
2576
Neal Norwitze36f2ba2007-02-26 23:12:28 +00002577/* TODO(guido): The views objects are not complete:
2578
2579 * support more set operations
2580 * support arbitrary mappings?
2581 - either these should be static or exported in dictobject.h
2582 - if public then they should probably be in builtins
2583*/
2584
Guido van Rossumaac530c2007-08-24 22:33:45 +00002585/* Return 1 if self is a subset of other, iterating over self;
2586 0 if not; -1 if an error occurred. */
Guido van Rossumd9214d12007-02-12 02:23:40 +00002587static int
2588all_contained_in(PyObject *self, PyObject *other)
2589{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002590 PyObject *iter = PyObject_GetIter(self);
2591 int ok = 1;
Guido van Rossumd9214d12007-02-12 02:23:40 +00002592
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002593 if (iter == NULL)
2594 return -1;
2595 for (;;) {
2596 PyObject *next = PyIter_Next(iter);
2597 if (next == NULL) {
2598 if (PyErr_Occurred())
2599 ok = -1;
2600 break;
2601 }
2602 ok = PySequence_Contains(other, next);
2603 Py_DECREF(next);
2604 if (ok <= 0)
2605 break;
2606 }
2607 Py_DECREF(iter);
2608 return ok;
Guido van Rossumd9214d12007-02-12 02:23:40 +00002609}
2610
2611static PyObject *
2612dictview_richcompare(PyObject *self, PyObject *other, int op)
2613{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002614 Py_ssize_t len_self, len_other;
2615 int ok;
2616 PyObject *result;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002617
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002618 assert(self != NULL);
2619 assert(PyDictViewSet_Check(self));
2620 assert(other != NULL);
Guido van Rossumd9214d12007-02-12 02:23:40 +00002621
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002622 if (!PyAnySet_Check(other) && !PyDictViewSet_Check(other)) {
2623 Py_INCREF(Py_NotImplemented);
2624 return Py_NotImplemented;
2625 }
Guido van Rossumaac530c2007-08-24 22:33:45 +00002626
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002627 len_self = PyObject_Size(self);
2628 if (len_self < 0)
2629 return NULL;
2630 len_other = PyObject_Size(other);
2631 if (len_other < 0)
2632 return NULL;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002633
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002634 ok = 0;
2635 switch(op) {
Guido van Rossumaac530c2007-08-24 22:33:45 +00002636
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002637 case Py_NE:
2638 case Py_EQ:
2639 if (len_self == len_other)
2640 ok = all_contained_in(self, other);
2641 if (op == Py_NE && ok >= 0)
2642 ok = !ok;
2643 break;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002644
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002645 case Py_LT:
2646 if (len_self < len_other)
2647 ok = all_contained_in(self, other);
2648 break;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002649
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002650 case Py_LE:
2651 if (len_self <= len_other)
2652 ok = all_contained_in(self, other);
2653 break;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002654
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002655 case Py_GT:
2656 if (len_self > len_other)
2657 ok = all_contained_in(other, self);
2658 break;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002659
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002660 case Py_GE:
2661 if (len_self >= len_other)
2662 ok = all_contained_in(other, self);
2663 break;
Guido van Rossumaac530c2007-08-24 22:33:45 +00002664
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002665 }
2666 if (ok < 0)
2667 return NULL;
2668 result = ok ? Py_True : Py_False;
2669 Py_INCREF(result);
2670 return result;
Guido van Rossumd9214d12007-02-12 02:23:40 +00002671}
2672
Raymond Hettingerb0d56af2009-03-03 10:52:49 +00002673static PyObject *
2674dictview_repr(dictviewobject *dv)
2675{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002676 PyObject *seq;
2677 PyObject *result;
Raymond Hettingerb0d56af2009-03-03 10:52:49 +00002678
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002679 seq = PySequence_List((PyObject *)dv);
2680 if (seq == NULL)
2681 return NULL;
2682
2683 result = PyUnicode_FromFormat("%s(%R)", Py_TYPE(dv)->tp_name, seq);
2684 Py_DECREF(seq);
2685 return result;
Raymond Hettingerb0d56af2009-03-03 10:52:49 +00002686}
2687
Guido van Rossum3ac67412007-02-10 18:55:06 +00002688/*** dict_keys ***/
Guido van Rossumb90c8482007-02-10 01:11:45 +00002689
2690static PyObject *
Guido van Rossum3ac67412007-02-10 18:55:06 +00002691dictkeys_iter(dictviewobject *dv)
Guido van Rossumb90c8482007-02-10 01:11:45 +00002692{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002693 if (dv->dv_dict == NULL) {
2694 Py_RETURN_NONE;
2695 }
2696 return dictiter_new(dv->dv_dict, &PyDictIterKey_Type);
Guido van Rossum3ac67412007-02-10 18:55:06 +00002697}
2698
2699static int
2700dictkeys_contains(dictviewobject *dv, PyObject *obj)
2701{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002702 if (dv->dv_dict == NULL)
2703 return 0;
2704 return PyDict_Contains((PyObject *)dv->dv_dict, obj);
Guido van Rossumb90c8482007-02-10 01:11:45 +00002705}
2706
Guido van Rossum83825ac2007-02-10 04:54:19 +00002707static PySequenceMethods dictkeys_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002708 (lenfunc)dictview_len, /* sq_length */
2709 0, /* sq_concat */
2710 0, /* sq_repeat */
2711 0, /* sq_item */
2712 0, /* sq_slice */
2713 0, /* sq_ass_item */
2714 0, /* sq_ass_slice */
2715 (objobjproc)dictkeys_contains, /* sq_contains */
Guido van Rossum83825ac2007-02-10 04:54:19 +00002716};
2717
Guido van Rossum523259b2007-08-24 23:41:22 +00002718static PyObject*
2719dictviews_sub(PyObject* self, PyObject *other)
2720{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002721 PyObject *result = PySet_New(self);
2722 PyObject *tmp;
2723 if (result == NULL)
2724 return NULL;
Guido van Rossum523259b2007-08-24 23:41:22 +00002725
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002726 tmp = PyObject_CallMethod(result, "difference_update", "O", other);
2727 if (tmp == NULL) {
2728 Py_DECREF(result);
2729 return NULL;
2730 }
Guido van Rossum523259b2007-08-24 23:41:22 +00002731
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002732 Py_DECREF(tmp);
2733 return result;
Guido van Rossum523259b2007-08-24 23:41:22 +00002734}
2735
2736static PyObject*
2737dictviews_and(PyObject* self, PyObject *other)
2738{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002739 PyObject *result = PySet_New(self);
2740 PyObject *tmp;
2741 if (result == NULL)
2742 return NULL;
Guido van Rossum523259b2007-08-24 23:41:22 +00002743
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002744 tmp = PyObject_CallMethod(result, "intersection_update", "O", other);
2745 if (tmp == NULL) {
2746 Py_DECREF(result);
2747 return NULL;
2748 }
Guido van Rossum523259b2007-08-24 23:41:22 +00002749
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002750 Py_DECREF(tmp);
2751 return result;
Guido van Rossum523259b2007-08-24 23:41:22 +00002752}
2753
2754static PyObject*
2755dictviews_or(PyObject* self, PyObject *other)
2756{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002757 PyObject *result = PySet_New(self);
2758 PyObject *tmp;
2759 if (result == NULL)
2760 return NULL;
Guido van Rossum523259b2007-08-24 23:41:22 +00002761
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002762 tmp = PyObject_CallMethod(result, "update", "O", other);
2763 if (tmp == NULL) {
2764 Py_DECREF(result);
2765 return NULL;
2766 }
Guido van Rossum523259b2007-08-24 23:41:22 +00002767
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002768 Py_DECREF(tmp);
2769 return result;
Guido van Rossum523259b2007-08-24 23:41:22 +00002770}
2771
2772static PyObject*
2773dictviews_xor(PyObject* self, PyObject *other)
2774{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002775 PyObject *result = PySet_New(self);
2776 PyObject *tmp;
2777 if (result == NULL)
2778 return NULL;
Guido van Rossum523259b2007-08-24 23:41:22 +00002779
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002780 tmp = PyObject_CallMethod(result, "symmetric_difference_update", "O",
2781 other);
2782 if (tmp == NULL) {
2783 Py_DECREF(result);
2784 return NULL;
2785 }
Guido van Rossum523259b2007-08-24 23:41:22 +00002786
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002787 Py_DECREF(tmp);
2788 return result;
Guido van Rossum523259b2007-08-24 23:41:22 +00002789}
2790
2791static PyNumberMethods dictviews_as_number = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002792 0, /*nb_add*/
2793 (binaryfunc)dictviews_sub, /*nb_subtract*/
2794 0, /*nb_multiply*/
2795 0, /*nb_remainder*/
2796 0, /*nb_divmod*/
2797 0, /*nb_power*/
2798 0, /*nb_negative*/
2799 0, /*nb_positive*/
2800 0, /*nb_absolute*/
2801 0, /*nb_bool*/
2802 0, /*nb_invert*/
2803 0, /*nb_lshift*/
2804 0, /*nb_rshift*/
2805 (binaryfunc)dictviews_and, /*nb_and*/
2806 (binaryfunc)dictviews_xor, /*nb_xor*/
2807 (binaryfunc)dictviews_or, /*nb_or*/
Guido van Rossum523259b2007-08-24 23:41:22 +00002808};
2809
Daniel Stutzbach045b3ba2010-09-02 15:06:06 +00002810static PyObject*
2811dictviews_isdisjoint(PyObject *self, PyObject *other)
2812{
2813 PyObject *it;
2814 PyObject *item = NULL;
2815
2816 if (self == other) {
2817 if (dictview_len((dictviewobject *)self) == 0)
2818 Py_RETURN_TRUE;
2819 else
2820 Py_RETURN_FALSE;
2821 }
2822
2823 /* Iterate over the shorter object (only if other is a set,
2824 * because PySequence_Contains may be expensive otherwise): */
2825 if (PyAnySet_Check(other) || PyDictViewSet_Check(other)) {
2826 Py_ssize_t len_self = dictview_len((dictviewobject *)self);
2827 Py_ssize_t len_other = PyObject_Size(other);
2828 if (len_other == -1)
2829 return NULL;
2830
2831 if ((len_other > len_self)) {
2832 PyObject *tmp = other;
2833 other = self;
2834 self = tmp;
2835 }
2836 }
2837
2838 it = PyObject_GetIter(other);
2839 if (it == NULL)
2840 return NULL;
2841
2842 while ((item = PyIter_Next(it)) != NULL) {
2843 int contains = PySequence_Contains(self, item);
2844 Py_DECREF(item);
2845 if (contains == -1) {
2846 Py_DECREF(it);
2847 return NULL;
2848 }
2849
2850 if (contains) {
2851 Py_DECREF(it);
2852 Py_RETURN_FALSE;
2853 }
2854 }
2855 Py_DECREF(it);
2856 if (PyErr_Occurred())
2857 return NULL; /* PyIter_Next raised an exception. */
2858 Py_RETURN_TRUE;
2859}
2860
2861PyDoc_STRVAR(isdisjoint_doc,
2862"Return True if the view and the given iterable have a null intersection.");
2863
Guido van Rossumb90c8482007-02-10 01:11:45 +00002864static PyMethodDef dictkeys_methods[] = {
Daniel Stutzbach045b3ba2010-09-02 15:06:06 +00002865 {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
2866 isdisjoint_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002867 {NULL, NULL} /* sentinel */
Guido van Rossumb90c8482007-02-10 01:11:45 +00002868};
2869
2870PyTypeObject PyDictKeys_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002871 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2872 "dict_keys", /* tp_name */
2873 sizeof(dictviewobject), /* tp_basicsize */
2874 0, /* tp_itemsize */
2875 /* methods */
2876 (destructor)dictview_dealloc, /* tp_dealloc */
2877 0, /* tp_print */
2878 0, /* tp_getattr */
2879 0, /* tp_setattr */
2880 0, /* tp_reserved */
2881 (reprfunc)dictview_repr, /* tp_repr */
2882 &dictviews_as_number, /* tp_as_number */
2883 &dictkeys_as_sequence, /* tp_as_sequence */
2884 0, /* tp_as_mapping */
2885 0, /* tp_hash */
2886 0, /* tp_call */
2887 0, /* tp_str */
2888 PyObject_GenericGetAttr, /* tp_getattro */
2889 0, /* tp_setattro */
2890 0, /* tp_as_buffer */
2891 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2892 0, /* tp_doc */
2893 (traverseproc)dictview_traverse, /* tp_traverse */
2894 0, /* tp_clear */
2895 dictview_richcompare, /* tp_richcompare */
2896 0, /* tp_weaklistoffset */
2897 (getiterfunc)dictkeys_iter, /* tp_iter */
2898 0, /* tp_iternext */
2899 dictkeys_methods, /* tp_methods */
2900 0,
Guido van Rossumb90c8482007-02-10 01:11:45 +00002901};
2902
2903static PyObject *
2904dictkeys_new(PyObject *dict)
2905{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002906 return dictview_new(dict, &PyDictKeys_Type);
Guido van Rossumb90c8482007-02-10 01:11:45 +00002907}
2908
Guido van Rossum3ac67412007-02-10 18:55:06 +00002909/*** dict_items ***/
Guido van Rossumb90c8482007-02-10 01:11:45 +00002910
2911static PyObject *
Guido van Rossum3ac67412007-02-10 18:55:06 +00002912dictitems_iter(dictviewobject *dv)
Guido van Rossumb90c8482007-02-10 01:11:45 +00002913{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002914 if (dv->dv_dict == NULL) {
2915 Py_RETURN_NONE;
2916 }
2917 return dictiter_new(dv->dv_dict, &PyDictIterItem_Type);
Guido van Rossum3ac67412007-02-10 18:55:06 +00002918}
2919
2920static int
2921dictitems_contains(dictviewobject *dv, PyObject *obj)
2922{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002923 PyObject *key, *value, *found;
2924 if (dv->dv_dict == NULL)
2925 return 0;
2926 if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 2)
2927 return 0;
2928 key = PyTuple_GET_ITEM(obj, 0);
2929 value = PyTuple_GET_ITEM(obj, 1);
2930 found = PyDict_GetItem((PyObject *)dv->dv_dict, key);
2931 if (found == NULL) {
2932 if (PyErr_Occurred())
2933 return -1;
2934 return 0;
2935 }
2936 return PyObject_RichCompareBool(value, found, Py_EQ);
Guido van Rossumb90c8482007-02-10 01:11:45 +00002937}
2938
Guido van Rossum83825ac2007-02-10 04:54:19 +00002939static PySequenceMethods dictitems_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002940 (lenfunc)dictview_len, /* sq_length */
2941 0, /* sq_concat */
2942 0, /* sq_repeat */
2943 0, /* sq_item */
2944 0, /* sq_slice */
2945 0, /* sq_ass_item */
2946 0, /* sq_ass_slice */
2947 (objobjproc)dictitems_contains, /* sq_contains */
Guido van Rossum83825ac2007-02-10 04:54:19 +00002948};
2949
Guido van Rossumb90c8482007-02-10 01:11:45 +00002950static PyMethodDef dictitems_methods[] = {
Daniel Stutzbach045b3ba2010-09-02 15:06:06 +00002951 {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
2952 isdisjoint_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002953 {NULL, NULL} /* sentinel */
Guido van Rossumb90c8482007-02-10 01:11:45 +00002954};
2955
2956PyTypeObject PyDictItems_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002957 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2958 "dict_items", /* tp_name */
2959 sizeof(dictviewobject), /* tp_basicsize */
2960 0, /* tp_itemsize */
2961 /* methods */
2962 (destructor)dictview_dealloc, /* tp_dealloc */
2963 0, /* tp_print */
2964 0, /* tp_getattr */
2965 0, /* tp_setattr */
2966 0, /* tp_reserved */
2967 (reprfunc)dictview_repr, /* tp_repr */
2968 &dictviews_as_number, /* tp_as_number */
2969 &dictitems_as_sequence, /* tp_as_sequence */
2970 0, /* tp_as_mapping */
2971 0, /* tp_hash */
2972 0, /* tp_call */
2973 0, /* tp_str */
2974 PyObject_GenericGetAttr, /* tp_getattro */
2975 0, /* tp_setattro */
2976 0, /* tp_as_buffer */
2977 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2978 0, /* tp_doc */
2979 (traverseproc)dictview_traverse, /* tp_traverse */
2980 0, /* tp_clear */
2981 dictview_richcompare, /* tp_richcompare */
2982 0, /* tp_weaklistoffset */
2983 (getiterfunc)dictitems_iter, /* tp_iter */
2984 0, /* tp_iternext */
2985 dictitems_methods, /* tp_methods */
2986 0,
Guido van Rossumb90c8482007-02-10 01:11:45 +00002987};
2988
2989static PyObject *
2990dictitems_new(PyObject *dict)
2991{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002992 return dictview_new(dict, &PyDictItems_Type);
Guido van Rossumb90c8482007-02-10 01:11:45 +00002993}
2994
Guido van Rossum3ac67412007-02-10 18:55:06 +00002995/*** dict_values ***/
Guido van Rossumb90c8482007-02-10 01:11:45 +00002996
2997static PyObject *
Guido van Rossum3ac67412007-02-10 18:55:06 +00002998dictvalues_iter(dictviewobject *dv)
Guido van Rossumb90c8482007-02-10 01:11:45 +00002999{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003000 if (dv->dv_dict == NULL) {
3001 Py_RETURN_NONE;
3002 }
3003 return dictiter_new(dv->dv_dict, &PyDictIterValue_Type);
Guido van Rossumb90c8482007-02-10 01:11:45 +00003004}
3005
Guido van Rossum83825ac2007-02-10 04:54:19 +00003006static PySequenceMethods dictvalues_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003007 (lenfunc)dictview_len, /* sq_length */
3008 0, /* sq_concat */
3009 0, /* sq_repeat */
3010 0, /* sq_item */
3011 0, /* sq_slice */
3012 0, /* sq_ass_item */
3013 0, /* sq_ass_slice */
3014 (objobjproc)0, /* sq_contains */
Guido van Rossum83825ac2007-02-10 04:54:19 +00003015};
3016
Guido van Rossumb90c8482007-02-10 01:11:45 +00003017static PyMethodDef dictvalues_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003018 {NULL, NULL} /* sentinel */
Guido van Rossumb90c8482007-02-10 01:11:45 +00003019};
3020
3021PyTypeObject PyDictValues_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003022 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3023 "dict_values", /* tp_name */
3024 sizeof(dictviewobject), /* tp_basicsize */
3025 0, /* tp_itemsize */
3026 /* methods */
3027 (destructor)dictview_dealloc, /* tp_dealloc */
3028 0, /* tp_print */
3029 0, /* tp_getattr */
3030 0, /* tp_setattr */
3031 0, /* tp_reserved */
3032 (reprfunc)dictview_repr, /* tp_repr */
3033 0, /* tp_as_number */
3034 &dictvalues_as_sequence, /* tp_as_sequence */
3035 0, /* tp_as_mapping */
3036 0, /* tp_hash */
3037 0, /* tp_call */
3038 0, /* tp_str */
3039 PyObject_GenericGetAttr, /* tp_getattro */
3040 0, /* tp_setattro */
3041 0, /* tp_as_buffer */
3042 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3043 0, /* tp_doc */
3044 (traverseproc)dictview_traverse, /* tp_traverse */
3045 0, /* tp_clear */
3046 0, /* tp_richcompare */
3047 0, /* tp_weaklistoffset */
3048 (getiterfunc)dictvalues_iter, /* tp_iter */
3049 0, /* tp_iternext */
3050 dictvalues_methods, /* tp_methods */
3051 0,
Guido van Rossumb90c8482007-02-10 01:11:45 +00003052};
3053
3054static PyObject *
3055dictvalues_new(PyObject *dict)
3056{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003057 return dictview_new(dict, &PyDictValues_Type);
Guido van Rossumb90c8482007-02-10 01:11:45 +00003058}