Debian Codegraph @

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