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