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
|
#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_dict_state.h"
#include "pycore_object.h"
#include "pycore_runtime.h" // _PyRuntime
// Unsafe flavor of PyDict_GetItemWithError(): no error checking
extern PyObject* _PyDict_GetItemWithError(PyObject *dp, PyObject *key);
extern int _PyDict_Contains_KnownHash(PyObject *, PyObject *, Py_hash_t);
extern int _PyDict_DelItemIf(PyObject *mp, PyObject *key,
int (*predicate)(PyObject *value));
extern int _PyDict_HasOnlyStringKeys(PyObject *mp);
extern void _PyDict_MaybeUntrack(PyObject *mp);
/* 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.
*/
extern int _PyDict_MergeEx(PyObject *mp, PyObject *other, int override);
extern void _PyDict_DebugMallocStats(FILE *out);
/* runtime lifecycle */
extern void _PyDict_Fini(PyInterpreterState *interp);
/* 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 _PyDict_LookupIndex(PyDictObject *, PyObject *);
extern Py_ssize_t _PyDictKeys_StringLookup(PyDictKeysObject* dictkeys, PyObject *key);
extern PyObject *_PyDict_LoadGlobal(PyDictObject *, PyDictObject *, PyObject *);
/* Consumes references to key and value */
extern int _PyDict_SetItem_Take2(PyDictObject *op, PyObject *key, PyObject *value);
extern int _PyObjectDict_SetItem(PyTypeObject *tp, PyObject **dictptr, PyObject *name, PyObject *value);
extern PyObject *_PyDict_Pop_KnownHash(PyObject *, PyObject *, Py_hash_t, PyObject *);
#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;
/* 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() macro */
};
/* 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 {
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)
#define DICT_VERSION_MASK (DICT_VERSION_INCREMENT - 1)
#define DICT_NEXT_VERSION(INTERP) \
((INTERP)->dict_state.global_version += DICT_VERSION_INCREMENT)
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_VERSION_MASK;
if (watcher_bits) {
_PyDict_SendEvent(watcher_bits, event, mp, key, value);
return DICT_NEXT_VERSION(interp) | watcher_bits;
}
return DICT_NEXT_VERSION(interp);
}
extern PyObject *_PyObject_MakeDictFromInstanceAttributes(PyObject *obj, PyDictValues *values);
extern int _PyObject_MakeInstanceAttributesFromDict(PyObject *obj, PyDictOrValues *dorv);
extern 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 void
_PyDictValues_AddToInsertionOrder(PyDictValues *values, Py_ssize_t ix)
{
assert(ix < SHARED_KEYS_MAX_SIZE);
uint8_t *size_ptr = ((uint8_t *)values)-2;
int size = *size_ptr;
assert(size+2 < ((uint8_t *)values)[-1]);
size++;
size_ptr[-size] = (uint8_t)ix;
*size_ptr = size;
}
#ifdef __cplusplus
}
#endif
#endif /* !Py_INTERNAL_DICT_H */
|
