Nuitka
The Python compiler
Loading...
Searching...
No Matches
HelpersDictionaries.c
1// Copyright 2025, Kay Hayen, mailto:kay.hayen@gmail.com find license text at end of file
2
3/* These helpers are used to work with dictionaries.
4
5*/
6
7// This file is included from another C file, help IDEs to still parse it on
8// its own.
9#ifdef __IDE_ONLY__
10#include "nuitka/prelude.h"
11#endif
12
13// spell-checker: ignore ob_shash,dictiterobject,dictiteritems_type,dictiterkeys_type
14// spell-checker: ignore dictitervalues_type,dictviewobject dictvaluesview_type,dictkeysview_type
15
16#ifdef Py_GIL_DISABLED
17
18#define IS_DICT_SHARED(mp) _PyObject_GC_IS_SHARED(mp)
19#define SET_DICT_SHARED(mp) _PyObject_GC_SET_SHARED(mp)
20#define LOAD_INDEX(keys, size, idx) \
21 _Py_atomic_load_int##size##_relaxed(&((const int##size##_t *)keys->dk_indices)[idx]);
22#define STORE_INDEX(keys, size, idx, value) \
23 _Py_atomic_store_int##size##_relaxed(&((int##size##_t *)keys->dk_indices)[idx], (int##size##_t)value);
24
25#define LOCK_KEYS(keys) PyMutex_LockFlags(&keys->dk_mutex, _Py_LOCK_DONT_DETACH)
26#define UNLOCK_KEYS(keys) PyMutex_Unlock(&keys->dk_mutex)
27
28#define INCREF_KEYS_FT(dk) Nuitka_Py_dictkeys_incref(dk)
29#define DECREF_KEYS_FT(dk, shared) Nuitka_Py_dictkeys_decref(_PyInterpreterState_GET(), dk, shared)
30
31#define LOCK_KEYS_IF_SPLIT(keys, kind) \
32 if (kind == DICT_KEYS_SPLIT) { \
33 LOCK_KEYS(keys); \
34 }
35
36#define UNLOCK_KEYS_IF_SPLIT(keys, kind) \
37 if (kind == DICT_KEYS_SPLIT) { \
38 UNLOCK_KEYS(keys); \
39 }
40
41#else
42
43#define LOAD_INDEX(keys, size, idx) ((const int##size##_t *)(keys->dk_indices))[idx]
44#define STORE_INDEX(keys, size, idx, value) ((int##size##_t *)(keys->dk_indices))[idx] = (int##size##_t)value
45
46#define LOCK_KEYS(keys)
47#define UNLOCK_KEYS(keys)
48#define INCREF_KEYS_FT(dk)
49#define DECREF_KEYS_FT(dk, shared)
50#define LOCK_KEYS_IF_SPLIT(keys, kind)
51#define UNLOCK_KEYS_IF_SPLIT(keys, kind)
52
53#endif
54
55PyObject *DICT_GET_ITEM0(PyThreadState *tstate, PyObject *dict, PyObject *key) {
56 CHECK_OBJECT(dict);
57 assert(PyDict_Check(dict));
58
59 CHECK_OBJECT(key);
60
61 Py_hash_t hash;
62
63// This variant is uncertain about the hashing.
64#if PYTHON_VERSION < 0x300
65 if (PyString_CheckExact(key)) {
66 hash = ((PyStringObject *)key)->ob_shash;
67
68 if (unlikely(hash == -1)) {
69 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
70 }
71
72 if (unlikely(hash == -1)) {
73 return NULL;
74 }
75 } else {
76 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
77
78 if (unlikely(hash == -1)) {
79 return NULL;
80 }
81 }
82
83 PyDictObject *dict_object = (PyDictObject *)dict;
84 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
85
86 if (unlikely(entry == NULL || entry->me_value == NULL)) {
87 return NULL;
88 }
89
90 CHECK_OBJECT(entry->me_value);
91 return entry->me_value;
92#else
93 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
94 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
95
96 if (unlikely(hash == -1)) {
97 return NULL;
98 }
99 }
100
101 PyDictObject *dict_object = (PyDictObject *)dict;
102
103#if PYTHON_VERSION < 0x360
104 PyObject **value_addr;
105 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
106
107 if (unlikely(entry == NULL || *value_addr == NULL)) {
108 return NULL;
109 }
110#else
111#if PYTHON_VERSION < 0x370
112 PyObject **value_addr;
113 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
114#elif PYTHON_VERSION < 0x3b0
115 PyObject *result;
116 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
117#else
118 PyObject **value_addr;
119 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
120#endif
121
122 if (unlikely(ix < 0)) {
123 return NULL;
124 }
125#endif
126
127#if PYTHON_VERSION < 0x370 || PYTHON_VERSION >= 0x3b0
128 assert(value_addr != NULL);
129 PyObject *result = *value_addr;
130#endif
131 if (unlikely(result == NULL)) {
132 return NULL;
133 }
134
135 CHECK_OBJECT(result);
136 return result;
137#endif
138}
139
140PyObject *DICT_GET_ITEM1(PyThreadState *tstate, PyObject *dict, PyObject *key) {
141 CHECK_OBJECT(dict);
142 assert(PyDict_Check(dict));
143
144 CHECK_OBJECT(key);
145
146 Py_hash_t hash;
147
148// This variant is uncertain about the hashing.
149#if PYTHON_VERSION < 0x300
150 if (PyString_CheckExact(key)) {
151 hash = ((PyStringObject *)key)->ob_shash;
152
153 if (unlikely(hash == -1)) {
154 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
155 }
156
157 if (unlikely(hash == -1)) {
158 return NULL;
159 }
160 } else {
161 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
162
163 if (unlikely(hash == -1)) {
164 return NULL;
165 }
166 }
167
168 PyDictObject *dict_object = (PyDictObject *)dict;
169 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
170
171 if (unlikely(entry == NULL || entry->me_value == NULL)) {
172 return NULL;
173 }
174
175 CHECK_OBJECT(entry->me_value);
176 Py_INCREF(entry->me_value);
177 return entry->me_value;
178#else
179 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
180 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
181
182 if (unlikely(hash == -1)) {
183 return NULL;
184 }
185 }
186
187 PyDictObject *dict_object = (PyDictObject *)dict;
188
189#if PYTHON_VERSION < 0x360
190 PyObject **value_addr;
191 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
192
193 if (unlikely(entry == NULL || *value_addr == NULL)) {
194 return NULL;
195 }
196#else
197#if PYTHON_VERSION < 0x370
198 PyObject **value_addr;
199 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
200#elif PYTHON_VERSION < 0x3b0
201 PyObject *result;
202 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
203#else
204 PyObject **value_addr;
205 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
206#endif
207
208 if (unlikely(ix < 0)) {
209 return NULL;
210 }
211#endif
212
213#if PYTHON_VERSION < 0x370 || PYTHON_VERSION >= 0x3b0
214 assert(value_addr != NULL);
215 PyObject *result = *value_addr;
216#endif
217 if (unlikely(result == NULL)) {
218 return NULL;
219 }
220
221 CHECK_OBJECT(result);
222 Py_INCREF(result);
223 return result;
224#endif
225}
226
227#if PYTHON_VERSION >= 0x3c0
228static PyObject *Nuitka_CreateKeyError(PyThreadState *tstate, PyObject *key) {
229 return (PyObject *)Nuitka_BaseExceptionSingleArg_new(tstate, (PyTypeObject *)PyExc_KeyError, key);
230}
231#endif
232
233static void SET_CURRENT_EXCEPTION_KEY_ERROR(PyThreadState *tstate, PyObject *key) {
234#if PYTHON_VERSION < 0x3c0
235 /* Wrap all kinds of tuples, because normalization will later unwrap
236 * it, but then that changes the key for the KeyError, which is not
237 * welcome. The check is inexact, as the unwrapping one is too.
238 */
239 if (PyTuple_Check(key) || key == Py_None) {
240 PyObject *tuple = MAKE_TUPLE1(tstate, key);
241
242 SET_CURRENT_EXCEPTION_TYPE0_VALUE1(tstate, PyExc_KeyError, tuple);
243 } else {
244 SET_CURRENT_EXCEPTION_TYPE0_VALUE0(tstate, PyExc_KeyError, key);
245 }
246#else
247 struct Nuitka_ExceptionPreservationItem exception_state = {Nuitka_CreateKeyError(tstate, key)};
248
249 RESTORE_ERROR_OCCURRED_STATE(tstate, &exception_state);
250#endif
251}
252
253// TODO: This gives a reference, where would often be one time immediate users
254// of the value, forcing temporary variable releases on the outside. We need
255// to add indication of how long a value is going to be used, so in case where
256// we have the knowledge, we can provide the reference or not. Maybe we can
257// also include temporary nature of the key and/or dict releases to be done
258// inside of such helper code, possibly in template generation, where also
259// the hashing check wouldn't be needed anymore.
260PyObject *DICT_GET_ITEM_WITH_ERROR(PyThreadState *tstate, PyObject *dict, PyObject *key) {
261 CHECK_OBJECT(dict);
262 assert(PyDict_CheckExact(dict));
263
264 CHECK_OBJECT(key);
265
266 Py_hash_t hash;
267
268// This variant is uncertain about the hashing.
269#if PYTHON_VERSION < 0x300
270 if (PyString_CheckExact(key)) {
271 hash = ((PyStringObject *)key)->ob_shash;
272
273 if (unlikely(hash == -1)) {
274 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
275 }
276
277 if (unlikely(hash == -1)) {
278 return NULL;
279 }
280 } else {
281 hash = HASH_VALUE_WITH_ERROR(tstate, key);
282
283 if (unlikely(hash == -1)) {
284 return NULL;
285 }
286 }
287
288 PyDictObject *dict_object = (PyDictObject *)dict;
289 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
290
291 if (unlikely(entry == NULL || entry->me_value == NULL)) {
292 SET_CURRENT_EXCEPTION_KEY_ERROR(tstate, key);
293
294 return NULL;
295 }
296
297 CHECK_OBJECT(entry->me_value);
298 Py_INCREF(entry->me_value);
299 return entry->me_value;
300#else
301 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
302 hash = HASH_VALUE_WITH_ERROR(tstate, key);
303 if (unlikely(hash == -1)) {
304 return NULL;
305 }
306 }
307
308 PyDictObject *dict_object = (PyDictObject *)dict;
309
310#if PYTHON_VERSION < 0x360
311 PyObject **value_addr;
312 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
313
314 if (unlikely(entry == NULL || *value_addr == NULL)) {
315 if (unlikely(HAS_ERROR_OCCURRED(tstate))) {
316 return NULL;
317 }
318
319 SET_CURRENT_EXCEPTION_KEY_ERROR(tstate, key);
320
321 return NULL;
322 }
323#else
324#if PYTHON_VERSION < 0x370
325 PyObject **value_addr;
326 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
327#elif PYTHON_VERSION < 0x3b0
328 PyObject *result;
329 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
330#else
331 PyObject **value_addr;
332 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
333#endif
334
335 if (unlikely(ix < 0)) {
336 if (unlikely(HAS_ERROR_OCCURRED(tstate))) {
337 return NULL;
338 }
339
340 SET_CURRENT_EXCEPTION_KEY_ERROR(tstate, key);
341
342 return NULL;
343 }
344#endif
345
346#if PYTHON_VERSION < 0x370 || PYTHON_VERSION >= 0x3b0
347 assert(value_addr != NULL);
348 PyObject *result = *value_addr;
349#endif
350
351 if (unlikely(result == NULL)) {
352 if (unlikely(HAS_ERROR_OCCURRED(tstate))) {
353 return NULL;
354 }
355
356 SET_CURRENT_EXCEPTION_KEY_ERROR(tstate, key);
357
358 return NULL;
359 }
360
361 CHECK_OBJECT(result);
362 Py_INCREF(result);
363 return result;
364#endif
365}
366
367PyObject *DICT_GET_ITEM_WITH_HASH_ERROR0(PyThreadState *tstate, PyObject *dict, PyObject *key) {
368 CHECK_OBJECT(dict);
369 assert(PyDict_CheckExact(dict));
370
371 CHECK_OBJECT(key);
372
373 Py_hash_t hash;
374
375// This variant is uncertain about the hashing.
376#if PYTHON_VERSION < 0x300
377 if (PyString_CheckExact(key)) {
378 hash = ((PyStringObject *)key)->ob_shash;
379
380 if (unlikely(hash == -1)) {
381 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
382 }
383
384 if (unlikely(hash == -1)) {
385 return NULL;
386 }
387 } else {
388 hash = HASH_VALUE_WITH_ERROR(tstate, key);
389
390 if (unlikely(hash == -1)) {
391 return NULL;
392 }
393 }
394
395 PyDictObject *dict_object = (PyDictObject *)dict;
396 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
397
398 if (unlikely(entry == NULL || entry->me_value == NULL)) {
399 return NULL;
400 }
401
402 CHECK_OBJECT(entry->me_value);
403 return entry->me_value;
404#else
405 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
406 hash = HASH_VALUE_WITH_ERROR(tstate, key);
407 if (unlikely(hash == -1)) {
408 return NULL;
409 }
410 }
411
412 PyDictObject *dict_object = (PyDictObject *)dict;
413
414#if PYTHON_VERSION < 0x360
415 PyObject **value_addr;
416 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
417
418 if (unlikely(entry == NULL || *value_addr == NULL)) {
419 return NULL;
420 }
421#else
422#if PYTHON_VERSION < 0x370
423 PyObject **value_addr;
424 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
425#elif PYTHON_VERSION < 0x3b0
426 PyObject *result;
427 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
428#else
429 PyObject **value_addr;
430 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
431#endif
432
433 if (unlikely(ix < 0)) {
434 return NULL;
435 }
436#endif
437
438#if PYTHON_VERSION < 0x370 || PYTHON_VERSION >= 0x3b0
439 assert(value_addr != NULL);
440 PyObject *result = *value_addr;
441#endif
442
443 if (unlikely(result == NULL)) {
444 return NULL;
445 }
446
447 CHECK_OBJECT(result);
448 return result;
449#endif
450}
451
452// TODO: Exact copy of DICT_GET_ITEM_WITH_HASH_ERROR0 with just a Py_INCREF added, we should
453// generate these and all other variants rather than manually maintaining them, so we can
454// also specialize by type and not just result needs.
455PyObject *DICT_GET_ITEM_WITH_HASH_ERROR1(PyThreadState *tstate, PyObject *dict, PyObject *key) {
456 CHECK_OBJECT(dict);
457 assert(PyDict_CheckExact(dict));
458
459 CHECK_OBJECT(key);
460
461 Py_hash_t hash;
462
463// This variant is uncertain about the hashing.
464#if PYTHON_VERSION < 0x300
465 if (PyString_CheckExact(key)) {
466 hash = ((PyStringObject *)key)->ob_shash;
467
468 if (unlikely(hash == -1)) {
469 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
470 }
471
472 if (unlikely(hash == -1)) {
473 return NULL;
474 }
475 } else {
476 hash = HASH_VALUE_WITH_ERROR(tstate, key);
477
478 if (unlikely(hash == -1)) {
479 return NULL;
480 }
481 }
482
483 PyDictObject *dict_object = (PyDictObject *)dict;
484 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
485
486 if (unlikely(entry == NULL || entry->me_value == NULL)) {
487 return NULL;
488 }
489
490 CHECK_OBJECT(entry->me_value);
491 Py_INCREF(entry->me_value);
492 return entry->me_value;
493#else
494 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
495 hash = HASH_VALUE_WITH_ERROR(tstate, key);
496 if (unlikely(hash == -1)) {
497 return NULL;
498 }
499 }
500
501 PyDictObject *dict_object = (PyDictObject *)dict;
502
503#if PYTHON_VERSION < 0x360
504 PyObject **value_addr;
505 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
506
507 if (unlikely(entry == NULL || *value_addr == NULL)) {
508 return NULL;
509 }
510#else
511#if PYTHON_VERSION < 0x370
512 PyObject **value_addr;
513 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
514#elif PYTHON_VERSION < 0x3b0
515 PyObject *result;
516 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
517#else
518 PyObject **value_addr;
519 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
520#endif
521
522 if (unlikely(ix < 0)) {
523 return NULL;
524 }
525#endif
526
527#if PYTHON_VERSION < 0x370 || PYTHON_VERSION >= 0x3b0
528 assert(value_addr != NULL);
529 PyObject *result = *value_addr;
530#endif
531
532 if (unlikely(result == NULL)) {
533 return NULL;
534 }
535
536 CHECK_OBJECT(result);
537 Py_INCREF(result);
538 return result;
539#endif
540}
541
542int DICT_HAS_ITEM(PyThreadState *tstate, PyObject *dict, PyObject *key) {
543 CHECK_OBJECT(dict);
544 assert(PyDict_Check(dict));
545
546 CHECK_OBJECT(key);
547
548 Py_hash_t hash;
549
550// This variant is uncertain about the hashing.
551#if PYTHON_VERSION < 0x300
552 if (PyString_CheckExact(key)) {
553 hash = ((PyStringObject *)key)->ob_shash;
554
555 if (unlikely(hash == -1)) {
556 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
557 }
558
559 if (unlikely(hash == -1)) {
560 return -1;
561 }
562 } else {
563 hash = HASH_VALUE_WITH_ERROR(tstate, key);
564
565 if (unlikely(hash == -1)) {
566 return -1;
567 }
568 }
569
570 PyDictObject *dict_object = (PyDictObject *)dict;
571 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
572
573 if (unlikely(entry == NULL || entry->me_value == NULL)) {
574 return 0;
575 }
576
577 return 1;
578#else
579 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
580 hash = HASH_VALUE_WITH_ERROR(tstate, key);
581 if (unlikely(hash == -1)) {
582 return -1;
583 }
584 }
585
586 PyDictObject *dict_object = (PyDictObject *)dict;
587
588#if PYTHON_VERSION < 0x360
589 PyObject **value_addr;
590 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
591
592 if (unlikely(entry == NULL || *value_addr == NULL)) {
593 return 0;
594 }
595
596 return 1;
597#else
598#if PYTHON_VERSION < 0x370
599 PyObject **value_addr;
600 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
601#elif PYTHON_VERSION < 0x3b0
602 PyObject *result;
603 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
604#else
605 PyObject **value_addr;
606 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
607#endif
608
609 if (unlikely(ix < 0)) {
610 if (unlikely(HAS_ERROR_OCCURRED(tstate))) {
611 return -1;
612 }
613
614 return 0;
615 }
616
617#if PYTHON_VERSION < 0x370 || PYTHON_VERSION >= 0x3b0
618 assert(value_addr != NULL);
619 PyObject *result = *value_addr;
620#endif
621
622 if (unlikely(result == NULL)) {
623 return 0;
624 }
625#endif
626 return 1;
627#endif
628}
629
630#if PYTHON_VERSION < 0x300
631PyObject *DICT_ITEMS(PyObject *dict) {
632 CHECK_OBJECT(dict);
633 assert(PyDict_Check(dict));
634
635 PyDictObject *mp = (PyDictObject *)dict;
636
637 PyObject *result;
638 Py_ssize_t size;
639
640 /* Preallocate the list of tuples, to avoid allocations during
641 * the loop over the items, which could trigger GC, which
642 * could resize the dict. :-(
643 */
644retry:
645 size = mp->ma_used;
646 result = MAKE_LIST_EMPTY(tstate, size);
647 CHECK_OBJECT(result);
648
649 for (Py_ssize_t i = 0; i < size; i++) {
650 // Later populated.
651 PyObject *item = MAKE_TUPLE_EMPTY(tstate, 2);
652 CHECK_OBJECT(item);
653
654 PyList_SET_ITEM(result, i, item);
655 }
656
657 if (unlikely(size != mp->ma_used)) {
658 // Garbage collection can compactify dictionaries.
659 Py_DECREF(result);
660 goto retry;
661 }
662
663 // Nothing must cause any functions to be called
664 PyDictEntry *ep = mp->ma_table;
665 Py_ssize_t mask = mp->ma_mask;
666
667 for (Py_ssize_t i = 0, j = 0; i <= mask; i++) {
668 PyObject *value = ep[i].me_value;
669 if (value != NULL) {
670 PyObject *key = ep[i].me_key;
671 PyObject *item = PyList_GET_ITEM(result, j);
672 PyTuple_SET_ITEM0(item, 0, key);
673 PyTuple_SET_ITEM0(item, 1, value);
674
675 j++;
676 }
677 }
678
679 assert(PyList_GET_SIZE(result) == size);
680
681 return result;
682}
683
684#if PYTHON_VERSION < 0x300
685PyObject *DICT_KEYS(PyObject *dict) {
686 CHECK_OBJECT(dict);
687 assert(PyDict_Check(dict));
688
689 PyDictObject *mp = (PyDictObject *)dict;
690
691 PyObject *result;
692 Py_ssize_t size;
693
694 /* Preallocate the list of tuples, to avoid allocations during
695 * the loop over the items, which could trigger GC, which
696 * could resize the dict. :-(
697 */
698retry:
699 size = mp->ma_used;
700 result = MAKE_LIST_EMPTY(tstate, size);
701 CHECK_OBJECT(result);
702
703 if (unlikely(size != mp->ma_used)) {
704 // Garbage collection can compactify dictionaries.
705 Py_DECREF(result);
706 goto retry;
707 }
708
709 // Nothing must cause any functions to be called
710 PyDictEntry *ep = mp->ma_table;
711 Py_ssize_t mask = mp->ma_mask;
712
713 for (Py_ssize_t i = 0, j = 0; i <= mask; i++) {
714 PyObject *value = ep[i].me_value;
715 if (value != NULL) {
716 PyObject *key = ep[i].me_key;
717 PyList_SET_ITEM0(result, j, key);
718
719 j++;
720 }
721 }
722
723 assert(PyList_GET_SIZE(result) == size);
724
725 return result;
726}
727#endif
728
729#if PYTHON_VERSION < 0x300
730PyObject *DICT_VALUES(PyObject *dict) {
731 CHECK_OBJECT(dict);
732 assert(PyDict_Check(dict));
733
734 PyDictObject *mp = (PyDictObject *)dict;
735
736 PyObject *result;
737 Py_ssize_t size;
738
739 /* Preallocate the list of tuples, to avoid allocations during
740 * the loop over the items, which could trigger GC, which
741 * could resize the dict. :-(
742 */
743retry:
744 size = mp->ma_used;
745 result = MAKE_LIST_EMPTY(tstate, size);
746 CHECK_OBJECT(result);
747
748 if (unlikely(size != mp->ma_used)) {
749 // Garbage collection can compactify dictionaries.
750 Py_DECREF(result);
751 goto retry;
752 }
753
754 // Nothing must cause any functions to be called
755 PyDictEntry *ep = mp->ma_table;
756 Py_ssize_t mask = mp->ma_mask;
757
758 for (Py_ssize_t i = 0, j = 0; i <= mask; i++) {
759 PyObject *value = ep[i].me_value;
760 if (value != NULL) {
761 PyList_SET_ITEM0(result, j, value);
762
763 j++;
764 }
765 }
766
767 assert(PyList_GET_SIZE(result) == size);
768
769 return result;
770}
771#endif
772
773#endif
774
775#if PYTHON_VERSION < 0x300
776typedef struct {
777 PyObject_HEAD PyDictObject *di_dict;
778 Py_ssize_t di_used;
779 Py_ssize_t di_pos;
780 PyObject *di_result;
781 Py_ssize_t len;
782} dictiterobject;
783#endif
784
785#if PYTHON_VERSION >= 0x300 && PYTHON_VERSION < 0x350
786typedef struct {
787 PyObject_HEAD PyDictObject *dv_dict;
788} _PyDictViewObject;
789
790#endif
791
792// Generic helper for various dictionary iterations, to be inlined.
793static inline PyObject *_MAKE_DICT_ITERATOR(PyThreadState *tstate, PyDictObject *dict, PyTypeObject *type,
794 bool is_iteritems) {
795 CHECK_OBJECT((PyObject *)dict);
796 assert(PyDict_CheckExact((PyObject *)dict));
797
798#if PYTHON_VERSION < 0x300
799 dictiterobject *di = (dictiterobject *)Nuitka_GC_New(type);
800 CHECK_OBJECT(di);
801 Py_INCREF(dict);
802 di->di_dict = dict;
803 di->di_used = dict->ma_used;
804 di->di_pos = 0;
805 di->len = dict->ma_used;
806 if (is_iteritems) {
807 // TODO: Have this as faster variants, we do these sometimes.
808 di->di_result = MAKE_TUPLE2(tstate, Py_None, Py_None);
809 CHECK_OBJECT(di->di_result);
810 } else {
811 di->di_result = NULL;
812 }
813
814 Nuitka_GC_Track(di);
815 return (PyObject *)di;
816#else
817 _PyDictViewObject *dv = (_PyDictViewObject *)Nuitka_GC_New(type);
818 CHECK_OBJECT(dv);
819
820 Py_INCREF(dict);
821 dv->dv_dict = dict;
822
823 Nuitka_GC_Track(dv);
824 return (PyObject *)dv;
825#endif
826}
827
828PyObject *DICT_ITERITEMS(PyThreadState *tstate, PyObject *dict) {
829#if PYTHON_VERSION < 0x270
830 static PyTypeObject *dictiteritems_type = NULL;
831
832 if (unlikely(dictiteritems_type == NULL)) {
833 dictiteritems_type =
834 Py_TYPE(CALL_FUNCTION_NO_ARGS(tstate, PyObject_GetAttrString(const_dict_empty, "iteritems")));
835 }
836
837 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, dictiteritems_type, true);
838#elif PYTHON_VERSION < 0x300
839 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictIterItem_Type, true);
840#else
841 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictItems_Type, true);
842#endif
843}
844
845PyObject *DICT_ITERKEYS(PyThreadState *tstate, PyObject *dict) {
846#if PYTHON_VERSION < 0x270
847 static PyTypeObject *dictiterkeys_type = NULL;
848
849 if (unlikely(dictiterkeys_type == NULL)) {
850 dictiterkeys_type =
851 Py_TYPE(CALL_FUNCTION_NO_ARGS(tstate, PyObject_GetAttrString(const_dict_empty, "iterkeys")));
852 }
853
854 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, dictiterkeys_type, false);
855#elif PYTHON_VERSION < 0x300
856 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictIterKey_Type, false);
857#else
858 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictKeys_Type, false);
859#endif
860}
861
862PyObject *DICT_ITERVALUES(PyThreadState *tstate, PyObject *dict) {
863#if PYTHON_VERSION < 0x270
864 static PyTypeObject *dictitervalues_type = NULL;
865
866 if (unlikely(dictitervalues_type == NULL)) {
867 dictitervalues_type =
868 Py_TYPE(CALL_FUNCTION_NO_ARGS(tstate, PyObject_GetAttrString(const_dict_empty, "itervalues")));
869 }
870
871 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, dictitervalues_type, false);
872#elif PYTHON_VERSION < 0x300
873 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictIterValue_Type, false);
874#else
875 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictValues_Type, false);
876#endif
877}
878
879typedef struct {
880 PyObject_HEAD PyDictObject *dv_dict;
881} dictviewobject;
882
883static PyObject *_MAKE_DICT_VIEW(PyDictObject *dict, PyTypeObject *type) {
884 CHECK_OBJECT((PyObject *)dict);
885 assert(PyDict_CheckExact((PyObject *)dict));
886
887 dictviewobject *dv = (dictviewobject *)Nuitka_GC_New(type);
888
889 CHECK_OBJECT(dv);
890 Py_INCREF(dict);
891 dv->dv_dict = (PyDictObject *)dict;
892 Nuitka_GC_Track(dv);
893 return (PyObject *)dv;
894}
895
896PyObject *DICT_VIEWKEYS(PyObject *dict) {
897#if PYTHON_VERSION < 0x270
898 static PyTypeObject *dictkeysview_type = NULL;
899
900 if (unlikely(dictkeysview_type)) {
901 dictkeysview_type = Py_TYPE(PyObject_GetIter(PyObject_GetAttrString(const_dict_empty, "viewkeys")));
902 }
903
904 return _MAKE_DICT_VIEW((PyDictObject *)dict, dictkeysview_type);
905#else
906 return _MAKE_DICT_VIEW((PyDictObject *)dict, &PyDictKeys_Type);
907#endif
908}
909
910PyObject *DICT_VIEWVALUES(PyObject *dict) {
911#if PYTHON_VERSION < 0x270
912 static PyTypeObject *dictvaluesview_type = NULL;
913
914 if (unlikely(dictvaluesview_type)) {
915 dictvaluesview_type = Py_TYPE(PyObject_GetIter(PyObject_GetAttrString(const_dict_empty, "viewvalues")));
916 }
917
918 return _MAKE_DICT_VIEW((PyDictObject *)dict, dictvaluesview_type);
919#else
920 return _MAKE_DICT_VIEW((PyDictObject *)dict, &PyDictValues_Type);
921#endif
922}
923
924PyObject *DICT_VIEWITEMS(PyObject *dict) {
925#if PYTHON_VERSION < 0x270
926 static PyTypeObject *dictvaluesview_type = NULL;
927
928 if (unlikely(dictvaluesview_type)) {
929 dictvaluesview_type = Py_TYPE(PyObject_GetIter(PyObject_GetAttrString(const_dict_empty, "viewitems")));
930 }
931
932 return _MAKE_DICT_VIEW((PyDictObject *)dict, dictvaluesview_type);
933#else
934 return _MAKE_DICT_VIEW((PyDictObject *)dict, &PyDictItems_Type);
935#endif
936}
937
938#if PYTHON_VERSION >= 0x300
939static PyDictObject *_Nuitka_AllocatePyDictObject(PyThreadState *tstate) {
940 PyDictObject *result_mp;
941
942#if NUITKA_DICT_HAS_FREELIST
943#if PYTHON_VERSION >= 0x3e0
944 // TODO: Eliminate _Py_freelists_GET for our own version, using tstate passed in
945 result_mp = (PyDictObject *)Nuitka_PyFreeList_Pop(&_Py_freelists_GET()->dicts);
946
947 if (result_mp == NULL) {
948 result_mp = (PyDictObject *)Nuitka_GC_New(&PyDict_Type);
949 } else {
950 Nuitka_Py_NewReference((PyObject *)result_mp);
951 }
952#else
953 // This is the CPython name, spell-checker: ignore numfree
954#if PYTHON_VERSION < 0x3d0
955 PyDictObject **items = tstate->interp->dict_state.free_list;
956 int *numfree = &tstate->interp->dict_state.numfree;
957#else
958 struct _Py_object_freelists *freelists = _Nuitka_object_freelists_GET(tstate);
959 struct _Py_dict_freelist *state = &freelists->dicts;
960 PyDictObject **items = state->items;
961 int *numfree = &state->numfree;
962#endif
963
964 if (*numfree) {
965 (*numfree) -= 1;
966 result_mp = items[*numfree];
967
968 Nuitka_Py_NewReference((PyObject *)result_mp);
969 } else
970#endif
971 {
972 result_mp = (PyDictObject *)Nuitka_GC_New(&PyDict_Type);
973 }
974#else
975 result_mp = (PyDictObject *)Nuitka_GC_New(&PyDict_Type);
976#endif
977 CHECK_OBJECT(result_mp);
978 assert(PyDict_CheckExact((PyObject *)result_mp));
979 return result_mp;
980}
981#endif
982
983#if PYTHON_VERSION >= 0x360
984static PyDictKeysObject *_Nuitka_AllocatePyDictKeysObject(PyThreadState *tstate, Py_ssize_t keys_size) {
985 // CPython names, spell-checker: ignore numfree,dictkeys
986 PyDictKeysObject *dk;
987
988// TODO: Cannot always use cached objects. Need to also consider
989// "log2_size == PyDict_LOG_MINSIZE && unicode" as a criterion,
990// seems it can only be used for the smallest keys type.
991#if NUITKA_DICT_HAS_FREELIST && 0
992#if PYTHON_VERSION < 0x3d0
993 PyDictKeysObject **items = tstate->interp->dict_state.keys_free_list;
994 int *numfree = &tstate->interp->dict_state.keys_numfree;
995#else
996 struct _Py_object_freelists *freelists = _Nuitka_object_freelists_GET(tstate);
997 struct _Py_dictkeys_freelist *state = &freelists->dictkeys;
998 PyDictKeysObject **items = state->items;
999 int *numfree = &state->numfree;
1000#endif
1001
1002 if (*numfree) {
1003 (*numfree) -= 1;
1004 dk = items[*numfree];
1005 } else
1006#endif
1007 {
1008#if PYTHON_VERSION < 0x3d0
1009 dk = (PyDictKeysObject *)NuitkaObject_Malloc(keys_size);
1010#else
1011 dk = (PyDictKeysObject *)NuitkaMem_Malloc(keys_size);
1012#endif
1013 }
1014
1015 return dk;
1016}
1017#endif
1018
1019#if PYTHON_VERSION >= 0x360 && !defined(_NUITKA_EXPERIMENTAL_DISABLE_DICT_OPT)
1020
1021// Usable fraction of keys.
1022#define DK_USABLE_FRACTION(n) (((n) << 1) / 3)
1023
1024static Py_ssize_t _Nuitka_Py_PyDict_KeysSize(PyDictKeysObject *keys) {
1025#if PYTHON_VERSION < 0x360
1026 return sizeof(PyDictKeysObject) + (DK_SIZE(keys) - 1) * sizeof(PyDictKeyEntry);
1027#elif PYTHON_VERSION < 0x370
1028 return (sizeof(PyDictKeysObject) - Py_MEMBER_SIZE(PyDictKeysObject, dk_indices) + DK_IXSIZE(keys) * DK_SIZE(keys) +
1029 DK_USABLE_FRACTION(DK_SIZE(keys)) * sizeof(PyDictKeyEntry));
1030#elif PYTHON_VERSION < 0x3b0
1031 return (sizeof(PyDictKeysObject) + DK_IXSIZE(keys) * DK_SIZE(keys) +
1032 DK_USABLE_FRACTION(DK_SIZE(keys)) * sizeof(PyDictKeyEntry));
1033#else
1034 size_t entry_size = keys->dk_kind == DICT_KEYS_GENERAL ? sizeof(PyDictKeyEntry) : sizeof(PyDictUnicodeEntry);
1035 return (sizeof(PyDictKeysObject) + ((size_t)1 << keys->dk_log2_index_bytes) +
1036 DK_USABLE_FRACTION(DK_SIZE(keys)) * entry_size);
1037#endif
1038}
1039#endif
1040
1041#if PYTHON_VERSION < 0x3b0
1042typedef PyObject *PyDictValues;
1043#endif
1044
1045#if PYTHON_VERSION < 0x360
1046#define DK_ENTRIES_SIZE(keys) (keys->dk_size)
1047#elif PYTHON_VERSION < 0x3b0
1048#define DK_ENTRIES_SIZE(keys) DK_USABLE_FRACTION(DK_SIZE(keys))
1049#else
1050#define DK_ENTRIES_SIZE(keys) (keys->dk_nentries)
1051#endif
1052
1053// More than 2/3 of the keys are used, i.e. no space is wasted.
1054#if PYTHON_VERSION < 0x360
1055#define IS_COMPACT(dict_mp) (dict_mp->ma_used >= (dict_mp->ma_keys->dk_size * 2) / 3)
1056#else
1057#define IS_COMPACT(dict_mp) (dict_mp->ma_used >= (dict_mp->ma_keys->dk_nentries * 2) / 3)
1058#endif
1059
1060static inline PyDictValues *_Nuitka_PyDict_new_values(Py_ssize_t size) {
1061#if PYTHON_VERSION < 0x3b0
1062 Py_ssize_t values_size = sizeof(PyObject *) * size;
1063
1064 return (PyDictValues *)NuitkaMem_Malloc(values_size);
1065#elif PYTHON_VERSION < 0x3d0
1066 Py_ssize_t values_size = sizeof(PyObject *) * size;
1067
1068 // With Python3.11-3.12 a prefix is allocated too.
1069 size_t prefix_size = _Py_SIZE_ROUND_UP(size + 2, sizeof(PyObject *));
1070 size_t n = prefix_size + values_size;
1071 uint8_t *mem = (uint8_t *)NuitkaMem_Malloc(n);
1072 assert(mem != NULL);
1073
1074 assert(prefix_size % sizeof(PyObject *) == 0);
1075 mem[prefix_size - 1] = (uint8_t)prefix_size;
1076
1077 return (PyDictValues *)(mem + prefix_size);
1078#else
1079 assert(size >= 1);
1080 size_t suffix_size = _Py_SIZE_ROUND_UP(size, sizeof(PyObject *));
1081 assert(suffix_size < 128);
1082 assert(suffix_size % sizeof(PyObject *) == 0);
1083 size_t n = (size + 1) * sizeof(PyObject *) + suffix_size;
1084 PyDictValues *result = (PyDictValues *)NuitkaMem_Malloc(n);
1085
1086 result->embedded = 0;
1087 result->size = 0;
1088 assert(size < 256);
1089 result->capacity = (uint8_t)size;
1090 return result;
1091#endif
1092}
1093
1094#if PYTHON_VERSION >= 0x3d0
1095
1096static PyDictValues *_Nuitka_PyDict_copy_values(PyDictValues *values) {
1097 PyDictValues *new_values = _Nuitka_PyDict_new_values(values->capacity);
1098 if (unlikely(new_values == NULL)) {
1099 return NULL;
1100 }
1101
1102 new_values->size = values->size;
1103
1104 uint8_t *values_order = get_insertion_order_array(values);
1105 uint8_t *new_values_order = get_insertion_order_array(new_values);
1106
1107 memcpy(new_values_order, values_order, values->capacity);
1108
1109 for (int i = 0; i < values->capacity; i++) {
1110 new_values->values[i] = values->values[i];
1111 }
1112 assert(new_values->embedded == 0);
1113 return new_values;
1114}
1115#endif
1116
1117#include "HelpersDictionariesGenerated.c"
1118
1119void DICT_CLEAR(PyObject *dict) {
1120 CHECK_OBJECT(dict);
1121 assert(PyDict_CheckExact(dict));
1122
1123 // TODO: Could inline this for enhanced optimization, but it does
1124 // some pretty sophisticated memory handling.
1125 PyDict_Clear(dict);
1126}
1127
1128#if PYTHON_VERSION >= 0x3b0
1129static inline int Nuitka_py_get_index_from_order(PyDictObject *mp, Py_ssize_t i) {
1130 assert(mp->ma_used <= SHARED_KEYS_MAX_SIZE);
1131#if PYTHON_VERSION < 0x3d0
1132 assert(i < (((char *)mp->ma_values)[-2]));
1133 return ((char *)mp->ma_values)[-3 - i];
1134#else
1135 assert(i < mp->ma_values->size);
1136 uint8_t *array = get_insertion_order_array(mp->ma_values);
1137 return array[i];
1138#endif
1139}
1140#endif
1141
1142#if PYTHON_VERSION >= 0x3b0
1143
1144static inline Py_ssize_t Nuitka_Py_dictkeys_get_index(const PyDictKeysObject *keys, Py_ssize_t i) {
1145 int log2size = DK_LOG_SIZE(keys);
1146 Py_ssize_t ix;
1147
1148 if (log2size < 8) {
1149 ix = LOAD_INDEX(keys, 8, i);
1150
1151 } else if (log2size < 16) {
1152 ix = LOAD_INDEX(keys, 16, i);
1153 }
1154#if SIZEOF_VOID_P > 4
1155 else if (log2size >= 32) {
1156 ix = LOAD_INDEX(keys, 64, i);
1157 }
1158#endif
1159 else {
1160 ix = LOAD_INDEX(keys, 32, i);
1161 }
1162
1163 assert(ix >= DKIX_DUMMY);
1164 return ix;
1165}
1166
1167// From CPython
1168#define PERTURB_SHIFT 5
1169
1170static Py_ssize_t Nuitka_Py_unicodekeys_lookup_generic(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key,
1171 Py_hash_t hash) {
1172 PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(dk);
1173
1174 size_t mask = DK_MASK(dk);
1175 size_t perturb = hash;
1176 size_t i = (size_t)hash & mask;
1177
1178 while (1) {
1179 Py_ssize_t ix = Nuitka_Py_dictkeys_get_index(dk, i);
1180
1181 if (ix >= 0) {
1182 PyDictUnicodeEntry *ep = &ep0[ix];
1183
1184 assert(ep->me_key != NULL);
1185 assert(PyUnicode_CheckExact(ep->me_key));
1186
1187 if (ep->me_key == key) {
1188 return ix;
1189 }
1190
1191 if (Nuitka_Py_unicode_get_hash(ep->me_key) == hash) {
1192 PyObject *startkey = ep->me_key;
1193 Py_INCREF(startkey);
1194 nuitka_bool cmp = RICH_COMPARE_EQ_NBOOL_UNICODE_OBJECT(startkey, key);
1195 Py_DECREF(startkey);
1196
1197 if (unlikely(cmp == NUITKA_BOOL_EXCEPTION)) {
1198 return DKIX_ERROR;
1199 }
1200
1201 if (dk == mp->ma_keys && ep->me_key == startkey) {
1202 if (cmp == NUITKA_BOOL_TRUE) {
1203 return ix;
1204 }
1205 } else {
1206 // In case of changed dictionary, trigger restart in caller.
1207 return DKIX_KEY_CHANGED;
1208 }
1209 }
1210 } else if (ix == DKIX_EMPTY) {
1211 return DKIX_EMPTY;
1212 }
1213 perturb >>= PERTURB_SHIFT;
1214 i = mask & (i * 5 + perturb + 1);
1215 }
1216
1217 NUITKA_CANNOT_GET_HERE("Nuitka_Py_unicodekeys_lookup_generic failed");
1218}
1219
1220Py_ssize_t Nuitka_Py_unicodekeys_lookup_unicode(PyDictKeysObject *dk, PyObject *key, Py_hash_t hash) {
1221 assert(PyUnicode_CheckExact(key));
1222 assert(dk->dk_kind != DICT_KEYS_GENERAL);
1223
1224 PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(dk);
1225
1226 size_t mask = DK_MASK(dk);
1227 size_t perturb = hash;
1228 size_t i = (size_t)hash & mask;
1229
1230 while (true) {
1231 Py_ssize_t ix = Nuitka_Py_dictkeys_get_index(dk, i);
1232
1233 // Found it.
1234 if (ix >= 0) {
1235 PyDictUnicodeEntry *ep = &ep0[ix];
1236 assert(ep->me_key != NULL);
1237 assert(PyUnicode_CheckExact(ep->me_key));
1238
1239 if (ep->me_key == key || (Nuitka_Py_unicode_get_hash(ep->me_key) == hash &&
1240 RICH_COMPARE_EQ_CBOOL_UNICODE_UNICODE(ep->me_key, key))) {
1241 return ix;
1242 }
1243 } else if (ix == DKIX_EMPTY) {
1244 return DKIX_EMPTY;
1245 }
1246 perturb >>= PERTURB_SHIFT;
1247
1248 i = mask & (i * 5 + perturb + 1);
1249 ix = Nuitka_Py_dictkeys_get_index(dk, i);
1250
1251 if (ix >= 0) {
1252 PyDictUnicodeEntry *ep = &ep0[ix];
1253
1254 assert(ep->me_key != NULL);
1255 assert(PyUnicode_CheckExact(ep->me_key));
1256
1257 if (ep->me_key == key || (Nuitka_Py_unicode_get_hash(ep->me_key) == hash &&
1258 RICH_COMPARE_EQ_CBOOL_UNICODE_UNICODE(ep->me_key, key))) {
1259 return ix;
1260 }
1261 } else if (ix == DKIX_EMPTY) {
1262 return DKIX_EMPTY;
1263 }
1264
1265 perturb >>= PERTURB_SHIFT;
1266 i = mask & (i * 5 + perturb + 1);
1267 }
1268
1269 NUITKA_CANNOT_GET_HERE("Nuitka_Py_unicodekeys_lookup_unicode failed");
1270}
1271
1272// Search key from Generic table.
1273static Py_ssize_t Nuitka_Py_dictkeys_generic_lookup(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key,
1274 Py_hash_t hash) {
1275 PyDictKeyEntry *ep0 = DK_ENTRIES(dk);
1276
1277 size_t mask = DK_MASK(dk);
1278 size_t perturb = hash;
1279 size_t i = (size_t)hash & mask;
1280
1281 while (1) {
1282 Py_ssize_t ix = Nuitka_Py_dictkeys_get_index(dk, i);
1283
1284 if (ix >= 0) {
1285 PyDictKeyEntry *ep = &ep0[ix];
1286 assert(ep->me_key != NULL);
1287 if (ep->me_key == key) {
1288 return ix;
1289 }
1290 if (ep->me_hash == hash) {
1291 PyObject *startkey = ep->me_key;
1292 Py_INCREF(startkey);
1293 nuitka_bool cmp = RICH_COMPARE_EQ_NBOOL_OBJECT_OBJECT(startkey, key);
1294 Py_DECREF(startkey);
1295
1296 if (unlikely(cmp == NUITKA_BOOL_EXCEPTION)) {
1297 return DKIX_ERROR;
1298 }
1299 if (dk == mp->ma_keys && ep->me_key == startkey) {
1300 if (cmp == NUITKA_BOOL_TRUE) {
1301 return ix;
1302 }
1303 } else {
1304 // In case of changed dictionary, trigger restart in caller.
1305 return DKIX_KEY_CHANGED;
1306 }
1307 }
1308 } else if (ix == DKIX_EMPTY) {
1309 return DKIX_EMPTY;
1310 }
1311 perturb >>= PERTURB_SHIFT;
1312 i = mask & (i * 5 + perturb + 1);
1313 }
1314}
1315
1316Py_ssize_t Nuitka_PyDictLookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr) {
1317 PyDictKeysObject *dk;
1318 DictKeysKind kind;
1319 Py_ssize_t ix;
1320
1321 _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(mp);
1322restart:
1323 dk = mp->ma_keys;
1324 kind = (DictKeysKind)dk->dk_kind;
1325
1326 if (kind != DICT_KEYS_GENERAL) {
1327 if (PyUnicode_CheckExact(key)) {
1328#ifdef Py_GIL_DISABLED
1329 if (kind == DICT_KEYS_SPLIT) {
1330 ix = Nuitka_Py_unicodekeys_lookup_unicode_threadsafe(dk, key, hash);
1331
1332 if (ix == DKIX_KEY_CHANGED) {
1333 LOCK_KEYS(dk);
1334 ix = Nuitka_Py_unicodekeys_lookup_unicode(dk, key, hash);
1335 UNLOCK_KEYS(dk);
1336 }
1337 } else
1338#endif
1339 {
1340 ix = Nuitka_Py_unicodekeys_lookup_unicode(dk, key, hash);
1341 }
1342 } else {
1343 INCREF_KEYS_FT(dk);
1344 LOCK_KEYS_IF_SPLIT(dk, kind);
1345
1346 ix = Nuitka_Py_unicodekeys_lookup_generic(mp, dk, key, hash);
1347
1348 UNLOCK_KEYS_IF_SPLIT(dk, kind);
1349 DECREF_KEYS_FT(dk, IS_DICT_SHARED(mp));
1350
1351 // Dictionary lookup changed the dictionary, retry.
1352 if (ix == DKIX_KEY_CHANGED) {
1353 goto restart;
1354 }
1355 }
1356
1357 if (ix >= 0) {
1358 if (kind == DICT_KEYS_SPLIT) {
1359 *value_addr = &mp->ma_values->values[ix];
1360 } else {
1361 *value_addr = &DK_UNICODE_ENTRIES(dk)[ix].me_value;
1362 }
1363 } else {
1364 *value_addr = NULL;
1365 }
1366 } else {
1367 ix = Nuitka_Py_dictkeys_generic_lookup(mp, dk, key, hash);
1368
1369 // Dictionary lookup changed the dictionary, retry.
1370 if (ix == DKIX_KEY_CHANGED) {
1371 goto restart;
1372 }
1373
1374 if (ix >= 0) {
1375 *value_addr = &DK_ENTRIES(dk)[ix].me_value;
1376 } else {
1377 *value_addr = NULL;
1378 }
1379 }
1380
1381 return ix;
1382}
1383
1384Py_ssize_t Nuitka_PyDictLookupStr(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr) {
1385 assert(PyUnicode_CheckExact(key));
1386
1387 PyDictKeysObject *dk = mp->ma_keys;
1388 assert(dk->dk_kind != DICT_KEYS_GENERAL);
1389
1390 Py_ssize_t ix = Nuitka_Py_unicodekeys_lookup_unicode(dk, key, hash);
1391
1392 if (ix >= 0) {
1393 if (dk->dk_kind == DICT_KEYS_SPLIT) {
1394 *value_addr = &mp->ma_values->values[ix];
1395 } else {
1396 *value_addr = &DK_UNICODE_ENTRIES(dk)[ix].me_value;
1397 }
1398 } else {
1399 *value_addr = NULL;
1400 }
1401
1402 return ix;
1403}
1404
1405#endif
1406
1407bool Nuitka_DictNext(PyObject *dict, Py_ssize_t *pos, PyObject **key_ptr, PyObject **value_ptr) {
1408 CHECK_OBJECT(dict);
1409 assert(PyDict_CheckExact(dict));
1410 assert(key_ptr != NULL);
1411 assert(value_ptr != NULL);
1412
1413#if PYTHON_VERSION < 0x300
1414 Py_ssize_t i = *pos;
1415
1416 PyDictEntry *ep = ((PyDictObject *)dict)->ma_table;
1417 Py_ssize_t mask = ((PyDictObject *)dict)->ma_mask;
1418
1419 while (i <= mask && ep[i].me_value == NULL) {
1420 i++;
1421 }
1422
1423 *pos = i + 1;
1424
1425 if (i > mask) {
1426 return false;
1427 }
1428
1429 *key_ptr = ep[i].me_key;
1430 *value_ptr = ep[i].me_value;
1431
1432 return true;
1433
1434#elif PYTHON_VERSION < 0x360
1435 PyDictObject *mp = (PyDictObject *)dict;
1436 PyObject **dict_value_ptr;
1437 Py_ssize_t offset;
1438
1439 Py_ssize_t i = *pos;
1440 assert(i >= 0);
1441
1442 if (mp->ma_values) {
1443 dict_value_ptr = &mp->ma_values[i];
1444 offset = sizeof(PyObject *);
1445 } else {
1446 dict_value_ptr = &mp->ma_keys->dk_entries[i].me_value;
1447 offset = sizeof(PyDictKeyEntry);
1448 }
1449
1450 Py_ssize_t mask = DK_MASK(mp->ma_keys);
1451
1452 while ((i <= mask) && (*dict_value_ptr == NULL)) {
1453 dict_value_ptr = (PyObject **)(((char *)dict_value_ptr) + offset);
1454 i++;
1455 }
1456
1457 if (i > mask) {
1458 return false;
1459 }
1460
1461 *key_ptr = mp->ma_keys->dk_entries[i].me_key;
1462 *value_ptr = *dict_value_ptr;
1463 *pos = i + 1;
1464
1465 return true;
1466
1467#elif PYTHON_VERSION < 0x3b0
1468 PyDictObject *mp = (PyDictObject *)dict;
1469 PyDictKeyEntry *entry;
1470 PyObject *value;
1471
1472 Py_ssize_t i = *pos;
1473 assert(i >= 0);
1474
1475 if (mp->ma_values) {
1476 if (i >= mp->ma_used) {
1477 return false;
1478 }
1479
1480 entry = &DK_ENTRIES(mp->ma_keys)[i];
1481 value = DK_VALUE(mp, i);
1482
1483 assert(value != NULL);
1484 } else {
1485 Py_ssize_t n = mp->ma_keys->dk_nentries;
1486
1487 if (i >= n) {
1488 return false;
1489 }
1490
1491 entry = &DK_ENTRIES(mp->ma_keys)[i];
1492
1493 while (i < n && entry->me_value == NULL) {
1494 entry += 1;
1495 i += 1;
1496 }
1497
1498 if (i >= n) {
1499 return false;
1500 }
1501
1502 value = entry->me_value;
1503 }
1504
1505 *pos = i + 1;
1506
1507 *key_ptr = entry->me_key;
1508 *value_ptr = value;
1509
1510 return true;
1511#else
1512 PyDictObject *mp = (PyDictObject *)dict;
1513 Py_ssize_t i = *pos;
1514 PyObject *key, *value;
1515
1516 if (mp->ma_values) {
1517 // Shared keys dictionary.
1518 assert(mp->ma_used <= SHARED_KEYS_MAX_SIZE);
1519
1520 if (i >= mp->ma_used) {
1521 return false;
1522 }
1523
1524 int index = Nuitka_py_get_index_from_order(mp, i);
1525 value = mp->ma_values->values[index];
1526
1527 key = DK_UNICODE_ENTRIES(mp->ma_keys)[index].me_key;
1528
1529 assert(value != NULL);
1530 } else {
1531 Py_ssize_t n = mp->ma_keys->dk_nentries;
1532
1533 if (i >= n) {
1534 return false;
1535 }
1536
1537 // Unicode keys or general keys have different sizes, make sure to index
1538 // the right type, the algorithm is the same however.
1539 if (DK_IS_UNICODE(mp->ma_keys)) {
1540 PyDictUnicodeEntry *entry_ptr = &DK_UNICODE_ENTRIES(mp->ma_keys)[i];
1541
1542 while (i < n && entry_ptr->me_value == NULL) {
1543 entry_ptr++;
1544 i++;
1545 }
1546
1547 if (i >= n) {
1548 return false;
1549 }
1550
1551 key = entry_ptr->me_key;
1552 value = entry_ptr->me_value;
1553 } else {
1554 PyDictKeyEntry *entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
1555
1556 while (i < n && entry_ptr->me_value == NULL) {
1557 entry_ptr++;
1558 i++;
1559 }
1560
1561 if (i >= n) {
1562 return false;
1563 }
1564
1565 key = entry_ptr->me_key;
1566 value = entry_ptr->me_value;
1567 }
1568 }
1569
1570 *pos = i + 1;
1571
1572 *key_ptr = key;
1573 *value_ptr = value;
1574
1575 return true;
1576#endif
1577}
1578
1579PyObject *TO_DICT(PyThreadState *tstate, PyObject *seq_obj, PyObject *dict_obj) {
1580 PyObject *result;
1581
1582 if (seq_obj != NULL) {
1583 CHECK_OBJECT(seq_obj);
1584
1585 // Fast path for dictionaries.
1586 if (PyDict_CheckExact(seq_obj)) {
1587 result = DICT_COPY(tstate, seq_obj);
1588 } else {
1589 result = MAKE_DICT_EMPTY(tstate);
1590
1591 Py_INCREF(seq_obj);
1592
1593#if PYTHON_VERSION >= 0x300
1594 int res = HAS_ATTR_BOOL2(tstate, seq_obj, const_str_plain_keys);
1595
1596 if (unlikely(res == -1)) {
1597 Py_DECREF(seq_obj);
1598 return NULL;
1599 }
1600#else
1601 int res = HAS_ATTR_BOOL(tstate, seq_obj, const_str_plain_keys) ? 1 : 0;
1602#endif
1603
1604 if (res) {
1605 res = PyDict_Merge(result, seq_obj, 1);
1606 } else {
1607 res = PyDict_MergeFromSeq2(result, seq_obj, 1);
1608 }
1609
1610 Py_DECREF(seq_obj);
1611
1612 if (unlikely(res == -1)) {
1613 return NULL;
1614 }
1615 }
1616 } else {
1617 result = MAKE_DICT_EMPTY(tstate);
1618 }
1619
1620 // TODO: Should specialize for dict_obj/seq_obj presence to save a bit of time
1621 // and complexity.
1622 if (dict_obj != NULL) {
1623 CHECK_OBJECT(dict_obj);
1624
1625 int res = PyDict_Merge(result, dict_obj, 1);
1626
1627 if (unlikely(res == -1)) {
1628 return NULL;
1629 }
1630 }
1631
1632 return result;
1633}
1634
1635#if _NUITKA_MAINTAIN_DICT_VERSION_TAG
1636uint64_t nuitka_dict_version_tag_counter = ((uint64_t)1) << 32;
1637#endif
1638
1639#if NUITKA_DICT_HAS_FREELIST
1640PyObject *MAKE_DICT_EMPTY(PyThreadState *tstate) {
1641 PyDictObject *empty_dict_mp = (PyDictObject *)const_dict_empty;
1642
1643#if PYTHON_VERSION < 0x3c0
1644 empty_dict_mp->ma_keys->dk_refcnt++;
1645#endif
1646
1647 PyDictObject *result_mp = _Nuitka_AllocatePyDictObject(tstate);
1648
1649 result_mp->ma_keys = empty_dict_mp->ma_keys;
1650 result_mp->ma_values = empty_dict_mp->ma_values;
1651 result_mp->ma_used = 0;
1652#if PYTHON_VERSION < 0x3e0
1653#if PYTHON_VERSION >= 0x3c0
1654 result_mp->ma_version_tag = DICT_NEXT_VERSION(_PyInterpreterState_GET());
1655#elif PYTHON_VERSION >= 0x360
1656 result_mp->ma_version_tag = 1;
1657#endif
1658#endif
1659
1660 // Key reference needs to be counted on older Python
1661#if defined(Py_REF_DEBUG) && PYTHON_VERSION < 0x3c0
1662 _Py_RefTotal++;
1663#endif
1664
1665 // No Nuitka_GC_Track for the empty dictionary.
1666 return (PyObject *)result_mp;
1667}
1668#endif
1669
1670PyObject *MAKE_DICT(PyObject **pairs, Py_ssize_t size) {
1671 PyObject *result = _PyDict_NewPresized(size);
1672
1673 // Reject usage like this.
1674 assert(size > 0);
1675 for (Py_ssize_t i = 0; i < size; i++) {
1676 PyObject *key = pairs[i * 2];
1677 PyObject *value = pairs[i * 2 + 1];
1678
1679 int res = PyDict_SetItem(result, key, value);
1680
1681 if (unlikely(res != 0)) {
1682 Py_DECREF(result);
1683 return NULL;
1684 }
1685 }
1686
1687 return result;
1688}
1689
1690PyObject *MAKE_DICT_X(PyObject **pairs, Py_ssize_t size) {
1691 PyObject *result = _PyDict_NewPresized(size);
1692
1693 // Reject usage like this.
1694 assert(size > 0);
1695 for (Py_ssize_t i = 0; i < size; i++) {
1696 PyObject *value = pairs[i * 2 + 1];
1697
1698 if (value != NULL) {
1699 PyObject *key = pairs[i * 2];
1700 CHECK_OBJECT(key);
1701 CHECK_OBJECT(value);
1702
1703 int res = PyDict_SetItem(result, key, value);
1704
1705 if (unlikely(res != 0)) {
1706 Py_DECREF(result);
1707 return NULL;
1708 }
1709 }
1710 }
1711
1712 return result;
1713}
1714
1715PyObject *MAKE_DICT_X_CSTR(char const **keys, PyObject **values, Py_ssize_t size) {
1716 PyObject *result = _PyDict_NewPresized(size);
1717
1718 // Reject usage like this.
1719 assert(size > 0);
1720 for (Py_ssize_t i = 0; i < size; i++) {
1721 PyObject *value = values[i];
1722
1723 if (value != NULL) {
1724 CHECK_OBJECT(value);
1725
1726 int res = PyDict_SetItemString(result, keys[i], value);
1727
1728 if (unlikely(res != 0)) {
1729 Py_DECREF(result);
1730 return NULL;
1731 }
1732 }
1733 }
1734
1735 return result;
1736}
1737
1738// Part of "Nuitka", an optimizing Python compiler that is compatible and
1739// integrates with CPython, but also works on its own.
1740//
1741// Licensed under the Apache License, Version 2.0 (the "License");
1742// you may not use this file except in compliance with the License.
1743// You may obtain a copy of the License at
1744//
1745// http://www.apache.org/licenses/LICENSE-2.0
1746//
1747// Unless required by applicable law or agreed to in writing, software
1748// distributed under the License is distributed on an "AS IS" BASIS,
1749// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
1750// See the License for the specific language governing permissions and
1751// limitations under the License.
Nuitka_ExceptionPreservationItem
Definition exceptions.h:712
dictiterobject
Definition HelpersDictionaries.c:776
dictviewobject
Definition HelpersDictionaries.c:879