1
2 #ifndef Py_INTERNAL_DICT_H
3 #define Py_INTERNAL_DICT_H
4 #ifdef __cplusplus
5 extern "C" {
6 #endif
7
8 #ifndef Py_BUILD_CORE
9 # error "this header requires Py_BUILD_CORE define"
10 #endif
11
12
13 /* runtime lifecycle */
14
15 extern void _PyDict_Fini(PyInterpreterState *interp);
16
17
18 /* other API */
19
20 #ifndef WITH_FREELISTS
21 // without freelists
22 # define PyDict_MAXFREELIST 0
23 #endif
24
25 #ifndef PyDict_MAXFREELIST
26 # define PyDict_MAXFREELIST 80
27 #endif
28
29 struct _Py_dict_state {
30 #if PyDict_MAXFREELIST > 0
31 /* Dictionary reuse scheme to save calls to malloc and free */
32 PyDictObject *free_list[PyDict_MAXFREELIST];
33 int numfree;
34 PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST];
35 int keys_numfree;
36 #endif
37 };
38
39 typedef struct {
40 /* Cached hash code of me_key. */
41 Py_hash_t me_hash;
42 PyObject *me_key;
43 PyObject *me_value; /* This field is only meaningful for combined tables */
44 } PyDictKeyEntry;
45
46 typedef struct {
47 PyObject *me_key; /* The key must be Unicode and have hash. */
48 PyObject *me_value; /* This field is only meaningful for combined tables */
49 } PyDictUnicodeEntry;
50
51 extern PyDictKeysObject *_PyDict_NewKeysForClass(void);
52 extern PyObject *_PyDict_FromKeys(PyObject *, PyObject *, PyObject *);
53
54 /* Gets a version number unique to the current state of the keys of dict, if possible.
55 * Returns the version number, or zero if it was not possible to get a version number. */
56 extern uint32_t _PyDictKeys_GetVersionForCurrentState(PyDictKeysObject *dictkeys);
57
58 extern Py_ssize_t _PyDict_KeysSize(PyDictKeysObject *keys);
59
60 /* _Py_dict_lookup() returns index of entry which can be used like DK_ENTRIES(dk)[index].
61 * -1 when no entry found, -3 when compare raises error.
62 */
63 extern Py_ssize_t _Py_dict_lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
64
65 extern Py_ssize_t _PyDict_GetItemHint(PyDictObject *, PyObject *, Py_ssize_t, PyObject **);
66 extern Py_ssize_t _PyDictKeys_StringLookup(PyDictKeysObject* dictkeys, PyObject *key);
67 extern PyObject *_PyDict_LoadGlobal(PyDictObject *, PyDictObject *, PyObject *);
68
69 /* Consumes references to key and value */
70 extern int _PyDict_SetItem_Take2(PyDictObject *op, PyObject *key, PyObject *value);
71 extern int _PyObjectDict_SetItem(PyTypeObject *tp, PyObject **dictptr, PyObject *name, PyObject *value);
72
73 extern PyObject *_PyDict_Pop_KnownHash(PyObject *, PyObject *, Py_hash_t, PyObject *);
74
75 #define DKIX_EMPTY (-1)
76 #define DKIX_DUMMY (-2) /* Used internally */
77 #define DKIX_ERROR (-3)
78 #define DKIX_KEY_CHANGED (-4) /* Used internally */
79
80 typedef enum {
81 DICT_KEYS_GENERAL = 0,
82 DICT_KEYS_UNICODE = 1,
83 DICT_KEYS_SPLIT = 2
84 } DictKeysKind;
85
86 /* See dictobject.c for actual layout of DictKeysObject */
87 struct _dictkeysobject {
88 Py_ssize_t dk_refcnt;
89
90 /* Size of the hash table (dk_indices). It must be a power of 2. */
91 uint8_t dk_log2_size;
92
93 /* Size of the hash table (dk_indices) by bytes. */
94 uint8_t dk_log2_index_bytes;
95
96 /* Kind of keys */
97 uint8_t dk_kind;
98
99 /* Version number -- Reset to 0 by any modification to keys */
100 uint32_t dk_version;
101
102 /* Number of usable entries in dk_entries. */
103 Py_ssize_t dk_usable;
104
105 /* Number of used entries in dk_entries. */
106 Py_ssize_t dk_nentries;
107
108 /* Actual hash table of dk_size entries. It holds indices in dk_entries,
109 or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
110
111 Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
112
113 The size in bytes of an indice depends on dk_size:
114
115 - 1 byte if dk_size <= 0xff (char*)
116 - 2 bytes if dk_size <= 0xffff (int16_t*)
117 - 4 bytes if dk_size <= 0xffffffff (int32_t*)
118 - 8 bytes otherwise (int64_t*)
119
120 Dynamically sized, SIZEOF_VOID_P is minimum. */
121 char dk_indices[]; /* char is required to avoid strict aliasing. */
122
123 /* "PyDictKeyEntry or PyDictUnicodeEntry dk_entries[USABLE_FRACTION(DK_SIZE(dk))];" array follows:
124 see the DK_ENTRIES() macro */
125 };
126
127 /* This must be no more than 250, for the prefix size to fit in one byte. */
128 #define SHARED_KEYS_MAX_SIZE 30
129 #define NEXT_LOG2_SHARED_KEYS_MAX_SIZE 6
130
131 /* Layout of dict values:
132 *
133 * The PyObject *values are preceded by an array of bytes holding
134 * the insertion order and size.
135 * [-1] = prefix size. [-2] = used size. size[-2-n...] = insertion order.
136 */
137 struct _dictvalues {
138 PyObject *values[1];
139 };
140
141 #define DK_LOG_SIZE(dk) ((dk)->dk_log2_size)
142 #if SIZEOF_VOID_P > 4
143 #define DK_SIZE(dk) (((int64_t)1)<<DK_LOG_SIZE(dk))
144 #else
145 #define DK_SIZE(dk) (1<<DK_LOG_SIZE(dk))
146 #endif
147 #define DK_ENTRIES(dk) \
148 (assert(dk->dk_kind == DICT_KEYS_GENERAL), (PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[(size_t)1 << (dk)->dk_log2_index_bytes]))
149 #define DK_UNICODE_ENTRIES(dk) \
150 (assert(dk->dk_kind != DICT_KEYS_GENERAL), (PyDictUnicodeEntry*)(&((int8_t*)((dk)->dk_indices))[(size_t)1 << (dk)->dk_log2_index_bytes]))
151 #define DK_IS_UNICODE(dk) ((dk)->dk_kind != DICT_KEYS_GENERAL)
152
153 extern uint64_t _pydict_global_version;
154
155 #define DICT_NEXT_VERSION() (++_pydict_global_version)
156
157 extern PyObject *_PyObject_MakeDictFromInstanceAttributes(PyObject *obj, PyDictValues *values);
158 extern PyObject *_PyDict_FromItems(
159 PyObject *const *keys, Py_ssize_t keys_offset,
160 PyObject *const *values, Py_ssize_t values_offset,
161 Py_ssize_t length);
162
163 static inline void
_PyDictValues_AddToInsertionOrder(PyDictValues * values,Py_ssize_t ix)164 _PyDictValues_AddToInsertionOrder(PyDictValues *values, Py_ssize_t ix)
165 {
166 assert(ix < SHARED_KEYS_MAX_SIZE);
167 uint8_t *size_ptr = ((uint8_t *)values)-2;
168 int size = *size_ptr;
169 assert(size+2 < ((uint8_t *)values)[-1]);
170 size++;
171 size_ptr[-size] = (uint8_t)ix;
172 *size_ptr = size;
173 }
174
175 #ifdef __cplusplus
176 }
177 #endif
178 #endif /* !Py_INTERNAL_DICT_H */
179