/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Martin Pool
  • Date: 2011-11-29 09:13:54 UTC
  • mto: This revision was merged to the branch mainline in revision 6329.
  • Revision ID: mbp@canonical.com-20111129091354-zcwnzn3cy1jfzqju
ContainerWriter: Avoid one possible large-string join

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,
33
37
    osutils,
34
38
    static_tuple,
35
39
    trace,
 
40
    transport,
36
41
    )
37
42
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
38
 
from bzrlib.transport import get_transport
39
43
 
40
44
 
41
45
_BTSIGNATURE = "B+Tree Graph Index 2\n"
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(get_transport('.'), '<temp>', size)
 
200
        new_backing = BTreeGraphIndex(transport.get_transport_from_path('.'),
 
201
                                      '<temp>', size)
197
202
        # GC will clean up the file
198
203
        new_backing._file = new_backing_file
199
204
        if self._combine_backing_indices:
315
320
                optimize_for_size=self._optimize_for_size)
316
321
            rows[-1].writer.write(_LEAF_FLAG)
317
322
        if rows[-1].writer.write(line):
 
323
            # if we failed to write, despite having an empty page to write to,
 
324
            # then line is too big. len is 2 here because we've already written
 
325
            # some header. raising the error avoids infinite recursion searching
 
326
            # for a suitably large page that will not be found.
 
327
            if rows[-1].writer.bytes_out_len <= 2:
 
328
                raise errors.BadIndexKey(string_key)
318
329
            # this key did not fit in the node:
319
330
            rows[-1].finish_node()
320
331
            key_line = string_key + "\n"
601
612
        """In memory index's have no known corruption at the moment."""
602
613
 
603
614
 
604
 
class _LeafNode(object):
 
615
class _LeafNode(dict):
605
616
    """A leaf node for a serialised B+Tree index."""
606
617
 
607
 
    __slots__ = ('keys', 'min_key', 'max_key')
 
618
    __slots__ = ('min_key', 'max_key', '_keys')
608
619
 
609
620
    def __init__(self, bytes, key_length, ref_list_length):
610
621
        """Parse bytes to create a leaf node object."""
616
627
            self.max_key = key_list[-1][0]
617
628
        else:
618
629
            self.min_key = self.max_key = None
619
 
        self.keys = dict(key_list)
 
630
        super(_LeafNode, self).__init__(key_list)
 
631
        self._keys = dict(self)
 
632
 
 
633
    def all_items(self):
 
634
        """Return a sorted list of (key, (value, refs)) items"""
 
635
        items = self.items()
 
636
        items.sort()
 
637
        return items
 
638
 
 
639
    def all_keys(self):
 
640
        """Return a sorted list of all keys."""
 
641
        keys = self.keys()
 
642
        keys.sort()
 
643
        return keys
620
644
 
621
645
 
622
646
class _InternalNode(object):
671
695
        self._recommended_pages = self._compute_recommended_pages()
672
696
        self._root_node = None
673
697
        self._base_offset = offset
 
698
        self._leaf_factory = _LeafNode
674
699
        # Default max size is 100,000 leave values
675
700
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
676
701
        if unlimited_cache:
949
974
        """Cache directly from key => value, skipping the btree."""
950
975
        if self._leaf_value_cache is not None:
951
976
            for node in nodes.itervalues():
952
 
                for key, value in node.keys.iteritems():
 
977
                for key, value in node.all_items():
953
978
                    if key in self._leaf_value_cache:
954
979
                        # Don't add the rest of the keys, we've seen this node
955
980
                        # before.
979
1004
        if self._row_offsets[-1] == 1:
980
1005
            # There is only the root node, and we read that via key_count()
981
1006
            if self.node_ref_lists:
982
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1007
                for key, (value, refs) in self._root_node.all_items():
983
1008
                    yield (self, key, value, refs)
984
1009
            else:
985
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1010
                for key, (value, refs) in self._root_node.all_items():
986
1011
                    yield (self, key, value)
987
1012
            return
988
1013
        start_of_leaves = self._row_offsets[-2]
998
1023
        # for spilling index builds to disk.
999
1024
        if self.node_ref_lists:
1000
1025
            for _, node in nodes:
1001
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1026
                for key, (value, refs) in node.all_items():
1002
1027
                    yield (self, key, value, refs)
1003
1028
        else:
1004
1029
            for _, node in nodes:
1005
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1030
                for key, (value, refs) in node.all_items():
1006
1031
                    yield (self, key, value)
1007
1032
 
1008
1033
    @staticmethod
1032
1057
        # iter_steps = len(in_keys) + len(fixed_keys)
1033
1058
        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1034
1059
        if len(in_keys) == 1: # Bisect will always be faster for M = 1
1035
 
            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
 
1060
            return [(bisect.bisect_right(fixed_keys, in_keys[0]), in_keys)]
1036
1061
        # elif bisect_steps < iter_steps:
1037
1062
        #     offsets = {}
1038
1063
        #     for key in in_keys:
1169
1194
                continue
1170
1195
            node = nodes[node_index]
1171
1196
            for next_sub_key in sub_keys:
1172
 
                if next_sub_key in node.keys:
1173
 
                    value, refs = node.keys[next_sub_key]
 
1197
                if next_sub_key in node:
 
1198
                    value, refs = node[next_sub_key]
1174
1199
                    if self.node_ref_lists:
1175
1200
                        yield (self, next_sub_key, value, refs)
1176
1201
                    else:
1244
1269
            # sub_keys is all of the keys we are looking for that should exist
1245
1270
            # on this page, if they aren't here, then they won't be found
1246
1271
            node = nodes[node_index]
1247
 
            node_keys = node.keys
1248
1272
            parents_to_check = set()
1249
1273
            for next_sub_key in sub_keys:
1250
 
                if next_sub_key not in node_keys:
 
1274
                if next_sub_key not in node:
1251
1275
                    # This one is just not present in the index at all
1252
1276
                    missing_keys.add(next_sub_key)
1253
1277
                else:
1254
 
                    value, refs = node_keys[next_sub_key]
 
1278
                    value, refs = node[next_sub_key]
1255
1279
                    parent_keys = refs[ref_list_num]
1256
1280
                    parent_map[next_sub_key] = parent_keys
1257
1281
                    parents_to_check.update(parent_keys)
1264
1288
            while parents_to_check:
1265
1289
                next_parents_to_check = set()
1266
1290
                for key in parents_to_check:
1267
 
                    if key in node_keys:
1268
 
                        value, refs = node_keys[key]
 
1291
                    if key in node:
 
1292
                        value, refs = node[key]
1269
1293
                        parent_keys = refs[ref_list_num]
1270
1294
                        parent_map[key] = parent_keys
1271
1295
                        next_parents_to_check.update(parent_keys)
1545
1569
                    continue
1546
1570
            bytes = zlib.decompress(data)
1547
1571
            if bytes.startswith(_LEAF_FLAG):
1548
 
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
 
1572
                node = self._leaf_factory(bytes, self._key_length,
 
1573
                                          self.node_ref_lists)
1549
1574
            elif bytes.startswith(_INTERNAL_FLAG):
1550
1575
                node = _InternalNode(bytes)
1551
1576
            else:
1570
1595
            pass
1571
1596
 
1572
1597
 
 
1598
_gcchk_factory = _LeafNode
 
1599
 
1573
1600
try:
1574
1601
    from bzrlib import _btree_serializer_pyx as _btree_serializer
 
1602
    _gcchk_factory = _btree_serializer._parse_into_chk
1575
1603
except ImportError, e:
1576
1604
    osutils.failed_to_load_extension(e)
1577
1605
    from bzrlib import _btree_serializer_py as _btree_serializer