Debian Codegraph @

Include/internal/pycore_dict.h

raw
1 #ifndef Py_INTERNAL_DICT_H
2 #define Py_INTERNAL_DICT_H
3 #ifdef __cplusplus
4 extern "C" {
5 #endif
6
7 #ifndef Py_BUILD_CORE
8 # error "this header requires Py_BUILD_CORE define"
9 #endif
10
11 #include "pycore_object.h" // PyManagedDictPointer
12 #include "pycore_pyatomic_ft_wrappers.h" // FT_ATOMIC_LOAD_SSIZE_ACQUIRE
13 #include "pycore_stackref.h" // _PyStackRef
14 #include "pycore_stats.h"
15
16 // Unsafe flavor of PyDict_GetItemWithError(): no error checking
17 extern PyObject* _PyDict_GetItemWithError(PyObject *dp, PyObject *key);
18
19 // Delete an item from a dict if a predicate is true
20 // Returns -1 on error, 1 if the item was deleted, 0 otherwise
21 // Export for '_asyncio' shared extension
22 PyAPI_FUNC(int) _PyDict_DelItemIf(PyObject *mp, PyObject *key,
23 int (*predicate)(PyObject *value, void *arg),
24 void *arg);
25
26 // "KnownHash" variants
27 // Export for '_asyncio' shared extension
28 PyAPI_FUNC(int) _PyDict_SetItem_KnownHash(PyObject *mp, PyObject *key,
29 PyObject *item, Py_hash_t hash);
30 // Export for '_asyncio' shared extension
31 PyAPI_FUNC(int) _PyDict_DelItem_KnownHash(PyObject *mp, PyObject *key,
32 Py_hash_t hash);
33
34 extern int _PyDict_DelItem_KnownHash_LockHeld(PyObject *mp, PyObject *key,
35 Py_hash_t hash);
36
37 extern int _PyDict_Contains_KnownHash(PyObject *, PyObject *, Py_hash_t);
38
39 // "Id" variants
40 extern PyObject* _PyDict_GetItemIdWithError(PyObject *dp,
41 _Py_Identifier *key);
42 extern int _PyDict_ContainsId(PyObject *, _Py_Identifier *);
43 extern int _PyDict_SetItemId(PyObject *dp, _Py_Identifier *key, PyObject *item);
44 extern int _PyDict_DelItemId(PyObject *mp, _Py_Identifier *key);
45
46 extern int _PyDict_Next(
47 PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value, Py_hash_t *hash);
48
49 extern int _PyDict_HasOnlyStringKeys(PyObject *mp);
50
51 // Export for '_ctypes' shared extension
52 PyAPI_FUNC(Py_ssize_t) _PyDict_SizeOf(PyDictObject *);
53
54 extern Py_ssize_t _PyDict_SizeOf_LockHeld(PyDictObject *);
55
56 #define _PyDict_HasSplitTable(d) ((d)->ma_values != NULL)
57
58 /* Like PyDict_Merge, but override can be 0, 1 or 2. If override is 0,
59 the first occurrence of a key wins, if override is 1, the last occurrence
60 of a key wins, if override is 2, a KeyError with conflicting key as
61 argument is raised.
62 */
63 PyAPI_FUNC(int) _PyDict_MergeEx(PyObject *mp, PyObject *other, int override);
64
65 extern void _PyDict_DebugMallocStats(FILE *out);
66
67
68 /* _PyDictView */
69
70 typedef struct {
71 PyObject_HEAD
72 PyDictObject *dv_dict;
73 } _PyDictViewObject;
74
75 extern PyObject* _PyDictView_New(PyObject *, PyTypeObject *);
76 extern PyObject* _PyDictView_Intersect(PyObject* self, PyObject *other);
77
78 /* other API */
79
80 typedef struct {
81 /* Cached hash code of me_key. */
82 Py_hash_t me_hash;
83 PyObject *me_key;
84 PyObject *me_value; /* This field is only meaningful for combined tables */
85 } PyDictKeyEntry;
86
87 typedef struct {
88 PyObject *me_key; /* The key must be Unicode and have hash. */
89 PyObject *me_value; /* This field is only meaningful for combined tables */
90 } PyDictUnicodeEntry;
91
92 extern PyDictKeysObject *_PyDict_NewKeysForClass(PyHeapTypeObject *);
93 extern PyObject *_PyDict_FromKeys(PyObject *, PyObject *, PyObject *);
94
95 /* Gets a version number unique to the current state of the keys of dict, if possible.
96 * Returns the version number, or zero if it was not possible to get a version number. */
97 extern uint32_t _PyDictKeys_GetVersionForCurrentState(
98 PyInterpreterState *interp, PyDictKeysObject *dictkeys);
99
100 /* Gets a version number unique to the current state of the keys of dict, if possible.
101 *
102 * In free-threaded builds ensures that the dict can be used for lock-free
103 * reads if a version was assigned.
104 *
105 * The caller must hold the per-object lock on dict.
106 *
107 * Returns the version number, or zero if it was not possible to get a version number. */
108 extern uint32_t _PyDict_GetKeysVersionForCurrentState(
109 PyInterpreterState *interp, PyDictObject *dict);
110
111 extern size_t _PyDict_KeysSize(PyDictKeysObject *keys);
112
113 extern void _PyDictKeys_DecRef(PyDictKeysObject *keys);
114
115 /* _Py_dict_lookup() returns index of entry which can be used like DK_ENTRIES(dk)[index].
116 * -1 when no entry found, -3 when compare raises error.
117 */
118 extern Py_ssize_t _Py_dict_lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
119 extern Py_ssize_t _Py_dict_lookup_threadsafe(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
120 extern Py_ssize_t _Py_dict_lookup_threadsafe_stackref(PyDictObject *mp, PyObject *key, Py_hash_t hash, _PyStackRef *value_addr);
121
122 extern int _PyDict_GetMethodStackRef(PyDictObject *dict, PyObject *name, _PyStackRef *method);
123
124 extern Py_ssize_t _PyDict_LookupIndex(PyDictObject *, PyObject *);
125 extern Py_ssize_t _PyDictKeys_StringLookup(PyDictKeysObject* dictkeys, PyObject *key);
126
127 /* Look up a string key in an all unicode dict keys, assign the keys object a version, and
128 * store it in version.
129 *
130 * Returns DKIX_ERROR if key is not a string or if the keys object is not all
131 * strings.
132 *
133 * Returns DKIX_EMPTY if the key is not present.
134 */
135 extern Py_ssize_t _PyDictKeys_StringLookupAndVersion(PyDictKeysObject* dictkeys, PyObject *key, uint32_t *version);
136 extern Py_ssize_t _PyDictKeys_StringLookupSplit(PyDictKeysObject* dictkeys, PyObject *key);
137 PyAPI_FUNC(PyObject *)_PyDict_LoadGlobal(PyDictObject *, PyDictObject *, PyObject *);
138 PyAPI_FUNC(void) _PyDict_LoadGlobalStackRef(PyDictObject *, PyDictObject *, PyObject *, _PyStackRef *);
139
140 // Loads the __builtins__ object from the globals dict. Returns a new reference.
141 extern PyObject *_PyDict_LoadBuiltinsFromGlobals(PyObject *globals);
142
143 /* Consumes references to key and value */
144 PyAPI_FUNC(int) _PyDict_SetItem_Take2(PyDictObject *op, PyObject *key, PyObject *value);
145 extern int _PyDict_SetItem_LockHeld(PyDictObject *dict, PyObject *name, PyObject *value);
146 // Export for '_asyncio' shared extension
147 PyAPI_FUNC(int) _PyDict_SetItem_KnownHash_LockHeld(PyDictObject *mp, PyObject *key,
148 PyObject *value, Py_hash_t hash);
149 // Export for '_asyncio' shared extension
150 PyAPI_FUNC(int) _PyDict_GetItemRef_KnownHash_LockHeld(PyDictObject *op, PyObject *key, Py_hash_t hash, PyObject **result);
151 extern int _PyDict_GetItemRef_KnownHash(PyDictObject *op, PyObject *key, Py_hash_t hash, PyObject **result);
152 extern int _PyDict_GetItemRef_Unicode_LockHeld(PyDictObject *op, PyObject *key, PyObject **result);
153 extern int _PyObjectDict_SetItem(PyTypeObject *tp, PyObject *obj, PyObject **dictptr, PyObject *name, PyObject *value);
154
155 extern int _PyDict_Pop_KnownHash(
156 PyDictObject *dict,
157 PyObject *key,
158 Py_hash_t hash,
159 PyObject **result);
160
161 extern void _PyDict_Clear_LockHeld(PyObject *op);
162
163 #ifdef Py_GIL_DISABLED
164 PyAPI_FUNC(void) _PyDict_EnsureSharedOnRead(PyDictObject *mp);
165 #endif
166
167 #define DKIX_EMPTY (-1)
168 #define DKIX_DUMMY (-2) /* Used internally */
169 #define DKIX_ERROR (-3)
170 #define DKIX_KEY_CHANGED (-4) /* Used internally */
171
172 typedef enum {
173 DICT_KEYS_GENERAL = 0,
174 DICT_KEYS_UNICODE = 1,
175 DICT_KEYS_SPLIT = 2
176 } DictKeysKind;
177
178 /* See dictobject.c for actual layout of DictKeysObject */
179 struct _dictkeysobject {
180 Py_ssize_t dk_refcnt;
181
182 /* Size of the hash table (dk_indices). It must be a power of 2. */
183 uint8_t dk_log2_size;
184
185 /* Size of the hash table (dk_indices) by bytes. */
186 uint8_t dk_log2_index_bytes;
187
188 /* Kind of keys */
189 uint8_t dk_kind;
190
191 #ifdef Py_GIL_DISABLED
192 /* Lock used to protect shared keys */
193 PyMutex dk_mutex;
194 #endif
195
196 /* Version number -- Reset to 0 by any modification to keys */
197 uint32_t dk_version;
198
199 /* Number of usable entries in dk_entries. */
200 Py_ssize_t dk_usable;
201
202 /* Number of used entries in dk_entries. */
203 Py_ssize_t dk_nentries;
204
205
206 /* Actual hash table of dk_size entries. It holds indices in dk_entries,
207 or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
208
209 Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
210
211 The size in bytes of an indice depends on dk_size:
212
213 - 1 byte if dk_size <= 0xff (char*)
214 - 2 bytes if dk_size <= 0xffff (int16_t*)
215 - 4 bytes if dk_size <= 0xffffffff (int32_t*)
216 - 8 bytes otherwise (int64_t*)
217
218 Dynamically sized, SIZEOF_VOID_P is minimum. */
219 char dk_indices[]; /* char is required to avoid strict aliasing. */
220
221 /* "PyDictKeyEntry or PyDictUnicodeEntry dk_entries[USABLE_FRACTION(DK_SIZE(dk))];" array follows:
222 see the DK_ENTRIES() / DK_UNICODE_ENTRIES() functions below */
223 };
224
225 /* This must be no more than 250, for the prefix size to fit in one byte. */
226 #define SHARED_KEYS_MAX_SIZE 30
227 #define NEXT_LOG2_SHARED_KEYS_MAX_SIZE 6
228
229 /* Layout of dict values:
230 *
231 * The PyObject *values are preceded by an array of bytes holding
232 * the insertion order and size.
233 * [-1] = prefix size. [-2] = used size. size[-2-n...] = insertion order.
234 */
235 struct _dictvalues {
236 uint8_t capacity;
237 uint8_t size;
238 uint8_t embedded;
239 uint8_t valid;
240 PyObject *values[1];
241 };
242
243 #define DK_LOG_SIZE(dk) _Py_RVALUE((dk)->dk_log2_size)
244 #if SIZEOF_VOID_P > 4
245 #define DK_SIZE(dk) (((int64_t)1)<<DK_LOG_SIZE(dk))
246 #else
247 #define DK_SIZE(dk) (1<<DK_LOG_SIZE(dk))
248 #endif
249
250 static inline void* _DK_ENTRIES(PyDictKeysObject *dk) {
251 int8_t *indices = (int8_t*)(dk->dk_indices);
252 size_t index = (size_t)1 << dk->dk_log2_index_bytes;
253 return (&indices[index]);
254 }
255
256 static inline PyDictKeyEntry* DK_ENTRIES(PyDictKeysObject *dk) {
257 assert(dk->dk_kind == DICT_KEYS_GENERAL);
258 return (PyDictKeyEntry*)_DK_ENTRIES(dk);
259 }
260 static inline PyDictUnicodeEntry* DK_UNICODE_ENTRIES(PyDictKeysObject *dk) {
261 assert(dk->dk_kind != DICT_KEYS_GENERAL);
262 return (PyDictUnicodeEntry*)_DK_ENTRIES(dk);
263 }
264
265 #define DK_IS_UNICODE(dk) ((dk)->dk_kind != DICT_KEYS_GENERAL)
266
267 #define DICT_VERSION_INCREMENT (1 << (DICT_MAX_WATCHERS + DICT_WATCHED_MUTATION_BITS))
268 #define DICT_WATCHER_MASK ((1 << DICT_MAX_WATCHERS) - 1)
269 #define DICT_WATCHER_AND_MODIFICATION_MASK ((1 << (DICT_MAX_WATCHERS + DICT_WATCHED_MUTATION_BITS)) - 1)
270 #define DICT_UNIQUE_ID_SHIFT (32)
271 #define DICT_UNIQUE_ID_MAX ((UINT64_C(1) << (64 - DICT_UNIQUE_ID_SHIFT)) - 1)
272
273
274 PyAPI_FUNC(void)
275 _PyDict_SendEvent(int watcher_bits,
276 PyDict_WatchEvent event,
277 PyDictObject *mp,
278 PyObject *key,
279 PyObject *value);
280
281 static inline void
282 _PyDict_NotifyEvent(PyInterpreterState *interp,
283 PyDict_WatchEvent event,
284 PyDictObject *mp,
285 PyObject *key,
286 PyObject *value)
287 {
288 assert(Py_REFCNT((PyObject*)mp) > 0);
289 int watcher_bits = FT_ATOMIC_LOAD_UINT64_ACQUIRE(mp->_ma_watcher_tag) & DICT_WATCHER_MASK;
290 if (watcher_bits) {
291 RARE_EVENT_STAT_INC(watched_dict_modification);
292 _PyDict_SendEvent(watcher_bits, event, mp, key, value);
293 }
294 }
295
296 extern PyDictObject *_PyObject_MaterializeManagedDict(PyObject *obj);
297
298 PyAPI_FUNC(PyObject *)_PyDict_FromItems(
299 PyObject *const *keys, Py_ssize_t keys_offset,
300 PyObject *const *values, Py_ssize_t values_offset,
301 Py_ssize_t length);
302
303 static inline uint8_t *
304 get_insertion_order_array(PyDictValues *values)
305 {
306 return (uint8_t *)&values->values[values->capacity];
307 }
308
309 static inline void
310 _PyDictValues_AddToInsertionOrder(PyDictValues *values, Py_ssize_t ix)
311 {
312 assert(ix < SHARED_KEYS_MAX_SIZE);
313 int size = values->size;
314 uint8_t *array = get_insertion_order_array(values);
315 assert(size < values->capacity);
316 assert(((uint8_t)ix) == ix);
317 array[size] = (uint8_t)ix;
318 values->size = size+1;
319 }
320
321 static inline size_t
322 shared_keys_usable_size(PyDictKeysObject *keys)
323 {
324 // dk_usable will decrease for each instance that is created and each
325 // value that is added. dk_nentries will increase for each value that
326 // is added. We want to always return the right value or larger.
327 // We therefore increase dk_nentries first and we decrease dk_usable
328 // second, and conversely here we read dk_usable first and dk_entries
329 // second (to avoid the case where we read entries before the increment
330 // and read usable after the decrement)
331 Py_ssize_t dk_usable = FT_ATOMIC_LOAD_SSIZE_ACQUIRE(keys->dk_usable);
332 Py_ssize_t dk_nentries = FT_ATOMIC_LOAD_SSIZE_ACQUIRE(keys->dk_nentries);
333 return dk_nentries + dk_usable;
334 }
335
336 static inline size_t
337 _PyInlineValuesSize(PyTypeObject *tp)
338 {
339 PyDictKeysObject *keys = ((PyHeapTypeObject*)tp)->ht_cached_keys;
340 assert(keys != NULL);
341 size_t size = shared_keys_usable_size(keys);
342 size_t prefix_size = _Py_SIZE_ROUND_UP(size, sizeof(PyObject *));
343 assert(prefix_size < 256);
344 return prefix_size + (size + 1) * sizeof(PyObject *);
345 }
346
347 int
348 _PyDict_DetachFromObject(PyDictObject *dict, PyObject *obj);
349
350 // Enables per-thread ref counting on this dict in the free threading build
351 extern void _PyDict_EnablePerThreadRefcounting(PyObject *op);
352
353 PyDictObject *_PyObject_MaterializeManagedDict_LockHeld(PyObject *);
354
355 // See `_Py_INCREF_TYPE()` in pycore_object.h
356 #ifndef Py_GIL_DISABLED
357 # define _Py_INCREF_DICT Py_INCREF
358 # define _Py_DECREF_DICT Py_DECREF
359 # define _Py_INCREF_BUILTINS Py_INCREF
360 # define _Py_DECREF_BUILTINS Py_DECREF
361 #else
362 static inline Py_ssize_t
363 _PyDict_UniqueId(PyDictObject *mp)
364 {
365 return (Py_ssize_t)(FT_ATOMIC_LOAD_UINT64_RELAXED(mp->_ma_watcher_tag) >> DICT_UNIQUE_ID_SHIFT);
366 }
367
368 static inline void
369 _Py_INCREF_DICT(PyObject *op)
370 {
371 assert(PyDict_Check(op));
372 Py_ssize_t id = _PyDict_UniqueId((PyDictObject *)op);
373 _Py_THREAD_INCREF_OBJECT(op, id);
374 }
375
376 static inline void
377 _Py_DECREF_DICT(PyObject *op)
378 {
379 assert(PyDict_Check(op));
380 Py_ssize_t id = _PyDict_UniqueId((PyDictObject *)op);
381 _Py_THREAD_DECREF_OBJECT(op, id);
382 }
383
384 // Like `_Py_INCREF_DICT`, but also handles non-dict objects because builtins
385 // may not be a dict.
386 static inline void
387 _Py_INCREF_BUILTINS(PyObject *op)
388 {
389 if (PyDict_CheckExact(op)) {
390 _Py_INCREF_DICT(op);
391 }
392 else {
393 Py_INCREF(op);
394 }
395 }
396
397 static inline void
398 _Py_DECREF_BUILTINS(PyObject *op)
399 {
400 if (PyDict_CheckExact(op)) {
401 _Py_DECREF_DICT(op);
402 }
403 else {
404 Py_DECREF(op);
405 }
406 }
407 #endif
408
409 #ifdef __cplusplus
410 }
411 #endif
412 #endif /* !Py_INTERNAL_DICT_H */