--- a/mercurial/revlog.py Tue Oct 17 22:55:33 2017 -0400
+++ b/mercurial/revlog.py Wed Oct 18 12:53:00 2017 +0200
@@ -17,6 +17,7 @@
import collections
import errno
import hashlib
+import heapq
import os
import struct
import zlib
@@ -170,49 +171,59 @@
start = revlog.start
length = revlog.length
- chunkqueue = collections.deque()
- chunkqueue.append((revs, 0))
+ if len(revs) <= 1:
+ yield revs
+ return
- while chunkqueue:
- revs, depth = chunkqueue.popleft()
+ startbyte = start(revs[0])
+ endbyte = start(revs[-1]) + length(revs[-1])
+ readdata = deltachainspan = endbyte - startbyte
+
+ chainpayload = sum(length(r) for r in revs)
- startbyte = start(revs[0])
- endbyte = start(revs[-1]) + length(revs[-1])
- deltachainspan = endbyte - startbyte
+ if deltachainspan:
+ density = chainpayload / float(deltachainspan)
+ else:
+ density = 1.0
- if deltachainspan <= revlog._srminblocksize or len(revs) <= 1:
- yield revs
- continue
+ # Store the gaps in a heap to have them sorted by decreasing size
+ gapsheap = []
+ heapq.heapify(gapsheap)
+ prevend = None
+ for i, rev in enumerate(revs):
+ revstart = start(rev)
+ revlen = length(rev)
- # Find where is the largest hole (this is where we would split) and
- # sum up the lengths of useful data to compute the density of the span
- textlen = 0
- prevend = None
- largesthole = 0
- idxlargesthole = -1
- for i, rev in enumerate(revs):
- revstart = start(rev)
- revlen = length(rev)
+ if prevend is not None:
+ gapsize = revstart - prevend
+ if gapsize:
+ heapq.heappush(gapsheap, (-gapsize, i))
+
+ prevend = revstart + revlen
+
+ # Collect the indices of the largest holes until the density is acceptable
+ indicesheap = []
+ heapq.heapify(indicesheap)
+ while gapsheap and density < revlog._srdensitythreshold:
+ oppgapsize, gapidx = heapq.heappop(gapsheap)
+
+ heapq.heappush(indicesheap, gapidx)
- if prevend is not None:
- hole = revstart - prevend
- if hole > largesthole:
- largesthole = hole
- idxlargesthole = i
-
- textlen += revlen
- prevend = revstart + revlen
+ # the gap sizes are stored as negatives to be sorted decreasingly
+ # by the heap
+ readdata -= (-oppgapsize)
+ if readdata > 0:
+ density = chainpayload / float(readdata)
+ else:
+ density = 1.0
- density = textlen / float(deltachainspan) if deltachainspan > 0 else 1.0
-
- if density > revlog._srdensitythreshold:
- yield revs
- continue
-
- # Add the left and right parts so that they will be sliced
- # recursively too
- chunkqueue.append((revs[:idxlargesthole], depth + 1))
- chunkqueue.append((revs[idxlargesthole:], depth + 1))
+ # Cut the revs at collected indices
+ previdx = 0
+ while indicesheap:
+ idx = heapq.heappop(indicesheap)
+ yield revs[previdx:idx]
+ previdx = idx
+ yield revs[previdx:]
# index v0:
# 4 bytes: offset