diff options
| author | Yury Selivanov <yury@edgedb.com> | 2022-05-22 08:35:54 -0700 |
|---|---|---|
| committer | Yury Selivanov <yury@edgedb.com> | 2022-05-22 08:35:54 -0700 |
| commit | a2ed8a2a17f6f2b71e1ee493d0a653427fd08161 (patch) | |
| tree | 5556f9df86dcbc11bbda6f9ec91f75601fcd607e | |
| parent | 2aa4cd62148bee94753b89a4c1a8b749c697312a (diff) | |
| download | immutables-a2ed8a2a17f6f2b71e1ee493d0a653427fd08161.tar.gz immutables-a2ed8a2a17f6f2b71e1ee493d0a653427fd08161.zip | |
| -rw-r--r-- | immutables/_map.h | 11 |
1 files changed, 11 insertions, 0 deletions
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 <stdint.h> #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 |