diff options
| author | Miss Islington (bot) <31488909+miss-islington@users.noreply.github.com> | 2022-05-24 08:52:29 (GMT) |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2022-05-24 08:52:29 (GMT) |
| commit | a4bea26ee4da780b399eab8f9f7eaa1517f52d56 (patch) | |
| tree | 5922b5637d21929d49301d179587a201dd78b1b7 /Include/internal | |
| parent | c1b12495f67be5eca2692532de14e81a93025e6a (diff) | |
| download | cpython-a4bea26ee4da780b399eab8f9f7eaa1517f52d56.zip cpython-a4bea26ee4da780b399eab8f9f7eaa1517f52d56.tar.gz cpython-a4bea26ee4da780b399eab8f9f7eaa1517f52d56.tar.bz2 | |
gh-93065: Fix HAMT to iterate correctly over 7-level deep trees (GH-93066) (GH-93146)
Also while there, clarify a few things about why we reduce the hash to 32 bits.
Co-authored-by: Eli Libman <eli@hyro.ai>
Co-authored-by: Yury Selivanov <yury@edgedb.com>
Co-authored-by: Łukasz Langa <lukasz@langa.pl>
(cherry picked from commit c1f5c903a7e4ed27190488f4e33b00d3c3d952e5)
Diffstat (limited to 'Include/internal')
| -rw-r--r-- | Include/internal/pycore_hamt.h | 14 |
1 files changed, 13 insertions, 1 deletions
diff --git a/Include/internal/pycore_hamt.h b/Include/internal/pycore_hamt.h index aaf6559..357d966 100644 --- a/Include/internal/pycore_hamt.h +++ b/Include/internal/pycore_hamt.h @@ -5,7 +5,19 @@ # error "this header requires Py_BUILD_CORE define" #endif -#define _Py_HAMT_MAX_TREE_DEPTH 7 + +/* +HAMT tree is shaped by hashes of keys. Every group of 5 bits of a hash denotes +the exact position of the key in one level of the tree. Since we're using +32 bit hashes, we can have at most 7 such levels. Although if there are +two distinct keys with equal hashes, they will have to occupy the same +cell in the 7th level of the tree -- so we'd put them in a "collision" node. +Which brings the total possible tree depth to 8. Read more about the actual +layout of the HAMT tree in `hamt.c`. + +This constant is used to define a datastucture for storing iteration state. +*/ +#define _Py_HAMT_MAX_TREE_DEPTH 8 #define PyHamt_Check(o) Py_IS_TYPE(o, &_PyHamt_Type) |