Merge branch 'master' into 7490-datamanager-dont-die-return-error
[arvados.git] / sdk / python / arvados / _ranges.py
1 import logging
2
3 _logger = logging.getLogger('arvados.ranges')
4
5 # Log level below 'debug' !
6 RANGES_SPAM = 9
7
8 class Range(object):
9     def __init__(self, locator, range_start, range_size, segment_offset=0):
10         self.locator = locator
11         self.range_start = range_start
12         self.range_size = range_size
13         self.segment_offset = segment_offset
14
15     def __repr__(self):
16         return "Range(%r, %r, %r, %r)" % (self.locator, self.range_start, self.range_size, self.segment_offset)
17
18     def __eq__(self, other):
19         return (self.locator == other.locator and
20                 self.range_start == other.range_start and
21                 self.range_size == other.range_size and
22                 self.segment_offset == other.segment_offset)
23
24 def first_block(data_locators, range_start):
25     block_start = 0L
26
27     # range_start/block_start is the inclusive lower bound
28     # range_end/block_end is the exclusive upper bound
29
30     hi = len(data_locators)
31     lo = 0
32     i = int((hi + lo) / 2)
33     block_size = data_locators[i].range_size
34     block_start = data_locators[i].range_start
35     block_end = block_start + block_size
36
37     # perform a binary search for the first block
38     # assumes that all of the blocks are contiguous, so range_start is guaranteed
39     # to either fall into the range of a block or be outside the block range entirely
40     while not (range_start >= block_start and range_start < block_end):
41         if lo == i:
42             # must be out of range, fail
43             return None
44         if range_start > block_start:
45             lo = i
46         else:
47             hi = i
48         i = int((hi + lo) / 2)
49         block_size = data_locators[i].range_size
50         block_start = data_locators[i].range_start
51         block_end = block_start + block_size
52
53     return i
54
55 class LocatorAndRange(object):
56     def __init__(self, locator, block_size, segment_offset, segment_size):
57         self.locator = locator
58         self.block_size = block_size
59         self.segment_offset = segment_offset
60         self.segment_size = segment_size
61
62     def __eq__(self, other):
63         return  (self.locator == other.locator and
64                  self.block_size == other.block_size and
65                  self.segment_offset == other.segment_offset and
66                  self.segment_size == other.segment_size)
67
68     def __repr__(self):
69         return "LocatorAndRange(%r, %r, %r, %r)" % (self.locator, self.block_size, self.segment_offset, self.segment_size)
70
71 def locators_and_ranges(data_locators, range_start, range_size, limit=None):
72     """Get blocks that are covered by a range.
73
74     Returns a list of LocatorAndRange objects.
75
76     :data_locators:
77       list of Range objects, assumes that blocks are in order and contiguous
78
79     :range_start:
80       start of range
81
82     :range_size:
83       size of range
84
85     :limit:
86       Maximum segments to return, default None (unlimited).  Will truncate the
87       result if there are more segments needed to cover the range than the
88       limit.
89
90     """
91     if range_size == 0:
92         return []
93     resp = []
94     range_end = range_start + range_size
95
96     i = first_block(data_locators, range_start)
97     if i is None:
98         return []
99
100     # We should always start at the first segment due to the binary
101     # search.
102     while i < len(data_locators) and len(resp) != limit:
103         dl = data_locators[i]
104         block_start = dl.range_start
105         block_size = dl.range_size
106         block_end = block_start + block_size
107         _logger.log(RANGES_SPAM,
108             "%s range_start %s block_start %s range_end %s block_end %s",
109             dl.locator, range_start, block_start, range_end, block_end)
110         if range_end <= block_start:
111             # range ends before this block starts, so don't look at any more locators
112             break
113
114         if range_start >= block_start and range_end <= block_end:
115             # range starts and ends in this block
116             resp.append(LocatorAndRange(dl.locator, block_size, dl.segment_offset + (range_start - block_start), range_size))
117         elif range_start >= block_start and range_end > block_end:
118             # range starts in this block
119             resp.append(LocatorAndRange(dl.locator, block_size, dl.segment_offset + (range_start - block_start), block_end - range_start))
120         elif range_start < block_start and range_end > block_end:
121             # range starts in a previous block and extends to further blocks
122             resp.append(LocatorAndRange(dl.locator, block_size, dl.segment_offset, block_size))
123         elif range_start < block_start and range_end <= block_end:
124             # range starts in a previous block and ends in this block
125             resp.append(LocatorAndRange(dl.locator, block_size, dl.segment_offset, range_end - block_start))
126         block_start = block_end
127         i += 1
128     return resp
129
130 def replace_range(data_locators, new_range_start, new_range_size, new_locator, new_segment_offset):
131     """
132     Replace a file segment range with a new segment.
133
134     NOTE::
135     data_locators will be updated in place
136
137     :data_locators:
138       list of Range objects, assumes that segments are in order and contiguous
139
140     :new_range_start:
141       start of range to replace in data_locators
142
143     :new_range_size:
144       size of range to replace in data_locators
145
146     :new_locator:
147       locator for new segment to be inserted
148
149     :new_segment_offset:
150       segment offset within the locator
151
152     """
153     if new_range_size == 0:
154         return
155
156     new_range_end = new_range_start + new_range_size
157
158     if len(data_locators) == 0:
159         data_locators.append(Range(new_locator, new_range_start, new_range_size, new_segment_offset))
160         return
161
162     last = data_locators[-1]
163     if (last.range_start+last.range_size) == new_range_start:
164         if last.locator == new_locator:
165             # extend last segment
166             last.range_size += new_range_size
167         else:
168             data_locators.append(Range(new_locator, new_range_start, new_range_size, new_segment_offset))
169         return
170
171     i = first_block(data_locators, new_range_start)
172     if i is None:
173         return
174
175     # We should always start at the first segment due to the binary
176     # search.
177     while i < len(data_locators):
178         dl = data_locators[i]
179         old_segment_start = dl.range_start
180         old_segment_end = old_segment_start + dl.range_size
181         _logger.log(RANGES_SPAM,
182             "%s range_start %s segment_start %s range_end %s segment_end %s",
183             dl, new_range_start, old_segment_start, new_range_end,
184             old_segment_end)
185         if new_range_end <= old_segment_start:
186             # range ends before this segment starts, so don't look at any more locators
187             break
188
189         if  old_segment_start <= new_range_start and new_range_end <= old_segment_end:
190             # new range starts and ends in old segment
191             # split segment into up to 3 pieces
192             if (new_range_start-old_segment_start) > 0:
193                 data_locators[i] = Range(dl.locator, old_segment_start, (new_range_start-old_segment_start), dl.segment_offset)
194                 data_locators.insert(i+1, Range(new_locator, new_range_start, new_range_size, new_segment_offset))
195             else:
196                 data_locators[i] = Range(new_locator, new_range_start, new_range_size, new_segment_offset)
197                 i -= 1
198             if (old_segment_end-new_range_end) > 0:
199                 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))
200             return
201         elif old_segment_start <= new_range_start and new_range_end > old_segment_end:
202             # range starts in this segment
203             # split segment into 2 pieces
204             data_locators[i] = Range(dl.locator, old_segment_start, (new_range_start-old_segment_start), dl.segment_offset)
205             data_locators.insert(i+1, Range(new_locator, new_range_start, new_range_size, new_segment_offset))
206             i += 1
207         elif new_range_start < old_segment_start and new_range_end >= old_segment_end:
208             # range starts in a previous segment and extends to further segments
209             # delete this segment
210             del data_locators[i]
211             i -= 1
212         elif new_range_start < old_segment_start and new_range_end < old_segment_end:
213             # range starts in a previous segment and ends in this segment
214             # move the starting point of this segment up, and shrink it.
215             data_locators[i] = Range(dl.locator, new_range_end, (old_segment_end-new_range_end), dl.segment_offset + (new_range_end-old_segment_start))
216             return
217         i += 1