← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: John Arbash Meinel
  • Date: 2009-02-23 15:29:35 UTC
  • mfrom: (3943.7.7 bzr.code_style_cleanup)
  • mto: This revision was merged to the branch mainline in revision 4033.
  • Revision ID: john@arbash-meinel.com-20090223152935-oel9m92mwcc6nb4h
Merge the removal of all trailing whitespace, and resolve conflicts.

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
 
515
515
 
516
516
    def _resolve_references(self, references):
517
517
        """Return the resolved key references for references.
518
 
        
 
518
 
519
519
        References are resolved by looking up the location of the key in the
520
520
        _keys_by_offset map and substituting the key name, preserving ordering.
521
521
 
522
 
        :param references: An iterable of iterables of key locations. e.g. 
 
522
        :param references: An iterable of iterables of key locations. e.g.
523
523
            [[123, 456], [123]]
524
524
        :return: A tuple of tuples of keys.
525
525
        """
683
683
                    # can't be empty or would not exist
684
684
                    item, value = key_dict.iteritems().next()
685
685
                    if type(value) == dict:
686
 
                        # push keys 
 
686
                        # push keys
687
687
                        dicts.extend(key_dict.itervalues())
688
688
                    else:
689
689
                        # yield keys
697
697
 
698
698
    def key_count(self):
699
699
        """Return an estimate of the number of keys in this index.
700
 
        
 
700
 
701
701
        For GraphIndex the estimate is exact.
702
702
        """
703
703
        if self._key_count is None:
719
719
        # Possible improvements:
720
720
        #  - only bisect lookup each key once
721
721
        #  - sort the keys first, and use that to reduce the bisection window
722
 
        # ----- 
 
722
        # -----
723
723
        # this progresses in three parts:
724
724
        # read data
725
725
        # parse it
734
734
                # We have the key parsed.
735
735
                continue
736
736
            index = self._parsed_key_index(key)
737
 
            if (len(self._parsed_key_map) and 
 
737
            if (len(self._parsed_key_map) and
738
738
                self._parsed_key_map[index][0] <= key and
739
739
                (self._parsed_key_map[index][1] >= key or
740
740
                 # end of the file has been parsed
744
744
                continue
745
745
            # - if we have examined this part of the file already - yes
746
746
            index = self._parsed_byte_index(location)
747
 
            if (len(self._parsed_byte_map) and 
 
747
            if (len(self._parsed_byte_map) and
748
748
                self._parsed_byte_map[index][0] <= location and
749
749
                self._parsed_byte_map[index][1] > location):
750
750
                # the byte region has been parsed, so no read is needed.
1005
1005
        # adjust offset and data to the parseable data.
1006
1006
        trimmed_data = data[trim_start:trim_end]
1007
1007
        if not (trimmed_data):
1008
 
            raise AssertionError('read unneeded data [%d:%d] from [%d:%d]' 
 
1008
            raise AssertionError('read unneeded data [%d:%d] from [%d:%d]'
1009
1009
                % (trim_start, trim_end, offset, offset + len(data)))
1010
1010
        if trim_start:
1011
1011
            offset += trim_start
1156
1156
 
1157
1157
class CombinedGraphIndex(object):
1158
1158
    """A GraphIndex made up from smaller GraphIndices.
1159
 
    
 
1159
 
1160
1160
    The backing indices must implement GraphIndex, and are presumed to be
1161
1161
    static data.
1162
1162
 
1186
1186
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
1187
1187
    def get_parents(self, revision_ids):
1188
1188
        """See graph._StackedParentsProvider.get_parents.
1189
 
        
 
1189
 
1190
1190
        This implementation thunks the graph.Graph.get_parents api across to
1191
1191
        GraphIndex.
1192
1192
 
1441
1441
                    raise errors.BadIndexKey(key)
1442
1442
                node = self._nodes[key]
1443
1443
                if node[0]:
1444
 
                    continue 
 
1444
                    continue
1445
1445
                if self.reference_lists:
1446
1446
                    yield self, key, node[2], node[1]
1447
1447
                else:
1472
1472
                    # can't be empty or would not exist
1473
1473
                    item, value = key_dict.iteritems().next()
1474
1474
                    if type(value) == dict:
1475
 
                        # push keys 
 
1475
                        # push keys
1476
1476
                        dicts.extend(key_dict.itervalues())
1477
1477
                    else:
1478
1478
                        # yield keys
1483
1483
 
1484
1484
    def key_count(self):
1485
1485
        """Return an estimate of the number of keys in this index.
1486
 
        
 
1486
 
1487
1487
        For InMemoryGraphIndex the estimate is exact.
1488
1488
        """
1489
1489
        return len(self._keys)
1497
1497
 
1498
1498
    Queries against this will emit queries against the adapted Graph with the
1499
1499
    prefix added, queries for all items use iter_entries_prefix. The returned
1500
 
    nodes will have their keys and node references adjusted to remove the 
 
1500
    nodes will have their keys and node references adjusted to remove the
1501
1501
    prefix. Finally, an add_nodes_callback can be supplied - when called the
1502
1502
    nodes and references being added will have prefix prepended.
1503
1503
    """
1530
1530
                    adjusted_references))
1531
1531
        except ValueError:
1532
1532
            # XXX: TODO add an explicit interface for getting the reference list
1533
 
            # status, to handle this bit of user-friendliness in the API more 
 
1533
            # status, to handle this bit of user-friendliness in the API more
1534
1534
            # explicitly.
1535
1535
            for (key, value) in nodes:
1536
1536
                translated_nodes.append((self.prefix + key, value))
1608
1608
 
1609
1609
    def key_count(self):
1610
1610
        """Return an estimate of the number of keys in this index.
1611
 
        
 
1611
 
1612
1612
        For GraphIndexPrefixAdapter this is relatively expensive - key
1613
1613
        iteration with the prefix is done.
1614
1614
        """