Debian Codegraph @

src/frozendict/c_src/3_10/cpython_src/Objects/dictobject.c

raw
1 /* Dictionary object implementation using a hash table */
2
3 /* The distribution includes a separate file, Objects/dictnotes.txt,
4 describing explorations into dictionary design and optimization.
5 It covers typical dictionary use patterns, the parameters for
6 tuning dictionaries, and several ideas for possible optimizations.
7 */
8
9 /* PyDictKeysObject
10
11 This implements the dictionary's hashtable.
12
13 As of Python 3.6, this is compact and ordered. Basic idea is described here:
14 * https://mail.python.org/pipermail/python-dev/2012-December/123028.html
15 * https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html
16
17 layout:
18
19 +---------------+
20 | dk_refcnt |
21 | dk_size |
22 | dk_lookup |
23 | dk_usable |
24 | dk_nentries |
25 +---------------+
26 | dk_indices |
27 | |
28 +---------------+
29 | dk_entries |
30 | |
31 +---------------+
32
33 dk_indices is actual hashtable. It holds index in entries, or DKIX_EMPTY(-1)
34 or DKIX_DUMMY(-2).
35 Size of indices is dk_size. Type of each index in indices is vary on dk_size:
36
37 * int8 for dk_size <= 128
38 * int16 for 256 <= dk_size <= 2**15
39 * int32 for 2**16 <= dk_size <= 2**31
40 * int64 for 2**32 <= dk_size
41
42 dk_entries is array of PyDictKeyEntry. Its size is USABLE_FRACTION(dk_size).
43 DK_ENTRIES(dk) can be used to get pointer to entries.
44
45 NOTE: Since negative value is used for DKIX_EMPTY and DKIX_DUMMY, type of
46 dk_indices entry is signed integer and int16 is used for table which
47 dk_size == 256.
48 */
49
50
51 /*
52 The DictObject can be in one of two forms.
53
54 Either:
55 A combined table:
56 ma_values == NULL, dk_refcnt == 1.
57 Values are stored in the me_value field of the PyDictKeysObject.
58 Or:
59 A split table:
60 ma_values != NULL, dk_refcnt >= 1
61 Values are stored in the ma_values array.
62 Only string (unicode) keys are allowed.
63 All dicts sharing same key must have same insertion order.
64
65 There are four kinds of slots in the table (slot is index, and
66 DK_ENTRIES(keys)[index] if index >= 0):
67
68 1. Unused. index == DKIX_EMPTY
69 Does not hold an active (key, value) pair now and never did. Unused can
70 transition to Active upon key insertion. This is each slot's initial state.
71
72 2. Active. index >= 0, me_key != NULL and me_value != NULL
73 Holds an active (key, value) pair. Active can transition to Dummy or
74 Pending upon key deletion (for combined and split tables respectively).
75 This is the only case in which me_value != NULL.
76
77 3. Dummy. index == DKIX_DUMMY (combined only)
78 Previously held an active (key, value) pair, but that was deleted and an
79 active pair has not yet overwritten the slot. Dummy can transition to
80 Active upon key insertion. Dummy slots cannot be made Unused again
81 else the probe sequence in case of collision would have no way to know
82 they were once active.
83
84 4. Pending. index >= 0, key != NULL, and value == NULL (split only)
85 Not yet inserted in split-table.
86 */
87
88 /*
89 Preserving insertion order
90
91 It's simple for combined table. Since dk_entries is mostly append only, we can
92 get insertion order by just iterating dk_entries.
93
94 One exception is .popitem(). It removes last item in dk_entries and decrement
95 dk_nentries to achieve amortized O(1). Since there are DKIX_DUMMY remains in
96 dk_indices, we can't increment dk_usable even though dk_nentries is
97 decremented.
98
99 In split table, inserting into pending entry is allowed only for dk_entries[ix]
100 where ix == mp->ma_used. Inserting into other index and deleting item cause
101 converting the dict to the combined table.
102 */
103
104 /* PyDict_MINSIZE is the starting size for any new dict.
105 * 8 allows dicts with no more than 5 active entries; experiments suggested
106 * this suffices for the majority of dicts (consisting mostly of usually-small
107 * dicts created to pass keyword arguments).
108 * Making this 8, rather than 4 reduces the number of resizes for most
109 * dictionaries, without any significant extra memory use.
110 */
111 #define PyDict_MINSIZE 8
112
113 #include "Python.h"
114 #include "dict-common.h"
115 #include "stringlib/eq.h" // unicode_eq()
116
117 /*[clinic input]
118 class dict "PyDictObject *" "&PyDict_Type"
119 [clinic start generated code]*/
120 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=f157a5a0ce9589d6]*/
121
122
123 /*
124 To ensure the lookup algorithm terminates, there must be at least one Unused
125 slot (NULL key) in the table.
126 To avoid slowing down lookups on a near-full table, we resize the table when
127 it's USABLE_FRACTION (currently two-thirds) full.
128 */
129
130 #define PERTURB_SHIFT 5
131
132 /*
133 Major subtleties ahead: Most hash schemes depend on having a "good" hash
134 function, in the sense of simulating randomness. Python doesn't: its most
135 important hash functions (for ints) are very regular in common
136 cases:
137
138 >>>[hash(i) for i in range(4)]
139 [0, 1, 2, 3]
140
141 This isn't necessarily bad! To the contrary, in a table of size 2**i, taking
142 the low-order i bits as the initial table index is extremely fast, and there
143 are no collisions at all for dicts indexed by a contiguous range of ints. So
144 this gives better-than-random behavior in common cases, and that's very
145 desirable.
146
147 OTOH, when collisions occur, the tendency to fill contiguous slices of the
148 hash table makes a good collision resolution strategy crucial. Taking only
149 the last i bits of the hash code is also vulnerable: for example, consider
150 the list [i << 16 for i in range(20000)] as a set of keys. Since ints are
151 their own hash codes, and this fits in a dict of size 2**15, the last 15 bits
152 of every hash code are all 0: they *all* map to the same table index.
153
154 But catering to unusual cases should not slow the usual ones, so we just take
155 the last i bits anyway. It's up to collision resolution to do the rest. If
156 we *usually* find the key we're looking for on the first try (and, it turns
157 out, we usually do -- the table load factor is kept under 2/3, so the odds
158 are solidly in our favor), then it makes best sense to keep the initial index
159 computation dirt cheap.
160
161 The first half of collision resolution is to visit table indices via this
162 recurrence:
163
164 j = ((5*j) + 1) mod 2**i
165
166 For any initial j in range(2**i), repeating that 2**i times generates each
167 int in range(2**i) exactly once (see any text on random-number generation for
168 proof). By itself, this doesn't help much: like linear probing (setting
169 j += 1, or j -= 1, on each loop trip), it scans the table entries in a fixed
170 order. This would be bad, except that's not the only thing we do, and it's
171 actually *good* in the common cases where hash keys are consecutive. In an
172 example that's really too small to make this entirely clear, for a table of
173 size 2**3 the order of indices is:
174
175 0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating]
176
177 If two things come in at index 5, the first place we look after is index 2,
178 not 6, so if another comes in at index 6 the collision at 5 didn't hurt it.
179 Linear probing is deadly in this case because there the fixed probe order
180 is the *same* as the order consecutive keys are likely to arrive. But it's
181 extremely unlikely hash codes will follow a 5*j+1 recurrence by accident,
182 and certain that consecutive hash codes do not.
183
184 The other half of the strategy is to get the other bits of the hash code
185 into play. This is done by initializing a (unsigned) vrbl "perturb" to the
186 full hash code, and changing the recurrence to:
187
188 perturb >>= PERTURB_SHIFT;
189 j = (5*j) + 1 + perturb;
190 use j % 2**i as the next table index;
191
192 Now the probe sequence depends (eventually) on every bit in the hash code,
193 and the pseudo-scrambling property of recurring on 5*j+1 is more valuable,
194 because it quickly magnifies small differences in the bits that didn't affect
195 the initial index. Note that because perturb is unsigned, if the recurrence
196 is executed often enough perturb eventually becomes and remains 0. At that
197 point (very rarely reached) the recurrence is on (just) 5*j+1 again, and
198 that's certain to find an empty slot eventually (since it generates every int
199 in range(2**i), and we make sure there's always at least one empty slot).
200
201 Selecting a good value for PERTURB_SHIFT is a balancing act. You want it
202 small so that the high bits of the hash code continue to affect the probe
203 sequence across iterations; but you want it large so that in really bad cases
204 the high-order hash bits have an effect on early iterations. 5 was "the
205 best" in minimizing total collisions across experiments Tim Peters ran (on
206 both normal and pathological cases), but 4 and 6 weren't significantly worse.
207
208 Historical: Reimer Behrends contributed the idea of using a polynomial-based
209 approach, using repeated multiplication by x in GF(2**n) where an irreducible
210 polynomial for each table size was chosen such that x was a primitive root.
211 Christian Tismer later extended that to use division by x instead, as an
212 efficient way to get the high bits of the hash code into play. This scheme
213 also gave excellent collision statistics, but was more expensive: two
214 if-tests were required inside the loop; computing "the next" index took about
215 the same number of operations but without as much potential parallelism
216 (e.g., computing 5*j can go on at the same time as computing 1+perturb in the
217 above, and then shifting perturb can be done while the table index is being
218 masked); and the PyDictObject struct required a member to hold the table's
219 polynomial. In Tim's experiments the current scheme ran faster, produced
220 equally good collision statistics, needed less code & used less memory.
221
222 */
223
224 /* forward declarations */
225 static Py_ssize_t lookdict(PyDictObject *mp, PyObject *key,
226 Py_hash_t hash, PyObject **value_addr);
227 static Py_ssize_t
228 lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
229 Py_hash_t hash, PyObject **value_addr);
230
231 /*Global counter used to set ma_version_tag field of dictionary.
232 * It is incremented each time that a dictionary is created and each
233 * time that a dictionary is modified. */
234 static uint64_t pydict_global_version = 0;
235
236 #define DICT_NEXT_VERSION() (++pydict_global_version)
237
238 #include "clinic/dictobject.c.h"
239
240 #define DK_SIZE(dk) ((dk)->dk_size)
241 #if SIZEOF_VOID_P > 4
242 #define DK_IXSIZE(dk) \
243 (DK_SIZE(dk) <= 0xff ? \
244 1 : DK_SIZE(dk) <= 0xffff ? \
245 2 : DK_SIZE(dk) <= 0xffffffff ? \
246 4 : sizeof(int64_t))
247 #else
248 #define DK_IXSIZE(dk) \
249 (DK_SIZE(dk) <= 0xff ? \
250 1 : DK_SIZE(dk) <= 0xffff ? \
251 2 : sizeof(int32_t))
252 #endif
253 #define DK_ENTRIES(dk) \
254 ((PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[DK_SIZE(dk) * DK_IXSIZE(dk)]))
255
256 #define DK_MASK(dk) (((dk)->dk_size)-1)
257 #define IS_POWER_OF_2(x) (((x) & (x-1)) == 0)
258
259 static void free_keys_object(PyDictKeysObject *keys);
260
261 static inline void
262 dictkeys_incref(PyDictKeysObject *dk)
263 {
264 #ifdef Py_REF_DEBUG
265 _Py_RefTotal++;
266 #endif
267 dk->dk_refcnt++;
268 }
269
270 static inline void
271 dictkeys_decref(PyDictKeysObject *dk)
272 {
273 assert(dk->dk_refcnt > 0);
274 #ifdef Py_REF_DEBUG
275 _Py_RefTotal--;
276 #endif
277 if (--dk->dk_refcnt == 0) {
278 free_keys_object(dk);
279 }
280 }
281
282 /* lookup indices. returns DKIX_EMPTY, DKIX_DUMMY, or ix >=0 */
283 static inline Py_ssize_t
284 dictkeys_get_index(const PyDictKeysObject *keys, Py_ssize_t i)
285 {
286 Py_ssize_t s = DK_SIZE(keys);
287 Py_ssize_t ix;
288
289 if (s <= 0xff) {
290 const int8_t *indices = (const int8_t*)(keys->dk_indices);
291 ix = indices[i];
292 }
293 else if (s <= 0xffff) {
294 const int16_t *indices = (const int16_t*)(keys->dk_indices);
295 ix = indices[i];
296 }
297 #if SIZEOF_VOID_P > 4
298 else if (s > 0xffffffff) {
299 const int64_t *indices = (const int64_t*)(keys->dk_indices);
300 ix = indices[i];
301 }
302 #endif
303 else {
304 const int32_t *indices = (const int32_t*)(keys->dk_indices);
305 ix = indices[i];
306 }
307 assert(ix >= DKIX_DUMMY);
308 return ix;
309 }
310
311 /* write to indices. */
312 static inline void
313 dictkeys_set_index(PyDictKeysObject *keys, Py_ssize_t i, Py_ssize_t ix)
314 {
315 Py_ssize_t s = DK_SIZE(keys);
316
317 assert(ix >= DKIX_DUMMY);
318
319 if (s <= 0xff) {
320 int8_t *indices = (int8_t*)(keys->dk_indices);
321 assert(ix <= 0x7f);
322 indices[i] = (char)ix;
323 }
324 else if (s <= 0xffff) {
325 int16_t *indices = (int16_t*)(keys->dk_indices);
326 assert(ix <= 0x7fff);
327 indices[i] = (int16_t)ix;
328 }
329 #if SIZEOF_VOID_P > 4
330 else if (s > 0xffffffff) {
331 int64_t *indices = (int64_t*)(keys->dk_indices);
332 indices[i] = ix;
333 }
334 #endif
335 else {
336 int32_t *indices = (int32_t*)(keys->dk_indices);
337 assert(ix <= 0x7fffffff);
338 indices[i] = (int32_t)ix;
339 }
340 }
341
342
343 /* USABLE_FRACTION is the maximum dictionary load.
344 * Increasing this ratio makes dictionaries more dense resulting in more
345 * collisions. Decreasing it improves sparseness at the expense of spreading
346 * indices over more cache lines and at the cost of total memory consumed.
347 *
348 * USABLE_FRACTION must obey the following:
349 * (0 < USABLE_FRACTION(n) < n) for all n >= 2
350 *
351 * USABLE_FRACTION should be quick to calculate.
352 * Fractions around 1/2 to 2/3 seem to work well in practice.
353 */
354 #define USABLE_FRACTION(n) (((n) << 1)/3)
355
356 /* Find the smallest dk_size >= minsize. */
357 static inline Py_ssize_t
358 calculate_keysize(Py_ssize_t minsize)
359 {
360 #if SIZEOF_LONG == SIZEOF_SIZE_T
361 minsize = (minsize | PyDict_MINSIZE) - 1;
362 return 1LL << _Py_bit_length(minsize | (PyDict_MINSIZE-1));
363 #elif defined(_MSC_VER)
364 // On 64bit Windows, sizeof(long) == 4.
365 minsize = (minsize | PyDict_MINSIZE) - 1;
366 unsigned long msb;
367 _BitScanReverse64(&msb, (uint64_t)minsize);
368 return 1LL << (msb + 1);
369 #else
370 Py_ssize_t size;
371 for (size = PyDict_MINSIZE;
372 size < minsize && size > 0;
373 size <<= 1)
374 ;
375 return size;
376 #endif
377 }
378
379 /* estimate_keysize is reverse function of USABLE_FRACTION.
380 *
381 * This can be used to reserve enough size to insert n entries without
382 * resizing.
383 */
384 static inline Py_ssize_t
385 estimate_keysize(Py_ssize_t n)
386 {
387 return calculate_keysize((n*3 + 1) / 2);
388 }
389
390
391 /* GROWTH_RATE. Growth rate upon hitting maximum load.
392 * Currently set to used*3.
393 * This means that dicts double in size when growing without deletions,
394 * but have more head room when the number of deletions is on a par with the
395 * number of insertions. See also bpo-17563 and bpo-33205.
396 *
397 * GROWTH_RATE was set to used*4 up to version 3.2.
398 * GROWTH_RATE was set to used*2 in version 3.3.0
399 * GROWTH_RATE was set to used*2 + capacity/2 in 3.4.0-3.6.0.
400 */
401 #define GROWTH_RATE(d) ((d)->ma_used*3)
402
403 /* This immutable, empty PyDictKeysObject is used for PyDict_Clear()
404 * (which cannot fail and thus can do no allocation).
405 */
406 static PyDictKeysObject empty_keys_struct = {
407 1, /* dk_refcnt */
408 1, /* dk_size */
409 lookdict_unicode_nodummy, /* dk_lookup */
410 0, /* dk_usable (immutable) */
411 0, /* dk_nentries */
412 {DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY,
413 DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY}, /* dk_indices */
414 };
415
416 static PyObject *empty_values[1] = { NULL };
417
418 #define Py_EMPTY_KEYS &empty_keys_struct
419
420 /* Uncomment to check the dict content in _PyDict_CheckConsistency() */
421 /* #define DEBUG_PYDICT */
422
423 #ifdef DEBUG_PYDICT
424 # define ASSERT_CONSISTENT(op) assert(_PyDict_CheckConsistency((PyObject *)(op), 1))
425 #else
426 # define ASSERT_CONSISTENT(op) assert(_PyDict_CheckConsistency((PyObject *)(op), 0))
427 #endif
428
429
430 static int
431 _PyDict_CheckConsistency(PyObject *op, int check_content)
432 {
433 #define CHECK(expr) \
434 do { if (!(expr)) { _PyObject_ASSERT_FAILED_MSG(op, Py_STRINGIFY(expr)); } } while (0)
435
436 assert(op != NULL);
437 CHECK(PyAnyDict_Check(op));
438 PyDictObject *mp = (PyDictObject *)op;
439
440 PyDictKeysObject *keys = mp->ma_keys;
441 int splitted = _PyDict_HasSplitTable(mp);
442 Py_ssize_t usable = USABLE_FRACTION(keys->dk_size);
443
444 CHECK(0 <= mp->ma_used && mp->ma_used <= usable);
445 CHECK(IS_POWER_OF_2(keys->dk_size));
446 CHECK(0 <= keys->dk_usable && keys->dk_usable <= usable);
447 CHECK(0 <= keys->dk_nentries && keys->dk_nentries <= usable);
448 CHECK(keys->dk_usable + keys->dk_nentries <= usable);
449
450 if (!splitted) {
451 /* combined table */
452 CHECK(keys->dk_refcnt == 1);
453 }
454
455 if (check_content) {
456 PyDictKeyEntry *entries = DK_ENTRIES(keys);
457 Py_ssize_t i;
458
459 for (i=0; i < keys->dk_size; i++) {
460 Py_ssize_t ix = dictkeys_get_index(keys, i);
461 CHECK(DKIX_DUMMY <= ix && ix <= usable);
462 }
463
464 for (i=0; i < usable; i++) {
465 PyDictKeyEntry *entry = &entries[i];
466 PyObject *key = entry->me_key;
467
468 if (key != NULL) {
469 if (PyUnicode_CheckExact(key)) {
470 Py_hash_t hash = ((PyASCIIObject *)key)->hash;
471 CHECK(hash != -1);
472 CHECK(entry->me_hash == hash);
473 }
474 else {
475 /* test_dict fails if PyObject_Hash() is called again */
476 CHECK(entry->me_hash != -1);
477 }
478 if (!splitted) {
479 CHECK(entry->me_value != NULL);
480 }
481 }
482
483 if (splitted) {
484 CHECK(entry->me_value == NULL);
485 }
486 }
487
488 if (splitted) {
489 /* splitted table */
490 for (i=0; i < mp->ma_used; i++) {
491 CHECK(mp->ma_values[i] != NULL);
492 }
493 }
494 }
495 return 1;
496
497 #undef CHECK
498 }
499
500
501 static PyDictKeysObject*
502 new_keys_object(Py_ssize_t size)
503 {
504 PyDictKeysObject *dk;
505 Py_ssize_t es, usable;
506
507 assert(size >= PyDict_MINSIZE);
508 assert(IS_POWER_OF_2(size));
509
510 usable = USABLE_FRACTION(size);
511 if (size <= 0xff) {
512 es = 1;
513 }
514 else if (size <= 0xffff) {
515 es = 2;
516 }
517 #if SIZEOF_VOID_P > 4
518 else if (size <= 0xffffffff) {
519 es = 4;
520 }
521 #endif
522 else {
523 es = sizeof(Py_ssize_t);
524 }
525
526 dk = PyObject_Malloc(sizeof(PyDictKeysObject)
527 + es * size
528 + sizeof(PyDictKeyEntry) * usable);
529 if (dk == NULL) {
530 PyErr_NoMemory();
531 return NULL;
532 }
533 #ifdef Py_REF_DEBUG
534 _Py_RefTotal++;
535 #endif
536 dk->dk_refcnt = 1;
537 dk->dk_size = size;
538 dk->dk_usable = usable;
539 dk->dk_lookup = lookdict_unicode_nodummy;
540 dk->dk_nentries = 0;
541 memset(&dk->dk_indices[0], 0xff, es * size);
542 memset(DK_ENTRIES(dk), 0, sizeof(PyDictKeyEntry) * usable);
543 return dk;
544 }
545
546 static void
547 free_keys_object(PyDictKeysObject *keys)
548 {
549 PyDictKeyEntry *entries = DK_ENTRIES(keys);
550 Py_ssize_t i, n;
551 for (i = 0, n = keys->dk_nentries; i < n; i++) {
552 Py_XDECREF(entries[i].me_key);
553 Py_XDECREF(entries[i].me_value);
554 }
555 PyObject_Free(keys);
556 }
557
558 #define new_values(size) PyMem_NEW(PyObject *, size)
559 #define free_values(values) PyMem_Free(values)
560
561 static Py_ssize_t
562 _d_PyDict_KeysSize(PyDictKeysObject *keys)
563 {
564 return (sizeof(PyDictKeysObject)
565 + DK_IXSIZE(keys) * DK_SIZE(keys)
566 + USABLE_FRACTION(DK_SIZE(keys)) * sizeof(PyDictKeyEntry));
567 }
568
569 static PyDictKeysObject *
570 clone_combined_dict_keys(PyDictObject *orig)
571 {
572 assert(PyAnyDict_Check(orig));
573
574 assert(
575 Py_TYPE(orig)->tp_iter == PyDict_Type.tp_iter ||
576 Py_TYPE(orig)->tp_iter == (getiterfunc)frozendict_iter
577 );
578
579 assert(orig->ma_values == NULL);
580 assert(orig->ma_keys->dk_refcnt == 1);
581
582 Py_ssize_t keys_size = _d_PyDict_KeysSize(orig->ma_keys);
583 PyDictKeysObject *keys = PyObject_Malloc(keys_size);
584 if (keys == NULL) {
585 PyErr_NoMemory();
586 return NULL;
587 }
588
589 memcpy(keys, orig->ma_keys, keys_size);
590
591 /* After copying key/value pairs, we need to incref all
592 keys and values and they are about to be co-owned by a
593 new dict object. */
594 PyDictKeyEntry *ep0 = DK_ENTRIES(keys);
595 Py_ssize_t n = keys->dk_nentries;
596 for (Py_ssize_t i = 0; i < n; i++) {
597 PyDictKeyEntry *entry = &ep0[i];
598 PyObject *value = entry->me_value;
599 Py_INCREF(value);
600 Py_INCREF(entry->me_key);
601 }
602
603 /* Since we copied the keys table we now have an extra reference
604 in the system. Manually call increment _Py_RefTotal to signal that
605 we have it now; calling dictkeys_incref would be an error as
606 keys->dk_refcnt is already set to 1 (after memcpy). */
607 #ifdef Py_REF_DEBUG
608 _Py_RefTotal++;
609 #endif
610 return keys;
611 }
612
613 /*
614 The basic lookup function used by all operations.
615 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
616 Open addressing is preferred over chaining since the link overhead for
617 chaining would be substantial (100% with typical malloc overhead).
618
619 The initial probe index is computed as hash mod the table size. Subsequent
620 probe indices are computed as explained earlier.
621
622 All arithmetic on hash should ignore overflow.
623
624 The details in this version are due to Tim Peters, building on many past
625 contributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and
626 Christian Tismer.
627
628 lookdict() is general-purpose, and may return DKIX_ERROR if (and only if) a
629 comparison raises an exception.
630 lookdict_unicode() below is specialized to string keys, comparison of which can
631 never raise an exception; that function can never return DKIX_ERROR when key
632 is string. Otherwise, it falls back to lookdict().
633 lookdict_unicode_nodummy is further specialized for string keys that cannot be
634 the <dummy> value.
635 For both, when the key isn't found a DKIX_EMPTY is returned.
636 */
637 static Py_ssize_t _Py_HOT_FUNCTION
638 lookdict(PyDictObject *mp, PyObject *key,
639 Py_hash_t hash, PyObject **value_addr)
640 {
641 size_t i, mask, perturb;
642 PyDictKeysObject *dk;
643 PyDictKeyEntry *ep0;
644
645 top:
646 dk = mp->ma_keys;
647 ep0 = DK_ENTRIES(dk);
648 mask = DK_MASK(dk);
649 perturb = hash;
650 i = (size_t)hash & mask;
651
652 for (;;) {
653 Py_ssize_t ix = dictkeys_get_index(dk, i);
654 if (ix == DKIX_EMPTY) {
655 *value_addr = NULL;
656 return ix;
657 }
658 if (ix >= 0) {
659 PyDictKeyEntry *ep = &ep0[ix];
660 assert(ep->me_key != NULL);
661 if (ep->me_key == key) {
662 *value_addr = ep->me_value;
663 return ix;
664 }
665 if (ep->me_hash == hash) {
666 PyObject *startkey = ep->me_key;
667 Py_INCREF(startkey);
668 int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
669 Py_DECREF(startkey);
670 if (cmp < 0) {
671 *value_addr = NULL;
672 return DKIX_ERROR;
673 }
674 if (dk == mp->ma_keys && ep->me_key == startkey) {
675 if (cmp > 0) {
676 *value_addr = ep->me_value;
677 return ix;
678 }
679 }
680 else {
681 /* The dict was mutated, restart */
682 goto top;
683 }
684 }
685 }
686 perturb >>= PERTURB_SHIFT;
687 i = (i*5 + perturb + 1) & mask;
688 }
689 Py_UNREACHABLE();
690 }
691
692 /* Faster version of lookdict_unicode when it is known that no <dummy> keys
693 * will be present. */
694 static Py_ssize_t _Py_HOT_FUNCTION
695 lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
696 Py_hash_t hash, PyObject **value_addr)
697 {
698 assert(mp->ma_values == NULL);
699 /* Make sure this function doesn't have to handle non-unicode keys,
700 including subclasses of str; e.g., one reason to subclass
701 unicodes is to override __eq__, and for speed we don't cater to
702 that here. */
703 if (!PyUnicode_CheckExact(key)) {
704 return lookdict(mp, key, hash, value_addr);
705 }
706
707 PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
708 size_t mask = DK_MASK(mp->ma_keys);
709 size_t perturb = (size_t)hash;
710 size_t i = (size_t)hash & mask;
711
712 for (;;) {
713 Py_ssize_t ix = dictkeys_get_index(mp->ma_keys, i);
714 assert (ix != DKIX_DUMMY);
715 if (ix == DKIX_EMPTY) {
716 *value_addr = NULL;
717 return DKIX_EMPTY;
718 }
719 PyDictKeyEntry *ep = &ep0[ix];
720 assert(ep->me_key != NULL);
721 assert(PyUnicode_CheckExact(ep->me_key));
722 if (ep->me_key == key ||
723 (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
724 *value_addr = ep->me_value;
725 return ix;
726 }
727 perturb >>= PERTURB_SHIFT;
728 i = mask & (i*5 + perturb + 1);
729 }
730 Py_UNREACHABLE();
731 }
732
733 #define MAINTAIN_TRACKING(mp, key, value) \
734 do { \
735 if (!_PyObject_GC_IS_TRACKED(mp)) { \
736 if (_PyObject_GC_MAY_BE_TRACKED(key) || \
737 _PyObject_GC_MAY_BE_TRACKED(value)) { \
738 PyObject_GC_Track(mp); \
739 } \
740 } \
741 } while(0)
742
743 /* Internal function to find slot for an item from its hash
744 when it is known that the key is not present in the dict.
745
746 The dict must be combined. */
747 static Py_ssize_t
748 find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash)
749 {
750 assert(keys != NULL);
751
752 const size_t mask = DK_MASK(keys);
753 size_t i = hash & mask;
754 Py_ssize_t ix = dictkeys_get_index(keys, i);
755 for (size_t perturb = hash; ix >= 0;) {
756 perturb >>= PERTURB_SHIFT;
757 i = (i*5 + perturb + 1) & mask;
758 ix = dictkeys_get_index(keys, i);
759 }
760 return i;
761 }
762
763 /*
764 Internal routine used by dictresize() to build a hashtable of entries.
765 */
766 static void
767 build_indices(PyDictKeysObject *keys, PyDictKeyEntry *ep, Py_ssize_t n)
768 {
769 size_t mask = (size_t)DK_SIZE(keys) - 1;
770 for (Py_ssize_t ix = 0; ix != n; ix++, ep++) {
771 Py_hash_t hash = ep->me_hash;
772 size_t i = hash & mask;
773 for (size_t perturb = hash; dictkeys_get_index(keys, i) != DKIX_EMPTY;) {
774 perturb >>= PERTURB_SHIFT;
775 i = mask & (i*5 + perturb + 1);
776 }
777 dictkeys_set_index(keys, i, ix);
778 }
779 }
780
781 static int
782 _d_PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey,
783 PyObject **pvalue, Py_hash_t *phash)
784 {
785 Py_ssize_t i;
786 PyDictObject *mp;
787 PyDictKeyEntry *entry_ptr;
788 PyObject *value;
789
790 if (!PyAnyDict_Check(op))
791 return 0;
792 mp = (PyDictObject *)op;
793 i = *ppos;
794 if (mp->ma_values) {
795 if (i < 0 || i >= mp->ma_used)
796 return 0;
797 /* values of split table is always dense */
798 entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
799 value = mp->ma_values[i];
800 assert(value != NULL);
801 }
802 else {
803 Py_ssize_t n = mp->ma_keys->dk_nentries;
804 if (i < 0 || i >= n)
805 return 0;
806 entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
807 while (i < n && entry_ptr->me_value == NULL) {
808 entry_ptr++;
809 i++;
810 }
811 if (i >= n)
812 return 0;
813 value = entry_ptr->me_value;
814 }
815 *ppos = i+1;
816 if (pkey)
817 *pkey = entry_ptr->me_key;
818 if (phash)
819 *phash = entry_ptr->me_hash;
820 if (pvalue)
821 *pvalue = value;
822 return 1;
823 }
824
825 /* Methods */
826
827 static void
828 dict_dealloc(PyDictObject *mp)
829 {
830 PyObject **values = mp->ma_values;
831 PyDictKeysObject *keys = mp->ma_keys;
832 Py_ssize_t i, n;
833
834 /* bpo-31095: UnTrack is needed before calling any callbacks */
835 PyObject_GC_UnTrack(mp);
836 Py_TRASHCAN_BEGIN(mp, dict_dealloc)
837 if (values != NULL) {
838 if (values != empty_values) {
839 for (i = 0, n = mp->ma_keys->dk_nentries; i < n; i++) {
840 Py_XDECREF(values[i]);
841 }
842 free_values(values);
843 }
844 dictkeys_decref(keys);
845 }
846 else if (keys != NULL) {
847 assert(keys->dk_refcnt == 1 || keys == Py_EMPTY_KEYS);
848 dictkeys_decref(keys);
849 }
850
851 Py_TYPE(mp)->tp_free((PyObject *)mp);
852
853 Py_TRASHCAN_END
854 }
855
856 static PyObject *
857 dict_repr(PyDictObject *mp)
858 {
859 Py_ssize_t i;
860 PyObject *key = NULL, *value = NULL;
861 _PyUnicodeWriter writer;
862 int first;
863
864 i = Py_ReprEnter((PyObject *)mp);
865 if (i != 0) {
866 return i > 0 ? PyUnicode_FromString("{...}") : NULL;
867 }
868
869 if (mp->ma_used == 0) {
870 Py_ReprLeave((PyObject *)mp);
871 return PyUnicode_FromString("{}");
872 }
873
874 _PyUnicodeWriter_Init(&writer);
875 writer.overallocate = 1;
876 /* "{" + "1: 2" + ", 3: 4" * (len - 1) + "}" */
877 writer.min_length = 1 + 4 + (2 + 4) * (mp->ma_used - 1) + 1;
878
879 if (_PyUnicodeWriter_WriteChar(&writer, '{') < 0)
880 goto error;
881
882 /* Do repr() on each key+value pair, and insert ": " between them.
883 Note that repr may mutate the dict. */
884 i = 0;
885 first = 1;
886 while (_d_PyDict_Next((PyObject *)mp, &i, &key, &value, NULL)) {
887 PyObject *s;
888 int res;
889
890 /* Prevent repr from deleting key or value during key format. */
891 Py_INCREF(key);
892 Py_INCREF(value);
893
894 if (!first) {
895 if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)
896 goto error;
897 }
898 first = 0;
899
900 s = PyObject_Repr(key);
901 if (s == NULL)
902 goto error;
903 res = _PyUnicodeWriter_WriteStr(&writer, s);
904 Py_DECREF(s);
905 if (res < 0)
906 goto error;
907
908 if (_PyUnicodeWriter_WriteASCIIString(&writer, ": ", 2) < 0)
909 goto error;
910
911 s = PyObject_Repr(value);
912 if (s == NULL)
913 goto error;
914 res = _PyUnicodeWriter_WriteStr(&writer, s);
915 Py_DECREF(s);
916 if (res < 0)
917 goto error;
918
919 Py_CLEAR(key);
920 Py_CLEAR(value);
921 }
922
923 writer.overallocate = 0;
924 if (_PyUnicodeWriter_WriteChar(&writer, '}') < 0)
925 goto error;
926
927 Py_ReprLeave((PyObject *)mp);
928
929 return _PyUnicodeWriter_Finish(&writer);
930
931 error:
932 Py_ReprLeave((PyObject *)mp);
933 _PyUnicodeWriter_Dealloc(&writer);
934 Py_XDECREF(key);
935 Py_XDECREF(value);
936 return NULL;
937 }
938
939 static Py_ssize_t
940 dict_length(PyDictObject *mp)
941 {
942 return mp->ma_used;
943 }
944
945 static PyObject *
946 dict_subscript(PyDictObject *mp, PyObject *key)
947 {
948 Py_ssize_t ix;
949 Py_hash_t hash;
950 PyObject *value;
951
952 if (!PyUnicode_CheckExact(key) ||
953 (hash = ((PyASCIIObject *) key)->hash) == -1) {
954 hash = PyObject_Hash(key);
955 if (hash == -1)
956 return NULL;
957 }
958 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
959 if (ix == DKIX_ERROR)
960 return NULL;
961 if (ix == DKIX_EMPTY || value == NULL) {
962 if (!PyAnyDict_CheckExact(mp)) {
963 /* Look up __missing__ method if we're a subclass. */
964 PyObject *missing, *res;
965 _Py_IDENTIFIER(__missing__);
966 missing = _PyObject_LookupSpecial((PyObject *)mp, &PyId___missing__);
967 if (missing != NULL) {
968 res = PyObject_CallOneArg(missing, key);
969 Py_DECREF(missing);
970 return res;
971 }
972 else if (PyErr_Occurred())
973 return NULL;
974 }
975 _PyErr_SetKeyError(key);
976 return NULL;
977 }
978 Py_INCREF(value);
979 return value;
980 }
981
982 static PyObject *
983 dict_richcompare(PyObject *v, PyObject *w, int op)
984 {
985 int cmp;
986 PyObject *res;
987
988 if (!PyAnyDict_Check(v) || !PyAnyDict_Check(w)) {
989 res = Py_NotImplemented;
990 }
991 else if (op == Py_EQ || op == Py_NE) {
992 cmp = frozendict_equal((PyDictObject *)v, (PyDictObject *)w);
993 if (cmp < 0)
994 return NULL;
995 res = (cmp == (op == Py_EQ)) ? Py_True : Py_False;
996 }
997 else
998 res = Py_NotImplemented;
999 Py_INCREF(res);
1000 return res;
1001 }
1002
1003 /*[clinic input]
1004
1005 @coexist
1006 dict.__contains__
1007
1008 key: object
1009 /
1010
1011 True if the dictionary has the specified key, else False.
1012 [clinic start generated code]*/
1013
1014 static PyObject *
1015 dict___contains__(PyDictObject *self, PyObject *key)
1016 /*[clinic end generated code: output=a3d03db709ed6e6b input=fe1cb42ad831e820]*/
1017 {
1018 register PyDictObject *mp = self;
1019 Py_hash_t hash;
1020 Py_ssize_t ix;
1021 PyObject *value;
1022
1023 if (!PyUnicode_CheckExact(key) ||
1024 (hash = ((PyASCIIObject *) key)->hash) == -1) {
1025 hash = PyObject_Hash(key);
1026 if (hash == -1)
1027 return NULL;
1028 }
1029 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
1030 if (ix == DKIX_ERROR)
1031 return NULL;
1032 if (ix == DKIX_EMPTY || value == NULL)
1033 Py_RETURN_FALSE;
1034 Py_RETURN_TRUE;
1035 }
1036
1037 /*[clinic input]
1038 dict.get
1039
1040 key: object
1041 default: object = None
1042 /
1043
1044 Return the value for key if key is in the dictionary, else default.
1045 [clinic start generated code]*/
1046
1047 static PyObject *
1048 dict_get_impl(PyDictObject *self, PyObject *key, PyObject *default_value)
1049 /*[clinic end generated code: output=bba707729dee05bf input=279ddb5790b6b107]*/
1050 {
1051 PyObject *val = NULL;
1052 Py_hash_t hash;
1053 Py_ssize_t ix;
1054
1055 if (!PyUnicode_CheckExact(key) ||
1056 (hash = ((PyASCIIObject *) key)->hash) == -1) {
1057 hash = PyObject_Hash(key);
1058 if (hash == -1)
1059 return NULL;
1060 }
1061 ix = (self->ma_keys->dk_lookup) (self, key, hash, &val);
1062 if (ix == DKIX_ERROR)
1063 return NULL;
1064 if (ix == DKIX_EMPTY || val == NULL) {
1065 val = default_value;
1066 }
1067 Py_INCREF(val);
1068 return val;
1069 }
1070
1071 static int
1072 dict_traverse(PyObject *op, visitproc visit, void *arg)
1073 {
1074 PyDictObject *mp = (PyDictObject *)op;
1075 PyDictKeysObject *keys = mp->ma_keys;
1076 PyDictKeyEntry *entries = DK_ENTRIES(keys);
1077 Py_ssize_t i, n = keys->dk_nentries;
1078
1079 if (keys->dk_lookup == lookdict) {
1080 for (i = 0; i < n; i++) {
1081 if (entries[i].me_value != NULL) {
1082 Py_VISIT(entries[i].me_value);
1083 Py_VISIT(entries[i].me_key);
1084 }
1085 }
1086 }
1087 else {
1088 if (mp->ma_values != NULL) {
1089 for (i = 0; i < n; i++) {
1090 Py_VISIT(mp->ma_values[i]);
1091 }
1092 }
1093 else {
1094 for (i = 0; i < n; i++) {
1095 Py_VISIT(entries[i].me_value);
1096 }
1097 }
1098 }
1099 return 0;
1100 }
1101
1102 static PyObject *dictiter_new(PyDictObject *, PyTypeObject *);
1103
1104 static PyObject *
1105 dict_sizeof(PyDictObject *mp, PyObject *Py_UNUSED(ignored))
1106 {
1107 return PyLong_FromSsize_t(_PyDict_SizeOf(mp));
1108 }
1109
1110 PyDoc_STRVAR(getitem__doc__, "x.__getitem__(y) <==> x[y]");
1111
1112 PyDoc_STRVAR(sizeof__doc__,
1113 "D.__sizeof__() -> size of D in memory, in bytes");
1114
1115 PyDoc_STRVAR(copy__doc__,
1116 "D.copy() -> a shallow copy of D");
1117
1118 PyDoc_STRVAR(keys__doc__,
1119 "D.keys() -> a set-like object providing a view on D's keys");
1120 PyDoc_STRVAR(items__doc__,
1121 "D.items() -> a set-like object providing a view on D's items");
1122 PyDoc_STRVAR(values__doc__,
1123 "D.values() -> an object providing a view on D's values");
1124
1125 /* Hack to implement "key in dict" */
1126 static PySequenceMethods dict_as_sequence = {
1127 0, /* sq_length */
1128 0, /* sq_concat */
1129 0, /* sq_repeat */
1130 0, /* sq_item */
1131 0, /* sq_slice */
1132 0, /* sq_ass_item */
1133 0, /* sq_ass_slice */
1134 PyDict_Contains, /* sq_contains */
1135 0, /* sq_inplace_concat */
1136 0, /* sq_inplace_repeat */
1137 };
1138
1139 /* Dictionary iterator types */
1140
1141 typedef struct {
1142 PyObject_HEAD
1143 PyDictObject *di_dict; /* Set to NULL when iterator is exhausted */
1144 Py_ssize_t di_used;
1145 Py_ssize_t di_pos;
1146 PyObject* di_result; /* reusable result tuple for iteritems */
1147 Py_ssize_t len;
1148 } dictiterobject;
1149
1150 static PyObject *
1151 dictiter_new(PyDictObject *dict, PyTypeObject *itertype)
1152 {
1153 dictiterobject *di;
1154 di = PyObject_GC_New(dictiterobject, itertype);
1155 if (di == NULL) {
1156 return NULL;
1157 }
1158 Py_INCREF(dict);
1159 di->di_dict = dict;
1160 di->di_used = dict->ma_used;
1161 di->len = dict->ma_used;
1162 if (itertype == &PyDictRevIterKey_Type ||
1163 itertype == &PyDictRevIterItem_Type ||
1164 itertype == &PyDictRevIterValue_Type) {
1165 if (dict->ma_values) {
1166 di->di_pos = dict->ma_used - 1;
1167 }
1168 else {
1169 di->di_pos = dict->ma_keys->dk_nentries - 1;
1170 }
1171 }
1172 else {
1173 di->di_pos = 0;
1174 }
1175 if (
1176 itertype == &PyFrozenDictIterItem_Type ||
1177 itertype == &PyDictRevIterItem_Type
1178 ) {
1179 di->di_result = PyTuple_Pack(2, Py_None, Py_None);
1180 if (di->di_result == NULL) {
1181 Py_DECREF(di);
1182 return NULL;
1183 }
1184 }
1185 else {
1186 di->di_result = NULL;
1187 }
1188 PyObject_GC_Track(di);
1189 return (PyObject *)di;
1190 }
1191
1192 static void
1193 dictiter_dealloc(dictiterobject *di)
1194 {
1195 /* bpo-31095: UnTrack is needed before calling any callbacks */
1196 PyObject_GC_UnTrack(di);
1197 Py_XDECREF(di->di_dict);
1198 Py_XDECREF(di->di_result);
1199 PyObject_GC_Del(di);
1200 }
1201
1202 static int
1203 dictiter_traverse(dictiterobject *di, visitproc visit, void *arg)
1204 {
1205 Py_VISIT(di->di_dict);
1206 Py_VISIT(di->di_result);
1207 return 0;
1208 }
1209
1210 static PyObject *
1211 dictiter_len(dictiterobject *di, PyObject *Py_UNUSED(ignored))
1212 {
1213 Py_ssize_t len = 0;
1214 if (di->di_dict != NULL && di->di_used == di->di_dict->ma_used)
1215 len = di->len;
1216 return PyLong_FromSize_t(len);
1217 }
1218
1219 PyDoc_STRVAR(length_hint_doc,
1220 "Private method returning an estimate of len(list(it)).");
1221
1222 static PyObject *
1223 dictiter_reduce(dictiterobject *di, PyObject *Py_UNUSED(ignored));
1224
1225 PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1226
1227 static PyMethodDef dictiter_methods[] = {
1228 {"__length_hint__", (PyCFunction)(void(*)(void))dictiter_len, METH_NOARGS,
1229 length_hint_doc},
1230 {"__reduce__", (PyCFunction)(void(*)(void))dictiter_reduce, METH_NOARGS,
1231 reduce_doc},
1232 {NULL, NULL} /* sentinel */
1233 };
1234
1235 /* dictreviter */
1236
1237 /*[clinic input]
1238 dict.__reversed__
1239
1240 Return a reverse iterator over the dict keys.
1241 [clinic start generated code]*/
1242
1243 static PyObject *
1244 dict___reversed___impl(PyDictObject *self)
1245 /*[clinic end generated code: output=e674483336d1ed51 input=23210ef3477d8c4d]*/
1246 {
1247 assert (PyAnyDict_Check(self));
1248 return dictiter_new(self, &PyDictRevIterKey_Type);
1249 }
1250
1251 static PyObject *
1252 dictiter_reduce(dictiterobject *di, PyObject *Py_UNUSED(ignored))
1253 {
1254 _Py_IDENTIFIER(iter);
1255 /* copy the iterator state */
1256 dictiterobject tmp = *di;
1257 Py_XINCREF(tmp.di_dict);
1258
1259 PyObject *list = PySequence_List((PyObject*)&tmp);
1260 Py_XDECREF(tmp.di_dict);
1261 if (list == NULL) {
1262 return NULL;
1263 }
1264 return Py_BuildValue("N(N)", _PyEval_GetBuiltinId(&PyId_iter), list);
1265 }
1266
1267 /***********************************************/
1268 /* View objects for keys(), items(), values(). */
1269 /***********************************************/
1270
1271 /* The instance lay-out is the same for all three; but the type differs. */
1272
1273 static void
1274 dictview_dealloc(_PyDictViewObject *dv)
1275 {
1276 /* bpo-31095: UnTrack is needed before calling any callbacks */
1277 PyObject_GC_UnTrack(dv);
1278 Py_XDECREF(dv->dv_dict);
1279 PyObject_GC_Del(dv);
1280 }
1281
1282 static int
1283 dictview_traverse(_PyDictViewObject *dv, visitproc visit, void *arg)
1284 {
1285 Py_VISIT(dv->dv_dict);
1286 return 0;
1287 }
1288
1289 static Py_ssize_t
1290 dictview_len(_PyDictViewObject *dv)
1291 {
1292 Py_ssize_t len = 0;
1293 if (dv->dv_dict != NULL)
1294 len = dv->dv_dict->ma_used;
1295 return len;
1296 }
1297
1298 static PyObject *
1299 _d_PyDictView_New(PyObject *dict, PyTypeObject *type)
1300 {
1301 _PyDictViewObject *dv;
1302 if (dict == NULL) {
1303 PyErr_BadInternalCall();
1304 return NULL;
1305 }
1306 if (!PyAnyDict_Check(dict)) {
1307 /* XXX Get rid of this restriction later */
1308 PyErr_Format(PyExc_TypeError,
1309 "%s() requires a dict argument, not '%s'",
1310 type->tp_name, Py_TYPE(dict)->tp_name);
1311 return NULL;
1312 }
1313 dv = PyObject_GC_New(_PyDictViewObject, type);
1314 if (dv == NULL)
1315 return NULL;
1316 Py_INCREF(dict);
1317 dv->dv_dict = (PyDictObject *)dict;
1318 PyObject_GC_Track(dv);
1319 return (PyObject *)dv;
1320 }
1321
1322 static PyObject *
1323 dictview_mapping(PyObject *view, void *Py_UNUSED(ignored)) {
1324 assert(view != NULL);
1325 assert(PyAnyDictKeys_Check(view)
1326 || PyAnyDictValues_Check(view)
1327 || PyAnyDictItems_Check(view));
1328 PyObject *mapping = (PyObject *)((_PyDictViewObject *)view)->dv_dict;
1329 return PyDictProxy_New(mapping);
1330 }
1331
1332 static PyGetSetDef dictview_getset[] = {
1333 {"mapping", dictview_mapping, (setter)NULL,
1334 "dictionary that this view refers to", NULL},
1335 {0}
1336 };
1337
1338 /* TODO(guido): The views objects are not complete:
1339
1340 * support more set operations
1341 * support arbitrary mappings?
1342 - either these should be static or exported in dictobject.h
1343 - if public then they should probably be in builtins
1344 */
1345
1346 /* Return 1 if self is a subset of other, iterating over self;
1347 0 if not; -1 if an error occurred. */
1348 static int
1349 all_contained_in(PyObject *self, PyObject *other)
1350 {
1351 PyObject *iter = PyObject_GetIter(self);
1352 int ok = 1;
1353
1354 if (iter == NULL)
1355 return -1;
1356 for (;;) {
1357 PyObject *next = PyIter_Next(iter);
1358 if (next == NULL) {
1359 if (PyErr_Occurred())
1360 ok = -1;
1361 break;
1362 }
1363 ok = PySequence_Contains(other, next);
1364 Py_DECREF(next);
1365 if (ok <= 0)
1366 break;
1367 }
1368 Py_DECREF(iter);
1369 return ok;
1370 }
1371
1372 static PyObject *
1373 dictview_richcompare(PyObject *self, PyObject *other, int op)
1374 {
1375 Py_ssize_t len_self, len_other;
1376 int ok;
1377 PyObject *result;
1378
1379 assert(self != NULL);
1380 assert(PyAnyDictViewSet_Check(self));
1381 assert(other != NULL);
1382
1383 if (!PyAnySet_Check(other) && !PyAnyDictViewSet_Check(other))
1384 Py_RETURN_NOTIMPLEMENTED;
1385
1386 len_self = PyObject_Size(self);
1387 if (len_self < 0)
1388 return NULL;
1389 len_other = PyObject_Size(other);
1390 if (len_other < 0)
1391 return NULL;
1392
1393 ok = 0;
1394 switch(op) {
1395
1396 case Py_NE:
1397 case Py_EQ:
1398 if (len_self == len_other)
1399 ok = all_contained_in(self, other);
1400 if (op == Py_NE && ok >= 0)
1401 ok = !ok;
1402 break;
1403
1404 case Py_LT:
1405 if (len_self < len_other)
1406 ok = all_contained_in(self, other);
1407 break;
1408
1409 case Py_LE:
1410 if (len_self <= len_other)
1411 ok = all_contained_in(self, other);
1412 break;
1413
1414 case Py_GT:
1415 if (len_self > len_other)
1416 ok = all_contained_in(other, self);
1417 break;
1418
1419 case Py_GE:
1420 if (len_self >= len_other)
1421 ok = all_contained_in(other, self);
1422 break;
1423
1424 }
1425 if (ok < 0)
1426 return NULL;
1427 result = ok ? Py_True : Py_False;
1428 Py_INCREF(result);
1429 return result;
1430 }
1431
1432 static PyObject *
1433 dictview_repr(_PyDictViewObject *dv)
1434 {
1435 PyObject *seq;
1436 PyObject *result = NULL;
1437 Py_ssize_t rc;
1438
1439 rc = Py_ReprEnter((PyObject *)dv);
1440 if (rc != 0) {
1441 return rc > 0 ? PyUnicode_FromString("...") : NULL;
1442 }
1443 seq = PySequence_List((PyObject *)dv);
1444 if (seq == NULL) {
1445 goto Done;
1446 }
1447 result = PyUnicode_FromFormat("%s(%R)", Py_TYPE(dv)->tp_name, seq);
1448 Py_DECREF(seq);
1449
1450 Done:
1451 Py_ReprLeave((PyObject *)dv);
1452 return result;
1453 }
1454
1455 /*** dict_keys ***/
1456
1457 static int
1458 dictkeys_contains(_PyDictViewObject *dv, PyObject *obj)
1459 {
1460 if (dv->dv_dict == NULL)
1461 return 0;
1462 return PyDict_Contains((PyObject *)dv->dv_dict, obj);
1463 }
1464
1465 static PySequenceMethods dictkeys_as_sequence = {
1466 (lenfunc)dictview_len, /* sq_length */
1467 0, /* sq_concat */
1468 0, /* sq_repeat */
1469 0, /* sq_item */
1470 0, /* sq_slice */
1471 0, /* sq_ass_item */
1472 0, /* sq_ass_slice */
1473 (objobjproc)dictkeys_contains, /* sq_contains */
1474 };
1475
1476 // Create an set object from dictviews object.
1477 // Returns a new reference.
1478 // This utility function is used by set operations.
1479 static PyObject*
1480 dictviews_to_set(PyObject *self)
1481 {
1482 PyObject *left = self;
1483 if (PyAnyDictKeys_Check(self)) {
1484 // PySet_New() has fast path for the dict object.
1485 PyObject *dict = (PyObject *)((_PyDictViewObject *)self)->dv_dict;
1486 if (PyAnyDict_CheckExact(dict)) {
1487 left = dict;
1488 }
1489 }
1490 return PySet_New(left);
1491 }
1492
1493 static PyObject*
1494 dictviews_sub(PyObject *self, PyObject *other)
1495 {
1496 PyObject *result = dictviews_to_set(self);
1497 if (result == NULL) {
1498 return NULL;
1499 }
1500
1501 _Py_IDENTIFIER(difference_update);
1502 PyObject *tmp = _PyObject_CallMethodIdOneArg(
1503 result, &PyId_difference_update, other);
1504 if (tmp == NULL) {
1505 Py_DECREF(result);
1506 return NULL;
1507 }
1508
1509 Py_DECREF(tmp);
1510 return result;
1511 }
1512
1513 static int
1514 dictitems_contains(_PyDictViewObject *dv, PyObject *obj);
1515
1516 static PyObject *
1517 _d_PyDictView_Intersect(PyObject* self, PyObject *other)
1518 {
1519 PyObject *result;
1520 PyObject *it;
1521 PyObject *key;
1522 Py_ssize_t len_self;
1523 int rv;
1524 int (*dict_contains)(_PyDictViewObject *, PyObject *);
1525
1526 /* Python interpreter swaps parameters when dict view
1527 is on right side of & */
1528 if (!PyAnyDictViewSet_Check(self)) {
1529 PyObject *tmp = other;
1530 other = self;
1531 self = tmp;
1532 }
1533
1534 len_self = dictview_len((_PyDictViewObject *)self);
1535
1536 /* if other is a set and self is smaller than other,
1537 reuse set intersection logic */
1538 if (PySet_CheckExact(other) && len_self <= PyObject_Size(other)) {
1539 _Py_IDENTIFIER(intersection);
1540 return _PyObject_CallMethodIdObjArgs(other, &PyId_intersection, self, NULL);
1541 }
1542
1543 /* if other is another dict view, and it is bigger than self,
1544 swap them */
1545 if (PyAnyDictViewSet_Check(other)) {
1546 Py_ssize_t len_other = dictview_len((_PyDictViewObject *)other);
1547 if (len_other > len_self) {
1548 PyObject *tmp = other;
1549 other = self;
1550 self = tmp;
1551 }
1552 }
1553
1554 /* at this point, two things should be true
1555 1. self is a dictview
1556 2. if other is a dictview then it is smaller than self */
1557 result = PySet_New(NULL);
1558 if (result == NULL)
1559 return NULL;
1560
1561 it = PyObject_GetIter(other);
1562 if (it == NULL) {
1563 Py_DECREF(result);
1564 return NULL;
1565 }
1566
1567 if (PyAnyDictKeys_Check(self)) {
1568 dict_contains = dictkeys_contains;
1569 }
1570 /* else PyDictItems_Check(self) */
1571 else {
1572 dict_contains = dictitems_contains;
1573 }
1574
1575 while ((key = PyIter_Next(it)) != NULL) {
1576 rv = dict_contains((_PyDictViewObject *)self, key);
1577 if (rv < 0) {
1578 goto error;
1579 }
1580 if (rv) {
1581 if (PySet_Add(result, key)) {
1582 goto error;
1583 }
1584 }
1585 Py_DECREF(key);
1586 }
1587 Py_DECREF(it);
1588 if (PyErr_Occurred()) {
1589 Py_DECREF(result);
1590 return NULL;
1591 }
1592 return result;
1593
1594 error:
1595 Py_DECREF(it);
1596 Py_DECREF(result);
1597 Py_DECREF(key);
1598 return NULL;
1599 }
1600
1601 static PyObject*
1602 dictviews_or(PyObject* self, PyObject *other)
1603 {
1604 PyObject *result = dictviews_to_set(self);
1605 if (result == NULL) {
1606 return NULL;
1607 }
1608
1609 if (_PySet_Update(result, other) < 0) {
1610 Py_DECREF(result);
1611 return NULL;
1612 }
1613 return result;
1614 }
1615
1616 static PyObject *
1617 dictitems_xor(PyObject *self, PyObject *other)
1618 {
1619 assert(PyAnyDictItems_Check(self));
1620 assert(PyAnyDictItems_Check(other));
1621 PyObject *d1 = (PyObject *)((_PyDictViewObject *)self)->dv_dict;
1622 PyObject *d2 = (PyObject *)((_PyDictViewObject *)other)->dv_dict;
1623
1624 PyObject *temp_dict;
1625
1626 if (PyDict_CheckExact(d1)) {
1627 temp_dict = PyDict_Copy(d1);
1628 }
1629 else {
1630 PyObject* args = PyTuple_New(1);
1631
1632 if (args == NULL) {
1633 return NULL;
1634 }
1635
1636 Py_INCREF(d1);
1637 PyTuple_SET_ITEM(args, 0, d1);
1638
1639 temp_dict = PyObject_Call((PyObject *) &PyDict_Type, args, NULL);
1640 Py_DECREF(args);
1641 }
1642 if (temp_dict == NULL) {
1643 return NULL;
1644 }
1645 PyObject *result_set = PySet_New(NULL);
1646 if (result_set == NULL) {
1647 Py_CLEAR(temp_dict);
1648 return NULL;
1649 }
1650
1651 PyObject *key = NULL, *val1 = NULL, *val2 = NULL;
1652 Py_ssize_t pos = 0;
1653 Py_hash_t hash;
1654
1655 while (_d_PyDict_Next(d2, &pos, &key, &val2, &hash)) {
1656 Py_INCREF(key);
1657 Py_INCREF(val2);
1658 val1 = _PyDict_GetItem_KnownHash(temp_dict, key, hash);
1659
1660 int to_delete;
1661 if (val1 == NULL) {
1662 if (PyErr_Occurred()) {
1663 goto error;
1664 }
1665 to_delete = 0;
1666 }
1667 else {
1668 Py_INCREF(val1);
1669 to_delete = PyObject_RichCompareBool(val1, val2, Py_EQ);
1670 if (to_delete < 0) {
1671 goto error;
1672 }
1673 }
1674
1675 if (to_delete) {
1676 if (_PyDict_DelItem_KnownHash(temp_dict, key, hash) < 0) {
1677 goto error;
1678 }
1679 }
1680 else {
1681 PyObject *pair = PyTuple_Pack(2, key, val2);
1682 if (pair == NULL) {
1683 goto error;
1684 }
1685 if (PySet_Add(result_set, pair) < 0) {
1686 Py_DECREF(pair);
1687 goto error;
1688 }
1689 Py_DECREF(pair);
1690 }
1691 Py_DECREF(key);
1692 Py_XDECREF(val1);
1693 Py_DECREF(val2);
1694 }
1695 key = val1 = val2 = NULL;
1696
1697 _Py_IDENTIFIER(items);
1698 PyObject *remaining_pairs = _PyObject_CallMethodIdNoArgs(temp_dict,
1699 &PyId_items);
1700 if (remaining_pairs == NULL) {
1701 goto error;
1702 }
1703 if (_PySet_Update(result_set, remaining_pairs) < 0) {
1704 Py_DECREF(remaining_pairs);
1705 goto error;
1706 }
1707 Py_DECREF(temp_dict);
1708 Py_DECREF(remaining_pairs);
1709 return result_set;
1710
1711 error:
1712 Py_XDECREF(temp_dict);
1713 Py_XDECREF(result_set);
1714 Py_XDECREF(key);
1715 Py_XDECREF(val1);
1716 Py_XDECREF(val2);
1717 return NULL;
1718 }
1719
1720 static PyObject*
1721 dictviews_xor(PyObject* self, PyObject *other)
1722 {
1723 if (PyAnyDictItems_Check(self) && PyAnyDictItems_Check(other)) {
1724 return dictitems_xor(self, other);
1725 }
1726 PyObject *result = dictviews_to_set(self);
1727 if (result == NULL) {
1728 return NULL;
1729 }
1730
1731 _Py_IDENTIFIER(symmetric_difference_update);
1732 PyObject *tmp = _PyObject_CallMethodIdOneArg(
1733 result, &PyId_symmetric_difference_update, other);
1734 if (tmp == NULL) {
1735 Py_DECREF(result);
1736 return NULL;
1737 }
1738
1739 Py_DECREF(tmp);
1740 return result;
1741 }
1742
1743 static PyNumberMethods dictviews_as_number = {
1744 0, /*nb_add*/
1745 (binaryfunc)dictviews_sub, /*nb_subtract*/
1746 0, /*nb_multiply*/
1747 0, /*nb_remainder*/
1748 0, /*nb_divmod*/
1749 0, /*nb_power*/
1750 0, /*nb_negative*/
1751 0, /*nb_positive*/
1752 0, /*nb_absolute*/
1753 0, /*nb_bool*/
1754 0, /*nb_invert*/
1755 0, /*nb_lshift*/
1756 0, /*nb_rshift*/
1757 (binaryfunc)_d_PyDictView_Intersect,/*nb_and*/
1758 (binaryfunc)dictviews_xor, /*nb_xor*/
1759 (binaryfunc)dictviews_or, /*nb_or*/
1760 };
1761
1762 static PyObject*
1763 dictviews_isdisjoint(PyObject *self, PyObject *other)
1764 {
1765 PyObject *it;
1766 PyObject *item = NULL;
1767
1768 if (self == other) {
1769 if (dictview_len((_PyDictViewObject *)self) == 0)
1770 Py_RETURN_TRUE;
1771 else
1772 Py_RETURN_FALSE;
1773 }
1774
1775 /* Iterate over the shorter object (only if other is a set,
1776 * because PySequence_Contains may be expensive otherwise): */
1777 if (PyAnySet_Check(other) || PyAnyDictViewSet_Check(other)) {
1778 Py_ssize_t len_self = dictview_len((_PyDictViewObject *)self);
1779 Py_ssize_t len_other = PyObject_Size(other);
1780 if (len_other == -1)
1781 return NULL;
1782
1783 if ((len_other > len_self)) {
1784 PyObject *tmp = other;
1785 other = self;
1786 self = tmp;
1787 }
1788 }
1789
1790 it = PyObject_GetIter(other);
1791 if (it == NULL)
1792 return NULL;
1793
1794 while ((item = PyIter_Next(it)) != NULL) {
1795 int contains = PySequence_Contains(self, item);
1796 Py_DECREF(item);
1797 if (contains == -1) {
1798 Py_DECREF(it);
1799 return NULL;
1800 }
1801
1802 if (contains) {
1803 Py_DECREF(it);
1804 Py_RETURN_FALSE;
1805 }
1806 }
1807 Py_DECREF(it);
1808 if (PyErr_Occurred())
1809 return NULL; /* PyIter_Next raised an exception. */
1810 Py_RETURN_TRUE;
1811 }
1812
1813 PyDoc_STRVAR(isdisjoint_doc,
1814 "Return True if the view and the given iterable have a null intersection.");
1815
1816 static PyObject* dictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored));
1817
1818 PyDoc_STRVAR(reversed_keys_doc,
1819 "Return a reverse iterator over the dict keys.");
1820
1821 static PyMethodDef dictkeys_methods[] = {
1822 {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
1823 isdisjoint_doc},
1824 {"__reversed__", (PyCFunction)(void(*)(void))dictkeys_reversed, METH_NOARGS,
1825 reversed_keys_doc},
1826 {NULL, NULL} /* sentinel */
1827 };
1828
1829 static PyObject *
1830 dictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
1831 {
1832 if (dv->dv_dict == NULL) {
1833 Py_RETURN_NONE;
1834 }
1835 return dictiter_new(dv->dv_dict, &PyDictRevIterKey_Type);
1836 }
1837
1838 /*** dict_items ***/
1839
1840 /* Variant of PyDict_GetItem() that doesn't suppress exceptions.
1841 This returns NULL *with* an exception set if an exception occurred.
1842 It returns NULL *without* an exception set if the key wasn't present.
1843 */
1844 static PyObject *
1845 d_PyDict_GetItemWithError(PyObject *op, PyObject *key)
1846 {
1847 Py_ssize_t ix;
1848 Py_hash_t hash;
1849 PyDictObject*mp = (PyDictObject *)op;
1850 PyObject *value;
1851
1852 if (!PyAnyDict_Check(op)) {
1853 PyErr_BadInternalCall();
1854 return NULL;
1855 }
1856 if (!PyUnicode_CheckExact(key) ||
1857 (hash = ((PyASCIIObject *) key)->hash) == -1)
1858 {
1859 hash = PyObject_Hash(key);
1860 if (hash == -1) {
1861 return NULL;
1862 }
1863 }
1864
1865 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
1866 if (ix < 0)
1867 return NULL;
1868 return value;
1869 }
1870
1871 static int
1872 dictitems_contains(_PyDictViewObject *dv, PyObject *obj)
1873 {
1874 int result;
1875 PyObject *key, *value, *found;
1876 if (dv->dv_dict == NULL)
1877 return 0;
1878 if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 2)
1879 return 0;
1880 key = PyTuple_GET_ITEM(obj, 0);
1881 value = PyTuple_GET_ITEM(obj, 1);
1882 found = d_PyDict_GetItemWithError((PyObject *)dv->dv_dict, key);
1883 if (found == NULL) {
1884 if (PyErr_Occurred())
1885 return -1;
1886 return 0;
1887 }
1888 Py_INCREF(found);
1889 result = PyObject_RichCompareBool(found, value, Py_EQ);
1890 Py_DECREF(found);
1891 return result;
1892 }
1893
1894 static PySequenceMethods dictitems_as_sequence = {
1895 (lenfunc)dictview_len, /* sq_length */
1896 0, /* sq_concat */
1897 0, /* sq_repeat */
1898 0, /* sq_item */
1899 0, /* sq_slice */
1900 0, /* sq_ass_item */
1901 0, /* sq_ass_slice */
1902 (objobjproc)dictitems_contains, /* sq_contains */
1903 };
1904
1905 static PyObject* dictitems_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored));
1906
1907 PyDoc_STRVAR(reversed_items_doc,
1908 "Return a reverse iterator over the dict items.");
1909
1910 static PyMethodDef dictitems_methods[] = {
1911 {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
1912 isdisjoint_doc},
1913 {"__reversed__", (PyCFunction)dictitems_reversed, METH_NOARGS,
1914 reversed_items_doc},
1915 {NULL, NULL} /* sentinel */
1916 };
1917
1918 static PyObject *
1919 dictitems_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
1920 {
1921 if (dv->dv_dict == NULL) {
1922 Py_RETURN_NONE;
1923 }
1924 return dictiter_new(dv->dv_dict, &PyDictRevIterItem_Type);
1925 }
1926
1927 /*** dict_values ***/
1928
1929 static PySequenceMethods dictvalues_as_sequence = {
1930 (lenfunc)dictview_len, /* sq_length */
1931 0, /* sq_concat */
1932 0, /* sq_repeat */
1933 0, /* sq_item */
1934 0, /* sq_slice */
1935 0, /* sq_ass_item */
1936 0, /* sq_ass_slice */
1937 (objobjproc)0, /* sq_contains */
1938 };
1939
1940 static PyObject* dictvalues_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored));
1941
1942 PyDoc_STRVAR(reversed_values_doc,
1943 "Return a reverse iterator over the dict values.");
1944
1945 static PyMethodDef dictvalues_methods[] = {
1946 {"__reversed__", (PyCFunction)dictvalues_reversed, METH_NOARGS,
1947 reversed_values_doc},
1948 {NULL, NULL} /* sentinel */
1949 };
1950
1951 static PyObject *
1952 dictvalues_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
1953 {
1954 if (dv->dv_dict == NULL) {
1955 Py_RETURN_NONE;
1956 }
1957 return dictiter_new(dv->dv_dict, &PyDictRevIterValue_Type);
1958 }