| 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 = FT_ATOMIC_LOAD_UINT64_ACQUIRE(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)(FT_ATOMIC_LOAD_UINT64_RELAXED(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 */ |