← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Martin Packman
  • Date: 2011-12-19 10:37:57 UTC
  • mto: This revision was merged to the branch mainline in revision 6394.
  • Revision ID: martin.packman@canonical.com-20111219103757-b85as9n9pb7e6qvn
Add tests for deprecated unicode wrapper functions in win32utils

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:
289
294
            flag when writing out. This is used by the _spill_mem_keys_to_disk
290
295
            functionality.
291
296
        """
 
297
        new_leaf = False
292
298
        if rows[-1].writer is None:
293
299
            # opening a new leaf chunk;
 
300
            new_leaf = True
294
301
            for pos, internal_row in enumerate(rows[:-1]):
295
302
                # flesh out any internal nodes that are needed to
296
303
                # preserve the height of the tree
315
322
                optimize_for_size=self._optimize_for_size)
316
323
            rows[-1].writer.write(_LEAF_FLAG)
317
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)
318
330
            # this key did not fit in the node:
319
331
            rows[-1].finish_node()
320
332
            key_line = string_key + "\n"
601
613
        """In memory index's have no known corruption at the moment."""
602
614
 
603
615
 
604
 
class _LeafNode(object):
 
616
class _LeafNode(dict):
605
617
    """A leaf node for a serialised B+Tree index."""
606
618
 
607
 
    __slots__ = ('keys', 'min_key', 'max_key')
 
619
    __slots__ = ('min_key', 'max_key', '_keys')
608
620
 
609
621
    def __init__(self, bytes, key_length, ref_list_length):
610
622
        """Parse bytes to create a leaf node object."""
616
628
            self.max_key = key_list[-1][0]
617
629
        else:
618
630
            self.min_key = self.max_key = None
619
 
        self.keys = dict(key_list)
 
631
        super(_LeafNode, self).__init__(key_list)
 
632
        self._keys = dict(self)
 
633
 
 
634
    def all_items(self):
 
635
        """Return a sorted list of (key, (value, refs)) items"""
 
636
        items = self.items()
 
637
        items.sort()
 
638
        return items
 
639
 
 
640
    def all_keys(self):
 
641
        """Return a sorted list of all keys."""
 
642
        keys = self.keys()
 
643
        keys.sort()
 
644
        return keys
620
645
 
621
646
 
622
647
class _InternalNode(object):
671
696
        self._recommended_pages = self._compute_recommended_pages()
672
697
        self._root_node = None
673
698
        self._base_offset = offset
 
699
        self._leaf_factory = _LeafNode
674
700
        # Default max size is 100,000 leave values
675
701
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
676
702
        if unlimited_cache:
949
975
        """Cache directly from key => value, skipping the btree."""
950
976
        if self._leaf_value_cache is not None:
951
977
            for node in nodes.itervalues():
952
 
                for key, value in node.keys.iteritems():
 
978
                for key, value in node.all_items():
953
979
                    if key in self._leaf_value_cache:
954
980
                        # Don't add the rest of the keys, we've seen this node
955
981
                        # before.
979
1005
        if self._row_offsets[-1] == 1:
980
1006
            # There is only the root node, and we read that via key_count()
981
1007
            if self.node_ref_lists:
982
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1008
                for key, (value, refs) in self._root_node.all_items():
983
1009
                    yield (self, key, value, refs)
984
1010
            else:
985
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1011
                for key, (value, refs) in self._root_node.all_items():
986
1012
                    yield (self, key, value)
987
1013
            return
988
1014
        start_of_leaves = self._row_offsets[-2]
998
1024
        # for spilling index builds to disk.
999
1025
        if self.node_ref_lists:
1000
1026
            for _, node in nodes:
1001
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1027
                for key, (value, refs) in node.all_items():
1002
1028
                    yield (self, key, value, refs)
1003
1029
        else:
1004
1030
            for _, node in nodes:
1005
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1031
                for key, (value, refs) in node.all_items():
1006
1032
                    yield (self, key, value)
1007
1033
 
1008
1034
    @staticmethod
1032
1058
        # iter_steps = len(in_keys) + len(fixed_keys)
1033
1059
        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1034
1060
        if len(in_keys) == 1: # Bisect will always be faster for M = 1
1035
 
            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
 
1061
            return [(bisect.bisect_right(fixed_keys, in_keys[0]), in_keys)]
1036
1062
        # elif bisect_steps < iter_steps:
1037
1063
        #     offsets = {}
1038
1064
        #     for key in in_keys:
1169
1195
                continue
1170
1196
            node = nodes[node_index]
1171
1197
            for next_sub_key in sub_keys:
1172
 
                if next_sub_key in node.keys:
1173
 
                    value, refs = node.keys[next_sub_key]
 
1198
                if next_sub_key in node:
 
1199
                    value, refs = node[next_sub_key]
1174
1200
                    if self.node_ref_lists:
1175
1201
                        yield (self, next_sub_key, value, refs)
1176
1202
                    else:
1244
1270
            # sub_keys is all of the keys we are looking for that should exist
1245
1271
            # on this page, if they aren't here, then they won't be found
1246
1272
            node = nodes[node_index]
1247
 
            node_keys = node.keys
1248
1273
            parents_to_check = set()
1249
1274
            for next_sub_key in sub_keys:
1250
 
                if next_sub_key not in node_keys:
 
1275
                if next_sub_key not in node:
1251
1276
                    # This one is just not present in the index at all
1252
1277
                    missing_keys.add(next_sub_key)
1253
1278
                else:
1254
 
                    value, refs = node_keys[next_sub_key]
 
1279
                    value, refs = node[next_sub_key]
1255
1280
                    parent_keys = refs[ref_list_num]
1256
1281
                    parent_map[next_sub_key] = parent_keys
1257
1282
                    parents_to_check.update(parent_keys)
1264
1289
            while parents_to_check:
1265
1290
                next_parents_to_check = set()
1266
1291
                for key in parents_to_check:
1267
 
                    if key in node_keys:
1268
 
                        value, refs = node_keys[key]
 
1292
                    if key in node:
 
1293
                        value, refs = node[key]
1269
1294
                        parent_keys = refs[ref_list_num]
1270
1295
                        parent_map[key] = parent_keys
1271
1296
                        next_parents_to_check.update(parent_keys)
1545
1570
                    continue
1546
1571
            bytes = zlib.decompress(data)
1547
1572
            if bytes.startswith(_LEAF_FLAG):
1548
 
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
 
1573
                node = self._leaf_factory(bytes, self._key_length,
 
1574
                                          self.node_ref_lists)
1549
1575
            elif bytes.startswith(_INTERNAL_FLAG):
1550
1576
                node = _InternalNode(bytes)
1551
1577
            else:
1570
1596
            pass
1571
1597
 
1572
1598
 
 
1599
_gcchk_factory = _LeafNode
 
1600
 
1573
1601
try:
1574
1602
    from bzrlib import _btree_serializer_pyx as _btree_serializer
 
1603
    _gcchk_factory = _btree_serializer._parse_into_chk
1575
1604
except ImportError, e:
1576
1605
    osutils.failed_to_load_extension(e)
1577
1606
    from bzrlib import _btree_serializer_py as _btree_serializer