~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

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

• reverse the comparison (4797.29.1 to 5401)
• stop comparing with revision 5401

Show diffs side-by-side

added

removed

bzrlib/index.py

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

462

455

        trailers = 0

463

456

        pos = stream.tell()

464

457

        lines = stream.read().split('\n')

465

 

        # GZ 2009-09-20: Should really use a try/finally block to ensure close

466

458

        stream.close()

467

459

        del lines[-1]

468

460

        _, _, _, trailers = self._parse_lines(lines, pos)

1198

1190

            self._buffer_all()

1199

1191

            return

1200

1192

 

1201

 

        base_offset = self._base_offset

1202

 

        if base_offset != 0:

1203

 

            # Rewrite the ranges for the offset

1204

 

            readv_ranges = [(start+base_offset, size)

1205

 

                            for start, size in readv_ranges]

1206

1193

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

1207

 

            self._size + self._base_offset)

 

1194

            self._size)

1208

1195

        # parse

1209

1196

        for offset, data in readv_data:

1210

 

            offset -= base_offset

1211

1197

            self._bytes_read += len(data)

1212

 

            if offset < 0:

1213

 

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

1214

 

                # this index

1215

 

                data = data[-offset:]

1216

 

                offset = 0

1217

1198

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

1218

1199

                # We read the whole range, most likely because the

1219

1200

                # Transport upcast our readv ranges into one long request

1246

1227

    static data.

1247

1228

 

1248

1229

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

1249

 

    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

1250

1231

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

1251

1232

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

1252

1233

    in the index list.

1253

 

    

1254

 

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

1255

 

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

1256

 

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

1257

 

    preserving the relative ordering).

1258

1234

    """

1259

1235

 

1260

1236

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

1267

1243

        """

1268

1244

        self._indices = indices

1269

1245

        self._reload_func = reload_func

1270

 

        # Sibling indices are other CombinedGraphIndex that we should call

1271

 

        # _move_to_front_by_name on when we auto-reorder ourself.

1272

 

        self._sibling_indices = []

1273

 

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

1274

 

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

1275

 

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

1276

 

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

1277

1246

 

1278

1247

    def __repr__(self):

1279

1248

        return "%s(%s)" % (

1302

1271

 

1303

1272

    has_key = _has_key_from_parent_map

1304

1273

 

1305

 

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

 

1274

    def insert_index(self, pos, index):

1306

1275

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

1307

1276

 

1308

1277

        :param pos: The position to insert the index.

1309

1278

        :param index: The index to insert.

1310

 

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

1311

 

            be used to reflect index reorderings to related CombinedGraphIndex

1312

 

            instances that use the same names.  (see set_sibling_indices)

1313

1279

        """

1314

1280

        self._indices.insert(pos, index)

1315

 

        self._index_names.insert(pos, name)

1316

1281

 

1317

1282

    def iter_all_entries(self):

1318

1283

        """Iterate over all keys within the index

1343

1308

        value and are only reported once.

1344

1309

 

1345

1310

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

1346

 

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

1347

 

            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

1348

1313

            efficient order for the index.

1349

1314

        """

1350

1315

        keys = set(keys)

1351

 

        hit_indices = []

1352

1316

        while True:

1353

1317

            try:

1354

1318

                for index in self._indices:

1355

1319

                    if not keys:

1356

 

                        break

1357

 

                    index_hit = False

 

1320

                        return

1358

1321

                    for node in index.iter_entries(keys):

1359

1322

                        keys.remove(node[1])

1360

1323

                        yield node

1361

 

                        index_hit = True

1362

 

                    if index_hit:

1363

 

                        hit_indices.append(index)

1364

 

                break

 

1324

                return

1365

1325

            except errors.NoSuchFile:

1366

1326

                self._reload_or_raise()

1367

 

        self._move_to_front(hit_indices)

1368

1327

 

1369

1328

    def iter_entries_prefix(self, keys):

1370

1329

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

1390

1349

        if not keys:

1391

1350

            return

1392

1351

        seen_keys = set()

1393

 

        hit_indices = []

1394

1352

        while True:

1395

1353

            try:

1396

1354

                for index in self._indices:

1397

 

                    index_hit = False

1398

1355

                    for node in index.iter_entries_prefix(keys):

1399

1356

                        if node[1] in seen_keys:

1400

1357

                            continue

1401

1358

                        seen_keys.add(node[1])

1402

1359

                        yield node

1403

 

                        index_hit = True

1404

 

                    if index_hit:

1405

 

                        hit_indices.append(index)

1406

 

                break

 

1360

                return

1407

1361

            except errors.NoSuchFile:

1408

1362

                self._reload_or_raise()

1409

 

        self._move_to_front(hit_indices)

1410

 

 

1411

 

    def _move_to_front(self, hit_indices):

1412

 

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

1413

 

 

1414

 

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

1415

 

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

1416

 

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

1417

 

        _move_to_front.

1418

 

 

1419

 

        _move_to_front propagates to all objects in self._sibling_indices by

1420

 

        calling _move_to_front_by_name.

1421

 

        """

1422

 

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

1423

 

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

1424

 

            # order), no need to re-order

1425

 

            return

1426

 

        hit_names = self._move_to_front_by_index(hit_indices)

1427

 

        for sibling_idx in self._sibling_indices:

1428

 

            sibling_idx._move_to_front_by_name(hit_names)

1429

 

 

1430

 

    def _move_to_front_by_index(self, hit_indices):

1431

 

        """Core logic for _move_to_front.

1432

 

        

1433

 

        Returns a list of names corresponding to the hit_indices param.

1434

 

        """

1435

 

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

1436

 

        if 'index' in debug.debug_flags:

1437

 

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

1438

 

                   indices_info, hit_indices)

1439

 

        hit_names = []

1440

 

        unhit_names = []

1441

 

        new_hit_indices = []

1442

 

        unhit_indices = []

1443

 

 

1444

 

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

1445

 

            if idx in hit_indices:

1446

 

                hit_names.append(name)

1447

 

                new_hit_indices.append(idx)

1448

 

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

1449

 

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

1450

 

                    # unhit

1451

 

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

1452

 

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

1453

 

                    break

1454

 

            else:

1455

 

                unhit_names.append(name)

1456

 

                unhit_indices.append(idx)

1457

 

 

1458

 

        self._indices = new_hit_indices + unhit_indices

1459

 

        self._index_names = hit_names + unhit_names

1460

 

        if 'index' in debug.debug_flags:

1461

 

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

1462

 

        return hit_names

1463

 

 

1464

 

    def _move_to_front_by_name(self, hit_names):

1465

 

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

1466

 

        described in _move_to_front.

1467

 

        """

1468

 

        # Translate names to index instances, and then call

1469

 

        # _move_to_front_by_index.

1470

 

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

1471

 

        hit_indices = []

1472

 

        for name, idx in indices_info:

1473

 

            if name in hit_names:

1474

 

                hit_indices.append(idx)

1475

 

        self._move_to_front_by_index(hit_indices)

1476

1363

 

1477

1364

    def find_ancestry(self, keys, ref_list_num):

1478

1365

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

1485

1372

            we care about.

1486

1373

        :return: (parent_map, missing_keys)

1487

1374

        """

1488

 

        # XXX: make this call _move_to_front?

1489

1375

        missing_keys = set()

1490

1376

        parent_map = {}

1491

1377

        keys_to_lookup = set(keys)

1571

1457

                         ' Raising original exception.')

1572

1458

            raise exc_type, exc_value, exc_traceback

1573

1459

 

1574

 

    def set_sibling_indices(self, sibling_combined_graph_indices):

1575

 

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

1576

 

        """

1577

 

        self._sibling_indices = sibling_combined_graph_indices

1578

 

 

1579

1460

    def validate(self):

1580

1461

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

1581

1462

        while True:

• Older »

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