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_freelist.h" // _PyFreeListState
12 #include "pycore_identifier.h" // _Py_Identifier
13 #include "pycore_object.h" // PyManagedDictPointer
14 #include "pycore_pyatomic_ft_wrappers.h" // FT_ATOMIC_LOAD_SSIZE_ACQUIRE
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 extern int _PyDict_Contains_KnownHash(PyObject *, PyObject *, Py_hash_t);
34
35 // "Id" variants
36 extern PyObject* _PyDict_GetItemIdWithError(PyObject *dp,
37 _Py_Identifier *key);
38 extern int _PyDict_ContainsId(PyObject *, _Py_Identifier *);
39 extern int _PyDict_SetItemId(PyObject *dp, _Py_Identifier *key, PyObject *item);
40 extern int _PyDict_DelItemId(PyObject *mp, _Py_Identifier *key);
41
42 extern int _PyDict_Next(
43 PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value, Py_hash_t *hash);
44
45 extern int _PyDict_HasOnlyStringKeys(PyObject *mp);
46
47 extern void _PyDict_MaybeUntrack(PyObject *mp);
48
49 // Export for '_ctypes' shared extension
50 PyAPI_FUNC(Py_ssize_t) _PyDict_SizeOf(PyDictObject *);
51
52 #define _PyDict_HasSplitTable(d) ((d)->ma_values != NULL)
53
54 /* Like PyDict_Merge, but override can be 0, 1 or 2. If override is 0,
55 the first occurrence of a key wins, if override is 1, the last occurrence
56 of a key wins, if override is 2, a KeyError with conflicting key as
57 argument is raised.
58 */
59 PyAPI_FUNC(int) _PyDict_MergeEx(PyObject *mp, PyObject *other, int override);
60
61 extern void _PyDict_DebugMallocStats(FILE *out);
62
63
64 /* _PyDictView */
65
66 typedef struct {
67 PyObject_HEAD
68 PyDictObject *dv_dict;
69 } _PyDictViewObject;
70
71 extern PyObject* _PyDictView_New(PyObject *, PyTypeObject *);
72 extern PyObject* _PyDictView_Intersect(PyObject* self, PyObject *other);
73
74 /* other API */
75
76 typedef struct {
77 /* Cached hash code of me_key. */
78 Py_hash_t me_hash;
79 PyObject *me_key;
80 PyObject *me_value; /* This field is only meaningful for combined tables */
81 } PyDictKeyEntry;
82
83 typedef struct {
84 PyObject *me_key; /* The key must be Unicode and have hash. */
85 PyObject *me_value; /* This field is only meaningful for combined tables */
86 } PyDictUnicodeEntry;
87
88 extern PyDictKeysObject *_PyDict_NewKeysForClass(void);
89 extern PyObject *_PyDict_FromKeys(PyObject *, PyObject *, PyObject *);
90
91 /* Gets a version number unique to the current state of the keys of dict, if possible.
92 * Returns the version number, or zero if it was not possible to get a version number. */
93 extern uint32_t _PyDictKeys_GetVersionForCurrentState(
94 PyInterpreterState *interp, PyDictKeysObject *dictkeys);
95
96 extern size_t _PyDict_KeysSize(PyDictKeysObject *keys);
97
98 extern void _PyDictKeys_DecRef(PyDictKeysObject *keys);
99
100 /* _Py_dict_lookup() returns index of entry which can be used like DK_ENTRIES(dk)[index].
101 * -1 when no entry found, -3 when compare raises error.
102 */
103 extern Py_ssize_t _Py_dict_lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
104 extern Py_ssize_t _Py_dict_lookup_threadsafe(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
105
106 extern Py_ssize_t _PyDict_LookupIndex(PyDictObject *, PyObject *);
107 extern Py_ssize_t _PyDictKeys_StringLookup(PyDictKeysObject* dictkeys, PyObject *key);
108 PyAPI_FUNC(PyObject *)_PyDict_LoadGlobal(PyDictObject *, PyDictObject *, PyObject *);
109
110 /* Consumes references to key and value */
111 PyAPI_FUNC(int) _PyDict_SetItem_Take2(PyDictObject *op, PyObject *key, PyObject *value);
112 extern int _PyDict_SetItem_LockHeld(PyDictObject *dict, PyObject *name, PyObject *value);
113 // Export for '_asyncio' shared extension
114 PyAPI_FUNC(int) _PyDict_SetItem_KnownHash_LockHeld(PyDictObject *mp, PyObject *key,
115 PyObject *value, Py_hash_t hash);
116 // Export for '_asyncio' shared extension
117 PyAPI_FUNC(int) _PyDict_GetItemRef_KnownHash_LockHeld(PyDictObject *op, PyObject *key, Py_hash_t hash, PyObject **result);
118 extern int _PyDict_GetItemRef_KnownHash(PyDictObject *op, PyObject *key, Py_hash_t hash, PyObject **result);
119 extern int _PyDict_GetItemRef_Unicode_LockHeld(PyDictObject *op, PyObject *key, PyObject **result);
120 extern int _PyObjectDict_SetItem(PyTypeObject *tp, PyObject *obj, PyObject **dictptr, PyObject *name, PyObject *value);
121
122 extern int _PyDict_Pop_KnownHash(
123 PyDictObject *dict,
124 PyObject *key,
125 Py_hash_t hash,
126 PyObject **result);
127
128 #define DKIX_EMPTY (-1)
129 #define DKIX_DUMMY (-2) /* Used internally */
130 #define DKIX_ERROR (-3)
131 #define DKIX_KEY_CHANGED (-4) /* Used internally */
132
133 typedef enum {
134 DICT_KEYS_GENERAL = 0,
135 DICT_KEYS_UNICODE = 1,
136 DICT_KEYS_SPLIT = 2
137 } DictKeysKind;
138
139 /* See dictobject.c for actual layout of DictKeysObject */
140 struct _dictkeysobject {
141 Py_ssize_t dk_refcnt;
142
143 /* Size of the hash table (dk_indices). It must be a power of 2. */
144 uint8_t dk_log2_size;
145
146 /* Size of the hash table (dk_indices) by bytes. */
147 uint8_t dk_log2_index_bytes;
148
149 /* Kind of keys */
150 uint8_t dk_kind;
151
152 #ifdef Py_GIL_DISABLED
153 /* Lock used to protect shared keys */
154 PyMutex dk_mutex;
155 #endif
156
157 /* Version number -- Reset to 0 by any modification to keys */
158 uint32_t dk_version;
159
160 /* Number of usable entries in dk_entries. */
161 Py_ssize_t dk_usable;
162
163 /* Number of used entries in dk_entries. */
164 Py_ssize_t dk_nentries;
165
166
167 /* Actual hash table of dk_size entries. It holds indices in dk_entries,
168 or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
169
170 Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
171
172 The size in bytes of an indice depends on dk_size:
173
174 - 1 byte if dk_size <= 0xff (char*)
175 - 2 bytes if dk_size <= 0xffff (int16_t*)
176 - 4 bytes if dk_size <= 0xffffffff (int32_t*)
177 - 8 bytes otherwise (int64_t*)
178
179 Dynamically sized, SIZEOF_VOID_P is minimum. */
180 char dk_indices[]; /* char is required to avoid strict aliasing. */
181
182 /* "PyDictKeyEntry or PyDictUnicodeEntry dk_entries[USABLE_FRACTION(DK_SIZE(dk))];" array follows:
183 see the DK_ENTRIES() / DK_UNICODE_ENTRIES() functions below */
184 };
185
186 /* This must be no more than 250, for the prefix size to fit in one byte. */
187 #define SHARED_KEYS_MAX_SIZE 30
188 #define NEXT_LOG2_SHARED_KEYS_MAX_SIZE 6
189
190 /* Layout of dict values:
191 *
192 * The PyObject *values are preceded by an array of bytes holding
193 * the insertion order and size.
194 * [-1] = prefix size. [-2] = used size. size[-2-n...] = insertion order.
195 */
196 struct _dictvalues {
197 uint8_t capacity;
198 uint8_t size;
199 uint8_t embedded;
200 uint8_t valid;
201 PyObject *values[1];
202 };
203
204 #define DK_LOG_SIZE(dk) _Py_RVALUE((dk)->dk_log2_size)
205 #if SIZEOF_VOID_P > 4
206 #define DK_SIZE(dk) (((int64_t)1)<<DK_LOG_SIZE(dk))
207 #else
208 #define DK_SIZE(dk) (1<<DK_LOG_SIZE(dk))
209 #endif
210
_DK_ENTRIES(PyDictKeysObject * dk)211 static inline void* _DK_ENTRIES(PyDictKeysObject *dk) {
212 int8_t *indices = (int8_t*)(dk->dk_indices);
213 size_t index = (size_t)1 << dk->dk_log2_index_bytes;
214 return (&indices[index]);
215 }
216
DK_ENTRIES(PyDictKeysObject * dk)217 static inline PyDictKeyEntry* DK_ENTRIES(PyDictKeysObject *dk) {
218 assert(dk->dk_kind == DICT_KEYS_GENERAL);
219 return (PyDictKeyEntry*)_DK_ENTRIES(dk);
220 }
DK_UNICODE_ENTRIES(PyDictKeysObject * dk)221 static inline PyDictUnicodeEntry* DK_UNICODE_ENTRIES(PyDictKeysObject *dk) {
222 assert(dk->dk_kind != DICT_KEYS_GENERAL);
223 return (PyDictUnicodeEntry*)_DK_ENTRIES(dk);
224 }
225
226 #define DK_IS_UNICODE(dk) ((dk)->dk_kind != DICT_KEYS_GENERAL)
227
228 #define DICT_VERSION_INCREMENT (1 << (DICT_MAX_WATCHERS + DICT_WATCHED_MUTATION_BITS))
229 #define DICT_WATCHER_MASK ((1 << DICT_MAX_WATCHERS) - 1)
230 #define DICT_WATCHER_AND_MODIFICATION_MASK ((1 << (DICT_MAX_WATCHERS + DICT_WATCHED_MUTATION_BITS)) - 1)
231
232 #ifdef Py_GIL_DISABLED
233
234 #define THREAD_LOCAL_DICT_VERSION_COUNT 256
235 #define THREAD_LOCAL_DICT_VERSION_BATCH THREAD_LOCAL_DICT_VERSION_COUNT * DICT_VERSION_INCREMENT
236
237 static inline uint64_t
dict_next_version(PyInterpreterState * interp)238 dict_next_version(PyInterpreterState *interp)
239 {
240 PyThreadState *tstate = PyThreadState_GET();
241 uint64_t cur_progress = (tstate->dict_global_version &
242 (THREAD_LOCAL_DICT_VERSION_BATCH - 1));
243 if (cur_progress == 0) {
244 uint64_t next = _Py_atomic_add_uint64(&interp->dict_state.global_version,
245 THREAD_LOCAL_DICT_VERSION_BATCH);
246 tstate->dict_global_version = next;
247 }
248 return tstate->dict_global_version += DICT_VERSION_INCREMENT;
249 }
250
251 #define DICT_NEXT_VERSION(INTERP) dict_next_version(INTERP)
252
253 #else
254 #define DICT_NEXT_VERSION(INTERP) \
255 ((INTERP)->dict_state.global_version += DICT_VERSION_INCREMENT)
256 #endif
257
258 void
259 _PyDict_SendEvent(int watcher_bits,
260 PyDict_WatchEvent event,
261 PyDictObject *mp,
262 PyObject *key,
263 PyObject *value);
264
265 static inline uint64_t
_PyDict_NotifyEvent(PyInterpreterState * interp,PyDict_WatchEvent event,PyDictObject * mp,PyObject * key,PyObject * value)266 _PyDict_NotifyEvent(PyInterpreterState *interp,
267 PyDict_WatchEvent event,
268 PyDictObject *mp,
269 PyObject *key,
270 PyObject *value)
271 {
272 assert(Py_REFCNT((PyObject*)mp) > 0);
273 int watcher_bits = mp->ma_version_tag & DICT_WATCHER_MASK;
274 if (watcher_bits) {
275 RARE_EVENT_STAT_INC(watched_dict_modification);
276 _PyDict_SendEvent(watcher_bits, event, mp, key, value);
277 }
278 return DICT_NEXT_VERSION(interp) | (mp->ma_version_tag & DICT_WATCHER_AND_MODIFICATION_MASK);
279 }
280
281 extern PyDictObject *_PyObject_MaterializeManagedDict(PyObject *obj);
282
283 PyAPI_FUNC(PyObject *)_PyDict_FromItems(
284 PyObject *const *keys, Py_ssize_t keys_offset,
285 PyObject *const *values, Py_ssize_t values_offset,
286 Py_ssize_t length);
287
288 static inline uint8_t *
get_insertion_order_array(PyDictValues * values)289 get_insertion_order_array(PyDictValues *values)
290 {
291 return (uint8_t *)&values->values[values->capacity];
292 }
293
294 static inline void
_PyDictValues_AddToInsertionOrder(PyDictValues * values,Py_ssize_t ix)295 _PyDictValues_AddToInsertionOrder(PyDictValues *values, Py_ssize_t ix)
296 {
297 assert(ix < SHARED_KEYS_MAX_SIZE);
298 int size = values->size;
299 uint8_t *array = get_insertion_order_array(values);
300 assert(size < values->capacity);
301 assert(((uint8_t)ix) == ix);
302 array[size] = (uint8_t)ix;
303 values->size = size+1;
304 }
305
306 static inline size_t
shared_keys_usable_size(PyDictKeysObject * keys)307 shared_keys_usable_size(PyDictKeysObject *keys)
308 {
309 // dk_usable will decrease for each instance that is created and each
310 // value that is added. dk_nentries will increase for each value that
311 // is added. We want to always return the right value or larger.
312 // We therefore increase dk_nentries first and we decrease dk_usable
313 // second, and conversely here we read dk_usable first and dk_entries
314 // second (to avoid the case where we read entries before the increment
315 // and read usable after the decrement)
316 Py_ssize_t dk_usable = FT_ATOMIC_LOAD_SSIZE_ACQUIRE(keys->dk_usable);
317 Py_ssize_t dk_nentries = FT_ATOMIC_LOAD_SSIZE_ACQUIRE(keys->dk_nentries);
318 return dk_nentries + dk_usable;
319 }
320
321 static inline size_t
_PyInlineValuesSize(PyTypeObject * tp)322 _PyInlineValuesSize(PyTypeObject *tp)
323 {
324 PyDictKeysObject *keys = ((PyHeapTypeObject*)tp)->ht_cached_keys;
325 assert(keys != NULL);
326 size_t size = shared_keys_usable_size(keys);
327 size_t prefix_size = _Py_SIZE_ROUND_UP(size, sizeof(PyObject *));
328 assert(prefix_size < 256);
329 return prefix_size + (size + 1) * sizeof(PyObject *);
330 }
331
332 int
333 _PyDict_DetachFromObject(PyDictObject *dict, PyObject *obj);
334
335 PyDictObject *_PyObject_MaterializeManagedDict_LockHeld(PyObject *);
336
337 #ifdef __cplusplus
338 }
339 #endif
340 #endif /* !Py_INTERNAL_DICT_H */
341