Repository navigation
Expand file tree
/
Copy pathpycore_dict.h
More file actions
328 lines (261 loc) · 11.3 KB
/
Copy pathpycore_dict.h
File metadata and controls
328 lines (261 loc) · 11.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
#ifndef Py_INTERNAL_DICT_H
#define Py_INTERNAL_DICT_H
#ifdef __cplusplus
extern "C" {
#endif
#ifndef Py_BUILD_CORE
# error "this header requires Py_BUILD_CORE define"
#endif
#include "pycore_freelist.h" // _PyFreeListState
#include "pycore_object.h" // PyManagedDictPointer
#include "pycore_pyatomic_ft_wrappers.h" // FT_ATOMIC_LOAD_SSIZE_ACQUIRE
// Unsafe flavor of PyDict_GetItemWithError(): no error checking
extern PyObject* _PyDict_GetItemWithError(PyObject *dp, PyObject *key);
extern int _PyDict_DelItemIf(PyObject *mp, PyObject *key,
int (*predicate)(PyObject *value));
// "KnownHash" variants
// Export for '_asyncio' shared extension
PyAPI_FUNC(int) _PyDict_SetItem_KnownHash(PyObject *mp, PyObject *key,
PyObject *item, Py_hash_t hash);
// Export for '_asyncio' shared extension
PyAPI_FUNC(int) _PyDict_DelItem_KnownHash(PyObject *mp, PyObject *key,
Py_hash_t hash);
extern int _PyDict_Contains_KnownHash(PyObject *, PyObject *, Py_hash_t);
// "Id" variants
extern PyObject* _PyDict_GetItemIdWithError(PyObject *dp,
_Py_Identifier *key);
extern int _PyDict_ContainsId(PyObject *, _Py_Identifier *);
extern int _PyDict_SetItemId(PyObject *dp, _Py_Identifier *key, PyObject *item);
extern int _PyDict_DelItemId(PyObject *mp, _Py_Identifier *key);
extern int _PyDict_Next(
PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value, Py_hash_t *hash);
extern int _PyDict_HasOnlyStringKeys(PyObject *mp);
extern void _PyDict_MaybeUntrack(PyObject *mp);
// Export for '_ctypes' shared extension
PyAPI_FUNC(Py_ssize_t) _PyDict_SizeOf(PyDictObject *);
#define _PyDict_HasSplitTable(d) ((d)->ma_values != NULL)
/* Like PyDict_Merge, but override can be 0, 1 or 2. If override is 0,
the first occurrence of a key wins, if override is 1, the last occurrence
of a key wins, if override is 2, a KeyError with conflicting key as
argument is raised.
*/
PyAPI_FUNC(int) _PyDict_MergeEx(PyObject *mp, PyObject *other, int override);
extern void _PyDict_DebugMallocStats(FILE *out);
/* _PyDictView */
typedef struct {
PyObject_HEAD
PyDictObject *dv_dict;
} _PyDictViewObject;
extern PyObject* _PyDictView_New(PyObject *, PyTypeObject *);
extern PyObject* _PyDictView_Intersect(PyObject* self, PyObject *other);
/* other API */
typedef struct {
/* Cached hash code of me_key. */
Py_hash_t me_hash;
PyObject *me_key;
PyObject *me_value; /* This field is only meaningful for combined tables */
} PyDictKeyEntry;
typedef struct {
PyObject *me_key; /* The key must be Unicode and have hash. */
PyObject *me_value; /* This field is only meaningful for combined tables */
} PyDictUnicodeEntry;
extern PyDictKeysObject *_PyDict_NewKeysForClass(void);
extern PyObject *_PyDict_FromKeys(PyObject *, PyObject *, PyObject *);
/* Gets a version number unique to the current state of the keys of dict, if possible.
* Returns the version number, or zero if it was not possible to get a version number. */
extern uint32_t _PyDictKeys_GetVersionForCurrentState(
PyInterpreterState *interp, PyDictKeysObject *dictkeys);
extern size_t _PyDict_KeysSize(PyDictKeysObject *keys);
extern void _PyDictKeys_DecRef(PyDictKeysObject *keys);
/* _Py_dict_lookup() returns index of entry which can be used like DK_ENTRIES(dk)[index].
* -1 when no entry found, -3 when compare raises error.
*/
extern Py_ssize_t _Py_dict_lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
extern Py_ssize_t _Py_dict_lookup_threadsafe(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
extern Py_ssize_t _PyDict_LookupIndex(PyDictObject *, PyObject *);
extern Py_ssize_t _PyDictKeys_StringLookup(PyDictKeysObject* dictkeys, PyObject *key);
PyAPI_FUNC(PyObject *)_PyDict_LoadGlobal(PyDictObject *, PyDictObject *, PyObject *);
/* Consumes references to key and value */
PyAPI_FUNC(int) _PyDict_SetItem_Take2(PyDictObject *op, PyObject *key, PyObject *value);
extern int _PyDict_SetItem_LockHeld(PyDictObject *dict, PyObject *name, PyObject *value);
extern int _PyDict_GetItemRef_Unicode_LockHeld(PyDictObject *op, PyObject *key, PyObject **result);
extern int _PyDict_GetItemRef_KnownHash(PyDictObject *op, PyObject *key, Py_hash_t hash, PyObject **result);
extern int _PyObjectDict_SetItem(PyTypeObject *tp, PyObject *obj, PyObject **dictptr, PyObject *name, PyObject *value);
extern int _PyDict_Pop_KnownHash(
PyDictObject *dict,
PyObject *key,
Py_hash_t hash,
PyObject **result);
#define DKIX_EMPTY (-1)
#define DKIX_DUMMY (-2) /* Used internally */
#define DKIX_ERROR (-3)
#define DKIX_KEY_CHANGED (-4) /* Used internally */
typedef enum {
DICT_KEYS_GENERAL = 0,
DICT_KEYS_UNICODE = 1,
DICT_KEYS_SPLIT = 2
} DictKeysKind;
/* See dictobject.c for actual layout of DictKeysObject */
struct _dictkeysobject {
Py_ssize_t dk_refcnt;
/* Size of the hash table (dk_indices). It must be a power of 2. */
uint8_t dk_log2_size;
/* Size of the hash table (dk_indices) by bytes. */
uint8_t dk_log2_index_bytes;
/* Kind of keys */
uint8_t dk_kind;
#ifdef Py_GIL_DISABLED
/* Lock used to protect shared keys */
PyMutex dk_mutex;
#endif
/* Version number -- Reset to 0 by any modification to keys */
uint32_t dk_version;
/* Number of usable entries in dk_entries. */
Py_ssize_t dk_usable;
/* Number of used entries in dk_entries. */
Py_ssize_t dk_nentries;
/* Actual hash table of dk_size entries. It holds indices in dk_entries,
or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
The size in bytes of an indice depends on dk_size:
- 1 byte if dk_size <= 0xff (char*)
- 2 bytes if dk_size <= 0xffff (int16_t*)
- 4 bytes if dk_size <= 0xffffffff (int32_t*)
- 8 bytes otherwise (int64_t*)
Dynamically sized, SIZEOF_VOID_P is minimum. */
char dk_indices[]; /* char is required to avoid strict aliasing. */
/* "PyDictKeyEntry or PyDictUnicodeEntry dk_entries[USABLE_FRACTION(DK_SIZE(dk))];" array follows:
see the DK_ENTRIES() / DK_UNICODE_ENTRIES() functions below */
};
/* This must be no more than 250, for the prefix size to fit in one byte. */
#define SHARED_KEYS_MAX_SIZE 30
#define NEXT_LOG2_SHARED_KEYS_MAX_SIZE 6
/* Layout of dict values:
*
* The PyObject *values are preceded by an array of bytes holding
* the insertion order and size.
* [-1] = prefix size. [-2] = used size. size[-2-n...] = insertion order.
*/
struct _dictvalues {
uint8_t capacity;
uint8_t size;
uint8_t embedded;
uint8_t valid;
PyObject *values[1];
};
#define DK_LOG_SIZE(dk) _Py_RVALUE((dk)->dk_log2_size)
#if SIZEOF_VOID_P > 4
#define DK_SIZE(dk) (((int64_t)1)<<DK_LOG_SIZE(dk))
#else
#define DK_SIZE(dk) (1<<DK_LOG_SIZE(dk))
#endif
static inline void* _DK_ENTRIES(PyDictKeysObject *dk) {
int8_t *indices = (int8_t*)(dk->dk_indices);
size_t index = (size_t)1 << dk->dk_log2_index_bytes;
return (&indices[index]);
}
static inline PyDictKeyEntry* DK_ENTRIES(PyDictKeysObject *dk) {
assert(dk->dk_kind == DICT_KEYS_GENERAL);
return (PyDictKeyEntry*)_DK_ENTRIES(dk);
}
static inline PyDictUnicodeEntry* DK_UNICODE_ENTRIES(PyDictKeysObject *dk) {
assert(dk->dk_kind != DICT_KEYS_GENERAL);
return (PyDictUnicodeEntry*)_DK_ENTRIES(dk);
}
#define DK_IS_UNICODE(dk) ((dk)->dk_kind != DICT_KEYS_GENERAL)
#define DICT_VERSION_INCREMENT (1 << (DICT_MAX_WATCHERS + DICT_WATCHED_MUTATION_BITS))
#define DICT_WATCHER_MASK ((1 << DICT_MAX_WATCHERS) - 1)
#define DICT_WATCHER_AND_MODIFICATION_MASK ((1 << (DICT_MAX_WATCHERS + DICT_WATCHED_MUTATION_BITS)) - 1)
#ifdef Py_GIL_DISABLED
#define THREAD_LOCAL_DICT_VERSION_COUNT 256
#define THREAD_LOCAL_DICT_VERSION_BATCH THREAD_LOCAL_DICT_VERSION_COUNT * DICT_VERSION_INCREMENT
static inline uint64_t
dict_next_version(PyInterpreterState *interp)
{
PyThreadState *tstate = PyThreadState_GET();
uint64_t cur_progress = (tstate->dict_global_version &
(THREAD_LOCAL_DICT_VERSION_BATCH - 1));
if (cur_progress == 0) {
uint64_t next = _Py_atomic_add_uint64(&interp->dict_state.global_version,
THREAD_LOCAL_DICT_VERSION_BATCH);
tstate->dict_global_version = next;
}
return tstate->dict_global_version += DICT_VERSION_INCREMENT;
}
#define DICT_NEXT_VERSION(INTERP) dict_next_version(INTERP)
#else
#define DICT_NEXT_VERSION(INTERP) \
((INTERP)->dict_state.global_version += DICT_VERSION_INCREMENT)
#endif
PyAPI_FUNC(void)
_PyDict_SendEvent(int watcher_bits,
PyDict_WatchEvent event,
PyDictObject *mp,
PyObject *key,
PyObject *value);
static inline uint64_t
_PyDict_NotifyEvent(PyInterpreterState *interp,
PyDict_WatchEvent event,
PyDictObject *mp,
PyObject *key,
PyObject *value)
{
assert(Py_REFCNT((PyObject*)mp) > 0);
int watcher_bits = mp->ma_version_tag & DICT_WATCHER_MASK;
if (watcher_bits) {
RARE_EVENT_STAT_INC(watched_dict_modification);
_PyDict_SendEvent(watcher_bits, event, mp, key, value);
}
return DICT_NEXT_VERSION(interp) | (mp->ma_version_tag & DICT_WATCHER_AND_MODIFICATION_MASK);
}
extern PyDictObject *_PyObject_MaterializeManagedDict(PyObject *obj);
PyAPI_FUNC(PyObject *)_PyDict_FromItems(
PyObject *const *keys, Py_ssize_t keys_offset,
PyObject *const *values, Py_ssize_t values_offset,
Py_ssize_t length);
static inline uint8_t *
get_insertion_order_array(PyDictValues *values)
{
return (uint8_t *)&values->values[values->capacity];
}
static inline void
_PyDictValues_AddToInsertionOrder(PyDictValues *values, Py_ssize_t ix)
{
assert(ix < SHARED_KEYS_MAX_SIZE);
int size = values->size;
uint8_t *array = get_insertion_order_array(values);
assert(size < values->capacity);
assert(((uint8_t)ix) == ix);
array[size] = (uint8_t)ix;
values->size = size+1;
}
static inline size_t
shared_keys_usable_size(PyDictKeysObject *keys)
{
// dk_usable will decrease for each instance that is created and each
// value that is added. dk_nentries will increase for each value that
// is added. We want to always return the right value or larger.
// We therefore increase dk_nentries first and we decrease dk_usable
// second, and conversely here we read dk_usable first and dk_entries
// second (to avoid the case where we read entries before the increment
// and read usable after the decrement)
Py_ssize_t dk_usable = FT_ATOMIC_LOAD_SSIZE_ACQUIRE(keys->dk_usable);
Py_ssize_t dk_nentries = FT_ATOMIC_LOAD_SSIZE_ACQUIRE(keys->dk_nentries);
return dk_nentries + dk_usable;
}
static inline size_t
_PyInlineValuesSize(PyTypeObject *tp)
{
PyDictKeysObject *keys = ((PyHeapTypeObject*)tp)->ht_cached_keys;
assert(keys != NULL);
size_t size = shared_keys_usable_size(keys);
size_t prefix_size = _Py_SIZE_ROUND_UP(size, sizeof(PyObject *));
assert(prefix_size < 256);
return prefix_size + (size + 1) * sizeof(PyObject *);
}
int
_PyDict_DetachFromObject(PyDictObject *dict, PyObject *obj);
#ifdef __cplusplus
}
#endif
#endif /* !Py_INTERNAL_DICT_H */