~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_pyx.pyx

  • Committer: John Arbash Meinel
  • Date: 2009-06-12 03:34:17 UTC
  • mto: (4371.4.5 vila-better-heads)
  • mto: This revision was merged to the branch mainline in revision 4449.
  • Revision ID: john@arbash-meinel.com-20090612033417-cg8dj74mkbuth2ob
Changing the code to allow a special case for not always popping the
last item, and instead re-using that slot for the next item.
It resolves the issue with OOo (w/ OOo being so linear, my guess is 90% of it is
numbered with a single entry in the list, which probably caused cycles of 
deallocating the buffer, and reallocating it on every node.)

Not sure if it worth the ugliness, though. Certainly the code is more prone to
mistakes now.
I'll probably go back to the heapq version. Approximately as fast, and much more
elegant.

Show diffs side-by-side

added added

removed removed

Lines of Context:
31
31
    PyObject * PyTuple_GET_ITEM(object t, Py_ssize_t o)
32
32
    Py_ssize_t PyTuple_GET_SIZE(object t)
33
33
    PyObject * PyDict_GetItem(object d, object k)
34
 
    PyObject * PyDict_GetItem(object d, object k)
 
34
    int PyDict_SetItem(object d, object k, object v) except -1
35
35
    Py_ssize_t PyDict_Size(object d) except -1
36
36
    int PyDict_CheckExact(object d)
37
37
    int PyDict_Next(object d, Py_ssize_t *pos, PyObject **k, PyObject **v)
38
38
    int PyList_Append(object l, object v) except -1
39
39
    PyObject * PyList_GET_ITEM(object l, Py_ssize_t o)
40
40
    Py_ssize_t PyList_GET_SIZE(object l)
41
 
    int PyDict_SetItem(object d, object k, object v) except -1
 
41
    int PyList_SetItem(object l, Py_ssize_t o, object v) except -1
42
42
    int PySet_Add(object s, object k) except -1
43
43
    void Py_INCREF(object)
44
44
 
306
306
                # There is no PyList_Pop, though there is a simple static
307
307
                # 'listpop' function that is only exposed through python
308
308
                # methods
309
 
                node = nodes_to_number_pop()
 
309
                temp_node = PyList_GET_ITEM(nodes_to_number,
 
310
                                            PyList_GET_SIZE(nodes_to_number) - 1)
 
311
                node = <_KnownGraphNode>temp_node
310
312
                if node.gdfo != -1: # Already done
311
313
                    # This can happen when you have complex history, and one
312
314
                    # parent queues up a child, and the other parent then
313
315
                    # queues it up again
 
316
                    nodes_to_number_pop()
314
317
                    continue
315
318
                # Find the gdfo for this node based on all parent nodes
316
319
                parent_gdfo = 0
330
333
                if node.gdfo == -1:
331
334
                    # We could not number this node, yet, we assume we'll get
332
335
                    # back to it when we number a different parent
 
336
                    nodes_to_number_pop()
333
337
                    continue
334
338
                # This node was numbered. Let's number all the children we can
335
339
                # There is no PyList_Extend either, and from the looks of it,
336
340
                # listextend(list) is much more efficient because it can
337
341
                # pre-allocated for all entries that will be added, and can do
338
342
                # fast PySequence iteration.
339
 
                nodes_to_number_extend(node.children)
 
343
                if PyList_GET_SIZE(node.children) == 0:
 
344
                    nodes_to_number_pop()
 
345
                else:
 
346
                    temp_node = PyList_GET_ITEM(node.children, 0)
 
347
                    child_node = <_KnownGraphNode>temp_node
 
348
                    # PyList_SetItem steals a reference 
 
349
                    Py_INCREF(child_node)
 
350
                    PyList_SetItem(nodes_to_number,
 
351
                                   PyList_GET_SIZE(nodes_to_number) - 1,
 
352
                                   child_node)
 
353
                    for pos2 from 1 <= pos2 < PyList_GET_SIZE(node.children):
 
354
                        temp_node = PyList_GET_ITEM(node.children, pos2)
 
355
                        child_node = <_KnownGraphNode>temp_node
 
356
                        PyList_Append(nodes_to_number, child_node)
340
357
 
341
358
    def heads(self, keys):
342
359
        """Return the heads from amongst keys.