diff options
| author | Yury Selivanov <yury@edgedb.com> | 2022-05-21 21:47:35 -0700 |
|---|---|---|
| committer | Yury Selivanov <yury@edgedb.com> | 2022-05-21 23:21:55 -0700 |
| commit | 37b52b7f9bcb9bb7353637563f24f18193b6c5d3 (patch) | |
| tree | 13f5a74adb452046d5d55670047b352d348c122a | |
| parent | 71ecba537df21ae1ba907fc00937f6bf77c045a8 (diff) | |
| download | immutables-37b52b7f9bcb9bb7353637563f24f18193b6c5d3.tar.gz immutables-37b52b7f9bcb9bb7353637563f24f18193b6c5d3.zip | |
Fix iteration when the tree is 7 levels deep + collisions
Fixes issue #84.
Co-authored-by: eli <eli@hyro.ai>
| -rw-r--r-- | immutables/_map.h | 2 | ||||
| -rw-r--r-- | tests/test_map.py | 34 |
2 files changed, 35 insertions, 1 deletions
diff --git a/immutables/_map.h b/immutables/_map.h index dd12af9..28142ce 100644 --- a/immutables/_map.h +++ b/immutables/_map.h @@ -4,7 +4,7 @@ #include <stdint.h> #include "Python.h" -#define _Py_HAMT_MAX_TREE_DEPTH 7 +#define _Py_HAMT_MAX_TREE_DEPTH 8 #define Map_Check(o) (Py_TYPE(o) == &_Map_Type) diff --git a/tests/test_map.py b/tests/test_map.py index 9fffd8c..4640029 100644 --- a/tests/test_map.py +++ b/tests/test_map.py @@ -254,6 +254,40 @@ class BaseMapTest: self.assertEqual(len(h), 0) self.assertEqual(list(h.items()), []) + def test_map_collision_3(self): + # Test that iteration works with the deepest tree possible. + + C = HashKey(0b10000000_00000000_00000000_00000000, 'C') + D = HashKey(0b10000000_00000000_00000000_00000000, 'D') + + E = HashKey(0b00000000_00000000_00000000_00000000, 'E') + + h = self.Map() + h = h.set(C, 'C') + h = h.set(D, 'D') + h = h.set(E, 'E') + + # BitmapNode(size=2 count=1 bitmap=0b1): + # NULL: + # BitmapNode(size=2 count=1 bitmap=0b1): + # NULL: + # BitmapNode(size=2 count=1 bitmap=0b1): + # NULL: + # BitmapNode(size=2 count=1 bitmap=0b1): + # NULL: + # BitmapNode(size=2 count=1 bitmap=0b1): + # NULL: + # BitmapNode(size=2 count=1 bitmap=0b1): + # NULL: + # BitmapNode(size=4 count=2 bitmap=0b101): + # <Key name:E hash:0>: 'E' + # NULL: + # CollisionNode(size=4 id=0x107a24520): + # <Key name:C hash:2147483648>: 'C' + # <Key name:D hash:2147483648>: 'D' + + self.assertEqual({k.name for k in h.keys()}, {'C', 'D', 'E'}) + def test_map_stress_02(self): COLLECTION_SIZE = 20000 TEST_ITERS_EVERY = 647 |