diff options
| -rw-r--r-- | .gitignore | 2 | ||||
| -rw-r--r-- | immutables/map.py | 27 | ||||
| -rw-r--r-- | tests/test_map.py | 108 |
3 files changed, 125 insertions, 12 deletions
@@ -17,3 +17,5 @@ __pycache__/ /dist /.cache /.pytest_cache +/.coverage + diff --git a/immutables/map.py b/immutables/map.py index 9f9554c..a7171b6 100644 --- a/immutables/map.py +++ b/immutables/map.py @@ -3,6 +3,15 @@ import reprlib import sys +__all__ = ('Map',) + + +# Python version of _map.c. The topmost comment there explains +# all datastructures and algorithms. +# The code here follows C code closely on purpose to make +# debugging and testing easier. + + def map_hash(o): x = hash(o) return (x & 0xffffffff) ^ ((x >> 32) & 0xffffffff) @@ -141,7 +150,7 @@ class BitmapNode: res, sub_node = val_or_node.without(shift + 5, hash, key) if res is W_EMPTY: - raise RuntimeError('unreachable code') + raise RuntimeError('unreachable code') # pragma: no cover elif res is W_NEWNODE: if (type(sub_node) is BitmapNode and @@ -162,6 +171,9 @@ class BitmapNode: else: if key == key_or_null: + if self.size == 2: + return W_EMPTY, None + new_array = self.array[:key_idx] new_array.extend(self.array[val_idx + 1:]) new_node = BitmapNode( @@ -201,7 +213,7 @@ class BitmapNode: else: yield key_or_null, val_or_node - def dump(self, buf, level): + def dump(self, buf, level): # pragma: no cover buf.append( ' ' * (level + 1) + 'BitmapNode(size={} count={} bitmap={} id={:0x}):'.format( @@ -274,7 +286,8 @@ class CollisionNode: new_size = self.size - 2 if new_size == 0: - return W_EMPTY, None + # Shouldn't be ever reachable + return W_EMPTY, None # pragma: no cover if new_size == 2: if key_idx == 0: @@ -303,7 +316,7 @@ class CollisionNode: for i in range(0, self.size, 2): yield self.array[i], self.array[i + 1] - def dump(self, buf, level): + def dump(self, buf, level): # pragma: no cover pad = ' ' * (level + 1) buf.append( pad + 'CollisionNode(size={} id={:0x}):'.format( @@ -445,9 +458,9 @@ class Map: h &= MASK if h > MAX: - h -= MASK + 1 + h -= MASK + 1 # pragma: no cover if h == -1: - h = 590923713 + h = 590923713 # pragma: no cover self.__hash = h return h @@ -460,7 +473,7 @@ class Map: return '<immutables.Map({{{}}}) at 0x{:0x}>'.format( ', '.join(items), id(self)) - def __dump__(self): + def __dump__(self): # pragma: no cover buf = [] self.__root.dump(buf, 0) return '\n'.join(buf) diff --git a/tests/test_map.py b/tests/test_map.py index 7af9513..c64258d 100644 --- a/tests/test_map.py +++ b/tests/test_map.py @@ -194,6 +194,50 @@ class BaseMapTest: self.assertEqual(len(h4), 2) self.assertEqual(len(h5), 3) + def test_map_collision_2(self): + A = HashKey(100, 'A') + B = HashKey(101, 'B') + C = HashKey(0b011000011100000100, 'C') + D = HashKey(0b011000011100000100, 'D') + E = HashKey(0b1011000011100000100, 'E') + + h = self.Map() + h = h.set(A, 'a') + h = h.set(B, 'b') + h = h.set(C, 'c') + h = h.set(D, 'd') + + # BitmapNode(size=6 bitmap=0b100110000): + # NULL: + # BitmapNode(size=4 bitmap=0b1000000000000000000001000): + # <Key name:A hash:100>: 'a' + # NULL: + # CollisionNode(size=4 id=0x108572410): + # <Key name:C hash:100100>: 'c' + # <Key name:D hash:100100>: 'd' + # <Key name:B hash:101>: 'b' + + h = h.set(E, 'e') + + # BitmapNode(size=4 count=2.0 bitmap=0b110000 id=10b8ea5c0): + # None: + # BitmapNode(size=4 count=2.0 + # bitmap=0b1000000000000000000001000 id=10b8ea518): + # <Key name:A hash:100>: 'a' + # None: + # BitmapNode(size=2 count=1.0 bitmap=0b10 + # id=10b8ea4a8): + # None: + # BitmapNode(size=4 count=2.0 + # bitmap=0b100000001000 + # id=10b8ea4e0): + # None: + # CollisionNode(size=4 id=10b8ea470): + # <Key name:C hash:100100>: 'c' + # <Key name:D hash:100100>: 'd' + # <Key name:E hash:362244>: 'e' + # <Key name:B hash:101>: 'b' + def test_map_stress(self): COLLECTION_SIZE = 7000 TEST_ITERS_EVERY = 647 @@ -296,6 +340,7 @@ class BaseMapTest: h = self.Map() h = h.set(A, 'a') + h = h.set(A, 'a') h = h.set(B, 'b') h = h.set(C, 'c') h = h.set(D, 'd') @@ -334,6 +379,7 @@ class BaseMapTest: A = HashKey(100, 'A') B = HashKey(201001, 'B') C = HashKey(101001, 'C') + BLike = HashKey(201001, 'B-like') D = HashKey(103, 'D') E = HashKey(104, 'E') Z = HashKey(-100, 'Z') @@ -347,6 +393,11 @@ class BaseMapTest: h = h.set(D, 'd') h = h.set(E, 'e') + h = h.set(B, 'b') # trigger branch in BitmapNode.assoc + + with self.assertRaises(KeyError): + h.delete(BLike) # trigger branch in BitmapNode.without + orig_len = len(h) # BitmapNode(size=8 bitmap=0b1110010000): @@ -387,11 +438,15 @@ class BaseMapTest: self.assertEqual(len(h), 0) def test_map_delete_3(self): - A = HashKey(100, 'A') - B = HashKey(101, 'B') - C = HashKey(100100, 'C') - D = HashKey(100100, 'D') - E = HashKey(104, 'E') + A = HashKey(0b00000000001100100, 'A') + B = HashKey(0b00000000001100101, 'B') + + C = HashKey(0b11000011100000100, 'C') + D = HashKey(0b11000011100000100, 'D') + X = HashKey(0b01000011100000100, 'Z') + Y = HashKey(0b11000011100000100, 'Y') + + E = HashKey(0b00000000001101000, 'E') h = self.Map() h = h.set(A, 'a') @@ -400,8 +455,15 @@ class BaseMapTest: h = h.set(D, 'd') h = h.set(E, 'e') + h = h.set(C, 'c') # trigger branch in CollisionNode.assoc + orig_len = len(h) + with self.assertRaises(KeyError): + h.delete(X) + with self.assertRaises(KeyError): + h.delete(Y) + # BitmapNode(size=6 bitmap=0b100110000): # NULL: # BitmapNode(size=4 bitmap=0b1000000000000000000001000): @@ -422,6 +484,14 @@ class BaseMapTest: self.assertEqual(h.get(C), 'c') self.assertEqual(h.get(B), 'b') + h2 = h.delete(C) + self.assertEqual(len(h2), orig_len - 3) + + h2 = h.delete(D) + self.assertEqual(len(h2), orig_len - 3) + + self.assertEqual(len(h), orig_len - 2) + def test_map_delete_4(self): A = HashKey(100, 'A') B = HashKey(101, 'B') @@ -516,6 +586,13 @@ class BaseMapTest: h = h.delete(key) self.assertEqual(len(h), 0) + def test_map_delete_6(self): + h = self.Map() + h = h.set(1, 1) + h = h.delete(1) + self.assertEqual(len(h), 0) + self.assertEqual(h, self.Map()) + def test_map_items_1(self): A = HashKey(100, 'A') B = HashKey(201001, 'B') @@ -577,6 +654,24 @@ class BaseMapTest: self.assertEqual(set(list(h.keys())), {A, B, C, D, E, F}) self.assertEqual(set(list(h)), {A, B, C, D, E, F}) + def test_map_values_1(self): + A = HashKey(100, 'A') + B = HashKey(101, 'B') + C = HashKey(100100, 'C') + D = HashKey(100100, 'D') + E = HashKey(100100, 'E') + F = HashKey(110, 'F') + + h = self.Map() + h = h.set(A, 'a') + h = h.set(B, 'b') + h = h.set(C, 'c') + h = h.set(D, 'd') + h = h.set(E, 'e') + h = h.set(F, 'f') + + self.assertEqual(set(list(h.values())), {'a', 'b', 'c', 'd', 'e', 'f'}) + def test_map_items_3(self): h = self.Map() self.assertEqual(len(h.items()), 0) @@ -645,6 +740,9 @@ class BaseMapTest: with self.assertRaisesRegex(ValueError, 'cannot compare'): h1 != h2 + def test_map_eq_3(self): + self.assertNotEqual(self.Map(), 1) + def test_map_gc_1(self): A = HashKey(100, 'A') |