Mercurial > public > mercurial-scm > hg

comparison contrib/shrink-revlog.py @ 10627:adcd5bcb37ab

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
shrink-revlog: factor out postorder algorithm
author Benoit Boissinot <benoit.boissinot@ens-lyon.org>
date Wed, 10 Mar 2010 09:52:16 +0100
parents 3fc95c3bc3ba
children f63fb5c0cf67
comparison
equal deleted inserted replaced
10626:3fc95c3bc3ba 10627:adcd5bcb37ab
23 from mercurial import revlog, transaction, node, util 23 from mercurial import revlog, transaction, node, util
24 from mercurial import changegroup 24 from mercurial import changegroup
25 from mercurial.i18n import _ 25 from mercurial.i18n import _
26 26
27 27
28 def postorder(start, edges):
29 result = []
30 visit = list(start)
31 finished = set()
32
33 while visit:
34 cur = visit[-1]
35 for p in edges[cur]:
36 if p not in finished:
37 visit.append(p)
38 break
39 else:
40 result.append(cur)
41 finished.add(cur)
42 visit.pop()
43
44 return result
28 45
29 def toposort_reversepostorder(ui, rl): 46 def toposort_reversepostorder(ui, rl):
30 # postorder of the reverse directed graph 47 # postorder of the reverse directed graph
31 48
32 # map rev to list of parent revs (p2 first) 49 # map rev to list of parent revs (p2 first)
41 parents[rev] = () # root node 58 parents[rev] = () # root node
42 elif p1 == p2 or p2 == node.nullrev: 59 elif p1 == p2 or p2 == node.nullrev:
43 parents[rev] = (p1,) # normal node 60 parents[rev] = (p1,) # normal node
44 else: 61 else:
45 parents[rev] = (p2, p1) # merge node 62 parents[rev] = (p2, p1) # merge node
46
47 heads.add(rev) 63 heads.add(rev)
48
49 for p in parents[rev]: 64 for p in parents[rev]:
50 heads.discard(p) 65 heads.discard(p)
51 finally: 66 finally:
52 ui.progress(_('reading'), None, total=len(rl)) 67 ui.progress(_('reading'), None, total=len(rl))
53 68
69 heads = list(heads)
70 heads.sort(reverse=True)
71
54 ui.status(_('sorting revs\n')) 72 ui.status(_('sorting revs\n'))
55 result = [] 73 return postorder(heads, parents)
56 visit = list(heads)
57 visit.sort(reverse=True)
58 finished = set()
59
60 while visit:
61 cur = visit[-1]
62 for p in parents[cur]:
63 if p not in finished:
64 visit.append(p)
65 break
66 else:
67 result.append(cur)
68 finished.add(cur)
69 visit.pop()
70
71 return result
72 74
73 def toposort_postorderreverse(ui, rl): 75 def toposort_postorderreverse(ui, rl):
74 # reverse-postorder of the reverse directed graph 76 # reverse-postorder of the reverse directed graph
75 77
76 children = {} 78 children = {}
80 for rev in rl: 82 for rev in rl:
81 ui.progress(_('reading'), rev, total=len(rl)) 83 ui.progress(_('reading'), rev, total=len(rl))
82 (p1, p2) = rl.parentrevs(rev) 84 (p1, p2) = rl.parentrevs(rev)
83 if p1 == p2 == node.nullrev: 85 if p1 == p2 == node.nullrev:
84 roots.add(rev) 86 roots.add(rev)
85
86 children[rev] = [] 87 children[rev] = []
87
88 if p1 != node.nullrev: 88 if p1 != node.nullrev:
89 children[p1].append(rev) 89 children[p1].append(rev)
90 if p2 != node.nullrev: 90 if p2 != node.nullrev:
91 children[p2].append(rev) 91 children[p2].append(rev)
92 finally: 92 finally:
93 ui.progress(_('reading'), None, total=len(rl)) 93 ui.progress(_('reading'), None, total=len(rl))
94 94
95 root = list(roots)
96 roots.sort()
97
95 ui.status(_('sorting revs\n')) 98 ui.status(_('sorting revs\n'))
96 result = [] 99 result = postorder(roots, children)
97 visit = list(roots)
98 visit.sort()
99 finished = set()
100
101 while visit:
102 cur = visit[-1]
103 for p in children[cur]:
104 if p not in finished:
105 visit.append(p)
106 break
107 else:
108 result.append(cur)
109 finished.add(cur)
110 visit.pop()
111
112 result.reverse() 100 result.reverse()
113 return result 101 return result
114 102
115 def writerevs(ui, r1, r2, order, tr): 103 def writerevs(ui, r1, r2, order, tr):
116 104