~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

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

• reverse the comparison (4988.4.2 to 5200.3.1)
• stop comparing with revision 5200.3.1

Show diffs side-by-side

added

removed

bzrlib/index.py

1

 

# Copyright (C) 2007-2010 Canonical Ltd

 

1

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

382

382

    suitable for production use. :XXX

383

383

    """

384

384

 

385

 

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

 

385

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

386

386

        """Open an index called name on transport.

387

387

 

388

388

        :param transport: A bzrlib.transport.Transport.

394

394

            avoided by having it supplied. If size is None, then bisection

395

395

            support will be disabled and accessing the index will just stream

396

396

            all the data.

397

 

        :param offset: Instead of starting the index data at offset 0, start it

398

 

            at an arbitrary offset.

399

397

        """

400

398

        self._transport = transport

401

399

        self._name = name

418

416

        self._size = size

419

417

        # The number of bytes we've read so far in trying to process this file

420

418

        self._bytes_read = 0

421

 

        self._base_offset = offset

422

419

 

423

420

    def __eq__(self, other):

424

421

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

447

444

            mutter('Reading entire index %s', self._transport.abspath(self._name))

448

445

        if stream is None:

449

446

            stream = self._transport.get(self._name)

450

 

            if self._base_offset != 0:

451

 

                # This is wasteful, but it is better than dealing with

452

 

                # adjusting all the offsets, etc.

453

 

                stream = StringIO(stream.read()[self._base_offset:])

454

447

        self._read_prefix(stream)

455

448

        self._expected_elements = 3 + self._key_length

456

449

        line_count = 0

1197

1190

            self._buffer_all()

1198

1191

            return

1199

1192

 

1200

 

        base_offset = self._base_offset

1201

 

        if base_offset != 0:

1202

 

            # Rewrite the ranges for the offset

1203

 

            readv_ranges = [(start+base_offset, size)

1204

 

                            for start, size in readv_ranges]

1205

1193

        readv_data = self._transport.readv(self._name, readv_ranges, True,

1206

 

            self._size + self._base_offset)

 

1194

            self._size)

1207

1195

        # parse

1208

1196

        for offset, data in readv_data:

1209

 

            offset -= base_offset

1210

1197

            self._bytes_read += len(data)

1211

 

            if offset < 0:

1212

 

                # transport.readv() expanded to extra data which isn't part of

1213

 

                # this index

1214

 

                data = data[-offset:]

1215

 

                offset = 0

1216

1198

            if offset == 0 and len(data) == self._size:

1217

1199

                # We read the whole range, most likely because the

1218

1200

                # Transport upcast our readv ranges into one long request

1245

1227

    static data.

1246

1228

 

1247

1229

    Queries against the combined index will be made against the first index,

1248

 

    and then the second and so on. The order of indices can thus influence

 

1230

    and then the second and so on. The order of index's can thus influence

1249

1231

    performance significantly. For example, if one index is on local disk and a

1250

1232

    second on a remote server, the local disk index should be before the other

1251

1233

    in the index list.

1252

 

    

1253

 

    Also, queries tend to need results from the same indices as previous

1254

 

    queries.  So the indices will be reordered after every query to put the

1255

 

    indices that had the result(s) of that query first (while otherwise

1256

 

    preserving the relative ordering).

1257

1234

    """

1258

1235

 

1259

1236

    def __init__(self, indices, reload_func=None):

1266

1243

        """

1267

1244

        self._indices = indices

1268

1245

        self._reload_func = reload_func

1269

 

        # Sibling indices are other CombinedGraphIndex that we should call

1270

 

        # _move_to_front_by_name on when we auto-reorder ourself.

1271

 

        self._sibling_indices = []

1272

 

        # A list of names that corresponds to the instances in self._indices,

1273

 

        # so _index_names[0] is always the name for _indices[0], etc.  Sibling

1274

 

        # indices must all use the same set of names as each other.

1275

 

        self._index_names = [None] * len(self._indices)

1276

1246

 

1277

1247

    def __repr__(self):

1278

1248

        return "%s(%s)" % (

1301

1271

 

1302

1272

    has_key = _has_key_from_parent_map

1303

1273

 

1304

 

    def insert_index(self, pos, index, name=None):

 

1274

    def insert_index(self, pos, index):

1305

1275

        """Insert a new index in the list of indices to query.

1306

1276

 

1307

1277

        :param pos: The position to insert the index.

1308

1278

        :param index: The index to insert.

1309

 

        :param name: a name for this index, e.g. a pack name.  These names can

1310

 

            be used to reflect index reorderings to related CombinedGraphIndex

1311

 

            instances that use the same names.  (see set_sibling_indices)

1312

1279

        """

1313

1280

        self._indices.insert(pos, index)

1314

 

        self._index_names.insert(pos, name)

1315

1281

 

1316

1282

    def iter_all_entries(self):

1317

1283

        """Iterate over all keys within the index

1342

1308

        value and are only reported once.

1343

1309

 

1344

1310

        :param keys: An iterable providing the keys to be retrieved.

1345

 

        :return: An iterable of (index, key, reference_lists, value). There is

1346

 

            no defined order for the result iteration - it will be in the most

 

1311

        :return: An iterable of (index, key, reference_lists, value). There is no

 

1312

            defined order for the result iteration - it will be in the most

1347

1313

            efficient order for the index.

1348

1314

        """

1349

1315

        keys = set(keys)

1350

 

        hit_indices = []

1351

1316

        while True:

1352

1317

            try:

1353

1318

                for index in self._indices:

1354

1319

                    if not keys:

1355

 

                        break

1356

 

                    index_hit = False

 

1320

                        return

1357

1321

                    for node in index.iter_entries(keys):

1358

1322

                        keys.remove(node[1])

1359

1323

                        yield node

1360

 

                        index_hit = True

1361

 

                    if index_hit:

1362

 

                        hit_indices.append(index)

1363

 

                break

 

1324

                return

1364

1325

            except errors.NoSuchFile:

1365

1326

                self._reload_or_raise()

1366

 

        self._move_to_front(hit_indices)

1367

1327

 

1368

1328

    def iter_entries_prefix(self, keys):

1369

1329

        """Iterate over keys within the index using prefix matching.

1389

1349

        if not keys:

1390

1350

            return

1391

1351

        seen_keys = set()

1392

 

        hit_indices = []

1393

1352

        while True:

1394

1353

            try:

1395

1354

                for index in self._indices:

1396

 

                    index_hit = False

1397

1355

                    for node in index.iter_entries_prefix(keys):

1398

1356

                        if node[1] in seen_keys:

1399

1357

                            continue

1400

1358

                        seen_keys.add(node[1])

1401

1359

                        yield node

1402

 

                        index_hit = True

1403

 

                    if index_hit:

1404

 

                        hit_indices.append(index)

1405

 

                break

 

1360

                return

1406

1361

            except errors.NoSuchFile:

1407

1362

                self._reload_or_raise()

1408

 

        self._move_to_front(hit_indices)

1409

 

 

1410

 

    def _move_to_front(self, hit_indices):

1411

 

        """Rearrange self._indices so that hit_indices are first.

1412

 

 

1413

 

        Order is maintained as much as possible, e.g. the first unhit index

1414

 

        will be the first index in _indices after the hit_indices, and the

1415

 

        hit_indices will be present in exactly the order they are passed to

1416

 

        _move_to_front.

1417

 

 

1418

 

        _move_to_front propagates to all objects in self._sibling_indices by

1419

 

        calling _move_to_front_by_name.

1420

 

        """

1421

 

        if self._indices[:len(hit_indices)] == hit_indices:

1422

 

            # The 'hit_indices' are already at the front (and in the same

1423

 

            # order), no need to re-order

1424

 

            return

1425

 

        hit_names = self._move_to_front_by_index(hit_indices)

1426

 

        for sibling_idx in self._sibling_indices:

1427

 

            sibling_idx._move_to_front_by_name(hit_names)

1428

 

 

1429

 

    def _move_to_front_by_index(self, hit_indices):

1430

 

        """Core logic for _move_to_front.

1431

 

        

1432

 

        Returns a list of names corresponding to the hit_indices param.

1433

 

        """

1434

 

        indices_info = zip(self._index_names, self._indices)

1435

 

        if 'index' in debug.debug_flags:

1436

 

            mutter('CombinedGraphIndex reordering: currently %r, promoting %r',

1437

 

                   indices_info, hit_indices)

1438

 

        hit_names = []

1439

 

        unhit_names = []

1440

 

        new_hit_indices = []

1441

 

        unhit_indices = []

1442

 

 

1443

 

        for offset, (name, idx) in enumerate(indices_info):

1444

 

            if idx in hit_indices:

1445

 

                hit_names.append(name)

1446

 

                new_hit_indices.append(idx)

1447

 

                if len(new_hit_indices) == len(hit_indices):

1448

 

                    # We've found all of the hit entries, everything else is

1449

 

                    # unhit

1450

 

                    unhit_names.extend(self._index_names[offset+1:])

1451

 

                    unhit_indices.extend(self._indices[offset+1:])

1452

 

                    break

1453

 

            else:

1454

 

                unhit_names.append(name)

1455

 

                unhit_indices.append(idx)

1456

 

 

1457

 

        self._indices = new_hit_indices + unhit_indices

1458

 

        self._index_names = hit_names + unhit_names

1459

 

        if 'index' in debug.debug_flags:

1460

 

            mutter('CombinedGraphIndex reordered: %r', self._indices)

1461

 

        return hit_names

1462

 

 

1463

 

    def _move_to_front_by_name(self, hit_names):

1464

 

        """Moves indices named by 'hit_names' to front of the search order, as

1465

 

        described in _move_to_front.

1466

 

        """

1467

 

        # Translate names to index instances, and then call

1468

 

        # _move_to_front_by_index.

1469

 

        indices_info = zip(self._index_names, self._indices)

1470

 

        hit_indices = []

1471

 

        for name, idx in indices_info:

1472

 

            if name in hit_names:

1473

 

                hit_indices.append(idx)

1474

 

        self._move_to_front_by_index(hit_indices)

1475

1363

 

1476

1364

    def find_ancestry(self, keys, ref_list_num):

1477

1365

        """Find the complete ancestry for the given set of keys.

1484

1372

            we care about.

1485

1373

        :return: (parent_map, missing_keys)

1486

1374

        """

1487

 

        # XXX: make this call _move_to_front?

1488

1375

        missing_keys = set()

1489

1376

        parent_map = {}

1490

1377

        keys_to_lookup = set(keys)

1570

1457

                         ' Raising original exception.')

1571

1458

            raise exc_type, exc_value, exc_traceback

1572

1459

 

1573

 

    def set_sibling_indices(self, sibling_combined_graph_indices):

1574

 

        """Set the CombinedGraphIndex objects to reorder after reordering self.

1575

 

        """

1576

 

        self._sibling_indices = sibling_combined_graph_indices

1577

 

 

1578

1460

    def validate(self):

1579

1461

        """Validate that everything in the index can be accessed."""

1580

1462

        while True:

• Older »

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