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 PyAPI_FUNC(PyObject *) PyDict_New(void); 110 PyAPI_FUNC(PyObject *) PyDict_GetItem(PyObject *mp, PyObject *key); 111 PyAPI_FUNC(PyObject *) _PyDict_GetItemWithError(PyObject *mp, PyObject *key); 112 PyAPI_FUNC(int) PyDict_SetItem(PyObject *mp, PyObject *key, PyObject *item); 113 PyAPI_FUNC(int) PyDict_DelItem(PyObject *mp, PyObject *key); 114 PyAPI_FUNC(int) _PyDict_DelItemIf(PyObject *mp, PyObject *key, 115 int (*predicate)(PyObject *value)); 116 117 PyAPI_FUNC(void) PyDict_Clear(PyObject *mp); 118 PyAPI_FUNC(int) PyDict_Next( 119 PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value); 120 PyAPI_FUNC(int) _PyDict_Next( 121 PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value, long *hash); 122 PyAPI_FUNC(PyObject *) PyDict_Keys(PyObject *mp); 123 PyAPI_FUNC(PyObject *) PyDict_Values(PyObject *mp); 124 PyAPI_FUNC(PyObject *) PyDict_Items(PyObject *mp); 125 PyAPI_FUNC(Py_ssize_t) PyDict_Size(PyObject *mp); 126 PyAPI_FUNC(PyObject *) PyDict_Copy(PyObject *mp); 127 PyAPI_FUNC(int) PyDict_Contains(PyObject *mp, PyObject *key); 128 PyAPI_FUNC(int) _PyDict_Contains(PyObject *mp, PyObject *key, long hash); 129 PyAPI_FUNC(PyObject *) _PyDict_NewPresized(Py_ssize_t minused); 130 PyAPI_FUNC(void) _PyDict_MaybeUntrack(PyObject *mp); 131 132 /* PyDict_Update(mp, other) is equivalent to PyDict_Merge(mp, other, 1). */ 133 PyAPI_FUNC(int) PyDict_Update(PyObject *mp, PyObject *other); 134 135 /* PyDict_Merge updates/merges from a mapping object (an object that 136 supports PyMapping_Keys() and PyObject_GetItem()). If override is true, 137 the last occurrence of a key wins, else the first. The Python 138 dict.update(other) is equivalent to PyDict_Merge(dict, other, 1). 139 */ 140 PyAPI_FUNC(int) PyDict_Merge(PyObject *mp, 141 PyObject *other, 142 int override); 143 144 /* PyDict_MergeFromSeq2 updates/merges from an iterable object producing 145 iterable objects of length 2. If override is true, the last occurrence 146 of a key wins, else the first. The Python dict constructor dict(seq2) 147 is equivalent to dict={}; PyDict_MergeFromSeq(dict, seq2, 1). 148 */ 149 PyAPI_FUNC(int) PyDict_MergeFromSeq2(PyObject *d, 150 PyObject *seq2, 151 int override); 152 153 PyAPI_FUNC(PyObject *) PyDict_GetItemString(PyObject *dp, const char *key); 154 PyAPI_FUNC(int) PyDict_SetItemString(PyObject *dp, const char *key, PyObject *item); 155 PyAPI_FUNC(int) PyDict_DelItemString(PyObject *dp, const char *key); 156 157 #ifdef __cplusplus 158 } 159 #endif 160 #endif /* !Py_DICTOBJECT_H */ 161