Source Code for Module arvados._ranges

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