Fossil SCM
Put the graph traversal core of the cycle breaker core into a separate class, for use in other parts of the system. TODO: Rewrite the cycle breaker core in terms of this class.
Commit
e70131373302d41968d95982033ddf3ef3de54f9
Parent
82e35d330423ddb…
2 files changed
+112
+1
| --- a/tools/cvs2fossil/lib/c2f_gtcore.tcl | ||
| +++ b/tools/cvs2fossil/lib/c2f_gtcore.tcl | ||
| @@ -0,0 +1,112 @@ | ||
| 1 | +$graph destroytializeCandidates $graph | |
| 2 | + } | |
| 3 | + | |
| 4 | + log write 3 gtcore Done. | |
| 5 | + ClearHooks | |
| 6 | + return | |
| 7 | + } | |
| 8 | + | |
| 9 | + # # ## ### ##### ######## ############# | |
| 10 | + ## Internal methods | |
| 11 | + | |
| 12 | + # Instead of searching the whole graph for the degree-0 nodes in | |
| 13 | + # each iteration we compute the list once to start, and then only | |
| 14 | + # update it incrementally based on the outgoing neighbours of the | |
| 15 | + # node chosen for commit. | |
| 16 | + | |
| 17 | + proc InitializeCandidates {graph} { | |
| 18 | + # bottom = list (list (node, range min, range max)) | |
| 19 | + ::variable mybottom | |
| 20 | + foreach node [$graph nodes] { | |
| 21 | + if {[$graph node degree -in $node]} continue | |
| 22 | + lappend mybottom [list $node [DataHook $graph $node]] | |
| 23 | + } | |
| 24 | + ScheduleCandidates $graph | |
| 25 | + ShowPendingNodes $graph | |
| 26 | + return | |
| 27 | + } | |
| 28 | + | |
| 29 | + proc WithoutPredecessor {graph nodevar} { | |
| 30 | + ::variable mybottom | |
| 31 | + | |
| 32 | + upvar 1 $nodevar node | |
| 33 | + if {![llength $mybottom]} { return 0 } | |
| 34 | + | |
| 35 | + set node [lindex [lindex $mybottom 0] 0] | |
| 36 | + set mybottom [lrange $mybottom 1 end] | |
| 37 | + set changed 0 | |
| 38 | + | |
| 39 | + # Update list of nodes without predecessor, based on the | |
| 40 | + # outgoing neighbours of the chosen node. This should be | |
| 41 | + # faster than iterating of the whole set of nodes, finding all | |
| 42 | + # without predecessors, sorting them by time, etc. pp. | |
| 43 | + | |
| 44 | + foreach out [$graph nodes -out $node] { | |
| 45 | + if {[$graph node degree -in $out] > 1} continue | |
| 46 | + # Degree-1 neighbour, will have no predecessors after the | |
| 47 | + # removal of n. Put on the list of candidates we can | |
| 48 | + # process. | |
| 49 | + lappend mybottom [list $out [DataHook $graph $out]] | |
| 50 | + set changed 1 | |
| 51 | + } | |
| 52 | + if {$changed} { | |
| 53 | + ScheduleCandidates $graph | |
| 54 | + } | |
| 55 | + | |
| 56 | + # We do not delete the node immediately, to allow the Save | |
| 57 | + # procedure to save the dependencies as well (encoded in the | |
| 58 | + # arcs). | |
| 59 | + return 1 | |
| 60 | + } | |
| 61 | + | |
| 62 | + proc ScheduleCandidates {graph} { | |
| 63 | + ::variable mybottom | |
| 64 | + ::variable mysortcmd | |
| 65 | + if {[llength $mysortcmd]} { | |
| 66 | + set mybottom [uplevel \#0 [linsert $mysortcmd end $graph $mybottom]] | |
| 67 | + } else { | |
| 68 | + set mybottom [lsort -index 0 -dict $mybottom] | |
| 69 | + } | |
| 70 | + return | |
| 71 | + } | |
| 72 | + | |
| 73 | + proc ShowPendingNodes {graph} { | |
| 74 | + if {[log verbosity?] < 10} return | |
| 75 | + ::variable mybottom | |
| 76 | + ::variable myformatcmd | |
| 77 | + | |
| 78 | + log write 10 gtcore "Pending..............................." | |
| 79 | + foreach item [struct::list map $mybottom \ | |
| 80 | + [linsert $myformatcmd end $graph]] { | |
| 81 | + log write 10 gtcore "Pending: $item" | |
| 82 | + } | |
| 83 | + return | |
| 84 | + } | |
| 85 | + | |
| 86 | + # # ## ### ##### ######## ############# | |
| 87 | + ## Callback invokation ... | |
| 88 | + | |
| 89 | + proc DataHook {graph node} { | |
| 90 | + # Allow the user of the traverser to a client data to a node | |
| 91 | + # in the list of nodes available for immediate processing. | |
| 92 | + # This data can be used by the sort callback. | |
| 93 | + | |
| 94 | + ::variable mydatacmd | |
| 95 | + if {![llength $mydatacmd]} { return {} } | |
| 96 | + | |
| 97 | + return [uplevel \#0 [linsert $mydatacmd end $graph $node]] | |
| 98 | + } | |
| 99 | + | |
| 100 | + proc FormatHook {graph item} { | |
| 101 | + # Allow the user to format a pending item (node + client data) | |
| 102 | + # according to its wishes. | |
| 103 | + | |
| 104 | + ::variable myformatcmd | |
| 105 | + if {![llength $myformatcmd]} { return $item } | |
| 106 | + | |
| 107 | + return [uplevel \#0 [linsert $myformatcmd end $graph $item]] | |
| 108 | + } | |
| 109 | + | |
| 110 | + proc ProcessedHook {graph node} { | |
| 111 | + # Give the user of the traverser the opportunity to work with | |
| 112 | + # the node before it is removed from |
| --- a/tools/cvs2fossil/lib/c2f_gtcore.tcl | |
| +++ b/tools/cvs2fossil/lib/c2f_gtcore.tcl | |
| @@ -0,0 +1,112 @@ | |
| --- a/tools/cvs2fossil/lib/c2f_gtcore.tcl | |
| +++ b/tools/cvs2fossil/lib/c2f_gtcore.tcl | |
| @@ -0,0 +1,112 @@ | |
| 1 | $graph destroytializeCandidates $graph |
| 2 | } |
| 3 | |
| 4 | log write 3 gtcore Done. |
| 5 | ClearHooks |
| 6 | return |
| 7 | } |
| 8 | |
| 9 | # # ## ### ##### ######## ############# |
| 10 | ## Internal methods |
| 11 | |
| 12 | # Instead of searching the whole graph for the degree-0 nodes in |
| 13 | # each iteration we compute the list once to start, and then only |
| 14 | # update it incrementally based on the outgoing neighbours of the |
| 15 | # node chosen for commit. |
| 16 | |
| 17 | proc InitializeCandidates {graph} { |
| 18 | # bottom = list (list (node, range min, range max)) |
| 19 | ::variable mybottom |
| 20 | foreach node [$graph nodes] { |
| 21 | if {[$graph node degree -in $node]} continue |
| 22 | lappend mybottom [list $node [DataHook $graph $node]] |
| 23 | } |
| 24 | ScheduleCandidates $graph |
| 25 | ShowPendingNodes $graph |
| 26 | return |
| 27 | } |
| 28 | |
| 29 | proc WithoutPredecessor {graph nodevar} { |
| 30 | ::variable mybottom |
| 31 | |
| 32 | upvar 1 $nodevar node |
| 33 | if {![llength $mybottom]} { return 0 } |
| 34 | |
| 35 | set node [lindex [lindex $mybottom 0] 0] |
| 36 | set mybottom [lrange $mybottom 1 end] |
| 37 | set changed 0 |
| 38 | |
| 39 | # Update list of nodes without predecessor, based on the |
| 40 | # outgoing neighbours of the chosen node. This should be |
| 41 | # faster than iterating of the whole set of nodes, finding all |
| 42 | # without predecessors, sorting them by time, etc. pp. |
| 43 | |
| 44 | foreach out [$graph nodes -out $node] { |
| 45 | if {[$graph node degree -in $out] > 1} continue |
| 46 | # Degree-1 neighbour, will have no predecessors after the |
| 47 | # removal of n. Put on the list of candidates we can |
| 48 | # process. |
| 49 | lappend mybottom [list $out [DataHook $graph $out]] |
| 50 | set changed 1 |
| 51 | } |
| 52 | if {$changed} { |
| 53 | ScheduleCandidates $graph |
| 54 | } |
| 55 | |
| 56 | # We do not delete the node immediately, to allow the Save |
| 57 | # procedure to save the dependencies as well (encoded in the |
| 58 | # arcs). |
| 59 | return 1 |
| 60 | } |
| 61 | |
| 62 | proc ScheduleCandidates {graph} { |
| 63 | ::variable mybottom |
| 64 | ::variable mysortcmd |
| 65 | if {[llength $mysortcmd]} { |
| 66 | set mybottom [uplevel \#0 [linsert $mysortcmd end $graph $mybottom]] |
| 67 | } else { |
| 68 | set mybottom [lsort -index 0 -dict $mybottom] |
| 69 | } |
| 70 | return |
| 71 | } |
| 72 | |
| 73 | proc ShowPendingNodes {graph} { |
| 74 | if {[log verbosity?] < 10} return |
| 75 | ::variable mybottom |
| 76 | ::variable myformatcmd |
| 77 | |
| 78 | log write 10 gtcore "Pending..............................." |
| 79 | foreach item [struct::list map $mybottom \ |
| 80 | [linsert $myformatcmd end $graph]] { |
| 81 | log write 10 gtcore "Pending: $item" |
| 82 | } |
| 83 | return |
| 84 | } |
| 85 | |
| 86 | # # ## ### ##### ######## ############# |
| 87 | ## Callback invokation ... |
| 88 | |
| 89 | proc DataHook {graph node} { |
| 90 | # Allow the user of the traverser to a client data to a node |
| 91 | # in the list of nodes available for immediate processing. |
| 92 | # This data can be used by the sort callback. |
| 93 | |
| 94 | ::variable mydatacmd |
| 95 | if {![llength $mydatacmd]} { return {} } |
| 96 | |
| 97 | return [uplevel \#0 [linsert $mydatacmd end $graph $node]] |
| 98 | } |
| 99 | |
| 100 | proc FormatHook {graph item} { |
| 101 | # Allow the user to format a pending item (node + client data) |
| 102 | # according to its wishes. |
| 103 | |
| 104 | ::variable myformatcmd |
| 105 | if {![llength $myformatcmd]} { return $item } |
| 106 | |
| 107 | return [uplevel \#0 [linsert $myformatcmd end $graph $item]] |
| 108 | } |
| 109 | |
| 110 | proc ProcessedHook {graph node} { |
| 111 | # Give the user of the traverser the opportunity to work with |
| 112 | # the node before it is removed from |
| --- tools/cvs2fossil/lib/pkgIndex.tcl | ||
| +++ tools/cvs2fossil/lib/pkgIndex.tcl | ||
| @@ -21,10 +21,11 @@ | ||
| 21 | 21 | package ifneeded vc::fossil::import::cvs::pass::breakrcycle 1.0 [list source [file join $dir c2f_pbreakrcycle.tcl]] |
| 22 | 22 | package ifneeded vc::fossil::import::cvs::pass::rtopsort 1.0 [list source [file join $dir c2f_prtopsort.tcl]] |
| 23 | 23 | package ifneeded vc::fossil::import::cvs::pass::breakscycle 1.0 [list source [file join $dir c2f_pbreakscycle.tcl]] |
| 24 | 24 | package ifneeded vc::fossil::import::cvs::pass::breakacycle 1.0 [list source [file join $dir c2f_pbreakacycle.tcl]] |
| 25 | 25 | package ifneeded vc::fossil::import::cvs::pass::atopsort 1.0 [list source [file join $dir c2f_patopsort.tcl]] |
| 26 | +package ifneeded vc::fossil::import::cvs::gtcore 1.0 [list source [file join $dir c2f_gtcore.tcl]] | |
| 26 | 27 | package ifneeded vc::fossil::import::cvs::cyclebreaker 1.0 [list source [file join $dir c2f_cyclebreaker.tcl]] |
| 27 | 28 | package ifneeded vc::fossil::import::cvs::project 1.0 [list source [file join $dir c2f_project.tcl]] |
| 28 | 29 | package ifneeded vc::fossil::import::cvs::project::lodmgr 1.0 [list source [file join $dir c2f_plodmgr.tcl]] |
| 29 | 30 | package ifneeded vc::fossil::import::cvs::project::rev 1.0 [list source [file join $dir c2f_prev.tcl]] |
| 30 | 31 | package ifneeded vc::fossil::import::cvs::project::revlink 1.0 [list source [file join $dir c2f_prevlink.tcl]] |
| 31 | 32 |
| --- tools/cvs2fossil/lib/pkgIndex.tcl | |
| +++ tools/cvs2fossil/lib/pkgIndex.tcl | |
| @@ -21,10 +21,11 @@ | |
| 21 | package ifneeded vc::fossil::import::cvs::pass::breakrcycle 1.0 [list source [file join $dir c2f_pbreakrcycle.tcl]] |
| 22 | package ifneeded vc::fossil::import::cvs::pass::rtopsort 1.0 [list source [file join $dir c2f_prtopsort.tcl]] |
| 23 | package ifneeded vc::fossil::import::cvs::pass::breakscycle 1.0 [list source [file join $dir c2f_pbreakscycle.tcl]] |
| 24 | package ifneeded vc::fossil::import::cvs::pass::breakacycle 1.0 [list source [file join $dir c2f_pbreakacycle.tcl]] |
| 25 | package ifneeded vc::fossil::import::cvs::pass::atopsort 1.0 [list source [file join $dir c2f_patopsort.tcl]] |
| 26 | package ifneeded vc::fossil::import::cvs::cyclebreaker 1.0 [list source [file join $dir c2f_cyclebreaker.tcl]] |
| 27 | package ifneeded vc::fossil::import::cvs::project 1.0 [list source [file join $dir c2f_project.tcl]] |
| 28 | package ifneeded vc::fossil::import::cvs::project::lodmgr 1.0 [list source [file join $dir c2f_plodmgr.tcl]] |
| 29 | package ifneeded vc::fossil::import::cvs::project::rev 1.0 [list source [file join $dir c2f_prev.tcl]] |
| 30 | package ifneeded vc::fossil::import::cvs::project::revlink 1.0 [list source [file join $dir c2f_prevlink.tcl]] |
| 31 |
| --- tools/cvs2fossil/lib/pkgIndex.tcl | |
| +++ tools/cvs2fossil/lib/pkgIndex.tcl | |
| @@ -21,10 +21,11 @@ | |
| 21 | package ifneeded vc::fossil::import::cvs::pass::breakrcycle 1.0 [list source [file join $dir c2f_pbreakrcycle.tcl]] |
| 22 | package ifneeded vc::fossil::import::cvs::pass::rtopsort 1.0 [list source [file join $dir c2f_prtopsort.tcl]] |
| 23 | package ifneeded vc::fossil::import::cvs::pass::breakscycle 1.0 [list source [file join $dir c2f_pbreakscycle.tcl]] |
| 24 | package ifneeded vc::fossil::import::cvs::pass::breakacycle 1.0 [list source [file join $dir c2f_pbreakacycle.tcl]] |
| 25 | package ifneeded vc::fossil::import::cvs::pass::atopsort 1.0 [list source [file join $dir c2f_patopsort.tcl]] |
| 26 | package ifneeded vc::fossil::import::cvs::gtcore 1.0 [list source [file join $dir c2f_gtcore.tcl]] |
| 27 | package ifneeded vc::fossil::import::cvs::cyclebreaker 1.0 [list source [file join $dir c2f_cyclebreaker.tcl]] |
| 28 | package ifneeded vc::fossil::import::cvs::project 1.0 [list source [file join $dir c2f_project.tcl]] |
| 29 | package ifneeded vc::fossil::import::cvs::project::lodmgr 1.0 [list source [file join $dir c2f_plodmgr.tcl]] |
| 30 | package ifneeded vc::fossil::import::cvs::project::rev 1.0 [list source [file join $dir c2f_prev.tcl]] |
| 31 | package ifneeded vc::fossil::import::cvs::project::revlink 1.0 [list source [file join $dir c2f_prevlink.tcl]] |
| 32 |