← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Jelmer Vernooij
  • Date: 2011-12-16 16:40:10 UTC
  • mto: This revision was merged to the branch mainline in revision 6391.
  • Revision ID: jelmer@samba.org-20111216164010-z3hy00xrnclnkf7a
Update tests.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
1
 
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 2008-2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
18
18
"""B+Tree indices"""
19
19
 
20
20
import cStringIO
21
 
from bisect import bisect_right
 
21
 
 
22
from bzrlib.lazy_import import lazy_import
 
23
lazy_import(globals(), """
 
24
import bisect
22
25
import math
23
26
import tempfile
24
27
import zlib
 
28
""")
25
29
 
26
30
from bzrlib import (
27
31
    chunk_writer,
158
162
        :param references: An iterable of iterables of keys. Each is a
159
163
            reference to another key.
160
164
        :param value: The value to associate with the key. It may be any
161
 
            bytes as long as it does not contain \0 or \n.
 
165
            bytes as long as it does not contain \\0 or \\n.
162
166
        """
163
167
        # Ensure that 'key' is a StaticTuple
164
168
        key = static_tuple.StaticTuple.from_sequence(key).intern()
193
197
            new_backing_file, size = self._spill_mem_keys_without_combining()
194
198
        # Note: The transport here isn't strictly needed, because we will use
195
199
        #       direct access to the new_backing._file object
196
 
        new_backing = BTreeGraphIndex(transport.get_transport('.'),
 
200
        new_backing = BTreeGraphIndex(transport.get_transport_from_path('.'),
197
201
                                      '<temp>', size)
198
202
        # GC will clean up the file
199
203
        new_backing._file = new_backing_file
290
294
            flag when writing out. This is used by the _spill_mem_keys_to_disk
291
295
            functionality.
292
296
        """
 
297
        new_leaf = False
293
298
        if rows[-1].writer is None:
294
299
            # opening a new leaf chunk;
 
300
            new_leaf = True
295
301
            for pos, internal_row in enumerate(rows[:-1]):
296
302
                # flesh out any internal nodes that are needed to
297
303
                # preserve the height of the tree
316
322
                optimize_for_size=self._optimize_for_size)
317
323
            rows[-1].writer.write(_LEAF_FLAG)
318
324
        if rows[-1].writer.write(line):
 
325
            # if we failed to write, despite having an empty page to write to,
 
326
            # then line is too big. raising the error avoids infinite recursion
 
327
            # searching for a suitably large page that will not be found.
 
328
            if new_leaf:
 
329
                raise errors.BadIndexKey(string_key)
319
330
            # this key did not fit in the node:
320
331
            rows[-1].finish_node()
321
332
            key_line = string_key + "\n"
1047
1058
        # iter_steps = len(in_keys) + len(fixed_keys)
1048
1059
        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1049
1060
        if len(in_keys) == 1: # Bisect will always be faster for M = 1
1050
 
            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
 
1061
            return [(bisect.bisect_right(fixed_keys, in_keys[0]), in_keys)]
1051
1062
        # elif bisect_steps < iter_steps:
1052
1063
        #     offsets = {}
1053
1064
        #     for key in in_keys: