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         long me_hash;      /* cached hash code of me_key */
  52         PyObject *me_key;
  53         PyObject *me_value;
  54 } PyDictEntry;
  55
  56 /*
  57 To ensure the lookup algorithm terminates, there must be at least one Unused
  58 slot (NULL key) in the table.
  59 The value ma_fill is the number of non-NULL keys (sum of Active and Dummy);
  60 ma_used is the number of non-NULL, non-dummy keys (== the number of non-NULL
  61 values == the number of Active items).
  62 To avoid slowing down lookups on a near-full table, we resize the table when
  63 it's two-thirds full.
  64 */
  65 typedef struct _dictobject PyDictObject;
  66 struct _dictobject {
  67         PyObject_HEAD
  68         int ma_fill;  /* # Active + # Dummy */
  69         int ma_used;  /* # Active */
  70
  71         /* The table contains ma_mask + 1 slots, and that's a power of 2.
  72          * We store the mask instead of the size because the mask is more
  73          * frequently needed.
  74          */
  75         int ma_mask;
  76
  77         /* ma_table points to ma_smalltable for small tables, else to
  78          * additional malloc'ed memory.  ma_table is never NULL!  This rule
  79          * saves repeated runtime null-tests in the workhorse getitem and
  80          * setitem calls.
  81          */
  82         PyDictEntry *ma_table;
  83         PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
  84         PyDictEntry ma_smalltable[PyDict_MINSIZE];
  85 };
  86
  87 PyAPI_DATA(PyTypeObject) PyDict_Type;
  88
  89 #define PyDict_Check(op) PyObject_TypeCheck(op, &PyDict_Type)
  90 #define PyDict_CheckExact(op) ((op)->ob_type == &PyDict_Type)
  91
  92 PyAPI_FUNC(PyObject *) PyDict_New(void);
  93 PyAPI_FUNC(PyObject *) PyDict_GetItem(PyObject *mp, PyObject *key);
  94 PyAPI_FUNC(int) PyDict_SetItem(PyObject *mp, PyObject *key, PyObject *item);
  95 PyAPI_FUNC(int) PyDict_DelItem(PyObject *mp, PyObject *key);
  96 PyAPI_FUNC(void) PyDict_Clear(PyObject *mp);
  97 PyAPI_FUNC(int) PyDict_Next(
  98         PyObject *mp, int *pos, PyObject **key, PyObject **value);
  99 PyAPI_FUNC(PyObject *) PyDict_Keys(PyObject *mp);
 100 PyAPI_FUNC(PyObject *) PyDict_Values(PyObject *mp);
 101 PyAPI_FUNC(PyObject *) PyDict_Items(PyObject *mp);
 102 PyAPI_FUNC(int) PyDict_Size(PyObject *mp);
 103 PyAPI_FUNC(PyObject *) PyDict_Copy(PyObject *mp);
 104 PyAPI_FUNC(int) PyDict_Contains(PyObject *mp, PyObject *key);
 105
 106 /* PyDict_Update(mp, other) is equivalent to PyDict_Merge(mp, other, 1). */
 107 PyAPI_FUNC(int) PyDict_Update(PyObject *mp, PyObject *other);
 108
 109 /* PyDict_Merge updates/merges from a mapping object (an object that
 110    supports PyMapping_Keys() and PyObject_GetItem()).  If override is true,
 111    the last occurrence of a key wins, else the first.  The Python
 112    dict.update(other) is equivalent to PyDict_Merge(dict, other, 1).
 113 */
 114 PyAPI_FUNC(int) PyDict_Merge(PyObject *mp,
 115                                    PyObject *other,
 116                                    int override);
 117
 118 /* PyDict_MergeFromSeq2 updates/merges from an iterable object producing
 119    iterable objects of length 2.  If override is true, the last occurrence
 120    of a key wins, else the first.  The Python dict constructor dict(seq2)
 121    is equivalent to dict={}; PyDict_MergeFromSeq(dict, seq2, 1).
 122 */
 123 PyAPI_FUNC(int) PyDict_MergeFromSeq2(PyObject *d,
 124                                            PyObject *seq2,
 125                                            int override);
 126
 127 PyAPI_FUNC(PyObject *) PyDict_GetItemString(PyObject *dp, const char *key);
 128 PyAPI_FUNC(int) PyDict_SetItemString(PyObject *dp, const char *key, PyObject *item);
 129 PyAPI_FUNC(int) PyDict_DelItemString(PyObject *dp, const char *key);
 130
 131 #ifdef __cplusplus
 132 }
 133 #endif
 134 #endif /* !Py_DICTOBJECT_H */