← Back to branch summary

~ubuntu-branches/ubuntu/maverick/python3.1/maverick

« back to all changes in this revision

Viewing changes to Include/dictobject.h

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Klose
  • Date: 2009-03-23 00:01:27 UTC
  • Revision ID: james.westby@ubuntu.com-20090323000127-5fstfxju4ufrhthq
Tags: upstream-3.1~a1+20090322
Import upstream version 3.1~a1+20090322

Show diffs side-by-side

added added

removed removed

Lines of Context:
Include/dictobject.h
 
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
PyAPI_DATA(PyTypeObject) PyDictIterKey_Type;
 
93
PyAPI_DATA(PyTypeObject) PyDictIterValue_Type;
 
94
PyAPI_DATA(PyTypeObject) PyDictIterItem_Type;
 
95
PyAPI_DATA(PyTypeObject) PyDictKeys_Type;
 
96
PyAPI_DATA(PyTypeObject) PyDictItems_Type;
 
97
PyAPI_DATA(PyTypeObject) PyDictValues_Type;
 
98
 
 
99
#define PyDict_Check(op) \
 
100
                 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)
 
105
/* This excludes Values, since they are not sets. */
 
106
# define PyDictViewSet_Check(op) \
 
107
        (PyDictKeys_Check(op) || PyDictItems_Check(op))
 
108
 
 
109
 
 
110
PyAPI_FUNC(PyObject *) PyDict_New(void);
 
111
PyAPI_FUNC(PyObject *) PyDict_GetItem(PyObject *mp, PyObject *key);
 
112
PyAPI_FUNC(PyObject *) PyDict_GetItemWithError(PyObject *mp, PyObject *key);
 
113
PyAPI_FUNC(int) PyDict_SetItem(PyObject *mp, PyObject *key, PyObject *item);
 
114
PyAPI_FUNC(int) PyDict_DelItem(PyObject *mp, PyObject *key);
 
115
PyAPI_FUNC(void) PyDict_Clear(PyObject *mp);
 
116
PyAPI_FUNC(int) PyDict_Next(
 
117
        PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value);
 
118
PyAPI_FUNC(int) _PyDict_Next(
 
119
        PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value, long *hash);
 
120
PyAPI_FUNC(PyObject *) PyDict_Keys(PyObject *mp);
 
121
PyAPI_FUNC(PyObject *) PyDict_Values(PyObject *mp);
 
122
PyAPI_FUNC(PyObject *) PyDict_Items(PyObject *mp);
 
123
PyAPI_FUNC(Py_ssize_t) PyDict_Size(PyObject *mp);
 
124
PyAPI_FUNC(PyObject *) PyDict_Copy(PyObject *mp);
 
125
PyAPI_FUNC(int) PyDict_Contains(PyObject *mp, PyObject *key);
 
126
PyAPI_FUNC(int) _PyDict_Contains(PyObject *mp, PyObject *key, long hash);
 
127
PyAPI_FUNC(PyObject *) _PyDict_NewPresized(Py_ssize_t minused);
 
128
 
 
129
/* PyDict_Update(mp, other) is equivalent to PyDict_Merge(mp, other, 1). */
 
130
PyAPI_FUNC(int) PyDict_Update(PyObject *mp, PyObject *other);
 
131
 
 
132
/* PyDict_Merge updates/merges from a mapping object (an object that
 
133
   supports PyMapping_Keys() and PyObject_GetItem()).  If override is true,
 
134
   the last occurrence of a key wins, else the first.  The Python
 
135
   dict.update(other) is equivalent to PyDict_Merge(dict, other, 1).
 
136
*/
 
137
PyAPI_FUNC(int) PyDict_Merge(PyObject *mp,
 
138
                                   PyObject *other,
 
139
                                   int override);
 
140
 
 
141
/* PyDict_MergeFromSeq2 updates/merges from an iterable object producing
 
142
   iterable objects of length 2.  If override is true, the last occurrence
 
143
   of a key wins, else the first.  The Python dict constructor dict(seq2)
 
144
   is equivalent to dict={}; PyDict_MergeFromSeq(dict, seq2, 1).
 
145
*/
 
146
PyAPI_FUNC(int) PyDict_MergeFromSeq2(PyObject *d,
 
147
                                           PyObject *seq2,
 
148
                                           int override);
 
149
 
 
150
PyAPI_FUNC(PyObject *) PyDict_GetItemString(PyObject *dp, const char *key);
 
151
PyAPI_FUNC(int) PyDict_SetItemString(PyObject *dp, const char *key, PyObject *item);
 
152
PyAPI_FUNC(int) PyDict_DelItemString(PyObject *dp, const char *key);
 
153
 
 
154
#ifdef __cplusplus
 
155
}
 
156
#endif
 
157
#endif /* !Py_DICTOBJECT_H */