← 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: 2012-01-24 13:14:06 UTC
  • mto: (6445.4.5 nested-trees-spec)
  • mto: This revision was merged to the branch mainline in revision 6518.
  • Revision ID: jelmer@samba.org-20120124131406-wedftkorbpv37bm0
Import nested tree doc from devnotes.

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