/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 4807)
• stop comparing with revision 4807

Show diffs side-by-side

added

removed

bzrlib/btree_index.py

1

 

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

31

31

    index,

32

32

    lru_cache,

33

33

    osutils,

 

34

    static_tuple,

34

35

    trace,

35

36

    )

36

37

from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN

159

160

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

160

161

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

161

162

        """

 

163

        # Ensure that 'key' is a StaticTuple

 

164

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

162

165

        # we don't care about absent_references

163

166

        node_refs, _ = self._check_key_ref_value(key, references, value)

164

167

        if key in self._nodes:

165

168

            raise errors.BadIndexDuplicateKey(key, self)

166

 

        # TODO: StaticTuple

167

 

        self._nodes[key] = (node_refs, value)

168

 

        self._keys.add(key)

 

169

        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)

169

170

        if self._nodes_by_key is not None and self._key_length > 1:

170

171

            self._update_nodes_by_key(key, value, node_refs)

171

 

        if len(self._keys) < self._spill_at:

 

172

        if len(self._nodes) < self._spill_at:

172

173

            return

173

174

        self._spill_mem_keys_to_disk()

174

175

 

203

204

                self._backing_indices[backing_pos] = None

204

205

        else:

205

206

            self._backing_indices.append(new_backing)

206

 

        self._keys = set()

207

207

        self._nodes = {}

208

208

        self._nodes_by_key = None

209

209

 

463

463

            efficient order for the index (keys iteration order in this case).

464

464

        """

465

465

        keys = set(keys)

466

 

        local_keys = keys.intersection(self._keys)

 

466

        # Note: We don't use keys.intersection() here. If you read the C api,

 

467

        #       set.intersection(other) special cases when other is a set and

 

468

        #       will iterate the smaller of the two and lookup in the other.

 

469

        #       It does *not* do this for any other type (even dict, unlike

 

470

        #       some other set functions.) Since we expect keys is generally <<

 

471

        #       self._nodes, it is faster to iterate over it in a list

 

472

        #       comprehension

 

473

        nodes = self._nodes

 

474

        local_keys = [key for key in keys if key in nodes]

467

475

        if self.reference_lists:

468

476

            for key in local_keys:

469

 

                node = self._nodes[key]

 

477

                node = nodes[key]

470

478

                yield self, key, node[1], node[0]

471

479

        else:

472

480

            for key in local_keys:

473

 

                node = self._nodes[key]

 

481

                node = nodes[key]

474

482

                yield self, key, node[1]

475

483

        # Find things that are in backing indices that have not been handled

476

484

        # yet.

559

567

                    else:

560

568

                        # yield keys

561

569

                        for value in key_dict.itervalues():

562

 

                            yield (self, ) + value

 

570

                            yield (self, ) + tuple(value)

563

571

            else:

564

572

                yield (self, ) + key_dict

565

573

 

586

594

 

587

595

        For InMemoryGraphIndex the estimate is exact.

588

596

        """

589

 

        return len(self._keys) + sum(backing.key_count() for backing in

 

597

        return len(self._nodes) + sum(backing.key_count() for backing in

590

598

            self._backing_indices if backing is not None)

591

599

 

592

600

    def validate(self):

624

632

    def _parse_lines(self, lines):

625

633

        nodes = []

626

634

        self.offset = int(lines[1][7:])

 

635

        as_st = static_tuple.StaticTuple.from_sequence

627

636

        for line in lines[2:]:

628

637

            if line == '':

629

638

                break

630

 

            # TODO: Switch to StaticTuple here.

631

 

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

 

639

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

632

640

        return nodes

633

641

 

634

642

 

639

647

    memory except when very large walks are done.

640

648

    """

641

649

 

642

 

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

 

650

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

 

651

                 offset=0):

643

652

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

644

653

 

645

654

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

652

661

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

653

662

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

654

663

            cache all leaf nodes.

 

664

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

 

665

            file. Instead it starts at some point later.

655

666

        """

656

667

        self._transport = transport

657

668

        self._name = name

659

670

        self._file = None

660

671

        self._recommended_pages = self._compute_recommended_pages()

661

672

        self._root_node = None

 

673

        self._base_offset = offset

662

674

        # Default max size is 100,000 leave values

663

675

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

664

676

        if unlimited_cache:

1486

1498

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

1487

1499

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

1488

1500

        ranges = []

 

1501

        base_offset = self._base_offset

1489

1502

        for index in nodes:

1490

 

            offset = index * _PAGE_SIZE

 

1503

            offset = (index * _PAGE_SIZE)

1491

1504

            size = _PAGE_SIZE

1492

1505

            if index == 0:

1493

1506

                # Root node - special case

1497

1510

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

1498

1511

                    # small indexes. So we read the whole thing

1499

1512

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

1500

 

                    self._size = len(bytes)

 

1513

                    num_bytes = len(bytes)

 

1514

                    self._size = num_bytes - base_offset

1501

1515

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

1502

 

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

 

1516

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

 

1517

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

1503

1518

                    break

1504

1519

            else:

1505

1520

                if offset > self._size:

1507

1522

                                         ' of the file %s > %s'

1508

1523

                                         % (offset, self._size))

1509

1524

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

1510

 

            ranges.append((offset, size))

 

1525

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

1511

1526

        if not ranges:

1512

1527

            return

1513

1528

        elif bytes is not None:

1514

1529

            # already have the whole file

1515

 

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

1516

 

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

 

1530

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

 

1531

                           for start, size in ranges]

1517

1532

        elif self._file is None:

1518

1533

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

1519

1534

        else:

1522

1537

                self._file.seek(offset)

1523

1538

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

1524

1539

        for offset, data in data_ranges:

 

1540

            offset -= base_offset

1525

1541

            if offset == 0:

1526

1542

                # extract the header

1527

1543

                offset, data = self._parse_header_from_bytes(data)

• Older »

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