Debian Codegraph @

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