~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

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

• reverse the comparison (5110 to 6621)
• stop comparing with revision 6621

Show diffs side-by-side

added

removed

bzrlib/btree_index.py

1

 

# Copyright (C) 2008-2011 Canonical Ltd

 

1

# Copyright (C) 2008, 2009, 2010 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

 

 

22

20

import cStringIO

23

 

 

24

 

from bzrlib.lazy_import import lazy_import

25

 

lazy_import(globals(), """

26

 

import bisect

 

21

from bisect import bisect_right

27

22

import math

28

23

import tempfile

29

24

import zlib

30

 

""")

31

25

 

32

26

from bzrlib import (

33

27

    chunk_writer,

39

33

    osutils,

40

34

    static_tuple,

41

35

    trace,

42

 

    transport,

43

36

    )

44

37

from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN

 

38

from bzrlib.transport import get_transport

45

39

 

46

40

 

47

41

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

164

158

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

165

159

            reference to another key.

166

160

        :param value: The value to associate with the key. It may be any

167

 

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

 

161

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

168

162

        """

169

163

        # Ensure that 'key' is a StaticTuple

170

164

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

199

193

            new_backing_file, size = self._spill_mem_keys_without_combining()

200

194

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

201

195

        #       direct access to the new_backing._file object

202

 

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

203

 

                                      '<temp>', size)

 

196

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

204

197

        # GC will clean up the file

205

198

        new_backing._file = new_backing_file

206

199

        if self._combine_backing_indices:

296

289

            flag when writing out. This is used by the _spill_mem_keys_to_disk

297

290

            functionality.

298

291

        """

299

 

        new_leaf = False

300

292

        if rows[-1].writer is None:

301

293

            # opening a new leaf chunk;

302

 

            new_leaf = True

303

294

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

304

295

                # flesh out any internal nodes that are needed to

305

296

                # preserve the height of the tree

324

315

                optimize_for_size=self._optimize_for_size)

325

316

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

326

317

        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)

332

318

            # this key did not fit in the node:

333

319

            rows[-1].finish_node()

334

320

            key_line = string_key + "\n"

615

601

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

616

602

 

617

603

 

618

 

class _LeafNode(dict):

 

604

class _LeafNode(object):

619

605

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

620

606

 

621

 

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

 

607

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

622

608

 

623

609

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

624

610

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

630

616

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

631

617

        else:

632

618

            self.min_key = self.max_key = None

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 = self.items()

639

 

        items.sort()

640

 

        return items

641

 

 

642

 

    def all_keys(self):

643

 

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

644

 

        keys = self.keys()

645

 

        keys.sort()

646

 

        return keys

 

619

        self.keys = dict(key_list)

647

620

 

648

621

 

649

622

class _InternalNode(object):

674

647

    memory except when very large walks are done.

675

648

    """

676

649

 

677

 

    def __init__(self, transport, name, size, unlimited_cache=False,

678

 

                 offset=0):

 

650

    def __init__(self, transport, name, size, unlimited_cache=False):

679

651

        """Create a B+Tree index object on the index name.

680

652

 

681

653

        :param transport: The transport to read data for the index from.

688

660

        :param unlimited_cache: If set to True, then instead of using an

689

661

            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always

690

662

            cache all leaf nodes.

691

 

        :param offset: The start of the btree index data isn't byte 0 of the

692

 

            file. Instead it starts at some point later.

693

663

        """

694

664

        self._transport = transport

695

665

        self._name = name

697

667

        self._file = None

698

668

        self._recommended_pages = self._compute_recommended_pages()

699

669

        self._root_node = None

700

 

        self._base_offset = offset

701

 

        self._leaf_factory = _LeafNode

702

670

        # Default max size is 100,000 leave values

703

671

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

704

672

        if unlimited_cache:

977

945

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

978

946

        if self._leaf_value_cache is not None:

979

947

            for node in nodes.itervalues():

980

 

                for key, value in node.all_items():

 

948

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

981

949

                    if key in self._leaf_value_cache:

982

950

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

983

951

                        # before.

1007

975

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

1008

976

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

1009

977

            if self.node_ref_lists:

1010

 

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

 

978

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

1011

979

                    yield (self, key, value, refs)

1012

980

            else:

1013

 

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

 

981

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

1014

982

                    yield (self, key, value)

1015

983

            return

1016

984

        start_of_leaves = self._row_offsets[-2]

1026

994

        # for spilling index builds to disk.

1027

995

        if self.node_ref_lists:

1028

996

            for _, node in nodes:

1029

 

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

 

997

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

1030

998

                    yield (self, key, value, refs)

1031

999

        else:

1032

1000

            for _, node in nodes:

1033

 

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

 

1001

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

1034

1002

                    yield (self, key, value)

1035

1003

 

1036

1004

    @staticmethod

1060

1028

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

1061

1029

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

1062

1030

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

1063

 

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

 

1031

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

1064

1032

        # elif bisect_steps < iter_steps:

1065

1033

        #     offsets = {}

1066

1034

        #     for key in in_keys:

1197

1165

                continue

1198

1166

            node = nodes[node_index]

1199

1167

            for next_sub_key in sub_keys:

1200

 

                if next_sub_key in node:

1201

 

                    value, refs = node[next_sub_key]

 

1168

                if next_sub_key in node.keys:

 

1169

                    value, refs = node.keys[next_sub_key]

1202

1170

                    if self.node_ref_lists:

1203

1171

                        yield (self, next_sub_key, value, refs)

1204

1172

                    else:

1272

1240

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

1273

1241

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

1274

1242

            node = nodes[node_index]

 

1243

            node_keys = node.keys

1275

1244

            parents_to_check = set()

1276

1245

            for next_sub_key in sub_keys:

1277

 

                if next_sub_key not in node:

 

1246

                if next_sub_key not in node_keys:

1278

1247

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

1279

1248

                    missing_keys.add(next_sub_key)

1280

1249

                else:

1281

 

                    value, refs = node[next_sub_key]

 

1250

                    value, refs = node_keys[next_sub_key]

1282

1251

                    parent_keys = refs[ref_list_num]

1283

1252

                    parent_map[next_sub_key] = parent_keys

1284

1253

                    parents_to_check.update(parent_keys)

1291

1260

            while parents_to_check:

1292

1261

                next_parents_to_check = set()

1293

1262

                for key in parents_to_check:

1294

 

                    if key in node:

1295

 

                        value, refs = node[key]

 

1263

                    if key in node_keys:

 

1264

                        value, refs = node_keys[key]

1296

1265

                        parent_keys = refs[ref_list_num]

1297

1266

                        parent_map[key] = parent_keys

1298

1267

                        next_parents_to_check.update(parent_keys)

1525

1494

        # list of (offset, length) regions of the file that should, evenually

1526

1495

        # be read in to data_ranges, either from 'bytes' or from the transport

1527

1496

        ranges = []

1528

 

        base_offset = self._base_offset

1529

1497

        for index in nodes:

1530

 

            offset = (index * _PAGE_SIZE)

 

1498

            offset = index * _PAGE_SIZE

1531

1499

            size = _PAGE_SIZE

1532

1500

            if index == 0:

1533

1501

                # Root node - special case

1537

1505

                    # The only case where we don't know the size, is for very

1538

1506

                    # small indexes. So we read the whole thing

1539

1507

                    bytes = self._transport.get_bytes(self._name)

1540

 

                    num_bytes = len(bytes)

1541

 

                    self._size = num_bytes - base_offset

 

1508

                    self._size = len(bytes)

1542

1509

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

1543

 

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

1544

 

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

 

1510

                    ranges.append((0, len(bytes)))

1545

1511

                    break

1546

1512

            else:

1547

1513

                if offset > self._size:

1549

1515

                                         ' of the file %s > %s'

1550

1516

                                         % (offset, self._size))

1551

1517

                size = min(size, self._size - offset)

1552

 

            ranges.append((base_offset + offset, size))

 

1518

            ranges.append((offset, size))

1553

1519

        if not ranges:

1554

1520

            return

1555

1521

        elif bytes is not None:

1556

1522

            # already have the whole file

1557

 

            data_ranges = [(start, bytes[start:start+size])

1558

 

                           for start, size in ranges]

 

1523

            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])

 

1524

                           for start in xrange(0, len(bytes), _PAGE_SIZE)]

1559

1525

        elif self._file is None:

1560

1526

            data_ranges = self._transport.readv(self._name, ranges)

1561

1527

        else:

1564

1530

                self._file.seek(offset)

1565

1531

                data_ranges.append((offset, self._file.read(size)))

1566

1532

        for offset, data in data_ranges:

1567

 

            offset -= base_offset

1568

1533

            if offset == 0:

1569

1534

                # extract the header

1570

1535

                offset, data = self._parse_header_from_bytes(data)

1572

1537

                    continue

1573

1538

            bytes = zlib.decompress(data)

1574

1539

            if bytes.startswith(_LEAF_FLAG):

1575

 

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

1576

 

                                          self.node_ref_lists)

 

1540

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

1577

1541

            elif bytes.startswith(_INTERNAL_FLAG):

1578

1542

                node = _InternalNode(bytes)

1579

1543

            else:

1598

1562

            pass

1599

1563

 

1600

1564

 

1601

 

_gcchk_factory = _LeafNode

1602

 

 

1603

1565

try:

1604

1566

    from bzrlib import _btree_serializer_pyx as _btree_serializer

1605

 

    _gcchk_factory = _btree_serializer._parse_into_chk

1606

1567

except ImportError, e:

1607

1568

    osutils.failed_to_load_extension(e)

1608

1569

    from bzrlib import _btree_serializer_py as _btree_serializer

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.1