~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

• browse files at revision 5362.1.1
• compare with another revision
• download diff
• download tarball
• view history from revision 5362.1.1

• reverse the comparison (5362.1.1 to 6217)
• stop comparing with revision 6217

Show diffs side-by-side

added

removed

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

18

18

"""B+Tree indices"""

19

19

 

20

20

import cStringIO

21

 

 

22

 

from bzrlib.lazy_import import lazy_import

23

 

lazy_import(globals(), """

24

 

import bisect

 

21

from bisect import bisect_right

25

22

import math

26

23

import tempfile

27

24

import zlib

28

 

""")

29

25

 

30

26

from bzrlib import (

31

27

    chunk_writer,

162

158

        :param references: An iterable of iterables of keys. Each is a

163

159

            reference to another key.

164

160

        :param value: The value to associate with the key. It may be any

165

 

            bytes as long as it does not contain \\0 or \\n.

 

161

            bytes as long as it does not contain \0 or \n.

166

162

        """

167

163

        # Ensure that 'key' is a StaticTuple

168

164

        key = static_tuple.StaticTuple.from_sequence(key).intern()

197

193

            new_backing_file, size = self._spill_mem_keys_without_combining()

198

194

        # Note: The transport here isn't strictly needed, because we will use

199

195

        #       direct access to the new_backing._file object

200

 

        new_backing = BTreeGraphIndex(transport.get_transport_from_path('.'),

 

196

        new_backing = BTreeGraphIndex(transport.get_transport('.'),

201

197

                                      '<temp>', size)

202

198

        # GC will clean up the file

203

199

        new_backing._file = new_backing_file

606

602

        """In memory index's have no known corruption at the moment."""

607

603

 

608

604

 

609

 

class _LeafNode(dict):

 

605

class _LeafNode(object):

610

606

    """A leaf node for a serialised B+Tree index."""

611

607

 

612

 

    __slots__ = ('min_key', 'max_key', '_keys')

 

608

    __slots__ = ('keys', 'min_key', 'max_key')

613

609

 

614

610

    def __init__(self, bytes, key_length, ref_list_length):

615

611

        """Parse bytes to create a leaf node object."""

621

617

            self.max_key = key_list[-1][0]

622

618

        else:

623

619

            self.min_key = self.max_key = None

624

 

        super(_LeafNode, self).__init__(key_list)

625

 

        self._keys = dict(self)

626

 

 

627

 

    def all_items(self):

628

 

        """Return a sorted list of (key, (value, refs)) items"""

629

 

        items = self.items()

630

 

        items.sort()

631

 

        return items

632

 

 

633

 

    def all_keys(self):

634

 

        """Return a sorted list of all keys."""

635

 

        keys = self.keys()

636

 

        keys.sort()

637

 

        return keys

 

620

        self.keys = dict(key_list)

638

621

 

639

622

 

640

623

class _InternalNode(object):

689

672

        self._recommended_pages = self._compute_recommended_pages()

690

673

        self._root_node = None

691

674

        self._base_offset = offset

692

 

        self._leaf_factory = _LeafNode

693

675

        # Default max size is 100,000 leave values

694

676

        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)

695

677

        if unlimited_cache:

968

950

        """Cache directly from key => value, skipping the btree."""

969

951

        if self._leaf_value_cache is not None:

970

952

            for node in nodes.itervalues():

971

 

                for key, value in node.all_items():

 

953

                for key, value in node.keys.iteritems():

972

954

                    if key in self._leaf_value_cache:

973

955

                        # Don't add the rest of the keys, we've seen this node

974

956

                        # before.

998

980

        if self._row_offsets[-1] == 1:

999

981

            # There is only the root node, and we read that via key_count()

1000

982

            if self.node_ref_lists:

1001

 

                for key, (value, refs) in self._root_node.all_items():

 

983

                for key, (value, refs) in sorted(self._root_node.keys.items()):

1002

984

                    yield (self, key, value, refs)

1003

985

            else:

1004

 

                for key, (value, refs) in self._root_node.all_items():

 

986

                for key, (value, refs) in sorted(self._root_node.keys.items()):

1005

987

                    yield (self, key, value)

1006

988

            return

1007

989

        start_of_leaves = self._row_offsets[-2]

1017

999

        # for spilling index builds to disk.

1018

1000

        if self.node_ref_lists:

1019

1001

            for _, node in nodes:

1020

 

                for key, (value, refs) in node.all_items():

 

1002

                for key, (value, refs) in sorted(node.keys.items()):

1021

1003

                    yield (self, key, value, refs)

1022

1004

        else:

1023

1005

            for _, node in nodes:

1024

 

                for key, (value, refs) in node.all_items():

 

1006

                for key, (value, refs) in sorted(node.keys.items()):

1025

1007

                    yield (self, key, value)

1026

1008

 

1027

1009

    @staticmethod

1051

1033

        # iter_steps = len(in_keys) + len(fixed_keys)

1052

1034

        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)

1053

1035

        if len(in_keys) == 1: # Bisect will always be faster for M = 1

1054

 

            return [(bisect.bisect_right(fixed_keys, in_keys[0]), in_keys)]

 

1036

            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]

1055

1037

        # elif bisect_steps < iter_steps:

1056

1038

        #     offsets = {}

1057

1039

        #     for key in in_keys:

1188

1170

                continue

1189

1171

            node = nodes[node_index]

1190

1172

            for next_sub_key in sub_keys:

1191

 

                if next_sub_key in node:

1192

 

                    value, refs = node[next_sub_key]

 

1173

                if next_sub_key in node.keys:

 

1174

                    value, refs = node.keys[next_sub_key]

1193

1175

                    if self.node_ref_lists:

1194

1176

                        yield (self, next_sub_key, value, refs)

1195

1177

                    else:

1263

1245

            # sub_keys is all of the keys we are looking for that should exist

1264

1246

            # on this page, if they aren't here, then they won't be found

1265

1247

            node = nodes[node_index]

 

1248

            node_keys = node.keys

1266

1249

            parents_to_check = set()

1267

1250

            for next_sub_key in sub_keys:

1268

 

                if next_sub_key not in node:

 

1251

                if next_sub_key not in node_keys:

1269

1252

                    # This one is just not present in the index at all

1270

1253

                    missing_keys.add(next_sub_key)

1271

1254

                else:

1272

 

                    value, refs = node[next_sub_key]

 

1255

                    value, refs = node_keys[next_sub_key]

1273

1256

                    parent_keys = refs[ref_list_num]

1274

1257

                    parent_map[next_sub_key] = parent_keys

1275

1258

                    parents_to_check.update(parent_keys)

1282

1265

            while parents_to_check:

1283

1266

                next_parents_to_check = set()

1284

1267

                for key in parents_to_check:

1285

 

                    if key in node:

1286

 

                        value, refs = node[key]

 

1268

                    if key in node_keys:

 

1269

                        value, refs = node_keys[key]

1287

1270

                        parent_keys = refs[ref_list_num]

1288

1271

                        parent_map[key] = parent_keys

1289

1272

                        next_parents_to_check.update(parent_keys)

1563

1546

                    continue

1564

1547

            bytes = zlib.decompress(data)

1565

1548

            if bytes.startswith(_LEAF_FLAG):

1566

 

                node = self._leaf_factory(bytes, self._key_length,

1567

 

                                          self.node_ref_lists)

 

1549

                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)

1568

1550

            elif bytes.startswith(_INTERNAL_FLAG):

1569

1551

                node = _InternalNode(bytes)

1570

1552

            else:

1589

1571

            pass

1590

1572

 

1591

1573

 

1592

 

_gcchk_factory = _LeafNode

1593

 

 

1594

1574

try:

1595

1575

    from bzrlib import _btree_serializer_pyx as _btree_serializer

1596

 

    _gcchk_factory = _btree_serializer._parse_into_chk

1597

1576

except ImportError, e:

1598

1577

    osutils.failed_to_load_extension(e)

1599

1578

    from bzrlib import _btree_serializer_py as _btree_serializer

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.1