Ticket #393: choose_segs3.py

def choose_segs(filesize, segsize, offset, length):
    """
    What segments do you need to write to, and to read from, given an
    filesize-byte file, split into segsize-byte segments, the last one of
    which could be fewer than segsize bytes, and an offset and non-zero
    length that needs to be written? Those are the inputs to the
    algorithm. The output is: first_segment (int), fetch_first_segment
    (boolean), last_segment (int), fetch_last_segment (boolean). The meaning
    of "fetch" is: "We have to fetch the current value of this segment in
    order to compute what the new value of the segment should be.". That is
    true whenever the write is writing part of the segment and leaving other
    bytes within the segment with their current value.

    The only constraints on the output are that last_segment >=
    first_segment, and that if last_segment == first_segment then
    fetch_last_segment == first_first_segment.
    """
    precondition(filesize >= 0, filesize)
    precondition(segsize >= 1, segsize)
    precondition(offset >= 0, offset)
    precondition(length >= 1, length)

    first_segment_of_write = offset // segsize
    last_byte_of_write = offset + length - 1
    last_segment_of_write = last_byte_of_write // segsize

    num_segs_in_current = div_ceil(filesize, segsize)
    last_segment_of_current = num_segs_in_current - 1

    # Now let's figure out if we need to fetch the first segment. Initialize
    # fetch_last_segment to True and then check whether we don't actually
    # need to fetch it.
    fetch_first_segment = True
    if first_segment_of_write > last_segment_of_current:
        # If it is a segment that doesn't currently exist at all (it is past
        # the end) then we don't need to fetch it.
        fetch_first_segment = False
    elif (first_segment_of_write == last_segment_of_current) and \
            (offset == (first_segment_of_write * segsize)) and \
            ((offset + length) >= filesize):
        # If this segment is the last segment of the current file and we're
        # overwriting all the bytes in this segment, then no need to fetch
        # it.
        fetch_first_segment = False
    elif (offset == (first_segment_of_write * segsize)) and \
            ((offset + length) >= ((first_segment_of_write+1) * segsize)):
        # If we are overwriting the entire segment, then no need to fetch the
        # current version.
        fetch_first_segment = False

    # If the last segment is also the first segment, then we're done.
    if last_segment_of_write == first_segment_of_write:
        return (first_segment, fetch_first_segment, first_segment, fetch_first_segment)

    # Now let's figure out if we need to fetch the last segment.
    fetch_last_segment = True

    if last_segment_of_write > last_segment_of_current:
        # If it is a segment that doesn't currently exist at all (it is past
        # the end) then we don't need to fetch it.
        fetch_last_segment = False
    elif last_segment_of_write == last_segment_of_current:
        # If this is the last segment of the current file and we are
        # overwriting all of the bytes in this segment, then we don't need to fetch it.
        if offset + length >= filesize:
            fetch_last_segment = False
    else:
        # If we are overwriting the entire segment, then no need to fetch the
        # current version.
        if (offset + length) % segsize == 0:
            fetch_last_segment = False
        
    return (first_segment, fetch_first_segment, last_segment, fetch_last_segment)