From a2ed8a2a17f6f2b71e1ee493d0a653427fd08161 Mon Sep 17 00:00:00 2001 From: Yury Selivanov Date: Sun, 22 May 2022 08:35:54 -0700 Subject: Add an explaining comment for _Py_HAMT_MAX_TREE_DEPTH --- immutables/_map.h | 11 +++++++++++ 1 file changed, 11 insertions(+) diff --git a/immutables/_map.h b/immutables/_map.h index 28142ce..37b02a4 100644 --- a/immutables/_map.h +++ b/immutables/_map.h @@ -4,6 +4,17 @@ #include #include "Python.h" +/* +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 `_map.c`. + +This constant is used to define a datastucture for storing iteration state. +*/ #define _Py_HAMT_MAX_TREE_DEPTH 8 -- cgit v1.2.3