Commit | Line | Data |
---|---|---|
86530b38 AT |
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 | long me_hash; /* cached hash code of me_key */ | |
52 | PyObject *me_key; | |
53 | PyObject *me_value; | |
54 | } PyDictEntry; | |
55 | ||
56 | /* | |
57 | To ensure the lookup algorithm terminates, there must be at least one Unused | |
58 | slot (NULL key) in the table. | |
59 | The value ma_fill is the number of non-NULL keys (sum of Active and Dummy); | |
60 | ma_used is the number of non-NULL, non-dummy keys (== the number of non-NULL | |
61 | values == the number of Active items). | |
62 | To avoid slowing down lookups on a near-full table, we resize the table when | |
63 | it's two-thirds full. | |
64 | */ | |
65 | typedef struct _dictobject PyDictObject; | |
66 | struct _dictobject { | |
67 | PyObject_HEAD | |
68 | int ma_fill; /* # Active + # Dummy */ | |
69 | int ma_used; /* # Active */ | |
70 | ||
71 | /* The table contains ma_mask + 1 slots, and that's a power of 2. | |
72 | * We store the mask instead of the size because the mask is more | |
73 | * frequently needed. | |
74 | */ | |
75 | int ma_mask; | |
76 | ||
77 | /* ma_table points to ma_smalltable for small tables, else to | |
78 | * additional malloc'ed memory. ma_table is never NULL! This rule | |
79 | * saves repeated runtime null-tests in the workhorse getitem and | |
80 | * setitem calls. | |
81 | */ | |
82 | PyDictEntry *ma_table; | |
83 | PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash); | |
84 | PyDictEntry ma_smalltable[PyDict_MINSIZE]; | |
85 | }; | |
86 | ||
87 | PyAPI_DATA(PyTypeObject) PyDict_Type; | |
88 | ||
89 | #define PyDict_Check(op) PyObject_TypeCheck(op, &PyDict_Type) | |
90 | #define PyDict_CheckExact(op) ((op)->ob_type == &PyDict_Type) | |
91 | ||
92 | PyAPI_FUNC(PyObject *) PyDict_New(void); | |
93 | PyAPI_FUNC(PyObject *) PyDict_GetItem(PyObject *mp, PyObject *key); | |
94 | PyAPI_FUNC(int) PyDict_SetItem(PyObject *mp, PyObject *key, PyObject *item); | |
95 | PyAPI_FUNC(int) PyDict_DelItem(PyObject *mp, PyObject *key); | |
96 | PyAPI_FUNC(void) PyDict_Clear(PyObject *mp); | |
97 | PyAPI_FUNC(int) PyDict_Next( | |
98 | PyObject *mp, int *pos, PyObject **key, PyObject **value); | |
99 | PyAPI_FUNC(PyObject *) PyDict_Keys(PyObject *mp); | |
100 | PyAPI_FUNC(PyObject *) PyDict_Values(PyObject *mp); | |
101 | PyAPI_FUNC(PyObject *) PyDict_Items(PyObject *mp); | |
102 | PyAPI_FUNC(int) PyDict_Size(PyObject *mp); | |
103 | PyAPI_FUNC(PyObject *) PyDict_Copy(PyObject *mp); | |
104 | PyAPI_FUNC(int) PyDict_Contains(PyObject *mp, PyObject *key); | |
105 | ||
106 | /* PyDict_Update(mp, other) is equivalent to PyDict_Merge(mp, other, 1). */ | |
107 | PyAPI_FUNC(int) PyDict_Update(PyObject *mp, PyObject *other); | |
108 | ||
109 | /* PyDict_Merge updates/merges from a mapping object (an object that | |
110 | supports PyMapping_Keys() and PyObject_GetItem()). If override is true, | |
111 | the last occurrence of a key wins, else the first. The Python | |
112 | dict.update(other) is equivalent to PyDict_Merge(dict, other, 1). | |
113 | */ | |
114 | PyAPI_FUNC(int) PyDict_Merge(PyObject *mp, | |
115 | PyObject *other, | |
116 | int override); | |
117 | ||
118 | /* PyDict_MergeFromSeq2 updates/merges from an iterable object producing | |
119 | iterable objects of length 2. If override is true, the last occurrence | |
120 | of a key wins, else the first. The Python dict constructor dict(seq2) | |
121 | is equivalent to dict={}; PyDict_MergeFromSeq(dict, seq2, 1). | |
122 | */ | |
123 | PyAPI_FUNC(int) PyDict_MergeFromSeq2(PyObject *d, | |
124 | PyObject *seq2, | |
125 | int override); | |
126 | ||
127 | PyAPI_FUNC(PyObject *) PyDict_GetItemString(PyObject *dp, const char *key); | |
128 | PyAPI_FUNC(int) PyDict_SetItemString(PyObject *dp, const char *key, PyObject *item); | |
129 | PyAPI_FUNC(int) PyDict_DelItemString(PyObject *dp, const char *key); | |
130 | ||
131 | #ifdef __cplusplus | |
132 | } | |
133 | #endif | |
134 | #endif /* !Py_DICTOBJECT_H */ |