|
1 #ifndef Py_DICTOBJECT_H |
|
2 #define Py_DICTOBJECT_H |
|
3 #ifdef __cplusplus |
|
4 extern "C" { |
|
5 #endif |
|
6 |
|
7 |
|
8 /* Dictionary object type -- mapping from hashable object to object */ |
|
9 |
|
10 /* The distribution includes a separate file, Objects/dictnotes.txt, |
|
11 describing explorations into dictionary design and optimization. |
|
12 It covers typical dictionary use patterns, the parameters for |
|
13 tuning dictionaries, and several ideas for possible optimizations. |
|
14 */ |
|
15 |
|
16 /* |
|
17 There are three kinds of slots in the table: |
|
18 |
|
19 1. Unused. me_key == me_value == NULL |
|
20 Does not hold an active (key, value) pair now and never did. Unused can |
|
21 transition to Active upon key insertion. This is the only case in which |
|
22 me_key is NULL, and is each slot's initial state. |
|
23 |
|
24 2. Active. me_key != NULL and me_key != dummy and me_value != NULL |
|
25 Holds an active (key, value) pair. Active can transition to Dummy upon |
|
26 key deletion. This is the only case in which me_value != NULL. |
|
27 |
|
28 3. Dummy. me_key == dummy and me_value == NULL |
|
29 Previously held an active (key, value) pair, but that was deleted and an |
|
30 active pair has not yet overwritten the slot. Dummy can transition to |
|
31 Active upon key insertion. Dummy slots cannot be made Unused again |
|
32 (cannot have me_key set to NULL), else the probe sequence in case of |
|
33 collision would have no way to know they were once active. |
|
34 |
|
35 Note: .popitem() abuses the me_hash field of an Unused or Dummy slot to |
|
36 hold a search finger. The me_hash field of Unused or Dummy slots has no |
|
37 meaning otherwise. |
|
38 */ |
|
39 |
|
40 /* PyDict_MINSIZE is the minimum size of a dictionary. This many slots are |
|
41 * allocated directly in the dict object (in the ma_smalltable member). |
|
42 * It must be a power of 2, and at least 4. 8 allows dicts with no more |
|
43 * than 5 active entries to live in ma_smalltable (and so avoid an |
|
44 * additional malloc); instrumentation suggested this suffices for the |
|
45 * majority of dicts (consisting mostly of usually-small instance dicts and |
|
46 * usually-small dicts created to pass keyword arguments). |
|
47 */ |
|
48 #define PyDict_MINSIZE 8 |
|
49 |
|
50 typedef struct { |
|
51 /* Cached hash code of me_key. Note that hash codes are C longs. |
|
52 * We have to use Py_ssize_t instead because dict_popitem() abuses |
|
53 * me_hash to hold a search finger. |
|
54 */ |
|
55 Py_ssize_t me_hash; |
|
56 PyObject *me_key; |
|
57 PyObject *me_value; |
|
58 } PyDictEntry; |
|
59 |
|
60 /* |
|
61 To ensure the lookup algorithm terminates, there must be at least one Unused |
|
62 slot (NULL key) in the table. |
|
63 The value ma_fill is the number of non-NULL keys (sum of Active and Dummy); |
|
64 ma_used is the number of non-NULL, non-dummy keys (== the number of non-NULL |
|
65 values == the number of Active items). |
|
66 To avoid slowing down lookups on a near-full table, we resize the table when |
|
67 it's two-thirds full. |
|
68 */ |
|
69 typedef struct _dictobject PyDictObject; |
|
70 struct _dictobject { |
|
71 PyObject_HEAD |
|
72 Py_ssize_t ma_fill; /* # Active + # Dummy */ |
|
73 Py_ssize_t ma_used; /* # Active */ |
|
74 |
|
75 /* The table contains ma_mask + 1 slots, and that's a power of 2. |
|
76 * We store the mask instead of the size because the mask is more |
|
77 * frequently needed. |
|
78 */ |
|
79 Py_ssize_t ma_mask; |
|
80 |
|
81 /* ma_table points to ma_smalltable for small tables, else to |
|
82 * additional malloc'ed memory. ma_table is never NULL! This rule |
|
83 * saves repeated runtime null-tests in the workhorse getitem and |
|
84 * setitem calls. |
|
85 */ |
|
86 PyDictEntry *ma_table; |
|
87 PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash); |
|
88 PyDictEntry ma_smalltable[PyDict_MINSIZE]; |
|
89 }; |
|
90 |
|
91 PyAPI_DATA(PyTypeObject) PyDict_Type; |
|
92 |
|
93 #define PyDict_Check(op) \ |
|
94 PyType_FastSubclass(Py_TYPE(op), Py_TPFLAGS_DICT_SUBCLASS) |
|
95 #define PyDict_CheckExact(op) (Py_TYPE(op) == &PyDict_Type) |
|
96 |
|
97 PyAPI_FUNC(PyObject *) PyDict_New(void); |
|
98 PyAPI_FUNC(PyObject *) PyDict_GetItem(PyObject *mp, PyObject *key); |
|
99 PyAPI_FUNC(int) PyDict_SetItem(PyObject *mp, PyObject *key, PyObject *item); |
|
100 PyAPI_FUNC(int) PyDict_DelItem(PyObject *mp, PyObject *key); |
|
101 PyAPI_FUNC(void) PyDict_Clear(PyObject *mp); |
|
102 PyAPI_FUNC(int) PyDict_Next( |
|
103 PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value); |
|
104 PyAPI_FUNC(int) _PyDict_Next( |
|
105 PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value, long *hash); |
|
106 PyAPI_FUNC(PyObject *) PyDict_Keys(PyObject *mp); |
|
107 PyAPI_FUNC(PyObject *) PyDict_Values(PyObject *mp); |
|
108 PyAPI_FUNC(PyObject *) PyDict_Items(PyObject *mp); |
|
109 PyAPI_FUNC(Py_ssize_t) PyDict_Size(PyObject *mp); |
|
110 PyAPI_FUNC(PyObject *) PyDict_Copy(PyObject *mp); |
|
111 PyAPI_FUNC(int) PyDict_Contains(PyObject *mp, PyObject *key); |
|
112 PyAPI_FUNC(int) _PyDict_Contains(PyObject *mp, PyObject *key, long hash); |
|
113 PyAPI_FUNC(PyObject *) _PyDict_NewPresized(Py_ssize_t minused); |
|
114 |
|
115 /* PyDict_Update(mp, other) is equivalent to PyDict_Merge(mp, other, 1). */ |
|
116 PyAPI_FUNC(int) PyDict_Update(PyObject *mp, PyObject *other); |
|
117 |
|
118 /* PyDict_Merge updates/merges from a mapping object (an object that |
|
119 supports PyMapping_Keys() and PyObject_GetItem()). If override is true, |
|
120 the last occurrence of a key wins, else the first. The Python |
|
121 dict.update(other) is equivalent to PyDict_Merge(dict, other, 1). |
|
122 */ |
|
123 PyAPI_FUNC(int) PyDict_Merge(PyObject *mp, |
|
124 PyObject *other, |
|
125 int override); |
|
126 |
|
127 /* PyDict_MergeFromSeq2 updates/merges from an iterable object producing |
|
128 iterable objects of length 2. If override is true, the last occurrence |
|
129 of a key wins, else the first. The Python dict constructor dict(seq2) |
|
130 is equivalent to dict={}; PyDict_MergeFromSeq(dict, seq2, 1). |
|
131 */ |
|
132 PyAPI_FUNC(int) PyDict_MergeFromSeq2(PyObject *d, |
|
133 PyObject *seq2, |
|
134 int override); |
|
135 |
|
136 PyAPI_FUNC(PyObject *) PyDict_GetItemString(PyObject *dp, const char *key); |
|
137 PyAPI_FUNC(int) PyDict_SetItemString(PyObject *dp, const char *key, PyObject *item); |
|
138 PyAPI_FUNC(int) PyDict_DelItemString(PyObject *dp, const char *key); |
|
139 |
|
140 #ifdef __cplusplus |
|
141 } |
|
142 #endif |
|
143 #endif /* !Py_DICTOBJECT_H */ |