Rev 2897: * Pack indices are now partially parsed for specific key lookup using a in http://people.ubuntu.com/~robertc/baz2.0/index

[Robert Collins]

At http://people.ubuntu.com/~robertc/baz2.0/index

------------------------------------------------------------
revno: 2897
revision-id: robertc at robertcollins.net-20071007225955-8ibbi8frtdrjt58q
parent: robertc at robertcollins.net-20071007225205-4ttygs5100xl33ac
committer: Robert Collins <robertc at robertcollins.net>
branch nick: index
timestamp: Mon 2007-10-08 08:59:55 +1000
message:
  * Pack indices are now partially parsed for specific key lookup using a
    bisection approach. (Robert Collins)
modified:
  NEWS                           NEWS-20050323055033-4e00b5db738777ff
  bzrlib/index.py                index.py-20070712131115-lolkarso50vjr64s-1
  bzrlib/tests/test_index.py     test_index.py-20070712131115-lolkarso50vjr64s-2
=== modified file 'NEWS'
--- a/NEWS	2007-10-05 10:45:11 +0000
+++ b/NEWS	2007-10-07 22:59:55 +0000
@@ -51,6 +51,9 @@
    * Inventory serialisation no longer double-sha's the content.
      (Robert Collins)
 
+   * Pack indices are now partially parsed for specific key lookup using a
+     bisection approach. (Robert Collins)
+
    * Partial commits are now approximately 40% faster by walking over the
      unselected current tree more efficiently. (Robert Collins)
 

=== modified file 'bzrlib/index.py'
--- a/bzrlib/index.py	2007-10-07 22:52:05 +0000
+++ b/bzrlib/index.py	2007-10-07 22:59:55 +0000
@@ -31,6 +31,7 @@
 from bzrlib.lazy_import import lazy_import
 lazy_import(globals(), """
 from bzrlib import trace
+from bzrlib.bisect_multi import bisect_multi_bytes
 from bzrlib.trace import mutter
 """)
 from bzrlib import debug, errors
@@ -420,19 +421,8 @@
         start, end = self._parsed_byte_map[index]
         return offset >= start and offset < end
 
-    def iter_entries(self, keys):
-        """Iterate over keys within the index.
-
-        :param keys: An iterable providing the keys to be retrieved.
-        :return: An iterable as per iter_all_entries, but restricted to the
-            keys supplied. No additional keys will be returned, and every
-            key supplied that is in the index will be returned.
-        """
-        keys = set(keys)
-        if not keys:
-            return
-        if self._nodes is None:
-            self._buffer_all()
+    def _iter_entries_from_total_buffer(self, keys):
+        """Iterate over keys when the entire index is parsed."""
         keys = keys.intersection(self._keys)
         if self.node_ref_lists:
             for key in keys:
@@ -442,6 +432,23 @@
             for key in keys:
                 yield self, key, self._nodes[key]
 
+    def iter_entries(self, keys):
+        """Iterate over keys within the index.
+
+        :param keys: An iterable providing the keys to be retrieved.
+        :return: An iterable as per iter_all_entries, but restricted to the
+            keys supplied. No additional keys will be returned, and every
+            key supplied that is in the index will be returned.
+        """
+        keys = set(keys)
+        if not keys:
+            return []
+        if self._nodes is not None:
+            return self._iter_entries_from_total_buffer(keys)
+        else:
+            return (result[1] for result in bisect_multi_bytes(
+                self.lookup_keys_via_location, self._size, keys))
+
     def iter_entries_prefix(self, keys):
         """Iterate over keys within the index using prefix matching.
 

=== modified file 'bzrlib/tests/test_index.py'
--- a/bzrlib/tests/test_index.py	2007-10-07 22:52:05 +0000
+++ b/bzrlib/tests/test_index.py	2007-10-07 22:59:55 +0000
@@ -583,7 +583,6 @@
         self.assertEqual([('readv', 'index', [(11976, 800)], True, 15813)],
             index._transport._activity)
 
-
     def test_iter_all_entries_empty(self):
         index = self.make_index()
         self.assertEqual([], list(index.iter_all_entries()))