blob: 547430ea93846e510114e05420b8bbcd874093c8 [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
Tim Peters6d6c1a32001-08-02 04:15:00 +000010/*
11There are three kinds of slots in the table:
12
131. Unused. me_key == me_value == NULL
14 Does not hold an active (key, value) pair now and never did. Unused can
15 transition to Active upon key insertion. This is the only case in which
16 me_key is NULL, and is each slot's initial state.
17
182. Active. me_key != NULL and me_key != dummy and me_value != NULL
19 Holds an active (key, value) pair. Active can transition to Dummy upon
20 key deletion. This is the only case in which me_value != NULL.
21
223. Dummy. me_key == dummy and me_value == NULL
23 Previously held an active (key, value) pair, but that was deleted and an
24 active pair has not yet overwritten the slot. Dummy can transition to
25 Active upon key insertion. Dummy slots cannot be made Unused again
26 (cannot have me_key set to NULL), else the probe sequence in case of
27 collision would have no way to know they were once active.
28
29Note: .popitem() abuses the me_hash field of an Unused or Dummy slot to
30hold a search finger. The me_hash field of Unused or Dummy slots has no
31meaning otherwise.
32*/
33
34/* PyDict_MINSIZE is the minimum size of a dictionary. This many slots are
35 * allocated directly in the dict object (in the ma_smalltable member).
36 * It must be a power of 2, and at least 4. 8 allows dicts with no more
37 * than 5 active entries to live in ma_smalltable (and so avoid an
38 * additional malloc); instrumentation suggested this suffices for the
39 * majority of dicts (consisting mostly of usually-small instance dicts and
40 * usually-small dicts created to pass keyword arguments).
41 */
42#define PyDict_MINSIZE 8
43
44typedef struct {
45 long me_hash; /* cached hash code of me_key */
46 PyObject *me_key;
47 PyObject *me_value;
48#ifdef USE_CACHE_ALIGNED
49 long aligner;
50#endif
51} PyDictEntry;
52
53/*
54To ensure the lookup algorithm terminates, there must be at least one Unused
55slot (NULL key) in the table.
56The value ma_fill is the number of non-NULL keys (sum of Active and Dummy);
57ma_used is the number of non-NULL, non-dummy keys (== the number of non-NULL
58values == the number of Active items).
59To avoid slowing down lookups on a near-full table, we resize the table when
60it's two-thirds full.
61*/
62typedef struct _dictobject PyDictObject;
63struct _dictobject {
64 PyObject_HEAD
65 int ma_fill; /* # Active + # Dummy */
66 int ma_used; /* # Active */
67
68 /* The table contains ma_mask + 1 slots, and that's a power of 2.
69 * We store the mask instead of the size because the mask is more
70 * frequently needed.
71 */
72 int ma_mask;
73
74 /* ma_table points to ma_smalltable for small tables, else to
75 * additional malloc'ed memory. ma_table is never NULL! This rule
76 * saves repeated runtime null-tests in the workhorse getitem and
77 * setitem calls.
78 */
79 PyDictEntry *ma_table;
80 PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
81 PyDictEntry ma_smalltable[PyDict_MINSIZE];
82};
83
Guido van Rossum2ec90311997-05-13 21:23:32 +000084extern DL_IMPORT(PyTypeObject) PyDict_Type;
85
Tim Peters6d6c1a32001-08-02 04:15:00 +000086#define PyDict_Check(op) PyObject_TypeCheck(op, &PyDict_Type)
Guido van Rossum2ec90311997-05-13 21:23:32 +000087
Tim Peters1f5871e2000-07-04 17:44:48 +000088extern DL_IMPORT(PyObject *) PyDict_New(void);
89extern DL_IMPORT(PyObject *) PyDict_GetItem(PyObject *mp, PyObject *key);
90extern DL_IMPORT(int) PyDict_SetItem(PyObject *mp, PyObject *key, PyObject *item);
91extern DL_IMPORT(int) PyDict_DelItem(PyObject *mp, PyObject *key);
92extern DL_IMPORT(void) PyDict_Clear(PyObject *mp);
Guido van Rossum43466ec1998-12-04 18:48:25 +000093extern DL_IMPORT(int) PyDict_Next
Tim Peters1f5871e2000-07-04 17:44:48 +000094 (PyObject *mp, int *pos, PyObject **key, PyObject **value);
95extern DL_IMPORT(PyObject *) PyDict_Keys(PyObject *mp);
96extern DL_IMPORT(PyObject *) PyDict_Values(PyObject *mp);
97extern DL_IMPORT(PyObject *) PyDict_Items(PyObject *mp);
98extern DL_IMPORT(int) PyDict_Size(PyObject *mp);
99extern DL_IMPORT(PyObject *) PyDict_Copy(PyObject *mp);
Jeremy Hyltona12c7a72000-03-30 22:27:31 +0000100
Tim Petersf582b822001-12-11 18:51:08 +0000101/* PyDict_Update(mp, other) is equivalent to PyDict_Merge(mp, other, 1). */
102extern DL_IMPORT(int) PyDict_Update(PyObject *mp, PyObject *other);
103
104/* PyDict_Merge updates/merges from a mapping object (an object that
105 supports PyMapping_Keys() and PyObject_GetItem()). If override is true,
106 the last occurrence of a key wins, else the first. The Python
107 dict.update(other) is equivalent to PyDict_Merge(dict, other, 1).
108*/
109extern DL_IMPORT(int) PyDict_Merge(PyObject *mp,
110 PyObject *other,
111 int override);
112
113/* PyDict_MergeFromSeq2 updates/merges from an iterable object producing
114 iterable objects of length 2. If override is true, the last occurrence
115 of a key wins, else the first. The Python dict constructor dict(seq2)
116 is equivalent to dict={}; PyDict_MergeFromSeq(dict, seq2, 1).
117*/
118extern DL_IMPORT(int) PyDict_MergeFromSeq2(PyObject *d,
119 PyObject *seq2,
120 int override);
Guido van Rossum2ec90311997-05-13 21:23:32 +0000121
Tim Peters1f5871e2000-07-04 17:44:48 +0000122extern DL_IMPORT(PyObject *) PyDict_GetItemString(PyObject *dp, char *key);
123extern DL_IMPORT(int) PyDict_SetItemString(PyObject *dp, char *key, PyObject *item);
124extern DL_IMPORT(int) PyDict_DelItemString(PyObject *dp, char *key);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000125
Guido van Rossuma3309961993-07-28 09:05:47 +0000126#ifdef __cplusplus
127}
128#endif
129#endif /* !Py_DICTOBJECT_H */