← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_pyx.pyx

  • Committer: Vincent Ladeuil
  • Date: 2009-06-18 18:26:10 UTC
  • mto: This revision was merged to the branch mainline in revision 4466.
  • Revision ID: v.ladeuil+lp@free.fr-20090618182610-o59r8149nlzb3b68
Simplify gdfo computing by finding tails when at graph build time.

* bzrlib/_known_graph_pyx.pyx:
(KnownGraph._get_or_create_node): We need to know if the ndoe as
created.
(KnownGraph._initialize_nodes): Calulate tails ahead of time to
intialize gdfo computing.
(KnownGraph._find_gdfo): Use tails directly.

* bzrlib/_known_graph_py.py:
(KnownGraph._initialize_nodes): Calulate tails ahead of time to
intialize gdfo computing.
(KnownGraph._find_gdfo): Use tails directly.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_pyx.pyx
150
150
    """This is a class which assumes we already know the full graph."""
151
151
 
152
152
    cdef public object _nodes
 
153
    cdef public object _tails
153
154
    cdef object _known_heads
154
155
    cdef public int do_cache
155
156
    # Nodes we've touched that we'll need to reset their info when heads() is
179
180
            child = <_KnownGraphNode>temp_node
180
181
            child.clear_references()
181
182
 
182
 
    cdef _KnownGraphNode _get_or_create_node(self, key):
 
183
    cdef _KnownGraphNode _get_or_create_node(self, key, int *created):
183
184
        cdef PyObject *temp_node
184
185
        cdef _KnownGraphNode node
185
186
 
187
188
        if temp_node == NULL:
188
189
            node = _KnownGraphNode(key)
189
190
            PyDict_SetItem(self._nodes, key, node)
 
191
            created[0] = 1 # True
190
192
        else:
191
193
            node = <_KnownGraphNode>temp_node
 
194
            created[0] = 0 # False
192
195
        return node
193
196
 
194
197
    def _initialize_nodes(self, parent_map):
195
198
        """Populate self._nodes.
196
199
 
197
 
        After this has finished, self._nodes will have an entry for every entry
198
 
        in parent_map. Ghosts will have a parent_keys = None, all nodes found
199
 
        will also have .child_keys populated with all known child_keys.
 
200
        After this has finished:
 
201
        - self._nodes will have an entry for every entry in parent_map.
 
202
        - ghosts will have a parent_keys = None,
 
203
        - all nodes found will also have .child_keys populated with all known
 
204
          child_keys,
 
205
        - self._tails will list all the nodes without parents.
200
206
        """
201
207
        cdef PyObject *temp_key, *temp_parent_keys, *temp_node
202
208
        cdef Py_ssize_t pos, pos2, num_parent_keys
203
209
        cdef _KnownGraphNode node
204
210
        cdef _KnownGraphNode parent_node
 
211
        cdef int created
205
212
 
 
213
        tails = self._tails = set()
206
214
        nodes = self._nodes
207
215
 
208
216
        if not PyDict_CheckExact(parent_map):
212
220
        while PyDict_Next(parent_map, &pos, &temp_key, &temp_parent_keys):
213
221
            key = <object>temp_key
214
222
            parent_keys = <object>temp_parent_keys
215
 
            node = self._get_or_create_node(key)
 
223
            num_parent_keys = len(parent_keys)
 
224
            node = self._get_or_create_node(key, &created)
 
225
            if not created and num_parent_keys != 0:
 
226
                # This node has been added before being seen in parent_map (see
 
227
                # below)
 
228
                tails.remove(node)
216
229
            # We know how many parents, so we could pre allocate an exact sized
217
230
            # tuple here
218
 
            num_parent_keys = len(parent_keys)
219
231
            parent_nodes = PyTuple_New(num_parent_keys)
220
232
            # We use iter here, because parent_keys maybe be a list or tuple
221
233
            for pos2 from 0 <= pos2 < num_parent_keys:
222
 
                parent_key = parent_keys[pos2]
223
 
                parent_node = self._get_or_create_node(parent_keys[pos2])
 
234
                parent_node = self._get_or_create_node(parent_keys[pos2],
 
235
                                                       &created)
 
236
                if created:
 
237
                    # Potentially a tail, if we're wrong we'll remove it later
 
238
                    # (see above)
 
239
                    tails.add(parent_node)
224
240
                # PyTuple_SET_ITEM will steal a reference, so INCREF first
225
241
                Py_INCREF(parent_node)
226
242
                PyTuple_SET_ITEM(parent_nodes, pos2, parent_node)
315
331
 
316
332
        nodes = self._nodes
317
333
        pending = []
318
 
        known_parent_gdfos = dict.fromkeys(nodes.keys(), 0)
 
334
        known_parent_gdfos = {}
319
335
 
320
 
        for node in nodes.values():
321
 
            if not node.parents:
322
 
                node.gdfo = 1
323
 
                known_parent_gdfos[node.key] = 0
324
 
                pending.append(node)
 
336
        for node in self._tails:
 
337
            node.gdfo = 1
 
338
            known_parent_gdfos[node] = 0
 
339
            pending.append(node)
325
340
 
326
341
        while pending:
327
342
            node = <_KnownGraphNode>pending.pop()
328
343
            for child in node.children:
329
 
                known_parent_gdfos[child.key] = known_parent_gdfos[child.key] + 1
 
344
                try:
 
345
                    known_parents = known_parent_gdfos[child.key]
 
346
                except KeyError:
 
347
                    known_parents = 0
 
348
                known_parent_gdfos[child.key] = known_parents + 1
330
349
                if child.gdfo is None or node.gdfo + 1 > child.gdfo:
331
350
                    child.gdfo = node.gdfo + 1
332
351
                if known_parent_gdfos[child.key] == len(child.parents):