1 #ifndef Py_DICT_COMMON_H
2 #define Py_DICT_COMMON_H
3 
4 typedef struct {
5     /* Cached hash code of me_key. */
6     Py_hash_t me_hash;
7     PyObject *me_key;
8     PyObject *me_value; /* This field is only meaningful for combined tables */
9 } PyDictKeyEntry;
10 
11 /* dict_lookup_func() returns index of entry which can be used like DK_ENTRIES(dk)[index].
12  * -1 when no entry found, -3 when compare raises error.
13  */
14 typedef Py_ssize_t (*dict_lookup_func)
15 (PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr,
16  Py_ssize_t *hashpos);
17 
18 #define DKIX_EMPTY (-1)
19 #define DKIX_DUMMY (-2)  /* Used internally */
20 #define DKIX_ERROR (-3)
21 
22 /* See dictobject.c for actual layout of DictKeysObject */
23 struct _dictkeysobject {
24     Py_ssize_t dk_refcnt;
25 
26     /* Size of the hash table (dk_indices). It must be a power of 2. */
27     Py_ssize_t dk_size;
28 
29     /* Function to lookup in the hash table (dk_indices):
30 
31        - lookdict(): general-purpose, and may return DKIX_ERROR if (and
32          only if) a comparison raises an exception.
33 
34        - lookdict_unicode(): specialized to Unicode string keys, comparison of
35          which can never raise an exception; that function can never return
36          DKIX_ERROR.
37 
38        - lookdict_unicode_nodummy(): similar to lookdict_unicode() but further
39          specialized for Unicode string keys that cannot be the <dummy> value.
40 
41        - lookdict_split(): Version of lookdict() for split tables. */
42     dict_lookup_func dk_lookup;
43 
44     /* Number of usable entries in dk_entries. */
45     Py_ssize_t dk_usable;
46 
47     /* Number of used entries in dk_entries. */
48     Py_ssize_t dk_nentries;
49 
50     /* Actual hash table of dk_size entries. It holds indices in dk_entries,
51        or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
52 
53        Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
54 
55        The size in bytes of an indice depends on dk_size:
56 
57        - 1 byte if dk_size <= 0xff (char*)
58        - 2 bytes if dk_size <= 0xffff (int16_t*)
59        - 4 bytes if dk_size <= 0xffffffff (int32_t*)
60        - 8 bytes otherwise (int64_t*)
61 
62        Dynamically sized, 8 is minimum. */
63     union {
64         int8_t as_1[8];
65         int16_t as_2[4];
66         int32_t as_4[2];
67 #if SIZEOF_VOID_P > 4
68         int64_t as_8[1];
69 #endif
70     } dk_indices;
71 
72     /* "PyDictKeyEntry dk_entries[dk_usable];" array follows:
73        see the DK_ENTRIES() macro */
74 };
75 
76 #endif
77