mercurial/revlog.py

34879:7d51a7792f52

import binascii
import collections
import errno
import hashlib
import os
import struct
import zlib

# import stuff from node for others to import from revlog

    Assume that revs are sorted.
    """
    start = revlog.start
    length = revlog.length

    chunkqueue = collections.deque()
    chunkqueue.append((revs, 0))

    while chunkqueue:
        revs, depth = chunkqueue.popleft()

        startbyte = start(revs[0])
        endbyte = start(revs[-1]) + length(revs[-1])
        deltachainspan = endbyte - startbyte

        if deltachainspan <= revlog._srminblocksize or len(revs) <= 1:
            yield revs
            continue

        # 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:
                hole = revstart - prevend
                if hole > largesthole:
                    largesthole = hole
                    idxlargesthole = i

            textlen += revlen
            prevend = revstart + revlen

        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))

# index v0:
#  4 bytes: offset
#  4 bytes: compressed length
#  4 bytes: base rev

34880:9e18ab7f7240

import binascii
import collections
import errno
import hashlib
import heapq
import os
import struct
import zlib

# import stuff from node for others to import from revlog

    Assume that revs are sorted.
    """
    start = revlog.start
    length = revlog.length

    if len(revs) <= 1:
        yield revs
        return

    startbyte = start(revs[0])
    endbyte = start(revs[-1]) + length(revs[-1])
    readdata = deltachainspan = endbyte - startbyte

    chainpayload = sum(length(r) for r in revs)

    if deltachainspan:
        density = chainpayload / float(deltachainspan)
    else:
        density = 1.0

    # 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)

        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)

        # 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

    # 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
#  4 bytes: compressed length
#  4 bytes: base rev