/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/btree_index.py

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

• reverse the comparison (6651.2.2 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

    map,

 

46

    range,

 

47

    )

39

48

 

40

49

 

41

50

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

68

77

    def finish_node(self, pad=True):

69

78

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

70

79

        if self.nodes == 0:

71

 

            self.spool = cStringIO.StringIO()

 

80

            self.spool = BytesIO()

72

81

            # padded note:

73

82

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

74

83

        elif self.nodes == 1:

158

167

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

159

168

            reference to another key.

160

169

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

 

170

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

162

171

        """

163

172

        # Ensure that 'key' is a StaticTuple

164

173

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

193

202

            new_backing_file, size = self._spill_mem_keys_without_combining()

194

203

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

195

204

        #       direct access to the new_backing._file object

196

 

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

 

205

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

 

206

                                      '<temp>', size)

197

207

        # GC will clean up the file

198

208

        new_backing._file = new_backing_file

199

209

        if self._combine_backing_indices:

256

266

        current_values = []

257

267

        for iterator in iterators_to_combine:

258

268

            try:

259

 

                current_values.append(iterator.next())

 

269

                current_values.append(next(iterator))

260

270

            except StopIteration:

261

271

                current_values.append(None)

262

272

        last = None

276

286

            yield (self,) + selected[1][1:]

277

287

            pos = selected[0]

278

288

            try:

279

 

                current_values[pos] = iterators_to_combine[pos].next()

 

289

                current_values[pos] = next(iterators_to_combine[pos])

280

290

            except StopIteration:

281

291

                current_values[pos] = None

282

292

 

289

299

            flag when writing out. This is used by the _spill_mem_keys_to_disk

290

300

            functionality.

291

301

        """

 

302

        new_leaf = False

292

303

        if rows[-1].writer is None:

293

304

            # opening a new leaf chunk;

 

305

            new_leaf = True

294

306

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

295

307

                # flesh out any internal nodes that are needed to

296

308

                # preserve the height of the tree

315

327

                optimize_for_size=self._optimize_for_size)

316

328

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

317

329

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

 

330

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

 

331

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

 

332

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

 

333

            if new_leaf:

 

334

                raise errors.BadIndexKey(string_key)

318

335

            # this key did not fit in the node:

319

336

            rows[-1].finish_node()

320

337

            key_line = string_key + "\n"

383

400

                                    self.reference_lists)

384

401

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

385

402

        for row in reversed(rows):

386

 

            pad = (type(row) != _LeafBuilderRow)

 

403

            pad = (not isinstance(row, _LeafBuilderRow))

387

404

            row.finish_node(pad=pad)

388

405

        lines = [_BTSIGNATURE]

389

406

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

394

411

        if row_lengths and row_lengths[-1] > 1:

395

412

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

396

413

        else:

397

 

            result = cStringIO.StringIO()

 

414

            result = BytesIO()

398

415

        result.writelines(lines)

399

416

        position = sum(map(len, lines))

400

417

        root_row = True

416

433

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

417

434

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

418

435

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

419

 

                if type(row) != _LeafBuilderRow:

 

436

                if not isinstance(row, _LeafBuilderRow):

420

437

                    raise AssertionError("Incorrect amount of data copied"

421

438

                        " expected: %d, got: %d"

422

439

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

560

577

                while dicts:

561

578

                    key_dict = dicts.pop(-1)

562

579

                    # can't be empty or would not exist

563

 

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

564

 

                    if type(value) == dict:

 

580

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

 

581

                    if isinstance(value, dict):

565

582

                        # push keys

566

583

                        dicts.extend(key_dict.itervalues())

567

584

                    else:

601

618

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

602

619

 

603

620

 

604

 

class _LeafNode(object):

 

621

class _LeafNode(dict):

605

622

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

606

623

 

607

 

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

 

624

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

608

625

 

609

626

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

610

627

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

616

633

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

617

634

        else:

618

635

            self.min_key = self.max_key = None

619

 

        self.keys = dict(key_list)

 

636

        super(_LeafNode, self).__init__(key_list)

 

637

        self._keys = dict(self)

 

638

 

 

639

    def all_items(self):

 

640

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

 

641

        items = sorted(self.items())

 

642

        return items

 

643

 

 

644

    def all_keys(self):

 

645

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

 

646

        keys = sorted(self.keys())

 

647

        return keys

620

648

 

621

649

 

622

650

class _InternalNode(object):

636

664

        for line in lines[2:]:

637

665

            if line == '':

638

666

                break

639

 

            nodes.append(as_st(map(intern, line.split('\0'))).intern())

 

667

            # GZ 2017-05-24: Used to intern() each chunk of line as well, need

 

668

            # to recheck performance and perhaps adapt StaticTuple to adjust.

 

669

            nodes.append(as_st(line.split(b'\0')).intern())

640

670

        return nodes

641

671

 

642

672

 

671

701

        self._recommended_pages = self._compute_recommended_pages()

672

702

        self._root_node = None

673

703

        self._base_offset = offset

 

704

        self._leaf_factory = _LeafNode

674

705

        # Default max size is 100,000 leave values

675

706

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

676

707

        if unlimited_cache:

689

720

    def __eq__(self, other):

690

721

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

691

722

        return (

692

 

            type(self) == type(other) and

 

723

            isinstance(self, type(other)) and

693

724

            self._transport == other._transport and

694

725

            self._name == other._name and

695

726

            self._size == other._size)

787

818

        if total_pages - len(cached_offsets) <= self._recommended_pages:

788

819

            # Read whatever is left

789

820

            if cached_offsets:

790

 

                expanded = [x for x in xrange(total_pages)

 

821

                expanded = [x for x in range(total_pages)

791

822

                               if x not in cached_offsets]

792

823

            else:

793

 

                expanded = range(total_pages)

 

824

                expanded = list(range(total_pages))

794

825

            if 'index' in debug.debug_flags:

795

826

                trace.mutter('  reading all unread pages: %s', expanded)

796

827

            return expanded

949

980

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

950

981

        if self._leaf_value_cache is not None:

951

982

            for node in nodes.itervalues():

952

 

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

 

983

                for key, value in node.all_items():

953

984

                    if key in self._leaf_value_cache:

954

985

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

955

986

                        # before.

979

1010

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

980

1011

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

981

1012

            if self.node_ref_lists:

982

 

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

 

1013

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

983

1014

                    yield (self, key, value, refs)

984

1015

            else:

985

 

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

 

1016

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

986

1017

                    yield (self, key, value)

987

1018

            return

988

1019

        start_of_leaves = self._row_offsets[-2]

989

1020

        end_of_leaves = self._row_offsets[-1]

990

 

        needed_offsets = range(start_of_leaves, end_of_leaves)

 

1021

        needed_offsets = list(range(start_of_leaves, end_of_leaves))

991

1022

        if needed_offsets == [0]:

992

1023

            # Special case when we only have a root node, as we have already

993

1024

            # read everything

998

1029

        # for spilling index builds to disk.

999

1030

        if self.node_ref_lists:

1000

1031

            for _, node in nodes:

1001

 

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

 

1032

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

1002

1033

                    yield (self, key, value, refs)

1003

1034

        else:

1004

1035

            for _, node in nodes:

1005

 

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

 

1036

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

1006

1037

                    yield (self, key, value)

1007

1038

 

1008

1039

    @staticmethod

1032

1063

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

1033

1064

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

1034

1065

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

1035

 

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

 

1066

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

1036

1067

        # elif bisect_steps < iter_steps:

1037

1068

        #     offsets = {}

1038

1069

        #     for key in in_keys:

1041

1072

        #     return [(o, offsets[o]) for o in sorted(offsets)]

1042

1073

        in_keys_iter = iter(in_keys)

1043

1074

        fixed_keys_iter = enumerate(fixed_keys)

1044

 

        cur_in_key = in_keys_iter.next()

1045

 

        cur_fixed_offset, cur_fixed_key = fixed_keys_iter.next()

 

1075

        cur_in_key = next(in_keys_iter)

 

1076

        cur_fixed_offset, cur_fixed_key = next(fixed_keys_iter)

1046

1077

 

1047

1078

        class InputDone(Exception): pass

1048

1079

        class FixedDone(Exception): pass

1064

1095

                    while cur_in_key < cur_fixed_key:

1065

1096

                        cur_keys.append(cur_in_key)

1066

1097

                        try:

1067

 

                            cur_in_key = in_keys_iter.next()

 

1098

                            cur_in_key = next(in_keys_iter)

1068

1099

                        except StopIteration:

1069

1100

                            raise InputDone

1070

1101

                    # At this point cur_in_key must be >= cur_fixed_key

1072

1103

                # the end

1073

1104

                while cur_in_key >= cur_fixed_key:

1074

1105

                    try:

1075

 

                        cur_fixed_offset, cur_fixed_key = fixed_keys_iter.next()

 

1106

                        cur_fixed_offset, cur_fixed_key = next(fixed_keys_iter)

1076

1107

                    except StopIteration:

1077

1108

                        raise FixedDone

1078

1109

        except InputDone:

1169

1200

                continue

1170

1201

            node = nodes[node_index]

1171

1202

            for next_sub_key in sub_keys:

1172

 

                if next_sub_key in node.keys:

1173

 

                    value, refs = node.keys[next_sub_key]

 

1203

                if next_sub_key in node:

 

1204

                    value, refs = node[next_sub_key]

1174

1205

                    if self.node_ref_lists:

1175

1206

                        yield (self, next_sub_key, value, refs)

1176

1207

                    else:

1244

1275

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

1245

1276

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

1246

1277

            node = nodes[node_index]

1247

 

            node_keys = node.keys

1248

1278

            parents_to_check = set()

1249

1279

            for next_sub_key in sub_keys:

1250

 

                if next_sub_key not in node_keys:

 

1280

                if next_sub_key not in node:

1251

1281

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

1252

1282

                    missing_keys.add(next_sub_key)

1253

1283

                else:

1254

 

                    value, refs = node_keys[next_sub_key]

 

1284

                    value, refs = node[next_sub_key]

1255

1285

                    parent_keys = refs[ref_list_num]

1256

1286

                    parent_map[next_sub_key] = parent_keys

1257

1287

                    parents_to_check.update(parent_keys)

1264

1294

            while parents_to_check:

1265

1295

                next_parents_to_check = set()

1266

1296

                for key in parents_to_check:

1267

 

                    if key in node_keys:

1268

 

                        value, refs = node_keys[key]

 

1297

                    if key in node:

 

1298

                        value, refs = node[key]

1269

1299

                        parent_keys = refs[ref_list_num]

1270

1300

                        parent_map[key] = parent_keys

1271

1301

                        next_parents_to_check.update(parent_keys)

1333

1363

            self._get_root_node()

1334

1364

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

1335

1365

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

 

1366

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

1337

1367

        nodes = {}

1338

1368

        if self.node_ref_lists:

1339

1369

            if self._key_length == 1:

1401

1431

                while dicts:

1402

1432

                    key_dict = dicts.pop(-1)

1403

1433

                    # can't be empty or would not exist

1404

 

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

1405

 

                    if type(value) == dict:

 

1434

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

 

1435

                    if isinstance(value, dict):

1406

1436

                        # push keys

1407

1437

                        dicts.extend(key_dict.itervalues())

1408

1438

                    else:

1471

1501

        if not options_line.startswith(_OPTION_ROW_LENGTHS):

1472

1502

            raise errors.BadIndexOptions(self)

1473

1503

        try:

1474

 

            self._row_lengths = map(int, [length for length in

 

1504

            self._row_lengths = [int(length) for length in

1475

1505

                options_line[len(_OPTION_ROW_LENGTHS):].split(',')

1476

 

                if len(length)])

 

1506

                if length]

1477

1507

        except ValueError:

1478

1508

            raise errors.BadIndexOptions(self)

1479

1509

        self._compute_row_offsets()

1514

1544

                    self._size = num_bytes - base_offset

1515

1545

                    # the whole thing should be parsed out of 'bytes'

1516

1546

                    ranges = [(start, min(_PAGE_SIZE, num_bytes - start))

1517

 

                        for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]

 

1547

                        for start in range(base_offset, num_bytes, _PAGE_SIZE)]

1518

1548

                    break

1519

1549

            else:

1520

1550

                if offset > self._size:

1545

1575

                    continue

1546

1576

            bytes = zlib.decompress(data)

1547

1577

            if bytes.startswith(_LEAF_FLAG):

1548

 

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

 

1578

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

 

1579

                                          self.node_ref_lists)

1549

1580

            elif bytes.startswith(_INTERNAL_FLAG):

1550

1581

                node = _InternalNode(bytes)

1551

1582

            else:

1566

1597

            # We shouldn't be reading anything anyway

1567

1598

            start_node = 1

1568

1599

        node_end = self._row_offsets[-1]

1569

 

        for node in self._read_nodes(range(start_node, node_end)):

 

1600

        for node in self._read_nodes(list(range(start_node, node_end))):

1570

1601

            pass

1571

1602

 

1572

1603

 

 

1604

_gcchk_factory = _LeafNode

 

1605

 

1573

1606

try:

1574

 

    from bzrlib import _btree_serializer_pyx as _btree_serializer

1575

 

except ImportError, e:

 

1607

    from breezy import _btree_serializer_pyx as _btree_serializer

 

1608

    _gcchk_factory = _btree_serializer._parse_into_chk

 

1609

except ImportError as e:

1576

1610

    osutils.failed_to_load_extension(e)

1577

 

    from bzrlib import _btree_serializer_py as _btree_serializer

 

1611

    from breezy import _btree_serializer_py as _btree_serializer

• Older »

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