/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

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

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

Show diffs side-by-side

added

removed

bzrlib/btree_index.py

33

33

    osutils,

34

34

    static_tuple,

35

35

    trace,

36

 

    transport,

37

36

    )

38

37

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(transport.get_transport('.'),

197

 

                                      '<temp>', size)

 

196

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

198

197

        # GC will clean up the file

199

198

        new_backing._file = new_backing_file

200

199

        if self._combine_backing_indices:

605

604

class _LeafNode(object):

606

605

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

607

606

 

608

 

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

 

607

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

609

608

 

610

609

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

611

610

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

617

616

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

618

617

        else:

619

618

            self.min_key = self.max_key = None

620

 

        self._keys = dict(key_list)

621

 

 

622

 

    def __len__(self):

623

 

        return len(self._keys)

624

 

 

625

 

    def __contains__(self, key):

626

 

        return key in self._keys

627

 

 

628

 

    def __getitem__(self, key):

629

 

        return self._keys[key]

630

 

 

631

 

    def all_items(self):

632

 

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

633

 

        items = self._keys.items()

634

 

        items.sort()

635

 

        return items

636

 

 

637

 

    def all_keys(self):

638

 

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

639

 

        keys = self._keys.keys()

640

 

        keys.sort()

641

 

        return keys

 

619

        self.keys = dict(key_list)

642

620

 

643

621

 

644

622

class _InternalNode(object):

693

671

        self._recommended_pages = self._compute_recommended_pages()

694

672

        self._root_node = None

695

673

        self._base_offset = offset

696

 

        self._leaf_klass = _LeafNode

697

674

        # Default max size is 100,000 leave values

698

675

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

699

676

        if unlimited_cache:

972

949

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

973

950

        if self._leaf_value_cache is not None:

974

951

            for node in nodes.itervalues():

975

 

                for key, value in node.all_items():

 

952

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

976

953

                    if key in self._leaf_value_cache:

977

954

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

978

955

                        # before.

1002

979

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

1003

980

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

1004

981

            if self.node_ref_lists:

1005

 

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

 

982

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

1006

983

                    yield (self, key, value, refs)

1007

984

            else:

1008

 

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

 

985

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

1009

986

                    yield (self, key, value)

1010

987

            return

1011

988

        start_of_leaves = self._row_offsets[-2]

1021

998

        # for spilling index builds to disk.

1022

999

        if self.node_ref_lists:

1023

1000

            for _, node in nodes:

1024

 

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

 

1001

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

1025

1002

                    yield (self, key, value, refs)

1026

1003

        else:

1027

1004

            for _, node in nodes:

1028

 

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

 

1005

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

1029

1006

                    yield (self, key, value)

1030

1007

 

1031

1008

    @staticmethod

1192

1169

                continue

1193

1170

            node = nodes[node_index]

1194

1171

            for next_sub_key in sub_keys:

1195

 

                if next_sub_key in node:

1196

 

                    value, refs = node[next_sub_key]

 

1172

                if next_sub_key in node.keys:

 

1173

                    value, refs = node.keys[next_sub_key]

1197

1174

                    if self.node_ref_lists:

1198

1175

                        yield (self, next_sub_key, value, refs)

1199

1176

                    else:

1267

1244

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

1268

1245

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

1269

1246

            node = nodes[node_index]

 

1247

            node_keys = node.keys

1270

1248

            parents_to_check = set()

1271

1249

            for next_sub_key in sub_keys:

1272

 

                if next_sub_key not in node:

 

1250

                if next_sub_key not in node_keys:

1273

1251

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

1274

1252

                    missing_keys.add(next_sub_key)

1275

1253

                else:

1276

 

                    value, refs = node[next_sub_key]

 

1254

                    value, refs = node_keys[next_sub_key]

1277

1255

                    parent_keys = refs[ref_list_num]

1278

1256

                    parent_map[next_sub_key] = parent_keys

1279

1257

                    parents_to_check.update(parent_keys)

1286

1264

            while parents_to_check:

1287

1265

                next_parents_to_check = set()

1288

1266

                for key in parents_to_check:

1289

 

                    if key in node:

1290

 

                        value, refs = node[key]

 

1267

                    if key in node_keys:

 

1268

                        value, refs = node_keys[key]

1291

1269

                        parent_keys = refs[ref_list_num]

1292

1270

                        parent_map[key] = parent_keys

1293

1271

                        next_parents_to_check.update(parent_keys)

1567

1545

                    continue

1568

1546

            bytes = zlib.decompress(data)

1569

1547

            if bytes.startswith(_LEAF_FLAG):

1570

 

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

1571

 

                                        self.node_ref_lists)

 

1548

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

1572

1549

            elif bytes.startswith(_INTERNAL_FLAG):

1573

1550

                node = _InternalNode(bytes)

1574

1551

            else:

• Older »

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