Rev 2250: Don't move the prev_range_id if we are completely removing the current node. in http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch

John Arbash Meinel john at arbash-meinel.com
Tue Jan 30 03:50:45 GMT 2007


At http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch

------------------------------------------------------------
revno: 2250
revision-id: john at arbash-meinel.com-20070130035040-sd7e63bpxs1xw4n6
parent: john at arbash-meinel.com-20070130030128-fh616n0n3kmerab2
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: list_patch
timestamp: Mon 2007-01-29 21:50:40 -0600
message:
  Don't move the prev_range_id if we are completely removing the current node.
modified:
  bzrlib/hybrid_linked_list.py   hybrid_linked_list.p-20070130001028-zlexwz74tzo56o2t-1
  bzrlib/tests/test_hybrid_linked_list.py test_hybrid_linked_l-20070130001028-zlexwz74tzo56o2t-2
-------------- next part --------------
=== modified file 'bzrlib/hybrid_linked_list.py'
--- a/bzrlib/hybrid_linked_list.py	2007-01-30 03:01:28 +0000
+++ b/bzrlib/hybrid_linked_list.py	2007-01-30 03:50:40 +0000
@@ -28,14 +28,17 @@
     node stores a pointer to the other nodes. However, this is inefficient at
     random access, because you have to iterate over all of the nodes.
 
-    This class attempts to create a hybrid between them. Which creates nodes
-    during insert, update, delete, but generally stores things as arrays.
-
-    The current structure is optimized for being able to modify small sections
-    at a time. But not really move hunks around. (so you can remove a few
-    lines, and add a few lines, but not really move lines around).
+    This class creates an linked-list of ranges into a set of content maps. As
+    entries are inserted or removed, the range list is updated, but the content
+    nodes themselves are never modified.
     """
 
+    # TODO: jam 20060129 Right now this class holds onto all content, even
+    #       after it is no longer being referenced. This is mostly because of
+    #       the internal content_id => content mapping.
+    #       It should actually be possible to use a reference to the content
+    #       directly, though it makes testing a little bit clumsier.
+
     def __init__(self, starting=[]):
         """Create a new HybridLinkedList.
 
@@ -45,21 +48,24 @@
 
     def _reset(self, starting):
         """Reset the internal structures to hold a single list."""
-        self._data_counter = 0
-        self._ranges_counter = 0
+        self._data_counter = -1
+        self._ranges_counter = -1
 
         # This uses 3 maps.
         # one map is just from simple id => content
-        self._content_map = {0:starting}
+        self._content_map = {}
 
         # This is a map from range_id => (content_node_id, start, end)
         # This allows us to avoid doing any work on the supplied content.
         # Instead, we just keep updating the information about what content
         # should be extracted at the right time
-        self._head = 0
-        self._range_map = {self._head:(0, 0, len(starting))}
+        self._head = None
+        self._range_map = {}
         # This is a singly linked list map for range to next range
-        self._links = {0:None}
+        self._links = {}
+
+        if starting:
+            self.insert(0, starting)
 
     def __iter__(self):
         """Iterate over the final content."""
@@ -231,12 +237,12 @@
                     # This only requires a node entry update
                     self._range_map[cur_range_id] = (content_id, cur_start,
                                                      cur_start + offset)
+                    prev_range_id = cur_range_id
                 remove_length -= possible_remove_length
                 if remove_length == 0:
                     break
                 # step to next
                 offset = 0
-                prev_range_id = cur_range_id
                 cur_range_id = next_range_id
                 content_id, cur_start, cur_end = self._range_map[next_range_id]
             else:

=== modified file 'bzrlib/tests/test_hybrid_linked_list.py'
--- a/bzrlib/tests/test_hybrid_linked_list.py	2007-01-30 03:01:28 +0000
+++ b/bzrlib/tests/test_hybrid_linked_list.py	2007-01-30 03:50:40 +0000
@@ -35,35 +35,27 @@
         self.assertEqual([], list(hll))
 
     def test__find_nodes_for_pos(self):
-        hll = hybrid_linked_list.HybridLinkedList([])
-        hll._range_map = {0:(0, 0, 2),
-                          1:(0, 3, 6),
-                          2:(0, 6, 7),
-                         }
-        hll._links = {0:1, 1:2, 2:None}
-        hll._content_map = {0:[0, 1, 2, 3, 4, 5, 6, 7, 8]}
-        self.assertEqual([0, 1, 3, 4, 5, 6], list(hll))
+        hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4, 5, 6, 7, 8])
+        hll.delete(2, 3)
+        hll.delete(5, 7)
+        self.assertEqual([0, 1, 3, 4, 5, 8], list(hll))
         self.assertEqual((None, 0, 0, 0, 0, 2), hll._find_nodes_for_pos(0))
         self.assertEqual((None, 0, 1, 0, 0, 2), hll._find_nodes_for_pos(1))
         self.assertEqual((0, 1, 0, 0, 3, 6), hll._find_nodes_for_pos(2))
         self.assertEqual((0, 1, 1, 0, 3, 6), hll._find_nodes_for_pos(3))
         self.assertEqual((0, 1, 2, 0, 3, 6), hll._find_nodes_for_pos(4))
-        self.assertEqual((1, 2, 0, 0, 6, 7), hll._find_nodes_for_pos(5))
+        self.assertEqual((1, 2, 0, 0, 8, 9), hll._find_nodes_for_pos(5))
         self.assertEqual((2, None, 0, None, None, None),
                          hll._find_nodes_for_pos(6))
         self.assertEqual((2, None, 1, None, None, None),
                          hll._find_nodes_for_pos(7))
 
     def test__getitem__(self):
-        hll = hybrid_linked_list.HybridLinkedList([])
-        hll._range_map = {0:(0, 0, 2),
-                          1:(0, 3, 6),
-                          2:(0, 6, 7),
-                         }
-        hll._links = {0:1, 1:2, 2:None}
-        hll._content_map = {0:[0, 1, 2, 3, 4, 5, 6, 7, 8]}
-        self.assertEqual([0, 1, 3, 4, 5, 6], list(hll))
-        for expected, pos in zip([0, 1, 3, 4, 5, 6], xrange(0,5)):
+        hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4, 5, 6, 7, 8])
+        hll.delete(2, 3)
+        hll.delete(5, 7)
+        self.assertEqual([0, 1, 3, 4, 5, 8], list(hll))
+        for expected, pos in zip([0, 1, 3, 4, 5, 8], xrange(0,5)):
             self.assertEqual(expected, hll[pos])
 
     def test_insert(self):
@@ -197,6 +189,27 @@
         self.assertEqual({0:(0, 0, 1), 2:(2, 2, 3), 3:(3, 0, 1)},
                          hll._range_map)
 
+    def test_delete_off_end(self):
+        hll = self.get_sectioned_hll()
+        hll.delete(1, 9)
+        self.assertEqual([0], list(hll))
+        self.assertEqual(3, hll._ranges_counter)
+        self.assertEqual(0, hll._head)
+        self.assertEqual({0:None}, hll._links)
+        self.assertEqual({0:(0, 0, 1)}, hll._range_map)
+
+    def test_delete_all(self):
+        hll = self.get_sectioned_hll()
+        hll.delete(0, 9)
+        self.assertEqual([], list(hll))
+        self.assertEqual(3, hll._ranges_counter)
+        self.assertEqual(None, hll._head)
+        self.assertEqual({}, hll._links)
+        self.assertEqual({}, hll._range_map)
+
+        hll.insert(0, [1])
+        self.assertEqual([1], list(hll))
+
     def test_replace_insert_beginning(self):
         """Test replacing when we are purely inserting."""
         hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])



More information about the bazaar-commits mailing list