« back to all changes in this revision
Viewing changes to bzrlib/_known_graph_pyx.pyx
- browse files at revision 4371.3.40
- compare with another revision
- compare with revision 4017
- download diff
- download tarball
- view history from revision 4371.3.40
- Committer: John Arbash Meinel
- Date: 2009-06-12 20:21:08 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-20090612202108-blsyks1kdxod0lsk
Fixes for linear_nodes in the pyrex version.
Doesn't seem to specifically impact performance.
Doesn't seem to specifically impact performance.
- files modified:
- bzrlib/_known_graph_py.py
added
removed
bzrlib/_known_graph_pyx.pyx
404
404
heads_key = PyFrozenSet_New(candidate_nodes)
405
405
if len(candidate_nodes) < 2:
406
406
return heads_key
407
# Check the linear dominators of these keys, to see if we already
408
# know the heads answer
409
dom_lookup_key, heads = self._heads_from_dominators(candidate_nodes)
407
dom_to_node = self._get_dominators_to_nodes(candidate_nodes)
408
if PyDict_Size(candidate_nodes) < 2:
409
return frozenset(candidate_nodes)
410
dom_lookup_key, heads = self._heads_from_dominators(candidate_nodes,
411
dom_to_node)
410
412
if heads is not None:
411
413
if self.do_cache:
412
414
# This heads was not in the cache, or it would have been caught
413
415
# earlier, but the dom head *was*, so do the simple cache
414
416
PyDict_SetItem(self._known_heads, heads_key, heads)
415
417
return heads
416
heads = self._heads_from_candidate_nodes(candidate_nodes)
418
heads = self._heads_from_candidate_nodes(candidate_nodes, dom_to_node)
417
419
if self.do_cache:
418
420
self._cache_heads(heads, heads_key, dom_lookup_key, candidate_nodes)
419
421
return heads
434
436
PyDict_SetItem(self._known_heads, dom_lookup_key,
435
437
PyFrozenSet_New(dom_heads))
436
438
437
cdef object _heads_from_dominators(self, candidate_nodes):
439
cdef _get_dominators_to_nodes(self, candidate_nodes):
440
"""Get the reverse mapping from dominator_key => candidate_nodes.
441
442
As a side effect, this can also remove potential candidate nodes if we
443
determine that they share a dominator.
444
"""
445
cdef Py_ssize_t pos
446
cdef _KnownGraphNode node, other_node
447
cdef PyObject *temp_node
448
cdef PyObject *maybe_node
449
450
dom_to_node = {}
451
keys_to_remove = []
452
pos = 0
453
while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
454
node = <_KnownGraphNode>temp_node
455
dom_key = node.linear_dominator_node.key
456
maybe_node = PyDict_GetItem(dom_to_node, dom_key)
457
if maybe_node == NULL:
458
PyDict_SetItem(dom_to_node, dom_key, node)
459
else:
460
other_node = <_KnownGraphNode>maybe_node
461
# These nodes share a dominator, one of them obviously
462
# supersedes the other, figure out which
463
if other_node.gdfo > node.gdfo:
464
PyList_Append(keys_to_remove, node.key)
465
else:
466
# This wins, replace the other
467
PyList_Append(keys_to_remove, other_node.key)
468
PyDict_SetItem(dom_to_node, dom_key, node)
469
for pos from 0 <= pos < PyList_GET_SIZE(keys_to_remove):
470
key = <object>PyList_GET_ITEM(keys_to_remove, pos)
471
candidate_nodes.pop(key)
472
return dom_to_node
473
474
cdef object _heads_from_dominators(self, candidate_nodes, dom_to_node):
438
475
cdef PyObject *maybe_heads
439
cdef PyObject *maybe_key
476
cdef PyObject *maybe_node
440
477
cdef _KnownGraphNode node
441
478
cdef Py_ssize_t pos
442
479
cdef PyObject *temp_node
452
489
return dom_lookup_key, None
453
490
# We need to map back from the dominator head to the original keys
454
491
dom_heads = <object>maybe_heads
455
dom_to_key = {}
456
pos = 0
457
while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
458
node = <_KnownGraphNode>temp_node
459
PyDict_SetItem(dom_to_key, node.linear_dominator_node.key,
460
node.key)
461
492
heads = []
462
493
for dom_key in dom_heads:
463
maybe_key = PyDict_GetItem(dom_to_key, dom_key)
464
if maybe_key == NULL:
494
maybe_node = PyDict_GetItem(dom_to_node, dom_key)
495
if maybe_node == NULL:
465
496
# Should never happen
466
497
raise KeyError
467
PyList_Append(heads, <object>maybe_key)
498
node = <_KnownGraphNode>maybe_node
499
PyList_Append(heads, node.key)
468
500
return dom_lookup_key, PyFrozenSet_New(heads)
469
501
470
502
cdef int _process_parent(self, _KnownGraphNode node,
471
503
_KnownGraphNode parent_node,
472
candidate_nodes,
504
candidate_nodes, dom_to_node,
473
505
queue, int *replace_item) except -1:
474
506
"""Process the parent of a node, seeing if we need to walk it."""
475
507
cdef PyObject *maybe_candidate
508
cdef PyObject *maybe_node
509
cdef _KnownGraphNode dom_child_node
476
510
maybe_candidate = PyDict_GetItem(candidate_nodes, parent_node.key)
477
511
if maybe_candidate != NULL:
478
512
candidate_nodes.pop(parent_node.key)
479
513
# We could pass up a flag that tells the caller to stop processing,
480
514
# but it doesn't help much, and makes the code uglier
481
515
return 0
516
maybe_node = PyDict_GetItem(dom_to_node, parent_node.key)
517
if maybe_node != NULL:
518
# This is a dominator of a node
519
dom_child_node = <_KnownGraphNode>maybe_node
520
if dom_child_node is not node:
521
# It isn't a dominator of a node we are searching, so we should
522
# remove it from the search
523
maybe_candidate = PyDict_GetItem(candidate_nodes, dom_child_node.key)
524
if maybe_candidate != NULL:
525
candidate_nodes.pop(dom_child_node.key)
526
return 0
482
527
if parent_node.ancestor_of is None:
483
528
# This node hasn't been walked yet, so just project node's ancestor
484
529
# info directly to parent_node, and enqueue it for later processing
499
544
parent_node.ancestor_of = tuple(sorted(all_ancestors))
500
545
return 0
501
546
502
cdef object _heads_from_candidate_nodes(self, candidate_nodes):
547
cdef object _heads_from_candidate_nodes(self, candidate_nodes, dom_to_node):
503
548
cdef _KnownGraphNode node
504
549
cdef _KnownGraphNode parent_node
505
550
cdef Py_ssize_t num_candidates
554
599
# We know that there is nothing between here and the tail
555
600
# that is interesting, so skip to the end
556
601
self._process_parent(node, node.linear_dominator_node,
557
candidate_nodes, queue, &replace_item)
602
candidate_nodes, dom_to_node, queue, &replace_item)
558
603
else:
559
604
for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
560
605
parent_node = _get_parent(node.parents, pos)
561
606
self._process_parent(node, parent_node, candidate_nodes,
562
queue, &replace_item)
607
dom_to_node, queue, &replace_item)
563
608
for pos from 0 <= pos < PyList_GET_SIZE(self._to_cleanup):
564
609
node = _get_list_node(self._to_cleanup, pos)
565
610
node.ancestor_of = None
Loggerhead is a web-based interface for Breezy
Version: 2.0.1