← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_btree_index.py

  • Committer: John Arbash Meinel
  • Date: 2008-10-14 21:35:27 UTC
  • mto: This revision was merged to the branch mainline in revision 3805.
  • Revision ID: john@arbash-meinel.com-20081014213527-4j9uc93aq1qmn43b
Add in a shortcut when we haven't cached much yet.

Document the current algorithm more completely, including the proper
justification for the various steps.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
1032
1032
 
1033
1033
    def make_100_node_index(self):
1034
1034
        index = self.make_index(4096*100, 6)
 
1035
        # Consider we've already made a single request at the middle
1035
1036
        self.prepare_index(index, node_ref_lists=0, key_length=1,
1036
1037
                           key_count=1000, row_lengths=[1, 99],
1037
 
                           cached_keys=[0])
 
1038
                           cached_keys=[0, 50])
1038
1039
        return index
1039
1040
 
1040
1041
    def make_1000_node_index(self):
1041
1042
        index = self.make_index(4096*1000, 6)
 
1043
        # Pretend we've already made a single request in the middle
1042
1044
        self.prepare_index(index, node_ref_lists=0, key_length=1,
1043
1045
                           key_count=90000, row_lengths=[1, 9, 990],
1044
 
                           cached_keys=[0])
 
1046
                           cached_keys=[0, 5, 500])
1045
1047
        return index
1046
1048
 
1047
1049
    def assertNumPages(self, expected_pages, index, size):
1143
1145
    def test_stay_within_layer(self):
1144
1146
        index = self.make_1000_node_index()
1145
1147
        # When expanding a request, we won't read nodes from the next layer
1146
 
        self.assertExpandNodes([1, 2, 3, 4, 5, 6], index, [2])
1147
 
        self.assertExpandNodes([3, 4, 5, 6, 7, 8, 9], index, [6])
1148
 
        self.assertExpandNodes([4, 5, 6, 7, 8, 9], index, [9])
 
1148
        self.assertExpandNodes([1, 2, 3, 4], index, [2])
 
1149
        self.assertExpandNodes([6, 7, 8, 9], index, [6])
 
1150
        self.assertExpandNodes([6, 7, 8, 9], index, [9])
1149
1151
        self.assertExpandNodes([10, 11, 12, 13, 14, 15], index, [10])
1150
1152
        self.assertExpandNodes([10, 11, 12, 13, 14, 15, 16], index, [13])
1151
1153
 
1152
1154
        self.set_cached_keys(index, [0, 4, 12])
1153
1155
        self.assertExpandNodes([5, 6, 7, 8, 9], index, [7])
1154
1156
        self.assertExpandNodes([10, 11], index, [11])
 
1157
 
 
1158
    def test_small_requests_unexpanded(self):
 
1159
        index = self.make_100_node_index()
 
1160
        self.set_cached_keys(index, [0])
 
1161
        self.assertExpandNodes([1], index, [1])
 
1162
        self.assertExpandNodes([50], index, [50])
 
1163
        # If we request more than one node, then we'll expand
 
1164
        self.assertExpandNodes([49, 50, 51, 59, 60, 61], index, [50, 60])
 
1165
 
 
1166
        # The first pass does not expand
 
1167
        index = self.make_1000_node_index()
 
1168
        self.set_cached_keys(index, [0])
 
1169
        self.assertExpandNodes([1], index, [1])
 
1170
        self.set_cached_keys(index, [0, 1])
 
1171
        self.assertExpandNodes([100], index, [100])
 
1172
        self.set_cached_keys(index, [0, 1, 100])
 
1173
        # But after the first depth, we will expand
 
1174
        self.assertExpandNodes([2, 3, 4, 5, 6, 7], index, [2])
 
1175
        self.assertExpandNodes([2, 3, 4, 5, 6, 7], index, [4])
 
1176
        self.set_cached_keys(index, [0, 1, 2, 3, 4, 5, 6, 7, 100])
 
1177
        self.assertExpandNodes([102, 103, 104, 105, 106, 107, 108], index,
 
1178
                               [105])