diff options
Diffstat (limited to 'Include/dictobject.h')
| -rw-r--r-- | Include/dictobject.h | 136 |
1 files changed, 101 insertions, 35 deletions
diff --git a/Include/dictobject.h b/Include/dictobject.h index b37573a..5a1e9fe 100644 --- a/Include/dictobject.h +++ b/Include/dictobject.h @@ -4,6 +4,7 @@ extern "C" { #endif + /* Dictionary object type -- mapping from hashable object to object */ /* The distribution includes a separate file, Objects/dictnotes.txt, @@ -12,26 +13,121 @@ extern "C" { tuning dictionaries, and several ideas for possible optimizations. */ +/* +There are three kinds of slots in the table: + +1. Unused. me_key == me_value == NULL + Does not hold an active (key, value) pair now and never did. Unused can + transition to Active upon key insertion. This is the only case in which + me_key is NULL, and is each slot's initial state. + +2. Active. me_key != NULL and me_key != dummy and me_value != NULL + Holds an active (key, value) pair. Active can transition to Dummy upon + key deletion. This is the only case in which me_value != NULL. + +3. Dummy. me_key == dummy and me_value == NULL + Previously held an active (key, value) pair, but that was deleted and an + active pair has not yet overwritten the slot. Dummy can transition to + Active upon key insertion. Dummy slots cannot be made Unused again + (cannot have me_key set to NULL), else the probe sequence in case of + collision would have no way to know they were once active. + +Note: .popitem() abuses the me_hash field of an Unused or Dummy slot to +hold a search finger. The me_hash field of Unused or Dummy slots has no +meaning otherwise. +*/ + +/* PyDict_MINSIZE is the minimum size of a dictionary. This many slots are + * allocated directly in the dict object (in the ma_smalltable member). + * It must be a power of 2, and at least 4. 8 allows dicts with no more + * than 5 active entries to live in ma_smalltable (and so avoid an + * additional malloc); instrumentation suggested this suffices for the + * majority of dicts (consisting mostly of usually-small instance dicts and + * usually-small dicts created to pass keyword arguments). + */ +#define PyDict_MINSIZE 8 + +typedef struct { + /* Cached hash code of me_key. Note that hash codes are C longs. + * We have to use Py_ssize_t instead because dict_popitem() abuses + * me_hash to hold a search finger. + */ + Py_ssize_t me_hash; + PyObject *me_key; + PyObject *me_value; +} PyDictEntry; + +/* +To ensure the lookup algorithm terminates, there must be at least one Unused +slot (NULL key) in the table. +The value ma_fill is the number of non-NULL keys (sum of Active and Dummy); +ma_used is the number of non-NULL, non-dummy keys (== the number of non-NULL +values == the number of Active items). +To avoid slowing down lookups on a near-full table, we resize the table when +it's two-thirds full. +*/ +typedef struct _dictobject PyDictObject; +struct _dictobject { + PyObject_HEAD + Py_ssize_t ma_fill; /* # Active + # Dummy */ + Py_ssize_t ma_used; /* # Active */ + + /* The table contains ma_mask + 1 slots, and that's a power of 2. + * We store the mask instead of the size because the mask is more + * frequently needed. + */ + Py_ssize_t ma_mask; + + /* ma_table points to ma_smalltable for small tables, else to + * additional malloc'ed memory. ma_table is never NULL! This rule + * saves repeated runtime null-tests in the workhorse getitem and + * setitem calls. + */ + PyDictEntry *ma_table; + PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash); + PyDictEntry ma_smalltable[PyDict_MINSIZE]; +}; + PyAPI_DATA(PyTypeObject) PyDict_Type; +PyAPI_DATA(PyTypeObject) PyDictIterKey_Type; +PyAPI_DATA(PyTypeObject) PyDictIterValue_Type; +PyAPI_DATA(PyTypeObject) PyDictIterItem_Type; +PyAPI_DATA(PyTypeObject) PyDictKeys_Type; +PyAPI_DATA(PyTypeObject) PyDictItems_Type; +PyAPI_DATA(PyTypeObject) PyDictValues_Type; #define PyDict_Check(op) \ PyType_FastSubclass(Py_TYPE(op), Py_TPFLAGS_DICT_SUBCLASS) #define PyDict_CheckExact(op) (Py_TYPE(op) == &PyDict_Type) +#define PyDictKeys_Check(op) (Py_TYPE(op) == &PyDictKeys_Type) +#define PyDictItems_Check(op) (Py_TYPE(op) == &PyDictItems_Type) +#define PyDictValues_Check(op) (Py_TYPE(op) == &PyDictValues_Type) +/* This excludes Values, since they are not sets. */ +# define PyDictViewSet_Check(op) \ + (PyDictKeys_Check(op) || PyDictItems_Check(op)) PyAPI_FUNC(PyObject *) PyDict_New(void); PyAPI_FUNC(PyObject *) PyDict_GetItem(PyObject *mp, PyObject *key); -PyAPI_FUNC(PyObject *) PyDict_GetItemWithError(PyObject *mp, PyObject *key); +PyAPI_FUNC(PyObject *) _PyDict_GetItemWithError(PyObject *mp, PyObject *key); PyAPI_FUNC(int) PyDict_SetItem(PyObject *mp, PyObject *key, PyObject *item); PyAPI_FUNC(int) PyDict_DelItem(PyObject *mp, PyObject *key); +PyAPI_FUNC(int) _PyDict_DelItemIf(PyObject *mp, PyObject *key, + int (*predicate)(PyObject *value)); + PyAPI_FUNC(void) PyDict_Clear(PyObject *mp); PyAPI_FUNC(int) PyDict_Next( PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value); +PyAPI_FUNC(int) _PyDict_Next( + PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value, long *hash); PyAPI_FUNC(PyObject *) PyDict_Keys(PyObject *mp); PyAPI_FUNC(PyObject *) PyDict_Values(PyObject *mp); PyAPI_FUNC(PyObject *) PyDict_Items(PyObject *mp); PyAPI_FUNC(Py_ssize_t) PyDict_Size(PyObject *mp); PyAPI_FUNC(PyObject *) PyDict_Copy(PyObject *mp); PyAPI_FUNC(int) PyDict_Contains(PyObject *mp, PyObject *key); +PyAPI_FUNC(int) _PyDict_Contains(PyObject *mp, PyObject *key, long hash); +PyAPI_FUNC(PyObject *) _PyDict_NewPresized(Py_ssize_t minused); +PyAPI_FUNC(void) _PyDict_MaybeUntrack(PyObject *mp); /* PyDict_Update(mp, other) is equivalent to PyDict_Merge(mp, other, 1). */ PyAPI_FUNC(int) PyDict_Update(PyObject *mp, PyObject *other); @@ -42,8 +138,8 @@ PyAPI_FUNC(int) PyDict_Update(PyObject *mp, PyObject *other); dict.update(other) is equivalent to PyDict_Merge(dict, other, 1). */ PyAPI_FUNC(int) PyDict_Merge(PyObject *mp, - PyObject *other, - int override); + PyObject *other, + int override); /* PyDict_MergeFromSeq2 updates/merges from an iterable object producing iterable objects of length 2. If override is true, the last occurrence @@ -51,43 +147,13 @@ PyAPI_FUNC(int) PyDict_Merge(PyObject *mp, is equivalent to dict={}; PyDict_MergeFromSeq(dict, seq2, 1). */ PyAPI_FUNC(int) PyDict_MergeFromSeq2(PyObject *d, - PyObject *seq2, - int override); + PyObject *seq2, + int override); PyAPI_FUNC(PyObject *) PyDict_GetItemString(PyObject *dp, const char *key); PyAPI_FUNC(int) PyDict_SetItemString(PyObject *dp, const char *key, PyObject *item); PyAPI_FUNC(int) PyDict_DelItemString(PyObject *dp, const char *key); -/* Dictionary (keys, values, items) views */ - -PyAPI_DATA(PyTypeObject) PyDictKeys_Type; -PyAPI_DATA(PyTypeObject) PyDictValues_Type; -PyAPI_DATA(PyTypeObject) PyDictItems_Type; - -#define PyDictKeys_Check(op) PyObject_TypeCheck(op, &PyDictKeys_Type) -#define PyDictValues_Check(op) PyObject_TypeCheck(op, &PyDictValues_Type) -#define PyDictItems_Check(op) PyObject_TypeCheck(op, &PyDictItems_Type) -/* This excludes Values, since they are not sets. */ -# define PyDictViewSet_Check(op) \ - (PyDictKeys_Check(op) || PyDictItems_Check(op)) - -/* Dictionary (key, value, items) iterators */ - -PyAPI_DATA(PyTypeObject) PyDictIterKey_Type; -PyAPI_DATA(PyTypeObject) PyDictIterValue_Type; -PyAPI_DATA(PyTypeObject) PyDictIterItem_Type; - -PyAPI_DATA(PyTypeObject) PyDictRevIterKey_Type; -PyAPI_DATA(PyTypeObject) PyDictRevIterItem_Type; -PyAPI_DATA(PyTypeObject) PyDictRevIterValue_Type; - - -#ifndef Py_LIMITED_API -# define Py_CPYTHON_DICTOBJECT_H -# include "cpython/dictobject.h" -# undef Py_CPYTHON_DICTOBJECT_H -#endif - #ifdef __cplusplus } #endif |