python3.13/internal/pycore_dict.h

0001 #ifndef Py_INTERNAL_DICT_H
0002 #define Py_INTERNAL_DICT_H
0003 #ifdef __cplusplus
0004 extern "C" {
0005 #endif
0006
0007 #ifndef Py_BUILD_CORE
0008 #  error "this header requires Py_BUILD_CORE define"
0009 #endif
0010
0011 #include "pycore_freelist.h"             // _PyFreeListState
0012 #include "pycore_identifier.h"           // _Py_Identifier
0013 #include "pycore_object.h"               // PyManagedDictPointer
0014 #include "pycore_pyatomic_ft_wrappers.h" // FT_ATOMIC_LOAD_SSIZE_ACQUIRE
0015
0016 // Unsafe flavor of PyDict_GetItemWithError(): no error checking
0017 extern PyObject* _PyDict_GetItemWithError(PyObject *dp, PyObject *key);
0018
0019 // Delete an item from a dict if a predicate is true
0020 // Returns -1 on error, 1 if the item was deleted, 0 otherwise
0021 // Export for '_asyncio' shared extension
0022 PyAPI_FUNC(int) _PyDict_DelItemIf(PyObject *mp, PyObject *key,
0023                                   int (*predicate)(PyObject *value, void *arg),
0024                                   void *arg);
0025
0026 // "KnownHash" variants
0027 // Export for '_asyncio' shared extension
0028 PyAPI_FUNC(int) _PyDict_SetItem_KnownHash(PyObject *mp, PyObject *key,
0029                                           PyObject *item, Py_hash_t hash);
0030 // Export for '_asyncio' shared extension
0031 PyAPI_FUNC(int) _PyDict_DelItem_KnownHash(PyObject *mp, PyObject *key,
0032                                           Py_hash_t hash);
0033 extern int _PyDict_Contains_KnownHash(PyObject *, PyObject *, Py_hash_t);
0034
0035 // "Id" variants
0036 extern PyObject* _PyDict_GetItemIdWithError(PyObject *dp,
0037                                             _Py_Identifier *key);
0038 extern int _PyDict_ContainsId(PyObject *, _Py_Identifier *);
0039 extern int _PyDict_SetItemId(PyObject *dp, _Py_Identifier *key, PyObject *item);
0040 extern int _PyDict_DelItemId(PyObject *mp, _Py_Identifier *key);
0041
0042 extern int _PyDict_Next(
0043     PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value, Py_hash_t *hash);
0044
0045 extern int _PyDict_HasOnlyStringKeys(PyObject *mp);
0046
0047 extern void _PyDict_MaybeUntrack(PyObject *mp);
0048
0049 // Export for '_ctypes' shared extension
0050 PyAPI_FUNC(Py_ssize_t) _PyDict_SizeOf(PyDictObject *);
0051
0052 #define _PyDict_HasSplitTable(d) ((d)->ma_values != NULL)
0053
0054 /* Like PyDict_Merge, but override can be 0, 1 or 2.  If override is 0,
0055    the first occurrence of a key wins, if override is 1, the last occurrence
0056    of a key wins, if override is 2, a KeyError with conflicting key as
0057    argument is raised.
0058 */
0059 PyAPI_FUNC(int) _PyDict_MergeEx(PyObject *mp, PyObject *other, int override);
0060
0061 extern void _PyDict_DebugMallocStats(FILE *out);
0062
0063
0064 /* _PyDictView */
0065
0066 typedef struct {
0067     PyObject_HEAD
0068     PyDictObject *dv_dict;
0069 } _PyDictViewObject;
0070
0071 extern PyObject* _PyDictView_New(PyObject *, PyTypeObject *);
0072 extern PyObject* _PyDictView_Intersect(PyObject* self, PyObject *other);
0073
0074 /* other API */
0075
0076 typedef struct {
0077     /* Cached hash code of me_key. */
0078     Py_hash_t me_hash;
0079     PyObject *me_key;
0080     PyObject *me_value; /* This field is only meaningful for combined tables */
0081 } PyDictKeyEntry;
0082
0083 typedef struct {
0084     PyObject *me_key;   /* The key must be Unicode and have hash. */
0085     PyObject *me_value; /* This field is only meaningful for combined tables */
0086 } PyDictUnicodeEntry;
0087
0088 extern PyDictKeysObject *_PyDict_NewKeysForClass(void);
0089 extern PyObject *_PyDict_FromKeys(PyObject *, PyObject *, PyObject *);
0090
0091 /* Gets a version number unique to the current state of the keys of dict, if possible.
0092  * Returns the version number, or zero if it was not possible to get a version number. */
0093 extern uint32_t _PyDictKeys_GetVersionForCurrentState(
0094         PyInterpreterState *interp, PyDictKeysObject *dictkeys);
0095
0096 extern size_t _PyDict_KeysSize(PyDictKeysObject *keys);
0097
0098 extern void _PyDictKeys_DecRef(PyDictKeysObject *keys);
0099
0100 /* _Py_dict_lookup() returns index of entry which can be used like DK_ENTRIES(dk)[index].
0101  * -1 when no entry found, -3 when compare raises error.
0102  */
0103 extern Py_ssize_t _Py_dict_lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
0104 extern Py_ssize_t _Py_dict_lookup_threadsafe(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
0105
0106 extern Py_ssize_t _PyDict_LookupIndex(PyDictObject *, PyObject *);
0107 extern Py_ssize_t _PyDictKeys_StringLookup(PyDictKeysObject* dictkeys, PyObject *key);
0108 PyAPI_FUNC(PyObject *)_PyDict_LoadGlobal(PyDictObject *, PyDictObject *, PyObject *);
0109
0110 /* Consumes references to key and value */
0111 PyAPI_FUNC(int) _PyDict_SetItem_Take2(PyDictObject *op, PyObject *key, PyObject *value);
0112 extern int _PyDict_SetItem_LockHeld(PyDictObject *dict, PyObject *name, PyObject *value);
0113 // Export for '_asyncio' shared extension
0114 PyAPI_FUNC(int) _PyDict_SetItem_KnownHash_LockHeld(PyDictObject *mp, PyObject *key,
0115                                                    PyObject *value, Py_hash_t hash);
0116 // Export for '_asyncio' shared extension
0117 PyAPI_FUNC(int) _PyDict_GetItemRef_KnownHash_LockHeld(PyDictObject *op, PyObject *key, Py_hash_t hash, PyObject **result);
0118 extern int _PyDict_GetItemRef_KnownHash(PyDictObject *op, PyObject *key, Py_hash_t hash, PyObject **result);
0119 extern int _PyDict_GetItemRef_Unicode_LockHeld(PyDictObject *op, PyObject *key, PyObject **result);
0120 extern int _PyObjectDict_SetItem(PyTypeObject *tp, PyObject *obj, PyObject **dictptr, PyObject *name, PyObject *value);
0121
0122 extern int _PyDict_Pop_KnownHash(
0123     PyDictObject *dict,
0124     PyObject *key,
0125     Py_hash_t hash,
0126     PyObject **result);
0127
0128 #define DKIX_EMPTY (-1)
0129 #define DKIX_DUMMY (-2)  /* Used internally */
0130 #define DKIX_ERROR (-3)
0131 #define DKIX_KEY_CHANGED (-4) /* Used internally */
0132
0133 typedef enum {
0134     DICT_KEYS_GENERAL = 0,
0135     DICT_KEYS_UNICODE = 1,
0136     DICT_KEYS_SPLIT = 2
0137 } DictKeysKind;
0138
0139 /* See dictobject.c for actual layout of DictKeysObject */
0140 struct _dictkeysobject {
0141     Py_ssize_t dk_refcnt;
0142
0143     /* Size of the hash table (dk_indices). It must be a power of 2. */
0144     uint8_t dk_log2_size;
0145
0146     /* Size of the hash table (dk_indices) by bytes. */
0147     uint8_t dk_log2_index_bytes;
0148
0149     /* Kind of keys */
0150     uint8_t dk_kind;
0151
0152 #ifdef Py_GIL_DISABLED
0153     /* Lock used to protect shared keys */
0154     PyMutex dk_mutex;
0155 #endif
0156
0157     /* Version number -- Reset to 0 by any modification to keys */
0158     uint32_t dk_version;
0159
0160     /* Number of usable entries in dk_entries. */
0161     Py_ssize_t dk_usable;
0162
0163     /* Number of used entries in dk_entries. */
0164     Py_ssize_t dk_nentries;
0165
0166
0167     /* Actual hash table of dk_size entries. It holds indices in dk_entries,
0168        or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
0169
0170        Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
0171
0172        The size in bytes of an indice depends on dk_size:
0173
0174        - 1 byte if dk_size <= 0xff (char*)
0175        - 2 bytes if dk_size <= 0xffff (int16_t*)
0176        - 4 bytes if dk_size <= 0xffffffff (int32_t*)
0177        - 8 bytes otherwise (int64_t*)
0178
0179        Dynamically sized, SIZEOF_VOID_P is minimum. */
0180     char dk_indices[];  /* char is required to avoid strict aliasing. */
0181
0182     /* "PyDictKeyEntry or PyDictUnicodeEntry dk_entries[USABLE_FRACTION(DK_SIZE(dk))];" array follows:
0183        see the DK_ENTRIES() / DK_UNICODE_ENTRIES() functions below */
0184 };
0185
0186 /* This must be no more than 250, for the prefix size to fit in one byte. */
0187 #define SHARED_KEYS_MAX_SIZE 30
0188 #define NEXT_LOG2_SHARED_KEYS_MAX_SIZE 6
0189
0190 /* Layout of dict values:
0191  *
0192  * The PyObject *values are preceded by an array of bytes holding
0193  * the insertion order and size.
0194  * [-1] = prefix size. [-2] = used size. size[-2-n...] = insertion order.
0195  */
0196 struct _dictvalues {
0197     uint8_t capacity;
0198     uint8_t size;
0199     uint8_t embedded;
0200     uint8_t valid;
0201     PyObject *values[1];
0202 };
0203
0204 #define DK_LOG_SIZE(dk)  _Py_RVALUE((dk)->dk_log2_size)
0205 #if SIZEOF_VOID_P > 4
0206 #define DK_SIZE(dk)      (((int64_t)1)<<DK_LOG_SIZE(dk))
0207 #else
0208 #define DK_SIZE(dk)      (1<<DK_LOG_SIZE(dk))
0209 #endif
0210
0211 static inline void* _DK_ENTRIES(PyDictKeysObject *dk) {
0212     int8_t *indices = (int8_t*)(dk->dk_indices);
0213     size_t index = (size_t)1 << dk->dk_log2_index_bytes;
0214     return (&indices[index]);
0215 }
0216
0217 static inline PyDictKeyEntry* DK_ENTRIES(PyDictKeysObject *dk) {
0218     assert(dk->dk_kind == DICT_KEYS_GENERAL);
0219     return (PyDictKeyEntry*)_DK_ENTRIES(dk);
0220 }
0221 static inline PyDictUnicodeEntry* DK_UNICODE_ENTRIES(PyDictKeysObject *dk) {
0222     assert(dk->dk_kind != DICT_KEYS_GENERAL);
0223     return (PyDictUnicodeEntry*)_DK_ENTRIES(dk);
0224 }
0225
0226 #define DK_IS_UNICODE(dk) ((dk)->dk_kind != DICT_KEYS_GENERAL)
0227
0228 #define DICT_VERSION_INCREMENT (1 << (DICT_MAX_WATCHERS + DICT_WATCHED_MUTATION_BITS))
0229 #define DICT_WATCHER_MASK ((1 << DICT_MAX_WATCHERS) - 1)
0230 #define DICT_WATCHER_AND_MODIFICATION_MASK ((1 << (DICT_MAX_WATCHERS + DICT_WATCHED_MUTATION_BITS)) - 1)
0231
0232 #ifdef Py_GIL_DISABLED
0233
0234 #define THREAD_LOCAL_DICT_VERSION_COUNT 256
0235 #define THREAD_LOCAL_DICT_VERSION_BATCH THREAD_LOCAL_DICT_VERSION_COUNT * DICT_VERSION_INCREMENT
0236
0237 static inline uint64_t
0238 dict_next_version(PyInterpreterState *interp)
0239 {
0240     PyThreadState *tstate = PyThreadState_GET();
0241     uint64_t cur_progress = (tstate->dict_global_version &
0242                             (THREAD_LOCAL_DICT_VERSION_BATCH - 1));
0243     if (cur_progress == 0) {
0244         uint64_t next = _Py_atomic_add_uint64(&interp->dict_state.global_version,
0245                                               THREAD_LOCAL_DICT_VERSION_BATCH);
0246         tstate->dict_global_version = next;
0247     }
0248     return tstate->dict_global_version += DICT_VERSION_INCREMENT;
0249 }
0250
0251 #define DICT_NEXT_VERSION(INTERP) dict_next_version(INTERP)
0252
0253 #else
0254 #define DICT_NEXT_VERSION(INTERP) \
0255     ((INTERP)->dict_state.global_version += DICT_VERSION_INCREMENT)
0256 #endif
0257
0258 void
0259 _PyDict_SendEvent(int watcher_bits,
0260                   PyDict_WatchEvent event,
0261                   PyDictObject *mp,
0262                   PyObject *key,
0263                   PyObject *value);
0264
0265 static inline uint64_t
0266 _PyDict_NotifyEvent(PyInterpreterState *interp,
0267                     PyDict_WatchEvent event,
0268                     PyDictObject *mp,
0269                     PyObject *key,
0270                     PyObject *value)
0271 {
0272     assert(Py_REFCNT((PyObject*)mp) > 0);
0273     int watcher_bits = mp->ma_version_tag & DICT_WATCHER_MASK;
0274     if (watcher_bits) {
0275         RARE_EVENT_STAT_INC(watched_dict_modification);
0276         _PyDict_SendEvent(watcher_bits, event, mp, key, value);
0277     }
0278     return DICT_NEXT_VERSION(interp) | (mp->ma_version_tag & DICT_WATCHER_AND_MODIFICATION_MASK);
0279 }
0280
0281 extern PyDictObject *_PyObject_MaterializeManagedDict(PyObject *obj);
0282
0283 PyAPI_FUNC(PyObject *)_PyDict_FromItems(
0284         PyObject *const *keys, Py_ssize_t keys_offset,
0285         PyObject *const *values, Py_ssize_t values_offset,
0286         Py_ssize_t length);
0287
0288 static inline uint8_t *
0289 get_insertion_order_array(PyDictValues *values)
0290 {
0291     return (uint8_t *)&values->values[values->capacity];
0292 }
0293
0294 static inline void
0295 _PyDictValues_AddToInsertionOrder(PyDictValues *values, Py_ssize_t ix)
0296 {
0297     assert(ix < SHARED_KEYS_MAX_SIZE);
0298     int size = values->size;
0299     uint8_t *array = get_insertion_order_array(values);
0300     assert(size < values->capacity);
0301     assert(((uint8_t)ix) == ix);
0302     array[size] = (uint8_t)ix;
0303     values->size = size+1;
0304 }
0305
0306 static inline size_t
0307 shared_keys_usable_size(PyDictKeysObject *keys)
0308 {
0309     // dk_usable will decrease for each instance that is created and each
0310     // value that is added.  dk_nentries will increase for each value that
0311     // is added.  We want to always return the right value or larger.
0312     // We therefore increase dk_nentries first and we decrease dk_usable
0313     // second, and conversely here we read dk_usable first and dk_entries
0314     // second (to avoid the case where we read entries before the increment
0315     // and read usable after the decrement)
0316     Py_ssize_t dk_usable = FT_ATOMIC_LOAD_SSIZE_ACQUIRE(keys->dk_usable);
0317     Py_ssize_t dk_nentries = FT_ATOMIC_LOAD_SSIZE_ACQUIRE(keys->dk_nentries);
0318     return dk_nentries + dk_usable;
0319 }
0320
0321 static inline size_t
0322 _PyInlineValuesSize(PyTypeObject *tp)
0323 {
0324     PyDictKeysObject *keys = ((PyHeapTypeObject*)tp)->ht_cached_keys;
0325     assert(keys != NULL);
0326     size_t size = shared_keys_usable_size(keys);
0327     size_t prefix_size = _Py_SIZE_ROUND_UP(size, sizeof(PyObject *));
0328     assert(prefix_size < 256);
0329     return prefix_size + (size + 1) * sizeof(PyObject *);
0330 }
0331
0332 int
0333 _PyDict_DetachFromObject(PyDictObject *dict, PyObject *obj);
0334
0335 PyDictObject *_PyObject_MaterializeManagedDict_LockHeld(PyObject *);
0336
0337 #ifdef __cplusplus
0338 }
0339 #endif
0340 #endif   /* !Py_INTERNAL_DICT_H */