← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

remove all trailing whitespace from bzr source

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
56
56
def _has_key_from_parent_map(self, key):
57
57
    """Check if this index has one key.
58
58
 
59
 
    If it's possible to check for multiple keys at once through 
 
59
    If it's possible to check for multiple keys at once through
60
60
    calling get_parent_map that should be faster.
61
61
    """
62
62
    return (key in self.get_parent_map([key]))
68
68
 
69
69
class GraphIndexBuilder(object):
70
70
    """A builder that can build a GraphIndex.
71
 
    
 
71
 
72
72
    The resulting graph has the structure:
73
 
    
 
73
 
74
74
    _SIGNATURE OPTIONS NODES NEWLINE
75
75
    _SIGNATURE     := 'Bazaar Graph Index 1' NEWLINE
76
76
    OPTIONS        := 'node_ref_lists=' DIGITS NEWLINE
246
246
        # one to pad all the data with reference-length and determine entry
247
247
        # addresses.
248
248
        # One to serialise.
249
 
        
 
249
 
250
250
        # forward sorted by key. In future we may consider topological sorting,
251
251
        # at the cost of table scans for direct lookup, or a second index for
252
252
        # direct lookup
329
329
 
330
330
class GraphIndex(object):
331
331
    """An index for data with embedded graphs.
332
 
 
 
332
 
333
333
    The index maps keys to a list of key reference lists, and a value.
334
334
    Each node has the same number of key reference lists. Each key reference
335
335
    list can be empty or an arbitrary length. The value is an opaque NULL
336
 
    terminated string without any newlines. The storage of the index is 
 
336
    terminated string without any newlines. The storage of the index is
337
337
    hidden in the interface: keys and key references are always tuples of
338
338
    bytestrings, never the internal representation (e.g. dictionary offsets).
339
339
 
502
502
 
503
503
    def _resolve_references(self, references):
504
504
        """Return the resolved key references for references.
505
 
        
 
505
 
506
506
        References are resolved by looking up the location of the key in the
507
507
        _keys_by_offset map and substituting the key name, preserving ordering.
508
508
 
509
 
        :param references: An iterable of iterables of key locations. e.g. 
 
509
        :param references: An iterable of iterables of key locations. e.g.
510
510
            [[123, 456], [123]]
511
511
        :return: A tuple of tuples of keys.
512
512
        """
670
670
                    # can't be empty or would not exist
671
671
                    item, value = key_dict.iteritems().next()
672
672
                    if type(value) == dict:
673
 
                        # push keys 
 
673
                        # push keys
674
674
                        dicts.extend(key_dict.itervalues())
675
675
                    else:
676
676
                        # yield keys
684
684
 
685
685
    def key_count(self):
686
686
        """Return an estimate of the number of keys in this index.
687
 
        
 
687
 
688
688
        For GraphIndex the estimate is exact.
689
689
        """
690
690
        if self._key_count is None:
706
706
        # Possible improvements:
707
707
        #  - only bisect lookup each key once
708
708
        #  - sort the keys first, and use that to reduce the bisection window
709
 
        # ----- 
 
709
        # -----
710
710
        # this progresses in three parts:
711
711
        # read data
712
712
        # parse it
721
721
                # We have the key parsed.
722
722
                continue
723
723
            index = self._parsed_key_index(key)
724
 
            if (len(self._parsed_key_map) and 
 
724
            if (len(self._parsed_key_map) and
725
725
                self._parsed_key_map[index][0] <= key and
726
726
                (self._parsed_key_map[index][1] >= key or
727
727
                 # end of the file has been parsed
731
731
                continue
732
732
            # - if we have examined this part of the file already - yes
733
733
            index = self._parsed_byte_index(location)
734
 
            if (len(self._parsed_byte_map) and 
 
734
            if (len(self._parsed_byte_map) and
735
735
                self._parsed_byte_map[index][0] <= location and
736
736
                self._parsed_byte_map[index][1] > location):
737
737
                # the byte region has been parsed, so no read is needed.
992
992
        # adjust offset and data to the parseable data.
993
993
        trimmed_data = data[trim_start:trim_end]
994
994
        if not (trimmed_data):
995
 
            raise AssertionError('read unneeded data [%d:%d] from [%d:%d]' 
 
995
            raise AssertionError('read unneeded data [%d:%d] from [%d:%d]'
996
996
                % (trim_start, trim_end, offset, offset + len(data)))
997
997
        if trim_start:
998
998
            offset += trim_start
1143
1143
 
1144
1144
class CombinedGraphIndex(object):
1145
1145
    """A GraphIndex made up from smaller GraphIndices.
1146
 
    
 
1146
 
1147
1147
    The backing indices must implement GraphIndex, and are presumed to be
1148
1148
    static data.
1149
1149
 
1173
1173
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
1174
1174
    def get_parents(self, revision_ids):
1175
1175
        """See graph._StackedParentsProvider.get_parents.
1176
 
        
 
1176
 
1177
1177
        This implementation thunks the graph.Graph.get_parents api across to
1178
1178
        GraphIndex.
1179
1179
 
1428
1428
                    raise errors.BadIndexKey(key)
1429
1429
                node = self._nodes[key]
1430
1430
                if node[0]:
1431
 
                    continue 
 
1431
                    continue
1432
1432
                if self.reference_lists:
1433
1433
                    yield self, key, node[2], node[1]
1434
1434
                else:
1459
1459
                    # can't be empty or would not exist
1460
1460
                    item, value = key_dict.iteritems().next()
1461
1461
                    if type(value) == dict:
1462
 
                        # push keys 
 
1462
                        # push keys
1463
1463
                        dicts.extend(key_dict.itervalues())
1464
1464
                    else:
1465
1465
                        # yield keys
1470
1470
 
1471
1471
    def key_count(self):
1472
1472
        """Return an estimate of the number of keys in this index.
1473
 
        
 
1473
 
1474
1474
        For InMemoryGraphIndex the estimate is exact.
1475
1475
        """
1476
1476
        return len(self._keys)
1484
1484
 
1485
1485
    Queries against this will emit queries against the adapted Graph with the
1486
1486
    prefix added, queries for all items use iter_entries_prefix. The returned
1487
 
    nodes will have their keys and node references adjusted to remove the 
 
1487
    nodes will have their keys and node references adjusted to remove the
1488
1488
    prefix. Finally, an add_nodes_callback can be supplied - when called the
1489
1489
    nodes and references being added will have prefix prepended.
1490
1490
    """
1517
1517
                    adjusted_references))
1518
1518
        except ValueError:
1519
1519
            # XXX: TODO add an explicit interface for getting the reference list
1520
 
            # status, to handle this bit of user-friendliness in the API more 
 
1520
            # status, to handle this bit of user-friendliness in the API more
1521
1521
            # explicitly.
1522
1522
            for (key, value) in nodes:
1523
1523
                translated_nodes.append((self.prefix + key, value))
1595
1595
 
1596
1596
    def key_count(self):
1597
1597
        """Return an estimate of the number of keys in this index.
1598
 
        
 
1598
 
1599
1599
        For GraphIndexPrefixAdapter this is relatively expensive - key
1600
1600
        iteration with the prefix is done.
1601
1601
        """