~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

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

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

Show diffs side-by-side

added

removed

bzrlib/index.py

1245

1245

    static data.

1246

1246

 

1247

1247

    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

 

1248

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

1249

1249

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

1250

1250

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

1251

1251

    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

1252

    """

1258

1253

 

1259

1254

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

1266

1261

        """

1267

1262

        self._indices = indices

1268

1263

        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

1264

 

1277

1265

    def __repr__(self):

1278

1266

        return "%s(%s)" % (

1301

1289

 

1302

1290

    has_key = _has_key_from_parent_map

1303

1291

 

1304

 

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

 

1292

    def insert_index(self, pos, index):

1305

1293

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

1306

1294

 

1307

1295

        :param pos: The position to insert the index.

1308

1296

        :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

1297

        """

1313

1298

        self._indices.insert(pos, index)

1314

 

        self._index_names.insert(pos, name)

1315

1299

 

1316

1300

    def iter_all_entries(self):

1317

1301

        """Iterate over all keys within the index

1342

1326

        value and are only reported once.

1343

1327

 

1344

1328

        :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

 

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

1347

1331

            efficient order for the index.

1348

1332

        """

1349

1333

        keys = set(keys)

1350

 

        hit_indices = []

1351

1334

        while True:

1352

1335

            try:

1353

1336

                for index in self._indices:

1354

1337

                    if not keys:

1355

 

                        break

1356

 

                    index_hit = False

 

1338

                        return

1357

1339

                    for node in index.iter_entries(keys):

1358

1340

                        keys.remove(node[1])

1359

1341

                        yield node

1360

 

                        index_hit = True

1361

 

                    if index_hit:

1362

 

                        hit_indices.append(index)

1363

 

                break

 

1342

                return

1364

1343

            except errors.NoSuchFile:

1365

1344

                self._reload_or_raise()

1366

 

        self._move_to_front(hit_indices)

1367

1345

 

1368

1346

    def iter_entries_prefix(self, keys):

1369

1347

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

1389

1367

        if not keys:

1390

1368

            return

1391

1369

        seen_keys = set()

1392

 

        hit_indices = []

1393

1370

        while True:

1394

1371

            try:

1395

1372

                for index in self._indices:

1396

 

                    index_hit = False

1397

1373

                    for node in index.iter_entries_prefix(keys):

1398

1374

                        if node[1] in seen_keys:

1399

1375

                            continue

1400

1376

                        seen_keys.add(node[1])

1401

1377

                        yield node

1402

 

                        index_hit = True

1403

 

                    if index_hit:

1404

 

                        hit_indices.append(index)

1405

 

                break

 

1378

                return

1406

1379

            except errors.NoSuchFile:

1407

1380

                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

1381

 

1476

1382

    def find_ancestry(self, keys, ref_list_num):

1477

1383

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

1484

1390

            we care about.

1485

1391

        :return: (parent_map, missing_keys)

1486

1392

        """

1487

 

        # XXX: make this call _move_to_front?

1488

1393

        missing_keys = set()

1489

1394

        parent_map = {}

1490

1395

        keys_to_lookup = set(keys)

1570

1475

                         ' Raising original exception.')

1571

1476

            raise exc_type, exc_value, exc_traceback

1572

1477

 

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

1478

    def validate(self):

1579

1479

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

1580

1480

        while True:

• Older »

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