/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/index.py

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

Show diffs side-by-side

added

removed

bzrlib/index.py

56

56

def _has_key_from_parent_map(self, key):

57

57

    """Check if this index has one key.

58

58

 

59

 

    If it's possible to check for multiple keys at once through 

 

59

    If it's possible to check for multiple keys at once through

60

60

    calling get_parent_map that should be faster.

61

61

    """

62

62

    return (key in self.get_parent_map([key]))

68

68

 

69

69

class GraphIndexBuilder(object):

70

70

    """A builder that can build a GraphIndex.

71

 

    

 

71

 

72

72

    The resulting graph has the structure:

73

 

    

 

73

 

74

74

    _SIGNATURE OPTIONS NODES NEWLINE

75

75

    _SIGNATURE     := 'Bazaar Graph Index 1' NEWLINE

76

76

    OPTIONS        := 'node_ref_lists=' DIGITS NEWLINE

246

246

        # one to pad all the data with reference-length and determine entry

247

247

        # addresses.

248

248

        # One to serialise.

249

 

        

 

249

 

250

250

        # forward sorted by key. In future we may consider topological sorting,

251

251

        # at the cost of table scans for direct lookup, or a second index for

252

252

        # direct lookup

329

329

 

330

330

class GraphIndex(object):

331

331

    """An index for data with embedded graphs.

332

 

 

 

332

 

333

333

    The index maps keys to a list of key reference lists, and a value.

334

334

    Each node has the same number of key reference lists. Each key reference

335

335

    list can be empty or an arbitrary length. The value is an opaque NULL

336

 

    terminated string without any newlines. The storage of the index is 

 

336

    terminated string without any newlines. The storage of the index is

337

337

    hidden in the interface: keys and key references are always tuples of

338

338

    bytestrings, never the internal representation (e.g. dictionary offsets).

339

339

 

435

435

            # there must be one line - the empty trailer line.

436

436

            raise errors.BadIndexData(self)

437

437

 

 

438

    def external_references(self, ref_list_num):

 

439

        """Return references that are not present in this index.

 

440

        """

 

441

        self._buffer_all()

 

442

        if ref_list_num + 1 > self.node_ref_lists:

 

443

            raise ValueError('No ref list %d, index has %d ref lists'

 

444

                % (ref_list_num, self.node_ref_lists))

 

445

        refs = set()

 

446

        for key, (value, ref_lists) in self._nodes.iteritems():

 

447

            ref_list = ref_lists[ref_list_num]

 

448

            refs.update(ref_list)

 

449

        return refs - self._keys

 

450

 

438

451

    def _get_nodes_by_key(self):

439

452

        if self._nodes_by_key is None:

440

453

            nodes_by_key = {}

502

515

 

503

516

    def _resolve_references(self, references):

504

517

        """Return the resolved key references for references.

505

 

        

 

518

 

506

519

        References are resolved by looking up the location of the key in the

507

520

        _keys_by_offset map and substituting the key name, preserving ordering.

508

521

 

509

 

        :param references: An iterable of iterables of key locations. e.g. 

 

522

        :param references: An iterable of iterables of key locations. e.g.

510

523

            [[123, 456], [123]]

511

524

        :return: A tuple of tuples of keys.

512

525

        """

670

683

                    # can't be empty or would not exist

671

684

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

672

685

                    if type(value) == dict:

673

 

                        # push keys 

 

686

                        # push keys

674

687

                        dicts.extend(key_dict.itervalues())

675

688

                    else:

676

689

                        # yield keys

684

697

 

685

698

    def key_count(self):

686

699

        """Return an estimate of the number of keys in this index.

687

 

        

 

700

 

688

701

        For GraphIndex the estimate is exact.

689

702

        """

690

703

        if self._key_count is None:

706

719

        # Possible improvements:

707

720

        #  - only bisect lookup each key once

708

721

        #  - sort the keys first, and use that to reduce the bisection window

709

 

        # ----- 

 

722

        # -----

710

723

        # this progresses in three parts:

711

724

        # read data

712

725

        # parse it

721

734

                # We have the key parsed.

722

735

                continue

723

736

            index = self._parsed_key_index(key)

724

 

            if (len(self._parsed_key_map) and 

 

737

            if (len(self._parsed_key_map) and

725

738

                self._parsed_key_map[index][0] <= key and

726

739

                (self._parsed_key_map[index][1] >= key or

727

740

                 # end of the file has been parsed

731

744

                continue

732

745

            # - if we have examined this part of the file already - yes

733

746

            index = self._parsed_byte_index(location)

734

 

            if (len(self._parsed_byte_map) and 

 

747

            if (len(self._parsed_byte_map) and

735

748

                self._parsed_byte_map[index][0] <= location and

736

749

                self._parsed_byte_map[index][1] > location):

737

750

                # the byte region has been parsed, so no read is needed.

992

1005

        # adjust offset and data to the parseable data.

993

1006

        trimmed_data = data[trim_start:trim_end]

994

1007

        if not (trimmed_data):

995

 

            raise AssertionError('read unneeded data [%d:%d] from [%d:%d]' 

 

1008

            raise AssertionError('read unneeded data [%d:%d] from [%d:%d]'

996

1009

                % (trim_start, trim_end, offset, offset + len(data)))

997

1010

        if trim_start:

998

1011

            offset += trim_start

1143

1156

 

1144

1157

class CombinedGraphIndex(object):

1145

1158

    """A GraphIndex made up from smaller GraphIndices.

1146

 

    

 

1159

 

1147

1160

    The backing indices must implement GraphIndex, and are presumed to be

1148

1161

    static data.

1149

1162

 

1173

1186

    @symbol_versioning.deprecated_method(symbol_versioning.one_one)

1174

1187

    def get_parents(self, revision_ids):

1175

1188

        """See graph._StackedParentsProvider.get_parents.

1176

 

        

 

1189

 

1177

1190

        This implementation thunks the graph.Graph.get_parents api across to

1178

1191

        GraphIndex.

1179

1192

 

1428

1441

                    raise errors.BadIndexKey(key)

1429

1442

                node = self._nodes[key]

1430

1443

                if node[0]:

1431

 

                    continue 

 

1444

                    continue

1432

1445

                if self.reference_lists:

1433

1446

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

1434

1447

                else:

1459

1472

                    # can't be empty or would not exist

1460

1473

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

1461

1474

                    if type(value) == dict:

1462

 

                        # push keys 

 

1475

                        # push keys

1463

1476

                        dicts.extend(key_dict.itervalues())

1464

1477

                    else:

1465

1478

                        # yield keys

1470

1483

 

1471

1484

    def key_count(self):

1472

1485

        """Return an estimate of the number of keys in this index.

1473

 

        

 

1486

 

1474

1487

        For InMemoryGraphIndex the estimate is exact.

1475

1488

        """

1476

1489

        return len(self._keys)

1484

1497

 

1485

1498

    Queries against this will emit queries against the adapted Graph with the

1486

1499

    prefix added, queries for all items use iter_entries_prefix. The returned

1487

 

    nodes will have their keys and node references adjusted to remove the 

 

1500

    nodes will have their keys and node references adjusted to remove the

1488

1501

    prefix. Finally, an add_nodes_callback can be supplied - when called the

1489

1502

    nodes and references being added will have prefix prepended.

1490

1503

    """

1517

1530

                    adjusted_references))

1518

1531

        except ValueError:

1519

1532

            # XXX: TODO add an explicit interface for getting the reference list

1520

 

            # status, to handle this bit of user-friendliness in the API more 

 

1533

            # status, to handle this bit of user-friendliness in the API more

1521

1534

            # explicitly.

1522

1535

            for (key, value) in nodes:

1523

1536

                translated_nodes.append((self.prefix + key, value))

1595

1608

 

1596

1609

    def key_count(self):

1597

1610

        """Return an estimate of the number of keys in this index.

1598

 

        

 

1611

 

1599

1612

        For GraphIndexPrefixAdapter this is relatively expensive - key

1600

1613

        iteration with the prefix is done.

1601

1614

        """

• Older »

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