Ticket #393: choose_segs2.py

File choose_segs2.py, 3.1 KB (added by zooko, at 2011-09-03T07:03:34Z)
Line 
1def choose_segs(filesize, segsize, offset, length):
2    """
3    What segments do you need to write to, and to read from, given an
4    filesize-byte file, split into segsize-byte segments, the last one of
5    which could be fewer than segsize bytes, and an offset and non-zero
6    length that needs to be written? Those are the inputs to the
7    algorithm. The output is: first_segment (int), fetch_first_segment
8    (boolean), last_segment (int), fetch_last_segment (boolean). The meaning
9    of "fetch" is: "We have to fetch the current value of this segment in
10    order to compute what the new value of the segment should be.". That is
11    true whenever the write is writing part of the segment and leaving other
12    bytes within the segment with their current value.
13
14    The only constraints on the output are that last_segment >=
15    first_segment, and that if last_segment == first_segment then
16    fetch_last_segment == first_first_segment.
17    """
18    precondition(filesize >= 0, filesize)
19    precondition(segsize >= 1, segsize)
20    precondition(offset >= 0, offset)
21    precondition(length >= 1, length)
22
23    first_segment_of_write = offset // segsize
24    last_byte_of_write = offset + length - 1
25    last_segment_of_write = last_byte_of_write // segsize
26
27    num_segs_in_current = div_ceil(filesize, segsize)
28    last_segment_of_current = num_segs_in_current - 1
29
30    # Now let's figure out if we need to fetch the first segment. Initialize
31    # fetch_last_segment to True and then check whether we don't actually
32    # need to fetch it.
33    fetch_first_segment = True
34    if first_segment_of_write > last_segment_of_current:
35        # If it is a segment that doesn't currently exist at all (it is past
36        # the end) then we don't need to fetch it.
37        fetch_first_segment = False
38    elif (offset == (first_segment_of_write * segsize)) and \
39            ((offset + length) >= ((first_segment_of_write+1) * segsize)):
40        # If we are overwriting the entire segment, then no need to fetch the
41        # current version.
42        fetch_first_segment = False
43
44    # If the last segment is also the first segment, then we're done.
45    if last_segment_of_write == first_segment_of_write:
46        return (first_segment, fetch_first_segment, first_segment, fetch_first_segment)
47
48    # Now let's figure out if we need to fetch the last segment.
49    fetch_last_segment = True
50
51    if last_segment_of_write > last_segment_of_current:
52        # If it is a segment that doesn't currently exist at all (it is past
53        # the end) then we don't need to fetch it.
54        fetch_last_segment = False
55    elif last_segment_of_write == last_segment_of_current:
56        # If this is the last segment of the current file and we are
57        # overwriting all of the bytes in this segment, then we don't need to fetch it.
58        if offset + length >= filesize:
59            fetch_last_segment = False
60    else:
61        # If we are overwriting the entire segment, then no need to fetch the
62        # current version.
63        if (offset + length) % segsize == 0:
64            fetch_last_segment = False
65       
66    return (first_segment, fetch_first_segment, last_segment, fetch_last_segment)