~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

• browse files at revision 3641.3.28
• compare with another revision
• compare with revision 6620
• download diff
• download tarball
• view history from revision 3641.3.28

Show diffs side-by-side

added

removed

bzrlib/btree_index.py

1105

1105

            pass

1106

1106

 

1107

1107

 

1108

 

class FixedMemoryGraphIndex(index.GraphIndex):

1109

 

    """A variant of GraphIndex which spools to disk during parsing.

1110

 

 

1111

 

    This is useful for avoiding particularly high memory use which can occur

1112

 

    with very large GraphIndices. As it imposes a performance overhead due

1113

 

    to generating disk-based b+tree's, it is not suitable for general use.

1114

 

 

1115

 

    Also, only iter_all_entries is implemented.

1116

 

    """

1117

 

 

1118

 

    def __init__(self, transport, name, size):

1119

 

        index.GraphIndex.__init__(self, transport, name, size)

1120

 

        self._locs = None

1121

 

        self._key_details = None

1122

 

 

1123

 

    def _resolve_locs(self, references):

1124

 

        """Return the resolved key references for references.

1125

 

 

1126

 

        References are resolved by looking up the location of the key in the

1127

 

        _keys_by_offset map and substituting the key name, preserving ordering.

1128

 

 

1129

 

        :param references: An iterable of iterables of key locations. e.g.

1130

 

            [[123, 456], [123]]

1131

 

        :return: A tuple of tuples of keys.

1132

 

        """

1133

 

        key_offsets = {}

1134

 

        needed_refs = set()

1135

 

        node_refs = []

1136

 

        for ref_list in references:

1137

 

            for ref in ref_list:

1138

 

                needed_refs.add(ref[:1])

1139

 

        for node in self._locs.iter_entries(needed_refs):

1140

 

            key_offsets[node[1][0]] = tuple(node[2].split(' '))

1141

 

        for ref_list in references:

1142

 

            node_refs.append(tuple([key_offsets[ref[0]] for ref in ref_list]))

1143

 

        return tuple(node_refs)

1144

 

 

1145

 

    def iter_all_entries(self):

1146

 

        if self._locs is None:

1147

 

            self._scan_index()

1148

 

        if self.node_ref_lists:

1149

 

            for node in self._key_details.iter_all_entries():

1150

 

                refs = self._resolve_locs(node[3])

1151

 

                yield (self,) + node[1:3] + (refs,)

1152

 

        else:

1153

 

            for node in self._key_details.iter_all_entries():

1154

 

                yield (self,) + node[1:3]

1155

 

 

1156

 

    def _scan_index(self):

1157

 

        stream = self._transport.get(self._name)

1158

 

        self._read_prefix(stream)

1159

 

        self._expected_elements = 3 + self._key_length

1160

 

        line_count = 0

1161

 

        self._locs = BTreeBuilder(key_elements=1, reference_lists=0)

1162

 

        self._key_details = BTreeBuilder(key_elements=self._key_length,

1163

 

            reference_lists=self.node_ref_lists)

1164

 

        # raw data keyed by offset

1165

 

        self._keys_by_offset = {}

1166

 

        # ready-to-return key:value or key:value, node_ref_lists

1167

 

        self._nodes = {}

1168

 

        self._nodes_by_key = {}

1169

 

        trailers = 0

1170

 

        pos = stream.tell()

1171

 

        lines = stream.read().split('\n')

1172

 

        del lines[-1]

1173

 

        key = None

1174

 

        first_key = None

1175

 

        trailers = 0

1176

 

        for line in lines:

1177

 

            if line == '':

1178

 

                # must be at the end

1179

 

                if self._size:

1180

 

                    if not (self._size == pos + 1):

1181

 

                        raise AssertionError("%s %s" % (self._size, pos))

1182

 

                trailers += 1

1183

 

                continue

1184

 

            elements = line.split('\0')

1185

 

            if len(elements) != self._expected_elements:

1186

 

                raise errors.BadIndexData(self)

1187

 

            # keys are tuples

1188

 

            key = tuple(elements[:self._key_length])

1189

 

            if first_key is None:

1190

 

                first_key = key

1191

 

            absent, references, value = elements[-3:]

1192

 

            ref_lists = []

1193

 

            for ref_string in references.split('\t'):

1194

 

                ref_lists.append(tuple([

1195

 

                    (str(int(ref)),) + ('X',) * (self._key_length - 1) for

1196

 

                    ref in ref_string.split('\r') if ref]))

1197

 

            ref_lists = tuple(ref_lists)

1198

 

            self._locs.add_node((str(pos),), ' '.join(key))

1199

 

            pos += len(line) + 1 # +1 for the \n

1200

 

            if absent:

1201

 

                continue

1202

 

            self._key_details.add_node(key, value, ref_lists)

1203

 

 

1204

 

 

1205

1108

try:

1206

1109

    from bzrlib import _parse_btree_c as _parse_btree

1207

1110

except ImportError:

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.1