/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

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

• reverse the comparison (5365.5.14 to 5200.3.2)
• stop comparing with revision 5200.3.2

Show diffs side-by-side

added

removed

bzrlib/btree_index.py

33

33

    osutils,

34

34

    static_tuple,

35

35

    trace,

 

36

    transport,

36

37

    )

37

38

from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN

38

 

from bzrlib.transport import get_transport

39

39

 

40

40

 

41

41

_BTSIGNATURE = "B+Tree Graph Index 2\n"

193

193

            new_backing_file, size = self._spill_mem_keys_without_combining()

194

194

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

195

195

        #       direct access to the new_backing._file object

196

 

        new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)

 

196

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

 

197

                                      '<temp>', size)

197

198

        # GC will clean up the file

198

199

        new_backing._file = new_backing_file

199

200

        if self._combine_backing_indices:

601

602

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

602

603

 

603

604

 

604

 

class _LeafNode(object):

 

605

class _LeafNode(dict):

605

606

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

606

607

 

607

 

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

 

608

    __slots__ = ('min_key', 'max_key')

608

609

 

609

610

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

610

611

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

616

617

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

617

618

        else:

618

619

            self.min_key = self.max_key = None

619

 

        self.keys = dict(key_list)

 

620

        super(_LeafNode, self).__init__(key_list)

 

621

 

 

622

    def all_items(self):

 

623

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

 

624

        items = self.items()

 

625

        items.sort()

 

626

        return items

 

627

 

 

628

    def all_keys(self):

 

629

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

 

630

        keys = self.keys()

 

631

        keys.sort()

 

632

        return keys

620

633

 

621

634

 

622

635

class _InternalNode(object):

671

684

        self._recommended_pages = self._compute_recommended_pages()

672

685

        self._root_node = None

673

686

        self._base_offset = offset

 

687

        self._leaf_klass = _LeafNode

674

688

        # Default max size is 100,000 leave values

675

689

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

676

690

        if unlimited_cache:

949

963

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

950

964

        if self._leaf_value_cache is not None:

951

965

            for node in nodes.itervalues():

952

 

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

 

966

                for key, value in node.all_items():

953

967

                    if key in self._leaf_value_cache:

954

968

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

955

969

                        # before.

979

993

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

980

994

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

981

995

            if self.node_ref_lists:

982

 

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

 

996

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

983

997

                    yield (self, key, value, refs)

984

998

            else:

985

 

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

 

999

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

986

1000

                    yield (self, key, value)

987

1001

            return

988

1002

        start_of_leaves = self._row_offsets[-2]

998

1012

        # for spilling index builds to disk.

999

1013

        if self.node_ref_lists:

1000

1014

            for _, node in nodes:

1001

 

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

 

1015

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

1002

1016

                    yield (self, key, value, refs)

1003

1017

        else:

1004

1018

            for _, node in nodes:

1005

 

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

 

1019

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

1006

1020

                    yield (self, key, value)

1007

1021

 

1008

1022

    @staticmethod

1169

1183

                continue

1170

1184

            node = nodes[node_index]

1171

1185

            for next_sub_key in sub_keys:

1172

 

                if next_sub_key in node.keys:

1173

 

                    value, refs = node.keys[next_sub_key]

 

1186

                if next_sub_key in node:

 

1187

                    value, refs = node[next_sub_key]

1174

1188

                    if self.node_ref_lists:

1175

1189

                        yield (self, next_sub_key, value, refs)

1176

1190

                    else:

1244

1258

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

1245

1259

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

1246

1260

            node = nodes[node_index]

1247

 

            node_keys = node.keys

1248

1261

            parents_to_check = set()

1249

1262

            for next_sub_key in sub_keys:

1250

 

                if next_sub_key not in node_keys:

 

1263

                if next_sub_key not in node:

1251

1264

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

1252

1265

                    missing_keys.add(next_sub_key)

1253

1266

                else:

1254

 

                    value, refs = node_keys[next_sub_key]

 

1267

                    value, refs = node[next_sub_key]

1255

1268

                    parent_keys = refs[ref_list_num]

1256

1269

                    parent_map[next_sub_key] = parent_keys

1257

1270

                    parents_to_check.update(parent_keys)

1264

1277

            while parents_to_check:

1265

1278

                next_parents_to_check = set()

1266

1279

                for key in parents_to_check:

1267

 

                    if key in node_keys:

1268

 

                        value, refs = node_keys[key]

 

1280

                    if key in node:

 

1281

                        value, refs = node[key]

1269

1282

                        parent_keys = refs[ref_list_num]

1270

1283

                        parent_map[key] = parent_keys

1271

1284

                        next_parents_to_check.update(parent_keys)

1545

1558

                    continue

1546

1559

            bytes = zlib.decompress(data)

1547

1560

            if bytes.startswith(_LEAF_FLAG):

1548

 

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

 

1561

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

 

1562

                                        self.node_ref_lists)

1549

1563

            elif bytes.startswith(_INTERNAL_FLAG):

1550

1564

                node = _InternalNode(bytes)

1551

1565

            else:

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.2.dev0