~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Matt Nordhoff
  • Date: 2009-06-23 05:12:07 UTC
  • mto: This revision was merged to the branch mainline in revision 4474.
  • Revision ID: mnordhoff@mattnordhoff.com-20090623051207-fksdtbzkwtnrw9dd
Update _add_text docstrings that still referred to add_text.

Show diffs side-by-side

added added

removed removed

Lines of Context:
39
39
from bzrlib import (
40
40
    debug,
41
41
    errors,
 
42
    symbol_versioning,
42
43
    )
43
44
 
44
45
_HEADER_READV = (0, 200)
333
334
        if combine_backing_indices is not None:
334
335
            self._combine_backing_indices = combine_backing_indices
335
336
 
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
 
 
352
337
 
353
338
class GraphIndex(object):
354
339
    """An index for data with embedded graphs.
718
703
                # the last thing looked up was a terminal element
719
704
                yield (self, ) + key_dict
720
705
 
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
 
 
738
706
    def key_count(self):
739
707
        """Return an estimate of the number of keys in this index.
740
708
 
1224
1192
                ', '.join(map(repr, self._indices)))
1225
1193
 
1226
1194
    def get_parent_map(self, keys):
1227
 
        """See graph.StackedParentsProvider.get_parent_map"""
 
1195
        """See graph._StackedParentsProvider.get_parent_map"""
1228
1196
        search_keys = set(keys)
1229
1197
        if NULL_REVISION in search_keys:
1230
1198
            search_keys.discard(NULL_REVISION)
1330
1298
            except errors.NoSuchFile:
1331
1299
                self._reload_or_raise()
1332
1300
 
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
 
 
1396
1301
    def key_count(self):
1397
1302
        """Return an estimate of the number of keys in this index.
1398
1303