Debian Codegraph @

src/frozendict/c_src/3_6/cpython_src/Objects/dictobject.c

raw
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 /* PyDictKeysObject
10
11 This implements the dictionary's hashtable.
12
13 As of Python 3.6, this is compact and ordered. Basic idea is described here:
14 * https://mail.python.org/pipermail/python-dev/2012-December/123028.html
15 * https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html
16
17 layout:
18
19 +---------------+
20 | dk_refcnt |
21 | dk_size |
22 | dk_lookup |
23 | dk_usable |
24 | dk_nentries |
25 +---------------+
26 | dk_indices |
27 | |
28 +---------------+
29 | dk_entries |
30 | |
31 +---------------+
32
33 dk_indices is actual hashtable. It holds index in entries, or DKIX_EMPTY(-1)
34 or DKIX_DUMMY(-2).
35 Size of indices is dk_size. Type of each index in indices is vary on dk_size:
36
37 * int8 for dk_size <= 128
38 * int16 for 256 <= dk_size <= 2**15
39 * int32 for 2**16 <= dk_size <= 2**31
40 * int64 for 2**32 <= dk_size
41
42 dk_entries is array of PyDictKeyEntry. Its size is USABLE_FRACTION(dk_size).
43 DK_ENTRIES(dk) can be used to get pointer to entries.
44
45 NOTE: Since negative value is used for DKIX_EMPTY and DKIX_DUMMY, type of
46 dk_indices entry is signed integer and int16 is used for table which
47 dk_size == 256.
48 */
49
50
51 /*
52 The DictObject can be in one of two forms.
53
54 Either:
55 A combined table:
56 ma_values == NULL, dk_refcnt == 1.
57 Values are stored in the me_value field of the PyDictKeysObject.
58 Or:
59 A split table:
60 ma_values != NULL, dk_refcnt >= 1
61 Values are stored in the ma_values array.
62 Only string (unicode) keys are allowed.
63 All dicts sharing same key must have same insertion order.
64
65 There are four kinds of slots in the table (slot is index, and
66 DK_ENTRIES(keys)[index] if index >= 0):
67
68 1. Unused. index == DKIX_EMPTY
69 Does not hold an active (key, value) pair now and never did. Unused can
70 transition to Active upon key insertion. This is each slot's initial state.
71
72 2. Active. index >= 0, me_key != NULL and me_value != NULL
73 Holds an active (key, value) pair. Active can transition to Dummy or
74 Pending upon key deletion (for combined and split tables respectively).
75 This is the only case in which me_value != NULL.
76
77 3. Dummy. index == DKIX_DUMMY (combined only)
78 Previously held an active (key, value) pair, but that was deleted and an
79 active pair has not yet overwritten the slot. Dummy can transition to
80 Active upon key insertion. Dummy slots cannot be made Unused again
81 else the probe sequence in case of collision would have no way to know
82 they were once active.
83
84 4. Pending. index >= 0, key != NULL, and value == NULL (split only)
85 Not yet inserted in split-table.
86 */
87
88 /*
89 Preserving insertion order
90
91 It's simple for combined table. Since dk_entries is mostly append only, we can
92 get insertion order by just iterating dk_entries.
93
94 One exception is .popitem(). It removes last item in dk_entries and decrement
95 dk_nentries to achieve amortized O(1). Since there are DKIX_DUMMY remains in
96 dk_indices, we can't increment dk_usable even though dk_nentries is
97 decremented.
98
99 In split table, inserting into pending entry is allowed only for dk_entries[ix]
100 where ix == mp->ma_used. Inserting into other index and deleting item cause
101 converting the dict to the combined table.
102 */
103
104 /* PyDict_MINSIZE is the starting size for any new dict.
105 * 8 allows dicts with no more than 5 active entries; experiments suggested
106 * this suffices for the majority of dicts (consisting mostly of usually-small
107 * dicts created to pass keyword arguments).
108 * Making this 8, rather than 4 reduces the number of resizes for most
109 * dictionaries, without any significant extra memory use.
110 */
111 #define PyDict_MINSIZE 8
112
113 #include "Python.h"
114 #include "dict-common.h"
115 #include "stringlib/eq.h" // unicode_eq()
116
117 /*[clinic input]
118 class dict "PyDictObject *" "&PyDict_Type"
119 [clinic start generated code]*/
120 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=f157a5a0ce9589d6]*/
121
122
123 /*
124 To ensure the lookup algorithm terminates, there must be at least one Unused
125 slot (NULL key) in the table.
126 To avoid slowing down lookups on a near-full table, we resize the table when
127 it's USABLE_FRACTION (currently two-thirds) full.
128 */
129
130 #define PERTURB_SHIFT 5
131
132 /*
133 Major subtleties ahead: Most hash schemes depend on having a "good" hash
134 function, in the sense of simulating randomness. Python doesn't: its most
135 important hash functions (for ints) are very regular in common
136 cases:
137
138 >>>[hash(i) for i in range(4)]
139 [0, 1, 2, 3]
140
141 This isn't necessarily bad! To the contrary, in a table of size 2**i, taking
142 the low-order i bits as the initial table index is extremely fast, and there
143 are no collisions at all for dicts indexed by a contiguous range of ints. So
144 this gives better-than-random behavior in common cases, and that's very
145 desirable.
146
147 OTOH, when collisions occur, the tendency to fill contiguous slices of the
148 hash table makes a good collision resolution strategy crucial. Taking only
149 the last i bits of the hash code is also vulnerable: for example, consider
150 the list [i << 16 for i in range(20000)] as a set of keys. Since ints are
151 their own hash codes, and this fits in a dict of size 2**15, the last 15 bits
152 of every hash code are all 0: they *all* map to the same table index.
153
154 But catering to unusual cases should not slow the usual ones, so we just take
155 the last i bits anyway. It's up to collision resolution to do the rest. If
156 we *usually* find the key we're looking for on the first try (and, it turns
157 out, we usually do -- the table load factor is kept under 2/3, so the odds
158 are solidly in our favor), then it makes best sense to keep the initial index
159 computation dirt cheap.
160
161 The first half of collision resolution is to visit table indices via this
162 recurrence:
163
164 j = ((5*j) + 1) mod 2**i
165
166 For any initial j in range(2**i), repeating that 2**i times generates each
167 int in range(2**i) exactly once (see any text on random-number generation for
168 proof). By itself, this doesn't help much: like linear probing (setting
169 j += 1, or j -= 1, on each loop trip), it scans the table entries in a fixed
170 order. This would be bad, except that's not the only thing we do, and it's
171 actually *good* in the common cases where hash keys are consecutive. In an
172 example that's really too small to make this entirely clear, for a table of
173 size 2**3 the order of indices is:
174
175 0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating]
176
177 If two things come in at index 5, the first place we look after is index 2,
178 not 6, so if another comes in at index 6 the collision at 5 didn't hurt it.
179 Linear probing is deadly in this case because there the fixed probe order
180 is the *same* as the order consecutive keys are likely to arrive. But it's
181 extremely unlikely hash codes will follow a 5*j+1 recurrence by accident,
182 and certain that consecutive hash codes do not.
183
184 The other half of the strategy is to get the other bits of the hash code
185 into play. This is done by initializing a (unsigned) vrbl "perturb" to the
186 full hash code, and changing the recurrence to:
187
188 perturb >>= PERTURB_SHIFT;
189 j = (5*j) + 1 + perturb;
190 use j % 2**i as the next table index;
191
192 Now the probe sequence depends (eventually) on every bit in the hash code,
193 and the pseudo-scrambling property of recurring on 5*j+1 is more valuable,
194 because it quickly magnifies small differences in the bits that didn't affect
195 the initial index. Note that because perturb is unsigned, if the recurrence
196 is executed often enough perturb eventually becomes and remains 0. At that
197 point (very rarely reached) the recurrence is on (just) 5*j+1 again, and
198 that's certain to find an empty slot eventually (since it generates every int
199 in range(2**i), and we make sure there's always at least one empty slot).
200
201 Selecting a good value for PERTURB_SHIFT is a balancing act. You want it
202 small so that the high bits of the hash code continue to affect the probe
203 sequence across iterations; but you want it large so that in really bad cases
204 the high-order hash bits have an effect on early iterations. 5 was "the
205 best" in minimizing total collisions across experiments Tim Peters ran (on
206 both normal and pathological cases), but 4 and 6 weren't significantly worse.
207
208 Historical: Reimer Behrends contributed the idea of using a polynomial-based
209 approach, using repeated multiplication by x in GF(2**n) where an irreducible
210 polynomial for each table size was chosen such that x was a primitive root.
211 Christian Tismer later extended that to use division by x instead, as an
212 efficient way to get the high bits of the hash code into play. This scheme
213 also gave excellent collision statistics, but was more expensive: two
214 if-tests were required inside the loop; computing "the next" index took about
215 the same number of operations but without as much potential parallelism
216 (e.g., computing 5*j can go on at the same time as computing 1+perturb in the
217 above, and then shifting perturb can be done while the table index is being
218 masked); and the PyDictObject struct required a member to hold the table's
219 polynomial. In Tim's experiments the current scheme ran faster, produced
220 equally good collision statistics, needed less code & used less memory.
221
222 */
223
224 /* forward declarations */
225 static Py_ssize_t lookdict(PyDictObject *mp, PyObject *key,
226 Py_hash_t hash, PyObject ***value_addr,
227 Py_ssize_t *hashpos);
228 static Py_ssize_t
229 lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
230 Py_hash_t hash, PyObject ***value_addr,
231 Py_ssize_t *hashpos);
232
233 /*Global counter used to set ma_version_tag field of dictionary.
234 * It is incremented each time that a dictionary is created and each
235 * time that a dictionary is modified. */
236 static uint64_t pydict_global_version = 0;
237
238 #define DICT_NEXT_VERSION() (++pydict_global_version)
239
240 /* Dictionary reuse scheme to save calls to malloc and free */
241 #ifndef PyDict_MAXFREELIST
242 #define PyDict_MAXFREELIST 80
243 #endif
244
245 #if PyDict_MAXFREELIST > 0
246 static PyDictObject *free_list[PyDict_MAXFREELIST];
247 static int numfree = 0;
248 static PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST];
249 static int numfreekeys = 0;
250 #endif
251
252 #include "clinic/dictobject.c.h"
253
254 #define DK_SIZE(dk) ((dk)->dk_size)
255 #if SIZEOF_VOID_P > 4
256 #define DK_IXSIZE(dk) \
257 (DK_SIZE(dk) <= 0xff ? \
258 1 : DK_SIZE(dk) <= 0xffff ? \
259 2 : DK_SIZE(dk) <= 0xffffffff ? \
260 4 : sizeof(int64_t))
261 #else
262 #define DK_IXSIZE(dk) \
263 (DK_SIZE(dk) <= 0xff ? \
264 1 : DK_SIZE(dk) <= 0xffff ? \
265 2 : sizeof(int32_t))
266 #endif
267 #define DK_ENTRIES(dk) \
268 ((PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[DK_SIZE(dk) * DK_IXSIZE(dk)]))
269
270 #define DK_MASK(dk) (((dk)->dk_size)-1)
271 #define IS_POWER_OF_2(x) (((x) & (x-1)) == 0)
272
273 static void free_keys_object(PyDictKeysObject *keys);
274
275 static inline void
276 dictkeys_incref(PyDictKeysObject *dk)
277 {
278 _Py_INC_REFTOTAL;
279 dk->dk_refcnt++;
280 }
281
282 static inline void
283 dictkeys_decref(PyDictKeysObject *dk)
284 {
285 assert(dk->dk_refcnt > 0);
286 _Py_DEC_REFTOTAL;
287 if (--dk->dk_refcnt == 0) {
288 free_keys_object(dk);
289 }
290 }
291
292 /* lookup indices. returns DKIX_EMPTY, DKIX_DUMMY, or ix >=0 */
293 static inline Py_ssize_t
294 dictkeys_get_index(const PyDictKeysObject *keys, Py_ssize_t i)
295 {
296 Py_ssize_t s = DK_SIZE(keys);
297 Py_ssize_t ix;
298
299 if (s <= 0xff) {
300 const int8_t *indices = (const int8_t*)(keys->dk_indices);
301 ix = indices[i];
302 }
303 else if (s <= 0xffff) {
304 const int16_t *indices = (const int16_t*)(keys->dk_indices);
305 ix = indices[i];
306 }
307 #if SIZEOF_VOID_P > 4
308 else if (s > 0xffffffff) {
309 const int64_t *indices = (const int64_t*)(keys->dk_indices);
310 ix = indices[i];
311 }
312 #endif
313 else {
314 const int32_t *indices = (const int32_t*)(keys->dk_indices);
315 ix = indices[i];
316 }
317 assert(ix >= DKIX_DUMMY);
318 return ix;
319 }
320
321 /* write to indices. */
322 static inline void
323 dictkeys_set_index(PyDictKeysObject *keys, Py_ssize_t i, Py_ssize_t ix)
324 {
325 Py_ssize_t s = DK_SIZE(keys);
326
327 assert(ix >= DKIX_DUMMY);
328
329 if (s <= 0xff) {
330 int8_t *indices = (int8_t*)(keys->dk_indices);
331 assert(ix <= 0x7f);
332 indices[i] = (char)ix;
333 }
334 else if (s <= 0xffff) {
335 int16_t *indices = (int16_t*)(keys->dk_indices);
336 assert(ix <= 0x7fff);
337 indices[i] = (int16_t)ix;
338 }
339 #if SIZEOF_VOID_P > 4
340 else if (s > 0xffffffff) {
341 int64_t *indices = (int64_t*)(keys->dk_indices);
342 indices[i] = ix;
343 }
344 #endif
345 else {
346 int32_t *indices = (int32_t*)(keys->dk_indices);
347 assert(ix <= 0x7fffffff);
348 indices[i] = (int32_t)ix;
349 }
350 }
351
352
353 /* USABLE_FRACTION is the maximum dictionary load.
354 * Increasing this ratio makes dictionaries more dense resulting in more
355 * collisions. Decreasing it improves sparseness at the expense of spreading
356 * indices over more cache lines and at the cost of total memory consumed.
357 *
358 * USABLE_FRACTION must obey the following:
359 * (0 < USABLE_FRACTION(n) < n) for all n >= 2
360 *
361 * USABLE_FRACTION should be quick to calculate.
362 * Fractions around 1/2 to 2/3 seem to work well in practice.
363 */
364 #define USABLE_FRACTION(n) (((n) << 1)/3)
365
366 /* Find the smallest dk_size >= minsize. */
367 static inline Py_ssize_t
368 calculate_keysize(Py_ssize_t minsize)
369 {
370 #if SIZEOF_LONG == SIZEOF_SIZE_T
371 minsize = (minsize | PyDict_MINSIZE) - 1;
372 return 1LL << _Py_bit_length(minsize | (PyDict_MINSIZE-1));
373 #elif defined(_MSC_VER)
374 // On 64bit Windows, sizeof(long) == 4.
375 minsize = (minsize | PyDict_MINSIZE) - 1;
376 unsigned long msb;
377 _BitScanReverse64(&msb, (uint64_t)minsize);
378 return 1LL << (msb + 1);
379 #else
380 Py_ssize_t size;
381 for (size = PyDict_MINSIZE;
382 size < minsize && size > 0;
383 size <<= 1)
384 ;
385 return size;
386 #endif
387 }
388
389 /* estimate_keysize is reverse function of USABLE_FRACTION.
390 *
391 * This can be used to reserve enough size to insert n entries without
392 * resizing.
393 */
394 static inline Py_ssize_t
395 estimate_keysize(Py_ssize_t n)
396 {
397 return calculate_keysize((n*3 + 1) / 2);
398 }
399
400
401 /* GROWTH_RATE. Growth rate upon hitting maximum load.
402 * Currently set to used*3.
403 * This means that dicts double in size when growing without deletions,
404 * but have more head room when the number of deletions is on a par with the
405 * number of insertions. See also bpo-17563 and bpo-33205.
406 *
407 * GROWTH_RATE was set to used*4 up to version 3.2.
408 * GROWTH_RATE was set to used*2 in version 3.3.0
409 * GROWTH_RATE was set to used*2 + capacity/2 in 3.4.0-3.6.0.
410 */
411 #define GROWTH_RATE(d) ((d)->ma_used*3)
412
413 /* This immutable, empty PyDictKeysObject is used for PyDict_Clear()
414 * (which cannot fail and thus can do no allocation).
415 */
416 static PyDictKeysObject empty_keys_struct = {
417 1, /* dk_refcnt */
418 1, /* dk_size */
419 lookdict_unicode_nodummy, /* dk_lookup */
420 0, /* dk_usable (immutable) */
421 0, /* dk_nentries */
422 {DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY,
423 DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY}, /* dk_indices */
424 };
425
426 static PyObject *empty_values[1] = { NULL };
427
428 #define Py_EMPTY_KEYS &empty_keys_struct
429
430 /* Uncomment to check the dict content in _PyDict_CheckConsistency() */
431 /* #define DEBUG_PYDICT */
432
433 #ifdef DEBUG_PYDICT
434 # define ASSERT_CONSISTENT(op) assert(_PyDict_CheckConsistency((PyObject *)(op), 1))
435 #else
436 # define ASSERT_CONSISTENT(op) assert(_PyDict_CheckConsistency((PyObject *)(op), 0))
437 #endif
438
439
440 #ifndef NDEBUG
441 static int
442 _PyDict_CheckConsistency(PyObject *op, int check_content)
443 {
444 assert(op != NULL);
445 assert(PyAnyDict_Check(op));
446 PyDictObject *mp = (PyDictObject *)op;
447
448 PyDictKeysObject *keys = mp->ma_keys;
449 int splitted = _PyDict_HasSplitTable(mp);
450 Py_ssize_t usable = USABLE_FRACTION(keys->dk_size);
451
452 assert(0 <= mp->ma_used && mp->ma_used <= usable);
453 assert(IS_POWER_OF_2(keys->dk_size));
454 assert(0 <= keys->dk_usable
455 && keys->dk_usable <= usable);
456 assert(0 <= keys->dk_nentries
457 && keys->dk_nentries <= usable);
458 assert(keys->dk_usable + keys->dk_nentries <= usable);
459
460 if (!splitted) {
461 /* combined table */
462 assert(keys->dk_refcnt == 1);
463 }
464
465 if (check_content) {
466 PyDictKeyEntry *entries = DK_ENTRIES(keys);
467 Py_ssize_t i;
468
469 for (i=0; i < keys->dk_size; i++) {
470 Py_ssize_t ix = dictkeys_get_index(keys, i);
471 assert(DKIX_DUMMY <= ix && ix <= usable);
472 }
473
474 for (i=0; i < usable; i++) {
475 PyDictKeyEntry *entry = &entries[i];
476 PyObject *key = entry->me_key;
477
478 if (key != NULL) {
479 if (PyUnicode_CheckExact(key)) {
480 Py_hash_t hash = ((PyASCIIObject *)key)->hash;
481 assert(hash != -1);
482 assert(entry->me_hash == hash);
483 }
484 else {
485 /* test_dict fails if PyObject_Hash() is called again */
486 assert(entry->me_hash != -1);
487 }
488 if (!splitted) {
489 assert(entry->me_value != NULL);
490 }
491 }
492
493 if (splitted) {
494 assert(entry->me_value == NULL);
495 }
496 }
497
498 if (splitted) {
499 /* splitted table */
500 for (i=0; i < mp->ma_used; i++) {
501 assert(mp->ma_values[i] != NULL);
502 }
503 }
504 }
505 return 1;
506 }
507 #endif
508
509
510 static PyDictKeysObject*
511 new_keys_object(Py_ssize_t size)
512 {
513 PyDictKeysObject *dk;
514 Py_ssize_t es, usable;
515
516 assert(size >= PyDict_MINSIZE);
517 assert(IS_POWER_OF_2(size));
518
519 usable = USABLE_FRACTION(size);
520 if (size <= 0xff) {
521 es = 1;
522 }
523 else if (size <= 0xffff) {
524 es = 2;
525 }
526 #if SIZEOF_VOID_P > 4
527 else if (size <= 0xffffffff) {
528 es = 4;
529 }
530 #endif
531 else {
532 es = sizeof(Py_ssize_t);
533 }
534
535 #if PyDict_MAXFREELIST > 0
536 if (size == PyDict_MINSIZE && numfreekeys > 0) {
537 dk = keys_free_list[--numfreekeys];
538 }
539 else
540 #endif
541 {
542 dk = PyObject_Malloc(sizeof(PyDictKeysObject)
543 + es * size
544 + sizeof(PyDictKeyEntry) * usable);
545 if (dk == NULL) {
546 PyErr_NoMemory();
547 return NULL;
548 }
549 }
550 _Py_INC_REFTOTAL;
551 dk->dk_refcnt = 1;
552 dk->dk_size = size;
553 dk->dk_usable = usable;
554 dk->dk_lookup = lookdict_unicode_nodummy;
555 dk->dk_nentries = 0;
556 memset(&dk->dk_indices[0], 0xff, es * size);
557 memset(DK_ENTRIES(dk), 0, sizeof(PyDictKeyEntry) * usable);
558 return dk;
559 }
560
561 static void
562 free_keys_object(PyDictKeysObject *keys)
563 {
564 PyDictKeyEntry *entries = DK_ENTRIES(keys);
565 Py_ssize_t i, n;
566 for (i = 0, n = keys->dk_nentries; i < n; i++) {
567 Py_XDECREF(entries[i].me_key);
568 Py_XDECREF(entries[i].me_value);
569 }
570 #if PyDict_MAXFREELIST > 0
571 if (keys->dk_size == PyDict_MINSIZE && numfreekeys < PyDict_MAXFREELIST) {
572 keys_free_list[numfreekeys++] = keys;
573 return;
574 }
575 #endif
576 PyObject_Free(keys);
577 }
578
579 #define new_values(size) PyMem_NEW(PyObject *, size)
580 #define free_values(values) PyMem_Free(values)
581
582 static Py_ssize_t
583 _d_PyDict_KeysSize(PyDictKeysObject *keys)
584 {
585 return (sizeof(PyDictKeysObject)
586 + DK_IXSIZE(keys) * DK_SIZE(keys)
587 + USABLE_FRACTION(DK_SIZE(keys)) * sizeof(PyDictKeyEntry));
588 }
589
590 static PyDictKeysObject *
591 clone_combined_dict_keys(PyDictObject *orig)
592 {
593 assert(PyAnyDict_Check(orig));
594
595 assert(
596 Py_TYPE(orig)->tp_iter == PyDict_Type.tp_iter ||
597 Py_TYPE(orig)->tp_iter == (getiterfunc)frozendict_iter
598 );
599
600 assert(orig->ma_values == NULL);
601 assert(orig->ma_keys->dk_refcnt == 1);
602
603 Py_ssize_t keys_size = _d_PyDict_KeysSize(orig->ma_keys);
604 PyDictKeysObject *keys = PyObject_Malloc(keys_size);
605 if (keys == NULL) {
606 PyErr_NoMemory();
607 return NULL;
608 }
609
610 memcpy(keys, orig->ma_keys, keys_size);
611
612 /* After copying key/value pairs, we need to incref all
613 keys and values and they are about to be co-owned by a
614 new dict object. */
615 PyDictKeyEntry *ep0 = DK_ENTRIES(keys);
616 Py_ssize_t n = keys->dk_nentries;
617 for (Py_ssize_t i = 0; i < n; i++) {
618 PyDictKeyEntry *entry = &ep0[i];
619 PyObject *value = entry->me_value;
620 Py_INCREF(value);
621 Py_INCREF(entry->me_key);
622 }
623
624 /* Since we copied the keys table we now have an extra reference
625 in the system. Manually call _Py_INC_REFTOTAL to signal that
626 we have it now; calling dictkeys_incref would be an error as
627 keys->dk_refcnt is already set to 1 (after memcpy). */
628 _Py_INC_REFTOTAL;
629
630 return keys;
631 }
632
633 /*
634 The basic lookup function used by all operations.
635 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
636 Open addressing is preferred over chaining since the link overhead for
637 chaining would be substantial (100% with typical malloc overhead).
638
639 The initial probe index is computed as hash mod the table size. Subsequent
640 probe indices are computed as explained earlier.
641
642 All arithmetic on hash should ignore overflow.
643
644 The details in this version are due to Tim Peters, building on many past
645 contributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and
646 Christian Tismer.
647
648 lookdict() is general-purpose, and may return DKIX_ERROR if (and only if) a
649 comparison raises an exception.
650 lookdict_unicode() below is specialized to string keys, comparison of which can
651 never raise an exception; that function can never return DKIX_ERROR when key
652 is string. Otherwise, it falls back to lookdict().
653 lookdict_unicode_nodummy is further specialized for string keys that cannot be
654 the <dummy> value.
655 For both, when the key isn't found a DKIX_EMPTY is returned. hashpos returns
656 where the key index should be inserted.
657 */
658 static Py_ssize_t _Py_HOT_FUNCTION
659 lookdict(PyDictObject *mp, PyObject *key,
660 Py_hash_t hash, PyObject ***value_addr, Py_ssize_t *hashpos)
661 {
662 size_t i, mask, perturb;
663 PyDictKeysObject *dk;
664 PyDictKeyEntry *ep0;
665
666 top:
667 dk = mp->ma_keys;
668 ep0 = DK_ENTRIES(dk);
669 mask = DK_MASK(dk);
670 perturb = hash;
671 i = (size_t)hash & mask;
672
673 for (;;) {
674 Py_ssize_t ix = dictkeys_get_index(dk, i);
675 if (ix == DKIX_EMPTY) {
676 if (hashpos != NULL)
677 *hashpos = i;
678 *value_addr = NULL;
679 return ix;
680 }
681 if (ix >= 0) {
682 PyDictKeyEntry *ep = &ep0[ix];
683 assert(ep->me_key != NULL);
684 if (ep->me_key == key) {
685 *value_addr = &ep->me_value;
686 if (hashpos != NULL)
687 *hashpos = i;
688 return ix;
689 }
690 if (ep->me_hash == hash) {
691 PyObject *startkey = ep->me_key;
692 Py_INCREF(startkey);
693 int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
694 Py_DECREF(startkey);
695 if (cmp < 0) {
696 *value_addr = NULL;
697 return DKIX_ERROR;
698 }
699 if (dk == mp->ma_keys && ep->me_key == startkey) {
700 if (cmp > 0) {
701 *value_addr = &ep->me_value;
702 if (hashpos != NULL)
703 *hashpos = i;
704 return ix;
705 }
706 }
707 else {
708 /* The dict was mutated, restart */
709 goto top;
710 }
711 }
712 }
713 perturb >>= PERTURB_SHIFT;
714 i = (i*5 + perturb + 1) & mask;
715 }
716 Py_UNREACHABLE();
717 }
718
719 /* Faster version of lookdict_unicode when it is known that no <dummy> keys
720 * will be present. */
721 static Py_ssize_t _Py_HOT_FUNCTION
722 lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
723 Py_hash_t hash, PyObject ***value_addr,
724 Py_ssize_t *hashpos)
725 {
726 assert(mp->ma_values == NULL);
727 /* Make sure this function doesn't have to handle non-unicode keys,
728 including subclasses of str; e.g., one reason to subclass
729 unicodes is to override __eq__, and for speed we don't cater to
730 that here. */
731 if (!PyUnicode_CheckExact(key)) {
732 return lookdict(mp, key, hash, value_addr, hashpos);
733 }
734
735 PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
736 size_t mask = DK_MASK(mp->ma_keys);
737 size_t perturb = (size_t)hash;
738 size_t i = (size_t)hash & mask;
739
740 for (;;) {
741 Py_ssize_t ix = dictkeys_get_index(mp->ma_keys, i);
742 assert (ix != DKIX_DUMMY);
743 if (ix == DKIX_EMPTY) {
744 if (hashpos != NULL)
745 *hashpos = i;
746 *value_addr = NULL;
747 return DKIX_EMPTY;
748 }
749 PyDictKeyEntry *ep = &ep0[ix];
750 assert(ep->me_key != NULL);
751 assert(PyUnicode_CheckExact(ep->me_key));
752 if (ep->me_key == key ||
753 (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
754 if (hashpos != NULL)
755 *hashpos = i;
756 *value_addr = &ep->me_value;
757 return ix;
758 }
759 perturb >>= PERTURB_SHIFT;
760 i = mask & (i*5 + perturb + 1);
761 }
762 Py_UNREACHABLE();
763 }
764
765 #define MAINTAIN_TRACKING(mp, key, value) \
766 do { \
767 if (!_PyObject_GC_IS_TRACKED(mp)) { \
768 if (_PyObject_GC_MAY_BE_TRACKED(key) || \
769 _PyObject_GC_MAY_BE_TRACKED(value)) { \
770 PyObject_GC_Track(mp); \
771 } \
772 } \
773 } while(0)
774
775 /* Internal function to find slot for an item from its hash
776 when it is known that the key is not present in the dict.
777
778 The dict must be combined. */
779 static Py_ssize_t
780 find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash)
781 {
782 assert(keys != NULL);
783
784 const size_t mask = DK_MASK(keys);
785 size_t i = hash & mask;
786 Py_ssize_t ix = dictkeys_get_index(keys, i);
787 for (size_t perturb = hash; ix >= 0;) {
788 perturb >>= PERTURB_SHIFT;
789 i = (i*5 + perturb + 1) & mask;
790 ix = dictkeys_get_index(keys, i);
791 }
792 return i;
793 }
794
795 /*
796 Internal routine used by dictresize() to build a hashtable of entries.
797 */
798 static void
799 build_indices(PyDictKeysObject *keys, PyDictKeyEntry *ep, Py_ssize_t n)
800 {
801 size_t mask = (size_t)DK_SIZE(keys) - 1;
802 for (Py_ssize_t ix = 0; ix != n; ix++, ep++) {
803 Py_hash_t hash = ep->me_hash;
804 size_t i = hash & mask;
805 for (size_t perturb = hash; dictkeys_get_index(keys, i) != DKIX_EMPTY;) {
806 perturb >>= PERTURB_SHIFT;
807 i = mask & (i*5 + perturb + 1);
808 }
809 dictkeys_set_index(keys, i, ix);
810 }
811 }
812
813 static int
814 _d_PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey,
815 PyObject **pvalue, Py_hash_t *phash)
816 {
817 Py_ssize_t i;
818 PyDictObject *mp;
819 PyDictKeyEntry *entry_ptr;
820 PyObject *value;
821
822 if (!PyAnyDict_Check(op))
823 return 0;
824 mp = (PyDictObject *)op;
825 i = *ppos;
826 if (mp->ma_values) {
827 if (i < 0 || i >= mp->ma_used)
828 return 0;
829 /* values of split table is always dense */
830 entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
831 value = mp->ma_values[i];
832 assert(value != NULL);
833 }
834 else {
835 Py_ssize_t n = mp->ma_keys->dk_nentries;
836 if (i < 0 || i >= n)
837 return 0;
838 entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
839 while (i < n && entry_ptr->me_value == NULL) {
840 entry_ptr++;
841 i++;
842 }
843 if (i >= n)
844 return 0;
845 value = entry_ptr->me_value;
846 }
847 *ppos = i+1;
848 if (pkey)
849 *pkey = entry_ptr->me_key;
850 if (phash)
851 *phash = entry_ptr->me_hash;
852 if (pvalue)
853 *pvalue = value;
854 return 1;
855 }
856
857 /* Methods */
858
859 static void
860 dict_dealloc(PyDictObject *mp)
861 {
862 PyObject **values = mp->ma_values;
863 PyDictKeysObject *keys = mp->ma_keys;
864 Py_ssize_t i, n;
865
866 /* bpo-31095: UnTrack is needed before calling any callbacks */
867 PyObject_GC_UnTrack(mp);
868 Py_TRASHCAN_SAFE_BEGIN(mp)
869 if (values != NULL) {
870 if (values != empty_values) {
871 for (i = 0, n = mp->ma_keys->dk_nentries; i < n; i++) {
872 Py_XDECREF(values[i]);
873 }
874 free_values(values);
875 }
876 dictkeys_decref(keys);
877 }
878 else if (keys != NULL) {
879 assert(keys->dk_refcnt == 1 || keys == Py_EMPTY_KEYS);
880 dictkeys_decref(keys);
881 }
882 #if PyDict_MAXFREELIST > 0
883 if (numfree < PyDict_MAXFREELIST && Py_IS_TYPE(mp, &PyDict_Type)) {
884 free_list[numfree++] = mp;
885 }
886 else
887 #endif
888 {
889 Py_TYPE(mp)->tp_free((PyObject *)mp);
890 }
891 Py_TRASHCAN_SAFE_END(mp)
892 }
893
894 static PyObject *
895 dict_repr(PyDictObject *mp)
896 {
897 Py_ssize_t i;
898 PyObject *key = NULL, *value = NULL;
899 _PyUnicodeWriter writer;
900 int first;
901
902 i = Py_ReprEnter((PyObject *)mp);
903 if (i != 0) {
904 return i > 0 ? PyUnicode_FromString("{...}") : NULL;
905 }
906
907 if (mp->ma_used == 0) {
908 Py_ReprLeave((PyObject *)mp);
909 return PyUnicode_FromString("{}");
910 }
911
912 _PyUnicodeWriter_Init(&writer);
913 writer.overallocate = 1;
914 /* "{" + "1: 2" + ", 3: 4" * (len - 1) + "}" */
915 writer.min_length = 1 + 4 + (2 + 4) * (mp->ma_used - 1) + 1;
916
917 if (_PyUnicodeWriter_WriteChar(&writer, '{') < 0)
918 goto error;
919
920 /* Do repr() on each key+value pair, and insert ": " between them.
921 Note that repr may mutate the dict. */
922 i = 0;
923 first = 1;
924 while (_d_PyDict_Next((PyObject *)mp, &i, &key, &value, NULL)) {
925 PyObject *s;
926 int res;
927
928 /* Prevent repr from deleting key or value during key format. */
929 Py_INCREF(key);
930 Py_INCREF(value);
931
932 if (!first) {
933 if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)
934 goto error;
935 }
936 first = 0;
937
938 s = PyObject_Repr(key);
939 if (s == NULL)
940 goto error;
941 res = _PyUnicodeWriter_WriteStr(&writer, s);
942 Py_DECREF(s);
943 if (res < 0)
944 goto error;
945
946 if (_PyUnicodeWriter_WriteASCIIString(&writer, ": ", 2) < 0)
947 goto error;
948
949 s = PyObject_Repr(value);
950 if (s == NULL)
951 goto error;
952 res = _PyUnicodeWriter_WriteStr(&writer, s);
953 Py_DECREF(s);
954 if (res < 0)
955 goto error;
956
957 Py_CLEAR(key);
958 Py_CLEAR(value);
959 }
960
961 writer.overallocate = 0;
962 if (_PyUnicodeWriter_WriteChar(&writer, '}') < 0)
963 goto error;
964
965 Py_ReprLeave((PyObject *)mp);
966
967 return _PyUnicodeWriter_Finish(&writer);
968
969 error:
970 Py_ReprLeave((PyObject *)mp);
971 _PyUnicodeWriter_Dealloc(&writer);
972 Py_XDECREF(key);
973 Py_XDECREF(value);
974 return NULL;
975 }
976
977 static Py_ssize_t
978 dict_length(PyDictObject *mp)
979 {
980 return mp->ma_used;
981 }
982
983 static PyObject *
984 dict_subscript(PyDictObject *mp, PyObject *key)
985 {
986 PyObject *v;
987 Py_ssize_t ix;
988 Py_hash_t hash;
989 PyObject **value_addr;
990
991 if (!PyUnicode_CheckExact(key) ||
992 (hash = ((PyASCIIObject *) key)->hash) == -1) {
993 hash = PyObject_Hash(key);
994 if (hash == -1)
995 return NULL;
996 }
997 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, NULL);
998 if (ix == DKIX_ERROR)
999 return NULL;
1000 if (ix == DKIX_EMPTY || *value_addr == NULL) {
1001 if (!PyAnyDict_CheckExact(mp)) {
1002 /* Look up __missing__ method if we're a subclass. */
1003 PyObject *missing, *res;
1004 _Py_IDENTIFIER(__missing__);
1005 missing = _PyObject_LookupSpecial((PyObject *)mp, &PyId___missing__);
1006 if (missing != NULL) {
1007 res = PyObject_CallFunctionObjArgs(missing,
1008 key, NULL);
1009 Py_DECREF(missing);
1010 return res;
1011 }
1012 else if (PyErr_Occurred())
1013 return NULL;
1014 }
1015 _PyErr_SetKeyError(key);
1016 return NULL;
1017 }
1018 v = *value_addr;
1019 Py_INCREF(v);
1020 return v;
1021 }
1022
1023 static PyObject *
1024 dict_richcompare(PyObject *v, PyObject *w, int op)
1025 {
1026 int cmp;
1027 PyObject *res;
1028
1029 if (!PyAnyDict_Check(v) || !PyAnyDict_Check(w)) {
1030 res = Py_NotImplemented;
1031 }
1032 else if (op == Py_EQ || op == Py_NE) {
1033 cmp = frozendict_equal((PyDictObject *)v, (PyDictObject *)w);
1034 if (cmp < 0)
1035 return NULL;
1036 res = (cmp == (op == Py_EQ)) ? Py_True : Py_False;
1037 }
1038 else
1039 res = Py_NotImplemented;
1040 Py_INCREF(res);
1041 return res;
1042 }
1043
1044 /*[clinic input]
1045
1046 @coexist
1047 dict.__contains__
1048
1049 key: object
1050 /
1051
1052 True if the dictionary has the specified key, else False.
1053 [clinic start generated code]*/
1054
1055 static PyObject *
1056 dict___contains__(PyDictObject *self, PyObject *key)
1057 /*[clinic end generated code: output=a3d03db709ed6e6b input=fe1cb42ad831e820]*/
1058 {
1059 register PyDictObject *mp = self;
1060 Py_hash_t hash;
1061 Py_ssize_t ix;
1062 PyObject **value_addr;
1063
1064 if (!PyUnicode_CheckExact(key) ||
1065 (hash = ((PyASCIIObject *) key)->hash) == -1) {
1066 hash = PyObject_Hash(key);
1067 if (hash == -1)
1068 return NULL;
1069 }
1070 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, NULL);
1071 if (ix == DKIX_ERROR)
1072 return NULL;
1073 if (ix == DKIX_EMPTY || *value_addr == NULL)
1074 Py_RETURN_FALSE;
1075 Py_RETURN_TRUE;
1076 }
1077
1078 static PyObject *
1079 dict_get(PyDictObject *self, PyObject *args)
1080 {
1081 PyObject *key;
1082 PyObject *default_value = Py_None;
1083 PyObject *val = NULL;
1084 Py_hash_t hash;
1085 Py_ssize_t ix;
1086 PyObject **value_addr;
1087
1088 if (!PyArg_UnpackTuple(args, "get", 1, 2, &key, &default_value))
1089 return NULL;
1090
1091 if (!PyUnicode_CheckExact(key) ||
1092 (hash = ((PyASCIIObject *) key)->hash) == -1) {
1093 hash = PyObject_Hash(key);
1094 if (hash == -1)
1095 return NULL;
1096 }
1097 ix = (self->ma_keys->dk_lookup) (self, key, hash, &value_addr, NULL);
1098 if (ix == DKIX_ERROR)
1099 return NULL;
1100 if (ix == DKIX_EMPTY || *value_addr == NULL) {
1101 val = default_value;
1102 }
1103 else {
1104 val = *value_addr;
1105 }
1106 Py_INCREF(val);
1107 return val;
1108 }
1109
1110 static int
1111 dict_traverse(PyObject *op, visitproc visit, void *arg)
1112 {
1113 PyDictObject *mp = (PyDictObject *)op;
1114 PyDictKeysObject *keys = mp->ma_keys;
1115 PyDictKeyEntry *entries = DK_ENTRIES(keys);
1116 Py_ssize_t i, n = keys->dk_nentries;
1117
1118 if (keys->dk_lookup == lookdict) {
1119 for (i = 0; i < n; i++) {
1120 if (entries[i].me_value != NULL) {
1121 Py_VISIT(entries[i].me_value);
1122 Py_VISIT(entries[i].me_key);
1123 }
1124 }
1125 }
1126 else {
1127 if (mp->ma_values != NULL) {
1128 for (i = 0; i < n; i++) {
1129 Py_VISIT(mp->ma_values[i]);
1130 }
1131 }
1132 else {
1133 for (i = 0; i < n; i++) {
1134 Py_VISIT(entries[i].me_value);
1135 }
1136 }
1137 }
1138 return 0;
1139 }
1140
1141 static PyObject *dictiter_new(PyDictObject *, PyTypeObject *);
1142
1143 static Py_ssize_t
1144 _d_PyDict_SizeOf(PyDictObject *mp)
1145 {
1146 Py_ssize_t size, usable, res;
1147
1148 size = DK_SIZE(mp->ma_keys);
1149 usable = USABLE_FRACTION(size);
1150
1151 res = _PyObject_SIZE(Py_TYPE(mp));
1152 if (mp->ma_values)
1153 res += usable * sizeof(PyObject*);
1154 /* If the dictionary is split, the keys portion is accounted-for
1155 in the type object. */
1156 if (mp->ma_keys->dk_refcnt == 1)
1157 res += (sizeof(PyDictKeysObject)
1158 + DK_IXSIZE(mp->ma_keys) * size
1159 + sizeof(PyDictKeyEntry) * usable);
1160 return res;
1161 }
1162
1163 static PyObject *
1164 dict_sizeof(PyDictObject *mp, PyObject *Py_UNUSED(ignored))
1165 {
1166 return PyLong_FromSsize_t(_d_PyDict_SizeOf(mp));
1167 }
1168
1169 PyDoc_STRVAR(getitem__doc__, "x.__getitem__(y) <==> x[y]");
1170
1171 PyDoc_STRVAR(sizeof__doc__,
1172 "D.__sizeof__() -> size of D in memory, in bytes");
1173
1174 PyDoc_STRVAR(copy__doc__,
1175 "D.copy() -> a shallow copy of D");
1176
1177 PyDoc_STRVAR(keys__doc__,
1178 "D.keys() -> a set-like object providing a view on D's keys");
1179 PyDoc_STRVAR(items__doc__,
1180 "D.items() -> a set-like object providing a view on D's items");
1181 PyDoc_STRVAR(values__doc__,
1182 "D.values() -> an object providing a view on D's values");
1183
1184 /* Hack to implement "key in dict" */
1185 static PySequenceMethods dict_as_sequence = {
1186 0, /* sq_length */
1187 0, /* sq_concat */
1188 0, /* sq_repeat */
1189 0, /* sq_item */
1190 0, /* sq_slice */
1191 0, /* sq_ass_item */
1192 0, /* sq_ass_slice */
1193 PyDict_Contains, /* sq_contains */
1194 0, /* sq_inplace_concat */
1195 0, /* sq_inplace_repeat */
1196 };
1197
1198 /* Dictionary iterator types */
1199
1200 typedef struct {
1201 PyObject_HEAD
1202 PyDictObject *di_dict; /* Set to NULL when iterator is exhausted */
1203 Py_ssize_t di_used;
1204 Py_ssize_t di_pos;
1205 PyObject* di_result; /* reusable result tuple for iteritems */
1206 Py_ssize_t len;
1207 } dictiterobject;
1208
1209 PyTypeObject PyDictRevIterKey_Type;
1210 PyTypeObject PyDictRevIterValue_Type;
1211 PyTypeObject PyDictRevIterItem_Type;
1212
1213 static PyObject *
1214 dictiter_new(PyDictObject *dict, PyTypeObject *itertype)
1215 {
1216 dictiterobject *di;
1217 di = PyObject_GC_New(dictiterobject, itertype);
1218 if (di == NULL) {
1219 return NULL;
1220 }
1221 Py_INCREF(dict);
1222 di->di_dict = dict;
1223 di->di_used = dict->ma_used;
1224 di->len = dict->ma_used;
1225 if (itertype == &PyDictRevIterKey_Type ||
1226 itertype == &PyDictRevIterItem_Type ||
1227 itertype == &PyDictRevIterValue_Type) {
1228 if (dict->ma_values) {
1229 di->di_pos = dict->ma_used - 1;
1230 }
1231 else {
1232 di->di_pos = dict->ma_keys->dk_nentries - 1;
1233 }
1234 }
1235 else {
1236 di->di_pos = 0;
1237 }
1238 if (
1239 itertype == &PyFrozenDictIterItem_Type ||
1240 itertype == &PyDictRevIterItem_Type
1241 ) {
1242 di->di_result = PyTuple_Pack(2, Py_None, Py_None);
1243 if (di->di_result == NULL) {
1244 Py_DECREF(di);
1245 return NULL;
1246 }
1247 }
1248 else {
1249 di->di_result = NULL;
1250 }
1251 PyObject_GC_Track(di);
1252 return (PyObject *)di;
1253 }
1254
1255 static void
1256 dictiter_dealloc(dictiterobject *di)
1257 {
1258 /* bpo-31095: UnTrack is needed before calling any callbacks */
1259 PyObject_GC_UnTrack(di);
1260 Py_XDECREF(di->di_dict);
1261 Py_XDECREF(di->di_result);
1262 PyObject_GC_Del(di);
1263 }
1264
1265 static int
1266 dictiter_traverse(dictiterobject *di, visitproc visit, void *arg)
1267 {
1268 Py_VISIT(di->di_dict);
1269 Py_VISIT(di->di_result);
1270 return 0;
1271 }
1272
1273 static PyObject *
1274 dictiter_len(dictiterobject *di, PyObject *Py_UNUSED(ignored))
1275 {
1276 Py_ssize_t len = 0;
1277 if (di->di_dict != NULL && di->di_used == di->di_dict->ma_used)
1278 len = di->len;
1279 return PyLong_FromSize_t(len);
1280 }
1281
1282 PyDoc_STRVAR(length_hint_doc,
1283 "Private method returning an estimate of len(list(it)).");
1284
1285 static PyObject *
1286 dictiter_reduce(dictiterobject *di, PyObject *Py_UNUSED(ignored));
1287
1288 PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1289
1290 static PyMethodDef dictiter_methods[] = {
1291 {"__length_hint__", (PyCFunction)(void(*)(void))dictiter_len, METH_NOARGS,
1292 length_hint_doc},
1293 {"__reduce__", (PyCFunction)(void(*)(void))dictiter_reduce, METH_NOARGS,
1294 reduce_doc},
1295 {NULL, NULL} /* sentinel */
1296 };
1297
1298 /* dictreviter */
1299
1300 static PyObject *
1301 dictreviter_iternext(dictiterobject *di)
1302 {
1303 PyDictObject *d = di->di_dict;
1304
1305 if (d == NULL) {
1306 return NULL;
1307 }
1308 assert (PyAnyDict_Check(d));
1309
1310 if (di->di_used != d->ma_used) {
1311 PyErr_SetString(PyExc_RuntimeError,
1312 "dictionary changed size during iteration");
1313 di->di_used = -1; /* Make this state sticky */
1314 return NULL;
1315 }
1316
1317 Py_ssize_t i = di->di_pos;
1318 PyDictKeysObject *k = d->ma_keys;
1319 PyObject *key, *value, *result;
1320
1321 if (i < 0) {
1322 goto fail;
1323 }
1324 if (d->ma_values) {
1325 key = DK_ENTRIES(k)[i].me_key;
1326 value = d->ma_values[i];
1327 assert (value != NULL);
1328 }
1329 else {
1330 PyDictKeyEntry *entry_ptr = &DK_ENTRIES(k)[i];
1331 while (entry_ptr->me_value == NULL) {
1332 if (--i < 0) {
1333 goto fail;
1334 }
1335 entry_ptr--;
1336 }
1337 key = entry_ptr->me_key;
1338 value = entry_ptr->me_value;
1339 }
1340 di->di_pos = i-1;
1341 di->len--;
1342
1343 if (Py_IS_TYPE(di, &PyDictRevIterKey_Type)) {
1344 Py_INCREF(key);
1345 return key;
1346 }
1347 else if (Py_IS_TYPE(di, &PyDictRevIterValue_Type)) {
1348 Py_INCREF(value);
1349 return value;
1350 }
1351 else if (Py_IS_TYPE(di, &PyDictRevIterItem_Type)) {
1352 Py_INCREF(key);
1353 Py_INCREF(value);
1354 result = di->di_result;
1355 if (Py_REFCNT(result) == 1) {
1356 PyObject *oldkey = PyTuple_GET_ITEM(result, 0);
1357 PyObject *oldvalue = PyTuple_GET_ITEM(result, 1);
1358 PyTuple_SET_ITEM(result, 0, key); /* steals reference */
1359 PyTuple_SET_ITEM(result, 1, value); /* steals reference */
1360 Py_INCREF(result);
1361 Py_DECREF(oldkey);
1362 Py_DECREF(oldvalue);
1363 // bpo-42536: The GC may have untracked this result tuple. Since
1364 // we're recycling it, make sure it's tracked again:
1365 // if (!_PyObject_GC_IS_TRACKED(result)) {
1366 // _PyObject_GC_TRACK(result);
1367 // }
1368 }
1369 else {
1370 result = PyTuple_New(2);
1371 if (result == NULL) {
1372 return NULL;
1373 }
1374 PyTuple_SET_ITEM(result, 0, key); /* steals reference */
1375 PyTuple_SET_ITEM(result, 1, value); /* steals reference */
1376 }
1377 return result;
1378 }
1379 else {
1380 Py_UNREACHABLE();
1381 }
1382
1383 fail:
1384 di->di_dict = NULL;
1385 Py_DECREF(d);
1386 return NULL;
1387 }
1388
1389 PyTypeObject PyDictRevIterKey_Type = {
1390 PyVarObject_HEAD_INIT(NULL, 0)
1391 "dict_reversekeyiterator",
1392 sizeof(dictiterobject),
1393 .tp_dealloc = (destructor)dictiter_dealloc,
1394 .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,
1395 .tp_traverse = (traverseproc)dictiter_traverse,
1396 .tp_iter = PyObject_SelfIter,
1397 .tp_iternext = (iternextfunc)dictreviter_iternext,
1398 .tp_methods = dictiter_methods
1399 };
1400
1401 PyTypeObject PyDictRevIterItem_Type = {
1402 PyVarObject_HEAD_INIT(NULL, 0)
1403 "dict_reverseitemiterator",
1404 sizeof(dictiterobject),
1405 .tp_dealloc = (destructor)dictiter_dealloc,
1406 .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,
1407 .tp_traverse = (traverseproc)dictiter_traverse,
1408 .tp_iter = PyObject_SelfIter,
1409 .tp_iternext = (iternextfunc)dictreviter_iternext,
1410 .tp_methods = dictiter_methods
1411 };
1412
1413 PyTypeObject PyDictRevIterValue_Type = {
1414 PyVarObject_HEAD_INIT(NULL, 0)
1415 "dict_reversevalueiterator",
1416 sizeof(dictiterobject),
1417 .tp_dealloc = (destructor)dictiter_dealloc,
1418 .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,
1419 .tp_traverse = (traverseproc)dictiter_traverse,
1420 .tp_iter = PyObject_SelfIter,
1421 .tp_iternext = (iternextfunc)dictreviter_iternext,
1422 .tp_methods = dictiter_methods
1423 };
1424
1425 /*[clinic input]
1426 dict.__reversed__
1427
1428 Return a reverse iterator over the dict keys.
1429 [clinic start generated code]*/
1430
1431 static PyObject *
1432 dict___reversed___impl(PyDictObject *self)
1433 /*[clinic end generated code: output=e674483336d1ed51 input=23210ef3477d8c4d]*/
1434 {
1435 assert (PyAnyDict_Check(self));
1436 return dictiter_new(self, &PyDictRevIterKey_Type);
1437 }
1438
1439 static PyObject *
1440 dictiter_reduce(dictiterobject *di, PyObject *Py_UNUSED(ignored))
1441 {
1442 _Py_IDENTIFIER(iter);
1443 /* copy the iterator state */
1444 dictiterobject tmp = *di;
1445 Py_XINCREF(tmp.di_dict);
1446
1447 PyObject *list = PySequence_List((PyObject*)&tmp);
1448 Py_XDECREF(tmp.di_dict);
1449 if (list == NULL) {
1450 return NULL;
1451 }
1452 return Py_BuildValue("N(N)", _PyEval_GetBuiltinId(&PyId_iter), list);
1453 }
1454
1455 /***********************************************/
1456 /* View objects for keys(), items(), values(). */
1457 /***********************************************/
1458
1459 /* The instance lay-out is the same for all three; but the type differs. */
1460
1461 static void
1462 dictview_dealloc(_PyDictViewObject *dv)
1463 {
1464 /* bpo-31095: UnTrack is needed before calling any callbacks */
1465 PyObject_GC_UnTrack(dv);
1466 Py_XDECREF(dv->dv_dict);
1467 PyObject_GC_Del(dv);
1468 }
1469
1470 static int
1471 dictview_traverse(_PyDictViewObject *dv, visitproc visit, void *arg)
1472 {
1473 Py_VISIT(dv->dv_dict);
1474 return 0;
1475 }
1476
1477 static Py_ssize_t
1478 dictview_len(_PyDictViewObject *dv)
1479 {
1480 Py_ssize_t len = 0;
1481 if (dv->dv_dict != NULL)
1482 len = dv->dv_dict->ma_used;
1483 return len;
1484 }
1485
1486 static PyObject *
1487 _d_PyDictView_New(PyObject *dict, PyTypeObject *type)
1488 {
1489 _PyDictViewObject *dv;
1490 if (dict == NULL) {
1491 PyErr_BadInternalCall();
1492 return NULL;
1493 }
1494 if (!PyAnyDict_Check(dict)) {
1495 /* XXX Get rid of this restriction later */
1496 PyErr_Format(PyExc_TypeError,
1497 "%s() requires a dict argument, not '%s'",
1498 type->tp_name, Py_TYPE(dict)->tp_name);
1499 return NULL;
1500 }
1501 dv = PyObject_GC_New(_PyDictViewObject, type);
1502 if (dv == NULL)
1503 return NULL;
1504 Py_INCREF(dict);
1505 dv->dv_dict = (PyDictObject *)dict;
1506 PyObject_GC_Track(dv);
1507 return (PyObject *)dv;
1508 }
1509
1510 static PyObject *
1511 dictview_mapping(PyObject *view, void *Py_UNUSED(ignored)) {
1512 assert(view != NULL);
1513 assert(PyAnyDictKeys_Check(view)
1514 || PyAnyDictValues_Check(view)
1515 || PyAnyDictItems_Check(view));
1516 PyObject *mapping = (PyObject *)((_PyDictViewObject *)view)->dv_dict;
1517 return PyDictProxy_New(mapping);
1518 }
1519
1520 static PyGetSetDef dictview_getset[] = {
1521 {"mapping", dictview_mapping, (setter)NULL,
1522 "dictionary that this view refers to", NULL},
1523 {0}
1524 };
1525
1526 /* TODO(guido): The views objects are not complete:
1527
1528 * support more set operations
1529 * support arbitrary mappings?
1530 - either these should be static or exported in dictobject.h
1531 - if public then they should probably be in builtins
1532 */
1533
1534 /* Return 1 if self is a subset of other, iterating over self;
1535 0 if not; -1 if an error occurred. */
1536 static int
1537 all_contained_in(PyObject *self, PyObject *other)
1538 {
1539 PyObject *iter = PyObject_GetIter(self);
1540 int ok = 1;
1541
1542 if (iter == NULL)
1543 return -1;
1544 for (;;) {
1545 PyObject *next = PyIter_Next(iter);
1546 if (next == NULL) {
1547 if (PyErr_Occurred())
1548 ok = -1;
1549 break;
1550 }
1551 ok = PySequence_Contains(other, next);
1552 Py_DECREF(next);
1553 if (ok <= 0)
1554 break;
1555 }
1556 Py_DECREF(iter);
1557 return ok;
1558 }
1559
1560 static PyObject *
1561 dictview_richcompare(PyObject *self, PyObject *other, int op)
1562 {
1563 Py_ssize_t len_self, len_other;
1564 int ok;
1565 PyObject *result;
1566
1567 assert(self != NULL);
1568 assert(PyAnyDictViewSet_Check(self));
1569 assert(other != NULL);
1570
1571 if (!PyAnySet_Check(other) && !PyAnyDictViewSet_Check(other))
1572 Py_RETURN_NOTIMPLEMENTED;
1573
1574 len_self = PyObject_Size(self);
1575 if (len_self < 0)
1576 return NULL;
1577 len_other = PyObject_Size(other);
1578 if (len_other < 0)
1579 return NULL;
1580
1581 ok = 0;
1582 switch(op) {
1583
1584 case Py_NE:
1585 case Py_EQ:
1586 if (len_self == len_other)
1587 ok = all_contained_in(self, other);
1588 if (op == Py_NE && ok >= 0)
1589 ok = !ok;
1590 break;
1591
1592 case Py_LT:
1593 if (len_self < len_other)
1594 ok = all_contained_in(self, other);
1595 break;
1596
1597 case Py_LE:
1598 if (len_self <= len_other)
1599 ok = all_contained_in(self, other);
1600 break;
1601
1602 case Py_GT:
1603 if (len_self > len_other)
1604 ok = all_contained_in(other, self);
1605 break;
1606
1607 case Py_GE:
1608 if (len_self >= len_other)
1609 ok = all_contained_in(other, self);
1610 break;
1611
1612 }
1613 if (ok < 0)
1614 return NULL;
1615 result = ok ? Py_True : Py_False;
1616 Py_INCREF(result);
1617 return result;
1618 }
1619
1620 static PyObject *
1621 dictview_repr(_PyDictViewObject *dv)
1622 {
1623 PyObject *seq;
1624 PyObject *result = NULL;
1625 Py_ssize_t rc;
1626
1627 rc = Py_ReprEnter((PyObject *)dv);
1628 if (rc != 0) {
1629 return rc > 0 ? PyUnicode_FromString("...") : NULL;
1630 }
1631 seq = PySequence_List((PyObject *)dv);
1632 if (seq == NULL) {
1633 goto Done;
1634 }
1635 result = PyUnicode_FromFormat("%s(%R)", Py_TYPE(dv)->tp_name, seq);
1636 Py_DECREF(seq);
1637
1638 Done:
1639 Py_ReprLeave((PyObject *)dv);
1640 return result;
1641 }
1642
1643 /*** dict_keys ***/
1644
1645 static int
1646 dictkeys_contains(_PyDictViewObject *dv, PyObject *obj)
1647 {
1648 if (dv->dv_dict == NULL)
1649 return 0;
1650 return PyDict_Contains((PyObject *)dv->dv_dict, obj);
1651 }
1652
1653 static PySequenceMethods dictkeys_as_sequence = {
1654 (lenfunc)dictview_len, /* sq_length */
1655 0, /* sq_concat */
1656 0, /* sq_repeat */
1657 0, /* sq_item */
1658 0, /* sq_slice */
1659 0, /* sq_ass_item */
1660 0, /* sq_ass_slice */
1661 (objobjproc)dictkeys_contains, /* sq_contains */
1662 };
1663
1664 // Create an set object from dictviews object.
1665 // Returns a new reference.
1666 // This utility function is used by set operations.
1667 static PyObject*
1668 dictviews_to_set(PyObject *self)
1669 {
1670 PyObject *left = self;
1671 if (PyAnyDictKeys_Check(self)) {
1672 // PySet_New() has fast path for the dict object.
1673 PyObject *dict = (PyObject *)((_PyDictViewObject *)self)->dv_dict;
1674 if (PyAnyDict_CheckExact(dict)) {
1675 left = dict;
1676 }
1677 }
1678 return PySet_New(left);
1679 }
1680
1681 static PyObject*
1682 dictviews_sub(PyObject* self, PyObject *other)
1683 {
1684 PyObject *result = dictviews_to_set(self);
1685 if (result == NULL) {
1686 return NULL;
1687 }
1688
1689 _Py_IDENTIFIER(difference_update);
1690 PyObject *tmp = _PyObject_CallMethodIdObjArgs(result, &PyId_difference_update, other, NULL);
1691 if (tmp == NULL) {
1692 Py_DECREF(result);
1693 return NULL;
1694 }
1695
1696 Py_DECREF(tmp);
1697 return result;
1698 }
1699
1700 static int
1701 dictitems_contains(_PyDictViewObject *dv, PyObject *obj);
1702
1703 static PyObject*
1704 _d_PyDictView_Intersect(PyObject* self, PyObject *other)
1705 {
1706 PyObject *result;
1707 PyObject *it;
1708 PyObject *key;
1709 Py_ssize_t len_self;
1710 int rv;
1711 int (*dict_contains)(_PyDictViewObject *, PyObject *);
1712
1713 /* Python interpreter swaps parameters when dict view
1714 is on right side of & */
1715 if (!PyAnyDictViewSet_Check(self)) {
1716 PyObject *tmp = other;
1717 other = self;
1718 self = tmp;
1719 }
1720
1721 len_self = dictview_len((_PyDictViewObject *)self);
1722
1723 /* if other is a set and self is smaller than other,
1724 reuse set intersection logic */
1725 if (PySet_CheckExact(other) && len_self <= PyObject_Size(other)) {
1726 _Py_IDENTIFIER(intersection);
1727 return _PyObject_CallMethodIdObjArgs(other, &PyId_intersection, self, NULL);
1728 }
1729
1730 /* if other is another dict view, and it is bigger than self,
1731 swap them */
1732 if (PyAnyDictViewSet_Check(other)) {
1733 Py_ssize_t len_other = dictview_len((_PyDictViewObject *)other);
1734 if (len_other > len_self) {
1735 PyObject *tmp = other;
1736 other = self;
1737 self = tmp;
1738 }
1739 }
1740
1741 /* at this point, two things should be true
1742 1. self is a dictview
1743 2. if other is a dictview then it is smaller than self */
1744 result = PySet_New(NULL);
1745 if (result == NULL)
1746 return NULL;
1747
1748 it = PyObject_GetIter(other);
1749 if (it == NULL) {
1750 Py_DECREF(result);
1751 return NULL;
1752 }
1753
1754 if (PyAnyDictKeys_Check(self)) {
1755 dict_contains = dictkeys_contains;
1756 }
1757 /* else PyDictItems_Check(self) */
1758 else {
1759 dict_contains = dictitems_contains;
1760 }
1761
1762 while ((key = PyIter_Next(it)) != NULL) {
1763 rv = dict_contains((_PyDictViewObject *)self, key);
1764 if (rv < 0) {
1765 goto error;
1766 }
1767 if (rv) {
1768 if (PySet_Add(result, key)) {
1769 goto error;
1770 }
1771 }
1772 Py_DECREF(key);
1773 }
1774 Py_DECREF(it);
1775 if (PyErr_Occurred()) {
1776 Py_DECREF(result);
1777 return NULL;
1778 }
1779 return result;
1780
1781 error:
1782 Py_DECREF(it);
1783 Py_DECREF(result);
1784 Py_DECREF(key);
1785 return NULL;
1786 }
1787
1788 static PyObject*
1789 dictviews_or(PyObject* self, PyObject *other)
1790 {
1791 PyObject *result = dictviews_to_set(self);
1792 if (result == NULL) {
1793 return NULL;
1794 }
1795
1796 if (_PySet_Update(result, other) < 0) {
1797 Py_DECREF(result);
1798 return NULL;
1799 }
1800 return result;
1801 }
1802
1803 static PyObject*
1804 dictitems_xor(PyObject *self, PyObject *other)
1805 {
1806 assert(PyAnyDictItems_Check(self));
1807 assert(PyAnyDictItems_Check(other));
1808 PyObject *d1 = (PyObject *)((_PyDictViewObject *)self)->dv_dict;
1809 PyObject *d2 = (PyObject *)((_PyDictViewObject *)other)->dv_dict;
1810
1811 PyObject *temp_dict;
1812
1813 if (PyDict_CheckExact(d1)) {
1814 temp_dict = PyDict_Copy(d1);
1815 }
1816 else {
1817 PyObject* args = PyTuple_New(1);
1818
1819 if (args == NULL) {
1820 return NULL;
1821 }
1822
1823 Py_INCREF(d1);
1824 PyTuple_SET_ITEM(args, 0, d1);
1825
1826 temp_dict = PyObject_Call((PyObject *) &PyDict_Type, args, NULL);
1827 Py_DECREF(args);
1828 }
1829 if (temp_dict == NULL) {
1830 return NULL;
1831 }
1832 PyObject *result_set = PySet_New(NULL);
1833 if (result_set == NULL) {
1834 Py_CLEAR(temp_dict);
1835 return NULL;
1836 }
1837
1838 PyObject *key = NULL, *val1 = NULL, *val2 = NULL;
1839 Py_ssize_t pos = 0;
1840 Py_hash_t hash;
1841
1842 while (_d_PyDict_Next(d2, &pos, &key, &val2, &hash)) {
1843 Py_INCREF(key);
1844 Py_INCREF(val2);
1845 val1 = _PyDict_GetItem_KnownHash(temp_dict, key, hash);
1846
1847 int to_delete;
1848 if (val1 == NULL) {
1849 if (PyErr_Occurred()) {
1850 goto error;
1851 }
1852 to_delete = 0;
1853 }
1854 else {
1855 Py_INCREF(val1);
1856 to_delete = PyObject_RichCompareBool(val1, val2, Py_EQ);
1857 if (to_delete < 0) {
1858 goto error;
1859 }
1860 }
1861
1862 if (to_delete) {
1863 if (_PyDict_DelItem_KnownHash(temp_dict, key, hash) < 0) {
1864 goto error;
1865 }
1866 }
1867 else {
1868 PyObject *pair = PyTuple_Pack(2, key, val2);
1869 if (pair == NULL) {
1870 goto error;
1871 }
1872 if (PySet_Add(result_set, pair) < 0) {
1873 Py_DECREF(pair);
1874 goto error;
1875 }
1876 Py_DECREF(pair);
1877 }
1878 Py_DECREF(key);
1879 Py_XDECREF(val1);
1880 Py_DECREF(val2);
1881 }
1882 key = val1 = val2 = NULL;
1883
1884 _Py_IDENTIFIER(items);
1885 PyObject *remaining_pairs = _PyObject_CallMethodIdObjArgs(temp_dict,
1886 &PyId_items, NULL);
1887 if (remaining_pairs == NULL) {
1888 goto error;
1889 }
1890 if (_PySet_Update(result_set, remaining_pairs) < 0) {
1891 Py_DECREF(remaining_pairs);
1892 goto error;
1893 }
1894 Py_DECREF(temp_dict);
1895 Py_DECREF(remaining_pairs);
1896 return result_set;
1897
1898 error:
1899 Py_XDECREF(temp_dict);
1900 Py_XDECREF(result_set);
1901 Py_XDECREF(key);
1902 Py_XDECREF(val1);
1903 Py_XDECREF(val2);
1904 return NULL;
1905 }
1906
1907 static PyObject*
1908 dictviews_xor(PyObject* self, PyObject *other)
1909 {
1910 if (PyAnyDictItems_Check(self) && PyAnyDictItems_Check(other)) {
1911 return dictitems_xor(self, other);
1912 }
1913 PyObject *result = dictviews_to_set(self);
1914 if (result == NULL) {
1915 return NULL;
1916 }
1917
1918 _Py_IDENTIFIER(symmetric_difference_update);
1919 PyObject *tmp = _PyObject_CallMethodIdObjArgs(result, &PyId_symmetric_difference_update, other, NULL);
1920 if (tmp == NULL) {
1921 Py_DECREF(result);
1922 return NULL;
1923 }
1924
1925 Py_DECREF(tmp);
1926 return result;
1927 }
1928
1929 static PyNumberMethods dictviews_as_number = {
1930 0, /*nb_add*/
1931 (binaryfunc)dictviews_sub, /*nb_subtract*/
1932 0, /*nb_multiply*/
1933 0, /*nb_remainder*/
1934 0, /*nb_divmod*/
1935 0, /*nb_power*/
1936 0, /*nb_negative*/
1937 0, /*nb_positive*/
1938 0, /*nb_absolute*/
1939 0, /*nb_bool*/
1940 0, /*nb_invert*/
1941 0, /*nb_lshift*/
1942 0, /*nb_rshift*/
1943 (binaryfunc)_d_PyDictView_Intersect,/*nb_and*/
1944 (binaryfunc)dictviews_xor, /*nb_xor*/
1945 (binaryfunc)dictviews_or, /*nb_or*/
1946 };
1947
1948 static PyObject*
1949 dictviews_isdisjoint(PyObject *self, PyObject *other)
1950 {
1951 PyObject *it;
1952 PyObject *item = NULL;
1953
1954 if (self == other) {
1955 if (dictview_len((_PyDictViewObject *)self) == 0)
1956 Py_RETURN_TRUE;
1957 else
1958 Py_RETURN_FALSE;
1959 }
1960
1961 /* Iterate over the shorter object (only if other is a set,
1962 * because PySequence_Contains may be expensive otherwise): */
1963 if (PyAnySet_Check(other) || PyAnyDictViewSet_Check(other)) {
1964 Py_ssize_t len_self = dictview_len((_PyDictViewObject *)self);
1965 Py_ssize_t len_other = PyObject_Size(other);
1966 if (len_other == -1)
1967 return NULL;
1968
1969 if ((len_other > len_self)) {
1970 PyObject *tmp = other;
1971 other = self;
1972 self = tmp;
1973 }
1974 }
1975
1976 it = PyObject_GetIter(other);
1977 if (it == NULL)
1978 return NULL;
1979
1980 while ((item = PyIter_Next(it)) != NULL) {
1981 int contains = PySequence_Contains(self, item);
1982 Py_DECREF(item);
1983 if (contains == -1) {
1984 Py_DECREF(it);
1985 return NULL;
1986 }
1987
1988 if (contains) {
1989 Py_DECREF(it);
1990 Py_RETURN_FALSE;
1991 }
1992 }
1993 Py_DECREF(it);
1994 if (PyErr_Occurred())
1995 return NULL; /* PyIter_Next raised an exception. */
1996 Py_RETURN_TRUE;
1997 }
1998
1999 PyDoc_STRVAR(isdisjoint_doc,
2000 "Return True if the view and the given iterable have a null intersection.");
2001
2002 static PyObject* dictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored));
2003
2004 PyDoc_STRVAR(reversed_keys_doc,
2005 "Return a reverse iterator over the dict keys.");
2006
2007 static PyMethodDef dictkeys_methods[] = {
2008 {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
2009 isdisjoint_doc},
2010 {"__reversed__", (PyCFunction)(void(*)(void))dictkeys_reversed, METH_NOARGS,
2011 reversed_keys_doc},
2012 {NULL, NULL} /* sentinel */
2013 };
2014
2015 static PyObject *
2016 dictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
2017 {
2018 if (dv->dv_dict == NULL) {
2019 Py_RETURN_NONE;
2020 }
2021 return dictiter_new(dv->dv_dict, &PyDictRevIterKey_Type);
2022 }
2023
2024 /*** dict_items ***/
2025
2026 /* Variant of PyDict_GetItem() that doesn't suppress exceptions.
2027 This returns NULL *with* an exception set if an exception occurred.
2028 It returns NULL *without* an exception set if the key wasn't present.
2029 */
2030 static PyObject *
2031 d_PyDict_GetItemWithError(PyObject *op, PyObject *key)
2032 {
2033 Py_ssize_t ix;
2034 Py_hash_t hash;
2035 PyDictObject*mp = (PyDictObject *)op;
2036 PyObject **value_addr;
2037
2038 if (!PyAnyDict_Check(op)) {
2039 PyErr_BadInternalCall();
2040 return NULL;
2041 }
2042 if (!PyUnicode_CheckExact(key) ||
2043 (hash = ((PyASCIIObject *) key)->hash) == -1)
2044 {
2045 hash = PyObject_Hash(key);
2046 if (hash == -1) {
2047 return NULL;
2048 }
2049 }
2050
2051 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, NULL);
2052 if (ix < 0)
2053 return NULL;
2054 return *value_addr;
2055 }
2056
2057 static int
2058 dictitems_contains(_PyDictViewObject *dv, PyObject *obj)
2059 {
2060 int result;
2061 PyObject *key, *value, *found;
2062 if (dv->dv_dict == NULL)
2063 return 0;
2064 if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 2)
2065 return 0;
2066 key = PyTuple_GET_ITEM(obj, 0);
2067 value = PyTuple_GET_ITEM(obj, 1);
2068 found = d_PyDict_GetItemWithError((PyObject *)dv->dv_dict, key);
2069 if (found == NULL) {
2070 if (PyErr_Occurred())
2071 return -1;
2072 return 0;
2073 }
2074 Py_INCREF(found);
2075 result = PyObject_RichCompareBool(found, value, Py_EQ);
2076 Py_DECREF(found);
2077 return result;
2078 }
2079
2080 static PySequenceMethods dictitems_as_sequence = {
2081 (lenfunc)dictview_len, /* sq_length */
2082 0, /* sq_concat */
2083 0, /* sq_repeat */
2084 0, /* sq_item */
2085 0, /* sq_slice */
2086 0, /* sq_ass_item */
2087 0, /* sq_ass_slice */
2088 (objobjproc)dictitems_contains, /* sq_contains */
2089 };
2090
2091 static PyObject* dictitems_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored));
2092
2093 PyDoc_STRVAR(reversed_items_doc,
2094 "Return a reverse iterator over the dict items.");
2095
2096 static PyMethodDef dictitems_methods[] = {
2097 {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
2098 isdisjoint_doc},
2099 {"__reversed__", (PyCFunction)dictitems_reversed, METH_NOARGS,
2100 reversed_items_doc},
2101 {NULL, NULL} /* sentinel */
2102 };
2103
2104 static PyObject *
2105 dictitems_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
2106 {
2107 if (dv->dv_dict == NULL) {
2108 Py_RETURN_NONE;
2109 }
2110 return dictiter_new(dv->dv_dict, &PyDictRevIterItem_Type);
2111 }
2112
2113 /*** dict_values ***/
2114
2115 static PySequenceMethods dictvalues_as_sequence = {
2116 (lenfunc)dictview_len, /* sq_length */
2117 0, /* sq_concat */
2118 0, /* sq_repeat */
2119 0, /* sq_item */
2120 0, /* sq_slice */
2121 0, /* sq_ass_item */
2122 0, /* sq_ass_slice */
2123 (objobjproc)0, /* sq_contains */
2124 };
2125
2126 static PyObject* dictvalues_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored));
2127
2128 PyDoc_STRVAR(reversed_values_doc,
2129 "Return a reverse iterator over the dict values.");
2130
2131 static PyMethodDef dictvalues_methods[] = {
2132 {"__reversed__", (PyCFunction)dictvalues_reversed, METH_NOARGS,
2133 reversed_values_doc},
2134 {NULL, NULL} /* sentinel */
2135 };
2136
2137 static PyObject *
2138 dictvalues_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
2139 {
2140 if (dv->dv_dict == NULL) {
2141 Py_RETURN_NONE;
2142 }
2143 return dictiter_new(dv->dv_dict, &PyDictRevIterValue_Type);
2144 }