Rev 2261: Switch to using lists instead of dicts. in http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch
John Arbash Meinel
john at arbash-meinel.com
Tue Jan 30 21:04:11 GMT 2007
At http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch
------------------------------------------------------------
revno: 2261
revision-id: john at arbash-meinel.com-20070130210407-ny0eh3g3fpf2bwnm
parent: john at arbash-meinel.com-20070130203411-hv76deu87n5hu3bb
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: list_patch
timestamp: Tue 2007-01-30 15:04:07 -0600
message:
Switch to using lists instead of dicts.
We were using integer keys anyway, and these seem slightly faster.
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 20:34:11 +0000
+++ b/bzrlib/hybrid_linked_list.py 2007-01-30 21:04:07 +0000
@@ -34,7 +34,6 @@
entries are inserted or removed, the range list is updated, but the content
nodes themselves are never modified.
- :ivar _counter: A counter so that all new ranges get their own handle.
:ivar _head: Pointer to the first range, may be None
:ivar _ranges: The map of ranges. This maps handle => (start, end, content)
:ivar _links: This maps each range to the next range. It could technically
@@ -43,7 +42,7 @@
:ivar _length: The current length of the output content
"""
- __slots__ = ['_counter', '_head', '_ranges', '_links', '_length']
+ __slots__ = ['_head', '_ranges', '_links', '_length']
def __init__(self, starting=[]):
"""Create a new HybridLinkedList.
@@ -54,17 +53,15 @@
def _reset(self, starting):
"""Reset the internal structures to hold a single list."""
- self._counter = -1
-
# This uses 2 maps.
# 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 = None
- self._ranges = {}
+ self._ranges = []
# This is a singly linked list map for range to next range
- self._links = {}
+ self._links = []
self._length = 0
if starting:
@@ -109,19 +106,22 @@
start, end, content) = self._find_nodes_for_pos(cur)
# They requested something out of range
- if content is None:
+ if cur_range_id is None:
return result
+ _links = self._links
+ _ranges = self._ranges
+
offset += start
while cur < stop:
while offset >= end:
# Keep skipping until we find next
offset -= end
- cur_range_id = self._links[cur_range_id]
+ cur_range_id = _links[cur_range_id]
if cur_range_id is None:
content = None
break
- start, end, content = self._ranges[cur_range_id]
+ start, end, content = _ranges[cur_range_id]
offset += start
if content is None:
break
@@ -191,6 +191,8 @@
# 4716 4.8879 bzrlib.hybrid_linked_list:182(_find_nodes_for_pos)
# to
# 4716 3.9053 bzrlib.hybrid_linked_list:176(_find_nodes_for_pos)
+ # and switching to lists instead of dicts
+ # 4716 3.4728 bzrlib.hybrid_linked_list:176(_find_nodes_for_pos)
_ranges = self._ranges
_links = self._links
@@ -202,15 +204,16 @@
prev_range_id = cur_range_id
cur_range_id = _links[cur_range_id]
cur_pos = next_pos
- content = start = end = None
+ #content = start = end = None
return (prev_range_id, cur_range_id, pos - cur_pos,
start, end, content)
def _new_range_id(self, start, end, content):
"""Get a new range id."""
- self._counter += 1
- self._ranges[self._counter] = (start, end, content)
- return self._counter
+ new_range_id = len(self._ranges)
+ self._ranges.append((start, end, content))
+ self._links.append(None)
+ return new_range_id
def insert(self, start, content):
"""Insert a set of entries starting at the first position."""
@@ -312,8 +315,8 @@
self._head = next_range_id
else:
_links[prev_range_id] = next_range_id
- del _links[cur_range_id]
- del _ranges[cur_range_id]
+ _links[cur_range_id] = -1
+ _ranges[cur_range_id] = None
else:
# CASE 2: we save the beginning, but remove the tail
# This only requires a node entry update
@@ -383,9 +386,8 @@
that should be fine.
"""
new_hll = HybridLinkedList()
- new_hll._counter = self._counter
new_hll._head = self._head
- new_hll._ranges = self._ranges.copy()
- new_hll._links = self._links.copy()
+ new_hll._ranges = self._ranges[:]
+ new_hll._links = self._links[:]
new_hll._length = self._length
return new_hll
=== modified file 'bzrlib/tests/test_hybrid_linked_list.py'
--- a/bzrlib/tests/test_hybrid_linked_list.py 2007-01-30 19:05:06 +0000
+++ b/bzrlib/tests/test_hybrid_linked_list.py 2007-01-30 21:04:07 +0000
@@ -183,14 +183,13 @@
hll = self.get_sectioned_hll()
self.assertEqual(9, len(hll))
self.assertEqual([0, 1, 2, 3, 4, 5, 6, 7, 8], hll)
- self.assertEqual(3, hll._counter)
self.assertEqual(0, hll._head)
- self.assertEqual({0:1, 1:2, 2:3, 3:None}, hll._links)
- self.assertEqual({0:(0, 3, [0, 1, 2]),
- 1:(0, 2, [3, 4]),
- 2:(0, 3, [5, 6, 7]),
- 3:(0, 1, [8]),
- }, hll._ranges)
+ self.assertEqual([1, 2, 3, None], hll._links)
+ self.assertEqual([(0, 3, [0, 1, 2]),
+ (0, 2, [3, 4]),
+ (0, 3, [5, 6, 7]),
+ (0, 1, [8]),
+ ], hll._ranges)
def test_copy(self):
hll = hybrid_linked_list.HybridLinkedList([0, 1, 2])
@@ -202,13 +201,16 @@
self.assertEqual([0, 1, 2, 3, 4, 5], hll2)
# After copying, the contents should be identical
- self.assertEqual(hll._counter, hll2._counter)
self.assertEqual(hll._head, hll2._head)
self.assertEqual(hll._ranges, hll2._ranges)
self.assertEqual(hll._links, hll2._links)
# The content entries should be identical items, but the rest are not
- for range_id, (start, end, content) in hll._ranges.iteritems():
+ for range_id, value in enumerate(hll._ranges):
+ if value is not None:
+ start, end, content = value
+ else:
+ continue
start2, end2, content2 = hll2._ranges[range_id]
self.assertEqual(id(content), id(content2))
@@ -235,77 +237,74 @@
hll = self.get_sectioned_hll()
hll.delete(0, 3)
self.assertEqual([3, 4, 5, 6, 7, 8], hll)
- self.assertEqual(3, hll._counter)
self.assertEqual(1, hll._head)
- self.assertEqual({1:2, 2:3, 3:None}, hll._links)
- self.assertEqual({1:(0, 2, [3, 4]),
- 2:(0, 3, [5, 6, 7]),
- 3:(0, 1, [8]),
- }, hll._ranges)
+ self.assertEqual([-1, 2, 3, None], hll._links)
+ self.assertEqual([None,
+ (0, 2, [3, 4]),
+ (0, 3, [5, 6, 7]),
+ (0, 1, [8]),
+ ], hll._ranges)
def test_delete_middle_range(self):
hll = self.get_sectioned_hll()
hll.delete(3, 5)
self.assertEqual([0, 1, 2, 5, 6, 7, 8], hll)
- self.assertEqual(3, hll._counter)
self.assertEqual(0, hll._head)
- self.assertEqual({0:2, 2:3, 3:None}, hll._links)
- self.assertEqual({0:(0, 3, [0, 1, 2]),
- 2:(0, 3, [5, 6, 7]),
- 3:(0, 1, [8]),
- }, hll._ranges)
+ self.assertEqual([2, -1, 3, None], hll._links)
+ self.assertEqual([(0, 3, [0, 1, 2]),
+ None,
+ (0, 3, [5, 6, 7]),
+ (0, 1, [8]),
+ ], hll._ranges)
def test_delete_last_range(self):
hll = self.get_sectioned_hll()
hll.delete(8, 9)
self.assertEqual([0, 1, 2, 3, 4, 5, 6, 7], hll)
- self.assertEqual(3, hll._counter)
self.assertEqual(0, hll._head)
- self.assertEqual({0:1, 1:2, 2:None}, hll._links)
- self.assertEqual({0:(0, 3, [0, 1, 2]),
- 1:(0, 2, [3, 4]),
- 2:(0, 3, [5, 6, 7]),
- }, hll._ranges)
+ self.assertEqual([1, 2, None, -1], hll._links)
+ self.assertEqual([(0, 3, [0, 1, 2]),
+ (0, 2, [3, 4]),
+ (0, 3, [5, 6, 7]),
+ None,
+ ], hll._ranges)
def test_delete_partial_beginning(self):
hll = self.get_sectioned_hll()
hll.delete(0, 2)
self.assertEqual([2, 3, 4, 5, 6, 7, 8], hll)
- self.assertEqual(3, hll._counter)
self.assertEqual(0, hll._head)
- self.assertEqual({0:1, 1:2, 2:3, 3:None}, hll._links)
- self.assertEqual({0:(2, 3, [0, 1, 2]),
- 1:(0, 2, [3, 4]),
- 2:(0, 3, [5, 6, 7]),
- 3:(0, 1, [8]),
- }, hll._ranges)
+ self.assertEqual([1, 2, 3, None], hll._links)
+ self.assertEqual([(2, 3, [0, 1, 2]),
+ (0, 2, [3, 4]),
+ (0, 3, [5, 6, 7]),
+ (0, 1, [8]),
+ ], hll._ranges)
def test_delete_partial_ending(self):
hll = self.get_sectioned_hll()
hll.delete(1, 3)
self.assertEqual([0, 3, 4, 5, 6, 7, 8], hll)
- self.assertEqual(3, hll._counter)
self.assertEqual(0, hll._head)
- self.assertEqual({0:1, 1:2, 2:3, 3:None}, hll._links)
- self.assertEqual({0:(0, 1, [0, 1, 2]),
- 1:(0, 2, [3, 4]),
- 2:(0, 3, [5, 6, 7]),
- 3:(0, 1, [8]),
- }, hll._ranges)
+ self.assertEqual([1, 2, 3, None], hll._links)
+ self.assertEqual([(0, 1, [0, 1, 2]),
+ (0, 2, [3, 4]),
+ (0, 3, [5, 6, 7]),
+ (0, 1, [8]),
+ ], hll._ranges)
def test_delete_middle_section(self):
hll = self.get_sectioned_hll()
hll.delete(1, 2)
self.assertEqual([0, 2, 3, 4, 5, 6, 7, 8], hll)
- self.assertEqual(4, hll._counter)
self.assertEqual(0, hll._head)
- self.assertEqual({0:4, 1:2, 2:3, 3:None, 4:1}, hll._links)
- self.assertEqual({0:(0, 1, [0, 1, 2]),
- 1:(0, 2, [3, 4]),
- 2:(0, 3, [5, 6, 7]),
- 3:(0, 1, [8]),
- 4:(2, 3, [0, 1, 2]),
- }, hll._ranges)
+ self.assertEqual([4, 2, 3, None, 1], hll._links)
+ self.assertEqual([(0, 1, [0, 1, 2]),
+ (0, 2, [3, 4]),
+ (0, 3, [5, 6, 7]),
+ (0, 1, [8]),
+ (2, 3, [0, 1, 2]),
+ ], hll._ranges)
# Make sure that even though we have 2 entries with the same content,
# it just copied a reference, not the actual content.
self.assertEqual(id(hll._ranges[0][2]), id(hll._ranges[4][2]))
@@ -314,45 +313,45 @@
hll = self.get_sectioned_hll()
hll.delete(3, 4)
self.assertEqual([0, 1, 2, 4, 5, 6, 7, 8], hll)
- self.assertEqual(3, hll._counter)
self.assertEqual(0, hll._head)
- self.assertEqual({0:1, 1:2, 2:3, 3:None}, hll._links)
- self.assertEqual({0:(0, 3, [0, 1, 2]),
- 1:(1, 2, [3, 4]),
- 2:(0, 3, [5, 6, 7]),
- 3:(0, 1, [8]),
- }, hll._ranges)
+ self.assertEqual([1, 2, 3, None], hll._links)
+ self.assertEqual([(0, 3, [0, 1, 2]),
+ (1, 2, [3, 4]),
+ (0, 3, [5, 6, 7]),
+ (0, 1, [8]),
+ ], hll._ranges)
def test_delete_across_sections(self):
hll = self.get_sectioned_hll()
hll.delete(1, 7)
self.assertEqual([0, 7, 8], hll)
- self.assertEqual(3, hll._counter)
self.assertEqual(0, hll._head)
- self.assertEqual({0:2, 2:3, 3:None}, hll._links)
- self.assertEqual({0:(0, 1, [0, 1, 2]),
- 2:(2, 3, [5, 6, 7]),
- 3:(0, 1, [8]),
- }, hll._ranges)
+ self.assertEqual([2, -1, 3, None], hll._links)
+ self.assertEqual([(0, 1, [0, 1, 2]),
+ None,
+ (2, 3, [5, 6, 7]),
+ (0, 1, [8]),
+ ], hll._ranges)
def test_delete_off_end(self):
hll = self.get_sectioned_hll()
hll.delete(1, 9)
self.assertEqual([0], hll)
- self.assertEqual(3, hll._counter)
self.assertEqual(0, hll._head)
- self.assertEqual({0:None}, hll._links)
- self.assertEqual({0:(0, 1, [0, 1, 2]),
- }, hll._ranges)
+ self.assertEqual([None, -1, -1, -1], hll._links)
+ self.assertEqual([(0, 1, [0, 1, 2]),
+ None,
+ None,
+ None,
+ ], hll._ranges)
def test_delete_all(self):
hll = self.get_sectioned_hll()
hll.delete(0, 9)
self.assertEqual([], hll)
- self.assertEqual(3, hll._counter)
self.assertEqual(None, hll._head)
- self.assertEqual({}, hll._links)
- self.assertEqual({}, hll._ranges)
+ self.assertEqual([-1, -1, -1, -1], hll._links)
+ self.assertEqual([None, None, None, None], hll._ranges)
hll.insert(0, [1])
self.assertEqual([1], hll)
More information about the bazaar-commits
mailing list