/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/btree_index.py

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

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

Show diffs side-by-side

added

removed

breezy/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

 

import cStringIO

21

 

from bisect import bisect_right

 

20

from __future__ import absolute_import

 

21

 

 

22

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

 

from bzrlib import (

 

30

from . import (

27

31

    chunk_writer,

28

32

    debug,

29

33

    errors,

33

37

    osutils,

34

38

    static_tuple,

35

39

    trace,

36

 

    )

37

 

from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN

38

 

from bzrlib.transport import get_transport

 

40

    transport,

 

41

    )

 

42

from .index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN

 

43

from .sixish import (

 

44

    BytesIO,

 

45

    )

39

46

 

40

47

 

41

48

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

68

75

    def finish_node(self, pad=True):

69

76

        byte_lines, _, padding = self.writer.finish()

70

77

        if self.nodes == 0:

71

 

            self.spool = cStringIO.StringIO()

 

78

            self.spool = BytesIO()

72

79

            # padded note:

73

80

            self.spool.write("\x00" * _RESERVED_HEADER_BYTES)

74

81

        elif self.nodes == 1:

158

165

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

159

166

            reference to another key.

160

167

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

 

168

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

162

169

        """

163

170

        # Ensure that 'key' is a StaticTuple

164

171

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

193

200

            new_backing_file, size = self._spill_mem_keys_without_combining()

194

201

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

195

202

        #       direct access to the new_backing._file object

196

 

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

 

203

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

 

204

                                      '<temp>', size)

197

205

        # GC will clean up the file

198

206

        new_backing._file = new_backing_file

199

207

        if self._combine_backing_indices:

289

297

            flag when writing out. This is used by the _spill_mem_keys_to_disk

290

298

            functionality.

291

299

        """

 

300

        new_leaf = False

292

301

        if rows[-1].writer is None:

293

302

            # opening a new leaf chunk;

 

303

            new_leaf = True

294

304

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

295

305

                # flesh out any internal nodes that are needed to

296

306

                # preserve the height of the tree

315

325

                optimize_for_size=self._optimize_for_size)

316

326

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

317

327

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

 

328

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

 

329

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

 

330

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

 

331

            if new_leaf:

 

332

                raise errors.BadIndexKey(string_key)

318

333

            # this key did not fit in the node:

319

334

            rows[-1].finish_node()

320

335

            key_line = string_key + "\n"

383

398

                                    self.reference_lists)

384

399

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

385

400

        for row in reversed(rows):

386

 

            pad = (type(row) != _LeafBuilderRow)

 

401

            pad = (not isinstance(row, _LeafBuilderRow))

387

402

            row.finish_node(pad=pad)

388

403

        lines = [_BTSIGNATURE]

389

404

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

394

409

        if row_lengths and row_lengths[-1] > 1:

395

410

            result = tempfile.NamedTemporaryFile(prefix='bzr-index-')

396

411

        else:

397

 

            result = cStringIO.StringIO()

 

412

            result = BytesIO()

398

413

        result.writelines(lines)

399

414

        position = sum(map(len, lines))

400

415

        root_row = True

416

431

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

417

432

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

418

433

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

419

 

                if type(row) != _LeafBuilderRow:

 

434

                if not isinstance(row, _LeafBuilderRow):

420

435

                    raise AssertionError("Incorrect amount of data copied"

421

436

                        " expected: %d, got: %d"

422

437

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

561

576

                    key_dict = dicts.pop(-1)

562

577

                    # can't be empty or would not exist

563

578

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

564

 

                    if type(value) == dict:

 

579

                    if isinstance(value, dict):

565

580

                        # push keys

566

581

                        dicts.extend(key_dict.itervalues())

567

582

                    else:

601

616

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

602

617

 

603

618

 

604

 

class _LeafNode(object):

 

619

class _LeafNode(dict):

605

620

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

606

621

 

607

 

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

 

622

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

608

623

 

609

624

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

610

625

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

616

631

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

617

632

        else:

618

633

            self.min_key = self.max_key = None

619

 

        self.keys = dict(key_list)

 

634

        super(_LeafNode, self).__init__(key_list)

 

635

        self._keys = dict(self)

 

636

 

 

637

    def all_items(self):

 

638

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

 

639

        items = sorted(self.items())

 

640

        return items

 

641

 

 

642

    def all_keys(self):

 

643

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

 

644

        keys = sorted(self.keys())

 

645

        return keys

620

646

 

621

647

 

622

648

class _InternalNode(object):

671

697

        self._recommended_pages = self._compute_recommended_pages()

672

698

        self._root_node = None

673

699

        self._base_offset = offset

 

700

        self._leaf_factory = _LeafNode

674

701

        # Default max size is 100,000 leave values

675

702

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

676

703

        if unlimited_cache:

689

716

    def __eq__(self, other):

690

717

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

691

718

        return (

692

 

            type(self) == type(other) and

 

719

            isinstance(self, type(other)) and

693

720

            self._transport == other._transport and

694

721

            self._name == other._name and

695

722

            self._size == other._size)

949

976

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

950

977

        if self._leaf_value_cache is not None:

951

978

            for node in nodes.itervalues():

952

 

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

 

979

                for key, value in node.all_items():

953

980

                    if key in self._leaf_value_cache:

954

981

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

955

982

                        # before.

979

1006

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

980

1007

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

981

1008

            if self.node_ref_lists:

982

 

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

 

1009

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

983

1010

                    yield (self, key, value, refs)

984

1011

            else:

985

 

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

 

1012

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

986

1013

                    yield (self, key, value)

987

1014

            return

988

1015

        start_of_leaves = self._row_offsets[-2]

998

1025

        # for spilling index builds to disk.

999

1026

        if self.node_ref_lists:

1000

1027

            for _, node in nodes:

1001

 

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

 

1028

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

1002

1029

                    yield (self, key, value, refs)

1003

1030

        else:

1004

1031

            for _, node in nodes:

1005

 

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

 

1032

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

1006

1033

                    yield (self, key, value)

1007

1034

 

1008

1035

    @staticmethod

1032

1059

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

1033

1060

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

1034

1061

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

1035

 

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

 

1062

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

1036

1063

        # elif bisect_steps < iter_steps:

1037

1064

        #     offsets = {}

1038

1065

        #     for key in in_keys:

1169

1196

                continue

1170

1197

            node = nodes[node_index]

1171

1198

            for next_sub_key in sub_keys:

1172

 

                if next_sub_key in node.keys:

1173

 

                    value, refs = node.keys[next_sub_key]

 

1199

                if next_sub_key in node:

 

1200

                    value, refs = node[next_sub_key]

1174

1201

                    if self.node_ref_lists:

1175

1202

                        yield (self, next_sub_key, value, refs)

1176

1203

                    else:

1244

1271

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

1245

1272

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

1246

1273

            node = nodes[node_index]

1247

 

            node_keys = node.keys

1248

1274

            parents_to_check = set()

1249

1275

            for next_sub_key in sub_keys:

1250

 

                if next_sub_key not in node_keys:

 

1276

                if next_sub_key not in node:

1251

1277

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

1252

1278

                    missing_keys.add(next_sub_key)

1253

1279

                else:

1254

 

                    value, refs = node_keys[next_sub_key]

 

1280

                    value, refs = node[next_sub_key]

1255

1281

                    parent_keys = refs[ref_list_num]

1256

1282

                    parent_map[next_sub_key] = parent_keys

1257

1283

                    parents_to_check.update(parent_keys)

1264

1290

            while parents_to_check:

1265

1291

                next_parents_to_check = set()

1266

1292

                for key in parents_to_check:

1267

 

                    if key in node_keys:

1268

 

                        value, refs = node_keys[key]

 

1293

                    if key in node:

 

1294

                        value, refs = node[key]

1269

1295

                        parent_keys = refs[ref_list_num]

1270

1296

                        parent_map[key] = parent_keys

1271

1297

                        next_parents_to_check.update(parent_keys)

1333

1359

            self._get_root_node()

1334

1360

        # TODO: only access nodes that can satisfy the prefixes we are looking

1335

1361

        # for. For now, to meet API usage (as this function is not used by

1336

 

        # current bzrlib) just suck the entire index and iterate in memory.

 

1362

        # current breezy) just suck the entire index and iterate in memory.

1337

1363

        nodes = {}

1338

1364

        if self.node_ref_lists:

1339

1365

            if self._key_length == 1:

1402

1428

                    key_dict = dicts.pop(-1)

1403

1429

                    # can't be empty or would not exist

1404

1430

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

1405

 

                    if type(value) == dict:

 

1431

                    if isinstance(value, dict):

1406

1432

                        # push keys

1407

1433

                        dicts.extend(key_dict.itervalues())

1408

1434

                    else:

1545

1571

                    continue

1546

1572

            bytes = zlib.decompress(data)

1547

1573

            if bytes.startswith(_LEAF_FLAG):

1548

 

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

 

1574

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

 

1575

                                          self.node_ref_lists)

1549

1576

            elif bytes.startswith(_INTERNAL_FLAG):

1550

1577

                node = _InternalNode(bytes)

1551

1578

            else:

1570

1597

            pass

1571

1598

 

1572

1599

 

 

1600

_gcchk_factory = _LeafNode

 

1601

 

1573

1602

try:

1574

 

    from bzrlib import _btree_serializer_pyx as _btree_serializer

1575

 

except ImportError, e:

 

1603

    from breezy import _btree_serializer_pyx as _btree_serializer

 

1604

    _gcchk_factory = _btree_serializer._parse_into_chk

 

1605

except ImportError as e:

1576

1606

    osutils.failed_to_load_extension(e)

1577

 

    from bzrlib import _btree_serializer_py as _btree_serializer

 

1607

    from breezy import _btree_serializer_py as _btree_serializer

• Older »

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