python3.12/internal/pycore_dict.h

0001
0002 #ifndef Py_INTERNAL_DICT_H
0003 #define Py_INTERNAL_DICT_H
0004 #ifdef __cplusplus
0005 extern "C" {
0006 #endif
0007
0008 #ifndef Py_BUILD_CORE
0009 #  error "this header requires Py_BUILD_CORE define"
0010 #endif
0011
0012 #include "pycore_dict_state.h"
0013 #include "pycore_runtime.h"         // _PyRuntime
0014
0015
0016 /* runtime lifecycle */
0017
0018 extern void _PyDict_Fini(PyInterpreterState *interp);
0019
0020
0021 /* other API */
0022
0023 typedef struct {
0024     /* Cached hash code of me_key. */
0025     Py_hash_t me_hash;
0026     PyObject *me_key;
0027     PyObject *me_value; /* This field is only meaningful for combined tables */
0028 } PyDictKeyEntry;
0029
0030 typedef struct {
0031     PyObject *me_key;   /* The key must be Unicode and have hash. */
0032     PyObject *me_value; /* This field is only meaningful for combined tables */
0033 } PyDictUnicodeEntry;
0034
0035 extern PyDictKeysObject *_PyDict_NewKeysForClass(void);
0036 extern PyObject *_PyDict_FromKeys(PyObject *, PyObject *, PyObject *);
0037
0038 /* Gets a version number unique to the current state of the keys of dict, if possible.
0039  * Returns the version number, or zero if it was not possible to get a version number. */
0040 extern uint32_t _PyDictKeys_GetVersionForCurrentState(
0041         PyInterpreterState *interp, PyDictKeysObject *dictkeys);
0042
0043 extern size_t _PyDict_KeysSize(PyDictKeysObject *keys);
0044
0045 /* _Py_dict_lookup() returns index of entry which can be used like DK_ENTRIES(dk)[index].
0046  * -1 when no entry found, -3 when compare raises error.
0047  */
0048 extern Py_ssize_t _Py_dict_lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
0049
0050 extern Py_ssize_t _PyDict_LookupIndex(PyDictObject *, PyObject *);
0051 extern Py_ssize_t _PyDictKeys_StringLookup(PyDictKeysObject* dictkeys, PyObject *key);
0052 extern PyObject *_PyDict_LoadGlobal(PyDictObject *, PyDictObject *, PyObject *);
0053
0054 /* Consumes references to key and value */
0055 extern int _PyDict_SetItem_Take2(PyDictObject *op, PyObject *key, PyObject *value);
0056 extern int _PyObjectDict_SetItem(PyTypeObject *tp, PyObject **dictptr, PyObject *name, PyObject *value);
0057
0058 extern PyObject *_PyDict_Pop_KnownHash(PyObject *, PyObject *, Py_hash_t, PyObject *);
0059
0060 #define DKIX_EMPTY (-1)
0061 #define DKIX_DUMMY (-2)  /* Used internally */
0062 #define DKIX_ERROR (-3)
0063 #define DKIX_KEY_CHANGED (-4) /* Used internally */
0064
0065 typedef enum {
0066     DICT_KEYS_GENERAL = 0,
0067     DICT_KEYS_UNICODE = 1,
0068     DICT_KEYS_SPLIT = 2
0069 } DictKeysKind;
0070
0071 /* See dictobject.c for actual layout of DictKeysObject */
0072 struct _dictkeysobject {
0073     Py_ssize_t dk_refcnt;
0074
0075     /* Size of the hash table (dk_indices). It must be a power of 2. */
0076     uint8_t dk_log2_size;
0077
0078     /* Size of the hash table (dk_indices) by bytes. */
0079     uint8_t dk_log2_index_bytes;
0080
0081     /* Kind of keys */
0082     uint8_t dk_kind;
0083
0084     /* Version number -- Reset to 0 by any modification to keys */
0085     uint32_t dk_version;
0086
0087     /* Number of usable entries in dk_entries. */
0088     Py_ssize_t dk_usable;
0089
0090     /* Number of used entries in dk_entries. */
0091     Py_ssize_t dk_nentries;
0092
0093     /* Actual hash table of dk_size entries. It holds indices in dk_entries,
0094        or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
0095
0096        Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
0097
0098        The size in bytes of an indice depends on dk_size:
0099
0100        - 1 byte if dk_size <= 0xff (char*)
0101        - 2 bytes if dk_size <= 0xffff (int16_t*)
0102        - 4 bytes if dk_size <= 0xffffffff (int32_t*)
0103        - 8 bytes otherwise (int64_t*)
0104
0105        Dynamically sized, SIZEOF_VOID_P is minimum. */
0106     char dk_indices[];  /* char is required to avoid strict aliasing. */
0107
0108     /* "PyDictKeyEntry or PyDictUnicodeEntry dk_entries[USABLE_FRACTION(DK_SIZE(dk))];" array follows:
0109        see the DK_ENTRIES() macro */
0110 };
0111
0112 /* This must be no more than 250, for the prefix size to fit in one byte. */
0113 #define SHARED_KEYS_MAX_SIZE 30
0114 #define NEXT_LOG2_SHARED_KEYS_MAX_SIZE 6
0115
0116 /* Layout of dict values:
0117  *
0118  * The PyObject *values are preceded by an array of bytes holding
0119  * the insertion order and size.
0120  * [-1] = prefix size. [-2] = used size. size[-2-n...] = insertion order.
0121  */
0122 struct _dictvalues {
0123     PyObject *values[1];
0124 };
0125
0126 #define DK_LOG_SIZE(dk)  _Py_RVALUE((dk)->dk_log2_size)
0127 #if SIZEOF_VOID_P > 4
0128 #define DK_SIZE(dk)      (((int64_t)1)<<DK_LOG_SIZE(dk))
0129 #else
0130 #define DK_SIZE(dk)      (1<<DK_LOG_SIZE(dk))
0131 #endif
0132
0133 static inline void* _DK_ENTRIES(PyDictKeysObject *dk) {
0134     int8_t *indices = (int8_t*)(dk->dk_indices);
0135     size_t index = (size_t)1 << dk->dk_log2_index_bytes;
0136     return (&indices[index]);
0137 }
0138 static inline PyDictKeyEntry* DK_ENTRIES(PyDictKeysObject *dk) {
0139     assert(dk->dk_kind == DICT_KEYS_GENERAL);
0140     return (PyDictKeyEntry*)_DK_ENTRIES(dk);
0141 }
0142 static inline PyDictUnicodeEntry* DK_UNICODE_ENTRIES(PyDictKeysObject *dk) {
0143     assert(dk->dk_kind != DICT_KEYS_GENERAL);
0144     return (PyDictUnicodeEntry*)_DK_ENTRIES(dk);
0145 }
0146
0147 #define DK_IS_UNICODE(dk) ((dk)->dk_kind != DICT_KEYS_GENERAL)
0148
0149 #define DICT_VERSION_INCREMENT (1 << DICT_MAX_WATCHERS)
0150 #define DICT_VERSION_MASK (DICT_VERSION_INCREMENT - 1)
0151
0152 #define DICT_NEXT_VERSION(INTERP) \
0153     ((INTERP)->dict_state.global_version += DICT_VERSION_INCREMENT)
0154
0155 void
0156 _PyDict_SendEvent(int watcher_bits,
0157                   PyDict_WatchEvent event,
0158                   PyDictObject *mp,
0159                   PyObject *key,
0160                   PyObject *value);
0161
0162 static inline uint64_t
0163 _PyDict_NotifyEvent(PyInterpreterState *interp,
0164                     PyDict_WatchEvent event,
0165                     PyDictObject *mp,
0166                     PyObject *key,
0167                     PyObject *value)
0168 {
0169     assert(Py_REFCNT((PyObject*)mp) > 0);
0170     int watcher_bits = mp->ma_version_tag & DICT_VERSION_MASK;
0171     if (watcher_bits) {
0172         _PyDict_SendEvent(watcher_bits, event, mp, key, value);
0173         return DICT_NEXT_VERSION(interp) | watcher_bits;
0174     }
0175     return DICT_NEXT_VERSION(interp);
0176 }
0177
0178 extern PyObject *_PyObject_MakeDictFromInstanceAttributes(PyObject *obj, PyDictValues *values);
0179 extern PyObject *_PyDict_FromItems(
0180         PyObject *const *keys, Py_ssize_t keys_offset,
0181         PyObject *const *values, Py_ssize_t values_offset,
0182         Py_ssize_t length);
0183
0184 static inline void
0185 _PyDictValues_AddToInsertionOrder(PyDictValues *values, Py_ssize_t ix)
0186 {
0187     assert(ix < SHARED_KEYS_MAX_SIZE);
0188     uint8_t *size_ptr = ((uint8_t *)values)-2;
0189     int size = *size_ptr;
0190     assert(size+2 < ((uint8_t *)values)[-1]);
0191     size++;
0192     size_ptr[-size] = (uint8_t)ix;
0193     *size_ptr = size;
0194 }
0195
0196 #ifdef __cplusplus
0197 }
0198 #endif
0199 #endif   /* !Py_INTERNAL_DICT_H */