diff options
author | Mariatta Wijaya <mariatta.wijaya@gmail.com> | 2017-02-06 20:16:58 -0800 |
---|---|---|
committer | Mariatta Wijaya <mariatta.wijaya@gmail.com> | 2017-02-06 20:16:58 -0800 |
commit | da79bcf8ac7ae72218ab023e1ed54390bc1a3a27 (patch) | |
tree | 74845e2dbd9521d9748b9c32f1922f4123083bf3 /Objects/dict-common.h | |
parent | e3c7e835bdfc97750eb9b7fc0ad2493108c2d438 (diff) | |
parent | 1fe806ac56f8b83694d24ab604eb695d00bc8497 (diff) | |
download | cpython-da79bcf8ac7ae72218ab023e1ed54390bc1a3a27.tar.gz |
Issue #29371: merge with 3.5
Diffstat (limited to 'Objects/dict-common.h')
-rw-r--r-- | Objects/dict-common.h | 60 |
1 files changed, 57 insertions, 3 deletions
diff --git a/Objects/dict-common.h b/Objects/dict-common.h index 2912eb94ea..ce9edabd89 100644 --- a/Objects/dict-common.h +++ b/Objects/dict-common.h @@ -8,15 +8,69 @@ typedef struct { PyObject *me_value; /* This field is only meaningful for combined tables */ } PyDictKeyEntry; -typedef PyDictKeyEntry *(*dict_lookup_func) -(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr); +/* dict_lookup_func() returns index of entry which can be used like DK_ENTRIES(dk)[index]. + * -1 when no entry found, -3 when compare raises error. + */ +typedef Py_ssize_t (*dict_lookup_func) +(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr, + Py_ssize_t *hashpos); +#define DKIX_EMPTY (-1) +#define DKIX_DUMMY (-2) /* Used internally */ +#define DKIX_ERROR (-3) + +/* See dictobject.c for actual layout of DictKeysObject */ struct _dictkeysobject { Py_ssize_t dk_refcnt; + + /* Size of the hash table (dk_indices). It must be a power of 2. */ Py_ssize_t dk_size; + + /* Function to lookup in the hash table (dk_indices): + + - lookdict(): general-purpose, and may return DKIX_ERROR if (and + only if) a comparison raises an exception. + + - lookdict_unicode(): specialized to Unicode string keys, comparison of + which can never raise an exception; that function can never return + DKIX_ERROR. + + - lookdict_unicode_nodummy(): similar to lookdict_unicode() but further + specialized for Unicode string keys that cannot be the <dummy> value. + + - lookdict_split(): Version of lookdict() for split tables. */ dict_lookup_func dk_lookup; + + /* Number of usable entries in dk_entries. */ Py_ssize_t dk_usable; - PyDictKeyEntry dk_entries[1]; + + /* Number of used entries in dk_entries. */ + Py_ssize_t dk_nentries; + + /* Actual hash table of dk_size entries. It holds indices in dk_entries, + or DKIX_EMPTY(-1) or DKIX_DUMMY(-2). + + Indices must be: 0 <= indice < USABLE_FRACTION(dk_size). + + The size in bytes of an indice depends on dk_size: + + - 1 byte if dk_size <= 0xff (char*) + - 2 bytes if dk_size <= 0xffff (int16_t*) + - 4 bytes if dk_size <= 0xffffffff (int32_t*) + - 8 bytes otherwise (int64_t*) + + Dynamically sized, 8 is minimum. */ + union { + int8_t as_1[8]; + int16_t as_2[4]; + int32_t as_4[2]; +#if SIZEOF_VOID_P > 4 + int64_t as_8[1]; +#endif + } dk_indices; + + /* "PyDictKeyEntry dk_entries[dk_usable];" array follows: + see the DK_ENTRIES() macro */ }; #endif |