blob: 71d6b0274420b83760b6ea684e57922251381cd6 [file] [log] [blame]
Eric Snow47db7172015-05-29 22:21:39 -06001#ifndef Py_DICT_COMMON_H
2#define Py_DICT_COMMON_H
3
4typedef 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
Victor Stinner742da042016-09-07 17:40:12 -070011/* 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 */
14typedef Py_ssize_t (*dict_lookup_func)
INADA Naoki778928b2017-08-03 23:45:15 +090015 (PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
Eric Snow47db7172015-05-29 22:21:39 -060016
Victor Stinner742da042016-09-07 17:40:12 -070017#define DKIX_EMPTY (-1)
18#define DKIX_DUMMY (-2) /* Used internally */
19#define DKIX_ERROR (-3)
20
21/* See dictobject.c for actual layout of DictKeysObject */
Eric Snow47db7172015-05-29 22:21:39 -060022struct _dictkeysobject {
23 Py_ssize_t dk_refcnt;
Victor Stinnera4348cc2016-09-08 12:01:25 -070024
25 /* Size of the hash table (dk_indices). It must be a power of 2. */
Eric Snow47db7172015-05-29 22:21:39 -060026 Py_ssize_t dk_size;
Victor Stinnera4348cc2016-09-08 12:01:25 -070027
28 /* Function to lookup in the hash table (dk_indices):
29
30 - lookdict(): general-purpose, and may return DKIX_ERROR if (and
31 only if) a comparison raises an exception.
32
33 - lookdict_unicode(): specialized to Unicode string keys, comparison of
34 which can never raise an exception; that function can never return
35 DKIX_ERROR.
36
37 - lookdict_unicode_nodummy(): similar to lookdict_unicode() but further
38 specialized for Unicode string keys that cannot be the <dummy> value.
39
40 - lookdict_split(): Version of lookdict() for split tables. */
Eric Snow47db7172015-05-29 22:21:39 -060041 dict_lookup_func dk_lookup;
Victor Stinnera4348cc2016-09-08 12:01:25 -070042
Victor Stinner611b0fa2016-09-14 15:02:01 +020043 /* Number of usable entries in dk_entries. */
Eric Snow47db7172015-05-29 22:21:39 -060044 Py_ssize_t dk_usable;
Victor Stinnera4348cc2016-09-08 12:01:25 -070045
Victor Stinner611b0fa2016-09-14 15:02:01 +020046 /* Number of used entries in dk_entries. */
Victor Stinnera4348cc2016-09-08 12:01:25 -070047 Py_ssize_t dk_nentries;
48
49 /* Actual hash table of dk_size entries. It holds indices in dk_entries,
50 or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
51
52 Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
53
54 The size in bytes of an indice depends on dk_size:
55
56 - 1 byte if dk_size <= 0xff (char*)
57 - 2 bytes if dk_size <= 0xffff (int16_t*)
58 - 4 bytes if dk_size <= 0xffffffff (int32_t*)
Benjamin Peterson3c569292016-09-08 13:16:41 -070059 - 8 bytes otherwise (int64_t*)
Victor Stinnera4348cc2016-09-08 12:01:25 -070060
Gregory P. Smith397f1b22018-04-19 22:41:19 -070061 Dynamically sized, SIZEOF_VOID_P is minimum. */
62 char dk_indices[]; /* char is required to avoid strict aliasing. */
Victor Stinnera4348cc2016-09-08 12:01:25 -070063
64 /* "PyDictKeyEntry dk_entries[dk_usable];" array follows:
65 see the DK_ENTRIES() macro */
Eric Snow47db7172015-05-29 22:21:39 -060066};
67
68#endif