← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Joe Julian
  • Date: 2010-01-10 02:25:31 UTC
  • mto: (4634.119.7 2.0)
  • mto: This revision was merged to the branch mainline in revision 4959.
  • Revision ID: joe@julianfamily.org-20100110022531-wqk61rsagz8xsiga
https://launchpad.net/bugs/175839
Added MANIFEST.in to allow bdist_rpm to have all the required include files and tools. bdist_rpm will still fail to build correctly on some distributions due to a disttools bug http://bugs.python.org/issue644744

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
1
 
# Copyright (C) 2007, 2008 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
39
39
from bzrlib import (
40
40
    debug,
41
41
    errors,
42
 
    symbol_versioning,
43
42
    )
44
43
 
45
44
_HEADER_READV = (0, 200)
334
333
        if combine_backing_indices is not None:
335
334
            self._combine_backing_indices = combine_backing_indices
336
335
 
 
336
    def find_ancestry(self, keys, ref_list_num):
 
337
        """See CombinedGraphIndex.find_ancestry()"""
 
338
        pending = set(keys)
 
339
        parent_map = {}
 
340
        missing_keys = set()
 
341
        while pending:
 
342
            next_pending = set()
 
343
            for _, key, value, ref_lists in self.iter_entries(pending):
 
344
                parent_keys = ref_lists[ref_list_num]
 
345
                parent_map[key] = parent_keys
 
346
                next_pending.update([p for p in parent_keys if p not in
 
347
                                     parent_map])
 
348
                missing_keys.update(pending.difference(parent_map))
 
349
            pending = next_pending
 
350
        return parent_map, missing_keys
 
351
 
337
352
 
338
353
class GraphIndex(object):
339
354
    """An index for data with embedded graphs.
353
368
    suitable for production use. :XXX
354
369
    """
355
370
 
356
 
    def __init__(self, transport, name, size):
 
371
    def __init__(self, transport, name, size, unlimited_cache=False):
357
372
        """Open an index called name on transport.
358
373
 
359
374
        :param transport: A bzrlib.transport.Transport.
703
718
                # the last thing looked up was a terminal element
704
719
                yield (self, ) + key_dict
705
720
 
 
721
    def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
 
722
        """See BTreeIndex._find_ancestors."""
 
723
        # The api can be implemented as a trivial overlay on top of
 
724
        # iter_entries, it is not an efficient implementation, but it at least
 
725
        # gets the job done.
 
726
        found_keys = set()
 
727
        search_keys = set()
 
728
        for index, key, value, refs in self.iter_entries(keys):
 
729
            parent_keys = refs[ref_list_num]
 
730
            found_keys.add(key)
 
731
            parent_map[key] = parent_keys
 
732
            search_keys.update(parent_keys)
 
733
        # Figure out what, if anything, was missing
 
734
        missing_keys.update(set(keys).difference(found_keys))
 
735
        search_keys = search_keys.difference(parent_map)
 
736
        return search_keys
 
737
 
706
738
    def key_count(self):
707
739
        """Return an estimate of the number of keys in this index.
708
740
 
1192
1224
                ', '.join(map(repr, self._indices)))
1193
1225
 
1194
1226
    def get_parent_map(self, keys):
1195
 
        """See graph._StackedParentsProvider.get_parent_map"""
 
1227
        """See graph.StackedParentsProvider.get_parent_map"""
1196
1228
        search_keys = set(keys)
1197
1229
        if NULL_REVISION in search_keys:
1198
1230
            search_keys.discard(NULL_REVISION)
1298
1330
            except errors.NoSuchFile:
1299
1331
                self._reload_or_raise()
1300
1332
 
 
1333
    def find_ancestry(self, keys, ref_list_num):
 
1334
        """Find the complete ancestry for the given set of keys.
 
1335
 
 
1336
        Note that this is a whole-ancestry request, so it should be used
 
1337
        sparingly.
 
1338
 
 
1339
        :param keys: An iterable of keys to look for
 
1340
        :param ref_list_num: The reference list which references the parents
 
1341
            we care about.
 
1342
        :return: (parent_map, missing_keys)
 
1343
        """
 
1344
        missing_keys = set()
 
1345
        parent_map = {}
 
1346
        keys_to_lookup = set(keys)
 
1347
        generation = 0
 
1348
        while keys_to_lookup:
 
1349
            # keys that *all* indexes claim are missing, stop searching them
 
1350
            generation += 1
 
1351
            all_index_missing = None
 
1352
            # print 'gen\tidx\tsub\tn_keys\tn_pmap\tn_miss'
 
1353
            # print '%4d\t\t\t%4d\t%5d\t%5d' % (generation, len(keys_to_lookup),
 
1354
            #                                   len(parent_map),
 
1355
            #                                   len(missing_keys))
 
1356
            for index_idx, index in enumerate(self._indices):
 
1357
                # TODO: we should probably be doing something with
 
1358
                #       'missing_keys' since we've already determined that
 
1359
                #       those revisions have not been found anywhere
 
1360
                index_missing_keys = set()
 
1361
                # Find all of the ancestry we can from this index
 
1362
                # keep looking until the search_keys set is empty, which means
 
1363
                # things we didn't find should be in index_missing_keys
 
1364
                search_keys = keys_to_lookup
 
1365
                sub_generation = 0
 
1366
                # print '    \t%2d\t\t%4d\t%5d\t%5d' % (
 
1367
                #     index_idx, len(search_keys),
 
1368
                #     len(parent_map), len(index_missing_keys))
 
1369
                while search_keys:
 
1370
                    sub_generation += 1
 
1371
                    # TODO: ref_list_num should really be a parameter, since
 
1372
                    #       CombinedGraphIndex does not know what the ref lists
 
1373
                    #       mean.
 
1374
                    search_keys = index._find_ancestors(search_keys,
 
1375
                        ref_list_num, parent_map, index_missing_keys)
 
1376
                    # print '    \t  \t%2d\t%4d\t%5d\t%5d' % (
 
1377
                    #     sub_generation, len(search_keys),
 
1378
                    #     len(parent_map), len(index_missing_keys))
 
1379
                # Now set whatever was missing to be searched in the next index
 
1380
                keys_to_lookup = index_missing_keys
 
1381
                if all_index_missing is None:
 
1382
                    all_index_missing = set(index_missing_keys)
 
1383
                else:
 
1384
                    all_index_missing.intersection_update(index_missing_keys)
 
1385
                if not keys_to_lookup:
 
1386
                    break
 
1387
            if all_index_missing is None:
 
1388
                # There were no indexes, so all search keys are 'missing'
 
1389
                missing_keys.update(keys_to_lookup)
 
1390
                keys_to_lookup = None
 
1391
            else:
 
1392
                missing_keys.update(all_index_missing)
 
1393
                keys_to_lookup.difference_update(all_index_missing)
 
1394
        return parent_map, missing_keys
 
1395
 
1301
1396
    def key_count(self):
1302
1397
        """Return an estimate of the number of keys in this index.
1303
1398