Eric Snow | 47db717 | 2015-05-29 22:21:39 -0600 | [diff] [blame] | 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 | |
Victor Stinner | 742da04 | 2016-09-07 17:40:12 -0700 | [diff] [blame] | 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); |
Eric Snow | 47db717 | 2015-05-29 22:21:39 -0600 | [diff] [blame] | 17 | |
Victor Stinner | 742da04 | 2016-09-07 17:40:12 -0700 | [diff] [blame] | 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 */ |
Eric Snow | 47db717 | 2015-05-29 22:21:39 -0600 | [diff] [blame] | 23 | struct _dictkeysobject { |
| 24 | Py_ssize_t dk_refcnt; |
Victor Stinner | a4348cc | 2016-09-08 12:01:25 -0700 | [diff] [blame] | 25 | |
| 26 | /* Size of the hash table (dk_indices). It must be a power of 2. */ |
Eric Snow | 47db717 | 2015-05-29 22:21:39 -0600 | [diff] [blame] | 27 | Py_ssize_t dk_size; |
Victor Stinner | a4348cc | 2016-09-08 12:01:25 -0700 | [diff] [blame] | 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. */ |
Eric Snow | 47db717 | 2015-05-29 22:21:39 -0600 | [diff] [blame] | 42 | dict_lookup_func dk_lookup; |
Victor Stinner | a4348cc | 2016-09-08 12:01:25 -0700 | [diff] [blame] | 43 | |
Victor Stinner | 611b0fa | 2016-09-14 15:02:01 +0200 | [diff] [blame] | 44 | /* Number of usable entries in dk_entries. */ |
Eric Snow | 47db717 | 2015-05-29 22:21:39 -0600 | [diff] [blame] | 45 | Py_ssize_t dk_usable; |
Victor Stinner | a4348cc | 2016-09-08 12:01:25 -0700 | [diff] [blame] | 46 | |
Victor Stinner | 611b0fa | 2016-09-14 15:02:01 +0200 | [diff] [blame] | 47 | /* Number of used entries in dk_entries. */ |
Victor Stinner | a4348cc | 2016-09-08 12:01:25 -0700 | [diff] [blame] | 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*) |
Benjamin Peterson | 3c56929 | 2016-09-08 13:16:41 -0700 | [diff] [blame] | 60 | - 8 bytes otherwise (int64_t*) |
Victor Stinner | a4348cc | 2016-09-08 12:01:25 -0700 | [diff] [blame] | 61 | |
| 62 | Dynamically sized, 8 is minimum. */ |
Benjamin Peterson | 186122e | 2016-09-08 12:20:12 -0700 | [diff] [blame] | 63 | union { |
| 64 | int8_t as_1[8]; |
| 65 | int16_t as_2[4]; |
| 66 | int32_t as_4[2]; |
Benjamin Peterson | 3c56929 | 2016-09-08 13:16:41 -0700 | [diff] [blame] | 67 | #if SIZEOF_VOID_P > 4 |
Benjamin Peterson | 186122e | 2016-09-08 12:20:12 -0700 | [diff] [blame] | 68 | int64_t as_8[1]; |
Benjamin Peterson | 3c56929 | 2016-09-08 13:16:41 -0700 | [diff] [blame] | 69 | #endif |
Benjamin Peterson | 186122e | 2016-09-08 12:20:12 -0700 | [diff] [blame] | 70 | } dk_indices; |
Victor Stinner | a4348cc | 2016-09-08 12:01:25 -0700 | [diff] [blame] | 71 | |
| 72 | /* "PyDictKeyEntry dk_entries[dk_usable];" array follows: |
| 73 | see the DK_ENTRIES() macro */ |
Eric Snow | 47db717 | 2015-05-29 22:21:39 -0600 | [diff] [blame] | 74 | }; |
| 75 | |
| 76 | #endif |