blob: 76fc75b6bbda214b1d629ec53888fd2223b5e3b9 [file] [log] [blame]
Guido van Rossuma3309961993-07-28 09:05:47 +00001#ifndef Py_DICTOBJECT_H
2#define Py_DICTOBJECT_H
3#ifdef __cplusplus
4extern "C" {
5#endif
6
Guido van Rossumf70e43a1991-02-19 12:39:46 +00007
Guido van Rossum2ec90311997-05-13 21:23:32 +00008/* Dictionary object type -- mapping from hashable object to object */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00009
Raymond Hettinger930427b2003-05-03 06:51:59 +000010/* The distribution includes a separate file, Objects/dictnotes.txt,
Thomas Wouters4d70c3d2006-06-08 14:42:34 +000011 describing explorations into dictionary design and optimization.
Raymond Hettinger930427b2003-05-03 06:51:59 +000012 It covers typical dictionary use patterns, the parameters for
13 tuning dictionaries, and several ideas for possible optimizations.
14*/
15
Tim Peters6d6c1a32001-08-02 04:15:00 +000016/*
17There are three kinds of slots in the table:
18
191. 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
242. 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
283. 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
35Note: .popitem() abuses the me_hash field of an Unused or Dummy slot to
36hold a search finger. The me_hash field of Unused or Dummy slots has no
37meaning 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
50typedef struct {
Thomas Wouters4d70c3d2006-06-08 14:42:34 +000051 /* 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;
Tim Peters6d6c1a32001-08-02 04:15:00 +000056 PyObject *me_key;
57 PyObject *me_value;
Tim Peters6d6c1a32001-08-02 04:15:00 +000058} PyDictEntry;
59
60/*
61To ensure the lookup algorithm terminates, there must be at least one Unused
62slot (NULL key) in the table.
63The value ma_fill is the number of non-NULL keys (sum of Active and Dummy);
64ma_used is the number of non-NULL, non-dummy keys (== the number of non-NULL
65values == the number of Active items).
66To avoid slowing down lookups on a near-full table, we resize the table when
67it's two-thirds full.
68*/
69typedef struct _dictobject PyDictObject;
70struct _dictobject {
71 PyObject_HEAD
Thomas Wouters4d70c3d2006-06-08 14:42:34 +000072 Py_ssize_t ma_fill; /* # Active + # Dummy */
73 Py_ssize_t ma_used; /* # Active */
Tim Peters6d6c1a32001-08-02 04:15:00 +000074
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 */
Thomas Wouters4d70c3d2006-06-08 14:42:34 +000079 Py_ssize_t ma_mask;
Tim Peters6d6c1a32001-08-02 04:15:00 +000080
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
Mark Hammond91a681d2002-08-12 07:21:58 +000091PyAPI_DATA(PyTypeObject) PyDict_Type;
Christian Heimesa22e8bd2007-11-29 22:35:39 +000092PyAPI_DATA(PyTypeObject) PyDictIterKey_Type;
93PyAPI_DATA(PyTypeObject) PyDictIterValue_Type;
94PyAPI_DATA(PyTypeObject) PyDictIterItem_Type;
95PyAPI_DATA(PyTypeObject) PyDictKeys_Type;
96PyAPI_DATA(PyTypeObject) PyDictItems_Type;
97PyAPI_DATA(PyTypeObject) PyDictValues_Type;
Guido van Rossum2ec90311997-05-13 21:23:32 +000098
Thomas Wouters27d517b2007-02-25 20:39:11 +000099#define PyDict_Check(op) \
Christian Heimes90aa7642007-12-19 02:45:37 +0000100 PyType_FastSubclass(Py_TYPE(op), Py_TPFLAGS_DICT_SUBCLASS)
101#define PyDict_CheckExact(op) (Py_TYPE(op) == &PyDict_Type)
102#define PyDictKeys_Check(op) (Py_TYPE(op) == &PyDictKeys_Type)
103#define PyDictItems_Check(op) (Py_TYPE(op) == &PyDictItems_Type)
104#define PyDictValues_Check(op) (Py_TYPE(op) == &PyDictValues_Type)
Christian Heimesa22e8bd2007-11-29 22:35:39 +0000105/* This excludes Values, since they are not sets. */
106# define PyDictViewSet_Check(op) \
107 (PyDictKeys_Check(op) || PyDictItems_Check(op))
108
Guido van Rossum2ec90311997-05-13 21:23:32 +0000109
Mark Hammond91a681d2002-08-12 07:21:58 +0000110PyAPI_FUNC(PyObject *) PyDict_New(void);
111PyAPI_FUNC(PyObject *) PyDict_GetItem(PyObject *mp, PyObject *key);
112PyAPI_FUNC(int) PyDict_SetItem(PyObject *mp, PyObject *key, PyObject *item);
113PyAPI_FUNC(int) PyDict_DelItem(PyObject *mp, PyObject *key);
114PyAPI_FUNC(void) PyDict_Clear(PyObject *mp);
115PyAPI_FUNC(int) PyDict_Next(
Martin v. Löwis18e16552006-02-15 17:27:45 +0000116 PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value);
Thomas Wouterscf297e42007-02-23 15:07:44 +0000117PyAPI_FUNC(int) _PyDict_Next(
118 PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value, long *hash);
Mark Hammond91a681d2002-08-12 07:21:58 +0000119PyAPI_FUNC(PyObject *) PyDict_Keys(PyObject *mp);
120PyAPI_FUNC(PyObject *) PyDict_Values(PyObject *mp);
121PyAPI_FUNC(PyObject *) PyDict_Items(PyObject *mp);
Martin v. Löwis18e16552006-02-15 17:27:45 +0000122PyAPI_FUNC(Py_ssize_t) PyDict_Size(PyObject *mp);
Mark Hammond91a681d2002-08-12 07:21:58 +0000123PyAPI_FUNC(PyObject *) PyDict_Copy(PyObject *mp);
Raymond Hettingerbc0f2ab2003-11-25 21:12:14 +0000124PyAPI_FUNC(int) PyDict_Contains(PyObject *mp, PyObject *key);
Thomas Wouterscf297e42007-02-23 15:07:44 +0000125PyAPI_FUNC(int) _PyDict_Contains(PyObject *mp, PyObject *key, long hash);
Christian Heimes99170a52007-12-19 02:07:34 +0000126PyAPI_FUNC(PyObject *) _PyDict_NewPresized(Py_ssize_t minused);
Jeremy Hyltona12c7a72000-03-30 22:27:31 +0000127
Tim Petersf582b822001-12-11 18:51:08 +0000128/* PyDict_Update(mp, other) is equivalent to PyDict_Merge(mp, other, 1). */
Mark Hammond91a681d2002-08-12 07:21:58 +0000129PyAPI_FUNC(int) PyDict_Update(PyObject *mp, PyObject *other);
Tim Petersf582b822001-12-11 18:51:08 +0000130
131/* PyDict_Merge updates/merges from a mapping object (an object that
132 supports PyMapping_Keys() and PyObject_GetItem()). If override is true,
133 the last occurrence of a key wins, else the first. The Python
134 dict.update(other) is equivalent to PyDict_Merge(dict, other, 1).
135*/
Mark Hammond91a681d2002-08-12 07:21:58 +0000136PyAPI_FUNC(int) PyDict_Merge(PyObject *mp,
Tim Petersf582b822001-12-11 18:51:08 +0000137 PyObject *other,
138 int override);
139
140/* PyDict_MergeFromSeq2 updates/merges from an iterable object producing
141 iterable objects of length 2. If override is true, the last occurrence
142 of a key wins, else the first. The Python dict constructor dict(seq2)
143 is equivalent to dict={}; PyDict_MergeFromSeq(dict, seq2, 1).
144*/
Mark Hammond91a681d2002-08-12 07:21:58 +0000145PyAPI_FUNC(int) PyDict_MergeFromSeq2(PyObject *d,
Tim Petersf582b822001-12-11 18:51:08 +0000146 PyObject *seq2,
147 int override);
Guido van Rossum2ec90311997-05-13 21:23:32 +0000148
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +0000149PyAPI_FUNC(PyObject *) PyDict_GetItemString(PyObject *dp, const char *key);
150PyAPI_FUNC(int) PyDict_SetItemString(PyObject *dp, const char *key, PyObject *item);
151PyAPI_FUNC(int) PyDict_DelItemString(PyObject *dp, const char *key);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000152
Guido van Rossuma3309961993-07-28 09:05:47 +0000153#ifdef __cplusplus
154}
155#endif
156#endif /* !Py_DICTOBJECT_H */