Debian Codegraph @

src/frozendict/c_src/3_7/cpython_src/Objects/dictobject_original.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 "internal/pystate.h"
115 #include "dict-common.h"
116 #include "stringlib/eq.h" /* to get unicode_eq() */
117
118 /*[clinic input]
119 class dict "PyDictObject *" "&PyDict_Type"
120 [clinic start generated code]*/
121 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=f157a5a0ce9589d6]*/
122
123
124 /*
125 To ensure the lookup algorithm terminates, there must be at least one Unused
126 slot (NULL key) in the table.
127 To avoid slowing down lookups on a near-full table, we resize the table when
128 it's USABLE_FRACTION (currently two-thirds) full.
129 */
130
131 #define PERTURB_SHIFT 5
132
133 /*
134 Major subtleties ahead: Most hash schemes depend on having a "good" hash
135 function, in the sense of simulating randomness. Python doesn't: its most
136 important hash functions (for ints) are very regular in common
137 cases:
138
139 >>>[hash(i) for i in range(4)]
140 [0, 1, 2, 3]
141
142 This isn't necessarily bad! To the contrary, in a table of size 2**i, taking
143 the low-order i bits as the initial table index is extremely fast, and there
144 are no collisions at all for dicts indexed by a contiguous range of ints. So
145 this gives better-than-random behavior in common cases, and that's very
146 desirable.
147
148 OTOH, when collisions occur, the tendency to fill contiguous slices of the
149 hash table makes a good collision resolution strategy crucial. Taking only
150 the last i bits of the hash code is also vulnerable: for example, consider
151 the list [i << 16 for i in range(20000)] as a set of keys. Since ints are
152 their own hash codes, and this fits in a dict of size 2**15, the last 15 bits
153 of every hash code are all 0: they *all* map to the same table index.
154
155 But catering to unusual cases should not slow the usual ones, so we just take
156 the last i bits anyway. It's up to collision resolution to do the rest. If
157 we *usually* find the key we're looking for on the first try (and, it turns
158 out, we usually do -- the table load factor is kept under 2/3, so the odds
159 are solidly in our favor), then it makes best sense to keep the initial index
160 computation dirt cheap.
161
162 The first half of collision resolution is to visit table indices via this
163 recurrence:
164
165 j = ((5*j) + 1) mod 2**i
166
167 For any initial j in range(2**i), repeating that 2**i times generates each
168 int in range(2**i) exactly once (see any text on random-number generation for
169 proof). By itself, this doesn't help much: like linear probing (setting
170 j += 1, or j -= 1, on each loop trip), it scans the table entries in a fixed
171 order. This would be bad, except that's not the only thing we do, and it's
172 actually *good* in the common cases where hash keys are consecutive. In an
173 example that's really too small to make this entirely clear, for a table of
174 size 2**3 the order of indices is:
175
176 0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating]
177
178 If two things come in at index 5, the first place we look after is index 2,
179 not 6, so if another comes in at index 6 the collision at 5 didn't hurt it.
180 Linear probing is deadly in this case because there the fixed probe order
181 is the *same* as the order consecutive keys are likely to arrive. But it's
182 extremely unlikely hash codes will follow a 5*j+1 recurrence by accident,
183 and certain that consecutive hash codes do not.
184
185 The other half of the strategy is to get the other bits of the hash code
186 into play. This is done by initializing a (unsigned) vrbl "perturb" to the
187 full hash code, and changing the recurrence to:
188
189 perturb >>= PERTURB_SHIFT;
190 j = (5*j) + 1 + perturb;
191 use j % 2**i as the next table index;
192
193 Now the probe sequence depends (eventually) on every bit in the hash code,
194 and the pseudo-scrambling property of recurring on 5*j+1 is more valuable,
195 because it quickly magnifies small differences in the bits that didn't affect
196 the initial index. Note that because perturb is unsigned, if the recurrence
197 is executed often enough perturb eventually becomes and remains 0. At that
198 point (very rarely reached) the recurrence is on (just) 5*j+1 again, and
199 that's certain to find an empty slot eventually (since it generates every int
200 in range(2**i), and we make sure there's always at least one empty slot).
201
202 Selecting a good value for PERTURB_SHIFT is a balancing act. You want it
203 small so that the high bits of the hash code continue to affect the probe
204 sequence across iterations; but you want it large so that in really bad cases
205 the high-order hash bits have an effect on early iterations. 5 was "the
206 best" in minimizing total collisions across experiments Tim Peters ran (on
207 both normal and pathological cases), but 4 and 6 weren't significantly worse.
208
209 Historical: Reimer Behrends contributed the idea of using a polynomial-based
210 approach, using repeated multiplication by x in GF(2**n) where an irreducible
211 polynomial for each table size was chosen such that x was a primitive root.
212 Christian Tismer later extended that to use division by x instead, as an
213 efficient way to get the high bits of the hash code into play. This scheme
214 also gave excellent collision statistics, but was more expensive: two
215 if-tests were required inside the loop; computing "the next" index took about
216 the same number of operations but without as much potential parallelism
217 (e.g., computing 5*j can go on at the same time as computing 1+perturb in the
218 above, and then shifting perturb can be done while the table index is being
219 masked); and the PyDictObject struct required a member to hold the table's
220 polynomial. In Tim's experiments the current scheme ran faster, produced
221 equally good collision statistics, needed less code & used less memory.
222
223 */
224
225 /* forward declarations */
226 static Py_ssize_t lookdict(PyDictObject *mp, PyObject *key,
227 Py_hash_t hash, PyObject **value_addr);
228 static Py_ssize_t lookdict_unicode(PyDictObject *mp, PyObject *key,
229 Py_hash_t hash, PyObject **value_addr);
230 static Py_ssize_t
231 lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
232 Py_hash_t hash, PyObject **value_addr);
233 static Py_ssize_t lookdict_split(PyDictObject *mp, PyObject *key,
234 Py_hash_t hash, PyObject **value_addr);
235
236 static int dictresize(PyDictObject *mp, Py_ssize_t minused);
237
238 static PyObject* dict_iter(PyDictObject *dict);
239
240 /*Global counter used to set ma_version_tag field of dictionary.
241 * It is incremented each time that a dictionary is created and each
242 * time that a dictionary is modified. */
243 static uint64_t pydict_global_version = 0;
244
245 #define DICT_NEXT_VERSION() (++pydict_global_version)
246
247 /* Dictionary reuse scheme to save calls to malloc and free */
248 #ifndef PyDict_MAXFREELIST
249 #define PyDict_MAXFREELIST 80
250 #endif
251 static PyDictObject *free_list[PyDict_MAXFREELIST];
252 static int numfree = 0;
253 static PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST];
254 static int numfreekeys = 0;
255
256 #include "clinic/dictobject.c.h"
257
258 int
259 PyDict_ClearFreeList(void)
260 {
261 PyDictObject *op;
262 int ret = numfree + numfreekeys;
263 while (numfree) {
264 op = free_list[--numfree];
265 assert(PyDict_CheckExact(op));
266 PyObject_GC_Del(op);
267 }
268 while (numfreekeys) {
269 PyObject_FREE(keys_free_list[--numfreekeys]);
270 }
271 return ret;
272 }
273
274 /* Print summary info about the state of the optimized allocator */
275 void
276 _PyDict_DebugMallocStats(FILE *out)
277 {
278 _PyDebugAllocatorStats(out,
279 "free PyDictObject", numfree, sizeof(PyDictObject));
280 }
281
282
283 void
284 PyDict_Fini(void)
285 {
286 PyDict_ClearFreeList();
287 }
288
289 #define DK_SIZE(dk) ((dk)->dk_size)
290 #if SIZEOF_VOID_P > 4
291 #define DK_IXSIZE(dk) \
292 (DK_SIZE(dk) <= 0xff ? \
293 1 : DK_SIZE(dk) <= 0xffff ? \
294 2 : DK_SIZE(dk) <= 0xffffffff ? \
295 4 : sizeof(int64_t))
296 #else
297 #define DK_IXSIZE(dk) \
298 (DK_SIZE(dk) <= 0xff ? \
299 1 : DK_SIZE(dk) <= 0xffff ? \
300 2 : sizeof(int32_t))
301 #endif
302 #define DK_ENTRIES(dk) \
303 ((PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[DK_SIZE(dk) * DK_IXSIZE(dk)]))
304
305 #define DK_DEBUG_INCREF _Py_INC_REFTOTAL _Py_REF_DEBUG_COMMA
306 #define DK_DEBUG_DECREF _Py_DEC_REFTOTAL _Py_REF_DEBUG_COMMA
307
308 #define DK_INCREF(dk) (DK_DEBUG_INCREF ++(dk)->dk_refcnt)
309 #define DK_DECREF(dk) if (DK_DEBUG_DECREF (--(dk)->dk_refcnt) == 0) free_keys_object(dk)
310 #define DK_MASK(dk) (((dk)->dk_size)-1)
311 #define IS_POWER_OF_2(x) (((x) & (x-1)) == 0)
312
313 /* lookup indices. returns DKIX_EMPTY, DKIX_DUMMY, or ix >=0 */
314 static inline Py_ssize_t
315 dk_get_index(PyDictKeysObject *keys, Py_ssize_t i)
316 {
317 Py_ssize_t s = DK_SIZE(keys);
318 Py_ssize_t ix;
319
320 if (s <= 0xff) {
321 int8_t *indices = (int8_t*)(keys->dk_indices);
322 ix = indices[i];
323 }
324 else if (s <= 0xffff) {
325 int16_t *indices = (int16_t*)(keys->dk_indices);
326 ix = indices[i];
327 }
328 #if SIZEOF_VOID_P > 4
329 else if (s > 0xffffffff) {
330 int64_t *indices = (int64_t*)(keys->dk_indices);
331 ix = indices[i];
332 }
333 #endif
334 else {
335 int32_t *indices = (int32_t*)(keys->dk_indices);
336 ix = indices[i];
337 }
338 assert(ix >= DKIX_DUMMY);
339 return ix;
340 }
341
342 /* write to indices. */
343 static inline void
344 dk_set_index(PyDictKeysObject *keys, Py_ssize_t i, Py_ssize_t ix)
345 {
346 Py_ssize_t s = DK_SIZE(keys);
347
348 assert(ix >= DKIX_DUMMY);
349
350 if (s <= 0xff) {
351 int8_t *indices = (int8_t*)(keys->dk_indices);
352 assert(ix <= 0x7f);
353 indices[i] = (char)ix;
354 }
355 else if (s <= 0xffff) {
356 int16_t *indices = (int16_t*)(keys->dk_indices);
357 assert(ix <= 0x7fff);
358 indices[i] = (int16_t)ix;
359 }
360 #if SIZEOF_VOID_P > 4
361 else if (s > 0xffffffff) {
362 int64_t *indices = (int64_t*)(keys->dk_indices);
363 indices[i] = ix;
364 }
365 #endif
366 else {
367 int32_t *indices = (int32_t*)(keys->dk_indices);
368 assert(ix <= 0x7fffffff);
369 indices[i] = (int32_t)ix;
370 }
371 }
372
373
374 /* USABLE_FRACTION is the maximum dictionary load.
375 * Increasing this ratio makes dictionaries more dense resulting in more
376 * collisions. Decreasing it improves sparseness at the expense of spreading
377 * indices over more cache lines and at the cost of total memory consumed.
378 *
379 * USABLE_FRACTION must obey the following:
380 * (0 < USABLE_FRACTION(n) < n) for all n >= 2
381 *
382 * USABLE_FRACTION should be quick to calculate.
383 * Fractions around 1/2 to 2/3 seem to work well in practice.
384 */
385 #define USABLE_FRACTION(n) (((n) << 1)/3)
386
387 /* ESTIMATE_SIZE is reverse function of USABLE_FRACTION.
388 * This can be used to reserve enough size to insert n entries without
389 * resizing.
390 */
391 #define ESTIMATE_SIZE(n) (((n)*3+1) >> 1)
392
393 /* Alternative fraction that is otherwise close enough to 2n/3 to make
394 * little difference. 8 * 2/3 == 8 * 5/8 == 5. 16 * 2/3 == 16 * 5/8 == 10.
395 * 32 * 2/3 = 21, 32 * 5/8 = 20.
396 * Its advantage is that it is faster to compute on machines with slow division.
397 * #define USABLE_FRACTION(n) (((n) >> 1) + ((n) >> 2) - ((n) >> 3))
398 */
399
400 /* GROWTH_RATE. Growth rate upon hitting maximum load.
401 * Currently set to used*3.
402 * This means that dicts double in size when growing without deletions,
403 * but have more head room when the number of deletions is on a par with the
404 * number of insertions. See also bpo-17563 and bpo-33205.
405 *
406 * GROWTH_RATE was set to used*4 up to version 3.2.
407 * GROWTH_RATE was set to used*2 in version 3.3.0
408 * GROWTH_RATE was set to used*2 + capacity/2 in 3.4.0-3.6.0.
409 */
410 #define GROWTH_RATE(d) ((d)->ma_used*3)
411
412 #define ENSURE_ALLOWS_DELETIONS(d) \
413 if ((d)->ma_keys->dk_lookup == lookdict_unicode_nodummy) { \
414 (d)->ma_keys->dk_lookup = lookdict_unicode; \
415 }
416
417 /* This immutable, empty PyDictKeysObject is used for PyDict_Clear()
418 * (which cannot fail and thus can do no allocation).
419 */
420 static PyDictKeysObject empty_keys_struct = {
421 1, /* dk_refcnt */
422 1, /* dk_size */
423 lookdict_split, /* dk_lookup */
424 0, /* dk_usable (immutable) */
425 0, /* dk_nentries */
426 {DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY,
427 DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY}, /* dk_indices */
428 };
429
430 static PyObject *empty_values[1] = { NULL };
431
432 #define Py_EMPTY_KEYS &empty_keys_struct
433
434 /* Uncomment to check the dict content in _PyDict_CheckConsistency() */
435 /* #define DEBUG_PYDICT */
436
437
438 #ifndef NDEBUG
439 static int
440 _PyDict_CheckConsistency(PyDictObject *mp)
441 {
442 PyDictKeysObject *keys = mp->ma_keys;
443 int splitted = _PyDict_HasSplitTable(mp);
444 Py_ssize_t usable = USABLE_FRACTION(keys->dk_size);
445 #ifdef DEBUG_PYDICT
446 PyDictKeyEntry *entries = DK_ENTRIES(keys);
447 Py_ssize_t i;
448 #endif
449
450 assert(0 <= mp->ma_used && mp->ma_used <= usable);
451 assert(IS_POWER_OF_2(keys->dk_size));
452 assert(0 <= keys->dk_usable
453 && keys->dk_usable <= usable);
454 assert(0 <= keys->dk_nentries
455 && keys->dk_nentries <= usable);
456 assert(keys->dk_usable + keys->dk_nentries <= usable);
457
458 if (!splitted) {
459 /* combined table */
460 assert(keys->dk_refcnt == 1);
461 }
462
463 #ifdef DEBUG_PYDICT
464 for (i=0; i < keys->dk_size; i++) {
465 Py_ssize_t ix = dk_get_index(keys, i);
466 assert(DKIX_DUMMY <= ix && ix <= usable);
467 }
468
469 for (i=0; i < usable; i++) {
470 PyDictKeyEntry *entry = &entries[i];
471 PyObject *key = entry->me_key;
472
473 if (key != NULL) {
474 if (PyUnicode_CheckExact(key)) {
475 Py_hash_t hash = ((PyASCIIObject *)key)->hash;
476 assert(hash != -1);
477 assert(entry->me_hash == hash);
478 }
479 else {
480 /* test_dict fails if PyObject_Hash() is called again */
481 assert(entry->me_hash != -1);
482 }
483 if (!splitted) {
484 assert(entry->me_value != NULL);
485 }
486 }
487
488 if (splitted) {
489 assert(entry->me_value == NULL);
490 }
491 }
492
493 if (splitted) {
494 /* splitted table */
495 for (i=0; i < mp->ma_used; i++) {
496 assert(mp->ma_values[i] != NULL);
497 }
498 }
499 #endif
500
501 return 1;
502 }
503 #endif
504
505
506 static PyDictKeysObject *new_keys_object(Py_ssize_t size)
507 {
508 PyDictKeysObject *dk;
509 Py_ssize_t es, usable;
510
511 assert(size >= PyDict_MINSIZE);
512 assert(IS_POWER_OF_2(size));
513
514 usable = USABLE_FRACTION(size);
515 if (size <= 0xff) {
516 es = 1;
517 }
518 else if (size <= 0xffff) {
519 es = 2;
520 }
521 #if SIZEOF_VOID_P > 4
522 else if (size <= 0xffffffff) {
523 es = 4;
524 }
525 #endif
526 else {
527 es = sizeof(Py_ssize_t);
528 }
529
530 if (size == PyDict_MINSIZE && numfreekeys > 0) {
531 dk = keys_free_list[--numfreekeys];
532 }
533 else {
534 dk = PyObject_MALLOC(sizeof(PyDictKeysObject)
535 + es * size
536 + sizeof(PyDictKeyEntry) * usable);
537 if (dk == NULL) {
538 PyErr_NoMemory();
539 return NULL;
540 }
541 }
542 DK_DEBUG_INCREF dk->dk_refcnt = 1;
543 dk->dk_size = size;
544 dk->dk_usable = usable;
545 dk->dk_lookup = lookdict_unicode_nodummy;
546 dk->dk_nentries = 0;
547 memset(&dk->dk_indices[0], 0xff, es * size);
548 memset(DK_ENTRIES(dk), 0, sizeof(PyDictKeyEntry) * usable);
549 return dk;
550 }
551
552 static void
553 free_keys_object(PyDictKeysObject *keys)
554 {
555 PyDictKeyEntry *entries = DK_ENTRIES(keys);
556 Py_ssize_t i, n;
557 for (i = 0, n = keys->dk_nentries; i < n; i++) {
558 Py_XDECREF(entries[i].me_key);
559 Py_XDECREF(entries[i].me_value);
560 }
561 if (keys->dk_size == PyDict_MINSIZE && numfreekeys < PyDict_MAXFREELIST) {
562 keys_free_list[numfreekeys++] = keys;
563 return;
564 }
565 PyObject_FREE(keys);
566 }
567
568 #define new_values(size) PyMem_NEW(PyObject *, size)
569 #define free_values(values) PyMem_FREE(values)
570
571 /* Consumes a reference to the keys object */
572 static PyObject *
573 new_dict(PyDictKeysObject *keys, PyObject **values)
574 {
575 PyDictObject *mp;
576 assert(keys != NULL);
577 if (numfree) {
578 mp = free_list[--numfree];
579 assert (mp != NULL);
580 assert (Py_TYPE(mp) == &PyDict_Type);
581 _Py_NewReference((PyObject *)mp);
582 }
583 else {
584 mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
585 if (mp == NULL) {
586 DK_DECREF(keys);
587 free_values(values);
588 return NULL;
589 }
590 }
591 mp->ma_keys = keys;
592 mp->ma_values = values;
593 mp->ma_used = 0;
594 mp->ma_version_tag = DICT_NEXT_VERSION();
595 assert(_PyDict_CheckConsistency(mp));
596 return (PyObject *)mp;
597 }
598
599 /* Consumes a reference to the keys object */
600 static PyObject *
601 new_dict_with_shared_keys(PyDictKeysObject *keys)
602 {
603 PyObject **values;
604 Py_ssize_t i, size;
605
606 size = USABLE_FRACTION(DK_SIZE(keys));
607 values = new_values(size);
608 if (values == NULL) {
609 DK_DECREF(keys);
610 return PyErr_NoMemory();
611 }
612 for (i = 0; i < size; i++) {
613 values[i] = NULL;
614 }
615 return new_dict(keys, values);
616 }
617
618
619 static PyObject *
620 clone_combined_dict(PyDictObject *orig)
621 {
622 assert(PyDict_CheckExact(orig));
623 assert(orig->ma_values == NULL);
624 assert(orig->ma_keys->dk_refcnt == 1);
625
626 Py_ssize_t keys_size = _PyDict_KeysSize(orig->ma_keys);
627 PyDictKeysObject *keys = PyObject_Malloc(keys_size);
628 if (keys == NULL) {
629 PyErr_NoMemory();
630 return NULL;
631 }
632
633 memcpy(keys, orig->ma_keys, keys_size);
634
635 /* After copying key/value pairs, we need to incref all
636 keys and values and they are about to be co-owned by a
637 new dict object. */
638 PyDictKeyEntry *ep0 = DK_ENTRIES(keys);
639 Py_ssize_t n = keys->dk_nentries;
640 for (Py_ssize_t i = 0; i < n; i++) {
641 PyDictKeyEntry *entry = &ep0[i];
642 PyObject *value = entry->me_value;
643 if (value != NULL) {
644 Py_INCREF(value);
645 Py_INCREF(entry->me_key);
646 }
647 }
648
649 PyDictObject *new = (PyDictObject *)new_dict(keys, NULL);
650 if (new == NULL) {
651 /* In case of an error, `new_dict()` takes care of
652 cleaning up `keys`. */
653 return NULL;
654 }
655 new->ma_used = orig->ma_used;
656 assert(_PyDict_CheckConsistency(new));
657 if (_PyObject_GC_IS_TRACKED(orig)) {
658 /* Maintain tracking. */
659 _PyObject_GC_TRACK(new);
660 }
661
662 /* Since we copied the keys table we now have an extra reference
663 in the system. Manually call _Py_INC_REFTOTAL to signal that
664 we have it now; calling DK_INCREF would be an error as
665 keys->dk_refcnt is already set to 1 (after memcpy). */
666 _Py_INC_REFTOTAL;
667
668 return (PyObject *)new;
669 }
670
671 PyObject *
672 PyDict_New(void)
673 {
674 PyDictKeysObject *keys = new_keys_object(PyDict_MINSIZE);
675 if (keys == NULL)
676 return NULL;
677 return new_dict(keys, NULL);
678 }
679
680 /* Search index of hash table from offset of entry table */
681 static Py_ssize_t
682 lookdict_index(PyDictKeysObject *k, Py_hash_t hash, Py_ssize_t index)
683 {
684 size_t mask = DK_MASK(k);
685 size_t perturb = (size_t)hash;
686 size_t i = (size_t)hash & mask;
687
688 for (;;) {
689 Py_ssize_t ix = dk_get_index(k, i);
690 if (ix == index) {
691 return i;
692 }
693 if (ix == DKIX_EMPTY) {
694 return DKIX_EMPTY;
695 }
696 perturb >>= PERTURB_SHIFT;
697 i = mask & (i*5 + perturb + 1);
698 }
699 Py_UNREACHABLE();
700 }
701
702 /*
703 The basic lookup function used by all operations.
704 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
705 Open addressing is preferred over chaining since the link overhead for
706 chaining would be substantial (100% with typical malloc overhead).
707
708 The initial probe index is computed as hash mod the table size. Subsequent
709 probe indices are computed as explained earlier.
710
711 All arithmetic on hash should ignore overflow.
712
713 The details in this version are due to Tim Peters, building on many past
714 contributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and
715 Christian Tismer.
716
717 lookdict() is general-purpose, and may return DKIX_ERROR if (and only if) a
718 comparison raises an exception.
719 lookdict_unicode() below is specialized to string keys, comparison of which can
720 never raise an exception; that function can never return DKIX_ERROR when key
721 is string. Otherwise, it falls back to lookdict().
722 lookdict_unicode_nodummy is further specialized for string keys that cannot be
723 the <dummy> value.
724 For both, when the key isn't found a DKIX_EMPTY is returned.
725 */
726 static Py_ssize_t _Py_HOT_FUNCTION
727 lookdict(PyDictObject *mp, PyObject *key,
728 Py_hash_t hash, PyObject **value_addr)
729 {
730 size_t i, mask, perturb;
731 PyDictKeysObject *dk;
732 PyDictKeyEntry *ep0;
733
734 top:
735 dk = mp->ma_keys;
736 ep0 = DK_ENTRIES(dk);
737 mask = DK_MASK(dk);
738 perturb = hash;
739 i = (size_t)hash & mask;
740
741 for (;;) {
742 Py_ssize_t ix = dk_get_index(dk, i);
743 if (ix == DKIX_EMPTY) {
744 *value_addr = NULL;
745 return ix;
746 }
747 if (ix >= 0) {
748 PyDictKeyEntry *ep = &ep0[ix];
749 assert(ep->me_key != NULL);
750 if (ep->me_key == key) {
751 *value_addr = ep->me_value;
752 return ix;
753 }
754 if (ep->me_hash == hash) {
755 PyObject *startkey = ep->me_key;
756 Py_INCREF(startkey);
757 int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
758 Py_DECREF(startkey);
759 if (cmp < 0) {
760 *value_addr = NULL;
761 return DKIX_ERROR;
762 }
763 if (dk == mp->ma_keys && ep->me_key == startkey) {
764 if (cmp > 0) {
765 *value_addr = ep->me_value;
766 return ix;
767 }
768 }
769 else {
770 /* The dict was mutated, restart */
771 goto top;
772 }
773 }
774 }
775 perturb >>= PERTURB_SHIFT;
776 i = (i*5 + perturb + 1) & mask;
777 }
778 Py_UNREACHABLE();
779 }
780
781 /* Specialized version for string-only keys */
782 static Py_ssize_t _Py_HOT_FUNCTION
783 lookdict_unicode(PyDictObject *mp, PyObject *key,
784 Py_hash_t hash, PyObject **value_addr)
785 {
786 assert(mp->ma_values == NULL);
787 /* Make sure this function doesn't have to handle non-unicode keys,
788 including subclasses of str; e.g., one reason to subclass
789 unicodes is to override __eq__, and for speed we don't cater to
790 that here. */
791 if (!PyUnicode_CheckExact(key)) {
792 mp->ma_keys->dk_lookup = lookdict;
793 return lookdict(mp, key, hash, value_addr);
794 }
795
796 PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
797 size_t mask = DK_MASK(mp->ma_keys);
798 size_t perturb = (size_t)hash;
799 size_t i = (size_t)hash & mask;
800
801 for (;;) {
802 Py_ssize_t ix = dk_get_index(mp->ma_keys, i);
803 if (ix == DKIX_EMPTY) {
804 *value_addr = NULL;
805 return DKIX_EMPTY;
806 }
807 if (ix >= 0) {
808 PyDictKeyEntry *ep = &ep0[ix];
809 assert(ep->me_key != NULL);
810 assert(PyUnicode_CheckExact(ep->me_key));
811 if (ep->me_key == key ||
812 (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
813 *value_addr = ep->me_value;
814 return ix;
815 }
816 }
817 perturb >>= PERTURB_SHIFT;
818 i = mask & (i*5 + perturb + 1);
819 }
820 Py_UNREACHABLE();
821 }
822
823 /* Faster version of lookdict_unicode when it is known that no <dummy> keys
824 * will be present. */
825 static Py_ssize_t _Py_HOT_FUNCTION
826 lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
827 Py_hash_t hash, PyObject **value_addr)
828 {
829 assert(mp->ma_values == NULL);
830 /* Make sure this function doesn't have to handle non-unicode keys,
831 including subclasses of str; e.g., one reason to subclass
832 unicodes is to override __eq__, and for speed we don't cater to
833 that here. */
834 if (!PyUnicode_CheckExact(key)) {
835 mp->ma_keys->dk_lookup = lookdict;
836 return lookdict(mp, key, hash, value_addr);
837 }
838
839 PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
840 size_t mask = DK_MASK(mp->ma_keys);
841 size_t perturb = (size_t)hash;
842 size_t i = (size_t)hash & mask;
843
844 for (;;) {
845 Py_ssize_t ix = dk_get_index(mp->ma_keys, i);
846 assert (ix != DKIX_DUMMY);
847 if (ix == DKIX_EMPTY) {
848 *value_addr = NULL;
849 return DKIX_EMPTY;
850 }
851 PyDictKeyEntry *ep = &ep0[ix];
852 assert(ep->me_key != NULL);
853 assert(PyUnicode_CheckExact(ep->me_key));
854 if (ep->me_key == key ||
855 (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
856 *value_addr = ep->me_value;
857 return ix;
858 }
859 perturb >>= PERTURB_SHIFT;
860 i = mask & (i*5 + perturb + 1);
861 }
862 Py_UNREACHABLE();
863 }
864
865 /* Version of lookdict for split tables.
866 * All split tables and only split tables use this lookup function.
867 * Split tables only contain unicode keys and no dummy keys,
868 * so algorithm is the same as lookdict_unicode_nodummy.
869 */
870 static Py_ssize_t _Py_HOT_FUNCTION
871 lookdict_split(PyDictObject *mp, PyObject *key,
872 Py_hash_t hash, PyObject **value_addr)
873 {
874 /* mp must split table */
875 assert(mp->ma_values != NULL);
876 if (!PyUnicode_CheckExact(key)) {
877 Py_ssize_t ix = lookdict(mp, key, hash, value_addr);
878 if (ix >= 0) {
879 *value_addr = mp->ma_values[ix];
880 }
881 return ix;
882 }
883
884 PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
885 size_t mask = DK_MASK(mp->ma_keys);
886 size_t perturb = (size_t)hash;
887 size_t i = (size_t)hash & mask;
888
889 for (;;) {
890 Py_ssize_t ix = dk_get_index(mp->ma_keys, i);
891 assert (ix != DKIX_DUMMY);
892 if (ix == DKIX_EMPTY) {
893 *value_addr = NULL;
894 return DKIX_EMPTY;
895 }
896 PyDictKeyEntry *ep = &ep0[ix];
897 assert(ep->me_key != NULL);
898 assert(PyUnicode_CheckExact(ep->me_key));
899 if (ep->me_key == key ||
900 (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
901 *value_addr = mp->ma_values[ix];
902 return ix;
903 }
904 perturb >>= PERTURB_SHIFT;
905 i = mask & (i*5 + perturb + 1);
906 }
907 Py_UNREACHABLE();
908 }
909
910 int
911 _PyDict_HasOnlyStringKeys(PyObject *dict)
912 {
913 Py_ssize_t pos = 0;
914 PyObject *key, *value;
915 assert(PyDict_Check(dict));
916 /* Shortcut */
917 if (((PyDictObject *)dict)->ma_keys->dk_lookup != lookdict)
918 return 1;
919 while (PyDict_Next(dict, &pos, &key, &value))
920 if (!PyUnicode_Check(key))
921 return 0;
922 return 1;
923 }
924
925 #define MAINTAIN_TRACKING(mp, key, value) \
926 do { \
927 if (!_PyObject_GC_IS_TRACKED(mp)) { \
928 if (_PyObject_GC_MAY_BE_TRACKED(key) || \
929 _PyObject_GC_MAY_BE_TRACKED(value)) { \
930 _PyObject_GC_TRACK(mp); \
931 } \
932 } \
933 } while(0)
934
935 void
936 _PyDict_MaybeUntrack(PyObject *op)
937 {
938 PyDictObject *mp;
939 PyObject *value;
940 Py_ssize_t i, numentries;
941 PyDictKeyEntry *ep0;
942
943 if (!PyDict_CheckExact(op) || !_PyObject_GC_IS_TRACKED(op))
944 return;
945
946 mp = (PyDictObject *) op;
947 ep0 = DK_ENTRIES(mp->ma_keys);
948 numentries = mp->ma_keys->dk_nentries;
949 if (_PyDict_HasSplitTable(mp)) {
950 for (i = 0; i < numentries; i++) {
951 if ((value = mp->ma_values[i]) == NULL)
952 continue;
953 if (_PyObject_GC_MAY_BE_TRACKED(value)) {
954 assert(!_PyObject_GC_MAY_BE_TRACKED(ep0[i].me_key));
955 return;
956 }
957 }
958 }
959 else {
960 for (i = 0; i < numentries; i++) {
961 if ((value = ep0[i].me_value) == NULL)
962 continue;
963 if (_PyObject_GC_MAY_BE_TRACKED(value) ||
964 _PyObject_GC_MAY_BE_TRACKED(ep0[i].me_key))
965 return;
966 }
967 }
968 _PyObject_GC_UNTRACK(op);
969 }
970
971 /* Internal function to find slot for an item from its hash
972 when it is known that the key is not present in the dict.
973
974 The dict must be combined. */
975 static Py_ssize_t
976 find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash)
977 {
978 assert(keys != NULL);
979
980 const size_t mask = DK_MASK(keys);
981 size_t i = hash & mask;
982 Py_ssize_t ix = dk_get_index(keys, i);
983 for (size_t perturb = hash; ix >= 0;) {
984 perturb >>= PERTURB_SHIFT;
985 i = (i*5 + perturb + 1) & mask;
986 ix = dk_get_index(keys, i);
987 }
988 return i;
989 }
990
991 static int
992 insertion_resize(PyDictObject *mp)
993 {
994 return dictresize(mp, GROWTH_RATE(mp));
995 }
996
997 /*
998 Internal routine to insert a new item into the table.
999 Used both by the internal resize routine and by the public insert routine.
1000 Returns -1 if an error occurred, or 0 on success.
1001 */
1002 static int
1003 insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
1004 {
1005 PyObject *old_value;
1006 PyDictKeyEntry *ep;
1007
1008 Py_INCREF(key);
1009 Py_INCREF(value);
1010 if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {
1011 if (insertion_resize(mp) < 0)
1012 goto Fail;
1013 }
1014
1015 Py_ssize_t ix = mp->ma_keys->dk_lookup(mp, key, hash, &old_value);
1016 if (ix == DKIX_ERROR)
1017 goto Fail;
1018
1019 assert(PyUnicode_CheckExact(key) || mp->ma_keys->dk_lookup == lookdict);
1020 MAINTAIN_TRACKING(mp, key, value);
1021
1022 /* When insertion order is different from shared key, we can't share
1023 * the key anymore. Convert this instance to combine table.
1024 */
1025 if (_PyDict_HasSplitTable(mp) &&
1026 ((ix >= 0 && old_value == NULL && mp->ma_used != ix) ||
1027 (ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) {
1028 if (insertion_resize(mp) < 0)
1029 goto Fail;
1030 ix = DKIX_EMPTY;
1031 }
1032
1033 if (ix == DKIX_EMPTY) {
1034 /* Insert into new slot. */
1035 assert(old_value == NULL);
1036 if (mp->ma_keys->dk_usable <= 0) {
1037 /* Need to resize. */
1038 if (insertion_resize(mp) < 0)
1039 goto Fail;
1040 }
1041 Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
1042 ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
1043 dk_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
1044 ep->me_key = key;
1045 ep->me_hash = hash;
1046 if (mp->ma_values) {
1047 assert (mp->ma_values[mp->ma_keys->dk_nentries] == NULL);
1048 mp->ma_values[mp->ma_keys->dk_nentries] = value;
1049 }
1050 else {
1051 ep->me_value = value;
1052 }
1053 mp->ma_used++;
1054 mp->ma_version_tag = DICT_NEXT_VERSION();
1055 mp->ma_keys->dk_usable--;
1056 mp->ma_keys->dk_nentries++;
1057 assert(mp->ma_keys->dk_usable >= 0);
1058 assert(_PyDict_CheckConsistency(mp));
1059 return 0;
1060 }
1061
1062 if (_PyDict_HasSplitTable(mp)) {
1063 mp->ma_values[ix] = value;
1064 if (old_value == NULL) {
1065 /* pending state */
1066 assert(ix == mp->ma_used);
1067 mp->ma_used++;
1068 }
1069 }
1070 else {
1071 assert(old_value != NULL);
1072 DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
1073 }
1074
1075 mp->ma_version_tag = DICT_NEXT_VERSION();
1076 Py_XDECREF(old_value); /* which **CAN** re-enter (see issue #22653) */
1077 assert(_PyDict_CheckConsistency(mp));
1078 Py_DECREF(key);
1079 return 0;
1080
1081 Fail:
1082 Py_DECREF(value);
1083 Py_DECREF(key);
1084 return -1;
1085 }
1086
1087 /*
1088 Internal routine used by dictresize() to build a hashtable of entries.
1089 */
1090 static void
1091 build_indices(PyDictKeysObject *keys, PyDictKeyEntry *ep, Py_ssize_t n)
1092 {
1093 size_t mask = (size_t)DK_SIZE(keys) - 1;
1094 for (Py_ssize_t ix = 0; ix != n; ix++, ep++) {
1095 Py_hash_t hash = ep->me_hash;
1096 size_t i = hash & mask;
1097 for (size_t perturb = hash; dk_get_index(keys, i) != DKIX_EMPTY;) {
1098 perturb >>= PERTURB_SHIFT;
1099 i = mask & (i*5 + perturb + 1);
1100 }
1101 dk_set_index(keys, i, ix);
1102 }
1103 }
1104
1105 /*
1106 Restructure the table by allocating a new table and reinserting all
1107 items again. When entries have been deleted, the new table may
1108 actually be smaller than the old one.
1109 If a table is split (its keys and hashes are shared, its values are not),
1110 then the values are temporarily copied into the table, it is resized as
1111 a combined table, then the me_value slots in the old table are NULLed out.
1112 After resizing a table is always combined,
1113 but can be resplit by make_keys_shared().
1114 */
1115 static int
1116 dictresize(PyDictObject *mp, Py_ssize_t minsize)
1117 {
1118 Py_ssize_t newsize, numentries;
1119 PyDictKeysObject *oldkeys;
1120 PyObject **oldvalues;
1121 PyDictKeyEntry *oldentries, *newentries;
1122
1123 /* Find the smallest table size > minused. */
1124 for (newsize = PyDict_MINSIZE;
1125 newsize < minsize && newsize > 0;
1126 newsize <<= 1)
1127 ;
1128 if (newsize <= 0) {
1129 PyErr_NoMemory();
1130 return -1;
1131 }
1132
1133 oldkeys = mp->ma_keys;
1134
1135 /* NOTE: Current odict checks mp->ma_keys to detect resize happen.
1136 * So we can't reuse oldkeys even if oldkeys->dk_size == newsize.
1137 * TODO: Try reusing oldkeys when reimplement odict.
1138 */
1139
1140 /* Allocate a new table. */
1141 mp->ma_keys = new_keys_object(newsize);
1142 if (mp->ma_keys == NULL) {
1143 mp->ma_keys = oldkeys;
1144 return -1;
1145 }
1146 // New table must be large enough.
1147 assert(mp->ma_keys->dk_usable >= mp->ma_used);
1148 if (oldkeys->dk_lookup == lookdict)
1149 mp->ma_keys->dk_lookup = lookdict;
1150
1151 numentries = mp->ma_used;
1152 oldentries = DK_ENTRIES(oldkeys);
1153 newentries = DK_ENTRIES(mp->ma_keys);
1154 oldvalues = mp->ma_values;
1155 if (oldvalues != NULL) {
1156 /* Convert split table into new combined table.
1157 * We must incref keys; we can transfer values.
1158 * Note that values of split table is always dense.
1159 */
1160 for (Py_ssize_t i = 0; i < numentries; i++) {
1161 assert(oldvalues[i] != NULL);
1162 PyDictKeyEntry *ep = &oldentries[i];
1163 PyObject *key = ep->me_key;
1164 Py_INCREF(key);
1165 newentries[i].me_key = key;
1166 newentries[i].me_hash = ep->me_hash;
1167 newentries[i].me_value = oldvalues[i];
1168 }
1169
1170 DK_DECREF(oldkeys);
1171 mp->ma_values = NULL;
1172 if (oldvalues != empty_values) {
1173 free_values(oldvalues);
1174 }
1175 }
1176 else { // combined table.
1177 if (oldkeys->dk_nentries == numentries) {
1178 memcpy(newentries, oldentries, numentries * sizeof(PyDictKeyEntry));
1179 }
1180 else {
1181 PyDictKeyEntry *ep = oldentries;
1182 for (Py_ssize_t i = 0; i < numentries; i++) {
1183 while (ep->me_value == NULL)
1184 ep++;
1185 newentries[i] = *ep++;
1186 }
1187 }
1188
1189 assert(oldkeys->dk_lookup != lookdict_split);
1190 assert(oldkeys->dk_refcnt == 1);
1191 if (oldkeys->dk_size == PyDict_MINSIZE &&
1192 numfreekeys < PyDict_MAXFREELIST) {
1193 DK_DEBUG_DECREF keys_free_list[numfreekeys++] = oldkeys;
1194 }
1195 else {
1196 DK_DEBUG_DECREF PyObject_FREE(oldkeys);
1197 }
1198 }
1199
1200 build_indices(mp->ma_keys, newentries, numentries);
1201 mp->ma_keys->dk_usable -= numentries;
1202 mp->ma_keys->dk_nentries = numentries;
1203 return 0;
1204 }
1205
1206 /* Returns NULL if unable to split table.
1207 * A NULL return does not necessarily indicate an error */
1208 static PyDictKeysObject *
1209 make_keys_shared(PyObject *op)
1210 {
1211 Py_ssize_t i;
1212 Py_ssize_t size;
1213 PyDictObject *mp = (PyDictObject *)op;
1214
1215 if (!PyDict_CheckExact(op))
1216 return NULL;
1217 if (!_PyDict_HasSplitTable(mp)) {
1218 PyDictKeyEntry *ep0;
1219 PyObject **values;
1220 assert(mp->ma_keys->dk_refcnt == 1);
1221 if (mp->ma_keys->dk_lookup == lookdict) {
1222 return NULL;
1223 }
1224 else if (mp->ma_keys->dk_lookup == lookdict_unicode) {
1225 /* Remove dummy keys */
1226 if (dictresize(mp, DK_SIZE(mp->ma_keys)))
1227 return NULL;
1228 }
1229 assert(mp->ma_keys->dk_lookup == lookdict_unicode_nodummy);
1230 /* Copy values into a new array */
1231 ep0 = DK_ENTRIES(mp->ma_keys);
1232 size = USABLE_FRACTION(DK_SIZE(mp->ma_keys));
1233 values = new_values(size);
1234 if (values == NULL) {
1235 PyErr_SetString(PyExc_MemoryError,
1236 "Not enough memory to allocate new values array");
1237 return NULL;
1238 }
1239 for (i = 0; i < size; i++) {
1240 values[i] = ep0[i].me_value;
1241 ep0[i].me_value = NULL;
1242 }
1243 mp->ma_keys->dk_lookup = lookdict_split;
1244 mp->ma_values = values;
1245 }
1246 DK_INCREF(mp->ma_keys);
1247 return mp->ma_keys;
1248 }
1249
1250 PyObject *
1251 _PyDict_NewPresized(Py_ssize_t minused)
1252 {
1253 const Py_ssize_t max_presize = 128 * 1024;
1254 Py_ssize_t newsize;
1255 PyDictKeysObject *new_keys;
1256
1257 /* There are no strict guarantee that returned dict can contain minused
1258 * items without resize. So we create medium size dict instead of very
1259 * large dict or MemoryError.
1260 */
1261 if (minused > USABLE_FRACTION(max_presize)) {
1262 newsize = max_presize;
1263 }
1264 else {
1265 Py_ssize_t minsize = ESTIMATE_SIZE(minused);
1266 newsize = PyDict_MINSIZE;
1267 while (newsize < minsize) {
1268 newsize <<= 1;
1269 }
1270 }
1271 assert(IS_POWER_OF_2(newsize));
1272
1273 new_keys = new_keys_object(newsize);
1274 if (new_keys == NULL)
1275 return NULL;
1276 return new_dict(new_keys, NULL);
1277 }
1278
1279 /* Note that, for historical reasons, PyDict_GetItem() suppresses all errors
1280 * that may occur (originally dicts supported only string keys, and exceptions
1281 * weren't possible). So, while the original intent was that a NULL return
1282 * meant the key wasn't present, in reality it can mean that, or that an error
1283 * (suppressed) occurred while computing the key's hash, or that some error
1284 * (suppressed) occurred when comparing keys in the dict's internal probe
1285 * sequence. A nasty example of the latter is when a Python-coded comparison
1286 * function hits a stack-depth error, which can cause this to return NULL
1287 * even if the key is present.
1288 */
1289 PyObject *
1290 PyDict_GetItem(PyObject *op, PyObject *key)
1291 {
1292 Py_hash_t hash;
1293 Py_ssize_t ix;
1294 PyDictObject *mp = (PyDictObject *)op;
1295 PyThreadState *tstate;
1296 PyObject *value;
1297
1298 if (!PyDict_Check(op))
1299 return NULL;
1300 if (!PyUnicode_CheckExact(key) ||
1301 (hash = ((PyASCIIObject *) key)->hash) == -1)
1302 {
1303 hash = PyObject_Hash(key);
1304 if (hash == -1) {
1305 PyErr_Clear();
1306 return NULL;
1307 }
1308 }
1309
1310 /* We can arrive here with a NULL tstate during initialization: try
1311 running "python -Wi" for an example related to string interning.
1312 Let's just hope that no exception occurs then... This must be
1313 _PyThreadState_Current and not PyThreadState_GET() because in debug
1314 mode, the latter complains if tstate is NULL. */
1315 tstate = PyThreadState_GET();
1316 if (tstate != NULL && tstate->curexc_type != NULL) {
1317 /* preserve the existing exception */
1318 PyObject *err_type, *err_value, *err_tb;
1319 PyErr_Fetch(&err_type, &err_value, &err_tb);
1320 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
1321 /* ignore errors */
1322 PyErr_Restore(err_type, err_value, err_tb);
1323 if (ix < 0)
1324 return NULL;
1325 }
1326 else {
1327 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
1328 if (ix < 0) {
1329 PyErr_Clear();
1330 return NULL;
1331 }
1332 }
1333 return value;
1334 }
1335
1336 /* Same as PyDict_GetItemWithError() but with hash supplied by caller.
1337 This returns NULL *with* an exception set if an exception occurred.
1338 It returns NULL *without* an exception set if the key wasn't present.
1339 */
1340 PyObject *
1341 _PyDict_GetItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
1342 {
1343 Py_ssize_t ix;
1344 PyDictObject *mp = (PyDictObject *)op;
1345 PyObject *value;
1346
1347 if (!PyDict_Check(op)) {
1348 PyErr_BadInternalCall();
1349 return NULL;
1350 }
1351
1352 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
1353 if (ix < 0) {
1354 return NULL;
1355 }
1356 return value;
1357 }
1358
1359 /* Variant of PyDict_GetItem() that doesn't suppress exceptions.
1360 This returns NULL *with* an exception set if an exception occurred.
1361 It returns NULL *without* an exception set if the key wasn't present.
1362 */
1363 PyObject *
1364 PyDict_GetItemWithError(PyObject *op, PyObject *key)
1365 {
1366 Py_ssize_t ix;
1367 Py_hash_t hash;
1368 PyDictObject*mp = (PyDictObject *)op;
1369 PyObject *value;
1370
1371 if (!PyDict_Check(op)) {
1372 PyErr_BadInternalCall();
1373 return NULL;
1374 }
1375 if (!PyUnicode_CheckExact(key) ||
1376 (hash = ((PyASCIIObject *) key)->hash) == -1)
1377 {
1378 hash = PyObject_Hash(key);
1379 if (hash == -1) {
1380 return NULL;
1381 }
1382 }
1383
1384 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
1385 if (ix < 0)
1386 return NULL;
1387 return value;
1388 }
1389
1390 PyObject *
1391 _PyDict_GetItemIdWithError(PyObject *dp, struct _Py_Identifier *key)
1392 {
1393 PyObject *kv;
1394 kv = _PyUnicode_FromId(key); /* borrowed */
1395 if (kv == NULL)
1396 return NULL;
1397 return PyDict_GetItemWithError(dp, kv);
1398 }
1399
1400 /* Fast version of global value lookup (LOAD_GLOBAL).
1401 * Lookup in globals, then builtins.
1402 *
1403 * Raise an exception and return NULL if an error occurred (ex: computing the
1404 * key hash failed, key comparison failed, ...). Return NULL if the key doesn't
1405 * exist. Return the value if the key exists.
1406 */
1407 PyObject *
1408 _PyDict_LoadGlobal(PyDictObject *globals, PyDictObject *builtins, PyObject *key)
1409 {
1410 Py_ssize_t ix;
1411 Py_hash_t hash;
1412 PyObject *value;
1413
1414 if (!PyUnicode_CheckExact(key) ||
1415 (hash = ((PyASCIIObject *) key)->hash) == -1)
1416 {
1417 hash = PyObject_Hash(key);
1418 if (hash == -1)
1419 return NULL;
1420 }
1421
1422 /* namespace 1: globals */
1423 ix = globals->ma_keys->dk_lookup(globals, key, hash, &value);
1424 if (ix == DKIX_ERROR)
1425 return NULL;
1426 if (ix != DKIX_EMPTY && value != NULL)
1427 return value;
1428
1429 /* namespace 2: builtins */
1430 ix = builtins->ma_keys->dk_lookup(builtins, key, hash, &value);
1431 if (ix < 0)
1432 return NULL;
1433 return value;
1434 }
1435
1436 /* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
1437 * dictionary if it's merely replacing the value for an existing key.
1438 * This means that it's safe to loop over a dictionary with PyDict_Next()
1439 * and occasionally replace a value -- but you can't insert new keys or
1440 * remove them.
1441 */
1442 int
1443 PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
1444 {
1445 PyDictObject *mp;
1446 Py_hash_t hash;
1447 if (!PyDict_Check(op)) {
1448 PyErr_BadInternalCall();
1449 return -1;
1450 }
1451 assert(key);
1452 assert(value);
1453 mp = (PyDictObject *)op;
1454 if (!PyUnicode_CheckExact(key) ||
1455 (hash = ((PyASCIIObject *) key)->hash) == -1)
1456 {
1457 hash = PyObject_Hash(key);
1458 if (hash == -1)
1459 return -1;
1460 }
1461
1462 /* insertdict() handles any resizing that might be necessary */
1463 return insertdict(mp, key, hash, value);
1464 }
1465
1466 int
1467 _PyDict_SetItem_KnownHash(PyObject *op, PyObject *key, PyObject *value,
1468 Py_hash_t hash)
1469 {
1470 PyDictObject *mp;
1471
1472 if (!PyDict_Check(op)) {
1473 PyErr_BadInternalCall();
1474 return -1;
1475 }
1476 assert(key);
1477 assert(value);
1478 assert(hash != -1);
1479 mp = (PyDictObject *)op;
1480
1481 /* insertdict() handles any resizing that might be necessary */
1482 return insertdict(mp, key, hash, value);
1483 }
1484
1485 static int
1486 delitem_common(PyDictObject *mp, Py_hash_t hash, Py_ssize_t ix,
1487 PyObject *old_value)
1488 {
1489 PyObject *old_key;
1490 PyDictKeyEntry *ep;
1491
1492 Py_ssize_t hashpos = lookdict_index(mp->ma_keys, hash, ix);
1493 assert(hashpos >= 0);
1494
1495 mp->ma_used--;
1496 mp->ma_version_tag = DICT_NEXT_VERSION();
1497 ep = &DK_ENTRIES(mp->ma_keys)[ix];
1498 dk_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
1499 ENSURE_ALLOWS_DELETIONS(mp);
1500 old_key = ep->me_key;
1501 ep->me_key = NULL;
1502 ep->me_value = NULL;
1503 Py_DECREF(old_key);
1504 Py_DECREF(old_value);
1505
1506 assert(_PyDict_CheckConsistency(mp));
1507 return 0;
1508 }
1509
1510 int
1511 PyDict_DelItem(PyObject *op, PyObject *key)
1512 {
1513 Py_hash_t hash;
1514 assert(key);
1515 if (!PyUnicode_CheckExact(key) ||
1516 (hash = ((PyASCIIObject *) key)->hash) == -1) {
1517 hash = PyObject_Hash(key);
1518 if (hash == -1)
1519 return -1;
1520 }
1521
1522 return _PyDict_DelItem_KnownHash(op, key, hash);
1523 }
1524
1525 int
1526 _PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
1527 {
1528 Py_ssize_t ix;
1529 PyDictObject *mp;
1530 PyObject *old_value;
1531
1532 if (!PyDict_Check(op)) {
1533 PyErr_BadInternalCall();
1534 return -1;
1535 }
1536 assert(key);
1537 assert(hash != -1);
1538 mp = (PyDictObject *)op;
1539 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
1540 if (ix == DKIX_ERROR)
1541 return -1;
1542 if (ix == DKIX_EMPTY || old_value == NULL) {
1543 _PyErr_SetKeyError(key);
1544 return -1;
1545 }
1546
1547 // Split table doesn't allow deletion. Combine it.
1548 if (_PyDict_HasSplitTable(mp)) {
1549 if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
1550 return -1;
1551 }
1552 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
1553 assert(ix >= 0);
1554 }
1555
1556 return delitem_common(mp, hash, ix, old_value);
1557 }
1558
1559 /* This function promises that the predicate -> deletion sequence is atomic
1560 * (i.e. protected by the GIL), assuming the predicate itself doesn't
1561 * release the GIL.
1562 */
1563 int
1564 _PyDict_DelItemIf(PyObject *op, PyObject *key,
1565 int (*predicate)(PyObject *value))
1566 {
1567 Py_ssize_t hashpos, ix;
1568 PyDictObject *mp;
1569 Py_hash_t hash;
1570 PyObject *old_value;
1571 int res;
1572
1573 if (!PyDict_Check(op)) {
1574 PyErr_BadInternalCall();
1575 return -1;
1576 }
1577 assert(key);
1578 hash = PyObject_Hash(key);
1579 if (hash == -1)
1580 return -1;
1581 mp = (PyDictObject *)op;
1582 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
1583 if (ix == DKIX_ERROR)
1584 return -1;
1585 if (ix == DKIX_EMPTY || old_value == NULL) {
1586 _PyErr_SetKeyError(key);
1587 return -1;
1588 }
1589
1590 // Split table doesn't allow deletion. Combine it.
1591 if (_PyDict_HasSplitTable(mp)) {
1592 if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
1593 return -1;
1594 }
1595 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
1596 assert(ix >= 0);
1597 }
1598
1599 res = predicate(old_value);
1600 if (res == -1)
1601 return -1;
1602
1603 hashpos = lookdict_index(mp->ma_keys, hash, ix);
1604 assert(hashpos >= 0);
1605
1606 if (res > 0)
1607 return delitem_common(mp, hashpos, ix, old_value);
1608 else
1609 return 0;
1610 }
1611
1612
1613 void
1614 PyDict_Clear(PyObject *op)
1615 {
1616 PyDictObject *mp;
1617 PyDictKeysObject *oldkeys;
1618 PyObject **oldvalues;
1619 Py_ssize_t i, n;
1620
1621 if (!PyDict_Check(op))
1622 return;
1623 mp = ((PyDictObject *)op);
1624 oldkeys = mp->ma_keys;
1625 oldvalues = mp->ma_values;
1626 if (oldvalues == empty_values)
1627 return;
1628 /* Empty the dict... */
1629 DK_INCREF(Py_EMPTY_KEYS);
1630 mp->ma_keys = Py_EMPTY_KEYS;
1631 mp->ma_values = empty_values;
1632 mp->ma_used = 0;
1633 mp->ma_version_tag = DICT_NEXT_VERSION();
1634 /* ...then clear the keys and values */
1635 if (oldvalues != NULL) {
1636 n = oldkeys->dk_nentries;
1637 for (i = 0; i < n; i++)
1638 Py_CLEAR(oldvalues[i]);
1639 free_values(oldvalues);
1640 DK_DECREF(oldkeys);
1641 }
1642 else {
1643 assert(oldkeys->dk_refcnt == 1);
1644 DK_DECREF(oldkeys);
1645 }
1646 assert(_PyDict_CheckConsistency(mp));
1647 }
1648
1649 /* Internal version of PyDict_Next that returns a hash value in addition
1650 * to the key and value.
1651 * Return 1 on success, return 0 when the reached the end of the dictionary
1652 * (or if op is not a dictionary)
1653 */
1654 int
1655 _PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey,
1656 PyObject **pvalue, Py_hash_t *phash)
1657 {
1658 Py_ssize_t i;
1659 PyDictObject *mp;
1660 PyDictKeyEntry *entry_ptr;
1661 PyObject *value;
1662
1663 if (!PyDict_Check(op))
1664 return 0;
1665 mp = (PyDictObject *)op;
1666 i = *ppos;
1667 if (mp->ma_values) {
1668 if (i < 0 || i >= mp->ma_used)
1669 return 0;
1670 /* values of split table is always dense */
1671 entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
1672 value = mp->ma_values[i];
1673 assert(value != NULL);
1674 }
1675 else {
1676 Py_ssize_t n = mp->ma_keys->dk_nentries;
1677 if (i < 0 || i >= n)
1678 return 0;
1679 entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
1680 while (i < n && entry_ptr->me_value == NULL) {
1681 entry_ptr++;
1682 i++;
1683 }
1684 if (i >= n)
1685 return 0;
1686 value = entry_ptr->me_value;
1687 }
1688 *ppos = i+1;
1689 if (pkey)
1690 *pkey = entry_ptr->me_key;
1691 if (phash)
1692 *phash = entry_ptr->me_hash;
1693 if (pvalue)
1694 *pvalue = value;
1695 return 1;
1696 }
1697
1698 /*
1699 * Iterate over a dict. Use like so:
1700 *
1701 * Py_ssize_t i;
1702 * PyObject *key, *value;
1703 * i = 0; # important! i should not otherwise be changed by you
1704 * while (PyDict_Next(yourdict, &i, &key, &value)) {
1705 * Refer to borrowed references in key and value.
1706 * }
1707 *
1708 * Return 1 on success, return 0 when the reached the end of the dictionary
1709 * (or if op is not a dictionary)
1710 *
1711 * CAUTION: In general, it isn't safe to use PyDict_Next in a loop that
1712 * mutates the dict. One exception: it is safe if the loop merely changes
1713 * the values associated with the keys (but doesn't insert new keys or
1714 * delete keys), via PyDict_SetItem().
1715 */
1716 int
1717 PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue)
1718 {
1719 return _PyDict_Next(op, ppos, pkey, pvalue, NULL);
1720 }
1721
1722 /* Internal version of dict.pop(). */
1723 PyObject *
1724 _PyDict_Pop_KnownHash(PyObject *dict, PyObject *key, Py_hash_t hash, PyObject *deflt)
1725 {
1726 Py_ssize_t ix, hashpos;
1727 PyObject *old_value, *old_key;
1728 PyDictKeyEntry *ep;
1729 PyDictObject *mp;
1730
1731 assert(PyDict_Check(dict));
1732 mp = (PyDictObject *)dict;
1733
1734 if (mp->ma_used == 0) {
1735 if (deflt) {
1736 Py_INCREF(deflt);
1737 return deflt;
1738 }
1739 _PyErr_SetKeyError(key);
1740 return NULL;
1741 }
1742 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
1743 if (ix == DKIX_ERROR)
1744 return NULL;
1745 if (ix == DKIX_EMPTY || old_value == NULL) {
1746 if (deflt) {
1747 Py_INCREF(deflt);
1748 return deflt;
1749 }
1750 _PyErr_SetKeyError(key);
1751 return NULL;
1752 }
1753
1754 // Split table doesn't allow deletion. Combine it.
1755 if (_PyDict_HasSplitTable(mp)) {
1756 if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
1757 return NULL;
1758 }
1759 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
1760 assert(ix >= 0);
1761 }
1762
1763 hashpos = lookdict_index(mp->ma_keys, hash, ix);
1764 assert(hashpos >= 0);
1765 assert(old_value != NULL);
1766 mp->ma_used--;
1767 mp->ma_version_tag = DICT_NEXT_VERSION();
1768 dk_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
1769 ep = &DK_ENTRIES(mp->ma_keys)[ix];
1770 ENSURE_ALLOWS_DELETIONS(mp);
1771 old_key = ep->me_key;
1772 ep->me_key = NULL;
1773 ep->me_value = NULL;
1774 Py_DECREF(old_key);
1775
1776 assert(_PyDict_CheckConsistency(mp));
1777 return old_value;
1778 }
1779
1780 PyObject *
1781 _PyDict_Pop(PyObject *dict, PyObject *key, PyObject *deflt)
1782 {
1783 Py_hash_t hash;
1784
1785 if (((PyDictObject *)dict)->ma_used == 0) {
1786 if (deflt) {
1787 Py_INCREF(deflt);
1788 return deflt;
1789 }
1790 _PyErr_SetKeyError(key);
1791 return NULL;
1792 }
1793 if (!PyUnicode_CheckExact(key) ||
1794 (hash = ((PyASCIIObject *) key)->hash) == -1) {
1795 hash = PyObject_Hash(key);
1796 if (hash == -1)
1797 return NULL;
1798 }
1799 return _PyDict_Pop_KnownHash(dict, key, hash, deflt);
1800 }
1801
1802 /* Internal version of dict.from_keys(). It is subclass-friendly. */
1803 PyObject *
1804 _PyDict_FromKeys(PyObject *cls, PyObject *iterable, PyObject *value)
1805 {
1806 PyObject *it; /* iter(iterable) */
1807 PyObject *key;
1808 PyObject *d;
1809 int status;
1810
1811 d = _PyObject_CallNoArg(cls);
1812 if (d == NULL)
1813 return NULL;
1814
1815 if (PyDict_CheckExact(d) && ((PyDictObject *)d)->ma_used == 0) {
1816 if (PyDict_CheckExact(iterable)) {
1817 PyDictObject *mp = (PyDictObject *)d;
1818 PyObject *oldvalue;
1819 Py_ssize_t pos = 0;
1820 PyObject *key;
1821 Py_hash_t hash;
1822
1823 if (dictresize(mp, ESTIMATE_SIZE(PyDict_GET_SIZE(iterable)))) {
1824 Py_DECREF(d);
1825 return NULL;
1826 }
1827
1828 while (_PyDict_Next(iterable, &pos, &key, &oldvalue, &hash)) {
1829 if (insertdict(mp, key, hash, value)) {
1830 Py_DECREF(d);
1831 return NULL;
1832 }
1833 }
1834 return d;
1835 }
1836 if (PyAnySet_CheckExact(iterable)) {
1837 PyDictObject *mp = (PyDictObject *)d;
1838 Py_ssize_t pos = 0;
1839 PyObject *key;
1840 Py_hash_t hash;
1841
1842 if (dictresize(mp, ESTIMATE_SIZE(PySet_GET_SIZE(iterable)))) {
1843 Py_DECREF(d);
1844 return NULL;
1845 }
1846
1847 while (_PySet_NextEntry(iterable, &pos, &key, &hash)) {
1848 if (insertdict(mp, key, hash, value)) {
1849 Py_DECREF(d);
1850 return NULL;
1851 }
1852 }
1853 return d;
1854 }
1855 }
1856
1857 it = PyObject_GetIter(iterable);
1858 if (it == NULL){
1859 Py_DECREF(d);
1860 return NULL;
1861 }
1862
1863 if (PyDict_CheckExact(d)) {
1864 while ((key = PyIter_Next(it)) != NULL) {
1865 status = PyDict_SetItem(d, key, value);
1866 Py_DECREF(key);
1867 if (status < 0)
1868 goto Fail;
1869 }
1870 } else {
1871 while ((key = PyIter_Next(it)) != NULL) {
1872 status = PyObject_SetItem(d, key, value);
1873 Py_DECREF(key);
1874 if (status < 0)
1875 goto Fail;
1876 }
1877 }
1878
1879 if (PyErr_Occurred())
1880 goto Fail;
1881 Py_DECREF(it);
1882 return d;
1883
1884 Fail:
1885 Py_DECREF(it);
1886 Py_DECREF(d);
1887 return NULL;
1888 }
1889
1890 /* Methods */
1891
1892 static void
1893 dict_dealloc(PyDictObject *mp)
1894 {
1895 PyObject **values = mp->ma_values;
1896 PyDictKeysObject *keys = mp->ma_keys;
1897 Py_ssize_t i, n;
1898
1899 /* bpo-31095: UnTrack is needed before calling any callbacks */
1900 PyObject_GC_UnTrack(mp);
1901 Py_TRASHCAN_SAFE_BEGIN(mp)
1902 if (values != NULL) {
1903 if (values != empty_values) {
1904 for (i = 0, n = mp->ma_keys->dk_nentries; i < n; i++) {
1905 Py_XDECREF(values[i]);
1906 }
1907 free_values(values);
1908 }
1909 DK_DECREF(keys);
1910 }
1911 else if (keys != NULL) {
1912 assert(keys->dk_refcnt == 1);
1913 DK_DECREF(keys);
1914 }
1915 if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
1916 free_list[numfree++] = mp;
1917 else
1918 Py_TYPE(mp)->tp_free((PyObject *)mp);
1919 Py_TRASHCAN_SAFE_END(mp)
1920 }
1921
1922
1923 static PyObject *
1924 dict_repr(PyDictObject *mp)
1925 {
1926 Py_ssize_t i;
1927 PyObject *key = NULL, *value = NULL;
1928 _PyUnicodeWriter writer;
1929 int first;
1930
1931 i = Py_ReprEnter((PyObject *)mp);
1932 if (i != 0) {
1933 return i > 0 ? PyUnicode_FromString("{...}") : NULL;
1934 }
1935
1936 if (mp->ma_used == 0) {
1937 Py_ReprLeave((PyObject *)mp);
1938 return PyUnicode_FromString("{}");
1939 }
1940
1941 _PyUnicodeWriter_Init(&writer);
1942 writer.overallocate = 1;
1943 /* "{" + "1: 2" + ", 3: 4" * (len - 1) + "}" */
1944 writer.min_length = 1 + 4 + (2 + 4) * (mp->ma_used - 1) + 1;
1945
1946 if (_PyUnicodeWriter_WriteChar(&writer, '{') < 0)
1947 goto error;
1948
1949 /* Do repr() on each key+value pair, and insert ": " between them.
1950 Note that repr may mutate the dict. */
1951 i = 0;
1952 first = 1;
1953 while (PyDict_Next((PyObject *)mp, &i, &key, &value)) {
1954 PyObject *s;
1955 int res;
1956
1957 /* Prevent repr from deleting key or value during key format. */
1958 Py_INCREF(key);
1959 Py_INCREF(value);
1960
1961 if (!first) {
1962 if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)
1963 goto error;
1964 }
1965 first = 0;
1966
1967 s = PyObject_Repr(key);
1968 if (s == NULL)
1969 goto error;
1970 res = _PyUnicodeWriter_WriteStr(&writer, s);
1971 Py_DECREF(s);
1972 if (res < 0)
1973 goto error;
1974
1975 if (_PyUnicodeWriter_WriteASCIIString(&writer, ": ", 2) < 0)
1976 goto error;
1977
1978 s = PyObject_Repr(value);
1979 if (s == NULL)
1980 goto error;
1981 res = _PyUnicodeWriter_WriteStr(&writer, s);
1982 Py_DECREF(s);
1983 if (res < 0)
1984 goto error;
1985
1986 Py_CLEAR(key);
1987 Py_CLEAR(value);
1988 }
1989
1990 writer.overallocate = 0;
1991 if (_PyUnicodeWriter_WriteChar(&writer, '}') < 0)
1992 goto error;
1993
1994 Py_ReprLeave((PyObject *)mp);
1995
1996 return _PyUnicodeWriter_Finish(&writer);
1997
1998 error:
1999 Py_ReprLeave((PyObject *)mp);
2000 _PyUnicodeWriter_Dealloc(&writer);
2001 Py_XDECREF(key);
2002 Py_XDECREF(value);
2003 return NULL;
2004 }
2005
2006 static Py_ssize_t
2007 dict_length(PyDictObject *mp)
2008 {
2009 return mp->ma_used;
2010 }
2011
2012 static PyObject *
2013 dict_subscript(PyDictObject *mp, PyObject *key)
2014 {
2015 Py_ssize_t ix;
2016 Py_hash_t hash;
2017 PyObject *value;
2018
2019 if (!PyUnicode_CheckExact(key) ||
2020 (hash = ((PyASCIIObject *) key)->hash) == -1) {
2021 hash = PyObject_Hash(key);
2022 if (hash == -1)
2023 return NULL;
2024 }
2025 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
2026 if (ix == DKIX_ERROR)
2027 return NULL;
2028 if (ix == DKIX_EMPTY || value == NULL) {
2029 if (!PyDict_CheckExact(mp)) {
2030 /* Look up __missing__ method if we're a subclass. */
2031 PyObject *missing, *res;
2032 _Py_IDENTIFIER(__missing__);
2033 missing = _PyObject_LookupSpecial((PyObject *)mp, &PyId___missing__);
2034 if (missing != NULL) {
2035 res = PyObject_CallFunctionObjArgs(missing,
2036 key, NULL);
2037 Py_DECREF(missing);
2038 return res;
2039 }
2040 else if (PyErr_Occurred())
2041 return NULL;
2042 }
2043 _PyErr_SetKeyError(key);
2044 return NULL;
2045 }
2046 Py_INCREF(value);
2047 return value;
2048 }
2049
2050 static int
2051 dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)
2052 {
2053 if (w == NULL)
2054 return PyDict_DelItem((PyObject *)mp, v);
2055 else
2056 return PyDict_SetItem((PyObject *)mp, v, w);
2057 }
2058
2059 static PyMappingMethods dict_as_mapping = {
2060 (lenfunc)dict_length, /*mp_length*/
2061 (binaryfunc)dict_subscript, /*mp_subscript*/
2062 (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
2063 };
2064
2065 static PyObject *
2066 dict_keys(PyDictObject *mp)
2067 {
2068 PyObject *v;
2069 Py_ssize_t i, j;
2070 PyDictKeyEntry *ep;
2071 Py_ssize_t size, n, offset;
2072 PyObject **value_ptr;
2073
2074 again:
2075 n = mp->ma_used;
2076 v = PyList_New(n);
2077 if (v == NULL)
2078 return NULL;
2079 if (n != mp->ma_used) {
2080 /* Durnit. The allocations caused the dict to resize.
2081 * Just start over, this shouldn't normally happen.
2082 */
2083 Py_DECREF(v);
2084 goto again;
2085 }
2086 ep = DK_ENTRIES(mp->ma_keys);
2087 size = mp->ma_keys->dk_nentries;
2088 if (mp->ma_values) {
2089 value_ptr = mp->ma_values;
2090 offset = sizeof(PyObject *);
2091 }
2092 else {
2093 value_ptr = &ep[0].me_value;
2094 offset = sizeof(PyDictKeyEntry);
2095 }
2096 for (i = 0, j = 0; i < size; i++) {
2097 if (*value_ptr != NULL) {
2098 PyObject *key = ep[i].me_key;
2099 Py_INCREF(key);
2100 PyList_SET_ITEM(v, j, key);
2101 j++;
2102 }
2103 value_ptr = (PyObject **)(((char *)value_ptr) + offset);
2104 }
2105 assert(j == n);
2106 return v;
2107 }
2108
2109 static PyObject *
2110 dict_values(PyDictObject *mp)
2111 {
2112 PyObject *v;
2113 Py_ssize_t i, j;
2114 PyDictKeyEntry *ep;
2115 Py_ssize_t size, n, offset;
2116 PyObject **value_ptr;
2117
2118 again:
2119 n = mp->ma_used;
2120 v = PyList_New(n);
2121 if (v == NULL)
2122 return NULL;
2123 if (n != mp->ma_used) {
2124 /* Durnit. The allocations caused the dict to resize.
2125 * Just start over, this shouldn't normally happen.
2126 */
2127 Py_DECREF(v);
2128 goto again;
2129 }
2130 ep = DK_ENTRIES(mp->ma_keys);
2131 size = mp->ma_keys->dk_nentries;
2132 if (mp->ma_values) {
2133 value_ptr = mp->ma_values;
2134 offset = sizeof(PyObject *);
2135 }
2136 else {
2137 value_ptr = &ep[0].me_value;
2138 offset = sizeof(PyDictKeyEntry);
2139 }
2140 for (i = 0, j = 0; i < size; i++) {
2141 PyObject *value = *value_ptr;
2142 value_ptr = (PyObject **)(((char *)value_ptr) + offset);
2143 if (value != NULL) {
2144 Py_INCREF(value);
2145 PyList_SET_ITEM(v, j, value);
2146 j++;
2147 }
2148 }
2149 assert(j == n);
2150 return v;
2151 }
2152
2153 static PyObject *
2154 dict_items(PyDictObject *mp)
2155 {
2156 PyObject *v;
2157 Py_ssize_t i, j, n;
2158 Py_ssize_t size, offset;
2159 PyObject *item, *key;
2160 PyDictKeyEntry *ep;
2161 PyObject **value_ptr;
2162
2163 /* Preallocate the list of tuples, to avoid allocations during
2164 * the loop over the items, which could trigger GC, which
2165 * could resize the dict. :-(
2166 */
2167 again:
2168 n = mp->ma_used;
2169 v = PyList_New(n);
2170 if (v == NULL)
2171 return NULL;
2172 for (i = 0; i < n; i++) {
2173 item = PyTuple_New(2);
2174 if (item == NULL) {
2175 Py_DECREF(v);
2176 return NULL;
2177 }
2178 PyList_SET_ITEM(v, i, item);
2179 }
2180 if (n != mp->ma_used) {
2181 /* Durnit. The allocations caused the dict to resize.
2182 * Just start over, this shouldn't normally happen.
2183 */
2184 Py_DECREF(v);
2185 goto again;
2186 }
2187 /* Nothing we do below makes any function calls. */
2188 ep = DK_ENTRIES(mp->ma_keys);
2189 size = mp->ma_keys->dk_nentries;
2190 if (mp->ma_values) {
2191 value_ptr = mp->ma_values;
2192 offset = sizeof(PyObject *);
2193 }
2194 else {
2195 value_ptr = &ep[0].me_value;
2196 offset = sizeof(PyDictKeyEntry);
2197 }
2198 for (i = 0, j = 0; i < size; i++) {
2199 PyObject *value = *value_ptr;
2200 value_ptr = (PyObject **)(((char *)value_ptr) + offset);
2201 if (value != NULL) {
2202 key = ep[i].me_key;
2203 item = PyList_GET_ITEM(v, j);
2204 Py_INCREF(key);
2205 PyTuple_SET_ITEM(item, 0, key);
2206 Py_INCREF(value);
2207 PyTuple_SET_ITEM(item, 1, value);
2208 j++;
2209 }
2210 }
2211 assert(j == n);
2212 return v;
2213 }
2214
2215 /*[clinic input]
2216 @classmethod
2217 dict.fromkeys
2218 iterable: object
2219 value: object=None
2220 /
2221
2222 Create a new dictionary with keys from iterable and values set to value.
2223 [clinic start generated code]*/
2224
2225 static PyObject *
2226 dict_fromkeys_impl(PyTypeObject *type, PyObject *iterable, PyObject *value)
2227 /*[clinic end generated code: output=8fb98e4b10384999 input=382ba4855d0f74c3]*/
2228 {
2229 return _PyDict_FromKeys((PyObject *)type, iterable, value);
2230 }
2231
2232 static int
2233 dict_update_common(PyObject *self, PyObject *args, PyObject *kwds,
2234 const char *methname)
2235 {
2236 PyObject *arg = NULL;
2237 int result = 0;
2238
2239 if (!PyArg_UnpackTuple(args, methname, 0, 1, &arg)) {
2240 result = -1;
2241 }
2242 else if (arg != NULL) {
2243 _Py_IDENTIFIER(keys);
2244 PyObject *func;
2245 if (_PyObject_LookupAttrId(arg, &PyId_keys, &func) < 0) {
2246 result = -1;
2247 }
2248 else if (func != NULL) {
2249 Py_DECREF(func);
2250 result = PyDict_Merge(self, arg, 1);
2251 }
2252 else {
2253 result = PyDict_MergeFromSeq2(self, arg, 1);
2254 }
2255 }
2256
2257 if (result == 0 && kwds != NULL) {
2258 if (PyArg_ValidateKeywordArguments(kwds))
2259 result = PyDict_Merge(self, kwds, 1);
2260 else
2261 result = -1;
2262 }
2263 return result;
2264 }
2265
2266 /* Note: dict.update() uses the METH_VARARGS|METH_KEYWORDS calling convention.
2267 Using METH_FASTCALL|METH_KEYWORDS would make dict.update(**dict2) calls
2268 slower, see the issue #29312. */
2269 static PyObject *
2270 dict_update(PyObject *self, PyObject *args, PyObject *kwds)
2271 {
2272 if (dict_update_common(self, args, kwds, "update") != -1)
2273 Py_RETURN_NONE;
2274 return NULL;
2275 }
2276
2277 /* Update unconditionally replaces existing items.
2278 Merge has a 3rd argument 'override'; if set, it acts like Update,
2279 otherwise it leaves existing items unchanged.
2280
2281 PyDict_{Update,Merge} update/merge from a mapping object.
2282
2283 PyDict_MergeFromSeq2 updates/merges from any iterable object
2284 producing iterable objects of length 2.
2285 */
2286
2287 int
2288 PyDict_MergeFromSeq2(PyObject *d, PyObject *seq2, int override)
2289 {
2290 PyObject *it; /* iter(seq2) */
2291 Py_ssize_t i; /* index into seq2 of current element */
2292 PyObject *item; /* seq2[i] */
2293 PyObject *fast; /* item as a 2-tuple or 2-list */
2294
2295 assert(d != NULL);
2296 assert(PyDict_Check(d));
2297 assert(seq2 != NULL);
2298
2299 it = PyObject_GetIter(seq2);
2300 if (it == NULL)
2301 return -1;
2302
2303 for (i = 0; ; ++i) {
2304 PyObject *key, *value;
2305 Py_ssize_t n;
2306
2307 fast = NULL;
2308 item = PyIter_Next(it);
2309 if (item == NULL) {
2310 if (PyErr_Occurred())
2311 goto Fail;
2312 break;
2313 }
2314
2315 /* Convert item to sequence, and verify length 2. */
2316 fast = PySequence_Fast(item, "");
2317 if (fast == NULL) {
2318 if (PyErr_ExceptionMatches(PyExc_TypeError))
2319 PyErr_Format(PyExc_TypeError,
2320 "cannot convert dictionary update "
2321 "sequence element #%zd to a sequence",
2322 i);
2323 goto Fail;
2324 }
2325 n = PySequence_Fast_GET_SIZE(fast);
2326 if (n != 2) {
2327 PyErr_Format(PyExc_ValueError,
2328 "dictionary update sequence element #%zd "
2329 "has length %zd; 2 is required",
2330 i, n);
2331 goto Fail;
2332 }
2333
2334 /* Update/merge with this (key, value) pair. */
2335 key = PySequence_Fast_GET_ITEM(fast, 0);
2336 value = PySequence_Fast_GET_ITEM(fast, 1);
2337 Py_INCREF(key);
2338 Py_INCREF(value);
2339 if (override || PyDict_GetItem(d, key) == NULL) {
2340 int status = PyDict_SetItem(d, key, value);
2341 if (status < 0) {
2342 Py_DECREF(key);
2343 Py_DECREF(value);
2344 goto Fail;
2345 }
2346 }
2347 Py_DECREF(key);
2348 Py_DECREF(value);
2349 Py_DECREF(fast);
2350 Py_DECREF(item);
2351 }
2352
2353 i = 0;
2354 assert(_PyDict_CheckConsistency((PyDictObject *)d));
2355 goto Return;
2356 Fail:
2357 Py_XDECREF(item);
2358 Py_XDECREF(fast);
2359 i = -1;
2360 Return:
2361 Py_DECREF(it);
2362 return Py_SAFE_DOWNCAST(i, Py_ssize_t, int);
2363 }
2364
2365 static int
2366 dict_merge(PyObject *a, PyObject *b, int override)
2367 {
2368 PyDictObject *mp, *other;
2369 Py_ssize_t i, n;
2370 PyDictKeyEntry *entry, *ep0;
2371
2372 assert(0 <= override && override <= 2);
2373
2374 /* We accept for the argument either a concrete dictionary object,
2375 * or an abstract "mapping" object. For the former, we can do
2376 * things quite efficiently. For the latter, we only require that
2377 * PyMapping_Keys() and PyObject_GetItem() be supported.
2378 */
2379 if (a == NULL || !PyDict_Check(a) || b == NULL) {
2380 PyErr_BadInternalCall();
2381 return -1;
2382 }
2383 mp = (PyDictObject*)a;
2384 if (PyDict_Check(b) && (Py_TYPE(b)->tp_iter == (getiterfunc)dict_iter)) {
2385 other = (PyDictObject*)b;
2386 if (other == mp || other->ma_used == 0)
2387 /* a.update(a) or a.update({}); nothing to do */
2388 return 0;
2389 if (mp->ma_used == 0)
2390 /* Since the target dict is empty, PyDict_GetItem()
2391 * always returns NULL. Setting override to 1
2392 * skips the unnecessary test.
2393 */
2394 override = 1;
2395 /* Do one big resize at the start, rather than
2396 * incrementally resizing as we insert new items. Expect
2397 * that there will be no (or few) overlapping keys.
2398 */
2399 if (USABLE_FRACTION(mp->ma_keys->dk_size) < other->ma_used) {
2400 if (dictresize(mp, ESTIMATE_SIZE(mp->ma_used + other->ma_used))) {
2401 return -1;
2402 }
2403 }
2404 ep0 = DK_ENTRIES(other->ma_keys);
2405 for (i = 0, n = other->ma_keys->dk_nentries; i < n; i++) {
2406 PyObject *key, *value;
2407 Py_hash_t hash;
2408 entry = &ep0[i];
2409 key = entry->me_key;
2410 hash = entry->me_hash;
2411 if (other->ma_values)
2412 value = other->ma_values[i];
2413 else
2414 value = entry->me_value;
2415
2416 if (value != NULL) {
2417 int err = 0;
2418 Py_INCREF(key);
2419 Py_INCREF(value);
2420 if (override == 1)
2421 err = insertdict(mp, key, hash, value);
2422 else if (_PyDict_GetItem_KnownHash(a, key, hash) == NULL) {
2423 if (PyErr_Occurred()) {
2424 Py_DECREF(value);
2425 Py_DECREF(key);
2426 return -1;
2427 }
2428 err = insertdict(mp, key, hash, value);
2429 }
2430 else if (override != 0) {
2431 _PyErr_SetKeyError(key);
2432 Py_DECREF(value);
2433 Py_DECREF(key);
2434 return -1;
2435 }
2436 Py_DECREF(value);
2437 Py_DECREF(key);
2438 if (err != 0)
2439 return -1;
2440
2441 if (n != other->ma_keys->dk_nentries) {
2442 PyErr_SetString(PyExc_RuntimeError,
2443 "dict mutated during update");
2444 return -1;
2445 }
2446 }
2447 }
2448 }
2449 else {
2450 /* Do it the generic, slower way */
2451 PyObject *keys = PyMapping_Keys(b);
2452 PyObject *iter;
2453 PyObject *key, *value;
2454 int status;
2455
2456 if (keys == NULL)
2457 /* Docstring says this is equivalent to E.keys() so
2458 * if E doesn't have a .keys() method we want
2459 * AttributeError to percolate up. Might as well
2460 * do the same for any other error.
2461 */
2462 return -1;
2463
2464 iter = PyObject_GetIter(keys);
2465 Py_DECREF(keys);
2466 if (iter == NULL)
2467 return -1;
2468
2469 for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) {
2470 if (override != 1 && PyDict_GetItem(a, key) != NULL) {
2471 if (override != 0) {
2472 _PyErr_SetKeyError(key);
2473 Py_DECREF(key);
2474 Py_DECREF(iter);
2475 return -1;
2476 }
2477 Py_DECREF(key);
2478 continue;
2479 }
2480 value = PyObject_GetItem(b, key);
2481 if (value == NULL) {
2482 Py_DECREF(iter);
2483 Py_DECREF(key);
2484 return -1;
2485 }
2486 status = PyDict_SetItem(a, key, value);
2487 Py_DECREF(key);
2488 Py_DECREF(value);
2489 if (status < 0) {
2490 Py_DECREF(iter);
2491 return -1;
2492 }
2493 }
2494 Py_DECREF(iter);
2495 if (PyErr_Occurred())
2496 /* Iterator completed, via error */
2497 return -1;
2498 }
2499 assert(_PyDict_CheckConsistency((PyDictObject *)a));
2500 return 0;
2501 }
2502
2503 int
2504 PyDict_Update(PyObject *a, PyObject *b)
2505 {
2506 return dict_merge(a, b, 1);
2507 }
2508
2509 int
2510 PyDict_Merge(PyObject *a, PyObject *b, int override)
2511 {
2512 /* XXX Deprecate override not in (0, 1). */
2513 return dict_merge(a, b, override != 0);
2514 }
2515
2516 int
2517 _PyDict_MergeEx(PyObject *a, PyObject *b, int override)
2518 {
2519 return dict_merge(a, b, override);
2520 }
2521
2522 static PyObject *
2523 dict_copy(PyDictObject *mp)
2524 {
2525 return PyDict_Copy((PyObject*)mp);
2526 }
2527
2528 PyObject *
2529 PyDict_Copy(PyObject *o)
2530 {
2531 PyObject *copy;
2532 PyDictObject *mp;
2533 Py_ssize_t i, n;
2534
2535 if (o == NULL || !PyDict_Check(o)) {
2536 PyErr_BadInternalCall();
2537 return NULL;
2538 }
2539
2540 mp = (PyDictObject *)o;
2541 if (mp->ma_used == 0) {
2542 /* The dict is empty; just return a new dict. */
2543 return PyDict_New();
2544 }
2545
2546 if (_PyDict_HasSplitTable(mp)) {
2547 PyDictObject *split_copy;
2548 Py_ssize_t size = USABLE_FRACTION(DK_SIZE(mp->ma_keys));
2549 PyObject **newvalues;
2550 newvalues = new_values(size);
2551 if (newvalues == NULL)
2552 return PyErr_NoMemory();
2553 split_copy = PyObject_GC_New(PyDictObject, &PyDict_Type);
2554 if (split_copy == NULL) {
2555 free_values(newvalues);
2556 return NULL;
2557 }
2558 split_copy->ma_values = newvalues;
2559 split_copy->ma_keys = mp->ma_keys;
2560 split_copy->ma_used = mp->ma_used;
2561 split_copy->ma_version_tag = DICT_NEXT_VERSION();
2562 DK_INCREF(mp->ma_keys);
2563 for (i = 0, n = size; i < n; i++) {
2564 PyObject *value = mp->ma_values[i];
2565 Py_XINCREF(value);
2566 split_copy->ma_values[i] = value;
2567 }
2568 if (_PyObject_GC_IS_TRACKED(mp))
2569 _PyObject_GC_TRACK(split_copy);
2570 return (PyObject *)split_copy;
2571 }
2572
2573 if (PyDict_CheckExact(mp) && mp->ma_values == NULL &&
2574 (mp->ma_used >= (mp->ma_keys->dk_nentries * 2) / 3))
2575 {
2576 /* Use fast-copy if:
2577
2578 (1) 'mp' is an instance of a subclassed dict; and
2579
2580 (2) 'mp' is not a split-dict; and
2581
2582 (3) if 'mp' is non-compact ('del' operation does not resize dicts),
2583 do fast-copy only if it has at most 1/3 non-used keys.
2584
2585 The last condition (3) is important to guard against a pathological
2586 case when a large dict is almost emptied with multiple del/pop
2587 operations and copied after that. In cases like this, we defer to
2588 PyDict_Merge, which produces a compacted copy.
2589 */
2590 return clone_combined_dict(mp);
2591 }
2592
2593 copy = PyDict_New();
2594 if (copy == NULL)
2595 return NULL;
2596 if (PyDict_Merge(copy, o, 1) == 0)
2597 return copy;
2598 Py_DECREF(copy);
2599 return NULL;
2600 }
2601
2602 Py_ssize_t
2603 PyDict_Size(PyObject *mp)
2604 {
2605 if (mp == NULL || !PyDict_Check(mp)) {
2606 PyErr_BadInternalCall();
2607 return -1;
2608 }
2609 return ((PyDictObject *)mp)->ma_used;
2610 }
2611
2612 PyObject *
2613 PyDict_Keys(PyObject *mp)
2614 {
2615 if (mp == NULL || !PyDict_Check(mp)) {
2616 PyErr_BadInternalCall();
2617 return NULL;
2618 }
2619 return dict_keys((PyDictObject *)mp);
2620 }
2621
2622 PyObject *
2623 PyDict_Values(PyObject *mp)
2624 {
2625 if (mp == NULL || !PyDict_Check(mp)) {
2626 PyErr_BadInternalCall();
2627 return NULL;
2628 }
2629 return dict_values((PyDictObject *)mp);
2630 }
2631
2632 PyObject *
2633 PyDict_Items(PyObject *mp)
2634 {
2635 if (mp == NULL || !PyDict_Check(mp)) {
2636 PyErr_BadInternalCall();
2637 return NULL;
2638 }
2639 return dict_items((PyDictObject *)mp);
2640 }
2641
2642 /* Return 1 if dicts equal, 0 if not, -1 if error.
2643 * Gets out as soon as any difference is detected.
2644 * Uses only Py_EQ comparison.
2645 */
2646 static int
2647 dict_equal(PyDictObject *a, PyDictObject *b)
2648 {
2649 Py_ssize_t i;
2650
2651 if (a->ma_used != b->ma_used)
2652 /* can't be equal if # of entries differ */
2653 return 0;
2654 /* Same # of entries -- check all of 'em. Exit early on any diff. */
2655 for (i = 0; i < a->ma_keys->dk_nentries; i++) {
2656 PyDictKeyEntry *ep = &DK_ENTRIES(a->ma_keys)[i];
2657 PyObject *aval;
2658 if (a->ma_values)
2659 aval = a->ma_values[i];
2660 else
2661 aval = ep->me_value;
2662 if (aval != NULL) {
2663 int cmp;
2664 PyObject *bval;
2665 PyObject *key = ep->me_key;
2666 /* temporarily bump aval's refcount to ensure it stays
2667 alive until we're done with it */
2668 Py_INCREF(aval);
2669 /* ditto for key */
2670 Py_INCREF(key);
2671 /* reuse the known hash value */
2672 b->ma_keys->dk_lookup(b, key, ep->me_hash, &bval);
2673 if (bval == NULL) {
2674 Py_DECREF(key);
2675 Py_DECREF(aval);
2676 if (PyErr_Occurred())
2677 return -1;
2678 return 0;
2679 }
2680 Py_INCREF(bval);
2681 cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
2682 Py_DECREF(key);
2683 Py_DECREF(aval);
2684 Py_DECREF(bval);
2685 if (cmp <= 0) /* error or not equal */
2686 return cmp;
2687 }
2688 }
2689 return 1;
2690 }
2691
2692 static PyObject *
2693 dict_richcompare(PyObject *v, PyObject *w, int op)
2694 {
2695 int cmp;
2696 PyObject *res;
2697
2698 if (!PyDict_Check(v) || !PyDict_Check(w)) {
2699 res = Py_NotImplemented;
2700 }
2701 else if (op == Py_EQ || op == Py_NE) {
2702 cmp = dict_equal((PyDictObject *)v, (PyDictObject *)w);
2703 if (cmp < 0)
2704 return NULL;
2705 res = (cmp == (op == Py_EQ)) ? Py_True : Py_False;
2706 }
2707 else
2708 res = Py_NotImplemented;
2709 Py_INCREF(res);
2710 return res;
2711 }
2712
2713 /*[clinic input]
2714
2715 @coexist
2716 dict.__contains__
2717
2718 key: object
2719 /
2720
2721 True if the dictionary has the specified key, else False.
2722 [clinic start generated code]*/
2723
2724 static PyObject *
2725 dict___contains__(PyDictObject *self, PyObject *key)
2726 /*[clinic end generated code: output=a3d03db709ed6e6b input=fe1cb42ad831e820]*/
2727 {
2728 register PyDictObject *mp = self;
2729 Py_hash_t hash;
2730 Py_ssize_t ix;
2731 PyObject *value;
2732
2733 if (!PyUnicode_CheckExact(key) ||
2734 (hash = ((PyASCIIObject *) key)->hash) == -1) {
2735 hash = PyObject_Hash(key);
2736 if (hash == -1)
2737 return NULL;
2738 }
2739 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
2740 if (ix == DKIX_ERROR)
2741 return NULL;
2742 if (ix == DKIX_EMPTY || value == NULL)
2743 Py_RETURN_FALSE;
2744 Py_RETURN_TRUE;
2745 }
2746
2747 /*[clinic input]
2748 dict.get
2749
2750 key: object
2751 default: object = None
2752 /
2753
2754 Return the value for key if key is in the dictionary, else default.
2755 [clinic start generated code]*/
2756
2757 static PyObject *
2758 dict_get_impl(PyDictObject *self, PyObject *key, PyObject *default_value)
2759 /*[clinic end generated code: output=bba707729dee05bf input=279ddb5790b6b107]*/
2760 {
2761 PyObject *val = NULL;
2762 Py_hash_t hash;
2763 Py_ssize_t ix;
2764
2765 if (!PyUnicode_CheckExact(key) ||
2766 (hash = ((PyASCIIObject *) key)->hash) == -1) {
2767 hash = PyObject_Hash(key);
2768 if (hash == -1)
2769 return NULL;
2770 }
2771 ix = (self->ma_keys->dk_lookup) (self, key, hash, &val);
2772 if (ix == DKIX_ERROR)
2773 return NULL;
2774 if (ix == DKIX_EMPTY || val == NULL) {
2775 val = default_value;
2776 }
2777 Py_INCREF(val);
2778 return val;
2779 }
2780
2781 PyObject *
2782 PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj)
2783 {
2784 PyDictObject *mp = (PyDictObject *)d;
2785 PyObject *value;
2786 Py_hash_t hash;
2787
2788 if (!PyDict_Check(d)) {
2789 PyErr_BadInternalCall();
2790 return NULL;
2791 }
2792
2793 if (!PyUnicode_CheckExact(key) ||
2794 (hash = ((PyASCIIObject *) key)->hash) == -1) {
2795 hash = PyObject_Hash(key);
2796 if (hash == -1)
2797 return NULL;
2798 }
2799
2800 if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {
2801 if (insertion_resize(mp) < 0)
2802 return NULL;
2803 }
2804
2805 Py_ssize_t ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
2806 if (ix == DKIX_ERROR)
2807 return NULL;
2808
2809 if (_PyDict_HasSplitTable(mp) &&
2810 ((ix >= 0 && value == NULL && mp->ma_used != ix) ||
2811 (ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) {
2812 if (insertion_resize(mp) < 0) {
2813 return NULL;
2814 }
2815 ix = DKIX_EMPTY;
2816 }
2817
2818 if (ix == DKIX_EMPTY) {
2819 PyDictKeyEntry *ep, *ep0;
2820 value = defaultobj;
2821 if (mp->ma_keys->dk_usable <= 0) {
2822 if (insertion_resize(mp) < 0) {
2823 return NULL;
2824 }
2825 }
2826 Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
2827 ep0 = DK_ENTRIES(mp->ma_keys);
2828 ep = &ep0[mp->ma_keys->dk_nentries];
2829 dk_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
2830 Py_INCREF(key);
2831 Py_INCREF(value);
2832 MAINTAIN_TRACKING(mp, key, value);
2833 ep->me_key = key;
2834 ep->me_hash = hash;
2835 if (_PyDict_HasSplitTable(mp)) {
2836 assert(mp->ma_values[mp->ma_keys->dk_nentries] == NULL);
2837 mp->ma_values[mp->ma_keys->dk_nentries] = value;
2838 }
2839 else {
2840 ep->me_value = value;
2841 }
2842 mp->ma_used++;
2843 mp->ma_version_tag = DICT_NEXT_VERSION();
2844 mp->ma_keys->dk_usable--;
2845 mp->ma_keys->dk_nentries++;
2846 assert(mp->ma_keys->dk_usable >= 0);
2847 }
2848 else if (value == NULL) {
2849 value = defaultobj;
2850 assert(_PyDict_HasSplitTable(mp));
2851 assert(ix == mp->ma_used);
2852 Py_INCREF(value);
2853 MAINTAIN_TRACKING(mp, key, value);
2854 mp->ma_values[ix] = value;
2855 mp->ma_used++;
2856 mp->ma_version_tag = DICT_NEXT_VERSION();
2857 }
2858
2859 assert(_PyDict_CheckConsistency(mp));
2860 return value;
2861 }
2862
2863 /*[clinic input]
2864 dict.setdefault
2865
2866 key: object
2867 default: object = None
2868 /
2869
2870 Insert key with a value of default if key is not in the dictionary.
2871
2872 Return the value for key if key is in the dictionary, else default.
2873 [clinic start generated code]*/
2874
2875 static PyObject *
2876 dict_setdefault_impl(PyDictObject *self, PyObject *key,
2877 PyObject *default_value)
2878 /*[clinic end generated code: output=f8c1101ebf69e220 input=0f063756e815fd9d]*/
2879 {
2880 PyObject *val;
2881
2882 val = PyDict_SetDefault((PyObject *)self, key, default_value);
2883 Py_XINCREF(val);
2884 return val;
2885 }
2886
2887 static PyObject *
2888 dict_clear(PyDictObject *mp)
2889 {
2890 PyDict_Clear((PyObject *)mp);
2891 Py_RETURN_NONE;
2892 }
2893
2894 static PyObject *
2895 dict_pop(PyDictObject *mp, PyObject *args)
2896 {
2897 PyObject *key, *deflt = NULL;
2898
2899 if(!PyArg_UnpackTuple(args, "pop", 1, 2, &key, &deflt))
2900 return NULL;
2901
2902 return _PyDict_Pop((PyObject*)mp, key, deflt);
2903 }
2904
2905 static PyObject *
2906 dict_popitem(PyDictObject *mp)
2907 {
2908 Py_ssize_t i, j;
2909 PyDictKeyEntry *ep0, *ep;
2910 PyObject *res;
2911
2912 /* Allocate the result tuple before checking the size. Believe it
2913 * or not, this allocation could trigger a garbage collection which
2914 * could empty the dict, so if we checked the size first and that
2915 * happened, the result would be an infinite loop (searching for an
2916 * entry that no longer exists). Note that the usual popitem()
2917 * idiom is "while d: k, v = d.popitem()". so needing to throw the
2918 * tuple away if the dict *is* empty isn't a significant
2919 * inefficiency -- possible, but unlikely in practice.
2920 */
2921 res = PyTuple_New(2);
2922 if (res == NULL)
2923 return NULL;
2924 if (mp->ma_used == 0) {
2925 Py_DECREF(res);
2926 PyErr_SetString(PyExc_KeyError,
2927 "popitem(): dictionary is empty");
2928 return NULL;
2929 }
2930 /* Convert split table to combined table */
2931 if (mp->ma_keys->dk_lookup == lookdict_split) {
2932 if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
2933 Py_DECREF(res);
2934 return NULL;
2935 }
2936 }
2937 ENSURE_ALLOWS_DELETIONS(mp);
2938
2939 /* Pop last item */
2940 ep0 = DK_ENTRIES(mp->ma_keys);
2941 i = mp->ma_keys->dk_nentries - 1;
2942 while (i >= 0 && ep0[i].me_value == NULL) {
2943 i--;
2944 }
2945 assert(i >= 0);
2946
2947 ep = &ep0[i];
2948 j = lookdict_index(mp->ma_keys, ep->me_hash, i);
2949 assert(j >= 0);
2950 assert(dk_get_index(mp->ma_keys, j) == i);
2951 dk_set_index(mp->ma_keys, j, DKIX_DUMMY);
2952
2953 PyTuple_SET_ITEM(res, 0, ep->me_key);
2954 PyTuple_SET_ITEM(res, 1, ep->me_value);
2955 ep->me_key = NULL;
2956 ep->me_value = NULL;
2957 /* We can't dk_usable++ since there is DKIX_DUMMY in indices */
2958 mp->ma_keys->dk_nentries = i;
2959 mp->ma_used--;
2960 mp->ma_version_tag = DICT_NEXT_VERSION();
2961 assert(_PyDict_CheckConsistency(mp));
2962 return res;
2963 }
2964
2965 static int
2966 dict_traverse(PyObject *op, visitproc visit, void *arg)
2967 {
2968 PyDictObject *mp = (PyDictObject *)op;
2969 PyDictKeysObject *keys = mp->ma_keys;
2970 PyDictKeyEntry *entries = DK_ENTRIES(keys);
2971 Py_ssize_t i, n = keys->dk_nentries;
2972
2973 if (keys->dk_lookup == lookdict) {
2974 for (i = 0; i < n; i++) {
2975 if (entries[i].me_value != NULL) {
2976 Py_VISIT(entries[i].me_value);
2977 Py_VISIT(entries[i].me_key);
2978 }
2979 }
2980 }
2981 else {
2982 if (mp->ma_values != NULL) {
2983 for (i = 0; i < n; i++) {
2984 Py_VISIT(mp->ma_values[i]);
2985 }
2986 }
2987 else {
2988 for (i = 0; i < n; i++) {
2989 Py_VISIT(entries[i].me_value);
2990 }
2991 }
2992 }
2993 return 0;
2994 }
2995
2996 static int
2997 dict_tp_clear(PyObject *op)
2998 {
2999 PyDict_Clear(op);
3000 return 0;
3001 }
3002
3003 static PyObject *dictiter_new(PyDictObject *, PyTypeObject *);
3004
3005 Py_ssize_t
3006 _PyDict_SizeOf(PyDictObject *mp)
3007 {
3008 Py_ssize_t size, usable, res;
3009
3010 size = DK_SIZE(mp->ma_keys);
3011 usable = USABLE_FRACTION(size);
3012
3013 res = _PyObject_SIZE(Py_TYPE(mp));
3014 if (mp->ma_values)
3015 res += usable * sizeof(PyObject*);
3016 /* If the dictionary is split, the keys portion is accounted-for
3017 in the type object. */
3018 if (mp->ma_keys->dk_refcnt == 1)
3019 res += (sizeof(PyDictKeysObject)
3020 + DK_IXSIZE(mp->ma_keys) * size
3021 + sizeof(PyDictKeyEntry) * usable);
3022 return res;
3023 }
3024
3025 Py_ssize_t
3026 _PyDict_KeysSize(PyDictKeysObject *keys)
3027 {
3028 return (sizeof(PyDictKeysObject)
3029 + DK_IXSIZE(keys) * DK_SIZE(keys)
3030 + USABLE_FRACTION(DK_SIZE(keys)) * sizeof(PyDictKeyEntry));
3031 }
3032
3033 static PyObject *
3034 dict_sizeof(PyDictObject *mp)
3035 {
3036 return PyLong_FromSsize_t(_PyDict_SizeOf(mp));
3037 }
3038
3039 PyDoc_STRVAR(getitem__doc__, "x.__getitem__(y) <==> x[y]");
3040
3041 PyDoc_STRVAR(sizeof__doc__,
3042 "D.__sizeof__() -> size of D in memory, in bytes");
3043
3044 PyDoc_STRVAR(pop__doc__,
3045 "D.pop(k[,d]) -> v, remove specified key and return the corresponding value.\n\
3046 If key is not found, d is returned if given, otherwise KeyError is raised");
3047
3048 PyDoc_STRVAR(popitem__doc__,
3049 "D.popitem() -> (k, v), remove and return some (key, value) pair as a\n\
3050 2-tuple; but raise KeyError if D is empty.");
3051
3052 PyDoc_STRVAR(update__doc__,
3053 "D.update([E, ]**F) -> None. Update D from dict/iterable E and F.\n\
3054 If E is present and has a .keys() method, then does: for k in E: D[k] = E[k]\n\
3055 If E is present and lacks a .keys() method, then does: for k, v in E: D[k] = v\n\
3056 In either case, this is followed by: for k in F: D[k] = F[k]");
3057
3058 PyDoc_STRVAR(clear__doc__,
3059 "D.clear() -> None. Remove all items from D.");
3060
3061 PyDoc_STRVAR(copy__doc__,
3062 "D.copy() -> a shallow copy of D");
3063
3064 /* Forward */
3065 static PyObject *dictkeys_new(PyObject *);
3066 static PyObject *dictitems_new(PyObject *);
3067 static PyObject *dictvalues_new(PyObject *);
3068
3069 PyDoc_STRVAR(keys__doc__,
3070 "D.keys() -> a set-like object providing a view on D's keys");
3071 PyDoc_STRVAR(items__doc__,
3072 "D.items() -> a set-like object providing a view on D's items");
3073 PyDoc_STRVAR(values__doc__,
3074 "D.values() -> an object providing a view on D's values");
3075
3076 static PyMethodDef mapp_methods[] = {
3077 DICT___CONTAINS___METHODDEF
3078 {"__getitem__", (PyCFunction)dict_subscript, METH_O | METH_COEXIST,
3079 getitem__doc__},
3080 {"__sizeof__", (PyCFunction)dict_sizeof, METH_NOARGS,
3081 sizeof__doc__},
3082 DICT_GET_METHODDEF
3083 DICT_SETDEFAULT_METHODDEF
3084 {"pop", (PyCFunction)dict_pop, METH_VARARGS,
3085 pop__doc__},
3086 {"popitem", (PyCFunction)dict_popitem, METH_NOARGS,
3087 popitem__doc__},
3088 {"keys", (PyCFunction)dictkeys_new, METH_NOARGS,
3089 keys__doc__},
3090 {"items", (PyCFunction)dictitems_new, METH_NOARGS,
3091 items__doc__},
3092 {"values", (PyCFunction)dictvalues_new, METH_NOARGS,
3093 values__doc__},
3094 {"update", (PyCFunction)dict_update, METH_VARARGS | METH_KEYWORDS,
3095 update__doc__},
3096 DICT_FROMKEYS_METHODDEF
3097 {"clear", (PyCFunction)dict_clear, METH_NOARGS,
3098 clear__doc__},
3099 {"copy", (PyCFunction)dict_copy, METH_NOARGS,
3100 copy__doc__},
3101 {NULL, NULL} /* sentinel */
3102 };
3103
3104 /* Return 1 if `key` is in dict `op`, 0 if not, and -1 on error. */
3105 int
3106 PyDict_Contains(PyObject *op, PyObject *key)
3107 {
3108 Py_hash_t hash;
3109 Py_ssize_t ix;
3110 PyDictObject *mp = (PyDictObject *)op;
3111 PyObject *value;
3112
3113 if (!PyUnicode_CheckExact(key) ||
3114 (hash = ((PyASCIIObject *) key)->hash) == -1) {
3115 hash = PyObject_Hash(key);
3116 if (hash == -1)
3117 return -1;
3118 }
3119 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
3120 if (ix == DKIX_ERROR)
3121 return -1;
3122 return (ix != DKIX_EMPTY && value != NULL);
3123 }
3124
3125 /* Internal version of PyDict_Contains used when the hash value is already known */
3126 int
3127 _PyDict_Contains(PyObject *op, PyObject *key, Py_hash_t hash)
3128 {
3129 PyDictObject *mp = (PyDictObject *)op;
3130 PyObject *value;
3131 Py_ssize_t ix;
3132
3133 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
3134 if (ix == DKIX_ERROR)
3135 return -1;
3136 return (ix != DKIX_EMPTY && value != NULL);
3137 }
3138
3139 /* Hack to implement "key in dict" */
3140 static PySequenceMethods dict_as_sequence = {
3141 0, /* sq_length */
3142 0, /* sq_concat */
3143 0, /* sq_repeat */
3144 0, /* sq_item */
3145 0, /* sq_slice */
3146 0, /* sq_ass_item */
3147 0, /* sq_ass_slice */
3148 PyDict_Contains, /* sq_contains */
3149 0, /* sq_inplace_concat */
3150 0, /* sq_inplace_repeat */
3151 };
3152
3153 static PyObject *
3154 dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
3155 {
3156 PyObject *self;
3157 PyDictObject *d;
3158
3159 assert(type != NULL && type->tp_alloc != NULL);
3160 self = type->tp_alloc(type, 0);
3161 if (self == NULL)
3162 return NULL;
3163 d = (PyDictObject *)self;
3164
3165 /* The object has been implicitly tracked by tp_alloc */
3166 if (type == &PyDict_Type)
3167 _PyObject_GC_UNTRACK(d);
3168
3169 d->ma_used = 0;
3170 d->ma_version_tag = DICT_NEXT_VERSION();
3171 d->ma_keys = new_keys_object(PyDict_MINSIZE);
3172 if (d->ma_keys == NULL) {
3173 Py_DECREF(self);
3174 return NULL;
3175 }
3176 assert(_PyDict_CheckConsistency(d));
3177 return self;
3178 }
3179
3180 static int
3181 dict_init(PyObject *self, PyObject *args, PyObject *kwds)
3182 {
3183 return dict_update_common(self, args, kwds, "dict");
3184 }
3185
3186 static PyObject *
3187 dict_iter(PyDictObject *dict)
3188 {
3189 return dictiter_new(dict, &PyDictIterKey_Type);
3190 }
3191
3192 PyDoc_STRVAR(dictionary_doc,
3193 "dict() -> new empty dictionary\n"
3194 "dict(mapping) -> new dictionary initialized from a mapping object's\n"
3195 " (key, value) pairs\n"
3196 "dict(iterable) -> new dictionary initialized as if via:\n"
3197 " d = {}\n"
3198 " for k, v in iterable:\n"
3199 " d[k] = v\n"
3200 "dict(**kwargs) -> new dictionary initialized with the name=value pairs\n"
3201 " in the keyword argument list. For example: dict(one=1, two=2)");
3202
3203 PyTypeObject PyDict_Type = {
3204 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3205 "dict",
3206 sizeof(PyDictObject),
3207 0,
3208 (destructor)dict_dealloc, /* tp_dealloc */
3209 0, /* tp_print */
3210 0, /* tp_getattr */
3211 0, /* tp_setattr */
3212 0, /* tp_reserved */
3213 (reprfunc)dict_repr, /* tp_repr */
3214 0, /* tp_as_number */
3215 &dict_as_sequence, /* tp_as_sequence */
3216 &dict_as_mapping, /* tp_as_mapping */
3217 PyObject_HashNotImplemented, /* tp_hash */
3218 0, /* tp_call */
3219 0, /* tp_str */
3220 PyObject_GenericGetAttr, /* tp_getattro */
3221 0, /* tp_setattro */
3222 0, /* tp_as_buffer */
3223 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
3224 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_DICT_SUBCLASS, /* tp_flags */
3225 dictionary_doc, /* tp_doc */
3226 dict_traverse, /* tp_traverse */
3227 dict_tp_clear, /* tp_clear */
3228 dict_richcompare, /* tp_richcompare */
3229 0, /* tp_weaklistoffset */
3230 (getiterfunc)dict_iter, /* tp_iter */
3231 0, /* tp_iternext */
3232 mapp_methods, /* tp_methods */
3233 0, /* tp_members */
3234 0, /* tp_getset */
3235 0, /* tp_base */
3236 0, /* tp_dict */
3237 0, /* tp_descr_get */
3238 0, /* tp_descr_set */
3239 0, /* tp_dictoffset */
3240 dict_init, /* tp_init */
3241 PyType_GenericAlloc, /* tp_alloc */
3242 dict_new, /* tp_new */
3243 PyObject_GC_Del, /* tp_free */
3244 };
3245
3246 PyObject *
3247 _PyDict_GetItemId(PyObject *dp, struct _Py_Identifier *key)
3248 {
3249 PyObject *kv;
3250 kv = _PyUnicode_FromId(key); /* borrowed */
3251 if (kv == NULL) {
3252 PyErr_Clear();
3253 return NULL;
3254 }
3255 return PyDict_GetItem(dp, kv);
3256 }
3257
3258 /* For backward compatibility with old dictionary interface */
3259
3260 PyObject *
3261 PyDict_GetItemString(PyObject *v, const char *key)
3262 {
3263 PyObject *kv, *rv;
3264 kv = PyUnicode_FromString(key);
3265 if (kv == NULL) {
3266 PyErr_Clear();
3267 return NULL;
3268 }
3269 rv = PyDict_GetItem(v, kv);
3270 Py_DECREF(kv);
3271 return rv;
3272 }
3273
3274 int
3275 _PyDict_SetItemId(PyObject *v, struct _Py_Identifier *key, PyObject *item)
3276 {
3277 PyObject *kv;
3278 kv = _PyUnicode_FromId(key); /* borrowed */
3279 if (kv == NULL)
3280 return -1;
3281 return PyDict_SetItem(v, kv, item);
3282 }
3283
3284 int
3285 PyDict_SetItemString(PyObject *v, const char *key, PyObject *item)
3286 {
3287 PyObject *kv;
3288 int err;
3289 kv = PyUnicode_FromString(key);
3290 if (kv == NULL)
3291 return -1;
3292 PyUnicode_InternInPlace(&kv); /* XXX Should we really? */
3293 err = PyDict_SetItem(v, kv, item);
3294 Py_DECREF(kv);
3295 return err;
3296 }
3297
3298 int
3299 _PyDict_DelItemId(PyObject *v, _Py_Identifier *key)
3300 {
3301 PyObject *kv = _PyUnicode_FromId(key); /* borrowed */
3302 if (kv == NULL)
3303 return -1;
3304 return PyDict_DelItem(v, kv);
3305 }
3306
3307 int
3308 PyDict_DelItemString(PyObject *v, const char *key)
3309 {
3310 PyObject *kv;
3311 int err;
3312 kv = PyUnicode_FromString(key);
3313 if (kv == NULL)
3314 return -1;
3315 err = PyDict_DelItem(v, kv);
3316 Py_DECREF(kv);
3317 return err;
3318 }
3319
3320 /* Dictionary iterator types */
3321
3322 typedef struct {
3323 PyObject_HEAD
3324 PyDictObject *di_dict; /* Set to NULL when iterator is exhausted */
3325 Py_ssize_t di_used;
3326 Py_ssize_t di_pos;
3327 PyObject* di_result; /* reusable result tuple for iteritems */
3328 Py_ssize_t len;
3329 } dictiterobject;
3330
3331 static PyObject *
3332 dictiter_new(PyDictObject *dict, PyTypeObject *itertype)
3333 {
3334 dictiterobject *di;
3335 di = PyObject_GC_New(dictiterobject, itertype);
3336 if (di == NULL)
3337 return NULL;
3338 Py_INCREF(dict);
3339 di->di_dict = dict;
3340 di->di_used = dict->ma_used;
3341 di->di_pos = 0;
3342 di->len = dict->ma_used;
3343 if (itertype == &PyDictIterItem_Type) {
3344 di->di_result = PyTuple_Pack(2, Py_None, Py_None);
3345 if (di->di_result == NULL) {
3346 Py_DECREF(di);
3347 return NULL;
3348 }
3349 }
3350 else
3351 di->di_result = NULL;
3352 _PyObject_GC_TRACK(di);
3353 return (PyObject *)di;
3354 }
3355
3356 static void
3357 dictiter_dealloc(dictiterobject *di)
3358 {
3359 /* bpo-31095: UnTrack is needed before calling any callbacks */
3360 _PyObject_GC_UNTRACK(di);
3361 Py_XDECREF(di->di_dict);
3362 Py_XDECREF(di->di_result);
3363 PyObject_GC_Del(di);
3364 }
3365
3366 static int
3367 dictiter_traverse(dictiterobject *di, visitproc visit, void *arg)
3368 {
3369 Py_VISIT(di->di_dict);
3370 Py_VISIT(di->di_result);
3371 return 0;
3372 }
3373
3374 static PyObject *
3375 dictiter_len(dictiterobject *di)
3376 {
3377 Py_ssize_t len = 0;
3378 if (di->di_dict != NULL && di->di_used == di->di_dict->ma_used)
3379 len = di->len;
3380 return PyLong_FromSize_t(len);
3381 }
3382
3383 PyDoc_STRVAR(length_hint_doc,
3384 "Private method returning an estimate of len(list(it)).");
3385
3386 static PyObject *
3387 dictiter_reduce(dictiterobject *di);
3388
3389 PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
3390
3391 static PyMethodDef dictiter_methods[] = {
3392 {"__length_hint__", (PyCFunction)dictiter_len, METH_NOARGS,
3393 length_hint_doc},
3394 {"__reduce__", (PyCFunction)dictiter_reduce, METH_NOARGS,
3395 reduce_doc},
3396 {NULL, NULL} /* sentinel */
3397 };
3398
3399 static PyObject*
3400 dictiter_iternextkey(dictiterobject *di)
3401 {
3402 PyObject *key;
3403 Py_ssize_t i;
3404 PyDictKeysObject *k;
3405 PyDictObject *d = di->di_dict;
3406
3407 if (d == NULL)
3408 return NULL;
3409 assert (PyDict_Check(d));
3410
3411 if (di->di_used != d->ma_used) {
3412 PyErr_SetString(PyExc_RuntimeError,
3413 "dictionary changed size during iteration");
3414 di->di_used = -1; /* Make this state sticky */
3415 return NULL;
3416 }
3417
3418 i = di->di_pos;
3419 k = d->ma_keys;
3420 assert(i >= 0);
3421 if (d->ma_values) {
3422 if (i >= d->ma_used)
3423 goto fail;
3424 key = DK_ENTRIES(k)[i].me_key;
3425 assert(d->ma_values[i] != NULL);
3426 }
3427 else {
3428 Py_ssize_t n = k->dk_nentries;
3429 PyDictKeyEntry *entry_ptr = &DK_ENTRIES(k)[i];
3430 while (i < n && entry_ptr->me_value == NULL) {
3431 entry_ptr++;
3432 i++;
3433 }
3434 if (i >= n)
3435 goto fail;
3436 key = entry_ptr->me_key;
3437 }
3438 di->di_pos = i+1;
3439 di->len--;
3440 Py_INCREF(key);
3441 return key;
3442
3443 fail:
3444 di->di_dict = NULL;
3445 Py_DECREF(d);
3446 return NULL;
3447 }
3448
3449 PyTypeObject PyDictIterKey_Type = {
3450 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3451 "dict_keyiterator", /* tp_name */
3452 sizeof(dictiterobject), /* tp_basicsize */
3453 0, /* tp_itemsize */
3454 /* methods */
3455 (destructor)dictiter_dealloc, /* tp_dealloc */
3456 0, /* tp_print */
3457 0, /* tp_getattr */
3458 0, /* tp_setattr */
3459 0, /* tp_reserved */
3460 0, /* tp_repr */
3461 0, /* tp_as_number */
3462 0, /* tp_as_sequence */
3463 0, /* tp_as_mapping */
3464 0, /* tp_hash */
3465 0, /* tp_call */
3466 0, /* tp_str */
3467 PyObject_GenericGetAttr, /* tp_getattro */
3468 0, /* tp_setattro */
3469 0, /* tp_as_buffer */
3470 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3471 0, /* tp_doc */
3472 (traverseproc)dictiter_traverse, /* tp_traverse */
3473 0, /* tp_clear */
3474 0, /* tp_richcompare */
3475 0, /* tp_weaklistoffset */
3476 PyObject_SelfIter, /* tp_iter */
3477 (iternextfunc)dictiter_iternextkey, /* tp_iternext */
3478 dictiter_methods, /* tp_methods */
3479 0,
3480 };
3481
3482 static PyObject *
3483 dictiter_iternextvalue(dictiterobject *di)
3484 {
3485 PyObject *value;
3486 Py_ssize_t i;
3487 PyDictObject *d = di->di_dict;
3488
3489 if (d == NULL)
3490 return NULL;
3491 assert (PyDict_Check(d));
3492
3493 if (di->di_used != d->ma_used) {
3494 PyErr_SetString(PyExc_RuntimeError,
3495 "dictionary changed size during iteration");
3496 di->di_used = -1; /* Make this state sticky */
3497 return NULL;
3498 }
3499
3500 i = di->di_pos;
3501 assert(i >= 0);
3502 if (d->ma_values) {
3503 if (i >= d->ma_used)
3504 goto fail;
3505 value = d->ma_values[i];
3506 assert(value != NULL);
3507 }
3508 else {
3509 Py_ssize_t n = d->ma_keys->dk_nentries;
3510 PyDictKeyEntry *entry_ptr = &DK_ENTRIES(d->ma_keys)[i];
3511 while (i < n && entry_ptr->me_value == NULL) {
3512 entry_ptr++;
3513 i++;
3514 }
3515 if (i >= n)
3516 goto fail;
3517 value = entry_ptr->me_value;
3518 }
3519 di->di_pos = i+1;
3520 di->len--;
3521 Py_INCREF(value);
3522 return value;
3523
3524 fail:
3525 di->di_dict = NULL;
3526 Py_DECREF(d);
3527 return NULL;
3528 }
3529
3530 PyTypeObject PyDictIterValue_Type = {
3531 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3532 "dict_valueiterator", /* tp_name */
3533 sizeof(dictiterobject), /* tp_basicsize */
3534 0, /* tp_itemsize */
3535 /* methods */
3536 (destructor)dictiter_dealloc, /* tp_dealloc */
3537 0, /* tp_print */
3538 0, /* tp_getattr */
3539 0, /* tp_setattr */
3540 0, /* tp_reserved */
3541 0, /* tp_repr */
3542 0, /* tp_as_number */
3543 0, /* tp_as_sequence */
3544 0, /* tp_as_mapping */
3545 0, /* tp_hash */
3546 0, /* tp_call */
3547 0, /* tp_str */
3548 PyObject_GenericGetAttr, /* tp_getattro */
3549 0, /* tp_setattro */
3550 0, /* tp_as_buffer */
3551 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
3552 0, /* tp_doc */
3553 (traverseproc)dictiter_traverse, /* tp_traverse */
3554 0, /* tp_clear */
3555 0, /* tp_richcompare */
3556 0, /* tp_weaklistoffset */
3557 PyObject_SelfIter, /* tp_iter */
3558 (iternextfunc)dictiter_iternextvalue, /* tp_iternext */
3559 dictiter_methods, /* tp_methods */
3560 0,
3561 };
3562
3563 static PyObject *
3564 dictiter_iternextitem(dictiterobject *di)
3565 {
3566 PyObject *key, *value, *result;
3567 Py_ssize_t i;
3568 PyDictObject *d = di->di_dict;
3569
3570 if (d == NULL)
3571 return NULL;
3572 assert (PyDict_Check(d));
3573
3574 if (di->di_used != d->ma_used) {
3575 PyErr_SetString(PyExc_RuntimeError,
3576 "dictionary changed size during iteration");
3577 di->di_used = -1; /* Make this state sticky */
3578 return NULL;
3579 }
3580
3581 i = di->di_pos;
3582 assert(i >= 0);
3583 if (d->ma_values) {
3584 if (i >= d->ma_used)
3585 goto fail;
3586 key = DK_ENTRIES(d->ma_keys)[i].me_key;
3587 value = d->ma_values[i];
3588 assert(value != NULL);
3589 }
3590 else {
3591 Py_ssize_t n = d->ma_keys->dk_nentries;
3592 PyDictKeyEntry *entry_ptr = &DK_ENTRIES(d->ma_keys)[i];
3593 while (i < n && entry_ptr->me_value == NULL) {
3594 entry_ptr++;
3595 i++;
3596 }
3597 if (i >= n)
3598 goto fail;
3599 key = entry_ptr->me_key;
3600 value = entry_ptr->me_value;
3601 }
3602 di->di_pos = i+1;
3603 di->len--;
3604 Py_INCREF(key);
3605 Py_INCREF(value);
3606 result = di->di_result;
3607 if (Py_REFCNT(result) == 1) {
3608 PyObject *oldkey = PyTuple_GET_ITEM(result, 0);
3609 PyObject *oldvalue = PyTuple_GET_ITEM(result, 1);
3610 PyTuple_SET_ITEM(result, 0, key); /* steals reference */
3611 PyTuple_SET_ITEM(result, 1, value); /* steals reference */
3612 Py_INCREF(result);
3613 Py_DECREF(oldkey);
3614 Py_DECREF(oldvalue);
3615 }
3616 else {
3617 result = PyTuple_New(2);
3618 if (result == NULL)
3619 return NULL;
3620 PyTuple_SET_ITEM(result, 0, key); /* steals reference */
3621 PyTuple_SET_ITEM(result, 1, value); /* steals reference */
3622 }
3623 return result;
3624
3625 fail:
3626 di->di_dict = NULL;
3627 Py_DECREF(d);
3628 return NULL;
3629 }
3630
3631 PyTypeObject PyDictIterItem_Type = {
3632 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3633 "dict_itemiterator", /* tp_name */
3634 sizeof(dictiterobject), /* tp_basicsize */
3635 0, /* tp_itemsize */
3636 /* methods */
3637 (destructor)dictiter_dealloc, /* tp_dealloc */
3638 0, /* tp_print */
3639 0, /* tp_getattr */
3640 0, /* tp_setattr */
3641 0, /* tp_reserved */
3642 0, /* tp_repr */
3643 0, /* tp_as_number */
3644 0, /* tp_as_sequence */
3645 0, /* tp_as_mapping */
3646 0, /* tp_hash */
3647 0, /* tp_call */
3648 0, /* tp_str */
3649 PyObject_GenericGetAttr, /* tp_getattro */
3650 0, /* tp_setattro */
3651 0, /* tp_as_buffer */
3652 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3653 0, /* tp_doc */
3654 (traverseproc)dictiter_traverse, /* tp_traverse */
3655 0, /* tp_clear */
3656 0, /* tp_richcompare */
3657 0, /* tp_weaklistoffset */
3658 PyObject_SelfIter, /* tp_iter */
3659 (iternextfunc)dictiter_iternextitem, /* tp_iternext */
3660 dictiter_methods, /* tp_methods */
3661 0,
3662 };
3663
3664
3665 static PyObject *
3666 dictiter_reduce(dictiterobject *di)
3667 {
3668 PyObject *list;
3669 dictiterobject tmp;
3670
3671 list = PyList_New(0);
3672 if (!list)
3673 return NULL;
3674
3675 /* copy the itertor state */
3676 tmp = *di;
3677 Py_XINCREF(tmp.di_dict);
3678
3679 /* iterate the temporary into a list */
3680 for(;;) {
3681 PyObject *element = 0;
3682 if (Py_TYPE(di) == &PyDictIterItem_Type)
3683 element = dictiter_iternextitem(&tmp);
3684 else if (Py_TYPE(di) == &PyDictIterKey_Type)
3685 element = dictiter_iternextkey(&tmp);
3686 else if (Py_TYPE(di) == &PyDictIterValue_Type)
3687 element = dictiter_iternextvalue(&tmp);
3688 else
3689 Py_UNREACHABLE();
3690 if (element) {
3691 if (PyList_Append(list, element)) {
3692 Py_DECREF(element);
3693 Py_DECREF(list);
3694 Py_XDECREF(tmp.di_dict);
3695 return NULL;
3696 }
3697 Py_DECREF(element);
3698 } else
3699 break;
3700 }
3701 Py_XDECREF(tmp.di_dict);
3702 /* check for error */
3703 if (tmp.di_dict != NULL) {
3704 /* we have an error */
3705 Py_DECREF(list);
3706 return NULL;
3707 }
3708 return Py_BuildValue("N(N)", _PyObject_GetBuiltin("iter"), list);
3709 }
3710
3711 /***********************************************/
3712 /* View objects for keys(), items(), values(). */
3713 /***********************************************/
3714
3715 /* The instance lay-out is the same for all three; but the type differs. */
3716
3717 static void
3718 dictview_dealloc(_PyDictViewObject *dv)
3719 {
3720 /* bpo-31095: UnTrack is needed before calling any callbacks */
3721 _PyObject_GC_UNTRACK(dv);
3722 Py_XDECREF(dv->dv_dict);
3723 PyObject_GC_Del(dv);
3724 }
3725
3726 static int
3727 dictview_traverse(_PyDictViewObject *dv, visitproc visit, void *arg)
3728 {
3729 Py_VISIT(dv->dv_dict);
3730 return 0;
3731 }
3732
3733 static Py_ssize_t
3734 dictview_len(_PyDictViewObject *dv)
3735 {
3736 Py_ssize_t len = 0;
3737 if (dv->dv_dict != NULL)
3738 len = dv->dv_dict->ma_used;
3739 return len;
3740 }
3741
3742 PyObject *
3743 _PyDictView_New(PyObject *dict, PyTypeObject *type)
3744 {
3745 _PyDictViewObject *dv;
3746 if (dict == NULL) {
3747 PyErr_BadInternalCall();
3748 return NULL;
3749 }
3750 if (!PyDict_Check(dict)) {
3751 /* XXX Get rid of this restriction later */
3752 PyErr_Format(PyExc_TypeError,
3753 "%s() requires a dict argument, not '%s'",
3754 type->tp_name, dict->ob_type->tp_name);
3755 return NULL;
3756 }
3757 dv = PyObject_GC_New(_PyDictViewObject, type);
3758 if (dv == NULL)
3759 return NULL;
3760 Py_INCREF(dict);
3761 dv->dv_dict = (PyDictObject *)dict;
3762 _PyObject_GC_TRACK(dv);
3763 return (PyObject *)dv;
3764 }
3765
3766 /* TODO(guido): The views objects are not complete:
3767
3768 * support more set operations
3769 * support arbitrary mappings?
3770 - either these should be static or exported in dictobject.h
3771 - if public then they should probably be in builtins
3772 */
3773
3774 /* Return 1 if self is a subset of other, iterating over self;
3775 0 if not; -1 if an error occurred. */
3776 static int
3777 all_contained_in(PyObject *self, PyObject *other)
3778 {
3779 PyObject *iter = PyObject_GetIter(self);
3780 int ok = 1;
3781
3782 if (iter == NULL)
3783 return -1;
3784 for (;;) {
3785 PyObject *next = PyIter_Next(iter);
3786 if (next == NULL) {
3787 if (PyErr_Occurred())
3788 ok = -1;
3789 break;
3790 }
3791 ok = PySequence_Contains(other, next);
3792 Py_DECREF(next);
3793 if (ok <= 0)
3794 break;
3795 }
3796 Py_DECREF(iter);
3797 return ok;
3798 }
3799
3800 static PyObject *
3801 dictview_richcompare(PyObject *self, PyObject *other, int op)
3802 {
3803 Py_ssize_t len_self, len_other;
3804 int ok;
3805 PyObject *result;
3806
3807 assert(self != NULL);
3808 assert(PyDictViewSet_Check(self));
3809 assert(other != NULL);
3810
3811 if (!PyAnySet_Check(other) && !PyDictViewSet_Check(other))
3812 Py_RETURN_NOTIMPLEMENTED;
3813
3814 len_self = PyObject_Size(self);
3815 if (len_self < 0)
3816 return NULL;
3817 len_other = PyObject_Size(other);
3818 if (len_other < 0)
3819 return NULL;
3820
3821 ok = 0;
3822 switch(op) {
3823
3824 case Py_NE:
3825 case Py_EQ:
3826 if (len_self == len_other)
3827 ok = all_contained_in(self, other);
3828 if (op == Py_NE && ok >= 0)
3829 ok = !ok;
3830 break;
3831
3832 case Py_LT:
3833 if (len_self < len_other)
3834 ok = all_contained_in(self, other);
3835 break;
3836
3837 case Py_LE:
3838 if (len_self <= len_other)
3839 ok = all_contained_in(self, other);
3840 break;
3841
3842 case Py_GT:
3843 if (len_self > len_other)
3844 ok = all_contained_in(other, self);
3845 break;
3846
3847 case Py_GE:
3848 if (len_self >= len_other)
3849 ok = all_contained_in(other, self);
3850 break;
3851
3852 }
3853 if (ok < 0)
3854 return NULL;
3855 result = ok ? Py_True : Py_False;
3856 Py_INCREF(result);
3857 return result;
3858 }
3859
3860 static PyObject *
3861 dictview_repr(_PyDictViewObject *dv)
3862 {
3863 PyObject *seq;
3864 PyObject *result = NULL;
3865 Py_ssize_t rc;
3866
3867 rc = Py_ReprEnter((PyObject *)dv);
3868 if (rc != 0) {
3869 return rc > 0 ? PyUnicode_FromString("...") : NULL;
3870 }
3871 seq = PySequence_List((PyObject *)dv);
3872 if (seq == NULL) {
3873 goto Done;
3874 }
3875 result = PyUnicode_FromFormat("%s(%R)", Py_TYPE(dv)->tp_name, seq);
3876 Py_DECREF(seq);
3877
3878 Done:
3879 Py_ReprLeave((PyObject *)dv);
3880 return result;
3881 }
3882
3883 /*** dict_keys ***/
3884
3885 static PyObject *
3886 dictkeys_iter(_PyDictViewObject *dv)
3887 {
3888 if (dv->dv_dict == NULL) {
3889 Py_RETURN_NONE;
3890 }
3891 return dictiter_new(dv->dv_dict, &PyDictIterKey_Type);
3892 }
3893
3894 static int
3895 dictkeys_contains(_PyDictViewObject *dv, PyObject *obj)
3896 {
3897 if (dv->dv_dict == NULL)
3898 return 0;
3899 return PyDict_Contains((PyObject *)dv->dv_dict, obj);
3900 }
3901
3902 static PySequenceMethods dictkeys_as_sequence = {
3903 (lenfunc)dictview_len, /* sq_length */
3904 0, /* sq_concat */
3905 0, /* sq_repeat */
3906 0, /* sq_item */
3907 0, /* sq_slice */
3908 0, /* sq_ass_item */
3909 0, /* sq_ass_slice */
3910 (objobjproc)dictkeys_contains, /* sq_contains */
3911 };
3912
3913 static PyObject*
3914 dictviews_sub(PyObject* self, PyObject *other)
3915 {
3916 PyObject *result = PySet_New(self);
3917 PyObject *tmp;
3918 _Py_IDENTIFIER(difference_update);
3919
3920 if (result == NULL)
3921 return NULL;
3922
3923 tmp = _PyObject_CallMethodIdObjArgs(result, &PyId_difference_update, other, NULL);
3924 if (tmp == NULL) {
3925 Py_DECREF(result);
3926 return NULL;
3927 }
3928
3929 Py_DECREF(tmp);
3930 return result;
3931 }
3932
3933 PyObject*
3934 _PyDictView_Intersect(PyObject* self, PyObject *other)
3935 {
3936 PyObject *result = PySet_New(self);
3937 PyObject *tmp;
3938 _Py_IDENTIFIER(intersection_update);
3939
3940 if (result == NULL)
3941 return NULL;
3942
3943 tmp = _PyObject_CallMethodIdObjArgs(result, &PyId_intersection_update, other, NULL);
3944 if (tmp == NULL) {
3945 Py_DECREF(result);
3946 return NULL;
3947 }
3948
3949 Py_DECREF(tmp);
3950 return result;
3951 }
3952
3953 static PyObject*
3954 dictviews_or(PyObject* self, PyObject *other)
3955 {
3956 PyObject *result = PySet_New(self);
3957 PyObject *tmp;
3958 _Py_IDENTIFIER(update);
3959
3960 if (result == NULL)
3961 return NULL;
3962
3963 tmp = _PyObject_CallMethodIdObjArgs(result, &PyId_update, other, NULL);
3964 if (tmp == NULL) {
3965 Py_DECREF(result);
3966 return NULL;
3967 }
3968
3969 Py_DECREF(tmp);
3970 return result;
3971 }
3972
3973 static PyObject*
3974 dictviews_xor(PyObject* self, PyObject *other)
3975 {
3976 PyObject *result = PySet_New(self);
3977 PyObject *tmp;
3978 _Py_IDENTIFIER(symmetric_difference_update);
3979
3980 if (result == NULL)
3981 return NULL;
3982
3983 tmp = _PyObject_CallMethodIdObjArgs(result, &PyId_symmetric_difference_update, other, NULL);
3984 if (tmp == NULL) {
3985 Py_DECREF(result);
3986 return NULL;
3987 }
3988
3989 Py_DECREF(tmp);
3990 return result;
3991 }
3992
3993 static PyNumberMethods dictviews_as_number = {
3994 0, /*nb_add*/
3995 (binaryfunc)dictviews_sub, /*nb_subtract*/
3996 0, /*nb_multiply*/
3997 0, /*nb_remainder*/
3998 0, /*nb_divmod*/
3999 0, /*nb_power*/
4000 0, /*nb_negative*/
4001 0, /*nb_positive*/
4002 0, /*nb_absolute*/
4003 0, /*nb_bool*/
4004 0, /*nb_invert*/
4005 0, /*nb_lshift*/
4006 0, /*nb_rshift*/
4007 (binaryfunc)_PyDictView_Intersect, /*nb_and*/
4008 (binaryfunc)dictviews_xor, /*nb_xor*/
4009 (binaryfunc)dictviews_or, /*nb_or*/
4010 };
4011
4012 static PyObject*
4013 dictviews_isdisjoint(PyObject *self, PyObject *other)
4014 {
4015 PyObject *it;
4016 PyObject *item = NULL;
4017
4018 if (self == other) {
4019 if (dictview_len((_PyDictViewObject *)self) == 0)
4020 Py_RETURN_TRUE;
4021 else
4022 Py_RETURN_FALSE;
4023 }
4024
4025 /* Iterate over the shorter object (only if other is a set,
4026 * because PySequence_Contains may be expensive otherwise): */
4027 if (PyAnySet_Check(other) || PyDictViewSet_Check(other)) {
4028 Py_ssize_t len_self = dictview_len((_PyDictViewObject *)self);
4029 Py_ssize_t len_other = PyObject_Size(other);
4030 if (len_other == -1)
4031 return NULL;
4032
4033 if ((len_other > len_self)) {
4034 PyObject *tmp = other;
4035 other = self;
4036 self = tmp;
4037 }
4038 }
4039
4040 it = PyObject_GetIter(other);
4041 if (it == NULL)
4042 return NULL;
4043
4044 while ((item = PyIter_Next(it)) != NULL) {
4045 int contains = PySequence_Contains(self, item);
4046 Py_DECREF(item);
4047 if (contains == -1) {
4048 Py_DECREF(it);
4049 return NULL;
4050 }
4051
4052 if (contains) {
4053 Py_DECREF(it);
4054 Py_RETURN_FALSE;
4055 }
4056 }
4057 Py_DECREF(it);
4058 if (PyErr_Occurred())
4059 return NULL; /* PyIter_Next raised an exception. */
4060 Py_RETURN_TRUE;
4061 }
4062
4063 PyDoc_STRVAR(isdisjoint_doc,
4064 "Return True if the view and the given iterable have a null intersection.");
4065
4066 static PyMethodDef dictkeys_methods[] = {
4067 {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
4068 isdisjoint_doc},
4069 {NULL, NULL} /* sentinel */
4070 };
4071
4072 PyTypeObject PyDictKeys_Type = {
4073 PyVarObject_HEAD_INIT(&PyType_Type, 0)
4074 "dict_keys", /* tp_name */
4075 sizeof(_PyDictViewObject), /* tp_basicsize */
4076 0, /* tp_itemsize */
4077 /* methods */
4078 (destructor)dictview_dealloc, /* tp_dealloc */
4079 0, /* tp_print */
4080 0, /* tp_getattr */
4081 0, /* tp_setattr */
4082 0, /* tp_reserved */
4083 (reprfunc)dictview_repr, /* tp_repr */
4084 &dictviews_as_number, /* tp_as_number */
4085 &dictkeys_as_sequence, /* tp_as_sequence */
4086 0, /* tp_as_mapping */
4087 0, /* tp_hash */
4088 0, /* tp_call */
4089 0, /* tp_str */
4090 PyObject_GenericGetAttr, /* tp_getattro */
4091 0, /* tp_setattro */
4092 0, /* tp_as_buffer */
4093 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
4094 0, /* tp_doc */
4095 (traverseproc)dictview_traverse, /* tp_traverse */
4096 0, /* tp_clear */
4097 dictview_richcompare, /* tp_richcompare */
4098 0, /* tp_weaklistoffset */
4099 (getiterfunc)dictkeys_iter, /* tp_iter */
4100 0, /* tp_iternext */
4101 dictkeys_methods, /* tp_methods */
4102 0,
4103 };
4104
4105 static PyObject *
4106 dictkeys_new(PyObject *dict)
4107 {
4108 return _PyDictView_New(dict, &PyDictKeys_Type);
4109 }
4110
4111 /*** dict_items ***/
4112
4113 static PyObject *
4114 dictitems_iter(_PyDictViewObject *dv)
4115 {
4116 if (dv->dv_dict == NULL) {
4117 Py_RETURN_NONE;
4118 }
4119 return dictiter_new(dv->dv_dict, &PyDictIterItem_Type);
4120 }
4121
4122 static int
4123 dictitems_contains(_PyDictViewObject *dv, PyObject *obj)
4124 {
4125 int result;
4126 PyObject *key, *value, *found;
4127 if (dv->dv_dict == NULL)
4128 return 0;
4129 if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 2)
4130 return 0;
4131 key = PyTuple_GET_ITEM(obj, 0);
4132 value = PyTuple_GET_ITEM(obj, 1);
4133 found = PyDict_GetItemWithError((PyObject *)dv->dv_dict, key);
4134 if (found == NULL) {
4135 if (PyErr_Occurred())
4136 return -1;
4137 return 0;
4138 }
4139 Py_INCREF(found);
4140 result = PyObject_RichCompareBool(value, found, Py_EQ);
4141 Py_DECREF(found);
4142 return result;
4143 }
4144
4145 static PySequenceMethods dictitems_as_sequence = {
4146 (lenfunc)dictview_len, /* sq_length */
4147 0, /* sq_concat */
4148 0, /* sq_repeat */
4149 0, /* sq_item */
4150 0, /* sq_slice */
4151 0, /* sq_ass_item */
4152 0, /* sq_ass_slice */
4153 (objobjproc)dictitems_contains, /* sq_contains */
4154 };
4155
4156 static PyMethodDef dictitems_methods[] = {
4157 {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
4158 isdisjoint_doc},
4159 {NULL, NULL} /* sentinel */
4160 };
4161
4162 PyTypeObject PyDictItems_Type = {
4163 PyVarObject_HEAD_INIT(&PyType_Type, 0)
4164 "dict_items", /* tp_name */
4165 sizeof(_PyDictViewObject), /* tp_basicsize */
4166 0, /* tp_itemsize */
4167 /* methods */
4168 (destructor)dictview_dealloc, /* tp_dealloc */
4169 0, /* tp_print */
4170 0, /* tp_getattr */
4171 0, /* tp_setattr */
4172 0, /* tp_reserved */
4173 (reprfunc)dictview_repr, /* tp_repr */
4174 &dictviews_as_number, /* tp_as_number */
4175 &dictitems_as_sequence, /* tp_as_sequence */
4176 0, /* tp_as_mapping */
4177 0, /* tp_hash */
4178 0, /* tp_call */
4179 0, /* tp_str */
4180 PyObject_GenericGetAttr, /* tp_getattro */
4181 0, /* tp_setattro */
4182 0, /* tp_as_buffer */
4183 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
4184 0, /* tp_doc */
4185 (traverseproc)dictview_traverse, /* tp_traverse */
4186 0, /* tp_clear */
4187 dictview_richcompare, /* tp_richcompare */
4188 0, /* tp_weaklistoffset */
4189 (getiterfunc)dictitems_iter, /* tp_iter */
4190 0, /* tp_iternext */
4191 dictitems_methods, /* tp_methods */
4192 0,
4193 };
4194
4195 static PyObject *
4196 dictitems_new(PyObject *dict)
4197 {
4198 return _PyDictView_New(dict, &PyDictItems_Type);
4199 }
4200
4201 /*** dict_values ***/
4202
4203 static PyObject *
4204 dictvalues_iter(_PyDictViewObject *dv)
4205 {
4206 if (dv->dv_dict == NULL) {
4207 Py_RETURN_NONE;
4208 }
4209 return dictiter_new(dv->dv_dict, &PyDictIterValue_Type);
4210 }
4211
4212 static PySequenceMethods dictvalues_as_sequence = {
4213 (lenfunc)dictview_len, /* sq_length */
4214 0, /* sq_concat */
4215 0, /* sq_repeat */
4216 0, /* sq_item */
4217 0, /* sq_slice */
4218 0, /* sq_ass_item */
4219 0, /* sq_ass_slice */
4220 (objobjproc)0, /* sq_contains */
4221 };
4222
4223 static PyMethodDef dictvalues_methods[] = {
4224 {NULL, NULL} /* sentinel */
4225 };
4226
4227 PyTypeObject PyDictValues_Type = {
4228 PyVarObject_HEAD_INIT(&PyType_Type, 0)
4229 "dict_values", /* tp_name */
4230 sizeof(_PyDictViewObject), /* tp_basicsize */
4231 0, /* tp_itemsize */
4232 /* methods */
4233 (destructor)dictview_dealloc, /* tp_dealloc */
4234 0, /* tp_print */
4235 0, /* tp_getattr */
4236 0, /* tp_setattr */
4237 0, /* tp_reserved */
4238 (reprfunc)dictview_repr, /* tp_repr */
4239 0, /* tp_as_number */
4240 &dictvalues_as_sequence, /* tp_as_sequence */
4241 0, /* tp_as_mapping */
4242 0, /* tp_hash */
4243 0, /* tp_call */
4244 0, /* tp_str */
4245 PyObject_GenericGetAttr, /* tp_getattro */
4246 0, /* tp_setattro */
4247 0, /* tp_as_buffer */
4248 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
4249 0, /* tp_doc */
4250 (traverseproc)dictview_traverse, /* tp_traverse */
4251 0, /* tp_clear */
4252 0, /* tp_richcompare */
4253 0, /* tp_weaklistoffset */
4254 (getiterfunc)dictvalues_iter, /* tp_iter */
4255 0, /* tp_iternext */
4256 dictvalues_methods, /* tp_methods */
4257 0,
4258 };
4259
4260 static PyObject *
4261 dictvalues_new(PyObject *dict)
4262 {
4263 return _PyDictView_New(dict, &PyDictValues_Type);
4264 }
4265
4266 /* Returns NULL if cannot allocate a new PyDictKeysObject,
4267 but does not set an error */
4268 PyDictKeysObject *
4269 _PyDict_NewKeysForClass(void)
4270 {
4271 PyDictKeysObject *keys = new_keys_object(PyDict_MINSIZE);
4272 if (keys == NULL)
4273 PyErr_Clear();
4274 else
4275 keys->dk_lookup = lookdict_split;
4276 return keys;
4277 }
4278
4279 #define CACHED_KEYS(tp) (((PyHeapTypeObject*)tp)->ht_cached_keys)
4280
4281 PyObject *
4282 PyObject_GenericGetDict(PyObject *obj, void *context)
4283 {
4284 PyObject *dict, **dictptr = _PyObject_GetDictPtr(obj);
4285 if (dictptr == NULL) {
4286 PyErr_SetString(PyExc_AttributeError,
4287 "This object has no __dict__");
4288 return NULL;
4289 }
4290 dict = *dictptr;
4291 if (dict == NULL) {
4292 PyTypeObject *tp = Py_TYPE(obj);
4293 if ((tp->tp_flags & Py_TPFLAGS_HEAPTYPE) && CACHED_KEYS(tp)) {
4294 DK_INCREF(CACHED_KEYS(tp));
4295 *dictptr = dict = new_dict_with_shared_keys(CACHED_KEYS(tp));
4296 }
4297 else {
4298 *dictptr = dict = PyDict_New();
4299 }
4300 }
4301 Py_XINCREF(dict);
4302 return dict;
4303 }
4304
4305 int
4306 _PyObjectDict_SetItem(PyTypeObject *tp, PyObject **dictptr,
4307 PyObject *key, PyObject *value)
4308 {
4309 PyObject *dict;
4310 int res;
4311 PyDictKeysObject *cached;
4312
4313 assert(dictptr != NULL);
4314 if ((tp->tp_flags & Py_TPFLAGS_HEAPTYPE) && (cached = CACHED_KEYS(tp))) {
4315 assert(dictptr != NULL);
4316 dict = *dictptr;
4317 if (dict == NULL) {
4318 DK_INCREF(cached);
4319 dict = new_dict_with_shared_keys(cached);
4320 if (dict == NULL)
4321 return -1;
4322 *dictptr = dict;
4323 }
4324 if (value == NULL) {
4325 res = PyDict_DelItem(dict, key);
4326 // Since key sharing dict doesn't allow deletion, PyDict_DelItem()
4327 // always converts dict to combined form.
4328 if ((cached = CACHED_KEYS(tp)) != NULL) {
4329 CACHED_KEYS(tp) = NULL;
4330 DK_DECREF(cached);
4331 }
4332 }
4333 else {
4334 int was_shared = (cached == ((PyDictObject *)dict)->ma_keys);
4335 res = PyDict_SetItem(dict, key, value);
4336 if (was_shared &&
4337 (cached = CACHED_KEYS(tp)) != NULL &&
4338 cached != ((PyDictObject *)dict)->ma_keys) {
4339 /* PyDict_SetItem() may call dictresize and convert split table
4340 * into combined table. In such case, convert it to split
4341 * table again and update type's shared key only when this is
4342 * the only dict sharing key with the type.
4343 *
4344 * This is to allow using shared key in class like this:
4345 *
4346 * class C:
4347 * def __init__(self):
4348 * # one dict resize happens
4349 * self.a, self.b, self.c = 1, 2, 3
4350 * self.d, self.e, self.f = 4, 5, 6
4351 * a = C()
4352 */
4353 if (cached->dk_refcnt == 1) {
4354 CACHED_KEYS(tp) = make_keys_shared(dict);
4355 }
4356 else {
4357 CACHED_KEYS(tp) = NULL;
4358 }
4359 DK_DECREF(cached);
4360 if (CACHED_KEYS(tp) == NULL && PyErr_Occurred())
4361 return -1;
4362 }
4363 }
4364 } else {
4365 dict = *dictptr;
4366 if (dict == NULL) {
4367 dict = PyDict_New();
4368 if (dict == NULL)
4369 return -1;
4370 *dictptr = dict;
4371 }
4372 if (value == NULL) {
4373 res = PyDict_DelItem(dict, key);
4374 } else {
4375 res = PyDict_SetItem(dict, key, value);
4376 }
4377 }
4378 return res;
4379 }
4380
4381 void
4382 _PyDictKeys_DecRef(PyDictKeysObject *keys)
4383 {
4384 DK_DECREF(keys);
4385 }