aboutsummaryrefslogtreecommitdiff
path: root/tests
diff options
context:
space:
mode:
authorYury Selivanov <yury@edgedb.com>2022-05-21 21:47:35 -0700
committerYury Selivanov <yury@edgedb.com>2022-05-21 23:21:55 -0700
commit37b52b7f9bcb9bb7353637563f24f18193b6c5d3 (patch)
tree13f5a74adb452046d5d55670047b352d348c122a /tests
parent71ecba537df21ae1ba907fc00937f6bf77c045a8 (diff)
downloadimmutables-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>
Diffstat (limited to 'tests')
-rw-r--r--tests/test_map.py34
1 files changed, 34 insertions, 0 deletions
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