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