codekingpro/portable-devtools

1#ifndef Py_INTERNAL_DICT_H2#define Py_INTERNAL_DICT_H3#ifdef __cplusplus4extern "C" {5#endif6 7#ifndef Py_BUILD_CORE8#  error "this header requires Py_BUILD_CORE define"9#endif10 11#include "pycore_object.h"               // PyManagedDictPointer12#include "pycore_pyatomic_ft_wrappers.h" // FT_ATOMIC_LOAD_SSIZE_ACQUIRE13#include "pycore_stackref.h"             // _PyStackRef14#include "pycore_stats.h"15 16// Unsafe flavor of PyDict_GetItemWithError(): no error checking17extern PyObject* _PyDict_GetItemWithError(PyObject *dp, PyObject *key);18 19// Delete an item from a dict if a predicate is true20// Returns -1 on error, 1 if the item was deleted, 0 otherwise21// Export for '_asyncio' shared extension22PyAPI_FUNC(int) _PyDict_DelItemIf(PyObject *mp, PyObject *key,23                                  int (*predicate)(PyObject *value, void *arg),24                                  void *arg);25 26// "KnownHash" variants27// Export for '_asyncio' shared extension28PyAPI_FUNC(int) _PyDict_SetItem_KnownHash(PyObject *mp, PyObject *key,29                                          PyObject *item, Py_hash_t hash);30// Export for '_asyncio' shared extension31PyAPI_FUNC(int) _PyDict_DelItem_KnownHash(PyObject *mp, PyObject *key,32                                          Py_hash_t hash);33 34extern int _PyDict_DelItem_KnownHash_LockHeld(PyObject *mp, PyObject *key,35                                              Py_hash_t hash);36 37extern int _PyDict_Contains_KnownHash(PyObject *, PyObject *, Py_hash_t);38 39// "Id" variants40extern PyObject* _PyDict_GetItemIdWithError(PyObject *dp,41                                            _Py_Identifier *key);42extern int _PyDict_ContainsId(PyObject *, _Py_Identifier *);43extern int _PyDict_SetItemId(PyObject *dp, _Py_Identifier *key, PyObject *item);44extern int _PyDict_DelItemId(PyObject *mp, _Py_Identifier *key);45 46extern int _PyDict_Next(47    PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value, Py_hash_t *hash);48 49extern int _PyDict_HasOnlyStringKeys(PyObject *mp);50 51// Export for '_ctypes' shared extension52PyAPI_FUNC(Py_ssize_t) _PyDict_SizeOf(PyDictObject *);53 54extern 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 occurrence60   of a key wins, if override is 2, a KeyError with conflicting key as61   argument is raised.62*/63PyAPI_FUNC(int) _PyDict_MergeEx(PyObject *mp, PyObject *other, int override);64 65extern void _PyDict_DebugMallocStats(FILE *out);66 67 68/* _PyDictView */69 70typedef struct {71    PyObject_HEAD72    PyDictObject *dv_dict;73} _PyDictViewObject;74 75extern PyObject* _PyDictView_New(PyObject *, PyTypeObject *);76extern PyObject* _PyDictView_Intersect(PyObject* self, PyObject *other);77 78/* other API */79 80typedef 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 87typedef 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 92extern PyDictKeysObject *_PyDict_NewKeysForClass(PyHeapTypeObject *);93extern 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. */97extern 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-free103 * 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. */108extern uint32_t _PyDict_GetKeysVersionForCurrentState(109        PyInterpreterState *interp, PyDictObject *dict);110 111extern size_t _PyDict_KeysSize(PyDictKeysObject *keys);112 113extern 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 */118extern Py_ssize_t _Py_dict_lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);119extern Py_ssize_t _Py_dict_lookup_threadsafe(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);120extern Py_ssize_t _Py_dict_lookup_threadsafe_stackref(PyDictObject *mp, PyObject *key, Py_hash_t hash, _PyStackRef *value_addr);121 122extern int _PyDict_GetMethodStackRef(PyDictObject *dict, PyObject *name, _PyStackRef *method);123 124extern Py_ssize_t _PyDict_LookupIndex(PyDictObject *, PyObject *);125extern 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, and128 * store it in version.129 *130 * Returns DKIX_ERROR if key is not a string or if the keys object is not all131 * strings.132 *133 * Returns DKIX_EMPTY if the key is not present.134 */135extern Py_ssize_t _PyDictKeys_StringLookupAndVersion(PyDictKeysObject* dictkeys, PyObject *key, uint32_t *version);136extern Py_ssize_t _PyDictKeys_StringLookupSplit(PyDictKeysObject* dictkeys, PyObject *key);137PyAPI_FUNC(PyObject *)_PyDict_LoadGlobal(PyDictObject *, PyDictObject *, PyObject *);138PyAPI_FUNC(void) _PyDict_LoadGlobalStackRef(PyDictObject *, PyDictObject *, PyObject *, _PyStackRef *);139 140// Loads the __builtins__ object from the globals dict. Returns a new reference.141extern PyObject *_PyDict_LoadBuiltinsFromGlobals(PyObject *globals);142 143/* Consumes references to key and value */144PyAPI_FUNC(int) _PyDict_SetItem_Take2(PyDictObject *op, PyObject *key, PyObject *value);145extern int _PyDict_SetItem_LockHeld(PyDictObject *dict, PyObject *name, PyObject *value);146// Export for '_asyncio' shared extension147PyAPI_FUNC(int) _PyDict_SetItem_KnownHash_LockHeld(PyDictObject *mp, PyObject *key,148                                                   PyObject *value, Py_hash_t hash);149// Export for '_asyncio' shared extension150PyAPI_FUNC(int) _PyDict_GetItemRef_KnownHash_LockHeld(PyDictObject *op, PyObject *key, Py_hash_t hash, PyObject **result);151extern int _PyDict_GetItemRef_KnownHash(PyDictObject *op, PyObject *key, Py_hash_t hash, PyObject **result);152extern int _PyDict_GetItemRef_Unicode_LockHeld(PyDictObject *op, PyObject *key, PyObject **result);153extern int _PyObjectDict_SetItem(PyTypeObject *tp, PyObject *obj, PyObject **dictptr, PyObject *name, PyObject *value);154 155extern int _PyDict_Pop_KnownHash(156    PyDictObject *dict,157    PyObject *key,158    Py_hash_t hash,159    PyObject **result);160 161extern void _PyDict_Clear_LockHeld(PyObject *op);162 163#ifdef Py_GIL_DISABLED164PyAPI_FUNC(void) _PyDict_EnsureSharedOnRead(PyDictObject *mp);165#endif166 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 172typedef enum {173    DICT_KEYS_GENERAL = 0,174    DICT_KEYS_UNICODE = 1,175    DICT_KEYS_SPLIT = 2176} DictKeysKind;177 178/* See dictobject.c for actual layout of DictKeysObject */179struct _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_DISABLED192    /* Lock used to protect shared keys */193    PyMutex dk_mutex;194#endif195 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 30227#define NEXT_LOG2_SHARED_KEYS_MAX_SIZE 6228 229/* Layout of dict values:230 *231 * The PyObject *values are preceded by an array of bytes holding232 * the insertion order and size.233 * [-1] = prefix size. [-2] = used size. size[-2-n...] = insertion order.234 */235struct _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 > 4245#define DK_SIZE(dk)      (((int64_t)1)<<DK_LOG_SIZE(dk))246#else247#define DK_SIZE(dk)      (1<<DK_LOG_SIZE(dk))248#endif249 250static 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 256static inline PyDictKeyEntry* DK_ENTRIES(PyDictKeysObject *dk) {257    assert(dk->dk_kind == DICT_KEYS_GENERAL);258    return (PyDictKeyEntry*)_DK_ENTRIES(dk);259}260static 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 274PyAPI_FUNC(void)275_PyDict_SendEvent(int watcher_bits,276                  PyDict_WatchEvent event,277                  PyDictObject *mp,278                  PyObject *key,279                  PyObject *value);280 281static inline void282_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 296extern PyDictObject *_PyObject_MaterializeManagedDict(PyObject *obj);297 298PyAPI_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 303static inline uint8_t *304get_insertion_order_array(PyDictValues *values)305{306    return (uint8_t *)&values->values[values->capacity];307}308 309static inline void310_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 321static inline size_t322shared_keys_usable_size(PyDictKeysObject *keys)323{324    // dk_usable will decrease for each instance that is created and each325    // value that is added.  dk_nentries will increase for each value that326    // is added.  We want to always return the right value or larger.327    // We therefore increase dk_nentries first and we decrease dk_usable328    // second, and conversely here we read dk_usable first and dk_entries329    // second (to avoid the case where we read entries before the increment330    // 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 336static inline size_t337_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 347int348_PyDict_DetachFromObject(PyDictObject *dict, PyObject *obj);349 350// Enables per-thread ref counting on this dict in the free threading build351extern void _PyDict_EnablePerThreadRefcounting(PyObject *op);352 353PyDictObject *_PyObject_MaterializeManagedDict_LockHeld(PyObject *);354 355// See `_Py_INCREF_TYPE()` in pycore_object.h356#ifndef Py_GIL_DISABLED357#  define _Py_INCREF_DICT Py_INCREF358#  define _Py_DECREF_DICT Py_DECREF359#  define _Py_INCREF_BUILTINS Py_INCREF360#  define _Py_DECREF_BUILTINS Py_DECREF361#else362static inline Py_ssize_t363_PyDict_UniqueId(PyDictObject *mp)364{365    return (Py_ssize_t)(mp->_ma_watcher_tag >> DICT_UNIQUE_ID_SHIFT);366}367 368static inline void369_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 376static inline void377_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 builtins385// may not be a dict.386static inline void387_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 397static inline void398_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#endif408 409#ifdef __cplusplus410}411#endif412#endif   /* !Py_INTERNAL_DICT_H */413