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