~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

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

• reverse the comparison (4842.1.1 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

205

205

                if reference not in self._nodes:

206

206

                    self._check_key(reference)

207

207

                    absent_references.append(reference)

208

 

            reference_list = as_st([as_st(ref).intern()

209

 

                                    for ref in reference_list])

210

 

            node_refs.append(reference_list)

 

208

            node_refs.append(as_st(reference_list))

211

209

        return as_st(node_refs), absent_references

212

210

 

213

211

    def add_node(self, key, value, references=()):

382

380

    suitable for production use. :XXX

383

381

    """

384

382

 

385

 

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

 

383

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

386

384

        """Open an index called name on transport.

387

385

 

388

386

        :param transport: A bzrlib.transport.Transport.

394

392

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

395

393

            support will be disabled and accessing the index will just stream

396

394

            all the data.

397

 

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

398

 

            at an arbitrary offset.

399

395

        """

400

396

        self._transport = transport

401

397

        self._name = name

418

414

        self._size = size

419

415

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

420

416

        self._bytes_read = 0

421

 

        self._base_offset = offset

422

417

 

423

418

    def __eq__(self, other):

424

419

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

447

442

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

448

443

        if stream is None:

449

444

            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

445

        self._read_prefix(stream)

455

446

        self._expected_elements = 3 + self._key_length

456

447

        line_count = 0

462

453

        trailers = 0

463

454

        pos = stream.tell()

464

455

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

465

 

        stream.close()

466

456

        del lines[-1]

467

457

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

468

458

        for key, absent, references, value in self._keys_by_offset.itervalues():

1197

1187

            self._buffer_all()

1198

1188

            return

1199

1189

 

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

1190

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

1206

 

            self._size + self._base_offset)

 

1191

            self._size)

1207

1192

        # parse

1208

1193

        for offset, data in readv_data:

1209

 

            offset -= base_offset

1210

1194

            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

1195

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

1217

1196

                # We read the whole range, most likely because the

1218

1197

                # Transport upcast our readv ranges into one long request

1245

1224

    static data.

1246

1225

 

1247

1226

    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

 

1227

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

1249

1228

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

1250

1229

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

1251

1230

    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

1231

    """

1258

1232

 

1259

1233

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

1266

1240

        """

1267

1241

        self._indices = indices

1268

1242

        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

1243

 

1277

1244

    def __repr__(self):

1278

1245

        return "%s(%s)" % (

1301

1268

 

1302

1269

    has_key = _has_key_from_parent_map

1303

1270

 

1304

 

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

 

1271

    def insert_index(self, pos, index):

1305

1272

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

1306

1273

 

1307

1274

        :param pos: The position to insert the index.

1308

1275

        :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

1276

        """

1313

1277

        self._indices.insert(pos, index)

1314

 

        self._index_names.insert(pos, name)

1315

1278

 

1316

1279

    def iter_all_entries(self):

1317

1280

        """Iterate over all keys within the index

1342

1305

        value and are only reported once.

1343

1306

 

1344

1307

        :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

 

1308

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

 

1309

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

1347

1310

            efficient order for the index.

1348

1311

        """

1349

1312

        keys = set(keys)

1350

 

        hit_indices = []

1351

1313

        while True:

1352

1314

            try:

1353

1315

                for index in self._indices:

1354

1316

                    if not keys:

1355

 

                        break

1356

 

                    index_hit = False

 

1317

                        return

1357

1318

                    for node in index.iter_entries(keys):

1358

1319

                        keys.remove(node[1])

1359

1320

                        yield node

1360

 

                        index_hit = True

1361

 

                    if index_hit:

1362

 

                        hit_indices.append(index)

1363

 

                break

 

1321

                return

1364

1322

            except errors.NoSuchFile:

1365

1323

                self._reload_or_raise()

1366

 

        self._move_to_front(hit_indices)

1367

1324

 

1368

1325

    def iter_entries_prefix(self, keys):

1369

1326

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

1389

1346

        if not keys:

1390

1347

            return

1391

1348

        seen_keys = set()

1392

 

        hit_indices = []

1393

1349

        while True:

1394

1350

            try:

1395

1351

                for index in self._indices:

1396

 

                    index_hit = False

1397

1352

                    for node in index.iter_entries_prefix(keys):

1398

1353

                        if node[1] in seen_keys:

1399

1354

                            continue

1400

1355

                        seen_keys.add(node[1])

1401

1356

                        yield node

1402

 

                        index_hit = True

1403

 

                    if index_hit:

1404

 

                        hit_indices.append(index)

1405

 

                break

 

1357

                return

1406

1358

            except errors.NoSuchFile:

1407

1359

                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

1360

 

1476

1361

    def find_ancestry(self, keys, ref_list_num):

1477

1362

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

1484

1369

            we care about.

1485

1370

        :return: (parent_map, missing_keys)

1486

1371

        """

1487

 

        # XXX: make this call _move_to_front?

1488

1372

        missing_keys = set()

1489

1373

        parent_map = {}

1490

1374

        keys_to_lookup = set(keys)

1570

1454

                         ' Raising original exception.')

1571

1455

            raise exc_type, exc_value, exc_traceback

1572

1456

 

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

1457

    def validate(self):

1579

1458

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

1580

1459

        while True:

• Older »

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