| Location | Tool | Test ID | Function | Issue |
|---|---|---|---|---|
| /builddir/build/BUILD/Python-2.7.3/Objects/dictobject.c:674:9 | clang-analyzer | Argument to free() is the address of the local variable 'small_copy', which is not memory allocated by malloc() |
1 /* Dictionary object implementation using a hash table */
2
3 /* The distribution includes a separate file, Objects/dictnotes.txt,
4 describing explorations into dictionary design and optimization.
5 It covers typical dictionary use patterns, the parameters for
6 tuning dictionaries, and several ideas for possible optimizations.
7 */
8
9 #include "Python.h"
10
11
12 /* Set a key error with the specified argument, wrapping it in a
13 * tuple automatically so that tuple keys are not unpacked as the
14 * exception arguments. */
15 static void
16 set_key_error(PyObject *arg)
17 {
18 PyObject *tup;
19 tup = PyTuple_Pack(1, arg);
20 if (!tup)
21 return; /* caller will expect error to be set anyway */
22 PyErr_SetObject(PyExc_KeyError, tup);
23 Py_DECREF(tup);
24 }
25
26 /* Define this out if you don't want conversion statistics on exit. */
27 #undef SHOW_CONVERSION_COUNTS
28
29 /* See large comment block below. This must be >= 1. */
30 #define PERTURB_SHIFT 5
31
32 /*
33 Major subtleties ahead: Most hash schemes depend on having a "good" hash
34 function, in the sense of simulating randomness. Python doesn't: its most
35 important hash functions (for strings and ints) are very regular in common
36 cases:
37
38 >>> map(hash, (0, 1, 2, 3))
39 [0, 1, 2, 3]
40 >>> map(hash, ("namea", "nameb", "namec", "named"))
41 [-1658398457, -1658398460, -1658398459, -1658398462]
42 >>>
43
44 This isn't necessarily bad! To the contrary, in a table of size 2**i, taking
45 the low-order i bits as the initial table index is extremely fast, and there
46 are no collisions at all for dicts indexed by a contiguous range of ints.
47 The same is approximately true when keys are "consecutive" strings. So this
48 gives better-than-random behavior in common cases, and that's very desirable.
49
50 OTOH, when collisions occur, the tendency to fill contiguous slices of the
51 hash table makes a good collision resolution strategy crucial. Taking only
52 the last i bits of the hash code is also vulnerable: for example, consider
53 [i << 16 for i in range(20000)] as a set of keys. Since ints are their own
54 hash codes, and this fits in a dict of size 2**15, the last 15 bits of every
55 hash code are all 0: they *all* map to the same table index.
56
57 But catering to unusual cases should not slow the usual ones, so we just take
58 the last i bits anyway. It's up to collision resolution to do the rest. If
59 we *usually* find the key we're looking for on the first try (and, it turns
60 out, we usually do -- the table load factor is kept under 2/3, so the odds
61 are solidly in our favor), then it makes best sense to keep the initial index
62 computation dirt cheap.
63
64 The first half of collision resolution is to visit table indices via this
65 recurrence:
66
67 j = ((5*j) + 1) mod 2**i
68
69 For any initial j in range(2**i), repeating that 2**i times generates each
70 int in range(2**i) exactly once (see any text on random-number generation for
71 proof). By itself, this doesn't help much: like linear probing (setting
72 j += 1, or j -= 1, on each loop trip), it scans the table entries in a fixed
73 order. This would be bad, except that's not the only thing we do, and it's
74 actually *good* in the common cases where hash keys are consecutive. In an
75 example that's really too small to make this entirely clear, for a table of
76 size 2**3 the order of indices is:
77
78 0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating]
79
80 If two things come in at index 5, the first place we look after is index 2,
81 not 6, so if another comes in at index 6 the collision at 5 didn't hurt it.
82 Linear probing is deadly in this case because there the fixed probe order
83 is the *same* as the order consecutive keys are likely to arrive. But it's
84 extremely unlikely hash codes will follow a 5*j+1 recurrence by accident,
85 and certain that consecutive hash codes do not.
86
87 The other half of the strategy is to get the other bits of the hash code
88 into play. This is done by initializing a (unsigned) vrbl "perturb" to the
89 full hash code, and changing the recurrence to:
90
91 j = (5*j) + 1 + perturb;
92 perturb >>= PERTURB_SHIFT;
93 use j % 2**i as the next table index;
94
95 Now the probe sequence depends (eventually) on every bit in the hash code,
96 and the pseudo-scrambling property of recurring on 5*j+1 is more valuable,
97 because it quickly magnifies small differences in the bits that didn't affect
98 the initial index. Note that because perturb is unsigned, if the recurrence
99 is executed often enough perturb eventually becomes and remains 0. At that
100 point (very rarely reached) the recurrence is on (just) 5*j+1 again, and
101 that's certain to find an empty slot eventually (since it generates every int
102 in range(2**i), and we make sure there's always at least one empty slot).
103
104 Selecting a good value for PERTURB_SHIFT is a balancing act. You want it
105 small so that the high bits of the hash code continue to affect the probe
106 sequence across iterations; but you want it large so that in really bad cases
107 the high-order hash bits have an effect on early iterations. 5 was "the
108 best" in minimizing total collisions across experiments Tim Peters ran (on
109 both normal and pathological cases), but 4 and 6 weren't significantly worse.
110
111 Historical: Reimer Behrends contributed the idea of using a polynomial-based
112 approach, using repeated multiplication by x in GF(2**n) where an irreducible
113 polynomial for each table size was chosen such that x was a primitive root.
114 Christian Tismer later extended that to use division by x instead, as an
115 efficient way to get the high bits of the hash code into play. This scheme
116 also gave excellent collision statistics, but was more expensive: two
117 if-tests were required inside the loop; computing "the next" index took about
118 the same number of operations but without as much potential parallelism
119 (e.g., computing 5*j can go on at the same time as computing 1+perturb in the
120 above, and then shifting perturb can be done while the table index is being
121 masked); and the PyDictObject struct required a member to hold the table's
122 polynomial. In Tim's experiments the current scheme ran faster, produced
123 equally good collision statistics, needed less code & used less memory.
124
125 Theoretical Python 2.5 headache: hash codes are only C "long", but
126 sizeof(Py_ssize_t) > sizeof(long) may be possible. In that case, and if a
127 dict is genuinely huge, then only the slots directly reachable via indexing
128 by a C long can be the first slot in a probe sequence. The probe sequence
129 will still eventually reach every slot in the table, but the collision rate
130 on initial probes may be much higher than this scheme was designed for.
131 Getting a hash code as fat as Py_ssize_t is the only real cure. But in
132 practice, this probably won't make a lick of difference for many years (at
133 which point everyone will have terabytes of RAM on 64-bit boxes).
134 */
135
136 /* Object used as dummy key to fill deleted entries */
137 static PyObject *dummy = NULL; /* Initialized by first call to newPyDictObject() */
138
139 #ifdef Py_REF_DEBUG
140 PyObject *
141 _PyDict_Dummy(void)
142 {
143 return dummy;
144 }
145 #endif
146
147 /* forward declarations */
148 static PyDictEntry *
149 lookdict_string(PyDictObject *mp, PyObject *key, long hash);
150
151 #ifdef SHOW_CONVERSION_COUNTS
152 static long created = 0L;
153 static long converted = 0L;
154
155 static void
156 show_counts(void)
157 {
158 fprintf(stderr, "created %ld string dicts\n", created);
159 fprintf(stderr, "converted %ld to normal dicts\n", converted);
160 fprintf(stderr, "%.2f%% conversion rate\n", (100.0*converted)/created);
161 }
162 #endif
163
164 /* Debug statistic to compare allocations with reuse through the free list */
165 #undef SHOW_ALLOC_COUNT
166 #ifdef SHOW_ALLOC_COUNT
167 static size_t count_alloc = 0;
168 static size_t count_reuse = 0;
169
170 static void
171 show_alloc(void)
172 {
173 fprintf(stderr, "Dict allocations: %" PY_FORMAT_SIZE_T "d\n",
174 count_alloc);
175 fprintf(stderr, "Dict reuse through freelist: %" PY_FORMAT_SIZE_T
176 "d\n", count_reuse);
177 fprintf(stderr, "%.2f%% reuse rate\n\n",
178 (100.0*count_reuse/(count_alloc+count_reuse)));
179 }
180 #endif
181
182 /* Debug statistic to count GC tracking of dicts */
183 #ifdef SHOW_TRACK_COUNT
184 static Py_ssize_t count_untracked = 0;
185 static Py_ssize_t count_tracked = 0;
186
187 static void
188 show_track(void)
189 {
190 fprintf(stderr, "Dicts created: %" PY_FORMAT_SIZE_T "d\n",
191 count_tracked + count_untracked);
192 fprintf(stderr, "Dicts tracked by the GC: %" PY_FORMAT_SIZE_T
193 "d\n", count_tracked);
194 fprintf(stderr, "%.2f%% dict tracking rate\n\n",
195 (100.0*count_tracked/(count_untracked+count_tracked)));
196 }
197 #endif
198
199
200 /* Initialization macros.
201 There are two ways to create a dict: PyDict_New() is the main C API
202 function, and the tp_new slot maps to dict_new(). In the latter case we
203 can save a little time over what PyDict_New does because it's guaranteed
204 that the PyDictObject struct is already zeroed out.
205 Everyone except dict_new() should use EMPTY_TO_MINSIZE (unless they have
206 an excellent reason not to).
207 */
208
209 #define INIT_NONZERO_DICT_SLOTS(mp) do { \
210 (mp)->ma_table = (mp)->ma_smalltable; \
211 (mp)->ma_mask = PyDict_MINSIZE - 1; \
212 } while(0)
213
214 #define EMPTY_TO_MINSIZE(mp) do { \
215 memset((mp)->ma_smalltable, 0, sizeof((mp)->ma_smalltable)); \
216 (mp)->ma_used = (mp)->ma_fill = 0; \
217 INIT_NONZERO_DICT_SLOTS(mp); \
218 } while(0)
219
220 /* Dictionary reuse scheme to save calls to malloc, free, and memset */
221 #ifndef PyDict_MAXFREELIST
222 #define PyDict_MAXFREELIST 80
223 #endif
224 static PyDictObject *free_list[PyDict_MAXFREELIST];
225 static int numfree = 0;
226
227 /* Print summary info about the state of the optimized allocator */
228 void
229 _PyDict_DebugMallocStats(FILE *out)
230 {
231 _PyDebugAllocatorStats(out,
232 "free PyDictObject", numfree, sizeof(PyDictObject));
233 }
234
235
236 void
237 PyDict_Fini(void)
238 {
239 PyDictObject *op;
240
241 while (numfree) {
242 op = free_list[--numfree];
243 assert(PyDict_CheckExact(op));
244 PyObject_GC_Del(op);
245 }
246 }
247
248 PyObject *
249 PyDict_New(void)
250 {
251 register PyDictObject *mp;
252 if (dummy == NULL) { /* Auto-initialize dummy */
253 dummy = PyString_FromString("<dummy key>");
254 if (dummy == NULL)
255 return NULL;
256 #ifdef SHOW_CONVERSION_COUNTS
257 Py_AtExit(show_counts);
258 #endif
259 #ifdef SHOW_ALLOC_COUNT
260 Py_AtExit(show_alloc);
261 #endif
262 #ifdef SHOW_TRACK_COUNT
263 Py_AtExit(show_track);
264 #endif
265 }
266 if (numfree) {
267 mp = free_list[--numfree];
268 assert (mp != NULL);
269 assert (Py_TYPE(mp) == &PyDict_Type);
270 _Py_NewReference((PyObject *)mp);
271 if (mp->ma_fill) {
272 EMPTY_TO_MINSIZE(mp);
273 } else {
274 /* At least set ma_table and ma_mask; these are wrong
275 if an empty but presized dict is added to freelist */
276 INIT_NONZERO_DICT_SLOTS(mp);
277 }
278 assert (mp->ma_used == 0);
279 assert (mp->ma_table == mp->ma_smalltable);
280 assert (mp->ma_mask == PyDict_MINSIZE - 1);
281 #ifdef SHOW_ALLOC_COUNT
282 count_reuse++;
283 #endif
284 } else {
285 mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
286 if (mp == NULL)
287 return NULL;
288 EMPTY_TO_MINSIZE(mp);
289 #ifdef SHOW_ALLOC_COUNT
290 count_alloc++;
291 #endif
292 }
293 mp->ma_lookup = lookdict_string;
294 #ifdef SHOW_TRACK_COUNT
295 count_untracked++;
296 #endif
297 #ifdef SHOW_CONVERSION_COUNTS
298 ++created;
299 #endif
300 return (PyObject *)mp;
301 }
302
303 /*
304 The basic lookup function used by all operations.
305 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
306 Open addressing is preferred over chaining since the link overhead for
307 chaining would be substantial (100% with typical malloc overhead).
308
309 The initial probe index is computed as hash mod the table size. Subsequent
310 probe indices are computed as explained earlier.
311
312 All arithmetic on hash should ignore overflow.
313
314 (The details in this version are due to Tim Peters, building on many past
315 contributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and
316 Christian Tismer).
317
318 lookdict() is general-purpose, and may return NULL if (and only if) a
319 comparison raises an exception (this was new in Python 2.5).
320 lookdict_string() below is specialized to string keys, comparison of which can
321 never raise an exception; that function can never return NULL. For both, when
322 the key isn't found a PyDictEntry* is returned for which the me_value field is
323 NULL; this is the slot in the dict at which the key would have been found, and
324 the caller can (if it wishes) add the <key, value> pair to the returned
325 PyDictEntry*.
326 */
327 static PyDictEntry *
328 lookdict(PyDictObject *mp, PyObject *key, register long hash)
329 {
330 register size_t i;
331 register size_t perturb;
332 register PyDictEntry *freeslot;
333 register size_t mask = (size_t)mp->ma_mask;
334 PyDictEntry *ep0 = mp->ma_table;
335 register PyDictEntry *ep;
336 register int cmp;
337 PyObject *startkey;
338
339 i = (size_t)hash & mask;
340 ep = &ep0[i];
341 if (ep->me_key == NULL || ep->me_key == key)
342 return ep;
343
344 if (ep->me_key == dummy)
345 freeslot = ep;
346 else {
347 if (ep->me_hash == hash) {
348 startkey = ep->me_key;
349 Py_INCREF(startkey);
350 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
351 Py_DECREF(startkey);
352 if (cmp < 0)
353 return NULL;
354 if (ep0 == mp->ma_table && ep->me_key == startkey) {
355 if (cmp > 0)
356 return ep;
357 }
358 else {
359 /* The compare did major nasty stuff to the
360 * dict: start over.
361 * XXX A clever adversary could prevent this
362 * XXX from terminating.
363 */
364 return lookdict(mp, key, hash);
365 }
366 }
367 freeslot = NULL;
368 }
369
370 /* In the loop, me_key == dummy is by far (factor of 100s) the
371 least likely outcome, so test for that last. */
372 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
373 i = (i << 2) + i + perturb + 1;
374 ep = &ep0[i & mask];
375 if (ep->me_key == NULL)
376 return freeslot == NULL ? ep : freeslot;
377 if (ep->me_key == key)
378 return ep;
379 if (ep->me_hash == hash && ep->me_key != dummy) {
380 startkey = ep->me_key;
381 Py_INCREF(startkey);
382 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
383 Py_DECREF(startkey);
384 if (cmp < 0)
385 return NULL;
386 if (ep0 == mp->ma_table && ep->me_key == startkey) {
387 if (cmp > 0)
388 return ep;
389 }
390 else {
391 /* The compare did major nasty stuff to the
392 * dict: start over.
393 * XXX A clever adversary could prevent this
394 * XXX from terminating.
395 */
396 return lookdict(mp, key, hash);
397 }
398 }
399 else if (ep->me_key == dummy && freeslot == NULL)
400 freeslot = ep;
401 }
402 assert(0); /* NOT REACHED */
403 return 0;
404 }
405
406 /*
407 * Hacked up version of lookdict which can assume keys are always strings;
408 * this assumption allows testing for errors during PyObject_RichCompareBool()
409 * to be dropped; string-string comparisons never raise exceptions. This also
410 * means we don't need to go through PyObject_RichCompareBool(); we can always
411 * use _PyString_Eq() directly.
412 *
413 * This is valuable because dicts with only string keys are very common.
414 */
415 static PyDictEntry *
416 lookdict_string(PyDictObject *mp, PyObject *key, register long hash)
417 {
418 register size_t i;
419 register size_t perturb;
420 register PyDictEntry *freeslot;
421 register size_t mask = (size_t)mp->ma_mask;
422 PyDictEntry *ep0 = mp->ma_table;
423 register PyDictEntry *ep;
424
425 /* Make sure this function doesn't have to handle non-string keys,
426 including subclasses of str; e.g., one reason to subclass
427 strings is to override __eq__, and for speed we don't cater to
428 that here. */
429 if (!PyString_CheckExact(key)) {
430 #ifdef SHOW_CONVERSION_COUNTS
431 ++converted;
432 #endif
433 mp->ma_lookup = lookdict;
434 return lookdict(mp, key, hash);
435 }
436 i = hash & mask;
437 ep = &ep0[i];
438 if (ep->me_key == NULL || ep->me_key == key)
439 return ep;
440 if (ep->me_key == dummy)
441 freeslot = ep;
442 else {
443 if (ep->me_hash == hash && _PyString_Eq(ep->me_key, key))
444 return ep;
445 freeslot = NULL;
446 }
447
448 /* In the loop, me_key == dummy is by far (factor of 100s) the
449 least likely outcome, so test for that last. */
450 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
451 i = (i << 2) + i + perturb + 1;
452 ep = &ep0[i & mask];
453 if (ep->me_key == NULL)
454 return freeslot == NULL ? ep : freeslot;
455 if (ep->me_key == key
456 || (ep->me_hash == hash
457 && ep->me_key != dummy
458 && _PyString_Eq(ep->me_key, key)))
459 return ep;
460 if (ep->me_key == dummy && freeslot == NULL)
461 freeslot = ep;
462 }
463 assert(0); /* NOT REACHED */
464 return 0;
465 }
466
467 #ifdef SHOW_TRACK_COUNT
468 #define INCREASE_TRACK_COUNT \
469 (count_tracked++, count_untracked--);
470 #define DECREASE_TRACK_COUNT \
471 (count_tracked--, count_untracked++);
472 #else
473 #define INCREASE_TRACK_COUNT
474 #define DECREASE_TRACK_COUNT
475 #endif
476
477 #define MAINTAIN_TRACKING(mp, key, value) \
478 do { \
479 if (!_PyObject_GC_IS_TRACKED(mp)) { \
480 if (_PyObject_GC_MAY_BE_TRACKED(key) || \
481 _PyObject_GC_MAY_BE_TRACKED(value)) { \
482 _PyObject_GC_TRACK(mp); \
483 INCREASE_TRACK_COUNT \
484 } \
485 } \
486 } while(0)
487
488 void
489 _PyDict_MaybeUntrack(PyObject *op)
490 {
491 PyDictObject *mp;
492 PyObject *value;
493 Py_ssize_t mask, i;
494 PyDictEntry *ep;
495
496 if (!PyDict_CheckExact(op) || !_PyObject_GC_IS_TRACKED(op))
497 return;
498
499 mp = (PyDictObject *) op;
500 ep = mp->ma_table;
501 mask = mp->ma_mask;
502 for (i = 0; i <= mask; i++) {
503 if ((value = ep[i].me_value) == NULL)
504 continue;
505 if (_PyObject_GC_MAY_BE_TRACKED(value) ||
506 _PyObject_GC_MAY_BE_TRACKED(ep[i].me_key))
507 return;
508 }
509 DECREASE_TRACK_COUNT
510 _PyObject_GC_UNTRACK(op);
511 }
512
513
514 /*
515 Internal routine to insert a new item into the table.
516 Used both by the internal resize routine and by the public insert routine.
517 Eats a reference to key and one to value.
518 Returns -1 if an error occurred, or 0 on success.
519 */
520 static int
521 insertdict(register PyDictObject *mp, PyObject *key, long hash, PyObject *value)
522 {
523 PyObject *old_value;
524 register PyDictEntry *ep;
525 typedef PyDictEntry *(*lookupfunc)(PyDictObject *, PyObject *, long);
526
527 assert(mp->ma_lookup != NULL);
528 ep = mp->ma_lookup(mp, key, hash);
529 if (ep == NULL) {
530 Py_DECREF(key);
531 Py_DECREF(value);
532 return -1;
533 }
534 MAINTAIN_TRACKING(mp, key, value);
535 if (ep->me_value != NULL) {
536 old_value = ep->me_value;
537 ep->me_value = value;
538 Py_DECREF(old_value); /* which **CAN** re-enter */
539 Py_DECREF(key);
540 }
541 else {
542 if (ep->me_key == NULL)
543 mp->ma_fill++;
544 else {
545 assert(ep->me_key == dummy);
546 Py_DECREF(dummy);
547 }
548 ep->me_key = key;
549 ep->me_hash = (Py_ssize_t)hash;
550 ep->me_value = value;
551 mp->ma_used++;
552 }
553 return 0;
554 }
555
556 /*
557 Internal routine used by dictresize() to insert an item which is
558 known to be absent from the dict. This routine also assumes that
559 the dict contains no deleted entries. Besides the performance benefit,
560 using insertdict() in dictresize() is dangerous (SF bug #1456209).
561 Note that no refcounts are changed by this routine; if needed, the caller
562 is responsible for incref'ing `key` and `value`.
563 */
564 static void
565 insertdict_clean(register PyDictObject *mp, PyObject *key, long hash,
566 PyObject *value)
567 {
568 register size_t i;
569 register size_t perturb;
570 register size_t mask = (size_t)mp->ma_mask;
571 PyDictEntry *ep0 = mp->ma_table;
572 register PyDictEntry *ep;
573
574 MAINTAIN_TRACKING(mp, key, value);
575 i = hash & mask;
576 ep = &ep0[i];
577 for (perturb = hash; ep->me_key != NULL; perturb >>= PERTURB_SHIFT) {
578 i = (i << 2) + i + perturb + 1;
579 ep = &ep0[i & mask];
580 }
581 assert(ep->me_value == NULL);
582 mp->ma_fill++;
583 ep->me_key = key;
584 ep->me_hash = (Py_ssize_t)hash;
585 ep->me_value = value;
586 mp->ma_used++;
587 }
588
589 /*
590 Restructure the table by allocating a new table and reinserting all
591 items again. When entries have been deleted, the new table may
592 actually be smaller than the old one.
593 */
594 static int
595 dictresize(PyDictObject *mp, Py_ssize_t minused)
596 {
597 Py_ssize_t newsize;
598 PyDictEntry *oldtable, *newtable, *ep;
599 Py_ssize_t i;
600 int is_oldtable_malloced;
601 PyDictEntry small_copy[PyDict_MINSIZE];
602
603 assert(minused >= 0);
604
605 /* Find the smallest table size > minused. */
606 for (newsize = PyDict_MINSIZE;
607 newsize <= minused && newsize > 0;
608 newsize <<= 1)
609 ;
610 if (newsize <= 0) {
611 PyErr_NoMemory();
612 return -1;
613 }
614
615 /* Get space for a new table. */
616 oldtable = mp->ma_table;
617 assert(oldtable != NULL);
618 is_oldtable_malloced = oldtable != mp->ma_smalltable;
619
620 if (newsize == PyDict_MINSIZE) {
621 /* A large table is shrinking, or we can't get any smaller. */
622 newtable = mp->ma_smalltable;
623 if (newtable == oldtable) {
624 if (mp->ma_fill == mp->ma_used) {
625 /* No dummies, so no point doing anything. */
626 return 0;
627 }
628 /* We're not going to resize it, but rebuild the
629 table anyway to purge old dummy entries.
630 Subtle: This is *necessary* if fill==size,
631 as lookdict needs at least one virgin slot to
632 terminate failing searches. If fill < size, it's
633 merely desirable, as dummies slow searches. */
634 assert(mp->ma_fill > mp->ma_used);
635 memcpy(small_copy, oldtable, sizeof(small_copy));
636 oldtable = small_copy;
637 }
638 }
639 else {
640 newtable = PyMem_NEW(PyDictEntry, newsize);
641 if (newtable == NULL) {
642 PyErr_NoMemory();
643 return -1;
644 }
645 }
646
647 /* Make the dict empty, using the new table. */
648 assert(newtable != oldtable);
649 mp->ma_table = newtable;
650 mp->ma_mask = newsize - 1;
651 memset(newtable, 0, sizeof(PyDictEntry) * newsize);
652 mp->ma_used = 0;
653 i = mp->ma_fill;
654 mp->ma_fill = 0;
655
656 /* Copy the data over; this is refcount-neutral for active entries;
657 dummy entries aren't copied over, of course */
658 for (ep = oldtable; i > 0; ep++) {
659 if (ep->me_value != NULL) { /* active entry */
660 --i;
661 insertdict_clean(mp, ep->me_key, (long)ep->me_hash,
662 ep->me_value);
663 }
664 else if (ep->me_key != NULL) { /* dummy entry */
665 --i;
666 assert(ep->me_key == dummy);
667 Py_DECREF(ep->me_key);
668 }
669 /* else key == value == NULL: nothing to do */
670 }
671
672 if (is_oldtable_malloced)
673 PyMem_DEL(oldtable);
674 return 0;
(emitted by clang-analyzer)TODO: a detailed trace is available in the data model (not yet rendered in this report)
675 }
676
677 /* Create a new dictionary pre-sized to hold an estimated number of elements.
678 Underestimates are okay because the dictionary will resize as necessary.
679 Overestimates just mean the dictionary will be more sparse than usual.
680 */
681
682 PyObject *
683 _PyDict_NewPresized(Py_ssize_t minused)
684 {
685 PyObject *op = PyDict_New();
686
687 if (minused>5 && op != NULL && dictresize((PyDictObject *)op, minused) == -1) {
688 Py_DECREF(op);
689 return NULL;
690 }
691 return op;
692 }
693
694 /* Note that, for historical reasons, PyDict_GetItem() suppresses all errors
695 * that may occur (originally dicts supported only string keys, and exceptions
696 * weren't possible). So, while the original intent was that a NULL return
697 * meant the key wasn't present, in reality it can mean that, or that an error
698 * (suppressed) occurred while computing the key's hash, or that some error
699 * (suppressed) occurred when comparing keys in the dict's internal probe
700 * sequence. A nasty example of the latter is when a Python-coded comparison
701 * function hits a stack-depth error, which can cause this to return NULL
702 * even if the key is present.
703 */
704 PyObject *
705 PyDict_GetItem(PyObject *op, PyObject *key)
706 {
707 long hash;
708 PyDictObject *mp = (PyDictObject *)op;
709 PyDictEntry *ep;
710 PyThreadState *tstate;
711 if (!PyDict_Check(op))
712 return NULL;
713 if (!PyString_CheckExact(key) ||
714 (hash = ((PyStringObject *) key)->ob_shash) == -1)
715 {
716 hash = PyObject_Hash(key);
717 if (hash == -1) {
718 PyErr_Clear();
719 return NULL;
720 }
721 }
722
723 /* We can arrive here with a NULL tstate during initialization: try
724 running "python -Wi" for an example related to string interning.
725 Let's just hope that no exception occurs then... This must be
726 _PyThreadState_Current and not PyThreadState_GET() because in debug
727 mode, the latter complains if tstate is NULL. */
728 tstate = _PyThreadState_Current;
729 if (tstate != NULL && tstate->curexc_type != NULL) {
730 /* preserve the existing exception */
731 PyObject *err_type, *err_value, *err_tb;
732 PyErr_Fetch(&err_type, &err_value, &err_tb);
733 ep = (mp->ma_lookup)(mp, key, hash);
734 /* ignore errors */
735 PyErr_Restore(err_type, err_value, err_tb);
736 if (ep == NULL)
737 return NULL;
738 }
739 else {
740 ep = (mp->ma_lookup)(mp, key, hash);
741 if (ep == NULL) {
742 PyErr_Clear();
743 return NULL;
744 }
745 }
746 return ep->me_value;
747 }
748
749 /* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
750 * dictionary if it's merely replacing the value for an existing key.
751 * This means that it's safe to loop over a dictionary with PyDict_Next()
752 * and occasionally replace a value -- but you can't insert new keys or
753 * remove them.
754 */
755 int
756 PyDict_SetItem(register PyObject *op, PyObject *key, PyObject *value)
757 {
758 register PyDictObject *mp;
759 register long hash;
760 register Py_ssize_t n_used;
761
762 if (!PyDict_Check(op)) {
763 PyErr_BadInternalCall();
764 return -1;
765 }
766 assert(key);
767 assert(value);
768 mp = (PyDictObject *)op;
769 if (PyString_CheckExact(key)) {
770 hash = ((PyStringObject *)key)->ob_shash;
771 if (hash == -1)
772 hash = PyObject_Hash(key);
773 }
774 else {
775 hash = PyObject_Hash(key);
776 if (hash == -1)
777 return -1;
778 }
779 assert(mp->ma_fill <= mp->ma_mask); /* at least one empty slot */
780 n_used = mp->ma_used;
781 Py_INCREF(value);
782 Py_INCREF(key);
783 if (insertdict(mp, key, hash, value) != 0)
784 return -1;
785 /* If we added a key, we can safely resize. Otherwise just return!
786 * If fill >= 2/3 size, adjust size. Normally, this doubles or
787 * quaduples the size, but it's also possible for the dict to shrink
788 * (if ma_fill is much larger than ma_used, meaning a lot of dict
789 * keys have been * deleted).
790 *
791 * Quadrupling the size improves average dictionary sparseness
792 * (reducing collisions) at the cost of some memory and iteration
793 * speed (which loops over every possible entry). It also halves
794 * the number of expensive resize operations in a growing dictionary.
795 *
796 * Very large dictionaries (over 50K items) use doubling instead.
797 * This may help applications with severe memory constraints.
798 */
799 if (!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))
800 return 0;
801 return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);
802 }
803
804 int
805 PyDict_DelItem(PyObject *op, PyObject *key)
806 {
807 register PyDictObject *mp;
808 register long hash;
809 register PyDictEntry *ep;
810 PyObject *old_value, *old_key;
811
812 if (!PyDict_Check(op)) {
813 PyErr_BadInternalCall();
814 return -1;
815 }
816 assert(key);
817 if (!PyString_CheckExact(key) ||
818 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
819 hash = PyObject_Hash(key);
820 if (hash == -1)
821 return -1;
822 }
823 mp = (PyDictObject *)op;
824 ep = (mp->ma_lookup)(mp, key, hash);
825 if (ep == NULL)
826 return -1;
827 if (ep->me_value == NULL) {
828 set_key_error(key);
829 return -1;
830 }
831 old_key = ep->me_key;
832 Py_INCREF(dummy);
833 ep->me_key = dummy;
834 old_value = ep->me_value;
835 ep->me_value = NULL;
836 mp->ma_used--;
837 Py_DECREF(old_value);
838 Py_DECREF(old_key);
839 return 0;
840 }
841
842 void
843 PyDict_Clear(PyObject *op)
844 {
845 PyDictObject *mp;
846 PyDictEntry *ep, *table;
847 int table_is_malloced;
848 Py_ssize_t fill;
849 PyDictEntry small_copy[PyDict_MINSIZE];
850 #ifdef Py_DEBUG
851 Py_ssize_t i, n;
852 #endif
853
854 if (!PyDict_Check(op))
855 return;
856 mp = (PyDictObject *)op;
857 #ifdef Py_DEBUG
858 n = mp->ma_mask + 1;
859 i = 0;
860 #endif
861
862 table = mp->ma_table;
863 assert(table != NULL);
864 table_is_malloced = table != mp->ma_smalltable;
865
866 /* This is delicate. During the process of clearing the dict,
867 * decrefs can cause the dict to mutate. To avoid fatal confusion
868 * (voice of experience), we have to make the dict empty before
869 * clearing the slots, and never refer to anything via mp->xxx while
870 * clearing.
871 */
872 fill = mp->ma_fill;
873 if (table_is_malloced)
874 EMPTY_TO_MINSIZE(mp);
875
876 else if (fill > 0) {
877 /* It's a small table with something that needs to be cleared.
878 * Afraid the only safe way is to copy the dict entries into
879 * another small table first.
880 */
881 memcpy(small_copy, table, sizeof(small_copy));
882 table = small_copy;
883 EMPTY_TO_MINSIZE(mp);
884 }
885 /* else it's a small table that's already empty */
886
887 /* Now we can finally clear things. If C had refcounts, we could
888 * assert that the refcount on table is 1 now, i.e. that this function
889 * has unique access to it, so decref side-effects can't alter it.
890 */
891 for (ep = table; fill > 0; ++ep) {
892 #ifdef Py_DEBUG
893 assert(i < n);
894 ++i;
895 #endif
896 if (ep->me_key) {
897 --fill;
898 Py_DECREF(ep->me_key);
899 Py_XDECREF(ep->me_value);
900 }
901 #ifdef Py_DEBUG
902 else
903 assert(ep->me_value == NULL);
904 #endif
905 }
906
907 if (table_is_malloced)
908 PyMem_DEL(table);
909 }
910
911 /*
912 * Iterate over a dict. Use like so:
913 *
914 * Py_ssize_t i;
915 * PyObject *key, *value;
916 * i = 0; # important! i should not otherwise be changed by you
917 * while (PyDict_Next(yourdict, &i, &key, &value)) {
918 * Refer to borrowed references in key and value.
919 * }
920 *
921 * CAUTION: In general, it isn't safe to use PyDict_Next in a loop that
922 * mutates the dict. One exception: it is safe if the loop merely changes
923 * the values associated with the keys (but doesn't insert new keys or
924 * delete keys), via PyDict_SetItem().
925 */
926 int
927 PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue)
928 {
929 register Py_ssize_t i;
930 register Py_ssize_t mask;
931 register PyDictEntry *ep;
932
933 if (!PyDict_Check(op))
934 return 0;
935 i = *ppos;
936 if (i < 0)
937 return 0;
938 ep = ((PyDictObject *)op)->ma_table;
939 mask = ((PyDictObject *)op)->ma_mask;
940 while (i <= mask && ep[i].me_value == NULL)
941 i++;
942 *ppos = i+1;
943 if (i > mask)
944 return 0;
945 if (pkey)
946 *pkey = ep[i].me_key;
947 if (pvalue)
948 *pvalue = ep[i].me_value;
949 return 1;
950 }
951
952 /* Internal version of PyDict_Next that returns a hash value in addition to the key and value.*/
953 int
954 _PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue, long *phash)
955 {
956 register Py_ssize_t i;
957 register Py_ssize_t mask;
958 register PyDictEntry *ep;
959
960 if (!PyDict_Check(op))
961 return 0;
962 i = *ppos;
963 if (i < 0)
964 return 0;
965 ep = ((PyDictObject *)op)->ma_table;
966 mask = ((PyDictObject *)op)->ma_mask;
967 while (i <= mask && ep[i].me_value == NULL)
968 i++;
969 *ppos = i+1;
970 if (i > mask)
971 return 0;
972 *phash = (long)(ep[i].me_hash);
973 if (pkey)
974 *pkey = ep[i].me_key;
975 if (pvalue)
976 *pvalue = ep[i].me_value;
977 return 1;
978 }
979
980 /* Methods */
981
982 static void
983 dict_dealloc(register PyDictObject *mp)
984 {
985 register PyDictEntry *ep;
986 Py_ssize_t fill = mp->ma_fill;
987 PyObject_GC_UnTrack(mp);
988 Py_TRASHCAN_SAFE_BEGIN(mp)
989 for (ep = mp->ma_table; fill > 0; ep++) {
990 if (ep->me_key) {
991 --fill;
992 Py_DECREF(ep->me_key);
993 Py_XDECREF(ep->me_value);
994 }
995 }
996 if (mp->ma_table != mp->ma_smalltable)
997 PyMem_DEL(mp->ma_table);
998 if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
999 free_list[numfree++] = mp;
1000 else
1001 Py_TYPE(mp)->tp_free((PyObject *)mp);
1002 Py_TRASHCAN_SAFE_END(mp)
1003 }
1004
1005 static int
1006 dict_print(register PyDictObject *mp, register FILE *fp, register int flags)
1007 {
1008 register Py_ssize_t i;
1009 register Py_ssize_t any;
1010 int status;
1011
1012 status = Py_ReprEnter((PyObject*)mp);
1013 if (status != 0) {
1014 if (status < 0)
1015 return status;
1016 Py_BEGIN_ALLOW_THREADS
1017 fprintf(fp, "{...}");
1018 Py_END_ALLOW_THREADS
1019 return 0;
1020 }
1021
1022 Py_BEGIN_ALLOW_THREADS
1023 fprintf(fp, "{");
1024 Py_END_ALLOW_THREADS
1025 any = 0;
1026 for (i = 0; i <= mp->ma_mask; i++) {
1027 PyDictEntry *ep = mp->ma_table + i;
1028 PyObject *pvalue = ep->me_value;
1029 if (pvalue != NULL) {
1030 /* Prevent PyObject_Repr from deleting value during
1031 key format */
1032 Py_INCREF(pvalue);
1033 if (any++ > 0) {
1034 Py_BEGIN_ALLOW_THREADS
1035 fprintf(fp, ", ");
1036 Py_END_ALLOW_THREADS
1037 }
1038 if (PyObject_Print((PyObject *)ep->me_key, fp, 0)!=0) {
1039 Py_DECREF(pvalue);
1040 Py_ReprLeave((PyObject*)mp);
1041 return -1;
1042 }
1043 Py_BEGIN_ALLOW_THREADS
1044 fprintf(fp, ": ");
1045 Py_END_ALLOW_THREADS
1046 if (PyObject_Print(pvalue, fp, 0) != 0) {
1047 Py_DECREF(pvalue);
1048 Py_ReprLeave((PyObject*)mp);
1049 return -1;
1050 }
1051 Py_DECREF(pvalue);
1052 }
1053 }
1054 Py_BEGIN_ALLOW_THREADS
1055 fprintf(fp, "}");
1056 Py_END_ALLOW_THREADS
1057 Py_ReprLeave((PyObject*)mp);
1058 return 0;
1059 }
1060
1061 static PyObject *
1062 dict_repr(PyDictObject *mp)
1063 {
1064 Py_ssize_t i;
1065 PyObject *s, *temp, *colon = NULL;
1066 PyObject *pieces = NULL, *result = NULL;
1067 PyObject *key, *value;
1068
1069 i = Py_ReprEnter((PyObject *)mp);
1070 if (i != 0) {
1071 return i > 0 ? PyString_FromString("{...}") : NULL;
1072 }
1073
1074 if (mp->ma_used == 0) {
1075 result = PyString_FromString("{}");
1076 goto Done;
1077 }
1078
1079 pieces = PyList_New(0);
1080 if (pieces == NULL)
1081 goto Done;
1082
1083 colon = PyString_FromString(": ");
1084 if (colon == NULL)
1085 goto Done;
1086
1087 /* Do repr() on each key+value pair, and insert ": " between them.
1088 Note that repr may mutate the dict. */
1089 i = 0;
1090 while (PyDict_Next((PyObject *)mp, &i, &key, &value)) {
1091 int status;
1092 /* Prevent repr from deleting value during key format. */
1093 Py_INCREF(value);
1094 s = PyObject_Repr(key);
1095 PyString_Concat(&s, colon);
1096 PyString_ConcatAndDel(&s, PyObject_Repr(value));
1097 Py_DECREF(value);
1098 if (s == NULL)
1099 goto Done;
1100 status = PyList_Append(pieces, s);
1101 Py_DECREF(s); /* append created a new ref */
1102 if (status < 0)
1103 goto Done;
1104 }
1105
1106 /* Add "{}" decorations to the first and last items. */
1107 assert(PyList_GET_SIZE(pieces) > 0);
1108 s = PyString_FromString("{");
1109 if (s == NULL)
1110 goto Done;
1111 temp = PyList_GET_ITEM(pieces, 0);
1112 PyString_ConcatAndDel(&s, temp);
1113 PyList_SET_ITEM(pieces, 0, s);
1114 if (s == NULL)
1115 goto Done;
1116
1117 s = PyString_FromString("}");
1118 if (s == NULL)
1119 goto Done;
1120 temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
1121 PyString_ConcatAndDel(&temp, s);
1122 PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
1123 if (temp == NULL)
1124 goto Done;
1125
1126 /* Paste them all together with ", " between. */
1127 s = PyString_FromString(", ");
1128 if (s == NULL)
1129 goto Done;
1130 result = _PyString_Join(s, pieces);
1131 Py_DECREF(s);
1132
1133 Done:
1134 Py_XDECREF(pieces);
1135 Py_XDECREF(colon);
1136 Py_ReprLeave((PyObject *)mp);
1137 return result;
1138 }
1139
1140 static Py_ssize_t
1141 dict_length(PyDictObject *mp)
1142 {
1143 return mp->ma_used;
1144 }
1145
1146 static PyObject *
1147 dict_subscript(PyDictObject *mp, register PyObject *key)
1148 {
1149 PyObject *v;
1150 long hash;
1151 PyDictEntry *ep;
1152 assert(mp->ma_table != NULL);
1153 if (!PyString_CheckExact(key) ||
1154 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
1155 hash = PyObject_Hash(key);
1156 if (hash == -1)
1157 return NULL;
1158 }
1159 ep = (mp->ma_lookup)(mp, key, hash);
1160 if (ep == NULL)
1161 return NULL;
1162 v = ep->me_value;
1163 if (v == NULL) {
1164 if (!PyDict_CheckExact(mp)) {
1165 /* Look up __missing__ method if we're a subclass. */
1166 PyObject *missing, *res;
1167 static PyObject *missing_str = NULL;
1168 missing = _PyObject_LookupSpecial((PyObject *)mp,
1169 "__missing__",
1170 &missing_str);
1171 if (missing != NULL) {
1172 res = PyObject_CallFunctionObjArgs(missing,
1173 key, NULL);
1174 Py_DECREF(missing);
1175 return res;
1176 }
1177 else if (PyErr_Occurred())
1178 return NULL;
1179 }
1180 set_key_error(key);
1181 return NULL;
1182 }
1183 else
1184 Py_INCREF(v);
1185 return v;
1186 }
1187
1188 static int
1189 dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)
1190 {
1191 if (w == NULL)
1192 return PyDict_DelItem((PyObject *)mp, v);
1193 else
1194 return PyDict_SetItem((PyObject *)mp, v, w);
1195 }
1196
1197 static PyMappingMethods dict_as_mapping = {
1198 (lenfunc)dict_length, /*mp_length*/
1199 (binaryfunc)dict_subscript, /*mp_subscript*/
1200 (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
1201 };
1202
1203 static PyObject *
1204 dict_keys(register PyDictObject *mp)
1205 {
1206 register PyObject *v;
1207 register Py_ssize_t i, j;
1208 PyDictEntry *ep;
1209 Py_ssize_t mask, n;
1210
1211 again:
1212 n = mp->ma_used;
1213 v = PyList_New(n);
1214 if (v == NULL)
1215 return NULL;
1216 if (n != mp->ma_used) {
1217 /* Durnit. The allocations caused the dict to resize.
1218 * Just start over, this shouldn't normally happen.
1219 */
1220 Py_DECREF(v);
1221 goto again;
1222 }
1223 ep = mp->ma_table;
1224 mask = mp->ma_mask;
1225 for (i = 0, j = 0; i <= mask; i++) {
1226 if (ep[i].me_value != NULL) {
1227 PyObject *key = ep[i].me_key;
1228 Py_INCREF(key);
1229 PyList_SET_ITEM(v, j, key);
1230 j++;
1231 }
1232 }
1233 assert(j == n);
1234 return v;
1235 }
1236
1237 static PyObject *
1238 dict_values(register PyDictObject *mp)
1239 {
1240 register PyObject *v;
1241 register Py_ssize_t i, j;
1242 PyDictEntry *ep;
1243 Py_ssize_t mask, n;
1244
1245 again:
1246 n = mp->ma_used;
1247 v = PyList_New(n);
1248 if (v == NULL)
1249 return NULL;
1250 if (n != mp->ma_used) {
1251 /* Durnit. The allocations caused the dict to resize.
1252 * Just start over, this shouldn't normally happen.
1253 */
1254 Py_DECREF(v);
1255 goto again;
1256 }
1257 ep = mp->ma_table;
1258 mask = mp->ma_mask;
1259 for (i = 0, j = 0; i <= mask; i++) {
1260 if (ep[i].me_value != NULL) {
1261 PyObject *value = ep[i].me_value;
1262 Py_INCREF(value);
1263 PyList_SET_ITEM(v, j, value);
1264 j++;
1265 }
1266 }
1267 assert(j == n);
1268 return v;
1269 }
1270
1271 static PyObject *
1272 dict_items(register PyDictObject *mp)
1273 {
1274 register PyObject *v;
1275 register Py_ssize_t i, j, n;
1276 Py_ssize_t mask;
1277 PyObject *item, *key, *value;
1278 PyDictEntry *ep;
1279
1280 /* Preallocate the list of tuples, to avoid allocations during
1281 * the loop over the items, which could trigger GC, which
1282 * could resize the dict. :-(
1283 */
1284 again:
1285 n = mp->ma_used;
1286 v = PyList_New(n);
1287 if (v == NULL)
1288 return NULL;
1289 for (i = 0; i < n; i++) {
1290 item = PyTuple_New(2);
1291 if (item == NULL) {
1292 Py_DECREF(v);
1293 return NULL;
1294 }
1295 PyList_SET_ITEM(v, i, item);
1296 }
1297 if (n != mp->ma_used) {
1298 /* Durnit. The allocations caused the dict to resize.
1299 * Just start over, this shouldn't normally happen.
1300 */
1301 Py_DECREF(v);
1302 goto again;
1303 }
1304 /* Nothing we do below makes any function calls. */
1305 ep = mp->ma_table;
1306 mask = mp->ma_mask;
1307 for (i = 0, j = 0; i <= mask; i++) {
1308 if ((value=ep[i].me_value) != NULL) {
1309 key = ep[i].me_key;
1310 item = PyList_GET_ITEM(v, j);
1311 Py_INCREF(key);
1312 PyTuple_SET_ITEM(item, 0, key);
1313 Py_INCREF(value);
1314 PyTuple_SET_ITEM(item, 1, value);
1315 j++;
1316 }
1317 }
1318 assert(j == n);
1319 return v;
1320 }
1321
1322 static PyObject *
1323 dict_fromkeys(PyObject *cls, PyObject *args)
1324 {
1325 PyObject *seq;
1326 PyObject *value = Py_None;
1327 PyObject *it; /* iter(seq) */
1328 PyObject *key;
1329 PyObject *d;
1330 int status;
1331
1332 if (!PyArg_UnpackTuple(args, "fromkeys", 1, 2, &seq, &value))
1333 return NULL;
1334
1335 d = PyObject_CallObject(cls, NULL);
1336 if (d == NULL)
1337 return NULL;
1338
1339 if (PyDict_CheckExact(d) && PyDict_CheckExact(seq)) {
1340 PyDictObject *mp = (PyDictObject *)d;
1341 PyObject *oldvalue;
1342 Py_ssize_t pos = 0;
1343 PyObject *key;
1344 long hash;
1345
1346 if (dictresize(mp, Py_SIZE(seq))) {
1347 Py_DECREF(d);
1348 return NULL;
1349 }
1350
1351 while (_PyDict_Next(seq, &pos, &key, &oldvalue, &hash)) {
1352 Py_INCREF(key);
1353 Py_INCREF(value);
1354 if (insertdict(mp, key, hash, value)) {
1355 Py_DECREF(d);
1356 return NULL;
1357 }
1358 }
1359 return d;
1360 }
1361
1362 if (PyDict_CheckExact(d) && PyAnySet_CheckExact(seq)) {
1363 PyDictObject *mp = (PyDictObject *)d;
1364 Py_ssize_t pos = 0;
1365 PyObject *key;
1366 long hash;
1367
1368 if (dictresize(mp, PySet_GET_SIZE(seq))) {
1369 Py_DECREF(d);
1370 return NULL;
1371 }
1372
1373 while (_PySet_NextEntry(seq, &pos, &key, &hash)) {
1374 Py_INCREF(key);
1375 Py_INCREF(value);
1376 if (insertdict(mp, key, hash, value)) {
1377 Py_DECREF(d);
1378 return NULL;
1379 }
1380 }
1381 return d;
1382 }
1383
1384 it = PyObject_GetIter(seq);
1385 if (it == NULL){
1386 Py_DECREF(d);
1387 return NULL;
1388 }
1389
1390 if (PyDict_CheckExact(d)) {
1391 while ((key = PyIter_Next(it)) != NULL) {
1392 status = PyDict_SetItem(d, key, value);
1393 Py_DECREF(key);
1394 if (status < 0)
1395 goto Fail;
1396 }
1397 } else {
1398 while ((key = PyIter_Next(it)) != NULL) {
1399 status = PyObject_SetItem(d, key, value);
1400 Py_DECREF(key);
1401 if (status < 0)
1402 goto Fail;
1403 }
1404 }
1405
1406 if (PyErr_Occurred())
1407 goto Fail;
1408 Py_DECREF(it);
1409 return d;
1410
1411 Fail:
1412 Py_DECREF(it);
1413 Py_DECREF(d);
1414 return NULL;
1415 }
1416
1417 static int
1418 dict_update_common(PyObject *self, PyObject *args, PyObject *kwds, char *methname)
1419 {
1420 PyObject *arg = NULL;
1421 int result = 0;
1422
1423 if (!PyArg_UnpackTuple(args, methname, 0, 1, &arg))
1424 result = -1;
1425
1426 else if (arg != NULL) {
1427 if (PyObject_HasAttrString(arg, "keys"))
1428 result = PyDict_Merge(self, arg, 1);
1429 else
1430 result = PyDict_MergeFromSeq2(self, arg, 1);
1431 }
1432 if (result == 0 && kwds != NULL)
1433 result = PyDict_Merge(self, kwds, 1);
1434 return result;
1435 }
1436
1437 static PyObject *
1438 dict_update(PyObject *self, PyObject *args, PyObject *kwds)
1439 {
1440 if (dict_update_common(self, args, kwds, "update") != -1)
1441 Py_RETURN_NONE;
1442 return NULL;
1443 }
1444
1445 /* Update unconditionally replaces existing items.
1446 Merge has a 3rd argument 'override'; if set, it acts like Update,
1447 otherwise it leaves existing items unchanged.
1448
1449 PyDict_{Update,Merge} update/merge from a mapping object.
1450
1451 PyDict_MergeFromSeq2 updates/merges from any iterable object
1452 producing iterable objects of length 2.
1453 */
1454
1455 int
1456 PyDict_MergeFromSeq2(PyObject *d, PyObject *seq2, int override)
1457 {
1458 PyObject *it; /* iter(seq2) */
1459 Py_ssize_t i; /* index into seq2 of current element */
1460 PyObject *item; /* seq2[i] */
1461 PyObject *fast; /* item as a 2-tuple or 2-list */
1462
1463 assert(d != NULL);
1464 assert(PyDict_Check(d));
1465 assert(seq2 != NULL);
1466
1467 it = PyObject_GetIter(seq2);
1468 if (it == NULL)
1469 return -1;
1470
1471 for (i = 0; ; ++i) {
1472 PyObject *key, *value;
1473 Py_ssize_t n;
1474
1475 fast = NULL;
1476 item = PyIter_Next(it);
1477 if (item == NULL) {
1478 if (PyErr_Occurred())
1479 goto Fail;
1480 break;
1481 }
1482
1483 /* Convert item to sequence, and verify length 2. */
1484 fast = PySequence_Fast(item, "");
1485 if (fast == NULL) {
1486 if (PyErr_ExceptionMatches(PyExc_TypeError))
1487 PyErr_Format(PyExc_TypeError,
1488 "cannot convert dictionary update "
1489 "sequence element #%zd to a sequence",
1490 i);
1491 goto Fail;
1492 }
1493 n = PySequence_Fast_GET_SIZE(fast);
1494 if (n != 2) {
1495 PyErr_Format(PyExc_ValueError,
1496 "dictionary update sequence element #%zd "
1497 "has length %zd; 2 is required",
1498 i, n);
1499 goto Fail;
1500 }
1501
1502 /* Update/merge with this (key, value) pair. */
1503 key = PySequence_Fast_GET_ITEM(fast, 0);
1504 value = PySequence_Fast_GET_ITEM(fast, 1);
1505 if (override || PyDict_GetItem(d, key) == NULL) {
1506 int status = PyDict_SetItem(d, key, value);
1507 if (status < 0)
1508 goto Fail;
1509 }
1510 Py_DECREF(fast);
1511 Py_DECREF(item);
1512 }
1513
1514 i = 0;
1515 goto Return;
1516 Fail:
1517 Py_XDECREF(item);
1518 Py_XDECREF(fast);
1519 i = -1;
1520 Return:
1521 Py_DECREF(it);
1522 return Py_SAFE_DOWNCAST(i, Py_ssize_t, int);
1523 }
1524
1525 int
1526 PyDict_Update(PyObject *a, PyObject *b)
1527 {
1528 return PyDict_Merge(a, b, 1);
1529 }
1530
1531 int
1532 PyDict_Merge(PyObject *a, PyObject *b, int override)
1533 {
1534 register PyDictObject *mp, *other;
1535 register Py_ssize_t i;
1536 PyDictEntry *entry;
1537
1538 /* We accept for the argument either a concrete dictionary object,
1539 * or an abstract "mapping" object. For the former, we can do
1540 * things quite efficiently. For the latter, we only require that
1541 * PyMapping_Keys() and PyObject_GetItem() be supported.
1542 */
1543 if (a == NULL || !PyDict_Check(a) || b == NULL) {
1544 PyErr_BadInternalCall();
1545 return -1;
1546 }
1547 mp = (PyDictObject*)a;
1548 if (PyDict_Check(b)) {
1549 other = (PyDictObject*)b;
1550 if (other == mp || other->ma_used == 0)
1551 /* a.update(a) or a.update({}); nothing to do */
1552 return 0;
1553 if (mp->ma_used == 0)
1554 /* Since the target dict is empty, PyDict_GetItem()
1555 * always returns NULL. Setting override to 1
1556 * skips the unnecessary test.
1557 */
1558 override = 1;
1559 /* Do one big resize at the start, rather than
1560 * incrementally resizing as we insert new items. Expect
1561 * that there will be no (or few) overlapping keys.
1562 */
1563 if ((mp->ma_fill + other->ma_used)*3 >= (mp->ma_mask+1)*2) {
1564 if (dictresize(mp, (mp->ma_used + other->ma_used)*2) != 0)
1565 return -1;
1566 }
1567 for (i = 0; i <= other->ma_mask; i++) {
1568 entry = &other->ma_table[i];
1569 if (entry->me_value != NULL &&
1570 (override ||
1571 PyDict_GetItem(a, entry->me_key) == NULL)) {
1572 Py_INCREF(entry->me_key);
1573 Py_INCREF(entry->me_value);
1574 if (insertdict(mp, entry->me_key,
1575 (long)entry->me_hash,
1576 entry->me_value) != 0)
1577 return -1;
1578 }
1579 }
1580 }
1581 else {
1582 /* Do it the generic, slower way */
1583 PyObject *keys = PyMapping_Keys(b);
1584 PyObject *iter;
1585 PyObject *key, *value;
1586 int status;
1587
1588 if (keys == NULL)
1589 /* Docstring says this is equivalent to E.keys() so
1590 * if E doesn't have a .keys() method we want
1591 * AttributeError to percolate up. Might as well
1592 * do the same for any other error.
1593 */
1594 return -1;
1595
1596 iter = PyObject_GetIter(keys);
1597 Py_DECREF(keys);
1598 if (iter == NULL)
1599 return -1;
1600
1601 for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) {
1602 if (!override && PyDict_GetItem(a, key) != NULL) {
1603 Py_DECREF(key);
1604 continue;
1605 }
1606 value = PyObject_GetItem(b, key);
1607 if (value == NULL) {
1608 Py_DECREF(iter);
1609 Py_DECREF(key);
1610 return -1;
1611 }
1612 status = PyDict_SetItem(a, key, value);
1613 Py_DECREF(key);
1614 Py_DECREF(value);
1615 if (status < 0) {
1616 Py_DECREF(iter);
1617 return -1;
1618 }
1619 }
1620 Py_DECREF(iter);
1621 if (PyErr_Occurred())
1622 /* Iterator completed, via error */
1623 return -1;
1624 }
1625 return 0;
1626 }
1627
1628 static PyObject *
1629 dict_copy(register PyDictObject *mp)
1630 {
1631 return PyDict_Copy((PyObject*)mp);
1632 }
1633
1634 PyObject *
1635 PyDict_Copy(PyObject *o)
1636 {
1637 PyObject *copy;
1638
1639 if (o == NULL || !PyDict_Check(o)) {
1640 PyErr_BadInternalCall();
1641 return NULL;
1642 }
1643 copy = PyDict_New();
1644 if (copy == NULL)
1645 return NULL;
1646 if (PyDict_Merge(copy, o, 1) == 0)
1647 return copy;
1648 Py_DECREF(copy);
1649 return NULL;
1650 }
1651
1652 Py_ssize_t
1653 PyDict_Size(PyObject *mp)
1654 {
1655 if (mp == NULL || !PyDict_Check(mp)) {
1656 PyErr_BadInternalCall();
1657 return -1;
1658 }
1659 return ((PyDictObject *)mp)->ma_used;
1660 }
1661
1662 PyObject *
1663 PyDict_Keys(PyObject *mp)
1664 {
1665 if (mp == NULL || !PyDict_Check(mp)) {
1666 PyErr_BadInternalCall();
1667 return NULL;
1668 }
1669 return dict_keys((PyDictObject *)mp);
1670 }
1671
1672 PyObject *
1673 PyDict_Values(PyObject *mp)
1674 {
1675 if (mp == NULL || !PyDict_Check(mp)) {
1676 PyErr_BadInternalCall();
1677 return NULL;
1678 }
1679 return dict_values((PyDictObject *)mp);
1680 }
1681
1682 PyObject *
1683 PyDict_Items(PyObject *mp)
1684 {
1685 if (mp == NULL || !PyDict_Check(mp)) {
1686 PyErr_BadInternalCall();
1687 return NULL;
1688 }
1689 return dict_items((PyDictObject *)mp);
1690 }
1691
1692 /* Subroutine which returns the smallest key in a for which b's value
1693 is different or absent. The value is returned too, through the
1694 pval argument. Both are NULL if no key in a is found for which b's status
1695 differs. The refcounts on (and only on) non-NULL *pval and function return
1696 values must be decremented by the caller (characterize() increments them
1697 to ensure that mutating comparison and PyDict_GetItem calls can't delete
1698 them before the caller is done looking at them). */
1699
1700 static PyObject *
1701 characterize(PyDictObject *a, PyDictObject *b, PyObject **pval)
1702 {
1703 PyObject *akey = NULL; /* smallest key in a s.t. a[akey] != b[akey] */
1704 PyObject *aval = NULL; /* a[akey] */
1705 Py_ssize_t i;
1706 int cmp;
1707
1708 for (i = 0; i <= a->ma_mask; i++) {
1709 PyObject *thiskey, *thisaval, *thisbval;
1710 if (a->ma_table[i].me_value == NULL)
1711 continue;
1712 thiskey = a->ma_table[i].me_key;
1713 Py_INCREF(thiskey); /* keep alive across compares */
1714 if (akey != NULL) {
1715 cmp = PyObject_RichCompareBool(akey, thiskey, Py_LT);
1716 if (cmp < 0) {
1717 Py_DECREF(thiskey);
1718 goto Fail;
1719 }
1720 if (cmp > 0 ||
1721 i > a->ma_mask ||
1722 a->ma_table[i].me_value == NULL)
1723 {
1724 /* Not the *smallest* a key; or maybe it is
1725 * but the compare shrunk the dict so we can't
1726 * find its associated value anymore; or
1727 * maybe it is but the compare deleted the
1728 * a[thiskey] entry.
1729 */
1730 Py_DECREF(thiskey);
1731 continue;
1732 }
1733 }
1734
1735 /* Compare a[thiskey] to b[thiskey]; cmp <- true iff equal. */
1736 thisaval = a->ma_table[i].me_value;
1737 assert(thisaval);
1738 Py_INCREF(thisaval); /* keep alive */
1739 thisbval = PyDict_GetItem((PyObject *)b, thiskey);
1740 if (thisbval == NULL)
1741 cmp = 0;
1742 else {
1743 /* both dicts have thiskey: same values? */
1744 cmp = PyObject_RichCompareBool(
1745 thisaval, thisbval, Py_EQ);
1746 if (cmp < 0) {
1747 Py_DECREF(thiskey);
1748 Py_DECREF(thisaval);
1749 goto Fail;
1750 }
1751 }
1752 if (cmp == 0) {
1753 /* New winner. */
1754 Py_XDECREF(akey);
1755 Py_XDECREF(aval);
1756 akey = thiskey;
1757 aval = thisaval;
1758 }
1759 else {
1760 Py_DECREF(thiskey);
1761 Py_DECREF(thisaval);
1762 }
1763 }
1764 *pval = aval;
1765 return akey;
1766
1767 Fail:
1768 Py_XDECREF(akey);
1769 Py_XDECREF(aval);
1770 *pval = NULL;
1771 return NULL;
1772 }
1773
1774 static int
1775 dict_compare(PyDictObject *a, PyDictObject *b)
1776 {
1777 PyObject *adiff, *bdiff, *aval, *bval;
1778 int res;
1779
1780 /* Compare lengths first */
1781 if (a->ma_used < b->ma_used)
1782 return -1; /* a is shorter */
1783 else if (a->ma_used > b->ma_used)
1784 return 1; /* b is shorter */
1785
1786 /* Same length -- check all keys */
1787 bdiff = bval = NULL;
1788 adiff = characterize(a, b, &aval);
1789 if (adiff == NULL) {
1790 assert(!aval);
1791 /* Either an error, or a is a subset with the same length so
1792 * must be equal.
1793 */
1794 res = PyErr_Occurred() ? -1 : 0;
1795 goto Finished;
1796 }
1797 bdiff = characterize(b, a, &bval);
1798 if (bdiff == NULL && PyErr_Occurred()) {
1799 assert(!bval);
1800 res = -1;
1801 goto Finished;
1802 }
1803 res = 0;
1804 if (bdiff) {
1805 /* bdiff == NULL "should be" impossible now, but perhaps
1806 * the last comparison done by the characterize() on a had
1807 * the side effect of making the dicts equal!
1808 */
1809 res = PyObject_Compare(adiff, bdiff);
1810 }
1811 if (res == 0 && bval != NULL)
1812 res = PyObject_Compare(aval, bval);
1813
1814 Finished:
1815 Py_XDECREF(adiff);
1816 Py_XDECREF(bdiff);
1817 Py_XDECREF(aval);
1818 Py_XDECREF(bval);
1819 return res;
1820 }
1821
1822 /* Return 1 if dicts equal, 0 if not, -1 if error.
1823 * Gets out as soon as any difference is detected.
1824 * Uses only Py_EQ comparison.
1825 */
1826 static int
1827 dict_equal(PyDictObject *a, PyDictObject *b)
1828 {
1829 Py_ssize_t i;
1830
1831 if (a->ma_used != b->ma_used)
1832 /* can't be equal if # of entries differ */
1833 return 0;
1834
1835 /* Same # of entries -- check all of 'em. Exit early on any diff. */
1836 for (i = 0; i <= a->ma_mask; i++) {
1837 PyObject *aval = a->ma_table[i].me_value;
1838 if (aval != NULL) {
1839 int cmp;
1840 PyObject *bval;
1841 PyObject *key = a->ma_table[i].me_key;
1842 /* temporarily bump aval's refcount to ensure it stays
1843 alive until we're done with it */
1844 Py_INCREF(aval);
1845 /* ditto for key */
1846 Py_INCREF(key);
1847 bval = PyDict_GetItem((PyObject *)b, key);
1848 Py_DECREF(key);
1849 if (bval == NULL) {
1850 Py_DECREF(aval);
1851 return 0;
1852 }
1853 cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
1854 Py_DECREF(aval);
1855 if (cmp <= 0) /* error or not equal */
1856 return cmp;
1857 }
1858 }
1859 return 1;
1860 }
1861
1862 static PyObject *
1863 dict_richcompare(PyObject *v, PyObject *w, int op)
1864 {
1865 int cmp;
1866 PyObject *res;
1867
1868 if (!PyDict_Check(v) || !PyDict_Check(w)) {
1869 res = Py_NotImplemented;
1870 }
1871 else if (op == Py_EQ || op == Py_NE) {
1872 cmp = dict_equal((PyDictObject *)v, (PyDictObject *)w);
1873 if (cmp < 0)
1874 return NULL;
1875 res = (cmp == (op == Py_EQ)) ? Py_True : Py_False;
1876 }
1877 else {
1878 /* Py3K warning if comparison isn't == or != */
1879 if (PyErr_WarnPy3k("dict inequality comparisons not supported "
1880 "in 3.x", 1) < 0) {
1881 return NULL;
1882 }
1883 res = Py_NotImplemented;
1884 }
1885 Py_INCREF(res);
1886 return res;
1887 }
1888
1889 static PyObject *
1890 dict_contains(register PyDictObject *mp, PyObject *key)
1891 {
1892 long hash;
1893 PyDictEntry *ep;
1894
1895 if (!PyString_CheckExact(key) ||
1896 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
1897 hash = PyObject_Hash(key);
1898 if (hash == -1)
1899 return NULL;
1900 }
1901 ep = (mp->ma_lookup)(mp, key, hash);
1902 if (ep == NULL)
1903 return NULL;
1904 return PyBool_FromLong(ep->me_value != NULL);
1905 }
1906
1907 static PyObject *
1908 dict_has_key(register PyDictObject *mp, PyObject *key)
1909 {
1910 if (PyErr_WarnPy3k("dict.has_key() not supported in 3.x; "
1911 "use the in operator", 1) < 0)
1912 return NULL;
1913 return dict_contains(mp, key);
1914 }
1915
1916 static PyObject *
1917 dict_get(register PyDictObject *mp, PyObject *args)
1918 {
1919 PyObject *key;
1920 PyObject *failobj = Py_None;
1921 PyObject *val = NULL;
1922 long hash;
1923 PyDictEntry *ep;
1924
1925 if (!PyArg_UnpackTuple(args, "get", 1, 2, &key, &failobj))
1926 return NULL;
1927
1928 if (!PyString_CheckExact(key) ||
1929 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
1930 hash = PyObject_Hash(key);
1931 if (hash == -1)
1932 return NULL;
1933 }
1934 ep = (mp->ma_lookup)(mp, key, hash);
1935 if (ep == NULL)
1936 return NULL;
1937 val = ep->me_value;
1938 if (val == NULL)
1939 val = failobj;
1940 Py_INCREF(val);
1941 return val;
1942 }
1943
1944
1945 static PyObject *
1946 dict_setdefault(register PyDictObject *mp, PyObject *args)
1947 {
1948 PyObject *key;
1949 PyObject *failobj = Py_None;
1950 PyObject *val = NULL;
1951 long hash;
1952 PyDictEntry *ep;
1953
1954 if (!PyArg_UnpackTuple(args, "setdefault", 1, 2, &key, &failobj))
1955 return NULL;
1956
1957 if (!PyString_CheckExact(key) ||
1958 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
1959 hash = PyObject_Hash(key);
1960 if (hash == -1)
1961 return NULL;
1962 }
1963 ep = (mp->ma_lookup)(mp, key, hash);
1964 if (ep == NULL)
1965 return NULL;
1966 val = ep->me_value;
1967 if (val == NULL) {
1968 val = failobj;
1969 if (PyDict_SetItem((PyObject*)mp, key, failobj))
1970 val = NULL;
1971 }
1972 Py_XINCREF(val);
1973 return val;
1974 }
1975
1976
1977 static PyObject *
1978 dict_clear(register PyDictObject *mp)
1979 {
1980 PyDict_Clear((PyObject *)mp);
1981 Py_RETURN_NONE;
1982 }
1983
1984 static PyObject *
1985 dict_pop(PyDictObject *mp, PyObject *args)
1986 {
1987 long hash;
1988 PyDictEntry *ep;
1989 PyObject *old_value, *old_key;
1990 PyObject *key, *deflt = NULL;
1991
1992 if(!PyArg_UnpackTuple(args, "pop", 1, 2, &key, &deflt))
1993 return NULL;
1994 if (mp->ma_used == 0) {
1995 if (deflt) {
1996 Py_INCREF(deflt);
1997 return deflt;
1998 }
1999 set_key_error(key);
2000 return NULL;
2001 }
2002 if (!PyString_CheckExact(key) ||
2003 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
2004 hash = PyObject_Hash(key);
2005 if (hash == -1)
2006 return NULL;
2007 }
2008 ep = (mp->ma_lookup)(mp, key, hash);
2009 if (ep == NULL)
2010 return NULL;
2011 if (ep->me_value == NULL) {
2012 if (deflt) {
2013 Py_INCREF(deflt);
2014 return deflt;
2015 }
2016 set_key_error(key);
2017 return NULL;
2018 }
2019 old_key = ep->me_key;
2020 Py_INCREF(dummy);
2021 ep->me_key = dummy;
2022 old_value = ep->me_value;
2023 ep->me_value = NULL;
2024 mp->ma_used--;
2025 Py_DECREF(old_key);
2026 return old_value;
2027 }
2028
2029 static PyObject *
2030 dict_popitem(PyDictObject *mp)
2031 {
2032 Py_ssize_t i = 0;
2033 PyDictEntry *ep;
2034 PyObject *res;
2035
2036 /* Allocate the result tuple before checking the size. Believe it
2037 * or not, this allocation could trigger a garbage collection which
2038 * could empty the dict, so if we checked the size first and that
2039 * happened, the result would be an infinite loop (searching for an
2040 * entry that no longer exists). Note that the usual popitem()
2041 * idiom is "while d: k, v = d.popitem()". so needing to throw the
2042 * tuple away if the dict *is* empty isn't a significant
2043 * inefficiency -- possible, but unlikely in practice.
2044 */
2045 res = PyTuple_New(2);
2046 if (res == NULL)
2047 return NULL;
2048 if (mp->ma_used == 0) {
2049 Py_DECREF(res);
2050 PyErr_SetString(PyExc_KeyError,
2051 "popitem(): dictionary is empty");
2052 return NULL;
2053 }
2054 /* Set ep to "the first" dict entry with a value. We abuse the hash
2055 * field of slot 0 to hold a search finger:
2056 * If slot 0 has a value, use slot 0.
2057 * Else slot 0 is being used to hold a search finger,
2058 * and we use its hash value as the first index to look.
2059 */
2060 ep = &mp->ma_table[0];
2061 if (ep->me_value == NULL) {
2062 i = ep->me_hash;
2063 /* The hash field may be a real hash value, or it may be a
2064 * legit search finger, or it may be a once-legit search
2065 * finger that's out of bounds now because it wrapped around
2066 * or the table shrunk -- simply make sure it's in bounds now.
2067 */
2068 if (i > mp->ma_mask || i < 1)
2069 i = 1; /* skip slot 0 */
2070 while ((ep = &mp->ma_table[i])->me_value == NULL) {
2071 i++;
2072 if (i > mp->ma_mask)
2073 i = 1;
2074 }
2075 }
2076 PyTuple_SET_ITEM(res, 0, ep->me_key);
2077 PyTuple_SET_ITEM(res, 1, ep->me_value);
2078 Py_INCREF(dummy);
2079 ep->me_key = dummy;
2080 ep->me_value = NULL;
2081 mp->ma_used--;
2082 assert(mp->ma_table[0].me_value == NULL);
2083 mp->ma_table[0].me_hash = i + 1; /* next place to start */
2084 return res;
2085 }
2086
2087 static int
2088 dict_traverse(PyObject *op, visitproc visit, void *arg)
2089 {
2090 Py_ssize_t i = 0;
2091 PyObject *pk;
2092 PyObject *pv;
2093
2094 while (PyDict_Next(op, &i, &pk, &pv)) {
2095 Py_VISIT(pk);
2096 Py_VISIT(pv);
2097 }
2098 return 0;
2099 }
2100
2101 static int
2102 dict_tp_clear(PyObject *op)
2103 {
2104 PyDict_Clear(op);
2105 return 0;
2106 }
2107
2108
2109 extern PyTypeObject PyDictIterKey_Type; /* Forward */
2110 extern PyTypeObject PyDictIterValue_Type; /* Forward */
2111 extern PyTypeObject PyDictIterItem_Type; /* Forward */
2112 static PyObject *dictiter_new(PyDictObject *, PyTypeObject *);
2113
2114 static PyObject *
2115 dict_iterkeys(PyDictObject *dict)
2116 {
2117 return dictiter_new(dict, &PyDictIterKey_Type);
2118 }
2119
2120 static PyObject *
2121 dict_itervalues(PyDictObject *dict)
2122 {
2123 return dictiter_new(dict, &PyDictIterValue_Type);
2124 }
2125
2126 static PyObject *
2127 dict_iteritems(PyDictObject *dict)
2128 {
2129 return dictiter_new(dict, &PyDictIterItem_Type);
2130 }
2131
2132 static PyObject *
2133 dict_sizeof(PyDictObject *mp)
2134 {
2135 Py_ssize_t res;
2136
2137 res = sizeof(PyDictObject);
2138 if (mp->ma_table != mp->ma_smalltable)
2139 res = res + (mp->ma_mask + 1) * sizeof(PyDictEntry);
2140 return PyInt_FromSsize_t(res);
2141 }
2142
2143 PyDoc_STRVAR(has_key__doc__,
2144 "D.has_key(k) -> True if D has a key k, else False");
2145
2146 PyDoc_STRVAR(contains__doc__,
2147 "D.__contains__(k) -> True if D has a key k, else False");
2148
2149 PyDoc_STRVAR(getitem__doc__, "x.__getitem__(y) <==> x[y]");
2150
2151 PyDoc_STRVAR(sizeof__doc__,
2152 "D.__sizeof__() -> size of D in memory, in bytes");
2153
2154 PyDoc_STRVAR(get__doc__,
2155 "D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.");
2156
2157 PyDoc_STRVAR(setdefault_doc__,
2158 "D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D");
2159
2160 PyDoc_STRVAR(pop__doc__,
2161 "D.pop(k[,d]) -> v, remove specified key and return the corresponding value.\n\
2162 If key is not found, d is returned if given, otherwise KeyError is raised");
2163
2164 PyDoc_STRVAR(popitem__doc__,
2165 "D.popitem() -> (k, v), remove and return some (key, value) pair as a\n\
2166 2-tuple; but raise KeyError if D is empty.");
2167
2168 PyDoc_STRVAR(keys__doc__,
2169 "D.keys() -> list of D's keys");
2170
2171 PyDoc_STRVAR(items__doc__,
2172 "D.items() -> list of D's (key, value) pairs, as 2-tuples");
2173
2174 PyDoc_STRVAR(values__doc__,
2175 "D.values() -> list of D's values");
2176
2177 PyDoc_STRVAR(update__doc__,
2178 "D.update([E, ]**F) -> None. Update D from dict/iterable E and F.\n"
2179 "If E present and has a .keys() method, does: for k in E: D[k] = E[k]\n\
2180 If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v\n\
2181 In either case, this is followed by: for k in F: D[k] = F[k]");
2182
2183 PyDoc_STRVAR(fromkeys__doc__,
2184 "dict.fromkeys(S[,v]) -> New dict with keys from S and values equal to v.\n\
2185 v defaults to None.");
2186
2187 PyDoc_STRVAR(clear__doc__,
2188 "D.clear() -> None. Remove all items from D.");
2189
2190 PyDoc_STRVAR(copy__doc__,
2191 "D.copy() -> a shallow copy of D");
2192
2193 PyDoc_STRVAR(iterkeys__doc__,
2194 "D.iterkeys() -> an iterator over the keys of D");
2195
2196 PyDoc_STRVAR(itervalues__doc__,
2197 "D.itervalues() -> an iterator over the values of D");
2198
2199 PyDoc_STRVAR(iteritems__doc__,
2200 "D.iteritems() -> an iterator over the (key, value) items of D");
2201
2202 /* Forward */
2203 static PyObject *dictkeys_new(PyObject *);
2204 static PyObject *dictitems_new(PyObject *);
2205 static PyObject *dictvalues_new(PyObject *);
2206
2207 PyDoc_STRVAR(viewkeys__doc__,
2208 "D.viewkeys() -> a set-like object providing a view on D's keys");
2209 PyDoc_STRVAR(viewitems__doc__,
2210 "D.viewitems() -> a set-like object providing a view on D's items");
2211 PyDoc_STRVAR(viewvalues__doc__,
2212 "D.viewvalues() -> an object providing a view on D's values");
2213
2214 static PyMethodDef mapp_methods[] = {
2215 {"__contains__",(PyCFunction)dict_contains, METH_O | METH_COEXIST,
2216 contains__doc__},
2217 {"__getitem__", (PyCFunction)dict_subscript, METH_O | METH_COEXIST,
2218 getitem__doc__},
2219 {"__sizeof__", (PyCFunction)dict_sizeof, METH_NOARGS,
2220 sizeof__doc__},
2221 {"has_key", (PyCFunction)dict_has_key, METH_O,
2222 has_key__doc__},
2223 {"get", (PyCFunction)dict_get, METH_VARARGS,
2224 get__doc__},
2225 {"setdefault", (PyCFunction)dict_setdefault, METH_VARARGS,
2226 setdefault_doc__},
2227 {"pop", (PyCFunction)dict_pop, METH_VARARGS,
2228 pop__doc__},
2229 {"popitem", (PyCFunction)dict_popitem, METH_NOARGS,
2230 popitem__doc__},
2231 {"keys", (PyCFunction)dict_keys, METH_NOARGS,
2232 keys__doc__},
2233 {"items", (PyCFunction)dict_items, METH_NOARGS,
2234 items__doc__},
2235 {"values", (PyCFunction)dict_values, METH_NOARGS,
2236 values__doc__},
2237 {"viewkeys", (PyCFunction)dictkeys_new, METH_NOARGS,
2238 viewkeys__doc__},
2239 {"viewitems", (PyCFunction)dictitems_new, METH_NOARGS,
2240 viewitems__doc__},
2241 {"viewvalues", (PyCFunction)dictvalues_new, METH_NOARGS,
2242 viewvalues__doc__},
2243 {"update", (PyCFunction)dict_update, METH_VARARGS | METH_KEYWORDS,
2244 update__doc__},
2245 {"fromkeys", (PyCFunction)dict_fromkeys, METH_VARARGS | METH_CLASS,
2246 fromkeys__doc__},
2247 {"clear", (PyCFunction)dict_clear, METH_NOARGS,
2248 clear__doc__},
2249 {"copy", (PyCFunction)dict_copy, METH_NOARGS,
2250 copy__doc__},
2251 {"iterkeys", (PyCFunction)dict_iterkeys, METH_NOARGS,
2252 iterkeys__doc__},
2253 {"itervalues", (PyCFunction)dict_itervalues, METH_NOARGS,
2254 itervalues__doc__},
2255 {"iteritems", (PyCFunction)dict_iteritems, METH_NOARGS,
2256 iteritems__doc__},
2257 {NULL, NULL} /* sentinel */
2258 };
2259
2260 /* Return 1 if `key` is in dict `op`, 0 if not, and -1 on error. */
2261 int
2262 PyDict_Contains(PyObject *op, PyObject *key)
2263 {
2264 long hash;
2265 PyDictObject *mp = (PyDictObject *)op;
2266 PyDictEntry *ep;
2267
2268 if (!PyString_CheckExact(key) ||
2269 (hash = ((PyStringObject *) key)->ob_shash) == -1) {
2270 hash = PyObject_Hash(key);
2271 if (hash == -1)
2272 return -1;
2273 }
2274 ep = (mp->ma_lookup)(mp, key, hash);
2275 return ep == NULL ? -1 : (ep->me_value != NULL);
2276 }
2277
2278 /* Internal version of PyDict_Contains used when the hash value is already known */
2279 int
2280 _PyDict_Contains(PyObject *op, PyObject *key, long hash)
2281 {
2282 PyDictObject *mp = (PyDictObject *)op;
2283 PyDictEntry *ep;
2284
2285 ep = (mp->ma_lookup)(mp, key, hash);
2286 return ep == NULL ? -1 : (ep->me_value != NULL);
2287 }
2288
2289 /* Hack to implement "key in dict" */
2290 static PySequenceMethods dict_as_sequence = {
2291 0, /* sq_length */
2292 0, /* sq_concat */
2293 0, /* sq_repeat */
2294 0, /* sq_item */
2295 0, /* sq_slice */
2296 0, /* sq_ass_item */
2297 0, /* sq_ass_slice */
2298 PyDict_Contains, /* sq_contains */
2299 0, /* sq_inplace_concat */
2300 0, /* sq_inplace_repeat */
2301 };
2302
2303 static PyObject *
2304 dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2305 {
2306 PyObject *self;
2307
2308 assert(type != NULL && type->tp_alloc != NULL);
2309 self = type->tp_alloc(type, 0);
2310 if (self != NULL) {
2311 PyDictObject *d = (PyDictObject *)self;
2312 /* It's guaranteed that tp->alloc zeroed out the struct. */
2313 assert(d->ma_table == NULL && d->ma_fill == 0 && d->ma_used == 0);
2314 INIT_NONZERO_DICT_SLOTS(d);
2315 d->ma_lookup = lookdict_string;
2316 /* The object has been implicitly tracked by tp_alloc */
2317 if (type == &PyDict_Type)
2318 _PyObject_GC_UNTRACK(d);
2319 #ifdef SHOW_CONVERSION_COUNTS
2320 ++created;
2321 #endif
2322 #ifdef SHOW_TRACK_COUNT
2323 if (_PyObject_GC_IS_TRACKED(d))
2324 count_tracked++;
2325 else
2326 count_untracked++;
2327 #endif
2328 }
2329 return self;
2330 }
2331
2332 static int
2333 dict_init(PyObject *self, PyObject *args, PyObject *kwds)
2334 {
2335 return dict_update_common(self, args, kwds, "dict");
2336 }
2337
2338 static PyObject *
2339 dict_iter(PyDictObject *dict)
2340 {
2341 return dictiter_new(dict, &PyDictIterKey_Type);
2342 }
2343
2344 PyDoc_STRVAR(dictionary_doc,
2345 "dict() -> new empty dictionary\n"
2346 "dict(mapping) -> new dictionary initialized from a mapping object's\n"
2347 " (key, value) pairs\n"
2348 "dict(iterable) -> new dictionary initialized as if via:\n"
2349 " d = {}\n"
2350 " for k, v in iterable:\n"
2351 " d[k] = v\n"
2352 "dict(**kwargs) -> new dictionary initialized with the name=value pairs\n"
2353 " in the keyword argument list. For example: dict(one=1, two=2)");
2354
2355 PyTypeObject PyDict_Type = {
2356 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2357 "dict",
2358 sizeof(PyDictObject),
2359 0,
2360 (destructor)dict_dealloc, /* tp_dealloc */
2361 (printfunc)dict_print, /* tp_print */
2362 0, /* tp_getattr */
2363 0, /* tp_setattr */
2364 (cmpfunc)dict_compare, /* tp_compare */
2365 (reprfunc)dict_repr, /* tp_repr */
2366 0, /* tp_as_number */
2367 &dict_as_sequence, /* tp_as_sequence */
2368 &dict_as_mapping, /* tp_as_mapping */
2369 (hashfunc)PyObject_HashNotImplemented, /* tp_hash */
2370 0, /* tp_call */
2371 0, /* tp_str */
2372 PyObject_GenericGetAttr, /* tp_getattro */
2373 0, /* tp_setattro */
2374 0, /* tp_as_buffer */
2375 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2376 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_DICT_SUBCLASS, /* tp_flags */
2377 dictionary_doc, /* tp_doc */
2378 dict_traverse, /* tp_traverse */
2379 dict_tp_clear, /* tp_clear */
2380 dict_richcompare, /* tp_richcompare */
2381 0, /* tp_weaklistoffset */
2382 (getiterfunc)dict_iter, /* tp_iter */
2383 0, /* tp_iternext */
2384 mapp_methods, /* tp_methods */
2385 0, /* tp_members */
2386 0, /* tp_getset */
2387 0, /* tp_base */
2388 0, /* tp_dict */
2389 0, /* tp_descr_get */
2390 0, /* tp_descr_set */
2391 0, /* tp_dictoffset */
2392 dict_init, /* tp_init */
2393 PyType_GenericAlloc, /* tp_alloc */
2394 dict_new, /* tp_new */
2395 PyObject_GC_Del, /* tp_free */
2396 };
2397
2398 /* For backward compatibility with old dictionary interface */
2399
2400 PyObject *
2401 PyDict_GetItemString(PyObject *v, const char *key)
2402 {
2403 PyObject *kv, *rv;
2404 kv = PyString_FromString(key);
2405 if (kv == NULL)
2406 return NULL;
2407 rv = PyDict_GetItem(v, kv);
2408 Py_DECREF(kv);
2409 return rv;
2410 }
2411
2412 int
2413 PyDict_SetItemString(PyObject *v, const char *key, PyObject *item)
2414 {
2415 PyObject *kv;
2416 int err;
2417 kv = PyString_FromString(key);
2418 if (kv == NULL)
2419 return -1;
2420 PyString_InternInPlace(&kv); /* XXX Should we really? */
2421 err = PyDict_SetItem(v, kv, item);
2422 Py_DECREF(kv);
2423 return err;
2424 }
2425
2426 int
2427 PyDict_DelItemString(PyObject *v, const char *key)
2428 {
2429 PyObject *kv;
2430 int err;
2431 kv = PyString_FromString(key);
2432 if (kv == NULL)
2433 return -1;
2434 err = PyDict_DelItem(v, kv);
2435 Py_DECREF(kv);
2436 return err;
2437 }
2438
2439 /* Dictionary iterator types */
2440
2441 typedef struct {
2442 PyObject_HEAD
2443 PyDictObject *di_dict; /* Set to NULL when iterator is exhausted */
2444 Py_ssize_t di_used;
2445 Py_ssize_t di_pos;
2446 PyObject* di_result; /* reusable result tuple for iteritems */
2447 Py_ssize_t len;
2448 } dictiterobject;
2449
2450 static PyObject *
2451 dictiter_new(PyDictObject *dict, PyTypeObject *itertype)
2452 {
2453 dictiterobject *di;
2454 di = PyObject_GC_New(dictiterobject, itertype);
2455 if (di == NULL)
2456 return NULL;
2457 Py_INCREF(dict);
2458 di->di_dict = dict;
2459 di->di_used = dict->ma_used;
2460 di->di_pos = 0;
2461 di->len = dict->ma_used;
2462 if (itertype == &PyDictIterItem_Type) {
2463 di->di_result = PyTuple_Pack(2, Py_None, Py_None);
2464 if (di->di_result == NULL) {
2465 Py_DECREF(di);
2466 return NULL;
2467 }
2468 }
2469 else
2470 di->di_result = NULL;
2471 _PyObject_GC_TRACK(di);
2472 return (PyObject *)di;
2473 }
2474
2475 static void
2476 dictiter_dealloc(dictiterobject *di)
2477 {
2478 Py_XDECREF(di->di_dict);
2479 Py_XDECREF(di->di_result);
2480 PyObject_GC_Del(di);
2481 }
2482
2483 static int
2484 dictiter_traverse(dictiterobject *di, visitproc visit, void *arg)
2485 {
2486 Py_VISIT(di->di_dict);
2487 Py_VISIT(di->di_result);
2488 return 0;
2489 }
2490
2491 static PyObject *
2492 dictiter_len(dictiterobject *di)
2493 {
2494 Py_ssize_t len = 0;
2495 if (di->di_dict != NULL && di->di_used == di->di_dict->ma_used)
2496 len = di->len;
2497 return PyInt_FromSize_t(len);
2498 }
2499
2500 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
2501
2502 static PyMethodDef dictiter_methods[] = {
2503 {"__length_hint__", (PyCFunction)dictiter_len, METH_NOARGS, length_hint_doc},
2504 {NULL, NULL} /* sentinel */
2505 };
2506
2507 static PyObject *dictiter_iternextkey(dictiterobject *di)
2508 {
2509 PyObject *key;
2510 register Py_ssize_t i, mask;
2511 register PyDictEntry *ep;
2512 PyDictObject *d = di->di_dict;
2513
2514 if (d == NULL)
2515 return NULL;
2516 assert (PyDict_Check(d));
2517
2518 if (di->di_used != d->ma_used) {
2519 PyErr_SetString(PyExc_RuntimeError,
2520 "dictionary changed size during iteration");
2521 di->di_used = -1; /* Make this state sticky */
2522 return NULL;
2523 }
2524
2525 i = di->di_pos;
2526 if (i < 0)
2527 goto fail;
2528 ep = d->ma_table;
2529 mask = d->ma_mask;
2530 while (i <= mask && ep[i].me_value == NULL)
2531 i++;
2532 di->di_pos = i+1;
2533 if (i > mask)
2534 goto fail;
2535 di->len--;
2536 key = ep[i].me_key;
2537 Py_INCREF(key);
2538 return key;
2539
2540 fail:
2541 Py_DECREF(d);
2542 di->di_dict = NULL;
2543 return NULL;
2544 }
2545
2546 PyTypeObject PyDictIterKey_Type = {
2547 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2548 "dictionary-keyiterator", /* tp_name */
2549 sizeof(dictiterobject), /* tp_basicsize */
2550 0, /* tp_itemsize */
2551 /* methods */
2552 (destructor)dictiter_dealloc, /* tp_dealloc */
2553 0, /* tp_print */
2554 0, /* tp_getattr */
2555 0, /* tp_setattr */
2556 0, /* tp_compare */
2557 0, /* tp_repr */
2558 0, /* tp_as_number */
2559 0, /* tp_as_sequence */
2560 0, /* tp_as_mapping */
2561 0, /* tp_hash */
2562 0, /* tp_call */
2563 0, /* tp_str */
2564 PyObject_GenericGetAttr, /* tp_getattro */
2565 0, /* tp_setattro */
2566 0, /* tp_as_buffer */
2567 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2568 0, /* tp_doc */
2569 (traverseproc)dictiter_traverse, /* tp_traverse */
2570 0, /* tp_clear */
2571 0, /* tp_richcompare */
2572 0, /* tp_weaklistoffset */
2573 PyObject_SelfIter, /* tp_iter */
2574 (iternextfunc)dictiter_iternextkey, /* tp_iternext */
2575 dictiter_methods, /* tp_methods */
2576 0,
2577 };
2578
2579 static PyObject *dictiter_iternextvalue(dictiterobject *di)
2580 {
2581 PyObject *value;
2582 register Py_ssize_t i, mask;
2583 register PyDictEntry *ep;
2584 PyDictObject *d = di->di_dict;
2585
2586 if (d == NULL)
2587 return NULL;
2588 assert (PyDict_Check(d));
2589
2590 if (di->di_used != d->ma_used) {
2591 PyErr_SetString(PyExc_RuntimeError,
2592 "dictionary changed size during iteration");
2593 di->di_used = -1; /* Make this state sticky */
2594 return NULL;
2595 }
2596
2597 i = di->di_pos;
2598 mask = d->ma_mask;
2599 if (i < 0 || i > mask)
2600 goto fail;
2601 ep = d->ma_table;
2602 while ((value=ep[i].me_value) == NULL) {
2603 i++;
2604 if (i > mask)
2605 goto fail;
2606 }
2607 di->di_pos = i+1;
2608 di->len--;
2609 Py_INCREF(value);
2610 return value;
2611
2612 fail:
2613 Py_DECREF(d);
2614 di->di_dict = NULL;
2615 return NULL;
2616 }
2617
2618 PyTypeObject PyDictIterValue_Type = {
2619 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2620 "dictionary-valueiterator", /* tp_name */
2621 sizeof(dictiterobject), /* tp_basicsize */
2622 0, /* tp_itemsize */
2623 /* methods */
2624 (destructor)dictiter_dealloc, /* tp_dealloc */
2625 0, /* tp_print */
2626 0, /* tp_getattr */
2627 0, /* tp_setattr */
2628 0, /* tp_compare */
2629 0, /* tp_repr */
2630 0, /* tp_as_number */
2631 0, /* tp_as_sequence */
2632 0, /* tp_as_mapping */
2633 0, /* tp_hash */
2634 0, /* tp_call */
2635 0, /* tp_str */
2636 PyObject_GenericGetAttr, /* tp_getattro */
2637 0, /* tp_setattro */
2638 0, /* tp_as_buffer */
2639 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2640 0, /* tp_doc */
2641 (traverseproc)dictiter_traverse, /* tp_traverse */
2642 0, /* tp_clear */
2643 0, /* tp_richcompare */
2644 0, /* tp_weaklistoffset */
2645 PyObject_SelfIter, /* tp_iter */
2646 (iternextfunc)dictiter_iternextvalue, /* tp_iternext */
2647 dictiter_methods, /* tp_methods */
2648 0,
2649 };
2650
2651 static PyObject *dictiter_iternextitem(dictiterobject *di)
2652 {
2653 PyObject *key, *value, *result = di->di_result;
2654 register Py_ssize_t i, mask;
2655 register PyDictEntry *ep;
2656 PyDictObject *d = di->di_dict;
2657
2658 if (d == NULL)
2659 return NULL;
2660 assert (PyDict_Check(d));
2661
2662 if (di->di_used != d->ma_used) {
2663 PyErr_SetString(PyExc_RuntimeError,
2664 "dictionary changed size during iteration");
2665 di->di_used = -1; /* Make this state sticky */
2666 return NULL;
2667 }
2668
2669 i = di->di_pos;
2670 if (i < 0)
2671 goto fail;
2672 ep = d->ma_table;
2673 mask = d->ma_mask;
2674 while (i <= mask && ep[i].me_value == NULL)
2675 i++;
2676 di->di_pos = i+1;
2677 if (i > mask)
2678 goto fail;
2679
2680 if (result->ob_refcnt == 1) {
2681 Py_INCREF(result);
2682 Py_DECREF(PyTuple_GET_ITEM(result, 0));
2683 Py_DECREF(PyTuple_GET_ITEM(result, 1));
2684 } else {
2685 result = PyTuple_New(2);
2686 if (result == NULL)
2687 return NULL;
2688 }
2689 di->len--;
2690 key = ep[i].me_key;
2691 value = ep[i].me_value;
2692 Py_INCREF(key);
2693 Py_INCREF(value);
2694 PyTuple_SET_ITEM(result, 0, key);
2695 PyTuple_SET_ITEM(result, 1, value);
2696 return result;
2697
2698 fail:
2699 Py_DECREF(d);
2700 di->di_dict = NULL;
2701 return NULL;
2702 }
2703
2704 PyTypeObject PyDictIterItem_Type = {
2705 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2706 "dictionary-itemiterator", /* tp_name */
2707 sizeof(dictiterobject), /* tp_basicsize */
2708 0, /* tp_itemsize */
2709 /* methods */
2710 (destructor)dictiter_dealloc, /* tp_dealloc */
2711 0, /* tp_print */
2712 0, /* tp_getattr */
2713 0, /* tp_setattr */
2714 0, /* tp_compare */
2715 0, /* tp_repr */
2716 0, /* tp_as_number */
2717 0, /* tp_as_sequence */
2718 0, /* tp_as_mapping */
2719 0, /* tp_hash */
2720 0, /* tp_call */
2721 0, /* tp_str */
2722 PyObject_GenericGetAttr, /* tp_getattro */
2723 0, /* tp_setattro */
2724 0, /* tp_as_buffer */
2725 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2726 0, /* tp_doc */
2727 (traverseproc)dictiter_traverse, /* tp_traverse */
2728 0, /* tp_clear */
2729 0, /* tp_richcompare */
2730 0, /* tp_weaklistoffset */
2731 PyObject_SelfIter, /* tp_iter */
2732 (iternextfunc)dictiter_iternextitem, /* tp_iternext */
2733 dictiter_methods, /* tp_methods */
2734 0,
2735 };
2736
2737 /***********************************************/
2738 /* View objects for keys(), items(), values(). */
2739 /***********************************************/
2740
2741 /* The instance lay-out is the same for all three; but the type differs. */
2742
2743 typedef struct {
2744 PyObject_HEAD
2745 PyDictObject *dv_dict;
2746 } dictviewobject;
2747
2748
2749 static void
2750 dictview_dealloc(dictviewobject *dv)
2751 {
2752 Py_XDECREF(dv->dv_dict);
2753 PyObject_GC_Del(dv);
2754 }
2755
2756 static int
2757 dictview_traverse(dictviewobject *dv, visitproc visit, void *arg)
2758 {
2759 Py_VISIT(dv->dv_dict);
2760 return 0;
2761 }
2762
2763 static Py_ssize_t
2764 dictview_len(dictviewobject *dv)
2765 {
2766 Py_ssize_t len = 0;
2767 if (dv->dv_dict != NULL)
2768 len = dv->dv_dict->ma_used;
2769 return len;
2770 }
2771
2772 static PyObject *
2773 dictview_new(PyObject *dict, PyTypeObject *type)
2774 {
2775 dictviewobject *dv;
2776 if (dict == NULL) {
2777 PyErr_BadInternalCall();
2778 return NULL;
2779 }
2780 if (!PyDict_Check(dict)) {
2781 /* XXX Get rid of this restriction later */
2782 PyErr_Format(PyExc_TypeError,
2783 "%s() requires a dict argument, not '%s'",
2784 type->tp_name, dict->ob_type->tp_name);
2785 return NULL;
2786 }
2787 dv = PyObject_GC_New(dictviewobject, type);
2788 if (dv == NULL)
2789 return NULL;
2790 Py_INCREF(dict);
2791 dv->dv_dict = (PyDictObject *)dict;
2792 _PyObject_GC_TRACK(dv);
2793 return (PyObject *)dv;
2794 }
2795
2796 /* TODO(guido): The views objects are not complete:
2797
2798 * support more set operations
2799 * support arbitrary mappings?
2800 - either these should be static or exported in dictobject.h
2801 - if public then they should probably be in builtins
2802 */
2803
2804 /* Return 1 if self is a subset of other, iterating over self;
2805 0 if not; -1 if an error occurred. */
2806 static int
2807 all_contained_in(PyObject *self, PyObject *other)
2808 {
2809 PyObject *iter = PyObject_GetIter(self);
2810 int ok = 1;
2811
2812 if (iter == NULL)
2813 return -1;
2814 for (;;) {
2815 PyObject *next = PyIter_Next(iter);
2816 if (next == NULL) {
2817 if (PyErr_Occurred())
2818 ok = -1;
2819 break;
2820 }
2821 ok = PySequence_Contains(other, next);
2822 Py_DECREF(next);
2823 if (ok <= 0)
2824 break;
2825 }
2826 Py_DECREF(iter);
2827 return ok;
2828 }
2829
2830 static PyObject *
2831 dictview_richcompare(PyObject *self, PyObject *other, int op)
2832 {
2833 Py_ssize_t len_self, len_other;
2834 int ok;
2835 PyObject *result;
2836
2837 assert(self != NULL);
2838 assert(PyDictViewSet_Check(self));
2839 assert(other != NULL);
2840
2841 if (!PyAnySet_Check(other) && !PyDictViewSet_Check(other)) {
2842 Py_INCREF(Py_NotImplemented);
2843 return Py_NotImplemented;
2844 }
2845
2846 len_self = PyObject_Size(self);
2847 if (len_self < 0)
2848 return NULL;
2849 len_other = PyObject_Size(other);
2850 if (len_other < 0)
2851 return NULL;
2852
2853 ok = 0;
2854 switch(op) {
2855
2856 case Py_NE:
2857 case Py_EQ:
2858 if (len_self == len_other)
2859 ok = all_contained_in(self, other);
2860 if (op == Py_NE && ok >= 0)
2861 ok = !ok;
2862 break;
2863
2864 case Py_LT:
2865 if (len_self < len_other)
2866 ok = all_contained_in(self, other);
2867 break;
2868
2869 case Py_LE:
2870 if (len_self <= len_other)
2871 ok = all_contained_in(self, other);
2872 break;
2873
2874 case Py_GT:
2875 if (len_self > len_other)
2876 ok = all_contained_in(other, self);
2877 break;
2878
2879 case Py_GE:
2880 if (len_self >= len_other)
2881 ok = all_contained_in(other, self);
2882 break;
2883
2884 }
2885 if (ok < 0)
2886 return NULL;
2887 result = ok ? Py_True : Py_False;
2888 Py_INCREF(result);
2889 return result;
2890 }
2891
2892 static PyObject *
2893 dictview_repr(dictviewobject *dv)
2894 {
2895 PyObject *seq;
2896 PyObject *seq_str;
2897 PyObject *result;
2898
2899 seq = PySequence_List((PyObject *)dv);
2900 if (seq == NULL)
2901 return NULL;
2902
2903 seq_str = PyObject_Repr(seq);
2904 result = PyString_FromFormat("%s(%s)", Py_TYPE(dv)->tp_name,
2905 PyString_AS_STRING(seq_str));
2906 Py_DECREF(seq_str);
2907 Py_DECREF(seq);
2908 return result;
2909 }
2910
2911 /*** dict_keys ***/
2912
2913 static PyObject *
2914 dictkeys_iter(dictviewobject *dv)
2915 {
2916 if (dv->dv_dict == NULL) {
2917 Py_RETURN_NONE;
2918 }
2919 return dictiter_new(dv->dv_dict, &PyDictIterKey_Type);
2920 }
2921
2922 static int
2923 dictkeys_contains(dictviewobject *dv, PyObject *obj)
2924 {
2925 if (dv->dv_dict == NULL)
2926 return 0;
2927 return PyDict_Contains((PyObject *)dv->dv_dict, obj);
2928 }
2929
2930 static PySequenceMethods dictkeys_as_sequence = {
2931 (lenfunc)dictview_len, /* sq_length */
2932 0, /* sq_concat */
2933 0, /* sq_repeat */
2934 0, /* sq_item */
2935 0, /* sq_slice */
2936 0, /* sq_ass_item */
2937 0, /* sq_ass_slice */
2938 (objobjproc)dictkeys_contains, /* sq_contains */
2939 };
2940
2941 static PyObject*
2942 dictviews_sub(PyObject* self, PyObject *other)
2943 {
2944 PyObject *result = PySet_New(self);
2945 PyObject *tmp;
2946 if (result == NULL)
2947 return NULL;
2948
2949 tmp = PyObject_CallMethod(result, "difference_update", "O", other);
2950 if (tmp == NULL) {
2951 Py_DECREF(result);
2952 return NULL;
2953 }
2954
2955 Py_DECREF(tmp);
2956 return result;
2957 }
2958
2959 static PyObject*
2960 dictviews_and(PyObject* self, PyObject *other)
2961 {
2962 PyObject *result = PySet_New(self);
2963 PyObject *tmp;
2964 if (result == NULL)
2965 return NULL;
2966
2967 tmp = PyObject_CallMethod(result, "intersection_update", "O", other);
2968 if (tmp == NULL) {
2969 Py_DECREF(result);
2970 return NULL;
2971 }
2972
2973 Py_DECREF(tmp);
2974 return result;
2975 }
2976
2977 static PyObject*
2978 dictviews_or(PyObject* self, PyObject *other)
2979 {
2980 PyObject *result = PySet_New(self);
2981 PyObject *tmp;
2982 if (result == NULL)
2983 return NULL;
2984
2985 tmp = PyObject_CallMethod(result, "update", "O", other);
2986 if (tmp == NULL) {
2987 Py_DECREF(result);
2988 return NULL;
2989 }
2990
2991 Py_DECREF(tmp);
2992 return result;
2993 }
2994
2995 static PyObject*
2996 dictviews_xor(PyObject* self, PyObject *other)
2997 {
2998 PyObject *result = PySet_New(self);
2999 PyObject *tmp;
3000 if (result == NULL)
3001 return NULL;
3002
3003 tmp = PyObject_CallMethod(result, "symmetric_difference_update", "O",
3004 other);
3005 if (tmp == NULL) {
3006 Py_DECREF(result);
3007 return NULL;
3008 }
3009
3010 Py_DECREF(tmp);
3011 return result;
3012 }
3013
3014 static PyNumberMethods dictviews_as_number = {
3015 0, /*nb_add*/
3016 (binaryfunc)dictviews_sub, /*nb_subtract*/
3017 0, /*nb_multiply*/
3018 0, /*nb_divide*/
3019 0, /*nb_remainder*/
3020 0, /*nb_divmod*/
3021 0, /*nb_power*/
3022 0, /*nb_negative*/
3023 0, /*nb_positive*/
3024 0, /*nb_absolute*/
3025 0, /*nb_nonzero*/
3026 0, /*nb_invert*/
3027 0, /*nb_lshift*/
3028 0, /*nb_rshift*/
3029 (binaryfunc)dictviews_and, /*nb_and*/
3030 (binaryfunc)dictviews_xor, /*nb_xor*/
3031 (binaryfunc)dictviews_or, /*nb_or*/
3032 };
3033
3034 static PyMethodDef dictkeys_methods[] = {
3035 {NULL, NULL} /* sentinel */
3036 };
3037
3038 PyTypeObject PyDictKeys_Type = {
3039 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3040 "dict_keys", /* tp_name */
3041 sizeof(dictviewobject), /* tp_basicsize */
3042 0, /* tp_itemsize */
3043 /* methods */
3044 (destructor)dictview_dealloc, /* tp_dealloc */
3045 0, /* tp_print */
3046 0, /* tp_getattr */
3047 0, /* tp_setattr */
3048 0, /* tp_reserved */
3049 (reprfunc)dictview_repr, /* tp_repr */
3050 &dictviews_as_number, /* tp_as_number */
3051 &dictkeys_as_sequence, /* tp_as_sequence */
3052 0, /* tp_as_mapping */
3053 0, /* tp_hash */
3054 0, /* tp_call */
3055 0, /* tp_str */
3056 PyObject_GenericGetAttr, /* tp_getattro */
3057 0, /* tp_setattro */
3058 0, /* tp_as_buffer */
3059 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
3060 Py_TPFLAGS_CHECKTYPES, /* tp_flags */
3061 0, /* tp_doc */
3062 (traverseproc)dictview_traverse, /* tp_traverse */
3063 0, /* tp_clear */
3064 dictview_richcompare, /* tp_richcompare */
3065 0, /* tp_weaklistoffset */
3066 (getiterfunc)dictkeys_iter, /* tp_iter */
3067 0, /* tp_iternext */
3068 dictkeys_methods, /* tp_methods */
3069 0,
3070 };
3071
3072 static PyObject *
3073 dictkeys_new(PyObject *dict)
3074 {
3075 return dictview_new(dict, &PyDictKeys_Type);
3076 }
3077
3078 /*** dict_items ***/
3079
3080 static PyObject *
3081 dictitems_iter(dictviewobject *dv)
3082 {
3083 if (dv->dv_dict == NULL) {
3084 Py_RETURN_NONE;
3085 }
3086 return dictiter_new(dv->dv_dict, &PyDictIterItem_Type);
3087 }
3088
3089 static int
3090 dictitems_contains(dictviewobject *dv, PyObject *obj)
3091 {
3092 PyObject *key, *value, *found;
3093 if (dv->dv_dict == NULL)
3094 return 0;
3095 if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 2)
3096 return 0;
3097 key = PyTuple_GET_ITEM(obj, 0);
3098 value = PyTuple_GET_ITEM(obj, 1);
3099 found = PyDict_GetItem((PyObject *)dv->dv_dict, key);
3100 if (found == NULL) {
3101 if (PyErr_Occurred())
3102 return -1;
3103 return 0;
3104 }
3105 return PyObject_RichCompareBool(value, found, Py_EQ);
3106 }
3107
3108 static PySequenceMethods dictitems_as_sequence = {
3109 (lenfunc)dictview_len, /* sq_length */
3110 0, /* sq_concat */
3111 0, /* sq_repeat */
3112 0, /* sq_item */
3113 0, /* sq_slice */
3114 0, /* sq_ass_item */
3115 0, /* sq_ass_slice */
3116 (objobjproc)dictitems_contains, /* sq_contains */
3117 };
3118
3119 static PyMethodDef dictitems_methods[] = {
3120 {NULL, NULL} /* sentinel */
3121 };
3122
3123 PyTypeObject PyDictItems_Type = {
3124 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3125 "dict_items", /* tp_name */
3126 sizeof(dictviewobject), /* tp_basicsize */
3127 0, /* tp_itemsize */
3128 /* methods */
3129 (destructor)dictview_dealloc, /* tp_dealloc */
3130 0, /* tp_print */
3131 0, /* tp_getattr */
3132 0, /* tp_setattr */
3133 0, /* tp_reserved */
3134 (reprfunc)dictview_repr, /* tp_repr */
3135 &dictviews_as_number, /* tp_as_number */
3136 &dictitems_as_sequence, /* tp_as_sequence */
3137 0, /* tp_as_mapping */
3138 0, /* tp_hash */
3139 0, /* tp_call */
3140 0, /* tp_str */
3141 PyObject_GenericGetAttr, /* tp_getattro */
3142 0, /* tp_setattro */
3143 0, /* tp_as_buffer */
3144 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
3145 Py_TPFLAGS_CHECKTYPES, /* tp_flags */
3146 0, /* tp_doc */
3147 (traverseproc)dictview_traverse, /* tp_traverse */
3148 0, /* tp_clear */
3149 dictview_richcompare, /* tp_richcompare */
3150 0, /* tp_weaklistoffset */
3151 (getiterfunc)dictitems_iter, /* tp_iter */
3152 0, /* tp_iternext */
3153 dictitems_methods, /* tp_methods */
3154 0,
3155 };
3156
3157 static PyObject *
3158 dictitems_new(PyObject *dict)
3159 {
3160 return dictview_new(dict, &PyDictItems_Type);
3161 }
3162
3163 /*** dict_values ***/
3164
3165 static PyObject *
3166 dictvalues_iter(dictviewobject *dv)
3167 {
3168 if (dv->dv_dict == NULL) {
3169 Py_RETURN_NONE;
3170 }
3171 return dictiter_new(dv->dv_dict, &PyDictIterValue_Type);
3172 }
3173
3174 static PySequenceMethods dictvalues_as_sequence = {
3175 (lenfunc)dictview_len, /* sq_length */
3176 0, /* sq_concat */
3177 0, /* sq_repeat */
3178 0, /* sq_item */
3179 0, /* sq_slice */
3180 0, /* sq_ass_item */
3181 0, /* sq_ass_slice */
3182 (objobjproc)0, /* sq_contains */
3183 };
3184
3185 static PyMethodDef dictvalues_methods[] = {
3186 {NULL, NULL} /* sentinel */
3187 };
3188
3189 PyTypeObject PyDictValues_Type = {
3190 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3191 "dict_values", /* tp_name */
3192 sizeof(dictviewobject), /* tp_basicsize */
3193 0, /* tp_itemsize */
3194 /* methods */
3195 (destructor)dictview_dealloc, /* tp_dealloc */
3196 0, /* tp_print */
3197 0, /* tp_getattr */
3198 0, /* tp_setattr */
3199 0, /* tp_reserved */
3200 (reprfunc)dictview_repr, /* tp_repr */
3201 0, /* tp_as_number */
3202 &dictvalues_as_sequence, /* tp_as_sequence */
3203 0, /* tp_as_mapping */
3204 0, /* tp_hash */
3205 0, /* tp_call */
3206 0, /* tp_str */
3207 PyObject_GenericGetAttr, /* tp_getattro */
3208 0, /* tp_setattro */
3209 0, /* tp_as_buffer */
3210 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3211 0, /* tp_doc */
3212 (traverseproc)dictview_traverse, /* tp_traverse */
3213 0, /* tp_clear */
3214 0, /* tp_richcompare */
3215 0, /* tp_weaklistoffset */
3216 (getiterfunc)dictvalues_iter, /* tp_iter */
3217 0, /* tp_iternext */
3218 dictvalues_methods, /* tp_methods */
3219 0,
3220 };
3221
3222 static PyObject *
3223 dictvalues_new(PyObject *dict)
3224 {
3225 return dictview_new(dict, &PyDictValues_Type);
3226 }