Debian Codegraph @

src/frozendict/c_src/3_6/cpython_src/Objects/dictobject_original.c

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