1 /* Dictionary object implementation using a hash table */
2
3 /* The distribution includes a separate file, Objects/dictnotes.txt,
4 describing explorations into dictionary design and optimization.
5 It covers typical dictionary use patterns, the parameters for
6 tuning dictionaries, and several ideas for possible optimizations.
7 */
8
9 /* PyDictKeysObject
10
11 This implements the dictionary's hashtable.
12
13 As of Python 3.6, this is compact and ordered. Basic idea is described here:
14 * https://mail.python.org/pipermail/python-dev/2012-December/123028.html
15 * https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html
16
17 layout:
18
19 +---------------+
20 | dk_refcnt |
21 | dk_size |
22 | dk_lookup |
23 | dk_usable |
24 | dk_nentries |
25 +---------------+
26 | dk_indices |
27 | |
28 +---------------+
29 | dk_entries |
30 | |
31 +---------------+
32
33 dk_indices is actual hashtable. It holds index in entries, or DKIX_EMPTY(-1)
34 or DKIX_DUMMY(-2).
35 Size of indices is dk_size. Type of each index in indices is vary on dk_size:
36
37 * int8 for dk_size <= 128
38 * int16 for 256 <= dk_size <= 2**15
39 * int32 for 2**16 <= dk_size <= 2**31
40 * int64 for 2**32 <= dk_size
41
42 dk_entries is array of PyDictKeyEntry. Its size is USABLE_FRACTION(dk_size).
43 DK_ENTRIES(dk) can be used to get pointer to entries.
44
45 NOTE: Since negative value is used for DKIX_EMPTY and DKIX_DUMMY, type of
46 dk_indices entry is signed integer and int16 is used for table which
47 dk_size == 256.
48 */
49
50
51 /*
52 The DictObject can be in one of two forms.
53
54 Either:
55 A combined table:
56 ma_values == NULL, dk_refcnt == 1.
57 Values are stored in the me_value field of the PyDictKeysObject.
58 Or:
59 A split table:
60 ma_values != NULL, dk_refcnt >= 1
61 Values are stored in the ma_values array.
62 Only string (unicode) keys are allowed.
63 All dicts sharing same key must have same insertion order.
64
65 There are four kinds of slots in the table (slot is index, and
66 DK_ENTRIES(keys)[index] if index >= 0):
67
68 1. Unused. index == DKIX_EMPTY
69 Does not hold an active (key, value) pair now and never did. Unused can
70 transition to Active upon key insertion. This is each slot's initial state.
71
72 2. Active. index >= 0, me_key != NULL and me_value != NULL
73 Holds an active (key, value) pair. Active can transition to Dummy or
74 Pending upon key deletion (for combined and split tables respectively).
75 This is the only case in which me_value != NULL.
76
77 3. Dummy. index == DKIX_DUMMY (combined only)
78 Previously held an active (key, value) pair, but that was deleted and an
79 active pair has not yet overwritten the slot. Dummy can transition to
80 Active upon key insertion. Dummy slots cannot be made Unused again
81 else the probe sequence in case of collision would have no way to know
82 they were once active.
83
84 4. Pending. index >= 0, key != NULL, and value == NULL (split only)
85 Not yet inserted in split-table.
86 */
87
88 /*
89 Preserving insertion order
90
91 It's simple for combined table. Since dk_entries is mostly append only, we can
92 get insertion order by just iterating dk_entries.
93
94 One exception is .popitem(). It removes last item in dk_entries and decrement
95 dk_nentries to achieve amortized O(1). Since there are DKIX_DUMMY remains in
96 dk_indices, we can't increment dk_usable even though dk_nentries is
97 decremented.
98
99 In split table, inserting into pending entry is allowed only for dk_entries[ix]
100 where ix == mp->ma_used. Inserting into other index and deleting item cause
101 converting the dict to the combined table.
102 */
103
104 /* PyDict_MINSIZE is the starting size for any new dict.
105 * 8 allows dicts with no more than 5 active entries; experiments suggested
106 * this suffices for the majority of dicts (consisting mostly of usually-small
107 * dicts created to pass keyword arguments).
108 * Making this 8, rather than 4 reduces the number of resizes for most
109 * dictionaries, without any significant extra memory use.
110 */
111 #define PyDict_MINSIZE 8
112
113 #include <Python.h>
114 #include "pycore_gc.h" // _PyObject_GC_IS_TRACKED()
115 #include "pycore_object.h" // _PyObject_GC_TRACK()
116 #include "pycore_pyerrors.h" // _PyErr_Fetch()
117 #include "pycore_pystate.h" // _PyThreadState_GET()
118 #include "dict-common.h"
119 #include "stringlib/eq.h" // unicode_eq()
120 #include "frozendictobject.h"
121 #include "setobject.h" // PyFrozenSet_Type.tp_hash
122
123 /*[clinic input]
124 class dict "PyDictObject *" "&PyDict_Type"
125 [clinic start generated code]*/
126 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=f157a5a0ce9589d6]*/
127
128
129 /*
130 To ensure the lookup algorithm terminates, there must be at least one Unused
131 slot (NULL key) in the table.
132 To avoid slowing down lookups on a near-full table, we resize the table when
133 it's USABLE_FRACTION (currently two-thirds) full.
134 */
135
136 #define PERTURB_SHIFT 5
137
138 /*
139 Major subtleties ahead: Most hash schemes depend on having a "good" hash
140 function, in the sense of simulating randomness. Python doesn't: its most
141 important hash functions (for ints) are very regular in common
142 cases:
143
144 >>>[hash(i) for i in range(4)]
145 [0, 1, 2, 3]
146
147 This isn't necessarily bad! To the contrary, in a table of size 2**i, taking
148 the low-order i bits as the initial table index is extremely fast, and there
149 are no collisions at all for dicts indexed by a contiguous range of ints. So
150 this gives better-than-random behavior in common cases, and that's very
151 desirable.
152
153 OTOH, when collisions occur, the tendency to fill contiguous slices of the
154 hash table makes a good collision resolution strategy crucial. Taking only
155 the last i bits of the hash code is also vulnerable: for example, consider
156 the list [i << 16 for i in range(20000)] as a set of keys. Since ints are
157 their own hash codes, and this fits in a dict of size 2**15, the last 15 bits
158 of every hash code are all 0: they *all* map to the same table index.
159
160 But catering to unusual cases should not slow the usual ones, so we just take
161 the last i bits anyway. It's up to collision resolution to do the rest. If
162 we *usually* find the key we're looking for on the first try (and, it turns
163 out, we usually do -- the table load factor is kept under 2/3, so the odds
164 are solidly in our favor), then it makes best sense to keep the initial index
165 computation dirt cheap.
166
167 The first half of collision resolution is to visit table indices via this
168 recurrence:
169
170 j = ((5*j) + 1) mod 2**i
171
172 For any initial j in range(2**i), repeating that 2**i times generates each
173 int in range(2**i) exactly once (see any text on random-number generation for
174 proof). By itself, this doesn't help much: like linear probing (setting
175 j += 1, or j -= 1, on each loop trip), it scans the table entries in a fixed
176 order. This would be bad, except that's not the only thing we do, and it's
177 actually *good* in the common cases where hash keys are consecutive. In an
178 example that's really too small to make this entirely clear, for a table of
179 size 2**3 the order of indices is:
180
181 0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating]
182
183 If two things come in at index 5, the first place we look after is index 2,
184 not 6, so if another comes in at index 6 the collision at 5 didn't hurt it.
185 Linear probing is deadly in this case because there the fixed probe order
186 is the *same* as the order consecutive keys are likely to arrive. But it's
187 extremely unlikely hash codes will follow a 5*j+1 recurrence by accident,
188 and certain that consecutive hash codes do not.
189
190 The other half of the strategy is to get the other bits of the hash code
191 into play. This is done by initializing a (unsigned) vrbl "perturb" to the
192 full hash code, and changing the recurrence to:
193
194 perturb >>= PERTURB_SHIFT;
195 j = (5*j) + 1 + perturb;
196 use j % 2**i as the next table index;
197
198 Now the probe sequence depends (eventually) on every bit in the hash code,
199 and the pseudo-scrambling property of recurring on 5*j+1 is more valuable,
200 because it quickly magnifies small differences in the bits that didn't affect
201 the initial index. Note that because perturb is unsigned, if the recurrence
202 is executed often enough perturb eventually becomes and remains 0. At that
203 point (very rarely reached) the recurrence is on (just) 5*j+1 again, and
204 that's certain to find an empty slot eventually (since it generates every int
205 in range(2**i), and we make sure there's always at least one empty slot).
206
207 Selecting a good value for PERTURB_SHIFT is a balancing act. You want it
208 small so that the high bits of the hash code continue to affect the probe
209 sequence across iterations; but you want it large so that in really bad cases
210 the high-order hash bits have an effect on early iterations. 5 was "the
211 best" in minimizing total collisions across experiments Tim Peters ran (on
212 both normal and pathological cases), but 4 and 6 weren't significantly worse.
213
214 Historical: Reimer Behrends contributed the idea of using a polynomial-based
215 approach, using repeated multiplication by x in GF(2**n) where an irreducible
216 polynomial for each table size was chosen such that x was a primitive root.
217 Christian Tismer later extended that to use division by x instead, as an
218 efficient way to get the high bits of the hash code into play. This scheme
219 also gave excellent collision statistics, but was more expensive: two
220 if-tests were required inside the loop; computing "the next" index took about
221 the same number of operations but without as much potential parallelism
222 (e.g., computing 5*j can go on at the same time as computing 1+perturb in the
223 above, and then shifting perturb can be done while the table index is being
224 masked); and the PyDictObject struct required a member to hold the table's
225 polynomial. In Tim's experiments the current scheme ran faster, produced
226 equally good collision statistics, needed less code & used less memory.
227
228 */
229
230 static Py_ssize_t
231 lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
232 Py_hash_t hash, PyObject **value_addr);
233 static PyObject* dict_iter(PyDictObject *dict);
234 static PyObject* frozendict_iter(PyDictObject *dict);
235 static PyObject *dictiter_new(PyDictObject *, PyTypeObject *);
236
237
238 /*Global counter used to set ma_version_tag field of dictionary.
239 * It is incremented each time that a dictionary is created and each
240 * time that a dictionary is modified. */
241 static uint64_t pydict_global_version = 0;
242
243 #define DICT_NEXT_VERSION() (++pydict_global_version)
244
245 /* Dictionary reuse scheme to save calls to malloc and free */
246 #ifndef PyDict_MAXFREELIST
247 #define PyDict_MAXFREELIST 80
248 #endif
249
250 #if PyDict_MAXFREELIST > 0
251 static PyDictObject *free_list[PyDict_MAXFREELIST];
252 static int numfree = 0;
253 static PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST];
254 static int numfreekeys = 0;
255 #endif
256
257 #include "clinic/frozendictobject.c.h"
258
259 #define DK_SIZE(dk) ((dk)->dk_size)
260 #if SIZEOF_VOID_P > 4
261 #define DK_IXSIZE(dk) \
262 (DK_SIZE(dk) <= 0xff ? \
263 1 : DK_SIZE(dk) <= 0xffff ? \
264 2 : DK_SIZE(dk) <= 0xffffffff ? \
265 4 : sizeof(int64_t))
266 #else
267 #define DK_IXSIZE(dk) \
268 (DK_SIZE(dk) <= 0xff ? \
269 1 : DK_SIZE(dk) <= 0xffff ? \
270 2 : sizeof(int32_t))
271 #endif
272 #define DK_ENTRIES(dk) \
273 ((PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[DK_SIZE(dk) * DK_IXSIZE(dk)]))
274
275 #define DK_MASK(dk) (((dk)->dk_size)-1)
276 #define IS_POWER_OF_2(x) (((x) & (x-1)) == 0)
277
278 static void free_keys_object(PyDictKeysObject *keys, const int decref_items);
279
280 static inline void
dictkeys_incref(PyDictKeysObject * dk)281 dictkeys_incref(PyDictKeysObject *dk)
282 {
283 #ifdef Py_REF_DEBUG
284 _Py_RefTotal++;
285 #endif
286 dk->dk_refcnt++;
287 }
288
289 static inline void
dictkeys_decref(PyDictKeysObject * dk,const int decref_items)290 dictkeys_decref(PyDictKeysObject *dk, const int decref_items)
291 {
292 assert(dk->dk_refcnt > 0);
293 #ifdef Py_REF_DEBUG
294 _Py_RefTotal--;
295 #endif
296 if (--dk->dk_refcnt == 0) {
297 free_keys_object(dk, decref_items);
298 }
299 }
300
301 /* lookup indices. returns DKIX_EMPTY, DKIX_DUMMY, or ix >=0 */
302 static inline Py_ssize_t
dictkeys_get_index(const PyDictKeysObject * keys,Py_ssize_t i)303 dictkeys_get_index(const PyDictKeysObject *keys, Py_ssize_t i)
304 {
305 Py_ssize_t s = DK_SIZE(keys);
306 Py_ssize_t ix;
307
308 if (s <= 0xff) {
309 const int8_t *indices = (const int8_t*)(keys->dk_indices);
310 ix = indices[i];
311 }
312 else if (s <= 0xffff) {
313 const int16_t *indices = (const int16_t*)(keys->dk_indices);
314 ix = indices[i];
315 }
316 #if SIZEOF_VOID_P > 4
317 else if (s > 0xffffffff) {
318 const int64_t *indices = (const int64_t*)(keys->dk_indices);
319 ix = indices[i];
320 }
321 #endif
322 else {
323 const int32_t *indices = (const int32_t*)(keys->dk_indices);
324 ix = indices[i];
325 }
326 assert(ix >= DKIX_DUMMY);
327 return ix;
328 }
329
330 /* write to indices. */
331 static inline void
dictkeys_set_index(PyDictKeysObject * keys,Py_ssize_t i,Py_ssize_t ix)332 dictkeys_set_index(PyDictKeysObject *keys, Py_ssize_t i, Py_ssize_t ix)
333 {
334 Py_ssize_t s = DK_SIZE(keys);
335
336 assert(ix >= DKIX_DUMMY);
337
338 if (s <= 0xff) {
339 int8_t *indices = (int8_t*)(keys->dk_indices);
340 assert(ix <= 0x7f);
341 indices[i] = (char)ix;
342 }
343 else if (s <= 0xffff) {
344 int16_t *indices = (int16_t*)(keys->dk_indices);
345 assert(ix <= 0x7fff);
346 indices[i] = (int16_t)ix;
347 }
348 #if SIZEOF_VOID_P > 4
349 else if (s > 0xffffffff) {
350 int64_t *indices = (int64_t*)(keys->dk_indices);
351 indices[i] = ix;
352 }
353 #endif
354 else {
355 int32_t *indices = (int32_t*)(keys->dk_indices);
356 assert(ix <= 0x7fffffff);
357 indices[i] = (int32_t)ix;
358 }
359 }
360
361
362 /* USABLE_FRACTION is the maximum dictionary load.
363 * Increasing this ratio makes dictionaries more dense resulting in more
364 * collisions. Decreasing it improves sparseness at the expense of spreading
365 * indices over more cache lines and at the cost of total memory consumed.
366 *
367 * USABLE_FRACTION must obey the following:
368 * (0 < USABLE_FRACTION(n) < n) for all n >= 2
369 *
370 * USABLE_FRACTION should be quick to calculate.
371 * Fractions around 1/2 to 2/3 seem to work well in practice.
372 */
373 #define USABLE_FRACTION(n) (((n) << 1)/3)
374
375 /* Find the smallest dk_size >= minsize. */
376 static inline Py_ssize_t
calculate_keysize(Py_ssize_t minsize)377 calculate_keysize(Py_ssize_t minsize)
378 {
379 #if SIZEOF_LONG == SIZEOF_SIZE_T
380 minsize = (minsize | PyDict_MINSIZE) - 1;
381 return 1LL << _Py_bit_length(minsize | (PyDict_MINSIZE-1));
382 #elif defined(_MSC_VER)
383 // On 64bit Windows, sizeof(long) == 4.
384 minsize = (minsize | PyDict_MINSIZE) - 1;
385 unsigned long msb;
386 _BitScanReverse64(&msb, (uint64_t)minsize);
387 return 1LL << (msb + 1);
388 #else
389 Py_ssize_t size;
390 for (size = PyDict_MINSIZE;
391 size < minsize && size > 0;
392 size <<= 1)
393 ;
394 return size;
395 #endif
396 }
397
398 /* estimate_keysize is reverse function of USABLE_FRACTION.
399 *
400 * This can be used to reserve enough size to insert n entries without
401 * resizing.
402 */
403 static inline Py_ssize_t
estimate_keysize(Py_ssize_t n)404 estimate_keysize(Py_ssize_t n)
405 {
406 return calculate_keysize((n*3 + 1) / 2);
407 }
408
409
410 /* GROWTH_RATE. Growth rate upon hitting maximum load.
411 * Currently set to used*3.
412 * This means that dicts double in size when growing without deletions,
413 * but have more head room when the number of deletions is on a par with the
414 * number of insertions. See also bpo-17563 and bpo-33205.
415 *
416 * GROWTH_RATE was set to used*4 up to version 3.2.
417 * GROWTH_RATE was set to used*2 in version 3.3.0
418 * GROWTH_RATE was set to used*2 + capacity/2 in 3.4.0-3.6.0.
419 */
420 #define GROWTH_RATE(d) ((d)->ma_used*3)
421
422 /* This immutable, empty PyDictKeysObject is used for PyDict_Clear()
423 * (which cannot fail and thus can do no allocation).
424 */
425 static PyDictKeysObject empty_keys_struct = {
426 1, /* dk_refcnt */
427 1, /* dk_size */
428 lookdict_unicode_nodummy, /* dk_lookup */
429 0, /* dk_usable (immutable) */
430 0, /* dk_nentries */
431 {DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY,
432 DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY}, /* dk_indices */
433 };
434
435 static PyObject *empty_values[1] = { NULL };
436
437 #define Py_EMPTY_KEYS &empty_keys_struct
438
439 /* Uncomment to check the dict content in _PyDict_CheckConsistency() */
440 /* #define DEBUG_PYDICT */
441
442 #ifdef DEBUG_PYDICT
443 # define ASSERT_CONSISTENT(op) assert(_PyAnyDict_CheckConsistency((PyObject *)(op), 1))
444 #else
445 # define ASSERT_CONSISTENT(op) assert(_PyAnyDict_CheckConsistency((PyObject *)(op), 0))
446 #endif
447
448
449 int
_PyAnyDict_CheckConsistency(PyObject * op,int check_content)450 _PyAnyDict_CheckConsistency(PyObject *op, int check_content)
451 {
452 #define CHECK(expr) \
453 do { if (!(expr)) { _PyObject_ASSERT_FAILED_MSG(op, Py_STRINGIFY(expr)); } } while (0)
454
455 assert(op != NULL);
456 CHECK(PyAnyDict_Check(op));
457 PyDictObject *mp = (PyDictObject *)op;
458
459 PyDictKeysObject *keys = mp->ma_keys;
460 int splitted = _PyDict_HasSplitTable(mp);
461 Py_ssize_t usable = USABLE_FRACTION(keys->dk_size);
462
463 CHECK(0 <= mp->ma_used && mp->ma_used <= usable);
464 CHECK(IS_POWER_OF_2(keys->dk_size));
465 CHECK(0 <= keys->dk_usable && keys->dk_usable <= usable);
466 CHECK(0 <= keys->dk_nentries && keys->dk_nentries <= usable);
467 CHECK(keys->dk_usable + keys->dk_nentries <= usable);
468
469 if (!splitted) {
470 /* combined table */
471 CHECK(keys->dk_refcnt == 1);
472 }
473
474 if (check_content) {
475 PyDictKeyEntry *entries = DK_ENTRIES(keys);
476 Py_ssize_t i;
477
478 for (i=0; i < keys->dk_size; i++) {
479 Py_ssize_t ix = dictkeys_get_index(keys, i);
480 CHECK(DKIX_DUMMY <= ix && ix <= usable);
481 }
482
483 for (i=0; i < usable; i++) {
484 PyDictKeyEntry *entry = &entries[i];
485 PyObject *key = entry->me_key;
486
487 if (key != NULL) {
488 if (PyUnicode_CheckExact(key)) {
489 Py_hash_t hash = ((PyASCIIObject *)key)->hash;
490 CHECK(hash != -1);
491 CHECK(entry->me_hash == hash);
492 }
493 else {
494 /* test_dict fails if PyObject_Hash() is called again */
495 CHECK(entry->me_hash != -1);
496 }
497 if (!splitted) {
498 CHECK(entry->me_value != NULL);
499 }
500 }
501
502 if (splitted) {
503 CHECK(entry->me_value == NULL);
504 }
505 }
506
507 if (splitted) {
508 /* splitted table */
509 for (i=0; i < mp->ma_used; i++) {
510 CHECK(mp->ma_values[i] != NULL);
511 }
512 }
513 }
514 return 1;
515
516 #undef CHECK
517 }
518
519
520 static PyDictKeysObject*
new_keys_object(Py_ssize_t size)521 new_keys_object(Py_ssize_t size)
522 {
523 PyDictKeysObject *dk;
524 Py_ssize_t es, usable;
525
526 assert(size >= PyDict_MINSIZE);
527 assert(IS_POWER_OF_2(size));
528
529 usable = USABLE_FRACTION(size);
530 if (size <= 0xff) {
531 es = 1;
532 }
533 else if (size <= 0xffff) {
534 es = 2;
535 }
536 #if SIZEOF_VOID_P > 4
537 else if (size <= 0xffffffff) {
538 es = 4;
539 }
540 #endif
541 else {
542 es = sizeof(Py_ssize_t);
543 }
544
545 #if PyDict_MAXFREELIST > 0
546 if (size == PyDict_MINSIZE && numfreekeys > 0) {
547 dk = keys_free_list[--numfreekeys];
548 }
549 else
550 #endif
551 {
552 dk = PyObject_MALLOC(sizeof(PyDictKeysObject)
553 + es * size
554 + sizeof(PyDictKeyEntry) * usable);
555 if (dk == NULL) {
556 PyErr_NoMemory();
557 return NULL;
558 }
559 }
560 #ifdef Py_REF_DEBUG
561 _Py_RefTotal++;
562 #endif
563 dk->dk_refcnt = 1;
564 dk->dk_size = size;
565 dk->dk_usable = usable;
566 dk->dk_lookup = lookdict_unicode_nodummy;
567 dk->dk_nentries = 0;
568 memset(&dk->dk_indices[0], 0xff, es * size);
569 memset(DK_ENTRIES(dk), 0, sizeof(PyDictKeyEntry) * usable);
570 return dk;
571 }
572
573 static void
free_keys_object(PyDictKeysObject * keys,const int decref_items)574 free_keys_object(PyDictKeysObject *keys, const int decref_items)
575 {
576 if (decref_items) {
577 PyDictKeyEntry *entries = DK_ENTRIES(keys);
578 Py_ssize_t i, n;
579 for (i = 0, n = keys->dk_nentries; i < n; i++) {
580 Py_XDECREF(entries[i].me_key);
581 Py_XDECREF(entries[i].me_value);
582 }
583 }
584
585 #if PyDict_MAXFREELIST > 0
586 if (keys->dk_size == PyDict_MINSIZE && numfreekeys < PyDict_MAXFREELIST) {
587 keys_free_list[numfreekeys++] = keys;
588 return;
589 }
590 #endif
591 PyObject_FREE(keys);
592 }
593
594 #define new_values(size) PyMem_NEW(PyObject *, size)
595 #define free_values(values) PyMem_FREE(values)
596
597 static PyDictKeysObject *
clone_combined_dict_keys(PyDictObject * orig)598 clone_combined_dict_keys(PyDictObject *orig)
599 {
600 assert(PyAnyDict_Check(orig));
601 assert(
602 Py_TYPE(orig)->tp_iter == (getiterfunc)dict_iter
603 || Py_TYPE(orig)->tp_iter == (getiterfunc)frozendict_iter
604 );
605 assert(orig->ma_values == NULL);
606 assert(orig->ma_keys->dk_refcnt == 1);
607
608 Py_ssize_t keys_size = _PyDict_KeysSize(orig->ma_keys);
609 PyDictKeysObject *keys = PyObject_Malloc(keys_size);
610 if (keys == NULL) {
611 PyErr_NoMemory();
612 return NULL;
613 }
614
615 memcpy(keys, orig->ma_keys, keys_size);
616
617 /* After copying key/value pairs, we need to incref all
618 keys and values and they are about to be co-owned by a
619 new dict object. */
620 PyDictKeyEntry *ep0 = DK_ENTRIES(keys);
621 Py_ssize_t n = keys->dk_nentries;
622 for (Py_ssize_t i = 0; i < n; i++) {
623 PyDictKeyEntry *entry = &ep0[i];
624 PyObject *value = entry->me_value;
625 if (value != NULL) {
626 Py_INCREF(value);
627 Py_INCREF(entry->me_key);
628 }
629 }
630
631 /* Since we copied the keys table we now have an extra reference
632 in the system. Manually call increment _Py_RefTotal to signal that
633 we have it now; calling dictkeys_incref would be an error as
634 keys->dk_refcnt is already set to 1 (after memcpy). */
635 #ifdef Py_REF_DEBUG
636 _Py_RefTotal++;
637 #endif
638 return keys;
639 }
640
641 /*
642 The basic lookup function used by all operations.
643 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
644 Open addressing is preferred over chaining since the link overhead for
645 chaining would be substantial (100% with typical malloc overhead).
646
647 The initial probe index is computed as hash mod the table size. Subsequent
648 probe indices are computed as explained earlier.
649
650 All arithmetic on hash should ignore overflow.
651
652 The details in this version are due to Tim Peters, building on many past
653 contributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and
654 Christian Tismer.
655
656 lookdict() is general-purpose, and may return DKIX_ERROR if (and only if) a
657 comparison raises an exception.
658 lookdict_unicode() below is specialized to string keys, comparison of which can
659 never raise an exception; that function can never return DKIX_ERROR when key
660 is string. Otherwise, it falls back to lookdict().
661 lookdict_unicode_nodummy is further specialized for string keys that cannot be
662 the <dummy> value.
663 For both, when the key isn't found a DKIX_EMPTY is returned.
664 */
665 static Py_ssize_t _Py_HOT_FUNCTION
lookdict(PyDictObject * mp,PyObject * key,Py_hash_t hash,PyObject ** value_addr)666 lookdict(PyDictObject *mp, PyObject *key,
667 Py_hash_t hash, PyObject **value_addr)
668 {
669 size_t i, mask, perturb;
670 PyDictKeysObject *dk;
671 PyDictKeyEntry *ep0;
672
673 top:
674 dk = mp->ma_keys;
675 ep0 = DK_ENTRIES(dk);
676 mask = DK_MASK(dk);
677 perturb = hash;
678 i = (size_t)hash & mask;
679
680 for (;;) {
681 Py_ssize_t ix = dictkeys_get_index(dk, i);
682 if (ix == DKIX_EMPTY) {
683 *value_addr = NULL;
684 return ix;
685 }
686 if (ix >= 0) {
687 PyDictKeyEntry *ep = &ep0[ix];
688 assert(ep->me_key != NULL);
689 if (ep->me_key == key) {
690 *value_addr = ep->me_value;
691 return ix;
692 }
693 if (ep->me_hash == hash) {
694 PyObject *startkey = ep->me_key;
695 Py_INCREF(startkey);
696 int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
697 Py_DECREF(startkey);
698 if (cmp < 0) {
699 *value_addr = NULL;
700 return DKIX_ERROR;
701 }
702 if (dk == mp->ma_keys && ep->me_key == startkey) {
703 if (cmp > 0) {
704 *value_addr = ep->me_value;
705 return ix;
706 }
707 }
708 else {
709 /* The dict was mutated, restart */
710 goto top;
711 }
712 }
713 }
714 perturb >>= PERTURB_SHIFT;
715 i = (i*5 + perturb + 1) & mask;
716 }
717 Py_UNREACHABLE();
718 }
719
720 /* Faster version of lookdict_unicode when it is known that no <dummy> keys
721 * will be present. */
722 static Py_ssize_t _Py_HOT_FUNCTION
lookdict_unicode_nodummy(PyDictObject * mp,PyObject * key,Py_hash_t hash,PyObject ** value_addr)723 lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
724 Py_hash_t hash, PyObject **value_addr)
725 {
726 assert(mp->ma_values == NULL);
727 /* Make sure this function doesn't have to handle non-unicode keys,
728 including subclasses of str; e.g., one reason to subclass
729 unicodes is to override __eq__, and for speed we don't cater to
730 that here. */
731 if (!PyUnicode_CheckExact(key)) {
732 mp->ma_keys->dk_lookup = lookdict;
733 return lookdict(mp, key, hash, value_addr);
734 }
735
736 PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
737 size_t mask = DK_MASK(mp->ma_keys);
738 size_t perturb = (size_t)hash;
739 size_t i = (size_t)hash & mask;
740
741 for (;;) {
742 Py_ssize_t ix = dictkeys_get_index(mp->ma_keys, i);
743 assert (ix != DKIX_DUMMY);
744 if (ix == DKIX_EMPTY) {
745 *value_addr = NULL;
746 return DKIX_EMPTY;
747 }
748 PyDictKeyEntry *ep = &ep0[ix];
749 assert(ep->me_key != NULL);
750 assert(PyUnicode_CheckExact(ep->me_key));
751 if (ep->me_key == key ||
752 (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
753 *value_addr = ep->me_value;
754 return ix;
755 }
756 perturb >>= PERTURB_SHIFT;
757 i = mask & (i*5 + perturb + 1);
758 }
759 Py_UNREACHABLE();
760 }
761
762 #define MAINTAIN_TRACKING(mp, key, value) \
763 do { \
764 if (!_PyObject_GC_IS_TRACKED(mp)) { \
765 if (_PyObject_GC_MAY_BE_TRACKED(key) || \
766 _PyObject_GC_MAY_BE_TRACKED(value)) { \
767 _PyObject_GC_TRACK(mp); \
768 } \
769 } \
770 } while(0)
771
772 /* Internal function to find slot for an item from its hash
773 when it is known that the key is not present in the dict.
774
775 The dict must be combined. */
776 static Py_ssize_t
find_empty_slot(PyDictKeysObject * keys,Py_hash_t hash)777 find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash)
778 {
779 assert(keys != NULL);
780
781 const size_t mask = DK_MASK(keys);
782 size_t i = hash & mask;
783 Py_ssize_t ix = dictkeys_get_index(keys, i);
784 for (size_t perturb = hash; ix >= 0;) {
785 perturb >>= PERTURB_SHIFT;
786 i = (i*5 + perturb + 1) & mask;
787 ix = dictkeys_get_index(keys, i);
788 }
789 return i;
790 }
791
792 /*
793 Internal routine used by dictresize() to build a hashtable of entries.
794 */
795 static void
build_indices(PyDictKeysObject * keys,PyDictKeyEntry * ep,Py_ssize_t n)796 build_indices(PyDictKeysObject *keys, PyDictKeyEntry *ep, Py_ssize_t n)
797 {
798 size_t mask = (size_t)DK_SIZE(keys) - 1;
799 for (Py_ssize_t ix = 0; ix != n; ix++, ep++) {
800 Py_hash_t hash = ep->me_hash;
801 size_t i = hash & mask;
802 for (size_t perturb = hash; dictkeys_get_index(keys, i) != DKIX_EMPTY;) {
803 perturb >>= PERTURB_SHIFT;
804 i = mask & (i*5 + perturb + 1);
805 }
806 dictkeys_set_index(keys, i, ix);
807 }
808 }
809
frozendict_resize(PyDictObject * mp,Py_ssize_t minsize)810 static int frozendict_resize(PyDictObject* mp, Py_ssize_t minsize) {
811 const Py_ssize_t newsize = calculate_keysize(minsize);
812
813 if (newsize <= 0) {
814 PyErr_NoMemory();
815 return -1;
816 }
817
818 assert(IS_POWER_OF_2(newsize));
819 assert(newsize >= PyDict_MINSIZE);
820
821 PyDictKeysObject* oldkeys = mp->ma_keys;
822
823 /* Allocate a new table. */
824 PyDictKeysObject* new_keys = new_keys_object(newsize);
825
826 if (new_keys == NULL) {
827 return -1;
828 }
829
830 // New table must be large enough.
831 assert(new_keys->dk_usable >= mp->ma_used);
832
833 new_keys->dk_lookup = oldkeys->dk_lookup;
834
835 const Py_ssize_t numentries = mp->ma_used;
836 PyDictKeyEntry* newentries = DK_ENTRIES(new_keys);
837
838 memcpy(
839 newentries,
840 DK_ENTRIES(oldkeys),
841 numentries * sizeof(PyDictKeyEntry)
842 );
843
844 build_indices(new_keys, newentries, numentries);
845 new_keys->dk_usable -= numentries;
846 new_keys->dk_nentries = numentries;
847
848 // do not decref the keys inside!
849 dictkeys_decref(oldkeys, 0);
850
851 mp->ma_keys = new_keys;
852
853 return 0;
854 }
855
frozendict_insert(PyDictObject * mp,PyObject * key,const Py_hash_t hash,PyObject * value,int empty)856 static int frozendict_insert(PyDictObject *mp,
857 PyObject *key,
858 const Py_hash_t hash,
859 PyObject *value,
860 int empty) {
861 Py_ssize_t ix;
862 PyObject *old_value;
863 PyDictKeysObject* keys = mp->ma_keys;
864
865 Py_INCREF(key);
866 Py_INCREF(value);
867 MAINTAIN_TRACKING(mp, key, value);
868
869 if (! empty) {
870 ix = keys->dk_lookup(mp, key, hash, &old_value);
871
872 if (ix == DKIX_ERROR) {
873 Py_DECREF(value);
874 Py_DECREF(key);
875 return -1;
876 }
877
878 empty = (ix == DKIX_EMPTY);
879 }
880
881 if (empty) {
882 /* Insert into new slot. */
883
884 if (mp->ma_keys->dk_usable <= 0) {
885 /* Need to resize. */
886 if (frozendict_resize(mp, GROWTH_RATE(mp))) {
887 Py_DECREF(value);
888 Py_DECREF(key);
889 return -1;
890 }
891
892 // resize changes keys
893 keys = mp->ma_keys;
894 }
895
896 const Py_ssize_t hashpos = find_empty_slot(keys, hash);
897 const Py_ssize_t dk_nentries = keys->dk_nentries;
898 PyDictKeyEntry* ep = &DK_ENTRIES(keys)[dk_nentries];
899 dictkeys_set_index(keys, hashpos, dk_nentries);
900 ep->me_key = key;
901 ep->me_hash = hash;
902 ep->me_value = value;
903 mp->ma_used++;
904 keys->dk_usable--;
905 keys->dk_nentries++;
906 assert(keys->dk_usable >= 0);
907 }
908 else {
909 DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
910 Py_DECREF(old_value); /* which **CAN** re-enter (see issue #22653) */
911 Py_DECREF(key);
912 }
913
914 ASSERT_CONSISTENT(mp);
915 return 0;
916 }
917
frozendict_setitem(PyObject * op,PyObject * key,PyObject * value,int empty)918 static int frozendict_setitem(PyObject *op,
919 PyObject *key,
920 PyObject *value,
921 int empty) {
922 Py_hash_t hash;
923
924 assert(key);
925 assert(value);
926
927 if (!PyUnicode_CheckExact(key) ||
928 (hash = ((PyASCIIObject *) key)->hash) == -1) {
929 hash = PyObject_Hash(key);
930
931 if (hash == -1) {
932 return -1;
933 }
934 }
935 return frozendict_insert((PyDictObject*) op, key, hash, value, empty);
936 }
937
_PyFrozendict_SetItem(PyObject * op,PyObject * key,PyObject * value,int empty)938 int _PyFrozendict_SetItem(PyObject *op,
939 PyObject *key,
940 PyObject *value,
941 int empty) {
942 if (! PyAnyFrozenDict_Check(op)) {
943 PyErr_BadInternalCall();
944 return -1;
945 }
946
947 return frozendict_setitem(op, key, value, empty);
948 }
949
950 /* Internal version of frozendict_next that returns a hash value in addition
951 * to the key and value.
952 * Return 1 on success, return 0 when the reached the end of the dictionary
953 * (or if op is not a dictionary)
954 */
955 static int
_frozendict_next(PyObject * op,Py_ssize_t * ppos,PyObject ** pkey,PyObject ** pvalue,Py_hash_t * phash)956 _frozendict_next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey,
957 PyObject **pvalue, Py_hash_t *phash)
958 {
959 Py_ssize_t i;
960 PyDictObject *mp;
961 PyDictKeyEntry *entry_ptr;
962 PyObject *value;
963
964 if (!PyAnyDict_Check(op))
965 return 0;
966 mp = (PyDictObject *)op;
967 i = *ppos;
968 if (mp->ma_values) {
969 if (i < 0 || i >= mp->ma_used)
970 return 0;
971 /* values of split table is always dense */
972 entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
973 value = mp->ma_values[i];
974 assert(value != NULL);
975 }
976 else {
977 Py_ssize_t n = mp->ma_keys->dk_nentries;
978 if (i < 0 || i >= n)
979 return 0;
980 entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
981 while (i < n && entry_ptr->me_value == NULL) {
982 entry_ptr++;
983 i++;
984 }
985 if (i >= n)
986 return 0;
987 value = entry_ptr->me_value;
988 }
989 *ppos = i+1;
990 if (pkey)
991 *pkey = entry_ptr->me_key;
992 if (phash)
993 *phash = entry_ptr->me_hash;
994 if (pvalue)
995 *pvalue = value;
996 return 1;
997 }
998
999 /*
1000 * Iterate over a frozendict. Use like so:
1001 *
1002 * Py_ssize_t i;
1003 * PyObject *key, *value;
1004 * i = 0; # important! i should not otherwise be changed by you
1005 * while (frozendict_next(yourdict, &i, &key, &value)) {
1006 * Refer to borrowed references in key and value.
1007 * }
1008 *
1009 * Return 1 on success, return 0 when the reached the end of the dictionary
1010 * (or if op is not a dictionary)
1011 *
1012 * CAUTION: In general, it isn't safe to use frozendict_next in a loop that
1013 * mutates the dict. One exception: it is safe if the loop merely changes
1014 * the values associated with the keys (but doesn't insert new keys or
1015 * delete keys), via _PyFrozendict_SetItem().
1016 */
1017 static int
frozendict_next(PyObject * op,Py_ssize_t * ppos,PyObject ** pkey,PyObject ** pvalue)1018 frozendict_next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue)
1019 {
1020 return _frozendict_next(op, ppos, pkey, pvalue, NULL);
1021 }
1022
1023 // empty frozendict singleton
1024 static PyObject* empty_frozendict = NULL;
1025
1026 static PyObject *
dict_iter(PyDictObject * dict)1027 dict_iter(PyDictObject *dict)
1028 {
1029 return dictiter_new(dict, &PyDictIterKey_Type);
1030 }
1031
1032 static PyObject* _frozendict_new(
1033 PyTypeObject* type,
1034 PyObject* args,
1035 PyObject* kwds,
1036 const int use_empty_frozendict
1037 );
1038
1039 /* Internal version of dict.from_keys(). It is subclass-friendly. */
1040 static PyObject *
frozendict_fromkeys_impl(PyObject * type,PyObject * iterable,PyObject * value)1041 frozendict_fromkeys_impl(PyObject *type, PyObject *iterable, PyObject *value)
1042 {
1043 PyObject *it; /* iter(iterable) */
1044 PyObject *key;
1045 PyObject *d;
1046 int status;
1047
1048 d = _frozendict_new(&PyFrozenDict_Type, NULL, NULL, 0);
1049
1050 if (d == NULL)
1051 return NULL;
1052
1053 Py_ssize_t size;
1054 PyDictObject *mp = (PyDictObject *)d;
1055 mp->ma_keys = new_keys_object(PyDict_MINSIZE);
1056
1057 if (PyAnyDict_CheckExact(iterable)) {
1058 PyObject *oldvalue;
1059 Py_ssize_t pos = 0;
1060 PyObject *key;
1061 Py_hash_t hash;
1062
1063 size = PyDict_GET_SIZE(iterable);
1064
1065 if (mp->ma_keys->dk_usable < size) {
1066 if (frozendict_resize(mp, estimate_keysize(size))) {
1067 Py_DECREF(d);
1068 return NULL;
1069 }
1070 }
1071
1072 while (_PyDict_Next(iterable, &pos, &key, &oldvalue, &hash)) {
1073 if (frozendict_insert(mp, key, hash, value, 0)) {
1074 Py_DECREF(d);
1075 return NULL;
1076 }
1077 }
1078 return d;
1079 }
1080 else if (PyAnySet_CheckExact(iterable)) {
1081 Py_ssize_t pos = 0;
1082 PyObject *key;
1083 Py_hash_t hash;
1084
1085 size = PySet_GET_SIZE(iterable);
1086
1087 if (mp->ma_keys->dk_usable < size) {
1088 if (frozendict_resize(mp, estimate_keysize(size))) {
1089 Py_DECREF(d);
1090 return NULL;
1091 }
1092 }
1093
1094 while (_PySet_NextEntry(iterable, &pos, &key, &hash)) {
1095 if (frozendict_insert(mp, key, hash, value, 0)) {
1096 Py_DECREF(d);
1097 return NULL;
1098 }
1099 }
1100 }
1101 else {
1102 it = PyObject_GetIter(iterable);
1103 if (it == NULL){
1104 Py_DECREF(d);
1105 return NULL;
1106 }
1107
1108 while ((key = PyIter_Next(it)) != NULL) {
1109 status = frozendict_setitem(d, key, value, 0);
1110 Py_DECREF(key);
1111 if (status < 0) {
1112 Py_DECREF(it);
1113 Py_DECREF(d);
1114 return NULL;
1115 }
1116 }
1117
1118 Py_DECREF(it);
1119
1120 if (PyErr_Occurred()) {
1121 Py_DECREF(d);
1122 return NULL;
1123 }
1124 }
1125
1126 ASSERT_CONSISTENT(mp);
1127
1128 if ((PyTypeObject*) type == &PyFrozenDict_Type || (PyTypeObject*) type == &PyCoold_Type) {
1129 return d;
1130 }
1131
1132 PyObject* args = PyTuple_New(1);
1133
1134 if (args == NULL) {
1135 Py_DECREF(d);
1136 return NULL;
1137 }
1138
1139 PyTuple_SET_ITEM(args, 0, d);
1140
1141 return PyObject_Call(type, args, NULL);
1142 }
1143
1144 static PyObject *
frozendict_fromkeys(PyTypeObject * type,PyObject * const * args,Py_ssize_t nargs)1145 frozendict_fromkeys(PyTypeObject *type, PyObject *const *args, Py_ssize_t nargs)
1146 {
1147 PyObject *return_value = NULL;
1148 PyObject *iterable;
1149 PyObject *value = Py_None;
1150
1151 if (!_PyArg_CheckPositional("fromkeys", nargs, 1, 2)) {
1152 goto exit;
1153 }
1154 iterable = args[0];
1155 if (nargs < 2) {
1156 goto skip_optional;
1157 }
1158 value = args[1];
1159 skip_optional:
1160 return_value = frozendict_fromkeys_impl((PyObject *)type, iterable, value);
1161
1162 exit:
1163 return return_value;
1164 }
1165
1166 /* Methods */
1167
1168 static void
dict_dealloc(PyDictObject * mp)1169 dict_dealloc(PyDictObject *mp)
1170 {
1171 PyObject **values = mp->ma_values;
1172 PyDictKeysObject *keys = mp->ma_keys;
1173 Py_ssize_t i, n;
1174
1175 /* bpo-31095: UnTrack is needed before calling any callbacks */
1176 PyObject_GC_UnTrack(mp);
1177 Py_TRASHCAN_BEGIN(mp, dict_dealloc)
1178 if (values != NULL) {
1179 if (values != empty_values) {
1180 for (i = 0, n = mp->ma_keys->dk_nentries; i < n; i++) {
1181 Py_XDECREF(values[i]);
1182 }
1183 free_values(values);
1184 }
1185 dictkeys_decref(keys, 1);
1186 }
1187 else if (keys != NULL) {
1188 assert(keys->dk_refcnt == 1);
1189 dictkeys_decref(keys, 1);
1190 }
1191 #if PyDict_MAXFREELIST > 0
1192 if (numfree < PyDict_MAXFREELIST && Py_IS_TYPE(mp, &PyDict_Type)) {
1193 free_list[numfree++] = mp;
1194 }
1195 else
1196 #endif
1197 {
1198 Py_TYPE(mp)->tp_free((PyObject *)mp);
1199 }
1200 Py_TRASHCAN_END
1201 }
1202
1203
1204 static PyObject *
dict_repr(PyDictObject * mp)1205 dict_repr(PyDictObject *mp)
1206 {
1207 Py_ssize_t i;
1208 PyObject *key = NULL, *value = NULL;
1209 _PyUnicodeWriter writer;
1210 int first;
1211
1212 i = Py_ReprEnter((PyObject *)mp);
1213 if (i != 0) {
1214 return i > 0 ? PyUnicode_FromString("{...}") : NULL;
1215 }
1216
1217 if (mp->ma_used == 0) {
1218 Py_ReprLeave((PyObject *)mp);
1219 return PyUnicode_FromString("{}");
1220 }
1221
1222 _PyUnicodeWriter_Init(&writer);
1223 writer.overallocate = 1;
1224 /* "{" + "1: 2" + ", 3: 4" * (len - 1) + "}" */
1225 writer.min_length = 1 + 4 + (2 + 4) * (mp->ma_used - 1) + 1;
1226
1227 if (_PyUnicodeWriter_WriteChar(&writer, '{') < 0)
1228 goto error;
1229
1230 /* Do repr() on each key+value pair, and insert ": " between them.
1231 Note that repr may mutate the dict. */
1232 i = 0;
1233 first = 1;
1234 while (frozendict_next((PyObject *)mp, &i, &key, &value)) {
1235 PyObject *s;
1236 int res;
1237
1238 /* Prevent repr from deleting key or value during key format. */
1239 Py_INCREF(key);
1240 Py_INCREF(value);
1241
1242 if (!first) {
1243 if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)
1244 goto error;
1245 }
1246 first = 0;
1247
1248 s = PyObject_Repr(key);
1249 if (s == NULL)
1250 goto error;
1251 res = _PyUnicodeWriter_WriteStr(&writer, s);
1252 Py_DECREF(s);
1253 if (res < 0)
1254 goto error;
1255
1256 if (_PyUnicodeWriter_WriteASCIIString(&writer, ": ", 2) < 0)
1257 goto error;
1258
1259 s = PyObject_Repr(value);
1260 if (s == NULL)
1261 goto error;
1262 res = _PyUnicodeWriter_WriteStr(&writer, s);
1263 Py_DECREF(s);
1264 if (res < 0)
1265 goto error;
1266
1267 Py_CLEAR(key);
1268 Py_CLEAR(value);
1269 }
1270
1271 writer.overallocate = 0;
1272 if (_PyUnicodeWriter_WriteChar(&writer, '}') < 0)
1273 goto error;
1274
1275 Py_ReprLeave((PyObject *)mp);
1276
1277 return _PyUnicodeWriter_Finish(&writer);
1278
1279 error:
1280 Py_ReprLeave((PyObject *)mp);
1281 _PyUnicodeWriter_Dealloc(&writer);
1282 Py_XDECREF(key);
1283 Py_XDECREF(value);
1284 return NULL;
1285 }
1286
1287 #define REPR_GENERIC_START "("
1288 #define REPR_GENERIC_END ")"
1289 #define FROZENDICT_CLASS_NAME "frozendict"
1290 #define COOLD_CLASS_NAME "coold"
1291
1292 size_t REPR_GENERIC_START_LEN = strlen(REPR_GENERIC_START);
1293 size_t REPR_GENERIC_END_LEN = strlen(REPR_GENERIC_END);
1294
frozendict_repr(PyFrozenDictObject * mp)1295 static PyObject* frozendict_repr(PyFrozenDictObject* mp) {
1296 PyObject* dict_repr_res = dict_repr((PyDictObject*) mp);
1297
1298 if (dict_repr_res == NULL) {
1299 return NULL;
1300 }
1301
1302 _PyUnicodeWriter writer;
1303 _PyUnicodeWriter_Init(&writer);
1304
1305 int error = 0;
1306
1307 PyObject* o = (PyObject*) mp;
1308
1309 Py_ReprEnter(o);
1310
1311 PyTypeObject* type = Py_TYPE(mp);
1312 size_t frozendict_name_len = strlen(type->tp_name);
1313
1314 writer.min_length = (
1315 frozendict_name_len +
1316 REPR_GENERIC_START_LEN +
1317 PyObject_Length(dict_repr_res) +
1318 REPR_GENERIC_END_LEN
1319 );
1320
1321 if (_PyUnicodeWriter_WriteASCIIString(
1322 &writer,
1323 type->tp_name,
1324 frozendict_name_len
1325 )) {
1326 error = 1;
1327 }
1328 else {
1329 if (_PyUnicodeWriter_WriteASCIIString(
1330 &writer,
1331 REPR_GENERIC_START,
1332 REPR_GENERIC_START_LEN
1333 )) {
1334 error = 1;
1335 }
1336 else {
1337 if (_PyUnicodeWriter_WriteStr(&writer, dict_repr_res)) {
1338 error = 1;
1339 }
1340 else {
1341 error = _PyUnicodeWriter_WriteASCIIString(
1342 &writer,
1343 REPR_GENERIC_END,
1344 REPR_GENERIC_END_LEN
1345 );
1346 }
1347 }
1348 }
1349
1350 Py_ReprLeave(o);
1351
1352 if (error) {
1353 _PyUnicodeWriter_Dealloc(&writer);
1354 return NULL;
1355 }
1356
1357 return _PyUnicodeWriter_Finish(&writer);
1358 }
1359
1360 static Py_ssize_t
dict_length(PyDictObject * mp)1361 dict_length(PyDictObject *mp)
1362 {
1363 return mp->ma_used;
1364 }
1365
1366 static PyObject *
dict_subscript(PyDictObject * mp,PyObject * key)1367 dict_subscript(PyDictObject *mp, PyObject *key)
1368 {
1369 Py_ssize_t ix;
1370 Py_hash_t hash;
1371 PyObject *value;
1372
1373 if (!PyUnicode_CheckExact(key) ||
1374 (hash = ((PyASCIIObject *) key)->hash) == -1) {
1375 hash = PyObject_Hash(key);
1376 if (hash == -1)
1377 return NULL;
1378 }
1379 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
1380 if (ix == DKIX_ERROR)
1381 return NULL;
1382 if (ix == DKIX_EMPTY || value == NULL) {
1383 if (!PyAnyDict_CheckExact(mp)) {
1384 /* Look up __missing__ method if we're a subclass. */
1385 PyObject *missing, *res;
1386 _Py_IDENTIFIER(__missing__);
1387 missing = _PyObject_LookupSpecial((PyObject *)mp, &PyId___missing__);
1388 if (missing != NULL) {
1389 res = PyObject_CallOneArg(missing, key);
1390 Py_DECREF(missing);
1391 return res;
1392 }
1393 else if (PyErr_Occurred())
1394 return NULL;
1395 }
1396 _PyErr_SetKeyError(key);
1397 return NULL;
1398 }
1399 Py_INCREF(value);
1400 return value;
1401 }
1402
1403 static PyMappingMethods frozendict_as_mapping = {
1404 (lenfunc)dict_length, /*mp_length*/
1405 (binaryfunc)dict_subscript, /*mp_subscript*/
1406 };
1407
frozendict_merge(PyObject * a,PyObject * b,int empty)1408 static int frozendict_merge(PyObject* a, PyObject* b, int empty) {
1409 /* We accept for the argument either a concrete dictionary object,
1410 * or an abstract "mapping" object. For the former, we can do
1411 * things quite efficiently. For the latter, we only require that
1412 * PyMapping_Keys() and PyObject_GetItem() be supported.
1413 */
1414 assert(a != NULL);
1415 assert(PyAnyFrozenDict_Check(a));
1416 assert(b != NULL);
1417
1418 PyDictObject* mp = (PyDictObject*) a;
1419
1420 if (
1421 PyAnyDict_Check(b) &&
1422 (
1423 Py_TYPE(b)->tp_iter == (getiterfunc)dict_iter ||
1424 Py_TYPE(b)->tp_iter == (getiterfunc)frozendict_iter
1425 )
1426 ) {
1427 PyDictObject* other = (PyDictObject*)b;
1428 const Py_ssize_t numentries = other->ma_used;
1429
1430 if (other == mp || numentries == 0) {
1431 /* a.update(a) or a.update({}); nothing to do */
1432 return 0;
1433 }
1434
1435 const int is_other_combined = other->ma_values == NULL;
1436
1437 PyDictKeysObject* okeys = other->ma_keys;
1438
1439 if (
1440 empty
1441 && is_other_combined
1442 && numentries == okeys->dk_nentries
1443 && (
1444 okeys->dk_size == PyDict_MINSIZE
1445 || USABLE_FRACTION(okeys->dk_size/2) < other->ma_used
1446 )
1447 ) {
1448 PyDictKeysObject *keys = clone_combined_dict_keys(other);
1449 if (keys == NULL) {
1450 return -1;
1451 }
1452
1453 mp->ma_keys = keys;
1454
1455 mp->ma_used = numentries;
1456 mp->ma_version_tag = DICT_NEXT_VERSION();
1457 ASSERT_CONSISTENT(mp);
1458
1459 if (_PyObject_GC_IS_TRACKED(other) && !_PyObject_GC_IS_TRACKED(mp)) {
1460 _PyObject_GC_TRACK(mp);
1461 }
1462
1463 return 0;
1464 }
1465
1466 PyDictKeyEntry* ep0 = DK_ENTRIES(okeys);
1467 PyDictKeyEntry* entry;
1468 PyObject* key;
1469 PyObject* value;
1470 Py_hash_t hash;
1471 int err;
1472
1473 if (mp->ma_keys == NULL) {
1474 mp->ma_keys = new_keys_object(PyDict_MINSIZE);
1475 }
1476
1477 /* Do one big resize at the start, rather than
1478 * incrementally resizing as we insert new items. Expect
1479 * that there will be no (or few) overlapping keys.
1480 */
1481 if (mp->ma_keys->dk_usable < numentries) {
1482 if (frozendict_resize(mp, estimate_keysize(mp->ma_used + numentries))) {
1483 return -1;
1484 }
1485 }
1486
1487 for (Py_ssize_t i = 0, n = okeys->dk_nentries; i < n; i++) {
1488 entry = &ep0[i];
1489 key = entry->me_key;
1490 hash = entry->me_hash;
1491
1492 if (is_other_combined) {
1493 value = entry->me_value;
1494 }
1495 else {
1496 value = other->ma_values[i];
1497 }
1498
1499 if (value != NULL) {
1500 Py_INCREF(key);
1501 Py_INCREF(value);
1502 err = frozendict_insert(mp, key, hash, value, empty);
1503 Py_DECREF(value);
1504 Py_DECREF(key);
1505
1506 if (err != 0) {
1507 return -1;
1508 }
1509
1510 if (n != other->ma_keys->dk_nentries) {
1511 PyErr_SetString(PyExc_RuntimeError,
1512 "dict mutated during update");
1513 return -1;
1514 }
1515 }
1516 }
1517 }
1518 else {
1519 /* Do it the generic, slower way */
1520 PyObject *keys = PyMapping_Keys(b);
1521 PyObject *iter;
1522 PyObject *key, *value;
1523 int status;
1524
1525 if (mp->ma_keys == NULL) {
1526 mp->ma_keys = new_keys_object(PyDict_MINSIZE);
1527 }
1528
1529 if (keys == NULL)
1530 /* Docstring says this is equivalent to E.keys() so
1531 * if E doesn't have a .keys() method we want
1532 * AttributeError to percolate up. Might as well
1533 * do the same for any other error.
1534 */
1535 return -1;
1536
1537 iter = PyObject_GetIter(keys);
1538 Py_DECREF(keys);
1539 if (iter == NULL)
1540 return -1;
1541
1542 for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) {
1543 value = PyObject_GetItem(b, key);
1544 if (value == NULL) {
1545 Py_DECREF(iter);
1546 Py_DECREF(key);
1547 return -1;
1548 }
1549 status = frozendict_setitem(a, key, value, 0);
1550 Py_DECREF(key);
1551 Py_DECREF(value);
1552 if (status < 0) {
1553 Py_DECREF(iter);
1554 return -1;
1555 }
1556 }
1557 Py_DECREF(iter);
1558 if (PyErr_Occurred())
1559 /* Iterator completed, via error */
1560 return -1;
1561 }
1562 ASSERT_CONSISTENT(a);
1563 return 0;
1564 }
1565
frozendict_merge_from_seq2(PyObject * d,PyObject * seq2)1566 static int frozendict_merge_from_seq2(PyObject* d, PyObject* seq2) {
1567 assert(d != NULL);
1568 assert(PyAnyFrozenDict_Check(d));
1569 assert(seq2 != NULL);
1570
1571 PyObject* it = PyObject_GetIter(seq2);
1572
1573 if (it == NULL) {
1574 return -1;
1575 }
1576
1577 PyObject* fast; /* item as a 2-tuple or 2-list */
1578 PyObject* key = NULL;
1579 PyObject* value = NULL;
1580 Py_ssize_t n;
1581 PyObject* item;
1582 int res = 0;
1583
1584 PyDictObject* mp = (PyDictObject*) d;
1585
1586 if (mp->ma_keys == NULL) {
1587 mp->ma_keys = new_keys_object(PyDict_MINSIZE);
1588 }
1589
1590 for (Py_ssize_t i = 0; ; ++i) {
1591 fast = NULL;
1592 item = PyIter_Next(it);
1593
1594 if (item == NULL) {
1595 if (PyErr_Occurred()) {
1596 res = -1;
1597 }
1598
1599 break;
1600 }
1601
1602 /* Convert item to sequence, and verify length 2. */
1603 fast = PySequence_Fast(item, "");
1604
1605 if (fast == NULL) {
1606 if (PyErr_ExceptionMatches(PyExc_TypeError)) {
1607 PyErr_Format(PyExc_TypeError,
1608 "cannot convert dictionary update "
1609 "sequence element #%zd to a sequence",
1610 i);
1611 }
1612 Py_DECREF(item);
1613 res = -1;
1614 break;
1615 }
1616
1617 n = PySequence_Fast_GET_SIZE(fast);
1618
1619 if (n != 2) {
1620 PyErr_Format(PyExc_ValueError,
1621 "dictionary update sequence element #%zd "
1622 "has length %zd; 2 is required",
1623 i, n);
1624 Py_DECREF(fast);
1625 Py_DECREF(item);
1626 res = -1;
1627 break;
1628 }
1629
1630 /* Update/merge with this (key, value) pair. */
1631 key = PySequence_Fast_GET_ITEM(fast, 0);
1632 Py_INCREF(key);
1633 value = PySequence_Fast_GET_ITEM(fast, 1);
1634 Py_INCREF(value);
1635
1636 if (frozendict_setitem(d, key, value, 0) < 0) {
1637 Py_DECREF(key);
1638 Py_DECREF(value);
1639 Py_DECREF(fast);
1640 Py_DECREF(item);
1641 res = -1;
1642 break;
1643 }
1644
1645 Py_DECREF(key);
1646 Py_DECREF(value);
1647 Py_DECREF(fast);
1648 Py_DECREF(item);
1649 }
1650
1651 Py_DECREF(it);
1652 ASSERT_CONSISTENT(d);
1653 return res;
1654 }
1655
frozendict_update_arg(PyObject * self,PyObject * arg,const int empty)1656 static int frozendict_update_arg(PyObject *self,
1657 PyObject *arg,
1658 const int empty) {
1659 if (PyAnyDict_CheckExact(arg)) {
1660 return frozendict_merge(self, arg, empty);
1661 }
1662 _Py_IDENTIFIER(keys);
1663 PyObject *func;
1664 if (_PyObject_LookupAttrId(arg, &PyId_keys, &func) < 0) {
1665 return -1;
1666 }
1667 if (func != NULL) {
1668 Py_DECREF(func);
1669 return frozendict_merge(self, arg, empty);
1670 }
1671 return frozendict_merge_from_seq2(self, arg);
1672 }
1673
frozendict_update_common(PyObject * self,PyObject * arg,PyObject * kwds)1674 static int frozendict_update_common(PyObject* self,
1675 PyObject* arg,
1676 PyObject* kwds) {
1677 int result = 0;
1678 const int no_arg = (arg == NULL);
1679
1680 if (! no_arg) {
1681 result = frozendict_update_arg(self, arg, 1);
1682 }
1683
1684 if (result == 0 && kwds != NULL) {
1685 if (PyArg_ValidateKeywordArguments(kwds)) {
1686 result = frozendict_merge(self, kwds, no_arg);
1687 }
1688 else {
1689 result = -1;
1690 }
1691 }
1692
1693 return result;
1694 }
1695
frozendict_copy(PyObject * o,PyObject * Py_UNUSED (ignored))1696 static PyObject* frozendict_copy(PyObject* o, PyObject* Py_UNUSED(ignored)) {
1697 if (PyAnyFrozenDict_CheckExact(o)) {
1698 Py_INCREF(o);
1699 return o;
1700 }
1701
1702 PyObject* args = PyTuple_New(1);
1703
1704 if (args == NULL) {
1705 return NULL;
1706 }
1707
1708 Py_INCREF(o);
1709 PyTuple_SET_ITEM(args, 0, o);
1710
1711 PyTypeObject* type = Py_TYPE(o);
1712
1713 return PyObject_Call((PyObject *) type, args, NULL);
1714 }
1715
frozendict_equal(PyDictObject * a,PyDictObject * b)1716 static int frozendict_equal(PyDictObject* a, PyDictObject* b) {
1717 if (a == b) {
1718 return 1;
1719 }
1720
1721 if (a->ma_used != b->ma_used) {
1722 /* can't be equal if # of entries differ */
1723 return 0;
1724 }
1725
1726 PyDictKeysObject* keys = a->ma_keys;
1727 PyDictKeyEntry* ep;
1728 PyObject* aval;
1729 int cmp = 1;
1730 PyObject* bval;
1731 PyObject* key;
1732
1733 /* Same # of entries -- check all of 'em. Exit early on any diff. */
1734 for (Py_ssize_t i = 0; i < keys->dk_nentries; i++) {
1735 ep = &DK_ENTRIES(keys)[i];
1736 aval = ep->me_value;
1737 Py_INCREF(aval);
1738 key = ep->me_key;
1739 Py_INCREF(key);
1740
1741 /* reuse the known hash value */
1742 b->ma_keys->dk_lookup(b, key, ep->me_hash, &bval);
1743
1744 if (bval == NULL) {
1745 if (PyErr_Occurred()) {
1746 cmp = -1;
1747 }
1748 else {
1749 cmp = 0;
1750 }
1751 }
1752 else {
1753 Py_INCREF(bval);
1754 cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
1755 Py_DECREF(bval);
1756 }
1757
1758 Py_DECREF(key);
1759 Py_DECREF(aval);
1760 if (cmp <= 0) { /* error or not equal */
1761 break;
1762 }
1763 }
1764
1765 return cmp;
1766 }
1767
frozendict_richcompare(PyObject * v,PyObject * w,int op)1768 static PyObject* frozendict_richcompare(PyObject *v, PyObject *w, int op) {
1769 int cmp;
1770 PyObject *res;
1771
1772 if (!PyAnyDict_Check(v) || !PyAnyDict_Check(w)) {
1773 res = Py_NotImplemented;
1774 }
1775 else if (op == Py_EQ || op == Py_NE) {
1776 cmp = frozendict_equal((PyDictObject *)v, (PyDictObject *)w);
1777 if (cmp < 0)
1778 return NULL;
1779 res = (cmp == (op == Py_EQ)) ? Py_True : Py_False;
1780 }
1781 else
1782 res = Py_NotImplemented;
1783 Py_INCREF(res);
1784 return res;
1785 }
1786
1787 /*[clinic input]
1788
1789 @coexist
1790 dict.__contains__
1791
1792 key: object
1793 /
1794
1795 True if the dictionary has the specified key, else False.
1796 [clinic start generated code]*/
1797
1798 static PyObject *
dict___contains__(PyDictObject * self,PyObject * key)1799 dict___contains__(PyDictObject *self, PyObject *key)
1800 /*[clinic end generated code: output=a3d03db709ed6e6b input=fe1cb42ad831e820]*/
1801 {
1802 register PyDictObject *mp = self;
1803 Py_hash_t hash;
1804 Py_ssize_t ix;
1805 PyObject *value;
1806
1807 if (!PyUnicode_CheckExact(key) ||
1808 (hash = ((PyASCIIObject *) key)->hash) == -1) {
1809 hash = PyObject_Hash(key);
1810 if (hash == -1)
1811 return NULL;
1812 }
1813 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
1814 if (ix == DKIX_ERROR)
1815 return NULL;
1816 if (ix == DKIX_EMPTY || value == NULL)
1817 Py_RETURN_FALSE;
1818 Py_RETURN_TRUE;
1819 }
1820
1821 /*[clinic input]
1822 dict.get
1823
1824 key: object
1825 default: object = None
1826 /
1827
1828 Return the value for key if key is in the dictionary, else default.
1829 [clinic start generated code]*/
1830
1831 static PyObject *
dict_get_impl(PyDictObject * self,PyObject * key,PyObject * default_value)1832 dict_get_impl(PyDictObject *self, PyObject *key, PyObject *default_value)
1833 /*[clinic end generated code: output=bba707729dee05bf input=279ddb5790b6b107]*/
1834 {
1835 PyObject *val = NULL;
1836 Py_hash_t hash;
1837 Py_ssize_t ix;
1838
1839 if (!PyUnicode_CheckExact(key) ||
1840 (hash = ((PyASCIIObject *) key)->hash) == -1) {
1841 hash = PyObject_Hash(key);
1842 if (hash == -1)
1843 return NULL;
1844 }
1845 ix = (self->ma_keys->dk_lookup) (self, key, hash, &val);
1846 if (ix == DKIX_ERROR)
1847 return NULL;
1848 if (ix == DKIX_EMPTY || val == NULL) {
1849 val = default_value;
1850 }
1851 Py_INCREF(val);
1852 return val;
1853 }
1854
dict_get_index(PyDictObject * self,PyObject * key)1855 static Py_ssize_t dict_get_index(PyDictObject *self, PyObject *key) {
1856 Py_hash_t hash;
1857 PyObject* val;
1858
1859 if (!PyUnicode_CheckExact(key) ||
1860 (hash = ((PyASCIIObject *) key)->hash) == -1) {
1861 hash = PyObject_Hash(key);
1862 if (hash == -1)
1863 return DKIX_ERROR;
1864 }
1865 return (self->ma_keys->dk_lookup) (self, key, hash, &val);
1866 }
1867
1868 static int
dict_traverse(PyObject * op,visitproc visit,void * arg)1869 dict_traverse(PyObject *op, visitproc visit, void *arg)
1870 {
1871 PyDictObject *mp = (PyDictObject *)op;
1872 PyDictKeysObject *keys = mp->ma_keys;
1873 PyDictKeyEntry *entries = DK_ENTRIES(keys);
1874 Py_ssize_t i, n = keys->dk_nentries;
1875
1876 if (keys->dk_lookup == lookdict) {
1877 for (i = 0; i < n; i++) {
1878 if (entries[i].me_value != NULL) {
1879 Py_VISIT(entries[i].me_value);
1880 Py_VISIT(entries[i].me_key);
1881 }
1882 }
1883 }
1884 else {
1885 if (mp->ma_values != NULL) {
1886 for (i = 0; i < n; i++) {
1887 Py_VISIT(mp->ma_values[i]);
1888 }
1889 }
1890 else {
1891 for (i = 0; i < n; i++) {
1892 Py_VISIT(entries[i].me_value);
1893 }
1894 }
1895 }
1896 return 0;
1897 }
1898
1899 /* Forward */
1900 static PyObject *frozendictkeys_new(PyObject *, PyObject *);
1901 static PyObject *frozendictitems_new(PyObject *, PyObject *);
1902 static PyObject *frozendictvalues_new(PyObject *, PyObject *);
1903
1904 static PyObject *
frozendict_reduce(PyFrozenDictObject * mp,PyObject * Py_UNUSED (ignored))1905 frozendict_reduce(PyFrozenDictObject* mp, PyObject *Py_UNUSED(ignored))
1906 {
1907 PyObject* items = frozendictitems_new((PyObject*) mp, NULL);
1908
1909 if (items == NULL) {
1910 return NULL;
1911 }
1912
1913 PyObject* items_tuple = PySequence_Tuple(items);
1914
1915 if (items_tuple == NULL) {
1916 return NULL;
1917 }
1918
1919 return Py_BuildValue("O(N)", Py_TYPE(mp), items_tuple);
1920 }
1921
1922 static PyObject *dictiter_new(PyDictObject *, PyTypeObject *);
1923
1924 static PyObject *
dict_sizeof(PyDictObject * mp,PyObject * Py_UNUSED (ignored))1925 dict_sizeof(PyDictObject *mp, PyObject *Py_UNUSED(ignored))
1926 {
1927 return PyLong_FromSsize_t(_PyDict_SizeOf(mp));
1928 }
1929
frozendict_clone(PyObject * self)1930 static PyObject* frozendict_clone(PyObject* self) {
1931 PyTypeObject* type = Py_TYPE(self);
1932 PyObject* new_op = type->tp_alloc(type, 0);
1933
1934 if (new_op == NULL){
1935 return NULL;
1936 }
1937
1938 if (type == &PyFrozenDict_Type || type == &PyCoold_Type) {
1939 _PyObject_GC_UNTRACK(new_op);
1940 }
1941
1942 PyDictObject* mp = (PyDictObject*) self;
1943
1944 PyDictKeysObject *keys = clone_combined_dict_keys(mp);
1945
1946 if (keys == NULL) {
1947 return NULL;
1948 }
1949
1950 PyFrozenDictObject* new_mp = (PyFrozenDictObject*) new_op;
1951 new_mp->ma_keys = keys;
1952
1953 if (_PyObject_GC_IS_TRACKED(mp) && !_PyObject_GC_IS_TRACKED(new_mp)) {
1954 _PyObject_GC_TRACK(new_mp);
1955 }
1956
1957 new_mp->ma_used = mp->ma_used;
1958 new_mp->_hash = -1;
1959 new_mp->_hash_calculated = 0;
1960 new_mp->ma_version_tag = DICT_NEXT_VERSION();
1961
1962 ASSERT_CONSISTENT(new_mp);
1963
1964 return new_op;
1965 }
1966
frozendict_set(PyObject * self,PyObject * const * args,Py_ssize_t nargs)1967 static PyObject* frozendict_set(
1968 PyObject* self,
1969 PyObject* const* args,
1970 Py_ssize_t nargs
1971 ) {
1972 PyObject* new_op = frozendict_clone(self);
1973
1974 if (new_op == NULL) {
1975 return NULL;
1976 }
1977
1978 PyObject* set_key = args[0];
1979
1980 if (frozendict_setitem(new_op, set_key, args[1], 0)) {
1981 Py_DECREF(new_op);
1982 return NULL;
1983 }
1984
1985 if (
1986 ((PyDictObject*) self)->ma_keys->dk_lookup == lookdict_unicode_nodummy &&
1987 ! PyUnicode_CheckExact(set_key)
1988 ) {
1989 ((PyFrozenDictObject*) new_op)->ma_keys->dk_lookup = lookdict;
1990 }
1991
1992 return new_op;
1993 }
1994
frozendict_del(PyObject * self,PyObject * const * args,Py_ssize_t nargs)1995 static PyObject* frozendict_del(PyObject* self,
1996 PyObject *const *args,
1997 Py_ssize_t nargs) {
1998 if (! _PyArg_CheckPositional("del", nargs, 1, 1)) {
1999 return NULL;
2000 }
2001
2002 PyDictObject* mp = (PyDictObject*) self;
2003 PyObject* del_key = args[0];
2004 const Py_ssize_t ix = dict_get_index(mp, del_key);
2005
2006 if (ix == DKIX_ERROR) {
2007 return NULL;
2008 }
2009
2010 if (ix == DKIX_EMPTY) {
2011 _PyErr_SetKeyError(del_key);
2012 return NULL;
2013 }
2014
2015 PyTypeObject* type = Py_TYPE(self);
2016 PyObject* new_op = type->tp_alloc(type, 0);
2017
2018 if (new_op == NULL) {
2019 return NULL;
2020 }
2021
2022 if (type == &PyFrozenDict_Type || type == &PyCoold_Type) {
2023 _PyObject_GC_UNTRACK(new_op);
2024 }
2025
2026 const Py_ssize_t size = mp->ma_used;
2027 const Py_ssize_t sizemm = size - 1;
2028 const Py_ssize_t newsize = estimate_keysize(sizemm);
2029
2030 if (newsize <= 0) {
2031 Py_DECREF(new_op);
2032 PyErr_NoMemory();
2033 return NULL;
2034 }
2035
2036 assert(IS_POWER_OF_2(newsize));
2037 assert(newsize >= PyDict_MINSIZE);
2038
2039 /* Allocate a new table. */
2040 PyDictKeysObject* new_keys = new_keys_object(newsize);
2041
2042 if (new_keys == NULL) {
2043 Py_DECREF(new_op);
2044 return NULL;
2045 }
2046
2047 const PyDictKeysObject* old_keys = mp->ma_keys;
2048 new_keys->dk_lookup = old_keys->dk_lookup;
2049
2050 PyFrozenDictObject* new_mp = (PyFrozenDictObject*) new_op;
2051
2052 // New table must be large enough.
2053 assert(new_keys->dk_usable >= new_mp->ma_used);
2054
2055 new_mp->ma_keys = new_keys;
2056 new_mp->_hash = -1;
2057 new_mp->_hash_calculated = 0;
2058 new_mp->ma_version_tag = DICT_NEXT_VERSION();
2059
2060 PyObject* key;
2061 PyObject* value;
2062 Py_hash_t hash;
2063 Py_ssize_t hashpos;
2064 PyDictKeyEntry* old_entries = DK_ENTRIES(old_keys);
2065 PyDictKeyEntry* new_entries = DK_ENTRIES(new_keys);
2066 PyDictKeyEntry* old_entry;
2067 PyDictKeyEntry* new_entry;
2068 Py_ssize_t new_i;
2069 int deleted = 0;
2070
2071 for (Py_ssize_t i = 0; i < size; i++) {
2072 if (i == ix) {
2073 deleted = 1;
2074 continue;
2075 }
2076
2077 new_i = i - deleted;
2078
2079 old_entry = &old_entries[i];
2080 hash = old_entry->me_hash;
2081 key = old_entry->me_key;
2082 value = old_entry->me_value;
2083 Py_INCREF(key);
2084 Py_INCREF(value);
2085 hashpos = find_empty_slot(new_keys, hash);
2086 dictkeys_set_index(new_keys, hashpos, new_i);
2087 new_entry = &new_entries[new_i];
2088 new_entry->me_key = key;
2089 new_entry->me_hash = hash;
2090 new_entry->me_value = value;
2091 }
2092
2093 new_mp->ma_used = sizemm;
2094 new_keys->dk_usable -= sizemm;
2095 new_keys->dk_nentries = sizemm;
2096
2097 ASSERT_CONSISTENT(new_mp);
2098
2099 return new_op;
2100 }
2101
2102 PyDoc_STRVAR(getitem__doc__, "x.__getitem__(y) <==> x[y]");
2103
2104 PyDoc_STRVAR(sizeof__doc__,
2105 "D.__sizeof__() -> size of D in memory, in bytes");
2106
2107 PyDoc_STRVAR(copy__doc__,
2108 "D.copy() -> a shallow copy of D");
2109
2110 PyDoc_STRVAR(keys__doc__,
2111 "D.keys() -> a set-like object providing a view on D's keys");
2112 PyDoc_STRVAR(items__doc__,
2113 "D.items() -> a set-like object providing a view on D's items");
2114 PyDoc_STRVAR(values__doc__,
2115 "D.values() -> an object providing a view on D's values");
2116
2117 static PyMethodDef frozen_mapp_methods[] = {
2118 DICT___CONTAINS___METHODDEF
2119 {"__getitem__", (PyCFunction)(void(*)(void))dict_subscript, METH_O | METH_COEXIST,
2120 getitem__doc__},
2121 {"__sizeof__", (PyCFunction)(void(*)(void))dict_sizeof, METH_NOARGS,
2122 sizeof__doc__},
2123 DICT_GET_METHODDEF
2124 {"keys", frozendictkeys_new, METH_NOARGS,
2125 keys__doc__},
2126 {"items", frozendictitems_new, METH_NOARGS,
2127 items__doc__},
2128 {"values", frozendictvalues_new, METH_NOARGS,
2129 values__doc__},
2130 {"fromkeys", (PyCFunction)(void(*)(void))frozendict_fromkeys, METH_FASTCALL|METH_CLASS,
2131 dict_fromkeys__doc__},
2132 {"copy", (PyCFunction)frozendict_copy, METH_NOARGS,
2133 copy__doc__},
2134 DICT___REVERSED___METHODDEF
2135 {"__class_getitem__", Py_GenericAlias, METH_O|METH_CLASS, "See PEP 585"},
2136 {"__reduce__", (PyCFunction)(void(*)(void))frozendict_reduce, METH_NOARGS,
2137 ""},
2138 {NULL, NULL} /* sentinel */
2139 };
2140
2141 PyDoc_STRVAR(frozendict_set_doc,
2142 "set($self, key, value, /)\n"
2143 "--\n"
2144 "\n"
2145 "Returns a copy of the dictionary with the new (key, value) item. ");
2146
2147 PyDoc_STRVAR(frozendict_del_doc,
2148 "del($self, key, /)\n"
2149 "--\n"
2150 "\n"
2151 "Returns a copy of the dictionary without the item of the corresponding key. ");
2152
2153 static PyMethodDef coold_mapp_methods[] = {
2154 DICT___CONTAINS___METHODDEF
2155 {"__getitem__", (PyCFunction)(void(*)(void))dict_subscript, METH_O | METH_COEXIST,
2156 getitem__doc__},
2157 {"__sizeof__", (PyCFunction)(void(*)(void))dict_sizeof, METH_NOARGS,
2158 sizeof__doc__},
2159 DICT_GET_METHODDEF
2160 {"keys", frozendictkeys_new, METH_NOARGS,
2161 keys__doc__},
2162 {"items", frozendictitems_new, METH_NOARGS,
2163 items__doc__},
2164 {"values", frozendictvalues_new, METH_NOARGS,
2165 values__doc__},
2166 {"fromkeys", (PyCFunction)(void(*)(void))frozendict_fromkeys, METH_FASTCALL|METH_CLASS,
2167 dict_fromkeys__doc__},
2168 {"copy", (PyCFunction)frozendict_copy, METH_NOARGS,
2169 copy__doc__},
2170 DICT___REVERSED___METHODDEF
2171 {"__reduce__", (PyCFunction)(void(*)(void))frozendict_reduce, METH_NOARGS,
2172 ""},
2173 {"set", (PyCFunction)(void(*)(void))
2174 frozendict_set, METH_FASTCALL,
2175 frozendict_set_doc},
2176 {"delete", (PyCFunction)(void(*)(void))
2177 frozendict_del, METH_FASTCALL,
2178 frozendict_del_doc},
2179 {NULL, NULL} /* sentinel */
2180 };
2181
2182 /* Hack to implement "key in dict" */
2183 static PySequenceMethods dict_as_sequence = {
2184 0, /* sq_length */
2185 0, /* sq_concat */
2186 0, /* sq_repeat */
2187 0, /* sq_item */
2188 0, /* sq_slice */
2189 0, /* sq_ass_item */
2190 0, /* sq_ass_slice */
2191 PyDict_Contains, /* sq_contains */
2192 0, /* sq_inplace_concat */
2193 0, /* sq_inplace_repeat */
2194 };
2195
frozendict_new_barebone(PyTypeObject * type)2196 static PyObject* frozendict_new_barebone(PyTypeObject* type) {
2197 PyObject* self = type->tp_alloc(type, 0);
2198
2199 if (self == NULL) {
2200 return NULL;
2201 }
2202
2203 /* The object has been implicitly tracked by tp_alloc */
2204 if (type == &PyFrozenDict_Type || type == &PyCoold_Type) {
2205 _PyObject_GC_UNTRACK(self);
2206 }
2207
2208 PyFrozenDictObject* mp = (PyFrozenDictObject*) self;
2209
2210 mp->ma_keys = NULL;
2211 mp->ma_values = NULL;
2212 mp->ma_used = 0;
2213 mp->_hash = -1;
2214 mp->_hash_calculated = 0;
2215
2216 return self;
2217 }
2218
frozendict_vectorcall(PyObject * type,PyObject * const * args,size_t nargsf,PyObject * kwnames)2219 static PyObject* frozendict_vectorcall(PyObject* type,
2220 PyObject* const* args,
2221 size_t nargsf,
2222 PyObject* kwnames) {
2223 assert(PyType_Check(type));
2224 Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);
2225
2226 if (! _PyArg_CheckPositional("dict", nargs, 0, 1)) {
2227 return NULL;
2228 }
2229
2230 PyTypeObject* ttype = (PyTypeObject*) type;
2231
2232 Py_ssize_t size;
2233 PyObject* arg;
2234
2235 if (nargs == 1) {
2236 arg = args[0];
2237
2238 // only argument is a frozendict
2239 if (
2240 arg != NULL
2241 && PyAnyFrozenDict_CheckExact(arg)
2242 && (
2243 ttype == &PyFrozenDict_Type
2244 || ttype == &PyCoold_Type
2245 )
2246 ) {
2247 size = (
2248 kwnames == NULL
2249 ? 0
2250 : PyTuple_GET_SIZE(kwnames)
2251 );
2252
2253 if (size == 0) {
2254 Py_INCREF(arg);
2255
2256 return arg;
2257 }
2258 }
2259 }
2260
2261 PyObject* self = frozendict_new_barebone(ttype);
2262
2263 PyFrozenDictObject* mp = (PyFrozenDictObject*) self;
2264
2265 int empty = 1;
2266
2267 if (nargs == 1) {
2268 empty = 0;
2269
2270 if (frozendict_update_arg(self, arg, 1) < 0) {
2271 Py_DECREF(self);
2272 return NULL;
2273 }
2274
2275 args++;
2276 }
2277
2278 if (kwnames != NULL) {
2279 if (mp->ma_keys == NULL) {
2280 mp->ma_keys = new_keys_object(PyDict_MINSIZE);
2281 }
2282
2283 size = (
2284 kwnames == NULL
2285 ? 0
2286 : PyTuple_GET_SIZE(kwnames)
2287 );
2288
2289 if (mp->ma_keys->dk_usable < size) {
2290 if (frozendict_resize((PyDictObject*) self, estimate_keysize(mp->ma_used + size))) {
2291 return NULL;
2292 }
2293 }
2294
2295 for (Py_ssize_t i = 0; i < size; i++) {
2296 if (frozendict_setitem(self, PyTuple_GET_ITEM(kwnames, i), args[i], empty) < 0) {
2297 Py_DECREF(self);
2298 return NULL;
2299 }
2300 }
2301 }
2302
2303 // if frozendict is empty, return the empty singleton
2304 if (mp->ma_used == 0 && (ttype == &PyFrozenDict_Type || ttype == &PyCoold_Type)) {
2305 if (empty_frozendict == NULL) {
2306 empty_frozendict = self;
2307 ((PyDictObject*) empty_frozendict)->ma_keys = Py_EMPTY_KEYS;
2308 mp->ma_version_tag = DICT_NEXT_VERSION();
2309 }
2310
2311 Py_INCREF(empty_frozendict);
2312
2313 return empty_frozendict;
2314 }
2315
2316 mp->ma_version_tag = DICT_NEXT_VERSION();
2317
2318 ASSERT_CONSISTENT(mp);
2319
2320 return self;
2321 }
2322
_frozendict_new(PyTypeObject * type,PyObject * args,PyObject * kwds,const int use_empty_frozendict)2323 static PyObject* _frozendict_new(
2324 PyTypeObject* type,
2325 PyObject* args,
2326 PyObject* kwds,
2327 const int use_empty_frozendict
2328 ) {
2329 assert(type != NULL && type->tp_alloc != NULL);
2330
2331 PyObject* arg = NULL;
2332
2333 if (args != NULL && ! PyArg_UnpackTuple(args, "dict", 0, 1, &arg)) {
2334 return NULL;
2335 }
2336
2337 const int arg_is_frozendict = (arg != NULL && PyAnyFrozenDict_CheckExact(arg));
2338 const int kwds_size = ((kwds != NULL)
2339 ? ((PyDictObject*) kwds)->ma_used
2340 : 0
2341 );
2342
2343 // only argument is a frozendict
2344 if (arg_is_frozendict && kwds_size == 0 && (type == &PyFrozenDict_Type || type == &PyCoold_Type)) {
2345 Py_INCREF(arg);
2346
2347 return arg;
2348 }
2349
2350 PyObject* self = frozendict_new_barebone(type);
2351
2352 PyFrozenDictObject* mp = (PyFrozenDictObject*) self;
2353
2354 if (frozendict_update_common(self, arg, kwds)) {
2355 Py_DECREF(self);
2356 return NULL;
2357 }
2358
2359 // if frozendict is empty, return the empty singleton
2360 if (
2361 mp->ma_used == 0
2362 && use_empty_frozendict
2363 && (
2364 type == &PyFrozenDict_Type
2365 || type == &PyCoold_Type
2366 )
2367 ) {
2368 if (empty_frozendict == NULL) {
2369 empty_frozendict = self;
2370 ((PyDictObject*) empty_frozendict)->ma_keys = Py_EMPTY_KEYS;
2371 mp->ma_version_tag = DICT_NEXT_VERSION();
2372 }
2373
2374 Py_INCREF(empty_frozendict);
2375
2376 return empty_frozendict;
2377 }
2378
2379 mp->ma_version_tag = DICT_NEXT_VERSION();
2380
2381 return self;
2382 }
2383
frozendict_new(PyTypeObject * type,PyObject * args,PyObject * kwds)2384 static PyObject* frozendict_new(PyTypeObject* type, PyObject* args, PyObject* kwds) {
2385 return _frozendict_new(type, args, kwds, 1);
2386 }
2387
2388 #define MINUSONE_HASH ((Py_hash_t) -1)
2389
frozendict_hash(PyObject * self)2390 static Py_hash_t frozendict_hash(PyObject* self) {
2391 PyFrozenDictObject* frozen_self = (PyFrozenDictObject*) self;
2392 Py_hash_t hash;
2393
2394 if (frozen_self->_hash_calculated) {
2395 hash = frozen_self->_hash;
2396
2397 if (hash == MINUSONE_HASH) {
2398 PyErr_SetObject(PyExc_TypeError, Py_None);
2399 }
2400 }
2401 else {
2402 PyObject* frozen_items_tmp = frozendictitems_new(self, NULL);
2403
2404 if (frozen_items_tmp == NULL) {
2405 return NULL;
2406 }
2407
2408 PyObject* frozen_items = PyFrozenSet_New(frozen_items_tmp);
2409
2410 if (frozen_items == NULL) {
2411 hash = MINUSONE_HASH;
2412 }
2413 else {
2414 hash = PyFrozenSet_Type.tp_hash(frozen_items);
2415 }
2416
2417 frozen_self->_hash = hash;
2418 frozen_self->_hash_calculated = 1;
2419 }
2420
2421 return hash;
2422 }
2423
frozendict_or(PyObject * self,PyObject * other)2424 static PyObject* frozendict_or(PyObject *self, PyObject *other) {
2425 if (! PyAnyFrozenDict_Check(self) || ! PyAnyDict_Check(other)) {
2426 Py_RETURN_NOTIMPLEMENTED;
2427 }
2428
2429 PyObject* new = frozendict_clone(self);
2430
2431 if (new == NULL) {
2432 return NULL;
2433 }
2434
2435 if (frozendict_update_arg(new, other, 0)) {
2436 Py_DECREF(new);
2437 return NULL;
2438 }
2439
2440 return new;
2441 }
2442
2443 static PyNumberMethods frozendict_as_number = {
2444 .nb_or = frozendict_or,
2445 };
2446
2447 PyDoc_STRVAR(frozendict_doc,
2448 "An immutable version of dict.\n"
2449 "\n"
2450 FROZENDICT_CLASS_NAME "() -> returns an empty immutable dictionary\n"
2451 FROZENDICT_CLASS_NAME "(mapping) -> returns an immutable dictionary initialized from a mapping object's\n"
2452 " (key, value) pairs\n"
2453 FROZENDICT_CLASS_NAME "(iterable) -> returns an immutable dictionary, equivalent to:\n"
2454 " d = {}\n"
2455 " "
2456 " for k, v in iterable:\n"
2457 " d[k] = v\n"
2458 " "
2459 " " FROZENDICT_CLASS_NAME "(d)\n"
2460 FROZENDICT_CLASS_NAME "(**kwargs) -> returns an immutable dictionary initialized with the name=value pairs\n"
2461 " in the keyword argument list. For example: " FROZENDICT_CLASS_NAME "(one=1, two=2)");
2462
2463 PyDoc_STRVAR(coold_doc,
2464 "An immutable version of dict.\n"
2465 "\n"
2466 COOLD_CLASS_NAME "() -> returns an empty immutable dictionary\n"
2467 COOLD_CLASS_NAME "(mapping) -> returns an immutable dictionary initialized from a mapping object's\n"
2468 " (key, value) pairs\n"
2469 COOLD_CLASS_NAME "(iterable) -> returns an immutable dictionary, equivalent to:\n"
2470 " d = {}\n"
2471 " "
2472 " for k, v in iterable:\n"
2473 " d[k] = v\n"
2474 " "
2475 " " COOLD_CLASS_NAME "(d)\n"
2476 COOLD_CLASS_NAME "(**kwargs) -> returns an immutable dictionary initialized with the name=value pairs\n"
2477 " in the keyword argument list. For example: " COOLD_CLASS_NAME "(one=1, two=2)");
2478
2479 PyTypeObject PyFrozenDict_Type = {
2480 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2481 "frozendict." FROZENDICT_CLASS_NAME, /* tp_name */
2482 sizeof(PyFrozenDictObject), /* tp_basicsize */
2483 0, /* tp_itemsize */
2484 (destructor)dict_dealloc, /* tp_dealloc */
2485 0, /* tp_vectorcall_offset */
2486 0, /* tp_getattr */
2487 0, /* tp_setattr */
2488 0, /* tp_as_async */
2489 (reprfunc)frozendict_repr, /* tp_repr */
2490 &frozendict_as_number, /* tp_as_number */
2491 &dict_as_sequence, /* tp_as_sequence */
2492 &frozendict_as_mapping, /* tp_as_mapping */
2493 (hashfunc)frozendict_hash, /* tp_hash */
2494 0, /* tp_call */
2495 0, /* tp_str */
2496 PyObject_GenericGetAttr, /* tp_getattro */
2497 0, /* tp_setattro */
2498 0, /* tp_as_buffer */
2499 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC
2500 | Py_TPFLAGS_BASETYPE, /* tp_flags */
2501 frozendict_doc, /* tp_doc */
2502 dict_traverse, /* tp_traverse */
2503 0, /* tp_clear */
2504 frozendict_richcompare, /* tp_richcompare */
2505 0, /* tp_weaklistoffset */
2506 (getiterfunc)frozendict_iter, /* tp_iter */
2507 0, /* tp_iternext */
2508 frozen_mapp_methods, /* tp_methods */
2509 0, /* tp_members */
2510 0, /* tp_getset */
2511 0, /* tp_base */
2512 0, /* tp_dict */
2513 0, /* tp_descr_get */
2514 0, /* tp_descr_set */
2515 0, /* tp_dictoffset */
2516 0, /* tp_init */
2517 PyType_GenericAlloc, /* tp_alloc */
2518 frozendict_new, /* tp_new */
2519 PyObject_GC_Del, /* tp_free */
2520 .tp_vectorcall = frozendict_vectorcall,
2521 };
2522
2523 PyTypeObject PyCoold_Type = {
2524 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2525 "frozendict." COOLD_CLASS_NAME, /* tp_name */
2526 sizeof(PyFrozenDictObject), /* tp_basicsize */
2527 0, /* tp_itemsize */
2528 (destructor)dict_dealloc, /* tp_dealloc */
2529 0, /* tp_vectorcall_offset */
2530 0, /* tp_getattr */
2531 0, /* tp_setattr */
2532 0, /* tp_as_async */
2533 (reprfunc)frozendict_repr, /* tp_repr */
2534 &frozendict_as_number, /* tp_as_number */
2535 &dict_as_sequence, /* tp_as_sequence */
2536 &frozendict_as_mapping, /* tp_as_mapping */
2537 (hashfunc)frozendict_hash, /* tp_hash */
2538 0, /* tp_call */
2539 0, /* tp_str */
2540 PyObject_GenericGetAttr, /* tp_getattro */
2541 0, /* tp_setattro */
2542 0, /* tp_as_buffer */
2543 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC
2544 | Py_TPFLAGS_BASETYPE, /* tp_flags */
2545 coold_doc, /* tp_doc */
2546 dict_traverse, /* tp_traverse */
2547 0, /* tp_clear */
2548 frozendict_richcompare, /* tp_richcompare */
2549 0, /* tp_weaklistoffset */
2550 (getiterfunc)frozendict_iter, /* tp_iter */
2551 0, /* tp_iternext */
2552 coold_mapp_methods, /* tp_methods */
2553 0, /* tp_members */
2554 0, /* tp_getset */
2555 &PyFrozenDict_Type, /* tp_base */
2556 0, /* tp_dict */
2557 0, /* tp_descr_get */
2558 0, /* tp_descr_set */
2559 0, /* tp_dictoffset */
2560 0, /* tp_init */
2561 PyType_GenericAlloc, /* tp_alloc */
2562 frozendict_new, /* tp_new */
2563 PyObject_GC_Del, /* tp_free */
2564 .tp_vectorcall = frozendict_vectorcall,
2565 };
2566
2567 /* Dictionary iterator types */
2568
2569 typedef struct {
2570 PyObject_HEAD
2571 PyDictObject *di_dict; /* Set to NULL when iterator is exhausted */
2572 Py_ssize_t di_used;
2573 Py_ssize_t di_pos;
2574 PyObject* di_result; /* reusable result tuple for iteritems */
2575 Py_ssize_t len;
2576 } dictiterobject;
2577
2578 static PyObject *
dictiter_new(PyDictObject * dict,PyTypeObject * itertype)2579 dictiter_new(PyDictObject *dict, PyTypeObject *itertype)
2580 {
2581 dictiterobject *di;
2582 di = PyObject_GC_New(dictiterobject, itertype);
2583 if (di == NULL) {
2584 return NULL;
2585 }
2586 Py_INCREF(dict);
2587 di->di_dict = dict;
2588 di->di_used = dict->ma_used;
2589 di->len = dict->ma_used;
2590 if (itertype == &PyDictRevIterKey_Type ||
2591 itertype == &PyDictRevIterItem_Type ||
2592 itertype == &PyDictRevIterValue_Type) {
2593 if (dict->ma_values) {
2594 di->di_pos = dict->ma_used - 1;
2595 }
2596 else {
2597 di->di_pos = dict->ma_keys->dk_nentries - 1;
2598 }
2599 }
2600 else {
2601 di->di_pos = 0;
2602 }
2603 if (itertype == &PyFrozenDictIterItem_Type ||
2604 itertype == &PyDictRevIterItem_Type) {
2605 di->di_result = PyTuple_Pack(2, Py_None, Py_None);
2606 if (di->di_result == NULL) {
2607 Py_DECREF(di);
2608 return NULL;
2609 }
2610 }
2611 else {
2612 di->di_result = NULL;
2613 }
2614 _PyObject_GC_TRACK(di);
2615 return (PyObject *)di;
2616 }
2617
frozendict_iter(PyDictObject * dict)2618 static PyObject* frozendict_iter(PyDictObject *dict) {
2619 return dictiter_new(dict, &PyFrozenDictIterKey_Type);
2620 }
2621
2622 static void
dictiter_dealloc(dictiterobject * di)2623 dictiter_dealloc(dictiterobject *di)
2624 {
2625 /* bpo-31095: UnTrack is needed before calling any callbacks */
2626 _PyObject_GC_UNTRACK(di);
2627 Py_XDECREF(di->di_dict);
2628 Py_XDECREF(di->di_result);
2629 PyObject_GC_Del(di);
2630 }
2631
2632 static int
dictiter_traverse(dictiterobject * di,visitproc visit,void * arg)2633 dictiter_traverse(dictiterobject *di, visitproc visit, void *arg)
2634 {
2635 Py_VISIT(di->di_dict);
2636 Py_VISIT(di->di_result);
2637 return 0;
2638 }
2639
2640 static PyObject *
dictiter_len(dictiterobject * di,PyObject * Py_UNUSED (ignored))2641 dictiter_len(dictiterobject *di, PyObject *Py_UNUSED(ignored))
2642 {
2643 Py_ssize_t len = 0;
2644 if (di->di_dict != NULL && di->di_used == di->di_dict->ma_used)
2645 len = di->len;
2646 return PyLong_FromSize_t(len);
2647 }
2648
2649 PyDoc_STRVAR(length_hint_doc,
2650 "Private method returning an estimate of len(list(it)).");
2651
2652 static PyObject *
2653 dictiter_reduce(dictiterobject *di, PyObject *Py_UNUSED(ignored));
2654
2655 PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
2656
2657 static PyMethodDef dictiter_methods[] = {
2658 {"__length_hint__", (PyCFunction)(void(*)(void))dictiter_len, METH_NOARGS,
2659 length_hint_doc},
2660 {"__reduce__", (PyCFunction)(void(*)(void))dictiter_reduce, METH_NOARGS,
2661 reduce_doc},
2662 {NULL, NULL} /* sentinel */
2663 };
2664
frozendictiter_iternextkey(dictiterobject * di)2665 static PyObject* frozendictiter_iternextkey(dictiterobject* di) {
2666 Py_ssize_t pos = di->di_pos;
2667 assert(pos >= 0);
2668 PyDictObject* d = di->di_dict;
2669 assert(d != NULL);
2670
2671 if (pos >= d->ma_used) {
2672 return NULL;
2673 }
2674
2675 assert(PyAnyFrozenDict_Check(d));
2676 PyObject* key = DK_ENTRIES(d->ma_keys)[di->di_pos].me_key;
2677 assert(key != NULL);
2678 di->di_pos++;
2679 di->len--;
2680 Py_INCREF(key);
2681 return key;
2682 }
2683
2684 PyTypeObject PyFrozenDictIterKey_Type = {
2685 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2686 "frozendict_keyiterator", /* tp_name */
2687 sizeof(dictiterobject), /* tp_basicsize */
2688 0, /* tp_itemsize */
2689 /* methods */
2690 (destructor)dictiter_dealloc, /* tp_dealloc */
2691 0, /* tp_vectorcall_offset */
2692 0, /* tp_getattr */
2693 0, /* tp_setattr */
2694 0, /* tp_as_async */
2695 0, /* tp_repr */
2696 0, /* tp_as_number */
2697 0, /* tp_as_sequence */
2698 0, /* tp_as_mapping */
2699 0, /* tp_hash */
2700 0, /* tp_call */
2701 0, /* tp_str */
2702 PyObject_GenericGetAttr, /* tp_getattro */
2703 0, /* tp_setattro */
2704 0, /* tp_as_buffer */
2705 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
2706 0, /* tp_doc */
2707 (traverseproc)dictiter_traverse, /* tp_traverse */
2708 0, /* tp_clear */
2709 0, /* tp_richcompare */
2710 0, /* tp_weaklistoffset */
2711 PyObject_SelfIter, /* tp_iter */
2712 (iternextfunc)frozendictiter_iternextkey, /* tp_iternext */
2713 dictiter_methods, /* tp_methods */
2714 0,
2715 };
2716
frozendictiter_iternextvalue(dictiterobject * di)2717 static PyObject* frozendictiter_iternextvalue(dictiterobject* di) {
2718 Py_ssize_t pos = di->di_pos;
2719 assert(pos >= 0);
2720 PyDictObject* d = di->di_dict;
2721 assert(d != NULL);
2722
2723 if (pos >= d->ma_used) {
2724 return NULL;
2725 }
2726
2727 assert(PyAnyFrozenDict_Check(d));
2728 PyObject* val = DK_ENTRIES(d->ma_keys)[di->di_pos].me_value;
2729 assert(val != NULL);
2730 di->di_pos++;
2731 di->len--;
2732 Py_INCREF(val);
2733 return val;
2734 }
2735
2736 PyTypeObject PyFrozenDictIterValue_Type = {
2737 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2738 "frozendict_valueiterator", /* tp_name */
2739 sizeof(dictiterobject), /* tp_basicsize */
2740 0, /* tp_itemsize */
2741 /* methods */
2742 (destructor)dictiter_dealloc, /* tp_dealloc */
2743 0, /* tp_vectorcall_offset */
2744 0, /* tp_getattr */
2745 0, /* tp_setattr */
2746 0, /* tp_as_async */
2747 0, /* tp_repr */
2748 0, /* tp_as_number */
2749 0, /* tp_as_sequence */
2750 0, /* tp_as_mapping */
2751 0, /* tp_hash */
2752 0, /* tp_call */
2753 0, /* tp_str */
2754 PyObject_GenericGetAttr, /* tp_getattro */
2755 0, /* tp_setattro */
2756 0, /* tp_as_buffer */
2757 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
2758 0, /* tp_doc */
2759 (traverseproc)dictiter_traverse, /* tp_traverse */
2760 0, /* tp_clear */
2761 0, /* tp_richcompare */
2762 0, /* tp_weaklistoffset */
2763 PyObject_SelfIter, /* tp_iter */
2764 (iternextfunc)frozendictiter_iternextvalue, /* tp_iternext */
2765 dictiter_methods, /* tp_methods */
2766 0,
2767 };
2768
frozendictiter_iternextitem(dictiterobject * di)2769 static PyObject* frozendictiter_iternextitem(dictiterobject* di) {
2770 Py_ssize_t pos = di->di_pos;
2771 assert(pos >= 0);
2772 PyDictObject* d = di->di_dict;
2773 assert(d != NULL);
2774
2775 if (pos >= d->ma_used) {
2776 return NULL;
2777 }
2778
2779 assert(PyAnyFrozenDict_Check(d));
2780 PyDictKeyEntry* entry_ptr = &DK_ENTRIES(d->ma_keys)[di->di_pos];
2781 PyObject* key = entry_ptr->me_key;
2782 PyObject* val = entry_ptr->me_value;
2783 assert(key != NULL);
2784 assert(val != NULL);
2785 di->di_pos++;
2786 Py_INCREF(key);
2787 Py_INCREF(val);
2788
2789 PyObject* result;
2790 if (Py_REFCNT(di->di_result) == 1) {
2791 result = di->di_result;
2792 PyObject *oldkey = PyTuple_GET_ITEM(result, 0);
2793 PyObject *oldvalue = PyTuple_GET_ITEM(result, 1);
2794 Py_INCREF(result);
2795 Py_DECREF(oldkey);
2796 Py_DECREF(oldvalue);
2797
2798 if (!_PyObject_GC_IS_TRACKED(result)) {
2799 _PyObject_GC_TRACK(result);
2800 }
2801 }
2802 else {
2803 result = PyTuple_New(2);
2804 if (result == NULL)
2805 return NULL;
2806 }
2807
2808 PyTuple_SET_ITEM(result, 0, key); /* steals reference */
2809 PyTuple_SET_ITEM(result, 1, val); /* steals reference */
2810 return result;
2811 }
2812
2813 PyTypeObject PyFrozenDictIterItem_Type = {
2814 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2815 "frozendict_itemiterator", /* tp_name */
2816 sizeof(dictiterobject), /* tp_basicsize */
2817 0, /* tp_itemsize */
2818 /* methods */
2819 (destructor)dictiter_dealloc, /* tp_dealloc */
2820 0, /* tp_vectorcall_offset */
2821 0, /* tp_getattr */
2822 0, /* tp_setattr */
2823 0, /* tp_as_async */
2824 0, /* tp_repr */
2825 0, /* tp_as_number */
2826 0, /* tp_as_sequence */
2827 0, /* tp_as_mapping */
2828 0, /* tp_hash */
2829 0, /* tp_call */
2830 0, /* tp_str */
2831 PyObject_GenericGetAttr, /* tp_getattro */
2832 0, /* tp_setattro */
2833 0, /* tp_as_buffer */
2834 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2835 0, /* tp_doc */
2836 (traverseproc)dictiter_traverse, /* tp_traverse */
2837 0, /* tp_clear */
2838 0, /* tp_richcompare */
2839 0, /* tp_weaklistoffset */
2840 PyObject_SelfIter, /* tp_iter */
2841 (iternextfunc)frozendictiter_iternextitem, /* tp_iternext */
2842 dictiter_methods, /* tp_methods */
2843 0,
2844 };
2845
2846 /* dictreviter */
2847
2848
2849 /*[clinic input]
2850 dict.__reversed__
2851
2852 Return a reverse iterator over the dict keys.
2853 [clinic start generated code]*/
2854
2855 static PyObject *
dict___reversed___impl(PyDictObject * self)2856 dict___reversed___impl(PyDictObject *self)
2857 /*[clinic end generated code: output=e674483336d1ed51 input=23210ef3477d8c4d]*/
2858 {
2859 assert (PyAnyDict_Check(self));
2860 return dictiter_new(self, &PyDictRevIterKey_Type);
2861 }
2862
2863 static PyObject *
dictiter_reduce(dictiterobject * di,PyObject * Py_UNUSED (ignored))2864 dictiter_reduce(dictiterobject *di, PyObject *Py_UNUSED(ignored))
2865 {
2866 _Py_IDENTIFIER(iter);
2867 /* copy the iterator state */
2868 dictiterobject tmp = *di;
2869 Py_XINCREF(tmp.di_dict);
2870
2871 PyObject *list = PySequence_List((PyObject*)&tmp);
2872 Py_XDECREF(tmp.di_dict);
2873 if (list == NULL) {
2874 return NULL;
2875 }
2876 return Py_BuildValue("N(N)", _PyEval_GetBuiltinId(&PyId_iter), list);
2877 }
2878
2879 /* The instance lay-out is the same for all three; but the type differs. */
2880
2881 static void
dictview_dealloc(_PyDictViewObject * dv)2882 dictview_dealloc(_PyDictViewObject *dv)
2883 {
2884 /* bpo-31095: UnTrack is needed before calling any callbacks */
2885 _PyObject_GC_UNTRACK(dv);
2886 Py_XDECREF(dv->dv_dict);
2887 PyObject_GC_Del(dv);
2888 }
2889
2890 static int
dictview_traverse(_PyDictViewObject * dv,visitproc visit,void * arg)2891 dictview_traverse(_PyDictViewObject *dv, visitproc visit, void *arg)
2892 {
2893 Py_VISIT(dv->dv_dict);
2894 return 0;
2895 }
2896
2897 static Py_ssize_t
dictview_len(_PyDictViewObject * dv)2898 dictview_len(_PyDictViewObject *dv)
2899 {
2900 Py_ssize_t len = 0;
2901 if (dv->dv_dict != NULL)
2902 len = dv->dv_dict->ma_used;
2903 return len;
2904 }
2905
2906 static PyObject *
frozendict_view_new(PyObject * dict,PyTypeObject * type)2907 frozendict_view_new(PyObject *dict, PyTypeObject *type)
2908 {
2909 _PyDictViewObject *dv;
2910 if (dict == NULL) {
2911 PyErr_BadInternalCall();
2912 return NULL;
2913 }
2914 if (!PyAnyDict_Check(dict)) {
2915 /* XXX Get rid of this restriction later */
2916 PyErr_Format(PyExc_TypeError,
2917 "%s() requires a dict argument, not '%s'",
2918 type->tp_name, Py_TYPE(dict)->tp_name);
2919 return NULL;
2920 }
2921 dv = PyObject_GC_New(_PyDictViewObject, type);
2922 if (dv == NULL)
2923 return NULL;
2924 Py_INCREF(dict);
2925 dv->dv_dict = (PyDictObject *)dict;
2926 _PyObject_GC_TRACK(dv);
2927 return (PyObject *)dv;
2928 }
2929
2930 static PyObject *
dictview_new(PyObject * dict,PyTypeObject * type)2931 dictview_new(PyObject *dict, PyTypeObject *type)
2932 {
2933 _PyDictViewObject *dv;
2934 if (dict == NULL) {
2935 PyErr_BadInternalCall();
2936 return NULL;
2937 }
2938 if (!PyAnyDict_Check(dict)) {
2939 /* XXX Get rid of this restriction later */
2940 PyErr_Format(PyExc_TypeError,
2941 "%s() requires a dict argument, not '%s'",
2942 type->tp_name, Py_TYPE(dict)->tp_name);
2943 return NULL;
2944 }
2945 dv = PyObject_GC_New(_PyDictViewObject, type);
2946 if (dv == NULL)
2947 return NULL;
2948 Py_INCREF(dict);
2949 dv->dv_dict = (PyDictObject *)dict;
2950 _PyObject_GC_TRACK(dv);
2951 return (PyObject *)dv;
2952 }
2953
2954 static PyObject *
dictview_mapping(PyObject * view,void * Py_UNUSED (ignored))2955 dictview_mapping(PyObject *view, void *Py_UNUSED(ignored)) {
2956 assert(view != NULL);
2957 assert(PyDictKeys_Check(view)
2958 || PyDictValues_Check(view)
2959 || PyDictItems_Check(view));
2960 PyObject *mapping = (PyObject *)((_PyDictViewObject *)view)->dv_dict;
2961 return PyDictProxy_New(mapping);
2962 }
2963
2964 static PyGetSetDef dictview_getset[] = {
2965 {"mapping", dictview_mapping, (setter)NULL,
2966 "dictionary that this view refers to", NULL},
2967 {0}
2968 };
2969
2970 /* TODO(guido): The views objects are not complete:
2971
2972 * support more set operations
2973 * support arbitrary mappings?
2974 - either these should be static or exported in dictobject.h
2975 - if public then they should probably be in builtins
2976 */
2977
2978 /* Return 1 if self is a subset of other, iterating over self;
2979 0 if not; -1 if an error occurred. */
2980 static int
all_contained_in(PyObject * self,PyObject * other)2981 all_contained_in(PyObject *self, PyObject *other)
2982 {
2983 PyObject *iter = PyObject_GetIter(self);
2984 int ok = 1;
2985
2986 if (iter == NULL)
2987 return -1;
2988 for (;;) {
2989 PyObject *next = PyIter_Next(iter);
2990 if (next == NULL) {
2991 if (PyErr_Occurred())
2992 ok = -1;
2993 break;
2994 }
2995 ok = PySequence_Contains(other, next);
2996 Py_DECREF(next);
2997 if (ok <= 0)
2998 break;
2999 }
3000 Py_DECREF(iter);
3001 return ok;
3002 }
3003
3004 static PyObject *
dictview_richcompare(PyObject * self,PyObject * other,int op)3005 dictview_richcompare(PyObject *self, PyObject *other, int op)
3006 {
3007 Py_ssize_t len_self, len_other;
3008 int ok;
3009 PyObject *result;
3010
3011 assert(self != NULL);
3012 assert(PyDictViewSet_Check(self));
3013 assert(other != NULL);
3014
3015 if (!PyAnySet_Check(other) && !PyDictViewSet_Check(other))
3016 Py_RETURN_NOTIMPLEMENTED;
3017
3018 len_self = PyObject_Size(self);
3019 if (len_self < 0)
3020 return NULL;
3021 len_other = PyObject_Size(other);
3022 if (len_other < 0)
3023 return NULL;
3024
3025 ok = 0;
3026 switch(op) {
3027
3028 case Py_NE:
3029 case Py_EQ:
3030 if (len_self == len_other)
3031 ok = all_contained_in(self, other);
3032 if (op == Py_NE && ok >= 0)
3033 ok = !ok;
3034 break;
3035
3036 case Py_LT:
3037 if (len_self < len_other)
3038 ok = all_contained_in(self, other);
3039 break;
3040
3041 case Py_LE:
3042 if (len_self <= len_other)
3043 ok = all_contained_in(self, other);
3044 break;
3045
3046 case Py_GT:
3047 if (len_self > len_other)
3048 ok = all_contained_in(other, self);
3049 break;
3050
3051 case Py_GE:
3052 if (len_self >= len_other)
3053 ok = all_contained_in(other, self);
3054 break;
3055
3056 }
3057 if (ok < 0)
3058 return NULL;
3059 result = ok ? Py_True : Py_False;
3060 Py_INCREF(result);
3061 return result;
3062 }
3063
3064 static PyObject *
dictview_repr(_PyDictViewObject * dv)3065 dictview_repr(_PyDictViewObject *dv)
3066 {
3067 PyObject *seq;
3068 PyObject *result = NULL;
3069 Py_ssize_t rc;
3070
3071 rc = Py_ReprEnter((PyObject *)dv);
3072 if (rc != 0) {
3073 return rc > 0 ? PyUnicode_FromString("...") : NULL;
3074 }
3075 seq = PySequence_List((PyObject *)dv);
3076 if (seq == NULL) {
3077 goto Done;
3078 }
3079 result = PyUnicode_FromFormat("%s(%R)", Py_TYPE(dv)->tp_name, seq);
3080 Py_DECREF(seq);
3081
3082 Done:
3083 Py_ReprLeave((PyObject *)dv);
3084 return result;
3085 }
3086
3087 /*** dict_keys ***/
3088
3089 static PyObject *
frozendictkeys_iter(_PyDictViewObject * dv)3090 frozendictkeys_iter(_PyDictViewObject *dv)
3091 {
3092 if (dv->dv_dict == NULL) {
3093 Py_RETURN_NONE;
3094 }
3095 return dictiter_new(dv->dv_dict, &PyFrozenDictIterKey_Type);
3096 }
3097
3098 static int
dictkeys_contains(_PyDictViewObject * dv,PyObject * obj)3099 dictkeys_contains(_PyDictViewObject *dv, PyObject *obj)
3100 {
3101 if (dv->dv_dict == NULL)
3102 return 0;
3103 return PyDict_Contains((PyObject *)dv->dv_dict, obj);
3104 }
3105
3106 static PySequenceMethods dictkeys_as_sequence = {
3107 (lenfunc)dictview_len, /* sq_length */
3108 0, /* sq_concat */
3109 0, /* sq_repeat */
3110 0, /* sq_item */
3111 0, /* sq_slice */
3112 0, /* sq_ass_item */
3113 0, /* sq_ass_slice */
3114 (objobjproc)dictkeys_contains, /* sq_contains */
3115 };
3116
3117 // Create an set object from dictviews object.
3118 // Returns a new reference.
3119 // This utility function is used by set operations.
3120 static PyObject*
dictviews_to_set(PyObject * self)3121 dictviews_to_set(PyObject *self)
3122 {
3123 PyObject *left = self;
3124 if (PyDictKeys_Check(self)) {
3125 // PySet_New() has fast path for the dict object.
3126 PyObject *dict = (PyObject *)((_PyDictViewObject *)self)->dv_dict;
3127 if (PyAnyDict_CheckExact(dict)) {
3128 left = dict;
3129 }
3130 }
3131 return PySet_New(left);
3132 }
3133
3134 static PyObject*
dictviews_sub(PyObject * self,PyObject * other)3135 dictviews_sub(PyObject *self, PyObject *other)
3136 {
3137 PyObject *result = dictviews_to_set(self);
3138 if (result == NULL) {
3139 return NULL;
3140 }
3141
3142 _Py_IDENTIFIER(difference_update);
3143 PyObject *tmp = _PyObject_CallMethodIdOneArg(
3144 result, &PyId_difference_update, other);
3145 if (tmp == NULL) {
3146 Py_DECREF(result);
3147 return NULL;
3148 }
3149
3150 Py_DECREF(tmp);
3151 return result;
3152 }
3153
3154 static PyObject*
dictviews_or(PyObject * self,PyObject * other)3155 dictviews_or(PyObject* self, PyObject *other)
3156 {
3157 PyObject *result = dictviews_to_set(self);
3158 if (result == NULL) {
3159 return NULL;
3160 }
3161
3162 if (_PySet_Update(result, other) < 0) {
3163 Py_DECREF(result);
3164 return NULL;
3165 }
3166 return result;
3167 }
3168
3169 static PyObject *
dictitems_xor(PyObject * self,PyObject * other)3170 dictitems_xor(PyObject *self, PyObject *other)
3171 {
3172 assert(PyDictItems_Check(self));
3173 assert(PyDictItems_Check(other));
3174 PyObject *d1 = (PyObject *)((_PyDictViewObject *)self)->dv_dict;
3175 PyObject *d2 = (PyObject *)((_PyDictViewObject *)other)->dv_dict;
3176
3177 PyObject *temp_dict = PyDict_Copy(d1);
3178 if (temp_dict == NULL) {
3179 return NULL;
3180 }
3181 PyObject *result_set = PySet_New(NULL);
3182 if (result_set == NULL) {
3183 Py_CLEAR(temp_dict);
3184 return NULL;
3185 }
3186
3187 PyObject *key = NULL, *val1 = NULL, *val2 = NULL;
3188 Py_ssize_t pos = 0;
3189 Py_hash_t hash;
3190
3191 while (_frozendict_next(d2, &pos, &key, &val2, &hash)) {
3192 Py_INCREF(key);
3193 Py_INCREF(val2);
3194 val1 = _PyDict_GetItem_KnownHash(temp_dict, key, hash);
3195
3196 int to_delete;
3197 if (val1 == NULL) {
3198 if (PyErr_Occurred()) {
3199 goto error;
3200 }
3201 to_delete = 0;
3202 }
3203 else {
3204 Py_INCREF(val1);
3205 to_delete = PyObject_RichCompareBool(val1, val2, Py_EQ);
3206 if (to_delete < 0) {
3207 goto error;
3208 }
3209 }
3210
3211 if (to_delete) {
3212 if (_PyDict_DelItem_KnownHash(temp_dict, key, hash) < 0) {
3213 goto error;
3214 }
3215 }
3216 else {
3217 PyObject *pair = PyTuple_Pack(2, key, val2);
3218 if (pair == NULL) {
3219 goto error;
3220 }
3221 if (PySet_Add(result_set, pair) < 0) {
3222 Py_DECREF(pair);
3223 goto error;
3224 }
3225 Py_DECREF(pair);
3226 }
3227 Py_DECREF(key);
3228 Py_XDECREF(val1);
3229 Py_DECREF(val2);
3230 }
3231 key = val1 = val2 = NULL;
3232
3233 _Py_IDENTIFIER(items);
3234 PyObject *remaining_pairs = _PyObject_CallMethodIdNoArgs(temp_dict,
3235 &PyId_items);
3236 if (remaining_pairs == NULL) {
3237 goto error;
3238 }
3239 if (_PySet_Update(result_set, remaining_pairs) < 0) {
3240 Py_DECREF(remaining_pairs);
3241 goto error;
3242 }
3243 Py_DECREF(temp_dict);
3244 Py_DECREF(remaining_pairs);
3245 return result_set;
3246
3247 error:
3248 Py_XDECREF(temp_dict);
3249 Py_XDECREF(result_set);
3250 Py_XDECREF(key);
3251 Py_XDECREF(val1);
3252 Py_XDECREF(val2);
3253 return NULL;
3254 }
3255
3256 static PyObject*
dictviews_xor(PyObject * self,PyObject * other)3257 dictviews_xor(PyObject* self, PyObject *other)
3258 {
3259 if (PyDictItems_Check(self) && PyDictItems_Check(other)) {
3260 return dictitems_xor(self, other);
3261 }
3262 PyObject *result = dictviews_to_set(self);
3263 if (result == NULL) {
3264 return NULL;
3265 }
3266
3267 _Py_IDENTIFIER(symmetric_difference_update);
3268 PyObject *tmp = _PyObject_CallMethodIdOneArg(
3269 result, &PyId_symmetric_difference_update, other);
3270 if (tmp == NULL) {
3271 Py_DECREF(result);
3272 return NULL;
3273 }
3274
3275 Py_DECREF(tmp);
3276 return result;
3277 }
3278
3279 static PyNumberMethods dictviews_as_number = {
3280 0, /*nb_add*/
3281 (binaryfunc)dictviews_sub, /*nb_subtract*/
3282 0, /*nb_multiply*/
3283 0, /*nb_remainder*/
3284 0, /*nb_divmod*/
3285 0, /*nb_power*/
3286 0, /*nb_negative*/
3287 0, /*nb_positive*/
3288 0, /*nb_absolute*/
3289 0, /*nb_bool*/
3290 0, /*nb_invert*/
3291 0, /*nb_lshift*/
3292 0, /*nb_rshift*/
3293 (binaryfunc)_PyDictView_Intersect, /*nb_and*/
3294 (binaryfunc)dictviews_xor, /*nb_xor*/
3295 (binaryfunc)dictviews_or, /*nb_or*/
3296 };
3297
3298 static PyObject*
dictviews_isdisjoint(PyObject * self,PyObject * other)3299 dictviews_isdisjoint(PyObject *self, PyObject *other)
3300 {
3301 PyObject *it;
3302 PyObject *item = NULL;
3303
3304 if (self == other) {
3305 if (dictview_len((_PyDictViewObject *)self) == 0)
3306 Py_RETURN_TRUE;
3307 else
3308 Py_RETURN_FALSE;
3309 }
3310
3311 /* Iterate over the shorter object (only if other is a set,
3312 * because PySequence_Contains may be expensive otherwise): */
3313 if (PyAnySet_Check(other) || PyDictViewSet_Check(other)) {
3314 Py_ssize_t len_self = dictview_len((_PyDictViewObject *)self);
3315 Py_ssize_t len_other = PyObject_Size(other);
3316 if (len_other == -1)
3317 return NULL;
3318
3319 if ((len_other > len_self)) {
3320 PyObject *tmp = other;
3321 other = self;
3322 self = tmp;
3323 }
3324 }
3325
3326 it = PyObject_GetIter(other);
3327 if (it == NULL)
3328 return NULL;
3329
3330 while ((item = PyIter_Next(it)) != NULL) {
3331 int contains = PySequence_Contains(self, item);
3332 Py_DECREF(item);
3333 if (contains == -1) {
3334 Py_DECREF(it);
3335 return NULL;
3336 }
3337
3338 if (contains) {
3339 Py_DECREF(it);
3340 Py_RETURN_FALSE;
3341 }
3342 }
3343 Py_DECREF(it);
3344 if (PyErr_Occurred())
3345 return NULL; /* PyIter_Next raised an exception. */
3346 Py_RETURN_TRUE;
3347 }
3348
3349 PyDoc_STRVAR(isdisjoint_doc,
3350 "Return True if the view and the given iterable have a null intersection.");
3351
3352 static PyObject* dictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored));
3353
3354 PyDoc_STRVAR(reversed_keys_doc,
3355 "Return a reverse iterator over the dict keys.");
3356
3357 static PyMethodDef dictkeys_methods[] = {
3358 {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
3359 isdisjoint_doc},
3360 {"__reversed__", (PyCFunction)(void(*)(void))dictkeys_reversed, METH_NOARGS,
3361 reversed_keys_doc},
3362 {NULL, NULL} /* sentinel */
3363 };
3364
3365 static PyTypeObject PyFrozenDictKeys_Type = {
3366 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3367 "frozendict_keys", /* tp_name */
3368 sizeof(_PyDictViewObject), /* tp_basicsize */
3369 0, /* tp_itemsize */
3370 /* methods */
3371 (destructor)dictview_dealloc, /* tp_dealloc */
3372 0, /* tp_vectorcall_offset */
3373 0, /* tp_getattr */
3374 0, /* tp_setattr */
3375 0, /* tp_as_async */
3376 (reprfunc)dictview_repr, /* tp_repr */
3377 &dictviews_as_number, /* tp_as_number */
3378 &dictkeys_as_sequence, /* tp_as_sequence */
3379 0, /* tp_as_mapping */
3380 0, /* tp_hash */
3381 0, /* tp_call */
3382 0, /* tp_str */
3383 PyObject_GenericGetAttr, /* tp_getattro */
3384 0, /* tp_setattro */
3385 0, /* tp_as_buffer */
3386 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3387 0, /* tp_doc */
3388 (traverseproc)dictview_traverse, /* tp_traverse */
3389 0, /* tp_clear */
3390 dictview_richcompare, /* tp_richcompare */
3391 0, /* tp_weaklistoffset */
3392 (getiterfunc)frozendictkeys_iter, /* tp_iter */
3393 0, /* tp_iternext */
3394 dictkeys_methods, /* tp_methods */
3395 .tp_getset = dictview_getset,
3396 };
3397
3398 static PyObject *
frozendictkeys_new(PyObject * dict,PyObject * Py_UNUSED (ignored))3399 frozendictkeys_new(PyObject *dict, PyObject *Py_UNUSED(ignored))
3400 {
3401 return dictview_new(dict, &PyFrozenDictKeys_Type);
3402 }
3403
3404 static PyObject *
dictkeys_reversed(_PyDictViewObject * dv,PyObject * Py_UNUSED (ignored))3405 dictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
3406 {
3407 if (dv->dv_dict == NULL) {
3408 Py_RETURN_NONE;
3409 }
3410 return dictiter_new(dv->dv_dict, &PyDictRevIterKey_Type);
3411 }
3412
3413 /*** dict_items ***/
3414
3415 static PyObject *
frozendictitems_iter(_PyDictViewObject * dv)3416 frozendictitems_iter(_PyDictViewObject *dv)
3417 {
3418 if (dv->dv_dict == NULL) {
3419 Py_RETURN_NONE;
3420 }
3421 return dictiter_new(dv->dv_dict, &PyFrozenDictIterItem_Type);
3422 }
3423
3424 static int
dictitems_contains(_PyDictViewObject * dv,PyObject * obj)3425 dictitems_contains(_PyDictViewObject *dv, PyObject *obj)
3426 {
3427 int result;
3428 PyObject *key, *value, *found;
3429 if (dv->dv_dict == NULL)
3430 return 0;
3431 if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 2)
3432 return 0;
3433 key = PyTuple_GET_ITEM(obj, 0);
3434 value = PyTuple_GET_ITEM(obj, 1);
3435 found = PyDict_GetItemWithError((PyObject *)dv->dv_dict, key);
3436 if (found == NULL) {
3437 if (PyErr_Occurred())
3438 return -1;
3439 return 0;
3440 }
3441 Py_INCREF(found);
3442 result = PyObject_RichCompareBool(found, value, Py_EQ);
3443 Py_DECREF(found);
3444 return result;
3445 }
3446
3447 static PySequenceMethods dictitems_as_sequence = {
3448 (lenfunc)dictview_len, /* sq_length */
3449 0, /* sq_concat */
3450 0, /* sq_repeat */
3451 0, /* sq_item */
3452 0, /* sq_slice */
3453 0, /* sq_ass_item */
3454 0, /* sq_ass_slice */
3455 (objobjproc)dictitems_contains, /* sq_contains */
3456 };
3457
3458 static PyObject* dictitems_reversed(_PyDictViewObject *dv);
3459
3460 PyDoc_STRVAR(reversed_items_doc,
3461 "Return a reverse iterator over the dict items.");
3462
3463 static PyMethodDef dictitems_methods[] = {
3464 {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
3465 isdisjoint_doc},
3466 {"__reversed__", (PyCFunction)(void(*)(void))dictitems_reversed, METH_NOARGS,
3467 reversed_items_doc},
3468 {NULL, NULL} /* sentinel */
3469 };
3470
3471 PyTypeObject PyFrozenDictItems_Type = {
3472 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3473 "frozendict_items", /* tp_name */
3474 sizeof(_PyDictViewObject), /* tp_basicsize */
3475 0, /* tp_itemsize */
3476 /* methods */
3477 (destructor)dictview_dealloc, /* tp_dealloc */
3478 0, /* tp_vectorcall_offset */
3479 0, /* tp_getattr */
3480 0, /* tp_setattr */
3481 0, /* tp_as_async */
3482 (reprfunc)dictview_repr, /* tp_repr */
3483 &dictviews_as_number, /* tp_as_number */
3484 &dictitems_as_sequence, /* tp_as_sequence */
3485 0, /* tp_as_mapping */
3486 0, /* tp_hash */
3487 0, /* tp_call */
3488 0, /* tp_str */
3489 PyObject_GenericGetAttr, /* tp_getattro */
3490 0, /* tp_setattro */
3491 0, /* tp_as_buffer */
3492 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3493 0, /* tp_doc */
3494 (traverseproc)dictview_traverse, /* tp_traverse */
3495 0, /* tp_clear */
3496 dictview_richcompare, /* tp_richcompare */
3497 0, /* tp_weaklistoffset */
3498 (getiterfunc)frozendictitems_iter, /* tp_iter */
3499 0, /* tp_iternext */
3500 dictitems_methods, /* tp_methods */
3501 .tp_getset = dictview_getset,
3502 };
3503
3504 static PyObject *
frozendictitems_new(PyObject * dict,PyObject * Py_UNUSED (ignored))3505 frozendictitems_new(PyObject *dict, PyObject *Py_UNUSED(ignored))
3506 {
3507 return frozendict_view_new(dict, &PyFrozenDictItems_Type);
3508 }
3509
3510 static PyObject *
dictitems_reversed(_PyDictViewObject * dv)3511 dictitems_reversed(_PyDictViewObject *dv)
3512 {
3513 if (dv->dv_dict == NULL) {
3514 Py_RETURN_NONE;
3515 }
3516 return dictiter_new(dv->dv_dict, &PyDictRevIterItem_Type);
3517 }
3518
3519 /*** dict_values ***/
3520
3521 static PyObject *
frozendictvalues_iter(_PyDictViewObject * dv)3522 frozendictvalues_iter(_PyDictViewObject *dv)
3523 {
3524 if (dv->dv_dict == NULL) {
3525 Py_RETURN_NONE;
3526 }
3527 return dictiter_new(dv->dv_dict, &PyFrozenDictIterValue_Type);
3528 }
3529
3530 static PySequenceMethods dictvalues_as_sequence = {
3531 (lenfunc)dictview_len, /* sq_length */
3532 0, /* sq_concat */
3533 0, /* sq_repeat */
3534 0, /* sq_item */
3535 0, /* sq_slice */
3536 0, /* sq_ass_item */
3537 0, /* sq_ass_slice */
3538 (objobjproc)0, /* sq_contains */
3539 };
3540
3541 static PyObject* dictvalues_reversed(_PyDictViewObject *dv);
3542
3543 PyDoc_STRVAR(reversed_values_doc,
3544 "Return a reverse iterator over the dict values.");
3545
3546 static PyMethodDef dictvalues_methods[] = {
3547 {"__reversed__", (PyCFunction)(void(*)(void))dictvalues_reversed, METH_NOARGS,
3548 reversed_values_doc},
3549 {NULL, NULL} /* sentinel */
3550 };
3551
3552 PyTypeObject PyFrozenDictValues_Type = {
3553 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3554 "frozendict_values", /* tp_name */
3555 sizeof(_PyDictViewObject), /* tp_basicsize */
3556 0, /* tp_itemsize */
3557 /* methods */
3558 (destructor)dictview_dealloc, /* tp_dealloc */
3559 0, /* tp_vectorcall_offset */
3560 0, /* tp_getattr */
3561 0, /* tp_setattr */
3562 0, /* tp_as_async */
3563 (reprfunc)dictview_repr, /* tp_repr */
3564 0, /* tp_as_number */
3565 &dictvalues_as_sequence, /* tp_as_sequence */
3566 0, /* tp_as_mapping */
3567 0, /* tp_hash */
3568 0, /* tp_call */
3569 0, /* tp_str */
3570 PyObject_GenericGetAttr, /* tp_getattro */
3571 0, /* tp_setattro */
3572 0, /* tp_as_buffer */
3573 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3574 0, /* tp_doc */
3575 (traverseproc)dictview_traverse, /* tp_traverse */
3576 0, /* tp_clear */
3577 0, /* tp_richcompare */
3578 0, /* tp_weaklistoffset */
3579 (getiterfunc)frozendictvalues_iter, /* tp_iter */
3580 0, /* tp_iternext */
3581 dictvalues_methods, /* tp_methods */
3582 .tp_getset = dictview_getset,
3583 };
3584
3585 static PyObject *
frozendictvalues_new(PyObject * dict,PyObject * Py_UNUSED (ignored))3586 frozendictvalues_new(PyObject *dict, PyObject *Py_UNUSED(ignored))
3587 {
3588 return frozendict_view_new(dict, &PyFrozenDictValues_Type);
3589 }
3590
3591 static PyObject *
dictvalues_reversed(_PyDictViewObject * dv)3592 dictvalues_reversed(_PyDictViewObject *dv)
3593 {
3594 if (dv->dv_dict == NULL) {
3595 Py_RETURN_NONE;
3596 }
3597 return dictiter_new(dv->dv_dict, &PyDictRevIterValue_Type);
3598 }
3599
3600 static int
frozendict_exec(PyObject * m)3601 frozendict_exec(PyObject *m)
3602 {
3603 /* Finalize the type object including setting type of the new type
3604 * object; doing it here is required for portability, too. */
3605 if (PyType_Ready(&PyFrozenDict_Type) < 0)
3606 goto fail;
3607
3608 if (PyType_Ready(&PyCoold_Type) < 0)
3609 goto fail;
3610
3611 PyModule_AddObject(m, "frozendict", (PyObject *)&PyFrozenDict_Type);
3612 PyModule_AddObject(m, "coold", (PyObject *)&PyCoold_Type);
3613 return 0;
3614 fail:
3615 Py_XDECREF(m);
3616 return -1;
3617 }
3618
3619 static struct PyModuleDef_Slot frozendict_slots[] = {
3620 {Py_mod_exec, frozendict_exec},
3621 {0, NULL},
3622 };
3623
3624 static struct PyModuleDef frozendictmodule = {
3625 PyModuleDef_HEAD_INIT,
3626 "frozendict", /* name of module */
3627 NULL, /* module documentation, may be NULL */
3628 0, /* size of per-interpreter state of the module,
3629 or -1 if the module keeps state in global variables. */
3630 NULL,
3631 frozendict_slots,
3632 NULL,
3633 NULL,
3634 NULL
3635 };
3636
3637 PyMODINIT_FUNC
PyInit__frozendict(void)3638 PyInit__frozendict(void)
3639 {
3640 return PyModuleDef_Init(&frozendictmodule);
3641 }
3642