diff options
| author | Łukasz Langa <lukasz@langa.pl> | 2022-05-24 09:26:25 (GMT) |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2022-05-24 09:26:25 (GMT) |
| commit | 6d4927ad1383e8bb8bda6659d24b6d05094a7b99 (patch) | |
| tree | 5d9c5cdf0653ca6220916feda723bcec5f622683 /Include/internal | |
| parent | 69cf0203ab47692efbc261c028e15e0d7a245c57 (diff) | |
| download | cpython-6d4927ad1383e8bb8bda6659d24b6d05094a7b99.zip cpython-6d4927ad1383e8bb8bda6659d24b6d05094a7b99.tar.gz cpython-6d4927ad1383e8bb8bda6659d24b6d05094a7b99.tar.bz2 | |
[3.8] gh-93065: Fix HAMT to iterate correctly over 7-level deep trees (GH-93066) (#93148)
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 e65aef5..ff9cc24 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_TYPE(o) == &_PyHamt_Type) |