Line data Source code
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_log2_size |
22 : | dk_log2_index_bytes |
23 : | dk_kind |
24 : | dk_usable |
25 : | dk_nentries |
26 : +---------------------+
27 : | dk_indices[] |
28 : | |
29 : +---------------------+
30 : | dk_entries[] |
31 : | |
32 : +---------------------+
33 :
34 : dk_indices is actual hashtable. It holds index in entries, or DKIX_EMPTY(-1)
35 : or DKIX_DUMMY(-2).
36 : Size of indices is dk_size. Type of each index in indices is vary on dk_size:
37 :
38 : * int8 for dk_size <= 128
39 : * int16 for 256 <= dk_size <= 2**15
40 : * int32 for 2**16 <= dk_size <= 2**31
41 : * int64 for 2**32 <= dk_size
42 :
43 : dk_entries is array of PyDictKeyEntry when dk_kind == DICT_KEYS_GENERAL or
44 : PyDictUnicodeEntry otherwise. Its length is USABLE_FRACTION(dk_size).
45 :
46 : NOTE: Since negative value is used for DKIX_EMPTY and DKIX_DUMMY, type of
47 : dk_indices entry is signed integer and int16 is used for table which
48 : dk_size == 256.
49 : */
50 :
51 :
52 : /*
53 : The DictObject can be in one of two forms.
54 :
55 : Either:
56 : A combined table:
57 : ma_values == NULL, dk_refcnt == 1.
58 : Values are stored in the me_value field of the PyDictKeysObject.
59 : Or:
60 : A split table:
61 : ma_values != NULL, dk_refcnt >= 1
62 : Values are stored in the ma_values array.
63 : Only string (unicode) keys are allowed.
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 : To preserve the order in a split table, a bit vector is used to record the
100 : insertion order. When a key is inserted the bit vector is shifted up by 4 bits
101 : and the index of the key is stored in the low 4 bits.
102 : As a consequence of this, split keys have a maximum size of 16.
103 : */
104 :
105 : /* PyDict_MINSIZE is the starting size for any new dict.
106 : * 8 allows dicts with no more than 5 active entries; experiments suggested
107 : * this suffices for the majority of dicts (consisting mostly of usually-small
108 : * dicts created to pass keyword arguments).
109 : * Making this 8, rather than 4 reduces the number of resizes for most
110 : * dictionaries, without any significant extra memory use.
111 : */
112 : #define PyDict_LOG_MINSIZE 3
113 : #define PyDict_MINSIZE 8
114 :
115 : #include "Python.h"
116 : #include "pycore_bitutils.h" // _Py_bit_length
117 : #include "pycore_call.h" // _PyObject_CallNoArgs()
118 : #include "pycore_code.h" // stats
119 : #include "pycore_dict.h" // PyDictKeysObject
120 : #include "pycore_gc.h" // _PyObject_GC_IS_TRACKED()
121 : #include "pycore_object.h" // _PyObject_GC_TRACK()
122 : #include "pycore_pyerrors.h" // _PyErr_Fetch()
123 : #include "pycore_pystate.h" // _PyThreadState_GET()
124 : #include "stringlib/eq.h" // unicode_eq()
125 :
126 : #include <stdbool.h>
127 :
128 : /*[clinic input]
129 : class dict "PyDictObject *" "&PyDict_Type"
130 : [clinic start generated code]*/
131 : /*[clinic end generated code: output=da39a3ee5e6b4b0d input=f157a5a0ce9589d6]*/
132 :
133 :
134 : /*
135 : To ensure the lookup algorithm terminates, there must be at least one Unused
136 : slot (NULL key) in the table.
137 : To avoid slowing down lookups on a near-full table, we resize the table when
138 : it's USABLE_FRACTION (currently two-thirds) full.
139 : */
140 :
141 : #define PERTURB_SHIFT 5
142 :
143 : /*
144 : Major subtleties ahead: Most hash schemes depend on having a "good" hash
145 : function, in the sense of simulating randomness. Python doesn't: its most
146 : important hash functions (for ints) are very regular in common
147 : cases:
148 :
149 : >>>[hash(i) for i in range(4)]
150 : [0, 1, 2, 3]
151 :
152 : This isn't necessarily bad! To the contrary, in a table of size 2**i, taking
153 : the low-order i bits as the initial table index is extremely fast, and there
154 : are no collisions at all for dicts indexed by a contiguous range of ints. So
155 : this gives better-than-random behavior in common cases, and that's very
156 : desirable.
157 :
158 : OTOH, when collisions occur, the tendency to fill contiguous slices of the
159 : hash table makes a good collision resolution strategy crucial. Taking only
160 : the last i bits of the hash code is also vulnerable: for example, consider
161 : the list [i << 16 for i in range(20000)] as a set of keys. Since ints are
162 : their own hash codes, and this fits in a dict of size 2**15, the last 15 bits
163 : of every hash code are all 0: they *all* map to the same table index.
164 :
165 : But catering to unusual cases should not slow the usual ones, so we just take
166 : the last i bits anyway. It's up to collision resolution to do the rest. If
167 : we *usually* find the key we're looking for on the first try (and, it turns
168 : out, we usually do -- the table load factor is kept under 2/3, so the odds
169 : are solidly in our favor), then it makes best sense to keep the initial index
170 : computation dirt cheap.
171 :
172 : The first half of collision resolution is to visit table indices via this
173 : recurrence:
174 :
175 : j = ((5*j) + 1) mod 2**i
176 :
177 : For any initial j in range(2**i), repeating that 2**i times generates each
178 : int in range(2**i) exactly once (see any text on random-number generation for
179 : proof). By itself, this doesn't help much: like linear probing (setting
180 : j += 1, or j -= 1, on each loop trip), it scans the table entries in a fixed
181 : order. This would be bad, except that's not the only thing we do, and it's
182 : actually *good* in the common cases where hash keys are consecutive. In an
183 : example that's really too small to make this entirely clear, for a table of
184 : size 2**3 the order of indices is:
185 :
186 : 0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating]
187 :
188 : If two things come in at index 5, the first place we look after is index 2,
189 : not 6, so if another comes in at index 6 the collision at 5 didn't hurt it.
190 : Linear probing is deadly in this case because there the fixed probe order
191 : is the *same* as the order consecutive keys are likely to arrive. But it's
192 : extremely unlikely hash codes will follow a 5*j+1 recurrence by accident,
193 : and certain that consecutive hash codes do not.
194 :
195 : The other half of the strategy is to get the other bits of the hash code
196 : into play. This is done by initializing a (unsigned) vrbl "perturb" to the
197 : full hash code, and changing the recurrence to:
198 :
199 : perturb >>= PERTURB_SHIFT;
200 : j = (5*j) + 1 + perturb;
201 : use j % 2**i as the next table index;
202 :
203 : Now the probe sequence depends (eventually) on every bit in the hash code,
204 : and the pseudo-scrambling property of recurring on 5*j+1 is more valuable,
205 : because it quickly magnifies small differences in the bits that didn't affect
206 : the initial index. Note that because perturb is unsigned, if the recurrence
207 : is executed often enough perturb eventually becomes and remains 0. At that
208 : point (very rarely reached) the recurrence is on (just) 5*j+1 again, and
209 : that's certain to find an empty slot eventually (since it generates every int
210 : in range(2**i), and we make sure there's always at least one empty slot).
211 :
212 : Selecting a good value for PERTURB_SHIFT is a balancing act. You want it
213 : small so that the high bits of the hash code continue to affect the probe
214 : sequence across iterations; but you want it large so that in really bad cases
215 : the high-order hash bits have an effect on early iterations. 5 was "the
216 : best" in minimizing total collisions across experiments Tim Peters ran (on
217 : both normal and pathological cases), but 4 and 6 weren't significantly worse.
218 :
219 : Historical: Reimer Behrends contributed the idea of using a polynomial-based
220 : approach, using repeated multiplication by x in GF(2**n) where an irreducible
221 : polynomial for each table size was chosen such that x was a primitive root.
222 : Christian Tismer later extended that to use division by x instead, as an
223 : efficient way to get the high bits of the hash code into play. This scheme
224 : also gave excellent collision statistics, but was more expensive: two
225 : if-tests were required inside the loop; computing "the next" index took about
226 : the same number of operations but without as much potential parallelism
227 : (e.g., computing 5*j can go on at the same time as computing 1+perturb in the
228 : above, and then shifting perturb can be done while the table index is being
229 : masked); and the PyDictObject struct required a member to hold the table's
230 : polynomial. In Tim's experiments the current scheme ran faster, produced
231 : equally good collision statistics, needed less code & used less memory.
232 :
233 : */
234 :
235 : static int dictresize(PyDictObject *mp, uint8_t log_newsize, int unicode);
236 :
237 : static PyObject* dict_iter(PyDictObject *dict);
238 :
239 : /*Global counter used to set ma_version_tag field of dictionary.
240 : * It is incremented each time that a dictionary is created and each
241 : * time that a dictionary is modified. */
242 : uint64_t _pydict_global_version = 0;
243 :
244 : #include "clinic/dictobject.c.h"
245 :
246 :
247 : #if PyDict_MAXFREELIST > 0
248 : static struct _Py_dict_state *
249 159510000 : get_dict_state(void)
250 : {
251 159510000 : PyInterpreterState *interp = _PyInterpreterState_GET();
252 159510000 : return &interp->dict_state;
253 : }
254 : #endif
255 :
256 :
257 : void
258 30840 : _PyDict_ClearFreeList(PyInterpreterState *interp)
259 : {
260 : #if PyDict_MAXFREELIST > 0
261 30840 : struct _Py_dict_state *state = &interp->dict_state;
262 1083500 : while (state->numfree) {
263 1052660 : PyDictObject *op = state->free_list[--state->numfree];
264 1052660 : assert(PyDict_CheckExact(op));
265 1052660 : PyObject_GC_Del(op);
266 : }
267 958320 : while (state->keys_numfree) {
268 927480 : PyObject_Free(state->keys_free_list[--state->keys_numfree]);
269 : }
270 : #endif
271 30840 : }
272 :
273 :
274 : void
275 3120 : _PyDict_Fini(PyInterpreterState *interp)
276 : {
277 3120 : _PyDict_ClearFreeList(interp);
278 : #if defined(Py_DEBUG) && PyDict_MAXFREELIST > 0
279 3120 : struct _Py_dict_state *state = &interp->dict_state;
280 3120 : state->numfree = -1;
281 3120 : state->keys_numfree = -1;
282 : #endif
283 3120 : }
284 :
285 : static inline Py_hash_t
286 2498040000 : unicode_get_hash(PyObject *o)
287 : {
288 2498040000 : assert(PyUnicode_CheckExact(o));
289 2498040000 : return _PyASCIIObject_CAST(o)->hash;
290 : }
291 :
292 : /* Print summary info about the state of the optimized allocator */
293 : void
294 1 : _PyDict_DebugMallocStats(FILE *out)
295 : {
296 : #if PyDict_MAXFREELIST > 0
297 1 : struct _Py_dict_state *state = get_dict_state();
298 1 : _PyDebugAllocatorStats(out, "free PyDictObject",
299 : state->numfree, sizeof(PyDictObject));
300 : #endif
301 1 : }
302 :
303 : #define DK_MASK(dk) (DK_SIZE(dk)-1)
304 :
305 : static void free_keys_object(PyDictKeysObject *keys);
306 :
307 : static inline void
308 46190500 : dictkeys_incref(PyDictKeysObject *dk)
309 : {
310 : #ifdef Py_REF_DEBUG
311 46190500 : _Py_RefTotal++;
312 : #endif
313 46190500 : dk->dk_refcnt++;
314 46190500 : }
315 :
316 : static inline void
317 69946400 : dictkeys_decref(PyDictKeysObject *dk)
318 : {
319 69946400 : assert(dk->dk_refcnt > 0);
320 : #ifdef Py_REF_DEBUG
321 69946400 : _Py_RefTotal--;
322 : #endif
323 69946400 : if (--dk->dk_refcnt == 0) {
324 23822900 : free_keys_object(dk);
325 : }
326 69946400 : }
327 :
328 : /* lookup indices. returns DKIX_EMPTY, DKIX_DUMMY, or ix >=0 */
329 : static inline Py_ssize_t
330 3268330000 : dictkeys_get_index(const PyDictKeysObject *keys, Py_ssize_t i)
331 : {
332 3268330000 : int log2size = DK_LOG_SIZE(keys);
333 : Py_ssize_t ix;
334 :
335 3268330000 : if (log2size < 8) {
336 2459020000 : const int8_t *indices = (const int8_t*)(keys->dk_indices);
337 2459020000 : ix = indices[i];
338 : }
339 809313000 : else if (log2size < 16) {
340 783542000 : const int16_t *indices = (const int16_t*)(keys->dk_indices);
341 783542000 : ix = indices[i];
342 : }
343 : #if SIZEOF_VOID_P > 4
344 25771500 : else if (log2size >= 32) {
345 0 : const int64_t *indices = (const int64_t*)(keys->dk_indices);
346 0 : ix = indices[i];
347 : }
348 : #endif
349 : else {
350 25771500 : const int32_t *indices = (const int32_t*)(keys->dk_indices);
351 25771500 : ix = indices[i];
352 : }
353 3268330000 : assert(ix >= DKIX_DUMMY);
354 3268330000 : return ix;
355 : }
356 :
357 : /* write to indices. */
358 : static inline void
359 320232000 : dictkeys_set_index(PyDictKeysObject *keys, Py_ssize_t i, Py_ssize_t ix)
360 : {
361 320232000 : int log2size = DK_LOG_SIZE(keys);
362 :
363 320232000 : assert(ix >= DKIX_DUMMY);
364 320232000 : assert(keys->dk_version == 0);
365 :
366 320232000 : if (log2size < 8) {
367 194945000 : int8_t *indices = (int8_t*)(keys->dk_indices);
368 194945000 : assert(ix <= 0x7f);
369 194945000 : indices[i] = (char)ix;
370 : }
371 125287000 : else if (log2size < 16) {
372 121721000 : int16_t *indices = (int16_t*)(keys->dk_indices);
373 121721000 : assert(ix <= 0x7fff);
374 121721000 : indices[i] = (int16_t)ix;
375 : }
376 : #if SIZEOF_VOID_P > 4
377 3566260 : else if (log2size >= 32) {
378 0 : int64_t *indices = (int64_t*)(keys->dk_indices);
379 0 : indices[i] = ix;
380 : }
381 : #endif
382 : else {
383 3566260 : int32_t *indices = (int32_t*)(keys->dk_indices);
384 3566260 : assert(ix <= 0x7fffffff);
385 3566260 : indices[i] = (int32_t)ix;
386 : }
387 320232000 : }
388 :
389 :
390 : /* USABLE_FRACTION is the maximum dictionary load.
391 : * Increasing this ratio makes dictionaries more dense resulting in more
392 : * collisions. Decreasing it improves sparseness at the expense of spreading
393 : * indices over more cache lines and at the cost of total memory consumed.
394 : *
395 : * USABLE_FRACTION must obey the following:
396 : * (0 < USABLE_FRACTION(n) < n) for all n >= 2
397 : *
398 : * USABLE_FRACTION should be quick to calculate.
399 : * Fractions around 1/2 to 2/3 seem to work well in practice.
400 : */
401 : #define USABLE_FRACTION(n) (((n) << 1)/3)
402 :
403 : /* Find the smallest dk_size >= minsize. */
404 : static inline uint8_t
405 10745300 : calculate_log2_keysize(Py_ssize_t minsize)
406 : {
407 : #if SIZEOF_LONG == SIZEOF_SIZE_T
408 10745300 : minsize = (minsize | PyDict_MINSIZE) - 1;
409 10745300 : return _Py_bit_length(minsize | (PyDict_MINSIZE-1));
410 : #elif defined(_MSC_VER)
411 : // On 64bit Windows, sizeof(long) == 4.
412 : minsize = (minsize | PyDict_MINSIZE) - 1;
413 : unsigned long msb;
414 : _BitScanReverse64(&msb, (uint64_t)minsize);
415 : return (uint8_t)(msb + 1);
416 : #else
417 : uint8_t log2_size;
418 : for (log2_size = PyDict_LOG_MINSIZE;
419 : (((Py_ssize_t)1) << log2_size) < minsize;
420 : log2_size++)
421 : ;
422 : return log2_size;
423 : #endif
424 : }
425 :
426 : /* estimate_keysize is reverse function of USABLE_FRACTION.
427 : *
428 : * This can be used to reserve enough size to insert n entries without
429 : * resizing.
430 : */
431 : static inline uint8_t
432 241825 : estimate_log2_keysize(Py_ssize_t n)
433 : {
434 241825 : return calculate_log2_keysize((n*3 + 1) / 2);
435 : }
436 :
437 :
438 : /* GROWTH_RATE. Growth rate upon hitting maximum load.
439 : * Currently set to used*3.
440 : * This means that dicts double in size when growing without deletions,
441 : * but have more head room when the number of deletions is on a par with the
442 : * number of insertions. See also bpo-17563 and bpo-33205.
443 : *
444 : * GROWTH_RATE was set to used*4 up to version 3.2.
445 : * GROWTH_RATE was set to used*2 in version 3.3.0
446 : * GROWTH_RATE was set to used*2 + capacity/2 in 3.4.0-3.6.0.
447 : */
448 : #define GROWTH_RATE(d) ((d)->ma_used*3)
449 :
450 : /* This immutable, empty PyDictKeysObject is used for PyDict_Clear()
451 : * (which cannot fail and thus can do no allocation).
452 : */
453 : static PyDictKeysObject empty_keys_struct = {
454 : 1, /* dk_refcnt */
455 : 0, /* dk_log2_size */
456 : 0, /* dk_log2_index_bytes */
457 : DICT_KEYS_UNICODE, /* dk_kind */
458 : 1, /* dk_version */
459 : 0, /* dk_usable (immutable) */
460 : 0, /* dk_nentries */
461 : {DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY,
462 : DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY}, /* dk_indices */
463 : };
464 :
465 : #define Py_EMPTY_KEYS &empty_keys_struct
466 :
467 : /* Uncomment to check the dict content in _PyDict_CheckConsistency() */
468 : // #define DEBUG_PYDICT
469 :
470 : #ifdef DEBUG_PYDICT
471 : # define ASSERT_CONSISTENT(op) assert(_PyDict_CheckConsistency((PyObject *)(op), 1))
472 : #else
473 : # define ASSERT_CONSISTENT(op) assert(_PyDict_CheckConsistency((PyObject *)(op), 0))
474 : #endif
475 :
476 : static inline int
477 888681 : get_index_from_order(PyDictObject *mp, Py_ssize_t i)
478 : {
479 888681 : assert(mp->ma_used <= SHARED_KEYS_MAX_SIZE);
480 888681 : assert(i < (((char *)mp->ma_values)[-2]));
481 888681 : return ((char *)mp->ma_values)[-3-i];
482 : }
483 :
484 : #ifdef DEBUG_PYDICT
485 : static void
486 : dump_entries(PyDictKeysObject *dk)
487 : {
488 : for (Py_ssize_t i = 0; i < dk->dk_nentries; i++) {
489 : if (DK_IS_UNICODE(dk)) {
490 : PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(dk)[i];
491 : printf("key=%p value=%p\n", ep->me_key, ep->me_value);
492 : }
493 : else {
494 : PyDictKeyEntry *ep = &DK_ENTRIES(dk)[i];
495 : printf("key=%p hash=%lx value=%p\n", ep->me_key, ep->me_hash, ep->me_value);
496 : }
497 : }
498 : }
499 : #endif
500 :
501 : int
502 401568000 : _PyDict_CheckConsistency(PyObject *op, int check_content)
503 : {
504 : #define CHECK(expr) \
505 : do { if (!(expr)) { _PyObject_ASSERT_FAILED_MSG(op, Py_STRINGIFY(expr)); } } while (0)
506 :
507 401568000 : assert(op != NULL);
508 401568000 : CHECK(PyDict_Check(op));
509 401568000 : PyDictObject *mp = (PyDictObject *)op;
510 :
511 401568000 : PyDictKeysObject *keys = mp->ma_keys;
512 401568000 : int splitted = _PyDict_HasSplitTable(mp);
513 401568000 : Py_ssize_t usable = USABLE_FRACTION(DK_SIZE(keys));
514 :
515 401568000 : CHECK(0 <= mp->ma_used && mp->ma_used <= usable);
516 401568000 : CHECK(0 <= keys->dk_usable && keys->dk_usable <= usable);
517 401568000 : CHECK(0 <= keys->dk_nentries && keys->dk_nentries <= usable);
518 401568000 : CHECK(keys->dk_usable + keys->dk_nentries <= usable);
519 :
520 401568000 : if (!splitted) {
521 : /* combined table */
522 386571000 : CHECK(keys->dk_kind != DICT_KEYS_SPLIT);
523 386571000 : CHECK(keys->dk_refcnt == 1 || keys == Py_EMPTY_KEYS);
524 : }
525 : else {
526 14996700 : CHECK(keys->dk_kind == DICT_KEYS_SPLIT);
527 14996700 : CHECK(mp->ma_used <= SHARED_KEYS_MAX_SIZE);
528 : }
529 :
530 401568000 : if (check_content) {
531 0 : for (Py_ssize_t i=0; i < DK_SIZE(keys); i++) {
532 0 : Py_ssize_t ix = dictkeys_get_index(keys, i);
533 0 : CHECK(DKIX_DUMMY <= ix && ix <= usable);
534 : }
535 :
536 0 : if (keys->dk_kind == DICT_KEYS_GENERAL) {
537 0 : PyDictKeyEntry *entries = DK_ENTRIES(keys);
538 0 : for (Py_ssize_t i=0; i < usable; i++) {
539 0 : PyDictKeyEntry *entry = &entries[i];
540 0 : PyObject *key = entry->me_key;
541 :
542 0 : if (key != NULL) {
543 : /* test_dict fails if PyObject_Hash() is called again */
544 0 : CHECK(entry->me_hash != -1);
545 0 : CHECK(entry->me_value != NULL);
546 :
547 0 : if (PyUnicode_CheckExact(key)) {
548 0 : Py_hash_t hash = unicode_get_hash(key);
549 0 : CHECK(entry->me_hash == hash);
550 : }
551 : }
552 : }
553 : }
554 : else {
555 0 : PyDictUnicodeEntry *entries = DK_UNICODE_ENTRIES(keys);
556 0 : for (Py_ssize_t i=0; i < usable; i++) {
557 0 : PyDictUnicodeEntry *entry = &entries[i];
558 0 : PyObject *key = entry->me_key;
559 :
560 0 : if (key != NULL) {
561 0 : CHECK(PyUnicode_CheckExact(key));
562 0 : Py_hash_t hash = unicode_get_hash(key);
563 0 : CHECK(hash != -1);
564 0 : if (!splitted) {
565 0 : CHECK(entry->me_value != NULL);
566 : }
567 : }
568 :
569 0 : if (splitted) {
570 0 : CHECK(entry->me_value == NULL);
571 : }
572 : }
573 : }
574 :
575 0 : if (splitted) {
576 0 : CHECK(mp->ma_used <= SHARED_KEYS_MAX_SIZE);
577 : /* splitted table */
578 0 : int duplicate_check = 0;
579 0 : for (Py_ssize_t i=0; i < mp->ma_used; i++) {
580 0 : int index = get_index_from_order(mp, i);
581 0 : CHECK((duplicate_check & (1<<index)) == 0);
582 0 : duplicate_check |= (1<<index);
583 0 : CHECK(mp->ma_values->values[index] != NULL);
584 : }
585 : }
586 : }
587 401568000 : return 1;
588 :
589 : #undef CHECK
590 : }
591 :
592 :
593 : static PyDictKeysObject*
594 31095800 : new_keys_object(uint8_t log2_size, bool unicode)
595 : {
596 : PyDictKeysObject *dk;
597 : Py_ssize_t usable;
598 : int log2_bytes;
599 31095800 : size_t entry_size = unicode ? sizeof(PyDictUnicodeEntry) : sizeof(PyDictKeyEntry);
600 :
601 31095800 : assert(log2_size >= PyDict_LOG_MINSIZE);
602 :
603 31095800 : usable = USABLE_FRACTION(1<<log2_size);
604 31095800 : if (log2_size < 8) {
605 30922800 : log2_bytes = log2_size;
606 : }
607 172932 : else if (log2_size < 16) {
608 172872 : log2_bytes = log2_size + 1;
609 : }
610 : #if SIZEOF_VOID_P > 4
611 60 : else if (log2_size >= 32) {
612 0 : log2_bytes = log2_size + 3;
613 : }
614 : #endif
615 : else {
616 60 : log2_bytes = log2_size + 2;
617 : }
618 :
619 : #if PyDict_MAXFREELIST > 0
620 31095800 : struct _Py_dict_state *state = get_dict_state();
621 : #ifdef Py_DEBUG
622 : // new_keys_object() must not be called after _PyDict_Fini()
623 31095800 : assert(state->keys_numfree != -1);
624 : #endif
625 31095800 : if (log2_size == PyDict_LOG_MINSIZE && unicode && state->keys_numfree > 0) {
626 15776600 : dk = state->keys_free_list[--state->keys_numfree];
627 15776600 : OBJECT_STAT_INC(from_freelist);
628 : }
629 : else
630 : #endif
631 : {
632 15319200 : dk = PyObject_Malloc(sizeof(PyDictKeysObject)
633 15319200 : + ((size_t)1 << log2_bytes)
634 15319200 : + entry_size * usable);
635 15319200 : if (dk == NULL) {
636 0 : PyErr_NoMemory();
637 0 : return NULL;
638 : }
639 : }
640 : #ifdef Py_REF_DEBUG
641 31095800 : _Py_RefTotal++;
642 : #endif
643 31095800 : dk->dk_refcnt = 1;
644 31095800 : dk->dk_log2_size = log2_size;
645 31095800 : dk->dk_log2_index_bytes = log2_bytes;
646 31095800 : dk->dk_kind = unicode ? DICT_KEYS_UNICODE : DICT_KEYS_GENERAL;
647 31095800 : dk->dk_nentries = 0;
648 31095800 : dk->dk_usable = usable;
649 31095800 : dk->dk_version = 0;
650 31095800 : memset(&dk->dk_indices[0], 0xff, ((size_t)1 << log2_bytes));
651 31095800 : memset(&dk->dk_indices[(size_t)1 << log2_bytes], 0, entry_size * usable);
652 31095800 : return dk;
653 : }
654 :
655 : static void
656 23822900 : free_keys_object(PyDictKeysObject *keys)
657 : {
658 23822900 : assert(keys != Py_EMPTY_KEYS);
659 23822900 : if (DK_IS_UNICODE(keys)) {
660 21528600 : PyDictUnicodeEntry *entries = DK_UNICODE_ENTRIES(keys);
661 : Py_ssize_t i, n;
662 183597000 : for (i = 0, n = keys->dk_nentries; i < n; i++) {
663 162069000 : Py_XDECREF(entries[i].me_key);
664 162069000 : Py_XDECREF(entries[i].me_value);
665 : }
666 : }
667 : else {
668 2294310 : PyDictKeyEntry *entries = DK_ENTRIES(keys);
669 : Py_ssize_t i, n;
670 20866400 : for (i = 0, n = keys->dk_nentries; i < n; i++) {
671 18572100 : Py_XDECREF(entries[i].me_key);
672 18572100 : Py_XDECREF(entries[i].me_value);
673 : }
674 : }
675 : #if PyDict_MAXFREELIST > 0
676 23822900 : struct _Py_dict_state *state = get_dict_state();
677 : #ifdef Py_DEBUG
678 : // free_keys_object() must not be called after _PyDict_Fini()
679 23822900 : assert(state->keys_numfree != -1);
680 : #endif
681 23822900 : if (DK_LOG_SIZE(keys) == PyDict_LOG_MINSIZE
682 13905000 : && state->keys_numfree < PyDict_MAXFREELIST
683 10912300 : && DK_IS_UNICODE(keys)) {
684 9654400 : state->keys_free_list[state->keys_numfree++] = keys;
685 : OBJECT_STAT_INC(to_freelist);
686 9654400 : return;
687 : }
688 : #endif
689 14168500 : PyObject_Free(keys);
690 : }
691 :
692 : static inline PyDictValues*
693 13062000 : new_values(Py_ssize_t size)
694 : {
695 13062000 : assert(size > 0);
696 13062000 : size_t prefix_size = _Py_SIZE_ROUND_UP(size+2, sizeof(PyObject *));
697 13062000 : assert(prefix_size < 256);
698 13062000 : size_t n = prefix_size + size * sizeof(PyObject *);
699 13062000 : uint8_t *mem = PyMem_Malloc(n);
700 13062000 : if (mem == NULL) {
701 0 : return NULL;
702 : }
703 13062000 : assert(prefix_size % sizeof(PyObject *) == 0);
704 13062000 : mem[prefix_size-1] = (uint8_t)prefix_size;
705 13062000 : return (PyDictValues*)(mem + prefix_size);
706 : }
707 :
708 : static inline void
709 13056100 : free_values(PyDictValues *values)
710 : {
711 13056100 : int prefix_size = ((uint8_t *)values)[-1];
712 13056100 : PyMem_Free(((char *)values)-prefix_size);
713 13056100 : }
714 :
715 : /* Consumes a reference to the keys object */
716 : static PyObject *
717 46984600 : new_dict(PyDictKeysObject *keys, PyDictValues *values, Py_ssize_t used, int free_values_on_failure)
718 : {
719 : PyDictObject *mp;
720 46984600 : assert(keys != NULL);
721 : #if PyDict_MAXFREELIST > 0
722 46984600 : struct _Py_dict_state *state = get_dict_state();
723 : #ifdef Py_DEBUG
724 : // new_dict() must not be called after _PyDict_Fini()
725 46984600 : assert(state->numfree != -1);
726 : #endif
727 46984600 : if (state->numfree) {
728 32260600 : mp = state->free_list[--state->numfree];
729 32260600 : assert (mp != NULL);
730 32260600 : assert (Py_IS_TYPE(mp, &PyDict_Type));
731 : OBJECT_STAT_INC(from_freelist);
732 32260600 : _Py_NewReference((PyObject *)mp);
733 : }
734 : else
735 : #endif
736 : {
737 14724000 : mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
738 14724000 : if (mp == NULL) {
739 0 : dictkeys_decref(keys);
740 0 : if (free_values_on_failure) {
741 0 : free_values(values);
742 : }
743 0 : return NULL;
744 : }
745 : }
746 46984600 : mp->ma_keys = keys;
747 46984600 : mp->ma_values = values;
748 46984600 : mp->ma_used = used;
749 46984600 : mp->ma_version_tag = DICT_NEXT_VERSION();
750 46984600 : ASSERT_CONSISTENT(mp);
751 46984600 : return (PyObject *)mp;
752 : }
753 :
754 : static inline Py_ssize_t
755 15100800 : shared_keys_usable_size(PyDictKeysObject *keys)
756 : {
757 15100800 : return keys->dk_nentries + keys->dk_usable;
758 : }
759 :
760 : /* Consumes a reference to the keys object */
761 : static PyObject *
762 4338660 : new_dict_with_shared_keys(PyDictKeysObject *keys)
763 : {
764 : PyDictValues *values;
765 : Py_ssize_t i, size;
766 :
767 4338660 : size = shared_keys_usable_size(keys);
768 4338660 : values = new_values(size);
769 4338660 : if (values == NULL) {
770 0 : dictkeys_decref(keys);
771 0 : return PyErr_NoMemory();
772 : }
773 4338660 : ((char *)values)[-2] = 0;
774 134498000 : for (i = 0; i < size; i++) {
775 130160000 : values->values[i] = NULL;
776 : }
777 4338660 : return new_dict(keys, values, 0, 1);
778 : }
779 :
780 :
781 : static PyDictKeysObject *
782 3327170 : clone_combined_dict_keys(PyDictObject *orig)
783 : {
784 3327170 : assert(PyDict_Check(orig));
785 3327170 : assert(Py_TYPE(orig)->tp_iter == (getiterfunc)dict_iter);
786 3327170 : assert(orig->ma_values == NULL);
787 3327170 : assert(orig->ma_keys->dk_refcnt == 1);
788 :
789 3327170 : Py_ssize_t keys_size = _PyDict_KeysSize(orig->ma_keys);
790 3327170 : PyDictKeysObject *keys = PyObject_Malloc(keys_size);
791 3327170 : if (keys == NULL) {
792 4 : PyErr_NoMemory();
793 4 : return NULL;
794 : }
795 :
796 3327170 : memcpy(keys, orig->ma_keys, keys_size);
797 :
798 : /* After copying key/value pairs, we need to incref all
799 : keys and values and they are about to be co-owned by a
800 : new dict object. */
801 : PyObject **pkey, **pvalue;
802 : size_t offs;
803 3327170 : if (DK_IS_UNICODE(orig->ma_keys)) {
804 3285660 : PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(keys);
805 3285660 : pkey = &ep0->me_key;
806 3285660 : pvalue = &ep0->me_value;
807 3285660 : offs = sizeof(PyDictUnicodeEntry) / sizeof(PyObject*);
808 : }
809 : else {
810 41507 : PyDictKeyEntry *ep0 = DK_ENTRIES(keys);
811 41507 : pkey = &ep0->me_key;
812 41507 : pvalue = &ep0->me_value;
813 41507 : offs = sizeof(PyDictKeyEntry) / sizeof(PyObject*);
814 : }
815 :
816 3327170 : Py_ssize_t n = keys->dk_nentries;
817 35393800 : for (Py_ssize_t i = 0; i < n; i++) {
818 32066600 : PyObject *value = *pvalue;
819 32066600 : if (value != NULL) {
820 31173300 : Py_INCREF(value);
821 31173300 : Py_INCREF(*pkey);
822 : }
823 32066600 : pvalue += offs;
824 32066600 : pkey += offs;
825 : }
826 :
827 : /* Since we copied the keys table we now have an extra reference
828 : in the system. Manually call increment _Py_RefTotal to signal that
829 : we have it now; calling dictkeys_incref would be an error as
830 : keys->dk_refcnt is already set to 1 (after memcpy). */
831 : #ifdef Py_REF_DEBUG
832 3327170 : _Py_RefTotal++;
833 : #endif
834 3327170 : return keys;
835 : }
836 :
837 : PyObject *
838 39665500 : PyDict_New(void)
839 : {
840 39665500 : dictkeys_incref(Py_EMPTY_KEYS);
841 39665500 : return new_dict(Py_EMPTY_KEYS, NULL, 0, 0);
842 : }
843 :
844 : /* Search index of hash table from offset of entry table */
845 : static Py_ssize_t
846 26415500 : lookdict_index(PyDictKeysObject *k, Py_hash_t hash, Py_ssize_t index)
847 : {
848 26415500 : size_t mask = DK_MASK(k);
849 26415500 : size_t perturb = (size_t)hash;
850 26415500 : size_t i = (size_t)hash & mask;
851 :
852 11873400 : for (;;) {
853 38288900 : Py_ssize_t ix = dictkeys_get_index(k, i);
854 38288900 : if (ix == index) {
855 26415500 : return i;
856 : }
857 11873400 : if (ix == DKIX_EMPTY) {
858 0 : return DKIX_EMPTY;
859 : }
860 11873400 : perturb >>= PERTURB_SHIFT;
861 11873400 : i = mask & (i*5 + perturb + 1);
862 : }
863 : Py_UNREACHABLE();
864 : }
865 :
866 : // Search non-Unicode key from Unicode table
867 : static Py_ssize_t
868 1365160 : unicodekeys_lookup_generic(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
869 : {
870 1365160 : PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(dk);
871 1365160 : size_t mask = DK_MASK(dk);
872 1365160 : size_t perturb = hash;
873 1365160 : size_t i = (size_t)hash & mask;
874 : Py_ssize_t ix;
875 : for (;;) {
876 1408200 : ix = dictkeys_get_index(dk, i);
877 1408200 : if (ix >= 0) {
878 43021 : PyDictUnicodeEntry *ep = &ep0[ix];
879 43021 : assert(ep->me_key != NULL);
880 43021 : assert(PyUnicode_CheckExact(ep->me_key));
881 43021 : if (ep->me_key == key) {
882 0 : return ix;
883 : }
884 43021 : if (unicode_get_hash(ep->me_key) == hash) {
885 341 : PyObject *startkey = ep->me_key;
886 341 : Py_INCREF(startkey);
887 341 : int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
888 341 : Py_DECREF(startkey);
889 341 : if (cmp < 0) {
890 0 : return DKIX_ERROR;
891 : }
892 341 : if (dk == mp->ma_keys && ep->me_key == startkey) {
893 341 : if (cmp > 0) {
894 13 : return ix;
895 : }
896 : }
897 : else {
898 : /* The dict was mutated, restart */
899 0 : return DKIX_KEY_CHANGED;
900 : }
901 : }
902 : }
903 1365180 : else if (ix == DKIX_EMPTY) {
904 1365150 : return DKIX_EMPTY;
905 : }
906 43040 : perturb >>= PERTURB_SHIFT;
907 43040 : i = mask & (i*5 + perturb + 1);
908 : }
909 : Py_UNREACHABLE();
910 : }
911 :
912 : // Search Unicode key from Unicode table.
913 : static Py_ssize_t _Py_HOT_FUNCTION
914 1663050000 : unicodekeys_lookup_unicode(PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
915 : {
916 1663050000 : PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(dk);
917 1663050000 : size_t mask = DK_MASK(dk);
918 1663050000 : size_t perturb = hash;
919 1663050000 : size_t i = (size_t)hash & mask;
920 : Py_ssize_t ix;
921 : for (;;) {
922 1995460000 : ix = dictkeys_get_index(dk, i);
923 1995460000 : if (ix >= 0) {
924 1111850000 : PyDictUnicodeEntry *ep = &ep0[ix];
925 1111850000 : assert(ep->me_key != NULL);
926 1111850000 : assert(PyUnicode_CheckExact(ep->me_key));
927 1913000000 : if (ep->me_key == key ||
928 893655000 : (unicode_get_hash(ep->me_key) == hash && unicode_eq(ep->me_key, key))) {
929 403205000 : return ix;
930 : }
931 : }
932 883613000 : else if (ix == DKIX_EMPTY) {
933 865470000 : return DKIX_EMPTY;
934 : }
935 726790000 : perturb >>= PERTURB_SHIFT;
936 726790000 : i = mask & (i*5 + perturb + 1);
937 726790000 : ix = dictkeys_get_index(dk, i);
938 726790000 : if (ix >= 0) {
939 375793000 : PyDictUnicodeEntry *ep = &ep0[ix];
940 375793000 : assert(ep->me_key != NULL);
941 375793000 : assert(PyUnicode_CheckExact(ep->me_key));
942 711854000 : if (ep->me_key == key ||
943 348148000 : (unicode_get_hash(ep->me_key) == hash && unicode_eq(ep->me_key, key))) {
944 51820100 : return ix;
945 : }
946 : }
947 350996000 : else if (ix == DKIX_EMPTY) {
948 342559000 : return DKIX_EMPTY;
949 : }
950 332411000 : perturb >>= PERTURB_SHIFT;
951 332411000 : i = mask & (i*5 + perturb + 1);
952 : }
953 : Py_UNREACHABLE();
954 : }
955 :
956 : // Search key from Generic table.
957 : static Py_ssize_t
958 58973800 : dictkeys_generic_lookup(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
959 : {
960 58973800 : PyDictKeyEntry *ep0 = DK_ENTRIES(dk);
961 58973800 : size_t mask = DK_MASK(dk);
962 58973800 : size_t perturb = hash;
963 58973800 : size_t i = (size_t)hash & mask;
964 : Py_ssize_t ix;
965 : for (;;) {
966 102418000 : ix = dictkeys_get_index(dk, i);
967 102418000 : if (ix >= 0) {
968 70640000 : PyDictKeyEntry *ep = &ep0[ix];
969 70640000 : assert(ep->me_key != NULL);
970 70640000 : if (ep->me_key == key) {
971 19200200 : return ix;
972 : }
973 51439800 : if (ep->me_hash == hash) {
974 10326500 : PyObject *startkey = ep->me_key;
975 10326500 : Py_INCREF(startkey);
976 10326500 : int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
977 10326500 : Py_DECREF(startkey);
978 10326500 : if (cmp < 0) {
979 14 : return DKIX_ERROR;
980 : }
981 10326500 : if (dk == mp->ma_keys && ep->me_key == startkey) {
982 10326500 : if (cmp > 0) {
983 9881820 : return ix;
984 : }
985 : }
986 : else {
987 : /* The dict was mutated, restart */
988 42 : return DKIX_KEY_CHANGED;
989 : }
990 : }
991 : }
992 31778300 : else if (ix == DKIX_EMPTY) {
993 29891800 : return DKIX_EMPTY;
994 : }
995 43444500 : perturb >>= PERTURB_SHIFT;
996 43444500 : i = mask & (i*5 + perturb + 1);
997 : }
998 : Py_UNREACHABLE();
999 : }
1000 :
1001 : /* Lookup a string in a (all unicode) dict keys.
1002 : * Returns DKIX_ERROR if key is not a string,
1003 : * or if the dict keys is not all strings.
1004 : * If the keys is present then return the index of key.
1005 : * If the key is not present then return DKIX_EMPTY.
1006 : */
1007 : Py_ssize_t
1008 66782900 : _PyDictKeys_StringLookup(PyDictKeysObject* dk, PyObject *key)
1009 : {
1010 66782900 : DictKeysKind kind = dk->dk_kind;
1011 66782900 : if (!PyUnicode_CheckExact(key) || kind == DICT_KEYS_GENERAL) {
1012 0 : return DKIX_ERROR;
1013 : }
1014 66782900 : Py_hash_t hash = unicode_get_hash(key);
1015 66782900 : if (hash == -1) {
1016 0 : hash = PyUnicode_Type.tp_hash(key);
1017 0 : if (hash == -1) {
1018 0 : PyErr_Clear();
1019 0 : return DKIX_ERROR;
1020 : }
1021 : }
1022 66782900 : return unicodekeys_lookup_unicode(dk, key, hash);
1023 : }
1024 :
1025 : /*
1026 : The basic lookup function used by all operations.
1027 : This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
1028 : Open addressing is preferred over chaining since the link overhead for
1029 : chaining would be substantial (100% with typical malloc overhead).
1030 :
1031 : The initial probe index is computed as hash mod the table size. Subsequent
1032 : probe indices are computed as explained earlier.
1033 :
1034 : All arithmetic on hash should ignore overflow.
1035 :
1036 : _Py_dict_lookup() is general-purpose, and may return DKIX_ERROR if (and only if) a
1037 : comparison raises an exception.
1038 : When the key isn't found a DKIX_EMPTY is returned.
1039 : */
1040 : Py_ssize_t
1041 1648910000 : _Py_dict_lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr)
1042 : {
1043 : PyDictKeysObject *dk;
1044 : DictKeysKind kind;
1045 : Py_ssize_t ix;
1046 :
1047 1648910000 : start:
1048 1648910000 : dk = mp->ma_keys;
1049 1648910000 : kind = dk->dk_kind;
1050 :
1051 1648910000 : if (kind != DICT_KEYS_GENERAL) {
1052 1589940000 : if (PyUnicode_CheckExact(key)) {
1053 1588570000 : ix = unicodekeys_lookup_unicode(dk, key, hash);
1054 : }
1055 : else {
1056 1365160 : ix = unicodekeys_lookup_generic(mp, dk, key, hash);
1057 1365160 : if (ix == DKIX_KEY_CHANGED) {
1058 0 : goto start;
1059 : }
1060 : }
1061 :
1062 1589940000 : if (ix >= 0) {
1063 423541000 : if (kind == DICT_KEYS_SPLIT) {
1064 12511400 : *value_addr = mp->ma_values->values[ix];
1065 : }
1066 : else {
1067 411030000 : *value_addr = DK_UNICODE_ENTRIES(dk)[ix].me_value;
1068 : }
1069 : }
1070 : else {
1071 1166390000 : *value_addr = NULL;
1072 : }
1073 : }
1074 : else {
1075 58973800 : ix = dictkeys_generic_lookup(mp, dk, key, hash);
1076 58973800 : if (ix == DKIX_KEY_CHANGED) {
1077 42 : goto start;
1078 : }
1079 58973800 : if (ix >= 0) {
1080 29082000 : *value_addr = DK_ENTRIES(dk)[ix].me_value;
1081 : }
1082 : else {
1083 29891800 : *value_addr = NULL;
1084 : }
1085 : }
1086 :
1087 1648910000 : return ix;
1088 : }
1089 :
1090 : int
1091 13577 : _PyDict_HasOnlyStringKeys(PyObject *dict)
1092 : {
1093 13577 : Py_ssize_t pos = 0;
1094 : PyObject *key, *value;
1095 13577 : assert(PyDict_Check(dict));
1096 : /* Shortcut */
1097 13577 : if (((PyDictObject *)dict)->ma_keys->dk_kind != DICT_KEYS_GENERAL)
1098 13574 : return 1;
1099 3 : while (PyDict_Next(dict, &pos, &key, &value))
1100 3 : if (!PyUnicode_Check(key))
1101 3 : return 0;
1102 0 : return 1;
1103 : }
1104 :
1105 : #define MAINTAIN_TRACKING(mp, key, value) \
1106 : do { \
1107 : if (!_PyObject_GC_IS_TRACKED(mp)) { \
1108 : if (_PyObject_GC_MAY_BE_TRACKED(key) || \
1109 : _PyObject_GC_MAY_BE_TRACKED(value)) { \
1110 : _PyObject_GC_TRACK(mp); \
1111 : } \
1112 : } \
1113 : } while(0)
1114 :
1115 : void
1116 38168200 : _PyDict_MaybeUntrack(PyObject *op)
1117 : {
1118 : PyDictObject *mp;
1119 : PyObject *value;
1120 : Py_ssize_t i, numentries;
1121 :
1122 38168200 : if (!PyDict_CheckExact(op) || !_PyObject_GC_IS_TRACKED(op))
1123 0 : return;
1124 :
1125 38168200 : mp = (PyDictObject *) op;
1126 38168200 : numentries = mp->ma_keys->dk_nentries;
1127 38168200 : if (_PyDict_HasSplitTable(mp)) {
1128 934820 : for (i = 0; i < numentries; i++) {
1129 933670 : if ((value = mp->ma_values->values[i]) == NULL)
1130 648 : continue;
1131 933022 : if (_PyObject_GC_MAY_BE_TRACKED(value)) {
1132 302449 : return;
1133 : }
1134 : }
1135 : }
1136 : else {
1137 37864600 : if (DK_IS_UNICODE(mp->ma_keys)) {
1138 32496900 : PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(mp->ma_keys);
1139 93911300 : for (i = 0; i < numentries; i++) {
1140 93763700 : if ((value = ep0[i].me_value) == NULL)
1141 7135160 : continue;
1142 86628500 : if (_PyObject_GC_MAY_BE_TRACKED(value))
1143 32349200 : return;
1144 : }
1145 : }
1146 : else {
1147 5367740 : PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
1148 6494660 : for (i = 0; i < numentries; i++) {
1149 6481220 : if ((value = ep0[i].me_value) == NULL)
1150 236436 : continue;
1151 7295560 : if (_PyObject_GC_MAY_BE_TRACKED(value) ||
1152 1050780 : _PyObject_GC_MAY_BE_TRACKED(ep0[i].me_key))
1153 5354300 : return;
1154 : }
1155 : }
1156 : }
1157 162255 : _PyObject_GC_UNTRACK(op);
1158 : }
1159 :
1160 : /* Internal function to find slot for an item from its hash
1161 : when it is known that the key is not present in the dict.
1162 :
1163 : The dict must be combined. */
1164 : static Py_ssize_t
1165 134416000 : find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash)
1166 : {
1167 134416000 : assert(keys != NULL);
1168 :
1169 134416000 : const size_t mask = DK_MASK(keys);
1170 134416000 : size_t i = hash & mask;
1171 134416000 : Py_ssize_t ix = dictkeys_get_index(keys, i);
1172 233790000 : for (size_t perturb = hash; ix >= 0;) {
1173 99373600 : perturb >>= PERTURB_SHIFT;
1174 99373600 : i = (i*5 + perturb + 1) & mask;
1175 99373600 : ix = dictkeys_get_index(keys, i);
1176 : }
1177 134416000 : return i;
1178 : }
1179 :
1180 : static int
1181 10503400 : insertion_resize(PyDictObject *mp, int unicode)
1182 : {
1183 10503400 : return dictresize(mp, calculate_log2_keysize(GROWTH_RATE(mp)), unicode);
1184 : }
1185 :
1186 : static Py_ssize_t
1187 7700960 : insert_into_dictkeys(PyDictKeysObject *keys, PyObject *name)
1188 : {
1189 7700960 : assert(PyUnicode_CheckExact(name));
1190 7700960 : Py_hash_t hash = unicode_get_hash(name);
1191 7700960 : if (hash == -1) {
1192 0 : hash = PyUnicode_Type.tp_hash(name);
1193 0 : if (hash == -1) {
1194 0 : PyErr_Clear();
1195 0 : return DKIX_EMPTY;
1196 : }
1197 : }
1198 7700960 : Py_ssize_t ix = unicodekeys_lookup_unicode(keys, name, hash);
1199 7700960 : if (ix == DKIX_EMPTY) {
1200 722919 : if (keys->dk_usable <= 0) {
1201 111104 : return DKIX_EMPTY;
1202 : }
1203 611815 : Py_INCREF(name);
1204 : /* Insert into new slot. */
1205 611815 : keys->dk_version = 0;
1206 611815 : Py_ssize_t hashpos = find_empty_slot(keys, hash);
1207 611815 : ix = keys->dk_nentries;
1208 611815 : PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(keys)[ix];
1209 611815 : dictkeys_set_index(keys, hashpos, ix);
1210 611815 : assert(ep->me_key == NULL);
1211 611815 : ep->me_key = name;
1212 611815 : keys->dk_usable--;
1213 611815 : keys->dk_nentries++;
1214 : }
1215 7589860 : assert (ix < SHARED_KEYS_MAX_SIZE);
1216 7589860 : return ix;
1217 : }
1218 :
1219 : /*
1220 : Internal routine to insert a new item into the table.
1221 : Used both by the internal resize routine and by the public insert routine.
1222 : Returns -1 if an error occurred, or 0 on success.
1223 : Consumes key and value references.
1224 : */
1225 : static int
1226 141099000 : insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
1227 : {
1228 : PyObject *old_value;
1229 :
1230 141099000 : if (DK_IS_UNICODE(mp->ma_keys) && !PyUnicode_CheckExact(key)) {
1231 105208 : if (insertion_resize(mp, 0) < 0)
1232 0 : goto Fail;
1233 105208 : assert(mp->ma_keys->dk_kind == DICT_KEYS_GENERAL);
1234 : }
1235 :
1236 141099000 : Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &old_value);
1237 141099000 : if (ix == DKIX_ERROR)
1238 3 : goto Fail;
1239 :
1240 141099000 : MAINTAIN_TRACKING(mp, key, value);
1241 :
1242 141099000 : if (ix == DKIX_EMPTY) {
1243 : /* Insert into new slot. */
1244 99409600 : mp->ma_keys->dk_version = 0;
1245 99409600 : assert(old_value == NULL);
1246 99409600 : if (mp->ma_keys->dk_usable <= 0) {
1247 : /* Need to resize. */
1248 9516690 : if (insertion_resize(mp, 1) < 0)
1249 0 : goto Fail;
1250 : }
1251 :
1252 99409600 : Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
1253 99409600 : dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
1254 :
1255 99409600 : if (DK_IS_UNICODE(mp->ma_keys)) {
1256 : PyDictUnicodeEntry *ep;
1257 86579000 : ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
1258 86579000 : ep->me_key = key;
1259 86579000 : if (mp->ma_values) {
1260 305380 : Py_ssize_t index = mp->ma_keys->dk_nentries;
1261 305380 : _PyDictValues_AddToInsertionOrder(mp->ma_values, index);
1262 305380 : assert (mp->ma_values->values[index] == NULL);
1263 305380 : mp->ma_values->values[index] = value;
1264 : }
1265 : else {
1266 86273700 : ep->me_value = value;
1267 : }
1268 : }
1269 : else {
1270 : PyDictKeyEntry *ep;
1271 12830500 : ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
1272 12830500 : ep->me_key = key;
1273 12830500 : ep->me_hash = hash;
1274 12830500 : ep->me_value = value;
1275 : }
1276 99409600 : mp->ma_used++;
1277 99409600 : mp->ma_version_tag = DICT_NEXT_VERSION();
1278 99409600 : mp->ma_keys->dk_usable--;
1279 99409600 : mp->ma_keys->dk_nentries++;
1280 99409600 : assert(mp->ma_keys->dk_usable >= 0);
1281 99409600 : ASSERT_CONSISTENT(mp);
1282 99409600 : return 0;
1283 : }
1284 :
1285 41689400 : if (old_value != value) {
1286 36568500 : if (_PyDict_HasSplitTable(mp)) {
1287 4978980 : mp->ma_values->values[ix] = value;
1288 4978980 : if (old_value == NULL) {
1289 4710100 : _PyDictValues_AddToInsertionOrder(mp->ma_values, ix);
1290 4710100 : mp->ma_used++;
1291 : }
1292 : }
1293 : else {
1294 31589500 : assert(old_value != NULL);
1295 31589500 : if (DK_IS_UNICODE(mp->ma_keys)) {
1296 30040800 : DK_UNICODE_ENTRIES(mp->ma_keys)[ix].me_value = value;
1297 : }
1298 : else {
1299 1548710 : DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
1300 : }
1301 : }
1302 36568500 : mp->ma_version_tag = DICT_NEXT_VERSION();
1303 : }
1304 41689400 : Py_XDECREF(old_value); /* which **CAN** re-enter (see issue #22653) */
1305 41689400 : ASSERT_CONSISTENT(mp);
1306 41689400 : Py_DECREF(key);
1307 41689400 : return 0;
1308 :
1309 3 : Fail:
1310 3 : Py_DECREF(value);
1311 3 : Py_DECREF(key);
1312 3 : return -1;
1313 : }
1314 :
1315 : // Same to insertdict but specialized for ma_keys = Py_EMPTY_KEYS.
1316 : // Consumes key and value references.
1317 : static int
1318 19668900 : insert_to_emptydict(PyDictObject *mp, PyObject *key, Py_hash_t hash,
1319 : PyObject *value)
1320 : {
1321 19668900 : assert(mp->ma_keys == Py_EMPTY_KEYS);
1322 :
1323 19668900 : int unicode = PyUnicode_CheckExact(key);
1324 19668900 : PyDictKeysObject *newkeys = new_keys_object(PyDict_LOG_MINSIZE, unicode);
1325 19668900 : if (newkeys == NULL) {
1326 0 : Py_DECREF(key);
1327 0 : Py_DECREF(value);
1328 0 : return -1;
1329 : }
1330 19668900 : dictkeys_decref(Py_EMPTY_KEYS);
1331 19668900 : mp->ma_keys = newkeys;
1332 19668900 : mp->ma_values = NULL;
1333 :
1334 19668900 : MAINTAIN_TRACKING(mp, key, value);
1335 :
1336 19668900 : size_t hashpos = (size_t)hash & (PyDict_MINSIZE-1);
1337 19668900 : dictkeys_set_index(mp->ma_keys, hashpos, 0);
1338 19668900 : if (unicode) {
1339 17569700 : PyDictUnicodeEntry *ep = DK_UNICODE_ENTRIES(mp->ma_keys);
1340 17569700 : ep->me_key = key;
1341 17569700 : ep->me_value = value;
1342 : }
1343 : else {
1344 2099180 : PyDictKeyEntry *ep = DK_ENTRIES(mp->ma_keys);
1345 2099180 : ep->me_key = key;
1346 2099180 : ep->me_hash = hash;
1347 2099180 : ep->me_value = value;
1348 : }
1349 19668900 : mp->ma_used++;
1350 19668900 : mp->ma_version_tag = DICT_NEXT_VERSION();
1351 19668900 : mp->ma_keys->dk_usable--;
1352 19668900 : mp->ma_keys->dk_nentries++;
1353 19668900 : return 0;
1354 : }
1355 :
1356 : /*
1357 : Internal routine used by dictresize() to build a hashtable of entries.
1358 : */
1359 : static void
1360 1208630 : build_indices_generic(PyDictKeysObject *keys, PyDictKeyEntry *ep, Py_ssize_t n)
1361 : {
1362 1208630 : size_t mask = DK_MASK(keys);
1363 19886000 : for (Py_ssize_t ix = 0; ix != n; ix++, ep++) {
1364 18677400 : Py_hash_t hash = ep->me_hash;
1365 18677400 : size_t i = hash & mask;
1366 25468600 : for (size_t perturb = hash; dictkeys_get_index(keys, i) != DKIX_EMPTY;) {
1367 6791150 : perturb >>= PERTURB_SHIFT;
1368 6791150 : i = mask & (i*5 + perturb + 1);
1369 : }
1370 18677400 : dictkeys_set_index(keys, i, ix);
1371 : }
1372 1208630 : }
1373 :
1374 : static void
1375 9388740 : build_indices_unicode(PyDictKeysObject *keys, PyDictUnicodeEntry *ep, Py_ssize_t n)
1376 : {
1377 9388740 : size_t mask = DK_MASK(keys);
1378 130624000 : for (Py_ssize_t ix = 0; ix != n; ix++, ep++) {
1379 121235000 : Py_hash_t hash = unicode_get_hash(ep->me_key);
1380 121235000 : assert(hash != -1);
1381 121235000 : size_t i = hash & mask;
1382 144687000 : for (size_t perturb = hash; dictkeys_get_index(keys, i) != DKIX_EMPTY;) {
1383 23452000 : perturb >>= PERTURB_SHIFT;
1384 23452000 : i = mask & (i*5 + perturb + 1);
1385 : }
1386 121235000 : dictkeys_set_index(keys, i, ix);
1387 : }
1388 9388740 : }
1389 :
1390 : /*
1391 : Restructure the table by allocating a new table and reinserting all
1392 : items again. When entries have been deleted, the new table may
1393 : actually be smaller than the old one.
1394 : If a table is split (its keys and hashes are shared, its values are not),
1395 : then the values are temporarily copied into the table, it is resized as
1396 : a combined table, then the me_value slots in the old table are NULLed out.
1397 : After resizing a table is always combined.
1398 :
1399 : This function supports:
1400 : - Unicode split -> Unicode combined or Generic
1401 : - Unicode combined -> Unicode combined or Generic
1402 : - Generic -> Generic
1403 : */
1404 : static int
1405 10597400 : dictresize(PyDictObject *mp, uint8_t log2_newsize, int unicode)
1406 : {
1407 : PyDictKeysObject *oldkeys;
1408 : PyDictValues *oldvalues;
1409 :
1410 10597400 : if (log2_newsize >= SIZEOF_SIZE_T*8) {
1411 0 : PyErr_NoMemory();
1412 0 : return -1;
1413 : }
1414 10597400 : assert(log2_newsize >= PyDict_LOG_MINSIZE);
1415 :
1416 10597400 : oldkeys = mp->ma_keys;
1417 10597400 : oldvalues = mp->ma_values;
1418 :
1419 10597400 : if (!DK_IS_UNICODE(oldkeys)) {
1420 1048780 : unicode = 0;
1421 : }
1422 :
1423 : /* NOTE: Current odict checks mp->ma_keys to detect resize happen.
1424 : * So we can't reuse oldkeys even if oldkeys->dk_size == newsize.
1425 : * TODO: Try reusing oldkeys when reimplement odict.
1426 : */
1427 :
1428 : /* Allocate a new table. */
1429 10597400 : mp->ma_keys = new_keys_object(log2_newsize, unicode);
1430 10597400 : if (mp->ma_keys == NULL) {
1431 0 : mp->ma_keys = oldkeys;
1432 0 : return -1;
1433 : }
1434 : // New table must be large enough.
1435 10597400 : assert(mp->ma_keys->dk_usable >= mp->ma_used);
1436 :
1437 10597400 : Py_ssize_t numentries = mp->ma_used;
1438 :
1439 10597400 : if (oldvalues != NULL) {
1440 115971 : PyDictUnicodeEntry *oldentries = DK_UNICODE_ENTRIES(oldkeys);
1441 : /* Convert split table into new combined table.
1442 : * We must incref keys; we can transfer values.
1443 : */
1444 115971 : if (mp->ma_keys->dk_kind == DICT_KEYS_GENERAL) {
1445 : // split -> generic
1446 3 : PyDictKeyEntry *newentries = DK_ENTRIES(mp->ma_keys);
1447 :
1448 3 : for (Py_ssize_t i = 0; i < numentries; i++) {
1449 0 : int index = get_index_from_order(mp, i);
1450 0 : PyDictUnicodeEntry *ep = &oldentries[index];
1451 0 : assert(oldvalues->values[index] != NULL);
1452 0 : Py_INCREF(ep->me_key);
1453 0 : newentries[i].me_key = ep->me_key;
1454 0 : newentries[i].me_hash = unicode_get_hash(ep->me_key);
1455 0 : newentries[i].me_value = oldvalues->values[index];
1456 : }
1457 3 : build_indices_generic(mp->ma_keys, newentries, numentries);
1458 : }
1459 : else { // split -> combined unicode
1460 115968 : PyDictUnicodeEntry *newentries = DK_UNICODE_ENTRIES(mp->ma_keys);
1461 :
1462 730865 : for (Py_ssize_t i = 0; i < numentries; i++) {
1463 614897 : int index = get_index_from_order(mp, i);
1464 614897 : PyDictUnicodeEntry *ep = &oldentries[index];
1465 614897 : assert(oldvalues->values[index] != NULL);
1466 614897 : Py_INCREF(ep->me_key);
1467 614897 : newentries[i].me_key = ep->me_key;
1468 614897 : newentries[i].me_value = oldvalues->values[index];
1469 : }
1470 115968 : build_indices_unicode(mp->ma_keys, newentries, numentries);
1471 : }
1472 115971 : dictkeys_decref(oldkeys);
1473 115971 : mp->ma_values = NULL;
1474 115971 : free_values(oldvalues);
1475 : }
1476 : else { // oldkeys is combined.
1477 10481400 : if (oldkeys->dk_kind == DICT_KEYS_GENERAL) {
1478 : // generic -> generic
1479 1048780 : assert(mp->ma_keys->dk_kind == DICT_KEYS_GENERAL);
1480 1048780 : PyDictKeyEntry *oldentries = DK_ENTRIES(oldkeys);
1481 1048780 : PyDictKeyEntry *newentries = DK_ENTRIES(mp->ma_keys);
1482 1048780 : if (oldkeys->dk_nentries == numentries) {
1483 921251 : memcpy(newentries, oldentries, numentries * sizeof(PyDictKeyEntry));
1484 : }
1485 : else {
1486 127530 : PyDictKeyEntry *ep = oldentries;
1487 897193 : for (Py_ssize_t i = 0; i < numentries; i++) {
1488 1049140 : while (ep->me_value == NULL)
1489 279477 : ep++;
1490 769663 : newentries[i] = *ep++;
1491 : }
1492 : }
1493 1048780 : build_indices_generic(mp->ma_keys, newentries, numentries);
1494 : }
1495 : else { // oldkeys is combined unicode
1496 9432620 : PyDictUnicodeEntry *oldentries = DK_UNICODE_ENTRIES(oldkeys);
1497 9432620 : if (unicode) { // combined unicode -> combined unicode
1498 9272770 : PyDictUnicodeEntry *newentries = DK_UNICODE_ENTRIES(mp->ma_keys);
1499 9272770 : if (oldkeys->dk_nentries == numentries && mp->ma_keys->dk_kind == DICT_KEYS_UNICODE) {
1500 8851020 : memcpy(newentries, oldentries, numentries * sizeof(PyDictUnicodeEntry));
1501 : }
1502 : else {
1503 421753 : PyDictUnicodeEntry *ep = oldentries;
1504 34060300 : for (Py_ssize_t i = 0; i < numentries; i++) {
1505 35160700 : while (ep->me_value == NULL)
1506 1522150 : ep++;
1507 33638600 : newentries[i] = *ep++;
1508 : }
1509 : }
1510 9272770 : build_indices_unicode(mp->ma_keys, newentries, numentries);
1511 : }
1512 : else { // combined unicode -> generic
1513 159850 : PyDictKeyEntry *newentries = DK_ENTRIES(mp->ma_keys);
1514 159850 : PyDictUnicodeEntry *ep = oldentries;
1515 572409 : for (Py_ssize_t i = 0; i < numentries; i++) {
1516 412559 : while (ep->me_value == NULL)
1517 0 : ep++;
1518 412559 : newentries[i].me_key = ep->me_key;
1519 412559 : newentries[i].me_hash = unicode_get_hash(ep->me_key);
1520 412559 : newentries[i].me_value = ep->me_value;
1521 412559 : ep++;
1522 : }
1523 159850 : build_indices_generic(mp->ma_keys, newentries, numentries);
1524 : }
1525 : }
1526 :
1527 : // We can not use free_keys_object here because key's reference
1528 : // are moved already.
1529 : #ifdef Py_REF_DEBUG
1530 10481400 : _Py_RefTotal--;
1531 : #endif
1532 10481400 : if (oldkeys == Py_EMPTY_KEYS) {
1533 58723 : oldkeys->dk_refcnt--;
1534 58723 : assert(oldkeys->dk_refcnt > 0);
1535 : }
1536 : else {
1537 10422700 : assert(oldkeys->dk_kind != DICT_KEYS_SPLIT);
1538 10422700 : assert(oldkeys->dk_refcnt == 1);
1539 : #if PyDict_MAXFREELIST > 0
1540 10422700 : struct _Py_dict_state *state = get_dict_state();
1541 : #ifdef Py_DEBUG
1542 : // dictresize() must not be called after _PyDict_Fini()
1543 10422700 : assert(state->keys_numfree != -1);
1544 : #endif
1545 10422700 : if (DK_LOG_SIZE(oldkeys) == PyDict_LOG_MINSIZE &&
1546 7735490 : DK_IS_UNICODE(oldkeys) &&
1547 7078300 : state->keys_numfree < PyDict_MAXFREELIST)
1548 : {
1549 7049850 : state->keys_free_list[state->keys_numfree++] = oldkeys;
1550 7049850 : OBJECT_STAT_INC(to_freelist);
1551 : }
1552 : else
1553 : #endif
1554 : {
1555 3372830 : PyObject_Free(oldkeys);
1556 : }
1557 : }
1558 : }
1559 :
1560 10597400 : mp->ma_keys->dk_usable -= numentries;
1561 10597400 : mp->ma_keys->dk_nentries = numentries;
1562 10597400 : ASSERT_CONSISTENT(mp);
1563 10597400 : return 0;
1564 : }
1565 :
1566 : static PyObject *
1567 21274500 : dict_new_presized(Py_ssize_t minused, bool unicode)
1568 : {
1569 21274500 : const uint8_t log2_max_presize = 17;
1570 21274500 : const Py_ssize_t max_presize = ((Py_ssize_t)1) << log2_max_presize;
1571 : uint8_t log2_newsize;
1572 : PyDictKeysObject *new_keys;
1573 :
1574 21274500 : if (minused <= USABLE_FRACTION(PyDict_MINSIZE)) {
1575 21126600 : return PyDict_New();
1576 : }
1577 : /* There are no strict guarantee that returned dict can contain minused
1578 : * items without resize. So we create medium size dict instead of very
1579 : * large dict or MemoryError.
1580 : */
1581 147902 : if (minused > USABLE_FRACTION(max_presize)) {
1582 0 : log2_newsize = log2_max_presize;
1583 : }
1584 : else {
1585 147902 : log2_newsize = estimate_log2_keysize(minused);
1586 : }
1587 :
1588 147902 : new_keys = new_keys_object(log2_newsize, unicode);
1589 147902 : if (new_keys == NULL)
1590 0 : return NULL;
1591 147902 : return new_dict(new_keys, NULL, 0, 0);
1592 : }
1593 :
1594 : PyObject *
1595 0 : _PyDict_NewPresized(Py_ssize_t minused)
1596 : {
1597 0 : return dict_new_presized(minused, false);
1598 : }
1599 :
1600 : PyObject *
1601 21274500 : _PyDict_FromItems(PyObject *const *keys, Py_ssize_t keys_offset,
1602 : PyObject *const *values, Py_ssize_t values_offset,
1603 : Py_ssize_t length)
1604 : {
1605 21274500 : bool unicode = true;
1606 21274500 : PyObject *const *ks = keys;
1607 :
1608 29439400 : for (Py_ssize_t i = 0; i < length; i++) {
1609 8215680 : if (!PyUnicode_CheckExact(*ks)) {
1610 50786 : unicode = false;
1611 50786 : break;
1612 : }
1613 8164890 : ks += keys_offset;
1614 : }
1615 :
1616 21274500 : PyObject *dict = dict_new_presized(length, unicode);
1617 21274500 : if (dict == NULL) {
1618 0 : return NULL;
1619 : }
1620 :
1621 21274500 : ks = keys;
1622 21274500 : PyObject *const *vs = values;
1623 :
1624 29636000 : for (Py_ssize_t i = 0; i < length; i++) {
1625 8361430 : PyObject *key = *ks;
1626 8361430 : PyObject *value = *vs;
1627 8361430 : if (PyDict_SetItem(dict, key, value) < 0) {
1628 1 : Py_DECREF(dict);
1629 1 : return NULL;
1630 : }
1631 8361430 : ks += keys_offset;
1632 8361430 : vs += values_offset;
1633 : }
1634 :
1635 21274500 : return dict;
1636 : }
1637 :
1638 : /* Note that, for historical reasons, PyDict_GetItem() suppresses all errors
1639 : * that may occur (originally dicts supported only string keys, and exceptions
1640 : * weren't possible). So, while the original intent was that a NULL return
1641 : * meant the key wasn't present, in reality it can mean that, or that an error
1642 : * (suppressed) occurred while computing the key's hash, or that some error
1643 : * (suppressed) occurred when comparing keys in the dict's internal probe
1644 : * sequence. A nasty example of the latter is when a Python-coded comparison
1645 : * function hits a stack-depth error, which can cause this to return NULL
1646 : * even if the key is present.
1647 : */
1648 : PyObject *
1649 1298190 : PyDict_GetItem(PyObject *op, PyObject *key)
1650 : {
1651 1298190 : if (!PyDict_Check(op)) {
1652 0 : return NULL;
1653 : }
1654 1298190 : PyDictObject *mp = (PyDictObject *)op;
1655 :
1656 : Py_hash_t hash;
1657 1298190 : if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
1658 235 : hash = PyObject_Hash(key);
1659 235 : if (hash == -1) {
1660 0 : PyErr_Clear();
1661 0 : return NULL;
1662 : }
1663 : }
1664 :
1665 1298190 : PyThreadState *tstate = _PyThreadState_GET();
1666 : #ifdef Py_DEBUG
1667 : // bpo-40839: Before Python 3.10, it was possible to call PyDict_GetItem()
1668 : // with the GIL released.
1669 1298190 : _Py_EnsureTstateNotNULL(tstate);
1670 : #endif
1671 :
1672 : /* Preserve the existing exception */
1673 : PyObject *exc_type, *exc_value, *exc_tb;
1674 : PyObject *value;
1675 : Py_ssize_t ix; (void)ix;
1676 :
1677 1298190 : _PyErr_Fetch(tstate, &exc_type, &exc_value, &exc_tb);
1678 1298190 : ix = _Py_dict_lookup(mp, key, hash, &value);
1679 :
1680 : /* Ignore any exception raised by the lookup */
1681 1298190 : _PyErr_Restore(tstate, exc_type, exc_value, exc_tb);
1682 :
1683 :
1684 1298190 : assert(ix >= 0 || value == NULL);
1685 1298190 : return value;
1686 : }
1687 :
1688 : Py_ssize_t
1689 907564 : _PyDict_GetItemHint(PyDictObject *mp, PyObject *key,
1690 : Py_ssize_t hint, PyObject **value)
1691 : {
1692 907564 : assert(*value == NULL);
1693 907564 : assert(PyDict_CheckExact((PyObject*)mp));
1694 907564 : assert(PyUnicode_CheckExact(key));
1695 :
1696 907564 : if (hint >= 0 && hint < mp->ma_keys->dk_nentries) {
1697 0 : PyObject *res = NULL;
1698 :
1699 0 : if (DK_IS_UNICODE(mp->ma_keys)) {
1700 0 : PyDictUnicodeEntry *ep = DK_UNICODE_ENTRIES(mp->ma_keys) + (size_t)hint;
1701 0 : if (ep->me_key == key) {
1702 0 : if (mp->ma_keys->dk_kind == DICT_KEYS_SPLIT) {
1703 0 : assert(mp->ma_values != NULL);
1704 0 : res = mp->ma_values->values[(size_t)hint];
1705 : }
1706 : else {
1707 0 : res = ep->me_value;
1708 : }
1709 0 : if (res != NULL) {
1710 0 : *value = res;
1711 0 : return hint;
1712 : }
1713 : }
1714 : }
1715 : else {
1716 0 : PyDictKeyEntry *ep = DK_ENTRIES(mp->ma_keys) + (size_t)hint;
1717 0 : if (ep->me_key == key) {
1718 0 : if (mp->ma_keys->dk_kind == DICT_KEYS_SPLIT) {
1719 0 : assert(mp->ma_values != NULL);
1720 0 : res = mp->ma_values->values[(size_t)hint];
1721 : }
1722 : else {
1723 0 : res = ep->me_value;
1724 : }
1725 0 : if (res != NULL) {
1726 0 : *value = res;
1727 0 : return hint;
1728 : }
1729 : }
1730 : }
1731 : }
1732 :
1733 907564 : Py_hash_t hash = unicode_get_hash(key);
1734 907564 : if (hash == -1) {
1735 0 : hash = PyObject_Hash(key);
1736 0 : if (hash == -1) {
1737 0 : return -1;
1738 : }
1739 : }
1740 :
1741 907564 : return _Py_dict_lookup(mp, key, hash, value);
1742 : }
1743 :
1744 : /* Same as PyDict_GetItemWithError() but with hash supplied by caller.
1745 : This returns NULL *with* an exception set if an exception occurred.
1746 : It returns NULL *without* an exception set if the key wasn't present.
1747 : */
1748 : PyObject *
1749 485606000 : _PyDict_GetItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
1750 : {
1751 : Py_ssize_t ix; (void)ix;
1752 485606000 : PyDictObject *mp = (PyDictObject *)op;
1753 : PyObject *value;
1754 :
1755 485606000 : if (!PyDict_Check(op)) {
1756 1 : PyErr_BadInternalCall();
1757 1 : return NULL;
1758 : }
1759 :
1760 485606000 : ix = _Py_dict_lookup(mp, key, hash, &value);
1761 485606000 : assert(ix >= 0 || value == NULL);
1762 485606000 : return value;
1763 : }
1764 :
1765 : /* Variant of PyDict_GetItem() that doesn't suppress exceptions.
1766 : This returns NULL *with* an exception set if an exception occurred.
1767 : It returns NULL *without* an exception set if the key wasn't present.
1768 : */
1769 : PyObject *
1770 243735000 : PyDict_GetItemWithError(PyObject *op, PyObject *key)
1771 : {
1772 : Py_ssize_t ix; (void)ix;
1773 : Py_hash_t hash;
1774 243735000 : PyDictObject*mp = (PyDictObject *)op;
1775 : PyObject *value;
1776 :
1777 243735000 : if (!PyDict_Check(op)) {
1778 0 : PyErr_BadInternalCall();
1779 0 : return NULL;
1780 : }
1781 243735000 : if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1)
1782 : {
1783 19484700 : hash = PyObject_Hash(key);
1784 19484700 : if (hash == -1) {
1785 11 : return NULL;
1786 : }
1787 : }
1788 :
1789 243735000 : ix = _Py_dict_lookup(mp, key, hash, &value);
1790 243735000 : assert(ix >= 0 || value == NULL);
1791 243735000 : return value;
1792 : }
1793 :
1794 : PyObject *
1795 2557170 : _PyDict_GetItemWithError(PyObject *dp, PyObject *kv)
1796 : {
1797 2557170 : assert(PyUnicode_CheckExact(kv));
1798 2557170 : Py_hash_t hash = kv->ob_type->tp_hash(kv);
1799 2557170 : if (hash == -1) {
1800 0 : return NULL;
1801 : }
1802 2557170 : return _PyDict_GetItem_KnownHash(dp, kv, hash);
1803 : }
1804 :
1805 : PyObject *
1806 8292 : _PyDict_GetItemIdWithError(PyObject *dp, _Py_Identifier *key)
1807 : {
1808 : PyObject *kv;
1809 8292 : kv = _PyUnicode_FromId(key); /* borrowed */
1810 8292 : if (kv == NULL)
1811 0 : return NULL;
1812 8292 : Py_hash_t hash = unicode_get_hash(kv);
1813 8292 : assert (hash != -1); /* interned strings have their hash value initialised */
1814 8292 : return _PyDict_GetItem_KnownHash(dp, kv, hash);
1815 : }
1816 :
1817 : PyObject *
1818 3624860 : _PyDict_GetItemStringWithError(PyObject *v, const char *key)
1819 : {
1820 : PyObject *kv, *rv;
1821 3624860 : kv = PyUnicode_FromString(key);
1822 3624860 : if (kv == NULL) {
1823 6 : return NULL;
1824 : }
1825 3624860 : rv = PyDict_GetItemWithError(v, kv);
1826 3624860 : Py_DECREF(kv);
1827 3624860 : return rv;
1828 : }
1829 :
1830 : /* Fast version of global value lookup (LOAD_GLOBAL).
1831 : * Lookup in globals, then builtins.
1832 : *
1833 : *
1834 : *
1835 : *
1836 : * Raise an exception and return NULL if an error occurred (ex: computing the
1837 : * key hash failed, key comparison failed, ...). Return NULL if the key doesn't
1838 : * exist. Return the value if the key exists.
1839 : */
1840 : PyObject *
1841 34888900 : _PyDict_LoadGlobal(PyDictObject *globals, PyDictObject *builtins, PyObject *key)
1842 : {
1843 : Py_ssize_t ix;
1844 : Py_hash_t hash;
1845 : PyObject *value;
1846 :
1847 34888900 : if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
1848 0 : hash = PyObject_Hash(key);
1849 0 : if (hash == -1)
1850 0 : return NULL;
1851 : }
1852 :
1853 : /* namespace 1: globals */
1854 34888900 : ix = _Py_dict_lookup(globals, key, hash, &value);
1855 34888900 : if (ix == DKIX_ERROR)
1856 0 : return NULL;
1857 34888900 : if (ix != DKIX_EMPTY && value != NULL)
1858 17430000 : return value;
1859 :
1860 : /* namespace 2: builtins */
1861 17458900 : ix = _Py_dict_lookup(builtins, key, hash, &value);
1862 17458900 : assert(ix >= 0 || value == NULL);
1863 17458900 : return value;
1864 : }
1865 :
1866 : /* Consumes references to key and value */
1867 : int
1868 154400000 : _PyDict_SetItem_Take2(PyDictObject *mp, PyObject *key, PyObject *value)
1869 : {
1870 154400000 : assert(key);
1871 154400000 : assert(value);
1872 154400000 : assert(PyDict_Check(mp));
1873 : Py_hash_t hash;
1874 154400000 : if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
1875 17838600 : hash = PyObject_Hash(key);
1876 17838600 : if (hash == -1) {
1877 5 : Py_DECREF(key);
1878 5 : Py_DECREF(value);
1879 5 : return -1;
1880 : }
1881 : }
1882 154400000 : if (mp->ma_keys == Py_EMPTY_KEYS) {
1883 19456000 : return insert_to_emptydict(mp, key, hash, value);
1884 : }
1885 : /* insertdict() handles any resizing that might be necessary */
1886 134944000 : return insertdict(mp, key, hash, value);
1887 : }
1888 :
1889 : /* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
1890 : * dictionary if it's merely replacing the value for an existing key.
1891 : * This means that it's safe to loop over a dictionary with PyDict_Next()
1892 : * and occasionally replace a value -- but you can't insert new keys or
1893 : * remove them.
1894 : */
1895 : int
1896 138051000 : PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
1897 : {
1898 138051000 : if (!PyDict_Check(op)) {
1899 0 : PyErr_BadInternalCall();
1900 0 : return -1;
1901 : }
1902 138051000 : assert(key);
1903 138051000 : assert(value);
1904 138051000 : Py_INCREF(key);
1905 138051000 : Py_INCREF(value);
1906 138051000 : return _PyDict_SetItem_Take2((PyDictObject *)op, key, value);
1907 : }
1908 :
1909 : int
1910 117935 : _PyDict_SetItem_KnownHash(PyObject *op, PyObject *key, PyObject *value,
1911 : Py_hash_t hash)
1912 : {
1913 : PyDictObject *mp;
1914 :
1915 117935 : if (!PyDict_Check(op)) {
1916 0 : PyErr_BadInternalCall();
1917 0 : return -1;
1918 : }
1919 117935 : assert(key);
1920 117935 : assert(value);
1921 117935 : assert(hash != -1);
1922 117935 : mp = (PyDictObject *)op;
1923 :
1924 117935 : Py_INCREF(key);
1925 117935 : Py_INCREF(value);
1926 117935 : if (mp->ma_keys == Py_EMPTY_KEYS) {
1927 22297 : return insert_to_emptydict(mp, key, hash, value);
1928 : }
1929 : /* insertdict() handles any resizing that might be necessary */
1930 95638 : return insertdict(mp, key, hash, value);
1931 : }
1932 :
1933 : static void
1934 3377130 : delete_index_from_values(PyDictValues *values, Py_ssize_t ix)
1935 : {
1936 3377130 : uint8_t *size_ptr = ((uint8_t *)values)-2;
1937 3377130 : int size = *size_ptr;
1938 : int i;
1939 9050240 : for (i = 1; size_ptr[-i] != ix; i++) {
1940 5673110 : assert(i <= size);
1941 : }
1942 3377130 : assert(i <= size);
1943 8079890 : for (; i < size; i++) {
1944 4702760 : size_ptr[-i] = size_ptr[-i-1];
1945 : }
1946 3377130 : *size_ptr = size -1;
1947 3377130 : }
1948 :
1949 : static int
1950 26220400 : delitem_common(PyDictObject *mp, Py_hash_t hash, Py_ssize_t ix,
1951 : PyObject *old_value)
1952 : {
1953 : PyObject *old_key;
1954 :
1955 26220400 : Py_ssize_t hashpos = lookdict_index(mp->ma_keys, hash, ix);
1956 26220400 : assert(hashpos >= 0);
1957 :
1958 26220400 : mp->ma_used--;
1959 26220400 : mp->ma_version_tag = DICT_NEXT_VERSION();
1960 26220400 : if (mp->ma_values) {
1961 4145 : assert(old_value == mp->ma_values->values[ix]);
1962 4145 : mp->ma_values->values[ix] = NULL;
1963 4145 : assert(ix < SHARED_KEYS_MAX_SIZE);
1964 : /* Update order */
1965 4145 : delete_index_from_values(mp->ma_values, ix);
1966 4145 : ASSERT_CONSISTENT(mp);
1967 : }
1968 : else {
1969 26216300 : mp->ma_keys->dk_version = 0;
1970 26216300 : dictkeys_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
1971 26216300 : if (DK_IS_UNICODE(mp->ma_keys)) {
1972 22930400 : PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[ix];
1973 22930400 : old_key = ep->me_key;
1974 22930400 : ep->me_key = NULL;
1975 22930400 : ep->me_value = NULL;
1976 : }
1977 : else {
1978 3285850 : PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[ix];
1979 3285850 : old_key = ep->me_key;
1980 3285850 : ep->me_key = NULL;
1981 3285850 : ep->me_value = NULL;
1982 3285850 : ep->me_hash = 0;
1983 : }
1984 26216300 : Py_DECREF(old_key);
1985 : }
1986 26220400 : Py_DECREF(old_value);
1987 :
1988 26220400 : ASSERT_CONSISTENT(mp);
1989 26220400 : return 0;
1990 : }
1991 :
1992 : int
1993 25545700 : PyDict_DelItem(PyObject *op, PyObject *key)
1994 : {
1995 : Py_hash_t hash;
1996 25545700 : assert(key);
1997 25545700 : if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
1998 2971210 : hash = PyObject_Hash(key);
1999 2971210 : if (hash == -1)
2000 0 : return -1;
2001 : }
2002 :
2003 25545700 : return _PyDict_DelItem_KnownHash(op, key, hash);
2004 : }
2005 :
2006 : int
2007 25567800 : _PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
2008 : {
2009 : Py_ssize_t ix;
2010 : PyDictObject *mp;
2011 : PyObject *old_value;
2012 :
2013 25567800 : if (!PyDict_Check(op)) {
2014 0 : PyErr_BadInternalCall();
2015 0 : return -1;
2016 : }
2017 25567800 : assert(key);
2018 25567800 : assert(hash != -1);
2019 25567800 : mp = (PyDictObject *)op;
2020 25567800 : ix = _Py_dict_lookup(mp, key, hash, &old_value);
2021 25567800 : if (ix == DKIX_ERROR)
2022 0 : return -1;
2023 25567800 : if (ix == DKIX_EMPTY || old_value == NULL) {
2024 41139 : _PyErr_SetKeyError(key);
2025 41139 : return -1;
2026 : }
2027 :
2028 25526600 : return delitem_common(mp, hash, ix, old_value);
2029 : }
2030 :
2031 : /* This function promises that the predicate -> deletion sequence is atomic
2032 : * (i.e. protected by the GIL), assuming the predicate itself doesn't
2033 : * release the GIL.
2034 : */
2035 : int
2036 177173 : _PyDict_DelItemIf(PyObject *op, PyObject *key,
2037 : int (*predicate)(PyObject *value))
2038 : {
2039 : Py_ssize_t hashpos, ix;
2040 : PyDictObject *mp;
2041 : Py_hash_t hash;
2042 : PyObject *old_value;
2043 : int res;
2044 :
2045 177173 : if (!PyDict_Check(op)) {
2046 0 : PyErr_BadInternalCall();
2047 0 : return -1;
2048 : }
2049 177173 : assert(key);
2050 177173 : hash = PyObject_Hash(key);
2051 177173 : if (hash == -1)
2052 0 : return -1;
2053 177173 : mp = (PyDictObject *)op;
2054 177173 : ix = _Py_dict_lookup(mp, key, hash, &old_value);
2055 177173 : if (ix == DKIX_ERROR)
2056 0 : return -1;
2057 177173 : if (ix == DKIX_EMPTY || old_value == NULL) {
2058 44 : _PyErr_SetKeyError(key);
2059 44 : return -1;
2060 : }
2061 :
2062 177129 : res = predicate(old_value);
2063 177129 : if (res == -1)
2064 0 : return -1;
2065 :
2066 177129 : hashpos = lookdict_index(mp->ma_keys, hash, ix);
2067 177129 : assert(hashpos >= 0);
2068 :
2069 177129 : if (res > 0)
2070 176359 : return delitem_common(mp, hashpos, ix, old_value);
2071 : else
2072 770 : return 0;
2073 : }
2074 :
2075 :
2076 : void
2077 1898000 : PyDict_Clear(PyObject *op)
2078 : {
2079 : PyDictObject *mp;
2080 : PyDictKeysObject *oldkeys;
2081 : PyDictValues *oldvalues;
2082 : Py_ssize_t i, n;
2083 :
2084 1898000 : if (!PyDict_Check(op))
2085 0 : return;
2086 1898000 : mp = ((PyDictObject *)op);
2087 1898000 : oldkeys = mp->ma_keys;
2088 1898000 : oldvalues = mp->ma_values;
2089 1898000 : if (oldkeys == Py_EMPTY_KEYS) {
2090 326272 : return;
2091 : }
2092 : /* Empty the dict... */
2093 1571720 : dictkeys_incref(Py_EMPTY_KEYS);
2094 1571720 : mp->ma_keys = Py_EMPTY_KEYS;
2095 1571720 : mp->ma_values = NULL;
2096 1571720 : mp->ma_used = 0;
2097 1571720 : mp->ma_version_tag = DICT_NEXT_VERSION();
2098 : /* ...then clear the keys and values */
2099 1571720 : if (oldvalues != NULL) {
2100 60 : n = oldkeys->dk_nentries;
2101 558 : for (i = 0; i < n; i++)
2102 498 : Py_CLEAR(oldvalues->values[i]);
2103 60 : free_values(oldvalues);
2104 60 : dictkeys_decref(oldkeys);
2105 : }
2106 : else {
2107 1571660 : assert(oldkeys->dk_refcnt == 1);
2108 1571660 : dictkeys_decref(oldkeys);
2109 : }
2110 1571720 : ASSERT_CONSISTENT(mp);
2111 : }
2112 :
2113 : /* Internal version of PyDict_Next that returns a hash value in addition
2114 : * to the key and value.
2115 : * Return 1 on success, return 0 when the reached the end of the dictionary
2116 : * (or if op is not a dictionary)
2117 : */
2118 : int
2119 77802600 : _PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey,
2120 : PyObject **pvalue, Py_hash_t *phash)
2121 : {
2122 : Py_ssize_t i;
2123 : PyDictObject *mp;
2124 : PyObject *key, *value;
2125 : Py_hash_t hash;
2126 :
2127 77802600 : if (!PyDict_Check(op))
2128 0 : return 0;
2129 77802600 : mp = (PyDictObject *)op;
2130 77802600 : i = *ppos;
2131 77802600 : if (mp->ma_values) {
2132 220438 : assert(mp->ma_used <= SHARED_KEYS_MAX_SIZE);
2133 220438 : if (i < 0 || i >= mp->ma_used)
2134 13249 : return 0;
2135 207189 : int index = get_index_from_order(mp, i);
2136 207189 : value = mp->ma_values->values[index];
2137 :
2138 207189 : key = DK_UNICODE_ENTRIES(mp->ma_keys)[index].me_key;
2139 207189 : hash = unicode_get_hash(key);
2140 207189 : assert(value != NULL);
2141 : }
2142 : else {
2143 77582200 : Py_ssize_t n = mp->ma_keys->dk_nentries;
2144 77582200 : if (i < 0 || i >= n)
2145 10489600 : return 0;
2146 67092600 : if (DK_IS_UNICODE(mp->ma_keys)) {
2147 63046300 : PyDictUnicodeEntry *entry_ptr = &DK_UNICODE_ENTRIES(mp->ma_keys)[i];
2148 82996800 : while (i < n && entry_ptr->me_value == NULL) {
2149 19950500 : entry_ptr++;
2150 19950500 : i++;
2151 : }
2152 63046300 : if (i >= n)
2153 50955 : return 0;
2154 62995400 : key = entry_ptr->me_key;
2155 62995400 : hash = unicode_get_hash(entry_ptr->me_key);
2156 62995400 : value = entry_ptr->me_value;
2157 : }
2158 : else {
2159 4046330 : PyDictKeyEntry *entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
2160 4116680 : while (i < n && entry_ptr->me_value == NULL) {
2161 70345 : entry_ptr++;
2162 70345 : i++;
2163 : }
2164 4046330 : if (i >= n)
2165 18255 : return 0;
2166 4028080 : key = entry_ptr->me_key;
2167 4028080 : hash = entry_ptr->me_hash;
2168 4028080 : value = entry_ptr->me_value;
2169 : }
2170 : }
2171 67230600 : *ppos = i+1;
2172 67230600 : if (pkey)
2173 66836800 : *pkey = key;
2174 67230600 : if (pvalue)
2175 57338000 : *pvalue = value;
2176 67230600 : if (phash)
2177 6121430 : *phash = hash;
2178 67230600 : return 1;
2179 : }
2180 :
2181 : /*
2182 : * Iterate over a dict. Use like so:
2183 : *
2184 : * Py_ssize_t i;
2185 : * PyObject *key, *value;
2186 : * i = 0; # important! i should not otherwise be changed by you
2187 : * while (PyDict_Next(yourdict, &i, &key, &value)) {
2188 : * Refer to borrowed references in key and value.
2189 : * }
2190 : *
2191 : * Return 1 on success, return 0 when the reached the end of the dictionary
2192 : * (or if op is not a dictionary)
2193 : *
2194 : * CAUTION: In general, it isn't safe to use PyDict_Next in a loop that
2195 : * mutates the dict. One exception: it is safe if the loop merely changes
2196 : * the values associated with the keys (but doesn't insert new keys or
2197 : * delete keys), via PyDict_SetItem().
2198 : */
2199 : int
2200 60364100 : PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue)
2201 : {
2202 60364100 : return _PyDict_Next(op, ppos, pkey, pvalue, NULL);
2203 : }
2204 :
2205 : /* Internal version of dict.pop(). */
2206 : PyObject *
2207 642378 : _PyDict_Pop_KnownHash(PyObject *dict, PyObject *key, Py_hash_t hash, PyObject *deflt)
2208 : {
2209 : Py_ssize_t ix;
2210 : PyObject *old_value;
2211 : PyDictObject *mp;
2212 :
2213 642378 : assert(PyDict_Check(dict));
2214 642378 : mp = (PyDictObject *)dict;
2215 :
2216 642378 : if (mp->ma_used == 0) {
2217 0 : if (deflt) {
2218 0 : Py_INCREF(deflt);
2219 0 : return deflt;
2220 : }
2221 0 : _PyErr_SetKeyError(key);
2222 0 : return NULL;
2223 : }
2224 642378 : ix = _Py_dict_lookup(mp, key, hash, &old_value);
2225 642378 : if (ix == DKIX_ERROR)
2226 1 : return NULL;
2227 642377 : if (ix == DKIX_EMPTY || old_value == NULL) {
2228 124955 : if (deflt) {
2229 85800 : Py_INCREF(deflt);
2230 85800 : return deflt;
2231 : }
2232 39155 : _PyErr_SetKeyError(key);
2233 39155 : return NULL;
2234 : }
2235 517422 : assert(old_value != NULL);
2236 517422 : Py_INCREF(old_value);
2237 517422 : delitem_common(mp, hash, ix, old_value);
2238 :
2239 517422 : ASSERT_CONSISTENT(mp);
2240 517422 : return old_value;
2241 : }
2242 :
2243 : PyObject *
2244 774244 : _PyDict_Pop(PyObject *dict, PyObject *key, PyObject *deflt)
2245 : {
2246 : Py_hash_t hash;
2247 :
2248 774244 : if (((PyDictObject *)dict)->ma_used == 0) {
2249 137995 : if (deflt) {
2250 96825 : Py_INCREF(deflt);
2251 96825 : return deflt;
2252 : }
2253 41170 : _PyErr_SetKeyError(key);
2254 41170 : return NULL;
2255 : }
2256 636249 : if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
2257 132604 : hash = PyObject_Hash(key);
2258 132604 : if (hash == -1)
2259 1 : return NULL;
2260 : }
2261 636248 : return _PyDict_Pop_KnownHash(dict, key, hash, deflt);
2262 : }
2263 :
2264 : /* Internal version of dict.from_keys(). It is subclass-friendly. */
2265 : PyObject *
2266 107871 : _PyDict_FromKeys(PyObject *cls, PyObject *iterable, PyObject *value)
2267 : {
2268 : PyObject *it; /* iter(iterable) */
2269 : PyObject *key;
2270 : PyObject *d;
2271 : int status;
2272 :
2273 107871 : d = _PyObject_CallNoArgs(cls);
2274 107871 : if (d == NULL)
2275 1 : return NULL;
2276 :
2277 107870 : if (PyDict_CheckExact(d) && ((PyDictObject *)d)->ma_used == 0) {
2278 107805 : if (PyDict_CheckExact(iterable)) {
2279 268 : PyDictObject *mp = (PyDictObject *)d;
2280 : PyObject *oldvalue;
2281 268 : Py_ssize_t pos = 0;
2282 : PyObject *key;
2283 : Py_hash_t hash;
2284 :
2285 268 : int unicode = DK_IS_UNICODE(((PyDictObject*)iterable)->ma_keys);
2286 268 : if (dictresize(mp, estimate_log2_keysize(PyDict_GET_SIZE(iterable)), unicode)) {
2287 0 : Py_DECREF(d);
2288 0 : return NULL;
2289 : }
2290 :
2291 845 : while (_PyDict_Next(iterable, &pos, &key, &oldvalue, &hash)) {
2292 577 : Py_INCREF(key);
2293 577 : Py_INCREF(value);
2294 577 : if (insertdict(mp, key, hash, value)) {
2295 0 : Py_DECREF(d);
2296 0 : return NULL;
2297 : }
2298 : }
2299 268 : return d;
2300 : }
2301 107537 : if (PyAnySet_CheckExact(iterable)) {
2302 313 : PyDictObject *mp = (PyDictObject *)d;
2303 313 : Py_ssize_t pos = 0;
2304 : PyObject *key;
2305 : Py_hash_t hash;
2306 :
2307 313 : if (dictresize(mp, estimate_log2_keysize(PySet_GET_SIZE(iterable)), 0)) {
2308 0 : Py_DECREF(d);
2309 0 : return NULL;
2310 : }
2311 :
2312 1154 : while (_PySet_NextEntry(iterable, &pos, &key, &hash)) {
2313 841 : Py_INCREF(key);
2314 841 : Py_INCREF(value);
2315 841 : if (insertdict(mp, key, hash, value)) {
2316 0 : Py_DECREF(d);
2317 0 : return NULL;
2318 : }
2319 : }
2320 313 : return d;
2321 : }
2322 : }
2323 :
2324 107289 : it = PyObject_GetIter(iterable);
2325 107289 : if (it == NULL){
2326 2 : Py_DECREF(d);
2327 2 : return NULL;
2328 : }
2329 :
2330 107287 : if (PyDict_CheckExact(d)) {
2331 799581 : while ((key = PyIter_Next(it)) != NULL) {
2332 692358 : status = PyDict_SetItem(d, key, value);
2333 692358 : Py_DECREF(key);
2334 692358 : if (status < 0)
2335 0 : goto Fail;
2336 : }
2337 : } else {
2338 449 : while ((key = PyIter_Next(it)) != NULL) {
2339 386 : status = PyObject_SetItem(d, key, value);
2340 386 : Py_DECREF(key);
2341 386 : if (status < 0)
2342 1 : goto Fail;
2343 : }
2344 : }
2345 :
2346 107286 : if (PyErr_Occurred())
2347 1 : goto Fail;
2348 107285 : Py_DECREF(it);
2349 107285 : return d;
2350 :
2351 2 : Fail:
2352 2 : Py_DECREF(it);
2353 2 : Py_DECREF(d);
2354 2 : return NULL;
2355 : }
2356 :
2357 : /* Methods */
2358 :
2359 : static void
2360 47273700 : dict_dealloc(PyDictObject *mp)
2361 : {
2362 47273700 : PyDictValues *values = mp->ma_values;
2363 47273700 : PyDictKeysObject *keys = mp->ma_keys;
2364 : Py_ssize_t i, n;
2365 :
2366 : /* bpo-31095: UnTrack is needed before calling any callbacks */
2367 47273700 : PyObject_GC_UnTrack(mp);
2368 47273700 : Py_TRASHCAN_BEGIN(mp, dict_dealloc)
2369 47183600 : if (values != NULL) {
2370 9660310 : for (i = 0, n = mp->ma_keys->dk_nentries; i < n; i++) {
2371 5234120 : Py_XDECREF(values->values[i]);
2372 : }
2373 4426190 : free_values(values);
2374 4426190 : dictkeys_decref(keys);
2375 : }
2376 42757400 : else if (keys != NULL) {
2377 42757400 : assert(keys->dk_refcnt == 1 || keys == Py_EMPTY_KEYS);
2378 42757400 : dictkeys_decref(keys);
2379 : }
2380 : #if PyDict_MAXFREELIST > 0
2381 47183600 : struct _Py_dict_state *state = get_dict_state();
2382 : #ifdef Py_DEBUG
2383 : // new_dict() must not be called after _PyDict_Fini()
2384 47183600 : assert(state->numfree != -1);
2385 : #endif
2386 47183600 : if (state->numfree < PyDict_MAXFREELIST && Py_IS_TYPE(mp, &PyDict_Type)) {
2387 33313500 : state->free_list[state->numfree++] = mp;
2388 33313500 : OBJECT_STAT_INC(to_freelist);
2389 : }
2390 : else
2391 : #endif
2392 : {
2393 13870100 : Py_TYPE(mp)->tp_free((PyObject *)mp);
2394 : }
2395 47183600 : Py_TRASHCAN_END
2396 47273700 : }
2397 :
2398 :
2399 : static PyObject *
2400 5722 : dict_repr(PyDictObject *mp)
2401 : {
2402 : Py_ssize_t i;
2403 5722 : PyObject *key = NULL, *value = NULL;
2404 : _PyUnicodeWriter writer;
2405 : int first;
2406 :
2407 5722 : i = Py_ReprEnter((PyObject *)mp);
2408 5722 : if (i != 0) {
2409 4 : return i > 0 ? PyUnicode_FromString("{...}") : NULL;
2410 : }
2411 :
2412 5718 : if (mp->ma_used == 0) {
2413 286 : Py_ReprLeave((PyObject *)mp);
2414 286 : return PyUnicode_FromString("{}");
2415 : }
2416 :
2417 5432 : _PyUnicodeWriter_Init(&writer);
2418 5432 : writer.overallocate = 1;
2419 : /* "{" + "1: 2" + ", 3: 4" * (len - 1) + "}" */
2420 5432 : writer.min_length = 1 + 4 + (2 + 4) * (mp->ma_used - 1) + 1;
2421 :
2422 5432 : if (_PyUnicodeWriter_WriteChar(&writer, '{') < 0)
2423 0 : goto error;
2424 :
2425 : /* Do repr() on each key+value pair, and insert ": " between them.
2426 : Note that repr may mutate the dict. */
2427 5432 : i = 0;
2428 5432 : first = 1;
2429 271812 : while (PyDict_Next((PyObject *)mp, &i, &key, &value)) {
2430 : PyObject *s;
2431 : int res;
2432 :
2433 : /* Prevent repr from deleting key or value during key format. */
2434 267590 : Py_INCREF(key);
2435 267590 : Py_INCREF(value);
2436 :
2437 267590 : if (!first) {
2438 262158 : if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)
2439 0 : goto error;
2440 : }
2441 267590 : first = 0;
2442 :
2443 267590 : s = PyObject_Repr(key);
2444 267590 : if (s == NULL)
2445 1 : goto error;
2446 267589 : res = _PyUnicodeWriter_WriteStr(&writer, s);
2447 267589 : Py_DECREF(s);
2448 267589 : if (res < 0)
2449 0 : goto error;
2450 :
2451 267589 : if (_PyUnicodeWriter_WriteASCIIString(&writer, ": ", 2) < 0)
2452 0 : goto error;
2453 :
2454 267589 : s = PyObject_Repr(value);
2455 267589 : if (s == NULL)
2456 1209 : goto error;
2457 266380 : res = _PyUnicodeWriter_WriteStr(&writer, s);
2458 266380 : Py_DECREF(s);
2459 266380 : if (res < 0)
2460 0 : goto error;
2461 :
2462 266380 : Py_CLEAR(key);
2463 266380 : Py_CLEAR(value);
2464 : }
2465 :
2466 4222 : writer.overallocate = 0;
2467 4222 : if (_PyUnicodeWriter_WriteChar(&writer, '}') < 0)
2468 0 : goto error;
2469 :
2470 4222 : Py_ReprLeave((PyObject *)mp);
2471 :
2472 4222 : return _PyUnicodeWriter_Finish(&writer);
2473 :
2474 1210 : error:
2475 1210 : Py_ReprLeave((PyObject *)mp);
2476 1210 : _PyUnicodeWriter_Dealloc(&writer);
2477 1210 : Py_XDECREF(key);
2478 1210 : Py_XDECREF(value);
2479 1210 : return NULL;
2480 : }
2481 :
2482 : static Py_ssize_t
2483 1860810 : dict_length(PyDictObject *mp)
2484 : {
2485 1860810 : return mp->ma_used;
2486 : }
2487 :
2488 : static PyObject *
2489 5242500 : dict_subscript(PyDictObject *mp, PyObject *key)
2490 : {
2491 : Py_ssize_t ix;
2492 : Py_hash_t hash;
2493 : PyObject *value;
2494 :
2495 5242500 : if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
2496 1144190 : hash = PyObject_Hash(key);
2497 1144190 : if (hash == -1)
2498 3 : return NULL;
2499 : }
2500 5242490 : ix = _Py_dict_lookup(mp, key, hash, &value);
2501 5242490 : if (ix == DKIX_ERROR)
2502 1 : return NULL;
2503 5242490 : if (ix == DKIX_EMPTY || value == NULL) {
2504 596442 : if (!PyDict_CheckExact(mp)) {
2505 : /* Look up __missing__ method if we're a subclass. */
2506 : PyObject *missing, *res;
2507 317926 : missing = _PyObject_LookupSpecial(
2508 : (PyObject *)mp, &_Py_ID(__missing__));
2509 317926 : if (missing != NULL) {
2510 269299 : res = PyObject_CallOneArg(missing, key);
2511 269299 : Py_DECREF(missing);
2512 269299 : return res;
2513 : }
2514 48627 : else if (PyErr_Occurred())
2515 1 : return NULL;
2516 : }
2517 327142 : _PyErr_SetKeyError(key);
2518 327142 : return NULL;
2519 : }
2520 4646050 : Py_INCREF(value);
2521 4646050 : return value;
2522 : }
2523 :
2524 : static int
2525 4987780 : dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)
2526 : {
2527 4987780 : if (w == NULL)
2528 2482090 : return PyDict_DelItem((PyObject *)mp, v);
2529 : else
2530 2505690 : return PyDict_SetItem((PyObject *)mp, v, w);
2531 : }
2532 :
2533 : static PyMappingMethods dict_as_mapping = {
2534 : (lenfunc)dict_length, /*mp_length*/
2535 : (binaryfunc)dict_subscript, /*mp_subscript*/
2536 : (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
2537 : };
2538 :
2539 : static PyObject *
2540 983729 : dict_keys(PyDictObject *mp)
2541 : {
2542 : PyObject *v;
2543 : Py_ssize_t n;
2544 :
2545 983729 : again:
2546 983729 : n = mp->ma_used;
2547 983729 : v = PyList_New(n);
2548 983729 : if (v == NULL)
2549 0 : return NULL;
2550 983729 : if (n != mp->ma_used) {
2551 : /* Durnit. The allocations caused the dict to resize.
2552 : * Just start over, this shouldn't normally happen.
2553 : */
2554 0 : Py_DECREF(v);
2555 0 : goto again;
2556 : }
2557 :
2558 : /* Nothing we do below makes any function calls. */
2559 983729 : Py_ssize_t j = 0, pos = 0;
2560 : PyObject *key;
2561 10876300 : while (_PyDict_Next((PyObject*)mp, &pos, &key, NULL, NULL)) {
2562 9892600 : assert(j < n);
2563 9892600 : Py_INCREF(key);
2564 9892600 : PyList_SET_ITEM(v, j, key);
2565 9892600 : j++;
2566 : }
2567 983729 : assert(j == n);
2568 983729 : return v;
2569 : }
2570 :
2571 : static PyObject *
2572 7 : dict_values(PyDictObject *mp)
2573 : {
2574 : PyObject *v;
2575 : Py_ssize_t n;
2576 :
2577 7 : again:
2578 7 : n = mp->ma_used;
2579 7 : v = PyList_New(n);
2580 7 : if (v == NULL)
2581 0 : return NULL;
2582 7 : if (n != mp->ma_used) {
2583 : /* Durnit. The allocations caused the dict to resize.
2584 : * Just start over, this shouldn't normally happen.
2585 : */
2586 0 : Py_DECREF(v);
2587 0 : goto again;
2588 : }
2589 :
2590 : /* Nothing we do below makes any function calls. */
2591 7 : Py_ssize_t j = 0, pos = 0;
2592 : PyObject *value;
2593 575 : while (_PyDict_Next((PyObject*)mp, &pos, NULL, &value, NULL)) {
2594 568 : assert(j < n);
2595 568 : Py_INCREF(value);
2596 568 : PyList_SET_ITEM(v, j, value);
2597 568 : j++;
2598 : }
2599 7 : assert(j == n);
2600 7 : return v;
2601 : }
2602 :
2603 : static PyObject *
2604 1397 : dict_items(PyDictObject *mp)
2605 : {
2606 : PyObject *v;
2607 : Py_ssize_t i, n;
2608 : PyObject *item;
2609 :
2610 : /* Preallocate the list of tuples, to avoid allocations during
2611 : * the loop over the items, which could trigger GC, which
2612 : * could resize the dict. :-(
2613 : */
2614 1397 : again:
2615 1397 : n = mp->ma_used;
2616 1397 : v = PyList_New(n);
2617 1397 : if (v == NULL)
2618 0 : return NULL;
2619 27390 : for (i = 0; i < n; i++) {
2620 25993 : item = PyTuple_New(2);
2621 25993 : if (item == NULL) {
2622 0 : Py_DECREF(v);
2623 0 : return NULL;
2624 : }
2625 25993 : PyList_SET_ITEM(v, i, item);
2626 : }
2627 1397 : if (n != mp->ma_used) {
2628 : /* Durnit. The allocations caused the dict to resize.
2629 : * Just start over, this shouldn't normally happen.
2630 : */
2631 0 : Py_DECREF(v);
2632 0 : goto again;
2633 : }
2634 :
2635 : /* Nothing we do below makes any function calls. */
2636 1397 : Py_ssize_t j = 0, pos = 0;
2637 : PyObject *key, *value;
2638 27390 : while (_PyDict_Next((PyObject*)mp, &pos, &key, &value, NULL)) {
2639 25993 : assert(j < n);
2640 25993 : PyObject *item = PyList_GET_ITEM(v, j);
2641 25993 : Py_INCREF(key);
2642 25993 : PyTuple_SET_ITEM(item, 0, key);
2643 25993 : Py_INCREF(value);
2644 25993 : PyTuple_SET_ITEM(item, 1, value);
2645 25993 : j++;
2646 : }
2647 1397 : assert(j == n);
2648 1397 : return v;
2649 : }
2650 :
2651 : /*[clinic input]
2652 : @classmethod
2653 : dict.fromkeys
2654 : iterable: object
2655 : value: object=None
2656 : /
2657 :
2658 : Create a new dictionary with keys from iterable and values set to value.
2659 : [clinic start generated code]*/
2660 :
2661 : static PyObject *
2662 107821 : dict_fromkeys_impl(PyTypeObject *type, PyObject *iterable, PyObject *value)
2663 : /*[clinic end generated code: output=8fb98e4b10384999 input=382ba4855d0f74c3]*/
2664 : {
2665 107821 : return _PyDict_FromKeys((PyObject *)type, iterable, value);
2666 : }
2667 :
2668 : /* Single-arg dict update; used by dict_update_common and operators. */
2669 : static int
2670 5555080 : dict_update_arg(PyObject *self, PyObject *arg)
2671 : {
2672 5555080 : if (PyDict_CheckExact(arg)) {
2673 5437150 : return PyDict_Merge(self, arg, 1);
2674 : }
2675 : PyObject *func;
2676 117930 : if (_PyObject_LookupAttr(arg, &_Py_ID(keys), &func) < 0) {
2677 0 : return -1;
2678 : }
2679 117930 : if (func != NULL) {
2680 43455 : Py_DECREF(func);
2681 43455 : return PyDict_Merge(self, arg, 1);
2682 : }
2683 74475 : return PyDict_MergeFromSeq2(self, arg, 1);
2684 : }
2685 :
2686 : static int
2687 5518840 : dict_update_common(PyObject *self, PyObject *args, PyObject *kwds,
2688 : const char *methname)
2689 : {
2690 5518840 : PyObject *arg = NULL;
2691 5518840 : int result = 0;
2692 :
2693 5518840 : if (!PyArg_UnpackTuple(args, methname, 0, 1, &arg)) {
2694 3 : result = -1;
2695 : }
2696 5518830 : else if (arg != NULL) {
2697 5427850 : result = dict_update_arg(self, arg);
2698 : }
2699 :
2700 5518840 : if (result == 0 && kwds != NULL) {
2701 3945 : if (PyArg_ValidateKeywordArguments(kwds))
2702 3943 : result = PyDict_Merge(self, kwds, 1);
2703 : else
2704 2 : result = -1;
2705 : }
2706 5518840 : return result;
2707 : }
2708 :
2709 : /* Note: dict.update() uses the METH_VARARGS|METH_KEYWORDS calling convention.
2710 : Using METH_FASTCALL|METH_KEYWORDS would make dict.update(**dict2) calls
2711 : slower, see the issue #29312. */
2712 : static PyObject *
2713 5430510 : dict_update(PyObject *self, PyObject *args, PyObject *kwds)
2714 : {
2715 5430510 : if (dict_update_common(self, args, kwds, "update") != -1)
2716 5430480 : Py_RETURN_NONE;
2717 27 : return NULL;
2718 : }
2719 :
2720 : /* Update unconditionally replaces existing items.
2721 : Merge has a 3rd argument 'override'; if set, it acts like Update,
2722 : otherwise it leaves existing items unchanged.
2723 :
2724 : PyDict_{Update,Merge} update/merge from a mapping object.
2725 :
2726 : PyDict_MergeFromSeq2 updates/merges from any iterable object
2727 : producing iterable objects of length 2.
2728 : */
2729 :
2730 : int
2731 74475 : PyDict_MergeFromSeq2(PyObject *d, PyObject *seq2, int override)
2732 : {
2733 : PyObject *it; /* iter(seq2) */
2734 : Py_ssize_t i; /* index into seq2 of current element */
2735 : PyObject *item; /* seq2[i] */
2736 : PyObject *fast; /* item as a 2-tuple or 2-list */
2737 :
2738 74475 : assert(d != NULL);
2739 74475 : assert(PyDict_Check(d));
2740 74475 : assert(seq2 != NULL);
2741 :
2742 74475 : it = PyObject_GetIter(seq2);
2743 74475 : if (it == NULL)
2744 15 : return -1;
2745 :
2746 853465 : for (i = 0; ; ++i) {
2747 : PyObject *key, *value;
2748 : Py_ssize_t n;
2749 :
2750 853465 : fast = NULL;
2751 853465 : item = PyIter_Next(it);
2752 853465 : if (item == NULL) {
2753 74449 : if (PyErr_Occurred())
2754 6 : goto Fail;
2755 74443 : break;
2756 : }
2757 :
2758 : /* Convert item to sequence, and verify length 2. */
2759 779016 : fast = PySequence_Fast(item, "");
2760 779016 : if (fast == NULL) {
2761 2 : if (PyErr_ExceptionMatches(PyExc_TypeError))
2762 2 : PyErr_Format(PyExc_TypeError,
2763 : "cannot convert dictionary update "
2764 : "sequence element #%zd to a sequence",
2765 : i);
2766 2 : goto Fail;
2767 : }
2768 779014 : n = PySequence_Fast_GET_SIZE(fast);
2769 779014 : if (n != 2) {
2770 9 : PyErr_Format(PyExc_ValueError,
2771 : "dictionary update sequence element #%zd "
2772 : "has length %zd; 2 is required",
2773 : i, n);
2774 9 : goto Fail;
2775 : }
2776 :
2777 : /* Update/merge with this (key, value) pair. */
2778 779005 : key = PySequence_Fast_GET_ITEM(fast, 0);
2779 779005 : value = PySequence_Fast_GET_ITEM(fast, 1);
2780 779005 : Py_INCREF(key);
2781 779005 : Py_INCREF(value);
2782 779005 : if (override) {
2783 779005 : if (PyDict_SetItem(d, key, value) < 0) {
2784 0 : Py_DECREF(key);
2785 0 : Py_DECREF(value);
2786 0 : goto Fail;
2787 : }
2788 : }
2789 : else {
2790 0 : if (PyDict_SetDefault(d, key, value) == NULL) {
2791 0 : Py_DECREF(key);
2792 0 : Py_DECREF(value);
2793 0 : goto Fail;
2794 : }
2795 : }
2796 :
2797 779005 : Py_DECREF(key);
2798 779005 : Py_DECREF(value);
2799 779005 : Py_DECREF(fast);
2800 779005 : Py_DECREF(item);
2801 : }
2802 :
2803 74443 : i = 0;
2804 74443 : ASSERT_CONSISTENT(d);
2805 74443 : goto Return;
2806 17 : Fail:
2807 17 : Py_XDECREF(item);
2808 17 : Py_XDECREF(fast);
2809 17 : i = -1;
2810 74460 : Return:
2811 74460 : Py_DECREF(it);
2812 74460 : return Py_SAFE_DOWNCAST(i, Py_ssize_t, int);
2813 : }
2814 :
2815 : static int
2816 9241220 : dict_merge(PyObject *a, PyObject *b, int override)
2817 : {
2818 : PyDictObject *mp, *other;
2819 :
2820 9241220 : assert(0 <= override && override <= 2);
2821 :
2822 : /* We accept for the argument either a concrete dictionary object,
2823 : * or an abstract "mapping" object. For the former, we can do
2824 : * things quite efficiently. For the latter, we only require that
2825 : * PyMapping_Keys() and PyObject_GetItem() be supported.
2826 : */
2827 9241220 : if (a == NULL || !PyDict_Check(a) || b == NULL) {
2828 0 : PyErr_BadInternalCall();
2829 0 : return -1;
2830 : }
2831 9241220 : mp = (PyDictObject*)a;
2832 9626210 : if (PyDict_Check(b) && (Py_TYPE(b)->tp_iter == (getiterfunc)dict_iter)) {
2833 9140630 : other = (PyDictObject*)b;
2834 9140630 : if (other == mp || other->ma_used == 0)
2835 : /* a.update(a) or a.update({}); nothing to do */
2836 8755640 : return 0;
2837 1126890 : if (mp->ma_used == 0) {
2838 : /* Since the target dict is empty, PyDict_GetItem()
2839 : * always returns NULL. Setting override to 1
2840 : * skips the unnecessary test.
2841 : */
2842 805337 : override = 1;
2843 805337 : PyDictKeysObject *okeys = other->ma_keys;
2844 :
2845 : // If other is clean, combined, and just allocated, just clone it.
2846 805337 : if (other->ma_values == NULL &&
2847 799424 : other->ma_used == okeys->dk_nentries &&
2848 754378 : (DK_LOG_SIZE(okeys) == PyDict_LOG_MINSIZE ||
2849 35960 : USABLE_FRACTION(DK_SIZE(okeys)/2) < other->ma_used)) {
2850 741884 : PyDictKeysObject *keys = clone_combined_dict_keys(other);
2851 741884 : if (keys == NULL) {
2852 2 : return -1;
2853 : }
2854 :
2855 741882 : dictkeys_decref(mp->ma_keys);
2856 741882 : mp->ma_keys = keys;
2857 741882 : if (mp->ma_values != NULL) {
2858 45682 : free_values(mp->ma_values);
2859 45682 : mp->ma_values = NULL;
2860 : }
2861 :
2862 741882 : mp->ma_used = other->ma_used;
2863 741882 : mp->ma_version_tag = DICT_NEXT_VERSION();
2864 741882 : ASSERT_CONSISTENT(mp);
2865 :
2866 741882 : if (_PyObject_GC_IS_TRACKED(other) && !_PyObject_GC_IS_TRACKED(mp)) {
2867 : /* Maintain tracking. */
2868 160362 : _PyObject_GC_TRACK(mp);
2869 : }
2870 :
2871 741882 : return 0;
2872 : }
2873 : }
2874 : /* Do one big resize at the start, rather than
2875 : * incrementally resizing as we insert new items. Expect
2876 : * that there will be no (or few) overlapping keys.
2877 : */
2878 385003 : if (USABLE_FRACTION(DK_SIZE(mp->ma_keys)) < other->ma_used) {
2879 93342 : int unicode = DK_IS_UNICODE(other->ma_keys);
2880 93342 : if (dictresize(mp, estimate_log2_keysize(mp->ma_used + other->ma_used), unicode)) {
2881 0 : return -1;
2882 : }
2883 : }
2884 :
2885 385003 : Py_ssize_t orig_size = other->ma_keys->dk_nentries;
2886 385003 : Py_ssize_t pos = 0;
2887 : Py_hash_t hash;
2888 : PyObject *key, *value;
2889 :
2890 6442520 : while (_PyDict_Next((PyObject*)other, &pos, &key, &value, &hash)) {
2891 6057530 : int err = 0;
2892 6057530 : Py_INCREF(key);
2893 6057530 : Py_INCREF(value);
2894 6057530 : if (override == 1) {
2895 6019710 : Py_INCREF(key);
2896 6019710 : Py_INCREF(value);
2897 6019710 : err = insertdict(mp, key, hash, value);
2898 : }
2899 : else {
2900 37821 : err = _PyDict_Contains_KnownHash(a, key, hash);
2901 37821 : if (err == 0) {
2902 37811 : Py_INCREF(key);
2903 37811 : Py_INCREF(value);
2904 37811 : err = insertdict(mp, key, hash, value);
2905 : }
2906 10 : else if (err > 0) {
2907 10 : if (override != 0) {
2908 10 : _PyErr_SetKeyError(key);
2909 10 : Py_DECREF(value);
2910 10 : Py_DECREF(key);
2911 10 : return -1;
2912 : }
2913 0 : err = 0;
2914 : }
2915 : }
2916 6057520 : Py_DECREF(value);
2917 6057520 : Py_DECREF(key);
2918 6057520 : if (err != 0)
2919 1 : return -1;
2920 :
2921 6057520 : if (orig_size != other->ma_keys->dk_nentries) {
2922 1 : PyErr_SetString(PyExc_RuntimeError,
2923 : "dict mutated during update");
2924 1 : return -1;
2925 : }
2926 : }
2927 : }
2928 : else {
2929 : /* Do it the generic, slower way */
2930 100587 : PyObject *keys = PyMapping_Keys(b);
2931 : PyObject *iter;
2932 : PyObject *key, *value;
2933 : int status;
2934 :
2935 100587 : if (keys == NULL)
2936 : /* Docstring says this is equivalent to E.keys() so
2937 : * if E doesn't have a .keys() method we want
2938 : * AttributeError to percolate up. Might as well
2939 : * do the same for any other error.
2940 : */
2941 23 : return -1;
2942 :
2943 100564 : iter = PyObject_GetIter(keys);
2944 100564 : Py_DECREF(keys);
2945 100564 : if (iter == NULL)
2946 0 : return -1;
2947 :
2948 2524540 : for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) {
2949 2423980 : if (override != 1) {
2950 149 : status = PyDict_Contains(a, key);
2951 149 : if (status != 0) {
2952 3 : if (status > 0) {
2953 3 : if (override == 0) {
2954 0 : Py_DECREF(key);
2955 0 : continue;
2956 : }
2957 3 : _PyErr_SetKeyError(key);
2958 : }
2959 3 : Py_DECREF(key);
2960 3 : Py_DECREF(iter);
2961 3 : return -1;
2962 : }
2963 : }
2964 2423980 : value = PyObject_GetItem(b, key);
2965 2423980 : if (value == NULL) {
2966 5 : Py_DECREF(iter);
2967 5 : Py_DECREF(key);
2968 5 : return -1;
2969 : }
2970 2423980 : status = PyDict_SetItem(a, key, value);
2971 2423980 : Py_DECREF(key);
2972 2423980 : Py_DECREF(value);
2973 2423980 : if (status < 0) {
2974 0 : Py_DECREF(iter);
2975 0 : return -1;
2976 : }
2977 : }
2978 100556 : Py_DECREF(iter);
2979 100556 : if (PyErr_Occurred())
2980 : /* Iterator completed, via error */
2981 0 : return -1;
2982 : }
2983 485547 : ASSERT_CONSISTENT(a);
2984 485547 : return 0;
2985 : }
2986 :
2987 : int
2988 342067 : PyDict_Update(PyObject *a, PyObject *b)
2989 : {
2990 342067 : return dict_merge(a, b, 1);
2991 : }
2992 :
2993 : int
2994 5484880 : PyDict_Merge(PyObject *a, PyObject *b, int override)
2995 : {
2996 : /* XXX Deprecate override not in (0, 1). */
2997 5484880 : return dict_merge(a, b, override != 0);
2998 : }
2999 :
3000 : int
3001 3412470 : _PyDict_MergeEx(PyObject *a, PyObject *b, int override)
3002 : {
3003 3412470 : return dict_merge(a, b, override);
3004 : }
3005 :
3006 : static PyObject *
3007 80177 : dict_copy(PyDictObject *mp, PyObject *Py_UNUSED(ignored))
3008 : {
3009 80177 : return PyDict_Copy((PyObject*)mp);
3010 : }
3011 :
3012 : PyObject *
3013 2617740 : PyDict_Copy(PyObject *o)
3014 : {
3015 : PyObject *copy;
3016 : PyDictObject *mp;
3017 : Py_ssize_t i, n;
3018 :
3019 2617740 : if (o == NULL || !PyDict_Check(o)) {
3020 0 : PyErr_BadInternalCall();
3021 0 : return NULL;
3022 : }
3023 :
3024 2617740 : mp = (PyDictObject *)o;
3025 2617740 : if (mp->ma_used == 0) {
3026 : /* The dict is empty; just return a new dict. */
3027 28369 : return PyDict_New();
3028 : }
3029 :
3030 2589370 : if (_PyDict_HasSplitTable(mp)) {
3031 : PyDictObject *split_copy;
3032 2288 : Py_ssize_t size = shared_keys_usable_size(mp->ma_keys);
3033 : PyDictValues *newvalues;
3034 2288 : newvalues = new_values(size);
3035 2288 : if (newvalues == NULL)
3036 0 : return PyErr_NoMemory();
3037 2288 : split_copy = PyObject_GC_New(PyDictObject, &PyDict_Type);
3038 2288 : if (split_copy == NULL) {
3039 0 : free_values(newvalues);
3040 0 : return NULL;
3041 : }
3042 2288 : size_t prefix_size = ((uint8_t *)newvalues)[-1];
3043 2288 : memcpy(((char *)newvalues)-prefix_size, ((char *)mp->ma_values)-prefix_size, prefix_size-1);
3044 2288 : split_copy->ma_values = newvalues;
3045 2288 : split_copy->ma_keys = mp->ma_keys;
3046 2288 : split_copy->ma_used = mp->ma_used;
3047 2288 : split_copy->ma_version_tag = DICT_NEXT_VERSION();
3048 2288 : dictkeys_incref(mp->ma_keys);
3049 61208 : for (i = 0, n = size; i < n; i++) {
3050 58920 : PyObject *value = mp->ma_values->values[i];
3051 58920 : Py_XINCREF(value);
3052 58920 : split_copy->ma_values->values[i] = value;
3053 : }
3054 2288 : if (_PyObject_GC_IS_TRACKED(mp))
3055 2006 : _PyObject_GC_TRACK(split_copy);
3056 2288 : return (PyObject *)split_copy;
3057 : }
3058 :
3059 2587080 : if (Py_TYPE(mp)->tp_iter == (getiterfunc)dict_iter &&
3060 2587080 : mp->ma_values == NULL &&
3061 2587080 : (mp->ma_used >= (mp->ma_keys->dk_nentries * 2) / 3))
3062 : {
3063 : /* Use fast-copy if:
3064 :
3065 : (1) type(mp) doesn't override tp_iter; and
3066 :
3067 : (2) 'mp' is not a split-dict; and
3068 :
3069 : (3) if 'mp' is non-compact ('del' operation does not resize dicts),
3070 : do fast-copy only if it has at most 1/3 non-used keys.
3071 :
3072 : The last condition (3) is important to guard against a pathological
3073 : case when a large dict is almost emptied with multiple del/pop
3074 : operations and copied after that. In cases like this, we defer to
3075 : PyDict_Merge, which produces a compacted copy.
3076 : */
3077 2585290 : PyDictKeysObject *keys = clone_combined_dict_keys(mp);
3078 2585290 : if (keys == NULL) {
3079 2 : return NULL;
3080 : }
3081 2585290 : PyDictObject *new = (PyDictObject *)new_dict(keys, NULL, 0, 0);
3082 2585290 : if (new == NULL) {
3083 : /* In case of an error, `new_dict()` takes care of
3084 : cleaning up `keys`. */
3085 0 : return NULL;
3086 : }
3087 :
3088 2585290 : new->ma_used = mp->ma_used;
3089 2585290 : ASSERT_CONSISTENT(new);
3090 2585290 : if (_PyObject_GC_IS_TRACKED(mp)) {
3091 : /* Maintain tracking. */
3092 2168460 : _PyObject_GC_TRACK(new);
3093 : }
3094 :
3095 2585290 : return (PyObject *)new;
3096 : }
3097 :
3098 1794 : copy = PyDict_New();
3099 1794 : if (copy == NULL)
3100 0 : return NULL;
3101 1794 : if (dict_merge(copy, o, 1) == 0)
3102 1794 : return copy;
3103 0 : Py_DECREF(copy);
3104 0 : return NULL;
3105 : }
3106 :
3107 : Py_ssize_t
3108 2039390 : PyDict_Size(PyObject *mp)
3109 : {
3110 2039390 : if (mp == NULL || !PyDict_Check(mp)) {
3111 0 : PyErr_BadInternalCall();
3112 0 : return -1;
3113 : }
3114 2039390 : return ((PyDictObject *)mp)->ma_used;
3115 : }
3116 :
3117 : PyObject *
3118 983729 : PyDict_Keys(PyObject *mp)
3119 : {
3120 983729 : if (mp == NULL || !PyDict_Check(mp)) {
3121 0 : PyErr_BadInternalCall();
3122 0 : return NULL;
3123 : }
3124 983729 : return dict_keys((PyDictObject *)mp);
3125 : }
3126 :
3127 : PyObject *
3128 7 : PyDict_Values(PyObject *mp)
3129 : {
3130 7 : if (mp == NULL || !PyDict_Check(mp)) {
3131 0 : PyErr_BadInternalCall();
3132 0 : return NULL;
3133 : }
3134 7 : return dict_values((PyDictObject *)mp);
3135 : }
3136 :
3137 : PyObject *
3138 1397 : PyDict_Items(PyObject *mp)
3139 : {
3140 1397 : if (mp == NULL || !PyDict_Check(mp)) {
3141 0 : PyErr_BadInternalCall();
3142 0 : return NULL;
3143 : }
3144 1397 : return dict_items((PyDictObject *)mp);
3145 : }
3146 :
3147 : /* Return 1 if dicts equal, 0 if not, -1 if error.
3148 : * Gets out as soon as any difference is detected.
3149 : * Uses only Py_EQ comparison.
3150 : */
3151 : static int
3152 122118 : dict_equal(PyDictObject *a, PyDictObject *b)
3153 : {
3154 : Py_ssize_t i;
3155 :
3156 122118 : if (a->ma_used != b->ma_used)
3157 : /* can't be equal if # of entries differ */
3158 16593 : return 0;
3159 : /* Same # of entries -- check all of 'em. Exit early on any diff. */
3160 1603030 : for (i = 0; i < a->ma_keys->dk_nentries; i++) {
3161 : PyObject *key, *aval;
3162 : Py_hash_t hash;
3163 1505050 : if (DK_IS_UNICODE(a->ma_keys)) {
3164 1270730 : PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(a->ma_keys)[i];
3165 1270730 : key = ep->me_key;
3166 1270730 : if (key == NULL) {
3167 398 : continue;
3168 : }
3169 1270330 : hash = unicode_get_hash(key);
3170 1270330 : if (a->ma_values)
3171 2972 : aval = a->ma_values->values[i];
3172 : else
3173 1267360 : aval = ep->me_value;
3174 : }
3175 : else {
3176 234324 : PyDictKeyEntry *ep = &DK_ENTRIES(a->ma_keys)[i];
3177 234324 : key = ep->me_key;
3178 234324 : aval = ep->me_value;
3179 234324 : hash = ep->me_hash;
3180 : }
3181 1504660 : if (aval != NULL) {
3182 : int cmp;
3183 : PyObject *bval;
3184 : /* temporarily bump aval's refcount to ensure it stays
3185 : alive until we're done with it */
3186 1504160 : Py_INCREF(aval);
3187 : /* ditto for key */
3188 1504160 : Py_INCREF(key);
3189 : /* reuse the known hash value */
3190 1504160 : _Py_dict_lookup(b, key, hash, &bval);
3191 1504160 : if (bval == NULL) {
3192 5551 : Py_DECREF(key);
3193 5551 : Py_DECREF(aval);
3194 5551 : if (PyErr_Occurred())
3195 7545 : return -1;
3196 5549 : return 0;
3197 : }
3198 1498610 : Py_INCREF(bval);
3199 1498610 : cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
3200 1498610 : Py_DECREF(key);
3201 1498610 : Py_DECREF(aval);
3202 1498610 : Py_DECREF(bval);
3203 1498610 : if (cmp <= 0) /* error or not equal */
3204 1994 : return cmp;
3205 : }
3206 : }
3207 97980 : return 1;
3208 : }
3209 :
3210 : static PyObject *
3211 122481 : dict_richcompare(PyObject *v, PyObject *w, int op)
3212 : {
3213 : int cmp;
3214 : PyObject *res;
3215 :
3216 122481 : if (!PyDict_Check(v) || !PyDict_Check(w)) {
3217 331 : res = Py_NotImplemented;
3218 : }
3219 122150 : else if (op == Py_EQ || op == Py_NE) {
3220 122118 : cmp = dict_equal((PyDictObject *)v, (PyDictObject *)w);
3221 122118 : if (cmp < 0)
3222 1934 : return NULL;
3223 120184 : res = (cmp == (op == Py_EQ)) ? Py_True : Py_False;
3224 : }
3225 : else
3226 32 : res = Py_NotImplemented;
3227 120547 : Py_INCREF(res);
3228 120547 : return res;
3229 : }
3230 :
3231 : /*[clinic input]
3232 :
3233 : @coexist
3234 : dict.__contains__
3235 :
3236 : key: object
3237 : /
3238 :
3239 : True if the dictionary has the specified key, else False.
3240 : [clinic start generated code]*/
3241 :
3242 : static PyObject *
3243 175896 : dict___contains__(PyDictObject *self, PyObject *key)
3244 : /*[clinic end generated code: output=a3d03db709ed6e6b input=fe1cb42ad831e820]*/
3245 : {
3246 175896 : register PyDictObject *mp = self;
3247 : Py_hash_t hash;
3248 : Py_ssize_t ix;
3249 : PyObject *value;
3250 :
3251 175896 : if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
3252 3269 : hash = PyObject_Hash(key);
3253 3269 : if (hash == -1)
3254 0 : return NULL;
3255 : }
3256 175896 : ix = _Py_dict_lookup(mp, key, hash, &value);
3257 175896 : if (ix == DKIX_ERROR)
3258 1 : return NULL;
3259 175895 : if (ix == DKIX_EMPTY || value == NULL)
3260 70840 : Py_RETURN_FALSE;
3261 105055 : Py_RETURN_TRUE;
3262 : }
3263 :
3264 : /*[clinic input]
3265 : dict.get
3266 :
3267 : key: object
3268 : default: object = None
3269 : /
3270 :
3271 : Return the value for key if key is in the dictionary, else default.
3272 : [clinic start generated code]*/
3273 :
3274 : static PyObject *
3275 18825700 : dict_get_impl(PyDictObject *self, PyObject *key, PyObject *default_value)
3276 : /*[clinic end generated code: output=bba707729dee05bf input=279ddb5790b6b107]*/
3277 : {
3278 18825700 : PyObject *val = NULL;
3279 : Py_hash_t hash;
3280 : Py_ssize_t ix;
3281 :
3282 18825700 : if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
3283 12016000 : hash = PyObject_Hash(key);
3284 12016000 : if (hash == -1)
3285 3 : return NULL;
3286 : }
3287 18825700 : ix = _Py_dict_lookup(self, key, hash, &val);
3288 18825700 : if (ix == DKIX_ERROR)
3289 1 : return NULL;
3290 18825700 : if (ix == DKIX_EMPTY || val == NULL) {
3291 9524350 : val = default_value;
3292 : }
3293 18825700 : Py_INCREF(val);
3294 18825700 : return val;
3295 : }
3296 :
3297 : PyObject *
3298 112826000 : PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj)
3299 : {
3300 112826000 : PyDictObject *mp = (PyDictObject *)d;
3301 : PyObject *value;
3302 : Py_hash_t hash;
3303 :
3304 112826000 : if (!PyDict_Check(d)) {
3305 0 : PyErr_BadInternalCall();
3306 0 : return NULL;
3307 : }
3308 :
3309 112826000 : if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
3310 98811600 : hash = PyObject_Hash(key);
3311 98811600 : if (hash == -1)
3312 5 : return NULL;
3313 : }
3314 :
3315 112826000 : if (mp->ma_keys == Py_EMPTY_KEYS) {
3316 190575 : Py_INCREF(key);
3317 190575 : Py_INCREF(defaultobj);
3318 190575 : if (insert_to_emptydict(mp, key, hash, defaultobj) < 0) {
3319 0 : return NULL;
3320 : }
3321 190575 : return defaultobj;
3322 : }
3323 :
3324 112635000 : if (!PyUnicode_CheckExact(key) && DK_IS_UNICODE(mp->ma_keys)) {
3325 52337 : if (insertion_resize(mp, 0) < 0) {
3326 0 : return NULL;
3327 : }
3328 : }
3329 :
3330 112635000 : Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &value);
3331 112635000 : if (ix == DKIX_ERROR)
3332 1 : return NULL;
3333 :
3334 112635000 : if (ix == DKIX_EMPTY) {
3335 34394900 : mp->ma_keys->dk_version = 0;
3336 34394900 : value = defaultobj;
3337 34394900 : if (mp->ma_keys->dk_usable <= 0) {
3338 829211 : if (insertion_resize(mp, 1) < 0) {
3339 0 : return NULL;
3340 : }
3341 : }
3342 34394900 : Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
3343 34394900 : dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
3344 34394900 : if (DK_IS_UNICODE(mp->ma_keys)) {
3345 29983800 : assert(PyUnicode_CheckExact(key));
3346 29983800 : PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
3347 29983800 : ep->me_key = key;
3348 29983800 : if (_PyDict_HasSplitTable(mp)) {
3349 85 : Py_ssize_t index = (int)mp->ma_keys->dk_nentries;
3350 85 : assert(index < SHARED_KEYS_MAX_SIZE);
3351 85 : assert(mp->ma_values->values[index] == NULL);
3352 85 : mp->ma_values->values[index] = value;
3353 85 : _PyDictValues_AddToInsertionOrder(mp->ma_values, index);
3354 : }
3355 : else {
3356 29983700 : ep->me_value = value;
3357 : }
3358 : }
3359 : else {
3360 4411080 : PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
3361 4411080 : ep->me_key = key;
3362 4411080 : ep->me_hash = hash;
3363 4411080 : ep->me_value = value;
3364 : }
3365 34394900 : Py_INCREF(key);
3366 34394900 : Py_INCREF(value);
3367 34394900 : MAINTAIN_TRACKING(mp, key, value);
3368 34394900 : mp->ma_used++;
3369 34394900 : mp->ma_version_tag = DICT_NEXT_VERSION();
3370 34394900 : mp->ma_keys->dk_usable--;
3371 34394900 : mp->ma_keys->dk_nentries++;
3372 34394900 : assert(mp->ma_keys->dk_usable >= 0);
3373 : }
3374 78240000 : else if (value == NULL) {
3375 18 : value = defaultobj;
3376 18 : assert(_PyDict_HasSplitTable(mp));
3377 18 : assert(mp->ma_values->values[ix] == NULL);
3378 18 : Py_INCREF(value);
3379 18 : MAINTAIN_TRACKING(mp, key, value);
3380 18 : mp->ma_values->values[ix] = value;
3381 18 : _PyDictValues_AddToInsertionOrder(mp->ma_values, ix);
3382 18 : mp->ma_used++;
3383 18 : mp->ma_version_tag = DICT_NEXT_VERSION();
3384 : }
3385 :
3386 112635000 : ASSERT_CONSISTENT(mp);
3387 112635000 : return value;
3388 : }
3389 :
3390 : /*[clinic input]
3391 : dict.setdefault
3392 :
3393 : key: object
3394 : default: object = None
3395 : /
3396 :
3397 : Insert key with a value of default if key is not in the dictionary.
3398 :
3399 : Return the value for key if key is in the dictionary, else default.
3400 : [clinic start generated code]*/
3401 :
3402 : static PyObject *
3403 419018 : dict_setdefault_impl(PyDictObject *self, PyObject *key,
3404 : PyObject *default_value)
3405 : /*[clinic end generated code: output=f8c1101ebf69e220 input=0f063756e815fd9d]*/
3406 : {
3407 : PyObject *val;
3408 :
3409 419018 : val = PyDict_SetDefault((PyObject *)self, key, default_value);
3410 419018 : Py_XINCREF(val);
3411 419018 : return val;
3412 : }
3413 :
3414 : static PyObject *
3415 130957 : dict_clear(PyDictObject *mp, PyObject *Py_UNUSED(ignored))
3416 : {
3417 130957 : PyDict_Clear((PyObject *)mp);
3418 130957 : Py_RETURN_NONE;
3419 : }
3420 :
3421 : /*[clinic input]
3422 : dict.pop
3423 :
3424 : key: object
3425 : default: object = NULL
3426 : /
3427 :
3428 : D.pop(k[,d]) -> v, remove specified key and return the corresponding value.
3429 :
3430 : If the key is not found, return the default if given; otherwise,
3431 : raise a KeyError.
3432 : [clinic start generated code]*/
3433 :
3434 : static PyObject *
3435 772820 : dict_pop_impl(PyDictObject *self, PyObject *key, PyObject *default_value)
3436 : /*[clinic end generated code: output=3abb47b89f24c21c input=e221baa01044c44c]*/
3437 : {
3438 772820 : return _PyDict_Pop((PyObject*)self, key, default_value);
3439 : }
3440 :
3441 : /*[clinic input]
3442 : dict.popitem
3443 :
3444 : Remove and return a (key, value) pair as a 2-tuple.
3445 :
3446 : Pairs are returned in LIFO (last-in, first-out) order.
3447 : Raises KeyError if the dict is empty.
3448 : [clinic start generated code]*/
3449 :
3450 : static PyObject *
3451 19389 : dict_popitem_impl(PyDictObject *self)
3452 : /*[clinic end generated code: output=e65fcb04420d230d input=1c38a49f21f64941]*/
3453 : {
3454 : Py_ssize_t i, j;
3455 : PyObject *res;
3456 :
3457 : /* Allocate the result tuple before checking the size. Believe it
3458 : * or not, this allocation could trigger a garbage collection which
3459 : * could empty the dict, so if we checked the size first and that
3460 : * happened, the result would be an infinite loop (searching for an
3461 : * entry that no longer exists). Note that the usual popitem()
3462 : * idiom is "while d: k, v = d.popitem()". so needing to throw the
3463 : * tuple away if the dict *is* empty isn't a significant
3464 : * inefficiency -- possible, but unlikely in practice.
3465 : */
3466 19389 : res = PyTuple_New(2);
3467 19389 : if (res == NULL)
3468 0 : return NULL;
3469 19389 : if (self->ma_used == 0) {
3470 1391 : Py_DECREF(res);
3471 1391 : PyErr_SetString(PyExc_KeyError, "popitem(): dictionary is empty");
3472 1391 : return NULL;
3473 : }
3474 : /* Convert split table to combined table */
3475 17998 : if (self->ma_keys->dk_kind == DICT_KEYS_SPLIT) {
3476 1 : if (dictresize(self, DK_LOG_SIZE(self->ma_keys), 1)) {
3477 0 : Py_DECREF(res);
3478 0 : return NULL;
3479 : }
3480 : }
3481 17998 : self->ma_keys->dk_version = 0;
3482 :
3483 : /* Pop last item */
3484 : PyObject *key, *value;
3485 : Py_hash_t hash;
3486 17998 : if (DK_IS_UNICODE(self->ma_keys)) {
3487 17830 : PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(self->ma_keys);
3488 17830 : i = self->ma_keys->dk_nentries - 1;
3489 17838 : while (i >= 0 && ep0[i].me_value == NULL) {
3490 8 : i--;
3491 : }
3492 17830 : assert(i >= 0);
3493 :
3494 17830 : key = ep0[i].me_key;
3495 17830 : hash = unicode_get_hash(key);
3496 17830 : value = ep0[i].me_value;
3497 17830 : ep0[i].me_key = NULL;
3498 17830 : ep0[i].me_value = NULL;
3499 : }
3500 : else {
3501 168 : PyDictKeyEntry *ep0 = DK_ENTRIES(self->ma_keys);
3502 168 : i = self->ma_keys->dk_nentries - 1;
3503 182 : while (i >= 0 && ep0[i].me_value == NULL) {
3504 14 : i--;
3505 : }
3506 168 : assert(i >= 0);
3507 :
3508 168 : key = ep0[i].me_key;
3509 168 : hash = ep0[i].me_hash;
3510 168 : value = ep0[i].me_value;
3511 168 : ep0[i].me_key = NULL;
3512 168 : ep0[i].me_hash = -1;
3513 168 : ep0[i].me_value = NULL;
3514 : }
3515 :
3516 17998 : j = lookdict_index(self->ma_keys, hash, i);
3517 17998 : assert(j >= 0);
3518 17998 : assert(dictkeys_get_index(self->ma_keys, j) == i);
3519 17998 : dictkeys_set_index(self->ma_keys, j, DKIX_DUMMY);
3520 :
3521 17998 : PyTuple_SET_ITEM(res, 0, key);
3522 17998 : PyTuple_SET_ITEM(res, 1, value);
3523 : /* We can't dk_usable++ since there is DKIX_DUMMY in indices */
3524 17998 : self->ma_keys->dk_nentries = i;
3525 17998 : self->ma_used--;
3526 17998 : self->ma_version_tag = DICT_NEXT_VERSION();
3527 17998 : ASSERT_CONSISTENT(self);
3528 17998 : return res;
3529 : }
3530 :
3531 : static int
3532 105582000 : dict_traverse(PyObject *op, visitproc visit, void *arg)
3533 : {
3534 105582000 : PyDictObject *mp = (PyDictObject *)op;
3535 105582000 : PyDictKeysObject *keys = mp->ma_keys;
3536 105582000 : Py_ssize_t i, n = keys->dk_nentries;
3537 :
3538 105582000 : if (DK_IS_UNICODE(keys)) {
3539 93179300 : if (mp->ma_values != NULL) {
3540 6606410 : for (i = 0; i < n; i++) {
3541 5805210 : Py_VISIT(mp->ma_values->values[i]);
3542 : }
3543 : }
3544 : else {
3545 92378100 : PyDictUnicodeEntry *entries = DK_UNICODE_ENTRIES(keys);
3546 1288550000 : for (i = 0; i < n; i++) {
3547 1196170000 : Py_VISIT(entries[i].me_value);
3548 : }
3549 : }
3550 : }
3551 : else {
3552 12403200 : PyDictKeyEntry *entries = DK_ENTRIES(keys);
3553 104032000 : for (i = 0; i < n; i++) {
3554 91628900 : if (entries[i].me_value != NULL) {
3555 82727800 : Py_VISIT(entries[i].me_value);
3556 82727800 : Py_VISIT(entries[i].me_key);
3557 : }
3558 : }
3559 : }
3560 105582000 : return 0;
3561 : }
3562 :
3563 : static int
3564 368057 : dict_tp_clear(PyObject *op)
3565 : {
3566 368057 : PyDict_Clear(op);
3567 368057 : return 0;
3568 : }
3569 :
3570 : static PyObject *dictiter_new(PyDictObject *, PyTypeObject *);
3571 :
3572 : Py_ssize_t
3573 46 : _PyDict_SizeOf(PyDictObject *mp)
3574 : {
3575 : Py_ssize_t res;
3576 :
3577 46 : res = _PyObject_SIZE(Py_TYPE(mp));
3578 46 : if (mp->ma_values) {
3579 15 : res += shared_keys_usable_size(mp->ma_keys) * sizeof(PyObject*);
3580 : }
3581 : /* If the dictionary is split, the keys portion is accounted-for
3582 : in the type object. */
3583 46 : if (mp->ma_keys->dk_refcnt == 1) {
3584 26 : res += _PyDict_KeysSize(mp->ma_keys);
3585 : }
3586 46 : return res;
3587 : }
3588 :
3589 : Py_ssize_t
3590 3327200 : _PyDict_KeysSize(PyDictKeysObject *keys)
3591 : {
3592 6654400 : size_t es = keys->dk_kind == DICT_KEYS_GENERAL
3593 3327200 : ? sizeof(PyDictKeyEntry) : sizeof(PyDictUnicodeEntry);
3594 : return (sizeof(PyDictKeysObject)
3595 3327200 : + ((size_t)1 << keys->dk_log2_index_bytes)
3596 3327200 : + USABLE_FRACTION(DK_SIZE(keys)) * es);
3597 : }
3598 :
3599 : static PyObject *
3600 34 : dict_sizeof(PyDictObject *mp, PyObject *Py_UNUSED(ignored))
3601 : {
3602 34 : return PyLong_FromSsize_t(_PyDict_SizeOf(mp));
3603 : }
3604 :
3605 : static PyObject *
3606 219 : dict_or(PyObject *self, PyObject *other)
3607 : {
3608 219 : if (!PyDict_Check(self) || !PyDict_Check(other)) {
3609 14 : Py_RETURN_NOTIMPLEMENTED;
3610 : }
3611 205 : PyObject *new = PyDict_Copy(self);
3612 205 : if (new == NULL) {
3613 0 : return NULL;
3614 : }
3615 205 : if (dict_update_arg(new, other)) {
3616 0 : Py_DECREF(new);
3617 0 : return NULL;
3618 : }
3619 205 : return new;
3620 : }
3621 :
3622 : static PyObject *
3623 1225 : dict_ior(PyObject *self, PyObject *other)
3624 : {
3625 1225 : if (dict_update_arg(self, other)) {
3626 3 : return NULL;
3627 : }
3628 1222 : Py_INCREF(self);
3629 1222 : return self;
3630 : }
3631 :
3632 : PyDoc_STRVAR(getitem__doc__, "x.__getitem__(y) <==> x[y]");
3633 :
3634 : PyDoc_STRVAR(sizeof__doc__,
3635 : "D.__sizeof__() -> size of D in memory, in bytes");
3636 :
3637 : PyDoc_STRVAR(update__doc__,
3638 : "D.update([E, ]**F) -> None. Update D from dict/iterable E and F.\n\
3639 : If E is present and has a .keys() method, then does: for k in E: D[k] = E[k]\n\
3640 : If E is present and lacks a .keys() method, then does: for k, v in E: D[k] = v\n\
3641 : In either case, this is followed by: for k in F: D[k] = F[k]");
3642 :
3643 : PyDoc_STRVAR(clear__doc__,
3644 : "D.clear() -> None. Remove all items from D.");
3645 :
3646 : PyDoc_STRVAR(copy__doc__,
3647 : "D.copy() -> a shallow copy of D");
3648 :
3649 : /* Forward */
3650 : static PyObject *dictkeys_new(PyObject *, PyObject *);
3651 : static PyObject *dictitems_new(PyObject *, PyObject *);
3652 : static PyObject *dictvalues_new(PyObject *, PyObject *);
3653 :
3654 : PyDoc_STRVAR(keys__doc__,
3655 : "D.keys() -> a set-like object providing a view on D's keys");
3656 : PyDoc_STRVAR(items__doc__,
3657 : "D.items() -> a set-like object providing a view on D's items");
3658 : PyDoc_STRVAR(values__doc__,
3659 : "D.values() -> an object providing a view on D's values");
3660 :
3661 : static PyMethodDef mapp_methods[] = {
3662 : DICT___CONTAINS___METHODDEF
3663 : {"__getitem__", _PyCFunction_CAST(dict_subscript), METH_O | METH_COEXIST,
3664 : getitem__doc__},
3665 : {"__sizeof__", _PyCFunction_CAST(dict_sizeof), METH_NOARGS,
3666 : sizeof__doc__},
3667 : DICT_GET_METHODDEF
3668 : DICT_SETDEFAULT_METHODDEF
3669 : DICT_POP_METHODDEF
3670 : DICT_POPITEM_METHODDEF
3671 : {"keys", dictkeys_new, METH_NOARGS,
3672 : keys__doc__},
3673 : {"items", dictitems_new, METH_NOARGS,
3674 : items__doc__},
3675 : {"values", dictvalues_new, METH_NOARGS,
3676 : values__doc__},
3677 : {"update", _PyCFunction_CAST(dict_update), METH_VARARGS | METH_KEYWORDS,
3678 : update__doc__},
3679 : DICT_FROMKEYS_METHODDEF
3680 : {"clear", (PyCFunction)dict_clear, METH_NOARGS,
3681 : clear__doc__},
3682 : {"copy", (PyCFunction)dict_copy, METH_NOARGS,
3683 : copy__doc__},
3684 : DICT___REVERSED___METHODDEF
3685 : {"__class_getitem__", Py_GenericAlias, METH_O|METH_CLASS, PyDoc_STR("See PEP 585")},
3686 : {NULL, NULL} /* sentinel */
3687 : };
3688 :
3689 : /* Return 1 if `key` is in dict `op`, 0 if not, and -1 on error. */
3690 : int
3691 558907000 : PyDict_Contains(PyObject *op, PyObject *key)
3692 : {
3693 : Py_hash_t hash;
3694 : Py_ssize_t ix;
3695 558907000 : PyDictObject *mp = (PyDictObject *)op;
3696 : PyObject *value;
3697 :
3698 558907000 : if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
3699 6861680 : hash = PyObject_Hash(key);
3700 6861680 : if (hash == -1)
3701 4 : return -1;
3702 : }
3703 558907000 : ix = _Py_dict_lookup(mp, key, hash, &value);
3704 558907000 : if (ix == DKIX_ERROR)
3705 2 : return -1;
3706 558907000 : return (ix != DKIX_EMPTY && value != NULL);
3707 : }
3708 :
3709 : /* Internal version of PyDict_Contains used when the hash value is already known */
3710 : int
3711 38710 : _PyDict_Contains_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
3712 : {
3713 38710 : PyDictObject *mp = (PyDictObject *)op;
3714 : PyObject *value;
3715 : Py_ssize_t ix;
3716 :
3717 38710 : ix = _Py_dict_lookup(mp, key, hash, &value);
3718 38710 : if (ix == DKIX_ERROR)
3719 0 : return -1;
3720 38710 : return (ix != DKIX_EMPTY && value != NULL);
3721 : }
3722 :
3723 : int
3724 1268 : _PyDict_ContainsId(PyObject *op, _Py_Identifier *key)
3725 : {
3726 1268 : PyObject *kv = _PyUnicode_FromId(key); /* borrowed */
3727 1268 : if (kv == NULL) {
3728 0 : return -1;
3729 : }
3730 1268 : return PyDict_Contains(op, kv);
3731 : }
3732 :
3733 : /* Hack to implement "key in dict" */
3734 : static PySequenceMethods dict_as_sequence = {
3735 : 0, /* sq_length */
3736 : 0, /* sq_concat */
3737 : 0, /* sq_repeat */
3738 : 0, /* sq_item */
3739 : 0, /* sq_slice */
3740 : 0, /* sq_ass_item */
3741 : 0, /* sq_ass_slice */
3742 : PyDict_Contains, /* sq_contains */
3743 : 0, /* sq_inplace_concat */
3744 : 0, /* sq_inplace_repeat */
3745 : };
3746 :
3747 : static PyNumberMethods dict_as_number = {
3748 : .nb_or = dict_or,
3749 : .nb_inplace_or = dict_ior,
3750 : };
3751 :
3752 : static PyObject *
3753 365139 : dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
3754 : {
3755 365139 : assert(type != NULL);
3756 365139 : assert(type->tp_alloc != NULL);
3757 : // dict subclasses must implement the GC protocol
3758 365139 : assert(_PyType_IS_GC(type));
3759 :
3760 365139 : PyObject *self = type->tp_alloc(type, 0);
3761 365139 : if (self == NULL) {
3762 0 : return NULL;
3763 : }
3764 365139 : PyDictObject *d = (PyDictObject *)self;
3765 :
3766 365139 : d->ma_used = 0;
3767 365139 : d->ma_version_tag = DICT_NEXT_VERSION();
3768 365139 : dictkeys_incref(Py_EMPTY_KEYS);
3769 365139 : d->ma_keys = Py_EMPTY_KEYS;
3770 365139 : d->ma_values = NULL;
3771 365139 : ASSERT_CONSISTENT(d);
3772 :
3773 365139 : if (type != &PyDict_Type) {
3774 : // Don't track if a subclass tp_alloc is PyType_GenericAlloc()
3775 102800 : if (!_PyObject_GC_IS_TRACKED(d)) {
3776 12663 : _PyObject_GC_TRACK(d);
3777 : }
3778 : }
3779 : else {
3780 : // _PyType_AllocNoTrack() does not track the created object
3781 262339 : assert(!_PyObject_GC_IS_TRACKED(d));
3782 : }
3783 365139 : return self;
3784 : }
3785 :
3786 : static int
3787 88330 : dict_init(PyObject *self, PyObject *args, PyObject *kwds)
3788 : {
3789 88330 : return dict_update_common(self, args, kwds, "dict");
3790 : }
3791 :
3792 : static PyObject *
3793 262342 : dict_vectorcall(PyObject *type, PyObject * const*args,
3794 : size_t nargsf, PyObject *kwnames)
3795 : {
3796 262342 : Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);
3797 262342 : if (!_PyArg_CheckPositional("dict", nargs, 0, 1)) {
3798 3 : return NULL;
3799 : }
3800 :
3801 262339 : PyObject *self = dict_new(_PyType_CAST(type), NULL, NULL);
3802 262339 : if (self == NULL) {
3803 0 : return NULL;
3804 : }
3805 262339 : if (nargs == 1) {
3806 125804 : if (dict_update_arg(self, args[0]) < 0) {
3807 24 : Py_DECREF(self);
3808 24 : return NULL;
3809 : }
3810 125780 : args++;
3811 : }
3812 262315 : if (kwnames != NULL) {
3813 147645 : for (Py_ssize_t i = 0; i < PyTuple_GET_SIZE(kwnames); i++) {
3814 100493 : if (PyDict_SetItem(self, PyTuple_GET_ITEM(kwnames, i), args[i]) < 0) {
3815 0 : Py_DECREF(self);
3816 0 : return NULL;
3817 : }
3818 : }
3819 : }
3820 262315 : return self;
3821 : }
3822 :
3823 : static PyObject *
3824 490586 : dict_iter(PyDictObject *dict)
3825 : {
3826 490586 : return dictiter_new(dict, &PyDictIterKey_Type);
3827 : }
3828 :
3829 : PyDoc_STRVAR(dictionary_doc,
3830 : "dict() -> new empty dictionary\n"
3831 : "dict(mapping) -> new dictionary initialized from a mapping object's\n"
3832 : " (key, value) pairs\n"
3833 : "dict(iterable) -> new dictionary initialized as if via:\n"
3834 : " d = {}\n"
3835 : " for k, v in iterable:\n"
3836 : " d[k] = v\n"
3837 : "dict(**kwargs) -> new dictionary initialized with the name=value pairs\n"
3838 : " in the keyword argument list. For example: dict(one=1, two=2)");
3839 :
3840 : PyTypeObject PyDict_Type = {
3841 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
3842 : "dict",
3843 : sizeof(PyDictObject),
3844 : 0,
3845 : (destructor)dict_dealloc, /* tp_dealloc */
3846 : 0, /* tp_vectorcall_offset */
3847 : 0, /* tp_getattr */
3848 : 0, /* tp_setattr */
3849 : 0, /* tp_as_async */
3850 : (reprfunc)dict_repr, /* tp_repr */
3851 : &dict_as_number, /* tp_as_number */
3852 : &dict_as_sequence, /* tp_as_sequence */
3853 : &dict_as_mapping, /* tp_as_mapping */
3854 : PyObject_HashNotImplemented, /* tp_hash */
3855 : 0, /* tp_call */
3856 : 0, /* tp_str */
3857 : PyObject_GenericGetAttr, /* tp_getattro */
3858 : 0, /* tp_setattro */
3859 : 0, /* tp_as_buffer */
3860 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
3861 : Py_TPFLAGS_BASETYPE | Py_TPFLAGS_DICT_SUBCLASS |
3862 : _Py_TPFLAGS_MATCH_SELF | Py_TPFLAGS_MAPPING, /* tp_flags */
3863 : dictionary_doc, /* tp_doc */
3864 : dict_traverse, /* tp_traverse */
3865 : dict_tp_clear, /* tp_clear */
3866 : dict_richcompare, /* tp_richcompare */
3867 : 0, /* tp_weaklistoffset */
3868 : (getiterfunc)dict_iter, /* tp_iter */
3869 : 0, /* tp_iternext */
3870 : mapp_methods, /* tp_methods */
3871 : 0, /* tp_members */
3872 : 0, /* tp_getset */
3873 : 0, /* tp_base */
3874 : 0, /* tp_dict */
3875 : 0, /* tp_descr_get */
3876 : 0, /* tp_descr_set */
3877 : 0, /* tp_dictoffset */
3878 : dict_init, /* tp_init */
3879 : _PyType_AllocNoTrack, /* tp_alloc */
3880 : dict_new, /* tp_new */
3881 : PyObject_GC_Del, /* tp_free */
3882 : .tp_vectorcall = dict_vectorcall,
3883 : };
3884 :
3885 : /* For backward compatibility with old dictionary interface */
3886 :
3887 : PyObject *
3888 0 : PyDict_GetItemString(PyObject *v, const char *key)
3889 : {
3890 : PyObject *kv, *rv;
3891 0 : kv = PyUnicode_FromString(key);
3892 0 : if (kv == NULL) {
3893 0 : PyErr_Clear();
3894 0 : return NULL;
3895 : }
3896 0 : rv = PyDict_GetItem(v, kv);
3897 0 : Py_DECREF(kv);
3898 0 : return rv;
3899 : }
3900 :
3901 : int
3902 10568 : _PyDict_SetItemId(PyObject *v, _Py_Identifier *key, PyObject *item)
3903 : {
3904 : PyObject *kv;
3905 10568 : kv = _PyUnicode_FromId(key); /* borrowed */
3906 10568 : if (kv == NULL)
3907 0 : return -1;
3908 10568 : return PyDict_SetItem(v, kv, item);
3909 : }
3910 :
3911 : int
3912 3897750 : PyDict_SetItemString(PyObject *v, const char *key, PyObject *item)
3913 : {
3914 : PyObject *kv;
3915 : int err;
3916 3897750 : kv = PyUnicode_FromString(key);
3917 3897750 : if (kv == NULL)
3918 49 : return -1;
3919 3897700 : PyUnicode_InternInPlace(&kv); /* XXX Should we really? */
3920 3897700 : err = PyDict_SetItem(v, kv, item);
3921 3897700 : Py_DECREF(kv);
3922 3897700 : return err;
3923 : }
3924 :
3925 : int
3926 0 : _PyDict_DelItemId(PyObject *v, _Py_Identifier *key)
3927 : {
3928 0 : PyObject *kv = _PyUnicode_FromId(key); /* borrowed */
3929 0 : if (kv == NULL)
3930 0 : return -1;
3931 0 : return PyDict_DelItem(v, kv);
3932 : }
3933 :
3934 : int
3935 612 : PyDict_DelItemString(PyObject *v, const char *key)
3936 : {
3937 : PyObject *kv;
3938 : int err;
3939 612 : kv = PyUnicode_FromString(key);
3940 612 : if (kv == NULL)
3941 0 : return -1;
3942 612 : err = PyDict_DelItem(v, kv);
3943 612 : Py_DECREF(kv);
3944 612 : return err;
3945 : }
3946 :
3947 : /* Dictionary iterator types */
3948 :
3949 : typedef struct {
3950 : PyObject_HEAD
3951 : PyDictObject *di_dict; /* Set to NULL when iterator is exhausted */
3952 : Py_ssize_t di_used;
3953 : Py_ssize_t di_pos;
3954 : PyObject* di_result; /* reusable result tuple for iteritems */
3955 : Py_ssize_t len;
3956 : } dictiterobject;
3957 :
3958 : static PyObject *
3959 1590340 : dictiter_new(PyDictObject *dict, PyTypeObject *itertype)
3960 : {
3961 : dictiterobject *di;
3962 1590340 : di = PyObject_GC_New(dictiterobject, itertype);
3963 1590340 : if (di == NULL) {
3964 0 : return NULL;
3965 : }
3966 1590340 : Py_INCREF(dict);
3967 1590340 : di->di_dict = dict;
3968 1590340 : di->di_used = dict->ma_used;
3969 1590340 : di->len = dict->ma_used;
3970 1590340 : if (itertype == &PyDictRevIterKey_Type ||
3971 1590310 : itertype == &PyDictRevIterItem_Type ||
3972 : itertype == &PyDictRevIterValue_Type) {
3973 51 : if (dict->ma_values) {
3974 3 : di->di_pos = dict->ma_used - 1;
3975 : }
3976 : else {
3977 48 : di->di_pos = dict->ma_keys->dk_nentries - 1;
3978 : }
3979 : }
3980 : else {
3981 1590290 : di->di_pos = 0;
3982 : }
3983 1590340 : if (itertype == &PyDictIterItem_Type ||
3984 : itertype == &PyDictRevIterItem_Type) {
3985 615184 : di->di_result = PyTuple_Pack(2, Py_None, Py_None);
3986 615184 : if (di->di_result == NULL) {
3987 0 : Py_DECREF(di);
3988 0 : return NULL;
3989 : }
3990 : }
3991 : else {
3992 975161 : di->di_result = NULL;
3993 : }
3994 1590340 : _PyObject_GC_TRACK(di);
3995 1590340 : return (PyObject *)di;
3996 : }
3997 :
3998 : static void
3999 1590340 : dictiter_dealloc(dictiterobject *di)
4000 : {
4001 : /* bpo-31095: UnTrack is needed before calling any callbacks */
4002 1590340 : _PyObject_GC_UNTRACK(di);
4003 1590340 : Py_XDECREF(di->di_dict);
4004 1590340 : Py_XDECREF(di->di_result);
4005 1590340 : PyObject_GC_Del(di);
4006 1590340 : }
4007 :
4008 : static int
4009 3886 : dictiter_traverse(dictiterobject *di, visitproc visit, void *arg)
4010 : {
4011 3886 : Py_VISIT(di->di_dict);
4012 3886 : Py_VISIT(di->di_result);
4013 3886 : return 0;
4014 : }
4015 :
4016 : static PyObject *
4017 274677 : dictiter_len(dictiterobject *di, PyObject *Py_UNUSED(ignored))
4018 : {
4019 274677 : Py_ssize_t len = 0;
4020 274677 : if (di->di_dict != NULL && di->di_used == di->di_dict->ma_used)
4021 274667 : len = di->len;
4022 274677 : return PyLong_FromSize_t(len);
4023 : }
4024 :
4025 : PyDoc_STRVAR(length_hint_doc,
4026 : "Private method returning an estimate of len(list(it)).");
4027 :
4028 : static PyObject *
4029 : dictiter_reduce(dictiterobject *di, PyObject *Py_UNUSED(ignored));
4030 :
4031 : PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
4032 :
4033 : static PyMethodDef dictiter_methods[] = {
4034 : {"__length_hint__", _PyCFunction_CAST(dictiter_len), METH_NOARGS,
4035 : length_hint_doc},
4036 : {"__reduce__", _PyCFunction_CAST(dictiter_reduce), METH_NOARGS,
4037 : reduce_doc},
4038 : {NULL, NULL} /* sentinel */
4039 : };
4040 :
4041 : static PyObject*
4042 6534360 : dictiter_iternextkey(dictiterobject *di)
4043 : {
4044 : PyObject *key;
4045 : Py_ssize_t i;
4046 : PyDictKeysObject *k;
4047 6534360 : PyDictObject *d = di->di_dict;
4048 :
4049 6534360 : if (d == NULL)
4050 7 : return NULL;
4051 6534350 : assert (PyDict_Check(d));
4052 :
4053 6534350 : if (di->di_used != d->ma_used) {
4054 236 : PyErr_SetString(PyExc_RuntimeError,
4055 : "dictionary changed size during iteration");
4056 236 : di->di_used = -1; /* Make this state sticky */
4057 236 : return NULL;
4058 : }
4059 :
4060 6534120 : i = di->di_pos;
4061 6534120 : k = d->ma_keys;
4062 6534120 : assert(i >= 0);
4063 6534120 : if (d->ma_values) {
4064 13644 : if (i >= d->ma_used)
4065 1687 : goto fail;
4066 11957 : int index = get_index_from_order(d, i);
4067 11957 : key = DK_UNICODE_ENTRIES(k)[index].me_key;
4068 11957 : assert(d->ma_values->values[index] != NULL);
4069 : }
4070 : else {
4071 6520470 : Py_ssize_t n = k->dk_nentries;
4072 6520470 : if (DK_IS_UNICODE(k)) {
4073 3326440 : PyDictUnicodeEntry *entry_ptr = &DK_UNICODE_ENTRIES(k)[i];
4074 14735200 : while (i < n && entry_ptr->me_value == NULL) {
4075 11408800 : entry_ptr++;
4076 11408800 : i++;
4077 : }
4078 3326440 : if (i >= n)
4079 285584 : goto fail;
4080 3040860 : key = entry_ptr->me_key;
4081 : }
4082 : else {
4083 3194030 : PyDictKeyEntry *entry_ptr = &DK_ENTRIES(k)[i];
4084 5463870 : while (i < n && entry_ptr->me_value == NULL) {
4085 2269840 : entry_ptr++;
4086 2269840 : i++;
4087 : }
4088 3194030 : if (i >= n)
4089 268784 : goto fail;
4090 2925250 : key = entry_ptr->me_key;
4091 : }
4092 : }
4093 : // We found an element (key), but did not expect it
4094 5978060 : if (di->len == 0) {
4095 1 : PyErr_SetString(PyExc_RuntimeError,
4096 : "dictionary keys changed during iteration");
4097 1 : goto fail;
4098 : }
4099 5978060 : di->di_pos = i+1;
4100 5978060 : di->len--;
4101 5978060 : Py_INCREF(key);
4102 5978060 : return key;
4103 :
4104 556056 : fail:
4105 556056 : di->di_dict = NULL;
4106 556056 : Py_DECREF(d);
4107 556056 : return NULL;
4108 : }
4109 :
4110 : PyTypeObject PyDictIterKey_Type = {
4111 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
4112 : "dict_keyiterator", /* tp_name */
4113 : sizeof(dictiterobject), /* tp_basicsize */
4114 : 0, /* tp_itemsize */
4115 : /* methods */
4116 : (destructor)dictiter_dealloc, /* tp_dealloc */
4117 : 0, /* tp_vectorcall_offset */
4118 : 0, /* tp_getattr */
4119 : 0, /* tp_setattr */
4120 : 0, /* tp_as_async */
4121 : 0, /* tp_repr */
4122 : 0, /* tp_as_number */
4123 : 0, /* tp_as_sequence */
4124 : 0, /* tp_as_mapping */
4125 : 0, /* tp_hash */
4126 : 0, /* tp_call */
4127 : 0, /* tp_str */
4128 : PyObject_GenericGetAttr, /* tp_getattro */
4129 : 0, /* tp_setattro */
4130 : 0, /* tp_as_buffer */
4131 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
4132 : 0, /* tp_doc */
4133 : (traverseproc)dictiter_traverse, /* tp_traverse */
4134 : 0, /* tp_clear */
4135 : 0, /* tp_richcompare */
4136 : 0, /* tp_weaklistoffset */
4137 : PyObject_SelfIter, /* tp_iter */
4138 : (iternextfunc)dictiter_iternextkey, /* tp_iternext */
4139 : dictiter_methods, /* tp_methods */
4140 : 0,
4141 : };
4142 :
4143 : static PyObject *
4144 1414760 : dictiter_iternextvalue(dictiterobject *di)
4145 : {
4146 : PyObject *value;
4147 : Py_ssize_t i;
4148 1414760 : PyDictObject *d = di->di_dict;
4149 :
4150 1414760 : if (d == NULL)
4151 1 : return NULL;
4152 1414760 : assert (PyDict_Check(d));
4153 :
4154 1414760 : if (di->di_used != d->ma_used) {
4155 1 : PyErr_SetString(PyExc_RuntimeError,
4156 : "dictionary changed size during iteration");
4157 1 : di->di_used = -1; /* Make this state sticky */
4158 1 : return NULL;
4159 : }
4160 :
4161 1414760 : i = di->di_pos;
4162 1414760 : assert(i >= 0);
4163 1414760 : if (d->ma_values) {
4164 0 : if (i >= d->ma_used)
4165 0 : goto fail;
4166 0 : int index = get_index_from_order(d, i);
4167 0 : value = d->ma_values->values[index];
4168 0 : assert(value != NULL);
4169 : }
4170 : else {
4171 1414760 : Py_ssize_t n = d->ma_keys->dk_nentries;
4172 1414760 : if (DK_IS_UNICODE(d->ma_keys)) {
4173 1279550 : PyDictUnicodeEntry *entry_ptr = &DK_UNICODE_ENTRIES(d->ma_keys)[i];
4174 1447020 : while (i < n && entry_ptr->me_value == NULL) {
4175 167467 : entry_ptr++;
4176 167467 : i++;
4177 : }
4178 1279550 : if (i >= n)
4179 350584 : goto fail;
4180 928970 : value = entry_ptr->me_value;
4181 : }
4182 : else {
4183 135207 : PyDictKeyEntry *entry_ptr = &DK_ENTRIES(d->ma_keys)[i];
4184 367598 : while (i < n && entry_ptr->me_value == NULL) {
4185 232391 : entry_ptr++;
4186 232391 : i++;
4187 : }
4188 135207 : if (i >= n)
4189 10414 : goto fail;
4190 124793 : value = entry_ptr->me_value;
4191 : }
4192 : }
4193 : // We found an element, but did not expect it
4194 1053760 : if (di->len == 0) {
4195 1 : PyErr_SetString(PyExc_RuntimeError,
4196 : "dictionary keys changed during iteration");
4197 1 : goto fail;
4198 : }
4199 1053760 : di->di_pos = i+1;
4200 1053760 : di->len--;
4201 1053760 : Py_INCREF(value);
4202 1053760 : return value;
4203 :
4204 360999 : fail:
4205 360999 : di->di_dict = NULL;
4206 360999 : Py_DECREF(d);
4207 360999 : return NULL;
4208 : }
4209 :
4210 : PyTypeObject PyDictIterValue_Type = {
4211 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
4212 : "dict_valueiterator", /* tp_name */
4213 : sizeof(dictiterobject), /* tp_basicsize */
4214 : 0, /* tp_itemsize */
4215 : /* methods */
4216 : (destructor)dictiter_dealloc, /* tp_dealloc */
4217 : 0, /* tp_vectorcall_offset */
4218 : 0, /* tp_getattr */
4219 : 0, /* tp_setattr */
4220 : 0, /* tp_as_async */
4221 : 0, /* tp_repr */
4222 : 0, /* tp_as_number */
4223 : 0, /* tp_as_sequence */
4224 : 0, /* tp_as_mapping */
4225 : 0, /* tp_hash */
4226 : 0, /* tp_call */
4227 : 0, /* tp_str */
4228 : PyObject_GenericGetAttr, /* tp_getattro */
4229 : 0, /* tp_setattro */
4230 : 0, /* tp_as_buffer */
4231 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
4232 : 0, /* tp_doc */
4233 : (traverseproc)dictiter_traverse, /* tp_traverse */
4234 : 0, /* tp_clear */
4235 : 0, /* tp_richcompare */
4236 : 0, /* tp_weaklistoffset */
4237 : PyObject_SelfIter, /* tp_iter */
4238 : (iternextfunc)dictiter_iternextvalue, /* tp_iternext */
4239 : dictiter_methods, /* tp_methods */
4240 : 0,
4241 : };
4242 :
4243 : static PyObject *
4244 7322090 : dictiter_iternextitem(dictiterobject *di)
4245 : {
4246 : PyObject *key, *value, *result;
4247 : Py_ssize_t i;
4248 7322090 : PyDictObject *d = di->di_dict;
4249 :
4250 7322090 : if (d == NULL)
4251 1 : return NULL;
4252 7322090 : assert (PyDict_Check(d));
4253 :
4254 7322090 : if (di->di_used != d->ma_used) {
4255 72 : PyErr_SetString(PyExc_RuntimeError,
4256 : "dictionary changed size during iteration");
4257 72 : di->di_used = -1; /* Make this state sticky */
4258 72 : return NULL;
4259 : }
4260 :
4261 7322020 : i = di->di_pos;
4262 7322020 : assert(i >= 0);
4263 7322020 : if (d->ma_values) {
4264 101978 : if (i >= d->ma_used)
4265 47344 : goto fail;
4266 54634 : int index = get_index_from_order(d, i);
4267 54634 : key = DK_UNICODE_ENTRIES(d->ma_keys)[index].me_key;
4268 54634 : value = d->ma_values->values[index];
4269 54634 : assert(value != NULL);
4270 : }
4271 : else {
4272 7220040 : Py_ssize_t n = d->ma_keys->dk_nentries;
4273 7220040 : if (DK_IS_UNICODE(d->ma_keys)) {
4274 6480470 : PyDictUnicodeEntry *entry_ptr = &DK_UNICODE_ENTRIES(d->ma_keys)[i];
4275 6684800 : while (i < n && entry_ptr->me_value == NULL) {
4276 204339 : entry_ptr++;
4277 204339 : i++;
4278 : }
4279 6480470 : if (i >= n)
4280 523017 : goto fail;
4281 5957450 : key = entry_ptr->me_key;
4282 5957450 : value = entry_ptr->me_value;
4283 : }
4284 : else {
4285 739572 : PyDictKeyEntry *entry_ptr = &DK_ENTRIES(d->ma_keys)[i];
4286 749962 : while (i < n && entry_ptr->me_value == NULL) {
4287 10390 : entry_ptr++;
4288 10390 : i++;
4289 : }
4290 739572 : if (i >= n)
4291 30358 : goto fail;
4292 709214 : key = entry_ptr->me_key;
4293 709214 : value = entry_ptr->me_value;
4294 : }
4295 : }
4296 : // We found an element, but did not expect it
4297 6721300 : if (di->len == 0) {
4298 1 : PyErr_SetString(PyExc_RuntimeError,
4299 : "dictionary keys changed during iteration");
4300 1 : goto fail;
4301 : }
4302 6721300 : di->di_pos = i+1;
4303 6721300 : di->len--;
4304 6721300 : Py_INCREF(key);
4305 6721300 : Py_INCREF(value);
4306 6721300 : result = di->di_result;
4307 6721300 : if (Py_REFCNT(result) == 1) {
4308 4946340 : PyObject *oldkey = PyTuple_GET_ITEM(result, 0);
4309 4946340 : PyObject *oldvalue = PyTuple_GET_ITEM(result, 1);
4310 4946340 : PyTuple_SET_ITEM(result, 0, key); /* steals reference */
4311 4946340 : PyTuple_SET_ITEM(result, 1, value); /* steals reference */
4312 4946340 : Py_INCREF(result);
4313 4946340 : Py_DECREF(oldkey);
4314 4946340 : Py_DECREF(oldvalue);
4315 : // bpo-42536: The GC may have untracked this result tuple. Since we're
4316 : // recycling it, make sure it's tracked again:
4317 4946340 : if (!_PyObject_GC_IS_TRACKED(result)) {
4318 571 : _PyObject_GC_TRACK(result);
4319 : }
4320 : }
4321 : else {
4322 1774960 : result = PyTuple_New(2);
4323 1774960 : if (result == NULL)
4324 0 : return NULL;
4325 1774960 : PyTuple_SET_ITEM(result, 0, key); /* steals reference */
4326 1774960 : PyTuple_SET_ITEM(result, 1, value); /* steals reference */
4327 : }
4328 6721300 : return result;
4329 :
4330 600720 : fail:
4331 600720 : di->di_dict = NULL;
4332 600720 : Py_DECREF(d);
4333 600720 : return NULL;
4334 : }
4335 :
4336 : PyTypeObject PyDictIterItem_Type = {
4337 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
4338 : "dict_itemiterator", /* tp_name */
4339 : sizeof(dictiterobject), /* tp_basicsize */
4340 : 0, /* tp_itemsize */
4341 : /* methods */
4342 : (destructor)dictiter_dealloc, /* tp_dealloc */
4343 : 0, /* tp_vectorcall_offset */
4344 : 0, /* tp_getattr */
4345 : 0, /* tp_setattr */
4346 : 0, /* tp_as_async */
4347 : 0, /* tp_repr */
4348 : 0, /* tp_as_number */
4349 : 0, /* tp_as_sequence */
4350 : 0, /* tp_as_mapping */
4351 : 0, /* tp_hash */
4352 : 0, /* tp_call */
4353 : 0, /* tp_str */
4354 : PyObject_GenericGetAttr, /* tp_getattro */
4355 : 0, /* tp_setattro */
4356 : 0, /* tp_as_buffer */
4357 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
4358 : 0, /* tp_doc */
4359 : (traverseproc)dictiter_traverse, /* tp_traverse */
4360 : 0, /* tp_clear */
4361 : 0, /* tp_richcompare */
4362 : 0, /* tp_weaklistoffset */
4363 : PyObject_SelfIter, /* tp_iter */
4364 : (iternextfunc)dictiter_iternextitem, /* tp_iternext */
4365 : dictiter_methods, /* tp_methods */
4366 : 0,
4367 : };
4368 :
4369 :
4370 : /* dictreviter */
4371 :
4372 : static PyObject *
4373 172 : dictreviter_iternext(dictiterobject *di)
4374 : {
4375 172 : PyDictObject *d = di->di_dict;
4376 :
4377 172 : if (d == NULL) {
4378 2 : return NULL;
4379 : }
4380 170 : assert (PyDict_Check(d));
4381 :
4382 170 : if (di->di_used != d->ma_used) {
4383 0 : PyErr_SetString(PyExc_RuntimeError,
4384 : "dictionary changed size during iteration");
4385 0 : di->di_used = -1; /* Make this state sticky */
4386 0 : return NULL;
4387 : }
4388 :
4389 170 : Py_ssize_t i = di->di_pos;
4390 170 : PyDictKeysObject *k = d->ma_keys;
4391 : PyObject *key, *value, *result;
4392 :
4393 170 : if (i < 0) {
4394 50 : goto fail;
4395 : }
4396 120 : if (d->ma_values) {
4397 4 : int index = get_index_from_order(d, i);
4398 4 : key = DK_UNICODE_ENTRIES(k)[index].me_key;
4399 4 : value = d->ma_values->values[index];
4400 4 : assert (value != NULL);
4401 : }
4402 : else {
4403 116 : if (DK_IS_UNICODE(k)) {
4404 13 : PyDictUnicodeEntry *entry_ptr = &DK_UNICODE_ENTRIES(k)[i];
4405 15 : while (entry_ptr->me_value == NULL) {
4406 2 : if (--i < 0) {
4407 0 : goto fail;
4408 : }
4409 2 : entry_ptr--;
4410 : }
4411 13 : key = entry_ptr->me_key;
4412 13 : value = entry_ptr->me_value;
4413 : }
4414 : else {
4415 103 : PyDictKeyEntry *entry_ptr = &DK_ENTRIES(k)[i];
4416 109 : while (entry_ptr->me_value == NULL) {
4417 6 : if (--i < 0) {
4418 0 : goto fail;
4419 : }
4420 6 : entry_ptr--;
4421 : }
4422 103 : key = entry_ptr->me_key;
4423 103 : value = entry_ptr->me_value;
4424 : }
4425 : }
4426 120 : di->di_pos = i-1;
4427 120 : di->len--;
4428 :
4429 120 : if (Py_IS_TYPE(di, &PyDictRevIterKey_Type)) {
4430 65 : Py_INCREF(key);
4431 65 : return key;
4432 : }
4433 55 : else if (Py_IS_TYPE(di, &PyDictRevIterValue_Type)) {
4434 36 : Py_INCREF(value);
4435 36 : return value;
4436 : }
4437 19 : else if (Py_IS_TYPE(di, &PyDictRevIterItem_Type)) {
4438 19 : Py_INCREF(key);
4439 19 : Py_INCREF(value);
4440 19 : result = di->di_result;
4441 19 : if (Py_REFCNT(result) == 1) {
4442 7 : PyObject *oldkey = PyTuple_GET_ITEM(result, 0);
4443 7 : PyObject *oldvalue = PyTuple_GET_ITEM(result, 1);
4444 7 : PyTuple_SET_ITEM(result, 0, key); /* steals reference */
4445 7 : PyTuple_SET_ITEM(result, 1, value); /* steals reference */
4446 7 : Py_INCREF(result);
4447 7 : Py_DECREF(oldkey);
4448 7 : Py_DECREF(oldvalue);
4449 : // bpo-42536: The GC may have untracked this result tuple. Since
4450 : // we're recycling it, make sure it's tracked again:
4451 7 : if (!_PyObject_GC_IS_TRACKED(result)) {
4452 1 : _PyObject_GC_TRACK(result);
4453 : }
4454 : }
4455 : else {
4456 12 : result = PyTuple_New(2);
4457 12 : if (result == NULL) {
4458 0 : return NULL;
4459 : }
4460 12 : PyTuple_SET_ITEM(result, 0, key); /* steals reference */
4461 12 : PyTuple_SET_ITEM(result, 1, value); /* steals reference */
4462 : }
4463 19 : return result;
4464 : }
4465 : else {
4466 0 : Py_UNREACHABLE();
4467 : }
4468 :
4469 50 : fail:
4470 50 : di->di_dict = NULL;
4471 50 : Py_DECREF(d);
4472 50 : return NULL;
4473 : }
4474 :
4475 : PyTypeObject PyDictRevIterKey_Type = {
4476 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
4477 : "dict_reversekeyiterator",
4478 : sizeof(dictiterobject),
4479 : .tp_dealloc = (destructor)dictiter_dealloc,
4480 : .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,
4481 : .tp_traverse = (traverseproc)dictiter_traverse,
4482 : .tp_iter = PyObject_SelfIter,
4483 : .tp_iternext = (iternextfunc)dictreviter_iternext,
4484 : .tp_methods = dictiter_methods
4485 : };
4486 :
4487 :
4488 : /*[clinic input]
4489 : dict.__reversed__
4490 :
4491 : Return a reverse iterator over the dict keys.
4492 : [clinic start generated code]*/
4493 :
4494 : static PyObject *
4495 26 : dict___reversed___impl(PyDictObject *self)
4496 : /*[clinic end generated code: output=e674483336d1ed51 input=23210ef3477d8c4d]*/
4497 : {
4498 26 : assert (PyDict_Check(self));
4499 26 : return dictiter_new(self, &PyDictRevIterKey_Type);
4500 : }
4501 :
4502 : static PyObject *
4503 42 : dictiter_reduce(dictiterobject *di, PyObject *Py_UNUSED(ignored))
4504 : {
4505 : /* copy the iterator state */
4506 42 : dictiterobject tmp = *di;
4507 42 : Py_XINCREF(tmp.di_dict);
4508 :
4509 42 : PyObject *list = PySequence_List((PyObject*)&tmp);
4510 42 : Py_XDECREF(tmp.di_dict);
4511 42 : if (list == NULL) {
4512 0 : return NULL;
4513 : }
4514 42 : return Py_BuildValue("N(N)", _PyEval_GetBuiltin(&_Py_ID(iter)), list);
4515 : }
4516 :
4517 : PyTypeObject PyDictRevIterItem_Type = {
4518 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
4519 : "dict_reverseitemiterator",
4520 : sizeof(dictiterobject),
4521 : .tp_dealloc = (destructor)dictiter_dealloc,
4522 : .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,
4523 : .tp_traverse = (traverseproc)dictiter_traverse,
4524 : .tp_iter = PyObject_SelfIter,
4525 : .tp_iternext = (iternextfunc)dictreviter_iternext,
4526 : .tp_methods = dictiter_methods
4527 : };
4528 :
4529 : PyTypeObject PyDictRevIterValue_Type = {
4530 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
4531 : "dict_reversevalueiterator",
4532 : sizeof(dictiterobject),
4533 : .tp_dealloc = (destructor)dictiter_dealloc,
4534 : .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,
4535 : .tp_traverse = (traverseproc)dictiter_traverse,
4536 : .tp_iter = PyObject_SelfIter,
4537 : .tp_iternext = (iternextfunc)dictreviter_iternext,
4538 : .tp_methods = dictiter_methods
4539 : };
4540 :
4541 : /***********************************************/
4542 : /* View objects for keys(), items(), values(). */
4543 : /***********************************************/
4544 :
4545 : /* The instance lay-out is the same for all three; but the type differs. */
4546 :
4547 : static void
4548 1133520 : dictview_dealloc(_PyDictViewObject *dv)
4549 : {
4550 : /* bpo-31095: UnTrack is needed before calling any callbacks */
4551 1133520 : _PyObject_GC_UNTRACK(dv);
4552 1133520 : Py_XDECREF(dv->dv_dict);
4553 1133520 : PyObject_GC_Del(dv);
4554 1133520 : }
4555 :
4556 : static int
4557 5802 : dictview_traverse(_PyDictViewObject *dv, visitproc visit, void *arg)
4558 : {
4559 5802 : Py_VISIT(dv->dv_dict);
4560 5802 : return 0;
4561 : }
4562 :
4563 : static Py_ssize_t
4564 39500 : dictview_len(_PyDictViewObject *dv)
4565 : {
4566 39500 : Py_ssize_t len = 0;
4567 39500 : if (dv->dv_dict != NULL)
4568 39500 : len = dv->dv_dict->ma_used;
4569 39500 : return len;
4570 : }
4571 :
4572 : PyObject *
4573 1133520 : _PyDictView_New(PyObject *dict, PyTypeObject *type)
4574 : {
4575 : _PyDictViewObject *dv;
4576 1133520 : if (dict == NULL) {
4577 0 : PyErr_BadInternalCall();
4578 0 : return NULL;
4579 : }
4580 1133520 : if (!PyDict_Check(dict)) {
4581 : /* XXX Get rid of this restriction later */
4582 0 : PyErr_Format(PyExc_TypeError,
4583 : "%s() requires a dict argument, not '%s'",
4584 0 : type->tp_name, Py_TYPE(dict)->tp_name);
4585 0 : return NULL;
4586 : }
4587 1133520 : dv = PyObject_GC_New(_PyDictViewObject, type);
4588 1133520 : if (dv == NULL)
4589 0 : return NULL;
4590 1133520 : Py_INCREF(dict);
4591 1133520 : dv->dv_dict = (PyDictObject *)dict;
4592 1133520 : _PyObject_GC_TRACK(dv);
4593 1133520 : return (PyObject *)dv;
4594 : }
4595 :
4596 : static PyObject *
4597 6 : dictview_mapping(PyObject *view, void *Py_UNUSED(ignored)) {
4598 6 : assert(view != NULL);
4599 6 : assert(PyDictKeys_Check(view)
4600 : || PyDictValues_Check(view)
4601 : || PyDictItems_Check(view));
4602 6 : PyObject *mapping = (PyObject *)((_PyDictViewObject *)view)->dv_dict;
4603 6 : return PyDictProxy_New(mapping);
4604 : }
4605 :
4606 : static PyGetSetDef dictview_getset[] = {
4607 : {"mapping", dictview_mapping, (setter)NULL,
4608 : "dictionary that this view refers to", NULL},
4609 : {0}
4610 : };
4611 :
4612 : /* TODO(guido): The views objects are not complete:
4613 :
4614 : * support more set operations
4615 : * support arbitrary mappings?
4616 : - either these should be static or exported in dictobject.h
4617 : - if public then they should probably be in builtins
4618 : */
4619 :
4620 : /* Return 1 if self is a subset of other, iterating over self;
4621 : 0 if not; -1 if an error occurred. */
4622 : static int
4623 93 : all_contained_in(PyObject *self, PyObject *other)
4624 : {
4625 93 : PyObject *iter = PyObject_GetIter(self);
4626 93 : int ok = 1;
4627 :
4628 93 : if (iter == NULL)
4629 0 : return -1;
4630 196 : for (;;) {
4631 289 : PyObject *next = PyIter_Next(iter);
4632 289 : if (next == NULL) {
4633 71 : if (PyErr_Occurred())
4634 0 : ok = -1;
4635 71 : break;
4636 : }
4637 218 : ok = PySequence_Contains(other, next);
4638 218 : Py_DECREF(next);
4639 218 : if (ok <= 0)
4640 22 : break;
4641 : }
4642 93 : Py_DECREF(iter);
4643 93 : return ok;
4644 : }
4645 :
4646 : static PyObject *
4647 118 : dictview_richcompare(PyObject *self, PyObject *other, int op)
4648 : {
4649 : Py_ssize_t len_self, len_other;
4650 : int ok;
4651 : PyObject *result;
4652 :
4653 118 : assert(self != NULL);
4654 118 : assert(PyDictViewSet_Check(self));
4655 118 : assert(other != NULL);
4656 :
4657 118 : if (!PyAnySet_Check(other) && !PyDictViewSet_Check(other))
4658 2 : Py_RETURN_NOTIMPLEMENTED;
4659 :
4660 116 : len_self = PyObject_Size(self);
4661 116 : if (len_self < 0)
4662 0 : return NULL;
4663 116 : len_other = PyObject_Size(other);
4664 116 : if (len_other < 0)
4665 0 : return NULL;
4666 :
4667 116 : ok = 0;
4668 116 : switch(op) {
4669 :
4670 59 : case Py_NE:
4671 : case Py_EQ:
4672 59 : if (len_self == len_other)
4673 48 : ok = all_contained_in(self, other);
4674 59 : if (op == Py_NE && ok >= 0)
4675 17 : ok = !ok;
4676 59 : break;
4677 :
4678 9 : case Py_LT:
4679 9 : if (len_self < len_other)
4680 5 : ok = all_contained_in(self, other);
4681 9 : break;
4682 :
4683 9 : case Py_LE:
4684 9 : if (len_self <= len_other)
4685 7 : ok = all_contained_in(self, other);
4686 9 : break;
4687 :
4688 9 : case Py_GT:
4689 9 : if (len_self > len_other)
4690 5 : ok = all_contained_in(other, self);
4691 9 : break;
4692 :
4693 30 : case Py_GE:
4694 30 : if (len_self >= len_other)
4695 28 : ok = all_contained_in(other, self);
4696 30 : break;
4697 :
4698 : }
4699 116 : if (ok < 0)
4700 6 : return NULL;
4701 110 : result = ok ? Py_True : Py_False;
4702 110 : Py_INCREF(result);
4703 110 : return result;
4704 : }
4705 :
4706 : static PyObject *
4707 501 : dictview_repr(_PyDictViewObject *dv)
4708 : {
4709 : PyObject *seq;
4710 501 : PyObject *result = NULL;
4711 : Py_ssize_t rc;
4712 :
4713 501 : rc = Py_ReprEnter((PyObject *)dv);
4714 501 : if (rc != 0) {
4715 6 : return rc > 0 ? PyUnicode_FromString("...") : NULL;
4716 : }
4717 495 : seq = PySequence_List((PyObject *)dv);
4718 495 : if (seq == NULL) {
4719 0 : goto Done;
4720 : }
4721 495 : result = PyUnicode_FromFormat("%s(%R)", Py_TYPE(dv)->tp_name, seq);
4722 495 : Py_DECREF(seq);
4723 :
4724 495 : Done:
4725 495 : Py_ReprLeave((PyObject *)dv);
4726 495 : return result;
4727 : }
4728 :
4729 : /*** dict_keys ***/
4730 :
4731 : static PyObject *
4732 112503 : dictkeys_iter(_PyDictViewObject *dv)
4733 : {
4734 112503 : if (dv->dv_dict == NULL) {
4735 0 : Py_RETURN_NONE;
4736 : }
4737 112503 : return dictiter_new(dv->dv_dict, &PyDictIterKey_Type);
4738 : }
4739 :
4740 : static int
4741 284201 : dictkeys_contains(_PyDictViewObject *dv, PyObject *obj)
4742 : {
4743 284201 : if (dv->dv_dict == NULL)
4744 0 : return 0;
4745 284201 : return PyDict_Contains((PyObject *)dv->dv_dict, obj);
4746 : }
4747 :
4748 : static PySequenceMethods dictkeys_as_sequence = {
4749 : (lenfunc)dictview_len, /* sq_length */
4750 : 0, /* sq_concat */
4751 : 0, /* sq_repeat */
4752 : 0, /* sq_item */
4753 : 0, /* sq_slice */
4754 : 0, /* sq_ass_item */
4755 : 0, /* sq_ass_slice */
4756 : (objobjproc)dictkeys_contains, /* sq_contains */
4757 : };
4758 :
4759 : // Create an set object from dictviews object.
4760 : // Returns a new reference.
4761 : // This utility function is used by set operations.
4762 : static PyObject*
4763 191 : dictviews_to_set(PyObject *self)
4764 : {
4765 191 : PyObject *left = self;
4766 191 : if (PyDictKeys_Check(self)) {
4767 : // PySet_New() has fast path for the dict object.
4768 165 : PyObject *dict = (PyObject *)((_PyDictViewObject *)self)->dv_dict;
4769 165 : if (PyDict_CheckExact(dict)) {
4770 165 : left = dict;
4771 : }
4772 : }
4773 191 : return PySet_New(left);
4774 : }
4775 :
4776 : static PyObject*
4777 153 : dictviews_sub(PyObject *self, PyObject *other)
4778 : {
4779 153 : PyObject *result = dictviews_to_set(self);
4780 153 : if (result == NULL) {
4781 0 : return NULL;
4782 : }
4783 :
4784 153 : PyObject *tmp = PyObject_CallMethodOneArg(
4785 : result, &_Py_ID(difference_update), other);
4786 153 : if (tmp == NULL) {
4787 2 : Py_DECREF(result);
4788 2 : return NULL;
4789 : }
4790 :
4791 151 : Py_DECREF(tmp);
4792 151 : return result;
4793 : }
4794 :
4795 : static int
4796 : dictitems_contains(_PyDictViewObject *dv, PyObject *obj);
4797 :
4798 : PyObject *
4799 29 : _PyDictView_Intersect(PyObject* self, PyObject *other)
4800 : {
4801 : PyObject *result;
4802 : PyObject *it;
4803 : PyObject *key;
4804 : Py_ssize_t len_self;
4805 : int rv;
4806 : int (*dict_contains)(_PyDictViewObject *, PyObject *);
4807 :
4808 : /* Python interpreter swaps parameters when dict view
4809 : is on right side of & */
4810 29 : if (!PyDictViewSet_Check(self)) {
4811 2 : PyObject *tmp = other;
4812 2 : other = self;
4813 2 : self = tmp;
4814 : }
4815 :
4816 29 : len_self = dictview_len((_PyDictViewObject *)self);
4817 :
4818 : /* if other is a set and self is smaller than other,
4819 : reuse set intersection logic */
4820 29 : if (PySet_CheckExact(other) && len_self <= PyObject_Size(other)) {
4821 7 : return PyObject_CallMethodObjArgs(
4822 : other, &_Py_ID(intersection), self, NULL);
4823 : }
4824 :
4825 : /* if other is another dict view, and it is bigger than self,
4826 : swap them */
4827 22 : if (PyDictViewSet_Check(other)) {
4828 12 : Py_ssize_t len_other = dictview_len((_PyDictViewObject *)other);
4829 12 : if (len_other > len_self) {
4830 3 : PyObject *tmp = other;
4831 3 : other = self;
4832 3 : self = tmp;
4833 : }
4834 : }
4835 :
4836 : /* at this point, two things should be true
4837 : 1. self is a dictview
4838 : 2. if other is a dictview then it is smaller than self */
4839 22 : result = PySet_New(NULL);
4840 22 : if (result == NULL)
4841 0 : return NULL;
4842 :
4843 22 : it = PyObject_GetIter(other);
4844 22 : if (it == NULL) {
4845 2 : Py_DECREF(result);
4846 2 : return NULL;
4847 : }
4848 :
4849 20 : if (PyDictKeys_Check(self)) {
4850 14 : dict_contains = dictkeys_contains;
4851 : }
4852 : /* else PyDictItems_Check(self) */
4853 : else {
4854 6 : dict_contains = dictitems_contains;
4855 : }
4856 :
4857 51 : while ((key = PyIter_Next(it)) != NULL) {
4858 31 : rv = dict_contains((_PyDictViewObject *)self, key);
4859 31 : if (rv < 0) {
4860 0 : goto error;
4861 : }
4862 31 : if (rv) {
4863 19 : if (PySet_Add(result, key)) {
4864 0 : goto error;
4865 : }
4866 : }
4867 31 : Py_DECREF(key);
4868 : }
4869 20 : Py_DECREF(it);
4870 20 : if (PyErr_Occurred()) {
4871 0 : Py_DECREF(result);
4872 0 : return NULL;
4873 : }
4874 20 : return result;
4875 :
4876 0 : error:
4877 0 : Py_DECREF(it);
4878 0 : Py_DECREF(result);
4879 0 : Py_DECREF(key);
4880 0 : return NULL;
4881 : }
4882 :
4883 : static PyObject*
4884 25 : dictviews_or(PyObject* self, PyObject *other)
4885 : {
4886 25 : PyObject *result = dictviews_to_set(self);
4887 25 : if (result == NULL) {
4888 0 : return NULL;
4889 : }
4890 :
4891 25 : if (_PySet_Update(result, other) < 0) {
4892 2 : Py_DECREF(result);
4893 2 : return NULL;
4894 : }
4895 23 : return result;
4896 : }
4897 :
4898 : static PyObject *
4899 105 : dictitems_xor(PyObject *self, PyObject *other)
4900 : {
4901 105 : assert(PyDictItems_Check(self));
4902 105 : assert(PyDictItems_Check(other));
4903 105 : PyObject *d1 = (PyObject *)((_PyDictViewObject *)self)->dv_dict;
4904 105 : PyObject *d2 = (PyObject *)((_PyDictViewObject *)other)->dv_dict;
4905 :
4906 105 : PyObject *temp_dict = PyDict_Copy(d1);
4907 105 : if (temp_dict == NULL) {
4908 0 : return NULL;
4909 : }
4910 105 : PyObject *result_set = PySet_New(NULL);
4911 105 : if (result_set == NULL) {
4912 0 : Py_CLEAR(temp_dict);
4913 0 : return NULL;
4914 : }
4915 :
4916 105 : PyObject *key = NULL, *val1 = NULL, *val2 = NULL;
4917 105 : Py_ssize_t pos = 0;
4918 : Py_hash_t hash;
4919 :
4920 1102 : while (_PyDict_Next(d2, &pos, &key, &val2, &hash)) {
4921 997 : Py_INCREF(key);
4922 997 : Py_INCREF(val2);
4923 997 : val1 = _PyDict_GetItem_KnownHash(temp_dict, key, hash);
4924 :
4925 : int to_delete;
4926 997 : if (val1 == NULL) {
4927 510 : if (PyErr_Occurred()) {
4928 0 : goto error;
4929 : }
4930 510 : to_delete = 0;
4931 : }
4932 : else {
4933 487 : Py_INCREF(val1);
4934 487 : to_delete = PyObject_RichCompareBool(val1, val2, Py_EQ);
4935 487 : if (to_delete < 0) {
4936 0 : goto error;
4937 : }
4938 : }
4939 :
4940 997 : if (to_delete) {
4941 166 : if (_PyDict_DelItem_KnownHash(temp_dict, key, hash) < 0) {
4942 0 : goto error;
4943 : }
4944 : }
4945 : else {
4946 831 : PyObject *pair = PyTuple_Pack(2, key, val2);
4947 831 : if (pair == NULL) {
4948 0 : goto error;
4949 : }
4950 831 : if (PySet_Add(result_set, pair) < 0) {
4951 0 : Py_DECREF(pair);
4952 0 : goto error;
4953 : }
4954 831 : Py_DECREF(pair);
4955 : }
4956 997 : Py_DECREF(key);
4957 997 : Py_XDECREF(val1);
4958 997 : Py_DECREF(val2);
4959 : }
4960 105 : key = val1 = val2 = NULL;
4961 :
4962 105 : PyObject *remaining_pairs = PyObject_CallMethodNoArgs(
4963 : temp_dict, &_Py_ID(items));
4964 105 : if (remaining_pairs == NULL) {
4965 0 : goto error;
4966 : }
4967 105 : if (_PySet_Update(result_set, remaining_pairs) < 0) {
4968 0 : Py_DECREF(remaining_pairs);
4969 0 : goto error;
4970 : }
4971 105 : Py_DECREF(temp_dict);
4972 105 : Py_DECREF(remaining_pairs);
4973 105 : return result_set;
4974 :
4975 0 : error:
4976 0 : Py_XDECREF(temp_dict);
4977 0 : Py_XDECREF(result_set);
4978 0 : Py_XDECREF(key);
4979 0 : Py_XDECREF(val1);
4980 0 : Py_XDECREF(val2);
4981 0 : return NULL;
4982 : }
4983 :
4984 : static PyObject*
4985 118 : dictviews_xor(PyObject* self, PyObject *other)
4986 : {
4987 118 : if (PyDictItems_Check(self) && PyDictItems_Check(other)) {
4988 105 : return dictitems_xor(self, other);
4989 : }
4990 13 : PyObject *result = dictviews_to_set(self);
4991 13 : if (result == NULL) {
4992 0 : return NULL;
4993 : }
4994 :
4995 13 : PyObject *tmp = PyObject_CallMethodOneArg(
4996 : result, &_Py_ID(symmetric_difference_update), other);
4997 13 : if (tmp == NULL) {
4998 2 : Py_DECREF(result);
4999 2 : return NULL;
5000 : }
5001 :
5002 11 : Py_DECREF(tmp);
5003 11 : return result;
5004 : }
5005 :
5006 : static PyNumberMethods dictviews_as_number = {
5007 : 0, /*nb_add*/
5008 : (binaryfunc)dictviews_sub, /*nb_subtract*/
5009 : 0, /*nb_multiply*/
5010 : 0, /*nb_remainder*/
5011 : 0, /*nb_divmod*/
5012 : 0, /*nb_power*/
5013 : 0, /*nb_negative*/
5014 : 0, /*nb_positive*/
5015 : 0, /*nb_absolute*/
5016 : 0, /*nb_bool*/
5017 : 0, /*nb_invert*/
5018 : 0, /*nb_lshift*/
5019 : 0, /*nb_rshift*/
5020 : (binaryfunc)_PyDictView_Intersect, /*nb_and*/
5021 : (binaryfunc)dictviews_xor, /*nb_xor*/
5022 : (binaryfunc)dictviews_or, /*nb_or*/
5023 : };
5024 :
5025 : static PyObject*
5026 29 : dictviews_isdisjoint(PyObject *self, PyObject *other)
5027 : {
5028 : PyObject *it;
5029 29 : PyObject *item = NULL;
5030 :
5031 29 : if (self == other) {
5032 0 : if (dictview_len((_PyDictViewObject *)self) == 0)
5033 0 : Py_RETURN_TRUE;
5034 : else
5035 0 : Py_RETURN_FALSE;
5036 : }
5037 :
5038 : /* Iterate over the shorter object (only if other is a set,
5039 : * because PySequence_Contains may be expensive otherwise): */
5040 29 : if (PyAnySet_Check(other) || PyDictViewSet_Check(other)) {
5041 18 : Py_ssize_t len_self = dictview_len((_PyDictViewObject *)self);
5042 18 : Py_ssize_t len_other = PyObject_Size(other);
5043 18 : if (len_other == -1)
5044 0 : return NULL;
5045 :
5046 18 : if ((len_other > len_self)) {
5047 4 : PyObject *tmp = other;
5048 4 : other = self;
5049 4 : self = tmp;
5050 : }
5051 : }
5052 :
5053 29 : it = PyObject_GetIter(other);
5054 29 : if (it == NULL)
5055 0 : return NULL;
5056 :
5057 58 : while ((item = PyIter_Next(it)) != NULL) {
5058 37 : int contains = PySequence_Contains(self, item);
5059 37 : Py_DECREF(item);
5060 37 : if (contains == -1) {
5061 0 : Py_DECREF(it);
5062 0 : return NULL;
5063 : }
5064 :
5065 37 : if (contains) {
5066 8 : Py_DECREF(it);
5067 8 : Py_RETURN_FALSE;
5068 : }
5069 : }
5070 21 : Py_DECREF(it);
5071 21 : if (PyErr_Occurred())
5072 0 : return NULL; /* PyIter_Next raised an exception. */
5073 21 : Py_RETURN_TRUE;
5074 : }
5075 :
5076 : PyDoc_STRVAR(isdisjoint_doc,
5077 : "Return True if the view and the given iterable have a null intersection.");
5078 :
5079 : static PyObject* dictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored));
5080 :
5081 : PyDoc_STRVAR(reversed_keys_doc,
5082 : "Return a reverse iterator over the dict keys.");
5083 :
5084 : static PyMethodDef dictkeys_methods[] = {
5085 : {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
5086 : isdisjoint_doc},
5087 : {"__reversed__", _PyCFunction_CAST(dictkeys_reversed), METH_NOARGS,
5088 : reversed_keys_doc},
5089 : {NULL, NULL} /* sentinel */
5090 : };
5091 :
5092 : PyTypeObject PyDictKeys_Type = {
5093 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
5094 : "dict_keys", /* tp_name */
5095 : sizeof(_PyDictViewObject), /* tp_basicsize */
5096 : 0, /* tp_itemsize */
5097 : /* methods */
5098 : (destructor)dictview_dealloc, /* tp_dealloc */
5099 : 0, /* tp_vectorcall_offset */
5100 : 0, /* tp_getattr */
5101 : 0, /* tp_setattr */
5102 : 0, /* tp_as_async */
5103 : (reprfunc)dictview_repr, /* tp_repr */
5104 : &dictviews_as_number, /* tp_as_number */
5105 : &dictkeys_as_sequence, /* tp_as_sequence */
5106 : 0, /* tp_as_mapping */
5107 : 0, /* tp_hash */
5108 : 0, /* tp_call */
5109 : 0, /* tp_str */
5110 : PyObject_GenericGetAttr, /* tp_getattro */
5111 : 0, /* tp_setattro */
5112 : 0, /* tp_as_buffer */
5113 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
5114 : 0, /* tp_doc */
5115 : (traverseproc)dictview_traverse, /* tp_traverse */
5116 : 0, /* tp_clear */
5117 : dictview_richcompare, /* tp_richcompare */
5118 : 0, /* tp_weaklistoffset */
5119 : (getiterfunc)dictkeys_iter, /* tp_iter */
5120 : 0, /* tp_iternext */
5121 : dictkeys_methods, /* tp_methods */
5122 : .tp_getset = dictview_getset,
5123 : };
5124 :
5125 : static PyObject *
5126 117082 : dictkeys_new(PyObject *dict, PyObject *Py_UNUSED(ignored))
5127 : {
5128 117082 : return _PyDictView_New(dict, &PyDictKeys_Type);
5129 : }
5130 :
5131 : static PyObject *
5132 2 : dictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
5133 : {
5134 2 : if (dv->dv_dict == NULL) {
5135 0 : Py_RETURN_NONE;
5136 : }
5137 2 : return dictiter_new(dv->dv_dict, &PyDictRevIterKey_Type);
5138 : }
5139 :
5140 : /*** dict_items ***/
5141 :
5142 : static PyObject *
5143 615175 : dictitems_iter(_PyDictViewObject *dv)
5144 : {
5145 615175 : if (dv->dv_dict == NULL) {
5146 0 : Py_RETURN_NONE;
5147 : }
5148 615175 : return dictiter_new(dv->dv_dict, &PyDictIterItem_Type);
5149 : }
5150 :
5151 : static int
5152 135 : dictitems_contains(_PyDictViewObject *dv, PyObject *obj)
5153 : {
5154 : int result;
5155 : PyObject *key, *value, *found;
5156 135 : if (dv->dv_dict == NULL)
5157 0 : return 0;
5158 135 : if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 2)
5159 10 : return 0;
5160 125 : key = PyTuple_GET_ITEM(obj, 0);
5161 125 : value = PyTuple_GET_ITEM(obj, 1);
5162 125 : found = PyDict_GetItemWithError((PyObject *)dv->dv_dict, key);
5163 125 : if (found == NULL) {
5164 16 : if (PyErr_Occurred())
5165 1 : return -1;
5166 15 : return 0;
5167 : }
5168 109 : Py_INCREF(found);
5169 109 : result = PyObject_RichCompareBool(found, value, Py_EQ);
5170 109 : Py_DECREF(found);
5171 109 : return result;
5172 : }
5173 :
5174 : static PySequenceMethods dictitems_as_sequence = {
5175 : (lenfunc)dictview_len, /* sq_length */
5176 : 0, /* sq_concat */
5177 : 0, /* sq_repeat */
5178 : 0, /* sq_item */
5179 : 0, /* sq_slice */
5180 : 0, /* sq_ass_item */
5181 : 0, /* sq_ass_slice */
5182 : (objobjproc)dictitems_contains, /* sq_contains */
5183 : };
5184 :
5185 : static PyObject* dictitems_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored));
5186 :
5187 : PyDoc_STRVAR(reversed_items_doc,
5188 : "Return a reverse iterator over the dict items.");
5189 :
5190 : static PyMethodDef dictitems_methods[] = {
5191 : {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
5192 : isdisjoint_doc},
5193 : {"__reversed__", (PyCFunction)dictitems_reversed, METH_NOARGS,
5194 : reversed_items_doc},
5195 : {NULL, NULL} /* sentinel */
5196 : };
5197 :
5198 : PyTypeObject PyDictItems_Type = {
5199 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
5200 : "dict_items", /* tp_name */
5201 : sizeof(_PyDictViewObject), /* tp_basicsize */
5202 : 0, /* tp_itemsize */
5203 : /* methods */
5204 : (destructor)dictview_dealloc, /* tp_dealloc */
5205 : 0, /* tp_vectorcall_offset */
5206 : 0, /* tp_getattr */
5207 : 0, /* tp_setattr */
5208 : 0, /* tp_as_async */
5209 : (reprfunc)dictview_repr, /* tp_repr */
5210 : &dictviews_as_number, /* tp_as_number */
5211 : &dictitems_as_sequence, /* tp_as_sequence */
5212 : 0, /* tp_as_mapping */
5213 : 0, /* tp_hash */
5214 : 0, /* tp_call */
5215 : 0, /* tp_str */
5216 : PyObject_GenericGetAttr, /* tp_getattro */
5217 : 0, /* tp_setattro */
5218 : 0, /* tp_as_buffer */
5219 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
5220 : 0, /* tp_doc */
5221 : (traverseproc)dictview_traverse, /* tp_traverse */
5222 : 0, /* tp_clear */
5223 : dictview_richcompare, /* tp_richcompare */
5224 : 0, /* tp_weaklistoffset */
5225 : (getiterfunc)dictitems_iter, /* tp_iter */
5226 : 0, /* tp_iternext */
5227 : dictitems_methods, /* tp_methods */
5228 : .tp_getset = dictview_getset,
5229 : };
5230 :
5231 : static PyObject *
5232 618264 : dictitems_new(PyObject *dict, PyObject *Py_UNUSED(ignored))
5233 : {
5234 618264 : return _PyDictView_New(dict, &PyDictItems_Type);
5235 : }
5236 :
5237 : static PyObject *
5238 9 : dictitems_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
5239 : {
5240 9 : if (dv->dv_dict == NULL) {
5241 0 : Py_RETURN_NONE;
5242 : }
5243 9 : return dictiter_new(dv->dv_dict, &PyDictRevIterItem_Type);
5244 : }
5245 :
5246 : /*** dict_values ***/
5247 :
5248 : static PyObject *
5249 372030 : dictvalues_iter(_PyDictViewObject *dv)
5250 : {
5251 372030 : if (dv->dv_dict == NULL) {
5252 0 : Py_RETURN_NONE;
5253 : }
5254 372030 : return dictiter_new(dv->dv_dict, &PyDictIterValue_Type);
5255 : }
5256 :
5257 : static PySequenceMethods dictvalues_as_sequence = {
5258 : (lenfunc)dictview_len, /* sq_length */
5259 : 0, /* sq_concat */
5260 : 0, /* sq_repeat */
5261 : 0, /* sq_item */
5262 : 0, /* sq_slice */
5263 : 0, /* sq_ass_item */
5264 : 0, /* sq_ass_slice */
5265 : (objobjproc)0, /* sq_contains */
5266 : };
5267 :
5268 : static PyObject* dictvalues_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored));
5269 :
5270 : PyDoc_STRVAR(reversed_values_doc,
5271 : "Return a reverse iterator over the dict values.");
5272 :
5273 : static PyMethodDef dictvalues_methods[] = {
5274 : {"__reversed__", (PyCFunction)dictvalues_reversed, METH_NOARGS,
5275 : reversed_values_doc},
5276 : {NULL, NULL} /* sentinel */
5277 : };
5278 :
5279 : PyTypeObject PyDictValues_Type = {
5280 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
5281 : "dict_values", /* tp_name */
5282 : sizeof(_PyDictViewObject), /* tp_basicsize */
5283 : 0, /* tp_itemsize */
5284 : /* methods */
5285 : (destructor)dictview_dealloc, /* tp_dealloc */
5286 : 0, /* tp_vectorcall_offset */
5287 : 0, /* tp_getattr */
5288 : 0, /* tp_setattr */
5289 : 0, /* tp_as_async */
5290 : (reprfunc)dictview_repr, /* tp_repr */
5291 : 0, /* tp_as_number */
5292 : &dictvalues_as_sequence, /* tp_as_sequence */
5293 : 0, /* tp_as_mapping */
5294 : 0, /* tp_hash */
5295 : 0, /* tp_call */
5296 : 0, /* tp_str */
5297 : PyObject_GenericGetAttr, /* tp_getattro */
5298 : 0, /* tp_setattro */
5299 : 0, /* tp_as_buffer */
5300 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
5301 : 0, /* tp_doc */
5302 : (traverseproc)dictview_traverse, /* tp_traverse */
5303 : 0, /* tp_clear */
5304 : 0, /* tp_richcompare */
5305 : 0, /* tp_weaklistoffset */
5306 : (getiterfunc)dictvalues_iter, /* tp_iter */
5307 : 0, /* tp_iternext */
5308 : dictvalues_methods, /* tp_methods */
5309 : .tp_getset = dictview_getset,
5310 : };
5311 :
5312 : static PyObject *
5313 376154 : dictvalues_new(PyObject *dict, PyObject *Py_UNUSED(ignored))
5314 : {
5315 376154 : return _PyDictView_New(dict, &PyDictValues_Type);
5316 : }
5317 :
5318 : static PyObject *
5319 14 : dictvalues_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
5320 : {
5321 14 : if (dv->dv_dict == NULL) {
5322 0 : Py_RETURN_NONE;
5323 : }
5324 14 : return dictiter_new(dv->dv_dict, &PyDictRevIterValue_Type);
5325 : }
5326 :
5327 :
5328 : /* Returns NULL if cannot allocate a new PyDictKeysObject,
5329 : but does not set an error */
5330 : PyDictKeysObject *
5331 681619 : _PyDict_NewKeysForClass(void)
5332 : {
5333 681619 : PyDictKeysObject *keys = new_keys_object(NEXT_LOG2_SHARED_KEYS_MAX_SIZE, 1);
5334 681619 : if (keys == NULL) {
5335 0 : PyErr_Clear();
5336 : }
5337 : else {
5338 681619 : assert(keys->dk_nentries == 0);
5339 : /* Set to max size+1 as it will shrink by one before each new object */
5340 681619 : keys->dk_usable = SHARED_KEYS_MAX_SIZE;
5341 681619 : keys->dk_kind = DICT_KEYS_SPLIT;
5342 : }
5343 681619 : return keys;
5344 : }
5345 :
5346 : #define CACHED_KEYS(tp) (((PyHeapTypeObject*)tp)->ht_cached_keys)
5347 :
5348 : static int
5349 8721090 : init_inline_values(PyObject *obj, PyTypeObject *tp)
5350 : {
5351 8721090 : assert(tp->tp_flags & Py_TPFLAGS_HEAPTYPE);
5352 : // assert(type->tp_dictoffset > 0); -- TO DO Update this assert.
5353 8721090 : assert(tp->tp_flags & Py_TPFLAGS_MANAGED_DICT);
5354 8721090 : PyDictKeysObject *keys = CACHED_KEYS(tp);
5355 8721090 : assert(keys != NULL);
5356 8721090 : if (keys->dk_usable > 1) {
5357 1402130 : keys->dk_usable--;
5358 : }
5359 8721090 : Py_ssize_t size = shared_keys_usable_size(keys);
5360 8721090 : assert(size > 0);
5361 8721090 : PyDictValues *values = new_values(size);
5362 8721090 : if (values == NULL) {
5363 0 : PyErr_NoMemory();
5364 0 : return -1;
5365 : }
5366 8721090 : assert(((uint8_t *)values)[-1] >= size+2);
5367 8721090 : ((uint8_t *)values)[-2] = 0;
5368 69413500 : for (int i = 0; i < size; i++) {
5369 60692400 : values->values[i] = NULL;
5370 : }
5371 8721090 : *_PyObject_ValuesPointer(obj) = values;
5372 8721090 : return 0;
5373 : }
5374 :
5375 : int
5376 10529000 : _PyObject_InitializeDict(PyObject *obj)
5377 : {
5378 10529000 : PyTypeObject *tp = Py_TYPE(obj);
5379 10529000 : if (tp->tp_dictoffset == 0) {
5380 1807940 : return 0;
5381 : }
5382 8721090 : if (tp->tp_flags & Py_TPFLAGS_MANAGED_DICT) {
5383 : OBJECT_STAT_INC(new_values);
5384 8721090 : return init_inline_values(obj, tp);
5385 : }
5386 : PyObject *dict;
5387 4 : if (_PyType_HasFeature(tp, Py_TPFLAGS_HEAPTYPE) && CACHED_KEYS(tp)) {
5388 0 : dictkeys_incref(CACHED_KEYS(tp));
5389 0 : dict = new_dict_with_shared_keys(CACHED_KEYS(tp));
5390 : }
5391 : else {
5392 4 : dict = PyDict_New();
5393 : }
5394 4 : if (dict == NULL) {
5395 0 : return -1;
5396 : }
5397 4 : PyObject **dictptr = _PyObject_DictPointer(obj);
5398 4 : *dictptr = dict;
5399 4 : return 0;
5400 : }
5401 :
5402 : static PyObject *
5403 247233 : make_dict_from_instance_attributes(PyDictKeysObject *keys, PyDictValues *values)
5404 : {
5405 247233 : dictkeys_incref(keys);
5406 247233 : Py_ssize_t used = 0;
5407 247233 : Py_ssize_t track = 0;
5408 2038720 : for (Py_ssize_t i = 0; i < shared_keys_usable_size(keys); i++) {
5409 1791480 : PyObject *val = values->values[i];
5410 1791480 : if (val != NULL) {
5411 778114 : used += 1;
5412 778114 : track += _PyObject_GC_MAY_BE_TRACKED(val);
5413 : }
5414 : }
5415 247233 : PyObject *res = new_dict(keys, values, used, 0);
5416 247233 : if (track && res) {
5417 125924 : _PyObject_GC_TRACK(res);
5418 : }
5419 247233 : return res;
5420 : }
5421 :
5422 : PyObject *
5423 576 : _PyObject_MakeDictFromInstanceAttributes(PyObject *obj, PyDictValues *values)
5424 : {
5425 576 : assert(Py_TYPE(obj)->tp_flags & Py_TPFLAGS_MANAGED_DICT);
5426 576 : PyDictKeysObject *keys = CACHED_KEYS(Py_TYPE(obj));
5427 : OBJECT_STAT_INC(dict_materialized_on_request);
5428 576 : return make_dict_from_instance_attributes(keys, values);
5429 : }
5430 :
5431 : int
5432 7700960 : _PyObject_StoreInstanceAttribute(PyObject *obj, PyDictValues *values,
5433 : PyObject *name, PyObject *value)
5434 : {
5435 7700960 : PyDictKeysObject *keys = CACHED_KEYS(Py_TYPE(obj));
5436 7700960 : assert(keys != NULL);
5437 7700960 : assert(values != NULL);
5438 7700960 : assert(Py_TYPE(obj)->tp_flags & Py_TPFLAGS_MANAGED_DICT);
5439 7700960 : Py_ssize_t ix = DKIX_EMPTY;
5440 7700960 : if (PyUnicode_CheckExact(name)) {
5441 7700960 : ix = insert_into_dictkeys(keys, name);
5442 : }
5443 7700960 : if (ix == DKIX_EMPTY) {
5444 : #ifdef Py_STATS
5445 : if (PyUnicode_CheckExact(name)) {
5446 : if (shared_keys_usable_size(keys) == SHARED_KEYS_MAX_SIZE) {
5447 : OBJECT_STAT_INC(dict_materialized_too_big);
5448 : }
5449 : else {
5450 : OBJECT_STAT_INC(dict_materialized_new_key);
5451 : }
5452 : }
5453 : else {
5454 : OBJECT_STAT_INC(dict_materialized_str_subclass);
5455 : }
5456 : #endif
5457 111105 : PyObject *dict = make_dict_from_instance_attributes(keys, values);
5458 111105 : if (dict == NULL) {
5459 0 : return -1;
5460 : }
5461 111105 : *_PyObject_ValuesPointer(obj) = NULL;
5462 111105 : *_PyObject_ManagedDictPointer(obj) = dict;
5463 111105 : if (value == NULL) {
5464 1 : return PyDict_DelItem(dict, name);
5465 : }
5466 : else {
5467 111104 : return PyDict_SetItem(dict, name, value);
5468 : }
5469 : }
5470 7589860 : PyObject *old_value = values->values[ix];
5471 7589860 : Py_XINCREF(value);
5472 7589860 : values->values[ix] = value;
5473 7589860 : if (old_value == NULL) {
5474 3465220 : if (value == NULL) {
5475 75 : PyErr_Format(PyExc_AttributeError,
5476 : "'%.100s' object has no attribute '%U'",
5477 75 : Py_TYPE(obj)->tp_name, name);
5478 75 : return -1;
5479 : }
5480 3465150 : _PyDictValues_AddToInsertionOrder(values, ix);
5481 : }
5482 : else {
5483 4124640 : if (value == NULL) {
5484 3372990 : delete_index_from_values(values, ix);
5485 : }
5486 4124640 : Py_DECREF(old_value);
5487 : }
5488 7589780 : return 0;
5489 : }
5490 :
5491 : PyObject *
5492 63073600 : _PyObject_GetInstanceAttribute(PyObject *obj, PyDictValues *values,
5493 : PyObject *name)
5494 : {
5495 63073600 : assert(PyUnicode_CheckExact(name));
5496 63073600 : PyDictKeysObject *keys = CACHED_KEYS(Py_TYPE(obj));
5497 63073600 : assert(keys != NULL);
5498 63073600 : Py_ssize_t ix = _PyDictKeys_StringLookup(keys, name);
5499 63073600 : if (ix == DKIX_EMPTY) {
5500 41229200 : return NULL;
5501 : }
5502 21844500 : PyObject *value = values->values[ix];
5503 21844500 : Py_XINCREF(value);
5504 21844500 : return value;
5505 : }
5506 :
5507 : int
5508 63142 : _PyObject_IsInstanceDictEmpty(PyObject *obj)
5509 : {
5510 63142 : PyTypeObject *tp = Py_TYPE(obj);
5511 63142 : if (tp->tp_dictoffset == 0) {
5512 1623 : return 1;
5513 : }
5514 : PyObject **dictptr;
5515 61519 : if (tp->tp_flags & Py_TPFLAGS_MANAGED_DICT) {
5516 60805 : PyDictValues *values = *_PyObject_ValuesPointer(obj);
5517 60805 : if (values) {
5518 51408 : PyDictKeysObject *keys = CACHED_KEYS(tp);
5519 51471 : for (Py_ssize_t i = 0; i < keys->dk_nentries; i++) {
5520 50944 : if (values->values[i] != NULL) {
5521 50881 : return 0;
5522 : }
5523 : }
5524 527 : return 1;
5525 : }
5526 9397 : dictptr = _PyObject_ManagedDictPointer(obj);
5527 : }
5528 : else {
5529 714 : dictptr = _PyObject_DictPointer(obj);
5530 : }
5531 10111 : PyObject *dict = *dictptr;
5532 10111 : if (dict == NULL) {
5533 960 : return 1;
5534 : }
5535 9151 : return ((PyDictObject *)dict)->ma_used == 0;
5536 : }
5537 :
5538 :
5539 : int
5540 105863000 : _PyObject_VisitInstanceAttributes(PyObject *self, visitproc visit, void *arg)
5541 : {
5542 105863000 : PyTypeObject *tp = Py_TYPE(self);
5543 105863000 : assert(Py_TYPE(self)->tp_flags & Py_TPFLAGS_MANAGED_DICT);
5544 105863000 : PyDictValues **values_ptr = _PyObject_ValuesPointer(self);
5545 105863000 : if (*values_ptr == NULL) {
5546 49690500 : return 0;
5547 : }
5548 56172000 : PyDictKeysObject *keys = CACHED_KEYS(tp);
5549 343088000 : for (Py_ssize_t i = 0; i < keys->dk_nentries; i++) {
5550 286916000 : Py_VISIT((*values_ptr)->values[i]);
5551 : }
5552 56172000 : return 0;
5553 : }
5554 :
5555 : void
5556 851210 : _PyObject_ClearInstanceAttributes(PyObject *self)
5557 : {
5558 851210 : PyTypeObject *tp = Py_TYPE(self);
5559 851210 : assert(Py_TYPE(self)->tp_flags & Py_TPFLAGS_MANAGED_DICT);
5560 851210 : PyDictValues **values_ptr = _PyObject_ValuesPointer(self);
5561 851210 : if (*values_ptr == NULL) {
5562 111643 : return;
5563 : }
5564 739567 : PyDictKeysObject *keys = CACHED_KEYS(tp);
5565 2909310 : for (Py_ssize_t i = 0; i < keys->dk_nentries; i++) {
5566 2169750 : Py_CLEAR((*values_ptr)->values[i]);
5567 : }
5568 : }
5569 :
5570 : void
5571 8878440 : _PyObject_FreeInstanceAttributes(PyObject *self)
5572 : {
5573 8878440 : PyTypeObject *tp = Py_TYPE(self);
5574 8878440 : assert(Py_TYPE(self)->tp_flags & Py_TPFLAGS_MANAGED_DICT);
5575 8878440 : PyDictValues **values_ptr = _PyObject_ValuesPointer(self);
5576 8878440 : if (*values_ptr == NULL) {
5577 410285 : return;
5578 : }
5579 8468160 : PyDictKeysObject *keys = CACHED_KEYS(tp);
5580 39131100 : for (Py_ssize_t i = 0; i < keys->dk_nentries; i++) {
5581 30663000 : Py_XDECREF((*values_ptr)->values[i]);
5582 : }
5583 8468160 : free_values(*values_ptr);
5584 : }
5585 :
5586 : PyObject *
5587 497358 : PyObject_GenericGetDict(PyObject *obj, void *context)
5588 : {
5589 : PyObject *dict;
5590 497358 : PyTypeObject *tp = Py_TYPE(obj);
5591 497358 : if (_PyType_HasFeature(tp, Py_TPFLAGS_MANAGED_DICT)) {
5592 299752 : PyDictValues **values_ptr = _PyObject_ValuesPointer(obj);
5593 299752 : PyObject **dictptr = _PyObject_ManagedDictPointer(obj);
5594 299752 : if (*values_ptr) {
5595 135552 : assert(*dictptr == NULL);
5596 : OBJECT_STAT_INC(dict_materialized_on_request);
5597 135552 : *dictptr = dict = make_dict_from_instance_attributes(CACHED_KEYS(tp), *values_ptr);
5598 135552 : if (dict != NULL) {
5599 135552 : *values_ptr = NULL;
5600 : }
5601 : }
5602 164200 : else if (*dictptr == NULL) {
5603 1949 : *dictptr = dict = PyDict_New();
5604 : }
5605 : else {
5606 162251 : dict = *dictptr;
5607 : }
5608 : }
5609 : else {
5610 197606 : PyObject **dictptr = _PyObject_DictPointer(obj);
5611 197606 : if (dictptr == NULL) {
5612 0 : PyErr_SetString(PyExc_AttributeError,
5613 : "This object has no __dict__");
5614 0 : return NULL;
5615 : }
5616 197606 : dict = *dictptr;
5617 197606 : if (dict == NULL) {
5618 168130 : PyTypeObject *tp = Py_TYPE(obj);
5619 168130 : if (_PyType_HasFeature(tp, Py_TPFLAGS_HEAPTYPE) && CACHED_KEYS(tp)) {
5620 0 : dictkeys_incref(CACHED_KEYS(tp));
5621 0 : *dictptr = dict = new_dict_with_shared_keys(CACHED_KEYS(tp));
5622 : }
5623 : else {
5624 168130 : *dictptr = dict = PyDict_New();
5625 : }
5626 : }
5627 : }
5628 497358 : Py_XINCREF(dict);
5629 497358 : return dict;
5630 : }
5631 :
5632 : int
5633 57668300 : _PyObjectDict_SetItem(PyTypeObject *tp, PyObject **dictptr,
5634 : PyObject *key, PyObject *value)
5635 : {
5636 : PyObject *dict;
5637 : int res;
5638 : PyDictKeysObject *cached;
5639 :
5640 57668300 : assert(dictptr != NULL);
5641 57668300 : if ((tp->tp_flags & Py_TPFLAGS_HEAPTYPE) && (cached = CACHED_KEYS(tp))) {
5642 5179820 : assert(dictptr != NULL);
5643 5179820 : dict = *dictptr;
5644 5179820 : if (dict == NULL) {
5645 4338660 : dictkeys_incref(cached);
5646 4338660 : dict = new_dict_with_shared_keys(cached);
5647 4338660 : if (dict == NULL)
5648 0 : return -1;
5649 4338660 : *dictptr = dict;
5650 : }
5651 5179820 : if (value == NULL) {
5652 6493 : res = PyDict_DelItem(dict, key);
5653 : }
5654 : else {
5655 5173320 : res = PyDict_SetItem(dict, key, value);
5656 : }
5657 : } else {
5658 52488500 : dict = *dictptr;
5659 52488500 : if (dict == NULL) {
5660 6280370 : dict = PyDict_New();
5661 6280370 : if (dict == NULL)
5662 0 : return -1;
5663 6280370 : *dictptr = dict;
5664 : }
5665 52488500 : if (value == NULL) {
5666 158522 : res = PyDict_DelItem(dict, key);
5667 : } else {
5668 52330000 : res = PyDict_SetItem(dict, key, value);
5669 : }
5670 : }
5671 57668300 : ASSERT_CONSISTENT(dict);
5672 57668300 : return res;
5673 : }
5674 :
5675 : void
5676 664372 : _PyDictKeys_DecRef(PyDictKeysObject *keys)
5677 : {
5678 664372 : dictkeys_decref(keys);
5679 664372 : }
5680 :
5681 : static uint32_t next_dict_keys_version = 2;
5682 :
5683 3275510 : uint32_t _PyDictKeys_GetVersionForCurrentState(PyDictKeysObject *dictkeys)
5684 : {
5685 3275510 : if (dictkeys->dk_version != 0) {
5686 3070360 : return dictkeys->dk_version;
5687 : }
5688 205146 : if (next_dict_keys_version == 0) {
5689 0 : return 0;
5690 : }
5691 205146 : uint32_t v = next_dict_keys_version++;
5692 205146 : dictkeys->dk_version = v;
5693 205146 : return v;
5694 : }
|
