Debian Codegraph @

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