← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-08-24 23:20:14 UTC
  • mfrom: (5365.5.29 2.3-btree-chk-leaf)
  • Revision ID: pqm@pqm.ubuntu.com-20100824232014-nu9owzel2zym2jk2
(jam) Use a custom C type for CHK index entries, saves memory

Show diffs side-by-side

added added

removed removed

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