← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2008-09-03 22:30:56 UTC
  • mfrom: (3644.2.13 index_builder_cleanup)
  • Revision ID: pqm@pqm.ubuntu.com-20080903223056-b108iytb38xkznci
(jam) Streamline BTreeBuilder.add_node et al to make btree creation
        faster.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
80
80
        """
81
81
        self.reference_lists = reference_lists
82
82
        self._keys = set()
 
83
        # A dict of {key: (absent, ref_lists, value)}
83
84
        self._nodes = {}
84
 
        self._nodes_by_key = {}
 
85
        self._nodes_by_key = None
85
86
        self._key_length = key_elements
86
87
 
87
88
    def _check_key(self, key):
94
95
            if not element or _whitespace_re.search(element) is not None:
95
96
                raise errors.BadIndexKey(element)
96
97
 
97
 
    def add_node(self, key, value, references=()):
98
 
        """Add a node to the index.
99
 
 
100
 
        :param key: The key. keys are non-empty tuples containing
101
 
            as many whitespace-free utf8 bytestrings as the key length
102
 
            defined for this index.
103
 
        :param references: An iterable of iterables of keys. Each is a
104
 
            reference to another key.
105
 
        :param value: The value to associate with the key. It may be any
106
 
            bytes as long as it does not contain \0 or \n.
 
98
    def _get_nodes_by_key(self):
 
99
        if self._nodes_by_key is None:
 
100
            nodes_by_key = {}
 
101
            if self.reference_lists:
 
102
                for key, (absent, references, value) in self._nodes.iteritems():
 
103
                    if absent:
 
104
                        continue
 
105
                    key_dict = nodes_by_key
 
106
                    for subkey in key[:-1]:
 
107
                        key_dict = key_dict.setdefault(subkey, {})
 
108
                    key_dict[key[-1]] = key, value, references
 
109
            else:
 
110
                for key, (absent, references, value) in self._nodes.iteritems():
 
111
                    if absent:
 
112
                        continue
 
113
                    key_dict = nodes_by_key
 
114
                    for subkey in key[:-1]:
 
115
                        key_dict = key_dict.setdefault(subkey, {})
 
116
                    key_dict[key[-1]] = key, value
 
117
            self._nodes_by_key = nodes_by_key
 
118
        return self._nodes_by_key
 
119
 
 
120
    def _update_nodes_by_key(self, key, value, node_refs):
 
121
        """Update the _nodes_by_key dict with a new key.
 
122
 
 
123
        For a key of (foo, bar, baz) create
 
124
        _nodes_by_key[foo][bar][baz] = key_value
 
125
        """
 
126
        if self._nodes_by_key is None:
 
127
            return
 
128
        key_dict = self._nodes_by_key
 
129
        if self.reference_lists:
 
130
            key_value = key, value, node_refs
 
131
        else:
 
132
            key_value = key, value
 
133
        for subkey in key[:-1]:
 
134
            key_dict = key_dict.setdefault(subkey, {})
 
135
        key_dict[key[-1]] = key_value
 
136
 
 
137
    def _check_key_ref_value(self, key, references, value):
 
138
        """Check that 'key' and 'references' are all valid.
 
139
 
 
140
        :param key: A key tuple. Must conform to the key interface (be a tuple,
 
141
            be of the right length, not have any whitespace or nulls in any key
 
142
            element.)
 
143
        :param references: An iterable of reference lists. Something like
 
144
            [[(ref, key)], [(ref, key), (other, key)]]
 
145
        :param value: The value associate with this key. Must not contain
 
146
            newlines or null characters.
 
147
        :return: (node_refs, absent_references)
 
148
            node_refs   basically a packed form of 'references' where all
 
149
                        iterables are tuples
 
150
            absent_references   reference keys that are not in self._nodes.
 
151
                                This may contain duplicates if the same key is
 
152
                                referenced in multiple lists.
107
153
        """
108
154
        self._check_key(key)
109
155
        if _newline_null_re.search(value) is not None:
111
157
        if len(references) != self.reference_lists:
112
158
            raise errors.BadIndexValue(references)
113
159
        node_refs = []
 
160
        absent_references = []
114
161
        for reference_list in references:
115
162
            for reference in reference_list:
116
 
                self._check_key(reference)
 
163
                # If reference *is* in self._nodes, then we know it has already
 
164
                # been checked.
117
165
                if reference not in self._nodes:
118
 
                    self._nodes[reference] = ('a', (), '')
 
166
                    self._check_key(reference)
 
167
                    absent_references.append(reference)
119
168
            node_refs.append(tuple(reference_list))
120
 
        if key in self._nodes and self._nodes[key][0] == '':
 
169
        return tuple(node_refs), absent_references
 
170
 
 
171
    def add_node(self, key, value, references=()):
 
172
        """Add a node to the index.
 
173
 
 
174
        :param key: The key. keys are non-empty tuples containing
 
175
            as many whitespace-free utf8 bytestrings as the key length
 
176
            defined for this index.
 
177
        :param references: An iterable of iterables of keys. Each is a
 
178
            reference to another key.
 
179
        :param value: The value to associate with the key. It may be any
 
180
            bytes as long as it does not contain \0 or \n.
 
181
        """
 
182
        (node_refs,
 
183
         absent_references) = self._check_key_ref_value(key, references, value)
 
184
        if key in self._nodes and self._nodes[key][0] != 'a':
121
185
            raise errors.BadIndexDuplicateKey(key, self)
122
 
        self._nodes[key] = ('', tuple(node_refs), value)
 
186
        for reference in absent_references:
 
187
            # There may be duplicates, but I don't think it is worth worrying
 
188
            # about
 
189
            self._nodes[reference] = ('a', (), '')
 
190
        self._nodes[key] = ('', node_refs, value)
123
191
        self._keys.add(key)
124
 
        if self._key_length > 1:
125
 
            key_dict = self._nodes_by_key
126
 
            if self.reference_lists:
127
 
                key_value = key, value, tuple(node_refs)
128
 
            else:
129
 
                key_value = key, value
130
 
            # possibly should do this on-demand, but it seems likely it is 
131
 
            # always wanted
132
 
            # For a key of (foo, bar, baz) create
133
 
            # _nodes_by_key[foo][bar][baz] = key_value
134
 
            for subkey in key[:-1]:
135
 
                key_dict = key_dict.setdefault(subkey, {})
136
 
            key_dict[key[-1]] = key_value
 
192
        if self._nodes_by_key is not None and self._key_length > 1:
 
193
            self._update_nodes_by_key(key, value, node_refs)
137
194
 
138
195
    def finish(self):
139
196
        lines = [_SIGNATURE]
142
199
        lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
143
200
        prefix_length = sum(len(x) for x in lines)
144
201
        # references are byte offsets. To avoid having to do nasty
145
 
        # polynomial work to resolve offsets (references to later in the 
 
202
        # polynomial work to resolve offsets (references to later in the
146
203
        # file cannot be determined until all the inbetween references have
147
204
        # been calculated too) we pad the offsets with 0's to make them be
148
205
        # of consistent length. Using binary offsets would break the trivial
325
382
                node_value = value
326
383
            self._nodes[key] = node_value
327
384
            if self._key_length > 1:
328
 
                subkey = list(reversed(key[:-1]))
 
385
                # TODO: We may want to do this lazily, but if we are calling
 
386
                #       _buffer_all, we are likely to be doing
 
387
                #       iter_entries_prefix
329
388
                key_dict = self._nodes_by_key
330
389
                if self.node_ref_lists:
331
390
                    key_value = key, node_value[0], node_value[1]
332
391
                else:
333
392
                    key_value = key, node_value
334
 
                # possibly should do this on-demand, but it seems likely it is 
335
 
                # always wanted
336
393
                # For a key of (foo, bar, baz) create
337
394
                # _nodes_by_key[foo][bar][baz] = key_value
338
395
                for subkey in key[:-1]:
1275
1332
                else:
1276
1333
                    yield self, key, node[2]
1277
1334
            return
 
1335
        nodes_by_key = self._get_nodes_by_key()
1278
1336
        for key in keys:
1279
1337
            # sanity check
1280
1338
            if key[0] is None:
1282
1340
            if len(key) != self._key_length:
1283
1341
                raise errors.BadIndexKey(key)
1284
1342
            # find what it refers to:
1285
 
            key_dict = self._nodes_by_key
 
1343
            key_dict = nodes_by_key
1286
1344
            elements = list(key)
1287
1345
            # find the subdict to return
1288
1346
            try: