(original) (raw)

changeset: 103346:378e000a6878 user: Victor Stinner victor.stinner@gmail.com date: Thu Sep 08 12:01:25 2016 -0700 files: Include/dictobject.h Objects/dict-common.h Objects/dictobject.c description: Add documentation to the dict implementation Issue #27350. diff -r fc8aaa073eb4 -r 378e000a6878 Include/dictobject.h --- a/Include/dictobject.h Thu Sep 08 11:37:36 2016 -0700 +++ b/Include/dictobject.h Thu Sep 08 12:01:25 2016 -0700 @@ -22,8 +22,17 @@ */ typedef struct { PyObject_HEAD + + /* Number of items in the dictionary */ Py_ssize_t ma_used; + PyDictKeysObject *ma_keys; + + /* If ma_values is NULL, the table is "combined": keys and values + are stored in ma_keys (and ma_keys->dk_refcnt == 1). + + If ma_values is not NULL, the table is splitted: + keys are stored in ma_keys and values are stored in ma_values */ PyObject **ma_values; } PyDictObject; diff -r fc8aaa073eb4 -r 378e000a6878 Objects/dict-common.h --- a/Objects/dict-common.h Thu Sep 08 11:37:36 2016 -0700 +++ b/Objects/dict-common.h Thu Sep 08 12:01:25 2016 -0700 @@ -22,11 +22,50 @@ /* 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 value. + + - lookdict_split(): Version of lookdict() for split tables. */ dict_lookup_func dk_lookup; + + /* Number of usable entries in dk_entries. + 0 <= dk_usable <= USABLE_FRACTION(dk_size) */ Py_ssize_t dk_usable; - Py_ssize_t dk_nentries; /* How many entries are used. */ - char dk_indices[8]; /* dynamically sized. 8 is minimum. */ + + /* Number of used entries in dk_entries. + 0 <= dk_nentries < dk_size */ + 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 (Py_ssize_t*) + + Dynamically sized, 8 is minimum. */ + char dk_indices[8]; + + /* "PyDictKeyEntry dk_entries[dk_usable];" array follows: + see the DK_ENTRIES() macro */ }; #endif diff -r fc8aaa073eb4 -r 378e000a6878 Objects/dictobject.c --- a/Objects/dictobject.c Thu Sep 08 11:37:36 2016 -0700 +++ b/Objects/dictobject.c Thu Sep 08 12:01:25 2016 -0700 @@ -593,7 +593,7 @@ Christian Tismer. lookdict() is general-purpose, and may return DKIX_ERROR if (and only if) a -comparison raises an exception (this was new in Python 2.5). +comparison raises an exception. lookdict_unicode() below is specialized to string keys, comparison of which can never raise an exception; that function can never return DKIX_ERROR. lookdict_unicode_nodummy is further specialized for string keys that cannot be/victor.stinner@gmail.com