← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-04-08 07:32:48 UTC
  • mfrom: (5138.1.1 integration)
  • Revision ID: pqm@pqm.ubuntu.com-20100408073248-aj7k8qkvbv4nzlxd
(igc for parthm) update -r dotted-revno support

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
462
462
        trailers = 0
463
463
        pos = stream.tell()
464
464
        lines = stream.read().split('\n')
465
 
        # GZ 2009-09-20: Should really use a try/finally block to ensure close
466
465
        stream.close()
467
466
        del lines[-1]
468
467
        _, _, _, trailers = self._parse_lines(lines, pos)
1246
1245
    static data.
1247
1246
 
1248
1247
    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
 
1248
    and then the second and so on. The order of index's can thus influence
1250
1249
    performance significantly. For example, if one index is on local disk and a
1251
1250
    second on a remote server, the local disk index should be before the other
1252
1251
    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
1252
    """
1259
1253
 
1260
1254
    def __init__(self, indices, reload_func=None):
1267
1261
        """
1268
1262
        self._indices = indices
1269
1263
        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
1264
 
1278
1265
    def __repr__(self):
1279
1266
        return "%s(%s)" % (
1302
1289
 
1303
1290
    has_key = _has_key_from_parent_map
1304
1291
 
1305
 
    def insert_index(self, pos, index, name=None):
 
1292
    def insert_index(self, pos, index):
1306
1293
        """Insert a new index in the list of indices to query.
1307
1294
 
1308
1295
        :param pos: The position to insert the index.
1309
1296
        :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
1297
        """
1314
1298
        self._indices.insert(pos, index)
1315
 
        self._index_names.insert(pos, name)
1316
1299
 
1317
1300
    def iter_all_entries(self):
1318
1301
        """Iterate over all keys within the index
1343
1326
        value and are only reported once.
1344
1327
 
1345
1328
        :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
 
1329
        :return: An iterable of (index, key, reference_lists, value). There is no
 
1330
            defined order for the result iteration - it will be in the most
1348
1331
            efficient order for the index.
1349
1332
        """
1350
1333
        keys = set(keys)
1351
 
        hit_indices = []
1352
1334
        while True:
1353
1335
            try:
1354
1336
                for index in self._indices:
1355
1337
                    if not keys:
1356
 
                        break
1357
 
                    index_hit = False
 
1338
                        return
1358
1339
                    for node in index.iter_entries(keys):
1359
1340
                        keys.remove(node[1])
1360
1341
                        yield node
1361
 
                        index_hit = True
1362
 
                    if index_hit:
1363
 
                        hit_indices.append(index)
1364
 
                break
 
1342
                return
1365
1343
            except errors.NoSuchFile:
1366
1344
                self._reload_or_raise()
1367
 
        self._move_to_front(hit_indices)
1368
1345
 
1369
1346
    def iter_entries_prefix(self, keys):
1370
1347
        """Iterate over keys within the index using prefix matching.
1390
1367
        if not keys:
1391
1368
            return
1392
1369
        seen_keys = set()
1393
 
        hit_indices = []
1394
1370
        while True:
1395
1371
            try:
1396
1372
                for index in self._indices:
1397
 
                    index_hit = False
1398
1373
                    for node in index.iter_entries_prefix(keys):
1399
1374
                        if node[1] in seen_keys:
1400
1375
                            continue
1401
1376
                        seen_keys.add(node[1])
1402
1377
                        yield node
1403
 
                        index_hit = True
1404
 
                    if index_hit:
1405
 
                        hit_indices.append(index)
1406
 
                break
 
1378
                return
1407
1379
            except errors.NoSuchFile:
1408
1380
                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
1381
 
1477
1382
    def find_ancestry(self, keys, ref_list_num):
1478
1383
        """Find the complete ancestry for the given set of keys.
1485
1390
            we care about.
1486
1391
        :return: (parent_map, missing_keys)
1487
1392
        """
1488
 
        # XXX: make this call _move_to_front?
1489
1393
        missing_keys = set()
1490
1394
        parent_map = {}
1491
1395
        keys_to_lookup = set(keys)
1571
1475
                         ' Raising original exception.')
1572
1476
            raise exc_type, exc_value, exc_traceback
1573
1477
 
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
1478
    def validate(self):
1580
1479
        """Validate that everything in the index can be accessed."""
1581
1480
        while True: