Branch data     Line data    Source code

       1                 :            : 
       2                 :            : #ifndef Py_INTERNAL_DICT_H
       3                 :            : #define Py_INTERNAL_DICT_H
       4                 :            : #ifdef __cplusplus
       5                 :            : extern "C" {
       6                 :            : #endif
       7                 :            : 
       8                 :            : #ifndef Py_BUILD_CORE
       9                 :            : #  error "this header requires Py_BUILD_CORE define"
      10                 :            : #endif
      11                 :            : 
      12                 :            : 
      13                 :            : /* runtime lifecycle */
      14                 :            : 
      15                 :            : extern void _PyDict_Fini(PyInterpreterState *interp);
      16                 :            : 
      17                 :            : 
      18                 :            : /* other API */
      19                 :            : 
      20                 :            : #ifndef WITH_FREELISTS
      21                 :            : // without freelists
      22                 :            : #  define PyDict_MAXFREELIST 0
      23                 :            : #endif
      24                 :            : 
      25                 :            : #ifndef PyDict_MAXFREELIST
      26                 :            : #  define PyDict_MAXFREELIST 80
      27                 :            : #endif
      28                 :            : 
      29                 :            : struct _Py_dict_state {
      30                 :            : #if PyDict_MAXFREELIST > 0
      31                 :            :     /* Dictionary reuse scheme to save calls to malloc and free */
      32                 :            :     PyDictObject *free_list[PyDict_MAXFREELIST];
      33                 :            :     int numfree;
      34                 :            :     PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST];
      35                 :            :     int keys_numfree;
      36                 :            : #endif
      37                 :            : };
      38                 :            : 
      39                 :            : typedef struct {
      40                 :            :     /* Cached hash code of me_key. */
      41                 :            :     Py_hash_t me_hash;
      42                 :            :     PyObject *me_key;
      43                 :            :     PyObject *me_value; /* This field is only meaningful for combined tables */
      44                 :            : } PyDictKeyEntry;
      45                 :            : 
      46                 :            : typedef struct {
      47                 :            :     PyObject *me_key;   /* The key must be Unicode and have hash. */
      48                 :            :     PyObject *me_value; /* This field is only meaningful for combined tables */
      49                 :            : } PyDictUnicodeEntry;
      50                 :            : 
      51                 :            : extern PyDictKeysObject *_PyDict_NewKeysForClass(void);
      52                 :            : extern PyObject *_PyDict_FromKeys(PyObject *, PyObject *, PyObject *);
      53                 :            : 
      54                 :            : /* Gets a version number unique to the current state of the keys of dict, if possible.
      55                 :            :  * Returns the version number, or zero if it was not possible to get a version number. */
      56                 :            : extern uint32_t _PyDictKeys_GetVersionForCurrentState(PyDictKeysObject *dictkeys);
      57                 :            : 
      58                 :            : extern Py_ssize_t _PyDict_KeysSize(PyDictKeysObject *keys);
      59                 :            : 
      60                 :            : /* _Py_dict_lookup() returns index of entry which can be used like DK_ENTRIES(dk)[index].
      61                 :            :  * -1 when no entry found, -3 when compare raises error.
      62                 :            :  */
      63                 :            : extern Py_ssize_t _Py_dict_lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
      64                 :            : 
      65                 :            : extern Py_ssize_t _PyDict_GetItemHint(PyDictObject *, PyObject *, Py_ssize_t, PyObject **);
      66                 :            : extern Py_ssize_t _PyDictKeys_StringLookup(PyDictKeysObject* dictkeys, PyObject *key);
      67                 :            : extern PyObject *_PyDict_LoadGlobal(PyDictObject *, PyDictObject *, PyObject *);
      68                 :            : 
      69                 :            : /* Consumes references to key and value */
      70                 :            : extern int _PyDict_SetItem_Take2(PyDictObject *op, PyObject *key, PyObject *value);
      71                 :            : extern int _PyObjectDict_SetItem(PyTypeObject *tp, PyObject **dictptr, PyObject *name, PyObject *value);
      72                 :            : 
      73                 :            : extern PyObject *_PyDict_Pop_KnownHash(PyObject *, PyObject *, Py_hash_t, PyObject *);
      74                 :            : 
      75                 :            : #define DKIX_EMPTY (-1)
      76                 :            : #define DKIX_DUMMY (-2)  /* Used internally */
      77                 :            : #define DKIX_ERROR (-3)
      78                 :            : #define DKIX_KEY_CHANGED (-4) /* Used internally */
      79                 :            : 
      80                 :            : typedef enum {
      81                 :            :     DICT_KEYS_GENERAL = 0,
      82                 :            :     DICT_KEYS_UNICODE = 1,
      83                 :            :     DICT_KEYS_SPLIT = 2
      84                 :            : } DictKeysKind;
      85                 :            : 
      86                 :            : /* See dictobject.c for actual layout of DictKeysObject */
      87                 :            : struct _dictkeysobject {
      88                 :            :     Py_ssize_t dk_refcnt;
      89                 :            : 
      90                 :            :     /* Size of the hash table (dk_indices). It must be a power of 2. */
      91                 :            :     uint8_t dk_log2_size;
      92                 :            : 
      93                 :            :     /* Size of the hash table (dk_indices) by bytes. */
      94                 :            :     uint8_t dk_log2_index_bytes;
      95                 :            : 
      96                 :            :     /* Kind of keys */
      97                 :            :     uint8_t dk_kind;
      98                 :            : 
      99                 :            :     /* Version number -- Reset to 0 by any modification to keys */
     100                 :            :     uint32_t dk_version;
     101                 :            : 
     102                 :            :     /* Number of usable entries in dk_entries. */
     103                 :            :     Py_ssize_t dk_usable;
     104                 :            : 
     105                 :            :     /* Number of used entries in dk_entries. */
     106                 :            :     Py_ssize_t dk_nentries;
     107                 :            : 
     108                 :            :     /* Actual hash table of dk_size entries. It holds indices in dk_entries,
     109                 :            :        or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
     110                 :            : 
     111                 :            :        Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
     112                 :            : 
     113                 :            :        The size in bytes of an indice depends on dk_size:
     114                 :            : 
     115                 :            :        - 1 byte if dk_size <= 0xff (char*)
     116                 :            :        - 2 bytes if dk_size <= 0xffff (int16_t*)
     117                 :            :        - 4 bytes if dk_size <= 0xffffffff (int32_t*)
     118                 :            :        - 8 bytes otherwise (int64_t*)
     119                 :            : 
     120                 :            :        Dynamically sized, SIZEOF_VOID_P is minimum. */
     121                 :            :     char dk_indices[];  /* char is required to avoid strict aliasing. */
     122                 :            : 
     123                 :            :     /* "PyDictKeyEntry or PyDictUnicodeEntry dk_entries[USABLE_FRACTION(DK_SIZE(dk))];" array follows:
     124                 :            :        see the DK_ENTRIES() macro */
     125                 :            : };
     126                 :            : 
     127                 :            : /* This must be no more than 250, for the prefix size to fit in one byte. */
     128                 :            : #define SHARED_KEYS_MAX_SIZE 30
     129                 :            : #define NEXT_LOG2_SHARED_KEYS_MAX_SIZE 6
     130                 :            : 
     131                 :            : /* Layout of dict values:
     132                 :            :  *
     133                 :            :  * The PyObject *values are preceded by an array of bytes holding
     134                 :            :  * the insertion order and size.
     135                 :            :  * [-1] = prefix size. [-2] = used size. size[-2-n...] = insertion order.
     136                 :            :  */
     137                 :            : struct _dictvalues {
     138                 :            :     PyObject *values[1];
     139                 :            : };
     140                 :            : 
     141                 :            : #define DK_LOG_SIZE(dk)  ((dk)->dk_log2_size)
     142                 :            : #if SIZEOF_VOID_P > 4
     143                 :            : #define DK_SIZE(dk)      (((int64_t)1)<<DK_LOG_SIZE(dk))
     144                 :            : #define DK_IXSIZE(dk)                     \
     145                 :            :     (DK_LOG_SIZE(dk) <= 7 ?               \
     146                 :            :         1 : DK_LOG_SIZE(dk) <= 15 ?       \
     147                 :            :             2 : DK_LOG_SIZE(dk) <= 31 ?   \
     148                 :            :                 4 : sizeof(int64_t))
     149                 :            : #else
     150                 :            : #define DK_SIZE(dk)      (1<<DK_LOG_SIZE(dk))
     151                 :            : #define DK_IXSIZE(dk)                     \
     152                 :            :     (DK_LOG_SIZE(dk) <= 7 ?               \
     153                 :            :         1 : DK_LOG_SIZE(dk) <= 15 ?       \
     154                 :            :             2 : sizeof(int32_t))
     155                 :            : #endif
     156                 :            : #define DK_ENTRIES(dk) \
     157                 :            :     (assert((dk)->dk_kind == DICT_KEYS_GENERAL), \
     158                 :            :      (PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[(size_t)1 << (dk)->dk_log2_index_bytes]))
     159                 :            : #define DK_UNICODE_ENTRIES(dk) \
     160                 :            :     (assert((dk)->dk_kind != DICT_KEYS_GENERAL), \
     161                 :            :      (PyDictUnicodeEntry*)(&((int8_t*)((dk)->dk_indices))[(size_t)1 << (dk)->dk_log2_index_bytes]))
     162                 :            : #define DK_IS_UNICODE(dk) ((dk)->dk_kind != DICT_KEYS_GENERAL)
     163                 :            : 
     164                 :            : extern uint64_t _pydict_global_version;
     165                 :            : 
     166                 :            : #define DICT_NEXT_VERSION() (++_pydict_global_version)
     167                 :            : 
     168                 :            : extern PyObject *_PyObject_MakeDictFromInstanceAttributes(PyObject *obj, PyDictValues *values);
     169                 :            : extern PyObject *_PyDict_FromItems(
     170                 :            :         PyObject *const *keys, Py_ssize_t keys_offset,
     171                 :            :         PyObject *const *values, Py_ssize_t values_offset,
     172                 :            :         Py_ssize_t length);
     173                 :            : 
     174                 :            : static inline void
     175                 :   35769789 : _PyDictValues_AddToInsertionOrder(PyDictValues *values, Py_ssize_t ix)
     176                 :            : {
     177                 :            :     assert(ix < SHARED_KEYS_MAX_SIZE);
     178                 :   35769789 :     uint8_t *size_ptr = ((uint8_t *)values)-2;
     179                 :   35769789 :     int size = *size_ptr;
     180                 :            :     assert(size+2 < ((uint8_t *)values)[-1]);
     181                 :   35769789 :     size++;
     182                 :   35769789 :     size_ptr[-size] = (uint8_t)ix;
     183                 :   35769789 :     *size_ptr = size;
     184                 :   35769789 : }
     185                 :            : 
     186                 :            : #ifdef __cplusplus
     187                 :            : }
     188                 :            : #endif
     189                 :            : #endif   /* !Py_INTERNAL_DICT_H */