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