← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Robert Collins
  • Date: 2007-07-13 08:10:09 UTC
  • mto: (2592.5.3 pack-repository)
  • mto: This revision was merged to the branch mainline in revision 2624.
  • Revision ID: robertc@robertcollins.net-20070713081009-uouct3cvz4dz1rtl
Node references are byte offsets.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
83
83
    def finish(self):
84
84
        lines = [_SIGNATURE]
85
85
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
 
86
        prefix_length = len(lines[0]) + len(lines[1])
 
87
        # references are byte offsets. To avoid having to do nasty
 
88
        # polynomial work to resolve offsets (references to later in the 
 
89
        # file cannot be determined until all the inbetween references have
 
90
        # been calculated too) we pad the offsets with 0's to make them be
 
91
        # of consistent length. Using binary offsets would break the trivial
 
92
        # file parsing.
 
93
        # to calculate the width of zero's needed we do three passes:
 
94
        # one to gather all the non-reference data and the number of references.
 
95
        # one to pad all the data with reference-length and determine entry
 
96
        # addresses.
 
97
        # One to serialise.
 
98
        non_ref_bytes = prefix_length
 
99
        total_references = 0
 
100
        # XXX: support 'a' field here.
 
101
        for key, (references, value) in sorted(self._nodes.items(),reverse=True):
 
102
            # key is literal, value is literal, there are 3 null's, 1 NL
 
103
            # (ref_lists -1) tabs, (ref-1 cr's per ref_list)
 
104
            non_ref_bytes += len(key) + 3 + 1 + self.reference_lists - 1
 
105
            for ref_list in references:
 
106
                # how many references across the whole file?
 
107
                total_references += len(ref_list)
 
108
                # accrue reference separators
 
109
                non_ref_bytes += len(ref_list) - 1
 
110
        # how many digits are needed to represent the total byte count?
 
111
        digits = 1
 
112
        possible_total_bytes = non_ref_bytes + total_references*digits
 
113
        while 10 ** digits < possible_total_bytes:
 
114
            digits += 1
 
115
            possible_total_bytes = non_ref_bytes + total_references*digits
 
116
        # resolve key addresses.
 
117
        key_addresses = {}
 
118
        current_offset = prefix_length
 
119
        for key, (references, value) in sorted(self._nodes.items(),reverse=True):
 
120
            key_addresses[key] = current_offset
 
121
            current_offset += len(key) + 3 + 1 + self.reference_lists - 1
 
122
            for ref_list in references:
 
123
                # accrue reference separators
 
124
                current_offset += len(ref_list) - 1
 
125
                # accrue reference bytes
 
126
                current_offset += digits * len(ref_list)
 
127
        # serialise
 
128
        format_string = '%%0%sd' % digits
86
129
        for key, (references, value) in sorted(self._nodes.items(),reverse=True):
87
130
            flattened_references = []
88
131
            for ref_list in references:
89
 
                flattened_references.append('')
 
132
                ref_addresses = []
 
133
                for reference in ref_list:
 
134
                    ref_addresses.append(format_string % key_addresses[reference])
 
135
                flattened_references.append('\r'.join(ref_addresses))
90
136
            lines.append("%s\0\0%s\0%s\n" % (key,
91
137
                '\t'.join(flattened_references), value))
92
138
        lines.append('\n')