Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/python3.14/internal/pycore_dict.h
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 = 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)(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 */
