aboutsummaryrefslogtreecommitdiffstats
path: root/tools/releasetools/blockimgdiff.py
diff options
context:
space:
mode:
Diffstat (limited to 'tools/releasetools/blockimgdiff.py')
-rw-r--r--tools/releasetools/blockimgdiff.py44
1 files changed, 23 insertions, 21 deletions
diff --git a/tools/releasetools/blockimgdiff.py b/tools/releasetools/blockimgdiff.py
index 31dabc7..cc06a42 100644
--- a/tools/releasetools/blockimgdiff.py
+++ b/tools/releasetools/blockimgdiff.py
@@ -1000,8 +1000,11 @@ class BlockImageDiff(object):
heap.append(xf.heap_item)
heapq.heapify(heap)
- sinks = set(u for u in G if not u.outgoing)
- sources = set(u for u in G if not u.incoming)
+ # Use OrderedDict() instead of set() to preserve the insertion order. Need
+ # to use 'sinks[key] = None' to add key into the set. sinks will look like
+ # { key1: None, key2: None, ... }.
+ sinks = OrderedDict.fromkeys(u for u in G if not u.outgoing)
+ sources = OrderedDict.fromkeys(u for u in G if not u.incoming)
def adjust_score(iu, delta):
iu.score += delta
@@ -1012,26 +1015,28 @@ class BlockImageDiff(object):
while G:
# Put all sinks at the end of the sequence.
while sinks:
- new_sinks = set()
+ new_sinks = OrderedDict()
for u in sinks:
if u not in G: continue
s2.appendleft(u)
del G[u]
for iu in u.incoming:
adjust_score(iu, -iu.outgoing.pop(u))
- if not iu.outgoing: new_sinks.add(iu)
+ if not iu.outgoing:
+ new_sinks[iu] = None
sinks = new_sinks
# Put all the sources at the beginning of the sequence.
while sources:
- new_sources = set()
+ new_sources = OrderedDict()
for u in sources:
if u not in G: continue
s1.append(u)
del G[u]
for iu in u.outgoing:
adjust_score(iu, +iu.incoming.pop(u))
- if not iu.incoming: new_sources.add(iu)
+ if not iu.incoming:
+ new_sources[iu] = None
sources = new_sources
if not G: break
@@ -1050,11 +1055,13 @@ class BlockImageDiff(object):
del G[u]
for iu in u.outgoing:
adjust_score(iu, +iu.incoming.pop(u))
- if not iu.incoming: sources.add(iu)
+ if not iu.incoming:
+ sources[iu] = None
for iu in u.incoming:
adjust_score(iu, -iu.outgoing.pop(u))
- if not iu.outgoing: sinks.add(iu)
+ if not iu.outgoing:
+ sinks[iu] = None
# Now record the sequence in the 'order' field of each transfer,
# and by rearranging self.transfers to be in the chosen sequence.
@@ -1073,8 +1080,7 @@ class BlockImageDiff(object):
# Each item of source_ranges will be:
# - None, if that block is not used as a source,
- # - a transfer, if one transfer uses it as a source, or
- # - a set of transfers.
+ # - an ordered set of transfers.
source_ranges = []
for b in self.transfers:
for s, e in b.src_ranges:
@@ -1082,23 +1088,19 @@ class BlockImageDiff(object):
source_ranges.extend([None] * (e-len(source_ranges)))
for i in range(s, e):
if source_ranges[i] is None:
- source_ranges[i] = b
+ source_ranges[i] = OrderedDict.fromkeys([b])
else:
- if not isinstance(source_ranges[i], set):
- source_ranges[i] = set([source_ranges[i]])
- source_ranges[i].add(b)
+ source_ranges[i][b] = None
for a in self.transfers:
- intersections = set()
+ intersections = OrderedDict()
for s, e in a.tgt_ranges:
for i in range(s, e):
if i >= len(source_ranges): break
- b = source_ranges[i]
- if b is not None:
- if isinstance(b, set):
- intersections.update(b)
- else:
- intersections.add(b)
+ # Add all the Transfers in source_ranges[i] to the (ordered) set.
+ if source_ranges[i] is not None:
+ for j in source_ranges[i]:
+ intersections[j] = None
for b in intersections:
if a is b: continue