1 from __future__ import division
2 from builtins import object
5 _logger = logging.getLogger('arvados.ranges')
7 # Log level below 'debug' !
11 __slots__ = ("locator", "range_start", "range_size", "segment_offset")
13 def __init__(self, locator, range_start, range_size, segment_offset=0):
14 self.locator = locator
15 self.range_start = range_start
16 self.range_size = range_size
17 self.segment_offset = segment_offset
20 return "Range(%r, %r, %r, %r)" % (self.locator, self.range_start, self.range_size, self.segment_offset)
22 def __eq__(self, other):
23 return (self.locator == other.locator and
24 self.range_start == other.range_start and
25 self.range_size == other.range_size and
26 self.segment_offset == other.segment_offset)
28 def first_block(data_locators, range_start):
31 # range_start/block_start is the inclusive lower bound
32 # range_end/block_end is the exclusive upper bound
34 hi = len(data_locators)
37 block_size = data_locators[i].range_size
38 block_start = data_locators[i].range_start
39 block_end = block_start + block_size
41 # perform a binary search for the first block
42 # assumes that all of the blocks are contiguous, so range_start is guaranteed
43 # to either fall into the range of a block or be outside the block range entirely
44 while not (range_start >= block_start and range_start < block_end):
46 # must be out of range, fail
48 if range_start > block_start:
53 block_size = data_locators[i].range_size
54 block_start = data_locators[i].range_start
55 block_end = block_start + block_size
59 class LocatorAndRange(object):
60 __slots__ = ("locator", "block_size", "segment_offset", "segment_size")
62 def __init__(self, locator, block_size, segment_offset, segment_size):
63 self.locator = locator
64 self.block_size = block_size
65 self.segment_offset = segment_offset
66 self.segment_size = segment_size
68 def __eq__(self, other):
69 return (self.locator == other.locator and
70 self.block_size == other.block_size and
71 self.segment_offset == other.segment_offset and
72 self.segment_size == other.segment_size)
75 return "LocatorAndRange(%r, %r, %r, %r)" % (self.locator, self.block_size, self.segment_offset, self.segment_size)
77 def locators_and_ranges(data_locators, range_start, range_size, limit=None):
78 """Get blocks that are covered by a range.
80 Returns a list of LocatorAndRange objects.
83 list of Range objects, assumes that blocks are in order and contiguous
92 Maximum segments to return, default None (unlimited). Will truncate the
93 result if there are more segments needed to cover the range than the
100 range_end = range_start + range_size
102 i = first_block(data_locators, range_start)
106 # We should always start at the first segment due to the binary
108 while i < len(data_locators) and len(resp) != limit:
109 dl = data_locators[i]
110 block_start = dl.range_start
111 block_size = dl.range_size
112 block_end = block_start + block_size
113 _logger.log(RANGES_SPAM,
114 "L&R %s range_start %s block_start %s range_end %s block_end %s",
115 dl.locator, range_start, block_start, range_end, block_end)
116 if range_end <= block_start:
117 # range ends before this block starts, so don't look at any more locators
120 if range_start >= block_start and range_end <= block_end:
121 # range starts and ends in this block
122 resp.append(LocatorAndRange(dl.locator, block_size, dl.segment_offset + (range_start - block_start), range_size))
123 elif range_start >= block_start and range_end > block_end:
124 # range starts in this block
125 resp.append(LocatorAndRange(dl.locator, block_size, dl.segment_offset + (range_start - block_start), block_end - range_start))
126 elif range_start < block_start and range_end > block_end:
127 # range starts in a previous block and extends to further blocks
128 resp.append(LocatorAndRange(dl.locator, block_size, dl.segment_offset, block_size))
129 elif range_start < block_start and range_end <= block_end:
130 # range starts in a previous block and ends in this block
131 resp.append(LocatorAndRange(dl.locator, block_size, dl.segment_offset, range_end - block_start))
132 block_start = block_end
136 def replace_range(data_locators, new_range_start, new_range_size, new_locator, new_segment_offset):
138 Replace a file segment range with a new segment.
141 data_locators will be updated in place
144 list of Range objects, assumes that segments are in order and contiguous
147 start of range to replace in data_locators
150 size of range to replace in data_locators
153 locator for new segment to be inserted
156 segment offset within the locator
159 if new_range_size == 0:
162 new_range_end = new_range_start + new_range_size
164 if len(data_locators) == 0:
165 data_locators.append(Range(new_locator, new_range_start, new_range_size, new_segment_offset))
168 last = data_locators[-1]
169 if (last.range_start+last.range_size) == new_range_start:
170 if last.locator == new_locator and (last.segment_offset+last.range_size) == new_segment_offset:
171 # extend last segment
172 last.range_size += new_range_size
174 data_locators.append(Range(new_locator, new_range_start, new_range_size, new_segment_offset))
177 i = first_block(data_locators, new_range_start)
181 # We should always start at the first segment due to the binary
183 while i < len(data_locators):
184 dl = data_locators[i]
185 old_segment_start = dl.range_start
186 old_segment_end = old_segment_start + dl.range_size
187 _logger.log(RANGES_SPAM,
188 "RR %s range_start %s segment_start %s range_end %s segment_end %s",
189 dl, new_range_start, old_segment_start, new_range_end,
191 if new_range_end <= old_segment_start:
192 # range ends before this segment starts, so don't look at any more locators
195 if old_segment_start <= new_range_start and new_range_end <= old_segment_end:
196 # new range starts and ends in old segment
197 # split segment into up to 3 pieces
198 if (new_range_start-old_segment_start) > 0:
199 data_locators[i] = Range(dl.locator, old_segment_start, (new_range_start-old_segment_start), dl.segment_offset)
200 data_locators.insert(i+1, Range(new_locator, new_range_start, new_range_size, new_segment_offset))
202 data_locators[i] = Range(new_locator, new_range_start, new_range_size, new_segment_offset)
204 if (old_segment_end-new_range_end) > 0:
205 data_locators.insert(i+2, Range(dl.locator, new_range_end, (old_segment_end-new_range_end), dl.segment_offset + (new_range_start-old_segment_start) + new_range_size))
207 elif old_segment_start <= new_range_start and new_range_end > old_segment_end:
208 # range starts in this segment
209 # split segment into 2 pieces
210 data_locators[i] = Range(dl.locator, old_segment_start, (new_range_start-old_segment_start), dl.segment_offset)
211 data_locators.insert(i+1, Range(new_locator, new_range_start, new_range_size, new_segment_offset))
213 elif new_range_start < old_segment_start and new_range_end >= old_segment_end:
214 # range starts in a previous segment and extends to further segments
215 # delete this segment
218 elif new_range_start < old_segment_start and new_range_end < old_segment_end:
219 # range starts in a previous segment and ends in this segment
220 # move the starting point of this segment up, and shrink it.
221 data_locators[i] = Range(dl.locator, new_range_end, (old_segment_end-new_range_end), dl.segment_offset + (new_range_end-old_segment_start))