Rev 25: Make sure we find the right nodes, even if the keys are randomly permutated. in http://bzr.arbash-meinel.com/plugins/index2

[John Arbash Meinel]

At http://bzr.arbash-meinel.com/plugins/index2

------------------------------------------------------------
revno: 25
revision-id: john at arbash-meinel.com-20080702182656-cudnvqe2kfstxits
parent: john at arbash-meinel.com-20080702181746-xlca6kf0iusfmxsy
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: index2
timestamp: Wed 2008-07-02 13:26:56 -0500
message:
  Make sure we find the right nodes, even if the keys are randomly permutated.
-------------- next part --------------
=== modified file 'btree_index.py'
--- a/btree_index.py	2008-07-02 18:17:46 +0000
+++ b/btree_index.py	2008-07-02 18:26:56 +0000
@@ -566,8 +566,10 @@
         # in sorted order anyway. Though we could filter at the bloom level
         # without sorting. *But* is the top level bloom going to restrict
         # enough keys that we care?
-        # keys = sorted(keys)
-        keys = frozenset(keys)
+        if self._use_blooms:
+            keys = frozenset(keys)
+        else:
+            keys = sorted(keys)
         if not keys:
             return
         if not self.key_count():
@@ -598,8 +600,6 @@
                         sub_keys = sorted(remaining_sub_keys)
                     else:
                         sub_keys = remaining_sub_keys
-                if isinstance(sub_keys, frozenset):
-                    sub_keys = sorted(sub_keys)
                 positions = self._multi_bisect_right(sub_keys, node.keys)
                 node_offset = row_offset + node.offset
                 next_nodes_and_keys.extend([(node_offset + pos, s_keys)

=== modified file 'tests/test_btree_index.py'
--- a/tests/test_btree_index.py	2008-07-02 18:17:46 +0000
+++ b/tests/test_btree_index.py	2008-07-02 18:26:56 +0000
@@ -17,6 +17,7 @@
 
 """Tests for btree indices."""
 
+import random
 import zlib
 
 from bzrlib import tests
@@ -495,7 +496,7 @@
 
     def test_iter_entries_w_blooms_finds_correct_nodes(self):
         builder = btree_index.BTreeBuilder(key_elements=1)
-        nodes = self.make_nodes(1200, 1, 0)
+        nodes = self.make_nodes(25000, 1, 0)
         for node in nodes:
             builder.add_node(*node)
         transport = get_transport('trace+' + self.get_url(''))
@@ -504,9 +505,10 @@
         index = btree_index.BTreeGraphIndex(transport, 'index', size)
         del transport._activity[:]
         index._use_blooms = True
-        # Search for every 100th key, to make sure the blooms are correct
-        search_nodes = nodes[::100]
+        # Search for every 1000th key, to make sure the blooms are correct
+        search_nodes = nodes[::1000]
         search_keys = [n[0] for n in search_nodes]
+        random.shuffle(search_keys)
         # We expect (key, value) tuples from the search result
         expected_result = sorted([n[:2] for n in search_nodes])
         # Ignore the index object
@@ -515,6 +517,13 @@
         if expected_result != sorted_result:
             self.assertEqualDiff(pprint.pformat(expected_result),
                                  pprint.pformat(sorted_result))
+        index = btree_index.BTreeGraphIndex(transport, 'index', size)
+        index._use_blooms = False
+        found_nodes = [n[1:] for n in index.iter_entries(search_keys)]
+        sorted_result = sorted(found_nodes)
+        if expected_result != sorted_result:
+            self.assertEqualDiff(pprint.pformat(expected_result),
+                                 pprint.pformat(sorted_result))
 
 
 class TestBTreeNodes(BTreeTestCase):