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// spell-checker: ignore qsbr,decref,dkix,ixsize
16
17// Only needed for 3.13t right now, but I suspect we'll need to remove this
18// guard later.
19#ifdef Py_GIL_DISABLED
20
21// From CPython
22#define PyDict_LOG_MINSIZE 3
23
24#if defined(WITH_FREELISTS) && PYTHON_VERSION >= 0x3d0
25static struct _Py_dictkeys_freelist *get_dictkeys_freelist(void) {
26 struct _Py_object_freelists *freelists = _Py_object_freelists_GET();
27 return &freelists->dictkeys;
28}
29#endif
30
31static void Nuitka_Py_dictkeys_free_keys_object(PyDictKeysObject *keys, bool use_qsbr) {
32#ifdef Py_GIL_DISABLED
33 if (use_qsbr) {
34 _PyMem_FreeDelayed(keys);
35 return;
36 }
37#endif
38
39#if defined(WITH_FREELISTS) && PYTHON_VERSION >= 0x3d0
40 struct _Py_dictkeys_freelist *freelist = get_dictkeys_freelist();
41 if (DK_LOG_SIZE(keys) == PyDict_LOG_MINSIZE && freelist->numfree < PyDict_MAXFREELIST && freelist->numfree >= 0 &&
42 DK_IS_UNICODE(keys)) {
43 freelist->items[freelist->numfree++] = keys;
44 return;
45 }
46#endif
47 PyMem_Free(keys);
48}
49
50#endif
51
52#ifdef Py_GIL_DISABLED
53
54static inline void ASSERT_DICT_LOCKED(PyObject *op) { _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(op); }
55#define ASSERT_DICT_LOCKED(op) ASSERT_DICT_LOCKED(_Py_CAST(PyObject *, op))
56#define ASSERT_WORLD_STOPPED_OR_DICT_LOCKED(op) \
57 if (!_PyInterpreterState_GET()->stoptheworld.world_stopped) { \
58 ASSERT_DICT_LOCKED(op); \
59 }
60#define ASSERT_WORLD_STOPPED_OR_OBJ_LOCKED(op) \
61 if (!_PyInterpreterState_GET()->stoptheworld.world_stopped) { \
62 _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(op); \
63 }
64
65#define IS_DICT_SHARED(mp) _PyObject_GC_IS_SHARED(mp)
66#define SET_DICT_SHARED(mp) _PyObject_GC_SET_SHARED(mp)
67#define LOAD_INDEX(keys, size, idx) \
68 _Py_atomic_load_int##size##_relaxed(&((const int##size##_t *)keys->dk_indices)[idx]);
69#define STORE_INDEX(keys, size, idx, value) \
70 _Py_atomic_store_int##size##_relaxed(&((int##size##_t *)keys->dk_indices)[idx], (int##size##_t)value);
71#define ASSERT_OWNED_OR_SHARED(mp) assert(_Py_IsOwnedByCurrentThread((PyObject *)mp) || IS_DICT_SHARED(mp));
72
73#define LOCK_KEYS_IF_SPLIT(keys, kind) \
74 if (kind == DICT_KEYS_SPLIT) { \
75 LOCK_KEYS(keys); \
76 }
77
78#define UNLOCK_KEYS_IF_SPLIT(keys, kind) \
79 if (kind == DICT_KEYS_SPLIT) { \
80 UNLOCK_KEYS(keys); \
81 }
82
83#define LOCK_KEYS(keys) PyMutex_LockFlags(&keys->dk_mutex, _Py_LOCK_DONT_DETACH)
84#define UNLOCK_KEYS(keys) PyMutex_Unlock(&keys->dk_mutex)
85
86#define ASSERT_KEYS_LOCKED(keys) assert(PyMutex_IsLocked(&keys->dk_mutex))
87#define LOAD_SHARED_KEY(key) _Py_atomic_load_ptr_acquire(&key)
88#define STORE_SHARED_KEY(key, value) _Py_atomic_store_ptr_release(&key, value)
89// Inc refs the keys object, giving the previous value
90#define INCREF_KEYS(dk) _Py_atomic_add_ssize(&dk->dk_refcnt, 1)
91// Dec refs the keys object, giving the previous value
92#define DECREF_KEYS(dk) _Py_atomic_add_ssize(&dk->dk_refcnt, -1)
93#define LOAD_KEYS_NENTRIES(keys) _Py_atomic_load_ssize_relaxed(&keys->dk_nentries)
94
95static inline void Nuitka_Py_dictkeys_incref(PyDictKeysObject *dk) {
96 if (FT_ATOMIC_LOAD_SSIZE_RELAXED(dk->dk_refcnt) == _Py_IMMORTAL_REFCNT) {
97 return;
98 }
99#ifdef Py_REF_DEBUG
100 _Py_IncRefTotal(_PyThreadState_GET());
101#endif
102 INCREF_KEYS(dk);
103}
104
105static inline void Nuitka_Py_dictkeys_decref(PyInterpreterState *interp, PyDictKeysObject *dk, bool use_qsbr) {
106 if (FT_ATOMIC_LOAD_SSIZE_RELAXED(dk->dk_refcnt) == _Py_IMMORTAL_REFCNT) {
107 return;
108 }
109 assert(FT_ATOMIC_LOAD_SSIZE(dk->dk_refcnt) > 0);
110#ifdef Py_REF_DEBUG
111 _Py_DecRefTotal(_PyThreadState_GET());
112#endif
113 if (DECREF_KEYS(dk) == 1) {
114 if (DK_IS_UNICODE(dk)) {
115 PyDictUnicodeEntry *entries = DK_UNICODE_ENTRIES(dk);
116 Py_ssize_t i, n;
117 for (i = 0, n = dk->dk_nentries; i < n; i++) {
118 Py_XDECREF(entries[i].me_key);
119 Py_XDECREF(entries[i].me_value);
120 }
121 } else {
122 PyDictKeyEntry *entries = DK_ENTRIES(dk);
123 Py_ssize_t i, n;
124 for (i = 0, n = dk->dk_nentries; i < n; i++) {
125 Py_XDECREF(entries[i].me_key);
126 Py_XDECREF(entries[i].me_value);
127 }
128 }
129 Nuitka_Py_dictkeys_free_keys_object(dk, use_qsbr);
130 }
131}
132
133#define INCREF_KEYS_FT(dk) Nuitka_Py_dictkeys_incref(dk)
134#define DECREF_KEYS_FT(dk, shared) Nuitka_Py_dictkeys_decref(_PyInterpreterState_GET(), dk, shared)
135
136static inline void split_keys_entry_added(PyDictKeysObject *keys) {
137 ASSERT_KEYS_LOCKED(keys);
138
139 // We increase before we decrease so we never get too small of a value
140 // when we're racing with reads
141 _Py_atomic_store_ssize_relaxed(&keys->dk_nentries, keys->dk_nentries + 1);
142 _Py_atomic_store_ssize_release(&keys->dk_usable, keys->dk_usable - 1);
143}
144
145#else /* Py_GIL_DISABLED */
146
147#define ASSERT_DICT_LOCKED(op)
148#define ASSERT_WORLD_STOPPED_OR_DICT_LOCKED(op)
149#define ASSERT_WORLD_STOPPED_OR_OBJ_LOCKED(op)
150#define LOCK_KEYS(keys)
151#define UNLOCK_KEYS(keys)
152#define ASSERT_KEYS_LOCKED(keys)
153#define LOAD_SHARED_KEY(key) key
154#define STORE_SHARED_KEY(key, value) key = value
155#define INCREF_KEYS(dk) dk->dk_refcnt++
156#define DECREF_KEYS(dk) dk->dk_refcnt--
157#define LOAD_KEYS_NENTRIES(keys) keys->dk_nentries
158#define INCREF_KEYS_FT(dk)
159#define DECREF_KEYS_FT(dk, shared)
160#define LOCK_KEYS_IF_SPLIT(keys, kind)
161#define UNLOCK_KEYS_IF_SPLIT(keys, kind)
162#define IS_DICT_SHARED(mp) (false)
163#define SET_DICT_SHARED(mp)
164#define LOAD_INDEX(keys, size, idx) ((const int##size##_t *)(keys->dk_indices))[idx]
165#define STORE_INDEX(keys, size, idx, value) ((int##size##_t *)(keys->dk_indices))[idx] = (int##size##_t)value
166#endif
167
168Py_ssize_t Nuitka_Py_dict_lookup_threadsafe(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
169
170PyObject *DICT_GET_ITEM0(PyThreadState *tstate, PyObject *dict, PyObject *key) {
171 CHECK_OBJECT(dict);
172 assert(PyDict_Check(dict));
173
174 CHECK_OBJECT(key);
175
176 Py_hash_t hash;
177
178// This variant is uncertain about the hashing.
179#if PYTHON_VERSION < 0x300
180 if (PyString_CheckExact(key)) {
181 hash = ((PyStringObject *)key)->ob_shash;
182
183 if (unlikely(hash == -1)) {
184 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
185 }
186
187 if (unlikely(hash == -1)) {
188 return NULL;
189 }
190 } else {
191 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
192
193 if (unlikely(hash == -1)) {
194 return NULL;
195 }
196 }
197
198 PyDictObject *dict_object = (PyDictObject *)dict;
199 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
200
201 if (unlikely(entry == NULL || entry->me_value == NULL)) {
202 return NULL;
203 }
204
205 CHECK_OBJECT(entry->me_value);
206 return entry->me_value;
207#else
208 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
209 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
210
211 if (unlikely(hash == -1)) {
212 return NULL;
213 }
214 }
215
216 PyDictObject *dict_object = (PyDictObject *)dict;
217
218#if PYTHON_VERSION < 0x360
219 PyObject **value_addr;
220 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
221
222 if (unlikely(entry == NULL || *value_addr == NULL)) {
223 return NULL;
224 }
225#else
226#if PYTHON_VERSION < 0x370
227 PyObject **value_addr;
228 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
229#elif PYTHON_VERSION < 0x3b0
230 PyObject *result;
231 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
232#elif defined(Py_GIL_DISABLED)
233 PyObject *result;
234 Py_ssize_t ix = Nuitka_Py_dict_lookup_threadsafe(dict_object, key, hash, &result);
235#else
236 PyObject **value_addr;
237 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
238#endif
239
240 if (unlikely(ix < 0)) {
241 return NULL;
242 }
243#endif
244
245#if PYTHON_VERSION < 0x370 || (PYTHON_VERSION >= 0x3b0 && !defined(Py_GIL_DISABLED))
246 assert(value_addr != NULL);
247 PyObject *result = *value_addr;
248#endif
249 if (unlikely(result == NULL)) {
250 return NULL;
251 }
252
253 CHECK_OBJECT(result);
254 return result;
255#endif
256}
257
258PyObject *DICT_GET_ITEM1(PyThreadState *tstate, PyObject *dict, PyObject *key) {
259 CHECK_OBJECT(dict);
260 assert(PyDict_Check(dict));
261
262 CHECK_OBJECT(key);
263
264 Py_hash_t hash;
265
266// This variant is uncertain about the hashing.
267#if PYTHON_VERSION < 0x300
268 if (PyString_CheckExact(key)) {
269 hash = ((PyStringObject *)key)->ob_shash;
270
271 if (unlikely(hash == -1)) {
272 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
273 }
274
275 if (unlikely(hash == -1)) {
276 return NULL;
277 }
278 } else {
279 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
280
281 if (unlikely(hash == -1)) {
282 return NULL;
283 }
284 }
285
286 PyDictObject *dict_object = (PyDictObject *)dict;
287 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
288
289 if (unlikely(entry == NULL || entry->me_value == NULL)) {
290 return NULL;
291 }
292
293 CHECK_OBJECT(entry->me_value);
294 Py_INCREF(entry->me_value);
295 return entry->me_value;
296#else
297 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
298 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
299
300 if (unlikely(hash == -1)) {
301 return NULL;
302 }
303 }
304
305 PyDictObject *dict_object = (PyDictObject *)dict;
306
307#if PYTHON_VERSION < 0x360
308 PyObject **value_addr;
309 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
310
311 if (unlikely(entry == NULL || *value_addr == NULL)) {
312 return NULL;
313 }
314#else
315#if PYTHON_VERSION < 0x370
316 PyObject **value_addr;
317 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
318#elif PYTHON_VERSION < 0x3b0
319 PyObject *result;
320 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
321#elif defined(Py_GIL_DISABLED)
322 PyObject *result;
323 Py_ssize_t ix = Nuitka_Py_dict_lookup_threadsafe(dict_object, key, hash, &result);
324#else
325 PyObject **value_addr;
326 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
327#endif
328
329 if (unlikely(ix < 0)) {
330 return NULL;
331 }
332#endif
333
334#if PYTHON_VERSION < 0x370 || (PYTHON_VERSION >= 0x3b0 && !defined(Py_GIL_DISABLED))
335 assert(value_addr != NULL);
336 PyObject *result = *value_addr;
337#endif
338 if (unlikely(result == NULL)) {
339 return NULL;
340 }
341
342 CHECK_OBJECT(result);
343 Py_INCREF(result);
344 return result;
345#endif
346}
347
348#if PYTHON_VERSION >= 0x3c0
349static PyObject *Nuitka_CreateKeyError(PyThreadState *tstate, PyObject *key) {
350 return (PyObject *)Nuitka_BaseExceptionSingleArg_new(tstate, (PyTypeObject *)PyExc_KeyError, key);
351}
352#endif
353
354static void SET_CURRENT_EXCEPTION_KEY_ERROR(PyThreadState *tstate, PyObject *key) {
355#if PYTHON_VERSION < 0x3c0
356 /* Wrap all kinds of tuples, because normalization will later unwrap
357 * it, but then that changes the key for the KeyError, which is not
358 * welcome. The check is inexact, as the unwrapping one is too.
359 */
360 if (PyTuple_Check(key) || key == Py_None) {
361 PyObject *tuple = MAKE_TUPLE1(tstate, key);
362
363 SET_CURRENT_EXCEPTION_TYPE0_VALUE1(tstate, PyExc_KeyError, tuple);
364 } else {
365 SET_CURRENT_EXCEPTION_TYPE0_VALUE0(tstate, PyExc_KeyError, key);
366 }
367#else
368 struct Nuitka_ExceptionPreservationItem exception_state = {Nuitka_CreateKeyError(tstate, key)};
369
370 RESTORE_ERROR_OCCURRED_STATE(tstate, &exception_state);
371#endif
372}
373
374// TODO: This gives a reference, where would often be one time immediate users
375// of the value, forcing temporary variable releases on the outside. We need
376// to add indication of how long a value is going to be used, so in case where
377// we have the knowledge, we can provide the reference or not. Maybe we can
378// also include temporary nature of the key and/or dict releases to be done
379// inside of such helper code, possibly in template generation, where also
380// the hashing check wouldn't be needed anymore.
381PyObject *DICT_GET_ITEM_WITH_ERROR(PyThreadState *tstate, PyObject *dict, PyObject *key) {
382 CHECK_OBJECT(dict);
383 assert(PyDict_CheckExact(dict));
384
385 CHECK_OBJECT(key);
386
387 Py_hash_t hash;
388
389// This variant is uncertain about the hashing.
390#if PYTHON_VERSION < 0x300
391 if (PyString_CheckExact(key)) {
392 hash = ((PyStringObject *)key)->ob_shash;
393
394 if (unlikely(hash == -1)) {
395 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
396 }
397
398 if (unlikely(hash == -1)) {
399 return NULL;
400 }
401 } else {
402 hash = HASH_VALUE_WITH_ERROR(tstate, key);
403
404 if (unlikely(hash == -1)) {
405 return NULL;
406 }
407 }
408
409 PyDictObject *dict_object = (PyDictObject *)dict;
410 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
411
412 if (unlikely(entry == NULL || entry->me_value == NULL)) {
413 SET_CURRENT_EXCEPTION_KEY_ERROR(tstate, key);
414
415 return NULL;
416 }
417
418 CHECK_OBJECT(entry->me_value);
419 Py_INCREF(entry->me_value);
420 return entry->me_value;
421#else
422 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
423 hash = HASH_VALUE_WITH_ERROR(tstate, key);
424 if (unlikely(hash == -1)) {
425 return NULL;
426 }
427 }
428
429 PyDictObject *dict_object = (PyDictObject *)dict;
430
431#if PYTHON_VERSION < 0x360
432 PyObject **value_addr;
433 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
434
435 if (unlikely(entry == NULL || *value_addr == NULL)) {
436 if (unlikely(HAS_ERROR_OCCURRED(tstate))) {
437 return NULL;
438 }
439
440 SET_CURRENT_EXCEPTION_KEY_ERROR(tstate, key);
441
442 return NULL;
443 }
444#else
445#if PYTHON_VERSION < 0x370
446 PyObject **value_addr;
447 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
448#elif PYTHON_VERSION < 0x3b0
449 PyObject *result;
450 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
451#elif defined(Py_GIL_DISABLED)
452 PyObject *result;
453 Py_ssize_t ix = Nuitka_Py_dict_lookup_threadsafe(dict_object, key, hash, &result);
454#else
455 PyObject **value_addr;
456 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
457#endif
458
459 if (unlikely(ix < 0)) {
460 if (unlikely(HAS_ERROR_OCCURRED(tstate))) {
461 return NULL;
462 }
463
464 SET_CURRENT_EXCEPTION_KEY_ERROR(tstate, key);
465
466 return NULL;
467 }
468#endif
469
470#if PYTHON_VERSION < 0x370 || (PYTHON_VERSION >= 0x3b0 && !defined(Py_GIL_DISABLED))
471 assert(value_addr != NULL);
472 PyObject *result = *value_addr;
473#endif
474
475 if (unlikely(result == NULL)) {
476 if (unlikely(HAS_ERROR_OCCURRED(tstate))) {
477 return NULL;
478 }
479
480 SET_CURRENT_EXCEPTION_KEY_ERROR(tstate, key);
481
482 return NULL;
483 }
484
485 CHECK_OBJECT(result);
486 Py_INCREF(result);
487 return result;
488#endif
489}
490
491PyObject *DICT_GET_ITEM_WITH_HASH_ERROR0(PyThreadState *tstate, PyObject *dict, PyObject *key) {
492 CHECK_OBJECT(dict);
493 assert(PyDict_CheckExact(dict));
494
495 CHECK_OBJECT(key);
496
497 Py_hash_t hash;
498
499// This variant is uncertain about the hashing.
500#if PYTHON_VERSION < 0x300
501 if (PyString_CheckExact(key)) {
502 hash = ((PyStringObject *)key)->ob_shash;
503
504 if (unlikely(hash == -1)) {
505 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
506 }
507
508 if (unlikely(hash == -1)) {
509 return NULL;
510 }
511 } else {
512 hash = HASH_VALUE_WITH_ERROR(tstate, key);
513
514 if (unlikely(hash == -1)) {
515 return NULL;
516 }
517 }
518
519 PyDictObject *dict_object = (PyDictObject *)dict;
520 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
521
522 if (unlikely(entry == NULL || entry->me_value == NULL)) {
523 return NULL;
524 }
525
526 CHECK_OBJECT(entry->me_value);
527 return entry->me_value;
528#else
529 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
530 hash = HASH_VALUE_WITH_ERROR(tstate, key);
531 if (unlikely(hash == -1)) {
532 return NULL;
533 }
534 }
535
536 PyDictObject *dict_object = (PyDictObject *)dict;
537
538#if PYTHON_VERSION < 0x360
539 PyObject **value_addr;
540 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
541
542 if (unlikely(entry == NULL || *value_addr == NULL)) {
543 return NULL;
544 }
545#else
546#if PYTHON_VERSION < 0x370
547 PyObject **value_addr;
548 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
549#elif PYTHON_VERSION < 0x3b0
550 PyObject *result;
551 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
552#elif defined(Py_GIL_DISABLED)
553 PyObject *result;
554 Py_ssize_t ix = Nuitka_Py_dict_lookup_threadsafe(dict_object, key, hash, &result);
555#else
556 PyObject **value_addr;
557 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
558#endif
559
560 if (unlikely(ix < 0)) {
561 return NULL;
562 }
563#endif
564
565#if PYTHON_VERSION < 0x370 || (PYTHON_VERSION >= 0x3b0 && !defined(Py_GIL_DISABLED))
566 assert(value_addr != NULL);
567 PyObject *result = *value_addr;
568#endif
569
570 if (unlikely(result == NULL)) {
571 return NULL;
572 }
573
574 CHECK_OBJECT(result);
575 return result;
576#endif
577}
578
579// TODO: Exact copy of DICT_GET_ITEM_WITH_HASH_ERROR0 with just a Py_INCREF added, we should
580// generate these and all other variants rather than manually maintaining them, so we can
581// also specialize by type and not just result needs.
582PyObject *DICT_GET_ITEM_WITH_HASH_ERROR1(PyThreadState *tstate, PyObject *dict, PyObject *key) {
583 CHECK_OBJECT(dict);
584 assert(PyDict_CheckExact(dict));
585
586 CHECK_OBJECT(key);
587
588 Py_hash_t hash;
589
590// This variant is uncertain about the hashing.
591#if PYTHON_VERSION < 0x300
592 if (PyString_CheckExact(key)) {
593 hash = ((PyStringObject *)key)->ob_shash;
594
595 if (unlikely(hash == -1)) {
596 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
597 }
598
599 if (unlikely(hash == -1)) {
600 return NULL;
601 }
602 } else {
603 hash = HASH_VALUE_WITH_ERROR(tstate, key);
604
605 if (unlikely(hash == -1)) {
606 return NULL;
607 }
608 }
609
610 PyDictObject *dict_object = (PyDictObject *)dict;
611 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
612
613 if (unlikely(entry == NULL || entry->me_value == NULL)) {
614 return NULL;
615 }
616
617 CHECK_OBJECT(entry->me_value);
618 Py_INCREF(entry->me_value);
619 return entry->me_value;
620#else
621 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
622 hash = HASH_VALUE_WITH_ERROR(tstate, key);
623 if (unlikely(hash == -1)) {
624 return NULL;
625 }
626 }
627
628 PyDictObject *dict_object = (PyDictObject *)dict;
629
630#if PYTHON_VERSION < 0x360
631 PyObject **value_addr;
632 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
633
634 if (unlikely(entry == NULL || *value_addr == NULL)) {
635 return NULL;
636 }
637#else
638#if PYTHON_VERSION < 0x370
639 PyObject **value_addr;
640 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
641#elif PYTHON_VERSION < 0x3b0
642 PyObject *result;
643 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
644#elif defined(Py_GIL_DISABLED)
645 PyObject *result;
646 Py_ssize_t ix = Nuitka_Py_dict_lookup_threadsafe(dict_object, key, hash, &result);
647#else
648 PyObject **value_addr;
649 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
650#endif
651
652 if (unlikely(ix < 0)) {
653 return NULL;
654 }
655#endif
656
657#if PYTHON_VERSION < 0x370 || (PYTHON_VERSION >= 0x3b0 && !defined(Py_GIL_DISABLED))
658 assert(value_addr != NULL);
659 PyObject *result = *value_addr;
660#endif
661
662 if (unlikely(result == NULL)) {
663 return NULL;
664 }
665
666 CHECK_OBJECT(result);
667 Py_INCREF(result);
668 return result;
669#endif
670}
671
672int DICT_HAS_ITEM(PyThreadState *tstate, PyObject *dict, PyObject *key) {
673 CHECK_OBJECT(dict);
674 assert(PyDict_Check(dict));
675
676 CHECK_OBJECT(key);
677
678 Py_hash_t hash;
679
680// This variant is uncertain about the hashing.
681#if PYTHON_VERSION < 0x300
682 if (PyString_CheckExact(key)) {
683 hash = ((PyStringObject *)key)->ob_shash;
684
685 if (unlikely(hash == -1)) {
686 hash = HASH_VALUE_WITHOUT_ERROR(tstate, key);
687 }
688
689 if (unlikely(hash == -1)) {
690 return -1;
691 }
692 } else {
693 hash = HASH_VALUE_WITH_ERROR(tstate, key);
694
695 if (unlikely(hash == -1)) {
696 return -1;
697 }
698 }
699
700 PyDictObject *dict_object = (PyDictObject *)dict;
701 PyDictEntry *entry = (dict_object->ma_lookup)(dict_object, key, hash);
702
703 if (unlikely(entry == NULL || entry->me_value == NULL)) {
704 return 0;
705 }
706
707 return 1;
708#else
709 if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *)key)->hash) == -1) {
710 hash = HASH_VALUE_WITH_ERROR(tstate, key);
711 if (unlikely(hash == -1)) {
712 return -1;
713 }
714 }
715
716 PyDictObject *dict_object = (PyDictObject *)dict;
717
718#if PYTHON_VERSION < 0x360
719 PyObject **value_addr;
720 PyDictKeyEntry *entry = dict_object->ma_keys->dk_lookup(dict_object, key, hash, &value_addr);
721
722 if (unlikely(entry == NULL || *value_addr == NULL)) {
723 return 0;
724 }
725
726 return 1;
727#else
728#if PYTHON_VERSION < 0x370
729 PyObject **value_addr;
730 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &value_addr, NULL);
731#elif PYTHON_VERSION < 0x3b0
732 PyObject *result;
733 Py_ssize_t ix = (dict_object->ma_keys->dk_lookup)(dict_object, key, hash, &result);
734#elif defined(Py_GIL_DISABLED)
735 PyObject *result;
736 Py_ssize_t ix = Nuitka_Py_dict_lookup_threadsafe(dict_object, key, hash, &result);
737#else
738 PyObject **value_addr;
739 Py_ssize_t ix = Nuitka_PyDictLookup(dict_object, key, hash, &value_addr);
740#endif
741
742 if (unlikely(ix < 0)) {
743 if (unlikely(HAS_ERROR_OCCURRED(tstate))) {
744 return -1;
745 }
746
747 return 0;
748 }
749
750#if PYTHON_VERSION < 0x370 || (PYTHON_VERSION >= 0x3b0 && !defined(Py_GIL_DISABLED))
751 assert(value_addr != NULL);
752 PyObject *result = *value_addr;
753#endif
754
755 if (unlikely(result == NULL)) {
756 return 0;
757 }
758#endif
759 return 1;
760#endif
761}
762
763#if PYTHON_VERSION < 0x300
764PyObject *DICT_ITEMS(PyObject *dict) {
765 CHECK_OBJECT(dict);
766 assert(PyDict_Check(dict));
767
768 PyDictObject *mp = (PyDictObject *)dict;
769
770 PyObject *result;
771 Py_ssize_t size;
772
773 /* Preallocate the list of tuples, to avoid allocations during
774 * the loop over the items, which could trigger GC, which
775 * could resize the dict. :-(
776 */
777retry:
778 size = mp->ma_used;
779 result = MAKE_LIST_EMPTY(tstate, size);
780 CHECK_OBJECT(result);
781
782 for (Py_ssize_t i = 0; i < size; i++) {
783 // Later populated.
784 PyObject *item = MAKE_TUPLE_EMPTY(tstate, 2);
785 CHECK_OBJECT(item);
786
787 PyList_SET_ITEM(result, i, item);
788 }
789
790 if (unlikely(size != mp->ma_used)) {
791 // Garbage collection can compactify dictionaries.
792 Py_DECREF(result);
793 goto retry;
794 }
795
796 // Nothing must cause any functions to be called
797 PyDictEntry *ep = mp->ma_table;
798 Py_ssize_t mask = mp->ma_mask;
799
800 for (Py_ssize_t i = 0, j = 0; i <= mask; i++) {
801 PyObject *value = ep[i].me_value;
802 if (value != NULL) {
803 PyObject *key = ep[i].me_key;
804 PyObject *item = PyList_GET_ITEM(result, j);
805 PyTuple_SET_ITEM0(item, 0, key);
806 PyTuple_SET_ITEM0(item, 1, value);
807
808 j++;
809 }
810 }
811
812 assert(PyList_GET_SIZE(result) == size);
813
814 return result;
815}
816
817#if PYTHON_VERSION < 0x300
818PyObject *DICT_KEYS(PyObject *dict) {
819 CHECK_OBJECT(dict);
820 assert(PyDict_Check(dict));
821
822 PyDictObject *mp = (PyDictObject *)dict;
823
824 PyObject *result;
825 Py_ssize_t size;
826
827 /* Preallocate the list of tuples, to avoid allocations during
828 * the loop over the items, which could trigger GC, which
829 * could resize the dict. :-(
830 */
831retry:
832 size = mp->ma_used;
833 result = MAKE_LIST_EMPTY(tstate, size);
834 CHECK_OBJECT(result);
835
836 if (unlikely(size != mp->ma_used)) {
837 // Garbage collection can compactify dictionaries.
838 Py_DECREF(result);
839 goto retry;
840 }
841
842 // Nothing must cause any functions to be called
843 PyDictEntry *ep = mp->ma_table;
844 Py_ssize_t mask = mp->ma_mask;
845
846 for (Py_ssize_t i = 0, j = 0; i <= mask; i++) {
847 PyObject *value = ep[i].me_value;
848 if (value != NULL) {
849 PyObject *key = ep[i].me_key;
850 PyList_SET_ITEM0(result, j, key);
851
852 j++;
853 }
854 }
855
856 assert(PyList_GET_SIZE(result) == size);
857
858 return result;
859}
860#endif
861
862#if PYTHON_VERSION < 0x300
863PyObject *DICT_VALUES(PyObject *dict) {
864 CHECK_OBJECT(dict);
865 assert(PyDict_Check(dict));
866
867 PyDictObject *mp = (PyDictObject *)dict;
868
869 PyObject *result;
870 Py_ssize_t size;
871
872 /* Preallocate the list of tuples, to avoid allocations during
873 * the loop over the items, which could trigger GC, which
874 * could resize the dict. :-(
875 */
876retry:
877 size = mp->ma_used;
878 result = MAKE_LIST_EMPTY(tstate, size);
879 CHECK_OBJECT(result);
880
881 if (unlikely(size != mp->ma_used)) {
882 // Garbage collection can compactify dictionaries.
883 Py_DECREF(result);
884 goto retry;
885 }
886
887 // Nothing must cause any functions to be called
888 PyDictEntry *ep = mp->ma_table;
889 Py_ssize_t mask = mp->ma_mask;
890
891 for (Py_ssize_t i = 0, j = 0; i <= mask; i++) {
892 PyObject *value = ep[i].me_value;
893 if (value != NULL) {
894 PyList_SET_ITEM0(result, j, value);
895
896 j++;
897 }
898 }
899
900 assert(PyList_GET_SIZE(result) == size);
901
902 return result;
903}
904#endif
905
906#endif
907
908#if PYTHON_VERSION < 0x300
909typedef struct {
910 PyObject_HEAD PyDictObject *di_dict;
911 Py_ssize_t di_used;
912 Py_ssize_t di_pos;
913 PyObject *di_result;
914 Py_ssize_t len;
915} dictiterobject;
916#endif
917
918#if PYTHON_VERSION >= 0x300 && PYTHON_VERSION < 0x350
919typedef struct {
920 PyObject_HEAD PyDictObject *dv_dict;
921} _PyDictViewObject;
922
923#endif
924
925// Generic helper for various dictionary iterations, to be inlined.
926static inline PyObject *_MAKE_DICT_ITERATOR(PyThreadState *tstate, PyDictObject *dict, PyTypeObject *type,
927 bool is_iteritems) {
928 CHECK_OBJECT((PyObject *)dict);
929 assert(PyDict_CheckExact((PyObject *)dict));
930
931#if PYTHON_VERSION < 0x300
932 dictiterobject *di = (dictiterobject *)Nuitka_GC_New(type);
933 CHECK_OBJECT(di);
934 Py_INCREF(dict);
935 di->di_dict = dict;
936 di->di_used = dict->ma_used;
937 di->di_pos = 0;
938 di->len = dict->ma_used;
939 if (is_iteritems) {
940 // TODO: Have this as faster variants, we do these sometimes.
941 di->di_result = MAKE_TUPLE2(tstate, Py_None, Py_None);
942 CHECK_OBJECT(di->di_result);
943 } else {
944 di->di_result = NULL;
945 }
946
947 Nuitka_GC_Track(di);
948 return (PyObject *)di;
949#else
950 _PyDictViewObject *dv = (_PyDictViewObject *)Nuitka_GC_New(type);
951 CHECK_OBJECT(dv);
952
953 Py_INCREF(dict);
954 dv->dv_dict = dict;
955
956 Nuitka_GC_Track(dv);
957 return (PyObject *)dv;
958#endif
959}
960
961PyObject *DICT_ITERITEMS(PyThreadState *tstate, PyObject *dict) {
962#if PYTHON_VERSION < 0x270
963 static PyTypeObject *dictiteritems_type = NULL;
964
965 if (unlikely(dictiteritems_type == NULL)) {
966 dictiteritems_type =
967 Py_TYPE(CALL_FUNCTION_NO_ARGS(tstate, PyObject_GetAttrString(const_dict_empty, "iteritems")));
968 }
969
970 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, dictiteritems_type, true);
971#elif PYTHON_VERSION < 0x300
972 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictIterItem_Type, true);
973#else
974 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictItems_Type, true);
975#endif
976}
977
978PyObject *DICT_ITERKEYS(PyThreadState *tstate, PyObject *dict) {
979#if PYTHON_VERSION < 0x270
980 static PyTypeObject *dictiterkeys_type = NULL;
981
982 if (unlikely(dictiterkeys_type == NULL)) {
983 dictiterkeys_type =
984 Py_TYPE(CALL_FUNCTION_NO_ARGS(tstate, PyObject_GetAttrString(const_dict_empty, "iterkeys")));
985 }
986
987 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, dictiterkeys_type, false);
988#elif PYTHON_VERSION < 0x300
989 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictIterKey_Type, false);
990#else
991 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictKeys_Type, false);
992#endif
993}
994
995PyObject *DICT_ITERVALUES(PyThreadState *tstate, PyObject *dict) {
996#if PYTHON_VERSION < 0x270
997 static PyTypeObject *dictitervalues_type = NULL;
998
999 if (unlikely(dictitervalues_type == NULL)) {
1000 dictitervalues_type =
1001 Py_TYPE(CALL_FUNCTION_NO_ARGS(tstate, PyObject_GetAttrString(const_dict_empty, "itervalues")));
1002 }
1003
1004 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, dictitervalues_type, false);
1005#elif PYTHON_VERSION < 0x300
1006 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictIterValue_Type, false);
1007#else
1008 return _MAKE_DICT_ITERATOR(tstate, (PyDictObject *)dict, &PyDictValues_Type, false);
1009#endif
1010}
1011
1012typedef struct {
1013 PyObject_HEAD PyDictObject *dv_dict;
1014} dictviewobject;
1015
1016static PyObject *_MAKE_DICT_VIEW(PyDictObject *dict, PyTypeObject *type) {
1017 CHECK_OBJECT((PyObject *)dict);
1018 assert(PyDict_CheckExact((PyObject *)dict));
1019
1020 dictviewobject *dv = (dictviewobject *)Nuitka_GC_New(type);
1021
1022 CHECK_OBJECT(dv);
1023 Py_INCREF(dict);
1024 dv->dv_dict = (PyDictObject *)dict;
1025 Nuitka_GC_Track(dv);
1026 return (PyObject *)dv;
1027}
1028
1029PyObject *DICT_VIEWKEYS(PyObject *dict) {
1030#if PYTHON_VERSION < 0x270
1031 static PyTypeObject *dictkeysview_type = NULL;
1032
1033 if (unlikely(dictkeysview_type)) {
1034 dictkeysview_type = Py_TYPE(PyObject_GetIter(PyObject_GetAttrString(const_dict_empty, "viewkeys")));
1035 }
1036
1037 return _MAKE_DICT_VIEW((PyDictObject *)dict, dictkeysview_type);
1038#else
1039 return _MAKE_DICT_VIEW((PyDictObject *)dict, &PyDictKeys_Type);
1040#endif
1041}
1042
1043PyObject *DICT_VIEWVALUES(PyObject *dict) {
1044#if PYTHON_VERSION < 0x270
1045 static PyTypeObject *dictvaluesview_type = NULL;
1046
1047 if (unlikely(dictvaluesview_type)) {
1048 dictvaluesview_type = Py_TYPE(PyObject_GetIter(PyObject_GetAttrString(const_dict_empty, "viewvalues")));
1049 }
1050
1051 return _MAKE_DICT_VIEW((PyDictObject *)dict, dictvaluesview_type);
1052#else
1053 return _MAKE_DICT_VIEW((PyDictObject *)dict, &PyDictValues_Type);
1054#endif
1055}
1056
1057PyObject *DICT_VIEWITEMS(PyObject *dict) {
1058#if PYTHON_VERSION < 0x270
1059 static PyTypeObject *dictvaluesview_type = NULL;
1060
1061 if (unlikely(dictvaluesview_type)) {
1062 dictvaluesview_type = Py_TYPE(PyObject_GetIter(PyObject_GetAttrString(const_dict_empty, "viewitems")));
1063 }
1064
1065 return _MAKE_DICT_VIEW((PyDictObject *)dict, dictvaluesview_type);
1066#else
1067 return _MAKE_DICT_VIEW((PyDictObject *)dict, &PyDictItems_Type);
1068#endif
1069}
1070
1071#if PYTHON_VERSION >= 0x300
1072static PyDictObject *_Nuitka_AllocatePyDictObject(PyThreadState *tstate) {
1073 PyDictObject *result_mp;
1074
1075#if NUITKA_DICT_HAS_FREELIST
1076#if PYTHON_VERSION >= 0x3e0
1077 // TODO: Eliminate _Py_freelists_GET for our own version, using tstate passed in
1078 result_mp = (PyDictObject *)Nuitka_PyFreeList_Pop(&_Py_freelists_GET()->dicts);
1079
1080 if (result_mp == NULL) {
1081 result_mp = (PyDictObject *)Nuitka_GC_New(&PyDict_Type);
1082 } else {
1083 Nuitka_Py_NewReference((PyObject *)result_mp);
1084 }
1085#else
1086 // This is the CPython name, spell-checker: ignore numfree
1087#if PYTHON_VERSION < 0x3d0
1088 PyDictObject **items = tstate->interp->dict_state.free_list;
1089 int *numfree = &tstate->interp->dict_state.numfree;
1090#else
1091 struct _Py_object_freelists *freelists = _Nuitka_object_freelists_GET(tstate);
1092 struct _Py_dict_freelist *state = &freelists->dicts;
1093 PyDictObject **items = state->items;
1094 int *numfree = &state->numfree;
1095#endif
1096
1097 if (*numfree) {
1098 (*numfree) -= 1;
1099 result_mp = items[*numfree];
1100
1101 Nuitka_Py_NewReference((PyObject *)result_mp);
1102 } else
1103#endif
1104 {
1105 result_mp = (PyDictObject *)Nuitka_GC_New(&PyDict_Type);
1106 }
1107#else
1108 result_mp = (PyDictObject *)Nuitka_GC_New(&PyDict_Type);
1109#endif
1110 CHECK_OBJECT(result_mp);
1111 assert(PyDict_CheckExact((PyObject *)result_mp));
1112 return result_mp;
1113}
1114#endif
1115
1116#if PYTHON_VERSION >= 0x360
1117static PyDictKeysObject *_Nuitka_AllocatePyDictKeysObject(PyThreadState *tstate, Py_ssize_t keys_size) {
1118 // CPython names, spell-checker: ignore numfree,dictkeys
1119 PyDictKeysObject *dk;
1120
1121// TODO: Cannot always use cached objects. Need to also consider
1122// "log2_size == PyDict_LOG_MINSIZE && unicode" as a criterion,
1123// seems it can only be used for the smallest keys type.
1124#if NUITKA_DICT_HAS_FREELIST && 0
1125#if PYTHON_VERSION < 0x3d0
1126 PyDictKeysObject **items = tstate->interp->dict_state.keys_free_list;
1127 int *numfree = &tstate->interp->dict_state.keys_numfree;
1128#else
1129 struct _Py_object_freelists *freelists = _Nuitka_object_freelists_GET(tstate);
1130 struct _Py_dictkeys_freelist *state = &freelists->dictkeys;
1131 PyDictKeysObject **items = state->items;
1132 int *numfree = &state->numfree;
1133#endif
1134
1135 if (*numfree) {
1136 (*numfree) -= 1;
1137 dk = items[*numfree];
1138 } else
1139#endif
1140 {
1141#if PYTHON_VERSION < 0x3d0
1142 dk = (PyDictKeysObject *)NuitkaObject_Malloc(keys_size);
1143#else
1144 dk = (PyDictKeysObject *)NuitkaMem_Malloc(keys_size);
1145#endif
1146 }
1147
1148 return dk;
1149}
1150#endif
1151
1152#if PYTHON_VERSION >= 0x360 && !defined(_NUITKA_EXPERIMENTAL_DISABLE_DICT_OPT)
1153
1154// Usable fraction of keys.
1155#define DK_USABLE_FRACTION(n) (((n) << 1) / 3)
1156
1157static Py_ssize_t _Nuitka_Py_PyDict_KeysSize(PyDictKeysObject *keys) {
1158#if PYTHON_VERSION < 0x360
1159 return sizeof(PyDictKeysObject) + (DK_SIZE(keys) - 1) * sizeof(PyDictKeyEntry);
1160#elif PYTHON_VERSION < 0x370
1161 return (sizeof(PyDictKeysObject) - Py_MEMBER_SIZE(PyDictKeysObject, dk_indices) + DK_IXSIZE(keys) * DK_SIZE(keys) +
1162 DK_USABLE_FRACTION(DK_SIZE(keys)) * sizeof(PyDictKeyEntry));
1163#elif PYTHON_VERSION < 0x3b0
1164 return (sizeof(PyDictKeysObject) + DK_IXSIZE(keys) * DK_SIZE(keys) +
1165 DK_USABLE_FRACTION(DK_SIZE(keys)) * sizeof(PyDictKeyEntry));
1166#else
1167 size_t entry_size = keys->dk_kind == DICT_KEYS_GENERAL ? sizeof(PyDictKeyEntry) : sizeof(PyDictUnicodeEntry);
1168 return (sizeof(PyDictKeysObject) + ((size_t)1 << keys->dk_log2_index_bytes) +
1169 DK_USABLE_FRACTION(DK_SIZE(keys)) * entry_size);
1170#endif
1171}
1172#endif
1173
1174#if PYTHON_VERSION < 0x3b0
1175typedef PyObject *PyDictValues;
1176#endif
1177
1178#if PYTHON_VERSION < 0x360
1179#define DK_ENTRIES_SIZE(keys) (keys->dk_size)
1180#elif PYTHON_VERSION < 0x3b0
1181#define DK_ENTRIES_SIZE(keys) DK_USABLE_FRACTION(DK_SIZE(keys))
1182#else
1183#define DK_ENTRIES_SIZE(keys) (keys->dk_nentries)
1184#endif
1185
1186// More than 2/3 of the keys are used, i.e. no space is wasted.
1187#if PYTHON_VERSION < 0x360
1188#define IS_COMPACT(dict_mp) (dict_mp->ma_used >= (dict_mp->ma_keys->dk_size * 2) / 3)
1189#else
1190#define IS_COMPACT(dict_mp) (dict_mp->ma_used >= (dict_mp->ma_keys->dk_nentries * 2) / 3)
1191#endif
1192
1193static inline PyDictValues *_Nuitka_PyDict_new_values(Py_ssize_t size) {
1194#if PYTHON_VERSION < 0x3b0
1195 Py_ssize_t values_size = sizeof(PyObject *) * size;
1196
1197 return (PyDictValues *)NuitkaMem_Malloc(values_size);
1198#elif PYTHON_VERSION < 0x3d0
1199 Py_ssize_t values_size = sizeof(PyObject *) * size;
1200
1201 // With Python3.11-3.12 a prefix is allocated too.
1202 size_t prefix_size = _Py_SIZE_ROUND_UP(size + 2, sizeof(PyObject *));
1203 size_t n = prefix_size + values_size;
1204 uint8_t *mem = (uint8_t *)NuitkaMem_Malloc(n);
1205 assert(mem != NULL);
1206
1207 assert(prefix_size % sizeof(PyObject *) == 0);
1208 mem[prefix_size - 1] = (uint8_t)prefix_size;
1209
1210 return (PyDictValues *)(mem + prefix_size);
1211#else
1212 assert(size >= 1);
1213 size_t suffix_size = _Py_SIZE_ROUND_UP(size, sizeof(PyObject *));
1214 assert(suffix_size < 128);
1215 assert(suffix_size % sizeof(PyObject *) == 0);
1216 size_t n = (size + 1) * sizeof(PyObject *) + suffix_size;
1217 PyDictValues *result = (PyDictValues *)NuitkaMem_Malloc(n);
1218
1219 result->embedded = 0;
1220 result->size = 0;
1221 assert(size < 256);
1222 result->capacity = (uint8_t)size;
1223 return result;
1224#endif
1225}
1226
1227#if PYTHON_VERSION >= 0x3d0
1228
1229static PyDictValues *_Nuitka_PyDict_copy_values(PyDictValues *values) {
1230 PyDictValues *new_values = _Nuitka_PyDict_new_values(values->capacity);
1231 if (unlikely(new_values == NULL)) {
1232 return NULL;
1233 }
1234
1235 new_values->size = values->size;
1236
1237 uint8_t *values_order = get_insertion_order_array(values);
1238 uint8_t *new_values_order = get_insertion_order_array(new_values);
1239
1240 memcpy(new_values_order, values_order, values->capacity);
1241
1242 for (int i = 0; i < values->capacity; i++) {
1243 new_values->values[i] = values->values[i];
1244 }
1245 assert(new_values->embedded == 0);
1246 return new_values;
1247}
1248#endif
1249
1250#include "HelpersDictionariesGenerated.c"
1251
1252void DICT_CLEAR(PyObject *dict) {
1253 CHECK_OBJECT(dict);
1254 assert(PyDict_CheckExact(dict));
1255
1256 // TODO: Could inline this for enhanced optimization, but it does
1257 // some pretty sophisticated memory handling.
1258 PyDict_Clear(dict);
1259}
1260
1261#if PYTHON_VERSION >= 0x3b0
1262static inline int Nuitka_py_get_index_from_order(PyDictObject *mp, Py_ssize_t i) {
1263 assert(mp->ma_used <= SHARED_KEYS_MAX_SIZE);
1264#if PYTHON_VERSION < 0x3d0
1265 assert(i < (((char *)mp->ma_values)[-2]));
1266 return ((char *)mp->ma_values)[-3 - i];
1267#else
1268 assert(i < mp->ma_values->size);
1269 uint8_t *array = get_insertion_order_array(mp->ma_values);
1270 return array[i];
1271#endif
1272}
1273#endif
1274
1275#if PYTHON_VERSION >= 0x3b0
1276
1277static inline Py_ssize_t Nuitka_Py_dictkeys_get_index(const PyDictKeysObject *keys, Py_ssize_t i) {
1278 int log2size = DK_LOG_SIZE(keys);
1279 Py_ssize_t ix;
1280
1281 if (log2size < 8) {
1282 ix = LOAD_INDEX(keys, 8, i);
1283
1284 } else if (log2size < 16) {
1285 ix = LOAD_INDEX(keys, 16, i);
1286 }
1287#if SIZEOF_VOID_P > 4
1288 else if (log2size >= 32) {
1289 ix = LOAD_INDEX(keys, 64, i);
1290 }
1291#endif
1292 else {
1293 ix = LOAD_INDEX(keys, 32, i);
1294 }
1295
1296 assert(ix >= DKIX_DUMMY);
1297 return ix;
1298}
1299
1300// From CPython
1301#define PERTURB_SHIFT 5
1302
1303// 3.13+
1304#if PYTHON_VERSION >= 0x3d0
1305
1306static inline Py_ALWAYS_INLINE Py_ssize_t Nuitka_Py_dictkeys_do_lookup(
1307 PyDictObject *mp, PyDictKeysObject *dk, PyObject *key, Py_hash_t hash,
1308 int (*check_lookup)(PyDictObject *, PyDictKeysObject *, void *, Py_ssize_t ix, PyObject *key, Py_hash_t)) {
1309 void *ep0 = _DK_ENTRIES(dk);
1310 size_t mask = DK_MASK(dk);
1311 size_t perturb = hash;
1312 size_t i = (size_t)hash & mask;
1313 Py_ssize_t ix;
1314 for (;;) {
1315 ix = Nuitka_Py_dictkeys_get_index(dk, i);
1316 if (ix >= 0) {
1317 int cmp = check_lookup(mp, dk, ep0, ix, key, hash);
1318 if (cmp < 0) {
1319 return cmp;
1320 } else if (cmp) {
1321 return ix;
1322 }
1323 } else if (ix == DKIX_EMPTY) {
1324 return DKIX_EMPTY;
1325 }
1326 perturb >>= PERTURB_SHIFT;
1327 i = mask & (i * 5 + perturb + 1);
1328
1329 // Manual loop unrolling
1330 ix = Nuitka_Py_dictkeys_get_index(dk, i);
1331 if (ix >= 0) {
1332 int cmp = check_lookup(mp, dk, ep0, ix, key, hash);
1333 if (cmp < 0) {
1334 return cmp;
1335 } else if (cmp) {
1336 return ix;
1337 }
1338 } else if (ix == DKIX_EMPTY) {
1339 return DKIX_EMPTY;
1340 }
1341 perturb >>= PERTURB_SHIFT;
1342 i = mask & (i * 5 + perturb + 1);
1343 }
1344 NUITKA_CANNOT_GET_HERE("Nuitka_Py_dictkeys_do_lookup failed");
1345}
1346
1347static inline int Nuitka_Py_dictkeys_compare_unicode_generic(PyDictObject *mp, PyDictKeysObject *dk, void *ep0,
1348 Py_ssize_t ix, PyObject *key, Py_hash_t hash) {
1349 PyDictUnicodeEntry *ep = &((PyDictUnicodeEntry *)ep0)[ix];
1350 assert(ep->me_key != NULL);
1351 assert(PyUnicode_CheckExact(ep->me_key));
1352 assert(!PyUnicode_CheckExact(key));
1353
1354 if (Nuitka_Py_unicode_get_hash(ep->me_key) == hash) {
1355 PyObject *startkey = ep->me_key;
1356 Py_INCREF(startkey);
1357 int cmp = RICH_COMPARE_EQ_NBOOL_OBJECT_OBJECT(startkey, key);
1358 Py_DECREF(startkey);
1359 if (cmp < 0) {
1360 return DKIX_ERROR;
1361 }
1362 if (dk == mp->ma_keys && ep->me_key == startkey) {
1363 return cmp;
1364 } else {
1365 /* The dict was mutated, restart */
1366 return DKIX_KEY_CHANGED;
1367 }
1368 }
1369 return 0;
1370}
1371
1372static Py_ssize_t Nuitka_Py_unicodekeys_lookup_generic(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key,
1373 Py_hash_t hash) {
1374 return Nuitka_Py_dictkeys_do_lookup(mp, dk, key, hash, Nuitka_Py_dictkeys_compare_unicode_generic);
1375}
1376
1377static inline int Nuitka_Py_dictkeys_compare_generic(PyDictObject *mp, PyDictKeysObject *dk, void *ep0, Py_ssize_t ix,
1378 PyObject *key, Py_hash_t hash) {
1379 PyDictKeyEntry *ep = &((PyDictKeyEntry *)ep0)[ix];
1380 assert(ep->me_key != NULL);
1381 if (ep->me_key == key) {
1382 return 1;
1383 }
1384 if (ep->me_hash == hash) {
1385 PyObject *startkey = ep->me_key;
1386 Py_INCREF(startkey);
1387 int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
1388 Py_DECREF(startkey);
1389 if (cmp < 0) {
1390 return DKIX_ERROR;
1391 }
1392 if (dk == mp->ma_keys && ep->me_key == startkey) {
1393 return cmp;
1394 } else {
1395 /* The dict was mutated, restart */
1396 return DKIX_KEY_CHANGED;
1397 }
1398 }
1399 return 0;
1400}
1401
1402// Search non-Unicode key from Unicode table
1403static Py_ssize_t Nuitka_Py_dictkeys_generic_lookup(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key,
1404 Py_hash_t hash) {
1405 return Nuitka_Py_dictkeys_do_lookup(mp, dk, key, hash, Nuitka_Py_dictkeys_compare_generic);
1406}
1407
1408static inline int Nuitka_Py_dictkeys_compare_unicode_unicode(PyDictObject *mp, PyDictKeysObject *dk, void *ep0,
1409 Py_ssize_t ix, PyObject *key, Py_hash_t hash) {
1410 PyDictUnicodeEntry *ep = &((PyDictUnicodeEntry *)ep0)[ix];
1411 PyObject *ep_key = FT_ATOMIC_LOAD_PTR_RELAXED(ep->me_key);
1412 assert(ep_key != NULL);
1413 assert(PyUnicode_CheckExact(ep_key));
1414 if (ep_key == key ||
1415 (Nuitka_Py_unicode_get_hash(ep_key) == hash && RICH_COMPARE_EQ_CBOOL_UNICODE_UNICODE(ep_key, key))) {
1416 return 1;
1417 }
1418 return 0;
1419}
1420
1421Py_ssize_t _Py_HOT_FUNCTION Nuitka_Py_unicodekeys_lookup_unicode(PyDictKeysObject *dk, PyObject *key, Py_hash_t hash) {
1422 return Nuitka_Py_dictkeys_do_lookup(NULL, dk, key, hash, Nuitka_Py_dictkeys_compare_unicode_unicode);
1423}
1424
1425#ifdef Py_GIL_DISABLED
1426
1427static inline Py_ALWAYS_INLINE int
1428Nuitka_Py_dictkeys_compare_unicode_generic_threadsafe(PyDictObject *mp, PyDictKeysObject *dk, void *ep0, Py_ssize_t ix,
1429 PyObject *key, Py_hash_t hash) {
1430 PyDictUnicodeEntry *ep = &((PyDictUnicodeEntry *)ep0)[ix];
1431 PyObject *startkey = _Py_atomic_load_ptr_relaxed(&ep->me_key);
1432 assert(startkey == NULL || PyUnicode_CheckExact(ep->me_key));
1433 assert(!PyUnicode_CheckExact(key));
1434
1435 if (startkey != NULL) {
1436 if (!_Py_TryIncrefCompare(&ep->me_key, startkey)) {
1437 return DKIX_KEY_CHANGED;
1438 }
1439
1440 if (Nuitka_Py_unicode_get_hash(startkey) == hash) {
1441 int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
1442 Py_DECREF(startkey);
1443 if (cmp < 0) {
1444 return DKIX_ERROR;
1445 }
1446 if (dk == _Py_atomic_load_ptr_relaxed(&mp->ma_keys) &&
1447 startkey == _Py_atomic_load_ptr_relaxed(&ep->me_key)) {
1448 return cmp;
1449 } else {
1450 /* The dict was mutated, restart */
1451 return DKIX_KEY_CHANGED;
1452 }
1453 } else {
1454 Py_DECREF(startkey);
1455 }
1456 }
1457 return 0;
1458}
1459
1460// Search non-Unicode key from Unicode table
1461static Py_ssize_t Nuitka_Py_unicodekeys_lookup_generic_threadsafe(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key,
1462 Py_hash_t hash) {
1463 return Nuitka_Py_dictkeys_do_lookup(mp, dk, key, hash, Nuitka_Py_dictkeys_compare_unicode_generic_threadsafe);
1464}
1465
1466static inline Py_ALWAYS_INLINE int
1467Nuitka_Py_dictkeys_compare_unicode_unicode_threadsafe(PyDictObject *mp, PyDictKeysObject *dk, void *ep0, Py_ssize_t ix,
1468 PyObject *key, Py_hash_t hash) {
1469 PyDictUnicodeEntry *ep = &((PyDictUnicodeEntry *)ep0)[ix];
1470 PyObject *startkey = _Py_atomic_load_ptr_relaxed(&ep->me_key);
1471 assert(startkey == NULL || PyUnicode_CheckExact(startkey));
1472 if (startkey == key) {
1473 return 1;
1474 }
1475 if (startkey != NULL) {
1476 if (_Py_IsImmortal(startkey)) {
1477 return Nuitka_Py_unicode_get_hash(startkey) == hash && RICH_COMPARE_EQ_CBOOL_UNICODE_UNICODE(startkey, key);
1478 } else {
1479 if (!_Py_TryIncrefCompare(&ep->me_key, startkey)) {
1480 return DKIX_KEY_CHANGED;
1481 }
1482 if (Nuitka_Py_unicode_get_hash(startkey) == hash && RICH_COMPARE_EQ_CBOOL_UNICODE_UNICODE(startkey, key)) {
1483 Py_DECREF(startkey);
1484 return 1;
1485 }
1486 Py_DECREF(startkey);
1487 }
1488 }
1489 return 0;
1490}
1491
1492static Py_ssize_t _Py_HOT_FUNCTION Nuitka_Py_unicodekeys_lookup_unicode_threadsafe(PyDictKeysObject *dk, PyObject *key,
1493 Py_hash_t hash) {
1494 return Nuitka_Py_dictkeys_do_lookup(NULL, dk, key, hash, Nuitka_Py_dictkeys_compare_unicode_unicode_threadsafe);
1495}
1496
1497static inline Py_ALWAYS_INLINE int Nuitka_Py_dictkeys_compare_generic_threadsafe(PyDictObject *mp, PyDictKeysObject *dk,
1498 void *ep0, Py_ssize_t ix,
1499 PyObject *key, Py_hash_t hash) {
1500 PyDictKeyEntry *ep = &((PyDictKeyEntry *)ep0)[ix];
1501 PyObject *startkey = _Py_atomic_load_ptr_relaxed(&ep->me_key);
1502 if (startkey == key) {
1503 return 1;
1504 }
1505 Py_ssize_t ep_hash = _Py_atomic_load_ssize_relaxed(&ep->me_hash);
1506 if (ep_hash == hash) {
1507 if (startkey == NULL || !_Py_TryIncrefCompare(&ep->me_key, startkey)) {
1508 return DKIX_KEY_CHANGED;
1509 }
1510 int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
1511 Py_DECREF(startkey);
1512 if (cmp < 0) {
1513 return DKIX_ERROR;
1514 }
1515 if (dk == _Py_atomic_load_ptr_relaxed(&mp->ma_keys) && startkey == _Py_atomic_load_ptr_relaxed(&ep->me_key)) {
1516 return cmp;
1517 } else {
1518 /* The dict was mutated, restart */
1519 return DKIX_KEY_CHANGED;
1520 }
1521 }
1522 return 0;
1523}
1524
1525static Py_ssize_t Nuitka_Py_dictkeys_generic_lookup_threadsafe(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key,
1526 Py_hash_t hash) {
1527 return Nuitka_Py_dictkeys_do_lookup(mp, dk, key, hash, Nuitka_Py_dictkeys_compare_generic_threadsafe);
1528}
1529
1530static inline void Nuitka_Py_dict_ensure_shared_on_read(PyDictObject *mp) {
1531 if (!_Py_IsOwnedByCurrentThread((PyObject *)mp) && !IS_DICT_SHARED(mp)) {
1532 // The first time we access a dict from a non-owning thread we mark it
1533 // as shared. This ensures that a concurrent resize operation will
1534 // delay freeing the old keys or values using QSBR, which is necessary
1535 // to safely allow concurrent reads without locking...
1536 Py_BEGIN_CRITICAL_SECTION(mp);
1537 if (!IS_DICT_SHARED(mp)) {
1538 SET_DICT_SHARED(mp);
1539 }
1540 Py_END_CRITICAL_SECTION();
1541 }
1542}
1543
1544Py_ssize_t Nuitka_Py_dict_lookup_threadsafe(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr) {
1545 PyDictKeysObject *dk;
1546 DictKeysKind kind;
1547 Py_ssize_t ix;
1548 PyObject *value;
1549
1550 Nuitka_Py_dict_ensure_shared_on_read(mp);
1551
1552 dk = _Py_atomic_load_ptr(&mp->ma_keys);
1553 kind = dk->dk_kind;
1554
1555 if (kind != DICT_KEYS_GENERAL) {
1556 if (PyUnicode_CheckExact(key)) {
1557 ix = Nuitka_Py_unicodekeys_lookup_unicode_threadsafe(dk, key, hash);
1558 } else {
1559 ix = Nuitka_Py_unicodekeys_lookup_generic_threadsafe(mp, dk, key, hash);
1560 }
1561 if (ix == DKIX_KEY_CHANGED) {
1562 goto read_failed;
1563 }
1564
1565 if (ix >= 0) {
1566 if (kind == DICT_KEYS_SPLIT) {
1567 PyDictValues *values = _Py_atomic_load_ptr(&mp->ma_values);
1568 if (values == NULL)
1569 goto read_failed;
1570
1571 uint8_t capacity = _Py_atomic_load_uint8_relaxed(&values->capacity);
1572 if (ix >= (Py_ssize_t)capacity)
1573 goto read_failed;
1574
1575 value = _Py_TryXGetRef(&values->values[ix]);
1576 if (value == NULL)
1577 goto read_failed;
1578
1579 if (values != _Py_atomic_load_ptr(&mp->ma_values)) {
1580 Py_DECREF(value);
1581 goto read_failed;
1582 }
1583 } else {
1584 value = _Py_TryXGetRef(&DK_UNICODE_ENTRIES(dk)[ix].me_value);
1585 if (value == NULL) {
1586 goto read_failed;
1587 }
1588
1589 if (dk != _Py_atomic_load_ptr(&mp->ma_keys)) {
1590 Py_DECREF(value);
1591 goto read_failed;
1592 }
1593 }
1594 } else {
1595 value = NULL;
1596 }
1597 } else {
1598 ix = Nuitka_Py_dictkeys_generic_lookup_threadsafe(mp, dk, key, hash);
1599 if (ix == DKIX_KEY_CHANGED) {
1600 goto read_failed;
1601 }
1602 if (ix >= 0) {
1603 value = _Py_TryXGetRef(&DK_ENTRIES(dk)[ix].me_value);
1604 if (value == NULL)
1605 goto read_failed;
1606
1607 if (dk != _Py_atomic_load_ptr(&mp->ma_keys)) {
1608 Py_DECREF(value);
1609 goto read_failed;
1610 }
1611 } else {
1612 value = NULL;
1613 }
1614 }
1615
1616 *value_addr = value;
1617 return ix;
1618
1619read_failed:
1620 // In addition to the normal races of the dict being modified the _Py_TryXGetRef
1621 // can all fail if they don't yet have a shared ref count. That can happen here
1622 // or in the *_lookup_* helper. In that case we need to take the lock to avoid
1623 // mutation and do a normal incref which will make them shared.
1624 Py_BEGIN_CRITICAL_SECTION(mp);
1625 ix = _Py_dict_lookup(mp, key, hash, &value);
1626 *value_addr = value;
1627 if (value != NULL) {
1628 assert(ix >= 0);
1629 _Py_NewRefWithLock(value);
1630 }
1631 Py_END_CRITICAL_SECTION();
1632 return ix;
1633}
1634
1635#else // Py_GIL_DISABLED
1636
1637Py_ssize_t Nuitka_Py_dict_lookup_threadsafe(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr) {
1638 Py_ssize_t ix = Nuitka_PyDictLookup(mp, key, hash, &value_addr);
1639 Py_XNewRef(*value_addr);
1640 return ix;
1641}
1642
1643#endif
1644
1645Py_ssize_t Nuitka_PyDictLookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr) {
1646 PyDictKeysObject *dk;
1647 DictKeysKind kind;
1648 Py_ssize_t ix;
1649
1650 _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(mp);
1651restart:
1652 dk = mp->ma_keys;
1653 kind = (DictKeysKind)dk->dk_kind;
1654
1655 if (kind != DICT_KEYS_GENERAL) {
1656 if (PyUnicode_CheckExact(key)) {
1657#ifdef Py_GIL_DISABLED
1658 if (kind == DICT_KEYS_SPLIT) {
1659 ix = Nuitka_Py_unicodekeys_lookup_unicode_threadsafe(dk, key, hash);
1660
1661 if (ix == DKIX_KEY_CHANGED) {
1662 LOCK_KEYS(dk);
1663 ix = Nuitka_Py_unicodekeys_lookup_unicode(dk, key, hash);
1664 UNLOCK_KEYS(dk);
1665 }
1666 } else
1667#endif
1668 {
1669 ix = Nuitka_Py_unicodekeys_lookup_unicode(dk, key, hash);
1670 }
1671 } else {
1672 INCREF_KEYS_FT(dk);
1673 LOCK_KEYS_IF_SPLIT(dk, kind);
1674
1675 ix = Nuitka_Py_unicodekeys_lookup_generic(mp, dk, key, hash);
1676
1677 UNLOCK_KEYS_IF_SPLIT(dk, kind);
1678 DECREF_KEYS_FT(dk, IS_DICT_SHARED(mp));
1679
1680 // Dictionary lookup changed the dictionary, retry.
1681 if (ix == DKIX_KEY_CHANGED) {
1682 goto restart;
1683 }
1684 }
1685
1686 if (ix >= 0) {
1687 if (kind == DICT_KEYS_SPLIT) {
1688 *value_addr = &mp->ma_values->values[ix];
1689 } else {
1690 *value_addr = &DK_UNICODE_ENTRIES(dk)[ix].me_value;
1691 }
1692 } else {
1693 *value_addr = NULL;
1694 }
1695 } else {
1696 ix = Nuitka_Py_dictkeys_generic_lookup(mp, dk, key, hash);
1697
1698 // Dictionary lookup changed the dictionary, retry.
1699 if (ix == DKIX_KEY_CHANGED) {
1700 goto restart;
1701 }
1702
1703 if (ix >= 0) {
1704 *value_addr = &DK_ENTRIES(dk)[ix].me_value;
1705 } else {
1706 *value_addr = NULL;
1707 }
1708 }
1709
1710 return ix;
1711}
1712
1713#else
1714static Py_ssize_t Nuitka_Py_unicodekeys_lookup_generic(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key,
1715 Py_hash_t hash) {
1716 PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(dk);
1717
1718 size_t mask = DK_MASK(dk);
1719 size_t perturb = hash;
1720 size_t i = (size_t)hash & mask;
1721
1722 while (1) {
1723 Py_ssize_t ix = Nuitka_Py_dictkeys_get_index(dk, i);
1724
1725 if (ix >= 0) {
1726 PyDictUnicodeEntry *ep = &ep0[ix];
1727
1728 assert(ep->me_key != NULL);
1729 assert(PyUnicode_CheckExact(ep->me_key));
1730
1731 if (ep->me_key == key) {
1732 return ix;
1733 }
1734
1735 if (Nuitka_Py_unicode_get_hash(ep->me_key) == hash) {
1736 PyObject *startkey = ep->me_key;
1737 Py_INCREF(startkey);
1738 nuitka_bool cmp = RICH_COMPARE_EQ_NBOOL_UNICODE_OBJECT(startkey, key);
1739 Py_DECREF(startkey);
1740
1741 if (unlikely(cmp == NUITKA_BOOL_EXCEPTION)) {
1742 return DKIX_ERROR;
1743 }
1744
1745 if (dk == mp->ma_keys && ep->me_key == startkey) {
1746 if (cmp == NUITKA_BOOL_TRUE) {
1747 return ix;
1748 }
1749 } else {
1750 // In case of changed dictionary, trigger restart in caller.
1751 return DKIX_KEY_CHANGED;
1752 }
1753 }
1754 } else if (ix == DKIX_EMPTY) {
1755 return DKIX_EMPTY;
1756 }
1757 perturb >>= PERTURB_SHIFT;
1758 i = mask & (i * 5 + perturb + 1);
1759 }
1760
1761 NUITKA_CANNOT_GET_HERE("Nuitka_Py_unicodekeys_lookup_generic failed");
1762}
1763
1764Py_ssize_t Nuitka_Py_unicodekeys_lookup_unicode(PyDictKeysObject *dk, PyObject *key, Py_hash_t hash) {
1765 assert(PyUnicode_CheckExact(key));
1766 assert(dk->dk_kind != DICT_KEYS_GENERAL);
1767
1768 PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(dk);
1769
1770 size_t mask = DK_MASK(dk);
1771 size_t perturb = hash;
1772 size_t i = (size_t)hash & mask;
1773
1774 while (true) {
1775 Py_ssize_t ix = Nuitka_Py_dictkeys_get_index(dk, i);
1776
1777 // Found it.
1778 if (ix >= 0) {
1779 PyDictUnicodeEntry *ep = &ep0[ix];
1780 assert(ep->me_key != NULL);
1781 assert(PyUnicode_CheckExact(ep->me_key));
1782
1783 if (ep->me_key == key || (Nuitka_Py_unicode_get_hash(ep->me_key) == hash &&
1784 RICH_COMPARE_EQ_CBOOL_UNICODE_UNICODE(ep->me_key, key))) {
1785 return ix;
1786 }
1787 } else if (ix == DKIX_EMPTY) {
1788 return DKIX_EMPTY;
1789 }
1790 perturb >>= PERTURB_SHIFT;
1791
1792 i = mask & (i * 5 + perturb + 1);
1793 ix = Nuitka_Py_dictkeys_get_index(dk, i);
1794
1795 if (ix >= 0) {
1796 PyDictUnicodeEntry *ep = &ep0[ix];
1797
1798 assert(ep->me_key != NULL);
1799 assert(PyUnicode_CheckExact(ep->me_key));
1800
1801 if (ep->me_key == key || (Nuitka_Py_unicode_get_hash(ep->me_key) == hash &&
1802 RICH_COMPARE_EQ_CBOOL_UNICODE_UNICODE(ep->me_key, key))) {
1803 return ix;
1804 }
1805 } else if (ix == DKIX_EMPTY) {
1806 return DKIX_EMPTY;
1807 }
1808
1809 perturb >>= PERTURB_SHIFT;
1810 i = mask & (i * 5 + perturb + 1);
1811 }
1812
1813 NUITKA_CANNOT_GET_HERE("Nuitka_Py_unicodekeys_lookup_unicode failed");
1814}
1815
1816// Search key from Generic table.
1817static Py_ssize_t Nuitka_Py_dictkeys_generic_lookup(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key,
1818 Py_hash_t hash) {
1819 PyDictKeyEntry *ep0 = DK_ENTRIES(dk);
1820
1821 size_t mask = DK_MASK(dk);
1822 size_t perturb = hash;
1823 size_t i = (size_t)hash & mask;
1824
1825 while (1) {
1826 Py_ssize_t ix = Nuitka_Py_dictkeys_get_index(dk, i);
1827
1828 if (ix >= 0) {
1829 PyDictKeyEntry *ep = &ep0[ix];
1830 assert(ep->me_key != NULL);
1831 if (ep->me_key == key) {
1832 return ix;
1833 }
1834 if (ep->me_hash == hash) {
1835 PyObject *startkey = ep->me_key;
1836 Py_INCREF(startkey);
1837 nuitka_bool cmp = RICH_COMPARE_EQ_NBOOL_OBJECT_OBJECT(startkey, key);
1838 Py_DECREF(startkey);
1839
1840 if (unlikely(cmp == NUITKA_BOOL_EXCEPTION)) {
1841 return DKIX_ERROR;
1842 }
1843 if (dk == mp->ma_keys && ep->me_key == startkey) {
1844 if (cmp == NUITKA_BOOL_TRUE) {
1845 return ix;
1846 }
1847 } else {
1848 // In case of changed dictionary, trigger restart in caller.
1849 return DKIX_KEY_CHANGED;
1850 }
1851 }
1852 } else if (ix == DKIX_EMPTY) {
1853 return DKIX_EMPTY;
1854 }
1855 perturb >>= PERTURB_SHIFT;
1856 i = mask & (i * 5 + perturb + 1);
1857 }
1858}
1859
1860Py_ssize_t Nuitka_PyDictLookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr) {
1861 PyDictKeysObject *dk;
1862 DictKeysKind kind;
1863 Py_ssize_t ix;
1864
1865 _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(mp);
1866restart:
1867 dk = mp->ma_keys;
1868 kind = (DictKeysKind)dk->dk_kind;
1869
1870 if (kind != DICT_KEYS_GENERAL) {
1871 if (PyUnicode_CheckExact(key)) {
1872#ifdef Py_GIL_DISABLED
1873 if (kind == DICT_KEYS_SPLIT) {
1874 ix = Nuitka_Py_unicodekeys_lookup_unicode_threadsafe(dk, key, hash);
1875
1876 if (ix == DKIX_KEY_CHANGED) {
1877 LOCK_KEYS(dk);
1878 ix = Nuitka_Py_unicodekeys_lookup_unicode(dk, key, hash);
1879 UNLOCK_KEYS(dk);
1880 }
1881 } else
1882#endif
1883 {
1884 ix = Nuitka_Py_unicodekeys_lookup_unicode(dk, key, hash);
1885 }
1886 } else {
1887 INCREF_KEYS_FT(dk);
1888 LOCK_KEYS_IF_SPLIT(dk, kind);
1889
1890 ix = Nuitka_Py_unicodekeys_lookup_generic(mp, dk, key, hash);
1891
1892 UNLOCK_KEYS_IF_SPLIT(dk, kind);
1893 DECREF_KEYS_FT(dk, IS_DICT_SHARED(mp));
1894
1895 // Dictionary lookup changed the dictionary, retry.
1896 if (ix == DKIX_KEY_CHANGED) {
1897 goto restart;
1898 }
1899 }
1900
1901 if (ix >= 0) {
1902 if (kind == DICT_KEYS_SPLIT) {
1903 *value_addr = &mp->ma_values->values[ix];
1904 } else {
1905 *value_addr = &DK_UNICODE_ENTRIES(dk)[ix].me_value;
1906 }
1907 } else {
1908 *value_addr = NULL;
1909 }
1910 } else {
1911 ix = Nuitka_Py_dictkeys_generic_lookup(mp, dk, key, hash);
1912
1913 // Dictionary lookup changed the dictionary, retry.
1914 if (ix == DKIX_KEY_CHANGED) {
1915 goto restart;
1916 }
1917
1918 if (ix >= 0) {
1919 *value_addr = &DK_ENTRIES(dk)[ix].me_value;
1920 } else {
1921 *value_addr = NULL;
1922 }
1923 }
1924
1925 return ix;
1926}
1927#endif
1928
1929Py_ssize_t Nuitka_PyDictLookupStr(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr) {
1930 assert(PyUnicode_CheckExact(key));
1931
1932 PyDictKeysObject *dk = mp->ma_keys;
1933 assert(dk->dk_kind != DICT_KEYS_GENERAL);
1934
1935 Py_ssize_t ix = Nuitka_Py_unicodekeys_lookup_unicode(dk, key, hash);
1936
1937 if (ix >= 0) {
1938 if (dk->dk_kind == DICT_KEYS_SPLIT) {
1939 *value_addr = &mp->ma_values->values[ix];
1940 } else {
1941 *value_addr = &DK_UNICODE_ENTRIES(dk)[ix].me_value;
1942 }
1943 } else {
1944 *value_addr = NULL;
1945 }
1946
1947 return ix;
1948}
1949
1950#endif
1951
1952bool Nuitka_DictNext(PyObject *dict, Py_ssize_t *pos, PyObject **key_ptr, PyObject **value_ptr) {
1953 CHECK_OBJECT(dict);
1954 assert(PyDict_CheckExact(dict));
1955 assert(key_ptr != NULL);
1956 assert(value_ptr != NULL);
1957
1958#if PYTHON_VERSION < 0x300
1959 Py_ssize_t i = *pos;
1960
1961 PyDictEntry *ep = ((PyDictObject *)dict)->ma_table;
1962 Py_ssize_t mask = ((PyDictObject *)dict)->ma_mask;
1963
1964 while (i <= mask && ep[i].me_value == NULL) {
1965 i++;
1966 }
1967
1968 *pos = i + 1;
1969
1970 if (i > mask) {
1971 return false;
1972 }
1973
1974 *key_ptr = ep[i].me_key;
1975 *value_ptr = ep[i].me_value;
1976
1977 return true;
1978
1979#elif PYTHON_VERSION < 0x360
1980 PyDictObject *mp = (PyDictObject *)dict;
1981 PyObject **dict_value_ptr;
1982 Py_ssize_t offset;
1983
1984 Py_ssize_t i = *pos;
1985 assert(i >= 0);
1986
1987 if (mp->ma_values) {
1988 dict_value_ptr = &mp->ma_values[i];
1989 offset = sizeof(PyObject *);
1990 } else {
1991 dict_value_ptr = &mp->ma_keys->dk_entries[i].me_value;
1992 offset = sizeof(PyDictKeyEntry);
1993 }
1994
1995 Py_ssize_t mask = DK_MASK(mp->ma_keys);
1996
1997 while ((i <= mask) && (*dict_value_ptr == NULL)) {
1998 dict_value_ptr = (PyObject **)(((char *)dict_value_ptr) + offset);
1999 i++;
2000 }
2001
2002 if (i > mask) {
2003 return false;
2004 }
2005
2006 *key_ptr = mp->ma_keys->dk_entries[i].me_key;
2007 *value_ptr = *dict_value_ptr;
2008 *pos = i + 1;
2009
2010 return true;
2011
2012#elif PYTHON_VERSION < 0x3b0
2013 PyDictObject *mp = (PyDictObject *)dict;
2014 PyDictKeyEntry *entry;
2015 PyObject *value;
2016
2017 Py_ssize_t i = *pos;
2018 assert(i >= 0);
2019
2020 if (mp->ma_values) {
2021 if (i >= mp->ma_used) {
2022 return false;
2023 }
2024
2025 entry = &DK_ENTRIES(mp->ma_keys)[i];
2026 value = DK_VALUE(mp, i);
2027
2028 assert(value != NULL);
2029 } else {
2030 Py_ssize_t n = mp->ma_keys->dk_nentries;
2031
2032 if (i >= n) {
2033 return false;
2034 }
2035
2036 entry = &DK_ENTRIES(mp->ma_keys)[i];
2037
2038 while (i < n && entry->me_value == NULL) {
2039 entry += 1;
2040 i += 1;
2041 }
2042
2043 if (i >= n) {
2044 return false;
2045 }
2046
2047 value = entry->me_value;
2048 }
2049
2050 *pos = i + 1;
2051
2052 *key_ptr = entry->me_key;
2053 *value_ptr = value;
2054
2055 return true;
2056#else
2057 PyDictObject *mp = (PyDictObject *)dict;
2058 Py_ssize_t i = *pos;
2059 PyObject *key, *value;
2060
2061 if (mp->ma_values) {
2062 // Shared keys dictionary.
2063 assert(mp->ma_used <= SHARED_KEYS_MAX_SIZE);
2064
2065 if (i >= mp->ma_used) {
2066 return false;
2067 }
2068
2069 int index = Nuitka_py_get_index_from_order(mp, i);
2070 value = mp->ma_values->values[index];
2071
2072 key = DK_UNICODE_ENTRIES(mp->ma_keys)[index].me_key;
2073
2074 assert(value != NULL);
2075 } else {
2076 Py_ssize_t n = mp->ma_keys->dk_nentries;
2077
2078 if (i >= n) {
2079 return false;
2080 }
2081
2082 // Unicode keys or general keys have different sizes, make sure to index
2083 // the right type, the algorithm is the same however.
2084 if (DK_IS_UNICODE(mp->ma_keys)) {
2085 PyDictUnicodeEntry *entry_ptr = &DK_UNICODE_ENTRIES(mp->ma_keys)[i];
2086
2087 while (i < n && entry_ptr->me_value == NULL) {
2088 entry_ptr++;
2089 i++;
2090 }
2091
2092 if (i >= n) {
2093 return false;
2094 }
2095
2096 key = entry_ptr->me_key;
2097 value = entry_ptr->me_value;
2098 } else {
2099 PyDictKeyEntry *entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
2100
2101 while (i < n && entry_ptr->me_value == NULL) {
2102 entry_ptr++;
2103 i++;
2104 }
2105
2106 if (i >= n) {
2107 return false;
2108 }
2109
2110 key = entry_ptr->me_key;
2111 value = entry_ptr->me_value;
2112 }
2113 }
2114
2115 *pos = i + 1;
2116
2117 *key_ptr = key;
2118 *value_ptr = value;
2119
2120 return true;
2121#endif
2122}
2123
2124PyObject *TO_DICT(PyThreadState *tstate, PyObject *seq_obj, PyObject *dict_obj) {
2125 PyObject *result;
2126
2127 if (seq_obj != NULL) {
2128 CHECK_OBJECT(seq_obj);
2129
2130 // Fast path for dictionaries.
2131 if (PyDict_CheckExact(seq_obj)) {
2132 result = DICT_COPY(tstate, seq_obj);
2133 } else {
2134 result = MAKE_DICT_EMPTY(tstate);
2135
2136 Py_INCREF(seq_obj);
2137
2138#if PYTHON_VERSION >= 0x300
2139 int res = HAS_ATTR_BOOL2(tstate, seq_obj, const_str_plain_keys);
2140
2141 if (unlikely(res == -1)) {
2142 Py_DECREF(seq_obj);
2143 return NULL;
2144 }
2145#else
2146 int res = HAS_ATTR_BOOL(tstate, seq_obj, const_str_plain_keys) ? 1 : 0;
2147#endif
2148
2149 if (res) {
2150 res = PyDict_Merge(result, seq_obj, 1);
2151 } else {
2152 res = PyDict_MergeFromSeq2(result, seq_obj, 1);
2153 }
2154
2155 Py_DECREF(seq_obj);
2156
2157 if (unlikely(res == -1)) {
2158 return NULL;
2159 }
2160 }
2161 } else {
2162 result = MAKE_DICT_EMPTY(tstate);
2163 }
2164
2165 // TODO: Should specialize for dict_obj/seq_obj presence to save a bit of time
2166 // and complexity.
2167 if (dict_obj != NULL) {
2168 CHECK_OBJECT(dict_obj);
2169
2170 int res = PyDict_Merge(result, dict_obj, 1);
2171
2172 if (unlikely(res == -1)) {
2173 return NULL;
2174 }
2175 }
2176
2177 return result;
2178}
2179
2180#if _NUITKA_MAINTAIN_DICT_VERSION_TAG
2181uint64_t nuitka_dict_version_tag_counter = ((uint64_t)1) << 32;
2182#endif
2183
2184#if NUITKA_DICT_HAS_FREELIST
2185PyObject *MAKE_DICT_EMPTY(PyThreadState *tstate) {
2186 PyDictObject *empty_dict_mp = (PyDictObject *)const_dict_empty;
2187
2188#if PYTHON_VERSION < 0x3c0
2189 empty_dict_mp->ma_keys->dk_refcnt++;
2190#endif
2191
2192 PyDictObject *result_mp = _Nuitka_AllocatePyDictObject(tstate);
2193
2194 result_mp->ma_keys = empty_dict_mp->ma_keys;
2195 result_mp->ma_values = empty_dict_mp->ma_values;
2196 result_mp->ma_used = 0;
2197#if PYTHON_VERSION < 0x3e0
2198#if PYTHON_VERSION >= 0x3c0
2199 result_mp->ma_version_tag = DICT_NEXT_VERSION(_PyInterpreterState_GET());
2200#elif PYTHON_VERSION >= 0x360
2201 result_mp->ma_version_tag = 1;
2202#endif
2203#endif
2204
2205 // Key reference needs to be counted on older Python
2206#if defined(Py_REF_DEBUG) && PYTHON_VERSION < 0x3c0
2207 _Py_RefTotal++;
2208#endif
2209
2210 // No Nuitka_GC_Track for the empty dictionary.
2211 return (PyObject *)result_mp;
2212}
2213#endif
2214
2215PyObject *MAKE_DICT(PyObject **pairs, Py_ssize_t size) {
2216 PyObject *result = _PyDict_NewPresized(size);
2217
2218 // Reject usage like this.
2219 assert(size > 0);
2220 for (Py_ssize_t i = 0; i < size; i++) {
2221 PyObject *key = pairs[i * 2];
2222 PyObject *value = pairs[i * 2 + 1];
2223
2224 int res = PyDict_SetItem(result, key, value);
2225
2226 if (unlikely(res != 0)) {
2227 Py_DECREF(result);
2228 return NULL;
2229 }
2230 }
2231
2232 return result;
2233}
2234
2235PyObject *MAKE_DICT_X(PyObject **pairs, Py_ssize_t size) {
2236 PyObject *result = _PyDict_NewPresized(size);
2237
2238 // Reject usage like this.
2239 assert(size > 0);
2240 for (Py_ssize_t i = 0; i < size; i++) {
2241 PyObject *value = pairs[i * 2 + 1];
2242
2243 if (value != NULL) {
2244 PyObject *key = pairs[i * 2];
2245 CHECK_OBJECT(key);
2246 CHECK_OBJECT(value);
2247
2248 int res = PyDict_SetItem(result, key, value);
2249
2250 if (unlikely(res != 0)) {
2251 Py_DECREF(result);
2252 return NULL;
2253 }
2254 }
2255 }
2256
2257 return result;
2258}
2259
2260PyObject *MAKE_DICT_X_CSTR(char const **keys, PyObject **values, Py_ssize_t size) {
2261 PyObject *result = _PyDict_NewPresized(size);
2262
2263 // Reject usage like this.
2264 assert(size > 0);
2265 for (Py_ssize_t i = 0; i < size; i++) {
2266 PyObject *value = values[i];
2267
2268 if (value != NULL) {
2269 CHECK_OBJECT(value);
2270
2271 int res = PyDict_SetItemString(result, keys[i], value);
2272
2273 if (unlikely(res != 0)) {
2274 Py_DECREF(result);
2275 return NULL;
2276 }
2277 }
2278 }
2279
2280 return result;
2281}
2282
2283// Part of "Nuitka", an optimizing Python compiler that is compatible and
2284// integrates with CPython, but also works on its own.
2285//
2286// Licensed under the Apache License, Version 2.0 (the "License");
2287// you may not use this file except in compliance with the License.
2288// You may obtain a copy of the License at
2289//
2290// http://www.apache.org/licenses/LICENSE-2.0
2291//
2292// Unless required by applicable law or agreed to in writing, software
2293// distributed under the License is distributed on an "AS IS" BASIS,
2294// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
2295// See the License for the specific language governing permissions and
2296// limitations under the License.
Nuitka_ExceptionPreservationItem
Definition exceptions.h:712
dictiterobject
Definition HelpersDictionaries.c:909
dictviewobject
Definition HelpersDictionaries.c:1012