/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

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

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

Show diffs side-by-side

added

removed

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

17

17

 

18

18

"""B+Tree indices"""

19

19

 

 

20

from __future__ import absolute_import

 

21

 

20

22

import cStringIO

21

 

from bisect import bisect_right

 

23

 

 

24

from bzrlib.lazy_import import lazy_import

 

25

lazy_import(globals(), """

 

26

import bisect

22

27

import math

23

28

import tempfile

24

29

import zlib

 

30

""")

25

31

 

26

32

from bzrlib import (

27

33

    chunk_writer,

33

39

    osutils,

34

40

    static_tuple,

35

41

    trace,

 

42

    transport,

36

43

    )

37

44

from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN

38

 

from bzrlib.transport import get_transport

39

45

 

40

46

 

41

47

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

158

164

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

159

165

            reference to another key.

160

166

        :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.

 

167

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

162

168

        """

163

169

        # Ensure that 'key' is a StaticTuple

164

170

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

193

199

            new_backing_file, size = self._spill_mem_keys_without_combining()

194

200

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

195

201

        #       direct access to the new_backing._file object

196

 

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

 

202

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

 

203

                                      '<temp>', size)

197

204

        # GC will clean up the file

198

205

        new_backing._file = new_backing_file

199

206

        if self._combine_backing_indices:

289

296

            flag when writing out. This is used by the _spill_mem_keys_to_disk

290

297

            functionality.

291

298

        """

 

299

        new_leaf = False

292

300

        if rows[-1].writer is None:

293

301

            # opening a new leaf chunk;

 

302

            new_leaf = True

294

303

            for pos, internal_row in enumerate(rows[:-1]):

295

304

                # flesh out any internal nodes that are needed to

296

305

                # preserve the height of the tree

315

324

                optimize_for_size=self._optimize_for_size)

316

325

            rows[-1].writer.write(_LEAF_FLAG)

317

326

        if rows[-1].writer.write(line):

 

327

            # if we failed to write, despite having an empty page to write to,

 

328

            # then line is too big. raising the error avoids infinite recursion

 

329

            # searching for a suitably large page that will not be found.

 

330

            if new_leaf:

 

331

                raise errors.BadIndexKey(string_key)

318

332

            # this key did not fit in the node:

319

333

            rows[-1].finish_node()

320

334

            key_line = string_key + "\n"

383

397

                                    self.reference_lists)

384

398

            self._add_key(string_key, line, rows, allow_optimize=allow_optimize)

385

399

        for row in reversed(rows):

386

 

            pad = (type(row) != _LeafBuilderRow)

 

400

            pad = (not isinstance(row, _LeafBuilderRow))

387

401

            row.finish_node(pad=pad)

388

402

        lines = [_BTSIGNATURE]

389

403

        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')

416

430

            position = 0 # Only the root row actually has an offset

417

431

            copied_len = osutils.pumpfile(row.spool, result)

418

432

            if copied_len != (row.nodes - 1) * _PAGE_SIZE:

419

 

                if type(row) != _LeafBuilderRow:

 

433

                if not isinstance(row, _LeafBuilderRow):

420

434

                    raise AssertionError("Incorrect amount of data copied"

421

435

                        " expected: %d, got: %d"

422

436

                        % ((row.nodes - 1) * _PAGE_SIZE,

561

575

                    key_dict = dicts.pop(-1)

562

576

                    # can't be empty or would not exist

563

577

                    item, value = key_dict.iteritems().next()

564

 

                    if type(value) == dict:

 

578

                    if isinstance(value, dict):

565

579

                        # push keys

566

580

                        dicts.extend(key_dict.itervalues())

567

581

                    else:

601

615

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

602

616

 

603

617

 

604

 

class _LeafNode(object):

 

618

class _LeafNode(dict):

605

619

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

606

620

 

607

 

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

 

621

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

608

622

 

609

623

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

610

624

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

616

630

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

617

631

        else:

618

632

            self.min_key = self.max_key = None

619

 

        self.keys = dict(key_list)

 

633

        super(_LeafNode, self).__init__(key_list)

 

634

        self._keys = dict(self)

 

635

 

 

636

    def all_items(self):

 

637

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

 

638

        items = sorted(self.items())

 

639

        return items

 

640

 

 

641

    def all_keys(self):

 

642

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

 

643

        keys = sorted(self.keys())

 

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:

689

715

    def __eq__(self, other):

690

716

        """Equal when self and other were created with the same parameters."""

691

717

        return (

692

 

            type(self) == type(other) and

 

718

            isinstance(self, type(other)) and

693

719

            self._transport == other._transport and

694

720

            self._name == other._name and

695

721

            self._size == other._size)

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)

1402

1427

                    key_dict = dicts.pop(-1)

1403

1428

                    # can't be empty or would not exist

1404

1429

                    item, value = key_dict.iteritems().next()

1405

 

                    if type(value) == dict:

 

1430

                    if isinstance(value, dict):

1406

1431

                        # push keys

1407

1432

                        dicts.extend(key_dict.itervalues())

1408

1433

                    else:

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

1575

 

except ImportError, e:

 

1603

    _gcchk_factory = _btree_serializer._parse_into_chk

 

1604

except ImportError as e:

1576

1605

    osutils.failed_to_load_extension(e)

1577

1606

    from bzrlib import _btree_serializer_py as _btree_serializer

• Older »

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