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